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.

Compare head and tail recursion in Python, tail recursion prints n before the recursive call, and explain how a base case prevents stack overflow while head recursion prints after returns.

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.

Transform a factorial head recursion into tail recursion using an accumulator to eliminate stack dependencies, compare base cases and stack frames, and note that Python doesn't optimize tail recursion.

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.

Explore binary search on sorted data, discarding half the items per iteration to achieve logarithmic running time, with comparisons guided by the middle element.

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.

Explore quickselect: a randomized, in-place selection algorithm that partitions an array around a pivot to find kth order statistics, recursing on one side for linear-time average performance.

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.

Explain how pivot choice affects quickselect performance, showing how bad pivots cause n squared time and how median of medians can keep the worst case linear.

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 numbers and the operations: and, or, xor, not, applied bit by bit to integers. See 27 and 15 = 11, 27 or 15 = 31, xor equals 20.

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.

Test parity with binary operations, using xor with 1 to toggle the least significant bit. If x xor 1 equals x + 1, the number is even; otherwise, it's odd.

Explore Russian peasant multiplication using binary operations, doubling the first number and halving the second, handling odd and even cases, and implementing the method with left shift and integer division.

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.

Explore the n-queens problem by placing n queens on an n by n board so they do not attack each other, using backtracking to eliminate bad states.

Explore the search tree representation of the three queens problem, showing how branches and nodes model moves, and how pruning eliminates bad states to speed up backtracking versus brute force.

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.

Explore the Hamiltonian cycle problem in graphs, using adjacency matrices and backtracking to find a path that visits every vertex once, and learn about the NP-complete nature and degree-based checks.

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.

Implement a hamiltonian path solver using backtracking and an adjacency matrix. Ensure each vertex is visited exactly once and only connected vertices are considered.

Discover the coloring problem in graphs, assigning colors to vertices so adjacent ones differ, and learn backtracking techniques, chromatic number concepts, and key applications like bipartite graphs and map coloring.

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.

Learn the Python implementation of the knight's tour on an eight by eight board using backtracking, with x and y move arrays and a solution matrix.

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 sudoku solver using backtracking in Python, defining a 9x9 board with 3x3 boxes, zeros as empty cells, and recursively fill valid numbers to reveal a solution.

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.

Investigate Fibonacci numbers, compare recursion with dynamic programming, and apply memoization using dictionaries to achieve linear time at the cost of extra memory.

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.

Explore the knapsack problem through a recursive solution, including base cases, include/exclude decisions, and a recursion tree, contrasting with dynamic programming.

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.

Implement rod cutting dynamic programming solution in Python by building a two dimensional DP table with length and price data to maximize profit and reconstruct the cuts in metres.

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.

Demonstrate solving the subset sum problem with dynamic programming using a table-based approach to show how five, two, one, and three sum to nine.

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.

Learn divide and conquer: recursion splits problems into independent subproblems to base cases, conquer by merging results, and contrast with dynamic programming for overlapping subproblems.

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.

Explore the merge sort algorithm, a divide-and-conquer, stable, comparison-based sort with n log n time. It uses extra memory for merging and uses insertion sort for small subarrays.

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.

Split the point set by the middle line into left and right subarrays, bound by delta, and sort by x and y to compare adjacent points for a closer pair.

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.