1. COMP.CS.300 Data Structures and Algorithms 1 »
  2. Decrease- and divide-and-conquer »
  3. Course topic 3 exercises

Course topic 3 exercises

Performance

Consider the pseudocode functions below. (It may help to recall insertion sort’s mechanism.) You can assume that only the things depicted affect the performance (efficiency) of the functions, so for example the performance of the APPEND()-function doesn’t matter.

1
2
3
4
5
6
7
8
9
  FunctionA(Array A):
    res := [[]] // empty 2D Array
    FOR i IN SIZE(A):
      FOR j IN SIZE(A):
        APPEND(res[i], A[i] * A[j])
      END LOOP
      APPEND(res, []) // Add empty array inside the 2D array
    END LOOP
    RETURN res

1
2
3
4
5
6
7
8
  FunctionB(Array A, Int target)
    FOR i IN A:
      FOR j IN A:
        IF i * j == target THEN
          RETURN [i, j]
        END IF
      END LOOP
    END LOOP

1
2
3
4
5
6
7
8
  FunctionC(Array A):
    IF SIZE(A) == 1 OR EMPTY(A) THEN
      RETURN TRUE
    ELSE IF FIRST(A) != LAST(A) THEN
      RETURN FALSE
    END IF
    POP_FIRST_AND_LAST(A) // Remove first and last elements
    FunctionC(A)
Which functions won’t necessarily slow down at all even though the size of the input grows?
What can be said about the input for the best case for FunctionB?
And what can be said in the worst case for FunctionB?
For which function are the performances of the best case, worst case and average case all the same?

Sum as a recursion

A+ presents the exercise submission form here.

Sum of digits as a recursion

A+ presents the exercise submission form here.