Algorithms (Cambridge (CIE) A Level Computer Science): Exam Questions

This binary tree shows an ordered list of integers.

A linked list of nodes is used to store the data. Each node consists of a left pointer, the data and a right pointer.

−1 is used to represent a null pointer.

Complete this linked list to represent the given binary tree organisation.

A 2D array is used to store the nodes of the linked list in part (a). Complete the diagram using your answer for part (a)

The linked list in part (a) is implemented using a 1D array of records. Each record contains a left pointer, data and a right pointer.

The following pseudocode represents a function that searches for an element in the array of records LinkList. It returns the index of the record if the element is found, or it returns a null pointer if the element is not found.

Complete the pseudocode for the function.

FUNCTION SearchList(Item : INTEGER) ........................................................................

NullPtr $\leftarrow$ −1

.................................................................... RootPtr

WHILE NowPtr <> NullPtr

IF LinkList[NowPtr].Data < Item THEN

NowPtr $\leftarrow$ LinkList[NowPtr].RightPtr

ELSE

IF ..................................................................... THEN

NowPtr $\leftarrow$..............................................................................

ELSE

RETURN NowPtr

ENDIF

ENDIF

ENDWHILE

RETURN NullPtr

ENDFUNCTION

State a condition that must be true for an array to be searchable for a binary search.

Complete the given pseudocode to find an item in a 1D array Names of type STRING using a binary search.

DECLARE Names : ARRAY[1:100000] OF STRING

DECLARE TopOfList : INTEGER

DECLARE EndOfList : INTEGER

DECLARE CurrentItem : INTEGER

DECLARE ToFind : STRING

DECLARE Found : BOOLEAN

DECLARE NotInList : BOOLEAN

TopOfList ← 1

EndOfList ← 100000

OUTPUT "Which name do you wish to find? "

INPUT ToFind

...................................................................................................................................................

NotInList ← FALSE

WHILE ................................................ AND ................................................

CurrentItem ← (TopOfList + EndOfList) DIV 2

IF ........................................................................................................... THEN

Found ← TRUE

ELSE

IF TopOfList >= EndOfList THEN

...........................................................................................................

ELSE

IF ToFind > Names[CurrentItem] THEN

...........................................................................................................

ELSE

EndOfList ← CurrentItem – 1

ENDIF

ENDIF

ENDIF

ENDWHILE

IF Found = TRUE THEN

OUTPUT "Item found at position ", CurrentItem, " in array"

ELSE

OUTPUT "Item not in array"

ENDIF

Describe the performance of a binary search in relation to the number of data items in the array being searched. Refer to Big O notation in your answer.

Complete the pseudocode to find an item in a 1D array Widgets of type STRING, using a linear search.

DECLARE Widgets : ARRAY[1:50000] OF STRING

DECLARE TopOfList : INTEGER

DECLARE EndOfList : INTEGER

DECLARE Count : INTEGER

DECLARE ToFind : STRING

DECLARE Found : BOOLEAN

DECLARE NotInList : BOOLEAN

TopOfList ← 1

EndOfList ← 50000

OUTPUT "Enter the name of the item you wish to find "

INPUT ToFind

Found ← FALSE

NotInList ← FALSE

Count ← TopOfList

WHILE Found = FALSE AND NotInList = FALSE

IF Widgets[Count] = ToFind THEN

Found ← TRUE

ENDIF

Count ← Count + 1

IF Count > EndOfList THEN

NotInList ← TRUE

ENDIF

ENDWHILE

IF Found = TRUE THEN

OUTPUT "Item found at position ", Count - 1, " in array"

ELSE

OUTPUT "Item not in array"

ENDIF

Compare the methods used by the linear and binary search algorithms to find an item in an array. Refer to Big O notation in your answer.

Show how the contents of the following stack will change as the RPN expression in part (a)(i) is evaluated.

Explain how a stack can be used to evaluate RPN expressions.

A stack is to be set up using the information in the table.

A constant, with identifier Capacity, limits the size of the stack to 25 items.

Write the pseudocode for the required declarations.

Complete the pseudocode function Pop() to pop an item from Stack.

// popping an item from the stack

