Computer Science A/L Study Notes

Introduction to Computer Science Notes

Welcome to the comprehensive study notes for GCE A/L Computer Science. These notes are structured to strictly follow the Cameroon GCE syllabus (Code 795), covering everything from the Von Neumann architecture and Boolean logic to relational databases and algorithmic complexity.

1. Computer Organisation

This section explores the physical components, logical operations, and architectural models that form the foundation of modern computing systems.

1.1 Hardware & Processor Architectures

Computer hardware is categorized by how it processes instructions and data streams, as well as the complexity of the instructions it can execute.

• CISC vs. RISC:
  • CISC (Complex Instruction Set Computer): Large set of complex instructions, variable instruction length, relies heavily on hardware. Takes fewer lines of code to execute tasks.
  • RISC (Reduced Instruction Set Computer): Small set of highly optimized instructions, fixed length, relies heavily on software/compilers. Usually executes one instruction per clock cycle (pipelining).
• Flynn's Taxonomy: Classifies architectures based on concurrent instruction and data streams:
  • SISD (Single Instruction, Single Data): Traditional uniprocessor machines (Von Neumann).
  • SIMD (Single Instruction, Multiple Data): Used in GPUs for vector processing and graphics.
  • MIMD (Multiple Instruction, Multiple Data): Multi-core processors where each core executes different instructions on different data.
• Storage Devices: RAM (Volatile, working memory), ROM (Non-volatile, stores BIOS/firmware), Cache (SRAM, extremely fast memory built into the CPU), and secondary storage (HDD, SSD, Optical).

1.2 Digital Arithmetic & Boolean Logic

At the lowest level, computers operate using binary logic. Understanding how data is represented and manipulated using logic gates is crucial.

