| Lecture |
Date |
Notes |
Lecture Notes |
| 1 |
Jan
19 |
Introduction,
basic properties and definitions |
Lecture 1 |
| 2 |
Jan
22 |
Degrees |
Lecture 2 |
| 3 |
Jan
23 |
Isomorphism |
Lecture 3 |
| 4 |
Jan
30 |
Trees |
Lecture 4 |
| 5 |
Feb
2 |
The
Minimun Spanning Tree Problem, Greedy algorithms |
Lecture 5 |
| 6 |
Feb
6 |
HW1 out (due 2 pm Feb 21st) Graph representations, BFS and properties |
Lecture 6 |
| 7 |
Feb
9 |
Connectivity
|
Lectures 7 & 8 |
| 8 |
Feb
13 |
Connectivity
(cont) |
Lectures 7 & 8 |
| 9 |
Feb
16 |
Graph
traversals: Eularian graphs |
Lecture 9 |
| 10 |
Feb
21 (Tue) |
Hw1 is due today Graph traversals: Hamiltonian graphs |
Lecture 10 |
| 11 |
Feb
23 |
HW
2 out (due 2pm Mar 6th) Directed Graphs |
Lecture 11 |
| 12 |
Feb
27 |
Matchings
and Vertex-Covers Midterm 1 will include topics from lectures 1 - 12 |
Lecture 12 |
| 13 |
Mar
2 |
Overview
Lecture. |
|
| 14 |
Mar
6 |
Matchings
and network flows Hw2 is due today |
Lecture 13 |
| 15 |
Mar
9 |
MIDTERM |
|
| Mar
13 - 17 |
Spring
break |
||
| 16 |
Mar
20 |
Planarity |
Lecture 14 |
| 17 |
Mar
23 |
Non-planar
embeddings |
Lecture 15 |
| 18 |
Mar
27 |
HW
3 out Art Gallery Theorem as an application of vertex coloring |
Lecture 16 |
| 19 |
Mar
30 |
Vertex
and Coloring |
Lecture 17 Quiz Solution |
| 20 |
April
3 |
Ramsey Theory | Lecture 18 |
| 21 |
April
6 |
Review
Lecture: solutions of homework 1, 2 and midterm |
|
| 22 |
April
10 |
HW3
due Extremal Graph Theory |
Not
available. Section 11.2 of text |
| 23 |
April
13 |
Intro
to approximation algorithms (vertex cover, dominating set,
k-center) |
Lecture 20 |
| 24 |
April
17 |
HW
4 out approximation algorithms (TSP, multi-way cut, max-cut) |
Lecture 21 |
| 25 |
April
20 |
Cancelled |
|
| 26 |
April
24 |
Distance | Lecture 22 |
| 27 |
April
27 |
Class
presentations |
Notes |
| 28 |
May
1 |
HW
4 due Course overview |
|
| May 8 (Mon) |
FINAL (3-6pm) Information about the final |