Administrative Details
Instructor:
Aravind
Srinivasan
Office: AVW 3263, Phone: 301-405-2695
Instructor's office Hours: Tue, Thu 11AM-noon in AVW 3263, or by
appointment (please email Aravind)
Half-TAs: Karthik Abinav Sankararaman and Pan Xu
TA Office Hours: Fri 3-5PM in AVW 4185
Course Time and Location: Tue, Thu
3:30-4:45, CSIC 1120
Course Webpage:
http://www.cs.umd.edu/class/spring2018/cmsc651/index.html
Announcements
Please register on the Piazza webpage for this class. All primary communication will happen on this site.
Approximate schedule:
The approximate schedule thus far is
here (make sure to reload this page).
Course Goals
Our primary goals are as follows:
- Use the standard class-format to:
- teach the basics of (modern) 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 online and distributed
computing, large data-sets & streaming data, and MapReduce-like
programming models.
- Foster independent and group-based learning via a project.
- 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.
Tentative List of Topics
- Randomized Algorithms and Probabilistic Analysis
- Quick recap of reductions, P and NP, NP-completeness, and other complexity classes including PSPACE, #P, and Exponential time
- Divide and conquer, Greedy algorithms, Dynamic Programming, and Local search using more advanced examples
- For self-study: A quick introduction to continuous and convex optimization (gradients, convexity, optimization using Lagrange multipliers): Boyd-Vandenberghe book
- Linear Programming (LP), duality, Matroids, Matching, and Flows
- Approximation algorithms, the primal-dual method, and rounding techniques
- A brief overview of Machine Learning and continuous optimization
- SVD and other basic linear-algebraic algorithms in Data Science
- Online algorithms (especially in the context of Internet advertising and E-commerce)
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)
- Project: 15%
- Free discussion is strongly encouraged; students will receive 5% credit
for coming to Aravind's office hours by April 15th to discuss
class-related material.
- Take-home mid-term (given out March 14th, due by noon on March 16th): 20%
- In-class final exam (May 18th, 10:30-12:30): 30%. You will be allowed
to bring one 8.5 x 11-inch sheet with anything written on both sides of it;
other material will not be allowed.
Course Evaluation
Students are strongly encouraged to complete their course evaluations toward
the end of the semester;
please do so at the CourseEvalUM
website.
Excused Absences
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.
Academic Integrity
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
http://www.studentconduct.umd.edu.
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)."
Web Accessibility