Stack Overflow
Stack Overflow

Questions tagged [clrs]

CLRS refers to the textbook "Introduction to Algorithms" by Thomas H. Cormen, Charles E. Leiserson, Ronald R. Rivest, and Clifford Stein. It is a standard textbook in algorithms and data structures.

170 questions
319
votes
16 answers

What is a loop invariant?

I'm reading "Introduction to Algorithm" by CLRS. In chapter 2, the authors mention "loop invariants". What is a loop invariant?
Attilah
  • 17,632
  • 38
  • 139
  • 202
20
votes
6 answers

asymptotic tight bound for quadratic functions

In CLRS (Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein), for a function f(n) = an2 + bn + c they said Suppose we take the constants c1 = a/4, c2 = 7a/4, and n0 = 2·max(|b|/a, √(|c|/a)). Then 0 ≤ c1n2 ≤ an2 + bn + c ≤ c2n2…
Happy Mittal
  • 3,667
  • 12
  • 44
  • 60
20
votes
7 answers

Unbiased random number generator using a biased one

You have a biased random number generator that produces a 1 with a probability p and 0 with a probability (1-p). You do not know the value of p. Using this make an unbiased random number generator which produces 1 with a probability 0.5 and 0 with a…
Rohit Banga
  • 18,458
  • 31
  • 113
  • 191
19
votes
2 answers

worst case in MAX-HEAPIFY: "the worst case occurs when the bottom level of the tree is exactly half full"

In CLRS, third Edition, on page 155, it is given that in MAX-HEAPIFY, "the worst case occurs when the bottom level of the tree is exactly half full" I guess the reason is that in this case, Max-Heapify has to "float down" through the left…
Happy Mittal
  • 3,667
  • 12
  • 44
  • 60
18
votes
1 answer

Red black tree pseudocode redundancy

In introduction to Algorithms Third Edition they have a pseudocode implementation of red-black tree deletion. Here it is... RB-DELETE(T, z) y = z y-original-color = y.color if z.left == T.nil x = z.right RB-TRANSPLANT(T,…
confused
  • 213
  • 2
  • 6
16
votes
2 answers

Graph - Square of a directed graph

Yes, this will be a homework (I am self-learning not for university) question but I am not asking for solution. Instead, I am hoping to clarify the question itself. In CLRS 3rd edition, page 593, excise 22.1-5, The square of a directed graph G =…
Jackson Tale
  • 25,428
  • 34
  • 149
  • 271
14
votes
5 answers

Implementing a direct address table

I was given as homework the Introduction to Algorithms exercise 11.1-3 which goes as follows: Suggest how to implement a direct-access table in which the keys of stored elements do not need to be distinct and the elements can have satellite data.…
CS n00b
  • 149
  • 1
  • 3
13
votes
5 answers

Does dijkstras algorithm relax the edges of the shortest path in order?

In "Introduction to algorithms, 3rd edition" exercise 24.3-5 wants an example that this is wrong (not always true). Is that possible? In my mind this is impossible because every edge is relaxed at a time when the path to the current vertice is…
Steinbitglis
  • 2,482
  • 2
  • 27
  • 40
12
votes
3 answers

Is a node in a tree considered its own ancestor?

I'm wondering what the consensus is on the definition of "ancestor" in a computer science context. I only ask because in Introduction to Algorithms, Second Edition, p. 259 there is a description of the algorithm Tree-Successor(x) that seems odd. In…
kostmo
  • 6,222
  • 4
  • 40
  • 51
10
votes
3 answers

maximum sum of a subset of size K with sum less than M

Given: array of integers value K,M Question: Find the maximum sum which we can obtain from all K element subsets of given array such that sum is less than value M? is there a non dynamic programming solution available to this problem? or if it is…
Shivendra
  • 1,542
  • 2
  • 22
  • 35
7
votes
1 answer

Printing out nodes in a disjoint-set data structure in linear time

I'm trying to do this exercise in Introduction to Algorithms by Cormen et al that has to do with the Disjoin Set data structure: Suppose that we wish to add the operation PRINT-SET(x), which is given a node x and prints all the members of x's…
user1596241
6
votes
3 answers

Deleting a random element from a heap

I read a few articles which said that, in a heap, only the root element can be deleted. However, why can't we delete elements, using the below approach? Find the index of the key element you want to delete Swap this element with the last element,…
saltandwater
  • 791
  • 2
  • 9
  • 25
6
votes
2 answers

Does this algorithm produce uniformly-random permuations?

I am studying CLRS and found a problem on shuffling algorithm. Does this produce a uniformly random permutations? 1 PERMUTE-WITH-ALL-IDENTITY(A) 2 n = A.length 3 for i = 1 to n 4 swap A[i] with A[RANDOM(1,n)] 5 swap A[i] with…
Bek Abdik
  • 99
  • 4
5
votes
3 answers

quicksort and insertion sort hybrid expected running time

I am self learning CLRS 3rd edition and here is one of the tougher questions that I have encountered along with its answer as a service to all. 7.4-5 We can improve the running time of quicksort in practice by taking advantage of the fast running…
Avi Cohen
  • 3,102
  • 2
  • 25
  • 26
5
votes
3 answers

Give an asymptotic upper bound on the height of an n-node binary search tree in which the average depth of a node is Θ(lg n)

Recently, I'm trying to solve all the exercises in CLRS. but there are some of them i can't figure out. Here is one of them, from CLRS exercise 12.4-2: Describe a binary search tree on n nodes such that the average depth of a node in the tree is…
meteorgan
  • 246
  • 3
  • 9
1
2 3
…
11 12