FUNCTION Pop()...............................................................................

DECLARE Item : REAL

Item$\leftarrow$0 ........................................BasePointer THEN

Item$\leftarrow$ ........................................

TopPointer ..................................................

ELSE

OUTPUT "The stack is empty – error"

ENDIF

.........................................................................

ENDFUNCTION

Compare and contrast the queue and stack Abstract Data Types (ADT).

The Reverse Polish Notation (RPN) expression:

a b * 2 / c d / *

is to be evaluated where a = 20, b = 3, c = 10 and d = 5.

Show the changing contents of the following stack as the RPN expression is evaluated.

A program stores the names of cities in alphabetical order in a linked list. The linked list is implemented using a 1D array of records, declared as follows:

TYPE ListNode

    DECLARE Data : STRING

    DECLARE NextPointer : INTEGER

ENDTYPE

CONSTANT NullPtr = 0

DECLARE List : ARRAY[1:8] OF ListNode

DECLARE HeadPointer : INTEGER

DECLARE FreePtr : INTEGER

• HeadPointer stores the index of the first node in the linked list.

• FreePtr stores the index of the first node in the free list. Nodes that are not in use are joined together in the free list.

• A NextPointer value of NullPtr (0) shows that there are no further nodes in that list.

The table shows the current contents of the array. HeadPointer is 5 and FreePtr is 7.

Use the table to:

• write the data items in the order they are visited when the linked list is traversed from HeadPointer

• state the value of FreePtr after one new city name has been added to the linked list.

A stack is implemented using a 1D array, Stack, declared as ARRAY[1:6] OF STRING, and two integer pointers.

• BasePointer points to the bottom of the stack.

• TopPointer points to the item currently at the top of the stack.

The table shows the current contents of the array and the values of the pointers.

BasePointer = 1 and TopPointer = 4

These three operations are carried out on the stack, in this order:

1. Pop an item.

2. Pop an item.

3. Push "Suva".

State the value of TopPointer and the item at the top of the stack after these three operations.

A queue Abstract Data Type (ADT) stores up to six strings. It is implemented using a 1D array and the global variables declared in this pseudocode.

CONSTANT MaxSize = 6

DECLARE Queue : ARRAY[1:MaxSize] OF STRING

DECLARE FrontPointer : INTEGER

DECLARE RearPointer : INTEGER

DECLARE Length : INTEGER

The queue is organised as follows:

• FrontPointer points to the first item in the queue.

• RearPointer points to the last item in the queue.

• Length stores the number of items currently in the queue.

• When a pointer moves past index 6 it is set back to index 1, so array locations can be reused.

Write the pseudocode for the function IsFull().

The function returns TRUE if no more items can be added to the queue, and returns FALSE otherwise.

A stack of integers is implemented using a 1D array and two pointers.

CONSTANT MaxSize = 50

DECLARE Stack : ARRAY[1:50] OF INTEGER

DECLARE BasePointer : INTEGER

DECLARE TopPointer : INTEGER

The pointer BasePointer points to the bottom of the stack. The pointer TopPointer points to the item currently at the top of the stack. When the stack is empty, TopPointer is one less than BasePointer.

A programmer has written this pseudocode to initialise the stack and to push an item onto it. The line numbers are not part of the pseudocode.

01  PROCEDURE Initialise()

02     BasePointer ← 1

03     TopPointer ← 1

04  ENDPROCEDURE

05

06  PROCEDURE Push(NewItem : INTEGER)

07     IF TopPointer <= MaxSize THEN

08        Stack[TopPointer] ← NewItem

09        TopPointer ← TopPointer + 1

10     ELSE

11        OUTPUT "The stack is full - error"

12     ENDIF

13  ENDPROCEDURE

The pseudocode contains three errors.

Identify each error. For each error, give the line number or numbers and write the corrected pseudocode.

A program stores the names of animals in alphabetical order in a linked list. The linked list is implemented using a 1D array of records, declared as follows:

TYPE ListNode

    DECLARE Data : STRING

    DECLARE NextPointer : INTEGER

ENDTYPE

CONSTANT NullPtr = 0

DECLARE List : ARRAY[1:8] OF ListNode

