Computer Science 140 and Mathematics 168
Algorithms
Syllabus, Spring 2007




Professor: Ran ("RON") Libeskind-Hadas
Office: Olin 1258
Phone: x18976
E-mail: hadas@cs.hmc.edu
Office Hours: Monday, Tuesday, Wednesday, and Friday from 3:30-5 PM in Olin 1258. You are always welcome to get in touch to set up a time to meet outside of regular office hours.
Course Time and Location: Tuesdays and Thursdays, 1:15-2:30 PM in Galileo Macalister

Course Grutors: Jonathan Beall, Mike Buchanan, Nate Chenette, Phil Miller, Carl Nygaard, and Steven Sloss
Course Homepage: www.cs.hmc.edu/courses/2007/spring/cs140


What Is This Course About?

This course will teach you to design algorithms, prove their correctness, and analyze their computational complexity. The course emphasizes general problem-solving techniques that will allow you to become a good algorithm designer.

Is This Course for You?

The answer is YES! Alright, seriously, the prerequisites for this course are Math 55 and CS 60. In addition, you must have completed either CS 70 or Math 131 before enrolling in this course. Much of our time will be spent carefully analyzing algorithms using mathematical induction, recurrence relations, and summation techniques. On some homeworks there will be short programming assignments. Any high-level language (which is defined formally to be an element of the set {C, C++, Java, Python, Scheme, rex, ML}) may be used for these assignments.

Lecture Notes and Text

The lecture notes provided in class will be self-contained outlines, but will require that you fill in many of the details that we do interactively at the blackboard.

The following book is the official textbook of this class, although it is primarily intended as a reference to reinforce concepts from class. It is available at Huntley Bookstore.

Algorithms, by S. Dasgupta, C. Papadimitriou, and U. Vazirani. McGraw-Hill, ISBN 978-0-07-352340-8.

In addition, the following book is an excellent reference that you will probably want to have in your book collection at some point. It is not sold at Huntley but is available online at most bookstores.

Introduction to Algorithms, 2nd Edition by T. Cormen, C. Leiserson, R. Rivest, and C. Stein. McGraw-Hill and MIT Press, ISBN 0-07-013151-1.

Attendance

If you are sick or have a special reason for missing class, please send Ran e-mail 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.

Assignments

There will be two assignments each week. On Tuesdays, you will receive a short assignment typically comprising 2-3 problems and worth approximately 20-35 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 65-80 points. This assignment is due on the following Tuesday at the beginning of class. Late homeworks will not be accepted unless arrangements have been made with Ran in advance for special circumstances.

Typesetting your Assignments

You are expected to typeset your assignments using LaTeX for the first two weeks of the semester. The reason for this requirement is that LaTeX is an important tool that is widely-used in computer science, mathematics, among other disciplines. Its use is required in some upper-division courses at HMC and you'll almost certainly need to use it in the future. Learning it now is useful! Check out the LaTeX link (also available from the course homepage) for tutorials, documentation, and sample latex documents.

After the second week of assignments, you may turn in your assignments any way you like (handwritten, LaTeX, or otherwise). You are certainly strongly encouraged to keep using LaTeX, but it's not required after the first two weeks.

Whenever you use LaTeX, if you wish to include a figure you may draw the figure in a drawing tool and import it, use LaTeX's own drawing facilities, or simply leave some space in your document and do the drawing by hand.

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 be 3 exams in this course: Two take-home exams during the semester and a comprehensive final exam. Dates and details of the exams will be announced in class.

Grades

The components of the course are worth the following: 
 
	Homework: 50 course points   
	Worksheets and Attendance: 10 course points
	Two "Midterm" Exams: 20 course points
	Final Exam: 20 course points
Note: You must turn in all worksheets in order to receive the 10 points for this component (unless you miss class due to illness or special circumstances). Since attendance is required, it is expected that all students will receive their 10 worksheet points.

Collaboration Policy

Collaboration on homeworks is permitted. Here are the stipulations:

List of Topics