算法代写 | CSC373 Assignment 2: Crazy Circus

这个作业是根据对应的场景设计相应的算法来解决问题
CSC373 Assignment 2: Crazy Circus

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 Θ(n
2
) possible queries, so if you pre-compute all the Θ(n
2
) 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 precompute whatever table you want) in O(n log n) 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
0 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.