The Tower Of Hanoi

The Tower Of Hanoi problem is perhaps the most frequently asked recursion-based problem in interviews and examinations. Perhaps the most succinct explanation of this problem can be found in Wikipedia here .

PROBLEM STATEMENT :
A set of n disks are kept on a peg A such that each disk lies on top of a disk larger in size than it. This set of disks is to be moved to another peg B; always minding the consistency that a smaller disk lies on a larger disk. We can use an auxiliary peg C for our aid.

ALGORITHM :
We use recursion to solve the problem. Consider an auxiliary function moveTower that accepts the parameters sourceTower, destTower, auxTower and numberOfDisks. This function moves numberOfDisks disks (<= n) from the sourceTower to the destTower using the auxTower. We follow the recursive idea that in order to move n disks from A to B using C as auxiliary, we move the top n-1 disks from A to C using auxiliary and then move the remaining 1 disk (the largest disk) from A to B. The problem now shortens to moving n-1 disks from C to B using A as auxiliary. Thus we see that after each iteration, the problem gets smaller and thus there will be a terminating condition. The terminating condition of the recursion is that n becomes 1. 1 disk can be moved in 1 move.

Algorithm moveTower (sourceTower, destTower, auxTower, numberOfDisks)

1. if (numberOfDisks == 1) then move disk from sourceTower to destTower and exit //terminating condition
2. else{
3.      moveTower(sourceTower, auxTower, destTower, numberOfDisks - 1)
4.      moveTower(sourceTower, destTower, auxTower, 1)   
5.      moveTower(auxTower, destTower, sourceTower, numberOfDisks-1)
6. } if - else ends 

The java code that simulates the Tower Of Hanoi problem is as follows:

ANALYSIS :
If T(n) is the time required to transfer n disks from sourceTower to destTower, then by the above algorithm, T(n) is distributed into 2 transfers of  n-1 disks and a transfer of 1 disk. Thus,
                                                 T(n) =  2T(n-1) + T(1)
But how many moves do we require to transfer n disks from A to B? We can prove by mathematical induction that the minimum number of moves required are 2ⁿ - 1. The 3 steps of mathematical induction are :

1. Basic Case : For n = 1 i.e if there is only 1 disk, then we directly transfer the disk from A to B in 1 move. 2¹ - 1 = 1. Hence, the equation holds true for the base case.
2. Assumption : We now assume that the equation holds true for all integers 1 to n-1.
3. Induction : Since the relation holds true for integers from 1 to n-1, we now check the relation for n number of disks. To transfer n disks from A to B, we first move n-1 disks from A to C in 2^n-1 - 1 moves, then transfer 1 disk from A to B in 1 move and lastly move n-1 disks from C to B in 2^n-1 - 1 moves. Thus, the total number of moves are 2^n-1 - 1 + 2^n-1 - 1 + 1 = 2*2^n-1 - 1 =
   2ⁿ - 1. Thus, we have "induced" the relation to all integers.

The Tower Of Hanoi problem is the best example where the advantages of using a recursive method far outweighs its disadvantages. While recursion may not be advisable in cases of problems like the Fibonacci series because of the overhead in calling a function recursively and maintaining stacks of duplicate variables, recursion proves to be a boon in Tower Of Hanoi and is, indeed, in many aspects better than the iterative method.

Parentheses' Check

PROBLEM STATEMENT :
A mathematical expression will be inputted as a string. We need to check where the mathematical string is properly parenthesized. This includes checking for 2 conditions :

1. Every opening parenthesis should have a similar closing parenthesis.
2.  The order of the opening and closing of parentheses should be correct i.e. the parenthesis to open last should be closed first.

A correct expression would be ( { [x+y*z] [x+y] } )
An incorrect expression would be something like { [x+y} ]

NOTE : We are not interested in the variable expression within the parentheses. As long the expression is correctly parenthesized, we need not encumber ourselves with the underlying variables and their relations.

