Contents (109 pages)
1 INTRODUCTION
   1.1 The stable matching problem
   1.2 Notion of an algorithm
   1.3 Proving correctness of algorithms
   1.4 Insertion sort
   1.5 Analysis of running time
   1.6 Asymptotic notation
2 SORTING
   2.1 Mergesort
       2.1.1 Recurrences
   2.2 Quicksort
   2.3 Randomized quicksort
   2.4 Lower bound on the time of sorting
   2.5 Countingsort
   2.6 Radixsort
3 DYNAMIC PROGRAMMING
   3.1 Assembly-line scheduling
   3.2 Matrix chain multiplication
   3.3 Longest common substring
4 GRAPH ALGORITHMS
   4.1 Breadth-first search
   4.2 Depth-first search
   4.3 Topological sort
   4.4 Minimum Spanning Tree
       4.4.1 Prim’s algorithm
   4.5 Network Flow
       4.5.1 Ford-Fulkerson Algorithm
   4.6 Maximum matchings in bipartite graphs
   4.7 Shortest Paths
       4.7.1 Dijkstra’s algorithm
       4.7.2 Directed acyclic graphs with possibly negative edge lengths
       4.7.3 Bellman-Ford

Linear programming is a very important class of problems, both algorithmically and
combinatorially. Linear programming has many applications. From an algorithmic
point-of-view, the simplex was proposed in the forties (soon after the war, and was
motivated by military applications) and, although it has performed very well in prac-
tice, is known to run in exponential time in the worst-case. On the other hand, since
the early seventies when the classes P and NP were defined, it was observed that linear
programming is... (39 pages)