templatetypedef
  • Member for 9 years, 6 months
  • Last seen more than a week ago
BIT: What is the intuition behind a binary indexed tree and how was it thought about?
Accepted answer
215 votes

Intuitively, you can think of a binary indexed tree as a compressed representation of a binary tree that is itself an optimization of a standard array representation. This answer goes into one ...

View answer
How does a computer work?
26 votes

The complete picture is fairly complicated. There are many layers built on top of one another that collectively implement high-level abstractions on top of electrical voltages. There is no simple ...

View answer
How to show that a "reversed" regular language is regular
19 votes

To add to the automata-based transformations described above, you can also prove that regular languages are closed under reversal by showing how to convert a regular expression for $L$ into a regular ...

View answer
Are regular expressions $LR(k)$?
Accepted answer
16 votes

All regular languages have LL(1) grammars. To obtain such a grammar, take any DFA for the regular language (perhaps by doing the subset construction on the NFA obtained from the regular expression), ...

View answer
Does a never-halting machine always loop?
Accepted answer
15 votes

Consider the TM that always moves the tape head to the right and prints a special non-blank tape symbol at each step. This means that the TM never halts, since it always moves to the right, and never ...

View answer
What is practical difference between NP and PSPACE-complete?
Accepted answer
13 votes

I think it depends on what you're interested in. If you're looking for an exact solution to a problem and you hear that it's either NP-hard or PSPACE-hard, then in either case you won't be able to ...

View answer
Which Grows Faster: Factorial or Double Exponentiation
11 votes

You noted in your question that $n^n$ grows faster than $n!$, and that’s a great starting point for comparing the growth of $2^{3^n}$ and $n!$. Specifically, let’s ask - of $n^n$ and $2^{3^n}$, which ...

View answer
Is there a meaningful difference between O(1) and O(log n)?
11 votes

There are actually all sorts of cases where $\log n$ gets way bigger than 100. For example, if you're working with variable-length integers - say, for cryptography - $\log n$ represents the number of ...

View answer
$O(\frac{\log n}{\log \log n})$ algorithm for the prefix parity problem
Accepted answer
10 votes

I did a quick read over the paper you linked. Based on the ideas given in that paper, here's a simple data structure that obtains an $O(\frac{\log n}{\log\log n})$ time bound on each operation. You ...

View answer
Time complexity of an algorithm: Is it important to state the base of the logarithm?
9 votes

In most cases, it's safe to drop the base of the logarithm because, as other answers have pointed out, the change-of-basis formula for logarithms means that all logarithms are constant multiples of ...

View answer
How to discuss coefficients in big-O notation
Accepted answer
9 votes

Big-$O$ and big-$\Theta$ notations hide coefficients of the leading term, so if you have two functions that are both $\Theta(n^2)$ you cannot compare their absolute values without looking at the ...

View answer
Solving or approximating recurrence relations for sequences of numbers
9 votes

Sedgewick and Flajolet have done extensive work in analytic combinatorics, which allows recurrences to be solved asymptotically using a combination of generating functions and complex analysis. Their ...

View answer
Help reducing 3-SAT to 3-COLORING
Accepted answer
8 votes

I believe the goal of this construction is to try to assign true or false to each variable. The color assigned to x will determine whether it's true or false, and there's an edge from x to ¬x to ...

View answer
Computing with the Monster
Accepted answer
8 votes

If you are storing a matrix of 0's and 1's, you could consider using a bitvector for storage. This can pack some fixed number of bits (say, 32 bits or 64 bits) into a single integer, which decreases ...

View answer
A polynomial reduction from any NP-complete problem to bounded PCP
8 votes

I think that you can prove that BPCP is NP-complete by using a reduction similar to the one used to prove its undecidability. We will directly prove that BPCP is NP-complete by showing how to reduce ...

View answer
Best and worse case inputs for heap sort and quick sort?
7 votes

heap- Since the best and worst case are the same does it not matter the input order? The number of comparisons and assignments will always be the same? I imagine in a heap sort it may be the same ...

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

Part of the issue with the idea of "proving" the Church-Turing thesis is that the Church-Turing thesis isn't a precise mathematical statement. Rather, it's the idea, or "belief" if you will, that any ...

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

Imagine having a tournament made of the array elements. Group the array elements into pairs, then compare each pair. Put the larger numbers into one group and the smallers number into another group. ...

View answer
Are there NP problems, not in P and not NP Complete?
7 votes

No NP-complete problems are known to be in P. If there is a polynomial-time algorithm for any NP-complete problem, then P = NP, because any problem in NP has a polynomial-time reduction to each NP-...

View answer
Get the running time of forest disjoint sets
Accepted answer
6 votes

You've asked two questions: Why is the tree height Θ(log n)? Why is the runtime Θ(m log n)? This answer addresses both questions. I'll start off with a review of the ranks of the ...

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

A quick note: the runtime is not guaranteed to be $O(m \log n)$. For example, suppose that your forest consists of $\sqrt{n}$ a linked lists, each of which has $\sqrt{n}$ nodes in it. Doing a total of ...

View answer
Equivalence of regular grammars
5 votes

Yes, this is decidable. There's a rather direct conversion from a regular grammar to an NFA. From there, run the subset construction to turn the NFAs into DFAs. Run minimization algorithms to convert ...

View answer
Depth first or breadth first ordering in binary search trees?
5 votes

Think about what happens when you move from one layer in the tree to the next. When you start getting to layers with progressively more nodes, you'll eventually get to a spot where the layers are so ...

View answer
Hash table collisions: why use a linked list if we can use a hash set?
5 votes

You absolutely can do this. You just have to be careful with how you set things up. There's a type of hash table called a dynamic perfect hash table that, with some modifications, is essentially what ...

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

I went and asked Don Knuth about this. He mentioned that he first used the new terminology in his 1972 paper Top-Down Syntax Analysis (link here) to provide a consistency between the terminology in $...

View answer
Analog of PP for computability rather than complexity?
5 votes

The ideas in this answer come directly from Ricky Demer. I wanted to write a more long-form answer that fills in a few of the details and justifies why this new complexity class is equal to RE. First,...

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

Another way to arrive at a solution here - you might recognize that this language is regular, since, intuitively, you’d only need to remember whether you’d seen zero a’s, one a, or two or more a’s. ...

View answer
Proof of decidability of determining whether a DFA accepts a string
Accepted answer
4 votes

I've often found that, with problems like these, it's easiest to reason by analogy to software, since anything you can do with a computer you can do with a TM and vice versa (with a giant asterisk). ...

View answer
What do you call a DAG with a single root/source?
4 votes

If you think of the DAG as a graph whose reachability relation is a partial order relation, then an element with that property would be a minimum element in that relation. I haven't seen the term "...

View answer
Do functions with slower growth than inverse Ackermann appear in runtime bounds?
4 votes

The most comically slowly-growing function I've ever seriously seen used in a paper is $\alpha^*(n)$, the number of times you have to apply the Ackermann inverse to drop $n$ to some fixed constant. It'...

View answer