Computer Science Paper 1

AQA Vocabulary Sheet

Define: Data type

Determines what type of value a variable will hold and the set of operations allowed.

Define: Pointer/Reference

A pointer is an object that stores a memory address.

Define: Records

A composite data structure which allows for a collection of fields to be grouped together.

Define: Arrays (lists)

A collection of elements, each accessed using an index and all elements must be of the same data type.

Define: User-defined data type

A custom data type created by the user combining existing data types.

Define: Variable

An identifier that represents a memory location that can store a value. This value can change during execution of a program.

Define: Constant

An identifier that represents a memory location that can store a value. This value cannot change during execution of a program.

Define: Assignment

A statement that sets the value of a variable/constant.

Define: Iteration

Iteration is the repetition of a block of code.

Define: Definite iteration

Definite iteration is the repetition of a block of code for a set number of times. An example structure is a FOR loop.

Define: Indefinite iteration

The repetition of a block of code being controlled by a condition. The number of iterations to be performed is not known when entering the block of code.

Define: Selection

Allows blocks of code to be executed only when a certain condition is satisfied.

Define: Nested (selection/iteration)

When an iteration/selection statement appears inside another iteration/selection statement it is considered nested.

Why are meaningful identifier names important?

Makes the code easier to understand and maintain as the name should describe the purpose of the variable or subroutine.

Define: Integer remainders

While integer division discards the remainder, this can still be a useful value. The remainder can be obtained by using the modulo operator.

Define: Exponentiation

refers to the repeated multiplication of a base number by a certain amount of times (the power).

Define: Rounding

Rounding refers to replacing a number with an approximate simpler value. This is often a whole number but could be a number with a fixed number of decimal places.

Define: Truncation

Truncation refers to shortening something. It usually refers to removing digits from a number.

Define: Exception handling

A programming mechanism that allows a graceful response to errors or events during the runtime of the program that would have caused the program to crash.

Define: Subroutine (procedure/function)

A named ‘out of line’ block of code that may be executed by simply writing its name in a program statement. It can be reused multiple times within a program.

Define: Parameter (of subroutine)

Parameters define the data to be passed to a subroutine.

Define: Subroutines with interfaces

A subroutine interface is the method of passing data in and out of a subroutine.

Define: Local variable

Variables that are declared within a subroutine, they exist only while a subroutine is executing and are accessible only from within the subroutine.

Define: Global variable

A variable with global scope, meaning it can be accessed from anywhere within the program.

Define: Stack frame

A stack frame is a portion of the stack memory used with subroutine calls to store: return address; parameters; local variables. A stack frame allows us to move to a subroutine call and then return to where we were called from and carry on.

Define: Recursion

A recursive subroutine is one that has a call to itself as part of its execution.

Define: Base case

A base case is a value that will not cause a recursive call and therefore allow the recursion to complete (and backtrack).

Define: Programming paradigm

A programming paradigm is a particular approach to writing programs.

Define: Procedural

A programming approach that is based on the use of procedures and functions.

Define: Structured approach to program design

Breaking down problems into sub-problems so that code is then organised into subroutines.

Define: Hierarchy chart

A diagram that represents the structure of a program. Each subroutine is shown as a rectangle and the hierarchy shows how subroutines are called from others.

Define: Object-oriented

The object-oriented paradigm makes use of objects as containers of both properties and methods.

Define: Class

Defines methods and property/attribute fields that capture the common behaviours and characteristics of objects.

Define: Object

A structure that combines data and the procedures necessary to operate on that data.

Define: Instantiation

Creating an instance of a class (creating an object from a class).

Define: Encapsulation

Combining of properties and methods together into a class where the way in which the data is stored and the way that methods are carried out is hidden from other classes.

Define: Inheritance

The relationship between two object types in which one is a kind of the other and shares some of its properties or behaviours.

Define Association and give the two type of Association

A relationship between two classes - Composition and Aggregation

Define: Aggregation

A type of association where the aggregated object has a weaker form of association with the objects that it is aggregating than is the case with composition. These objects have an existence independent of the aggregated object and can continue to exist even after the aggregated object is disposed of.

Define: Composition

A type of association where the relationship is stronger. If the containing object is destroyed, the associated object is also destroyed.

Define: Polymorphism

The concept that different objects can respond to the same method call in different ways based on their class.

Define: Overriding

An overridden method has the same name as a method from an inherited class but a different implementation.

Define: Encapsulate what varies

The separation of code that might need to be constantly changed. Areas of code that might need to be changed can be encapsulated behind an interface. Then, when any changes are needed, software written to use the interface does not need to be changed.

Define: Favour composition over inheritance

The principle that programmers should look to use composition over inheritance when looking at concepts such as polymorphism.

Define: Program to interfaces, not implementation

The principle that programmers should look to communicate between parts of a program by using an interface rather than the knowledge of an implementation.

Define: Class diagram

