Divide and conquer and dynamic programming

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

Divide and Conquer and Dynamic Programming

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

divide and conquer dynamic programming corrected exercises

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

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

divide and conquer dynamic programming corrected exercises

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

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

divide and conquer dynamic programming corrected exercises common substring

Solution

divide and conquer dynamic programming corrected exercises common substring

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

divide and conquer dynamic programming corrected exercises maximum subsequence

divide and conquer dynamic programming corrected exercises maximum subsequence

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.

Solution

divide and conquer dynamic programming corrected exercises Levenshtein distance

divide and conquer dynamic programming corrected exercises Levenshtein distance

To share
en_GBEN
%d bloggers like this: