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.

Filter by
Sorted by
Tagged with
195 votes
3 answers
26k views

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 ...
Raphael's user avatar
  • 72.4k
101 votes
3 answers
35k views

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 ...
Jack H's user avatar
  • 1,323
141 votes
5 answers
206k views

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 ...
Raphael's user avatar
  • 72.4k
40 votes
5 answers
120k views

How to come up with the runtime of algorithms? [duplicate]

I've not gone much deep into CS. So, please forgive me if the question is not good or out of scope for this site. I've seen in many sites and books, the big-O notations like $O(n)$ which tell the ...
Code0987's user avatar
  • 523
86 votes
6 answers
22k views

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 ...
user avatar
50 votes
2 answers
9k views

What is the difference between an algorithm, a language and a problem?

It seems that on this site, people will often correct others for confusing "algorithms" and "problems." What are the difference between these? How do I know when I should be considering algorithms and ...
Joey Eremondi's user avatar
52 votes
6 answers
7k views

Dealing with intractability: NP-complete problems

Assume that I am a programmer and I have an NP-complete problem that I need to solve it. What methods are available to deal with NPC problems? Is there a survey or something similar on this topic?
Anonymous's user avatar
  • 621
34 votes
6 answers
15k views

Differences and relationships between randomized and nondeterministic algorithms?

What differences and relationships are between randomized algorithms and nondeterministic algorithms? From Wikipedia A randomized algorithm is an algorithm which employs a degree of randomness ...
Tim's user avatar
  • 4,895
40 votes
7 answers
4k views

Explaining the relevance of asymptotic complexity of algorithms to practice of designing algorithms

In algorithms and complexity we focus on the asymptotic complexity of algorithms, i.e. the amount of resources an algorithm uses as the size of the input goes to infinity. In practice, what is ...
Kaveh's user avatar
  • 22.2k
386 votes
12 answers
348k views

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)$ ...
Janoma's user avatar
  • 5,535
56 votes
4 answers
9k views

Why polynomial time is called "efficient"?

Why in computer science any complexity which is at most polynomial is considered efficient? For any practical application(a), algorithms with complexity $n^{\log n}$ are way faster than algorithms ...
Ran G.'s user avatar
  • 20.7k
14 votes
2 answers
17k views

When can I use dynamic programming to reduce the time complexity of my recursive algorithm?

Dynamic programming can reduce the time needed to perform a recursive algorithm. I know that dynamic programming can help reduce the time complexity of algorithms. Are the general conditions such that ...
Anonymous's user avatar
  • 141
36 votes
4 answers
5k views

What is dynamic programming about?

Sorry in advance if this question sounds dumb... As far as I know, building an algorithm using dynamic programming works this way: express the problem as a recurrence relation; implement the ...
hey hey's user avatar
  • 463
16 votes
4 answers
5k views

Algorithms computing if a number is a multiple of 3

When doing mental calculus one can do: Given an integer k, sum all the digits (in base 10), and if the result is a multiple of 3, then k is a multiple of 3. Do you know of any algorithm working ...
Stephane Rolland's user avatar
48 votes
4 answers
66k views

Longest path in an undirected tree with only one traversal

There is this standard algorithm for finding longest path in undirected trees using two depth-first searches: Start DFS from a random vertex $v$ and find the farthest vertex from it; say it is $v'$. ...
e_noether's user avatar
  • 1,299
23 votes
3 answers
4k views

Converting (math) problems to SAT instances

What I want to do is turn a math problem I have into a boolean satisfiability problem (SAT) and then solve it using a SAT Solver. I wonder if someone knows a manual, guide or anything that will help ...
Dchris's user avatar
  • 415
14 votes
2 answers
10k views

Algorithm to determine whether two regexes are equivalent

Given two arbitrary regular expressions, is there an "efficient" algorithm to determine whether they match the same set of strings? More generally, can we compute the size of the intersection of the ...
MathematicalOrchid's user avatar
13 votes
4 answers
5k views

Is there a method for automatic runtime analysis of algorithms?

I am wondering, is there a method for automatic runtime analysis that works at least on a relevant subset of algorithms (algorithms that can be analyzed)? I googled "Automatic algorithm analysis" ...
Nathvi's user avatar
  • 185
19 votes
3 answers
3k views

