Hottest Questions This Week

1

vote

2

answers

103

views

Can the pre-order traversal of two different trees be the same even though they are different?

modified 2 hours ago lox 1,007

2

votes

3

answers

190

views

Is time complexity more important than space complexity?

algorithms time-complexity cryptography

modified Jun 12 at 4:02 Apass.Jack 17k

2

votes

3

answers

52

views

How is functional property guaranteed in type theory when function type is defined?

type-theory homotopy-type-theory

modified Jun 12 at 21:03 Andrej Bauer 21k

0

votes

2

answers

67

views

What is the height of a tree with recursion formula: $T(n) = T(n - \sqrt{n})$

time-complexity trees recursion

answered Jun 12 at 14:49 Emil Jeřábek 406

1

vote

1

answer

132

views

how to find total paths in a graph which have only one vertex common with a given path

algorithms graphs trees

modified Jun 13 at 8:19 Vince 1,008

4

votes

1

answer

198

views

Data structure for selection of K elements and taking sum

algorithms data-structures

modified Jun 10 at 17:41 Community♦ 1

2

votes

1

answer

109

views

Showing that a language is NP Complete (advice)

complexity-theory

answered yesterday David Richerby 72.6k

0

votes

1

answer

61

views

Is computer science really a branch or sub-branch of physics? [on hold]

physics

modified Jun 13 at 11:29 orlp 6,610

5

votes

1

answer

65

views

Searching a Treasure

algorithms complexity-theory time-complexity search-algorithms

modified 2 days ago Apass.Jack 17k

1

vote

1

answer

55

views

Are all compilers Turing Machines?

turing-machines compilers

answered yesterday David Richerby 72.6k

3

votes

2

answers

47

views

Proving a problem as NP-complete

np-complete np

answered Jun 13 at 16:36 David Richerby 72.6k

4

votes

2

answers

36

views

Can every Turing Machine be translated into a SAT formula?

satisfiability halting-problem

modified Jun 12 at 18:51 MLStudent 52

5

votes

1

answer

45

views

Two languages such that $L_1 \cup L_2 \leq_m\, L_1 \cap L_2$ and two (other?) such that $L_1 \cap L_2 ≤_m\, L_1 \cup L_2$?

automata regular-languages context-free

modified Jun 10 at 16:52 Apass.Jack 17k

4

votes

1

answer

92

views

Matching Algorithm - How to maximize matched quantity with unique matching rules?

algorithms graphs time-complexity matching bipartite-matching

modified 19 hours ago luca590 121

2

votes

2

answers

40

views