A class diagram shows the relationship between classes in a program. Class diagrams involve single inheritance, composition (black diamond line), aggregation (white diamond line), public (+), private (-) and protected (#) specifiers.

Define: Data structure

Allows for a collection of data to be organised and processed.

Define: Single- and multi-dimensional arrays (lists)

An array is a data structure that holds a number of elements of the same data type. A single-dimensional array is like a single row of values. A two-dimensional array is like a table of values.

Define: Binary file

A binary file is a file whose binary content must be interpreted by a program or processor that can identify how the data is formatted. Generally, any non-text file, such as an executable, image or movie.

Define: Text file

A text file is a file whose content is characters encoded from a character set, with a new line character being used to separate lines.

Define: Abstract data type

A model of a data type that is defined in terms of its behaviour and operations without specifying how these are implemented.

Define: Queue

A data structure that follows the first in, first out (FIFO) principle.

Define: Enqueue

The concept of adding an element to the rear of a queue.

Define: Dequeue

The concept of removing an element from the front of a queue.

Define: Linear queue

A linear data structure where elements are added to the rear of the queue and are removed from the queue at the front, following the FIFO principle.

Define: Circular queue

A queue implemented using an array such that when the rear pointer reaches the end of the array it can wrap around to reuse empty spaces at the beginning of the array.

Define: Priority queue

Each element of a priority queue has an associated priority. Elements are dequeued in order of priority and, where two elements have the same priority, elements that were added first are removed first.

Define: Stack

A stack is a data structure that follows the last in, first out (LIFO) principle.

Define: Push

The concept of adding an element to the top of a stack.

Define: Pop

The concept of removing an element from the top of a stack.

Define: Peek

The concept of looking at the element at the top of a stack.

Define: Graph

A diagram consisting of vertices joined by edges.

Define: Weighted graph

When values are associated with the edges on a graph.

Define: Directed graph

A diagram consisting of nodes joined by directed edges.

Define: Connected graph

If there is always a path between any two nodes in a graph it is said to be connected.

Define: Adjacency matrix

An adjacency matrix is a 2D array that records the relationship between nodes in a graph. For a graph with n nodes, we create an n by n adjacency matrix.

Define: Adjacency list

An adjacency list is a list of all nodes and for each node we record neighbouring nodes.

Define: Tree

A tree is a connected, undirected graph with no cycles.

Define: Rooted tree

A tree in which one node has been designated as the root. A rooted tree has a parent-child relationship between nodes. The root is the only node with no parent and all other nodes are descendants of the root.

Define: Binary tree

A binary tree is a rooted tree in which each node has at most two children. A common application of a binary tree is as a binary search tree.

Define: Hash table

A hash table is a data structure that creates a mapping between keys and values.

Define: Collision

A collision occurs when two key values compute the same hash.

Define: Dictionary

A collection of key-value pairs in which the value is accessed via the associated key.

Define: Vector

A quantity having direction as well as magnitude.

Define: Vector addition

Adding each corresponding element of two vectors together to generate a new vector. Vector addition achieves translation.

Define: Scalar vector multiplication

The multiplication of a scalar and a vector generates a new vector which is made by multiplying the scalar value against each of the components of the vector. Vector multiplication achieves scaling.

Define: Convex combination of two vectors, u and v

Is an expression of the form α u + β v where α, β ≥ 0 and α + β = 1.

Define: Dot product of two vectors

The dot product of two vectors, u and v, u = [u1, …, un] and v = [v1, …, vn] is u ∙ v = u1v1 + u2v2 + …… + unvn.

Define: Static data structure

The size of a static data structure is fixed and the memory required to store the data structure is determined before runtime.

Define: Dynamic data structure

The size and memory taken up by a dynamic data structure can vary while a program is running.

Define: Heap

Heap memory is a region of memory used for dynamic allocation. As programs request memory they can be allocated memory from the heap.

Define: Graph traversal

A graph traversal is the process of visiting each node in a graph.

Define: Breadth first search

A graph traversal algorithm which makes use of a queue, it visits all nodes on the same level before moving on to the next level. It can be used to find the shortest path for an unweighted graph.

Define: Depth first search

Depth first search is a graph traversal algorithm which makes use of a stack. A depth first search proceeds down through a node branch as far as possible before backtracking. Application: navigating a maze.

Define: Tree traversal

Visiting each node in a tree.

Define: Pre-order traversal application

Pre-order: Copying a tree.

Define: In-order traversal application

Outputting the contents of a binary search tree in ascending order.

Define: Post-order traversal application

Post-order: Infix to RPN conversions, producing a postfix expression from an expression tree, emptying a tree.

Define: Infix notation

Infix notation is the standard way of writing mathematical expressions where the operators are placed between their operands.

Define: Prefix notation

A way of writing mathematical expressions where the operators precede their operands.

Define: RPN – Reverse Polish Notation

A form of mathematical notation where operators follow operands and is also known as postfix form. There is no need for brackets when using RPN and there is also no need for the concept of operator precedence.

Define: Linear search – O(n)

An algorithm that sequentially checks each element in an array or list until a match is found or the end is reached.

Define: Binary search – O(log n)

An algorithm that compares a search item to the middle item of an array or list. If they do not match, half of the array or list can be eliminated and the search continues in the other half. The array or list needs to be sorted so that a binary search can be performed.

Define: Binary tree search – O(log n)

A binary tree that is ordered allows for the use of a binary tree search algorithm. This is similar in principle to a binary search and we compare our search item to the root node. If they do not match, we can eliminate one half of the tree and the search can continue in the other half. If the tree is balanced, it has a complexity of O(log n).

Define: Bubble sort – O(n2)

A bubble sort works by making passes through the array or list. While making a pass we compare neighbours and swap them if they are out of order. After a series of passes the array or list will be sorted.

Define: Merge sort – O(nlog n)

The merge sort is a divide-and-conquer algorithm. The original array or list is broken down into smaller and smaller parts until we have individual elements. The merge sort continues by building back sorted groups until we end with the full sorted result.

Define: Dijkstra’s shortest path

Dijkstra’s shortest path algorithm works as a means of finding the shortest path for a whole set of nodes. It finds the shortest path from a start node to all other nodes in a graph.

Define: Algorithm

A sequence of steps that can be followed to complete a task and that always terminates.

Define: Abstraction

The process of removing unnecessary details from a problem.

Define: Representational abstraction

Removing unnecessary details.