SDD Questions - testnaman

An algorithm for performing a binary search for a given word from a set of individual words has been written and appears as follows:

BEGIN binary_search

INITIALISATION
    set lower to position of first word
    set upper to position of last word
    set found to false
    get target
END INITIALISATION

REPEAT

    find_middleposition

    IF target equals data at middleposition THEN
        set found to true
    ELSE IF target < data at middleposition THEN
        set upper to middleposition
    ELSE
        set lower to middleposition
    ENDIF

UNTIL found is true OR position of lower > position of upper

IF found is true THEN
    report data at found position
ELSE
    report target not present
ENDIF

END

BEGIN subprogram find_middleposition
set middleposition to (upper+lower)/2
set middleposition to integer part of middle
END

(a)

(i)

If the data to be searched is in the form of individual words, describe the preconditions which must be satisfied for this algorithm to work correctly.

Suggested answer

The data must be pre-sorted into alphabetic order

Criteria	Marks
Correct answer	2
Only states that the data must be pre-ordered	1

(ii)

Select and justify your choice of a suitable data type for the input to this algorithm.

Suggested answer

The data should be an array of strings

Criteria	Marks
Selects and justifies a suitable data type	2
States array only	1

(b)

(i)

Justify the decision to write the calculation of the middle position as a subprogram.

Suggested answer

The algorithm is easier to follow if seperate processes are specified
This subprogram may be reused in another part of the program
Debugging is aided by modular approach

Criteria	Marks
Provides a thorough justification	2
Poorly justified answer	1

(b)

(ii)

Explain the way in which the subprogram finds the middle position of a given number of words.

Suggested answer

Total of items is determined then halved. This results in pointer to halfway point in case of odd (for 5 items > 1+5=6 > 6+2=3) and fractional value in case of even number of items where there is no item at halfway point. By taking the integer part of the number in each case the pointer correctly points to an actual value or just below halfway.

Criteria	Marks
Gives a complete and thorough explanation	3
Gives an incomplete explanation or a pooly explained answer	1-2

(c)

Outline in words the steps this algorithm uses to search for a given word.

Suggested answer

The data is divided into two parts. the half with the target item is kept and the other half is discarded. This process continues until either a match occurs or there is no more data.
After each division only 3 possibilities present themselves:
- the target is at the point of this division
- the target is to the left of this division
- the target is to the right of this division

Criteria	Marks
Gives a complete explanation	5
Omits second half of explanation	3-4
Poor attempt at explanation	1-2

(d)

This algorithm contains an error. Perform TWO desk checks on this algorithm using the sets of input data that follow. Present your checks in tabular form. Explain the output from each of these two checks and suggest how the algorithm should be corrected.

Suggested answer

input	target	upper	lower	middlepos	found
apple, banana, orange	orange	4	1	2	false
	orange	4	2	3	true

input	target	upper	lower	middlepos	found
apple, banana, orange	orange	3	1	2	false
	orange	3	2	2	false
	orange	3	2	2	false
				etc	etc

(never reaches target word)

Target is not found if it is the last lement as the action of taking the integer part of a sublist with an odd number of elements will never reach the last integer (upper)
It is NOT a solution to change this runding as this will now not work where seacrh word is first in the list and fractional values appear for length of sub list
Solution is as follows:

IF target equals data at middleposition THEN set found to true set position to middleposition ELSE IF target < data at middleposition THEN set upper to middleposition -1 ELSE set lower to middleposition -1 ENDIF

Criteria	Marks
Presents TWO desk checks in tabular form Explains the output from the TWO checks and suggests how the algorithm should be corrected	6
Omits corrected algorithm OR performs ONE desk check only OR answer has minor errors	3-5
Omits TWO or more items in the desk check	1-2

Examine the following algorithm written in pseudocode:

BEGIN Pattern_search

Initialisation_goes_here

REPEAT
    IF Pattern[PatternPos] equals Text[TextPos] THEN
        TextPos=TextPos+1
        PatternPos=PatterPos+1

    ELSE
        reset_values
    ENDIF

