Algorithms Flashcards
time complexity
the number of elementary instructions a program executes
Big O
upper bound on time (asymptotic performance)
Big Ω
lower bound
Big θ
both O and Ω
3 ways to describe runtime of an algorithm
best case
worst case
expected case
space complexity
amount of memory or space required by an algorithm
data structures
Linked List Tree, Trie and Graph Stack and Queue Heap Vector/ArrayList HashTable
search and sort algorithms
breadth-first search depth-first search binary search merge sort quick sort
steps to handle a technical question
- Listen carefully
- Draw an example
- State a brute force
- Optimize
- Walk through
- Implement
- Test
Look for bottlenecks, unnecessary work and duplicated work.
Linked List
runner technique: two pointers, one runs ahead
many linked list problems rely on recursion
Stack
LIFO: most recent item added is the first to be removed. E.g. stack of dinner plates
Used in some recursive algorithms and to implement a recursive algorithm iteratively.
pop()
push(item)
peek()
isEmpty()
Queue
FIFO: first-in, first-out. E.g. ticket line
Often used in breadth-first search or caches.
add(item)
remove()
peek()
isEmpty()
Tree
data structure comprised of nodes. Has a root node with zero or more child nodes. Each child node has zero or more child nodes. Cannot contain cycles.
Binary Tree
a tree in which each node has up to two children
Binary Search Tree
a binary tree in which every node has a specific ordering property:
all left descendants <= n < all right descendants
Balanced Tree
a tree that is “not terribly imbalanced”. Left and right subtrees do not have to be exactly the same size.
Complete Binary Tree
a binary tree in which every level of the tree is fully filled except for perhaps the last level. The last level is filled left to right.
Full Binary Tree
a binary tree in which every node has either zero or two children. No node has only one child.
Perfect Binary Tree
a binary tree that is both full and complete. All leaf nodes will be at the same level, and this level has the maximum number of nodes.
In-Order Traversal
visit the left branch, the current node, then finally the right branch
Pre-Order Traversal
visit the current node before its child nodes.
Post-Order Traversal
visit the current node after its child nodes
Min-Heap
complete binary tree where each node is smaller than its children. The root is the minimum element in the tree.
Max-Heap
complete binary tree where each node is larger than its children. The root is the maximum element in the tree.
Trie
variant of an n-ary tree in which characters are stored at each node. Each path down the tree may represent a word. Also known as Prefix Tree.
Graph
a collection of nodes with edges between some of them. Can be directed or undirected.
Adjacency List
most common way to represent a graph. Every node stores a list of adjacent vertices.
Depth-First Search
search that starts at the root (or other node) and explores each branch completely before moving on to the next branch. Go deep before going wide. Preferred if we want to visit every node in the graph.
Breadth-First Search
search that starts at the root (or other node) and explores each neighbor before going on to any of their children. Go wide before going deep. Generally better than DFS for finding a path.
DFS steps
- Push the root node on to the stack
- Loop until the stack is empty
- Peek the stack
- If the node has unvisited child nodes, get the unvisited child node, mark it as visited, and push it on the stack
- If the node does not have any unvisited child nodes, pop the node from the stack
DFS algorithm
public void dfs() {
Stack s = new Stack()
s.push(rootNode)
rootNode.visited = true
print(rootNode)
while (!s.isEmpty()) {
Node n = s.peek()
Node child = getUnvisitedChildNode(n)
if (child != null) {
child.visited = true
print(child)
s.push(child)
} else {
s.pop()
}
}
}BFS steps
- Push the root node on to the queue
- Loop until the queue is empty
- Remove the node from the queue
- If the removed node has unvisited child nodes, mark them as visited and insert the unvisited children in the queue
BFS algorithm
public void bfs() {
Queue q = new Queue()
q.add(root)
print(root)
root.visited = true
while (!q.isEmpty()) {
Node n - q.remove()
Node child = null
while (child = getUnvisitedChildNode(n) != null) {
child.visited = true
print(child)
q.add(child)
}
}
}Bottom-Up Approach for recursion
start by knowing how to solve for a simple case. Build the solution for a case off the previous one.
Top-Down Approach for recursion
think about how to divide a problem for a case into subproblems.
Half and Half Approach for recursion
divide the data set in half. Examples are binary search and merge sort.
Dynamic Programming
taking a recursive algorithm, finding the repeated calls and caching the results for future recursive calls.
Bubble Sort
Runtime: O(n²) average and worst case
Memory: O(1)
BubbleSort(A) {
for (i=0; i A[i+1] {
swap(A[i], A[i+1])
}
}
}
Selection Sort
Runtime: O(n²) average and worst case
Memory: O(1)
void selection_sort (int A[ ], int n) {
int minimum;
for (int i = 0; i < n-1 ; i++) {
minimum = i ;
}
for (int j = i+1; j < n ; j++ ) {
if (A[ j ] < A[ minimum ]) {
minimum = j ;
}
}
swap ( A[ minimum ], A[ i ]) {
}
Merge Sort
Runtime: O(n log (n)) average and worst case
Memory: Depends
Divides the array in half, sorts each half and merges them back together.
MergeSort(arr[], l, r)
If r > l
1. Find the middle point to divide the array into two halves:
middle m = (l+r)/2
2. Call mergeSort for first half:
Call mergeSort(arr, l, m)
3. Call mergeSort for second half:
Call mergeSort(arr, m+1, r)
4. Merge the two halves sorted in step 2 and 3:
Call merge(arr, l, m, r)
Quick Sort
Runtime: O(n log (n)) average worst case O(n²)
Memory: O(n log (n))
quickSort(arr[], low, high) {
if (low < high) {
pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
