A-Level Computer Science (GCE Cameroon)

Cheatsheet Content

1. Data Representation 1.1 Number Systems Binary (Base 2): Digits 0, 1. Used by computers. Octal (Base 8): Digits 0-7. Each octal digit represents 3 binary digits. Decimal (Base 10): Digits 0-9. Human-readable. Hexadecimal (Base 16): Digits 0-9, A-F. Each hex digit represents 4 binary digits. Conversions: Binary to Decimal: $\sum (b_i \times 2^i)$ Decimal to Binary: Repeated division by 2, taking remainders. Binary to Hex/Octal: Group bits (4 for Hex, 3 for Octal) and convert each group. Hex/Octal to Binary: Convert each digit to its binary equivalent. 1.2 Signed Integers Sign-Magnitude: Leftmost bit is sign (0 for +, 1 for -), rest is magnitude. Range for $n$ bits: $-(2^{n-1}-1)$ to $(2^{n-1}-1)$ Two representations for zero (+0, -0). One's Complement: Invert all bits for negative numbers. Range for $n$ bits: $-(2^{n-1}-1)$ to $(2^{n-1}-1)$ Two representations for zero (+0, -0). End-around carry in addition. Two's Complement: Invert all bits and add 1 for negative numbers. Most common. Range for $n$ bits: $-2^{n-1}$ to $(2^{n-1}-1)$ Unique representation for zero. Simplifies arithmetic. 1.3 Floating Point Numbers (IEEE 754) Represents real numbers. Format: Sign bit (S), Exponent (E), Mantissa (M). Value: $(-1)^S \times M \times 2^{E'}$ Normalized Mantissa: Always starts with '1.' (implicit 1). Biased Exponent: Stored exponent is $E + \text{bias}$. (e.g., bias 127 for single precision) Single Precision (32-bit): 1 S-bit, 8 E-bits, 23 M-bits. Double Precision (64-bit): 1 S-bit, 11 E-bits, 52 M-bits. Errors: Rounding error, Overflow, Underflow. 1.4 Character Representation ASCII: 7-bit code, 128 characters. Basic English alphabet, numbers, symbols. Extended ASCII: 8-bit code, 256 characters. Includes some foreign characters. Unicode: Universal character encoding. Supports characters from all languages. (e.g., UTF-8, UTF-16). 1.5 Images and Sound Images: Bitmap: Pixel-based. Resolution (width x height), Color depth (bits per pixel). File size: Resolution $\times$ Color Depth (bits). Vector: Object-based (lines, curves, shapes). Scalable without loss of quality. Sound: Sampling Rate: Number of samples per second (Hz). Higher rate = better quality. Bit Depth: Number of bits per sample. Higher depth = better dynamic range. File size: Sampling Rate $\times$ Bit Depth $\times$ Duration (seconds) $\times$ Channels. 2. Logic Gates and Boolean Algebra 2.1 Basic Gates AND: $A \cdot B$ (Output is 1 if ALL inputs are 1) OR: $A + B$ (Output is 1 if ANY input is 1) NOT: $\bar{A}$ (Inverts input) XOR: $A \oplus B$ (Output is 1 if inputs are DIFFERENT) NAND: $\overline{A \cdot B}$ (NOT AND) NOR: $\overline{A + B}$ (NOT OR) XNOR: $\overline{A \oplus B}$ (NOT XOR) 2.2 Boolean Algebra Laws Commutative: $A+B = B+A$, $A \cdot B = B \cdot A$ Associative: $(A+B)+C = A+(B+C)$, $(A \cdot B) \cdot C = A \cdot (B \cdot C)$ Distributive: $A \cdot (B+C) = A \cdot B + A \cdot C$, $A + (B \cdot C) = (A+B) \cdot (A+C)$ Identity: $A+0=A$, $A \cdot 1=A$ Null/Annihilation: $A+1=1$, $A \cdot 0=0$ Complement: $A+\bar{A}=1$, $A \cdot \bar{A}=0$ Idempotent: $A+A=A$, $A \cdot A=A$ Absorption: $A+(A \cdot B)=A$, $A \cdot (A+B)=A$ De Morgan's Laws: $\overline{A+B} = \bar{A} \cdot \bar{B}$, $\overline{A \cdot B} = \bar{A} + \bar{B}$ 2.3 Logic Circuits Truth Tables: Map all possible input combinations to outputs. Karnaugh Maps (K-Maps): Graphical method to simplify Boolean expressions. Group adjacent 1s in powers of 2 (1, 2, 4, 8...). Groups can wrap around edges. Aim for largest possible groups to eliminate variables. Combinational Circuits: Output depends only on current inputs (e.g., Half/Full Adders, Decoders, Multiplexers). Sequential Circuits: Output depends on current inputs AND past inputs/state (e.g., Flip-Flops, Registers, Counters). 3. Computer Architecture 3.1 Von Neumann Architecture Single address space for instructions and data. Fetch-Decode-Execute cycle. Components: CPU (ALU, Control Unit, Registers), Memory, I/O. Bottleneck: Shared bus for data and instructions can limit performance. 3.2 Harvard Architecture Separate memory and buses for instructions and data. Allows simultaneous fetching of instructions and data. Faster execution, common in embedded systems and DSPs. 3.3 CPU Components Arithmetic Logic Unit (ALU): Performs arithmetic and logical operations. Control Unit (CU): Manages and coordinates all components. Fetches, decodes, executes instructions. Registers: Small, fast storage within the CPU. Program Counter (PC): Stores address of next instruction. Memory Address Register (MAR): Stores address for read/write to memory. Memory Data Register (MDR): Stores data read from/written to memory. Instruction Register (IR): Stores the current instruction being executed. Accumulator (ACC): Stores results of ALU operations. General Purpose Registers: For temporary data storage. Buses: Data Bus: Carries data between CPU and memory/I/O. Address Bus: Carries memory addresses from CPU to memory/I/O. Control Bus: Carries control signals (read/write, clock, interrupt). 3.4 Fetch-Decode-Execute Cycle Fetch: PC content loaded into MAR. Instruction at MAR address loaded into MDR, then into IR. PC incremented. Decode: CU interprets the instruction in IR. Execute: CU sends signals to other components to carry out the instruction. Data processed by ALU, results stored. 3.5 Instruction Set Architecture (ISA) RISC (Reduced Instruction Set Computer): Few, simple, fixed-length instructions. Execute in one clock cycle. More general-purpose registers. Load/Store architecture (only load/store instructions access memory). CISC (Complex Instruction Set Computer): Many, complex, variable-length instructions. Instructions can take multiple clock cycles. Less general-purpose registers. Instructions can directly manipulate memory. 3.6 Pipelining Overlapping execution of multiple instructions. While one instruction is executing, the next is being decoded, and another is being fetched. Increases CPU throughput, not individual instruction speed. 3.7 Interrupts Signal to the CPU indicating an event needs immediate attention. Can be hardware (I/O completion, timer) or software (system call, error). CPU saves current state, executes Interrupt Service Routine (ISR), then restores state and resumes. 4. Memory Hierarchy Registers: Fastest, smallest, in CPU. Cache Memory (L1, L2, L3): Faster than main memory, stores frequently accessed data for CPU. Main Memory (RAM): Volatile, stores programs and data currently in use. Secondary Storage (HDD, SSD): Non-volatile, stores data persistently. Slower, larger capacity. Virtual Memory: Uses secondary storage as an extension of RAM. Allows running programs larger than physical RAM. 5. Operating Systems 5.1 Functions Resource Management: CPU scheduling, memory management, I/O device management. Process Management: Creation, termination, scheduling, synchronization of processes. Memory Management: Allocating and deallocating memory to processes, virtual memory. File Management: Organizing, storing, retrieving files. Access control. User Interface: CLI (Command Line Interface) or GUI (Graphical User Interface). Security: User authentication, access control. 5.2 Process Management Process: An instance of a program in execution. States: New, Ready, Running, Waiting (Blocked), Terminated. Scheduling: Deciding which process to run next. Preemptive: OS can interrupt a running process. Non-preemptive: Process runs until completion or voluntarily yields CPU. Algorithms: FCFS (First-Come, First-Served), SJF (Shortest Job First), Priority, Round Robin. 5.3 Memory Management Paging: Divides physical memory into fixed-size blocks (frames) and logical memory into same-size blocks (pages). Segmentation: Divides logical memory into variable-size blocks (segments) based on program structure. Virtual Memory: Uses paging/segmentation to map virtual addresses to physical addresses. Paging File/Swap Space: Area on disk used to store pages swapped out of RAM. Page Fault: Occurs when a process tries to access a page not currently in physical memory. 6. Networking 6.1 Network Topologies Bus: All devices share a single cable. Simple, cheap, but collision-prone and single point of failure. Star: All devices connect to a central hub/switch. Reliable, easy to add devices, but central device is single point of failure. Ring: Devices connected in a closed loop. Data travels in one direction. Token passing to avoid collisions. Mesh: Every device connected to every other device. Highly redundant, fault-tolerant, but expensive. Hybrid: Combination of two or more topologies. 6.2 Network Hardware NIC (Network Interface Card): Connects a computer to a network. Hub: Broadcasts all incoming data to all connected devices. (Layer 1) Switch: Learns MAC addresses and forwards data only to the intended recipient. (Layer 2) Router: Connects different networks, forwards packets based on IP addresses. (Layer 3) Modem: Modulates/demodulates signals for transmission over telephone lines/cable. Repeater: Boosts signals over long distances. Bridge: Connects two LAN segments, filters traffic based on MAC addresses. 6.3 Network Types LAN (Local Area Network): Covers a small geographical area (home, office). WAN (Wide Area Network): Covers a large geographical area (cities, countries), often uses public infrastructure. MAN (Metropolitan Area Network): Covers a city or large campus. PAN (Personal Area Network): Smallest network (Bluetooth, USB). 6.4 OSI Model (Open Systems Interconnection) Application Layer (7): Provides network services to applications (HTTP, FTP, SMTP). Presentation Layer (6): Data formatting, encryption, compression. Session Layer (5): Manages communication sessions, establishes, maintains, terminates connections. Transport Layer (4): End-to-end communication, reliability (TCP), flow control, segmentation. Network Layer (3): Logical addressing (IP), routing packets between networks. Data Link Layer (2): Physical addressing (MAC), error detection/correction, frame synchronization. Physical Layer (1): Physical transmission of bits over media (cables, Wi-Fi). 6.5 TCP/IP Model Application Layer: (OSI 5,6,7) HTTP, FTP, DNS, SMTP. Transport Layer: (OSI 4) TCP (reliable, connection-oriented), UDP (unreliable, connectionless). Internet Layer: (OSI 3) IP (Internet Protocol) for addressing and routing. Network Access Layer: (OSI 1,2) Ethernet, Wi-Fi. 6.6 IP Addressing IPv4: 32-bit address, dotted decimal format (e.g., 192.168.1.1). Classes: A, B, C, D, E (multicast/experimental). Subnet Mask: Divides IP into network and host portions. CIDR (Classless Inter-Domain Routing): Uses `/prefix` notation. IPv6: 128-bit address, hexadecimal format (e.g., 2001:0db8:85a3:0000:0000:8a2e:0370:7334). DHCP (Dynamic Host Configuration Protocol): Automatically assigns IP addresses. DNS (Domain Name System): Translates domain names to IP addresses. 6.7 Network Security Firewall: Filters network traffic based on rules. Encryption: Converts data into a coded form to prevent unauthorized access. Authentication: Verifies identity (passwords, biometrics). Access Control: Restricts who can access what resources. Malware: Viruses, Worms, Trojan Horses, Spyware, Ransomware. Attacks: DoS (Denial of Service), Phishing, Brute Force, Man-in-the-Middle. 7. Programming Concepts 7.1 Programming Paradigms Procedural: Sequence of instructions, uses procedures/functions. (e.g., C, Pascal) Object-Oriented (OOP): Uses objects and classes. (e.g., Java, Python, C++) Encapsulation: Bundling data and methods that operate on the data within a single unit (class). Inheritance: A class can inherit properties and methods from another class. Polymorphism: Objects of different classes can be treated as objects of a common type. Abstraction: Hiding complex implementation details and showing only essential features. Declarative: Focuses on *what* to do, not *how*. (e.g., SQL, Prolog, Haskell) 7.2 Data Structures Arrays: Fixed-size collection of elements of the same data type, stored in contiguous memory. Linked Lists: Collection of nodes, each containing data and a pointer to the next node. Dynamic size. Singly, Doubly, Circular. Stacks: LIFO (Last In, First Out). Operations: Push, Pop, Peek. Queues: FIFO (First In, First Out). Operations: Enqueue, Dequeue, Peek. Trees: Hierarchical structure. Root, nodes, leaves, branches. Binary Tree: Each node has at most two children. Binary Search Tree (BST): Left child Graphs: Collection of vertices (nodes) and edges (connections). Directed/Undirected, Weighted/Unweighted. Hash Tables: Maps keys to values using a hash function. Fast average-case lookups. 7.3 Algorithms Sorting: Arranging elements in a specific order. Bubble Sort: Repeatedly steps through list, compares adjacent elements and swaps if in wrong order. $O(n^2)$. Insertion Sort: Builds final sorted array one item at a time. $O(n^2)$. Merge Sort: Divide and conquer. Divides list into halves, sorts them, then merges. $O(n \log n)$. Quick Sort: Divide and conquer. Picks an element as pivot and partitions array around pivot. $O(n \log n)$ average. Searching: Finding a specific element. Linear Search: Checks each element sequentially. $O(n)$. Binary Search: Requires sorted data. Repeatedly divides search interval in half. $O(\log n)$. Graph Traversal: BFS (Breadth-First Search): Explores layer by layer. Uses a queue. DFS (Depth-First Search): Explores as far as possible along each branch before backtracking. Uses a stack. 7.4 Program Development Life Cycle Problem Definition: Understand requirements. Analysis: Detailed study of requirements, inputs, outputs, processes. Design: Algorithm development (flowcharts, pseudocode), data structures. Coding: Writing the program in a chosen language. Testing: Debugging, unit testing, integration testing, system testing, acceptance testing. Implementation: Deployment and installation. Maintenance: Bug fixing, updates, enhancements. 7.5 Software Testing White Box Testing: Tests internal structure/code. (e.g., path coverage, statement coverage). Black Box Testing: Tests functionality without knowing internal structure. (e.g., boundary value analysis, equivalence partitioning). Alpha Testing: Done by internal staff before release. Beta Testing: Done by external users in a real environment. 8. Databases 8.1 Database Concepts DBMS (Database Management System): Software for creating, managing, and querying databases. Relational Database: Data stored in tables (relations) with rows (records) and columns (fields/attributes). Primary Key: Uniquely identifies each record in a table. Foreign Key: A field in one table that refers to the primary key in another table, establishing a relationship. Normalization: Organizing database to reduce data redundancy and improve data integrity. 1NF (First Normal Form): No repeating groups, atomic values. 2NF (Second Normal Form): 1NF + no partial dependencies. 3NF (Third Normal Form): 2NF + no transitive dependencies. 8.2 SQL (Structured Query Language) DDL (Data Definition Language): CREATE TABLE table_name (column_name DATATYPE PRIMARY KEY, ...); ALTER TABLE table_name ADD column_name DATATYPE; DROP TABLE table_name; DML (Data Manipulation Language): INSERT INTO table_name (col1, col2) VALUES (val1, val2); SELECT col1, col2 FROM table_name WHERE condition ORDER BY col1; UPDATE table_name SET col1 = val1 WHERE condition; DELETE FROM table_name WHERE condition; Joins: Combine rows from two or more tables based on a related column. INNER JOIN , LEFT JOIN , RIGHT JOIN , FULL JOIN .