CPN CPE Computer Engineering cheat sheet

CPU time = (Instruction count × CPI × clock cycle time); CPI = total cycles / instruction count.

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

Pipeline speedup is bounded by 1 + (stages − 1) × stall cycles per instruction when hazards exist.

Cache AMAT = hit time + miss rate × miss penalty; split caches reduce structural hazards between fetch and data access.

Write-through keeps memory coherent but costs bandwidth; write-back defers memory writes until eviction (dirty bit).

Direct-mapped address split: offset bits = log2(block size), index bits = log2(number of sets), remaining bits = tag.

RISC favors fixed-length instructions and load/store access; CISC favors variable-length, memory-operand instructions.

Little's law for memory-level parallelism: concurrency = latency × throughput; applies to outstanding cache misses.

Virtual memory translation: VPN indexes the page table, offset is copied unchanged; TLB caches recent PTE entries.

De Morgan: ¬(A·B) = ¬A + ¬B and ¬(A+B) = ¬A·¬B; apply to convert between AND/OR/NOT forms.

Karnaugh maps group 1s in powers of two (1, 2, 4, 8); overlapping groups are allowed and essential primes must be covered.

A D flip-flop samples D at the clock edge; setup and hold times bound the valid data window around that edge.

Maximum clock frequency is limited by t_clk ≥ t_cq + t_logic + t_setup + clock skew.

A 2-to-1 mux implements any 2-variable function; a 2^n-to-1 mux implements any n-variable function directly.

Mealy outputs depend on state and input; Moore outputs depend only on state, so Moore has no combinational output glitch path.

An n-bit ripple-carry adder has O(n) critical path; carry-lookahead reduces depth to O(log n) using generate/propagate.

Setup violation is fixed by shortening combinational logic or pipelining; hold violation is fixed by adding delay or buffers.

SR latch with NOR gates: S=1 sets, R=1 resets, S=R=1 is invalid; S=R=0 holds state.

Necessary conditions for deadlock: mutual exclusion, hold-and-wait, no preemption, circular wait; break any one to prevent it.

Banker's algorithm grants a request only if the resulting state remains safe (some completion order exists).

Round-robin with quantum q: average waiting time grows with q; too small q raises context-switch overhead.

Priority inversion occurs when a low-priority holder blocks a high-priority waiter; priority inheritance bounds the delay.

Thrashing happens when the working set exceeds physical frames; page-fault rate spikes and CPU utilization collapses.

Semaphore P (wait) decrements and blocks at zero; V (signal) increments and wakes a waiter; binary semaphore acts as a mutex.

Belady's anomaly: FIFO page replacement can fault more with more frames; LRU and optimal are stack algorithms and avoid it.

A context switch saves registers and PCB state; it is pure overhead with no useful user work performed.

Virtual address translation uses page tables; a TLB miss costs a page-table walk, a page fault costs disk I/O.

TCP three-way handshake: SYN, SYN-ACK, ACK; teardown uses FIN/ACK in each direction plus a TIME_WAIT state.

TCP congestion control: slow start doubles cwnd per RTT; congestion avoidance adds roughly one MSS per RTT (AIMD).

Stop-and-wait utilization = (frame time) / (frame time + 2 × propagation delay); sliding window fixes low utilization.

IPv4 header is 20 bytes minimum; fragmentation offset is in 8-byte units and the DF flag forbids fragmentation.

CIDR /n leaves 2^(32−n) addresses; usable hosts = 2^(32−n) − 2 for a standard subnet (network and broadcast reserved).

CSMA/CD detects collisions and backs off exponentially; CSMA/CA avoids collisions with ACKs and random backoff windows.

DNS resolves names via recursive resolvers querying authoritative servers; records include A, AAAA, CNAME, MX, and NS.

NAT rewrites source IP/port on egress and tracks a translation table so return traffic maps back to the internal host.

BGP is the inter-domain path-vector protocol; OSPF and RIP are intra-domain (link-state and distance-vector respectively).

SOLID: single responsibility, open/closed, Liskov substitution, interface segregation, dependency inversion.

Coupling measures interdependence between modules; cohesion measures relatedness within a module - minimize coupling, maximize cohesion.

Waterfall suits stable requirements; iterative/incremental and agile suit evolving requirements with frequent feedback.

Unit tests isolate one unit with test doubles; integration tests exercise real component boundaries.

Version control branching: a merge preserves history with two parents; a rebase replays commits and rewrites hashes.

Code review and static analysis catch defects earlier; cost to fix rises sharply the later a defect is found.

Continuous integration requires automated build plus test on every commit; continuous delivery keeps releases deployable.

Cyclomatic complexity V(G) = E − N + 2P; higher values indicate more independent paths and more test cases needed.

Refactoring changes internal structure without changing observable behavior; it must be backed by tests.

Average complexities: hash lookup O(1), balanced BST O(log n), sorted array search O(log n), unsorted linear search O(n).

Quicksort average O(n log n), worst O(n²) on already-sorted data with a poor pivot; median-of-three mitigates this.

