### Compiling FordFulkersonExample.java (Bash)

Source: https://github.com/williamfiset/algorithms/blob/master/slides/graphtheory/scripts/network_flow_max_flow.txt

Compiles the specific Java source file FordFulkersonExample.java located within the network flow examples package using the javac command. This generates the corresponding .class file.

```bash
javac com/williamfiset/algorithms/graphtheory/networkflow/examples/FordFulkersonExample.java
```

--------------------------------

### Executing FordFulkersonExample (Bash)

Source: https://github.com/williamfiset/algorithms/blob/master/slides/graphtheory/scripts/network_flow_max_flow.txt

Executes the compiled Java class FordFulkersonExample using the java command. This runs the network flow example and prints the results to the console, including the max flow and edge details.

```bash
java com/williamfiset/algorithms/graphtheory/networkflow/examples/FordFulkersonExample
```

--------------------------------

### Example: Running Binary Search with Gradle (Subpackage)

Source: https://github.com/williamfiset/algorithms/blob/master/README.md

An example demonstrating how to run the Binary Search algorithm using the Gradle command with the subpackage and class name format.

```Shell
./gradlew run -Palgorithm=search.BinarySearch
```

--------------------------------

### Example: Compiling and Running Binary Search with JDK

Source: https://github.com/williamfiset/algorithms/blob/master/README.md

A combined example showing the commands to compile and then run the Binary Search algorithm manually using only a JDK.

```Shell
$ javac -d classes -sourcepath src/main/java src/main/java/com/williamfiset/algorithms/search/BinarySearch.java
$ java -cp classes com.williamfiset.algorithms.search.BinarySearch
```

--------------------------------

### Example: Running Binary Search with Gradle (Full Class Name)

Source: https://github.com/williamfiset/algorithms/blob/master/README.md

An example demonstrating how to run the Binary Search algorithm using the Gradle command with the fully qualified class name format.

```Shell
./gradlew run -Pmain=com.williamfiset.algorithms.search.BinarySearch
```

--------------------------------

### Setup Phase - Pseudo-code

Source: https://github.com/williamfiset/algorithms/blob/master/slides/graphtheory/scripts/travelling_salesman_problem.txt

Initializes the memoization table for partial tours starting at S and visiting one other node. It iterates through all nodes except S and stores the direct cost from S to each node i in the memo table, using a bitmask representing the visited nodes {S, i}.

```Pseudo-code
function setup(m, S, memo):
  N = m.size
  // Loop through all nodes i
  for i from 0 to N-1:
    // Skip the start node itself
    if i == S:
      continue
    // State: end node is i, visited mask has bits S and i set
    // The mask is (1 << S) | (1 << i)
    memo[i][(1 << S) | (1 << i)] = m[S][i]
```

--------------------------------

### Cloning the Algorithms Repository (Bash)

Source: https://github.com/williamfiset/algorithms/blob/master/slides/graphtheory/scripts/network_flow_max_flow.txt

Clones the William Fiset Algorithms repository from GitHub to the local machine. This command fetches the entire project source code.

```bash
git clone https://github.com/williamfiset/Algorithms
```

--------------------------------

### Using Fenwick Tree for Range Queries and Point Updates - Java

Source: https://github.com/williamfiset/algorithms/blob/master/src/main/java/com/williamfiset/algorithms/datastructures/fenwicktree/README.md

This snippet demonstrates how to use a Fenwick Tree implementation optimized for range queries and point updates. It shows initialization with a 1-based array, performing range sum queries using `sum`, adding a value to a point using `add`, setting a point value using `set`, and getting a point value using `get`. The operations are shown with example values and expected outputs.

```java
// The values array must be one based
long[] values = {0,1,2,2,4};
//               ^ first element does not get used
  
FenwickTreeRangeQueryPointUpdate ft = new FenwickTreeRangeQueryPointUpdate(values);

ft.sum(1, 4); // 9, sum all numbers in interval [1, 4] in O(log(n))
ft.add(3, 1); // Adds +1 to index 3.

ft.sum(1, 4); // 10, sum all numbers in interval [1, 4]
ft.set(4, 0); // Set index 4  to have value zero.

ft.sum(1, 4); // 6, sum all numbers in interval [1, 4]
ft.get(2);    // 2, Get the value at index 2, this is the same as .sum(2, 2)
```

--------------------------------

### Changing Directory to Algorithms Repo (Bash)

Source: https://github.com/williamfiset/algorithms/blob/master/slides/graphtheory/scripts/network_flow_max_flow.txt

Changes the current working directory to the base directory of the recently cloned Algorithms repository. This is necessary to access the project files.

```bash
cd Algorithms
```

--------------------------------

### Initialize BFS Queue and Visited State (Pseudocode)

