Computer Science

Excavator

 Excavator
Edit first post that was inactive for 6 months.
Awarded 510 times.
Do theorem provers demonstrate their own correctness?
Awarded 5 hours ago
Is path induction constructive?
Awarded Jan 14 at 4:56
Does every problem in NP have an exponential time algorithm?
Awarded Jan 11 at 5:18
Why is Radix Sort $O(n)$?
Awarded Dec 22 '21 at 5:35
Advantages of amortized analysis
Awarded Dec 13 '21 at 4:16
How fast can we find all Four-Square combinations that sum to N?
Awarded Dec 2 '21 at 4:34
Show that the single-tape TMs that can not write on the portion of the tape containing the input string recognize only regular languages
Awarded Nov 28 '21 at 6:02
CISC and RISC - synchronous and asynchronous
Awarded Nov 21 '21 at 3:40
Generate all permutations of 1 to n with i stacks
Awarded Nov 20 '21 at 6:06
QuickSort Dijkstra 3-Way Partitioning: why the extra swapping?
Awarded Nov 16 '21 at 6:31
Best and worse case inputs for heap sort and quick sort?
Awarded Nov 16 '21 at 6:31
Show that any monotone Boolean function is computable by a circuit containing only AND and OR gates
Awarded Nov 16 '21 at 6:31
Relation beetween log-space reduction and polynomial time reduction
Awarded Nov 10 '21 at 5:16
Why do more powerful programming languages tend to have slower implementations?
Awarded Oct 29 '21 at 5:37
CFG to CNF conversion steps
Awarded Oct 28 '21 at 5:15
Does spanning tree make sense for DAG?
Awarded Oct 27 '21 at 4:34
Guessing the smallest unique positive integer
Awarded Oct 18 '21 at 4:17
What is the difference between an algorithm, a language and a problem?
Awarded Oct 6 '21 at 6:00
What is the definition of P, NP, NP-complete and NP-hard?
Awarded Oct 3 '21 at 6:51
Decidable languages kleene star closure - question on a proof
Awarded Oct 3 '21 at 6:51
How does the NegaScout algorithm work?
Awarded Oct 2 '21 at 6:46
When is a regexp not a Regular Expression?
Awarded Oct 2 '21 at 6:46
Binary search algorithm - worst-case complexity
Awarded Sep 23 '21 at 4:17
For $T(n) = 16T(n/4) + n^2\lg^3n$ prove: $T(n) = \Theta(n^2\lg^3n)$
Awarded Aug 10 '21 at 7:31
Can any computably enumerable set be generated by a prefix-free set?
Awarded Jul 31 '21 at 4:11
Show that $L = \{1^n w 1^n | n > 0 \text{ and } w ∈ \{0,1\}^*\}$ is regular
Awarded Jun 15 '21 at 4:27
Are LR(k) languages and DCFLs equivalent?
Awarded Jun 9 '21 at 5:27
CFG that generates $1^*$ is decidable
Awarded Jun 3 '21 at 5:10
Without Rare Metals
Awarded Jun 2 '21 at 4:15
Circuits for Modular Arithmetic
Awarded May 30 '21 at 4:04
How to generate, validate, and invalidate a set/list of numbers in O(1) time and space?
Awarded May 26 '21 at 4:35
Is there a complexity metric for finite state machines?
Awarded May 26 '21 at 4:35
Does two languages being in P imply reduction to each other?
Awarded May 21 '21 at 4:21
Find a weighted median for unsorted array in linear time
Awarded May 17 '21 at 4:31
Proving that recursively enumerable languages are closed against taking prefixes
Awarded May 15 '21 at 4:45
How can there be undecidable languages in P/1?
Awarded Apr 28 '21 at 4:07
Solving $T(n) = 3T(\frac{n}{3})+\sqrt{n}$ using master method
Awarded Apr 23 '21 at 4:26
NFA with exponential number of states when determinized
Awarded Apr 22 '21 at 6:14
There are pretty much no algorithms in P
Awarded Apr 22 '21 at 6:14
Floyd's Cycle detection algorithm | Determining the starting point of cycle
Awarded Apr 20 '21 at 8:53
Existence of non-context free but decidable languages
Awarded Apr 20 '21 at 8:53
Half-SAT intractability proof
Awarded Apr 16 '21 at 5:42
What is the definition of P, NP, NP-complete and NP-hard?
Awarded Apr 10 '21 at 5:12
Proving that the shortest simple path problem between two vertices $s$ and $t$ in a graph is NP-complete
Awarded Apr 7 '21 at 5:47
What is a forwarding pointer? [closed]
Awarded Apr 5 '21 at 4:06
Which research languages have a stronger typesystem than Haskell and why?
Awarded Mar 22 '21 at 5:25
(post deleted or otherwise unavailable)
Awarded Mar 21 '21 at 4:08
Why are so many internet protocols text-based?
Awarded Mar 19 '21 at 4:32
Checking equality of integers: O(1) in C but O(log n) in Python 3?
Awarded Mar 13 '21 at 4:26
Minimum number of processes for the deadlock?
Awarded Mar 5 '21 at 6:51
Why are CFLs not closed under intersection?
Awarded Mar 3 '21 at 4:56
Instruction Set Architecture (ISA) design
Awarded Mar 1 '21 at 5:33
Can I simplify log(n+1) before showing that it is in O(log n)?
Awarded Feb 26 '21 at 4:15
Is a balanced binary tree a complete binary tree?
Awarded Feb 22 '21 at 4:17
Is "super-exponential" a precise definition of algorithmic complexity?
Awarded Feb 20 '21 at 6:33
What's the difference between a stream and a queue?
Awarded Feb 18 '21 at 4:20
Difference between Turing machine and Universal Turing machine
Awarded Feb 17 '21 at 5:49
A reference for pseudocode for Monge-Elkan algorithm?
Awarded Jan 31 '21 at 5:01
What is decider?
Awarded Jan 28 '21 at 4:21
Finding Permutations with Exclusions
Awarded Jan 21 '21 at 4:40
1
2 3 4 5
…
9

Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.