ALGORITHM : 
For rule no.1, we need to establish concurrency between the symbols i.e. we need to have a '}' for every '{' only. '}' doesn't correspond to '['. And since according to rule no.2, the last parenthesis to be opened should be the first to be closed, we use a LIFO kind of data structure: a stack.

We scan the expression from left to right character by character. Whenever we encounter an opening parenthesis, we push it into a stack. Whenever we find a closing parenthesis, we compare it with the top of the stack and if the correspondence relation holds true, we pop the stack. We ignore all other characters.

The java code that follows the above algorithm is given in the form of a Gist below :
Each of the routines push, pop and checkForParentheses takes O(1) time. Thus, for a n-character long string, the main function takes O(n) time, ignoring the overheads for calling a function. 

Thus we see another important application of the data structure stack. Parentheses check is an important routine in expression-checking as well as expression-evaluation.

The 3SUM Problem

Another very frequently-visited problem is "The 3SUM Problem", sometimes also known as the Subset Sum Problem This problem lays path to many concepts in Algorithmic Science such as sub-quadratic time problems, 3SUM hard problems, etc.

INPUT :
A sequence (taken in as an array A) of n distinct integers, preferably whose absolute value (modulus) can be given by a polynomial p(n).

OUTPUT :
The combinations of 3 integers from the sequence whose sum equals 0 i.e. the numbers i, j and k such that i+j+k = 0. Note that the integers i, j, k have to be distinct and the combinations themselves have to be distinct. For example, i,j,k and k,j,i represent the same combination and therefore, are not distinct.


THE "BRUTE FORCE" METHOD :
The obvious and perhaps the most trivial method would be to scan the array 3 times in one direction (to ensure distinctness of the combinations) and take every possible combination of 3 integers and check whether their sum is 0. For an n-input array, the number of combinations will be ⁿC₃ = O(n³). The following algorithm is an illustration of the above method.

Algorithm 3SUM (A, n) 

1. for i = 0 upto (n-2)
2.        for j = i+1 upto (n-1)
3.              for k = j+1 upto n
4.                     if (A[i] + A[j] + A[k] == 0) then print A[i], A[j], A[k] 

Thus, we see that the algorithm is nothing but 3 nested for loops giving a performance of O(n³). Can we do any better?

THE BINARY-SEARCH METHOD :
This method uses the idea that instead of traversing the array for 3 elements requiring 3 nested for loops, we can traverse the array only 2 times using the following simple manipulation:
                            if x+y+z = 0, then z = - (x+y)
Thus, if we choose a particular "x" and a "y", we just need to search the array for the "z". This searching can be done by an efficient search technique, The Binary Search Technique. This technique, however requires us to first sort the array, hence that will be our first step. 

We assume a routine binarySearch(Array, low, high, key) which searches for "key" within the bounds "low" and "high" and returns the index of the key, if found or if not found; returns -1.

Algorithm 3SUM PLUS (A, n)

1. sort(A)
2. for i = 0 upto n
3.       for j = i+1 upto (n-1)
4.            k = binarySearch(A, j, n, -(A[i] + A[j]) )
5.            if(k != -1) then print A[i], A[j], k

The if statement is executed in O(1). We know that binarySearch has a performance of O(log₂n). However, it is called within 2 nested for loops i.e. ⁿC₂ = O(n²) times, thus giving the routine 3SUM PLUS  a performance of  O(n²*log₂n). Note that the method used for sorting can be anything from insertion (O(n²)) to merge sort (O(n*log₂n)) as they are both asymptotically smaller than O(n²*log₂n). However, can we do still better? (obviously we can, or else this question wouldnt be here!)

THE HASH MAP METHOD :
We continue with the above idea of traversing the array only twice instead of 3 times. We will prove later that the sorting technique used doesn't play a role in the final performance, so the only scope of improvement is in the search technique. We need a search technique faster than the Binary Search. Hash-based searching is an example. Searches performed using a hash table take O(1) if we know the hash index or the function that gives the hash index. Therefore, we will copy the entire array into a hash table and then inside the nested for loop, we search the hash table for the integer z = - (x+y). 

Algorithm 3SUM PLUS PLUS (A, n)

1. sort(A)
2. for i = 0 upto n
3.       hash.put(<unique key determined by a hash function>, A[i])
4. for ends
5. for i = 0 upto n
6.       for j = i+1 upto (n-1)
7.           k = hash.search(- (A[i] + A[j]) )
8.           if (k != null) then print A[i], A[j], k        
9.   nested for ends

Here again, we have 2 for loops nested giving O(n²). Thus again, the method used in sorting doesn't affect the overall performance. 3SUM PLUS PLUS routine takes O(n²) which is asymptotically better than O(n²*log₂n) and O(n³). 

Wikipedia offers another interesting method which also gives O(n²) but does not use hash tables. Go, have a look here

FUN FACT : Although it hasn't been successfully proved that the 3SUM problem can't be solved faster than O(n²), no better algorithm has yet been found. Do you have it in you to find it? Leave us a comment!

The Maximum Subarray Problem

Let us take another common problem in the world of computing and see various algorithms to solve it. Once again, we will start will a trivial or a "naive" method and then analyze and try to improve the efficiency of our algorithms.

INPUT :
A sequence of n real numbers (can be positive or negative)  which may indicate real-world numbers like stock prices over a period, or the business profit sheet of an individual over a period, where negative numbers indicate loss.
OUTPUT :
A smaller sequence from the original sequence wherein the numbers' sum is the maximum. This sequence may indicate the period wherein its most profitable to hold a stock as its value is the maximum or the period wherein the individual made the maximum profit. Since, practically, the sequence of numbers will be inputted as an array by the computer, we need to find the maximum non-empty contiguous subarray of that array.

1) THE TRIVIAL METHOD :
The trivial method is to traverse the entire array once and look for the difference in every combination-pair of the numbers. For an n-element array, the number of possible combinations will be ⁿC₂= n(n-1)/2. This takes ϴ(n²) asymptotically. (Recall that ϴ notation denotes asymptotically bound function between two functions c₁f(n) and c₂f(n), thus giving the "average case".) Also, the comparison of the various differences will take a constant amount of time, thus giving the trivial method a Ω(n²).

