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, and so 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

The official text for this course is Introduction to Algorithms, 2nd Edition by T. Cormen, C. Leiserson, R. Rivest, and C. Stein. A fair bit of material is presented in simpler ways during lecture, however. Course notes are thus invaluable; pre-punched handouts to aid in note taking will be provided at the beginning of class. You should buy a 3-inch wide 3-ring binder for archiving this material.

Attendance

I will keep an attendance record. Simply email me in advance if you have a compelling reason to be late or absent. Lateness is defined as coming into class anytime after the lecture has begun. (Lecture will typically begin with a discussion of the most recent homework set.) Never fear---lecture will never begin before 2:45 :-), but I will make every effort to begin each lecture within a few minutes thereafter.

Grading Scheme:

The course is graded along two dimensions: participation and exams. I weight participation slightly more than exams because I believe it is the best indicator of how well you truly understand the material.

Participation contributes 60 percent to your final grade and consists of:

Exams comprise the other 40 percent, weighted as follows: Within the A to D range, grading will be relatively linear. However, if your lack of participation exceeds any of the following threshholds, I reserve the right to not pass you on the grounds of unacceptable participation:

Homework

Typically, there will be two homework sets per week (one per lecture). I will pass out hard copies of assignments during the lectures in which they are assigned. Assignments are due at the beginning of the following lecture (except for extra credit, which is due on Fridays at 6pm). Tuesday assignments tend to be shorter (2-3 problems, ranging from 15-40 points), while Thursday assignments tend to be longer and more involved (5-6 problems, ranging from 65-80 points). Provided that you always make a significant effort (turning in a reasonable solution for every homework set) your two lowest homework scores will be dropped before calculating your total homework score. Extra credit, a great mechanism for improving your score, will be accepted provided you've already turned in the non-extra-credit portion of a homework set.

I encourage everyone to use LaTeX when writing up their solutions, although this is only required on the first two assignments (HW1a and HW1b). Information on using LaTeX is available at this link. Per-assignment LaTeX and ps files are available this link.

Hard copy solutions will be provided for homeworks after their due dates. Solutions serve three purposes: to provide examples of high-quality technical writing (proofs, run-time analyses, pseudo-code, etc.); to identify equally good approaches (when multiple solutions exist); and to facilitate grading. You can help contribute to these solutions by bringing any errors that you find to my attention. In addition, please let me know if a solution you have developed needs to be added to the list! These solutions are for your eyes only; by accepting them, you agree (via the HMC Honor Code) not to distribute them.

High-quality assessment of your homework performance is crucial; if you have an issue with a particular grade, please let me know. I simply ask that you familiarize yourself with the hard copy solution beforehand. Please also let me know how your graders are doing, e.g. Are their comments useful? Is there anything they can do to make their comments more valuable? etc. They often ask me for feedback; your opinions matter.

Expect to spend between 1.5-4 hours on a Tuesday assignment and 3.5-8 hours on a Thursday one. How much time you'll need to spend will depend upon how strong your discrete math and logic skills are, how well you can debug code, and what kind of study group you arrange (these are encouraged; see the Collaboration section). One of the most important things you can do to minimize the amount of time you spend mastering algorithms material is to seek help early and often. As a rough guide: if your homework score drops below 85 percent (on average, excluding extra credit), odds are you're not coming to office hours enough. I recommend reading carefully through each assignment (and the prior assignment's solution) within 2-4 hours after class, so that you have plenty of time to seek help when needed.

A mistake several students have made in the past is sitting around spinning their wheels indefinitely, "working" on a problem without making progress. There are simply too many crucial problems assigned for such a strategy to pay off. As my student, it is your responsibility to get help when you need it: come to office hours (arrange a special meeting if necessary), meet with one of the graders, etc. In turn, it is my job to not just "give you the answer", but rather to guide you towards finding a solution on your own. My desire is for help-seeking to be an empowering experience.

Exams

The reason I give exams is to provide a measure of how well you understand the material in a calm, solo, unhurried environment. For this reason, I lean towards giving untimed take-home exams. All exams, with the exception of a single page (double-sided is okay) crib sheet that you have prepared in advance, are closed book.

I will let you keep your graded midterms. Again, these are for your eyes only; by accepting them, you agree (via the HMC Honor Code) not to distribute them.

A take-home final will be handed out during the designated time slot for this class. Your solutions will be due that Friday at 5pm. You are free to open the final exam and read it whenever you like. However, once you open the exam, the only access you will have to outside material is your pre-prepared crib sheet. Taking the exam begins when you start writing up your answers. At this point, you will have 3 hours to complete your exam and turn it in. Although I will keep your graded final exam, I encourage you to drop by my office to take a look at it if you wish.

Special Arrangements

I am willing to consider special circumstances that justify deviating from one or more of the policies outlined above (e.g. suppose the material comes so easily to you that you'd rather be doing something else during class; your grandmother died and so you need an extension; etc). Please come talk to me; decisions will be made on a case-by-case basis.

Collaboration

Collaboration with other students on homeworks is encouraged! Simply indicate on your solutions with whom you have collaborated. Collaboration includes things like: discussing approaches to solving a problem; walking through your course notes together; etc. Neither of the following is ever allowed: copying written solutions from any source (such as person, a text book, or a web page) or collaboration on an exam. All parties, including off-campus students, are expected to follow the Harvey Mudd Honor code.

Agreement

Please print your name and sign below. Your signature indicates that you have CAREFULLY READ this syllabus and AGREE (VIA THE HMC HONOR CODE) TO ABIDE BY THESE CONDITIONS. Thanks---I look forward to having you in Algorithms this semester!


Your name, signature, and date:

Topic Outline