Search In A Young tableau - A Sorted Matrix

Young tableau : For our present discussion ,we confine this entity to a table which elements are sorted both column wise and row wise.The degree of orderliness among the elements is loosely bound that a row by row or column by column traversal of this matrix doesn't essentially list out the elements in a sorted manner.So the search on this matrix is not all that simple and straight forward as it looks like.
In the following sections we will look at some interesting approaches to search for a key in this 2D array(after all it is!!).

One interesting yet simple thing worth observing is that
element A[i][j] is always > A[p][q] for i > p and j> q .
The next 2 strategies are based on this simple fact.

Strategy1 - A grid search: About any element A[i][i] divide the matrix in to 4 quadrants.
If the key K we are looking for is

1. <A[i][j] then we can eliminate the lower right quadrant because all its elements are > A[i][j].


2. <A[i][j] then we can eliminate the lower right quadrant because all its elements are > A[i][j].


3. =A[i][j]. then our search is over.The choice of this i can be done in a binary search manner.. reducing the search space by half.

Now we can search the 3 quadrants individually and hence recursively.

T(N)=3*T(N/4)+O(1) which comes out to be O(N^(log3/log4)) which is less than O(N).

Strategy2:Now we move a step further in reducing the search space.Iterate along the diagonal and find i such that A[i][i] <k and A[i+1][i+1] >k.Now we have only 2 search intervals to search for.

T(N)=2*T(N/4)+O(N) which comes out to be O(N).

Strategy3:One more interesting solution and smart solution that I found was(the credit goes to the geek named Novice in the discussion http://inder-gnu.blogspot.com/2008/01/find-element-in-row-and-column-sorted.html ) this.

Start from the point in the last row first column. Every point to its right is greater than this point and every point on its top is smaller than this. So, if the point is greater than this point then move right otherwise move top. So, you will traverse at most 2*n points.


Well, these are 3 interesting solutions I could find till now and at this juncture ,it is not surprising if one wishes to compare these strategies to figure out the best and I don't even rule out any other solutions to this problem.So folks if you do any ,please put them in the comments sections and let others know.

Continued

Here are the C codes for the above discussed strategies.

Strategy1




strategy1

bool novice_search(int **grid,int size, int key,int &x,int &y)
{
        int i=size-1,j=0;
        while(0<=i && i<size && 0<=j && j<size)
        {
                if(grid[i][j]==key)
                {
                        x=i;
                        y=j;
                        return true;
                }
                else if(grid[i][j] <key)
                {
                        j++;
                }
                else
                        i--;
        }
        return false;
}

strategy2

bool quadra_partitionsearch(int **grid,int row_min,int row_max,int col_min,int col_max,int key,int &x,int &y)
{
        if((row_min > row_max) ||( col_min >col_max))
                return false;
        else if((row_min==row_max) &&(col_min==col_max))
        {
                if(grid[row_min][col_min]==key)
                {
                        x=row_min;
                        y=col_min;
                        return true;
                }
                else
                        return false;
        }
        else if((grid[row_min][col_min] <=key) && (grid[row_max][col_max]>=key))
        {
                int row_mid =(row_min +row_max)/2;
                int col_mid =(col_min+col_max)/2;
                bool flag;
                //      cout <<row_min <<'\t' <<row_max<<'\t'<<col_min<<'\t'<<col_max<<'\n';
                if(grid[row_mid][col_mid]==key)
                {
                        x=row_mid;
                        y=col_mid;
                        return true;
                }

                else if(grid[row_mid][col_mid]>key)
                {
                        if(quadra_partitionsearch(grid,row_min,row_mid,col_min,col_mid,key,x,y))
                                return true;
                }
                else
                {
                        if(quadra_partitionsearch(grid,row_mid,row_max,col_mid+1,col_max,key,x,y))
                                return true;
                }
                if(quadra_partitionsearch(grid,row_min,row_mid,col_mid+1,col_max,key,x,y))
                        return true;
                else if(quadra_partitionsearch(grid,row_mid+1,row_max,col_min,col_mid,key,x,y))
                        return true;

        }
        return false;
}

strategy3

bool binary_partitionsearch(int **grid,int row_min,int row_max,int col_min,int col_max,int key,int &x,int &y)
{
        if((row_min > row_max) ||( col_min >col_max))
                return false;
        else if((row_min==row_max) &&(col_min==col_max))
        {
                if(grid[row_min][col_min]==key)
                {
                        x=row_min;
                        y=col_min;
                        return true;
                }
                else
                        return false;
        }
        else
        {
                if(grid[row_min][col_min] > key)
                        return false;
                int row_mid=row_min,col_mid=col_min;
                while(grid[row_mid][col_mid] < key)
                {
                        row_mid++;
                        col_mid++;
                }
                if(grid[row_mid][col_mid]==key)
                {
                        x=row_mid;
                        y=col_mid;
                        return true;
                }
                else
                {
                        if(binary_partitionsearch(grid,row_mid,row_max,col_min,col_mid-1,key,x,y))
                                return true;
                        return binary_partitionsearch(grid,row_min,row_mid -1,col_mid,col_max,key,x,y);
                }
        }
}

I tried to check which of them is efficient by noting the runtimes and well all of them were quite close,though 2nd and 3rd approaches did mostly well compared to the first one.All these strategies worked more or less in the same manner on an grids of size varying from 100 to 1000.The last 2 strategies worked much better than the first one mostly.

Trees Revisited

We complete the trees sections in this post adding some more questions to the already posted ones.

1)What are splay trees?How are they different from normal trees?

