Pearson Edexcel International GCSE (9-1) Computer Science Exhaustive Study Notes

Understanding Algorithms

• Definition: An algorithm is a precise, unambiguous method for solving a problem, consisting of a sequence of step-by-step instructions.

• Unambiguity: Instructions must not be misunderstood. Stating 'turn' is ambiguous; 'turn left' or 'turn right' is unambiguous.

• Successful Algorithm Criteria:     * Accuracy: It must lead to the expected outcome (e.g., calculating a route between the correct cities).     * Consistency: It must produce the same result every time it is run.     * Efficiency: It must solve the problem in the shortest time using minimum computer resources.

• Relationship to Programs: An algorithm is the design for a solution; a program is the implementation of that design in a programming language.

• Written Descriptions: The simplest way to express algorithms (e.g., steps for making coffee).

• Flowcharts: Visual diagrams using specific symbols:     * Oval: Start or end of an algorithm.     * Rectangle: A process to be carried out.     * Diamond: A decision to be made.     * Parallelogram: Input or output.     * Arrows: The logical flow.

• Pseudocode: A structured, code-like language used to describe logic without the strict rules of specific programming languages. It centralizes on logic and efficiency.

• Arithmetic Operators:     * $+$ (Addition): Adds values.     * $-$ (Subtraction): Subtracts the second value from the first.     * $<em>$ (Multiplication): Multiplies values.      $/$ (Real Division): Returns a result with decimal places (e.g., $13/4 = 3.25$).     * $DIV$ (Quotient): Returns the whole number/integer result (e.g., $13 ext{ DIV } 4 = 3$).     * $MOD$ (Modulus/Modulo): Returns the remainder (e.g., $13 ext{ MOD } 4 = 1$).     * ^ (Exponentiation): 'To the power of' (e.g., $3^3 = 27$).

• Variables and Constants:     * Variable: A 'container' for data where the value can change during program execution.     * Constant: A 'container' that holds a value that never changes (e.g., $ext{pi}$).     * Identifiers: Unique descriptive names (e.g., $firstName$).     * Naming Conventions: 'camelCase' (e.g., $firstName$) or 'snake_case' (e.g., $first_name$).

Creating Algorithms and Logic Constructs

• Programming Constructs:     * Sequence: Step-by-step instructions in the correct order.     * Selection: Allowing choices between alternatives (e.g., IF statements).     * Iteration: Repeating a process ('looping') until a condition is met.

• Selection in Pseudocode:     * Uses $IF...THEN...ELSE...END IF$ syntax.     * Nested IF statements are used when there are more than two possible courses of action.

• Iteration (Loops):     * Definite Iteration: Used when the number of turns is known in advance (e.g., $REPEAT...END REPEAT$ or $FOR...END FOR$).     * Indefinite Iteration: Used when the number of repetitions is unknown in advance (e.g., $WHILE...DO...END WHILE$).

• Relational Operators:     * $==$ (Equal to)     * > (Greater than)     * >= (Greater than or equal to)     * < (Less than)     * <= (Less than or equal to)     * $!=$ (Not equal to)

• Logical Operators:     * AND: Both conditions must be true.     * OR: Either condition can be true.     * NOT: Reverses the logic (TRUE becomes FALSE).     * Operator Precedence: Brackets $\rightarrow$ NOT $\rightarrow$ AND $\rightarrow$ OR.

Sorting and Searching Algorithms

• Bubble Sort:     * Method: Starts at one end, compares pairs of data, and swaps them if in the wrong order. One complete traversal is a 'pass'.     * Efficiency: Brute force method; inefficient for lists larger than $1000$ items.

• Merge Sort:     * Method: 'Divide and conquer' approach. Recursively divides a list until the size of each sub-list is one, then merges them in order.     * Efficiency: Much more efficient than bubble sort for large datasets.

• Linear Search:     * Method: Sequential search through a list, item by item.     * Advantage: Works on unsorted lists.

