Theory of Computation Breadth Exam Fall 1989

Directions: There are six problems. Answer any four.

1. Let Σ = {0, 1}. A language L in Σ^{∗} is called prefix-free if no proper prefix of a string in L is also in L. (If x is a string, a proper prefix of x is a string y with |y| < |x| for which x = yz for some z.)

a) Give an example of a language that is prefix-free and another language that is not.

b) Show that if L is prefix-free, then

∑_{x∈L} \frac{1}{2^{|x|}} ≤ 1.

c) Give an example to show that this can be false if L is not prefix-free.

2. The standard queue operations are:

• enqueue(Q, d): places d on queue Q,

• dequeue(Q, d): removes the least recently enqueued element of Q and returns it in d, and • empty(Q): a Boolean function that returns true when Q is empty and false otherwise.

Similarly, the standard stack operations are:

• push(S, d): places d on stack S,

• pop(S, d): removes the most recently pushed element of S and returns it in d, and

• empty(S): a Boolean function that returns true when S is empty and false otherwise.

Show how to implement the three queue operations above using two stacks so that, if any k queue operations are performed, the total number of stack operations is at most O(k). (The elements in the two stacks should make up the queue, and each queue operation should be “simulated” with appropriate stack operations.) Explain why your implementation achieves the desired performance.

3. Give examples of languages in each of the following classes:

a) P, the class of polynomial-time recognizable languages,

b) the class of NP-complete languages,

c) the class of languages in NP that are thought unlikely to be NP-complete,

d) the class of languages that are not in NP, but are recursive,

e) the class of recursively enumerable languages that are not recursive.

4. The maximum bipartite subgraph problem is: Given a graph G and an integer k, does G have a bipartite subgraph with at least k nodes?

Prove that this problem is NP-complete. (Hint: try reducing the maximum independent set problem to it in the following way. Given a graph G and an integer k, construct a new graph G′ with twice as many nodes as G, such that G′ has a bipartite subgraph of size 2k if and only if G has an independent set of size k.)

5. For this problem we will say that a tree is a binary tree if each node in the tree has 0, 1 or 2 children. For a tree T we will denote the number of nodes in T by #(T) and for a node d we will denote the subtree rooted at d by T_{d}.

Design an algorithm which takes as input a binary tree and returns as output a node d from the input tree such that the following holds when #(T) is sufficiently large:

\frac{1}{3}#(T) ≤ #(T_{d}) ≤ \frac{2}{3}#(T).

Your algorithm should run time in O(#(T)) and use as little additional storage as possible.

6. Let A(n) denote the average number of comparisons made by insertion sort for an input array of size n. It is not difficult to show that A(n) is O(n^{2}). However, the simplicity of the insertion sort algorithm also makes it possible to calculate fairly exactly the function A(n). For this problem you are to calculate it as exactly as you can. You may assume that the the input array does not contain duplicate entries and that all input permutations are equally likely.

Theory of Computation Depth Exam Fall 1989

Directions: There are six questions. Answer any three.

1. A Euclidean graph is a graph whose nodes have 2-dimensional Euclidean co-ordinates associated with them. A triangulation is a connected planar Euclidean graph whose straight-line edges divide the region of the plane enclosed by the graph into triangular regions. The greedy triangulation of a point set is the triangulation formed by successively adding the shortest possible edge to the already formed graph while maintaining the invariant that the graph is planar.

Show that the minimum spanning tree for a 2-dimensional Euclidean point set is always a subgraph of the greedy triangulation.

2. Let M be an n-by-n matrix with entries chosen from some field (for example, the real numbers). Let k be a positive integer. Using the ordinary algorithm for matrix multiplication, and repeated squaring, roughly how many arithmetic operations are needed to compute M^{k}?

Can you think of a way to compute M^{k} that will use fewer operations when k is large compared to n? How large must k be for your method to be an improvement on the algorithm described above?

[Hint: A matrix satisfies its own characteristic equation.]

3. An n-variable branching program is a directed acyclic graph, where all nodes are labeled with a variable from the set {x_{1},…, x_{n}}. The nodes are arranged in rows, with all edges from nodes at the ith row going to nodes at the (i + 1)st row. All nodes except those in the last row have outdegree two, with one edge from each node labeled 0 and one labeled 1. There is a special start node, which is in the first row, and a special accept node in the last row.

Any binary string w_{1} … w_{n} defines a path in the branching program from the start node in the following way. The first node in the path is the start node. If v is a node in the path that is labeled with the variable x_{k}, then the next node in the path is defined to be the node reachable from v on the edge labeled w_{k}, if v is not in the last row. Otherwise v is the last node on the path. (Note that the path might be longer than the string.)

This model is used to define language acceptance in the following way. A string w_{1} … w_{n} of length n is accepted by the branching program if and only if the associated path leads to the sink node. A family of branching programs B = {B_{0},…, B_{n},…} accepts a language L if and only if for every n, B_{n} is an n-variable branching program and accepts exactly the strings of L of length n.

Resources of a branching program are its size and its width. B has bounded width if there is a constant b such that for every n, the maximum number of nodes in any row of B_{n} is at most b. B has size f(n) if for every n, the number of nodes of B_{n} is at most f(n).

a) Show that each language in AC^{0} is accepted by a family of polynomial size, bounded width branching programs, where AC^{0} is the class of languages accepted by constant depth, unbounded fan-in circuits with and, or and not gates.

