CAS CS 330 - Fall 2006 - Introduction to Analysis of Algorithms

Syllabus

Course Description

Official Description: Examines the basic principles of algorithm analysis; techniques of efficient programming; analysis of sorting and searching; graph algorithms; string-matching algorithms; matrix algorithms; integer and polynomial arithmetic; the fast Fourier transform; and NP-hard and NP-complete problems.

Elaboration: This course is about the forest behind the trees: we will focus on the big-pictures ideas that are more readily apparent when one does not need to deal with syntax, pointers, compiling, code structure, etc. We will avoid dealing with such details not because they are unimportant, but because without getting the big picture right there is no point in dealing with the details. While we don't expect each of you to use every algorithm we learn in this class, we do expect each of you to carry away the ability to step back and analyze the big picture. We also expect this class to provide you with useful techniques and skills (not the least of which is mathematical maturity).

The tentative schedule is as follows, at approximately one topic per week:

  1. Running times and recurrence relations
  2. Sorting (lower bounds and how to beat them)
  3. Median, rank and order statistics
  4. Balanced trees, order statistic trees, and interval trees
  5. Greedy algorithms for optimization problems; Huffman coding (2 weeks)
  6. Dynamic programming for optimization problems (2 weeks)
  7. Arithmetic algorithms; Euclid's GCD; application to error-correcting codes
  8. Graph algorithms and their applications
  9. Optimization problems that seem hard (introduction to NP)
  10. Approximation algorithms
  11. Max-flow/min-cut

Prerequisites and Related Courses

The class assumes working knowledge of CS 112 and MA 293. (MA 242 or CS 232) and (MA 294 or CS 235) are co-requisites. If you don't have the prerequisites, talk to us before deciding to continue with this class. If you encounter some math you don't know, try looking in the appendix to the textbook. If you don't find it there, ask the TF or one of the instructors.

Staff

This course has two instructors. Professor Steve Homer will teach most of the course, with the exception of the first two weeks and the week of October 30, which will be taught by Professor Leo Reyzin. The teaching fellow is Debajyoti Bera. Contact information follows. We encourage you to come to our office hours. If you need to talk to us but can't make the office hours, please send one of us email. We check it a few times on a weekday and at least once on a weekend.

Texts

Introduction to Algorithms, by Cormen, Leiserson, Rivest and Stein. Available at the BU bookstore. The book has a homepage with an errata page.

Meetings and Other Communication

Lectures are Tuesdays and Thursdays 2:00-3:30 in MCS (111 Cummington) B33. Lecture attendance is required. Students are responsible for all material covered in lecture. Some lecture material may not appear in the text.

You should have also selected the lab when you registered (if not, add it to your schedule!). Labs, which meet Fridays 2-3 in MCS B33 and are headed by the TF, are a required part of the course. If you are unable to attend lab, you must send email to Debajyoti beforehand.

The class has a home page: http://www.cs.bu.edu/~homer/330/. Important news about the class will be posted there. On occasion, we will send out email to the class list, so please log in to csa and type csmail -a cs330. "I didn't get your email" won't ordinarily be an acceptable excuse.

Assignments and Tests

There will be about 7 homeworks (mainly problem-solving, no programming) (50%), a midterm (20%) and a final (30%). We reserve the right to deviate from this formula in unusual cases (in particular if your exam performance is significantly lower than your homework performance, we will consider your homework grade less trustworthy).

The midterm will be in class some time in October (probably between October 17 and 26). The final exam will be scheduled by the registrar.

Late Homeworks Policy

Every semester we have to manage extension requests from students ("I have a cold," "I have a job interview," etc.). In order to save everyone's time, we will allow you to manage your own extensions. The extension policy is as follows. Each student is credited six late days. If a homework is submitted late, the appropriate number of late days is deducted (rounded up--a fractional day counts as a full day). Because homework solutions will be discussed in lab, the absolute latest you may submit a homework is by lab time on Friday (homeworks will usually be due on Tuesdays). You may use these days without penalty, except that it will probably take us longer to get the graded homework back to you if you submit it late. However, if you run out of late days, or submit your homework after solutions have been discussed in lab, your late homework will not be accepted, and you will receive a zero for it.

Exceptions to this late policy will be granted only in extremely serious circumstances (such as extended hospital stays) that we hope none of you will have. So use your late days wisely, and don't expect us to make exceptions if you use them all up without good reason (the whole point of having the policy in the first place to remove the need for exceptions). Plan for that unexpected cold or headache on the last assignment.

Important Dates

Last day to drop without a W grade: Friday, October 6, 2006.
Last day to drop with a W grade: Friday, October 27, 2006.

Academic Honesty

Plagiarism is any attempt to represent the work of another as one's own. Read the BU CAS Academic Conduct Code and follow it. Do not misrepresent your work or aid others in doing so. If you are sharing your homework write-up with your classmate, you are, in my eyes, as culpable as your classmate. Collaboration policy for this class is as follows. The last point is particularly important: if you don't make an honest effort on the homework but always get ideas from others, your exam score will reflect it.

If you violate this policy (e.g., by looking at another person's write-up or finding a solution on-line), you can avoid being treated as a cheater by acknowledging your violation in your write-up: you probably won't get much credit for the problem, but at least you won't have lied to me and violated BU policy on academic honesty. Remember, citing your sources properly is often the easiest way out of trouble.

Violations of academic honesty result in an automatic failing grade and are reported to the Academic Conduct Committee (ACC). The ACC often suspends or expels students deemed guilty of plagiarism or other forms of cheating. We have seen it happen.

If you are uncertain as to whether or not a particular kind of interaction with someone else constitutes illegal collaboration or academic dishonesty, please ask us before taking any action that might violate the rules.