2) THE DIVIDE AND CONQUER METHOD :
The Divide and Conquer approach is a very common method in Computer Science problems. It works on 3 basic stages:

1. Divide
2. Solve/Conquer
3. Merge

Recursion is very widely used in divide-and-conquer approaches. Our divide-and-conquer algorithm works on the principle that an array can be divided into m (preferably equal) parts and then we can search each part-array for the maximum subarray. The combination of the maximum number of such contiguous part-subarrays will eventually merge into the required subarray. For our convenience, let us take m to be 2. Our algorithm has the following stages.

1. Recursively divide the array into 2 equal parts
2. Find the maximum subarray on the left half of the array
3. Find the maximum subarray on the right half of the array
4. Find the maximum subarray that "crosses over" the division i.e. that contains the point of division

Our pseudocode of the above algorithm accepts 3 parameters: The array A, a starting index "low", an ending index "high" and returns 3 parameters: a starting index lower, an ending index "higher" and the maximum sum "maxSum".

Algorithm findMaxSubarray(A, low, high)

1. if low == high then return (low, high, A[low])
2. mid = ⌊(low+high)/2⌋
3. (left-low, left-sum, left-high) = findMaxSubarray(A, low, mid)
4. (cross-low, cross-sum, cross-high) = findMaxCrossOverSubarray(A, low, mid, high)
5. (right-low, right-sum, right-high) = findMaxSubarray(A, mid, high)
6. if left-sum > cross-sum and left-sum > right-sum then return (left-low, left-sum, left-high)
7. else if right-sum > cross-sum and right-sum > left-sum then return (right-low, right-sum, right-high)
8. else return (cross-low, cross-sum, cross-high)

