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

This site uses Just the Docs, a documentation theme for Jekyll.