• Show understanding of linear and binary searching methods

  • Write an algorithm to implement a linear search

  • Write an algorithm to implement a binary search

  • The conditions necessary for the use of a binary search

  • How the performance of a binary search varies according to the number of data items

• Show understanding of insertion sort and bubble sort methods

  • Write an algorithm to implement an insertion sort

  • Write an algorithm to implement a bubble sort

  • Performance of a sorting routine may depend on the initial order of the data and the number of data items

• Show understanding of and use Abstract Data Types (ADT)

  • Write algorithms to find an item in each of the following: linked list, binary tree

  • Write algorithms to insert an item into each of the following: stack, queue, linked list, binary tree

  • Write algorithms to delete an item from each of the following: stack, queue, linked list

  • Show understanding that a graph is an example of an ADT. Describe the key features of a graph and justify its use for a given situation

    • Candidates will not be required to write code for this structure

• 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

• Show understanding that different algorithms which perform the same task can be compared by using criteria (e.g. time taken to complete the task and memory used)

  • Including use of Big O notation to specify time and space complexity

The textbook has a good section (Chapter 23 Langfield and Duddell ) on the different algorithms. This page will add, rather than replace that information.

Here is my implementation of the bubble sort in VB,NET (from lesson 4).  I have also included an output of the elements following the sort.

Dim Array() = {33, 6, 5, 8, 3, 11, 1}

Dim OuterLoop, InnerLoop, Temp, Length As Integer

Length = Array.Length

For OuterLoop = Length - 1 To 1 Step -1

     For InnerLoop = 0 To OuterLoop - 1

         If Array(InnerLoop) > Array(InnerLoop + 1) Then  ' Compare elements

             Temp = Array(InnerLoop)

             Array(InnerLoop) = Array(InnerLoop + 1)

             Array(InnerLoop + 1) = Temp

         End If

     Next InnerLoop

 Next OuterLoop

For Each a As Integer In Array

     Console.WriteLine(a)

Next

Console.ReadLine()

The textbook on page 149 gives a more improved version of the algorithm that replaces the outer loop with a WHILE loop that ends execution once the inner loop completes without making any swaps.  Try and re-create this with the code above.

Here is my implementation in VB of the insertion sort.

Dim Array() As Integer = {15, 8, 22, 43, 5, 9, 11, 3}

Dim iLoop, j, Element As Integer

For iLoop = 1 To Array.Length - 1

    Element = Array(iLoop)

    j = iLoop

    While j > 0 AndAlso Array(j - 1) > Element

        Array(j) = Array(j - 1)

        j = j - 1

    End While

    Array(j) = Element

Next iLoop

For Each num As Integer In Array

    Console.WriteLine(num)

Next

Console.ReadLine()

Another insertion sort VB video

Insertion Sort Videos

These are two videos from Kevin Drumm.  You can follow through to the video to watch the other videos in his series.

This Computerphile video shows how stacks and pointers are used for managing subroutines.

Stack Algorithms

CIE sometimes uses two pointers for stacks, this assumes one will be used to indicate the current top of stack.  Using one pointer assumes that the base of stack pointer is simply the first element in the structure (e.g. array).  In addition, stacks generally do not implement circular references, as queues do.  We'll also assume any structures have a lower bound of 1, not 0.

Inserting an item onto a stack (pushing)

• 1. Check if stack is not full (there is space available).  E.g. TopOfStack < array length

  2. Increment TopOfStack

  3. Insert item at current TopOfStack position

IF ToS = ARRAY.LENGTH THEN

    OUTPUT "STACK FULL"

ELSE

    ToS <-- ToS + 1

    ARRAY[ToS] <-- ITEM

ENDIF

Removing an item from a stack (popping)

• 1. Check that stack is not empty.  E.g. TopOfStack <> NULL

  2. Return item at TopOfSTack, or output it,etc.

  3. Decrement TopOfStack (if the only item, this would now indicate the stack is empty)

IF ToS = 0 THEN

    OUTPUT "STACK EMPTY"

ELSE

    ITEM <-- ARRAY[ToS]

    ToS <-- ToS - 1

    RETURN ITEM

ENDIF

Stack Code

The worksheet requires you to use my existing class code to implement a basic stack.  The code is below.  The worksheet (found at the bottom of the page in the files section) will also ask you to extend the functionality of the class.

