Homework #1 Solution

Sharing this PDF file in any way, e.g., via email, uploading to a web site (personal, public, commercial) is




unauthorized.




This file is copyrighted material. Copyright held by Professor Dimitris Achlioptas and UC Santa Cruz.







Each problem is worth 25 points. For each problem you must specify your algorithm clearly, prove that it is correct, give the recurrence for its running time and use the MT to solve the recurrence (just state the final answer). Most of the points will be given for stating your algorithm clearly and for proving that it is correct.




Reminder: For each of the four problems you receive 6 of the 25 points if you write nothing about the problem. If you feel that you have a partial answer worth more than 6 points, e.g., you have an algorithm but can’t prove it correct, or your algorithm can be proven correct but is too slow, you can still write this information as long as you begin your answer by assessing your work. If we find your work as assessed, you will receive at least 6 points.




Maximum Profit



You’ve been hired by a financial company that periodically examines how a particular security has done in the last n days, and then tries to determine the maximum possible profit that could have been made by someone buying and selling that security during those n days.




More formally, let A be an array of n numbers. We wish to find




max (A[k] A[j ]) :

1 j<k n




The idea is that on day j we could buy at A[j] dollars and at a later date, k j, we could sell it for A[k] dollars, making a profit of A[k] A[j]. (Note that in only considering k j we are, implicitly, ignoring the possibility of making money by “short-selling”).




Give a O(n log n) divide-and-conquer algorithm for this task.




“To play or not to play?”






Your friend proposes to play with her the following game. She writes in a piece of paper a list of n positive integers, one after the other. Then a pair of integers, (i; j) from f1; : : : ; ng, is drawn uniformly at random. If the sum of the numbers written between the i-th and j-th number (inclusive), is even, you win the game, otherwise she wins.




Immediately you realize that not every instance of the game is in your favor; thus you modify the rules as follows. After your friend reveals you the list of numbers, you have the option to either accept and proceed to the game, or decline and start over. Give a divide and conquer algorithm that takes as input a list L of n positive integers and computes your probability of winning.







Yet another search problem



Let A[0 : : : n] be an array of n + 1 natural numbers not exceeding n. Let k < n be an integer such that the values of




any two successive entries of A differ at most by k, i.e., jA[j] A[j + 1]j k for all j 2 f0; : : : ; n 1g.




Prove that there exist an index j such that jA[j] jj (k + 1)=2.



Given the number k, find an O(log n) divide and conquer algorithm that finds such an index.
Fool’s Gold



You recently purchased a claim to search for gold along the Trans-Canada Highway. You are only allowed to mine at mile markers i = 1; 2; : : : ; n.




You know that a suitable spot to mine for gold is anywhere that has higher levels of quartz than its neighboring locations, i.e., qi qi 1 and qi qi+1. Each time you hire a surveyor to measure quartz levels, she provides you the quartz levels at mile marker i as well mile markers i 1 and i + 1. The surveyor is extremely expensive so you want to hire her as few times as possible. Develop a divide and conquer algorithm that can identify a suitable spot to mine for gold where the number of times you must hire the surveyor is O(log n).




Assume the quartz levels at i = 0 and i = n + 1 are zero and that all other quartz levels are positive and distinct.





























































































































































2