CMSC 451: Design and Analysis of Algorithms

Spring 2013

Home | Syllabus/Homeworks | Schedule | Resources



Announcements

5/8 Koyel will have extra office hours from 10am-12pm on Monday.
Practice problems posted to Piazza.
Notes on periodic scheduling and reductions from SAT to CLIQUE and SAT to SUBSETSUM posted.
5/1 Notes on Finding an optimal VC.
No class on Friday. Please attend Tim Roughgarden's talk in CSIC1122 instead.
4/28 HW7 posted, due 5/8 at the beginning of class.
Details about the final posted under "Syllabus/Homeworks".
4/14 HW6 posted, due 4/24 at the beginning of class.
Samir's OH on 4/15 canceled.
4/5 Alternate proof to Kruskal's greedy alg
4/3 Homework 5 solutions
4/1 Notes to NIM games (from lecture 3/29) here.
3/17 Second midterm has been postponed to Monday, April 8.
HW5 due date has been extended to 4/03.
3/13 HW5 posted here, due 3/27 at the beginning of class.
3/06 No class due to campus closing (inclement weather).
HW4 posted here, due 3/13 at the beginning of class.
2/24 Practice midterm here.
Notes on matchings here (pages 39-40).
Dave Mount's 451 lecture notes here.
2/22 Notes on scheduling jobs to maximize profit.
Monday 2/25 will be a review for the midterm on 2/27.
Jessica has additional OH on Monday 2/25, 3-5pm, AVW1152.
Practice exam to be posted Sunday.
Graded homeworks and quiz to be returned Monday in class.
2/13 Jessica's OH changed to Tu 10-11a/F 12-1p for the rest of the semester.
HW3 posted here, due 2/20 at the beginning of class.
Notes on 2-edge connectivity.
2/6 HW2 posted here, due 2/13 at the beginning of class.
2/4 Jessica covering Samir's 2-3pm OH today in AVW1152.
2/1 Supplemental figure to HW1 Problem 3 (from KT).
CLRS text on strong connectivity.
1/30 HW1 posted here, due 2/6 at the beginning of class.
1/25 Samir's OH canceled 1/28.
Let me (Jessica) know on Monday if you are registered and did not receive the test email.
HW1 to be handed out in class Wednesday 1/30.
Proof that GS is man-optimal is in KT 1.1 and also here.
1/22 Welcome to CMSC451! Sign up for Piazza here.

General Course Information

Room and Time: 1121 Computer Science Instruction Center
MWF, 11:00 - 11:50am
Instructors: Jessica Chang (jschang at cs) and Samir Khuller (samir at cs)
TAs: Koyel Mukherjee (email: koyelm at cs) and Alex Golden
Office Hours: Jessica: Tu 10-11am, F 12-1pm, AVW1152
Samir: M 2-3pm, AVW4175
Koyel: Tu 3-5pm, AVW1152
Alex: Th 11-12pm, AVW1112

Course Description

This course presents the fundamental techniques for designing efficient computer algorithms, proving their correctness, and analyzing their complexity. General topics include graph algorithms, and basic algorithm design paradigms (such as divide-and-conquer, dynamic programming and greedy algorithms), lower bounds and NP-completeness.