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)

15
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 ...
15
votes
3answers
7k views

Interview question: How would you implement Google Search?

Supposed you were asked in an interview "How would you implement Google Search?" How would you answer such a question? There might be resources out there that explain how some pieces in Google are ...
15
votes
12answers
4k views

How to write a command interpreter/parser?

Problem: Run commands in the form of a string. command example: /user/files/ list all; equivalent to: /user/files/ ls -la; another one: post tw fb "HOW DO YOU STOP THE TICKLE MONSTER?;" ...
15
votes
6answers
726 views

How does a garbage collector prevent the whole memory from being scanned on every collect?

Some (at least Mono's and .NET's) garbage collectors have a short term memory area which they scan often, and a secondary memory area which they scan less often. Mono calls this a nursery. To find ...
15
votes
2answers
4k views

Conflict resolution for two-way sync

How do you manage two-way synchronization between a 'main' database server and many 'secondary' servers, in particular conflict resolution, assuming a connection is not always available? For example, ...
15
votes
2answers
568 views

Algorithm for fast tag search

The problem is the following. There's a set of simple entities E, each one having a set of tags T attached. Each entity might have an arbitrary number of tags. Total number of entities is near 100 ...
14
votes
6answers
3k views

It takes me hours to completely understand solutions to 1000-pt problems on TopCoder. Should I get discouraged? [closed]

Sometimes this applies to the 500-pt ones too. I sometimes start feeling I will never improve enough to code them with ease like the others. Should I just quit? If not, why? It is extremely annoying, ...
14
votes
4answers
2k views

Is this XOR value swap algorithm still in use or useful

When I first started working a mainframe assembler programmer showed me how they swap to values without using the traditional algorithm of: a = 0xBABE b = 0xFADE temp = a a = b b = temp What they ...
14
votes
5answers
3k views

What would be the Impact of P=NP? [closed]

I am preparing for a test and I can't find a clear answer on the question: What would be the impact of proving that PTIME=NPTIME. I checked wikipedia and it just mentioned that it would have "profound ...
14
votes
5answers
3k views

Algorithm for Learning development [closed]

This is a fairly general question. I know a bit of Perl and Python and I am looking to learn programming in more depth so that once I get the hang of it I can start developing applications and then ...
14
votes
10answers
1k views

Find out whose turn it is to buy the croissants, accounting for possible absences

A team has decided that every morning someone should bring croissants for everybody. It shouldn't be the same person every time, so there should be a system to determine whose turn it is next. The ...
14
votes
4answers
11k views

Prerequisite math skill for Introduction to Algorithms (CLRS) book

I already have knowledge about basic algorithms. Now I plan to study more advance algorithms and I decide to go with Introduction to Algorithms. I'm not sure, do I need to refresh my math's skill ...
14
votes
9answers
3k views

What should a programmer learn first: Algorithms or Design Patterns? [closed]

I have new junior programmers (new graduates) who just joined my team, some of them do not know much about algorithms and design patterns. I am not sure which one should I teach them first?
14
votes
4answers
1k views

What algorithms can I use to detect if articles or posts are duplicates?

I'm trying to detect if an article or forum post is a duplicate entry within the database. I've given this some thought, coming to the conclusion that someone who duplicate content will do so using ...
14
votes
4answers
1k views

How can I estimate the entropy of a password?

Having read various resources about password strength I'm trying to create an algorithm that will provide a rough estimation of how much entropy a password has. I'm trying to create an algorithm ...
14
votes
4answers
2k views

Is this a Proper “Rule” for Identifying the “Big O” Notation of an Algorithm?

I've been learning more about Big O Notation and how to calculate it based on how an algorithm is written. I came across an interesting set of "rules" for calculating an algorithms Big O notation and ...
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 ...
13
votes
3answers
1k views

Would using a hash table in garbage collection solve the stop the world problem of mark and sweep?

In mark-sweep-compact garbage collection algorithm you have to stop-the-world when relocating objects because reference graph becomes inconsistent and you have to replace values of all references ...
13
votes
6answers
509 views

When to prefer a generalized solution over solving specific cases

In programming we're often faced with a choice: cover each conceivable use case individually, or solve the general problem: Its obvious that solving the immediate problem is faster, however ...
13
votes
10answers
3k views

Preferring Python over C for Algorithmic Programming

I've been studying a bit of algorithms and have been looking at sites like SPOJ.pl TopCoder etc. I've seen that programmers prefer C or C++ usually for most algorithmic programming contests. Now ...
13
votes
10answers
22k views

Difference between a pseudo code and algorithm?

Technically, Is there a difference between these two words or can we use them interchangeably? Both of them more or less describe the logical sequence of steps that follow in solving a problem. ain't ...
13
votes
10answers
769 views

In what areas of programming is algorithm run time actually an important issue?

Sometimes I hear people say that because of the speed of processors and the amount of memory available, algorithm efficiency and runtime aren't, in practice, of major concern. But I imagine there ...
13
votes
4answers
559 views

Searching integer sequences

I have a fairly complex search problem that I've managed to reduce to the following description. I've been googling but haven't been able to find an algorithm that seems to fit my problem cleanly. In ...
13
votes
6answers
1k views

Is it ok to not fully understand RB Trees? [closed]

