algorithm

Nth largest element in a binary search tree

How to find the Nth largest node in a BST? Do I keep a count variable while doing In Order Traversal of a BST? Return the element when the count = N??? ...

calculating the potential effect of inaccurate triangle vertex positions on the triangle edge lenghts

i'm not sure how to solve the following problem: i have a triangle with each of the three known vertex positions A,B,C being inaccurate, meaning they can each deviate up to certain known radii rA, rB, rC into arbitrary directions. given such a triangle, i want to calculate how much the difference of two specific edge lengths (for insta...

Reservoir sampling

to retrieve k random numbers from an array of undetermined size we use a technique called reservoir sampling. Can anybody briefly highlight how it happens with a sample code?? ...

Rerversing AND Bitwise.

Hey all, Here's the following algorithm: int encryption(int a, int b) { short int c, c2; uint8_t d; c = a ^ b; c2 = c; d = 0; while(c) { c &= c - 1; d++; } return d; } How can I find which variable a and b I should send in that function to decide of the output value of d? In other w...

Determine coordinates of rotated rectangle

I'm creating an utility application that should detect and report the coordinates of the corners of a transparent rectangle (alpha=0) within an image. So far, I've set up a system with Javascript + Canvas that displays the image and starts a floodfill-like operation when I click inside the transparent rectangle in the image. It correct...

String searching algorithms

For the two string searching algorithms: KMP and suffix tree, which is preferred in which cases? Give some practical examples. ...

Bezier Algoritms - an algorithm for inserting points

I'm looking for an algorithm to insert a new control point on a bezier curve, without deforming: did anybody knows a library or reference for bezier algorithms (insertion, optimize, de Casteljau ...) ...

C++ priority queue structure used ?

While searching for some functions in C++ STL documentation I read that push and pop for priority queues needs constant time. http://www.cplusplus.com/reference/stl/priority_queue/push/ "Constant (in the priority_queue). Although notice that push_heap operates in logarithmic time." My question is what kind of data structure is used...

Efficiently storing a list of prime numbers

This article says: Every prime number can be expressed as 30k±1, 30k±7, 30k±11, or 30k±13 for some k. That means we can use eight bits per thirty numbers to store all the primes; a million primes can be compressed to 33,334 bytes "That means we can use eight bits per thirty numbers to store all the primes" This "eigh...

reservoir sampling problem

This MSDN article proves the correctness of Reservoir Sampling algorithm as follows: Base case is trivial. For the k+1st case, the probability a given element i with position <= k is in R is s/k. The probability i is replaced is the probability k+1st element is chosen multiplied by i being chosen to be replaced, which is: s/(k+1) * 1...

Algorithm to find lenth of longest sequence of blanks in a given string

Looking for an algorithm to find the length of longest sequence of blanks in a given string examining as few characters as possible? Hint : Your program should become faster as the length of the sequence of blanks increases. I know the solution which is O(n).. But looking for more optimal solution ...

Is there a minimum spanning tree that does not contain the min/max weighted edge?

If we have an (arbitrary) connected undirected graph G, whose edges have distinct weights, does every MST of G contains the minimum weighted edge? is there an MST of G that does not contain the maximum weighted edge? Also, I'm more thankful if someone can give a hint of the key things one must keep in mind when dealing with such MST ...

How to generate all permutations of a string in PHP ?

I need an algorithm that return all possible combination of all characters in one string. I've tried: $langd = strlen($input); for($i = 0;$i < $langd; $i++){ $tempStrang = NULL; $tempStrang .= substr($input, $i, 1); for($j = $i+1, $k=0; $k < $langd; $k++, $j++){ if($j > $langd) $j = 0; $tempStrang .= substr($input, $...

How to convert closed bezier curves to Bitmaps?

I need an algorithm to convert a closed bezier curve (perhaps self-crossing) to a binary bitmap: 0 for inside pixels and 1 for outside. I'm writing a code that needs to implement some operations on bezier curves, could anybody give me some resources or tutorials about beziere? Wikipedia and others didn't say anything about optimization, ...

Backtracking: N Bishops Problem

This problem is driving me crazy... Place N bishops on NxN board in a way, where all squares would be occupied or attacked with at least one of them. Could anyone help me out with an algorithm for solving this problem? ...

naive bayesian spam filter question

Hi guys, I am planning to implement spam filter using Naive Bayesian classification model. Online I see a lot of info on Naive Bayesian classification, but the problem is its a lot of mathematical stuff, than clearly stating how its done. And the problem is I am more of a programmer than a mathematician (yes I had learnt Probability a...

Optimally reducing maximum flow

Given a parameter k, I'm trying to delete k edges from a directed graph such that the maximum flow is reduced by as much as possible. The graph has a source s and a sink t, and the capacity of each edge is one. The graph may or may not contain cycles. My proposed solution would be to first perform a topological sorting on the graph, usi...

algorithm optimization: returning object and sub-objects from single SQL statement in PHP

I have an object oriented PHP application. I have a simple hierarchy stored in an SQL table (Chapters and Authors that can be assigned to a chapter). I wrote the following method to fetch the chapters and the authors in a single query and then loop through the result, figuring out which rows belong to the same chapter and creating bot...

Algorithm for dynamic combinations

My code has a list called INPUTS, that contains a dynamic number of lists, let's call them A, B, C, .. N. These lists contain a dynamic number of Events I would like to call a function with each combination of Events. To illustrate with an example: INPUTS: A(0,1,2), B(0,1), C(0,1,2,3) I need to call my function this many times for ea...

What is better, a STL list or a STL Map for 20 entries, considering order of insertion is as important as the search speed.

I have the following scenario.The implementation is required for a real time application. 1)I need to store at max 20 entries in a container(STL Map, STL List etc). 2)If a new entry comes and 20 entries are already present i have to overwrite the oldest entry with the new entry. Considering point 2, i feel if the container is full (Max...