Source: https://github.com/williamfiset/algorithms/blob/master/slides/graphtheory/scripts/bfs_grid_shortest_path.txt

Initializes the BFS by adding the starting cell's coordinates (sr, sc) to the row and column queues (rq and cq) respectively. It also marks the starting cell as visited in the visited matrix to prevent revisiting it during the search.

```Pseudocode
add sr to rq
add sc to cq
mark (sr, sc) as visited
```

--------------------------------

### Using Fenwick Tree for Range Updates and Point Queries - Java

Source: https://github.com/williamfiset/algorithms/blob/master/src/main/java/com/williamfiset/algorithms/datastructures/fenwicktree/README.md

This snippet demonstrates how to use a Fenwick Tree implementation optimized for range updates and point queries. It shows initialization with a 1-based array, performing range updates using `updateRange`, and querying point values using `get`. The operations are shown with example values and expected outputs.

```java
// The values array must be one based
long[] values = {0,+1,-2,+3,-4,+5,-6};
//               ^ first element does not get used
  
FenwickTreeRangeUpdatePointQuery ft = new FenwickTreeRangeUpdatePointQuery(values);

ft.updateRange(1, 4, 10); // Add +10 to interval [1, 4] in O(log(n))
ft.get(1); // 11
ft.get(4); // 6
ft.get(5); // 5

ft.updateRange(3, 6, -20); // Add -20 to interval [3, 6] in O(log(n))
ft.get(3); // -7
ft.get(4); // -14
ft.get(5); // -15
```

--------------------------------

### Overall TSP Solver Structure - Pseudo-code

Source: https://github.com/williamfiset/algorithms/blob/master/slides/graphtheory/scripts/travelling_salesman_problem.txt

Outlines the main function for solving the TSP using Dynamic Programming. It takes the adjacency matrix 'm' and start node 'S' as input, initializes the memoization table, and calls helper functions for setup, solving the DP, finding the minimum cost, and reconstructing the optimal tour.

```Pseudo-code
function solveTSP(m, S):
  N = m.size
  // Initialize memo table of size N x 2^N with nulls
  memo = initialize 2D table (N, 1 << N) with nulls
  setup(m, S, memo)
  solve(m, S, memo)
  minCost = findMinCost(m, S, memo)
  // findOptimalTour(m, S, memo) is also called but not detailed here
  return minCost
```

--------------------------------

### Finding Connected Components using DFS - Pseudo-code

Source: https://github.com/williamfiset/algorithms/blob/master/slides/graphtheory/scripts/depth_first_search.txt

This snippet demonstrates how to use DFS to find and count connected components in a graph. It iterates through all nodes, starting a new DFS whenever an unvisited node is encountered. Each DFS traversal explores an entire component, marking all nodes within it with the same component ID and incrementing the component count.

```Pseudo-code
// Variables
n = number of nodes
g = adjacency list
count = 0
components = integer array of size n
visited = boolean array of size n, all false

// Main function
findComponents():
  for i from 0 to n-1:
    if not visited[i]:
      DFS(i, count)
      count++
  return count, components

// DFS function for components
DFS(at, componentId):
  visited[at] = true
  components[at] = componentId

  for neighbor in g[at]:
    if not visited[neighbor]:
      DFS(neighbor, componentId)
```

--------------------------------

### Implementing Basic Recursive DFS - Pseudo-code

Source: https://github.com/williamfiset/algorithms/blob/master/slides/graphtheory/scripts/depth_first_search.txt

This snippet outlines the core recursive Depth First Search algorithm. It requires an adjacency list representation of the graph, a boolean array to track visited nodes, and a starting node. The function recursively explores unvisited neighbors until no further nodes are reachable from the current path.

```Pseudo-code
// Variables
n = number of nodes
g = adjacency list
visited = boolean array of size n, all false

// Main part
start_node = 0 // Example starting node
DFS(start_node)

// DFS function
DFS(at):
  // Base case: already visited
  if visited[at]:
    return

  // Visit node
  visited[at] = true

  // Explore neighbors
  for neighbor in g[at]:
    DFS(neighbor)
```

--------------------------------

### Recursive Tree Building (DFS)

Source: https://github.com/williamfiset/algorithms/blob/master/slides/graphtheory/scripts/trees.txt

Performs a depth-first search traversal starting from the current node to build the rooted tree structure. It iterates through the neighbors of the current node, ensuring not to traverse back to the parent, creates new child nodes, adds them to the current node's children list, and recursively calls itself for each child.

```Pseudocode
function buildTree(graph g, TreeNode curr, TreeNode parent) {
  for (int childId : g.neighbors(curr.id)) {
    // Avoid adding edge pointing back to parent
    if (parent != null && childId == parent.id) continue

    TreeNode child = new TreeNode(childId, curr, new List<TreeNode>())
    curr.children.add(child)
    buildTree(g, child, curr) // Recurse
  }
  return curr
}
```

