|
Math 61, Lecture 2, Spring 2009 Homework Assignments:Please do the problems NEATLY and staple all homeworks! Late homework will not be accepted. Excessively messily written solutions will be counted as wrong. Sections given are from Discrete Source unless otherwise noted. Due Friday, April 3: Mathematical Induction: Review Exercise 3 -- when you find a formula, prove it by induction; Exercises 2, 3, 8, 13, 14, 22. Due Friday, April 10: Sets: Exercises 54, 66, 71, 72, 73. Functions: Exercises 3, 5, 26, 39. Sequences and Strings: Exercises 122, 125. Relations: Exercises 14, 36 (give a brief explanation in each case), 37, 45, 49, 51, 52. Due Friday, April 17: Equivalence Relations: Exercises 6, 16, 30. Matrices of Relations: Exercises 1, 14, 16, 21. Counting Methods: Basic Principles: Exercises 5, 21, 28, 29, 30, 35, 54, 56. Permutations and Combinations: Exercises 8, 11, 35, 45, 48, 60, 65. Due Friday, April 24: Generalized Permutations and Combinations: Exercises 3, 4, 15, 16, 19, 22, 23, 33, 36, 37. Binomial Coefficients and Combinatorial Identities: Exercises 3, 4, 5, 13, 15, 16. Due Friday, May 1: Pigeonhole Principle: Exercises 2, 3, 5, 6. Recurrence Relations: Exercises 2, 3, 9, 10, 11, 12, 19, 22, 23, 49. Solving Recurrence Relations: Exercises 2, 5, 6, 9, 12, 16, 17, 19, 34. Due Friday, May 8: Solving Recurrence Relations: Exercises 20, 22, 42, 43, 45, and these extra problems. Graph Theory: Introduction: Exercises 3, 12, 13, 15, 17, 18, 22, 25, 40, 41, 52. Paths and Cycles: Exercises 5, 11, 12, 14, 26, 30 (just say whether an Euler cycle exists and justify your answer; you do not need to exhibit an Euler cycle), 33 (same instructions as 30), 35, 36, 38, 41, 46. Due Friday, May 15: Hamiltonian Cycles and the Traveling Salesperson Problem: Exercises 2, 5, 7, 8, 9, 10, 11, 14. A Shortest-Path Algorithm: Exercise 5 (use Dijkstra's algorithm). Representations of Graphs: Exercises 3, 6, 15, 17, 20, 23. Isomorphisms of Graphs: Exercises 2, 3, 5, 8, 9, 20. (For Exercises 2, 3, 5, 8, 9, if the graphs are isomorphic, just give f, the bijection between the vertices; you do not need to write out g.) Due Friday, May 22: Planar Graphs: Exercises 2, 5, 6, 7, 11, 12. Trees: Introduction: Exercises 2, 3, 5, 6, 10, 25, 32. Due Friday, May 29: Terminology and Characterizations of Trees: Exercises 18, 19, 20, 23, 24, 25, 26. Spanning Trees: Exercises 2, 8. Minimal Spanning Trees: Exercises 2, 3, 11, 15. Due Friday, June 5: Binary Trees: Exercises 2, 4, 5, 6, 7. Recurrence Relations: Applications to the Analysis of Algorithms: Exercises 8, 10, 11, 12, 13, 14. Decision Trees and the Minimum Time for Sorting: Exercises 1, 2, 10 (you don't need to give an algorithm; just answer the first part of the question), 14, 16. Isomorphisms of Trees: Exercises 2, 3, 8, 12, 16, 18.
|