The tag has no wiki summary.

learn more… | top users | synonyms

2
votes
0answers
25 views

Can we sort 6 numbers with at most 9 comparison?

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.
7
votes
1answer
51 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
41 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
39 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. ...
2
votes
1answer
51 views

Why is the sentence true?

I am looking at the algorithm of the insertion sort: ...
2
votes
1answer
32 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
50 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
54 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?
2
votes
2answers
55 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
42 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
17 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
378 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
25 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
52 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
26 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
43 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
33 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
92 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
45 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
194 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
58 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
127 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
60 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
63 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
132 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
288 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
51 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
25 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 ...
0
votes
0answers
48 views

Calculating the Nth linear extension of a partially ordered set

Is it possible to convert an index into a predetermined sequence of all the linear extensions of a poset, using either graycode or lexicographic orderings, without enumerating the whole set? ...
1
vote
2answers
92 views

Probability of a sorted sequence

Now I tried tackling this question from different sizes and perspectives (and already asked a couple of questions here and there), but perhaps only now can I formulate it well and ask you (since I ...
1
vote
1answer
40 views

Array sort input

Suppose that there is an algorithm which sort a sequence of $n$ elements $$a_1, a_2, ..., a_n$$ Each of the $a_i$ is chosen with probability $1/k$ from a set of $k$ distinct integer numbers. Is it ...
1
vote
1answer
233 views

Sorting Numbers into Groups

I have a list of numbers N1,N2,N3………… The list must be grouped into groups of 3 G1,G2,G3….. The sum of Each Group must be >= X, The sum of Each Group must be <= Y I understand that there may be ...
0
votes
1answer
74 views

Formula for sorting a list of two values

I have one problem during building my online service and need your help: I have a list of workers who are working on some task. They can be rewarded for their results or not. Of course they try to ...
0
votes
0answers
398 views

Packing rectangles in a grid

I have a problem that, discovered today, may be called "rectangle packing". I found extremely interesting references to papers in this question. But the rectangles I want to pack have dimensions that ...
0
votes
0answers
107 views

Worst case lower bound for comparison sort

It is known that in the worst case comparison sort takes $\Omega(nlgn)$ of time for n elements. Let's say I'm given $n$ elements as input to sort. Each input sequence of $n$ elements has $n/k$ ...
0
votes
1answer
43 views

how to sort a matrix in matlab

I have matrix like= 1 10 2 0 1 5 9 7 50 5 7 13 87 3 10 9 54 90 60 2 25 16 0 1 0 25 3 but after sorting the matrix will look like 0 1 1 2 5 7 9 10 50 3 5 7 9 10 13 54 87 ...
1
vote
1answer
2k views

Compute number of comparisons in quicksort pivoting on median or third

With a few friends we read the Algorithm Design Manual from Skiena. One of his (chapter 4) exercises asks for the number of comparisons that the quicksort algorithm does (comparing an element to the ...
1
vote
2answers
79 views

Could graph theory aid in the understanding of comparison sorting algorithms?

I am interested in computing the exact number of comparisons that are needed to sort a list. See this wikipedia article. Up to $n=15$, we know how many comparisons between elements one must make to ...
1
vote
1answer
185 views

Is there an optimized version of rectangle packing algorithm?

I have a rectangle with 200 width and 100 height. I have a mix pool of 50 rectangles and boxes. The rectangles comes in shapes like 20x40, and 40x20. The boxes will come in shapes of 20x20 and 40x40. ...
0
votes
0answers
293 views

What is the algorithm to sort 5 elements in 7 binary comparisons?

I'm tasked with finding the algo that sorts 5 elements in 7 binary comparisons. (The 7 is derived from ceilingFunction(log 5!), which our text states is the minimum number of comparisons required for ...
0
votes
1answer
39 views

Creating bounds of a shape

I have a list of coordinates, I need to find the bounds of the points as in a shape where all the points fit into, this shape can be any type of 2D shape (I only have (x, y) no z), as in lets say I ...
1
vote
0answers
42 views

Sorting Vectors based on their correlation

This problem [question]: Sort vectors according to their distance between them is about sorting vectors based on the distance between them. What about sorting vectors based on the correlation ...
2
votes
1answer
169 views

Sort vectors according to their distance between them

I have a collection of vectors, let`s say $n$ vectors. I am trying to find an easy way to SORT these vectors in that way that after sorting of vectors $(V_1,V_2,...,V_n)$ the first vector $V_1$ and ...
0
votes
1answer
320 views

How can I calculate the exact expected value of merge sort comparison (not O(n))?

First, the question stated that I have one unsorted list and then I have to split it out into two lists by fair coin flips. (Ex. Head goes A-list, tail goes B-list) Second, I'm trying to solve the ...
1
vote
1answer
108 views

Worded problems. [closed]

There are 9 chocolates in a selection box: 3 white, 3 milk & 3 dark chocolates. There are 3 soft centres, 3 truffles & 3 pralines. Each chocolate is different. Using the clues below, arrange ...
2
votes
1answer
302 views

Lower bound for matrix sorting?

Consider the problem of sorting a $n$ by $n$ matrix i.e. the rows and columns are in ascending order. I want to find the lower and upper bound of this problem. I found that it is $O(n^2logn)$ by just ...
1
vote
1answer
137 views

How to convert a sequence of numbers in the formula?

I'm trying to understand different sorting algorithms and their BigO notation. Suppose, I'm using insertion sort and I have the worst case: 6 | 5 | 4 | 3 | 2 | 1 ...
1
vote
2answers
78 views

How to find on what ranges one sorting algorithm is better than other?

I'm reading the book "Introduction to algorithms" and want to solve one task from it. But don't know the best way how to find solution. The task is: We have 2 sorting algorithms. Сomplexity of first ...
2
votes
3answers
187 views

Why is antisymmetry necessary for comparison sort?

If you want to sort Objects in a list $C$ in Java, you use Collections.sort(myList) do it. This will apply the mergesort algorithm to any List of Objects. You only have to make sure that the ...