Computer Algorithms

A practical study guide to the major algorithm families

Sorting, searching, graphs, trees, strings, dynamic programming, security,

databases, operating systems, AI, optimization, and more.

Important note: No single PDF can literally list every algorithm ever invented. This guide covers the main
families and representative algorithms that students, programmers, and technical readers most often need.

How to use this guide

- Read Sections 1-3 first if you are new to algorithms.
- Use the comparison tables to choose which algorithm fits a problem.
- Focus on the idea and trade-off before memorising code.
- Use the appendix checklist as a revision sheet before tests or interviews.

Page 1
Computer Algorithms Study Guide

Contents
- 1. What is an algorithm?
- 2. Big-O and complexity basics
- 3. Algorithm design techniques
- 4. Core data structures used by algorithms
- 5. Searching algorithms
- 6. Sorting algorithms
- 7. Recursion and backtracking
- 8. Greedy algorithms
- 9. Dynamic programming
- 10. Graph algorithms
- 11. Tree and heap algorithms
- 12. String and text algorithms
- 13. Mathematical and number algorithms
- 14. Cryptography, hashing, and checksums
- 15. Compression algorithms
- 16. Computational geometry
- 17. Randomized and probabilistic algorithms
- 18. Databases and storage algorithms
- 19. Operating system and distributed algorithms
- 20. Optimization and machine learning algorithms
- 21. Algorithm choice cheat sheets
- 22. Revision checklist and practice prompts

Page 2
Computer Algorithms Study Guide

1. What Is an Algorithm?
An algorithm is a precise step-by-step method for solving a problem. It takes input, follows clear
instructions, and produces output. A good algorithm is correct, understandable, efficient, and suitable for
the constraints of the problem.

Term Meaning Simple example

Input The data given to the algorithm. A list of numbers: [7, 2, 9].

Output The result produced. The sorted list: [2, 7, 9].

Correctness The algorithm gives the right answer for all valid inputs. Binary search only works if the list is sorted.

Efficiency How much time and memory the algorithm needs. Merge sort is usually faster than bubble sort for
large lists.

Trade-off A benefit that comes with a cost. Hash tables are fast but use extra memory.

A basic algorithm template

Algorithm solve_problem(input):
validate the input
prepare useful data structures
repeat the main steps until finished
return the result

Key idea: An algorithm is not the same as a programming language. The same algorithm can be written in
Python, JavaScript, C++, Java, or any other language.

2. Big-O and Complexity Basics

Complexity describes how an algorithm grows as the input size grows. If n is the number of items, Big-O
gives a simplified upper-bound growth rate. It ignores small constants and focuses on the main trend.

Big-O Name What it feels like Common examples

O(1) Constant Time stays about the same. Array index access, stack push/pop.

O(log n) Logarithmic Very slow growth. Binary search, balanced tree search.

O(n) Linear Double input roughly doubles work. Linear search, scanning a list.

O(n log n) Linearithmic Good for many sorting tasks. Merge sort, heap sort, average quicksort.

O(n^2) Quadratic Gets slow quickly. Nested loops, bubble sort.

O(2^n) Exponential Often too slow except small n. Brute-force subsets.

O(n!) Factorial Explodes extremely fast. Brute-force travelling salesperson.

Time vs space
- Time complexity asks: how many operations are needed?
- Space complexity asks: how much extra memory is needed?
- Sometimes you use more memory to make the algorithm faster, for example hash tables and dynamic
programming tables.
- Worst case is the slowest possible case. Average case is typical behaviour. Best case is often less
useful for planning.

Page 3
Computer Algorithms Study Guide

Common complexity patterns

Code pattern Typical complexity Reason
One loop over n items O(n) Each item is processed once.

Two nested loops over n items O(n^2) For every item, you may compare with every other item.

Repeatedly halving the input O(log n) The problem size shrinks quickly.

Divide, solve two halves, then merge O(n log n) There are log n levels and n work per level.

Try every subset O(2^n) Each item is either included or not included.

3. Algorithm Design Techniques

Design techniques are reusable ways of thinking. Many famous algorithms are examples of these
patterns.

Technique Core idea Typical algorithms

Brute force Try all possibilities. Linear search, exhaustive password guessing,
brute-force TSP.

Divide and conquer Split problem, solve parts, combine results. Merge sort, quicksort, binary search, closest pair.

Greedy Make the locally best choice now. Activity selection, Huffman coding, Dijkstra, Kruskal,
Prim.

Dynamic programming Store answers to overlapping subproblems. Knapsack, LCS, edit distance, shortest paths in
DAGs.

Backtracking Build a solution, undo when stuck. Sudoku, N-Queens, permutations, combinations.

