# Question
Title: Does array always have a wasted space of O(n)?
In this question it's stated that dynamic array wasted space is O(n). Here is the explanation why:

> Because, when a dynamic array is full, its size is increased by some factor `α`. This means that, immediately after growing, a dynamic array holding `n` items has size about nαnα, so the amount of wasted space is `n(α−1)=O(n)n(α−1)=O(n)`.

I'm wondering if it's always `O(n)`. Maybe there is some logic similar to this one which proves that wasted space is not `O(n)`?

# Answer
It depends on the algorithm used. Someone made the assumption that when an array has space for n items, and the n+1st item needs to be added, the array would be resized to a size c·n for some constant c \> 1. But there is nothing forcing us to do this; we could resize from n items to f (n) items, where f (n) ≥ n+1 obviously but f (n) - n = o (n).
> 1 votes

---
Tags: algorithm-analysis, data-structures, arrays, space-analysis
---


# Question
Title: Why is the lower bound of element uniqueness in $\Omega(n\log n)$?
I wish to discuss the element uniqueness problem. First let's define the problem:

Definition from wikipedia:

> In computational complexity theory, the element distinctness problem or element uniqueness problem is the problem of determining whether all the elements of a list are distinct.

i am aware that this question has been asked before, however, I am confused about what lower bound actually means.

Let's say we are given an arbitrary array of integers. We could simply use hashing to check for element uniqueness. Hashing works in amortized $O(1)$ time. Hence, shouldn't the lower bound of element uniqueness be $\Omega(n)$?

Am I understanding lower bound wrongly? Does lower bound mean an asymptotic lower bound for general cases (i.e. we could have arrays of strings as well) or does it apply to all cases?

# Answer
We assume the comparison model in the lower bound of the element uniqueness problem. That is, the key operations are to compare elements. In particular, hashing is not allowed.
> 8 votes

# Answer
I see at least two objections to your linear-time solution for the element uniqueness problem. First, the algorithm you propose doesn't work, because hashing works for most datasets and most hashes, but by the pigeon hole principle, not always. If an adversary knows the hash you use, she can give you a list of items that all hash into the same bucket. (She simply draws $n$ items from her favourite bucket. These exist, if the hash sufficiently reduces the length of the item, namely by at least $\log(n)$ bits).

Second, the assumption that hashing is in $O(1)$ time, works in a computational model where you can manipulate these items in constant time, but this isn't necessarily realistic. Suppose that all of $n$ elements are unique. Then each element is described by at least $\log(n)$ bits, so the length of these registers grows with $n$, so realistically you can't manipulate registers in constant time. Then hashing takes $\Omega(\log(n))$ time, and hashing $n$ elements takes $\Omega(n\log(n))$ time.

The same objection holds against the model where comparison is $O(1)$; here sorting takes $O(n\log(n)^2)$ real-world steps, where $n$ is the number of items, if you use QuickSort and use a black-box sorting algorithm. In a sense, this is a strange model; items can be compared in $O(1)$ time, but they can't be hashed in $O(1)$ time.
> 1 votes

# Answer
If you use a hash table, I will examine your hash function, and give you an array of values that all have the same hash value. Your hashing will take quadratic time. Actually, if you have say an excellent 64 bit hash function, and the number of values is not limited (much bigger than $2^{64}$ items), then most hash tables will run in $\Theta(n^2)$ with a tiny, tiny constant. The quadratic behaviour only shows itself if n is much larger than $2^{64}$.
> 1 votes

---
Tags: complexity-theory, lower-bounds
---


# Question
Title: Using random projections for locally sensitive hashing
I recently came to see that this library sparselsh uses random projection to perform locally sensitive hashing of documents.

The proof is such that based on cosine similarity to the vector. In other words if the dot product of a random projection vector and a feature vector \> 0, it would mean that the angle is obtuse and \<0 if the angle is acute. However, i cannot seem to understand it.

Assuming v is a feature vector containing a bag of words, and the random projection vector being drawn from a normal distribution. I can safely say that v will never have negative elements since the bag of words vector can never have a negative value. In this case, How would there be a situation when r.v give an obtuse angle? Am i misunderstanding something?

I have referred to this question but to no avail. Locality-sensitive hashing random projection

Let me state my confusion clearer.

Consider a 2 dimensional vector space, Given that r.v \< 0 if the angle between the two vectors are less than 90degrees and \>0 when they are above 90 degrees. This would mean that the probability of the blue vector dot product with another data point giving a r.v \> 0 is zero. This would mean that i can only draw vectors in the negative space?

# Answer
> 1 votes
$r \cdot v$ can be negative even if all elements of $v$ are positive: consider, e.g., $r = (2,-3)$ and $v=(1,1)$. Then $r \cdot v = -1$.

Also, using random projections is not the same as defining a hash to be 1 if the dot-product is $\ge 0$ and 0 if it is $\<0$. You can still use a random projection without using that particular hash function. I haven't looked at the sparselsh code, but it's also possible that it could be using a random projection but without using that specific hash function.

---
Tags: hash, linear-algebra, hashing
---


title: How is Grover's Algorithm useful?

text:
# Question
Title: How is Grover's Algorithm useful?
I am at a loss when it comes to understanding how Grover's Algorithm gives any useful information. Suppose we have a 4-qubit states (|0⟩ to |15⟩), and we are searching for the state |3⟩. The oracle would thus be O=I−2|3⟩⟨3|

And then, at the end, after all the amplitude amplification steps, we would get the state |3⟩ with a high probability, but does this give any new information, since we already used |3⟩ inside the oracle?

I know I am missing out something crucial, but I absolutely cannot put my finger on it.

Please help. Thank you.

# Answer
> 4 votes
The thing you're missing is that you aren't search for $|3\rangle$, you're searching for "the input that makes $f$ return true" where $f$ is some function.

For example, maybe $f$ is a discrete logarithm checker like $x \rightarrow 2^x \equiv^? 432821 \pmod{7438927891}$. Or $f$ could interpret its input as a claimed proof of the Riemann hypothesis, and check if that proof is correct. Anything you can imagine checking, $f$ could be that.

So Grover's algorithm is very *very* widely applicable. But unfortunately it also only gives a quadratic advantage, so "applicable" often doesn't translate into "useful". For example, the space of (reasonably sized) possible Riemann-hypothesis proofs is so huge that it laughs at square roots.

---
Tags: quantum-computing
---


# Question
Title: The difference between dynamic logic and temporal logic
To find the difference, I'd just encountered with assertions below about temporal logic in Wikipedia:

> another variant of modal logic sharing many common features with dynamic logic, differs from all of the above-mentioned logics by being what Pnueli has characterized as an "endogenous" logic, the others being "exogenous" logics. By this Pnueli meant that temporal logic assertions are interpreted within a universal behavioral framework in which a single global situation changes with the passage of time, whereas the assertions of the other logics are made externally to the multiple actions about which they speak. The advantage of the endogenous approach is that it makes no fundamental assumptions about what causes what as the environment changes with time. Instead a temporal logic formula can talk about two unrelated parts of a system, which because they are unrelated tacitly evolve in parallel. In effect ordinary logical conjunction of temporal assertions is the concurrent composition operator of temporal logic. The simplicity of this approach to concurrency has resulted in temporal logic being the modal logic of choice for reasoning about concurrent systems with its aspects of synchronization, interference, independence, deadlock, livelock, fairness, etc.

I could not realize the difference, considerably. Can't dynamic logic cover every time-driven aspect within arguments, as well as temporal logic?

Or why is dynamic not supposed to handle concurrent systems?

Would you please clear the case?

# Answer
> 0 votes
OK, dynamic logic adds assertions that specify what modal situation should exist following an action, however way this action is specified. In temporal logic the modal aspect is not emphasized. For example, if we consider dynamic alethic logic, the alethic bit would be missing from temporal logic. I hope this helps.

---
Tags: logic, linear-temporal-logic, temporal-logic
---


# Question
Title: $L\in NC^1$ iff there exists a sequence of poly sized formulas that decides $L$
**Prove** that $L\in NC^1$ iff there exists a sequence of poly sized formulas that decides $L$.

I managed to prove the $(\impliedby)$ and I want to prove $(\implies)$.

I feel that we need to take the boolean circuit and duplicate the sub-circuits of $fan-out\gt 1$ into exact circuits but with $fan-out = 1$. I fail to argue why the resulting tree is of polynomial size and not of exponential one.

# Answer
> 2 votes
Let the *size* of a circuit or formula be the number of leaves. The total number of vertices in a formula is at most twice its size.

You can prove by induction the following claim:

> If a function is computed by a fan-in 2 circuit of size $S$ and depth $D$, then it is computed by a formula of size $2^D S$.

If $L$ is in NC1 then its $n$-bit fragments have circuits of size $n^{O(1)}$ and depth $O(\log n)$. The claim shows that there are equivalent formulas of size $n^{O(1)} 2^{O(\log n)} = n^{O(1)}$.

---
Tags: complexity-theory, circuits
---


# Question
Title: How to Optimise my Time Optimisation Algorithm
I recently encountered a problem which goes like this : A student is given N number of questions and T time in total. Each question requires different time to complete and carries different marks. The problem asks to find the maximum marks the student can get by attempting some of the N questions within T time (Assuming if a question is attempted, it must be fully completed,no partial attempt of a question is allowed).

I tried to solve the problem by computing all possible combinations of questions which takes \<= T seconds to complete but soon found out its ineffective for large datasets.

How can I optimise my solution? Is there any alternative solution available?

# Answer
You're trying to solve a knapsack problem – you're trying to choose items of maximum value, given a constraint on their total size. These problems are **NP**-complete but can be solved reasonably efficiently in practice. The standard technique is to use dynamic programming. This gives a solution in time polynomial in $N$ and $T$. This is still, technically, an exponential-time algorithm (since an input of length $\ell$ could give $T$ as large as $2^\ell$) but it works well in practice.

I won't give details of how to do the dynamic programming, since knapsack is one of the standard examples of the technique so it's easy to find the details online and in textbooks.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Definition of the inverse of the Ackermann function
I am somewhat puzzled by the definition of the inverse of the Ackermann function: The normal Ackermann function $A$ can be used to define a function from $\mathbb{N} \to \mathbb{N}$ via $A(n, n)$. The inverse of this function, denoted by $\alpha$, is known as the *inverse Ackermann function*.

My problem is: Only bijective functions have an inverse. But I have seen no proof that $A(n, n)$ is indeed bijective. It seems highly unlikely to me that this is the case (since the value of $A(n, n)$ increases very quickly in $n$).

My guess is that $\alpha(m)$ should be defined as $\min \\{n \mid A(n, n) \geq m\\}$ or $\max \\{n \mid A(n, n) \leq m\\}$. Is that the case?

# Answer
The Ackermann function $n \mapsto A(n,n)$ is definitely very far from being bijective, otherwise it could not grow so quickly. However, in the contexts it is usually employed (complexity theory, oh notations, ...) it is not really relevant which are the actual values of $\alpha$ point by point. You can add one or multiply by three and the results are the same, so nobody really cares about what is the actual definition. Any of your two will work.
> 5 votes