Why use comparisons instead of runtime for comparing two algorithms?

I notice that in a few CS research papers, to compare the efficiency of two algorithms, the total number of key comparison in the algorithms is used rather than the real computing times themselves. ...
has's user avatar
  • 361
3 votes
3 answers
8k views

Iterative and/or tail-recursive implementations of merge sort?

I recently learned how to implement merge-sort, using a standard recursive algorithm. Can the algorithm be implemented in a way that allows for a tail-recursive implementation? Can it be implemented ...
Aseem Bansal's user avatar
110 votes
2 answers
80k views

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,...
Robert S. Barnes's user avatar
35 votes
6 answers
17k views

Uniform sampling from a simplex

I am looking for an algorithm to generate an array of N random numbers, such that the sum of the N numbers is 1, and all numbers lie within 0 and 1. For example, N=3, the random point (x, y, z) should ...
Ruofeng's user avatar
  • 453
21 votes
2 answers
6k views

How to describe algorithms, prove and analyse them?

Before reading The Art of Computer Programming (TAOCP), I have not considered these questions deeply. I would use pseudo code to describe algorithms, understand them and estimate the running time only ...
Yai0Phah's user avatar
  • 621
13 votes
9 answers
2k views

What exactly is an algorithm?

I know that this may sound a bit out of the box, in fact i used to always think inside the box, but recently i've been thinking, possibly because computer science provides an high degree of freedom, ...
Devian Dover's user avatar
43 votes
3 answers
20k views

Deciding on Sub-Problems for Dynamic Programming

I have used the technique of dynamic programming multiple times however today a friend asked me how I go about defining my sub-problems, I realized I had no way of providing an objective formal answer....
daniel gratzer's user avatar
30 votes
1 answer
13k views

How hard is counting the number of simple paths between two nodes in a directed graph?

There is an easy polynomial algorithm to decide whether there is a path between two nodes in a directed graph (just do a routine graph traversal with, say, depth-first-search). However it seems that, ...
hugomg's user avatar
  • 1,379
9 votes
3 answers
5k views

How to develop an $O(N)$ algorithm solve the 2-sum problem?

Given an sorted array of integers, I want to find the number of pairs that sum to $0$. For example, given $\{-3,-2,0,2,3,4\}$, the number of pairs sum to zero is $2$. Let $N$ be the number of ...
Laura's user avatar
  • 291
6 votes
2 answers
4k views

Does Ford-Fulkerson always produce the left-most min-cut

When using Ford-Fulkerson to find max-flow between s and t, the exact choice of flow-graph depends on which paths are found. However, if you then use the left-over residual graph to produce a min-cut ...
dspyz's user avatar
  • 416
5 votes
2 answers
2k views

How fast can we identifiy almost-duplicates in a list of strings?

I'm having trouble figuring out the upper bound running time for this scenario: Input: $N$ number of strings $M$ upper bound of string length $T$ threshold for edit distance (2 strings with a ...
Eran Medan's user avatar
4 votes
1 answer
562 views

state of the art of subset, set containment and partial match queries

The subset query problem is defined as: Given a list D of size N where the entries are subsets of a universe with ...
Memphisd's user avatar
  • 153
101 votes
5 answers
10k views

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 ...
shole's user avatar
  • 1,200
31 votes
1 answer
10k views

Which combinations of pre-, post- and in-order sequentialisation are unique?

We know post-order, post L(x) => [x] post N(x,l,r) => (post l) ++ (post r) ++ [x] and pre-order ...
Raphael's user avatar
  • 72.4k
9 votes
1 answer
8k views

Finding the k-shortest path between two nodes

Given a weighted digraph $G=V,E$, and a weight function, $d(u,v)$, one can normally use Dijkstra's algorithm to obtain the shortest path. What I am interested in, is how to obtain the $2^{nd}$-...
Realz Slaw's user avatar
  • 6,191
5 votes
1 answer
2k views

Algorithm to find maximum number of floors you can check with N eggs and D maximum drops

Question: You are given access to a multistory building. You have N eggs and are allowed D maximum drops from their window. Rules: If a egg is dropped from window of floor F and it breaks, it will ...
Smart Home's user avatar
137 votes
3 answers
48k views

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 ...
Nikunj Banka's user avatar
  • 1,545
128 votes
15 answers
16k views

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 ...
D.W.'s user avatar
  • 159k
