Question
A class of students are developing a program to send data between computers. Many computers are connected together to form a wired network. Serial ports are used to connect one computer to another.
Each computer:
• is assigned a unique three-digit ID
• has three ports, each identified by an integer value
• is connected to between one and three other computers.
Data is sent as individual message strings.
Each string contains the destination ID (the ID of the computer that is to receive the message) followed by the data:
<DestinationID><Data>
Messages may pass through several computers on the way to their destination.
When a message arrives at a computer, that is not the destination, the program needs to forward it on to another computer using one of its serial ports.
The port to use is obtained from information that is stored in an array RouteTable.
RouteTable is a global 2D array of integers. It is declared in pseudocode as follows:
DECLARE RouteTable : ARRAY[1:6,1:3] OF INTEGER
The values in the first two columns of RouteTable define a range of ID values.
Column 3 gives the corresponding port number to use when forwarding the message to a computer with an ID within this range.
For example, the contents of RouteTable could be:
Column 1 Column 2 Column 3
Row 1 100 199 1
Row 2 200 259 2
Row 3 −1 <undefined> <undefined>
Row 4 260 399 2
Row 5 400 599 3
Row 6 600 999 1
In this example, a message that arrives with a DestinationID of "283" will be forwarded using port 2.
Row 3 in the example shows an unused row. These may occur anywhere. Unused rows have the column 1 element set to −1. The value of unused elements in the other two columns is undefined.
The programmer has defined the first program module as follows:
Module Description
• takes a DestinationID as a parameter of type string
• searches for the range corresponding to the DestinationID
GetPort() in the array
• returns the port number, or returns −1 if no corresponding range is found
(a) Write pseudocode for module GetPort().
Assume DestinationID contains a valid three-digit string.
…… [7]
(b) Copies of the same program will run on each computer. The program contains a global variable MyID of type string, which contains the unique ID of the computer in which the program is running.
When messages are received, they are placed on one of two stacks. Stack 1 is used for messages that have reached their destination and stack 2 is used for messages that will be forwarded on to another computer.
Additional modules are defined:
Module Description
• takes two parameters:
○ a string representing a message
StackMsg() ○ an integer representing the stack number
(already written) • adds the message to the required stack
• returns TRUE if the message is added to the required stack, otherwise returns FALSE
• takes a message as a parameter of type string
• ignores any message with a zero-length data field
• extract the DestinationID from the message
• checks whether the DestinationID is this computer or
ProcessMsg() whether the message is to be forwarded
• uses StackMsg() to add the message to the appropriate stack
• outputs an error if the message could not be added to the stack
Write pseudocode for module ProcessMsg().
Module StackMsg() must be used.
…… [7]
(c) The program contains a module GetFile() which receives text files sent from another computer.
Lines from the file are sent one at a time. Each message contains one line and ProcessMsg() from part (b) adds each message as it is received onto stack 1.
Module GetFile() removes messages from stack 1 and writes the data to a text file.
There is a problem. Under certain circumstances, the received file does not appear as expected.
Assume that while a file is being received ProcessMsg() receives only messages containing lines from the file.
(i) Describe the circumstances and explain the problem.
Circumstances ……
Explanation ……
[3]
(ii) Suggest a more appropriate Abstract Data Type that could be used to store the messages that would not have the same problem.
…… [1]
Mark scheme
8(a) Solution using a loop 7
Example solution – using a loop
FUNCTION GetPort(ThisDest : STRING) RETURNS INTEGER
DECLARE Index, DNum, Port : INTEGER
DNum ← STR_TO_NUM(ThisDest)
Index ← 1
Port ← -1
REPEAT
IF RouteTable[Index, 1] <> -1 THEN
IF DNum >= RouteTable[Index, 1] AND __
DNum <= RouteTable[Index, 2] THEN
Port ← RouteTable[Index, 3]
ENDIF
ENDIF
Index ← Index + 1
UNTIL Index = 7 OR Port <> -1 // end of array or
range found
RETURN Port
ENDFUNCTION
Mark as follows Max 7:
1.Function heading and ending including parameter and return type
2 Convert parameter to a number
3 (Conditional) loop through array
4 Skip unused element in a loop
5 Attempt to check one range with destination in a loop
6 Test all ranges correctly with destination in a loop
7 Store port value if destination matched in a loop (and exit loop)
8 Return port value including -1 if no match found
Solution using selection statement(s)
Example solution
FUNCTION GetPort(ThisDest : STRING) RETURNS INTEGER
DECLARE Index, DNum, Port : INTEGER
DNum ← STR_TO_NUM(ThisDest)
Port ← -1
IF RouteTable[1, 1] <> -1 AND RouteTable[1, 1] >= DNum
AND RouteTable[1, 2] <= DNum THEN
8(a) Port ← RouteTable[1, 3]
END IF
IF RouteTable[2, 1] <> -1 AND RouteTable[2, 1] >= DNum
AND __ RouteTable[2, 2] <= DNum THEN
Port ← RouteTable[2, 3]
END IF
IF RouteTable[3, 1] <> -1 AND RouteTable[3, 1] >= DNum
AND __ RouteTable[3, 2] <= DNum THEN
Port ← RouteTable[3, 3]
END IF
IF RouteTable[4, 1] <> -1 AND RouteTable[4, 1] >= DNum
AND __ RouteTable[4, 2] <= DNum THEN
Port ← RouteTable[4, 3]
END IF
IF RouteTable[5, 1] <> -1 AND RouteTable[5, 1] >= DNum
AND __ RouteTable[5, 2] <= DNum THEN
Port ← RouteTable[5, 3]
END IF
IF RouteTable[6, 1] <> -1 AND RouteTable[6, 1] >= DNum
AND __ RouteTable[6, 2] <= DNum THEN
Port ← RouteTable[6, 3]
END IF
RETURN Port
ENDFUNCTION
Mark as follows Max 7:
1 Function heading and ending including parameter and return type
2 Convert parameter to a number
3 Skip all unused elements
4 Attempt to check one range
5 Check two ranges with destination correctly
6 Check all ranges with destination correctly
7 Store port value if destination matched
8 Return port value including -1 if no match found
8(b) Example solution 7
PROCEDURE ProcessMsg(ThisMsg : STRING)
DECLARE ThisDest : STRING
DECLARE Response : BOOLEAN
DECLARE StackNum : INTEGER
IF LENGTH(ThisMsg) >= 4 THEN
ThisDest ← LEFT(ThisMsg, 3)
IF ThisDest = MyID THEN // It's for this computer
StackNum ← 1
ELSE
StackNum ← 2
ENDIF
Response ← StackMsg(ThisMsg, StackNum)
IF Response = FALSE THEN
OUTPUT "Message discarded - no room on stack"
ENDIF
ENDIF
ENDPROCEDURE
Mark as follows:
1. Ignore message if data field is empty
2. Extract ThisDest from ThisMsg
3. Test if destination is this computer
4. Attempt to use StackMsg()
5. Fully correct use of StackMsg()for both cases / stacks
6. Test StackMsg() return value for both cases
7. Following a reasonable attempt at MP6 output warning if StackMsg()
returns FALSE
8(c)(i) One mark per point Max 3 marks: 3
Decide on scenario and mark accordingly.
Scenario one:
• If more than one line is / all lines are stored on the stack (before line(s)
are removed)
• The stack operates as a FILO device // Last item added to stack will be in
first item out
• So lines in the file appear out of sequence
Scenario two:
• Stack is Full
• Not all lines can be stored on the stack
• so resulting file will not contain all the original lines
Scenario three:
• (All) the data in a line read can’t be stored on the stack
• Stack elements have not been allocated enough memory
• so only part of each line is stored in the file
Scenario four:
• Stack is empty
• The stack is being read faster than it is being written to
• so blank lines may be inserted into the file
8(c)(ii) Queue 1