Overview

This repository contains C++ implementations of the algorithms and clients in the textbook Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

For the original Java source code, visit the official repository.

Algorithms

Fundamentals

• 1.5 Union-find: UF.h | UF.cpp

Sorting

• 2.1 Selection sort: Selection.h
• 2.2 Insertion sort: Insertion.h
• 2.3 Shellsort: Shell.h
• 2.4 Top-down mergesort: Merge.h
• Bottom-up mergesort: MergeBU.h
• 2.5 Quicksort: Quick.h
• Quicksort with 3-way partitioning: Quick3way.h
• 2.6 Heap priority queue: MaxPQ.h
• 2.7 Heapsort: Heap.h

Symbol Tables

• 3.1 Sequential search: SequentialSearchST.h
• 3.2 Binary search: BinarySearchST.h
• 3.3 Binary tree search: BST.h
• 3.4 Red-black BST search: RedBlackBST.h
• 3.5 Hashing with separate chaining: SeparateChainingHashST.h
• 3.6 Hashing with linear probing: LinearProbingHashST.h

Graphs

• 4.1 Depth-first search: DepthFirstPaths.h | DepthFirstPaths.cpp
• 4.2 Breadth-first search: BreadthFirstPaths.h | BreadthFirstPaths.cpp
• 4.3 Connected components: CC.h | CC.cpp
• 4.4 Reachability: DirectedDFS.h | DirectedDFS.cpp
• 4.5 Topological order: Topological.h
• 4.6 Strong components (Kosaraju): KosarajuSCC.h | KosarajuSCC.cpp
• 4.7 Minimum spanning tree (Prim): PrimMST.h | PrimMST.cpp
• 4.8 Minimum spanning tree (Kruskal): KruskalMST.h | KruskalMST.cpp
• 4.9 Shortest paths (Dijkstra): DijkstraSP.h | DijkstraSP.cpp
• 4.10 Shortest paths in DAGs: AcyclicSP.h | AcyclicSP.cpp
• 4.11 Shortest paths (Bellman-Ford): BellmanFord.h | BellmanFord.cpp

Strings

• 5.1 LSD string sort: LSD.h | LSD.cpp
• 5.2 MSD string sort: MSD.h | MSD.cpp
• 5.3 Three-way string quicksort: Quick3string.h | Quick3string.cpp
• 5.4 Trie symbol table: TrieST.h
• 5.5 TST symbol table: TST.h
• 5.6 Substring search (Knuth-Morris-Pratt): KMP.h | KMP.cpp
• 5.7 Substring search (Boyer-Moore): BoyerMoore.h | BoyerMoore.cpp
• 5.8 Substring search (Rabin-Karp): RabinKarp.h | RabinKarp.cpp
• 5.9 Regular expression pattern matching: NFA.h | NFA.cpp
• 5.10 Huffman compression/expansion: Huffman.h | Huffman.cpp
• 5.11 LZW compression/expansion: LZW.h | LZW.cpp

Clients

Fundamentals

• Union-find (UF): main_UF.cpp

Sorting

• Sorts (Selection, Insertion, Shell, Merge, MergeBU, Quick, Quick3way, Heap): main_Sorting.cpp.in
• Heap priority queue (MaxPQ): main_MaxPQ.cpp

Symbol Tables

• Symbol table tests (TestSequentialSearchST, TestBinarySearchST, TestBST, TestRedBlackBST, TestSeparateChainingHashST, TestLinearProbingHashST): main_TestST.cpp.in

Graphs

• Depth-first search (DepthFirstPaths) | Breadth-first search (BreadthFirstPaths): main_Paths.cpp.in
• Connected components (CC, KosarajuSCC): main_CC.cpp.in
• Reachability (DirectedDFS): main_DirectedDFS.cpp
• Topological order (Topological): main_Topological.cpp
• Minimum spanning tree (PrimMST, KruskalMST): main_MST.cpp.in
• Shortest paths (DijkstraSP, AcyclicSP, BellmanFordSP): main_SP.cpp.in

Strings

• String sorts (LSD, MSD, Quick3string): main_Sorting.cpp.in
• Trie symbol table tests (TestTrieST) | TST symbol table tests (TestTST): main_TestST.cpp.in
• Substring search (KMP, BoyerMoore, RabinKarp): main_SubstrSearch.cpp.in
• Regular expression pattern matching (GREP): main_GREP.cpp
• Huffman compression/expansion (Huffman) | LZW compression/expansion (LZW): main_Compress.cpp.in

Build and Run

1. Configure the project in the build directory:

   cmake -B build

2. Build all clients:

   cmake --build build

   Alternatively, you can build only a specific client (e.g., the "Union-find" client):

   cmake --build build --target UF

3. (Optional) Download sample input files from the book's website: https://algs4.cs.princeton.edu/code/.

4. From the build directory, run the client. You may redirect the input from a file (possibly one obtained in step 3):

   ./UF < tinyUF.txt

   You may also pipe the output of one client to the input of another:

   ./Huffman - < abra.txt | ./Huffman +

   Some clients expect command-line arguments:

   ./DepthFirstPaths tinyCG.txt 0

   This will run depth-first search on the graph in tinyCG.txt starting from vertex 0.