# 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.

740 views

### Searching integer sequences

I have a fairly complex search problem that I've managed to reduce to the following description. I've been googling but haven't been able to find an algorithm that seems to fit my problem cleanly. In ...
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, ...
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 ...
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 ...
679 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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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.
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, ...
613 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 ...
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 ...
364 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 ...
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 ...
668 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 ...
320 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-...
3k 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 ...
549 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 ...
6k 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 ...
465 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 ...
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 ...
425 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 ...
529 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 ...
697 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 ...
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] ...
73 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 ...
325 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 ...
639 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 ...
80 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 ...
786 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 ...
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 ...
357 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) ...
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 ...
527 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. ...
544 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 ...
702 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 ...
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 ...
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 ...
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) { ...
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 ...
517 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 ...
417 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++...
377 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 ...
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....
460 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 ...
1k 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 ...