# Question
Title: Why does going from 2's complement (in binary) to the positive value by completing to 1 then adding 1 work?
I'm studying Computer science and this has confused me for a long time since our professor didn't give any proof.

When changing from 2's complement to the positive value, we can go in reverse (by subtracting 1, then using 1's complement), and that's clear why it works.

But our professor told us another method which is taking the number, using 1's complement, THEN adding 1.

I don't understand why the second method works.

# Answer
Suppose that your integers are $n$ bit long. One's complement changes $x$ to $2^n-1-x$, since adding $x$ to its one's complement gives $\underbrace{1\dots 1}\_{n}{}\_2 = 2^n-1$.

Subtracting 1 and taking one's complement changes $x$ to $2^n-1-(x-1) = 2^n-x$.

Taking one's complement and adding 1 changes $x$ to $(2^n-1-x)+1 = 2^n-x$.
> 2 votes

---
Tags: binary
---


# Question
Title: Height of epsilon-balanced binary search tree
In Balanced Binary Search Trees on the basis of size of left and right child subtrees, Hannes says:

> For example, one can say, a BST is balanced, if each subtree has at most epsilon * n nodes, where epsilon \< 1 (for example epsilon = 3/4 or even epsilon = 0.999 -- which are practically not balanced at all). The reason for that is that the height of such a BST is roughly log\_{1/epsilon}

I am a bit puzzled on the last statement -- how do we know that the height is roughly 1/epsilon?

# Answer
Take any path in the tree, starting at the root, and consider the number of nodes at the subtree rooted at each vertex along the path. For the root, it's $n$ nodes. For the second vertex, it's at most $\epsilon n$ nodes. For the third vertex, it's at most $\epsilon^2 n$ nodes. For the $t$'th vertex, it's at most $\epsilon^{t-1} n$ nodes. If the path has length $\ell$ (edges), then the last node contains at most $\epsilon^\ell n$ nodes, and so $\epsilon^\ell n \geq 1$, or equivalently, $\ell \leq \log\_{1/\epsilon} n$.
> 4 votes

---
Tags: binary-trees, balanced-search-trees, binary-search-trees
---


# Question
Title: Could anyone prove why O(n^(log n)) < O((log n)^n)?
Could someone provide a rigorous proof of why $O(n^{log n}) \leq O((\log n)^n)$ is true? I'm trying to do this by induction but it isn't working. Thanks.

# Answer
Using $ \< $ with the big-oh notation is a bit of abuse of notation. Formally, I take your statement to mean $\forall f(n) \in O(n^{\log n}), \\; f(n) \in O((\log n)^n)$.

Let $f(n) \in O(n^{\log n})$, by definition of big-oh we know that the function is eventually bounded from above by $c n^{\log n}$ for some constant $c \> 0$. Then, for sufficiently large $n$, $$ f(n) \le c n^{\log n} = c 2^{\log(n^{\log n})} = c2^{\log^2 n} \< c2^n \< c (\log n)^n, $$ showing that $f(n) \in O((\log n)^n)$.

In particular the constant c in the last term can be made arbitrarily small. Indeed $n^{\log n} \in o((\log n)^n)$. A simple way to see this is by taking the limit of the ratio of the two functions:

$$ \lim\_{n \to \infty} \frac{n^{\log n}}{(\log n)^n} = \lim\_{n \to \infty} \frac{2^{\log^2 n}}{2^{n \log n}} = 2^{\lim\_{n \to \infty} \log^2 n - n \log n} = 0 $$
> 6 votes

# Answer
Try to check for large values of n Suppose n = 1000 and base of log = 10. i.e for n^(logn) = (1000)^3 = 1000000000
(logn)^n = (3)^100 = 5.1537752e+47

Thus results are speaking for itself.
> -5 votes

---
Tags: algorithms
---


# Question
Title: Are you allowed to use index variables in grammars?
If we say that the grammar for the language $L = \\{ww \mid w \in \\{a,b\\}^\*\\}$, is:

$\begin{align} S &\rightarrow A\_1A\_2S \mid B\_1B\_2S \mid Z\_2\\ A\_2A\_1 &\rightarrow A\_1A\_2\\ A\_2B\_1 &\rightarrow B\_1A\_2\\ B\_2A\_1 &\rightarrow A\_1B\_2\\ B\_2B\_1 &\rightarrow B\_1B\_2\\ A\_2Z\_2 &\rightarrow Z\_2a\\ B\_2Z\_2 &\rightarrow Z\_2b\\ Z\_2 &\rightarrow Z\_1\\ A\_1Z\_1 &\rightarrow Z\_1a\\ B\_1Z\_1 &\rightarrow Z\_1b\\ Z\_1 &\rightarrow \lambda\\ \end{align}$

Here, the characters for each word are generated in the order they appear in a word $x \in L$ in pairs $A\_1A\_2$ and $B\_1B\_2$, sorted using rules like $A\_2B\_1 \rightarrow B\_1A\_2$ and then converted with the end character, $Z\_2$.

It can be seen that we could easily adapt this grammar to recognise the language $L = \\{www \mid w \in \\{a,b\\}^\*\\}$, by changing the start rule to $S \rightarrow A\_1A\_2A\_3S \mid B\_1B\_2B\_3S \mid Z\_3$ and then adding more sorting and converting rules accordingly.

I am struggling to see how we can generalise this to the language $L = \\{w^i \mid w \in \\{a,b\\}^\*,i \ge 2\\}$, however.

Can you use a rule that looks like $S \rightarrow A\_1A\_2\dots A\_iS \mid B\_1B\_2\dots B\_iS \mid Z\_i$, where $i \ge 2$?

If so, can we use sorting rules that look like:

$A\_kB\_j \rightarrow B\_jA\_k$, where $1 \le j \< k \le i$,

are you allowed to use variables in grammars like that? If so, you could just write the whole grammar as:

$\begin{align} S &\rightarrow A\_1A\_2\dots A\_iS \mid B\_1B\_2\dots B\_iS \mid Z\_i,\text{ where } i \ge 2.\\ A\_kA\_j &\rightarrow A\_jA\_k;\\ A\_kB\_j &\rightarrow B\_jA\_k;\\ B\_kA\_j &\rightarrow A\_jB\_k;\\ B\_kB\_j &\rightarrow B\_jB\_k,\text{ where } 1 \le j \< k \le i.\\ A\_kZ\_k &\rightarrow Z\_ka;\\ B\_kZ\_k &\rightarrow Z\_kb;\\ Z\_k &\rightarrow Z\_{k-1},\text{ where } 1 \le k \le i.\\ Z\_0 &\rightarrow \lambda\\ \end{align}$

I have never seen a grammar with variables like this though. But I guess they aren't really variables, because $i$ needs to be specified before the computation begins. So, what you would actually be doing is choosing some $i$ and then instantiating a version of that grammar, specifially for a given $i$. Once the computation has begun, there are no actual variables in the grammar and, effectively, we are just providing rules to build a grammar for the language, based on some $i$.

I can think of an algorithm for a Turing machine that could recognise that language (by partitioning the input string $w$ in all possible ways such that $|w|\text{ mod }n = 0$, where $n$ is the number of substrings, and then checking each partition to see if any of them have exactly the same substrings), so the language must be recursively enumerable - I just can't think how to write something like this as a grammar without making rules with variables (if you arent allowed to.. if you are allowed to then I think what I have is okay..)

**EDIT:**

I think I might have come up with a way of solving the problem without using index variables:

$\begin{align} S &\rightarrow LZ\_1XR\\ X &\rightarrow A\_0X \mid B\_0X \mid \lambda\\ Z\_1A\_0 &\rightarrow A\_1A\_0Z\_1\\ Z\_1B\_0 &\rightarrow B\_1B\_0Z\_1\\ A\_0A\_1 &\rightarrow A\_1A\_0\\ A\_0B\_1 &\rightarrow B\_1A\_0\\ B\_0A\_1 &\rightarrow A\_1B\_0\\ B\_0B\_1 &\rightarrow B\_1B\_0\\ LA\_1 &\rightarrow A\_1L\\ LB\_1 &\rightarrow B\_1L\\ Z\_1R &\rightarrow RZ\_0 \mid Y\_0\\ A\_0Z\_0 &\rightarrow Z\_0A\_0\\ B\_0Z\_0 &\rightarrow Z\_0B\_0\\ LZ\_0 &\rightarrow LZ\_1\\ A\_0Y\_0 &\rightarrow Y\_0a\\ B\_0Y\_0 &\rightarrow Y\_0b\\ LY\_0 &\rightarrow Y\_1\\ A\_1Y\_1 &\rightarrow Y\_1a\\ B\_1Y\_1 &\rightarrow Y\_1b\\ Y\_1 &\rightarrow \lambda\\ \end{align}$

Here, an initial string $w$ is generated between $L$ and $R$ markers using $A\_0$ and $B\_0$ non-terminals, then the $Z\_1$ character is moved to the right of the string, making a copy of the word in $A\_1$ and $B\_1$ non-terminals which are then shuffled to the left of the $L$ marker, and this process is repeated until you have $i$ copies of the string $w$, at which point the $Z\_1$ changes and runs across the string to the left changing all the non-terminals into terminals.

I think this should work fine.. but it is a pretty complicated grammar, so my initial question still remains, are you allowed to use index variables to make rules to generate grammars like I did in the original question?

# Answer
> 3 votes
> Can you use a rule that looks like $S \rightarrow A\_1A\_2\dots A\_iS \mid B\_1B\_2\dots B\_iS \mid Z\_i$, where $i \ge 2$?

No. Grammar rules consist of explicitly given finite strings of terminals and non-terminals on each side of the arrow, and a grammar may contain only finitely many rules. The first restriction rules out the "for all $i\ge 2$" part of your rule, and the second part rules out viewing that single rule as standing for the infinite sequence of rules $A\_1\to B\_1$, $A\_1A\_2\to B\_1B\_2$, $\dotsc$.

Note that, if rules are allowed to be infinite (in size or number) then you can write a grammar for every language, as you can just give the infinite rule $A\to s\_1\mid s\_2\mid \dots$.

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


# Question
Title: show that if L is a regular, then drop(L) is a regular
I am trying to prove the following problem, but honestly I don't know what "proof" is considered a good proof.

I tried to prove it by constructing an NFA that start with w1 and ends with wk, but I feel something is missing.

I also tried to prove it by showing that w1 ∈ L1, w2 ∈ L2, …, wk ∈ Lk and a ∈ La.

thus Language L can be represented by:

L = L1\*La\*L2\*La\*…*La*Lk If L is regular then L1,L2,...,Lk and La are also regular.

Finally drop(L) can be presented as follow: drop(L) = L1\*L2\*…\*Lk, since L1,L2,...Lk are regular is drop(L) (because we know that it is closed under concatenation)

I feel that there are some notation that I am not using correctly, I don't know why I feel something is missing but can't figure it out.

# Answer
> 3 votes
I'm not sure what $L1, \dots, Lk$ are since you did not define them. The easiest way is probably that of starting with a DFA for $L$ and constructing a NFA for $drop(L)$ (hint in the spoiler below).

> Replace all transitions labelled with "a" in the DFA for $L$ with $\epsilon$-transitions in the NFA for $drop(L)$.

Then it should be easy to show that:

* If $w \in drop(L)$ then the NFA accepts $w$: use the definition of the function $drop$ to conclude that there must be a suitable word $w' \in L$. Start from an accepting path $\pi$ for $w'$ in the DFA for $L$ and modify $\pi$ to be an accepting path for $w$ in the NFA for $drop(L)$.
* If the NFA accepts a word $w$ then $w \in drop(L)$: look at an accepting path in the NFA for $drop(L)$ and use it construct a word $w'$ that is accepted by the DFA for $L$. Use the fact that you just proved that $w' \in L$ and the definition of the function $drop$ to conclude that $w$ must belong to $drop(L)$.

I'm purposefully being a bit vague on the details, so I don't completely give away the solution. Comment if you need more help.

---
Tags: formal-languages, automata, regular-languages, regular-expressions
---


# Question
Title: How to Optimise the following algorithm? maximum good value of an element in an array
I was recently stuck while doing a question, please suggest a way with a code/pseudo code to optimize the following algorithm for finding the maximum good value in an array where a good value of an array element $A\_i$ is defined as the total no. of Valid indices $\<$ such that $\_$ is divisible by $\_$. My approach is as follows,

