ILTS Computer Science (205) cheat sheet

Big-O classes in ascending growth: O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!).

Binary search requires a sorted array and runs in O(log n); each comparison eliminates half the remaining search space.

Merge sort is O(n log n) in all cases and stable but needs O(n) auxiliary space; quicksort averages O(n log n) and is in-place but worst-case O(n^2).

A binary search tree supports search, insert, and delete in O(h), where h is height; a balanced tree keeps h = O(log n), a degenerate tree gives O(n).

Breadth-first search uses a queue and finds shortest paths in unweighted graphs in O(V + E); depth-first search uses a stack or recursion.

Dijkstra's algorithm finds single-source shortest paths on non-negative edge weights; Bellman-Ford handles negative edges and detects negative cycles.

Number bases: binary 1101 equals decimal 13; each hex digit maps to exactly four bits, so one byte is two hex digits.

Two's complement negates a value by inverting all bits and adding 1; an n-bit signed range is -2^(n-1) to 2^(n-1) - 1.

Boolean identities include De Morgan's laws: NOT(A AND B) = (NOT A) OR (NOT B), and NOT(A OR B) = (NOT A) AND (NOT B).

Value parameters copy the argument; reference parameters alias the caller's variable, so mutations inside the procedure are visible to the caller.

A while loop tests before each iteration and may run zero times; a do-while tests after the body and always runs at least once.

Scope rules: a local variable shadows a same-named outer variable, and block-scoped variables cease to exist when their block exits.

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

Pass-by-value semantics for object references copy the reference, not the object, so methods can mutate the object's fields but cannot reassign the caller's reference.

Compilation translates source to machine code ahead of time; interpretation executes statements directly; JIT compilation combines both at run time.

Unit tests isolate one unit and assert expected outputs; integration tests verify that components work together; regression tests guard previously fixed defects.

Encapsulation hides internal state behind methods; inheritance reuses a superclass contract; polymorphism dispatches a call to the correct subclass implementation.

Version control commits form a directed history; a merge combines branches, and a conflict occurs when both branches edit the same lines.

A stack is last-in-first-out with push and pop; a queue is first-in-first-out with enqueue and dequeue; a deque allows both ends.

A hash table gives average O(1) lookup but degrades to O(n) when many keys collide; load factor equals entries divided by buckets.

Arrays give O(1) indexed access and O(n) insertion or deletion in the middle; linked lists give O(1) insertion given a node reference but O(n) search.

A heap is a complete binary tree stored in an array where parent index i has children 2i+1 and 2i+2; insert and extract-min are O(log n).

Traversals: preorder visits root-left-right, inorder visits left-root-right (sorted output for a BST), postorder visits left-right-root.

Relational keys: a primary key uniquely identifies a row and cannot be null; a foreign key references a primary key in another table and enforces referential integrity.

SQL joins: INNER returns matching rows only; LEFT returns all left rows plus matches; FULL returns all rows from both sides with nulls where unmatched.

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

ACID properties are Atomicity, Consistency, Isolation, and Durability; an index speeds reads but adds write cost and storage.

The fetch-decode-execute cycle: the program counter addresses the next instruction, which is loaded into the instruction register and decoded by the control unit.

Memory hierarchy from fastest to slowest: registers, cache (L1/L2/L3), RAM, SSD/disk, tape; each level trades capacity for speed and cost.

IPv4 addresses are 32 bits; IPv6 addresses are 128 bits. A subnet mask separates the network portion from the host portion of an address.

TCP is connection-oriented and reliable with handshake, sequencing, and retransmission; UDP is connectionless and unreliable but has lower overhead.

DNS resolves names to IP addresses; DHCP assigns addresses dynamically; ARP maps IP addresses to MAC addresses on a local network.

The OSI model has seven layers: Physical, Data Link, Network, Transport, Session, Presentation, Application; TCP/IP collapses these into four.

Symmetric encryption uses one shared key and is fast; asymmetric encryption uses a public/private pair and enables key exchange and digital signatures.

Hashing verifies integrity but is not encryption; salting defeats rainbow tables; TLS combines asymmetric key exchange with symmetric bulk encryption.

Common attacks: phishing (deceptive messages), SQL injection (unvalidated input altering queries), DDoS (flooding), and man-in-the-middle (intercepted traffic).

The ACM Code of Ethics core principles include contributing to society, avoiding harm, being honest and trustworthy, and respecting privacy.

FERPA protects students' education records and restricts disclosure without consent; COPPA governs collection of data from children under 13.

Copyright protects original expression fixed in a tangible medium; it does not protect ideas, algorithms, or facts, which patents or trade secrets may cover.

Open-source licenses differ: permissive licenses (MIT, Apache) allow proprietary reuse; copyleft licenses (GPL) require derivative works to stay open.

Fair use weighs purpose, nature, amount used, and market effect; educational use is not automatically exempt.

Digital divide refers to unequal access to devices, connectivity, and skills; it affects participation in computing education and employment.

Algorithmic bias arises when training data or design choices encode historical inequities, producing unfair outcomes in areas such as hiring or lending.

Computing professions address accessibility through universal design, screen-reader compatibility, and keyboard navigation rather than add-on fixes.

Formative assessment informs instruction during learning; summative assessment judges achievement at the end of a unit or course.

Bloom's revised taxonomy orders objectives: remember, understand, apply, analyze, evaluate, create; verbs in a standard should match the intended level.

Constructivism holds that learners build knowledge by connecting new information to prior conceptions; misconceptions must be surfaced and addressed explicitly.

Pair programming assigns driver (keyboard) and navigator (review) roles that rotate; it supports collaboration and code review skills.

Parsons problems present shuffled code lines for reordering, lowering syntax burden while assessing logical sequencing.

Rubrics list criteria and performance levels; analytic rubrics score criteria separately, holistic rubrics assign a single overall score.

The PRIMM model sequences instruction as Predict, Run, Investigate, Modify, Make, moving from reading code to writing it.

Equity practices include culturally relevant contexts, avoiding unnecessary prerequisites, and providing multiple means of representation and expression.

AP Computer Science A uses Java and free-response questions scored with point-based rubrics; AP CSP uses a performance task and multiple-choice exam.