Welcome to the home page for the Computer Science Department's
Graduate Algorithms course GRS CS 630.
This page is the starting point for online course information and documentation.
You should also look at the syllabus for the class for further information about this semester's
class.
CS 630 is the central graduate algorithms course in the
MS program in Computer Science in CAS.
It is a successor to the undergraduate algorithms course, CS 330,
and has the 330 course as a prerequisite. The course begins where CS 330
leaves off.
In CS 630 students will learn fundamental algorithm design and
algorithm analysis covering more advanced topics at the graduate level.
The CS 630 Syllabus contains the prereqisites for the
class, a list of topics we may cover, the grading scheme for the class and some other
important course information.
Lecturer: Steve Homer (homer@bu.edu), Office: MCS 226, Office Phone: 353-8927
a Office Hours: Tuesday after class for about 30 minutes in my office in the CS department.
Thursday 1:30 - 2:30 in my office.
and by appointment via email.
Class lectures will be held Tuesday and Thursday 11:00-12:15 in Room CAS 224.
Teaching Fellows: Nathan Dang (ndang@bu.edu) and Yida Xin (yxin@bu.edu)
Nathan's office hours are in the basement of the MCS building, room B21. His hours will be 6:00-7:00pm on both Tuesday and Wednesday, both given in room MCS B21.
Yida Xin's office hours will be 4-5pm on Wednesdays and Fridays 9:30-10:30am. Yida's office hours will meet remotely via Zoom. The Zoom url will be posted soon. In the meantime you can email him.
All lab section are held on Wednesdays. (See the syllabus for times and locations.)
Most recent class assignment :HW 5
All assignments (except HW 0) will be turned in using Gradescope software (gradescope.com). If gradescope is new to you, have a look at the gradescope system and some of their on-line demos.
You can sign up for gradescope in 630 using our course code which is 74PN26.
You can also use the url piazza.com/bu/ to sign up for CS 630's version of Piazza.
Previous assignments: HW 0, HW 1, HW 2, HW 3, HW 4
Some brief answers to homework assignments and the quizes: HW 1 Answers, HW 2 Answers, HW 3 Answers.
Extra Reading:
These 4 pages are from the Algorithms book by Dasgupta, Papadimitriou and Vazirani.
They formed the basis of lecture 2 (September 7) about efficient binary multipication .
Here is 2-approximation algorithm for max-cut we discussed in class on October 7.
You can find some reading (for HW 3) about randomized algorithms here.
Here are a couple of places on-line where you can learn about bin packing in a manner similar to problem 3 of Homework 4.
The first is a short youtube video
and the second is a few pages of notes on the bin packing problem.
This includes many of the simple approximate bin packing algorithm like first fit and best fit.
Here is a few pages of notes explaining Christofides Algorithm which is a 1.5 approximation for the Euclidean TSP problem.