DECLARE HeadPointer : INTEGER

DECLARE FreePtr : INTEGER

• HeadPointer stores the index of the first node in the linked list.

• FreePtr stores the index of the first node in the free list. Nodes that are not in use are joined together in the free list.

• A NextPointer value of NullPtr (0) shows that there are no further nodes in that list.

The table shows the contents of the array. HeadPointer is 4 and FreePtr is 6.

The node containing Horse is deleted from the linked list. The deleted node is added to the start of the free list. The data item in the deleted node is not removed from the array.

Complete the table to show the values of HeadPointer, FreePtr and every NextPointer after the deletion.

A stack of characters is implemented using a 1D array and two pointers.

CONSTANT MaxSize = 3

DECLARE Stack : ARRAY[1:3] OF CHAR

DECLARE BasePointer : INTEGER

DECLARE TopPointer : INTEGER

DECLARE Code : CHAR

DECLARE Count : INTEGER

PROCEDURE Push(NewItem : CHAR)

   IF TopPointer < MaxSize THEN

      TopPointer ← TopPointer + 1

      Stack[TopPointer] ← NewItem

   ELSE

      OUTPUT "Full"

   ENDIF

ENDPROCEDURE

FUNCTION Pop() RETURNS CHAR

   DECLARE Item : CHAR

   Item ← '-'

   IF TopPointer >= BasePointer THEN

      Item ← Stack[TopPointer]

      TopPointer ← TopPointer - 1

   ENDIF

   RETURN Item

ENDFUNCTION

// main program

BasePointer ← 1

TopPointer ← 0

FOR Count ← 1 TO 8

   INPUT Code

   IF Code = 'U' THEN

      OUTPUT Pop()

   ELSE

      CALL Push(Code)

   ENDIF

NEXT Count

The main program is run and these eight characters are input, in this order:

'U', 'A', 'B', 'U', 'C', 'D', 'E', 'U'

Complete the trace table. The first row shows the values before the loop starts. Record a value only when it changes.

The 1D array Stock is declared as:

DECLARE Stock : ARRAY[1:8] OF INTEGER

It contains these values:

This function performs a linear search on Stock.

FUNCTION FindItem(SearchValue : INTEGER) RETURNS INTEGER

   DECLARE Index : INTEGER

   Index ← 1

   WHILE Index <= 8

      IF Stock[Index] = SearchValue THEN

         RETURN Index

      ENDIF

      Index ← Index + 1

   ENDWHILE

   RETURN -1

ENDFUNCTION

State the value returned by each of these function calls.

(i) FindItem(12)

(ii) FindItem(45)

A queue Abstract Data Type (ADT) is implemented using a 1D array and three global variables.

CONSTANT MaxSize = 5

DECLARE Queue : ARRAY[1:MaxSize] OF STRING

DECLARE FrontPointer : INTEGER

DECLARE RearPointer : INTEGER

DECLARE Length : INTEGER

PROCEDURE Initialise()

   FrontPointer ← 1

   RearPointer ← 0

   Length ← 0

ENDPROCEDURE

PROCEDURE Enqueue(NewItem : STRING)

   IF Length < MaxSize THEN

      RearPointer ← RearPointer + 1

      IF RearPointer > MaxSize THEN

         RearPointer ← 1

      ENDIF

      Queue[RearPointer] ← NewItem

      Length ← Length + 1

   ELSE

      OUTPUT "The queue is full"

   ENDIF

ENDPROCEDURE

FUNCTION Dequeue() RETURNS STRING

   DECLARE Item : STRING

   IF Length > 0 THEN

      Item ← Queue[FrontPointer]

      FrontPointer ← FrontPointer + 1

      Length ← Length - 1

      IF Length = 0 THEN

         CALL Initialise()

      ELSE

         IF FrontPointer > MaxSize THEN

            FrontPointer ← 1

         ENDIF

      ENDIF

   ELSE

      OUTPUT "The queue is empty"

      Item ← ""

   ENDIF

   RETURN Item

ENDFUNCTION

The current contents of the array are:

FrontPointer = 5, RearPointer = 5 and Length = 1.

These three operations are then carried out, in this order.

