# Question
Title: Shortest traverse path in a matrix given the start point $(i,j)$
Given a $m\times n$ matrix and a starting position $(i,j)$, how can we find the shortest path to go through all the elements at least once if we can only move by a single unit (i.e. up, right, left or down) at a time?

Currently all I could think of was moving to the nearest corner and then traversing from there, but that would not be the shortest path unless the start position is already a corner. And unfortunately I couldn't find anything similar to this problem.

# Answer
> 1 votes
If either $m=1$ or $n=1$, the starting position will determine how many elements will need to be revisited - head to the nearest end and the back to the other. The following cases consider $m,n\>1$.

If either $m$ or $n$ is even, there is a simple traverse starting from any element (and which will conclude on an adjacent element), without revisiting any element.

Consider a $2\times n$ matrix. Then there is a loop traverse that runs one way along one row and back along the other row:

Now for a $2k\times n$ matrix you can stack these loops and jump from loop to loop as required:

(there is no requirement to stagger the loop jumps - that is purely choice). The same idea applies if it is $n$ rather than $m$ that is even.

When $m$ and $n$ are both odd, you do not have a convenient loop path. If for your starting square, $i$ and $j$ are opposite parity - one odd, one even - you cannot avoid one revisit of a cell. A checkerboard colouring argument shows that easily. I believe that otherwise you can complete a path without a revisit, provided you avoiding leaving "dead end" elements until inevitable.

---
Tags: algorithms
---


# Question
Title: Given the following state diagram, write out its formal definition as a 5-tuple
I got these for four of them, but I can't get the transition function.

Q = {q1, q2, q3, q4}

Σ = {a,b}

q1 is the start state, and

F = {q4}

# Answer
The transition function can be represented as a two dimensional array. For your automaton, you just need to complete the following:

$\begin{array}{|c|c|c|} \hline & a & b\\ \hline q\_1& &\\ \hline q\_2& &\\ \hline q\_3& &\\ \hline q\_4& &\\ \hline \end{array}$

It can also be defined as a set of triplets $(q, a, \delta(q, a))$ (for example $(q\_1, a, q\_2)$ can be a triplet of the set).
> 2 votes

---
Tags: algorithms, algorithm-analysis
---


# Question
Title: Proving non-regularity of $\{a^p \mid p \in \text{Prime} \}$ without pumping lemma
I was wondering whether it is possible to prove $\\{a^p \mid p \in \text{Prime} \\}$ is a non-regular language without using the pumping lemma. I'm having trouble choosing an alphabet that completes the proof using Myhill-Nerode and figuring out other methods to use generally.

# Answer
Let $L=\\{a^p \mid p \in \text{Prime} \\}$.

Let $m,n\in\Bbb N$, $m\<n$. Let $s$ be the smallest prime number that is bigger than $(3n)! + 3n$.

* $a^na^{s-n}=a^s\in L$.
* $a^ma^{s-n}=a^{s-(n-m)}$. Note that $(3n)! + 2n \< s - (n-m) \< s $.

+ Any number between $(3n)! + 2n $ and $(3n)!+ 3n$ inclusive is not a prime number.
    + Any number between $(3n)!+3n$ and $s$ exclusive is not a prime number.

So $s-(n-m)$ is not prime, i.e., $a^ma^{s-n}\not\in L$.

The above shows that $a^m$ and $a^n$ represent different Myhill-Nerode equivalence classes. That means each word represents a distinct Myhill-Nerode equivalence class. Since there are infinitely many of them, $L$ cannot be regular.
> 2 votes

# Answer
Consider a DFA which has a unary input alphabet. Every state has exactly one successor state. Without restriction of generality, the trace of an input long enough will be $q\_0 q\_1 \dotsm q\_k q\_i$, where $q\_0, q\_1, \dotsc, q\_k$ are all distinct states and $i \in \\{ 0, \dotsc, k\\}$. Hence, $q\_i \dotsm q\_k q\_i$ is a cycle.

If the DFA's language is infinite, there must be an accepting state $q\_j$ with $j \in \\{ i, \dotsc, k \\}$. Note we may assume $j \> 1$ since otherwise we immediately obtain $\varepsilon$ or $a$ is in the DFA's language (and neither have prime length). But then $a^{j + m(k - i + 1)}$ is accepted for all $m \in \mathbb{N}\_0$. Since $j + j(k - i + 1) \> j$ is not prime, the DFA's language contains strings with composite length (unless it is finite).
> 1 votes

# Answer
Parikh's theorem (whose proof in this case is trivial) implies that if your language were regular, then the set of primes would be eventually periodic: there exist $n\_0 \geq 0$ and $m \geq 1$ such that for $n \geq n\_0$, $n$ is prime iff $n+m$ is prime. In particular, since the set of primes is infinite, it would have positive density. However, it is well-known that the set of primes has vanishing density (this follows from, but is much easier than, the prime number theorem).
> 1 votes

# Answer
Another weird way to prove it is using *busy beavers* and the *prime gaps theorem*:

* suppose that you have a $DFA$ $A$ that accepts the primes $\\{ a^p\mid p \text{ prime} \\}$
* given a state $q$ of $A$, you can build a Turing machine $M\_{\langle A,q \rangle}$ that sequentially simulates $A$ *starting from state $q$* on inputs $a^1, a^2, a^3, a^4,...$ until $A$ accepts some $a^k$ (or never halt)
* let $|M\_{\langle q,A \rangle}| = n$ be the size of such Turing machine, and $BB(n)$ the maximum number of steps achievable by a halting Turing machine of size $n$ (uncomputable)
* by the prime gaps theorem, there exists a prime $p\_i$ such that $p\_{i+1} - p\_i \gg BB(n)$
* $A$ accepts $a^{p\_{i+1}}$, so let $q\_i$ be the state of $A$ on input $a^{p\_{i+1}}$ after $p\_{i}$ steps (i.e. it has scanned the first part $a^{p\_i}...$ and the head is at the beginning of the remaining part of the input $...a^{p\_{i+1} - p\_{i}}$)
* so there exists $M\_{\langle A,q\_i\rangle}$ of size $n$ that by construction will run for a number of steps greater than $p\_{i+1} - p\_i \gg BB(n)$ and halt, contradicting the hypothesis that $BB(n)$ is the maximum number of steps achievable by a halting TM of size $n$
> 1 votes

# Answer
This is probably a better and clearer solution using the Myhill-Nerode Theorem. As there are infinite prime numbers, so for the sake of contradiction, let us assume that the language has finite classes. Thus there exist at least two primes $p\_1$ and $p\_2$ (wlog $p\_2 \> p\_1$) such that $$\[a^{p\_1}\]\_{\equiv\_L} = \[a^{p\_2}\]\_{\equiv\_L}$$ Now, using the right congruence rule on these classes and appending the words with $a^{p\_2 - p\_1}$, we get $$\[a^{p\_2}\]\_{\equiv\_L} = \[a^{2p\_2 - p\_1}\]\_{\equiv\_L}$$ which implies$$\[a^{p\_1}\]\_{\equiv\_L} = \[a^{2p\_2 - p\_1}\]\_{\equiv\_L}$$ Continuing this for $p\_1 - 2$ times more we get that $$\[a^{p\_1}\]\_{\equiv\_L} = \[a^{p\_1p\_2 - (p\_1 - 1)p\_1}\]\_{\equiv\_L}$$ Clearly, $p\_1p\_2 - (p\_1-1)p\_1 = p\_1(p\_2-p\_1+1)$ is not a prime number, whereas $p\_1$ is a prime. Hence, the two classes above cannot be equivalent which results in a contradiction and completes our proof that the language is not regular.
> 1 votes

# Answer
Take two inputs x and y, and for each one find the shortest non-empty string $a^k$ such that adding $a^k$ ends up in an accepting state. If for x and y these strings are different, then x and y must reach different states. If there are infinitely many x and y such that these strings are different, then the language cannot be regular.

Let x = $a^p$ for a prime number p, and g(p) be the gap between p and the next larger prime. Same with y = $a^q$. If g(q) ≠ g(p) then x and y must be in different states. There is a theorem about prime numbers that the gaps between primes become arbitrary large, so there is an unlimited number of different states, and the language is not regular.

The same is true for every set of integers where the gaps between consecutive integers become arbitrary large.
> 0 votes

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


title: Memory allocation of priority queues

text:
# Question
Title: Memory allocation of priority queues
So, i faced this question during a pratice quiz

i have no idea why " all of the elements are located contiguously in memory " wrong!! My logic is that priority queues are made of binary heaps and binary heaps are made of arrays ( according to introduction to algorithms by CLRS ) , so this means that elements are located contiguously in memory is true for PQ since it's true for arrays so, what am i doing wrong ?!

# Answer
> 1 votes
An associative dictionary is any data structure which maps keys to values. Binary search trees, hash tables, and B-trees are all examples of associative dictionaries. It is incorrect to say that an associative dictionary must be a binary search tree.

Similarly, a priority queue is any data structure which allows insertion in any order and removal in priority order. A binary heap is an example of a priority queue, but it is incorrect to say that a priority queue must be a binary heap.

There are lots of other data structures which implement priority queues, including n-ary heaps (for n greater than 2), binomial heaps, Fibonacci heaps, Brodal queues, van Emde Boas trees, and many more besides.

And that's leaving aside the issue that a binary heap doesn't strictly need to be stored in contiguous memory. Any storage scheme can be used as long as it can be indexed like an array and supports $O(1)$ access time.

---
Tags: data-structures, heaps
---


# Question
Title: PAC learning: success of learning when receiving a sample from a different distribution
I've come across this question and I think I'm on the right track with the idea I just don't really know how to formalize it properly or understand why everything said in the question is required for the proof. The question is as follows:

> Let $\mathcal X$ be a finite example domain and let $\mathcal Y = \\{0, 1\\}$. Let $H ⊆ \mathcal Y^ \mathcal X$ be a finite hypothesis class. Let $\mathcal D$ be a distribution over $\mathcal X \times \mathcal Y$. Let $\mathcal G$ be a different distribution over $\mathcal X × \mathcal Y$, such that $G\_{Y |X} = D\_{Y |X}$. Suppose that an ERM algorithm $\mathcal A$ receives a sample from $\mathcal G$ instead of a sample from $ \mathcal D$, that is: $S \sim \mathcal G^m$. Prove that if $\mathcal D$ and $\mathcal G$ are realizable by $\mathcal H$, and $supp(\mathcal D\_\mathcal X) ⊆ supp(\mathcal G\_\mathcal X)$, then for every $\epsilon, \delta \in (0, 1)$, there exists a sample size $m$ (that can depend on $\mathcal D, \mathcal G, \mathcal H, \epsilon, \delta)$ such that $\mathbb P\_{S\sim \mathcal G^m}\[err(\mathcal A\[S\], \mathcal D) \geq \epsilon)\] \leq \delta$.

My idea was that since the conditional distributions are equal and the realizability assumption holds it must be that the labeling function for each distribution, say f and g, are the same as well. Now since the support of D is contained in the support of G, any example that can be observed in the sample drawn from D can also be observed in a sample drawn from G, hence enough examples drawn from G will suffice to achieve a training set S that contains all of the support of D. However, I can't quite formalize this idea.

Thanks in advance!

# Answer
> 1 votes
Let $x\_1,...,x\_N$ denote the elements of $\mathcal{X}$ and consider the marginal distributions $D\_\mathcal{X}=(p\_1,...,p\_N)$ and $G\_\mathcal{X}=(q\_1,...,q\_N)$. Recall that $p\_i\>0$ implies that $q\_i\>0$, hence the ratio $R=\max\_i\frac{p\_i}{q\_i}$ is well defined. Also denote the output of the algorithm on a sample set $S$ by $h\_S$, then:

