CS 330, Spring 2025, Homework 7
Due Wednesday, April 2, 11:59 pm EST, via Gradescope
Homework Guidelines
Collaboration policy You must write up each problem solution by yourself without assistance, even if you collaborate with others to solve the problem. You must also identify your collaborators. If you did not work with anyone, you should write ”Collaborators: none.” It is a violation of this policy to submit a problem solution that you cannot orally explain to an instructor or TA.
Typesetting Solutions should be typed and submitted as a PDF file on Gradescope. You may use any program you like to type your solutions. LATEX, or “Latex”, is commonly used for technical writing (overleaf .com is a free web-based platform for writing in Latex) since it handles math very well. Word, Google Docs, Markdown or other software are also fine.
Content of the Solution. When a problem asks you to design an algorithm, a complete (a.k.a. full credit) solution always consists of a description of the algorithm using pseudocode (thus not actual code) with well-chosen comments, preferable some short and high level description in English so that the reader has an idea of what the code does, a proof of the correctness of the algorithm and a running time analysis.
Here are some guidelines specific to the solution of DP problems: Any solution should cover 4 main parts:
1. Clearly state what the subproblems and variables are. e.g. WIS: OPT(j) is the max value solution on jobs 1; . . . j if sorted by earliest finish time. Knapsack: OPT(i,w) is the max value solution on items 1 . . . i with capacity w.
2. write the recursive formula (including base cases!) and a detailed explanation while the parts of the formula correctly compute the objective. You can omit the induction proof that would apply it to each index.
3. write the pseudocode for your algorithm (bottom-up or top-down are both fine) and analyze its running time. The explanation of the recursive formula serves as proof of correctness, you don’t need to write anything in addition here.
4. (*) write the backtracking algorithm and analyze its running time. No proof needed as the algorithm is mostly reverse-engineering of the recursive formula. However, it will be graded both on correctness and efficiency. (*) You can either write backtracking as a separate algorithm to be run after the DP algorithm or you can incorporate the backtracking steps in your DP algorithm, both are acceptable. Make sure to include clear comments in your code.
Organizing a Conference (Again)
You are at it again! You have been tasked with organizing the schedule for another conference. In order to raise the profile of your conference you decide to invite some very famous speakers to give keynote presentations (keynotes are talks that everybody at the conference attends). Because of this, you have to make sure that you schedule the talks so that none of them overlap. These famous people are very busy and have inflexible schedules. In particular, each of them sends you one specific time interval (si, fi) when they are available. The presence of each potential speaker adds to the prestige of your event. In particular, speaker i contributes vi amount. Unfortunately you are operating on a budget and you can only invite K speakers.
Design a dynamic programming algorithm that takes as input a list T with the availability and prestige of each potential speaker. T [i] = (si, ti, vi) is a tuple with the time interval that speaker i is available and the value of their presence. Further, you also have the budget K as input, each speaker has a ”cost” of 1 unit. After the backtracking, your algorithm should return a set of speakers - within your budget - that maximize the total prestige (value) of your conference.
Catering Events
You are a caterer who provides food for events, such as the above conference. In order to do so you have to buy the ingredients in advance of each event. The amount of ingredients you need depends on the number of participants pi at event i. You cater one event each week, hence you shop for supplies once per week. The wholesale restaurant supplier where you buy your ingredients has two options; you can either get a per person rate r. For example, if there are pi participants then you would pay r · pi total for this week. The other option is to pay a flat rate price c for the whole event, thus your cost for the week is c. However, this latter options requires you to commit to the flat rate 4 weeks in a row. Thus, you pay 4 · c over 4 weeks.
Here is an example input and solution. Suppose that the per person price is r = $150, the weekly flat rate is c = $2000. Your optimal cost for these 15 weeks would be 8c + (11 + 8 + 15 + 10 + 11 + 8 + 5)r = 26200.
|
week
|
1
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
9
|
10
|
11
|
12
|
13
|
14
|
15
|
|
# participants
|
25
|
1
|
50
|
20
|
11
|
8
|
15
|
20
|
10
|
3
|
30
|
10
|
11
|
8
|
5
|
|
solution
|
c
|
c
|
c
|
c
|
r
|
r
|
r
|
c
|
c
|
c
|
c
|
r
|
r
|
r
|
r
|
Write a dynamic programming solution to find the minimum cost travel plan when as input you are given the list P with P [i] = pi the number of participants, for each of the next n weeks. After backtracking you should return the choice (per person r or lat rate c) for each week.