Homework
The goal of the homework is for you to think deeply about the material. This thinking process is where most of your learning occurs.
It is not harmful to work with others, provided that doing so does not short-circuit your deep thinking process: When others tell you the answer, they steal your learning opportunity. My advice: Only ask when you are stuck. Never ask "What is the answer to this problem?" Avoid asking "How do you do this problem?" Try to formulate your question so that the answer only gets you unstuck. It does not give away the whole problem.
Similarly, if asked to answer a question about a problem, try to answer with minimal extra information about solving the problem. Although it may feel good to show the asker how much you know, it is in the asker's interest that you refrain: It is a charitable act to not say too much.
Submit only those problems that are noted in bold. Beyond providing a correct solution, endeavor to be clear and precise. Achieving a proof that is clear, precise, and correct is similar to achieving a program that is clear, precise, and correct: Some features of the solution that are necessary may seem tedious. We accept that about computer programs. Please apply the same standard to your proofs. Take satisfaction in the process of increasing the precision or clarity of your proof. Like a beautiful poem, musical composition, or computer program, a beautiful proof requires work, and rarely is the first thing we write down. An explanation, computer program, or proof that is clear, precise, correct, and surprisingly succinct is elegant.
Submission process
Create a Sharelatex project that will be the repository of all your homework submissions. The project should be private, except that you must share it with Pete. Here is a template.
| Section # | Section Name | Problems |
|---|---|---|
| 1.1 | Propositional Logic | 24, 26, 34, 40, 42, 44, and 50. |
| 1.2 | Applications of Propositional Logic | 12, 14, 30, 36, 38, 40, and 42. |
| 1.3 | Propositional Equivalences | 42, 44, 52, 54, 62(c), 64, and 66. |
| 1.4 | Predicates and Quantifiers | 36, 42, 54, 58, 60, and 62. |
| 1.5 | Nested Quantifiers | 38, 40, 42, 44, 50, and 52. |
| 1.6 | Rules of Inference | 16, 20, 28, 30, 32, and 34. |
| 1.7 | Introduction to Proofs | 18, 24, 26, 30, 38, and 42. |
| 1.8 | Proof Methods & Strategy | 24, 36, 38, 42, 44, and 46. |
| 2.1 | Sets | 24, 36, 40, 42, 44, 46, and 47. |
| 2.2 | Set Operations | 18(e), 40, 42, 50, 58, 60, and 62. |
| 2.3 | Functions | 44, 56, 60, 68 (note 1 below), 70, and 72. |
| 3.1 | Algorithms | 56, 58, 60, 62, and 64 |
| 3.2 | The Growth of Functions | 48, 52, and 54. |
| 3.3 | Complexity of Algorithms | 36, 38, 40, 42, 44, and 46 |
| 4.1 | Divisibility & Modular Arithmetic | 36, 38, 40, 42, 44, and 46. |
| 5.1 | Mathematical Induction | 60, 62, 64, 70, 74, 78. |
| 5.2 | Strong Induction & Well-Ordering | 12, 26, 28, 34, and 42. |
| 5.3 | Recursive Definitions & Structural Induction | 26, 32, 44, 46, 62, and 64. |
| 5.4 | Recursive Algorithms | 14, 24, 26, 28, and 42. |
| 9.1 | Relations & Their Properties | 40, 42, 50, 54, and 56. |
| 9.3 | Representing Relations | 12, 14, 30, 32, 34, and 36. |
| 9.5 | Equivalence Relations | 46, 54, 56, 58, 62, and 66. |
| 9.6 | Partial Orderings | 42, 48, 50, 52, 56, and 60. |
| 6.1 | The Basics of Counting | 62, 64, 66, 68, 70, 72, and 74. |
| 6.2 | The Pigeonhole Principle | 34, 36, 38, 40, 42, and 46. |
| 6.3 | Permutations & Combinations | 32, 34, 36, 38, 42, and 44. |
| 6.4 | Binomial Coefficients | 22, 26, 28, 32, 36, and 38. |
| 6.5 | Generalized Permutations & Combinations | 28, 34, 48, 58, 60, and 63. |
| 8.1 | Applications of Recurrence Relations | 26, 28, 32, 50, 52, and 56. |
| 8.3 | Divide-&-Conquer Algorithms & Recurrence Relations | 18, 24, 26, 30, 32, and 36. |
| 8.5 | Inclusion-Exclusion | 12, 14, 16, 18, 20, and 22. |
Exercise notes
- There is a typographical error in exercise 68, part f: The 2nd term in the definition of f(x) should be the ceiling of x/2.
- Unit move: When beside an open position, a peg may move 1 unit to occupy that position (provided it is in the required direction).
- Jump move: If a peg of one color is in front of a peg of the other color that is followed by an open position (in the required direction), a peg may jump 2 units to the open position (the jumped peg is not removed).
- Play this game for n = 3 and n = 4.
- Show that, in general, n2 + 2n moves are required to complete the game.
Challenge problems
Basics of Counting
The White-Blue Peg Game
On the real line, place n white pegs at positions 1, 2, ..., n and n blue pegs at positions -1, -2, ..., -n (0 is open). Whites move only to the left, blues to the right. The following moves are possible:
By a sequence of these 2 types of moves (not necessarrily alternating between white and blue pegs), one seeks to interchange the positions of the white and blue pegs.