Textbook: Stephen B. Maurer and Anthony Ralston (MR)
Discrete Algorithmic Mathematics, 3rd ed.
A. K. Peters (ISBN 1-56881-166-7)
The web
notes 1-4 are available on the course outline. For the review material on
linear algebra following the midterm break, use whatever book was assigned in
your freshman calculus class.
Date Chapter.Section/Topics or Page/Problems
M Jan 8 Web notes 1, Sections 1-2. Sequences and limits.
T 9 Problems: p. 6, #1.2; p. 13, #2.5
W 10 Web notes 1. Section 3. Monotone sequences, bounded and unbounded.
Th 11 Problems: p. 19, #3.2, 3.3; p. 24, #4.3, 4.7
F 12 Web notes 1, Section 4. Rates of growth: O() and o() notation.
M 15 *** holiday (MLK Day) no class ***
T 16 Problems: p. 30, #5.1, 5.7
W 17 Web notes 1, Section 5. Standard sequences.
Th 18 Problems: MR, p. 148 # 5, 11, 16, 17
F 19 MR Sect 2.1-2.2 Induction.
M 22 MR 2.3 Second form of induction and well ordering.
T 23 Problems: p. 149, # 27, 28; p.156, # 2, 20
W 24 MR 2.3 Divisibility theory
Th 25 Problems: p. 191, # 4, 15
F 26 MR 2.3 Unique Factorization
M 29 MR 2.4 Euclid's algorithm for gcd
T 30 Problems: p. 214, # 23, 24, 30
W 31 *** first examination ***
Th Feb 1 Problems: p. 326, # 7, 24; p. 338, # 8, 36
F 2 MR 4.1-4.3 Counting
M 5 MR 4.4 Permutations and Combinations
T 6 Problems: p. 347, # 8
W 7 MR 4.5 Combinatorial Identities
Th 8 Problems: p. 353-4, #2, 19
F 9 MR 4.6 Binomial Theorem
M 12 MR 4.7 Partitions of an integer
T 13 Problems: p. 363, # 3; p. 373, # 10, 16
W 14 MR 4.8 Generating function for sums
Th 15 Problems: p. 385, # 27
F 16 MR 4.8 Generating function for partitions (progress report due)
M 19 MR 4.8 Generating functions
T 20 Problems: p. 233-4, # 4, 18, 19, 21, 23
W 21 MR 3.1 Graph theory
Th 22 Problems: p. 247-9, # 3, 7, 8, 20
F 23 MR 3.2 Paths, Cycles
M 26 MR 3.2 Adjacency Matrix
T 27 Problems: p. 263-5, # 9, 26 & 27
W 28 MR 3.2 Warshall's algorithm
Th Mar 1 Problems: p. 263-4, # 7, 31, 32, 34, 35
F 2 MR 3.3 Euler Cycles and Paths (Final drop date)
M 5 MR 3.3 Hamiltonian Cycles and Paths
T 6 Problems: p. 275, # 1, 7, 22
W 7 MR 3.4 Dijkstra's Algorithm for Shortest paths
Th 8 Problems: p. 284-5, #7, 8, 9
F 9 MR 3.5 Search algorithms
M 12 MR 3.6 Graph Coloring; Bipartite graphs
T 13 Problems: p. 266, # 39; p. 292-3, #2, 3, 4, 5, 8
W 14 MR 3.7 Trees
Th 15 Problems: p. 295, #30, 34; p. 306-8, #2, 3, 4, 5, 12, 20
F 16 *** second examination ***
M 19 *** holiday (Spring Recess) no class ***
T 20 *** holiday (Spring Recess) no class ***
W 21 *** holiday (Spring Recess) no class ***
Th 22 *** holiday (Spring Recess) no class ***
F 23 *** holiday (Spring Recess) no class ***
M 26 Augmented Matrices, Elementary Operations
T 27 Problems:
W 28 Gaussian Elimination and Back Substitution (GEBS Algorithm)
Th 29 Problems:
F 30 Gauss-Jordan Reduction (GJR Algorithm)
M Apr 2 Complexity Analysis for the GEBS Algorithm
T 3 Problems:
W 4 Eigenvalues and eigenvectors
Th 5 Problems:
F 6 Projection Matrices for Eigenspaces
M 9 Markov chains
T 10 Problems:
W 11 Web notes 2 and 3. Linear Programming
Th 12 Problems:
F 13 *** third hour exam ***
M 16 Web notes 2 and 3. Simplex Algorithm
T 17 Problems: section 21 in lp_basics.pdf
W 18 Web notes 2. Simplex Algorithm
Th 19 Problems: section 4.1 in lp.pdf
F 20 Web notes 3. Artificial Variables (big M method)
M 23 Web notes 3. Artificial Variables (two-phase method)
T 24 Problems: section 23 in lp_basics.pdf
W 25 Integer Programming
Th 26 Problems: Review for final.
F 27 Review (Last day of classes)
Final exam: 2007 April 30 at 2:50-5:40 p.m. in Skiles 146.
Be aware that the tentative final exam information available on the Registrar web site is subject to change.
homepage for Belinfante's Math 2602.
Revised: 2007 January 3