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 116, 1924,
2835, and 4652.
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
 Constructive proofs
 The computational power of the collapsingcompass
 Proofs by caseanalysis
 Web: Applet for Euclid's Second Proposition 
http://aleph0.clarku.edu/~djoyce/java/elements/bookI/propI2.html
Lecture 2:
 The knottedstring computer
 If and only if theorems
 The Pythagorean Theorem and its converse
 Disproof by counterexample
 Text: Chapter 1, Sections 14, pp. 125.
 Web: Chapter 1, Section 1.1.
 The Pythagorean Theorem 
http://aleph0.clarku.edu/~djoyce/java/elements/bookI/propI47.html
 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
Lecture 1:
 Logic
 Caseanalysis proofs of logical equivalence via truth tables
 Boolean algebra and Boolean circuits
 AND, OR, and NOT gates
 Contradictions and tautologies
 Circuit complexity
 Text: Chapter 1, Sections 56, pp. 2536.
 Web Tutorial on Boolean circuits and expressions (7 sections):
http://www.electronicstutorials.ws/boolean/bool_1.html
 Text: page 33, 6.11, 6.12
Lecture 2:
 De Morgan's Rules
 Universality Theorem
 Proof via sumofproducts expansions
 Majority function
 Odd parity function
 Threshold logic units (TLUs)
 Computational power of a TLU
 Linear separability
 Exclusive OR function
 Neural networks
 Combining Boolean and threshold logics: Rosenblat's Perceptron
 Prove in as much detail as you can that an uninhibited
McCullochPitts threshold logic unit can compute only monotonic logical functions. (You
will need to do the reading assignment to solve this problem.)
 Text: Functions, pp. 193197.
 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:
 Proofs by contradiction
 In a rightangle triangle the hypotenuse is less than the sum
on the other two sides.
 Maximum distance between two points in a polygon is
determined by a pair of vertices.
 Integers that are even and odd.
 Text: Chapter 4, Sections 1920, pp. 135142.
Lecture 2: To be given
February 23
 Proofs by contradiction continued
 If a^2 is even then so is a.
 Infinitude of prime numbers.
 Irrationality of the square root of 2.
 Contradicting irreducibility of integers
 Contradicting positivity of integers
 Diophantine equations: There are no positive integer
solutions to the equation x^2  y^2 = 1.
 Induction proofs
 Weak induction  3coloring the vertices of a triangulated
polygon
 Proofs
by Contradiction Tutorial
Week 4  Monday Feb 14 and
Wednesday Feb 16
Lecture 1: To be given
February 24
 More induction proofs
 Weak induction proofs in sums of sequences
 Strong induction  every triangulated polygon has at least
two exterior triangles (ears)
 Text: Chapter 4, Section 21, pp. 155171.
Lecture 2: 40minutequiz
on contradiction proofs
Week 5  Monday Feb 21 and
Wednesday Feb 23
Lecture 1:
 Functions
 Counting functions
 The pigeonhole principle
 Text: Chapter 5, Sections 2324, pp. 193211.
Lecture 2:
 Asorted notation
 Big oh
 Omega and Theta
 Little oh
 Floor and ceiling
 Text: Chapter 5, Section 28, pp. 236244.
Week 6  Monday Feb 28 and
Wednesday March 2
Lecture 1:
 Induction proofs continued
 Number of triangles in a triangulated polygon
 Twocoloring the faces of an arrangement of lines
 Existence of triangular faces in arrangements of lines
 Existence proofs
 Coloring points in the plane
 Interactive
Introduction to Graph Theory (Register and do the Quiz)
 Web: Coloring Points in the Plane 
http://www.cuttheknot.org/proofs/two_color.shtml
Lecture 2:
 Induction proofs continued
 Tiling chess boards with triominoes
 Graphs
 Adjacencies, adjacency matrices, and the HandShaking Lemma
 Combinatorial proofs
 Degree, simple graphs, regular graphs,
complete graphs, dense graphs, sparse graphs, edgeless graphs and empty
graphs
 Order, size,
 Isomorphic and isotopic graphs
 Plane graphs, planar graphs and graph embeddings
 Text: Section 46  Fundamentals of Graph Theory, pp. 389399.
Week 7  Monday March 7 and
Wednesday March 9
Lecture 1:
 Sets and subsets
 Counting subsets
 Power sets
 Operations on sets
 Union
 Intersection
 Size  inclusionexclusion counting
 Difference
 Symmetric difference
 Notation
 Big "Oh"  upper bounds
 Big "Ω"  lower bounds
 Big "Θ"  lower and upper bounds
 Ceiling and floor functions
 Models of computation
 Complexity of algorithms
 Practice Problems: Exercises
28, p. 242

Reading Assignment
 Text: Chapter 2  Collections (lists, factorial, sets, counting
sets, quantifiers, union, intersection, symmetric difference), pp.
3782.
 Text: Chapter 5, Section 28  Assorted Notation, pp. 236242.
 Growth
