Basic Data Structures-Welcome
Welcome
Basic Data Structures-Arrays and Linked Lists
Arrays
()
Singly-Linked Lists
()
Doubly-Linked Lists
()
Slides and External References
Basic Data Structures-Stacks and Queues
Stacks
()
Queues
()
Slides and External References
Basic Data Structures-Trees
Trees
()
Tree Traversal
()
Slides and External References
Basic Data Structures-Programming Assignment 1
Available Programming Languages
FAQ on Programming Assignments
Basic Data Structures-Acknowledgements (Optional)
Acknowledgements
Dynamic Arrays and Amortized Analysis-Dynamic Arrays and Amortized Analysis
Dynamic Arrays
()
Amortized Analysis: Aggregate Method
()
Amortized Analysis: Banker's Method
()
Amortized Analysis: Physicist's Method
()
Amortized Analysis: Summary
()
Slides and External References
Priority Queues and Disjoint Sets-Priority Queues: Introduction
Introduction
()
Naive Implementations of Priority Queues
()
Slides
Priority Queues and Disjoint Sets-Priority Queues: Heaps
Binary Trees
()
Tree Height Remark
Basic Operations
()
Complete Binary Trees
()
Pseudocode
()
Slides and External References
Priority Queues and Disjoint Sets-Priority Queues: Heap Sort
Heap Sort
()
Building a Heap
()
Final Remarks
()
Slides and External References
Priority Queues and Disjoint Sets-Disjoint Sets: Naive Implementations
Overview
()
Naive Implementations
()
Slides and External References
Priority Queues and Disjoint Sets-Disjoint Sets: Efficient Implementation
Trees for Disjoint Sets
()
Union by Rank
()
Path Compression
()
Analysis (Optional)
()
Slides and External References
Hash Tables-Introduction, Direct Addressing and Chaining
Applications of Hashing
()
Analysing Service Access Logs
()
Direct Addressing
()
Hash Functions
()
Chaining
()
Chaining Implementation and Analysis
()
Hash Tables
()
Slides and External References
Hash Tables-Hash Functions
Phone Book Data Structure
()
Universal Family
()
Hashing Phone Numbers
()
Hashing Names
()
Analysis of Polynomial Hashing
()
Slides and External References
Hash Tables-Search Substring
Find Substring in Text
()
Rabin-Karp's Algorithm
()
Recurrence for Substring Hashes
()
Improving Running Time
()
Slides and External References
Hash Tables-Blockchain
Julia's Diary
()
Julia's Bank
()
Blockchain
()
Merkle Tree
()
Slides and External References
Binary Search Trees-Binary Search Trees
Introduction
()
Search Trees
()
Basic Operations
()
Balance
()
Slides and External References
Binary Search Trees-AVL Trees
AVL Trees
()
AVL Tree Implementation
()
Split and Merge
()
Slides and External References
Binary Search Trees 2-Applications
Applications
()
Slides and External References
Binary Search Trees 2-Splay Trees
Splay Trees: Introduction
()
Splay Trees: Implementation
()
(Optional) Splay Trees: Analysis
()
Slides and External References