Computer Science

Revival

 Revival
Answer more than 30 days after a question was asked as first answer scoring 2 or more. This badge can be awarded multiple times.
Awarded 1200 times.
Regular expression vs rational expression
Awarded yesterday
Invertability of Karp reductions
Awarded yesterday
Length of the certificate in complexity classes
Awarded Apr 7 at 11:36
Flow graph that requires pushing back flow in Ford Fulkerson
Awarded Apr 7 at 10:22
Two Vs Dual Port RAM
Awarded Mar 31 at 3:26
Are all instructions eventually converted to zero-operand instructions?
Awarded Mar 30 at 2:41
How does the half-integer spanning-tree problem contain the TSP?
Awarded Mar 28 at 16:30
Nodes reached with exactly $k$ steps in an undirected graph?
Awarded Mar 28 at 13:27
Is it possible to encode logical expression and interpret it with SQL?
Awarded Mar 19 at 10:48
Refine quickselect with Median of Medians to deal with duplicates
Awarded Mar 14 at 14:47
Are there problems in NP that would solve P vs NP, but are not NP complete
Awarded Mar 12 at 16:33
Max flow algorithm for floating-point weights and E~=10*V
Awarded Mar 12 at 14:03
What's the relationship between "semantic type soundness" and "functional correctness"?
Awarded Mar 11 at 21:48
O(m) time algorithm to check for a strongly connected graph
Awarded Mar 11 at 12:55
Proving why decreasing an edge weight in a graph may change it's MST by one edge
Awarded Mar 4 at 13:40
Uniform generation of random bipartite bi-regular graphs?
Awarded Feb 29 at 13:01
Named outputs of a function
Awarded Feb 28 at 21:10
Alternatives to SVD for rank factorization
Awarded Feb 24 at 7:56
Is the ABC-partition problem NP-hard?
Awarded Feb 23 at 17:12
Name of class of errors where the real state differs from the recorded state?
Awarded Feb 21 at 18:35
Convert the given NFA to DFA
Awarded Feb 21 at 12:11
What is the asymptotic bound for $T(n)= 3T(\sqrt[3]{n})+n^3$?
Awarded Feb 21 at 12:11
A Turing machine for which it is impossible to predict whether it halts or not on a fixed input
Awarded Feb 12 at 13:07
What is the definition of a redex and what are they for in programming languages literature?
Awarded Feb 9 at 6:47
Can the loops be in any order in the Floyd-Warshall algorithm?
Awarded Feb 5 at 12:33
Optimal flow in a network with non-constant edges' weights
Awarded Feb 1 at 12:55
Mapping reducibility from recursive to recursively enumerable language
Awarded Jan 23 at 22:57
Easy proof of IP ⊆ PSPACE for private coins
Awarded Jan 23 at 20:56
Is there such a thing as $coW[1]$-hardness?
Awarded Jan 14 at 5:02
Proving that $(A \cup B)^* = A^*(BA^*)^*$
Awarded Jan 13 at 1:09
ALL_{NFA} is PSPACE-complete
Awarded Jan 13 at 1:04
Is the set of all DFAs countable?
Awarded Jan 12 at 22:12
How to remove null production from context free grammar?
Awarded Jan 11 at 16:41
Finding missing edge weights in the context of minimum spanning tree
Awarded Jan 11 at 15:07
How to prove that {<M1, M2> : M1 and M2 are two DFAs and L(M1) $\neq$ L(M2)} is in NL?
Awarded Jan 6 at 20:48
Find a node with maximum distance from query node in a tree
Awarded Jan 1 at 22:35
Tail call optimization via translating to CPS
Awarded Jan 1 at 20:05
Sorting O(log n) elements in O(n) time
Awarded Dec 29, 2023 at 15:46
Algorithm question - check if there exists a path that touches A nodes exactly once and can revisit all other nodes
Awarded Dec 20, 2023 at 21:46
Parametrized threshold for LP Approximation in Vertex Cover Problem
Awarded Dec 16, 2023 at 9:17
When would it be optimal to use an Edge List as opposed to an Adjacency List / Matrix when representing a graph?
Awarded Dec 7, 2023 at 17:12
how to prove correctness of this BFS algorithm?
Awarded Dec 7, 2023 at 3:15
How to determine the maximum valued play in Rummikub?
Awarded Dec 3, 2023 at 13:41
Prove ALL$_{\text{TM}}$ is undecidable reduction problem
Awarded Dec 3, 2023 at 13:33
Incomplete definition of function- first order logic
Awarded Nov 28, 2023 at 15:35
"Fuzzy" Chinese Remainder Theorem
Awarded Nov 28, 2023 at 4:19
EQtm is not mapping reducible to its complement
Awarded Nov 17, 2023 at 6:19
challenge: Closing hash, linear probing, probe length 1
Awarded Nov 11, 2023 at 22:31
Hoare's Partition Scheme Stuck
Awarded Nov 9, 2023 at 17:16
Expression with fastest growth in lambda-calculus
Awarded Nov 9, 2023 at 8:42
Given a set, partition it into ordered triples
Awarded Nov 8, 2023 at 21:50
Is there any practical trick to mentally count in Gray code?
Awarded Oct 31, 2023 at 15:16
Partitioning a graph into connected pairs and triplets
Awarded Oct 27, 2023 at 9:17
How to maintain completely dynamic convex hull quickly?
Awarded Sep 25, 2023 at 10:35
Shamos-Hoey Line segment intersection runtime
Awarded Sep 25, 2023 at 10:35
State Machines as Functors
Awarded Sep 21, 2023 at 20:52
Why is KMP preprocessing O(N)?
Awarded Sep 19, 2023 at 20:37
How to provide a reduction from 3SAT to domatic number problem
Awarded Sep 12, 2023 at 22:42
Compiler that compiles to a Turing machine?
Awarded Sep 6, 2023 at 7:15
How to handle coplanarity in convex hull?
Awarded Aug 16, 2023 at 17:16
1
2 3 4 5
…
20