A Level Computer Science (A2) key facts

Data Representation

User-defined data types

• Enumerated type: TYPE TSeason = (Spring, Summer, Autumn, Winter). The values are names, not strings, so they have no quotation marks, and they are ordered.
• Pointer type: TYPE TIntPtr = ^INTEGER. P ← ^Num stores the address of Num in P; P^ means the value at that address.
• Record: TYPE TBook … ENDTYPE with a DECLARE line for each field; a field is reached with a dot, e.g. Shelf[3].Pages.
• Set: no order, no repeated values. Union = values in either set; intersection = values in both; difference = values in the first set but not the second.
• Class: properties (data) plus methods (procedures and functions); an object is one instance of a class.
• Choosing: several different facts about one thing → record; one value from a short fixed list → enumerated type; membership with no repeats → set.

File organisation and access

• Serial: new records are added at the end; good for logs and transaction files that are read once, start to end.
• Sequential: records in key order; good for batch jobs that process every record, such as payroll. Adding a record usually means writing a new file to keep the order.
• Random: address = hash of the key; good when any one record is needed at once, such as a booking system.
• Access: serial and sequential files use sequential access; sequential files (with an index) and random files allow direct access.
• A common hash: address = key MOD number of record positions, which gives addresses from 0 to (number of positions − 1).
• Collision: two different keys hash to the same address. One fix is to use the next free position; another is an overflow area.
• A good hashing algorithm spreads keys evenly, so there are few collisions. A random file may have unused positions, so it can take more space.

Floating-point numbers, representation and manipulation

• value = mantissa × 2^exponent; a positive exponent moves the binary point right, a negative exponent moves it left.
• Mantissa place values: −1, then 1/2, 1/4, 1/8 … The first bit is the sign bit: 0 positive, 1 negative.
• Normalised: a positive mantissa starts 01, a negative mantissa starts 10.
• To normalise: each shift of the mantissa one place to the left needs 1 to be subtracted from the exponent, so the value stays the same.
• More bits for the mantissa → more precision; more bits for the exponent → a larger range of values. The total number of bits is fixed, so one is gained at the cost of the other.
• Overflow: the result is too large for the exponent to hold. Underflow: the result is too close to zero to be represented.
• Rounding errors: do not test two real numbers for exact equality after calculations.

Communication and internet technologies

Protocols

• Application layer: protocols used by programs, e.g. HTTP, FTP, SMTP, POP3, IMAP, BitTorrent.
• Transport layer: splits the data into segments, adds port numbers and sequence numbers, and (with TCP) checks delivery and asks for resending.
• Internet layer: adds source and destination IP addresses to make packets and routes them between networks.
• Link layer: puts packets into frames with MAC addresses and sends them over the physical network.
• HTTP: requests and sends web pages. FTP: transfers files between two hosts.
• SMTP: sends email. POP3: downloads email to one device and usually removes it from the server. IMAP: reads email that stays on the server, kept in step on several devices.
• BitTorrent: peer-to-peer file sharing; a file is split into pieces that peers download from, and upload to, each other.

Circuit switching, packet switching

• Circuit switching benefits: the full bandwidth is reserved, the data rate is constant, the data arrives in order with no delay once the circuit is set up.
• Circuit switching drawbacks: time is needed to set up the circuit, the reserved path is wasted when nothing is sent, and if a link fails the connection is lost.
• Circuit switching is used for a traditional landline telephone call and other real-time uses that need a steady rate.
• Packet switching benefits: links are shared efficiently, packets can be sent round a failed or busy route, and only a lost or damaged packet is resent.
• Packet switching drawbacks: packets can be delayed, lost or arrive out of order, each one carries a header as overhead, and they must be reassembled.
• Packet switching suits data sent in bursts, such as web pages and email; it is how the internet works.
• A routing table entry links a destination network to the next hop (where to send the packet next).

Hardware and Virtual Machines

Processors, Parallel Processing and Virtual Machines

