Hottest Questions This Week

10

votes

2

answers

3k

views

How is conditional jump implemented in the CPU?

computer-architecture cpu

answered Apr 7 at 17:10 David Schwartz 181

1

vote

1

answer

398

views

Decidable? If a Turing Machine M, on input w, will M ever move its read/write head to the left?

turing-machines

modified Apr 8 at 20:39 Juns 1

6

votes

2

answers

135

views

Minimal number of states for an NFA of all different words

regular-languages finite-automata nondeterminism

answered yesterday amalloy 101

2

votes

1

answer

120

views

Weighted binary search tree

algorithms data-structures

modified Apr 8 at 18:07 Steven 14.4k

0

votes

2

answers

84

views

Primes not dividing sequence $a_{n+1} = 1 + a_0 a_1 \cdots a_n$

discrete-mathematics number-theory

modified 2 days ago D.W.♦ 130k

1

vote

1

answer

80

views

Where does 1.3606 approximation ratio come from for vertex cover approximation?

approximation vertex-cover

modified 2 days ago Steven 14.4k

4

votes

1

answer

40

views

Are the sets in $\Sigma_{p}$ (or $\Pi_{p}$) totally ordered?

computability mathematical-foundations

modified 7 mins ago Noah Schweber 2,102

0

votes

1

answer

47

views

How to prove (un)decidability

turing-machines undecidability halting-problem semi-decidability

modified 2 days ago Steven 14.4k

1

vote

1

answer

54

views

How do Kruskal's and Prim's algorithms compare to each other?

algorithms graphs minimum-spanning-tree

modified Apr 6 at 10:28 Nathaniel 1,893

-2

votes

2

answers

46

views

Convert NFA to DFA

automata

modified Apr 8 at 6:57 TigerTV.ru 103

1

vote

1

answer

45

views

Reducibility: Show that SUBSET SUM is reducible to the following problem A

time-complexity

modified 2 days ago Steven 14.4k

1

vote

1

answer

33

views

A monotonically nondecreasing function $ f(n) $ s.t $ f \in O(n^2) $ and $ f \notin o(n^2) $ but also $ f \in \Omega(n) $ and $ f \notin \omega(n) $

asymptotics big-o-notation

modified Apr 7 at 21:51 Nathaniel 1,893

1

vote

1

answer

33

views

Prolog: Deletion of all appearances of an element in a list

prolog predicate-logic

answered Apr 6 at 13:48 Alp 46

1

vote

1

answer

41

views

Minimal unsatisfiable core algorithm

algorithms search-algorithms satisfiability 3-sat

answered yesterday Kyle Jones 7,260

2

votes

1

answer

66

views

How does strong NP-completeness agree with encoding complexity?

complexity-theory np-complete reductions complexity-classes encoding-scheme

modified Apr 9 at 9:07 programonkey 21

0

votes

2

answers

51

views

Build an FA that accepts only the words baa, ab, and abb and no other strings longer or shorter

finite-automata nondeterminism

answered Apr 6 at 19:29 benrg 706

2

votes

1

answer

50

views

Closure of regular languages under interchanging two different letters

regular-languages finite-automata

modified Apr 8 at 15:56 Yuval Filmus 249k

1

vote

1

answer

36

views

How would I prove that the regular expression rejects string?

algorithms algorithm-analysis

modified Apr 7 at 22:01 plop 946

0

votes

1

answer

46

views

Four functions problem

mathematical-programming mathematical-analysis primes

modified Apr 9 at 6:02 plop 946

1

vote

1

answer

34

views

Given two DFA's accepting the same language, does one have to refine the other?

regular-languages automata finite-automata

modified Apr 8 at 15:56 Yuval Filmus 249k

1

vote

1

answer

43

views

How to prove NP-completeness of this mail-problem?

np-complete np-hard np polynomial-time

answered 2 days ago Steven 14.4k

1

vote

1

answer

21

views

Expected behavior of an algorithm to minimize rankings

graphs greedy-algorithms

modified 2 days ago John L. 25.5k

-1

votes

2

answers

16

views

Can you have an approximation that is higher than the optimal for a maximum value and a lower than the optimal for a minimum value?

