Praxis Computer Science cheat sheet

CPU cycle: fetch the instruction at the program counter, decode it, execute it, and write back results; the program counter then advances.

For n-bit two's complement, the representable range is -2^(n-1) to 2^(n-1)-1; negation is invert all bits and add 1.

Memory hierarchy from fastest/smallest to slowest/largest: registers, L1/L2/L3 cache, RAM, SSD, magnetic disk, tape.

Performance = clock rate × instructions per cycle; total time = instruction count × CPI / clock rate.

Amdahl's law: speedup = 1 / ((1 - f) + f/s), where f is the improved fraction and s the improvement factor.

Pipelining overlaps instruction stages; data hazards need forwarding or stalls, control hazards need branch prediction, structural hazards need extra hardware.

RISC uses fixed-length simple instructions, many registers, and load/store architecture; CISC uses variable-length complex instructions and fewer registers.

OS responsibilities include process scheduling, virtual memory and paging, file systems, device drivers, and access control.

1 byte = 8 bits; 1 KiB = 1024 bytes; one hexadecimal digit = 4 bits; ASCII uses 7 bits; UTF-8 is variable-length and backward-compatible with ASCII.

Growth order: O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!).

Bubble, insertion, and selection sort are O(n^2); merge sort is O(n log n) in all cases; quicksort averages O(n log n) but worst case is O(n^2).

Binary search requires a sorted array and runs in O(log n); linear search runs in O(n) and needs no ordering.

Stack is LIFO with push/pop; queue is FIFO with enqueue/dequeue; deque allows insertion and removal at both ends.

Hash table average-case insert, delete, and lookup are O(1); worst case is O(n) when many keys collide.

Balanced binary search tree operations are O(log n); an unbalanced BST can degrade to O(n).

BFS uses a queue and finds shortest paths in unweighted graphs; DFS uses a stack or recursion and detects cycles and connected components.

Recursion requires a base case and a recursive case; each call adds a stack frame, so deep recursion risks stack overflow.

Pass by value copies the argument; pass by reference passes an alias, so callee mutations affect the caller's variable.

Relational terms: relation = table, tuple = row, attribute = column, degree = number of columns, cardinality = number of rows.

Primary key uniquely identifies rows and cannot be NULL; foreign key references another table's primary key and enforces referential integrity.

SQL clause order: SELECT, FROM, WHERE, GROUP BY, HAVING, ORDER BY; WHERE filters rows before grouping, HAVING filters groups after.

1NF requires atomic column values; 2NF removes partial dependencies on part of a composite key; 3NF removes transitive dependencies on non-key attributes.

ACID: atomicity (all or nothing), consistency (constraints preserved), isolation (concurrent transactions do not interfere), durability (committed data survives failure).

Indexes speed reads and slow writes; B-tree indexes support equality and range queries; a clustered index determines physical row order.

Inner join returns matching rows only; left/right outer joins keep all rows from one side; full outer join keeps all rows from both.

Inverted index maps each term to a posting list of documents; Boolean AND/OR/NOT operate on posting lists.

Precision = TP/(TP+FP); recall = TP/(TP+FN); F1 = 2 × precision × recall / (precision + recall).

OSI layers bottom-up: physical, data link, network, transport, session, presentation, application; TCP/IP collapses to link, internet, transport, application.

Encapsulation wraps data with headers at each layer: application data → TCP segment → IP packet → Ethernet frame → bits.

TCP provides connection setup, ordered reliable delivery, acknowledgments, retransmission, and flow control; UDP provides connectionless best-effort datagrams.

IPv4 addresses are 32 bits; IPv6 addresses are 128 bits; private IPv4 ranges are 10/8, 172.16/12, and 192.168/16.

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

Well-known ports: HTTP 80, HTTPS 443, DNS 53, SMTP 25, SSH 22, FTP 20/21.

A subnet mask or CIDR prefix defines network bits; /24 means 24 network bits and 8 host bits, giving 254 usable IPv4 host addresses.

Routers forward packets between networks using IP addresses; switches forward frames within a LAN using MAC addresses.

Bandwidth is maximum data rate; latency is delay; throughput is actual achieved rate; packet switching shares links statistically.

Moore's law observed transistor counts doubling roughly every two years, driving long-term gains in computing power and reductions in cost per operation.

Digital divide describes unequal access to devices, broadband, and digital literacy across income, geography, age, and disability groups.

Intellectual property types: copyright protects expressive works, patents protect inventions, trademarks protect brand identifiers, trade secrets protect confidential information.

Open-source licenses grant rights to use, study, modify, and redistribute code; permissive licenses such as MIT and Apache differ from copyleft licenses such as GPL in derivative licensing terms.

Automation shifts labor demand; it displaces some routine tasks while creating roles in system design, data analysis, maintenance, and oversight.

Universal design and assistive technology increase accessibility; examples include screen readers, captions, keyboard navigation, and high-contrast interfaces.

Filter bubbles and echo chambers can result from personalization algorithms that prioritize engagement, amplifying confirmation bias and misinformation.

Data centers consume significant electricity for computing and cooling; e-waste recycling recovers metals and reduces hazardous landfill contamination.

Net neutrality is the principle that ISPs treat all internet traffic equally, without blocking, throttling, or paid prioritization.

CIA triad: confidentiality prevents unauthorized disclosure, integrity prevents unauthorized modification, availability ensures timely access.

Authentication factors are knowledge (password), possession (token or phone), and inherence (biometric); MFA requires two or more independent factors.

Symmetric encryption uses one shared key such as AES; asymmetric encryption uses a public/private key pair such as RSA or ECC and supports key exchange and digital signatures.

Cryptographic hashes such as SHA-256 are one-way and collision-resistant; passwords are stored as salted hashes, never plaintext or reversible encryption.

Common attacks include phishing and social engineering, malware, SQL injection, cross-site scripting, man-in-the-middle, denial of service, and credential stuffing.

Defenses include least privilege, defense in depth, input validation, parameterized queries, patching, firewalls, TLS, and monitoring.

Digital signature: the signer hashes the message and encrypts the hash with a private key; anyone can verify with the public key.

Ethical frameworks: utilitarianism judges actions by overall consequences; deontology judges by duties and rules; virtue ethics focuses on character.

Responsible disclosure reports vulnerabilities to vendors before public release; privacy principles include data minimization, consent, and purpose limitation.