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)

-3
votes
4answers
88 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
92 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
133 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 ...
-5
votes
1answer
34 views

Proving that each element in reservoir have equal probability of been selected in reservoir sampling? [on hold]

Here is the proof After the (i-1)th round, let us assume, the probability of a number being in the reservoir array is k/(i-1). Since the probability of the number being replaced in the ith round is ...
-1
votes
0answers
33 views

Detecting similar sets

I have a set S consisting of N sets, each containing 2 or more numbers. E.g.: S={{1,2,6},{6,3,4,2},{6,2},{1,9,12},{7,8,13}}. So, here N=5 The question is: Determine which sets should be grouped ...
0
votes
1answer
24 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
135 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
0answers
36 views

Algorithms with natural language [closed]

I am building a web app where people can post their problems in 140 character length and the most common problem will be outputted in a list. To determent the most common problem, the app must match ...
3
votes
3answers
123 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 ...
-1
votes
0answers
25 views

algorithm to find lowest-weighted sub graph [closed]

It's a question I read it in a book but I couldn't solve it. Give an algorithm to find the lowest-weighted sub graph that maybe its edge weights lower than zero. algorithm should be in O(E logV)
-2
votes
0answers
24 views

Persist and sync custom sorting information [closed]

Assume a task app like asana with multiple client apps and the data must be synced across multiple systems. I have a list of 'tasks' and they can be custom sorted. What is the optimum way for me to ...
2
votes
0answers
161 views

What AI algorithm should I use to develop an automatic personal scheduler? [on hold]

In a project that I'm doing for my Artificial Intelligence course, I'm developing a software for automatic personal scheduling. The user tells the software what tasks he has to perform (along with ...
2
votes
2answers
183 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
145 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 ...
0
votes
0answers
30 views

Trouble with a heightmap adjusting algorithm [migrated]

I have a 2D grid of integers. The user can pick any location and increase or decrease its number by one. The algorithm should adjust all eight adjacent locations so there is no more than a difference ...
1
vote
1answer
110 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
votes
0answers
56 views

How to apply Alpha-Beta pruning to a game tree? (Algorithms Theory)

I'm studying for an AI exam, and having trouble working out this question on Alpha Beta pruning. I can answer on the effectiveness of the pruning method and the rules involved in the pruning process, ...
0
votes
0answers
103 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
320 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
229 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
132 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
242 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
93 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 ...
-1
votes
1answer
68 views

Build odd and even hanoi tower [closed]

I've got problem with hanoi tower. I know how to build normal hanoi tower, it's simple: void solveTowers(char src, char dst, char mid, int n) { if (n == 0) { return; } ...
4
votes
1answer
114 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
27 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
165 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. ...
1
vote
2answers
77 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) ...
3
votes
0answers
88 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
208 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
151 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
157 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
78 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
120 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 ...
2
votes
2answers
88 views

MaxHeap-like data structure supporting max AND min, also decrease-key (yes decrease-key)

For the purpose of implementing an optimization algorithm (finding the minimum of a multivariate function) I want to create a data structure that supports the following operations: load from array ...
0
votes
3answers
57 views

Algorithm to generate parallel path inside polygon

A path is defined as a list of 2D points (x,y) (and may be open or closed). Given a path p, what is an algorithm which generates a path p' which is "inside" p and at constant offset to p i.e. each ...
-2
votes
1answer
66 views

Pairing 40 people over 20 days such that no pair is the same twice or more [duplicate]

I'm trying to figure out what algorithm / method I can use to figure out how to pair people together such that the pairs aren't repeated i.e. if a unique individual is denoted by Px where x is their ...
2
votes
3answers
208 views

Close to knapsack problem?

I think that I am trying to solve a problem somewhat similar to a knapsack problem. I am not sure though. Please see the input given below and my solution. There are three types of items and 4 ...
2
votes
0answers
89 views

Smallest number of rectangles covering marked parts of grid

I have an N by N grid of cells, and certain blocks are marked: +--+---+---+---+ | | | | | | | x | x | | | | x | x | | | | | | | | | | | x | +--+---+---+---+ I would like to ...
1
vote
1answer
128 views

Increment or double problem

I have a problem with an assignment. In this assignment I have to create a program which needs to calculate how many different possibilities are there to get from number a to b. To get from a to b you ...
1
vote
0answers
56 views

Combining items from several lists with pagination

I am trying to come up with an algorithm for getting items for a news feed from several sources. There are multiple lists of data: S1, S2, ... Sn. Each of these lists has a certain known amount of ...
0
votes
1answer
46 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}, ...
1
vote
4answers
165 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
65 views

Translation algorithm - combinations to indices

I have a deck of 52 poker cards represented as array of int - [0, 1, ... 51]. There are 2.598.960 possible combinations of 5 cards. I can generate all combinations like this: #id #combination ...
0
votes
0answers
51 views

scrabble solving with maximum score

I was asked a question You are given a list of characters, a score associated with each character and a dictionary of valid words ( say normal English dictionary ). you have to form a word ...
0
votes
5answers
496 views

Fastest way to determine if a value is in a list?

I'm aware there may not be a good solution to this problem. I'm looking for a fast algorithm that determines whether or not a value (let's say an integer) exists in a set of values, however I need the ...
2
votes
3answers
194 views

fast, say O(log2(N)), sliding median algorithm

So I know how to do a fast O(log2(N)) sliding max or sliding min algorithm. Brookes: "Algorithms for Max and Min Filters with Improved Worst-Case Performance" IEEE TRANSACTIONS ON CIRCUITS AND ...
1
vote
1answer
179 views

Calculate Big-O for nested for loops

I found this nested loop to calculate the Big-O notation. for(i=0;i<n;i++) for(j=0;j<i*i;j++) for(k=0;k<j;k++) I got the time complexity for the algorithm with this polynomial ...
0
votes
0answers
14 views

Polling more recent / active items more frequently

I'm setting up a service that is meant to query, via a rate-limited API, a number of posts in real-time. Now, some of these posts can be several months old, and they should really only be queried, ...
0
votes
2answers
139 views

Is there a approximate string comparison function which is odd like mathematical functions are odd?

I say odd like a mathematical function, a mathematical function is odd if f(-x) = -f(x) I understand that comparing two strings may seem to have little to do with this, because the arguments cannot ...