Wednesday, July 28, 2010

Inheritance

Inheritance
Inheritance is similar in Java and C++. Java uses the extends keyword instead of the : token. All inheritance in Java is public inheritance; there is no analog to the C++ features of private and protected inheritance.

Calling base class constructor
In java, we can use super keyword.

super(parameter-list);

eg.
//X is super class, with attributes width, height, depth and has constructor for 3 attributes.

class Y extends X
{
  double weight; // weight of box
  // initialize width, height, and depth using super()
  Y(double w, double h, double d, double m) {
  super(w, h, d); // call superclass constructor
  weight = m;
   }
}

2nd use of super in java

The second form of super acts somewhat like this, except that it always refers to 

the



 superclass of the subclass in which it is used. This usage has the following 

general form:









super.member

Here, member can be either a method or an instance variable.
eg.
// Using super to overcome name hiding.
class A {
int i;
}
// Create a subclass by extending class A.
class B extends A {
int i; // this i hides the i in A
  B(int a, int b) {
   super.i = a; // i in A
   i = b; // i in B
  }
  void show() {
    System.out.println("i in superclass: " + super.i);
    System.out.println("i in subclass: " + i);
   }
}

Multilevel inheritance - Base class constructor is called 1st.



// Demonstrate when constructors are called.




// Create a super class.
class A {
A() {
System.out.println("Inside A's constructor.");
}
}
// Create a subclass by extending class A.
class B extends A {
B() {
System.out.println("Inside B's constructor.");
}
}
// Create another subclass by extending B.
class C extends B {
C() {
System.out.println("Inside C's constructor.");
}
}
class CallingCons {
public static void main(String args[]) {
C h a p t e r 8 : I n h e r i t a n c e 207
THE JAVA LANGUAGE
C c = new C();
}
}
The output from this program is shown here:
Inside A’s constructor
Inside B’s constructor
Inside C’s constructor




Primary data types

Some udfs for arrays in c

1D arrays
Printing 1 D arrays
void printArray (int *array,int size)
{
int i;
for (i = 0; i < size; i++)
     printf("%d",array[i]);
printf("\n");
}
2 D arrays 
Printing 2D arrays
void printArray(int **array, int m, int n)
{
           for(i = 0; i < nrows; i++)  
              for(j= 0; j < nrows; i++)  
                         printf("%d",array[i][j]);
}

Allocating and Deallocating 2 D Arrays 

/*   allocate2D
/*   function to dynamically allocate 2-dimensional array using malloc.
/*
/*   accepts an int** as the "array" to be allocated, and the number of rows and
/*   columns.
*/
void allocate2D(int** array, int nrows, int ncols) {
     
     /*  allocate array of pointers  */
     array = ( int** )malloc( nrows*sizeof( int* ) );
     
     /*  allocate each row  */
     int i;
     for(i = 0; i < nrows; i++) {
          array[i] = ( int* )malloc( ncols*sizeof( int ) );
     }
}
/*   deallocate2D
/*   corresponding function to dynamically deallocate 2-dimensional array using
/*   malloc.
/*
/*   accepts an int** as the "array" to be allocated, and the number of rows. 
/*   as with all dynamic memory allocation, failure to free malloc'ed memory
/*   will result in memory leaks
*/
void deallocate2D(int** array, int nrows) {
     
     /*  deallocate each row  */
     int i;
     for(i = 0; i < nrows; i++) {
          free(array[i]);
     }
     
     /*  deallocate array of pointers  */
     free(array);
     
}
/*   EXAMPLE USAGE:   
int** array1;

allocate2D(array1,1000,1000); //allocates a 1000x1000 array of ints

deallocate2D(array1,1000);    //deallocates the same array

*/

Friday, July 2, 2010

Common characterstics in dynamic programming

Dynamic Programming is an algorithm design technique for optimization problems: often minimizing or maximizing.
  • Like divide and conquer, DP solves problems by combining solutions to subproblems.
  • Unlike divide and conquer, subproblems are not independent.
Subproblems may share subsubproblems,
However, solution to one subproblem may not affect the solutions to other subproblems of the same problem. (More on this later.)
  • DP reduces computation by:
Solving subproblems in a bottom-up fashion.
Storing solution to a subproblem the first time it is solved.
Looking up the solution when subproblem is encountered again.
  • Key: determine structure of optimal solutions

Dynamic programming

Dynamic programming is a method for efficiently solving a broad range of search and optimization problems which exhibit the characteristics of overlappling subproblems and optimal substructure. I’ll try to illustrate these characteristics through some simple examples and end with an exercise. Happy coding!

Contents

Common Characterstics of Dynamic programming
Overlapping Subproblems
Optimal Substructure
The Knapsack Problem
Everyday Dynamic Programming








Everyday Dynamic Programming

The above examples might make dynamic programming look like a technique which only applies to a narrow range of problems, but many algorithms from a wide range of fields use dynamic programming. Here's a very partial list.
  1. The Needleman-Wunsch algorithm, used in bioinformatics.
  2. The CYK algorithm which is used the theory of formal languages and natural language processing.
  3. The Viterbi algorithm used in relation to hidden Markov models.
  4. Finding the string-edit distance between two strings, useful in writing spellcheckers.
  5. The D/L method used in the sport of cricket.
That's all for today. Cheers!