Hottest Questions This Week

5

votes

1

answer

834

views

Dijkstra with max instead of sum

answered 2 days ago Artur Riazanov 201

2

votes

2

answers

201

views

How to prove LastToken problem is NP-complete

complexity-theory np-complete decision-problem

answered yesterday Toin321 1

3

votes

2

answers

143

views

Why is the assignment rule the way it is in Hoare Logic?

programming-languages logic semantics software-verification hoare-logic

answered yesterday chi 13.4k

6

votes

2

answers

59

views

Voronoi Diagram Drawing Variations and Charateristics

algorithms computational-geometry discrete-mathematics voronoi-diagrams

answered 2 days ago Yves Daoust 1,937

5

votes

1

answer

88

views

Voronoi Cell and Voronoi Diagram

algorithms computational-geometry discrete-mathematics voronoi-diagrams

answered Dec 9 at 22:01 Tassle 1,107

5

votes

1

answer

69

views

Minimum edge weight k-exact cover with triangle inequality

graphs weighted-graphs

modified Dec 8 at 11:25 narek Bojikian 2,261

3

votes

1

answer

101

views

Regular expression for strings not starting with 10

regular-languages regular-expressions

modified Dec 7 at 12:29 Hendrik Jan 23.1k

1

vote

1

answer

127

views

Proving NP-Complete problem by reduction of subset-sum

complexity-theory reductions

modified Dec 7 at 14:16 narek Bojikian 2,261

3

votes

2

answers

62

views

Can a Non-Deterministic Pushdown Automaton recognize $ \# a^nb^{2^n} \# $ which a TM can?

turing-machines pushdown-automata

modified Dec 9 at 13:19 Aaron Rotenberg 555

0

votes

1

answer

46

views

Which sort algorithm to choose given two specific arrays?

algorithms sorting arrays

answered Dec 6 at 13:51 Tassle 1,107

2

votes

1

answer

58

views

How to solve $T(n)= 4T(\sqrt n) +\log^2n$?

recurrence-relation master-theorem

modified Dec 8 at 20:54 TheSimpliFire 162

1

vote

2

answers

45

views

Prove the Droid Trader Problem is NP-complete

complexity-theory np-complete reductions

answered Dec 9 at 12:29 xskxzr 5,575

5

votes

1

answer

57

views

Near Triangulation Planar Graph

algorithms graphs computational-geometry discrete-mathematics planar-graphs

modified 2 days ago narek Bojikian 2,261

2

votes

1

answer

65

views

Converting connected graph to disconnected graph by removing minimum vertices

algorithms graphs

answered Dec 8 at 11:52 Yuval Filmus 214k

5

votes

0

answers

81

views

Placing a tripod in a plane such that it partition a given set of points (with pic)

algorithms graphs computational-geometry discrete-mathematics voronoi-diagrams

modified yesterday AlgorithmUser785 131

3

votes

1

answer

35

views

Prove vertices of polygon are endpoints of disjoint line segments

algorithms computational-geometry discrete-mathematics

answered 2 days ago Tassle 1,107

2

votes

1

answer

55

views

Why is IDA$^$ faster than A$^$? Why does IDA$^$ visit more nodes than A$^$?

algorithms search-algorithms artificial-intelligence

modified Dec 6 at 11:26 Carlos Linares López 3,076

0

votes

1

answer

88

views

Using a polynomial-time Boolean formula program to evaluate Boolean circuits [closed]

algorithms np-complete np

answered Dec 7 at 4:25 tradewinds 53

2

votes

2

answers

41

views

Does any algorithm loops at some point?

algorithms turing-machines finite-automata loops

modified 2 days ago Gianluca Ghettini 123

1

vote

1

answer

39

views

How do I use message passing to find the maximum of all values in a grid?

algorithms distributed-systems parallel-computing message-passing

modified Dec 7 at 17:00 greybeard 546

3

votes

1

answer

38

views

