15-750: Course Policies for Graduate Algorithms, Spring 2020

Description

The course covers a broad set of topics in algorithms design and analysis. The goal is to cover tools and algorithms that give students the ability to (a) recognize which tool or method to apply to problems, (b) to become reasonably proficient at using these tools, and (c) to be able to reason about the correctness and performance of the resulting algorithms. The course webpage for this semester will list the tentative list of topics to be covered; these will include basic graph algorithms, randomized algorithms, hashing and streaming, flows and linear programming, convex optimization, and linear algebraic algorithms.

This is a graduate breadth (aka star) course aimed at students who have learned some basic undergraduate algorithms material (probably not 15-451, see the FAQ), and want to get a broader/deeper understanding of algorithms. (Students aiming to specialize in theoretical CS should consider 15-850 Advanced Algorithms instead.)

Syllabus

Here is a very tentative schedule (speadsheet format) for the course. Broadly, we want to cover:

Some basic graph algorithms: trees, matchings
Hashing and Randomization.
Streaming algorithms (a.k.a. algorithms for big data)
Flows and Cuts, Graph Partitioning
Linear Programming and LP Duality
Convex Programming
Continuous Optimization, gradient descent, multiplicative weights
High-dimensional data: nearest neighbor, dimensionality reduction.
Random walks.
Online algorithms
NP completeness and Approximation Algorithms

Previous versions of the course (taught by Gary Miller) are available here: S19 , S18 , and S17. The topics this year will be a bit different.

Effort and Criteria for Evaluation:

Your grade will depend on HWs, exams, and class participation.

We have ~7 HWs (including HW0), roughly every other week. Some may be solved with collaboration, some solved individually.
There will be one midterm and one final exam. Both will be during the class times.
We expect you to attend the lectures, and will give you some points for attendance/class participation.

The rough breakdown will be 32% each for the exams (midterm and finals), 32% for the homeworks, and 4% for attendance/class participation in lecture or Piazza.

Homeworks:

Homeworks are due at 11:59pm on the due date. They must be submitted via gradescope. We will not accept late HWs, barring exceptional circumstances. However, each individual student has a single 48 hours pass. This pass can be used to extend the deadline for one homework by up to 48 hours. You are not allowed to split this pass to use among several HWs.

Collaboration policy: On solo homeworks (like HW0) you must solve all the problems yourself. You must not discuss the problems with others. On other collaboration HWs (like HW1) we will permit groups of two people (3 if you must). We require that collaborations be "whiteboard" collaborations, you can discuss problems and solutions with your group on a "whiteboard". After this each person should go away and write their own solutions, which they then submit. That is, collaboration should be limited to *talking* about the problems, so that your write-up is written entirely by you. No written work should be shared. Of course, you must also list all members of your group. In all cases if you use any resources not on the course webpage, you should cite them.

Prerequisites:

We will assume basic knowledge in algorithms, probability, and linear algebra. We urge you to brush up on them if you are rusty --- we can point you to books or lecture notes on them. The use of linear algebra and probability is ubiquitous across all of CS, just like the use of algorithms. Learning those topics will not be a waste of your time, whether you take this course or not. See below for some resources to help you brush up.

Textbook:

There is no mandatory textbook for the course. We will provide lecture notes, or reading from books. Some good books include:

The Design and Analysis of Algorithms by Dexter Kozen: CMU Access via SpringerLink.
Algorithm Design by Kleinberg and Tardos: CMU library, slides by Kevin Wayne.
Algorithms by Dasgupta, Papadimitriou, and Vazirani (DPV): CMU library, author's site.
Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein (CLRS): CMU library with links to e-copy.
Randomized Algorithms by Motwani and Raghavan: CMU Access to e-copy.
Algorithms by Jeff Erickson: online PDF.
Design and Analysis of Computer Algorithms by Aho, Hopcroft, and Ullman: CMU library.

We assume basic discrete mathematics (counting, basic probability, basic graphs theory, basic linear algebra): some resources include:

