Introduction to the Design and Analysis of Algorithms
Textbook.
 CS 3343
 Analysis of Algorithms
 Fall 2012
 Recitation 12 
 BFS, Etc. 
    Week 12: Nov 13-Nov 15
 Due (on time): 2012-11-19  23:59:59
 Due (late):        2012-11-23  23:59:59

Recitation 12 should be submitted following directions at: submissions with deadlines
  • 2012-11-19  23:59:59 (that's Mon, 19 Nov 2012, 11:59:59 pm) for full credit.
  • 2012-11-23  23:59:59 (that's Fri, 23 Nov 2012, 11:59:59 pm) for 75% credit.

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).

BFS with only two colors. See BFS
  1. 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.

Easy Instances of Subset Sum (SS). We'll make use of problem 3 below later in the course (um, we'd better hurry).

  1. 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.

    1. 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?

    2. 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.]

Revision date: 2012-11-04. (Please use ISO 8601, the International Standard.)