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

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, linear algebraic algorithms, compression, and algorithms for error correction.

Syllabus

Here is a tentative schedule for the course. Broadly, we plan to cover:
  1. Some basic graph algorithms: trees, matchings
  2. Hashing and Randomization
  3. Streaming algorithms (a.k.a. algorithms for big data)
  4. Flows and Cuts, Graph Partitioning
  5. Linear Programming and LP Duality
  6. Convex Programming
  7. Continuous Optimization, gradient descent, multiplicative weights
  8. High-dimensional data: nearest neighbor, dimensionality reduction
  9. Random walks
  10. Online algorithms
  11. NP completeness and Approximation Algorithms
  12. Compression
  13. Error Correcting Codes

Course Policies

Effort and Criteria for Evaluation:

Your grade will depend on HWs, exams, and 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. For each homework, there will be a two-day (48 hours) no-questions-asked extension. Students can use this extension for any valid reason without having to ask the instructors. We do not plan to provide additional extensions (barring exceptional circumstances).

We're happy with clear legible handwritten homeworks, to start off. However, if legibility turns out to be a problem later, we may revisit this decision.

Collaboration policy: On the solo homeworks (like HW0) you must solve all the problems yourself. You must not discuss the problems with others. On the 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.

You must list all members of your group. In all cases, if you use any resources other than the course notes/slides, you must cite them.

Grading: The homework grading will be a combination of self-grading plus grading by the course staff, as follows. We will release sample solutions for the homeworks soon after the due date. Students then grade their own homeworks, assigning grades to the problems. We grade some fraction of the problems, and use our grades and yours to assign you a score for the entire HW. Here's an example: suppose you gave yourself 8,7,10,3 for the four problems, each problem being worth 10 points. We randomly choose the first two, and gave you 9 and 7 on them. This would mean we would scale up each of your self-assigned scores by a factor of (9+7)/(8+7), capping each score at their maximum score of 10, thereby getting a total of 8.53+7.47+10+3.2=29.2.

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:

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


FAQs:


Accommodations for Students with Disabilities:

If you have a disability and are registered with the Office of Disability Resources, We encourage you to use their online system to notify us of your accommodations and discuss your needs with us as early in the semester as possible. We 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, We 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.

Diversity in the Classroom

In this course, we strive to treat everyone with respect, and provide everyone with the best learning experience we can. We believe that diversity, equity, and inclusion should be our goals, not only because they fuel excellence and innovation, but because these are just. Your suggestions are encouraged and appreciated. Please let us know ways to improve the effectiveness of the course for you personally, or for others.

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 and Rashmi Vinayak