Given \(N\), how do I generate all the valid push/pop sequences (or draw all the trees)? I’ll generate the sequence of 1’s and 0’s....
We showed that the number of binary trees with \(N\) nodes is the Catalan numbers. It is also the number of valid push/pop sequences for...
Say we have the numbers from 1 to \(N\) in sequence. We will do a random sequence of pushes and pops into a stack: \(N\) pushes and...
How fast is the iterative version of the Fibonacci algorithm? You’d think it is \(O(n)\), but it’s really \(O(n^{2})\), because for...
In backtracking algorithms, you make a sequence of decisions. Every recursive call will make one decision, and will take as an input...
Given a set \(X\) of positive integers, can you find a subset that sums to \(T\)? The general idea is that you have two choices: Either...
Suppose you have a game on an \(n\times n\) board with some rules and players take turns. Assume no randomness in the game. For most...
Let \(x,y\) be two non-negative integers. We want to compute \(p\), the product: Set p=0 While x > 0: if x is odd: p = p + y x = x/2...
The method: Given a string of, say, length 8, form all 8 rotations of it, and then sort them lexicographically. Then form the 8 letter...
The idea: First assign a number to all the letters of the alphabet. Say A is 41, B is 42, etc. Now let’s say we’re compressing the...
The problem with run length encoding was that our chunk size (e.g. 4 bits) is fixed. This is nonoptimal. With Huffman encoding, we can...
We have a large string (e.g. text file). Usually, ASCII is not the optimal space allocation for the file. There are various schemes for...
We have a string of length \(N\), and wish to find an \(M\) character string in it. Brute Force Keep moving through the string till the...
An R-way trie is a tree where each node has \(R\) children. It’s best described by an example: Each node consists only of two...
A symbol table is an associative array. It’s a good idea to make the keys orderable for performance reasons (it also opens up more...
Bloom filters are an application of hashing. It is a data structure that allows us to check if an object has already been seen (without...
We often want to store an object for quick retrieval, or see if a given object has been observed before in \(O(1)\) time. Let \(U\) be...
A suffix array is an array formed by taking a string, and storing pointers to all the suffixes in the array. As an example, if the...
Least Significant Digit Suppose we have \(N\) strings of length \(W\). The idea behind the LSD sort is to first sort the last “digit”...
Counting Sort Suppose we have \(N\) elements, but we know the elements are drawn from a fixed, finite list (called the alphabet in this...
Mincut Problem An s-t cut is a cut with \(s\) in one set and \(t\) in the other. Call the sets \(A\) and \(B\). Given a digraph, with...
There are many “kinds” of shortest paths. Algorithm Constraint Typical Worst Case Topological Sort No directed cycles \(N+M\) \(N+M\)...
A negative cycle is a directed cycle where the sum of the edge weights is negative. A shortest paths tree exists if and only if there...
Given a digraph, we may wish to find the shortest distance between two nodes, or between a node and all other nodes, etc. Each edge has...
Given a connected graph \(G\), with positive edge weights, the spanning tree is a subgraph \(T\) that is both a tree (connected and...
Applications When looking at code/library dependencies, one may want to see which code pieces form strongly connected components, and...
Topological Sort A topological sort is a traversal of a digraph with ordering constraints. Let each node have some value/weight. It is a...
A cut of a graph is a partitioning of the nodes into two nonempty sets. A minimum cut is a cut that minimizes the number of edges...
In grade school we learn an algorithm for multiplying two \(N\) digit integers. Let our basic operation to be the multiplication or...
Given \(N\) rectangles, find all the intersections. This algorithm is very similar to the 1-D line intersection search. The difference...
Suppose we have \(N\) 1-D intervals of the form \((a,b)\) where \(a
This is like the 1-D range search, but where the keys can now have two coordinates. It’s finding the number of points in a rectangle...
Sample problems we want to solve: What are all the keys between two keys? (Relevant to databases) How many keys exist between two keys?...
We introduced 2-3 trees with highly desirable properties. Here we’ll convert them into binary trees while maintaining all the...
A 2-node is like a regular node in a binary search tree: It has one key and two children. A 3-node has 2 keys and 3 children. The middle...
A binary search tree is a fairly useful structure for storing ordered data. The invariant for a binary search tree is straightforward:...
One way to sort a list is to use the heap data structure. Given an array of \(N\) unsorted elements, build a max heap in place. Start...
At times we want a structure similar to a queue or stack, but instead of LIFO or FIFO, we want it to pop the maximum element each time....
Sometimes we wish to find the k-th largest element in a list. Brute Force A brute force way to do this would be to sort the list and...
A quick sort works recursively: Shuffle the list. This protects against a carefully crafted input that will make the algorithm...
Say you have \(N\) points on a Euclidean plane. You want to find the polygon with the smallest area that can be formed connecting a...
Any comparison based sorting algorithm must use at least \(\lg(N!)\sim N\lg N\) comparisons for the worst case. This is absent any...
Suppose we have \(N\) points in a plane, and we wish to find the closest pair. The brute force algorithm takes \(\Theta(N^{2})\). We can...
Why would we want to count the number of inversions? One application may be to see how close two different people’s rankings of the same...
A merge sort works recursively: Split the list into two roughly equal halves. Sort each half using mergesort. Merge the two...
When using a random number generator for shuffling, be wary of simple issues. Using cards as an example: If the seed is 32 bits, you’ll...
A shell sort works somewhat recursively. It first sorts every \(k\) elements (i.e. the sublist formed by elements 0, \(k\), \(2k\),...
An insertion sort starts from the first element in the list, and then for each element will check with the previous one to see if it is...
An inversion in a list of elements is a pair of elements where the 2nd element is smaller than the first (i.e. the 2nd element would be...
A selection sort starts out by traversing the whole list, finding the minimal element, and swapping it with the first element. It then...
A loop invariant is a statement that holds true just before and after each iteration. It may be violated within the iteration, but the...
NetworkX is a Python library for handling graphs. In [1]: %matplotlib inline In [14]: import networkx as nx import pylab as plt In [3]:...
We wish to find the distance between two nodes \(a\) and \(b\). Let’s generalize this further and find the distance from \(a\) to all...
The depth first search algorithm is a way to traverse all the nodes in a graph. The algorithm is trivial: Start at a given node. Mark it...
A queue is a data structure for holding objects. It is a FIFO structure. It supports two operations: enqueue and dequeue dequeue returns...
An undirected graph is defined by \((V, E)\) where \(V\) is a set of nodes and \(E\) is a set of edges (each edge is an unordered set of...
A stack is a data structure for holding objects. It is a LIFO structure. It supports two operations: pop and push. pop returns (and...
2-Sum Problem Statement Given a set of \(N\) integers, find how many pairs sum to 0. Brute Force Sum all pairs and count whichever sum...
Consider an \(N\times N\) square grid, where all the grids are black. Now let each square in the grid be white with probability \(p\)....
Dynamic Connectivity & Disjoint Sets Given \(N\) nodes, some connected amongst themselves, does a path exist between any two...
An asymptotically positive function \(f(n)\) is one that is always positive for sufficiently large \(n\). A similar definition holds for...