Advanced Algorithms — Exam Cheat Sheet

Python List Operations

Operation	Cost
list[i]	O(1)
len(list)	O(1)
list.append(x)	O(1)*
list.insert(0, x)	O(n)
list + [x]	O(n)
x in list	O(n)
x in set	O(1)
dict[key]	O(1)

* amortised; resize is O(n)

Comparison Table

Type	Ordered	Mutable	Dups	Hash
list []	✅	✅	✅	❌
tuple ()	✅	❌	✅	✅
set {}	❌	✅*	❌	✅
dict {k:v}	✅ 3.7+	✅	Keys ❌	✅

*set items must be immutable (hashable)

When to use each

• Tuple — immutable records, dict keys, returning multiple values, faster than list
• Set — deduplicate (list(set(l))), O(1) membership test
• Dict — O(1) lookup by key, counting (Counter), grouping
• List — ordered sequence, index access, dynamic size

Tuple is faster than list because it uses a single memory block vs. list's two-block structure (object info + data pointers).

Core Properties

LIFO — Last In, First Out

Operation	Cost
push(x)	O(1)
pop()	O(1)
peek()	O(1)
size()	O(1)

Implement with: list or collections.deque (preferred — O(1) both ends)

Applications

• Program call stack / recursion
• Undo / redo operations
• Infix → postfix conversion
• Postfix expression evaluation
• Syntax / bracket matching
• DFS (iterative)
• Browser back button

Infix → Postfix Rules