\begin{align\*} err\_G(h\_S)&=\sum\limits\_{i=1}^N q\_i\Pr\limits\_{(x,y)\sim G}\[h\_S(x\_i)\neq y | x=x\_i\]=\sum\limits\_{i=1}^N q\_i\Pr\limits\_{(x,y)\sim D}\[h\_S(x\_i)\neq y | x=x\_i\]\\ &=R^{-1}\sum\limits\_{i=1}^N q\_iR\Pr\limits\_{(x,y)\sim D}\[h\_S(x\_i)\neq y | x=x\_i\]\ge R^{-1}\sum\limits\_{i=1}^Np\_i\Pr\limits\_{(x,y)\sim D}\[h\_S(x\_i)\neq y | x=x\_i\]\\ &=R^{-1}err\_D(h\_S) \end{align\*}

Thus, to show $err\_D(h\_S)$ is small with high probability when given samples from $G$, it suffices to show that $err\_G(h\_S)$ is small and using the bound $err\_D(h\_S)\le R \cdot err\_G(h\_S)$ where $R$ is a constant depending on the distributions. This is the standard problem of showing that the ERM is able to learn a finite hypothesis class, so I leave the details to you.

---
Tags: machine-learning
---


# Question
Title: Finite automaton whose alphabet is $\mathbb{N}$
> Is it possible to have a finite automaton where $\Sigma = \mathbb{N}$? Why or why not?

I think it is possible to have a set of all natural numbers, however I'm not sure why.

# Answer
> 1 votes
In the standard definition of a finite automaton (say a DFA or an NFA), the alphabet is a *non-empty finite set* (perhaps the empty set is allowed by some definitions). The reason we insist that the alphabet be finite is that otherwise the description of the automaton would potentially not be finite.

For example, in one common definition of DFAs, the transition function is a function from $Q \times \Sigma$ to $Q$, where $Q$ is the set of states. If $\Sigma$ is infinite, then describing the transition function would require us to list infinitely many values of the transition function.

Some definitions of DFA allow the transition function to be partial, and in that case, we could have an automaton with a finite description even when the alphabet is infinite; and the same always holds for NFAs. However, in such cases all words accepted by the automaton belong to $\Delta^\*$ for some finite $\Delta$, and so the effective alphabet is finite.

---

While the usual definition requires $\Sigma$ to be finite, the definitions of DFA and NFA still make sense even for infinite alphabets. However, if you keep the set of states finite, then you can find a partition of the alphabet into finitely many subsets $\\{\Sigma\_\sigma : \sigma \in \Delta\\}$ so that the language accepted by the automaton behaves as a language over $\Delta$, in the sense that whether a word is accepted or not depends only on which partitions $\Sigma\_\sigma$ its letters belong to (that is, it is obtained from a language over $\Delta$ by applying the inverse of the homomorphism mapping all letters in $\Sigma\_\sigma$ to $\sigma$).

Allowing infinitely many states doesn't really change the picture: if the set of states is allowed to have the same cardinality as the alphabet, then all languages are regular, and otherwise the "effective alphabet" has the same cardinality as the set of states (as in the case considered above), and all languages over that alphabet can be accepted.

This shows that even from a theoretical perspective, the most interesting case is that of finitely many states and ("without loss of generality") finite alphabet.

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


# Question
Title: TM decidability using pigeonhole principle
I think since the input word is delimited by special symbols, which the machine cannot move past, the language accepted by such a device should be finite. Are all finite languages are regular, and are regular languages decidable by a TM?

# Answer
> 1 votes
> I think since the input word is delimited by special symbols, which the machine cannot move past, the language accepted by such a device should be finite. We know that all finite languages are regular, and regular languages are decidable by a TM. Does it make sense for answering the question?

You can easily simulate any DFA in your model, and so your model accepts all regular languages. In particular, it also accepts some infinite languages, for example the language of *all* words.

---

Your class of machines is two-way finite automata, and it is known to accept the regular languages, that is, it coincides in power with one-way finite automata such as DFAs and NFAs.

However, that is not the answer that the setter had in mind. Rather, imagine the working of such a machine, having $m$ states, on an input word of length $n$. The head could be in $n+2$ different positions, and consequently the machine can be in $(n+2)m$ different configurations. Therefore, after that many steps, either the machine has halted (either accepting or rejecting the input), or some configuration has repeated (by the pigeonhole principle), in which case the machine is in an infinite loop, and will never accept. Hence after $(n+2)m$ steps we can already tell the fate of the input.

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


title: Smart most recently used algorithm

text:
# Question
Title: Smart most recently used algorithm
**Background**

I need such an algorithm inside an android app (home launcher) to show the recently used apps. I want to avoid simple LRU / MRU logic by combining those logics (or use an alternative if anyone has a suggestion). I don't want an app that was started 100x before 10 weeks to stay on top until another app was started 100x and I don't want to only show the LRU apps on top. I want something that matches what a human would expect to see in the most recently used section.

**Solution**

I can of course save every app launch in a database (including its timestamp) and then give each launch a weight based on its age and then sum them up and calc an avarage value. That's a valid solution and would fit my needs. BUT it will grow the database indefinitely.

**Question**

Does anyone has an idea or does there exist an algorithm for such a problem already that does not depend on a full list of historical data (app launches in my case)? But instead does update values that belong to each app?

# Answer
> 2 votes
I suggested looking at the Reddit ranking system in a comment, however, that system is made in such a way that the time of *creation* is what matters, and that's not really relevant in your scenario.

I therefore suggest a physics-based approach.

Model each app as a balloon (circular, in vacuum). Every time you open an app, it corresponds to hitting the balloon straight upwards (like a volleyball set hit), and when you're not hitting the balloon, it falls towards the earth. Once it hits the ground it can remain idle (or bump up a bit if you want to remind the user of apps they forgot about).

In order for an app to remain "hot" you need to keep it above ground.

So how to implement this?

We have a list of timestamps that maps days since epoch to the number of times it was opened that day. In the below sketch, I use a linear decay (gravity would of course be quadratic).

You need to experiment with the constants and try different functions (logarithms and polynomials) to get it to work to your likings.

## Sketch

```
USAGE = {  # map day to number of opens for that day
    "A": {0: 2, 1: 2, 2: 2, 3: 2, 4: 2},
    "B": {0: 10, 1: 0, 2: 0, 4: 0},
    "C": {0: 0, 1: 3, 2: 3, 4: 3},
    "D": {0: 0, 1: 0, 2: 0, 3: 5},
    "X": {0: 3, 1: 3, 2: 3, 3: 3, 4: 0},
    "Y": {0: 0, 1: 0, 2: 0, 3: 0, 4: 3},
    "Z": {0: 0, 1: 0, 2: 0, 3: 0, 4: 2},
}
IMPACT = 1.1
DECAY  = 1.1

def rank_app(timemap, t):
    """Return the "height" of the balloon on day t given the timemap"""
    height = 0
    for day in range(t + 1):
        height += timemap.get(day, 0) ** IMPACT  # impact of opening
        since = abs((t - day - 1))
        height = max(0, height - since ** DECAY)  # decay
    return round(height, 1)

def rank(usage, day):
    """Return (heigh, app) for each app on given day t."""
    return sorted(
        [(rank_app(usage[app], day), app) for app in usage],
        reverse=True,
    )

print("\n".join([f"{e[0]} {e[1]}" for e in rank(USAGE, day=5)]))

```

... which gives

```
3.9 D
2.6 X
2.6 C
2.3 Y
2.3 A
1.1 Z
0.5 B

```

Notice that `D` is on top because it was visited 5 times yesterday. On the other hand, `B` was visited 10 times on Day 0, but hasn't been visited since, so it is on the bottom.

If you are worried about the space it takes to store all the timestamps, you can truncate the list at any point and replace with its height at a given day.

---
Tags: algorithms
---


# Question
Title: What is the relation between $USAT$, $UP$ and $NP=RP$?
Definition:

*AtmostONESAT*: SAT instance having promise of $\leq1$ witness.

What is the complexity consequence if an instance of $SAT\in$ *AtmostONESAT* can be decided whether or not there is a witness in $P$?

