Welcome to the home page for the Computer Science Department's Graduate Algorithms course CLA CS 530. This is the starting point for online course information and documentation.
CS 530 is the central algorithms course in the computer science M.S. Program. It serves as a core graduate breadth course in theory. It is the successor to the undergraduate algorithms course, CS 330, and has this course as its main prerequisite. In CS 530 students will learn fundamental algorithm design and analysis methods at the graduate level. The following list of topics provides access to information concerning the instructor, the TF and the class, as well as pointers to other information you may need.
Steven Homer (homer@bu.edu)
Office: MCS 283
Phone: 353-8927
Office hours: Tuesday 11:30-12:30 and Wednesday, 1:15-2:15, and by appointment.
Teaching Fellow: William Blair (wdblair@bu.edu)
Office: Room 204
Office hours are: Thursday 1-2 and 3-4, and by appointment
Most recent CS 530 Course News.
Assignments: All assignments will be turned in using Gradescope software (gradescope.com). Have a look at their system and some of their demos.
You can sign up for gradescope in 530 using our course code which is M4DXDY.
You can use the url piazza.com/bu/fall2019/cs530 to sign up for CS 530's version of Piazza.
Most recent class assignment:
Discussion Sections:
The 4 section are all on Friday.
Section A2: 9:05am - 9:55am in CAS 228
Section A3: 10:10am - 11:00am in KCB 103
Section A4: 11:15am - 12:05pm in CAS 216
Section A5: 12:20pm - 1:10pm in CAS 228
Please select one of the lab sections to attend each week.
Quiz 2 will be in class on Tuesday, November 19.
HW 1, HW 2 , HW 3 (very brief), HW 4
Some extra material and notes from class:
A few pages for the Garey and Johnson NP-Completeness book about the bin packing problem which will be a good start in reading about the class discussion of this problem.,
There are many places to read about the details and proofs of Christofides Algorithm. You can see a nice set of slides with a full example of full example of how the algorithm works here, together with some sketchy proofs.
Here is reading on a few randomized algorithms which will be discussed in class. The reading is from Chapters 1 and 7 of Randomized Algorithms by Motwani and Raghavan.
Here is a short example of the simplex algorithm.