Links: Canvas, Piazza, syllabus (pdf)
For lecture, recitation and office hour times and Zoom links, see Canvas or Piazza.
Become familiar with standard algorithms and their merits and drawbacks in practice.
Learn to prove an algorithm’s correctness and rigorously analyze time and space complexity.
Practice adapting and combining algorithms to solve real problems.
Learn strategies for designing new algorithms for emerging applications.
Learn to communicate clearly about algorithm design, correctness, and complexity analysis.
This course is delivered synchronously, fully remote. All lectures, recitations, and office hours will take place live on Zoom with the meeting links posted to Canvas. All resources and information will be posted to Canvas and the course website, and we encourage discussions on Piazza. Assignments will be submitted online through Canvas or Gradescope, and quizzes and exams will be administered online.
This course uses mastery-based grading, sometimes known as standards-based grading. For a brief introduction see e.g. the first 6 minutes of this video.
You will have opportunities to demonstrate mastery each week on homework and an online quiz, on midterm exams in weeks 8 and 13, and on a final exam. This means that it is possible to attain mastery for most standards either (i) in homework and a quiz (without passing any exam), (ii) entirely in exams (a midterm plus the final), or (iii) a mixture of these modalities. We believe this offers you (our students) the best chance of achieving a high grade, as you can focus on the types of assessment that suit you. See Section 3 in the full syllabus for more details.
Week 1. | Proof by induction, loop invariants, insertion sort |
Week 2. | Asymptotic analysis, start divide and conquer algorithms |
Week 3. | Divide and conquer algorithms, recurrence relations, mergesort, quicksort |
Week 4. | Average case analysis, randomized quicksort, hash tables |
Week 5. | Greedy algorithms I: introduction, Huffman codes |
Week 6. | Greedy algorithms II: graph search including breadth-first search and Dijkstra's algorithm, start Greedy algorithms III: minimum spanning trees including Prim's and Kruskal's algorithm |
Week 7. | Greedy algorithms III and IV: finish minimum spanning trees, max flow min cut |
Week 8. | Review and midterm |
Week 9. | Dynamic programming I: introduction, Fibonacci numbers, rod cutting |
Week 10. | Dynamic programming II: the Bellman–Ford algorithm |
Week 11. | Dynamic programming III: edit distance |
Week 12. | Complexity theory: definitions of P, NP, etc., reductions |
Week 13. | Review and midterm |
Week 14. | Complexity theory: further discussion, approximation algorithms |
Week 15. | Final review and non-examinable bonus material |
In this class, if you are sick or quarantined you can request deadline extension for homework and online quizzes. As all teaching in this course is fully remote you are welcome to attend as much as you can though your quarantine period. Lectures are recorded so you can catch up when you are well again. A “doctor’s note” is not required to request a deadline extension, and you are not required to disclose confidential health information to course staff. If you have been exposed to a confirmed or presumed positive COVID-19 case you should prioritize self-isolation over administrative tasks such as obtaining a doctor’s note, and seek medial advice only if you experience symptoms. This reduces the load on our healthcare resources and allows treatment of the sick to be prioritized.
All students enrolled in a University of Colorado Boulder course are responsible for knowing and adhering to the Honor Code. Violations of the policy may include: plagiarism, cheating, fabrication, lying, bribery, threat, unauthorized access to academic materials, clicker fraud, submitting the same or similar work in more than one course without permission from all course instructors involved, and aiding academic dishonesty.