COP 4534 Assignment 2 PDF

Preview

Summary

Solutions for assignment 2 in the course COP 4534 please don't kill me professor!...

Description

COP-4534: Algorithm Techniques Homework 2! 1) We learned in class the hare-tortoise algorithm of cycle-finding in a linked list. Based on this, design an algorithm that is both time and space efficient which finds the starting node of the cycle. Answer: To solve this problem we start with the hare-tortoise algorithm and work from there to find the first node of the cycle. First we must look at the hare-tortoise algorithm. To find a cycle in the linked list we use two pointers, one named T and the other one H. The pointer T moves one node at a time while the pointer H moves two nodes at a time so when pointer T is pointing at node i H will be pointing at 2i. If at some point in the Linked List both H and T are pointing at the same node we must terminate and return that there is a cycle in the list. Let’s define C as the distance between the start of the list and the first node of the cycle, L as the length of the cycle, and k as the distance from the start of the cycle to the point where H and T met. We must also notice that T and H can meet after one or more revolutions in the cycle so we also define p as the number of times T went through the cycle, and q as the number of times H went through the cycle. We know that the distance covered by T when the hare-tortoise algorithm terminates is: (I)

T = m + pL + k

and the distance covered by H is: (II)

H = m + qL + k.

Since H moves twice as fast as T then H = 2T. If we substitute H with 2T in (II) and set (I) and (II) equal to each other we get 2m + 2pL + 2k = m + qL + k m + k = qL – 2pL m + k = L(q -2p) then m + k must be a multiple of L (the length of the cycle). So this means we can set one of the pointers to the start of the list and keep the other one k nodes from the start of the cycle where it ends up at the end of the hare-tortoise algorithm, set them both to move one node at a time and they will eventually meet at the first node of the cycle after moving m nodes. The running time of the algorithm is O(n).

2) A patient has n pills to take. In each day, he can take either one pill or two pills until all

pills are gone. Let T(n) denote the number of different ways the patient can take all n pills. Give a closed form for T (n). (Note that – for example – the two sequences (1, 2, 2) and (2, 1, 2) are considered as two different ways of taking 5 pills.) ! Answer: First lets try to find the answer for T(1), T(2), T(3), T(4)… Notice that for each T(n) we are creating a set 𝑆! which contains every possible way of taking n pills so T(n) = |𝑆! | For T(1), 𝑆" = { (1)} so there is only one way of taking one pill and T(1) = |𝑆" | = 1 For T(2), 𝑆# = {(1, 1), (2)}+ we get that T(2) = |𝑆# | = 2 For+T (3), 𝑆$ = {( 1, 1,1), (1,2), (2,1)}+ so T(3) = |𝑆$ | = 3 For T(4), 𝑆% = {(1, 1,1,1), (1,1,2), (1,2,1), (2,1,1) , (2,2)}+ we get that T(4) = |𝑆% | = 5 For T(5), 𝑆& = {(1,1,1,1,1), (1,1,1,2), (1,1,2,1), (1,2,1,1), (2,1,1,1), (1,2,2),(2,1,2),+ (2,2,1)}+then T(5) = |𝑆& | = 8 For T(6), 𝑆' = {(1,1,1,1,1,1), (1,1,1,1,2), (1,1,1,2,1), (1,1,2,1,1), (1,2,1,1,1),+ (2,1,1,1,1), (1,1,2,2), (1,2,1,2), (1,2,2,1), (2,1,1,2), (2,1,2,1), (2,2,1,1), (2,2,2)} then T(6) = |𝑆' | = 13 !"" !

In general for any n ≥ 1 T(n) = ∑#$% "

𝑛−𝑘 & to see that this is true lets take T(4) as an 𝑘

4 example, there is only one way of using 1’s to take 4 pills 2 5 ways, after that there are 3 0 3 ways or 2 5 ways of using one 2 and two 1’s, and finally there is only one way or 1 2 4 3 2 2 5 +𝑤𝑎𝑦𝑠, of taking 4 pills with two 2’s. If we add 2 5 + 2 5 + 2 5 = 5 2 0 1 2 The closed form of T(n) is equal to the closed form of the Fibonacci numbers except n must be larger or equal to 3 because T(0) is not defined. T(n) = T(n-1) + T(n-2) 3) An array A of n distinct numbers are said to be unimodal if there exists an index k, 1 ≤ k

