AS Level9Paper 2 — Problem-solving and Programming

Algorithm Design and Problem-solving

Turning a problem into a plan: decomposition, structure charts, pseudocode and testing.

YOU SHOULD BE ABLE TO

Use abstraction, decomposition and stepwise refinement.
Produce structure charts, flowcharts and pseudocode.
Write algorithms using the standard patterns (totalling, counting, max, min).
Perform a linear search, a binary search, a bubble sort and an insertion sort.
Produce and complete trace tables.
Identify and correct logic errors.

RUN THE PSEUDOCODE

Write the pseudocode your syllabus uses and press Run. Assignment is the arrow — type <- and it works the same as ←. Both syllabuses are accepted, so OUTPUT and PRINT both work; where a word differs from the one the exam prints, the runner says so.

PROGRAM

DECLARE Name : STRING
DECLARE Age : INTEGER

Name <- "Bat"
Age <- 14

OUTPUT "Hello ", Name
OUTPUT "Next year you are ", Age + 1

INPUT — ONE VALUE PER LINE

OUTPUT

Press Run to see what it does

TRACE TABLE

Total ← 0
FOR Count ← 1 TO N
    Total ← Total + Count
NEXT Count
OUTPUT Total

STARTN = 5

Count	Total	OUTPUT

One row per pass through the loop. Leave a cell blank if it does not change on that pass.

//Binary search — and its one condition

Binary search only works on SORTED data. Say that whenever you describe it. Each comparison halves the search space, so it is far faster than linear search on large data.

Low ← 1
High ← N
Found ← FALSE
WHILE Low <= High AND Found = FALSE DO
   Mid ← (Low + High) DIV 2
   IF A[Mid] = Target THEN
      Found ← TRUE
   ELSE
      IF A[Mid] < Target THEN
         Low ← Mid + 1
      ELSE
         High ← Mid - 1
      ENDIF
   ENDIF
ENDWHILE

//Insertion sort vs bubble sort

Bubble sort repeatedly swaps neighbours, so the biggest value bubbles to the end each pass. Insertion sort takes each element and slides it back into its correct place among those already sorted — it is generally faster on nearly-sorted data.

FOR i ← 2 TO N
   Key ← A[i]
   j ← i - 1
   WHILE j > 0 AND A[j] > Key DO
      A[j+1] ← A[j]
      j ← j - 1
   ENDWHILE
   A[j+1] ← Key
NEXT i

//Stepwise refinement

Start with the whole task in one line, then break each line into smaller steps, and repeat until every step is small enough to code directly. A structure chart shows the same idea as a diagram, with parameters passed between boxes.

CHECK YOURSELF

1.What must be true before a binary search will work?

2.After one full pass of a bubble sort, what is guaranteed?

Databases Data Types and Structures

RUN THE PSEUDOCODE

PROGRAM

DECLARE Name : STRING
DECLARE Age : INTEGER

Name <- "Bat"
Age <- 14

OUTPUT "Hello ", Name
OUTPUT "Next year you are ", Age + 1

INPUT — ONE VALUE PER LINE

OUTPUT

Press Run to see what it does

Count

Total

OUTPUT

//Binary search — and its one condition

Binary search only works on SORTED data. Say that whenever you describe it. Each comparison halves the search space, so it is far faster than linear search on large data.

Low ← 1
High ← N
Found ← FALSE
WHILE Low <= High AND Found = FALSE DO
   Mid ← (Low + High) DIV 2
   IF A[Mid] = Target THEN
      Found ← TRUE
   ELSE
      IF A[Mid] < Target THEN
         Low ← Mid + 1
      ELSE
         High ← Mid - 1
      ENDIF
   ENDIF
ENDWHILE

//Insertion sort vs bubble sort

FOR i ← 2 TO N
   Key ← A[i]
   j ← i - 1
   WHILE j > 0 AND A[j] > Key DO
      A[j+1] ← A[j]
      j ← j - 1
   ENDWHILE
   A[j+1] ← Key
NEXT i