A-level Computing/AQA/Problem Solving, Programming, Operating Systems, Databases and Networking/Programming Concepts

3 From the Specification : Programming Paradigms Understand the need for and characteristics of a variety of programming paradigms. Structured programming techniques Procedural-oriented programming Event-driven programming Object-oriented programming Object-oriented programming Be familiar with the concept of an object class, an object, instantiation, encapsulation, inheritance. Practical experience of programming using objects to model a simple problem. Recursive Techniques Illustrate the use of recursive techniques in programming language Abstract Data Types / Data Structures Pointer Stacks Lists - Linear lists, Linked lists Queues - linear, circular, priority Graphs Trees Rooted tree Binary trees 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. Compare the use of each. 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/ /Object-oriented programming (OOP)/ /Pointers/ /Recursive Techniques/ /Abstract data types and data structures/ /Stacks/ /Queues/ /Lists/ /Graphs/ Binary trees /Binary search/ /Insertion sort/ /Hashing/ 3 Simulations 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. /Simulations/ Standard Algorithms You should be able to recognise and use trace tables on code that does the following: Binary trees 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 Terminology 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? Efficiency 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. Balance 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. Queue 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 Stack 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: Undiscovered The algorithm has yet to discover this vertex Discovered 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 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.