Data Structures and Algorithms 2
Course Overview: The goal of this course is to build a tool kit to better solve a variety of computational problems, and to evaluate the quality of such solutions. In particular, we will cover:
- Formal metrics for evaluating algorithm complexity (including the asymptotic classes big-oh, big-omega, big-theta, little-oh, and little-omega)
- Evaluating an algorithm’s usage of resources (including time and space complexities) by a worst-case analysis, expected-case analysis, and amortized analysis
- Algorithm design strategies (including divide and conquer, dynamic programming, greedy, and reductions)
- The impact of data-structure choice on algorithm design
- Proving algorithm correctness
- Proving worst-case lower bounds on algorithm efficiency using reductions
- Algorithms on graphs
Learning Outcomes: At the conclusion of this course, a successful student will be able to:
- Analyze a pre-written algorithm to determine its resource complexity
- Employ the strategies of divide and conquer, greedy, and dynamic programming (perhaps in concert) to develop novel algorithms
- Prove the correctness of algorithms built using these strategies
- Identify trade-offs in algorithm design (such as time vs. space, average-case vs. worst case, dynamic vs. static)
- Prove lower bounds on algorithm complexity
Eligibility: You should take this course if and only if
- You have credit for CS 2100, CS 2150, or an equivalent data structures course
- You have credit for CS 2120, CS 2102, or an equivalent discrete math course
Background
This course will assume knowledge of several topics from discrete math (CS2120 at UVA), two semesters of programming experience (through CS2100 at UVA), and data structures (also CS2100 at UVA)
In particular, we assume knowledge of (with recommended resources for review):
- Logarithms and identities (Log rules)
- Sets (CS2102 Sets Primer)
- Functions (Section 4.3 of this text)
- Proof Techniques (CS2102 Proof Techniques)
- Proof Styles, we’ll mostly be using “prose proofs” (CS2102 Proof style guide)
- Logic and Notation (CS2102 Glossary of logical terms)
- Recursion (CS2100, CS2110 part 1, CS2110 part 2)
- Trees (CS2100, CS2150)
- Lists (CS2100, CS2150)
- Queues (CS2100, CS2150)
- Stacks (CS2100, CS2150)
- Priority Queues (CS2100, CS2150)
- Hash Tables (CS2100, CS2150)
For each of the Discrete Math topics, the Fall 2019 lectures are publicly available.
Platforms
| Platform | Purpose |
|---|---|
| This Website | Central repository of course information and content including: syllabus, schedule, file hosting, readings, assignment writeups, etc. |
| Canvas | Linking to all of the other tools, lecture recordings |
| Piazza | Course content and policy questions |
| Discord | Online office hours, informal interactions, homework collaboration |
| Gradescope | Homework submission and grading |