I came across this passage on page 47 of Introduction to Algorithms by Cormen et al.: The number of anonymous functions in an expression is understood to be equal to the number of times the asym...

Problem: Show that RANDOMIZED-SELECT never makes a recursive call to a 0-length array. Hint: Don't assume that the input array is empty, i.e., p>r. Rather, show that if an empty (sub-)array is e...

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, Ma...

I'm reading "Introduction to Algorithm" by CLRS. In chapter 2, the authors mention "loop invariants". What is a loop invariant?

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 ...

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...

I understand that the algorithm uses 8 multiplications and 4 additions with time-complexity: The multiplication is done on every n/2 * n/2 matrices. I have few questions on this : Does every n...

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(...

Not sure where I am going wrong with my implementation of merge sort in python. import sys sequence = [6, 5, 4, 3, 2, 1] def merge_sort(A, first, last): if first < last: middle = (fir...

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[...

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 b...

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 ...

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 ...

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 programm...

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, ...

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 ...

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 o...