All Questions
21
questions
1
vote
1
answer
78
views
Is there an intuitive reason natural logarithms arise in the analysis of randomized quicksort?
The randomized quicksort algorithm works as follows:
If the list to sort is empty or has length one, it’s sorted.
Otherwise, pick a uniformly random element of the list called the pivot element. ...
- 10.5k
0
votes
0
answers
67
views
How to prove if a list is sorted if any two consecutive elements are sorted?
To check if a list is sorted, a typical approach is to check every element and its next element, and see if they are sorted. Intuitively, I understand it is correct. But is there a more mathematical ...
- 101
0
votes
1
answer
133
views
Minimize the absolute difference of the sum of two dijoint sets in which terms are in the powers of $p$.
Given $n(n>=1)$ integers $k_1,k_2 \cdots k_n(k_i>=0)$, and an integer
$p>=1$, Johny picks $p^{k_i}$ from $i-th$ category for each category , and he wants to
divide them into two disjoint sets,...
- 888
1
vote
2
answers
7k
views
How many comparisons does the insertion sort use to sort the lists in question
I have two lists to sort using insertion sort:
How many comparisons does the insertion sort use to sort the list
$n, n − 1, . . . , 2, 1$?
How many comparisons does the insertion sort use to sort ...
- 1,189
1
vote
2
answers
776
views
Minimum Comparisons needed for worst case sorting of array consisting of only 1,-1,0
Let $A$ be an array of $n$ elements consisting of only $-1,1,0$. What is the least number of comparisons that must be made in worst case to sort the array?
At first I was thinking of the answer is 0 ...
- 889
3
votes
1
answer
184
views
Generate a new total ordered set from an existing ordered set and a partial ordering
I have a totally ordered set S and I'd like to re-order it based on a partial ordering P.
If set S looks like [A, B, C, D, E] where A < B, B < C, and so on. And set P looks like [A, E, B]. Then ...
- 135
1
vote
1
answer
145
views
Sorting algorithms
How could we show that the algorithm of
Mergesort is stable,
Quicksort is not stable but it can be implemented as stable,
Heapsort is not stable.
I have show that the algorithm of Insertion Sort ...
- 14k
1
vote
1
answer
62
views
Is the invariant correct?
I want to show that Insetion Sort is stable... Do I have to do that using an invariant??
Is the invariant the following??
At the beginning of each iteration of the for loop, if $A[a]=A[b], a<b \...
- 14k
0
votes
2
answers
3k
views
Dividing the interval in subintervals of equal length
I am asked to describe the operation of the processure BUCKET SORT at the array $$A=\langle 0.75, 0.13, 0.16, 0.64, 0.39, 0.20, 0.89, 0.53, 0.71, 0.42, 0.19 \rangle $$
dividing the interval $[0, 1)$ ...
- 14k
0
votes
1
answer
79
views
Quicksort-How did we get the relation?
At the proof of the theorem that the expected time of Quicksort is $O(n \log n)$, there is the following sentence:
We suppose that the partitions are equally likely, so the possibility that the sizes ...
- 14k
3
votes
1
answer
856
views
Expected time of Quicksort
I am reading the proof of the theorem:
The Algorithm Quicksort sorts a sequence of $n$ elements in $O(n \log n)$ expected time.
The proof is this:
For simplicity in the timing analysis assume ...
user175343
1
vote
2
answers
95
views
The expected time to sort $n$ elements is bounded below
Prove that the expected time to sort $n$ elements is bounded below by $cn \log n$ for some constant $c$.
Could you give me some hints how I could do that?
- 14k
3
votes
2
answers
1k
views
Find both the largest and second largest elements from a set
Consider finding both the largest and second largest elements from a set of $n$ elements by means of comparisons.
Prove that $n+\lceil \log n \rceil -2$ comparisons are necessary and sufficient.
...
- 14k
1
vote
3
answers
2k
views
How many comparisons are required?
Let $S$ be a set of $n$ integers. Assume you can perform only addition of elements of $S$ and comparisons between sums. Under these conditions how many comparisons are required to find the maximum ...
- 14k
2
votes
2
answers
8k
views
The decision tree has height at least $\log n!$
The proof of the theorem
Any decision tree that sorts $n$ distinct elements has height at least $\log n!$
is the following:
Since the result of sorting $n$ elements can be any one of the $n!$ ...
- 14k