Computer Science 141
Advanced Topics in Algorithms
Syllabus, Spring 2004

Professor: Ran ("RON") Libeskind-Hadas
Office: Olin 1245
Phone: x18976
E-mail: hadas@cs.hmc.edu
Office Hours: TBD
Course Time and Location: Mondays and Wednesdays, 2:45-4 PM, in Thomas-Garrett 208
Course Assistants: Ian Ferrel and Alex Popkin

Course Homepage: www.cs.hmc.edu/courses/2004/spring/cs141


What Is This Course About?

This course will expose you to a number of advanced topics in algorithm design and analysis. The course is divided into two parts. Part 1 of the course will last approximately 9 weeks. During this part of the course, Ran will present topics including advanced data structures and their amortized analysis, on-line algorithms, matroids and the theory of greedy algorithms, and parallel and distributed algorithms.

Part 2 of the course will comprise student presentations of material related to this course. The objective of this part of the course is to develop the ability to read original research papers, present the material clearly in class, and to write a self-contained module on the topic presented. This part of the course is described in more detail later in this syllabus.

Texts

There is no textbook for the course. Lectures will be self-contained.

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 Mondays, you will receive a short assignment typically comprising 2 problems and worth approximately 20-25 points. This assignment is due on Wednesday at the beginning of class. On Wednesday, you will receive a longer assignment typically comprising 4-6 problems and worth approximately 75-80 points. This assignment is due on the following Monday at the beginning of class. All problem set submissions must be typeset, preferably using LaTeX. Assignments will be posted in both pdf and LaTeX source formats on the course web page.

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.

Exam

There will be one exam in this course. It will be a take-home exam and will cover all of the material presented in class during Part 1. The exam will take place at the end of Part 1 of the course, roughly in week 9 or 10 of the semester.

Student Presentations

In Part 2 of the course, 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. Optionally, students may work individually and give a 35-40 minute presentation. You will work with Ran in advance to select the topic, find the appropriate papers to read, and develop your in-class presentation. In addition, you will write a self-contained module on the topic that you present which should be a clear and easy-to-read explanation of the topic. Finally, you will be asked to assign approximately 2 homework problems on your topic and you will grade these problems. These homeworks scores will count as required regular homework for your classmates.

Grades

The components of the course are worth the following: 
 
	Homework: 40% 
	Worksheets and Participation: 10%
	Take-home Exam:  20%
	Part 2 oral and written presentation:  30%

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.