Algorithms · Prerequisites

Prerequisites for Algorithms

Algorithms combine programming, mathematical reasoning, data structures, proof techniques, complexity analysis, graph theory, probability, and optimization.

Core background

The strongest preparation is practical programming experience together with the ability to reason about runtime, recursion, correctness, graphs, and combinatorial growth.

Programming · Proofs · Analysis

Essential Background

These topics support complexity analysis, sorting and searching, graph and string algorithms, dynamic programming, approximation, randomization, online algorithms, divide-and-conquer, greedy methods, backtracking, and branch-and-bound.

PF

Programming Fundamentals

Variables · loops · functions

Algorithm design is much easier when basic programming constructs are already automatic.

Technical significance

You should be able to translate pseudocode into working code and trace execution without struggling with syntax.

ProgrammingLoopsFunctions
Be comfortable with variables, conditionals, loops, functions, arrays/lists, and simple input/output.
  • Trace nested loops.
  • Write helper functions.
  • Implement pseudocode faithfully.

Connections: sorting, searching, graph traversal, recursion, dynamic programming.
DS

Data Structures

Arrays · stacks · queues · trees · heaps

Algorithms depend heavily on how input and intermediate state are represented.

Technical significance

A strong algorithm can perform poorly when paired with an unsuitable data structure.

ArraysQueuesTreesHeaps
Know operation costs for arrays, linked lists, stacks, queues, hash tables, trees, heaps, and graphs.

Connections: Dijkstra, BFS/DFS, heapsort, union-find, memoization.
DM

Discrete Mathematics

Sets · relations · logic

Algorithms are described with sets, functions, relations, sequences, and logical conditions.

Technical significance

Discrete mathematics is the language of correctness and complexity.

SetsFunctionsLogic
Be comfortable with sets, Cartesian products, functions, relations, sequences, and quantifiers.

Connections: graphs, combinatorics, proofs, recurrences.
PR

Mathematical Proofs

Induction · contradiction · invariants

Correctness is as important as runtime.

Technical significance

Proof techniques explain why an algorithm always returns the right answer.

InductionInvariantContradiction
Know direct proof, contradiction, induction, and loop invariants.
  • Initialization, maintenance, termination.
  • Use induction for recursive algorithms.
  • Construct counterexamples.
BO

Big-O Notation

Asymptotic growth · scalability

Algorithm analysis compares how resource use grows with input size.

Technical significance

Big-O, Big-Theta, and Big-Omega provide the basic vocabulary for runtime and space.

Big-OThetaOmega
Know O(1), O(log n), O(n), O(n log n), O(n²), O(2^n), and O(n!).

Connections: runtime analysis, scalability, NP-hard search.
LE

Logarithms & Exponents

log n · powers · growth

Binary search, divide-and-conquer, heaps, and balanced trees produce logarithmic behavior.

Technical significance

Exponential and factorial growth explain why brute force quickly becomes infeasible.

LogarithmsExponents
Understand powers, log₂n, exponent laws, and rough growth comparisons.

Connections: binary search, recurrences, divide-and-conquer.
RC

Recursion

Base case · recursive case · call stack

Many algorithms are naturally recursive.

Technical significance

Recursion is central to divide-and-conquer, DFS, backtracking, and tree algorithms.

RecursionCall Stack
Trace recursive calls, identify base cases, and understand recursion depth.

Connections: mergesort, quicksort, DFS, backtracking, dynamic programming.
RR

Recurrence Relations

T(n) · recursive runtime

Recursive algorithms often require recurrence equations for runtime analysis.

Technical significance

Recurrences convert recursive structure into mathematical cost models.

RecurrencesMaster Theorem
Recognize forms such as T(n)=2T(n/2)+n. Use substitution, recursion trees, and the Master Theorem for standard forms.
PB

Probability

Random variables · expectation

Randomized algorithms use probability as part of the algorithm.

Technical significance

Expected runtime and failure probability require basic probability skills.

