First, I’ll show you a recursive version. typedef std::vector<int> Vi; typedef std::vector<Vi> Vvi; // recursive algorithm to to produce cart. prod. // At any given moment, “me” points to some Vi in the middle of the // input data set. // for int i in *me: // add i to current result // recurse on … Read more
A die (half a pair of dice) is handy for observing the 24 different orientations, and can suggest operation sequences to generate them. You will see that any of six faces can be uppermost, and the sides below can be rotated into four different cardinal directions. Let us denote two operations: “turn” and “roll”, where … Read more
Another way of solving this is using Quickselect. This should give you a total average time complexity of O(n). Consider this: Find the kth largest number x using Quickselect (O(n)) Iterate through the array again (or just through the right-side partition) (O(n)) and save all elements ≥ x Return your saved elements (If there are … Read more
You could always just use Data.Sequence. Alternatively, a well-known implementation of a purely functional queue is to use two lists. One for enqueue and another for dequeue. Enqueue would simply cons with the enqueue list. Dequeue takes the head of the dequeue list. When the dequeue list is shorter than the enqueue list, refill it … Read more
I am sorry to disagree with the answer of Peter Walser. Solving the equations gives on my desk: u = ((bs.y – as.y) * bd.x – (bs.x – as.x) * bd.y) / (bd.x * ad.y – bd.y * ad.x) v = ((bs.y – as.y) * ad.x – (bs.x – as.x) * ad.y) / (bd.x * … Read more
Array.Sort() chooses one of three sorting algorithm, depending on the size of the input: If the size is fewer than 16 elements, it uses an insertion sort algorithm. If the size exceeds 2 * log^N, where N is the range of the input array, it uses a Heap Sort algorithm. Otherwise, it uses a Quicksort … Read more
Here’s a great article that should help you build your algorithm http://www.codeproject.com/KB/datetime/christianholidays.aspx Based on this example, you should be able to write: DateTime goodFriday = EasterSunday(DateTime.Now.Year).AddDays(-2); Full Example: public static DateTime EasterSunday(int year) { int day = 0; int month = 0; int g = year % 19; int c = year / 100; int … Read more
An O(ND) Difference Algorithm and its Variations (1986, Eugene W. Myers) is a fantastic paper and you may want to start there. It includes pseudo-code and a nice visualization of the graph traversals involved in doing the diff. Section 4 of the paper introduces some refinements to the algorithm that make it very effective. Successfully … Read more
I learned that depth and height are properties of a node: The depth of a node is the number of edges from the node to the tree’s root node.A root node will have a depth of 0. The height of a node is the number of edges on the longest path from the node to … Read more
alt text http://imagebin.ca/img/yhFOHb.png Diagram After you find intersection of lines L1:Ax+By=C and L2:ax+by=c i.e. point A(x1,y1). Define two more lines y = ceil(y1) and y = floor(y1) parallel to X-axis and find their intersection with L1 and L2 i.e. Points B(x2,y2) and C(x3,y3). Then point you require is D or E whichever is closer to … Read more