// Two's Complement (Used for negative numbers in subtraction)
Example: Represent -5 in 8-bit binary
1. Find positive 5:   0000 0101
2. Invert all bits:   1111 1010  (One's Complement)
3. Add 1:             1111 1011  (Two's Complement)
            

• Logic Gates: The building blocks of digital circuits.
  • AND: Output is 1 only if ALL inputs are 1. ($A \cdot B$)
  • OR: Output is 1 if AT LEAST ONE input is 1. ($A + B$)
  • XOR (Exclusive OR): Output is 1 if inputs are DIFFERENT. ($A \oplus B$)
  • NAND / NOR: Universal gates. The inverted outputs of AND and OR.
• De Morgan's Laws: Used to simplify complex Boolean expressions.
  • $\overline{A \cdot B} = \overline{A} + \overline{B}$ (The complement of a product is the sum of the complements).
  • $\overline{A + B} = \overline{A} \cdot \overline{B}$ (The complement of a sum is the product of the complements).
• Combinational Logic:
  • Half Adder: Adds two single-bit numbers. Outputs a Sum and a Carry.
  • Full Adder: Adds three bits (two significant bits and a carry-in from a previous addition).

1.3 The Von Neumann Architecture

The Von Neumann model is based on the stored-program concept, where both instruction data and program data are stored in the same unified memory space and are fetched sequentially by the CPU.

• CPU Registers: Small, ultra-fast memory locations inside the processor.
  • Program Counter (PC): Holds the memory address of the NEXT instruction to be fetched.
  • Memory Address Register (MAR): Holds the address of the current instruction/data being fetched from or written to memory.
  • Memory Data Register (MDR): Temporarily holds the actual data/instruction fetched from memory.
  • Current Instruction Register (CIR): Holds the instruction currently being decoded and executed.
  • Accumulator (ACC): Stores the intermediate results of ALU calculations.

2. System Software

System software is the foundational programming that manages computer hardware and provides a stable platform for running application software. The most critical component of this is the Operating System (OS).

2.1 Operating System Concepts & Evolution

An Operating System acts as an intermediary between the user, application software, and the computer hardware. Its primary goals are convenience (providing a user interface) and efficiency (resource management).

• Evolution & Types of OS:
  • Batch Processing: Jobs with similar needs are grouped and executed sequentially without human interaction.
  • Multiprogramming: Keeps multiple jobs in memory; when one job pauses to wait for I/O (like reading a disk), the CPU switches to another job, maximizing CPU utilization.
  • Time-Sharing (Multitasking): The CPU switches between multiple users/tasks so rapidly that it creates the illusion of simultaneous execution for everyone.
  • Real-Time OS (RTOS): Processing must occur within strict, rigid time constraints to prevent system failure (e.g., flight control systems, medical life-support).
  • Distributed OS: Manages a group of independent, networked computers and makes them appear to the user as a single, powerful system.
• User Interfaces: Command Line Interfaces (CLI) require typing text commands (e.g., MS-DOS, Linux Terminal), whereas Graphical User Interfaces (GUI) use visual elements like windows, icons, menus, and pointers (WIMP).

2.2 Language Translators & System Utilities

Processors only execute machine code (binary). Language translators are required to convert human-readable source code into executable instructions.

• Compilers: Translate the entire high-level source code into an executable object file all at once before execution. This results in faster execution times, but errors are only reported after the entire compilation process.
• Interpreters: Translate and execute the source code line-by-line. This is slower during execution, but much easier to debug because the program halts at the exact line an error occurs.
• Assemblers: Convert low-level assembly language (which uses mnemonics like ADD, SUB, MOV) into machine code.
• Linkers & Loaders:
  • Linker: Combines multiple compiled object files and system library files into a single, complete executable program.
  • Loader: Copies the executable program from secondary storage (the hard drive) into main memory (RAM) so the CPU can begin execution.

2.3 Resource Management & Process Scheduling

The OS must efficiently and fairly allocate the CPU, memory, and I/O devices among competing processes.

• CPU Scheduling Algorithms: The logic used by the OS to decide which process in the 'Ready' queue gets the CPU next.
  • First Come First Serve (FCFS): Non-preemptive. A simple FIFO queue. Can cause the "convoy effect" where short processes get stuck waiting behind one massive process.
  • Shortest Job First (SJF): Non-preemptive. Selects the process with the smallest execution time. Mathematically optimal for minimizing average waiting time, but it's hard to predict exact job lengths in reality.
  • Round Robin (RR): Preemptive. Each process gets a small, fixed unit of CPU time (a time quantum). If it doesn't finish in that time, it is paused and moved to the back of the queue. Highly responsive for time-sharing systems.
  • Shortest Remaining Time (SRT): The preemptive version of SJF. If a new process arrives that is shorter than the remaining time of the currently running process, the OS will interrupt the current process to run the new one.
• Memory Management:
  • Paging: Divides physical memory into fixed-size blocks (frames) and logical memory into identical-sized blocks (pages) to eliminate external fragmentation.
  • Virtual Memory: Uses a designated portion of the hard drive as an extension of RAM. The OS swaps pages in and out of main memory as needed. If the system spends more time swapping pages than executing instructions, it leads to a severe performance collapse known as thrashing.

3. Communication & Information Systems

This section bridges the gap between organizational data management and the physical networks used to transmit that data across the globe.

3.1 Information Systems & System Design

An Information System (IS) is a collection of hardware, software, data, people, and procedures that work together to produce quality information for organizational decision-making.

• The System Development Life Cycle (SDLC): The formal process of developing an information system.
  • 1. Feasibility Study: Assessing if the project is technically, economically, and legally viable.
  • 2. Analysis: Identifying the exact needs of the organization and the flaws in the current system.
  • 3. Design: Planning the new system's hardware, software, and user interfaces.
  • 4. Implementation: Coding and constructing the system.
  • 5. Testing & Maintenance: Verifying the system works using normal, extreme, and erroneous data, followed by ongoing updates.
• System Modelling Tools:
  • Data Flow Diagrams (DFD): A visual representation of how data moves through a system, showing inputs, processes, data stores, and outputs.
  • Flowcharts: A graphical representation of the sequence of operations or algorithms within the system.
• Changeover Strategies: How an organization transitions to a new system (Direct, Parallel, Phased, or Pilot running).

3.2 Computer Networks & Data Communication

A computer network is a collection of interconnected computing devices that share resources and data.

• Network Topologies: The physical or logical layout of a network.
  • Star Topology: All nodes connect to a central hub or switch. If one cable fails, only that node goes down. If the central switch fails, the whole network crashes.
  • Bus Topology: All nodes share a single central backbone cable. Data collisions are common, and a break in the main cable takes down the entire network.
  • Ring Topology: Nodes form a closed loop. Data travels in one direction, preventing collisions, but a broken node breaks the ring.
• Transmission Media:
  • Twisted Pair (Copper): Cheap, flexible, but susceptible to electromagnetic interference (EMI). Used for short-distance LANs.
  • Coaxial Cable: Better shielding against EMI, used for cable television and older networks.
  • Fiber Optics (Glass/Plastic): Transmits data as pulses of light using total internal reflection. Extremely high bandwidth, completely immune to EMI, and used for long-distance WAN backbones, but expensive and fragile.
• Network Hardware:
  • Switch: Intelligently forwards data packets only to the specific device that needs them within a LAN (uses MAC addresses).
  • Router: Connects different networks together (e.g., your LAN to the WAN/Internet) and directs data packets using IP addresses.
  • Modem: Converts digital signals from a computer into analog signals for telephone/cable lines, and vice versa (Modulation/Demodulation).
  • Gateway: Connects two completely different networks that use entirely different protocols.
• Security & Threats: Protecting the network from unauthorized access using Firewalls, Encryption, and User Access Rights (Passwords/Biometrics), and defending against malware (Viruses, Worms, Trojans).

4. Database Design & Modelling

A database is an organized, structured collection of related data. This section covers the transition from traditional flat-file systems to modern relational databases, emphasizing data integrity, modeling, and efficient retrieval.

4.1 Basic Concepts & ER Modelling

Traditional flat-file systems suffer from data redundancy (duplication) and data inconsistency. A Relational Database Management System (RDBMS) solves this by separating data into distinct tables linked by defined relationships.

• Entity-Relationship (ER) Modelling: A graphical way to design a database structure.
  • Entity: A real-world object or concept about which data is stored (e.g., STUDENT, COURSE). It becomes a table in the database.
  • Attribute: A property or characteristic of an entity (e.g., Name, Age). It becomes a column.
• Database Keys:
  • Primary Key (PK): A unique identifier for every record in a table (e.g., StudentID).
  • Foreign Key (FK): A primary key from one table placed into another table to create a relationship. This enforces referential integrity.
  • Composite Key: A primary key made of two or more attributes combined to create a unique identifier.
• Relationships & Cardinality: How entities interact. They can be One-to-One (1:1), One-to-Many (1:M), or Many-to-Many (M:M). Note that M:M relationships cannot be implemented directly in an RDBMS and must be resolved using a junction/bridge table.

4.2 Database Normalization

Normalization is the step-by-step mathematical process of organizing data to reduce redundancy and eliminate insertion, update, and deletion anomalies.

4.3 Structured Query Language (SQL)

SQL is the standard language used to communicate with an RDBMS (such as MySQL, MS Access, or Oracle). It is divided into sub-languages based on functionality.

• Data Definition Language (DDL): Used to define the database structure (e.g., CREATE TABLE, ALTER, DROP).
• Data Manipulation Language (DML): Used to manipulate the actual data inside the tables (e.g., INSERT, UPDATE, DELETE, SELECT).

-- DDL Example: Creating a Table
CREATE TABLE Students (
    StudentID INT PRIMARY KEY,
    Name VARCHAR(50),
    DOB DATE
);

-- DML Example: Inserting and Querying Data
INSERT INTO Students (StudentID, Name, DOB) 
VALUES (101, 'Mohammadu', '2005-09-05');

SELECT Name FROM Students 
WHERE StudentID = 101;
            

5. Algorithms & Programming

This section transitions from the hardware and system management into the logic of problem-solving. An algorithm is a finite sequence of unambiguous instructions to solve a problem, which is then translated into a programming language.

5.1 Data Representation & Structures

Before processing data, we must understand how it is organized and stored in memory. The fundamental unit of data is the bit (0 or 1). 8 bits make a byte, and the processor's architecture determines the word size (e.g., 32-bit or 64-bit words).

• Standard Data Types:
  • Integer: Whole numbers without a fractional part.
  • Real / Float: Numbers with fractional parts. Represented in memory using a Sign, Mantissa, and Exponent. Note that floating-point arithmetic can sometimes lead to precision errors (rounding errors).
  • Boolean: True or False values.
  • Character & String: Text data, typically encoded using ASCII or Unicode.
• Complex Data Structures:
  • Arrays: A static, ordered collection of items of the same data type, stored in contiguous memory locations. Accessible via an index.
  • Records (Structs): A collection of related data items (fields) that can be of different data types, grouped under a single name (e.g., a Student record containing an Integer ID and a String Name).
  • Files: Used for persistent data storage on secondary devices, grouped into records and fields.

5.2 Algorithm Design & Recursion

Effective algorithms use a top-down design (stepwise refinement), breaking a large, complex problem down into smaller, manageable sub-problems or modules.

• Control Structures: The logical flow of an algorithm.
  • Sequence: Executing instructions one after the other.
  • Selection (Choice): Making decisions using IF...THEN...ELSE or CASE statements.
  • Iteration: Repeating instructions using loops (FOR, WHILE, REPEAT...UNTIL).
• Standard Algorithms:
  • Linear Search: Checks every element one by one. Slow, but works on unsorted lists.
  • Binary Search: Checks the middle element and halves the search area each time. Extremely fast, but the list must be sorted first.
  • Sorting: Bubble Sort (compares adjacent elements and swaps), Insertion Sort (builds a sorted list one element at a time), and Merge Sort (a divide-and-conquer strategy).
• Recursion: A function that calls itself to solve smaller instances of the same problem.
  • Must have a base case to stop the recursion, otherwise it creates an infinite loop.
  • Examples: Calculating Factorials ($n!$), Fibonacci sequence, or Towers of Hanoi.
  • Memory Risk: Every recursive call adds a new layer to the system's Call Stack. Too many calls will result in a "Stack Overflow" error and crash the program.

5.3 Computational Complexity & Computability

Not all algorithms are created equal. We must measure how much time and memory an algorithm consumes as the input size ($n$) grows.

• Computability & Turing Thesis: A problem is considered "computable" if an algorithm can be written to solve it on a Turing Machine in a finite amount of time.
• P vs NP Problems:
  • P (Polynomial): Problems that can be solved quickly (in polynomial time) by a computer.
  • NP (Non-deterministic Polynomial): Intractable problems where the solution can be verified quickly, but finding the solution takes an impractically long time (e.g., the Traveling Salesman Problem). We often rely on heuristic algorithms to find a "good enough" approximation for these.

6. System Design & Software Development

The final stage of the syllabus focuses on the practical application of algorithms and data structures to build real-world software, evaluating different programming approaches and rigorous testing methodologies.

6.1 Software Design & Methodologies

Before writing code, software must be carefully designed to ensure it meets user requirements and is easy to maintain.

• Top-Down Design: Breaking a large, complex system down into smaller, independent, and manageable modules (Stepwise Refinement).
• Design Tools: Representing logic visually using Structure Diagrams, Flowcharts, and Pseudocode.
• Prototyping: Building an early, simplified version of the software to gather user feedback before full-scale development.
• APIs (Application Programming Interfaces): Sets of protocols and tools that allow different software applications to communicate with each other.

6.2 Programming Paradigms

A programming paradigm is a fundamental style or approach to writing software. The syllabus requires knowledge of three main types.

• Imperative (Procedural) Programming: Writing explicit, step-by-step instructions that change the program's state (e.g., C, Pascal). Uses sequence, selection, and iteration.
• Declarative (Logic) Programming: The programmer states what the problem is, rather than exactly how to solve it. The underlying engine figures out the steps using facts and rules (e.g., Prolog, SQL).

6.3 Software Testing & Evaluation

Testing ensures the software is robust and free of critical bugs before deployment.

• Types of Test Data:
  • Normal: Standard data that the program should easily accept.
  • Extreme (Boundary): Data at the absolute limits of acceptability (e.g., if a system accepts ages 1-18, testing 1 and 18).
  • Erroneous: Data that is completely invalid and should be rejected (e.g., entering letters for an age).
• Testing Phases:
  • Alpha Testing: Conducted internally by the developers before release.
  • Beta Testing: Releasing the software to a limited group of external users to find bugs in real-world environments.

Conclusion & Further Study

These notes serve as a robust foundation for your GCE A/L Computer Science journey. To truly excel, practice writing code, trace algorithms manually, and solve past paper logic problems. Remember that a deep understanding of core concepts will always outlast memorizing syntax!