--------------------------------

### Fenwick Tree - Range Queries and Point Updates (Java)

Source: https://github.com/williamfiset/algorithms/blob/master/slides/datastructures/fenwicktree/README.md

This snippet demonstrates initializing and using a Fenwick Tree implementation optimized for range queries and point updates. It shows how to query the sum of values in a range, add a value to a specific index, set a value at an index, and get the value at an index. The values array is 1-based.

```java

// The values array must be one based
long[] values = {0,1,2,2,4};
//               ^ first element does not get used
  
FenwickTreeRangeQueryPointUpdate ft = new FenwickTreeRangeQueryPointUpdate(values);

ft.sum(1, 4); // 9, sum all numbers in interval [1, 4] in O(log(n))
ft.add(3, 1); // Adds +1 to index 3.

ft.sum(1, 4); // 10, sum all numbers in interval [1, 4]
ft.set(4, 0); // Set index 4  to have value zero.

ft.sum(1, 4); // 6, sum all numbers in interval [1, 4]
ft.get(2);    // 2, Get the value at index 2, this is the same as .sum(2, 2)

```

--------------------------------

### Declare BFS Variables (Pseudocode)

Source: https://github.com/williamfiset/algorithms/blob/master/slides/graphtheory/scripts/bfs_grid_shortest_path.txt

Declares the necessary variables for implementing the BFS algorithm to solve the dungeon escape problem. This includes grid dimensions, the grid itself, start coordinates, queues for row and column indices, variables to track steps and layer progress, a flag for reaching the end, a visited matrix, and direction vectors.

```Pseudocode
R, C // number of rows and columns
m // input character matrix
sr, sc // start row and column
rq, cq // row queue and column queue
move_count // steps taken
nodes_left_in_layer // nodes to dequeue in current layer
nodes_in_next_layer // nodes added in next layer
reached_end // boolean flag
visited // visited matrix
dr, dc // direction vectors (north, south, east, west)
```

--------------------------------

### Public Insert Method - AVL Tree - Pseudocode

Source: https://github.com/williamfiset/algorithms/blob/master/slides/datastructures/avltree/script.txt

The public facing method for inserting a value into the AVL tree. It first checks if the value is null or already exists in the tree to prevent duplicates, returning false if either condition is met. Otherwise, it initiates the recursive insertion process starting from the root.

```Pseudocode
method insert(value):
    if value is null or value exists in tree:
        return false
    root = recursiveInsert(root, value)
    return true
```

--------------------------------

### Solve Phase - Main Loop Structure - Pseudo-code

Source: https://github.com/williamfiset/algorithms/blob/master/slides/graphtheory/scripts/travelling_salesman_problem.txt

The core of the DP solution. It iterates through increasing sizes of partial tours (r), from 3 up to N. For each size r, it considers all possible subsets of r nodes that include the start node S, generated by a combinations function.

```Pseudo-code
function solve(m, S, memo):
  N = m.size
  // Iterate through partial tour sizes r from 3 to N (inclusive)
  for r from 3 to N:
    // Generate all bit sets of size N with r bits set (subsets)
    for subset in combinations(N, r):
      // Ensure the start node S is part of the current subset
      if notIn(S, subset):
        continue
      // Process this valid subset...
```

--------------------------------

### Finalizing TSP Tour - Finding Minimum Cost - Pseudo-code

Source: https://github.com/williamfiset/algorithms/blob/master/slides/graphtheory/scripts/travelling_salesman_problem.txt

After the main solve loop completes, this step finds the overall minimum cost for a complete tour. It iterates through all possible end nodes (excluding the start node S) in the final state (where all nodes are visited, represented by a mask of all 1s) and adds the cost of returning from that end node back to the start node S, minimizing this total cost.

```Pseudo-code
// After solve(m, S, memo) is complete:
function findMinCost(m, S, memo):
  N = m.size
  // The final state where all nodes are visited (mask with all N bits set)
  finalState = (1 << N) - 1
  minTourCost = infinity // Initialize with a very large value

  // Iterate through all possible end nodes (0 to N-1)
  for endNode from 0 to N-1:
    // The end node of the full tour cannot be the start node S
    if endNode == S:
      continue

    // Lookup the cost of the partial tour ending at endNode in the final state mask
    tourCost = memo[endNode][finalState]

    // If a valid tour cost exists for this endNode in the final state
    if tourCost != null:
      // Add the cost of returning from the endNode back to the start node S
      totalCost = tourCost + m[endNode][S]

      // Update the overall minimum tour cost found so far
      minTourCost = min(minTourCost, totalCost)

  return minTourCost
```

--------------------------------

### Running Java Algorithm with Gradle (Subpackage)

