CMSC-203 Discrete Math: Schedule (spring 2001)

CMSC-203 Discrete Math Schedule (spring 2001--Section 0101, Alan Sherman)

This schedule is recommended by the course coordinator Dr. Alan T. Sherman as the common schedule for all sections of CMSC-203. Elements of this schedule include: (1) A strong emphasis on proofs, calculation, and counting. (2) Weekly written homework. (3) Two tests exams and a comprehensive final exam. (4) Specific topics as described in this schedule. In addition, Dr. Sherman recommends strongly that a significant amount of class time be devoted to active problem-solving by students in small groups.

Part I: Proofs (Chapters 1-5, plus additional material on program correctness)

Six weeks, including ten lectures and one test.

Week 1 (1/29-31). Sets, proofs, and first-prder predicate logic. DeMorgan's Law. Universal and existential quantifiers. Construction of the natural numbers, integers, rational numbers, real numbers, extended real numbers, and complex numbers. Proof by counterexample.
Week 2 (2/5-7). HW1 due. Direct proof (apply defs, case analysis, set equality, biconditional, circle of implications). Indirect proof and contraposition.
Week 3 (2/12-14). HW2 due. Induction (strong and weak forms).
Week 4 (2/19-21). HW3 due. More induction. Loop invariants and program correctness.
Week 5 (2/26-28). HW4 due. Epsilon-delta proofs and alternating quantifiers. Proofs with Big-Oh notation.
Week 6 (3/5-7). Begin calculation: Introduction to summations and difference equations.
Exam I on Chapters 1-5, with emphasis on proofs (counterexample, direct, indirect, contraposition, strong and weak induction, epsilon-delta). Includes proving simple programs correct.

Part II: Calculation (Chapters 7,8,10+, plus additional material on solving difference equations)

Five weeks, including nine lectures and one test.

Week 7 (3/12-14). HW5 due. Summations and recurrences. Calculating running times of iterative and recursive programs. Elementary summations (constant, arithmetic, geometric, harmonic, telescoping). Solving linear difference equations by characteristic equations, and iteration. Introduction to Maple.
spring break
Week 8 (3/26-28). HW6 due. Summations and recurrences. Characteristic equations: the cases of complex and multiple roots. Expressing periodic solutions in terms of the elementary functions sin and cos.
Week 9 (4/2-4). HW7 due. Functions and relations. Injections, surjections, bijections, permutations. Visual vs. combinatorial graphs. Equivalence and order relations.
Week 10 (4/9-11). HW8 due. More equation solving. The method of transformation. Solving linear Diophantine equations.
Week 11 (4/16-18). Begin counting: fundamental principles of counting and the urn model.
Exam II on Chapters 7,8,10, not including Sections 7.4 and 7.6, with emphasis on solving summations and recurrences. Includes solving second-order linear difference equations with multiple or complex roots, expressing periodic solutions using the elementary functions sin and cos. Includes counting running times of simple looping and recursive programs. Includes proving solutions to recurrences by induction

Part III: Counting (Chapter 6+, Sections 7.4 and 7.6 and 8.1, plus additional material on counting by inclusion/exclusion)

Four weeks, including eight lectures.

Week 12 (4/23-25). HW9 due. D'Alembert's counting method. Binomial Theorem and Pascal's Triangle. Counting by inclusion/exclusion (general case, including the "ghastly formula").
Week 13 (4/30-5/2). HW10 due. More inclusion/exclusion. Couting arguments: Diagonalization, Pigeonhole Principle.
Week 14 (5/7-9). HW11 due. More diagonalization. Counting by recurrence relations.
Week 15 (5/14-16) More examples of counting, with applications to probability.

Comprehensive Examinations

(5/16) Comprehensive test on fundamentals. Sharply worded short-answer questions requiring straightforward applications of basic concepts and definitions.
(1-3pm, 5/23) Comprehensive Final Examination on Chapters 1-8,10, with challenging questions on proofs, calculation, and counting asked mostly through couting problems. Includes proofs by induction, diagonalization, and counting arguments, and counting by solving difference equations.