May 17, 1999|
Computer Science 226
This test is 16 questions for a total of 100 points, weighted as
indicated. Do all of your work on these pages (use the back for
scratch space), giving the answer in the space provided. Put your name
on every page (now), and write out and sign the Honor Code
pledge before turning in the test. You have three hours to complete
``I pledge my honor that I have not violated the Honor Code during
1. (15 points)
Match each of the given graph processing algorithms with one of its most
important features. Write the letter corresponding to your answer
in the blank to the left of the name of the algorithm.
In some cases, more than one answer might be argued, but
you must put only one letter per algorithm.
If you pick the best matches, you will use all the letters.
___ Kruskal A. finds strong components in linear time
___ Floyd B. general graph-searching scheme
___ Kosaraju C. optimal MST algorithm for dense graphs
___ Prim D. fundamental recursive method
___ Warshall E. for single-source shortest paths in unweighted graphs
___ DFS F. for reachability in dense digraphs
___ BFS G. reduces MST computation to sorting
___ PFS H. for all-pairs shortest paths in dense graphs
2. (5 points)
The following table gives the KMP state transitions
for the string 10100110, except for one
state transition, labelled X in the table. What should the value of X be?
0 1 2 3 4 5 6 7
0 | 0 2 0 4 5 0 2 8
1 | 1 1 3 1 X 6 7 1
3. (5 points)
It is easy to build a nondeterministic FSA corresponding to a regular
expression, and a basic theorem from automata theory says that we
can convert every nondeterministic FSA to a deterministic one. Why
do we not do so to implement RE pattern matching? Circle one of the
A. The deterministic FSA might have an exponential number of states.
B. There might exist a string that the deterministic FSA
recognizes but the nondeterministic FSA does not.
C. There might exist a string that the nondeterministic FSA
recognizes but the deterministic FSA does not.
D. The nondeterministic FSA might loop.
E. The proof of the theorem is not constructive (does not
tell us how to construct the deterministic FSA).
4. (5 points)
Fill in the following table with dictionary
entries that could be produced for a Huffman encoding
of the string accctggccccccg.
5. (5 points)
What is the last digit of the decimal representation
of 13 raised to the 1000th power?
6. (10 points)
Which of the following best describes
the asymptotic growth (within a constant factor) of
the length of the code produced by the two versions of Lempel-Ziv encoding
for a string of 8N characters made up of copies of the string
Give two answers, one for the pure version (LZ) and the other for
the dictionary-based version (LZW).
A. log N
B. (log N)*(log N)
C. square root of N
D. N * log N
7. (5 points)
Draw the subdivision of the plane that corresponds to inserting the following
points into an initially empty 2D tree, in the order given.
(10, 15) (2, 3) (5, 6) (8, 9)
8. (5 points)
What is the maximum number of line segments that can appear in the Voronoi
diagram of four points? Draw a small diagram to justify your answer.
9. (5 points)
Consider the digraph on eight nodes, labelled 0 through 7, with
the 13 directed edges
0-7 0-1 1-4 1-6 2-3 3-4 4-2 5-2 6-0 6-3 6-5 7-1 7-3 .
List the strongly
connected components of this digraph.
10. (5 points)
Match each of the given recurrences with the asymptotic
growth (to within a constant factor)
of the corresponding quantity, assuming in each case that
division by 2 is rounded down to the nearest integer and that the recurrence
is valid for N > 1 with T(0) = T(1) = 1.
Write the letter corresponding to your answer
in the blank to the left of the recurrence.
If you pick the best matches, you will use all the letters.
___ T(N) = 2 T (N/2) + 1 A. N log N
___ T(N) = T (N/2) + 1 B. linear
___ T(N) = 3 T (N/2) + N C. log N
___ T(N) = 4 T (N/2) + 1 D. quadratic
___ T(N) = 2 T (N/2) + N E. none of the above
11. (5 points)
Give the average node depth in the DFS and the BFS
trees for a complete graph of N nodes.
(Count the root as being at depth 0.)
12. (10 points)
Classify each of the following graph-processing problems as
easy or intractable, by writing E or I, respectively,
in the space provided.
___ Find the largest complete subgraph.
___ Find a set of edges that separates the graph.
___ Find a path that uses each vertex exactly once, or report that none exists.
___ Find a path that uses each edge exactly twice, or report that none exists.
___ Find the smallest set of edges that connects all the vertices.
___ Find the vertices in a digraph that are not on a directed cycle.
13. (5 points)
Consider the following undirected graph (edge weights are in parentheses)
0-1 (.4) 0-2 (.5) 0-3 (.9) 1-2 (.3) 2-3 (.2)
2-4 (.4) 3-5 (.8) 3-6 (.6) 4-6 (.5) 5-6 (.4)
Give the parent-link representation of the MST
computed by Prim's algorithm, using the standard adjacency-matrix
14. (5 points)
Give the parent-link representation of the shortest-paths tree
from node 0 that is computed by the PFS implementation of
Dijkstra's algorithm for the graph of the previous question,
using the standard adjacency-lists representation.
15. (5 points)
Consider the edges given in question 13 to be directed edges and
the weights to be capacities. What is the value of the
maximum flow from 0 to 6?
16. (10 points)
Match each of the given algorithm-analysis activities with one of its
most important goals. Write the letter corresponding to your answer
in the blank to the left of the name of the method. In some cases,
more than one answer might be argued, but you must put only one letter
per algorithm. You will use two of the letters twice.
___ empirical study A. know to stop seeking a better algorithm
___ linear programming B. cope with NP-completeness
___ NP-completeness proof C. guarantee performance
___ average-case analysis D. predict performance
___ optimality proof E. find a polynomial-time solution
___ worst-case analysis
___ approximation algorithm