Join us in building a kind, collaborative learning community via our updated Code of Conduct.

Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up

Here's how it works:

Anybody can ask a question
Anybody can answer
The best answers are voted up and rise to the top

Top Questions

active 2 featured hot week month

17

votes

5

answers

4k

views

What does a faster algorithm mean in theoretical computer science?

algorithms

modified Aug 11 at 4:29 Jared Goguen 43

22

votes

2

answers

6k

views

Do any programming languages use general recursive functions as their basis?

programming-languages mathematical-foundations church-turing-thesis

modified Aug 1 at 7:49 xuq01 927

8

votes

2

answers

1k

views

Double exponentials vs single exponentials

asymptotics discrete-mathematics notation

modified Jul 21 at 18:19 Draconis 2,555

2

votes

3

answers

2k

views

Interpretation of for loop.

programming-languages

modified Jul 30 at 15:02 Yuval Filmus 180k

6

votes

1

answer

422

views

Applicative-order languages don't support constant time array writes? If not, why not?

arrays

answered Aug 2 at 4:29 Derek Elkins 8,466

3

votes

3

answers

71

views

Represent there are infinitely many in FOL

logic first-order-logic

answered Jul 19 at 20:27 Noah Schweber 433

7

votes

1

answer

97

views

Find a straight line to divide two convex polygons by equal area

computational-geometry

modified Jul 30 at 2:22 John Reese 38

4

votes

1

answer

566

views

Making 5-tuples out of their respective 4-tuples

algorithms combinatorics

answered Jul 23 at 10:34 Yuval Filmus 180k

5

votes

2

answers

95

views

Explanation of implication-introduction rule

proof-assistants natural-deduction

modified Jul 29 at 7:24 Mario Román 151

-3

votes

1

answer

153

views

Is Alan Turing's proof of the incomputability of halting problem invalid?

computability halting-problem mathematical-foundations

modified yesterday Apass.Jack 727

2

votes

1

answer

243

views

Determining if given languages are regular or recursively enumerable

formal-languages regular-languages undecidability semi-decidability

modified Jul 29 at 20:09 Draconis 2,555

3

votes

2

answers

294

views

Time Complexity to find height of a BST

algorithms algorithm-analysis trees binary-trees search-trees

modified Aug 2 at 8:49 xskxzr 2,551

1

vote

1

answer

279

views

Is every AVL tree a BST or just BT?

trees balanced-search-trees

modified Jul 27 at 11:30 John P 453

2

votes

1

answer

116

views

Is a sum of n terms considered O(1) or O(n)?

complexity-theory asymptotics

answered Aug 7 at 16:35 Pål GD 5,687

2

votes

2

answers

262

views

Does UDP always deliver packets inorder to the application layer

computer-networks

answered Aug 11 at 13:36 Damon 151

3

votes

2

answers

148

views

PCP undecidability

reductions undecidability

answered Aug 7 at 21:40 Yuval Filmus 180k

4

votes

1

answer

436

views

Algorithm for using power series to numerically solve a partial differential equation given a boundary condition?

algorithms asymptotics numerical-algorithms

modified Aug 4 at 11:04 Foad 121

4

votes

2

answers

72

views

Proving that $\{0^{m^2}\mid m\geq 3\}^*$ is regular

automata regular-languages number-theory

answered Jul 19 at 20:10 gnasher729 9,018

2

votes

1

answer

229

views

Why is this n^2 growth?

algorithms algorithm-analysis python

modified Aug 5 at 5:16 Glorfindel 133

1

vote

2

answers

77

views

Super-strongly connected components?

graph-theory

modified Aug 9 at 5:51 Karel Macek 108

3

votes

2

answers

59

views

What is the State of The Art of Writer AIs (Deep Learning)?

machine-learning

modified Aug 7 at 0:42 Filip 58

1

vote

3

answers

58

views

Algorithm to compute maximum of blocks

algorithms arrays

modified Aug 1 at 7:04 Yuval Filmus 180k

1

vote

3

answers

56

views

How does computer store non-repeating decimal very accurately?

floating-point

answered Jul 28 at 23:56 TEMLIB 1,266

1

vote

2

answers

126

views

Random walk increasing distance

random-walks

modified Aug 6 at 21:42 alfredopacino 106

2

votes

2

answers

59

views

How is space from malloc allocated?

