NYSTCE Computer Science cheat sheet

Big-O growth order (best to worst): O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(n^3) < O(2^n) < O(n!).

Binary search runs in O(log n) but requires the array to be sorted first; linear search is O(n) on unsorted data.

Stack is LIFO (push/pop at top); queue is FIFO (enqueue at rear, dequeue at front); a priority queue removes the highest-priority item first.

Hash table average lookup is O(1); worst case degrades to O(n) when many keys collide in one bucket.

Balanced binary search trees (AVL, red-black) guarantee O(log n) insert, delete, and search; an unbalanced BST can degrade to O(n).

Breadth-first search uses a queue and finds shortest paths in unweighted graphs; depth-first search uses a stack or recursion and detects cycles.

Dijkstra's algorithm finds single-source shortest paths with non-negative edge weights in O(E log V) with a binary heap; it fails on negative edges.

Recursion needs a base case to terminate; each call adds a frame to the call stack, so deep recursion risks stack overflow.

Value types (int, char, boolean) store data directly; reference types (objects, arrays) store an address to heap data, so assignment copies the reference.

Pass-by-value is the default in Java and C: the callee receives a copy, so reassigning a parameter does not affect the caller's variable.

Scope rules: a local variable shadows a same-named field; block scope ends at the closing brace; static members belong to the class, not an instance.

Loop equivalence: any for loop can be rewritten as a while loop with initialization before and update inside the body.

Short-circuit evaluation: in A && B, B is evaluated only if A is true; in A || B, B is evaluated only if A is false.

Integer division truncates toward zero (7/2 == 3); the modulo operator returns the remainder and is negative when the dividend is negative in Java/C.

Compile-time errors (syntax, type mismatch) prevent execution; run-time errors (divide by zero, null dereference) occur during execution; logic errors produce wrong output.

Unit tests isolate one method; integration tests combine components; a regression test is added after a bug fix to prevent recurrence.

n bits represent 2^n distinct values; unsigned range is 0 to 2^n - 1; two's complement signed range is -2^(n-1) to 2^(n-1) - 1.

Two's complement negation: invert all bits and add 1; the most significant bit carries weight -2^(n-1).

Hexadecimal digit = 4 bits, octal digit = 3 bits; convert binary to hex by grouping bits from the right.

ASCII is 7-bit (128 codes); Unicode assigns code points and UTF-8 encodes them in 1-4 bytes, backward-compatible with ASCII.

CPU fetch-decode-execute cycle: fetch instruction at the program counter, decode opcode, execute, write back, increment PC.

Von Neumann architecture shares one memory for instructions and data; Harvard architecture uses separate instruction and data memories.

Memory hierarchy by speed and cost: registers > cache (L1/L2/L3) > RAM > SSD/disk > tape; cache exploits temporal and spatial locality.

Boolean identities: De Morgan's laws, A + A' = 1, A·A' = 0, A + AB = A; a half adder computes sum = A XOR B and carry = A AND B.

OSI layers bottom-up: Physical, Data Link, Network, Transport, Session, Presentation, Application; TCP/IP collapses these to Link, Internet, Transport, Application.

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

IPv4 addresses are 32 bits; IPv6 addresses are 128 bits; a /24 subnet mask leaves 8 host bits, allowing 254 usable hosts.

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

HTTP is stateless and typically runs over TCP port 80; HTTPS adds TLS on port 443 for confidentiality and integrity.

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

Hashing (SHA-256) is one-way and verifies integrity; a cryptographic hash is not encryption because it cannot be reversed.

Common attacks: phishing (social engineering), SQL injection (unvalidated input), DDoS (flooding), man-in-the-middle (interception); mitigations include input validation, firewalls, and TLS.

Digital divide refers to unequal access to computing devices, broadband, and digital literacy across socioeconomic groups.

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

FERPA protects student education records; COPPA restricts collecting data from children under 13; HIPAA governs health information.

Open source licenses: MIT/BSD are permissive; GPL is copyleft and requires derivative works to remain open source.

Intellectual property categories: copyright (expression), patent (inventions, limited term), trademark (brand identifiers), trade secret (confidential know-how).

Algorithmic bias arises when training data or model design encodes historical inequities, producing unfair outcomes for groups.

Creative Commons licenses let creators grant reuse rights with attribution and optional share-alike or non-commercial conditions.

Accessibility standards (WCAG) require perceivable, operable, understandable, and robust interfaces, such as alt text and keyboard navigation.