Recursion, Backtracking and Dynamic Programming in Python

Download python from python.org, install the Windows version 3.11.x, and add python.exe to the PATH; verify the path via environment variables for the next lecture on IDE installation.

Install Python and set up PyCharm IDE, configure the base interpreter, create a new project, and run a sample program that prints hi.

Explore memory management by comparing stack memory and heap memory, how stack frames store local variables and calls during recursion, and how dynamic allocation and garbage collection shape performance.

Demonstrate how Python uses the stack to track function calls, frames, and local variables, while the heap stores objects and class variables, and how references enable garbage collection.

Learn the core concept of recursion, define base cases to avoid infinite loops, and compare tail and head recursion with a concrete sum example, showing how recursion and iteration relate.

Visualize how recursion uses the stack to track frames, illustrate base cases and backtracking, and show that deep recursion can cause a stack overflow, while tail recursion enables iteration.

Learn how to compute factorials using head recursion in Python, with base cases, recursive calls, and combining subresults to obtain n factorial, illustrated by examples like 5! and 10!.

Visualize factorial function via source code and stack memory, tracing recursive calls and base-case returns to see 5! equals five times four times three times two times one equals 120.

Learn how to compute Fibonacci numbers using head recursion, including base cases and the f(n-1) and f(n-2) formula, and why dynamic programming improves efficiency.

Explore how recursion builds Fibonacci numbers and how stack memory and backtracking operate, illustrating base cases, frames, and returns in a depth-first style.

Explore the towers of Hunua problem, and see how recursion solves it with three pegs, disk rules, and an exponential number of moves, illustrated by a concrete solution and implementation.

Visualize the towers of Hanoi through stack frames and recursion, tracing base case moves of the smallest disk and how Python manages stack memory with parameters A, B, C.

Discover the euclidean algorithm for finding the greatest common divisor of two integers using modulo and recursion. See the base case and how the gcd becomes stable.

Implement the Euclidean algorithm to compute the greatest common divisor, using iterative and recursive approaches, base case with zero, and modulo operations to reduce values.

Explore the key differences between recursion and iteration, showing how recursion uses independent stack frames and cannot mutate outer variables, while iteration enables in‑place changes for backtracking and dynamic programming.

Explore linear search as a method for finding an item in an unsorted list by checking each item one by one until the target is found, illustrating its linear running time.

Implement binary search in Python using recursion, with left, right, and middle indices, base cases for misses, integer division for middle, and left/right subarray decisions for sorted data.

Learn selection algorithms to find the k smallest or largest items with linear time, in-place methods like quickselect and the median of medians, plus online and secretary problem concepts.

Visualize quickselect on a six-item array to find the second smallest item by partitioning around a random pivot and using k prime (k minus one) to guide recursion.

Learn a Python quickselect implementation using a class with partition and selection phases and a random pivot to find the k-th smallest or largest item in a list.

Learn how the median of medians pivot guarantees linear time in quickselect by splitting into five chunks, finding medians via insertion sort, and performing balanced partitioning.

Implement median of medians in Python with a Pythonic quickselect approach. Split into five-item chunks, compute chunk medians, choose a pivot, and partition to find the k-th order statistic.

Introselect, a hybrid that starts with quickselect and falls back to median of medians to guarantee linear-time selection and efficient memory use when pivots are poor.

Explore online selection algorithms and the secretary problem for data streams, and learn the optimal strategy to reject the first n/e items then select the next item surpassing all seen.

Explore binary numbers and decode decimal equivalents by multiplying bits by powers of two. See how 11011 yields 27 and learn about bit capacity and floating point representations.

Explore binary shift operators, left shift and right shift, and how shifting bits changes values from 27 to 54 and 27 to 13, with notes on cryptography and hashing.

Compute the bit length of a decimal integer using a counter and the right shift operator; demonstrate with 412 and 16, showing nine and five bits and logarithmic time.

Backtracking, a form of recursion, finds all solutions to constraint satisfaction problems by pruning invalid partial candidates, often faster than brute force through depth-first search on a game tree.

Compare brute-force search and backtracking using a search tree; backtracking prunes bad states via depth-first search, discarding branches to solve faster, though factorial or exponential running times persist.

implement the n-queens problem by creating a queens class with an n-by-n board initialized to empty values, using backtracking to place one queen per column.

Implement the print function and is_place_valid for the n-queens solver, validating diagonals and rows while printing the board with queens and empty cells to guide backtracking.

