O Level / IGCSE Computer Science key facts

Data representation

Number systems

• 8-bit place values: 128, 64, 32, 16, 8, 4, 2, 1
• One hex digit = 4 bits (a nibble): A = 10, B = 11, C = 12, D = 13, E = 14, F = 15
• Largest positive value in n bits = 2ⁿ − 1 (8 bits: 255, 16 bits: 65 535)
• Binary addition: 0 + 1 = 1, 1 + 1 = 0 carry 1, 1 + 1 + 1 = 1 carry 1
• Overflow: the result is bigger than 255, so it needs a 9th bit that an 8-bit register cannot hold
• Logical shift left by n places multiplies by 2ⁿ; shift right divides by 2ⁿ; empty places fill with 0 and bits pushed off the end are lost
• Two's complement, 8 bits: left bit = −128, range −128 to +127. To make a number negative: invert every bit, then add 1

Text, sound and images

• Character set: the list of characters a computer can use, each with a unique binary code
• ASCII: 7 bits, 128 characters (extended ASCII: 8 bits, 256). Unicode: up to 32 bits per character, far more characters
• Sample rate: number of samples taken per second, measured in hertz (Hz)
• Sample resolution: number of bits used to store each sample
• Image resolution: number of pixels in the image (width × height)
• Colour depth: number of bits per pixel. Number of colours = 2^{colour depth}
• Raising sample rate, sample resolution, image resolution or colour depth improves accuracy and increases file size

Data storage and compression

• 4 bits = 1 nibble; 8 bits = 1 byte
• 1024 bytes = 1 KiB; then × 1024 each step: KiB, MiB, GiB, TiB, PiB, EiB
• Image file size in bits = width in pixels × height in pixels × colour depth
• Sound file size in bits = sample rate × sample resolution × length in seconds
• Bits ÷ 8 = bytes; bytes ÷ 1024 = KiB; KiB ÷ 1024 = MiB
• Lossy: data removed permanently, e.g. JPEG, MP3. Good for photos, music and video
• Lossless, e.g. run length encoding (RLE): repeated data is stored once with a count. Needed for text and program files

Data transmission

Types and methods of data transmission

• Packet header: destination IP address, sender's (originator's) IP address, packet number
• Packet trailer: marks the end of the packet and holds error-checking data
• Serial: one bit at a time, one wire. Reliable over long distances, cheaper, but slower
• Parallel: several bits at once on several wires. Faster, but only for short distances because bits can arrive out of step (skewed)
• Simplex: one direction only. Half-duplex: both directions, one at a time. Full-duplex: both directions at the same time
• USB: serial; device is detected automatically and its driver loaded; plug fits one way only; can supply power; cable length is limited

Methods of error detection

• Even parity: the total number of 1s in each byte, including the parity bit, must be even. Odd parity: it must be odd
• A parity check misses errors where an even number of bits are flipped
• Parity block: a parity bit on every byte (row) plus a parity byte (columns). The failing row and column cross at the wrong bit
• Checksum: a value calculated from the block of data and sent with it; the receiver recalculates and compares
• Echo check: the receiver sends the data back and the sender compares. It cannot tell on which journey the error happened
• Check digit: an extra digit calculated from the other digits. It finds wrong digits and swapped digits
• ARQ: receiver sends an acknowledgement. If none arrives before the timeout, the sender sends the data again

Encryption

• Plaintext: data before encryption. Ciphertext: data after encryption
• Encryption makes data meaningless if intercepted; it does not prevent interception
• Symmetric: one key, used by both sender and receiver, to encrypt and to decrypt
• Asymmetric: a public key and a private key. The public key is given to anyone; the private key is kept secret by its owner
• To send to someone: encrypt with the receiver's public key
• Only the receiver's matching private key can decrypt it

Hardware

Computer architecture

• PC: address of the next instruction. MAR: address being read from or written to. MDR: data or instruction just fetched. CIR: instruction being decoded. ACC: results from the ALU
• ALU: does arithmetic and logic. CU: decodes instructions and sends control signals
• Address bus: one direction, CPU to memory. Data bus and control bus: both directions
• Fetch: PC → MAR, PC increases by 1, instruction → MDR → CIR. Then the CU decodes and the instruction is executed
• Clock speed: cycles per second. More cores: more instructions at the same time. Larger cache: more often-used data kept close to the CPU
• Instruction set: the list of all machine code commands a CPU can carry out
• Embedded system: a computer built into a device to do one dedicated job, e.g. washing machine, traffic lights

