I have a database with 500,000 points in a 100 dimensional space, and I want to find the closest 2 points. How do I do it? Update: Space is Euclidean, Sorry. And thanks for all the answers. BTW this is not homework. ...
I am reviewing the Heap Sort Algorithm. I am wondering why it is implemented in binary tree? Could it use other tree? Such as a three-child-node tree? Or four? With more child count, though a little more comparison is needed for deletion operation. the height of the tree can be reduced much more. I believe the time cost should drop signi...
I'm looking for algorithms to find a "best" set of parameter values. The function in question has a lot of local minima and changes very quickly. To make matters even worse, testing a set of parameters is very slow - on the order of 1 minute - and I can't compute the gradient directly. Are there any well-known algorithms for this kind o...
In reference to fastest sort of fixed length 6 int array, I do not fully understand how this sorting network beats an algorithm like insertion sort. Form that question, here is a comparison of the number of CPU cycles taken to complete the sort : Linux 32 bits, gcc 4.4.1, Intel Core 2 Quad Q8300, -O2 Insertion Sort (Daniel S...
What are the applications of red-black trees? Is there any application where only RB Trees can be used and no other data structures? ...
How would you find the correct words in a long stream of characters? Input : "The revised report onthesyntactictheoriesofsequentialcontrolandstate" Google's Output: "The revised report on syntactic theories sequential controlandstate" (which is close enough considering the time that they produced the output) How do you think Goo...
I'm trying to write a bitmap editor for a mobile device (i.e. a limited version of Photoshop). The user's document consists of ~4 bitmaps around 1000x500 in size each. I want a robust and efficient undo/redo system that's as simple as possible. I'm aiming for about ~0.2s to undo or redo an edit. I'm looking for some feedback on my curre...
I am trying to solve this problem: http://stackoverflow.com/questions/268079/search-multiple-list-for-missing-entries. I used a multimap for duplication of keys. Here is my code: #include <iostream> #include <map> #include <list> #include <utility> using namespace std; int main(){ list<char>a; list<int> b; multimap<char,int...
I'm working on a 3D tile based game and I'm using AABB collision detection. For every cube that the player is intersecting, I find the axis along which the player is intersecting the cube the least, and push the player out of the cube along that axis. Depending on the order that the cubes are checked in, this can cause problems when sli...
What is the most efficient way to do this? There must be some better method other than brute force. ...
I came across a definition of Perfect matching: a set of edges that touches each node exactly once. However, i didnt really understand the definition. Can somebody give me an example of any such edge. Or may be point me towards some reference that does. I tried to google but it didnt give me any example. ...
while I am working at a project that requires simulate the movement of a fish, I put the fish in a 3D environment and I wish it could swim in a path looks like a real fish will do. I am wondering if there is any algorithm that can generate a quasi-random, fish-like path? best wishes,everyone. ...
Here's a brain teaser that's been on my mind for a few days. We have a sequence S of n elements. Each element is an integer in the range [0, n^2-1]. Describe a simple method for sorting S in O(n) time. Probably something obvious that I am just missing, but I'd appreciate any insight. ...
Input : A[4] = {0,4,-1,1000} - Actual Array P[4] = {1,0,3,2} - Order to be reshuffled Output: A[4] = {4,0,1000,-1} Condition : Don't use an additional array as memory. Can use an extra variable or two. Problem : I have the below program in C++, but this fails for certain inputs of array P. #include<iostream> using nam...
I'm trying to calculate the absolute deviation of a vector online, that is, as each item in the vector is received, without using the entire vector. The absolute deviation is the sum of the absolute difference between each item in a vector and the mean: I know that the variance of a vector can be calculated in such a manner. Va...
Hi, I'm basically new to coding for random results, but did some reading and tested out the javascript version of the Fisher-Yates algorithm (as seen on wikipedia), with an ordered list. I ended up adding code to make sure the array was shuffled differently than its initial order, and also calculated the percentage of how many objects ...
I'm looking for a data structure for string(UTF-8) indices that is highly optimized for range queries and space usage. Thanks! Elaboration: I have list of arbitrary length utf-8 strings that i need to index. I will be use only range queries. Example: I have strings - apple, ape, black, cool, dark. Query will be something like this -...
While answering to this question a debate began in comments about complexity of QuickSort. What I remember from my university time is that QuickSort is O(n^2) in worst case, O(n log(n)) in average case and O(n log(n)) (but with tighter bound) in best case. What I need is a correct mathematical explanation of the meaning of average compl...
The function a = 2 ^ b can quickly be calculated for any b by doing a = 1 << b. What about the other way round, getting the value of b for any given a? It should be relatively fast, so logs are out of the question. Anything that's not O(1) is also bad. I'd be happy with can't be done too if its simply not possible to do without logs or ...
Given a list of ranges ie: 1-3,5,6-4,31,9,19,10,25-20 how can i reduce it to 1-6,9-10,19-25,31 ? Here is what i've done so far, it seems a little bit complicated, so is there any simpler/clever method to do this. $in = '1-3,5,6-4,31,9,19,10,25-20'; // Explode the list in ranges $rs = explode(',', $in); $tmp = array(); // for each range...