Introduction to Analysis of Algorithms Final Exam CS4820/5820 Fall 2021
This exam consists of 6 questions on a total of 10 pages, worth a total of 70 points. There is an extra (empty) page included at the end. Please provide the answer at the space right under the question. You may also use the back of this page or the last page for additional space, but please mark on the question page itself if you are using this as part of an answer. You have 2 hours and 15 minutes to complete this exam.
This exam is closed-book and closed-notes. When you are asked to design and analyze an algorithm, you must present a full description of the algorithm and an analysis of its running time. The algorithm’s running time is required to be polynomial in the input size. You may reduce problems to ones presented in textbooks, lectures, or homework, in which case you need not explain the details of the algorithm, and can simply state its running time. However, you still must provide the full protocol to reduce to the existing problem, as well as a correct running time analysis of the combined process of reducing the new problem to the existing one and executing the algorithm for the reduced problem. On this exam, to save time, please only prove what we ask for in each problem.
Important: Follow the directions to each question carefully. If you are printing the exam, place answers in designated spaces. If you are writing the exam on separate paper, clearly label which of your work corresponds to each question.
STATEMENT:
• I am aware that my score on this exam may increase or lower my final letter grade.
• I took this exam without accessing any course materials or notes.
• I understand that academic integrity violations on this exam result in an F in the course.
SIGNATURE:
(If you did not print the exam, please state at the top of your first page that you read all instructions, and sign your statement.)
This page can be used as extra space. Please mark on the question page itself if you are using this page for part of an answer.
2
Net ID:
Part II: Long Answer Questions (39 points)
- (2+14 points) A electronic toy company must include resistors between certain components of a toy’s circuitry. More specifically, if they need to ensure a resistance R between two components, they will need to include individual resistors whose resistance values sum to R1. Each resistor, regardless of its resistance, has the same cost, so the company wishes to minimize the number of resistors used. That is, given a set of possible resistor types r1 < ⋅⋅⋅ < rk, the company must select the number ni of units of resistor ri to buy for each 1 ≤ i ≤ k, such that R = ∑ki=1(ni ⋅ ri) and ∑ki=1 ni is minimized.
Currently, the toy company works with a supplier that sells 1Ω, 4Ω and 16Ω resistors. To determine which resistors to buy, the company utilizes a greedy procedure that considers the resistors in decreasing order resistance ri, and takes as many of each as possible without going over the target resistance R:
for i = k to 1: n i ← ⌊ rR ⌋
i
R ← R − ni ⋅ ri end for
This procedure returns the optimal selection for this set of resistors.
(a) The supplier introduces a new 9Ω resistor to their catalog. Argue that the greedy procedure is no longer always optimal.
(b) Due to supply chain issues, the toy company would like the flexibility to switch between suppliers. However, each supplier offers a different set of resistor types. Design an algorithm that takes in a set of resistor types r1 < ⋅ ⋅ ⋅ < rk and a target resistance R, and returns the optimal selection (n1, . . . , nk) as described above. If the target resistance cannot be achieved (for example, if each ri is even, but R is odd), this should be reported.
Assume all inputs are positive integers.
Give a pseudo-polynomial-time algorithm to solve this problem. Your algorithm should return the number of each resistor type (n1, . . . , nk) or report that no solution can achieve the target resistance. You should give the algorithm and analyze the running time, but you do not have to give a proof of correctness. Pseudocode is acceptable, as long as you explain in English the intended meaning of your variables, and you explain the reasoning behind your algorithm.
(Write your answer on the following page.)
1Here, we are only concerned with wiring resistors in series, so the total resistance equals the sum of the resistances. 6
Net ID:
- (8+5 points) A company wishes to treat its employees to donuts. An assorted box from Ed- mond’s donuts contains one donut of each of their 12 flavors. From each of their n employees, the company collects a non-empty list Di ⊆ {1, . . . , 12} of the donut flavors that employee i likes. They must to determine how many assorted boxes of donuts they should order so that every employee gets a donut that they like.
In the following two subparts, you are asked to design two algorithms. You must fully explain how your algorithms work (for example, explain the meanings of all variables other than loop counters) and analyze their running times, but you do not need to provide proofs of correctness.
(a) Design a polynomial time algorithm that takes as input the n flavor lists D1,…,Dn and an integer b. The algorithm should return whether ordering b boxes is sufficient to ensure everyone gets a donut that they like.
(b) Design a polynomial time algorithm that takes as input the n flavor lists D1,…,Dn and returns the minimum number of boxes that must be purchased to ensure everyone gets a donut that they like. Regardless of your progress, you may assume that you have a correct and sufficiently fast implementation of the algorithm from part (a). For full credit, your algorithm’s runtime should match our solution’s.
8
Net ID: - (10 points) An elementary school teacher has a class of n students. For each student s, they have a list of that student’s friends. Assume that these friendship lists are symmetric, so if t is on s’s friend list, then s is also on t’s list. We can model this friendship information as a graph G on n nodes, where (undirected) edges represent mutual friendships.
Suppose that on a particular day, some subset A of the students are absent. The teacher has a worksheet that they would like to pass along to the absent students. The Deliver Papers problem takes as input G, A, and an integer k and asks whether there is a subset P of students such that:
• ∣P∣≤k.
• Each student in P is in school (i.e. not absent).
• Each student in A is friends with at least one student in P .
DeliverPapers is in NP (you do not have to prove this).
Prove that DeliverPapers is NP-hard. That is, argue that Y ≤p DeliverPapers for some NP-complete problem Y .
9
Net ID: