Computer Science 477/677 Fall 1998
Final Exam 6:00 PM, Thursday, December 17, 1998, TBE B170




Name:


No books, notes, or scratch paper.  Use pen or pencil, any color.
Use the rest of this page and the backs of the pages for scratch paper.
If you need more scratch paper, it will be provided.

If the answer to any question is an asymptotic expression,
give the sharpest answer you can.  For example, if
Theta(n^2) is correct, then the answer O(n^2), although correct, will
only receive partial credit, because it gives less information.


The entire test is 200 points.




 Fill in the blanks. [5 points each]



_________ is the asymptotic time complexity of Prim's algorithm on a weighted
connected graph that has $n$ vertices and m edges.



_________ is one example of an  NP-complete problem.  (Don't describe the
problem, just name it: such as, ``The Halting Problem.'')


_________ is an algorithm technique where a set of subproblems is solved
leading up to the main problem, where the solution of each subproblem
depends on some subset of the previously solved subproblems.



[10 points each]
Solve each of the following recurrences.



f(n) = 2f(n/2)+O(n)


f(n) <= n^2 + f(n-1)


f(n) <= f(sqrt{n}) + 1




[10 points]
What method would you use to sort a list of several thousand
strings, where each string consists of exactly 80 symbols?  Assume
that the strings are in a text file, which is already ``partially
sorted'' (you are told by your supervisor) and the answer must be written
to a different textfile.  Also, assume that the memory of your computer
is very large.


[10 points each]
Consider the following pseudocode.   How much time does the code take
to execute?  Express all answers in terms of the input variable $n$.





input n
for i from 1 to n loop
for j from 1 to i loop
output "hello world"
end loop
end loop




input n
m = n
while m > 1 loop
m = m/2
for i from 1 to m loop
output "hello world"
end loop
end loop





input n
m = n
while m > 0 loop
output "hello world"
input k
if k > 0
  m = m-k
else
  m = m-1
end loop












[20 points]
Let G =

infty  infty  -2
4      1      5
3      infty  infty


Draw a picture of the weighted digraph G.


Compute the matrix G*



[15 points]
Write pseudocode for breadth first search of a directed graph.
Your code should contain one line that says ``visit x'' where x
is a node.



[20 points]
Explain, in detail,
how a to implement a priority queue such that each insert and
each deletemin takes O(log n) time, where n is the current number
of items in the priority queue.



[20 points]
Some English words are derived from French, some from Dutch, etc.
Suppose you are given a list of all English words that are derived
from the Greek language, such as "monochrome."
Let's say that the list has thousands of words.

Then, you are given a truly huge text file that contains literally millions
of words, and your job is to count the number of times each of the words
in your list of words derived from Greek occurs in the text file.

How would you do this efficiently?  Give the answer as a narrative, not
as pseudocode.





[20 points]
Write pseudocode for an algorithm, whose inputs are a directed graph G
and a node s, which outputs a list consisting of
all the nodes of G which are in the same strong component as s.
(Hint: Use depth first search.)







[20 points]
Explain, in words, pseudocode, or both, Dijkstra's algorithm for the
single source shortest path problem in a non-negatively weighted directed
graph.