Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged cormen
0
votes
0
answers
151
Cormen Edition 3 Exercise 3.2 Question 6 (Page No. 60)
Show that the golden ratio $\phi$ and its conjugate $\hat{\phi}$ both satisfy the equation $x^2=x+1$.
Show that the golden ratio $\phi$ and its conjugate $\hat{\phi}$ both satisfy the equation $x^2=x+1$.
akash.dinkar12
209
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
asymptotic-notation
descriptive
+
–
0
votes
1
answer
152
Cormen Edition 3 Exercise 3.2 Question 5 (Page No. 60)
Which is asymptotically larger: $lg(lg^*n)$ and $lg^*(lg n)$ ?
Which is asymptotically larger: $lg(lg^*n)$ and $lg^*(lg n)$ ?
akash.dinkar12
304
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
asymptotic-notation
descriptive
difficult
+
–
1
votes
0
answers
153
Cormen Edition 3 Exercise 3.2 Question 4 (Page No. 60)
Is the function $\lceil$ $lg$ $n$ $\rceil$!$ polynomially bounded ? Is the function $\lceil$ $lg$ $lg$ $n$ $\rceil$!$ polynomially bounded ?
Is the function $\lceil$ $lg$ $n$ $\rceil$$!$ polynomially bounded ? Is the function $\lceil$ $lg$ $lg$ $n$ $\rceil$$!$ polynomially bounded ?
akash.dinkar12
170
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
asymptotic-notation
descriptive
difficult
+
–
0
votes
0
answers
154
Cormen Edition 3 Exercise 3.2 Question 1 (Page No. 60)
Show that if $f(n)$ and $g(n)$ are monotonically increasing functions, then so are the functions $f(n) +g(n)$ and $f(g(n))$, and if $f(n)$ and $g(n)$ are in addition nonnegative, then $f(n) . g(n)$ is monotonically increasing.
Show that if $f(n)$ and $g(n)$ are monotonically increasing functions, then so are the functions $f(n) +g(n)$ and $f(g(n))$, and if $f(n)$ and $g(n)$ are in addition nonn...
akash.dinkar12
313
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
asymptotic-notation
descriptive
+
–
0
votes
0
answers
155
Cormen Edition 3 Exercise 3.1 Question 8 (Page No. 53)
We can extend our notation to the case of two parameters $n$ and $m$ that can go to infinity independently at different rates.For a given function $g(n,m)$, we denote by $O(g(n,m))$ the set of functions $O(g(n,m))$ $=$ {$f(n,m) :$ ... all $n \geq n_0$ or $m \geq m_0$ } Give corresponding definitions for $\Omega(g(n,m))$ and $\Theta(g(n,m))$.
We can extend our notation to the case of two parameters $n$ and $m$ that can go to infinity independently at different rates.For a given function $g(n,m)$, we denote by ...
akash.dinkar12
313
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
asymptotic-notation
descriptive
+
–
0
votes
1
answer
156
Cormen Edition 3 Exercise 3.1 Question 7 (Page No. 53)
Prove that $o(g(n)) \cap \omega(g(n))$ is the empty set.
Prove that $o(g(n)) \cap \omega(g(n))$ is the empty set.
akash.dinkar12
2.6k
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
asymptotic-notation
descriptive
+
–
0
votes
0
answers
157
Cormen Edition 3 Exercise 3.1 Question 6 (Page No. 53)
Prove that the running time of an algorithm is $\Theta (g(n))$ if and only if its worst-case running time is $O(g(n))$ and its best-case running time is $\Omega(g(n))$.
Prove that the running time of an algorithm is $\Theta (g(n))$ if and only if its worst-case running time is $O(g(n))$ and its best-case running time is $\Omega(g(n))$.
akash.dinkar12
255
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
asymptotic-notation
descriptive
+
–
0
votes
1
answer
158
Cormen Edition 3 Exercise 3.1 Question 4 (Page No. 53)
Is $2^{n+1} = O(2^n) $? $2^{2n} = O(2^n)$?$
Is $2^{n+1} = O(2^n) $? $2^{2n} = O(2^n)$$?$
akash.dinkar12
508
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
asymptotic-notation
descriptive
+
–
0
votes
2
answers
159
Cormen Edition 3 Exercise 3.1 Question 3 (Page No. 53)
Explain why the statement, “The running time of algorithm A is at least $O(n^2),$” is meaningless.
Explain why the statement, “The running time of algorithm A is at least $O(n^2),$” is meaningless.
akash.dinkar12
584
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
asymptotic-notation
descriptive
+
–
0
votes
1
answer
160
Cormen Edition 3 Exercise 3.1 Question 2 (Page No. 52)
Show that for any real constants $a$ and $b$, where $b > 0,$ $(n+a)^b=\Theta(n^b)$
Show that for any real constants $a$ and $b$, where $b 0,$$(n+a)^b=\Theta(n^b)$
akash.dinkar12
296
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
asymptotic-notation
descriptive
+
–
0
votes
0
answers
161
Cormen Edition 3 Exercise 3.1 Question 1 (Page No. 52)
Let $f(n)$ and $g(n)$ be asymptotically nonnegative functions. Using the basic definition of $\Theta$ notation, prove that $max(f(n),g(n)) = \Theta(f(n)+g(n))$.
Let $f(n)$ and $g(n)$ be asymptotically nonnegative functions. Using the basic definition of $\Theta$ notation, prove that $max(f(n),g(n)) = \Theta(f(n)+g(n))$.
akash.dinkar12
371
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
asymptotic-notation
descriptive
+
–
0
votes
0
answers
162
Cormen Edition 3 Exercise 11.4 Question 5 (Page No. 277)
Consider an open-address hash table with a load factor $\alpha$ Find the nonzero value $\alpha$ for which the expected number of probes in an unsuccessful search equals twice the expected number of probes in a successful search.
Consider an open-address hash table with a load factor $\alpha$ Find the nonzero value $\alpha$ for which the expected number of probes in an unsuccessful search equals t...
akash.dinkar12
375
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
hashing
descriptive
+
–
0
votes
1
answer
163
Cormen Edition 3 Exercise 11.4 Question 4 (Page No. 277)
Suppose that we use double hashing to resolve collisions--that is, we use the hash function $h(k,i) = (h_1(k) + ih_2(k))$ $mod$ $m$.Show that if $m$ and $h_2(k)$ have greatest common divisor $d\geq 1$ for some key $k$,then ... $d=1$, so that $m$ and $h_2(k)$ are relatively prime, the search may examine the entire hash table.
Suppose that we use double hashing to resolve collisions that is, we use the hash function $h(k,i) = (h_1(k) + ih_2(k))$ $mod$ $m$.Show that if $m$ and $h_2(k)$ have grea...
akash.dinkar12
372
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
hashing
descriptive
+
–
0
votes
1
answer
164
Cormen Edition 3 Exercise 11.4 Question 3 (Page No. 277)
Consider an open-address hash table with uniform hashing. Give upper bounds on the expected number of probes in an unsuccessful search and on the expected number of probes in a successful search when the load factor is $3/4$ and when it is $7/8$.
Consider an open-address hash table with uniform hashing. Give upper bounds on the expected number of probes in an unsuccessful search and on the expected number of probe...
akash.dinkar12
444
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
hashing
descriptive
+
–
0
votes
0
answers
165
Cormen Edition 3 Exercise 11.4 Question 2 (Page No. 277)
Write pseudo code for $HASH-DELETE$ as outlined in the text, and modify $HASHINSERT$ to handle the special value $DELETED.$
Write pseudo code for $HASH-DELETE$ as outlined in the text, and modify $HASHINSERT$ to handle the special value $DELETED.$
akash.dinkar12
232
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
hashing
descriptive
+
–
0
votes
0
answers
166
Cormen Edition 3 Exercise 11.4 Question 1 (Page No. 277)
Consider inserting the keys $10, 22, 31, 4,15,28,17,88,59$ into a hash table of length $m =11$ using open addressing with the auxiliary hash function $h'(k) =k$ ... double hashing with $h_1(k) =k$ and $h_2(k)$ $=$ $1$+$($k$ $mod$ $(m-1)$)$.
Consider inserting the keys $10, 22, 31, 4,15,28,17,88,59$ into a hash table of length $m =11$ using open addressing with the auxiliary hash function $h’(k) =k$. Illust...
akash.dinkar12
454
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
hashing
descriptive
+
–
0
votes
0
answers
167
Cormen Edition 3 Exercise 11.3 Question 6 (Page No. 269)
Let $U$ be a set of $n-tuples$ of values drawn from$\mathbb{\ Z_p}$ , let $B$ $=$ $\mathbb{\ Z_p}$ , where p is prime. Define the hash function $h_b :U \rightarrow B$ for $b$ $\in$\mathbb{\ Z_p}$ on an input $ ... $\mathscr{H}$ is $n(n-1)/p$- universal according to the definition of the $\epsilon$ universal.
Let $U$ be a set of $n-tuples$ of values drawn from$\mathbb{\ Z_p}$ , let $B$ $=$ $\mathbb{\ Z_p}$ , where p is prime. Define the hash function $h_b :U \rightarrow B$ for...
akash.dinkar12
324
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
hashing
descriptive
+
–
0
votes
0
answers
168
Cormen Edition 3 Exercise 11.3 Question 5 (Page No. 269)
Define a family $\mathscr{H}$ of hash functions from a finite set $U$ to a finite set $B$ to be universal if for all pairs of distinct elements $k$ and $l$ in $U$, $Pr\{h(k) = h(l)\} \leq \epsilon$ where the probability is ... Show that an $\epsilon-$universal family of hash functions must have $\epsilon \geq \frac{1}{|B|} - \frac{1}{|U|}$
Define a family $\mathscr{H}$ of hash functions from a finite set $U$ to a finite set $B$ to be universal if for all pairs of distinct elements $k$ and $l$ in $U$,$Pr\{h(...
akash.dinkar12
272
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
hashing
descriptive
+
–
0
votes
1
answer
169
Cormen Edition 3 Exercise 11.3 Question 4 (Page No. 269)
Consider a hash table of size $m =1000$ and a corresponding hash function $h(k) =$ $\lfloor$ $m$($kA$ $mod$ $1$)$\rfloor$ for $A = \frac{(\sqrt{5} – 1)}{2}$ .Compute the locations to which the keys $61, 62, 63, 64,$ and $65$ are mapped.
Consider a hash table of size $m =1000$ and a corresponding hash function $h(k) =$ $\lfloor$ $m$$($$kA$ $mod$ $1$)$\rfloor$ for $A = \frac{(\sqrt{5} – 1)}{2}$ .Compute...
akash.dinkar12
547
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
hashing
+
–
0
votes
0
answers
170
Cormen Edition 3 Exercise 11.3 Question 3 (Page No. 269)
Consider a version of the division method in which $h(k) =k$ $mod$ $m$, where $m = 2^p-1$ and $k$ is a character string interpreted in $radix$ $2^p$. Show that if we can derive string $x$ from string $y$ by ... $y$ hash to the same value. Give an example of an application in which this property would be undesirable in a hash function.
Consider a version of the division method in which $h(k) =k$ $mod$ $m$, where $m = 2^p-1$ and $k$ is a character string interpreted in $radix$ $2^p$. Show that if we can ...
akash.dinkar12
316
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
hashing
descriptive
+
–
0
votes
0
answers
171
Cormen Edition 3 Exercise 11.3 Question 2 (Page No. 268)
Suppose that we hash a string of $r$ characters into $m$ slots by treating it as a $radix-128$ number and then using the division method. We can easily represent the number $m$ as a $32-bit$ computer word, but ... the hash value of the character string without using more than a constant number of words of storage outside the string itself ?
Suppose that we hash a string of $r$ characters into $m$ slots by treating it as a $radix-128$ number and then using the division method. We can easily represent the numb...
akash.dinkar12
183
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
hashing
descriptive
+
–
0
votes
0
answers
172
Cormen Edition 3 Exercise 11.3 Question 1 (Page No. 268)
Suppose we wish to search a linked list of length $n$, where each element contains a key $k$ along with a hash value $h(k)$. Each key is a long character string. How might we take advantage of the hash values when searching the list for an element with a given key ?
Suppose we wish to search a linked list of length $n$, where each element contains a key $k$ along with a hash value $h(k)$. Each key is a long character string. How migh...
akash.dinkar12
189
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
hashing
descriptive
+
–
0
votes
0
answers
173
Cormen Edition 3 Exercise 11.2 Question 6 (Page No. 261)
Suppose we have stored $n$ keys in a hash table of size $m$, with collisions resolved by chaining, and that we know the length of each chain, including the length $L$ of the longest chain. Describe a procedure that selects a key uniformly at ... the keys in the hash table and returns it in expected time $\mathcal{O}(L*(1+\frac{1}{\alpha}))$.
Suppose we have stored $n$ keys in a hash table of size $m$, with collisions resolved by chaining, and that we know the length of each chain, including the length $L$ of ...
akash.dinkar12
330
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
hashing
descriptive
+
–
0
votes
0
answers
174
Cormen Edition 3 Exercise 11.2 Question 5 (Page No. 261)
Suppose that we are storing a set of $n$ keys into a hash table of size $m$. Show that if the keys are drawn from a universe $U$ with $|U| > nm$, then $U$ has a subset of size $n$ consisting of keys that all hash to the same slot, so that the worst-case searching time for hashing with chaining is $\Theta(n)$.
Suppose that we are storing a set of $n$ keys into a hash table of size $m$. Show that if the keys are drawn from a universe $U$ with $|U| nm$, then $U$ has a subset of ...
akash.dinkar12
272
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
hashing
descriptive
+
–
0
votes
0
answers
175
Cormen Edition 3 Exercise 11.2 Question 4 (Page No. 261)
Suggest how to allocate and deallocate storage for elements within the hash table itself by linking all unused slots into a free list. Assume that one slot can store a flag and either one element plus a pointer or two pointers. All ... expected time. Does the free list need to be doubly linked, or does a singly linked free list suffice?
Suggest how to allocate and deallocate storage for elements within the hash table itself by linking all unused slots into a free list. Assume that one slot can store a fl...
akash.dinkar12
258
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
hashing
descriptive
+
–
0
votes
0
answers
176
Cormen Edition 3 Exercise 11.2 Question 3 (Page No. 261)
Professor Marley hypothesizes that he can obtain substantial performance gains by modifying the chaining scheme to keep each list in sorted order. How does the professor’s modification affect the running time for successful searches, unsuccessful searches, insertions, and deletions?
Professor Marley hypothesizes that he can obtain substantial performance gains by modifying the chaining scheme to keep each list in sorted order. How does the professor�...
akash.dinkar12
474
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
hashing
descriptive
+
–
0
votes
0
answers
177
Cormen Edition 3 Exercise 11.2 Question 2 (Page No. 261)
Demonstrate what happens when we insert the keys $5,28,19,15,20,33,12,17,10$ into a hash table with collisions resolved by chaining. Let the table have $9$ slots, and let the hash function be $h(k) = k$ $mod$ $9$.$
Demonstrate what happens when we insert the keys $5,28,19,15,20,33,12,17,10$ into a hash table with collisions resolved by chaining. Let the table have $9$ slots, and let...
akash.dinkar12
290
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
hashing
+
–
0
votes
0
answers
178
Cormen Edition 3 Exercise 11.2 Question 1 (Page No. 261)
Suppose we use a hash function $h$ to hash $n$ distinct keys into an array $T$ of length $m$. Assuming simple uniform hashing, what is the expected number of collisions ? More precisely, what is the expected cardinality of $\{\{k,l\}:k\neq l and h(k)=h(l)\}$ ?
Suppose we use a hash function $h$ to hash $n$ distinct keys into an array $T$ of length $m$. Assuming simple uniform hashing, what is the expected number of collisions ?...
akash.dinkar12
399
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
hashing
descriptive
+
–
0
votes
0
answers
179
Cormen Edition 3 Exercise 11.1 Question 4 (Page No. 255)
We wish to implement a dictionary by using direct addressing on a huge array. At the start, the array entries may contain garbage, and initializing the entire array is impractical because of its size. Describe a scheme for implementing a ... stored in the dictionary, to help determine whether a given entry in the huge array is valid or not.)
We wish to implement a dictionary by using direct addressing on a huge array. At the start, the array entries may contain garbage, and initializing the entire array is im...
akash.dinkar12
325
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
hashing
descriptive
+
–
0
votes
0
answers
180
Cormen Edition 3 Exercise 11.1 Question 3 (Page No. 255)
Suggest how to implement a direct-address table in which the keys of stored elements do not need to be distinct and the elements can have satellite data. All three dictionary operations ($INSERT$,$ DELETE$, and $SEARCH$ ... (Don't forget that $DELETE$ takes as an argument a pointer to an object to be deleted, not a key.)
Suggest how to implement a direct-address table in which the keys of stored elements do not need to be distinct and the elements can have satellite data. All three dictio...
akash.dinkar12
338
views
akash.dinkar12
asked
Apr 4, 2019
Algorithms
cormen
algorithms
hashing
descriptive
+
–
Page:
« prev
1
2
3
4
5
6
7
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register