6.11. Understanding Algorithms

You’ll often be faced with new algorithms and it is an important skill for you to be able to read through the algorithm and figure out what the algorithm is meant to do. Have a go at trying to understand the algorithms given below.

Question 1

Determine the purpose of the algorithm given below. Note that \(n\) is expected to be a positive integer.

BEGIN
    Get n
    total = 0
    i = 0
    WHILE total <= n
        i = i + 1
        total = total + i
    ENDWHILE
    largest = i - 1
    Display largest
END

1. It sums all positive integers between 0 and \(n\), e.g. if \(n=5\) this program would output \(1 + 2 + 3 + 4 + 5 = 15\).

2. It sums all positive integers between 0 and up to but not including \(n\), e.g. if \(n=5\) this program would output \(1 + 2 + 3 + 4 = 10\).

3. It finds the number largest such that the sum of positive integers between 0 and largest does not exceed \(n\), e.g. if \(n=11\) this program would output 4 because \(1 + 2 + 3 + 4\) is the sum of consecutive integers that gets you closest to 11 without exceeding 11.

4. It finds the number largest such that \(i-1\) still gives you a value less than or equal to \(n\).

Solution

Solution is locked

Question 2

What are the inputs and outputs of the algorithm provided below?

1    BEGIN
2        Get word
3        reverse = ''
4        FOR i = 0 TO Length(word) - 1
5            Append word[-i-1] to reverse
6        NEXT i
7        IF word = reverse THEN
8            Display "It's the same forwards and backwards!"
9        ENDIF
10    END

1. Input: word, which given the description is expected to be a single word represented as a string.

   Output: the string “It’s the same forwards and backwards!”

2. Input: word, which given the description is expected to be a single word represented as a string and reverse, which is an empty string.

   Output: the string “It’s the same forwards and backwards!”

3. Input: word, which given the description is expected to be a single word represented as a string.

   Output: the boolean value True/False, depending whether the condition on line 7 is True or False and the string “It’s the same forwards and backwards!”

4. Input: word, which given the description is expected to be a single word represented as a string and reverse, which is an empty string.

   Output: the boolean value True/False, depending whether the condition on line 7 is True or False and the string “It’s the same forwards and backwards!”

Solution

Solution is locked

Question 3

Determine the purpose of the algorithm provided below.

1    BEGIN
2        Get word
3        reverse = ''
4        FOR i = 0 TO Length(word) - 1
5            Append word[-i-1] to reverse
6        NEXT i
7        IF word = reverse THEN
8            Display "It's the same forwards and backwards!"
9        ENDIF
10    END

Solution

Solution is locked

Question 4

Determine the purpose of the algorithm provided below.

1    BEGIN locate_max(array)
2        max_index = [0]
3        max_value = array[0]
4        i = 1
5        WHILE i < Length(array)
6             IF array[i] > max_value THEN
7                 max_index = i
8                 max_value = array[i]
9             ELSEIF array[i] = max_value THEN
10                 Append i to max_index
11             ENDIF
12             i = i + 1
13        ENDWHILE
14        RETURN max_index
15    END locate_max(array)

Solution

Solution is locked

Question 5

Determine the purpose of the algorithm provided below.

1    BEGIN fibonacci(n)
2        IF n <= 2 THEN
3            RETURN 1
4        ELSE
5            RETURN fibonacci(n-1) + fibonacci(n-2)
6        ENDIF
7    END fibonacci(n)

Solution

Solution is locked