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)

1
vote
2answers
105 views

Find the maximum number of pairs of numbers that are in a range, between two arrays

Lets say I have two arrays A and B A = {1,2,3} B = {12,11,67} and have max sum value S = 10 How many maximum number of unique pairs can be formed between the two arrays who's sum is less than or ...
14
votes
4answers
927 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 ...
5
votes
2answers
313 views

What does pi mean in this BFS algorithm pseudocode?

I have the following pseudocode for breadth-first search algorithm BFS(G,s) 1 for each vertex u ∈ V(G) \ {s} 2 color[u] = white 3 d[u] = ∞ 4 π[u] = nil 5 color[s] = gray 6 d[s] = 0 ...
1
vote
0answers
75 views

Choose a number of arrays which have the smallest cardinal number when unified

Say we have multiple arrays: var a := [1, 2, 3] var b := [2, 3, 4, 5] var c := [1, 3, 4, 6] var d := [1, 2, 5] We want to find the three arrays with the smallest cardinal number when the three ...
7
votes
1answer
213 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 ...
2
votes
2answers
103 views

Shape-Checking algorithm

I normally have a very intuitive approach to an efficient algorithm. In essence, I know what the bottleneck is, and how I can improve the algorithm. However, I'm now stuck and I am in the need of some ...
2
votes
3answers
63 views

Find all circles that cover one point

I'm not sure if I've been searching using the wrong keywords, but I've tried so many different ways of wording this and I can't find a relevant answer. Basically, given a set of circles defined by ...
6
votes
1answer
371 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
57 views

Need semi-efficient algorithm for 3-dimensional increasing sequence

I have a set of puzzle challenges for a prototype jigsaw puzzle kit, similar to commercial products offered by Thinkfun and Popular Playthings. I have a candidate list of 300 puzzle challenges and ...
3
votes
1answer
92 views

Algorithm to compute k-permutation without repeating and no duplicates

I have a set of integers, for example 1..20 and I want to get all possible combinations of that set drawing 5 numbers. So each combination has 5 numbers from that set of integers. But I don't want ...
1
vote
2answers
65 views

Given an array of n bits, how to generate every permutation with i 1's and n-i 0's?

It's simple enough to brute force a collection of strings and then filter for every occurrence with the required count of 1's. As n increases the number of possible permutations becomes very large, ...
2
votes
1answer
71 views

Best-matching comparative values using all items in array

I have two arrays of objects (items) in the exact same format. Each item represents a wager, and each array represents one of two outcomes for that wager (ex: Team A vs Team B). Both arrays look ...
3
votes
3answers
108 views

Find a line that is closest to scattered points

I came across the below interview question on Glassdoor: A scatter graph of points on a page, draw a horizontal line across the page such the the perpendicular y distance to the line from all ...
1
vote
0answers
79 views

Reversing dithering algorithms?

I was trying to make an implementation of the Floyd-Steinberg dithering algorithm in Python, and I was wondering, since Bitmaps files store their data starting from the bottom-left corner, would it be ...
18
votes
5answers
4k views

Advantage in being the first to copyleft a new algorithm? [closed]

Say I have created a new (DSP) algorithm. Will I have some advantage if I open source the algorithm under copyleft licence (GPL etc.)? From what I know about licensing this should lock people out from ...
2
votes
0answers
29 views

Project a piece of image cut by N-vertex shape to a different N-vertex shape

I have an N-vertex shape that I cut out from an image, and I want to project it onto another shape with the same amount of vertices, but different. So, the image will get changed inside the ...
0
votes
4answers
116 views

Pick highest score sum, but at least X from each region

Can you think of a solution to the following seemingly simple algorithmic problem? I am given a list of data points with scores and regions they belong to: [(9, A), (8, B), (7, A), (3, C), ...]. ...
0
votes
1answer
85 views

Algorithm to find groups of common relations

I have a very large dataset with two columns of interest: Name and Cousin. Each row has a unique name and each name has a cousin. The data is mutually inclusive, so the cousin's name will also ...
6
votes
2answers
140 views

Algorithm for comparing hundreds of similar, but not identical documents

I have seen similar questions about text comparison, but none on such a large scale. I have a client with two sets of recordings of speeches, 250 and 550 recordings each. Each of the recordings in ...
1
vote
2answers
60 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 ...
0
votes
1answer
72 views

How can I map a number of points of a polygon to matching points of a larger rectangle?

