# Question
Title: Any proof of correctness of the Toom-Cook algorithm?
I found the toom-cook algorithm here: http://www.cs.cmu.edu/~ab/Desktop/15-211%20Archive/res00037/Multiplication\_1\_print.pdf

and have been trying to chase down proof of it being correct, but can't find anything. Does anyone know how to go about proving the algorithm? I was thinking induction but I can't even figure out how to do it.

This is just for the three-way splitting, page 6. Any ideas?

# Answer
If you're only interested in the three-way splitting…

We know that any natural number is a linear combination of powers of ten, where the coefficients are in the range \[0,9\]. This is our writing system for numbers: the coefficients are simply the digits of the number.

Let's assume that our number has at least six digits (just for simplicity). If it has less than that, we don't need Toom-Cook: $n$ is bounded by a constant, so we can do the multiplication in $O(1)$.

So our number can now be written as $a\_0 10^0 + a\_1 10^1 + a\_2 10^2 + \cdots + a\_n 10^n$, where all $a\_i$ are single-digit non-negative integers. And $n$ is at least 6.

We also know that we can find $p$ such that $|(n - 2p) - p| \leq 1$. (If $n$ is divisible by 3, then $p = \frac{n}{3}$. If $n-1$ is divisible by 3, then we let $(n-2p)$ be larger by 1. And if $n-2$ is divisible by 3, then we increase $p$ by 1.)

Now, through the laws of multiplication and exponents, it's clear that our number is equal to $(a\_0 10^0 + a\_1 10^1 + \cdots) + (a\_p 10^0 + a\_{p+1} 10^1 + \cdots) 10^p + (a\_{2p} 10^0 + a\_{2p+1} 10^1 + \cdots) 10^{2p}$.

Thus, the number can be divided into three generally-close-to-equal parts, as the paper says.
> 2 votes

---
Tags: algorithms, correctness-proof
---


# Question
Title: is an empty string accepted by this NFA accepters
is the string epsilon(empty string) accepted by this NFA ?

# Answer
> 2 votes
I think this question could be much better worded if you asked

"If the starting state $q\_0$ is also an accepting state, is the empty string $\lambda$ also accepted if it leads to a non-accepting state $q\_2$?"

But regardless, the short answer is yes, as greatly explained by Mr. Draconis above.

One of the fundamental differences between DFA's and NFA's is the transition function $\delta$.

Remember that for DFA's, $$\delta : Q \times \Sigma \rightarrow Q$$

This means that the transition function takes an **internal state** and an **input alphabet** as arguments, and **returns an internal state**.

But for NFA's, $$\delta : Q \times (\Sigma \cup \\{\lambda\\}) \rightarrow \\{Q\\}$$

Notice that the differences are the curly brackets around the returned $Q$ and the union of the set containing the empty string $\lambda$ with $\Sigma$. This is the same as the DFA's $\delta$, but this time the function **accepts the empty string as input** and returns a **set of internal states rather than a single state**.

So as Mr. Draconis mentioned, the empty string is also accepted by the given NFA because it leads to $\\{q\_0, q\_2\\}$ with $q\_0 \in F$.

# Answer
> 1 votes
The short answer is, yes.

To process an NFA, you start with an initial state set $Q\_0 = \\{q\_0\\}$. Then, for each step, you take one character of input, then form the next state set by following all possible transitions from all states in the previous set.

In this case, your initial state set is $\\{q\_0\\}$, and after reading no input your state set is $\\{q\_0, q\_2\\}$. There is an accepting state in this state set, so the NFA accepts the empty string.

# Answer
> 0 votes
A DFA is defined as a tuple $⟨Σ,Q,δ,q\_0,F⟩$. The state $q\_0$ is your initial state, and also an element in your set of accepting states $F$. If you process the empty string, you will make no transition, and you will still be standing in an accepting state. Therefore the DFA accepts the empty word.

---
Tags: finite-automata
---


# Question
Title: Relative order of values and weights in Knapsack
In knapsack problem, we have some items with some values and weights. We also have a knapsack with a specific capacity, and we intend to fill the knapsack with these items. The main objective of this problem is to maximize the value of items in the knapsack.

Knapsack can contain maximum 11 kg items

item1: value(1) weight(1 kg)

item2: value(6) weight(2 kg)

item3: value(18) weight(5 kg)

item4: value(22) weight(6 kg)

item5: value(28) weight(7 kg)

Are the items also sorted by their weights when we sort them by their values ?

In other words, are the weights parallel with the values ?

For example, can the item2 have a value 20 but its weight is equal to 2 kg ?

# Answer
> 1 votes
The weights and values can be arbitrary. In particular, if you sort the items by their weight, then they need not be sorted by their value.

More generally, if you look at a formal definition of the Knapsack problem, you will see that nothing is mentioned about the possible weights and values of the items (beyond their being positive integers). *Every instance which conforms to the definition is valid.*

In other words, you should be able to answer such questions by looking at the formal definition of the problem. There is no hidden information which can only be obtained by asking questions on forums. Indeed, it is exactly the opposite — the problem statement defines the problem *completely*.

---
Tags: knapsack-problems
---


# Question
Title: Determining whether the language of a DFA is closed under reversal
The question and its answer is given below:

> Let $S = \\{ \langle M \rangle \mid \text{$M$ is a $\textsf{DFA}$ that accepts $w^{\mathcal{R}}$ whenever it accepts $w$}\\}$. Show that $S$ is decidable.
>
> **Answer:**
>
> For any language $A$, let $A^{\mathcal{R}} = \\{w^{\mathcal{R}} \mid w \in A\\}$. If $\langle M \rangle \in S$, then $L(M) = L(M)^{\mathcal{R}}$. The following $\textsf{TM}$ $T$ decides $S$.
>
> $T = $ “On input $\langle M \rangle$, where $M$ is a $\textsf{DFA}$:
>
> 1. Construct $\textsf{DFA}$ $N$ that recognizes $L(M)^{\mathcal{R}}$.
> 2. Run $\textsf{TM}$ $F$ from Theorem 4.5 on $\langle M,N \rangle$, where $F$ is the Turing machine deciding $EQ\_{\textsf{DFA}}$.
> 3. If $F$ accepts, *accept*. If $F$ rejects, *reject*.”

But I do not understand in the first line of the answer, in the second statement why does it say that $L(M) = L(M)^{\mathcal{R}}$, could anyone explain this for me please?

# Answer
For a language $L$, we define the *reverse language* $L^{\mathcal{R}}$ by $$ L^{\mathcal{R}} = \\{ x^{\mathcal{R}} : x \in L \\}. $$ In words, $L^{\mathcal{R}}$ is obtained from $L$ by reversing all words.

It follows that $L = L^{\mathcal{R}}$ if and only if, for each word $x$, we have $x \in L \Leftrightarrow x^{\mathcal{R}} \in L$.
> 1 votes

---
Tags: turing-machines, computability
---


# Question
Title: Fibonacci Series with Dynamic Programming
We can compute Fibonacci numbers by means of dynamic programming approach. If we do not store intermediate solutions, we cannot use them for future necessities. In this case, asymptotic complexity reaches exponential time.

```
             f(5)    -> 2^0
            /    \
           /      \
          f(4)    f(3)   -> 2^1
         /   \    /   \
       f(3) f(2) f(2) f(1) ->2^2
      /   \
     f(2)f(1)............

```

Each recursive call consumes only O(1) time.

T(n) = 2^0 + 2^1 + 2^2.... (geometri series)

T(n) = (2^n - 1) / 2 - 1

T(n) = O(2^n)

In some places, it is written that n is size of the problem, but I think n is number of levels in recursion tree. Is n equal to size of the problem or number of recursion levels ?

# Answer
$n$ is the index of the Fibonacci number you're computing. For example, the sixth Fibonacci number, $f(6)$, is equal to 8.

If we assume that function calls take constant time and we are using your model, then it's clear that the number of calls, $C(n)$, to compute the $n$-th Fib will be given by $$C(n)=C(n-1)+C(n-2)$$ with $C(0)$ and $C(1)$ both being 1.

Hmm. That recurrence is almost exactly the recurrence for the Fibs, just shifted by a place, so we have $C(n)=f(n+1)$. In other words, the asymptotic growth of $C(n)$ is the same as the Fibs themselves.
> 1 votes

# Answer
It's *both* (up to a possible off-by-one error). If you look at the left-most branch of the recursion tree, it's labelled $f(n)$, $f(n-1)$, ..., so the number of levels of the tree is equal to the index of the Fibonacci number you're computing (plus or minus one, depending on where exactly you stop the recursion).
> 1 votes

# Answer
n-th number of Fibonacci series is : f(n) = f(n-1) + f(n-2) with f(0)=1 & f(1)=1 if we don't use Dynamic programming time complexity will be O(2^n) but if we use space of O(n) we can do it in O(n) ! We allocate an array A of size n; then we set A\[0\]=A\[1\]=1; now we calculates eazh A\[i\] i\>2 by having A\[i-1\] and A\[i-2\] as below : A\[i\] = A\[i-1\] + A\[i-2\] so a for loop in O(n) computes f(n) !!
> -1 votes

---
Tags: asymptotics, dynamic-programming
---


title: Word arrangement in caches

text:
# Question
Title: Word arrangement in caches
Why are the words in a cache line adjacent to one another? Does this arrangement improve reading/writing performance or are there other reasons to justify this choice?

# Answer
> 1 votes
Because it's common for programs to access data sequentially.

This arrangement of the cache will make sequential data access more efficient. In particular, when the program accesses the first word, that word and subsequent words in the same cache line are all loaded into the cache, so when the program accesses the next word, it will already be cached and access will be very fast.

Any other arrangement would make sequential access slower.

---
Tags: cpu-cache
---


# Question
Title: Ensure groups of four 3-tuples have 9 unique numbers
Note: I know the numbers are arbitrary, but this problem about this size has practical implications. It is an applied algorithm problem.

Suppose you have 200 bins. Each bin would be very happy to have the integer sequence: 1, 2, 3, 4, 5, 6, 7, 8, 9. And the algorithm would be very happy if all bins get that.

The algorithm is allowed to choose four 3-tuples from a collection of 800 3-tuples. It will assign assign 4 of them to each bin. So each bin will have four 3-tuples assigned to them. These 3-tuples have the following properties:

1. They are pseudo-randomly generated all at once as a collection of 800 3-tuples.
2. Each number in a generated 3-tuple is unique. For example, (1, 1, 2) and (7, 4, 4) are impossible but (1, 2, 3) and (8, 2, 9) are possible.
3. Each value within the 3-tuple can only be a number from 1 to 9. For example, (10, 3, 15) is an impossible tuple. The 3 could occur, but 10 and 15 could not.

A corollary from point 1 is that it could be the case that some integers occur less than the amount of bins that exist. In such a case the application would be very happy if as many bins get a numerical sequence from 1 to 9 and the other bins get as close as possible to such a sequence. For example, suppose that the number 9 has been randomly generated in 180 3-tuples, then at least 20 bins will not get the number 9, but they hopefully should be able to get the integers 1 to 8.

Here is an example of 2 bins and 8 3-tuples. The following numbers are pseudo-randomly generated.

```
(3, 8, 2)
(2, 1, 5)
(2, 7, 8)
(7, 8, 5)
(7, 8, 4)
(7, 5, 8)
(7, 9, 5)
(4, 7, 3)

```

Assigning them to two bins as optimal as possible by the requirements yields:

```
Bin 1 - Sequence: 1, 2, 3, 4, 5, 7, 8, 9
(2, 1, 5)
(4, 7, 3)
(7, 9, 5)
(7, 8, 5)

Bin 2 - Sequence: 2, 3, 4, 5, 7, 8
(2, 7, 8)
(7, 8, 4)
(7, 5, 8)
(3, 8, 2)

```

