Home Page for CMSC451 Design and Analysis of Computer Algorithms, Fall 2016
CMSC451 Design and Analysis of Computer Algorithms, Fall 2016
Class Venue and Time: MCB 1207, TuTh 9:30-10:45am
tl;dr -- Students: please add
yourselves to the Piazza page for
the class! We will use Piazza extensively.
Office: AVW 3263, Phone: 301-405-2695
Instructor's Office Hours: Tue 12:30-2:30 in AVW 3263, or by
appointment (please email Aravind)
TAs: Meir Friedenberg (meir AT terpmail),
Karthik A. Sankararaman (kabinav AT cs), and Pan Xu (panxu AT cs)
TA Office Hours: Thu 2:15-3:15 (Meir), Wed 11:15-12:15 (Karthik),
and Fri 3:30-5:30 (Pan);
all in AVW 4101 or 4103 (may change from week to week)
Course Time and Location: Tue, Thu
9:30-10:45, MCB 1207
Lecture Notes and Related Resources
There is no required textbook. Instead, we will use, among others, the
following excellent publicly-available resources:
We thank the authors for these very-helpful resources.
Aravind's Pledge to the Students
Your education is very important to me, and I respect each of you regardless
of how you do in the class. My expectations of you are that you attend class
and pay full attention, and give enough time to the course.
I strongly encourage you to ask questions in class,
and to come to the office hours (mine or the TAs')
with any further questions. We can have a
very enjoyable educational experience if you pay attention
in class, give sufficient time to our course,
and bring any difficulties you have promptly to our attention. I look forward
to our interaction both inside and outside the classroom.
This course presents the fundamental techniques for designing efficient computer algorithms, proving their correctness,
and analyzing their complexity. General topics include the following;
also, given the expected needs of Data Science (Big Data), we will
place added emphasis on probability/statistics, sublinear
algorithms, and linear algebra.
CMSC 351 is the prerequisite. Each student is expected to know the basic concepts of programming (e.g. loops, pointers, recursion), discrete mathematics (proof by induction, sets), simple data structures (lists, stacks, queues, trees, heaps), and calculus (logarithms, differentiation, integration).
We will assume knowledge of the basic algorithm-analysis techniques
covered in CMSC 351.
All course materials, including the homework and project, will be
posted on Piazza.
The coursework will consist of 5-7 homework
assignments, a small project and two exams (one midterm and a
comprehensive final). Homework problems will be mathematically oriented.
- Graph algorithms
- Randomized algorithms
- Basic algorithm design paradigms such as
- Dynamic programming
- Greedy algorithms
- Lower bounds
- Approximation algorithms
- Algorithms for Data Science (i.e., Big Data)
Homeworks are to be turned in at the start of class on the due date. Since
homework solutions will be handed out on the day the homework is due,
no late homeworks will be accepted.
All homeworks are to be done independently, with no help from the web or other sources. If you have questions, please talk to the TA or the Instructor.
Assignments are to be written up neatly.
Please staple your homework. It is your responsibility to make sure
that you pick up all homeworks and handouts. All course information and
handouts will be available in Piazza.
The topics, times and order listed in the syllabus next are tentative
and are subject to change:
- Graph exploration: 4-5 lectures
- Randomized Algorithms: 2 lectures
- Divide-and-Conquer algorithms: 4 lectures
- Greedy algorithms: 4 lectures
- Dynamic programming: 5 lectures
- Lower Bounds: 1 lecture
- NP-completeness and Intractability: 2 lectures
- Approximation Algorithms: 2 lectures
- Algorithms for Data Science: 2 lectures
Topics, Schedule, and Online Resources
This course will use Piazza as a tool for communication between students, TA, and Instructor. The schedule for the next few lectures will always be
available on Piazza; we will also have an "inverted classroom" to some extent,
where you will do assigned reading at home, with more problem-solving done in
class. You are
very strongly encouraged to bring your questions to office hours. In addition, you may consider checking Piazza and posting questions there. Students are also encouraged to contribute answers to questions posed by others.
Grading, Homework, and Exams
Final grades will be based on homework assignments, the project, the midterm exam, and the comprehensive final exam with relative weights as follows:
- Homework: 25% (Your lowest HW score will be
- Project: 10% (Due by 11:59PM EST on Nov 30th,
- Midterm: 25%
- Date: Thursday, Oct. 13, 9:30-10:45AM in class
- Final exam: 40%
- Date: Thursday, December 15, 8-10AM
- Both exams will be held in the classroom, and will both be closed-book, closed-notes.
Students are strongly encouraged to complete their course evaluations;
please do so at the CourseEvalUM
website when it is ready.
Academic Accommodations for Disabilities
Any student eligible for and requesting reasonable academic accommodations
due to a disability is requested to provide, to the instructor in office
hours, a letter of accommodation from the Office of Disability Support
Services (DSS) within the first two weeks of the semester.
Excused Absences, Academic Integrity, and Additional Info.
Please see the university's policies on various important issues.