README.md

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

• UF: main_UF.cpp

Sorting

• Selection | Insertion | Shell | Merge | MergeBU | Quick | Quick3way | Heap: main_Sorting.cpp.in
• MaxPQ: main_MaxPQ.cpp

Symbol Tables

• TestSequentialSearchST | TestBinarySearchST | TestBST | TestRedBlackBST | TestSeparateChainingHashST | TestLinearProbingHashST: main_TestST.cpp.in

Graphs

• DepthFirstPaths | BreadthFirstPaths: main_Paths.cpp.in
• CC | KosarajuSCC: main_CC.cpp.in
• DirectedDFS: main_DirectedDFS.cpp
• Topological: main_Topological.cpp
• PrimMST | KruskalMST: main_MST.cpp.in
• DijkstraSP | AcyclicSP | BellmanFordSP: main_SP.cpp.in

Strings

• LSD | MSD | Quick3string: main_Sorting.cpp.in
• TestTrieST | TestTST: main_TestST.cpp.in
• KMP | BoyerMoore | RabinKarp: main_SubstrSearch.cpp.in
• GREP: main_GREP.cpp
• Huffman | LZW: main_Compress.cpp.in
• BinaryDump: main_BinaryDump.cpp

Build and Run

Prerequisites

• CMake 3.20 or later
• C++ compiler with C++17 support

Steps

1. Create and navigate to a build directory:

   mkdir build
   cd build

2. Configure and build all targets. This will produce all clients:

   cmake ..
   cmake --build .

   Alternatively, build a specific target that produces a specific client:

   cmake --build . --target UF

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

4. Run the client. You may redirect the input from a file (possibly one obtained in step 3):

   ./UF < tinyUF.txt

   Some clients may expect command-line arguments. For example:

   ./DepthFirstPaths tinyCG.txt 0

   This will run DepthFirstPaths on the graph in tinyCG.txt starting from vertex 0.