The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent questions tagged cormen
0
votes
0
answers
1
Cormen Edition 3 Exercise 6.5 Question 5 (Page No. 166)
Argue the correctness of HEAPINCREASEKEY using the following loop invariant: At the start of each iteration of the while loop of lines $46$, the subarray $A[1..A.heapsize]$ satisfies the maxheap property, except that there ... assume that the subarray $A[a..heapsize]$ satisfies the maxheap property at the time HEAPINCREASEKEY is called.
asked
Jun 27, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.3k
points)

6
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
2
Cormen Edition 3 Exercise 6.5 Question 4 (Page No. 165)
Why do we bother setting the key of the inserted node to $\infty$ in line $2$ of MAXHEAPINSERT when the next thing we do is increase its key to the desired value?
asked
Jun 27, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.3k
points)

6
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
3
Cormen Edition 3 Exercise 6.5 Question 3 (Page No. 165)
Write pseudo code for the procedures HEAPMINIMUM, HEAPEXTRACTMIN, HEAPDECREASEKEY, and MINHEAPINSERT that implement a minpriority queue with a minheap.
asked
Jun 27, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.3k
points)

5
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
4
Cormen Edition 3 Exercise 6.5 Question 2 (Page No. 165)
HEAPINCREASEKEY(A,i,key) 1 if key < A[i] 2 error new key is smaller than current key 3 A[i] = key 4 while i > 1 and A[parent(i)] < A[i] 5 exchange A[i] with A[parent(i)] 6 i=parent(i) MAXHEAPINSERT(A,key) 1 A ... ,key) Illustrate the operation of MAXHEAPINSERT$(A,10)$ on the heap $A=\langle 15,13,9,5,12,8,7,4,0,6,2,1 \rangle$.
asked
Jun 27, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.3k
points)

14
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
5
Cormen Edition 3 Exercise 6.5 Question 1 (Page No. 164)
HEAPEXTRACTMAX(A) 1 if A.heapsize < 1 2 error “heap underflow” 3 max=A[1] 4 A[1]=A[A.heapsize] 5 A.heapsize=A.heapsize1 6 MAXHEAPIFY(A,1) 7 return max Illustrate the operation of HEAPEXTRACTMAX on the heap $A=\langle 15,13,9,5,12,8,7,4,0,6,2,1 \rangle$.
asked
Jun 27, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.3k
points)

7
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
6
Cormen Edition 3 Exercise 6.4 Question 5 (Page No. 161)
Show that when all elements are distinct, the bestcase running time of HEAPSORT is $\Omega(n\lg\ n)$.
asked
Jun 27, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.3k
points)

11
views
cormen
algorithms
heap
heapsort
descriptive
difficult
0
votes
0
answers
7
Cormen Edition 3 Exercise 6.4 Question 4 (Page No. 160)
Show that the worstcase running time of HEAPSORT is $\Omega(n\lg\ n)$.
asked
Jun 27, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.3k
points)

12
views
cormen
algorithms
heap
heapsort
descriptive
0
votes
0
answers
8
Cormen Edition 3 Exercise 6.4 Question 3 (Page No. 160)
What is the running time of HEAPSORT on an array $A$ of length $n$ that is already sorted in increasing order? What about decreasing order?
asked
Jun 27, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.3k
points)

5
views
cormen
algorithms
heap
heapsort
descriptive
0
votes
0
answers
9
Cormen Edition 3 Exercise 6.4 Question 2 (Page No. 160)
Argue the correctness of HEAPSORT using the following loop invariant: At the start of each iteration of the for loop of lines $2–5$,the subarray $A[1..i]$ is a maxheap containing the $i$ smallest elements of $A[1..n] $, and the subarray $A[i+1..n]$ contains the $n i$ largest elements of $A[1..n]$, sorted.
asked
Jun 27, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.3k
points)

5
views
cormen
algorithms
heap
heapsort
descriptive
0
votes
0
answers
10
Cormen Edition 3 Exercise 6.4 Question 1 (Page No. 160)
HEAPSORT(A) 1 BUILDMAXHEAP(A) 2 for i = A.length down to 2 3 exchange A[1] with A[i] 4 A.heapsize=A.heapsize – 1 5 MAXHEAPIFY(A,1) illustrate the operation of HEAPSORT on the array $A=\langle 5,13,2,25,7,17,20,8,4 \rangle$
asked
Jun 27, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.3k
points)