Input and output devices

• Sensor readings are usually analogue, so an analogue-to-digital converter (ADC) changes them to digital data
• A sensor only measures. The microprocessor makes the decision and an actuator carries out the movement
• Temperature: heat. Light: brightness. Humidity: water vapour in air. Moisture: water in soil. pH: acidity
• Pressure: force or weight. Acoustic: sound. Gas: a gas level. Level: height of liquid. Flow: rate of liquid or gas movement
• Infra-red and proximity: something present or near. Accelerometer: movement and tilt. Magnetic field: magnetism
• Touch screens: resistive (pressure joins two layers), capacitive (a finger changes the charge), infra-red (a finger breaks light beams)
• Printers: laser (charged drum, toner, heat), inkjet (sprays liquid ink), 3D (builds an object layer by layer)

Data storage

• RAM: volatile (loses contents without power), can be read and written, holds data and programs in use
• ROM: non-volatile, read only, holds the start-up (boot) instructions
• Magnetic (HDD): spinning platters; tiny areas are magnetised to stand for 1 or 0; a read/write head moves over them
• Optical (CD, DVD, Blu-ray): a laser reads pits and lands on the disc surface
• Solid-state (SSD, USB flash drive, SD card): transistors hold charge; no moving parts; fast, quiet, robust
• Virtual memory: part of secondary storage used as extra RAM; slower than real RAM
• Cloud: access from anywhere and no hardware to maintain, but needs an internet connection and you depend on the provider for security

Network hardware

• MAC address: 48 bits, written as 6 pairs of hex digits, e.g. 00:1A:2B:3C:4D:5E
• First 3 pairs of a MAC address = manufacturer code; last 3 pairs = serial number of the device
• IPv4: 32 bits, 4 denary numbers from 0 to 255 separated by dots, e.g. 192.168.0.12
• IPv6: 128 bits, 8 groups of hex digits separated by colons. Introduced because IPv4 was running out of addresses
• Static IP address: stays the same; used for servers so they can always be found
• Dynamic IP address: can change each time the device connects; given out automatically

Software

Types of software and interrupts

• Operating system functions: managing files, memory, multitasking, peripherals and drivers, user accounts and security; handling interrupts; providing an interface; running applications
• Device driver: software that lets the operating system communicate with a hardware device
• Hardware interrupts: key pressed, mouse moved, printer out of paper
• Software interrupts: division by zero, two processes trying to use the same memory location
• Handling: the CPU finishes its current fetch-decode-execute cycle, checks the interrupt's priority, saves the current state (register contents), runs the interrupt service routine (ISR), then restores the state and continues
• Multitasking: the CPU gives each task a short slice of time in turn and uses interrupts to switch

Types of programming language, translators and IDEs

• Assembly language is a low-level language that uses mnemonics such as LDA and ADD. An assembler translates it into machine code.
• Compiler: translates the whole high-level program before it runs and produces an executable file.
• Compiler: reports all the errors in the code together, after it has tried to translate the whole program.
• Interpreter: translates and runs one line at a time, and stops at the first error. It does not produce an executable file.
• A compiled program runs without the translator and does not show the source code, so it suits a finished program that is sold.
• An interpreter suits development: the error is shown at the line where it happens, so it can be fixed and the code run again quickly.
• IDE functions: code editor, run-time environment, translator, error diagnostics, auto-completion, auto-correction and prettyprint.

The internet and its uses

The internet and the world wide web

• A URL has a protocol, a domain name and a web page or file name. In https://www.myschool.org/exams/dates.html these are https, www.myschool.org and /exams/dates.html.
• HTTP (hypertext transfer protocol) is the set of rules for sending web pages between a web server and a browser.
• HTTPS is the secure version: the data sent between the browser and the web server is encrypted.
• Browser functions: rendering HTML, address bar, navigation tools, bookmarks and favourites, user history, multiple tabs, storing cookies.
• Retrieving a page: browser sends the domain name to the DNS → DNS returns the IP address → browser sends a request to the web server at that address → server sends the HTML → browser renders it.
• Cookies are small text files sent by a web server and stored by the browser. They save personal details, login details, preferences and items in a shopping basket.
• A session cookie is deleted when the browser is closed. A persistent cookie stays on the device until it expires or the user deletes it.

