# Tagged Questions

For questions about various search algorithms.

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 ...
86 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()$?...
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 ...
588 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 ...
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 ...
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 ...
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 ...
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.
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 ...
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 ...
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 ...