UNM Computer Science

Home > Degrees > PhD Degrees > Comprehensive Examinations > Fall_97_theory > Theory

In This Section:

Suggested Reading List

Theory PhD Exam - UNM - Fall 1997

Fall 1997
Computer Science Department
University of New Mexico

The examination is in three parts. Each of the three parts has the same weight. You are to answer all three questions in Part A, all questions in Part B, and any two of the questions in Part C.

Part A

Do all three questions.

Recall that a Hamiltonian circuit for an undirected graph is a simple (i.e., never visiting any vertex more than once) cycle which passes through all vertices of the graph, while a Hamiltonian path is a simple path with the same property.
- Consider the family of undirected graphs defined by a (rectangular) grid, where each grid point is a vertex and grid edges are graph edges. For which values of p and q do such graphs admit a Hamiltonian circuit?
- Consider now the family of undirected graphs defined by n-dimensional (hyper)cubes, where each (hyper)cube vertex is a graph vertex and each (hyper)cube edge is a graph edge. For which n does the corresponding graph admit a Hamiltonian path between the extreme vertices (00... 0 and 11... 1)?
Consider the following two-person game. Four cards are placed face down on a table. Each card is inscribed with an arbitrary integer. The first player can turn over one, two, or three cards, and scores the value of the last card turned over; the second player turns over exactly one card and scores the value of that card. The player with the higher score wins. First assume that the four cards always have different values and solve the questions below. Then repeat for the general case.
- Suppose that the first player turns over two cards and the second card has a higher value than the first. Should the first player turn over a third card? Justify your answer.
- What is the optimal strategy for the first player?
- Is the game a fair game (probabilistically speaking; i.e., do both players have an equal chance of winning)?
Recall that a connected undirected graph is biconnected iff the removal of a single edge does not disconnect the graph.
- What is the minimum number of edges that must be added to a tree in order to produce a biconnected graph?
- Develop an algorithm which turns an arbitrary tree into such a minimum biconnected graph.

Part B

Attached is a column dated June 1992 from the Bulletin of the European Association for Theoretical Computer Science devoted to the question of relativization. Read the article, then answer all 7 questions below; keep each answer short!

What is an oracle in complexity theory?
Why are contradictory relativizations interesting?
What was revolutionary about the result?
Why is it easier to define a reasonable mode of oracle access for time complexity classes than for space complexity classes?
Why is the mode of access to an oracle important?
Subsequent authors have argued that the “Revisionist Tale” of pp. 148--150 is not convincing, because it relies entirely on the access mechanism---the result does not relativize because of the unfortunate definition of what a space-bounded machine can do with an oracle. Propose an alternate definition of how a space-bounded machine can access an oracle.
The authors argue that the key change caused by relativization is the destruction of local coherence; that may explain the result, but does it explain the two contradictory relativizations of the ¶ vs. question?

Part C

Do any two questions.

(Algorithms) Devise a polynomial-time algorithm to decide whether or not an arbitrary instance of 3-Satisfiability has a truth assignment that causes each clause (independently) to have either 1 or 3 literals set to true.
(Algorithms) You are given an array which stores the results of a tournament in which every one of the n players played against every other player. (There are no draws; diagonal values are left empty.) Design and analyze an algorithm that runs in time and orders the players in such a way that the ith player in the resulting ordering has defeated the i+1st, for each i, . (Note that the running time is less than the size of the input!)
(Parallel Algorithms) A tridiagonal matrix has non-zero elements only on the principal diagonal and on the two subdiagonals adjacent to it; formally, . Let A be an square tridiagonal matrix and y be an vector. Develop a PRAM algorithm to solve the linear system Ax=y in time and total work.
(Automata Theory) Let L be a nonempty regular language. Prove that L can be accepted by a deterministic finite automaton with a unique accepting state if and only if, whenever strings u, uv, and w belong to L, then so does string uvw.
(Complexity) Most -complete problems can be shown to be complete for under logspace reductions. Suppose that one could show that some -complete problem could not be logspace-complete for ; what would be the consequences?
(Complexity) Let be some complexity class and M any Turing machine. Define the language accepts x within the resource bounds of . We can show that L is -complete when is , but that L is undecidable when is . (You need not show that here.) Why can we not immediately conclude that and differ and thus that and differ and thus that ¶ and differ?
(Computability) Define a real number to be computable if there exists a total function f such that: (i) is the integer part of the number; and (ii) for n>0, is the nth decimal digit of the fractional part of the number.
- Are computable numbers closed under the standard arithmetic operations? (Prove or disprove.)
- Prove that all rational numbers are computable.
- Prove that e and are computable numbers.
- Describe a noncomputable number.
(Computability) Let be the set of functions that converge on the diagonal in at most t steps; that is, is a (proper) subset of the diagonal (halting) set K. Verify that is recursive but that the union of the s over all values of t is K itself and thus non-recursive. Conclude that, if S is an r.e. set, then the set need not be r.e.