This repository is a collection of canonical data structures and algorithms based on the corresponding pseudocode described in "Introduction to Algorithms" (third edition, 2009) by Cormen, Leiserson, Rivest, and Stein (CLRS).
The objective of this repository is to gain insight into these fundamental concepts, and to implement them with modern programming languages using language-specific features and idioms.
Filename convention: Prefixed by CLRS 3ed page reference (e.g., p156_... for page 156).
JavaScript: Requires Node.js v12 or higher. Run shell command node javascript in root directory for console outputs (cf. javascript/index.js for output script code).
Python: Requires Python 3.8 or higher. Run shell command python main.py in sub-directory /python for console outputs (cf. python/main.py for output script code).
| Section | Topic | CLRS 3ed Reference | Dependencies |
|---|---|---|---|
| Sorting Algorithms | Insertion Sort | Section 2.1 | (N/A) |
| Sorting Algorithms | Merge Sort | Section 2.3 | (N/A) |
| Sorting Algorithms | Bubble Sort | Problem 2.2 | (N/A) |
| Sorting Algorithms | Heapsort | Section 6.4 | Max-Heap |
| Sorting Algorithms | Quicksort | Section 7.1 | (N/A) |
| Sorting Algorithms | Counting Sort | Section 8.2 | (N/A) |
| Data Structures | Max-Heap | Section 6.3 | (N/A) |
| Data Structures | Min-Heap | Section 6.3 | (N/A) |
| Data Structures | Max Priority Queue | Section 6.5 | Max-Heap |
| Data Structures | Min Priority Queue | Exercise 6.5-3 | Min-Heap |
| Data Structures | Stack | Section 10.1 | (N/A) |
| Data Structures | Queue | Section 10.1 | (N/A) |
| Data Structures | Deque | Exercise 10.1-5 | (N/A) |
| Data Structures | Linked List | Section 10.2 | (N/A) |
| Data Structures | Circular Linked List with Sentinel | Section 10.2 | (N/A) |
| Data Structures | Hash Table with Chaining | Section 11.2 | Linked List |
| Data Structures | Hash Table with Probing | Section 11.4 | (N/A) |
| Data Structures | Binary Search Tree | Chapter 12 | (N/A) |
| Data Structures | Red-Black Tree | Chapter 13 | (N/A) |
| Algorithm Design Techniques | Dynamic Programming: Rod Cutting | Section 15.1 | (N/A) |
| Algorithm Design Techniques | Dynamic Programming: Longest Common Subsequence | Section 15.4 | (N/A) |
| Algorithm Design Techniques | Greedy Algorithm: Activity Selector | Section 16.1 | (N/A) |
| Algorithm Design Techniques | Dynamic Programming: 0-1 Knapsack Problem | Exercise 16.2-2 | (N/A) |
| Algorithm Design Techniques | Greedy Algorithm: Fractional Knapsack Problem | Exercise 16.2-6 | (N/A) |
| Algorithm Design Techniques | Greedy Algorithm: Huffman Codes | Section 16.3 | Min Priority Queue |
| Advanced Data Structures | Disjoint Set with Union by Rank and Path Compression | Section 21.3 | (N/A) |
| Graph Algorithms | Breadth-First Search | Section 22.2 | Queue |
| Graph Algorithms | Depth-First Search | Section 22.3 | (N/A) |
| Graph Algorithms | Minimum Spanning Tree: Kruskal's Algorithm | Section 23.2 | Disjoint Set |
| Graph Algorithms | Minimum Spanning Tree: Prim's Algorithm | Section 23.3 | Min Priority Queue |
| Graph Algorithms | Single-Source Shortest Path: Bellman-Ford Algorithm | Section 24.1 | (N/A) |
| Graph Algorithms | Single-Source Shortest Path: Dijkstra's Algorithm | Section 24.3 | Min Priority Queue |