OAE Computer Science cheat sheet

Number base conversion: repeatedly divide by the target radix and read remainders bottom-up; to convert to decimal, sum each digit times its place value (e.g., binary 1101 = 8+4+1 = 13).

Two's complement of an n-bit value: invert all bits and add 1. Range is -2^(n-1) to 2^(n-1)-1; the most significant bit carries weight -2^(n-1).

Boolean identities: De Morgan's laws ¬(A∧B) = ¬A∨¬B and ¬(A∨B) = ¬A∧¬B; XOR is 1 when inputs differ and equals (A∧¬B)∨(¬A∧B).

Big-O growth ordering: O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!). Constants and lower-order terms are dropped.

Master Theorem for T(n) = aT(n/b) + f(n): compare f(n) with n^(log_b a); larger side dominates, equal sides give an extra log factor, smaller f(n) gives Θ(n^(log_b a)).

Loop analysis rule: nested loops multiply their iteration counts; sequential loops add. A loop that halves its counter each pass is O(log n).

Recursion requires a base case and a progress step toward it; each call consumes stack space, so depth-d recursion uses O(d) auxiliary space.

Algorithm categories: divide-and-conquer (merge sort), greedy (Dijkstra, Huffman), dynamic programming (optimal substructure plus overlapping subproblems), and backtracking.

Value vs. reference semantics: primitives are copied on assignment and argument passing; objects/arrays pass a reference, so callee mutation is visible to the caller.

Scope rules: a variable is visible from its declaration to the end of its block; a local declaration shadows an outer one of the same name.

Pass-by-value vs. pass-by-reference: pass-by-value cannot change the caller's variable; pass-by-reference (or passing an object reference) can.

Compilation pipeline: source → lexer (tokens) → parser (syntax tree) → semantic analysis → intermediate code → optimization → code generation; a linker resolves external symbols.

Error classes: syntax errors are caught at compile/parse time; runtime errors (division by zero, null dereference) occur during execution; logic errors produce wrong output with no diagnostic.

Short-circuit evaluation: in A && B, B is skipped when A is false; in A || B, B is skipped when A is true.

Testing vocabulary: unit tests isolate one function, integration tests combine components, black-box tests use only the interface, and white-box tests use internal structure for coverage.

Loop control: break exits the innermost loop, continue skips to the next iteration, and a while loop may execute zero times while do-while always executes at least once.

Array: O(1) indexed access, O(n) insert/delete at arbitrary positions; dynamic arrays amortize O(1) append by doubling capacity.

Linked list: O(1) insert/delete given a node reference, O(n) search; singly linked lists cannot traverse backward, doubly linked lists can.

Stack is LIFO (push/pop at top); queue is FIFO (enqueue at rear, dequeue at front); a deque allows both ends.

Binary search requires a sorted array, runs in O(log n), and uses mid = low + (high - low)/2 to avoid overflow.

Binary search tree: average O(log n) search/insert/delete; degenerates to O(n) when unbalanced. In-order traversal yields sorted order.

Balanced trees: AVL enforces height balance via rotations; a red-black tree guarantees O(log n) with fewer rotations, so it is preferred for frequent insertion.

Hash table: average O(1) lookup; collisions are resolved by chaining or open addressing. Load factor drives resizing; worst case is O(n).

Heap: a complete binary tree with the parent ≤ children (min-heap); insert and extract-min are O(log n), peek is O(1); heapsort is O(n log n) in place.

Sorting properties: merge sort is stable and O(n log n) but needs O(n) extra space; quicksort averages O(n log n) with O(n^2) worst case and is in place; insertion sort is O(n^2) but adaptive on nearly sorted data.

Graph traversal: BFS uses a queue and finds shortest paths in unweighted graphs; DFS uses a stack/recursion and detects cycles. Dijkstra requires non-negative edge weights.

CPU cycle: fetch → decode → execute → writeback. Clock rate is cycles per second; execution time = instruction count × CPI / clock rate.

Memory hierarchy from fastest to slowest: registers, cache (L1/L2/L3), RAM, SSD/disk. Locality (temporal and spatial) explains cache hit rates.

OS roles: process scheduling, virtual memory (paging maps virtual to physical addresses via a page table and TLB), file systems, and device I/O.

OSI seven layers: Physical, Data Link, Network, Transport, Session, Presentation, Application. TCP/IP collapses these into link, internet, transport, and application layers.

TCP is connection-oriented and reliable (three-way handshake, acknowledgments, retransmission); UDP is connectionless and unreliable but low-latency.

Addressing: IPv4 is 32 bits, IPv6 is 128 bits; a subnet mask separates network and host bits; DNS resolves names to IP addresses; DHCP assigns addresses dynamically.

CIA triad: confidentiality (encryption), integrity (hashing, MACs), availability (redundancy). Symmetric encryption (AES) uses one shared key; asymmetric (RSA) uses a public/private pair.

Common attacks: SQL injection (mitigate with parameterized queries), XSS (escape output), phishing (social engineering), and man-in-the-middle (mitigate with TLS).

Access control models: DAC (owner discretion), MAC (labels/clearances), and RBAC (role-based permissions).