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.
3
votes
4answers
121 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 ...
8
votes
5answers
639 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 ...
60
votes
1answer
2k 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 ...
2
votes
1answer
124 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
1answer
102 views
Algorith 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; ...
1
vote
2answers
107 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 ...
9
votes
5answers
467 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
344 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
6answers
551 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, ...
6
votes
3answers
400 views
How can I design an anti-spam algorithm based on a web usage profile?
I've looked at other anti-spam algorithms, notably Reddit's, but they seem to be inadequate and naive: for example, only banning specific words (like "spam") that appear in the title of a post.
How ...
6
votes
2answers
301 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?
...
5
votes
4answers
686 views
patented algorithm
What does it mean when an algorithm is patented? Am I allowed to use it as long as I am not making money out of it? I am asking because I am working on a project and I happened to discover a feature ...
32
votes
9answers
2k views
Is there an encyclopedia of algorithms?
Is there an encyclopedia of algorithms similar in style to the Handbook of Mathematics? It seems useful to have large numbers of them available in one place. I know the Art of Computer Programming is ...
3
votes
4answers
230 views
Efficiently implementing a prime sieve [closed]
I've been trying to solve a class of problems that require the generation of 1st n prime numbers. Now, n may be large, so completely fitting (2..n) in memory as required by some sieve techniques isn't ...
2
votes
1answer
155 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 ...
5
votes
2answers
940 views
How to learn about graph algorithms and some real world applications?
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 ...
2
votes
6answers
863 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
605 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 ...
4
votes
4answers
1k 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 ...
6
votes
5answers
1k 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 ...
13
votes
8answers
664 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
1k views
What is the best way to introduce algorithms to undergraduate students?
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 ...
2
votes
4answers
474 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 ...
8
votes
4answers
2k 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 ...
19
votes
4answers
2k views
Which algorithms and data structures should a developer absolutely know?
I want to be a successful enterprise Java developer. With what algorithms and data structures should I be well versed? What books would you recommend to me?
To be a successful Java developer, do I ...
3
votes
4answers
101 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
2answers
390 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 ...
3
votes
3answers
256 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 ...
1
vote
2answers
202 views
complexity of suffix tree question [closed]
Build a suffix tree from a string.
While creating the suffix tree, count re-occurrences of every substring and save it on the number of occurrences on the node.
Then do a BFS search on the tree (from ...
2
votes
1answer
292 views
Did eastern PKUFFT algorithm beat FFTW3 (Fastest FFT on the west) 20 fold?
I wonder if PKUFFT is Chinese algorithm/library and is it really better than FFTW, MKL ?
Thank you
Edit: I will elaborate. My personal programmers interest is in fast parallel algorithms like FFTW3, ...
5
votes
3answers
508 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
376 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 ...
0
votes
1answer
458 views
question, the best data structure and algorithm
I have a question about implementing a data structure (with algorithm) that has these features:
There are too many places (like stores), and each place can store too many items, I want to store ...
52
votes
11answers
3k 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 ...
2
votes
4answers
249 views
Process each row against each other, how much would it cost?
If I have n rows in a database, and I want to compare every row against each other, how many loops (or processes) would I need to do.
Is it n2? (so if I have 30,000 rows then it would be 900,000,000)
...
8
votes
3answers
8k views
Good way to learn how to solve questions on InterviewStreet [duplicate]
Possible Duplicate:
How do I adapt to pre-interview challenge questions?
InterviewStreet is a new company that essentially acts as a filter for companies to find programmers that can code. ...
7
votes
7answers
467 views
When developing algorithms, is skipping the pen&paper phase a bad habit?
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
4answers
262 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 ...
2
votes
2answers
807 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 ...
13
votes
3answers
788 views
Implementing technical paper algorithms in C++ or MATLAB
I am an Electrical Engineering undergrad. I've reading many technical papers about Signal and Image processing algorithms (reconstruction, segmentation, filtering, etc). Most of the algorithms shown ...
12
votes
4answers
688 views
What are the algorithms behind low pause GC?
Some languages, for exemple java, introduced a low pause GC.
Those GC can do most of the work without pausing the whole world. This is obviously a quite hard problem because it require to analyze the ...
8
votes
4answers
370 views
File shredder algorithm
As a part of learning system programming, I am looking to implement a file shredder. The simplest way (and probably seen as naive) would be to replace the data bytes with zeroes (I know OS splits the ...
3
votes
2answers
2k views
OCR - starting point
I really am a starter with OCR, and would like to implement an OCR system. Any pointers on where I can find the introductory material, with the programming kept in mind, like what algorithms or data ...
4
votes
3answers
251 views
Implementing a machine learning algorithm to detect the region of an address
I have 10,000 addresses from a city, which all have a region field in the database.
When a new address is entered, then I want my software to automatically detect the region of the address .
I think ...
1
vote
1answer
205 views
Subset counting algorithm
I have a following problem i want to solve efficiently :
Input: Set s of {Pass,Fail}^k vectors, m - minimum percent of vectors
Output : Set of Sets of indexes: Where each set Contains indexes of ...
1
vote
2answers
122 views
Generating functions in analyzing algorithms
I am reading a book on Algorithms and it was mentioned that generating functions are helpful in analyzing algorithms. I am not able to understand how it is useful? I request help here like giving an ...
10
votes
2answers
287 views
How to select a most probable option from the list based on user text Input
I am working over a OCR Application where I need to select a option based on user text input.
Ex:
Available Options:
["python", "ruby", "java", "clojure", "haskell"]
Input: kava
Output: java
Input: ...
4
votes
1answer
290 views
Using Quadratic Bezier Curves to generate a cave that stays within certain bounds
I'm working on a project that generates a series of quadratic bezier curves and connects them together, maintaining slope from the end of one segment to the beginning of the next to make the ...
1
vote
7answers
719 views
Responding to interview questions involving unknown algorithms
Is there any acceptable/effective way to deal with interviewers who ask you to implement an algorithm that you aren't familiar with?
I've been interviewing a lot lately and encountering this a lot. ...
14
votes
4answers
2k views
Is MapReduce anything more than just an application of divide and conquer?
Dividing a problem to smaller ones until the individual problems can be solved independently and then combining them to answer the original question is known as the divide and conquer algorithm design ...
