Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Recent questions tagged bucket-sort
1
votes
0
answers
1
Cormen Edition 3 Exercise 8.4 Question 5 (Page No. 204)
A probability distribution function $P(x)$ for a random variable $X$ is defined by $P(x) =Pr\{X\leq x\}$.Suppose that we draw a list of $n$ random variables $X_1,X_2,…,X_n$ from a continuous probability distribution function $P$ that is computable in $O(1)$ time. Give an algorithm that sorts these numbers in linear averagecase time.
A probability distribution function $P(x)$ for a random variable $X$ is defined by $P(x) =Pr\{X\leq x\}$.Suppose that we draw a list of $n$ random variables $X_1,X_2,…,...
akash.dinkar12
452
views
akash.dinkar12
asked
Jun 28, 2019
Algorithms
cormen
algorithms
sorting
bucket-sort
descriptive
difficult
+
–
0
votes
0
answers
2
Cormen Edition 3 Exercise 8.4 Question 4 (Page No. 204)
We are given $n$ points in the unit circle, $P_i=(x_i,y_i)$, such that $0<x_i^2+y_i^2<1$ for $i=1,2, .,n$.Suppose that the points are uniformly distributed; that is, the probability of finding a point in ... the origin. (Hint: Design the bucket sizes in BUCKET-SORT to reflect the uniform distribution of the points in the unit circle.)
We are given $n$ points in the unit circle, $P_i=(x_i,y_i)$, such that $0<x_i^2+y_i^2<1$ for $i=1,2,….,n$.Suppose that the points are uniformly distributed; that is, th...
akash.dinkar12
648
views
akash.dinkar12
asked
Jun 28, 2019
Algorithms
cormen
algorithms
sorting
bucket-sort
descriptive
difficult
+
–
1
votes
1
answer
3
Cormen Edition 3 Exercise 8.4 Question 3 (Page No. 204)
Let $X$ be a random variable that is equal to the number of heads in two flips of a fair coin. What is $E[X^2]$? What is $E^2[X]$?
Let $X$ be a random variable that is equal to the number of heads in two flips of a fair coin. What is $E[X^2]$? What is $E^2[X]$?
akash.dinkar12
753
views
akash.dinkar12
asked
Jun 28, 2019
Algorithms
cormen
algorithms
sorting
bucket-sort
expectation
descriptive
+
–
1
votes
1
answer
4
Cormen Edition 3 Exercise 8.4 Question 2 (Page No. 204)
Explain why the worst-case running time for bucket sort is $\Theta(n^2)$. What simple change to the algorithm preserves its linear average-case running time and makes its worst-case running time $O(n\ lg\ n)$?
Explain why the worst-case running time for bucket sort is $\Theta(n^2)$. What simple change to the algorithm preserves its linear average-case running time and makes its...
akash.dinkar12
680
views
akash.dinkar12
asked
Jun 28, 2019
Algorithms
cormen
algorithms
sorting
bucket-sort
descriptive
+
–
0
votes
1
answer
5
Cormen Edition 3 Exercise 8.4 Question 1 (Page No. 204)
BUCKET-SORT(A) 1 let B[0...n-1] be a new array 2 n = A.length 3 for i - 0 to n - 1 4 make B[i] an empty list 5 for i = 1 to n 6 insert A[i] into list B[nA[i]] 7 for i = 0 to n - 1 8 sort list B[i] with ... ,B[n-1] together in order illustrate the operation of BUCKET-SORT on the array $A=\langle .79,.13,.16,.64,.39,.20,.89,.53,.71,.42\rangle$
BUCKET-SORT(A) 1 let B[0...n-1] be a new array 2 n = A.length 3 for i – 0 to n – 1 4 make B[i] an empty list 5 for i = 1 to n 6 insert A[i] into list B[nA[i]] 7 for i...
akash.dinkar12
421
views
akash.dinkar12
asked
Jun 28, 2019
Algorithms
cormen
algorithms
sorting
bucket-sort
descriptive
+
–
1
votes
1
answer
6
Suppose we radix sort n words of b bits each
Suppose we radix sort n words of b bits each. Each could be viewed as having (b/r) digits or r bits each. for some integer r now fill in the blanks a)Each part of radix sort takes _________ time 2) At min r= _______ 3)T(n,b)= ____________
Suppose we radix sort n words of b bits each. Each could be viewed as having (b/r) digits or r bits each. for some integer r now fill in the blanksa)Each part of radix so...
Sanjay Sharma
524
views
Sanjay Sharma
asked
Feb 20, 2018
Algorithms
bucket-sort
+
–
To see more, click for the
full list of questions
or
popular tags
.
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register