Algorithms' Syllabus

This course will introduce you to fundamental algorithm design and analysis techniques. In addition to learning about a number of important classical algorithms, you will also gain experience designing new and extending existing algorithms. This experience will include analyzing various algorithms' computational efficiency and applying them to a variety of interesting real-world computational problems.

Is This Course for You (a.k.a Prereqs!)?

The short answer is Yes! -- as long as you've met a few basic requirements. Much of our time will be spent carefully analyzing algorithms using mathematical induction, recurrence relations, and summation techniques. Hence, Math 55 is a non-negotiable prerequisite. On some homeworks there will also be programming assignments that may be solved in a high-level language of your choice (e.g., C, C++, Java, Pascal, SML, Matlab). Thus, CS 60 and CS 70 (if registered as CS 140) or Math 131 (if registered as Math 168) are also required.

Text

Introduction to Algorithms, 2nd Edition by T. Cormen, C. Leiserson, R. Rivest, and C. Stein.

Homework

Typically, there will be two homework sets per week, one assigned per lecture. You will receive a hardcopy of each homework set in class on the day it is assigned (LaTeX and ps files can also be downloaded here). Homework is due at the beginning of the following lecture.

Since learning by example is such a powerful tool in this course, I will provide a model solution (hardcopy) for each homework assigned, typically on the day you turn yours in. I am also eager to provide high-quality assessment of your work. Should you have an issue with a particular grade, I encourage you to bring it up with me, but only after you have familiarized yourself with the solution I handed out in class.

Tuesday assignments will typically be shorter, e.g. 2-3 problems, worth approximately 20-35 points, and Thursday assignments will typically be longer and more involved, e.g. 5-6 problems, worth approximately 65-80 points. Students can typically spend anywhere between 1.5 to 4 hours on a Tuesday assignment and 3.5 to 8 hours on a Thursday one. How much time you'll need to spend will depend upon how strong your discrete mathematics and proof skills are, what kind of study group you arrange (these are encouraged!), and how effective you are in seeking help early and often.

With respect to getting help, a few words are in order. Don't sit around spinning your wheels indefinitely as you work on a problem. There are simply too many crucial homeworks assigned in this class for such a strategy to pay off. It is your responsibility to come get help when you need it: come to office hours, hit up one of the graders, etc. In turn, it is my responsibility to make sure that I don't just "give you the answer", but rather guide you to find it for yourself, which means that you can be certain that seeking help will always be a strengthening -- as opposed to an disenfranchising -- experience. It is also my responsibility to ensure that help is readily available to you, i.e. if you're having scheduling problems, contact me and we'll set aside a time especially for you!

I encourage you to use LaTeX to writeup solutions -- although you are not required to do so on any but the very first one (HW1a) -- because it is such a valuable skill. Requiring you to use LaTeX on the first assignment is an experiment that I am trying out in response to student input from last year. (In particular, students have observed that it would have really helped them later on in the course if they had bothered to learn LaTeX earlier on, when they had more free time.) Instructions for using LaTeX in this class are here.

Exams

The primary reason I give exams is to assess your grasp of the course material within a calm and unhurried test-taking environment. For this reason, I am leaning towards untimed take-home exams. I expect to give two midterm exams and a final. The exact dates and procedures for taking these exams will be announced in class as the semester progresses.

Collaboration

Collaboration with other students is allowed -- in fact, I encourage it! Collaboration includes discussing approaches to solving a problem, walking through your course notes together, etc. Copying written solutions from any source (such as person, a text book, or a web page) is not allowed. If you do decide to collaborate on homework, I only insist that you indicate the names of any of the people with whom you have discussed your approach. No collaboration is allowed on any exam. Needless to say, all parties, including off-campus students, are expected to follow the Harvey Mudd Honor code.

Topic Outline