(15-251) Great Theoretical Ideas in CS: slides from our undergraduate course.
(15-151) Discrete Mathematics: our undergraduate course page (contains the textbook).
Mathematics for Computer Science by Lehman, Leighton, and Meyer: lecture notes from MIT.
A useful stackexchange thread on good linear algebra sources (with links to several free texts).
A primer on matrices (by Shephen Boyd), and a linear algebra review (from Stanford's cs229, by our own Zico Kolter) with some multivariate calculus too.
Some helpful videos on linear algebra (thanks Anil!).

FAQs:

Q: I am struggling with the homework: what should I do?
A little struggle in doing the homework is expected (and healthy), since you're probably learning something new. However, if you are struggling a fair bit, or if the struggle is unpleasant for you, come talk to us.

Q: I am on the wait-list: will I get in?
We hope everyone who wants to take the class will get in. (Usually some students are "shopping around" in the first couple weeks, and things settle down after that.) Just come to the lectures, and we will try to get clear the wait-lists soon. OTOH, if you are on the wait-list because you have too many credits, or are enrolled for a course with a conflicting time-slot, you should fix those issues yourself. Update (Nov 24): we currently have a long waiting list. I don't know if we will even be able to let in all the students who are serious about the course. If you are risk-averse you may want to consider other options. We will keep you updated.

Q: I have taken 451/651 at CMU, can I take this course?
Most likely not. Our undergraduate algorithms course (recent versions: S18, S19) contains fairly advanced material, and 750 will have non-trivial overlap with it. If you still feel you want to take 15-750, please talk to us first.

Q: I am a CS UG. Will 15-750 count towards the algorithms/complexity concentration?
No. See here.

Q: I am an undergraduate who's taken 210 and 251. Can I take 750 instead of 451?
You should not. The undergrad course 15-451 has been designed for the UG curriculum, and you should take that course.

Q: I am interested in theoretical CS, and want a challenging graduate algorithms course: what do you recommend?
This course (15-750) is a PhD star/breadth course. It aims at students whose primary focus is not theoretical CS, but who want to learn more about algorithms beyond what you learned in your standard undergraduate algorithms course. If you want more depth than 15-750, check out 15-850: Advanced Algorithms (recent versions: F18, S17). It is aimed at beginning Ph.D. and advanced MS/undergraduate students who want to focus on theoretical CS. We will likely teach 15-850 in F20.

Accommodations for Students with Disabilities:

If you have a disability and are registered with the Office of Disability Resources, ~~I encourage you to use their online system to notify me of your accommodations and~~ come and see me to discuss your needs with me as early in the semester as possible. We should discuss how to make things work out. I will work with you to ensure that accommodations are provided as appropriate. If you suspect that you may have a disability and would benefit from accommodations but are not yet registered with the Office of Disability Resources, I encourage you to contact them at access@andrew.cmu.edu.

Make-ups for the midterm/final must be arranged at least one week in advance, barring extreme situations. Please make sure to document any health problems you might have.

Academic Integrity

Honesty and transparency are important features of good scholarship. On the flip side, plagiarism and cheating are serious academic offenses with serious consequences. If you are discovered engaging in either behavior in this course, you will earn a failing grade on the assignment in question, and further disciplinary action may be taken. For a clear description of what counts as plagiarism, cheating, and/or the use of unauthorized sources, please see the University Policy on Academic Integrity and the Carnegie Mellon Code on Academic Integrity.

For each HW, we will specify if it is a solo HW (like Hw0) or if collaboration is allowed (and the rules for such collaboration). If you are allowed to collaborate, your submission must contain the names of person(s) you collaborated with. You are not allowed to look at online resources or books when solving the homeworks (except for resources provided on the course webpage).

Your Health & Well-being

Part of making sure that you enjoy the course involves taking care of yourself. Do your best to maintain a healthy lifestyle this semester by eating well, exercising, avoiding drugs and alcohol, getting enough sleep and taking some time to relax. This will help you achieve your goals and cope with stress.

If you or anyone you know experiences any academic stress, difficult life events, or feelings like anxiety or depression, we strongly encourage you to seek support. Counseling and Psychological Services (CaPS) is here to help: call 412-268-2922 and visit http://www.cmu.edu/counseling/. Consider reaching out to a friend, faculty or family member you trust for help getting connected to the support that can help.

Back to course main page.
Maintained by Anupam Gupta