Branch and bound Search but prune using bounds. Optimisation variants of TSP and integer
programming.

Randomized Use randomness to improve average performance or Randomized quicksort, reservoir sampling, Monte
simplicity. Carlo.

Approximation Find a good enough answer when exact is too slow. Approximation for NP-hard optimisation problems.

Problem-solving workflow
1. Understand the input and output.
2. Estimate constraints: n = 100? 10,000? 10,000,000?
3. Choose a data structure: array, hash table, stack, queue, tree, graph.
4. Choose a design technique: brute force, greedy, DP, backtracking, etc.
5. Prove or test correctness.
6. Analyse time and space complexity.
7. Implement carefully and test edge cases.

4. Core Data Structures Used by Algorithms

Algorithms often become easier when the right data structure is chosen. A data structure controls how
information is stored and accessed.

Data structure Strength Common operations Used in

Array / list Fast indexing, simple storage. Access, append, scan, sort. Sorting, binary search, dynamic arrays.

Linked list Easy insertion/deletion if node is Insert, delete, traverse. Queues, memory allocators.
known.

Stack Last-in, first-out. push, pop, peek. DFS, undo, parsing brackets.

Queue First-in, first-out. enqueue, dequeue. BFS, scheduling, buffering.

Deque Insert/remove at both ends. push front/back, pop front/back. Sliding window algorithms.

Hash table Very fast average lookup. insert, search, delete. Dictionaries, sets, caches.

Heap / priority queue Quick access to smallest/largest push, pop min/max. Dijkstra, scheduling, heap sort.
priority.

Tree Hierarchical data and ordered search, insert, traversal. BST, file systems, parse trees.
search.

Graph Networks of relationships. BFS, DFS, shortest path. Maps, social networks, dependencies.

Trie Fast prefix search. insert word, prefix lookup. Autocomplete, dictionaries, IP routing.

Page 4
Computer Algorithms Study Guide

5. Searching Algorithms
Searching means finding an item, position, answer, or condition. It may happen in an array, tree, graph,
database, or search space.

Linear Search
Main idea Used for Typical complexity
Check items one by one until the target is found. Small or unsorted lists. Time: O(n). Space: O(1).

for i from 0 to n-1:

if A[i] == target:
return i
return not_found

- Common mistake: Forgetting that the target may not exist.

Binary Search
Main idea Used for Typical complexity
Repeatedly compare with the middle and discard Sorted arrays, answer search on monotonic Time: O(log n). Space: O(1) iterative.
half. conditions.

low = 0, high = n - 1
while low <= high:
mid = (low + high) // 2
if A[mid] == target: return mid
if A[mid] < target: low = mid + 1
else: high = mid - 1
return not_found

- Common mistake: Using it on unsorted data or getting boundary conditions wrong.

Other search types

Search type Idea Typical use
Hash lookup Use a hash function to jump near the item. Dictionaries, sets, caches.

Tree search Use tree ordering or structure. BST, AVL, red-black tree.

Graph search Explore connected nodes. BFS, DFS, path finding.

Exponential search Find a range by doubling, then binary search. Sorted unbounded/infinite-like arrays.

Interpolation search Estimate position using value distribution. Uniformly distributed sorted numeric data.

6. Sorting Algorithms
Sorting rearranges data into order. Sorting is important because many other algorithms become faster
after data is sorted.

Algorithm Best / average / worst Space Stable? When useful

Bubble sort O(n) / O(n^2) / O(n^2) O(1) Yes Teaching only, tiny data.

Selection sort O(n^2) all cases O(1) Usually no Few writes; educational.

Insertion sort O(n) / O(n^2) / O(n^2) O(1) Yes Small or nearly sorted data.

Merge sort O(n log n) all cases O(n) Yes Reliable sorting; linked lists; external sorting.

Quicksort O(n log n) avg, O(n^2) worst O(log n) No Fast in practice with good pivots.

Heap sort O(n log n) all cases O(1) No Good worst-case memory-limited sorting.

Counting sort O(n + k) O(k) Yes Small integer range k.

Radix sort O(d(n+k)) O(n+k) Yes Integers/strings with fixed digits.

Bucket sort O(n) average O(n) Depends Uniform numeric distribution.

Timsort O(n) best, O(n log n) worst O(n) Yes Real-world built-in sort in Python/Java.

Page 5
Computer Algorithms Study Guide

Merge Sort
Main idea Used for Typical complexity
Split the list in half, sort each half, then merge Reliable general-purpose sorting and external Time: O(n log n). Space: O(n).
sorted halves. sorting.

merge_sort(A):
if len(A) <= 1: return A
left = merge_sort(first half)
right = merge_sort(second half)
return merge(left, right)

