Overview
This interactive text used in this course was written with the intention of teaching Computer Science students about various data structures as well as the applications in which each data structure would be appropriate to use. It is currently beingtaught at the University of California, San Diego (UCSD), the University of San Diego (USD), and the University of Puerto Rico (UPR).
Thiscoursework utilizes the Active Learning approach to instruction, meaning it has various activities embedded throughout to help stimulate your learning and improve your understanding of the materials we will cover. You will encounter “STOP and Think” questions that will help you reflect on the material, “Exercise Breaks” that will test your knowledge and understanding of the concepts discussed, and “Code Challenges” that will allow you to actually implement some of the algorithms we will cover.
Currently, all code challenges are in C++ or Python, but the vast majority of the content is language-agnostic theory of complexity and algorithm analysis. In other words, even without C++ or Python knowledge, the key takeaways can still be obtained.
Syllabus
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