User Raphael

158 votes

Is there a system behind the magic of algorithm analysis?

answered Apr 9, 2014 at 12:59

94 votes

How can a language whose compiler is written in C ever be faster than C?

programming-languages compilers efficiency

answered Aug 23, 2015 at 10:20

84 votes

Accepted

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

algorithms terminology asymptotics landau-notation reference-question

answered Mar 7, 2012 at 2:06

61 votes

Accepted

How is this sorting algorithm Θ(n³) and not Θ(n²), worst-case?

algorithm-analysis asymptotics runtime-analysis sorting

answered Jan 18, 2017 at 7:06

55 votes

Accepted

Dealing with intractability: NP-complete problems

algorithms reference-request np-complete efficiency reference-question

answered Apr 24, 2012 at 6:58

55 votes

How to convert finite automata to regular expressions?

algorithms formal-languages finite-automata regular-expressions reference-question

answered May 23, 2012 at 8:19

54 votes

Accepted

How do O and Ω relate to worst and best case?

algorithm-analysis asymptotics landau-notation reference-question

answered Mar 26, 2014 at 15:29

54 votes

Accepted

Are there minimum criteria for a programming language being Turing complete?

computability programming-languages turing-machines turing-completeness

answered Apr 2, 2012 at 16:57

52 votes

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

algorithms data-structures education didactics

answered Feb 17, 2016 at 11:38

52 votes

Accepted

Sorting functions by asymptotic growth

asymptotics landau-notation reference-question

answered Mar 27, 2012 at 17:12

49 votes

How does a computer work?

computer-architecture education reference-question

answered Sep 2, 2012 at 15:03

44 votes

Accepted

Is there an existing data structure that is of fixed size, and will push the oldest/last element out if a new element is inserted?

data-structures arrays queues

answered Jul 12, 2017 at 4:56

42 votes

Accepted

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

algorithms graphs shortest-path weighted-graphs

answered Jan 16, 2014 at 22:50

42 votes

Accepted

Show that { xy ∣ |x| = |y|, x ≠ y } is context-free

formal-languages context-free

answered Mar 13, 2012 at 14:36

39 votes

Why do pushdown automata use a stack?

automata pushdown-automata computation-models

answered Oct 23, 2018 at 19:34

36 votes

Perplexed by Rice's theorem

terminology computability undecidability rice-theorem

answered Jul 18, 2012 at 10:26

35 votes

How to prove that a language is not context-free?

formal-languages context-free proof-techniques reference-question

answered Mar 16, 2012 at 15:21

34 votes

Accepted

Why are these (lossless) compression methods of many similar png images ineffective?

data-compression

answered Jul 14, 2016 at 11:24

34 votes

Accepted

Are there any non-finite automata?

automata finite-automata

answered Dec 6, 2017 at 14:06

32 votes

Is there a system behind the magic of algorithm analysis?

algorithms algorithm-analysis runtime-analysis proof-techniques reference-question

answered Apr 9, 2014 at 13:01

32 votes

Accepted

Least number of comparisons needed to sort (order) 5 elements

algorithms sorting lower-bounds

answered Aug 3, 2015 at 15:07

32 votes

The time complexity of finding the diameter of a graph

algorithms time-complexity graphs

answered Mar 10, 2012 at 14:12

31 votes

Accepted

Not all Red-Black trees are balanced?

data-structures binary-trees search-trees

answered Mar 14, 2012 at 15:00

30 votes

Why is quicksort better than other sorting algorithms in practice?

algorithms sorting

answered Mar 6, 2012 at 23:01

29 votes

Why hasn't there been an encryption algorithm that is based on the known NP-Hard problems?

complexity-theory np-hard encryption cryptography

answered Mar 14, 2012 at 9:04

27 votes

Accepted

Does there exist a priority queue with $O(1)$ extracts?

data-structures amortized-analysis priority-queues

answered Mar 20, 2012 at 13:02

27 votes

Solving or approximating recurrence relations for sequences of numbers

asymptotics proof-techniques combinatorics recurrence-relation reference-question

answered Aug 12, 2012 at 16:26

25 votes

How to prove that a grammar is unambiguous?

context-free formal-grammars proof-techniques ambiguity

answered Jun 11, 2012 at 11:38

24 votes

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

algorithms complexity-theory education

answered Sep 13, 2012 at 7:27

24 votes

How to show that L = L(G)?

formal-languages formal-grammars proof-techniques reference-question

answered Apr 14, 2013 at 19:02

Stack Exchange Network

current community

your communities

more stack exchange communities

936 Answers

Is there a system behind the magic of algorithm analysis?

How can a language whose compiler is written in C ever be faster than C?

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

How is this sorting algorithm Θ(n³) and not Θ(n²), worst-case?

Dealing with intractability: NP-complete problems

How to convert finite automata to regular expressions?

How do O and Ω relate to worst and best case?

Are there minimum criteria for a programming language being Turing complete?

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

Sorting functions by asymptotic growth

How does a computer work?

Is there an existing data structure that is of fixed size, and will push the oldest/last element out if a new element is inserted?

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

Show that { xy ∣ |x| = |y|, x ≠ y } is context-free

Why do pushdown automata use a stack?

Perplexed by Rice's theorem

How to prove that a language is not context-free?

Why are these (lossless) compression methods of many similar png images ineffective?

Are there any non-finite automata?

Is there a system behind the magic of algorithm analysis?

Least number of comparisons needed to sort (order) 5 elements

The time complexity of finding the diameter of a graph

Not all Red-Black trees are balanced?

Why is quicksort better than other sorting algorithms in practice?

Why hasn't there been an encryption algorithm that is based on the known NP-Hard problems?

Does there exist a priority queue with $O(1)$ extracts?

Solving or approximating recurrence relations for sequences of numbers

How to prove that a grammar is unambiguous?

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

How to show that L = L(G)?