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
1answer
118 views

problem on calculating Big O complexity

i have this function on which i have to calculate the time complexity with the Big O notation: public void print(ArrayList<String> operations, ArrayList<LinkedHashSet<String>> ...
-1
votes
0answers
33 views

Preference Matching Algorithm [migrated]

There's this side project I'm working on where I need to structure a solution to the following problem. I have two groups of people (clients). Group "A" intends to buy and group "B" intends to sell a ...
6
votes
1answer
339 views

How do I efficiently store all OpenStreetMap data in an indexed way?

I have a PBF file that contains the following information about a country: Nodes, each with their own longitude, latitude and properties; used to store points in a 2D space. Ways, each with their ...
1
vote
2answers
56 views

Adding a minimum rectangle overlap threshold

I have a function that works perfectly for detecting whether or not r1 overlaps with r2: boolean overlaps( Rectangle r1, Rectangle r2 ) { return r1.x < r2.x + r2.width && r1.x + ...
1
vote
3answers
65 views

Count unique visitors by group of visited places

I'm facing the problem of counting the unique visitors of groups of places. Here is the situation: I have visitors that can visit places. For example, that can be internet users visiting web pages, ...
6
votes
2answers
3k views

Which string search algorithm is actually the fastest?

I have been stuck for some time on which is the fastest string search algorithm, heard many opinions, but in the end I'm not sure. I have heard some people saying that the fastest algorithm is ...
0
votes
1answer
237 views

Algorithm to Copy data faster than windows default copy provider

I need an algorithm which can copy data(files/folder) from one place to another, faster than windows default copy/paste option. I'm working in vc++. Is there any algorithm by which I can do copy/paste ...
0
votes
0answers
35 views

How do I prove theta(log n)=o(log n)? [migrated]

I'm solving a question from CLRS where we need to prove that (ceil(lg lg n))! is polynomially bounded. Let g(n)=(ceil(lg lg n))! lg(g(n))=lg((ceil(lg lg n))!) =theta(ceil(lg lg n) * lg ...
0
votes
1answer
46 views

How to create a scoring system with time and correct answers for a game?

o create a scoring system with time and correct answers for a game? up vote 0 down vote favorite I have a small mobile quiz game, which consists of 30 questions, and a timer which starts from 0 ...
0
votes
1answer
29 views

Matching weighted unbalanced Bipartite graph

I am looking for a way to solve an assignment problem, but I am having some problems finding the correct algorithm to use. I have 2 list of nodes A and B, and in my problem may the length of A not be ...
1
vote
3answers
66 views

Algorithm to reduce calls to mapping API

A random distribution of points lies on a map. This data lies behind an API, and I want to grab the complete set of points within a given bounding box. I can query the API with the bounding box and ...
0
votes
2answers
72 views

Tournament bracket method to put distance between teammates

I am using a proper binary tree to simulate a tournament bracket. It's preferred any competitors in the bracket that are teammates don't meet each other until the later rounds. What is an efficient ...
1
vote
0answers
53 views

Can TDD help me develop a CUDA version of image/video processing algorithms? [closed]

I have tried many ways to migrate the image/video processing algorithm I have to run on GPU using CUDA framework and made a little progress. From reading around Stack Overflow I found a lot of ...
0
votes
2answers
87 views

High-level strategy for distinguishing a regular string from invalid JSON (ie. JSON-like string detection)

Disclaimer On Absence of Code: I have no code to post because I haven't started writing; was looking for more theoretical guidance as I doubt I'll have trouble coding it but am pretty befuddled on ...
0
votes
1answer
34 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 ...
0
votes
1answer
58 views

Algorithm to measure how “diffused” 5,000 pennies are in an economy?

Please allow me to use this example/metaphor to describe an algorithm I need. Objects There are 5 thousand pennies. There are 50 cups. There is a tracking history (Passport "stamp" etc) that is ...
0
votes
0answers
205 views

Multidimensional multiple-choice knapsack problem: find a feasible solution

My assignment is to use local search heuristics to solve the Multidimensional multiple-choice knapsack problem, but to do so I first need to find a feasible solution to start with. Here is an example ...
3
votes
4answers
220 views

Indefinite loops where the first time is different

This isn't a serious problem or anything someone has asked me to do, just a seemingly simple thing that I came up with as a mental exercise but has stumped me and which I feel that I should know the ...
3
votes
2answers
158 views

Find points whose pairwise distances approximate a given distance matrix

Problem. I have a symmetric distance matrix with entries between zero and one, like this one: D = ( 0.0 0.4 0.0 0.5 ) ( 0.4 0.0 0.2 1.0 ) ( 0.0 0.2 0.0 0.7 ) ( 0.5 1.0 0.7 0.0 ) I would ...
1
vote
2answers
96 views

Efficient algorithm to find a the set of numbers in a range

If I have an array of sorted numbers and every object is one of the numbers or multiplication. For example if the sorted array is [1, 2, 7] then the set is {1, 2, 7, 1*2, 1*7, 2*7, 1*2*7}. As you can ...
8
votes
5answers
9k views

How to quickly search through a very large list of strings / records on a database

I have the following problem: I have a database containing more than 2 million records. Each record has a string field X and I want to display a list of records for which field X contains a certain ...
-4
votes
1answer
97 views

Algorithm for drawing a circle within another shape?

Is there an algorithm or a class of algorithms for drawing a circle within another shape? I have a shape, represented in some data structure. How to find a maximal circle, which can be inscribed into ...
0
votes
1answer
62 views

Algorithmic Forecasting and Pattern Recognition

Say a user could enter project data into my software. Each project has 2 variables "size" and "work" and they're related but the relationship is not known. Is there a way to programmatically determine ...
1
vote
2answers
36 views

Minimizing Average Pairwise Squared Euclidean Norm

I'm pretty new to programming and computer science, but I was wondering if there was any good way to approach the following problem: For a set of 2n points (not necessarily unique) in R^k (assume each ...
8
votes
3answers
334 views

How many copies are needed to enlarge an array?

I am reading an analysis on dynamic arrays (from the Skiena's algorithm manual). I.e. when we have an array structure and each time we are out of space we allocate a new array of double the size of ...
4
votes
1answer
85 views

Tail-recursive implementation of take-while

I am trying to write a tail-recursive implementation of the function take-while in Scheme (but this exercise can be done in another language as well). My first attempt was (define (take-while p xs) ...
4
votes
1answer
261 views

Writing a spell checker similar to “did you mean”

I'm hoping to write a spellchecker for search queries in a web application - not unlike Google's "Did you mean?" The algorithm will be loosely based on this: http://catalog.ldc.upenn.edu/LDC2006T13 ...
2
votes
1answer
125 views

How to Detect Sprites in a SpriteSheet?

I'm currently writing a Sprite Sheet Unpacker such as Alferds Spritesheet Unpacker. Now, before this is sent to gamedev, this isn't necessarily about games. I would like to know how to detect a sprite ...
1
vote
0answers
46 views

How to canonise a road network

I am working on geographical data which represents the road network of some city and I need to automatically fix inaccuracies in the data. Data was manually produced by “drawing” the road network ...
0
votes
1answer
275 views

What data structure is suitable for implementing dynamic huffman encoding and decoding on a piece of text?

Some pseudo code or resources will be appreciated.I was thinking if implementing it in form of a BST stored in an array. However,not all operations can be performed easily using this approach. I am ...
519
votes
8answers
159k views

Which hashing algorithm is best for uniqueness and speed?

Which hashing algorithm is best for uniqueness and speed? Example (good) uses include hash dictionaries. I know there are things like SHA-256 and such, but these algorithms are designed to be ...
2
votes
1answer
104 views

How to avoid oscillation by async event based systems?

Imagine a system where there are data sources which need to be kept in sync. A simple example is model - view data binding by MVC. Now I intend to describe these kind of systems with data sources and ...
3
votes
1answer
3k views

Magic square check for N×N matrix with minimum complexity

Is there any algorithm that works better than O(n²) to verify whether a square matrix is a magic one (e.g. such as sum of all the rows, cols and diagonally are equal to each other)? I did see someone ...
0
votes
2answers
51 views

Algorithm for optimal combination of two variables

I'm looking for an algorithm that would be able to determine the optimal combination of two variables, but I'm not sure where to start looking. For example, if I have 10,000 rows in a database and ...
7
votes
5answers
292 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 ...
1
vote
4answers
165 views

How can the following algorithm be optimized?

I am currently working on a tic tac toe auto-mover game. I have come upon a decent algorithm that allows the computer to easily build towards, and claim victory spots. The problem however is that when ...
2
votes
1answer
71 views

Maze generation given intersection tree

Background Information: I'm building a 2D maze generator. I have tried Prim's algorithm, Wilson's algorithm, and a recursive backtracker algorithm for generating my maze, however was not satisfied ...
0
votes
1answer
169 views

Algorithm for detecting windows in a room

I am dealing with the following problem and i was looking to write a Pseudo-code for developing an algorithm that can be generic for such a problem. Here is what i have come up with thus far. ...
1
vote
1answer
106 views

How to construct a cubie representation of a rubik's cube, given an array

Just to get this out of the way, I have seen this, and it is not what I'm looking for. So, let's say you are programming a Rubik's Cube. (I know, very unoriginal, but bored programmers have to do ...
4
votes
1answer
185 views

Does anybody recognize this scheduling problem? Is there an algorithm for it?

Consider the following problem: Description: There are n jobs J1...Jn with cycle times C1....Cn. Find a time quanta and a scheduling table considering that: any element of the table contains at ...
0
votes
1answer
103 views

Exercise 3.6: Skiena Algorithm Design Manual

I am preparing for interview and try to solve the exercise problems of the book. 3-6. [5] Describe how to modify any balanced tree data structure such that search, insert, delete, minimum, and ...
7
votes
5answers
2k views

Improving performance for grepping over a huge file

I have FILE_A which has over 300,000 lines and FILE_B which has over 30 million lines. I created a Bash script that greps each line in FILE_A over in FILE_B and writes the result of the grep to a new ...
0
votes
1answer
27 views

What would be the most efficient way to reduce the complexity of a set of rotations to a cube?

Despite the long title, my question is fairly simple. Let's say you have a cube in 3D-space and you want to rotate it along the three axes based on the set of instructions provided by a user or ...
2
votes
1answer
83 views

Why is time complexity of k-way merge sort O(nk^2)?

I'm comparatively new to algorithm analysis and am taking a related course on coursera where I came accross k way merge sort. The time complexity of 2 way merge sort is n log2 n, of 3 way merge sort ...
9
votes
2answers
684 views

Ideal data structure for storing map data?

I was asked this in an interview test. I did okay on the test but didn't know enough to answer this question. I am curious to know what data structures I can use to query the data quickly. Basically ...
9
votes
2answers
996 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 ...
6
votes
1answer
408 views

Min cost concatenation alignment [closed]

I am doing a project on data mining. I have a very large string of size, say n and many small strings, l_1,l_2.. each of size at most m. I want to find the sequence of small strings such that their ...
0
votes
0answers
32 views

Search substring using suffix array (and LCP)

I'm searching for a best way to improve suffix array run time using LCP. My text (about 2 500 000 chars) seems like: 0ricco0eric0america0polo0.... My thoughs: SA=suffixArray char=firstChar(input) s ...
2
votes
2answers
120 views

Find number of occurrence of a word in a 2D matrix of Characters

Given a two dimensional matrix of alphabets, search the given word in all directions. Below is an example to search for the word "TEAM": No of occurrences is 4 in matrix below. What is the best ...
1
vote
2answers
30 views

Fixed duration Jobs need to be scheduled across fixed number of queues

Say I have 9 jobs with estimates of how long they will take to complete, and 3 queues that process these jobs - this constitutes one batch. Note that all the jobs are allocated to a queue beforehand ...