• Binary Search:     * Method: Selects the median (middle) item. If the median is the target, it stops; if higher/lower, it repeats recursion on the relevant half-list.     * Requirement: The list must be sorted (ascending or descending).     * Efficiency: Search in a list of $1000$ items takes an average of $500$ comparisons for linear search, but a maximum (worst-case) of $10$ for binary search.

Computational Thinking: Decomposition and Abstraction

• Computational Thinking: The thought processes involved in formulating problems such that solutions can be carried out by a computer.

• Decomposition: Breaking a complex problem into smaller, manageable sub-problems (e.g., breaking a 'noughts and crosses' game into grid design, move tracking, win/draw checking).

• Abstraction: Removing unnecessary detail to focus on important points (e.g., representing a physical die as a virtual random number generator between $1$ and $6$).

• Levels of Abstraction: Higher levels have less detail (e.g., a driver turning a car key without understanding engine mechanics).

• Subprograms: Self-contained modules of code (functions or procedures) that perform specific tasks.     * Functions: Return a value to the main program (e.g., $RANDOM(6)$).     * Procedures: Do not return values.     * Scope: Local variables exist only within a subprogram; global variables are accessible anywhere.     * Arguments vs. Parameters: Arguments are data passed in; parameters are names used inside the subprogram to handle that data.

Programming Languages and Data Types

• Data Types:     * Integer: Whole numbers (e.g., $30$).     * Real/Float: Numbers with fractional parts (e.g., $25.5$).     * Boolean: True or False.     * Character: A single letter, symbol, or space (e.g., 'm').     * String: A sequence of characters (e.g., 'Catherine').

• Variable Initialisation: Setting starting values (e.g., $SET ext{ total TO } 0$). Failure to do this can lead to unexpected results.

• Type Coercion/Casting: Converting data from one type to another (e.g., $1 ( ext{int}) + 2.25 ( ext{real}) = 3.25 ( ext{real})$).