• RISC: few instructions, fixed length, few addressing modes, many general-purpose registers, hard-wired control unit, only LOAD and STORE use memory, easy to pipeline.
• CISC: many instructions, variable length, many addressing modes, fewer registers, microprogrammed control unit, hard to pipeline.
• Pipelined time for n instructions with k stages, no stalls = k + (n − 1) clock cycles; without a pipeline it is k × n.
• Interrupt: checked at the end of the fetch–execute cycle; the program counter and registers are saved, the interrupt service routine runs, then the registers are restored.
• SISD: one processor, one data stream. SIMD: the same instruction on many data items at once (arrays, graphics). MISD: several processors, different instructions, the same data. MIMD: several processors, different instructions, different data (multi-core).
• Massively parallel computer: a very large number of processors linked together, working on parts of one problem and passing messages to each other.
• Virtual machine: lets another OS or old software run on a host and be tested safely; it runs more slowly than real hardware and depends on the host.

Boolean Algebra and Logic Circuits

• Half adder: sum = A XOR B, carry = A AND B.
• Full adder: sum = A XOR B XOR Cin; carry-out = (A AND B) OR (Cin AND (A XOR B)). It can be made from two half adders and an OR gate.
• SR flip-flop: S = 1, R = 0 sets Q to 1; S = 0, R = 1 resets Q to 0; S = 0, R = 0 keeps Q unchanged; S = 1, R = 1 is not allowed.
• JK flip-flop (changes on the clock pulse): J = 0, K = 0 no change; J = 1, K = 0 sets Q to 1; J = 0, K = 1 resets Q to 0; J = 1, K = 1 toggles Q.
• De Morgan's laws: NOT (A AND B) = (NOT A) OR (NOT B); NOT (A OR B) = (NOT A) AND (NOT B).
• Useful laws: A OR (NOT A) = 1; A AND (NOT A) = 0; A OR (A AND B) = A; A AND (B OR C) = (A AND B) OR (A AND C).
• Karnaugh map: labels in the order 00, 01, 11, 10; groups of 1, 2, 4, 8 or 16 cells, as large as possible; groups may overlap and wrap round the edges.

System Software

Purposes of an Operating System (OS)

• State changes: ready → running (chosen by the scheduler); running → ready (time slice ends); running → blocked (waits for I/O); blocked → ready (I/O done). Blocked → running is not possible.
• Round robin: each process gets a fixed time slice in turn, then rejoins the end of the ready queue. Fair, with a good response time.
• First come first served: processes run to completion in order of arrival; simple, but a long process holds up the others.
• Shortest job first: the process with the shortest total time runs next and is not interrupted; shortest remaining time is the same idea but a new, shorter process can take the processor. Long processes may wait a very long time.
• Paging: memory is divided into fixed-size blocks; pages (logical) are loaded into page frames (physical), and a page table maps one to the other.
• Segmentation: memory is divided into variable-size blocks that match logical parts of the program.
• Page fault: the page needed is not in RAM, so it is brought in from disk and another page may be replaced (e.g. first in first out, or least recently used). Disk thrashing: so many pages are swapped that more time goes on swapping than on running processes.

Translation Software

• Lexical analysis: removes spaces and comments, turns the characters into tokens, and builds the symbol table.
• Syntax analysis: checks the tokens against the grammar rules, builds a parse tree and reports syntax errors.
• Code generation: produces the object code. Optimisation: makes the code run faster or use less memory.
• BNF: ::= means "is defined as", | means "or", and a name in angle brackets such as <digit> is an item defined by another rule.
• A BNF rule that uses its own name, e.g. <number> ::= <digit> | <number><digit>, allows repetition (one or more digits).
• Infix to RPN: (a + b) * c becomes a b + c *, and a + b * c becomes a b c * +.
• To evaluate RPN: push each operand; for an operator, pop two values, apply it as (second popped) operator (first popped), then push the result.

Security

Encryption, Encryption Protocols and Digital Certificates

• Private message to a person: the sender encrypts with the receiver's public key; only the receiver's private key can decrypt it.
• Verified message to the public: the sender encrypts with their own private key; anyone can decrypt it with the sender's public key, which proves who sent it.
• Digital signature: the message is hashed to give a digest, and the digest is encrypted with the sender's private key. Matching digests show the message is authentic and has not been changed.
• Digital certificate: issued by a Certificate Authority (CA) after it checks the applicant; it holds the owner's name, the owner's public key, the issuer, a serial number, valid dates and the CA's digital signature.
• SSL/TLS: the server sends its certificate, the browser checks it, a session key is agreed with asymmetric encryption, then the data is sent with faster symmetric encryption.
• Each extra bit in a key doubles the number of possible keys: n bits give 2ⁿ keys.
• Quantum cryptography sends the key as photons. Benefit: any eavesdropping changes the photons and is detected. Drawbacks: high cost, special equipment (fibre optic links) and limited distance.

