CS 3343
Analysis of Algorithms
Fall 2012 Recitation 12
BFS, Etc. Partial Answers
In-class Problems:
The first problems will be made accessible during the
Recitation hour:
Rec 12,
In-Class Problems
(password protected, use "CS3343" without quotes for "User Name" and
password from class just before the recitation). Answers:
Rec 12,
In-Class Answers.
Text, Exercise 22.2-3 on page 602. [Show that using a single
bit to store each vertex color suffices by arguing that
the BFS procedure would produce the same result if line
18 were removed.] The previous method from the book eliminated
the color BLACK, with only WHITE and GRAY remaining.
Another approach would use the fact that in the BFS
scan from the book on my page, it was hard to tell
the GRAY circles from the WHITE ones. But it turns out there
is a trivial way to tell the GRAY from WHITE even if all the
GRAY are turned to WHITE. For this version you would eliminate
line 5 and change line 13. You should use one or the other
of these approaches.
[Leaving off line 18 would clearly have no
effect on the algorithm because nothing in the algorithm
checks for the color BLACK. At the point of line 18,
u has color GRAY. It would really mess things up to set
u to color WHITE, by leaving it GRAY is fine.
For the second method, I think you can leave off line
5, not use GRAY at all, and replace line 13
with if v.color == WHITE and v.d == infinity ...]
Easy Instances of Subset Sum (SS).
We'll make use of problem 3 below later in the course (um,
we'd better hurry).
Recall that SS starts with an array
A =
{a0, a1, a2, ... , an-1}
of distinct positive integers,
and an integer t which may be the sum
of a subset of the ai. The optimization
problem is to discover a subset that sums to t, if one exists.
Consider A =
{1, 2, 4, 8 , ... , 2n-1}.
To make this concrete, take n = 6, so A =
{1, 2, 4, 8, 16, 32}. If t = 54,
what is the subset that adds up to t ?
Can you see a general strategy for finding the sum when A
has this form? [Just write n in binary and pick off the correct
powers of 2 from A. So 56=1011002, that is,
56=32+8+4, so we use these from A.]
Suppose each ai is greater than
the sum of all the mumbers of A that come before
ai. (Such a sequence of numbers is called
"super increasing".)
Is the sequence of numbers in part a above super increasing?
Again, to be specific, suppose
A = {171,196,457,1191,2410} and suppose t = 3797.
What is the subset in this case? Is the subset always
unique, if there is a subset? Can you see a general strategy
for finding the sum when A has this form? [Solving this uses a
simple greedy algorithm.]
[A greedy strategy chooses the
largest ai that is <= the current target t,
and then uses t' = t - ai as the new target.
Then repeat. In case the same ai is still
<= the current target, then there is no answer (since you can't
use an ai more than once. In case there
are no more ai and the current target is
still > 0, then again there is no answer.
An inductive argument will show that this algorithm
must work, but I haven't seen a way to make this argument simple.]
]
Revision date:2012-11-04.
(Please use ISO
8601, the International Standard.)