Source: https://github.com/williamfiset/algorithms/blob/master/README.md

Use this command with Gradle to run a specific algorithm class by specifying its subpackage and class name. Replace placeholders with the actual algorithm details. On Windows, use `gradlew.bat` instead of `./gradlew`.

```Shell
./gradlew run -Palgorithm=<algorithm-subpackage>.<algorithm-class>
```

--------------------------------

### Running Java Algorithm with Gradle (Full Class Name)

Source: https://github.com/williamfiset/algorithms/blob/master/README.md

Alternatively, run an algorithm using Gradle by providing the fully qualified class name. Replace the placeholder with the complete package and class name. On Windows, use `gradlew.bat` instead of `./gradlew`.

```Shell
./gradlew run -Pmain=<algorithm-fully-qualified-class-name>
```

--------------------------------

### Creating Classes Directory for JDK Compile

Source: https://github.com/williamfiset/algorithms/blob/master/README.md

Navigate to the project root and create a directory named 'classes' to store compiled Java files when compiling manually with a JDK.

```Shell
cd Algorithms
mkdir classes
```

--------------------------------

### Rooting a Tree Function

Source: https://github.com/williamfiset/algorithms/blob/master/slides/graphtheory/scripts/trees.txt

Initiates the tree rooting process. It takes the original graph (tree) and the ID of the desired root node as input. It creates the root node object and calls the recursive buildTree function to construct the rest of the rooted tree.

```Pseudocode
function rootTree(graph g, int rootId) {
  TreeNode root = new TreeNode(rootId, null, new List<TreeNode>())
  buildTree(g, root, null)
  return root
}
```

--------------------------------

### Compiling Java Algorithm with JDK

Source: https://github.com/williamfiset/algorithms/blob/master/README.md

Compile a specific Java algorithm source file using the `javac` command. This command compiles the source file from `src/main/java` and places the output `.class` file into the `classes` directory.

```Shell
javac -sourcepath src/main/java -d classes src/main/java/ <relative-path-to-java-source-file>
```

--------------------------------

### Running Compiled Java Algorithm with JDK

Source: https://github.com/williamfiset/algorithms/blob/master/README.md

Execute a compiled Java algorithm class using the `java` command. The `-cp classes` option tells the JVM to look for classes in the 'classes' directory.

```Shell
java -cp classes <class-fully-qualified-name>
```

--------------------------------

### Implementing Prim's MST (Eager, Adjacency List) in Java

Source: https://github.com/williamfiset/algorithms/blob/master/README.md

Provides an eager implementation of Prim's algorithm to find the Minimum Spanning Tree (MST) using an adjacency list. Has a time complexity of O(Elog(V)).

```Java
src/main/java/com/williamfiset/algorithms/graphtheory/EagerPrimsAdjacencyList.java
```

--------------------------------

### Demonstrating Red-Black Tree Operations in Java

Source: https://github.com/williamfiset/algorithms/blob/master/slides/datastructures/redblacktree/README.md

This snippet initializes a RedBlackTree of Integers, inserts random numbers into it, attempts to remove a specific element (5), and then checks if that element is still present in the tree. It showcases basic insert, remove, and contains operations.

```java
RedBlackTree<Integer> tree = new RedBlackTree<>();

int numElements = 15;
for (int i = 0; i < numElements; i++) {
  int randNumber = (int)(Math.random() * 100);
  tree.insert(randNumber);
}

// Remove element 5 if it exists in the tree
tree.remove(5);

// Check if element 5 is inside the tree
System.out.println("Tree contains element 5: " + tree.contains(5));
```

--------------------------------

### Implementing Bellman-Ford (Edge List, Optimized) in Java

Source: https://github.com/williamfiset/algorithms/blob/master/README.md

Provides a fast and optimized implementation of the Bellman-Ford algorithm using an edge list representation. Supports detection of negative cycles and has a time complexity of O(VE).

```Java
src/main/java/com/williamfiset/algorithms/graphtheory/BellmanFordEdgeList.java
```

--------------------------------

### Finding Strongly Connected Components (Kosaraju's, Adjacency List) in Java

Source: https://github.com/williamfiset/algorithms/blob/master/README.md

Implements Kosaraju's algorithm to find strongly connected components (SCCs) in a directed graph using an adjacency list. Has a time complexity of O(V+E).

```Java
src/main/java/com/williamfiset/algorithms/graphtheory/Kosaraju.java
```

--------------------------------

### Performing Breadth First Search (Adjacency List, Fast Queue) in Java

Source: https://github.com/williamfiset/algorithms/blob/master/README.md

Provides an iterative implementation of Breadth First Search (BFS) using an adjacency list and an optimized fast queue. Has a time complexity of O(V+E).