Artificial Intelligence (AI)

Artificial Intelligence (AI)

• Dijkstra: always visit the unvisited vertex with the smallest total distance from the start, then update its neighbours if a shorter route is found.
• A*: f(n) = g(n) + h(n), where g is the cost from the start so far and h is the heuristic estimate of the cost to the goal. Expand the vertex with the smallest f.
• A heuristic is admissible if it never overestimates the true cost to the goal; A* then finds the shortest path.
• Supervised learning: trained with labelled data (inputs with known correct outputs). Unsupervised learning: no labels, the system finds patterns or groups itself.
• Reinforcement learning: an agent learns by trial and error, with rewards for good actions and penalties for bad ones.
• Back propagation: compare the output with the expected output, pass the error back through the layers and adjust the weights to reduce it; repeat many times.
• Regression: finds the relationship between variables (for example a best-fit line y = mx + c) and uses it to predict a value.

Computational thinking and Problem-solving

Algorithms

• Binary search: Mid ← (Low + High) DIV 2; if the item at Mid is too small then Low ← Mid + 1; if too large then High ← Mid − 1; stop when found or when Low > High.
• Time: linear search O(n); binary search O(log n), so doubling the number of items adds only one more comparison.
• Bubble sort and insertion sort: O(n²) in the worst case (reverse order), O(n) in the best case (already sorted; bubble sort needs a "no swaps" flag to stop early).
• Stack: last in, first out (LIFO); push and pop at the top. Queue: first in, first out (FIFO); add at the rear, remove from the front.
• Linked list: each node holds data and a pointer to the next node; insert or delete by changing pointers, with no items moved. Free nodes are kept in a free list.
• Ordered binary tree: smaller values go to the left subtree, larger values to the right; each node has a left pointer and a right pointer.
• Dictionary: a set of key and value pairs, searched by key. ADTs can be built from arrays, records or other ADTs.

Recursion

• Essential features: a base case, a general (recursive) case, and each call moving closer to the base case.
• Each call pushes a stack frame holding its parameters, local variables and return address.
• On return the frame is popped and control goes back to the statement after the call (unwinding).
• To trace: write the calls down the page until the base case, then work the return values back up.
• Statements placed after the recursive call run during unwinding, so their output appears in reverse order.
• No base case, or a base case that is never reached, gives endless calls and stack overflow.
• Any recursive routine can be rewritten with a loop; the loop usually runs faster and uses less memory.

Further Programming

Programming Paradigms

• Immediate: the operand is the value itself (LDM #n). Direct: the operand is the address of the value (LDD). Indirect: the operand is an address that holds the address of the value (LDI).
• Indexed: address used = operand + contents of the index register IX (LDX). Relative: address used = current address + offset.
• A function returns a value; a procedure does not. BYVAL passes a copy; BYREF passes the address, so changes affect the original variable.
• A class is a template; an object is an instance of a class. A constructor sets up a new object.
• Encapsulation: attributes are kept private and reached only through public methods (getters read a value, setters change it).
• Inheritance: a subclass takes the attributes and methods of its parent class. Polymorphism: a subclass redefines an inherited method so the same call behaves differently. Containment (aggregation): one class contains objects of another class.
• Declarative: a fact such as parent(amir, sara). A rule such as grandparent(X, Z) IF parent(X, Y) AND parent(Y, Z). Names starting with a capital letter are variables.

File Processing and Exception Handling

• OPENFILE "F.txt" FOR READ (or WRITE, APPEND, RANDOM); CLOSEFILE "F.txt" when finished.
• READFILE "F.txt", Line reads the next line; WRITEFILE "F.txt", Line writes one line; EOF("F.txt") is TRUE at the end of the file.
• Read every line with: WHILE NOT EOF("F.txt") ... READFILE ... ENDWHILE.
• Random files: SEEK "F.dat", Address moves to a record; GETRECORD reads the record there; PUTRECORD writes a record there.
• To insert into a sequential file or delete from a serial or sequential file: copy the records to a new file, adding or leaving out the one record, then replace the old file.
• Python: code that may fail goes in try:, the handler goes in except:, and the program then carries on after the handler.
• Use exception handling for events the program cannot prevent: file not found, wrong data type entered, division by zero, disk full.