## 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

##### Lecture 1: Introduction to proofs
1. Constructive proofs
2. The computational power of the collapsing-compass
3. Proofs by case-analysis
• Practice Problem
• ##### Play
1. Web: Applet for Euclid's Second Proposition - http://aleph0.clarku.edu/~djoyce/java/elements/bookI/propI2.html
##### 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
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
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

##### 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
3. Circuit complexity
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
• Practice Problems
1. Text: page 33, 6.11, 6.12
##### 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.)
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. 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
1. Exercises 19.1-19.11 in text on p. 141-142.
2. Proofs by Contradiction: 12 Practice Problems
1. Text: Chapter 4, Sections 19-20, pp. 135-142.
##### Lecture 2: To be given February 23
1. If a^2 is even then so is a.
2. Infinitude of prime numbers.
3. Irrationality of the square root of 2.
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

### 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)
1. Text: Chapter 4, Section 21, pp. 155-171.

### Week 5 - Monday Feb 21 and Wednesday Feb 23

##### Lecture 1:
1. Functions
1. Counting functions
2. The pigeonhole principle
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
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)
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. 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
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
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
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
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

### 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
##### Lecture 2:
1. Probability continued
1. Conditional probability
2. Independence
2. Multisets
1. Homometric sets
2. Examples of homometric sets in music theory
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
##### 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
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.
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
1. Text: Chapter 9, Section 50, pp. 421-427.

### Week 13 - Monday April 18 and Wednesday April 20

##### 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
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
##### 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
1. Text: Section 50 - Eulerian Graphs
2. Web: Fleury's Algorithm Explained
3. Web: 3.2 - Graph isomorphism
4. Web: 3.3 - Graph planarity

### 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