Algorithms: Basic Exercises – Part 1

In this post, you’ll find a collection of basic exercises for you to practice ‘Algorithms’ which is a fundamental topic in Computer Science. Each exercise includes a solution but for the absolute beginners, I recommend to try and solve the questions by yourself, without peeking at the solution. This is the best way to master algorithms over time. Enjoy!

Index equal to value

Given a sorted array T of integers, write an algorithm (using pseudocode) that searches for T[i] = i

In case of success, it will return the value of i, otherwise, it will return -1.

Answer

To solve this problem, we’ll use the binary search algorithm.

Index_Equal_Value(T, st, end)
if st > end
    then return -1
mid <- (st + end) / 2
if T[mid] > mid
    then return Index_Equal_Value(T, st, mid - 1)
else if T[mid] < mid
    then return Index_Equal_Value(T, mid + 1, end)
else return mid

The call of the function would look like this

Index_Equal_Value(T, 0, length[T] - 1)

The algorithm basically split the array into two each time, checking if the middle index is equal to the middle cell value. If yes, we’ll return the value/index.

If not, it will check if the value of the middle cell is bigger than the index. if yes, it will send the second half of the original array as the new array to check. If the middle cell value is smaller than the index, it will call the function again, this time with the first half of the array as the new array to check.

If you confused about how binary search works, have a look at this video.

The above solution is also a recursive one. If for some reason you are not a big fan of recursion, here is a solution using a simple loop.

Index_Equal_Value(T)
st <- 1
end <- length[T]
while st <= end do
    mid = (st + end) / 2
    if T[mid] = mid
        then reuturn mid
    else if T[mid] > mid
        end <- mid - 1
    else if T[mid] < mid
        st <- mid + 1
return -1

Insertion Sort

Using pseudocode, implement Insertion Sort algorithm.

What is the worst case (time) complexity of the algorithm you wrote?

Answer

for i <- 1 to length[A] - 1
   do key <- A[i]
   j <- i
   while j > 0 and A[j - 1] > key
       do A[j] <- A[j - 1]
       j <- j - 1
   A[j] <- key

The worst case in case of the above algorithm is O(n^2). The best would be O(n).

If you find it hard to follow the insertion sort algorithm, you can try to watch this great video.

Backward Insertion Sort

Originally, Insertion Sort algorithm implemented from left to right. Write a backward version which will sort the array from right to left.

Answer

for i <- length[A] - 2 downto 0
   do key <- A[i]
   j <- i + 1
   while j < length[A] - 1 and key > A[j]
       do A[j - 1] <- A[j]
       j <- j + 1
   A[j - 1] <- key

Maximum between given indexes

1. Write an algorithm to return the index of the maximum value between two given indexes in a given array.

2. Here is a recursive solution for the previous question.

MaxValue(A, p, r)
max <- p
for i <- p + 1 to r
    if A[i] > A[max]
        then max <- i
return max

Find the recurrence relation that fits the time complexity of the algorithm.

3. Write a recursive algorithm to solve the issue presented in the first question. Do so by splitting the solution into two sub-issues/steps.

4. What is the recurrence relation of the algorithm from the previous question?

Answer

1. The algorithm for returning the index of the maximum value between two indexes

MaxValue(A, p, r)
max <- p
for i <- p + 1 to r
    if A[i] > A[max]
        then max <- i
return max

2. Since the time run depends on the size of the input (n = r – p + 1) the recurrence relation is as following

