Question

Given a search problem where some elements are searched more than others, it is more important...

Given a search problem where some elements are searched more than others, it is more important to minimize the total cost of several searches rather than the worst-case cost of a single search. If x is a more frequent search target than y, building a tree where the depth of x is smaller than the depth of y will work better, even if that means increasing the overall depth of the tree. A perfectly balanced tree is not the best choice if some items are significantly more popular than others.
Suppose we are given a sorted array of keys A[1..n] and an array of corresponding access frequencies f[1..n]. Build the binary search tree that minimizes the total search time, assuming that there will be exactly f[i] searches for each key A[i]. Suggest a recursive definition of the cost function, such that Cost(T, f[1..n]]=..., where T is the tree.

Homework Answers

Answer #1

1. This is very famous dynamic programming problem known as optimal cost binary search tree.

Lets understand problem with a example

suppose keys = [ 5,7]

frequency = [10 , 14)

so we can have trees in these two forms

5 or 7

\ /

7 5

Cost = 10*1 + 14*2 = 38 cost = 14*1 + 10*2 = 34

So in right side of tree cost of searching is minimum.  

Here cost[i][j] denotes min cost binary search tree which can we formed taking R as a root and

freq[i...j] denotes sum of frequency of keys from i to j.

Base case

i == j only one element so return freq[i]

i>j return 0. As no elements occur between [j,i]

Here we are calculating cost[i][j] using cost[i][R] and cost[R+1][j] as this problems satisfy optimal substructure property.

Feel free to ask doubts in comments if any

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
1. Given an n-element array A, Algorithm X executes an O(n)-time computation for each even number...
1. Given an n-element array A, Algorithm X executes an O(n)-time computation for each even number in A and an O(log n)-time computation for each odd number in A. What is the best-case running time of Algorithm X? What is the worst-case running time of Algorithm X? 2. Given an array, A, of n integers, give an O(n)-time algorithm that finds the longest subarray of A such that all the numbers in that subarray are in sorted order. Your algorithm...
1. We consider the two-point boundary problem uy00(t) + vy0(t) + wy(t) = f(t), where a...
1. We consider the two-point boundary problem uy00(t) + vy0(t) + wy(t) = f(t), where a ≤ t ≤ b and y(a) = α, y(b) = β Here u,v,w, are constants and f(t) is a given function. We assume that u 6= 0. (a) Using the numerical techniques discussed in the book (or class) show how an approximation to y(t) on the interval a ≤ t ≤ b may be generated by solving a tridiagonal system of linear equations of...
1.- While insecurity causes losses for some, it generates profits for others. "From a couple of...
1.- While insecurity causes losses for some, it generates profits for others. "From a couple of years to now, the search for us has skyrocketed. Before, it was us looking for clients, making them see the need to hire private, specialized and armed security," Fuentes said. Miguel Ángel Silva Gómez, Code Uno's chief operating officer, with 16 years in the market, indicated that, although there is more demand for these services, they have not been able to increase the price...
Are some cities more windy than others? Does Chicago deserve to be nicknamed "The Windy City"?...
Are some cities more windy than others? Does Chicago deserve to be nicknamed "The Windy City"? Given below are the average wind speeds (in miles per hour) for 45 selected cities. 8.7 12.3 8.6 11.5 9.1 8.8 35.1 6.1 7.0 7.2 11.8 10.9 7.6 9.2 9.1 8.1 9.0 8.9 9.2 10.7 10.5 9.6 7.8 11.4 9.5 7.7 8.8 8.8 12.9 8.3 7.8 5.9 10.4 10.4 9.6 8.7 10.1 10.5 7.9 10.6 8.5 8.8 9.4 8.8 9.3 (a) Calculate y and...
Match the statement to the correct answer. (Some reagents can be used more than once.) The...
Match the statement to the correct answer. (Some reagents can be used more than once.) The flowchart along with the report sheets in experiment 5 should be very helpful. A 6M Nitric Acid (HNO3) B Colbalt Nitrate (Co(NO3)2) C Disodium EDTA (Na2EDTA) D Aluminum Nitrate (Al(NO3)3) E Zinc Nitrate (Zn(NO3)2 F Barium Nitrate (Ba(NO3)2) G 6M Hydrochloric Acid (HCl) H OH-, CO32-, and PO43- I Lead chloride (PbCl2(s)) J 0.1M sodium carbonate (Na2CO3) K NH4+(aq) and OH-(aq) L Silver chloride...
Why do we naturally tend to trust some strangers more than others? One group of researchers...
Why do we naturally tend to trust some strangers more than others? One group of researchers decided to study the relationship between eye color and trustworthiness. In their experiment the researchers took photographs of 80 students (20 males with brown eyes, 20 males with blue eyes, 20 females with brown eyes, and 20 females with blue eyes), each seated in front of a white background looking directly at the camera with a neutral expression. These photos were cropped so the...
Why do we naturally tend to trust some strangers more than others? One group of researchers...
Why do we naturally tend to trust some strangers more than others? One group of researchers decided to study the relationship between eye color and trustworthiness. In their experiment the researchers took photographs of 80 students (20 males with brown eyes, 20 males with blue eyes, 20 females with brown eyes, and 20 females with blue eyes), each seated in front of a white background looking directly at the camera with a neutral expression. These photos were cropped so the...
Why do we naturally tend to trust some strangers more than others? One group of researchers...
Why do we naturally tend to trust some strangers more than others? One group of researchers decided to study the relationship between eye color and trustworthiness. In their experiment the researchers took photographs of 80 students (20 males with brown eyes, 20 males with blue eyes, 20 females with brown eyes, and 20 females with blue eyes), each seated in front of a white background looking directly at the camera with a neutral expression. These photos were cropped so the...
Why do we naturally tend to trust some strangers more than others? One group of researchers...
Why do we naturally tend to trust some strangers more than others? One group of researchers decided to study the relationship between eye color and trustworthiness. In their experiment the researchers took photographs of 80 students (20 males with brown eyes, 20 males with blue eyes, 20 females with brown eyes, and 20 females with blue eyes), each seated in front of a white background looking directly at the camera with a neutral expression. These photos were cropped so the...
Why do we naturally tend to trust some strangers more than others? One group of researchers...
Why do we naturally tend to trust some strangers more than others? One group of researchers decided to study the relationship between eye color and trustworthiness. In their experiment the researchers took photographs of 80 students (20 males with brown eyes, 20 males with blue eyes, 20 females with brown eyes, and 20 females with blue eyes), each seated in front of a white background looking directly at the camera with a neutral expression. These photos were cropped so the...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT