Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.

Sign up to join this community

Anybody can ask a question

Anybody can answer

The best answers are voted up and rise to the top

Explore our Questions

Ask Question

more tags

Active 4 Bountied Hot Week Month

0

votes

1

answer

999

views

given a weighted, directed graph. Give an O(VE)-time algorithm to find, for each vertex v∈V, the value δ∗(v)=Min u∈V{δ(u,v)}?

algorithms graphs shortest-path

modified 1 hour ago Community♦ 1

0

votes

1

answer

33

views

Is this Language decidable?

turing-machines undecidability

answered 2 hours ago Steven 9,640

43

votes

12

answers

13k

views

Is C actually Turing-complete?

computability turing-completeness c

modified 2 hours ago polcott 149

0

votes

0

answers

12

views

Understand vertex cover problem

linear-programming vertex-cover

asked 2 hours ago Niklas R. 903

0

votes

1

answer

33

views

Converting a Mixed SUBSET-SUM Problem To All-Positive Case

subset-sum polynomial-time-reductions

modified 3 hours ago Community♦ 1

1

vote

2

answers

369

views

Variant of the Knapsack Problem

algorithms complexity-theory knapsack-problems integer-programming

modified 4 hours ago Community♦ 1

0

votes

0

answers

7

views

Semantics of “write-once” variables for complex data structures

programming-languages type-theory semantics syntax variable-binding

asked 4 hours ago phipsgabler 310

0

votes

1

answer

6

views

Bottom-up Mergesort vs Natural Merge Sort

algorithms sorting mergesort

answered 4 hours ago BearAqua 584

0

votes

1

answer

28

views

Equivalence of two definitions of mutual information

information-theory

modified 5 hours ago Community♦ 1

0

votes

2

answers

1k

views

Show that the single-tape TMs that can not write on the portion the portion of the tape containing the input string recognize only regular languages

complexity-theory turing-machines computability

modified 5 hours ago xdavidliu 278

1

vote

1

answer

22

views

How to convert a recursive function to a non recursive one using stack while keeping memoization?

algorithms optimization recursion stacks memoization

modified 6 hours ago Yago Tomé 11

0

votes

2

answers

45

views

Complexity of Subset Sum where the size of the subset is specified

complexity-theory np-complete subset-sum

modified 7 hours ago Community♦ 1

2

votes

0

answers

19

views

How to efficiently handle racing conditions when synchronising a tags list over the network?

computer-networks synchronization

modified 8 hours ago caveman 121

2

votes

0

answers

111

views

First circuit size lower bound ever

algorithms complexity-theory time-complexity circuits boolean-algebra

modified 11 hours ago Dudi Frid 261

Browse more Questions

Computer Science Stack Exchange works best with JavaScript enabled