Questions tagged [comparison]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
0 answers
93 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, ...
user avatar
  • 99
0 votes
0 answers
17 views

Algorithm to compare two live changing sets

I have two databases that are updated from asynchronous events, those updates should perform the same changes on both. both database have different structures a common id exists between "...
user avatar
1 vote
1 answer
52 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 ...
user avatar
0 votes
2 answers
33 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 ...
user avatar
1 vote
1 answer
48 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 ...
user avatar
  • 283
1 vote
3 answers
138 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 ...
user avatar
  • 283
2 votes
1 answer
20 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 ...
user avatar
0 votes
1 answer
24 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 -...
user avatar
0 votes
1 answer
37 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.
user avatar
  • 171
1 vote
0 answers
28 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?
user avatar
  • 11
1 vote
2 answers
378 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 ...
user avatar
3 votes
3 answers
80 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. ...
user avatar
  • 389
0 votes
0 answers
60 views

Counting the number of comparisons in red black tree

I have an array with $N$ elements and I run an algorithm that find how many distinct elements are in the array by using a red black tree as follows: for each element if element not in tree insert ...
user avatar
1 vote
1 answer
278 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 ...
user avatar
  • 11
1 vote
0 answers
54 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 ...
user avatar
0 votes
1 answer
395 views

Algorithm to compare two data sets

I have two data sets of a particular structure: ...
user avatar
2 votes
2 answers
86 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: ...
user avatar
1 vote
1 answer
77 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 ...
user avatar
0 votes
1 answer
33 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 ...
user avatar
  • 3
19 votes
7 answers
4k 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 ...
user avatar
3 votes
3 answers
259 views

Sorting array of strings (with repetitions) according to a given ordering

We get two arrays: ordering = ["one", "two", "three"] and ...
user avatar
  • 131
-1 votes
1 answer
408 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 ...
user avatar
3 votes
1 answer
837 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?
user avatar
0 votes
0 answers
33 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 ...
user avatar
2 votes
0 answers
94 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 ...
user avatar
  • 21
1 vote
0 answers
32 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 ...
user avatar
  • 159
1 vote
1 answer
1k 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 ...
user avatar
3 votes
1 answer
132 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. ...
user avatar
  • 4,361
3 votes
1 answer
39 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 ...
user avatar
  • 33
4 votes
1 answer
166 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 ...
user avatar
1 vote
1 answer
89 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 ...
user avatar
  • 241
1 vote
1 answer
701 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 ...
user avatar
  • 65
3 votes
1 answer
372 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 ...
user avatar
2 votes
1 answer
97 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 ...
user avatar
  • 208
0 votes
1 answer
2k 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, ...
user avatar
  • 125
3 votes
2 answers
91 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 ...
user avatar
  • 293
1 vote
0 answers
46 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 ...
user avatar
20 votes
12 answers
12k 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 ...
user avatar
  • 311
1 vote
2 answers
118 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: ...
user avatar
2 votes
2 answers
82 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 ...
user avatar
0 votes
2 answers
805 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-...
user avatar
  • 235
1 vote
3 answers
839 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 ...
user avatar
3 votes
0 answers
937 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 $...
user avatar
2 votes
2 answers
2k views

Proving at least $n-1$ comparisons are needed to test if an array is sorted

so I need to prove the following: Prove that $n-1$ comparisons are sometimes necessary to test whether an array with $n$ distinct elements is sorted in increasing order, for any $n \geq 1$. The ...
user avatar
  • 21
1 vote
1 answer
383 views

Identify similar functions

I was wondering if there is any technique in order to recognize similar functions behaviour. In particular, suppose that I implement two functions $f$ and $g$ in a certain programming language $P$ and ...
user avatar
  • 111
4 votes
1 answer
746 views

Median-of-medians in O(log n) memory

Is there a way to use median-of-medians to find a median in, simultaneously, ​ ​O(log n) ​ ​memory and O(n) comparisons? The user orlp on this site seems to claim that there is. Getting ​ ​O(log n) ...
user avatar
4 votes
2 answers
362 views

Is there a metric for the similarity of two image filters?

Definitions An image filter is a matrix $m \in \mathbb{R}^{k_1 \times k_2 \times k_3}$ which gets applied to an image $I \in \mathbb{R}^{l_1 \times l_2 \times l_3}$ as a discrete convolution $$I'(...
user avatar
  • 2,280
0 votes
1 answer
302 views

Comparing 2 video files [closed]

I have a bunch of wmv files (~300), named the following way: video1.wmv -> videox.wmv. Some of these video files, are exact ...
user avatar
0 votes
2 answers
196 views

Sorting algorithm which sorts half the possible inputs in linear time

Prove that there isn't any comparison sort algorithm which for an input of size $n$ can sort at least half of the permutations of the input in linear time. (For the other half the algorithm can ...
user avatar
1 vote
1 answer
421 views

How to compare two objects for percentage of equivalence

I'm trying to create a nodeJS application. It allows users to rate a bunch of songs and it stores them in their user profiles. I use this information to compare them to other users, and try to find ...
user avatar