This course covers various topics in algorithms that do not fit in the standard introduction course CS300.
I plan to cover the following topics:
This course is a one credit course. We will only meet once a week for the lecture. There will be some (theoretical) homeworks - maybe one single problem every two weeks. In general, the workload should be about 1/3 of CS300 (but without programming projects).
However, it is important to reserve time to review each lecture - otherwise you will have forgotten what we covered a week later!
This course is not suitable for students who have not yet taken CS300 (Introduction to Algorithms), or another algorithm course.
The class meets Wednesday from 10:00 to 10:50 in classroom 4 (room 2445) in the EECS building (E3-1). Lectures are given in English.
The grade will be composed as follows (small changes reserved): Participation (20%), Homework (30%), Exam (50%).
There will be one exam on December 12, from 10:00 to 11:00 in our usual classroom.
Please check the bulletin board regularly for announcements. You can also post your questions there. Both Korean and English are acceptable on the BBS :-)
We will use lecture notes available on-line, such as the notes by Jeff Erickson. We may also use some material from the book Algorithms by Dasgupta, Papadimitriou, Vazirani. The international edition is quite inexpensive, and there is also a Korean translation. The draft version is available online for free. Students are not required to buy the book.
I will put up links to the lecture notes as we cover each topic.
The course will be taught on the blackboard, so do not expect slides or other such lecture materials. If you miss a class, you'll have to ask a friend for their notes.
The material covered in the lectures so far:
| 09-05 | Optimal Binary Search Trees | Section 5.6 in Lecture 5 |
| 09-12 | Optimal Binary Search Trees, Longest Common Subsequence | Sections 6.3 and 6.2 in Lecture 6 |
| 09-19 | Matroids | Section 8.1 in Lecture 8 |
| 09-26 | Greedy algorithm for matroids | Sections 8.1 and 8.2 in Lecture 8 |
| 10-10 | Linear Decision Trees | Sections 7.1 and 7.2 in notes |
| 10-17 | Algebraic Decision Tree, Algebraic Computation Trees | Sections 7.3 and 7.4 |
| 10-31 | Examples of Ben-Or's technique: Diameter and MaxGap | |
| 11-07 | Amortization: Summation, Taxation, Potential | Section 14.2 in Lecture 14 |
| 11-14 | Incrementing and Decrementing, Quacks | Section 14.3 in Lecture 14 |
| 11-21 | Splay trees | Section 15.6 in Lecture 15 |
| 11-28 | A bit more on splay trees, Entropy | Chapter 4 in David MacKay, Information Theory, Inference, and Learning Algorithms |
| 12-05 | Xavier Goaoc's guest lecture: k-covers using Inclusion/Exclusion and zeta-transforms | Original article |
| 12-12 | Final exam |
There will be several homework assignments in this course. Homeworks must be turned in in English, and must be submitted on paper at the beginning of the lecture in the classroom.