Instructor: Jittat Fakcharoenphol

email: jtf@ku.ac.th

- Final practice #1 is here.

Course syllabus: TBA.

- Homework.1 (out 4/12/48 due 16/12/48) [.ps] [.pdf]
- Homework. 2 (out 3/1/49 due 13/1/49) [.ps] [.pdf]
- Midterm practice [.ps] [.pdf] (Also, you should try to work on homework problems as well.)
- Final practice#1 [.pdf]

1 | 18 Nov | Introduction. Triangulations. | 1a [.pdf], 1b [.pdf] |

2 | 25 Nov | Recurrence relations. Divide and conquer. Merge sort. Strassen's algorithm. | 2 |

3 | 2 Dec | Data structures: binary search trees, AVL trees,
priority queues, binary heaps, binomial heaps. Amortized
analysis. Splay trees (intro) |
3 |

4 | 9 Dec | Splay trees (finish), basic probability, skip lists (intro) | |

5 | 16 Dec | Skip lists (finish), treaps | |

6 | 23 Dec, 30 Dec |
Minimum spanning trees | |

7 | 6 Jan | Shortest paths (intro). Minimum spanning trees in randomized linear time (Karger, Klein, Tarjan algorithm). |

Notes: In many lectures, I converted MS Word documents to pdf's, but the picture quality is so poor. If you know how to fix it, please let me know. Thanks!

- 6.854/18.415J MIT Advanced Algorithms
- CS270 Berkeley Combinatorial Algorithms and Data Structures
- CS 473 UIUC Algorithms
- CS 683Cornell Advanced Algorithms