- Common mistake: Forgetting that the merge step must preserve order and takes linear time.

Quicksort
Main idea Used for Typical complexity
Pick a pivot, partition smaller values left and Fast in-memory sorting with good pivot selection. Average: O(n log n). Worst: O(n^2).
larger values right, then recurse.

quicksort(A, low, high):

if low >= high: return
p = partition(A, low, high)
quicksort(A, low, p - 1)
quicksort(A, p + 1, high)

- Common mistake: Choosing bad pivots on already sorted or adversarial data.

7. Recursion and Backtracking

Recursion means a function solves a problem by calling itself on smaller versions of the problem.
Backtracking is recursion plus undoing choices when they do not lead to a solution.

Recursion pattern
recursive_function(problem):
if problem is small enough:
return direct answer # base case
split or reduce the problem
call recursive_function on smaller problem(s)
combine the results

Backtracking pattern
backtrack(state):
if state is a complete solution:
save or return it
for each possible choice:
if choice is valid:
make choice
backtrack(new state)
undo choice

Algorithm/problem Idea Common complexity

Permutations Try every order of items. O(n!)

Subsets For each item: include or exclude. O(2^n)

N-Queens Place queens row by row, backtrack on attacks. Exponential

Sudoku solver Fill empty cells, backtrack on invalid placements. Exponential worst case

DFS maze solving Explore a path, backtrack when blocked. O(V+E) for graph form

8. Greedy Algorithms
A greedy algorithm makes the best-looking local choice at each step. Greedy is fast and elegant, but it
only works when local choices can be proven to lead to a global optimum.

Page 6
Computer Algorithms Study Guide

Greedy algorithm Greedy choice Used for Complexity

Activity selection Choose the event that finishes earliest. Maximum number of non-overlapping O(n log n) with
activities. sorting.

Fractional knapsack Take highest value/weight ratio first. Items can be split. O(n log n).

Huffman coding Merge two lowest-frequency symbols Prefix-code compression. O(n log n).
repeatedly.

Dijkstra Choose unvisited node with smallest known Shortest paths with non-negative weights. O((V+E) log V) with
distance. heap.

Kruskal Add smallest edge that does not create a Minimum spanning tree. O(E log E).
cycle.

Prim Grow tree using smallest outgoing edge. Minimum spanning tree. O(E log V) with heap.

Warning: Greedy does not solve 0/1 knapsack correctly in general, because items cannot be split. That
problem usually needs dynamic programming or search.

Activity Selection
Main idea Used for Typical complexity
Sort by finish time and repeatedly choose the Scheduling the maximum number of compatible Time: O(n log n) due to sorting.
activity that ends earliest without overlapping. tasks.

sort activities by finish time

result = []
last_finish = -infinity
for activity in activities:
if [Link] >= last_finish:
add activity to result
last_finish = [Link]
return result

- Common mistake: Sorting by start time or duration looks reasonable but can fail.

9. Dynamic Programming
Dynamic programming (DP) solves problems with overlapping subproblems and optimal substructure.
Instead of recalculating the same thing many times, DP stores answers in a table or memo cache.

Two styles of DP
Style How it works When it feels natural
Top-down memoization Write recursive solution and cache answers. When the recurrence is easy to express
recursively.

Bottom-up tabulation Fill a table from smaller cases to larger cases. When the order of computation is clear.

Common DP algorithms/problems
Problem State idea Typical complexity Use
Fibonacci DP dp[i] = dp[i-1] + dp[i-2] O(n) Intro to memoization.

0/1 Knapsack best value using first i items and capacity w O(nW) Selection under capacity.

Longest Common Subsequence best subsequence length for prefixes O(nm) Text comparison, DNA.

Edit Distance min operations to convert prefix A to prefix B O(nm) Spell check, similarity.

Longest Increasing Subsequence best increasing subsequence ending at i O(n^2) or O(n log n) Sequence analysis.

Matrix Chain Multiplication best split point for multiplying matrices O(n^3) Optimization of
computation order.

Floyd-Warshall shortest path using first k intermediate nodes O(V^3) All-pairs shortest paths.

0/1 Knapsack DP
Main idea Used for Typical complexity
For each item, choose either take it or leave it, Choosing items under a fixed weight/budget Time: O(nW). Space: O(nW) or O(W).
then keep best value for each capacity. limit.

Page 7
Computer Algorithms Study Guide

for item i from 1 to n:

for capacity w from 0 to W:
dp[i][w] = dp[i-1][w]
if weight[i] <= w:
dp[i][w] = max(dp[i][w], dp[i-1][w-weight[i]] + value[i])
return dp[n][W]

