Algorithms and Dynamic Programming Questionnaire

Algorithms and Dynamic Programming Questionnaire

Algorithms and Dynamic Programming

 

Bibek Adhikari

CSCI 3613. 01 Introduction to Algorithms

Pro. Wen Xu

Assignment 1 (A01)

Chapter 1

 Solution: – Let’s proof by contradiction:

1. Claim: f(n) = 3n³+ n² is O(n³).

We need to find c and n₀ such that:

f(n)=3n³ + n² <= cn³ for all n >= n₀

Divide both sides by n³, getting:

3 + 1/n <= c for all n >= n₀ .

If we choose n₀ equal to 1, then we need a value of c such that:

3 + 1<= c

We can set c equal to 5. Now we have:

3n³ + n² <= 5n³ for all n >= 1 .

Thus, we can say that f(n) = 3n³ + n² is O(n³).

2. Claim: f(n) = 3n³+ n² is (n³).

We need to find c and n₀ such that:

f(n)=3n³ + n² >= cn³ for all n >= n₀

Divide both sides by n³, getting:

3 + 1/n >= c for all n >= n₀ .

If we choose n₀ equal to 1, then we need a value of c such that:

3 + 1>= c

We can set c equal to 3. Now we have:

3n³ + n² >= 3n³ for all n >= 1 .

Thus, we can say that f(n) = 3n³ + n² is (n³).

Hence, from 1 & 2 we conclude that f(n) = 3n³ + n² is (n³⁾

 

29 Answer

a)

n=2,

first loop:// n*1.5= integer(3.0)=3

123

second loop:

21

output:12321

n=4,

first loop:// n*1.5= integer(6.0)=6

123456

second loop:4321

output:1234564321

 

n=6,

first loop:// n*1.5= integer(9.0)=9

123456789

second loop:

654321

output:123456789654321

29 (b)

First loop O(1.5n)

Second loop O(n)

Total O(n) because constant are ignored.

Hence , Time complexity T(n) = O (n)

35 Answer

a)

#include <iostream>

using namespace std ;

 

int add_them (int n, int A [])

{

int  i , j , k ;

j=0 ;

for ( i=1 ; i<=n ; i++ )

j = j + A [i] ;

k= 1 ;

for ( i = 1  ; i  <= n ; i ++ )

k= k+k ;

return j + k ;

}

 

int main ()

{

int n = 5 ;

int A [] = { 0,2,5,3,7,8 }; /* Array index starts with 0. But the index starts with 1 in the given code. So,

consider that the first element in the array is 0 as above array declaration. */

cout << “Result: “<< add_them (n,A) ;

cout << endl << endl ;

system (“pause”);

return 0 ;

}

 

Output of the algorithm:

Result: 57

 

1. b)

The first for-loop iterates for n times.

The second for-loop iterates for n times

So, the total running time is n + n = 2n

Hence, the time complexity T (n) = O(n)

 

Chapter – 2

 

2) Solution: – Search using binary search is the fastest one when comparing to the others. In this case we have the order of 700 million (700000000) items. initially we need to check the middle position of the list. Because if we find that searching element in the first half then we can neglect the second half, if we continue this repeatedly that is recursively we can easily find the solution.

 

We have 700 million items, and each item has the list of account numbers in the order. Now we need to look at the number 2100 is the 350^th item. If the account number will be 1008 we don’t need to check the 349^th item split it into half 351 to 700 that would be 175. Each time we need to split the records in this sequence.

 

700-350-175-83-42-21-10-5-3-1

 

For this sequence we need to calculate with log function

Time complexity of binary search is O(logN) in worst case, best case and average case as well. That means it can search for an item in Log N time where N is size of the input. Here problem talks about the item not getting found. So, this is a worst case scenario. Even in this case, binary search runs in O(logN) time.

N = 700000000.

So, number of comparisons can be log(N) = 29.3 = 29.

