Past questions › sdd2021-q30
2021 4 marks Extended response The Software Engineering Project (Year 12) Algorithm design (string matching)
NESA 2021 HSC Software Design and Development (OLD syllabus) - Section II Question 30, with NESA Marking Guidelines
A subroutine IsMatch(string, BigString) is needed to check if a string is found in a bigger | 4 string. The following library routines are available: • length(string) which returns the number of characters in the string • extract(string, start, length) which extracts length characters from string beginning at character start. If text = ‘software’, then extract(text, 2, 4) will return ‘oftw’. Design the algorithm for IsMatch(string, BigString).
Marking criteria
[Question 30] Criteria | Marks • Provides a substantially correct algorithm that includes the following features: – Looks for a match in the description | 4 – Checks the required number of characters – Uses the library routines appropriately • Provides an algorithm that addresses most of the features | 3 • Provides an algorithm that attempts to address some features | 2 • Shows some understanding of the problem | 1
Sample answer
Sample answer: BEGIN IsMatch (string, BigString ) Located = FALSE NumToCheck = length (BigString) – length (string) + 1 FOR j = 1 to NumToCheck Check = extract (BigString, j, length (string)) IF Check = string THEN Located = TRUE ENDIF NEXT j RETURN Located END IsMatch