b) Show that any language over the alphabet {0, 1}^{∗} that is accepted by an s(n)-space bounded deterministic Turing machine is accepted by a family of branching programs with size 2^{O(s(n))}. Do you think the converse is true?

c) How would you define a nondeterministic branching program, to extend the result of part (b) to nondeterministic Turing machines?

4. Fortune proved that if \overline{SAT} is polynomially many-one reducible to a polynomially sparse set, then P = NP. His proof was based on an algorithm that did a depth-first search and pruning of the self-reduction trees of Boolean formulas. The fact that his algorithm used depth-first search turns out to be irrelevant. Your job is to prove that an algorithm based on breadth-first search also works. The algorithm is given below.

Preliminaries. Assume that \overline{SAT} is polynomially many-one reducible to a sparse set. Call the sparse set S and call the reduction f. Let p(n) be a polynomial bound on the number of elements of S that Boolean formulas of length less than or equal to n can be mapped to. I.e., p is a composition of the polynomial bound on the census of S and a polynomial stretching factor from the reduction.

Algorithm. To decide whether a Boolean formula b, of length n, is in SAT we perform a breadth-first search of its self-reduction tree. We search the tree level by level. As we search a level we build up a list of nodes whose children will be searched at the next level. For the algorithm to run in polynomial time we need to make sure that at each level this list contains only a polynomial number of nodes. To do so we keep a counter which is set to 0 at the beginning of the search over each level.

Searching a level: When a node x is visited we compute f(x). If f(x) is distinct from any other element in the range of f that we have found AT THIS LEVEL, then we increment the counter and add x’s children to the list of nodes to be visit at the next level. (If f(x) is not distinct, then we do nothing and thus x’s children will not be visited when we seach the next level.) If the counter value is greater than p(n), then we stop the entire algorithm and report that b is satisfiable, otherwise we consider the next node on the level. When a level is completed we go on to the next level, resetting the counter.

When/if the bottom level of the tree is reached we test to see whether any of the assignments corresponding to the leaves that remain are satisfying assignments. We report that b is satisfiable if we find a satisfying assignment among these assingments, and otherwise report that it b is unsatisfiable.

Your job. Prove that the above algorithm runs in polynomial time and correctly decides membership for SAT.

5. The maximum bipartite subgraph problem is: Given a graph G, find a bipartite subgraph of G with the maximum number of nodes. The associated decision problem is: Given a graph G and an integer k, does the maximum bipartite subgraph of G have at least k nodes?

a) Show that this decision problem is NP-complete (try reducing the maximum independent set problem to it).

For many NP-complete graph problems, if the class of graphs allowable as input is restricted, the problem is polynomial-time solvable. Suppose G is a class of graphs for which a maximum independent set can be found in polynomial time. The following algorithm attempts to use this fact to find the maximum bipartite subgraph for a graph in G. Given a graph G ∈ G as input, the algorithm simply finds a maximum independent set, deletes it, finds another maximum independent set in the remaining graph and outputs the bipartite subgraph induced by the two independent sets.

b) Show that this algorithm does not always work in general. That is, construct a graph G for which the algorithm outputs a bipartite subgraph which is not the maximum bipartite subgraph of G.

c) Show that this algorithm does however provide a good approximation to the maximum bipartite subgraph, in the following sense. Let R_{G} denote the ratio of the size of the the graph output by the algorithm on input G to the size of the maximum bipartite subgraph of G. Show that for all graphs G, R_{G} ≥ 1/2. Can you show that R_{G} ≥ 3/4 for all G?

6. Consider the following (not very efficient) strategy for card shuffling. Start with a deck of n cards in sorted order. Repeatedly apply the following operation: take the top card, and place it at a randomly chosen position in the deck. This is to be repeated until the original bottom card appears on top, at which time the insertion operation is done once more and the process stops.

a) Show that the expected number of operations until the process is completed is O(n log n). [Hint: consider the times at which the original bottom card changes position.]

b) Show that when the process is finished, all n! permutations of the original deck are equally likely.

c) Show that if the operation is applied a predetermined number of times, say k, then the deck is not placed into random order.