Computer Science

Excavator

 Excavator
Edit first post that was inactive for 6 months.
Awarded 599 times.
To prove 4-SAT CNF is NP-complete [closed]
Awarded yesterday
Prove correctness of in-order tree traversal subroutine
Awarded yesterday
minimizing the summed cardinality of set unions
Awarded yesterday
How to calculate the dimension of a convex polyhedron?
Awarded Mar 23 at 4:30
Show that { xy ∣ |x| = |y|, x ≠ y } is context-free
Awarded Mar 19 at 4:47
Proving that any CF language over a 1 letter alphabet is regular
Awarded Mar 4 at 6:03
Does the circuit value problem require only log space in alternating Turing machines
Awarded Feb 24 at 4:26
Whats the point of caching if the minimum single clock cycle time is the prorogation delay of the slowest component (fetching from DRAM)?
Awarded Feb 22 at 4:17
Breadth-first forest
Awarded Feb 22 at 4:17
Is finding arbitrary-but-fixed length cycles in a graph NP-Hard?
Awarded Feb 22 at 4:17
For $T(n) = 16T(n/4) + n^2\lg^3n$ prove: $T(n) = \Theta(n^2\lg^3n)$
Awarded Feb 21 at 12:27
Do Karnaugh maps yield the simplest solution possible?
Awarded Feb 17 at 6:01
Why does case 3 regularity condition of master theorem always hold when f(n)=$n^k$ and f(n)=$\Omega(n^{\log_b a+\epsilon})$
Awarded Jan 10 at 5:05
Algorithm for display nodes of a particular node based on in-degree and out-degree
Awarded Jan 10 at 5:05
A string that contains aabb, does this work?
Awarded Jan 6 at 5:56
What's the difference between subtyping and inheritance?
Awarded Dec 15, 2023 at 4:26
Why does space(n) <= time(n) imply that TIME(f(n)) is a subset of SPACE(f(n))?
Awarded Dec 8, 2023 at 6:27
How is Memory Segmentation done in 8086?
Awarded Dec 8, 2023 at 6:27
Does PETSc really give speedup?
Awarded Dec 1, 2023 at 4:41
Proof that median of an array is the number that minimizes the sum of manhattan distance to all points
Awarded Dec 1, 2023 at 4:41
Data Structure for Set Intersection?
Awarded Dec 1, 2023 at 4:41
Show that any monotone Boolean function is computable by a circuit containing only AND and OR gates
Awarded Nov 28, 2023 at 16:23
What would be the practical consequences of ZPP=exptime
Awarded Nov 5, 2023 at 4:16
Maximum sub-matrix sum
Awarded Oct 25, 2023 at 4:08
BIT: What is the intuition behind a binary indexed tree and how was it thought about?
Awarded Oct 25, 2023 at 4:08
Complexity class of Matrix Inversion
Awarded Oct 25, 2023 at 4:08
Are there any algorithms that decide if a PDA (pushdown automaton) accepts a sentence?
Awarded Oct 5, 2023 at 4:58
The meaning of discount factor on reinforcement learning
Awarded Sep 7, 2023 at 4:35
Are all irregular languages infinite?
Awarded Sep 3, 2023 at 4:11
Confused about Turing Recognizability
Awarded Sep 1, 2023 at 5:35
Calculate shortest cycle that contains node $s$
Awarded Aug 26, 2023 at 5:45
Having trouble calculating the asymptotic running time of MAX-HEAPIFY
Awarded Aug 12, 2023 at 6:31
Why doesn't the Needleman-Wunsch algorithm find solutions that begin with a gap?
Awarded Aug 10, 2023 at 19:05
Algorithm to find diameter of a tree using BFS/DFS. Why does it work?
Awarded Aug 4, 2023 at 6:03
Do all computers use parity checking? When does it happen?
Awarded Jul 27, 2023 at 5:09
Why do Karnaugh maps work?
Awarded Jul 27, 2023 at 5:09
Initial temperature in simulated annealing algorithm
Awarded Jul 27, 2023 at 5:09
Algorithm Asymptotic Analysis
Awarded Jul 27, 2023 at 5:09
Finding the runtime out of a recursion formula when using divide-and-conquer
Awarded Jul 27, 2023 at 5:09
Single queue instruction issuing in computer architecture
Awarded Jul 27, 2023 at 5:09
Interval Scheduling Problem with more than One Resource
Awarded Jul 27, 2023 at 5:09
Double Hashing with Strings as key
Awarded Jul 19, 2023 at 4:46
Context Sensitive Grammar for the language $\{a^nb^nc^n\mid n≥1\}$
Awarded Jul 14, 2023 at 8:33
Asymptotic Relationship between $\frac{1}{n}$ and $\frac{1}{2^n}$
Awarded Jun 23, 2023 at 5:31
Relationship between NP and CoNP
Awarded Jun 22, 2023 at 5:41
What does it mean to "strengthen the precondition and weaken the postcondition" in Hoare logic?
Awarded Jun 22, 2023 at 5:41
Is $B=\{a^n b^m \mid n \not= 2m\}$ a context free grammar
Awarded Jun 4, 2023 at 4:26
Turing Machines: What is the difference between recognizing, deciding, total, accepting, rejecting?
Awarded May 30, 2023 at 5:55
show for any Languages $L_1$ and $L_2$ exists a Language $L$ with $L_1 \leq_{log} L$ and $L_2 \leq_{log} L$
Awarded May 20, 2023 at 4:17
Proof: is the language $L_1=\{\langle M\rangle\mid\emptyset \subseteq L(M)\}$ (un)-decidable?
Awarded May 18, 2023 at 4:08
Are there lossless data compression techniques that do not exploit repetitive patterns?
Awarded Apr 19, 2023 at 4:15
why does ${a^nb^n}$ fit the pumping lemma for context-free languages?
Awarded Mar 1, 2023 at 6:27
How to cover given entries in a matrix with minimum number of rows and columns?
Awarded Feb 22, 2023 at 2:03
Counter automata with a bound on the counters?
Awarded Feb 19, 2023 at 4:07
What defines how many lookahead a lexer has?
Awarded Feb 15, 2023 at 4:36
Is the halting problem theorem really proven
Awarded Feb 15, 2023 at 4:36
Proving that the shortest simple path problem between two vertices $s$ and $t$ in a graph is NP-complete
Awarded Feb 9, 2023 at 5:07
Why product type is a dependent SUM?
Awarded Feb 7, 2023 at 4:35
Time complexity of a 2-heap question
Awarded Jan 20, 2023 at 5:28
Finding the frequency of each unique value of an attribute in a relation (RELATIONAL ALGEBRA)
Awarded Jan 20, 2023 at 5:28
1
2 3 4 5
…
10