Discrete Mathematics - Spring 2011

Lecture Descriptions, Homework, Play and Tests

Week 1 - Monday Jan 24 and Wednesday Jan 26

Lecture 1: Introduction to proofs


1. Constructive proofs
   
2. The computational power of the collapsing-compass
   
3. Proofs by case-analysis
   

• Reading Assignment

1. Text: pp. xv-xxiii
   
2. Read the paper: A New Look at Euclid's Second Proposition (PDF)
   

1. The Collapsing Compass (PDF)
   

• Play
  

Lecture 2:

1. The knotted-string computer
2. If and only if theorems
   
3. The Pythagorean Theorem and its converse
   
4. Disproof by counter-example

• Reading Assignment

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
   

• Play

Week 2 - Monday Jan 31 and Wednesday Feb 2

Lecture 1:

1. Logic
2. Case-analysis proofs of logical equivalence via truth tables
   
3. Boolean algebra and Boolean circuits
1. AND, OR, and NOT gates
2. Contradictions and tautologies
   
3. Circuit complexity
   

• Reading Assignment

1. Text: Chapter 1, Sections 5-6, pp. 25-36.
2. Web Tutorial on Boolean circuits and expressions (7 sections): http://www.electronics-tutorials.ws/boolean/bool_1.html
   

Lecture 2:

1. De Morgan's Rules
2. Universality Theorem
1. Proof via sum-of-products expansions
2. Majority function
3. Odd parity function
   
3. Threshold logic units (TLUs)
   
1. Computational power of a TLU
2. Linear separability
3. Exclusive OR function
   
4. Neural networks
1. Combining Boolean and threshold logics: Rosenblat's Perceptron

• Practice Problem

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.)
   

• Reading Assignment

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

Lecture 1:

1. Proofs by contradiction
1. In a right-angle triangle the hypotenuse is less than the sum on the other two sides.
   
2. Maximum distance between two points in a polygon is determined by a pair of vertices.
   
3. Integers that are even and odd.

• Practice Problems

• Reading Assignment

1. Text: Chapter 4, Sections 19-20, pp. 135-142.
   

Lecture 2: To be given February 23


1. Proofs by contradiction continued
   
1. If a^2 is even then so is a.
2. Infinitude of prime numbers.
3. Irrationality of the square root of 2.
1. Contradicting irreducibility of integers
2. Contradicting positivity of integers
   
4. Diophantine equations: There are no positive integer solutions to the equation x^2 - y^2 = 1.
5. Induction proofs
1. Weak induction - 3-coloring the vertices of a triangulated polygon
   

• Reading Assignment

1. Proofs by Contradiction Tutorial
   

Week 4 - Monday Feb 14 and Wednesday Feb 16

Lecture 1: To be given February 24


1. More induction proofs
1. Weak induction proofs in sums of sequences
   
2. Strong induction - every triangulated polygon has at least two exterior triangles (ears)

• Reading Assignment

1. Text: Chapter 4, Section 21, pp. 155-171.

Lecture 2: 40-minute-quiz on contradiction proofs

Week 5 - Monday Feb 21 and Wednesday Feb 23

Lecture 1:

1. Functions
1. Counting functions
2. The pigeonhole principle

• Reading Assignment

1. Text: Chapter 5, Sections 23-24, pp. 193-211.
   

Lecture 2:

1. Asorted notation
1. Big oh
2. Omega and Theta
3. Little oh
   
4. Floor and ceiling
   

• Reading Assignment

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

Week 6 - Monday Feb 28 and Wednesday March 2

Lecture 1:

1. Induction proofs continued
1. Number of triangles in a triangulated polygon
   
2. Two-coloring the faces of an arrangement of lines
3. Existence of triangular faces in arrangements of lines
2. Existence proofs
1. Coloring points in the plane

• Practice Problems

1. Interactive Introduction to Graph Theory (Register and do the Quiz)
   

• Reading Assignment

1. Web: Coloring Points in the Plane - http://www.cut-the-knot.org/proofs/two_color.shtml
   

Lecture 2:

1. Induction proofs continued
1. Tiling chess boards with triominoes
2. Graphs
1. Adjacencies, adjacency matrices, and the Hand-Shaking Lemma
1. Combinatorial proofs
   
2. Degree, simple graphs, regular graphs, complete graphs, dense graphs, sparse graphs, edgeless graphs and empty graphs
   
3. Order, size,
   
4. Isomorphic and isotopic graphs
   
5. Plane graphs, planar graphs and graph embeddings

• Reading Assignment

1. Text: Section 46 - Fundamentals of Graph Theory, pp. 389-399.

Week 7 - Monday March 7 and Wednesday March 9

Lecture 1:

1. Sets and subsets
2. Counting subsets
3. Power sets
4. Operations on sets
1. Union
2. Intersection
3. Size - inclusion-exclusion counting
   
4. Difference
5. Symmetric difference
5. Notation
1. Big "Oh" - upper bounds
2. Big "Ω" - lower bounds
3. Big "Θ" - lower and upper bounds
   
4. Ceiling and floor functions
   
6. Models of computation
   
7. Complexity of algorithms

• Practice Problems: Exercises 28, p. 242
  

• Reading Assignment

