Computer Science 140 and Mathematics 168
Algorithms
Syllabus, Spring 2012




Professor: Ran ("RON") Libeskind-Hadas
Office: Olin 1258
Phone: x18976
Ran's E-mail: ran@cs.hmc.edu
Algorithms Help E-mail: algorithms@cs.hmc.edu
Office Hours: Here
Time and Location: Tuesdays and Thursdays, 9:35-10:50 AM, Beckman Auditorium
Course Grutors: Tselil Schramm (Head Grutor), Chris Beavers, Kevin Black, Aaron Gable, Lindsay Hall, Jenny Iglesias, Sean Laguna, Kathryn Lingel, Steve Matsumoto, Alice Paul, Matt Richman, Louis Ryan, Xanda Schofield, Veerasak "Jeep" Srisuknimit

Tutoring Hours: Tutoring hours are held in the Platt Campus Center living room near one of the whiteboards.

Getting Help: You are strongly encouraged to come and visit Ran during office hours or talk to the grutors during their grutoring hours. 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.

Course Homepage: www.cs.hmc.edu/courses/2012/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, Haskell, or 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 relatively few reading assignments from this book.

Algorithms by S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani. McGraw Hill.

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. You may not redeem more than one dollar per assignment (for a longer extension).

If you are sick and your illness warrants a visit to the doctor, then please let Ran know in advance of the homework deadline and an extension can be arranged that does not use your Algorithms Dollars.

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 in-class final exam. The final exam will be held during the regular final exam time established by the registrar.

Grades

The components of the course are worth the following: 
 
	Homework: 50%   
	Attendance, Worksheets, and Participation: 10%
	Two "Midterm" Take-Home Exams: 10% each, 20% total
	Final Exam: 20%

Honor Code and Collaboration Policy

All students in this class are expected to abide by the Harvey Mudd Honor Code for work in this course. Collaboration on homeworks is permitted and encouraged. Here are the stipulations:

Use of laptops and portable devices in class...

As a courtesy to your fellow students and your instructor, please do not use laptops, iPads, mobile phones, etc. in class. If you genuinely need to use such a device in class, please talk to me and we'll find a way for you to do so.

List of Topics