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

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?

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

```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?

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

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?

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

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

```MinMax(A)
min <- A
max <- A
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
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?

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

```MaxDifference(A)
maxDiff <- A – A
min <- A
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 – A)
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

2. What is the time complexity of your implementation?

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