Homework 2

Due Tuesday October 3 at 11:59pm via Gradescope

• Make sure to put your name on the first page. If you are using the LATEX template we provided, then you can make sure it appears by filling in the yourname command.
• This assignment is due Tuesday October 3 at 11:59pm via Gradescope. There is a 24-hour grace period for late assignments. Make sure to submit something well before the deadline.
• Solutions must be typeset. If you need to draw any diagrams, you may draw them by hand as long as they are embedded in the PDF. We recommend that you use LATEX, in which case it would be best to use the source file for this assignment to get started.
• We encourage you to work with your classmates on the homework problems, but also urge you to attempt all of the problems by yourself first. If you do collaborate, you must write all solutions by yourself, in your own words. Do not submit anything you cannot explain. Please list all your collaborators in your solution for each problem by filling in the yourcollaborators command.
• Finding solutions to homework problems on the web, or by asking students not enrolled in the class is strictly forbidden.

Problem 1. Recurrences (10 points)

Suppose we have algorithms with running times T (n) given by the recurrences:

1. $T (n) = 8T (n/2) + n3$
2. $T (n) = 4T (n/12) + n4
3. $T (n) = 5T (n/5) + 5$
4. $T (n) = 4T (n/81) + n1/2$
5. $T (n) = 10T (n/2) + n2.7$ Determine and state the asymptotic running time of each of these five algorithms, and then rank them in ascending order of their asymptotic running time. You do not need to justify your ranking.

Problem 2. Recursion Tree (10 points)

Consider the following recurrence: $T (n) = 3T (n/4) + T (n/8) + n2$ $T (1) = C$ Solve this recurrence with a recursion tree. That is find a function f (n) (whose specification does not involve a recurrence) such that T (n) = O(f (n)). To do this, start by examining the first tree levels of the recursion tree, showing how to compute the amount of work at each level. From here, establish a formula for the amount of work on level i. Then, determine the last level of the recursion tree. Finally, construct a summation which totals the amount of work over all levels and show why this summation is O(f (n)). Your f (n) should follow directly from your analysis. You are welcome to embed a photo of a hand drawn image into your LaTeX file

Problem 3. Improve the MBTA (2+6+4+3 = 15 points)

You have been commissioned to design a new bus system that will run along Huntington Avenue. The bus system must provide service to n stops on the eastbound route. Commuters may begin their trip at any stop i and end at any other step j > i. Here are some na¨ıve ways to design the system:

1. You can have a bus run from the western-most point to the eastern-most point making all n stops. The system would be cheap because it only requires n − 1 route segments for the entire system. However, a person traveling from stop i = 1 to stop j = n has to wait while the bus makes n − 1 stops.
2. You can have a special express bus from i to j for every stop i to every other stop j > i. No person will ever have to make more than one stop. However, this system requires Θ(n2) route segments and will be expensive. Using divide-and-conquer, we will find a compromise solution that uses only Θ(nlogn) route segments, but with the property that a user can get from any stop i to any stop j > i making at most two route segments in total. That is, it should be possible to get from any i to any j > i either by taking a direct route i →j or by taking two routes i →m and m→j. The input to your algorithm should simply be a number n, describing how many stops there are, and the output should be a list of route segments i →j. For example, if the input is n = 4, the output could be the list [(1→2), (1→3), (2→3), (3→4)], which is a set of 4 route segments such that we can travel from any stop i to any stop j > i using at most two route segments.

• (a) For the base cases n = 1,2, design a system using at most 1 route segment.
• (b) For n > 2 we will use divide-and-conquer. Assume that we already put in place routes connecting the first ⌈n/2⌉ stops and routes connecting the last ⌊n/2⌋ stops so that if i and j both belong to the first half, or both belong to the second half, then we can get from i to j in at most two segmets. Show how to add O(n) additional route segments so that if i is in the first half and j is in the second half we can get from i to j making only two stops.
• (c) Using part (b), write (in pseudocode) a divide-and-conquer algorithm that takes as input the number of stops n and outputs the list of all the route segments used by your bus system.
• (d) Write the recurrence for the number of route segments your solution uses and solve it. You may use any method for solving the recurrence that we have discussed in class.
• (e) (Challenge Question! You are not required to submit an answer.) Suppose the MBTA is willing to compromise even further by designing a solution where users may need three segments to get from i to j. Design a solution that uses as few route segments as possible. The number of route segments should be asymptotically smaller than the previous solution. That is, it should use o(nlogn) route segments. For an extra challenge, what if we allow four segments to get from i to j?

Problem 4. A brickin’ awesome problem (2+8+2+3 = 15 points)

Drew’s dad collects bricks.2. The bricks are laid out in a n × n display, meaning there are n2 bricks in total (note that you can visualize this as n rows and n columns). Each brick has an age, which is simply the number of years it has been since the brick was produced. You can think of the input as being a n × n matrix B, where B[i, j] is the age of the brick in position i, j. You have been tasked with finding a brick such that none of the bricks adjacent to it (above, below, left, or right) are older than that brick. It is certainly possible that more than one brick meets this condition, in which case, finding any single brick with this property would suffice. If a brick is on a corner or a side, it only needs to be older than all of the adjacent bricks. You are able to access the age of any single brick in O(1) time. Design a O(n)-time divide-and-conquer algorithm to solve this problem.

• (a)
• (b) Note that there must be a brick with the desired property. That is, a solution exists. Let L be the largest value of any brick and let (x,y) be any brick such that B[x,y] = L. Argue that (x,y) is a brick with the desired property. Can there be a brick (x,y) with the desired property such that B[x,y] < L? If so, give an argument as to why. If not, provide a counterexample. ...