A-Level Computer Science Theory

A-Level Computer Science Theory

1. 4.2 Fundamentals of Data Structures

   • 4.2.1 Data Structures
     • A data structure is a structure in which data is stored and organised
     • Arrays
       • -They allow multiple values of the same data type to be stored in a single structure -They are indexed allowing a particular value to be referenced directly -One dimensional arrays are indexed by a single number, for example: animals[3] -N-dimensional arrays are indexed by multiple numbers, for example: seat[4][6] -A two-dimensional array is usually implemented as an array of arrays - a three dimensional array is an array of two dimensional arrays.  
     • Files
       • Data can be stored persistently in a file, as text or binary data. Text files only store ASCII or Unicode text and are therefore readable by humans. Binary files store different data types as their direct binary representations and are therefore not easily readable by humans. As the binary file contains only binary data, the program reading the file mus cast the binary to the appropriate data type.
     • Static data structures
       • Static data structures are stored in a fixed block of concurrent memory locations. The memory is allocated when the structure is declared, and can no longer be changed once it is in use.
       • Quick to locate and retrieve data
       • Quick to edit existing data
       • Cannot be resized
       • Removal of data is slow
         • This is due to a gap being left, and all subsequent data having to be 'shifted' up.
     • Dynamic data structures
       • Dynamic data structures adjust their storage as necessary to fit the data they hold - data is not stored in concurrent memory locations, so new locations can be used as needed.
       • Easily re-sized and new data added
       • Slower to locate and read data
       • Data can be removed quicker
         • As it is easier to re-allocate existing data - only one pointer has to be altered
     • Abstract data structures
       • Abstract data structures are structures defined by what they do, rather than how they are implemented - they can be implemented using other data structures.
   • 4.2.2 Queues
     • Works on a first-in, first-out basis, such as pushing things through a tube. Used to store anything to be executed the same order as when it was submitted, such as: -Print jobs -Keyboard presses
     • Priority queue
       • Allows data to be added with a priority value, allowing it to be removed before other items, even if it was added afterwards.
     • Circular queue
       • Loops back to the start once it is full - the back of the queue starts overwriting the front of the queue as it circles.
       • Advantages: can be more efficient as if data is added part way through the queue, it can fill up completely still by looping back round, and the only thing to be altered are the pointers of the front and back of the queue, as opposed to shifting each data value, which is time consuming.
     • Required functions
       • Add item to queue
       • Remove item from queue
       • Empty queue test
       • Full queue test
   • 4.2.3 Stacks
     • Works on a first-in, last-out basis, such as putting items in a box. Used to store the return parameters when a function is called. Each nested function is added to the stack, and removed as it finishes.
     • Required functions
       • Push
         • Enter data to the stack
       • Pop
         • Remove the most recently added data from the stack
       • Peek / top
         • "view" the data most recently added to the stack, without removing it.
       • Empty stack test
       • Full stack test
   • 4.2.4 Graphs
     • an abstract data structure used to represent more complex relationships.
     • Types
       • Standard graph
         • Vertices connected by edges
       • Weighted graph
         • Edges are assigned a value
       • Directed graph
         • Edges are only in one direction 
     • Representations
       • Adjacency list
         • Useful when there is low connectivity as due to it being quicker to read.
         • Used to save space
       • Adjacency matrix
         • Useful when there are few nodes, and especially when there is a high connectivity.
         • Used to save time
   • 4.2.5 Trees
     • A tree is any undirected graph that does not contain any loops. A rooted tree is a tree that has one vertex designated as the root.
     • Rooted tree
       • -Has one vertex designated as the root -Traversal of a rooted tree starts at the root and continues outwards -Each vertex has a parent vertex and child vertices, with the root being a vertex with no parents
     • Binary tree
       • -A rooted tree in which each vertex has a maximum of two children
     • Uses
       • Graphics
       • Classification
       • File systems
       • Binary search trees
       • Parsing HTML
   • 4.2.7 Dictionary
     • Is an abstract data structure where data is stored as a key-value pair. A value is stored with its associated key, and the key can be used to "look up" the value. Many programming languages have an associative array, which is an implementation of a dictionary. A dictionary is a good structure to use for information retrieval.
   • 4.2.6 Hash Tables
     • A hash tables is an abstract data structure that can be used for exceptionally quick searches. They use a static data structure (array) to store data at specific instances. A hash function is applied to data, which creates a key - the data is stored at that address. When searching for a value, the hash function can be used to know where to look, eliminating the need to use time-consuming search algorithms.
     • Collisions
       • These occur when two data items produce the same key, and therefore would be stored in the same location - there are two methods to solve this; closed hashing and open hashing.
       • Open hashing
         • The second value is stored in the next available space, which results in more collisions as the data occupies a space that another value may need. This can cause problems if the table isn't large enough, as the "next available space" may run past the end of the table, requiring rehashing. The table typically needs to be 30% larger than the number of items it will store, resulting in wasted space.
       • Closed hashing
         • Data is stored within a dynamic data structure (linked list) in each location, therefore there is no need for larger tables or rehashing. They can be slower to read due to there being no immediate way to access the required data, a path must be followed through all the pointers.
         • Slower - following pointers takes time No collisions - solves the issue with open hashing
     • Rehashing
       • Rehashing is the process of creating a new, usually larger table, and re-calculating the hashes of all the values in the current table in order to transfer them - which is a slow process.
   • 4.2.8 Vectors
     • A vector (in computing) is a set of values that follow the rules of vector mathematics. All entries must be drawn from the same field  (integers, real numbers etc.) They can be visualised as arrows - each of the vector values representing its magnitude in a given dimension.
     • Notation
       • There are lots of different ways of representing a vector; such as arrows, arrays etc.
     • Vector addition
       • A = [a1, a2] B = [b1, b2] A + B = [a1+b1, a2+b2]
     • Scalar multiplication
       • A = [a1, a2] 2A = [2xa1, 2xa2]
     • Dot product
       • A = [a1, b1] B = [b1, b2] A.B = [a1xb1 + a2xb2]
     • Convex combination
       • This is a technique that combines two vectors in the form au+bv where a, b >= 0 and a + b = 1
     • Uses
       • Vector graphics
       • Parity bit
         • Using dot product
       • Angle between two vectors
         • Using dot product
     • Representation
       • A dictionary, list or one-dimensional array are useful ways of representing a vector.
       • A list of numbers
       • A function
         • One that maps the ordinal number (index) to a value.

