This page offers several corrected exercises on algorithms, more specifically on the Divide & Conquer paradigm (Divide and rule) and the dynamic programming.

**Exercise 1**

**Exercise 1**

Write a pseudo code for a algorithm divide and conquer to find the position of the largest element in an array of numbers. Write a pseudocode for a brute force algorithm, compare with the previous one. Show a process tree of the divide and conquer algorithm. What is the maximum tree level for numbers?

## Solution

The brute force algorithm is trivial: a loop.

At each level l, the complete binary tree is composed of 2^(l-1) leaves. So the total of the vertices is 2^l -1. Let l be the level of the tree, so l=sup(log_2 (n)).

**Exercise 2**

**Exercise 2**

Write pseudocode for a divide-and-conquer algorithm for the exponentiation problem of computing a^n where a>0 and n is a positive integer. Write a pseudocode for a brute force algorithm, compare with the previous one. Show a process tree of the divide and conquer algorithm. What is the maximum level of the tree for n not given? Check the termination, accuracy and completeness.

## Solution

**Exercise 3**

**Exercise 3**

You are given an array with integers (positive, negative, zero) and you are supposed to find the maximum contiguous sum in this array. Therefore, you need to find a subarray that gives the largest sum. Example, if the given array is: 5, -6, 7, 12, -3, 0, -11, -6

## Solution

Suppose your input array is called A. What you need to do is form another array, say B, each i value of which is calculated using the recursive formula, max(A[i], B[i- 1]+A[i ])

What you actually do is choose to expand the previous window or start a new one. You can do this since you are only supposed to select continuous elements as part of your subsets.

5, -6, 7, 12, -3, 0, -11, -6

The answer would be 19 (from sub-array {7,12} )

**Exercise 4**

**Exercise 4**

Use the longest common substring for: BDCABA and ABCBDAB. The algorithm is described as follows:

## Solution

**Exercise 5**

**Exercise 5**

Match the longest common substring to the longest common subsequence: BDCABA and ABCBDAB. The longest common subsequence (LCS) problem is to find the longest common subsequence of all sequences in a set of sequences (often only two sequences).

This differs from common substring search problems: unlike substrings, subsequences are not required to occupy consecutive positions in the original sequences.

## Solution

**Exercise 6**

**Exercise 6**

Levenshtein distance is a string metric for measuring the difference between two sequences. Informally, the Levenshtein distance between two words is the minimum number of single-character modifications (i.e., insertions, deletions, or substitutions) needed to change one word into the other. Propose a dynamic program to solve this problem. Trial with MEILENSTEIN and LEVENSHTEIN.