OSAT Computer Science (OK181) cheat sheet

Decomposition, pattern recognition, abstraction, and algorithm design are the four pillars of computational thinking; abstraction removes detail irrelevant to the problem while preserving essential structure.

Binary place values double leftward from 1: 1011₂ = 8+0+2+1 = 11₁₀; hexadecimal groups four bits per digit, so 0xF3 = 1111 0011₂ = 243₁₀.

Two's complement: invert all bits and add 1 to negate; an n-bit signed range is −2^(n−1) to 2^(n−1)−1, so 8-bit signed values run −128 to 127.

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

Logic gate truth rules: AND outputs 1 only if all inputs are 1; OR outputs 1 if any input is 1; NAND and NOR are the negations of AND and OR and are each functionally complete alone.

ASCII uses 7 bits (128 codes); extended ASCII uses 8; Unicode assigns code points and UTF-8 encodes them in 1–4 bytes, backward-compatible with ASCII for code points below 128.

A finite state machine is defined by states, an input alphabet, a transition function, a start state, and accepting states; it has no memory beyond its current state.

Problem-solving sequence: understand the problem, identify inputs/outputs and constraints, design the algorithm, implement, test with normal, boundary, and invalid data, then refine.

Variable scope: local variables exist only within their block or function; global variables are visible throughout the module; parameter passing by value copies, by reference shares the caller's object.

Control structures: sequence, selection (if/else, switch), and iteration (count-controlled for, condition-controlled while, and do-while which tests after executing once).

Loop invariants state what stays true before and after each iteration; they are the standard tool for proving a loop computes the intended result and terminates.

Recursion requires a base case and a recursive case that moves toward it; each call consumes stack frames, so deep recursion risks stack overflow where iteration does not.

Big-O of common patterns: single loop over n is O(n); nested loops over n are O(n²); halving the range each step is O(log n); sorting then binary searching is O(n log n).

Searching: linear search is O(n) and works on unsorted data; binary search is O(log n) but requires a sorted array and random access to the middle element.

Sorting comparisons: bubble, selection, and insertion are O(n²) average; merge sort and heap sort are O(n log n) in all cases; quicksort averages O(n log n) but degrades to O(n²) on poor pivots.

Debugging strategy: reproduce the fault, isolate it by narrowing inputs or code regions, form a hypothesis, test with a minimal case, fix, then add a regression test.

Array: contiguous, O(1) indexed access, O(n) insertion or deletion in the middle; a dynamic array amortizes growth by doubling capacity.

Linked list: nodes hold data plus a pointer; O(1) insertion or deletion given the node, but O(n) search and no random access; a doubly linked list adds a previous pointer.

Stack is LIFO (push/pop); queue is FIFO (enqueue/dequeue); a deque allows both ends; these are used for expression evaluation, undo, and breadth-first traversal.

Hash table: average O(1) lookup, insert, and delete; collisions are handled by chaining or open addressing; performance degrades toward O(n) as the load factor approaches 1.

Binary search tree: in-order traversal yields sorted output; operations are O(log n) when balanced but O(n) in the worst case, which balanced trees such as AVL and red-black trees prevent.

Heap: a complete binary tree stored in an array where each parent compares favorably with its children; insert and remove-min/max are O(log n), peek is O(1), and it backs a priority queue.

Graph representations: an adjacency matrix uses O(V²) space and answers edge queries in O(1); an adjacency list uses O(V+E) space and suits sparse graphs.

Traversal and shortest path: BFS uses a queue and finds shortest paths in unweighted graphs; DFS uses a stack or recursion; Dijkstra requires nonnegative edge weights.

CPU cycle: fetch, decode, execute, store; the program counter holds the next instruction address, and the ALU performs arithmetic and logic operations on registers.

Memory hierarchy from fastest to slowest: registers, cache (L1/L2/L3), RAM, SSD/disk, tape; each level trades capacity and cost per byte for speed, and locality of reference makes caches effective.

OS responsibilities: process scheduling, memory allocation, file systems, device drivers, and access control; a process owns an address space, while threads of one process share memory.

Network layers (TCP/IP): application, transport, internet, and link; TCP is connection-oriented and reliable, UDP is connectionless and best-effort, and IP handles addressing and routing.

Addressing: MAC addresses identify hardware on a local link, IPv4 addresses are 32 bits in dotted decimal, IPv6 is 128 bits in hex, and DNS maps names to IP addresses.

Confidentiality, integrity, and availability form the CIA triad; encryption protects confidentiality, hashing detects tampering, and redundancy supports availability.