2)What are the key operations which characterize splay trees?

3)How are AVL rotations different from the operations performed in splay trees?

4)Show that if all the nodes in a splay tree are accessed sequentially,then the total access time is O(N),regardless of the initial tree?

5)Given 2 binary trees T1 and T2 with same set of nodes,show how you can transform one in to the other?

6)Give an algorithm to transform a binary tree T1 into another binary tree T2?

7)Give an algorithm to find all the elements between 2 keys K1 and K2 with K1<=K2
in a binary search tree T?

8)How do you convert the parent-child tree to a child-sibling tree(assume the tree is a binary tree)?

9)Two binary trees T1 and T2 are isomorphic if T1 can be transformed into T2 swapping left and right children of the nodes in T1.Give an algorithm to report whether 2 given binary trees are isomorphic.

10)Analyze the complexity of the above algorithm and report whether there exists a linear solution to it?

Recursion Analysis

Recursion algorithms can be analysed by 3 methods : Substitution method,recursion tree method and master method.

1)Show that the solution of T(n)=T(n/2) + 1 is O(lg n).

2)Show that the solution to T(n)=2*T((n/2)+17) is O(n*(lg n)).

3)Solve the recurrence T(n)=2*T(sqrt(n)) + 1.

4)Use a recursion tree to determine a good asymptotic upper bound on the recurrence T(n)=3*T(n/2) + n.

5)Use a recursion tree to give an asymptotically tight solution to the recurrence T(n)=T(n-a) + T(a) +cn,where a >=1 and c>0 are constants.

6)Draw the recursion tree for t(n)=4T(n/2)+cn,where c is a constant,and provide a tight asymptotic bound on its solution.

7)Use a recursion tree to give an asymptotically tight solution to the recurrence T(n)=T(an)+T((1-a)n)+cn,where a is a constant in the range 0<>0 is also a constant.

8)Use master method to give tight asymptotic bounds for the following recurrences.
a.T(n)=4T(n/2)+n.
b.T(n)=4T(n/2)+n^3

9)The recurrence T(n)=7T(n/2)+n^2 describes the running time of an algorithm A.A completing algorithm A' has a running time of T'(n)=aT'(n/4)+n^2.What is the largest integer value for a such that A' is asymptotically faster than A?

10)Can the master method be applied to the recurrence T(n)=4T(n/2)+n^2(lg n)? Why or why not? Give an asymptotic upper bound for this recurrence.

11)Use the master method to show that the solution to the binary-search recurrence T(n)=T(n/2)+ Theta(1) is T(n)=Theta(lg n).

Click here for the solutions

Find some problems on recursion here

Some Basic Questions on Sorting

1 .In a selectionsort of n elements, how many times is the swap function called in the complete execution of the algorithm?

A. 1
B. n - 1
C. n log n
D. n^2

2 .Selectionsort and quicksort both fall into the same category of sorting algorithms. What is this category?

* A. O(n log n) sorts
* B. Divide-and-conquer sorts
* C. Interchange sorts
* D. Average time is quadratic.

3 . Suppose that a selectionsort of 100 items has completed 42 iterations of the main loop. How many items are now guaranteed to be in their final spot (never to be moved again)?

* A. 21
* B. 41
* C. 42
* D. 43

4 .Suppose we are sorting an array of ten integers using a some quadratic sorting algorithm. After four iterations of the algorithm's main loop, the array elements are ordered as shown here:

1 2 3 4 5 0 6 7 8 9

Which statement is correct? (Note: Our selectionsort picks largest items first.)

* A. The algorithm might be either selectionsort or insertionsort.
* B. The algorithm might be selectionsort, but could not be insertionsort.
* C. The algorithm might be insertionsort, but could not be selectionsort.
* D. The algorithm is neither selectionsort nor insertionsort.

5 .Suppose we are sorting an array of eight integers using a some quadratic sorting algorithm. After four iterations of the algorithm's main loop, the array elements are ordered as shown here:

