UNB/ CS/ David Bremner/ teaching/ cs3383/ Final Exam

Recurrences

example 1

Let T (n) = T (n/4) + T (n/2) + Θ(n). Prove by substitution that

T (n) ∈ O(n)

example 2

Let T(n) = T(n/6) + T(4n/5) + Θ(n). Show that T(n) ∈ O(n)

Divide and Conquer

Binary Multiplication

In the following, suppose x and y are two n bit numbers, where n = 2ᵏ for some integer k. The function shiftl(a, b) returns 2ᵇ × a, and takes Θ(log b) time. The function plus(a, b) returns a + b and takes Θ(log a + log b) time (i.e. plus(x, y) would take Θ(n) time). Analyze the complexity of the following algorithm.

function Mult(x, y)
    Let n = bits(x) = bits(y)
    if n=1 return x*y
    Let xL (yL ) be the left n/2 bits of x (y).
    Let xR (yR) be the right n/2 bits of x (y).
    z ← shiftl(Mult(xL , yL ), n)
    z ← plus(z, shiftl(plus(Mult(xL , yR ), Mult(xR , yL )), n/2 ))
    z ← plus(z, Mult(xR , yR ))
    return z
end function

Randomized Algorithms

Recursive example 1

function foo(n)
   if n ≤ 1
        return
   else
        i = random(n)
        foo(i)
   end
end

Suppose that random(n) takes Θ(1) time to return a random integer between 1 and n inclusive.

Recursive example II: Loopy

Suppose that random(n) returns a random integer between 1 and n inclusive. What is the expected running time of Loopy as a function of n and a. You may assume random(n) takes Θ(1) time, and that 1 ≤ a < n/2.

function Loopy(n, a, j)
    r ← random(n)
    if (r ≤ a or r > n − a) then
        return Loopy(n, a, j + 1)
    else
        return j
    end if
end function

Randomized select

Consider the following randomized selection algorithm we studied in class. You may assume RandomPartition takes O(n)

  def RandSelect (A, p, q, i):
      if p == q:
          return A[p]
      r = RandPartition (A, p, q)
      k = r – p + 1
      if i == k:
          return A[r]
      if i < k:
          return RandSelect (A, p, r – 1, i )
      else
          return RandSelect (A, r + 1, q, i – k )

Let Xⱼ be the indicator variable defined by

  Xⱼ = 1    if j = k = r-p+1
       0    otherwise

Let n denote q-p+1. Let T(n) denote the (random) running time of this algorithm. Use your indicator variables to show that

E[T(n)] ≤ 1/n ∑_{j=1}ⁿ  E[max(T(j-1), T(n-j))] + O(n)

Minimum Spanning Tree

Local improvement

Let G = (V, E) be a connected, undirected graph with distinct edge weights. Let T be a spanning tree of G. Let e be an edge of G not in T.

Heaviest Edge

Kruskal's Algorithm

Prove during the execution of Kruskal's algorithm (below) that X always represents a forest, i.e. a graph without any cycles.

  for u ∈ V:
      makeset(u)
  X ← {}
  sort edges by weight
  for (u, v) ∈ E:
      if find(u)find(v):
          X ← X ∪ \{(u, v)\}
          union(u,v)

Topological Sort

Dynamic Programming

Longest Alternating subsequence

Given a sequence of nonzero integers, the longest alternating subsequence is the longest subsequence such that succesive elements of the subsequence change sign. For example given the sequence

  1, 7, −3, −4, 5, 7, −9,

a (non-unique) longest alternating subsequence is 7, −3, 5, −9. We interested here in computing the length of the longest alternating subsequence.

Give a dynamic programming algorithm for this problem

Longest Divisor Sequence

This is a midterm question based on the previous question (also very similar to Longest Increasing Subsequence from class).

A divisor sequence from a list (array) S, is a subsequence of not-necessarily consecutive elements from S such that each element of the subsequence after the first divides the previous on. Given the input S

  28, -3, 14, 7, −3, −4, 5, -7, −9, 1

The longest divisor sequence is 28, 14, 7, -7, 1

Edit Distance

Edit distance measures the number of single character inserts, deletes, and substitutions needed to transform one string into another. Each set of editing operations can be represented as an alignment, i.e. a table where all non-matching positions cost one operation. For example the following alignment costs 5.

exam__ination
_caffeination

University of Dynamic Programming

At the University of Dynamic Programming, you can take a course if you have taken any one of it's prerequisites (i.e. all of the prequisite lists are of the form "Course 1 or Course 2 or Course 3 ..."). Courses are numbered from 1 to n across the entire University, and each course is priced individually (according to a scheme based on popularity). You may assume there are no directed cycles in the prerequisite structure.

recursive function

Define a recursive function mincost(c) for the minimum cost of taking course c. You may assume the existence of a function prereqs(c) that returns a list of prerequisite courses for course c, and a function tuition(c) that returns the tuition for course c.

Hint: This should only be a few lines of pseudocode.

Memoization

Give a memoized implementation of mincost(c)

table driven algorithm

Give a non-memoized dynamic programming algorithm for mincost(c). Hint: Think about the ordering of subproblems.

Huffman Tree

The cost of a Huffman tree is defined as ∑ᵢ f_i d_i

where f_i is the frequency of symbol i (part of the input to the tree builder), and d_i is the depth of symbol i in the tree. Prove that in any minimum cost tree with the two symbols with smallest f_i are on the lowest level.

Union Find

Prove that if we only union root elements x and y with rank(x) == rank(y), the invariant ∀ z rank(z) ≤ height(z) is maintained

Multithreaded algorithms

Merge sort

function mergesort(A, lo, hi) // Sort A[lo...hi-1]
    if lo+1 < hi then  // at least two elements.
        mid =⌊(lo + hi) / 2⌋
        spawn mergesort(A, lo, mid)
        mergesort(A, mid, hi)
        sync
        parallel_merge(A, lo, mid, hi)
    end
end

Assume that parallel_merge takes Θ(k) work and has span Θ(log^2(k)) when called on k elements (i.e. hi-lo = k).

  1. Give a recurrence for the work T₁ of mergesort.
  2. Give a Θ bound for recurrence of part (1).
  3. Give a recurrence for the span T_∞ of mergesort.
  4. Give a big-O bound for the recurrence of part (3).

Counting non-zeros

Write a O(log n) span algorithm to count the non-zero elements in an array. Analyze the work and span of your algorithm.

Backtracking, SAT

Monotone SAT

Give a fast algorithm for solving monotone SAT problems, i.e. the input is CNF either without any negated variables, or with all negated variables.

Partition

The Partition problem is defined as follows. You are given a set S of positive integers, and you need to decide is there is a partition of S into two sets disjoint sets U,V such that ∑_{u ∈ U} u = ∑_{v∈ V} v.

def backtrack(P_0):
    Q = { P_0 }
    while ! empty(Q):
        P= Q.dequeue()
        for R ∈ expand(P):
            v = test(R)
            if (v == True ):  # SUCCESS
                return R
            elif (v == None):   # UNKNOWN
                Q.enqueue(R)
            elif (v == False):
                pass