Computer Science 181b
Advanced Topics in Algorithms
Syllabus, Spring 2002

Professor: Ran (``RON'') Libeskind-Hadas
Office: Olin 1245
Phone: x18976
E-mail: hadas@cs.hmc.edu
Office Hours: Monday, Wednesday, and Friday 1-3:30 PM
Course Time and Location: Tuesdays and Thursdays, 2:45-4 PM in Jacobs 134
Course Assistant: Kurt Dresner
Course Homepage: www.cs.hmc.edu/courses/2002/spring/cs181b


What Is This Course About?

This course will expose you to a number of advanced topics in algorithm design and analysis. During the first 10 weeks of the semester we will examine several interesting data structures and their amortized analysis, on-line algorithms, matroids and the theory of greedy algorithms, parallel and distributed algorithms, and a brief exposure to several other topics such as computational geometry and circuit algorithms, among others. In the last 5 weeks of the course, each student will present a result of his or her choice.

Texts

There is no single textbook for this course. A variety of relevant texts will be placed on reserve at Sprague Library and these will be announced in class.

Attendance and Participation

On-time attendance in every class is absolutely required to pass the course. If you are sick or have a special reason for missing class, please contact Ran before the class that you will miss. Otherwise, you are expected to be in class. Please make sure to arrive on-time as a courtesy to the instructor and your classmates. Participation in class is also expected and is a component of the course grade.

Assignments

There will be two assignments each week. On Tuesdays, you will receive a short assignment typically comprising 2 problems and worth approximately 20-25 points. This assignment is due on Thursday at the beginning of class. On Thursdays, you will receive a longer assignment typically comprising 4-6 problems and worth approximately 75-80 points. This assignment is due on the following Tuesday at the beginning of class. All problem set submissions must be typeset, preferably using LaTeX.

Worksheets

In almost every class, you will be asked to solve a problem on a worksheet. These worksheets will be turned in at the end of class. If you turn in a worksheet which exhibits effort, you will receive full credit for it. Worksheets will not be returned but you can assume that you have received full credit for it unless you hear otherwise from Ran.

Exams

There will two take-home exams during the first 10 weeks of the term. There will also be a final exam which will be comprehensive including coverage of the topics presented by the students.

Student Presentations

During the last 5 weeks of the semester, each student will present a result to the class. The expectation is that students will work in pairs, with each pair of students using a full 75 minute period to present a result. It is possible, although not preferable, for a student to present a result individually. The students will work with Ran in advance to select the topic and practice the presentation. In addition, the student presenters will be required to find a small number of homework problems on the topic and to help grade these problems.

Grades

The components of the course are worth the following: 
 
	Homework: 35% 
	Worksheets and Participation: 10%
        In-class Presentation: 15%
	Two Takehome Exams: 20%
	Final Exam: 20%

Collaboration Policy

Collaboration on homeworks is encouraged. This means that you may discuss approaches to solving a problem with anyone in the class. On each submitted homework, please indicate the names of all people with whom you discussed your solutions. Copying written solutions from any source (such as person or written source) is disallowed. There should be no collaboration on the takehome exams. All parties, including off-campus students, are expected to follow the Harvey Mudd Honor code.