2. 4.1 Fundamentals of Programming

   • 4.1.1 Programming
     • Procedural Programs
       • Data is stored as different types
         • Integer
           • A whole number, positive or negative
         • Real / Float
           • A fractional number, positive or negative
         • Boolean
           • One of two values, such as True and False
         • String
           • A group of characters, stored as ASCII or Unicode
         • Date or time
           • A representation of a date or time
         • Pointer / Reference
           • A link to data elsewhere in memory
         • Record
           • A group of values, which can be of different data types
         • Array
           • An indexed group of values, which are all the same data type
         • List
           • An indexed group of values, which are all the same data type
       • User defined data types can be created
         • Such as records and linked lists of a given type
       • Procedural programs are combinations of statement types
         • Variable declaration
           • Defining a variable and its type, ready to be used. The named value can be changed throughout the program
         • Constant declaration
           • Defining a constant and its type. This named value cannot be changed once assigned
         • Assignment
           • Assigning a value to a previously declared constant or variable
         • Iteration
           • Repeating a section of code based on a given condition
           • Definite
             • A fixed number of repetitions is defined (such as a FOR loop)
           • Indefinite
             • Repeat for as long as a condition is met, potentially infinite (such as a WHILE loop)
         • Selection
           • Branching to a section of code depending on a given condition (IF loops)
         • Subroutine
           • A pre-defined section of code that can be called at any time by the main menu
           • Procedure
             • A subroutine with no output
           • Function
             • A subroutine with an output
       • Can contain nested selection / iteration
         • Where a branch or loop is contained within another branch or loop
       • Can contain identifiers
         • Should be descriptive of the purpose of the value, improving the code's readability
     • Operations
       • Numerical operations
         • These are applied to integer and real values
         • Addition
         • Subtraction
         • Multiplication
         • Division
           • Real division
             • Division of one real value by another, resulting in a decimal value, using the / operator
           • Integer division
             • Division of one integer value by another, resulting in a value and a remainder using the / and % operators
         • Rounding
           • Rounding a value to a given number of decimal places. Rounding to the nearest whole number can be done with Math.round() 
         • Exponentiation
           • Raising one value to the power of another by using Math.pow()
         • Truncation
           • Reducing the accuracy of the value by storing it using fewer bits
       • Bitwise operations
         • These are applied to the binary bits that comprise the value
         • NOT
         • AND
         • OR
         • XOR
       • String operations
         • These are applied to the binary bits that comprise the value
         • Length
           • Returns the number of characters in a string( and also the number of elements in an array)
         • Position
           • Returns the character at a given position, starting at 0
         • Substring
           • Returns the string of characters specified between two specific points
         • Concatenation
           • Appends a string to the end of another and returns the new string
         • Character -> Character code
           • Converts a character to its equivalent ASCII code
         • Character code -> Character
           • Converts an integer to the character represented by that value in ASCII
         • String conversion operations
           • String -> Integer
           • String -> Float
           • Integer -> String
           • Float -> String
           • Date/time -> String
           • String -> Date/time
     • Conditions
       • Conditions compare two values using a comparison operator and return either true or false.
       • Comparison operators
         • Equal to
           • == Returns true if two values are the same
         • Not equal to
           • != Returns true if two values are not the same 
         • Less than
           • < Returns true if the first (left) value is less than the second value (right)
         • Greater than
           • > Returns true if the first (left) value is greater than the second (right)
         • Less than or equal to
           • <= The first (left) value is less than or equal to the second (right) value
         • Greater than or equal to
           • <= Returns true if the first (left) value is greater than or equal to the second (right) value
       • Uses
         • Used in selection to decide which branch to use
         • Used in indefinite iteration to determine whether or not to repeat the loop
     • Procedural Techniques
       • Random number generation
         • A random float between 0 and 1
         • A random integer between 0 and a given maximum
           • Can add the lower bound to this to generate between numbers larger than 0,  e.g.: random.nextInt(5)+8; will generate a random integer between 8 and 13 (not including 13)
       • Exception handling
         • Code within a 'try' block will divert the code to its 'catch' block when a specified exception occurs
           • Runtime errors will be caught by this
           • A 'finally' block can be optionally added after the catch, which will always run regardless of exceptions
             • This can be used to close files and prevent memory leaks
       • Local and global variables
         • Local variables
           • Exist only within the subroutine that they were created in
           • Cannot be accessed or altered by other subroutines
           • Memory is freed up once the subroutine has completed
         • Global variables
           • Exist for the entire running of the program or class
           • Produces a larger memory footprint as memory locations cannot be re-used
           • Are visible / accessible within all subroutines
       • Recursion
         • A subroutine calling itself
         • Can be used to efficiently make multiple calls to different data
         • Can cause memory overflows if conditions for preventing continuous recursion are not implemented
     • Subroutines
       • Uses
         • -To group code together to improve readability -To remove the need for duplicating large chunks of code that are repeatedly called
       • Types
         • -Subroutines exist with or without parameters (arguements) -Subroutines exist with or without returned values (function or procedure)
       • Stack frame
         • Created to store:
           • It is created when a subroutines is run. When the subroutine completes, the stack frame is used to restore the state of the calling routine and continue its execution.
           • Return address
           • Parameters
           • Local variables
   • 4.1.2 Programming Paradigms
     • Object Orientated Paradigm
       • These define classes, create instances of those classes and execute methods within the objects
       • Class
         • "Defines the methods and property / attribute fields that capture the common behaviors and characteristics of objects" A class is a definition of an object - a Cat class could define how to walk, purr and do other functions, and store age, colour and other properties They consist of attributes (variables) and methods (functions)
       • Object
         • "Objects based on a class are created using a constructor, implicit or explicit, and a reference to the object assigned to a reference variable of class type." The object is an instance of a class - Tibbles is an instance of the Cat classMultiple objects can be created from a single class
       • Instantiation
         • The process of creating an instance of a class - for creating an object from a class. e.g.:The Cat class can be instantiated to create Tibbles
       • Encapsulation
         • The technique of keeping a class's attributes and functionality within the class. Good encapsulation means that other emmewledge of how a class works, only that it does
       • Inheritance
         • Creating a class that is an extension of an existing class - the new class will contain all the public functionality of its parent class.  Additions and alterations can be made in the extended class, rather than re-writing the entire class
       • Aggregation
         • An object containing another object as one of its attributes. The functionality of the parent class can use the functionality of its aggregated class
       • Composition
         • A special case of aggregation where the aggregated object is created by its parent class, and therefore does not exist without its parent
       • Polymorphism
         • The ability of a method to behave differently under different circumstances, either through inheritance or overloading
       • Overriding
         • Replacing the parent class's implementation of a method in its extended class
     • Object Orientated Design Principles
       • All the following principles are guidelines that work in many situations - however there are situations where they do not work and others where they can't be followed.
       • Encapsulate what varies
         • -Where possible any variable should be encapsulated within the class or subroutine that they are used -Access to data should be on a need-to-know basis -The "internal workings" of a class or procedure should be hidden - how it works should be known
         • Advantages
           • -It is easier to change the inner workings of a method or class if those workings are hidden - other classes will not be using this class' variables depending on them staying the same. -Development can more easily be distributed among developers if each developer doesn't have to understand how other developers' classes work. -Decomposing problems into smaller, more manageable problems is easier - each solution works independently of the others.
       • Favour composition over inheritance
         • -Where possible, transferring the properties of one class to another should be done using composition instead of inheritance -Instead of making 'cat' extend 'mammal', cat should create a private instance of mammal, which can be used to pass on method calls.
         • Advantages
           • -Easier to test each class using unit testing - each class can be tested separately with composition, but an inherited class can not be tested separately from its parent class. -As only the required methods are used, there will be a lower chance of unintended effects if the parent class is altered -Easier to upgrade or use a new class for the composition than for an inherited parent.
       • Program to interfaces, not implementation
         • -When connecting different pieces of code together, use interfaces rather than directly referencing them -Don't directly alter variables in other classes -Keep attributes private where possible and create 'setters and gettters'
         • Advantages
           • -Allows implementation of programs to be updated while maintaining compatibility -If the interfaces ('setters and getters') still perform the same function, a change in implementation will not affect any other programs. -If a bug is discovered, it can be corrected without having to notify others that use the code.

