AS Level Computer Science key facts

Every chapter of AS Level Computer Science on one page: the 207 key facts, definitions and facts to remember, in syllabus order. Use it for a last look before a test, then check yourself.

Test yourself free About this test

Information representation

Data representation

Binary prefixes: 1 KiB = 2¹⁰ = 1024 bytes, 1 MiB = 2²⁰, 1 GiB = 2³⁰, 1 TiB = 2⁴⁰ bytes
Decimal prefixes: 1 kB = 10³ = 1000 bytes, 1 MB = 10⁶, 1 GB = 10⁹, 1 TB = 10¹² bytes
One hexadecimal digit = 4 bits; A = 10, B = 11, C = 12, D = 13, E = 14, F = 15
BCD: each denary digit is coded separately in 4 bits, e.g. 59 = 0101 1001
One's complement: invert every bit. Two's complement: invert every bit, then add 1. The 8-bit two's complement range is −128 to +127
Overflow: the result is outside the range, e.g. adding two positive numbers gives a result with a sign bit of 1
ASCII uses 7 bits (128 characters), extended ASCII 8 bits (256 characters); Unicode uses more bits so it can code the characters of all languages

Multimedia

Bitmap file size in bits = width in pixels × height in pixels × colour depth (ignoring the header)
Number of colours = 2^{colour depth}, e.g. 8 bits give 256 colours
Image resolution: number of pixels in the image. Screen resolution: number of pixels the display can show
Sampling rate: number of samples taken per second (Hz). Sampling resolution: number of bits used to store each sample
Sound file size in bits = sampling rate × sampling resolution × time in seconds × number of channels
Bits ÷ 8 = bytes; bytes ÷ 1024 = KiB; KiB ÷ 1024 = MiB
Bitmap for photographs (many colours and fine detail); vector for logos and diagrams that must be resized

Compression

Lossless: the original file can be restored exactly; used for text files, program files and spreadsheets
Lossy: data is removed permanently and the original cannot be restored; used for photographs, music and video
RLE stores each run as a count and a value, e.g. WWWWWBB becomes 5W2B
RLE works well when there are long runs, e.g. an image with large areas of one colour; it works badly when neighbouring values keep changing
Text: lossless only, e.g. repeated words are replaced by short codes kept in a dictionary
Bitmap: use RLE (lossless), or reduce the colour depth or the resolution (lossy)
Sound: remove sounds people cannot hear, or reduce the sampling rate or sampling resolution (lossy)

Communication

Networks and network models

Client-server: central storage, security and backup; needs a server and someone to manage it. Peer-to-peer: cheap and simple for a few computers; each user manages their own files and security
Thin client: relies on the server for processing and storage. Thick client: does most of its own processing and can work without the server
Bus: all devices share one backbone cable; a break in the backbone stops the network, and the shared cable allows collisions
Star: each device has its own cable to a central switch, which sends a packet only to the destination; one cable failing affects one device
Mesh: devices have many links to each other, so a packet can take another route if a link fails. Hybrid: a mixture of topologies
Public cloud: services from a provider, shared by many customers over the internet. Private cloud: used by one organisation only
Fibre-optic cable: higher bandwidth, less signal loss over distance and no electrical interference compared with copper; wireless gives mobility but is slower and easier to intercept

Network hardware and the internet

Switch: sends data only to the device it is addressed to, inside one LAN. Router: forwards packets between networks using IP addresses
Repeater: regenerates a weak signal. Bridge: joins two LAN segments. WAP: lets wireless devices join a wired LAN
CSMA/CD: listen before sending; if a collision is detected, stop, send a jam signal, wait a random time, then send again
Bit streaming: real-time is a live event sent as it happens; on-demand is a stored file the user starts when they choose. The broadband speed must be at least the bit rate, or the video keeps stopping to buffer
IPv4: 32 bits, four denary numbers from 0 to 255 separated by dots. IPv6: 128 bits, eight groups of four hexadecimal digits separated by colons
Public IP address: unique on the internet. Private: used only inside a LAN, not routed over the internet. Static: never changes. Dynamic: may change each time the device connects
URL = protocol + domain name + path and file name; the DNS returns the IP address for the domain name

Hardware

Computers and their components

