CSC 477/677 Assignment 5

Due date: Tuesday, May 3, 2011, 4:00 PM.

Under Construction

1. Draw the transitive closure of the following directed graph.
   encapsulated postscript
   portable document format
2. Draw the transitive reduction of the following directed acyclic graph.
   encapsulated postscript
   portable document format
3. Which of the following problems are known to be NP-complete? Which are known to be polynomial?
   I urge you to make use of the world wide web to answer some of these.
   1. The 0-1 traveling salesman problem.
   2. The clique problem. Given a graph G and an integer k, does G have a subgraph of k nodes which is a clique?
   3. Primality. Given an n-digit integer, is it prime? (We input an integer as a string of digits.)
   4. The factoring problem. Given two positive integers a and b, where a has n digits, does there exist a factorization of a into two integers both of which are larger than b?
   5. Minimum spanning tree. Given a weighted graph G and a weight w, does G have a spanning tree of weight at most w?
   6. Limited degree minimum spanning tree. Given a weighted graph G, an integer d, and a weight w, does G have a spanning tree of weight at most w and degree at most d?
   7. Halting problem. Given a C++ program P of length n, does P halt regardless of the input data?
   8. Program grader's problem, Are two C++ programs P₁ and P₂ equivalent? (Two C++ programs are defined to be equivalent if they give the same outputs given the same inputs. For example, any two programs which read two integers, write the product, and then halt, are equivalent, regardless of which algorithms they use to multiply the two numbers.)
   9. Given a weighted directed graph G, nodes u and v, and a weight w, does there exist a path from u to v of weight no more than w?
4. In class Thursday, April 14, we learned the Karatsuba Algorithm for fast multiplication of integers. This algorithm takes O(n^(log₂3)) time to multiply two n digit integers. But there are still faster multiplication algorithms that are known. Give one.
5. Use Knuth's quadratic time algorithm to construct an optimal binary search tree for the list of frequences: 2,3,8,5,4,9,6,2,1.
   Handout in postscript
   Handout in portable document format
6. Use the Ford-Fulkerson algorithm to find a maximum flow from s to t in the following weighted directed graph.
   encapsulated postscript
   portable document format
7. Three schools, Harvard, Princeton, and Yale, have each received a number of applicants for a certain progam. Each school has ranked applicants it deems qualified (possibly not all applicants).
   Each applicant has also ranked the schools. The rankings can be seen here.
   Find a stable assignment of applicants to schools. (Not all students will be assigned.)
   The Gayle Shapley algorithm works for this problem.
8. How long is the longest common subsequence of the two binary strings 01001101110010100 and 001011100010100110110? Be sure to show your work, rather than giving a (hopefully) lucky guess.
9. It is well-known that no comparison based sorting algorithm can sort n items with fewer than log₂(n!) comparisons. For example, you cannot sort 4 items with only 4 comparisons, since log₂(4!) is greater than 4. Show how to sort 4 items with at most 5 comparisons.
10. What is the maximum height that a 2-3 tree with 1000 leaves could have?
    What is the minimum height that a 2-3 tree with 1000 leaves could have?
    I want exact answers.
11. What is the maximum number of nodes that an AVL tree of height nine could have?
    What is the manimum number of nodes that an AVL tree of height nine could have?
    I want exact answers.
12. Given an asymptotic solution to the following recurrence.
    F(n) = F(3/5 n) + F(4/5 n) + n
    I have never gone over any problem like this, but you can figure it out!
    Hint: Guess the answer, and see if you can prove it. If you fail, guess again.