Design an Algorithm for Ternary Search

The Tower of Hanoi problem involves moving n disks from one rod to another, following specific rules: only the top disk can be moved, no large disk can sit over a small disk, and order must be maintained. The algorithm for solving this problem is recursive and requires 2^n-1 steps. Another problem mentioned is the Ternary Search algorithm, which divides a sorted list of n elements into three sublists and searches for an element in log3n time complexity.

Assignment
On
Design and Analysis of Algorithms
Subject: Design and Analysis of Algorithms
Topics: HW2

Q1.Find the recurrence relation on given equation:
T (n) = 7T(n/5) +10n for n>1
T(1)= 1, Find T(625)
Solution: Here this recurrence relation is evaluate for n=5^s where s>0, since we have been
given T (1),
Using the given formula,
T (n) = 7T(n/5) + 10n
T(625) = 7*T(125) + 10*625
= =7*[ 7*T(25) + 10*125 ] + 10*625
= 7*[ 7*{ 7*T(5) + 10*25 } + 10*125 ] +10*625
= 7*[ 7*{ 7*( 7*T(1) + 10*5 ) + 10*25 } + 10*125 ] +10*625
………………………………………………………………
………………………………………………………………..
Now here T(1)=1
Now, we can open the bracket to evaluate this expression,
T(625) = (7^4) + (7^3)*10*5 + (7^2)*10*25 + (7^1)*10*125 + 10*625
We can also write as:
T(625) = (7^4) + (7^3)*10*(5^1) + (7^2)*10*(5^2) + (7^1)*10*(5^3) + (7^0)*10*(5^4)
So, In general to evaluate the relation for n=5^s , so we can express in relation.
T(5^s) = 7^s + Σ{7^(s-k-1)*10*5^(k+1)} where k can varies from 0 to (s-1), which is given
s>0.
When we will calculate this equation then we will found:
T(625) will come out: 46801

Q2. Write a non-recursive algorithm for merge sort.
Solution:
As per the question, we have to explain the non-recursive algorithms for Merge Sort.
Suppose we know the number of inversions in the left half and right half of the array (let be
inv1 and inv2), what kinds of inversions are not accounted for in Inv1 + Inv2? The answer is
– the inversions we have to count during the merge step. Therefore, to get number of
inversions, we need to add number of inversions in left subarray, right subarray and merge().
How to get number of inversions in merge()?
In merge process, let i is used for indexing left sub-array and j for right sub-array. At any step
in merge(), if a[i] is greater than a[j], then there are (mid – i) inversions. Because left and
right subarrays are sorted, so all the remaining elements in left-subarray (a[i+1], a[i+2] …
a[mid]) will be greater than a[j].

Merge-and-Count
MergeAndCount(SortedList A, SortedList B):
a = b = CrossInvCount = 0
OutList = empty list
While a < |A| and b < |B|: // not at end of a list
next = min(A[a], B[b])
OutList.append(next)
If B[b] == next:
b = b + 1
CrossInvCount += |A| - a //inc by # left in A
Else
a = a + 1
EndWhile
Append the non-empty list to OutList
Return CrossInvCount and OutList
Note that MergeAndCount will produce a sorted list as well as the number of cross
inversions.

SortAndCount(List L):
If |L| == 1: Return 0
A, B = first & second halves of L
invA, SortedA = SortAndCount(A)
invB, SortedB = SortAndCount(B)
crossInv, SortedL = MergeAndSort(SortedA, SortedB)
Return invA + invB + crossInv and SortedL
Recurence Relation => recurence relation of merge sort:
T(n) = T(n/2) + n , n>2, Where T(2) = 1
Let T(n) be the running time of the above algorithm for n elements then we have
T(n) = 2 * T(n/2) + O(n), since we are solving recursively the left half of the list and right
half and merge operation takes O(n) time
now here we will use the master theorem a = 2, b = 2 and f(n) = O(n)
since n raised to power log(a) to the base b = n itself since log(2) to the base 2 is 1 which is
equal to f(n) = O(n)
hence this is the second case of master theorem and hence the running time complexity of
this algorithm is T(n) = O(nlogn)

