1 Format and Logistics
2 Topics Covered
Final Exam Practice Problems
2.1 MathFundamentals …………………………………. 2 2.2 GraphSearch…………………………………….. 2 2.3 MinimumSpanningTrees ………………………………. 3 2.4 Greedy………………………………………… 3 2.5 DivideandConquer …………………………………. 3 2.6 DynamicProgramming ……………………………….. 3 2.7 RandomizedAlgorithmsandCryptography ……………………… 4 2.8 LinearProgrammingandNetworkFlows……………………….. 4 2.9 NP-Completeness…………………………………… 4
3 Practice Problems
1 Format and Logistics
You will have 3 hours to complete an exam whose format is very similar to that of the midterm. It will be 1.5 times the length of the midterm, but you have twice the amount of time, so it should be a little easier.
You can expect short answer questions like true/false, multiple choice, run this algorithm and example/counter- example as well as many long answer questions that ask you to give and analyze an algorithm to solve a problem.
Solutions to all problems will be released at 10pm on Monday May 8, 2017. In the meantime, we strongly suggest that you try to work out as many of these problems as possible.
2 Topics Covered
There will be an emphasis on the material from the second half of class as well as important topics from the first half of the class.
This is a pretty comprehensive list of topics for the entire course, but anything said in lecture is fair game for the exam.
2.1 Math Fundamentals
• Coin Flipping and basic statistics.
• Induction. If P (n) is a statement (“2n is even”), P (1) is true, and ∀n, P (n) → P (n + 1), then ∀n,
P(n) is true.
• Big-O Notation. o, O, ω, Ω, Θ and identifying which of these relations hold for two functions.
• Recurrence Relations. Solve simple ones by finding a pattern and proving them with induction. More complicated recurrences can be solved using the Master Theorem (must memorize)
2.2 Graph Search
• Representation. Adjacency list versus adjacency matrix
• Depth First Search (DFS). Uses a stack to process nodes, Pre and post order numbers, labels for the edges (tree, forward, back, cross).
Important Applications. Detecting cycles, topological sorting, finding strongly connected components
• Breadth First Search (BFS). Uses a queue to process nodes, can be used to find the shortest path when all edge weights are 1.
• Dijkstra’s Algorithm. Single source shortest path for non-negative edge weights. Uses a heap or priority queue to process nodes. Does not work when there are negative edge weights (why?).
• Heaps. binary heap implementation, operations: deleteMin, insert, decreaseKey, how they are used in Dijkstra’s algorithm
• Bellman-Ford Algorithm. Single source shortest path for general edge weights, edge relaxation procedure (referred to as update in the lecture notes), detecting negative cycles
• Shortest Path in DAG. Can be done in linear time via dynamic programming regardless of edge weights.
2.3 Minimum Spanning Trees
• Basic Properties. Connected, acyclic, |E| = |V | − 1.
• Cut Property: The basis for why our MST algorithms are correct, allows us to greedily add edges
to a sub-MST.
• Prim’s Algorithm: Implemented in a similar fashion as Dijkstra’s, builds MST from a single vertex.
• Kruskal’s Algorithm: Implemented using a union-find data structure, builds MST from lightest edges of the graph
• Disjoint Forest Data Structure: Maintain a bunch of sets that can be combined efficiently Operations: makeset(x), find(x), union(x,y)
Heuristics: Union by Rank, Path Compression
2.4 Greedy
• Main Idea: At each step, make a locally optimal choice in hope of reaching the globally optimal solution.
• Horn Formula: set all variables to false and greedily set ones to be true when forced to
• Huffman Coding: find the best encoding by greedily combining the two least frequently items
• Set Cover: greedy approximation algorithm with O(log n) performance ratio, showed on problem set 3 that we can actually achieve Θ(log n) by example.
2.5 Divide and Conquer
• Main Idea: Divide the problem into smaller pieces, recursively solve those, and then combine them in the right way.
• Mergesort and Stoogesort.
• Integer Multiplication. Perform 3 multiplications on n/2 digit numbers, and then do some addi-
• Strassen’s Algorithm. Multiplies two n × n matrices by doing 7 multiplications on n/2 × n/2 matrices.
• Selection. Finds the kth smallest element in a n-length list in O(n) by picking a (random or not random) pivot, partitioning based on the pivot, then recursing on one of the two sublists.
2.6 Dynamic Programming
• Main Idea: Maintain a lookup table of correct solutions to sub-problems and build up this table in a particular order.
• Run-time and Space Analysis. How does one go about analyzing the time and space complexity of a DP algorithm
• String Reconstruction. Tries to find where the first dictionary word ends by checking all possible breaking points.
• Edit Distance. Tries all possibilities of insert, delete, change on letters that are different.
• All Pairs Shortest Paths. Uses the idea that the shortest path to a node must have come via one of the neighboring nodes.
• Traveling Salesman. DP can provide better exponential-time solutions to NP-hard problems.
2.7 Randomized Algorithms and Cryptography
• Hashing: Relationship to the birthday problem, balls and bins.
• Bloom Filters: Uses less space than a hash table, but in return also may not give you the correct answer all the time. Has some probability of giving a false positive (i.e. saying something is in the bloom filter when it really isn’t).
• Fingerprinting: Probabilistic technique for pattern matching, how to efficiently compute all fin- gerprints by having a sliding window, decreasing failure probability by choosing a prime p.
• Document Similarity: Set resemblance, shingling, document sketch, failure probability given say 90 out of 100 entries in the sketch match.
• Primality Testing: Fermat’s test, a-psuedoprime, witness, Carmichael number, Rabin-Miller test- ing, non-trivial square root
• RSA Encryption: Extended Euclidean algorithm, modular exponentiation (repeated squaring with mod), public key, private key, factoring is hard
• Random Walks: Randomized algorithm for 2-SAT by randomly choosing one variable in an un- satisfied clause and flipping it. Recurrence relation for expected number of steps until reaching a boundary.
2.8 Linear Programming and Network Flows
• Linear Programming: Objective function and constraints must all be linear functions of the variables, Simplex algorithm. Duality (max flow LP to min cut LP, row player LP to column player LP)
• Max Flow: Intuitive formulation with water, reduction to linear programming with conservation, non-negativity, and capacity constraints. If capacities are integral, then there exists an integral max flow solution. Solving matching problems
• Ford-Fulkerson Algorithm: Finds augmenting paths in the residual graph until none can be found anymore. Run-time is O(|E|f∗).
• Min-Cut Max Flow: The value of the minimum s − t cut in a graph is exactly equal to the value of the maximum s − t flow. How to find this min cut given the residual graph from Ford-Fulkerson.
• Two-Player Games: Row player LP and column player LP, solving for the value of the game 2.9 NP-Completeness
• Definition of P and NP: NP requires a polynomial-length certificate that verifies the instance to be yes. P ⊆ NP
• Polynomial-time Reductions: Show that A is easy by reducing A to B, which is known to be easy. Show that A is hard by reducing B, which is known to be hard, to A.
• NP-Completeness: Is in NP and all other problems in NP reduce to it. Circuit SAT is NP- complete. Circuit SAT → 3-SAT, 3-SAT → Integer Linear Programming, 3-SAT → Independent Set, Independent Set → Vertex Cover, Vertex Cover ↔ Maximum Clique
• Local Search: Start with a set of possible solutions and an easy to compute neighbor function. Try to minimize a cost function by moving to neighbors in a particular way.
• Approximations: O(log n), 2-approximation for vertex cover, randomized and local search max cut approximation, 2-approximation for Euclidean travelling salesman probelm, LP relaxation, Max-SAT with randomness,
3 Practice Problems
Exercise (True or False). Answer True or False to the following questions:
1. If x is a 2−psuedoprime, then x is also a 4-psedoprime.
2. Letxbeanintegerandwritex−1=2t·uwithuodd. Then,ifforsomea,a2iu =1 modxbut a2i+1u ̸= −1, 1 mod x, then x is composite.
3. When using both the Union by Rank and Path Compression heuristics, each find operation takes O(log∗ n) time.
4. Kruskal’s algorithm is better for dense graphs, while Prim’s algorithm with a Fibonacci heap is better for sparse graphs. (Recall that Fibonacci heap gives O(1) insert and O(log |V |) delete-Min).
5. 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 at least 1.
1. True. By definition, 2x−1 = 1 mod x. Squaring both sides, this implies that 4x−1 = 1 mod x. This is why when we look at pseudoprimes, we only need to check 2,3,5,7… pseudoprimes, and not 4, 6, 8…
2. False. It is the wrong direction for Rabin-Miller Testing. We should be checking for non-trivial square roots.
3. False. The run-time is O(log∗ n) amortized. This means that one operation may take longer, but on average, each operation takes O(log∗ n).
4. False. Kruskal’s is better for sparse graphs and Prim’s for dense graphs. Kruskal’s runtime is O(|E| log |V |), while Prim’s can run in O(|E| + |V | log |V |) amortized time when using a Fibonacci heap.
5. False. A later augmenting path may pass through (v, u), causing the flow on (u, v) to be decreased.
Exercise (Big O Only). Is it possible to find two functions f(n),g(n) such that f(n) = O(g(n)), but f (n) ̸= o(g(n)), f (n) ̸= Ω(g(n))? If so, give an example. If not, give a proof.
The challenge here is to come up with 2 functions such that big O is the only relationship that holds between them. An example of such a pair of functions is f(n) = nsinn and g(n) = n. It is clear that f (n) ≤ 1 · g(n). It is also clear that f (n) ̸= o(g(n)) because the limit of the ratio does not exist. We also have that f(n) ̸= Ω(g(n)) because f(n) can be arbitrarily small when sinn = −1 for example.
Exercise (Cyclic Sorted Array). You’re given an array A of n distinct numbers that is sorted up to a cyclic shift, i.e. A = (a1,a2,…,an) where there exists a k such that ak < ak+1 < ... < an < a1 < ... < ak−1, but you don’t know what k is. Give an efficient algorithm to find the largest number in this array.
Here’s a recursive solution based on binary search that runs in O(log n) time.
First, we check that the array isn’t cycled at all if an > a0, then we can return the last element (which will be the greatest), an. Otherwise, a0 > an, and start at the middle element am of the entire array. If am > a0, then move to the right half of the array and recurse. Otherwise, if am < a0, move to the left half of the array and recurse.
Exercise (Counting Permutations). How many permutations of {1, 2, . . . , N } have exactly K inversions? An inversion is a pair of numbers i, j in the permutation such that i > j but i comes before j. For example, for N = 3 and K = 1 the answer is 2: {2,1,3} and {1,3,2}.
We use dynamic programming on N and K, and at each step, we decide where the smallest number goes. • Definition: Define X[i, j] to be the number of permutations of {1, 2, 3 . . . , N} that have exactly j
inversions. Our desired answer is X[N, K].
• Recurrence: Consider the element i. Given the any permutation of 1, 2, . . . , i − 1, we can insert i into any of the i slots (i.e. before 1, between 1 and 2, between 2 and 3… after i − 1). Inserting all the way at the beginning causes i − 1 inversions, while inserting all the way at the end incurs 0 inversions. Therefore, we have:
Pi−1 X [i − 1, j − l]
j < 0 i=0,j=0 otherwise
• Analysis: The run-time is O(N2K) because there are O(NK) states of the DP and each takes O(N) time to compute. The space complexity is naviely O(NK), but since we are only interested in the count of the number of permutations and not the permutations themselves, we can get away with O(K) space by only storing each row X[·,K] of the table at a time.
Exercise (Shortest Path LP). Given a weighted, directed graph G = (V,E), with weight function w mapping edges to positive real-valued weights, a source vertex s, and a destination vertex t. Show how to compute the value d[t], which is the weight of a shortest path from s to t, by linear programming.
Hint: Have variables x(u,v) for each edge and think about constraints similar to that of flow.
Let l(u, v) be the length of the edge (u, v). x(u,v) is 1 when (u, v) is in the shortest path from s to t and 0
Code Help, Add WeChat: cstutorcs
otherwise:
minimize X l(u,v)x(u,v) (u,v)
subject to X x(u,s) − X x(s,w) = −1 uw
X x(u,t) − X x(t,w) = 1 uw
X x(u,v) − X x(v,w) = 0 for every vertex v uw
x(u,v) ≥ 0 for every edge (u, v)
Note that it is possible for this LP to give us a non-integral solution, but the length of the shortest path computed is always correct.
Exercise (Dijkstra’s Variations). In lecture, we showed that Dijkstra’s algorithm may not work correctly if negative edge weights are present. In this problem. Let G = (V,E) be a weighted, directed graph with no negative-weight cycles. For each of the following property of G, give an algorithm that finds the length the shortest path from s to all other vertices in V . In both cases, your algorithm should have the same run-time as that of Dijkstra’s.
1. G only has one negative edge. Give an algorithm to find length of the shortest path from s to all other vertices in V .
2. The edges leaving from the source s may have negative weights, but all other edges in E have non- negative weights,
1. Let’s say the negative-weight edge is (u,v). First, remove the edge and run Dijkstra from s. Then, check if ds[u] + w(u, v) < ds[v]. If not, then we’re done because it implies that the shortest path tree does not use this negative edge.
If yes, then run Dijkstra from v, with the negative-weight edge still removed. Let the distances obtained by that be dv[·]. Then, for any node t, its shortest distance from s will be min(ds[t],ds[u]+ w(u, v) + dv [t]).. This works because the shortest path to any node is either that where you use the negative edge or you do not. If you do use the negative edge, then the shortest path consists of the shortest path to u, using (u, v) and then the shortest path from v to t.
2. The claim is that running Dijkstra’s as usual will work. Let’s compare the execution of Dijkstra’s algorithm on G to the execution on a graph G′ where we’ve added the same amount m to the weights of all edges coming out of the source so as to make them non-negative.
On the one hand, since all edge weights in G′ are non-negative, we know that Dijkstra’s algorithm will find the correct shortest-path distances in G′.
On the other hand, observe that the flow of Dijkstra’s algorithm is controlled by two things: the comparisons dist[w] > dist[v] + length[v, w], and the element with lowest priority in the heap.
Observe that at any step in Dijkstra’s algorithm, in the comparison dist[w] > dist[v] + length[v, w] we’re actually comparing the lengths of two paths from s w. Whenever w ̸= s, both of these paths contain exactly one edge coming out of s. So the truth value of the comparison will be the same in G and G′ because the difference is m on both sides of the comparison. Moreover, once we pop s from the queue, the queue for G′ will be a copy of the queue for G, but with all priorities shifted up by m. This preserves the minimal element.
It follows that Dijkstra’s algorithm is the same on G and G′, up to the priorities of all vertices v ̸= s shifted by m. Thus, Dijkstra’s algorithm on G will find the shortest paths in G′. But the shortest paths in G′ to all v ̸= s are the same as those in G by an argument similar to the above: if we have a path p : s → v which is shortest in G′, this means that l′(p) ≤ l′(q) for any q : s → v, where l′ is distance calculated in G′, and l is distance calculated in G. But then, l(p) = l′(p) − m ≤ l′(q) − m = l(q) for all such q in G, hence p is a shortest path in G.
Finally, it remains to show that we find the right distance to s itself in G – which is clear because we assumed G has no negative cycles, so the true distance is 0, and this is what Dijkstra’s algorithm gives.
Exercise (Largest Submatrix of 1’s). You are given a matrix M with m rows and n columns consisting of only 0’s and 1’s. Give an efficient algorithm for find the maximum size square sub-matrix consisting of only 1’s.
We will solve this via dynamic programming:
• Definition: Let S[i,j] be the size of largest square of 1’s submatrix containing M[i,j] in the right- most and bottom-most corner. Note that if M[i,j] = 0, then S[i,j] = 0. The desired answer is maxi,j S[i, j].
• Recurrence: We can then copy the first row and column from M to S because at most it will be a square of size 1×1. This is equivalent to saying that if i = 1 or j = 1, then we have that S[i,j] = M[i,j]. For the recursive case, we can then fill S according to
min(S[i,j−1],S[i−1,j],S[i−1,j−1])+1 :M[i,j]=1 S[i,j] = 0 : M[i,j] = 0
It is pretty easy to see why this is correct after drawing an example. • Analysis: This will take O(mn) time and space.
Exercise (Minimum Bottleneck Spanning Tree). 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 maximum edge.
1. Show that any minimum spanning tree is necessarily a minimum bottle neck spanning tree
2. Give an example of a graph and a minimum bottle neck spanning tree that is not a minimum spanning
1. Assume that there is an MST T of a graph G. Let T′ be an MBST of G. Define b(T) and b(T′) to be the weight of the bottleneck edge in T and T′. Let e be the bottleneck edge of T. Consider the cut in the tree defined by e. By the cut property every other edge crossing the cut necessarily has weight at least that of e. Now look at the edges of T′ which cross the cut. By the above statement they must too all have weight at least that of c(e). But then if b(T) is the bottleneck cost of a tree T, b(T) = c(e). Thus, we know that b(T) ≤ the cost of any edge of T′ crossing the cut ≤ b(T′). Therefore, we have shown that b(T) ≤ b(T′). We also know that by definition of minimum bottle neck spanning tree that b(T ′) ≤ b(T ). Therefore, b(T ′) = b(T ) and T , a MST, is also an MBST.
≤ cost of any edge of T0 crossing the cut ≤ b(T0) : b(T) ≤ b(T0), and so since T0 has minimum bottleneck cost among trees (b(T0)) ≤ b(T )), b(T ) = b(T0) − T is an MBST.
2. Consider the following graph:
[scale=0.15] every node+=[inner sep=0pt] [black] (25.1,-17.8) circle (3); (25.1,-17.8) node a; [black] (52,-17.8) circle (3); (52,-17.8) node b; [black] (25.1,-40.4) circle (3); (25.1,-40.4) node d; [black] (52,-40.4) circle (3); (52,-40.4) node c; [black] (25.1,-20.8) – (25.1,-37.4); (24.6,-29.1) node [left] 2; [black] (28.1,-17.8) – (49,-17.8); (38.55,-18.3) node [below] 1; [black] (52,-20.8) – (52,-37.4); (51.5,-29.1) node [left] 2; [black] (49,-40.4) – (28.1,-40.4); (38.55,-39.9) node [above] 1;
Notice that the minimum spanning tree has weight 4 and has bottle-neck edge 2. However, d−a−b−c is a minimum bottle neck spanning tree because it has heaviest edge 2 and it is impossible to find any other spanning trees that have a lighter bottle neck edge.
Exercise (Building Hospitals). Suppose we are given a set of cities represented by points in the plane, P = {p1, . . . , pn}. We will choose k of these cities in which to build a hospital. We want to minimize the maximum distance that you have to drive to get to a hospital from any of the cities pi. That is, for any subset S ⊂ P, we define the cost of S to be
max dist(pi, S) where dist(pi, S) = min dist(pi, s). 1≤i≤n s∈S
This problem is known to be NP-hard, but we will find a 2-approximation. The basic idea: Start with one hospital in some arbitrary location. Calculate distances from all other cities — find the “bottleneck city,” and add a hospital there. Now update distances and repeat.
1. Give a precise description of this algorithm, and prove that it runs in time O(nk). 2. Prove that this is a 2-approximation.
Hint: Any two points within a circle of radius r are at most 2r away from each other.
1. For each city pi we let di denote its distance from the set of hospitals so far. Suppose we have just added the j-th hospital sj. To decide where to add the next hospital, we look at O(n) cities, updating the distances di by taking di = min(di, dist(pi, sj )). The bottleneck city is the one with maximal di
after this update, so we set sj+1 to be this city. We continue until k hospitals have been added, and we do a last update of the distances to find the final cost of our choice of S.
2. Consider the optimal choice of S ∗ = {s1 , . . . , sk }, and let Dj denote the disc with center sj and radius r∗, where r∗ denotes the cost of S∗. Now consider the S that we obtained from our approximation algorithm, which has cost r. If every Dj contains some point of S then we are done, because then every pi will be within distance 2r∗ of S. Suppose not: By the pigeonhole principle, two points s,t ∈ S must be contained in a single disc D = Dj. But by the way we constructed S, dist(s,t) ≥ r. We also have dist(s, t) ≤ 2r∗, so again r ≤ 2r∗ which concludes the proof.
Exercise (MST Bound). Suppose that we are given a graph with the following guarantee: for any two
disjoint sets S,T of vertices, there exists some edge between a vertex in S and one in T with length no
more than 1 . Find a bound on the size of the minimum spanning tree for this graph, in terms of max(|S|,|T |)
the number of vertices. Hint: Think Prim’s algorithm. You may find the following approximation useful:
Xn 1i≈ln(n) i=1
We create a tree similarly to that of Prim’s algorithm. In particular, start with sets of vertices of size 1 and n − 1; we know that there exists an edge of size no more than 1/(n − 1) from the single vertex to one of the other vertices. Add that edge. Now, we have sets of size 2 (connected) and n − 2 (disconnected), and can find an edge of size no more than 1/(n − 2) from one of the two vertices into a disconnected one. We can continue this process until we have one connected set of size ⌈n/2⌉ (the tree so far) and one entirely disconnected set of ⌊n/2⌋ vertices.
This is the point at which we switch from using the bound 1/(#disconnected vertices) for a bound on the edge length to 1/(#vertices in tree so far).
Now there is some disconnected vertex of distance at most 1/⌈n/2⌉ from our tree so far, then one of 1/⌈n/2 + 1⌉, etc. Finishing out this process gives a total edge length of
n−1 1 n−11 ⌈n2−1⌉1 n
2 X ≤2X −2 X ≈2ln(n−1)−2ln ⌈ −1⌉ ≈2ln2
i=⌈n/2⌉ i i=1 i i=1 i 2 This does not depend on n!
Exercise (Well-Nested Brackets). There are four types of brackets: (, ), <, and >. We define what it means for a string made up of these four characters to be well-nested in the following way:
1. The empty string is well-nested.
2. If A is well-nested, then so are and (A).
3. If S, T are both well-nested, then so is their concatenation ST.
For example, (), <>, (()), (<>), ()<>, and ()<()> are all well-nested. Meanwhile, (, <, ), )(, (<)>, and (<(> are not well-nested.
Programming Help
Devise an algorithm that takes as input a string s of length n made up of these four types of characters. The output should be the length of the shortest well-nested string that contains s as a subsequence (not sub-string). For example, if (<(> is the input, then the answer is 6; a shortest string containing s as a subsequence is ()<()>.
This problem can be solved with dynamic programming.
• Definition: Let s[i,j] be the substring of s from the ith to the j1st character, inclusive. Then, we define the sub problem f(i, j) to be the length of the shortest well-nested string containing s[i, j]. Our desired output is f(0, n).
• Recurrence: The base case is where the length of the substring is 1 or 0. If i = j, the substring has length 0, and f(i,j) = 0.
If i = j + 1, the substring has length 1, and we must add one character to close it, so f(i,j) = 2. To compute f(i,j) recursively, we first note that if s[i] is a closing bracket, ) or ¿, we must insert an matching opening bracket to achieve well-nestedness. Otherwise, the opening bracket s[i] must be matched by some closing bracket s[k] where i < k < j, or by adding a closing bracket. Let the matching closing bracket of of s[i] be denoted by s[i]′
The analysis above give the following recurrence:
(2 + f(i + 1, j) s[i] =), >
2+min(f(i+1,j),mins[k]=s[i]′(f(i+1,k)+f(k+1,j))) s[i]=(,<
• Analysis The runtime is O(n3) since there are O(n2) values to calculate, each of which takes O(n) time (from scanning the substring for the matching bracket of s[i]). The space of the algorithm is O(n2) since the array is n + 1 by n + 1.
Exercise (Hopfield Network). A Hopfield Network is an undirected graph where each node v is assigned a state s(v) ∈ {−1, 1}. Every edge (i, j) has an integer weight wij .
For a given configuration of node state assignments, we call an edge (u, v) good if w(u, v)s(u)s(v) < 0 and bad otherwise. A node u is satisfied if the sum of the weights of the good edges incident to u is larger than the sum of the weights of the bad edges incident to u, i.e.
w(u, v)s(u)s(v) ≤ 0 v:(u,v)∈E
A configuration is stable if all nodes are satisfied. In this problem, we will use local search to find a stable configuration. Let our cost function f be defined as follows:
f(V,E) = X w(u,v)s(u)s(v) (u,v)∈E
Let our neighbor function be simply: pick a vertex u and flip s(u) to −s(u).
Explain why this algorithm will always succeed in finding a stable configuration. Remember that there are
two parts to succeeding: you must terminate and must be correct.
程序代写 CS代考 加微信: cstutorcs
Note: if we’re actually trying to minimize f rather than just find a stable configuration, this approach fails to yield the minimum because it gets stuck at local optima. As an example, take the line graph: A–B–C–DwherethecurrentvaluesareA,B=1andC,D=−1. AB=5,BC=3,CD=5. Itwould be best if every node of this graph had the same value, but hill climbing can’t get there from the current configuration.
There exists at least one local minimum: a state that cannot be improved by flipping a node. Local minima of this cost function are exactly stable states. Consider the change in the cost function from flipping a node. If we flip s(v) from 1 to -1 then the change is:
−2 X w(u, v)s(u) (u,v)∈E
(where v is now fixed). If we flip it from -1 to 1 then the change is 2 X w(u, v)s(u)
In order for this change to have improved our cost function, v must have been in an unstable state when we flipped it.
Exercise (NP-Completeness). Show that the following 2 problems are NP-complete:
1. Subgraph isomorphism: Consider graphs G = (V,E), H = (V2,E2). Does G contain a subgraph
(V1, E1) which is isomorphic to H?
(An isomorphism of graphs (V1,E1) and (V2,E2) is a 1-1 function f : V1 → V2 such that the map
(u, v) 7→ (f(u), f(v)) is a 1-1 function E1 → E2.)
2. 4-Exact-cover: Given a finite set X of size 4q and a collection C of 4-element subsets of X, does C
contain an exact cover (i.e. a partition) of X?
You may use without proof that 3-exact-cover is NP-complete.
1. This is clearly in NP because our certificate is the subgraph itself. To show this is NP-complete, we reduce from clique: Asking whether there is a clique of size ≥ K is equivalent to asking whether there is a subgraph isomorphic to CK, the complete graph on K vertices.
2. Expand X to X′ by adding the elements e1,...,eq. For each 3-element set S ∈ C, define 4-element sets S(i) = S ∪ {ei} for 1 ≤ i ≤ q. Solving 4-exact-cover for X′ with
C′ ={S(i):S ∈C,1≤i≤q} will give the result for 3-exact-cover.
Exercise (Two Player Game). Consider the following zero-sum game, where the entries denote the payoffs of the row player:
2 −4 3 1 3 −3
Write the column player’s minimization as an LP. Then, write the dual LP, which is the row player’s maximization problem.
Let p be the payoff of the row player. The column player wishes to minimize p with to a strategy of (y1, y2, y3) (probabilities of picking column 1, 2, 3 respectively). Recall that for any given strategy of one player, the best response of the other player will occur when the other player plays one of their pure strategies. That’s why in the constraints, we only consider the opponent playing pure strategies.
Thus, the column player’s LP is
p≥2y1 −4y2 +3y3 p≥y1 +3y2 −3y2
y1 + y2 + y3 = 1, y1,y2,y3 ≥0.
On the other hand, let the row player’s strategy be (x1,x2). Then, the dual LP is
p ≤ 2x1 + x2 p≤−4x1 +3x2 p ≤ 3x1 − 3x2
x1 + x2 = 1 x1,x2 ≥0.
Exercise (3-SAT Random Walk). In lecture, we saw a random walk algorithm for 2-SAT that ran in O(n2) time. In this problem, we will attempt to extend that algorithm for 3-SAT.
1. Consider a random walk on the vertices {0, 1, 2, n − 1, n} where we start at vertex 1. At each step, we go up with probability 13 and down with probability 23. When we are at 0, we will always move to 1. Let Ti be