User xdavidliu - Computer Science Stack Exchange

5 votes

2 answers

2k views

is it possible to determine using a single depth-first search, in O(V+E) time, whether a directed graph is singly connected?

asked Jan 15, 2018 at 22:28

4 votes

1 answer

810 views

Undecidability of "is this CFG prefix-free?"

asked Oct 11, 2020 at 23:54

3 votes

0 answers

409 views

is it decidable whether a grammar in Chomsky normal form has useless rules?

asked Oct 12, 2020 at 17:55

3 votes

1 answer

206 views

NP completeness of deciding whether a set of examples, consisting of strings and states, has a corresponding DFA?

asked May 16, 2021 at 23:38

2 votes

1 answer

216 views

Unsure why (or whether?) a certain algorithm correctly computes a Minimum spanning tree

asked Dec 27, 2020 at 3:11

2 votes

2 answers

353 views

how does Kleene-Post show two languages that are not Turing reducible to each other?

asked Oct 24, 2020 at 20:22

2 votes

1 answer

901 views

monotonically increasing codeword length in optimal (maybe Huffman) code for alphabet with monotonically decreasing frequencies

asked Jan 21, 2018 at 2:55

2 votes

2 answers

2k views

how to bound the probability that quicksort takes greater than n lg n time?

asked Jan 1, 2018 at 15:25

1 vote

0 answers

208 views

why does message authentication using 2-universal family of hash functions require a prime number of possible hash values?

asked Dec 26, 2017 at 2:36

1 vote

2 answers

226 views

walk / traverse a disjoint set that has union rank and path compression

asked Nov 26, 2020 at 18:23

1 vote

0 answers

81 views

efficient DELETE in proto-Van Emde Boas Tree?

asked Dec 17, 2020 at 21:26

1 vote

1 answer

332 views

why does the poly-time reduction from dominating set to vertex cover require adding a vertex to every edge?

asked May 16, 2021 at 2:44

0 votes

1 answer

743 views

Vertices reachable from negative-weight cycles in Bellman-Ford

asked Dec 27, 2020 at 20:17

0 votes

0 answers

304 views

What is the significance of Bellman-Ford and linear programming for scheduling and makespans?

asked Dec 29, 2020 at 4:12

0 votes

1 answer

74 views

why does relabel take O(VE) time total for unit capacity flow networks?

asked Jan 3, 2021 at 2:05

Stack Exchange Network

15 Questions

is it possible to determine using a single depth-first search, in O(V+E) time, whether a directed graph is singly connected?

Undecidability of "is this CFG prefix-free?"

is it decidable whether a grammar in Chomsky normal form has useless rules?

NP completeness of deciding whether a set of examples, consisting of strings and states, has a corresponding DFA?

Unsure why (or whether?) a certain algorithm correctly computes a Minimum spanning tree

how does Kleene-Post show two languages that are not Turing reducible to each other?

monotonically increasing codeword length in optimal (maybe Huffman) code for alphabet with monotonically decreasing frequencies

how to bound the probability that quicksort takes greater than n lg n time?

why does message authentication using 2-universal family of hash functions require a prime number of possible hash values?

walk / traverse a disjoint set that has union rank and path compression

efficient DELETE in proto-Van Emde Boas Tree?

why does the poly-time reduction from dominating set to vertex cover require adding a vertex to every edge?

Vertices reachable from negative-weight cycles in Bellman-Ford

What is the significance of Bellman-Ford and linear programming for scheduling and makespans?

why does relabel take O(VE) time total for unit capacity flow networks?