Explore how the n-queens problem uses a recursive backtracking solve function to place queens column by column, visualize stack frames, and backtrack on invalid placements.

Visualize the hamiltonian cycle problem with backtracking, visiting every vertex exactly once and returning to the start, while pruning dead ends to speed up the search.

Implement Hamiltonian path and cycle using an adjacency matrix, and solve it via recursive backtracking, feasibility checks, and path backtracking with a path list.

Coloring a graph with four colors demonstrates backtracking, pruning invalid states, and a search-tree approach, illustrating how fixed color counts change the solution.

Implement a graph coloring solver with adjacency matrices, backtracking, and color validity checks to assign colors from one to n for each vertex.

Explore the knight's tour problem on an n by n board by visiting every cell once, relate closed tours to Hamiltonian cycles, and note backtracking amid eight-move exponential search space.

Implement the knight's tour with backtracking, including print_solution and is_valid_move, validating moves on the board and updating the solution matrix to visit every cell exactly once.

Solve an n by n maze with obstacles using backtracking and depth-first search from top-left to bottom-right. See how backtracking backtracks and why Trémeau's approach equals depth-first search.

Visualize the maze problem using a recursive solve method that moves right or down, tracks visited cells, and backtracks via stack frames to reach the destination.

Explore sudoku as a 9x9 grid where each row, column, and 3x3 box contains digits 1 to 9 exactly once, and see how backtracking prunes the search space.

Implement a backtracking sudoku solver by skipping nonempty cells, trying numbers 1-9, validating each placement, backtracking by resetting cells, and printing the solved grid.

Define the is valid function to verify placing a number in a Sudoku cell by checking the column, row, and 3x3 box, enabling backtracking to solve Sudoku in Python.

Explore why brute force is slow, how backtracking reduces to exponential time for np complete and np hard problems, and how metaheuristics like genetic algorithms and simulated annealing offer approximations.

Explore dynamic programming as an optimization technique and programming paradigm that solves problems by breaking them into overlapping subproblems recursively, storing results with memoization or tabulation.

Explore the zero-one knapsack problem through dynamic programming, with binary inclusion decisions, memoization, and a two-dimensional dynamic programming table to maximize value under weight capacity, leveraging optimal substructure.

This lecture demonstrates solving the knapsack problem with a two-dimensional dynamic programming table for three items and a five-kilogram capacity, yielding a maximum profit of $11.

implement the knapsack problem from scratch using dynamic programming, building a dp table with weights, values, and capacity, and applying memoization to find the optimal solution.

Explore the rod cutting problem via recursion and dynamic programming, relate it to the knapsack problem, and use memoization with a two-dimensional DP table to maximize revenue from given prices.

Explore the subset sum problem and its knapsack relation, and learn to decide if integers can sum to a target using recursion and dynamic programming.

Implement the subset sum problem with dynamic programming in Python, building a boolean DP table and applying include-exclude logic to determine and reconstruct the subset for the target sum.

Explore the maximum subarray problem and implement Kadane's algorithm to find the largest sum of consecutive numbers in a one-dimensional array, in linear time using dynamic programming.

Learn how to solve the longest common subsequence problem for two strings using dynamic programming and memoization, handling matching and nonmatching cases with a two-string table and subproblem reuse.

This lecture teaches implementing the longest common subsequence with a dynamic programming two-dimensional table, filling zeros, updating on matches, and backtracking to reconstruct the sequence.

Explore the recursive solution to the longest common subsequence problem, including base cases, matching characters, and exclusion choices, with notes on dynamic programming benefits.

Explore the bin packing problem, an np-complete task of packing items into bins to minimize the number of bins, comparing brute-force, first fit, and first fit decreasing.

Demonstrates the first fit decreasing algorithm for the bin packing problem in Python, showing how to sort items by capacity, create runtime bins, and place items until bins fill.

Binary search uses a divide and conquer approach, selecting the middle element and recursively inspecting left or right subarrays to find the item in logarithmic time.

The algorithm uses recursion and divide-and-conquer to sort a list by splitting into left and right halves until single-item subarrays, then merges them into an ascending Python list.

Explore how merge sort uses recursion and stack memory to split data into left and right subarrays, base-case returns, and merge results into a sorted array.

This lecture explains the closest pair of points problem in the plane, using Euclidean distance and a divide-and-conquer approach that achieves O(n log n) time.

Implement the closest pair of points in Python using a divide-and-conquer approach, with a point class, Euclidean distance, a base brute force case, and a strip optimization for linear time.