```Java
src/main/java/com/williamfiset/algorithms/graphtheory/BreadthFirstSearchAdjacencyListIterativeFastQueue.java
```

--------------------------------

### Implementing Dijkstra's Shortest Path (Adjacency List, Eager + D-ary Heap) in Java

Source: https://github.com/williamfiset/algorithms/blob/master/README.md

Provides an eager implementation of Dijkstra's algorithm using an adjacency list and a D-ary heap for optimized performance. Has a time complexity of O(Elogₚₑₖ(V)).

```Java
src/main/java/com/williamfiset/algorithms/graphtheory/DijkstrasShortestPathAdjacencyListWithDHeap.java
```

--------------------------------

### Performing Depth First Search (Adjacency List, Iterative, Fast Stack) in Java

Source: https://github.com/williamfiset/algorithms/blob/master/README.md

Provides an iterative implementation of Depth First Search (DFS) using an adjacency list and an optimized fast stack. Has a time complexity of O(V+E).

```Java
src/main/java/com/williamfiset/algorithms/graphtheory/DepthFirstSearchAdjacencyListIterativeFastStack.java
```

--------------------------------

### Balance Node - AVL Tree - Pseudocode

Source: https://github.com/williamfiset/algorithms/blob/master/slides/datastructures/avltree/script.txt

This method checks if a node is unbalanced (balance factor is -2 or +2) and performs the necessary rotations to restore the AVL property. It identifies the specific case (Left-Left, Left-Right, Right-Right, Right-Left) based on the node's balance factor and its child's balance factor, then applies the appropriate rotation(s). If the node is balanced (+1, 0, or -1), it returns the node unchanged.

```Pseudocode
method balance(node):
    if node.balanceFactor == -2: // Left heavy
        if node.left.balanceFactor <= 0: // Left-Left case
            return rightRotation(node)
        else: // Left-Right case
            node.left = leftRotation(node.left)
            return rightRotation(node)
    else if node.balanceFactor == +2: // Right heavy
        if node.right.balanceFactor >= 0: // Right-Right case
            return leftRotation(node)
        else: // Right-Left case
            node.right = rightRotation(node.right)
            return leftRotation(node)
    // Already balanced (+1, 0, -1)
    return node
```

--------------------------------

### Recursive Insert Method - AVL Tree - Pseudocode

Source: https://github.com/williamfiset/algorithms/blob/master/slides/datastructures/avltree/script.txt

The private recursive method responsible for traversing the tree and inserting the new node. It handles the base case (inserting at a null node), recursively calls itself on the appropriate subtree based on comparison, and then updates the node's height and balance factor before rebalancing the tree on the return path.

```Pseudocode
method recursiveInsert(node, value):
    if node is null:
        return new Node(value)
    comparator = compare(value, node.value)
    if comparator < 0:
        node.left = recursiveInsert(node.left, value)
    else if comparator > 0:
        node.right = recursiveInsert(node.right, value)
    // else comparator == 0, value exists, handled by public insert

    update(node) // Update height and balance factor
    return balance(node) // Rebalance and return new root of subtree
```

--------------------------------

### Implementing Floyd Warshall (Adjacency Matrix) in Java

Source: https://github.com/williamfiset/algorithms/blob/master/README.md

Implements the Floyd-Warshall algorithm for all-pairs shortest paths using an adjacency matrix. Includes negative cycle detection and has a time complexity of O(V³).

```Java
src/main/java/com/williamfiset/algorithms/graphtheory/FloydWarshallSolver.java
```

--------------------------------

### Finding Connected Components (Adjacency List, DFS) in Java

Source: https://github.com/williamfiset/algorithms/blob/master/README.md

Implements an algorithm to find connected components in a graph using an adjacency list and Depth First Search (DFS). Has a time complexity of O(V+E).

```Java
src/main/java/com/williamfiset/algorithms/graphtheory/ConnectedComponentsDfsSolverAdjacencyList.java
```

--------------------------------

### Implementing Prim's MST (Lazy, Adjacency Matrix) in Java

Source: https://github.com/williamfiset/algorithms/blob/master/README.md

Provides a lazy implementation of Prim's algorithm to find the Minimum Spanning Tree (MST) using an adjacency matrix. Has a time complexity of O(V²).

```Java
src/main/java/com/williamfiset/algorithms/graphtheory/LazyPrimsAdjacencyMatrix.java
```

--------------------------------

### Implementing Steiner Tree Algorithm in Java

Source: https://github.com/williamfiset/algorithms/blob/master/README.md

Implements an algorithm for the Steiner tree problem, which is a generalization of the Minimum Spanning Tree problem. Has a time complexity of O(V³ + V² * 2ⁿ + V * 3ⁿ), where T is the number of terminals.

```Java
src/main/java/com/williamfiset/algorithms/graphtheory/SteinerTree.java
```

