Algorithms
Dynamic Programming — Lecture Notes 1. What Is Dynamic Programming? Dynamic programming (DP) is an algorithmic paradigm for solving problems that have overlapping subproblems and optimal substructure. Overlapping subproblems: the subproblems are smaller versions of the original problem. Optimal substructure: the optimal solution to a larger problem contains the optimal solutions to its smaller problems, so the larger problem can be derived from the smaller ones. 2. Example: Climbing Stairs A staircase has $n$ steps. Each move, you can climb 1 or 2 steps. How many distinct ways are there to reach the top?
Read note →1. What Is Breadth-First Search? Core idea: expand level by level Breadth-first search (BFS) is the other classic graph traversal algorithm. Starting from a source vertex, it first visits all of its immediate neighbors — these form the first level. Then it visits, in order, all not-yet-visited neighbors of the first-level nodes — these form the second level. The process resembles the ripples spreading out when a stone is dropped into water: it expands outward one level at a time until every reachable node has been visited. Key data structure: the queue BFS makes perfect use of a queue’s first-in, first-out (FIFO) property to guarantee level-by-level traversal order.
Read note →1. What Is a Graph? Concept: From Trees to Graphs A graph can be understood as an extension and generalization of the tree structure. In fact, a tree is just a special kind of graph. A graph consists of a set of vertices and a set of edges. Each edge connects a pair of vertices in the graph. Graphs can model more complex real-world relationships, and are no longer restricted to the hierarchical relationships of a tree. Applications of Graphs Social networks: individuals or organizations are vertices; the social connections between them are edges. Maps and navigation: key locations (intersections, landmarks) are vertices; roads are edges. Computer networks: computers or routers are vertices; network connections are edges. 2. Key Terminology Undirected Graph Edges have no direction. If there is an edge between vertices A and B, we can travel from A to B and also from B to A.
Read note →1. DFS: From Trees to Graphs Core idea recap: follow one path to the end The core idea of depth-first search (DFS) — explore a branch as deeply as possible, then backtrack when you hit a dead end — carries over to graphs unchanged.
The new challenge: cycles Trees are acyclic. We move from a parent node to its children and never “walk back” to the parent. (For unrooted trees, this is avoided by passing the parent node as a parameter.) General graphs contain cycles. If we travel from u to v, v may well reach back to u along some other path. If this is not handled, DFS will fall into an infinite loop when it hits a cycle, causing a stack overflow. The solution: mark visited nodes We need an auxiliary data structure — typically a boolean array visited — to record which nodes have already been visited. Before visiting a new node, check whether it has been visited already.
Read note →Difference on Trees 1. Concept Tree difference means applying the difference-array technique to a tree structure instead of a linear array. It is almost always used together with LCA (lowest common ancestor).
On an array, prefix sum and difference are inverse operations:
prefix sum <----- inverse -----> difference On a tree, the analogue of “prefix sum” is the subtree sum: after all marks have been placed, the true value at node u equals the sum of the difference values over the whole subtree rooted at u. That aggregation is done with a single post-order DFS.
Read note →Lowest Common Ancestor (LCA) 1. Definition LCA (Lowest Common Ancestor) refers to finding, in a rooted tree, the nearest (deepest) common ancestor of two given nodes x and y.
Using the reference tree below as an example:
LCA(5, 8) = 1 LCA(6, 10) = 3 Reference Tree 1 / \ 2 3 / | \ | \ 11 4 5 6 7 | 8 / \ 9 10 2. Naive Solution Steps:
Read note →Memoization 1. What Is Memoization? Memoization: a way of implementing a search that records information about states it has already visited, so that the same state is never traversed (recomputed) more than once.
Memoization = DFS + an extra dictionary (cache)
If the state has been searched before: look it up in the dictionary and return the stored result directly. If the state has not been searched before: keep searching, and finally record that state’s result into the dictionary. 2. Worked Example — Fibonacci Sequence Problem Define the Fibonacci sequence as:
Read note →Introduction to DFS (Depth-First Search) What is a Search Algorithm? A search algorithm exhaustively explores part or all of the solution space of a problem to find its solution.
Depth-First Search (DFS) Essence: DFS is essentially brute-force enumeration. “Depth-first” principle: Go as far down one path as possible; only backtrack when no further progress can be made. Example: Finding a Path from Node 1 to Node 8 Starting from node 1, always move to an unvisited node if one exists; otherwise, backtrack.
Read note →Two pointers are useful when performing operations on a range: two indices traverse the data simultaneously and exploit the range’s structure. The technique can often reduce $\mathcal{O}(n^2)$ time complexity to $\mathcal{O}(n)$.
Opposite-Direction Scan The left pointer starts at the beginning and continuously moves to the right, while the right pointer starts at the end and continuously moves to the left, until they meet and stop. This is generally used for problems involving sorted arrays or strings.
Read note →Stack A Stack is a special linear data structure that only allows insertion and deletion operations at one end of the structure. This end is called the Top, and the other end is called the Bottom. Stack operations follow the Last-In, First-Out (LIFO) principle. Push Add a new element at the top of the stack.
Pop Remove and return the element at the top of the stack.
Top (Peek) Return the element at the top of the stack without removing it.
Read note →Queue A Queue is a special linear data structure that only allows insertion at one end of the structure and deletion at the other end. The end where insertion occurs is called the Rear, and the end where deletion occurs is called the Front. Queue operations follow the First-In, First-Out (FIFO) principle. Enqueue Add a new element at the rear of the queue.
Dequeue Remove and return the element at the front of the queue.
Read note →What is a Tree? Concept: A Non-Linear Hierarchical Structure Tree is an abstract data type used to simulate data with hierarchical relationships. It consists of n (n ≥ 0) finite nodes. It is a non-linear data structure, in contrast to the linear structures we studied earlier such as lists, stacks, and queues. In a tree structure, there is a special node called the Root. The remaining nodes can be divided into m (m ≥ 0) disjoint sets T₁, T₂, …, Tₘ, each of which is itself a tree, referred to as a Subtree of the root. Real-Life Examples Book table of contents: The book is the root node, chapters are intermediate nodes, and sections are leaf nodes. File system: The root directory is the root node, subdirectories at each level are intermediate nodes, and files are leaf nodes. Key Terminology (Based on the tree diagram with nodes A, B, C, D, E, F, G, H, I, K)
Read note →What is Depth-First Search? Concept: Go All the Way Down One Path Depth-First Search (DFS) is an algorithm for traversing or searching trees or graphs. Its core idea is: starting from the root node, explore each branch as deeply as possible. When exploring along a path and all children of a node have been visited, the algorithm backtracks to that node’s parent and continues exploring any unvisited children. This process is typically implemented using recursion, which naturally uses the function call stack to handle the “going deeper” and “backtracking” phases. Traversal Order The order in which DFS visits nodes is closely tied to the order of recursive calls. It always completes the full exploration of one subtree before moving on to the next sibling subtree.
Read note →Union-Find (Disjoint Set Union) Problem Definition Given N mutually disjoint sets, we need to support two operations:
Merge: Union two sets together Query: Determine whether two elements belong to the same set Example Operation Sequence Elements: a, b, c, d, e, f
Operations: Merge(a,b), Merge(b,e), Merge(c,f), Merge(b,f)
Approach 1: Naive Label-Based Assign each element a set ID. To merge, update all elements of one set to the other’s ID.
Operation a b c d e f Init 1 2 3 4 5 6 Merge(a,b) 1 1 3 4 5 6 Merge(b,e) 1 1 3 4 1 6 Merge(c,f) 1 1 3 4 1 3 Merge(b,f) 1 1 1 4 1 1 Complexity: Query: O(1) | Merge: O(n)
Read note →What is a Linked List? Concept: A Dynamic Data Structure A Linked List is a linear data structure, but its elements are not stored contiguously in memory. It is composed of a series of Nodes, where each node contains two parts: Data field: stores the element’s data. Pointer field: stores the memory address of the next node. This structure — discrete memory blocks chained together via pointers — makes linked lists very efficient for insertion and deletion operations. Comparison with Arrays Array Linked List Memory Contiguous Non-contiguous Access Fast — O(1) Slow — O(n) Insert/Delete Slow — O(n) Fast — O(1) Structure: Nodes and Pointers Singly Linked List The simplest type of linked list. Each node has exactly one pointer pointing to its successor node.
Read note →Concept: A Special Kind of Queue A priority queue is an abstract data type that allows us to store elements and retrieve (usually remove) the minimum or maximum element at any time.
Unlike a regular queue’s “first-in, first-out” principle, a priority queue outputs the highest-priority element first. An element’s “priority” is typically determined by its value. Comparison with Stack and Queue Structure Order Policy Regular Queue First-In, First-Out (FIFO) — cares about insertion order Stack Last-In, First-Out (LIFO) — also cares about insertion order Priority Queue Highest priority out first — cares about the element’s own priority, regardless of insertion order 1. What Is a Heap? A heap is a special data structure based on a complete binary tree, commonly used to implement priority queues.
Read note →Greedy Algorithms Definition: The greedy method decomposes an overall problem into multiple steps. In each step, it selects the optimal solution for the current state until all steps are completed. The choice made in one step does not depend on or affect subsequent steps.
Core Property: By consistently making locally optimal choices, the final result is the globally optimal solution.
If a problem satisfies the core property above, it can be solved using a greedy approach.
Read note →1. Core Concepts Binary search is the standard algorithm for locating a specific element in a sorted sequence. It operates on the divide-and-conquer principle.
Mechanism: Repeatedly halves the search space. By comparing the target with the middle element, we eliminate half of the candidates instantly. Prerequisite: The sequence must be sorted (monotonic). Complexity: Time: $O(\log n)$ (Dramatically faster than the $O(n)$ of linear search). Space: $O(1)$ (Iterative implementation). 2. Python’s bisect Module implementing binary search manually is error-prone (off-by-one errors are common). Python’s bisect module provides a standardized, robust C-optimized implementation.
Read note →Prefix Sum A prefix sum array p is a data structure that helps answer range sum queries efficiently. Given an input array a of length $n$, its prefix sum array p (also of length $n$) is defined as: $$ p[i] = a[0] + a[1] + \dots + a[i] = \sum_{k=0}^{i} a[k] $$ This means $p[i]$ stores the cumulative sum of all elements from the start of the array up to and including index $i$. For example, if:
Read note →Difference Arrays For an array $a$, the difference array $\mathrm{diff}$ is defined as: $$ \mathrm{diff}[i] = a[i] - a[i - 1], \quad \text{where } a[0] = 0. $$ Computing the prefix sums of the difference array restores the original array: $$ \mathrm{diff}[1] + \mathrm{diff}[2] + \dots + \mathrm{diff}[i] = a[1] + (a[2] - a[1]) + \dots + (a[i] - a[i - 1]) = a[i]. $$ To perform range addition on the original array (adding $x$ to all elements in the interval $[l, r]$), the operations on the difference array are: $$ \mathrm{diff}[l] \mathrel{+}= x, \quad \mathrm{diff}[r + 1] \mathrel{-}= x. $$ Two-dimensional Difference Arrays $$ \mathrm{diff}_{i, j} = a_{i, j} - a_{i - 1, j} - a_{i, j - 1} + a_{i - 1, j - 1} $$ To perform range addition between $(x_{1}, y_{1})$ and $(x_{2}, y_{2})$, do
Read note →Quicksort is a Divide and Conquer algorithm.
Divide (Pick Pivot): Choose one element from the array to be the pivot. Conquer (Partition): Rearrange the array so that the pivot is in its final sorted position. All elements smaller than the pivot are placed to its left, and all elements greater than the pivot are placed to its right. (Elements equal to the pivot can go on either side, depending on the scheme). Combine (Recurse): Recursively apply the same strategy to the two smaller subarrays—the one to the left of the pivot’s new position and the one to the right. The “combine” step is trivial as the sorting happens in place. def partition(a, left, right): """ Partitions the subarray a[left...right] using the Lomuto scheme with a[left] as the pivot. Returns the final index of the pivot. """ # The pivot is the first element pivot_value = a[left] # 'idx' will track the boundary of the 'less-than-or-equal-to' partition. # All elements at indices [left+1 ... idx-1] will be <= pivot. idx = left + 1 # Iterate through the array to partition it for i in range(left + 1, right + 1): # If current element is smaller or equal to the pivot if a[i] <= pivot_value: # Move it to the 'less-than' partition a[idx], a[i] = a[i], a[idx] # Expand the 'less-than' partition idx += 1 # At the end, swap the pivot (originally at a[left]) with # the last element of the 'less-than' partition (at a[idx - 1]) # to put the pivot in its final sorted position. pivot_final_index = idx - 1 a[left], a[pivot_final_index] = a[pivot_final_index], a[left] return pivot_final_index def quicksort(a, left, right): """ Sorts the array 'a' in-place from index 'left' to 'right' using the quicksort algorithm. """ if left < right: # Partition the array and get the pivot's final index pivot_index = partition(a, left, right) # Recursively sort the two subarrays quicksort(a, left, pivot_index - 1) # Subarray to the left of pivot quicksort(a, pivot_index + 1, right) # Subarray to the right of pivot
Read note →The algorithm breaks the problem down into smaller, manageable pieces and then reassembles them in a sorted order. This happens in three main phases:
Divide: The list is repeatedly divided in half until you are left with many small lists, each containing only one element. A list with one element is considered, by definition, to be sorted (this is the base case for the recursion). Conquer: This phase is trivial. Since the base-case lists (of one element) are already sorted, there’s no work to do. The real work happens in the “Combine” step. Combine (The “Merge”): This is the core of the algorithm. Merge sort begins to combine (or “merge”) the small, one-element lists back together, two at a time. Crucially, it merges them in sorted order. It then takes those newly sorted lists (now of 2 elements) and merges them together, and so on, until the entire list is reassembled into one final, sorted list. def merge_sort(arr): """ Sorts a list in ascending order using the merge sort algorithm. """ # Base case: A list with 0 or 1 elements is already sorted if len(arr) <= 1: return arr # 1. Divide: Split the list into two halves mid = len(arr) // 2 left_half = arr[:mid] right_half = arr[mid:] # 2. Conquer: Recursively sort each half sorted_left = merge_sort(left_half) sorted_right = merge_sort(right_half) # 3. Combine: Merge the two sorted halves merged = [] i = 0 # Pointer for sorted_left j = 0 # Pointer for sorted_right # Loop while both halves have elements to compare while i < len(sorted_left) and j < len(sorted_right): if sorted_left[i] < sorted_right[j]: merged.append(sorted_left[i]) i += 1 else: merged.append(sorted_right[j]) j += 1 # At this point, one of the halves is empty. # Add all remaining elements from the non-empty half. merged.extend(sorted_left[i:]) merged.extend(sorted_right[j:]) return merged # --- Example Usage --- my_list = [38, 27, 43, 3, 9, 82, 10] print(f"Original list: {my_list}") sorted_list = merge_sort(my_list) print(f"Sorted list: {sorted_list}")
Read note →Bucket sort is a non-comparison sorting algorithm that works by distributing the elements of an array into a number of “buckets.” It is highly efficient when the input data is uniformly distributed (i.e., spread out evenly) across its range.
The algorithm follows these four main steps:
Initialize Buckets: First, create a fixed number of empty buckets (in your case, bucket_count). Scatter: Iterate through the input array. For each element, calculate its proper bucket index (based on its value relative to the min/max values) and place the element into that bucket. Sort Buckets: Go through each bucket, one by one, and sort the elements within it. This is typically done using another algorithm like insertion sort (or, in this case, Python’s built-in sort()). Gather: Finally, concatenate the sorted buckets in order (from bucket 0 to the last bucket) to reassemble the full, sorted array. from itertools import chain def bucket_sort(arr, bucket_count): """ Sorts a list in ascending order using the bucket sort algorithm. """ # 1. Edge case: Handle empty or single-element lists if len(arr) <= 1: return arr # 2. Initialize Buckets & Find Range min_val, max_val = min(arr), max(arr) # Edge case: If all elements are the same, no sorting needed if min_val == max_val: return arr # Calculate the size of each bucket. # The '+1' ensures the range [min_val, max_val] is covered. bucket_size = (max_val - min_val + 1) // bucket_count # Fix for bucket_size becoming 0 if bucket_count > (max_val - min_val) if bucket_size == 0: bucket_size = 1 buckets = [[] for _ in range(bucket_count)] # 3. Scatter: Distribute elements into buckets for x in arr: # Calculate the bucket index for the element idx = (x - min_val) // bucket_size # CRITICAL FIX: Ensure max_val lands in the last bucket idx = min(idx, bucket_count - 1) buckets[idx].append(x) # 4. Sort Buckets: Sort each individual bucket for bucket in buckets: bucket.sort() # Using built-in sort (Timsort) # 5. Gather: Concatenate the sorted buckets return list(chain(*buckets)) # --- Example Usage --- my_list = [0.42, 0.32, 0.33, 0.52, 0.37, 0.47, 0.51] # Using bucket_count = 5 sorted_list = bucket_sort(my_list, 5) print(f"Original list: {my_list}") print(f"Sorted list: {sorted_list}") my_list_2 = [29, 25, 3, 49, 9, 37, 21, 43] # Using bucket_count = 4 sorted_list_2 = bucket_sort(my_list_2, 4) print(f"\nOriginal list: {my_list_2}") print(f"Sorted list: {sorted_list_2}")
Read note →Selection sort works by conceptually dividing the list into two parts:
A sorted subarray, which is built up from left to right at the beginning. An unsorted subarray, which makes up the rest of the list. The algorithm iterates through the list, and at each step $i$ (from $i = 0$ to $n-1$): Find: It finds the smallest element in the unsorted subarray (i.e., from index $i$ to the end). Swap: It swaps that smallest element with the element at the first position of the unsorted subarray (which is index $i$). def selection_sort(arr): """ Sorts a list in ascending order using the selection sort algorithm. """ n = len(arr) # Outer loop: Move the boundary of the sorted subarray # This corresponds to your "i-th position" for i in range(n): # Step 1: Find the index of the smallest element in the # remaining unsorted part (from index i to n-1) min_index = i for j in range(i + 1, n): if arr[j] < arr[min_index]: min_index = j # Step 2: Swap the found smallest element with the # element at the i-th position # This "puts the smallest element" into its final sorted place arr[i], arr[min_index] = arr[min_index], arr[i] # --- Example Usage --- my_list = [64, 25, 12, 22, 11] print(f"Original list: {my_list}") selection_sort(my_list) print(f"Sorted list: {my_list}")
Read note →Start with the second element (at index 1), assuming the first element (at index 0) is already a sorted list of one. Store this current element in a temporary variable (let’s call it the key). Compare the key with the elements in the sorted subarray, moving from right to left (i.e., from index $i-1$ down to 0). Shift any element in the sorted subarray that is greater than the key one position to the right. This opens up a “gap” for the key. Insert the key into the gap once you find an element smaller than it, or when you reach the beginning of the list. Repeat this process, expanding the sorted subarray by one element each time, until the entire list is sorted. def insertion_sort(arr): """ Sorts a list in ascending order using the insertion sort algorithm. """ # Start from the second element (index 1) # The first element (index 0) is treated as the initial sorted part for i in range(1, len(arr)): # Step 2: Store the current element to be inserted key = arr[i] # Step 3 & 4: Move elements of the sorted part (arr[0..i-1]) # that are greater than key, one position to the right j = i - 1 while j >= 0 and key < arr[j]: arr[j + 1] = arr[j] # Shift element to the right j -= 1 # Step 5: Insert the key into its correct position arr[j + 1] = key # --- Example Usage --- my_list = [12, 11, 13, 5, 6] print(f"Original list: {my_list}") insertion_sort(my_list) print(f"Sorted list: {my_list}")
Read note →Make a “pass” through the unsorted part of the list, comparing every pair of adjacent items (from the beginning to the end of the unsorted section). For each pair, if the item on the left is greater than the item on the right, swap them. This moves the larger element one position to the right. After the first full pass, the largest element in the list will have “bubbled up” to the very last position. Repeat the process for the remaining unsorted portion of the list (i.e., from the beginning up to the now-sorted end), making one less comparison each time. Continue until no more swaps are needed. def bubble_sort(arr): """ Sorts a list in ascending order using the bubble sort algorithm. """ n = len(arr) # Outer loop for the number of passes for i in range(n): # A flag to optimize if the list becomes sorted early swapped = False # Inner loop for comparing adjacent elements # The range is (n-i-1) because the last 'i' elements are already in place for j in range(0, n - i - 1): # Compare adjacent elements if arr[j] > arr[j + 1]: # Swap them if the first is greater than the second arr[j], arr[j + 1] = arr[j + 1], arr[j] swapped = True # If no swaps occurred in a full pass, the list is sorted if not swapped: break # --- Example Usage --- my_list = [64, 34, 25, 12, 22, 11, 90] print(f"Original list: {my_list}") bubble_sort(my_list) print(f"Sorted list: {my_list}")
Read note →