Is the language L = {(a,b)* | #a * #b is an odd number} regular?

automata regular-languages finite-automata

answered Jun 13 at 12:40 gandalf61 176

2

votes

1

answer

105

views

+50

Algorithm for fewest number of moves with artificial minimum

algorithms graphs coin-change

modified Jun 12 at 20:32 David Fox 73

1

vote

2

answers

48

views

How can the length of a string be $O(\log n)$?

time-complexity python

modified Jun 12 at 13:54 Yuval Filmus 202k

3

votes

1

answer

60

views

Does a Minimum-Spanning-Tree always give a lower bound for the weight of any Hamiltonian cycle of the graph?

complexity-theory graphs

modified 10 hours ago lox 1,007

3

votes

1

answer

36

views

How to calculate Big O of $T(n) = aT(n^b) + f(n)$?

complexity-theory time-complexity big-o-notation

answered 2 days ago Apass.Jack 17k

2

votes

1

answer

76

views

Can these two languages be reduced to one another?

turing-machines computability reductions

modified Jun 10 at 17:46 Yuval Filmus 202k

1

vote

1

answer

59

views

Is “Query Equivalence” decidable?

computability database-theory

answered yesterday Curtis F 507

-1

votes

1

answer

71

views

Can we find every 216 digit number combination? [on hold]

computability mathematical-programming mathematical-analysis mathematical-software

modified 22 hours ago Jonathan Irons 99

2

votes

1

answer

55

views

Conditions for a binary tree being balanced

trees combinatorics

modified Jun 11 at 17:26 Apass.Jack 17k

3

votes

2

answers

52

views

Count paths of length $n$ that a player can take

algorithms graphs combinatorics

modified Jun 12 at 6:22 kyle_williams 16

0

votes

1

answer

85

views

Proving NP completeness of maximal length path

complexity-theory np-complete np-hard np complexity-classes

modified 2 days ago Panzerkroete 110

1

vote

0

answers

72

views

+100

How does a Turing machine with one tape read its input?

turing-machines computability

modified 9 hours ago Yuval Filmus 202k

2

votes

1

answer

23

views

NL problem? $CONN$= {$〈G,k〉$ ∶$G$ is undirected graph with at least k connected components}

complexity-theory graph-theory nondeterminism

answered Jun 11 at 16:30 Yuval Filmus 202k

1

vote

2

answers

62

views

Algorithm for generating random incrementing numbers up to a limit

algorithms

modified yesterday Apass.Jack 17k

2

votes

1

answer

26

views

One-taped RAM vs Multi-taped RAM

complexity-theory turing-machines

answered 2 days ago Yuval Filmus 202k

0

votes

1

answer

42

views

Advantages of Lambda calculus over Turing machine and vice versa [closed]

turing-machines computability lambda-calculus

answered Jun 10 at 9:49 gandalf61 176

3

votes

1

answer

32

views

Quantum vs classic in NP-hard problems

complexity-theory time-complexity np-hard np quantum-computing

answered Jun 10 at 9:22 Yuval Filmus 202k

2

votes

1

answer

48

views

Thought process for the following problem?

algorithms arrays

modified 2 days ago Navjot Waraich 728

1

vote

0

answers

47

views

divide and conquer algorithm for finding a 3-colored triangle in an undirected graph with the following properties?

graphs graph-theory divide-and-conquer

modified Jun 11 at 19:37 Gilfoyle 6

2

votes

1

answer

28

views

Non-Deterministic Turing machine vs Probabilistic Turing Machine vs Deterministic Turing Machine

complexity-theory turing-machines

modified Jun 11 at 17:21 lox 1,007

4

votes

1

answer

28

views

How to construct an ordinary matching from a fractional matching?

graphs matching

modified Jun 10 at 10:02 Discrete lizard♦ 5,183

2

votes

0

answers

46

views

Minimum clique cover

graph-theory reductions linear-programming integer-programming clique

modified 7 hours ago Rodrigo de Azevedo 700

2

votes

1

answer

27

views

How to find size of each tree in a forest?

trees

modified 10 hours ago lox 1,007

1

vote

1

answer

44

views

How do you write a diff algorithm given limited amount of RAM?

algorithms memory-management filesystems

answered Jun 13 at 0:01 Bulat 1,266

1

vote

2

answers

26

views

What is the graphic TSP?

graphs weighted-graphs traveling-salesman

answered 2 days ago David Richerby 72.6k

1

vote

1

answer

42

views

How does dynamic memory-allocation exactly work?

operating-systems memory-allocation c

modified Jun 10 at 15:34 TVSuchty 66

2

votes

1

answer

42

views

Construct a DFA from the regular expression (a)+(aab)

automata regular-languages finite-automata

modified Jun 12 at 17:45 Apass.Jack 17k

0

votes

0

answers

41

views

Is it possible to create a black box program where the source code is completely obfuscated? [closed]

java c

modified Jun 12 at 12:45 VARUN.N RAO 48

0

votes

0

answers

40

views

On the same group data strcture

data-structures time-complexity

modified Jun 13 at 8:38 Yuval Filmus 202k

0

votes

1

answer

40

views

pseudo-polynomial reduction from 3-Partition to Partition

complexity-theory np-complete reductions pseudo-polynomial

modified 2 days ago Tom van der Zanden 9,264

2

votes

0

answers

37

views

Closure under polynomial reduction

complexity-theory

modified Jun 12 at 14:44 Yuval Filmus 202k

0

votes

1

answer

37

views

Given n standard C++ STL maps, can I merge them? [on hold]

algorithms data-structures

modified yesterday rici 4,755

4

votes

0

answers

36

views

Algorithm for Unique Selections

algorithms time-complexity

asked Jun 10 at 23:04 Draconis 6,082

3

votes

0

answers

36

views

Assign weights to the edges in a DAG so that, for all S and T, all paths from S to T have equal weight

algorithms graphs weighted-graphs dag

modified Jun 12 at 19:20 Paul Accisano 116

Top Questions

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