Digital currency

• Digital currency: money with no physical form, held and transferred electronically.
• Blockchain: a digital ledger, which is a time-stamped series of records that cannot be altered.
• A block holds the transaction data, a time stamp, its own hash value and the hash value of the previous block.
• The stored hash of the previous block is what links the blocks into a chain.
• If the data in a block is changed, its hash changes and no longer matches the hash stored in the next block, so the change is detected.
• Decentralised: copies of the ledger are held by many computers, not by one central authority.

Cyber security

• Virus: attaches to a file and copies itself when the file is run. Worm: copies itself and spreads across a network without a host file or any user action.
• Trojan horse: malware hidden inside software that looks harmless. Ransomware: encrypts files and demands payment for the key.
• Spyware: secretly records what the user does, such as key presses, and sends it to a third party. Adware: displays unwanted adverts.
• Phishing: a fake email or message with a link to a fake website. Pharming: malicious code redirects a correctly typed URL to a fake website.
• DDoS (distributed denial of service): many computers send requests to one server at the same time so it cannot respond to real users.
• Solutions: anti-malware, firewall, proxy server, strong passwords, biometrics, two-step verification, access levels, automatic software updates, SSL and privacy settings.
• Firewall: checks incoming and outgoing traffic against set rules. Proxy server: sits between the user and the internet, hides the user's IP address and filters requests.

Automated and emerging technologies

Automated systems

• Sensor = input device that measures a physical quantity. It does not make decisions and does not control anything.
• The signal from a sensor is often analogue, so it is converted to digital (by an ADC) for the microprocessor.
• Sequence: sensor sends reading → microprocessor compares it with the preset value → signal sent to actuator if needed → process repeats.
• Actuator = device that turns a signal into movement, for example to open a window, turn on a pump or raise a barrier.
• Advantages: works continuously without breaks, consistent results, faster response, safer in dangerous places, less waste of materials and energy.
• Disadvantages: high set-up cost, needs maintenance, a faulty sensor gives wrong results, can be hacked, cannot deal with unexpected situations, may replace jobs.

Robotics

• Characteristics of a robot: a mechanical structure, electrical components (sensors, microprocessor, actuators) and it is programmable.
• Roles: welding and painting in factories, driverless vehicles, harvesting and weeding crops, surgery, vacuum cleaners and lawn mowers, entertainment.
• Advantages: can work 24 hours a day, precise and consistent work, can work in places that are dangerous for people, lower running costs over time.
• Disadvantages: expensive to buy and maintain, cannot deal well with unexpected situations, can replace workers' jobs, people may lose skills.
• A robot is not the same as AI: a simple robot only repeats the instructions it has been given.

Artificial intelligence

• Knowledge base: the facts about the subject, collected from human experts.
• Rule base: the set of rules (often in the form IF ... THEN ...) that link the facts.
• Inference engine: applies the rules to the facts and to the user's answers to reach a conclusion. It also decides which question to ask next.
• Interface: how the user and the system communicate. It shows the questions, takes the answers and displays the result.
• Machine learning: the program is trained on data, finds patterns, and changes its own rules or data to improve its results.
• Difference: the rules of a basic expert system are set by experts; a machine learning program adapts its own.

Algorithm design and problem-solving

Program development life cycle and decomposition

• Order of the life cycle: analysis → design → coding → testing.
• Analysis: abstraction, decomposition, identifying the problem and the requirements.
• Design: decomposition, structure diagrams, flowcharts and pseudocode. Coding: writing program code and iterative testing. Testing: using test data.
• Input = data entered. Process = what is done to the data. Output = what is shown or produced. Storage = data kept for later use.
• Structure diagram: shows a system broken down into sub-systems in a hierarchy, level by level from the top.
• Flowchart symbols: rounded box (terminator) for start and stop, parallelogram for input or output, rectangle for a process, diamond for a decision.
• To give the purpose of an algorithm, say what it does overall, not what each line does.

Standard methods of solution