--------------------------------

### Find Node for Removal - BST/AVL - Pseudocode

Source: https://github.com/williamfiset/algorithms/blob/master/slides/datastructures/avltree/script.txt

The initial step in removing a node from a BST or AVL tree involves searching for the node containing the target value. This recursive method traverses the tree based on comparisons until the node is found or a null node is encountered, indicating the value is not present.

```Pseudocode
method findNodeToRemove(node, value):
    if node is null:
        return null // Value not found
    comparator = compare(value, node.value)
    if comparator < 0:
        return findNodeToRemove(node.left, value)
    else if comparator > 0:
        return findNodeToRemove(node.right, value)
    else: // comparator == 0
        return node // Found the node to remove
```

--------------------------------

### Update Node Height and Balance Factor - AVL Tree - Pseudocode

Source: https://github.com/williamfiset/algorithms/blob/master/slides/datastructures/avltree/script.txt

This method recalculates and updates the height and balance factor for a given node. The height is determined by the maximum height of its left and right subtrees plus one (using -1 for null children). The balance factor is the difference between the right subtree's height and the left subtree's height.

```Pseudocode
method update(node):
    leftHeight = height(node.left) // Use -1 for null nodes
    rightHeight = height(node.right) // Use -1 for null nodes
    node.height = max(leftHeight, rightHeight) + 1
    node.balanceFactor = rightHeight - leftHeight
```

--------------------------------

### Implementing Prim's MST (Lazy, Adjacency List) in Java

Source: https://github.com/williamfiset/algorithms/blob/master/README.md

Provides a lazy implementation of Prim's algorithm to find the Minimum Spanning Tree (MST) using an adjacency list. Has a time complexity of O(Elog(E)).

```Java
src/main/java/com/williamfiset/algorithms/graphtheory/LazyPrimsAdjacencyList.java
```

--------------------------------

### Performing Topological Sort (Kahn's Algorithm, Adjacency List) in Java

Source: https://github.com/williamfiset/algorithms/blob/master/README.md

Implements Kahn's algorithm for topological sorting of a directed acyclic graph (DAG) using an adjacency list. Has a time complexity of O(E+V).

```Java
src/main/java/com/williamfiset/algorithms/graphtheory/Kahns.java
```

--------------------------------

### Calculating Leaf Node Sum using DFS - Pseudo-code

Source: https://github.com/williamfiset/algorithms/blob/master/slides/graphtheory/scripts/trees.txt

This pseudo-code implements a recursive Depth First Search (DFS) algorithm to calculate the sum of all leaf node values in a tree. It handles the base case of a null node and a leaf node, recursively summing the results from the left and right subtrees.

```Pseudo-code
leafSum(node):
  if node is null:
    return 0
  if node is a leaf:
    return node.value
  return leafSum(node.left) + leafSum(node.right)
```

--------------------------------

### Implementing Bellman-Ford (Adjacency List) in Java

Source: https://github.com/williamfiset/algorithms/blob/master/README.md

Implements the Bellman-Ford algorithm for single-source shortest paths using an adjacency list. Supports detection of negative cycles and has a time complexity of O(VE).

```Java
src/main/java/com/williamfiset/algorithms/graphtheory/BellmanFordAdjacencyList.java
```

--------------------------------

### Finding Connected Components (Adjacency List, Union Find) in Java

Source: https://github.com/williamfiset/algorithms/blob/master/README.md

Implements an algorithm to find connected components in a graph using an adjacency list and the Union-Find data structure. Has a time complexity of O(Elog(E)).

```Java
src/main/java/com/williamfiset/algorithms/graphtheory/ConnectedComponentsAdjacencyList.java
```

--------------------------------

### Performing Breadth First Search (Adjacency List, Iterative) in Java

Source: https://github.com/williamfiset/algorithms/blob/master/README.md

Provides an iterative implementation of Breadth First Search (BFS) for graphs represented by an adjacency list. Has a time complexity of O(V+E).

```Java
src/main/java/com/williamfiset/algorithms/graphtheory/BreadthFirstSearchAdjacencyListIterative.java
```

--------------------------------

### Performing Depth First Search (Adjacency List, Iterative) in Java

Source: https://github.com/williamfiset/algorithms/blob/master/README.md

Provides an iterative implementation of Depth First Search (DFS) for graphs represented by an adjacency list. Has a time complexity of O(V+E).

```Java
src/main/java/com/williamfiset/algorithms/graphtheory/DepthFirstSearchAdjacencyListIterative.java
```

--------------------------------

### TreeNode Object Structure

Source: https://github.com/williamfiset/algorithms/blob/master/slides/graphtheory/scripts/trees.txt

Defines the structure for a node in the rooted tree. Each node has a unique integer ID, an optional reference to its parent node, and a list of its child nodes.

