For questions about various search algorithms.

learn more… | top users | synonyms

1
vote
1answer
2k 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
85 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 $p()$?...
0
votes
1answer
121 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
578 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
2answers
4k 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 ...
8
votes
2answers
3k 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 ...
4
votes
4answers
4k 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
75 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
269 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
149 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 ...
7
votes
3answers
9k 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
886 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. ...