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...
-
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...
-
(a) Both sides of a uniform film that has index of refraction n and thickness d are in contact with air. For normal incidence of light, an intensity minimum is observed in the reflected light at A2...
-
Louis wants to take out a $14,000 loan with a 6.8% APR. He can afford to pay no more than $400 per month for loan payments. What would be the length of his loan? Round to the nearest tenth of a year.
-
The defendant, Sterile Technologies, Inc., purchased a sterilizer from the plaintiff, Troy Boiler Works, on an installment payment plan. The defendant was to make installment payments charged with
-
Mike Greenberg opened Kleene Window Washing Inc. on July 1, 2017. During July, the following transactions were completed. July 1 Issued 12,000 shares of common stock for $12000 cash. 1 Purchased used...
-
(b) If the game below is repeated twice, the following strategies form an SPNE when = 1: Strategies Player 1 period 1: Play C period 2: Play B if (C,Y) in stage 1. Play A otherwise. Player 2 period...
-
Sarah recently sold her partnership interest for significantly more than her outside basis in the interest. Two separate appraisals were commissioned at the time of the sale to estimate the value of...
-
The Rocchio' algorithm implements relevance feedback in the vector space model chooses the query as: dopt = (Dr) + [(Dr) - H(Dnr)] For a given graph where circles are relevant documents, and Xs are...
-
Which of the following is generally the least effective methodology to detect sales or accounts receivable skimming? 1. Count and summarize accounts receivable write-offs by employee. 2. Periodically...
-
Assume that you have been asked to perform an examination and report on your findings, conclusions, and opinions. Assume the following: 1. The industry is oil production (at a well-head),...
-
Which of the following is not a means to a negotiated remedy? 1. Arbitration 2. Mediation 3. Remediation 4. Out-of-court settlements
-
The difference between fraud and errors is: 1.The materiality of the value involved 2. Intent of those involved 3. Whether it affects owners equity or not 4. All of the choices are correct
-
Answer the following questions: 1. Name at least five industries that might be affected by weather. 2. Is it appropriate for the forensic accountant/fraud examiner to examine the effect of weather?...
-
At the end of December, a business has accrued $1,450 of interest on a loan, on which it will not make another payment until the next year. The adjusting entry necessary would be journalized as a...
-
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...
-
Show that for a gas of noninteracting bosons, or fermions, the pair correlation function \(g(r)\) is given by the expression \[g(r)=1 \pm \frac{g_{s}}{n^{2} h^{6}}\left|\int_{-\infty}^{\infty}...
-
Show that, in the case of a degenerate gas of fermions \(\left(T \ll T_{F} ight)\), the correlation function \(g(r)\), for \(r \gg \hbar / p_{F}\), reduces to the expression \[g(r)-1=-\frac{3(m k...
-
Show that the pressure and Helmholtz free energy of a fluid at temperature \(T\) can be determined by performing a thermodynamic integration of the inverse of the isothermal compressibility from the...
Study smarter with the SolutionInn App