- Common mistake: Updating a one-dimensional DP array in the wrong direction can reuse an item more than once.

How to recognise DP
- The problem asks for best, minimum, maximum, count, or number of ways.
- A brute-force recursive solution repeats the same subproblems.
- A decision at one step depends on results from smaller cases.
- You can define a state, recurrence, base case, and answer location.

10. Graph Algorithms

A graph contains vertices (nodes) and edges (connections). Graphs model maps, networks,
dependencies, recommendations, social links, circuits, and many real-world systems.

Graph term Meaning

Vertex / node An object or point in the graph.

Edge A connection between two vertices.

Directed graph Edges have direction, for example A -> B.

Undirected graph Edges have no direction, for example friendships.

Weighted graph Edges have costs, distances, or capacities.

Path A sequence of connected vertices.

Cycle A path that returns to a previous vertex.

DAG Directed acyclic graph; useful for dependency ordering.

Graph algorithm overview

Problem Algorithm(s) Typical complexity Notes
Explore all reachable nodes BFS, DFS O(V+E) Works on directed/undirected graphs.

Shortest path, unweighted BFS O(V+E) Each edge counts as 1.

Shortest path, non-negative Dijkstra O((V+E) log V) Needs no negative weights.

weights

Shortest path with negative Bellman-Ford O(VE) Can detect negative cycles.
edges

All-pairs shortest paths Floyd-Warshall O(V^3) Simple DP over vertices.

Heuristic path finding A* Depends Uses heuristic estimate to guide search.

Dependency ordering Topological sort O(V+E) Only works for DAGs.

Minimum spanning tree Kruskal, Prim O(E log V) Connects all vertices cheaply.

Strongly connected components Kosaraju, Tarjan O(V+E) Directed graph components.

Maximum flow Ford-Fulkerson, Edmonds-Karp, Varies Capacity and network flow problems.
Dinic

Breadth-First Search (BFS)

Main idea Used for Typical complexity
Use a queue to explore nearest nodes before Unweighted shortest paths, level order traversal, Time: O(V+E). Space: O(V).
farther nodes. connected components.

BFS(start):
queue = [start]
visited = {start}
while queue not empty:
v = queue.pop_front()

Page 8
Computer Algorithms Study Guide

for each neighbor u of v:

if u not visited:
[Link](u)
queue.push_back(u)

- Common mistake: Using a stack by accident turns BFS into DFS.

Depth-First Search (DFS)

Main idea Used for Typical complexity
Go as deep as possible before backtracking. Cycle detection, topological sort, components, Time: O(V+E). Space: O(V).
maze solving.

DFS(v):
mark v as visited
for each neighbor u of v:
if u not visited:
DFS(u)

- Common mistake: Forgetting visited nodes can cause infinite loops in cyclic graphs.

Dijkstra's Algorithm
Main idea Used for Typical complexity
Repeatedly finalise the unvisited node with the Shortest paths with non-negative edge weights. Time: O((V+E) log V) using a priority queue.
smallest known distance.

dist[start] = 0
priority_queue.push((0, start))
while queue not empty:
d, v = pop smallest distance
if d is outdated: continue
for each edge v -> u with weight w:
if dist[v] + w < dist[u]:
dist[u] = dist[v] + w
push(dist[u], u)

- Common mistake: It is not correct with negative edge weights.

Graph representations
Representation Memory Good for Weakness
Adjacency list O(V+E) Sparse graphs, BFS/DFS/Dijkstra. Checking if a specific edge exists
may take time.

Adjacency matrix O(V^2) Dense graphs, fast edge check. Wastes memory on sparse graphs.

Edge list O(E) Kruskal, Bellman-Ford. Finding neighbours is slower.

11. Tree and Heap Algorithms

Trees are graphs with hierarchical structure. They are common in search, parsing, file systems, user
interfaces, databases, and priority queues.

Algorithm / structure Core idea Typical operations

Tree traversal Visit nodes in preorder, inorder, postorder, or level order. O(n).

Binary search tree Left values < node < right values. Search/insert/delete O(h), where h is
height.

AVL tree Self-balancing BST using height balance. O(log n) search/insert/delete.

Red-black tree Self-balancing BST with colour rules. O(log n), used in many libraries.

Heap Parent priority is before child priority. push/pop O(log n), peek O(1).

Trie Tree of characters or bits. Prefix lookup O(length).

Segment tree Tree storing range summaries. Range query/update O(log n).

Fenwick tree Compact structure for prefix sums. Prefix query/update O(log n).

Page 9
Computer Algorithms Study Guide

Algorithm / structure Core idea Typical operations

