1. 3.1.2 21 2. 3.1.18 use the fact that if c1 and c2 are centers, and b1 and b2 are leaves that witness for the respective longest paths, and c1->b1 and c2->b2 are the same lengths, then c2 must lie on c1->b1, and visa versa. Then a third center must also fall along the same line, and the center in the middle would be better than the others. 3. 3.1.24 n cans = n entrants. One can used per game. And one can left over at the end of the final match. 4. 3.1.26 L= 5**6, I = (5**6-1)/4, n-1 = num of edges = num of stamps = m*I = 5*(5**6-1)/4. Multiply this by 34. 5. 3.1.28 (a) 20 coins require 3 weighings; (b) base: 3 coins, 1 weighing; induction step: divide into 3 equal groups. One weighing identifies which group has the light coin, and by induction that group requires n-1 weighings. 6. 3.1.30 no picture.. 7. 3.2.6 Need to show that such a set of vertices must be connected (and thus will be a spanning tree). If not connected, then look at connected components. Each of these must be a spanning tree, and thus each has k-1 edges in a component with k vertices. But then there are n-j edges altogether, where j is the number of components. But j is 1 by assumption, and so the original set of edges must be a spanning tree. 8. 3.2 - 16-a 800-503-530-233-251-701-710-413-440

-- RobbieMoll - 16 Oct 2006

Edit | Attach | Print version | History: r1 | Backlinks | Raw View | Raw edit | More topic actions

Topic revision: r1 - 2006-10-16 - RobbieMoll

Copyright © 2008-2019 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.

Ideas, requests, problems regarding UMass CS EdLab? Send feedback

Ideas, requests, problems regarding UMass CS EdLab? Send feedback