RAM: volatile, can be read and written, holds the programs and data in use. ROM: non-volatile, read only, holds the start-up instructions
SRAM: uses flip-flops, needs no refresh, faster and more expensive, used for cache. DRAM: uses capacitors that leak and must be refreshed, cheaper, more bits per chip, used for main memory
PROM: programmed once, cannot be changed. EPROM: erased with ultraviolet light, then reprogrammed. EEPROM: erased with an electrical signal while still in the circuit
Buffer: a temporary storage area that holds data on its way between two devices that work at different speeds
Monitoring system: sensors take readings and the computer only records them or warns. Control system: the computer uses the readings to change the conditions through actuators
Feedback: the output changes the conditions, so it affects the next sensor reading (the next input)
Magnetic hard disk: magnetised spots on spinning platters. Solid state (flash): electrons trapped in floating-gate transistors, no moving parts. Optical disc: a laser reads pits and lands

Logic gates and logic circuits

NOT: the output is the opposite of the input
AND: output 1 only when both inputs are 1. OR: output 1 when at least one input is 1
NAND (NOT AND): output 0 only when both inputs are 1. NOR (NOT OR): output 1 only when both inputs are 0
XOR: output 1 when the two inputs are different
Number of rows in a truth table = 2ⁿ for n inputs: 4 rows for 2 inputs, 8 rows for 3 inputs
Evaluate brackets first; NOT applies only to the input or bracket that follows it
From words: "and" becomes AND, "or" becomes OR, "not" or "is off" becomes NOT, "exactly one of" becomes XOR

Processor fundamentals

Central Processing Unit (CPU) architecture

PC: address of the next instruction. MAR: address of the memory location to be read or written. MDR: the data just read or about to be written. CIR: the instruction being decoded and executed
ACC: results from the ALU. IX: index register, used for indexed addressing. Status Register: flags such as carry, negative and overflow
Fetch: MAR ← [PC]; PC ← [PC] + 1; MDR ← [[MAR]]; CIR ← [MDR]
[X] means the contents of X; [[MAR]] means the contents of the memory location whose address is in MAR
Address bus: one direction, CPU to memory; n lines can address 2ⁿ locations. Data bus: both directions. Control bus: carries signals such as read, write, clock and interrupt
Performance improves with more cores, a higher clock speed, wider buses and more cache memory
Interrupt: checked at the end of each cycle; the contents of the registers are saved, the PC is loaded with the address of the Interrupt Service Routine (ISR), and the registers are restored afterwards

Assembly language

