Writing Assignment Idea By using class notes, the textbook and online resources,

Question

Writing Assignment Idea By using class notes, the textbook and online resources, you will write a paper explaining the topic of Dynamic Programming Specification Write a paper that explains the concept of Dynamic Programming for each of the two problems of Optimal Binary Search Trees and Longest Common Subsequence. Write the paper so that a classmate who knows nothing about Dynamic Programming or the two problems would be able to read and understand t. Divide the paper into 2 sections, one for each problem. Each section should have the following structure: 1. Define the problem. Why is it useful to solve? (Where is it used?) 2. Size of the entire solution space. Is it n or n or better? Or is it exponential? Estimate it. No need for a proof. 3. Can it be solved by other approaches such as Brute Force, Decrement and Conquer, Divide and Conquer, Greedy Methods? If so, what would be the time and space complexity of an 4. Show the structure of the optimal solution to this problem. Give an informal (brief) 5. Based on 4, give the pseudo code for an algorithm based on the dynamic programming 6. What is the time and space complexity of your algorithm? algorithm based on those approaches? justification that the principle of optimality holds approach. Note: 1. The first problem is discussed in the text. For the second problem, please look up online resources or other books such as Introduction to Algorithms by Cormen et. al (MIT Press) 2. Please study the material and then write in your own words. You may not copy and paste from any source. Also, cite the source that you used to understand the problem and the solution approaches.

Explanation / Answer

Kindly raise a seprate question for second problem

Optimal Binary Search Tree

1.Problem Definition:

An optimal binary search tree is a binary search tree for which the nodes are arranged on levels such that the tree cost is minimum.

Let us consider below example of extended BST, in which the keys are stored at their internal nodes. Suppose there are “n” keys k1, k2, … , kn are stored at the internal nodes of the BST. Assuming keys are in sorted order, i.e. k1< k2 < … < kn. An extended binary search tree is obtained from the binary search tree by adding the successor node to each of the terminal nodes as shown below-

Here-

- the squares represent terminal nodes. These terminal nodes represent unsuccessful searches of the tree for key values. The searches did not end successfully, that is, because they represent key values that are not actually stored in the tree;

- the round nodes represent internal nodes; these are the actual keys stored in the tree;

- if the relative frequency with which each key value is accessed is known, weights can be assigned to each node of the extended tree (p1 … p6). They represent the relative frequencies of searches terminating at each node, that is, they mark the successful searches.

If the user searches a key in the tree, 2 cases can occur:

Case 1 – the key is found, so the corresponding weight ‘p’ is incremented;

Case 2 – the key is not found, so the corresponding ‘q’ value is incremented.

2.Where it is used-

In general, word prediction is the problem of guessing the next word in a sentence as the sentence is being entered, and updates this prediction as the word is typed. Currently “word prediction” implies both “word completion and word prediction”.

Word completion is defined as offering the user a list of words after a letter has been typed, while word prediction is defined as offering the user a list of probable words after a word has been typed or selected, based on previous words rather than based on the letter. Word completion problem is easier to solve since the knowledge of some letter(s) provides the predictor a chance to eliminate many of irrelevant words. Online dictionaries rely heavily on the facilities provided by optimal search trees.

As the dictionary has more and more users, it is able to assign weights to the corresponding words, according to the frequency of their search. This way, it will be able to provide a much faster answer, as search time dramatically decreases when storing words into a binary search tree. Word prediction applications are becoming increasingly popular. For example, when you start typing a query in google search, a list of possible entries almost instantly appears.

Solution and its estimation

the terminal node in the extended tree that is the left successor of k1 can be interpreted as representing all key values that are not stored and are less than k1. Similarly, the terminal node in the extended tree that is the right successor of kn, represents all key values not stored in the tree that are greater than kn. The terminal node that is successes between ki and ki-1 in an in-order traversal represents all key values not stored that lie between ki and ki-1.

In the extended tree in the above figure if the possible key values are 0, 1, 2, 3, …, 100 then the terminal node labeled q0 represents the missing key values 0, 1 and 2 if k1=3. The terminal node labeled q3 represents the key values between k3 and k4. If k3=17 and k4=21 then the terminal node labeled q3 represents the missing key values 18, 19 and 20. If k6 is 90 then the terminal node q6 represents the missing key values 91 through 100.