So, in the worst case it does comparisons 29 times

 

7) solution

int findMax(key type s[low…high], index low, index high)
{
if (low > high) return 0;

else if (low == high) return s[low];

else
{
int a = findMax(low, floor( (high – low) / 2) + low);
int b = findMax(floor( (high – low) / 2) + low + 1, high);

if(a > b)
{
return a;
}
else return b;
}
}

b.) There is no best, worst or average case. We then look for the every time complexity.

Let’s look at an example:

[1 2 3 4 5 6 7 8]
0

[1 2 3 4] | [5 6 7 8]
n / 8 = n / 8 comparisons

[1 2] | [3 4] | [5 6] | [7 8]
n / 8 + n / 8 = n / 4 comparisons

[1] | [2] | [3] | [4] | [5] | [6] | [7] | [8]
n/8 + n/8 + n/8 + n/8 = n / 2 comparisons

So n / 2 + n / 2^2 + n / 2^3 +… + n / n (1) = T(n)

Try some values of n:

T(2) = 2 / 2 = 1
T(4) = 4 / 2 + 4 / 4 = 2 + 1 = 3
T(8) = 8 / 2 + 8 / 4 + 8 / 8 = 7

Thus, T(n) = n – 1

c.) Let’s check. We can just use a straightforward loop comparison:

int findMax(low, high)
{
int max = 0;

for(index i = low; i <= high; i++)
if( list[i] > max )
max = list[i];
}

This will find the largest element in n – 1 comparisons, thus T(n) = n – 1. It’s the same time complexity as the divide and conquer approach.

13. Solution

For the given problem I have written a java program to perform 3 items using Merge Sort recursively. Merge sort involves recursively splitting the array into 2 parts, sorting and finally merging them. A variant of merge sort is called 3-way merge sort where instead of splitting the array into 2 parts we split it into 3 parts.

// Java program to perform 3 items using Merge Sort recursively

public class MergeSort3Way

{

// Function for 3-way merge sort process

public static void mergeSort3Way(Integer[] gArray)

{

// if array of size is zero returns null

if (gArray == null)

return;

// creating duplicate of given array

Integer[] fArray = new Integer[gArray.length];

// copying alements of given array into duplicate array

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

fArray[i] = gArray[i];

// sort function

mergeSort3WayRec(fArray, 0, gArray.length, gArray);

// copy back elements of duplicate array to given array

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

gArray[i] = fArray[i];

}

/* Performing the merge sort algorithm on the given array of values in the rangeof indices [low, high). low is minimum index, high is maximum index (exclusive) */

public static void mergeSort3WayRec(Integer[] gArray,int low, int high, Integer[] destArray)

{

// If array size is 1 then do nothing

if (high – low < 2)

return;

// Splitting array into 3 parts

int mid1 = low + ((high – low) / 3);

int mid2 = low + 2 * ((high – low) / 3) + 1;

// Sorting 3 arrays recursively

mergeSort3WayRec(destArray, low, mid1, gArray);

mergeSort3WayRec(destArray, mid1, mid2, gArray);

mergeSort3WayRec(destArray, mid2, high, gArray);

// Merging the sorted arrays

merge(destArray, low, mid1, mid2, high, gArray);

}

/* Merge the sorted ranges [low, mid1), [mid1,mid2) and [mid2, high) mid1 is first midpoint index in overall range to merge mid2 is second midpoint index in overall range to merge*/

public static void merge(Integer[] gArray, int low,

int mid1, int mid2, int high,

Integer[] destArray)

{

int i = low, j = mid1, k = mid2, l = low;

// choose smaller of the smallest in the three ranges

while ((i < mid1) && (j < mid2) && (k < high))

{

if (gArray[i].compareTo(gArray[j]) < 0)

{

if (gArray[i].compareTo(gArray[k]) < 0)

destArray[l++] = gArray[i++];

else

destArray[l++] = gArray[k++];

}

else

{

if (gArray[j].compareTo(gArray[k]) < 0)

destArray[l++] = gArray[j++];

else

destArray[l++] = gArray[k++];

}

}

// case where first and second ranges have remaining values

while ((i < mid1) && (j < mid2))

{

if (gArray[i].compareTo(gArray[j]) < 0)

destArray[l++] = gArray[i++];

else

destArray[l++] = gArray[j++];

}

// case where second and third ranges have remaining values

while ((j < mid2) && (k < high))

{

if (gArray[j].compareTo(gArray[k]) < 0)

destArray[l++] = gArray[j++];

else

destArray[l++] = gArray[k++];

}

// case where first and third ranges have remaining values

while ((i < mid1) && (k < high))

{

if (gArray[i].compareTo(gArray[k]) < 0)

destArray[l++] = gArray[i++];

else

destArray[l++] = gArray[k++];

}

// copy remaining values from the first range

while (i < mid1)

destArray[l++] = gArray[i++];

// copy remaining values from the second range

while (j < mid2)

destArray[l++] = gArray[j++];

// copy remaining values from the third range

while (k < high)

destArray[l++] = gArray[k++];

}

// Main function

public static void main(String args[])

{

// test case of values

Integer[] data = new Integer[] {45, -2, -45, 78,30, -42, 10, 19, 73, 93};

mergeSort3Way(data);

System.out.println(“After 3 way merge sort: “);

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

System.out.print(data[i] + ” “);

}

}

