CAS CS 330 - Fall 2011 - Introduction to Algorithms

Course Overview

1. Course overview. Stable matching, implementation, running times.
2. Graphs and basic graph algorithms (2 weeks)
3. Greedy algorithms for optimization problems (2 weeks)
4. Divide-and-conquer; Integer multiplication (2 weeks)
5. Dynamic programming for optimization problems (2 weeks)
6. Max-flow/min-cut
7. Optimization problems for which no polynomial time algorithms are known; introduction to NP (2 weeks)
8. Lower bounds and approximation algorithms
9. Local search and heuristic approaches
10. Randomized algorithms, including median-finding and order statistics

Class meeting time:   Tues/Thurs 3:30 - 5,   CAS 316.

Lab meeting times:    Mon 11-12 (GCB 201), Mon 12-1 (CAS 233) and Mon 3-4 PM (CAS 323B).

Course homepage:   http://www.cs.bu.edu/fac/byers/cs330.html

Staff

Instructor:  Prof. John W. Byers
Email (preferred): byers @ cs . bu . edu
Phone: 617-353-8925

Office Hours:    Mon 9:30 - 11AM and Wed 11-12:30AM, held in MCS 270 (John's office).

Teaching Fellow:  Sam Epstein
Email: samepst @ cs . bu . edu

Office Hours:    Tues 12-1, Wed 2-3, Thu 10-11, held in EMA 302 (next to ugrad lab).

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 us an email. We check it a few times on a weekday and usually at least once a weekend.

Prerequisites:    

The class assumes working knowledge of CS 112 and CS 131 (or MA 293). (MA 242 or CS 232) and (MA 294 or CS 235) are co-requisites. If you don't have the prerequisites, please talk to the instructor before deciding to continue with this class.

Textbooks:     The required textbook is:

• Algorithm Design, by Jon Kleinberg and Eva Tardos. ISBN #0-321-29535-8. The textbook is available at the B.U. bookstore and at online bookstores.

Workload:     Be forewarned -- the workload in this course will be moderately heavy. We will have seven assignments, plus or minus one, due roughly every other week. The majority of the assignments will consist of problem sets, but some of the problems will contain small-scale implementations and simulations, especially later in the semester. These can readily be done in a language of your choice -- for example, Java is fine.

Grading:     The course grade will break down as follows:

• 50% homework assignments (tentatively due on Thursdays 9/15, 9/29, 10/13, 10/27, 11/10, Tuesday 11/22, and Thursday 12/8).
• 20% in-class midterm exam (most likely in-class on Thursday 10/20).
• 30% comprehensive final (in the normal exam slot, 3-5PM, Friday 12/16).

Exams:     There will be one eighty minute in-class midterm held during the middle of the semester in mid October, probably Thursday, October 20. The cumulative final will be held during the normal two-hour final exam slot. Please make your end-of-semester travel plans accordingly. In the event of serious illness documented by a doctor's note, makeup examinations will be given orally.

Attendance:     It is expected that you will attend lecture and the laboratory section for this course. Some material covered in lecture and lab will not be covered by our textbooks. I also ask that you arrive in class on time, since it is highly disruptive to have students flowing in throughout the class period. When students are at a borderline between grades, I consider attendance and class participation in making a final determination.

Late Policy:     Homework assignments will be due Thursdays at the beginning of class. During the course, you will have a total of 3 late days to turn in assignments late with no penalty. Any given assignment must be turned in no later than one day late, i.e. Friday 3:30 PM is the cutoff. Fractions of late days are rounded up to the nearest whole day, so three hours late equals one late day. No additional time will be granted, nor will additional late submissions be granted. As you already know, solving challenging problems can take more time than you expect, so plan to finish a little early.

CAS Academic Conduct Code:     Academic standards and the code of academic conduct are taken very seriously by our university, the College of Arts and Sciences, and the Department of Computer Science. Course participants must adhere to the CAS Academic Conduct Code -- please take the time to review this document if you are unfamiliar with its contents.

Collaboration Policy:     The work that you submit must be your own original work and it is an act of plagiarism to represent the work of another as your own. For the problem sets, limited collaboration in planning and thinking through solutions to homework problems is allowed, but no collaboration is allowed in writing up solutions. You are allowed to work with one or two other students currently taking CS 330 in discussing, brainstorming, and verbally walking through solutions to homework problems. But when you are through talking, you must write up your solutions independently and may not check them against each other. There may be no passing of homework papers between collaborators; nor is it permissible for one person simply to tell another the answer. If you collaborate with one or two other students in the course in the planning and design of solutions to homework problems, then you must acknowledge the collaboration and supply their names on your submissions. Under no circumstances may you use solution sets to problems that may have been distributed in past years, nor the homework papers of students who have taken the course in past years, nor should you look up solution sets from other similar courses. If you are uncertain whether an action constitutes a violation of the collaboration policy, please come by to discuss the matter with me before you act.