BCS Written Computer Science cheat sheet

Von Neumann architecture stores program instructions and data in the same memory, sharing one bus for fetch and execution cycles.

CPU time = instruction count × cycles per instruction × clock cycle time; clock rate = 1 / clock cycle time.

Speedup from pipelining is limited by the slowest pipeline stage; ideal speedup ≈ number of stages when balanced.

Memory hierarchy rule: registers < cache < main memory < secondary storage in speed, with inverse order in capacity and cost per bit.

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

Cache write-through updates main memory on every write; write-back defers until the block is evicted, using a dirty bit.

RISC favors fixed-length instructions and many registers; CISC favors variable-length, multi-cycle complex instructions.

Number systems: binary to hex groups 4 bits; two's complement range for n bits is −2^(n−1) to 2^(n−1) − 1.

Direct memory access (DMA) transfers blocks between I/O and memory without per-byte CPU involvement, raising an interrupt on completion.

Average access: array O(1) by index; balanced BST search O(log n); hash table O(1) average, O(n) worst case on collisions.

Stack is LIFO (push/pop); queue is FIFO (enqueue/dequeue); both give O(1) insertion and deletion at the operative end.

Sorting: bubble/insertion/selection O(n²); merge sort O(n log n) guaranteed with O(n) extra space; quicksort O(n log n) average, O(n²) worst.

Binary search requires a sorted array and runs in O(log n), halving the search interval each comparison.

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

Dijkstra's algorithm finds single-source shortest paths with non-negative weights in O((V+E) log V) using a min-heap.

Minimum spanning tree via Kruskal (sort edges, union-find) or Prim (grow from a vertex); both are greedy and O(E log V).

A hash function maps keys to buckets; load factor = n / m; open addressing and chaining are the two standard collision resolutions.

Big-O upper-bounds growth: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2^n).

Compilation translates source to machine code before execution; interpretation executes source statement by statement at run time.

Static typing checks types at compile time; dynamic typing checks at run time, trading early error detection for flexibility.

Pass by value copies the argument; pass by reference passes the address so callee modifications affect the caller's variable.

Scope rules: lexical (static) scoping resolves names by program text; dynamic scoping resolves by call order.

Object-oriented pillars: encapsulation, inheritance, polymorphism, and abstraction; overloading is compile-time, overriding is run-time.

Recursion needs a base case and a recursive case; each call consumes stack frames, risking stack overflow on deep recursion.

Garbage collection reclaims unreachable heap objects automatically; manual memory management uses malloc/free or new/delete.

Testing levels: unit (single component), integration (interfaces), system (end-to-end), acceptance (user requirements).

Version control records snapshots (commits); branching isolates work and merging reconciles divergent histories.

ACID: Atomicity (all-or-nothing), Consistency (valid state transitions), Isolation (concurrent transactions do not interfere), Durability (committed data survives failure).

Normalization: 1NF removes repeating groups; 2NF removes partial dependencies on a composite key; 3NF removes transitive dependencies; BCNF requires every determinant to be a candidate key.

SQL clauses execute logically in order FROM → WHERE → GROUP BY → HAVING → SELECT → ORDER BY; WHERE filters rows, HAVING filters groups.

Primary key uniquely identifies rows and cannot be null; a foreign key references a candidate key and enforces referential integrity.

INNER JOIN returns matching rows only; LEFT/RIGHT OUTER JOIN retains unmatched rows from one side with nulls.

A transaction schedule is serializable if it is equivalent to some serial order; locking (2PL) and timestamp ordering enforce this.

Indexes (commonly B+ trees) speed reads to O(log n) but add write cost and storage; full table scans are O(n).

A view is a stored query presenting a virtual table; it can restrict column access without duplicating data.

NoSQL families: key-value, document, column-family, and graph; they relax strict schemas and often favor BASE over ACID.

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

TCP is connection-oriented, reliable, and ordered (three-way handshake SYN, SYN-ACK, ACK); UDP is connectionless and best-effort.

IPv4 addresses are 32-bit; IPv6 are 128-bit. A /24 subnet has 256 addresses; usable hosts = 2^(32 − prefix) − 2.

Private IPv4 ranges: 10.0.0.0/8, 172.16.0.0/12, 192.168.0.0/16; NAT translates them to public addresses.

DNS resolves names to IP addresses; DHCP assigns addresses dynamically via DORA (Discover, Offer, Request, Acknowledge).

CSMA/CD detects collisions on shared Ethernet; CSMA/CA avoids them in wireless LANs using acknowledgements.

Routing: distance-vector (RIP, hop count, Bellman-Ford) versus link-state (OSPF, Dijkstra, full topology).

Bandwidth-delay product = link capacity × round-trip propagation delay; it bounds data in flight for full utilization.

Encryption layers: TLS secures application traffic; IPsec secures at the network layer; WPA2/WPA3 secure wireless links.