Note: in this particular example there is no 6. There is one 1 and one 9. This means that the 1 and the 9 automatically go to Bin 1. The integer 6, well it simply isn't there, so it cannot be assigned to a bin.

**My first question:** Design an algorithm that ensures the most optimal solution.

**My second question:** is a generalized or analogous version known as a certain problem or field in mathematics?

I suppose this problem is a variant of the set cover problem. However, instead of covering a universe, 200 'universes' need to be covered. Or said in another way: the universe needs to be covered 200 times in such a way that the cover can be split up into 200 groups of four 3-tuples.

# Answer
I suspect finding the optimal assignment will be NP-hard in theory and possibly hard in practice, but it might be possible to find a near-optimal solution.

One approach is to express this as an instance of integer linear programming, and use an off-the-shelf ILP solver. Let $x\_{i,j}$ be a zero-or-one integer variable, with the intended meaning that $x\_{i,j}=1$ implies the $i$th tuple is assigned to the $j$th bin, and $y\_{j,d}$ another zero-or-one variable, with the intended meaning that $y\_{j,d}=1$ means that digit $d$ is covered in bin $j$. Then you can write down a set of linear inequalities on the $x$'s and $y$'s that captures what constitutes a consistent and valid solution.

For instance, the constraints might be: $\sum\_j x\_{i,j} = 1$ (each tuple is assigned to one bin), $\sum\_i x\_{i,j}=4$ (each bin receives 4 tuples), $y\_{j,d} \ge x\_{i,j}$ if the $i$th tuple contains digit $d$, and $y\_{j,d} \le \sum\_i x\_{i,j}$ where the sum is over all tuples $i$ that contain digit $d$. Now you want to maximize the linear objective function $\sum\_{j,d} y\_{j,d}$. Then, you could use an off-the-shelf ILP solver to try to find an optimal solution to this linear program, or ask it to report the best solution it can find within a given time bound.

I don't know if there is a better approach. You could look at algorithms for exact cover to see if any of them can be adapted to your setting.
> 1 votes

---
Tags: approximation, set-cover
---


# Question
Title: An axiomatic theory of computational models?
There are many different computational models, e.g. Turing machines, register machines, lambda calculus, etc.

I am wondering if there exists an axiomatization of computation, that abstracts away from the specifically constructed computational model.

I.e. is there a more general theory about computation that deals with computational machines that are not perfectly specified, but that still captures their common characteristic as computation machines?

# Answer
> 4 votes
The question "what is a computational model" is quite open ended and is difficult to answer definitely. It's a bit like asking "what is geometry". But people have given some answers.

As far as I can understand you, you are looking for a general **theory of computation** (so, not a model that "contains other, for what's that supposed to mean, nor an "axiomatization" of a specific thing). One such theory is offered by partial combinatory algebras (PCA), which are very simple structures that subsume many models of computation, including: Turing machines (with and without oracles), $\lambda$-calculus (with many of its extensions), enumeration operators, and even topological models of computation. There are further variants of PCAs: ordered PCAs, typed PCAs, etc.

One should never just "collect models of computation" but also ask how to relate them, so we should think about transformations between PCAs. John Longley gave a very good account of these, namely the applicative morphisms. Speaking a bit vaguely, an applicative morphism is an interpretr of one PCA implemented in another PCA.

If you are interested in this topic you can consul Jaap van Oosten's book on realizability.

---
Tags: computation-models
---


# Question
Title: In a bloom filter, why does the optimal number of hashes *increase* with the number of bits in the filter?
Multiple resources, such as Wikipedia, state that if you have an $m$-bit Bloom filter with $n$ elements inserted, then the optimal number $k$ of hash functions to use is

$k = \frac{m}{n} \ln 2$

This is very counterintuitive. If $m$ is the number of bits in the filter, then as you increase $m$, why would the optimal number of hashes have to *increase* to reduce the rate of false positives?

Intuitively, as you increase $m$, the number of collisions goes *down*. So, as $m \to \infty$, using only one hash function would yield a 0% false positive rate. But this equation would say that as $m \to \infty$, you would need $k \to \infty$ as well. Why?

Is there some way to understand this?

# Answer
This balances two considerations:

* The more hash functions you have, the more bits will be set in the Bloom filter when you create the filter (because each element you insert causes up to $k$ bits to be set in the filter). The more bits that are set, the higher the risk of false positives.
* The more hash functions you have, the less likely that one of them triggers a false positive (because a false positive will be triggered only if *all* of the bit positions you inspect are set, and the number of bit positions you inspect is equal to the number of hash functions).

So, increasing the number of hash functions ($k$) has two effects, one of which increases the likelihood of false positives, and the other of which decreases the likelihood of false positives. To figure out how to balance those two, you need to work through the math.

I suspect your intuition was missing the second factor, and once you take that into account the result will feel less absurd.

---

I agree that if you hold $k,n$ fixed and increase $m$, then the false positive probability will decrease. But it would decrease *even more* if you held $n$ fixed and increased both $m$ and $k$ (due to the way the math works out, and due to the second consideration above).
> 9 votes

---
Tags: bloom-filters
---


# Question
Title: How to keep track of changes done to concurrent stacks?
I am writing a small RPN calculator that works on some stacks concurrently. For example, if I have two functions:

```
add-int(a: int, b: int): a b +
add-float(a: float, b: float): a b +

```

and I have two stacks with the following:

```
Int [1 2 3]
Float [4.0 5.5]

```

I can just do:

```
add-int add-float

```

and the new stacks will be:

```
Int [1 5]
Float [9.5]

```

Everything works well there, but if I were to add parametric polymorphism with this function:

```
add-num(a: num, b: num): a b +

```

Then it would not work as one would expect. Is it going to add the two integers or the two floats? or perhaps one from each?

To solve the issue, I added a new stack `Num` that keeps the address of every number pushed into the other stacks to keep a sense of history, but it created two new issues.

First, memory addresses take a lot of space, sometimes more than the data itself, and this would only get worse if I were to add new number types like ratios and complex.

Second, what if I wanted to pop a number that is on top of the stack for its type but way behind in the `Num` stack.

For example:

```
> 1 2 3.14 4.0 5/5  -- This is the expression.
Int [1 2]  -- These are the stacks.
Float [3.14 4.0]
Ratio [5/5]
Num [&Int[0] &Int[1] &Float[0] &Float[1] &Ratio[0]]

> add-int  -- Then I do this.

```

If I call the function above, there is no issue popping the two integers, but what about deleting the two pointers in the `Num` stack? It can get pretty expensive to look for the element and remove it every single time a number is popped.

**I have realized that this approach is not pretty effective in terms of space consumption and performance, so is there an alternative, more efficient way of keeping track of the changes done to these stacks?**

# Answer
> 1 votes
I would use doubly-linked lists instead of opaque stacks for this.

```
Node = {
    type : "INT" or "FLOAT"
    value : int or float
    prev-generic : pointer to Node
    next-generic : pointer to Node
    prev-specific : pointer to Node
    next-specific : pointer to Node
}

```

Now you can keep three lists: a list of ints (using the specific pointers), a list of floats (using the specific pointers), and a list of both (using the generic pointers). If you keep track of the head of each list, you can treat them as stacks (pushing and popping in $O(1)$), and a popped node can also be deleted from both stacks in $O(1)$ just like in a normal doubly-linked list.

---
Tags: concurrency, memory-management, stacks
---


# Question
Title: Prove correctness of the iterative algorithm
**Description:**

Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

**Code:**

```
class Solution {
    public int removeElement(int[] nums, int val) {
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                nums[count++] = nums[i];
            }
        }
        return count;
    }
}

```

The problem may seem very simple but the solution I came up with is quite intuitive and hence it may be prone to errors in situations like interviews, I would like to know if there is some sort of formal check for the correctness? if yes then, is there any generic approach?

# Answer
Let `Nums` be the value of the array *after* method execution, and `nums` the initial value. Let,

```
P(i) = Nums[0..i-1] is the same as nums[0..i-1], but ignoring `val`.

```

Your algorithm is correct if `P(nums.length)` is true. This can be shown by realising that `P` is true at the beginning of the loop, and each iteration of the loop *preserves* `P`.

Initially, `i = 0` in the `for` loop, and we have

```
   P(0)
 = Nums[0..0-1] is the same as nums[], but ignoring `val`.
 = Nums[] is the same as nums[], but ignoring `val`.
 = true

```

Next, assuming `P(i)`, for $i \leq nums.length$, show `P(i+1)` ;-)

---

This is some of the work of the Hoare Calculus mentioned above.
> 1 votes

---
Tags: algorithms, arrays, correctness-proof, program-correctness, iteration
---


# Question
Title: Time Complexity of Basic Primality Test Algorithm
The algorithm I'm referring to is one of the most fundamental primality checks: For a number, $n$, check if it is divisible by some odd number, $k$, less than or equal to $\sqrt{n}$. Assume $n$ is a fixed size and that all basic arithmetic operations (add, subtract, multiply, divide, remainder) run in $O(1)$. I don't see why this algorithm will not be $O(\sqrt{n})$, but apparently it's not since PRIMES was considered an NP problem up until the AKS primality check.

# Answer
The problem with your statement is that you assume that all the basic arithmetic operations are $O(1)$ and that the amount of numbers you will have to check is $O(\sqrt{n})$, relative to the size of the input.

This is wrong because $\text{PRIMES}$ is the language of all the prime numbers, given in a binary format. So an input of length $n$ will be a number of size $O(2^n)$. Then, if the input is some number $x$, in order to check all the numbers up to $\sqrt x$ you will have to go over $O(\sqrt{2^n})$ numbers, which is $O(2^{n/2})$ numbers. Even with $O(1)$ operations this will not take a polynomial amount of time.
> 4 votes

---
Tags: runtime-analysis
---


# Question
Title: Time complexity of sum of $2^n$ values of polynomials
First a simpler question: let $q\_{1}(k),\dots,q\_{n}(k)$ be $n$ polynomials of degree smaller or equal to $n$.

Let $f(n): \mathbb{N} \rightarrow \mathbb{N}$ defined by $f(n) = \sum\_{i=1}^{n}q\_{i}(n)$.

Assume also $0\leq f\_{i}(n)\leq n$.

What is the time complexity as a function of the input size for calculating $f(n)$ by the above definition?

I'm not quite sure how to approach this, but my current guess is as follows:

I know evaluating a polynomial is $O(n)$ time, where $n$ is the degree of the polynomial.

I know adding two integers is $O(n)$ where $n$ is the number of bits of the larger integer.

Every try to calculate this seems to get stuck, as i'm getting confused between the time complexity by input size and by actual size (the number itself).

after understanding this, i would like to understand the calculation for time complexity as a function of the input size for a similar problem:

Let $q\_{1}(k),\dots,q\_{2^n}(k)$ be $2^n$ polynomials of degree smaller or equal to $2^n$.

Let $f(n): \mathbb{N} \rightarrow \mathbb{N}$ defined by $f(n) = \sum\_{i=1}^{2^n}q\_{i}(n)$.

Assume also $0\leq f\_{i}(n)\leq 2^n$.

Thanks for any help, i hope this is well enough defined.

# Answer
> 1 votes
It takes $O(n^2)$ time. A polynomial can be represented as the list of its coefficients. Since it has degree $n$, it can be represented by a list of $n+1$ numbers. Now adding polynomials can be done by adding their corresponding coefficients. There are $n+1$ coefficients of $f(n)$, and each takes $O(n)$ time to compute (you have to add up $n$ numbers), for a total of $O(n \times (n+1)) = O(n^2)$.

There's no possibility to do anything faster, as the input contains $n(n+1)$ numbers, and any correct solution will have to read all the input. It takes $\Theta(n^2)$ time even to read the input, let alone to do any processing, so any correct algorithm will have to take time at least $\Theta(n^2)$.

