Instructions
CSC373 Fall’20 Assignment 2: Crazy Circus
Due Date: 1st November 2020, 11:59pm ET
1. Typed assignments are preferred (e.g., PDFs created using LaTeX or Word), especially if your handwriting is possibly illegible or if you do not have access to a good quality scanner. Either way, you need to submit a single PDF named “hwk2.pdf” on MarkUS at https: //markus.teach.cs.toronto.edu/csc373-2020-09
2. You will receive 20% of the points for a (sub)question when you leave it blank (or cross off any written solution) and write “I do not know how to approach this problem.” If you leave it blank but do not write this or a similar statement, you will receive 10%. This does not apply to any bonus (sub)questions.
3. You may receive partial credit for the work that is clearly on the right track. But if your answer is largely irrelevant, you will receive 0 points.
Q1 [20 Points] Fruit Frenzy, Revisited
In the dilemma that you helped Dinosaur Bobby solve in Assignment 1, there were n gardens. Each garden i was described by two integers: ei, the easiness of reaching garden i, and qi, the number of fruits in garden i. Garden i was called a smarter choice than garden j if ei > ej and qi > qj .
Bobby is now employed at a circus and wants your help again in selecting a smart garden. But a couple of things are different this time around.
1. First, Bobby wants to find a sequence of gardens (i1, i2, . . . , ik) such that each garden ir+1 is a smarter choice than the previous garden ir; such a sequence is called a chain. Essentially, Bobby wants to impress his manager by saying “Look, I could’ve selected garden i1. But I found a smarter choice i2. And then an even smarter choice i3. . . And then an even smarter choice ik. That’s why I picked garden ik.”
2. Each garden i additionally has a non-negative weight wi. And Bobby wants you to find a chain with the highest total weight.
Design a dynamic programming algorithm to help Bobby.
(a) [5 Points] Define an array or arrays storing the necessary information from subproblems. Clearly define what each entry means, and how you would compute the final answer given the array entries.
(b) [5 Points] Write a Bellman equation and briefly justify its correctness.
(c) [5 Points] Describe a bottom-up implementation to compute the array entries.
(d) [5 Points] Analyze the worst-case running time and space complexity of your algorithm.
1
Q2 [25 Points] The Manager Wants the Tallest Giraffes
You are a new hire at the circus and your manager has assigned you your first task. There are n giraffes in a line, and giraffe i has height H[i]. The manager wants you to study their heights carefully. Later, the manager will ask you a series of queries of the form “What is the maximum height across giraffes i through j?”, where i and j (with i ≤ j) will vary from one query to the next. You ought to be able to answer these queries rapidly.
Of course, there are only Θ(n2) possible queries, so if you pre-compute all the Θ(n2) answers and store them in a table, then you can answer any query in O(1) time simply by looking at your table.
However, the manager wants you to be quicker. You need to study the giraffes’ heights (and pre- compute whatever table you want) in O(nlogn) time. Afterwards, you still need to be able to answer any query in O(1) time simply by looking at your table entries.
(a) [15 Points] Define the table that you would pre-compute. Clearly define what each entry means and how you would answer any query in O(1) time if all the table entries were pre-computed.
(b) [10 Points] Write a Bellman equation for the table entries, justify its correctness, and provide a bottom-up implementation.
Q3 [20 Points] Scheduling Performances
Having moved up the hierarchy, you are now the circus manager. Your first task is to schedule performances for the next n days. Here are some inputs and constraints:
• There are p prepared performances. Each performance requires one ringmaster.
• There are m ringmasters. Ringmaster j can only lead performances in the set Pj.
• Exactly k of the prepared performances should be scheduled on each day.
• No performance should be scheduled twice in the same day (or the audience will get bored!).
• No ringmaster should be scheduled to lead more than L performances across all n days (as you’re not paying them all that much!).
(a) [10 Points] Use the network flow framework to design an efficient algorithm that either finds a feasible schedule or declares that there isn’t one. Clearly define each component of the network.
(b) [10 Points] Justify the correctness of your algorithm. Analyze the worst-case running time of the na ̈ıve Ford-Fulkerson algorithm on your network from part (a).
Q4 [25 Points] Scheduling Staff Duties
Performances are just the “front end”. You also need to schedule the staff to perform various duties during the n-day event in the “back end” for the circus to run smoothly.
Exactly ai staff members should be scheduled on day i. Each staff member j is available on a subset of days Aj ⊆ {1,…,n}, and can be scheduled on at most L days from Aj.
2
(a) [10 Points] Use the network flow framework to design an efficient algorithm that either finds a feasible schedule or declares that there isn’t one. Clearly define each component of the network. Justify the correctness of your algorithm and analyze the worst-case running time of the na ̈ıve Ford-Fulkerson algorithm on your network.
(b) [15 Points] You realize that these constraints are too tight and ask the staff members for help. They agree to the following: each staff member j, in addition to coming in on at most L days from Aj, can also come in on at most L′ days outside of Aj (i.e. from {1,…,n}\Aj). Use the network flow framework to design an efficient algorithm under these relaxed constraints. Justify its correctness and the worst-case running time when using the na ̈ıve Ford-Fulkerson algorithm.
3