Algorithm Design and Analysis September 15, 2008Pennsylvania State University CSE 565, Fall 2008Adam Smith Handout 5Homework 2 – Due Friday, September 17, 2008Please refer to the general information handout for the full homework policy and options.Reminders• Your solutions are due before the lecture. Late homework will not b e acc epted.• Collaboration is permitted, but you must write the solutions by yourself without assistance,and be ready to explain them orally to a member of the course staff if asked. You must alsoidentify your collaborators. Getting solutions from outside sources such as the Web or studentsnot enrolled in the class is strictly forbidden.• To facilitate grading, please write down your solution to each problem on a separate sheet ofpaper. Make sure to include all identifying information and your collaborators on each sheet.Your solutions to different problems will be graded separately, possibly by different people, andreturned to you independently of each other.• For problems that require you to provide an algorithm, you must give a precise description ofthe algorithm, together with a proof of correctness and an analysis of its running time.You may use algorithms from class as subroutines. You may also use any facts that we provedin class or from the book.Reading Review chapter 4.1-4.5 in Kleinberg Tardos.Exercises These should not be handed in, but the material they cover may appear on exams:1. Exercises in Chapter 4.2. (Caching) In our discussion of optimal caching, we used the fact that any eviction schedule maybe changed to a reduced eviction schedule without affecting its cost. This is stated informally inthe book (Lemma 4.11 on page 134).Let us make this more precise. If an eviction schedule brings an item d into the cache in astep where the d was not requested, we say the eviction was unreduced. Prove the followingby induction on the number of unreduced items: Let S be any eviction schedule which has nounreduced evictions up to some step j. There exists a reduced schedule¯S that brings in as mostas many items as S and that performs the same actions as S in the first j steps.3. Point out the error in the following proof by induction.Claim 1 In any set of h horses, all horses are the same color.Proof: We proceed by induction on the number h of horses. (Base case) If h = 1, then there isonly one horse in the set, and so all the horses in the set are clearly the same color.1(Induction Step) For k ≥ 1, we assume that the claim holds for h = k and prove that it is truefor h = k + 1. Take any set H of k +1 horses. We show that all horses in this set are of the s amecolor. Remove one horse from this set to obtain the set H1with just k horses. By the inductionhypothesis, all the horse s in H1are the same color. Now replace the removed horse and removea different one to obtain a the set H2. By the same argument, all the horses in H2are the samecolor. Therefore all the horses in H must be the same color, and the proof is complete.4. (Analysis of d-ary heaps) A d-ary heap is like a binary heap, describe d in Chapter 2.5 ofKleinberg Tardos, with the exception that non-leaf nodes have d children instead of 2.(a) How would you represent a d-ary heap in an array?(b) Implement Parent(i) that, given the index i of a node, returns the index of its parent andChild(i, k) that, given the index i of a node, returns the index of its kth child.(c) What are the minimum and the maximum number of elements in a d-ary heap of height h?(d) Design an efficient implementation of Heapify-Up in a d-ary min-heap, analogous to theprocedure on page 61 of KT. Analyze the running time of your algorithm in terms of d andn.(e) Design an efficient implementation of Heapify-Down in a d-ary min-heap, analogous tothe procedure on page 63 of KT. Analyze the running time of your algorithm in terms of dand n.(f) Suppose we implement a priority queue using a d-ary heap. Give the running times of alloperations, described on pages 64–65 of KT, in terms of d and n.Problems to be handed inPage limits: The answer to each problem should fit in 2 pages (or one double-sided sheet) ofpaper. Longer answers will be penalized.1. (Asymptotic Notation) Let f(n) and g(n) be asymptotically positive functions. Prove ordisprove (by giving a counterexample) each of the following conjectures.(a) Let f(n) a positive function. Prove or disprove: f (n) = Θ(f(n/2)).(b) Let f1, f2, f... be an infinite sequence of positive functions such that for all k ≥ 0, we havefk(n) = O(n). Prove or disprove:Pni=1fi(n) = O(n2).(c) For what positive number a does the following hold (prove the correcntess of your answer):The probability that a fair coin flipped n times (independently) comes up heads e xactlyn/2 times is Θ(n−a).(Hint: use Stirling’s approximation to approximate the number of strings in {0, 1}nthathave exactly n/2 ones. Stirling’s approximation isn! = (√2πn)(ne)n(1 + wn) ,where wn≥ 0 for all n, and wn= O(1n).)(d) Prove thatPni=1log2(i) = Θ(n log2(n)). (Hint: this sum is bounded below byn2log2(n2).)2. (Greedy algorithms: Matching points to intervals) Chapter 4, Problem 16.3. (Greedy Algorithms: El Goog) Chapter 4, Problem 7.4. (Greedy Algorithms: Structural Argument) Chapter 4, Problem