This repository is based on the book by Robert Sedgewick and Kevin Wayne entitled Algorithms, fourth edition.
1. Fundamentals
- 1.3 Bags, queues, and stacks
- APIs
- Implementing collections
- Linked lists
- Overview
- 1.4 Analysis of algorithms
- Scientific method
- Mathematical models
- Order-of-growth classification
- Coping with dependence on inputs
- Memory
- 1.5 Union-Find
- Dynamic connectivity
- Implementations
- Quick-find
- Quick-union
- Weighted quick-union
2. Sorting
- 2.1 Elementary Sorts
- Selectionsort
- Insertionsort
- Shellsort
- 2.2 Mergesort
- Top-down mergesort
- Bottom-up mergesort
- 2.3 QuickSort
- Quicksort partitioning
- Quicksort
- Quicksort with 3-way partitioning
- 2.4 Priority Queues
- API
- Algorithms on heaps
- Heap priority queue
- Heapsort
- Summary
3. Searching
- 3.1 Symbol Tables
- API
- Ordered symbol table
- Sequential search (in an unordered linked list)
- Binary search (in an ordered array)
- Ordered symbol-table operations for binary search
- Analysis of binary search
- 3.2 Binary Search Trees
- Basic implementation
- Analysis
- Order-based methods and deletion
- 3.3 Balanced Search Trees
- 2-3 search trees
- Red-black BSTs
- Deletion
- Properties of red-black BSTs
- 3.4 Hash Tables
- Hash functions
- Hashing with separate chaining
- Hashing with linear probing
- Applications
4. Graphs
- 4.1 Undirected Graphs
- Glossary
- Undirected graph data type
- Depth-first search
- Finding paths
- Breadth-first search
- Connected components
- Symbol graphs
- Summary
- 4.2 Directed Graphs
- Glossary
- Digraph data type
- Reachability in digraphs
- Cycles and DAGs
- Strong connectivity in digraphs
- Summary
- 4.3 Minimum Spanning Trees
- Underlying principles
- Edge-weighted graph data type
- Prim's algorithm
- Eager version of Prim's algorithm
- Kruskal's algorithm
- Perspective
- 4.4 Shortest Paths
- Properties of shortest paths
- Edge-weighted digraph data types
- Theoretical basis for shortest-paths algorithms
- Dijkstra's algorithm
- Acyclic edge-weighted digraphs
- Shortest paths in general edge-weighted digraphs
- Perspective