2 4 5 7 8 1 3 6

Which statement is correct? (Note: Our selectionsort picks largest items first.)

* A. The algorithm might be either selectionsort or insertionsort.
* B. The algorithm might be selectionsort, but it is not insertionsort.
* C. The algorithm is not selectionsort, but it might be insertionsort.
* D. The algorithm is neither selectionsort nor insertionsort.

6 .When is insertionsort a good choice for sorting an array?

* A. Each component of the array requires a large amount of memory.
* B. Each component of the array requires a small amount of memory.
* C. The array has only a few items out of place.
* D. The processor speed is fast.

7 What is the worst-case time for mergesort to sort an array of n elements?

* A. O(log n)
* B. O(n)
* C. O(n log n)
* D. O(n^2)

8 What is the worst-case time for quicksort to sort an array of n elements?

* A. O(log n)
* B. O(n)
* C. O(n log n)
* D. O(n^2)

9 .Mergesort makes two recursive calls. Which statement is true after these recursive calls finish, but before the merge step?

* A. The array elements form a heap.
* B. Elements in each half of the array are sorted amongst themselves.
* C. Elements in the first half of the array are less than or equal to elements in the second half of the array.
* D. None of the above.

10 .Suppose we are sorting an array of eight integers using quicksort, and we have just finished the first partitioning with the array looking like this:

2 5 1 7 9 12 11 10

Which statement is correct?

* A. The pivot could be either the 7 or the 9.
* B. The pivot could be the 7, but it is not the 9.
* C. The pivot is not the 7, but it could be the 9.
* D. Neither the 7 nor the 9 is the pivot.

11 .What is the worst-case time for heapsort to sort an array of n elements?

* A. O(log n)
* B. O(n)
* C. O(n log n)
* D. O(n^2)

12.Suppose you are given a sorted list of N elements followed by f(N) randomly ordered elements.How would you sort the entire list if
* A. f(N)=O(1)
* B. f(N)=O(logN)
* C. f(N)=O(N^1/2)
* D. How large can f(N) be for the entire list still to be sortable in O(N) time?

13.Prove that any algorithm that find an element X in a sorted list of N elements requires Omega(log N) comparisons.

14.Prove that sorting N elements with integer keys in the range 1 < Key < M
takes O(M + N) time using bucket sort.

15.Suppose you have an array of N elements,containing only 2 distinct keys, true and false.Give an O(N) algorithm to sort the array.

16.Prove that any comparison based algorithm to sort 4 elements requires atleast 5 comparisons

17. In how many ways can 2 sorted arrays of combined size N be merged?

18.Show that binary insertion may reasonably be expected to be an O(n log n) sort.

19.You are given two sets of numbers Xi and Yj , where i and j run from 1 to N.
Devise an algorithm to find the M largest values of Xi −Yj . This algorithm should
not be quadratic in N, though it is permitted to be quadratic in M.
You should regard N as being of the order of 20,000 and M as being of the order
of 1,000.


20.If 1024 numbers are drawn randomly in the range 0–127 and sorted by binary
insertion, about how many compares would you expect?


Click Here for Solutions

Interview questions on Sorting - Quick Sort

QuickSort

Here are some of the commonly asked and good questions on quick sort.

1. Determine the running time of QuickSort for
   
   a.Sorted input
   b.reverse -ordered input
   c.random input
   d. When all the elements are equal
   
   link to solution
   
   



2. The ones who are familiar with QuickSort as also well aware of the important phase of the algorithm-the pivot selection.Suppose we always choose the middle element as the pivot .Does this make it unlikely that QuickSort will require quadratic time?
   
   link to solution
   
   



3. What is the worst-case behavior (number of comparisons) for quick sort?
   link to solution
   



4. In selecting the pivot for QuickSort, which is the best choice for optimal partitioning:
   a.The first element of the array
   b.The last element of the array
   c.The middle element of the array
   d.The largest element of the array
   e.The median of the array
   f.Any of the above
   link to solution
   



5. In its worst case QuickSort behaves like:
   a.Bubble sort
   b.Selection sort
   c.Insertion sort
   d.Bin sort
   link to solution
   




6. Describe an efficient algorithm based on Quicksort that will find the element of a set that would be at position k if the elements were sorted.
   link to solution
   



7. Recall that the linked-list version of quicksort() puts all items whose keys are equal to the pivot's key into a third queue, which doesn't need to be sorted. This can save much time if there are many repeated keys.
   
   The array-based version of quicksort() does not treat items with equal keys specially, so those items are sorted in the recursive calls.
   
   Is it possible to modify array-based quicksort() so that the array is partitioned into three parts (keys less than pivot, keys equal to pivot, keys greater than pivot) while still being in-place? (The only memory you may use is the array plus a constant amount of additional memory.)
   
   Why or why not?
   
   link to solution
   

