Efficient Algorithms (2003/4)

1. Part I (Fall 2003):
   • Exam questions: [.txt] [.ps] [.pdf] .
   • Here is a source that may be of help for some of you: [pdf] [ps] [ps.gz] .

     I have put there lecture notes taken in 2001; only lectures relevant to the part I exam are selected; some typos are corrected. Alternatively, look into the web page of a similar course I taught in 2001.

2. Part II (Spring 2004):
   0. A file [defs.tex] that you need if you would like to compile .tex sources.
   1. Karmarkar's algorithm for linear programming: [tex] [pdf] [ps.gz] .
   2. SAT algorithms: [tex] [pdf] [ps.gz] .
   3. Parallel algorithm for minimum perfect matching in general graphs: [tex] [pdf] [ps.gz] .
   4. Parallel algorithms for integer addition, multiplication, and matrix determinant: [tex] [pdf] [ps.gz] .
   5. Edmonds algorithm for maximum weighted matching in general graphs: [tex + pictures: 1, 2, 3 ] [pdf] [ps.gz] .
   6. Most general unifier: [tex] [pdf] [ps.gz] .
   7. How to draw a planar graph: [tex] [pdf] [ps.gz] .