Complete the table to show the value returned by each operation and the values of the three variables after each operation has finished.

A program stores the names of cities in alphabetical order in a linked list. The linked list is implemented using a 1D array of records, declared as follows:

TYPE ListNode

    DECLARE Data : STRING

    DECLARE NextPointer : INTEGER

ENDTYPE

CONSTANT NullPtr = 0

DECLARE List : ARRAY[1:8] OF ListNode

DECLARE HeadPointer : INTEGER

DECLARE FreePtr : INTEGER

• HeadPointer stores the index of the first node in the linked list.

• FreePtr stores the index of the first node in the free list. Nodes that are not in use are joined together in the free list.

• A NextPointer value of NullPtr (0) shows that there are no further nodes in that list.

• When there are no free nodes, FreePtr is NullPtr.

• List, HeadPointer and FreePtr are global. The array and both pointers have already been initialised.

A procedure InsertItem(NewItem : STRING) adds a city name to the linked list. The procedure must:

• output a suitable message if there are no free nodes

• otherwise, take the first node from the free list and store NewItem in it

• insert the new node into the linked list so that the data items stay in alphabetical order. The new item may belong at the start, in the middle or at the end of the list, and the list may be empty.

Write pseudocode for the procedure InsertItem().

A program uses a bubble sort to put the values in the 1D array Data into ascending order. Data is declared as ARRAY[1:8] OF INTEGER.

Boundary ← 7

REPEAT

    NoSwaps ← TRUE

    FOR J ← 1 TO Boundary

        IF Data[J] > Data[J + 1] THEN

            Temp ← Data[J]

            Data[J] ← Data[J + 1]

            Data[J + 1] ← Temp

            NoSwaps ← FALSE

        ENDIF

    NEXT J

    Boundary ← Boundary - 1

UNTIL NoSwaps = TRUE

Before the sort starts, Data holds these eight values:

3, 7, 12, 15, 20, 26, 31, 40

State:

• the number of passes that the algorithm makes through Data

• the number of times the condition Data[J] > Data[J + 1] is evaluated.

A program stores six product codes in the 1D array Codes.

DECLARE Codes : ARRAY[1:6] OF STRING

This pseudocode performs a linear search for the value in Target.

Found ← FALSE

Index ← 0

REPEAT

   Index ← Index + 1

   IF Codes[Index] = Target THEN

      Found ← TRUE

   ENDIF

UNTIL Found OR Index = 6

IF Found THEN

   OUTPUT "Found at ", Index

ELSE

   OUTPUT "Not found"

ENDIF

Complete the trace table for the pseudocode when Target is "K7". Record the values at the end of each pass through the loop. You may not need all the rows.

A queue Abstract Data Type (ADT) stores the names of up to six customers. It is implemented using a 1D array and the global variables declared in this pseudocode.

CONSTANT MaxSize = 6

DECLARE Queue : ARRAY[1:MaxSize] OF STRING

DECLARE FrontPointer : INTEGER

DECLARE RearPointer : INTEGER

DECLARE Length : INTEGER

The queue is organised as follows:

• FrontPointer points to the first item in the queue.

• RearPointer points to the last item in the queue.

• Length stores the number of items currently in the queue.

• When a pointer moves past index 6 it is set back to index 1, so array locations can be reused.

• Items that have been removed from the queue are not cleared from the array.

The current state of the queue is:

FrontPointer = 5, RearPointer = 2 and Length = 4.

A function Position() takes a customer name as a parameter. It returns the position of that name in the queue, where the first item in the queue is position 1. If the name is not in the queue, the function returns -1. The function must not change the contents of the queue or the values of the three global variables.

For example, with the queue shown:

• Position("Chen") returns 3

• Position("Okoro") returns -1, because "Okoro" has already been removed from the queue.

Write the pseudocode for the function Position().

A bubble sort is used to put the six values in the 1D array Points into descending order. Points is declared as ARRAY[1:6] OF INTEGER.

Boundary ← 5

REPEAT

    NoSwaps ← TRUE

    FOR J ← 1 TO Boundary

        IF Points[J] < Points[J + 1] THEN

            Temp ← Points[J]

            Points[J] ← Points[J + 1]

            Points[J + 1] ← Temp

            NoSwaps ← FALSE

        ENDIF

    NEXT J

    Boundary ← Boundary - 1

