Login
Register
Dark Mode
Brightness
Profile
Edit Profile
Messages
My favorites
My Updates
Logout
Filter
akash.dinkar12
Wall
Recent activity
All questions
All answers
Exams Taken
All Blogs
Questions by akash.dinkar12
0
votes
0
answers
1
Cormen Edition 3 Exercise 10.2 Question 8 (Page No. 241)
Explain how to implement doubly linked lists using only one pointer value $x.np$ per item instead of the usual two (next and prev). Assume that all pointer values can be interpreted as $k$-bit integers, and define $x.np$ ... $INSERT$, and $DELETE$ operations on such a list. Also, show how to reverse such a list in $O(1)$ time.
Explain how to implement doubly linked lists using only one pointer value $x.np$ per item instead of the usual two (next and prev). Assume that all pointer values can be ...
637
views
asked
Jun 30, 2019
Algorithms
cormen
data-structures
linked-list
descriptive
difficult
+
–
0
votes
1
answer
2
Cormen Edition 3 Exercise 10.2 Question 7 (Page No. 241)
Give a $\Theta(n)$ time nonrecursive procedure that reverses a singly linked list of $n$ elements. The procedure should use no more than constant storage beyond that needed for the list itself.
Give a $\Theta(n)$ time nonrecursive procedure that reverses a singly linked list of $n$ elements. The procedure should use no more than constant storage beyond that need...
888
views
asked
Jun 30, 2019
Algorithms
cormen
data-structures
linked-list
descriptive
+
–
1
votes
1
answer
3
Cormen Edition 3 Exercise 10.2 Question 6 (Page No. 241)
The dynamic-set operation $UNION$ takes two disjoint sets $S_1$ and $S_2$ as input, and it returns a set $S=S_1 \cup S_2$ consisting of all the elements of $S_1$ and $S_2$.The sets $S_1$ and $S_2$ are usually destroyed by the operation. Show how to support $UNION$ in $O(1)$ time using a suitable list data structure.
The dynamic-set operation $UNION$ takes two disjoint sets $S_1$ and $S_2$ as input, and it returns a set $S=S_1 \cup S_2$ consisting of all the elements of $S_1$ and $S_2...
586
views
asked
Jun 30, 2019
Algorithms
cormen
data-structures
linked-list
descriptive
+
–
1
votes
1
answer
4
Cormen Edition 3 Exercise 10.2 Question 5 (Page No. 240)
Implement the dictionary operations $INSERT$, $DELETE$, and $SEARCH$ using singly linked, circular lists. What are the running times of your procedures?
Implement the dictionary operations $INSERT$, $DELETE$, and $SEARCH$ using singly linked, circular lists. What are the running times of your procedures?
607
views
asked
Jun 30, 2019
Algorithms
cormen
data-structures
linked-list
descriptive
+
–
0
votes
0
answers
5
Cormen Edition 3 Exercise 10.2 Question 4 (Page No. 240)
LIST-SEARCH’(L, k) 1 x = L.nil.next 2 while x != L.nil and x.key != k 3 x = x.next 4 return x As written, each loop iteration in the LIST-SEARCH’ procedure requires two tests: one for $x\neq L.nil$ and one for $x.key\neq k$. Show how to eliminate the test for $x\neq L.nil$ in each iteration.
LIST-SEARCH’(L, k) 1 x = L.nil.next 2 while x != L.nil and x.key != k 3 x = x.next 4 return xAs written, each loop iteration in the LIST-SEARCH’ procedure requires tw...
372
views
asked
Jun 30, 2019
Algorithms
cormen
data-structures
linked-list
descriptive
+
–
1
votes
2
answers
6
Cormen Edition 3 Exercise 10.2 Question 3 (Page No. 240)
Implement a queue by a singly linked list $L$. The operations of $ENQUEUE$ and $DEQUEUE$ should still take $O(1)$ time.
Implement a queue by a singly linked list $L$. The operations of $ENQUEUE$ and $DEQUEUE$ should still take $O(1)$ time.
389
views
asked
Jun 30, 2019
Algorithms
cormen
data-structures
linked-list
descriptive
+
–
1
votes
1
answer
7
Cormen Edition 3 Exercise 10.2 Question 2 (Page No. 240)
Implement a stack using a singly linked list $L$. The operations $PUSH$ and $POP$ should still take $O(1)$ time.
Implement a stack using a singly linked list $L$. The operations $PUSH$ and $POP$ should still take $O(1)$ time.
394
views
asked
Jun 30, 2019
Algorithms
cormen
data-structures
linked-list
descriptive
+
–
0
votes
1
answer
8
Cormen Edition 3 Exercise 10.2 Question 1 (Page No. 240)
Can you implement the dynamic-set operation $INSERT$ on a singly linked list in $O(1)$ time? How about $DELETE$?
Can you implement the dynamic-set operation $INSERT$ on a singly linked list in $O(1)$ time? How about $DELETE$?
499
views
asked
Jun 30, 2019
Algorithms
cormen
data-structures
linked-list
descriptive
+
–
4
votes
2
answers
9
Cormen Edition 3 Exercise 10.1 Question 7 (Page No. 236)
Show how to implement a stack using two queues. Analyze the running time of the stack operations.
Show how to implement a stack using two queues. Analyze the running time of the stack operations.
1.3k
views
asked
Jun 28, 2019
Algorithms
cormen
data-structures
stack
descriptive
+
–
1
votes
2
answers
10
Cormen Edition 3 Exercise 10.1 Question 6 (Page No. 236)
Show how to implement a queue using two stacks. Analyze the running time of the queue operations.
Show how to implement a queue using two stacks. Analyze the running time of the queue operations.
553
views
asked
Jun 28, 2019
Algorithms
cormen
data-structures
queue
descriptive
+
–
0
votes
1
answer
11
Cormen Edition 3 Exercise 10.1 Question 5 (Page No. 236)
Whereas a stack allows insertion and deletion of elements at only one end, and a queue allows insertion at one end and deletion at the other end, a deque (double ended queue) allows insertion and deletion at both ends. Write ... time procedures to insert elements into and delete elements from both ends of a deque implemented by an array.
Whereas a stack allows insertion and deletion of elements at only one end, and a queue allows insertion at one end and deletion at the other end, a deque (double ended qu...
1.6k
views
asked
Jun 28, 2019
Algorithms
cormen
algorithms
data-structures
queue
descriptive
+
–
0
votes
1
answer
12
Cormen Edition 3 Exercise 10.1 Question 4 (Page No. 235)
Rewrite ENQUEUE and DEQUEUE to detect underflow and overflow of a queue.
Rewrite ENQUEUE and DEQUEUE to detect underflow and overflow of a queue.
553
views
asked
Jun 28, 2019
Algorithms
cormen
data-structures
queue
descriptive
+
–
0
votes
1
answer
13
Cormen Edition 3 Exercise 10.1 Question 3 (Page No. 235)
ENQUEUE(Q, x) 1 Q[Q.tail] = x 2 if Q.tail == Q.length 3 Q.tail = 1 4 else Q.tail = Q.tail + 1 DEQUEUE(Q) 1 x = Q[Q.head] 2 if Q.head == Q.length 3 Q.head = 1 4 else Q.head = Q.head + 1 5 return x illustrate the ... (Q,4),ENQUEUE(Q,1),ENQUEUE(Q,3),DEQUEUE(Q),ENQUEUE(Q,8),DEQUEUE(Q) on an initially empty queue $Q$ stored in array $Q[1...6]$.
ENQUEUE(Q, x) 1 Q[Q.tail] = x 2 if Q.tail == Q.length 3 Q.tail = 1 4 else Q.tail = Q.tail + 1 DEQUEUE(Q) 1 x = Q[Q.head] 2 if Q.head == Q.length 3 Q.head = 1 4 else Q.hea...
410
views
asked
Jun 28, 2019
Algorithms
cormen
data-structures
queue
descriptive
+
–
1
votes
1
answer
14
Cormen Edition 3 Exercise 10.1 Question 2 (Page No. 235)
Explain how to implement two stacks in one array $A[1...n]$ in such a way that neither stack overflows unless the total number of elements in both stacks together is $n$.The $PUSH$ and $POP$ operations should run in $O(1)$ time.
Explain how to implement two stacks in one array $A[1...n]$ in such a way that neither stack overflows unless the total number of elements in both stacks together is $n$....
2.5k
views
asked
Jun 28, 2019
Algorithms
cormen
data-structures
stack
descriptive
+
–
1
votes
1
answer
15
Cormen Edition 3 Exercise 10.1 Question 1 (Page No. 235)
STACK-EMPTY(S) 1 if S.top == 0 2 return TRUE 3 else return FALSE PUSH(S , x) 1 S.top = S.top + 1 2 S[S.top] = x POP(S) 1 if STACK-EMPTY(S) 2 error underflow 3 else S.top = S.top - 1 4 return S[S.top + 1] illustrate the result of ... $S$ stored in array $S[1...6]$
STACK-EMPTY(S) 1 if S.top == 0 2 return TRUE 3 else return FALSE PUSH(S , x) 1 S.top = S.top + 1 2 S[S.top] = x POP(S) 1 if STACK-EMPTY(S) 2 error “underflow” 3 else ...
536
views
asked
Jun 28, 2019
Algorithms
cormen
data-structures
stack
descriptive
+
–
0
votes
1
answer
16
Cormen Edition 3 Exercise 9.1 Question 2 (Page No. 215)
Prove the lower bound of $\lceil 3n/2\rceil – 2$ comparisons in the worst case to find both the maximum and minimum of $n$ numbers. (Hint: Consider how many numbers are potentially either the maximum or minimum and investigate how a comparison affects these counts.)
Prove the lower bound of $\lceil 3n/2\rceil – 2$ comparisons in the worst case to find both the maximum and minimum of $n$ numbers. (Hint: Consider how many numbers are...
1.2k
views
asked
Jun 28, 2019
Algorithms
cormen
algorithms
descriptive
+
–
0
votes
2
answers
17
Cormen Edition 3 Exercise 9.1 Question 1 (Page No. 215)
Show that the second smallest of $n$ elements can be found with $n+\lceil lg\ n \rceil -2$ comparisons in the worst case. (Hint: Also find the smallest element.)
Show that the second smallest of $n$ elements can be found with $n+\lceil lg\ n \rceil -2$ comparisons in the worst case. (Hint: Also find the smallest element.)
455
views
asked
Jun 28, 2019
Algorithms
cormen
algorithms
descriptive
+
–
1
votes
0
answers
18
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,…,...
441
views
asked
Jun 28, 2019
Algorithms
cormen
algorithms
sorting
bucket-sort
descriptive
difficult
+
–
0
votes
0
answers
19
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...
635
views
asked
Jun 28, 2019
Algorithms
cormen
algorithms
sorting
bucket-sort
descriptive
difficult
+
–
1
votes
1
answer
20
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]$?
711
views
asked
Jun 28, 2019
Algorithms
cormen
algorithms
sorting
bucket-sort
expectation
descriptive
+
–
Page:
1
2
3
4
5
6
...
28
next »
Email or Username
Show
Hide
Password
I forgot my password
Remember
Log in
Register