Keyboard shortcuts

Go home G then H
Browse sets G then B
Create set G then C
My library G then L
Show shortcuts ?
Go back Swipe from left edge
Library

Advanced Computer Science — Algorithms

Algorithm design paradigms, complexity, and advanced techniques

N
np_hard_nph 24 terms Feb 27, 2026
Flashcards
Learn
Written
Match
Test
Blitz

Terms 24

1
Time Complexity
How runtime grows with input size n; expressed in Big O; worst-case unless stated
2
Space Complexity
How memory usage grows with input size; includes stack space for recursion
3
Amortized Analysis
Average cost per operation over sequence; e.g. dynamic array append is O(1) amortized despite O(n) resizes
4
Divide and Conquer
Break into subproblems, solve recursively, combine; merge sort T(n) = 2T(n/2) + O(n)
5
Master Theorem
Solves T(n) = aT(n/b) + f(n) recurrences; three cases based on f(n) vs n^(log_b a)
6
Dynamic Programming
Break into overlapping subproblems; memoize results; bottom-up or top-down
7
Optimal Substructure
Optimal solution contains optimal solutions to subproblems; DP requires this
8
Overlapping Subproblems
Same subproblems recur; memoization avoids recomputation; distinguishes DP from D&C
9
Greedy Algorithm
Makes locally optimal choice at each step; works when greedy choice property holds
10
Greedy Choice Property
Globally optimal solution can be built by choosing locally optimal at each step
11
Dijkstra's Algorithm
Single-source shortest paths with nonnegative weights; O((V+E)logV) with min-heap
12
Bellman-Ford Algorithm
Shortest paths allowing negative weights; detects negative cycles; O(VE)
13
Floyd-Warshall Algorithm
All-pairs shortest paths; O(V³); handles negative weights (not negative cycles)
14
Prim's Algorithm
Minimum spanning tree; grows from one vertex; O(ElogV); greedy
15
Kruskal's Algorithm
MST by sorting edges and adding if no cycle (Union-Find); O(ElogE)
16
P vs NP
P: polynomial-time solvable; NP: polynomial-time verifiable; P=NP? unsolved
17
NP-Complete
In NP and as hard as any NP problem; if one solvable in poly-time, all are; SAT is NP-complete
18
NP-Hard
At least as hard as NP-complete problems; not necessarily in NP; e.g. halting problem
19
Reduction
Transform one problem to another; if A reduces to B and B is easy, so is A
20
Approximation Algorithm
Finds near-optimal solution for NP-hard problem; guaranteed within ratio of optimal
21
Backtracking
Explore solution space recursively; prune branches that violate constraints
22
Branch and Bound
Backtracking with bounds on subproblem optima; prunes unpromising branches
23
Randomized Algorithms
Use random choices; Las Vegas (always correct), Monte Carlo (probably correct); e.g. quicksort
24
FFT (Fast Fourier Transform)
Computes DFT in O(n log n); divide and conquer; polynomial multiplication, signal processing