### Topic Outline

Here is a tentative topic outline for the course:-
Greedy Algorithms - 2 weeks

Dynamic Programming - 2 weeks

Network Flows and Reductions - 2 weeks

Linear Programming - 2 weeks

Introduction to Complexity Theory - 2 weeks

Approximation Algorithms and Randomization - 2 weeks

**Weekly Readings (R), Lecture Notes (LN), and tutorials (TT)**

**Week 9 & 10:**

**R**: CLRS Section 35

**LN**: Some inapproximability results

**LN**: Weighted Vertex Cover with Edge Penalties

**LN**: Introduction to Approximation Algorithms

**LN**: Minimum Makespan Job Scheduling

**LN**: Subset Sum is NP-complete

**Week 9: - These are notes from 2014, I haven't had time to edit them so beware of silly mistakes.**

**R**: CLRS Section 34

**LN**: 3-Colouring is NP-complete

**LN**: SAT is NP-complete

**LN**: Introduction to Complexity

**Week 8:**

**R**: CLRS Section 29

**LN**: Introduction to Linear Programming

**Week 6:**

**R**: CLRS Sections 26.1 to 26.3

**LN**: The Max Flow/Min Cut Theorem

**LN**: Bipartite Matching

**Week 5:**

**R**: CLRS Sections 26.1 to 26.3

**LN**: Intro to Network Flows, Maximum Flow Problem

**Week 4:**

**R**: Sections 15, 25.2

**LN**: All Pairs Shortest Paths

**Week 3:**

**R**: Sections 15, 24.1-24.3,

**LN**: Weighted Interval Scheduling

**LN**: Bellman Ford Algorithm

**Week 2:**

**R**: CLRS 23 and 24.3

**LN**: Dijkstra's Shortest Path Algorithm

**LN**: Minimum Spanning Tree

**Week 1:**

**R**: Allan Borodin's lecture 2 and Jeff Erickson's notes on Sections 7.2 and 7.3

**LN**: Interval Scheduling

**TT**: Minimum Spanning Tree - Prim's Algorithm.

Notes to be posted next week when we cover Kruskal's algorithm