Sorting -MergeSort

MergeSort

Mergesort is one of the beautiful examples of recursion.
It runs in O(NlogN) time.
The fundamental operation involved in this algorithm is merging 2 sorted lists.This can be done in one pass through the 2 lists if the output is a third list.

Conceptually, merge sort works as follows:

1. Divide the unsorted list into two sublists of about half the size
2. Divide each of the two sublists recursively until we have list sizes of length 1, in which case the list itself is returned
3. Merge the two sorted sublists back into one sorted list.

The crucial step determining the complexity of the algorithm is the merge .

In merge,we start of with 2 sorted sub arrays A,B and an output array C in to which the sorted union of A,B has to be copied.

Let Aptr,Bptr and Cptr be the 3 counters set to the beginning of the resprective arrays. we go on retrieving the smallest element of A[Aptr] , B[Bptr] and copy it to C[Cptr] and advance the counter Cptr as well as the counter of the array from which the element is copied to C.

This process of retrieval takes place as long as both the arrays A,B are unfinished.
When one of them is finished ,the remaining portion of the second array is copied into C.

Pseudo Code

Procedure MergeSort (Array(First..Last))
Begin

If Array contains only one element Then
     Return Array
Else
     Middle= ((Last + First)/2) rounded down to the nearest integer
LeftHalfArray = MergeSort(Array(First..Middle))
RightHalfArray = MergeSort(Array(Middle+1..Last))
ResultArray = Merge(LeftHalfArray, RightHalfArray)
Return ResultArray
EndIf

End MergeSort

Procedure Merge (LeftHalfArray(LHFirst..LHLast), RightHalfArray(RHFirst..RHLast))
Begin

Result: Array(ResultFirst..ResultLast) of size (LHLast-LHFirst+1+RHLast-RHFirst+1)
LeftPointer = LHFirst
RightPointer = RHFirst
ResultPointer = ResultFirst
Loop
     If LeftHalfArray(LeftPointer) <= RightHalfArray(RightPointer)  
       Then
             
   Result(ResultPointer) = LeftHalfArray(LeftPointer)
       LeftPointer = LeftPointer + 1
   ResultPointer = ResultPointer + 1
   Else  
         Result(ResultPointer) = RightHalfArray(RightPointer)
   RightPointer = RightPointer + 1
   ResultPointer = ResultPointer + 1
 Until all elements in either LeftHalfArray or RightHalfArray have been moved to
 Result.If all elements in the LeftHalfArray have been moved to Result

Then  

Move remaining elements in RightHalfArray to Result       

Else                

Move remaining elements in LeftHalfArray to Result

End If       

Return Result End Merge 

Analysis of MergeSort

The time to mergesort N numbers is the time to mergesort 2 subarrays of size N/2 and merge them.

As we knew ,Merge takes at the maximum N-1 comparisons hence linear.

Hence T(N)=2*T(N/2)+N .

Solving the above recursion ,we get the time complexity to be O(NlogN).

Having looked at this brief though detailed analysis on Mergesort, We shall look at some questions which throw further light on the behaviour of the mergesort.

Questions

1) Determine the running time of mergesort for
a. sorted input
b.reverse-ordered input
c.random input


Solution:One would be surprised to see that the complexity of this algorithm doesn't change according to that of input.One can clearly see that the merge is the only phase affected by the ordering of the input.In this case,logN iterations would anyway occur in dividing phase of divide and conquer strategy.
a.Sorted Input:In merge phase, only the left pointer sweeps down its array while the right remains unmoved.Hence the number of comparisons reduces to N/2 instead of N.So the algorithm is still of order O(N*logN).

b.reverse-ordered input:This is similar to the earlier one.In this case the right portion gets copied first.Hence the order doesn't change.

c.random input:This is the normal case we have analysed the complexity for :).So obviously true.




2)Prove that the minimum number of comparisons used in mergesort in the worst case is N*floor(LogN)-2^floor(logN) +1(don't ignore the constants)

Solution:In the worst case the no of comparisons used to merge 2 arrays making up for a union of size N is N-1.So the equations looks like this.
T(N)=2*T(N/2)+N-1 (considering only comparisons)
T(N)=4*T(N/4)+N-1 +N-2
.
.
.
T(N)=2^k T(N/2^k) +N-1 +N-2 +.......+N-2^(k-1)

Hence T(N)=2^floor(logN) T(1) + N*floor(logN)-(1+2+.....+2^(k-1))

T(1)=0 since no comparisons are involved for an array of size 1.

Hence T(N)=N*floor(logN)-2^floor(logN) +1





3)You are given with three sorted arrays ( in ascending order), you are required to find a triplet ( one element from each array) such that distance is minimum.
Distance is defined like this :
If a[i], b[j] and c[k] are three elements then

distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))

Please give a solution in O(n) time complexity.

Solution: Point to the first elements of the three arrays, namely a[0],b[0],c[0].
Find the smallest and second smallest of the three.Let us say that a[0] is the smallest and b[0] is the second smallest. Increment the pointer of a until you find a[i]>b[0]. Calculate the difference between a[i-1] and c[0] and store it as current min. Now,again find the smallest and second smallest between a[i], b[0], and c[0] and repeat the above process. If the new difference is smaller than current min,update the value of current min.
Repeat the above process until one of the arrays are finished.


Post your answers in Comments Section .The answers for these questions shall be posted soon.

Some Interesting Algorithm Questions

1. Here's a problem that occurs in automatic program analysis. For a set of variables x1; ...... ; xn, you are given some equality constraints, of the form "xi = xj" and some dis equality constraints, of the form "xi != xj" Is it possible to satisfy all of them? Give an efficient algorithm that takes as input m constraints over n variables and decides whether the constraints can be satisfied.



2. What are the running times of each of these algorithms, and which would you choose?
   
   
   • Algorithm A solves problems by dividing them into 5 subproblems of half the size, recursively solving each subproblem, and then combining the solutions in linear time.
   • Algorithm B solves problems of size n by recursively solving two subproblems of size n-1 and then combining the solutions in constant time.
   • Algorithm C solves problems of size n by dividing them into nine subproblems of size n=3, recursively solving each subproblem, and then combining the solutions in O(n2) time.



3. You are given two sorted lists of size m and n. Give an O(log m+log n) time algorithm for computing the kth smallest element in the union of the two lists.



4. An array A[1....n] is said to have a majority element if more than half of its entries are the same. Given an array, the task is to design an efficient algorithm to tell whether the array has a majority element, and, if so, to find that element.
   The elements of the array are not necessarily from some ordered domain like the integers, and so there can be no comparisons of the form "is A[i] > A[j]?".
   However you can answer questions of the form: "is A[i] = A[j]?" in constant time.

Sorting - Insertion Sort

Insertion Sort
Any basic sorting algorithm which uses comparison of elements involves a number of inversions to be made to the given array to sort it.

An Inversion in an array of numbers is any ordered pair (i,j) such that
(a[i] - a[j] )*( i - j) .
Pseudo Code

void InsertionSort(int A[],int N)
{
    int pos,i;
    int temp;
    
    for(pos=1; pos < n; pos++>
    {
         temp=A[pos];
         for(j=pos;j>0;j--)
         {
                if(A[j-1] > temp)
                {
                        A[j]=A[j-1];
                }
                else
                {
                    break;
                }
                A[j]=temp;
         }
    }
}

Analysis of Insertion Sort:

The efficiency of insertion sort depends upon the distribution of the data.This is because insertion sort tries to put each of the elements in the sorted array of preceding elements.If the array is presorted , then the running time of the algorithm is O(N) because the inner for loop always breaks immediately.In the worst case, it is of O(N^2) as can be observed for each position i, the inner loop is O(i).
Hence the complexity of this algorithm is O(N^2).

Questions:

1) What is the running time of the above algorithm if all the elements in the array are equal?

Solution:O(N).Each of the Inner for loop becomes O(1).Hence the complexity O(N).

2)Suggest a modified Insertion Sort algorithm to check whether an array is sorted or not?
Give also the complexity analysis

Solution:One can prove that complexity is O(N) with out fuss.The modification is when one finds that the first swap is required just print that it is not ordered and break the loop.

Prime Numbers!

Prime Numbers:

Prime Numbers are those natural numbers divisible only by 1 and themselves.These are building blocks of natural number arithmetic.

Some interesting things about prime numbers.

1)Any Natural number can be expressed uniquely as product of powers of distinct primes.This procedure of finding the powers of primes contained in a number is called Prime Factorization.

2)There are infinitely many prime numbers.

3)If a number N is not prime, then it should have a factor less than sqrt(N).Hence the procedure to test whether a number is prime or not is of complexity O(sqrt(N)).

Prime Twin Pairs

One of the first things noticeable about tables of primes is that there are many instances of pairs of prime numbers with the form n and n + 2.

Examples are 11 and 13, 17 and 19, 29 and 31, 101 and 103, 881 and 883, and so on.

These are sometimes called prime twin pairs. No one has ever determined if this is an interesting property of numbers or just a curious coincidence.
The instances of pairs of prime numbers decrease for ever larger numbers.

Palindromic Primes

One of the more curious prime number puzzles that mathematicians have examined is the occurrence of palindromic primes.

