2.1. Algorithm design and problem-solving
A subsection of Computer Science, 9608, through 2. Fundamental Problem-solving and Programming Skills
Listing 6 of 6 questions
A large office building has many floors. On each floor there are security sensors and security cameras. There is the same number of sensors on each floor. The building has a single security room. The images from the security cameras are output on monitors (one monitor for each floor) placed in the security room. The data from the sensors are read and processed by a computer system. Sensor readings and warning messages can be displayed on the monitors. State the name given to the type of system described. Explain your answer to part . State two sensors that could be used in this system. Sensor 1 Sensor 2 A software routine: • checks the readings from the sensors • outputs readings and warning messages to the monitors • loops continuously. The routine uses the following pseudocode variables: Identifier Data type Description FloorCounter INTEGER Loop counter for number of floors SensorCounter INTEGER Loop counter for number of sensors NumberOfFloors INTEGER Stores the number of floors NumberOfSensors INTEGER Stores the number of sensors ForEver BOOLEAN Stores value that ensures continuous loop Complete the following pseudocode algorithm for the routine. 01 ForEver 02 REPEAT 03 FOR FloorCounter 1 TO NumberOfFloors 04 FOR SensorCounter 1 TO 05 READ Sensor(SensorCounter)on Floor(FloorCounter) 06 IF Sensor value outside range 07 THEN 08 OUTPUT “Problem on Floor ”, FloorCounter 09 ENDIF 10 ENDFOR 11 ENDFOR 12 // 13 // Delay loop 14 // Delay loop 15 // 16 UNTIL A delay needs to be introduced before the loop is processed again. Write a FOR loop, in pseudocode, to replace lines 13 and 14. Give a reason for this delay in the system. An alternative method of reading and processing sensor data is to use interrupts. Each sensor is connected so that it can send an interrupt signal to the processor if its value changes. On receipt of an interrupt signal, the processor carries out a number of steps as shown in the following diagram. Interrupt 1. Disable interrupts Return to task 6. Enable interrupts 2. Save current task 3. Identify source of interrupt 4. Jump to Interrupt Service Routine 5. Restore task State the purpose of step 3. Explain what happens at step 4.
9608_s17_qp_32
THEORY
2017
Paper 3, Variant 2
View
A large apartment block has 20 floors. On each floor there is one security camera and four sensors. The image from each security camera is output to a display screen for that floor. • There are 20 display screens in the reception area on the lowest floor. • The data from the sensors are read and processed by a computer system. • Warning messages can also be displayed on each display screen. Identify the type of system described. Justify your answer to part . Identify two types of sensor that could be used by this system. State a reason for the use of each sensor. Sensor 1 Reason Sensor 2 Reason A program regularly checks each sensor’s readings. If the value of the reading is out of range, a warning message is displayed on the screen for that floor. A pseudocode algorithm to output the warnings has been written using these identifiers. Identifier Data type Description FloorNumber INTEGER Floor number SensorNumber INTEGER Sensor number Always BOOLEAN Value to ensure continuous loop The pseudocode algorithm uses: • the function CheckSensor(Floor, Sensor) that returns TRUE if the sensor reading is out of range and FALSE otherwise • the procedure ScreenOut(Floor, Sensor) that outputs the warning message "Problem on Floor" to the appropriate screen. Complete the pseudocode algorithm. 01 Always ………………………………………………………………………… 02 REPEAT 03 FOR FloorNumber 1 TO ………………………………………………………………………… 04 FOR SensorNumber 1 TO ………………………………………………………………………… 05 IF CheckSensor(FloorNumber, SensorNumber) 06 THEN 07 ScreenOut(FloorNumber, SensorNumber) 08 ENDIF 09 ENDFOR 10 ENDFOR 12 // delay loop 13 // delay loop 14 UNTIL ………………………………………………………………………… Write a delay loop in pseudocode for lines 12 and 13 of the pseudocode algorithm. If a sensor reading is out of range, a bit is set in a memory location allocated to that floor. The addresses for the memory locations are 401 to 420. For example, memory location 401 is used to store the status of the sensors 1 to 4 on floor 1, memory location 402 is used to store the status of the sensors 1 to 4 on floor 2. The table shows data for some of the floors, with sensor 1 on floor 1 set, sensor 2 on floor 2 set and sensors 3 and 4 on floor 20 set. Bits Memory location Sensor number Floor … … … … … … … … … … The data in memory location 410 is shown. State what this data represents. Explain the way in which the data from sensor 3 on floor 7 can be checked. To avoid the issue of disclosure of answer-related information to candidates, all copyright acknowledgements are reproduced online in the Cambridge Assessment International Education Copyright Acknowledgements Booklet. This is produced for each series of examinations and is freely available to download at www.cambridgeinternational.org after the live examination series.
9608_w21_qp_31
THEORY
2021
Paper 3, Variant 1
View
A large car park has 6 floors. There is a large screen at the entrance to the car park. This screen displays the number of empty parking spaces on each floor. • There are 256 parking spaces for cars on each floor. • Each parking space has a sensor that detects if a car is parked on it. • Data from the sensors are read and processed by a computer system. Identify the type of system described. Justify your answer to part . Identify two types of sensor that could be used by this system. Sensor 1 Sensor 2 A program regularly checks each sensor’s readings. The number of empty parking spaces is displayed on the screen for each floor. If there are no empty parking spaces on a floor, a message is displayed on the screen to show that the floor is full. The pseudocode algorithm to display this information has been written using these identifiers. Identifier Data type Description FloorNumber INTEGER Floor number SpaceNumber INTEGER Parking space number SpaceAvailable INTEGER Counts number of empty parking spaces on a floor ForEver BOOLEAN Value to ensure continuous loop The pseudocode algorithm uses the function CheckSpace(Floor, Space). This function returns TRUE if the parking space is empty and FALSE otherwise. Complete the following pseudocode algorithm to check the number of parking spaces available. 01 ForEver ………………………………………………………………………… 02 REPEAT 03 FOR FloorNumber 1 TO ………………………………………………………………………… 04 SpaceAvailable 05 FOR SpaceNumber 1 TO ………………………………………………………………………… 06 IF CheckSpace(FloorNumber, SpaceNumber) 07 THEN 08 SpaceAvailable SpaceAvailable + 1 09 ENDIF 10 ENDFOR 11 IF SpaceAvailable > ………………………………………………………………………… 12 THEN 13 OUTPUT "Floor ", …………………………………………………………………………, " empty parking spaces "………………………………………………………………………… 14 ELSE 15 OUTPUT "Floor ", …………………………………………………………………………, " full" 16 ENDIF 17 ENDFOR 19 // delay loop 20 // delay loop 21 UNTIL ………………………………………………………………………… Write a delay loop in pseudocode for lines 19 and 20 of the pseudocode algorithm. State why a delay loop is used in this system. When a car is parked in a parking space, a bit is set in the appropriate memory location. • 32 memory locations are used for each floor with address X01 to X32, where X is the number of the floor. • Each location is one byte in length to hold the data for 8 parking spaces. For example, memory location 101 is used for parking spaces 1 to 8 and memory location 102 is used for parking spaces 9 to 16. The table shows part of floor 1 with cars parked in parking spaces 4, 11, 16 and 255. Memory location Bits Parking space number 8 – 1 16 – 9 … … … … … … … … … … 256 – 249 The data in memory location 604 is shown. State what this data represents. Explain the way in which the parking space 254 on floor 5 can be checked to see if it is empty.
9608_w21_qp_32
THEORY
2021
Paper 3, Variant 2
View
A large apartment block has 20 floors. On each floor there is one security camera and four sensors. The image from each security camera is output to a display screen for that floor. • There are 20 display screens in the reception area on the lowest floor. • The data from the sensors are read and processed by a computer system. • Warning messages can also be displayed on each display screen. Identify the type of system described. Justify your answer to part . Identify two types of sensor that could be used by this system. State a reason for the use of each sensor. Sensor 1 Reason Sensor 2 Reason A program regularly checks each sensor’s readings. If the value of the reading is out of range, a warning message is displayed on the screen for that floor. A pseudocode algorithm to output the warnings has been written using these identifiers. Identifier Data type Description FloorNumber INTEGER Floor number SensorNumber INTEGER Sensor number Always BOOLEAN Value to ensure continuous loop The pseudocode algorithm uses: • the function CheckSensor(Floor, Sensor) that returns TRUE if the sensor reading is out of range and FALSE otherwise • the procedure ScreenOut(Floor, Sensor) that outputs the warning message "Problem on Floor" to the appropriate screen. Complete the pseudocode algorithm. 01 Always ………………………………………………………………………… 02 REPEAT 03 FOR FloorNumber 1 TO ………………………………………………………………………… 04 FOR SensorNumber 1 TO ………………………………………………………………………… 05 IF CheckSensor(FloorNumber, SensorNumber) 06 THEN 07 ScreenOut(FloorNumber, SensorNumber) 08 ENDIF 09 ENDFOR 10 ENDFOR 12 // delay loop 13 // delay loop 14 UNTIL ………………………………………………………………………… Write a delay loop in pseudocode for lines 12 and 13 of the pseudocode algorithm. If a sensor reading is out of range, a bit is set in a memory location allocated to that floor. The addresses for the memory locations are 401 to 420. For example, memory location 401 is used to store the status of the sensors 1 to 4 on floor 1, memory location 402 is used to store the status of the sensors 1 to 4 on floor 2. The table shows data for some of the floors, with sensor 1 on floor 1 set, sensor 2 on floor 2 set and sensors 3 and 4 on floor 20 set. Bits Memory location Sensor number Floor … … … … … … … … … … The data in memory location 410 is shown. State what this data represents. Explain the way in which the data from sensor 3 on floor 7 can be checked. To avoid the issue of disclosure of answer-related information to candidates, all copyright acknowledgements are reproduced online in the Cambridge Assessment International Education Copyright Acknowledgements Booklet. This is produced for each series of examinations and is freely available to download at www.cambridgeinternational.org after the live examination series.
9608_w21_qp_33
THEORY
2021
Paper 3, Variant 3
View
A company has a number of lorries that deliver items around the country. The items in each lorry are its load. Each lorry has a monitoring system that provides information to the driver about the state of the load and other data from each trip. • Data is stored in three memory locations with addresses 801 to 803. • Location 801 contains the distance travelled in kilometres for the current trip, stored as a binary integer. • Location 802 contains the quantity of fuel used in litres for the current trip, stored as a fixed-point binary number with six places before the binary point and two places after the binary point. • The four most significant bits of location 803 are flags used to identify problems with the load, for example it is too heavy. A flag is set to 1 if there is a problem, or 0 if not. The problems are: • Bit 7 – load too heavy • Bit 6 – load too high • Bit 5 – load unstable • Bit 4 – load not secured (risk of the load falling off) • Bits 0 to 3 are not used The current contents of addresses 801 to 803 are: Most significant bit Least significant bit State the information that the current contents of addresses 801 to 803 will provide to the driver. A lorry has a load that is too heavy and is not secured. It has travelled 120 kilometres and used 35.25 litres of fuel. Complete the contents of the addresses to record this information. The following table shows the instructions for the lorry load monitoring system in assembly language. There is one general purpose register, the Accumulator (ACC). Table 7.1 Instruction Explanation Label Op code Operand LDM #n Load the number n to ACC LDD Load the contents of the location at the given address to ACC STO Store the contents of ACC at the given address AND #n Bitwise AND operation of the contents of ACC with the operand CMP #n Compare the contents of ACC with number n JPE Following a compare instruction, jump to or if the compare was True JMP Jump to the given address or label : Labels an instruction Note: # denotes immediate addressing B denotes a binary number, for example B01001010 & denotes a hexadecimal number, for example &4A Write assembly language instructions to set the contents of addresses 801 and 802 to zero, and set all four most significant bits of the contents of address 803 to one. Use the instruction set from Table 7.1. A program written in assembly language, continuously checks the flags. If a flag is set, the program jumps to the error-handling routine at the specified label. For example, if the load is too heavy, the program jumps to the error-handling routine with the label TOOHEAVY. The error-handling routine instructions have not been provided. A programmer has written most of the instructions for the program in the following table. There are four missing operands. Complete the assembly language program by writing the four missing operands. Label Op code Operand CHECKLOAD: LDD AND &F0 STO TEMP AND &80 CMP &80 JPE TOOHEAVY LDD TEMP AND &40 CMP JPE TOOHIGH LDD TEMP AND CMP &20 JPE UNSTABLE LDD AND &10 CMP &10 JPE NOTSECURED JMP TEMP:
9608_w20_qp_31
THEORY
2020
Paper 3, Variant 1
View
A company has a number of lorries that deliver items around the country. The items in each lorry are its load. Each lorry has a monitoring system that provides information to the driver about the state of the load and other data from each trip. • Data is stored in three memory locations with addresses 801 to 803. • Location 801 contains the distance travelled in kilometres for the current trip, stored as a binary integer. • Location 802 contains the quantity of fuel used in litres for the current trip, stored as a fixed-point binary number with six places before the binary point and two places after the binary point. • The four most significant bits of location 803 are flags used to identify problems with the load, for example it is too heavy. A flag is set to 1 if there is a problem, or 0 if not. The problems are: • Bit 7 – load too heavy • Bit 6 – load too high • Bit 5 – load unstable • Bit 4 – load not secured (risk of the load falling off) • Bits 0 to 3 are not used The current contents of addresses 801 to 803 are: Most significant bit Least significant bit State the information that the current contents of addresses 801 to 803 will provide to the driver. A lorry has a load that is too heavy and is not secured. It has travelled 120 kilometres and used 35.25 litres of fuel. Complete the contents of the addresses to record this information. The following table shows the instructions for the lorry load monitoring system in assembly language. There is one general purpose register, the Accumulator (ACC). Table 7.1 Instruction Explanation Label Op code Operand LDM #n Load the number n to ACC LDD Load the contents of the location at the given address to ACC STO Store the contents of ACC at the given address AND #n Bitwise AND operation of the contents of ACC with the operand CMP #n Compare the contents of ACC with number n JPE Following a compare instruction, jump to or if the compare was True JMP Jump to the given address or label : Labels an instruction Note: # denotes immediate addressing B denotes a binary number, for example B01001010 & denotes a hexadecimal number, for example &4A Write assembly language instructions to set the contents of addresses 801 and 802 to zero, and set all four most significant bits of the contents of address 803 to one. Use the instruction set from Table 7.1. A program written in assembly language, continuously checks the flags. If a flag is set, the program jumps to the error-handling routine at the specified label. For example, if the load is too heavy, the program jumps to the error-handling routine with the label TOOHEAVY. The error-handling routine instructions have not been provided. A programmer has written most of the instructions for the program in the following table. There are four missing operands. Complete the assembly language program by writing the four missing operands. Label Op code Operand CHECKLOAD: LDD AND &F0 STO TEMP AND &80 CMP &80 JPE TOOHEAVY LDD TEMP AND &40 CMP JPE TOOHIGH LDD TEMP AND CMP &20 JPE UNSTABLE LDD AND &10 CMP &10 JPE NOTSECURED JMP TEMP:
9608_w20_qp_33
THEORY
2020
Paper 3, Variant 3
View
Questions Discovered
6