≤ n, such that A[1] < A[2] < … < A[k−1] < A[k] and A[k] > A[k+1] > … > A[n]. In other words, A has a unique peak and is monotone on both sides of the peak. Design an efficient algorithm that finds the peak in a unimodal array of size n. ! Answer: For an efficient algorithm to find the peek in a unimodal array we can modify binary search to find the peek in O(log n) time. First we pick an element in the middle of the array mid = n/2, A[mid] and we compare it with A[mid-1] and A[mid+1]. There are 3 cases, A[mid-1] < A[mid] < A[mid+1] which means that we are on the left side of the peek and we can eliminate everything to the left of A[mid], A[mid-1] > A[mid] > A[mid+1] which means that we are to the right of the peek, in this case we can also assume that the peek is not to the right of A[mid] so we can eliminate these elements too, and the final case A[mid-1] < A[mid] > A[mid+1] means that we have found the peek and we should return A[mid]. In the first two cases wee need to call our binary search algorithm recursively with the new start and end of the array as pointers so that we can do it with O(1) space complexity and the third case the one where A[mid-1] < A[mid] > A[mid+1] is our base case. As I mentioned at the beginning this algorithm has a time complexity of O(log n). 4) Suppose we are given two sorted arrays A and B each consisting of n numbers, and an integer 1 ≤ k ≤ 2n. Describe an algorithm that finds the kth smallest element in the union of A and B in O(log n) time. ! Answer: To solve this problem in O(log n) we need to use a divide and conquer ( algorithm. First we need to find the element with index 𝑖 = ; #< in A, and the element with index 𝑗 = ; < in array B. We compare A[i] and B[j], if it turns out that A[i] > B[j] then, ( #

because both arrays are sorted the kth smallest must be an element of A with an index less than i or an element in B with index greater than j. This means that we can discard A[i] and every element with index less than i and we can also discard elements to the left of B[j] including B[j]. Notice that all the elements of B with index less than j must be less than the ktth elements, so now we only need to find the rest of the elements that come before the kth element in other words we need to update k and call the function recursively with the new arrays and with k = (k-j) to find the (k-j) th element. In the case that A[i] < B[j] the kth element should be to the right of A[i] in array A or to the left of B[j] in array B, and we can eliminate every element to the left of A[i] and every element to the right of B[j]. in this case we must update k to k = k-i since we have found i elements that are less than the kth element. Finally the base case is k = 1 because if we keep doing j = ; < and i = ; < each iteration, at some point we will reach k = 1, when (

(

#

#

that happens we return the min(A[i], B[j]). If at some point of the algorithm one of the arrays is empty then we return the kth element of the other array. This algorithm runs in O(log k), but since k can be at most 2n the worst case running time is O(log n).

5) Your friend claims that it is asymptotically faster to square an n-bit integer than to multiply two n-bit integers. Should you believe your friend? Why? ! I would say that my friend is a liar! Multiplying two n-bit numbers has the same asymptotic complexity as squaring an n-bit number. If we assume that there is some optimal algorithm that finds the square of a number in 𝑂(𝑓(𝑛)), we can show that if squaring an n-bit number takes 𝑂(𝑓(𝑛)) then multiplying two n-bit numbers will also take 𝑂(𝑓(𝑛)). To find a*b first we must define n and m as two numbers such that 𝑎+ = +𝑚 + +𝑛 (I) 𝑏+ = +𝑚 − +𝑛 , (II) solving this equation system we get that 𝑎+ + +𝑏+ = +2𝑚 )*+*, 𝑚+ = + # so if we substitute m in 2 and solve for n we get )*-*, 𝑛+ = + #

since we want to find a*b we must multiply equations (I) and (II) to get 𝑎 ∗ 𝑏 = (𝑚 + 𝑛 )( 𝑚 − 𝑛 ) = (𝑚# − 𝑛 # )+ so if we substitute n and m we get ()*+*,)! ()*-*,)! 𝑎 ∗ 𝑏 = (+ % − + % )+

this means that we can calculate 𝑎 ∗ 𝑏 by squaring two numbers (a+b) and (a-b). This takes O(2𝑓(𝑛)) or O(f(n))....