Questions tagged [algorithms]

An algorithm is a sequence of well-defined steps that defines an abstract solution to a problem. Use this tag when your issue is related to design and analysis of algorithms.

An algorithm is a finite description of a computational process that transforms input data into output data.

And an algorithm is a set of ordered instructions based on a formal language with the following conditions:

  • Finite. The number of instructions must be finite.
  • Executable. All instructions must be executable in some language-dependent way, in a finite amount of time.

An algorithm does not have to be deterministic - there are many random-based algorithms, e.g. QuickSort with selecting the pivot element randomly.

An algorithm can be expressed in many ways:

  • As a sequence of instructions
  • As a block-scheme
  • As a code in an existing or new programming language
  • As a piece of text in a human language
  • As a realization in a formal model of computation such as a Turing machine
  • Or in other, similar ways

An algorithm can solve a class of problems. For example, both "sum 1 and 3" and "sum 4 and 5" are problems in the same class: "sum two integer numbers." Furthermore, a given class of problems can generally be solved by a variety of algorithms.

Questions tagged with typically ask for an algorithm to solve a specific task, or ask for an analysis of a given algorithm (note also . In the former case, it is possible to ask for an algorithm whose resource (time/memory/etc.) consumption is somehow bounded.

Questions which seek the intrinsic difficulty of some problem (rather than some specific algorithm) are better tagged with .

11822 questions
389
votes
12 answers

Why is quicksort better than other sorting algorithms in practice?

In a standard algorithms course we are taught that quicksort is $O(n \log n)$ on average and $O(n^2)$ in the worst case. At the same time, other sorting algorithms are studied which are $O(n \log n)$ in the worst case (like mergesort and heapsort ),…
Janoma
  • 5,585
  • 3
  • 22
  • 21
196
votes
3 answers

Is there a system behind the magic of algorithm analysis?

There are lots of questions about how to analyze the running time of algorithms (see, e.g., runtime-analysis and algorithm-analysis ). Many are similar, for instance those asking for a cost analysis of nested loops or divide & conquer algorithms,…
Raphael
  • 73,461
  • 31
  • 185
  • 415
147
votes
5 answers

How to convert finite automata to regular expressions?

Converting regular expressions into (minimal) NFA that accept the same language is easy with standard algorithms, e.g. Thompson's algorithm . The other direction seems to be more tedious, though, and sometimes the resulting expressions are messy.…
Raphael
  • 73,461
  • 31
  • 185
  • 415
143
votes
4 answers

BIT: What is the intuition behind a binary indexed tree and how was it thought about?

A binary indexed tree has very less or relatively no literature as compared to other data structures. The only place where it is taught is the topcoder tutorial . Although the tutorial is complete in all the explanations, I cannot understand the…
Nikunj Banka
  • 1,605
  • 3
  • 12
  • 9
132
votes
15 answers

How to fool the "try some test cases" heuristic: Algorithms that appear correct, but are actually incorrect

To try to test whether an algorithm for some problem is correct, the usual starting point is to try running the algorithm by hand on a number of simple test cases -- try it on a few example problem instances, including a few simple "corner cases".…
D.W.
  • 170,893
  • 23
  • 241
  • 528
132
votes
14 answers

Why can I look at a graph and immediately find the closest point to another point, but it takes me O(n) time through programming?

Let me clarify: Given a scatterplot of some given number of points n, if I want to find the closest point to any point in the plot mentally, I can immediately ignore most points in the graph, narrowing my choices down to some small, constant number…
Ari
  • 1,417
  • 2
  • 10
  • 5
110
votes
2 answers

Quicksort Partitioning: Hoare vs. Lomuto

There are two quicksort partition methods mentioned in Cormen: (the argument A is the array, and [p, r] is the range, inclusive, to perform the partition on. The returned value is the index to the pivot after the partition.) Hoare-Partition(A, p, r)…
Robert S. Barnes
  • 2,941
  • 5
  • 26
  • 24
103
votes
5 answers

What are the reasons to learn different algorithms / data structures serving the same purpose?

I have been wondering about this question since I was an undergraduate student. It is a general question but I will elaborate with examples below. I have seen a lot of algorithms - for example, for maximum flow problems, I know around 3 algorithms…
shole
  • 1,220
  • 2
  • 10
  • 10
102
votes
3 answers

How does one know which notation of time complexity analysis to use?

In most introductory algorithm classes, notations like $O$ (Big O) and $\Theta$ are introduced, and a student would typically learn to use one of these to find the time complexity. However, there are other notations, such as $o$, $\Omega$ and…
Miles
  • 1,333
  • 3
  • 11
  • 11
87
votes
8 answers

Graph searching: Breadth-first vs. depth-first

When searching graphs, there are two easy algorithms: breadth-first and depth-first (Usually done by adding all adjactent graph nodes to a queue (breadth-first) or stack (depth-first)). Now, are there any advantages of one over another? The ones I…
malexmave
  • 995
  • 1
  • 7
  • 9
87
votes
6 answers

How can we assume that basic operations on numbers take constant time?

Normally in algorithms we do not care about comparison, addition, or subtraction of numbers -- we assume they run in time $O(1)$. For example, we assume this when we say that comparison-based sorting is $O(n\log n)$, but when numbers are too big to…
user742
80
votes
8 answers

Floyd's Cycle detection algorithm | Determining the starting point of cycle

I am seeking help understanding Floyd's cycle detection algorithm. I have gone through the explanation on wikipedia ( http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare ) I can see how the algorithm detects cycle in O(n) time. However, I…
Anurag Kapur
  • 903
  • 1
  • 7
  • 8
76
votes
4 answers

What is tail recursion?

I know the general concept of recursion. I came across the concept of tail recursion while studying the quicksort algorithm. In this video of quick sort algorithm from MIT at 18:30 seconds the professor says that this is a tail recursive algorithm.…
Geek
  • 1,191
  • 1
  • 10
  • 12
75
votes
4 answers

Find median of unsorted array in $O(n)$ time

To find the median of an unsorted array, we can make a min-heap in $O(n\log n)$ time for $n$ elements, and then we can extract one by one $n/2$ elements to get the median. But this approach would take $O(n \log n)$ time. Can we do the same by some…
Luv
  • 871
  • 1
  • 7
  • 5
73
votes
4 answers

What is the novelty in MapReduce?

A few years ago, MapReduce was hailed as revolution of distributed programming. There have also been critics but by and large there was an enthusiastic hype. It even got patented! [1] The name is reminiscent of map and reduce in functional…
Raphael
  • 73,461
  • 31
  • 185
  • 415
1
2 3
…
99 100