19 - Computational thinking and Problem-solving

Write pseudocode for a linear search algorithm.

DECLARE MyList : ARRAY[0:9] OF INTEGER
DECLARE MaxIndex : INTEGER
DECLARE Index : INTEGER
DECLARE Found : BOOLEAN
DECLARE ValueToFind : INTEGER

INPUT ValueToFind
Found ← FALSE
Index ← 0
MaxIndex ← 9

REPEAT
 IF MyList[Index] = ValueToFind THEN
 Found ← TRUE
 ENDIF
 Index ← Index + 1
UNTIL Found OR Index > MaxIndex

IF Found THEN
 OUTPUT "Value found at position ", Index
ELSE
 OUTPUT "Value not found"
ENDIF

Write pseudocode for a binary search algorithm.

DECLARE Names : ARRAY[0:99] OF STRING
DECLARE Lower, Upper, Mid : INTEGER
DECLARE Exit : BOOLEAN
DECLARE Target : STRING
Lower ← 0
Upper ← 99
Mid ← 0
Exit ← FALSE

OUTPUT "Enter the name to be found "
INPUT Target

REPEAT
   IF Upper < Lower THEN
      OUTPUT Target, " does not exist"
      Exit ← TRUE
   ENDIF

   Mid ← Lower + (Upper – Lower + 1) DIV 2

   IF Names[Mid] < Target THEN
      Lower ← Mid + 1
   ENDIF

   IF Names[Mid] > Target THEN
      Upper ← Mid - 1
   ENDIF

   IF Names[Mid] = Target THEN
      OUTPUT Target, " was found at location ", Mid
      Exit ← TRUE
   ENDIF
UNTIL Exit = TRUE

Write pseudocode for an insertion sort algorithm.

DECLARE MyList : ARRAY[1:249] OF INTEGER
DECLARE ListSize, Index : INTEGER
DECLARE Temp : INTEGER
DECLARE Counter : INTEGER

ListSize ← 249
FOR Index ← 2 TO ListSize
   Temp ← MyList[Index]
   Counter ← Index

   WHILE Counter > 1 AND MyList[Counter - 1] < Temp
      MyList[Counter] ← MyList[Counter - 1]
      Counter ← Counter – 1
   ENDWHILE

   MyList[Counter] ← Temp
NEXT Index

Write pseudocode for a bubble sort algorithm.

DECLARE MyList : ARRAY[1:249] OF INTEGER
DECLARE ListSize, Index : INTEGER
DECLARE Temp : INTEGER
DECLARE Counter : INTEGER
DECLARE Flag : BOOLEAN

ListSize ← 249
Flag ← TRUE

WHILE Flag = TRUE
   Flag ← FALSE
   FOR Index ← 1 TO ListSize - 1
      IF MyList[Index] < MyList[Index + 1] THEN
         Temp ← MyList[Index]
         MyList[Index] ← MyList[Index + 1]
         MyList[Index + 1] ← Temp
         Flag ← TRUE
      ENDIF
   NEXT Index
ENDWHILE

Describe the factors that may affect the performance of a sorting algorithm. [3]

• The initial order of the data

• The number of data items to be sorted

• The efficiency of the sorting algorithm

Explain what is meant by recursion. [3]

• A process using a function or procedure defined in terms of itself / calls itself.

• A recursive process must have a base case (which is a way to return without making a recursive call) // terminating solution // concept of unwinding described

• There must (also) be a general case where the recursive call takes place.

Describe the essential features of recursion. [5]

• Must have a base case/stopping condition

• Must have a general case

• …which calls itself (recursively) // Defined in terms of itself

• …which changes its state and moves towards the base case

• Unwinding can occur once the base case is reached.

Describe the benefits of recursion. [2]

• can contain fewer programming statements than an iterative solution

• can solve complex problems in a simpler way

Explain why a stack is a suitable abstract data type (ADT) to implement for recursion. [5]

• A stack is a LIFO data structure

• Each recursive call is pushed onto the stack

• … and is then popped as the function ends

• Enables backtracking/unwinding

• … to maintain the required order.

Explain how a compiler makes use of a stack when translating recursive programming code. [5]

• The compiler must produce object code to

• …push return addresses / values of local variables onto a stack

• …with each recursive call // … to set up winding

• …pop return addresses / values of local variables off the stack …

• …after the base case is reached // … to implement unwinding.