31
votes
Accepted
One element that differs in two arrays. How to find it efficiently?
I see four main ways to solve this problem, with different running times:
$O(n^2)$ solution: this would be the solution that you propose. Note that, since the arrays are unsorted, deletion takes ...
- 3,634
23
votes
Accepted
Can this algorithm still be considered a Binary Search algorithm?
I would not call this a binary search.
It is clearly similar to binary search and it's natural to see it as a refinement of binary search. However it has significantly different algorithm complexity ...
- 595
19
votes
Accepted
How do I find my wife in a supermarket?
This is called rendezvous problem.
As the paper: Mobile Agent Rendezvous: A Survey mentioned, this problem is original proposed by Alpern: The Rendezvous Search Problem:
Two astronauts land on a ...
- 9,461
17
votes
Can this algorithm still be considered a Binary Search algorithm?
Yes, this is known as Interpolation Search. With some caveats (depending on your computational model and the distribution of the data) its expected running time is $O(\log \log n)$, better than binary ...
- 13.1k
17
votes
Accepted
"Guess the number" Problem on Turing machines
Yes, it is pointless and absurd to implement an algorithm to "guess the number" using the most common kind of Turing machine, whose head can read any cell on the tape, since, as you pointed ...
- 38.5k
16
votes
One element that differs in two arrays. How to find it efficiently?
The $\Theta(n)$ difference-of-sums solution proposed by Tobi and Mario can in fact be generalized to any other data type for which we can define a (constant-time) binary operation $\oplus$ that is:
...
- 2,090
16
votes
Accepted
Finding k'th smallest element from a given sequence only with O(k) memory O(n) time
Create a buffer of size $2k$. Read in $2k$ elements from the array. Use a linear-time selection algorithm to partition the buffer so that the $k$ smallest elements are first; this takes $O(k)$ time. ...
- 3,290
15
votes
One element that differs in two arrays. How to find it efficiently?
I'd post this as a comment on Tobi's answer, but I don't have the reputation yet.
As an alternative to calculating the sum of each list (especially if they are large lists or contain very large ...
- 411
14
votes
One element that differs in two arrays. How to find it efficiently?
Element = Sum(Array2) - Sum(Array1)
I sincerely doubt this is the most optimum algorithm. But it's another way to solve the problem, and is the simplest way to solve it. Hope it helps.
If the number ...
- 1,607
14
votes
Time Complexity of Linear Search vs Brute Force
Time complexity is expressed as a function of some parameter, which is usually the size of the input.
The combination lock is not a perfect analogy as it is not immediately clear what the input would ...
- 27.4k
13
votes
Algorithm to find diameter of a tree using BFS/DFS. Why does it work?
The intuition behind is very easy to understand. Suppose I have to find longest path that exists between any two nodes in the given tree.
After drawing some diagrams we can observe that the longest ...
- 185
12
votes
Accepted
Compression type that can be searched
Compressed self-indexes such as the FM Index allow arbitrary substring searches in near entropy-compressed space. These are essentially compressed suffix arrays or suffix trees, which have a lot of ...
- 1,264
10
votes
Accepted
$O(\frac{\log n}{\log \log n})$ algorithm for the prefix parity problem
I did a quick read over the paper you linked. Based on the ideas given in that paper, here's a simple data structure that obtains an $O(\frac{\log n}{\log\log n})$ time bound on each operation.
You ...
- 9,027
10
votes
Accepted
What's the fastest way to find the Kth smallest value in an unsorted list without sorting?
Use selection algorithm for linear time https://en.m.wikipedia.org/wiki/Selection_algorithm
- 1,086
9
votes
An efficient algorithm to find a shortest cycle including a specific vertex
You can find the shortest cycle that contains $v$ by running BFS from $v$, and stopping at the first time that $v$ is reached again (or if BFS terminated without reaching $v$).
An important property ...
- 17k
9
votes
Accepted
Why is the running time for BFS $O(b^{d+1})$?
This represents a difference between the kinds of problems the CS algorithms community usually uses BFS to solve, vs the kinds of problems the CS artificial intelligence community usually uses BFS to ...
D.W.♦
- 154k
9
votes
Accepted
How binary search works in real world scenario?
As Prof. Filmus said, it isn't necessary for Binary Search Trees (hereafter referred to as BST's) to necessarily have ints/Integers as the data within the nodes.
At least in Java, all we need is data ...
- 106
9
votes
Why say that breadth-first search runs in time $O(|V|+|E|)$?
BFS is usually described something like the following (from Wikipedia).
...
- 81.4k
8
votes
How does the NegaScout algorithm work?
NegaScout is a very simple algorithm. To understand we should first review iterative deepening negamax (minimax).
Iterative deepening is a technique to search for depth i, then i+1, then i+2, etc. ...
- 191
8
votes
Why is the running time for BFS $O(b^{d+1})$?
The bounds $O(|V|+|E|)$ and $O(b^d)$ are talking about different things. The former is appropriate when you know what $V$ and $E$ are in advance, and they're both finite. The latter is ...
- 81.4k
7
votes
Algorithm to find diameter of a tree using BFS/DFS. Why does it work?
Update 3 and corrected answer
There's an error in the linked solution set (see update 2 below), but it can be easily corrected with @Yuval Filmus's suggestion in the question's comment, which further ...
- 838
7
votes
How do I find the max and min value of an array in 3n/2−2 comparisons?
Imagine having a tournament made of the array elements. Group the array elements into pairs, then compare each pair. Put the larger numbers into one group and the smallers number into another group. ...
- 9,027
7
votes
Accepted
Proof of correctness of A star search algorithm
Check the original paper which talks about its correctness -
Hart, Peter E., Nils J. Nilsson, and Bertram Raphael. "A formal basis for the heuristic determination of minimum cost paths." Systems ...
- 186
7
votes
Accepted
Bidirectional Dijkstra vs Dijkstra
Absolutely yes! your arguments are correct. And, as matter of fact, it is very easy to come up with a graph where Bidirectional Dijkstra would expand more nodes than Unidirectional Dijkstra, following ...
- 3,433
7
votes
Accepted
Is uniform cost search optimal?
In my AI lecture notes (also many other AI lectures) it's written that uniform cost search is optimal (that is, uniform search always outputs the optimal path)
Kinda. While it's true that the ...
- 1,341
7
votes
Accepted
Search a sorted array that ends with zeros in O(log n) time
Here is a simple algorithm to solve the problem as in Yuval's comment.
Algorithm
Input: A positive number $w$ and array $A$ of $m$ numbers, $A[0],\cdots, A[m-1]$. The first $n$ numbers of $A$ are non-...
- 38.5k
7
votes
Time Complexity of Linear Search vs Brute Force
You are absolutely right that they are the same algorithm! At least, in this context. "Brute-force attack" is a general term referring to finding a solution to the problem at hand by trying ...
- 456
6
votes
Accepted
Is there a more efficient algorithm than backtracking/dynamic programming?
(Throughout this answer I use $\phi = \frac{1+\sqrt{5}}{2}$, which is the Golden Ratio.)
Solution:
If $s\leq n$, the attackers can win in one day.
If $s+dpw<\phi^2n$ and $s<2n$, the attackers ...
- 608
6
votes
Comparison between IDA* and Recursive best first search
Let me please start by succintly summarizing the behaviour of RBFS. For a thorough explanation of the algorithm refer to the original journal paper: Richard Korf. Linear-space best-first search. ...
- 3,433
6
votes
Is there any study or theory behind combining binary search and interpolation search?
Interleaving two algorithms to get the best of both worlds is a known technique, though it is usually stated as running them in "parallel" and returning an answer as soon as either terminates.
Though ...
- 13.1k
Only top scored, non community-wiki answers of a minimum length are eligible