CS315 (Prof. Szajda) Final Examination April 27, 2008

Name:______

This is an open book, open note exam: you may consult ONLY our class text, your your notes from this class, and the class lecture slides. Texts and notes related to other classes may be consulted as needed for those other classes (so if you get lucky and find a solution in one of them by accident, that’s OK – you just cannot go to those books with the intention of finding a solution to a problem on this exam). You may not consult any other resources or people regarding the contents of this exam during the completion of the exam. To be specific, the term “completion of exam” refers to the time from when you first examine the contents of any part of the exam until the moment that the exam has been turned in to me.

This exam is due (at my office, by email, or in my netfiles inbox) by 11:59:59pm on Sunday, May 4, 2008.

Please read and adhere to the following:

Your solutions should be succinct and precise.
If I cannot read a solution, or have the least bit of difficulty interpreting your handwriting, I will assume the solution to the problem in question is not correct and you will receive no credit for that problem!

3. When a problem asks you to provide an O(f(n)) complexity algorithm, part of your solution must be an explanation of why your algorithm meets the required complexity constraint!

Whether submitting and electronic copy or a hard copy of your test, be sure to include a copy of the test, and not just your solutions.

All binary trees on this exam are assumed to be proper. Also, so that all of our definitions are consistent with the text, the depth of a node v is recursively defined to be 0 if v is the root of a tree, and depth(parent) + 1 if v is not the root. The height of a tree is the maximum depth among the depths of all external nodes in the tree. Finally, the height of a node v is 0 if v is an external node, and one plus the maximum depth of a child of v if v is not an external node.

If a question asks you to prove something that is listed in the text as a theorem (for example, question 1), then you cannot use the theorem as proof for that question. You must instead prove the theorem!

As mentioned in class, it often helps to write a high level description of your algorithm before diving into the details. This helps make the details (and pseudocode, if present) easier to understand.

Question 1 is worth 12 points. The remaining questions are each worth 8 points.

Prove the following using the precise definition of the “Big-Oh” concept (i.e. tell me what c is as well as the value of n0).
If f(n) is a polynomial of degree d (i.e. ) then f(n) is O(nd).
nx is O(an) for any fixed x>0 and a > 1.

Give an example of a positive function f(n) such that f is neither O(n) nor (n).

Describe an algorithm that computes the kth smallest element of a set of n distinct integers in O(n + k log n) time.

Suppose you are given an array A containing n-1 unique integers in the range [0,n-1] in sorted order (smallest to largest). Describe an O(log n) time algorithm for finding the integer in the range [0,n-1] that is not in A.

Describe a divide-and-conquer algorithm, not based on the Fast Fourier Transform (which we did not cover), for multiplying two degree-n polynomials with integer coefficients in time . Hint: think Section 5.2.2.

Describe an algorithm that, given a weighted graph with positive weights, finds a spanning tree having the least possible product of its edge weights. Your algorithm must run in O(m log n) time, where as usual n is the number of vertices in the graph and m is the number of edges. You must justify why your algorithm produces the minimum product.

Give an O(n2 log n) time algorithm to find the maximum collinear subset of a given set of points in the Cartesian plane.

Define HYPER-COMMUNITY to be the problem that takes a collection of n web pages and an integer k, and determines if there are k web pages that all contain hyperlinks to each other. Show that HYPER-COMMUNITY is NP-complete.

Let T be a heap storing n keys. Give an efficient algorithm for reporting all the keys in T that are smaller than or equal to a given query key x (which is not necessarily in T). Your algorithm should run in O(k) time, where k is the number of keys reported.

Characterize the following recurrence relations using the Master method:
T(n) = 2T(n/2) + log n.
T(n) = 7T(n/3) + n.

Show that we can deterministically simulate in polynomial time any nondeterministic algorithm A that runs in polynomial time and makes at most O(log n) calls to the choose method, where n is the size of the input to A.

Suppose an oracle has given you a magic computer, C, that when given any Boolean formula B in CNF will tell you in one step whether B is satisfiable or not. Show how to use C to construct an actual assignment of satisfying Boolean values to the variables in any satisfiable formula B. Assuming that a formula B contains n variables, how many calls do you need to make to C in the worst case in order to do this?