APM 463/ APM 563/ MTS 663 Fall 2002

  • Office Hours: Tuesday 4:00 to 5:00 and Thursday 4:00pm to 5:00pm
  • Information Sheet: ps file .
  • Assignment 1: ps file .
  • Assignment 2: ps file .
  • Assignment 3: ps file .

    • (Updated 7th November, 2002)

  • For relevant exercises, see below.
  • For a more detailed syllabus, see below.
  • 3rd Sept: Covered 1.1-1.2
  • 5th Sept: The proof of Havel-Hakimi Theorem, 1.4, 1.5, 2.1
  • 10th Sept: The rest of 1.5, 2.3, 2.4 and 6.1
  • 12th Sept: The rest of 2.1 and 2.2, 2.5 and 3.1
  • 17th Sept: Kruskal's Algorithm, 4.5 and Matrix-Tree Theorem and Cayley's Theorem
  • 19th Sept: Shortest path in 4.5, beginning of 12.1-12.2
  • 24th Sept: 12.1-12.2
  • 26th Sept: Karger's algorithm
  • 1st Oct: Chapter 9 (different approach)
  • 3rd Oct: Q and A
  • 15th Oct: Discussion of Midterm
  • 17th Oct: Discussion of Project, Proof of 6 and 5 colours theorems
  • 22nd Oct: Ordinary generating functions, Sum Lemma, Product Lemma, Identites.
  • 24th Oct: Composition of integers.
  • 29th Oct: Partition of integers, recurrence relations, system of recurrence relations.
  • 5th Nov: {0,1}-strings, decomposition with respect to blocks.
  • 7th Nov: Planted plane trees, Lagrange's Inversion Formula.
  • 12th Nov: Exponential generating functions, Sum and Product Lemmas, rooted labelled trees, cycle decomposition of permutations, enumeration of cycles with respect to cycle structures.
  • 14th Nov: Q and A
  • 19th Nov: Permutations with restricted cycle structres, Binomial sums.
  • 21st Nov: Binomial sums, Q and A.
  • 26th Nov: Discussion of assignment, interconnection networks.

    • Relevant Sections: Graph Theory

    1.1-1.2, 1.4 (except Example 1.4.7, Example 1.4.8, Theorem 1.4.1)
    1.5 (except Applications 1.5.2 and 1.5.3)
    1.6 (except Applications 1.6.5)
    2.3-2.4, 3.1
    2.1, 2.2 (except the subsection on "Two Secondary Operations")
    Prim's Algorithm (p146-p147 in Section 4.5), Kruskal's Algorithm (the book introduces this as part of a more general algorithm in the study of matroids on p172; you may use the notes I gave in class instead of the approach given in the book.)
    4.4 (You are not required for the material in this section except Cayley's Theorem which we will prove using Matrix-Tree Theorem.)
    4.5 (p147-150)
    6.1
    12.1-12.2 (I will take a simplified approach.)
    Unrestricted minimum cut and a probalistic algorithm (not in text)
    Additional materials not in text.

    Topics discussed in class that are not covered in the main sections of the text

    Havel-Hakimi Theorem
    Matrix-Tree Theorem
    Karger's umrestricted minimum cut algorithm

    Relevant exercises: Graph Theory

    1.1.1-1.1.6,1.1.15-1.1.18,1.2.1-1.2.3,
    1.4.1-1.4.5,1.4.9-1.4.10,1.4.12,1.4.14-1.4.16,1.4.23-1.4.24,1.4.31
    1.5.1-1.5.6,1.5.9,1.5.19-1.5.22,1.5.25-5.28,1.5.36
    2.4.1-2.4.12
    3.1.1-3.1.10,3.1.14-3.1.17,3.1.21-3.1.26
    4.5.1-4.5.4,4.5.10-4.5.11,4.8.1-4.8.4
    4.5.5-4.5.9
    6.1.1-6.1.28
    12.2.2-12.2.8