CSCI 3014: Algorithms. Fall 2020

Lectures

Section 100
Ewan Davies
TTh 9:35–10:50am
See Canvas for Zoom link
Section 200
Charles (Charlie) Carlson
TTh 2:20–3:35pm
See Canvas for Zoom link

Links: Canvas, Piazza, syllabus (pdf)

For lecture, recitation and office hour times and Zoom links, see Canvas or Piazza.

Course objectives

Course structure

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.

Assessment and grades

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.

Standards

  1. Loop invariants and proof by induction
  2. Asymptotic notation
  3. Asymptotic analysis I: correctly writing down equations for counting operations given pseudocode with simple independent loops
  4. Asymptotic analysis II: correctly writing down equations for counting operations given pseudocode with nested dependent loops
  5. Recurrence relations I: write down correct recurrence for a recursive algorithm
  6. Recurrence relations II: solve by unrolling
  7. Recurrence relations III: solve by tree method
  8. Divide and conquer: important principles (when does it apply and when not)
  9. Average case analysis (of quicksort), compare to worst-case behavior
  10. Hash tables: collisions, load factor, when to apply vs balanced binary tree
  11. Greedy algorithms I: exchange argument for correctness (mastery can be demonstrated either using interval scheduling or Huffman coding)
  12. Greedy algorithms II: examples where greedy algorithms do not work
  13. Shortest paths I: breadth-first search for unweighted graphs
  14. Shortest paths II: Dijkstra’s algorithm (or Bellman–Ford which we cover later)
  15. Minimum spanning trees I: safe and useless edges
  16. Minimum spanning trees II: the generic algorithm and at least one of Kruskal’s or Prim’s algorithms
  17. Max flow min cut I: residual graph
  18. Max flow min cut II: applying max flow (reducing to max flow, e.g. bipartite matching)
  19. Dynamic programming I: principles (when does it apply and when not)
  20. Dynamic programming II: rigorous understanding of a simple 1-dimensional example (Fibonacci numbers or rod cutting)
  21. Dynamic programming III: write down recurrence for computing local solution in a complex example (e.g. edit distance)
  22. Dynamic Programming IV: order of subproblems and topological sort
  23. Dynamic Programming V: backtracking (recovering the optimal solution not just its value)
  24. Complexity theory: basic definitions (P, NP, NP-hard, NP-complete, reduction)
  25. Participation standard

Schedule

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

Health

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.

Honor code

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.