11
views
cormen
algorithms
heap
heapsort
descriptive
0
votes
0
answers
11
Cormen Edition 3 Exercise 6.3 Question 3 (Page No. 159)
Show that there are at most $\lceil n/2^{h+1}\rceil$ nodes of height $h$ in any $n$element heap.
asked
Jun 26, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.3k
points)

14
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
12
Cormen Edition 3 Exercise 6.3 Question 2 (Page No. 159)
Why do we want the loop index $i$ in line $2$ of BUILDMAXHEAP to decrease from $\lfloor A.length/2 \rfloor$ to 1 rather than increase from 1 to $\lfloor A.length/2 \rfloor$?
asked
Jun 26, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.3k
points)

9
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
13
Cormen Edition 3 Exercise 6.3 Question 1 (Page No. 159)
BUILDMAXHEAP(A) 1 A.heapsize=A.length 2 for i=A.length/2 downto 1 3 MAXHEAPIFY(A,i) Using Figure $6.3$ as a model, illustrate the operation of BUILDMAXHEAP on the array $A=\langle 5,3,17,10,84,19,6,22,9 \rangle $
asked
Jun 26, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.3k
points)

10
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
14
Cormen Edition 3 Exercise 6.2 Question 6 (Page No. 156)
Show that the worstcase running time of MAXHEAPIFY on a heap of size $n$ is $\Omega(lg\ n)$.(Hint: For a heap with $n$ nodes, give node values that cause MAXHEAPIFY to be called recursively at every node on a simple path from the root down to a leaf).
asked
Jun 26, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.3k
points)

5
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
15
Cormen Edition 3 Exercise 6.2 Question 5 (Page No. 156)
The code for MAXHEAPIFY is quite efficient in terms of constant factors, except possibly for the recursive call in line 10, which might cause some compilers to produce inefficient code. Write an efficient MAXHEAPIFY that uses an iterative control construct (a loop) instead of recursion.
asked
Jun 26, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.3k
points)

7
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
16
Cormen Edition 3 Exercise 6.2 Question 4 (Page No. 156)
What is the effect of calling MAXHEAPIFY$(A,i)$ for $i > A.heapsize/2$.
asked
Jun 26, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.3k
points)

4
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
17
Cormen Edition 3 Exercise 6.2 Question 3 (Page No. 156)
What is the effect of calling MAXHEAPIFY$(A, i)$ when the element $A[i]$ is larger than its children?
asked
Jun 26, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.3k
points)

6
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
18
Cormen Edition 3 Exercise 6.2 Question 2 (Page No. 156)
Starting with the procedure MAXHEAPIFY, write pseudocode for the procedure MINHEAPIFY$(A, i )$, which performs the corresponding manipulation on a minheap. How does the running time of MINHEAPIFY compare to that of MAXHEAPIFY?
asked
Jun 26, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.3k
points)

4
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
19
Cormen Edition 3 Exercise 6.2 Question 1 (Page No. 156)
MAXHEAPIFY(A,i) 1 l=Left(i) 2 r=Right(i) 3 if l <= A.heapsize and A[l] > A[i] 4 largest=l 5 else largest = i 6 if r <= A.heapsize and A[r] > A[largest] 7 largest=r 8 if largest!=i 9 exchange A[i] with A[ ... model, illustrate the operation of MAXHEAPIFY(A,3) on the array $A=\langle 27,17,3,16,13,10, 1,5,7,12,4,8,9,0 \rangle$
asked
Jun 26, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.3k
points)

9
views
cormen
algorithms
heap
descriptive
0
votes
1
answer
20
Cormen Edition 3 Exercise 3.2 Question 3 (Page No. 60)
Prove that $n!=\omega(2^n)$ and $n!=o(n^n)$.
asked
Jun 26, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.3k
points)

21
views
cormen
algorithms
asymptoticnotations
descriptive
0
votes
0
answers
21
Cormen Edition 3 Exercise 2.4 Question 4 (Page No. 42)
Give an algorithm that determines the number of inversions in any permutation on $n$ elements in $\Theta (n\ lg\ n)$ worstcase time. (Hint: Modify merge sort.)
asked
Jun 26, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.3k
points)

15
views
cormen
algorithms
algorithmdesigntechniques
inversions
descriptive
0
votes
0
answers
22
Cormen Edition 3 Exercise 2.4 Question 3 (Page No. 42)
What is the relationship between the running time of insertion sort and the number of inversions in the input array? Justify your answer.
asked
Jun 26, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.3k
points)

