Name: ____________________________________________________ Alpha: _____________________
Describe help received: _________________________________________________________________
Per-problem assessment:
• 5 (Perfect): Correct solution
• 4 (Good effort): Good effort, solution may or may not be correct.
• 2 (Poor effort): Some basic misunderstandings demonstrated that could have
been cleared up by reading the notes or giving a serious try.
• 0 (No effort): No progress towards a solution.
Problem 0 (assessment: self_______ final_______)
Consider the Longest Common Subsequence (LCS) from the notes.
We phrased the solving of this problem as a sequence of choices:
add&chop, chop-X and chop-Y.
I stated that no greedy choice works for this. Find
counterexamples for the following two greedy choice strategies:
-
Strategy 1:
choose add&chop if the last letters of X and Y are
equal, and otherwise chose to chop whichever of X and Y is
longer.
-
Strategy 2:
choose add&chop if the last letters of X and Y are
equal, and otherwise
- set S to the set of letters appearing in both X and Y
- set dX to the number of chop-X's needed to get to
where the last character of X is an element of S
- set dY to the number of chop-Y's needed to get to
where the last character of Y is an element of S
- if dX < dY choose chop-Y else choose chop-X
Problem 1 (assessment: self_______ final_______)
Go read the
Class 23 notes on
making Prim's greedy choice quickly. To the right is a graph
$G$, and below are all the data structures we use to track
Prim's algorithm, frozen at a moment in time part-way through
the algorithm. Array $P$ shows the current tree (which
contains vertices 2,4,5,6,7. The meanings of heap $H$ and
arrays $W$, $P'$, and $H_{pos}$ you'll have to get from reading
the notes. Your job is to go through one step of Prim's
algorithm: find the greedy choice (which vertex to add, and
which edge you're using), update $P$ to reflect what you've just
added to the "current spanning tree", and update $H$, $W$, $P'$
and $H_{pos}$ to reflect the new situation.
Note: clearly indicate all new values in the arrays/heap below!
| H: |  |