Course topic 4 exercises¶

Iteration vs. recursion¶

Iterative problems can be switched to recursion and the other way around. Both approaches can be used to either decrease- or divide-and-conquer.

Consider for example, the Search and BinarySearch algorithms below.

Search

  Search(Int a, Array N):
   FOR elem IN N:
     IF elem == a:
       return true
     END IF
   END LOOP
   return false

Binary search

  BinarySearch(A, left, right, value)
   (A in ascending order)
   if left = right then
     if A[left] = value then
         return true
     else
         return false
   else
     middle := ⌊(left+right)/2⌋
     if value ≤ A[middle] then
         return BinarySearch(A, left, middle, value)
     else
         return BinarySearch(A, middle+1, right, value)

The first one uses iteration, the second one, recursion. Another difference between the two algorithms is the efficiency: logarithmic BinarySearch is asymptotically more efficient than linear Search. On the other hand, Search does not set any prerequisites for the order the items are in prior to the search. BinarySearch uses divide-and-conquer principle, whose benefits become the clearer the more data one has to scan through.

Search the smallest missing¶

Let us consider similar problem, where an algorithm searches smallest missing value, and takes an array of unique integer numbers in ascending order as a parameter.

For example, with the input of [0, 1, 2, 3, 4, 5, 12, 23], the function returns 6. If no value is missing, then function must return NO_VALUE_MISSING.

Can you figure out two solutions?

One that uses iteration (searchSmallestMissingIteration())
Another that uses recursion (searchSmallestMissing())

Attention

Before you start working on the exercises, make sure you have pulled the latest updates from the course repository:

git pull course-upstream main

You should now find the files needed for the exercises inside the directory wk02_decrease_or_divide/missing

searchSmallestMissingIteration()¶

Implement the algorithm searchSmallestMissingIteration() in the file wk02_decrease_or_divide/missing/missing.cc.

int searchSmallestMissingIteration(int* arr, int size) {
  // returns the first missing number, or NO_VALUE_MISSING if not found
  return NO_VALUE_MISSING;
}

The parameter arr is the array to be checked, and size is the array size.

Write your solution for searchSmallestMissingIteration() in C++ using decrease-and-conquer principles.

Hint

You are supposed to use iteration, i.e. for or while loop in this solution

A+ presents the exercise submission form here.

searchSmallestMissing()¶

Implement the algorithm searchSmallestMissing() in the file wk02_decrease_or_divide/missing/missing2.cc.

int searchSmallestMissing(int* A, int left, int right) {
  // returns the first missing number, or NO_VALUE_MISSING if not found
  return NO_VALUE_MISSING;
}

The parameters:

A is the array to be checked
left the leftmost index of an array, initially 0
right the rightmost index of an array, initially size-1 when size is the array size.

Write your solution for searchSmallestMissing() in C++ using divide-and-conquer principles.

Hint

You are supposed to use recursion, i.e. DO NOT use for or while loop in this solution!

A+ presents the exercise submission form here.

Quicksort¶

[JSAV Placeholder: sorting_quicksort]

Mergesort¶

[JSAV Placeholder: sorting_mergesort]