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
0answers
75 views

Minimum of Overlapping Intervals

we have a 1-d space [1...N]. We are given M intervals of the form [L(i), R(i), C(i)] for 1 <= i <= M, where L(i) is the left most point, R(i) the rightmost and C(i) the value of that interval . ...
2
votes
1answer
91 views

What's the name of the algorithm to balance an acyclic graph?

Algorithms class was a such a long time ago and I can't remember the name of the algorithm to balance an acyclic graph. Let's start with a graph that looks like this: 1 | 2 ...
0
votes
0answers
112 views

What is this compression algorithm? (Similar to RLE)

In Run Length Encoding (RLE), a large set of information is encoded by storing the quantity of consecutive sequences. A canonical example is: ...
-2
votes
2answers
91 views

Find index of string in an array of strings where overlap could occur

I am having some trouble writing a variant of sub-string search. Essentially the goal is to write a method that can perform sub-string search except that the source data is in an array of Strings ...
0
votes
1answer
216 views

How to test an algorithm with multiple inputs?

I want to check group of algorithms which has up to 8 input options. The native idea would be to check all possibilities via brute force. How can I reduce it without leaving out required combinations? ...
1
vote
2answers
145 views

Refactoring method with nested loops and 6 variables [duplicate]

I have a method which implements a small section of a (complex) algorithm. This algorithm has taken me several weeks to perfect and is by far the fastest method I can find. The method in question has ...
2
votes
1answer
74 views

Running time of the specified Bubble Sort Algorithm

