hw3

CS 381-Fall 2020 Homework 3 Due Date: Feb 29, 2024 at 11:59PM on Gradescope. Instructors: Jeremiah Blocki and Simina Branzi Name: Purdue ID: Learning Objectives The homework is relevant to the following learning objectives: • LO 1.1 Students are able to provide examples of divide-and-conquer algorithms to solve fundamental problems (e.g., Sorting, Multiplication, Skyline, Finding the Mean) and identify the three main components of a divide-and-conquer algorithm (Divide, Conquer and Merge). Students should be able to design their own divide-and-conquer algorithms to solve problems. • LO 1.2 Students are able to provide examples of greedy algorithms and design their own greedy algorithms to solve problems when applicable. Students should be able to provide counter-examples when a proposed greedy algorithm is incorrect. • LO 3.1 Students are able to use induction/invariants to prove that a divide-and-conquer algorithm is correct. • LO 3.2 Students are able to prove that a greedy algorithm is correct using exchange arguments, contradiction and structural arguments. Homework Guideline Reminders • Assignments must be typed. Submit one pdf file to Gradescope by 11:59PM, or else late penalties will apply. The pdf file can include hand-drawn images of figures. • Each question needs to start with the resources and collaborator (RC) statement. You will not be penalized for using resources or having collaborators if your answers are expressed in your own words. If you consulted no resources outside of course material or had no collaborators, you must state so. A question without a complete RC statement will not be graded. 1

Question 1 (25 points) (Double Inversions) Given an array A with n positive integers a 1 , . . . , a n ≥ 1 we say that a pair ( i, j ) forms a double inversion if i < j but a i > 2 a j . If j = i + 1 we call the pair ( i, j ) a consecutive double inversion. (a) (7 points) Alice claims that if the array contains a double inversion ( i, j ) then the array must contain a consecutive double inversion. Do you agree with Alice’s claim? If so prove that Alice’s claim is true. If not provide a counterexample. (b) (18 points) Give an efficient algorithm to count the number of double inversions. Prove that your algorithm is correct and analyze the running time of your algorithm. Collaborators: Resources: 2

Question 3 (25 Points) There are n beaches in Pirates Cove, and Captain Jack Sparrow has buried his immense treasure chest on one of these beaches. You do not know which beach Captain Jack Sparrow picked, but after consulting with historical experts you have determined probability values p 1 , . . . , p n ≥ 0 such p i denotes the probability that Captain Jack Sparrow burried his treasure at beach i . You have also consulted with engineers and have found costs c 1 , . . . , c n ≥ 1 where c i denotes the cost of a thorough search of beach i e.g., the cost to rent digging equipment and transport that equipment to beach i . You may assume that the probabilities and costs are accurate and you may assume that p 1 + . . . + p n = 1 i.e., one of the n beaches does contain the treasure. However, the probabilities are not all equal i.e., it may be less likely that captain Jack buried his treasure on some of the beaches. Similarly, the cost c i to conduct a thorough search of beach i may vary from beach to beach. Because the treasure is said to be immense you are determined to find it and plan to continue digging up beaches until you find the treasure. However, you want to order your search to minimize your expected guessing costs. (a) (4 points) Suppose that you do not strategically order your searches and simply check beach 1, then beach 2 etc... stopping once you find the buried treasure. Let X be a random variable indicating your total cost e.g., if you find the treasure on beach 3 then X = c 1 + c 2 + c 3 since you would pay to dig up beaches 1 , 2 and 3 before you found the treasure. Give a formula for the expected cost E [ X ] if you follow this strategy. (b) (7 points) Jane proposes the following greedy strategy: Check beaches in descending order of probability i.e., search at the most likely beach first then the second most likely etc... (For simplicity you may assume that beaches are relabeled such that p 1 ≥ p 2 ≥ . . . ≥ p n ). Does Jane’s greedy strategy minimize the expected cost? If so you should prove that Jane’s algorithm is correct. If not you should provide a counter-example. (c) (7 points) Blackbeard proposes the following greedy strategy: Check beaches in as- cending order of cost i.e., check the cheapest beach first then move on to the second cheapest beach etc... (For simplicity you may assume that beaches are relabeled such that c 1 ≤ c 2 ≤ . . . ≤ c n ). Does Blackbeard’s greedy strategy minimize the expected cost? If so you should prove that Blackbeard’s algorithm is correct. If not you should provide a counter-example. (d) (7 points) Calico proposes the following greedy strategy. For each beach i define the cost-price ratio r i = c i /p i and check beaches in ascending order of their cost-price ratio i.e., check the beach with the smallest cost-price ratio first then move on to the beach with the second smallest ratio etc... (For simplicity you may assume that beaches are relabeled such that r 1 ≤ r 2 ≤ . . . ≤ r n ). Does Calico’s greedy strategy minimize the expected cost? If so you should prove that Calico’s algorithm is correct. If not you should provide a counter-example. Collaborators: Resources: 4

Question 4 (25 Points) Jane is now a baker at Blocki’s Blasted Bakery (BBB), and she bakes cakes of varying sizes for her customers. She has to pack the cakes in boxes and send them out for delivery at the end of the day. She bakes the cakes in order of when the customer places their order, and she must pack the cake before starting the next cake. She can use as many boxes as she needs, but the delivery cost is dependent on the number of boxes she uses. She can stack several cakes in the same box, but she cannot stack a larger cake onto a smaller cake or it will collapse. She seeks out help from the students in CS381 as she wants to minimize the delivery cost. More precisely the input to our algorithm is an ordered list of cakes’ sizes e.g., [52, 32, 38, 10, 18]. The output is a list of valid stacks of cakes. A valid stack should be non-collapsing e.g., the stack (32 , 38) would collapse since the larger cake (size 38) is on top of the smaller one (size 32). Similarly, a valid stack should respect the original ordering of cakes e.g., the stack (38 , 32) is invalid because the cake with size 38 would have been baked/packed after the cake with size 32. The goal is to minimize the number of stacks of cakes. For this problem we will assume that there is no limit on the height of a stack. Since cakes must be stacked in order, we could, for example, stack cake 1 on box 1, cake 2 on box 2, cake 3 on box 3, cake 4 on box 2, and cake 5 on box 1 as shown below. However, the optimal solution is 2 boxes as follows. (a) (13 points) Devise a greedy algorithm which returns a packing of the cakes that mini- mizes her delivery cost. Analyze the time and space complexity of your algorithm. (b) (12 points) Prove the correctness of your algorithm i.e. prove that the number of boxes used by your greedy algorithm is no more than number of boxes used by any optimal algorithm. Collaborators: Resources: 5