A-level Computing/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.
Links to other topics
Stack, queue and list operations
Simple graph traversal algorithms
think of an algorithm that takes a particular map and can traverse every part of it. you will need two flags for each vertex
- Completely explored
You can only say it is fully explored once every vertex has been completely explored
simulates real life and imaginary life. think about computer games. Lets you try things out that you wouldn't be able to in real life for cost / time reasons.
Know how to simulate simple queues