With this, you should now be able to do a similar analysis for the variant you list near the end of your question.

---
Tags: time-complexity, polynomial-time
---


# Question
Title: DFS vs. Union Find for computing connected components of a static graph
According to CLRS,

> When the edges of the graph are static—not changing over time—we can compute the connected components faster by using depth-first search.

However, I tried to do some runtime analysis, and in a graph $G(V, E)$ on which we have to answer $Q$ connectivity queries.

DFS would take $O(V+E)$ asymptotic time to calculate the connected components, followed by $O(1)$ to answer each query, which leads to a total running time of $O(V+E+Q)$.

Whereas, an optimised Union Find would take $O(E.α(V))$ time to “add” all the edges, followed by $O(α(V))$ per query, which gives a total running time of $O(α(V).(E+Q))$.

Now, as we, know $α$ can be taken to be a constant factor for all practically conceivable applications, so Union Find works out to be faster, hence I am confused as to why the authors of CLRS call DFS faster.

Am I making a mistake with my analysis somewhere?

# Answer
Your running time analysis of Union-Find is incorrect. To use Union-Find for this situation, we need to perform $V$ MakeSet operations, $E$ Union operations, and $2Q$ Find operations. Each operation takes $O(\alpha(V))$ amortized time. Therefore, the total running time for the Union-Find-based algorithm will be $O(\alpha(V) (V+E+Q))$ ... not $O(\alpha(V) (E+Q))$ as you claimed. I suspect you forgot the cost of the MakeSet operations.

It seems clear that $O(\alpha(V) (V+E+Q))$ is asymptotically slower than $O(V+E+Q)$, or at least no faster.

If you care, you can reduce the running time of DFS to $O(E+Q)$ and the running time of the Union-Find algorithm to $O(\alpha(V) (E+Q))$. Basically, you first scan the graph to remove all isolated vertices (vertices with no edges incident on them). You know that the isolated vertices aren't connected to anything, so they can be ignored. Then, run your algorithm on the resulting graph, after removal of isolated vertices. For the resulting graph, we have $E/2 \le V \le E$, so $V = \Theta(Q)$ and $O(V+E+Q) = O(E+Q)$ and $O(\alpha(V) (V+E+Q)) = O(\alpha(V) (E+Q))$.
> 3 votes

# Answer
When the graph is dynamic, union-find can update the list of connected components in time $O(\alpha(V))$ per vertex or edge, whereas it is not clear how to run DFS progressively. So we can complement the statement you quote by

> When the edges of the graph are dynamic – changing over time – DFS is not a good choice since it cannot be applied progressively; we can compute the connected components faster by using union-find.

That said, union-find is helpful only if edges and vertices are never deleted.
> 5 votes

---
Tags: graphs, runtime-analysis
---


# Question
Title: Can agent be autonomous without having consciousness?
My intuition is that 1) self-awareness (modeled through epistemic modal logics); 2) goal reasoning (e.g. https://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/view/12292) and 3) consciousness (e.g. Integrated Information Theory) are the necessary and sufficient features for agent to be truly autonomous. Especially - consciousness is the key feature of autonomy. So - can truly autonomous (human-level autonomy) agent exist without consciousness?

Of course, I am thinking about autonomy not ultimate freedom. E.g. every agent can be autonomous but it will be bounded by 1) scarcity of resources; 2) ultimate goals and values which will be inscribed into agent by the humans.

# Answer
> 1 votes
Here is a glimpse.

Concerning agents you're trying to elaborate here,I would like to give you some insights of these following key aspects,which might help in your future research nor knowledge;

* Consciousness Here an agent is capable of understanding its own existence nor selfawareness.
* Intelligence An agent is capable solving problem based reasoning with no help from third-party knowledge.
* Autonomous An agent has the ability to solve problems basing on the third-party knowledge for instance,self driving car does its own problem solving basing on the existing knowledge it discovers from the environment.

> Therefore,for any agent to be autonomous,it doesn't mean its selfaware or conscious,otherwise. For your information,do further reading on the above three terminologies.

---
Tags: logic, agent-based-computing, philosophy
---


# Question
Title: This doesn't seem like a valid regular grammar; my instructor says it is
The following is a screenshot of a lecture slide from my programming language concepts course:

According to Wikipedia and other sources, a regular grammar is one that is either *left linear* or *right linear*, meaning it has at most:

* one nonterminal symbol on the left end of its right hand side

e.g., A -\> Ba

* one nonterminal symbol on the right end of its right hand side

e.g., A -\> aB

But if we follow this definition, then the "regular grammar" in the screenshot above isn't really a regular grammar because it has two nonterminal symbols on its right hand sides.

My teacher argues it "technically" is because:

> Identifier -\> Identifier Letter

is "essentially" the same as writing multiple things like:

> Identifier -\> Identifier 'a'
>
> Identifier -\> Identifier 'b'
>
> ...

More generally, my instructor says that if a grammar's production rules can be reduced to a form where they have at most one nonterminal symbol, then that grammar is regular. To me, this doesn't seem correct—because then essentially, just by substitution, we can reduce any grammar we want to a regular form. And it seems to destroy the definition/restriction imposed on regular grammars, which is that they may have at most one nonterminal.

Could someone please clarify whether this is in fact a valid regular grammar?

# Answer
Your teacher is wrong, unless of course s/he does not adhere to the wikipedia definitions. It is "technically" equivalent to a regular grammar, but that is not a well defined concept. What can we allow as extensions that give us "technically" regular grammars.

There is a concept that is perhaps suited. That is *self-embedding*. A variable $A$ is self-embedding if $A\Rightarrow^\*uAv$ for non-empty $u,v$. A grammar is *non self-embedding* if none of its variables is self-embedding. Every non self-embedding context-free grammar has an equivalent regular grammar, which was already observed by Chomsky. With this concept we extend the regular grammars, while we are certain to stay within the regular languages.

And, since you are asking more details, your instructor is wrong again on the single nonterminal remark. Such grammars also include $S\to aSb\mid \varepsilon$ for which every sentential form has (at most) one nonterminal, but for which the language is non-regular. In fact these languages are called linear, and form a family between regular and context-free.

Note that $S\to AB, A\to aA|\varepsilon, B\to Bb|\varepsilon$ defines a regular language (mixing leftmost and rightmost). On the other hand $A\to aB\mid\varepsilon, B\to Ab$ is nonregular. This exemplifies the non self-embedding distinction.
> 3 votes

---
Tags: formal-languages, regular-languages, formal-grammars
---


title: Polynomial-Time Reduction

text:
# Question
Title: Polynomial-Time Reduction
I have read many resources, but I cannot understand what the polynomial-time reduction is. In everywhere, this is explained with standard-pattern sentences.

Please can anyone explain it in detailed version ?

# Answer
> 5 votes
I think your best bet is probably to get an introductory text on the theory of computation and/or take a course on the subject. I think the typical courses teach quite a lot before getting to polynomial time reduction, so you are most likely skipping over a lot prerequisite material. I'll try to give a common language understanding of what a polynomial time reduction is without too many details.

First you have to understand what a reduction is, so I would start here. To quote the linked wikipedia page:

> In computability theory and computational complexity theory, a reduction is an algorithm for transforming one problem into another problem. A reduction from one problem to another may be used to show that the second problem is at least as difficult as the first.

If you want to understand it precisely you should carefully read the definition section of the page. The situation where we are interested in reductions can be roughly described as attempting to encode problems that we know are "hard" or complete for a class as a newly defined problem that we are unsure about. This will prove that the new problem is at least as hard as the one that we know to be hard.

In the vaguest sense you can think of a polynomial time reduction as a reduction that requires $O(n^k)$ steps (for a fixed k). So we require polynomial time in order to transform any instance of the "hard" problem into an instance of the new problem. Again the wiki page gives a description of different types of polynomial time reductions.

---
Tags: np-complete, polynomial-time
---


# Question
Title: Find largest subset of vertices in graph so that every pair of vertices have an edge between them
Let's say you have a graph like this:

##

The largest subset of nodes so that every pair of vertices have an edge between them is $\\{3, 5, 7, 12\\}$. The second largest subsets are

* $\\{4, 7, 21\\}$,
* $\\{3, 5, 7\\}$,
* $\\{3, 5, 12\\}$,

etc.

Is there an algorithm to find the largest subset efficiently?

Also, keep in mind that I know virtually nothing about graphs (haven't learned at school, haven't taught myself). The data was originally given as a set of pairs of numbers.

# Answer
> 2 votes
Unfortunately, the answer is no.

In graph theory, such a subset is called a *clique*. (Essentially, a graph is a set of nodes and a set of edges between those nodes, and a clique is a set of nodes in a graph such that every node in the set has an edge to every other node in the set.) What you want is to find the largest clique in a given graph.

This is called the Maximum Clique Problem, and it's NP-hard. The decision problem version, "is there a clique with size $k$?", is in fact NP-complete. So an efficient solution to the Maximum Clique Problem would prove that P=NP and earn you the $1,000,000 prize and eternal fame.

---
Tags: graphs
---


title: DFA impossible problem?

text:
# Question
Title: DFA impossible problem?
As you can see from the title this is the impression that i have on this problem, but probably it isn't impossible.

The required DFA is :

"The set of the strings with equal number of 0 and 1 such that for each prefix the difference between the number of 0's and the number of 1's is minor(\<) than 2".

Maybe I've misread the requirements I've thought of them as follows :

* by prefix I thought of all the strings with length \< than the original one, for example in my opinion the prefixes for "cat" are "c" and "ca" but not "cat";

+ "the difference between the number of 0's and the number of 1's is minor(\<) than 2" by this i thought that we should have (number of 0 - number of 1) \< 2, but now I'm realazing that even (number of 1 - number of 0) \< 2 should be fine.

One user suggested to do this :

"Note that you can build a simple DFA which checks if the difference between the number of ones and the number of zeroes never exeeds 2 for any prefix of the input string: Add accepting states qk for −2≤k≤2 (where q0 is the initial state) and a rejecting sink state qs with transitions qk→qk+1 via 1 and qk→qk−1 via 0 for appropriate values of k and qk→qs for the other values."

but I don't understand quite well what it means, I've tried some solutions on my own and they don't work properly :

Any possible solutions? EDIT The DFA should be impossible as a matter of fact : here is the explanation

# Answer
> 2 votes
Note: I am the user who gave the comment cited in the OP on the CSTheory thread. Also, I am writing this as an answer rather than a comment to JohEker's post as I do not have enough reputation here to comment.

---

The idea is to exploit that we have a finite, local bound on the difference between zeroes and ones in the input word, i.e. we accept every word where this difference does not exceed 1 at any point. Note that if we drop the requirement that this holds for all prefixes, then the language is not regular (and thus not recognized by a DFA) by the Myhill-Nerode theorem as pointed out by JohEker.

So let $\\#0(w)$ and $\\#1(w)$ denote the number of ones and zeroes in the word $w$ respectively. To build a DFA from the idea above, we see that a word $w$ should be accepted if every prefix $v$ of $w$ satisfies $|\\#1(v) - \\#0(v)| \leq 1$, or equivalently $-1 \leq \\#1(v) - \\#0(v) \leq 1$. We can keep track of the value $\\#1(v) - \\#0(v)$ by creating a state for every value of it that we care about and specifying transitions between these states to model how the counter changes when we read a $0$ or a $1$. Combining this with our previous idea that we only need to know if the value of the counter is between $-1$ and $1$, we create three states $q\_{-1}, q\_0$ and $q\_1$.

