CAS CS 330 - Spring 2016 - Introduction to Algorithms

Syllabus


Official Course Description

This course 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.

Prerequisites: The class assumes working knowledge of CS 112 and CS 131 (or MA 293) as a prerequisite. CS majors typically complete their Group B coursework (any two of CS 132, CS 235 and CS 237) before taking CS 330, and that is recommended. If you don't have the prerequisites, please talk to the instructor before deciding to continue with this class.

Course Handouts Page

Our Piazza page (includes lab handouts)

Lectures

Lecture A1: Tues/Thurs 11 - 12:30 PM, CAS 313.

I expect students to come to class, and to come on time. While the class is large, class participation and questions will be encouraged. Also, while our textbook will be very helpful, they are an imperfect substitute for in-class learning, which is the fastest (and easiest) way to learn the material. If you miss a class, please get the notes and work through the material with a fellow student.

Discussion Labs

Lab A2: Mon 12-1PM, MCS B31
Lab A3: Mon 1-2PM, MCS B19
Lab A4: Mon 4-5PM, MCS B19
Lab A5: Mon 9-10AM, MCS B21

Labs will be an invaluable part of the course involving interactive problem-solving sessions, tips on homework questions, and supplemental material not covered in lecture. Attendance is mandatory and will be taken.

Instructor

Prof. John W. Byers
Homepage: http:// www.cs.bu.edu/fac/byers
Email:    byers @ cs . bu . edu [preferred]

Office Hours (in MCS 270):  Tues 3-4PM, Wed 1-3PM.
For technical questions beyond what Piazza can answer (see below), or when you are really stuck on a problem.
During office hours, if it's not too busy, I'll answer my phone at 617-353-8925.
Other times, I generally let phone calls go to voicemail. Please send email instead.

Teaching Fellows

Hannah Flynn (TF) and Sridevi Suresh (TA)
Email:     {hmflynn, sridevis}@bu.edu

Office Hours (all held in EMA 302, next to ugrad lab):
Tuesday: 8-10PM (SS)
Wed 3-5PM (HF)
Wed 5-6PM (SS)
Thu 4:30 - 5:30PM (HF)

Hannah and Sridevi will lead the discussion sessions. The objective is to reinforce the concepts covered in the lectures through problem-solving, and provide clarifications regarding the homework assignments. The purpose of the office hours of the Instructor and Teaching Fellows is to answer specific questions or clarify specific issues. Office hours are not to be used to fill you in on a class you skipped or to re-explain entire topics. Office hours are scheduled at times to provide help to students who start the homework before the last minute.


Textbook

Algorithm Design, by Kleinberg and Tardos. ISBN 0-321-29535-8.

Communications:

We will be using Piazza for all discussions outside of class. The system is highly catered to getting you answers to your questions fast and efficiently from classmates, the TFs, and myself. Rather than emailing questions to the teaching staff, I encourage you to post your questions on Piazza. We also encourage you to post answers to other students' questions there (but obviously, not answers to problems on the problem sets!). Our class page is located at: https://piazza.com/bu/spring2016/cs330/home. Please go there to sign up today. We will also use Piazza to post announcements, homework assignments, etc.

Grading and Attendance

The course grade will break down as follows: Last day to drop without a W: Feb 23. With a W: April 1. Incompletes for this class will not be granted.

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.

Exams:    There will be one eighty minute in-class midterm held during the middle of the semester before spring break, very likely on Thursday, March 3. The cumulative final will be held during the normal two-hour final exam slot. Please make your spring break and end-of-semester travel plans accordingly.

Homework Submission:     Assignments will typically be due Thursdays at 7PM. You must submit a hardcopy no later than 7PM in the drop box on the first floor of the MCS building, near the CS department office. From the CS office, walk toward the shorter end of the hallway, and turn right. Drop box is immediately on your right. Assignments must go *in the box*, not on the shelves above, which is where we will *return* assignments.

As you likely already know, assignments requiring substantial creativity can take more time than you expect, so plan to finish a day early.

Late Policy:    During the course, you will have 2 chances to turn in assignments up to 22 hours late with no penalty, with Friday 5PM *in the drop box* as the cutoff (hard deadline). Any assignment arriving between Thursday 7PM and Friday 5PM is considered late.

Regrading Procedure:     If, after reviewing your solution, you still believe a portion of your homework was graded in error, you may request a regrade. Please write, on a PostIt, the problem number and a brief description of the incorrect deduction, stick it on your homework, and give it to Prof. Byers for a regrade. Note that when we regrade a problem, your score may go up or down.

Attendance: It is expected that you will attend lecture and the laboratory section for this course. Attendance will be taken in labs. 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 disruptive to have students flowing in throughout the class period. Moreover, when students are at a borderline between grades, I will factor in attendance before making a final determination.


Topics

We will no doubt drift from any formal plan, but a rough schedule of where we are headed is provided in the roadmap below. Each of the topics will take roughly one week, except as noted. A more detailed and continually updated schedule will be maintained on the main course homepage.

  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; fast multiplication of integers, matrices, and polynomials (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


Academic Conduct

Academic standards and the code of academic conduct are taken very seriously by our university, by the College of Arts and Sciences, and by 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 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 scores (accounting for the majority of your grade) will reflect it.