50 votes
3 answers
80k views

Why does Dijkstra's algorithm fail on a negative weighted graphs? [duplicate]

I know this is probably very basic, I just can't wrap my head around it. We recently studied about Dijkstra's algorithm for finding the shortest path between two vertices on a weighted graph. My ...
so.very.tired's user avatar
35 votes
5 answers
9k views

Enumerate all non-isomorphic graphs of a certain size

I'd like to enumerate all undirected graphs of size $n$, but I only need one instance of each isomorphism class. In other words, I want to enumerate all non-isomorphic (undirected) graphs on $n$ ...
D.W.'s user avatar
  • 159k
29 votes
4 answers
43k views

The time complexity of finding the diameter of a graph

What is the time complexity of finding the diameter of a graph $G=(V,E)$? ${O}(|V|^2)$ ${O}(|V|^2+|V| \cdot |E|)$ ${O}(|V|^2\cdot |E|)$ ${O}(|V|\cdot |E|^2)$ The diameter of a ...
Gigili's user avatar
  • 2,193
25 votes
1 answer
7k views

How to prove correctness of a shuffle algorithm?

I have two ways of producing a list of items in a random order and would like to determine if they are equally fair (unbiased). The first method I use is to construct the entire list of elements and ...
edA-qa mort-ora-y's user avatar
22 votes
4 answers
4k views

Sorting algorithms which accept a random comparator

Generic sorting algorithms generally take a set of data to sort and a comparator function which can compare two individual elements. If the comparator is an order relation¹, then the output of the ...
edA-qa mort-ora-y's user avatar
20 votes
1 answer
20k views

Find the Simple Cycles in a Directed Graph

This problem, for me, looks very interesting. It was about to find a simple cycle (i.e. cycle where are not repeat nodes) in a directed graph. My solution is going like this, i.e, this graph is a ...
Jonathan Prieto-Cubides's user avatar
18 votes
3 answers
4k views

Algorithm books on a range of topics

I've been tasked with building a library of books on algorithms for our small company (about 15 people). The budget is more than 5k, but certainly less than 10k, so I can buy a fair number of books. ...
mtf's user avatar
  • 189
15 votes
1 answer
7k views

Are all MST minimum spanning trees reachable by Kruskal and Prim?

I believe this is true but have not been able to get a formal proof for either. But is it true that any minimum spanning tree is reachable by applying Kruskal's algorithm? Similarly, is this true for ...
domoremath's user avatar
14 votes
2 answers
10k views

Why can't we find shortest paths with negative weights by just adding a constant so that all weights are positive?

I'm currently reading introduction to algorithms and came by Johnson’s algorithm that depends on making sure that all paths are positive. the algo depends on finding a new weight function (w') that ...
Mr.Me's user avatar
  • 243
13 votes
2 answers
21k views

Time complexity of a triple-nested loop

Please consider the following triple-nested loop: ...
Xin's user avatar
  • 131
7 votes
1 answer
7k views

Find a 3-colouring using the 3-colourability decision problem

I was learning about NP problems. I read that for many problems, like Clique, we can easily convert its decision problem to derive a solution of search problem. (For Clique problem, you only need to ...
Zzq's user avatar
  • 71
2 votes
3 answers
2k views

Given a set of 2D vectors, find the furthest reachable point

Input: a set of 2D vectors $S=\{v_1,v_2,\dots,v_n\mid v_i\in \mathbb{Z}^2 \}$ Question: name $P=\{\sum_{v_i\in S'}v_i\mid S'\subseteq S \}$ for all subsets of $S$ (obviously $|P|=O(2^n)$). In ...
Harry's user avatar
  • 111
48 votes
8 answers
77k views

The math behind converting from any base to any base without going through base 10?

I've been looking into the math behind converting from any base to any base. This is more about confirming my results than anything. I found what seems to be my answer on mathforum.org but I'm still ...
Griffin's user avatar
  • 593
42 votes
9 answers
63k views

Algorithm to find diameter of a tree using BFS/DFS. Why does it work?

This link provides an algorithm for finding the diameter of an undirected tree using BFS/DFS. Summarizing: Run BFS on any node s in the graph, remembering the node u discovered last. Run BFS from u ...
curryage's user avatar
  • 531

1
2 3 4 5
21