Suppose I have 2D polygon image and a larger 2D rectangle image and that I have a collection of points for each that I want to align. For Example the polygon has point collection: [PA(a, b), PB(c, ...
0
votes
3answers
172 views

Best algorithm to determine whether two arrays can be the same in a circular queue

I'm trying to figure out an efficient way to determine whether two distinct arrays of the same size can be shifted to form the same circular queue. For example: Array1 = ['A','B','C','D'] Array2 = ...
0
votes
1answer
61 views

hashing algorithm to check inclusion in a set

The problem I am trying to solve is to validate if a username is already used before allowing an admin user to create a new user with that username. Currently I am doing an ajax request to check if ...
0
votes
0answers
36 views

Algorithms for Academic Auditing?

I am trying to come up with an algorithm to perform academic auditing for college students. I never took an Algorithm course, any help is appreciated. Input: Degree requirements, Additional program ...
2
votes
0answers
33 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 ...
-3
votes
4answers
120 views

Time complexity of this loop [duplicate]

Is the time complexity for this loop O(n) or O(log n)? for(i=0;i<n/2;i++){} I am thinking, the time is proportional with the input size.
2
votes
2answers
132 views

“Hand written” recursive descent parser with “catch all” rule

I'm trying to write a (scannerless) recursive descent parser with a "catch all" rule for the following "Mustache template" grammar (simplified here): content : (variable_tag | section_tag | ...
3
votes
3answers
162 views

What is the most efficient way to find a set of locations within a radius of a certain point?

Imagine a dataset of all the restaurants in the US (similar to Yelp, etc), how would you return a set of restaurants within a certain range of a particular zip code. (Assuming you have already a ...
0
votes
3answers
91 views

Avoid numeric errors in Naive Bayes method

I am implementing the Naive Bayes method with Gaussian distribution. The problem that I have is that the variance used on the Gaussian curve (calculated from a training set) is REALLY small. They ...
5
votes
1answer
259 views

Kth selection routine - Floyd Algorithm 489

I have recently come across a promising Kth selection routine that reportedly outperforms quickselect the Floyd, Rivest Select routine. This Wikipedia article provides a pseudocode version which I ...
4
votes
3answers
148 views

How to determine if set of ordered coordinates form a simple curve?

I hope it is the right place to ask this. I wasn't sure if it belongs to Stack Overflow or Computer Science. Eventually this seemed more suitable. Anyway, some background first: A closed curve, is ...
2
votes
2answers
199 views

How to iterate between these elements

I have an array of elements: int[] elem = new int[] {A, B, C}; I need to calculate the sum of ALL the combinations of those elements, where only some of the elements can be optionally selected. I ...
0
votes
1answer
210 views

I need a data structure for a card game

I am programming a card game in java, and unsure what data structure I should use for the player's hand. I considered using an array, with one integer to traverse the array and another integer to ...
1
vote
1answer
126 views

Big O notation of randomness

I was thinking about inefficient algorithms based on randomness and wondered how to categorise them. For instance. Say you wanted to generate all the numbers from 1 to N in a random order but only ...
1
vote
2answers
259 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
331 views

What algorithm should I use for a lot of if else(s)?

I have to implement a lot of if else statements and I'm thinking of using Decision Tree but I'm not sure if it's going to be the right algorithm. I don't want to insert a piece of html code based on ...
4
votes
3answers
249 views

GPLing an implementation of a patented algorithm

TL;DR: Can you publicly release your own implementation of a patented algorithm as a free research tool for others, under the GPL, when you do not hold the patent (but will happily give clear and ...
0
votes
0answers
140 views

Is this a Bin Packing Problem?

Let us consider we have B Bags and each Bag has some number of Items. The problem is to distribute Bags of Items uniformly across as minimum number of Bins as possible. However, there are two ...
1
vote
2answers
253 views

Looking for the name of an algorithm (or technique)

I am searching for an article on the net which I can't find anymore. It was describing an algorithm to rank web pages. I am trying to remember the name of this algorithm or technique. The principle ...
0
votes
1answer
104 views

Decision tree (?) reduction

I need to check certain conditions (of size n) on an object and perform one of several options available (size m) based on the result. Seems to me it fits a tree. Now. The tree is quite large and I ...
4
votes
1answer
128 views

Algorithm to find whether there is a path (any path) above length X between two vertices

We all know how to find the shortest path between two vertices, but what if I just want to know the answer to this question - is there a path, (any path), between vertex A and B of length larger than ...
0
votes
0answers
39 views

Best and simplest way to implement a double ended priority queue with insertion and find operations lg(n)?

What is the best way to implement a double ended priority queue with O(log(n)) complexity of insertion, find min and find max operations? I was thinking to implement a red black tree, but it is a ...
5
votes
1answer
246 views

Python rectangle packing

I'm working on a project which involves packing multiple rectangles in a larger rectangle(the bounding box). Rectangles can't overlap with each other or with the boundaries of the bounding box. ...
2
votes
2answers
83 views

Efficient range search for pair of numbers

Assume we have large list of pairs: struct {x: double, y: double} pair; vector<pair> What is the most effective way to find all pairs where (x1 < x < x2) AND (y1 < y < y2)? O(n) ...
5
votes
1answer
130 views

Graph visualization algorithm

I need a 2d or 3d graph visualization algorithm by which adding/removing a node or a relationship does not have a butterfly effect on the positions of other nodes. (We are talking about a directed ...
5
votes
2answers
230 views

Algorithms for allocating N balls into M boxes

Every box has at least no balls and at most N balls. Of course the total number of balls in M boxes must equal to N. For each allocation, I calculated a value based on the allocation: ...
-2
votes
2answers
170 views

Some people told me that finding all prime factors of a number is an unsolvable problem. Is that real? [closed]

I'm a beginner, so I spent a lot of time trying to solve the 3rd problem on projecteuler.net, which is: "Find the largest prime factor of 600851475143" Now, I imagined it would be more useful if I ...
3
votes
2answers
210 views

Is it possible to speed up a hash table by using binary search trees for separate chaining?

I want to implement a Hash Table using Binary Search Trees to reduce the search complexity in the Separate Chaining process from O(n) (using linked list) to O(log n) (using BST). Can this be done, and ...
1
vote
1answer
122 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 ...
0
votes
2answers
153 views

Is studying algorithms important for game development? [closed]

I am fairly new in the programming world, I have a 1-year experience and I learned by watching online courses, and I made few iOS apps. Now I am moving into game development and I already ...