Process states: new, ready, running, waiting, terminated; the scheduler moves processes between ready and running.

Context switch saves one process's state (registers, program counter) and restores another's; it is pure overhead.

CPU scheduling: FCFS (convoy effect), SJF (optimal average wait, needs prediction), Round Robin (time quantum), priority (risk of starvation, fixed by aging).

Deadlock requires mutual exclusion, hold-and-wait, no preemption, and circular wait; breaking any one condition prevents it.

Banker's algorithm is deadlock avoidance; resource-allocation graphs detect cycles for deadlock detection.

Paging divides memory into fixed-size frames; segmentation uses variable-size logical segments; both use a page/segment table.

Thrashing occurs when excessive paging leaves too few frames per process; the working-set model bounds it.

Semaphores (P/wait and V/signal) and mutexes enforce mutual exclusion; monitors bundle locks with condition variables.

File allocation: contiguous (fast, fragmented), linked (no external fragmentation, slow random access), indexed (direct access via index block).

SDLC phases: requirements, design, implementation, testing, deployment, maintenance; maintenance consumes the largest share of lifetime cost.

Waterfall is sequential with frozen requirements; iterative/incremental and Agile deliver working software in short cycles.

Requirement types: functional (what the system does) versus non-functional (performance, security, usability, availability).

UML: use case (actors and goals), class (structure), sequence (message order over time), activity (workflow), state (object lifecycle).

DFD levels: context diagram (level 0, one process), level 1 decomposes processes; data stores and external entities are not decomposed.

Coupling should be low and cohesion high; modularity with information hiding reduces ripple effects of change.

Estimation: COCOMO relates effort to size in KLOC; function points measure size from inputs, outputs, queries, files, and interfaces.

Verification asks 'are we building the product right'; validation asks 'are we building the right product'.

Black-box testing uses equivalence partitioning and boundary value analysis; white-box testing uses statement, branch, and path coverage.

CIA triad: Confidentiality, Integrity, Availability; augmented by authentication, authorization, and non-repudiation.

Symmetric encryption (AES, DES) uses one shared key and is fast; asymmetric (RSA, ECC) uses key pairs and enables digital signatures.

Hashing (SHA-256) is one-way and collision-resistant; salting defeats precomputed rainbow tables for passwords.

Digital signature = hash of message encrypted with sender's private key; verified with the sender's public key.

PKI binds public keys to identities through certificates signed by a trusted certificate authority.

Attack classes: phishing (social engineering), DoS/DDoS (availability), MITM (interception), SQL injection (unsanitized input), malware (payload).

Defense in depth layers controls: firewalls, IDS/IPS, access control, encryption, patching, and user awareness.

Access control models: DAC (owner discretion), MAC (labels/clearances), RBAC (roles), ABAC (attributes).

Risk = likelihood × impact; controls are preventive, detective, or corrective, and residual risk remains after treatment.

Cloud service models: IaaS (virtual machines, storage), PaaS (runtime and deployment platform), SaaS (ready applications); deployment models are public, private, hybrid, community.

Cloud characteristics: on-demand self-service, broad network access, resource pooling, rapid elasticity, measured service.

Virtualization abstracts hardware so multiple VMs share a host; containers share the host OS kernel and are lighter than VMs.

Machine learning types: supervised (labelled data), unsupervised (clustering), reinforcement (reward-driven); deep learning uses multi-layer neural networks.

Blockchain is a distributed append-only ledger secured by cryptographic hashes and consensus (proof of work or stake); immutability makes tampering evident.

IoT combines sensors, actuators, connectivity, and analytics; constrained devices demand lightweight protocols such as MQTT and CoAP.

Big data is characterized by volume, velocity, variety, veracity, and value; MapReduce and Spark parallelize processing.

Edge and fog computing push computation near data sources to cut latency and bandwidth use versus centralized cloud.

Quantum computing uses qubits and superposition; Shor's algorithm threatens RSA, motivating post-quantum cryptography.

E-government stages: information publishing, interaction (forms and queries), transaction (full online service), and transformation (integrated services).

G2C serves citizens, G2B serves businesses, G2G serves inter-agency coordination, and G2E serves government employees.

Digital identity and authentication underpin online service delivery; single sign-on reduces credential sprawl across agencies.

Interoperability requires shared data standards, metadata, and APIs so agencies can exchange data without custom point-to-point links.

Open data publishing increases transparency and enables reuse; it requires anonymization to protect personal privacy.

National data centers and shared cloud infrastructure reduce duplication and cost through consolidation and economies of scale.

Digital divide: unequal access to ICT by geography, income, age, or literacy; universal access policies target it.

Data protection principles: lawful purpose, data minimization, accuracy, retention limits, security safeguards, and citizen access rights.

Public key infrastructure and digital certificates enable legally valid electronic signatures in government transactions.