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
All Activity
Questions
Unanswered
Tags
Categories
Users
Ask a Question
Prev
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged cormen
0
votes
0
answers
1
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

3
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
2
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

5
views
cormen
algorithms
heap
heapsort
descriptive
difficult
0
votes
0
answers
3
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

5
views
cormen
algorithms
heap
heapsort
descriptive
0
votes
0
answers
4
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

3
views
cormen
algorithms
heap
heapsort
descriptive
0
votes
0
answers
5
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

1
view
cormen
algorithms
heap
heapsort
descriptive
0
votes
0
answers
6
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

4
views
cormen
algorithms
heap
heapsort
descriptive
0
votes
0
answers
7
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

10
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
8
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

5
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
9
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

6
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
10
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

3
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
11
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

4
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
12
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

1
view
cormen
algorithms
heap
descriptive
0
votes
0
answers
13
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

2
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
14
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

2
views
cormen
algorithms
heap
descriptive
0
votes
0
answers
15
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

4
views
cormen
algorithms
heap
descriptive
0
votes
1
answer
16
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

13
views
cormen
algorithms
asymptoticnotations
descriptive
0
votes
0
answers
17
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

13
views
cormen
algorithms
algorithmdesigntechniques
inversions
descriptive
0
votes
0
answers
18
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

3
views
cormen
algorithms
inversions
descriptive
0
votes
1
answer
19
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

12
views
cormen
algorithms
inversions
descriptive
0
votes
1
answer
20
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

6
views
cormen
algorithms
inversions
descriptive
0
votes
1
answer
21
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

31
views
cormen
algorithms
recurrence
timecomplexity
descriptive
0
votes
1
answer
22
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

8
views
cormen
algorithms
algorithmdesigntechniques
descriptive
difficult
0
votes
1
answer
23
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

13
views
algorithms
cormen
searching
descriptive
0
votes
0
answers
24
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

6
views
cormen
algorithms
searching
descriptive
0
votes
1
answer
25
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

25
views
cormen
algorithms
sorting
timecomplexity
descriptive
0
votes
0
answers
26
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
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

5
views
cormen
algorithms
sorting
mergesort
descriptive
0
votes
1
answer
27
Cormen Edition 3 Exercise 2.3 Question 1 (Page No. 37)
Using Figure $2.4$ as a model, illustrate the operation of merge sort on the array $A=\langle 3,41,52,26,38,57,9,49 \rangle $
asked
Jun 26
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

11
views
cormen
algorithms
sorting
mergesort
descriptive
0
votes
1
answer
28
Cormen Edition 3 Exercise 2.2 Question 4 (Page No. 29)
How can we modify almost any algorithm to have a good bestcase running time?
asked
Jun 25
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

22
views
cormen
algorithms
asymptoticnotations
descriptive
0
votes
1
answer
29
Cormen Edition 3 Exercise 2.2 Question 3 (Page No. 29)
Consider the linear search again (see Exercise 2.13). How many elements of the input sequence need to be checked on the average, assuming that the element being searched for is equally likely to be any element in the array? ... case? What are the averagecase and worstcase running times of linear search in notation? Justify your answers.
asked
Jun 25
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

18
views
cormen
algorithms
searching
descriptive
0
votes
1
answer
30
Cormen Edition 3 Exercise 2.2 Question 2 (Page No. 29)
Consider sorting $n$ numbers stored in an array $A$ by first finding the smallest element of $A$ and exchanging it with the element in $A[1]$. Then find the second smallest element of $A$ ... , rather than for all n elements? Give the bestcase and worstcase running times of selection sort in $\Theta$notation
asked
Jun 25
in
Algorithms
by
akash.dinkar12
Boss
(
41.3k
points)

14
views
algorithms
cormen
timecomplexity
descriptive
Page:
« prev
1
2
3
4
5
6
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
ISI MTECH CS 2019 INTERVIEW EXPERIENCE
IIT HYDERABAD MTECH TA INTERVIEW EXPERIENCE
How to prepare for GATE with a fulltime job??
Interview Experience at IISc
All subject Gate notes from Standard Books!!
Follow @csegate
Recent questions tagged cormen
Recent Blog Comments
Refund time depends on the payment mode ...
@Arjun Sir , when can i expect my refund in the...
This book is returned you can enable a pay now...
@Pranavcool The book stocks are over and no one...
@Lokesh Thats unfortunate. I have refunded you....
49,830
questions
54,800
answers
189,506
comments
80,732
users