204512: Design and analysis of algorithms


Instructor: Jittat Fakcharoenphol
email: jtf@ku.ac.th


Announcement

Course Overview

This course provides an overview on the design and analysis of algorithms at a graduate level. We will focus on many useful algorithms, which should provide a good guide for the students on fundamental algorithm design techniques.
Course syllabus: TBA.

Assignments

Assignments are available in both postscript format (.ps) and pdf format (.pdf). To read pdf files, use acrobat reader. To read postscript files, use GSView.

Lecture Notes

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!

Useful links