9.1 Computational Thinking
AS Level · 11 questions found
What this topic covers
Section titled “What this topic covers”- Abstraction: need, purpose; produce an abstract model including only essential details
- Decomposition: break problems into sub-problems leading to procedures/functions
Past paper questions
Section titled “Past paper questions”There are several different ways to express an algorithm during the design of a program.
(a) One part of the program contains an algorithm which is represented by a state-transition diagram. 5 marks
The table shows the inputs, outputs and states for the algorithm:
| Current state | Input | Output | Next state |
|---|---|---|---|
| S1 | A2 | X2 | S3 |
| S1 | A1 | X1 | S2 |
| S2 | A4 | X4 | S5 |
| S3 | A1 | S3 | |
| S3 | A3 | X3 | S2 |
| S3 | A2 | X4 | S4 |
| S4 | A1 | X1 | S4 |
| S4 | A3 | S2 | |
| S4 | A4 | X4 | S5 |
Complete the state-transition diagram to represent the information given in the table.
(b) A structure chart is used to document a different part of the program. 5 marks
This part of the program contains six modules:
Pseudocode module header
PROCEDURE Setup()
PROCEDURE Restart(H1 : STRING, C1 : INTEGER)
FUNCTION Modify(B1 : BOOLEAN) RETURNS INTEGER
PROCEDURE Final(T1 : INTEGER)
PROCEDURE Update(BYREF R2 : STRING)
FUNCTION Confirm() RETURNS BOOLEAN
Module Setup will repeatedly call three of the modules.
Complete the structure chart to document the information given in the table.
Show mark scheme
7(a) [5 marks]
One mark for each: 1 Label A1 | X1 added on line from S1 to state labelled S2 2 States S3, S4 and S5 labelled 3 Line from S2 to S5 with event label A4|X4 4 Lines from S3 with correct event labels including 'loop' label 5 Lines from S4 with correct event labels including 'loop'
7(b) [5 marks]
One mark per point: 1 All boxes correctly labelled 2 Iteration arrow 3 Parameter to Restart 4 Return value from Modify and parameter to Final 5 BYREF parameter to Update
There are several different ways to express an algorithm during the design of a program.
(a) One part of the program contains an algorithm which is represented by a state-transition diagram. 5 marks
The table shows the inputs, outputs and states for the algorithm:
| Current state | Input | Output | Next state |
|---|---|---|---|
| S1 | A1 | S2 | |
| S2 | A2 | X4 | S3 |
| S3 | A1 | X1 | S3 |
| S3 | A2 | X1 | S3 |
| S3 | A3 | X3 | S4 |
| S3 | A4 | S2 | |
| S4 | A3 | X4 | S5 |
| S4 | A4 | X4 | S5 |
| S4 | A1 | S2 |
Complete the state-transition diagram to represent the information given in the table:
(b) A structure chart is used to document a different part of the program, made up of five modules. 4 marks
Program notes:
module Setup calls either module Restart, or module Confirm
module Confirm takes a string as a parameter and returns an integer
module Modify has no parameters and returns a Boolean
module Update takes a string as a parameter
module Restart repeatedly calls module Update followed by module Modify
module Restart takes a string as a parameter that is passed by reference.
Draw a structure chart to represent the relationship between the five modules, including all parameters and return values.
Show mark scheme
7(a) [5 marks]
One mark for each: 1 S2 to S5 labelled 2 Label A1 added to event from S1 to S2 3 Event lines from S2 to S3 and S3 to S2 correctly labelled 4 Events lines from S3 to S3 and event line from S3 to S4 all labelled correctly 5 Event lines from S4 to S5 correctly and event line from S4 to S2 labelled correctly Max 4 for any additional events/lines
7(b) [4 marks]
One mark for each: 1 All boxes correctly labelled and connected in correct hierarchy 2 BYREF parameter to Restart, parameter to Confirm and return 3 Diamond and loop symbol 4 Parameter to Update and return from Modify
An automated digital camera system is used to take a sequence of pictures of animals in a garden. During the design of the system, a state‑transition diagram is produced.
The table details the states in the automated digital camera system along with the events which cause the states to change.
The system starts in standby mode. The sequence of pictures is taken when in active mode.
| Current state | Event | Next state |
|---|---|---|
| standby mode | turn on | detect mode |
| detect mode | turn off | standby mode |
| detect mode | movement detected | active mode |
| active mode | 20 seconds elapsed | sequence complete |
| active mode | turn off | standby mode |
| sequence complete | time saved | detect mode |
(a) Complete the state‑transition diagram for the automated digital camera system. 4 marks
(b) At the end of each sequence of pictures, the time is saved as a string in the format <HH><MM><SS> where: 8 marks
HH represents the hours using two digits
MM represents the minutes using two digits
SS represents the seconds using two digits.
For example:
"081230" is stored to represent the time 8:12:30, in the morning
"152235" is stored to represent the time 15:22:35, in the afternoon.
Each string is stored on a new line in the text file TimeTaken.txt
An algorithm is required to process the content of the text file TimeTaken.txt once it has been transferred to the computer.
For each hour when pictures are taken, output a suitable message showing the hour and the total number of sequences of pictures taken within that hour.
Example outputs:
Hour : 15 Total : 32 Hour : 18 Total : 1
Write pseudocode for this algorithm.
Assume the text file TimeTaken.txt contains at least one line.
Show mark scheme
5(a) [4 marks]
Mark as follows: 1 Mark: The three new states drawn and labelled. 1 Mark: Two of the events drawn with labels connecting correct states and correct line direction 1 Mark: Four of the events drawn with labels connecting correct states and correct line direction. 1 Mark: All and only six events drawn with labels connecting correct states and correct line direction.
5(b)
Alternative solution and mark scheme use of an array to hold count for each hour Also, for use of 24 variables and 24 selection conditions DECLARE HoursArray[0 : 23] OF INTEGER DECLARE Index, Hour : INTEGER DECLARE Line : STRING FOR Index 0 TO 23 HoursArray[Index] 0 NEXT Index OPENFILE "TimeTaken.txt" FOR READ WHILE NOT EOF("TimeTaken.txt") READFILE "TimeTaken.txt", Line Hour STR_TO_NUM(LEFT(Line, 2)) HoursArray[Hour] HoursArray[Hour] + 1 ENDWHILE FOR Index 0 TO 23 IF HoursArray[Index] <> 0 THEN OUTPUT "Hour : ", Index, " Total : ", HoursArray[Index] ENDIF NEXT Index CLOSEFILE "TimeTaken.txt" Mark as follows:
- Initialisation of 24 array elements to 0 // Initialisation of 24 Integer variables to 0
- Open for read and subsequently close "TimeTaken.txt"
- Conditional loop until EOF
- Read a line from in a loop "TimeTaken.txt"
- Extract Hour from line read in a loop
- Convert Hour to an integer value in a loop
- Increment appropriate array element / variable in a loop
- Output of each hour and corresponding count variable (with a suitable message) for all values where count is not zero
A coffee shop owner wants to introduce a computerised loyalty card system.
A programmer discusses the details of the system with the shop owner.
(a) Identify the stage of the program development life cycle that this discussion is part of and give a document that will be produced during this stage. 2 marks
Stage
Document
(b) The shop will give each customer a loyalty card that displays a unique customer ID as a bar code. A customer will be able to present their card each time they make a purchase. The system will scan the bar code, calculate points, and add them to the customer’s total. When the customer next makes a purchase and presents their card, they will have the option to exchange points for a discount. 4 marks
The designer decides that this activity will be handled by a new module. Decomposition will be used to break the problem of designing the new module down into sub-problems (sub-modules).
Identify four sub-modules that could be used in the design of the new module and describe their use.
Sub-module 1
Use
Sub-module 2
Use
Sub-module 3
Use
Sub-module 4
Use
Show mark scheme
7(a) [2 marks]
One mark per answer: MP1 Analysis MP2 Named document, examples include: • A requirement specification • Definition of System Objectives • List of problems with existing system • Survey results • Feasibility study • Interview notes Max 2 marks
7(b) [4 marks]
One mark for name and use Mark as follows: Examples include: Sub-module: ScanCard()/ GetID() Use: Read the barcode from the loyalty card / Get the customer ID from the barcode Sub-module: GetPoints() Use: Get the number of points the customer has Sub-module: ExchangePoints() / UpdateCard() Use: Reduce the number of loyalty points Sub-module: GetDiscount() / CalculateDiscount() Use: Calculate the discount Sub-module: CalculatePoints() Use: Calculate points (following a purchase) Sub-module: UpdatePoints() Use: Update total points a customer has (following a purchase) Sub-module: ShowDiscount() Use: Display the discount Max 4 marks
A fitness club has a computerised membership system. The fitness club offers a number of different exercise classes.
The following information is stored for each club member: name, home address, email address, mobile phone number, date of birth and the exercise(s) they are interested in.
(a) When an exercise class is planned, a new module will send personalised text messages to each member who has expressed an interest in that exercise. Members wishing to join the class send a text message back. Members may decide not to receive future text messages by replying with the message ‘STOP’.
The process of abstraction is used to filter out unnecessary information.
(i) State one advantage of applying abstraction to this problem. 1 mark
(ii) Identify three items of information that will be required by the new module. 3 marks
Justify your choices with reference to the given scenario.
Item 1 required
Justification
Item 2 required
Justification
Item 3 required
Justification
(iii) Identify two operations that would be required to process data when the new module receives a text message back from a member. 2 marks
Operation 1
Operation 2
(b) The structure chart illustrates part of the membership program:
| Update A P2 T1 Name P1 Sub-A Sub-B Sub-C |
|
|---|---|
| Sub-A | Sub-C |
Data item notes:
Name contains the name of a club member
P1 and T1 are of type real.
(i) Explain the meaning of the diamond symbol (labelled with the letter A) in the chart. 2 marks
(ii) Write the pseudocode module headers for Sub-A and Sub-B. 4 marks
Sub-A
Sub-B
Show mark scheme
7(a)(i) [3 marks]
To make the solution easier to design / implement / solve
7(a)(ii)
One mark per item and justification Item: mobile phone number Justification: to send the text message Item: name Justification: to personalise the text message Item: exercise interest Justification: to determine whether this member would be interested
7(a)(iii) [2 marks]
Examples include: Add a member to a list of those interested in the new class Remove the member from future SMS messages Read/process Message Identify who from One mark for each. Max 2 marks
7(b)(i) [4 marks]
Means that calls (one of) either or Update Sub-A, Sub-B Sub-C One mark for each point: reference to selection / decision / if naming all four modules correctly PROCEDURE Sub-A (Name : STRING, BYREF P2 : BOOLEAN)
7(b)(ii) [8 marks]
FUNCTION Sub-B (P1 : REAL) RETURNS REAL One mark per underlined part in each case FUNCTION DeleteComment(Line : STRING) RETURNS STRING
A fitness club has a computerised membership system.
The system stores information for each club member: name, home address, email address, mobile phone number, date of birth and exercise preferences.
Many classes are full, and the club creates a waiting list for each class. The club adds details of members who want to join a class that is full to the waiting list for that class.
When the system identifies that a space is available in one of the classes, a new module will send a text message to each member who is on the waiting list.
(a) Decomposition will be used to break the new module into sub‑modules (sub‑problems). 3 marks
Identify three sub‑modules that could be used in the design and describe their use.
Sub‑module 1
Use
Sub‑module 2
Use
Sub‑module 3
Use
(b) A different part of the program is represented by the following state‑transition diagram. 5 marks
Input-B | Output-W
Assume that the current state for each row is given by the ‘Next state’ on the previous row. For example, the first Input‑A is made when in state S1.
If there is no output for a given transition, then the output cell should contain ‘none’.
The first two rows have been completed.
| Input | Output | Next state |
|---|---|---|
| S1 | ||
| Input‑A | none | S3 |
| Output‑W | ||
| none | ||
| Input‑B | ||
| Input‑A | ||
| S4 |
(ii) Identify the input sequence that will cause the minimum number of state changes in the transition from S1 to S4. 1 mark
Show mark scheme
7(a)
Examples include: Module: IdentifyMember() Use: Identifies a club member who has expressed an interest in a given class Module: GetMemberPhoneNumber() Use: Gets the mobile phone number of a member Module: CreateMessage() Use: Generates a text message to a member Module: SendMessage() Use: Sends a text message to a member in the waiting list One mark for name and use Note: max 3 marks
7(b)(i) [5 marks]
Input Output Next state S1 Input-A none S3 Input-A Output-W S3 Input-B none S2 Input-B none S5 Input-A none S2 Input-A Output-X S4 One mark per row 3 to 7
7(b)(ii) [2 marks]
Input-B, Input-A
A school has a computerised library system that allows students to borrow books for a fixed length of time. The system uses text files to store details of students, books and loans.
A new module is to be written which will generate emails to each student who has an overdue book.
(a) Decomposition will be used to break down the problem of designing the new module into sub-problems. 3 marks
Identify three program modules that could be used in the design and describe their use.
Module 1
Use
Module 2
Use
Module 3
Use
(b) The program designer produces a structure chart for the new module. Part of the structure chart is shown:
(i) Explain the relationship between the four modules shown. 2 marks
(ii) Two new modules are added: Module‑X() and Module‑Y() . 3 marks
Module‑X()has no parameters.Module‑Y()will take a string and a real number as parameters and return a Boolean value.Module‑D()will call eitherModule‑X()orModule‑Y().
Draw only the part of the structure chart that represents the relationship between
Module‑X(), Module‑Y() and Module‑D() .
Show mark scheme
7(a) [2 marks]
Examples include: Module: GetOverdueLoan() Use: Identifies an overdue book Module: IdentifyStudent() Use: Identifies a student (with an overdue book)1 Module: GetStudentEmail() Use: Gets the email address of a student with an overdue book Module: CreateEmail() Use: Generates an email to a student with an overdue book Module: SendEmail() Use: Sends an email to a student with an overdue book One mark for name and use Note: Max 3 marks
7(b)(i)
One mark per point: Module-A calls the other three modules The process is repeated
7(b)(ii) [7 marks]
One mark per bullet point: All rectangles correctly labelled and interconnected All and only parameters as shown Selection diamond FUNCTION IsNewSupp(ThisString : STRING) RETURNS BOOLEAN
A computer system for a shop stores information about each customer. The items of information include name and address (both postal and email) together with payment details and order history. The system also stores the product categories they are interested in and how they would like to be contacted.
(a) The shop wants to add a program module that will generate emails to be sent to customers who may be interested in receiving details of new products.
(i) State three items of information that the new module would need. Justify your choice in each case. 3 marks
Information
Justification
Information
Justification
Information
Justification
(ii) Identify two items of customer information that would not be required by the new module. 2 marks
Justify your choice in each case.
Information
Justification
Information
Justification
(b) The program includes a module to validate a Personal Identification Number (PIN). This is used when customers pay for goods using a bank card. 4 marks
A state‑transition diagram has been produced for this module.
The table show the inputs, outputs and states for this part of the program:
| Current state | Input | Output | Next state |
|---|---|---|---|
| S1 | Input PIN | S2 | |
| S2 | Re‑input PIN | Display error | S2 |
| S2 | Cancel | Re‑prompt | S1 |
| S2 | Valid PIN | Enable payment | S4 |
| S2 | Too many tries | Block Account | S3 |
Complete the state‑transition diagram to represent the information given in the table.
Show mark scheme
7(a)(i)
Correct answers include: Information: customer name Justification: to personalise / address the email Information: email address Justification: so that the email can be delivered correctly Information: product category preference Justification: to check that the customer would be interested in the product Information: contact preference Justification: to check that the customer will accept contact via email Information: order history Justification: to send details of product similar to that already bought // to identify frequent shoppers Information: new product information Justification: to include information about the new product in the email One mark for each piece of information and matching justification Note: Max 3 marks
7(a)(ii) [2 marks]
One mark for each piece of information and matching justification: postal address Justification: sending an email, not a letter payment details Justification: Nothing being bought / sold at this stage order history Justification: Customer preference used to decide if new product is relevant Note: Max 2 marks
7(b) [7 marks]
One mark for each: 1 Line from S1 to S2 and label 2 S2 loop label 3 S3 circle and label on incoming 4 S4 circle and label on incoming FUNCTION CheckInfo(NewLine: STRING) RETURNS BOOLEAN
A school has a library system which allows students to borrow books for a length of time. Information relating to students and books is stored in text files. Student information includes name, home address, email address, date of birth, tutor and subject choices. Book information includes author, title, subject category, library location and the date that the book was borrowed.
A program helps the staff to manage the borrowing of books.
(a) A new module needs to be written to generate emails to send to students who have an overdue book. Students who are sent an email are prevented from borrowing any more books until the overdue book is returned.
The process of abstraction has been used when designing the new module.
(i) State the purpose of applying abstraction to this problem. 1 mark
(ii) Identify one item of information that is required and one item that is not required in the new module. Justify your choices. 2 marks
Item required
Justification
Item not required
Justification
(iii) Identify two operations that would be required to process data when an overdue book is returned. 2 marks
Operation 1
Operation 2
(b) Part of the library program contains program modules with headers as follows: 3 marks
Pseudocode module header
PROCEDURE Module-X()
PROCEDURE Module-Y(BYREF RA : INTEGER, SA : REAL)
PROCEDURE Overlay()
FUNCTION Replace(RA : INTEGER, RB : BOOLEAN) RETURNS BOOLEAN
FUNCTION Reset(TA : STRING) RETURNS INTEGER
Module-X() and Module-Y() are both called from module Overlay() .
Complete the structure chart.
Show mark scheme
7(a)(i) [2 marks]
To filter out information (that is not necessary to solve the problem) // to include only essential information
7(a)(ii) [2 marks]
Required: Student : Student name / email (address) Loan: Return/Issue date Book: Book title Not Required: Student: Home address / DoB / tutor / subject choices Book: Library location / category / author / book title
7(a)(iii) [3 marks]
Max 2 marks Examples could include: Clear the loan // indicate that the book has been returned // update loan history Take the student off 'block' // allow the student to borrow further books Send acknowledgement to the student when book is returned
7(b) [8 marks]
Max 3 marks MP1 All modules correctly labelled and interconnected. MP2 Correct parameters and return type to Module-X and Reset MP3 Correct parameters and return type to Module-Y and Replace MP4 Correct parameters and return type to Overlay and Module-Y FUNCTION ChangeSupp(Code1, Code2 : STRING) RETURNS
The manager of a cinema wants a program to allow users to book seats. The cinema has several screens. Each screen shows a different film.
(a) Decomposition will be used to break the problem down into sub-problems. 3 marks
Describe three program modules that could be used in the design.
Module 1
Module 2
Module 3
(b) Two types of program modules may be used in the design of the program. 1 mark
Identify the type of program module that should be used to return a value.
Show mark scheme
3(a) [3 marks]
One mark per description of appropriate sub-problem for given scenario. Examples include: Allows the user to search for films being shown // input name of film they want to see Allows the user to search for available seats Calculate cost of booking Book a given number of seats for a particular screening
3(b) [1 mark]
Function
(a) A programmer applies decomposition to a problem that she has been asked to solve. 2 marks
Describe decomposition.
(b) The following pseudocode assigns a value to an element of an array: 3 marks
ThisArray[n] 42
# ←
Complete the following table by writing the answer for each row.
| Answer | |
|---|---|
The number of dimensions ofThisArray |
|
| The technical terms for minimum and maximum values that the variable n may take |
|
The technical term for the variablen in thepseudocode statement |
(c) Complete the pseudocode expressions so that they evaluate to the values shown. 4 marks
| Any functions and operators used must be defined in the insert. | |
|---|---|
| Expression | Evaluates to |
______ ('C') |
67 |
2 *______ ("27") |
54 |
(27 /) |
13 |
"Sub" & ("Abstraction",, ______) |
"Subtract" |
Show mark scheme
1(a)
The process involves: 1 Breaking down a problem / task into sub problems / steps / smaller parts 2 In order to explain / understand // easier to solve the problem 3 Leading to the concept of program modules // assigning problem parts to teams Max 2
1(b) [4 marks]
The number of dimensions of 1 ThisArray The technical terms for minimum and Lower bound, upper bound maximum values that variable may take n The technical term for the variable in the Index / Subscript n pseudocode expression. One mark per row
1(c) [2 marks]
Expression Evaluates to ('C') 67 ASC 2 * ("27") 54 STR_TO_NUM (27 / ) 13 INT 2 "Sub" & ("Abstraction" , , ) "Subtract" MID 4 5 One mark per row Function names must be exactly as shown
1(d)
Expression Evaluates to FALSE PressureOK AND HiFlow TRUE PumpOn OR PressureOK TRUE NOT PumpOn OR (PressureOK AND NOT HiFlow) FALSE NOT (PumpOn OR PressureOK) AND NOT HiFlow 1 mark for any two rows correct 2 marks for all rows correct.