Class myStack

        Private sta() As String ' array used to simulate memory - we will not use element 0 to keep things simple

        Private BottomOfStackPointer As Integer ' represents a pointer indicating the start of the stack in memory (in our case, the array)

        Private TopOfStackPointer As Integer ' top of stack pointer

        Private StackTop As Integer = 20 ' sets the upper stack limit

        Public Sub New()

            ' constuctor procedure to initialise the stack

            ReDim sta(StackTop)

            TopOfStackPointer = 0 ' indicates nothing in stack

            BottomOfStackPointer = 1 ' the bottom of the stack

        End Sub

        Public Function Peek() As String

            ' will let the user view (without popping) the top of stack

            If isEmpty() Then

                Throw New Exception("Stack is empty!")

            Else

                Return sta(TopOfStackPointer)

            End If

        End Function

        Public Function Pop() As String

            ' pops the stack

            If isEmpty() Then ' the stack is empty

                Throw New Exception("Stack is empty!") ' generate an exception

            Else

                Pop = sta(TopOfStackPointer)

                TopOfStackPointer -= 1

            End If

        End Function

        Public Sub Push(Item As String)

            ' push an item onto the stack

            TopOfStackPointer += 1

            sta(TopOfStackPointer) = Item

        End Sub

        Public Function Size() As Integer

            ' returns the number of items stored in the stack

            Return TopOfStackPointer

        End Function

        Public Function isEmpty() As Boolean

            Return TopOfStackPointer < BottomOfStackPointer ' evaluate expression and return Bool result

        End Function

End Class

Here is the code that uses the class.  Both of these should be pasted within your Module 1 region.  The code is basic and you should definitely attempt to test it more thoroughly.  

Dim N As New MyStack

Console.WriteLine("# items: " & N.Size)

N.Push("Hello")

Console.WriteLine("# items: " & N.Size)

Console.WriteLine("peek: " & N.Peek)

Console.WriteLine("pop: " & N.Pop)

Console.WriteLine("# items: " & N.Size)

Console.WriteLine("pop: " & N.Pop)

Console.ReadKey()

Queue Algorithms

