Log In
0% completed
Overview
Introduction
The Need for Efficiency
Interfaces
Mathematical Background
The Model of Computation
Approach and Coverage
Quiz
Discussion
Array-Based Lists
Array Implementation of Stack
ArrayQueue: An Array-Based Queue
ArrayDeque: Fast Deque Operations Using an Array
DualArrayDeque: Building a Deque from Two Stacks
RootishArrayStack: A Space-Efficient Array Stack
Analysis of RootishArrayStack
Quiz on Array-Based Lists
Discussion on Array-Based Lists
Exercise: Array-Based Lists
Solution: Array-Based Lists
Linked Lists
SLList: A Singly-Linked List
DLList: A Doubly-Linked List
SEList: A Space-Efficient Linked List
Operations on SEList
Amortized Analysis of Spreading and Gathering
Quiz on Linked Lists
Discussion on Linked Lists
Skiplists
Introduction to Skiplist
SkiplistSSet: An Efficient SSet
SkiplistList: An Efficient Random-Access List
Analysis of Skiplists
Quiz on Skiplists
Discussion on Skiplists
Exercise: Skiplists
Solution: Skiplists
Hash Tables
ChainedHashTable: Hashing with Chaining
LinearHashTable: Linear Probing
Hash Codes
Quiz on Hash Tables
Discussion on Hash Tables
Exercise: Hash Tables
Solution: Hash Tables
Binary Trees
Introduction to Binary Trees
BinaryTree: A Basic Binary Tree
BinarySearchTree: An Unbalanced Binary Search Tree
Quiz on Binary Trees
Discussion on Binary Trees
Random Binary Search Trees
Introduction to Random Binary Search Trees
Treap: A Randomized Binary Search Tree
Quiz on Random Binary Search Trees
Discussion on Random Binary Search Trees
Exercise: Random Binary Search Trees
Solution: Random Binary Search Trees
Scapegoat Trees
Introduction to Scapegoat Trees
Analysis of Correctness and Running Time
Quiz on Scapegoat Trees
Discussion on Scapegoat Trees
Exercise: Scapegoat Trees
Solution: Scapegoat Trees
Red-Black Trees
The 2–4 Trees
Fundamentals of Red-Black Trees
Red-Black Tree Operations
Quiz on Red-Black Trees
Discussion on Red-Black Trees
Heaps
BinaryHeap: An Implicit Binary Tree
MeldableHeap: A Randomized Meldable Heap
Quiz on Heaps
Discussion on Heaps
Exercise: Heaps
Solution: Heaps
Sorting Algorithms
Merge-sort
Quicksort
Heap-sort
A Lower Bound for Comparison-Based Sorting
Counting-Based Sorting
Quiz on Sorting Algorithms
Discussion on Sorting Algorithms
Exercise: Sorting Algorithms
Solution: Sorting Algorithms
Graphs
Introduction to Graphs
AdjacencyMatrix: Representing a Graph by a Matrix
AdjacencyLists: A Graph as a Collection of Lists
Graph Traversal
Quiz on Graphs
Discussion on Graphs
Exercise: Graphs
Solution: Graphs
Data Structures for Integers
Partial Integers
Doubly-Logarithmic Time
Quiz on Data Structures for Integers
Discussion on Data Structures for Integers
External Memory Searching
B-Trees
Searching and Addition in B-Tree
Removal from B-Tree
Analysis of B-Trees
Quiz on External Memory Searching
Discussion on External Memory Searching
Wrap Up
Conclusion
Data Structures with Generic Types in Python
/
...
/
Quiz on Red-Black Trees
Quiz on Red-Black Trees
Test yourself on what you've learned about red-black trees.
We'll cover the following...
...