• Linear search: the number of comparisons equals the position of the item. If the item is not in a list of n items, all n are compared.
• Bubble sort: the first pass through n items makes n − 1 comparisons and, for ascending order, moves the largest value to the end.
• A flag such as Swapped stops the bubble sort early when a pass makes no swaps.
• Totalling: Total ← Total + Value. Counting: Count ← Count + 1. Both must be set to 0 before the loop.
• Maximum: start Highest at the first item, then IF Value[i] > Highest THEN Highest ← Value[i].
• Minimum: start Lowest at the first item, then replace it whenever a smaller value is found.
• Average = Total ÷ Count, calculated once, after the loop has finished.

Validation, verification and test data

• Range check: the value is between two limits. Length check: the number of characters is correct. Type check: the data is of the right data type.
• Presence check: the field has not been left empty. Format check: the characters follow a pattern, such as two letters then four digits.
• Check digit: an extra digit calculated from the other digits, used to find errors in a code number such as a barcode.
• Visual check: a person compares the data on screen with the source document. Double entry: the data is typed twice and the computer compares the two entries.
• Normal data: sensible data the program should accept and process. Abnormal data: data that should be rejected.
• Extreme data: the largest and smallest values that are accepted.
• Boundary data: the pair of values at each limit, one that is accepted and one that is rejected.

Trace tables and correcting algorithms

• A WHILE loop tests its condition before each pass, so it may run zero times. A REPEAT ... UNTIL loop tests at the end, so it always runs at least once.
• A REPEAT loop stops when its condition becomes true. A WHILE loop stops when its condition becomes false.
• DIV(x, y) gives the whole-number part of x ÷ y. MOD(x, y) gives the remainder. DIV(17, 5) = 3 and MOD(17, 5) = 2.
• MOD(Num, 2) = 1 means Num is odd. MOD(Num, 2) = 0 means Num is even.
• Totals and counts must be set to 0 before the loop, not inside it.
• To accept values from 0 to 100 inclusive, use >= 0 AND <= 100.
• When a loop ends on a special value, input before the loop and again at the end of the loop, so the special value is not processed.

Programming

Variables, data types and operators

• Declare a variable: DECLARE Score : INTEGER. Declare a constant: CONSTANT Rate ← 0.15. Assign with ←.
• INTEGER = whole number (7); REAL = number with a decimal part (4.0); CHAR = one character ('A'); STRING = text ("Hello"); BOOLEAN = TRUE or FALSE.
• INPUT Name reads a value into a variable. OUTPUT "Total: ", Total prints the text and then the value held in Total.
• Arithmetic operators: + − * / and ^ (power). The / operator gives a real result, e.g. 10 / 4 = 2.5.
• DIV(17, 5) = 3 (whole-number part of the division). MOD(17, 5) = 2 (the remainder).
• Order of operations: brackets, then ^, then * and /, then + and −.
• Relational operators (=, <>, <, <=, >, >=) give TRUE or FALSE. AND needs both conditions TRUE; OR needs at least one; NOT reverses the value.

Sequence, selection, iteration and string handling

• IF condition THEN ... ELSE ... ENDIF. CASE OF variable ... OTHERWISE ... ENDCASE; OTHERWISE runs when no listed value matches.
• FOR i ← 1 TO 10 ... NEXT i is count-controlled: a fixed number of repeats. STEP changes the amount added each time, e.g. STEP −3.
• WHILE condition DO ... ENDWHILE is pre-condition: the test is at the start, so the loop may run zero times.
• REPEAT ... UNTIL condition is post-condition: the test is at the end, so the loop always runs at least once.
• Totalling: Total ← Total + Value. Counting: Count ← Count + 1. Set both to 0 before the loop.
• LENGTH("Cat") = 3 (spaces count as characters). SUBSTRING("Lahore", 2, 3) = "aho": start position, then number of characters, first character at position 1.
• UCASE("Cat") = "CAT" and LCASE("Cat") = "cat".

Procedures, functions and maintainable programs

• PROCEDURE DrawLine(Size : INTEGER) ... ENDPROCEDURE. Call it with CALL DrawLine(5).
• FUNCTION Area(L : INTEGER, W : INTEGER) RETURNS INTEGER ... RETURN L * W ... ENDFUNCTION. Use it in an expression: X ← Area(5, 3).
• Local variable: declared inside a subroutine, usable only there. Global variable: declared outside all subroutines, usable anywhere in the program.
• MOD(x, y) gives the remainder and DIV(x, y) gives the whole-number quotient: MOD(14, 4) = 2, DIV(14, 4) = 3.
• ROUND(x, places) rounds x to the given number of decimal places: ROUND(6.283, 2) = 6.28.
• RANDOM() returns a random number between 0 and 1 inclusive.
• Maintainable program: meaningful identifiers, comments, procedures and functions, and consistent indentation.