---
Tags: complexity-theory
---


title: The number of nodes in a binary tree

text:
# Question
Title: The number of nodes in a binary tree
If a binary tree is both a max-heap and an AVL tree, what is its largest possible number of nodes, assuming all keys are different?

# Answer
> 2 votes
I'm going to say 2.

A max-heap is a near-complete binary tree. This means any child must have a key less than it's parent's key.

An AVL tree is a balanced binary **search** tree. This means the left child must have a key less than it's parent and the right child must have key greater than it's parent.

From these, You can see that there can be no right-children in the tree. Hence, You can only have left-children. Since the max-heap has the near-complete property, The largest tree you can have is the root node with a left-child.

Hence, The maximum size is 2.

---
Tags: binary-trees, heaps
---


# Question
Title: The advantages and disadvantages of using an assembler over hexidecimal and binary coding
What are the benefits and cons of using an assembler, rather than programming directly into hexadecimal or binary code?

# Answer
1. Readability.
2. Writability.
3. Usability.
4. Sanity.
5. Humanity.

I'll leave it as an exercise which of these are advantages and which ones are disadvantages.
> 5 votes

# Answer
It is not practical to program in binary or hexadecimal, as it would be nearly unreadable. Programming in assembly allows the programmer to write very precise instructions for the processor, while still allowing them to produce a readable and understandable program.
> 2 votes

---
Tags: programming-languages
---


# Question
Title: Algorithm to generate integer sets fulfills restrictions
I'm trying to solve the following problem.

**Input**

* positive integers $v$, $b$ and $\ell$. ($\ell\leq v\leq b\ell$.)

**Output**

