Hottest Questions This Week

29

votes

13

answers

4k

views

What are some real world applications of graphs?

graphs

answered 15 hours ago Austin Hemmelgarn 151

4

votes

2

answers

463

views

Can 3-coloring be reduced to 3-clique?

modified May 23 at 8:02 WBT 103

4

votes

2

answers

327

views

Find the shortest path that goes through an even number of red edges

algorithms graphs dijkstras-algorithm

modified May 21 at 10:23 Especially Lime 241

2

votes

2

answers

261

views

What does the phrase “Simple For Loops” mean in computability theory?

computability recursion primitive-recursion

answered yesterday Yuval Filmus 226k

3

votes

3

answers

70

views

$\mathcal{G} = \{ v_2 v_4 \ldots v_{k} : v_1 v_2 v_3 v_4 \ldots v_{k-1} v_{k} \in \mathcal{L}, \text{ $k$ even} \} $ is context free language

context-free pushdown-automata closure-properties

answered May 22 at 17:30 Hendrik Jan 23.7k

2

votes

1

answer

138

views

Organizing a “speedback”

combinatorics functional-programming

modified May 22 at 12:58 Luís Soares 123

4

votes

1

answer

104

views

Prove finding k disjoint paths from n given paths in a directed graph is NP-complete

graphs np-complete np-hard polynomial-time-reductions directed-graphs

modified May 21 at 16:35 John L. 22.2k

3

votes

1

answer

77

views

Having trouble understanding a proof of Mahaney’s theorem

complexity-theory np-complete np-hard np satisfiability

modified May 21 at 12:47 Yuval Filmus 226k

0

votes

2

answers

57

views

Constructing a rectangle of size nx2 with dominos and L-shaped trominos

algorithms tiling

modified 10 hours ago John L. 22.2k

1

vote

0

answers

184

views

Channel coding and Error probability. Where are these probabilities from?

probability-theory coding-theory error-correcting-codes hamming-distance

asked May 23 at 3:08 Rapiz 51

0

votes

2

answers

50

views

Are all language over $\Sigma= \{0\}$ decidable?

formal-languages

answered 2 days ago gnasher729 18.6k

2

votes

3

answers

63

views

Are any two complexity classes equipped with an oracle to solve the halting problem equivalent?

complexity-theory oracle-machines

modified May 23 at 5:40 Bernardo Subercaseaux 191

2

votes

1

answer

59

views

What does Lambda Calculus teach us about data?

data-structures lambda-calculus computation-models

modified 10 hours ago Alex Zolotko 121

1

vote

2

answers

57

views

Detect cycles of odd total weight in a graph with {0,1}-weighted edges

graphs weighted-graphs

modified 2 days ago D.W.♦ 120k

2

votes

1

answer

53

views

Under what kind of oracles are $P$ and $NP$ equivalent?

halting-problem oracle-machines

modified 2 days ago Samuel Muldoon 105

1

vote

1

answer

66

views

Is co-P recursively enumerable?

polynomial-time enumeration

modified May 23 at 14:26 Steven 7,150

2

votes

3

answers

59

views

Little O notation relationship

time-complexity asymptotics runtime-analysis big-o-notation

answered May 20 at 18:45 Yuval Filmus 226k

1

vote

1

answer

45

views

If anything can be verified efficiently, must it be solvable efficiently on a Non-Deterministic machine?

complexity-theory nondeterminism

modified May 23 at 4:05 Bernardo Subercaseaux 191

4

votes

2

answers

74

views

Algorithm design: find any path in an undirected acyclic graph which has a total sum of the nodes as a specific value

graphs graph-traversal depth-first-search

answered 4 hours ago ryan 4,046

0

votes

2

answers

61

views

How do I prove that $3x^3 +2x + 1 $ is $\omega(x \cdot \log x) $

complexity-theory asymptotics proof-techniques complexity-classes landau-notation

modified May 22 at 0:54 Steven 7,150

-2

votes

1

answer

59

views

Wall Climbing Dynamic program

dynamic-programming

modified May 23 at 15:47 Steven 7,150

2

votes

1

answer

33

views

Determine whether removing a node on a graph will disconnect the graph

graphs connected

modified yesterday D.W.♦ 120k

1

vote

2

answers

41

views

is (infinitely often p) ∨ (infinitely often ¬p) valid?