3. 4.3 Fundamentals of Algorithms

   • 4.3.1 Graph Traversal
     • This is the method of reading the contents of each vertex in a graph. The order in which the vertices are reached depends on the traversal algorithm used.
     • Breadth-first
       • From any given vertex, each adjacent unread vertex is read, before moving to one of first of these vertices and repeating the process.
       • Useful for finding the shortest path between vertices in an unweighted graph.
     • Depth-first
       • From any given vertex, the first unread child node is read until it's end, where it will return to its parent node and traverse to the next child node.
       • Useful for navigating a maze, as it will find a route through the maze quickly, but it won't always be the shortest route.
   • 4.3.2 Tree Traversal
     • Pre-order
       • A depth-first traversal algorithm for traversing a tree. The vertex is read, before exploring each of the adjacent vertices.
       • Used for copying a tree, and producing a prefix expression from a tree.
     • Post-order
       • A breadth-first traversal algorithm for a tree, where each adjacent vertex is explored before reading the current vertex.
       • Used for infix to reverse polish notation conversions, producing a postfix expression from a tree, and emptying a tree.
     • In--order
       • applies to a binary tree, where the left adjacent vertex is explored, then the current vertex is read, followed by the right adjacent vertex.
       • Used in binary search trees, and producing an infix expression from a tree
   • 4.3.3 Reverse Polish Notation
     • infix notation
     • Postfix notation
   • 4.3.4 Searching algorithms
     • Linear search
     • Binary search
     • Binary tree search
   • 4.3.5 Sorting Algorithms
     • Bubble sort
     • Merge sort
   • 4.3.6 Optimisation algorithms
     • Dijkstra's shortest path