T(1) = 2
T(n) = 2 + (2 + T(n -1) = 4 + T(n -1)

If you are a little bit confused about what is recurrence relation, you can find a nice video explains recurrence relation here.

3. The recursive algorithm for returning the index of the maximum value between two indexes by splitting the issue into two sub-issues

MaxValue(A, p, r)
if r > p
    then mid <- (p + r) / 2
    leftMax <- MaxValue(A, p, mid)
    rightMax <- MaxValue(A, mid + 1, r)
    if A[leftMax] > A[rightMax]
        then return leftMax
        else return rightMax
else return p

4. The recurrence relation is

T(1) = 2
T(n) = 2T(n/2) + 6

Backward Insertion Sort

1. Write a recursive algorithm to check the number of occurrences of a given number in a given array. Note: the length of the array is also given with ‘n’.

2. Find the recurrence relation of the algorithm from the previous question.

3. Is there a difference between worst case and the best case for the algorithm you wrote as an answer to the first question?.

4. Change the algorithm in the first question to receive an additional parameter (t) to check if ‘num’ appears t times. What would be the best case and the worst case this time?.

Answer

1.  The recursive algorithm for counting the number of occurrences of a certain number in a given array.

CountNum(A, n, t, num)
if A[n - 1] = num
    then count <- 1
    else count <- 0
if n > 1
    count <- count + CountNum(A, n - 1, num)
return count

2. The recurrence relation is

T(1) = 4
T(n) = 4 + T(n-1)

3.  No difference since in any case, the algorithm would have to go over all the cells so it’s O(n).

4. The new algorithm to check if ‘num’ is included t times in the array

CountNum(A, n,, num, t)
if t < 0 return false
if n = 1
    then if t = 0
        then return true
        else return false
if A[n - 1] = num
    then t <- t - 1
return CountNum(A, n - 1, num ,t)

Same number in both arrays

You are given two arrays and your goal is to find out if a number that included in the first array is also included in the second array.

1.  Write an algorithm that for a given number in the first array will go over all the numbers in the second array.

2. Find and write a more efficient solution. What is the time complexity?

Answer

1.  The less efficient algorithm -> O(n^2)

findMatch(A, B)
for i <-0 to (length(A) - 1)  do
    for j <-0 to (length(B) - 1) do
        if A[i] = B[j] return true
return False

2. The more efficient algorithm

findMatch(A, B)
MergeSort(A)
MergeSort(B)
i <- 0
j <- 0
while i <= (length(A) - 1) and j <= (length(B) - 1)
    if A[i] < B[j]
        then i <- i + 1
    else if A[i] > B[j]
        then j <- j + 1
    else return true

return false

Let’s check what would be time complexity of the above algorithm.

  • MergeSort -> O(n*log n) x 2
  • Going over A/B -> O(n) x 2

Time complexity is O(n*log n).

Maximum and Minimum Values

Given an array of size n

1. Write an algorithm to return the minimum and maximum items of the array. What would be the time complexity of this algorithm?

2. If the algorithm you wrote isn’t recursive, write a recursive version of it using divide and conquer method. If it is recursive, you are off the hook 🙂

3. Find the recurrence relation of the recursive algorithm

Answer

1.  The algorithm to return the maximum and minimum in a given array

MinMax(A)
min <- A[0]
max <- A[0]
for i <- 1 to (length(A) - 1)
    do if A[i] < min
        then min <- A[i]
    if A[i] > max
        then max <- A[i]
return min, max

The time complexity is O(n).

2. The recursive algorithm for finding minimum and maximum in an array

RecursiveMinMax(A, l, r)
if l >= r
max <- A[0]
for i <- 1 to (length(A) - 1)
    do if A[i] < min
        then min <- A[i]
    if A[i] > max
        then max <- A[i]
return min, max

3. The recurrence relation

n > 2        T(n/2) + T(n/2) + 2
n = 2        1

Maximum and Minimum differences

Given an array of size n

1. Write an algorithm to return the maximum difference between two elements

2. Write an algorithm to return the minimum difference between two elements. What is the time complexity of the algorithm you wrote?

Answer

1.  The algorithm to return the maximum difference of two elements in an array

MaxDifference(A)
maxDiff <- A[1] – A[0]
min <- A[0]
for i <- 1 to length[A] do
    If A[i] – min > maxDiff
        then maxDiff <- A[i] – min
    If A[i] < min
        then min <- A[i]
return maxDiff

2. To find the minimum difference, we’ll have to first sort the array. For that, we’ll use Merge Sort algorithm. You can learn more about it here or watch a full demonstration here.

We’ll then iterate over the array and check if the difference between two cells is the new smaller than the minimum set at the beginning

MinDifference(A)
Merge-Sort(A, 0, length[A] -1)
MinDiff <- abs(A[0] – A[1])
for i <- 2 to length[A] - 1 do
    diff = abs(A[i – 1] – A[i]
    If minDiff < diff
        Then minDiff <- diff
Return minDiff

Since merge sort is O(nlogn) and going over the array once is O(n) the overall time complexity is O(nlogn).

Selection Sort

1. Implement selection sort algorithm. You can read about it here.

2. What is the time complexity of your implementation?

Answer

1. The algorithm

SelectionSort(A)
for i <- 0 to (length[A] – 2) do
    indexMin <- i
    for j <- i +1 to (length[A] – 1) do
        if A[j] < A[indexMin]
            then indexMin = j
    If indexMin != i     
        then temp <- A[i]
        A[i] <- A[indexMin]
        A[indexMin] <- temp

2. Time complexity is O(n^2) since in both worst case and best case, we’ll go over the entire array for each element to check if there is a smaller value. You can also see we have nested loop in our implementation above.

References

I gathered all the links posted in this post here for your convenience

You can find more exercises for free on different topics in my repository ‘AskMe‘ on Github.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s