Lecturer: Steven Homer (homer@bu.edu)

Office: MCS 226

Office Hours: Tuesday after class for about 30 minutes in my office in MCS,

Thursday 2:30 - 3:30 in my office, and by appointment.

Teaching Fellow Nathan Dang (ndang@bu.edu)

Nathan's office hours are in the MCS building, room 117E.

His hours will be 10:30am - 11:30am both Wednesday and Friday

Lectures

The CS 630 class lectures will be on Tuesdays and Thursdays from 11:00am - 12:15pm, EST (Boston time) in room CAS 224.

The first lecture is on Thursday, September 2.

Text

Introduction to Algorithms by Cormen, Rivest, Leiserson and Stein, Edition 3, MIT Press

There will also be some other supplementary books and notes which will be given to you on-line and used from time to time.

There is a short bibliography of more advanced algorithm texts referenced below.

Discussion Sections All students are expected to enroll in, attend and participate in a weekly discussion section. These sections will be held on Wednesdays and begin on September 8.

The 4 section are:

Section A2: 1:25pm - 2:15pm in room CAS 227

Section A3: 2:30pm - 3:20pm in room EPC 208

Section A4: 3:35pm - 4:25pm in room MCS B37

Section A5: 6:30pm - 7:20pm in room NIP 920

All Eastern Standard Time (EST)

Sections are required and important to the class as often new information, hints on homework/exms, and answers to problems will be discussed there.

Section will be run by the TF's and and are required once a week for each student that is enrolled. Students living in Boston and will meet their section in one of the sections above. Note that Section 5 is taught remotely for students living outside of the U.S.

Prerequisites and Related Courses

CS 630 is the core graduate algorithms course for the MS program in Computer Science.

Its only strict course prerequisite is CS 330 or a similar introductory algorithms course.

Also required is a working knowledge of the basic mathematical skills needed to design, write and analyze algorithms, and to measure and express their efficiency.

List of topics and schedule of classes and reading

Some of the topics planned for CS 630 this semester include

Basic operations on integers, complex number, polynomials, matrices and other algebraic structures and applications.

-the Fast Fourier Transform

-linear programming and its applications

-review of elementary complexity theory including P, NP-complete and NP-hard problems

-approximation methods for hard problems

-basic discrete and continuous optimization methods

-probabilistic algorithms, specifically those related to finding cuts in graphs, polynomial identity testing and maximum matching.

-algorithms for large datasets and graphs; clustering using k-means and k-median, cuts in graphs, duality and others

-If time permits, one special topic to be determined later, possibly quantum computing, parallel algorithms, or games theoretic algorithms

Background

CS 630 is a "continuation " of CS 330 and the background material and basic algorithmic techniques covered in CS 330 are assumed in this class. Missing background must be studied on your own or learned by taking CS330 if needed.

To begin CS 630 we will very briefly review a couple of the central topics already studied in CS330. Students are responsible for knowing these prerequisite undergraduate topics.

Other background material in algorithms includes

-basic algorithms concerning sorting and searching, lists, graphs, algebraic operations, NP completeness, and heuristic algorithms for combinatorial problems

-basic algorithm using special data structures such as linked lists, specialized matrices, trees, and graphs,

-algorithmic techniques including exhaustive search algorithms, greedy algorithms, recursion (aka divide and conquer), exhaustive search, dynamic programming and maximum flow methods

-the background necessary to analyze the efficiency of these algorithms including basic discrete mathematics, logic, probability and linear algebra.

-Also required is a working knowledge of the basic mathematical skills needed to design, write and analyze algorithms.

If this material is unfamiliar, you will have to spend some time doing supplementary reading or sitting in on the prerequisite classes (CS 330) or even some classes which 330 depends on.

Grading

There will be five or six graded homework assignments, 1 quiz, and a final exam The grade will be determined by: HW - 25%, 1 quiz/midterm - 25%, and a final - 50%. The lowest homework grade will be dropped. There will be no extra credit given, even for more work.

Missing exams policy: Students missing an exam will not be allowed to make it up unless they show evidence of an illness (usually by having a doctor's letter), or they let the instructor know of the absence at least a week before the exam and can justify this absence.

No incompletes will be given.

Late policy: A penalty of 10% per day may will be assessed for late homeworks. Furthermore homework will only be accepted up until the answers are posted on-line. You may request an extension of the homework due date once (or maybe twice) during the term.

Collaboration Policy

You are strongly encouraged to collaborate with one another in studying the lecture materials and preparing for homework, quizzes and exams.

You may discuss ideas and approaches to the assignments with others but such discussions should be kept at a general level, and should not involve actual details of the answers or code. You must complete and write the actual solutions on your own.

Academic Misconduct

We will assume that you have read and understood BU's Academic Conduct Code, see https://www.bu.edu/cas/current-students/phd-mfa-students/academic-policies-and-conduct-code/ Undergraduates should see https://www.bu.edu/academics/policies/academic-conduct-code/

Class Recording Policy

All class sessions will be recorded for the benefit of registered students who are unable to attend live sessions due to time zone differences, illness or other special circumstances. Recorded sessions will be made available to registered students ONLY via their password-protected account. Students may not share such sessions with anyone not registered in the course and may not repost them in a public platform. Students have the right to opt-out of being part of the class recording. Please contact your instructor or teaching assistant to discuss options for attending the course in such cases.

Covid-19 Issues (which hopefully won't arise this term) These are not formally part of the syllabus but they will be discussed in class. (to appear)