# A-level Computing/CIE/Further Problem Solving and Programming skills/Computational thinking and problem-solving

* 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