operating-systems

answered Jul 21 at 20:06 JeanPierre 141

1

vote

1

answer

86

views

Why is $n + 2n^2 + 10n^4 = O(n^5)$?

asymptotics

answered Aug 7 at 4:54 6005 824

1

vote

3

answers

85

views

Can computers lose information?

memory-management

modified Jul 24 at 7:02 Yuval Filmus 180k

3

votes

2

answers

81

views

Binary search with alternative comparison cost

algorithms binary-search

answered Jul 24 at 21:30 D.W.♦ 94.5k

4

votes

2

answers

45

views

Chernoff-like Concentration Bounds on Permutations

permutations chernoff-bounds

answered Aug 12 at 21:04 Jeff Cooper 43

0

votes

2

answers

88

views

Given n numbers How to find out a set of numbers whose sum equal to a certain given number

algorithms complexity-theory combinatorics sets

modified Jul 21 at 23:05 Gassa 600

1

vote

2

answers

112

views

Can hypercomputation compute all kinds of incomputable numbers/functions/problems…etc?

computability quantum-computing hypercomputation

answered Aug 7 at 1:41 Aryeh 126

1

vote

2

answers

39

views

Are all computational complexity results oracle results?

complexity-theory programming-languages computation-models

answered Jul 22 at 7:07 Yuval Filmus 180k

4

votes

2

answers

48

views

Given $k$ points in $n$-dimensions, such that $n\geq3$, is there a polytime algorithm for finding a curve that splits them into 2 sets of points?

algorithms polynomial-time classification

modified yesterday karthik 1

4

votes

1

answer

129

views

+50

How can I correct this Hamming code?

error-correcting-codes hamming-code

modified yesterday Apass.Jack 727

1

vote

1

answer

47

views

Artificial intelligence and undecidibility

undecidability artificial-intelligence

answered Jul 23 at 15:52 D.W.♦ 94.5k

3

votes

2

answers

124

views

Skip List estimate number of elements less than (or greater than) a value

algorithms data-structures time-complexity multi-tasking

answered Aug 9 at 8:15 Dmitri Urbanowicz 216

5

votes

2

answers

45

views

Big O notation: removing big O from denominator

asymptotics numerical-analysis

modified Aug 10 at 20:34 Apass.Jack 727

1

vote

1

answer

71

views

Haskell type class and initial algebra

haskell

modified Aug 1 at 20:36 Mario Román 151

3

votes

2

answers

71

views

Predicate Logic - Natural Deduction; Assumptions about exists-elimination

logic natural-deduction

answered Aug 7 at 5:35 6005 824

3

votes

1

answer

71

views

What textbooks includes explanations of advanced data structures found commonly in competitive programming?

algorithms data-structures books

answered Jul 19 at 7:47 Jakube 560

3

votes

2

answers

104

views

Is there a name and efficient algorithm for this Tree Traversal method?

algorithms data-structures trees

modified Aug 7 at 11:08 Dmitri Urbanowicz 216

3

votes

1

answer

49

views

How to distinguish between bits?

computer-networks bit-manipulation

modified Jul 28 at 0:56 Draconis 2,555

3

votes

1

answer

103

views

Is this scheduling problem with arrival times, deadlines, and costs NP-hard?

algorithms np-hard

answered Jul 25 at 3:02 j_random_hacker 2,484

2

votes

1

answer

80

views

Finding the maximum substring for which a given predicate is true

algorithms strings substrings

modified Jul 28 at 9:42 Dmitri Urbanowicz 216

4

votes

1

answer

74

views

How to generate branch tables from SSA form?

compilers code-generation

answered yesterday Tim Foley 31

5

votes

2

answers

95

views

Path in an edge-weighted undirected graph

graphs np-complete weighted-graphs

modified yesterday Apass.Jack 727

6

votes

0

answers

116

views

Testing algorithm for a modified sieve of Eratosthenes

algorithms complexity-theory number-theory

modified Aug 5 at 15:43 Daniel Castle 131

2

votes

1

answer

68

views

Proving Progress for STLC with Linear and Unrestricted Types

programming-languages lambda-calculus

answered Jul 20 at 8:53 Rodolphe Lepigre 631

Looking for more? Browse the complete list of questions, or popular tags. Help us answer unanswered questions.

Computer Science Stack Exchange works best with JavaScript enabled