Special Topics in Computer Science I: Advanced Algorithms (CS493)

Fall Semester 2012

Course summary

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.

Course information

Lecturer:
Otfried Cheong. Office: E3-1 3434, Phone: 3542.
Lectures

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.

Grading policy

The grade will be composed as follows (small changes reserved): Participation (20%), Homework (30%), Exam (50%).

Exams

There will be one exam on December 12, from 10:00 to 11:00 in our usual classroom.

Bulletin board

Please check the bulletin board regularly for announcements. You can also post your questions there. Both Korean and English are acceptable on the BBS :-)

Lecture notes

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.

Course progress

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

Homework

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.