Data Structures and Algorithms

[celebi]

If you are attending in interview in India, be prepared for questions on very theoretical subjects like these

Let us revise and get prepared on this topic. I will try to post notes and points to remember, so that we can brush thro this set before attending any interview.

[celebi]

Let us start with very basic definitions and principles.

Object-Oriented Design Goals:Software implementations should achieve robustness, adaptability, and reusability.
Robustness: Every good programmer wants to develop software that is correct, which means that a program produces the right output for all the anticipated inputs in the program's application. In addition, we want software to be robust, that is, capable of handling unexpected inputs that are not explicitly defined for its application.

Adaptability: Modern software applications, such as Web browsers and Internet search engines, typically involve large programs that are used for many years. Software, therefore, needs to be able to evolve over time in response to changing conditions in its environment. Thus, another important goal of quality software is that it achieves adaptability (also called evolvability). Related to this concept is portability, which is the ability of software to run with minimal change on different hardware and operating system platforms.

Reusability: Going hand in hand with adaptability is the desire that software be reusable, that is, the same code should be usable as a component of different systems in various applications.

Object-Oriented Design Principles:
Chief among OO Principles: Abstraction, Encapsulation and Modularity

Abstraction:
The notion of abstraction is to distill a complicated system down to its most fundamental parts and describe these parts in a simple, precise language.
Applying the abstraction paradigm to the design of data structures gives rise to abstract data types (ADTs). An ADT is a mathematical model of a data structure that specifies the type of data stored, the operations supported on them, and the types of parameters of the operations. An ADT specifies what each operation does, but not how it does it. In Java, an ADT can be expressed by an interface, which is simply a list of method declarations, where each method has an empty body.
An ADT is realized by a concrete data structure, which is modeled in Java by a class. A Java class is said to implement an interface if its methods include all the methods declared in the interface, thus providing a body for them.

Encapsulation: states that different components of a software system should not reveal the internal details of their respective implementations.

Modularity: refers to an organizing principle for code in which different components of a software system are divided into separate functional units.
A natural way to organize various structural components of a software package is in a hierarchical fashion, which groups similar abstract definitions together in a level-by-level manner that goes from specific to more general as one traverses up the hierarchy.

Inheritance and Polymorphism:
To take advantage of hierarchical relationships, which are common in software projects, the object-oriented design approach provides ways of reusing code.
Inheritance allows the design of general classes(base class) that can be specialized to more particular classes(subclass), with the specialized classes(subclass) reusing the code from the general class(base class).
Polymorphism refers to the ability of an object variable to take different forms.
Some object-oriented languages, such as Java, also provide a useful technique related to polymorphism, which is called method overloading. Overloading occurs when a single class T has multiple methods with the same name, provided each one has a different signature. The signature of a method is a combination of its name and the type and number of arguments that are passed to it.
Inheritance, polymorphism, and method overloading support the development of reusable software.

[celebi]

Insertion sort Algorithm:

We start with the first character in the array. One character by itself is already sorted. Then we consider the next character in the array. If it is smaller than the first, we swap them and form the sorted subset. Now, the third element is placed in the right position in the sorted subset and a new sorted subset is formed.

High Level Description:
Algorithm InsertionSort(A):
Input: An Array A of n Comparable elements
Output: the Array A with elements rearranged in ascending order.
For i <- 1 to n-1 do
Insert A at it’s proper location in {A[0], A[1],..A[i-1]}
This algorithm is called "insertion-sort", because each iteration of the main inserts the next element into the sorted part of the array that comes before it.

public static void insertSort(int[] A){
 for(int i = 1; i < A.length; i++){
   int value = A[i];
   int j = i - 1;
   while(j >= 0 && A[j] > value){
     A[j + 1] = A[j];
     j = j - 1;
   }
   A[j + 1] = value;
 }
}

An interesting thing happens in the insertion-sort algorithm if the array is already sorted. In this case, the inner loop does only one comparison, determines that there is no swap needed, and returns back to the outer loop. That is, we perform only one iteration of the inner loop for each iteration of the outer loop. Thus, in this case, we perform a minimum number of comparisons. Of course, we might have to do a lot more work than this if the input array is extremely out of order. In fact, we will have to do the most work if the input array is in decreasing order.

It is a O(n²) sorting algorithm

-----------------------------------------------
P.S:
In Java, java.util.Arrays.sort(A) sorts the array A using the natural ordering of its elements.