# Tag Info

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 ...
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 ...
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 ...

### 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 ...
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 ...

### 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: ...
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. ...

### 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 ...

### 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 ...

### 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 ...

### 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 ...
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 ...
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 ...
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

### 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 ...
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 ...
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 ...

### Why say that breadth-first search runs in time $O(|V|+|E|)$?

BFS is usually described something like the following (from Wikipedia). ...

### 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. ...

### 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 ...

### 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 ...

### 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. ...
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 ...
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 ...
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 ...
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,\cdots, A[m-1]$. The first $n$ numbers of $A$ are non-...

### 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 ...
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 ...