Math 55

Discrete Mathematics

Lectures TuTh 8:00-9:30, 2060 Valley LSB

Office hours TuTh 11:00-12:00, 821 Evans Hall

GSIs: Bernard Anderson, John Goodrick.

Table of Contents

• Course Info
• Resources (books, notes, more)
• Academic honesty
• Assignments
• Solutions
• Exams

Topics covered

• 08/29: Propositional logic. Propositional equivalence. Predicates and quantifiers.
• 08/31: Nested quantifiers. Rules of inference.
• 09/05: Introduction to proofs. Proof methods and strategy.
• 09/07: Sets and set operations.
• 09/12: Functions; 1-1 and onto functions. Cardinality. Countable and uhncountable sets.
• 09/14: Inverses and composition of functions. Sequences and sums.
• 09/19: Algorithms. Searching and sorting. The halting problem.
• 09/21: The growth of functions. Big O, big Omega, big Theta notation.
• 09/26: Complexity of basic algorithms. Number theory: congruence.
• 09/28: Primes. Commond divisers and common multiples.
• 10/03: 1st midterm.
• 10/05: Integers and algorithms.
• 10/10: Applications of number theory.
• 10/12: Mathematical induction, incl. strong induction.
• 10/17: Recursive definitions and structural induction.
• 10/19: Recursive algorithms. Program correctness.
• 10/24: Basic counting techniques.
• 10/26: Pigeonhole principle.
• 10/31: Permutations and combinations.
• 11/02: Binomial coefficients. Generating combinations and permutations.
• 11/07: Introduction to discrete probability.
• 11/09: Basic probabilistic notions.
• 11/14: 2nd midterm.
• 11/16: Bayes' Theorem and applications.
• 11/21: Expected value and variance.
• 11/28: Linear recurrence relations.
• 11/30: Divide-and-conquer algorithms. Generating functions.
• 12/05: Graphs and graph models. Terminology and special graphs.
• 12/07: Basic facts about directed and undirected graphs. Euler and Hamilton paths.

Resources

• Books.
  • K. H. Rosen, Discrete mathematics and its applcations, 6th Edition, McGraw-Hill.
  • R. L. Graham, D. E. Knuth, O. Patashnik, Concrete mathematics, Addison-Wesley.

  The first book is the textbook for the course.

• Additional notes may be found here.

Academic honesty

The instructor welcomes cooperation among students and the use of books. However, handing in homework that makes use of other people's work (be it from a fellow student, a book or paper, or whatever) without explicit acknowledgement is considered academic misconduct.

Assignments

All homework problems are from the 6th edition of Rosen.

• Homework assignment #1, due Wed Sep 6th:
  Sec 1.1 - 24, 30, 38; Sec 1.2 - 30, 39, 51; Sec 1.3 - 10.
• Homework assignment #2, due Wed Sep 13th:
  Sec 1.4 - 30, 50; Sec 1.5 - 26, 28; Sec 1.6 - 24, 32, 38; Sec 1.7 - 8, 38, 42.
• Homework assignment #3, due Wed Sep 20th:
  Sec 2.1 - 8, 36; Sec 2.2 - 30, 48, 54; Sec 2.3 - 38, 64; Sec 2.4 - 10, 26, 34.
• Homework assignment #4, due Wed Sep 27th:
  Sec 3.1 - 4, 8, 14, 20, 34, 42; Sec 3.2 - 2, 8, 32, 62.
• Homework assignment #5, due Wed Oct 4th:
  Sec 3.3 - 4; Sec 3.4 - 16, 28; Sec 3.5 - 8; Sec 3.6 - 4.
• Homework assignment #6, due Wed Oct 11th:
  Sec 3.5 - 14, 20, 24; Sec 3.6 - 10, 24, 26, 30, 32, 38, 56.
• Homework assignment #7, due Wed Oct 18th:
  Sec 3.7 - 4, 20, 26, 42, 60; Sec 4.1 - 6, 10, 14, 28, 50.
• Homework assignment #8, due Wed Oct 25th:
  Sec 4.2 - 8, 10, 12, 30, 34; Sec 4.3 - 4, 8, 14, 34, 36.
• Homework assignment #9, due Wed Nov 1st:
  Sec 4.4 - 6, 8, 24; Sec 4.5 - 2, 4; Sec 5.1 - 2, 4, 6, 16, 34.
• Homework assignment #10, due Wed Nov 8th:
  Sec 5.2 - 16, 22, 26, 36; Sec 5.3 - 8, 24, 42; Sec 5.4 - 10, 24, 28.
• Homework assignment #11, due Wed Nov 29th:
  Sec 6.1 - 20, 36, 38, 40; Sec 6.2 - 12, 14, 24, 38; Sec 6.3 - 8, 16, 18; Sec 6.4 - 8, 16, 18, 22.
• Homework assignment #12, due Wed Dec 6th:
  Sec 7.2 - 4, 26, 40; Sec 7.3 - 10, 18, 30; Sec 7.4 - 2, 12, 16, 48.
• Suggested problems from the last sections:
  Sec 9.1 - 11, 13, 25; Sec 9.2 - 3, 27, 28; Sec 9.5 - 3, 10, 35, 41.

Solutions

• Solutions to homework assignment #1: in PS and in PDF.
• Solutions to homework assignment #2: in PS and in PDF.
• Solutions to homework assignment #3: main file and a supplement.
• Solutions to homework assignment #4: in PS and in PDF.
• Solutions to homework assignment #5: in PS and in PDF.
• Solutions to homework assignment #6: in PS and in PDF.
• Solutions to homework assignment #7: in PS and in PDF.
• Solutions to homework assignment #8: in PS and in PDF.
• Solutions to homework assignment #9: in PS and in PDF.
• Solutions to homework assignment #10: in PS and in PDF.
• Solutions to homework assignment #11: in PS and in PDF.
• Solutions to homework assignment #12: in PS and in PDF.

Exams

All tests in this class are open book and open notes.

• The first midterm (.ps, .pdf) was held Oct 3 in class.
• The second midterm (.ps, .pdf) was held Nov 14 in class.
• Final: Dec 15, 12:30 - 3:30, in 60 Evans Hall.