Benny, is taking his CS 325 algorithms exam which consists of n questions. He no

Question

Benny, is taking his CS 325 algorithms exam which consists of n questions. He notices that the professor has assigned points { p1, p2, ..., pn } to each problem according to the professor's opinion of the difficulty of the problem. Benny wants to maximize the total number of points he earns on the exam, but he is worried about running out of time since there is only T minutes for the exam. He estimates that the amount of time it will take him to solve each of the n questions is { t1, t2, ..., tn }. You can assume that Benny gets full credit for every question he answers completely. Develop an algorithm to help Benny select which questions to answer to maximize his total points earned. Note: NO partial credit is assigned to problems that are only partially completed.

(a) Verbally describe a DP algorithm to solve this problem.
(b) Give pseudocode with enough detail to obtain the running time, include the formula used to fill the table or array.
(c) What is the running time of your algorithm? Explain.
(d) Would Benny use this algorithm if the professor gave partial credit for partially completed questions on the exam? Discuss.

Explanation / Answer

Solution:

a)

b)

Pseudocode:

c)

Running time: The running time of the algorithm will be n log n, since we are sorting the weight and O(n) time will take to pick the questions.

T(n)= O(n log n)

Correctness: SInce we are answering the questions in the order of the reward in proportion with time, so the algorithm will give us the optimal result.

d)

Yes, but at last when T is remaining and to>TRemaining then the partial question will be answered.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.