A list $S\_1, \dots, S\_k$ of all possible integer multisets (a generalization of the concept of a set that, unlike a set, allows multiple instances of the multiset's elements), such that each $S\_i$ fulfills following constraints:

* $|S\_i|=\ell$
* $\sum\_{s\in S\_i}s=v$
* for all $s\in S\_i$, $s\in \\{1, \dots, b\\}$

For example, a solution to the instance $v=4$, $b=4$, $\ell=2$, is $\[\\{1,3\\},\\{2,2\\}\]$.

For now I have a recursive function working to give something not exactly the same as what I'm expecting. For the input above, it returns $\[\\{1,3\\},\\{2,2\\},\\{3,1\\}\]$. I know I can use extra steps to eliminate the duplicates but I'm wondering if there's a mathematical formula I can use? Or some other algorithm acts smarter?

Below is my code:

```
public static List<List<Integer>> getIntegerSets(int v, int base, int l) {
    if (v < l || l <= 0) return null;
    List<List<Integer>> result = new ArrayList<>();
    if (l == 1) {
        if (v > base) return null;
        List set = new ArrayList<Integer>();
        set.add(v);
        result.add(set);
    } else {
        for (int i = Math.min(base, l * v); i > 0; i--) {
            List<List<Integer>> list = getIntegerSets(v - i, base, l - 1);
            if (list == null) continue;
            for (List<Integer> subset : list) {
                subset.add(0, i);
                result.add(subset);
            }
        }
    }
    return result;
}

```

Another extended problem is, can we (use another algorithm) directly get the size of the list, which is the $k$ value, with or without duplicates, perfectly both, without executing this very function?

# Answer
You want to enumerate all integer partitions of $v$ into exactly $\ell$ parts, where each part is $\le b$. Let $F(v,\ell,b)$ denote the set of all such partitions.

One can construct a recursive algorithm for this. For instance, any such partition must include the number $b$ one, two, three, ..., or $\lfloor v/b \rfloor$ times, so:

$$F(v,\ell,b) = \bigcup\_{i=0}^{\lfloor v/b \rfloor} F(v-ib,\ell-1,b-1) + b+\cdots + b,$$

where $F(\star)+b+\cdots+b$ represents the set of partitions (multisets) obtained by starting with each partition in $F(\star)$ and adding $i$ copies of the number $b$ to it. Moreover, this is a disjoint union, so there is no need to use hashtables to eliminate duplicates.

However, the number of such partitions can be exponentially large in $v$, so in general the algorithm might be infeasibly expensive, unless $v$, $\ell$, or $b$ are sufficiently small.
> 2 votes

---
Tags: combinatorics, permutations
---


title: What does $L$-uniformity mean?

text:
# Question
Title: What does $L$-uniformity mean?
I've understood that $L$-uniformity means that there's a TM that can output the description of $C\_n$ in $O(\log n)$ **space**. Now, that seems odd to me since the description itself (as far as I understand) must be a $O(n)$. I'd be glad for clarification.

Also, in that context: What does $L$-uniform $NC^k$ means?

Thanks!

# Answer
> 3 votes
What is usually meant by saying that a (not necessarily binary) function is computable in $O(\log n)$ space, is that there exists a Turing machine computing it which uses only $O(\log n)$ space in its work tape. This limitation does not concern the output tape, which is write only. You can also think of this condition as being able to, given $i$, output the $i$'th bit of the circuits description using only $O(\log n)$ space.

A circuit family $\\{c\_n\\}\_{n\in\mathbb{N}}$ is logspace uniform $NC^k$ iff $c\_n$ is a circuit with $n$ inputs of size $poly(n)$ and depth $O(\log ^k n)$, and additionally, there exists a logspace Turing machine such that given $1^n$ as input, outputs a description of $c\_n$.

---
Tags: complexity-theory, complexity-classes, space-complexity
---


# Question
Title: Higher order empirical entropy is not the entropy of the empirical distribution?
Basically, the problem is that I always thought that the (unnormalized) $k$th order empirical entropy $n\cdot H\_k(x)$ (see "Backround" at the end of this post for more information) for a given string $x$ of length $n$ equals the entropy of the empirical distribution on the set of all words of length $n$ (the conditional probabilities are taken from the observed occurrences in $x$). Until today, I was totally sure that this is true, but it seems to be wrong for very easy examples (e.g. for $x=1011$).

To be more accurate, consider $\Sigma=\\{0,1\\}$, $x=1011$ and $k=1$ such that $$n\cdot H\_k(x)=4\cdot H\_1(x)=2.$$ On the other hand, the corresponding empirical distribution is a First-order Markov source described by

* $P(\text{The first letter is }0)=0$
* $P(\text{The first letter is }1)=1$
* $P(\text{Letter }0 \text{ immediately follows after letter }0)=0$
* $P(\text{Letter }1 \text{ immediately follows after letter }0)=1$
* $P(\text{Letter }0 \text{ immediately follows after letter }1)=0.5$
* $P(\text{Letter }1 \text{ immediately follows after letter }1)=0.5$

Now this probabilities yield a random variable $X$ on words of length $n=4$, where the Shannon entropy is $$H(X)=-\sum\_{w\in\Sigma^4}P(w)\log P(w)=\frac{9}{4}.$$ (You only need to consider words of length $4$ which start with $1$ and do not contain $00$.)

But shouldn't be both measures intuitively give the same value? I did the calculations more than once, so I am pretty sure the mistake is in my understanding, not in the calculation. Or did I always thought something wrong? But it seems so clear that the empirical entropy is the entropy of the empirical distribution (also for higher order Markov sources).

$ $

$ $
**Backround**
For a given string $x\in\Sigma^n$ over an alphabet of size $k$, the ($0$-th order) empirical entropy is defined as $$H\_0(x)=\frac{1}{n}\sum\_{i=1}^{k}n\_i\cdot\log \frac{n}{n\_i},$$ where $n\_i$ is the number of occurrences of the $i$th alphabet symbol. The $k$-order empirical entropy ($k\ge 1$) is then defined as $$H\_k(x)=\frac{1}{n}\sum\_{|w|=k}|S\_w|H\_0(S\_w),$$ where $S\_w$ is the string obtained by concatenating the characters immediately following occurrences of $w$ in $x$.

# Answer
No, as your counterexample shows, it is not true. I don't understand why you previously thought it was true, either, so it's hard to say what might have gone wrong with your previous intuition.

We *can* say that

$$H(X) = H(X\_1) + H(X\_2 | X\_1) + H(X\_3 | X\_1,X\_2) + H(X\_4 | X\_1,X\_2,X\_3),$$

where $X\_i$ denotes the $i$th character in $X$. that much is true.

In the example you gave, $H(X\_1) = 0$, $H(X\_2|X\_1) = 1$, $H(X\_3|X\_1,X\_2) = 0.5$, $H(X\_4 | X\_1,X\_2,X\_3) = 0.75$ (see footnote * for explanation). Thus $H(X) = 1 + 0.5 + 0.75 = 2.25$.

Do notice that $\Pr\[X\_i=1\]$ and $H(X\_{i+1}|X\_1,\dots,X\_i)$ both depend on $i$. This might be important.

Also, notice that $H(X\_{i+1}|X\_1,\dots,X\_i)$ is unrelated to $H\_1(x)$.

Perhaps you were expecting $\Pr\[X\_i=1\]$ and $H(X\_{i+1}|X\_1,\dots,X\_i)$ to be the same for all $i$? If that were true, there might be a relationship between $H\_1(x)$ and $\Pr\[X\_i=1\]$ and $H(X\_{i+1}|X\_1,\dots,X\_i)$ (or something similar to them)... but it's not.

---

Footnote \*: How did I calculate those? I used the formula

$$H(X\_{i+1}|X\_1,\dots,X\_i) = \sum\_v \Pr\[(X\_1,\dots,X\_i) = v\] \times H(X\_{i+1}|(X\_1,\dots,X\_i) = v).$$

For $i=1,2$, we only need to consider two values of $v$; for $i=3$, we only need to consider three values of $v$.
> 1 votes

---
Tags: probability-theory, information-theory, entropy
---


# Question
Title: Why can we not find the generally superior machine learning algorithm in practice?
TL;DR Our mind is a superior meta-machine learning algorithm, it can figure out tradeoffs in a much more general case than any machine learning algorithm we have. Furthermore, its Kolmogorov complexity is 4MB or less, and thus should be fairly easy to discover. However, despite our best efforts, no algorithm we've discovered has even approached this meta-capability. Is there a CS grounded explanation for this? The NFLT is not applicable because it does not apply in practice, and the human mind is an instance of said meta-algorithm.

---

There are many machine learning algorithms. The no free lunch theorem (NFLT) says, in theory, all these algorithms are exactly equal according to an error function over all possible problem domains. In practice, this doesn't matter because we are only dealing with a very small subset of these problem domains.

In practice, this often involves a tradeoff between multiple objectives. Making a problem multi-objective instead of single objective often causes it to become much more complex and difficult. There is no longer a single best solution, but there are still better and worse solutions. One way of describing the set of better solutions is with the notion of "Pareto optimality," which is the set of solutions that dominate all other solutions in all objectives, but do not dominate each other. These optimal solutions describe a surface in a graph of the solutions known as the "Pareto front." The following Figure is an example of a Pareto front where solutions A-H dominate all other solutions, but not each other.

That being the case, if we ask "what is the best ML algorithm?" we cannot say "None, b/c NFLT," since we are asking about the best ML algorithm in practice. If the NFLT does not matter in practice, then there must be a best ML algorithm, in practice. If there is a set of algorithms that describe the Pareto front, then the best algorithm is any member of this set.

What is this best practical algorithm? There does not seem to be one, to the best of our knowledge. Even "magical" general ML algorithms such as deep learning or extreme boosting have many knobs to twiddle, and are only good for the right kind of problem. There is no one size fits all ML paradigm.

Yet, there must be one, since data scientists are able to match the right algorithm to the right problem and achieve outstanding results, such as Google's search capabilities. Whatever it is that powers the data scientist brain must be relatively simple, since human DNA can be compressed to 4 MB, not much bigger than, and often quite smaller than, many ML frameworks when zipped.

Furthermore, the data scientist brain algorithm is an extremely powerful program. For a binary prediction problem of $N$ predictions, there are $2^N$ different possible predictions. To be right more than half the time, we need to eliminate more than $2^{N-1}$ possibilities. We also have to do this in polynomial time. Both feats seem astounding for any reasonably sized $N$, especially since so many important problems are NP-Complete or worse in the general case.

Since we aren't dealing with a halting problem (data scientists reliably halt on good solutions), even some kind of assisted enumeration of 4MB programs in a Turing complete language would seem to hit on this master algorithm sooner or later.

Is there a CS explanation for this discrepancy, or flaw in my reasoning, that the super powerful and extremely quick master algorithm is \<= 4MB, yet despite all our searching we've been unable to find it?

# Answer
Say that you want to minimize $f\left(x\right)$ where $x{\in}\left\[0,100\right\]$. What's the best solution strategy?

### There's no free lunch...

In the general case, you basically just have to compute $f\left(0\right){\dots}f\left(100\right)$, then check for the largest value.

"No free lunch" means that, given the above problem, no one can provide a faster, reliable algorithm to optimize it beyond naively trying from $x=0$ to $x=100$.

### ... *after* you've eaten them all...

Say that you already had an optimization algorithm that called for you evaluating $f\left(0\right){\dots}f\left(100\right)$ ***twice***. If you drop that done to *once*, then you've had your free lunch.

"No free lunch" applies once you've done all of this stuff already. So, it's less of a theory and more of a statement about optimality.

### ...and haven't missed anything

Say that $f\left(x\right)$ is well-behaved, where $$ \begin{array}{ccccr} &&\left|f\left(x\right)-f\left(x-1\right)\right|\<10 && \forall x \\ \end{array} $$ ; then you can construct new evaluation strategies where you try to minimize the number of evaluations by identifying points that can't be minimal and skipping them.

### It's hard to know what you might be missing

In machine learning cases where you're analyzing the real world, we don't really have an analytical problem statement. Physics isn't perfectly accurate; measurements aren't perfectly reliable; and things can change.

So, you're right that data scientists can usually improve algorithms in real-world cases.

### Human brains are good at human problems due to *extreme* selection bias

Regarding,

> Whatever it is that powers the data scientist brain must be relatively simple, since human DNA can be compressed to 4 MB, not much bigger than, and often quite smaller than, many ML frameworks when zipped.

Historically, this oddity was discussed in "The Unreasonable Effectiveness of Mathematics in the Natural Sciences" (1960). The Wikipedia page discusses some common responses.

Personally, my take is that we and our science co-evolved, so evolutionary pressures have favored compatibility. Our brains are pretty well wired to think in ways that were both do-able and practical to our ancestors.
> 2 votes

# Answer
There are many dimensions that "intelligence" could potentially be measured on. We already know of some artificial intelligence schemes that do better than humans on some dimensions.

It's true that we don't have artificial intelligence schemes that do better than humans, on the sorts of problems that tend to arise in practice as part of everyday human life and experience. On the other hand, humans have had hundreds of millions of years to evolve and adapt. Artificial intelligence has only been around for maybe half a decade. That might be one possible explanation.

---

Separately: The question seems to be based on several misconceptions. Let me point out a few things you've written, and try to clarify the misconceptions:

> The point is that our mind is a superior algorithm, it can figure out tradeoffs in a much more general case than any machine learning algorithm we have.

Our mind is better for some tasks, but not all. There are other tasks where machines are better. For instance, machines are superior at chess, or at adding up small integers billions of times in a row without making a single error. Humans are superior at making other people laugh, cry, or feel better about themselves, or at folding laundry.

For instance, machines can solve Connect Four perfectly, but most people can't. Thus, if we allow "performance at Connect Four" as one of the dimensions that we're measuring Pareto-optimality at, machines are Pareto-optimal: they dominate humans in at least one dimension.

Now what you're probably really asking is, why do humans dominate machines in *most* dimensions? But to make that question well-defined, we have to define what is the set of all dimensions. What's probably implicit in that question is the assumption that you mean "the set of all dimensions we (humans) care about", or "the set of all dimensions that are meaningful to us (humans)". Now consider that the human brain has had hundreds of millions of years to evolve and get better at the dimensions that humans care about or that matter to us, whereas artificial intelligence hasn't.

> Furthermore, its Kolmogorov complexity is 4MB or less, and thus should be fairly easy to discover.

Actually, no, that doesn't follow. Let's suppose for the sake of argument that an entire human organism can be described in 4MB of data (after compression; let's not quibble about whether that's actually biologically correct; and let's not worry about the fact that Kolmogorov complexity is primarily meaningful in an asymptotic sense, and ignore those issues), or equivalently, 32 megabits of data.

That means that a program that behaves like a human would require 32,000,000 bits of data to describe. So, you're asking: Why is it hard to find such a program? Perhaps implicit in your question is: How many programs can there be? How hard can it be to find the right one?

The answer is: it might be *very very* hard. There are $2^{32,000,000}$ possible programs (of that length). That's an enormously large space -- and it's a space where maybe all but one of them are useless, and only one is any good. Trying all of the possibilities is way beyond feasible: like, you couldn't do it within the lifetime of the universe, even if you imagine a universe full of supercomputers, where each atom in the known universe has the computational power of one of today's supercomputers. $2^{32,000,000}$ is an unimaginably large number.

So, it shouldn't be such a great surprise that it might be hard to find an example of such a program explicitly. Just because we know that it exists doesn't make it easy to find such a thing.

For instance, even if space aliens had landed 150 years ago and told us that there exists a proof of Fermat's last theorem, it still would have taken close to 150 years to find the proof. Just knowing that a proof exists doesn't really help you in finding it. I bet that the Latex source file for the papers that prove Fermat's last theorem correct could be compressed to less than 4MB. Even if I tell you that there exists a proof whose Kolmogorov complexity is at most 4MB, it's still not at all easy to find that proof.
> 5 votes

---
Tags: machine-learning
---


# Question
Title: Using finite state machines for lexical analysis
I'm a high school student and I'm passionate about everything language related - lexers, parsers, compilers, interpreters and so on. Some time ago I've written a calculator in Python (now willing to use a better language), which uses the Shunting yard algorithm and my own lexer.

So I want to start learning more about this topic and found this Compilers course. I pretty much understand how RegExp are used to specify the language but when the professor started talking about finite-state machines I just got lost in all the theory.

So this is my question: How do I use DFAs and NFAs for lexical analysis ? What does "state" mean in this context ?

# Answer
The goal of any parser is to verify that a sequence of characters is a string in a specific language \[C, Python, whatever\]. In principle, the parser can be written to inspect each character in the sequence directly, but the parser will be more comprehensible and efficient if built to inspect higher-level *lexical tokens* \- names, numbers, quoted-strings, miscellaneous operator symbols, parentheses, etc. This is where the scanner comes in. The scanner is essentially a subroutine which the parser calls to read the raw character stream and extract & return the next lexical token.

The scanner is implemented as a DFA which recognizes any token. Each token type has its own structure as a character sub-sequence, representable as a regular expression which in turn is translated to a simple DFA; for example: a name is (in most languages) a sequence of characters consisting of \[letter\] followed by zero or more \[letter or digit\]. The scanner combines the simple DFAs for these expressions into a single DFA for their union. This is (conceptually) implemented as a simple two-dimensional table, where rows are indexed by character values and columns are indexed by DFA state numbers (actually the rows are usually indexed by character classes - e.g 'letter' instead of 'a', 'b', ...).

Each call to the scanner follows this process: Begin in a common start state (e.g 0), looking at the next character \[in the I/O buffer\]. Using the lookup table, calculate the next state and 'consume' the next character \[typically this means copying the character into the next slot in a buffer\]. Repeat until a final state is reached, then return an object identifying the type of lexical token and the value from the buffer. Example: Suppose the scanner is called when the next few characters are 'foo '. The machine will move from state 0 to state (say) 11 and copy 'f' to the buffer; then move from state 11 back to state 11 and copy 'o' to the buffer - twice (two 'o'-s); then seeing the space it will move to some final state (say) 12, and return from the call, returning the object \[type = NAME, value = 'foo'\]. The next call to the scanner will begin where the last ended, looking at that space.

Most scanners do a bit more than this, of course. In languages with reserved words, when the scanner finishes reading the name, it will typically look up the name in a table of reserved words; if found, it will return an object representing that specific reserved word instead of a generic 'name' object. The scanner will usually 'eat' all contiguous whitespace without returning any token; similarly for comment text. And so on and so forth....
> 4 votes

---
Tags: regular-languages
---


# Question
Title: Best and worse case inputs for heap sort and quick sort?
So given an input of lets say 10 strings, what way can we input these so we get the best or worst case for these two given sorts?

```
Heap sort:
best case - nlogn
worst case - nlogn

Quick sort:
best case - nlogn
worst case - n^2

```

Where I get confused on these two is:

* **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 since the real work is done in the insertion, but the sorting only uses the removal of the max/min heap? Is that why?
* **quick sort**\- This one I don't know for sure. I'm not sure what the best case and worst case situations are for this. If its a already sorted list of 10 strings for example wouldn't we always have to choose the same amount of pivots to get complete the recursive algorithm? Any help on this explanation would really help.

# Answer
> 6 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 since the real work is done in the insertion, but the sorting only uses the removal of the max/min heap? Is that why?

The number of comparisons made actually can depend on the order in which the values are given. The fact that the best and worst case are each Θ(n log n) - assuming all elements are distinct - only means that *asymptotically* there's no difference between the two, though they can differ by a constant factor. I don't have any simple examples of this off the top of my head, but I believe that you can construct inputs where the number of comparisons differs by a constant factor between the two approaches. Since big-O notation ignores constants, though, this isn't reflected in the best-case and worst-case analysis.

> quick sort- This one I don't know for sure. I'm not sure what the best case and worst case situations are for this. If its a already sorted list of 10 strings for example wouldn't we always have to choose the same amount of pivots to get complete the recursive algorithm? Any help on this explanation would really help.

The number of pivots chosen is indeed the same regardless of the execution of the algorithm. However, the *work done per pivot* can vary based on what sort of splits you get. In the best case, the pivot chosen at each step ends up being the median element of the array. When this happens, there are (roughly) n comparisons done at the top layer of the recursion, then (roughly) n at the next layer because there are two subarrays of size n / 2, then there are (roughly) n at the next layer because there are four subarrays of size n / 4, etc. Since there are Θ(log n) layers and each layer does Θ(n) work, the total work done is Θ(n log n). On the other hand, consider choosing the absolute minimum of each array as a pivot. Then (roughly) n compares are done at the top layer, then (roughly) n - 1 in the next layer, then (roughly) n - 2 in the next, etc. The sum 1 + 2 + 3 + ... + n is Θ(n2), hence the worst case.

Hope this helps!

# Answer
> 5 votes
Since nobody's really addressed heapSort yet:

Assuming you're using a max heap represented as an array and inserting your max elements backwards into your output array/into the back of your array if you're doing it in-place, the worst case input for heapSort is any input that forces you to "bubble down" or reheapify every time you remove an element. This happens every time you are trying to sort a set with no duplicates. It will still be Θ(n log n), as templatetypedef said. The reason the worst case is Θ(log n) for a single element is because the height of the tree will be log n, and having to traverse the entire height is the worst case, and thus it is log n. The height is log n because we have a full binary tree where every parent has two children, and hence the height of n nodes becomes log n.

This property implies that heapSort's best-case is when all elements are equal (Θ(n), since you don't have to reheapify after every removal, which takes log(n) time since the max height of the heap is log(n)). It's kind of a lousy/impractical case, though, which is why the real best case for heapsort is Θ(n log n).

# Answer
> 4 votes
* **Quick Sort**

**Worst case:** $\mathcal{O}(n^2)$. Lets assume the pivot element is always the right-most element: Input an already sorted list with $n$ elements. So each partitioning leads to one list with $n-1$ elements and one list with $0$ elements. Even if you choose the pivot element randomly, you can still be unlucky and always choose the maximum value in the list.

Let $T(n)$ be the number of comparisions quicksort requires to sort a list with $n$ elements. Worst case: \begin{align} T(n) = & T(n-1) + n & \text{($T(n-1)$ recursive, $n$ to partion)}\\ = & \frac{n(n+1)}{2} \in \mathcal{O}(n) \end{align}

**Best case:** $\mathcal{O}(n \log n)$. If the pivot element is chosen in such way, that it partitions the list evenly:

\begin{align} T(n) = & 2 \ T\left(\frac{n}{2}\right) + n & (\text {2 times $\frac{n}{2}$ recursive, $n$ to partition)} \\ \in & \mathcal{O}(n \log n) & (\text{master theorem}) \end{align}
* **Heap Sort**

The worst case and best case complexity for heap sort are both $\mathcal{O}(n \log n)$. Therefore heap sort needs $\mathcal{O}(n \log n)$ comparisons for any input array. Complexity of heap sort:

\begin{align} & \mathcal{O}(n) & (\text{build $(1,n)$ heap}) \\ \+ & \sum\_{i=1}^{n} \mathcal{O}(\log i - \log 1) & (\text{build $(1,j)$ heap}) \\ = & \mathcal{O}(n) + \sum\_{i=1}^{n} \mathcal{O}(\log i) & (\text{logarithm quotient rule}) \\ = & \mathcal{O}(n \log n) & \left(\sum\_{i=1}^{n} \log i \< \sum\_{i=1}^{n} \log n = n \log n\right) \end{align}

---
Tags: algorithms, complexity-theory, sorting, heaps
---


title: Recurrence Solution

text:
# Question
Title: Recurrence Solution
What's the (asymptotic) solution of the recurrence $T(n,m,k,t)\leq T(n^\frac 1 m, 1, km, kt) + \Theta(n)$?

I know how to solve univariate recurrences, but this recurrence is much more difficult, so I am stuck here.

**Edit:**
The solution of this inequality should be something that does not imply any "dependency" between $n,m,k,t$. For example, subtituting the solution $T(n,m,k,t)=n^\frac k m$ yields $n^\frac m k\leq n^k$ which is true for every $n,m,k,t\geq 1$, while $T(n,m,k,t)=nk$ implies $nk\leq n^\frac 1 m km$ which is equaivalent to $n\leq n^\frac 1 m m$ which is not always true, and thus implies some dependency between $n,m$. Therefore, this solution holds only in special cases that satisfy this dependency.

I believe that the set of solutions of this inequality is a *subset* of the set of solutions that @D.W. has shown (as some of which are true only assuming some dependency between $m,n,k,t$).

# Answer
> 1 votes
There isn't enough information to provide a solution. See explanation below.

Let $c\>0$ be a constant so that $T(n,m,k,t) \le T(n^{1/m},1,km,kt) + cn$. When we unroll your recurrence twice, we find that

$$T(n,m,k,t) \le T(n^{1/m},1,km,kt) + cn \le T(n^{1/m},1,km,k^2mt) + 2cn.$$

Unroll $r$ times, and we find that

$$T(n,m,k,t) \le T(n^{1/m},1,km,k^r m^{r-1} t) + rcn.$$

This terminates at a base case when $k^r m^{r-1} t = 1$, which is equivalent to $(km)^r = m/t$. Taking logs, we find that this happens when

$$r = {\log(m/t) \over \log(km)}.$$

Thus we find

$$T(n,m,k,t) \le T(n^{1/m},1,km,1) + {\log(m/t) \over \log(km)}cn.$$

Let $f(x,y)$ be a function of $x,y$. Then

$$T(n,m,k,t) = \Theta(f(n^{1/m},km) + {\log(m/t) \over \log(km)}n)$$

is a possible solution of this recurrence (simply take $T(x,1,y,1) = f(x,y)$), as is any asymptotically smaller function. To determine whether this is actually a feasible solution, plug into the definition above and check whether it satisfies your inequality for all $n,m,k,t$.

Is there a solution that is polynomial in $n$? Yes, for instance $T(n,m,k,t) = n$ is easily verified to satisfy your inequality for all $n,m,k,t$ and to be polynomial in $n$. Also $T(n,m,k,t)=n^2$ or indeed $T(n,m,k,t)=n^d$ for any constant $d$ is a solution.

---
Tags: recurrence-relation
---


title: Gauss-Jordan using stacks and list

text:
# Question
Title: Gauss-Jordan using stacks and list
I have a homework assignment in which I need to write an implementation of Gauss-Jordan with complete pivoting. Complete pivoting is a modification to the basic Gauss-Jordan algorithm in which rows and columns are swapped around pivots. This is done to minimize the numerical errors by avoiding operations with small floating-point values.

A common approach would be to use `for` loops for swapping rows, but it would cost $O(n)$ operations to move a row and $O(n)$ to move a column. Using stack and list could be faster.

So the question is, how can stacks and lists be used in an implementation of Gauss-Jordan to efficiently swap columns in a matrix $A$?

I can change rows using pointers, but I can't realize how to use those structures to move columns and do Gauss-Jordan.

EDIT: Sorry i was to tired when create this question, as i'm not from a english speaker native country, i made some mistakes. The questions is about swapping columns using lists and stack. I'm really sorry, i wasted almost week thinking about it.

# Answer
What you want is called **indirection**. Instead of physically moving the rows/columns, you move their names.

Let's say I call row 1 `r[0]`, and row 3 `r[2]`, in a matrix A, which has size n by n. Initially, the rows are exactly as I call them, so we initialize `r[i] = i` for all `i < n`.

Now I want to swap the third (`r[2]`) and the fifth row (`r[4]`). I could move the elements in matrix A, but this would require *n* swaps. Instead, I can just swap `r[2]` and `r[4]`! This is just swapping one integer.

The tradeoff is that now we must read matrix A as `A[r[i]][c[j]]` (where `c` is the equivalent of `r`, but for columns) instead of `A[i][j]`. This is a bit slower.
> 3 votes

# Answer
Agree with orlp's answer, which correctly discusses the complete pivoting asked about in the question. This answer shows a common variant, partial pivoting, which only swaps rows (and not columns). This approach is often more efficient, but complete pivoting can offer more reliable results.

### The problem

The mathematical method that you're referring to, i.e. pivoting in Gauss-Jordan elimination, requires swapping rows in a matrix.

Naively, rows can be swapped by swapping each of their values one-at-a-time:

```
// Swap rows 1 and 3
int row_0 = 1;
int row_1 = 3;

for (int i=0; i < rowLength; ++i)
{
    var temp = matrix[row_0, i];
    matrix[row_0, i] = matrix[row_1, i];
    matrix[row_1, i] = temp;
}

```

This gets you from

```
matrix[,] = {  1    2    3    4
               5    6    7    8
               9   10   11   12
              13   14   15   16  }

```

to

```
matrix[,] = {  1    2    3    4
              13   14   15   16
               9   10   11   12
               5    6    7    8 }

```

But, as you've said, that requires looping over each element in the rows to swap them, and you want something more efficient.

### The solution: Indirection

Instead of using a multi-dimensional array like `matrix[,]`, you can use an array-of-arrays (also called a jagged array) like `matrix[][]`.

```
row_0[] =   {  1    2    3    4  }
row_1[] =   {  5    6    7    8  }
row_2[] =   {  9   10   11   12  }
row_3[] =   { 13   14   15   16  }

matrix[] =  {        row_0
                     row_1
                     row_2
                     row_3       }

```

You can still access the array in pretty much the same manner as before; the notation just changes slightly:

```
//  Before, with multi-dimensional array:
matrix[2, 3]  == 7

//  After, with array-of-arrays:
matrix[2][3]  == 7

```

However swapping rows is a lot easier since you have an array that's literally just a collection of row indices. By swapping those row indices, you effectively swap those rows.

```
// Swap rows 1 and 3
int row_0 = 1;
int row_1 = 3;

var temp = matrix[row_0];
matrix[row_0] = matrix[row_1];
matrix[row_1] = temp;

```

This gives you the same switch without having to loop over each element in the row.

```
row_0[] =   {  1    2    3    4  }
row_1[] =   {  5    6    7    8  }
row_2[] =   {  9   10   11   12  }
row_3[] =   { 13   14   15   16  }

matrix[] =  {        row_0
                     row_3
                     row_2
                     row_1       }

```

### Performance

This change from a multi-dimensional array to array-of-arrays has a few effects on performance and implementation:

* Memory allocation:

+ Multi-dimensional arrays are often allocated as one block of memory.
    + Array-of-arrays can allocate $1$ block of memory for the array-of-arrays, then $n\_{\text{rows}}$ for each subordinate array, for a total of $n\_{\text{rows}}+1$ memory blocks.
* Row-swap operations:

+ Multi-dimensional arrays can't just swap rows; the operation must be performed member-wise.
    + Array-of-arrays can swap rows, as shown above.
* Serialization, caching, and multi-threading:

+ If your matrix is huge, you might only need to work with part of it at a time, or part of it in different threads. An array-of-arrays allows you to access the relevant parts without serializing/loading/passing the entire thing.

A few bloggers have noted that arrays-of-arrays can be more performant in C#. This can be counter-intuitive as they're more general structures than multi-dimensional arrays, but apparently real-world implementations can have arrays-of-arrays be faster even when their extra functionality isn't used.
> 1 votes

---
Tags: algorithms, data-structures, linear-algebra, lists, stacks
---


# Question
Title: Can you give an inductive definition to define the length of a list L?
Having trouble understanding what it means to define something inductively in the following context.

> Can you give an inductive to define the length of a list L?
>
> a. The total number of items in L is the length of L
>
> b. Basis: the length of an empty list is 0 Induction: the length of a list is 2\*(length of half the list)
>
> c. Basis: the length of an empty list is 0 Induction: the length of a list is (length of head(list))+(length of tail(list))
>
> **d. Basis: the length of an empty list is 0 Induction: the length of a list is 1+(length of tail(list))**

The answer is (d). Why might this be?

And also for this similar question:

> Can you give an inductive definition to define what it means for an element X to be a member of a list L?
>
> a. X is a member of a list L if and only if X belongs to the list L.
>
> **b. X is a member of a list L if either X is the head of the list or X is a member of the tail of L.**
>
> c. X is a member of a list L if we can find an element Y in L and X=Y.
>
> d. X is a member of a list L if we can find an element Y in the tail of L

The answer is (b).

Thank you.

# Answer
In an inductive definition what you have to do is to find a base case and the inductive step.

In your case, suppose to have a list $L$ and let head be the first element and tail the rest of the list.

For example, if $L=\[1,2,3,4,5\]$:

* head = $1$
* tail = $\[2,3,4,5\]$

In order to understand the meaning you could consider writing a recursive function to compute the length of the list.

According to the answer

* Basis: the length of an empty list is *0*
* Induction: the length of a list is *1+(length of tail(list))*

This corresponds to the recursive function

```
function len(list L)
   if L is empty
        return 0
   else return 1 + len(tail(L))

```

Same for the second question:

```
function member(elem x, list L)
   if L is empty
       return false
   if head == x
       return true
   else return member(x, tail(L))

```

and this corresponds to say: X is a member of a list L if either

* X is the head of the list or
* X is a member of the tail of L.
> 1 votes

---
Tags: induction
---


# Question
Title: Approximation scheme for Multiple Choice Knapsack
The paper \_Fast Approximation Algorithms for Knapsack Problems (E. Lawler, 1979) gives an FPTAS (fully polynomial time approximation scheme) for the multiple choice knapsack problem (MKP). But MKP is strongly NP-hard, so it cannot have an FPTAS unless P=NP. Is the result of this paper wrong?

# Answer
The paper you cite is not available to me. However, according to this paper: "Improved Fully Polynomial time Approximation Scheme for the 0-1 Multiple-choice Knapsack Problem",

> 0-1 MCKP is $\text{NP}$-hard \[4\] as it contains the 0-1 Knapsack problem as a special case \[5, 13\] but *it can be solved in pseudo-polynomial time* (emphasis added) through dynamic programming \[7, 2\].

Thus, 0-1 MCKP is not strongly $\text{NP}$-hard.

One of the citations is

\[7\] K. Dudzinski, S. Walukiewicz, “Exact Methods for the Knapsack Problem and its Generalizations”, European Journal of Operational Research, (28), (1987): 3–21.
> 1 votes

---
Tags: algorithms, approximation, knapsack-problems
---


# Question
Title: Whats the difference between Processor bus and System bus
Is there something called Processor Bus? Whist solving one of the MCQ I ended up seeing the term "Processor Bus". Does this thing actually exists?

I did some research, but couldn't find one article that talks about Processor bus.

It would be great, if someone can guide me along.

# Answer
> 4 votes
A lot of terminology is vendor-specific. Different architectures and CPU vendors use different terms to describe different ways of connecting CPUs and peripherals, and the technology is constantly changing.

In what follows, I'm going to use the word "bus", but do be aware that a bus could be realised in multiple ways depending on speed and requirements, such as a point-to-point, crossbar, or switched fabric topology. It's logically a bus, even if it isn't physically a bus.

As a general rule, modern busses are hierarchical, and the hierarchy reflects the way the computer system is constructed. For example, a modern computer may have more than one logical processor/core in a given die or package, and have more than one die or package on the motherboard. A large computer (e.g. a mainframe) may have more than one motherboard connected by a backplane.

Every time you have more than one thing which needs to communicate with each other thing, you need a bus/switch/whatever to connect them together.

Here's a simplified example:

Each package or die comprises multiple logical CPUs which are connected by some kind of internal bus. These are then connected to a common bus which connect the CPUs together, along with high-speed/high-bandwidth peripherals such as RAM (which increasingly looks like a peripheral these days), coprocessors such GPUs, and fast devices such as gigabit ethernet, Fibre Channel, InfiniBand, etc.

This bus is then connected via interfaces to lower-speed busses such as PCI, USB, SCSI, I2C, etc. Most of the things that you typically think of as "peripherals" are connected to peripheral busses such as these.

Of course this is just an illustrative example, not based on any particular computer design. Different architectures do different things. Large-scale high-availability machines (e.g. modern mainframes) typically have "local" RAM for each CPU die or motherboard, and CPUs designed for those high-availability applications commonly have a backplane bus interface built onto each CPU package plus a redundant backplane connection hanging off the high-speed I/O bus.

So given all that, the term "processor bus" probably refers a bus which connects processors together. That would mean one of two things:

1. The bus connecting logical processors together within a single package or die.
2. The bus connecting processor packages or dies together.

# Answer
> 1 votes
Personally, I think the terms "processor bus" and "system bus" lead to confusion, one way to look at a processor bus vs a system bus is how Intel chips deal with messaging between the CPU and the system peripherals. Intel separates these into a "Northbridge" and "Southbridge".

# Northbridge

* Handles messaging between the RAM, CPU, and PCI-E.
* This is a "memory controller hub"

# Southbridge

* Handles BIOS, USB, PCI, IDE, Ethernet and other peripherals
* This is an "I/O controller hub"

---
Tags: computer-architecture
---


# Question
Title: boolean circuit to decide if there's a path of at most $k$ edges from $u$ to $v$ in graph $G$
> Let an undirected graph and $k\in\mathbb{N}$. Prove that there's a circuit of depth $2$, size of $n^{O(k)}$ and **unlimited fan-in**, which gets $\langle G,v,u\rangle$ as an input and checks if there's a path from $u$ to $v$ of at most $k$ edges.

So I'm familiar with Warshall's algorithm and I think I should utilize it here. The problem is that it seems impossible to do that with a depth-$2$ circuit.

I'd be glad if you could direct me what to do.

Thanks

# Answer
Since you are allowed an $n^{O(k)}$ size circuit, you could go over all possible $k$-length paths originating at $u$. The first level will contain $n^{O(k)}$ AND gates, one for every possible sequence of vertices $v\_1=u,v\_2,...,v\_l=v$, for $l\le k$, and in the second level you input the results of the previous level to an OR gate.
> 2 votes

---
Tags: algorithms, complexity-theory, circuits
---


title: Best case analysis for Shell sort

text:
# Question
Title: Best case analysis for Shell sort
The exercises in a textbook I studied asks about the best case for Shell sort. I have scribbled a derivation for the same along the margins almost two years ago. Basically I don't know if this was my own derivation or one copied from an authoritative source.

I have elaborated upon the same below. Could you let me know if the reasoning is right here?

* The least number of comparisons occur when the data is completely sorted.
* For a particular value of the increment, say, $h\_i$, each of the $h\_i$ sub-sequences require at most one less comparison than the number of elements in the sub-sequence(as insertion sort is used) which is,${N \over h\_i} - 1$ ,where N is the total number of data items.
* For the given data in this situation $h\_i \times \left (N \over h\_i - 1 \right ) = N - h\_i$ number of comparisons are needed as there are $h\_i$ sub-sequences.
* If the increment sequence selected is has $k$ increments(such that $h\_k = 1$), the total number of comparisons required would be $C(N) \ge (N - h\_i) + (N - h\_2) + ... + (N - h\_k) = kN - \sum h\_i = O(N)$

# Answer
> -1 votes
The best case for Shell sort is when the array is already sorted.
In that case the inner loop does not need to any work and a simple comparison will be sufficient to skip the inner sort loop.

A best case of $Θ(N)$ is reached by using a constant number of increments.
But the problem is that the best value for the gapping depends on the input. Therefore you cannot choose a single best value for the gap and must suffer a $log^2(N)$ delay due to repeated compares.

So you are almost correct. Obviously there is no way to compare fewer than N-1 elements before we can conclude that the array is already sorted, so $Θ(N\space log^2(N) )$ it is.

Note that this best case is for randomized Shell sort which is subtly different from the original.

See: https://arxiv.org/pdf/0909.1037.pdf

All this means that Shell sort is not a particularly good algorithm for a (nearly) sorted array. The gapping introduces redundant compares whereas other sorting algorithms only have to go over the array once in the best case.
When the array is random, the gapping works in your favor, and these other algorithms that perform so wonderfully on a (nearly) sorted array perform at a dismal $O(N^2)$

# Answer
> -1 votes
The best case is O(n). Here's why:

Let's start with insertion sort. An already sorted list of n entries will require n minus 1 comparisons to complete (no exchanges necessary).

Put the insertion sort in the context of a shellsort with a single increment - 1. An already sorted list of n entries will require n minus the gap (1).

Suppose you have two gaps 5 followed by 1 and n is greater than 5. An already sorted list will require n-5 comparisons to process the first gap (no exchanges necessary) plus n-1 comparisons for the second or 2n-6 (no exchanges necessary).

So the algorithm for the best case is "n\*number of gaps - the sum of all gaps".

I don't see how "n\*number of gaps - ..." could be anything other than O(n).

I know most discussions put it as something else and I get the impression that no one has bothered to sit down and do the math. As you can see, it's not rocket science.

---
Tags: algorithms, algorithm-analysis, runtime-analysis, sorting
---


# Question
Title: Is it possible to partially decide when will halt given any arbitrary input?
This is a problem that I think is a reduction from the halting problem. I have on two separate practice exams statements that,

> Given a Turing machine T and a string w, to determine whether T will halt when started on input w.

and

> Given a Turing machine T and a string w, to determine whether T will halt when started on a blank tape.

The answer key states that these problems are both partially decidable, which is astonishing to me given that they are reductions from the halting problem, which is undecidable.

If there was a Turing maching M, that would halt if it's input was another Turing machine T that also halted on an arbitrary string, would that not violate the halting problem? Why are the two above statements considered to be partially decidable?

# Answer
> 4 votes
The halting problem is not decidable, but it is still *partially decidable* (other terms for this are "recursively enumerable" and "Turing recognizable"). So, you are right that both of these problems are equivalent to the halting problem. That is why they are undecidable, but still partially decidable.

You may want to review the definition of "partially decidable" in your textbook or notes.

# Answer
> 1 votes
A problem $P$ is said to be partially decidable (or semidecidable, or recursively enumerable, or ... (too many other names for the same notion)) when there is a TM that can take any instance $x$ of the problem and:

1. if $x\in P$, the TM eventually accepts
2. if $x \not\in P$, the TM diverges

If we had rejection instead of divergence, we would have that $P$ is decided by such TM. However, the TM above does only "half" of the deciding: it recognizes all the $x$ to be accepted, but computes forever on those which should be rejected.

The halting problem falls into this case. It is easy to accept a halting TM: simulate it, and after it halts, accept. However, if this procedure is run on a diverging TM, the simulation diverges. So, this procedure is only semideciding the halting problem.

# Answer
> 0 votes
The above questions are semi-decidable because we can design a Turing Machine to "semi-decide" each of them. This means that the Turing Machine must only halt for strings that are in its language.

For the blank-tape halting problem, let's call our Turing Machine B. On input , where M is a Turing Machine, B simply simulates M on a blank tape. B halts and accepts if and only if M halts. We could design a similar Turing Machine to recognize the other language you gave.

---
Tags: turing-machines, halting-problem
---


# Question
Title: Cost in time of constructing and running an NFA vs DFA for a given regex
Repost from Stack Overflow:

I'm going through past exams and keep coming across questions that I can't find an answer for in textbooks or on google, so any help would be much appreciated.

The question I'm having problems with at the moment is as follows:

> Given a regular expression (a|bb)\*, derive an estimate of the cost in time for converting it to a corresponding NFA and a DFA. Your answer should refer to the size of the regular expression.

A similar question from another year is:

> Given that, for the above example, you know the size of the original regular expression, |r| and the size of the input string |x|, explain how you would calculate the cost in time for constructing and running the NFA versus constructing and running an equivalent DFA.

The resulting NFA for (a|bb)\* has 9 states, while the DFA has 4. Even knowing this, I have no idea how to approach the question.

# Answer
Preface: I asked this question yesterday, so don't assume I know what I'm talking about. This should get you on the right path (I hope), but don't take it as fact.

Remember to read the comments below. Much of the original answer is incorrect, but the tips from helpful and more experienced people below should help clear it up.

From my understanding of it, the cost in time (or memory) is based on orders of complexity. As per: http://en.wikipedia.org/wiki/Regular\_expression#Implementations\_and\_running\_times

* The construction time for a DFA from an NFA is O(2^m) where m is the number of nodes.
* The running time of a DFA is O(n) where n is the length of the input string. This is because there is only 1 path through the DFA for a given string.
* The construction time for an NFA should be O(m), where m is the number of nodes (don't quote me on that one, it's more of a semi-logical assumption than anything)
* The running time for an NFA is O(m²n) because it is non-deterministic and the computer must check every possible path for the current character in the string. (assuming no lookahead, it doesn't know what the next character will be so it runs into dead ends)

So for an NFA with 9 nodes (m) and an input string of length 4 (n):

* The construction time for the DFA is O(2^m) while the construction time for the NFA should simply be O(m). These equate to 512 and 9 respectively.
* The running time for the DFA is O(n) while the running time for the NFA is O(m²n) these equate to 4 and 1296.

For the sake of argument, we'll assume each operation takes 1 'tick' (could be operations, milliseconds, etc). If we convert to a DFA we're looking at 516 'ticks' to construct the DFA and check the string. If we run the NFA we end up with 1300 'ticks'. Without being given a running time for an operation or the clock speed of the processor, these are simply relative numbers and should be compared in relative terms.

As to questions that may ask whether it is 'worth converting' (sounds like a terrible question but hey), the answer is yes in most cases due to the fact that once constructed the DFA would be used to check multiple strings of varying length, making the construction time less relevant than the running time.
> 1 votes

# Answer
Kiliki's answer has some things wrong.

They say:

> The construction time for an NFA should be O(m), where m is the number of nodes (don't quote me on that one, it's more of a semi-logical assumption than anything)

This doesn't even really make sense. If you are constructing a NFA from a regular expression there are no well defined "nodes" to speak of. A sufficient algorithm is the Thompson's construction.

## Amortized time for constructing an NFA from a regular expression

A regular expression is composed *literal characters* stuck together in various ways

* **concatenation**
* **alteration** and
* **Kleene star**.

Thompson's construction defines rules for making an NFA for literal characters. For the character 'x' where `O`s are states.

```
       x
    O ---> O

```

There are other rules for concatenation, etc. that join together NFA's like the one above, but the important part is that any operation adds a small finite number of states and transitions (never more than two states or four transitions actually. If you want the details have a look at the super helpful wiki link above).

The number of literals and operations (concatenation, etc.) is easily determined from the length of the string of the regular expression. The amount of one or the other is different only by a constant factor. Thus we can safely say that constructing an NFA from a regular expression using Thompson's construction is O(n) where n is the length of the string of the regular expression.
> 2 votes

---
Tags: regular-languages, automata, finite-automata, compilers
---


# Question
Title: Given two $a^n b^n$-style languages, how do I find out if their intersection is regular?
I have two languages as below.

$$L\_1=\\{a^ncb^n\\}\cup\\{a^mdb^{2m}\\}$$ $$L\_2=\\{a^{2n}cb^{2m+1}\\}\cup\\{a^{2m+1}db^{2n}\\}$$

Now, I wonder what is $L\_1\cap L\_2$. Is it a regular language? Is it context-free?

---

To solve the problem, I feel like I need to solve the following system of equations, but I'm not sure.

$$ \begin{cases} 2n=2m+1\\ 2m+1=\frac{2n}{2} \end{cases} $$

# Answer
$L\_1=\\{a^ncb^n\\}\cup\\{a^mdb^{2m}\\}$

$L\_2=\\{a^{2n}cb^{2m+1}\\}\cup\\{a^{2m+1}db^{2n}\\}$

If we say $\\;L\_1=L\_{11}\cup L\_{12}\\;\\:$and$\\;L\_2=L\_{21}\cup L\_{22}$

$L\_1\cap L\_2=((L\_{11}\cap L\_{21})\cup (L\_{12}\cap L\_{21}))\cup ((L\_{11}\cap L\_{22})\cup (L\_{12}\cap L\_{22})) $

$L\_{11}\cap L\_{22}\\:,\\:L\_{12}\cap L\_{21}\\;$will be zero because d and c are different symbols.

So $\\;L\_1\cap L\_2=(L\_{11}\cap L\_{21})\cup (L\_{12}\cap L\_{22}) $

$L\_{11}\cap L\_{21}=\emptyset \\:\\;$because it is not possible for an even number to be equal to an odd number.

$\\;L\_1\cap L\_2=L\_{12}\cap L\_{22}=L=\\{a^{2m+1}db^{4m+2}\\}$

So the language is not regular but context free. It is impossible to construct a finite automaton for this language because finite automaton has a memory that is fixed and cannot thereafter be expanded. ( It cannot store number of a's ) But it is easy to recognize that L is context free since $L=(a(aa)^\*db^\*)\cap \\{a^ndb^{2n}|n\geq 0\\}$ ( intersection of a CFL with a regular language is CFL ) And $ \\{a^ndb^{2n}|n\geq 0\\} $ is context free because there exists a push-down automaton that accepts L. When this automaton sees an $\\:a\\:$ it pushes 2 $\\:a\\:$'s into the stack and when $\\:d\\:$ is the input it changes it's state to a final state and then for each $\\:b\\:$ it pops an $\\:a\\:$ from the stack.
> 2 votes

# Answer
Any string in the intersection of $L\_1$ and $L\_2$ must be in either the first subset of $L\_1$, hence has a 'c' in the middle, hence is ALSO in the first subset of $L\_2$, OR \[by similar reasoning\] is in the second subsets of $L\_1$ and $L\_2$. A string in the first subset of $L\_1$ has equal numbers of 'a'-s and 'b'-s, while a string in the first subset of $L\_2$ has an even number of 'a'-s and an odd number of 'b'-s, hence an UNequal number of 'a'-s and 'b'-s. Therefore there is NO string which is in the first subsets of both $L\_1$ and $L\_2$.

To be in the second subsets of both $L\_1$ and $L\_2$ IS possible: the number of 'b'-s must be twice the number of 'a'-s (by $L\_1$), and this is possible with $L\_2$ if $n\_1$ is odd and $n\_2$ = $2m\_2+1$ = $n\_1$ \[where '$n\_i$' means 'the $n$ in $L\_i$' etc\]. Therefore the language of the intersection is equal to the set of strings of the form $a^{2m+1}db^{4m+2}$, which is regular.
> 1 votes

---
Tags: formal-languages, regular-languages, context-free
---


# Question
Title: What is the theory behind testing fixes for intermittent bugs?
I ask this question because I deal with alot of intermittent bugs and want to be able to answer the question "Can I be at least 95% sure that my changes to the code fix the bug?". I've got some ideas on how one could formalize the problem, but I'm guessing that someone else has done this.

I'm particularly interested in theory where we do NOT already know a value of $p$ - the probability that a bug will hit. This means we'll likely have to assume some distribution on $p$.

It seems like this should be a known thing, especially within TDD. Some problems are just so hard that we have to rely on testing results. Thanks for any direction you can give me.

# Answer
You juggle with "probabilities" without defining any. There are two different questions here.

> For practical programs, can I use random testing to establish that any given execution has close to 100% success probability?

Not in the strict sense, no. Even if input spaces are finite, they are typically huge. Without further information, you'd have to test *a lot* of inputs (and/or contexts), which is not feasible. As in, solving most NP-complete problems is faster.

You *could* try to perform statistical testing, that is get some bound on the error for some statistical significance -- but that would assume that you have a model for the error distribution. Which I would be surprised to hear if you had. And even if, it's probably not one of those that mathematicians have bothered to explore. So, ballpark guess, statistical tests are impossible (or meaningless, if you went ahead and did the numbers assuming a normal model or something).

> Can I formalize programs and their execution so that I can make meaningful statements about (stochastic) bug-freeness?

Yes, sure. What you need are

* formal semantics,
* formal specifications, and
* a distribution of inputs.

Then, you can (in principle) prove (not test!) what the expected error rate is. I've never seen it done, though -- probably because it's at least as hard as proving the program correct in the first place.

If you ask me, you are better served with reasonable heuristics and solid processes. Specification testing may be helpful in certain contexts, just because it makes it easy to test many different variants.
> 2 votes

---
Tags: statistics, software-engineering, software-testing
---


# Question
Title: Data structure/aglorithm for strings to see if there exists two strings you can concatenate to get a target?
I want to come up with an arbitrary string, and feed it into my program to see if there exists two strings that I can concatenate to get the target string. What kind of data structure and algorithm would be good for this? I'm thinking a sorted array would be good, and then walk down the list, binary searching for the suffix/prefix needed. That would be O of NlogN I think.

# Answer
> 1 votes
Store the strings in a trie. Build a second trie that stores the reverse of the strings. Now you can quickly check whether the target string T is a concatenation of some pair of strings: start walking the first trie, using the left-most characters of T (walking left to right), and simultaneously start walking the second trie, using the right-most characters of T (walking right to left). By walking the first trie, you find all prefixes of T that are in the dataset; by walking the second trie, you find all suffices of T that are in the dataset; and then you can look for a pair of a prefix and a suffix of the right length to cover all of T (without overlap).

Your approach of storing the strings in sorted order is also reasonable, but you'll need two sorted arrays: one to store the strings; another to store the reverse of the strings. Given a target string T of length n, for each i, you look up T\[1..i\] in the first sorted array (using binary search) and look up reverse(T\[i+1..n\]) in the second sorted array (using binary search). As an optimization, start each binary search from where the previous search left off (i.e., once you've found T\[1..i\] in the first sorted array, that helps you find T\[1..i+1\]; you shouldn't need to start over from scratch.)

So yeah, your idea based on sorted arrays works too, though two tries might be somewhat more efficient.

---
Tags: algorithms, data-structures, strings
---


# Question
Title: What is an example of complex random string, in the Kolmogorov-Chatin sense?
Any string generated from a PRNG clearly has a very short description. You need the code for the random number generator, the seed, and then the number of times to iterate. So, it seems that all such strings have low KC complexity.

If the above it true, then what is an example of a "complex" string, in the Kolmogorov-Chatin sense?

# Answer
It is impossible to give a specific example of a string with high Kolmogorov complexity. If I was to give an example in this answer, then the following piece of code would retrieve it:

```
wget http://cs.stackexchange.com/q/9721

```

(plus some O(1) post-processing).

A string of high Kolmogorov complexity is as elusive as a random number:

There is in fact a connection between randomness and Kolmogorov complexity: a random string has maximal complexity for its length. (At least for one definition of randomness, appropriately called Kolmogorov randomness.)

This observation that it is impossible to exhibit a string of high Kolmogorov complexity can be put into a mathematical form and proved: it is called Chaitin's theorem.

The high-complexity strings are all the ones that you cannot describe.
> 7 votes

# Answer
New research since this question was asked may actually provide an answer, if I read it correctly.

One of the most complex\* 12 bit strings in the Kolmogorov sense is 001111000011, relative to all 5 state, 2 symbol Turing machines. It has a Kolmogorov complexity of approximately 37.06… bits, which is 11.45… bits higher than the simplest 12 bit strings. (which are twelve 0 bits in a row or 1 bits in a row)

* The inverse bit string has the same complexity. There are also two 12 bit strings that are uncomputable by 5 state Turing machines, so likely have a slightly higher Kolmogorov complexity.
> 3 votes

# Answer
The infinite string that has a 1 at the $i$-th position if the $i$-th Turing machine (in some fixed enumeration of TMs) halts on all inputs has a very high complexity.
> 2 votes

# Answer
Here is one example of a random string in the Kolmogorov sense:

kejrjtokplarkoprl\[paxes,0owp,itro,se0ofiespoKWP\[OLAOINJ-O2CLKSEJOPOS\[P3VTOIIOIopqwiodhriuropdiorpdioieurfpoiopdioiuoidurodpiwoptdopirtois02-9980uhoititoci0ieioq34u0-40brnjvhw09a3=-rjchgo0ewir
> 0 votes

---
Tags: kolmogorov-complexity
---


# Question
Title: does every graph have a complete, preferred, stable and grounded extension?
I was looking at graph extensions in argumentation theory and was wondering, which of those extensions does every graph have? and which of those only some graphs have? and is there a proof for each?

thanks

# Answer
As a complete extension is an admissible set containing exactly these arguments it defends, there is always at least one complete extension, that may be the empty set and nothing else.

Grounded extension is a minimal complete extension, hence there is always one, and it also has the property to be a unique fixed point.

Perferred extension are maximal complete ones, hence starting from the same principle (there is at least one complete extension) there should always be at least one.

As far as I know, the notion of stable extension is not so well-defined and their existence therefore depends on the chosen definition.

You can probably work out additional properties from the paper

Baroni, P., Caminada, M., & Giacomin, M. (2011). An introduction to argumentation semantics. The Knowledge Engineering Review, 26(04), 365-410.
> 2 votes

---
Tags: graphs, artificial-intelligence
---


# Question
Title: Why top down merge sort is popular for learning, while most libraries use bottom up?
Most libraries use some variation of bottom up merge sort, but top down merge sort seems to dominate web sites and forums.

Assume reasonably optimized implementations, where a single working array is used in addition to the original array, and copy or copy back avoided in top down merge sort by tying the direction of merge (to or from the working buffer) based on level of recursion (bottom up does this based on merge pass), then the key differences are the generation and storage of indices for runs via recursion and storage on the stack for top down versus iteration and storage possibly in registers for bottom up, and cache locality affected by the order of merge operations (top down is depth first, left first, while bottom up is breadth first).

For cache locality issues, assuming at least a 4 way set associative cache, that's enough for 2 lines for input, and 1 line for merged output, and the merge operation is a sequential operation for the 2 input runs and the merged output run. It's not clear to me if there are a few levels of recursion for top down versus passes for bottom up where top down is more cache friendly.

In all the benchmarks I've run, bottom up merge sort is faster than top down, which would explain why most libraries use some variation of bottom up merge sort. As array size increases, the relative difference decreases because most of the time is spent in a merge function that can be identical for top down and bottom up.

From a historical perspective, going back to the days of disk or tape sorts, merge sort started out as bottom up merge sort (or a variation called polyphase merge sort).

My questions are when and why top down merge sort became more popular in a classroom environment, or later on the web?

---

Update - I'm also wondering why bottom up merge sort seems to be so rarely seen in a classroom environment, web sites, or forum sites. My guess is that 80+% of the questions about merge sort at Stack Overflow are about top down merge sort. I only recall one question about bottom up merge sort in the last month or so.

# Answer
Because top-down mergesort is conceptually simpler, and fits right into the curriculum of new computer scientists that learn about recursion. A small constant performance difference between top-down and bottom-up is irrelevant for its educational value.
> 6 votes

# Answer
Merge sort is often paired with quicksort as the next sort algorithm after the O(n^2) sorting algorithms. This also tends to coincide with recursion as a concept.

Quick sort has to be done top down. So explaining the merge sort in the same vein (split the input and sort the parts merge after) is easier to grok.

Bottom up has much better cache performance because the cache predictor will read ahead in the array as you are iterating over the input and output arrays. In the top down you will restart often which messes up the cache predictor and the beginning of the array may have been flushed from cache at that point. It also has less random branches which means the branch predictor is also much happier.
> 3 votes

---
Tags: mergesort
---


# Question
Title: Genetic algorithm does not always find the global optima and a higher mutation rate finds a better solution
I wanted to make a tool which minimizes the interference between antennas.

Currently, the tool is very limited for prototyping reasons. It can only place an antenna every 1 meters. The available space that the antennas can be placed is 1 dimensional and is 15 meters wide.

The user can only decide how many antennas will be used (e.g. 3 antennas).

I decided to encode the setup as follows: a binary array where 1 represents an antenna and 0 is an empty space because it seemed straightforward. The length of the array is thus the available space to place those antennas (= 15 meters).

For example, here are all the antennas on the left: **11100 00000 00000** and here they are on the right: **00000 00000 00111**.

My mutate function enforces that the offspring contains only 3 antennas. If it is not the case the mutate function will try again. Same thing for the crossover.

In this case, the total search space consists of 455 solutions since there are only 455 ways to place those antennas.

I benchmarked a little bit the algorithm and I got the following results:

* If I use a 5% of the search space, thus a population of 7 with 4 generations (7 * 4 = 28) then I got a solution which is better than 96% of the 455 solutions.
* If I use a population of 10% of the search space, thus a population of 9 with 5 generations (9 * 5 = 45) then I got a solution which is better than 98% of the 455 solutions
* The higher the mutation rate the better the results. This one is very strange since the algorithm becomes more and more a random search. I thought that it should normally give worst results. The difference of the results is 1-2% better when using a mutation rate of e.g. 0.8 instead of 1 / n = 1 / 15 (where n is the length of the encoding).

Finally, I have two questions:

I got a good solution but never the best one, even by using 10% of the search space. Is this normal?

A higher mutation rate gives me better results? Is it because I am working with a toy problem? Or is my encoding bad?

# Answer
> 2 votes
I'll start with the second question because it's easier. How could increasing the mutation rate improve the results?

Genetic algorithms can beat random searches when they converge on the right answer. Similar to other machine learning algorithms, genetic algorithms have an "explore" phase and a "converge" phase. If the algorithm doesn't run long enough (enough rounds) to enter the converge phase, then a higher mutation rate will likely give you better results. The other culprit may be that the utility score of offspring may be independent of the utility score of the parents even though their parameters are very similar. If this is the case (especially around "good" results) then convergence may be impossible and random search would outperform genetic algorithms.

The other question "Why didn't I ever find the best solution?" could also have a few explanations. First, you could have just been unlucky - especially if you didn't run your experiment very many times. Intuitively, a single run searching 10% of the space will have roughly a 10% chance of finding the best solution. Second, it may be that all antenna configurations which are similar to an optimal solution have low scores. This would make it less likely to produce the optimal solution genetically.

# Answer
> 1 votes
I would say you have at least chosen a bad encoding. At minimum, enforcing that all crossover or mutation results have exactly three 1-s limits the possible population members to a very sparse subset of the chosen binary space.

Further, this encoding doesn't appear to work well according to G.A theory. The power of a well-designed genetic search derives (according to theory) from *implicit parallelism*. The idea here is that each explicit population member - say '1101100010' - also *implicitly* represents all of its sub-patterns - eg, '1xxxxxxxxx', 'xx011xxxxx', 'x1xxxx0xx0', and so on, where 'x' is a don't-care. If in the current population, all members matching '1xxxxxxxxx' have a higher average fitness than all members matching '0xxxxxxxxx', then members starting with a leading 1 will tend to fill up subsequent generations. These combinations are called 'schema'; while a G.A is explicitly evaluating $N$ explicit designs at a time, it is *implicitly* evaluating at least $N^3$ schema at a time. But that only works if each schema is manifested by a large number of possible population members. Your encoding seems to greatly cut down the number of achievable schema.

Also, the whole point of crossover is to combine as many good schema from the parent members as possible, while disrupting as few as possible. In your encoding, if (for example) one parent has all three 1-s to the left, and the other has all three 1-s to the right, enforcing only three 1-s in the child actually destroys all meaningful schema from both parents. And that is the *typical* outcome.

What you need is an encoding where all, or nearly all, possible strings represent legitimate legitimate population members, and where crossover naturally produces legitimate members. For some reason my gut instinct here is to advise you to study the encoding schemes used to apply G.A-s to the Travelling Salesman problem.

---
Tags: algorithms, optimization, genetic-algorithms
---


title: Cache (TLB) - fully associative cache

text:
# Question
Title: Cache (TLB) - fully associative cache
I have an exercise and I don't understand the solution.

```
Given memory data ranging from 1A0040h:
000102070405060708090A0B0C0D0E0F101112131415161718191A1B1C1D1E1F

Given memory data ranging from 1A0090h:
202122272425262728292A2B2C2D2E2F303132333435363738393A3B3C3D3E3F

Given memory data ranging from 7B0040h:
404142474445464748494A4B4C4D4E4F505152575455565758595A5B5C5D5E5F

Given memory data ranging from CD0090h:
606162676465666768696A6B6C6D6E6F707172777475767778797A7B7C7D7E7F

Given memory data ranging from FF0040h:
808182878485868788898A8B8C8D8E8F909192999495969798999A9B9C9D9E9F

Given memory data ranging from AD0040h:
A0A1A2A7A4A5A6A7A8A9AAABACADAEAFB0B1B2BBB4B5B6B7B8B9BABBBCBDBEBF

```

Given the fully associative cache at size 4 (4 cache lines) with counter, with 16 Byte data space

Describe the contents of the cache after these steps:

1. Reading from 1A0046
2. Write F to the address 1A0053
3. Reading from 7B0049h
4. Reading from FF0042h

This is the solution:

How do I fill an empty table to get to the answer?

/*Reading from 1A0046 means reading all 16 Byte and what about the writing?*/

Thanks.

# Answer
> 0 votes
So, the cache tags at the 16 byte address range, so the tags for 4 reads are as given (as you simply drop the last nibble of the address - which then becomes the offset in the range 0x0 - 0xF).

The cache reads from the 16 byte division, so for the first read it reads the first 16 bytes in from 0x1A0040 (which covers the range sought).

In the second the cache reflects the data from 0x1A0050 with the write as required.

From the third the cache line begins at 0x7B0040 (with the tag dropping the nibble) and so on...

---
Tags: computer-architecture, cpu-cache
---


# Question
Title: Are poly-reductions to PSPACE problems for following problems are known?
List of problems I'm interested in:

1. $\oplus$SAT
2. #SAT-decision
3. Permanent-decision (YES if permanent is greater than given number $k$)

I have discovered poly-reduction for MAJSAT (and MAJQBF). However, I don't know such reduction (practical) for these problems.

How can I solve any of these problems with polynomial runs of TQBF? Or can I make a special TQBF to solve them. The special TQBF length should increase (not more than) polynomially compared to original problem.

# Answer
> 2 votes
The reduction you refer to is called Turing reduction. Given $A,B\subseteq \Sigma^\*$, we say $A\le\_T B$ if there exists a polynomial time Turing machine which decides $A$, given oracle access to $B$. You might call this practical, and in some sense this is the natural way to say $A$ is no harder than $B$ (give me a program for $B$, and i'll write an efficient program for $A$ which uses the previous program as a subroutine).

The standard notion of reduction in complexity theory is Karp reduction (also called many to one reduction). We say $A$ is reducible to $B$ in this sense, if there exists a polynomial time computable function $f$ such that $x\in A \iff f(x)\in B$. Note that this is a weaker condition, i.e. if $A$ is Karp reducible to $B$, it is also Turing reducible to $B$ (apply $f$ on the input, and query the oracle on the result).

Since TQBF is PSPACE complete, then by definition, every language in PSAPCE has a Karp reduction to it (and thus also a Turing reduction). Not only that we know there exists such a reduction, but given a PSPACE machine for some language $L$, then we know how to construct a reduction from $L$ to TQBF (this is done in the proof for the PSPACE completeness of TQBF).

The decision versions of $\\#P$ problems are in PSPACE, since you can go over all possible witnesses and count how many are accepting (the only thing you need to store is the counter). This means that all such problems are reducible to TQBF. This is a very precise statement, but intuitively, it says exactly what you want it to. If you can efficiently decide TQBF, then you can efficiently decide all languages in PSPACE, which includes the decision versions of #SAT and permanent.

---
Tags: algorithms, complexity-theory, time-complexity, decision-problem
---


# Question
Title: How to determine convergence when using Q-learning?
I'm using Q-Learning to find the values of states in on a gameboard. For example, something like:

```
-----------------
|   |   |   | 1 |
-----------------
|   | W |   | -1|
-----------------
|   | W |   |   |
-----------------
| S |   |   | 1 |
-----------------

```

I have the transition, and I can calculate the values of the states, but I can't tell when to stop computing. Normally I would just compute until a terminal state, for x-episodes; but this particular board has no terminal states. So I'm stuck to just calculating the values over say 1000 iterations (the more the more accurate obviously). I would like a way to stop though when I'm within an acceptable range.

How is this normally done for a non-terminal state space?

# Answer
> 1 votes
There are two ways that I know of: First, based on how many iterations, like you would do. Second, based on the difference between current Q value and previous Q value (i.e., insignificant difference means termination).

---
Tags: artificial-intelligence, reinforcement-learning
---


# Question
Title: What is the type of linked list where order doesn't matter
I'm reading the The Algorithm Design Manual book on Data Structures and it says the following about linked listed implementation:

> Insertion into a singly-linked list is a nice exercise in pointer manipulation, as shown below. **Since we have no need to maintain the list in any particular order**, we might as well insert each new item in the simplest place. Insertion at the beginning of the list avoids any need to traverse the list, but does require us to update the pointer (denoted l) to the head of the data structure.

I'm wondering what kind of list is that because I can't use it for index based access. All other basic implementations I've seen provide index based access.

When searching for an item, their implementation shows direct object comparison:

```
list *search_list(list *l, item_type x)
{
    if (l == NULL) return(NULL);
    if (l->item == x)
        return(l);
    else
        return( search_list(l->next, x) );
}

```

So I'm thinking maybe they didn't account for index based access.

This book also distinguishes `Container` and `Dictionary` categories of DS:

> We use the term container to denote a data structure that permits storage and retrieval of data items independent of content. They are distinguished by the particular retrieval order they support (LIFO, FIFO). By contrast, dictionaries are abstract data types that retrieve based on key values or content.

It seems that the linked listed implementation at hand falls into a container category with the object reference as the key, something alike a map DS.

Is this assumption valid?

# Answer
> 2 votes
I took a look at the book you are referencing, and it does appear that Steven Skiena made an unordered Dictionary implemented as a linked list. It's not a terribly efficient data structure, but he was only using it to illustrate basic linked list coding techniques, so I expect he just wanted to keep things as simple as possible.

For what it's worth, a stack is a container that only allows you to add to or access from the very top item, which isn't really *index based* in the way we'd usually use that term. I mention this only to highlight that Containers do not need to have index-based retrieval.

---
Tags: data-structures, linked-lists
---


# Question
Title: Why is average waiting time is the same for FIFO and LIFO
I'm reading the The Algorithm Design Manual book on Data Structures and it says the following about FIFO and LIFO containers:

> Support retrieval in first in, first out (FIFO) order. This is surely the fairest way to control waiting times for services. You want the container holding jobs to be processed in FIFO order to minimize the maximum time spent waiting. **Note that the average waiting time will be the same regardless of whether FIFO or LIFO is used**. Many computing applications involve data items with infinite patience, which renders the question of maximum waiting time moot.

Can someone please explain what is meant by minimizing maximum time spent waiting and why the waiting time is same for FIFO and LIFO?

Thanks

# Answer
> 2 votes
Maybe an example will help, consider lets say for 3 minutes we add 2 tasks each minute, and we process 1 task a minute. With a FIFO queue the timeline will be:

* t(0): 'a' and 'b' added: \[a, b\] - 'a' processed after waiting $0$ - \[b\]
* t(1): 'c' and 'd' added: \[b, c, d\] - 'b' processed after waiting $1$ - \[c, d\]
* t(2): 'e' and 'f' added: \[c, d, e, f\] - 'c' processed after waiting $1$ - \[d, e, f\]
* t(3): \[d, e, f\] - 'd' processed after waiting $2$ - \[e, f\]
* t(4): \[e, f\] - 'e' processed after waiting $2$ - \[f\]
* t(5): \[f\] - 'f' processed after waiting $3$ - \[\]

Average wait time: $(0 + 1 + 1 + 2 + 2 + 3) / 6 = 1.5$, longest wait time: $3$

Then consider a LIFO stack:

* t(0): 'a' and 'b' added: \[a, b\] - 'b' processed after waiting $0$ - \[a\]
* t(1): 'c' and 'd' added: \[a, c, d\] - 'd' processed after waiting $0$ - \[a, c\]
* t(2): 'e' and 'f' added: \[a, c, e, f\] - 'f' processed after waiting $0$ - \[a, c, e\]
* t(3): \[a, c, e\] - 'e' processed after waiting $1$ - \[a, c\]
* t(4): \[a, c\] - 'c' processed after waiting $3$ - \[a\]
* t(5): \[a\] - 'a' processed after waiting $5$ - \[\]

Average wait time: $(0 + 0 + 0 + 1 + 3 + 5) / 6 = 1.5$, longest wait time: $5$

# Answer
> 1 votes
The example by @MattD is great inspiration to see what happens. Note how there is a difference between *maximal* and *average* waiting time. The maximal waiting time *can* be optimized.

The average waiting time equals the *total waiting* time divided by the number of tasks. So you can prove that the average waiting time is the same under all executions by looking at the total waiting time. This can be done as follows. Look at any two tasks and swap them. This will not change the total waiting time: one will be $x$ units faster, the other $x$ units later. (This even holds when swapping a task to a time before it was added, but that is a mathematical curiosity...) This reasoning only holds when all tasks are of the same length.

---
Tags: data-structures, stacks, queues
---


title: $e^{-5}$ error using Taylor's series

text:
# Question
Title: $e^{-5}$ error using Taylor's series
I am a student and I was reading Numerical Analysis by Burden. In one of the exercises, I have to calculate $e^{-5}$ in two ways.

The first is using the Taylor's series for $x=-5$, $( e^{-5} = 1 - 5/1! + 5^2/2!-...)$ and second way is calculating $e^5$ and then $e^{-5}=1/e^5$, again using Taylor's series but this time for $x=5$. In his solution, he says second way gives better results because we avoid subtraction. I think that it has to do with the floating point system but I am not very sure so I thought someone could further explain it to me. (Sorry if I have made any mistakes. English is not my native language)

# Answer
Use a spreadsheet and calculate $e^{-100}$ both ways. It will become totally obvious what is going on. "We avoid subtraction" is not the problem. The problem is that you are adding the sum or difference of large numbers, and each large number has a large rounding error. For one method, the rounding error is not large compared to the result. For the other matter, the rounding errors are huge compared to the result.
> 1 votes

# Answer
Once you expand the series for

$$e^{(-x)} $$

you are going to get alternative negative terms as we can see the nth derivative of

$$e^{(-x)} = (-1)^n * e^{(-x)} $$

therefore the author advises to use the other method instead.
> 0 votes

---
Tags: numerical-analysis
---