The subroutine "findMaxCrossOverSubarray" returns the maximum subarray that "crosses-over" the midpoint "mid". The pseudocode of this subroutine is:

Algorithm findMaxCrossOverSubarray(A, low, mid, high)

1. leftSum = rightSum = -∞
2. leftIndex = rightIndex = -∞
3. sum = 0
4. for i = mid downto low
5. sum += A[i]
6. if leftSum < sum then leftSum = sum, leftIndex = i
7. for j = mid upto high
8. sum += A[j]
9. if rightSum < sum then rightSum = sum, rightIndex = j
10. return (leftIndex, leftSum+rightSum, rightIndex)

It can be proved that the above pseudocodes take ϴ(n*log₂n), which is way better than the trivial method. The java version of the above pseudocodes is as follows:

NOTE :

As we are attempting to return more than one parameter from the function, we cannot do it in Java. Thus, we encapsulate all the 3 different entities into a user-defined data type (class). This introduces the overhead of instantiating the class objects and their handling. Thus, we see, that although the time asymptotically remains ϴ(n*log₂n), the overhead memory allocation increases in Java. In languages like Python where functions can return more than one variable, this overhead is avoided. This is a classic example of the constraints introduced during actual application of algorithms into languages.

KADANE'S ALGORITHM:
We end our discussion with the best possible algorithm for the problem stated. Kadane introduced an algorithm to solve the maximum subarray problem in O(n) since it is nothing but a for loop which is traversed n times. Kadane's algforithm is an implementation of "the two finger rule" which states that one finger is kept at the first index of the array and another finger is allowed to scan through the array finding the sum of the elements as it goes". The java program which implements Kadane's Algorithm is:

Evaluating a polynomial and Horner's Rule

Given the polynomial

where  are real numbers, we wish to evaluate the polynomial i.e. find it's value at a given value of x, say x₀. This value represents the value of p(x), which can be any function under analysis at the point x₀ in space.

INPUT :

1. The value of x₀
2. The values of the coefficients a₀...a_n

OUTPUT :

The value of the polynomial at x.


THE "NAIVE" METHOD :

The most basic and preliminary method would be to separately evaluate each term in the expression and then successively add all the terms (monomials). Let us consider p(x) to be a polynomial of degree n. It, then contains, at the most, n+1 terms (from degree 0 to n). The naive method, then, requires at the most n additions to add those n+1 terms. In fact, these n additions are absolutely necessary for any algorithm used.

Now lets consider the number of multiplications involved. An n-degree polynomial will have at the most n co-efficients. We need to perform 1 multiplication for each, giving us a total of n multiplications. This factor, too, is independent of the algorithm chosen. Additionally, when we calculate the powers of x, we multiply x by itself each time to get a higher power (we consider a machine where power calculation is NOT O(1), i.e. it cannot be performed in a single step, which is true in most cases). Therefore, to get xⁿ, we need to perform n multiplications. Therefore, maximum total number of multiplications for power will be:
                                                      ∑(i=0 to n-1) {i} = n(n-1)/2
i.e. (n²- n)/2 multiplications. But we can avoid the need to multiply n times to get xⁿ. We can use iterative methods to increase the efficiency, because xⁿ is x*x^n-1 and so on. Thus, by using iterative functions, we need only (n-1) multiplications.
Therefore, in the basic method, we need a total of n additions and (n²-n)/2 + n i.e. (n²+n)/2 multiplications, giving O(n²). However, in the iterative method, we need n - 1 + n = 2n - 1 multiplications along with n additions, still giving O(n). Can we do any better?

HORNER'S ALGORITHM :

Horner's algorithm provides a way of evaluating any polynomial in ϴ(n). It is just another way of representing every polynomial by iteratively multiplying the variable 'x' to a shorter sequence. Horner's method can be represented as follows:


The algorithm for Horner's method is pretty straightforward:

1.  y = 0                                         ϴ(1) 1 time
2.  for i = n downto 0                       ϴ(1) n+1 times
3. y = ai + x*y                                ϴ(1)                                     n times

Thus, the algorithm takes ϴ(n) which is way better than the naive method. Also, Horner's method takes n additions and n multiplications as can be seen from the algorithm above. Thus, it is more efficient i terms of space as well.

Horner's algorithm can be extended to find the "approximate roots" of the equation. If the Horner's equation above is observed, we find that each pair of parantheses enclose 1 polynomial smaller than p(x). Thus we can "break down" any given polynomial into smaller polynomials by dividing it by a given factor and subtracting it from a constant term. The constant term, thus becomes, the remainder and the constant factor, the divisor. For example,
                  x³ - 6x² + 11x - 6 can be represented in Horner's form as -6 + x (11 + x (-6 + x (1)))
When x-1 = 0; x = 1. This implies, that if we divide the above polynomial by (x-1), we can consider 1 to be a value of x. The above polynomial can, thus, be divided by (x-1) (here, the constant factor and divisor is 1) to get the quotient x² - 5x + 6 and remainder 0. This leads us to a very important format in Mathematics and in Computer Science: The Synthetic Division.

 x₀│   x³    x²    x¹    x⁰
 3 │   2    −6     2    −1
   │         6     0     6    
   └────────────────────────
       2     0     2     5

Notice the similarity between the algorithm mentioned above and the synthetic division performed here. The coefficient of x³ which is equivalent to a_n for n = 3 is directly copied and the later coefficients (a_n-1 to a₀) are multiplied by the value of x(i.e.3) to get the coefficients of a smaller polynomial (2x² + 0x + 2) and remainder 5. Thus, we see that by mere manipulation of coefficients as in the Horner's rule, we can not only evaluate any polynomial, but can also calculate the approximate roots of the same.

Paint Shapes - Paint With File-Handling

As promised, we are back with a whole new Paint Applet, this time using javax.swing and JFrame. If you havent seen our previous attempt at the Paint Brush Applet, you can view it here. The bugs that we encountered last time have been somewhat solved in this applet.

First of all, the output looks something like this:

As you can see, one can draw rectangle, round rectangle and ovals to their file. The applet provides facility to save their file, rename it, save it in a different location and to view saved files. 

You can view the actual source code here. We have tried our best to comment wherever necessary. Still, if you have any doubts or any kind of ambiguity, please feel free to leave a comment: 

BUGS AND HOW THEY ARE SOLVED:

Now we will show how the 3 bugs mentioned in Paint Brush Applet are solved.

1. The shapes that are added do not now disappear when paint() is called again (implicitely and explicitely). This is because all shapes are stored in an ArrayList of the name "shapes". The paint function simply draws all the shapes in the list again, thus losing none!
2.  File Handling concepts are used to store and open files. Note that the files thus created do not have any extensions like .jpg, etc. and are thus read by the Windows System as of the type "file". It cannot be rendered effectively by any application other than this applet. Results may/may not be different in Linux-based systems because of its "Everything is a file" policy.
3.  The "drawing area" is defined separately and does not include the menu bar, thus solving this error.

Basic Calculator Applet

After about 1-2 days of work, I finally created a Java Applet of a simple binary calculator which performs binary operations on positive numbers. The main aim was to solve using this calculator an expression like:

32+45/89*6 = 5.19101

from left-to-right, step by step i.e. computing two variables at a time.(so you enter 32 + 45 = and the result (77) then becomes your first operand)

The idea was not to give a demonstration of the calculator algorithm, but to show the use of the applet class and the basic components like buttons, text fields, etc. Thus, this can be the ideal code for anyone who is planning to make a small project using java applet class. The functions and the overall view and flow of the code is deliberately made very simple so that even those who are not-so-experienced with applets can understand.

I encourage the readers to go through the code and mail/leave a comment if you have doubts, suggestions or if you made an improvised version of the code!