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.

learn more… | top users | synonyms (1)

0
votes
0answers
53 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 ...
2
votes
1answer
589 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(...). ...
0
votes
1answer
97 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 ...
2
votes
3answers
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 ...
1
vote
1answer
350 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 ...
1
vote
2answers
84 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 ...
1
vote
1answer
172 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 ...
2
votes
2answers
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 ...
3
votes
2answers
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. ...
2
votes
1answer
78 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: ...
1
vote
0answers
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 ...
1
vote
1answer
98 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 ...
18
votes
1answer
3k 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 ...
2
votes
1answer
56 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 ...
5
votes
2answers
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 ...
1
vote
2answers
63 views

Advantage of non-deterministic staistical analysis?

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 ...
15
votes
4answers
945 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 ...
3
votes
1answer
125 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 ...
-3
votes
2answers
84 views

Integer Map Algorithm [closed]

For my project, I need to map integers so that inputting int X will output int Y where both X and Y are defined during runtime. I've used Dictionary<int,int> in .NET but its memory use is too ...
0
votes
1answer
120 views

How to sort fractions (small numbers)

We have 100 000 fractions: Let's consider following fractions. p/(2^q) such that 0 <= p,q <= 10 As you can see there are <= 10 * 10 different fractions, but we have 100 000 that we have to ...
1
vote
1answer
97 views

Algorithm to cut out and straighten rectangles from image

I am looking to write an algorithm to cut rectangular images and straighten them in a new image. The bigger concept is that I will be scanning a bunch of physical pictures (on a physical scanner). ...
4
votes
4answers
454 views

Why are return values from compare functions in many languages defined loosely?

Many languages define that compare functions should return ANY negative value, zero, or ANY positive value. Is there some reason that it shouldn't be clearly defined as -1 0 and 1? Does a wide range ...
2
votes
0answers
34 views

Optimizing trigram look ups with wildcards

I am working on creating a spell-checking service for Android (note: this is a platform- and language-neutral question) for Asturian, a minority Romance language. We're using hunspell as the base but ...
1
vote
2answers
271 views

Algorithm to detect if a word is spelled correctly

I am trying to develop a javascript spellchecker that doesn't use a dictionary, and can correctly, given a single word, detect if a word is spelled correctly or not. Right now, I just have a list of ...
0
votes
2answers
83 views

AABB collision algorithm with a condition

So I'm doing a 3D implementation of collision detection. Considering Boxes are oriented on the axis. They are rotatable but has to be orientated on the axis. Box A and Box B cannot go through each ...
2
votes
1answer
73 views

Seeds distribution algorithm with complexity better than O(n^3)?

I have included my approach and solution. My solution works fine, however, is unoptimized with O(n^3) complexity An NGO is running seed distribution program. It has limited quantity of varied quality ...
2
votes
2answers
125 views

Algorithm to solve this “treefarm” puzzle