An obvious way to find an optimal binary search tree is to generate each possible binary search tree for the keys, calculate the weighted path length, and keep that tree with the smallest weighted path length. This search through all possible solutions is not feasible, since the number of such trees grows exponentially with “n”.

An alternative would be a recursive algorithm. Consider the characteristics of any optimal tree. Of course, it has a root and two subtrees. Both subtrees must themselves be optimal binary search trees with respect to their keys and weights. First, any subtree of any binary search tree must be a binary search tree.

Second, the subtrees must also be optimal. Since there are “n” possible keys as candidates for the root of the optimal tree, the recursive solution must try them all. For each candidate key as root, all keys less than that key must appear in its left subtree while all keys greater than it must appear in its right subtree. Stating the recursive algorithm based on these observations requires some notations:

All possible optimal subtrees are not required. Those that are consist of sequences of keys that are immediate successors of the smallest key in the subtree, successors in the sorted order for the keys.

The bottom-up approach generates all the smallest required optimal subtrees first, then all next smallest, and so on until the final solution involving all the weights is found.

Since the algorithm requires access to each subtree’s weighted path length, these weighted path lengths must also be retained to avoid their recalculation. They will be stored in the weight matrix ‘W’. Finally, the root of each subtree must also be stored for reference in the root matrix ‘R’.

The algorithm requires O (n2 ) time and O (n2 ) storage. Therefore, as ‘n’ increases it will run out of storage even before it runs out of time. The storage needed can be reduced by almost half by implementing the two-dimensional arrays as one-dimensional arrays.

OBST Time/Space complexities with different approaches-

Algorithm

Time Complexity

Space Complexity

Brute Force

exponential

exponential

Dynamic Programming

O(n^2)

O(n^2)

Example of Optimal Binary Search Tree (OBST)

Find the optimal binary search tree for N = 6, having keys k1 … k6 and weights p1 = 10, p2 = 3, p3 = 9, p4 = 2, p5 = 0, p6 = 10; q0 = 5, q1 = 6, q2 = 4, q3 = 4, q4 = 3, q5 = 8, q6 = 0. The following figure shows the arrays as they would appear after the initialization and their final disposition.

The elements of the cost matrix are afterwards computed following a pattern of lines that are parallel with the main diagonal.

And so on … C(1, 5) = W(1, 5) + min(C(1, 1) + C(2, 5), C(1, 2) + C(3, 5), C(1, 3) + C(4, 5), C(1, 4) + C(5, 5)) = = 39 + min(81, 64, 75, 78) = 103

Optimal Binary Search Tree

1.Problem Definition:

An optimal binary search tree is a binary search tree for which the nodes are arranged on levels such that the tree cost is minimum.

Let us consider below example of extended BST, in which the keys are stored at their internal nodes. Suppose there are “n” keys k1, k2, … , kn are stored at the internal nodes of the BST. Assuming keys are in sorted order, i.e. k1< k2 < … < kn. An extended binary search tree is obtained from the binary search tree by adding the successor node to each of the terminal nodes as shown below-

Here-

- the squares represent terminal nodes. These terminal nodes represent unsuccessful searches of the tree for key values. The searches did not end successfully, that is, because they represent key values that are not actually stored in the tree;

- the round nodes represent internal nodes; these are the actual keys stored in the tree;

- if the relative frequency with which each key value is accessed is known, weights can be assigned to each node of the extended tree (p1 … p6). They represent the relative frequencies of searches terminating at each node, that is, they mark the successful searches.

If the user searches a key in the tree, 2 cases can occur:

Case 1 – the key is found, so the corresponding weight ‘p’ is incremented;

Case 2 – the key is not found, so the corresponding ‘q’ value is incremented.

2.Where it is used-

In general, word prediction is the problem of guessing the next word in a sentence as the sentence is being entered, and updates this prediction as the word is typed. Currently “word prediction” implies both “word completion and word prediction”.