1. Operand → copy to output
2. ( → push to stack
3. ) → pop to output until (
4. Operator: pop any higher/equal-precedence ops to output, then push
5. End: pop all remaining stack → output

Example: (a+b)/(b+c) → ab+bc+/

Precedence: * / > + −

Queue — FIFO (First In, First Out)

• Enqueue → add to rear
• Dequeue → remove from front
• Both O(1) with collections.deque

Applications: task scheduling, BFS, print queues, buffering

Priority Queue

• Every item has a priority; higher priority dequeued first
• Equal priority → FIFO order
• Implementations: array, linked list, heap (best), binary tree
• heapq in Python gives a min-heap (negate values for max-heap)

Operations & Costs

Operation	Linked List	Array
Access by index	O(n)	O(1)
Search	O(n)	O(n)
Insert at head	O(1)	O(n)
Insert at tail	O(n)*	O(1)†
Delete (given node)	O(1)	O(n)

*O(1) if tail pointer kept  †amortised

Types

• Singly — value + next pointer only → forward traversal
• Doubly — prev + value + next → O(1) delete if node known
• Circular — tail's next → head; good for round-robin

Use / Avoid

✅ Use when:

• Frequent inserts/deletes in middle
• Unknown size at compile time
• No need for random access

❌ Avoid when:

• Need index / random access
• Memory is constrained (pointer overhead)
• Cache performance matters

Mechanics

Hash function maps key → integer index.
Example (modulo):

# Table size = 10
sum("John Smith") = 948
948 mod 10 = 8  ← stored at index 8

Good hash function: fast, distributes keys evenly

Hash Fn	Use
MurmurHash	Python dicts/sets
SHA-256	Encryption / signatures
Argon2	Password hashing
MD5	Fast, not secure

Collision Resolution

Linear Probing

• On collision → try next slot: (h + i) mod k
• Faster when table is sparse
• Risk: clustering

Chaining

• Each slot holds a linked list of entries
• Better when table is nearly full
• Extra memory for pointers

Load Factor

n = occupied entries    k = table size

Language	Default λ	Table size
Python dict	2/3	Power of 2 (init 8)
Java HashMap	0.75	Power of 2 (init 16)

When λ exceeds threshold → rehash (create larger table, reinsert all)

Terminology

• Root — top node, no parent
• Leaf / Terminal — no children
• Internal node — has ≥1 child
• Height — longest root-to-leaf path
• Siblings — same parent
• Edge / Branch — connection between nodes

BST Property

Operation	Avg	Worst
Search	O(log n)	O(n)*
Insert	O(log n)	O(n)*
Delete	O(log n)	O(n)*

*when tree is fully unbalanced (e.g. sorted input)

BST Deletion (3 Cases)

1. No children — set parent pointer to NULL
2. One child — parent pointer skips node, points to child
3. Two children — replace value with in-order predecessor (or successor), then delete that predecessor (falls to case 1)

Orders at a Glance

Order	Pattern	Use case
Pre-order	Root → L → R	Copy a tree; DFS path
In-order	L → Root → R	Sorted output from BST
Post-order	L → R → Root	Delete tree (leaves first)
BFS / Level	Level by level	Shortest path (unweighted)
DFS	Deep first	Cycle detect, connected components

Example — Tree: A(B(D,E), C(F,G))

Order	Output
Pre-order	A B D E C F G
In-order	D B E A F C G
Post-order	D E B F G C A

BFS vs DFS

	BFS	DFS
Structure	Queue	Stack / recursion
Direction	Level by level	Deep → backtrack
Visited array?	✅ (graphs)	✅ (graphs)

Recursive In-Order (Python)

def inorder(root):
    if root is None: return []
    return inorder(root.left) + [root.val] + inorder(root.right)

BFS with Queue (Python)

from collections import deque
def bfs(root):
    q = deque([root])
    while q:
        cur = q.popleft()
        print(cur.val)
        if cur.left:  q.append(cur.left)
        if cur.right: q.append(cur.right)

AVL Tree

First self-balancing BST (1962)

Balance Factor (BF) = Height(L) − Height(R)

Must be −1, 0, or +1 at every node

If |BF| > 1 → rotate to rebalance

Rotations: LL, RR, LR (double), RL (double)

✅ Faster lookups (stricter balance)

❌ Slower inserts/deletes (more rotations)

Used in: databases, Linux memory management

Red-Black Tree

Self-balancing BST with node colours (1972)

Rules:

1. Every node is Red or Black
2. Root is always Black
3. Children of a Red node are Black
4. Every root→NULL path has the same number of Black nodes
5. All NULL nodes are Black

✅ Faster inserts/deletes (relaxed balance, fewer rotations)

Only 1 bit extra per node (the colour)

Used in: C++ map/set, Linux CFS scheduler, Linux epoll

AVL vs Red-Black

	AVL	Red-Black
Lookup	Faster	Slower
Insert/Delete	Slower	Faster
Balance	Stricter	Relaxed
Memory/node	int (BF)	1 bit
Used in	DBs	Lang libs

Other Variants

Tree	Key idea	Use
Splay	Access → root	Caches
Heap	Parent ≤/≥ child	Priority queue
Treap	BST + heap priority	Randomised sets
B-Tree	Multi-key nodes	DB indexing, FS

Merge Sort — Pseudocode

def merge_sort(lst):
    if len(lst) <= 1: return lst
    mid = len(lst) // 2
    L = merge_sort(lst[:mid])
    R = merge_sort(lst[mid:])
    return merge(L, R)

def merge(L, R):
    out, i, j = [], 0, 0
    while i < len(L) and j < len(R):
        if L[i] < R[j]: out.append(L[i]); i += 1
        else:            out.append(R[j]); j += 1
    return out + L[i:] + R[j:]

Quick Sort — Not-in-place

def quick_sort(lst):
    if len(lst) < 2: return lst
    pivot = lst[0]   # or random choice
    left  = [x for x in lst[1:] if x <= pivot]
    right = [x for x in lst[1:] if x  > pivot]
    return quick_sort(left) + [pivot] + quick_sort(right)

In-place partition

# pivot = last element; i from low, j from high
while i < j:
    while lst[i] < pivot: i += 1
    while lst[j] > pivot: j -= 1
    if i < j: lst[i], lst[j] = lst[j], lst[i]; i += 1
recurse(low, i-1); recurse(i, high)

Requirements & Complexity

IMPORTANT: Array must be sorted

Complexity: O(log n)

Each step halves the search space.

Iterative (preferred)

def binary_search(lst, target):
    lo, hi = 0, len(lst) - 1
    while lo <= hi:
        mid = lo + (hi - lo) // 2  # avoids overflow
        if   lst[mid] == target: return mid
        elif lst[mid]  < target: lo = mid + 1
        else:                    hi = mid - 1
    return -1  # not found

Recursive Version

def bs_rec(lst, target, lo, hi):
    if lo > hi: return -1
    mid = lo + (hi - lo) // 2
    if   lst[mid] == target: return mid
    elif lst[mid]  < target: return bs_rec(lst, target, mid+1, hi)
    else:                    return bs_rec(lst, target, lo, mid-1)

Strategy

1. Divide — break problem into smaller subproblems
2. Conquer — solve each recursively
3. Combine — merge results

Subproblems are independent (no overlap).

Usually recursive.

D&C Examples

• Merge Sort — split + merge
• Quick Sort — partition + recurse
• Binary Search — split search space
• Majority Element (LC 169):
  split → find majority in L and R → count both candidates → return higher

When D&C goes wrong

If subproblems overlap (same sub-calculation repeated), D&C wastes time recomputing.

Example: Naive Fibonacci
fib(5) calls fib(3) twice, fib(2) three times…
→ O(2ⁿ)

→ Use Dynamic Programming instead

Core Idea

Solve overlapping subproblems once, store results — avoid recomputation.

Two key properties required:

• Optimal Substructure — optimal solution built from optimal sub-solutions
• Overlapping Subproblems — same sub-calculations repeated

	D&C	DP
Subproblems	Independent	Overlapping
Style	Recursive	Recursive or iterative
Recomputes?	Yes	No (stores)
Examples	Merge/Quick sort	Fibonacci, Knapsack

Two Approaches

Top-Down (Memoization) — recursive + cache

memo = {}
def fib(n):
    if n in memo: return memo[n]
    if n <= 1: return n
    memo[n] = fib(n-1) + fib(n-2)
    return memo[n]   # O(n) time & space

Bottom-Up (Tabulation) — iterative, fill table from small → large

def fib(n):
    dp = [0, 1]
    for i in range(2, n+1):
        dp.append(dp[i-1] + dp[i-2])
    return dp[n]      # O(n) time & space

Fundamentals

G = (V, E) — vertices + edges

• Order = |V|
• Size = |E|
• Degree = edges incident to a vertex
• Weighted — edges have costs
• Directed — edges have direction

Path — sequence of vertices

Simple path — all vertices distinct

Length = number of edges (vertices − 1)

Representations

Type	Space	Edge lookup	Best for
Edge list	O(E)	O(E)	Simple/sparse
Adjacency matrix	O(V²)	O(1)	Dense graphs
Adjacency list	O(V+E)	O(deg)	Sparse (most common)

Adjacency list is the standard choice — efficient space and lookup for sparse graphs.

Graph Traversal

	BFS	DFS
Structure	Queue	Stack / recursion
Order	Level by level	Deep, then backtrack
Visited array?	✅ (cycles)	✅ (cycles)
Time	O(V+E)	O(V+E)
Shortest path?	✅ (unweighted)	❌

Requirements & Complexity

• Weighted graph, no negative weights
• Single-source shortest path to all vertices
• Complexity: O((V + E) log V) with min-heap

Steps

1. Mark all nodes unvisited; source distance = 0, rest = ∞
2. Set source as current node
3. For each unvisited neighbour: new_dist = cur_dist + edge_weight
4. If new_dist < neighbour_dist → update neighbour
5. Mark current node visited
6. Pick unvisited node with smallest distance → new current
7. Repeat from step 3 until destination visited or all visited

Pseudocode

import heapq

def dijkstra(graph, src):
    dist = {v: float('inf') for v in graph}
    dist[src] = 0
    pq = [(0, src)]   # (distance, vertex)

    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]: continue  # stale entry

        for v, w in graph[u]:      # neighbour, weight
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))

    return dist

Real-world uses

• GPS navigation (shortest/fastest route)
• OSPF routing protocol (Open Shortest Path First)
• Network packet routing