I believe the problem is similar to UnambiguousSAT (wiki says we get NP=RP if USAT is in P https://en.wikipedia.org/wiki/Boolean\_satisfiability\_problem#Extensions\_of\_SAT).

Are following correct?

1. Given $\phi\in$*AtmostONESAT* we can decide $\exists x:\phi(x)=TRUE$ in $P$ $\implies P=UP\wedge NP=RP$?
2. $P=UP\implies NP=RP$?
3. $P=UP\implies$ Given $\phi\in$*AtmostONESAT* we can decide $\exists x:\phi(x)=TRUE$ in $P$?

# Answer
You seem to be asking about SAT under the promise that there is at most one satisfying assignment, which you seem to call USAT. That is, you are interested in the promise problem in which the Yes instances are CNFs with a unique satisfying assignment, and the No instances are CNFs with no satisfying assignments.

Valiant and Vazirani, in a celebrated paper, used the isolation lemma to give a randomized reduction from SAT to this promise problem, thus showing that the promise problem is unlikely to be much easier than SAT itself.

The problem USAT is complete for the class UP (which consists of all problems solvable by an NP machine with the promise that there is at most one accepting computation), hence P=UP iff USAT can be solved in polynomial time.
> 1 votes

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


# Question
Title: Solving Budgeted Maximum Coverage Problem using Greedy and Genetic Algorithm
I am trying to solve the Budgeted Maximum Coverage Problem.

I have read and implemented the greedy and modified-greedy methods to solve it, as proposed by Khuller.

Both are approximation algorithms. The greedy provides a $1/2(1-1/e)$ approximation, and the modified greedy guarantees $1-1/e$.

I am trying to get better results than this using a genetic algorithm. However, I am not sure if that is at all possible.

My question is, can GA (or any metaheuristics) provide better results? Or is trying such a thing futile?

# Answer
Absolutely they can. The approximation algorithms give a formal guarantee that the solution won't be too bad and they quantify what this means whereas with a metaheuristic such as GA all bets are off. Really, the only guarantee you have with GA is that the solution is valid, but that's it.

Your best bet is to just implement the GA and give it a try. Much will depend on the details and choices you make inside the method as well as on your instances and their structure.
> 4 votes

# Answer
Assuming P≠NP, it is known that no polynomial time approximation algorithm can always give a $1-1/e + \epsilon$ approximation ratio, for any positive $\epsilon$.

However, this is a worst-case hardness result. In real life, instances are typically not worst-case, and therefore you can get better guarantees in practice. This holds not only for genetic algorithms, but also for more standard algorithms, including various greedy strategies, which might perform much better in practice than their worst-case approximation guarantees.

With current mathematical technology, the only way to truly assess an approximation heuristic is to try it out on real data.
> 2 votes

---
Tags: algorithms, genetic-algorithms, set-cover
---


# Question
Title: Number of compatible trees with an ancestry matrix
Suppose you are given an ancestry matrix $M$ which means that $M\[ij\] = 1$ iff node $i$ is an ancestor of node $j$. If $M$ represents no cycles (treated as an adjacency matrix) the corresponding graph is a tree (or a forest). My question is what is the number of trees where their ancestry matrix is $M$.

Is this question any simpler than counting number of directed graphs which are compatible to a general ancestry matrix?

# Answer
> 0 votes
As hinted in the comments by @j\_random\_hacker, ancestry matrix, if valid, characterizes a unique rooted tree. A simple algorithm would be to create the tree from leaves to the root or vice versa.

---
Tags: graphs
---


title: Exclusion in a context-free language?

text:
# Question
Title: Exclusion in a context-free language?
I am learning automata theory, and I am confused about this exercise:

> Give context free grammar to create the following language where the input alphabet is $\\{a,b\\}$
>
> $L = \\{w \text{ where }w\text{ is NOT of the form }b^n a^n\\}$

So, I understand how to create $\\{b^n a^n, n\in\mathbb{N}\\}$:

> $$S \to bSa \mid \epsilon$$

But I am lost as to how to generate a language that is $\\{w \text{ where }w\text{ is NOT of the form }b^n a^n\\}$. Help would be appreciated.

# Answer
A word in $L$ must either be of the form $b^i a^j$ with $i \neq j$ or it must have $ab$ as a substring. Therefore you can write a context-free grammar $G$ for $L$ as the union of two context-free grammars $G\_1$ and $G\_2$ for $L\_1 = \\{b^i a^j \mid i \neq j\\}$ and $L\_2 = \\{w \in \\{a,b\\}^\* \mid ab \mbox{ is a substring of } w\\}$.

It is easy to come up with a context-free grammar $G\_2$. In fact, it is even easy to come up with a regular expression for $L\_2$: $(a \mid b)^\*ab(a \mid b)^\*$. Therefore I will only focus building $G\_1$.

A word in $w=b^ia^j \in L\_1$ can be written as $w = b^k \alpha a^k$, where $k = \min \\{i,j \\}$ and $\alpha$ is a non-empty string containing only $a$s or only $b$s. Conversely, all words of the form $b^k \alpha a^k$ belong to $L\_1$. Then, this is a valid grammar $G\_1$:

$$ \begin{align\*} S &\to bSa \mid A \mid B \\ A & \to aA \mid a \\ B & \to bB \mid b \end{align\*} $$
> 4 votes

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


# Question
Title: Given L is a regular language, prove that Perm(L) is Context-Free
Given a regular language $L$ defined over $\Sigma = \\{0, 1\\}$. We define a new language $$Perm(L) = \\{w \mid \exists x \in L, w \in perm(x)\\}, $$ where $perm(x)$ is the set of all permutations of the word $x$.

We have to show that $Perm(L)$ is context-free.

I have looked at the properties that neither CFL nor Regular languages are closed under permutation. Also, the problem comes with the following hint.

**Hint:** Build a PDA for $perm(L)$ which guesses a permutation of the input string and runs the DFA for $L$ on it, and uses the stack to check that it indeed guessed a valid permutation of the input string. The fact that the alphabet has only two symbols will be crucial for the latter check.

I am unable to use this hint to proceed further. Any help is appreciated!

# Answer
> 5 votes
For every symbol $\sigma\_i$ that the PDA reads, it guesses a symbol $\tau\_i$. It simulates the DFA on the word $\tau\_1 \ldots \tau\_i$, and will only accept if the DFA accepts. Using the stack, it maintains the following counter: $$ (\\#\_a(\sigma\_1 \ldots \sigma\_i) - \\#\_b(\sigma\_1 \ldots \sigma\_i)) - (\\#\_a(\tau\_1 \ldots \tau\_i) - \\#\_b(\tau\_1 \ldots \tau\_i)), $$ and only accepts if this equals zero at the end. Since $$ \\#\_a(\sigma\_1 \ldots \sigma\_i) + \\#\_b(\sigma\_1 \ldots \sigma\_i) = \\#\_a(\tau\_1 \ldots \tau\_i) + \\#\_b(\tau\_1 \ldots \tau\_i), $$ the counter equals zero iff $\tau\_1 \ldots \tau\_i$ is a permutation of $\sigma\_1 \ldots \sigma\_i$ (this only works because the alphabet is binary).

To see that this approach doesn't work for a ternary alphabet, it suffices to consider $$ \operatorname{Perm}((abc)^\*) \cap a^\*b^\*c^\* = \\{ a^nb^nc^n : n \geq 0 \\}. $$

# Answer
> 6 votes
Clearly we cannot keep both the number of $a$'s and the number of $b$'s on the stack, because what order should we use. The solution (I think) is to keep the difference of these numbers on the stack. Or better, the difference between the promised numbers in the DFA computation on word $x\in L$ that we guess, and those that are realised by the (permuted) word $w$ that we read. The stack is used to count this difference (and we must be able to store both positive and negative numbers).

In each step of the computation (i) we read a symbol $a$ from the tape and (ii) randomly follow a letter $b$ in the DFA for $L$. If these letters match then we comtinue. If these letters differ we increase or decrease the number of symbols on the stack: say we increase that number if $a=0$ and decrease if $a=1$. We accept if the simulated computation on the DFA ends in an accepting state ánd the stack is empty (or better represents the number zero).

PS. This might look different from Yuval's solution, but it basically the same.)

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


# Question
Title: What is the space complexity of quicksort?
What is the space complexity of quicksort?

I was doing some research and found some saying it is $O(1)$, some saying it's $O(\log n)$, and some saying $O(n)$. Not sure what to believe, even though $O(\log n)$ seems to make the most sense for me. Does it all depend on the pivot point that is chosen?

# Answer
Here is quicksort in a nutshell:

* Choose a pivot somehow.
* Partition the array into two parts (smaller than the pivot, larger than the pivot).
* Recursively sort the first part, then recursively sort the second part.

Each recursive call uses $O(1)$ words in local variables, hence the total space complexity is proportional to the height of the recursion tree.

The height of the recursion tree is always at least $\Omega(\log n)$, hence this is a *lower bound* on the space complexity. If you choose the pivot at random or using a good heuristic, then the recursion tree will have height $O(\log n)$, and so the space complexity is $\Theta(\log n)$. If the pivot can be chosen adversarially, you can cause the recursion tree to have height $\Theta(n)$, causing the worst-case space complexity to be $\Theta(n)$.
> 7 votes

# Answer
Since worst case space complexity of $\Theta(n)$ could be a problem, you can make a slight modification to the Qicksort algorithm: Partition the array, then sort the smaller half recursively, and sort the larger half iteratively. Roughly:

```
Sort (range r)
    While r contains two or more elements
        Partition range r
        Sort (smaller sub partition)
        r = larger sub partition

```

This reduces the worst case space required to $\Theta(\log n))$. It does *not* help with the worst case execution time.
> 2 votes

---
Tags: algorithms, sorting, quicksort
---


# Question
Title: What computational complexity classification does autonomous/self-driving cars belong to?
Self-driving car technology continues to attract popular attention and interest in today's media, but how would a computer scientist explain the theoretical nature of the problem? For example, we are frequently told that Sudoku and Go are examples of NP-completeness and PSPACE-completeness, and a range of practical progress has been made in dealing with these two categories. So similarly with autonomous vehicles, I think laypeople people (like myself) intuitively accept that learning to drive properly is a "problem", but then, what is the underlying problem that such machine learning algorithms are trying to tackle?

I did some Googling around and found different articles and papers alluding to some parts or formal abstractions of the driving problem and/or maybe robotics being PSPACE-complete. So is that the answer basically? Or is it that the question is too vague to be answerable? Or even that there hasn't been a clear understanding yet, because the area is fairly new? I'm just really curious, but didn't find anything explaining this at a high level. But when I took CS in college, the professors would emphasize to programmers that understanding the nature of the problem can be very important, e.g. understanding if your specific problem is in P or is NP-complete, and so forth.

# Answer
> 2 votes
Complexity theory is mostly interested in decision problems and in optimization problems, and your problem belongs to neither class. Complexity theory is also interested in other resources, such as communication, but at the cost of neglecting computational complexity.

Apart from not fitting the mold of problems typically considered in complexity theory, your problem is also not well-defined. There is no accurate and formal specification of the required behavior. Without such a specification it is hard to mathematically gauge its complexity.

While it is possible to abstract some aspects of "autonomous driving" into pieces which do fit current theory, in my opinion it doesn't bring us any closer to understanding the actual difficulty of solving this problem.

Complexity theory won't help you in understanding the problem of poverty, or even the problem of writing poetry, or even the decision problem of determining whether a given poem is "good" or "bad". It is not an all-encompassing theory of reality, and as you observe, it doesn't even capture all problems in which computers are involved.

Autonomous driving, in particular, combines hardware, software, legal issues, and philosophical issues. When designing autonomous vehicles, we also design the sensors available to the software controller, the mechanical interventions it is allowed to use, the laws it complies with, and so on. All of these important and pertinent issues are beyond what computational complexity theory offers.

# Answer
> 1 votes
Let’s say your self driving car is supposed to do the following steps in a loop:

```
Read all the sensors.
Calculate optimum pressure on accelerator and brakes
Calculate optimum angle for steering wheel
Set the optimum pressure and angle.

```

Now if the calculation takes too long then it is no good, your car will crash before the calculation finishes. So instead of finding optimum values, you will try to run the calculation for a fixed time, like 10 ms, and use the best result found in that time.

So you are forced to use an algorithm that works in constant time. Whether calculating the optimum values is for example np-complete or np-hard or just a high degree polynomial doesn’t matter, because you only have limited time available.

Here’s a problem that can be reasonably formalised: The Real-time Travelling Salesman problem. It’s the same as ordinary TSP, except: We are not given distances but driving times, we have a starting point, we accept the result bit by bit (give the fist destination, then the second etc. ) and the real difference: The computer has a clock that provided the real time, and the driver can start the tour as soon as one destination is given, and must stop if he or she arrives at a destination and the computer hasn’t provided the next destination.

Clearly taking a long time to find the optimal tour while forcing the driver to wait is no good. The algorithm should produce the first destination when taking longer for the calculation isn’t likely to improve the total driving time enough. We can first use some heuristics which very quickly produces a non-optimal tour, and the algorithm has to balance quality of the tour and execution time in a way that the heuristic will be beaten.

---
Tags: complexity-theory, machine-learning, robotics
---


# Question
Title: Proving program termination in the $\lambda$-calculus
Turing's *Checking a large routine*:

> Finally the checker has to verify that the process comes to an end. Here again he should be assisted by the programmer giving a further definite assertion to be verified. This may take the form of a quantity which is asserted to decrease continually and vanish when the machine stops. To the pure mathematician it is natural to give an ordinal number.

How do you apply this to a program written in the untyped $\lambda$-calculus?

# Answer
> This may take the form of a quantity which is asserted to decrease continually and vanish when the machine stops.

Lambda calculus evaluation is a sequence of beta reduction steps. So for the lambda calculus (with or without types: types don't affect evaluation), you want a quantity (a positive integer) that decreases at each reduction step.

Such a quantity exists if and only if the lambda-term is normalizable (according to a chosen reduction strategy $\to$). Proof: suppose there is a function $f : \mathbf{\Lambda}(M\_0) \to \mathbb{N}$ where $\mathbf{\Lambda}(M\_0)$ is the set of lambda-terms $M$ such that $M\_0 \to^\star M$, such that if $M \to M'$ then $f(M) \lt f(M')$. Then the length of a reduction chain from $M\_0$ is bounded by $f(M\_0)$ and in particular cannot be infinite, so $M\_0$ is strongly normalizable. Conversely, if $M\_0$ is strongly normalizable, define $f(M)$ as the length of the longest reduction starting at $M$.
> 4 votes

---
Tags: lambda-calculus, software-verification, termination
---


# Question
Title: Training a neural network by classifying its own output
The usual way one trains a neural network is to give it some input and provide the correct classification.

But what about letting the neural network produce its own inputs, and then classifying those?

Imagine the following "algorithm".

* Use a neural network to generate 2 images (random at the beginning)
* Let the user pick which one is more "interesting"
* Update the neural network based on the choice

Do you think that as a general principle this might make sense, i.e. there might be an approach that generates more "interesting" images over time? Has something similar been done until now? What approaches/papers/libraries might best help one achieve such a goal?

# Answer
No, that doesn't seem likely to be a very useful direction.

Neural networks are a form of statistical machine learning. The premise behind all statistical machine learning schemes -- including neural networks -- is that the instances in the training set need to come from the same distribution as the instances that you will apply the classifer to (i.e., the instances in the test set).

If you artificially generate instances via some arbitrary procedure, they might not come from the right distribution. That will invalidate the core assumption behind statistical machine learning and may make the classifier perform poorly.

Your approach would only work if we knew that the neural network was able to generate images that come from the right distribution (i.e., the distribution on natural images that you'll want to classify). But there's no reason to believe that will be the case. In particular, I suspect it most likely *won't* be the case.

Or, to put it another way, your approach would only work if we had a way to characterize the probability distribution on natural images and sample from this distribution. However, this appears to be as hard as building a classifier, or even harder. So, there is no free lunch.

You might interested in the distinction between discriminative vs generative models. Standard neural networks are discriminative models, and thus don't provide any (direct) way to generate images. It is also possible to build generative models, which *can* generate images. However, building a generative model is believed to be at least as hard as building a discriminative model, and probably even harder. So, your proposal amounts to saying: "if I had a generative model, I could use that to build a training set to train a discriminative model". But if building a generative model is likely even harder than building a discriminative model, so this doesn't seem to help much. There's no free lunch.

---

Separately: You don't say *how* you plan to use a neural network to generate images. Neural networks are a classifier, so they can classify an existing image, but not generate a new image. You have to do something special to generate images from a neural network.
> 1 votes

# Answer
I think that similar concept is actually used in Generative Adversarial Network. The entire neural network is like this:

real image --\> discriminator (neural network)
generator (neural network) -- fake image ---\>--┘

If you want to try your idea of "interesting image" generation, the Keras tool had a code example.
> 0 votes

---
Tags: neural-networks
---


# Question
Title: Parallized algorithm for getting the frequencies of numbers in an array
I have an array $A$ of length $n$, containing integers between $0$ and $n-1$ inclusively. I would like to convert this to an array of frequencies $F$, that is, $F\[i\]$ should be the number of times $i$ appears in the array $A$. For example, $A=\[1,3,1,1,0\]$ would be mapped to $F=\[1,3,0,1,0\]$. There is an easy algorithm for this, however I would like to do this efficiently in parallel. Here is my first attempt at doing so:

Let $n = p\*k$ where $p$ is the number of threads, $k$ is the number of indices each thread will process and $n$ is the total number of indices (length of A). Each thread is given a range containing $k$ indices and all threads have access to an array $F$ that will be the frequency list. $F\[i\]$ starts off containing $0$ but after successfully running the algorithm, will contain the frequency of index $i$ in the array $A$.

Each thread runs the following pseudo code:

```
for i in given range:
  F[A[i]] += 1

```

Assuming a mutex is used, I think this algorithm works fine, however it runs into efficiency problems because all threads may want to increase the same index of $F$ at the same time. For example, this would happen if every index of $A$ contains the same number.

I would like an algorithm which avoids this problem and is deterministic. Ideally the time complexity should be something like $O(n/p)$. This is probably not possible of course, but I would like to be able to take at least some advantage of the parallelism, even when assuming a worst case input.

# Answer
> 1 votes
It is common problem in parallel computing. Many parallel framework have "reduction operator" for such processing. Idea is simple.

Use separate **local copies** of F\[A\[i\]\] in each threads. Calculate frequency in parallel for each sub-array block in parallel. Now since each thread is updating only its local copy of frequency array F\[A\[i\]\], no mutex is required. After the completion of all threads, join all the per thread F\[\[A\]\] array's into a single application array, i.e., reduce. You will get almost O(n/p) time complexity. The actual time complexity will depend on Size of your array (larger, the better) and the number of threads (creating and joining threads takes time).

# Answer
> 1 votes
One option would be to sort the data and then compute offsets where runs of equal integers appear in the sorted array. Then, the frequencies are just differences in these offsets.

Computing the offsets can be done with a parallel "filter", sometimes also called "compaction" or "packing". For the sorting step, you could do a parallel radix sort. A semisort (e.g. https://people.csail.mit.edu/jshun/semisort.pdf) would work too. With the semisort, you get a total of O(n) work and polylog depth, which when scheduled onto p processors comes out to O(n/p + polylog(n)) time.

You won't be able to get down to exactly O(n/p) time, because at the very least you have to do a parallel summation, which for realistic computation models takes at least Ω(log(n)) time.

---
Tags: parallel-computing
---


# Question
Title: How to do asynchronous programming with only global variables?
If a programming language only supports global variables, is it still possible to use asynchronicity, like callbacks, event-driven programming, other kinds of parallelisation?

How can it be done?

# Answer
Every program that uses local variables can be converted to one that uses only global variables. So, the answer is trivially yes. However, it might not be pleasant for the software developer.
> 2 votes

---
Tags: programming-languages, language-design
---


# Question
Title: looking for counterexample for my algorithm for maximum independent set in Bipartite Graph
We wish to find the maximum independent set in a bipartite graph. My intuition led me to the following algorithm. (Assume that the bipartite graph is connected and has at least 3 vertices, if not run the algorithm on each component)

1. Given $G=(L,R,E)$
2. Let $S$ be the set of vertices with degree $1$. Note that since graph is connected and has at least $3$ vertices, $v,u\in S\implies (v,u)\not \in E$. (If $S$ is empty, go to step $5$)
3. Add the vertices in $S$ to the independent set. $\forall s\in S$, remove $s$ and neighborhood of $s$ from $G$
4. If the graph is connected, repeat steps $2-4$. If it is disconnected, repeat the steps $2-4$ for each component.
5. if $|L| \> |R|$, add $L$ to the independent set, else add $R$

Obviously, the output is some independent set, not necessarily the maximum. However, I could neither prove nor come up with an counter example. Any help will be appreciated.

https://cs.stackexchange.com/a/3033 has a answer which does not rely on intuition

# Answer
> 4 votes
Consider the following graph:

None of the vertices has degree 1, so we go straight to step 5. Your algorithm would return 5 as the maximum independent set size, as both $L$ and $R$ have 5 vertices. However, the actual maximum independent set is $\\{1, 2, 3, 6, 7, 8\\}$, which has 6 vertices.

---
Tags: graphs, bipartite-graph
---


# Question
Title: Converting 4 variable if else condition to Linear integer program
There are four variables: $x\_1, x\_2, x\_3, x\_4$.

If you choose either $x\_3$ or $x\_4$ or both — then you should choose exactly one of $x\_1$ or $x\_2$.

If you choose neither $x\_3$ or $x\_4$ — then there is no restriction in choosing $x\_1$ or $x\_2$.

I have come up with the following if else logic for this, but cannot proceed from there.

> If $x\_3+x\_4 = 0$ then $x\_1 + x\_2 \ge 0$
>
> If $x\_3 + x\_4 \ge 1$ then $x\_1 + x\_2 = 1$

Can you let me know how to come up with an integer linear program with this understanding?

# Answer
> 2 votes
Every logical formula can be converted to conjunctive normal form (CNF), that is, into a conjunction (AND) of clauses (OR). In turn, a clause $\ell\_1 \lor \cdots \lor \ell\_m$ can be expressed as the constraint $\ell\_1 + \cdots + \ell\_m \geq 1$. In this way, you can express any logical condition in an integer program.

As an example, consider the logical formula $x \oplus y$, that is, exactly one of $x,y$ is true. While it can be expressed directly as $x + y = 1$, let's see how to do it using CNF. Putting it into CNF, we get $(x \lor y) \land (\lnot x \lor \lnot y)$. Therefore we add the following constraints: $x + y \geq 1$ and $(1-x) + (1-y) \geq 1$, i.e., $-x-y \geq -1$.

---
Tags: integer-programming
---


# Question
Title: Proving a language with $(ab)^n$ is not regular with pumping lemma?
I have been working to understand the pumping lemma better, but I am quite stuck at proving these two languages is not regular:

\begin{align} L\_1 &= \\{(ab)^n c^m \mid n\ge 1, m\ge 2n \\} \\ L\_2 &= \\{(ab)^n a^k (ba)^n \mid k\<3\\} \end{align}

For $L\_2$ my approach was:

> Let us be given a number $p$. Let $z = (ab)^p a^k (ba)^p$, which satisfies $|z| = 2p \> p$, and let $z = uvw$ be its decomposition satisfying $|uv| \leq p$ and $|v| \> 0$. This means that $v = (ab)^j$ for some $0 \le j \le p$. We choose $i = 2$ for $uv^iw$, which equals $(ab)^{p+j} a^k (ba)^p$. This word has more $ab$ than $ba$, which means that it doesn't belong to the language. Therefore $L\_2$ is not regular.

Mainly I am actually confused with the $(ab)^n$, we should decomposed it so that we can pump $v$, but it is necessary to consider different cases of $v$, or is this sufficient?

# Answer
> 1 votes
Let's suppose, for concreteness, that $p = 3$.

You choose the word $z = (ab)^3a^k(ba)^3$. How does this word look like? It is impossible to tell, since we don't know what the value of $k$ is. Let's therefore take $k = 3$, that is, we are looking at the word $z = (ab)^3(ba)^3 = abababbababa$.

Next, we are given a decomposition $abababbababa = uvw$, where $|uv| \leq 3$ and $v \neq \epsilon$. There are six possibilities:

1. $u = \epsilon$, $v = a$, $w = bababbababa$.
2. $u = \epsilon$, $v = ab$, $w = ababbababa$.
3. $u = \epsilon$, $v = aba$, $w = babbababa$.
4. $u = a$, $v = b$, $w = ababbababa$.
5. $u = a$, $v = ba$, $w = babbababa$.
6. $u = ab$, $v = a$, $w = babbababa$.

You need to be able to handle *all* of them. There are four different cases: $v \in (ab)^\*$, $v \in (ba)^\*$, $v \in a(ba)^\*$, $v \in b(ab)^\*$. For each of them, you need to find a value of $i$ so that $uv^iw \notin L\_2$. When showing that $uv^iw \notin L\_2$, you have to show that there are no $n \geq 0$ and $k \< 3$ such that $uv^iw = (ab)^n a^k (ba)^n$.

---
Tags: formal-languages, regular-languages, pumping-lemma
---


title: Is squaring easier than multiplication?

text:
# Question
Title: Is squaring easier than multiplication?
Let $T\_1(n)$ be the time complexity of computing the square of an $n$-bit integer, and let $T\_2(n)$ be the time complexity of computing the product of two $n$-bit integers.

Assuming that addition is asymptotically faster than multiplication, which of the following is correct?

1. $T\_1(n) = \Theta(T\_2(n))$.
2. $T\_1(n) = o(T\_2(n))$.
3. $T\_2(n) = o(T\_1(n))$.

Please choose one correct option of above .

# Answer
> 7 votes
Observe that $ab=\frac{1}{2}\left((a+b)^2-a^2-b^2\right)$,

hence multiplication requires three squaring operations and 3 additions/subtractions (division by 2 is easy), which means squaring is asymptotically as hard as multiplying.

---
Tags: time-complexity, asymptotics, arithmetic, big-o-notation
---


# Question
Title: How Data Compression relates to Estimating Distribution?
I recently read this paper Mahoney, 1999. And encountered this line,

> optimal compression of a probabilistic language L with unknown distribution (such as English) using an estimated distribution M (an encoding of length −log2 M(x) bits for each string x) is M = L, by the discrete channel capacity theorem.

Can you please explain what this means and what is the relation between data compression and estimation of distribution?

# Answer
> 2 votes
Suppose that we have a random source $X$, and we wish to encode many independent samples $x\_1,\ldots,x\_n$ taken from $X$. An *compression scheme* is an algorithm that converts $n$ samples of $X$ to a binary string in a reversible way. Shannon showed that the optimal compression scheme produces binary strings of length roughly $nH(X)$, where $H(X)$ is the entropy of $X$.

In practice, we may have access to $X$ but might not know its distribution exactly. What we can do is to estimate its distribution as $Y$, and then use an optimal compression for $Y$. This will produce binary strings of length roughly $n(H(X) + D(X\\|Y))$, where $D(X\\|Y)$ is the Kullback–Leibler divergence (called cross-entropy by Mahoney). We have $D(X\\|Y) \geq 0$, with equality only when $Y = X$. Thus optimal compression requires knowing the distribution of the source exactly.

---
Tags: probability-theory, information-theory, data-compression
---


# Question
Title: Data structure to query intersection of a line and a set of line segments
We want to pre-process a set $S$ of $n$ line segments into a data structure, such that we can answer some queries: *Given a query line $l$, report how many line segments in $S$ does it intersect.*

It is required that the query should be done in $O(\log{n})$ time. The data structure itself should take up to $O(n^{2})$ storage and be built in $O(n^{2}\log{n})$ time. It is suggested that it should be done in dual plane.

I understand that the question may require me to look for the number of double wedge that the a query point is in, but I can't think of any efficient data structure to report such information. Any suggestions?

This question is basically a homework question from the textbook Computational Geometry by de Berg et al (Question 8.15). I would like to apologize that this question may not be exciting to you.

Edit: Yes it is in $\mathbb{R}^{2}$. By query point I mean the query line dualised into a point on dual plane.

# Answer
HERE is the solution I did in the homework but it still lose three points on:

(3 points) Construct the O(n^2) faces with proper intersection counts of each faces.
> 1 votes

---
Tags: data-structures, computational-geometry
---


# Question
Title: Negative Numbers in 32 bit Floating Point IEEE Numbers
So I understand the logic behind converting positive decimal numbers to IEEE 32 bit floating numbers but I'm not completely sure behind the negative one's. If for example we have a decimal number say -15.5, do we have to do two's complement first then convert it to the floating point representation or we directly do it for 15.5 and at the sign bit we do 1. Thank you in advance.

# Answer
Contrary to two's complement representation of negative integers, the negative numbers in IEEE floating-point are represented with only a sign bit change, as shown in there.

For example, $0\cdot01111100\cdot01000000000000000000000$ is the representation of $0.15625$, and $1\cdot01111100\cdot01000000000000000000000$ is the representation of $-0.15625$.

In particular, there are two representations of zero (the positive one and the negative one).
> 1 votes

# Answer
IEEE floating point numbers have a sign bit. The representation of $-x$ is generally the same as that of $x$, with the sign bit flipped. This has the unfortunate consequence of having two different zeroes.
> 0 votes

# Answer
To get the binary representation for -x in IEEE754 floating point format, you start with the binary representation of x, then change the sign bit. That’s it.
> 0 votes

---
Tags: computer-architecture, floating-point, binary, number-formats
---


# Question
Title: Solving $T(n) = 2T(n/3) + T(2n/3) + n^3$
How can I solve this recursive function using substitution method?

$$T(n) = 2T(n/3) + T (2n/3) + n^3$$

I substitute $T(n/3)$ and after that $T(n/9)$. when it goes to k-step, I'm stuck.

# Answer
> 2 votes
You can use the Akra-Bazzi theorem as

$$g(x) = n^3 \in O(n^c), a\_1=2, a\_2 = 1, b\_1 = \frac{1}{3}, b\_2 = \frac{2}{3}$$

So, just we need to find $p$ such that:

$$2\left(\frac{1}{3}\right)^p + \left(\frac{2}{3}\right)^p = 1$$

You can find the computation for finding $p$ here. It is around $1.4$. Now, we can write:

$$T(n) \in \Theta\left(n^{p}\left(1 + \int\_{1}^{n}\frac{u^3}{u^{1+p}}du\right)\right)$$

To simplify the term, we can write:

$$ \int\_{1}^{n}\frac{u^3}{u^{1+p}}du = \int\_{1}^{n}u^{2-p}du = \frac{1}{3-p}u^{3-p} |\_1^n = \frac{1}{3-p}(n^{3-p}-1) $$

Now, by substituting this term in the main complexity term, we can conclude that $T(n) \in \Theta(n^3)$.

# Answer
> 0 votes
You can use proof by induction, ignoring for a moment the fact that $n/3$ and $2n/3$ are not always integers. We aim at a bound of the form $Cn^3$, which for large enough $C$ will satisfy the base case. As for the inductive step: $$ T(n) = 2T(n/3) + T(2n/3) + n^3 \leq 2C(n/3)^3 + C(2n/3)^3 + n^3 = \left(\frac{10}{27}C + 1\right)n^3. $$ This is bounded by $Cn^3$ for all $C \geq 27/17$.

# Answer
> 0 votes
If you look at the other two answers: The term $...+ n^3$ means the solution cannot be less than $O(n^3)$. At this point you can guess that the p from the Akra-Bazzi Theorem is less than 3, in that case the proof by complete induction works (lucky you!)

Same problem with a term $... + n^{1.2}$, proof by induction that $T(n) = O(n^{1.2}) would fail, so you would have to go the complicated route following OmG’s answer.

---
Tags: asymptotics
---


# Question
Title: PDA accepting all words not of the form $b^na^n$
I am studying Automata theory. DFAs and NFAs seem pretty straightforward to me, but I don't quite understand how to design push-down automata for context-free languages.

If I have context-free language where the input alphabet is $\\{a,b\\}$ $L = \\{w \text{ where }w\text{ is NOT of the form }b^n a^n\\}$

How would I design a push-down automata for it? What are the steps I would need to take, and what would it look like (formal description)?

# Answer
> 1 votes
In a related question you obtained a context-free grammar for this language.

* $S\to bSa \mid A\mid B$
* $A\to aA \mid a$
* $B\to bB \mid b$

Although I agree with Yuval that directly constructing a push-down automaton shows you understood the concepts of a PDA, I like to recall that there are direct constructions between PDA and CFG. As wikipedia mentions the construction from CFG to PDA is straightforward. The other direction is more tedious.

The construction in wikipedia is called *expand-match*. One obtains a PDA that accepts by empty stack that way, which is slightly nonstandard. I will add the details for a PDA with final state acceptance.

The new PDA has three states, initial state $q\_0$, working state $q\_1$ and accepting state $q\_2$. The initial push-down symbol is $Z$. First step: push the axiom on the stack.

* $(q\_0,\varepsilon,Z, q\_1, SZ)$

Now perform the CFG derivation on the stack (expand), checking the derived terminals with the tape symbols (match)

* $(q\_1,\varepsilon ,A,q\_1,\alpha )$ for each rule $A\to \alpha$
* $(q\_1,a,a,q\_1,\varepsilon )$ for each terminal symbol $a$

Finally, move to accept when the stack reaches bottom.

* $(q\_1,\varepsilon,Z,q\_2,Z)$

As an example, the CFG production $S\to bSa$ is directly translated into the PDA instruction $(q\_1,\varepsilon ,S,q\_1,bSa )$.

# Answer
> 1 votes
The PDA has two main states:

* No $a$ has been encountered.
* Some $a$ has been encountered.

While in the first state, it pushes $B$ onto the stack for any $b$ it encounters. It moves to the second state when encountering an $a$, at which point it removes $B$ from the stack for any $a$ it encounters (including the first $a$). If it ever realizes that it has seen more $a$s than $b$s, or if it encounters $b$ again, it can immediately accept (depending on your model, you might have to read the remainder of the input). After finishing reading the entire input, if the stack contains at least one $B$ then it accepts, and otherwise it rejects. You can implement this by requiring the PDA to pop at least one $B$ before accepting.

Formally describing this PDA depends on the exact definition of PDAs in your class, and in any case, it is an exercise which is best for you to do on your own.

---
Tags: automata, context-free, pushdown-automata
---


# Question
Title: Construct a Deterministic Pushdown Automaton for unequal number of elements
Can anyone help me construct a deterministic PDA for the following language:

$$L=\\{w\in(a,b)^\* \mid \\#\_a(w)\neq \\#\_b(w)\\}$$

Or can anyone check if the following solution is correct?

# Answer
The image in the question shows a correct construction of a deterministic pushdown automaton (DPDA) for the language of unequal number of $a$'s and $b$'s, as the OP and I have come to an agreement in a long discussion.

Please note that in OP's notation for DPDA, a fixed symbol $Z$ is at the bottom of the stack. The only case of an $\epsilon$-transition being used is when the stack top is $Z$.

The basic idea is to **use the stack to record the difference of the number of $a's$ and the number of $b's$**.

* If the symbol above $Z$ is $a$, then the stack does not contain $b$ and the number of $a$'s in the stack is how many more $a$'s have been fed to the DPDA than $b$'s.
* If the symbol above $Z$ is $b$, then the stack does not contain $a$ and the number of $b$'s in the stack is how many more $b$'s have been fed to the DPDA than $a$'s.
> 0 votes

# Answer
The answer in that image is actually not a deterministic PDA, because in the definition of DPDA, the transition functions need to satisfy the following rules: 1. $\delta(q, a, b)$ contains at most one element; 2. if $\delta(q,\lambda,b)$ is not empty, then $\delta(q,c,b)$ must be empty for every $c\in\Sigma$. These two rules prevent multiple paths for same input symbol and stack symbol (to make it deterministic). From the PDA in the question, there are some transitions like $\delta(q\_0,a,b)$ and $\delta(q\_0,\lambda,b)$, which does not satisfy the second rule.

There is one way to get the DPDA for this language $L=\\{w: n\_a(w)\neq n\_b(w)\\}$, which is to get the DPDA of the complement of $L$ first, and that is $\bar{L}=\\{w: n\_a(w)=n\_b(w)\\}$. Then you can simply convert the final states to non-final states and vice versa. The DPDA for $\bar{L}$ is very similar to the one in the question, except that the transitions from $q\_0$ to $q\_1$ should be changed to $ \delta(q\_0,\lambda,＄)=(q\_1,＄). $ After that, changing $q\_0$ to a final state and $q\_1$ to a non-final state and you will get the correct answer. This method is based on the closure property for DCFL that DCFL is closed under complementation.
> 1 votes

---
Tags: context-free, pushdown-automata
---


# Question
Title: Finding a lower bound for the expression $\ln^k(n)$
Problem:
Assume that $k \geq 1$ and $\epsilon \geq 0$, is $\ln^k(n) \in$ $\Omega( n^\epsilon)$?

Answer:

In the special case of $\epsilon = 0$, I claim the answer is no. I suspect the person who wrote this problem meant to write: assuming $\epsilon \> 0$.

I claim that if we differentiate $\log^k(n)$, k times then we get an expression with $n^{-k}$ in it. If we differentiate $n^{e}$ k times then we get an expression with $n^{\epsilon- 2}$ in it. Let me illustrate this with an example. Suppose I pick $k = 2$. Then if I differentiate the first expression twice, I get: $$ \frac{ 2 - 2 \ln(x) }{x^2} $$ When I differentiate the second expression twice, I get: $$ \epsilon ( \epsilon - 1 ) n ^ { \epsilon - 2 } $$ Hence, I claim the answer is no. Do I have this right?

# Answer
> 1 votes
The notation $\log^k n$ most likely stands for $(\ln n)^k$ (this is a common abuse of notation). In this case the claim is trivially when $\varepsilon=0$ true since $n^\varepsilon=1$ and $\ln^k n = \Omega(1)$.

For constant $\varepsilon\>0$ and $k \ge 1$ you have: $$ \lim\_{n \to +\infty} \frac{\ln^k n}{n^\varepsilon} = \lim\_{n \to +\infty} \left( \frac{\ln n}{n^\frac{\varepsilon}{k}} \right)^k = \left( \lim\_{n \to +\infty} \frac{\ln n}{n^\frac{\varepsilon}{k}} \right)^k = \left( \lim\_{n \to +\infty} \frac{1}{n \cdot \frac{\varepsilon}{k} \cdot n^{\frac{\varepsilon}{k}-1}}\right)^k = \left( \lim\_{n \to +\infty} \frac{k}{\varepsilon n^\frac{\varepsilon}{k}} \right)^k = 0, $$

showing that $\ln^k n = o(n^\varepsilon)$, and hence that the claim is false.

# Answer
> 1 votes
It is well known that $\ln(n)=o(n^{\epsilon'})$ for any $\epsilon'\>0$. Now, fix some $k$, and define $\epsilon':=\frac{\epsilon}{k}$.

From the multiplicative rule of the small-o (or equivalently, the multiplicative rule of limits), since $k\in \mathbb{N}$, we get: $\ln^k(n)={o(n^{\epsilon'})}^k=o({(n^{\epsilon'})}^k)=o(n^{k\epsilon'})=o(n^\epsilon)$.

Thus $\ln^k(n)=o(n^\epsilon)$, which means that $\ln^k=\Omega(n^\epsilon)$ **is a false statement**, for any $\epsilon$.

---
Tags: algorithm-analysis
---


# Question
Title: With a list of opcodes for a virtual machine, is it possible to assign a number to every possible program of size n that can be run on that machine?
Say you have some virtual machine with \< 100 numbered opcodes that fully specify its behaviour. Is there an easy way to order and enumerate all possible programs of less than n instructions, the result being that a particular number refers to a particular program? Preferably with natural numbers and short programs at the begining.

As this list would be combinatorially large, it would be helpful to assign these numbers without running the programs or loading them into memory.

# Answer
There is no need to *assign* a number. The program already *is* a number.

If you have $m$ opcodes and your program has $n$ instructions, then it can be interpreted as an $n$-"digit" number written in base $m$.
> 2 votes

---
Tags: programming-languages
---


# Question
Title: Finding a lower bound for the expression $\log(n!)$
Problem:
Is $\log(n!) \in$ $\Omega( n^n )$?

Answer:
Since $n! \> n^n$ for all $n \> 1$ we can conclude that: $\log(n!) \in$ $O( n^n )$.
Let us look at the special case where $n = 4$. \begin{align\*} n! &= 4(3)(2) = 24 \\ n^n &= 4^4 = 256 \end{align\*} Let us look at the special case where $n = 5$. \begin{align\*} n! &= 5(4)(3)(2) = 5(24) = 120 \\ n^n &= 5^5 = 3125 \end{align\*} Let us look at the special case where $n = 8$. \begin{align\*} n! &= 8! = 40320 \\ n^n &= 8^8 = 16777216 \end{align\*} It looks to me that $n^n$ is growing faster but that is not a proof. To prove it, I need to show that there exists an $M \> 0$ and $n\_o \> 0$ such that the following statement is true for all $n \geq n\_0$: $$ n! \leq M n^n $$ I select $n\_0 = 4$ and $M = 1$. Hence the expression reduces to: $$ n! \leq n^n $$ We have already shown that this expression is true for the special case of $n = 4$. Now, if we add $1$ to $n$ we have: $$ (n+1)! \leq (n+1)^{(n+1)} $$ This must be true because the left hand side increased by a factor of $n+1$ and the right hand side increased by more than a factor of $n+1$. Now we add $1$ to $n$ again. The left hand side increases by a factor of $n+2$ and the right hand side increases by more than a factor of $n+2$. Hence the right side increases more. We can repeat this process for ever. Therefore, I conclude the statement is true.
Do I have this right?

# Answer
Firstly, $n!$ is NOT greater than $n^n$. Indeed, $n! = \displaystyle\prod\limits\_{k=1}^nk\leq \prod\limits\_{k=1}^nn = n^n$.

Secondly, even if you have a function $f(n)$ such that $f(n) \> n^n$, that does not mean that $\log(f(n)) \in \Omega(n^n)$. For example, $n^{n+1}\>n^n$, but $\log(n^{n+1}) = (n+1)\log n \< n^2 = o(n^n)$.

Finaly, you can write $\log(n!) = \log(\prod\limits\_{k=1}^nk) = \sum\limits\_{k=1}^n\log(k) \leq \sum\limits\_{k=1}^n\log(n) = n\log n$.

With this inequality, we can deduce that $\log(n!) \in O(n\log n)$ and since $n\log n = o(n^n)$, the statement $\log(n!) \in \Omega(n^n)$ is false.
> 0 votes

# Answer
$\log n! \le \log n^n = n \log n = o(n^n)$.
> 1 votes

---
Tags: algorithm-analysis
---


# Question
Title: Finding a tight bound for a recurrence relation
Problem:
Give tight asymptotic bounds $( \Theta )$ for the following function: $$ T(n) = T(n-2) + n $$
Answer:

We are not given the base case. I am going to assume that $T(0) = 0$ and $T(1) = 1$. Here are some values for the function. $$T(2) = T(0) + 2 = 2$$ $$T(3) = T(1) + 3 = 4 $$ $$T(4) = T(2) + 4 = 6 $$ $$T(5) = T(3) + 5 = 9 $$ $$T(6) = T(4) + 6 = 12 $$ $$T(7) = T(5) + 7 = 16 $$ $$T(8) = T(6) + 8 = 20 $$ $$T(9) = T(7) + 9 = 25 $$ $$T(10) = T(8) + 10 = 30 $$ It is growing faster than $O(n)$ time. I am fairly sure that $T(n) \in O(n^2)$. That is, $O(n^2)$ is an upper bound. If $T(n)$ is $\theta(n^2)$ then going from $n = 5$ to $n = 10$ we would expect, about, a factor of $4$ increase. We got an increased by a factor of $\frac{ 10}{3}$. I am thinking that the correct answer is: $$T(n) = \Theta(n^2)$$. However, I do not know how to prove that it is correct? or disprove it?

# Answer
> 0 votes
You just need to expant it (suppose $n$ is even) and using mathematical induction:

$$T(n) = n + (n-2) + T(n-4) = n + (n-2) + (n-4) + \cdots + 4 + 2 = $$ $$2 ( 1 + 2 + \cdots + \frac{n}{2}) = 2\frac{\frac{n}{2}(\frac{n}{2}+1)}{2} = \frac{n(n+2)}{4} = \Theta(n^2)$$

---
Tags: algorithm-analysis
---


# Question
Title: Is this language a context free language?
Consider the following language, where the alphabet is $\\{0, 1, 2\\}$: $B = \\{0^a1^b2^c|a, b, c \geq 0 \text{ and }c = ab + 1\\}$.

Is this language a context free language? Prove your answer.

I am having trouble using the pumping lemma of context free languages to show if this language is context free? Can anyone give me any tips or advice on how to approach this problem? Thanks in advance!

# Answer
You can use the pumping lemma to prove that the language is not context-free. Suppose $B$ is context-free and let $n$ be the constant of the pumping lemma. Consider the word $u = 0^n1^n2^{n^2+1} \in B$. Then we can write $u = vwxyz$ such that:

* $|wxy| \leq n$;
* $|wy| \> 0$;
* $\forall k\in \mathbb{N}, vw^kxy^kz \in B$

Now since $|wxy| \leq n$, we either have $wxy\in \\{0,1\\}^\*$ or $wxy\in \\{1,2\\}^\*$. You can then study all the different possibilities and find a contradiction in each case.
> 2 votes

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


# Question
Title: Tuple relational calculus: existential quantifiers
I have the following question and given answer:

> Question: List the names of managers who have at least one dependant.
>
> Answer: `{e.Fname, e.Lname | EMPLOYEE(e) AND (∃d)(∃t)(DEPARTMENT(d) AND DEPENDANT(t) AND e.Ssn = d.Mgrssn AND t.Essn = e.Ssn) }`

My answer was exactly the same except that instead of the `(∃d)(∃t)(...)` section I said `(∃d)(DEPARTMENT(d) AND e.Ssn = d.Mgrssn) AND (∃t)(DEPENDANT(t) AND t.Essn = e.Ssn)`.

Are these equivalent?

# Answer
Let me concentrate, as you asked, on section $(\exists d)(\exists t)(\cdots)$.

In case when one part of conjuction is "not depend" on letter under existence quantifier, holds $$(\exists d)(A \text{ and } B)\Leftrightarrow (\exists d)(A) \text{ and } B$$ Where we assume $B$ does not containt letter $d$. $$$$ In your case, for simplicity, let make following designations: $$\begin{array}{l} A(d) = \text{ DEPARTMENT(d) }\\ B(t) = \text{ DEPENDANT(t) } \\ C(d) = (\text{e.Ssn = d.Mgrssn})\\ E(t) = (\text{t.Essn = e.Ssn}) \end{array}$$ and assume, that $A,C$ doesn't depend on $t$ and $B,E$ doesn't depend on $d$. Then we have

$$(\exists d)(\exists t)\big(A(d) \text{ and } B(t)\text{ and } C(d) \text{ and } E(t)\big) \Leftrightarrow \\ \Leftrightarrow (\exists d)\big(A(d) \text{ and } C(d)\big) \text{ and } (\exists t) \big(B(t)\text{ and } E(t)\big)$$ So, you are right, they are equivalent in reviewed case.

Generally we cannot distribute existence quantifier with respect to $\text{AND}$(conjunction) operation as shows example: take $A=$"$d$ is even" and $B=$"$d$ is odd". Then, of course, sentence "$(\exists d)(A) \text{ and } (\exists d)(B)$" is true, but sentence "$(\exists d)(A \text{ and } B)$" is false.
> 1 votes

---
Tags: sets, first-order-logic, relational-calculus, tuple-relational-calculus
---


title: Random Sudoku generator

text:
# Question
Title: Random Sudoku generator
I want to generate a completely random Sudoku.

Define a Sudoku grid as a $9\times9$ grid of integers between $1$ and $9$ where some elements can be omitted. A grid is a valid puzzle if there is a **unique** way to complete it to match the Sudoku constraints (each line, column and aligned $3\times3$ square has no repeated element) and it is minimal in that respect (i.e. if you omit any more element the puzzle has multiple solutions).

How can I generate a random Sudoku puzzle, such that all Sudoku puzzles are equiprobable?

# Answer
> 16 votes
Generating the *exact* uniform distribution of all sudoku puzzles can be done that way: you can just randomly generate a 9x9 grid and then only keep it if it is a correct sudoku grid, otherwise retry.

This brute-force approach guarantees you a uniform distribution but is clearly not efficient, since you can multiply the probability of the grid to be correct by $9^{17}$ only by generating a random 8x8 grid and then fill the remaining two lines. This is still a random distribution, but still way too inefficient.

You can also force the first line to be $\[1, 2, .. 9\]$, then randomly generate the remaining of the grid and then randomly pick a permutation of all digits. You will still pick all the grids with the same probability but $9!$ faster.

Maybe you see where I am going: answering this problem in a clever way will probably lead you to wonder about the underlying symmetries of sudoku grids. A lot of work was done in this direction to prove the fact that 17 is the minimal number of clues to a sudoku (see this article) and you can go here to see this precise enumeration of 5,472,730,538 classes of 3,359,232 similar grids, which uses these symmetries:

1. Permutations of digits
2. Permutations of rows (the bands and the rows inside each band)
3. Same thing for columns
4. Transposition

With this framework you can pick randomly one of the 5,472,730,538 classes (they can actually be compressed into 6 GB) and then pick one of the representative for each symmetry, respectively one in $9!, 6^4, 6^4, 2$.

EDIT: to adapt this to incomplete puzzles, you can choose randomly a subset of your grid, check if the solution is unique with a sudoku solver and retry if not. This is **not** a uniform distribution since the number of incomplete puzzles with a unique solution may be different for two grids. (I would be very surprised otherwise)

# Answer
> 1 votes
First, you must have a sudoku solver. Apply the solver on an empty sudoku. That is to find a solution for a sudoku with no clues. Filling in numbers from top left to right bottom in order. Otherwise, there is a time issue. I don't know why. Anyway, it works very fast wait no time to have a completed sudoku puzzle. When you apply backtracking, shuffle the list of possible numbers for each position. Otherwise, you will get the same puzzle everytime.

Second, randomize a new list of all positions. That is a list of 81 positions in random order. According to this list of order, try removing numbers from the above puzzle. Everytime, you remove a number, you have to check if it has more than one solution. If it has more than one solution. The number should put back and try next position in the random list. This process continues until the end of list or you already has removed 64 numbers from the puzzle successfully. The number is 64 because somebody has proved that there is no sudoku with less than 17 clues with unique solution. This process is varies from 15 seconds to 2 minutes. Usually 30 seconds to get a sudoku puzzle.

Third, if you don't want to wait 30 seconds to 2 minutes for each sudoku puzzle, you may apply some mutations to the above sudoku. This includes switching rows and columns, rotating. You may also remap the numbers. For example, 1-\>2, 2-\>3...9-\>1. After rotating and remapping, no one will notice this is the original sudoku.

There is no way to know the generated sudoku puzzles are equiprobable.

---
Tags: algorithms, randomness, sudoku
---


# Question
Title: Repeatedly finding and deleting maximal independent sets on a graph: Number of necessary iterations in restricted cases
I am trying to design a parallel scheduling algorithm based on a constraint graph $G=(V,E)$ in which each node represents a task and each edge $e=(v\_1, v\_2)$ signifies, that tasks $v\_1$ and $v\_2$ can not be executed in parallel. Each task is executed exactly once, so the problem is finding "good" independent sets $V\_i$, so that

$$ \bigcup\_{i=1}^{k} V\_i = V\\ $$

with all independent sets $V\_i, V\_j$ being pairwise disjoint. Since MaxIS is NP-Hard my approach would be solving MIS repeatedly (finding some maximal independent set, removing those vertices and start again until the Graph is empty). I know that in the worst case of $G$ being a clique this approach would yield $n$ iterations, however in my instance i would have the guarantee that the number of neighbors of each node would be upper-bound by $c \ll |V|$.

My question is: Given such a $c$ is there any upper bound on the number of necessary steps $k$?

# Answer
> 1 votes
A partition of a graph into independent set is the same as graph coloring. Therefore we can reformulate your question as follows:

> Can we bound the chromatic number of a graph in terms of its maximum degree?

If every vertex has at most $c$ different neighbors, then the chromatic number is at most $c+1$, and this can be achieved using a greedy approach: scan the vertices in an arbitrary order, and color each vertex in a color different from all its already colored neighbors (this will always succeed since there are $c+1$ possible colors and only $c$ potential already colored neighbors).

There are graphs with maximum degree $c$ which have chromatic number $c+1$, for example the clique $K\_{c+1}$ on $c+1$ vertices, so this bound is tight.

---
Tags: graphs, parallel-computing, scheduling
---


title: Variant of assignment problem

text:
# Question
Title: Variant of assignment problem
This is something like assignment problem, we have 2 group of people, first contains $n$ person and second contains $m$ person. we have a matrix $C$ which is an $n \times m$ matrix and our goal is to find an assignment matrix $A$ which is again an $n \times m$ binary matrix (contains ones and zeros) and if $A\_{ij}$ is $1$ it shows $i$-th person from first group has assigned to $j$-th person of second group, and maximize $\displaystyle\sum\_{i}\sum\_{j} C\_{ij}A\_{ij}$, subject to following constraints:

$$ 1)\\;\\; \forall i: \\;\\; \displaystyle\sum\_{j} A\_{ij} = 1 \\ 2)\\;\\; \forall j: \\;\\; \displaystyle\sum\_{i} A\_{ij} \le 2 $$

how should I solve this problem?

**how should we solve if we have another matrix $D$ and we also want $\displaystyle\sum\_{i} D\_{ij}A\_{ij} \le constant$ ?*

# Answer
> 1 votes
You want to assign $n$ persons to $m$ groups, so that

1. Each person is assigned one group.
2. Each group is assigned at most two people.
3. For each possible person $i$ and group $j$ there is a score $C\_{ij}$, and you want to maximize the sum of scores of all assignments.

If such an assignment is at all possible, then $n \leq 2m$.

Create an instance of the usual assignment problem (in which we are looking for a one-to-one correspondence between persons and groups) as follows:

* There are $n$ real persons $1,\ldots,n$ and $2m-n$ dummy persons $n+1,\ldots,2m$.
* There are $2m$ groups, composed of two copies of the original groups: $1,\ldots,m$ and $m+1,\ldots,2m$.
* The costs $C'\_{ij}$ of the instance are: for $i \in \\{1,\ldots,n\\}$ and $j \in \\{1,\ldots,m\\}$, define $C'\_{ij} = C'\_{i(j+m)} = C\_{ij}$, and set all other costs to zero.

Every feasible solution of the original problem translates to a feasible solution of the new problem with identical cost, and vice versa.

---
Tags: algorithms, graphs, optimization, weighted-graphs, assignment-problem
---


# Question
Title: Huffman coding for non-dyadic distribution
I have a question regarding the methodology of Huffman coding. So, is there a Huffman coding methodology that approximates the minimum average number of bits per decimal character when the odds of information symbols are not powers of 2? I can't understand or find anything relevant

# Answer
Huffman's algorithm solves the following problem. Given a distribution $P=(p\_1,\ldots,p\_n)$, find a prefix code $w\_1,\ldots,w\_n$ which minimizes the expected codeword length $$ \sum\_{i=1}^n p\_i |w\_i|. $$ If $p\_i = 2^{-\ell\_i}$ then the optimal solution has $|w\_i| = \ell\_i$, and the resulting expected codeword length is exactly the entropy of $P$, but Huffman's algorithm works for any distribution.

If we call a distribution in which $p\_i = 2^{-\ell\_i}$ *dyadic* (there is no common term in the literature), then Huffman's algorithm "rounds" an arbitrary distribution $P$ into a dyadic distribution $Q$ which minimizes the Kullback–Leibler divergence $D(P\\|Q)$.

We can get closer to the entropy of $P$ by encoding together groups of symbols. If you encode $m$-tuples of symbols together, then the expected codeword length *per symbol* (i.e., dividing the expression above by $m$) is at most $H(P) + 1/m$, and in particular, it tends to the entropy as $m \to \infty$. Shannon's source coding theorem shows that you cannot go below the entropy using *any* encoding scheme, so using Huffman coding in blocks is asymptotically optimal as the block size goes to infinity.
> 1 votes

---
Tags: huffman-coding
---


# Question
Title: what is approach of solving MINUS on SPOJ?
Link: http://www.spoj.com/problems/MINUS/

I have an Idea, after doing n-1 operations one can see that there is just + and - coefficients before each number that matters. For eg. given sequence: 12 10 4 3 5 and we need to make it a mathematical expression using + and - signs only to get 4 ,one solution will be +12-10+4+3-5 = 4 ,this expression (+12-10+4+3-5) is get by using knapsack dp, so the exact sign sequence (+)12(-)10(+)4(+)2(-)5 i.e. +-++- is the required signs sequence and at first stage (+)12(+)10(+)4(+)3(+)5 i.e. +++++ how to get +-++- and what should be sequence of operations?

# Answer
I am assuming that you have found out the sequence of $+$ and $-$ which lead to getting the final result as the required integer $m$.

One observation here is that the sequence of $+$ and $-$ of length $n$ (size of array) will always start with $+$ $-$, and remaining integers can be either $+$ or $-$. To clarify: if the array is $a\_1, a\_2, a\_3, a\_4, a\_5, \ldots, a\_n$ then $m= +a\_1-a\_2 \\# a\_3 \\# a\_4 \\# \cdots \\# a\_n$, where $\\#$ is either $+$ or $-$.

Now to decipher the order in which operations should be carried out to get such a sequence we first look at the rightmost $-$ in the sequence.

For example, let the integers be $5,8,1,6,2,12$ and $m=6$.

One way to get this is $+5-8+1-6+2+12$.

The rightmost $-$ is near $6$.

Let's add parenthesis here to divide the problem into two smaller ones: $(5-8+1)-(6-2-12)$.

Now solve these two smaller problems individually with same idea of rightmost $-$: $(5-(8-1))-((6-2)-12)$.

We can clearly see the operation that is asked in the question.
> 1 votes

---
Tags: dynamic-programming, knapsack-problems
---


# Question
Title: Pumping lemma for an involved non context free language
Hi I'm trying to show $C=\\{wzzw^R|w,z\in\\{0,1\\}^+\\}$ is not a context-free language.( I have this believe because $C=\\{ww|w\in\\{0,1\\}^+\\}$ is not a context free language.) I'm really struggling to come up with a string that captures the essence of irregularity of this language: I tried strings like $s=1^p0^p1^p0^p1^p1^p$ but there are too many cases to deal with and most of the examples I saw only use 1 or 2 cases, so I believe the direction I'm going is wrong. Can you provide a hint on which string to pick as the 'pumping string'? Thank you.

# Answer
> 2 votes
Suppose that $C$ were context-free. Then the following language would also be context-free: $$ C' = C \cap 0(100+110)^+0. $$ What does $C'$ look like? Suppose that $x = wzzw^R$ belongs to $0(100+110)^+0$, where $z,w \neq \epsilon$. Note that the first two symbols of $x$ are $01$, and last two are $00$. This shows that $w = 0$, and so $zz$ belongs to $(100+110)^+$. Thus $|zz| = 3m$ for some $m \geq 1$. Since $|zz|$ is even, $m = 2k$, and so $|z| = 3m/2 = 3k$. Therefore $z$ belongs to $(100+110)^+$, and we conclude that $$ C' = \\{ 0 zz 0 : z \in (100+110)^+ \\}. $$ If $C'$ were context-free, then so would be the language $$ 0^{-1} C' 0^{-1} = \\{ zz : z \in (100+110)^+ \\}, $$ obtained by taking left and right quotients with $\\{0\\}$. Finally, if we define a homomorphism $h\colon \\{a,b\\} \to \\{0,1\\}^\*$ by $h(a) = 100$ and $h(b) = 110$ then the following language would also be context-free: $$ h^{-1}(0^{-1} C' 0^{-1}) = \\{ zz : z \in (a+b)^\* \\}. $$ Since this language is well-known not to be context-free, we conclude that so is $C$.

---
Tags: context-free, pumping-lemma
---


# Question
Title: Running time of heap sort, when all number are identical
Given n numbers that all are identical, then what would be the running time of heap sort?

Will it be in linear time $O(n)$ or, best case $\Theta(n\log n)$?

# Answer
It would be $O(n)$, because each call to a `siftdown` or `siftup` procedure would be executed in $O(1)$ if well implemented.

Indeed, in a maxheap, the siftdown procedure is called in the heapify procedure, or to extract a node from the tree, and is defined as follow:

```
siftdown(x):
   while x is not a leaf and x is strictly smaller than its two children:
      swap x and its largest child

```

Since you consider an array of $n$ equal values, the test `x is strictly smaller than its two children` will never be true, so the loop will never be executed and the complexity is $O(1)$.

Now, the heapsort procedure in an array of size $n$ is defined as follow:

* heapify the array ($n$ siftdown from last to first element);
* extract each value ($n$ siftdown).

The total complexity is indeed $O(n)$. Please note that one can prove that the heapify procedure can be executed in $O(n)$ in all cases (and not only with equal values).
> 2 votes

---
Tags: algorithms, time-complexity, sorting, heap-sort
---


# Question
Title: Is the inverse of MST cut property true? Why?
If we partition the nodes of a graph into sets A and B, there is an edge *e* of weight larger than any other edge crossing the cut between A and B, *e* would never be in the minimum spanning tree?

# Answer
This is not the case.

If an edge $e$ is a bridge in the graph, then every MST has to include $e$. There can exist some cut in which $e$ is the heaviest edge, but this does not change the fact that $e$ must be included (there is some other cut in which $e$ is the only - and therefore the lighest - edge).
> 3 votes

# Answer
There is some ambiguity in the question. I would like to present some detailed versions, where we can enjoy both the cut property and its inverse.

---

Let $G$ be a connected, edge-weighted undirected graph, $C$ be a cut of $G$ and $e$ be an edge that crosses $C$.

**The cut property of Minimum Spanning Trees (MSTs) for $(G, C, e)$**: If, for any other edge $e'$ that crosses $C$, the weight of $e$ is not larger that of $e'$, then there is an MST of $G$ that contains $e$.

Here is the inverse proposition.

**The inverse cut property of Minimum Spanning Trees (MSTs) for $(G, C, e)$**: If there exists an edge $e'$ that crosses $C$ such that the weight of $e$ is larger than that of $e'$, then there is no MST of $G$ that contains $e$.

The inverse proposition is true. We can prove it by contradiction. Suppose there is MST $M$ that contains $e$. We can replace $e$ with $e'$ to obtain a new spanning tree. This new spanning tree has less weight than $M$, which is false since $M$ has the least weight.

---

Here is a different version of the cut property.

**(*Second version*) The cut property of Minimum Spanning Trees (MSTs) for $(G, C, e)$**: If, for any other edge $e'$ that crosses $C$, the weight of $e$ is smaller than that of $e'$, then every MST of $G$ contains $e$.

Here is the inverse proposition.

**(*Second version*) The inverse cut property of Minimum Spanning Trees (MSTs) for $(G, C, e)$**: If there exists an edge $e'$ that crosses $C$ such that the weight of $e$ is not smaller than that of $e'$, then there is an MST of $G$ that does not contain $e$.

The inverse proposition is true. We can prove it directly.

* If there is MST $M$ that does not contains $e$, our proof is done.
* Otherwise, let $M$ be an MST that does contain $e$. We can replace $e$ with $e'$ to obtain a new spanning tree, which does not contain $e$. This new spanning tree has the same weight as $M$. Hence, the new spanning tree is an MST, too. $\quad\checkmark$
> -1 votes

---
Tags: graphs, weighted-graphs, minimum-spanning-tree, spanning-trees
---


# Question
Title: Iterated multiplication of permutation matrices
> Given $m$ matrices of size $n\times n$ each of which is promised to be a permutation is it in $\mathit{quasiAC}^0$ or $\mathit{AC}^0$ to multiply the permutations where

1. $m=\mathit{poly}(n)$
2. $m=\mathit{poly}(\log n)$ which means $m=O(\log^k n)$ where $k\in\mathbb N\_{\>1}$
3. $m=O(\log n)$?

Given $\mathit{poly}(n)$ inputs it is clearly in $\mathit{AC}^0$ to test the promise every input matrix is a permutation.

On other hand general iterated matrix multiplication is is $\mathit{NC}^2$.

# Answer
> 1 votes
Ben Rossman showed that any unbounded fan-in depth $d$ circuit for your problem has size at least $n^{\Omega(m^{1/2d})}$. Conversely, a simple recursive construction gives an unbounded fan-in depth $d$ formula of size $n^{O(m^{1/d})}$.

---
Tags: complexity-theory, circuits, matrices, permutations, matrix-multiplication
---


title: Arrays and pointers

text:
# Question
Title: Arrays and pointers
so I know the name of the array is a pointer to the first element of the array. But I've noticed something weird Here's the code.

Here is the result:

How is it possible that the pointer is pointing to itself and when I dereference it, I get the first element of the array? Are arrays implemented using struct? What am I missing here.

# Answer
> 1 votes
In low-level programming languages like C, arrays are implemented as a range of memory cells. Moreover, an array variable is just a pointer to the first memory cell. Now let's break the different values that you're printing:

* `a` is the address of the first memory cell.
* `&a` is the same as `a`. See this question on stackoverflow.
* `*a` is the value found at the address `a`, which is just the first element in the array.
* `a[0]` (which you're not printing) is also the first element in the array.
* `&a[0]` is the address of the first element in the array, which is the same as `a`.

In low-level programming languages like C, structs (also known as records) are also implemented as a range of memory cells. In a sense, an array of length $n$ is just a struct containing $n$ elements, ignoring the issue of alignment; but whereas arrays support access using an index, structs typically do not.

---
Tags: arrays
---


# Question
Title: A general picture of formal verification in software
I'm trying to piece together a general picture of the state of formal software verification, and I'm having a good bit of trouble. For context, I come from mostly a math background. I'm quite familiar with the state of automated theorem provers and proof assistants with respect to their use to prove well formed mathematical statements (e.g. in Coq, Isabelle, Lean, etc.). What I'm having trouble understanding is what is going on with "formal methods" in practical CS applications.

I've found that companies such as Microsoft and AWS have used TLA+ as a "formal method" in their software development somewhat substantially. But when I started to read Wayne's *Practical TLA+* book, I found that he considered a program to be formally checked if we just check say a sorting algorithm on lists of length $\<n$ with entries between 1 and $n$ for some fixed $n$, i.e. we are just checking finitely many cases and saying that therefore the algorithm should work in general. This doesn't seem particularly interesting; just an example of particularly rigorous unit testing. Notably it is not a formal proof of correctness.

On the other hand, I've seen murmurs about Isabelle and Coq being able to prove things about software just like they can prove mathematical theorems. Though when I look into the books which seem to promise this, e.g. Chlipala's *Certified Programming with Dependent Types*, I see a lot of abstract stuff that seems to vaguely relate to formally verifying programs, but no examples of taking a real program written in a language that has widespread use (e.g. C++, Python, Java, etc.) or even just pseudocode and "verifying it", whatever that means.

Can someone try to clear up my confusion?

# Answer
A formally proven program is a formally proven program regardless of which language it's in. Just because a program is written in Coq and perhaps extracted to OCaml or Haskell, rather than written in a more “enterprisy” language such as C++ or Java, doesn't make it any less of a program.

Proving programs written in general-purpose programming languages, even “tame” ones like Haskell, is hard because these languages typically include a lot of convenience features, dark corners for performance and to interface with the operating system, and rich and complex libraries. To prove a property of a program, you first need to state this property, and the statement embeds the semantics of the language that the program is written in. When you try to formalize languages that were initially designed without a formal semantics (which is almost all of them), you very quickly hit dark corners which the English description leaves unspecified, or where it's ambiguous, or where it's outright self-contradictory, or where the reference implementation doesn't do what the description says and that's considered a bug in the English rather than in the implementation. The state of the art of proving properties of programs written in a preexisting language is to restrict the programs to a subset of the language.

What goes into that subset is highly variable. Syntactic sugar is not too difficult: the semantics just needs to translate it into simpler constructs. Reflection properties aren't particularly difficult to model, but may make the model a lot more difficult to reason about (for example, it invalidates properties such as “this snippet of code doesn't have any way to reference this variable, therefore it cannot change its value”), so many frameworks rule this out. Interactions with the operating system (typically via libraries) are problematic because they require modeling the operating system, which get be extremely complex. Floating point operations are hard because keeping track of the approximations across successive operations causes a huge blow up.

For C, one of the main large subsets with a formal model is CompCert C, the language of CompCert. CompCert is a formally verified compiler (written in Coq), so if you prove a property of the C program, you can additionally get a proof of the generated machine code. CompCert C is a very large subset of C99, but the formalization excludes most of the standard library and some quirks of the language.

To prove a program that is written in a (suitable subset of a) real-world programming language, the program needs to be structured in such a way as to make the proof tractable. In practice, this means having written and proved the program first in a higher-level language (which has no implementation on real hardware), and using this higher-level language as a specification of the final program. Often there are several levels of successive refinements between the executable program and the specification.

It's fairly common that the final program is not written manually, but extracted mechanically from a higher-level language. For example, writing Coq which is extracted to OCaml, or writing F\* which is extracted to C. But the opposite approach is possible as well, for example writing (“tame”) C, annotating it with properties of functions and other code subdivisions, and using Frama-C to prove those properties (and the implied property that the C program has no undefined behavior).

When you have a formal semantics of a programming language and a way to express properties of programs, proving these properties is a mathematical theorem. Typically these theorems don't involve any complex mathematics such as calculus (unless brought in by the application domain, such as tracking the movement of a physical object), but they're difficult to prove because involve very large formulae, and contain arithmetic statements ($x^n+y^n=z^n$ is not a complex equation, but solving it is not elementary!). It's theoretically impossible to write a program that can prove a non-trivial semantic property of all programs, and practically impossible to write a program that can prove many interesting properties of typical programs. Formal verification involves a combination of breaking the problem down into sufficiently small steps (writing small functions and stating enough precise properties of those functions), having a tool automatically prove some of those properties (such as a SAT solver for propositional logic), and having humans write proofs where the computer can't do it (but the computer will check the human's proof). Proof assistants such as Coq and Isabelle come in for this last step.

Formally proving a real-world program is a huge effort, requiring a much larger amount of time and expertise than the typical software project. It's rarely done outside of high-assurance environments, mostly environments with high safety requriements such as transportation (planes, trains, not so much cars), sometimes environments with high costs such as space or (very rarely) with high security requirements such as smart cards.

> if we just check say a sorting algorithm on lists of length \<n with entries between 1 and n for some fixed n, i.e. we are just checking finitely many cases and saying that therefore the algorithm should work in general.

That would not be a formal proof unless the program had a limit of n items for its input. I don't know this book, but I suspect either you misread something. Formally checking a sorting program would involve proving its correctness for all n.
> 6 votes

# Answer
The book that defines TLA+ is "Specifying systems" by Leslie Lamport. TLA+ *is* a language for writing mathematics (TLA+ is based on Zermelo-Fraenkel set theory).

TLA+ includes temporal formulas, which can describe hardware and software systems. PlusCal is an algorithm language (user manual) that is translated to TLA+. So systems can be described either in TLA+, or in PlusCal (and then translated to TLA+). Facts about systems *are* mathematical theorems.

A TLA+ specification can be checked in two ways:

* using model checking (e.g., with the model checker TLC)
* using theorem proving (e.g., with the proof system TLAPS)

TLC and TLAPS are two of the TLA+ Tools.

Model checking can check finitely many states. So for systems with finitely many states, model checking can ensure that the system implies the given properties. For other systems, model checking can be used to increase confidence that they are correct, but cannot ensure that they have the given properties.

Theorem proving can prove any (provable) mathematical theorem, provided humans have written a sufficiently detailed TLA+ proof. So theorem proving can prove (provable) system properties. See also the paper "How to write a 21st century proof" by Leslie Lamport. One of the backends used by TLAPS is Isabelle, with a formalization of TLA+ in Isabelle/Pure.

Both theorem proving and model checking have been used in industry.

When proving properties of algorithms in TLA+, usually one first uses model checking on small/bounded instances of the problem to find errors that can be found in this way, and then writes a proof of correctness to check with a theorem prover.

What the OP mentions about checking a sorting algorithm probably was about model checking a sorting algorithm's TLA+ specification. Model checking of the TLA+ specification can check the sorting algorithm for a finite set of inputs. This does not ensure the sorting algorithm's correctness. Theorem proving *can* prove the sorting algorithm's correctness, provided one writes a TLA+ proof.

About "verifying" programs written in a programming language: it is unclear whether these have precise meaning (depends on how ambiguous the language specification is), how much their behavior is affected by compiler, operating system, and other implementation details, and their complexity is typically prohibitive for formal reasoning.

About "pseudocode", "pseudocode" does not have precise meaning. PlusCal does, and it can be used to describe algorithms.
> 4 votes

---
Tags: formal-methods, software-verification, mathematical-foundations
---