William Fiset Algorithms and Data Structures

The repository provides implementations for several Dynamic Programming (DP) categories:

• Classics: Coin Change, Edit Distance (Iterative/Recursive), Knapsack (0/1 and Unbounded), Maximum Contiguous Subarray, Longest Common Subsequence (LCS), Longest Increasing Subsequence (LIS), Longest Palindrome Subsequence (LPS), Traveling Salesman Problem (TSP), and Minimum Weight Perfect Matching.
• Problem Examples: Adhoc problems (Magic Cows, Narrow Art Gallery) and Tiling problems (Dominoes, Dominoes and Trominoes, Mountain Scenes).

The repository contains implementations of various data structures, including:

• Trees: Balanced Trees (AVL, Red-Black), Binary Search Trees, Splay Trees, Segment Trees, and Fenwick Trees.
• Heaps & Queues: Fibonacci Heap, Priority Queues (Min Binary Heap, Min Indexed Binary Heap, Min D-Heap, Min Indexed D-Heap), and various Queue implementations.
• Hashing: Hashtables with different collision resolution strategies (Double Hashing, Linear Probing, Quadratic Probing, Separate Chaining).
• Linear Structures: Dynamic Arrays, Linked Lists, Stacks (Array, List, and Integer-only versions), and Deques.
• Advanced Structures: Suffix Arrays, Tries, and Union-Find.

The repository contains a variety of geometry algorithms implemented in Java and JavaScript. These include:

• 2D/3D Vector operations: Angle between vectors.
• Circle & Line intersections: Circle-circle, circle-line, circle-line segment, and line segment-circle intersections.
• Convex Hull algorithms: Graham Scan and Monotone Chain.
• Polygon operations: Convex polygon area, checking if a convex polygon contains a point, and convex polygon cutting.
• Point & Line properties: Collinear points test, triangle area, point rotation, and line segment to general form conversion.
• Other: Closest pair of points (line sweeping), and geographic distance (Longitude-Latitude).

A comprehensive collection of graph algorithms is provided, including:

• Connectivity & Components: Articulation points, bridges, finding connected components (via Union-Find or DFS), and Strongly Connected Components (Kosaraju's or Tarjan's algorithms).
• Shortest Paths: Bellman-Ford (edge list or adjacency list) and Dijkstra's (lazy implementation or eager implementation with D-ary heap).
• Spanning Trees: Boruvkas, Kruskal's (edge list), and Prim's (lazy or eager versions).
• Traversal: Breadth-First Search (BFS) and Depth-First Search (DFS).
• Topological Sorting: Kahn's algorithm and general topological sort for acyclic graphs.
• Other: Eulerian Path, Floyd Warshall (adjacency matrix), Steiner Tree, and Traveling Salesman Problem (TSP) using iterative or recursive dynamic programming.

The library provides several algorithms specifically for tree structures:

• Rooting: Rooting an undirected tree.
• Isomorphism: Identifying if two trees are isomorphic.
• Structure: Finding tree centers and the tree diameter.
• Ancestry: Lowest Common Ancestor (LCA) using the Euler tour method (O(1) queries after O(n log n) preprocessing).

For network flow problems, the following implementations are available:

• Bipartite Graphs: Verification using adjacency lists and Maximum Cardinality Bipartite Matching (augmenting path algorithm).
• Max Flow & Min Cut:
  • Ford-Fulkerson (DFS with adjacency list or adjacency matrix).
  • Edmonds-Karp (adjacency list).
  • Capacity Scaling (adjacency list).
  • Dinic's algorithm (adjacency list).
• Min Cost Max Flow:
  • Using Bellman-Ford (adjacency list).
  • Using Johnson's algorithm (adjacency list).

The project uses Bazel as its build system. This is the recommended way to compile and run specific algorithm implementations or run tests.

To run a single algorithm, use bazel run followed by the target path in the format //src/main/java/com/williamfiset/algorithms/<subpackage>:<ClassName>.

To run all tests in the repository, use bazel test //src/test/....

To run tests for a specific package, use bazel test //src/test/java/com/williamfiset/algorithms/<package>:all.

# Run a single algorithm
bazel run //src/main/java/com/williamfiset/algorithms/search:BinarySearch

# Run all tests
bazel test //src/test/...

# Run tests for a specific package
bazel test //src/test/java/com/williamfiset/algorithms/sorting:all

If you do not want to use Bazel, you can use a standard JDK (version 8 or higher).

1. Create a classes folder: Create a directory named classes to hold compiled files.
2. Compile: Use javac with the -sourcepath pointing to src/main/java and the -d flag pointing to your classes folder.
3. Run: Use java with the -cp (classpath) flag pointing to the classes folder and provide the fully qualified class name.

# 1. Create classes folder
mkdir classes

# 2. Compile the algorithm
javac -sourcepath src/main/java -d classes src/main/java/com/williamfiset/algorithms/search/BinarySearch.java

# 3. Run the algorithm
java -cp classes com.williamfiset.algorithms.search.BinarySearch

The QuadTree class is a spatial data structure used to store and query points with integer coordinates within a defined rectangular region. It supports adding points, counting points within a specific area, and performing k-nearest neighbor (kNN) searches.

Note: This implementation is currently under development.

// Example initialization
QuadTree.Rect region = new QuadTree.Rect(0, 0, 100, 100);
QuadTree qt = new QuadTree(region);

// Adding a point
qt.add(10, 10);

// Counting points in an area
int count = qt.count(new QuadTree.Rect(5, 5, 15, 15));

// Finding k-nearest neighbors
List<QuadTree.Pt> neighbors = qt.kNearestNeighbors(3, 12, 12);