Find out its asymptotic tight bound using the master theorem

Assignment Help Data Structure & Algorithms

Reference no: EM131307220

Answer all questions and for all questions, show the step using algorithm.

Q1. Running time analysis

(a) Given T(n) = 5T(n/2) + n². Find out its asymptotic tight bound using the Master Theorem.

(b) Prove the previous asymptotic tight bound using either substitution or induction methods.

Q2. Rod-black tree.

(a) Step-by-step, build a red-black tree with the an ordered input sequence of {20, 5, 11, 10, 29, 5, 21, 4, 15}.

(b) Given the following red-black tree, step-by-step show how to delete the rod node of 21.

Q3. van Embde Boas tree

(a) What is the worst-case run time of the operations on a Van Emde Boas tree? Most time complexity analysis is concerned with the number of elements that are being looked at. How does the time-complexity of a Van Emde Boas tree differ from that norm?

(b) Describe the two functions high(x) and low(x) in the context of a Van Emde Boas tree.

Q4. You are asked to modify the LCS algorithm to identify the heaviest common subsequence (HCS) using a weighted scoring scheme, denoted as matrix M, as shown below.

	A	B	C	D
A	1	0.5	0	0
B	0.5	2	0	0
C	0	0	1	0.5
D	0	0	0.5	1

Based on this score scheme, A-A match has a score of 1, B-B match has a score of 2, A-B match has a score of 0.5. For example, given that X = {BACBADCDD} and Y = {BC DABCBDD), the subsequences S₁x = {BABA} and S₁y = {BABB} has a matching scorn of 2 + 1 + 2 + 0.5 = 5.5, and the subsequence S₂ = {CDCDD} has a matching score of 1 + 1 + 1 + 1 + 1 = 5. Hence, the shared sequence of S₁x and S₁y is heavier (with higher scores) than the perfect match subsequence of S₂. (In practice, S₁a and S₁b are often merged as {BABA/B}. Your task is to design an algorithm to identify the heaviest common subsequence by modifying the LCS algorithm in CLRS textbook.

(a) First, illustrate the application of dynamic programming on heaviest common sub-sequence (HCS) using the example of X and Y sequences given above, by following the example of Figure 15.8 in the CLRS textbook.

(b) Design a HCS algorithm by modifying the LCS-LENGTH(X, Y) in Chapter 15 of the CLRS textbook using a weighted scoring matrix M as shown above. The rows and columns in M are symbols of {A. B, C, D}, and the elements of M are scores such that M[A, A] = 1, M[B, B] = 2, M [A, B] = 0.5, M[A, C] = 0, . .

Q5. Knap-sack problem. Illustrate the application of dynamic programming on the following Knapsack problem with the maximum weight 7 pounds. Please note that chargers and their served devices should always be taken together.

Item	Value (dollars)	Weight (pounds)
Cell phone	100	1
Charger for cell phone	30	1
Laptop	300	3
Charger for laptop	70	1
Tent	250	4
Medicine	200	1
Instant food	80	2
Water bottle	10	1
Umbrella	20	1
Flashlight	35	1

Q6. Computational geometry: A generic point representation is P = (X, Y). Given that P₀ = (0, 0); P₁ = (4, 3); P₂ = (1, 0), P3 = (3, 4), calculate the cross product (P₀P₁)^→x(P₂P₃)^→. Are (P₂P₃)^→clockwise or counterclockwise to (P₀P₁)^→ with respect to their cross point? Your explanation should be justified by the cross-product.

Reference no: EM131307220

Questions Cloud

Determine the specific weight of lightweight concrete : Determine the specific weight of lightweight concrete and calculate its dead load intensity if it is used in an 80-mm (3.25-in) cover of a formed steel deck walkway. Compare this result with that found in Problem CS1.2 and explain any differences.

What is the potential for advancement in the career : How "new" your career is to the market. How much training is generally required to enter the field in this career? What is the potential for advancement in this career.

Chosen newspaper article-summarizes the newspaper article : briefly describes the contents of your paper, an introductory section that describes the general research topic with cited and referenced sources and summarizes the newspaper article.

What contribution is made to the hanger rod load p : If the Kansas City Building Code specified that a floor structure must support a live load of 4.79 kPa (100 psf), and if the walkway length L = 9.1 m = 30.0 ft and width b = 2 m = 6.56 ft, what contribution is made to the hanger rod load P?

Find out its asymptotic tight bound using the master theorem : Running time analysis Given T(n) = 5T(n/2) + n2. Find out its asymptotic tight bound using the Master Theorem. Prove the previous asymptotic tight bound using either substitution or induction methods

Write a literature review about mobile-point-of-sale : Need to write a literature review about Mobile-point-of-sale as a description LR since it's not applied yet in Saudi Arabia - NFS(digital wallets) and POS which are type of mobile payment, are common used everywhere in saudi, while Mpos not yet.

Explain how available are the resources in saudi arabia : How available are these resources in Saudi Arabia? How well are these resources used to promote education and provide a quality education for students?

Find reactions at both walls for the given applied load p : The bar shown has a varying cross section and is fixed rigidly at both walls. The crosssectional area of the narrower section is A; the cross-sectional area of the wider section is larger by a factor of m , or m A.

What issues did the artist address in her work : What materials did the artist use in her works? How is this representative of her work? What do the forms suggest in this work? What issues did this artist address in her work?

User Account

All Pages