Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [search-algorithms]

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

1
vote
1answer
37 views

How many queries does it take to find the best flight?

I often find flights through a search engine like Google Flights. On input some refined subset of the space of all flights (e.g., non-stop only, departing in the morning, from one of two airports, and ...
0
votes
0answers
29 views

Generation vs expansion BFS

I can not understand the difference between generation and expansion of nodes. How the time and space complexity of BFS are different in each two scenarios? ...
2
votes
1answer
104 views

Variant of nim game with particular rules

Let's say we have the following rule for that particular Nim game: You have multiple heaps, and you have to remove 1,2 or 3 sticks (not more) from a SINGLE choosen heap. The player who pick up the ...
0
votes
1answer
527 views

Find all local minima in a big 2d array

Assume we have a big 2d array. All its elements are either zeros or natural numbers. A local minimum is an element that is less than all its 8 neighbors. Is there an effective algorithm to find all ...
1
vote
1answer
22 views

Better algorithm for aggregating data from various LDAP systems

I have 10 LDAP systems which contain users and groups in the form of objects. Each user / group is identified by a distinguishedName like ...
0
votes
0answers
32 views

Fuzzy, nonsequential string search algorithm?

Is there an algorithm that can find p + stuff within t, where stuff is any set of characters,...
2
votes
0answers
28 views

Avoiding collisions in space and time

Say I have an image, represented as a 2D array of pixel values. Also, say I have a set of points on that image where each has a current (x, y) position and a Destination (x, y) associated with it. I ...
0
votes
1answer
23 views

The optimal way to find leaves in a weighted full binary tree

Let T be a full binary weighted tree. For a node v in T, the cost of going right is a i.e w(v, v.right) = a while w(v, v.left) = b How do I find optimal paths to all leaves from the root. I don't ...
2
votes
1answer
87 views

Average-case analysis of linear search given that the desired element appears $k$ times

The problem below is adapted from CLRS Problem 5-2 "Searching an unsorted array": Consider a deterministic linear search algorithm which searches an array $A$ for $x$ in order, say $A[1], A[2], \...
4
votes
0answers
46 views

Efficient approximation for find all the nodes and edges which match with some sub-tree in a graph

Let's suppose that I have a big digraph D and a small tree T (small w.r.t D), both directed, D can be connected or not, but T is connected. Here an example: Let's say that D is as follow: And T is ...
2
votes
2answers
187 views

Infix search in millions of strings

Let's say we have millions of strings (each of them < 100 characters): alpha allo blah hello world orlando ... I know how a binary search tree or a trie can ...
2
votes
1answer
61 views

Fastest way to search a word in a word list?

I have a word list like "English Open Word List" used to create word games. The list is in txt file with space between words, like; aa aah aahed .........and so on. I want to search it while typing ...
1
vote
0answers
29 views

Do we need visited flags when applying BFS on a tree?

Do we need visited boolean flags when applying BFS on a tree ? ...
2
votes
0answers
261 views

How to traverse a graph in reverse dfs order

For kosaraju's algorithm to traverse the graph in reverse order the naive solution is to reconstruct the original input graph in reverse order and dfs on it. Is there any way I can avoid creating ...
0
votes
1answer
30 views

Algorithm to find a shortest past under a special condition

I am trying to come up with an algorithm that calculates the length of shortest rectangle movement in a given bitmap. For example, let's say we have a 24x24 bitmap where 1 is black pixel and 0 is a ...
2
votes
1answer
62 views

Local search (Hill Climbing) scope and definition

I'm taking an artificial intelligence class and in one of the recent lectures the topic was local search algorithms, more specifically Hill Climbing. At one point the professor showed the classic 8-...
0
votes
1answer
312 views

How to calculate number of nodes opened by BFS?

In the below diagram, each node takes up a space of 2KB. I need to find the total memory consumed to reach the goal : I I know that the equation for BFS is b1 + b2 + ...... + (bd+1 - b) Where b is ...
1
vote
1answer
34 views

data structure admitting top items with prefix

A trie can answer a query for all items with a certain prefix in $O(m + \log n)$ time, where $m$ is the number of matches and $n$ is the number of items. A trie also supports $O(\log n)$ insertion and ...
-1
votes
1answer
16 views

Count points on same distance from set of points

Let's consider finite grid of points with size of $N$ by $M$ and set of $x$ points ($x$ is small number, up to 10, $N$ and $M$ are big numbers, up to 30000 )). Each of the $x$ points is described with ...
1
vote
1answer
48 views

Thompson Regular Expression Search Algorithm 3rd Stage

My professor assigned us to read Thompson' Regular Expression Search Algorithm paper. I am struggling to understand the third stage of the compiler. The first two stages are as follows: Check that ...
4
votes
0answers
33 views

Any elegant approach to search where users have permissions on subset of records?

I work in Search and have seen following problem appear in different forms. There are many users in an enterprise; they have ability to create records. Each user has variable level of access to some ...
-2
votes
1answer
193 views

If $h(s)$ is an admissible heuristic, is $\sqrt{h(s)}$ admissible?

I was thinking yes because $0 \leq \sqrt{h(s)} < h(s)$ but I'm not entirely sure.
3
votes
1answer
195 views

Are the No Free Lunch theorems useful for anything?

I have been thinking about the No Free Lunch (NFL) theorems lately, and I have a question which probably every one who has ever thought of the NFL theorems has also had. I am asking this question here,...
0
votes
0answers
299 views

Creating admissible and consistent Heuristic function Help

I am trying to create a heuristic function for use in an A* algorithm. The problem to be solved is a single row tile puzzle with 3 total w tiles and 3 b tiles and one "_" tile as shown below WWW_BBB ...
0
votes
1answer
35 views

Given a set of points, find the one closest to a given point

So, I'm given an arbitrary set of points $(p_1, p_2, p_3,\ldots)$ with an $x$ and $y$ coordinate. I have no information about the order they're given to me. I need to write code that will take in a ...
-1
votes
1answer
38 views

Using computer vision instead of algorithms?

I have been thinking of a problem i have here with a calendar scheduler where i basically want to split a year into seconds and have access to the dataset of whole year. In this year i assign blocks ...
1
vote
2answers
123 views

Best way we know search for an integer

Basically, you have $n$ integers. The data structure is for your choice, it is ok to do polynomial time preprocessing on them. Then you have multiple questions "Is an integer $k$ in the set?" My ...
2
votes
1answer
48 views

Finding the best poker hand in a connected grid structure where order matters

I am trying to find the best poker hand in a connected grid, where order matters. An illustration is the best way of explaining the situation. This grid has 12 random cards, in random positions. Each ...
0
votes
0answers
34 views

Computing the shortest path in a labyrinth

I'm currently trying to map how to make a good algorithm that won't have issues to find the shortest path. The labyrinth consists of an X and Y dimensions as input; However, the labyrinth will ...
1
vote
2answers
55 views

Finding an index such that $A[i] = i$ in a strictly increasing integer array

I'm looking for a hint for solving the following problem : Given an array $A[1, \dots, k]$ of integers where $A[1] < A[2] < \dots < A[k]$ write pseudocode for an algorithm that ...
1
vote
0answers
22 views

How can I find the pattern with one mismatch at most by modifying Naive Algorithm?

I want to modify the Naive algorithm to find out if there is any occurrence of the string P in T as a substring with at most one mismatch - where a mismatch is either one of the following: INSERT, ...
1
vote
2answers
30 views

How would I go about determining popularity and relevance among articles and use it to improve my search algorithm

Disclaimer: First of all I've had a lot of trouble finding the right stack exchange site for this question and I don't know if it's correct here either. The Problem: I'm working on a search algorithm ...
1
vote
1answer
27 views

Generate a unique number for a set of sequences of letters

A sequence of English letters are given, every sequence forms a word and we know that the size of each word is at most $15$ and the number of words is at most $50000$. For a given input word $w$ I ...
0
votes
1answer
55 views

Returning two array indices in an array for a given value

Give an algorithm that takes as input an array A sorted in non-decreasing order, and a value x, and that returns two indices (F and L) into A, where A[F] is the first value equal to x and A[L] is the ...
0
votes
1answer
46 views

Hueristic Algorithm to find the maximum clique

Let the algorithm be defined as follows: Consider the following heuristic algorithm for finding the maximum size clique in a graph. (1). Delete from the graph a vertex that is not connected to every ...
2
votes
0answers
27 views

Search algorithm with constraint of proximity to another point

Let us consider a plain search algorithm (Dijkstra being one example) which will calculate the shortest path from A to B. Now introduce the additional constraint that the path must be as close as ...
2
votes
2answers
692 views

Does the A* algorithm visit every node?

I have been taught that the A* algorithm visits every node on the graph, like Dijkstra's does, prioritising nodes with the smallest cost. However, visualisations of the algorithm, such as this one, ...
2
votes
1answer
36 views

Does there exist a sorted search with $O(\log n)$ worst-case runtime and $O(\log \log n)$ on average?

I thought of some mixed algorithm: binary + interpolation search. While first has $O(\log n)$ runtime in both worst and average cases, second has $O(n)$ worst case runtime and $O(\log \log n)$ average ...
0
votes
0answers
66 views

Algorithm to find extrema of a function?

What are some simple algorithms that find the maximum of a function in a certain domain? The function $f$ is guaranteed to have 1 maximum and no other turning points between $a$ and $b$, how can I ...
0
votes
1answer
66 views

How consistent heuristics guarantees A* optimality without adding same node to the frontier twice or more

Taken from Artificial Intelligence A Modern Approach : Notice how a node doesn't gets added to the frontier twice in Graph-Search, And then take a look at this : Now obviously this is not true as in ...
1
vote
1answer
134 views

consistent heuristic - does it always exist?

I am studying for an artificial inteligence class, and i have to classify the following sentence "For any search space, there is always an admissable and consistent A* heuristic". Well, i know that ...
1
vote
1answer
34 views

Is it possible to obtain dynamic tree with two dimensions in big matrix

Let's say we have given matrix of size $n \cdot m$, such that both $n, m$ are big numbers and we cannot keep the whole matrix in memory (up to 10 millions). In some of the coordinates of the matrix ...
0
votes
2answers
2k views

Number of comparisons in Binary search

I know this question is very trivial to ask, but I have got some doubt while solving this problem.Code is given below ...
1
vote
1answer
232 views

If h(n) is a perfect heuristic (that is, h(n) = h*(n)), then does it imply that A* will always take linear time complexity?

That is, if h(n) = h*(n), then A* only expands nodes that lie on an optimal path to the goal. But does this imply that A* will always take a linear time in the solution length to find an optimal ...
1
vote
3answers
104 views

Solving a discrete optimization problem

Assume that $x_1,\dots,x_n$ are $n$ integer variables which takes values in a subset of given numbers, say $x_i\in\{5,6,\dots,5000\}$. Let $f_i(x_i)$ and $g_i(x_i)$ both be non-decreasing non-negative ...
2
votes
0answers
25 views

Heuristic Consistency with float multiplications

I'm running A* search with a theoretically consistent heuristic. I'm doing a lot of float multiplications, and I'm not sure how best to ensure that my heuristic remains consistent down to the last ...
0
votes
1answer
47 views

Check if current interval is overlapping some intervals, or is being overlapped

Let's say we have array of $K$ integers, and we have given $N$ intervals in the form $l_{i}, r_{i}$, both inclusive, the interval $i$ means that all elements in the range $[l_i, r_i]$ are covered. Our ...
5
votes
1answer
350 views

nlp: phonetic edit distance between a word and the closest of a set of words

Let's say someone is using Dragon Dictation, Google Speech, or some other free form dictation software (it will recognize anything they say to the best of its ability). I have some reasonably large ...
0
votes
1answer
141 views

Finding an element in a infinite unsorted doubly linked list

Is there any way to find an element in an unsorted doubly linked list given an element and pointer from which we can navigate? (we can't use head/tail pointers since the list is infinite)
1
vote
0answers
161 views

Prove that a convex combination of admissible heuristics is admissible

I got this question that's been troubling me for some time. If $h_1$ and $h_2$ are admissible heuristic functions, prove that $h_3 = (c-1)\,h_1 + c\,h_2$, $0 < c < 1$, is also an admissible ...