A palindrome is a word or phrase that reads the same forward or backward. Some examples of palindromic primes are 101, 131, 151, 181, 313, 353, 727, 757, 787, 79997, 91019, 1818181, 7878787, 7272727, and 3535353. There is an infinite number of palindromic primes.

Sieve of Eratosthenes

The Sieve of Eratosthenes is an algorithm for generating a list of all prime numbers up to a given integer N. It does this using O(N) space .

We begin by making a table of integers 2 to N.We find the smallest integer i, that is not crossed out,print i and cross out i, 2i , 3i, .........When i >sqrt(N) the algorithm terminates and further numbers which aren't crossed out printed.

Q1)Suggest ways to improve it further.

Solution:The improvement in terms of space requirements that can be done is accomodating only odd numbers as 2 is the only even prime.
considering time complexity, we can limit the strike off to multiples of prime P greater than P*P ,hence reducing the number of numbers traversed.



What is the complexity of this algorithm?

Solution:Nlog(N)

Q2)In the above mentioned facts about primes ,the second one claims that there are infinite number of primes.Prove it

Solution:Let there be finite number of primes say K.let the primes be P1,P2,....,Pk.
now consider the number N=P1*P2*P3*P4....*Pk + 1.
clearly none of the above k primes divide N.Hence N is also a prime contradicting our initial assumption.

Q3)Show that (N^4 + 4N) is a prime number if and only if N=1. (really simple)

Solution:let f(N)=N^4 + 4N.
f(1)=5 which is prime.
for N greater than 2 we can write f(N)=N(N^3+4) as product of 2 numbers both of which are greater than 1.Hence it is composite.
Hence proved.


Relative Primes

When gcd(m, n) = 1, the integers m and n have no prime factors in
common and we say that they’re relatively prime.

Euler's Phi Function

Euler's Phi function, also known as the totient function, is a function that, for a given positive integer N, calculates the number of positive integers smaller than or equal to N that are relative prime to N. (Note that except when N = 1, only integers strictly smaller than N are counted.

Mathematical Definition


where | | indicates the cardinality of the set.

Features of Euler's Phi Function

1) φ(p) = p - 1 for p prime, because all numbers smaller than p are relatively prime to p.

2) φ(N) is even for all N > 2, because if k is relatively prime to N, so is N - k, and they are distinct.

3) It is a multiplicative function in the number-theoretic sense: φ(MN) = φ(M)φ(N) whenever gcd(M,N) = 1.

4), because among the integers from 1 to p^k, the integers not relatively prime to p^k are precisely those divisible by p, and there are p^{k - 1} of them.

5)Let be the prime factorisation of N. That is, the p_is are distinct primes and each α_i is a positive integer. Then

If you have perhaps gone through the above facts,you can try solving the below mentioned
programming problems which test the basics

http://acm.uva.es/p/v101/10168.html

http://acm.uva.es/p/v106/10699.html

http://acm.uva.es/p/v107/10789.html

http://acm.uva.es/p/v108/10852.html

http://acm.uva.es/p/v108/10871.html

http://acm.uva.es/p/v109/10924.html

http://acm.uva.es/p/v1/160.html

http://acm.uva.es/p/v2/294.html

http://acm.uva.es/p/v4/406.html

http://acm.uva.es/p/v5/516.html

http://acm.uva.es/p/v5/543.html

http://acm.uva.es/p/v5/583.html

Remember that the solutions to these problems should be efficient in terms of time and space complexities.


post your valuable comments so that we can learn better through discussion.

Solutions to all the above problems shall be posted soon!!

Binary search

Binary Search



1. Given an array which is sorted but the sequence of sorted elements not necessarily starting from the first position which means you were given an array which is of the form [Ak+1 Ak+2,......An,A1,A2,............Ak]where A[1] <A[2] < .......... <A[N] find whether a given element E is present or not?


Solution: The only difference between a normal binary search and this problem is that the sorted array might start somewhere in the middle of the array.

We solve this problem in 2 steps.
step1:find the position P from which the array starts

Explanation:

int findstart(A,int left,int right)
{
int middle=(left+right)/2;

if(A[left] < A[middle] < A[right]) // the array is in sorted order
{
return left;
}

else if(A[right] <A[left] <A[middle]) // the left portion is in order
{
return findstart(A,middle+1,right);
}

else // the right portion is in order
return findstart(A,left,middle-1);
}


step2:Search in a subarray of the given array for the element E.


if we know the position p of the smallest element in the array say ,
then
if P=0 then it is in no respect different from the normal binary search.

otherwise we can partition the given array A in to 2 subarrays A(0,..,P-1)
and A(P,...,N).


