Deep Dive into Algorithms

Explore dynamic programming through a fibonacci example, contrast recursive solutions with base cases, and learn how memoization and dynamic programming reduce exponential time while touching on Binet formula.

Learn how memorization and dynamic programming reduce exponential time in problems like Fibonacci, comparing top-down memorization with bottom-up dynamic programming and handling overlapping subproblems.

Explore the 0/1 knapsack problem through a dynamic programming approach, building a (n+1) by (W+1) DP matrix to maximize value without exceeding capacity, while ignoring items heavier than the knapsack.

Implement the 0/1 knapsack problem with dynamic programming using a (n+1) by (W+1) DP matrix. Read item values and weights, then apply the max transition to compute the optimal value.

Discover how to print all items that yield the maximum value in the 0/1 knapsack problem by backtracking from the last cell and subtracting weights.

Trace the dynamic programming matrix to print the selected items in the 0/1 knapsack problem, starting from the last column and moving upward to reveal chosen weights and values.

Uncover the minimum cost path using dynamic programming on a cost matrix, handling rectangular grids and moves only down or right from (0,0) to (m-1,n-1).

Implement a minimum cost path algorithm using dynamic programming on a user-built cost matrix, computing DP values from the left, top, and diagonal neighbors, and printing the resulting matrix.

Learn how to trace the minimum cost path in a matrix from the end, using left, top, and diagonal moves and handle zero-row or zero-column edge cases.

Develop a dynamic programming method to trace the path of minimum cost, using left, top, and diagonal moves, with backtracking to reveal the optimal route on the cost matrix.

Explore the subset sum problem for non-negative integers using dynamic programming, building a (n+1) by (sum+1) DP matrix to decide if a subset sums to the target.

Demonstrates implementing the subset sum problem with dynamic programming, constructing and filling a boolean DP matrix to verify achievable sums and visualize the DP table.

Reconstruct a subset that sums to the target in the subset sum problem using a dynamic programming table, tracing from top to bottom.

Implement printing all selected items in the subset sum problem using dynamic programming, tracing the matrix from the last column and printing elements, with time and space analysis.

Explore dynamic programming to find the maximum size square submatrix with all ones in a binary matrix, using a DP table built from top, left, and diagonal neighbors.

Use dynamic programming to compute size square submatrix with all ones by filling a DP matrix from input, using the minimum of top, left, and top-left values, then output result.

The lecture explains the longest increasing subsequence via dynamic programming with a one-dimensional dp array, initializing each element as length one and updating dp when a later element is larger.

Implement the longest increasing subsequence with dynamic programming. Initialize dp[i] to 1, read the input sequence, update dp[i] using dp[j]+1 when a[j] < a[i], and print dp.

Learn how to extract the longest increasing subsequence from the DP data by locating the maximum element and its index, printing the LIS, and noting DP gives one optimized subsequence.

Implement recursive printing of the longest increasing subsequence by tracking the maximum element and its index, printing after recursive calls to produce reverse order while updating max element and index.

Delve into the longest common subsequence problem with dynamic programming, building a matrix, filling with matches diagonally and non-matches from top or left, and tracing to reconstruct the subsequence.

Learn to implement the longest common subsequence by building a dp matrix, filling base zeros, and using max of top and left, with diagonal increment on character matches.

Trace the longest common subsequence from the dynamic programming matrix, matching diagonally on equal characters and taking the max of top or left on mismatches, with backtracking for enumeration.

Implement tracing the longest common subsequence using a dynamic programming matrix, reconstruct the subsequence by following top, left, and diagonal moves, and reverse the result for correct order.

Explore the range minimum query and compare five methods: brute force to dynamic programming, segment approaches, sparse table, and lowest common ancestor across multiple queries.

Explore the brute-force range minimum query by selecting a start and end index, iterating through the range, updating the minimum, and printing the result.

Learn how dynamic programming computes range minimum queries by filling a DP matrix, deriving minimums for all ranges, and using upper triangular memory optimization to reduce space.

Explore implementing dynamic programming for range minimum query by building a triangular dp matrix, filling base cases, and answering min range queries using precomputed values.

Learn how a segment tree answers range minimum queries with a bottom-up construction, where leaves hold elements and internal nodes store minimums, using an array representation and size considerations.

Learn how to construct a segment tree by recursively splitting an array into halves, building leaf nodes from input elements, and storing minimums at internal nodes.

This lecture demonstrates implementing a segment tree with a recursive build function that splits the array into left and right halves, sizing with the next power of two.

Compute the range minimum in a constructed segment tree by traversing left and right subtrees, handling complete, partial, and no overlap to return the minimum.

Implement a range minimum query on a constructed segment tree, handling complete, partial, and no overlap with recursive left and right queries to return the minimum value.

Explore range minimum query using a sparse table, building a precomputed minimum table from an example array, and compare brute force, dynamic programming, and segment tree approaches.

Learn to perform range minimum queries on a constructed sparse table by using logarithms to determine the interval, then merge results to obtain the minimum efficiently.

Learn to efficiently fill the sparse table for minimum queries, storing the index of the minimum rather than the value. Build with powers of two to enable fast queries.

Implement range minimum query using a sparse table, including preprocessing with logarithms and power-of-two intervals, then answer queries efficiently. Compare brute-force and dynamic programming approaches.

Learn to represent graphs with adjacency lists for directed and undirected graphs, using an array of linked lists to store adjacent vertices, with proper memory management and source–destination concepts.

Learn to implement adjacency lists for directed and undirected graphs, including graph creation, vertex structures, edge insertion, and head-pointer based storage of adjacency lists.

This lecture covers Hierholzer's algorithm to find an Eulerian circuit in a directed graph, outlining conditions of strong connectivity and equal in and out degrees, and describing a stack-based process.

Learn to implement Hierholzer's algorithm by building a graph, using a stack and a current path to traverse edges, remove visited edges, and output the eulerian circuit in reverse order.

Learn how the union find data structure uses makeset, union, and find to detect cycles in undirected graphs, by merging sets and tracking representative elements.

Learn to implement union-find to detect cycles in a graph by performing union and find operations, tracking set representatives for vertices, and applying unions across graph edges to reveal cycles.

Learn topological sorting to resolve module dependencies and compute a valid installation order, using a set and a stack to visit and backtrack through vertices.

Explore Dijkstra's algorithm for single-source shortest paths on weighted graphs, leveraging a min-heap priority queue and distance and predecessor maps to construct the shortest path.

Explore the Bellman-Ford algorithm for single-source shortest paths, including edge relaxation over B−1 iterations, handling negative weights, and detecting negative cycles with an extra pass.

Dive into the Ford-Fulkerson maximum flow algorithm, defining capacity, flow, residual capacity, and augmented paths, and show how to find them with breadth-first search.

Explore Karger's algorithm, a Monte Carlo randomized method for finding a minimum cut in undirected graphs. It contracts random edges, merges vertices, removes self-loops, and stops when two components remain.

Explore Kruskal's algorithm for building a minimum spanning tree in an undirected weighted graph. Learn the greedy edge selection, edge sorting, and union-find cycle checks to avoid cycles.

Learn how Prim's algorithm builds a minimum spanning tree using a binary heap, a hash map for vertex indexing, and priority queue, with insert, extract minimum, contains, and decrease operations.