Discrete Mathematics - Spring 2011


"There is no problem in the whole of mathematics which cannot be solved by direct counting." - Ernst Mach

Lecture Descriptions, Homework, Play and Tests

Most of the material for this course will come from the text:
Mathematics: A Discrete Introduction (Second Edition) by Edward Scheinerman, Brooks/Cole 2006.
Most of the material covered will come from Sections 1-16, 19-24, 28-35, and 46-52.
The rest of the material will come from handouts and reading material found on the course web page and the links thereon.

Week 1 - Monday Jan 24 and Wednesday Jan 26

  1. Web: Applet for Euclid's Second Proposition - http://aleph0.clarku.edu/~djoyce/java/elements/bookI/propI2.html
  1. Text: Chapter 1, Sections 1-4, pp. 1-25.
  2. Web: Chapter 1, Section 1.1.
  3. The Pythagorean Theorem - http://aleph0.clarku.edu/~djoyce/java/elements/bookI/propI47.html
  4. The Converse of the Pythagorean Theorem - http://aleph0.clarku.edu/~djoyce/java/elements/bookI/propI48.html
Web: Chapter 1, Section 1.2.1 - Java applet for Hinged Disection Proof of Pythagorean Theorem

Week 2 - Monday Jan 31 and Wednesday Feb 2

  1. Text: page 33, 6.11, 6.12
      1. Prove in as much detail as you can that an uninhibited McCulloch-Pitts threshold logic unit can compute only monotonic logical functions. (You will need to do the reading assignment to solve this problem.)
  1. Text: Functions, pp. 193-197.
  2. Read Chapter 2 of Neural Networks - A Systematic Introduction by R. Rojas: Threshold Logic (PDF)

Week 3 - Monday Feb 7 and Wednesday Feb 9

  1. Exercises 19.1-19.11 in text on p. 141-142.
  2. Proofs by Contradiction: 12 Practice Problems
    1. Proofs by Contradiction Tutorial

Week 4 - Monday Feb 14 and Wednesday Feb 16

Week 5 - Monday Feb 21 and Wednesday Feb 23

  1. Text: Chapter 5, Section 28, pp. 236-244.

Week 6 - Monday Feb 28 and Wednesday March 2

    1. Interactive Introduction to Graph Theory (Register and do the Quiz)
  1. Text: Section 46 - Fundamentals of Graph Theory, pp. 389-399.

Week 7 - Monday March 7 and Wednesday March 9

  1. Web: Range searching via locus method using inclusion-exclusion principle (play with the applet)
  2. Text: Section 52 - Planar Graphs, pp. 435-438.

Week 8 - Monday March 14 and Wednesday March 16

Lecture 1:
  1. Binomial coefficients
  2. Pascal's triangle
  3. More on graphs
    1. Euler's Formula - proof by double induction
  4. Reading Assignment
  1. Handout: Introduction to recursion
  2. Web: The Euclidean Algorithm Generates Traditional Musical Rhythms.
  3. Web: Euclidean Rhythms.
  1. Web: Applet for generating Euclidean Rhythms.

Week 9 - Monday March 21 and Wednesday March 23

Week 10 - Monday March 28 and Wednesday March 30

  1. Text: Chapter 6, Sections 29-31, pp. 245-266.
  2. Handout: Multisets in Music

Week 11 - Monday April 4 and Wednesday April 6

  1. Handout: Simple Induction Proof of the Arithmetic Mean - Geometric Mean Inequality
  2. Handout: A linear-time algorithm for computing the maximum gap among  a set of numbers (a marriage between the floor function and the Pigeonhole Principle)
  3. Text: Chapter 6, Sections 32-33, pp. 276-291.

Week 12 - Monday April 11 and Wednesday April 13

  1. Text: Section 47 - Subgraphs, Section 48 - Connection, Section 49 - Trees. Pages 399-421.
  2. Web: Orthogonal Connect-the-Dots (Play with the applet.)

Week 13 - Monday April 18 and Wednesday April 20

  1. Handout: Bucket Sorting - Expected Complexity
  2. Handout: Proof of Ore's Theorem via Backwards Induction

Week 14 - Monday April 25 and Wednesday April 27

    1. Text: Section 50 - Eulerian Graphs
    2. Web: Fleury's Algorithm Explained
    3. Web: 3.2 - Graph isomorphism
    4. Web: 3.3 - Graph planarity
      1. Web: Applet for Fleury's Algorithm for Eulerian Paths and Cycles

Week 15 - Monday May 2