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.
Your grade will depend on HWs, exams, and class participation.
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.
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.
There is no mandatory textbook for the course. We will provide lecture notes, or reading from books. Some good books include:
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.
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.
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.