Recursion, Backtracking and Dynamic Programming in Java

Explore recursion as solving a problem by smaller subproblems using the same function, with a base case to avoid infinite loops. Identify tail and head recursion and their memory differences.

Study the factorial problem for non-negative integers with head recursion in Java, using a base case at zero and n minus one recursion to compute n, and guard stack overflow.

Visualize stack memory during a recursive factorial in Java, showing how head recursion pushes frames, backtracks at the base case, and reveals the final result.

Compare head recursion and tail recursion in the factorial problem, showing how calculations occur during backtracking versus during recursive calls, using an accumulator and base case n=0.

Compute Fibonacci numbers using head recursion, applying base cases 0 and 1 and the recurrence f(n)=f(n-1)+f(n-2), while noting the repeated calls and performance implications.

Visualize how fibonacci recursion uses stack memory, base cases, and stack frames. See how fib(n) calls fib(n-1) and fib(n-2) and backtracks to return results.

Explore the towers of Hanoi: a three-peg recursion puzzle moving n-1 disks to an auxiliary peg, then the largest to the destination, under top-only moves and exponential time.

Learn how the Euclidean algorithm computes the greatest common divisor using modulo and recursion, with a base case when the remainder is zero and examples like 45 and 10.

Implement the gcd in Java with a recursive Euclidean algorithm, using base case b equals zero and a mod b to reduce to the gcd, illustrated by 48 and 18.

Visualize quickselect’s partition and selection phases to find the second smallest item (k=2, k-1=1) in an array, using random pivots and left-right partitioning.

Apply the median of medians to select the pivot for quickselect, achieving balanced partitions and guaranteed linear time.

Master online selection strategies for the secretary problem, using the odds algorithm to maximize a 1/e (about 37%) chance of selecting the best secretary from a data stream.

Explore bitwise operators on binary values, including and, or, and exclusive or, with examples like 27 and 15, and see how Java applies them bit by bit.

Explore backtracking, a form of recursion, to solve constraint satisfaction problems (n-queens, Sudoku, coloring) by pruning invalid partial candidates through a depth-first search on a game tree.

Apply a backtracking approach to the hamiltonian cycle problem by building a hamiltonian path with an adjacency matrix and validating the last-to-first edge to form a cycle.

Explore the knight's tour: visit every cell on an n by n board exactly once, with a closed tour equaling a Hamiltonian cycle, tackling eight-move exponential running time with backtracking.

Explore knight's tour solving in Java using recursion and backtracking, validating moves to stay on the board and avoid revisiting cells by checking unvisited positions on a chessboard.

Explore the sudoku problem on a nine by nine grid, enforcing digits 1–9 in every row, column, and box, and apply backtracking to prune invalid states in this np-complete search.

Implement a sudoku solver in Java from scratch using a 9x9 board, 3x3 boxes, and a backtracking algorithm with a two-dimensional sudoku table.

Explore Fibonacci numbers, compare recursive and dynamic programming approaches, and introduce memoization to avoid repeated subproblems. Store subproblem results in a hash table for linear time with extra memory.

Explore the knapsack problem solved by recursion, with include and exclude choices, a recursion tree visualization, exponential running time, and the comparison to dynamic programming.

Learn to implement the subset sum problem in Java using dynamic programming with a two-dimensional boolean array, including initialization and solving steps to determine a feasible solution.

Explore the longest common sop sequence problem: find the longest subsequence common to two strings, not necessarily consecutive, using dynamic programming and memoization.

Explore the bin packing problem, a knapsack-like, np-complete optimization, and compare naive brute-force, first fit, and first fit decreasing methods for efficient bin usage.

Execute the bin packing solution by applying the first fit decreasing algorithm in Java, sorting items by volumes, creating bins with a capacity, and placing items into bins.