```Pseudocode
object TreeNode {
  int id
  TreeNode parent // optional
  List<TreeNode> children
}
```

--------------------------------

### Performing Depth First Search (Adjacency List, Recursive) in Java

Source: https://github.com/williamfiset/algorithms/blob/master/README.md

Provides a recursive implementation of Depth First Search (DFS) for graphs represented by an adjacency list. Has a time complexity of O(V+E).

```Java
src/main/java/com/williamfiset/algorithms/graphtheory/DepthFirstSearchAdjacencyListRecursive.java
```

--------------------------------

### Fenwick Tree - Range Updates and Point Queries (Java)

Source: https://github.com/williamfiset/algorithms/blob/master/slides/datastructures/fenwicktree/README.md

This snippet demonstrates initializing and using a Fenwick Tree implementation optimized for range updates and point queries. It shows how to apply updates to a range of indices and retrieve the value at a specific index after updates. The values array is 1-based.

```java

// The values array must be one based
long[] values = {0,+1,-2,+3,-4,+5,-6};
//               ^ first element does not get used
  
FenwickTreeRangeUpdatePointQuery ft = new FenwickTreeRangeUpdatePointQuery(values);

ft.updateRange(1, 4, 10); // Add +10 to interval [1, 4] in O(log(n))
ft.get(1); // 11
ft.get(4); // 6
ft.get(5); // 5

ft.updateRange(3, 6, -20); // Add -20 to interval [1, 4] in O(log(n))
ft.get(3); // -7
ft.get(4); // -14
ft.get(5); // -15

```

--------------------------------

### Finding Articulation Points/Cut Vertices (Adjacency List) in Java

Source: https://github.com/williamfiset/algorithms/blob/master/README.md

Implements the algorithm to find articulation points or cut vertices in a graph represented using an adjacency list. Has a time complexity of O(V+E).

```Java
src/main/java/com/williamfiset/algorithms/graphtheory/ArticulationPointsAdjacencyList.java
```

--------------------------------

### Implementing Kruskal's MST (Edge List, Union Find, Lazy Sort) in Java

Source: https://github.com/williamfiset/algorithms/blob/master/README.md

Implements Kruskal's algorithm for Minimum Spanning Tree (MST) using an edge list, Union-Find, and lazy sorting. Has a time complexity of O(Elog(E)).

```Java
src/main/java/com/williamfiset/algorithms/graphtheory/KruskalsEdgeListPartialSortSolver.java
```

--------------------------------

### Implementing Kruskal's MST (Edge List, Union Find) in Java

Source: https://github.com/williamfiset/algorithms/blob/master/README.md

Implements Kruskal's algorithm to find the Minimum Spanning Tree (MST) using an edge list and the Union-Find data structure. Has a time complexity of O(Elog(E)).

```Java
src/main/java/com/williamfiset/algorithms/graphtheory/KruskalsEdgeList.java
```

--------------------------------

### Left Rotation - AVL Tree - Pseudocode

Source: https://github.com/williamfiset/algorithms/blob/master/slides/datastructures/avltree/script.txt

Performs a standard left rotation operation on the given node. Similar to the right rotation, it is essential to update the height and balance factor for both the original node and the node that becomes the new root of the subtree immediately after the rotation to ensure AVL tree properties are correct.

```Pseudocode
method leftRotation(node):
    // Perform standard BST left rotation
    newRoot = node.right
    node.right = newRoot.left
    newRoot.left = node

    // Update heights and balance factors
    update(node) // Update the old root first
    update(newRoot) // Update the new root

    return newRoot
```

--------------------------------

### Implementing Bellman-Ford (Adjacency Matrix) in Java

Source: https://github.com/williamfiset/algorithms/blob/master/README.md

Implements the Bellman-Ford algorithm using an adjacency matrix representation. Supports detection of negative cycles and has a time complexity of O(V³).

```Java
src/main/java/com/williamfiset/algorithms/graphtheory/BellmanFordAdjacencyMatrix.java
```

--------------------------------

### Finding Eulerian Path (Directed Edges) in Java

Source: https://github.com/williamfiset/algorithms/blob/master/README.md

Implements the algorithm to find an Eulerian path in a directed graph. Has a time complexity of O(E+V).

```Java
src/main/java/com/williamfiset/algorithms/graphtheory/EulerianPathDirectedEdgesAdjacencyList.java
```

--------------------------------

### Right Rotation - AVL Tree - Pseudocode

Source: https://github.com/williamfiset/algorithms/blob/master/slides/datastructures/avltree/script.txt

Performs a standard right rotation operation on the given node. After rearranging the nodes, it is crucial to update the height and balance factor for both the original node and the node that becomes the new root of the subtree to maintain AVL tree properties.

