This is a repository of pseudocode implementations discussed in the main text of a classic - 📖 Introduction to Algorithms, widely known as CLRS. There are some great solution manuals for more theoretical problems, such as https://walkccc.github.io/CLRS/, so I have decided to focus only on the main text pseudocode and personally more interesing exercises. All implementations are written in C and should be cross-platform.
The folder structure of this repository resembles the book structure. Usually, implementations come with small auxiliary programs and simple test inputs.
For example, along with an implementation of Huffman coding algorihm there is a small program to print the generated prefix code.
For some "heavier" implementations, depending on some data structures or algorithms, there is also a small bash script in the implementation folder to aid compilation.
Also, although the pseudocode in the book may not have the best variable naming, I have decided to respect it for the sake of consistency. However, I did not respect pseudocode conventions when it comes to implementations of algorithms presented as exercise problems or as end of chapter problems.
Foundations (Chapters 2, 3, 4) 🔗
- InsertionSort
- MergeSort
- Maximum Subarray (Divide and Conquer, BruteForce)
- Max Heap 🔗
- HeapSort 🔗
- Max Priority Queue 🔗
- Min Priority Queue 🔗
- Implemented as Max Priority Queue with inverted keys
- QuickSort (non-randomised) 🔗
- QuickSort (randomised) 🔗
- CountingSort 🔗
- RadixSort 🔗
- BucketSort 🔗
- RandomisedSelect aka QuickSelect 🔗
- Stack
- Queue
- Linked-List (doubly-linked, circular) 🔗
- Hash Table
- Binary Search Tree 🔗
- All discussed operations
- Red Black Tree 🔗
- Insertion
- Deletion
- AVL Tree 🔗
- AVL Sort
- All discussed BST operations, along with AVL Insert and Delete
- Disjoint Set Union 🔗
- implemented path compression and union by rank heuristics
- rod cutting 🔗
- matrix chain multiplication 🔗
- longest common subsequence 🔗
- optimal binary search tree 🔗
- longest path in a dag 🔗
- longest palindromic subsequence 🔗
- implemented as longest-common-subsequence(input, reversed(input))
- printing neatly 🔗
- also known as a variant of the word wrap problem
- simplified-edit-distance 🔗
- coin changing 🔗
- classical dynamic programming problem, presented as exercise 16.1.d)
- activity scheduling 🔗
- interval graph coloring(scheduling) - exercise 16.1.4
- We are given n activities to be held in some lecture halls. For each activity we know its starting time, finishing time and id. Any activity can take place in any lecture hall. Design a fast greedy algorithm to determine the minimal number of lecture halls required to ensure all activities can happen. Algorithm should also determine activity schedule taking place in each lecture hall used.
- The algorithm implemented 🔗 here has O(nlogn) time complexity. All data structures used (min priority queue, doubly linked list) are implemented in the corresponding folders in this repository.
- Huffman codes 🔗
- A small program to print a generated prefix code 🔗
- BFS 🔗
- performs unweighted shortest path computation
- DFS 🔗
- performs vertex timestamping and edge classification
- Topological Sorting
- Strongly connected components of a directed graph
- Kosaraju's 'two pass' algorithm 🔗
- implemented with the aid of dfs-based topological sort, also implemented above
- Kosaraju's 'two pass' algorithm 🔗
- Biconnected components of an undirected graph
- Hopcroft-Tarjan's algorithm for detecting articulation points and bridges 🔗
- Detects bridges
- Detects articulation points
- Hopcroft-Tarjan's algorithm for detecting articulation points and bridges 🔗
- An Euler tour of a directed graph
- presented as the problem in End of Chapter 22 problems
- implemented Hierholzer's algorithm 🔗
- Prim's algorithm 🔗
- computes the cost and the tree edges set
- Kruskal's algorithm 🔗
- computes the cost and the tree edges set
- The Bellman-Ford algorithm 🔗
- detects existence of a negative-weight cycle reachable from source vertex
- in case there is no negative-weight cycle reachable from source vertex, the algorithm returns the shortest path from s to every vertex v in the input graph as well as the shortest path tree rooted at s
- Shortest Path in a directed acyclic graph using Topological Sort + Relax 🔗
- the algorithm returns the shortest path from s to every vertex v in the input graph as well as the shortest path tree rooted at s
- Dijkstra's algorithm 🔗
- computes the shortest path weights and shortest path tree from a source vertex s
- implemented with a Min Priority Queue
-
'Slow all pairs shortest paths' 🔗
- This algorithm is based on dynamic programming on edges and has worst case complexity O(|V|^4)
- The algorithm is developed 'from scratch' in the textbook Chapter 25.1
- An algebraically optimised version of the same algorithm is also implemented 🔗, having worst case complexity O(|V|^3 log(|V|))
- Implemented both shortest path cost computation and path reconstruction for every vertex pair (non-optimised version only)
-
Floyd-Warshall algorithm 🔗
- Implemented both shortest path cost computation and path reconstruction for every vertex pair
-
Transitive closure algorithm 🔗
- Adapted Floyd-Warshall's procedure
Huffman codes 🔗 - a beautiful greedy 'construction' algorithm
printing neatly 🔗 - a neat, non obvious application of dynamic programming
constructing an optimal binary search tree 🔗- a nice application of DP on trees
constructing an Euler tour with Hierholzer's algorithm
🔗 - a nice 'construction' graph algorithm, challenging to implement in C. Presented as one of end of chapter problems.
scheduling lectures with interval graph coloring 🔗 - a nice, real world application of greedy activity scheduling. Presented as one of exercises.
topological sorting of a 'clothing' graph 🔗 - a nice 'real-world' example of topological sorting graph algorithm