CS 225 - Data Structures

This core class is essentially a continuation of CS 128. Much like CS 128, this course primarily consists of biweekly Machine Problems graded through PrairieLearn and exams administered through CBTF. There are also labs assignments, which are smaller in scope when compared to machine problems, but are a more direct application of lecture content. Lectures are in person, and there is a final exam.

There is also an honours section. Topics covered in this section will vary by semester. Past material include string algorithms and tries.

Topics Covered

• Abstract Data Structures
  • Lists
  • Stacks/Queues
  • Array Lists
  • Trees
    • KD Trees
    • Binary Search Trees
    • AVL Trees (Self-balancing Trees)
    • BTrees
  • Heaps
  • Disjoint Sets
• Graph Algorithms
  • Tree Traversal
  • Tree Search
  • Minimum Spanning Tree
  • All-Pair-Shortest-Path (APSP)
  • Single-Source-Shortest-Path (SSSP)
• Hashing
  • Open Addressing
  • Bloom Filters

Resources

There are official notes posted to the CS225 website.

Developer’s Commentary

This class introduces important concepts in how we organize data in programs, how data is accessed in these data structures, and the performance implications of each data structure. This is enormously important as deliberating over which data structure is appropriate and how to organize data in general is an important skill within the system design process. The content of this class will get revisited in many future classes; having a solid understanding of the content will prove very helpful.

The caching content in CS 233 fits in nicely with the discussion of performance implications of various data structures.