Name:
Class Teacher:
Date:
OCR H446
A-Level Computer Science
REVISION BOOKLET
2.2 PROBLEM SOLVING AND PROGRAMMING
Content in H446 A-Level Computer Science:
1.1 The characteristics of contemporary processors, input, output and storage devices
1.2 Software and software development
1.3 Exchanging data
1.4 Data types, data structures and algorithms
1.5 Legal, moral, cultural and ethical issues
2.1 Elements of computational thinking
2.2 Problem solving and programming
2.3 Algorithms
www.learn-computerscience.com
2.2.1 PROGRAMMING TECHNIQUES
TOPIC
Programming constructs:
Sequence
Iteration
Branching
Recursion, how it can be used and compares to an iterative approach
Global and local variables
Modularity, functions and procedures, parameter passing by value
and by reference
Use of an IDE to develop/debug a program
Use of object-oriented techniques
2.2.1 PROGRAMMING TECHNIQUES
PROGRAMMING CONSTRUCTS
SEQUENCE
ITERATION
BRANCHING
HOW RECURSION CAN BE USED AND COMPARES TO AN ITERATIVE APPROACH
GLOBAL AND LOCAL VARIABLES
MODULARITY
FUNCTIONS AND PROCEDURES
PARAMETERS PASSING BY VALUE AND BY REFERENCE
USE OF AN IDE TO DEVELOP/DEBUG A PROGRAM
USE OF OBJECT-ORIENTED TECHNIQUES
2.2.2 COMPUTATIONAL METHODS
TOPIC
Features that make a problem solvable by computational methods
Problem recognition
Problem decomposition
Use of divide and conquer
Use of abstraction
Learners should apply their knowledge of:
Backtracking
Data mining
Heuristics
Performance modelling
Pipelining
Visualisation to solve problems
2.2.2 COMPUTATIONAL METHODS
FEATURES THAT MAKE A PROBLEM SOLVABLE BY COMPUTATIONAL METHODS
PROBLEM RECOGNITION
PROBLEM DECOMPOSITION
USE OF DIVIDE AND CONQUER
USE OF ABSTRACTION
BACKTRACKING
DATA MINING
HEURISTICS
PERFORMANCE MODELLING
PIPELINING
VISUALISATION TO SOLVE PROBLEMS
EXAM QUESTIONS
QUESTION 1
A systems analyst has been employed by a busy city library to produce a new computerised
system. Explain the stages of the systems life cycle that must be completed after the design
stage and describe the documentation that the analyst must produce. The quality of written
communication will be assessed in your answer to this question.
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
[8]
QUESTION 2
Four in a Row is a game where two players drop coloured discs into a grid, with the aim to
get four of their own colour in a row. Each player is given a set of coloured discs, red (R) or
yellow (Y). The players take it in turns to drop their disc into a column in the grid. The disc
drops down to the lowest available space in that column. The grids below (Fig 7.1 and 7.2)
show what happens when the yellow player drops a disc into column 2:
The game continues until one player has got four discs of their colour in a straight row in
any direction i.e. vertical, horizontal or a diagonal.
A programmer is going to use decomposition to help produce the game. Explain how
decomposition can be used in the design of the game Four in a Row.
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
[2]
The program will allow the players to take it in turns to make a move. Each move will be
checked to ensure it is valid (i.e. the column is not already full). After each move the program
will check if that player has won by checking the horizontal, vertical and diagonal positions
to confirm if that player has four discs in a row.
The programmer has developed a top-down design for the program as shown in the
structure diagram Fig 7.3.
Add one further level to the structure diagram, by dividing the sub-modules ‘Player move’,
‘Check valid’ and ‘Check won’ into further sub-modules.
[3]
The structured design for this program makes use of pipelining. Describe one example of
where pipelining could be used in this program.
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
[2]
A 2-dimensional array, grid, is used to hold the game grid. Using pseudocode, write a
function that takes as input the player whose turn it is, and the column number they select
as their turn. The function either:
• Returns 999 (i.e. the column is already full), or
• Stores the player’s move in the array and returns the row the disc has been placed in
Annotate your pseudocode with comments to show how it solves the problem.
[6]
After a player makes their move, the program needs to check if that player has won (i.e. the
player has four discs in a row). Subroutines have already been written to check if the player
has won vertically, or diagonally. Using pseudocode, write a procedure that reads
appropriate parameters and checks if the player has won horizontally. If the player has won,
display an appropriate message identifying which player has won.
[6]
The programmer is writing a new version of the game, where each player removes one disc
from the bottom row of the grid before a new move is made. In the example below, player
R removes one disc from column 2 (before) and places one in column 4 (after).
The programmer has to decide whether to continue to use a 2D array or produce an array
of queues. Evaluate the use of 2D array of queues to perform this action.
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
[9]
Explain why a stack would not be an appropriate data structure for this revised game.
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
[2]
A procedure needs to be written to remove the disc from the chosen column. The procedure
will:
• Have the column the disc is being removed from as a parameter
• Move each disc in that column down to the bottom of the grid
• Replace the top space with an empty string (“”)
Complete the algorithm below.
[3]
The programmer is adding a feature that allows a player to play against the computer.
Explain how the programmer could make use of a tree structure, using a heuristic approach
in the development of the computer player.
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
[7]
QUESTION 3
José works for a company that provides loans to its customers. When customers take out a
load they decide how much money to borrow and for how many years. The interest rate is
currently 10% but it may change in the future. José writes the following program to calculate
the monthly payment for a loan.
Using the code above, show the value that will be output if the inputs are:
Amount: 600
Years: 5
You must show all your working.
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
[3]
Parentheses have been used in lines 09 and 10. State why the parentheses in line 09 are not
essential.
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
[1]
Explain why the parentheses in line 09 are useful.
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
[2]
Explain why the parentheses in line 10 are essential.
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
[2]
QUESTION 4
A procedural programming language may use procedures. Explain the term procedural
programming language.
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
[2]
The same variable name may be used in more than one procedure in a programming.
Explain how a variable named result may be used in different procedures without causing
errors.
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
[2]
Explain parameter passing.
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
[5]
Algebraic notation may in infix or reverse Polish. Convert (p – q)/r to reverse Polish.
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
[2]
Convert stu*+ to infix.
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
[2]
QUESTION 5
Variables are used in programming. Describe the use of local variables.
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
[4]
State two features of global variables that distinguish them from local variables.
1
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
2
……………………………………………………………………………………………………………………………………………
……………………………………………………………………………………………………………………………………………
[2]
