Algorithms are steps or instructions for solving mathematically well-defined problems. This course covers the fundamentals of algorithms and various algorithmic strategies, including time and space complexity, divide and conquer algorithms, greedy algorithms, graph algorithms, dynamic programming, and P versus NP.
This is an intensive course that is core to the Computer Science degree. It builds heavily on the prerequisites of Discrete Structures and Data Structures. Many upper-level courses and many Computer Science careers rely heavily on Algorithms. This offering emphasizes proofs and written in-person assessment.
All resources, additional information, and course details will be posted on Canvas.
When you have questions:
Prerequisites:
Workload:
Motivation and content:
Learning objectives:
Text and resources:
Recitations are mandatory and attendance will be taken. To pass the class, you must be present for at least five (5) recitations during the semester. Any fewer than five recitation attendances results in an automatic failure of the course. No extenuating circumstances will be accepted, as you should plan to attend all ten (10) recitations. Quizzes do not count for recitation attendance.
Letter grades will be assigned using Standards-Based Grading. There will be 28 standards. Your final letter grade is determined by the number of standards you “achieve”. Each standard is achieved by solving problems on homework and/or exams as described below.
The standards are divided into seven topics. There are four standards per topic, where the fourth is a "challenge" standard involving harder problems.
| Topic | Description |
|---|---|
| A | Big-O and Complexity |
| B | Divide and Conquer |
| C | Graph Traversal |
| D | Greedy Algorithms |
| E | Max Flow |
| F | Dynamic Programming |
| G | Hash Tables and P vs NP |
The standards are:
| Topic | Number | Name | Description |
|---|---|---|---|
| A | 1 | Big-O and Complexity 1: Growth Rates | Sort functions by asymptotic growth rate. Identify O, Omega, Theta, o, omega relations. |
| A | 2 | Big-O and Complexity 2: Proofs | Prove statements of the form f = O(g). |
| A | 3 | Big-O and Complexity 3: Iterative Algorithms | Analyze time and space complexity of basic iterative algorithms, nested loops, etc. |
| B | 4 | Divide and Conquer 1: Induction | Prove theorems by numerical and/or structural induction. |
| B | 5 | Divide and Conquer 2: Algorithms | Construct and execute D&C algorithms; give counterexamples for incorrect algorithms. |
| B | 6 | Divide and Conquer 3: Recurrences | Analyze novel D&C algorithms; write down recurrences and their solutions. |
| C | 7 | Graph Traversal 1: Graphs and Trees | Use graph terminology; prove statements about graphs, trees, and paths. |
| C | 8 | Graph Traversal 2: DFS and BFS | Construct and execute graph traversal algorithms based on DFS and BFS. |
| C | 9 | Graph Traversal 3: Shortest Paths | Apply BFS and Dijkstra’s algorithm; identify complexity and failure points. |
| D | 10 | Greedy Algs 1: Algorithms | Construct and execute greedy algorithms; identify failures of greedy. |
| D | 11 | Greedy Algs 2: Proofs | Analyze novel greedy algorithms using exchange arguments; prove correctness. |
| D | 12 | Greedy Algs 3: Minimum Spanning Tree | Apply definition of MST; execute Prim’s and Kruskal’s algorithms; identify complexity. |
| E | 13 | Max Flow 1: Definitions | Apply definitions of flow, capacity, residual; identify valid and invalid flows. |
| E | 14 | Max Flow 2: Ford-Fulkerson | Execute the Edmonds-Karp algorithm on examples; identify complexity. |
| E | 15 | Max Flow 3: Reductions and Applications | Use max flow to solve related problems via reductions; prove correctness. |
| F | 16 | Dynamic Programming 1: Algorithms | Execute a given DP algorithm on examples; identify DP components and failures. |
| F | 17 | Dynamic Programming 1: Fill in | Given portions of a DP solution, complete the algorithm; justify correctness. |
| F | 18 | Dynamic Programming 3: Solve From Scratch | Solve DP problems without scaffolding; justify correctness. |
| G | 19 | Hash Tables | Analyze hash tables and random hashing processes; pigeonhole, birthday paradox. |
| G | 20 | P and NP 1: Definitions | Define P and NP, apply the verifier definition, relate to exponential time and brute force. |
| G | 21 | P and NP 2: NP-Completeness | Apply definition of NP-completeness; prove NP-completeness with reductions. |
| 22 | Challenge A | Challenge problems relating to Topic A. | |
| 23 | Challenge B | Challenge problems relating to Topic B. | |
| 24 | Challenge C | Challenge problems relating to Topic C. | |
| 25 | Challenge D | Challenge problems relating to Topic D. | |
| 26 | Challenge E | Challenge problems relating to Topic E. | |
| 27 | Challenge F | Challenge problems relating to Topic F. | |
| 28 | Challenge G | Challenge problems relating to Topic G. |
A standard is achieved by passing two (2) problems on that standard. During the semester, you will generally have four (4) opportunities to solve a problem on that standard. Each problem is graded pass/fail. If you pass at least two of the problems, you achieve the standard. One of these problems will be on homework. The other problems will be on quizzes and exams.
Example. Standard 1 is Big-O Notation 1: Compare Growth Rates. For this standard, you will have four opportunities to solve a problem during the semester:
Each of these problems will be graded pass/fail. If you pass at least two of these problems, then you achieve Standard 1.
Note. Once you achieve Standard 1, you do not need to solve any more problems on Standard 1. For example, if you pass the Standard 1 problem on both Homework 1 and Quiz 1, then you have already achieved Standard 1 at that point. You can skip the Standard 1 problems on Midterm Exam 1 and the Final Exam, as they will not help your grade any further.
Special standards. Because of their timing at the end of the course, some standards may only have three opportunities instead of four. This also applies to the Challenge standards. The Challenge standards are for more difficult problems and are available only on the exams. To achieve an "A" in the class, students must pass at least one challenge standard, since at least 22 standards are needed for an A.
Fairness statement. In this course, our goal is that every student has a fair opportunity to learn the material and a fair opportunity to demonstrate their understanding for a grade. If you face extenuating circumstances such as illness, you may not be able to take advantage of all the opportunities offered (e.g. you may miss a homework or an exam). However, you will still have opportunities to achieve the standards, because each standard has at least 3 and generally 4 opportunities to pass. The course builds in these redundant, additional opportunities so that even a student who misses some opportunities still has a fair chance to demonstrate understanding and earn a grade. It is up to you to take advantage of those opportunities.
Extenuating circumstances. In this class, no late work will be accepted and no make-up work will be offered. The grading structure automatically gives every student extra opportunities to achieve the standards, partially in case of extenuating circumstances. If you encounter an extenuating circumstance that prevents you from turning in a homework or attending an exam, you can still achieve the relevant standards at your other opportunities during the semester.
Example. Suppose that you are ill for an extended time early in the semester and miss Quiz 1 as well as Homework 3. This still leaves you with three opportunities to obtain a pass on Standards 1-4 (namely, Homework 1 or 2, the Makeup Exam, and the Final Exam) and two opportunities to obtain a pass on Standards 5-6 (namely, the Makeup Exam and the Final Exam). Only two passes are needed to achieve a standard, so you still have a full opportunity to achieve all of the standards in this case.
Highly extenuating circumstances. If you encounter challenging circumstances that may prevent you from passing the course with the given grading opportunities, such as a lengthy injury or illness, please contact the instructor as soon as possible to discuss your situation. In such cases, it is unfortunately usually the case that the student should drop the class, as it usually means that the student will not have the opportunity to learn the material sufficiently during this semester in order to be able to demonstrate understanding and pass the class.
The class will have weekly homework assignments, a number of in-recitation quizzes, two Midterm Exams, and a Final Exam.
Find a full and up-to-date schedule of assignments on Canvas.
Quiz and recitation logistics: The quizzes and exams will be in-class (or in-recitation for the quizzes), written with pen and paper, with absolutely no electronic devices, notes, or aids allowed. For exams, you will be sent a room assignment for where to take the exam.
Homework must be typeset in LaTeX and submitted on Gradescope as a single PDF. Pages must be assigned on Gradescope correctly. Images of diagrams may be included in the LaTeX submissions, but all text and math must be typeset. Late homework will not be accepted. Gradescope will close the submission at the exact time of the due date.
Collaboration policy. Students may collaborate to discuss the homework problems and the solutions. Students must write up solutions themselves in their own words.
External resource policy. An external resource is anything not provided on the course Canvas page or anyone not part of the course staff. Students may use external resources to understand course material in general. Such resources include books, notes, websites, and AI tools (beware: see the warning below). Students may not use external resources to seek an answer specifically to a homework problem as asked. This includes pasting the question into an AI tool or chatbot. In addition, students must write up solutions themselves in their own words. Students may use tools, including AI tools, for formatting and LaTeX assistance but not for producing the content or wording their solutions.
AI policy. The AI policy is described in the “external resource policy” above. We warn you that AI tools, as well as some popular websites such as “Geeks for Geeks”, often make mistakes or contain inaccuracies that can be very difficult to detect as a student. You may be learning something incorrectly if you rely on these tools. If you use them, it is best to double-check information with a more reliable source, such as a textbook.
Example: Suppose the homework assignment is: “Prove that binary search makes at most log(n) comparisons.” A student may use an external textbook, website, or AI tool to learn more about how binary search works. However, the student may not search for an answer to the homework problem or a reworded version of it like “how many comparisons does binary search make?”
Reasoning. The reason behind the policies is that students learn the material by thinking it through themselves. Discussing with classmates generally supports learning and understanding. Similarly, we encourage using high-quality external resources to study more and understand the material better. But simply plugging in the question to an external resource and copying or re-wording the answer does not support learning and understanding. To achieve any standard in the class, the student must solve problems on an exam without any external materials, which is unlikely to be possible without developing understanding.
Students must take quizzes and exams without any resources except a writing utensil (pen or pencil), unless specific accommodations apply.
During each quiz and exam, students will turn off all electronics and place them in a bag at the front of the room before taking a paper exam. Students may not have paper or electronics with them during an exam, and if the proctor finds a violation, the instructor reserves the right to not only fail the student on all problems in that exam, but to fail them from the entire course.
Students requesting additional accommodations must do so through the official CU process at least two weeks in advance of the first exam. It is said students’ responsibility to ensure they have received exam instructions that match their accommodations. Please email the instructor with any questions.
Every problem, whether on homework, quiz, or exam, is graded pass/fail. Every problem is associated with one standard. If you pass the problem, that counts toward achieving the standard.
Every problem has a specific rubric describing what an answer must satisfy in order to pass. The criteria will always include writing quality, including clarity and conciseness. An answer that contains correct elements may still fail if it is difficult to read, difficult to understand or follow, rambles, or contains excess unnecessary information.
To provide additional feedback, problems will be scored on a 0-4 scale:
We emphasize that the numerical scores have no impact on your final grade, which only depends on whether you passed the problem. The numerical scores are only for providing feedback.
Before requesting a regrade, you must be sure you fully understand the problem, the correct solution, and the rubric. You should ask other students, in office hours or student hours, and/or on Piazza to be sure you understand.
Find on Canvas a Google Form for submitting regrade requests. A regrade request must clearly and concisely describe why the rubric was incorrectly applied, resulting in a fail that you believe should be a pass. It should specifically cite the rubric and the written answer.
We can only grade the answer as written, not what you may have had in mind while writing it.
Each student gets two (2) regrade requests. However, if we grant your request, it does not count against your limit of two. After two regrade requests that were not granted, we will not accept any more regrade requests from you this semester. This policy is necessary to manage this large course successfully.
Find the rest of the syllabus here: https://www.colorado.edu/academicaffairs/media/534