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

learn more… | top users | synonyms

-1
votes
0answers
22 views

Number of nodes to be expanded for DFS, BFS and Iterative-deepening search

I was wondering given depth d and branching factor b and maximum depth m, what would be the minimum and maximum nodes to be expanded for BFS, DFS and iterative-deepening search with cut off d with ...
0
votes
1answer
31 views

Why do heuristic functions only approximate the real value of the cost?

As stated in the title I'm wondering why do heuristic functions only approximate the real value of the cost? I understand it can never overestimate, but can it ensure the cost is accurate?
1
vote
1answer
28 views

Using A* search with different heuristic values

I am currently trying to use A* to create cyclical routes (for plotting driving routes of set distances). I want to find a driving route from my start location that is as close to my specified length ...
0
votes
1answer
15 views

Modified Bellman Ford to find minmum cost cycle in O(E²V) time?

I'm thinking about how you can modify Bellman Ford a bit to calculate the minimum weight cycle in an undirected graph with positive weights. Note that the constraint is that the algorithm must run in ...
2
votes
1answer
42 views

Time complexity of solving a set of 2-sat instances?

Suppose I have a set of 2-SAT instances, the set is of size $2^{3C}$ for some constant $C$. What is the time complexity of solving all instances using the fastest known 2-SAT solver?
0
votes
2answers
42 views

Why is And-Or-Graph-Search called a search algorithm?

An algorithm in Artificial Intelligence: A Modern Approach for planning in stochastic, fully observable environments is called And-Or-Graph-Search, implying that it's a search algorithm. However, I ...
1
vote
2answers
131 views

Implement a search procedure in terms of a set test procedure

Suppose you have a procedure $\mathrm{Prod}(S, t)$ that inputs a finite set of integers $S$ and an integer target $t$, and outputs either “yes” or “no” according to whether there exist ...
0
votes
0answers
38 views

Using A* to find the word closest to an input rejected by a finite automaton

In the article Fast approximate string matching with finite automata by M. Hulden (2009) (mostly pages 58/59), the author describes how to search for a closest matching string word from an automaton ...
0
votes
0answers
37 views

Learn feature value range for a classification

Which domain does this problem belong to? Given a set of products some are classified as cheap and some not. The task is to determine the price range (probabilistic) for cheap products. Supervised ...
1
vote
1answer
43 views

Finding Triples that satisfy modulo equation in $O(n\log n)$ time

Given $n$, I am trying to count the number of values $(a,b,c)$ that satisfy the following equation in $O(n\log n)$ time. I do not need the values themselves only the number of total values that ...
3
votes
1answer
34 views

Best sort method for median: median heap or insertion sort on a vector

I'm trying to decide between two methods of calculating a median, that will optimize the following operations: Add integer to data structure (insert) Get the median of all integer (getMedian) The ...
1
vote
1answer
80 views

Find all $k$ local maximums in an array of length $n$ in $O(n \log k)$ time

Given a sequence of numbers $a_1, a_2, ..., a_n$, a number $a_i$ is called the $k$ local maximum $\iff i > k$ and $a_i$ is the largest number among the $(k+1)$ numbers $a_{i-k}, a_{i-k+1}, ..., ...
1
vote
1answer
29 views

Is Binary Search Related to Binary Search Tree? [closed]

I was reading binary search and suddenly realized that it would be very difficult for a binary search tree to find the middle value and then split in two. Are these related at all?
0
votes
0answers
16 views

Finding Degree of match with Soundex or Metaphone

I am working on a search where user would search names. Spelling mistakes are bound to happen. I have used edit distance, soundex and metaphone implementations in java so far. Each one separately and ...
-2
votes
1answer
134 views

Finding bridge edges more efficiently than Tarjan's algorithm [closed]

I have to find a bridge edge in a graph but have to find it efficient time complexity. Is there an algorithm that is better than Tarjan's Bridge-finding algorithm?
4
votes
2answers
761 views

Why is the A* search heuristic optimal even if it underestimates costs?

