NB Algorithms: Final Exam

Bart Massey 2018-03-14

This exam is due by noon Thursday 2018-03-22. You may take up to four hours to work on the exam, broken up however you wish. I strongly suggest that when you get stuck, you walk away and let the problem percolate, then come back: that time does not count against the four hours. Please use only your textbook and notes and the notes on the wiki.

Please submit your exam by email as a PDF (only) to myself bart@cs.pdx.edu. A subject line of "NB Algs Final W2018" would be really helpful. You may do the exam with pencil and paper and scan it to PDF if you are a really clear writer. Otherwise get PDF output from whatever tool you're using and send that.


  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.

    (b) What is the running time of parity_vector as a function of |a| (the length of a)?

    (c) Give a simple non-recursive algorithm for parity_vector with the same running time.

  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.

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

    (c) Argue the correctness of your algorithm.

    (d) What is the worst-case asymptotic running time of your algorithm?

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

    (b) Give pseudocode for a tabular dynamic programming algorithm that runs in time O(n).

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

  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.