Algorithms & Common Data Structures

Module 1: Recursion

Recursion is about a recursive method that calls itself. A recursive method actually knows how to solve a base case (the simplest case). If the method is called with a base case, the method simply returns a result. Rule 1: always have at least one case that can be solved without using a recursion. If the method is called with a more complex problem, the method divides the problem into 2 conceptual pieces: a piece that the method knows how to do, and a piece that the method does not know how to do. Rule 2: any recursion call must make progress towards a base case.

Recursion: 3 requirements
1. function calls itself.
2. function has a 'base' or 'stopping' case.
3. function 'converges' towards the base case.

Eg 1: Find the factorial of a number N, i.e. N!
A good example:
public static long factorial (int n) {
if (n == 0)   // base case
   return 1;
else
   return n * factorial(n - 1); }   // factorial(n - 1) calls itself ; (n - 1) converges toward base case

A bad example:
public static long factorial (int n) {
if (n == 0)   //base case
   return 1;
else
   return n * (n - 1); }   // no recursion !

Another bad example:
public static long factorial (int n) {
if (n == 0)   //base case
   return 1;
else
   return n * factorial(n); }   // doesn't converge to base case !

Still another bad example:
public static long factorial (int n) {
// no base case here !
return n * factorial(n -1); }

Module 2: Algorithm Analysis

What is an algorithm? It is a clearly specified set of instructions the computer will follow to solve a problem.
In analysis, we are interested in the amount of resources, such as time and storage space, that the algorithm will require.

In algorithm analysis, we want to be able to answer this question: if two algorithms perform the same task, which should be used? Basically, only significant differences in efficiency should be considered when balanced with style.

The running time of an algorithm is a function of the input size. Hence, the amount of time that any algorithm takes to run almost always depends on the amount of input it must process.

Module 3: Sequential Search

A sequential search, by comparing an item with its adjacent item one at a time, most likely will occur when an array of items are unsorted. Why? Because the array is unsorted - which leave us little choice but to do a sequential search! It is the most inefficient searching algorithm. This tells us that if an array is sorted, we can peform more efficient search, such as binary search.

Module 4: Why do we need data structures?

Data structure is a representation of data and the operations allowed on the data. Data structures allow us to achieve an important object-oriented programming goal: component reuse. As it is shown later in the module, the data structures have recurring uses. Once each data structure has been implemented once, it can be used over and over again in various applications.

Module 5: Arrays

An array is a very common data representation. It is a basic mechanism for storing a collection of identical datatype entities. In Java, the array is not a primitive type. Instead, it behaves very much like an object.

In Java, each entity in the array is accessed via the array indexing operator [ ]. Bound checking is performed automatically.

Arrays are always indexed starting at 0. Thus, an array Z of three items stores Z[0], Z[1], Z[2].

An array is an object; it is declared like this:

int array1 [ ];

To have 100 ints, we issue the code:

array1 = new int [100];

A typical array loop would use:

for ( int i = 0, i < array1.length; i++ )

where array1.length (a method) returns the number of items in the array, that is 100.

For further information on arrays, refer to the recommended texts.

Module 6: Linked Lists

A linked list is another data representation. A linked list consists of a sequence of nodes. Each node contains:
. data items
. a link which references the next node in the list.

Linked lists are used to save space in contrast to arrays. It grows as new data is added and shrinks when data is deleted. It uses references to allocate memory dynamically.

Module 7: An assignment using recursion

Here is an assignment which uses recursion extensively.

The source programs and data files (HexDriver.java (not available), HexGrid.java, HexTest.txt, HexTestMast.txt) needed to run the application are shown here.

Copy all the files in a c: drive directory, say c:\test, and run it at:

c:\test>java HexDriver

Use HexTest.txt as your first test data file to have a feel of it. Then get other test data from HexTestMast.txt.