# Questions tagged [search-algorithms]

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

697 questions
Filter by
Sorted by
Tagged with
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?
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 ...
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 ...
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 ...
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
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
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, ...
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 ...
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 ...
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 ...
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 ...
96 views

1 vote
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
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 ...
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 ...
42 views

1 vote