I have been working on a few algorithm questions the last few days, and one bubble sort problem in particular has been giving me headaches. for (k=1; k <= A.length - 1; k++) { //Line 1 ...
-3
votes
3answers
93 views

Link to ISO doc? Complexity of unordered_map operations in C++::stl [closed]

In different forums, I have found the statement that in C++::stl, insert and find for unordered_map have guaranteed amortized time complexity O(1). This puzzles me, and I would like to see the ...
0
votes
0answers
33 views

Pseudorandom in Android

I am building a security mechanism and I need a Pseudorandom functionality in my app. More particularly I need to convert a String to fix length. My strings are random already, they just to long so I ...
-1
votes
2answers
197 views

Gödel's Incompleteness Theorem and Algorithms [closed]

According to Gödel's incompleteness theorem, not every problem can be solved using algorithms. How do we know if a problem can be solved using algorithm? How do we know that NP problems are ...
1
vote
0answers
101 views

Finding the longest acyclical path in a 2D maze

I have a n by n maze, like this: [0, 1, 0, 0, 0, 1] [1, 1, 0, 1, 1, 0] [1, 0, 0, 1, 0, 1] [0, 1, 1, 0, 0, 1] [0, 0, 0, 1, 0, 1] [1, 0, 1, 0, 1, 1] Only 0-fields are passable, and one can only move ...
1
vote
0answers
70 views

Generate a fixed length number hash from a number

Let say I've a fixed length number, e.g. 6 digit: 837493, I want to apply some process (with a salt), and generate a new number of another 6 digits, e.g. number = 837493 another = hash(number + ...
1
vote
3answers
247 views

What's the big-O complexity of this recursive algorithm?

I am following a course of Algorithms and Data Structures. Today, my professor said the complexity of the following algorithm is 2^n. I waited till the lesson was over, approached him and told him ...
1
vote
0answers
81 views

distribute rectangles in order to do not overlap

I've a series of labels and icons inside the screen. A label is on the right of corresponding icon. I must perform a sort of declutter: when two or more labels overlap each other (or a label with an ...
0
votes
5answers
424 views

How do I avoid having to compute square roots for every element in a data set?

I have a list of points, with floating point coordinates, of which I've computed the square of the Euclidean distance between these points. I have not computed the actual Euclidean distance between ...
0
votes
2answers
356 views

Does algorithm design belong to software engineering? [closed]

In academic meaning, it seems to me that algorithm design is studied in a high/abstract level of computation (computability, complexity), although software engineering is also studied in ...
0
votes
2answers
132 views

What is a readable algorithm for selecting a random buyer based on what they purchased?

I am working on a giveaway algorithm to select a customer based on what they purchased: If they purchase item 1, they gain 1 point. If they purchase item 2, they gain 2 points. If they purchase item ...
2
votes
1answer
157 views

Best approach to implement multiple levels of difficulty to a minimax AI [closed]

I'm programming a game (turned base, in a grid) for which I implemented an AI using the minimax algorithm (with alpha-beta prunning). It's all fine and working, but the AI is too good and I can't win ...
1
vote
0answers
77 views

Algorithm for evaluating line breaks efficiently [closed]

Consider following problem : Given: String input with the length n Font(-metrics) - potentially slow in usage Bounds of an abstract Textview which shall contain the text in a specific manner: e.g ...
0
votes
2answers
100 views

Anonymize Public Health Records Database

I am working on a project to anonymize PHI in our health records database when databases are copied to our testing environments. Currently, the database is copied and fields in the tables (first name, ...
2
votes
0answers
102 views

Predicting package delivery schedules

I'm trying to solve the following problem: A delivery man has N packages to deliver, already sorted. He starts the route at start_time, he works until end_time. I have historical data of his ...
4
votes
3answers
183 views

Algorithm to determine best combination of keeping students together in their camp rooms

I have a problem I'd like to solve and am not sure whether there is a known algorithm or how the best way to approach it would be. Say for example there is a class of 30 students who are going on a ...
3
votes
0answers
143 views

How to distribute a number of elements in a bucket so that it is within a range?

I have 50 elements n1, n2, n3, ... , n50 and a limited number of buckets, say 5 buckets and each bucket can hold a range from, say 100 to 150 only (which is nothing but the sum of the elements in that ...
4
votes
1answer
191 views

Optimal fixed-size sequential sorting algorithms

I have been working on sorting algorithms for a few weeks now, but one of my question still hasn't an answer: are there optimal sequential comparison sorts for fixed-size – and random-access – ...
1
vote
1answer
334 views

Generating combinations algorithmically

Suppose I have an n-high pyramid of numbers like: 1 5 8 2 5 4 8 9 3 1 2 8 3 7 2 How can I algorithmically walk through every possible path from the top of the pyramid to the bottom? To ...
3
votes
2answers
88 views

Algorithm to identify degree of similarity based on prior categorization

I am working with digital images that people have manually categorized on a number of parameters. I want to be able to find images that are similar or dissimilar based on certain categories. For ...
1
vote
1answer
98 views

Algorithm for optimized variable generation without collisions?

I'm looking for an algorithm that can generate optimized syntactically valid variable names (for javascript in this case) without collisions. So as general rule I would want something that generated ...
3
votes
2answers
209 views

Big O Nested For Loop Breakdown

I understand how to get a general picture of the big O of a nested loop, but what would be the operations for each loop in a nested for loop? If we have: for(int i=0; i<n; i++) { for(int ...
2
votes
1answer
217 views

How do you calculate affinity in Edge Rank/Activity Streams

I have been researching how to build a newsfeed that sorts the order by relevancy. I have been following along Facebook's Edge Rank and Etsy's Activity Feed Architecture and I can't figure out how ...
0
votes
1answer
129 views

Finite Element Shader

I am working on a geometric wrapper for a space jet exhaust impingement solver. A key part of the solution is determining what the jet can "see" and therefore hit. My model is grouped with nodes or ...
1
vote
0answers
44 views

Matching data based on multiple parameters and certain limits

I've been looking into the k-nearest neighbors algorithm as I might be developing an application that matches boxers in the near future. The reason my for question, is to figure out which would be ...
-2
votes
1answer
72 views

Computer Algorithms for Polynomial Regression [closed]

Given a data set of arbitrary size, what algorithm would be appropriate for performing the polynomial regression on the data set such that the highest degree of the polynomial is n? If there are ...
5
votes
1answer
152 views

Algorithm for predicting outcome based on parameters

I've never done anything with statistics, so I'm unsure of how to start with this problem that I need to solve for some software that I'm working on. Basically, there are three parameters An ...
1
vote
0answers
47 views

Recursive(?) algorithm design help

I have a requirement to allow my end users to input formula much like a spreadsheet. I have an array like this: $table = array( 1=>array( "id"=>1, ...
3
votes
2answers
89 views

Sparse set lossy compression algorithm

I am looking for algorithm or idea for the following problem. Suppose we have a data type, say 64-bit integer. Now we have a relatively small set of such items, say few hundred at most. The simplest ...
4
votes
1answer
121 views

Sentence Word-Grading Algorithm

I need an algorithm to detect incorrect answers in memorization of sentences. Confused? Let me show you. I need to repeat the following sentence by memorization: The quick brown fox jumps over the ...
2
votes
1answer
83 views

How to test the best combination of ratios to fit inside an overarching ratio?

We have a problem we are trying to solve where we have a number of different containers. Each container can hold a number of different items (call them "item A" through to "item H"). Each container ...
2
votes
1answer
257 views

Dependency ordering algorithm of a compiler

Let's say, hypothetically, I'm writing a Java compiler. And we assume that in my case a class can't be fully compiled until all signatures of dependencies (imports and other used classes) are known. ...
1
vote
1answer
56 views

How an add vertex operation could be performed in constant time for a graph represented using adjacency list?

Adding a vertex in a graph that is represented using an adjacency list takes O(1) time complexity according to http://bigocheatsheet.com/ (graph operation > adjacency list > add vertex). It is said ...
3
votes
1answer
181 views

why adding a vertex in a graph represented using an adjacency matrix takes O(|v|^2) time complexity?

Adding a vertex in a graph that is represented using an adjacency matrix takes O(|v|^2) time complexity according to http://bigocheatsheet.com/ (graph operation > adjacency matrix > add vertex). But ...
2
votes
1answer
101 views

Time slot generation based on available technicians

Consider an Organization which provides technicians for different types of jobs. Each job type varies in completion time and technician count. For e.g., Job type 1 requires 2 technicians and 1 hour ...
0
votes
0answers
116 views

Algorithm to maximize pairwise comparisons using transitive property

I'm looking for some direction on building an algorithm that will maximize the number of pairwise comparisons of objects in a set using transitivity. To explain in detail: Suppose there are x ...
2
votes
0answers
114 views

Creating a better mouse dragger function

I originally posted this to code review, not knowing incomplete code was off-topic and was pointed to post here. I don't believe this question is a good fit for stack overflow because the code I ...
5
votes
3answers
715 views

Is O(log n) + O(log n) = O(n)? [duplicate]

We know that binary search takes O(log n) in Big O notation but if we need to run twice an algorithm of O(log n), would it be the same as O(n) in time complexity? For example, if I have a method to ...
4
votes
1answer
64 views

Can edit distance be used in a simple fashion to restrict editing to spelling mistakes only?

For a small hobby project I thought about giving users the ability to edit their submissions, but, since their submissions will be voted on by other users, restrict editing to correct (minor) spelling ...
5
votes
3answers
4k 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 ...
0
votes
1answer
110 views

What does “amortized” mean in “amortized analysis” of algorithms? [duplicate]

"amortize" mean reduce or extinguish (a debt) by money regularly put aside. i.e. to pay off of debt with a fixed repayment schedule in regular installments over a period of time. In amortized ...
1
vote
1answer
142 views

Find all the pairs in the array that match the condition

Problem: We have an int array[n]. We need to find all the pairs for which array[a] + array[b] = 0. The only algorithm I came up with so far has O(n^2) - tho most obious one. Is there a better way ...
-2
votes
2answers
462 views

Difference between O(N^2) and Θ(N^2) [duplicate]

What is the difference between O(N^2) and Θ(N^2)? I know that O is the upper bound and Θ is tight bound. Could someone explain me this concept with an example.
-1
votes
3answers
380 views

What is O(m+n) and O(m*n) in Big O notation? [duplicate]

I understand that O(n) describes an algorithm whose performance will grow linearly and in direct proportion to the size of the input data set. An example of this is a for loop: for n in 0.100 puts ...