Union-Find Tracks disjoint sets with parent links. Nearly O(1) amortized with path
compression.

Heap Operations
Main idea Used for Typical complexity
Maintain a partially ordered tree so the min or Priority queues, heap sort, Dijkstra, scheduling. push/pop: O(log n). peek: O(1).
max priority is easy to access.

heap_push(x):
add x at end
bubble x upward while parent has lower priority

heap_pop():
replace root with last item
bubble root downward until heap property is restored

- Common mistake: A heap is not a fully sorted structure; only the root is guaranteed to be min/max.

Union-Find / Disjoint Set Union

Main idea Used for Typical complexity
Keep groups of elements and quickly merge Kruskal MST, connectivity, clustering. Almost O(1) amortized per operation.
groups or test if two elements are in the same
group.

find(x):
if parent[x] != x:
parent[x] = find(parent[x]) # path compression
return parent[x]

union(a, b):
rootA = find(a); rootB = find(b)
attach smaller tree under larger tree

- Common mistake: Forgetting path compression or union by rank makes it slower.

12. String and Text Algorithms

String algorithms process text, DNA sequences, logs, documents, commands, and programming
languages. The main challenge is matching patterns efficiently.

Algorithm Core idea Typical complexity Used for

Naive pattern matching Try pattern at each position. O(nm) Small texts or teaching.

KMP Precompute pattern prefix table to avoid O(n+m) Exact pattern search.
rechecking.

Rabin-Karp Use rolling hash to compare quickly. Average O(n+m) Multiple pattern search, plagiarism
detection.

Boyer-Moore Compare from right and skip positions. Often sublinear in Fast text search.
practice

Trie Store words by prefixes. O(length) Autocomplete, dictionary lookup.

Aho-Corasick Trie plus failure links. O(text + matches) Many patterns at once.

Suffix array Sorted list of suffixes. Search O(m log n) Indexing large texts.

Suffix tree Compressed trie of suffixes. Search O(m) Advanced text indexing.

Edit distance DP for insert/delete/replace cost. O(nm) Spellcheck, similarity.

Regex automata Convert pattern to NFA/DFA. Varies Pattern matching languages.

Knuth-Morris-Pratt (KMP)
Main idea Used for Typical complexity
Use a prefix table so mismatches do not restart Exact substring search in linear time. Time: O(n+m). Space: O(m).
the search from zero.

Page 10
Computer Algorithms Study Guide

build prefix table for pattern P

j = 0
for each character in text T:
while j > 0 and T[i] != P[j]:
j = prefix[j-1]
if T[i] == P[j]: j += 1
if j == len(P):
report match
j = prefix[j-1]

- Common mistake: The prefix table stores border lengths, not random jumps.

13. Mathematical and Number Algorithms

Many programs need arithmetic, divisibility, random numbers, geometry, cryptography, and numerical
approximation. Number algorithms must also handle overflow and precision.

Algorithm Purpose Typical complexity / note

Euclidean algorithm Greatest common divisor (GCD). O(log min(a,b)).

Extended Euclidean algorithm Find x,y such that ax + by = gcd(a,b). Used for modular inverse.

Sieve of Eratosthenes Find primes up to n. O(n log log n).

Fast exponentiation Compute a^b quickly by squaring. O(log b).

Modular exponentiation Compute a^b mod m without huge numbers. O(log b).

Miller-Rabin Probabilistic primality test. Fast, widely used.

Newton's method Approximate roots or optimisation points. Fast when conditions are good.

Gaussian elimination Solve systems of linear equations. O(n^3).

FFT Fast polynomial multiplication / signal transform. O(n log n).

Euclidean Algorithm
Main idea Used for Typical complexity
Repeatedly replace the larger number by the Finding GCD, simplifying fractions, cryptography Time: O(log min(a,b)).
remainder until the remainder is zero. foundations.

gcd(a, b):
while b != 0:
a, b = b, a mod b
return a

- Common mistake: Using subtraction version is correct but much slower for large numbers.

14. Cryptography, Hashing, and Checksums

Security algorithms protect confidentiality, integrity, authentication, and non-repudiation. Checksums
and hashes help detect accidental or intentional changes.

Category Algorithms / examples Purpose

Hashing SHA-256, SHA-3, BLAKE2 Fixed-size fingerprint of data.

Password hashing bcrypt, scrypt, Argon2 Slow, salted password storage.

Checksums Parity bit, Luhn, CRC Detect accidental errors.

Symmetric encryption AES, ChaCha20 Same key encrypts and decrypts.

Asymmetric encryption RSA, ECC-based schemes Public/private key pairs.

Key exchange Diffie-Hellman, ECDH Agree on a shared secret.

