# NB Algorithms: Final Exam Key

*Bart Massey* 2018-03-24

The parity vector of an array is an indication of whether elements are odd or even. Let's define the parity vector of an array of positive integers by this algorithm:

`parity_step(a, start, end): if end - start = 0 return [] if end - start = 1 if a[start] is odd return [1] else return [0] m ← start + (end - start) div 2 left ← parity_step(a, start, m) right ← parity_step(a, m, end) result ← concatenate left and right return result parity_vector(a): return parity_step(a, 0, |a|)`

For example, the output on an input of [1,13,7,12] would be [1,1,1,0].

(a) Argue that parity_vector terminates on all valid inputs.

*Base Case: terminates when length of input is 0 or 1.*

*Recursive Case: Always recurses on a smaller vector.*(b) What is the running time of parity_vector as a function of |a| (the length of

*a*)?*Assuming concatenation is O(1) (as I did) then the parity is computed exactly once on each element of the array, so O(n). Assuming it is O(n), then O(n lg n).*(c) Give a simple non-recursive algorithm for parity_vector with the same running time.

*This should work:*`p ← new array of size |a| for i in 0..|a|-1 if a[i] is odd p[i] ← 1 else p[i] ← 0 return p`

*Discussion: Most folks did fine on this.*The diameter d of an undirected weighted graph G is defined as follows: Let P(G) be the set of all least-weight paths between pairs of vertices in G. Then d(G) is the maximum-weight path in P(G). d(G) is thus the weight of the "heaviest lightest path" in G.

For example, this graph

`A--4--B | / | / 3 8 | / |/ C--8--D`

has diameter 15. The maximal least-weight path is between B and D.

(a) Give a formal description of the problem of finding the diameter of a graph.

`GRAPH DIAMETER Instance: A graph G=(V,E). An edge weight function w:E→N Find: The largest n for which there is a shortest path of weight n between some two vertices v,w in G.`

(b) Give high-level pseudocode for an algorithm for finding the diameter of a graph. Your algorithm should be polytime in the number of edges and vertices of the instance. Do

*not*write out the details of standard algorithms used in your solution.*Several possibilities here. Probably the easiest is to use all-pairs least-weight paths via Floyd-Warshall.*`G' ← Adjacency-matrix representation of directed version of G M ← Floyd-Warshall matrix of least path weights in G' return maximum entry in M`

(c) Argue the correctness of your algorithm.

*The maximum least-weight path is called for. Floyd-Warshall computes all possible least-weight paths. Its maximum entry is thus what is asked for.*(d) What is the worst-case asymptotic running time of your algorithm?

*O(|V|^2) for graph conversion (line 1). O(|V|^3) for Floyd-Warshall (line 2). O(|V|^2) for finding the maximum (line 3). So O(|V|^3) overall.**Discussion: This seemed to go OK for folks. Some used Djikstra's Algorithm repeatedly, which is fine. Most had a good formal problem description, with instance and question.*Here's an interesting problem from Sphere Online Judge http://www.spoj.com/problems/MST1/

`SHORTEST PATH TO ONE Given: A positive integer n Find: The length of a shortest path from n to 1. For a given n, there are up to 3 possible choices at each step: a) Subtract 1 from n b) If n is even, divide n by 2 c) If n is divisible by 3, divide n by 3`

For example, when n = 7, a shortest path is 7,6(a),2(c),1(b) and the length of this path is 4.

Here's some pseudocode for a solution algorithm.

`shortest-path-to-one(n): if n = 1 return 1 return 1 + minimum of shortest-path-to-one applied to each of the following that qualify: n - 1 n / 2 [if n is divisible by 2] n / 3 [if n is divisible by 3]`

(a) Explain why this algorithm appears to be O(3

^{n}).*Three choices need to be explored at each recursive step. At best, must take O(n) steps. So O(3*^{n}).(b) Give pseudocode for a tabular dynamic programming algorithm that runs in time O(n).

*Just like the Fibonacci example, but with the whole table needed…*`a ← new array of length n a[1] ← 1 for i from 2..n a[i] ← 1 + a[i-1] if 2 divides i a[i] <- min a[i], a[i / 2] + 1 if 3 divides i a[i] <- min a[i], a[i / 3] + 1 return a[n]`

(c) Explain why O(n) time is still considered "exponential time" in this case.

*The running time of an algorithm on a problem is usually considered as a function of the instance size of the problem. In this case, the instance is just the number n. This number is a number of |n| = lg n bits. Thus, the running time is O(2^|n|), which is exponential time.**Discussion: Only a few got (c) correct. Almost everyone struggled with (b). Some folks gave a memoized solution, which is ok. Many folks had bad details in their pseudocode which made it effectively wrong.*One of my former students, Bob Hypothetical, turned in the following proof of the NP-completeness of 2-SAT.

*For any given 2-SAT instance I, one can construct a 3-SAT instance I' as follows: Take each clause c[i] in I and repeat it. In the first copy, add some new variable v[i]. In the second copy, add not v[i].**For example, if clause 7 of the 2-SAT problem is*`(a or not b)`

*produce*`(a or not b or v[7]) and (a or not b or not v[7]).`

*It can be seen that I' is satisfiable if and only if I is satisfiable, so 2-SAT is NP complete.*Explain things that are wrong with this proof. Do not try to prove anything new.

*We know that 2-SAT is in polytime. The reduction goes in the wrong direction. Also, there is no proof given that 2-SAT is in NP.**Discussion: Most folks got the reduction direction. Only a couple noticed the missing "in NP" proof.*