Question 3: use binary search, recursive to search the integer 120 in the following list
(array) of integers.
12 34 37 45 57 82 99 120 134
Solution:
As per the question, we have to use the recursive approach it work as top down approach by
divide and conquer. Binary search locates the key x in sorted list array by first comparing the
x with middle term of array if searching integer is equal to that array the algorithm is done.
Otherwise we further dived the sub array into two parts into middle first one is left and right.
This procedure is repeated till determine x found.
Here X is 120 in the following array.
12 34 37 45 57 82 99 120 134
1. Here middle term is 57
2. Divide the array because X>57 , we need to search
82 99 120 134
3. Conquer the sub array and determine the weather x is in sub array
Yes , X is in sub array.
4. Again we repeat the same process, we further divide the sub array.
5. Right side value 82 99 120 134
6. Here middle term is 99
7. Again we will check with x, X>99, again we need to search the value
8. Now as per the algorithm if mid is less than x it will return low =mid + 1
9. So here it is determine the solution x = 120.
Algorithm Binary search (Recursive method).
Problem: Determine whether X is in sorted array of S size of N.
Inputs : positive integer n, Sorted array of key s, Here S is index the value should be 1 to n,
Key is x
Output: index location of x in S. value should >0.
Index location (index low, index high)
{
Index mid; //find mid value on sorted array.
If index ( low> high)
Return 0;
Else
{
Middle =[low+high)/2];

If (x== S[mid])
Return mid
Else if (x== S[mid])
Return location(low, mid-1);
Else
Return location(mid+1, high);
}
}

Question 4. Write an algorithm for tower of Hanoi problem.
Solution: Tower of Hanoi problem is mathematical puzzle which consist three tower and
more than one ring.
The main rules of tower of Hanoi, which we have to follow:
1. At the given time we can move only single move among the tower.
2. Only the top disk can be move
3. No large disk can sit over the small disk.
4. Order should be maintain.
Take an example for 2 disks:
First rod = A, second rod = B, Third rod 3 = C.
1 Step shift first disk from A to B.
2 Step shift second disk from A to C.
3 Step shift first disk from B to C.
We have identify the pattern here is:
1.Shift n-1 disks from A to B.
2.Shift last disk from A to C.
3.Shift n-1 disks from B to C.
Here we have illustrate with image:
Tower of Hanoi problem puzzle with n disk can be solved in minimum 2^n-1 steps.
Here we have taken 3 disk it has taken 2^3-1 = 7 steps.

The Patten of tower of Hanoi problem is which we identify :
1.Shift n-1 disks from A to B.
2.Shift last disk from A to C.
3.Shift n-1 disks from B to C.
Algorithm of tower of hanoi problem:
Procedure T-Hanoi(disk, source, destination, auxiliary)
{
If disk ==1,
{
Move disk from source to destination.
Else
T-Hanoi(disk-1, source, auxiliary, destination)
Move disk from source to destination
T-Hanoi(disk-1, auxiliary, destination, source)
}
}
There is no better algorithm to Tower of Hanoi problem puzzle with n disk can be solved in
minimum 2^n-1 steps.

Question 5. Write an algorithm that searches a sorted list of n time by dividing into
three sub list of almost n/3 items.
Solution:
Tannery search is a divided and conquer Tannery algorithm, it is search technique used to
determine the position of a specific value in an array, it is similar to a binary search
algorithm, the sorted array is divided into two parts, while in ternary search it is divided into
three parts And then you decide which element is present in the part.
This is mandatory for array (in which you will search for an element) before you start
searching you have to sort it out. In this quest, after each repetition, it ignores 1/3 part of the
array and repeats the same operation on the rest 2/3.
Note: as similar to binary search Array should be sorted to perform ternary search on it.
Here the Steps to perform Ternary Search:
1. First of all, we compare the element to mid 1. If found equally, then we return mid 1.
2. If it not found then we compare with the key with the element at mid2. If found equal,
then we return mid 2.
3. If it not found, then we check whether the key is less than the element at mid1. If yes,
then recur to the first part.
4. If it not found, then we check whether the key is greater than the element at mid 2. If
yes, then recur to the third part.
5. If it not found, then we recur to the second (middle) part.
Algorithm to perform Ternary Search:
int ternary_search(int left,int right, int x)
{
if(right>=l)
{
int mid1 = left + (right-l)/3;
int mid2 = right - (right-l)/3;
if(arr[mid1] == x)
return mid1;
if(arr[mid2] == x)
return mid2;
if(x<arr[mid1])
return ternary_search(left,mid1-1,x);
else if(x>arr[mid2])
return ternary_search(mid2+1,right,x);
else

return ternary_search(mid1+1,mid2-1,x);
}
return -1;
}
Time Complexity:
The recurrence equation of ternary search complexity
T(n)= T(n/3)+4c, C is constant here
So T(n) = 4clog3 n+ o(1)
So the final time complexity is
O (log3 N), Where n is the size of array.