Digital signatures RSA signatures, ECDSA, EdDSA Prove message origin and integrity.

Message authentication HMAC, Poly1305 Verify message authenticity with shared secret.

Security note: Never invent your own encryption algorithm for real security. Use standard, reviewed libraries
and protocols.

Page 11
Computer Algorithms Study Guide

Hash table vs cryptographic hash

A hash table hash function is designed for speed and even distribution in a data structure. A
cryptographic hash is designed to resist collision attacks and preimage attacks. They are related ideas,
but not interchangeable.

15. Compression Algorithms

Compression reduces file size by representing data more efficiently. Lossless compression preserves
exact data; lossy compression removes less important information.

Algorithm Type Main idea Used in

Run-length encoding (RLE) Lossless Replace repeated runs with count + value. Simple images, masks.

Huffman coding Lossless Short codes for frequent symbols. ZIP components, images,
teaching.

LZ77 / LZ78 Lossless Refer back to repeated previous text. ZIP, PNG, gzip-related
methods.

LZW Lossless Build dictionary of repeated sequences. GIF, old compression formats.

Arithmetic coding Lossless Encode message as interval using probabilities. Advanced compression.

JPEG-style DCT Lossy Transform image blocks and discard high-frequency JPEG images.
details.

MP3/AAC-style Lossy Remove audio details humans hear less. Audio compression.

Choosing compression
- Use lossless compression for code, documents, database backups, and exact records.
- Use lossy compression for media when smaller size matters more than perfect reconstruction.
- Compression works best when data has repetition or predictable patterns.

16. Computational Geometry

Computational geometry algorithms solve problems involving points, lines, polygons, distances, and
shapes. They are used in graphics, robotics, games, maps, CAD, and vision.

Problem Algorithm Idea Typical

complexity
Convex hull Graham scan, Andrew monotonic Find the smallest convex boundary around points. O(n log n).
chain

Closest pair of points Divide and conquer Split points and check crossing strip. O(n log n).

Line segment intersection Orientation tests, sweep line Detect crossings efficiently. O((n+k) log n).

Point in polygon Ray casting, winding number Count crossings or angle winding. O(n).

Voronoi diagram Fortune's algorithm Partition plane by nearest site. O(n log n).

Delaunay triangulation Various algorithms Triangulation related to Voronoi. O(n log n).

Important detail
Geometry algorithms often fail due to floating-point precision errors. Robust implementations use careful
orientation tests, tolerances, or exact arithmetic where necessary.

17. Randomized and Probabilistic Algorithms

Randomized algorithms use random choices. They can be simpler or faster on average, but may produce
probabilistic results or require careful analysis.

Algorithm / structure Main idea Use

Randomized quicksort Choose random pivots to avoid bad patterns. Fast average sorting.

Page 12
Computer Algorithms Study Guide

Algorithm / structure Main idea Use

Reservoir sampling Keep a random sample from a stream of unknown length. Streaming data.

Monte Carlo simulation Use random trials to estimate results. Risk, physics, optimisation, probability.

Las Vegas algorithm Random time, always correct answer. Randomized quicksort is often described
this way.

Bloom filter Probabilistic set membership with false positives. Caches, databases, web crawlers.

Skip list Random levels create balanced search structure. Alternative to balanced trees.

False positive example: A Bloom filter may say an item is possibly present when it is not, but it should not say
an inserted item is absent.

18. Databases and Storage Algorithms

Database systems rely heavily on algorithms. They need to store data, search quickly, join tables,
recover from crashes, and handle many users at once.

Area Algorithm / structure Purpose

Indexing B-tree, B+ tree Keep sorted keys on disk with few reads.

Hash indexing Extendible hashing, linear hashing Fast equality lookup.

Joins Nested-loop join, hash join, sort-merge join Combine rows from tables.

Query planning Cost-based optimisation Choose efficient execution plan.

Transactions Two-phase locking, MVCC Consistency with concurrent users.

Recovery Write-ahead logging Recover after crash.

Caching LRU, LFU, clock algorithm Keep useful pages in memory.

External sorting External merge sort Sort data larger than memory.

Why B-trees are common in databases

A B-tree or B+ tree stores many keys per node, matching disk and SSD page access patterns. This
reduces the number of storage reads compared with a simple binary search tree.

19. Operating System and Distributed Algorithms

Operating systems and distributed systems use algorithms for scheduling, memory, files, networks,
reliability, and agreement between machines.

Area Algorithm Purpose / trade-off

CPU scheduling FCFS Simple, but can cause long waiting.

CPU scheduling Shortest Job First Minimises average waiting if job lengths known.

