|
|
|
|
LECTURE
NOTES |
GENERAL
NOTES |
|
1 |
Jan 18 |
Thursday |
|
|
|
2 |
Jan 22 |
Monday |
|
|
|
3 |
Jan 25 |
Thursday |
Regular graphs
(Theorem 2.6, Theorem 2.7) |
|
|
4 |
Jan 29 |
Monday |
Isomorphism (Theorem
3.1, 3.2, 3.5) |
|
|
5 |
Feb 1 |
Thursday |
Trees: |
Note: Hw1 is out. It's due Feb 12. |
|
6 |
Feb 5 |
Monday |
The minimum spanning tree problem |
You can pickup handouts on the
Generic MST algorithm from the box
outside my office. |
|
7 |
Feb 8 |
Thursday |
Connectivity: |
|
|
8 |
Feb 12 |
Monday |
Connectivity |
Hw1 due. Hw2 out. |
|
9 |
Feb 15 |
Thursday |
Connectivity cont. |
|
|
10 |
Feb 20 |
Tuesday |
Eulerian Graphs Lecture notes |
|
| 11 |
Feb 22 |
Thursday |
Hamiltonian Graphs |
|
|
12 |
Feb 26 |
Monday |
Hamiltonian Graphs (cont) |
Hw2 due
-- No late submissions |
|
13 |
March 1 |
Thursday |
MIDTERM |
|
|
|
March 5-8 |
|
Spring Break |
|
|
14 |
March 12 |
Monday |
I will be out of town. |
|
|
15 |
March 15 |
Thursday |
Directed Graphs (Theorems 7.1 -- 7.5) |
|
|
16 |
March 19 |
Monday |
Tournaments (Theorems 7.6 -- 7.11) |
|
|
17 |
March 22 |
Thursday |
Matchings |
|
|
18 |
March 26 |
Monday |
Matchings (cont) |
Grand Marshall Wk. |
|
19 |
March 29 |
Thursday |
Flows |
Grand Marshall Wk. |
|
20 |
April 2 |
Monday |
We will continue our discussions on flows from where we left off.. |
Last day to
sign up for a
presentation Hw3 Out. Note the correction in Question 5: "Prove that G has a matching that saturates S union T" |
|
21 |
April 5 |
Thursday |
Planarity |
|
|
22 |
April 9 |
Monday |
Non-planar embeddings |
|
|
23 |
April 12 |
Thursday |
Review lecture focusing on matchings |
|
|
24 |
April 16 |
Monday |
Other graph parameters: coloring, independent
sets and dominating sets |
Hw3 Due Hw 4 Out |
|
25 |
April 19 |
Thursday |
Ramsey Theory |
|
|
26 |
April 23 |
Monday |
Extremal Graph Theory
|
|
|
27 |
April 26 |
Thursday |
Intro. to approximation algorithms |
|
|
28 |
April 30 |
Monday |
Project presentations:
|
Hw4 Due |
|
|
May 8 |
FINAL |
Tuesday, 5/8, 11:30-2:30pm |