UCSanDiegoX: Data Structures: An Active Learning Approach

• The algorithms behind fundamental data structures (dynamic arrays, linked structures, (un)balanced trees/tries, graph algorithms, hash tables/functions)
• How to reason about appropriate data structures to solve problems, including their strengths and weaknesses
• How to analyze algorithms theoretically (worst-case, average-case, and amortized)
• The key distinctions and relations between "Abstract Data Types" and "Data Structures"
• Basic information theory and data compression utilizing the data structures covered

Module 1: Introduction and Review

• 1.1 Welcome to Data Structures!
• 1.2 Tick Tock, Tick Tock
• 1.3 Classes of Computational Complexity
• 1.4 The Fuss of C++
• 1.5 Random Numbers
• 1.6 Bit-by-Bit
• 1.7 The Terminal-ator
• 1.8 Git: the "Undo" Button of Software Development

Module 2: Introductory Data Structures

• 2.1 Array Lists
• 2.2 Linked Lists
• 2.3 Skip Lists
• 2.4 Circular Arrays
• 2.5 Abstract Data Types
• 2.6 Deques
• 2.7 Queues
• 2.8 Stacks
• 2.9And the Iterators Gonna Iterate-ate-ate

Module 3: Tree Structures

• 3.1Lost in a Forest of Trees
• 3.2 Heaps
• 3.3 Binary Search Trees
• 3.4 BST Average-Case Time Complexity
• 3.5 Randomized Search Trees
• 3.6 AVL Trees
• 3.7 Red-Black Trees
• 3.8 B- Trees
• 3.9 B+ Trees

Module 4: Introduction to Graphs

• 4.1 Introduction to Graphs
• 4.2 Graph Representations
• 4.3 Algorithms on Graphs: Breadth-First Search
• 4.4 Algorithms on Graphs: Depth-First Search
• 4.5 Dijkstra's Algorithm
• 4.6 Minimum Spanning Trees: Prim's and Kruskal's Algorithms
• 4.7 Disjoint Sets

Module 5: Hashing

• 5.1The Unquenched Need for Speed
• 5.2 Hash Functions
• 5.3 Introduction to Hash Tables
• 5.4 Probability of Collisions
• 5.5Collision Resolution: Open Addressing
• 5.6Collision Resolution: Closed Addressing (Separate Chaining)
• 5.7Collision Resolution: Cuckoo Hashing
• 5.8 Hash Maps

Module 6:Implementing a Lexicon

• 6.1 Creating a Lexicon
• 6.2 Using Linked Lists
• 6.3 Using Arrays
• 6.4 Using Binary Search Trees
• 6.5 Using Hash Tables and Hash Maps
• 6.6 Using Multiway Tries
• 6.7 Using Ternary Search Trees

Module 7:Coding and Information Compression

• 7.1Return of the (Coding) Trees
• 7.2 Entropy and Information Theory
• 7.3 Honey, I Shrunk the File
• 7.4 Bitwise I/O

Module 8: Conclusions

• 8.1Summaries of Data Structures