Now if given key E < A[N] then call binarysearch(A,left=P,right=N,E)
else call binarysearch(A,left=0,right=P-1,E)







2.Given an array A[1,...,N] such that A[1] <A[2] < .......... <A[N].
find a position i such that A[i]=i.

Sol: This just uses a flavor of binarysearch.
Initial search space of i is [1,2,.....,N]

Here goes the algorithm.
int Search (int A[], int left, int right)

{

If(left < right)
return -1 (indicates that there is no i such that A[i]=i.

else
{
Middle=(left+right)/2;

if(A[Middle] == Middle)
then return Middle;

else if(A[Middle] < Middle)

return Search(A,left,Middle-1);

else
return Search(A,Middle+1,right);
}

}






3.Given 2 sorted arrays A and B each of size N,find the combined median of A and B?

Sol:Let A[i] denote "i" th element in A and B[i] be the corresponding in B (1 <= i <= N)
The combined median of A and B will have N elements to its left and N-1 elements to its right in the combined sorted union of A and B.
We shall use this fact to solve this question.
if A[i] is the median, then there should be N-i elements in B less than it and the rest more .
So it amounts to saying that A[i] falls between B[N-i] and B[N-i+1].

If B[N-i] <= A[i] <= B[N-i+1] then A[i] is the combined median.

else if A[i] < B[N-1] then the combined median if it at all belongs to A will be to the left of A[i].

else the combined median if it at all belongs to A will be to the right of A[i].


The border cases of i=1 and i=N can be properly manages with out much fuss.

So the initial search space of i for the above procedure will be [1,2,.........,N].

We can employ a flavor of binary search in choosing i in each iteration where in the above procedure is employed.

1)We start with i=N/2 .

begin
2) if B[N-i] <= A[i] <= B[N-i+1] then A[i] is the combined median.
3) else if A[i] < B[N-1] then the search space of i is [1,2,...,N/2 -1] and goto step2
4) else the search space of i is [N/2 +1,....,N] and goto step2

end

Hence using the above procedure if the median belongs to A can be determined in log(N) (binary searching for i)

Euclidean Algorithm

The Euclidean algorithm is an algorithm for finding the greatest common divisor of two integers.

Pseudo Code:

function gcd(  a,b : Integer ) returns Integer
{
 if ( b != 0 )
    return gcd( b, a mod b ) 
 return abs(a)
}


Explanation

The fact we need is that gcd(a,b) = gcd(b,a - kb) for any integer k. To see why this is true, let g be any common divisor of a and b. Then g divides a and kb (as it divides b), so it divides their difference a - kb. Conversely, let h be any common divisor of b and a - kb. Then h divides kb (as it divides b) and it divides a - kb, so it divides their sum a. Thus, the set of common divisors of a and b is the same as the set of common divisors of b and a - kb. In particular, their greatest common divisor is the same.

Complexity:

The estimation of the complexity of the Euclidean Algorithm is slightly tricky.

We shall prove a small theorem to estimate the time complexity.

Theorem: if M > N then M mod N < M/2

Proof:
if N < M/2 then as M mod N < N we have M mod N < N < M/2
if N > M/2 then clearly N goes once in to M with a remainder M-N which is less than M/2.


Now having proved the above theorem, we shall look into the time complexity.

after 2 iterations the remainder decreases by atleast half(using the above theorem... employ it for 2 iterations!!)
hence in the worst case,the no of iterations are 2*(logN) =O(logN).


Some Properties of the gcd

Any number that divides both a and b divides gcd(a,b)

gcd(a,b) is expressible as ax + by for some integers x and y

More generally, the equation ax + by = c has integer solutions for x and y if and only if gcs(a,b) divides c.

Majority Element

Well ,to all those who aren't familiar with majority element,a majority element in an array of size N is any element which is present more than N/2 times.

Now our task is given an array of size N ,we need to find the majority element if it exists ,as efficiently as possible.

Here are some of the ways to do it.

Naive approach:

Just scan the array element wise and then make a count of the frequency of each of the distinct elements present in the array and if any element's count is more than N/2 then it is the majority element, otherwise it doesn't exist!!

One needn't ponder much on the complexity of this bruteforce approach.

This requires O(N) additional space and O(N) time.

Recursive Approach:

Here’s a divide-and-conquer algorithm:

function majority (A[1 . . . N])

if N = 1: return A[1]

let AL , AR be the first and second halves of A

ML = majority(AL ) and MR = majority(AR )

if neither half has a majority:

return ‘‘no majority’’

else:

check whether either ML or MR is a majority element of A

if so, return that element; else return ‘‘no majority’’

Brief justification: If A has a majority element x, then x appears more than N/2 times in A and
thus appears more than N/4 times in either AL or AR ; it follows that x must also be a majority
element of one (or both) of these two arrays.
Running time: T (N) = 2T (N/2) + O(N) = O(N log N).

