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.
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.
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.
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/fall2017/cs330.
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, most likely 9/14, 9/28,
10/12, 11/2, 11/16, 12/7.
5% attendance and participation in lecture, lab, and on Piazza
25% in-class midterm exam (most likely in-class on Thursday 10/19).
35%
comprehensive
final, in
the
normal
exam slot
for classes
in our respective
time blocks.
Last day to drop without a W: 10/10. With a W: 11/10. 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.
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 on Thursday, October 19. The
cumulative final will be held during the normal two-hour final exam
slot:
at XX (updated when dates available) for students in the 9:30AM lecture and
at XX for students in the 11AM lecture.
Both in room XX.
Please make your travel plans
accordingly.
Homework Submission:
Assignments will typically be due Thursdays at 11:59PM electronically via
websubmit.
Late Policy:
During the course, you will have 2 chances to turn in assignments up to 24
hours late with no
penalty, with Friday 11:59PM as the cutoff (hard deadline).
Any assignment arriving
between Thursday 11:59PM and Friday 11:59PM is considered late.
Topics
This list is tentative. The exact topics covered as well as the
corresponding textbook chapters will be updated. Slides and other handouts
can be found on piazza.
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.