Data Structures and Algorithms 2

Email the course staff Canvas workspace Gradescope workspace Piazza workspace

Office Hours:

The office hours for this semester are:

  • Professor Hott’s office hours are Tues & Thurs 2:30-3:30pm and Weds 3-4pm in Rice 401
  • Professor Bloomfield’s office hours are Wed 10-noon and Thu 2-3pm in Rice 402
  • TA office hours are Mondays through Thursdays, from 5pm to 9pm, in Rice 442

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):

  • Logarithms and identities
  • Sets
  • Functions
  • Proof Techniques
  • Proof Styles, we’ll mostly be using “prose proofs”
  • Logic and Notation
  • Recursion
  • Trees
  • Lists
  • Queues
  • Stacks
  • Priority Queues
  • Hash Tables
This site uses Just the Docs, a documentation theme for Jekyll.