Problem Set 1 Solution

Advice 1 : For every problem in this class, you must justify your answer: show how you arrived at it and why it is correct. If there are assumptions you need to make along the way, state those clearly.




Advice 2 : Verbal reasoning is typically insu cient for full credit. Instead, write a logical argument, in the style of a mathematical proof.
















1. (10 pts total) For each of the following claims, determine whether they are true or false. Justify your determination (show your work). If the claim is false, state the correct asymptotic relationship as O, , or .




n + 1 = O(n4)
22n = O(2n)



2n = (2n+7)



1 = O(1=n)



(e) ln2 n = (lg2 n)




(f) n2 + 2n 4 = (n2)

33n = (9n)
(h)
2n+1
= (2n lg n)


p




n = O(lg n)



10100 = (1)



(15 pts) Professor Dumbledore needs your help optimizing the Hogwarts budget. You’ll be given an array A of exchange rates for muggle money and wizard coins, expressed at integers. Your task is help Dumbledore maximize the payo by buying at some time i and selling at a future time j i, such that both A[j] A[i] and the corresponding di erence of A[j] A[i] is as large as possible.



For example, let A = [8; 9; 3; 4; 14; 12; 15; 19; 7; 8; 12; 11]. If we buy stock at time i = 2 with A[i] = 3 and sell at time j = 7 with A[j] = 19, Hogwarts gets in income of




3 = 16 coins.



Consider the pseudocode below that takes as input an array A of size n:



makeWizardMoney(A) : maxCoinsSoFar = 0




for i = 0 to length(A)-1 { for j = i+1 to length(A) {







1



CSCI 3104, Algorithms
Profs. Clauset & Grochow
Problem Set 1
, CU-Boulder










coins = A[j] - A[i]




if (coins maxCoinsSoFar) { maxCoinsSoFar = coins }




}}




return maxCoinsSoFar




What is the running time complexity of the procedure above? Write your answer as a bound in terms of n.




Explain (1{2 sentences) under what conditions on the contents of A the makeWizardMoney algorithm will return 0 coins.



Dumbledore knows you know that makeWizardMoney is wildly ine cient. With a wink, he suggests writing a function to make a new array M of size n such that



M[i] = min A[j] :

0 j i




That is, M[i] gives the minimum value in the subarray of A[0::i].




What is the running time complexity of the pseudocode to create the array M? Write your answer as a bound in terms of n.




Use the array M computed from (2c) to compute the maximum coin return in time (n).



Give Dumbledore what he wants: rewrite the original algorithm in a way that combine parts (2b){(2d) to avoid creating a new array M.



(15 pts) Consider the problem of linear search. The input is a sequence of n numbers A = ha1; a2; : : : ; ani and a target value v. The output is an index i such that v = A[i] or the special value NIL if v does not appear in A.



Write pseudocode for a simple linear search algorithm, which will scan through the input sequence A, looking for v.



Using a loop invariant, prove that your algorithm is correct. Be sure that your loop invariant and proof covers the initialization, maintenance, and termination conditions.



(15 pts) Crabbe and Goyle are arguing about binary search. Goyle writes the following pseudocode on the board, which he claims implements a binary search for a target value v within input array A containing n elements.












2



CSCI 3104, Algorithms
Profs. Clauset & Grochow
Problem Set 1
, CU-Boulder




bSearch(A, v) {


return binarySearch(A, 1, n-1, v)


}


binarySearch(A, l, r, v) {


if l <= r then return -1


p = floor( (l + r)/2 )


if A[p] == v then return p


if A[p] < v then


return binarySearch(A, p+1, r, v)


else return binarySearch(A, l, p-1, v)





Help Crabbe determine whether this code performs a correct binary search. If it does, prove to Goyle that the algorithm is correct. If it is not, state the bug(s), give line(s) of code that are correct, and then prove to Goyle that your xed algorithm is correct.



Goyle tells Crabbe that binary search is e cient because, at worst, it divides the remaining problem size in half at each step. In response Crabbe claims that four-nary search, which would divide the remaining array A into fourths at each step, would be way more e cient. Explain who is correct and why.



(10 pts extra credit) You are given two arrays of integers A and B, both of which are sorted in ascending order. Consider the following algorithm for checking whether or not A and B have an element in common.



findCommonElement(A, B) :




assume A,B are both sorted in ascending order



for i = 0 to length(A) { # iterate through A




for j = 0 to length(B) { # iterate through B




if (A[i] == B[j]) { return TRUE } # check pairwise




}




}




return FALSE




If arrays A and B have size n, what is the worst case running time of the procedure findCommonElement? Provide a bound.



For n = 5, describe input arrays A1, B1 that will be the best case, and arrays A2, B2 that will be the worst case for findCommonElement.









3



CSCI 3104, Algorithms
Profs. Clauset & Grochow
Problem Set 1
, CU-Boulder










Write pseudocode for an algorithm that runs in (n) time for solving the problem. Your algorithm should use the fact that A and B are sorted arrays.



(Hint: repurpose the merge procedure from MergeSort.)





























































































































































4