• Readability Techniques:     * Comments: Explain code purpose (Python: #, Java/C#: //).     * Descriptive Identifiers: Meaningful names for variables/subprograms.     * Indentation: Shows where code blocks start and finish.     * White Space: Blank lines to separate blocks.

Strings and Data Structures

• String Indexing: Characters are referenced using index numbers starting at $0$.

• Length: The $LENGTH()$ function returns the count of characters (e.g., 'Computer Science' length is $16$, indices $0-15$).

• String Traversal: Using a loop to cycle through each character.

• Concatenation: Joining items together (e.g., 'Hello' + userName).

• Arrays: An organized collection of related values of the same type.     * Static Arrays: Fixed size (declared as $arrayFriends[5]$).     * Dynamic Lists: Can grow/shrink; Python uses lists which are dynamic by default.

• Multidimensional Arrays: An 'array of arrays' (e.g., $results[3, 4]$).

• Records: A data structure storing related values of different data types (e.g., a student record with $learnerNum$ (integer) and $firstName$ (string)). Each element is a 'field'.

Input, Output, and Validation

• Validation: Checking data meets requirements (ensures it is reasonable, not necessarily 'correct').

• GIGO Principle: 'Garbage In, Garbage Out'.

• Validation Types:     * Range Check: Within specified limits (e.g., $1$ to $10$).     * Presence Check: Data was actually entered.     * Look-up Check: Checks value against a predefined set (e.g., valid form names).     * Length Check: Correct number of characters (e.g., UK postcodes $6-8$ chars).

• Text Files: Provide permanent storage separate from RAM.     * File Handling Terms: File handle (label for resource), overwritten (losing a file by opening a new one of the same name).     * CSV (Comma Separated Values): Using commas to separate data fields for spreadsheet compatibility.

Testing and Evaluation

• Logic Errors: Program runs but produces incorrect results (e.g., $12 + 6 / 2 = 15$ instead of $(12 + 6) / 2 = 9$).

• Syntax Errors: Breaching the grammar rules of the language (e.g., writing 'prnit' instead of 'print').

• Runtime Errors: Occur during execution (e.g., division by zero).

• Trace Tables: A formal technique to check logic by recording variable changes row-by-row.

• Integrated Development Environment (IDE): Tools including code editors and debuggers.

• Test Plans: Documenting tests with:     * Normal Data: Within limits.     * Boundary Data: At the outer limits (e.g., $0$ or $100$ for a $0-100$ range).     * Erroneous Data: Values that should be rejected (e.g., negative numbers).

Binary and Number Systems in Data

• Bit and Byte: A bit is $1$ or $0$. A nibble is $4$ bits. A byte is $8$ bits.

• Binary Prefixes (IEC Standards):     * Kibibyte (KiB): $2^{10} = 1024$ bytes.     * Mebibyte (MiB): $2^{20}$ bytes.     * Gibibyte (GiB): $2^{30}$ bytes.     * Tebibyte (TiB): $2^{40}$ bytes.

• Decimal Prefixes:     * Kilobyte (KB): $10^3 = 1000$ bytes.     * Megabyte (MB): $10^6$ bytes.     * Gigabyte (GB): $10^9$ bytes.     * Terabyte (TB): $10^{12}$ bytes.

• Representation of Text:     * ASCII: Original $7$-bit code ($128$ characters).     * Extended ASCII: $8$-bit code ($256$ characters).     * Unicode: Universal standard using $2$ or $4$ bytes to represent all known languages.

• Representation of Graphics:     * Pixel: 'Picture element'; smallest single point of colour.     * Resolution: Pixels per inch.     * Colour Depth: Bits per pixel (e.g., $8$ bits = $256$ colors, $24$ bits = True Colour / over $16.7$ million colors).     * File Size Expression: $ext{Width} imes ext{Height} imes ext{Colour Depth}$ (measured in bits; divide by $8$ for bytes).

• Representation of Sound:     * Sampling: Measurement of sound waves at regular intervals.     * Sample Rate: Samples per second ($44.1 ext{ kHz}$ for CD).     * Bit Depth: Number of bits per sample (e.g., $16$-bit for CD).     * Formula: $ext{Rate} imes ext{Bit Depth} imes ext{Duration} imes ext{Channels}$.

Data Compression and Encryption

• Lossless Compression: No data lost. Essential for text/code.     * Run-Length Encoding (RLE): Represents repeated strings as (number, data) pairs (e.g., $wwbbb$ becomes $2w3b$).

• Lossy Compression: Deletes data humans can't distinguish. Permanent.     * JPEG: Images.     * MP3: Audio (removes frequencies humans can't hear).

• Encryption Concepts:     * Plaintext: Original text.     * Ciphertext: Encrypted text.     * Key: Algorithm/value used to encode.

• Ciphers:     * Pigpen: Substitutes letters with symbols from a grid.     * Caesar: Shift cipher (e.g., Key $+3$, A becomes D).     * Vigenère: Uses polyalphabetic substitution (keyword and grid).     * Rail Fence: Transposition cipher; letters written in zigzag pattern based on a key (number of tracks).

Computer Hardware and the von Neumann Model

• von Neumann Architecture: Program instructions and data are stored together in memory.

• CPU Components:     * Control Unit (CU): Coordinates CPU actions.     * Arithmetic/Logic Unit (ALU): Performs math and Booleans.     * Clock: Synchronizes cycles; measured in Gigahertz (GHz).     * Registers: Accumulator (math results), Program Counter (next address), Current Instruction.

• Buses:     * Address Bus: Carries memory locations.     * Data Bus: Carries actual data.     * Control Bus: Carries control signals (read/write).

• Memory Types:     * RAM: Random-Access Memory. Volatile (lost without power).     * ROM: Read-Only Memory. Non-volatile. Stores firmware (BIOS/UEFI).     * Cache: Fast memory between CPU and RAM to bridge speed differences.     * Virtual Memory: Using secondary storage (HDD/SSD) as 'RAM' when physical RAM is full. Can lead to 'disk thrashing'.