10
views
cormen
algorithms
inversions
descriptive
0
votes
1
answer
23
Cormen Edition 3 Exercise 2.4 Question 2 (Page No. 42)
What array with elements from the set $\{1,2,\dots n\}$ has the most inversions? How many does it have?
asked
Jun 26, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.3k
points)

15
views
cormen
algorithms
inversions
descriptive
0
votes
1
answer
24
Cormen Edition 3 Exercise 2.4 Question 1 (Page No. 41)
List the five inversions of the array $\langle 2,3,8,6,1\rangle$
asked
Jun 26, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.3k
points)

12
views
cormen
algorithms
inversions
descriptive
0
votes
1
answer
25
Cormen Edition 3 Exercise 2.3 Question 3 (Page No. 39)
Use mathematical induction to show that when $n$ is an exact power of $2$, the solution of the recurrence $T(n) = \begin{cases} 2 \text{, if n=2, } \\2T(n/2)+n \text{, if n=$2^k$,for k >1} \end{cases}$ is $T(n) = n\ lg\ n$.
asked
Jun 26, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.3k
points)

55
views
cormen
algorithms
recurrence
timecomplexity
descriptive
0
votes
1
answer
26
Cormen Edition 3 Exercise 2.3 Question 7 (Page No. 39)
Describe a $\Theta(n\ lg\ n)$ time algorithm that, given a set $S$ of $n$ integers and another integer $x$, determines whether or not there exist two elements in $S$ whose sum is exactly $x$.
asked
Jun 26, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.3k
points)

12
views
cormen
algorithms
algorithmdesigntechniques
descriptive
difficult
0
votes
1
answer
27
Cormen Edition 3 Exercise 2.3 Question 6 (Page No. 39)
Observe that the while loop of the INSERTIONSORT procedure uses a linear search to scan (backward) through the sorted subarray $A[i\dots j1]$ Can we use a binary search (see Exercise 2.35) instead to improve the overall worstcase running time of insertion sort to $\Theta(n\ lg\ n)$?
asked
Jun 26, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.3k
points)

18
views
algorithms
cormen
searching
descriptive
0
votes
0
answers
28
Cormen Edition 3 Exercise 2.3 Question 5 (Page No. 39)
Referring back to the searching problem (see Exercise 2.13), observe that if the sequence $A$ is sorted, we can check the midpoint of the sequence against $v$ and eliminate half of the sequence from further consideration. The binary ... recursive, for binary search. Argue that the worstcase running time of binary search is $\Theta (lg\ n)$.
asked
Jun 26, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.3k
points)

13
views
cormen
algorithms
searching
descriptive
0
votes
1
answer
29
Cormen Edition 3 Exercise 2.3 Question 4 (Page No. 38)
We can express the insertion sort as a recursive procedure as follows.In order to sort $A[1\dots n]$, we recursively sort $A[1 \dots n1]$ and then insert $A[n]$ into the sorted array $A[1 \dots n1]$. Write a recurrence for the running time of this recursive version of insertion sort.
asked
Jun 26, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.3k
points)

41
views
cormen
algorithms
sorting
timecomplexity
descriptive
0
votes
0
answers
30
Cormen Edition 3 Exercise 2.3 Question 2 (Page No. 37)
Rewrite the MERGE procedure so that it does not use sentinels, instead of stopping once either array $L$ or $R$ has had all its elements copied back to $A$ and then copying the remainder of the other array back into $A$.
asked
Jun 26, 2019
in
Algorithms
by
akash.dinkar12
Boss
(
42.3k
points)

19
views
cormen
algorithms
sorting
mergesort
descriptive
Page:
« prev
1
2
3
4
5
6
7
next »
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
ISRO CSE 2020 PAPER ANALYSE
BARC OCES/DGFS 2020
ISI CMI PDF by GATE Overflow
Management Trainee Recruitment COAL INDIA 2020
ECIL Interview Experience
Follow @csegate
Recent questions tagged cormen
Recent Blog Comments
it's depends year to year
What was the average cutoff that was maintained...
@Shivateja MST I don't think it will go high
http://univ.tifr.res.in/gs2020/Test_Results/INT_Sh...
TIFR interview shortlist is published.
50,741
questions
57,243
answers
198,012
comments
104,604
users