Merge sort is stable and O(n log n) worst case but needs O(n) auxiliary space.

Heapsort is in-place O(n log n) but not stable; a binary heap supports O(log n) insert and extract-min.

BFS finds shortest paths in unweighted graphs; Dijkstra requires non-negative weights; Bellman-Ford handles negative edges.

Dynamic programming requires optimal substructure and overlapping subproblems; memoization caches top-down results.

A hash table degrades to O(n) when load factor approaches 1; open addressing and chaining are the two collision strategies.

Amortized analysis: a dynamic array doubling gives O(1) amortized append despite O(n) occasional copies.

Big-O upper bounds, Big-Omega lower bounds, Big-Theta tight bounds; drop constants and lower-order terms.

ACID: atomicity, consistency, isolation, durability; isolation levels trade consistency for concurrency.

Normalization: 1NF atomic values, 2NF no partial dependency on a composite key, 3NF no transitive dependency, BCNF every determinant is a candidate key.

An index speeds reads but slows writes; a covering index answers a query from the index alone without table access.

SQL join semantics: INNER keeps matches; LEFT keeps all left rows with NULLs where unmatched.

Transactions use locks or MVCC; two-phase locking guarantees serializability but can deadlock.

ACID isolation anomalies: dirty read, non-repeatable read, phantom read - each higher level removes one.

A B+ tree index keeps data in leaves and keys in internal nodes, giving O(log n) lookups and efficient range scans.

Primary key implies unique and not null; a foreign key enforces referential integrity to a referenced key.

CAP theorem: under a network partition a distributed store chooses consistency or availability, not both.

Symmetric ciphers (AES) are fast but need shared keys; asymmetric (RSA, ECC) solve key distribution but are slower.

AES block size is 128 bits; key sizes are 128, 192, or 256 bits; ECB mode leaks patterns and should not be used.

RSA security rests on integer factorization; ECC on the elliptic-curve discrete log; both are broken by large quantum computers.

Hashes (SHA-256) provide preimage resistance and collision resistance; they are not encryption and are not reversible.

HMAC gives message authentication using a shared key; a digital signature gives non-repudiation using a private key.

TLS combines asymmetric key exchange with symmetric session encryption and certificates for server authentication.

Salt defeats rainbow tables; a slow KDF (bcrypt, scrypt, Argon2) resists brute-force password guessing.

Nonce/IV reuse in stream or CTR mode breaks confidentiality by leaking the XOR of plaintexts.

Defense in depth layers controls; least privilege and input validation reduce the attack surface.

Hard real-time misses a deadline as a system failure; soft real-time degrades quality but tolerates occasional misses.

Rate-monotonic scheduling assigns higher priority to shorter periods; it is optimal for fixed-priority preemptive tasks.

EDF (earliest deadline first) is optimal for dynamic priorities and can reach 100% utilization on one processor.

Utilization bound for n rate-monotonic tasks: U ≤ n(2^(1/n) − 1), approaching ln 2 ≈ 0.693 as n grows.

Worst-case execution time (WCET) plus blocking and interrupt time determines schedulability, not average time.

Interrupt latency plus context-switch time bounds the response time of an event-driven embedded system.

Watchdog timers reset a hung system; they must be serviced only by a healthy path, not blindly in a loop.

Memory-mapped I/O uses volatile pointers; the compiler must not cache or reorder device register accesses.

RTOS priority inheritance prevents unbounded priority inversion when a low-priority task holds a shared mutex.

Requirements must be verifiable: state measurable criteria rather than vague adjectives such as fast or user-friendly.

Design reviews and peer inspection catch defects before test; inspection is among the cheapest defect-removal methods.

Trade-off analysis documents alternatives, criteria, and rationale; it is the core artifact of engineering judgment.

Configuration management tracks versions, baselines, and change control so any released build is reproducible.

A hazard analysis (e.g., FMEA) ranks risk by severity × occurrence × detection and drives mitigation priority.

Prototyping reduces uncertainty early; a throwaway prototype should not be shipped as production code.

Technical debt is a deliberate or accidental shortcut; it accrues interest as future changes get harder.

Test coverage measures executed code, not correctness; high coverage with weak assertions still misses defects.

Documentation of interfaces and assumptions is part of the deliverable, not an optional extra.

Core professional obligations: public safety and welfare first, competence, honesty, confidentiality, and avoiding conflicts of interest.

Whistleblowing is justified when a serious harm is imminent, internal channels fail, and the disclosure is proportionate.

Conflicts of interest must be disclosed and, where possible, avoided rather than merely managed silently.

Competence boundary: accept only work within your expertise or with adequate supervision and disclosure.

Confidentiality obligations persist after employment ends; trade secrets and personal data remain protected.

Data privacy principles: collect only what is needed, state the purpose, limit retention, and secure the data.

Bribery and kickbacks are prohibited even when customary in a market; gifts must be nominal and disclosed.

Falsifying test results or safety data is a serious breach; report accurate findings even when unfavorable.

Give credit for others' work; plagiarism and misattributed authorship violate professional and academic norms.