Past questions › sdd2024-q30
2024 7 marks Extended response The Software Engineering Project (Year 12) Algorithm design (random allocation); testing with stubs
NESA 2024 HSC Software Design and Development (OLD syllabus) - Section II Question 30, with NESA Marking Guidelines
For a particular concert, there are 10 000 tickets available, and 2000 customers wanting to buy tickets. Customers are allocated tickets randomly. Customers are required to indicate the number of tickets they would like to purchase, up to a limit of 8. Seats are not allocated until all ticket requests have been entered. Details of the 2000 customers are already stored, in no particular order, in an array of records called Customer_Array. Each customer record has the following structure: Cust_ID | : String Name | : String Num_Tickets : Integer Allocated | : Boolean (becomes TRUE when tickets have been allocated) For example: Cust_ID | Name | Num_Tickets | Allocated Wong4567 | Wong, F | 1 | FALSE Jones34 | Jones, Q | 3 | FALSE (a) | An algorithm called AllocateTickets is required to allocate ticket numbers to | 5 customers. Customers are selected at random to receive their requested tickets until all available tickets are allocated. The tickets allocated will always be sequentially numbered. The Cust_ID of the chosen customers are stored next to the relevant ticket number in a 10 000-element array of records called Ticket_Array. For example: TicketNumber | AllocatedCustomer 1 | Jones34 2 | Jones34 3 | Jones34 4 | Abu507 5 | Abu507 9998 | Wong4567 9999 | Rakash234 10000 | Rakash234 As the last tickets are allocated, a customer may not get all the tickets they have requested (as there may be no more tickets left). Some customers may not be allocated any tickets at all. In the example shown above, even if Rakash234 requested five tickets, there will only be two allocated because that is all that is left. Design an appropriate algorithm for AllocateTickets. You may use this function: • Rand (Min, Max) generates a random integer between Min and Max, inclusive (b) | The algorithm AllocateTickets, as described in part (a), is implemented as code. | 2 Explain why the function Rand(), as described in part (a), cannot be a stub during the testing of this code. 2024 HIGHER SCHOOL CERTIFICATE EXAMINATION Centre Number Software Design and Development | Student Number
Marking criteria
[Question 30 (a)] Criteria | Marks • Provides a substantially correct algorithm that includes the following features: – Randomly allocates customers one at a time from the customer array using a loop | 5 – Allocates the correct number of tickets – Updates array(s) correctly – Deals correctly with last few remaining tickets • Provides an algorithm that addresses most of the key aspects of the problem • Provides an algorithm that addresses some key aspects of the problem | 3 • Provides an algorithm that shows some understanding of the problem | 2 • Shows some understanding of the problem | 1 Criteria | Marks • Provides an explanation of the use of this stub in testing | 2 • Shows some understanding of a stub | 1
Sample answer
Sample answer: BEGIN AllocateTickets TixIndex = 1 WHILE TixIndex < 10000 Pos = Rand (1, 2000) IF (CustomerArray[Pos].Allocated = FALSE) THEN IF (TixIndex + CustomerArray[Pos].Num_Tickets > 10000) THEN NumToInsert = 10000 – TixIndex ELSE NumToInsert = CustomerArray[Pos].Num_Tickets ENDIF UserToInsert = CustomerArray[Pos].CustId Allocate(UserToInsert, NumToInsert, TixIndex) CustomerArray[Pos].Allocated = TRUE ENDIF ENDWHILE END AllocateTickets BEGIN Allocate(CustId, Num_Tickets, TixIndex) FOR i = 1 to Num_Tickets Ticket_Array[TixIndex].AllocatedCustomer = CustId Add 1 to TixIndex NEXT i END Allocate
[Question 30 (b)] Sample answer: For the function Rand(), it is critical that it returns relevant values (in this case a random number in the specified range). It is not possible to write a stub that can pass back the required values to fully test the main program logic without including the logic to generate the random numbers required by the calling program, to enable it to allocate tickets meaningfully.