approximation

answered 2 days ago Nathaniel 1,893

1

vote

1

answer

33

views

Simplifying $b(abb + abbbb + aba^bbb)^$

regular-expressions

modified Apr 7 at 6:41 Yuval Filmus 249k

-1

votes

0

answers

42

views

Why do name abbreviations continue to exist? [closed]

programming-languages

asked yesterday Monther 71

1

vote

1

answer

42

views

Finding all pairs of points with no point in between

algorithms computational-geometry

modified 6 hours ago orlp 11.7k

1

vote

2

answers

25

views

Reduction from Independent Set with fixed vertex to Independent Set

complexity-theory reductions

answered Apr 6 at 8:11 Yuval Filmus 249k

0

votes

2

answers

32

views

Is it decidable whether a TM is a LBA?

turing-machines linear-bounded-automata

modified Apr 6 at 8:05 Yuval Filmus 249k

0

votes

2

answers

32

views

Consider a 1-tape TM that starts with n ≥ 1 written in unary/binary notation on its tape. Explain how it can count down from n to 0 in O(n) steps

time-complexity

modified Apr 8 at 22:33 Steven 14.4k

-1

votes

1

answer

31

views

Time Complexity when there is while loop

time-complexity

modified 2 days ago grus 11

1

vote

1

answer

24

views

What is the Number of Possible Nonequivalent Propositions with $P_1, P_2, P_3$ Using $\iff$ Operator?

logic propositional-logic

modified Apr 6 at 15:10 Nathaniel 1,893

0

votes

1

answer

39

views

Find offset and page number given paged virtual memory address

memory-management memory-access virtual-memory c

answered Apr 7 at 9:44 greybeard 814

0

votes

0

answers

39

views

Necessary or useful models/techniques for simulating natural evolution?

artificial-intelligence evolutionary-computing

modified 2 days ago lafinur 101

0

votes

0

answers

39

views

How to derive max amount of items from DP table of Knapsack problem?

dynamic-programming knapsack-problems

modified 39 mins ago Nikita 1

0

votes

1

answer

30

views

Randomized algorithm for minimum cut

randomized-algorithms minimum-cuts

modified Apr 8 at 16:22 Pål GD 10.4k

0

votes

0

answers

38

views

Converting python/numpy code into pseudocode

pseudocode

asked Apr 7 at 7:45 stevew 101

0

votes

0

answers

38

views

Eliminating ambiguity in $A \to AA \mid (A) \mid a$

context-free formal-grammars compilers ambiguity

modified Apr 8 at 10:30 Yuval Filmus 249k

-2

votes

0

answers

38

views

why aren't games developed by TRNG?

randomized-algorithms randomness computer-games

asked 2 days ago Monther 71

0

votes

1

answer

23

views

Church-Turing Thesis - the mechanical model - the turing machine- its limits and its equivalence with a modern digital computer

turing-machines computation-models church-turing-thesis

answered 13 hours ago D.W.♦ 130k

0

votes

2

answers

28

views

no of times partion is called in quick sort, assuming array is always halved

algorithms quicksort algorithm-design

answered 19 hours ago gnasher729 22.3k

1

vote

0

answers

35

views

Different PDA design processes — both valid?

automata context-free pushdown-automata

asked Apr 7 at 22:59 am2021 67

1

vote

1

answer

27

views

Dynamic programming: Maximize total value

dynamic-programming

modified Apr 7 at 18:25 Nathaniel 1,893

0

votes

1

answer

33

views

What is this turing machine doing

turing-machines

modified Apr 7 at 21:44 Nathaniel 1,893

1

vote

1

answer

20

views

Let $G$ be an undirected graph with $n$ nodes. Prove the following

graphs trees

answered 4 hours ago Elie 36

1

vote

1

answer

25

views

Why does taking advantage of locality matter in multithreaded systems?

concurrency process-scheduling cpu-pipelines

modified 19 hours ago gnasher729 22.3k

0

votes

0

answers

32

views

Compiler optimisation and dependent type programming

compilers dependent-types type-checking

asked Apr 6 at 12:00 thoughtpolice 205

Top Questions

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