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 the 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 the 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, the 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 the 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 a nested loop in our implementation above.
References
I gathered all the links posted in this post here for your convenience
Dev In Practice 