Data Structures & Algorithms

How to Build

Java Code with Maven

Maven is the build tool that manages all of the Java code in this project.

Building algs4

Some of the source code written in java will depend on the algs4 library. Here are the following steps to include the algs4.jar into this project. We are building this jar from source because the bintray repository has been shutdown, preventing Maven from easily pulling an already created algs4.jar

1. git clone https://github.com/kevin-wayne/algs4.git
2. cd algs4 && mvn package
3. cd </path/of/this-project>
4. mvn package
5. mvn install:install-file -Dfile=/path/to/algs4/target/algs4-1.0.0.0.jar -DgroupId=edu.princeton.cs -DartifactId=algs4 -Dversion=1.0.0 -Dpackaging=jar

Normal Usage

1. mvn package to compile and package.
2. java -jar target/<name-of-file>.jar to run the compiled code
3. mvn test to build and run tests.

C++ Code with CMake

CMake (version >= 3.23) is the build tool that manages all of the C++ code in this project. Code is compiled with a C++17 compiler.

Normal Usage

Do the "cmake dance".

1. cmake -S. -Bbuild to create a separate build folder to isolate generate cmake build files.
2. cmake --build build --parallel && ctest --test-dir build --parallel to compile source and run tests.

Or My Personal One-Liner

cmake -S~/workspace/algorithms -GNinja -B~/workspace/algorithms/build && cmake --build ~/workspace/algorithms/build --parallel 8 && ctest --test_dir ~/workspace/algorithms/build --parallel 8

Python Code with VirtualEnv

1. Install pyenv
2. Use pyenv to install Python3 (e.g. pyenv install 3.9.5)
3. Use the installed pip3 to install virtualenv pip install virtualenv
4. Create and source virtualenv virtualenv venv && source venv/bin/activate
5. Install pybuilder in virtualenv
6. Call pyb to run all tests

Table of Contents

Chapter 1. Fundamentals

Topic	C++	Java	Tests
Stacks	✔️	✔️	✔️
Queues	✔️	✔️	✔️
Bags		✔️	✔️
Deque		✔️	✔️
Union Find		x

Chapter 2. Sorting

Topic	C++	Java	Tests
Insertion Sort	✔️	✔️	✔️
Selection Sort	✔️	✔️	✔️
ShellSort	✔️	✔️	✔️
QuickSort	✔️	✔️	✔️
MergeSort	✔️		✔️
HeapSort	✔️		✔️
Binary Heaps	✔️		✔️

Chapter 3. Searching

Topic	C++	Tests
Binary Search Trees	✔️	✔️
Red-Black Trees	x
k-d trees	✔️	✔️
Separate Chaining Hash Tables
Linear Probing Hash Tables

Chapter 4. Graphs

Topic	C++	Tests
Undirected Graph Data Structure	✔️	✔️
Depth-First Search	✔️	✔️
Connected Components	✔️	✔️
Breadth-First Search	✔️	✔️
Directed Graph Data Structure	✔️	✔️
Cycle Detection	✔️	✔️
Topological Sort	✔️	✔️
Kosaraju−Sharir	✔️	✔️
Weighted Edge Data Structure	✔️	✔️
Edge Weighted Graph Data Structure	✔️	✔️
Kruskal	✔️	✔️
Prim	✔️	✔️
Dijkstra	✔️	✔️
Bellman−Ford

Chapter 5. Strings

Topic	C++	Tests
LSD Radix Sort
MSD Radix Sort
3-Way Radix QuickSort
Multiway Tries
Ternary Search Tries
Knuth−Morris−Pratt
Boyer−Moore
Rabin–Karp
Regular Expression Matching
Run-Length Coding
Huffman Coding
LZW Compression
Burrows−Wheeler Transform

Chapter 6. Context

Topic	C++	Tests
Networking: Ford-Fulkerson

Coursera Assignments

1.1 Percolation
1.2 Deque & Randomized Queue
1.3 Collinear Points
1.4 Slider Puzzle
1.5 KdTree
2.1 WordNet
2.2 Seam Carving
2.3 Baseball Elimination
2.4 Boggle
2.5 Burrows-Wheeler

Resources Used

Java

Sedgewick - Algorithms, Fourth Edition
Algorithms, Part 1 on Coursera
Algorithms, Part 2 on Coursera

C++

Stroustrup - The C++ Programming Language, Fourth Edition
Aziz, Adnan, et al. - Elements of Programming Interviews