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)

9
votes
5answers
15k 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 ...
7
votes
3answers
2k 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 ...
4
votes
3answers
727 views

Is wikipedia a valuable resource for studying data structures? (can we call it complete?)

Can I depend on wikipedia to learn data structures fully using the list of data structures http://en.wikipedia.org/wiki/List_of_data_structures and the links they refer to? The same question for ...
4
votes
3answers
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 ...
1
vote
1answer
178 views

Is there a standard name for this search approach? [closed]

In order to create a (Lucene) query, an "incomplete" domain object is used. All properties with a value are used for the query, the rest is ignored. In the absence of a better name, we call it ...
2
votes
1answer
240 views

Best way to parse optional grammar rules?

I started to write a hand written parser just for fun. For simple rules it is working, but I have problem with the optional grammar rules. I marked the optional rules with a question mark. Here is a ...
11
votes
2answers
1k 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 ...
8
votes
2answers
1k views

How is the “Pizza picking problem‍​” solved using dynamic programming techniques?

Winkler's pizza picking problem: A circular pizza pie of n slices, where slice i has area S_i i.e, the area is different for each pie piece. Eaters Alice and Bob take turns picking slices, but it ...
3
votes
4answers
130 views

How to handle “X” data sets as input

I participated in a coding competition today, and I found that almost all of the command line input our programs needed to receive would start with an integer representing the amount of data sets to ...
10
votes
5answers
1k views

Algorithm refresher. Why is heapsort an insort algorithm?

I can not see why the heapsort is considered an inplace sorting algorithm. I mean an extra data structure populated with the elements of the array to be sorted i.e. a heap, is used to assist in the ...
6
votes
2answers
463 views

How to trim emails for just the body, when using email as input to an external system?

When an application allows emails to be sent to it to either reply to comments or add todos, trimming those emails for just the relevant text becomes a problem, since there are many different ...
5
votes
3answers
373 views

How can I best study a problem to determine whether recursion can/should be used?

In some cases, I fail to see that a problem could be solved by the divide and conquer method. To give a specific example, when studying the find max sub-array problem, my first approach is to brute ...
2
votes
1answer
134 views

What techniques should I keep in mind in order to design efficient algorithms in PHP?

I am trying to solve programming challenges on www.interviewstreet.com using PHP. Are there certain techniques I should keep in mind that will optimize the efficiency of the algorithm? For example, I ...
1
vote
2answers
125 views

Help on clarification of a formal statement concerning algorithms running time