Clearly we want the initial value of the counter to be $0$, so we use $q\_0$ as the initial state of our automaton and we transition from $q\_k$ to $q\_{k+1}$ if we read a $1$ (for $k \in \\{-1, 0\\}$ -- else we leave the space of values that we are interested in; more on this later) and similarly we transition from $q\_k$ to $q\_{k-1}$ (for $k \in \\{0, 1\\}$). As we want to accept the words for which the counter ends up at 0, we also define $q\_0$ as the only accepting state.

Now, what happens if the counter does not stay within $\\{-1, 0, 1\\}$? We want to reject the input.

In our automaton, this corresponds either to reading a $0$ while we are in the state $q\_{-1}$ (i.e. we have $\\#1(v) - \\#0(v) = -1$ that for the input $v$ before reading the $0$ and thus $\\#1(v0) - \\#0(v0) = -2$) or reading a $1$ while we are in the state $q\_1$. So we introduce a new, "rejecting" state $q\_s$ (also called a *sink-state* as the DFA cannot escape from this state once it is reached) which we transition to in case we detect one of the above-described scenarios. This now completes the description of our DFA, which looks like this:

# Answer
> 0 votes
How does the formal description of this language look like? A finite DFA does not support infinite languages that require to balance the different parts together, because we would have to keep building new states forever. Lets say we have L = {0^i 1^j | i = j}. Which is, we need to start making 0s, and then we need to make equal amount of 1s. This would be easy for the strings {"01", "0011" "000111"}. By just manually add that path of states to the DFA. But what happends with this string s = "00000000001111111111". We would have to make a path allowing exactly ten 0s, followed by ten 1s, and we would have to add another path for the next string, we would eventually run out of memory.

Using the pumping lemma for regular languages, we can also see that languages such as this are not regular, and if it is not regular, it simply cannot be converted to a DFA.

EDIT: Reading the question again i realised the language does not force us to give the stringbuilds in specific order, therefore by always controlling `| #0(w) - #1(w) | < 2` and then accepting when the difference is 0, we can do something like this.

---
Tags: automata, finite-automata
---


# Question
Title: Descriptive complexity: 3-colorability example
So in Neil Immerman's book http://books.google.co.kr/books?id=kWSZ0OWnupkC&pg=PA113&lpg=PA113#v=onepage&q&f=false, 3-colorability problem in descriptive complexity fashion is expressed as following: $\exists R \exists Y \exists B \forall x \left\[(R(x) \vee Y(x) \vee B(x)) \wedge (\forall y) (E(x,y) \rightarrow \neg(R(x) \wedge R(y)) \wedge \neg(Y(x) \wedge Y(y)) \wedge \neg (B(x) \wedge B(y))) \right\]$.

My previous question seems to have been misunderstood - I was not asking about what first-order or second-order logic is, but rather on the use of quantifier. Here $\forall x$ seems to imply that universe is already predefined to refer to vertices only. Is this correct understanding? If so, why is it the case? Is it pre-defined rule of descriptive complexity usage of logic?

Also for any similar graph problems, is universe of sets restricted to vertices only, or are we allowed to add sensible sets to universe?

# Answer
The convention in descriptive complexity is that for graph properties, the universe always consists of the set of vertices, and there is an additional two-place edge relation.
> 2 votes

# Answer
To expand a bit on Yuval Filmus' answer:

> Here ∀x seems to imply that universe is already predefined to refer to vertices only. Is this correct understanding?

Yes.

Implicitly, descriptive complexity is querying a model(?). Here's a quote from the beginning of the book:

"A structure with vocabulary τ is a tuple, A = ⟨|A|,R1A,...,RrA,cA1 ,...,cAs ,f1A,...,ftA⟩ whose universe is the nonempty set |A|"

The model is |A|.

When you're dealing with graphs, usually the model is the set of vertices. For the edges there would be a binary relation E, which you see in your query.

Although I suppose you could encode the graph differently, if you wanted.
> 1 votes

---
Tags: complexity-theory, logic, descriptive-complexity
---


# Question
Title: PCP is decidable over the unary alphabet
Show that the Post Correspondence Problem (PCP) is decidable over the unary alphabet ? = {0}.

# Answer
I will use the following formalization: A PCP-instance is a set $X = \\{(a\_1, b\_1), ..., (a\_n, b\_n)\\}$ where $a\_i, b\_i \in \Sigma^\ast$ where $\Sigma = \\{0\\}$ is our alphabet (note that thus every $a\_i, b\_i$ is of the form $0^k$). Such an instance is a yes-instance if there exists a finite sequence $I \in \\{1, ..., n\\}^m$ such that $a\_{I\_1}...a\_{I\_m} = b\_{I\_1}...b\_{I\_m}$.

Now, obviously, if there exists a pair such that $a\_i = b\_i$, then we have a yes-instance and if $|a\_i| \< |b\_i|$ (or, by symmetry, $|b\_i| \< |a\_i|$) for all $i$, then the instance must be a no-instance. Otherwise, there exist $i \neq j$ such that $|a\_i| \< |b\_i|$ and $|a\_j| \> |b\_j|$ and note that the problem now boils down to finding $k\_i, k\_j \in \mathbb{N}$ such that $k\_i \Delta\_i = k\_j \Delta\_j$ where $\Delta\_i = |b\_i| - |a\_i|$ and $\Delta\_j = |a\_j| - |b\_j|$. But this equation clearly has a solution for all $(\Delta\_i, \Delta\_j) \in \mathbb{N}^2$ by simply choosing $k\_i = \Delta\_j$ and $k\_j = \Delta\_i$, giving us that $$ a\_i^{\Delta\_j} a\_j^{\Delta\_i} = b\_i^{\Delta\_j} b\_j^{\Delta\_i} $$ as $|b\_i^{\Delta\_j}| - |a\_i^{\Delta\_j}| = \Delta\_j (|b\_i| - |a\_i|) = \Delta\_i \Delta\_j$ and $|a\_j^{\Delta\_i}| - |b\_j^{\Delta\_i}| = \Delta\_i (|a\_j| - |b\_j|) = \Delta\_i \Delta\_j$ and thus, $$ \begin{align} |a\_i^{\Delta\_j} a\_j^{\Delta\_i}| - |b\_i^{\Delta\_j} b\_j^{\Delta\_i}| &= |a\_i^{\Delta\_j}| + |a\_j^{\Delta\_i}| - |b\_i^{\Delta\_j}| - |b\_j^{\Delta\_i}| \\ &= (|a\_j^{\Delta\_i}| - |b\_j^{\Delta\_i}|) - (|b\_i^{\Delta\_j}| -|a\_i^{\Delta\_j}|) \\ &= \Delta\_i \Delta\_j - \Delta\_i \Delta\_j\\ &= 0 \end{align} $$.

Hence, it suffices to check whether there exist $i, j$ such that $|a\_i| \leq |b\_i|$ and $|b\_j| \leq |a\_j|$ (output yes if this is the case and no otherwise) and it follows that the PCP over unary alphabets is decidable.
> 2 votes

---
Tags: computation-models
---


# Question
Title: Perfect (or almost perfect) Hash function for n bit integers with exactly k bits set
I have a a data set with 2598960 elements of of unsigned integers of (at most) 52-bit length. The data set has a property that exactly 5 bits set.

This is only 1 data sets – I have similar data sets of integers with exactly 6, 7 and 9 bits set.

Given this peculiar property of the data set, is there a way I can create a minimum perfect hash function other than the method proposed here, which I rejected as lookup requires 2 hashes and dealing with negative hash results by using an if statement?

I am not looking for a ranking/unranking solution. As that is dependent on the fact that all ranks be present, I am looking for a more general solution that can take advantage of the fact that only k bits are set.

Additionally if a non hashing solution is proposed, Performance should be similar to a hash table i.e. O(1)

# Answer
The problem is trivial. You don't need a data structure to store this data set. There are only ${52 \choose 5}=2598960$ possible 52-bit integers with 5 bits set. You say that your data set contains 2598960 distinct 52-bit integers with 5 bits set. That means that every possible 52-bit integer with 5 bits set appears exactly once in your data set. Therefore, rather than using a fancy data structure to store the data set, don't store anything.

You can test whether a given integer is in the data set by simply testing whether it has 5 bits set or not. You can also enumerate all elements in the data set by enumerating all 52-bit integers with 5 bits set, which is straightforward to do. You don't need a hash function, or a data structure, or indeed to store anything at all.

Since this answer is trivial, I suspect you must actually be wondering about something else, but I can't quite understand what, from what you have written.

Perhaps you are wondering how to convert a 52-bit integer with 5 bits set into a number in the range 0..2598959, or vice versa. If so, look into ranking and unranking algorithms: see, e.g., https://oeis.org/wiki/Ranking\_and\_unranking\_functions, https://computationalcombinatorics.wordpress.com/2012/09/10/ranking-and-unranking-of-combinations-and-permutations/, https://en.wikipedia.org/wiki/Combinatorial\_number\_system. That's exactly what they do, and there are elegant and efficient algorithms for solving this problem. Then, you could store those numbers in sorted order, or store them with a bitvector (with $i$th bit in the bitvector indicates whether the number $i$ is present, i.e., whether the 52-bit integer with rank $i$ is present in your dataset).

In summary, let me outline the possible solutions and the extent to which they meet the stated requirements:

* Use the FNV algorithm for perfect hashing. You have already rejected this as too slow.
* Don't store any data structure. Just remember that every 52-bit integer with 5 bits set is in the dataset, and any time you want to enumerate the data set or test for presence in the dataset, reconstruct the data. This requires no storage and is very fast, and meets all of your stated requirements. However, it is not a general solution. It is specific to the fact that you stated your dataset contains exactly 2598960 distinct integers. If your dataset had anything less -- for example, a dataset with 1000000 52-bit integers with 5 bits set -- then this would not be possible. So this is very specific to the particular numbers in your post, and is not at all general.
* Use ranking/unranking to convert each 52-bit integer into a short number, then store the resulting numbers using any standard data structure for sets (e.g., a sorted array or a bitvector). This is a general solution that should meet all of the stated requirements, including minimal space and fast lookup. It is not perfect hashing, and it is not the same as the FNV hash.
> 2 votes

# Answer
If all you know about the dataset is that it is a subset of the binary representations of the 5-combinations of 52, then there are 2598960 different possible potential values and the only way to avoid a collision is to assign each element to a distinct integer in a set of 2598960 different integers. That's isomorphic to a ranking algorithm, and provides for a hash of less than 22 bits.

Undoubtedly, if your dataset only contains a small subset of that universe, a smaller hash would be useful. Any perfect hash algorithm will work unmodified. You could run the perfect hash algorithm on the 22-bit rank rather than the 52-bit representation, but the possible gains are probably not sufficient to overcome the cost of computing the rank. And that is the best use you can make of your knowledge about the domain restriction.

I don't know anything about you application environment but it is quite possible that you could achieve better performance with a simpler hash function and an efficient hash table implementation. For example, for fixed datasets, cuckoo hashtables can guarantee that only two locations need to be examined in a `find` operation. To compute the two locations, two different hash functions are used but since the hash computations are completely independent, the two computations can be performed in parallel. That might be an improvement over the FNV algorithm. The cost of this guarantee is a maximum load factor of 0.5, which is a lot worse than the FNV algorithm, but might still be bearable for small datasets.
> 1 votes

---
Tags: hash, hash-tables
---


title: Context-free grammars for two languages

text:
# Question
Title: Context-free grammars for two languages
How do I write context-free grammars for the following languages?

1. $B\_2 = \\{0^n1^n \mid n \> 0\\} \cup \\{0^n1^{2n} \mid n \> 0\\}$
2. $B\_3 = \\{a^nb^mc^k \mid k = n+m\\}$

Can someone help me? I'm not sure how to deal with the exponents.

# Answer
I'm also in a position of still learning (in fact I'm currently taking a Theory of Computation course at school), and I used to have the same problem as you.