UNTIL (PatternPos>length of search pattern) OR (TextPos>length of text)

report_any_matches

END

(a)

Write pseudocode for the initialisation section marked Initialisation_goes_here, if the maximum length of the text to be searched is 100 characters.

Suggested answer

INITIALISATION
Text as Array of length 100
Pattern as Array of length 100
set TextPos to 1
set PatternPos to 1
ENDINITIALISATION

Criteria	Marks
Correct pseudocode	2
Pseudocode has minor errors	1

(b)

If there is a failure to match, the code following the ELSE statement is reached, marked here as reset_values.

(i)

Identify the values which must be reset and justify the order in which they must be reset.

Suggested answer

TextPos and PatternPos
TextPos before PatternPos

Criteria	Marks
Identifies values and justifies their order	2
One error in answer	1

(ii)

Write pseudocode for the section marked reset_values and explain the logic of your answer.

Suggested answer

patternPos=1
TextPos=(TextPos-PatternPos) + 2
Since we have to go back to the Pos where the search started matching then add 1. The start will be PatterPos-1 elements back

Criteria	Marks
Correct pseudocode and explanation	4
One mark off for each error	1-3

(iii)

The algorithm does not indicate whether or not a match has occurred after the repeat loop has exited. Write pseudocode for the section marked report_any_matches and explain the logic of your answer

Suggested answer

If the value of PatternPos>length of search then match has occurred
(place this after the loop)
logic: this only occures when the search pattern has matched

Criteria	Marks
Correct pseudocode and explanation	2
One mark off for logic failure or pseudocode error	1

(c)

The programmer has been asked to add a feature to this algorithm to allow a '?' symbol to match any character. Write pseudocode to perform this function.

Suggested answer

Increment PatternPos and TextPos by 1 if the current element in Pattern equals '?'

Criteria	Marks
Correct pseudocode	2
Incorrect logic	0-1

(d)

(i)

Outline the steps a software programmer should take prior to coding this module for use in a software application.

Suggested answer

Desk checking thoroughly
Volume real data testing
User testing
Test on many systems

Criteria	Marks
Thoroughly outlines steps a programmer should take prior to coding the module	2
Less than THREE steps outlined	1

(ii)

Identify ONE other feature which could be added to dhis algorithm

Suggested answer

wildcards

Criteria	Marks
Identifies one other feature	2
Poor response	1

(e)

In coding the algorithm, the programmer should produce documentation. Describe THREE of these types of documentation and justify their inclusion.

Suggested answer

Internal
Intrinsic
Manual
Installation
Gantt chart
Structure chart

Criteria	Marks
Describes THREE types of documentation a programmer should produce	4
No justification OR no description OR fewer than THREE items provided	1-3

Evolution of programming languages

(a)

Convergence is a common contemporary characteristic of computer-based hardware. Discuss how convergence influences the development of programming paradigms.

Suggested answer

Internal
Intrinsic
Manual
Installation
Gantt chart
Structure chart

Criteria	Marks
Describes THREE types of documentation a programmer should produce	4
No justification OR no description OR fewer than THREE items provided	1-3

(b)

(i)

Describe the nature and purpose of an assembler

Suggested answer

Objext oriented paradigm is a suitable match for hardware in which disparate items must talk to each other as the paradigm is based on encapsulation principles

Criteria	Marks
Provides an accurate discussion about how convergence influences the development of programming paradigms	2
Provides a response that lacks detail or a clear explanation	1

(ii)

Compare and contranst the two systems of categorising computing languages: as generations and as paradigms.

Suggested answer

Internal
Intrinsic
Manual
Installation
Gantt chart
Structure chart

Criteria	Marks
Describes THREE types of documentation a programmer should produce	4
No justification OR no description OR fewer than THREE items provided	1-3

(a)

Convergence is a common contemporary characteristic of computer-based hardware. Discuss how convergence influences the development of programming paradigms.