This course covers various topics in algorithms that do not fit in the standard introduction course CS300.

I plan to cover the following topics:

- Advanced Dynamic Programming "tricks"
- Greedy algorithms for matroids
- Lower bounds: Linear and algebraic decision trees, algebraic computation trees
- Lower bounds: adversary arguments
- Treaps and skip lists
- (perhaps) Cuckoo hashing
- (perhaps) algorithm analysis techniques
- (perhaps) Linear programming and maximum flow

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.

- Exercise 2 on page 5 of Lecture 6 in Jeff Erickson's lecture notes. Deadline: Beginning of class on September 26.
- Give an algorithm to solve the MaxGap problem in linear time, by making use of the floor function. (The floor function allows you to convert a real number into an integer, which you can then use as an index into an array.) Deadline: Beginning of class on November 14.
- Exercise 3 on page 9 of
Lecture 15
in Jeff Erickson's lecture notes. Hint: Give a binary search tree
where a node
*v*has depth*n-1*, and show that after the MoveToRoot(v) operation, there will again be a node at depth*n-1*, and so on. Deadline: Beginning of class on December 5.