```
    int maximum=-1;
    for(int i=n-1;i>=0;i--){
        int count=0;
        for(int j=0;j<i;j++){
            if(arr[j]%arr[i]==0)
            count++;
        }
        maximum=max(count,maximum);
     }
     print(maximum);

```

# Answer
Depending on the input values the following strategy might work: keep an array $C$ of $10^6$ elements where $C\[i\]$ will store the number of times number $i$ appears in the elements of the input array that have already been processed.

Initially $C$ is identically 0, then you consider the elements $A\_i$ one at a time. When you are processing the $A\_i$ you can compute the "good value" by taking the sum of all $C\[k A\_i\]$ for $k=1,\dots,\lfloor 10^6 / A\_i \rfloor$. Then, increment $C\[A\_i\]$.

At the end of the process return the maximum sum.

A more refined strategy is that of handling separately small and large values of $A\_i$. If $A\_i \ge 1000$ then the above algorithm check at most $10^3$ entries in $C$. If $A\_i \< 1000$ then you can find the number of its multiples by checking and keeping track of how many of the input elements seen so far are divisible by the numbers between $1$ and $1000$. This also requires $\approx 1000$ operations. So you'll be performing $\approx 2 \cdot 10^5 \cdot 10^3$ operations as opposed to $10^{10}$ of your algorithm.

An even better strategy is to keep an array $D$ where $D\[n\]=j$ means that $j$ of the numbers seen so far have $n$ a divisor. Since the number of divisors grows slowly (as $O(\log n / \log \log n)$, and it is always at most $240$ for your values) this strategy will only increment a few values per input number (less than 14 on average, assuming an uniform input distribution. See here for a plot of the number of divisors of the first $10^5$ integers). The leaves you with a number of operations of the order of $10^6$ to $10^7$.

The problem is now that of enumerating, for each number $n$, its divisors efficiently. But you can just do this as a preprocessing step by multiplying each $i=1,\dots,10^6$ by consecutive integers $k$ until it exceeds $10^6$. For each such $k$ add $i$ to the list of divisors of $k \cdot i$. This could even be done once-for-all and hardcoded in your algorithm.
> 2 votes

---
Tags: algorithms, optimization, number-theory
---


title: number of permutation with k inversions

text:
# Question
Title: number of permutation with k inversions
We are given two numbers N and K.

N \<= 10^9.

K\<=min{1000,(N\*(N-1))/2}

We need to find numbers of permutations of ( 1 to N ) such that inversions are exactly K.

If N was \<= 10^3. It would be a simple Dynamic programming question.

https://www.geeksforgeeks.org/number-of-permutation-with-k-inversions/

can we optimize it?

# Answer
> 4 votes
This is only a sketch of solution (there might be some off-by-ones)

---

Looking at a permutation of $\\{1\ldots,n\\}$ is equivalent at looking its inversion table $(a\_1, \ldots, a\_n)$ where $a\_i$ is the number of elements to the left of $i$ that are greater than $i$. Basically that gives you a bijection between $S\_n$ and $\prod\_{1\le i\le n} \\{0,\ldots,i-1\\}$ and the number of inversions of the permutation is exactly the sum of all $a\_i$ corresponding to it (see for example Knuth TAOCP volume 3 for a nice development).

So the problem is equivalent to computing the cardinal of:

$$\\{(a\_1, \ldots, a\_n) \in \prod\_{i=1}^{n}\\{0,\ldots,i-1\\}, \sum\_{i=1}^n a\_i=k\\}$$

This way, we find a DP algorithm with $n\times k$ states:

$$\text{dp}(n,k)=\sum\_{i=0}^{\min(k,n-1)}\text{dp}(n-1,k-i)$$

Thus:

* When $n$ is small ($n\le k+1$):

$$\text{dp}(n,k)=\sum\_{i=0}^{n-1}\text{dp}(n-1,k-i)=\text{dp}(n,k-1)+\text{dp}(n-1,k)$$

So you can compute these in $O(k^2)$. In particular, we will need the following vector of size $k$:

$$\begin{bmatrix} \text{dp}(k+1,0)\\ \vdots\\ \text{dp}(k+1,k) \end{bmatrix}$$

* When $n$ is large ($n\>k+1$):

$$\text{dp}(n,k)=\sum\_{i=0}^{k}\text{dp}(n-1,k-i)=\sum\_{i=0}^k \text{dp}(n-1,i)$$

In this case $\text{dp}(n,\cdot)$ depends linearly on $\text{dp}(n-1,\cdot)$, the matrix being a $k\times k$ lower triangular matrix with nonzero coefficients being all 1-s. More formally, you can rewrite the previous equality as:

$$\begin{bmatrix} \text{dp}(n,0)\\ \vdots\\ \text{dp}(n,k) \end{bmatrix}= \begin{bmatrix} 1&0&\ldots&\ldots&0\\ 1&1&0&\ldots&0\\ \vdots&\vdots&\ddots&\ddots&\vdots\\ 1&1&\ldots&1&0\\ 1&1&\ldots&1&1 \end{bmatrix} \begin{bmatrix} \text{dp}(n-1,0)\\ \vdots\\ \text{dp}(n-1,k) \end{bmatrix}$$

Just let me note:

$$A=\begin{bmatrix} 1&0&\ldots&\ldots&0\\ 1&1&0&\ldots&0\\ \vdots&\vdots&\ddots&\ddots&\vdots\\ 1&1&\ldots&1&0\\ 1&1&\ldots&1&1 \end{bmatrix}$$

Now if you iterate the relation, you will get for any $i$:

$$\begin{bmatrix} \text{dp}(n+i,0)\\ \vdots\\ \text{dp}(n+i,k) \end{bmatrix}= A^i \begin{bmatrix} \text{dp}(n,0)\\ \vdots\\ \text{dp}(n,k) \end{bmatrix}$$

In particular:

$$\begin{bmatrix} \text{dp}(n,0)\\ \vdots\\ \text{dp}(n,k) \end{bmatrix}= A^{n-k-1} \begin{bmatrix} \text{dp}(k+1,0)\\ \vdots\\ \text{dp}(k+1,k) \end{bmatrix}$$

The vector on the left hand side is what we want ($\text{dp}(n,k)$), the vector on the right hand side is what we computed in the first step (when $n$ is small). So if we can compute the $k\times k$ matrix $A^{n-k-1}$, computing the answer can be done in $O(k^2)$.

---

Now let's see how fast we can compute $A^{n-k-1}$. I suggest three different ideas (I assume that you want the answer modulo some prime $p$):

1) Matrix exponentiation: if we can multiply $k\times k$ matrices with coefficients in $\mathbb{Z}\_p$ in time $O(k^\omega)$), you can use fast exponentiation to have a $O(k^\omega \log n)$ algorithm ($\omega =2.38$ nowadays). Actually, if you are fine with a $O(k^3 \log n)$ algorithm, this should be easy to code (with the naive matrix multiplication algorithm)

2) Polynomial interpolation: if you look at the coefficients of $(A^T)^n$, it looks like:

$$(A^T)^n=\begin{bmatrix} P\_1(n)&P\_2(n)&\ldots&P\_k(n)\\ 0&P\_!(n)&\ldots&P\_{k-1}(n)\\ \vdots&\ddots&\ddots&\vdots\\ 0&\ldots&0&P\_1(n) \end{bmatrix}$$

where $P\_1, \ldots, P\_k$ are polynomials with integer coefficients and $P\_i$ is of degre $i-1$. They satisfy some kind of "generalized Pascal triangle relationship":

$$P\_i(n)=1+\sum\_{j=0}^{n-1}P\_{i-1}(j)$$

So it's possible to compute $P\_i(j)$ for $1\le i \le k$ and $0\le j\le k-1$ in $O(k^2)$. We can find coefficients of $P\_i$ by doing a Newton interpolation in $O(k \log k)$, so this should give a $O(k^2 \log k)$ algorithm.

3) Find a closed form for $A^i$ with the help of some well-known combinatorial objects. As I said in the comments, the polynomials $P\_1, \ldots, P\_k$ are close to Faulhaber's polynomials which can be computed in linear time. This might require some heavy handmade computation. I think it should lead to a $O(k^2)$ algorithm.

# Answer
> 0 votes
You could look at the answers to this question on SO: https://stackoverflow.com/questions/19372991/number-of-n-element-permutations-with-exactly-k-inversions (in particular the part about Mahonian numbers)

Additionally, it seems that dynamic programming with memoisation runs in $\mathcal{O}(N\cdot k)$ \[NB: I didn't actually check this, it's in one of the answers to the linked question\]: if this is for a competitive programming problem, you might consider trying it: even though in theory $N\cdot k$ can be as large as $10^{12}$, the judge system may test/query only reasonable cases (it happens).

---
Tags: algorithms, data-structures, dynamic-programming, permutations, mergesort
---


# Question
Title: Showing the following language is decidable
Let $BAL\_{DFA} = \\{\<M\> \mid M \text{ is a DFA that accepts some string containing an equal number of 0's and 1's } \\}$ Show that $BAL\_{DFA}$ is decidable.

Generally such questions seem to be solved by constructing a DFA that accepts all strings that have equal number of 0's and 1's and then constructing a DFA that accepts the intersection of the one we constructed and M. Then we can run $E\_{DFA}$ to check. Here we can't construct a DFA that accepts $0^n1^n$ as it is not regular, but we could construct a PDA. I think Sipser's book gives a way. But intersection of two PDA's need not necessarily be a PDA. Also we don;t have anything like $E\_{PDA}$ which is decidable. I am not aware. How could we solve this. I know this is a solved excercise in Sipser, but I want to understand how one could approach such questions.

# Answer
> 2 votes
You're almost there. Yes, the intersection of two context-free languages is in general not context-free, but you have more structure here: one of your languages is regular! The intersection of a regular language and a context-free language is context-free, which gives us something to work with.

