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 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.
Prof. Dora Erdos Email: edori @ bu . edu
Office Hours Wed 9:30 - 10:30 (by appointment), Thurs 12:30 - 2:30 in MCS 288.
Prof. Evimaria Terzi Email: evimaria @ bu . edu
Office Hours Tues 2:30 - 4:00, Wed 1:30 - 3:00 MCS 280.
TF Hannah Catabia Email: catabia @ bu . edu
Office Hours Wed 2:30 - 3:30, Thurs 2:30 - 4:00 in EMA 302 (undergrad lab).
TF Konstantinos Sotiropolus Email: ksotirop @ bu . edu
Office Hours Wed 5:00 - 7:00, Thurs 6:00 - 7:00 in EMA 302 (undergrad lab).
The class will be co-taught by Professors Terzi 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 room CAS B18.
Lecture B1: Tues/Thurs 9:30 - 10:45 AM, room CAS B18.
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.
All labs are in MCS XXX.
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/spring2019/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 .
5% attendance and participation in lecture, lab, and on Piazza
25% in-class midterm exam (most likely in-class on Thursday 3/7).
35%
comprehensive
final, in
the
normal
exam slot
for classes
in our respective
time blocks.
Last day to drop without a W: 2/16. With a W: 4/5. 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, March 1. The
cumulative final will be held during the normal two-hour final exam
slot:
TBD for students in the A1 lecture and
TBD for students in the B1 lecture.
Both in room XX.
Please make your travel plans
accordingly.
Homework Submission:
Assignments will typically be due Thursdays at 11:59PM electronically via
Gradescope.
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.
Sign up to Gradescope:
You can sign up by visiting
our Gradescope page. The
registration code for CS330 is M5KVD6 Regrade policy:
You may request a regrade via Gradescope, NOT through email. One of the
staff will look at your request and adjust your grade if appropriate. We
reserve the right to change your grade up or down.
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.
Optimization problems for which no polynomial time algorithms are
known; introduction to NP
Local search and heuristic approaches
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.
Details and examples on Academic Integrity can be
found
here
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.