UNTIL NoSwaps = TRUE

Complete the table to show the contents of Points at the end of each of the first three passes.

A weather station stores 500 temperature readings in a global 1D array Readings.

DECLARE Readings : ARRAY[1:500] OF INTEGER

The readings are not in any order. The same value may appear more than once.

A function LinearSearch() is needed. It:

• takes an integer parameter SearchValue

• performs a linear search on Readings

• stops searching as soon as SearchValue is found

• returns the index of the first element that matches SearchValue

• returns -1 if SearchValue is not in the array.

Write pseudocode for the function LinearSearch().

The 1D array Scores holds 15 integers in ascending order.

DECLARE Scores : ARRAY[1:15] OF INTEGER

A binary search is used to find the value 52. The search starts with Lower ← 1, Upper ← 15 and Found ← FALSE. On each pass it carries out these steps.

Mid ← (Lower + Upper) DIV 2

IF Scores[Mid] = 52 THEN

   Found ← TRUE

ELSE

   IF Scores[Mid] < 52 THEN

      Lower ← Mid + 1

   ELSE

      Upper ← Mid - 1

   ENDIF

ENDIF

The search stops when Found is TRUE.

State, in order, each value in Scores that is compared with 52.

A library system stores 1000 book titles in a 1D array, sorted into alphabetical order. The number of titles is going to increase to 2000.

When the array holds 1000 titles, a binary search makes at most 10 comparisons to find a title or to decide that it is not in the array.

Explain how increasing the number of titles to 2000 affects the maximum number of comparisons made by:

• a binary search

• a linear search.

The 1D array Values is declared as ARRAY[1:6] OF INTEGER. Before sorting, it holds:

3, 5, 6, 8, 9, 2

The array is to be sorted into ascending order. Two algorithms are being compared.

Algorithm A: bubble sort

Boundary ← 5

REPEAT

    NoSwaps ← TRUE

    FOR J ← 1 TO Boundary

        IF Values[J] > Values[J + 1] THEN

            Temp ← Values[J]

            Values[J] ← Values[J + 1]

            Values[J + 1] ← Temp

            NoSwaps ← FALSE

        ENDIF

    NEXT J

    Boundary ← Boundary - 1

UNTIL NoSwaps = TRUE

Algorithm B: insertion sort

FOR Index ← 2 TO 6

    Item ← Values[Index]

    Pos ← Index

    WHILE Pos > 1 AND Values[Pos - 1] > Item

        Values[Pos] ← Values[Pos - 1]

        Pos ← Pos - 1

    ENDWHILE

    Values[Pos] ← Item

NEXT Index

A comparison is one check of whether a value in Values is greater than another value in Values. In Algorithm B, when Pos > 1 is FALSE, assume that the rest of the WHILE condition is not checked.

Complete the table to show the number of comparisons each algorithm makes to sort this data. Then explain why Algorithm B makes fewer comparisons than Algorithm A for this data.

Describe how an insertion sort puts the values in a 1D array into ascending order.

A school stores the names of 200 students in a global 1D array Names.

DECLARE Names : ARRAY[1:200] OF STRING

The names are stored in ascending alphabetical order. Each name appears only once.

A function BinarySearch() is needed. It:

• takes a string parameter Target

• performs a binary search on Names

• returns the index of the element that matches Target

• returns -1 if Target is not in the array.

Write pseudocode for the function BinarySearch().

An insertion sort is used to put the six values in the 1D array Numbers into ascending order. Numbers is declared as ARRAY[1:6] OF INTEGER.

FOR Index ← 2 TO 6

    Item ← Numbers[Index]

    Pos ← Index

    WHILE Pos > 1 AND Numbers[Pos - 1] > Item

        Numbers[Pos] ← Numbers[Pos - 1]

        Pos ← Pos - 1

    ENDWHILE

    Numbers[Pos] ← Item

NEXT Index

Complete the table to show the contents of Numbers at the end of the iterations of the FOR loop when Index is 2, 3 and 4.

A race organiser stores the results of 40 runners in two global 1D arrays:

