CS 330 - Spring '17 - 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 an instructor
before deciding to continue with this class.
Instructors and Teaching Fellows
Prof. John W. Byers
Homepage: http:// www.cs.bu.edu/fac/byers
Email: byers @ cs . bu . edu [preferred]
Office Hours: Tues 1:30-2:30 PM (by appointment) and Wed 2-4 in MCS 295B
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.
Prof. Dora Erdos
Email: edori @ bu . edu
Office Hours Tues 3-5 and Thurs 2-3 in MCS 288.
TF Maryam Ghasemi
Email: ghasemi @ cs . bu . edu
Office Hours Wed 4-5 and Thurs 4-6 in EMA 302 (undergrad lab).
TF Mark Lemay
Email: lemay @ bu . edu
Office Hours Tues 5-6 and Wed 5-7 in EMA 302 (undergrad lab). Bonus tutoring hour: Tues 4-5.
The class will be co-taught by Professors Byers and Erdos. On any given lecture date, one of the two
instructors will deliver the lecture for both the A1 and B1 sections. The TFs will lead the discussion sessions.
The objective is to reinforce the concepts covered in the lectures through problem-solving, and to provide clarifications and
guidance on the homework assignments.
The purpose of the office hours of the Instructors and Teaching Fellows is to answer specific
questions or clarify specific issues. Your fastest route to get an answer to most questions
is via Piazza. 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 the
most help to students who start the homework before the last minute.
Lectures
Lecture A1: Tues/Thurs 11 - 12:15 AM, KCB 101.
Lecture B1: Tues/Thurs 9:30 - 10:45 AM, KCB 101.
We 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, it is 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 9:05 - 9:55AM (Mark)
Lab A3: Mon 10:10 - 11:00AM (Mark)
Lab A4: Mon 12:20 - 1:10PM (Mark)
Lab B2: Mon 1:25 - 2:15PM (Maryam)
Lab B3: Mon 4:40 - 5:30PM (Maryam)
Lab B4: Mon 2:30 - 3:20PM (Maryam)
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. We will post labs on Piazza in advance --
please read before coming to lab. Attendance is mandatory and will be taken.
Lab solutions will be posted on Monday evening after all labs conclude.
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 instructors.
Please do not email questions to the teaching staff -- post your questions on Piazza instead.
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/spring2017/cs330/home.
Please go there to sign up today.
We will also use Piazza to post announcements, homework assignments, labs and lab solutions, etc.
Grading and Attendance
The course grade will break down as follows:
-
35% homework assignments, due on Thursdays 1/26, 2/9, 2/23, 3/16, 3/30, Tuesday 4/18, and Tuesday 5/2.
-
5% attendance and participation in lecture, lab, and on Piazza.
-
25% in-class midterm exam (most likely in-class on Thursday 3/2).
-
35% comprehensive final, in the normal exam slot for classes in our respective time blocks.
Last day to drop without a W: Feb 23. With a W: March 31. 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, either Java or Python is fine.
As you likely already know, assignments requiring substantial creativity
can take more time than you expect, so plan to finish a day early.
Exams:
There will be one eighty minute in-class midterm held during the
middle of the semester before spring break, on Thursday, March 2. The
cumulative final will be held during the normal two-hour final exam slot:
Tuesday May 9, 9-11AM for students in the 9:30AM lecture and
Thursday May 11, 12:30 - 2:30PM for students in the 11AM lecture. Both in KCB 101.
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.
LET ME REPEAT: Assignments must go *in the box*, not on the shelves
above, which is where we will *return* assignments.
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 one of the
instructors 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. We ask that you please 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, we 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.
- Course overview. Stable matching, implementation, running times.
- Graphs and basic graph algorithms (2 weeks)
- Greedy algorithms for optimization problems (2 weeks)
- Divide-and-conquer; fast multiplication of integers, matrices, and polynomials (2 weeks)
- Dynamic programming for optimization problems (2 weeks)
- Max-flow/min-cut
- Optimization problems for which no polynomial time algorithms are known; introduction to NP (2 weeks)
- Lower bounds and approximation algorithms
- Local search and heuristic approaches
- 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.
- You are encouraged to
collaborate with one another in studying the textbook and lecture material.
- As long as it satisfies the following conditions, collaboration on the homework assignments is permitted and will not reduce your grade:
- Before discussing each homework problem with anyone
else, you must give it an honest half-hour of serious thought.
- You may discuss ideas and approaches with other students in the class, but not share any
written solutions. In other words, the writeups you submit must be entirely your own work.
You must also acknowledge clearly in the appropriate portion of your solutions
(e.g., at the top of your writeups) people with whom you discussed ideas for that portion.
- You may get help from TFs and undergrad assistants for the class for specific problems.
Don't expect them to do it for you, however.
- You may not work with people outside this class (but come and talk to us if you
have a tutor), seek on-line solutions, get someone else to do it for you, etc.
- You are not permitted to collaborate on exams.
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.