Questions tagged [comparison]
The comparison tag has no usage guidance.
70 questions
1
vote
1
answer
82
views
At least 3n/2-2 comparisons needed to find minimum and maximum of an unsorted array
Show that $\left\lfloor \frac{3n}2\right\rfloor-2$ comparisons are necessary to find the minimum and maximum in an unsorted array of $n$ elements
So we keep a tag $M$ for the possible maximum and a ...
- 145
0
votes
0
answers
30
views
What could cause a Windows 11 machine to have so much more elapsed time relative to a Windows 10 machine?
I have a Windows 10 desktop (6 years old - Dell Optiplex) and a new Windows 11 laptop (maybe last years model - Lenovo Thinkpad P16 Gen2).
I am running scripts in R to compare their compute times. The ...
- 111
3
votes
2
answers
1k
views
Find 1s in almost all 0 array using comparisons only
So, we are given a 100 long array, with 97 0s and 3 1s of which we do not know the locations. We must find them using only a compare function, which I managed to write (in Python):
...
- 61
0
votes
0
answers
50
views
Ideal less-than-or-equal circuit for multiple inputs?
I'm interested in what the best way is to design a circuit that takes multiple values as input, and then outputs which value is the lowest. If multiple values are the lowest, it outputs "true&...
- 233
4
votes
0
answers
138
views
Comparison-based computation: percentage of current software development?
Vol. III of The Art of Computer Programming, chapter 5 (Sorting, intro) mentions:
Computer manufacturers of the 1960s estimated that more than 25
percent of the running time on their computers was ...
- 622
1
vote
3
answers
336
views
How do you write a logic function to determine if one 2s complement binary number is less than another?
Working on logic design in class, and I'm trying to figure out how to write a specific logic function [and by write, I mean something along the lines of (x NOR y) OR (a NOR b), for example]
It asks to ...
- 11
0
votes
0
answers
34
views
Where can I find a list of logics with their corresponding calculus and computation phenomena?
I was watching some lectures by Prof. Pfenning on Proof Theory. Between 5:30 and 15:00, he gave a list for some different kinds of judgments along with their calculus and computation phenomena that ...
- 109
0
votes
2
answers
41
views
Compare list of parameters with each other and sort them from most to least selected
I want to sort the list of parameters (p1, p2, p3, p4, ..., pn) according to their importance.
All parameters have to be compared with each other at best once, but not less than once.
The person will ...
0
votes
3
answers
473
views
Can we create a decision tree for any comparison sorting algorithm even if it is very complicated?
I am reading an algorithm book.
Any comparison sort must make $\Omega(n\log(n))$ comparisons in the worst case to sort $n$ elements.
Can we create a decision tree for any comparison sorting algorithm ...
- 113
1
vote
0
answers
133
views
Is there an efficient algorithm for finding a minimal common subset of pairwise distinct bits in a set of bit strings?
I am working on an efficient mapping function represented as a directed graph. In essence, it is a sort of radix trie. A path must be formed from a bit string [string hereon] efficiently. To do this, ...
- 97
1
vote
1
answer
60
views
Efficient comparison, using only sum, product, difference, and conditional jump if zero
I was wondering how small we could make the instruction set of a typical machine that supports a single datatype: arbitrary integers. If you need a heap, you declare an integer variable $h$ where you ...
- 548
0
votes
2
answers
149
views
Can you compare large numbers this way?
If you created two very large numbers represented by binary data (perhaps using sha512 with random input for each hash) could you determine what binary block is numerically larger by iterating over ...
- 103
1
vote
1
answer
79
views
Examples of comparison-based algorithms that are not a sort or a search over lists
Can you share examples of comparison-based algorithms used in practice that are not a sort or a search over lists? Heapify is an example of a comparison-based algorithm that is neither a sort nor a ...
- 622
1
vote
3
answers
919
views
Best-case time: comparison-based sorting on a list of size n must make n-1 comparisons (reference to proof)
I am looking for a reference to a proof that for every list of size $n$ comparison-based sorting cannot make less than $n-1$ comparisons. Do you have a reference of a book that covers it (with page ...
- 622
2
votes
1
answer
30
views
Comparing various ways to move a game actor having time-dependent velocity
Assume I have a game actor (name it MyActor for further references) to be moved up and down according to $z=f(t)=A\sin \omega t$ (or any non constant velocity). The ...
- 123
0
votes
1
answer
220
views
Algorithm best compare similarities between two data sets in percentage
I'm trying to create an algorithm that finds the percentage of similarity between two subjects with sets of survey questions.
Example:
Q1: Do you prefer physically demanding tasks?
A1: Nope Maybe Yes -...
- 101
-3
votes
3
answers
153
views
Average number of comparison for 3 items
What is the average number of comparisons performed when sorting 3 items?
The question is based on the above picture.
- 165
1
vote
0
answers
41
views
n-bit ALU usually do comparison operation on maximum n/2-bit or n-bit?
For n-bit ALU is equal-to operation and similar comparisons generally limited to n/2-bit words, or n-bit?
- 11
1
vote
2
answers
562
views
Sorting an array with x sorted subarrays
I have been given two True/False questions regarding sorting an array. The questions are as following -
Question A
Given an array A with 3n keys that contains three equal parts
A[1,n], A[n+1,2n] and ...
- 231
4
votes
3
answers
247
views
What is a sorting algorithm that is robust to a faulty comparison?
I want to sort a list of n items with a comparison sort. However, one of the comparisons made by the algorithm will be flipped from what it's supposed to be. ...
- 542
2
votes
2
answers
1k
views
What is the best way to compare two images for similarity if the brightness of the second image was changed?
I calculate similarity percent between two images. Another image is the same with changed brightness. I've already tried comparing by pixel (euclidean distance for grayscale and 0/1 values), comparing ...
- 21
1
vote
0
answers
129
views
QuickSort when the range of data is known
In QuickSort Algorithm, the pivot is chosen as the first element or a randomised element. However, if the range of data to be sorted is known, For example, from 1 to 100, and they are mostly equally ...
0
votes
1
answer
2k
views
2
votes
2
answers
123
views
Constraint satisfaction problem: solve system, then evaluate whether many additional constraints are satisfied one at a time
I have a system that consists of binary inequality constraints between variables, plus some indicator variables that can assume only two values:
...
- 23
1
vote
1
answer
97
views
Finding maximum of $n$ many $m$-bit integers
Suppose you want to determine the largest number in an $n$-element set $X = (x_1, x_2, \dots , x_{n})$, where each element $x_i$ is an integer between $1$ and $2^m − 1$. Describe an algorithm that ...
- 123
0
votes
1
answer
47
views
Longest palindrome substring in logarithmic runtime complexity
In a palindrome of size N, the amount of candidates for the longest palindrome is N^2. Therefore, the information theoretic lower bound (IBT) should be lg(N^2), which is equivalent to a runtime ...
- 3
19
votes
7
answers
6k
views
Why do we use the number of compares to measure the time complexity when compare is quite cheap?
I think one reason a compare is regarded as quite costly is due to the historical research as remarked by Knuth, that it came from tennis match trying to find the second or third best tennis player ...
- 413
4
votes
3
answers
379
views
Sorting array of strings (with repetitions) according to a given ordering
We get two arrays:
ordering = ["one", "two", "three"]
and
...
- 143
-1
votes
1
answer
591
views
Recurrence Relation of Ternary search and the number of comparisons with binary search
i was reading the binary search and ternary search algorithms. But i had a doubt with recurrence relation of ternary search as somewhere it is T(n/3)+c and T(2*n/3)+c. I want to know which one is ...
3
votes
1
answer
1k
views
Minimum number of comparision to find the third largest element in an array of distinct integers?
For the second largest element, I know that the formula is $n+ \lceil\log n \rceil -2 $
Is there any formula for the third largest element? and if so, what is the derivation?
user106464
0
votes
0
answers
34
views
Algorithm for comparing object dates and types
I'm looking for a good / efficient algorithm to compare classes of driver licences (or any type of similar objects) and their dates, so that they do not overlap and come in certain order.
eg. We have ...
- 101
2
votes
1
answer
184
views
Goemans' Extended Formulation of the Permutahedron And Comparator Networks that are not Sorting Networks
I am interested in using Michel Goemans' extended formulation first developed for the permutahedron to study comparator networks that are not sorting networks. In his paper "Smallest Compact ...
- 21
1
vote
0
answers
34
views
How to justify using available code (in different language) for comparing algorithms [closed]
I have proposed an algorithm for a scheduling problem in a submitting paper. In the revision, the reviewer asked us to compare with another algorithm in the literature. Our algorithm is in MATLAB, and ...
- 159
1
vote
1
answer
2k
views
Turing machine - compare two words
I have a simple turing machine with single tape.
I need to compare two words <w1>$<w2>$ and write output.
Language is all letters and numbers.
I did ...
- 13
3
votes
1
answer
232
views
Why is finding minimum number of comparisons to sort $n$ elements so difficult?
In The Art of Computer Programming 2nd Ed, Vol 3, Section 5.3.1 then discuss a function $S(n)$ which is define as:
$S(n)$ : The minimum number of comparisons that suffice to sort $n$ elements.
...
- 4,523
3
votes
1
answer
71
views
Finding maximum takes at least $\lceil n/2 \rceil$ comparisons
We are given an array $A$ with $n$ elements, $n \in \mathbb{N}$ and all elements are in the set $\{1,2,3, \cdots, n \}$.
I want to prove that finding the maximum in $A$ (that is, outputting the index ...
- 33
4
votes
1
answer
267
views
Are comparison sort algos appropriate for SUBJECTIVE sorting?
I've been tasked with creating an online feature that ranks 50 fantasy characters from a variety of domains based on combat acumen and polls users one which one is the most powerful based on their ...
- 143
1
vote
1
answer
139
views
An algorithm to drop low-priority items from a heap-based priority queue
I am looking for an efficient algorithm to drop from a complete binary min heap all items whose weight exceeds a given value. (Or, equivalently, to drop from a priority queue realised by such a heap ...
- 251
1
vote
1
answer
948
views
Sorting lower bounds for almost sorted array
Can't find a good way to tackle the problem. Would appreciate any help.
$A$ is an $n$ items array from an ordered set, in which every item is at most
$\log n $ indices away from its position in the ...
- 175
2
votes
1
answer
486
views
d-ary heap implementation vs Fibonacci heap implementation Dijkstra performance comparions
Let's say that Dijkstra’s algorithm with the priority queue using a d-ary heap. if adjusting d, we can try to achieve the best runtimes for the algorithm with d being $\sim |E|/|V|$.
Then for a ...
- 81
2
votes
1
answer
107
views
Optimize sorting matrix entries by row and column
I am writing a routine to store an $M$-by-$N$ sparse matrix in a balanced binary tree. The insertion routine calls a comparison function to determine where a new matrix entry $(i,j)$ should be ...
- 208
0
votes
1
answer
4k
views
How to compare an element with other elements within an array efficiently for a condition
I need to compare each index with one another and associated array value as well.
For example,
...
- 125
3
votes
2
answers
225
views
sort n numbers in the range [0,1] without multiplying or dividing
Given an array with n real numbers, each in the range [0,1], I need to sort them. Moreover, the only operations that are allowed are comparisons or copying.
It means I cannot multiply or divide the ...
- 325
1
vote
0
answers
55
views
Merge unstructured with structured data
We have a database with well-formated and structured data. From time to time we get Excel - files from our clients. This Excel Files have to be imported to the database. It it very important that we ...
- 111
21
votes
12
answers
14k
views
Data structure or algorithm for quickly finding differences between strings
I have an array of 100,000 strings, all of length $k$. I want to compare each string to every other string to see if any two strings differ by 1 character. Right now, as I add each string to the ...
- 321
1
vote
2
answers
133
views
What is the name for the comparison used in C's memcmp?
The C memcmp function (and strcmp) does a comparison similar to the function below for comparing integers:
...
- 113
2
votes
2
answers
113
views
Compare two atan2
I tried to implement points location algorithm using Fortune's algorithm to get Voronoi diagram and another sweepline algorithm to locate many points in $O(n\cdot\log(n))$. If there are multiple ...
- 165
0
votes
2
answers
983
views
Turing Machine for $\{w\# w ' |$ where $w < w'$ lexicographically, and $w,w'\in \{0,1\}^* \}$
I am blocked with this question for a long time.
$L = \{w\# w ' |$ where $w < w'$ lexicographically, and $w,w'\in \{0,1\}^* \}$
I am trying to find
A Deterministic Turing Machine for L.
A Non-...
- 255
1
vote
3
answers
1k
views
finding best n players in minimum number of comparisons
I am trying to find out if there is any generic way to find out first to nth best player in a tournament if n is less than the square root of input size i.e. 5 best players in the sample size of 25 ...
- 213
3
votes
0
answers
1k
views
How to determine the fewest number of comparisons for Heapsort?
I'm currently doing an exercise that asks to prove that Standard-Heapsort requires at fewest $\frac{1}{8} n \log(n) - O(n)$ comparisons, in its best case.
In its average case, Heapsort only requires $...
- 31