formal-methods linear-temporal-logic

answered May 22 at 7:49 Yuval Filmus 226k

0

votes

2

answers

67

views

Is $MIN_{TM}$ not in $\overline{RE\cup coRE}$

turing-machines computability reductions

answered 2 days ago Doron Bruder 1

0

votes

1

answer

62

views

Hard Drive Seek Time using FIFO, SSF, SCAN

memory-hardware memory-access

modified May 22 at 13:19 PSKP 126

1

vote

1

answer

37

views

Solution of CLRS question 4.6-2

algorithm-analysis recurrence-relation

modified May 21 at 15:33 V K 185

2

votes

1

answer

44

views

Is there an algorithm to determine which face of an n-dimensional hypercube is closest to a given point in $O(n\log(n))$?

algorithms time-complexity computational-geometry big-o-notation

answered May 23 at 22:41 Oberdiah 31

1

vote

2

answers

34

views

Given a list of integers and a target integer, return the number of triplets whose product is the target integer and two adjacent triplets

algorithms data-structures arrays

modified May 20 at 13:52 Idonknow 133

1

vote

1

answer

43

views

Managing an hotel using AVL trees - Data Structures

time-complexity data-structures arrays avl-trees

modified 8 hours ago StackOMeow 13

1

vote

1

answer

33

views

Is solving a quadratic equation using Turing machine impossible?

complexity-theory turing-machines

answered May 22 at 19:49 Bernardo Subercaseaux 191

-1

votes

1

answer

25

views

Grammar with a long derivation generates an infinite language

formal-languages context-free formal-grammars

modified yesterday Frank 21

2

votes

2

answers

32

views

Median-of-Medians proof for time complexity

selection-problem

modified May 21 at 18:04 ryan 4,046

2

votes

1

answer

40

views

How to tell if a proof relativizes?

oracle-machines relativization

modified yesterday RingRing 165

2

votes

2

answers

24

views

Why double error correction and quadruple error detection cannot occur at the same time?

error-correcting-codes

modified May 22 at 15:28 Nurin Izzati Jafri 77

1

vote

1

answer

39

views

Turing machine with a finite tape after the input word ends

turing-machines

answered May 22 at 15:23 Yuval Filmus 226k

1

vote

3

answers

50

views

Why ASCII letter A has a Hamming Distance of 3?

hamming-code hamming-distance

modified May 22 at 0:05 John L. 22.2k

1

vote

1

answer

37

views

Substitution lemma for types

logic type-theory

answered yesterday Gilles 'SO- stop being evil' 38.2k

-2

votes

0

answers

47

views

dining philosophers problem with deadlock

algorithms operating-systems c

modified 2 days ago Dor 1

0

votes

1

answer

47

views

MST - algorithm to add an edge to the graph

algorithms graphs minimum-spanning-tree

modified yesterday 6005 2,798

0

votes

1

answer

36

views

Virtual Memory vs Cache for block identification

cpu-cache virtual-memory

answered May 24 at 3:47 Gabriel S 26

1

vote

1

answer

36

views

Languages A, B ∈ NP-complete such that A⋃B = Σ*

complexity-theory formal-languages np-complete

modified 2 days ago D.W.♦ 120k

0

votes

1

answer

46

views

Dynamic Program for Tree based question

dynamic-programming

modified 2 days ago Bernardo Subercaseaux 191

4

votes

0

answers

45

views

Decide whether two strings $x, y$ can be split into substrings $a,b,c$ such that $x=abc$ and $y=cba$

strings substrings

modified May 21 at 21:02 Karam Mohamed 101

2

votes

1

answer

35

views

Algorithm for splitting an array into k sub-arrays

algorithms data-structures arrays selection-problem

modified 2 days ago Steven 7,150

0

votes

1

answer

26

views

Data extaction vs information extraction

information-retrieval

answered May 21 at 10:51 Koenig Lear 453

1

vote

1

answer

26

views

PAC-learning definition

machine-learning

modified yesterday curlycharcoal 121

-1

votes

0

answers

42

views

Automata Regular Expression (a+b)

automata

asked May 20 at 8:51 Array 1

0

votes

1

answer

42

views

Same notation/terminology for union of sets and concatenation (Kleene star)?

formal-languages automata discrete-mathematics notation

answered May 23 at 13:54 Yuval Filmus 226k

Top Questions

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