CS3343, Spring 2012, Quiz 3, 24 April 2012
Your Name:
- In your text's algorithms for breadth-first and depth-first
search, each vertex at various stages had one of three
colors: white, gray, or black.
With one line of explanation
for each color, explain how the color is used by the algorithm
or what specifically the different colors indicate.
White:
Gray:
Black:
- The algorithm for breadth-first search manages to visit all
vertices near the starting vertex, before moving
further away. How is this managed? In other words, why doesn't
the algorithm just wander away from the starting vertex without
visiting all nearby vertices? (Short answer.)
- Consider the directed graph below:
Use the "Alternative Method" of carrying out a topological sort
given at the end of Recitation 10: "Another way to perform topological
sorting on a directed acyclic graph is to repeatedly find a vertex
of in-degree 0, output it, and remove it and all its outgoing
edges from the graph." For full credit, it is not enough to display
a topological sort, but you must show (more or less) that you are using the
method in quotation marks.
- Suppose you are finding log2(t) where t=13 as we
did in the first part of Recitation 11. Suppose you first want
to normalize t=13 into the interval from 1 to 2 inclusive.
What operation(s) would you perform on this value of t
to produce t' satifying 1 <= t' <= 2? After finding
log2(t'), what operation(s) would you perform
on the result to get the desired value log2(13).
(Just two very short answers are all you need here: what you do
to 13 to normalize, and what you do at the end to denormalize.)