The tip that I taught myself and always tell myself is to:

**Look for patterns. The trick is to observe the exponents and see what kind of pattern or relationship they have (e.g. where are the terminal symbols located, how many are there in relation to each other, etc.).**

Let's take grammar $B\_2$ as an example.

The condition for the exponent $n$ is $n \gt 0$, so we know that the empty string ($\lambda$ or $\epsilon$ whichever you prefer) is *not* accepted, because if $n = 0$ then $0^01^0 = \lambda$ and $0^01^{2\times0} = \lambda$.

Next, what kind of pattern regarding exponents does the grammar have? First of all, you're very fortunate that there's only one exponent here, which makes it much simpler. Regardless of how the value of $n$ changes, the pattern of the grammar will always follow the same pattern.

For $\\{0^n1^n | n \> 0\\}$, the immediate things we recognize are that: 1) 0's come before 1's, and 2) the number of 0's and 1's are the same.

How could we create a production rule for this?

The first thing to keep in mind is that the position of 0's and 1's doesn't change, so it's better if we anchor them down like this:

$$S \rightarrow 01$$

This takes care of the first string in the grammar, $01$. How do we produce this string in an infinite manner? We could keep repeating the variable $S$'s production, right?

Therefore,

$$S \rightarrow 0S1\ |\ 01$$

This is the context-free grammar for the first portion of $B\_2$.

