IB Computer Science SL cheat sheet

System fundamentals: a computer system is hardware + software + data + users + procedures; the four stages of the system life cycle are analysis, design, development, and implementation/testing (with evaluation feeding back to analysis).

Binary basics: n bits represent 2^n distinct values; unsigned range is 0 to 2^n − 1. Two's complement range for n bits is −2^(n−1) to 2^(n−1) − 1; negate by inverting bits and adding 1.

Data units: 1 byte = 8 bits; 1 KiB = 2^10 bytes = 1024 B; 1 MiB = 2^20 B; 1 GiB = 2^30 B. Decimal prefixes (kB, MB) use powers of 1000.

Number conversions: hexadecimal uses 16 digits (0–9, A–F); each hex digit maps to exactly 4 binary bits, so grouping binary from the right in 4s converts to hex directly.

Logic: AND outputs 1 only if both inputs are 1; OR outputs 1 if at least one input is 1; NOT inverts; XOR outputs 1 when inputs differ. A NAND gate is universal - any circuit can be built from NAND gates alone.

Boolean algebra laws: A·A = A, A + A = A, A·Ā = 0, A + Ā = 1, A + A·B = A (absorption), A + Ā·B = A + B. De Morgan: NOT(A·B) = NOT A + NOT B; NOT(A + B) = NOT A · NOT B.

Networks: LAN covers a small geographic area under single ownership; WAN spans large distances. A router forwards packets between networks; a switch forwards frames within a LAN using MAC addresses; a hub broadcasts to all ports.

Topologies: star - central switch/AP, single point of failure, easy fault isolation; mesh - redundant paths, high cabling cost; bus - shared backbone, collision-prone. Client-server centralises control; peer-to-peer shares directly between nodes.

Data transmission: serial sends bits one at a time over one channel; parallel sends several simultaneously (skew limits distance). Simplex is one-way, half-duplex alternates, full-duplex is simultaneous both ways.

Abstraction removes unnecessary detail to model a problem; decomposition splits a problem into sub-problems; pattern recognition identifies repeated structure. These three drive computational thinking.

Algorithm efficiency: linear search is O(n) and works on unsorted data; binary search is O(log n) but requires the data to be sorted first.

Sorting: bubble sort repeatedly swaps adjacent out-of-order pairs, O(n²) worst case; selection sort finds the minimum of the unsorted part each pass, O(n²); merge sort divides and merges, O(n log n) but needs extra memory.

Data structures: arrays store fixed-size elements of one type with O(1) indexed access; linked lists store nodes with pointers, giving O(1) insertion at a known position but O(n) access; stacks are LIFO (push/pop); queues are FIFO (enqueue/dequeue).

Trees: a binary tree has at most two children per node; a binary search tree keeps left subtree values smaller and right subtree values larger than the node, giving O(log n) search when balanced.

Recursion: a recursive method must have a base case to terminate and a recursive case that moves toward the base case; each call adds a frame to the call stack, risking stack overflow if depth is large.

Tracing rules: for loops, count iterations from the initial value to the condition inclusive/exclusive as written; for while loops, record variable values after each iteration; nested loops multiply iteration counts.

Search and sort decisions: use binary search only on sorted collections; use merge sort when worst-case guarantees matter; use bubble/selection sort for small n or when memory is tight.

CPU components: the ALU performs arithmetic and logic; the control unit fetches, decodes and coordinates; registers hold the program counter (PC), instruction register (IR), memory address register (MAR), memory data register (MDR) and accumulator (ACC).

Fetch–decode–execute cycle: PC value goes to MAR, memory returns the instruction to MDR then IR, the control unit decodes it, operands are fetched and the ALU executes; the PC is incremented during fetch.

Memory hierarchy from fastest/smallest to slowest/largest: registers, cache (L1/L2/L3), RAM, secondary storage (SSD/HDD), off-line storage. Cache stores recently used instructions/data to reduce average access time.

Primary memory: RAM is volatile and holds running programs and data; ROM is non-volatile and holds the bootstrap loader. Secondary storage is non-volatile and persistent (magnetic, optical, solid-state).

Operating system roles: memory management, process scheduling, device driver management, file system management, user interface, and security/access control.

Virtual memory extends usable RAM by paging inactive pages to disk; thrashing occurs when pages are swapped so frequently that performance collapses.

Polling vs interrupts: polling repeatedly checks a device's status flag, wasting CPU cycles; an interrupt signal suspends the current process and runs an interrupt service routine.

Cloud and virtualisation: a hypervisor runs multiple virtual machines on one host; cloud services are categorised as IaaS, PaaS and SaaS, with trade-offs in control, cost model and data location.

Secondary storage comparison: SSDs have no moving parts, faster random access and lower power draw but higher cost per GB and finite write cycles; HDDs offer cheaper capacity but slower seek times.