I am reading the following in a book on algorithms (Cormen's to be specific): That is, we are concerned with how the running time of an algorithm increases with the size of the input in the ...
1
vote
1answer
159 views

Algorithm analysis refresher help

I haven't touched algorithm complexity stuff in quite a while, so I am trying to do a refresher. I am trying to figure out the number of steps in the following for loop. for(i = 0; i < n; ...
11
votes
5answers
859 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 ...
6
votes
6answers
374 views

Why do many older algorithms papers reference implementations on a PDP-10 or PDP-11?

Take the original Boyer-Moore paper, for instance. It seems every time I look for an algorithm the paper I see referenced is talking about implementation idiosyncrasies on a PDP-10 or PDP-11. I know ...
6
votes
2answers
527 views

How should I organize the words of a sentence for better outputs/maintenance and performance?

Having this sentence (consider many sentences in the future) David Henderson Houston patented the first roll film for cameras in 1881. I can make questions like 1. Who patented the roll film? ...
61
votes
1answer
3k views

What task did Dijkstra give volunteers, which was mentioned in his paper “The Humble Programmer”?

In Dijkstra's paper "Humble Programmer", he mentions that he gave some volunteers a problem to solve: “I have run a little programming experiment with really experienced volunteers, but something ...
4
votes
1answer
427 views

What's the difference between the greedy and Hamiltonian methods?

Given T={CTAGC, GAGCG, AGCGG, CGGAG}, using a greedy algorithm, the superstring S will be CTAGCGGAGCG. From S, the combination of triplets will be given as s = {CTA, TAG, AGC, GCG, CGG, GGA, GAG, ...
6
votes
6answers
650 views

What kinds of development jobs require knowledge of advanced concepts? [closed]

When I was in university, I participated in a programming contest; the problems turned out to be extremely difficult and boring, and they required previous knowledge about a particular set of problem, ...
7
votes
2answers
736 views

Where can I find an algorithm for creating 3D anaglyphs using a depth map image?

I'm looking for a generic algorithm to calculate a red/cyan anaglyph starting from the original image and its black/white depth map, as in this example? That algorithm is used, for example, in ...
1
vote
3answers
603 views

Finding all nearby points in a point cloud

What's the best way to store 3D point cloud data, optimising for time it takes to find all the points in a sphere of 3D space, and also for time it takes to insert new data points into the data set? ...
2
votes
1answer
200 views

Is there an efficient way to align degenerate strings?

I have a degenerate string S1=xadcdax, where x can be replaced by any of the four characters a, b, c, or d. This S1 string is match with another non-degerate string S2=dcbaa. I can first use brute ...
6
votes
2answers
246 views

What are the common techniques to handle user-generated HTML modified differently by different browsers?

I am developing a website updater. The front end uses HTML, CSS and JavaScript, and the backend uses Python. The way it works is that <p/>, <b/> and some other HTML elements can be ...
38
votes
20answers
4k views

Do real-world algorithms that greatly outperform in the class below exist? [closed]

Last night I was discussing with another programmer that even though something may be O(1), an operation which is O(n) may outperform it if there are is a large constant in the O(1) algorithm. He ...
6
votes
2answers
2k views

How to learn about graph algorithms and some real world applications? [closed]

I've read Franco Moretti's work, but I'm looking for something more technical and perhaps broad in scope, if possible. Specifically, I want to learn about techniques programmers are using to glean ...
17
votes
8answers
4k views

Is having trouble with data structures common for beginners?

I'm taking my second course on Java. We are getting into data structures. I have done an assignment on a linked list, and now a stack. I had a hard time with the linked list. The stack gave me a ...
2
votes
6answers
1k views

Why is the formal definition of Big O notation formulated as such?

Consider the formal definition: f(n) = O(g(n)) Why is it not: f(n) = O(f(n)) or f(n) = O(c*f(n)) since for the Big O analysis, f(n)=2n and g(n)=n are identical? I am ...
4
votes
4answers
981 views

Should I learn design patterns or algorithms to improve my logical thinking skills? [duplicate]

Possible Duplicate: How can I improve my problem-solving ability? When starting a programming task, I have trouble breaking it up into steps and figuring out how to go about solving it. I ...
5
votes
4answers
3k views

Big-O for nested loop

I am reading this post on Big-O It says that the following code is O(n^2): bool ContainsDuplicates(String[] strings) { for(int i = 0; i < strings.Length; i++) { for(int j = 0; j ...
7
votes
5answers
2k views

Theta notation on constant time. Why we use the 1?

In asymptotic notation when it is stated that if the problem size is small enough (e.g. n<c for some constant c) the solution takes constant time and is writen as Theta(1). Why we write 1 inside ...
12
votes
8answers
955 views

Algorithm Vs Design [duplicate]

Possible Duplicate: Is it essential to learn algorithms to be a real programmer? This question is, perhaps, related mostly to web developers who, like myself, code enterprise applications ...
4
votes
12answers
2k views

What is the best way to introduce algorithms to undergraduate students? [closed]

If you are given the task of designing the courses leading up to a degree in computer science and are allowed just two courses on the topic of 'Algorithms', how would you structure the courses? My ...
13
votes
14answers
2k views

Can a candidate be judged by asking to write a complex program on “paper”?

Sometime back in an interview, I was asked to write following program: In a keypad of a mobile phone, there is a mapping between number and characters. e.g. 0 & 1 corresponds to nothing; 2 ...
2
votes
4answers
759 views

Difference between complexity and performance guarantee

I'm a bit confused with the performance guarantee and complexity of selection sort. I checked through internet and the complexity of selection sort is O(n^2). This O(n^2) is in terms of time ...
2
votes
6answers
260 views

Complexity vs maintainability in modern hardware

Today with the modern hardware and memory coming cheap, how much sense does it make to spend effort to analyze algoriths or data structure complexity? Wouldn't it be better instead, to focus on clean, ...
8
votes
4answers
7k views

Fast algorithm to search a sorted array of floats to find the pair of floats bracketing an input value

I have an array of floats, sorted from smallest to largest, and need to be able to pick out the nearest float greater than or less than a passed input value. This input value is not necessarily ...
3
votes
4answers
111 views

Is it possible to evaluate the efficiency of a testable algorithm against alternative solutions that aren't already built? [closed]

An e-commerce application I used to work on used a decision tree and a rules engine for each node in order to determine if a customer qualified for certain discounts. The problem was that every ...
3
votes
3answers
328 views

Does it always require a lot of programming practice before you really master an algorithm?

I have programmed for several years. And I found it is always difficult to master an algorithm(What 'master' mean here is to understand how the algorithm works and could implement independently in ...
16
votes
3answers
1k views

Java and .NET: Why different sorting algorithms are used by default?

Just wondering why Java and .NET Framework uses different sorting algorithm by default. In Java Array.Sort() uses Merge Sort algorithm by default and as Wikipedia.com says: In Java, the ...
3
votes
2answers
746 views

Are suffix trees and suffix arrays identical? What are the differences?

I have read some information through internet...i found that somehow suffix tree is quite similar to suffix array but somehow they are no the same thing.. Given a string, a suffix tree construction ...
9
votes
4answers
2k views

N queens, X by Y board decision problem interview question

I was asked the following question in an interview today and I've been thinking about it ever since. I was not able to answer it and haven't been able to find a solution online. Given a chess board ...
5
votes
3answers
1k views

does quicksort provide less swapping step?

So far, most of the fastest and common sorting method is quicksort. Although it has its pro and cons. However, i'm thinking that although this sorting method is fast but does it provide shortest ...
5
votes
5answers
1k 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 ...
7
votes
1answer
4k views

What is the best “bucket-fill” algorithm?

I'm pretty new to image processing, and I am currently working on a paint-like application that will feature a bucket-fill. However, I have no idea what the best algorithm for a bucket-fill is. I ...
2
votes
4answers
411 views

Algorithm design for comparing split times in a race

I need to determine the ranking of values in an array without altering their position, so that I can print the position of each split time next to the actual value of the split time in a table like ...
8
votes
8answers
920 views

When developing algorithms, is skipping the pen&paper phase a bad habit? [closed]

I heard many people saying that when developing algorithms you should first use pen and paper, flowcharts and what not, so that you can focus on the algorithm itself, not worrying about the ...
2
votes
2answers
2k views

Best resources to really understand run-time complexity

I'm familiar with the basics of run-time analysis such as what makes certain types of code O(n) and O(n^2). But I'm having real trouble learning, understanding, and really remembering how to analyze ...
54
votes
11answers
4k views

Should a competent programmer be able to come up with his own shortest path algorithm?

I'm suffering a crisis of confidence in my ability as a computer programmer. Yesterday I tried to come up with my own shortest path algorithm for a graph and after some hours I simply threw in the ...