CS 124 Final exam: Spring 2023
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 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, for extension students or with prior approval typesetting your solutions, 2. for extension students only asking clarification questions of the instructors on Ed.
You may use no notes but up to four singlesided or two doublesided 8.5×11 pages of notes you prepare ahead of time.
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.
Reminder for extension students:
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. Do not spend too much time on any single problem: we recommend roughly n minutes on an n point problem. Read all the problems first, and attack them in the order that allows you to make the most progress.
You can ask clarification questions of the instructors on Edin person.
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 rederiving results presented in class, psets, or sections. You may simply state and cite them.
1 True or False 18 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. The longest increasing subsequence in an array A1,…,n is correctly found by a greedy algorithm that chooses the longest increasing subsequence in A1,…,i starting with A1 and extends it by picking the next element larger than last chosen element. A subsequence doesnt need to have contiuguous elements; for instance, 1,3 is a subsequence of 1,4,3.
True False
2. If a hash function maps n elements into a hash table with m slots, then the probability that a new lookup of an element which isnt one of those n 1 is a false positive is at least nm.
True False
3. AdisadvantageofusingaBloomfilterwithk1hashfunctionsmappingtomlocationsoverasingle hash function mapping to m locations is additional computation time.
True False
4. IfGisaconnectedgraphwithedgeweightswhicharedistinctnotnecessarilypositiveintegers,then Kruskals algorithm always finds the same Minimum Spanning Tree for G as Prims algorithm.
True False
5. IfGisaconnectedgraphwithedgeweightswhicharepositivenotnecessarilydistinctintegers,then Kruskals algorithm always finds the same Minimum Spanning Tree for G as Prims algorithm.
True False
6. Given a set S of positive integers and a positive integer k, the problem of finding the sizek subset of S whose sum is greatest is correctly solved by a greedy algorithm which repeatedly chooses the greatest notyetchosen element of S.
True False
7. Let n and m be such that if we pick a random hash function h : 1,…,n 1,…,m then the probability that there is a hash collision i.e., i j 1, . . . , n such that hi h j is within 1
124 of 12. Then for a random hash function h : 1,…,2n 1,…,2m i.e, both domain and range
are doubled, the probability of a hash collision is within 2 of 12. 124
True False
8. For every randomized algorithm A and integer T , if A stops in T steps with probability 12, then A stops in 4T steps with probability 1 24 .
True False
9. Let p 0, 1 and let n and T be positive integers. We take a random walk on a line, starting at n2, where in each step we increase by 1 with probability p and otherwise decrease by 1, except that if we reach 0, the next step is always to 1. Suppose that with probability 12 , that walk reaches state n in
T steps. Then that walk reaches state n in 4T steps with probability 15 . 16
True False
2 False 18 points
Each of the following statements is FALSE. For each of them, prove its false by providing a counterexam
1. For every undirected graph G with V G 1, if G has a vertex v whose degree is less than every
other vertexs degree, then every maximum independent set of G contains v.
2. For every undirected graph G with V G 1, if G has a vertex v whose degree is greater than every other vertexs degree, then every minimum vertex cover of G contains v.
3. For every instance A of the Number Partition problem that is, every list A of nonnegative integers, if the three greatest elements are a, b, and c with a b c and all other elements are less than a, b, and c, then no optimal solution to Number Partition gives a, b, and c all the same sign.
Calculations 34 points
1. 8 points Recall that the resemblance RA, B of two sets A and B is defined as RA, B AB , and
we proved in class that if A,B N and we choose a uniformly random permutation : N N,
the probability that mina : a A minb : b B is RA, B.
a 1pointWhatstheresemblanceofthesetsA1,2,4andB1,2,3?HereN4.
b 7pointsSupposewerestrictourchoiceofpermutationstoderangements,thatis,permutations such that for all x, x x. Whats the probability that if we choose a uniformly random derangement, then mina : a A minb : b B, if A 1,2,4 and B 1,2,3, and N 4?
2. 17 points Suppose I run the FordFulkerson algorithm to find a maximum flow from s to t in the graph below, selecting paths to push flow along by a depthfirst search that explores alphabetically earlier vertices before alphabeticallylater ones. What paths does FordFulkerson push flow along, in order, and how much flow does it push along each? Your answer should be of a form like First, 3 flow on SABT, then 3 flow on SBAT, then . . . .
3. 9 points Yavanya, the head TF for Yales Data Structures and Algorithms class CS 421, is trying to spy on CS 124 office hours. She lurks in a corner of Dunster grille, and writes down the name of each student who walks into office hours. She stores these names in a rooted ternary tree, that is, a tree where each node has 0, 1, 2, or 3 children, and each node stores the name of one student.
A nodes level is the length of the path from the root to that node so the root is level 0, its children are level 1, and so on. Initially, Yavanya is only willing to make nodes at level at most d 1.
A tree is dfull if all nodes at level d have 0 children and all nodes at level less than d have 3 children. Whenever Yavanyas tree is dfull for some d, she emails it to Yadam, the professor of CS421, and increases d by 1. Assume that writing a name down takes O1 time and emailing a tree with n nodes takes On time. Find the amortized runtime of Yavanya inserting a name into her tree.
4 Kind graphs 15 points
1. a directed graph G with nonnegative integer edge weights, 2. a nonnegative integer c, and
3. avertexsVG,
G is called a c, skind graph if both of the following are true:
1. every edge s,w EG has weight 1,
2. for every edge v,w EG with v s, the weight of v,w is c times the minimum weight of edges u,v EG.
For example, the left graph below is an example of a 124, Skind graph, but the right isnt: SS
A 124 DA 124 D 124 124 1242 124
Sara claims that, for all kind graphs, to find the shortest path from s to some other vertex t, she can run breadthfirst search starting from s tracking prev pointers and ignoring the edge weights and return the path that BFS finds from s to t. Prove that Sara is correct, or give a counterexample where her algorithm fails to find the shortest path. Write your solution on the following page.
Extra page for problem ??
5 Turkish Coins 10 points
TF Emin has started a business buying and selling rare Turkish coins. There are n buyers and m sellers of coins. Buyer i wants to buy up to ai coins, and seller j wants to sell b j coins. Transactions can be made of any nonnegative integer number of coinsfor instance, a buyer who wants to buy 124 coins could buy 20 from one seller, 13 from another, and still be willing to buy 91 more. However, because of Turkish legislation, a seller can only sell to a buyer if they are connected online: each seller i has some subset Si of the buyers to whom theyre allowed to sell. Given ai, b j, and Si for all i, j, give an algorithm to find the maximum number of coins that can be sold from the sellers to the buyers. Your algorithm should run in time On3m3, but you dont need to prove this. Prove the correctness of your algorithm.
6 Mimikyu Liars 20 points
Howie has N 2n Pokemon, each of which is either a Pikachu or a Mimikyu, but he cannot tell them apart because they are indistinguishable. However, he is able to perform a pairwise test on 2 Pokemon. If he takes two Pokemon, he can ask each Pokemon the species of the other. Pikachus will always tell the truth and correctly identify the other Pokemons species. Mimikyus may tell the truth, but may not.
1. 2 points If a test between two Pokemon says that both are Pikachus, what could be the possible true species of the two Pokemon?
2. 1 point If a pairwise test says that at least one Pokemon is a Mimikyu, is it possible for both Pokemon to be Pikachus? Explain very briefly why or why not.
3. 16 points Let NP be the number of Pikachus and let NM be the number of Mimikyus so that NP NM N 2n. Suppose NP NM, that is, Howie has strictly more Pikachus than Mimikyus. Howie does not know NP and NM, only that NP NM. Howie wants to give a Pikachu to his friend Sahil, but needs to be certain that he does not accidentally give a Mimikyu. Give an algorithm for Howie to find a Pikachu. For full credit, your algorithm should use ON pairwise tests, but you dont need to explain why beyond giving your algorithm. Prove the correctness of your algorithm.
7 Kitty! 20 points
Remy is planning her visits around campus today. There are n locations she can visit, with a total of m n walkways connecting some pairs of the locations. Each walkway e has some nonnegative integer weight we representing the emotional support Remy can offer to students on that walkway. Remy can repeatedly walk the same walkway e and provide we emotional support each time, since she will meet new students every time. Remy starts her day at her owners house one of the n locations and has to return to her house after walking along at most k walkway. Give an algorithm for Remy to find the path where she can give the most emotional support. For full credit, your algorithm should run in Okm time and use Okn space, and you should prove so. Algorithms with greater time andor space needs may get partial credit. Prove the correctness of your algorithm.
8 Bandwidth maximization 25 points
Derision QIOS is the latest telephony service that aims to provide quantum communication ability between Austin A, Boston B and Chicago C. Their service is built on existing telephone communication wires, whose network is described by n nodes including A, B, and C and m wires each of which connects two nodes and has a capacity restriction. Derision QIOS would like to use this network to create a collection of undirected paths. Each path has endpoints which are two distinct cities in A,B,C. Each path has a positive integer bandwidth. On every edge e, the total bandwidth of all paths that use e in any direction is at most the capacity of e. Their goal is to maximize the total bandwidth of all the paths. All bandwidths are
A10 10 10 10 1
4,4 4,3 4,2 B 4,1
0,0 1,0 2,0 3,0
nonnegative real numbers. For example, if the network were the grid above where vertices are labelled by their x, y coordinates with A 0, 4, B 4, 2 and C 2, 0 with horizontal edges having capacity of 10 and vertical edges having capacity of 1, a feasible solution would be to route one unit each along each of the following paths:
A0,41,42,43,44,44,34,2B. A0,41,42,43,43,33,24,2B. A0,41,42,42,32,23,24,2B. A0,41,41,31,22,23,24,2B. A0,40,30,20,10,01,02,0C. C2,02,12,23,24,2B.
This would achieve an objective of 6 units of flow which is not maximal.
Formulate the bandwidth maximization problem on a general graph, not just the example above as a linear program with polynomial in n m variables and constraints. Your LP objective should be the total bandwith achieved. Clearly specify all variables, the constraints and the objective function. No proof necessary.
Extra page for problem ??
Poisoned Pond 20 points
1. 5 points Our favorite pond, which has an assortment of beautiful fish, is getting poisoned alas!; and the n fish have to be moved ASAP to another pond. Our volunteers are willing to move the fish over in small containers but each container can only move 5 fish at a time, and one volunteer can move just one container. Furthermore the fish are not all compatible. We have a graph GoFISH with incompatibility information nodes are the n fish and the edges represent pairs of incompatible fish. A container should also only contain fish that are all pairwise compatible. We would like to assign to each volunteer a set of fish that they should move, subject to the constraint that each volunteer gets a set of compatible fish. Subject to these constraints we would like to use a minimum number of volunteers, but because we think that is NPhard, we are willing to settle for an approximation.
Give a constant c 1 and an algorithm that outputs a capproximation to the minimal number of volunteers needed to move the fish. Your algorithm should run in time On5, but you dont need to prove anything about its runtime. Prove the correctness of your algorithm.
2. 15 points Having explored the solution above we decide the volunteerbased process will be too slow and so we are planning to hire a professional fishmoving company. They have custom crates that can each move a different subset of fish and they charge by the crate. Their catalog lists all their crates and the sets S1,S2,…,Sm n of the n fish they can carry. If a crate can move a set Si of fish, we can use it to move any subset of fish T1 S1. Every fish in our collection has at least one crate that can move it and at most 3 crates that can move it. Every crate is GoFISHsafe i.e., no pair of fish in any of the crates form an edge in GoFISH. We wish to pick a minimum subset of these crates that will suffice to move all the fish. Give a 3approximation algorithm to find a small set of crates that can move all the fish. Your algorithm should run in time On5, but you dont need to prove anything about its runtime. Prove your approximation guarantee.
For up to 6 points of partial credit, you can assume that each fish has at most 2 crates that can move it and your approximation factor can be any constant, not necessarily 3.
Extra page for problem
Extra page for problem
Extra page for problem