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)

13
votes
2answers
1k views

How did Strassen come up with his matrix multiplication method?

The famous Strassen's matrix multiplication algorithm is a real treat for us, as it reduces the time complexity from the traditional O(n3) to O(n2.8). But of all the resources I have gone through, ...
13
votes
4answers
2k views

Pattern for algorithm that outputs an explanation of how it gets to a solution when needed

The following scenario happened to me several times. I programmed a algorithm that solves a certain problem. It works fine and finds the correct solutions. Now, I want to have an option to tell the ...
12
votes
2answers
4k 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 ...
12
votes
2answers
2k views

Converting a bounded knapsack problem to 0/1 knapsack problem

I ran across a problem where goal was to use dynamic programming (instead of other approaches). There is a distance to be spanned, and a set of cables of different lengths. What is the minimum number ...
12
votes
5answers
673 views

Programmaticaly finding the Landau notation (Big O or Theta notation) of an algorithm?

I'm used to search for the Landau (Big O, Theta...) notation of my algorithms by hand to make sure they are as optimized as they can be, but when the functions are getting really big and complex, it's ...
11
votes
3answers
2k views

How to implement a Weighted shuffle

I recently wrote some code that I thought very inefficient, but since it included only a few values, I accepted it. However, I'm still interested at a better algorithm for the following: A list of ...
8
votes
5answers
2k views

Algorithm for flattening overlapping ranges

I am looking for a nice way of flattening (splitting) a list of potentially-overlapping numeric ranges. The problem is very similar to that of this question: Fastest way to split overlapping date ...
17
votes
4answers
5k views

Is this XOR value swap algorithm still in use or useful

When I first started working a mainframe assembler programmer showed me how they swap to values without using the traditional algorithm of: a = 0xBABE b = 0xFADE temp = a a = b b = temp What they ...
16
votes
3answers
12k views

Why isn't Radix Sort used more often?

It's stable and has a time complexity of O(n). It should be faster than algorithms like Quicksort and Mergesort, yet I hardly ever see it used.
13
votes
10answers
1k views

Find out whose turn it is to buy the croissants, accounting for possible absences

A team has decided that every morning someone should bring croissants for everybody. It shouldn't be the same person every time, so there should be a system to determine whose turn it is next. The ...
9
votes
2answers
3k views

B Tree compared to an R tree - Isn't it just a bunch of linked lists linked together?

I'm pretty familiar with a B Tree, mainly having to keep the databases well fed with electricity, air conditioning, and harddrive space. I associate with a double (doubl[ie,ey]?) linked list. Today, ...
8
votes
7answers
602 views

Refactoring While Programming

When posed with a problem, particularly when it is complicated in nature, I try to take some time to think about the approach I am going to take to solve the problem. Despite this, what often happens ...
0
votes
3answers
354 views

How to convert this recursive problem to iterative? Line Simplification algorithm fails to run due to Maximum Recursion Depth being hit

I am implementing the Douglas, Peucker's Line Simplification algorithm in Python. I started with this implementation. However, it fails to run in Python due to Maximum Recursion Depth being hit. How ...
0
votes
1answer
286 views

What data structure can I use to implement a double ended priority queue with log(n) insertion and find?

How can I implement a double ended priority queue with O(log(n)) complexity of insertion, find min and find max operations? I was thinking of using a red black tree, but it is a little bit ...
12
votes
5answers
1k views

How to do TDD for something with many permutations?

When creating a system like an AI, which can take many different paths very quickly, or really any algorithm that has several different inputs, the possible result set can contain a large number of ...
6
votes
5answers
316 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 cat-->cot-->dot-...
6
votes
2answers
665 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 ...
6
votes
5answers
2k views

How do I go about data deduplication at scale?

I need to develop, or at least conceptualize a module that does efficient data deduplication. Say we have millions of data records already. Insertion of another 100 mn records, making sure that there ...
5
votes
3answers
544 views

Algorithm to pick user

I need an algorithm for picking a user. Users are identified by letter {A, B, C, ...} and are ranked by number {1, 2, 3, ...}. Rank is the degree of likelihood to be picked, so a rank 2 user is ...
4
votes
4answers
463 views

Building a route creator

Ok, already up front, I'm going to tell you, that this is a bonus task for Data structure course I'm taking. That should take care of all the questions whether or not this is for a homework. Route ...
4
votes
3answers
2k views

Basic premise on counting sort. How is k related to to Big Oh?

I am reading (Cormen) on counting sort. I understand the structure of the algorithm but the statement: In practice, we usually use counting sort when we have k = O(n), in which case the ...
3
votes
3answers
420 views

“Read user input”: Could it be a step of an algorithm?

Based on this definition of algorithm from Wikipedia: In mathematics and computer science, an algorithm is a self-contained step-by-step set of operations to be performed. Algorithms exist that ...
2
votes
2answers
227 views

What kind of transform is this?

I have a function that linearly "remaps" a value from a given interval to an other interval? The function remaps a value from a given interval [oldMin, oldMax] to another interval [newMin, newMax] ...
2
votes
1answer
71 views

Caching in '3D' - data-structures and octree recursion - hrrm!

The Situation: I have 68GB of data that is conceptually realized as a 3D matrix of 8-bit values with dimension 4096*4096*4096. I need to access multiple sections of this data for processing in a ...
2
votes
2answers
518 views

Mutual exclusion over network - pattern?

I want to do the following: I have a number of computers. On each computer a programm will run. There is no centralized server. The program can choose by defined criteria to give another computer ...
2
votes
1answer
673 views

Algorithm to update priority ordered list where changing priority of an item is expensive

I am working against an API where I can add and update items in a list that is ordered by a priority field I can set (which need not be contiguous but must be a positive integer). Updating a list ...
1
vote
1answer
79 views

Clairvoyance in caching - optimal strategies?

This question relates to the question here, but I'll generalise it so that you can answer effectively without reading all of that. Context: Imagine you had a large set of data greater than your ...
1
vote
3answers
745 views

Is there an algorithm to determine the amount of work needed to keep workers busy?

I wrote a multi-threaded program that randomly generates strings, and after generating, checks to see if the string contains a certain value. Namely, StringGenerator and StringChecker. What I'm trying ...
1
vote
1answer
314 views

How to count sort comparison

When it is said that this sort has M number of comparisons what does it mean? As an example: procedure bubbleSort( A : list of sortable items ) n = length(A) repeat swapped = false ...
9
votes
3answers
5k views

Is there a known algorithm for scheduling tournament matchups?

Just wondering if there is a tournament scheduling algorithm already out there that I could use or even adapt slightly. Here are my requirements: A variable number of opponents belonging to a ...
6
votes
4answers
356 views

How to convert the following node evaluation procedure to a non recursive solution?

I have the following recursive method. It evaluates a node (that represent a logical expression), using deep first search traversal : EvaluateNode(Node node) { bool result; switch(node.Type) ...
5
votes
3answers
5k views

Why is mergesort O(log n)?

Mergesort is a divide and conquer algorithm and is O(log n) because the input is repeatedly halved. But shouldn't it be O(n) because even though the input is halved each loop, each input item needs to ...
5
votes
1answer
1k views

What is the difference between Quantum annealing and simulated annealing?

In both algorithms objective functions, that will be executed with non quantum computers, are used. Both algorithms are methods for finding the global minimum of a given objective function. From ...
4
votes
3answers
539 views

Is it better to use a switch statement or database to look through 5,000 to 10,000 instances?

I have some JSON data in this format (5,000 instances for now): {"id":"123456","icon":"icon.png","caseName":"name of case"} I am allowing the user to search for the name of the case and then return ...
4
votes
2answers
695 views

How much logic can be put into an object-pooling factory class before it does more harm than good?

The main language I'm interested in doing object pooling in is AS3, which is known to need it in many cases. In the past I've always made a brand new factory class for every type I was going to try ...
4
votes
2answers
526 views

Why hill climbing is called anytime algorithm?

From wikipedia, Anytime algorithm In computer science an anytime algorithm is an algorithm that can return a valid solution to a problem even if it's interrupted at any time before it ends. ...
3
votes
2answers
1k views

Which of these two shuffle algorithms is more random?

Which of below two shuffle algorithms (shuffle1 and shuffle2) is more random? public final class Shuffle { private static Random random; public static void shuffle1(final Object[] array) { ...
3
votes
1answer
342 views

What technology/algorithm should be used to abstract meaning or keywords from a passage of text?

Hi and thanks for looking! Background I have a project wherein I need to abstract meaning from a passage of text to determine what the text is seeking and then match that text to a list of search ...
3
votes
2answers
1k views

Product classifying algorithm - text classification - C# - algorithm suggestions

Alright people. Finally with the help of stackoverflow community i have gathered 20 commercial product selling websites product pages with the following features Product URL Product Price Product ...
2
votes
2answers
450 views

Graph traversal and filtering in indoor navigation and path finding

Which of the following options take less processing time/is less expensive in a graph traversal algorithm for a (indoor)navigation system? a) To produce all possible paths between start and ...
2
votes
1answer
360 views

Why create a Huffman tree per character instead of a Node?

For a school assignment we're supposed to make a Java implementation of a compressor/decompresser using Huffman's algorithm. I've been reading a bit about it, specially this C++ tutorial: http://www....
2
votes
1answer
415 views

Asymptotic running time of for-loops

I have this question which I need answered: What is the asymptotic running time for the following piece of code? if (N < 1000) for (int i = 0; i < N; i++) for (int j = 0; j < N; j++...
2
votes
4answers
4k views

Complexity in nested loops

Foreword: In this post, I will make the common confusion between O(n) and Theta(n) as complexity notations. I will write pseudo-code to talk about algorithms, using whatever notation I find to my ...
2
votes
1answer
374 views

Most efficient way of finding entities in a grid?

I'm working on my first game; a tower defense. So far It's coming along nicely. The only issue I am having (so far) is I can't figure out a way to effciently discover if an entity has entered a towers ...
2
votes
1answer
512 views

Closest location - Heapify or Build-heap

So lets say we have a set of gps data points and your current location. If asked to give the closest point to your current location we can utilize a heap with the distance being the key. Now if we ...
1
vote
4answers
889 views

List comparing techniques for faster performance

I need to cross names from two lists, and find all occurrences of one name in the other. The lists are too big, one have 50k elements and the other 400k. For a small list I would use two foreach ...
0
votes
1answer
395 views

Designing online exam

I need to design an online exam server for an exam like GRE in which question difficulty increases if you answer correctly and decreases if you answer wrong. Questions are multiple choice ...
0
votes
3answers
658 views

Abstraction in algorithms

I asked some questions about algorithms, and some replied they are abstract concepts, however I don't know what abstraction means for algorithms or how it applies. For objects, I know if we remove ...
0
votes
2answers
379 views

Randomized Hash function with no collisions

Related to the question Which hashing algorithm is best for uniqueness and speed? Is there a way to create a hash function, or find one, whose hash length depends completely on the input length, has ...
0
votes
3answers
728 views

How to create single integer index value based on two integers where first is unlimited?

I have table data containing an integer value X ranging from 1.... unknown, and an integer value Y ranging from 1..9 The data need to be presented in order 'X then Y'. For one visual component I can ...