User xdavidliu - Computer Science Stack Exchange

7 votes

Algorithm to find diameter of a tree using BFS/DFS. Why does it work?

answered Jan 15, 2018 at 5:27

6 votes

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

answered Aug 24, 2020 at 20:18

5 votes

Undecidability of "is this CFG prefix-free?"

answered Oct 12, 2020 at 1:32

3 votes

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

answered Oct 25, 2020 at 16:29

3 votes

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

answered Jan 1, 2018 at 17:31

2 votes

Decidability of halting problem for DPDAs with $\epsilon$-transitions?

answered Sep 16, 2020 at 23:42

2 votes

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

answered Jan 15, 2018 at 22:50

2 votes

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

answered Jan 21, 2018 at 12:22

1 vote

Matrix rank only adding single row

answered Sep 19, 2020 at 17:06

1 vote

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

answered Nov 26, 2020 at 19:00

1 vote

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

answered Dec 27, 2020 at 5:29

1 vote

Finding all vertices on negative cycles

answered Dec 27, 2020 at 20:22

1 vote

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

answered Jan 3, 2021 at 2:33

1 vote

Linear programming formulation for the single-source shortest path problem

answered Apr 22, 2021 at 2:32

1 vote

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

answered May 16, 2021 at 3:11

0 votes

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

answered May 26, 2021 at 23:15

0 votes

EQtm is not mapping reducible to its complement

answered Oct 20, 2020 at 5:25

0 votes

Example of two undecidable languages that cannot be mapping reduced to each other

answered Oct 24, 2020 at 20:42

0 votes

Show a TM-recognizable language of TMs can be expressed by TM-description language of equivalent TMs

answered Aug 22, 2020 at 14:58

Stack Exchange Network

19 Answers

Algorithm to find diameter of a tree using BFS/DFS. Why does it work?

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

Undecidability of "is this CFG prefix-free?"

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

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

Decidability of halting problem for DPDAs with $\epsilon$-transitions?

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

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

Matrix rank only adding single row

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

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

Finding all vertices on negative cycles

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

Linear programming formulation for the single-source shortest path problem

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

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

EQtm is not mapping reducible to its complement

Example of two undecidable languages that cannot be mapping reduced to each other

Show a TM-recognizable language of TMs can be expressed by TM-description language of equivalent TMs