CIE sometimes uses two pointers for queues, and always if implementing a circular queue (which is often the examiner's preferred structure).  In addition, as with stacks, we'll assume any structures have a lower bound of 1, not 0.  The two pointers are the head or FrontOfQueue pointer and the tail or EndOfQueue pointer.  Due to the circular nature of this implementation, checking for a full queue is not as simple as with a stack.

Inserting an item into a queue (enqueuing)

• 1. check if the queue full (see pseudocode)

  2. If not, check if queue is empty

  3. If it is, set both pointers to start of array

  4. If not, check if EndOfQueue pointer is at end of structure, if so, set EndOfQueue to start

  5. Otherwise, increment EndOfQueue by 1

  6. Insert new item at EndOfQueue position in array

IF (FoQ = 1 AND EoQ = ARRAY.LENGTH) OR (FoQ = EoQ + 1) THEN

    OUTPUT "Overflow! Queue Full"

ELSE

    IF EoQ = NullPointer THEN // Queue empty

        FoQ <-- 1

        EoQ <-- 1

    ELSEIF EoQ = ARRAY.LENGTH THEN // wrap around to front

        EoQ <-- 1

    ELSE

        EoQ <-- EoQ + 1

    ENDIF

    ARRAY[EoQ] <-- ITEM

ENDIF

Removing an item from a queue (dequeuing)

• 1. Check if queue is empty

  2. If not, output item

  3. Determine if this was last item, if so, set EndOfQueue and FrontOfQueue to null

  4. If not, check if FrontOfQueue is at end of array, and wrap back to 1 if so

  5. Otherwise, increment FrontOfQueue by 1

IF FrontOfQueue = NullPointer THEN // Queue empty

    OUTPUT "Queue Empty"

ELSE

    ITEM <-- ARRAY[FoQ]

    IF FoQ = EoQ THEN // Last item in queue

        FoQ <-- NullPointer

        EoQ <-- NullPointer

    ELSEIF FoQ = ARRAY.LENGTH THEN // Need to wrap around to start

        FoQ <-- 1

    ELSE

        FoQ <-- FoQ + 1

    ENDIF

    RETURN ITEM

ENDIF

Linked lists are a fairly standard topic and both the lesson PowerPoint and textbook give enough background to get you started.  Therefore, this section will offer additional reading on the topic.

The following Wikibooks site gives detail on both linear lists and linked lists.

Stanford University have produced a document on problems with linked lists.  This is additional reading and not required for the specification.

Finally, the MSDN website has information on the actual linked list class available from the .NET platform.

The following video is one of a series looking at linked lists in VB.NET.  Only the first video is given below.

From the same author as the linked list video, this goes into detail (ignore traversal, this is not in the CIE spec) on binary trees.  This video too is only one of a series of videos on binary trees.

Algorithms

A binary tree is an ordered data structure. Another consideration when dealing with binary trees, is the grouping of the data and pointer (as these are not stored in a contiguous manner), as with a linked list.  To accommodate this, as with linked lists, we create a user-defined data type (UDT) to hold the data and the two pointers (left and right sub-tree).

When implementing binary trees in arrays, not only do we need to consider which node is the starting node (as you would using other methods), but also which elements are free for use (using the left pointer). Two external pointers are used:  StartPointer and FreePointer.  The NullPointer is used to signify the end of the chain, or that the list is either empty or full.

A binary tree can be seen as a linked list, with each node chaining to successive nodes.

Initialising a binary tree

Sometimes, exam questions will ask you to initialise a linked list or binary tree, etc. This is a simple task whereby all items in the array (usually the preferred underlying data structure) are chained together to form a linked list of free nodes. The StartPointer is set to the NullPointer value and the FreeListPointer set to the first item in the array. The final item in the array has its left pointer set to NullPointer so as to indicate the end of the list.

An example of initialisation and declarations can be found in the 2015 CIE A Level book on page 330 and copied below for reference. This assumes an array with 7 elements. You can use array length to make this generic, or adapt as necessary.

// NullPointer should be set to -1 if using array element with index 0

CONSTANT NullPointer = 0

// Declare record type to store data and pointers

TYPE TreeNode

    DECLARE Data : STRING

    DECLARE LeftPointer : INTEGER // we only need LeftPointer to set up free list

    DECLARE RightPointer : INTEGER

ENDTYPE

DECLARE RootPointer : INTEGER

DECLARE FreePtr : INTEGER

DECLARE Tree[l : 7] OF TreeNode

PROCEDURE InitialiseTree

    RootPointer <-- NullPointer // set start pointer

    FreePtr <-- 1 // set starting position of free list

    FOR Index = 1 TO 6 // link all nodes to make free list

        Tree[Index].LeftPointer <-- Index + 1

    ENDFOR

    Tree[7].LeftPointer <-- NullPointer // last node of free list

END PROCEDURE

Searching a binary tree

Searching can be done recursively or non-recursively. However, with each node having two pointers, the search technique is slightly different to that of a linked list.  However, given that binary trees are ordered, deciding which sub-tree to traverse is a simple decision. 

The structured English below is more verbose, so you can follow the logic of searching a binary tree. 

• 1. Start at the root node and set as the current node

  2. Repeat

     1. IF search data = node's data value then 

        1. Return position, etc.

     2. ELSE

• • • 1. If search data value is greater than the node's value

         1. Does RightPointer = NullPointer

            1. Item not found

         2. ELSE

• • • • • 1. set right sub-tree as current node

• • • 2. Otherwise, follow left

• • • • 1. Does LeftPointer = NullPointer

           1. Item not found

        2. ELSE

• • • • • 1. set left sub-tree as current node

The above can simplify the checking for NullPointers by only looping while the current node is not NULL.  This example is taken from the CIE textbook (p331).

FUNCTION FindNode(Searchitem) RETURNS INTEGER // returns pointer to node

    ThisNodePtr <-- RootPointer // start at the root of the tree

    WHILE ThisNodePtr <> NullPointer // while there's a pointer to follow

    AND Tree[ThisNodePtr].Data <> Searchitem // and search item not found

        IF Tree[ThisNodePointer].Data > Searchitem THEN // follow left pointer

            ThisNodePtr <-- Tree[ThisNodePointer].LeftPointer

        ELSE // follow right pointer

            ThisNodePtr <-- Tree[ThisNodePointer].RightPointer

        ENDIF

    ENDWHILE

    RETURN ThisNodePointer // will return null pointer if search item not found

END FUNCTION

Inserting into a binary tree

inserting a node must take account of position, which involves navigating around the tree until there is a leaf node (a node with no children) or a node with a null pointer at the position that will then have the new node added.  This can be done recursively, so ensure you understand the procedure, as the exam could go either way lately.

You can also find another example taken from the 2015 textbook on page 331.

Structured English

• 1. Check that there is room in the structure for a new node, if so

  2. Add data to node indicated by FreePointer

  3. Set FreePointer by assigning the pointer value stored in the left sub-tree field

  4. Now set both left and right sub-tree pointers to NullPointer.  The new node will automatically be a leaf node

  5. IF the tree is empty (StartPointer = NullPointer)

     1. Make this the root node by setting StartPointer to the node's location

1. ELSE

   1. WHILE ThisNodePointer <> NullPointer // keep repeating until space to insert new node (leaf node)

      1. Remember current node (PreviousPointer <-- ThisNodePointer)

      2. If current item < new item (alphabetical or numerical) then we turn right, else left

         1. Record which direction turned (important for later adding new node)

         2. Set ThisNodePointer to current node's left or right pointer accordingly

   2. If we turned left last

• • 1. set the PreviousPointer's left pointer to point to our new node

1. 3. ELSE

• • 1. set the PreviousPointer's right pointer to point to our new node

2015 text book

PROCEDURE InsertNode(Newitem)

    IF FreePtr <> NullPointer THEN // there is space in the array

        // take node from free list, store data item and set null pointers

        NewNodePtr <-- FreePtr

        FreePtr <-- Tree[FreePtr].LeftPointer

        Tree[NewNodePtr].Data <-- Newitem

        Tree[NewNodePtr].LeftPointer <-- NullPointer

        Tree[NewNodePtr].RightPointer <-- NullPointer

        // check if empty tree

        IF RootPointer = NullPointer THEN //insert new node at root

            RootPointer <-- NewNodePtr

        ELSE //find insertion point

            ThisNodePtr <-- RootPointer //start at the root of the tree

            WHILE ThisNodePtr <> NullPointer //while not a leaf node

                PreviousNodePtr <-- ThisNodePtr //remember this node

                IF Tree[ThisNodePtr].Data > NewItem THEN //follow left pointer

                    TurnedLeft <-- TRUE

                    ThisNodePtr <-- Tree[ThisNodePtr].LeftPointer

                ELSE //follow right pointer

                    TurnedLeft <-- FALSE

                    ThisNodePtr <-- Tree[ThisNodePtr].RightPointer

                ENDIF

            ENDWHILE

            IF TurnedLeft = TRUE THEN

                Tree[PreviousNodePtr].LeftPointer <-- NewNodePtr

            ELSE

                Tree[PreviousNodePtr].RightPointer <- NewNodePtr

            ENDIF

        ENDIF

    ENDIF

ENDPROCEDURE

Deleting a binary tree node

Deleting a binary tree node is reasonably complex, and may require re-organising the tree.  For this reason, it IS NOT in the specification and you WILL NOT be required to do this in your exam.

Outputting all items in a binary tree

This process can be done recursively and simply. The procedure looks like this:

PROCEDURE TraverseTree(BYVALUE Pointer : INTEGER)

    IF Pointer <> NULL THEN

        TraverseTree(Tree[Pointer].LeftPointer)

        OUTPUT Tree[Pointer].Data

        TraverseTree(Tree[Pointer].RightPointer)

    ENDIF

ENDPROCEDURE

Notice how there are no checks for nulls when traversing, only when the procedure is called.  This way, if any call is made with a NullPointer, the routine simply completes and nothing is output.

Graph (including Tree) Traversal Methods (new)

CAIE seem to have moved to ask for specific traversal methods (which are not listed in the specification). You will have done work on traversal with Dykstra and A*, but when searching a tree, there are numerous other ways to access nodes. This is a link to Isaac Computing (an excellent CS resource for all specifications). It will talk you through the simple types of graph traversal.

Isaac Computing Site

A more basic video to start with, looking at the concepts of, and how to derive a hash value and table.  The second and third video go into much more detail.

LEFT: Continuation video from Harvard, going into further detail.  E.g. hash functions, etc. 

RIGHT: The following video looks at open addressing (closed hashing).  it also covers double-hashing, which is beyond the scope of the specification.

Algorithms

A dictionary (and hash table - derived from a dictionary) is an abstract data type using a key-value relationship. The specification only considers hash tables for the algorithm work, so we will use these. 

A consideration with a hash table is open addressing (closed hashing) or closed addressing (open hashing).  The former requires you to start at the hashed value and then keep moving down until there is a free slot in which to insert.  Closed addressing must use a linked list, or other mechanism, but which multiple data items can hang from the same position in the table.

Remember, there is a difference between a hash value and a hash table. 

Watson and Williams textbook page 487

Langfield and Duddell textbook pages 424-426

This can be found on sub page here.