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
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
