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

learn more… | top users | synonyms

9
votes
2answers
600 views

What is a lay explanation for universal search?

I am reading a book on a computer science topic but lack some of the prerequisite background. Normally when I run into terms I don't understand I simply look them up, but for Universal Search I simply ...
0
votes
0answers
49 views

Iterative lengthening search: iterative version of Uniform Cost Search or DFS?

Actually my question has two parts: 1) I wanted to know that whether Iterative Lengthening Search is used in combination with DFS or Uniform Cost Search? Actually, in Russell and Norvig book (on page ...
4
votes
1answer
109 views

Finding all circuits that contain a given edge

Given a directed graph $G = (V, E)$ and an edge $e \in E$, I'm trying to come up with an algorithm to construct the minimum induced subgraph $H$ of $G$ with the property that every circuit in $G$ that ...
0
votes
1answer
30 views

Algorithm to determine two binary expression trees will give the same result based on associative and commutative properties of some operators

Given n different numbers, I would like to find out whether there exists an algebraic expression using all the n numbers, with n−1 binary operators and unlimited number of parentheses, that ...
0
votes
0answers
60 views

What data structure would help find nearby coordinates quickly?

I need to write a program that does the following: Take an input list of objects whose properties include latitude and longitude to, say, 5 decimal places Store them in a data structure once Provide ...
2
votes
1answer
133 views

What is the name for this search algorithm?

A colleague came up with the following search algorithm: We have an array of sorted, distinct integers [$i_0$ < $i_2$ < ... < $i_n$] We are looking for the index of $i_k$ (for simplicity ...
3
votes
2answers
61 views

Finding the lightest simple path in trees with integer weights

A tree with integer weights (positive, negative or zero) is given. We want to design an efficient algorithm for finding a simple path with lightest weight in this tree. That is, we look for shortest ...
1
vote
2answers
68 views

How to find the Branch factor of 8 Puzzle

I would like to know how to find the average branching factor for 8 puzzle.While referring Artificial Intelligence by George F Luger it says that: Suppose,for example we wish to establish the ...
-1
votes
1answer
22 views

Is it possible to make excluded search with for loop in Java? [closed]

I am trying to calculate all pure strategy Nash equilibrium in a mxn game. It requires to check all pure strategy pairs (m.n pairs). Suppose player 1 has m strategies. Algorithm should start with the ...
1
vote
0answers
37 views

Given an algorithm, what are the probabilities for its run-time cases?

I am given this algorithm And I am also given the fact that $1 \leq k \leq n$. If we let X be the number of times line 2 is executed, then I am supposed to find the run-time probabilities for the ...
2
votes
0answers
22 views

Heuristic for weighted maximum independent set in graph with ~$2 \times 10^5$ nodes and $|E| \propto |V|$

I want to find a near-optimal solution for a maximum weight independent set. i.e given a graph $G = (V,E)$ I want to find a set $S = \{v_1,v_2,\dots,v_n\}$ of nodes in $V$ such that the sum of their ...
0
votes
0answers
4 views

Detecting junctions algorithmically

With route finding algorithms, we get the children of each node. So for example, an A* search on google maps at each point in the search would know which roads can be the successor to the current ...
0
votes
1answer
31 views

Heuristic for sokoban puzzle problem

I am trying to write IDA* for Sokoban puzzle problem (http://en.wikipedia.org/wiki/Sokoban) but It seems that my heuristic is not so good for making the algorithm fast. My heuristic is to consider ...
0
votes
3answers
41 views

Complexity of BST [duplicate]

I have the following pseudo-code for printing all nodes of a BST : ...
1
vote
3answers
115 views

Fastest possible way to check what of X is in a string

I am trying to speed up one of my application, one of the places where I can speed up is in my test if a string contains an array of strings. example: I have the matches "dog", "cat" "apple" and the ...
0
votes
1answer
58 views

Efficiently count frequency of n-grams at start of words

I have a text file with all possible 5-grams (26^5 = 11.881.376) organized in rows as: aaaaa aaaab aaaac aaaad ..... and I have a txt file (organized in rows) with all English words. I have to find ...
0
votes
0answers
32 views

Finding and Grouping like children

I'm working on a dependency managemen solution for a JavaScript. I'm trying to find the best pattern for grouping similar items in a graph into their own 'modules'. Given a dependency tree like ...
1
vote
0answers
43 views

Formulating an arrangement problem with STRIPS

The problem is rearranging furniture in a flat. We are given rectangular rooms of natural width and height with doors between them, (the walls have no width) and rectangular furniture at starting ...
1
vote
1answer
37 views

How to do high performance string matching when comparing unordered sets of tokens [closed]

This is the problem: I have some strings stored in the database. Each of the strings can be seen as a set of tokens separated by comma with no repetition (I mean a token cannot appear more than one ...
-1
votes
1answer
50 views

Given two heuristic values how do I tell which one is admissible?

I am given 2 list of admissible values for a graph, and the graph with the real cost to each of the nodes. Am I correct in thinking the way to see which one is admissible is add up all the values of ...
1
vote
2answers
167 views

Greedy and backtracking solutions to an arrangement problem with constraints

I'm revising for my finals. I have found a pattern in past papers in terms of a recurring question, reworded coming up every year. But I've no idea what the marker actually wants... I've asked class ...
3
votes
1answer
77 views

Efficient algorithm to find vertex with paths to every other vertex

$G=<V,E>$ is a directed graph. I need to write an efficient algorithm that finds a $v \in V$ such that there exists a path $\forall w \in V$ $v \rightarrow w$ ($v$ has a path to every other ...
0
votes
2answers
68 views

Why is it the lower the h(n) cost the more nodes need to be expanded in A*?

Why is it the lower the h(n) cost the more nodes need to be expanded in A*? As found here - http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html If h(n) is always lower than (or ...
1
vote
1answer
49 views

negative effective branching factor it's possible?

i've implemented A* algorithm in python,after that i calculate with this python function the effective branching factor $ B^* $ $ T+1=1+B^*+(B^*)^2+⋯+(B^*)^L$ where $T$ is the number of expanded ...
0
votes
1answer
40 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
47 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
28 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
48 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
65 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
137 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 ...
1
vote
0answers
46 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
48 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
45 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
52 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
95 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
32 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
33 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
287 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
885 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
40 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
61 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
66 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
20 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
317 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 ...
29
votes
3answers
6k 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
88 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
61 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
155 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
89 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
66 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)$ ...