4. 4.7 Fundamentals of Computer Organisation and Architecture

   • 4.7.1 Internal hardware components of a computer
     • Processor
     • Main memory
     • Address bus
     • Data bus
     • Control bus
     • I/O controllers
     • Von Neumann vs Harvard
     • Addressable memory
   • 4.7.2 The stored program concept
     • Machine code instructions stored in main memory are fetched and executed serially by a processor that performs arithmetic and logical operations
   • 4.7.3 Structure and role of the processor and its components
     • Arithmetic logic unit
     • Control unit
     • Clock
     • General-purpose registers
     • Dedicated registers
       • Program counter (PC)
       • Current instruction register (CIR)
       • Memory address register (MAR)
       • Memory buffer register (MBR)
       • Status register
     • Fetch-execute cycle
     • Processor instruction set
       • An instruction set that is processor specific
     • Direct & Immediate addressing
     • Interrupts & Interrupt service routines (ISRs)
     • Effect on processor performance
       • Multiple cores
       • Cache memory
       • Clock speed
       • Word length
       • Address bus width
       • Data bus length
   • 4.7.4 External hardware devices

5. 4.4 Theory of Compution

   • 4.4.1 Abstraction and Automation
     • Algorithms
     • Pseudo-code
     • Hand-trace
     • Decomposition
     • Abstraction
     • Automation
   • 4.4.2 Set terminology
   • 4.4.2 Set operations
   • 4.4.2 Regular expressions
   • 4.4.3 Context-free languages
   • 4.4.3 BNF & Syntax diagrams
   • 4.4.4 Classification of algorithms
   • 4.4.5 Turing machine

6. 4.9 Fundamentals of Communication and Networking