Share Description
In this course, you will learn:
- Fundamental data structures (dynamic arrays, linked structures, (un)balanced trees/tries, graph algorithms, hash tables/functions) are all based on algorithms.
- How to use logic to determine the best data structures for a given situation, as well as their strengths and disadvantages.
- How to do a theoretical analysis of algorithms (worst-case, average-case, and amortized).
- The fundamental differences and relationships between "Abstract Data Types" and "Data Structures."
- Data compression using the data structures presented as well as basic information theory.
Syllabus:
1. Introduction and Review
- Welcome to Data Structures!
- Tick Tock, Tick Tock
- Classes of Computational Complexity
- The Fuss of C++
- Random Numbers
- Bit-by-Bit
- The Terminal-ator
- Git: the "Undo" Button of Software Development
2. Introductory Data Structures
- Array Lists
- Linked Lists
- Skip Lists
- Circular Arrays
- Abstract Data Types
- Deques
- Queues
- Stacks
- And the Iterators Gonna Iterate-ate-ate
3. Tree Structures
- Lost in a Forest of Trees
- Heaps
- Binary Search Trees
- BST Average-Case Time Complexity
- Randomized Search Trees
- AVL Trees
- Red-Black Trees
- B- Trees
- B+ Trees
4: Introduction to Graphs
- Introduction to Graphs
- Graph Representations
- Algorithms on Graphs: Breadth-First Search
- Algorithms on Graphs: Depth-First Search
- Dijkstra's Algorithm
- Minimum Spanning Trees: Prim's and Kruskal's Algorithms
- Disjoint Sets
5: Hashing
- The Unquenched Need for Speed
- Hash Functions
- Introduction to Hash Tables
- Probability of Collisions
- Collision Resolution: Open Addressing
- Collision Resolution: Closed Addressing (Separate Chaining)
- Collision Resolution: Cuckoo Hashing
- Hash Maps
6: Implementing a Lexicon
- Creating a Lexicon
- Using Linked Lists
- Using Arrays
- Using Binary Search Trees
- Using Hash Tables and Hash Maps
- Using Multiway Tries
- Using Ternary Search Trees
7: Coding and Information Compression
- Return of the (Coding) Trees
- Entropy and Information Theory
- Honey, I Shrunk the File
- Bitwise I/O
8. Conclusions
- Summaries of Data Structures