```Pseudocode
method rightRotation(node):
    // Perform standard BST right rotation
    newRoot = node.left
    node.left = newRoot.right
    newRoot.right = node

    // Update heights and balance factors
    update(node) // Update the old root first
    update(newRoot) // Update the new root

    return newRoot
```

--------------------------------

### Implementing Dijkstra's Shortest Path (Adjacency List, Lazy) in Java

Source: https://github.com/williamfiset/algorithms/blob/master/README.md

Provides a lazy implementation of Dijkstra's algorithm for finding the shortest path in a graph using an adjacency list. Has a time complexity of O(Elog(V)).

```Java
src/main/java/com/williamfiset/algorithms/graphtheory/DijkstrasShortestPathAdjacencyList.java
```

--------------------------------

### Solve Phase - Finding Optimal End Node - Pseudo-code

Source: https://github.com/williamfiset/algorithms/blob/master/slides/graphtheory/scripts/travelling_salesman_problem.txt

For a given subset and a fixed 'next' node, this section iterates through all possible 'end' nodes (e) within the 'state' mask (subset excluding 'next'). It looks up the optimal cost for the partial tour ending at 'e' with the 'state' mask, adds the cost from 'e' to 'next', and updates the minimum cost for the current subset ending at 'next' in the memo table.

```Pseudo-code
// Inside solve(m, S, memo) function, within the subset and next loops:
// ... (previous loops for r, subset, next, and state calculation)

// Iterate through all possible 'end' nodes 'e' (0 to N-1)
for e from 0 to N-1:
  // The 'end' node cannot be S, cannot be 'next', and must be in the 'state' mask
  if e == S or e == next or notIn(e, state):
    continue

  // Lookup the cost of the partial tour ending at 'e' with the 'state' mask
  prevCost = memo[e][state]

  // If a valid previous cost exists (i.e., the state is reachable ending at e)
  if prevCost != null:
    // Calculate the new cost by adding the edge from e to next
    newCost = prevCost + m[e][next]

    // Update the minimum cost for the partial tour represented by 'subset' ending at 'next'
    // memo[next][subset] stores this minimum cost
    if memo[next][subset] == null or newCost < memo[next][subset]:
      memo[next][subset] = newCost
```

--------------------------------

### Solve Phase - Processing Subset and Next Node - Pseudo-code

Source: https://github.com/williamfiset/algorithms/blob/master/slides/graphtheory/scripts/travelling_salesman_problem.txt

Inside the subset loop, this section iterates through all possible 'next' nodes that are part of the current subset. For each 'next' node (which cannot be S), it calculates the 'state' mask representing the subset *excluding* the 'next' node. This 'state' is used for memoization lookups.

```Pseudo-code
// Inside solve(m, S, memo) function, within the subset loop:
// for r from 3 to N:
//   for subset in combinations(N, r):
//     if notIn(S, subset): continue

// Iterate through all possible 'next' nodes (0 to N-1)
for next from 0 to N-1:
  // The 'next' node cannot be S and must be in the current subset
  if next == S or notIn(next, subset):
    continue

  // Calculate the state mask by removing the 'next' node's bit from the subset mask
  state = subset ^ (1 << next)

  // Now, find the best end node 'e' for the 'state' partial tour...
```

--------------------------------

### Calculating Graph Diameter (Adjacency List) in Java

Source: https://github.com/williamfiset/algorithms/blob/master/README.md

Implements an algorithm to calculate the diameter of a graph represented using an adjacency list. Has a time complexity of O(VE).

```Java
src/main/java/com/williamfiset/algorithms/graphtheory/GraphDiameter.java
```

--------------------------------

### Finding Bridges/Cut Edges (Adjacency List) in Java

Source: https://github.com/williamfiset/algorithms/blob/master/README.md

Implements the algorithm to find bridges or cut edges in a graph represented using an adjacency list. Has a time complexity of O(V+E).

```Java
src/main/java/com/williamfiset/algorithms/graphtheory/BridgesAdjacencyList.java
```

--------------------------------

### Check if Node is Not In Subset - Pseudo-code

Source: https://github.com/williamfiset/algorithms/blob/master/slides/graphtheory/scripts/travelling_salesman_problem.txt

A helper function that checks if a specific node (represented by its index i) is *not* included in a given subset (represented by a bitmask). It does this by checking if the i-th bit in the subset mask is 0 using bitwise operations.

```Pseudo-code
function notIn(i, subset):
  // Check if the i-th bit is 0 in the subset mask
  // (subset >> i) shifts the i-th bit to the least significant position
  // (& 1) checks if that bit is 0 or 1
  return ((subset >> i) & 1) == 0
```

=== COMPLETE CONTENT === This response contains all available snippets from this library. No additional content exists. Do not make further requests.