Arbitrary Precision Types In Java

QUESTION : 
What will be the output in the following code snippet?

Here's the snapshot of the output of the above function

NOTE : 
For built-in primitive data types such as int, long, double, etc. Java never throws any overflow or underflow exception, even though the size and the bounds for these data types is defined. 

Why? Because all data is internally stored by the JVM in binary-format. Thus, in actual memory, each variable, whether int or double is stored as a string of 1's and 0's. There is no concept of a "negative sign" in binary system. Negative numbers are stored in a special format called 2's complement . 

Hence, when the bound on any data type is reached and exceeded, the JVM simply reverses the sign of the number and prints the largest number in that sign. For example, in the above example, if we exceed 2147483647 which is the upper bound on int, the sign is reversed to negative and the value of smallest possible int is printed.

How do we avoid this? By casting the number into a larger data type and checking its value. If indeed, overflow or underflow has occurred, we can throw an exception and take the necessary rectification. Following is a code snippet which illustrates this.

What if overflow/underflow is a valid case in my problem?
Overflow is a valid case practically when problems involving very large numbers are present. In such cases, a way to implement variables is to use Arbitrary Precision Data Types. Java offers 2 arbitrary precision types : BigInteger and BigDecimal in java.math library.

The word "arbitrary precision" means that a variable of such type uses exactly as much space as required or mentioned. Thus, the precision is "set" according to our needs. Theoretically, there is no limitation to the size, the only limitations being that of insufficient memory. 

It is important to note that these data types are implemented internally as a collection of primitive data type. Thus, BigInteger is implemented as an array of ints. Also, these are implemented classes and not default and Java does not allow operator overloading. Thus, primitive operations such as addition, multiplication, power, etc. although present for these classes, do not use operators such as "+", "*" etc. Instead, they use functions such as a.add(b), a.multiply(b), etc. Since the use of functions is involved, the operations tend to be slower.

BigInteger is generally used for large integers and BigDecimal is used when extremely high levels of precisions is required (1000th decimal place of π).

Tic Tac Toe Applet

Here is a simple two-player Tic Tac Toe applet, just to get familiar with ActionListeners and basic GridView. Hopefully, the code below is well-commented and self-explanatory.


Here are some snaps of the output :

Smallest Sum Not Present In An Array

INPUT :
An array "A" of size "n".

OUTPUT :
The smallest integer that cannot be represented by the sum of any subset of "A".
E.g. if A = {1, 1, 1, 1}, output = 5; if A = {1, 2, 3, 4, 5}, output = 16

BRUTE FORCE METHOD :
The simplest and possibly the worst method would be to find out all the subsets of A and store each's sum in a Hash Map, then keep an integer i starting from 1 and check every time whether any sum equals to i. This method, is not only inefficient in nature, but also can be unsolvable in the sense that it can be, in worst cases, a NP-Complete problem .

PRE-REQUISUTE :
Before we actually look into our algorithm, let us do a little background. If someone asks you to give a list of numbers that can, with the sum of any of its sub-sets, give a result upto 2^k-1, what numbers do you choose? It is proven mathematically that you need a minimum of k numbers. And each of these numbers is a power of 2. 

So, if given k numbers, all subsequent powers of starting from 1; we can form all numbers from 1 to 2^k, from them. For example, an array {1, 2, 4, 8, 16} can be used to form all numbers from 1-31. This property forms the basis of Binary Number System. Thus, a 5 bit binary number can represent upto 2⁵-1 = 31 i.e. in total, 32 numbers.

OUR APPROACH :
We first sort the array in ascending order. Using the property mentioned above, we assume the entire array to be consisting of powers of 2 or, since its the decimal system, consisting of only consecutive numbers. If our assumption is true and the array indeed consists of only powers of 2 or consecutive integers, then the least number will be 2ⁿ-1, where n is the length of the array. If our assumption fails at any point, then we have found the "gap" in the sequence and the sum of all elements uptill that point is our answer.

We first sort the array in ascending order. We keep a pointer "i" such that "i" traverses the given array A. We also keep a variable "sno" which is the smallest sum initialized at 1. Then we check whether "sno" is lesser than A[ i ], if it is, then we print "sno". Otherwise, we increment "sno" by A[ i ].
 
Algorithm SmallestSum(A)

1. QuickSort(A);
2. sno = 1, i = 1;
3. Traverse A
4.          if(sno >= A[ i ])
5.                 sno += A[ i ];
6.           else return sno;
   

The Java implementation of QuickSort can be found here . The Java implementation of the algorithm is as follows: Note that, ignoring the time efficiency of QuickSort, the algorithm executes in O(n) time. Also note that, since we have extended the logic behind Binary Number System and negative numbers cannot be represented by this system (they are usually represented in sign-magnitude form, wherein the magnitude is always positive. Even the 2's complement form is just a positive number taken with different meaning, e.g. 1110 is either +15 or -2 in 2's complement form), our algorithm will not work for negative numbers. If you find any algorithm which does work for negative integers too, feel free to provide a link in the comments.

