Textbook.

CS 3343/3341  Analysis of Algorithms  Fall 2012  Recitation 10  Subset Sum, Etc.     Answers

Remaining Problems:

---

3. Refer to the weird topic Fast Multiply.
   1. Verify that the product

           a ∙ b = (a₁∙10 + a₀) ∙ (b₁∙10 + b₀)

      is correctly calculated by the following:

           (100 + 10)a₁∙b₁ + 10(a₁ - a₀)∙(b₀ - b₁) + (10+1)a₀∙b₀,

      where a₀, a₁, b₀, and b₁ are single-digit numbers.
      

      (100 + 10)a₁∙b₁ + 10(a₁ - a₀)∙(b₀ - b₁) + (10+1)a₀∙b₀ =
      100a₁∙b₁ + 10a₁∙b₁ + 10a₁∙b₀ + 10a₀∙b₁ - 10a₀∙b₀ - 10a₁∙b₁ + 10a₀∙b₀ + a₀∙b₀ =
      100a₁∙b₁ + 10a₁∙b₀ + 10a₀∙b₁ + a₀∙b₀ =
      (a₁∙10 + a₀) ∙ (b₁∙10 + b₀) =
      a ∙ b

   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.

      [Here is the example done using the new formula given in Part a above:

      To calculate: a*b = 54524139 * 98646231 = 5378600810870109 Break a and b apart: a = 10^4*a1 + a0, b = 10^4*b1 + b0 a1=5452, a0=4139, b1=9864, b0=6231 Then a*b = (10^8 + 10^4)*a1*b1 + 10^4*(a1-a0)*(b0-b1) + (10^4+1)*a0*b0 Here are the 3 4-digit multiplications: a1*b1 = 5452*9864 = 53778528 a0*b0 = 4139*6231 = 25790109 (a1-a0)*(b0-b1) = (5452-4139)*(6231-9864) = (1313)*(-3633) = -4770129 a*b = (10^8 + 10^4)*a1*b1 + 10^4*(a1-a0)*(b0-b1) + (10^4+1)*a0*b0= 10^8*53778528 + 10^4*53778528 + 10^4*(-4770129) + 10^4*25790109 + 25790109= 5377852800000000 + 537785280000 + -47701290000 + 257901090000 + 25790109 = 5378600810870109

      Here is the same problem done after the fashion of the example on the web page.

      8-digit numbers: c = a * b = c 54524139 * 98646231 = 5378600810870109 Break up a and b into 4-digit pieces: a = a1∙10e4 + a0 = a 54520000 + 4139 = 54524139 b = b1∙10e4 + b0 = b 98640000 + 6231 = 98646231 c = a * b = (a1∙10e4 + a0) * (b1∙10e4 + b0) = c2∙10e8 + c1∙10e4 + c0 c2 = a1 * b1 = c2 5452 * 9864 = 53778528 c0 = a0 * b0 = c0 4139 * 6231 = 25790109 Use the fancy method for c1: c1 = (a1 + a0) * (b1 + b0) - (c2 + c0) = c1 9591 * 16095 - 79568637 = 74798508 c = c2∙10e8 + c1∙10e4 + c0 = c 5377852800000000 + 747985080000 + 25790109 = 5378600810870109

      ]

   ---

4. 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? [This is pretty easy.]

   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.) [Consider what would happen if, instead of the new node DC and the new undirected edges {MD , DC} and {DC , VA}, we just put DC in as a new node between MD and DC. In other words, we replace the undirected edge {MD , VA} with edges {MD , DC} and {DC , VA}, so that there is no longer an edge {MD , VA}.
      
      Click box or here for full size image.

      DC only has two connections to the rest of the graph. Any HP must include DC and so it must use the two dark edges in the middle and on the right. In the middle, the original edge from VA to MD can never be part of an HP. In effect, with DC added, either as in the middle or at the right, the only HPs we get are those the same as in the original graph that used the edge from VA to MD. Look at the three HPs pictured at the link directly above. Only one of these (the middle one) would be possible if DC were added. The other two would be eliminated. Thus adding DC in either way above adds no new HPs at all, but leaves out an unknown number of them, perhaps roughly half. ]