# Tag Info

80

If you apply binary search, you have $$\log_2(n)+O(1)$$ many comparisons. If you apply ternary search, you have $$2 \cdot \log_3(n) + O(1)$$ many comparisons, as in each step, you need to perform 2 comparisons to cut the search space into three parts. Now if you do the math, you can observe that:  2 \cdot \log_3(n) + O(1) = 2 \cdot \frac{\log(2)}{\log(3)}...

31

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 linear time. You carry out $n$ deletions; therefore, this algorithm takes quadratic time. $O(n \: log \: n)$ solution: sort the arrays beforehand; then, perform a ...

30

DCTLib is right, but forget the math for a second. By your logic then, n-ary should be the fastest. But if you think about it, n-ary is exactly equal to a regular iteration search (just iterating through the list 1 by 1, but in reverse order). First you select the last (or next to last) item in the list and compare that value to your comparison value. Then ...

29

When doing a DFS, any node is in one of three states - before being visited, during recursively visiting its descendants, and after all its descendants have been visited (returning to its parent, i.e., wrap-up phase). The three colors correspond to each of the three states. One of the reasons for mentioning colors and time of visit and return is to ...

23

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 characteristics, Interpolation Search has expected run time of O(log(log(n)) assuming the data is uniformly distributed, however it pays for this by having O(n)...

19

A* maintains a priority queue of options that it's considering, ordered by how good they might be. It keeps searching until it finds a route to the goal that's so good that none of the other options could possibly make it better. How good an alternative might be is based on the heuristic and on actual costs found in the search so far. If the heuristic ...

19

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 spherical body that is much larger than the detection radius (within which they can see each other). The body does not have fixed orientation in space, nor ...

17

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

16

If the heuristic function is not admissible, than we can have an estimation that is bigger than the actual path cost from some node to a goal node. If this higher path cost estimation is on the least cost path (that we are searching for), the algorithm will not explore it and it may find another (not least cost) path to the goal. Look at this simple example....

16

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: total, such that for any values $a$ and $b$, $a \oplus b$ is defined and of the same type (or at least of some appropriate supertype of it, for which the ...

16

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. Now read in another $k$ items from your array into the buffer, replacing the $k$ largest items in the buffer, partition the buffer as before, and repeat. This ...

15

Think of it like this. You have a problem, with input $x$ and you know how to verify a solution if you ever found one (like the inverse of a matrix or whatever you'd like to imagine). Now, take your favourite programming language (say Python), and create every single Python program consisting of at most 10 characters! Then you run all those programs with ...

15

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 numbers that might overflow your data type when summed) you can use xor instead. Just calculate the xor-sum (i.e. x[0]^x[1]^x[2]...x[n]) of each list and then xor ...

14

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 of added elements is more than one, this won't work. My answer has the same run time complexity for best, worst, and average case, EDIT After some thinking, ...

13

A quick recap first. We are looking for a pattern $P[1\ldots m]$ in a string $S[1\ldots n]$. The Rabin-Karp algorithm does this by defining a hash function $h$. We compute $h(P)$ (that is, the hash of the pattern), and comparing it to $h(S[1\ldots m])$, $h(S[2\ldots m+1])$ and so on. If we find a matching hash, then it is a potential matching substring. The ...

12

Actually it depends on your point of view, or level of detail. The heap, or better priority queue, as abstract data structure usually supports operations like is-empty, add-element, delete-min. And usually not find-element. This is the data structure seen as a specification, fixing the set of operations and their behaviour. The implementation is unknown, it ...

12

All parts of proving the claim hinge on 2 crucial properties of trees with undirected edges: 1-connectedness (ie. between any 2 nodes in a tree there is exactly one path) any node can serve as the root of the tree. Choose an arbitrary tree node $s$. Assume $u, v \in V(G)$ are nodes with $d(u,v) = diam(G)$. Assume further that the algorithm finds a node $x$ ...

12

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 path will always occur between two leaf nodes( nodes having only one edge linked). This can also be proved by contradiction that if longest path is between two ...

12

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 literature. Basic substring search can be o(k) or o(k log n) in time for length k, depending on what data structures are chosen (different types of rank/...

10

If the elements need not be distinct, then you cannot have an $O(\log n)$ time algorithm. Consider the sorted array $[0,0, \dots, 1]$ which has been cyclic shifted $k$ (unknown) times and you need to find where the $1$ appears. This needs $\Omega(n)$ time, as you need to examine at least $n-1$ elements. However, if you assume the elements are distinct, ...

10

My two cents: exhaustive search is also known as brute force search, an approach in which you have no better strategy than to explore the entire search space, testing every possible candidate solution. Two examples were given by @Yuval Filmus. If you are really unlucky, the solution may well be the last candidate explored, or one of the last ones. Therefore, ...

10

Warmup: random bitvectors As a warm-up, we can start with the case where each bitvector is chosen iid uniformly at random. Then it turns out that the problem can be solved in $O(n^{1.6} \min(k, \lg n))$ time (more precisely, the $1.6$ can be replaced with $\lg 3$). We'll consider the following two-set variant of the problem: Given sets $S,T \subseteq \{0,... 10 For your problem with the array: No, there is no better algorithm. That's the best you can do. Any deterministic algorithm will in the worst case have to look at every array element (technically: at least$n-1$of the$n$elements). This can be proven by an adversarial algorithm: consider any algorithm, and imagine it has looked at$n-2$elements and hasn'... 10 Use selection algorithm for linear time https://en.m.wikipedia.org/wiki/Selection_algorithm 9 Divide your original array into$n/\log n$blocks of length$\log n$. Put each processor in charge of each block, and find the maximum using the usual algorithm in time$\log n$. We now need to compute the maximum of an array of length$n/\log n$. Pair up the elements and compute the pairwise maxima to reduce the size of the array by a half. Repeat it$\log ...

9

You could possibly save some space using a "meet in the middle" approach. Make a list of all nodes at distance at most 3 from A, and another list of all nodes at distance at most 3 from B. If the lists intersect, then A and B are at distance at most 6. In the fact, it is enough to construct one of the lists and then generate the other list, testing whether ...

9

Create a temporary source string by concatenating itself together until the length of the source string is at least twice the length of the search string. The source string must be concatenated at least once. Then perform a simple (non-circular) search on that temporary string.

9

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 mentioned in your question that you can use balanced, augmented trees to speed this up. In particular, if you have a binary tree and augment each node with the ...

9

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 solve. The algorithms community typically is focused on the case where we have a finite graph, and where we're going to run some algorithm that probably visits ...

9

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 that is either Comparable to itself or some superclass of itself (implementing Comparable) or can be compared with an outside tool (using a Comparator). But I ...

Only top voted, non community-wiki answers of a minimum length are eligible