1. Text: Chapter 2 - Collections (lists, factorial, sets, counting sets, quantifiers, union, intersection, symmetric difference), pp. 37-82.
2. Text: Chapter 5, Section 28 - Assorted Notation, pp. 236-242.
3. Growth of Functions (PDF file)
   

Lecture 2:

1. Application of inclusion-exclusion to range searching
1. Data-structures for answering queries efficiently
2. The locus method
   
3. Space complexity, preprocessing complexity, and query complexity
   

• Reading Assignment

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. Text: Chapter 3, Section 16, Binomial Coefficients, pp. 104-117.
   

Lecture 2:

1. Recurrence relations
1. Linear search
2. Binary search
   
2. Number theory:
1. Maximally even sets
   
2. The greatest common divisor and the mod function
   
3. The Euclidean algorithm
1. Iterative version
2. Recursive version
   
4. Applications of the Euclidean algorithm:
1. Musical rhythm generation

• Reading Assignment

1. Handout: Introduction to recursion
   
2. Web: The Euclidean Algorithm Generates Traditional Musical Rhythms.
   
3. Web: Euclidean Rhythms.

• Play

Week 9 - Monday March 21 and Wednesday March 23

Lecture 1: Spring Break - no class

Lecture 2: Spring Break - no class

Week 10 - Monday March 28 and Wednesday March 30

Lecture 1:

1. More applications of the Euclidean algorithm:
1. Pattern analysis and design
   
2. The Pigeonhole Principle
1. Integer lattice problems
   
3. Recursion trees
1. Divide-and-conquer
2. Merge-sort
3. Triangulating points in the plane
4. Probability
1. Sample space
2. Events

• Reading Assignment

1. Handout: Unraveling Roman mosaic meander patterns: A simple algorithm for their generation.
2. Text: Chapter 5, Section 24, The Pigeonhole Principle, pp. 205-207.

Lecture 2:

1. Probability continued
   
1. Conditional probability
2. Independence
2. Multisets
1. Homometric sets
   
2. Examples of homometric sets in music theory

• Reading Assignment

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

Week 11 - Monday April 4 and Wednesday April 6

Lecture 1:

1. Induction proof of the Hexachordal Theorem
1. Deep sets: examples from music theory
   
2. Random variables
1. Probability distributions and density functions
2. Bernoulli trials and binomial random variables
   
3. Independent random variables
4. Expectation
5. Product of random variables
6. Measures of central tendency

• Reading Assignment

1. Text: Chapter 6, Sections 32-33, pp. 266-275.
2. Handout: Introduction to Random Variables
   

Lecture 2:

1. Random variables continued...
1. The arithmetic mean - geometric mean inequality
2. Induction proof of the AM-GM inequality
   
2. The Monty Hall problem
3. The Pigeonhole Principle in algorithm design
1. The largest gap problem
   

• Reading Assignment

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

Lecture 1:

1. Graph theory
   
1. Subgraphs
2. Connections
3. Paths
4. Cycles
2. Hamiltonian graphs
1. Travelling sales-person problems
2. Polygonizations of point sets
1. Monotonic polygonizations

• Problem Assignment: Text: Problems 48.6 and 49.16.
  

• Reading Assignment

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

Lecture 2:

1. More on Hamiltonian graphs
1. Polygonizations of point sets
1. Star-shaped polygonizations
   
2. Orthogonal connect-the-dots

• Reading Assignment

1. Text: Chapter 9, Section 50, pp. 421-427.

Week 13 - Monday April 18 and Wednesday April 20

Lecture 1: Patriot's Day - No classes  

Lecture 2:

1. Measures of variability
   
2. Expected complexity of algorithms
   
1. Bucket sorting in linear expected time
3. More on Hamiltonian cycles and paths
   
1. Proof of Ore's theorem on cycle-Hamiltonicity of dense graphs via backwards induction and the Pigeonhole Principle
   

• Reading Assignment

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

Lecture 1:

1. Decision theory
1. Bayes' Rule
   
2. Bayes' Theorem
3. Parametric decision rules
4. Linear discriminat functions
1. The threshold logic unit as a classifier
   
5. Non-parametric decision rules
1. The k-Nearest-Neighbor decision rule

• Reading Assignment

1. Handout: Introduction to Bayes Decision Theory
2. Handout: Minimum Distance Classifying Threshold Logic Unit.pdf

Lecture 2:

1. Eulerian circuits
1. Eulerian tours and the Konigsberg bridge problem
2. The Euler-Hierholzer Theorem
1. Sub-circuit merging algorithm for computing Euler circuits
   
2. Fleury's algorithm for computing Euler circuits or paths
   
2. Map coloring
1. The four-color theorem

• Reading Assignment

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

• Playing Assignment

1. Web: Applet for Fleury's Algorithm for Eulerian Paths and Cycles

Week 15 - Monday May 2

Lecture 1:

1. More map (graph) coloring
1. Scheduling problems via graph coloring
2. The chromatic number of a graph
2. Proof that every planar graph has a vertex of degree at most 5
3. Induction proof of the the 5-color theorem for planar graphs

• Reading Assignment

1. Text: Section 51 - Coloring, pp. 427-435.
2. Text: Section 52 - Planar Graphs, The 5-Color Theorem, pp. 435-447.
3. Handout: Map-Graph-Coloring.pdf