Time complexity:-

The recurrence relation of the given program will be:

T(n) = 3 T(n/3) +o(n) // Here o(n ) is used for merge operation.

I will solve this recurrence relation using master theorem.

Here a =3 and b =3 , and f(n)(n) and o(n).

Therefore,

=  .

It belongs to the second case of the master theorem.

therefore, time complexity of the program is   O (nlog(n)) .

 

14.

Recursion :

This is the process of repeating the loop or the piece of code till the value of the integer gets satisfied. This is generally used to calculate the values of a given number without the use of a loop or a iteration.

For the given condition this values has been calculated for the every recursion calls.

T(625)=7T(125)+10n for n>1 = 40551 + 6250 = 46801

T(125)=7T(25)+10n for n>1 = 4543 + 1250 = 5793

T(25)=7T(5)+10n for n>1 = 399 + 250 = 649

T(5)=7T(1)+10n for n>1 = 57

So the result value after recursion is 46801.

 

15

Solution

1. a)

T(1) = 0

T(n)  = 5 * T(n/3) + g (n) Where n >1

17 Solution

a ) Prove of S(n) = 2^n – 1

Let us find the recurrence relation between tower of Hanoi problem .

1. First move n-1 disks from source to temp.
2. Move disk from source to destination
3. Move n-1 disks from temp to source.

The number of steps are

T(n) = T (n-1) + 1 + T (n-1)

T(n) = 2 T(n-1) +1

Let us assume that the solution of recurrence relation is

T(n) = 2^n -1

Case 1 :

Let n=1,

T(1) = 2^1 – 1 =1

T(n) = 1

The number of moves n=1 is T(1) =1

Case 2:

Assume T(n) is true for

Case 3 :

Let us prove for n=n+1

T(n) = 2T(n-1) + 1

T (n + 1) = 2T(n+1-1) + 1

T (n+1) = 2 T(n) + 1

T(n+1) = 2 (2^n -1 ) + 1

T(n+1) =  – 2 + 1

T(n+1) =  – 1

Therefore , it is true for n+1.

 

24. Solution
25. Let the given list of items to represent the worst case scenario would be sorted list.

For example

{10,9,8,7,6,5,4,3,2,1}

As given , the Quicksort will take 10 as the first pivot and put all remaining value to the left of it . Then it will take 9 and do the same .

This would produce as n + (n-1) + …. + 2 + 1 association or n(n+1)/2

Which is O (n^2).