National Year 13 Computer Science
Chapters: 11
1. 4.1 Fundamentals of programming (A-level)
Pointer data type · Stack frames and recursion · Object-oriented programming
- Programming Basics: Sequence, Selection, Loops and Functions – A program is a set of exact instructions a computer follows. Every program is built from three structures: sequence (steps in order), selection (if/else choices) and iteration (loops). Variables store values. Functions group code into reusable, named blocks, which makes programs modular and easier to test, debug and maintain.
- Recursion: Functions That Call Themselves – Recursion is when a function solves a problem by calling itself on a smaller version of the same problem. Every recursive function needs a base case, where it stops and returns an answer directly, and a recursive case that moves closer to the base case. Each call gets its own stack frame on the call stack; frames are removed as calls return.
- Object-Oriented Programming (OOP) – Object-oriented programming builds a program out of objects. A class is a blueprint that lists the data (attributes) and actions (methods) its objects will have. Each object is made from a class and keeps its own data. The four big ideas are encapsulation (hide data behind methods), inheritance (a new class reuses an old one), polymorphism (the same method call behaves in the right way for each object) and abstraction (show only what is needed).
2. 4.2 Fundamentals of data structures (A-level)
Abstract data types
- Data Structures: Arrays, Lists, Stacks, Queues and Trees – A data structure is a way of organising data in memory so a program can use it well. Arrays keep items in numbered boxes for instant access by index. Linked lists chain nodes with pointers, so inserting is easy. Stacks work last-in-first-out, queues first-in-first-out. Dictionaries find values by key, and trees store data in levels so searching is fast. Choosing the right structure makes programs faster and simpler.
3. 4.3 Fundamentals of algorithms
Traversals · Reverse Polish notation · Searching and sorting · Optimisation
- Graph Algorithms – A graph is a set of vertices joined by edges, which can carry weights. Breadth-first search (BFS) explores in layers using a queue and finds the fewest-edge path. Depth-first search (DFS) goes deep using a stack or recursion and backtracks. Trees can be traversed pre-order, in-order and post-order. Dijkstra's algorithm finds shortest paths from one vertex when weights are non-negative. Kruskal's and Prim's algorithms build a minimum spanning tree. Route inspection finds the shortest closed route using every edge; the travelling salesperson problem asks for the shortest tour of every vertex. In a flow network, the maximum flow equals the capacity of the minimum cut.
- Data Structures: Arrays, Lists, Stacks, Queues and Trees – A data structure is a way of organising data in memory so a program can use it well. Arrays keep items in numbered boxes for instant access by index. Linked lists chain nodes with pointers, so inserting is easy. Stacks work last-in-first-out, queues first-in-first-out. Dictionaries find values by key, and trees store data in levels so searching is fast. Choosing the right structure makes programs faster and simpler.
- Searching and Sorting Algorithms – A searching algorithm finds an item in a list; a sorting algorithm puts a list in order. Linear search checks items one by one and works on any list. Binary search halves a sorted list each time and is much faster. Bubble sort swaps neighbours pass by pass; merge sort splits the list and merges sorted halves, which is faster for big lists.
4. 4.4 Theory of computation (A-level)
Regular languages · Context-free languages · Classification of algorithms · Turing machine
- Finite State Machines and Formal Languages – A finite state machine (FSM) has a fixed set of states, an alphabet of input symbols, a start state, a transition function that says which state comes next for each symbol, and (for an acceptor) a set of accepting states. It reads an input string one symbol at a time; if it ends in an accepting state the string is accepted. A Mealy machine also gives an output on each transition. The strings an FSM accepts form a regular language, which can also be described by a regular expression. Languages with nesting (like brackets) need more power: they are context-free and are written with BNF rules or syntax diagrams.
- Computational Complexity: Easy, Hard and Impossible Problems – Complexity measures how the number of steps grows as the input size n grows. Polynomial algorithms (n, n², n³) are tractable; exponential (2ⁿ) and factorial (n!) ones become hopeless very fast, so such problems are intractable. Some problems are easy to check but hard to solve (NP). Some, like the halting problem, cannot be solved by any algorithm at all.
- Computability: Turing Machines and the Limits of Computing – A Turing machine is a simple model of any computer: an endless tape of cells, a head that reads and writes one cell at a time, a finite set of states and a table of transition rules. Anything an algorithm can compute, a Turing machine can compute (Church–Turing thesis). A universal Turing machine reads another machine's rules from its tape and runs it. Some problems, like the halting problem, can never be solved by any algorithm: they are non-computable (undecidable).
5. 4.5 Data representation (A-level)
Floating point · Vector graphics
- Number Systems and Encoding – A number system is a way to write numbers using a set of digits and a base. Decimal (base 10) uses 0–9, binary (base 2) uses 0 and 1, octal (base 8) uses 0–7, and hexadecimal (base 16) uses 0–9 and A–F. To go from decimal to any base, divide repeatedly by the base and read remainders bottom to top; for fractions, multiply by the base and read the integer parts top to bottom. To go to decimal, multiply each digit by its place value and add. Binary ↔ octal uses groups of 3 bits, binary ↔ hex groups of 4. Text is stored with encoding schemes: ASCII (7-bit, 128 characters), ISCII (8-bit, Indian scripts) and Unicode (every script), stored as UTF-8 (1–4 bytes) or UTF-32 (4 bytes).
- Data Representation: How Computers Store Numbers, Text, Images and Sound – Data is raw facts; information is data given meaning; knowledge is information we can use. A computer stores all data as bits (0 or 1). 8 bits make a byte, and 1 kB = 1000 bytes, 1 MB = 1000 kB, 1 GB = 1000 MB, 1 TB = 1000 GB. Numbers are stored in binary, where place values double: 1, 2, 4, 8 and so on. Text uses a character set: in ASCII 'A' is 65; Unicode covers every script. A bitmap image is a grid of pixels; size = width × height × colour depth. Sound is sampled: size = sample rate × bit depth × seconds. Vector images store shapes instead of pixels. Compression makes files smaller: lossless keeps every bit, lossy throws some detail away.
6. 4.6-4.7 Computer systems and architecture (A-level)
Logic circuits · Interrupts
- Boolean Logic – Boolean logic works with only two values: 1 (true) and 0 (false). Logic gates act on them: NOT flips a value; AND gives 1 only if all inputs are 1; OR gives 1 if any input is 1; NAND and NOR are the opposites of AND and OR; XOR gives 1 when inputs differ. A truth table lists the output for every input combination (2ⁿ rows for n inputs). De Morgan's laws: (A·B)' = A' + B' and (A + B)' = A'·B'. Gates joined together form logic circuits that match Boolean expressions.
- Processor Internals: Registers, the Fetch–Execute Cycle, Addressing Modes and Interrupts – A processor has an ALU, a control unit, a clock and registers (PC, MAR, MDR, CIR, accumulator, status register), joined to main memory by the address, data and control buses. Each instruction is fetched (MAR ← [PC]; MDR ← [Memory[MAR]], PC ← [PC] + 1; CIR ← [MDR]), decoded into opcode and operand, and executed. Operands use immediate addressing (the value itself) or direct addressing (a memory address). Assembly language uses mnemonics such as LDR, STR, ADD, SUB, CMP, B and BEQ. Performance depends on cores, cache, clock speed, word length and bus widths. Interrupts make the processor save its volatile environment on a stack, run an interrupt service routine and then resume.
7. 4.9 Communication and networking
The Internet · TCP/IP
- Web Services: What Happens When You Open a Website – The World Wide Web (WWW) is a system of linked web pages that live on the Internet and are reached with a browser. Web pages are written in HTML, which uses fixed tags to show content; XML uses tags you make yourself to store and carry data. Every website has a domain name, like example.org, which DNS turns into an IP address. A URL is the full address of one resource: protocol, domain and path. A website is a set of related web pages. A web browser asks for pages and shows them; a web server stores them and sends them; web hosting is renting space on such a server so your site is online all the time.
- Network Types, Topologies and Protocols: Size, Shape and Rules – Networks are grouped by size: PAN (a few metres around one person), LAN (a room, building or campus), MAN (a city) and WAN (a country or the world). A topology is the layout of how nodes are wired: bus (all on one backbone cable), star (all to a central hub or switch) and tree (stars joined in levels). A protocol is a set of rules: TCP/IP breaks and routes data on the Internet, HTTP and HTTPS carry web pages, FTP moves files, SMTP sends email, POP3 downloads email, PPP links two devices directly, TELNET logs into a remote computer, and VoIP carries voice calls over the Internet.
8. 4.10 Fundamentals of databases
Data modelling and relational design · SQL and client-server databases
- Relational Databases: Tables, Rows, Columns and Keys – Keeping data in many separate files leads to repeated data, mismatched copies and hard searching, so we use a database managed by a DBMS. In the relational model data sits in tables called relations. A column is an attribute, a row is a tuple, and the set of allowed values for a column is its domain. The number of columns is the degree; the number of rows is the cardinality. A candidate key is any column (or set) that can identify every row uniquely; the one chosen is the primary key and the others are alternate keys. A foreign key is a column in one table that refers to the primary key of another table, linking them.
- SQL for Class 12: Build Tables, Ask Questions, Join Tables – SQL is the language used to create and query relational databases. DDL commands (CREATE, ALTER, DROP) build structure; DML commands (INSERT, UPDATE, DELETE) change rows; SELECT reads data. Columns get data types (CHAR, VARCHAR, INT, FLOAT, DATE) and constraints (NOT NULL, UNIQUE, PRIMARY KEY, DEFAULT, FOREIGN KEY). SELECT can use aliases, DISTINCT, WHERE with relational and logical operators, IN, BETWEEN, LIKE and IS NULL, and ORDER BY. Aggregate functions (MAX, MIN, AVG, SUM, COUNT) summarise many rows; GROUP BY makes groups and HAVING filters groups. A Cartesian product pairs every row of one table with every row of another; an equi-join keeps only pairs whose common column matches; a natural join does the same and shows the common column once.
9. 4.11 Big Data
What Big Data is · Processing Big Data · Modelling Big Data
- Big Data – Big data is data that is too big, too fast or too mixed to store and process on one ordinary computer with normal tools. We describe it with Volume (how much), Velocity (how fast it arrives) and Variety (how many kinds). To handle it, the work is split across many machines that run at the same time (distributed processing, for example MapReduce). Big data is often stored as simple facts or as a graph of nodes and links, and it is used for weather forecasts, maps, health, shopping and training AI. It also raises questions about privacy and fairness.
10. 4.12 Fundamentals of functional programming
Functional paradigm · Writing functional programs and lists
- Functional Programming: Functions, Map, Filter and Fold – In functional programming a program is built from functions. A function maps each input from its domain to one output in its co-domain, and its type is written f: A → B. Pure functions give the same output for the same input and change nothing else (no side effects); data is immutable. Functions are first-class: they can be named, passed in and returned. Partial application gives a function some of its inputs and returns a new function. Composition g ∘ f runs f, then g. Higher-order functions take or return functions: map applies a function to every list item, filter keeps items that pass a test, fold (reduce) combines a list into one value. A list is a head (first item) plus a tail (the rest).
11. 4.14 Non-exam assessment: practical project
Choosing the project · Report sections and marks · Technical skill and coding style · Testing and evaluation evidence
- The Capstone Computing Project: Choose, Analyse, Design, Build, Test, Evaluate – A capstone (practical) project is a large piece of work where you solve a real problem with a program, or investigate a computing question, and write a report about it. Choose a problem with a real user and enough technical depth: complex data structures, algorithms or models. The report follows the stages of development: analysis (problem, user, research, measurable objectives), documented design (data structures, algorithms, interfaces, modules), technical solution (the working code, which carries most marks), testing (a test plan with normal, boundary and erroneous data and evidence) and evaluation (judging each objective, using user feedback and suggesting improvements). Good coding style means meaningful names, small cohesive modules, comments where needed, and defensive code that handles bad input.