Dynamic length of union of segments (1d Klee's measure problem)

algorithms computational-geometry

modified Dec 7 at 22:16 David 33

0

votes

0

answers

60

views

Minimizing the distance from a set of nodes in a tree

dynamic-programming

modified yesterday maverick98 65

2

votes

1

answer

22

views

How does a dual core microprocessors run so many programs?

dynamic-programming memory-hardware process-scheduling threads multi-tasking

answered Dec 9 at 20:46 ss09 61

0

votes

1

answer

35

views

How to divide an unsorted list in linear time where every element in the first part is smaller than every element in the second list

algorithms algorithm-analysis data-structures time-complexity

modified 2 days ago Xi N 53

2

votes

2

answers

35

views

Joining line segments to make tree

algorithms graphs computational-geometry trees discrete-mathematics

answered yesterday Tassle 1,107

1

vote

1

answer

44

views

Why in the code i ≃ n?

algorithms notation

modified 2 days ago Yamar69 974

1

vote

1

answer

34

views

Algorithm for idempotent algebra

complexity-theory np-complete boolean-algebra oracles

modified Dec 8 at 17:29 D.W.♦ 112k

2

votes

2

answers

34

views

Knapsack with a fixed number of weights

greedy-algorithms knapsack-problems

modified Dec 8 at 22:47 gnasher729 16.1k

0

votes

1

answer

43

views

NP-completeness for integer linear program

np-complete reductions decision-problem

modified yesterday Aaron Rotenberg 555

0

votes

1

answer

33

views

Does quantum computing convert any O(2^n) algorithm into a polynomial running time and how?

quantum-computing

modified yesterday Ordoshsen 363

4

votes

0

answers

53

views

Assign n people to m rooms of different sizes, such that noone is alone

algorithms dynamic-programming assignment-problem

modified Dec 7 at 21:50 D.W.♦ 112k

0

votes

0

answers

52

views

What's the problem of Learning Algorithms used for Automated Theorem Provers?

proof-assistants automated-theorem-proving

modified Dec 8 at 18:42 D.W.♦ 112k

0

votes

1

answer

51

views

Given a boolean matrix A of size n, A^p can be computed in space O(log n log p)

complexity-theory space-complexity

answered 2 days ago D.W.♦ 112k

0

votes

1

answer

28

views

Does Warnsdorff’s algorithm for Knight’s tour problem always gives complete tour

algorithms time-complexity optimization backtracking

answered Dec 9 at 18:45 Juho 18.2k

2

votes

1

answer

35

views

Proof that $(L_{all})^C$ is not recursively enumerable

complexity-theory turing-machines

modified Dec 9 at 16:58 Yuval Filmus 214k

0

votes

1

answer

35

views

Validity of self refering state with linear temporal logic 'X' connective

linear-temporal-logic

answered 9 hours ago DCTLib 2,407

0

votes

1

answer

27

views

What is the relation between a programming language and the language of its input?

formal-languages context-free programming-languages context-sensitive

modified yesterday chi 13.4k

2

votes

1

answer

57

views

What is the problem in this Turing Machine that describes $a^nb^{2^n}$?

turing-machines

modified 19 hours ago André Souza Lemos 2,992

1

vote

1

answer

43

views

Independent set problem

complexity-theory np-complete

answered Dec 9 at 18:43 Pål GD 7,425

1

vote

2

answers

33

views

graph theory proof or disproving

graphs

modified Dec 6 at 17:38 Arkajyoti Banerjee 84

1

vote

1

answer

33

views

Why is $T(n)=3T(n/4) + n\log n$ solvable with Master Method but $T(n)=2T(n/2) + n\log n$ is not?

algorithm-analysis asymptotics runtime-analysis recurrence-relation

modified Dec 8 at 8:08 Yuval Filmus 214k

3

votes

0

answers

42

views

Max nodes whose value exceeds all neighbors

algorithms graphs trees

modified Dec 9 at 2:27 narek Bojikian 2,261

0

votes

1

answer

42

views

Simple algorithm to code

algorithms

modified 2 days ago greybeard 546

1

vote

0

answers

42

views

PSPACE-hardness of the unbounded puzzle

complexity-theory reductions space-complexity

modified Dec 9 at 19:45 carpenter 111

1

vote

1

answer

25

views

doubt in pipelining

computer-architecture operating-systems

modified Dec 7 at 23:32 gnasher729 16.1k

0

votes

1

answer

40

views

Convert ambiguous grammar to unambiguous and SLR(1)

formal-grammars parsers ambiguity

answered yesterday rici 5,665

0

votes

1

answer

30

views

Difference between a skiplist and an Indexable skiplist

algorithms time-complexity search-algorithms lists

answered Dec 6 at 4:06 Matt Groff 745

0

votes

0

answers

38

views

A question about Pipeline Cycle

computer-architecture cpu-pipelines

modified 14 hours ago ChristiePPP 1

Top Questions

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