For questions about various search algorithms.

learn more… | top users | synonyms

1
vote
1answer
31 views

Exploiting geometric invariants via group theory

Let $T$ be the set of all plane triangles. The problem is to find $t \in T$ s.t.h. a predicate $P(t)$ holds. At present, I'm doing this by a form of randomized search procedure (effectively via a ...
1
vote
1answer
21 views

Need help understanding a simplification in a simultaneous search model.

The problem I am trying to solve is $\max_{k \in \mathbb{N}} \int_0^1 u d F(u)^k - ck$, where the associated utility is an iid random variable U following $F(\cdot)$ on [0,1]. $c > 0$ is the ...
2
votes
1answer
21 views

Find the three closest surrounding neighbors from a data

I have a data of coordinates $x$ and $y$ where we know the range of both variables, e.g. $(x,y)\in[0,1]^2$. So for a given any random point $\theta_0=(x_0~~y_0)^T$ in the range of $x$ and $y$ I would ...
0
votes
0answers
23 views

Fewest questions to reach an arbitrary confidence level about the number of words a person knows in a foreign language

I have a list of 13060 Chinese characters that are pre-sorted from most frequently used to least frequently used. I would like to design a simple test to determine the total number (or approximate ...
1
vote
0answers
27 views

How to determine size and height balance of binary search tree?

I've been reading/ learning binary search trees and I've been stuck on the following question for a while now. I have the following tree, how do I determine the height and size balance of it? How do ...
0
votes
0answers
30 views

Breadth First Search Question

The adjacency matrix for a simple graph is shown here (as an HTML table). The questions below refer to the graph that this table represents. Give the path that is found from vertex G to vertex E ...
0
votes
0answers
15 views

Estimate parameters of a system on realtime defined as follows

I have a motor I need to estimate the parameters on real time. To simplify the problem I will put the general equation in matrix form that governs it in discrete time: $$ u_q(k) = \left[ ...
1
vote
1answer
79 views

Searching Algorithm

A company database has 10,000 customers sorted by last name, 20% of whom are known to be good customers. When looking up a customer’s record in the database, the good customers account for 60%. Two ...
0
votes
0answers
47 views

binary search worst case for a set database of entries some good some bad

A database has 10,000 sorted entries, 20% known to be good. When looking up a record in the database, the good entries account for 60%. Two design options are considered to store the data in the ...
0
votes
0answers
22 views

Obtaining Pareto front for more than 2 objectives

I have a reasonably tractable problem withe >2 objectives in which I apply multi-objective evolutionary algorithms (MOEA) like PSO, ACO, GA. I would like to compare the performance and quality of ...
0
votes
1answer
39 views

A mathematical expression for “grid search”?

I've got a question whether there is a mathematical expression for a grid search? I have two parameters a and b in [0;1]. Depending on the values of a and b, I get a value for my function (the value ...
2
votes
0answers
18 views

n-dimensional searching alogrithm

If you want to store various points in a $n$ dimensional (here $n=2$) space. Is there a possibility to do that with a tree (as a binary-tree for $n=1$ is usually used) for efficient and fast finding ...
10
votes
1answer
200 views

The “find my car” problem: proper interpretation and solution?

This has been asked at least twice here, but both questions have accepted answers which are wrong. I don't really know any good way to draw attention to the question besides asking again and being a ...
1
vote
2answers
53 views

How to use binary search to find a function

I am reading somewhere that $$(\phi'(y))^{-1}=y^{-c_1}+y^{-c_2},$$ $c_1,c_2$ are some numbers, can be solved for $\phi$ using binary search. I am surprised because binary search binary search is used ...
0
votes
1answer
53 views

Infinite Search Tree Probibility

I have a question on Search Trees. I have a balanced, infinite, search tree. If you check a node at level $l$, the probability of finding a solution at that node is $p^l$. Questions The first ...
3
votes
1answer
68 views

Spacing of fence posts with minimal distance to other fence posts

Definition 1: A "fence" is a set of "fence post positions", where each pair of adjacent positions has the same difference (the spacing), e.g. $\{1,2, 3, 4\}$. A fence is described by three values ...
1
vote
1answer
131 views

How to search between $n$ candidates from unknown position?

It might be involved more with search algorithm but I cannot think of any of them. Here is the problem: You are in a corridor that stretches infinitely in both directions. Your room is somewhere ...
3
votes
1answer
382 views

Choose a k-subset such that its elements 's gcd is maximal

Given $n$ positive integer and a positive integer k. How to find a subset of size k such that its elements 's gcd is maximal (just give the maximum value of gcd is okay). Example: Give $3$ integers ...
1
vote
1answer
20 views

Binary search in merged arrays.

Given two arrays, sorted by ascending. Result array is first array and second at the end of first. Example: [1, 4, 7, 11] and [2, 3, 5]. Result array is [1, 4, 7, 11, 2, 3, 5]. How to find element ...
1
vote
0answers
44 views
0
votes
1answer
42 views

How to extract all the points from a noisy surface?

I have points representing a bridge like in this picture: My goal is to get all the points that are in the red box. These points all share a common surface that is not necessarily planar. The ...
2
votes
0answers
108 views

A* vs D* vs Dijkstra [closed]

I understand the basis of A* as being a derivative of Dijkstra, however, I recently found out about D*. From wikipedia, I can understand the algorithm. What I do not understand is why I would use D* ...
0
votes
2answers
179 views

Shortest Path between two vertices of a weighted, undirected graph IN LINEAR TIME

Studying for an algorithms test, and a surprisingly simple problem has me somewhat stumped. The following is the question: My issue has been - looking online, everyone uses this kind of problem to ...
1
vote
1answer
118 views

Searching for random items in a set of lists

This is a programming question, but I'm interested in the math behind it so I think it's better asked here. Say I have a list of items and I'm looking for one item in the list that satisfies a ...
0
votes
0answers
44 views

How to search for an object in more efficient way?

I have a doubt how to check if structure contains an object. Simple sketch of my structure: Root - is a group which can contain groups, keys, values. Group - can contain groups keys, values. Key - ...
1
vote
0answers
34 views

State Space Search

I searched in the web about simple example about State Space Search, but I didn't find any simple and clear one. Can anybody explain to me what State Space Search about by a simple example? Thanks ...
1
vote
1answer
31 views

Having objects trajctories and directions how to find where objects traverse same path?

I have N objects that travel on some trajectories (unique for each object). At each agent curve point we can get object speed (direction). Having some distance ...
1
vote
1answer
439 views

Breadth-first search tree

It seems intuitive, and is actually proven in many books, that each path from starting vertex to another one in any search tree of a breadth-first algorithm is the shortest. However, I couldn't find ...
1
vote
1answer
891 views

Term-document vs document-term matrix [closed]

I am not sure if this is the right website to ask this question but I cant figure out where else to get the answer so, please, dont be mad :-) As my bachelor thesis/project, I am trying to construct ...
2
votes
0answers
163 views

Partition minimizing maximum of Euler's totient function across terms

Given natural numbers $M$ and $N$, I'd like to find a partition of $2^N$ with $M$ or fewer terms, $t_1 + t_2 + ... + t_M$, such that $\max(\phi(t_1), \phi(t_2), ..., \phi(t_M))$ is minimized, where ...
0
votes
1answer
43 views

Trivial case of $s \in T$

I was reading paper A Formal Basis for the Heuristics Determination of Minimum Cost Paths in section B "Some Definition About Graphs" there is footnote that say "We exclude the trivial case of $s \in ...
4
votes
1answer
2k views

Median of medians algorithm

I am referring to the algorithm presented here used to find a good pivot: http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm My ...
0
votes
1answer
504 views

Help in understanding search of Vantage-Point tree

This is my reference: http://stevehanov.ca/blog/index.php?id=130 A vantage-point tree is a way of organizing a set of points so that finding the n-nearest neighbors is as efficient as possible. It ...
1
vote
0answers
53 views

How to formulate a best-search algorithm limited by a count of nodes visited?

The problem I'm doing a search by computer program. Each node takes about 5 minutes of wall time to get a result so I'm looking to carefully choose the nodes to inspect so as to find the best result ...
1
vote
1answer
1k views

What is the lower bound and upper bound on time for inserting n nodes into a binary search tree?

So given a $n$ array of few numbers(say $n$) we can sort them using the binary search tree (BST) as a black box . In order to that we first build a BST out of the array taking all the elements in ...
2
votes
1answer
79 views

Searching for a secret, given a non-uniform distribution

Let $s$ be an unknown bit string of length $n$. Let $p(i, b)$ be the probability that $i$-th bit of $s$ is equal to $b \in \{0,1\}$. What's the fastest method to find $s$, given the distribution ...
0
votes
1answer
120 views

Ranking System :S

My math experiences I had at school are not very advanced and I'm struggling with a calculation right now... I'm programming an image Search script for my company where you can find all pictures we ...
3
votes
2answers
420 views

In what sense is “Uniform-cost search” uniform?

The name of Uniform-cost search in computer science is not instinctive since what part of it being "uniform" is not clear to me. Apparently uniformity is not about the cost of each edge - most of the ...
2
votes
1answer
3k views

What is the best strategy for a guess-my-number game?

In the "guess-my-number" game, one player (player A) makes guesses at another player's (player B) secret number. All games would follow the following procedure: Player B decides on a number between ...
7
votes
2answers
2k views

Algorithm wanted: Enumerate all subsets of a set in order of increasing sums

I'm looking for an algorithm but I don't quite know how to implement it. More importantly, I don't know what to google for. Even worse, I'm not sure it can be done in polynomial time. Given a set of ...
3
votes
4answers
2k views

Need an efficient algorithm to visit all nodes of a graph, revisiting edges and nodes is allowed

Update: This is my solution with Kruskal's Algorithm, although it doesn't take into account real "path". Brute force may be the only solution. http://www.youtube.com/watch?v=VbSwwos4R2E Hi, I ...
0
votes
1answer
74 views

In Mathematica, is there a way to set a variable to the lowest value in a matrix?

It seems that a major aspect of this question is figuring out whether or not I can search the matrix and compare values.
1
vote
1answer
230 views

calculating walks in an undirected graph using linear algebra identity

I am reading a text on maths applied to naturally occurring networks, eg. social networks. The section I am on is "Walks" networks. The text says: Walks: which allow both nodes and edges to be ...
1
vote
1answer
147 views

Is there a simple function which can be used to determine the two “next” search indexes in a binary search?

Edit: question simplified to remove confusion Assuming a sorted list of items with indexes from 1 to N, and given only an index number ...
6
votes
3answers
6k views

Lower bound for finding second largest element

In a recent discussion, I came across the idea of proving a lower bound for the number of comparisons required to find the largest element in an array. The bound is $n - 1$. This is so because the set ...
12
votes
3answers
792 views

Twenty questions against a liar

Here's one that popped into my mind when I was thinking about binary search. I'm thinking of an integer between 1 and n. You have to guess my number. You win as soon as you guess the correct number. ...