Symmetric encryption uses one shared key; asymmetric encryption uses a public/private pair for key exchange and signatures; TLS combines both to secure web traffic.

Common attacks: phishing (deceptive messages), SQL injection (unvalidated input altering queries), and malware; defenses include input validation, least privilege, patching, and multi-factor authentication.

Relational model: tables hold rows (records) and columns (attributes); a primary key uniquely identifies a row, and a foreign key references a primary key in another table to enforce referential integrity.

Normalization: 1NF removes repeating groups, 2NF removes partial dependencies on part of a composite key, and 3NF removes transitive dependencies on non-key attributes.

SQL categories: SELECT (DML query), INSERT/UPDATE/DELETE (DML changes), CREATE/ALTER/DROP (DDL schema); WHERE filters rows, GROUP BY aggregates, and HAVING filters aggregated groups.

Joins: INNER returns matching rows only, LEFT returns all left rows plus matches, RIGHT the reverse, and FULL returns all rows from both sides with NULLs where unmatched.

ACID properties of transactions: atomicity (all or nothing), consistency (valid state to valid state), isolation (concurrent transactions do not interfere), and durability (committed changes persist).

Data types and quality: numeric, text, date/time, and boolean types constrain values; quality dimensions include accuracy, completeness, consistency, timeliness, and validity.

Analysis workflow: state a question, collect and clean data, explore with summary statistics and visualizations, model, then interpret; correlation does not establish causation.

Visualization choice: bar charts compare categories, line charts show trends over time, histograms show distributions, and scatter plots show relationships between two variables.

Computing impacts to evaluate: economic (automation and job change), social (access and digital divide), environmental (energy and e-waste), and legal (intellectual property and privacy).

Ethical frameworks applied to computing: utilitarian (greatest good), deontological (duties and rules), and virtue (character); each can yield different conclusions on the same case.

ACM Code of Ethics core duties: contribute to society and human well-being, avoid harm, be honest and trustworthy, be fair and avoid discrimination, and respect privacy.

Intellectual property: copyright protects expression, patents protect novel inventions, trademarks protect brand identifiers, and trade secrets protect confidential information; open-source licenses grant defined reuse rights.

Privacy principles: collect only necessary data (minimization), obtain informed consent, limit retention, and protect data with appropriate safeguards; FERPA governs student education records in the US.

Digital divide dimensions: access to devices, connectivity, and the skills needed to use them effectively; unequal access affects educational and economic outcomes.

Professional practice: document decisions, use version control, review code, test changes, credit others' work, and disclose conflicts of interest or security vulnerabilities responsibly.

Accessibility: WCAG principles are perceivable, operable, understandable, and robust; captions, alt text, keyboard navigation, and sufficient contrast reduce barriers.

AP CSA is Java-based; AP CSP emphasizes computational thinking and programming through projects, and both use multiple-choice plus performance or free-response components.

Formative assessment (exit tickets, live coding checks, peer review) guides instruction during learning; summative assessment (unit tests, projects) measures achievement at the end.

Pair programming roles: driver writes code while navigator reviews and plans; roles should rotate so each student practices both.

Parsons problems (reordering scrambled code lines) and PRIMM (predict, run, investigate, modify, make) reduce syntax load and build program comprehension before writing from scratch.

Culturally responsive CS teaching: connect content to students' interests and communities, use collaborative and choice-based tasks, and actively recruit underrepresented groups.

Equity in access: unplugged activities, low-cost or browser-based tools, and clear scaffolds widen participation for students without home computers or prior experience.

Rubrics for programming should separate correctness, algorithm design, code style and documentation, and testing; analytic rubrics give per-criterion feedback.

Misconception diagnosis: common errors include confusing = with ==, off-by-one loop bounds, treating array indexes as 1-based, and misunderstanding scope; targeted questions expose them.

Placeholder section: this domain is merged with Computer Science Instruction and Assessment; see that section for instructional and assessment facts.

Formative checks such as exit tickets, live coding observation, and peer review inform in-lesson adjustments; summative tests and projects measure end-of-unit mastery.

Parsons problems and PRIMM (predict, run, investigate, modify, make) lower syntax load and build comprehension before independent coding.

Rubrics separate correctness, algorithm design, style and documentation, and testing so feedback targets each criterion.

Misconceptions to probe: = versus ==, off-by-one loop bounds, 1-based array indexing, and variable scope.

Equity strategies: unplugged activities, browser-based tools, and scaffolds support students lacking devices or prior experience.

AP CSA uses Java; AP CSP centers computational thinking and a performance task; both combine multiple-choice with written or project components.