Math 2602. Discrete Mathematics
Professor Johan G. F. Belinfante
Summer 2007 Revised Syllabus of Lectures and Recitations

 
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  May 14  Web notes 1, Sections 1-2. Sequences and limits.  
T    15    Problems: p. 6, #1.2; p. 13, #2.5
W    16    Web notes 1. Sections 3-4. Rates of growth: O() and o() notation.
Th   17    Problems: p. 19, #3.2, 3.3; p. 24, #4.3, 4.7; p. 30, #5.1, 5.7
F    18    Web notes 1, Section 5. Standard sequences. 

M    21    MR Sect 2.1  Induction.  
T    22    Problems: MR, p. 148 # 5, 11, 16, 17; p. 149, # 27, 28;
W    23    MR 2.2  Round-Robin Tournaments
Th   24    Problems: p.156, # 2, 20; p. 191, # 4, 15
F    25    MR 2.3  Second form of induction and well ordering.

M    28    *** holiday   no class ***
T    29    Problems: p. 214, # 23, 24, 30; p. 326, # 7, 24
W    30    MR 2.3  Divisibility; mod[n,d] 
Th   31    Problems: p. 338, # 8, 36
F  June 1  PID property of integers; Bezout identity for gcd; Euclid's Lemma

   
M     4    MR 2.4  Euclid's algorithm for gcd
T     5    Problems: p. 347, # 8; p. 353-4, #2, 19
W     6    *** first examination (mainly on Chap. 2) ***
Th    7    Problems: p. 363, # 3; p. 373, # 10, 16; 
F     8    MR 4.1-4.4  Counting; Permutations and Combinations

M    11    MR 4.5-4.6  Combinatorial Identities; Binomial Theorem 
T    12    Problems: p. 385, # 27
W    13    MR 4.7  Partitions of an integer      (progress report due)
Th   14    Problems: p. 233-4, # 4, 18, 19, 21, 23
F    15    MR 4.8  Generating functions.  Counting binary trees.
 
M    18    MR 4.8  Generating functions for sums and partitions
T    19    Problems: p. 247-9, # 3, 7, 8, 20
W    20    MR 3.1  Graph theory
Th   21    Problems: p. 263-5, # 7, 9, 26, 27
F    22    MR 3.2  Paths, Cycles and Adjacency Matrix; Warshall's Algorithm (Final drop date)

M    25    MR 3.3  Euler Cycles and Paths    
T    26    Problems:  p. 263-5, # 31, 32, 34, 35; p. 266, # 39; 
W    27    MR 3.6 Graph Coloring; Bipartite graphs
Th   28    Problems:  p. 292-5, #2, 3, 4, 5, 8, 30, 34
F    29    *** second examination ***

M  July 2  MR 3.4  Dijkstra's Algorithm for Shortest paths 
T     3    p. 284-5, #7, 8, 9; 
W     4    *** holiday   no class *** 
Th    5    Problems: Review of Linear Algebra
F     6    Review of Linear Algebra: Augmented Matrices; Elementary Operations
   
M     9    Gaussian Elimination and Back Substitution (GEBS Algorithm)
T    10    Problems: Review of Linear Algebra
W    11    Gauss-Jordan Reduction (GJR Algorithm)
Th   12    Problems: Review of Linear Algebra
F    13    Eigenvalues and eigenvectors; Cayley-Hamilton Theorem; Markov chains

M    16    *** third hour exam *** 
T    17    Problems: section 21 in lp_basics.pdf
W    18    Web notes 2 and 3. Linear Programming
Th   19    Problems: section 4.1 in lp.pdf
F    20    Web notes 2 and 3. Simplex Algorithm
 
M    23    Web notes 3. Artificial Variables (big M method)
T    24    Problems: section 23 in lp_basics.pdf
W    25    Web notes 3. Artificial Variables (two-phase method) 
Th   26    Review for final
F    27    Review  (Last day of classes)

Final exam: Monday 2007 July 30 at 2:50-5:40 p.m. in Skiles 202. 

This tentative final exam information comes from the Registrar web site.


homepage for Belinfante's Math 2602.


Revised: 2007 July 13