CompSci 161 Design and Analysis of Algorithms Problem Set 5

Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due

CompSci 161 Design and Analysis of Algorithms Problem Set 5 

In CompSci161, your response to each numbered question must be contained within a single piece of paper. Each numbered question must be responded to on a separate page. When you submit to GradeScope, you will need to inform the system which page of your scanned PDF contains the response you want graded. On occasion, we might request you to tag two (or more) parts, even though we know the two parts will be on the same page; when that happens, it usually means we are going to grade the parts separately. Failure to follow these directions will be treated as non-submission for the question(s) affected. 

Please review the syllabus and course reference for the expectations of assignments in this class. Remember that problem sets are not online treasure hunts. You are welcome to discuss matters with classmates, but remember the Kenny Loggins rule. Remember that you may not seek help from any source where not all respondents are subject to UC Irvine’s academic honesty policy. 

1. You’ve decided to play some music late night at your local club and want to impress. To prepare your strategy, you have reviewed your notes and used statistical analysis to figure out which moves get the most applause ending at certain musical measures. In your findings you’ve found that at each measure, you can perform one of three different moves. 

• Jazzy riff: This is short and improvised. How long it lasts is constant, but how you play depends on the ending measure. Played for 1 measure until the end of measure t, it awards you jt applause. Note that j is a vector: the measure on which you end the riff affects the applause earned. 

• Instrumental chorus: Your bread and butter. Both how long it lasts and how you play is constant. Played for 2 measures until the end of measure t, it awards you C applause. Note that C is a constant: an instrumental chorus always earned you C applause. 

• Solo: You play your heart out! Both how long it lasts and how you play depends on the ending measure. Played for kt measures until the end of measure t, it awards you st applause. Note that k and s are vectors: the measure on which you end a solo affects the applause earned. 

Given these statistical models (the vectors j, k, s and the constant C) are correct, you want to figure out the maximum amount of applause you can obtain in n musical measures. Solutions that omit the inclusion of the “solo” option but are otherwise correct will receive reasonable partial credit.

Questions 2 and 3 are on the next digital page. 

2. When their respective sport is not in season, UCI’s student-athletes are very involved in their community, helping people and spreading goodwill for the school. Unfortunately, NCAA1 regulations limit each student-athlete to at most one community service project per semester, so the athletic department is not always able to help every deserving charity. For the upcoming quarter, we have S student-athletes who want to volunteer their time, and B buses to help get them between campus and the location of their volunteering2 . There are F projects under consideration; project i requires si student-athletes and bi buses to accomplish, and will generate gi > 0 units of goodwill for the university. 

If you are having trouble solving this problem, look at the 0-1 Knapsack Problem in the textbook. Remember, just because you have to be the sole provider of answering this question for yourself doesn’t mean you can’t ask for help on related problems! 

3. Planning lectures can be quite the challenge. Luckily, I have already made a few key decisions already. 

• Use at most M minutes per lecture. 

• Teach all n topics and teach them in order (Topic 1 must be taught before Topic 3). • Allocate topic i exactly ti minutes. 

• Topics cannot run over into another lecture (It is guaranteed that ∀i ti ≤ M). 

• I can have as many lectures as I want. 

If I was trying to minimize the number of lectures, I could just try to cover as many topics as possible per lecture until I finish them. However, my goal is to provide the best education experience and I have noticed that some topics work together better than others. According to my findings, I have found students receive Eij engagement when I cover topics i through j in the same lecture given that i ≤ j. 

If you would like to assume that Eij = −∞ whenever topics i . . . j do not fit into a single lecture spot, you may. 

Given the topic time list t and the engagement matrix E, design a dynamic programming solution to find the maximum total engagement I can achieve by teaching all n topics in order without exceeding M minutes per lecture. 

发表评论

电子邮件地址不会被公开。 必填项已用*标注