Arrays and file handling

• 1D array: DECLARE Names : ARRAY[1:30] OF STRING gives 30 elements, Names[1] to Names[30].
• 2D array: DECLARE Grid : ARRAY[1:5, 1:8] OF INTEGER gives 5 × 8 = 40 elements. Grid[2, 7] is the element in row 2, column 7.
• All elements of an array have the same data type.
• Fill or read an array with a loop: FOR i ← 1 TO 30 ... INPUT Names[i] ... NEXT i.
• OPENFILE "Data.txt" FOR READ or FOR WRITE. Opening an existing file FOR WRITE replaces its old contents.
• READFILE "Data.txt", LineOfText reads one line into a variable. WRITEFILE "Data.txt", LineOfText writes one line to the file.
• Always finish with CLOSEFILE "Data.txt". Order: open, read or write, close.

Databases

Single-table databases and primary keys

• Field = one column (one item of data). Record = one row (all the data about one item).
• Number of fields = number of columns. Number of records = number of items stored.
• Data types: text/alphanumeric (letters, digits and symbols), character (one character), Boolean (true/false or yes/no), integer (whole number), real (decimal number), date/time.
• Use text/alphanumeric for codes and phone numbers: they are not used in calculations and may start with 0.
• Validation checks include range, length, type, presence and format checks.
• Primary key: a field that uniquely identifies each record. It must hold a different value in every record.

Structured query language (SQL)

• Order of clauses: SELECT fields FROM table WHERE condition ORDER BY field;
• SELECT chooses the fields (columns). WHERE chooses the records (rows).
• AND: a record must meet both conditions. OR: a record must meet at least one condition.
• ORDER BY Price ASC sorts from smallest to largest. ORDER BY Price DESC sorts from largest to smallest.
• SUM(field) adds up the values in a numeric field for the matching records.
• COUNT(field) gives the number of matching records.
• Text values go in quotes, e.g. WHERE Type = 'Pen'. Numbers do not.

Boolean logic

Logic gates

• NOT: output is the opposite of the input. Symbol: triangle with a small circle at the output.
• AND: output is 1 only when both inputs are 1. Symbol: flat input side, rounded (D-shaped) output side.
• OR: output is 1 when at least one input is 1. Symbol: curved input side, pointed output (shield shape).
• NAND: output is 0 only when both inputs are 1. Symbol: AND with a small circle at the output.
• NOR: output is 1 only when both inputs are 0. Symbol: OR with a small circle at the output.
• XOR (EOR): output is 1 only when the two inputs are different. Symbol: OR with an extra curved line across the inputs.
• Outputs for inputs 00, 01, 10, 11: AND 0001; OR 0111; NAND 1110; NOR 1000; XOR 0110.

Logic circuits and logic expressions

• Each operator in an expression needs one gate: X = (A AND B) OR NOT C needs one AND, one NOT and one OR gate.
• The operation done last in the expression is the gate that produces the final output.
• Brackets show what is worked out first, so that part is drawn nearest the inputs.
• NOT (A OR B) is the same as A NOR B. NOT (A AND B) is the same as A NAND B.
• If a condition is described as 0 (off, closed, not pressed), put NOT in front of that input.
• From a truth table: for each row where X = 1, write the inputs joined by AND (with NOT on any input that is 0), then join these rows with OR.

Truth tables

• Number of rows = 2ⁿ for n inputs: 2 inputs give 4 rows, 3 inputs give 8 rows.
• Write the rows in binary order: 000, 001, 010, 011, 100, 101, 110, 111.
• Work in stages: brackets first, then the gate that uses those results.
• Use working columns for intermediate outputs, e.g. P = A AND B, then X = P OR C.
• AND gives 1 only for 1,1. OR gives 0 only for 0,0. XOR gives 1 only when the inputs differ. NAND and NOR are the inverses of AND and OR.
• NOT changes 1 to 0 and 0 to 1 before the value is used by the next gate.