Notes-for-CAIE

4.1 Computational thinking and problem-solving

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

Explain how an insertion sort puts a set of data into ascending order

w20 43 Q5 [4]

• Uses a sorted and unsorted list
• Takes first value and makes it sorted list
• Takes next value and compare with previous one,
• … to find location of next value in the sorted list
• Insert it into correct position in sorted list
• Repeat until all items are in the sorted list

Features that a recursive algorithm must include

s20 43 Q2 [2]

• General case
• Base case
• It calls itself

Pseudocode hints

• Call function: CALL FunctionName()
• Index starts from 0
• Declare array typed Type and sized 100: DECLARE Name : ARRAY[0..99] OF Type
• Assignment is <-

Python hints

• Remainder operator: %
• Devision to int: //

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

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

How stack used during execution of a recursive procedure

s15 43 Q6.b

• Before procedure call is executed current state of the registers/local variables is saved onto the stack
• When returning from a procedure call the registers/local variables are re-instated