Pass 1: remove comments and build a symbol table of labels and their addresses. Pass 2: use the symbol table to generate the machine code
Immediate (LDM #n): the operand is the value to use
Direct (LDD address): the operand is the address of the value
Indirect (LDI address): the operand is an address that holds the address of the value
Indexed (LDX address): the address used is the operand + the contents of IX
Relative: the address used is the address of the current instruction + the operand (an offset)
Groups: data movement (LDM, LDD, STO, MOV); input and output (IN, OUT); arithmetic (ADD, SUB, INC, DEC); compare (CMP, CMI); unconditional jump (JMP); conditional jump (JPE, JPN)

Bit manipulation

Logical shift: zeros fill the empty places and the bits pushed off the end are lost
Left shift by n places multiplies by 2ⁿ; right shift by n places divides by 2ⁿ, losing any remainder
Arithmetic shift right: the sign bit is copied into the empty places, so a negative number stays negative
Cyclic shift: a bit leaving one end re-enters at the other end, so no bits are lost
AND with a mask: 1 keeps the bit, 0 clears it to 0. Used to test a bit or to clear a bit
OR with a mask: 1 sets the bit to 1, 0 leaves it unchanged
XOR with a mask: 1 flips (toggles) the bit, 0 leaves it unchanged

System software

Operating systems

Memory management: gives RAM to each process, keeps processes from using each other's memory, handles paging and virtual memory.
Process management: decides which process gets the processor next (scheduling) and handles interrupts.
Hardware management: uses device drivers to talk to peripherals, and buffers for input and output.
File management: file names, folders, storage space and access rights. Security management: user accounts, passwords, access control.
Disk formatter: prepares a disk for use by setting up a file system. Defragmentation: moves the blocks of each file so they sit next to each other, so a hard disk reads files faster.
Library routines are already tested, so they save development time and reduce errors.
A DLL is linked at run time, loaded only when needed and can be shared by several programs. If the DLL is missing, changed or corrupted, the program may fail.

Language translators

Assembler: assembly language → machine code, usually one instruction to one instruction.
Compiler: reports all errors together after translation; the executable runs fast, runs without the compiler and hides the source code.
Interpreter: stops at the first error it meets, so errors are easy to find and fix during development; the program runs more slowly and the interpreter must be present every time.
Java: source code → compiler → bytecode → interpreted by the Java Virtual Machine, so the same bytecode runs on any platform that has a JVM.
IDE coding features: context-sensitive prompts (auto-complete). Error detection: dynamic syntax checking while typing.
IDE presentation features: prettyprint (colour and indentation), expand and collapse code blocks.
IDE debugging features: breakpoint (stops the program at a chosen line), single stepping (runs one line at a time), report window (shows the values of variables).

Security, privacy and data integrity

Data security

Virus: malicious code that copies itself and can delete or corrupt files. Spyware: secretly records what the user does, such as key presses, and sends it to a third party.
Phishing: a fake email or message with a link that tricks the user into giving personal details.
Pharming: malicious code or a changed DNS entry sends the user to a fake website even when the correct address is typed.
Firewall: checks incoming and outgoing network traffic against a set of rules and blocks traffic that does not meet them.
Encryption: turns data into ciphertext that cannot be understood without the key. It does not stop the data being stolen or deleted.
Digital signature: shows who sent a document and that it was not changed on the way.
Access rights: each user or group may only read, write or delete the data their job needs.

Data integrity

Range check: between two limits, e.g. 0 to 100. Limit check: only one boundary, e.g. not above 100.
Format check: the right pattern of letters and digits. Length check: the right number of characters. Presence check: the field is not left empty.
Existence check: the value is already stored in the system, e.g. the customer ID is in the customer table.
Check digit: an extra digit calculated from the other digits; it detects mistyped or swapped digits.
Verification at entry: visual check (compare with the source by eye) and double entry (type twice, the computer compares).
Parity by byte detects an odd number of flipped bits but cannot say which bit. Two flipped bits in a byte go unnoticed.
Parity block check: each byte has its own parity bit, and an extra parity byte holds a parity bit for each column, so one wrong bit can be located and corrected. Checksum: the receiver recalculates it and asks for the data again if the two values differ.

Ethics and ownership

Joining a professional body gives: a code of conduct to follow, training and guidance, and recognition that the member meets a professional standard.
Acting unethically can harm the public and lead to loss of reputation, loss of the job and legal action.
Free Software Foundation: users may run, study, change and share the software; changed versions must be released under the same terms.
Open Source Initiative: the source code is available, and users may modify and redistribute it.
Shareware: free to try for a limited time or with limited features, then the user must pay. The source code is not provided.
Commercial: a fee is paid for a licence; no copying or modifying; the source code is not provided; support and updates usually come with it.
AI impact: economic (some jobs replaced, new jobs created, lower costs), social (bias, privacy, help in medicine), environmental (large energy use for training models).

Databases

Database concepts

Candidate key: any attribute or smallest set of attributes that could identify each record. Primary key: the candidate key that is chosen. Secondary key: a candidate key that was not chosen, or a field indexed for searching.
Foreign key: a field in one table that refers to the primary key of another table.
Referential integrity: every foreign key value must match an existing primary key value.
Relationships are one-to-one, one-to-many or many-to-many. A many-to-many relationship is replaced by a link table and two one-to-many relationships.
1NF: no repeating groups; every field holds one value. 2NF: in 1NF, and no non-key field depends on only part of a composite primary key.
3NF: in 2NF, and no non-key field depends on another non-key field.
Index: a separate structure that makes searching on a field faster.

Database Management Systems (DBMS)

Data dictionary: metadata such as table names, field names, data types, field lengths, keys, validation rules and relationships. It holds no actual records.
Logical schema: a description of the design of the database (entities, attributes and relationships) that does not depend on how the data is physically stored.
Data modelling: planning the structure of the data, for example with an E-R diagram.
Data integrity: the DBMS applies validation rules, data types and referential integrity.
Data security: user accounts and passwords, access rights for individuals and groups, and regular backups so data can be restored after loss.
Developer interface: lets a developer create tables, forms, reports and queries.
Query processor: takes a query (written in SQL), checks it, finds an efficient way to run it and returns the result.

Data Definition Language (DDL) and Data Manipulation Language (DML)

DDL: CREATE DATABASE, CREATE TABLE, ALTER TABLE, PRIMARY KEY, FOREIGN KEY ... REFERENCES.
DML: SELECT, INSERT INTO, DELETE FROM, UPDATE.
Data types: CHARACTER, VARCHAR(n), BOOLEAN, INTEGER, REAL, DATE, TIME.
Keys: PRIMARY KEY (MemberID) and FOREIGN KEY (MemberID) REFERENCES MEMBER(MemberID). New field: ALTER TABLE MEMBER ADD Phone VARCHAR(15);
Join: SELECT ... FROM A INNER JOIN B ON A.Key = B.Key returns only records that match in both tables.
ORDER BY sorts ascending unless DESC is written.
INSERT INTO T (F1, F2) VALUES (v1, v2); UPDATE T SET F1 = v1 WHERE condition; DELETE FROM T WHERE condition;

Algorithm design and problem-solving

Computational thinking skills

Abstraction: filter out unnecessary detail and keep the essential features.
Benefits of abstraction: the problem is simpler to understand, the program is shorter and quicker to write, and it needs less memory and processing.
To build an abstract model, ask of each detail: does the solution need it? If not, leave it out.
Decomposition: split a problem into sub-problems until each can be coded directly.
Benefits of decomposition: modules can be written and tested separately, shared between programmers and reused.
A function returns a value; a procedure carries out a task and does not return a value.

Algorithms

Identifier table: lists each identifier with its data type and a description of its purpose.
Identifiers should be meaningful, for example TotalMark, not T.
FOR ... NEXT: count-controlled loop, the number of repeats is known.
WHILE ... ENDWHILE: condition tested at the start, so the loop may run zero times.
REPEAT ... UNTIL: condition tested at the end, so the loop runs at least once.
Flowchart symbols: parallelogram for input or output, rectangle for a process, diamond for a decision.
A range needs both tests joined with AND, e.g. Mark >= 40 AND Mark <= 59. Use brackets when AND and OR are mixed: (A OR B) AND C.

Data types and structures

Data types and records

INTEGER: a whole number, e.g. 42. REAL: a number with a fractional part, e.g. 12.99
CHAR: one character in single quotes, e.g. 'Y'. STRING: text in double quotes, e.g. "Yes"
BOOLEAN: TRUE or FALSE only. DATE: a calendar date, e.g. 14/03/2009
Define a record type:
TYPE StudentRecord
DECLARE Name : STRING
DECLARE Age : INTEGER
ENDTYPE
Declare a variable of that type: DECLARE Student1 : StudentRecord
Access a field with variable name, dot, field name: Student1.Age ← 17
In an array of records the index comes first, then the field: Group[3].Name

Arrays

1D: DECLARE Marks : ARRAY[1:30] OF INTEGER. 2D: DECLARE Grid : ARRAY[1:3, 1:4] OF CHAR (row first, then column)
number of elements = upper bound − lower bound + 1, e.g. ARRAY[0:19] has 20 elements
Linear search of n items: 1 comparison at best, n comparisons if the item is last or not present
A swap needs a temporary variable:
Temp ← List[i]
List[i] ← List[i + 1]
List[i + 1] ← Temp
A bubble sort of n items needs at most n − 1 passes
A Boolean flag such as Swapped lets the sort stop early when a pass makes no swaps

Files

OPENFILE "data.txt" FOR READ: read an existing file, starting from its first line
FOR WRITE: a new file is created; if the file already exists, its old contents are lost
FOR APPEND: new lines are added after the existing lines, which are kept
READFILE "data.txt", Line reads the next line into Line. WRITEFILE "data.txt", Line writes Line as a new line
EOF("data.txt") returns TRUE if there are no more lines to read, otherwise FALSE
Reading loop:
WHILE NOT EOF("data.txt") DO
READFILE "data.txt", Line
ENDWHILE
CLOSEFILE "data.txt" saves any buffered data and releases the file

Introduction to Abstract Data Types (ADT)

Stack: LIFO. Push adds to the top, pop removes from the top. Uses: return addresses, undo, reversing data
Queue: FIFO. Add at the rear, remove from the front. Uses: print jobs, keyboard buffer
Linked list: a start pointer gives the first node; the last node holds the null pointer
Stack in an array: TopPointer. Push: check not full, add 1 to TopPointer, store the item. Pop: check not empty, take the item, subtract 1
Queue in an array: FrontPointer and RearPointer. In a circular queue a pointer at the upper bound moves next to the lower bound
Linked list in arrays: Data[i] holds the item and Pointer[i] holds the index of the next node; unused nodes are kept in a free list
Insert X between P and Q: X points to Q, then P points to X. Delete Q: the node before Q points to the node after Q

Programming

Programming basics

DECLARE Count : INTEGER declares a variable; CONSTANT VAT = 0.2 declares a constant; Count ← Count + 1 assigns
INPUT Name reads from the keyboard; OUTPUT "Hello ", Name writes to the screen
DIV(x, y) is the whole-number quotient and MOD(x, y) is the remainder: DIV(23, 4) = 5, MOD(23, 4) = 3. The operator / gives a real result: 7 / 2 = 3.5
LEFT(s, n) and RIGHT(s, n) return n characters from that end; MID(s, x, y) returns y characters starting at position x
LENGTH(s) returns the number of characters; & joins two strings
INT(x) returns the integer part of x; ASC(c) returns the character code of c; CHR(n) returns the character with code n
AND is TRUE only if both parts are TRUE; OR is TRUE if at least one part is TRUE; NOT reverses the value

Constructs

IF condition THEN ... ELSE ... ENDIF. In nested IFs, only the first branch whose condition is TRUE runs
CASE OF Day
   1 : ...
   2 TO 4 : ...
   OTHERWISE : ...
ENDCASE
FOR i ← 1 TO 10 STEP 2 ... NEXT i: number of repetitions known in advance
repetitions of a FOR loop with a positive step = DIV(end − start, step) + 1, e.g. 1 TO 10 STEP 2 gives DIV(9, 2) + 1 = 5
WHILE condition DO ... ENDWHILE: body runs 0 or more times
REPEAT ... UNTIL condition: body runs 1 or more times
A loop never ends if nothing in its body can make the condition change to the stopping value

Structured programming

PROCEDURE Name(BYVAL X : INTEGER, BYREF Y : INTEGER) ... ENDPROCEDURE, run with CALL Name(A, B)
FUNCTION Name(X : INTEGER) RETURNS INTEGER ... RETURN value ... ENDFUNCTION, used as Result ← Name(A)
Header: the first line of the definition. Interface: the parameters, their data types, their order and how each is passed
Parameter: the variable named in the header. Argument: the value supplied in the call
BYVAL passes a copy; BYREF passes the address. If neither is written, BYVAL is assumed
Efficiency: leave a loop as soon as the result is known, and do not repeat inside a loop a calculation whose result never changes

Software development

Program development life cycle

Order of stages: analysis → design → coding → testing → maintenance
Analysis: investigate the problem and the current system; produce the requirements specification
Design: plan the solution with structure charts, pseudocode or flowcharts, and data structures
Coding: write the program. Testing: find and correct errors using test data. Maintenance: correct, adapt and improve the program after release
Waterfall: easy to manage, with clear milestones and full documentation; but users see a working program late, so changes are costly
Iterative: a working version exists early and requirements can change; but the total time and cost are hard to predict
RAD: fast delivery and easy changes; but users must be available often, and it suits smaller projects that split into modules

Program design

Structure chart: box = module; line = a call from the upper module to the lower module
Arrow with a hollow (empty) circle = a data parameter; arrow with a filled circle = a flag (Boolean value)
Diamond where the lines leave a module = selection: which lower module runs depends on a condition
Curved arrow across the lines below a module = iteration: the lower modules are called repeatedly
State-transition diagram: each state is drawn once; an arrow labelled with an event is a transition
An event that does not change the state is drawn as an arrow that returns to the same state
A state-transition table lists the same facts: current state, event, next state

Program testing and maintenance

Syntax error: e.g. a missing ENDIF. Logic error: e.g. < written instead of <=. Run-time error: e.g. an array index outside the bounds
Normal data: typical valid values, accepted. Abnormal data: invalid values, rejected. Extreme data: the largest and smallest valid values. Boundary data: the values on each side of a limit
Dry run: tracing the code by hand with a trace table. Walkthrough: a team works through the code or design step by step
White-box: tests every path, using the structure of the code. Black-box: checks inputs against expected outputs without seeing the code
Stub: a dummy module stands in for one not yet written. Integration: tested modules are combined and tested together
Alpha: in-house, by the developer's own staff. Beta: by selected real users before general release. Acceptance: by the client, to agree that the system meets the requirements
Corrective: fix errors found in use. Adaptive: change the program for new rules, hardware or needs. Perfective: improve a program that already works, e.g. make it faster