which sorting algorithm is used for std::list's sort member function ?
Possible Duplicate: Which sorting algorithm is used by STLs list::sort()? Which sorting algorithm can be used for sorting std::list ? ...
algorithm
Algorithm for reflecting a point across a line
Given a point (x1, y1) and an equation for a line (y=mx+c), I need some pseudocode for determining the point (x2, y2) that is a reflection of the first point across the line. Spent about an hour trying to figure it out with no luck! See here for a visualization - http://www.analyzemath.com/Geometry/Reflection/Reflection.html ...
Covariance matrix computation
Input : random vector X=xi, i=1..n. vector of means for X=meanxi, i=1..n Output : covariance matrix Sigma (n*n). Computation : 1) find all cov(xi,xj)= 1/n * (xi-meanxi) * (xj-meanxj), i,j=1..n 2) Sigma(i,j)=cov(xi,xj), symmetric matrix. Is this algorithm correct and has no side-effects? ...
A data structure problem
Given a sequence of integers, there are a number of queries. Each query has a range [l, r], and you are to find the median of the given range [l, r] The number of queries can be as large as 100,000 The length of the sequence can be as large as 100,000 I wonder if there is any data structure can support such query My solution: I con...
Topological sort variant algorithm
I have a set of data on which I need to perform a topological sort, with a few assumptions and constraints, and I was wondering if anyone knew an existing, efficient algorithm that would be appropriate for this. The data relationships are known to form a DAG (so no cycles to worry about). An edge from A to B indicates that A depends on...
Analysis of Permutation Finder algorithm(pseudo code)
A SO post about generating all the permutations got me thinking about a few alternative approaches. I was thinking about using space/run-time trade offs and was wondering if people could critique this approach and possible hiccups while trying to implement it in C#. The steps goes as follows: Given a data-structure of homogeneous elem...
Should I be an algorithm developer, or java web frameworks type developer?
So - as I see it, there are really two kinds of developers. Those that do frameworks, web services, pretty-making front ends, etc etc. Then there are developers that write the algorithms that solve the problem. That is, unless the problem is "display this raw data in some meaningful way." In that case, the framework/web developer guy mig...
Best book with only programming exercises and solutions
I want to improve my programming skills for a future job interview (and for myself) and I am looking for some book or text that has only problems and solutions (in some general language like C or in pseudo code) that illustrate basic algorithms and data structures. Problems that I expect to find are for example: find sub string in a ...
Is there a Boyer-Moore string search and fast search and replace function and fast string count for Delphi 2010 String (UnicodeString) out there?
I need three fast-on-large-strings functions: fast search, fast search and replace, and fast count of substrings in a string. I have run into Boyer-Moore string searches in C++ and Python, but the only Delphi Boyer-Moore algorithm used to implement fast search and replace that I have found is part of the FastStrings by Peter Morris, fo...
What is the fastest way to sort 1 million integers when integers are from the range [1,100]?
Notes: I've thought about Radix sort, bucket sort, counting sort. Is there anyway to achieve big O(n)? ...
How to merge two sorted portions of same array in O(n) time and O(1) space
Possible Duplicates: How to sort in-place using the merge sort algorithm? Regarding in-place merge in an array Given an array of size N, which is divided into two sets of sorted integers(0 to P and P+1 to N-1). How would you sort this array using constant extra space (O(1)) and in O(n) time. For e.g A = {1,3,5,7,2,4,6,8}, h...
Tree traversal with corecursion
I'm trying to figure out corecursion in Clojure with nontrivial (i.e. not Fibonacci), but manageable, examples. Apparently it is possible to implement binary tree traversal with corecursion. Wikipedia has an example in Python which I am unable to understand. How can I implement it in Clojure? Let's say I'm looking for BFS, but it could ...
index many documents to enable queries that supports AND/OR operations
We have many documents that consists of words. What is most appropriate way to index the documents. A search query should support the AND/OR operations. The query runtime should be efficient as possible. Please describe the space required for the index. The documents contain words only(excluding AND/OR) and the query contains words and...
Inconsistent behaviour with Haskell
I was reading on perceptrons and trying to implement one in haskell. The algorithm seems to be working as far as I can test. I'm going to rewrite the code entirely at some point, but before doing so I thought of asking a few questions that have arosen while coding this. The neuron can be trained when returning the complete neuron. let n...
diameter of a huge graph
I have a huge graph that I would like to process using many machines. I had like to compute if the graph diameter is higher than 50. How would I split the data and I would I write a parallel algorithm that can calculate it? (the return value is boolean) The graph diameter is the greatest distance between any pair of vertices ...
How to make a controled "shuffle" order?
I have a set of quiz game questions in a sql database (javascript and sqlite actually). The questions all have a difficulty level from 1 to 5, 5 being hardest. Here is a simplified visualization of the data... +---------+--------------+ | id | difficulty | +---------+--------------+ | 1 | 1 | | 2 ...
solve a maze by using DFS, BFS, A*
I want to know the change in results when we use open maze or closed maze for the DFS, BFS, and A* search algorithms? Is there any big difference in the output like increase in number of expanded nodes, cost, etc.? ...
Sort a single linked list
How would you sort a single linked list. (the problem here is the single property + using LinkedList for sorting is harder than an array) I had like to see a pseudo code.. try to make it efficient as possible for both time and space. Thanks! ...
Randomly dividing a 2d complex enclosed region
First I will define: Region: big stuff manually created I want to divide. Zone: small stuff I want to generate. I have a map. The world map in fact. And I want to divide it into small zones. The size of the zones will be dependent on what region the zone is in. For instance very small for Europe (maybe Europe will have like 200 zones...
Search a sorted 2D matrix
M is a 2D matrix of integers (nXm) they are sorted in both row and column Write a function search(int s) that return the exact location of the number or Null. What would be the most efficient way to do so? ...