Sorting Based Approach:
It is well known that an array of size N can be sorted in O(NlogN).

A majority element if it exists,should be the median!!

The simple reason to justify the above statement is ,that the majority element is present more than N/2 times hence occupies more than N/2 contiguous positions after sorting,which is bound to contain the middle position.


Linear Time Algorithm:

function majority (A[1 . . . N])

x = prune(A)

if x is a majority element of A:

return x

else:

return ‘‘no majority’’

function prune (S[1 . . . N])

if N = 1: return S[1]

S = [ ] (empty list)

for i = 1 to N/2:

if S[2i − 1] = S[2i]: add S[2i] to S

return prune(S )


Justification: We’ll show that each iteration of the prune procedure maintains the following
invariant: if x is a majority element of S then it is also a majority element of S . The rest then follows.
Suppose x is a majority element of S. In an iteration of prune, we break S into pairs. Suppose
there are k pairs of Type One and l pairs of Type Two:

• Type One: the two elements are different. In this case, we discard both.

• Type Two: the elements are the same. In this case, we keep one of them.

Since x constitutes at most half of the elements in the Type One pairs, x must be a majority element in the Type Two pairs.
At the end of the iteration, what remains are l elements, one from each Type Two pair. Therefore x is the majority of these elements.

Running time: In each iteration of prune, the number of elements in S is reduced to l ≤ |S|/2.
Therefore, the total time taken is T (N) ≤ T (N/2) + O(N) = O(N).


Moore's Voting Approach:

sweep down the sequence starting at the pointer position shown above.

As we sweep we maintain a pair consisting of a current candidate and a counter. Initially, the current candidate is unknown and the counter is 0.

When we move the pointer forward over an element e:

• If the counter is 0, we set the current candidate to e and we set the counter to 1.
• If the counter is not 0, we increment or decrement the counter according to whether e is the current candidate.

When we are done, the current candidate is the majority element, if there is a majority.To ensure that just iterate over the array again and count the number of times the current candidate appears.
This is O(N) approach and more importantly requires only O(1) additional space.


Justification:This simple approach is tougher to crack.But the justification is simple with the help of an example.

Ex:
Imagine a convention center filled with delegates (i.e., voters) each carrying a placard proclaiming the name of his candidate. Suppose a floor fight ensues and delegates of different persuasions begin to knock one another down with their placards.
Suppose that each delegate who knocks down a member of the opposition is
simultaneously knocked down by his opponent. Clearly, should any candidate field more delegates than all the others combined, that candidate would win the floor fight and, when the chaos subsided, the only delegates left standing would be from the majority block. Should no candidate field a clear majority, the outcome is less clear; at the conclusion of the fight, delegates in favor of at most one candidate, say, the nominee, would remain
standing--but the nominee might not represent a majority of all the delegates.
Thus, in general, if someone remains standing at the end of such a fight, the convention chairman is obliged to count the nominee’s placards
(including those held by downed delegates) to determine whether a majority exists.

This is what the above voting algorithm simulates ,if we can correlate carefully!!

check your skill in basic algorithm analysis!!

one of the basic algorithms has been the exponentiation.

Exponentiation
This involves raising an integer to a power (which is also an integer).
The obvious algorithm to compute X^N uses N-1 multiplications.
In this section we shall see a better algorithm compared to the above one.


Efficient Exponentiation

long int pow(long int X, unsigned int N)

{

/* 1 */ if(N==0)

/* 2 */ return 1;

/* 3 */ else if(N==1)

/* 4 */ return X;

/* 5 */ else if(isEven(N))

/* 6 */ return pow( X * X, N /2);

else

/* 7 */ return pow( X * X, N /2)*X;

}


Analysis

Lines 1 to 4 handle the base case of recursion. Otherwise

if N is even , we have X^N = X^N/2 * X^N/2

and if N is odd, we have X^N= X^(N-1)/2 * X^(N-1)/2


The number of multiplications required is clearly at most 2 log N, because at most 2 multiplications are required(if N is odd) to halve the problem.

Simple intuition obviates the need for a brute-force approach.

one of the following alternative lines for line 6 are bad, even though they look correct:

/* 6a */ return pow( pow( X,2) , N/2);



/* 6b */ return pow( pow( X,N/2) , 2);



/* 6c */ return pow(X,N/2) * pow(X,N/2);

guess why??


Both lines 6a and 6b are incorrect because when N is 2, one of the recursive calls to pow has 2 as the second argument.Thus no progress is made, and an infinite loop results in an eventual crash.

Using line 6c effects the efficiency, because there are now 2 recursive calls of size N/2 instead of one.