How would I go about writing a program to solve this kind of puzzle: The green squares represent trees, and you have to plant them in such a way, so that: Trees do not touch each other at all (not ...
10
votes
9answers
2k views

Big O Question about an algorithm with (n^2 + n) / 2 growth rate

I'm asking this question because I am confused about one aspect regarding big O notation. I am using the book, Data Structures and Abstractions with Java by Frank Carrano. In the chapter on the ...
0
votes
4answers
265 views

Big-O of this algorithm?

How can I describe the growth function in terms of n for the following algorithm? What is the bounding function (the Big-O)? Is it O(n^3)? for(i = 0 to n - 1) { c = i + 1 for(j = c to n) ...
6
votes
5answers
214 views

Hamming Distance using a dictionary

First time poster. I'm currently programming a hamming distance program using a dictionary. So if we start with the word "cat" and we want to transform it into "dog", the sequence is ...
7
votes
4answers
3k views

Smallest lexicographical rotation of a string using suffix arrays in O(n)

I will quote the problem from ACM 2003: Consider a string of length n (1 <= n <= 100000). Determine its minimum lexicographic rotation. For example, the rotations of the string “alabala” ...
1
vote
3answers
424 views

How can I rank teams based off of head to head wins/losses

I'm trying to write an algorithm (specifically in Ruby) that will rank teams based on their record against each other. If a team A and team B have won the same amount of games against each other, then ...
3
votes
1answer
800 views

How can this deterministic linear time selection algorithm be linear?

I'm trying to understand the basic concepts of algorithms through the classes offered at Coursera (in bits and pieces), I came across the deterministic linear time selection algorithm that works as ...
5
votes
5answers
582 views

Win loss code that does not make 1-0 record better than someone like 20-3

ok, am just looking for a win loss code example. This can be for any language, just wanting the outline. Fairly new to programming, so dummy it up for me :) I can do (win-loss/total of win loss). ...
6
votes
1answer
389 views

Algorithm/data structure to answer “what recipes can I make with this set of ingredients?”

Formally, let s(U, Q) = {V | V ∈ U and V ⊆ Q} where U, Q, and V all represent sets, and U, more specifically, represents a set of sets. For the sake of example, U might be a set of the (sets of) ...
1
vote
1answer
122 views

What does it mean for an algorithm to converge?

I keep coming across this term when reading about reinforcement learning, for example in this sentence: If the problem is modelled with care, some Reinforcement Learning algorithms can converge to ...
0
votes
0answers
44 views

Final array after M updates on Segment Tree

I am stuck in a middle of a problem. I have made segment Tree of N elements and performed M updates through lazy propagation Now I need to store the final array (to some array B of size N) after all ...
25
votes
5answers
9k views

Return random `list` item by its `weight`

I have, for example, this table +-----------------+ | fruit | weight | +-----------------+ | apple | 4 | | orange | 2 | | lemon | 1 | +-----------------+ I need to return random ...
2
votes
1answer
44 views

Which algorithm to find the shortest (nodes count) path that encompasses all polygons inside a larger polygon?

Inside a large polygon (say the USA boundaries) I need to find the shortest path that will encompass smaller polygons (say the following cities: Kansas city, St Louis, Memphis, Oklahoma City) By ...
0
votes
0answers
57 views

Simple Path to Route Algorithm

I'm currently conducting research into subway paths, but stand in front of a problem, with no programming knowledge and an extremely short time-limit. Probably the question I am asking is trivial, ...
4
votes
1answer
100 views

Improve bisection method or alternate algorithm for efficient determination of text font size to fit in a box

I need to find the font size of a text that fits in a box. Given my current font size, I can get the bounding rectangle of the text. If I set some arbitrary min and max font size, I suppose I can ...
3
votes
3answers
2k views

Try to find a word in the dictionary that has most letters given

I recently came across an algorithm design problem that I'd like some help with: Given some letters, for example a,e,o,g,z,k,l,j,w,n and a dictionary of words. Find a word in the dictionary that ...
1
vote
0answers
101 views

Software Design, Generic Programming, Physical Devices, and Algorithms in C++ [closed]

I often have data that in some contexts I want to handle uniformly, but in other contexts I wish to differentiate it. For example, I could have a vector that is series of angles or a series of ...
0
votes
0answers
36 views

Approaches to combinatorial optimization problem

Problem I have the following combinatorial optimization problem: A set of applications need to be distributed among a set of nodes. Each node has a capacity and each application has a required ...
2
votes
2answers
172 views

Algorithm and data structure to match groups of users (1-5 each) into 2 balanced sets of 5 users

I'm building a matchmaking queueing service for a 5v5 team-based game. I have a large set of users that are grouped into unique lobbies comprised of 1-5 users each. Each user has an integer based ...
4
votes
1answer
185 views

Minimizing compression overhead in a simple compression algorithm

Note: this question has been re-written to simplify and generalize the problem. The original is available below. Suppose I created a simple compression scheme for lists of 2-digit numbers. It has 2 ...
12
votes
2answers
3k views

What is the relationship between data structures and algorithms? [closed]

I have been searching for a good online course in data structures but have found that Google also returns results for algorithms courses, which say stuff like: In this course you will learn ...
16
votes
2answers
11k views

How would you implement Google Search? [closed]

Supposed you were asked in an interview "How would you implement Google Search?" How would you answer such a question? There might be resources out there that explain how some pieces in Google are ...
3
votes
2answers
68 views

(Partially) Sorting a lazy-evaluated collection

So I'm trying to implement a lazy-evaluating data type (in PHP, though that shouldn't matter any) where you can queue up actions to take on a set of data. This data can come (theoretically) from any ...
4
votes
2answers
150 views

Algorithm to find the optimal trade route (negative cycle with lowest cost per edge in a digraph)

Given the following problem (a slightly simplified description of trading in the computer game Escape Velocity: Nova (system map)): Given a set of (solar) systems. Each system is connected by ...