templatetypedef's user avatar
templatetypedef's user avatar
templatetypedef's user avatar
templatetypedef
  • Member for 10 years, 3 months
  • Last seen this week
224 votes
Accepted

BIT: What is the intuition behind a binary indexed tree and how was it thought about?

27 votes

How does a computer work?

20 votes

How to show that a "reversed" regular language is regular

16 votes
Accepted

Are regular expressions $LR(k)$?

15 votes
Accepted

Does a never-halting machine always loop?

13 votes
Accepted

What is practical difference between NP and PSPACE-complete?

11 votes

Is there a meaningful difference between O(1) and O(log n)?

11 votes

Which Grows Faster: Factorial or Double Exponentiation

10 votes
Accepted

$O(\frac{\log n}{\log \log n})$ algorithm for the prefix parity problem

9 votes

A polynomial reduction from any NP-complete problem to bounded PCP

9 votes

Solving or approximating recurrence relations for sequences of numbers

9 votes
Accepted

How to discuss coefficients in big-O notation

9 votes

Time complexity of an algorithm: Is it important to state the base of the logarithm?

8 votes
Accepted

Computing with the Monster

8 votes
Accepted

Help reducing 3-SAT to 3-COLORING

7 votes

Best and worse case inputs for heap sort and quick sort?

7 votes

Are there NP problems, not in P and not NP Complete?

7 votes

How do I find the max and min value of an array in 3n/2−2 comparisons?

7 votes

Would creating a complete computer simulation of the human brain prove the Church-Turing thesis?

6 votes
Accepted

Get the running time of forest disjoint sets

5 votes

Analog of PP for computability rather than complexity?

5 votes
Accepted

When did $LR(k)$ acquire the meaning "left-to-right scan, rightmost derivation?"

5 votes

Depth first or breadth first ordering in binary search trees?

5 votes

Why is the path compression (no rank) for disjoint sets $O(\log n)$ amortized for Find-Set?

5 votes

Hash table collisions: why use a linked list if we can use a hash set?

5 votes

Equivalence of regular grammars

5 votes

Do functions with slower growth than inverse Ackermann appear in runtime bounds?

4 votes

What do you call a DAG with a single root/source?

4 votes
Accepted

Proof of decidability of determining whether a DFA accepts a string

4 votes

Give a grammar for a language on Σ={a,b,c} that accepts all strings containing exactly one a