CPU scheduling Round Robin Fair time slices for interactive systems.

CPU scheduling Priority scheduling Important tasks first, but may starve low priority tasks.

Memory FIFO page replacement Simple but can perform poorly.

Memory LRU page replacement Evict least recently used page.

Deadlock Banker's algorithm Avoid unsafe resource allocation.

Distributed systems Paxos, Raft Consensus: agree on a value despite failures.

Distributed data Consistent hashing Distribute keys and reduce remapping.

Big data MapReduce Parallel map and reduce operations across clusters.

Distributed systems warning: Network failures, message delays, and clock differences make distributed
algorithms much harder than single-machine algorithms.

20. Optimization and Machine Learning Algorithms

Optimization algorithms search for good or best solutions. Machine learning algorithms learn patterns
from data. Many ML methods are built on optimisation.

Page 13
Computer Algorithms Study Guide

Optimization algorithms
Algorithm Main idea Used for
Gradient descent Move parameters in direction that reduces loss. Training ML models, numerical
optimisation.

Stochastic gradient descent Use small batches for faster noisy updates. Large-scale ML.

Newton's method Use curvature information for fast convergence. Root finding and optimisation.

Simulated annealing Sometimes accept worse moves to escape local optima. Hard optimisation problems.

Genetic algorithms Evolve candidate solutions using selection/mutation/crossover. Search spaces with weak structure.

Linear programming / simplex Optimise linear objective under linear constraints. Operations research, allocation.

Machine learning algorithm overview

Algorithm Task Core idea
Linear regression Predict numeric values. Fit a line/plane to minimise error.

Logistic regression Classification. Predict probability of class.

k-Nearest Neighbours Classification/regression. Use labels/values of nearby examples.

Decision tree Classification/regression. Split data using feature questions.

Random forest Classification/regression. Combine many decision trees.

Gradient boosting Classification/regression. Add models that correct previous errors.

k-Means Clustering. Group points around k centres.

PCA Dimensionality reduction. Find directions of greatest variance.

Naive Bayes Classification. Use probability with independence assumption.

Neural network Many tasks. Layers learn representations using backpropagation.

Transformer attention Language/vision sequences. Each token attends to relevant tokens.

For beginners: Do not try to memorise all ML algorithms first. Learn the difference between supervised
learning, unsupervised learning, classification, regression, clustering, training, validation, overfitting, and loss
functions.

21. Algorithm Choice Cheat Sheets

These quick tables help you choose a likely algorithm family based on problem clues.

By problem clue
Problem clue Usually consider Why
Data is sorted Binary search, two pointers Sorted order gives structure.

Need fastest lookup by key Hash table Average O(1) lookup.

Need items by priority Heap / priority queue Fast min/max priority access.

Need nearest unweighted path BFS Explores by distance in edges.

Need weighted shortest path Dijkstra / Bellman-Ford Depends on negative weights.

Need all dependencies in order Topological sort Works on DAGs.

Need best value/count/ways Dynamic programming Often overlapping subproblems.

Need try choices with constraints Backtracking Search tree with pruning.

Need connect all nodes cheaply Minimum spanning tree Kruskal or Prim.

Need pattern in text KMP, Rabin-Karp, Boyer-Moore Avoid repeated matching work.

Need range sum/min/max updates Segment tree / Fenwick tree Efficient range queries.

Need prefix words Trie Prefix operations by character path.

Page 14
Computer Algorithms Study Guide

By input size
Input size n Usually acceptable Usually risky
n <= 20 O(2^n), backtracking with pruning O(n!) unless heavily pruned.

n <= 500 O(n^3) may be acceptable O(2^n).

n <= 5,000 O(n^2) sometimes acceptable O(n^3).

n <= 100,000 O(n log n), O(n) O(n^2).

n >= 1,000,000 O(n), O(n log n) with care High constants or memory-heavy methods.

Sorting choice
Situation Recommended
General-purpose sorting Use the language built-in sort, often highly optimised.

Need stable sort Merge sort or Timsort.

Need O(1) extra memory and good worst case Heap sort.

Small/nearly sorted Insertion sort or built-in sort.

Small integer range Counting sort.

Fixed-length integer/string keys Radix sort.

22. Revision Checklist and Practice Prompts

Core revision checklist
- I can explain what an algorithm is without naming a programming language.
- I can estimate whether O(n^2) is too slow for a given input size.
- I can choose between array, hash table, stack, queue, heap, tree, and graph.
- I know when binary search is valid.
- I can compare bubble, insertion, merge, quick, heap, counting, and radix sort.
- I can trace BFS and DFS on a small graph.
- I know when Dijkstra cannot be used.
- I can recognise a dynamic programming problem and define state, recurrence, base case, and answer.
- I can explain greedy vs dynamic programming vs backtracking.
- I can name examples of algorithms used in databases, operating systems, security, compression, and
machine learning.