Intersection And Union Of Arrays

INPUT : Two Arrays "A" and "B" consisting of "n" and "m" elements respectively.

OUTPUT :
The union "U" of the two arrays and the intersection "I" of the arrays.
Example : if A = {1, 2, 4, 8}, B = {2, 6, 8, 10} then,
                U = {1, 2, 4, 6, 8, 10}, I = {2, 8}
Note : Since arrays are fundamentally different from Sets in the sense that every element is unique, we neglect the repeating elements in the union and the intersection as well i.e. if A = {1, 1, 1} and B = {1, 1} then, U = {1, 1, 1, 1, 1} and I = {1, 1}. This is because each element in an array is fundamentally unique.

OUR APPROACH :
 The first step is to sort each array in the same order (we used quick-sort to sort the array in ascending order). For each of the 2 functions (union and intersection), we maintain 2 pointers, one for each array. Now, we compare the elements at the ith position of A and jth position of B. Since the arrays are in increasing order, we know that if A[ i ] < B[ j ], the value equal to B[j] will be found only on the right side of i and vice versa. Thus, we traverse the 2 arrays and store the required elements.

The Java code for the said functions is as follows:
The Java implementation of QuickSort can be found here .
Note that, if we ignore the running time of QuickSort, the running time of each of the two functions is O(n+m).

Run Length Encoding

INPUT :
A string "s" consisting of possibly repeating characters. 
E.g. "aaaaabbbcddddefgttt"

OUTPUT :
A string s' such that s'.length() <= s.length(). String shortening is done by counting the contiguous occurrence of the characters and replacing them by the single character and its count of occurrence.
E.g. "a5b3cd4efgt3" 

Wikipedia Page

Number Of Possible Triangles In An Array

We have "n" sticks with us. The length of each stick is known to us. We need to find the number the triangles that can possibly be made from these sticks. The condition for making a triangle is that the sum of any two sides of the triangle should be greater than the third side. i.e. if a, b, c form a triangle, then :
1) a+b>c
2) b+c>a
3) a+c>b

INPUT:
The first input will be "n" i.e. the number of sticks in our hands. The second input will be an array of the lengths of each stick i.e. the size of the array will be "n".

OUTPUT:
The number of triangles possible. For example, for an input array {14, 8, 2, 1, 3, 9}, the 3 possible triangles are : (14, 8, 9) , (8, 3, 9), (8, 2, 9). So the output should be 3.

BRUTE FORCE METHOD:
The brute-force method dictates that we take every combination of 3 elements in the array and check if the triangle-conditions 1), 2), 3) hold. Thus, for n sticks, we will have ⁿC₃ = ϴ(n³) comparisons. Following is the brute force approach:

Algorithm bruteForce(int[n] a)

1. For (i = 0 upto n-3)
2.      For(j = i+1 upto n-2)
3.           For(k = j+1 upto n-1)
4.                  if(a[i]+a[j] > a[k] AND a[j]+a[k] > a[i] AND a[i]+a[k] > a[j])
5.                        count++

A BETTER APPROACH:
Instead of the brute-force approach, we make use of a simple mathematical manipulation:
If in a combination (a, b, c), a is the greatest element, and if b+c > a, then  (a, b, c) can form a triangle.

This manipulation is illustrated as follows : 
Consider a combination (14, 8, 9). Here 14 is the greatest element in the combination. Now, 8+9 = 17 > 14. Thus, condition 2) is satisfied. Now, since we know that 14 is the largest element, we will be sure that 14 + 8 or 14 + 9 will surely exceed the other element. Thus conditions 1) and 3) are satisfied and a triangle is possible.

The above approach first sorts the array in a descending order so that the initial elements will be the largest. We then traverse through the array and check for any combination of 3 elements whose sum of 2 exceeds the first. If we do not find such pairs, we stall the traversal.

Note that the above approach is what can be called as "output-dependent". If, in an array of size "n", there are "m" triangles possible, then the maximum number of comparisons will be n+m-3 which is much much lesser that n³. Thus, we have eliminated a lot of redundant comparisons and made our program quicker. As a result, athough the program implements 3 nested for-loops, by eliminating redundancy, we have greatly improved the efficiancy of the program.

Number Of Occurences Of A Word In A Sentence

INPUT: A sentence containing one or many words like "Hello World Hello Java". We assume that no punctuation marks have been used.

OUTPUT: The number of occurenes of each word. For example, in the above example, the output we get is:
Hello - 2
World - 1
Java - 1
Note that the words "Hello" and "hello" are not the same i.e. the words are case-sensitive

