|
Specification link
4.1.1 Abstraction
- show understanding of how to model a complex system by only including essential details, using:
- functions and procedures with suitable parameters (as in imperative programming, see Section 2.3)
- ADTs (see Section 4.1.3)
- classes (as used in object-oriented programming, see Section 4.3.1)
- facts, rules (as in declarative programming, see Section 4.3.1)
4.1.2 Algorithms
- write a binary search algorithm to solve a particular problem
- show understanding of the conditions necessary for the use of a binary search
- show understanding of how the performance of a binary search varies according to the number of data items
- write an algorithm to implement an insertion sort
- write an algorithm to implement a bubble sort
- show understanding that performance of a sort routine may depend on the initial order of the data and the number of data items
- write algorithms to find an item in each of the following: linked list, binary tree, hash table
- write algorithms to insert an item into each of the following: stack, queue, linked list, binary tree, hash table
- write algorithms to delete an item from each of the following: stack, queue, linked list
- show understanding that different algorithms which perform the same task can be compared by using criteria such as time taken to complete the task and memory used
4.1.3 Abstract data types (ADT)
- show understanding that an ADT is a collection of data and a set of operations on those data
- show understanding that data structures not available as built-in types in a particular programming language need to be constructed from those data structures which are built-in within the language
TYPE <identifier1>
DECLARE <identifier2> : <data type>
DECLARE <identifier3> : <data type>
…
ENDTYPE
- show how it is possible for ADTs to be implemented from another ADT
- describe the following ADTs and demonstrate how they can be implemented from appropriate built-in types or other ADTs: stack, queue, linked list, dictionary, binary tree
Stack
- describe and demonstrate how this ADT can be implemented from appropriate built-in types or other ADTs
- Write algorithms to:
- find an item
- insert and item
- delete an item
Queue
- describe and demonstrate how this ADT can be implemented from appropriate built-in types or other ADTs
- Write algorithms to:
- find an item
- insert and item
- delete an item
Linked list
- describe and demonstrate how this ADT can be implemented from appropriate built-in types or other ADTs
- Write algorithms to:
- find an item
- insert and item
- delete an item
Dictionary
- describe and demonstrate how this ADT can be implemented from appropriate built-in types or other ADTs
- Write algorithms to:
- find an item
- insert and item
- delete an item
Binary tree
- describe and demonstrate how this ADT can be implemented from appropriate built-in types or other ADTs
- Write algorithms to:
- find an item
- insert and item
- delete an item
4.1.4 Recursion
- show understanding of the essential features of recursion
- show understanding of how recursion is expressed in a programming language
- trace recursive algorithms
- write recursive algorithms
- show understanding of when the use of recursion is beneficial
- show awareness of what a compiler has to do to implement recursion in a programming language
|