ProbabilityExpectation
Know independence, conditional probability, expectation, and repeated trials.

Connections: randomized quicksort, hashing, primality tests.
GR

Graphs

Vertices · edges · paths · cycles

A large part of the course operates directly on graphs.

Technical significance

Graph algorithms require comfort with graph terminology and representation.

GraphsPathsAdjacency
Know directed/undirected graphs, weighted edges, paths, cycles, connectedness, trees, adjacency lists and matrices.

Connections: shortest paths, MST, max flow, A*, TSP.
CB

Basic Combinatorics

Counting · permutations · combinations

Search spaces are often combinatorial.

Technical significance

Counting explains why exhaustive algorithms become exponential or factorial.

CountingPermutations
Know factorials, combinations, permutations, and product-rule counting.

Connections: TSP, backtracking, branch-and-bound, NP-complete problems.
SS

Sorting & Searching Basics

Order · comparison · binary search

Many later algorithms assume data can be sorted or searched efficiently.

Technical significance

Sorting is often an essential preprocessing step.

SortingBinary Search
Know linear search, binary search, and common comparison sorting behavior.

Connections: Kruskal, divide-and-conquer, selection, preprocessing.
AC

Algorithm Correctness

Preconditions · postconditions · invariants

An efficient algorithm is useless if it computes the wrong result.

Technical significance

Correctness reasoning should accompany design.

CorrectnessSpecification
State preconditions and postconditions, identify loop invariants, and separate termination from partial correctness.
OP

Basic Optimization

Objective · constraints · feasible solution

Dynamic programming, greedy, approximation, and branch-and-bound solve optimization problems.

Technical significance

You should be able to identify what is minimized or maximized.

OptimizationObjective
Recognize decision variables, feasible solutions, objective functions, and bounds.

Connections: shortest path, MST, knapsack, scheduling.
BM

Bit Manipulation

Bits · masks · shifts

Bit operations are useful in subset algorithms, hashing, and low-level optimization.

Technical significance

Bit masks encode finite sets compactly.

BitsMasksShifts
Know AND, OR, XOR, NOT, left/right shift, and binary representation.

Connections: subset DP, combinatorial search, number theory.
DT

Debugging & Testing

Tracing · edge cases · validation

Algorithm bugs often appear only on boundary cases.

Technical significance

Systematic testing reveals implementation errors and incorrect assumptions.

DebuggingTesting
Test empty input, one element, duplicates, sorted/reverse-sorted input, disconnected graphs, and extreme values. Compare with a slow reference on small cases.
CC

Complexity Classes

P · NP · NP-hard · NP-complete

Later topics include approximation and NP-completeness.

Technical significance

Basic complexity vocabulary explains why some problems need approximation or exponential search.

PNPNP-Complete
P: polynomial-time solvable. NP: polynomial-time verifiable. NP-hard: at least as hard as all NP problems. NP-complete: in NP and NP-hard.
LA

Basic Linear Algebra

Vectors · matrices

Matrix representations appear in graph and dynamic-programming algorithms.

Technical significance

Comfort with matrix notation helps with matrix-based methods.

MatricesVectors
Know dimensions, row/column indexing, and simple multiplication.

Connections: Floyd-Warshall, transitive closure, matrix algorithms.
PA

Parallelism Basics

Tasks · dependencies · speedup

Parallel algorithms require more than running loops on several cores.

Technical significance

Dependencies, synchronization, communication, and load balance determine speedup.

ParallelismSpeedup
Understand work, dependencies, critical paths, synchronization overhead, and load balance.

Connections: parallel sorting, prefix operations, work/span.
OD

Online Decision Making

Unknown future · competitive ratio

Online algorithms act before future input is known.

Technical significance

Performance is compared with an optimal offline solution.

OnlineCompetitive Ratio
Understand irreversible decisions, adversarial input order, and competitive analysis.

Connections: paging, caching, scheduling, online matching.
No prerequisite matches your search or filter.