Computer Science 140 and Mathematics 168
Algorithms
Syllabus, Spring 2009




Professor: Ran ("RON") Libeskind-Hadas
Office: Olin 1245
Phone: x18976
E-mail: ran@cs.hmc.edu
Ran's Spring 2009 schedule with office hours (... and 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, 9:35-10:50 AM Jacobs B132

Course Grutors: Bob Chen (bob_chen@hmc.edu), Steven Ehrlich (steven_ehrlich@hmc.edu), Marty Field (mfield@hmc.edu), Bryce Lampe (bryce_lampe@hmc.edu), David Lapayowker (dlapayowker@hmc.edu), Kevin Oelze (koelze@hmc.edu)

Getting Help: You are strongly encouraged to come and visit Ran during office hours, just drop in, or send an e-mail to set up a meeting time. You are also welcome to find a grutor to ask questions. Finally, if you have a short question about the homework, please send e-mail to algorithms@cs.hmc.edu. Ran and the grutors all get this e-mail so it's the fastest and most reliable way to get your question answered. You can also write to this address to arrange to meet with a grutor.

Course Homepage: www.cs.hmc.edu/courses/2009/spring/cs140


What Is This Course About?

This course will teach you to design algorithms, prove their correctness, and analyze their efficiency. 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, summations, and basic combinatorics. On some homeworks there will be short programming assignments. You may use your favorite high-level language (where "your favorite high-level language" is defined formally to be an element of the set {C, C++, Java, Python, Scheme, rex, ML})

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. There will be no official reading assignments from this book nor will problems be assigned from this book. It is a nice and readable book and 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 two or three 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 four to six more substantial problems and worth approximately 65-80 points. This assignment is due on the following Tuesday at the beginning of class.

Algorithms Dollars

There will be times during the semester when you will need a little extra time on an assignment. To that end, an account has been established for you with three "Algorithms Dollars". A dollar may be redeemed for an extension until 5 PM on the day after the assignment is normally due. You do not need to request permission for a dollar, simply slide your homework under Ran's office door by the extension time and a dollar will automatically be charged from your account. Aside from Algorithm dollar extensions, late homeworks will not be accepted unless there are special circumstances vetted by the Dean of Students or the Associate Dean for Academic Affairs.

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 three 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%   
	Attendance, Worksheets, and Participation: 10%
	Two "Midterm" Exams:  10% each, 20% total
	Final Exam: 20%

Collaboration Policy

Collaboration on homeworks is permitted. Here are the stipulations:

List of Topics