A* search finds optimal solution to problems as long as the heuristic is admissible which means it never overestimates the cost of the path to the from any given node (and consistent but let us focus ...
-1
votes
1answer
38 views

Understanding A* Search on Tropical Island

I am working on an online course on AI and I am now working to understand A* better. Basically, right now I am working on a problem where: we live on a tropical island and we're trying to navigate ...
3
votes
1answer
52 views

Efficient algorithm for detecting overlaps in time intervals

Let's say I am building a time clock app. The employee can log into the interface and then enter time for multiple projects so that we can generate reports for billing as well as payroll. A table in ...
2
votes
1answer
63 views

Where is knowing the 2^k largest elements in a array useful?

I came across this question today on stackoverflow. It asks: Find the largest, $2$nd, $4$th, $8$th, ..., $2^{\log n}$-th largest element in an arrary. Use $O(n)$ algorithm. $2^k$ I've come ...
0
votes
1answer
17 views

Searching for an item over a non-uniform query distribution

If I have a static set of $n$ items in a database that are all queried with uniform probability it makes sense to put them in a binary search tree. This way any given search will take, on average, ...
2
votes
0answers
219 views

Fastest algorithm for shortest path with atmost k edges on a DAG with non-negative edge weights?

(Please note, this is not a duplicate to Shortest path with exactly $k$ edges OR Shortest path with a fixed number of edges. What I want is a better algorithm) The problem under consideration is to ...
27
votes
3answers
5k views

Why is binary search faster than ternary search?

Searching an array of $N$ elements using binary search takes, in the worst case $\log_2 N$ iterations because, at each step we trim half of our search space. If, instead, we used 'ternary search', ...
1
vote
0answers
86 views

Boyer-Moore with Don't Cares

I have been doing a lot of research into pattern matching algorithms. For some background I am searching a long binary alphabet text consisting of considerably more 0s than 1s. The individual ...
2
votes
1answer
59 views

Relationship between message entropy and complexity of the best algorithm

Is it possible to estimate number of steps in best possible algorithm for classification of messages, using entropy of messages? E.g. linear search problem. We have an ordered set of incomparable ...
4
votes
1answer
144 views

Finding an element in a sorted array with at most three queries to larger elements

Given a sorted array A, we have to find the position of an element m in it. (It is also given that the element exists in the array.) However there is a constraint. Like in a game you have 3 lives. If ...
1
vote
2answers
83 views

Can you explain this improvement to this frequency distribution algorithm?

I came across the following in a text book: Frequency distribution – Given a set of n items, which element occurs the largest number of times in the set? If the items are sorted, we can sweep from ...
2
votes
0answers
49 views

Stopping condition for goal-directed bidirectional search for shortest path

So I have a graph and need to find shortest path between two points in it. I need1 to do it it using bidirectional search. The bidirectional search should be goal-directed, i.e. A*. So let $l(u,v)$ ...
1
vote
1answer
32 views

Text search by first order formula

I am searching for substrings that satisfy a given first order formula in a moderately sized text. The formula is made out of usual $\wedge, \neg, \exists$ and predicates ...
3
votes
2answers
78 views

Find rectangle of minimum area where dimensions are larger than minimum

Problem: Given a collection $S$ containing $|S|=n$ rectangles defined by dimensions $(x,y)\in R^2$ (width and height of rectangles are real numbers), find the rectangles with the minimum area ($A_i = ...
0
votes
1answer
106 views

Longest Path A*, Admissible Heuristics, and Optimalness

Im working on a modified A Star algorithm, that instead of attempting to find the shortest path, it tries to find the longest past, or in my specific case, the highest weighted path. I have some ...
2
votes
1answer
67 views

Efficient algorithm for iterated find/replace

I'm looking for an algorithm for doing iterated find/replace, where the act of finding the replacement list of tokens for a given find is slow. Specifically: I have a function, ...
6
votes
0answers
95 views

Approximate nearest neighbour in practice

I have $10^3$ vectors each of dimension $10^4$. Each dimension takes an integer from a limited range. I would like to build a data structure that will answer approximate nearest neighbour queries ...
5
votes
0answers
66 views

Understanding the Baeza-Yates Régnier algorithm (multiple string matching, extended from Boyer-Moore)

First of all, excuse me if I write a lot, I tried to summarize my research so that everyone can understand. R. Baeza-Yates and M. Regnier published in 1993 a new algorithm for searching a two ...
-2
votes
1answer
97 views

How do you return the k smallest elements of an array using Mergesort?

I'd like to create a modified mergesort algorithm to return the k smallest elements of an array. The mergesort algorithm below sorts an unordered array of size n. How do I modify the algorithm so that ...
1
vote
2answers
132 views

Finding shortest path from a node to any node of a particular type [closed]

I have an un-directed, un-weighted graph G.Starting from a given node A, i want to find whether there is a path from A to a node of a certain type .There can be many nodes of that type. The problem is ...
2
votes
1answer
104 views

Why is the base used to compute hashes in Rabin–Karp always primes?

The Rabin–Karp string matching algorithm requires a hash function which can be computed quickly. A common choice is $$ h(x_0\ldots x_n) = \sum_{i=0}^n b^i x_i, $$ where $b$ is prime (all computations ...
0
votes
2answers
383 views

Maximum length path between any two nodes in a tree with possible negative edge weights

Is there an efficient way to find the longest path between any two nodes in a tree. Given that edges can have negative weights. I know about the diameter problem which finds the longest path in a ...
3
votes
3answers
89 views

Minimum number of tests to identify subset of modules that trigger a bug?

I have an ordered set of $M$ software modules compiled together. The interaction of some $N$-tuple of these modules is causing a bug when the program is run. I can run the program with any desired ...
1
vote
1answer
33 views

What is the algo used for Phonetic Search

I am new to the field of text mining. Could not figure out what to search on google so am here for the same help. When we talk of approximate / fuzzy string match. searching for RAT would give RAAT ...
-4
votes
1answer
60 views

Implement “from” function for AVL Tree java

I posted this same question on stackoverflow but I think it might be better suited here as I am having trouble with coming up with an algorithm with O(log(n)) running time. Question: I am ...
2
votes
1answer
64 views

What is the complexity of depth first traversal that don't label nodes as discovered?

I've found an algorithm that acts like a depth first traversal that don't recognizes nodes that have been visited before. A / \ B C \ / D | E If run ...
2
votes
0answers
38 views

Searching for multiple elements of an array

Suppose we have two sorted arrays $A$ and $B$, and we want to find the indices in $B$ of all elements of $A$. We can do this in $\mathcal O(|A|\log|B|)$ time by simply binary searching $|A|$ times. We ...
1
vote
1answer
127 views

Shortest path from starting cell to all cells in the grid

I found an algorithm for finding the shortest path on grid between selected cell, to all cells on the grid, with $O(KN)$ where $K$ is the number of neighbor cells and $N$ is the number of cells. How ...
0
votes
1answer
123 views

Sorted array with odd indexed elements swapped randomly [closed]

A sorted array $\mathcal{A}$ with even number of elements is given. Consider $\mathcal{A}$ be partitioned from the middle such that both parts ($\mathcal{A}_1, \mathcal{A}_2$) contain equal number ...
1
vote
0answers
26 views

Grover algorithm for known number of solutions

I am reading Computational Complexity book and specifically Grovers search algorithm. I am aware that if we knew in advance exact number of solutions $K$, then the basic algorithm can be tweaked to ...
4
votes
1answer
73 views

How to perform local search on simple paths?

I have a local search problem. The set of valid solutions are all the simple paths (i.e. without repeated nodes) from a node $S$ to a node $T$ in a directed graph. The question is: given a current ...
4
votes
1answer
46 views

Placing 1d items in a 2d grid with constraints

I'M looking for an algorithm (preferably polynomial) for the following problem: Input: - an M x N grid, where each square can be either empty or occupied - a list of items - a list of constraints ...
1
vote
0answers
23 views

Steps to implement PageRank Algorithm on a local set of webpages [closed]

I just completed a detailed theoretical mathematical study about the PageRank algorithm, I want to make a sample implementation to make some tests and play with it, supposing that I have a local ...
0
votes
0answers
65 views

How to populate the tabu list in tabu search?

I am trying to implement Tabu search, as shown here, for my problem. I am now stuck on how to generate the tabu list. In algorithm it mentions that if cost of the candidate is better than the best, ...
1
vote
2answers
116 views

Searching for a string of numbers in a large digit sequence [closed]

How would one search for a string of digits in a large digit sequence? For example, I'd like to search for 351814 in Euler's number. I'm not too keen on computer ...