Computer Science Level 3 cheat sheet

Big-O bounds describe growth of an algorithm's work as input size n grows: O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n).

Binary search requires a sorted array and halves the search interval each step, giving O(log n) comparisons; linear search is O(n) and needs no ordering.

A problem is decidable if some algorithm always halts with a correct yes/no answer; the halting problem is undecidable.

P problems are solvable in polynomial time; NP problems have polynomial-time verifiable certificates; whether P = NP is open.

Decomposition splits a problem into independent subproblems; abstraction hides detail behind an interface, keeping only relevant properties.

Recursion needs a base case plus a recursive case that strictly reduces the problem size, or it will not terminate.

Merge sort and heap sort run in O(n log n) worst case; quicksort averages O(n log n) but degrades to O(n^2) worst case.

A greedy algorithm is correct only when the problem has the greedy-choice property and optimal substructure; otherwise use dynamic programming.

Loop invariants state a condition true before and after each iteration; initialization, maintenance, and termination together prove correctness.

Pass by value copies the argument; pass by reference lets the callee modify the caller's variable - the distinction determines observable side effects.

A variable's scope is where its name is visible; lifetime is when its storage exists - the two are related but not identical.

Compilers translate source to machine code before execution; interpreters execute statements directly, trading speed for flexibility.

Unit tests exercise one function in isolation; integration tests check interaction between components; both belong to a regression suite.

Version control commits are immutable snapshots identified by hashes; branches are movable pointers to commits, enabling parallel work.

Exceptions propagate up the call stack until caught; a finally block runs whether or not an exception escapes.

An API contract specifies parameter types, return types, and error behavior; callers may rely only on what the contract guarantees.

Refactoring changes internal structure without changing external behavior, so existing tests should still pass unchanged.

Array indexing is O(1); inserting or deleting in the middle is O(n) because elements shift.

A linked list gives O(1) insertion or deletion at a known node but O(n) search because nodes are not contiguous.

A stack is LIFO (push/pop); a queue is FIFO (enqueue/dequeue); both support O(1) operations at their ends.

A hash table averages O(1) lookup but degrades to O(n) when collisions cluster; load factor triggers resizing.

A balanced binary search tree (e.g., AVL, red-black) keeps height O(log n), so search, insert, and delete are O(log n).

A heap supports O(1) peek at the min or max and O(log n) insert and extract; building a heap from n items is O(n).

Breadth-first search uses a queue and finds shortest paths in unweighted graphs; depth-first search uses a stack or recursion.

A relational table's primary key uniquely identifies rows; a foreign key references another table's primary key to enforce referential integrity.

Normalization removes redundancy: 1NF atomic values, 2NF no partial dependencies on a composite key, 3NF no transitive dependencies.

The CPU fetch-decode-execute cycle reads an instruction at the program counter, decodes it, executes it, and updates the counter.

The memory hierarchy trades size for speed: registers, cache (L1/L2/L3), RAM, SSD/disk - each level is larger and slower than the one above.

Binary numbers use base 2; one byte is 8 bits, so n bits encode 2^n distinct values (unsigned range 0 to 2^n − 1).

Two's complement represents negatives by inverting bits and adding one; it makes addition and subtraction the same hardware operation.

The TCP/IP stack layers application, transport, internet, and link; TCP is reliable and connection-oriented, UDP is unreliable and connectionless.

IPv4 addresses are 32 bits; DNS resolves names to addresses; DHCP assigns addresses dynamically; HTTPS is HTTP over TLS.

Symmetric encryption uses one shared key (fast, e.g., AES); asymmetric encryption uses a public/private pair (e.g., RSA) for key exchange or signatures.

Hashing verifies integrity but is not encryption; salting and slow hashes (bcrypt, Argon2) defend stored passwords against precomputation.

The CIA triad is confidentiality, integrity, availability; authentication proves identity, authorization decides permitted actions.

Mean is sensitive to outliers; median is the middle value of sorted data and is robust; mode is the most frequent value.

Standard deviation measures spread around the mean; variance is its square, so units differ between the two.

Correlation r ranges from −1 to 1 and measures linear association only; correlation does not establish causation.

A histogram bins a numeric variable to show distribution shape; a bar chart compares categorical counts; a scatter plot shows two-variable relationships.

Sampling bias arises when the sample is not representative; random sampling reduces it but does not eliminate small-sample variability.

A p-value is the probability of data at least as extreme given the null hypothesis is true; it is not the probability the null is true.

Data cleaning steps include removing duplicates, handling missing values (drop or impute), and standardizing units and formats.

Overfitting means a model fits training noise and generalizes poorly; held-out validation or cross-validation detects it.

Algorithmic bias occurs when training data or design encodes historical inequity, producing systematically unfair outputs.

Informed consent requires disclosing what data is collected, why, and to whom it is shared before collection.

The digital divide describes unequal access to devices, connectivity, and skills, which amplifies existing social and economic gaps.

Open-source licenses (e.g., MIT, GPL) grant reuse rights under conditions; GPL is copyleft, requiring derivative works to stay open.

Intellectual property protection for software includes copyright (code), patents (processes), and trade secrets.

Automation shifts labor demand; it displaces some roles while creating others, and the net effect varies by skill level and region.

A professional code of ethics (e.g., ACM/IEEE) prioritizes public welfare, honesty about capability, and avoidance of harm.

Accessibility standards (WCAG) require perceivable, operable, understandable, and robust interfaces so users with disabilities can use software.

Data protection principles include purpose limitation, data minimization, and storage limitation, limiting collection to what is needed.