Word completion is defined as offering the user a list of words after a letter has been typed, while word prediction is defined as offering the user a list of probable words after a word has been typed or selected, based on previous words rather than based on the letter. Word completion problem is easier to solve since the knowledge of some letter(s) provides the predictor a chance to eliminate many of irrelevant words. Online dictionaries rely heavily on the facilities provided by optimal search trees.

As the dictionary has more and more users, it is able to assign weights to the corresponding words, according to the frequency of their search. This way, it will be able to provide a much faster answer, as search time dramatically decreases when storing words into a binary search tree. Word prediction applications are becoming increasingly popular. For example, when you start typing a query in google search, a list of possible entries almost instantly appears.

Solution and its estimation

the terminal node in the extended tree that is the left successor of k1 can be interpreted as representing all key values that are not stored and are less than k1. Similarly, the terminal node in the extended tree that is the right successor of kn, represents all key values not stored in the tree that are greater than kn. The terminal node that is successes between ki and ki-1 in an in-order traversal represents all key values not stored that lie between ki and ki-1.

In the extended tree in the above figure if the possible key values are 0, 1, 2, 3, …, 100 then the terminal node labeled q0 represents the missing key values 0, 1 and 2 if k1=3. The terminal node labeled q3 represents the key values between k3 and k4. If k3=17 and k4=21 then the terminal node labeled q3 represents the missing key values 18, 19 and 20. If k6 is 90 then the terminal node q6 represents the missing key values 91 through 100.

An obvious way to find an optimal binary search tree is to generate each possible binary search tree for the keys, calculate the weighted path length, and keep that tree with the smallest weighted path length. This search through all possible solutions is not feasible, since the number of such trees grows exponentially with “n”.

An alternative would be a recursive algorithm. Consider the characteristics of any optimal tree. Of course, it has a root and two subtrees. Both subtrees must themselves be optimal binary search trees with respect to their keys and weights. First, any subtree of any binary search tree must be a binary search tree.

Second, the subtrees must also be optimal. Since there are “n” possible keys as candidates for the root of the optimal tree, the recursive solution must try them all. For each candidate key as root, all keys less than that key must appear in its left subtree while all keys greater than it must appear in its right subtree. Stating the recursive algorithm based on these observations requires some notations:

All possible optimal subtrees are not required. Those that are consist of sequences of keys that are immediate successors of the smallest key in the subtree, successors in the sorted order for the keys.

The bottom-up approach generates all the smallest required optimal subtrees first, then all next smallest, and so on until the final solution involving all the weights is found.

Since the algorithm requires access to each subtree’s weighted path length, these weighted path lengths must also be retained to avoid their recalculation. They will be stored in the weight matrix ‘W’. Finally, the root of each subtree must also be stored for reference in the root matrix ‘R’.

The algorithm requires O (n2 ) time and O (n2 ) storage. Therefore, as ‘n’ increases it will run out of storage even before it runs out of time. The storage needed can be reduced by almost half by implementing the two-dimensional arrays as one-dimensional arrays.

OBST Time/Space complexities with different approaches-

Algorithm

Time Complexity

Space Complexity

Brute Force

exponential

exponential

Dynamic Programming

O(n^2)

O(n^2)

Example of Optimal Binary Search Tree (OBST)

Find the optimal binary search tree for N = 6, having keys k1 … k6 and weights p1 = 10, p2 = 3, p3 = 9, p4 = 2, p5 = 0, p6 = 10; q0 = 5, q1 = 6, q2 = 4, q3 = 4, q4 = 3, q5 = 8, q6 = 0. The following figure shows the arrays as they would appear after the initialization and their final disposition.

The elements of the cost matrix are afterwards computed following a pattern of lines that are parallel with the main diagonal.

And so on … C(1, 5) = W(1, 5) + min(C(1, 1) + C(2, 5), C(1, 2) + C(3, 5), C(1, 3) + C(4, 5), C(1, 4) + C(5, 5)) = = 39 + min(81, 64, 75, 78) = 103

Algorithm

Time Complexity

Space Complexity

Brute Force

exponential

exponential

Dynamic Programming

O(n^2)

O(n^2)

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.