Introduction to the Design and Analysis of Algorithms
Textbook.
 CS 3343/3341
 Analysis of Algorithms
 Fall 2012
 Recitation 10
 Subset Sum, Etc.
    Week 10: Oct 30-Nov 01
 Due (on time): 2012-11-05  23:59:59
 Due (late):        2012-11-09  23:59:59

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

In-class Problems: The first problems will be made accessible during the Recitation hour: Rec 10, In-Class Problems (password protected, use "CS3343" without quotes for "User Name" and password from class just before the recitation).

Remaining Problems:

  1. Refer to the weird topic Fast Multiply.

    1. Verify that the product

           a ∙ b = (a1∙10 + a0) ∙ (b1∙10 + b0)

      is correctly calculated by the following:

           (100 + 10)a1∙b1 + 10(a1 - a0)∙(b0 - b1) + (10+1)a0∙b0,

      where a0, a1, b0, and b1 are single-digit numbers.

    2. Use the method on the link above to do a "mental calculation" (this is the technique shown in the third displayed formula at that link). You should calculate the product 54524139 * 98646231 = 5378600810870109. Of course you don't have to do this in your head, but pretend you only have a low-tech calculator that can display no more than 10 digits. You should use your "calculator" to multiply 4-digit numbers by 4-digit numbers, but don't mulitply anthing bigger. Additions could be done by hand. There will be one 16-digit number to add to other numbers. Show all the work, as with the example at the end of the link above.

  2. Consider the weird topic Hamiltonian Paths.

    1. Give the seven possible simple paths from ME to NY in the graph. Which of these 7 is or are the start of a Hamiltonian path from ME to some other node? How would this fact help if you were searching for all Hamiltonian paths in this graph from ME to some other node?

    2. The above page states that there are 68,656,026 Hamiltonian paths from ME to some other node in the graph. Normally if we add nodes and edges to a graph like this, the number of possible paths increases dramatically. Even a single node can multiply the number of possible paths. Knuth studies a 49-node graph along with this one, which has one more node (city) called DC for "District of Columbia" and two more undirected edges (meaning that you can go either way on them, just as with the other edges), from MD to DC and from VA to DC. When I first investigated this enlarged graph, I thought there would be many more Hamiltonian paths on it than on the 48-node version. I was surprised to discover that there are far fewer Hamiltonian paths on the larger graph, perhaps half as many. (At first I thought there must be a bug in my program.) Can you give a simple explanation for this? (There is a simple explanation. If you figure it out, please don't tell others in the class.)

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