So. We have some DFA $M$, and we can build a PDA $N$ which recognizes the language $\\{w : \\#\_0(w) = \\#\_1(w)\\}$, where $\\#\_a(w)$ denotes the number of occurrences of the symbol $a$ in the string $w$ (note this is not the same as $\\{0^n 1^n : n \geq 0\\}$). Then $L(M) \cap L(N)$ is context-free. Checking if $M$ accepts a balanced string amounts to checking if $L(M) \cap L(N)$ is the empty language. But it's known that emptiness of context-free languages is decidable. Given $M$, we can easily construct the machine which recognizes $L(M) \cap L(N)$ and check if $L(M) \cap L(N)$ is empty. So your problem is decidable!

---
Tags: complexity-theory, turing-machines, computability, automata, computation-models
---


title: How to construct a Turing Machine

text:
# Question
Title: How to construct a Turing Machine
Can someone help me to write a Turing Machine that decides whether its input sentence is in a particular language or not? This particular language generates alternating 01's. If it decides the input is in the language it enters to the halting state 'y', otherwise it enters to the halting state 'n'.

Example sentences from that language: 010101 0101 0 01 010101010101 Example sentences not from that language: 110 0101011010101

# Answer
I will assume that your tape alphabet is $\Sigma = \\{0, 1, "\\,"\\}$, where the last character is a space. Also, it is not clear if a word in the language must start with a $0$ and end with a $1$. In the following I will assume so (it should be easy to modify the machine to remove one or both of these constraints).

The Turning Machine is $\langle \\{y,n,q\_0,q\_1\\}, \Sigma, \varepsilon, \Sigma, \delta, q\_0, \\{y,n\\} \rangle$, where:

* $\delta(q\_0,0) = (q\_1, 0, R)$,
* $\delta(q\_0,1) = (n, 1, R)$,
* $\delta(q\_0,"\\,") = (q\_0, "\\,", R)$,
* $\delta(q\_1,0) = (n, 0, R)$,
* $\delta(q\_1,1) = (q\_0, 1, R)$,
* $\delta(q\_1,"\\,") = (q\_1, "\\,", R)$,
* $\delta(q\_0,\varepsilon) = (y, \varepsilon, R)$,
* $\delta(q\_1,\varepsilon) = (n, \varepsilon, R)$.

Here state $q\_0$ (resp. $q\_1$) represents that, if the input word is in $L$, its next input character must be one of $\epsilon, 0, "\\,"$ (resp. $\epsilon, 1, "\\,"$).
> 1 votes

---
Tags: turing-machines
---


# Question
Title: lambda-calc program which halts on only one input
Does there exist a normal-form lambda calculus program $f$ such that

* $f (\lambda x . x)$ normalizes
* For all normal form $e \ne \lambda x . x$, $f e$ does not normalize

# Answer
> 4 votes
Well nevermind this has an easy answer.

Let $r\_n = \lambda x\_1 ... x\_n . \lambda p . p \\: x\_1 ... x\_n$

Note that for $m \< n$, $r\_n\\: A\_1 ... A\_m$ normalizes for any normal $A\_1 ... A\_m$.

Then for any $f$, let $n$ be larger than the number of subterms in $f$.

$f \\:r\_n$ normalizes, so therefore no $f$ exists which only normalizes for a specific input.

---
Tags: lambda-calculus
---


# Question
Title: Sampling a uniform distribution of fixed size strings containing no forbidden substrings
Given a list of "forbidden" words (substrings), an alphabet, and a desired output string length, how would I efficiently sample output strings containing no forbidden word?

For short output strings with few forbidden words, I would use simple rejection sampling. Pick a string (uniformly) with the specified alphabet and length, return that string if it contains no element of the forbidden list, try again otherwise.

If I use that algorithm for output lengths several times larger than the typical forbidden word, then the probability of rejection will be higher. (Most words are 2 or 3 characters long.)

Assume the requested output length is too long to enumerate and store every possible value. My alphabet size would be 16 to 36 characters, but solutions to large alphabets would be interesting to think about. (In which case I would call these things *random sentences, forbidden n-grams, and dictionary words*.)

My forbidden word list will have one hundred to one thousand strings. I would like to avoid solutions requiring expensive precomputation or lots of memory.

---

My first idea was to try to build a random string incrementally, in contrast to the all-or-nothing approach of straightforward rejection sampling. I doubt that my algorithm produces each possible output with equal probability.

The algorithm idea follows:

1. Initialize a char buffer long enough to fit `outlen` characters.
2. Pick a random letter of the alphabet and append it to the buffer.
3. If the buffer ends with a forbidden word of length `k`, then remove the last `k` letters from the char buffer and go to 2.
4. Otherwise, go to 2 if the buffer has less than `outlen` characters.
5. Return the contents of the buffer if it is full.

Step 3 serves to rewind the algorithm, returning the char buffer to a previous legal state.

I understand that clearing the whole buffer in step 3 definitely would produce uniform output just like the straightforward rejection sampling method. However, the average number of rejections before the first valid output is generated will be the same.

I've gotten stuck trying to determine if my proposed algorithm is uniform. I have had no luck finding alternative algorithms either. I haven't yet looked at how this algorithm's performance would compare to basic rejection sampling.

# Answer
Suppose the alphabet is $\\{a,b\\}$, and you have one forbidden word, $aa$. Suppose we are trying to generate a word of length 3. The first two letters will be distributed uniformly over $ab,ba,bb$. Hence the first letter has the following distribution: $a$ with probability $1/3$, $b$ with probability $2/3$. In contrast, the allowable words are $$ aba,abb,bab,bba,bbb. $$ So the first letter should have the distribution $a$ with probability $2/5$, $b$ with probability $3/5$.

---

Here is an algorithm that does work. Construct a DFA (or UFA) for your language. For each state $q$, using dynamic programming you can count how many words of length $m$ are accepted when the automaton is started at $q$. Let us denote this by $c(q,m)$.

The correct distribution of the first letter $\sigma\_1$ of a word of length $n$ in the language is $$ \Pr\[\sigma\_1 = \sigma\] = \frac{c(\delta(q\_0,\sigma),n-1)}{c(q\_0,n)}. $$ More generally, given the first $\ell$ letters $\sigma\_1 \ldots \sigma\_\ell$, the following letter has the distribution $$ \Pr\[\sigma\_{\ell+1} = \sigma \mid \sigma\_1 \ldots \sigma\_\ell\] = \frac{c(\delta(q\_0,\sigma\_1\ldots\sigma\_\ell\sigma),n-\ell-1)}{c(\delta(q\_0,\sigma\_1\ldots\sigma\_\ell),n-\ell)}. $$ Ignoring the cost of arithmetic, you can implement this scheme in roughly $O(|Q|n)$, where $Q$ is the set of states, or in $O(|\Sigma|n^2)$. (The former, assuming that $|Q| = \Omega(|\Sigma|)$.)

As an example, let us consider the counterexample above. We construct a DFA containing two states (we can omit the sink state, obtaining a UFA) $q\_0,q\_1$. The transition function is $\delta(q\_0,a) = q\_1$, $\delta(q\_0,b) = q\_0$, $\delta(q\_1,b) = q\_0$. The relevant values of $c$ are $$ \begin{array}{c|cc} n & c(q\_0,n) & c(q\_1,n) \\\hline 0 & 1 & 1 \\ 1 & 2 & 1 \\ 2 & 3 & 2 \\ 3 & 5 & 3 \end{array} $$ These are computed by the recurrences $c(q\_0,n) = c(q\_0,n-1) + c(q\_1,n-1)$ and $c(q\_1,n) = c(q\_0,n-1)$, with base case $c(q,0) = 1$.

Since $\delta(q\_0,a) = q\_1$ and $\delta(q\_0,b) = q\_0$, we see that (for $n = 3$) $\Pr\[\sigma\_1 = a\] = c(q\_1,2)/c(q\_0,3) = 2/5$ and $\Pr\[\sigma\_1 = b\] = c(q\_0,2)/c(q\_0,3) = 3/5$.
> 5 votes

---
Tags: strings, substrings, sampling, random-number-generator
---


# Question
Title: How does the slow All-pairs-shortest-paths algorithm work?
I am trying to fully understand the following algorithm from CLRS book:

I like to think that it works similarly to Bellman-Ford algorithm by relaxing all edges once for every vertex in the graph. Then we repeat the process for every source vertex $s \in V$. But then looking at the three nested loops in `EXTEND-SHORTEST-PATHS` and the additional loop in `SLOW-ALL-PAIRS-SHORTEST-PATHS` I am confused what is happening in every loop. The book says that in every iteration of the loop in `SLOW-ALL-PAIRS-SHORTEST-PATHS` it computes a matrix of size at most $m$ edges which confuses me even more.

Could someone please explain in simple terms how the algorithm works? Also in line 7 in `EXTEND-SHORTEST-PATHS` does it mean: $$l^{'}\_{ij} \> l\_{ik} + w\_{kj} \Rightarrow l^{'}\_{ij} = l\_{ik} + w\_{kj}$$ or $$l^{'}\_{ij} \>= l\_{ik} + w\_{kj} \Rightarrow l^{'}\_{ij} = l\_{ik} + w\_{kj}$$ While there might not be a difference in both of these cases on computing shortest path distances, it does, however, produce different results when computing predecessor-subgraph.

Thanks in advance.

# Answer
> 2 votes
Let me tell you what Bellman-Fords is actually doing because the sentence `by relaxing all edges once for every vertex in the graph` is not very accurate. In Bellman-Ford you care about single-source-shortest-path. Since every path in the graph have at most $n$ nodes it has at most $n-1$ edges.

Let's say the source node is $s$, then create a table $distance\[\cdot\]$ such that $distance\[s\] = 0$ and it is $\infty$ elsewhere. Let's solve the following dynamic programming problem, compute shortest path from $s$ to $u$ (for every $u$) that uses at at least $t$ edges.

The table we already filled is correct for the case of $t=0$. If you have this table already computed for some $t$ after relaxing all edges (in any order) it will be correct for $t+1$, since you extend all shortest path that uses $t$ edges with at least one more edge by relaxing the end of the path. Notice that you don't need to relax every edge $n$ times, but $n - 1$ times since largest path will have at most $n - 1$ edges.

The algorithm you showed is doing that for every pair of nodes in parallel. The first loop only runs $n - 2$ (instead of $n - 1$ times as I stated above) because you started with a matrix with all shortest path of length 1 already calculated (your base case is $t = 1$ instead of $t = 0$).

First loop of `Extend-shortest-path` is selecting the source node and following two loops are iterating through all edges (it assume the graph is complete) and relax the path that starts at $i$ ends in $j$ and use the edge $j-k$ next.

---

Old answer below (I miss-read the question and assumed it was asking about Floyd-Warshall)

The key element that makes Floyd-Warshall (All-pairs-shortest-path) works is very different from Bellman-Fords key element.

Floyd-Warshall solves the following problem using dynamic programming. Calculate shortest path from every pair of vertex that use only first `k` vertex as intermediate hops. At the beginning it is the initial weight of existing edges and $\infty$ elsewhere (That is the base case).

Assume you have calculated such matrix for the first $k$ vertex and let's try to compute it for the first $k+1$ vertex. We should take into account paths that uses first $k$ vertex and goes through vertex $k+1$. Denote by $dp\_k(u, v)$ the shortest path from $u$ to $v$ using first $k$ vertex, then it follows that the optimal path from $u$ to $v$ using $k+1$ vertex don't use this new vertex or indeed use it, so we get minimum from both values:

$$dp\_{k+1}(u, v) = min(dp\_k(u, v), dp(u, k) + dp(k, v))$$

In practice, the same table is reused on every step, so the algorithm only requires $O(n^2)$ spatial complexity. Temporal complexity is $O(n^3)$.

---
Tags: algorithms, graphs, shortest-path
---


# Question
Title: How can I solve this problem using dynamic programming?
I'm stuck in this problem and I would need some help:

Given an array `arr`, in each step, 1, 2 or 5 units have to be incremented **to all but one item of the array**. The goal is to find the minimum number of steps to all items to be equal.

**First example**

`arr = [1, 1, 5]`

```
1) [1 (+2), 1 (+2), 5] = [3, 3, 5]
2) [3 (+2), 3 (+2), 5] = [5, 5, 5]

```

Solution: 2 steps

---

**Second example**

`arr = [2, 2, 3, 7]`

```
1) [2 (+1), 2 (+1), 3, 7 (+1)] = [3, 3, 3, 8]
2) [3 (+5), 3 (+5), 3 (+5), 8] = [8, 8, 8, 8]

```

Solution: 2 steps

---

I have tried some things but I'm really stuck.

I consider a base case when all items are already equal. In another case, I try to find all the possible solutions by incrementing 1, 2 and 5 to every item but one in the array:

```
def equal(arr):

    if (allElementsIdentical(arr)):
        return 0

    min = sys.maxsize
    for i in [1, 2, 5]:
        for j in range(len(arr)):

            #Increment all items by "i", except item at index "j"
            newArr = arr.copy()
            for k in range(j):
                newArr[k] += i
            for k in range(j + 1, len(newArr)):
                newArr[k] += i

            movements = 1 + equal(newArr)
            if movements < min:
                min = movements
    return min

```

This solution doesn't work because recursion never ends. E.g.

```
[1, 1, 5] -> [1, 2, 6] -> [1, 3, 7] -> [1, 4, 8] -> [1, 5, 9] -> ...

```

Is it my initial approach correct? How can I break it down in subproblems?

# Answer
> 1 votes
The main idea is as in the answer by @izanbf1803.

However, there is a detail: after you find the minimum value `m`, you should go through the array again, keeping in mind that `m`, `m - 1` and `m - 2` could all be your final target. After getting the total number of steps for all three of them, just return the smallest one.

For example, if the array is `[0, 0, 0]`, then the best final target is `m = 0`;

if the array is `[1, 5, 5]`, then the best final target is `m - 1 = 0`;

if the array is `[2, 5, 5]`, then the best final target is `m - 2 = 0`.

---

But why only these three possibilities? The reason is as follows.

Let `f(n)` be the number of steps required to decrease a number by `n`. It's easy to show by induction that:

* `f(5k) = k`
* `f(5k + 1) = k + 1`
* `f(5k + 2) = k + 1`
* `f(5k + 3) = k + 2`
* `f(5k + 4) = k + 2`

and to continue:

* `f(5k + 5) = k + 1`
* `f(5k + 6) = k + 2`
* `f(5k + 7) = k + 2`
* etc.

from which one sees that `f(n) <= f(n + 3)`.

If a number `t` is chosen as the final target, then the total minimum number of steps is just the sum of `f(x - t)` for all `x` in the array. Hence choosing any number `t <= m - 3` as final target would be pointless, since `t + 3` would be a better choice.

Thus the final algorithm goes like this:

---

Input: array `arr`

Output: minimum number of steps to make all numbers equal

```
Define a constant array c = [0, 1, 1, 2, 2].
Let m = minimum value in the array arr.
Let s = 0, s1 = 0 and s2 = 0.
For every element x in arr:
    Let y = x - m, y1 = y + 1 and y2 = y + 2
    Add [y / 5] + c[y mod 5] to s.
    Add [y1 / 5] + c[y1 mod 5] to s1.
    Add [y2 / 5] + c[y2 mod 5] to s2.
End For.
Return min(s, s1, s2).

```

# Answer
> 0 votes
Increasing all elements but one is equivalent to decrease only that element. Find minimum value `m`, now for each element `x` you need to find minumum number of subtractions to go from `x` to `m` (change-making problem), since you can use greedy algorithm for coins `(1, 2, 5)`, you can solve this problem in O(n).

---
Tags: algorithms, dynamic-programming
---


title: Finding efficient randomized algorithm

text:
# Question
Title: Finding efficient randomized algorithm
I'm doing a course on randomized algorithms and I've encountered a question that I'm struggling to solve.

Given a system of $m$ linear equations with $n$ variables over finite field $\mathbb{F\_2}$ where every equation is of form $a\_1x\_1+...+a\_nx\_n=b \mod 2$ and $x\_i,a\_i,b\in\\{0,1\\}$ and multiplication and sum are $\mod 2$.

*First part* of the question is to find an efficient randomized algorithm that finds an assignment to the variables over $\\{0,1\\}$ so that expected value of satisfied equations is $\frac{m}{2}$. This part is relatively easy, choosing a random assingment over $\\{0,1\\}$ gives us the desired result. Each equation is satisfied with probability $\frac{1}{2}$ and expected value over $m$ equations will give us $\frac{m}{2}$ satisfied equations.

*The second part* is the one I struggle with, it is asked to prove that there exist $O(logm)$ assignments to the variables such that every equation is satisfied by *at least* one assignment. And it is asked to propose a randomized efficient algorithm that finds those $O(logm)$ assignments with probability at least $\frac{1}{2}$. **There is also a hint:** let $E\_i$ be an event that random assignment satisfies equation $i$, then events $E\_i(1\<=i\<=m)$ are $2-wise$ independent.

I really don't know how to approach this. Any help would be appreciated.

# Answer
You already proved in *First part* that using random assignments to the values it solves $\frac{m}{2}$ equations in expected value. Moreover, this fact came from knowing that each individual equation will be solved with probability $\frac{1}{2}$ on every random assignment. So we can use the following algorithm to solve this problem:

```
E = Unsolved equations (initially all equations)
A = {} # Assignments that solves the problem.

while E is not empty:
    a = Random assignment
    SE = solved_by(E, a) # Equations in E solved by assignment a
    if |SE| * 2 >= |E|:
         E = E \ SE      # Remove solved equations
         A = A U {a}     # Add this assignment to the solution

return A

```

This algorithm will find at most $\lfloor log\_2(n) \rfloor + 1$ assignments so that every equation is solved by at least one assignment because condition `if |SE| * 2 >= |E|` half the size of `|E|` and add one assignment to `A` after every success. This will also run in time, since the probability of success is $\frac{1}{2}$, so the expected iterations for success is `2`.
> 3 votes

---
Tags: algorithms, randomized-algorithms, randomness
---


title: inserting into min heap

text:
# Question
Title: inserting into min heap
These are the instructions I been given :

> What does the array look like at each step when inserting "2" into the following min-heap?
>
> Give your answer as comma-separated numbers, with a space after each number, eg., 0, 2, 3, 4
>
> The heap starts at entry 1 (second entry) of the array, so begin with "0,..." for the unused entry.

and I need to write down the array at each step like

Immediately after item is added: for this step I got `4 6 8 7 2`

After first sift up step: `4 2 8 7 6`

but that is wrong apparently? I'm not sure why also I'm not sure where and why I'm suppose to put a 0.. is there a different way to write it?

# Answer
For any element at index $i$ store its left chid at index $2i +1$ and right child at index $2i+2$.

Your heap in the form of array without any insertion. The $0$ in the array given below means no key at that index. $$\fbox{4}\fbox{6} \fbox{8} \fbox{7}\fbox{0}\fbox{0} \fbox{0} \fbox{0}$$

After inserting $2$.

$$\fbox{4}\fbox{6} \fbox{8} \fbox{7}\fbox{2}\fbox{0} \fbox{0} \fbox{0}$$

But you need to maintain the min heap property. So

$$\fbox{4}\fbox{2} \fbox{8} \fbox{7}\fbox{6}\fbox{0} \fbox{0} \fbox{0}$$

Again $2$ is less than $8$. So

$$\fbox{2}\fbox{4} \fbox{8} \fbox{7}\fbox{6}\fbox{0} \fbox{0} \fbox{0}$$
> 1 votes

# Answer
The contents of the heap look like this: 04687, 046872, 042876, 024876. I have prefixed a 0 because, as you mention, the heap contents actually start in the second position.
> 0 votes

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


# Question
Title: Divide $n$ gifts among three people so as to minimize the difference in the total cost of gifts between the most lucky and the most unlucky people
> Divide $n$ gifts of different values among three people so as to minimize the difference in the total cost of the gifts for the most lucky and the most unlucky persons.

The total value of $n$ gifts is $W$. The most fair division will be to give all of them gifts of the total value $W/3$.

Suppose $W\_1, W\_2, W\_3$ are the total values of the gifts of the first, second and third person.

We want to minimize: $\max(W\_1, W\_2, W\_3) - \min(W\_1, W\_2, W\_3)$.

Using the knapsack problem. Assign to the first knapsack the "weight" $W/3$ and the same for the second knapsack $W/3$. Use double knapsack algorithm and get the for each knapsack the gifts that maximizes the total value but obeys the $W\_{i \in {1,2}} \le W/3$ property. Then the remaining gifts give to the third person.

The question is if such kind of algorithm is correct? If so why? If no can you provide your own solution to the problem?

# Answer
What if having empty basket for each person, keep tracking on sum of items in each basket. So we always know which basket has the minimum value. Then we can go over list of items and put the new one, in the basket with minimum total value. The complexity of this hypothesis is $O(n \log(n))$.
> -1 votes

# Answer
Say your best answer so far has a difference D, and you can give w/3 - a to the first person. The best result you can have is w/3 + a/2 to the other two, giving a difference of 3a/2, so you only proceed if 3a \< 2D (actually, you will distinguish cases depending on w modulo 3 if all sizes are integers).

Then you pick items for the second person. If you can give them w/3 - b, b ≥ a, then diff = a + 2b, so you need a + 2b \< D, or b \< (D - a) / 2; only if a ≤ D/3. If you can give them w/3 - b, 0 ≤ b ≤ a, then diff = 2a + b, so you need b ≤ D - 2a, only if a ≤ D/2. You analyse the case w/3 + b for the second person as well, so you find a range for how much goes to the second person.

Problem is that you waste a lot of time with sets for the first person that are not particularly close to w/3. Based on the number of items and their values I'd make an estimate how good the best solution would be (how much the smallest D will be) and only look for items for the first person that might give a result \< 2D, then extending to 4D, 8D etc. if nothing is found.

And you should check the case where one item is \> w/3 first, or you might waste a lot of time.
> 1 votes

# Answer
Problem 1: Divide $$ gifts among three people so as to minimize the difference in the total cost of gifts between the most lucky and the most unlucky people.

Problem 2: Partition problem

Problem 2 is known to be NP-complete. Given an instance $A$ of problem 2, we can transform it into an instance $B$ of problem 1. Here is the rule of transformation: $A= w\_1, w\_2, \dots, w\_n$. Let $t= \sum\_{i=1}^n w\_i$. Now $B=\frac{t}{2}, w\_1, w\_2, \dots, w\_n$.

Then it is easy to prove that $A$ has a partition if and only if $B$ has zero solution. Hence problem 1 is NP-hard.
> 1 votes

# Answer
This problem can be solved using double knapsack algorithm, just don't restrict yourself to the case $W\_{i \in {1, 2}} \le \frac{W}{3}$. Find all ways to decompose elements in subsets of value $A$ and $B$. Define $C = W - A - B$ (the value of the remaining set) and let the value of such decomposition be $max(A, B, C) - min(A, B, C)$. You just need to find the decomposition with least value. This can be solved in $O(W^2 \cdot n)$ (This is a pseudo-polynomial solution to the problem).

The problem is NP-Hard as mentioned previously by @jaxxa, and can be solved in $O(3^n)$ by trying all possible decomposition in three different sets, and finding the value of each decomposition.

There exists a faster solution using Meet in the middle in $O(3^{\frac{n}{2}} poly(n))$. Roughly speaking this is done dividing the set in two "equals" sets left and right, finding all decomposition in three sets of both left and right, and finding fast for every decomposition in one side best decomposition in the other side. This last part is obviously under-explained, but if someone is interested I can elaborate more on how this algorithm works.

By the way, I met this problem participating in competitive programming contests, and you can find it here. The statement is in spanish, but it is basically asking the exact same question.
> 1 votes

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


# Question
Title: Dynamic programming and multiple optimal solutions
I have tried researching how I can handle multiple optimal solutions based using dynamic programming. The answer is found from this question is simply that you have to backtrack. What if this is not possible and one of my solutions can't be found this way?

From this YouTube video we are given the problem of finding the optimal rod cuttings for maximizing profit.

The rod has a length of $n=5$, and the possible ways to cut with its respective values in parenthesis are $1(2)$, $2(5)$, $3(7)$ and $4(8)$. By setting up a matrix as in the video we end up finding that the optimal solution is $12$. By backtracking this we are only able to find one of the solutions $1,2,2$ and not the other solution consisting of $2,3$.

My question is, how can I combine dynamic programming with some sort of best sequence sum algorithm so that I am able to backtrack both solutions? The algorithm he proposes uses the max of the previous subproblem, however, that might not be the only solution as a combination of the current subproblem might also be feasible.

The matrix proposed in the video looks like this (rows are the possible cuts and columns are the rod length): $$ \begin{bmatrix} 0 & 2 & 4 & 6 & 8 & 10 \\ 0 & 2 & 5 & 7 & 10 & 12 \\ 0 & 2 & 5 & 7 & 10 & 12 \\ 0 & 2 & 5 & 7 & 10 & 12 \\ \end{bmatrix} $$

# Answer
Assume you already computed the dynamic programming table `DP[SIZE][LENGTH]` where `DP[s][l]` stands for maximum profit that can be obtained by using cuts up to size `s` on a rod of length `l`. You want to find all decomposition to get the value `DP[SIZE][LENGTH]`, to do this notice that at every step `DP[s][l]` we have two options, use the cut of size `s` or don't use it (possibly using both values we get optimal answer). The pseudo code will look like this:

```
PROFIT[s] = value of using a cut of size `s`.

def find_answers(s, l, partial_answer):
    """ Populate in `partial_answer` possible ways to
        partition a rod of length `l` using cuts of
        size up to `s` and report them.

        `partial_answer` is a multiset that will contain all cuts
        done so far.
    """

    # Base case when length is `0`.
    if l == 0:
        report partial_answer

    best = DP[s][l]

    # If not using the cut of size `s` gets a profit as good
    # as best expected profit, find solutions.
    if DP[s - 1][l] == best:
        find_answers(s - 1, l, partial_answer)

    # Try to find an answer that uses current cut size if `s` is
    # less than current length, and profit using this cut is as good
    # as best expected profit.
    if s <= l and DP[s][l - s] + PROFIT[s] == best:
        find_answers(s, l - s, partial_answer + {s})

```

Call this function like `find_answers(SIZE, LENGTH, {})` with an empty multi-set as `partial_answer`. Since it is doing backtracking it is possible to get to the same state `(s, l)` several times with different `partial_answers`. This function will call `report partial_answer` exactly once per valid decomposition, also notice that the number of optimal decomposition can be exponentially large.
> 1 votes

---
Tags: algorithms, dynamic-programming
---


title: 3-heap max heap

text:
# Question
Title: 3-heap max heap
I have this 3 heap max heap that I need to write the array for it, but I'm not sure how. Would it just be

20,18,13,15,11,12,16,10,9,11,13,2,9?

# Answer
Yes, it would be Just the Level Order Traversal of the tree, In this case, it is 20,18,13,15,11,12,16,10,9,11,13,2,9,10,1.

More generally for a generalized d-heap, the items may be viewed as the nodes in a complete d-ary tree, listed in breadth-first traversal order: the item at position $0$ of the array (using zero-based numbering) forms the root of the tree, the items at positions 1 through d are its children, the next $d^2$ items are its grandchildren, etc. Thus, the parent of the item at position $i$ (for any $i \> 0$) is the item at position $⌊(i − 1)/d⌋$ and its children are the items at positions $d\cdot i + 1$ through $d\cdot i + d$.
> 1 votes

---
Tags: heaps
---


title: reverse string to pattern matching

text:
# Question
Title: reverse string to pattern matching
I have a list of patterns, and I need to find the pattern that matches an input string the most. I.e.:

Patterns:

```
[
    'AB1XXX',
    'AB2XXX',
    'ABXXXX-0080',
    'BC1XXX',
    'BC15XX'
]

```

The `X` character in the patterns is reserved as the `wildcard` or `don't care` character. It can be any single alphanumeric character.

I then get an input, i.e.: `AB1100`. In this case I expect the pattern `AB1XXX` to be the best match. However, if I get an input `AB1100-0080` I expect `ABXXXX-0080` to be the best match for the given input.

I currently use a Trie to find the matching pattern, but it doesn't really work for the given example as it either can't find a match once it gets to `-0080`.

`Best match` can be seen as "shortest Levenshtein distance with the least amount of **X** characters used".

Is there a known algorithm I could implement or should I stick to implementing a Levenshtein distance algorithm?

# Answer
> 2 votes
The Shortest Levenshtein's Distance should be good enough. See if this Matching Wildcards Wikipedia page can be of help.

---
Tags: algorithms, search-algorithms, pattern-recognition, string-matching
---


# Question
Title: Algorithm for dividing items into buckets while minimizing total weight
Let's say I have two buckets coloured red and blue, both of which can hold two rocks. I need to divide a set of $n$ weighted rocks into these buckets in such a way as to minimize the total weight of the rocks in the buckets, while filling each bucket to its capacity.

An additional constraint is this: the rocks are themselves coloured red or blue, and can only be placed in a bucket of the corresponding colour. Moreover, the rocks can be coloured multiple different colours. In this case, the rock can be placed in any of the buckets with which it shares a colour.

For example, if our rocks are

$$\begin{array}{c|c|c|} & \text{Colours} & \text{Weight} \\ \hline \text{Rock 1} & \text{Red, blue} & 1\\ \hline \text{Rock 2} & \text{Red} & 2 \\ \hline \text{Rock 3} & \text{Red} & 3 \\ \hline \text{Rock 4} & \text{Blue} & 4 \\ \hline \text{Rock 5} & \text{Blue} & 5 \\ \hline \end{array}$$ then the optimal solution is $$\begin{array}{c|c} \text{Red Bucket} & \text{Blue Bucket} \\ \hline \text{Rock 2} & \text{Rock 1} \\ \text{Rock 3} & \text{Rock 4} \end{array}$$ as then the sum of the weights in the buckets is minimized.

One idea for an approximate algorithm as follows. First, sort the rocks in order of increasing weight. We make two passes of this list:

* First pass: if the rock has only one colour, and if fewer than 2 rocks in the list so far have had that colour, then we can add that rock to the appropriate bucket. From the above example, we see that this step will place Rock 2 into the Red Bucket and Rock 4 into the Blue Bucket. (This step will never make an incorrect placement.)
* Second pass (greedy): if the rock can fit into any of the buckets, put it there.

This algorithm does not generate the optimal solution for the above example, since on the second pass it will incorrectly place Rock 1 into the Red Bucket.

My question is this: does there exist a polynomial time algorithm to solve this problem optimally for $k$ buckets and $n$ rocks? If not, are there any polynomial time algorithms that generate approximate solutions (better than the one I've given here)?

# Answer
I assume that in the $k$ bucket case, each rock has up to $k$ colors (buckets) associated with it, which are the ones it can be put into.

It seems to me that a polynomial time algorithm can be obtained by reduction to a minimum-cost flow problem, which can be solved in polynomial time. Create a network with $k + n + 1$ nodes: $n$ rock nodes, $k$ bucket nodes, and $1$ source node. The source node is adjacent to each of the rock nodes, with edge capacity 1 and edge cost equal to the weight of the rock. Each rock node is also adjacent to all the bucket nodes it can be put into, with edge capacity 1 and edge cost 0. The source node has a supply of $2k$ units, and each bucket node has a demand of 2 units. Any integer flow of value $2k$ corresponds to a feasible assignment of $2k$ rocks to the buckets. The minimum cost integer flow corresponds to an assignment of minimum weight.
> 2 votes

---
Tags: algorithms, optimization
---


title: How do I "apply" a loop invariant?

text:
# Question
Title: How do I "apply" a loop invariant?
A homework problem I have asks that I "state" a loop invariant, then "prove" it, then "apply" it. I get state and prove, but my textbook doesn't explicitly state how to "apply" a loop invariant.

# Answer
> 3 votes
You “state” a loop invariant - that’s an educated guess.

You “prove” a loop invariant - you show it’s true before the loop is first entered, and you show that if it’s true before an iteration, then it is true after the iteration.

You apply the loop invariant - you take the fact that the loop invariant is proven, and the fact that the loop stopped iterating, to prove facts that hold after the loop is finished.

---
Tags: loop-invariants
---


# Question
Title: Is unconstrained quadratic programming NP-hard?
I could not find the answer on the Internet. The case of quadratic programming with constraints is already solved on this forum, see Transforming SAT to Quadratic Programming in polynomial time. But what happens if there are no constraints or if the only acceptable constraint is that the variables are non-negative?

# Answer
1-IN-3SAT is an NP-complete variant of 3SAT in which the goal is to determine whether some assignment satisfies *exactly* one literal per clause. We can convert an instance of 1-IN-3SAT (even without the restriction on the number of literals per clause) to an equivalent instance of quadratic programming in which all the variables are constrained to be non-negative as follows:

* For each variable $x\_i$, the quadratic program has two variables $x\_i^+,x\_i^-$, constrained to be non-negative.
* The objective is to minimize

$$ \sum\_i (x\_i^+ + x\_i^- - 1)^2 + x\_i^+ x\_i^- + \sum\_j (C\_j - 1)^2, $$ where $i$ goes over all variables, $j$ goes over all clauses, and $C\_j$ is the sum of all literals in $C\_j$: for example, if the $j$th clause is $x\_1 \lor \bar{x}\_2 \lor x\_3$ then $C\_j = x\_1 + (1-x\_2) + x\_3$.

By construction the objective function is always non-negative. The first two summands are zero if the $x\_i^\pm$ encode an assignment to the original variables, and the third is zero is this assignment satisfies exactly one literal per clause.

---

Without any constraints, the problem becomes easy. The law of inertia (which can be implemented efficiently) shows that up to a linear change of basis, we can assume that the quadratic to be minimized is $$ \sum\_{i \in A} z\_i^2 - \sum\_{j \in B} z\_j^2 + 2\sum\_k c\_k z\_k + M, $$ where $A,B$ are disjoint. If $B$ is non-empty then the quadratic form is unbounded from below, so let us assume that $B = \emptyset$. If $c\_k \neq 0$ for some $k \notin A$, then the quadratic form is also unbounded from below, so let us assume that the $c\_k$ are supported on $A$. Therefore the quadratic is equal to $$ \sum\_{i \in A} \[(z\_i + c\_i)^2 - c\_i^2\] + M, $$ showing that the minimum is $M - \sum\_i c\_i^2$.

---

A third variant that can be considered is a homogeneous objective function with non-negativity constraints. This variant is also easy.

The law of inertia transforms the problem into that of minimizing $$ \sum\_{i \in A} z\_i^2 - \sum\_{j \in B} z\_j^2 $$ under some arbitrary linear constraints.

Using linear algebra, we can check whether the linear constraints force $z\_j = 0$ for all $j \in B$. If not, then the quadratic form is unbounded from below, so let us assume it is the case. Our quadratic form is thus positive semidefinite, and so convex optimization algorithms can be used to solve it (see Wikipedia).
> 4 votes

---
Tags: optimization, quadratic-programming
---


# Question
Title: $A$ nonregular language, is $A\cup B$ nonregular?
I was reading this question; regarding whether $L=A\cup B$ is nonregular if $A$ is. As is rightly pointed out in that answer, there is no simple rule. But what if we imposed the following conditions:

1. $A \cap B=\emptyset$
2. $A\neq B^C$ and $B \neq A^C$

The examples I know of where $L$ fails to be nonregular is where $B$ somehow "makes up" for the nonregularity of $A$, such as setting $B$ as the language of all strings, or the complement of $A$.

But with these new conditions, is there any way for $B$ to turn the union $A\cup B$ into a regular language?

EDIT: Actually, if $L=\\{0^n1^m|n,m\geq 0\\}$, then

$$L=\\{0^n1^n|n\geq 0\\} \cup \\{0^n1^m|n\neq m\\}$$

and both the conditions above are fulfilled. So $L$ can still be regular. Sorry :)

# Answer
Here is one result in the direction you're looking into:

> Suppose that $A,B,C$ are languages such that $A$ is a non-regular subset of the regular language $C$, and $B$ is disjoint from $C$. Then $A \cup B$ is non-regular.

For the proof, consider the intersection of $A \cup B$ and $C$. Details left to the reader.

The question you link to concerns the language $$ \\{ a^p : p \text{ is prime} \\} \cup \\{ w : |w| \text{ is even} \\} = \\{ a^p : p \text{ is an odd prime} \\} \cup \\{ w : |w| \text{ is even} \\}. $$ We can write this in the form $A \cup B$, where $A = \\{ a^p : p \text{ is an odd prime}\\}$ and $B = \\{ w : |w| \text{ is even}\\}$. Let $C = \\{ w : |w| \text{ is odd} \\}$. Applying the result above, we deduce that $A \cup B$ is non-regular (assuming we already know that $A$ is non-regular).
> 1 votes

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


# Question
Title: Is it possible for a Turing machine to halt without reading the complete input string?
Is it possible for a Turing machine to halt without reading the complete input string. Suppose there is a string "adc" preceded and succeeded by infinite number of blanks. Can a Turing machine halt after reading just "a" and never touching "dc" or any of the blanks. If yes, will this string be accepted or rejected?

# Answer
Nothing special happens if the Turing machine doesn't read the entire input. For example, the machine can halt immediately, without looking at the input at all. If the Turing machine halts at an accepting state, then the input is accepted. If it halts at a rejecting state, then the input is rejected. In this way you can construct a Turing machine that accepts all inputs or that rejects all inputs, in both cases without looking at the input string at all.

In your example, the machine accepts "adc" iff it accepts "a".
> 3 votes

---
Tags: turing-machines
---


# Question
Title: Guess the number from its different base representations
Given a set of numbers in different representations (we don't know the value of the base in which we are representing) of bases, find the original number (in decimal representation) if it exists or return no number exists.

**Constraints given**: $2\leq base \leq 36$, No. of numbers given in different representations is **N** $\le$ 100, Test Cases $\leq$200, time Limit 1sec

For example,

Here $T=1,N=3$,

$1001111$

$117$

$4F$

These all represent the same number, i.e **$(79)\_{10}$**. $(1001111)\_3$ = $(117)\_8$=$(4F)\_{16}$ Hence answer is $79$. Whereas if any of the above number is changed to any other except those (for eg. if (1001111) is changed to something else) then the answer would be "No such number exist".

Please suggest an Efficient way with a pseudo code/code.

# Answer
Let's start with a simple algorithm. Go over all possible interpretations of the first string (using all possible bases). For each such interpretation, go over the remaining string, and check whether they equal the interpretation of the first string for one of the possible bases. If there are $m$ possible bases and $n$ digits in total, then the running time is $O(m^2 n)$, ignoring the cost of arithmetic.

We can improve this as follows. Suppose for simplicity that all strings are at least two digits long (if not, we know the value of the number, and can finish in $O(nm)$ time). Compute all possible interpretations for each string, put all of these $nm$ numbers together, and sort them. Check whether the sorted list contain $n$ identical elements. This algorithm takes $O(nm \log (nm))$ time.

Another improvement, with a slightly better running time, modifies the original approach using binary search. Go over all possible interpretations of the first string. For each such interpretation, go over the remaining string, and for each one, use binary search (on the base) to find whether they equal the interpretation of the first string for one of the possible bases. This algorithm runs in $O(nm \log m)$ time.
> 1 votes

---
Tags: algorithms, discrete-mathematics, number-theory
---


# Question
Title: What is minimum cost perfect matching problem for general graph?
It does make sense when we talk about perfect matching in bipartite graphs because there are two sets of points, for example, one set may be jobs and other set may contain different machines. But when we talk about minimum cost perfect matching in general graphs, it is not making any sense for me, what are the nodes and edge cost representing, If you can give some real-life example depicting minimum cost perfect matching in general graphs. It will be very helpful to me.

Also, I need a precise definition of the minimum cost perfect matching problem. Thank You.

# Answer
The minimum cost perfect matching problem is formally defined as an optimization problem where:

* The set of instances is the set of all edge-weighted undirected graphs $G=(V, E, w)$, where $w : E \to \mathbb{R}$.
* Given an instance $G=(V, E, w)$, the set of feasible solutions are the perfect matchings $M$ of $G$, i.e., all the sets $M \subseteq E$ such that, $\forall u \in V \\; |M \cap \\{ (u, v) \in E : v \in V \\}| = 1$.
* Given an instance $G=(V, E, w)$ and a feasible solution $M$ for $G$, the is a function called *measure* defined as $m(G, M) = \sum\_{e \in M} w(e)$.
* The measure is to be minimized.

As for the problem making sense... the problem is abstract in nature and it can be perfectly well-defined without any need for vertices, edges, weights or the matching itself to represent anything.

Of course it is fairly easy to come up with (mock) scenarios in which you might want to compute a minimum cost perfect matching of a suitable graph that is modelling some real-world entities, e.g., the one that follows.

You are organizing a trip for a (large) group of $n=4k$, $k \in \mathbb{N}^+$, participants that will travel together on a bus with $n$ seats. Bus seats are arranged in rows of $4$, with $2$ adjacent seats on each side and a corridor in the middle. Not all of the participants enjoy their company equally (indeed, some of them categorically refuse to be close by) and you know, for each pair of people that can sit together, how much they'd happy (or unhappy) to be sat next to each other (say, in a scale from $-1$ to $1$). Being a thoughtful organizer, you want to arrange seats in order to maximize the social welfare of the participants, i.e., the sum of the happiness of all pairs of neighbors in the arrangement you choose.
> 3 votes

---
Tags: graphs
---


title: Compare log^k(n) with n^(1/2)

text:
# Question
Title: Compare log^k(n) with n^(1/2)
I'm trying to prove or disprove that $\log^{k}(n) \in O(\sqrt{n}), \ \forall k \> 0$. By using the free version of wolfram and testing some increasing values of $k$ I get that:

$$\lim\_{n \rightarrow \infty} \frac{\log^{k}(n)}{\sqrt{n}} = 0$$

And apparently $\log^{k}(n) \in O(\sqrt{n})$, but by trying to solve this limit on paper in order to reach an appropriate proof I would need to keep applying L'Hospital rule indefinitely. Is that what I suppose to be doing? How could I proceed to build this proof?

# Answer
> 2 votes
Yes. Using L'Hospital:

$\lim\_{n \rightarrow \infty} \frac{\ln^k (n)}{\sqrt n} = \lim \frac{k \ln^{k - 1} (n) \frac{1}{n}}{ \frac{1}{\sqrt n }} = \lim \frac{ k \sqrt n \ln^{k -1 } (n) }{ n } = \lim \frac{k \ln^{k-1} (n)}{\sqrt n} = \dots = \lim \frac{k \cdot (k -1) \cdots 2 \ln (n) }{ \sqrt n} = \lim \frac{k! \frac{1}{n}}{\frac{1}{\sqrt n}} = \lim \frac{k!}{\sqrt n} = 0$

I hope I got it right, quite some time since I've used it. I^ve left out the $\frac{1}{2}$ from the $\sqrt n$

---
Tags: complexity-theory, asymptotics, big-o-notation
---


title: How to show that A is not regular?

text:
# Question
Title: How to show that A is not regular?
Let Σ = {0, 1, ⊕, =} and define a language A as follows: A = {x = y ⊕ z | x, y, z are binary integers, and x is the XOR of y and z}. For example string “1011 = 1111 ⊕ 0100” is in A, whereas string “1011 = 1011 ⊕ 1011” is not

How can I show that A is not regular? How should I have the string?

Also, if the binary numbers are of fixed length, 64 bit long, would A then be regular or not?

# Answer
Any **regular language** upholds the **pumping lemma**. Hence, if a language doesn't uphold the pumping lemma, it is not a regular language. This is in fact the standard way of proving a language is not regular.

Let us choose $p$ to be the pumping length. Let's now take $0^n=1^n \oplus 1^n$, which is in $A$. This string can be decomposed into three concatenated substrings $xyz$. Since $|xy| \leq p$, we see that $v=0^k$ for some $k$ greater than 0. If we choose to pump it $i$ times, we will then obviously obtain an $x$ which is longer ($i \> 1$) or shorter ($i = 0$) than the other two operands and cannot then be the result of their XOR, hence proving that the language is not regular.

However, it may be that you forgot to add some clauses to the problem statement, since this seems quite trivial. *Edit*: my intention was not to point out that this is easy in general, the principle itself of the proof being rather non-trivial. However, some additional clauses, such as the strings having the same length would render this sensibly harder, and it may be what the problem had in mind.
> 2 votes

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


# Question
Title: I want to solve this question for algorithm, please
Write an algorithm that calculates the monthly payment of a bank loan with a fixed interest-rate. Given the principal amount, the fixed interest rate, the number of years to pay the loan, you can calculate the monthly payment as: ℎ =(××#+)/#ℎ Your program should print the required monthly payment of this loan

# Answer
> -4 votes
Here is working code. Don't forget to input your percentage in fractional form (e.g. $0.02$ for $2\\%$).

```
#include <stdio.h>

#define MONTHS_IN_YEAR 12

float monthlyRepaymentAmount(float principalAmount, float interestRate, int numberOfYears);

int main(void) {
    //Problem statement variables
    float principalAmount; // use int if principal can only be an integer
    float interestRate;
    int numberOfYears;

    //Ask user for problem statement variables
    printf("Please enter the principal amount of the loan: \n");
    scanf("%f", &principalAmount);
    if (principalAmount <= 0) return -1;

    printf("Please enter the interest rate: \n");
    scanf("%f", &interestRate);
    if (interestRate <= 0) return -1;

    printf("Please enter the number of years (term of the loan): \n");
    scanf("%d", &numberOfYears);
    if (numberOfYears <= 0) return -1;

    //Compute and output result
    printf("You need to make monthly loan repayments of $%f \n", \
        monthlyRepaymentAmount(principalAmount, interestRate, numberOfYears));

    return 0;
}

float monthlyRepaymentAmount(float principalAmount, float interestRate, int numberOfYears) {
    return (principalAmount * interestRate * numberOfYears \
            + principalAmount) / (numberOfYears * MONTHS_IN_YEAR);
}

```

---
Tags: algorithms, complexity-theory, formal-languages, computability, data-structures
---


title: $\epsilon$-transitions in NFAs

text:
# Question
Title: $\epsilon$-transitions in NFAs
I am reading "Introduction to the Theory of Computation" (2ed) by Michael Sipser. In Example 1.35, it says the NFA accepts $\epsilon$, which I understand, since the state can stay at $q\_1$ upon input of $\epsilon$:

But in Example 1.38, it shows to be an empty set for $q\_1$, $q\_3$, and $q\_4$:

I thought it should be $\delta(q\_1, \epsilon)=\\{q\_1\\}$ at least, for instance. I always assume there is an "implicit self-$\epsilon$-transition" at every state, but why it is $\emptyset$ now? I also noticed the lack of a "self-$\epsilon$-transition" in the proof of Theorem 1.45 (no staying at $q\_0$ upon the input of $\epsilon$). Have I missed something important?

# Answer
> 0 votes
I think you're making a good point. It's just that since an $\epsilon$-transition from a state to itself must always be there in some sense (we can read nothing from the input stream and stay in the same state) it's more economical to make the convention that **we don't consider such "transitions" to be transitions**.

---
Tags: automata
---


# Question
Title: Is monoid the category for untyped lambda calculus?
If cartesian closed categories are the model for simply typed lambda calculus, then can it be said that a monoid is a categorical model for untyped lambda calculus?

# Answer
> 3 votes
*$C$-monoids* and their variants is what you are looking for. You can find further references and an account of what is what in Martin Hyland's Towards a Notion of Lambda Monoid.

---
Tags: lambda-calculus, category-theory
---


# Question
Title: Prove, a^2+b^2=c^2,there exists only 1 case such that a,b,c are consecutive non negative integers(3,4,5)
I want to prove, $a^2+b^2=c^2$,there exists only 1 case such that a,b,c are consecutive non-negative integers(3,4,5).

I have no clue to prove this lemma. Please help me to prove this lemma.

# Answer
$n^2 + (n + 1)^2 = (n + 2)^2 \Rightarrow n^2 + n^2 + 2n + 1 = n^2 + 4n + 4 \Rightarrow 2n^2 2n + 1 = n^2 + 4n + 4 \Rightarrow n^2 - 2n - 3 = 0 \Rightarrow n = -1, 3$

Therefore, 3 is the only plausible solution.
> 5 votes

---
Tags: discrete-mathematics, number-theory
---


# Question
Title: Will a node with no incoming arc or no out coming arc affect the maximum flow?
So in a maximum flow question, say if we have a node which is not $s$ nor $t$, if it has no incoming arc, can we delete it without affecting the maximum flow? What if it has no output arc? How so?

# Answer
> 1 votes
Yes, you can. If it has, say, no outcoming edge, there can be no flow routed over this node. Otherwise the flow conservation constraint for this node ($v$) $$\sum\_{(u,v) \in E} f\_{uv} - \underbrace{\sum\_{(v,w) \in E} f\_{vw}}\_{= 0} = 0$$ is violated if you have incoming flow.

---
Tags: network-flow
---


# Question
Title: is it possible to find the maximal min cut in polynomial time?
A maximal minimum cut is a minimum capacity cut with the largest number of edges.

# Answer
> 1 votes
This problem is NP-hard if 0 weight is allowed. We can reduce Not-All-Equal 3SAT to the decision version of this problem.

Given an instance of Not-All-Equal 3SAT with $n$ variables and $m$ clauses, for each variable $x\_i$, we create two vertices $v\_i$ and $v\_i'$ with an edge between them for each variable. In addition, for each clause, for example, $x\_1\vee x\_2\vee \neg x\_3$, we add three edges among $v\_1,v\_2,v\_3'$ (thus they form a triangle). All edges have weight 0. Now we can see there is a minimum cut (in fact, every cut is a minimum cut) with at least $n+2m$ edges if and only if the Not-All-Equal 3SAT instance is satisfiable.

---
Tags: algorithms, network-flow, ford-fulkerson, minimum-cuts
---


title: Range Query with conditions

text:
# Question
Title: Range Query with conditions
Suppose I have an $N$ length integer array of pairs of the type $\[value, key\]$. Now, I need to query for range sum. Query is of the type : $l, N, x$ meaning I have to sum up all the $value$ in the index range $l$ to $N$ having key as $x$. Also, there can be updates that add a new pair to the end of the array increasing $N$. Succeeding queries consider the updated $N$. There can be multiple queries so I need to answer the query in $O(logN)$ but precomputation is allowed.

I think it might be done with a Segment Tree but I cannot see what to keep in the nodes. Is it even possible to do it with required complexity, because I feel you actually need to go to every element in the array to check it's key. Any help is appreciated.

# Answer
> 1 votes
Since there are no updates there is a rather simple solution. Store a map of key -\> array of pairs, such that for every element in your original vector (value, key) at position pos, you store in the vector associated with given key in the map the pair (position, value). Keep every vector sorted by position.

For example in the input array: $$\[(3, 1), (2, 3), (2, 5), (1, 6), (3, 3)\]$$ you would build the map:

```
{
    1 : {(4, 6)} // (value 6 at position 4)
    2 : {(2, 3), (3, 5)}
    3 : {(1, 1), (5, 3)}
}

```

Notice that with this data structure you can solve queries in vector by finding the sum in suffix. First find the corresponding vector in $O(log N)$ (possible in $O(1)$ if used unordered\_map instead of map) and use lower\_bound (also in $O(log N)$) to determine the target suffix. You should keep cumulative sums of the vector to calculate the sum on a suffix in $O(1)$.

---

To handle updates of the form add an element of the form (key, value) to the end of the original array you should only extend the vector corresponding with key in the map. You know the new position in the original array, which is greater than all previous position since it is at the end, so add the pair (new\_size, value) to the end of the array associated with given key.

Notice that we must keep cumulative sum up to date, but cumulative sum up to the first $n$ values is equal to the cumulative sum up to the first $n-1$ values plus the last value. The new cumulative sum can be computed in $O(1)$.

Notice that in practice we don't need to have on each vector in the map a pair of (position, value), but instead (position, cumulative\_sum).

# Answer
> 0 votes
Since you have specified that the array is unsorted, i am afraid you cant do a query in $O(logN)$, assuming we are talking about time complexity and not space complexity (but i think this is the case since you have expressed the desire to make the query efficient because there can be more than one). Keep in mind that (apart from a few exceptions which however do not help in ordering the type of array you have) the greater time complexity for sorting algorithms does not go under $O(n(logN))$, and that just for sorting the array.

---
Tags: algorithms, data-structures, search-trees
---


# Question
Title: Time complexity of linear iteration bounded by logarithmic iteration?
I was wondering about the time complexity of something like the following loop (where `work()` is `O(1)`):

```
for (i = 0 to N; i = i * 2) do
    for(j = 0 to i; j = j + 1) do
        work()
    end
end

```

The outer loop takes $\lg(N)$ steps, and the inner loop takes (on the final iteration) $N$ steps. So, a simple bound would be $O(N\lg(N))$. However, the inner loop doesn't fully reach $N$ until the last iteration, so I was wondering if the bound could be narrowed any further.

# Answer
Derp, nevermind. I observed that on the last iteration, the inner loop takes $N$ steps. On the previous iteration, the inner loop would take $\frac{N}{2}$ steps. Overall, this would take $N, \frac{N}{2}, \frac{N}{4}, \frac{N}{8},...$ steps, which has a geometric sum to $2N$ steps. Therefore, the loop is $O(N)$.
> 1 votes

---
Tags: algorithms, time-complexity
---


# Question
Title: Formal definition of an empty stack accepting PDA
PDA's are usually defined using the 7-tuple convention.

$M=(Q, \Sigma, \Gamma, \delta, q\_{0}, Z, F)$

F is the set of accepting states.

I want to design a PDA accepting by empty stack, so using this notation makes no sense, as I don't need F and I want to make the acceptance condition clear.

How is this usually done? Can I just dismiss F?

$M'=(Q, \Sigma, \Gamma, \delta, q\_{0}, Z)$

# Answer
> 1 votes
You don't need to remove $F$ from your definition, you just don't use it in the definition for the accepted words.

Let $(p, w, \beta) \in Q \times \Sigma^\* \times\Gamma^\*$ be the current full state description of the PDA, where $p$ is the current state, $w$ the yet unread input and $\beta$ the current stack. The accepted language $L(M)$ then is normally defined as

$$L(M) = \\{w \in \Sigma^\*\mid (q\_0, w, Z) \vdash^\* (q, \varepsilon, \beta), q \in F, \beta \in \Gamma^\*\\}$$

i.e. all words that, when completely read, result after zero or more steps of the machine in a state that is in the set of final states $F$. (Definitions also vary whether your stack is empty at start or initialized with a single symbol $Z$, and whether it should be empty when the final state is reached.)

For your modified PDA you can define an L' as follows:

$$L'(M) = \\{w \in \Sigma^\*\mid (q\_0, w, Z) \vdash^\* (q, w', \varepsilon), q \in Q, w' \in \Sigma^\*\\}$$

The most important changes here are that the language doesn't depend on $F$ anymore and that the condition for an accepted word is a series of machine steps that leads to an empty stack.

# Answer
> 1 votes
When the stack is finished you can go to the specified state which shows the empty stack. In addition, when you reach in a state which you found it's a solution but the stack is not empty, iterate over a "pop" action to empty the stack and finally go the empty stack state.

Hence, you can explain this PD using the defined notation.

---
Tags: pushdown-automata
---


# Question
Title: Example of a code that can be decoded using bounded distance decoder
In the book *Information theory, Inference and Learning Algorithm*, in chapter 13, MacKay defines bounded distance decoding

> A bounded distance decoder is a decoder that returns the closest codeword to a received binary vector $\mathbf{r}$ if the distance from $\mathbf{r}$ to that codeword is less than or equal to $t$; otherwise it returns a failure message.

Could anybody provide an example of a simple linear code that can be decoded by such a bounded distance decoder?

# Answer
> 0 votes
The simplest example is a repetition code. You encode the bit 0 as 000 and the bit 1 as 111. The decoder outputs the majority bit, which is always at distance at most $t = 1$.

As another example, suppose we encode 0 as 0000 and 1 as 1111. We can still correct up to one error (by taking the majority), but we cannot accommodate $t = 2$, since given 0011 we can't tell whether it came from 0000 or from 1111. Therefore we need to declare failure.

# Answer
> 0 votes
Any perfect code will do. A perfect code is a $t-$error correcting code where the spheres of Hamming radius $t$ around the codewords cover the whole space.

**Edit:** In response to OP's comment, if the $t-$spheres around codewords overlap, the code, by definition, is not a $t-$error correcting code.

In general, all decoding algorithms used in practice are bounded distance decoding algorithms, since except for very short lengths, it is not feasible to do a brute force comparison of the received word with all codewords.

The Syndrome decoding of a linear code is one such example, see any coding textbook, as well as Wikipedia entry here

---
Tags: coding-theory, error-correcting-codes
---


# Question
Title: Minimum sum of two numbers formed from digits of two arrays
Given two arrays of digits, both of size $n$, $2 \le n \le 9$, form two separate numbers $n\_1$ and $n\_2$, so the difference $n\_1 - n\_2$ is positive and minimal, if multiple solutions are possible the one with the smallest $n\_1$ is chosen.

Restrictions:

Time: 0.1 s (brute force ain't gonna do it)

Memory: 2 MB

# Answer
> 2 votes
This problem can be solved greedily. First remove all digits that are present in both arrays since they can be used as prefix of the number and we keep difference of high order digits as low as possible. Add them to the numbers from lower digits to higher digits in order to obtain smallest $n\_1$ at the end. Observation: after this process is done all remaining digits in both arrays are different (but this is not very relevant).

Brute force the next digit of $n\_1$, there are at most 9 possible digits that can be used for $n\_1$. Fix a digit $d$ not used yet in the first array. Once $d$ is fixed as the next digit of $n\_1$ use the largest digit lower than $d$ for $n\_2$ (if no such digit exists continue with next digit for $n\_1$).

After we have this prefix for $n\_1$ and $n\_2$ we already know that the inequality $n\_1 \> n\_2$ holds, whatever order we use for following digits. In order to minimize $n\_1 - n\_2$ we should order remaining digits from first array in such a way that $n\_1$ is minimized and order remaining digits from second array in such a way that $n\_2$ is maximized. For the first case we should add remaining digits of $n\_1$ in non-decreasing order, and for $n\_2$ in non-increasing order.

Next is the pseudo-code for the explained algorithm. Notice that $n\_1$ and $n\_2$ are treated as string, not like numbers, so addition means concatenation. Also, instead of dealing with array of digits as input, convert them to array of frequency, $F\_i(d)$ denotes how many times digit $d$ can be used for number $n\_i$.

```
F1 = Frequency of each digit in first array.
F2 = Frequency of each digit in first array.

n1 = ""
n2 = ""

# Remove common digits in both arrays
for d in [0..9]:
    while F1[d] > 0 and F2[d] > 0:
        n1 += d, n2 += d
        F1[d] -= 1, F2[d] -= 1

# Brute force next digit for number n1
for d1 in [1..9]:
    # Ignore digit if it is not available
    if F1[d1] == 0:
        continue

    d2 = None

    # Iterate backwards and find higher digit available for d2
    for d2_it in [d1 - 1..0]:
         if F2[d2_it] > 0:
             d2 = d2_it
             break

    # If there is no available next digit for n2 continue
    if d2 is None:
        continue

    tmp_n1 = n1 + d1
    tmp_n2 = n2 + d2

    # Add next digits greedily
    for d in [0..9]:
        for i in [0..F1[d]):
             tmp_n1 += d

    for d in [9..0]:
        for i in [0..F2[d]):
             tmp_n2 += d

    # Check difference of this pair
    # and keep better pair accordingly to problem restrictions.
    # This function will be called at most 9 times.
    report tmp_n1, tmp_n2

```

Notice that `report` will be called 0 times in case there is no valid answer.

---
Tags: algorithms, optimization
---


title: LL(k) language and not LL(k) grammar

text:
# Question
Title: LL(k) language and not LL(k) grammar
I have nonambiguous and not LL(k) grammar which defines some language. How can I prove that I can't build some LL(k) grammar for this language?

Grammar:

S -\> a b X c d | a X f

X -\> b X c | ε

# Answer
> 2 votes
You can prove by contradiction, assuming there is a value of $k$ that allows you to anticipate the sequence of derivations that is guaranteed to produce a unique tree for any input string, given some unambiguous grammar that accepts the language.

You then prove that there is a string for which a lookahead $\>k$ will be needed, no matter how the grammar is constructed, *because the derivation sequence is affected early in the process*. A strategy similar to the pumping lemma for context-free languages comes to mind.

Incidentally, your grammar is equivalent to the following LL(1) grammar:

$\begin{align} S &\to aT \\ T &\to f \mid bXcV \\ X &\to bXc \mid \epsilon \\ V &\to d \mid f \end{align}$

Perhaps a more interesting example would be

$\begin{align} S &\to T \mid U \mid V \\ T &\to aTb \mid \epsilon \\ U &\to aUc \mid \epsilon \\ V &\to dVc \mid \epsilon \end{align}$

whose language is both not $LL(k)$ and not $RR(k)$.

---
Tags: formal-grammars
---


# Question
Title: Find the error in the following “proof” that $O(n) = O(n^2)$
Let $f(n) = n^2 , g(n) = n$, and $h(n) = g(n)−f(n)$. It is clear that $h(n) ≤ g(n) ≤ f(n)$ for all $n ≥ 0$. Therefore, $f (n) = \max(f (n), h(n))$. Thus, $O(n) = O(g(n)) = O(f(n) + h(n)) = O(\max(f(n), h(n))) = O(f(n)) = O(n^2)$.

Can you explain why this statement is wrong?

# Answer
> 2 votes
You're basically claiming that $O(n^2+n-n^2)$ is the same thing as $O(n^2)$, and that's not true.

# Answer
> 2 votes
Depends on what you mean when you write $O(a(n)) = O(b(n))$.

Do you mean that the two set of functions are identical or are you using the (common) abuse of notation to mean $O(a(n)) \subseteq O(b(n))$?

In the former case this is wrong: $O(f(n) + h(n)) = O(\max(f(n), h(n)))$. Notice that the first term is $O(n)$ by definition of $h(n)$, while the second term is $O(n^2)$ since the maximum is always attained by $f(n)$. Clearly, the sets of functions $O(n)$ and $O(n^2)$ do not coincide. For example $n^{3/2} \not\in O(f(n) + h(n))$ but $n^{3/2} \in O(\max(f(n), h(n)))$.

In the second case nothing is wrong. In fact, it is true that $O(n) \subseteq O(n^2)$.

Let $d(n) \in O(n)$ and notice that, by definition of $O(\cdot)$, there exist two constants $n\_0 \ge 1$ and $c \> 0 $ such that $\forall n \ge n\_0$, $d(n) \le c n$. But then $d(n) \le c n \le c n^2$, showing that $d(n) \in O(n^2)$.

# Answer
> 1 votes
Because $h(n)$ is negative, as soon as $n\geq 2$ your argument does not work. Complexities are supposed to be nonnegative and $a(n)=O(b(n))$ requires $a(n)\leq cb(n)$ where $c\>0$ is a constant.

---
Tags: big-o-notation
---


# Question
Title: Recursive algorithm for finding a common ancestor between two nodes in a tree, if it exists?
Here's the start and the vernacular I'm using.

```
# in class Scene
@staticmethod
def common_ancestor(item1, item2):
    if item1 is item2:
        return item1
    com = Scene.common_ancestor(item1.parentItem(), item2)
    if com is None:
        com = Scene.common_ancestor(item1, item2.parentItem())
    return com

```

Anyway, confusion sets in quickly with this one. Any ideas how to proceed logically?

Steven's idea in the comments:

```
# in class Scene
@staticmethod
def is_ancestor_of(anc, item):
    if anc is None:
        return True
    if item is None:
        return False
    if item is anc:
        return True
    return Scene.is_ancestor_of(anc, item.parentItem())

@staticmethod
def common_ancestor(item1, item2):
    if Scene.is_ancestor_of(item1, item2):
        return item1
    if Scene.is_ancestor_of(item2, item1):
        return item2
    return Scene.common_ancestor(item1.parentItem(), item2.parentItem())

```

# Answer
> 1 votes
The algorithm in the (edited) answer has worst-case quadratic time complexity. (An worst-case example is a tree where there are just two strands and the given nodes are the two leaves.)

A (non-recursive) $O(n)$ time and $O(1)$ space algorithm, assuming that nodes have parent pointers:

1. Compute the height of both target nodes.
2. Until the heights are equal, replace the deeper node with its parent.
3. Until the two nodes are the same, replace both nodes with their respective parent.

The time complexity of this solution is actually $O(h)$ where $h$ is the maximum height of the tree; by the same token, the time complexity of the solution in the question is $O(h)^2$. If the tree is known to be (somewhat) balanced, then $h = O(\log n)$. Even so, $O(\log n)$ is probably better than $O((\log n)^2)$.

---
Tags: algorithms, graphs, trees
---


title: Typesetting LTL in Unicode?

text:
# Question
Title: Typesetting LTL in Unicode?
Unicode has an abundance of open circles, diamonds and boxes. Using these, we can typeset linear-time temporal logic formulas such as

$$ (\mathop{⬦}ψ)\ \\,\land\ \\,\mathop{⬦}(θ\ \mathsf{U}\ \mathop{◻}\mathop{○}φ)\ \ . $$

However, in my browser, the sizes of the symbols vary too much; the heights don't match, and the result looks ugly. The same happens in LaTeX (though, you could fiddle with sizes there manually in some circumstances, but it's a mess). Are there any "proper" Unicode codepoints made specifically for typesetting LTL formulas? I failed to find any, but, maybe, I have not looked everywhere. As the pre-Unicode LTL standard take a look into the papers and books by Manna/Pnueli, e.g., http://theory.stanford.edu/~zm/tvors3.html .

Crosspost: http://latex.org/forum/viewtopic.php?f=46&t=32886

# Answer
I don't know if there is a correct or recommended usage of Unicode codepoints for the LTL operators, but the mapping we used in LaTeX was the following:

```
□ (U+25A1) => \Box
◇ (U+25C7) => \Diamond
○ (U+25CB) => \medcirc (from txfonts/pxfonts)

```
> 2 votes

# Answer
(This may be slightly off-topic here.) Manna & Pnueli typeset their books in (La)TeX using the font ZMSY10. Here's the head of the metafont file zmsy10.mf that I'm hesitant to publish in full because I'm unsure about its copyright situation:

```
% Font parameters

% This is the font ZMSY10, containing special symbols used by Zohar Manna.
% It has been worked on by several people, notably:
%
%   Frank Yellin, who converted it from old MF to new MF;
%   Eric Muller, who added various symbols;
%   Joe Weening, who added more symbols, modified some existing ones,
%   and cleaned up various things.
%   Eric Muller, who added some more symbol and tried to convert the thing
%       to use Metafont 2.0. Added Min{C,B,D}.

% Last modified on Wed Nov  6 14:36:40 PST 1991 by muller

```

Perhaps you can find it somewhere else on the net.
> 0 votes

---
Tags: terminology, notation
---


# Question
Title: How to Implement a reversible OR operator with a Fredkin gate (controlled swap)?
How to implement a reversible **OR** operator with a *Fredkin gate* ?

# Answer
As also stated in the relevant Wikipedia page, you can do it by using the first two inputs (the control-bit and one of the target bits) as input for the reversible OR, and the third input bit fixed with the value 1. Then, the second output is what you want.

To better see this, write the general action of a Fredkin on an input as following: $$\begin{pmatrix}a\\b\\ c\end{pmatrix}\mapsto \begin{pmatrix} a \\ (a c)\oplus\[(1\oplus a)b\] \\ (a b)\oplus\[(1\oplus a)c\] \end{pmatrix}.$$ Note that this is just rewriting the action of the Fredkin algebraically.

Then, if you use as input $(a,b,1)$, you get

$$\begin{pmatrix}a\\b\\ 1\end{pmatrix}\mapsto \begin{pmatrix} a \\ a\oplus\[(1\oplus a)b\] \\ (a b)\oplus(1\oplus a) \end{pmatrix},$$ which is what you want as soon as you notice that $a \oplus b\oplus ab=a\\,\operatorname{OR}\\, b$.
> 2 votes

---
Tags: logic, reversible-computing
---


title: Recurrence Problem T(n) = 3T(n/3) + n

text:
# Question
Title: Recurrence Problem T(n) = 3T(n/3) + n
I am trying to get better at solving recurrence relations, so I am making my own simple relations and try to solve them. I have made the following recurrence: $$T(n) = 3T(\frac{n}{3}) + n$$

How can I solve $T(n) = 3T(\frac{n}{3}) + n$ using unfolding when $T(1) = 1$ ?

# Answer
> 1 votes
Using master theorem you can say it is $\Theta(n\log n)$. Also, try to expand the relation: $$T(n) = 3(3T(\frac{n}{3^2}) + \frac{n}{3}) + n = 3^2 T(\frac{n}{3^2}) + 2n$$ If you continue the above expansion, you will get that $T(n) \sim n\log\_3(n) = \Theta(n\log(n))$.

---
Tags: recurrence-relation
---


# Question
Title: I want to design a context free grammar for the following
This below language

$$L = \\{ w \in \\{a, b\\}^n : \lvert w\rvert \text{ mod } 3 = 0 \\}$$ where $n \geq0$.

# Answer
Since this seems very much like homework, i will give you a little Hint, taking as example a sub-case of your language:

The ***GFC*** for the string $a^3b^3$ is the following:

$S ⇒ aSb$

$aSb ⇒ aaSbb$

$aaSbb ⇒ aaaSbbb$

$aaaSbbb ⇒ aaabbb$

You can take the above as a starting point from which to adapt the grammar to your case.
> 0 votes

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


# Question
Title: An underestimated tradeoff between Memory and the Effectivity of Computation?
Is there a theorem / single formula, that describes the often necessary **tradeoff between memoiziation** (for example that of a certain variable x) and **effective computation** as written in any common form such as runtime?

(A good purely theoretical startig point to work with could really be a number sequence...)

# Answer
I'm not sure I understand your question entirely, but I'm going to assume that you're talking about the **space-time tradeoff**. The gist of the aforementioned tradeoff is as you put it, in the context of an algorithm, the balance you have to strike between the memory it will use (its **space complexity**) and the time it will take to run (its **time complexity**). Obviously, the faster you want it to run, the more memory you will need to use, and vice-versa. The tradeoff is in general present in most fields of computer science besides pure algorithm design, but this provides I believe a nice abstract starting point.

Let's start with the bad news: from a rigid theoretical computer science point of view, tough luck, no such unifying formula exists and it is actually a fairly well-known open problem (for more info you may want to check this question about the space-time tradeoff, but it is fairly technical). Even worse, few general results are known about this.

Now the good news, of which there are two. First of all, I highly encourage you to think about the problem yourself and come up with your own (even incomplete theory), as it isn't very hard to qualitatively come up with some pretty interesting remarks.

For instance, let us try to develop a (very!) basic theory here. At its core, a result to be obtained through computation can be decomposed into a bunch of dependencies and operations. For instance, to compute `c=a+b`, you need to know a and b (the dependencies, also known as operands), and add them together (the operation). This decomposition can be applied iteratively many times until all of the dependencies are directly known (present in the problem instance/the input you receive). There are many ways of looking at this, one of them is as a **DFG** (Data Flow Graph), but there are of course many more with varying degrees of complexity, which each offer accuracy for different factors. For convenience, have this nice picture of a DFG:

Abstracting the compute cost of one operation to 1 (no matter its complexity or the number of operands), we can see that the lower time bound to obtain the value of a node of the DFG is equal to the length of the longest path from the node to an input operand. Indeed, if we assume entirely parallel computation (possible if no interdependencies exist between nodes at the same depth), this bound can be attained. If we would however assume entirely serial computation, we would need to add the cost of obtaining each result one by one and I choose not complicate myself with this here. If we add memoization, this time becomes the length of the longest path from the node to a memoized operand (but we stop when we reach the first one on a given path backwards from the target node).

This sounds suspiciously simple, right? If we know the DFG beforehand and we assume parallelism, it indeed isn't very complicated, but a few avenues of thought would be if we consider as mentioned serial (or partly serial execution) and then memoization strategy.

I'll just point out that while it's not what you're looking for, for practical purposes it's always a good idea to benchmark on real hardware as well.

Now since I mentioned that there are two good news: there are bounds on this tradeoff which have been found and proven for specific problems and computation models. If you're interested, you can find some of these purely theoretical results in this answer.
> 1 votes

# Answer
To more generally answer @DavidChian,

Thank you very much, especially for cheering me up a bit. Now, if I understood your post right, you say, that there isn't a general way, but you still gave the following starting point: instead of my proposed number sequence, you choose a Data Flow Graph (DFG). Using your model, where the most effective space-time tradeoff for like n computations defined for specific variables and operands, such as simplicity-wise 0 Interdependencies (guaranteed for by mere sequential computations / iterations like: x2 = x1 + 1 instead of like: Find me the meaning of everything :-) ), would possibly be calculated by something like this:
Cost C(Compute) of completing some defined computation Cost C(Memorize) of saving and reopening some defined memory address (which always is a variable with some states (numerically like f. e. x = 3.14…) Then for C(c) = C(m) the cost of both memorization and that of direct computation are equal, because their functions cross each other. Is it now possible that the biggest problem remaining is that of (a) parallel processing and (b) the cost of the meta-optimization we just did, that will always (due to the halting problem) be \> the cost of the computation itself!?
> 0 votes

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


# Question
Title: Finding a Hamiltonian path in this graph family
Given a directed graph $G = (V, E)$, you have been told that a Hamiltonian path $p\_0p\_1\ldots p\_V$ exists with the property that for each edge $p\_ip\_j$ that is not part of the Hamiltonian path, $i \> j$.

Find any Hamiltonian path.

It is not too hard to find an $O(|V||E|)$ solution to this problem: for every vertex with out-degree one, try starting a BFS from this vertex. If ever there is more than one vertex that could be expanded next in the BFS, give up and try another vertex.

I am not necessarily looking for a more efficient solution than this (though that would be nice), but I'm having trouble finding literature on this type of graph (in general, it seems very hard to look up literature on a family of graphs you do not know the name of).

Do you know where I can find out more about this graph family, or other graph families that involve guaranteeing the existence of a Hamiltonian path/cycle with interesting properties?

# Answer
> 2 votes
The class of graphs that contain a Hamiltonian cycle is known as *Hamiltonian graphs*. Being Hamiltonian doesn't really imply much: a wide range of well-known graph parameters (diameter, treewidth, chromatic number, ...) can still be unbounded. At least partly, this is the reason there aren't many non-trivial subclasses of Hamiltonian graphs known.

As an example, every 2-connected $(P\_6,K\_{1,3})$-free graph is Hamiltonian (see e.g., \[1\]). Further, \[1\] also cites some conjectures which claim that every 2-tough graph is Hamiltonian, or that every 4-connected $K\_{1,3}$-free graph is Hamiltonian.

On the algorithmic side, even recognizing Hamiltonian graphs is of course well-known to be NP-complete. That is, *recognition* means the problem of deciding whether a given graph is Hamiltonian or not. Also, because many structural parameters remain unbounded, many classical problems also remain hard for Hamiltonian graphs (as there is no clear algorithmic foothold to exploit).

You might also enjoy Hypohamiltonian graphs, which are "almost Hamiltonian".

---

\[1\] R. Faudree, E. Flandrin, Z. Ryjacek. Claw-free graphs - a survey. Discrete Math. 164 87-147 (1997)

# Answer
> -1 votes
"*I'm having trouble finding literature on this type of graph*"

A good book recommended by universities is **Discrete Mathematics and It's Applications by Kenneth H. Rosen**. You can find the chapter on graphs (Euler and Hamilton paths) on page 666.

---
Tags: graphs, hamiltonian-path
---