• RunnerID is declared as ARRAY[1:40] OF STRING and holds the ID of each runner

• FinishTime is declared as ARRAY[1:40] OF INTEGER and holds the finishing time of each runner, in seconds.

The runner whose ID is in RunnerID[N] has the finishing time in FinishTime[N].

Write pseudocode for a procedure SortResults() that uses an insertion sort to put FinishTime into ascending order. The IDs in RunnerID must be put into the same order, so that each ID stays with its finishing time.

An ordered binary tree stores the names of cities in alphabetical order.

The tree is implemented as a 1D array of records, BinTree. Each record contains a left pointer, the data and a right pointer.

• RootPtr points to the root node.

• FreePtr points to the first unused record. Unused records are linked together through their LeftPtr field.

• -1 is used to represent a null pointer.

The table shows the contents of the array.

RootPtr = 0 and FreePtr = 6

The tree is searched for the city Nairobi. The search starts at the node pointed to by RootPtr. At each node it follows the left pointer if the item searched for comes before the data in that node, and the right pointer if it comes after. The search returns the index of the node if the item is found, or a null pointer if it is not found.

Identify the index of each node visited, in the order they are visited, and state the value returned by the search.

An ordered binary tree stores integers. It is implemented as a 1D array of records, BinTree, with indexes 0 to 7. Each record contains a left pointer, the data and a right pointer.

• RootPtr points to the root node.

• FreePtr points to the first unused record. Unused records are linked together through their LeftPtr field.

• -1 is used to represent a null pointer.

A new item is always stored in the record pointed to by FreePtr. It is then joined to the tree as a new leaf node.

The table shows the contents of the array before any more items are added.

RootPtr = 0 and FreePtr = 6

The integer 30 is added to the tree, and then the integer 64 is added.

Complete the table and the values of RootPtr and FreePtr to show the contents after both items have been added.

RootPtr = ..........

FreePtr = ..........

A program stores integers in an ordered binary tree. The tree is implemented as a 1D array of records. No two items in the tree have the same value.

TYPE Node

    DECLARE LeftPtr : INTEGER

    DECLARE Data : INTEGER

    DECLARE RightPtr : INTEGER

ENDTYPE

DECLARE BinTree : ARRAY[0:19] OF Node

DECLARE RootPtr : INTEGER

DECLARE FreePtr : INTEGER

• BinTree, RootPtr and FreePtr are global.

• -1 is used to represent a null pointer. RootPtr is -1 when the tree is empty.

• FreePtr points to the first unused record. Unused records are linked together through their LeftPtr field. FreePtr is -1 when there are no unused records.

• An item that is smaller than the data in a node is stored in that node's left subtree. An item that is larger is stored in its right subtree.

Write pseudocode for the procedure AddNode(NewItem : INTEGER).

The procedure must:

• output "Tree full" and add nothing if there are no unused records

• otherwise store NewItem in a record taken from the free list, and join that record to the tree as a leaf node in the correct position.

A food delivery company holds customer orders in a queue Abstract Data Type (ADT) until the kitchen is ready for them. The number of orders waiting changes a lot during the day. Late at night the queue is often empty, but at lunchtime several hundred orders can be waiting.

The queue can be implemented using a 1D array or using a linked list.

Justify the use of a linked list instead of a 1D array to implement this queue.

A print server stores print jobs in a queue Abstract Data Type (ADT). The queue is implemented using two stacks, StackA and StackB.

• StackA holds the queue. The item at the front of the queue is at the top of StackA.

• StackB is empty except while a new item is being added.

To add a new item to the queue, these three steps are carried out in order:

1. Every item is popped from StackA and pushed onto StackB, until StackA is empty.

2. The new item is pushed onto StackB.

3. Every item is popped from StackB and pushed onto StackA, until StackB is empty.

The queue currently holds the print jobs 104, 105 and 106. Job 104 is at the front of the queue and job 106 is at the rear.

Job 107 is now added to the queue.

Complete the table to show the contents of each stack after each step. Write the items in each stack in order from the bottom of the stack to the top. Write "empty" for an empty stack.

