Home Page for CMSC451 Design and Analysis of Computer Algorithms, Fall 2014
CMSC451 Design and Analysis of Computer Algorithms, Fall 2014
Class Venue and Time: CSI 3120, TuTh 12:30-1:45pm
Office: AVW 3263, Phone: 301-405-2695
Instructor's Office Hours: Tue 10-11AM, Thurs 11AM-12PM in AVW 3263, or by
appointment (please email Aravind)
TA: Brian Brubach (bbrubach AT cs.umd)
TA Office Hours: Mon, Wed 10:30-11:30AM in AVW 4103
Course Time and Location: Tue, Thu
12:30-1:45, CSIC 3120
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 on the class web page.
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. 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%
- Project: 10%
- Midterm: 25%
- Date: Tuesday, Oct. 14, 12:30-1:45PM in class
- Final exam: 40%
- Date: Friday, December 19, 1:30-3:30PM
- 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.
See the university's policy on medically-necessitated absence from class. The
"Major Scheduled Grading Events" for this course are the mid-term and
final exams; students claiming an excused absence from these events
must apply in writing and furnish documentary support (such as from a
health-care professional who treated
the student) for any assertion that the absence qualifies as an excused
absence. The support should explicitly indicate the dates or times the
student was incapacitated due to illness. Self-documentation of illness
is not itself sufficient support to excuse the absence. An instructor
is not under obligation to offer a substitute assignment or to give a
student a make-up assessment unless the failure to perform was due to
an excused absence.
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.
The University of Maryland, College Park has a nationally recognized
Code of Academic Integrity, administered by the Student Honor Council.
This Code sets standards for academic integrity at Maryland for all
undergraduate and graduate students. As a student you are responsible
for upholding these standards for this course. It is very important for
you to be aware of the consequences of cheating, fabrication,
facilitation, and plagiarism. For more information on the Code of
Academic Integrity or the Student Honor Council, please visit
To further exhibit your commitment to academic integrity, remember to
sign the Honor Pledge on all examinations and assignments: "I pledge on
my honor that I have not given or received any unauthorized assistance
on this examination (assignment)."