CS 124 Final: Spring 2021
Your name: Instructions:
• Spend at most 180 minutes on the exam, from the time you first see a problem to the last time you write anything in your solutions. (Time spent uploading doesn’t count against your time.)
Time started: Time ended:
• Do not communicate with anyone but the course staff about the contents of the exam.
• Do not use a computer or other electronic aids during the exam for anything except for:
1. (optionally) typesetting your solutions,
2. (optionally) accessing the reference materials in the list below.
3. (optionally) asking clarification questions of the instructors on Ed.
• Do not use any reference materials (e.g. class notes, textbooks, internet) except:
1. Jeff Erickson’s textbook Algorithms at http://jeffe.cs.illinois.edu/teaching/
algorithms/
2. Cormen, Leiserson, Rivest, and Stein’s textbook Introduction to Algorithms
3. Kleinberg and Tardos’s textbook Algorithm Design
4. The note sheet titled “CS-124-Algorithms-review” from Canvas-Files-Exam Prep
5. At most two single-sided letter/A4-sized sheets of paper with your own handwritten notes.
• After you finish the exam, write your name in affirmation of the following statement:
I, , pledge
my honor that I have obeyed all instructions on this page in taking this exam.
After you finish, upload your exam to Gradescope as if it were a problem set.
• You have 180 minutes to earn a maximum of 180 points. We recommend that you read all the problems first, and attack them in the order that allows you to make the most progress. Do not spend too much time on any single problem: We recommend roughly n minutes on an n point problem (leaving time to check your answers).
• You can ask clarification questions of the instructors on Ed.
• Be neat and write legibly and clearly. You will be graded not only on the correctness of your
answers, but also on the clarity with which you express them.
• Do not waste time re-deriving results presented in class or sections. You may simply state and cite them.
1 True/False (32 points)
For each of the following statements, say whether the statement is TRUE or FALSE. Each correct answer is worth 2 points. Incorrect answers are worth 0 points. No explanations are needed.
1. If x is a 2-pseudoprime, then x is also a 4-pseudoprime. TRUE
2. If an iteration of the Ford-Fulkerson algorithm on a network places flow 1 through an edge (u, v), then in every later iteration, the flow through (u, v) is necessarily at least 1.
TRUE FALSE
3. In every directed graph, running a DFS and ordering by decreasing postorder number gives a topological sort.
TRUE FALSE
4. Let G be a directed graph with edge capacities and two vertices labeled s and t, and let GR be the same graph with the edges reversed. The maximum flow from s to t in G necessarily equals the maximum flow from t to s in GR.
TRUE FALSE
5. Let G be a directed graph with edge capacities and two vertices labeled s and t. Suppose we find a max flow F from s to t by Ford-Fulkerson, and delete an edge that had positive flow in F to get a new graph G′. The max flow from s to t in G′ is necessarily less than the max flow from s to t in G.
TRUE FALSE
6. For every pair of positive integers a and b, we can find integers x and y using the Extended Euclid’s Algorithm such that ax + by = 1.
TRUE FALSE
7. Ifpn−1 ≡1 modnforeveryprimep
6 Greedy problem set groups (16 points)
A class contains 2n students numbered 1, 2, . . . , 2n. The teacher wants to group the students into n pairs of 2. Each student k has some set Sk of students they’d be satisfied working with; if k works with a student outside Sk, then k is unsatisfied. (Satisfaction is symmetric: if j ∈ Sk, then k ∈ Sj.) The teacher wishes to maximize the number of satisfied students.
1. (6 points) Suppose the teacher uses the following algorithm: At each step, pair the lowest- numbered unpaired student t with a student in St, starting with student 1. If there are no remaining unpaired students in St, pair student t with any other unpaired student. Give an example where this algorithm yields a number of satisfied students that differs by 2n−2 from optimal. (For partial credit, give an example where this algorithm instead yields a number of satisfied students that differs by at least 2 from optimal.)
2. (10 points) Suppose that for all k, |Sk| ≥ |S|/2. Suppose we randomly pair the students by picking a random two unpaired students, pairing them, and repeating until all students are in pairs. (You may use without proof that every division of the students into n pairs is equally likely.) Show that this yields, in expectation, at least half the optimal number of satisfied students.
7 Minimum-Bottleneck Spanning Trees (25 points)
Let G = (V,E) be an undirected graph with weights we on the edges. A minimum-bottleneck spanning tree of G is a spanning tree such that the weight of the heaviest edge is as small as possible. Note that for minimum-bottleneck spanning trees, we do not care about the sum of the weights of the chosen edges, only the weight of the maximum edge.
1. (20 points) Show that every minimum spanning tree is necessarily a minimum-bottleneck spanning tree.
2. (5 points) Give an example of a graph and a minimum-bottleneck spanning tree of it that is not a minimum spanning tree.
程序代写 CS代考 加QQ: 749389476
8 Restaurant (30 points)
A restaurant has n tables and 2 waiters. Table i is located at coordinates (xi,yi) in the restaurant for i = 1,2,…,n. At the beginning, one waiter is at table 1 and the other waiter is at table 2. We will then receive a sequence of m queries. Each query is simply a number in {1,2,3,…,n} representing that the customer at that table needs some kind of service. Hence, one of the two waiters needs to serve that table. The waiters are complaining of walking too much and so the restaurant has hired you to help them be more efficient.
Suppose an omniscient being has told you in advance the order in which the tables would need service. Let t1, t2, . . . , tm be the sequence of queries (i.e. tables that need service). The goal is to minimize the total walking distance of the two waiters, where the distance between two tables is the standard Euclidean distance. Assume that there is enough time between the queries for whichever of the 2 waiters is chosen to walk to the table and serve it.
1. (5 points) Consider the following greedy algorithm. In order to serve table ti, we will have whichever waiter is closer serve that table. Give an example to show that this greedy algorithm is not optimal.
2. (20 points) Give a O(n2m)-time algorithm that finds the value of the shortest total walking distance. (Hint: how many pairs of positions can the waiters occupy?)
3. (5 points) Give an algorithm for the above problem that satisfies the same time bound and is O(n2) space, or explain why your previous solution already meets that space bound.
Code Help, Add WeChat: cstutorcs