of Functions (PDF file)
Lecture 2:
 Application of inclusionexclusion to range searching
 Datastructures for answering queries efficiently
 The locus method
 Space complexity, preprocessing complexity, and query
complexity
 Web: Range
searching via locus method using inclusionexclusion principle
(play with the applet)
 Text: Section 52  Planar Graphs, pp. 435438.
Week 8  Monday March 14 and
Wednesday March 16
Lecture 1:
 Binomial coefficients
 Pascal's triangle
 More on graphs
 Euler's Formula  proof by double induction

Reading Assignment
 Text: Chapter 3, Section 16, Binomial Coefficients, pp. 104117.
Lecture 2:
 Recurrence relations
 Linear search
 Binary search
 Number theory:
 Maximally even sets
 The greatest common divisor and the mod function
 The Euclidean algorithm
 Iterative version
 Recursive version
 Applications of the Euclidean algorithm:
 Musical rhythm generation
 Handout: Introduction
to recursion
 Web: The
Euclidean Algorithm Generates Traditional Musical Rhythms.
 Web: Euclidean
Rhythms.
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
 More applications of the Euclidean algorithm:
 Pattern analysis and design
 The Pigeonhole Principle
 Integer lattice problems
 Recursion trees
 Divideandconquer
 Mergesort
 Triangulating points in the plane
 Probability
 Sample space
 Events
Lecture 2:
 Probability continued
 Conditional probability
 Independence
 Multisets
 Homometric sets
 Examples of homometric sets in music theory
 Text: Chapter 6, Sections 2931, pp. 245266.
 Handout: Multisets in
Music
Week 11  Monday April 4 and
Wednesday April 6
Lecture 1:
 Induction proof of the Hexachordal Theorem
 Deep sets: examples from music theory
 Random variables
 Probability distributions and density functions
 Bernoulli trials and binomial random variables
 Independent random variables
 Expectation
 Product of random variables
 Measures of central tendency
Lecture 2:
 Random variables continued...
 The arithmetic mean  geometric mean inequality
 Induction proof of the AMGM inequality
 The Monty Hall problem
 The Pigeonhole Principle in algorithm design
 The largest gap problem
 Handout: Simple
Induction Proof of the Arithmetic Mean  Geometric Mean Inequality
 Handout: A
lineartime algorithm for computing the maximum gap among a set
of numbers (a marriage between the floor function and the
Pigeonhole Principle)
 Text: Chapter 6, Sections 3233, pp. 276291.
Week 12  Monday April 11 and
Wednesday April 13
Lecture 1:
 Graph theory
 Subgraphs
 Connections
 Paths
 Cycles
 Hamiltonian graphs
 Travelling salesperson problems
 Polygonizations of point sets
 Monotonic polygonizations
 Problem Assignment: Text:
Problems 48.6 and 49.16.

Reading Assignment
 Text: Section 47  Subgraphs, Section 48  Connection, Section 49
 Trees. Pages 399421.
 Web: Orthogonal
ConnecttheDots (Play with the applet.)
Lecture 2:
 More on Hamiltonian graphs
 Polygonizations of point sets
 Starshaped polygonizations
 Orthogonal connectthedots
 Text: Chapter 9, Section 50, pp. 421427.
Week 13  Monday April 18 and
Wednesday April 20
Lecture 1: Patriot's Day
 No classes
Lecture 2:
 Measures of variability
 Expected complexity of algorithms
 Bucket sorting in linear expected time
 More on Hamiltonian cycles and paths
 Proof of Ore's theorem on cycleHamiltonicity of dense
graphs
via
backwards
induction and the Pigeonhole Principle
 Handout:
Bucket
Sorting  Expected Complexity
 Handout: Proof
of Ore's Theorem via Backwards Induction
Week 14  Monday April 25 and
Wednesday April 27
Lecture 1:
 Decision theory
 Bayes' Rule
 Bayes' Theorem
 Parametric decision rules
 Linear discriminat functions
 The threshold logic unit as a classifier
 Nonparametric decision rules
 The kNearestNeighbor decision rule
Lecture 2:
 Eulerian circuits
 Eulerian tours and the Konigsberg bridge problem
 The EulerHierholzer Theorem
 Subcircuit merging algorithm for computing Euler circuits
 Fleury's algorithm for computing Euler circuits or paths
 Map coloring
 The fourcolor theorem
 Text: Section 50  Eulerian Graphs
 Web: Fleury's
Algorithm Explained
 Web: 3.2  Graph isomorphism
 Web: 3.3  Graph planarity
 Web: Applet
for Fleury's Algorithm for Eulerian Paths and Cycles
Week 15  Monday May 2
Lecture 1:
 More map (graph) coloring
 Scheduling problems via graph coloring
 The chromatic number of a graph
 Proof that every planar graph has a vertex of degree at most 5
 Induction proof of the the 5color theorem for planar graphs
 Text: Section 51  Coloring, pp. 427435.
 Text: Section 52  Planar Graphs, The 5Color Theorem, pp.
435447.
 Handout: MapGraphColoring.pdf