As Mr. Filmus has mentioned in the comments, see for yourself if you can make a context-free grammar for $\\{0^n1^{2n} | n \gt 0\\}$ *(Hint: How are the placements of 0's and 1's? How many 1's are there for every 0?)*. If you can, then remember the theorem that states: "If $L\_1$ and $L\_2$ are both context-free grammars, then they are closed under union."

Grammar $B\_3$ is a bit trickier, but I think if you keep the tips I gave you in mind it's easily solvable with the same concepts.

Hope this helps. Good luck!
> 0 votes

# Answer
Some ideas on how to tackle the B2 language.

The exponents are telling us the correlation between the number of 0s and the number of 1s. {0^n 1^n | n \> 0} Accepts all strings that starts with an arbitrary amount of 0s, and ends with the same amount of 1s. {0^n 1^2n | n \> 0} accepts all strings that starts an arbitrary amount of 0s and ends with the double amount of 1s. The union of these languages will therefore accepts any string satisfying the first language or any string satisfying the other language.

So if we had a CFG S, such that

```
S -> A
A -> 01 | 0A1

```

Would this one be able to create all the strings accepted by the first language?

Can you figure out how to finish the construction of the CFG, so that it also is possible to create strings accepted by the other language?
> 0 votes

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


# Question
Title: How would a Turing Machine recognize n consecutive characters
I have difficulties understanding how a TM could count number of characters. I have this problem where the input is made out of characters $\\{a, b\\}$ and I need to accept if there are $n$ characters of type a in the string. The formal definition for the input language is:

$$ L=\\{ \\{w,n\\}\in\\{a,b\\}^\*\times \mathbb{N} \mid n\neq 0, \exists \alpha,\beta\in\\{a,b\\} \text{ s.t. }w=\alpha a^n\beta\\}. $$

What I do not understand is how could I hold the count since I need to have exactly n characters.

# Answer
What answer I came up with would be this. We would use a TM with 2 tapes, t1, t2 and 2 headers h1, h2.

* P0. Scan the first tape with the input, if a character ∉ {a, b} REJECT.
* P1. Write "#" and n character of "1" on t2, the head remaining in the right extremity.
* P2. Read characters on t1 and while they are "a" repeat P3, P4.
* P3. Move h1 to the right
* P4. Read the character on t2 and if it's "1" move h2 to the left, if it's "#" move h2 to the right extremity.
* P5. If the read character on t1 is "b" repeat P6
* P6. Read the character on t2, if it's "1" move h2 to the right extremity, if it's "#" ACCEPT
* P7. Getting at the end and not accepting means we REJECT

I had no example so I am not sure this is 100% correct but it's what I came up with after few hours of thinking. Hope it helps someone and please correct me if it's wrong.
> 0 votes

---
Tags: formal-languages, turing-machines
---


title: CIRCUITSAT ∈ DTIME(2^n/n^c) ⟹ NP ≠ EXP?

text:
# Question
Title: CIRCUITSAT ∈ DTIME(2^n/n^c) ⟹ NP ≠ EXP?
$\mathsf{EXP}\not\subseteq \mathsf{DTIME}(2^{n})$ and $\mathrm{CIRCUITSAT}\in \mathsf{DTIME}({2^{n}})$ holds and so why does $\mathsf{NP}\neq \mathsf{EXP}$ not hold while we know $\mathsf{NP}\subseteq \mathsf{DTIME}({2^{n}})\implies \mathsf{NP}\neq \mathsf{EXP}$?

Does $\mathrm{CIRCUITSAT}$ in any of $\mathsf{DTIME}(\frac{2^{n}}{n^c})$, $\mathsf{DTIME}({2^{\sqrt n}})$ or $\mathsf{DTIME}({2^{(\log n)^2}})$ $\implies \mathsf{NP}\neq \mathsf{EXP}$?

# Answer
$\mathsf{CircuitSat\in DTIME(2^n)}$ does not imply $\mathsf{NP\subseteq DTIME(2^n)}$ since the reduction might increase the input's size. Suppose for example that $L\in NP$ and the reduction from $L$ to $\mathsf{CircuitSat}$ maps strings of length $n$ to strings of length $n^c$ (for all $n\in\mathbb{N}$), then applying the reduction and using a naive exponential time algorithm for circuit sat yields a $2^{n^c}$ time algorithm for $L$.

If however you can place an NP-complete problem in a subexponential time class, e.g. $n^{\log n}$, then $NP\neq EXP$, since $n^{O(\log n)}$ is closed under polynomial transformations, i.e. $n\mapsto n^c$.
> 5 votes

---
Tags: complexity-theory, np, complexity-classes
---


# Question
Title: I can construct DFA for $a^{3n+1}$ but pumping lemma says it is not regular
Recently I stumbled across this language $L=\\{a^{n}a^{{(n + 1)}^2-n^2} \in \Sigma^\* \mid n\geq 0\\}$ that I can rewrite as $a^{3n + 1}$.

So I applied the pumping lemma to see if it is non regular, and I get:

* given a pumping length **p** I should have a string $z\in L$ such that $\mid z \mid \ge p$
* I choose $z=a^pa^pa^pa$ such that $z\in L$ and $\mid z \mid = (3p + 1)\ge p$
* now I can slipt the string in 3 parts, $z=uvw$ with $u=a^{p-1}, v=a,w=a^{2p}a$ and it satisfies the two following conditions of the lemma $\mid uv \mid \leq p$ and $\mid v \mid \> 0$
* then given $z = uv^iw$, if I pump $v$ I see that $z \notin L$ because if for example I choose $i=2$ than $\mid z \mid = (p-1)+i+2p+1=3p+2 \geq 3p+1$

So $z \notin L$ and it means that $L$ is not regular, but I noticed that I can construct a DFA that accepts this language:

So now I'm really confused. Probably I'm applying the pumping lemma in the wrong way but I don't understand where.

## UPDATE

Now, thanks to all of you, I think I understood my mistake. So to prove that a language is not regular I have to show that every decomposition fails to satisfy the pumping condition for some pumping number $i$. But in this case there is a decomposition that satisfies the pumping condition so I can't prove that the language is regular (but we know it is regular because we can construct a DFA that accepts it).

# Answer
> 0 votes
You should notice that if the conditions hold, the language can be regular (necessary, but not sufficient). However, you proved the third condition is not held in your case, hence it is not regular which this is not true. Therefore, your proof is not correct.

On the other hand, if we suppose $x = a$ and $y = a^{3}$ and $z = 3n-4$ we can say $xy^nz$ is in $L$ for all $n\geq1$ ($p = 4$). Hence, we can't proof $L$ is not regular by pumping lemma.

---
Tags: finite-automata, pumping-lemma
---


title: Definition of an Upper Bound

text:
# Question
Title: Definition of an Upper Bound
The definition my professor gave us is: f(n) is O(g(n) for constant c \> 0 and n0 ≥ 0 where all n ≥ n0 and f(n) ≤ cg(n). I was wondering what n0 and n are?

Example:
for the function f(n) = an2\+ bn + cn = (a+b+c)n2.
Assuming a,b,c were constants we can say: f(n) = O(n2) where f(n) ≤ cn2.

What am I actually looking and to make sure that n0 ≥ 0 where all n ≥ n0

# Answer
Let me write the definition in a little bit more detail.

> Suppose that $f(n),g(n)$ are two functions from $\mathbb{N}$ to $\mathbb{R}\_+$, that is, they accept as input a natural number, and return as output a positive real number.
>
> We say that $f(n) = O(g(n))$ if there exist $n\_0 \in \mathbb{N}$ and $C \in \mathbb{R}\_+$ such that for all $n \geq n\_0$,
>
> $$ f(n) \leq Cg(n). $$

In order to show that $f(n) = O(g(n))$, you have to find $n\_0$ and $C$ such that for all $n \geq n\_0$ it holds that $f(n) \leq Cg(n)$. You can choose whatever $n\_0,C$ you want as long as the condition holds. It turns out that for this definition, we can always take $n\_0 = 1$ (for other variants of the definition, this no longer holds). So you only have to find a positive constant $C \> 0$ such that for all $n \geq 1$ it holds that $$ f(n) \leq Cg(n). $$ (This assumes that the first natural number is 1 rather than 0.)

Now we can answer your question:

* $n$ is the argument of the functions $f,g$.
* $n\_0$ is the point beyond which the inequality $f(n) \leq C g(n)$ should hold. When proving that $f(n) = O(g(n))$, you get to choose $n\_0$. In most cases you can just take $n\_0 = 1$.

---

For the curious: why do we need $n\_0$? Sometimes we would like to accommodate functions which are not strictly positive, but just eventually positive. For example, if 0 is a natural number (in contrast to the convention used above) then $n^2$ is not strictly positive, since it vanishes at $n = 0$. Therefore $n = O(n^2)$ is only true if we allow to "skip" $n = 0$, which we do by choosing $n\_0 = 1$.
> 2 votes

---
Tags: time-complexity, asymptotics, runtime-analysis, upper-bound
---


# Question
Title: Different topologically sorted order based on DFS vertex ordering
The algorithm for topological sort, in CLRS goes as follows :

1. call DFS(G) to compute finishing times *v.f* for each vertex *v*
2. as each vertex is finished, insert it onto the front of a linked list
3. return the linked list of vertices

Let's we have a directed graph, as in the figure here:

If we start DFS from arbitrary vertices, we get different topological orders -- for instance, if the top level DFS loop goes through vertex `b` first, then `d`, then `i` and finally `a`, one possible ordering of finishing times (largest to smallest) is :

`(a), (i), (d,h,l,k,j), (b,c,f,e,g)`

where each grouped term within the parenthesis indicates one iteration of DFS from the starting vertex.

If the vertices are taken in a different order, say `a` first, then `d`, and then `i`, the order of finishing times becomes:

`(i), (d,h,l,k,j), (a,b,c,f,e,g)`.

If these were to indicate valid orders of events, how can they *both* be valid topological orders? The sorting algorithm does not mention any specific order of vertices to use in DFS.

# Answer
A topological ordering of a DAG $G$ is any ordering $v\_1,\ldots,v\_n$ of the vertices in which $(v\_i,v\_j) \in G$ implies $v\_i \leq v\_j$. That is, if there is an edge from $x$ to $y$, then $x$ must precede $y$ in the ordering (assuming $x \neq y$). A DAG can have many topological orderings. For example, the empty DAG on $n$ vertices has $n!$ topological orderings. In contrast, a path $v\_1 \to v\_2 \to \cdots \to v\_n$ has a unique topological ordering.
> 2 votes

---
Tags: algorithms, graph-traversal
---


# Question
Title: mapping reduction from $A_i=\{x|i \in W_x\}$ to $A_j=\{x|j \in W_x\}$
If $$ A\_n = \\{ x | n \in W\_x\\} \ where \ W\_x \ is \ domain \ of \ M\_x $$ how can I show that $$ \forall i,j \ \ \ A\_i \le\_M A\_j $$

# Answer
The language $A\_i$ consists of all Turing machines which halt on input "$i$".

Suppose I have an oracle which, given a Turing machine, can tell me whether it halts on the input $j$. Using this oracle, I want to decide, given a Turing machine, whether it halts on the input $i$. Can you think of a way of doing this?
> 1 votes

---
Tags: turing-machines, computability, reductions
---


title: Strassen Algorithm for Unusal Matrices

text:
# Question
Title: Strassen Algorithm for Unusal Matrices
The Strassen algorithm is developed for multiplying the matrices faster. It enables us to reduce O(n^3) time complexity to O(n^2.81).

However, this algorithm is applied for the matrices which are square and the dimension of the matrices must be a power of 2.

Assume that the matrices are called A and B.

`Problem 1:` A = 3x3 B = 3x3

`Problem 2:` A = 2x3 B = 3x1

How can we apply Strassen algorithm to multiplication of these matrices ? The only thing which comes to mind is enlarging the matrices to convert them into square non matrices by adding zeros, which is called padding operation. However, I am not sure whether this method is proper or not.

Is there another method ?

Is my notion correct ?

# Answer
Strassen's algorithm, when applied directly, only multiplies two square matrices of dimension $2^n$. You can use it to multiply two $m \times m$ matrices by finding the smallest power of 2 such that $m \leq 2^n$, padding your matrices to $2^n \times 2^n$, and using Strassen's algorithm. This results in an $O(m^{\log\_2 7})$ algorithm.

When multiplying rectangular matrices using Strassen's algorithm, padding still works but the exponent might change. However, there are other algorithms which are more suitable for multiplying rectangular matrices. In particular, it is known that there is a constant $\alpha \> 0$ such that multiplying an $n \times n^\alpha$ matrix by an $n^\alpha \times n$ matrix uses only $\tilde{O}(n^2)$ operations. These algorithms are probably impractical.

Finally, if you multiply small matrices as in your example, you shouldn't be using any fancy matrix multiplication method. Just use the usual algorithm. Strassen's algorithm is only worth it for very large matrices (if at all).
> 3 votes

# Answer
Almost the same as Yuval's answer, except...

If I gave you two 1025 x 1025 matrices, you wouldn't extend them to 2048 x 2048. You'd extend them to 1026 x 1026, and use one layer of Strassen's algorithm with 513 x 513 matrices - if you decided that this is faster than direct calculation of a 1025 x 1025 product. One recursion level lower, you'd decide whether your seven 513 x 513 products are faster to calculate directly or as a 514 x 514 product using one layer of Strassen's algorithm and so on.

I very much doubt that Strassen's algorithm will be an improvement for 65 x 65 products. There are fewer floating-point operations, but probably a lot more overhead.

For non-square matrices: If you want to multiply a (100x100) by a (1000x100) matrix, that can be done trivially by calculating ten (100x100) x (100x100) products. Filling up to 1000x1000 would be madness.
> 3 votes

---
Tags: matrices, divide-and-conquer
---


title: Comparing nodes in A*

text:
# Question
Title: Comparing nodes in A*
Nodes in the open list in A\* will be sorted by their f-cost, but if the f-cost of two nodes are equal, will their h-costs instead be compared? I'm asking because I've seen implementations where the h-costs are compared and where they aren't, so which version is the right one? What is the benefit of doing either?

g-cost: Cost from start to node

h-cost: Heuristic from node to end

f-cost: g-cost + h-cost

**Edit:** From Hart, P. E.; Nilsson, N. J.; Raphael, B. (1968). "A Formal Basis for the Heuristic Determination of Minimum Cost Paths"

"Select the open node n whose value of f is smallest. Resolve ties arbitrarily, but always in favor of any node n ∈ T."

It is stated that "T" is the goal set (I thought there was only one goal node?)

My interpretation is that if the goal node is in the open set, then it should be picked first, meaning resolving ties via h-cost is certainly a correct way because h(end) = 0.

# Answer
It's not problematic to have more than one goal node in A\* if you just want to reach any goal node. You simply keep running the search until you have expanded the first goal node.

Provided that your $h(x)$ function is consistent (or just admissible if your graph is a tree) the way of breaking ties does not affect the optimality of the search. As A\* always expands all nodes with $f(x) \lt C^\*$ where $C^\*$ is the true cost of the optimal solution, and never expands nodes with $f(x) \gt C^\*$, the number of nodes that gets expanded will end up being the same (or almost the same, as we will see).

Consider this case: We have two nodes $a$ and $b$, who are both on the open list, and we have that $f(a) = f(b)$ and $h(a) \lt h(b)$. We choose to expand $a$ because of the lower $h$-value and discover that a goal node $g$ is a neighbor to $a$. As $h(x)$ is at least admissible the actual distance between $a$ and $g$ can not be shorter than $h(a)$ and therefore $f(g) \geq f(a)$. There are now two cases:

\- If $f(g) \gt f(a)$, then we also have that $f(g) \gt f(b)$ and we therefore need to expand $b$ before we can conclude that we have found the fastest way to $g$.

\- If $f(g) = f(a)$, then we also have $f(g) = f(b)$, but this only happens if the distance between $a$ and $g$ is $0$ and in that case $h(a)$ must also be $0$. We now have both $b$ and $g$ on the open list and their $f$-value is the same and so we expand $g$ as it is a goal node. In this case we do not need to expand $b$.

Had we expanded $b$ first, the exact same thing would have happened and we would have had to expand $a$ as well unless $h(b)$ was $0$. In other words, taking the lowest $h$-value first has no influence on the number of nodes expanded unless it is the case that $h(x) = 0$, in which case it does make sense to expand this node first. Note however, that only if the actual distance from $x$ to the goal is also $0$ (it could be more that $h(x)$) do we actually save a node from being expanded. So while A\* always expands all nodes with $f(x) \lt C^\*$ and never expands nodes with $f(x) \gt C^\*$, the nodes with $f(x) = C^\*$ could be expanded or not expanded depending on your tie-braking and the structure of the graph.
> 1 votes

---
Tags: shortest-path
---


# Question
Title: How many queries does it take to find the best flight?
I often find flights through a search engine like Google Flights. On input some refined subset of the space of all flights (e.g., non-stop only, departing in the morning, from one of two airports, and on a certain date) the search engine returns the cheapest flight in this subset. My goal using the search engine, however, is not so simple as restricting to a subset and finding the cheapest flight. Rather, I mentally place a certain dollar value on how much I am willing to pay extra for various options: e.g., willing to pay \\$20 extra for nonstop, willing to pay \\$50 extra for closer airport. I want to find the cheapest flight after these dollar values are taken into account.

This raises an algorithmic question: how many queries to the search engine does it take to find the best flight? We can formulate this as the following search problem:

* $X$ is a search space (set of flights);
* $f: X \to \mathbb{R}^+$ is an unknown price function, where $f(x)$ is the price of $x$;
* $g: X \to \mathbb{R}^+$ is a known additional cost to us, which we assume is a weighted sum of $k$ known indicator functions: $$ g(x) = \alpha\_1 \[x \in A\_1\] \+ \alpha\_2 \[x \in A\_2\] + \cdots + \alpha\_k \[x \in A\_k\], $$ where $\alpha\_i \ge 0$ are weights and $\[x \in A\] = \begin{cases} 1 &\text{if } x \in A \\ 0 &\text{otherwise} \end{cases}$ is the Iverson bracket.

**The problem:** Determine $\min\_{x \in X} (f(x) + g(x))$, using queries to an oracle which, on input any subset $X' \subseteq X$, returns $\min\_{x \in X'} f(x)$ and $\arg\min\_{x \in X'} f(x)$.

**Question 1:** As a function of $k$, how many queries to the oracle are needed in the worst case?

It can easily be done in $2^k$ queries: the sets $A\_1, A\_2, \ldots, A\_k$ collectively partition $X$ into $2^k$ regions, so we can query on each subset. Is there a better algorithm in general?

**Question 2:** Assume that the actual minimum of $f(x) + g(x)$ falls into at most $k' \ll k$ of the indicator sets $A\_i$ (so I'm not going to pay *too* much extra). As a function of $k$ and $k'$, how many queries to the oracle are now needed?

# Answer
There are problem parameters where you need $2^k$ queries in the worst case. I'll prove this by giving an explicit example of an instance where you need $2^k$ queries.

Suppose $X = \\{0,1\\}^k$ and $A\_i = \\{x \in X : x\_i = 1\\}$ (this is without loss of generality in any case). Suppose $\alpha\_i = 1/2^i$. Pick a single value $x^\* \in X$, and define

$$f(x) = 1 - g(x) - 2^{-k-1} \[x = x^\*\].$$

To any query set $X'$ we can associate a single element $m(X') = \arg \max\_{x \in X'} g(x)$. Notice that the results of the query $X'$ depends only on $m(X')$, and there are $2^k$ possible values for $m(X')$. Thus we can identify each query with the value of $m(X')$, so effectively there are only $2^k$ different queries (where I consider two queries different if their value of $m(\cdot)$ differs; formally, consider the equivalence relation induced by $m(\cdot)$, choose one canonical representative for each equivalence class, and from here on we will assume that each query is one of these $2^k$ canonical representatives). Now I claim that out of these $2^k$ possible queries, there is only a single one that gives you any useful information about $x^\*$. In particular, the only thing you learn about $x^\*$, when you query on the set $X'$, is whether $x^\* = m(X')$ or not. Why? If $x^\* = m(X')$, then the oracle will return $x^\*$, and you can recognize that this has happened by looking at the value of $f$. However, if $x^\* \ne m(X')$, then the oracle will return $m(X')$ as well as the value of $f$ on that element, and that is something you could have computed on your own using your knowledge of $g$, so you have learned nothing about $x^\*$ other than that it is different from $m(X')$. Moreover, there is only a single (canonical) set $X'$ where $x^\* = m(X')$.

So, you have a search space of size $2^k$, and each query only lets you test a single candidate for $x^\*$. It's like playing a game where I think of a secret number, and you can ask me questions like "is your number 17?" where you replace 17 with any number of your choice. It's easy to see that this game will require $2^k$ guesses in the worst case, and $2^{k-1}$ guesses on average.

So for that setting of weights, you can't do any better than $2^k$ queries.

(As a generalization, for your Question 2, this will require ${k \choose k'}$ queries in the worst case.)

---

In contrast, there also exist choices of weights where this allows an efficient solution. Consider the case where $\alpha\_1=\cdots=\alpha\_k=1$. Then you can query on the subsets $X'\_0 = \\{x \in X : g(x) = 0\\}$, $X'\_1 = \\{x \in X : g(x)=1\\}$, .., $X'\_k= \\{x \in X : g(x)=k\\}$. Then, take the best of those results -- the one that has the smallest value of $f(x)+g(x)$. After doing $k+1$ queries, this is guaranteed to find you the optimal solution to the problem. As a generalization, if the set of sums $\\{\sum\_i c\_i \alpha\_i : c \in \\{0,1\\}^k\\}$ has cardinality Q, then Q queries suffice to obtain the exact answer.

---

So, ultimately, the number of queries needed to the oracle depends on the weights. There are some choices where this might require many queries, and other choices where very few queries suffice.

One nice thing is that you can approximate the optimal value to within an additive error of $\delta$ using $(\sum\_i \alpha\_i)/\delta$ queries. In particular, query the subset $X' = \\{x \in X : g(x) \le t\\}$ for $t:=\delta,2\delta,3\delta,\dots,\sum\_i \alpha\_i$. Take the best solution found over all of those queries, and that will be at most $\delta$ worse than the optimum.
> 3 votes

---
Tags: algorithms, optimization, search-algorithms
---


# Question
Title: The total time require for a pipeline to execute
The book says that a total time required for a pipeline with k stages to execute n instructions is as follows.

$T \_{k,n} =\[pqnk+(1-pq)(k+n-1)\] \tau$

p is the probability of encountering a branch instruction.

q is the probability that execution of a branch instruction I causes a jump to a nonconsecutive address.

(Each jump requires the pipeline to be cleared)

However, I can not understand why this makes sense. The formula indicates that

> "If there is a branch instruction and is taken, the number of stages is nk. And in the remaining cases, it is (1-pq)(k+n-1)

I can understand the second case, but why is the number of stages nk in the first case? I think that the result of nk stages never occurs unless every instruction is a branch instruction so that the pipeline is cleared every time each instruction is executed. Instructions after a branch instruction which is taken can be executed in the pipeline, so it must be less than nk. What do I miss?

# Answer
The exact time could be obtained as $\tau\sum p\_i\\,c\_i$ where $p\_i$ is the probability of taking $c\_i$ cycles. Let's admit that by virtue of linearity, it ends up to be equivalent to $\tau\sum p\_i\\,C\_i$ with two terms, $p\_0=pq$, thus $p\_1=(1-pq)$. The two terms $C\_0$ and $C\_1$ must make the formula correct for the extreme cases $pq=1$ and $pq=0$.

The $C\_0=nk$ term (the question's first case) is the number of cycles it would take to execute the $n$ instructions with each requiring $k$ cycles (because each jumps to a non-consecutive location and requires refilling the $k$ stages).

The $C\_1=k+n−1$ term is the number of cycles it would take for linear code (either because there is no branch instruction, or none jumps to a non-consecutive address). The $n$ term is such that each additional instruction adds one cycle, and the other terms are such that for $n=1$, the outcome is the $k$ cycles necessary to fill the $k$ stages of pipeline.
> 1 votes

---
Tags: cpu-pipelines
---


# Question
Title: Understanding the Reasoning Behind These Typing Rules
So the expression $\Gamma \ \vdash \ e:\sigma$ states that under assumptions $\Gamma$, the expression $e$ has type $\sigma$. Then we have the following rules:

\begin{array}{cl}\displaystyle {\frac {x:\sigma \in \Gamma }{\Gamma \vdash \_{D}x:\sigma }}&\[{\mathtt {Var}}\]\\\\\displaystyle {\frac {\Gamma \vdash \_{D}e\_{0}:\tau \rightarrow \tau '\quad \quad \Gamma \vdash \_{D}e\_{1}:\tau }{\Gamma \vdash \_{D}e\_{0}\ e\_{1}:\tau '}}&\[{\mathtt {App}}\]\\\\\displaystyle {\frac {\Gamma \vdash \_{D}e\_{0}:\sigma \quad \quad \Gamma ,\\,x:\sigma \vdash \_{D}e\_{1}:\tau }{\Gamma \vdash \_{D}{\mathtt {let}}\ x=e\_{0}\ {\mathtt {in}}\ e\_{1}:\tau }}&\[{\mathtt {Let}}\]\end{array}

where

* $\mathtt {Var}$ is variable access.
* $\mathtt {App}$ is function call with one parameter (function application).
* $\mathtt {Let}$ is variable declaration.

I would like to understand how these rules work. This is my understanding so far...

**\[$\mathtt {Var}$\]** "if $x$ is of type $\sigma$ from environment $\Gamma$, then under the assumption of $\Gamma$, $x$ is of type $\sigma$." Two things are confusing me so far. First is the $D$ in $\vdash\_D$. The second is that the premise and conclusion seem to say the same things: "if x is of type y, then x is of type y". Wondering what this is actually saying so that I can see why it's necessary.

**\[$\mathtt {App}$\]** "if under the assumption of $\Gamma$, $e\_0$ is of type $\tau \to \tau'$ $\land$ under the assumption of $\Gamma$, $e\_1$ is of type $\tau$, then under the assumption of $\Gamma$, $e\_0\ e\_1$ is of type $\tau$." So that last part is introducing some new syntax $e\_0\ e\_1$, which means function application. So that makes sense. What I get confused about is the "if, then" part in this definition. Wondering if it is saying, "if the function and the parameter are present, then we *can* do function application", or "if the function and parameter are present, then function application occurs." I keep on interpreting it as the latter for some reason.

**\[$\mathtt {Let}$\]** "if under the assumption of $\Gamma$, $e\_0$ is of type $\sigma$, and under the assumption of $\Gamma$ and $x$ of type $\sigma$, $e\_1$ is of type $\tau$, then under the assumption of $\Gamma$ **we can do** $\mathtt {let}\ x=e\_{0}\ {\mathtt {in}}\ e\_{1}$ of type $\tau$." That "we can do" part is my understanding that this is saying, because of these premises, we can declare a variable. Also I'm not sure about the $\Gamma ,\\,x:\sigma\vdash \_{D}$, wondering if that is just saying that $x:\sigma$ is in the environment $\Gamma$, or if it's a separate thing. So basically it is just highlighting the fact that we are in the environment *and* we have this particular type of interest in the environment.

So to summarize, the questions are:

1. The meaning of $D$ in $\vdash\_D$.
2. In $\mathtt {Var}$, wondering what the definition is actually saying and why it is necessary.
3. If my understanding of $\mathtt {App}$ and $\mathtt {Let}$ are correct.

# Answer
> 6 votes
For question 1, I don't think that the $D$ carries any particular meaning, it is just part of the notation, and might refer to the name given to the corresponding calculus.

For 2, what you need to understand is that $\Gamma$ really is a set of assumptions. So if $\Gamma = x\_1 : \sigma\_1, \dots, x\_n : \sigma\_n$ then $\Gamma$ is a *typing context* that tells us that we will assume that $x\_1$ has type $\sigma\_1$, that $x\_2$ has type $\sigma\_2$ and so on.

Now, what might be confusing to you is that there are several different levels of implications in the syntax of typing rules.

* First, the typing rules themselves are implications of the form "if the premises hold, then the conclusion hold" (the premises being the hypotheses given above the line, and the conclusion being the *typing judgment* below the line.
* Second, a typing judgments $\Gamma \vdash e : \sigma$ is also a form of implication, meaning "if the assumptions on the types of variables given in $\Gamma$ are correct, then $e$ has type $\sigma$".
* And finally, there is also the arrow type $\sigma\_1 \to \sigma\_2$, which is also a form of implication.

So in the end, what the \[Var\] rule says, is that we may assume that $x$ has type $\sigma$, provided that this is part of our assumptions. Or in other words, it is always true that $x$ has type $\sigma$ under the assumption that $x$ has type $\sigma$. Or, reformulating again: when you made an assumption, you have the right to use it.

For 3, the main thing that you need to understand is that typing rules are implications (as explained above). For example, \[App\] says that if we can show that $e\_1$ has an arrow type and that $e\_2$ has the same type as the domain of the arrow (i.e., $e\_1$ and $e\_2$ have compatible types), then we can perform an application.

# Answer
> 3 votes
In addition to the other answer:

> In *Var*, wondering what the definition is actually saying and why it is necessary.

Indeed, the rule might seem trivial, but the point is that by introducing typing judgements we build another layer on top of our syntax, namely a set of assertions that some terms have some types: $\Gamma \vdash e : \tau$.
Therefore, it is natural to have one typing rule for every term in the inductive definition of terms (e.g. $s, t ::== x | \lambda x. s | s t$ for the simply typed Lambda calculus).

Note that terms may have multiple types. Let $\Gamma = \\{x: \text{Int}\\}$ and $t = x$, then $\Gamma \vdash t: \text{Int}$, $\Gamma \vdash t: \forall \alpha. \text{Int}$ and $\Gamma \vdash t: \forall \alpha, \beta. \text{Int}$ are all equally valid assertions which are inferable.

Hence, you can interpret $\Gamma \vdash t: \sigma$ more like: there is an inference of that type for $t$ or we can deal with $t$ as if it was of type $\sigma$. Especially, you can apply different inferences in different places.

**Example:** Let $$ \Gamma = \\{42: \text{Int}, \text{false}: \text{bool}, \text{toStr}: \forall \alpha. \alpha \rightarrow \text{String}, \text{concat}: \text{String} \rightarrow \text{String} \rightarrow \text{String}\\}, $$

then $\Gamma \vdash \text{concat } (\text{toStr } 42)\ (\text{toStr } \text{false}) : \text{String}$ is inferable. On the first occurrence of $\text{toStr}$, its type is inferred as $\text{Int} \to \text{String}$, but upon the second occurrence, it is inferred as $\text{bool} \to \text{String}$.

---
Tags: type-theory, notation
---


title: Recursive relations in binary trees

text:
# Question
Title: Recursive relations in binary trees
I have an exercise in my algorithm's Course for which I have the correction but do not understand it.

**1.Exercise** .

Let Th be a full binary three of height h(meaning all the levels all completely full).

(1.a) : Let f(h) be the number of leaves of Th(nodes of the last level). Establish a relation for f(h) and solve it recursively. Give the exact expression for f(h) in terms of h, and the asymptote expression (in Big-O notation)

**Correction**

f(h)=2\*f(h-1) for h \>= 1 and f(0) =1.
f(h)=2\*f(h-1)=4\*f(h-2)=8\*f(h-3)=...=2^h*f(h-h)=2^h*f(0) =2^h.
*Complexity :* O(2^h)

I simply do not understand why h-1. Because suppose we have a full binary tree with h=2 . If h=2, then number of leaves = 4 . Applying the correction resolution:
f(2) = 2\*f(2-1) = 2\*f(1) = 2, which is different from the number of leaves, which is 4.

# Answer
> 0 votes
In a binary full tree, if in the level **i** there is **n** nodes then in the level **i+1** there is **2n** nodes, because each node produce 2 child.

So if you think about the nodes at every level, if you have **k** nodes in the h level, then **k = 2\*k'** where k' is the number of nodes in level h-1, correct?

then you can write a recursion like the recursion in correction.

Regarding your example, there is a small mistake:

if we have a full binary tree with h = 2 then the recursion calculate the correct value because: `f(2) = 2*f(1) = 2*2 = 4` because f(1) = 2\*f(0) and f(0)=1 for base case.

# Answer
> 1 votes
I think you're just confused about the definition of "height". You write that you expect $f(2)=4$, where $f(h)$ is the number of leaves when the height is $h$. A full binary tree with four leaves looks like this:

```
     o
   /   \
  o     o
 / \   / \
o   o o   o

```

So, in this case, you're taking the height to be the number of edges between the root and a leaf, and a tree of height $h$ has $h+1$ levels of nodes.

But you also write $f(2) = 2f(2-1) = 2f(1) = 2$, implying that $f(1)=1$. A full binary tree with only one leaf looks like this:

```
     o

```

However, that tree has one level of nodes, so it has height zero. The height $1$ tree is

```
     o
    / \
   o   o

```

so we see that $f(2) = 2f(2-1) = 2\times 2 = 4$, as expected. Perhaps you were thinking of the following tree, which has one leaf and height $1$, but isn't a full binary tree.

```
     o
     |
     o

```

---
Tags: binary-trees, recursion
---


title: Finite state automata: final states

text:
# Question
Title: Finite state automata: final states
In our programming language concepts course, our instructor claimed that it's okay for a final state to lead to another state in a finite state diagram.

But this seems to be a fundamentally contradictory concept. Because a final state by definition is one that terminates transitions, i.e., that once you reach it, there's nothing else left to do.

And yet he presented a slide such as this one, where final states are represented by two circles... How is it possible for B, D, E, and H to be final states when they're so clearly not?

# Answer
You seem to have a misunderstanding of generative models v.s. "recognizing" models.

The grammar you have on the right *generates* words by applying rules, starting from the initial variable, and stopping after there are no more variables.

Automata, however, *recognize* a language as follows: you feed the automaton a word, letter by letter, and the automaton takes transitions based on the letters given to it.

If, after reading all the letters, the automaton ends up in an accepting (a.k.a final) state, then we say that the automaton accepts the word.

So it's better to think of those as "accepting" states, rather than "final" states, although both terms are commonly used.
> 17 votes

# Answer
Indeed, it is confusing! To solve your problem, call them "accepting" states instead of "final" states. Because that is what they really are, just a marker that tells us that at this moment the string processed belongs to the language.
> 7 votes

# Answer
> a final state by definition is one that terminates transitions, i.e., that once you reach it, there's nothing else left to do.

The source of your confusion is that this *isn't* the definition. "Final state" is a poor choice of name, and most authors seem to prefer "accepting state". The definition is that the automaton accepts if its run ends in a final/accepting state and rejects otherwise.
> 7 votes

# Answer
"a final state by definition is one that terminates transitions, i.e., that once you reach it, there's nothing else left to do."

In the traditional convention of working with acceptors (that is, finite state automata which tell you whether a given string belongs/doesn't belong to a language), a final state is one that, when reached with an empty string (the input was consumed entirely) signifies that the initial string is accepted, i.e. it is part of the automaton's language.
> 3 votes

# Answer
As you can see. The grammar given says A -\> a. Therefore the automatom accepts to terminate on the string "a". But it also allows A -\> aB -\> abD -\> abc, so the string "abc" is also accepted. If we finish the string at this point, we will be standing in a final state and so the string was accepted. But we might still want the string "ab" to be accepted. So we need to make sure that {"a", "ab", "abc"} are all accepted by the automaton. Do no the see final states as a state such that if we enter it we may never leave it, see it as a state to tell us if our current string is accepted or not.
> 3 votes

---
Tags: formal-languages, graphs, regular-languages, finite-automata
---


# Question
Title: Why we write "Ignore the input " when describing an Enumerator?(Sipser Chapter 3)
The Theorem and its proof is given below:

>

But I am wondering why we write "Ignore the input " when describing an Enumerator? could anyone explain this for me please?

# Answer
> 2 votes
It's just an explicit statement that the behaviour of the machine doesn't depend on its input in any way. This could be inferred from the rest of the machine's description, but explicitly saying it makes it clear that it's not a mistake.

---
Tags: complexity-theory, turing-machines, computability
---


# Question
Title: A necessary [and sufficient?] condition for the number of comparisons required to sort $n$ elements
I am familiar with the decision tree based argument for the minimal number of comparisons required to sort $n$ distinct elements - Since there are $n!$ permutations on the $n$ elements, the decision tree for any comparison based sorting algorithms must have at least $n!$ leaves, and therefore at least one path of length $\left\lceil \log\_{2}\left(n!\right)\right\rceil $, corresponding to the worst case performance of said algorithm.

**Question:** The condition $$\left\lceil \log\_{2}\left(n!\right)\right\rceil \leq\\#\text{ of comparisons in the worst case}$$

is a necessary condition for any comparison based sorting algorithm. Is it also sufficient? e.g. if I am asked if it is possible to sort 5 elements in 7 comparisons, does it suffice to observe that $\log\_{2}\left(5!\right)\<7$ to deduce that such an algorithm must exist?

# Answer
Following the conventions of Peczarski, Towards Optimal Sorting of 16 Elements, let us denote by $S(n)$ the optimal number of comparisons needed, and by $C(n)$ the information-theoretic lower bound $\lceil \log\_2 n! \rceil$. It is known that $S(n) = C(n)$ for all $n \leq 11$, but $S(n) = C(n)+1$ for $12 \leq n \leq 15$. See Peczarski's paper for references. See also A036604.
> 4 votes

---
Tags: time-complexity, sorting, information-theory
---


# Question
Title: Algorithm for nearest edge detection with respect to a point (in all directions)
I'm looking for an algorithm, a set of algorithms, or any pointers/remarks how to solve the following problem:

Given a polygon, a central point, and a set of points scaterred around the central point inside the polygon, I want to find the nearest "edges" being created by those points with respect to the central point. One of the algorithm's parameters should be "distance sensitivity" (meaning how far two points have to be far from eachother to be considered in a different cluster and break the line).

An illustration will maybe explain it better... this could be the input, where the + denotes the central point:

The output would be the following:

I am not very well-versed in computational geometry, so any pointers would be welcome.

I'd naively like to imagine the algorithm as a growing circle spreading outwards from the central point, parts of it getting stuck on the points (larger parts get stuck if the cluster is dense enough), and tearing off at the ends of the cluster because there are no points to support it there.

I have done some research into line-sweep algorithms, which partly fit my criteria. However, what I think I need is some kind of a circle-sweep algorithm.

# Answer
> 2 votes
I would suggest you use a sweep line algorithm, sweeping a line that emanates from the origin and rotating around it. Think of a lighthouse placed at the origin, with a beam of light that rotates around in a circle, and find the closest point illuminated by that beam of light.

In more detail: Convert the points to polar coordinates $(r,\theta)$ and sort them by increasing angle $\theta$. Let $S$ denote the set of resulting points. Then for each angle $\theta$ find the point closest to the origin out of all points whose angle is in the range $\[\theta-\epsilon,\theta+\epsilon\]$, and use this as the location of the perimeter at that angle. In particular, let $f(\theta) = \min \\{r : (r,\theta') \in S, |\theta-\theta'| \le \epsilon\\}$; then $f$ defines a curved line/path. You can apply some smoothing to it, and then use that as your red line. If there is no point with angle in the range $\[\theta-\epsilon,\theta+\epsilon\]$, then there is no red line there; you have a break in the line.

You could of course apply a standard clustering algorithm first, and then do this separately on each cluster, removing clusters that are "hidden" (further away than another cluster). From your image it looks like the clustering problem should be easy and you shouldn't have a difficult time finding a clustering algorithm that does a good job of separating the points into clusters. However, I'm not sure that's even necessary.

---
Tags: computational-geometry
---


# Question
Title: Rollback and Timestamp Ordering in Database
If we use the Timestamp Ordering for concurrency control in the following scheduling:

My TA says $T\_2,T\_3,T\_5$ is Run and $T\_4,T\_5$ is Rollback. I think it's false. Is there any expert who could help us?

# Answer
> 1 votes
Timestamp Ordering ensures **serializability** by serializing transactions in order of their timestamps.

The *transaction that starts earlier is assigned smaller timestamp than a transaction started later*. Assuming the given schedule shows each transaction's start. $T\_{5}$ will have smallest timestamp.

So to ensure serializability the given schedule must be **conflict serializable**. In other words it must be conflict equivalent to a serial schedule(*It is a schedule in which transactions are aligned in such a way that one transaction is executed first. When the first transaction completes its cycle, then the next transaction is executed*) whose first transaction is $T\_{5}$ because of smallest timestamp.

Because $Write(y)$ of $T\_{5}$ **conflicts** with $Write(y)$ of $T\_{3}$, $T\_{5}$ is rolled back. Now considering $T\_{1}$ , $T\_{2}$, $T\_{3}$ , $T\_{4}$, their execution is already serial with respect to each other , the order being $T\_{2}$ followed by $T\_{1}$, followed by $T\_{3}$, followed by $T\_{4}$.

Hence only transaction $T\_{5}$ is rolled back.

# Answer
> 0 votes
I know its a little too late, but here's my take:

> All the read and writes by t1,t2,t3,t4 are sucessfully run, since there are just 1 instructions until that point. And assuming the systems assigns the timestamp just before each transaction's first instruction.
>
> The last write(y) instruction by t5 is rejected, since the TS(T5) \< W-TStamp and R-TStamp. Hence its restarted with a new time stamp.

---
Tags: concurrency, database-theory, databases
---


# Question
Title: Decidability of determining whether a context-free grammar generates all strings in 1*
How could I prove that the following language is decidable?

$\\{\langle G\rangle \mid G\ \text{is a CFG over}\ \\{0,1\\}\ \text{and}\ 1^\* \subseteq L(G)\\}$

P.S. It's the problem 4.15 of the third edition of the "Introduction to the Theory of Computation" by Michael Sipser.

# Answer
> 2 votes
You can find the solutions to the exercises of that book here. For completeness of the answer, I rewrite the solution (with some more details) here.

Let $p$ be an upper bound of the pumping length of $G$, you only need to check whether $1^0, 1^1,\ldots,1^{p+p!} \in G$. If not, we can certainly reject $\langle G\rangle$. Otherwise, applying pumping lemma on $1^k$ ($p\le k\le p + p!$), we can conclude that there exist substrings $u,v,w,x,y$ such that

* $1^k=uvwxy$, which means $u,v,w,x,y$ contain only 1s,
* $|vwx|\le \text{pumping length} \le p$,
* $|vx|\ge1$ and
* $uv^nwx^ny\in G$, i.e. $1^{|uwy|+n|vx|}=1^{k+(n-1)|vx|}\in G$, for all $n\ge 0$, which means $1^{k+n(p!)}\in G$ for all $n\ge0$.

Note $\\{1^{k+n(p!)}\mid n\ge0, p\le k\le p + p!\\}$ covers all $1^m$ for large $m$, so $1^0, 1^1,\ldots,1^{p+p!} \in G$ indeed implies $1^\*\subseteq G$.

---
Tags: complexity-theory, computability, context-free, decision-problem
---


title: LTL globally implies

text:
# Question
Title: LTL globally implies
I have got confused in undressing the informal definition of LTL below: $$G(\phi \Longrightarrow\psi)\Longrightarrow(G\phi \Longrightarrow G\psi)$$

1. in many literatures I have seen implies is said as replies like for LHS we can say Always/Globally $\psi$ replies to $\phi$. is it correct?
2. Does the LHS implies the RHS if so what is the informal interpretation of the formula? (**Alway** $\psi$ replies to **Always** $\phi$) replies to (**Always** $\psi$ replies to $\phi$)

# Answer
> 2 votes
You seem to be pretty confused, so let's sort some things out. First, it's "implies", not "replies". That is, the formula $\phi\implies \psi$ means that if $\phi$ holds, then $\psi$ holds.

To be more precise, the formula $\phi\implies \psi$ is true in one of two cases: either $\phi$ is false, in which case we say that the implication is vacuously true, or if both $\phi$ and $\psi$ are true.

Now, in LTL, the operator $G$ means that something holds in every position in the computation. Let's examine the two "sides" of your formula with respect to that.

The formula $G(\phi\implies \psi)$ means that in every point of the computation, the formula $\phi\implies \psi$ is true, in the form mentioned above.

The formula $G\phi\implies G\psi$ means, as above, that either $G\phi$ is false, or both $G\phi$ and $G\psi$ is true.

Now it is fairly easy to see why the formula you have is true: if $G(\phi\implies \psi)$ is true, then, if $G\phi$ is true, then $\phi$ is true in every position, but then according to the LHS we have that $\psi$ is also true in every position, so $G\phi\implies G\psi$ is true.

For your second question, an informal way to think about this (there are many others, probably) is this: if you require that whenever $\phi$ holds, then $\psi$ must also hold, then in particular, if $\phi$ is always true, then $\psi$ is also always true.

---
Tags: linear-temporal-logic, temporal-logic, computation-tree-logic
---