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.

1 2 3 4 5 6 7 8 9 |
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

1 |
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.

1 2 3 4 5 6 7 8 9 10 11 12 |
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**

1 2 3 4 5 6 7 |
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**

1 2 3 4 5 6 7 |
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.

1 2 3 4 5 6 |
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

1 2 3 4 5 6 |
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

1 2 |
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

1 2 3 4 5 6 7 8 9 |
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

1 2 |
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.

1 2 3 4 5 6 7 |
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

1 2 |
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

1 2 3 4 5 6 7 8 9 |
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)

1 2 3 4 5 |
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

1 2 3 4 5 6 7 8 9 10 11 12 13 |
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

1 2 3 4 5 6 7 8 9 |
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

1 2 3 4 5 6 7 8 9 |
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

1 2 |
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

1 2 3 4 5 6 7 8 9 |
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

1 2 3 4 5 6 7 8 |
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

1 2 3 4 5 6 7 8 9 10 |
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

- Binary Search video
- Insertion Sort wiki
- Insertion Sort video
- Recurrence Relation video
- Merge Sort wiki
- Merge Sort video
- Selection Sort wiki
- Selection Sort video

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

## Leave a Reply