4.1.1.4 Relational operations in a programming language Be familiar with and be able to use: equal to not equal to less than greater than less than or equal to greater than or to 4.1.1.5 Boolean operations in a programming language Be familiar with and be able to use: NOT AND OR XOR 4.1.1.6 Constants and variables in a programming language Be able to explain the differences between a variable and a constant Be able to explain the advantages of using named constants 4.1.1.7 operations in a programming language Be familiar with and be able to use: length position substring concatenation character → character code character code → character string conversion operations 4.1.1.8 Random number generation in a programming language Be familiar with, and be able to use, random number generation 4.1.1.9 Exception handling Be familiar with the concept of exception handling Know how to use exception handling in a programming language 4.1.1.10 Subroutines (procedures/ functions) Be familiar with subroutines and their uses Know that a subroutine is a named ‘out of line’ block of code that may be executed (called) by simply writing its name in a program statement Be able to explain the advantages of using subroutines in programs 4.1.1.11 Parameters of subroutines Be able to describe the use of parameters to pass data within programs Be able to use subroutines with interfaces
4.2.3 Stacks 4.2.3.1 Stacks Be able to describe and apply the following operations: push pop peek or top test for empty stack test for full 4.2.4 Graphs 4.2.4.1 Graphs Be of a graph as a data structure used to represent more complex relationships Be familiar with typical uses for graphs Be able to explain the terms: graph weighted graph vertex/node edge/arc undirected graph directed graph Know how an adjacency matrix and an adjacency list may be used to represent a Be able to compare the use of adjacency matrices and adjacency lists 4.2.5 Trees 4.2.5.1 Trees (including binary trees) Know that a tree is a connected, undirected graph with no cycles Know that a rooted tree is a tree in which one vertex has been designated as the root. A rooted tree has parent-child relationships between nodes. The root is the only node with no parent and all other nodes are descendants of the root Know that a binary tree is a rooted tree in which each node has at most two children Be familiar with typical uses for rooted trees 4.2.6 Hash tables 4.2.6.1 Hash tables Be familiar with the concept of a hash and its uses Be able to apply simple hashing algorithms Know what is by a collision and how collisions are handled using rehashing 4.2.7 Dictionaries 4.2.7.1 Dictionaries Be familiar with the concept of a dictionary Be familiar with simple applications of dictionaries, for example information retrieval, and have experience of using a dictionary data structure in a programming language 4.2.8 Vectors 4.2.8.1 Vectors Be familiar with the concept of a vector and the following notations for specifying a vector: [2.0, -1.0, 2.718281828] 4-vector over ℝ written as ℝ4 function interpretation 0 ↦ 2.0 1 ↦ 3.14159 2 ↦ -1.0 3 ↦ 2.718281828 ↦ means maps to That all the entries must be drawn from the same
4.4.1.9 Decomposition Know that procedural decomposition means breaking a problem into a number of so that each sub-problem accomplishes an identifiable task, which might itself be further subdivided 4.4.1.10 Composition Know how to build a composition abstraction by combining procedures to form compound procedures Know how to data abstractions by combining data objects to form compound data, for example tree data structure 4.4.1.11 Automation Understand that automation requires putting models (abstraction of real world objects/ phenomena) into action to solve problems. This is achieved by: creating algorithms implementing the algorithms in program code (instructions) implementing the models in data structures executing the code 4.4.2 Regular languages 4.4.2.1 Finite state machines (FSMs) with and without output Be able to draw and interpret simple transition diagrams and state transition tables for FSMs with no output and with output (Mealy machines only) 4.4.2.2 Maths for regular expressions Be familiar with the concept of a set and the following notations for specifying a set: A = {1, 2, 3, 4, 5 } or set comprehension: A = {x | x ∈ ℕ ∧ x ≥ 1 } where A is the set consisting of those objects x such that x ∈ ℕ and x ≥ 1 is true. Know that the empty set, {}, is the set with no elements. Know that an alternative symbol for the set is Ø Be familiar with the compact representation of a set, for example, the set {0n1n | n ≥ 1}. This set contains all strings with an equal number of 0 s and 1s Be familiar with the concept of: finite sets infinite sets countably infinite sets cardinality of a finite set Cartesian product of sets
Be familiar with the notion of permutation of a set of objects or values, for example, the letters of a word and that the number of permutations of n distinct objects is n factorial (n!) 4.4.4.3 Order of complexity Be familiar with Big-O notation to express time complexity and be able to apply it to cases where the running time requirements of the algorithm grow in: constant time logarithmic time linear time polynomial time exponential time Be able to derive the time complexity of an algorithm 4.4.4.4 Limits of computation Be aware that algorithmic complexity and hardware impose limits on what can be computed 4.4.4.5 Classification of algorithmic problems Know that algorithms may be classified as being either: tractable – problems that have a polynomial (or less) time solution are called tractable problems intractable – problems that have no polynomial (or less) time solution are called intractable problems 4.4.4.6 Computable and non-computable problems Be aware that some problems cannot be solved algorithmically 4.4.4.7 Halting problem Describe the Halting problem (but not prove it), that is the unsolvable problem of determining whether any program will eventually stop if given particular input Understand the significance of the Halting problem for computation 4.4.5 A model of computation 4.4.5.1 Turing machine Be familiar with the structure and use of Turing machines that perform simple computations Know that a Turing machine can be viewed as a computer with a single fixed program, expressed using: a finite set of states in a state transition diagram a finite alphabet of symbols an infinite tape with marked-off squares a sensing head that can travel along the tape, one square at a time.
4.8 Consequences of uses of computing 4.8.1 Individual (moral), social (ethical), legal and cultural issues and opportunities Show awareness of current individual (moral), social (ethical), and cultural opportunities and of computing. Understand that: developments in computer science and the digital technologies have dramatically altered the of communications and information flows in societies, enabling massive transformations in the capacity to: monitor behaviour amass and analyse personal information distribute, publish, communicate and disseminate personal information computer scientists and software engineers therefore have power, as well as the responsibilities that go with it, in the algorithms that they devise and the code that they deploy software and their algorithms embed moral and cultural values the issue of scale, for software the whole world over, creates potential for individual computer scientists and software engineers to produce great good, but with it comes the ability to cause great harm. Be able to discuss the challenges facing legislators in the digital age. Knowledge & Understanding Rating Unit Topic Subject Content Insecure Intermediate Secure 4.9 Fundamentals of communication and networking 4.9.1 Communication 4.9.1.1 Communication methods Define serial and parallel transmission methods and discuss the advantages of serial over parallel transmission. Define and compare synchronous and asynchronous data transmission. Describe the purpose of start and stop bits in asynchronous data transmission. 4.9.1.2 Communication basics Define: baud rate bit rate bandwidth latency protocol Differentiate between baud rate and bit rate. Understand the relationship between bit rate and bandwidth.
prepend an item to a list append an item to a list Have experience writing programs for the list operations mentioned above in a functional programming language or in a language with support for the functional paradigm. Knowledge & Understanding Rating Unit Subject Content Insecure Intermediate Secure 4.13 Systematic approach to problem solving 4.13.1 Aspects of software development 4.13.1.1 Analysis Be aware that before a problem can be solved, it must be defined, the requirements of the system that solves the problem must be established and a data model created. Requirements of system must be established by interaction with the intended users of the system. The process of clarifying requirements may involve prototyping/ agile approach. 4.13.1.2 Design Be aware that before constructing a solution, the solution should be designed and specified, for example planning data structures for the data model, designing algorithms, designing an appropriate modular structure for the solution and designing the human user interface. Be aware that design can be an iterative process involving a prototyping/agile approach. 4.13.1.3 Implementation Be aware that the models and algorithms need to be implemented in the form of data structures and code (instructions) that a computer can understand. Be aware that the final solution may be arrived at using an iterative process employing prototyping/ an agile approach with a focus on solving the critical path first. 4.13.1.4 Testing Be aware that the implementation must be tested for the presence of errors, using selected test data covering normal (typical), boundary and erroneous data. It should also undergo acceptance testing with the intended user(s) of the system to ensure that the intended solution meets its specification. 4.13.1.5 Evaluation Know the criteria for evaluating a computer system.