A-level Computing 2009/AQA/Problem Solving, Programming, Operating Systems, Databases and Networking/Programming Concepts
Understand the need for and characteristics of a variety of programming paradigms.
Abstract Data Types / Data Structures
Be familiar with the concept of a list, a tree, a queue, a stack, a pointer and be familiar with the data structures and methods for representing these when a programming language does not support these structures as built-in types. Distinguish between static and dynamic structures and compare their uses. Use of free memory, the heap and pointers Be aware of a graph as a data structure to represent more complex relationships. Explain the terms graph, labelled graph, unlabelled graph, vertex, edge, digraph and arc. Know how an adjacency matrix and an adjacency list may be used to represent a graph.
A tree is a connected undirected graph with no cycles. A rooted tree is a tree in which one vertex has been designed as the root and every edge is directed away from the root.
- Programming paradigms
- Recursive Techniques
- Abstract data types and data structures
- Binary search
- Insertion sort
Be familiar with a simulation as a computer program or network of computers that attempts to simulate a model of a particular system.
Know that computer simulations can represent real and imaginary situations. Know that simulations allow users to study or try things that would be difficult or impossible to do in real life. Be familiar with simple simulation techniques involving queues.
You should be able to recognise and use trace tables on code that does the following:
A binary tree can be defined recursively as
- an empty tree, containing no nodes or
- a node, called the root, usually containing some data, with at most 2 subtrees, each of which is itself a binary tree
Node - a part of the tree holding some data
Branches - connections between nodes
Root - the node that has no parent, i.e., is at the top of the tree
Leaf - a node that has no subtrees, i.e., is at the bottom of the tree
Parent - a node that is connected to the root of a subtree
Level - all the nodes that are at the same depth in the tree, i.e., there are the same number of branches to get 'back to' the root, are at the same level. The root is at level 0
Child - the root of a subtree that is connected 'upwards' to its parent
Sibling - the next node at the same level
Binary tree search
Thinking of any particular binary tree, how many searches will it take to find a certain item?
Thinking of any particular binary tree, how many searches will it take to find a certain item (in the best and worst cases) if the tree has n nodes?
Does the number of searches (in both cases) differ depending on whether the item is in the tree or not?
Does the number of searches (in both cases) depend on the structure of the tree?
What is the worst case? What is the best case?
A binary tree has n items in it, and takes s searches (in the worst case) to find an item. If another n items are added to the tree how many searches will it need to find an item (in the worst case) if the tree is perfectly balanced, i.e., each node (apart from the leaf nodes) has two subtrees.
A perfectly balanced binary tree is one where every node, has 0 or 2 subtrees. The leaves have 0 subtrees, and the 'internal' nodes each have 2.
Stack, queue and list operations
Queue - FIFO Stack - LIFO
Simple graph traversal algorithms
(see: AQA supplementary materials, document called: 'Unit guide: COMP3 - Graph traversals')
A graph traversal algorithm aims to 'explore' every vertex.
If the algorithm is searching for a particular vertex (eg. the exit to a maze) then it considers whether each vertex is the one it is looking for.
After evaluation, if it has not found what it was looking for, the algorithm adds every vertex adjacent to the current one onto a 'list' of vertices to visit next.
The type of structure used to store this 'list' of vertices determines how the algorithm moves through the graph.
- FIFO (first in, first out)
- siblings are processed before their children
- 'Breadth-first traversal'
- all vertices on the same level are processed before moving to the next level
- LIFO (last in, first out)
- children are processed before the siblings of the current vertex
- 'Depth-first traversal'
These algorithms also have to keep track of the state of each vertex:
- The algorithm has yet to discover this vertex
- A vertex is discovered once the algorithm has evaluated the vertex, and added its children to the list of vertices to visit. However not all of them have been evaluated yet
- Completely explored/Processed
- All adjacent vertices have been discovered
Simulations model real and imaginary situations. They may be used to test scenarios that wouldn't be feasible in real life for cost or time reasons. Many computer games could be considered simulations.
You should know how to simulate simple queues.