So I just learned red black trees at Cormen and wow! Typically I like to understand all algorithms and data structures to the point I can rebuild them from scratch without having to cheat looking at ...
13
votes
3answers
6k views

Efficient graph clustering algorithm

I'm looking for an efficient algorithm to find clusters on a large graph (It has approximately 5000 vertices and 10000 edges). So far I am using the Girvan–Newman algorithm implemented in the JUNG ...
13
votes
3answers
1k 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 ...
13
votes
3answers
1k views

Initialize array in amortized constant time — what is this trick called?

There is this data structure that trades performance of array access against the need to iterate over it when clearing it. You keep a generation counter with each entry, and also a global generation ...
12
votes
8answers
2k views

Find a “hole” in a list of numbers

What is the fastest way to find the first (smallest) integer that doesn't exist in a given list of unsorted integers (and that is greater than the list's smallest value)? My primitive approach is ...
12
votes
8answers
853 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 ...
12
votes
4answers
2k views

NP complete or NP hard problems in real life

Does anybody have real life examples where they regularly solve NP complete or NP hard problems (by heuristics, or chasing a suboptimal solution or whatever) in their job? I know they occur in ...
12
votes
4answers
964 views

How do you identify a problem as being suitable for dynamic programming?

I have been reading up on dynamic programming lately. Would like to hear from someone who started from scratch and now is pretty good at identifying and solving DP problems. I am struggling in ...
12
votes
4answers
943 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 ...
12
votes
5answers
542 views

Programmaticaly finding the Landau notation (Big O or Theta notation) of an algorithm?

I'm used to search for the Landau (Big O, Theta...) notation of my algorithms by hand to make sure they are as optimized as they can be, but when the functions are getting really big and complex, it's ...
11
votes
7answers
7k views

If your algorithm is correct, does it matter how long it took you to write it?

I recently found out that Facebook had a programming challenge that if completed correctly you automatically get a phone interview. There is a sample challenge that asks you to write an algorithm ...
11
votes
5answers
12k views

Determining if an Algorithm is O (log n)

I'm refreshing my CS Theory, and I want to know how to identify that an algorithm O (log n) complexity. Specifically, is there an easy way to identify it? I know with O(n), you usually have a single ...
11
votes
7answers
4k views

How important is studying algorithms and theory is to becoming a great programmer? [duplicate]

Possible Duplicate: Should I keep investing into data structures and algorithms? I'm a CS student. I want to become a really great programmer, what do I need to do to be come a great ...
11
votes
7answers
2k views

Generating random math expression

I have this idea running around in my head, to generate and evaluate random mathematical expressions. So, I decided to give it a shot and elaborate an algorithm, before coding it to test it. Example: ...
11
votes
4answers
1k views

Interview question ranking FizzBuzz (1), implementing malloc (10)

I'd like to have your opinion on the difficulty of the following interview question: Find the contiguous subarray with maximum sum in an array of integers in O(n) time. This trivial sounding problem ...
11
votes
2answers
6k views

What does it mean to say an algorithm is Sound and Complete?

I heard different interpretations of sound and complete. I understand that completeness means finding a solution if there is one. What does it mean to say an algorithm is sound. What does it mean ...
11
votes
3answers
780 views

Please explain the statement that the function an+b belongs to O(n^2) and and Θ(n)?

Let's say I have a linear function f(n)= an+b, what is the best way to prove that this function belongs to O(n2) and Θ(n)? I do not need mathematical rigor here. I need a programmers answer. Some ...
11
votes
2answers
327 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: ...
11
votes
2answers
683 views

Functional programming and stateful algorithms

I'm learning functional programming with Haskell. In the meantime I'm studying Automata theory and as the two seem to fit well together I'm writing a small library to play with automata. Here's the ...
11
votes
5answers
315 views

Convert list of 24-hour-precipitation values into total-by-hour

Let's say I have a list of precipitation values by hour, each showing how much rain happened in the prior 24 hours, ordered by date. For example: { '2012-05-24 12:00': 0.5, // .5" of rain from ...
11
votes
5answers
790 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 ...
11
votes
3answers
325 views

Why does the iterative version take longer?

I was looking over at http://programming.lispdream.com/blog/2011/06/recursion-vs-iteration/ and I saw that on his implementation of the recursive and iterative implementations of the factorial ...
11
votes
2answers
716 views

Is Dijkstra's algorithm an appropriate solution to this signal routing problem?

I'm in the process of developing a signal management and routing module for an integrated audiovisual system and am designing it with the intent of being as flexible as possible across different ...
11
votes
4answers
1k views

Database fuzzy search concept

I thought about this, and have been trying to come up with solutions on how to fuzzy search a database, if for say example a user types a spelling mistake. Any glaring problems with the logic behind ...
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 ...
10
votes
6answers
1k views

Are all programming problems algorithm problems?

I like how "Introduction to Algorithms" by Cormen et al. conveys knowledge. One reason is that everything has to do with programming problems and the book is not implemented in any particular ...
10
votes
11answers
1k views

Prefer algorithms to hand-written loops?

Which of the following to you find more readable? The hand-written loop: for (std::vector<Foo>::const_iterator it = vec.begin(); it != vec.end(); ++it) { bar.process(*it); } Or the ...