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.

The call of the function would look like this

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.

Insertion Sort

Using pseudocode, implement Insertion Sort algorithm.

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

Answer

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

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.

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

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

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

4. The recurrence relation is

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.

2. The recurrence relation is

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

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)

2. The more efficient algorithm

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

The time complexity is O(n).

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

3. The recurrence relation

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

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

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

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.