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

  1. You have credit for CS 2100, CS 2150, or an equivalent data structures course
  2. 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):

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

Copyright © 2024 John Hott and Raymond Pettit.
Released under the CC-BY-NC-SA 4.0 license.
Creative Commons License