Home Page for CMSC451 Design and Analysis of Computer Algorithms (Section 0101), Spring 2019

CMSC451 Design and Analysis of Computer Algorithms (Section 0101), Spring 2019

Instructor: Aravind Srinivasan
Class Venue and Time: ESJ 1202, TuTh 11AM - 12:15PM

tl;dr -- Students: please add yourselves to the Piazza page for the class! We will use Piazza extensively.

Administrative Details

Instructor: Aravind Srinivasan
Office: IRB 4164, Phone: 301-405-2695
Instructor's Office Hours: Tuesdays 2:30-4:30 in IRB 4164, or by appointment (please email Aravind)
TAs: Suhas Amireddy, Aounon Kumar, Jerry Peng, Leonidas Tsepenekas, George Tong, and Pan Xu
TA Office Hours: Mon (10-11, 2-4), Tue 4-6, Wed 2-3, Thu 1:30-2:30, and Fri 2-3 at AVW 4101/4103
Course Time and Location: Tue, Thu 11-12:15, ESJ 1202
Course Webpage: http://www.cs.umd.edu/class/spring2019/cmsc451-0101/index.html

Textbook, Lecture Notes and Related Resources

The required textbook is Algorithm Design by Kleinberg and Tardos. We may also occasionally use, among others, the following excellent publicly-available resources:

Kevin Wayne's lecture notes from Princeton
Jeff Erickson's Algorithms book from Urbana-Champaign
Avrim Blum, Anupam Gupta, and Danny Sleator's lecture notes from Carnegie-Mellon

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.

Course Overview

This course presents the fundamental techniques for designing efficient computer algorithms, proving their correctness, and analyzing their complexity. General topics include the following.

Recap of the math background
Graph algorithms
Basic algorithm design paradigms such as
- Divide-and-conquer
- Dynamic programming
- Greedy algorithms
Lower bounds
NP-completeness
Approximation algorithms
Randomized algorithms
Quantum Algorithms
A brief statement on sustainability: Since Information Technology has become a significant consumer of energy and a major source of greenhouse gases, we will also cover the energy-efficiency of algorithms. The growth rate of the electricity use of all forms of information-technology use in the US is more than twelve times the growth rate of the total US electricity usage. Hence, algorithms designed with an eye toward their resource use and energy footprint hold out the possibility of making a good dent in energy costs and in greenhouse-gas emissions. We will hence also study models for algorithms that are more resource-efficient.

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 homeworks, will be posted on Piazza. The coursework will consist of 5-6 homework assignments and three exams (two midterms and a comprehensive final). Homework problems will be mathematically oriented.

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. You can discuss homeworks with other students, but with no help from the Web or other sources. Assignments are to be written up independently by each student, regardless of collaboration. If you have questions, please talk to the TA or the Instructor. It is your responsibility to make sure that you pick up all homeworks and handouts. All course information and handouts will be available on Piazza.

Grading, Homework, and Exams

Final grades will be based on homework assignments, the two midterm exams, and the comprehensive final exam with relative weights as follows:

Homework: 30% (Your lowest HW score will be dropped)
Midterm 1 (Mar 5, 2019; 11-12:15): 15%
Midterm 2 (Apr 18, 2019; 11-12:15): 15%
Final exam: 40%
- Date: Thursday, May 16, 8-10 AM
All exams will be held in the classroom. Grades will follow a curve; in my typical 451 classes, the median score received a B- or C+, but this can change slightly.

Course Evaluation

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. Specifically, any student who needs to be excused from a mid-term or the final exam, must provide written documentation of the illness from the Health Center or from an outside health-care provider.

Web Accessibility