Practice prompts
- Given a list of 1,000,000 numbers, which sorting algorithms are reasonable and why?
- Why does binary search require sorted data? Trace it on [2, 4, 7, 9, 13, 18].
- A map has roads with distances. Which algorithm finds shortest routes if all distances are
non-negative?
- A graph has edges with negative weights. Which shortest-path algorithm is safer than Dijkstra?
- You need autocomplete for a dictionary. Which data structure helps and why?
- You need to count ways to make change using coins. Why might dynamic programming help?
- You need to detect if two accounts are in the same group after many merge operations. Which
structure helps?
- You need to find a substring in a huge document. Why is naive search sometimes inefficient?
- You need to store passwords. Why is a fast general hash not enough?

Page 15
Computer Algorithms Study Guide

- You need to schedule fair CPU time between many programs. Which OS scheduling ideas apply?

Suggested learning order

Stage Learn
1 Basic programming, arrays/lists, loops, functions.

2 Big-O, linear search, binary search, simple sorting.

3 Stacks, queues, hash tables, recursion.

4 Merge sort, quicksort, heaps, priority queues.

5 BFS, DFS, graph representations, topological sort.

6 Dijkstra, MST, union-find.

7 Dynamic programming and backtracking.

8 String algorithms, databases, operating systems, security.

9 Machine learning, optimisation, advanced graph and geometry algorithms.

Page 16
Computer Algorithms Study Guide

Appendix: Major Algorithm Catalog

This catalog is not exhaustive, but it gives a broad map of major algorithms and where they belong.

Family Representative algorithms

Searching Linear search, binary search, exponential search, interpolation search, ternary search, hash lookup.

Sorting Bubble, selection, insertion, shell, merge, quick, heap, counting, radix, bucket, Timsort, external merge sort.

Arrays / sequences Two pointers, sliding window, prefix sums, difference arrays, Kadane's algorithm, monotonic stack/queue.

Recursion / search space Backtracking, branch and bound, DFS search tree, permutations, subsets, N-Queens, Sudoku solver.

Greedy Activity selection, interval scheduling, fractional knapsack, Huffman, Dijkstra, Kruskal, Prim.

Dynamic programming Fibonacci, knapsack, coin change, LCS, LIS, edit distance, matrix chain, DP on trees, bitmask DP.

Graphs BFS, DFS, topological sort, Dijkstra, Bellman-Ford, Floyd-Warshall, A*, Kruskal, Prim, Kosaraju, Tarjan,
Ford-Fulkerson, Edmonds-Karp, Dinic.

Trees Tree traversals, BST operations, AVL rotations, red-black balancing, heap operations, trie operations, segment
tree, Fenwick tree, LCA.

Strings Naive matching, KMP, Rabin-Karp, Boyer-Moore, Aho-Corasick, suffix array, suffix tree, Z-algorithm, edit
distance, regex automata.

Math / number theory Euclid, extended Euclid, sieve, fast exponentiation, modular inverse, CRT, Miller-Rabin, FFT, Gaussian
elimination.

Cryptography AES, ChaCha20, RSA, ECC, Diffie-Hellman, ECDH, ECDSA, EdDSA, SHA-256, SHA-3, HMAC, Argon2.

Compression RLE, Huffman, arithmetic coding, LZ77, LZ78, LZW, DEFLATE, JPEG-style DCT, audio/video codecs.

Geometry Orientation test, convex hull, closest pair, sweep line, point-in-polygon, Voronoi, Delaunay, polygon triangulation.

Randomized Randomized quicksort, reservoir sampling, Bloom filter, skip list, Monte Carlo, Las Vegas algorithms.

Databases B-tree, B+ tree, hash join, sort-merge join, nested-loop join, query optimization, WAL, LRU/LFU cache
replacement.

Operating systems FCFS, SJF, round robin, priority scheduling, LRU/FIFO page replacement, Banker's algorithm, deadlock detection.

Distributed systems Consensus concepts, Paxos, Raft, consistent hashing, vector clocks, leader election, MapReduce.

Machine learning Linear/logistic regression, k-NN, Naive Bayes, decision trees, random forests, boosting, k-means, PCA, SVM,
neural networks, backpropagation, attention.

Optimisation Gradient descent, SGD, Newton, simplex, simulated annealing, genetic algorithms, local search, hill climbing.

Final advice: Algorithms are best learned by tracing small examples by hand, then implementing them, then
testing edge cases. Memorising names alone is not enough.

Page 17