Homework 1- Algorithms Problem Set 1

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 Ω. (a) n + 1 = O(n4) (b) 22n = O(2n) (c) 2n = Θ(2n+7) (d) 1 = O(1/n) (e) ln2 n = Θ(lg2 n) (f) n2 + 2n−4 = Ω(n2) (g) 33n = Θ(9n) (h) 2n+1 = Θ(2nlgn) (i) √n = O(lgn) (j) 10100 = Θ(1)
2. (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 payoff by buying at some time i and selling at a future time j i, such that both A[j] A[i] and the corresponding difference 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 19−3 = 16 coins. (a) 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
 Algorithms Problem Set 1
Profs. Clauset & Grochow Spring 2018, 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. (b) Explain (1–2 sentences) under what conditions on the contents of A the makeWizardMoney algorithm will return 0 coins. (c) Dumbledore knows you know that makeWizardMoney is wildly inefficient. With a wink, he suggests writing a function to make a new array M of size n such that
M[i] = min 0≤j≤i
A[j] .
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. (d) Use the array M computed from (2c) to compute the maximum coin return in time Θ(n). (e) Give Dumbledore what he wants: rewrite the original algorithm in a way that combine parts (2b)–(2d) to avoid creating a new array M.
3. (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.
(a) Write pseudocode for a simple linear search algorithm, which will scan through the input sequence A, looking for v. (b) 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.
4. (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
 Algorithms Problem Set 1
Profs. Clauset & Grochow Spring 2018, 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)
(a) 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 fixed algorithm is correct. (b) Goyle tells Crabbe that binary search is efficient 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 efficient. Explain who is correct and why.
5. (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
(a) If arrays A and B have size n, what is the worst case running time of the procedure findCommonElement? Provide a Θ bound. (b) 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
 Algorithms Problem Set 1
Profs. Clauset & Grochow Spring 2018, CU-Boulder
(c) 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.)