Tagged Questions

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning.

175 views

Shuffle/Randomize a collection without knowing the number of items?

Let's say I have a sequence of items of unknown length, n. I want to randomize the order of this sequence without having to go through the entire sequence. Are there any algorithms that can do this? ...
117 views

Work out which parcel deliveries we ship ourselves and which we outsource

Firstly, I hope I'm asking this in the right place. I work for a large online retailer in UK. We ship approaching 2000 orders each day and are growing very quickly. We currently use multiple delivery ...
205 views

Min weight feedback edge set with DFS?

Exercise from The Algorithm Design Manual 6-10. [4] Let G = (V,E) be an undirected graph. A set F ⊆ E of edges is called a feedback-edge set if every cycle of G has at least one edge in F. ...
138 views

Sorting a large number of unknown items with multiple stacks

Here is a problem I'm trying to solve for a personal project. I'm not exactly sure how best to even approach it. Problem: I have a single stack already populated with several thousands of unknown ...
181 views

Is there a better algorithm to distribute integer to X integers minimizing their difference?

Is there a better algorithm to distribute values from one source to X destinations minimizing their difference? I have some source integer. I need to know how much of that value I need to distribute ...
22 views

Segment sieve of Eratosthenes code [on hold]

I got this code to print prime number between m and n and while doing its dry run ,i observed that even if prime is not set to be 1 for composite 4 it gives same result int main(int argc, char** ...
1k views

Is it possible to efficiently store all possible phone numbers in memory?

Given the standard North American phone number format: (Area Code) Exchange - Subscriber, the set of possible numbers is about 6 billion. However, efficiently breaking down the nodes into the sections ...
59 views

Search algorithm on sequential data model

For sequential data models like LinkedList, search algorithms like linear-search and binary-search are well known. Are their any other search algorithms apart from these two, that work on sequential ...
63 views

inserting into priority queue. MIT c programming opencourseware [migrated]

Iam currently trying an exercise from the "practical programming in C" from MIT opencourseware. the exercise is on huffman coding. it is lab2 part 2 where Iam having an Issue. Primarily the ...
231 views

Fast fixed-size (256 bit) integer modulo/division

What is the fastest way to divide two 256-bit integers? They are represented as an array of 26-bit words, each stored in 32-bit integers. I have access to a 64-bit type if that's useful. It seems ...
141 views

Finding the closest n points to any arbitrary point in two dimensions (r-tree, quadtree, spatial index)

I have a distribution of two dimensional point objects. How is it possible to find the nearest N number of points to any given point without iterating over the entire collection of points (and only ...
63 views

Intersection of two arrays [closed]

While solving problem abcdef on spoj i came across this code for intersection of two sorted arrays Here is the link to problem http://www.spoj.com/problems/ABCDEF/ The code sort(s1.begin(), ...
113 views

How can I learn algorithms? [closed]

I just took a coding challenge on a popular coding challenge site which gives you a problem and a fixed amount of time to solve it. I've been writing software for around 10 years, good software for ...
86 views

Incorporating functions into a Shunting-Yard algorithm implementation

tl;dr What would be a simple way of incorporating functions into a Shunting-Yard algorithm implementation? If only expressions like function(arg1, arg2, arg3) were allowed (where function is some ...
551 views

Algorithm for calculating a bullet path to a target with max. 2 ricochets

Sorry for the poor title but I didn't have a better way to phrase it... So there's this amazing game by Nintendo (yes!) on Wii called WiiPlay. There're 9 minigames in it, and my favorite one is ...
89 views

Split multiple overlapping intervals to non overlapping intervals

currently I try to build an algorithm to split an array of overlapping intervals to a new array with non overlapping intervals. For example: Array of overlapping intervals: [ {0,7}, {8,12}, ...
132 views

Non-fixed-size Fenwick Tree implementation

I'm planning to implement a non-fixed-size Fenwick tree. That is, a Fenwick tree that allows interleaving range queries with adding/removing elements. All implementations and samples I've seen so far ...
3k views

When speaking, how can I say that the time complexity order of an algorithm is O(N log N)?

What term can I use to describe something with O(N log N) complexity? For example: O(1): Constant O(log N): Logarithmic O(N): Linear O(N log N): ?????? O(N2): Quadratic O(N3): Cubic
23 views

What is prerequisite for Algorithm and Data Structure Analysis and Designing [closed]

I want to learn Programming, So I want to start this learning program with studying of the Introduction to algorithms book. I'm familiar with C, C++ and ASM Language a little bit, but I can't write ...
582 views

Why would I care about the asymptotic growth of the lower bound of the worst case time/space?

In mathematics, there are notations for asymptotic lower bounds, upper bounds, and tight (within-a-constant-factor) bounds. When describing the growth of functions in general, it makes sense that all ...
295 views

Efficient algorithm for Virtual Machine(VM) Consolidation in Cloud

PROBLEM: We have N physical machines(PMs) each with ram Ri, cpu Ci and a set of currently scheduled VMs each with ram requirement ri and ci respectively Moving(Migrating) any VM from one PM to ...
95 views

Algorithm to go from infix notation to a tree

I've been trying to figure out an algorithm to go from an infix equation to a syntax tree, like so: (1+3)*4+5 + * 5 + 4 1 3 However, I don't just want it to handle operators, I ...
2k views

My algorithm that extracts the largest box that can be made from smaller boxes, is too slow

Imagine a cube based world (such as Minecraft, Trove, or Cube World) where everything is made up of identically sized cubes and all the cubes are of the same kind. The goal is to represent the world ...
25 views

Why do drawing applications use handles to connect lines to shapes? [migrated]

Most drawing programs that I know of (eg. Visio) give shapes handles in order to connect two shapes with a line. These handles allow lines to be "locked on" to the shape so if you move the shape, the ...
141 views

Merge directed acyclic graphs minimizing number of nodes

I have some DAGs (directed acylic graphs) and I want to merge them in order to minimize the number of nodes (we could say that every node has a cost, while edges are free). These four different DAGs ...
2k views

Is Pre-Order traversal same as Depth First Search?

It seems to me like pre-order traversal and DFS are same as in both the cases we traverse from root till the left branch and back to root and then to the right branch recursively. Could any please ...
4k views

TEA algorithm constant 0x9e3779b9 said to be derived from golden ratio, but the golden number is 1.618?

I'm trying to understand a constant 0x9e3779b9. What kind of data is this? It's not binary, not decimal, what is this? It's a constant used on the TEA algorithm. It says it's derived from the golden ...
22 views

My code compiles, executes, but crashes for certain inputs [migrated]

I am trying to get the length of longest common subsequence for two strings. It works for most of the inputs but it crashes for the input specified. The code is as follows: #include <cmath> ...
50 views

Calculating audio delay to eliminate echo in VoIP

In this issue, the microphone at point A records audio, compresses it, and sends it to the server at point B somewhere "in the cloud." The point B server then figures out what rooms the recorded ...
574 views

What is O(…) and how do I calculate it?

I've seen some questions here and on SO talking about the most efficient way to find or sort this or that. The questions usually talk about the efficiency of a certain algorithms in terms of O(...). ...
94 views

Bad idea to use the same test cases for multiple parts of a contiguous algorithm?

I'm working on an algorithm that's split up into multiple parts, each of which performs different tasks but is more or less separate from the others, by which I mean the only interaction between the ...
7k views

Why does a proportional controller have a steady state error?

I've read about feedback loops, how much this steady state error is for a given gain and what to do to remove this steady state error (add integral and/or derivative gains to the controller), but I ...
346 views

Assembly vs. algorithmic languages (like C, Algol, etc) [duplicate]

Usually, computer science papers describe algorithms in Algol-like pseudolanguage, similar to Pascal or even C/C++. But Donald Knuth uses his own assembly language (MMIX). Are there any good known ...
80 views

Multi-pattern matching

I have a given byte array in C and I need to match it against several byte arrays and return true if there is any match. I can make various memcmp's but I feel that it is very inefficient. Do you ...
152 views

Is the time complexity of a while loop with three pointers different than 3 nested for loops?

This program (written in ruby) finds the largest 3 numbers in an array (without sorting the array). It has a while loop with three pointers. My fist instinct, since there is only one loop is to say ...
180 views

How they design this algorithm? [closed]

I started taking the lessons from Codility. In the PDF about time complexity, at the end, the put an simple example: Problem: You are given an integer n. Count the total of 1 + 2 + . . . + n. The ...
3k views

What is the time complexity of the algorithm to check if a number is prime?

What is the time complexity of the algorithm to check if a number is prime? This is the algorithm : bool isPrime(int number){ if(number < 2) return false; if(number == 2) return true; if(number ...
168 views

Obstacle bypass in 2d environment

For this 2d grid (black square are not penetrable, white square are): I want to find path who permit to move an object to a start point (x:18, y:18) to a end point (x:1, y:1), square by square. ...
63 views

Precedence of function in Shunting-yard algorithm

I am working through the Shunting-yard algorithm, as described by wikipedia. The description of the algorithm when dealing with operators is as follows: If the token is an operator, o1, then: ...
46 views

clustering of strings with variable-length prefixes

I've got bunch of strings with variable-length prefixes (or postfixes - I can always revert them) as follows: 0155555555 523455555555 755555555 ... 87129999999999999 119999999999999 09119999999999999 ...
88 views

How to generate Generate Hash incorporating time stamp so it can be unhashed to get the timestamp when it was generated?

I want to create hash based on random id, That hash has to be valid for only 15 minutes. Is there a way to do that? I'm using this for form submission. If some unknown submitted form or some one ...
2k views

3d Packing algorithm for item's shipping

I've received a task to build a shipping estimative that suggests the best accomodation of goods on as few boxes as possible: There is a finite set of known retangular box sizes There are many ...
54 views

Looking for an Appropriate Search Algorithm

I am currently planning an upcoming project and am looking for an algorithm for searching a database. The search is as follows; There will be some specifically labelled criteria (or fields) and I ...
1k views

Writing recursive functions

I am having a lot of trouble writing recursive functions related to trees. I can't just use google for these functions as they are not general and I won't be able to use google in an exam setting! Is ...
60 views

I am working with a Java Library used for identifying the language of a given text. It relies on an n-gram analysis of the text to return a set of languages it might be and the "confidence" that it ...
937 views

Are Constant Time and Amortized Constant Time effectively considered equivalent?

I need to write a RandomQueue that allows for appends and random removal in Constant Time ( O(1) ). My first thought was to back it with some kind of Array (I chose an ArrayList), since arrays have ...
224 views

Fast indexing of k-combinations

I'm revisiting an old problem that I was working on some time ago. A typical scenario is "3 bits are set within an 8 bit integer", i.e. 00000111. All unique combinations with 3 set bits can easily ...
121 views

Finding the optimal root

I am trying to solve a quora hackathon challenge question. The question descrpition is as follows : For the purposes of this problem, suppose Quora has N questions, and question i (1≤i≤N) takes ...