walkccc/CLRS
CLRS
This repository is a comprehensive collection of fully worked solutions to exercises and problems from the standard algorithms textbook by Cormen, Leiserson, Rivest, and Stein (CLRS). It serves as an educational reference for algorithm design and analysis, providing step-by-step reasoning, pseudocode, and mathematical proofs for a wide range of topics.
The content spans core computer science areas: algorithm analysis with asymptotic notation, recurrence solving, and amortized cost analysis; data structure implementation and operations for binary search trees, red-black trees, B-trees, Fibonacci heaps, hash tables, and more; graph algorithms covering traversal, shortest paths, minimum spanning trees, connectivity, and topological sorting; dynamic programming and greedy approaches for optimization problems; plus sorting, order statistics, and string/sequence algorithms.
The site is built as a static website using Markdown-driven content with KaTeX-rendered mathematical notation, organized via file-based routing for easy browsing of solutions by chapter and exercise.
Features
- Textbook Exercise Solutions - Providing fully worked solutions to exercises and problems from the CLRS algorithms textbook with step-by-step reasoning and pseudocode.
- Exercise Solutions - Provides fully worked solutions to CLRS textbook exercises and problems with KaTeX notation.
- Worked Solutions - A collection of fully worked solutions to exercises and problems from the standard algorithms textbook by Cormen, Leiserson, Rivest, and Stein.
- Hash Tables - Covers direct-address dictionaries and amortized analysis of dynamic table expansion and contraction.
- B-Tree - Provides search, insertion, deletion, and predecessor operations in B-trees while preserving balance.
- Amortized Cost Analyses - Demonstrates amortized analysis using aggregate analysis and accounting method to bound operation costs.
- Algorithm and Data Structure Guides - A reference that provides detailed answers and derivations for topics like sorting, graph algorithms, dynamic programming, and advanced data structures.
- Dynamic Programming - Contains a wide range of DP solutions including knapsack, activity selection, and rod cutting.
- Graph Traversal Algorithms - Covers BFS and DFS implementations with timing, edge classification, and bipartiteness detection.
- Algorithm Implementations - Provides pseudocode implementations and step-by-step execution traces of fundamental algorithms.
- Red-Black Trees - Covers join, amortized cost, properties, and deletion fixup for red-black trees.
- Algorithm Analysis - Analyzing graph algorithms such as BFS, DFS, shortest paths, minimum spanning trees, and network flow with proofs of correctness and complexity.
- Greedy Algorithms - Covers optimal prefix codes, activity selection, matroid scheduling, and coin change with optimality proofs.
- Dynamic Programming Strategies - Solving optimization problems with dynamic programming or greedy strategies, including proofs of optimal substructure and exchange arguments.
- Stack and Queue Algorithms - Provides overflow/underflow detection, double-ended array implementation, two stacks in one array, and simulation of queue with two stacks and stack with two queues.
- Computer Science Education - An educational resource that helps students and professionals understand algorithm design and analysis through clear, annotated solutions.
- Recurrence Relation Solving - Solves recurrence relations using master theorem, recursion tree, and substitution method.
- Binary Search Trees - Covers insertion, search, deletion, traversal, rotation, property analysis, and counting of binary search trees.
- Educational Implementations - Implementing and analyzing fundamental data structures including binary search trees, red-black trees, heaps, hash tables, and B-trees.
- Algorithm Analysis - Compares asymptotic running times and analyzes modifications to determine efficiency changes.
- Asymptotic Notations - Verifies properties and compares growth rates of big-O, theta, and omega notations using proofs.
- Correctness Proofs - Provides formal proofs of algorithm correctness using invariants and induction.
- Minimum Spanning Tree Algorithms - Covers MST algorithms including bottleneck spanning tree, preprocessing, and correctness verification.
- Shortest Path Algorithms - Provides Bellman-Ford, DAG longest path, all-pairs shortest paths, and mean-weight cycle algorithms.
- Fibonacci - Covers decrease-key, pruning operations, and amortized cost analysis for Fibonacci heaps.
- String and Sequence Algorithm Solutions - Provides DP-based solutions for edit distance, longest common subsequence, longest increasing subsequence, optimal string break points, and paragraph line breaking.
- Free-List Allocators - Implements allocation and deallocation of array objects from a stack-like free list for reuse.
- Dynamic Data Structures - Covers minimum gap maintenance in dynamic sets, node depth tracking, and insertion into sorted arrays.
- AVL Tree Operations - Maintains height balance in a BST after insertions by performing single rotations to keep subtree heights within one.
- Stable Sorting Preservations - Augments a non-stable sort with original indices to preserve relative order of equal elements.
- Probabilistic Analyses - Applies probabilistic methods to analyze randomized algorithms such as random permutations and chip testing.
- Order Statistics - Augments balanced BSTs with subtree sizes to support rank queries, order-statistic selection, and range enumeration.
- Interval Tree Operations - Provides detection, search for exact and open intervals, enumeration of overlapping intervals, and maintenance of max attribute during rotations.
- Linked List Manipulation Utilities - Compares asymptotic running times for operations on singly, doubly, and circular linked lists and implements in-place compaction.
- Sorting Algorithm Variants - Analyzes and implements variations of sorting algorithms including hybrid sort thresholds, three-way partitioning, insertion sort in descending order, and specific constraints.
