CSCI 3014: Algorithms. Fall 2020

Lectures

Links: Canvas, Piazza, syllabus (pdf)

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

Course objectives

• 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.

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.

• There are 24 content standards (listed below) and 1 participation standard.
• For each content standard you will have several opportunities (usually at least 4) to demonstrate that you have mastered that standard. To be awarded a standard, you must demonstrate mastery twice.
• You earn points towards your participation standard by doing the online quizzes, by attending recitation, and by posting high quality content to Piazza. If you earn enough points, you are awarded the participation standard.
• Your final grade is determined by how many standards you are awarded (i.e. demonstrate mastery of at least twice).

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

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.