1. Let S be a set of n keys being mapped to a hash table (also)...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
1. Let S be a set of n keys being mapped to a hash table (also) of size n. Find the expected number of empty slots under uniform hashing assumption. 2. Let S be a set of n keys being mapped to a has table of size n under chaining. Let X denote the length of longest chain in any slot. Show that the expected value E[X] = O(logn). 3. A string is palindromic if it is equal to its reverse. e.g.,abcabacba. Given a string T[1..n], find the largest palindromic suffix of this string in O(n) time. 4. Let T[1..n] be the text drawn from alphabet set E. Now, given i we want to find the lexi- cographic rank of suffix T[i..n] among all the suffixes of T. Give an O(n) algorithm for this task which does not involve building a suffix array or suffix tree. 5. Let T[1..n] be the text drawn from alphabet E. Our task is to construct an LCP array. LCP stands for longest common prefix. LCP array aids SA (suffix array) in doing faster binary search. LCP array is defined as LCP[i] = length of the longest common prefix of T[SA[i]..n] and T[SA[i+1]...n]. For example, for acacaac#, SA = = [8,5,6,3, 1, 7, 4, 2] and LCP = [0, 1,2,3,0, 1,2]. Given a suffix tree show an algorithm which can compute LCP in O(n) time. Assume that the suffix tree has edge labels which are in terms of two integers: starting and ending locations of the substring in T. Clearly describe what fields you would maintain in the "Node" structure and give a precise pseudocode based on tree traversal. Note that this is an implementation-level question so you must give a pseudocode. Just a high level description is not sufficient. 1. Let S be a set of n keys being mapped to a hash table (also) of size n. Find the expected number of empty slots under uniform hashing assumption. 2. Let S be a set of n keys being mapped to a has table of size n under chaining. Let X denote the length of longest chain in any slot. Show that the expected value E[X] = O(logn). 3. A string is palindromic if it is equal to its reverse. e.g.,abcabacba. Given a string T[1..n], find the largest palindromic suffix of this string in O(n) time. 4. Let T[1..n] be the text drawn from alphabet set E. Now, given i we want to find the lexi- cographic rank of suffix T[i..n] among all the suffixes of T. Give an O(n) algorithm for this task which does not involve building a suffix array or suffix tree. 5. Let T[1..n] be the text drawn from alphabet E. Our task is to construct an LCP array. LCP stands for longest common prefix. LCP array aids SA (suffix array) in doing faster binary search. LCP array is defined as LCP[i] = length of the longest common prefix of T[SA[i]..n] and T[SA[i+1]...n]. For example, for acacaac#, SA = = [8,5,6,3, 1, 7, 4, 2] and LCP = [0, 1,2,3,0, 1,2]. Given a suffix tree show an algorithm which can compute LCP in O(n) time. Assume that the suffix tree has edge labels which are in terms of two integers: starting and ending locations of the substring in T. Clearly describe what fields you would maintain in the "Node" structure and give a precise pseudocode based on tree traversal. Note that this is an implementation-level question so you must give a pseudocode. Just a high level description is not sufficient.
Expert Answer:
Answer rating: 100% (QA)
Solutions Step 1 The expected number of empty slots in a hash table with n keys and n slots under uniform hashing assumption can be calculated as follows Let pi be the probability that the ith slot re... View the full answer
Related Book For
Introduction to Algorithms
ISBN: 978-0262033848
3rd edition
Authors: Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest
Posted Date:
Students also viewed these programming questions
-
Four identical point charges (+6.0 nC) are placed at the corners of a rectangle which measures 6.0 m x 8.0 m. If the electric potential is taken to be zero at infinity, what is the potential at the...
-
Consider what is involved in changing the culture, even within a small organization. Share some thoughts as to how you might change the culture . Do you think culture change here is possible? Why or...
-
Let S be a set of n elements. Determine the number of ordered partitions of the types. 1. n = 5; (3, 1, 1) 2. n = 5; (2, 1, 2) 3. n = 6; (2, 1, 2, 1) 4. n = 6; (3, 3) 5. n = 7; (3, 2, 2) 6. n = 7;...
-
Suppose that the magnetic field in some region has the form B = kzx (where k is a constant). Find the force on a square loop (side a), lying in the yz plane and centered at the origin, if it carries...
-
You have just arranged for a $1,950,000 mortgage to finance the purchase of a large tract of land. The mortgage has an APR of 5.2 percent, and it calls for monthly payments over the next 30 years....
-
Treasury stock is listed as a(n) __________ on the balance sheet. (a) current liability (b) current asset (c) deduction from stockholders equity (d) addition to stockholders equity
-
What companies are required to present the disclosures specified by SFAS No. 69?
-
Your parents will retire in 18 years. They currently have $250,000, and they think they will need $1,000,000 at retirement. What annual interest rate must they earn to reach their goal, assuming they...
-
Vintage Clothing Ltd. shows gross profit of $337000, operating expenses of $170,000, and cost of goods sold of $204,000. Required: What is the amount of net sales revenue? Answer:
-
Zia Co. makes flowerpots from recycled plastic in two departments, Molding and Packaging. Zia uses the weighted average method, and units completed in the Molding department are transferred to the...
-
Achilles tendon 4) A 61 kg woman stands on one foot, on tiptoe, with the sole of her foot making a 25 angle with the floor; the distances are as shown in in the figure. What is the magnitude of the...
-
2. Based on the information below, (A) calculate the accounting profit, (B) the economic profit, and (C) explain if this enterprise was worth the endeavor for the investor/business person. Total...
-
A 1.75 L balloon initially contains 2.87 g CO2. If I untie the knot and release some carbon dioxide so that only 2.05 g remains, what is the new volume? Assume the temperature and pressure do not...
-
Read INHERENT INSTABILITY IN BANKING: THE FREE BANKING EXPERIENCE: https://pdfs.semanticscholar.org/ca4d/802fc714155b66465effa4d41ea5dd6840a0.pdf Notes on Rolnick and Weber (1986): p. 883 contains an...
-
explain in detail the impact that Quincy Jones has had on the African American music & television scene in the years that he was active! Did he move the imagery of African Americans forward with his...
-
The Golden Mushroom has two classes of stock authorized: 8%, $10 par preferred, and $1 par value common. The following transactions affect stockholders' equity during 2024, its first year of...
-
"Evergreen Enterprises" began its operations on January 1, 20X1. Throughout the year, the company engaged in numerous transactions to grow its business. Record the following transactions in the...
-
Do public and private companies follow the same set of accounting rules? Explain.
-
It is often desirable to keep all elements of a doubly linked list compact in storage, using, for example, the first m index locations in the multiple-array representation. (This is the case in a...
-
Most computers can perform the operations of subtraction, testing the parity (odd or even) of a binary integer, and halving more quickly than computing remainders. This problem investigates the...
-
Suppose that we are given a set of n objects, where the size si of the i th object satisfies 0 < si < 1. We wish to pack all the objects into the minimum number of unit-size bins. Each bin can hold...
-
Given the probabilities of expected states of the economy shown here, and the expected returns to stocks A and B in those states, what is the standard deviation of a portfolio with weights of 40...
-
The controller of Getty Industries has collected the following monthly expense data for use in analysis the cost behavior of maintenance costs. Instructions (a) Determine the fixed and variable cost...
-
Stock W has an expected return of 12.4 percent and a beta of 1.8. If the expected market return is 10 percent, what is the risk-free rate? a. -5.6% b. 3.0% c. 5.6% d. 7.0%
Study smarter with the SolutionInn App