For questions about dividing groups of objects based on their properties.

learn more… | top users | synonyms

1
vote
1answer
41 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 ...
1
vote
2answers
39 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?
0
votes
0answers
7 views

Order subsets amongst em self and in global list?

This is the scenario, I have a list of 200 names I want to order to the users preferences. I present this names to the user four at the time and the user ranks em 1-4 click next and gets to see a new ...
0
votes
2answers
31 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. ...
1
vote
3answers
56 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 ...
1
vote
1answer
43 views

A decision tree has an expected depth of at least $\log n!$

I am looking at the proof of the following theorem and I have some questions. The theorem is the following: On the assumption that all permutations of a sequence of $n$ elements are equally ...
0
votes
2answers
52 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!$ ...
3
votes
2answers
120 views

Application of Mergesort

We have $8$ players and we want to sort them in $24$ hours. There is one stadium. Each game lasts one hour. In how many hours can we sort them?? I thought that we could it as followed: ...
0
votes
1answer
31 views

Merge two sets, list and tree

We are given two sets $S_1$ and $S_2$. We consider that $S_1$ is implemented, using a sorted list, and $S_2$ is implemented, using a pre-order sorted tree. I have to write a pseudocode, that ...
1
vote
0answers
20 views

Help with proof about merge two heaps to one heap…

We have two heaps: $H_1,H_2$ that have $n_1,n_2$ elements ($H_1$ have $n_1$ elements and $H_2$ have $n_2$ elements). We know that the smallest element at $H_1$ is bigger the root (the biggest element) ...
0
votes
0answers
15 views

number of call randomized partition function in quick sort

If the number of calling randomized partition function in the array of n elements name $C(n)$ I know that $\frac{n}{2} \leqslant C(n) \leqslant n - 1$ and the question is show that for every number ...
0
votes
1answer
38 views

Notation for rank of weakly ordered elements

I'm looking for a mathematical notation for the following algorithm where $D$ is a diagonal square matrix and $w$ a scalar value. Sort $D$ by the diagonal entries ascending for the first entry ...
1
vote
0answers
16 views

Minimal and maximal elements of a set consisting of sums of random variables

Consider a set of $n$ correlated random variables, $A =\{X_1, \ldots, X_n\}$. Suppose that I have another set, $B$, of all possible combinations of size $k$ of the random variables. Now, if for each ...
0
votes
1answer
21 views

Recursive sort that doesn't require list splicing?

I was just wondering if there was some form of sort algorithm that doesn't require any form of splicing of the original list? Thanks in advance.
0
votes
0answers
13 views

Estimating how many searches will be needed to justify time spent on presorting an array.

