NB Algorithms: Final Exam Key

Bart Massey 2018-03-24

  1. 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.

  2. 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.

  3. 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(3n).

    Three choices need to be explored at each recursive step. At best, must take O(n) steps. So O(3n).

    (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.

  4. 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.