The Design and Analysis of Algorithm Masterclass

Explore the foundations of algorithms as finite, unambiguous instructions that map inputs to outputs in a finite time, distinguish algorithms from programs, and survey analysis and design tools.

Analyze algorithm efficiency through asymptotic notations: big o, big omega, and big theta, understanding growth rates, tight bounds, and constant factors with practical examples.

Examine key big o properties through problem solving, including constants, self, asymptotic notations, transitivity, and multiplicativity. Analyze how logarithms, polynomials, factorials, and log factorial compare in growth.

Relate asymptotic notations to code and analyze running time for input size n. Compare big O, big Omega, and big Theta across constant, linear, and quadratic patterns, including nested loops.

Explore the design and analysis of algorithms, comparing iterative and recursive approaches with linear search and gcd via Euclid, highlighting best, worst, and average cases.

Explore factorial computation through iterative and recursive approaches, analyze base cases and the recursive definition, and understand tail recursion and why iteration is often preferred for efficiency.

Explore solving recurrence relations by substitution, deriving running time, and applying telescoping and back substitution with base cases, including factorial and exponential examples and closed-form results.

Explore the divide and conquer approach with binary search, featuring iterative and recursive versions on sorted arrays, middle-element selection, and recurrence-based time analysis.

Apply the master method to analyze divide and conquer recurrences, including binary search, by comparing a, b, and n^log_b to determine the time complexity.

Learn to tile a defective n×n chessboard with L-shaped polyominoes using a divide-and-conquer algorithm. Analyze the recurrence TI(n)=4 TI(n/2)+theta(1) and prove theta(n^2) runtime.

Master merge sort, a divide-and-conquer stable sorting algorithm that is not in-place, merges two sorted subarrays, uses a single-element base case, and runs in theta(n log n).

Discover the divide-and-conquer power of merge sort to count inversions in an array, by tallying left-half, right-half, and merge-step inversions.

Master quicksort via in-place divide-and-conquer with a rightmost pivot and partitioning. Analyze best-case theta(n log n) and worst-case theta(n^2), with average near 1.38 n log n, and apply quickselect for the k-th smallest element.

Explore dynamic programming to compute the nth Fibonacci number, compare bottom-up tabulation with top-down approach, and see when divide and conquer suffices for independent subproblems.

Explore the rod cutting problem as a dynamic programming optimization, using prices for rod lengths to maximize revenue via the optimal substructure and comparing top-down versus bottom-up approaches.

Learn matrix chain multiplication and solve it with dynamic programming, building a bottom-up table to minimize scalar multiplications and determine the optimal parenthesization of a matrix chain.

Master the longest common subsequence problem via dynamic programming, building a bottom-up table and using two-column space optimization to compute LCS length and relate to edit distance.

Explore greedy algorithms through the knapsack problem, comparing zero-one and fractional variants, and learn how sorting by value per unit weight guides optimal or suboptimal results.

Learn Kruskal's algorithm to find a minimum spanning tree in a weighted graph by sorting edges and adding edges that do not form a cycle to connect all vertices.

Explore disjoint sets and the union-find data structure, including union, find, path compression, and weighted unions, and apply them to Kruskal's algorithm for constructing a minimum spanning tree.

See how disjoint sets enable a greedy scheduling algorithm for job sequencing with deadlines, using union-find and path compression to maximize profit by completing tasks on time.

Explore the heap data structure, its complete binary tree form, and max and min heap properties, with array representations and the max-heap construction from an unsorted array.

Build a max heap from the input array, swap the root with the last unsorted element, and repeatedly max-heapify the remainder to achieve heap sort in O(n log n).

Explore how priority queues can be implemented with min or max heaps, detailing heapify, extract min, decrease key, and insert operations with O(log n) complexity.

Apply greedy prim's algorithm to build a minimum spanning tree from a start vertex using a priority queue, initializing d and p, and performing extract-min and decrease-key operations.

Explore Huffman codes by building a Huffman tree from symbol frequencies using a priority queue, producing optimal prefix codes and analyzing the n log n complexity.

Learn a recursive method to print Huffman codes from a given Huffman tree, outputting each symbol with its corresponding code, handling left and right children and leaf nodes.

Explore the single source shortest path problem with Dijkstra's algorithm on a weighted directed graph, updating distances and routes to reveal the shortest paths from the source to all vertices.

Explore how Dijkstra's algorithm initializes vertex distances to infinity and sets the source distance to zero. It then uses relaxations and a priority queue to propagate the shortest paths.

Analyze Dijkstra's algorithm, its time complexity of O(n log n) with initialization, priority queue creation, and extract-min steps, and note that negative edges may fail it, unlike Bellman-Ford.

Bellman-Ford algorithm computes single-source shortest paths in directed graphs with possible negative weights by iterative edge relaxations and a final negative cycle check.

Learn to compute a topological sort on a directed acyclic graph by visiting vertices with recursion and a stack, producing an order where each edge's source precedes its destination.

Use topological sort to compute single-source shortest paths in a directed acyclic graph, initializing distances and predecessors, then relaxing edges along the sorted order to reveal shortest routes.

The Floyd-Warshall algorithm finds the shortest paths between every pair of vertices in a weighted directed graph by updating a shortest-path matrix through intermediate vertices, illustrated with a three-vertex example.

Explore the string matching problem and how the naive brute force matcher finds all pattern occurrences in a text. Discover why its O(mn) time complexity motivates preprocessing the pattern.

Preprocess the pattern with a finite automaton to speed up string matching, building transitions for abcba over A, B, C and using longest borders to guide shifts.

Explore pattern preprocessing by building the failure/border array F for a pattern, identifying the longest border lengths of prefixes to enable efficient string matching with finite automata.

Learn how the Knuth Morris Pratt string matching algorithm uses pattern preprocessing to guide matching, scans the text efficiently, and finds all pattern occurrences in linear time.

Explore backtracking to solve the n-queens problem, detecting column and diagonal attacks, and using a one dimensional queen array. Implement a place-and-backtrack algorithm that assigns queens row by row.

Explore the n-queens problem on an n by n chessboard using a place algorithm and backtracking to place all queens and enumerate all solutions.

Explore the graph coloring problem with backtracking to produce proper colorings, minimize colors, and understand the chromatic number, using an adjacency matrix and a seating example.

Develop a backtracking algorithm to find all proper colorings of a graph by painting vertices in order, choosing colors for each vertex, and exploring all valid permutations.

presents backtracking to solve the hamiltonian cycles problem on a graph, modeling with an n by n adjacency matrix, visiting every vertex exactly once and returning to the start.

Explore backtracking to enumerate all Hamiltonian cycles in a graph, then apply to the traveling salesman problem to find the minimum-cost Hamiltonian cycle.

Explore the subset sum problem with a backtracking approach, maximize total calories under 700, and relate it to knapsack ideas and branch-and-bound pruning.