Problem Estimate how many searches will be needed to justify time spent on presorting an array of $10^3$ elements if sorting is done by merge sort and searching is done by binary search. (You may ...
1
vote
2answers
65 views

Sort sequences of the form ABCABCABC, ABABAB, ABCDABCD, etc.

You are given a sequence of distinct elements $P$ and a positive integer $R$. Consider the sequence obtained by repeating $P$ $R$ times and concatenating together. For example, if $P = \langle A, ...
0
votes
0answers
55 views

About Bayesian formula and rating system

I'm building a scoring system with score from 0 to 5) and I would like to sort products according to the number of reviews and their scores. After some research on the Internet I have found two ...
1
vote
1answer
22 views

correcting an invalid binary heap in $\Theta (n)$

We are given a binary max (every node is larger than its children) heap with $n$ elements. We now change $\frac{n}{4}$ of the elements at random. We don't know which ones and to which value. And so, ...
2
votes
1answer
40 views

How equal are two given numbers

I have two numbers x & y for N different readings and wish to find how close they are from each other and would like to rank the reading in order of they equalness. If I were to have the ...
0
votes
0answers
30 views

# of ways to sort. Quick Sort Problem.

This is a question about the quick sort algorithm and the # of ways I can place the books on shelves. I have to place a book on n number of shelves with m number of books; m >= n >= 1. But I have to ...
2
votes
0answers
31 views

Empty List is Sorted?

Is an empty list considered to be sorted? Let's say I have a math function sort that sorts a list of numbers. ...
1
vote
0answers
38 views

Can we sort 6 numbers with at most 9 comparison? [duplicate]

i know there is an algorithm to sort 5 numbers with 7 comparison. Can we sort 6 numbers with at most 9 comparison? thanks to all.
5
votes
1answer
98 views

SQRTSORT from Vazirani's book on algorithms

I study the Algorithm book and saw the following exercise. I couldn't solve it. This is not homework, nor exam. Just reading some material on algorithms for preparing entrance exam. Any nice idea or ...
1
vote
1answer
147 views

Recurrence Relation - Merge Sort

We know the recurrence relation for normal merge sort. It is T(n) = 2T(n/2) + n. After solving it we can get T(n) = cnlogn. I ...
0
votes
0answers
63 views

sorting young's tableau better than n^3

Young's tableau takes $O(n^3)$ to sort. By sorting I mean sort numbers in existing young's tableau. http://en.wikipedia.org/wiki/Young_tableau Simply it is a matrix sorted by rows and columns. ...
0
votes
1answer
55 views

Why is the sentence true?

I am looking at the algorithm of the insertion sort: ...
0
votes
1answer
36 views

Show that the height of the heap is $\lfloor \lg n \rfloor$

I want to show that a heap with $n$ elements has the height $ \lfloor \lg n\rfloor$. That's what I have tried: The "best" case is a complete binary tree,and then it is of the form: So,the height ...
0
votes
2answers
52 views

Why is the height of a heap defined as $\lg n$?

I'm a bit confused about why the height of a heap (or a binary tree in general) is given by the floor of $\lg n$. E.g. if you have a tree with 7 nodes, you would get $h = 0$ instead of $h = 2$. Isn't ...
1
vote
1answer
67 views

Find 3rd largest number out of 7 under at most 11 comparisons

I know similar problem like "sort 5 numbers in 7 comparisons". I know no general algorithms exist. Do I just enlist all possible game trees?
0
votes
2answers
57 views

The value of loop variable at the end of a loop in the insertion sort

I am looking at the algorithm of the insertion sort: Input: $A[1 \dots n]$ ...
0
votes
0answers
59 views

An efficient algorithm to pair chess players in a team tournament

I found this question on a website. Your team is playing a chess tournament against a visiting team. Your opponents have arrived with a team of $M$ players, numbered $1,2,\dots,M$. You have $N$ ...
2
votes
0answers
27 views

Ordering binary matrices for reflection/rotation

I have a collection of $n\times n$ binary matrices and I would like to reduce it for symmetry ($D_4$ -- reflections and rotations). The naive method of testing each pair is very slow because the ...
5
votes
2answers
440 views

Is it possible to sort an array of 10 elements with 20 comparisons of two elements?

I think it's not, because there are $10!$ permutations of $10$ elements, and $10! \gt 2^{20}$. Can anyone point me how to prove it rigorously?
2
votes
0answers
28 views

Is it possible to sort products by result without calculating?

I have some numbers n in range 100 ... 999 and some other numbers m also in range 100 ... 999. Is it possible to sort all the product m*n without calculating the actual product? Sorry, my English for ...
1
vote
0answers
116 views

Pancake and increasing order

Determine the number of 5 pancake stacks that requires exactly 2 flips to put into the increasing order, i.e., 1,2,3,4,5. (Example: 3,4,2,1,5 is one of them.)
1
vote
0answers
30 views

Elementary Discrete Math Sorting Algorithms

I have a quiz tomorrow and cannot figure out a few of the examples he wishes us to complete. They seem pretty basic. Add (Input a list of numbers A1,A2.....An) Step 1: Let i =1 and S = 0 Step 2: ...
0
votes
1answer
53 views

Optimization problem for feeding the hungry

So I am trying to solve a problem. I believe it is $NP$. Assume we have $F$ cans of food of varying sizes. There are $P$ homeless people at the local shelter, where $F>P$. Each can of food, $i$ , ...
0
votes
0answers
36 views

Sorted result of a mod operation

Here is a fairly interesting but potentially unsolvable problem at stake. I hope it's in fact fairly well covered and known within modular mathematics. Let's suppose there is a segment of contiguous ...
2
votes
0answers
122 views

Finding maximum differences in an array of real numbers .

This is an algorithm design question which often appears in exams in a course that I take in the university . Suppose I have an array $A\in\mathbb{R}$ of size $n$ . I am required to find the ...
1
vote
1answer
47 views

Comparing factorials (From greatest to least)

Let's say we're asked to arrange these factorials in descending order: $1000!, \,\,700!\cdot300!,\,\,500!\cdot500!,\,\,600!\cdot300!\cdot100!$ For the first three, we could do: ...
0
votes
1answer
17 views

Question about $N$ numbers sorting

Gonna use some help on this: I have $M$ channels lining up and each channel possesses $n$ users, with $n$ taking value from $1$ to $N$. I'm interested in such a situation: the numbers of users in the ...
6
votes
2answers
201 views

Average complexity of random-pick comparison sort

Motivation. Suppose we have a number of images that we want to arrange in a linear order from the prettiest to the ugliest. At our disposal we have a trained aesthete, whom we can show two pictures ...
0
votes
1answer
75 views

How many digits are in the bijective base-k numeral for n?

For integers $n \ge 0$ and $k \ge 2$, the following are equivalent: How many digits are in the bijective base-k numeral for n? If all the words on an alphabet of size $k$ are listed in shortlex ...
0
votes
3answers
169 views

Minimum number of exchanges

Suppose we want to arrange n numbers stored in an array such that all negative value occur before the positive ones. What will be the minimum number of exchanges in the worst case ? I tried it in the ...
0
votes
1answer
63 views

Question Understanding Simple Algebra With Regards to Computational Complexity

Initial Disclaimer: I decided not to post this on Stack Overflow as my problem lies with understanding the mathematics of this problem, but does not relate to theory at all. I am studying Parallel ...
1
vote
1answer
83 views

Why elapsed time is an exponential function of the number of elements in a vector that is sorted (MATLAB)

In the following script (that performs "bubble sort" on an row vector) it seems that the time elapsed when matlab executes the sorting depends exponentially on the number of elements in the vector. ...
6
votes
1answer
137 views

Reference Request on Order Theory topics

I am looking for some references (especially a good recent book) that covers important topics involving partial orders such as: order polytopes, sorting/selection in partially ordered sets, upper and ...
1
vote
1answer
593 views

What is meaning of strict weak ordering in layman's term?

I gone through many pages using Google, but not understand exact meaning of Stick-weak Ordering term. I have this requirement while sorting strings. Thanks.
1
vote
1answer
52 views

Minimization of difference

Given two lists $\{a_1,a_2, \ldots,a_n\}$ and $\{b_1,b_2, \ldots,b_n\}$ and you can rearrange elements in each list individually. You have to rearrange element in it in such a way value of S is ...
1
vote
0answers
26 views

Redistribution Algorithm

I've one thousand buckets of different sizes. Each bucket consists of red and blue balls of different weights. I know that 60 percent of the total ball weight comes from the red balls and 40 percent ...