Questions tagged [search-algorithms]

Algorithms for finding an element in some specified data-structure (most commonly, in a tree).

Filter by
Sorted by
Tagged with
0 votes
1 answer
30 views

Is this depth search correct (DFS) Shouldn't one act according to the LIFO principle?

Shouldn't we actually continue with C after A, thought a depth search, follows the LIFO principle, isn't C the last node added in this case and shouldn't we expand C before B?
3 votes
1 answer
763 views

How to efficiently create balanced KD-Trees from a static set of points

From Wikipedia, KD-Trees: Alternative algorithms for building a balanced k-d tree presort the data prior to building the tree. They then maintain the order of the presort during tree construction ...
2 votes
1 answer
179 views

Design a data structure with constant insertion and sublinear range maximum query

Suppose we have access to a stream of ordered pairs, where the $i^{\text{th}}$ element in the stream is an ordered pair $(a_i, b_i)$, where $a_i$ is a timestamp and $b_i$ is an arbitrary real. How can ...
2 votes
1 answer
74 views

Graph labyrinth solving sequence

Starting from a vertex of an unknown, finite, strongly connected directed graph, we want to 'get out' (reach the vertex of the labyrinth called 'end'). Each vertex has two exits (edge which goes from ...
0 votes
2 answers
56 views

Correctness proof of bubble sort(bogus proof)

I am aware of bubble sort correctness proof. But what is wrong with following argument while using induction. Proof: Assume correctness of array size $1$ and $n$ (base and hypothesis). Then for ...
1 vote
1 answer
486 views

Find all polygons from a set that overlap a given polygon (convex case)

Problem: Given a set of $N$ non-overlapping convex polygons $\{S_i | 1\leq i\leq N\}$ defined by their vertex coordinates $(x,y)$ and a convex polygon $P$, also defined by its vertex coordinates, ...
1 vote
1 answer
70 views

How to find largest caterpillar in a tree

A caterpillar is a subgraph which consists of a path with at most four leaves (legs) attached to each node (but a node can also have no leaves). This is not the same as finding the longest path, ...
2 votes
1 answer
48 views

Maximum of a tritonic array

I have found out how to find the maximum of a "bitonic" array. The problem is as follows. An array is bitonic if it is comprised of an increasing or decreasing sequence of integers followed ...
0 votes
1 answer
89 views

How to cover elements with minimum amount of elements

I'm trying to create a game but I am having some difficulties in coming up with a suitable algorithm for my problem. I have elements from 1 to n and I am trying to cover all of the elements using the ...
2 votes
1 answer
259 views

Prove the relation between space complexity and time complexity of the graph search which uses "the explored set"

I was referring to the textbook Artificial Intelligence: A modern approach 3rd by Stuart Russell and Peter Norvig. what to prove about the general "graph search": (Here I assume "within ...
0 votes
1 answer
118 views

In RBFS, why should expanded nodes inherit F-value of their parent, if their f-value (g(n)+h(n)) is less than their parent's F-value

Here https://uk.wikipedia.org/wiki/RBFS and here https://www.eecs.yorku.ca/course_archive/2013-14/F/3401/slides/15b-RBFS.pdf it's said that f[s] ← max(g(s)+h(s) , f[node] ) Why is it so? I can see a ...
2 votes
1 answer
96 views

Faster selection algorithm for small order statistics

SELECT(A,p,r,i) is an algorithm that partitions $A[p:r]$ around the $i$ th order statistic ie. in the output, we have $l\in A[p:p+i-2]<A[p+i-1]< h\in A[p+i:...
4 votes
2 answers
777 views

What is the name of this search algorithm?

I was thinking about an efficient binary search for unsorted arrays with $n$ entirely unique elements, and came up with something that probably already exists. Here's how it works: At each level of ...
0 votes
3 answers
194 views

Need help with adding elements to hashtable with linear probing

Here is an example problem which I have having trouble figuring out. The red text is the answer. I get how the values are added before the hashtable is resized... that is common sense. (Insert 0 at ...
0 votes
4 answers
389 views

Find median in a sorted matrix

Suppose we are given a $n\times n$ matrix that is sorted row-wise and column-wise. We want to find the median in $\mathcal{O}(n\log{n})$. This is my approach: We know median is such element that is ...
0 votes
1 answer
62 views

Find multiple order-statistics of an array

Given array $a$ of size $n$ and array $p$ of size $m$. How we can for every $i < m$ find $p_i$-th order statistics of array $a$ in $O(m log(n) + n)$? We can find order statistics separately, but it ...
5 votes
3 answers
3k views

Uniform-cost Search Problem

Suppose that we take an initial search problem and we add $c > 0$ to the costs on all edges. Will uniform-cost search return the same answer as in the initial search problem? Definitions: Uniform-...
0 votes
0 answers
24 views

Manhattan distance always less node expansion than misplaced tiles heuristic?

I created a 8-puzzle search solver using BFS, A* with manhattan distance, and A* with misplaced tiles. I generated data that said that for a particular random board, misplaced tiles did less node ...
0 votes
1 answer
37 views

Time complexity of search algorithms?

Can we prove that classical search algorithms cannot do better than a binary search algorithm with complexity $O(log(n))$ ? If so, how do we prove it?
0 votes
2 answers
1k views

Algorithmic challenge: generate a list of random non overlapping squares [closed]

For an undisclosed reason, I need a list of $n$ squares in a two dimensions space where each square does not overlap. So the challenge is simply: given a two dimensional area $a$ (...
1 vote
2 answers
115 views

Find a subsequence with fastest time for specific distance

I have two arrays. ...
0 votes
2 answers
574 views

Can Dijkstra's algorithm outperform A star, in terms of vertices checked?

I know Dijkstra's algorithm can be seen as a specific case of A star, when the estimation heuristic used simply returns 0, so I know that A star with this specific heuristic can not check more ...
6 votes
3 answers
15k views

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), but what if the cost is negative, won't ...
5 votes
5 answers
4k views

Time Complexity of Linear Search vs Brute Force

I am currently watching the FreeCodeCamp Algorithms and Data Structures Tutorial. In the explanation for exponential time complexity, they explain that using a brute force attack on a combination lock ...
2 votes
2 answers
125 views

Any text similarity algorithms for substrings?

I need to implement simple search on Python package names and I'm struggling with ranking the results. Considered Levenshtein distance, but it would give too low ranking for matches which contain the ...
3 votes
2 answers
1k views

What is an algorithm that maps back and forth from (x,y) coordinates to the index of that point in a space filling curve over a rectangle?

Suppose that I have a space filling curve over a rectangle of width W and height H. For example, for the rectangle: ...
24 votes
5 answers
14k views

The purpose of grey node in graph depth-first search

In many implementations of depth-first search that I saw (for example: here), the code distinguish between a grey vertex (discovered, but not all of its neighbours was visited) and a black vertex (...
0 votes
0 answers
8 views

The Multi-Room Muddy Forehead Puzzle with Varied Color Perception

Imagine there are n children, and they are divided into three separate rooms (Room A, Room B, Room C) without knowing how many children are in each room. As before, their foreheads are marked with ...
0 votes
2 answers
204 views

Minimum number of comparisons to find $2$nd smallest element

Show that the second smallest of $n$ elements can be found with $n+\lceil\lg n\rceil-2$ comparisons in the worst case. (Hint: Also find the smallest element.) [1] I tried but I have no idea how to, e....
42 votes
9 answers
63k views

Algorithm to find diameter of a tree using BFS/DFS. Why does it work?

This link provides an algorithm for finding the diameter of an undirected tree using BFS/DFS. Summarizing: Run BFS on any node s in the graph, remembering the node u discovered last. Run BFS from u ...
1 vote
0 answers
415 views

Can the shortest path problem be solved using Monte Carlo Tree Search?

I think Monte Carlo Tree Search could be used to find the shortest path, but it seems that this method is only used considering win/lose outcomes in the simulation step. If we consider the path ...
0 votes
0 answers
52 views

Graph Search Algorithms that are practically fast on dense graphs

I'm trying to do some research on graph search algorithms that are practically fast on relatively dense graphs. Besides the common ones like A* or Dijkstra's, what are some graph search algorithms ...
0 votes
0 answers
25 views

Is this Greedy Search or Uniform Cost Search?

In the below Image, S is the starting point and E is the end point. Image link Now, the Title of the video says that its a Greedy Best First Search. However, while browsing stackoverflow, I came ...
1 vote
1 answer
35 views

Algorithms/Data-Structures to calculate transitive call graphs in the presence of virtual dispatch?

Algorithms/Data-Structures to calculate transitive call graphs in the presence of virtual dispatch? I am trying to write a program to analyze Java programs and figure out the transitive closure of the ...
2 votes
1 answer
4k views

Prove that a hamiltonian DAG has a single topological sort

I've been straggling a little proving the argument "a hamiltonian directed acyclic graph has a single topological sort". This is pretty much the idea of what I've come along: lets prove by ...
0 votes
0 answers
38 views

Data structure for arithmetic logical queries

Abstract Problem I'm looking for a data structure that will (1) allow me to make queries of the form A.x - B.x <= 0.1 AND A.y + B.y >= C.y + D.y and (2) allow ...
0 votes
0 answers
24 views

Help regarding alpha-beta search

I am self teaching myself basics of AI, from the internet, I am trying to do pset3 of MIT's 6.034 here at https://ocw.mit.edu/courses/6-034-artificial-intelligence-fall-2010/pages/assignments/ the ...
6 votes
2 answers
16k views

An efficient algorithm to find a shortest cycle including a specific vertex

We wish to find shortest cycle (if any cycle exists) that includes a special vertex $v$. We know if we run DFS on an undirected graph, back edges show us that there exists at least one cycle. This ...
0 votes
0 answers
20 views

Cutting trees using depth bounded search?

I'm looking at writing a FPT (fixed parameter tractable) algorithm that takes in a tree; $T = (V, E)$. And a set of pairwise distinct vertex pairs (from $V$), $H$ and a $k>0$. Does there exist a ...
1 vote
3 answers
54 views

How to store set of long char strings to search for long char string key

I have a set of several thousand strings of max length 1024 (containing all visible ASCII chars plus space) I need to store to make it fast to search for an exact match of a key. What is the best ...
2 votes
1 answer
81 views

Finding an approximate double-zero using binary search

Let $f$ be a continuous real function on $[-1,1]$. The function is accessible via queries: for any $x$, the value of $f(x)$ can be computed in constant time. If $f(-1)<0$ and $f(1)>0$, then by ...
1 vote
1 answer
756 views

Parallel algorithm for finding the maximum in $O(\log \log n)$ time

With a CRCW (Concurrent Read, Concurrent Write) PRAM model, it is possible to find the maximum in an array containing $n$ elements with $n$ processors in $O(\log \log n)$ time. The algorithm is: If $...
1 vote
0 answers
71 views

Difference between Hadlock's algorithm and A* search

I recently read about pathfinding algorithms on grids. It seems two of the most popular are Lee's algorithm and Hadlock's algorithm. Other than the space optimizations that these algorithms employ, it ...
1 vote
0 answers
139 views

Simplified Memory Bounded A*

I have been studying the SMA* algorithm and I am having trouble understanding the backup operation. Specifically, I don't understand why the f value of a child node should be the maximum of its own f ...
0 votes
2 answers
229 views

String Search - how to find the "most" accurate string?

Assume I have the following list of companies: Apple Big Apple Google Then I have this sample string: Big Apple is a company that is trying to be the next Google. Given the list of companies and ...
2 votes
0 answers
42 views

Quantum search with input as a classical circuit

Grover's algorithm assumes $U_f$ computing a function $f$ as an oracle input. But in practice, an oracle isn't given. Instead a circuit computing $f$ is given. So let's assume a reversible circuit, $C ...
3 votes
1 answer
161 views

Find the largest caterpillar subtree

I have a problem to solve, but I am having some issues with it... Find an algorithm with time complexity O(V+E), where V and E stand for vertices and edges respectively. The algorithm searches a tree ...
2 votes
1 answer
223 views

Why is this proof that CHESS is in EXPTIME correct?

I've been reading the following paper (open) by Fraenkel and Lichtenstein that shows that the Generalized $n \times n$ Chess problem ($\texttt{CHESS}$) is $\texttt{EXPTIME-complete}$. They start by ...
1 vote
1 answer
162 views

Finding Optimal Configuration of Formula without trying every Permutation

I have a math problem I need to solve so I can complete an optimisation in a computer program. My initial approach was just to brute force all the possible permutations but it got out of hand quite ...
0 votes
1 answer
72 views

Find Best N Points From a Graph

I've given a task and wonder if there are any better solutions. Inputs of task are: Distance of district pairs Population of pairs Goal is: Find n districts at which its population and districts ...

1
2 3 4 5
14