BRUTE FORCE METHOD:
The first step is to break the sentence into words. We then store the words in an ArrayList for ease.

The brute force method is obviously to compare every word in the sentence with every other word. This will take ϴ(n²) for a n-worded sentence as it will involve 2 nested for-loops and every possible pair will be checked.

HASH-MAP IMPLEMENTATION:
In this approach, the first step remains the same - to break the sentence up ino words and arrange the in an ArrayList. Note that this step costs ϴ(n) as 1 full traversal of the array is needed.

However, we now count the number of occurences using Hash-Map instead. We create a HashMap named "map" which has the ASCII value of each word as its key and the word itself as its value. We then iterate over this HashMap and print count of each word. To store count, we either implement another HashMap or a set of variables.

Note that the above step finds the number of occurences in O(n) time. The worst case will be achieved when each word is distinct in the sentence. Thus, at the cost of O(n) extra memory, we reduced the ime-complexity of the programme from ϴ(n²) to O(n).

Implementation Of Quick Sort

We have observed that although the logic behind quick sort is quite simple and straight-forward, people do find it a bit difficult to implement. So we have implemented this very useful and efficient (O(n*log₂n)) sort in java. It has been tested for all cases, yet if you find any flaws in it, please leave a comment.

The logic behind this quick sort implementation is picked up from CLRS 3rd edition. 
 

Longest Palindrome In The String

INPUT :
A string of length n.

OUTPUT :
A palindromic string which is the longest sub-string of the inputted string. Thus the output string can have a maximum length of 'n'

THE BRUTE FORCE METHOD :
Since we are looking for a sub-string, the brute force method would suggest finding every possible sub-string in the string and checking if its a palindrome. The algorithm to find every sub-string accepts the inputted string 's' and its length 'n' as parameters. We assume the existence of a pseudo function isPalindrome which accepts a string as parameter and returns true if the string is a palindrome and false otherwise. We also assume subString(String, startIndex, endIndex) to be a function that returns the substring of s beginning from startIndex (including) and ending at endIndex (excluding). This is quite similar to the Java.lang.String.substring(int beginIndex, int endIndex). The algorithm uses 3 variables : maxlen to find out the maximum length of the palindrome, templen to compare with maxlen, start and end as the begin and end indices of the palindrome respectively.

Algorithm findSubString (String s)

1. maxlen = 0 ,  templen = 0, start = 0, end = 0
2. for (int i = 0 up to n-1) 
3.      for (int j = i down to 0)
4.            for (int k = i+1 up to n)
5.                          templen = k-j+1
6.                          if ( isPalindrome(subString(s, j, k+1)) && templen > maxlen) 
7.                               maxlen = templen
8.                               start = j
9.                               end = k+1 // k+1 is because subString excludes the endIndex
10.                          end if
11.               end for
12.         end for
13. end for
14. return subString(s, start, end)

However, as we see, this approach uses 3 traversals in 3 nested for loops, taking O(n³) time. It should be noted that the time-efficiency of the function isPalindrome() is not taken into consideration as it is, anyways, less than O(n³) (shall be proved in a few moments).

THE isPalindrome() FUNCTION :
The most efficient method of determining whether a string is palindrome or no is to start with its central character and to go one character each to the left and right simultaneously checking whether the string is a palindrome. For example, for "abcba", we start at "c", which is the central character and then go one character to the left getting "b" and one character to the right getting "b" again. Thus "bcb" is a palindrome. We go on doing this till the string stops being a palindrome. This is essentially the algorithm behind isPalindrome(). Let us say that we divide every palindromic string of length, say p, into 2 kinds : when p is even and when p is odd. 

1.  when p is odd, as in "abcba", we fix 1 mid-point (here "c"), then compare every character at an "x" distance from it to the left to every character at the same distance from it to the right.
2. when p is even, like "abccba", we fix no mid-point, and begin comparing from "c" and "c" (they occupy the center positions in the string; 6/2 = 3 therefore 3rd and 4th positions are central) and then continue as above.

Thus we see, that any string can be checked for palindrome in O(n) times (1 traversal).

A BETTER APPROACH :
Note that we need to find a palindromic sub-string. Such a sub-string may begin or end at any index in the string, and not necessarily at the beginning and the end of the string. For example, for "banana", the longest palindromic sub-string is "anana" which doesn't start at the beginning of the string. So to speak, we do not know the start or the end of the sub-string and thus we cannot find the mid-point. Hence, we need to consider every character as the mid-point and begin checking for the palindromes. This will take 1 traversal of the string. A java code implementing this approach is as follows :

Do leave any comments if you find a better approach or if you have any doubts regarding the given approach. 

Courtesy : http://www.geeksforgeeks.org/longest-palindrome-substring-set-1/

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.