Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
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$.
akash.dinkar12
asked
in
Algorithms
Apr 4, 2019
by
akash.dinkar12
213
views
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)$ ?
akash.dinkar12
asked
in
Algorithms
Apr 4, 2019
by
akash.dinkar12
307
views
cormen
algorithms
asymptotic-notation
descriptive
difficult
1
vote
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 ?
akash.dinkar12
asked
in
Algorithms
Apr 4, 2019
by
akash.dinkar12
175
views
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.
akash.dinkar12
asked
in
Algorithms
Apr 4, 2019
by
akash.dinkar12
317
views
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))$.
akash.dinkar12
asked
in
Algorithms
Apr 4, 2019
by
akash.dinkar12
318
views
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.
akash.dinkar12
asked
in
Algorithms
Apr 4, 2019
by
akash.dinkar12
2.6k
views
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))$.
akash.dinkar12
asked
in
Algorithms
Apr 4, 2019
by
akash.dinkar12
258
views
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)$?$
akash.dinkar12
asked
in
Algorithms
Apr 4, 2019
by
akash.dinkar12
529
views
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.
akash.dinkar12
asked
in
Algorithms
Apr 4, 2019
by
akash.dinkar12
603
views
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)$
akash.dinkar12
asked
in
Algorithms
Apr 4, 2019
by
akash.dinkar12
302
views
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))$.
akash.dinkar12
asked
in
Algorithms
Apr 4, 2019
by
akash.dinkar12
378
views
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.
akash.dinkar12
asked
in
Algorithms
Apr 4, 2019
by
akash.dinkar12
383
views
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.
akash.dinkar12
asked
in
Algorithms
Apr 4, 2019
by
akash.dinkar12
380
views
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$.
akash.dinkar12
asked
in
Algorithms
Apr 4, 2019
by
akash.dinkar12
451
views
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.$
akash.dinkar12
asked
in
Algorithms
Apr 4, 2019
by
akash.dinkar12
235
views
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)$)$.
akash.dinkar12
asked
in
Algorithms
Apr 4, 2019
by
akash.dinkar12
459
views
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.
akash.dinkar12
asked
in
Algorithms
Apr 4, 2019
by
akash.dinkar12
329
views
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|}$
akash.dinkar12
asked
in
Algorithms
Apr 4, 2019
by
akash.dinkar12
278
views
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.
akash.dinkar12
asked
in
Algorithms
Apr 4, 2019
by
akash.dinkar12
555
views
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.
akash.dinkar12
asked
in
Algorithms
Apr 4, 2019
by
akash.dinkar12
318
views
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 ?
akash.dinkar12
asked
in
Algorithms
Apr 4, 2019
by
akash.dinkar12
187
views
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 ?
akash.dinkar12
asked
in
Algorithms
Apr 4, 2019
by
akash.dinkar12
194
views
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}))$.
akash.dinkar12
asked
in
Algorithms
Apr 4, 2019
by
akash.dinkar12
334
views
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)$.
akash.dinkar12
asked
in
Algorithms
Apr 4, 2019
by
akash.dinkar12
278
views
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?
akash.dinkar12
asked
in
Algorithms
Apr 4, 2019
by
akash.dinkar12
262
views
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?
akash.dinkar12
asked
in
Algorithms
Apr 4, 2019
by
akash.dinkar12
476
views
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$.$
akash.dinkar12
asked
in
Algorithms
Apr 4, 2019
by
akash.dinkar12
294
views
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)\}$ ?
akash.dinkar12
asked
in
Algorithms
Apr 4, 2019
by
akash.dinkar12
406
views
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.)
akash.dinkar12
asked
in
Algorithms
Apr 4, 2019
by
akash.dinkar12
332
views
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.)
akash.dinkar12
asked
in
Algorithms
Apr 4, 2019
by
akash.dinkar12
342
views
cormen
algorithms
hashing
descriptive
Page:
« prev
1
2
3
4
5
6
7
next »
Subscribe to GATE CSE 2024 Test Series
Subscribe to GO Classes for GATE CSE 2024
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
-tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
Post GATE 2024 Guidance [Counseling tips and resources]
GATE CSE 2024 Result Responses
[Project Contest] Pytorch backend support for MLCommons Cpp Inference implementation
Participating in MLCommons Inference v4.0 submission (deadline is February 23 12pm IST)
IIITH PGEE 2024 Test Series by GO Classes
Subjects
All categories
General Aptitude
(3.5k)
Engineering Mathematics
(10.4k)
Digital Logic
(3.6k)
Programming and DS
(6.2k)
Algorithms
(4.8k)
Theory of Computation
(6.9k)
Compiler Design
(2.5k)
Operating System
(5.2k)
Databases
(4.8k)
CO and Architecture
(4.0k)
Computer Networks
(4.9k)
Artificial Intelligence
(79)
Machine Learning
(48)
Data Mining and Warehousing
(25)
Non GATE
(1.4k)
Others
(2.7k)
Admissions
(684)
Exam Queries
(1.6k)
Tier 1 Placement Questions
(17)
Job Queries
(80)
Projects
(11)
Unknown Category
(870)
64.3k
questions
77.9k
answers
244k
comments
80.0k
users
Recent questions tagged cormen
Recent Blog Comments
category ?
Hi @Arjun sir, I have obtained a score of 591 in ...
download here
Can you please tell about IIT-H mtech CSE self...
Please add your admission queries here:...