A queue Abstract Data Type (ADT) of strings is implemented using two stacks. Each stack is a 1D array with its own top pointer. The global declarations are:

CONSTANT MaxSize = 20

DECLARE StackA : ARRAY[1:MaxSize] OF STRING

DECLARE StackB : ARRAY[1:MaxSize] OF STRING

DECLARE TopPointerA : INTEGER

DECLARE TopPointerB : INTEGER

A stack is empty when its top pointer is 0. StackA holds the queue, with the item at the front of the queue at the top of StackA. StackB is empty except while a new item is being added.

These modules are already written:

• PushA(NewItem : STRING) pushes NewItem onto StackA

• PopA() RETURNS STRING removes and returns the item at the top of StackA

• PushB(NewItem : STRING) pushes NewItem onto StackB

• PopB() RETURNS STRING removes and returns the item at the top of StackB

PopA() and PopB() are only called when that stack is not empty.

Write pseudocode for:

• the procedure Enqueue(NewItem : STRING), which outputs "Queue full" if StackA holds MaxSize items, and otherwise adds NewItem to the rear of the queue

• the function Dequeue(), which outputs "Queue empty" and returns an empty string if the queue is empty, and otherwise removes and returns the item at the front of the queue.

Two different algorithms can perform the same task.

State two criteria that can be used to compare the two algorithms.

A delivery company stores the details of 800 parcels in a 1D array. The array is not sorted.

Parcels are added to the array and removed from it many times each minute, in no particular order. After each change, the program searches the array once to find one parcel ID.

A binary search usually checks far fewer items than a linear search.

Explain why a linear search is more suitable than a binary search for this program.

The 1D array IDs is declared as:

DECLARE IDs : ARRAY[1:500] OF INTEGER

Each element holds a student ID between 1 and 1000. A program must find out whether any ID is stored more than once. Two algorithms are being considered.

Algorithm P

Duplicate ← FALSE

FOR I ← 1 TO 499

    FOR J ← I + 1 TO 500

        IF IDs[I] = IDs[J] THEN

            Duplicate ← TRUE

        ENDIF

    NEXT J

NEXT I

Algorithm Q

Algorithm Q uses a second array, Seen, which is declared in its first line.

DECLARE Seen : ARRAY[1:1000] OF BOOLEAN

FOR K ← 1 TO 1000

    Seen[K] ← FALSE

NEXT K

Duplicate ← FALSE

FOR I ← 1 TO 500

    IF Seen[IDs[I]] = TRUE THEN

        Duplicate ← TRUE

    ENDIF

    Seen[IDs[I]] ← TRUE

NEXT I

Compare the suitability of Algorithm P and Algorithm Q for this task, in terms of the time taken and the memory used.

Your answer must include the number of times the IF condition is evaluated by each algorithm.

A linear search has a time complexity of O(n) in Big O notation.

(i) State what Big O notation is used to indicate about an algorithm.

(ii) State what O(n) shows about how the time taken by a linear search changes as the number of items in the array increases.

The 1D array Heights is declared as ARRAY[1:N] OF INTEGER. The values in Heights are in ascending order.

Algorithm A finds the total of all the values in Heights.

Total ← 0

FOR Index ← 1 TO N

    Total ← Total + Heights[Index]

NEXT Index

Algorithm B finds out whether the value Target is stored in Heights.

Low ← 1

High ← N

Found ← FALSE

REPEAT

    Mid ← (Low + High) DIV 2

    IF Heights[Mid] = Target THEN

        Found ← TRUE

    ELSE

        IF Heights[Mid] > Target THEN

            High ← Mid - 1

        ELSE

            Low ← Mid + 1

        ENDIF

    ENDIF

UNTIL Found = TRUE OR Low > High

Identify the Big O time complexity of each algorithm. Justify your answer for Algorithm B.

A developer tests two search algorithms, X and Y, on arrays of different sizes. The table shows the maximum number of items each algorithm checks before it finds an item or decides that the item is not in the array.

(a) Identify the Big O time complexity of each algorithm. Use the data in the table to justify each answer. [3]

(b) The number of items is increased to 1 048 576, which is 16 times the largest array in the table.

State the maximum number of items that Algorithm Y will check. [1]