Home Page for CMSC651 Analysis of Algorithms, Fall 2013
CMSC651 Analysis of Algorithms, Fall 2013
Class Venue and Time: CSI 2120, TuTh 11-12:15
Office: AVW 3263, Phone: 301-405-2695
Instructor's office Hours: Tue, Thu 9-10AM in AVW 3263, or by
appointment (please email Aravind)
Grader: Khoa Trinh (khoa AT cs.umd)
Course Time and Location: Tue, Thu
11-12:15, CSIC 2120
The course will have good overlap with its Fall 2012 cousin. I thank
Neal Young for their help with
background and exercises related to
Our primary goals are as follows:
- Use the standard class-format to:
- teach the basics of algorithms, and
- use an "inverted classroom" format where students will do some assigned
reading/work at home, with related problem-solving (e.g., HW solutions)
done in class.
- Expose the students (in the HWs and in class) to different
models such as parallel, multi-core, online, and distributed
computing, large data-sets & streaming data, and MapReduce-like
- Foster independent and group-based learning via a semester-long
reading and problem-solving project: students will read portions of
Welzl's notes and the
- Encourage participation and the airing of ideas: 5% of the class credit
will be for introducing oneself and having
a technical discussion during office hours.
Topics, Schedule, and Online Resources
Please click here for a lecture-by-lecture
schedule and online resources (notes and videos).
Grading, Homework, and Exams
The grading will be as follows -- students will form groups of typical size
three for the first two items below:
- Homework based on class material: 30% (your lowest HW score will be dropped)
- Homework based on Welzl's notes and on the
Arora-Hazan-Kale survey: 15%
- Free discussion is strongly encouraged; students will receive 5% credit
for coming to Aravind's office hours before the end of October to discuss
- Take-home mid-term: 20%
- Emailed on Oct 18th, due in class on Oct 22nd
- Will include everything covered in class and given as required reading
up to (and including) Oct 15th,
as well as Chapters 1, 2, 3, and 4 of Welzl's notes
- In-class final exam, 8-10AM on Dec 16th in our classroom: 30%
- The final covers all of the course,
Chapters 1, 2, 3, and 4 of Welzl's notes, and up to the end of Section 3.1
- Students can bring their own notes, Welzl's notes, Arora-Hazan-Kale, and
all the material assigned as reading ("required" or not) in class
Homework and Mid-Term
Homework 1, due Sept 17th.
Homework 2, due Sept 26th.
Homework 3, due Oct 8th.
Homework 4, due Oct 17th.
HW based on Welzl's notes, due Nov 7th.
Mid-Term, due Oct 22nd.
Homework 5, deadline extended to Nov 7th.
Homework 6, due Nov 21st.
Homework related to AHK, due Dec 12th.
Students are strongly encouraged to complete their course evaluations;
please do so at the CourseEvalUM
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)."