• Secondary Storage Technologies:     * Magnetic: Platters, tracks, sectors (e.g., Hard Disks).     * Optical: Lasers and pits/lands (e.g., CD, DVD, Blu-Ray).     * Solid State (Flash): Trapped electrons in transistor pools (e.g., USB sticks, SSDs). No moving parts.

• Embedded Systems: Small, low-power computers dedicated to one task (e.g., washing machine, car engine management).

• Internet of Things (IoT): Physical objects connected to the Internet.

Software and Systems

• System Software:     * Operating System (OS): Manages hardware, UI (GUI or CLI), processes (scheduling), and memory (paging).     * Utility Software: Tools for management (defragmenters, compression, backup) and security (antivirus, firewall).

• Application Software: Performs user tasks (e.g., Word, Spreadsheet).

• Multitasking: OS allows processes to run concurrently by giving each a share of CPU time.

• Simulation and Modelling: Using abstraction to ask 'what if?' questions (e.g., flight simulators, weather models).

• Programming Languages:     * Machine Code: Binary $1s$ and $0s$.     * Low-level (Assembly): Uses mnemonics (e.g., $LDR, ADD$). Translated by an Assembler.     * High-level: Human-like (Python, Java). Translated by Compilers (all at once) or Interpreters (line-by-line).

Networks and Connectivity

• Scale:     * PAN: Personal Area Network (Bluetooth).     * LAN: Local Area Network (single site).     * WAN: Wide Area Network (large area, e.g., the Internet).

• Models:     * Client-Server: Powerful servers provide services; clients request them.     * Peer-to-Peer: Every computer acts as both client and server.

• Topologies:     * Bus: Single cable; terminators stop signal bounce.     * Ring: Closed loop; no collisions.     * Star: Central hub or switch. Most reliable (cable break only affects one device).     * Mesh: Fully or partially connected. Highly fault-tolerant; largest example is the Internet.

• Network Hardware: Switch (routes packets within LAN), Router (routes packets between networks), Modem (converts digital/analogue), WAP (Wireless Access Point).

• Protocols:     * Email: SMTP (sending), POP3 (downloads/deletes), IMAP (syncs/keeps on server).     * Transfer: HTTP (web), HTTPS (secure encrypted web), FTP (files).     * TCP/IP Layers: Application $\rightarrow$ Transport $\rightarrow$ Internet $\rightarrow$ Link.

• Mobile Generations: $3G$ (video/streaming), $4G$ (higher speed/gaming), $5G$ (low latency, $100 ext{ Gbps}$ peak).

Network Security and Ethics

• Cyber Attacks:     * Social Engineering: Phishing (fake emails), Pharming (DNS redirection), Shoulder Surfing.     * Technical: Unpatched software, malware (viruses, worms, Trojans, ransomware), eavesdropping.

• Security Measures:     * Authentication: Passwords, Biometrics.     * Access Control: Read/Write permissions.     * Firewalls: Hardware or software filters for traffic.     * Internal Security: Audit trails, modular testing, penetration testing ('pen testing').

• Privacy Issues: Personal data harvesting, Big Data analysis, surveillance technology (CCTV, facial recognition, drones).

• Legal Impact:     * Intellectual Property (IP): Creations of the mind. Protected by Copyright/Patents (exclusive rights for $20$ years).     * Licensing: Proprietary (closed source) vs. Open-source (freely editable).     * Creative Commons: Licenses allowing copying for non-commercial use.

Current and Emerging Trends

• Artificial Intelligence (AI): Machines solving cognitive problems (learning, planning, perception).

• DNA Computing: Using DNA as data storage and processing; Uses four bases (A, T, G, C) forming 'codons' of $64$ values. Small and durable over thousands of years.

• Nanotechnology: Manipulating matter at the $1-100 ext{ nanometre}$ scale. Used for carbon nanotubes to replace silicon transistors.

• Quantum Computing: Based on subatomic physics.     * Qubits: Can be $1$ and $0$ at the same time (Superposition).     * Entanglement: Qubits influence each other over distance.     * Impact: Can solve complex encryption in seconds that classical computers would take millions of years to calculate.