# Question
Title: What is the name of the following binary encoding?
S is a the set of binary strings in Shortlex order: `[0,1,00,01,10,11,...]`

I want to encode / decode natural numbers with the following scheme:

Encoding N: For natural number N return the binary string with index N in S: `Code(N)=S[N]`

Decoding Code: Return the index of the binary string Code in S: `Decode(11)=5`

Can you please suggest the name of this encoding and how to implement it?

Example of Numbers and Codes:

```
Number | Code
0  | 0
1  | 1
2  | 00
3  | 01
4  | 10
5  | 11
6  | 000
7  | 001
8  | 010
9  | 011
10 | 100
11 | 101
12 | 110
13 | 111

```

# Answer
> 8 votes
Your encoding is not self-terminating, which makes it somewhat less useful than encodings such as universal codes.

Given an integer $n \geq 0$, write $n+2$ in binary without leading zeroes, and remove the MSB to get your encoding. In the other direction, add a leading one, and subtract $2$.

If you also allow the empty string, and you are only interested in encoding integers $n \geq 1$, then there is no need to add or subtract $2$ in the above recipe.

# Answer
> 2 votes
That's essentially bijective base 2. The only differences are that the set of digits used is $\\{0, 1\\}$ instead of $\\{1, 2\\}$, and that in the sequence of codes, the empty string is skipped.

As others have already suggested, you can encode a number by adding 2, writing it in binary, and removing the leading 1; and you can decode a number by adding a leading 1, decoding the result as binary, and then subtracting 2.

# Answer
> 1 votes
I don't know the name of this encoding, but notice that with $k$ digits you'll be able to encode exactly $2^k$ numbers. In particular, those starting from: $ \sum\_{i=1}^{k-1} 2^i =2^{k}-2. $

It follows that, given an integer $n$, the number of digits of the encoding can be found as the largest value of $k$ such that $2^k \le n+2$, i.e., $k=\lfloor \log\_2 (n+2) \rfloor$. Notice that $k$ is exactly one less than the number of digits needed to write $n+2$ in binary, so you can find it in time $O(\log n)$.

Then, you can also write down the actual digits in time $O(k)=O(\log n)$ by looking at the binary representation of $n-(2^k-2) = n-2^k+2$.

As an example, the encoding of $42$ consists of $k=\lfloor \log\_2 (44) \rfloor = 5$ digits (since $2^5=32$ and $2^6=64$). These digits are $01100$ (notice the leading $0$) since $(42-32+2)\_{10} = (12)\_{10} = (1100)\_2$.

---

To decode a number, you can do the reverse: count the number $k$ of digits in the encoded version, then add together $2^{k}-2$ and the number whose binary representation corresponds to the given digits. This also requires $O(k)=O(\log n)$ time.

For example, the encoded number $01100$ has $5$ digits, so the represented integer is $(2^5 -2)\_{10} + (01100)\_2 = (30 + 12 )\_{10} =(42)\_{10}$.

# Answer
> 0 votes
From shortlex to natural:

* add $(10\_b)^l-10\_b$ to the binary value, where $l$ stands for the length (number of bits).

E.g. $011\_s\to l=3\to11\_b+1000\_b-10\_b=1001\_b=9$.

From natural to shortlex:

* the length is $l=\lfloor\log\_2(n+2)\rfloor$,
* subtract $2^l-2$,
* fill left with zeroes.

E.g. $9\to l=\lfloor\log\_2(11\_d)\rfloor=3\to9-2^3+2=3=11\_b\to011\_s$

---
Tags: strings, information-theory, coding-theory, encoding-scheme
---


# Question
Title: Difficulty understanding how federation increases cache performance for databases?
I am studying system design for distributed systems and in this page (https://github.com/donnemartin/system-design-primer), one of the following advantages was mentioned for federation for databases was:

> Smaller databases result in more data that can fit in memory, which in turn results in more cache hits due to improved cache locality.

What I don't understand is why would smaller databases have more memory? Furthermore, how does federation improve cache locality and result in more cache hits?

# Answer
It's not smaller databases have more memory - it's about size of a data set.

Let's say we have a data set of 100G and we have a cache of 10G - assuming completely random access to data, we have 1/10 probability of reading data from the memory cache vs reading it all the way from a storage.

What if we take our 100G and shard (e.g. using hash of a key) it to two nodes of 50G each? In that case, the probability of fining the data in the cache on every node is 10/50-\> 1/5 - twice better than before.

Can we do our system even faster? Let's have 10 nodes! Now every node has just 10G of data and 10G of memory - we can read all data from the memory - making it fast.
> 1 votes

---
Tags: computer-architecture, distributed-systems, high-performance-computing
---


title: What is an API, exactly

text:
# Question
Title: What is an API, exactly
I’ve read the Wikipedia article and know it’s basic function but I don’t understand what it physically is. Like, is an api a text file that the main program reads from and you are just putting your text in that file to be read or is it an other program that just puts what you type directly into the main program? I don’t understand. Maybe what I’m really asking is what is the actual process that allows an api to take an executable with no way to input information and allows you the programmer to input information.

# Answer
API is a contract between two systems. Nothing more, nothing less.

The key question is why do you need api? Api's allow decoupling systems and modelling interaction between them. Here are few examples:

A file system has a set of APIs to manage files and directories. One of those apis is "touch a file" which "updates timestamp on the file". As a customer of that api, you don't need to know how timestamp is stored and how the actual update is happening - all you need to know - there is a contract.

Another example would be a database. When you tell database to commit a transaction, the database guarantees certain properties, like data durability.

Basically API allows simpler modelling of systems.

I highly recommend to lookup on youtube a video: "How To Design A Good API and Why it Matters". It is a very old talk from google. It gives you a perspective on what is api and when an api is a good one.
> 2 votes

---
Tags: programming-languages, api-design
---


# Question
Title: expected running time of Randomwalk for k-SAT
## model: gambler ruin theorem.

A gambler has $i$ coins initially, in every step, he wins a coin with probability $p$, and loses a coin with probability $1-p$. The expected time that he loses all his coins or wins $n-i$ coins (thus he has $n$ coins totally) is as following: $$E(i)=-\frac{n}{1-2p}\frac{(\frac{1-p}{p})^i-1}{\frac{1-p}{p})^n-1}+\frac{i}{1-2p}$$ this result is from p272 of https://www.emis.de/journals/AMEN/2018/AMEN-171010.pdf

## K-SAT problem

https://cstheory.stackexchange.com/questions/1196/what-is-the-k-sat-problem

Assume that there are $n$ variables in K-SAT.

I use $X=(x\_i, x\_2, \dots x\_n)$ to denote the candidate solution of K-SAT.

$X$ is a vector of $n$ dimensions.

$x\_i=1$ means the i-th variable is true, $x\_i=0$ means the i-th variable is false.

## The algorithm:

## Apply gambler ruin theorem to analysis

Assuming there is a unique solution $X^\*$, and the initial solution $X$ generated by the algorithm has the same $i$ bits with the unique solution $X^\*$.

Apparently, when $i$ becomes $0$ or $n$, the algorithm will stopped, and I want to calculate the expected iterations of the algorithm before it stop.

In each iteration, the same bits can be decrease or increase by 1.

and the probability of increase by 1 is at least $p=1/k$. (Because it's k-sat, in each unsatisfied clause, there are at least one variables that doesn't match $X^\*$)

The number of same bits between $X^\*$ and$X$ incrases by 1, corresponding to the gambler wins a coin. And decreasing by 1 corresponding to the gambler lose a coin.

Thus I think I can use $$E(i)=-\frac{n}{1-2p}\frac{(\frac{1-p}{p})^i-1}{\frac{1-p}{p})^n-1}+\frac{i}{1-2p}$$ to calculate the expected runtime.

**but the expected run time is O(n), which is impossible for k-sat problem.**

My question is , **where am i wrong?**

# Answer
> 2 votes
The probability that step 4 brings $X$ closer to the unique satisfying assignment is not $1/k$. Rather, it is *at least* $1/k$. When $X$ is far away from a satisfying assignment, the probability is likely to be significantly larger. This makes it quite unlikely that you will ever get to a situation in which $Y$ is close to the unique satisfying assignment.

As a concrete illustration, consider the 2CNF containing all $\binom{n}{2}$ clauses of the form $x\_i \lor x\_j$ and all $2\binom{n}{2}$ clauses of the form $x\_i \lor \bar{x}\_j$. The only satisfying assignment has all variables positive. Suppose that the current assignment $X$ contains $d$ negative variables. There are $\binom{n}{2} - \binom{n-d}{2}$ unsatisfied clauses, one for each pair of variables, not both of which are positive. In $\binom{d}{2}$ of them, both literals are false, and in $d(n-d)$, one literal is false. Therefore, the probability that we flip a negative variable is $$ \frac{\binom{d}{2} \cdot 1 + d(n-d) \cdot \frac{1}{2}}{\binom{d}{2} + d(n-d)} = \frac{n-1}{2n-d-1} = \frac{1}{2} + \frac{d-1}{2(2n-d-1)}. $$ When $d$ is linear in $n$, this probability is larger than $1/2$ by a constant.

If we repeat the same calculation for $k$CNFs (we have all clause of width $k$ in which at least one variable is positive), the value of $p$ that we get is $$ \frac{\frac{1}{k} \sum\_{\ell=1}^k \binom{d}{\ell} \binom{n-d}{k-\ell} \ell}{\sum\_{\ell=1}^k \binom{d}{\ell} \binom{n-d}{k-\ell}} = \frac{\frac{d}{k} \sum\_{\ell=1}^k \binom{d-1}{\ell-1} \binom{n-d}{k-\ell}}{\sum\_{\ell=1}^k \frac{d}{\ell} \binom{d-1}{\ell-1} \binom{n-d}{k-\ell}} = \frac{\frac{1}{k} \binom{n-1}{k-1}}{\binom{n-1}{k-1} + \sum\_{\ell=2}^k \frac{1}{\ell} \binom{d-1}{\ell-1} \binom{n-d}{k-\ell}}. $$ This expression shows that when $d$ is small, the probability is indeed close to $1/k$. On the other hand, another expression is $$ \frac{\frac{d}{k} \binom{n-1}{k-1}}{\binom{n}{k} - \binom{n-d}{k}} = \frac{\frac{d}{n} \binom{n}{k}}{\binom{n}{k} - \binom{n-d}{k}} \approx \frac{d}{n} \frac{n^k}{n^k - (n-d)^k} = \frac{d}{n} \frac{1}{1 - (1-d/n)^k}. $$ When $d \approx \alpha n$ for $\alpha$ satisfying $\alpha/(1-\alpha^k) = 1/2$ (for example, when $k = 3$, we get $\alpha \approx 0.45$), $p$ crosses $1/2$, and so the algorithm will start improving the solution in expectation. Consequently, $X$ is unlikely to have more than $0.46n$ many negative variables.

---

When analyzing Schöning's algorithm, we keep track of the distance of $X$ from a fixed satisfying assignment. In the analysis, we say that the behavior of $X$ *stochastically dominates* a biased random walk with constant $p = 1/k$. This means that $X$ behaves *better* than such a random walk, and so if we show that a $1/k$-biased random walk hits its target with some probability $q$, then it follows that the actual algorithm also finds a satisfying assignment with probability $q$.

---
Tags: complexity-theory, time-complexity, runtime-analysis, satisfiability, random-walks
---


# Question
Title: Is there an O(m (log n+ log m))-time algorithm that finds k-th smallest element in a row-wise-sorted two dimensional array?
I prepare for entrance exam and try to practice some hard problems.

The following nice problem is problem 1(c) of this problem set.

> Suppose we are given a two-dimensional array $A\[1...m\]\[1...n\]$ in which every row $A\[i\]\[\]$ is sorted, and an integer $k$. Describe an algorithm to find the $k$-th smallest element in $A$ as quickly as possible. How does the running time of your algorithm depend on $m$?

I googled the answer that says that there is one algorithm that can solve this problem in $O(m (\log n+ \log m))$ time. Is it possible? Is there any idea?

I found an answer by *Yuval Filmus*. But I couldn't understand it. Is it related or not? It is so hard to understand it as a general algorithm. Since the goal of this site is to provide good material to learn from others, I would like to ask for more general and easier pseudocode or hint that help understand that answer.

# Answer
> -1 votes
It is certainly possible in time complexion O(m + k * log(m)). So it definetly is doable in O(m * (log n + log m)). One way would be to complete the calculation and then wait the appropriate amount of time. I don't know how one would do it in exactly that time without waiting.

From the linked PDF:

> Finally, suppose we are given a two dimensional array A\[1 . . . m\]\[1 . . . n\] in which every row A\[i\]\[\] is sorted, and an integer k. Describe an algorithm to find the k th smallest element in A as quickly as possible. How does the running time of your algorithm depend on m?

## Update

With the sorted rows we can do this: First build a heap of the smallest element in each array (storing the index of the array too). Building a heap of size m is O(m).

Then, repeat k times: Take an element from the heap (O (log m)) and insert the next smallest element from the array the element you took was from (O(log m)).

The number taken at iteration k is the k smallest number

Overall, this is O(m + k * log(m)) Of course if k is close to (n\*m) this algorithm should be flipped

### NOTE, this is wrong or at least seems wrong

~~It is possible to sort a matrix in O(n√nlog√n) \[1\]\[1\] (External link).~~

YvesDaoust has rightfully pointed out that sorting n² objects should not be possible in less than O(n² log(n²)) while there are sorting algorithms that are "faster" this is objection is generally correct.

Given that your matrix is already sorted around one axis I am not entirely certain how this will improve performance but thats not even necessary.

To find your solution from that we need O(log n)  or O(k log k)  (Both SO links)

Because of Big O rules of summation O(log n) + O(n√nlog√n) = max (O(log n) + O(n√nlog√n)) = O(n√nlog√n) which is even smaller than the result you found.

The problem with Big O notation is, that we are don't know the prefactor or any additional cost, which in this case include the entirety of the searching algorithm (lol)

---
Tags: algorithms, time-complexity, data-structures, sorting, search-algorithms
---


# Question
Title: How to identify Context-Sensitive Grammar?
Context-Sensitive Grammar is defined as a 4 tuple G = (V, Σ, R, S) where:

V is a finite set of elements known as variables.

Σ is a finite set of elements known as terminals

V ∩ Σ = Null (empty set)

S is an element of V and is known as the start variable.

R is a fine set of elements known as Production Rules. Each rule is like aAb -\> ayb where A is in V, a and b is in (V union Σ) and y is in (V union Σ)+.

The following is an example of this type of grammar that I found a lot in the literature.

1. $s \to abc|aAbc$
2. $Ab \to bA$
3. $Ac \to Bbcc$
4. $bB \to Bb$
5. $aB \to aa | aaA$

my question is: how this example could be of this type if there is no context for production 4 and 2?

# Answer
You are right: the grammar in your example is strictly speaking not context-sensitive. It is a monotonic (or non-contracting) grammar. In those grammars the main restriction is that the lefthand side of a production rule cannot be longer than the righthand side.

> A grammar is *monotonic* if its productions are of the form $\alpha \to \beta$ with $1\le |\alpha| \le |\beta|$. (Some sources require $\alpha$ to have at least one terminal symbol.)
>
> A grammar is *context-sensitive* if its productions are of the form $\alpha A \beta \to \alpha \gamma \beta$, with $A$ a nonterminal symbol and $|\gamma| \ge 1$. (This is basically a context-free production $A \to \gamma$ which is only allowed in context $\alpha A \beta$. )

The two grammar types are equivalent. First, every context-sensitive grammar is also monotonic. Conversely, it seems to be hard to construct a context-sensitive grammar from scratch, but there is a simple algorithm to convert from monotonic to context-sensitive. Therefore most people are using the terminology alternately.

For an example of this conversion, see the detailed answer by John L which constructs a monotonous grammar for $\\{x\\#x^R\\#x\mid x\in\\{a,b\\}^∗\\}$ and from there a context-sensitive grammar for the same language using the standard technique.

Note the length restriction is essential. If we are allowed to shorthen the string, then we obtain the type-0 (or unrestricted) grammar.
> 4 votes

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


# Question
Title: Proving a predicate assignment is correct
I am currently reading Formal Methods - An Appetizer and am stuck in chapter 3 (Program Verification).

I am unfamiliar with logic and I do not think I understand the $\vDash$ notation correctly.

---

I tried to work through Definition 3.8 by giving myself a super-simple example:

Let there be an edge $(q\_1, \texttt{y:=1}, q\_2)$ and a predicate assignment that is given by $P(q\_1)=(\texttt{x}=\underline{n})\land(\underline{n}\>0)$.

How do I now prove in the sense of Definition 3.8 that the predicate assignment is correct given $\mathcal{S}\[\\!\[\texttt{y:=1}\]\\!\](\sigma)=\sigma\[\texttt{y}\mapsto 1\]$ (which means the memory is updated so that $\texttt{y}$ now has value 1)?

I do not even know how to start.

What does it mean to have "suitable pairs of memory"?

Further, I already get stuck finding out whether $(\sigma,\underline{\sigma})\vDash P(q\_1)$. I think what I am supposed to do is

$$\begin{align\*}&(\sigma,\underline{\sigma})\vDash P(q\_1)\\ =\quad &(\sigma,\underline{\sigma})\vDash (\texttt{x}=\underline{n})\land(\underline{n}\>0)\\ =\quad &\left(\\,(\sigma,\underline{\sigma})\vDash (\texttt{x}=\underline{n})\\,\right)\land\left(\\,(\sigma,\underline{\sigma})\vDash(\underline{n}\>0\\,\right)\\ \end{align\*}$$

and then first do

$$\begin{align\*}&(\sigma,\underline{\sigma})\vDash (\texttt{x}=\underline{n})\\ =\quad &\[\\!\[\texttt{x}\]\\!\](\sigma,\underline{\sigma})=\[\\!\[\underline{n}\]\\!\](\sigma,\underline{\sigma})\end{align\*}$$

and this is where I am stuck... now, $\[\\!\[\texttt{x}\]\\!\](\sigma,\underline{\sigma})$ is $\sigma(x)$ by definition, that is, the value of $\texttt{x}$ in the memory $\sigma$, and $\[\\!\[\underline{n}\]\\!\](\sigma,\underline{\sigma})$ is $\underline{\sigma}(\underline{n})$, but I never specified which values are in $\sigma$ and $\underline{\sigma}$.

And rightfully so, I think, because I want to prove it for all "suitable" memories. How do I proceed here?

Any help would be greatly appreciated!

---

These are the relevant parts from the book in order to provide (hopefully) enough context.

as well as

# Answer
## What does it mean to have "suitable pairs of memory"?

In the case of the Definition 3.8 it means exactly any pair that **makes** $(\sigma,\underline{\sigma})\vDash P(q\_1)$ true. If it's not true then the whole premise of implication in the Definition 3.8 is false and from false anything goes thus the predicate $P$ is vacuously correct. That's a boring case so we're only interested in $(\sigma,\underline{\sigma})$ that indeed validates the predicate, which means we have some *constrains* regarding the sigmas.

In your examples constrains are straightforward, they are precisely where you stopped: $\[\\!\[\texttt{x}\]\\!\](\sigma,\underline{\sigma})=\[\\!\[\underline{n}\]\\!\](\sigma,\underline{\sigma})$ meaning $\sigma(\texttt{x}) = \underline{\sigma}(\underline{n})$.

The next step is to show $(\sigma',\underline{\sigma})\vDash P(q\_2)$ given $\sigma' = \mathcal{S}\[\\!\[\texttt{y:=1}\]\\!\](\sigma)$ and $\sigma(\texttt{x}) = \underline{\sigma}(\underline{n})$. Simplifying this gives us $\sigma' = \sigma\[\texttt{x}\mapsto \underline{\sigma}(\underline{n})\]\[\texttt{y}\mapsto 1\]$ (yeah we can simply chain square brackets especially realizing they even commute in a case of different variables :)).

I guess the rest is rather obvious considering your predicate $P$ does not depend on $q\_1$ or $q\_2$ and the update to the $\sigma$ does not affect variable $\texttt{x}$. :)

I hope this helps!
> 1 votes

---
Tags: logic, formal-methods, predicate-logic
---


# Question
Title: Do all Turing-complete programming languages have to contain infinite loops?
Intuitively, it seems that if a programming language is Turing-complete, then it must contain a program that's an infinite loop. I have formalized this below:

> **Conjecture.** There does not exist a set $S$ of Turing machines such that all three of these properties hold:
>
> * $S$ is decidable. (That is, there exists a Turing machine that checks whether a Turing machine description is in $S$.)
> * $S$ is Turing-complete. (That is, for every decidable language $L$, there exists some Turing machine in $S$ that decides $L$.)
> * All Turing machines in $S$ halt on all input strings.

How could this be proven (or disproven)?

# Answer
> 5 votes
Suppose that such a set $S$ existed. Consider the following program, which accepts an input $x$:

* Check whether $x \in S$. If not, return TRUE.
* Run $x$ on $x$, and return the opposite.

By assumption, the corresponding language $L$ is decidable, and so there exists some $x \in S$ that decides it. We get a contradiction by considering whether $x \in L$ or not.

# Answer
> 0 votes
I think there might be two questions in this.

1. Do all Turing complete programming languages have to contain infinite loops? Yes. Turing complete \<=\> Simulate any Turing machines. As there are Turing machines with infinite loops your statement has to be true.
2. How to (dis)prove your Conjuncture. One has to either find a Set S that has these properties to prove it OR find that one property can not be achieved while any of the other two are achieved.

I only have a non conclusive proof for this: An Emulator on a normal PC needs to run forever (Turing completeness ignores pesky physics), not for a million years but forever (theoretically). The PC running this program would be a Universal Turing machine. As previously stated Turing complete \<=\> Simulate any Turing machines. Your Set would need to be able to simulate this UTM which sometimes does not halt. Meaning your Set can be only Turing complete or halt on all Inputs but not both

---
Tags: turing-machines, computability, computation-models, halting-problem, turing-completeness
---


# Question
Title: Post Correspondence Problem is undecidable
I am reading Introduction to the Theory of Computation by Michael Sipser and I am in chapter 5. It says here that the Post Correspondence Problem is undecidable, but thinking about it, given a collection, if someone permutes using the algorithm:

```
try every single permutation of the collection:
    if it is a match return True
If nothing was found after trying all permutation return False

```

This should decide if there is a match in $O(n!)$ as I understand the problem, is there something I am missing?

# Answer
Yes. You are missing the fact that the indices that you need to select do not need to be a permutation. In fact you can use the same index multiple times (or never).
> 1 votes

# Answer
It turns out you can use the same domino multiple times, thanks myself.
> 1 votes

---
Tags: algorithms, complexity-theory, turing-machines, np-complete, undecidability
---


# Question
Title: Finding the flaw in a reduction from Hamiltonian cycle to Hamiltonian cycle on bipartitie graphs
I'm trying to solve a problem for class that is stated like so:

> A bipartite graph is an undirected graph in which every cycle has even length. We attempt to show that the Hamiltonian cycle (a cycle that passes through each node exactly once) problem polynomially reduces to the Hamiltonian cycle problem in bipartite graphs. We need a function $T: \\{\text{graphs}\\} \to \\{\text{bipartite graphs}\\}$ such that $T$ can be computed in polynomial time and for any graph $G$, $G$ has Hamiltonian cycle iff $T(G)$ has a Hamiltonian cycle. Let $T(G)$ be the bipartite graph obtained by inserting a new vertex on every edge. What is wrong with this transformation?

I think the problem with the transformation is that for $T(G)$ you need to insert an edge between each pair of vertices and not just insert a new vertex on every edge. I'm actually a bit stumped by this one. Any advice would be much appreciated!

# Answer
The problem is that a Hamiltonian cycle has to pass through **all** vertices: if the cycle in the original graph does not take some edge $e$, then the vertex you split $e$ with will not be taken if you take the same route. This means that the resulting cycle is not Hamiltonian.
> 4 votes

# Answer
Here's a graphic illustration of the problem after changing the diagonal line with edge-vertex-edge there isn't a Ham-Cycle
> 1 votes

# Answer
Is it possible that the transformation is correct but pointless? Consider Barnette's conjecture:

> If a planar graph is bipartite and cubic but only 2-connected, then it may be non-Hamiltonian, and it is NP-complete to test Hamiltonicity for these graphs.

(possibly taken out of context - check back with the Wikipedia entry). Is it possible that all you are doing is reducing one known NP-complete problem to another known NP-complete problem?
> -2 votes

---
Tags: complexity-theory, np-complete, reductions
---


# Question
Title: 3-SAT with atmost 3 variables and variable occuring once per clause
I've stumbled across this problem on CSES https://cses.fi/345/task/E/ and was wondering is it somehow reducible to 2-SAT with given constraints?

So, the problem states that you need to solve a 3-SAT given in a CNF form, albeit a special case, where:

1. Each clause has exactly 3 distinct variables
2. Each variable occurs at most 3 times in all clauses

I doubt that CSES would ask for a heuristic, solver like, approach but can't figure out how those new constraints help in creating a polynomial, possibly close to linear (due to size of input) solution.

Any help would be much appreciated :)

# Answer
> 3 votes
Consider a bipartite graph $G=(C+V, E)$, where $C$ is the set of clauses and $V$ is the set of variables in the SAT instance. There is an edge $(c,x)$ with $c \in C$ and $x \in V$ if $x$ appears (possibly negated) in $c$.

Let $S \subseteq C$ and define $N\[S\] = \\{x \in V \mid \exists c \in C, (c,x) \in E \\}$. I claim that $|N\[S\]| \ge |S|$. Indeed, if we had $|S| \< |N\[S\]|$ then the average number of occurrences of a variable in a clause in $S$ would be $\frac{3 |S|}{|N\[S\]|} \> 3$, showing that some variable must appear at least $4$ times among the clauses in $S$.

Then, by Hall's theorem, $G$ admits a $C$-perfect matching. Consider any such matching and let $x\_c \in V$ be the variable matched to $c \in C$. A satisfying assignment sets $x\_c$ to true if $x\_c$ is positive in $c$, and sets $x\_c$ otherwise. All unmatched variables can be set arbitrarily.

A matching in a bipartite graph can be found in time $O(m \sqrt{n})$, where $n$ (resp. $m$) is the number of vertices (resp. edges) of $G$. In your case $m = \Theta(n)$, so the above simplifies to $O(n^{3/2})$.

---
Tags: satisfiability, 3-sat, 2-sat
---


title: Complexity of unrolled loop in saxpy

text:
# Question
Title: Complexity of unrolled loop in saxpy
I'm trying to calculate the complexity of the saxpy method, which aims to solve the equation $y=\alpha\*x+y$, where $x$ and $y$, are vectors and $\alpha$ is a scalar.

There two versions of the algorithm, with loop unrolling and without, the version without (as seeing below), I've manage to find the complexity, been $2n$ for the number of floating point operations and $3n$ for the number of access to the vectors, where $n$ is the length of the vectors.

Non-unrolled version:

```
integer function saxpy(x, alfa, y, z) result (rslt)
    implicit none
    real, dimension(:), intent(in) :: x, y
    real, dimension(:), intent(out) :: z
    real, intent(in) :: alfa
    integer :: i, n
    n = size(x)
    if (size(x)/=size(y) .and. size(x)/=size(z)) then
        rslt = -1
        return
    end if
    do i = 1, n
        z(i) = alfa * x(i) + y(i)
    end do
    rslt = 0
end function saxpy

```

Unrolled by a factor of 4:

```
integer function saxpy4(x, alfa, y, z) result (rslt)
    implicit none
    real, dimension(:), intent(in) :: x, y
    real, dimension(:), intent(out) :: z
    real, intent(in) :: alfa
    integer :: i, n, m
    n = size(x)
    if (size(x)/=size(y).and.size(x)/=size(z)) then
        rslt = -1
        return
    end if
    m = mod(n, 4)
    do i = 1, m
        z(i) = alfa * x(i) + y(i)
    end do
    do i = m + 1, n, 4
        z(i) = alfa * x(i) + y(i)
        z(i + 1) = alfa * x(i + 1) + y(i + 1)
        z(i + 2) = alfa * x(i + 2) + y(i + 2)
        z(i + 3) = alfa * x(i + 3) + y(i + 3)
    end do
    rslt = 0
end function saxpy4

```

If someone could shed a light to the problem, I'll be very grateful.

# Answer
> 2 votes
Asymptotic complexity is always "up to a constant factor".

To say "$f(n)$ is $O(g(n))$", that means that there exists a constant $c$, and there exists a constant $n\_0$, such that for all $n \> n\_0$, $\left| f(n) \right| \le c \left|g(n)\right|$.

All this says is that the constant $c$ *exists*, and says nothing about what kind of magnitude it might have. The saxpy operation *must* access every value of the vectors $x$ and $y$ at least once, so it must be at least $O(n)$. Both the original and unrolled versions are both $O(n)$, so they save the same *complexity*, even if the constants are different for each version.

When we are analysing algorithms and need something more precise than asymptotic complexity, we typically count specific things, like floating point operations or number of memory accesses (measured in words). Again, both of your versions are identical when you use a measure like that. You could measure branch instructions, I suppose, but it's hard to see how that would be helpful; on modern CPUs, correctly predicted branches are essentially free, and for loops, branches are typically incorrectly predicted at *most* once.

Anything more than that, and you're not really doing algorithm analysis, you're benchmarking.

The actual runtime depends on a large number of details, including the instruction set of the CPU (how wide is its vector registers anyway?). Indeed, rather than this:

```
m = mod(n, 4)
do i = 1, m
    z(i) = alfa * x(i) + y(i)
end do
do i = m + 1, n, 4
    z(i) = alfa * x(i) + y(i)
    z(i + 1) = alfa * x(i + 1) + y(i + 1)
    z(i + 2) = alfa * x(i + 2) + y(i + 2)
    z(i + 3) = alfa * x(i + 3) + y(i + 3)
end do

```

you probably want to swap these two loops:

```
! Disclaimer: It's been a while since I last wrote any Fortran.
m = n - mod(n, 4)
do i = 1, m, 4
    z(i) = alfa * x(i) + y(i)
    z(i + 1) = alfa * x(i + 1) + y(i + 1)
    z(i + 2) = alfa * x(i + 2) + y(i + 2)
    z(i + 3) = alfa * x(i + 3) + y(i + 3)
end do
do i = m+1,n
    z(i) = alfa * x(i) + y(i)
end do

```

Why? Because if the compiler decides to SIMD-optimise the loop, the loads and stores will be aligned.

All of these implementation details matter in practice, and it's why I can pretty much guarantee that, assuming you don't have a hand-tuned BLAS for your CPU, the best "wall time" will be obtained by letting a modern compiler do all the hard work:

```
! Disclaimer still applies.
integer function saxpy(x, alfa, y, z) result (rslt)
    implicit none
    real, dimension(:), intent(in) :: x, y
    real, dimension(:), intent(out) :: z
    real, intent(in) :: alfa
    if (size(x)/=size(y) .and. size(x)/=size(z)) then
        rslt = -1
        return
    end if
    z = alfa * x + y
    rsult = 0
end function saxpy

```

That's assuming you really need `rsult`.

(Note: The "real" BLAS saxpy includes index increments for `x` and `y`, which is why it's "needed" instead of just using array expressions, but of course you probably knew that...)

---
Tags: time-complexity, runtime-analysis
---


# Question
Title: How much faster would a semantic segmentation model be with just 2 classes compared to 100 classes?
Let's say I have a semantic segmentation model that distinguishes between 100 classes of objects, and the speed of running the model is 1 image per second.

Now let's say I take the same model architecture (with untrained parameters), and train it to distinguish between just 2 classes of objects. **Is there any theoretical increase in speed performance under this new model that only detects 2 classes of objects?** Would the speed, for example, now be 2 or 10 or 20, etc... images per second?

I'm trying to increase the speed of my semantic segmentation model and want to know if it would help at all to decrease the number of model outputs to only those classes I need. I'm assuming the accuracy would at least increase, but I'd like to know about the benefit to speed, if any.

# Answer
Changing the number of classes doesn't directly impact the speed. The speed is determined by the size of the neural network.

There is a chance that if you have only 2 classes, then maybe the task becomes easier and you can use a smaller neural network, leading to better speed.

That doesn't seem like the most promising approach to me, though. Instead, I would first try looking at neural net architectures that are optimized for efficiency (e.g., on mobile devices), e.g., MobileNet, EfficientNet, etc.
> 1 votes

---
Tags: algorithms, machine-learning, efficiency
---


# Question
Title: Algorithm which allows the backend to find compromised data from a 3rd party service
On my backend I use a 3rd party service which provides currency exchange rates. I use this rate for the funds conversion within the customer’s accounts. As far as this rate affects customers’ money, I have to be sure that it’s legit. Let’s pretend a 3rd party service is experiencing a glitch and returns 100x times bigger rate than it should be, but the backend is going to carry out this transaction, which will lead to huge issues.

The only solution which I found is:

1. to retrieve the same rate from 5 different sources
2. to calculate a standard deviation for them
3. to compare the needed rate with an arithmetic average
4. to compare arithmetic average with a verifying rate

But this algorithm didn’t work for me — a tiny difference between the rates leads to negative results.

Is there an algorithm which can help me be sure that the rate is correct?

# Answer
> -1 votes
It sounds like this is not a matter for algorithms, but rather for business rules and risk assessment.

That said, on the algorithmic side, you might be interested in changepoint detection as an additional way to detect glitches.

---
Tags: algorithms
---


# Question
Title: Is there a polynomial time reduction from B to A in this case?
Suppose we have an NP-complete problem A, an NP-hard problem B, and a polynomial time reduction from A to B exists. Do we have a polynomial time reduction from B to A as a result?

# Answer
Since $A$ is an NP-complete problem, $A$ is also in NP. Since $B$ is NP-hard, there is a polynomial-time reduction from $A$ to $B$, only by definition and without any further assumption.

So your question is essentially, "Are all NP-hard problems also in NP?", or "Are all NP-hard problems also NP-complete?" But the answer is of course No: very hard problems could be NP-hard but outside of NP. For example, the Halting problem is NP-hard, but obviously not in NP.
> 1 votes

---
Tags: complexity-theory, np-complete, np-hard
---


# Question
Title: Non adjacent sum: Why do we need to include or exclude the current element?
The problem goes like this:

> Write a function, nonAdjacentSum, that takes in an array of numbers as an argument. The function should return the maximum sum of non-adjacent elements in the array. There is no limit on how many elements can be taken into the sum as long as they are not adjacent.

I am struggling to understand the solutions that are online regarding this dynamic programming problem.

All types of solutions one way or other, start by stating that when looping through each element of an array you can either include the current item or exclude the current item. And my question is Why is that? There seems a really basic thing I am missing here.

What I understand clearly is that, When I am looping through the array, if I am observing the element at position `i` then I cannot take element at `i-1` and `i+1` but any elements beyond them are possible.

Now in order to solve this via Dynamic programming, I need to reduce the problem size and solve the base case. I think this is where exclusion is coming from, but I don't understand why though.

Some solutions I have read/viewed are:

# Answer
> 3 votes
To really understand dynamic programming algorithm, it is usually convenient to explain (in natural language) what the subproblems your algorithm is solving dynamically.

Let $T$ be the table of length $n$ that is given in the input.

**Subproblems**: for every $i \leq n$, we compute the maximum sum $S\_i$ of non-adjacent elements in the array $T\[1..i\]$ (the array containing only the first $i$ elements of $T$).

In the end, we want to output $S\_n$, so if we solve these subproblems for every $i\leq n$, we are done.

Now you need to explain how you solve base cases and how you propagate dynamically.

**Base cases**: for $i=1$, it is easy since $T\[1..1\]$ only contains one element. Thus $S\_1 = \max(0, T\[1\])$ (it may be that $T\[1\]$ is negative, and you do not want to take it).

**Dynamic step**: assume you have computed $S\_1, \dots, S\_i$, how do you compute $S\_{i+1}$ from there?

What we usually do is that we take an optimal solution for the subproblem we want to solve at this step and see how it can be computed from optimal solutions for already solved subproblems.

Here, consider an optimal solution of the problem for the array $T\[1..i+1\]$. That is, take $j\_1, \dots, j\_p \in \[1;i+1\]$ such that:

* $1 \leq j\_1 \< \dots \< j\_p \leq i+1$
* $j\_{k+1} - j\_k \> 1$ (no adjacent elements)
* $\sum\_{k=1}^p T\[j\_k\] = S\_{i+1}$ that is, $j\_1,\dots,j\_p$ are optimal for the task we want to solve on $T\[1..i+1\]$.

How does $j\_1, \dots, j\_p$ relate with optimal solutions of other subproblems? There are two cases:

1. either you have not taken $T\[i+1\]$, that is, $j\_p \< i+1$. In this case, $j\_1, \dots, j\_p \in \[1;i\]$. Now I claim that $S\_{i+1} = S\_i$. Indeed, if $\sum\_{k=1}^p T\[j\_k\] \neq S\_i$, then we could have found other non adjacent positions with a greater sum (by definition of $S\_i$), contradicting the way we chose $j\_1,\dots,j\_p$.
2. either you have taken $T\[i+1\]$, that is $j\_p = i+1$. In this case, $j\_{p-1} \< i$ (no adjacent elements are taken). In other words, $j\_1,\dots, j\_{p-1} \in \[1;i-1\]$. Again, I claim that $\sum\_{k=1}^{p-1} T\[j\_k\] = S\_{i-1}$, otherwise, you could have picked non-adjacent positions with a greater sum, contradicting the definition of $j\_1, \dots, j\_p$. Hence $S\_{i+1} = T\[i+1\]+S\_i$.

Since at least one of the previous case happens, we have: $S\_{i+1} = \max(S\_i, S\_{i-1}+T\[i+1\])$.

Now you have it: you only have to compute $S\_i$ for every $i$ following this scheme. You can do it in an array of size $n$. But you can do better: you only need to remember $S\_{i-1}$ and $S\_i$ to compute $S\_{i+1}$. Thus, you can solve the problem by only maintaining two variables $a, b$. At the end of step $i$, you will enforce the condition that $a = S\_{i-1}$ and $b = S\_{i}$.

```
a = 0 # convention : S_0 is 0
b = max(T[1], 0) # b is S_1

for i in rang(2, n+1):
  # At this point, a=S_{i-2} and b=S_{i-1}
  tmp = b # save S_{i-1} before erasing it
  b = max(b, a+T[i]) # S_i is max(S_{i-1}, S_{i-2}+T[i])
  a = tmp # a is now S_{i-1} and b is S_i

return b

```

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


# Question
Title: Find the output value using call by value and call by reference
Given the following code: int p = 5 , q=2; int f( int b, int c){ b = 2 * c; c = 3 + p; return b + c ;} print f(p,q); print p; print q;

I have found that the output values using call by value are: f(p,q)=12 p=5 q=2

And as far as i know also the output using call by reference in this example ,gives the same values.Am I right?

# Answer
Both by value:

```
{p = 5, q = 2, b = 5, c = 2}
b= 2 * c;
{p = 5, q = 2, b = 4, c = 2}
c= 3 + p;
{p = 5, q = 2, b = 4, c = 8}
return b + c;
{b + c = 12}

```

Both by reference:

```
{p = b = 5, q = c = 2}
b= 2 * c;
{p = b = 4, q = c = 2}
c= 3 + p;
{p = b = 4, q = c = 7}
return b + c;
{b + c = 11}

```
> 0 votes

---
Tags: programming-languages, java
---


# Question
Title: Single-tape $o(n\log n)$ Turing machines and nonregular languages
I am reading Sipser's *Introduction to the Theory of Computation*, and encountered two propositions:

1. $A = \\{0^k1^k \mid k ≥ 0\\}$ is nonregular language (pumping lemma).
2. Any language that can be decided in $o(n\log n)$ time on a single-tape Turing machine is regular.

The author shows how to construct a Turing machine that recognizes $A$ in $O(n\log n)$ time. Meaning, nonregular language was recognized in $o(n\log n)$.

Can you please explain where is my mistake in understanding?

This topic describes similar question but does not explain why $A$ was accepted in $O(n\log n)$ time.

# Answer
> 4 votes
You misunderstood $O$ vs $o$. Specifically, for every function $f(n)$ it holds that $f(n)\in O(f(n))$, but $f(n)\notin o(f(n))$ (because $\lim\_{n\to \infty} \frac{f(n)}{f(n)}=1\neq 0$).

There is indeed a theorem showing that a language that is decidable in $o(n\log n)$ time is regular, and the example above shows that there are decidable languages in $O(n \log n)$ time that are not regular.

# Answer
> 3 votes
Here is a similar example.

> Claim: If a language is recognized by a Turing machine running in $o(n)$, then it is accepted by a Turing machine running in $O(1)$.

For the proof, find $n\_0$ such that on inputs of size $n\_0$, the Turing machine $M$ terminates in time less than $n\_0$. For every input $x$ of length $n\_0$, the behavior of $M$ on $x$ is the same as its behavior on $xy$ for *any* string $y$, because $M$ doesn't run long enough to notice the difference. If we denote the running time of $M$ on inputs of length $n$ by $T(n)$, this shows that its running time is at most $\max\_{n \leq n\_0} T(n)$, which is constant.

> Claim: The language of all binary strings of even parity is recognized by a Turing machine running in time $O(n)$, but not by any Turing machine running in $O(1)$.

You can simulate a DFA to accept this language in time $n$. On the other hand, a machine running in time $T$ doesn't reach the last bit of inputs whose length is larger than $T$. Since the last bit determines whether the machine should accept an input or not, such a machine cannot accept this language.

---

The two claims do not contradict each other, since a machine running in $O(n)$ doesn't necessarily run also in $o(n)$.

---
Tags: complexity-theory, time-complexity
---


# Question
Title: To what extent is `this` state considered hidden-state - or its mutations a side-effect?
I was re-reviewing a somewhat upvoted answer of mine where I attempt to explain the differences between pure, impure, deterministic, non-deterministic, and idempotent functions.

In my answer I use .NET's or Java's `List<T>.Add( T )` as an example of an impure deterministic function.

I also use `Random.Next()` as an example of an impure nondeterministic function.

I now think both examples are wrong.

---

Part of my uncertainty comes from how the `this` parameter is syntactically hidden in most languages with classes and instance-methods. But at the same time, whether or not `this` is hidden doesn't affect a function's behaviour: it's trivial to show that a `static` method or *free function* taking an explicit `const me` parameter is identical to an instance method with a hidden `const this` parameter.

...but when `this` is mutable, I'm unsure. Actually, in the *general case* of a free-function that accepts a reference to a mutable structure: are those mutations considered (impure) side-effects even if they aren't "hidden"?

## So, is `List<T>.Add( T )` impure and deterministic? Or pure and non-deterministic?

Assuming that `List<T>.Add( T item )` and its static equivalent `static void Add( List<T> me, T item )` are considered identical, then it follows that destructing `me` to separate parameters shouldn't make a difference either, so therefore the following 3 methods are identical, no?

* `void Add( T item )`
* `static void Add( List<T>* me, T item )`
* `static void Add( T[]** array, size_t* index, T item )`
    + <sub>`array` is `T[]**` rather than `T[]*` to allow for reallocating when resizing.</sub>

I also have contradictory arguments going-on in my head:

* "**It's impure**" because `Add` mutates state.
* "**It's pure**" because `Add` doesn't mutate any hidden or private state: it mutates *only its inputs*, therefore it's pure.

If mutating objects passed by-reference (namely `T[]** array`) is what matters, then what about if `static void Add` instead returns a tuple of `array` and `index`, e.g. `static ( T[]* nextArr, size_t nextIndex ) Add( T[]* array, size_t* index, T item )` (thus shifting the responsibility of reassigning `this.array` to `nextArr` onto the caller), but it still mutates `array`'s contents if the resize/reallocation wasn't necessary, but there's no *hidden* mutations going on, so I'm finding it very hard to say if it's now pure or not...

Similarly for determinism:

* "**It's deterministic**" because identical input will always result in identical output: that is, if the inner structure's `T[]` array and `int index` are considered input, then the end-result output is the same (i.e. `[out] index = [in] index + 1` and `[out] array = [in] array OR [new] resizedArray`).
* "**It's nondeterministic**" because the caller has no way of knowing if the `.Add` call will fail due to the array resizing (allocate, copy, deallocate) operation will fail due to unpredictable *underlying* runtime state, e.g. memory fragmentation, even if the length and contents of the input array is identical to previous `Add` calls.

---

In languages like C# and Java, functions *generally* do not have their own state, so API design horrors like `strtok` can't happen again.

...except when they do: both C# and Java allow the creation of *closures*, which means that what *looks* like a stateless function-pointer/delegate type really has a bound hidden `this` () parameter pointing to the closure capture object, which in-turn probably also contains the original `this` too - which gives me a headache because if `List<T>.Add( T )` is-or-is-not pure or impure and deterministic or non-deterministic because of *its* `this` parameter, how is a closure any different?

Oh, and both C# and Java *also* have thread-local storage - which allows for oddly-behaved *concurrent but not necessarily reentrant* functions, but I'm happy to keep that out-of-scope for now.

# Answer
> 2 votes
Warning: "pure" does not have a 100% agreed upon definition. I have seen different people use it differently.

In the meaning of purity that I learned, all three variants of `Add` that you list are absolutely impure. They perform an (externally observable) mutation to state.

In the meaning of purity that I learned, mutating the inputs is enough to render a function impure.

In contrast, we can consider a function `append(l,x)` that returns a new list that is a copy of the input list `l` with `x` appended to it: this would be pure.

One more detail that you might be wondering about: a function that internally performs a mutation that is not externally observable is typically considered pure, because it has no externally observable mutation (though there might be some authors who have a different definition). For example:

```
def f(x):
    t = 0
    t = t + 1
    return x

```

This performs a mutation to `t`, but it is not externally observable (the function is observationally equivalent to a pure function), so `f` is typically considered pure, too.

# Answer
> 2 votes
There are three aspects to this:

1. How do you define "pure"?
2. On what scale do you consider purity?
3. What is your contract?

# Purity == Referential Transparency

Regarding #1, I prefer to equate "purity" with "referential transparency". The idea behind referential transparency is rather simple: an expression / statement / subroutine / function / procedure / method is *referentially transparent* IFF you can replace it with its value (and vice versa) without changing the meaning of the program.

For example, in C, `2 + 2` is referentially transparent because I can replace `2 + 2` with `4` and also replace `4` with `2 + 2` without changing the meaning of the program. `printf("Hello")` is *not* pure because if I replace it with its value (`6`), that will change the meaning of the program:

```
printf("Hello");
printf("Hello");

```

does *not* have the same result as

```
6;
printf("Hello");

```

or

```
printf("Hello");
6;

```

or

```
6;
6;

```

# Scope

You can apply the concept of referential transparency on any granularity you like. You can choose to treat functions as black boxes or you can zoom in to the level of individual statements or sub-expressions.

The classic example is a memoizing function that uses local mutable state to keep a cache of values. Something like this pseudo-code:

```
def add(a: int, b: int) -> int:
    static const cache: Map[Set[int], int]

    if !cache.hasKey({ a, b }):
        # Assume Map.add is a `void` procedure
        cache.add({ a, b }, a + b)

    return cache[{ a, b }]

```

If you treat the function as a *black box* and look at it from the outside, then it is referentially transparent: you can replace it with its value, and it will not change the meaning of the program:

```
add(2, 3)

```

is the same as

```
5

```

But if you analyze the code of the function itself, then it is clear that its *internals* are not referentially transparent. In fact, *anything* which involves a `void` procedure is not referentially transparent: RT means you can replace it with its value, but a `void` procedure has no value, so RT means you can just delete it. Unless it is doing nothing (in which case, why is it there in the place), this will change the meaning of the program.

In this case, if I replace the call to `Map.add` with its value (nothing), nothing will ever get added to the cache and thus the lookup will fail and `add` will throw an exception or return `nil` or something like that:

```
def add(a: int, b: int) -> int:
    static const cache: Map[Set[int], int]

    if !cache.hasKey({ a, b }):
        NOP

    return cache[{ a, b }] # Boom! Key does not exist

```

Software Engineering is all about abstractions. In a perfect world, you would not be able to know whether or not `add` uses memoization and you wouldn't have access to its source code. Therefore, *from your perspective* as the client of `add`, it is referentially transparent.

Which brings us to #3:

# Contract

> "**It's nondeterministic**" because the caller has no way of knowing if the `.Add` call will fail due to the array resizing (allocate, copy, deallocate) operation will fail due to unpredictable *underlying* runtime state, e.g. memory fragmentation, even if the length and contents of the input array is identical to previous `Add` calls.

And `1 + 1` could fail if a meteorite destroys the computer just as it is computing the answer. That does not make it non-deterministic. It could also return `4` if a cosmic ray flips the wrong bit in RAM. That does not make it impure, even though it has a hidden dependency on the mutable state of the universe.

It is a question of the *contract* you have with the function. Does the contract include resistance to cosmic rays? To meteorites? Does it include resistance to Operating System failure? To OS memory overcommitment?

This brings us back to the issue of abstractions above: software is built by building abstractions on top of abstractions, and we generally must assume that abstractions work as documented. In fact, with *proper* abstractions we have no other choice since we don't have access to the inner workings.

# Answer
> 1 votes
List.Add(T) is impure function because it mutates state thereby producing side effects upon mutation.Data structure is a set of values that can be accessed via memory.Thereby mutating certain data structures in an algorithm makes it an impure function,without mutable state ,it would be simply stateful functions which are called procedures would be mathematical functions without any side effect lke printng on the screen or mutating a data type.

---
Tags: functional-programming
---


# Question
Title: Constructing an unrestricted grammar for XWX, where W is the reverse of X
I'm trying to construct an unrestricted grammar for strings of the form XWX, where W is the reverse of X, over the alphabet {a, b}.

I think I can apply similar logic to the a^nb^nc^n solution (below), but am running into issues.

```
S ->
S -> aSBC
CB -> BC
aB -> ab
bB -> bb
bC -> bc
cC -> cc

```

I've thought about it a lot, and have tried starting off with the following, but cannot make the needed reordering steps work:

```
S ->
S -> aSXA
S -> bSYB

```

A shove in the right direction would be helpful!

# Answer
> 1 votes
The idea of that solution is to generate $a^nY$, where $Y$ is a bunch of nonterminals, such that $Y$ can only generate $b^nc^n$.

To apply the same idea here, you'd want to generate $xY$ such that $x \in X$, $Y$ is a bunch of nonterminals, and $Y$ can only generate $x^{-1}x$.

So what I'd start with is

```
S ->
S -> aSA
S -> bSB
S -> cSC
S -> dSD

```

(and so on for each character in the alphabet).

Now comes the tricky part: how to expand those nonterminals into $x^{-1}x$? E.g., CBA needs to generate cbaabc.

Just like in the example you're following, work from left to right. Only when C has a terminal to its left, replace it with cC'. Send C' to the right and expand it there only when it has arrived.

Tricks: you can change S into T and keep T around as a marker. You can mark the end of the word with a nonterminal and remove that mark when you're done. It's much like programming Turing machines.

Good luck.

---
Tags: formal-grammars
---


# Question
Title: Image registration using gradient descent
I have a target image $f(x,y)$ (where $x \in \[0, 250\]$ and $y \in \[0,300\]$), and a source image $g(x,y)$

I want to align $g$ to $f$ using the transformation : $$\Psi(x,y;t\_x, t\_y, \theta) = \begin{pmatrix}\cos(\theta) & -\sin(\theta) & t\_x \\ \sin(\theta) & \cos(\theta) & t\_y\end{pmatrix}\begin{pmatrix}x \\ y \end{pmatrix}$$

I'm trying to do this by minimizing the squared error : $$l(p) = \sum\_{x,y}{(f(x,y) - g(\Psi(x,y;p))}^2$$

I first computed the gradients : $$ \begin{align} \frac{\partial l(p)}{\partial t\_x} & = \sum\_{x,y}\left(2(f(x,y) - g(\Psi(x,y;p)) \left(\frac{\partial }{\partial t\_x}g(\Psi(x,y,p))\right)\right) \\ & = 2\sum\_{x,y}\left((f(x,y) - g(\Psi(x,y;p)) \left(\frac{\partial }{\partial t\_x}g(\Psi(x,y,p))\right)\right) \\ & = 2\sum\_{x,y}\left((f(x,y) - g(\Psi(x,y;p)) \left(\frac{\partial }{\partial \Psi\_x}g(\Psi(x,y,p))\frac{\partial \Psi\_x}{\partial t\_x}\right)\right)\\ & = 2\sum\_{x,y}\left((f(x,y) - g(\Psi(x,y;p)) \left(\frac{\partial }{\partial \Psi\_x}g(\Psi(x,y,p))\right)\right)\\ \frac{\partial l(p)}{\partial t\_y} & = 2\sum\_{x,y}\left((f(x,y) - g(\Psi(x,y;p)) \left(\frac{\partial }{\partial \Psi\_y}g(\Psi(x,y,p))\right)\right) \end{align} $$ However, for $\theta$, I find this : $$ \begin{align} \frac{\partial l(p)}{\partial \theta} & = \sum\_{x,y}\left(2(f(x,y) - g(\Psi(x,y;p)) \left(\frac{\partial }{\partial \theta}g(\Psi(x,y,p))\right)\right) \\ & = 2\sum\_{x,y}\left((f(x,y) - g(\Psi(x,y;p)) \left(\frac{\partial }{\partial \theta}g(\Psi(x,y,p))\right)\right) \\ & \text{by chain rule } \frac{\partial}{\partial \theta}g(\Psi(x,y,p)) = \frac{\partial}{\partial \Psi\_x}g(\Psi\_x(x,y;p), \Psi\_y(x,y;p))\frac{\partial \Psi\_x}{\partial \theta} + \\ & \frac{\partial}{\partial \Psi\_y}g(\Psi\_x(x,y;p), \Psi\_y(x,y;p))\frac{\partial \Psi\_y}{\partial \theta} \\ & = 2\sum\_{x,y}\left((f(x,y) - g(\Psi(x,y;p)) \left(\frac{\partial }{\partial \Psi\_x}g\_\Psi\frac{\partial \Psi\_x}{\partial \theta} + \frac{\partial }{\partial \Psi\_y}g\_\Psi\frac{\partial \Psi\_y}{\partial \theta}\right)\right) \end{align} $$

Since $\frac{\partial \Psi\_x}{\partial \theta} = -x\sin(\theta) - y\cos(\theta)$, it can reach high values such as $300$ (depending on $\theta$). This means that $\frac{\partial l(p)}{\partial \theta}$ have values way bigger than $\frac{\partial l(p)}{\partial t\_x}$ for instance, which feel quite wrong.

I think I did a mistake calculating the gradient, but I don't understand where?

# Answer
> 0 votes
It doesn't feel wrong to me.

A rotation by a small amount, say one degree, changes the location of an object in the image by many pixels. For instance, suppose you have a 1000x1000 image, and you rotate it by one degree around the upper-left corner. Then an object near the upper-right corner moves upward/downward by about 17 pixels. There is "leverage" proportional to the size of the image; rotate a long lever by a small rotation, and the end of the lever still moves a large way.

In contrast, a translation by a small amount, say one pixel, changes the location of an object in the image by only a little. For instance, if you have that same image and you translate by one pixel, then the object moves by only 1 pixel.

So it is not surprising (to me) that the gradient in the first case might be much larger than the gradient in the second case.

# Answer
> 0 votes
By the chain rule, for some parameter $\xi$,

$$\frac12\frac{\partial l}{\partial\xi}=\sum\_{x,y}(f-g)\left(\frac{\partial g}{\partial \Psi\_x}\frac{\partial \Psi\_x}{\partial\xi}+\frac{\partial g}{\partial \Psi\_y}\frac{\partial \Psi\_y}{\partial\xi}\right).$$

Using complex numbers for convenience,

$$\Psi=e^{i\theta}z+t$$ and

$$\left|\frac{\partial\Psi}{\partial\theta}\right|=|ie^{i\theta}z|=|z|,\\ \left|\frac{\partial\Psi}{\partial t}\right|=1.$$

As you see, those derivatives don't have comparable magnitudes.

---

The moral of the story is that the steps used in the iterations should be adjusted accordingly. For instance, a unit step for translation will be coherent with an angular step that corresponds to an *average* translation of one unit for the whole image (so the step should be inversely proportional to the image size).

---
Tags: optimization, computer-vision
---


# Question
Title: If language $P$ is not regular, is $\{ w \in \Sigma ^* : |w| \geq 1000 \}\cup P$ regular necessarily?
Prove or refute.

> Let $ L = \\{ w \in \Sigma ^\* :\ |w| \geq 1000 \\} $. Let $ P $ be a non-regular language. Then $ L \cup P $ is regular necessarily.

I think it is true, but I don't have any idea about how to prove is formally. It is just that when the word becomes greater than 1000 it will be inside the language. Can you help me say it more formally please?

# Answer
> 2 votes
Consider $P \cap L^c$. Such a set is necessarily finite (why?). Can you use closure properties of regular languages to finish the rest?

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


# Question
Title: Using algorithm for weighted graphs when the weights are vectors
Consider the following example problem. Given a graph with edge weights, find a matching that maximizes the number of matched vertices, and subject to this, maximizes the total weight. This problem can be reduced to simple maximum-weight matching as follows:

* Construct a graph in which the weight of each edge $e$ is $(1, w\_e)$, where $w\_e$ is the weight of $e$ in the original graph.
* Run any algorithm for finding a maximum-weight matching on the new graph, where the arithmetic operations (addition and subtraction) on the weights are done elementwise, and comparison (less-than or greater-than) is done in a lexicographic order. The returned matching maximizes a vector in which the first element is the number of matches and the second element is the total weight. The vector is maximum in lexicographic order, which is exactly what we wanted.

While there are other algorithms for this specific problem, the method is quite flexible and intuitive. For example, if we want to first maximize the total weight, and subject to this maximize the number of matches, then we should just change the vector weights to $(w\_e, 1)$. If we want to maximize the number of matches in a particular subgroup of edges $F$, then the total number of matches, and then the total weight, we can change the vector weights on edges of $F$ to $(1, 1, w\_e)$ and on other edges to $(0, 1, w\_e)$.

My question is: can I assume that any algorithm for maximum-weight matching would work when the edge weights are vectors?

More generally: can I assume that any algorithm for weighted graphs would work with vector weights?

Are there algorithms that do not work with vector weights?

NOTE: In most textbooks, I see similar reductions done without vectors, e.g. by multiplying the first element by a sufficiently large number, and then adding the second element. I find the vector-weight explanation more simple and intuitive; this is why I ask if it is correct.

# Answer
Let $M$ be a number which is larger than the weight of a maximum matching. For example, you can take $M$ to be $nW$, where $n$ is the number of vertices and $W$ is the maximal weight. Apply the transformation $w \mapsto M + w$, and run your favorite algorithm.

Similar tricks should work in other cases: apply the transformation $(v\_1,\ldots,v\_k) \mapsto M^{k-1} v\_1 + \cdots + Mv\_{k-1} + v\_k$, where $M$ is large enough.
> 1 votes

---
Tags: graphs, reductions, matching
---


title: Does computer use NFA or DFA?

text:
# Question
Title: Does computer use NFA or DFA?
I am now learning about automation and I am wondering if personal computers use NFAs or DFAs.

I believe it uses a DFA since when we are clicking on something it is in a way determined what will happen. Any thoughts? :)

# Answer
They use something else, called a RAM computational model, which is Turing complete (so it's equivalent to Turing machines).
> 2 votes

---
Tags: automata
---


title: Algorithms for almost sorting

text:
# Question
Title: Algorithms for almost sorting
I want to find a comparison sorting algorithm that can **almost** sort a set of data, using the least comparisons possible.

What I mean by "almost" is that if the perfectly sorted data is $\[x\_1, x\_2, …, x\_n\]$ and the almost sorted data is $\[x\_{i\_1}, x\_{i\_2}, …, x\_{i\_n}\]$, then $\forall j \in \[\\!\[1, n\]\\!\], |i\_j - j| \leq C$, $C$ being a parameter of the algorithm.

I want to emphasize that I want to minimize the number of comparisons. Other operations don't matter in the complexity. I would like to know if a number of comparisons next to $\frac{n\log\_2 n}{C}$ can be possible.

In practice, I have to work with $n \simeq 1000$ and $C \simeq 10$ and only the comparisons are done by a human.

Are there any algorithm of the kind? Could I have some insight about it? Thanks.

EDIT: I got two ideas to almost sort:

* The first one is to quicksort the array, and stop when I have to sort a sub-array of $\leq C$ data. The best case scenario requires roughly $\sum\limits\_{k=0}^{\log\_2(n/C)}2^k\frac{n}{2^k} = n\log\_2(n/C)$ comparisons. The algorithm is correct because sub-arrays are relatively sorted, and since they are of size $\leq C$, a value can't be farther than $C$ from its sorted position. The problem is that the worst case scenario is still in $\Omega(n^2)$ ;
* The second idea is to sort using an insertion sort with a dichotomic search, and stop the search when the bounds of the search are distant of at most $C$. With this method, I get roughly $\sum\limits\_{k=1}^{n-1}\log\_2(k/C) = \log\_2((n-1)!) - n\log\_2(C)\simeq n\log\_2(n/C) - n$ in the worst case, which is better than the previous algorithm, but I am not quite sure that the array will be $C$-almost sorted.

EDIT 2: I found that the second algorithm is not correct. If, during the first insertion, $x\_n$ is put before $x\_1$, then their relative order will not change during the rest of the execution, therefore one of them will be farther than $C$ from its sorted index if $n \> 2C$.

# Answer
Call an array $C$-sorted if each element is at-most $C$ places away from its place had the array been sorted (this is the same as "almost"-sorted array in the question, but in plain English).

Assume we will use comparison sort.

**Claim One**: Given an array of $n$ elements that is $C$-sorted, we can sort it with at most $n\lceil\log\_2 (C+1)\rceil$ comparisons.

**Proof**: Here is how we can sort the given array.

1. Create a buffer that is an array of size $C+1$.
2. One by one move the first $\min(n, C+1)$ elements to the buffer, keeping the buffer sorted using binary search to find the right place for each new element.
3. One by one move the min element from the buffer array to the result array, and, if the given array is not empty yet, add the next element to the buffer, keeping the buffer sorted using binary search to find the right place for that next element.

For each element in the array, at most $\lceil\log\_2 (C+1)\rceil$ comparisons is used to find its right place in the buffer. The number of total comparisons used is at most $n\lceil\log\_2 (C+1)\rceil$. $\quad\checkmark$

---

**Claim Two**: At least $\log\_2 (n!) - n\lceil\log\_2 (C+1)\rceil$ comparisons are needed to $C$-sort an array of size $n$ in the worst case.

**Proof**: Otherwise, suppose there is an algorithm that can $C$-sort any given array of size $n$ with less than $\log\_2 (n!) - n\lceil\log\_2 (C+1)\rceil$ comparisons. Extending that algorithm with the algorithm shown in the proof of claim one, we obtain an algorithm that can sort any given array of size $n$ with less than $\log\_2(n!)$ comparisons. That is well-known to be impossible. $\quad\checkmark$

---

**Claim Three**: There is no algorithm that can $C$-sort an array of size $n$ with $O(\frac{n\log\_2 n}{C})$ comparisons.

**Proof**: We have, if $n\ge C^{1+\epsilon}$ for some fixed $\epsilon\gt0$, $$\begin{aligned}\lim\_{C\to\infty} \frac{\log\_2 (n!) - n\lceil\log\_2 (C+1)\rceil}{\frac{n\log\_2 n}{C}} &= \lim\_{C\to\infty} C\left(\frac{\log\_2 (n!)}{n\log\_2 n}-\frac{\lceil\log\_2 (C+1)\rceil}{\log\_2 n}\right)\\\&\ge \lim\_{C\to\infty} C\left(1-\frac1{1+\epsilon}\right)=\infty. \end{aligned}\quad\checkmark$$

---

Indeed, $\log\_2 (n!) - n\lceil\log\_2 (C+1)\rceil$ gives a pretty strong lower bound for the number of comparison needed in the worst case since $\log\_2 (n!)$ is the lower bound to sort an array by comparison sort in the worst case, and, as $\log\_2(n!)\approx n\log n$, for any fixed $C$,

$$n\lceil\log\_2 (C+1)\rceil = o(\log\_2 (n!)). \ \ \color{#d0d0d0}{\text{(small o, not big O!)}}$$

That is, at least $(1-\epsilon)\log\_2(n!)$ comparison is needed to $C$-sort array when $n$ is sufficiently large, for all fixed $\epsilon\gt0$ and $C$.

The statements above support the usage of "almost sort" and "almost sorted" to refer to "$C$-sort" and "$C$-sorted" respectively.

---

We also note that

> on average, quicksort performs only about 39% worse than in its best case. In this sense, it is closer to the best case than the worst case. A comparison sort cannot use less than $\log\_2(n!)$ comparisons on average to sort $n$ items (as explained in the article Comparison sort) and in case of large $n$, Stirling's approximation yields $log\_2(n!) \approx n(\log\_2 n − log\_2 e)$, so quicksort is not much worse than an ideal comparison sort.

---

Now let us have an array of $n=1000$ elements and $C=10$.

* Quicksort will perform about $2n\log n\approx 19931$ comparisons on average to sort the array, as shown on Wikipedia.
* Claim Two says $\log\_2 (n!) - n\lceil\log\_2 (C+1)\rceil\approx4529$ are needed to $10$-sort the array in the worse case, which is sort of information-theoretical the best.
* Note that $\frac{n\log\_2 n}{C}\approx997$, which is much less than of 4529.

So I believe, (some more argument are omitted here), an algorithm that performs about $n\log\_2(n/C)\approx6643$ comparisons to $10$-sort the array is pretty much about the best we can get.
> 7 votes

# Answer
This paper, Approximate Sorting (PDF) says

> We show that any comparison based, randomized algorithm to approximate any given ranking of $n$ items within expected Spearman’s footrule distance $n^2/ν(n)$ needs at least
>
> $n(\min\\{\log ν(n), \log n\\} − 6)$
>
> comparisons in the worst case. This bound is tight up to a constant factor since there exists a deterministic algorithm that shows that $6n \log ν(n)$ comparisons are always sufficient.

They give an algorithm that is based on Quicksort which recursively finds medians and partitions the elements into buckets. Buckets are in sorted order but items within the buckets are unsorted.
> 0 votes

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


# Question
Title: Fastest Algorithm for "Merge" step in Mergesort
Given two sorted arrays $a\_1,a\_2,\dots,a\_n$ and $b\_1,b\_2,\dots,b\_m$, merge them together into one sorted array $c\_1,c\_2,\dots,c\_{n+m}$ containing the elements of $a$ and $b$.

The typical mergesort method works in $O(n+m)$, and if we run binary search for each element from one of the arrays, it works in $O(\min(n,m)\log(\max(n,m)))$. However, the latter method is no better than if the smaller array was unsorted. I was wondering if there is any use of the fact that both arrays are sorted to optimise the latter solution. In particular, I was hoping for an algorithm in time $O(\min(n,m))$ or so.

I attempted a "parallel binary search" method, but it seems in the worst case that it is no better than the naive binary search method.

# Answer
> 1 votes
If you only want to count the number of comparisons then you can achieve $O\left(n\log(1+\frac{m}{n})\right)$ comparisons as follows:

Let $k\_1$ denote the index of $a\_1$ in the final array $c$ and for $1\<i\leq n$ let $k\_i$ denote the difference between the indices of $a\_i$ and $a\_{i-1}$ in the final array $c$.

To insert $a\_1$ in $b$, start by doing an exponential search to find the smallest $r$ such that $b\_{2^r} \geq a\_1$ (this is also the smallest $r$ such that $2^r \geq k\_1$). This takes $O(\log k\_1)$ comparisons. Now do a binary search between the indices $1$ and $2^r$ to locate the correct position $k\_1$ to insert $a\_1$, and insert the element there. This also takes $O(\log k\_1)$ comparisons.

To insert $a\_2$ into $b$ start by doing an exponential search, starting at $k\_1$, to find the smallest $r$ such that $b\_{k\_1+2^r} \geq a\_2$ (this is also the smallest $r$ such that $2^r \geq k\_2$). This takes $O(\log k\_2)$ comparisons. Now do a binary search between the indices $k\_1$ and $k\_1+2^r$ to locate the correct position $k\_1+k\_2$ to insert $a\_2$, and insert the element there. This also takes $O(\log k\_2)$ comparisons.

In general following this strategy you will make $O(\log k\_i)$ comparisons to insert element $a\_i$. So the total number of comparisons will be $T = O\left(\sum\_{i=1}^n\log k\_i\right)$. Because the $\log$ function is concave, by Jensen's inequality we have $\sum\_{i=1}^n\log k\_i \leq n\log \frac{\sum k\_i}{n} \leq n\log \frac{n+m}{n}$. The result follows.

Notice that (assuming $n\leq m$) this is asymptotically always at least as good as $O(n+m)$ and $O(n\log m)$, and sometimes better than both: if you take for example $m=n\log n$ you get $O(n\log\log n)$ comparisons compared to $O(n\log n)$ with both other methods.

To complement this, let us show that this is optimal (up to a constant factor, still assuming $m\geq n$). The number of ways to insert $n\geq 1$ ordered elements into an ordered array of length m is $\frac{(m+n)!}{m!n!} \geq \frac{(m+1)^n}{n!} \geq \max\\{(\frac{m}{n})^n, 2^n\\}$. Thus to distinguish between these cases you need at least $T\geq \log\_2(\frac{(m+1)^n}{n!})$ comparisons in the worst case. We have $T \geq \max\\{n\log\_2\frac{m}{n}, n\\}$, which implies $T \geq \frac{1}{2}n\log\_2(1+\frac{m}{n})$.

# Answer
> 0 votes
One method fitting the analysis results presented is
*one by one, insert elements of the shorter sequence ($s$) in the longer one ($l$)*.

There are several way to reduce the search range in the longer sequence exploiting the shorter one to be ordered, too, starting with

*position ← 0*
*for every element $e$ of* $s$
*position ← insertion position of* $e$ *in* $l$*, starting from position*
*insert* $e$ *in* $l$ *at position*

— without any relation specified between $n$, $m$, and the values in $a$ and $b$, I don't see *any* to allow a tighter bound on time than
$O(\min(n,m)\log(\max(n,m)))$.

Try proving $O(n+m)$ is optimal.

# Answer
> 0 votes
The purpose of a merge is to form a single, continuous array holding the $n+m$ keys from the original arrays.

Even if everything can be done in-place (by $a$ and $b$ being contiguous), in the worst case you need to *move* all of them, which is $\Omega(n+m)$. Hence a merge in time $O(n+m)$ is optimal.

Even ignoring the moves (?), in the worst case you need to look at all keys at least once, and $O(n+m)$ is still optimal.

---

A light of hope: the best case is more promising. If $a, b$ are contiguous and $a\_n\<b\_1$, the merge can be done in $O(1)$.

---
Tags: sorting, binary-search
---


title: Finding loop invariant

text:
# Question
Title: Finding loop invariant
I am really new concerning loop invariants and I am currently trying to figure out a loop invariant of an algorithm for prime numbers. I tried a lot of ideas, but I still have problems since there are two nested loops. I am also really grateful if someone have any tips regarding finding a loop invariant. My idea is that all $i$ which are primes are set on true and all $i$ which are not primes are set on false.. but I don't think that this is the loop invariant.

```

PRIME_FILTER(n)
1  P = INIT(n) // Initialize array P[1::n] with True
2  P[1] = False
3  i = 2
4  while i * i <_ n
5     if P[i] == True
6       j = i * i
7       while j <_ n
8          P[j] = False // Not prime
9          j = j + i
10    i = i + 1
11 return P

```

# Answer
> 1 votes
Let's see what the algorithm does in its first few iterations:

* Mark all elements other than 1 as "potentially prime".
* Mark all multiples of 2, starting at 4, as "not prime".
* Mark all multiples of 3, starting at 9, as "not prime".
* Skip 4, since it is known to be not prime.
* Mark all multiples of 5, starting at 25, as "not prime".
* Skip 6, since it is known to be not prime.
* Mark all multiples of 7, starting at 49, as "not prime".

So it continues, until the next element is already larger than $\sqrt{n}$.

Here is how we can describe the contents of the array:

* All elements other than 1 are "potentially prime".
* All elements not divisible by 2 are "potentially prime", except for 2.
* All elements not divisible by 2,3 are "potentially prime", except for 2,3.
* All elements not divisible by 2,3,4 (equivalently, by 2,3) are "potentially prime", except for 2,3.

And so on.

Hopefully this gives you some ideas on the loop invariant.

# Answer
> 0 votes
The inner loop is a "for" loop in disguise, from `j` to `n` in steps `i`. The invariant can only express that all values in the array P from the initial value of `j` until the current value of `j` have been set to `False`. It is worth to note that the initial value of `j` is , hence all the indexes set to `False` are multiples of `i`.

The outer loop tries all increasing values of `i` from `2` on until  exceeds `n`. The invariant of this loop expresses that for all `i` from `2` to the current value, the multiples of `i` such that `P[i]` is `True`, from  to `n` have been struck out.

---

In fact, these invariants are not very informative, as they essentially repeat what the statements do. Things get more interesting if you establish, by a theorem, that all `P[i]` until the current `i` are `True` for primes and `False` otherwise. Hence the outer invariant can be rephrased as "the values in `P` up to `i` indicate primality of the corresponding index".

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


# Question
Title: Given a sequence of strings how can you find the maximum number of strings so that if you concatenate them you have a dominant letter?
The naive approach, which is the first thing that came to my mind, is to use some sort of backtracking to generate all subsets of the given set of strings and then to find the subset with the maximum number of strings that satisfies the condition. But I don\`t believe it is ok, because for large numbers of strings the exponential nature of bkt (2^n subsets) will severely affect the time of execution.

Any other ways to find the maximum number of strings from the given list of strings, so that if you concatenate them the property is satisfied, would be welcomed.

# Answer
Consider that dominant letter. Suppose it is $A$. Now the question is to find the maximum number of strings in which $A$s are the majority. So it is a duel between $A$s and all other letters.

A good string should have lots of $A$s. In fact, since it is a duel in cardinality, the most advantageous string should be the string in which the difference between the number of $A$s and the number of other letters are the greatest.

Can you see the greedy strategy?

---

The algorithm will run in $O(n+26k)$ time, where $n$ is the total length of all strings and $k$ is the number of strings, assuming all strings are made of uppercase English letters.
> 1 votes

---
Tags: algorithms, data-structures, optimization, backtracking
---


# Question
Title: Find the proper hypothesis for the substitution method for a recurrence problem
I'm trying to solve a recurrence problem using substitution method:

> Given the following recurrence equation:
> $ T(n) = \begin{cases} 3 &n = 0 \\ 3T(\frac{n}{5}) + T(\frac{n}{6}) + n&n \> 0 \end{cases} $
> provide a tight asymptotic bound for the solution

I've been trying to understand how the recursion tree is made, but I'm not sure that's the smartest way to get the hypothesis to apply the substitution method.

In fact, I looked at the solution provided with the exercise and the first statement is just $T(n) = \Theta(n)$ (the demonstration of this is made right after)
I just don't understand how to get the *proper hypothesis*, because in my mind, this should have been something like $T(n) = \Theta(n\log n)$.

# Answer
> 1 votes
#### A simple rule to get the hypothesis.

Assume $T(n)\ge0$ for all $n$. Suppose the recurrence relation is $$T(n) = a\_1T(b\_1n) + a\_2T(b\_2n) + cn$$ where $a\_i, b\_i, c$ are constants, $a\_i\ge0$ and $0\lt b\_i\lt 1$ for all $i$, $c\>0$.

The asymptotic approximation depends on the value $a\_1b\_1+a\_2b\_2$.

* If $a\_1b\_1+a\_2b\_2\<1$, then $T(n)=\Theta(n)$;
* If $a\_1b\_1+a\_2b\_2=1$, then $T(n)=\Theta(n\log n)$;
* If $a\_1b\_1+a\_2b\_2\>1$, then $T(n)=\Theta(n^p)$ for some $p\>1$.

#### Some examples

| Recurrence relation | $a\_1b\_1$ \+ $a\_2b\_2$ | $T(n)$ |
| --- | --- | --- |
| $T(n)=2T(n/2)+n$ | $2\times\frac12$ = $1$ $\ \ \ $($a\_2=0$) | $\Theta(n\log n)$ |
| $T(n)=T(2n/3)+2T(n/6)+5n$ | $\frac23+$ $2\times$ $\frac16=$ $1$ | $\Theta(n\log n)$ |
| $T(n)= 3T(\frac{n}{5}) + T(\frac{n}{6}) + 3n$ | $3\times\frac15$ \+ $\frac16$ = $\frac{23}{30}\<1$ | $\Theta(n)$ |
| $T(n)= 3T(\frac{n}{5}) + 3T(\frac{n}{6}) + \frac n7$ | $3\times\frac15$ \+ $3\times\frac36$ = $\frac{11}{10}\>1$ | $\Theta(n^p)$ for some $p\>1$ |

#### What about more general situations?

The simple rule above should be sufficient for most of the basic exercises or tests in an introductory course.

The rule stays the same basically when there are more terms like $af(bn)$ in the recurrence relation. Or $cn$ is not changed much, such as $cn+d$ for some constant $d$ or $cn+\log n$.

For more general situations, you can take a look at the Akra–Bazzi method. It is also explained here. You can find how the exponent $p$ in the case of $a\_1b\_1+a\_2b\_2\>1$ is defined.

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: Creating a PDA that accepts the following language
Using automata-lib 5.0.0 (Python library), I need help creating a Python program that simulates a PDA that only accepts the following language:

L = {a^m b^n | 0 ≤ m != n}

If you could provide any diagrams, or flowcharts to help me understand, they would be greatly appreciated.

# Answer
Cases M\>n M\<n

The union of these cases will give you answer
> 0 votes

---
Tags: automata, pushdown-automata, python
---


# Question
Title: Prove it is undecidable that a Turing machine accepts at least one input w in space $|w|^2$
This question is part of the undecidable lecture by Jeff Erickson.

$$\\{\langle M\rangle\mid M \text{ accepts at least one string }w\text{ in space }|w|^2\\}$$

We should prove that this language is undecidable. So what i tried is to create a new TM $M'$ where $M'$ moves $|w|^2$ steps to the right and than tries to accept $w$. So in my opinion that would solve the Accept Problem which we know is undecidable.

My problem with this is that we don't actually get $w$ as an input we just ask if there is a word that accepts after $|w|^2$ steps. And i don't really know how to handle this.

# Answer
> 2 votes
Let $\text{AnySpaceSquare}$ denote the language in the question.

Let us reduce the well-known undecidable language $\text{Accept} :=\\{\langle M, w\rangle\mid\text{Turing machine }M\text{ accepts }w\\}$ to $\text{AnySpaceSquare}$.

---

Suppose a TM $M$ and a word $w$ is given. Construct TM $M'$ so that upon any input, it will simulate $M$ on input $w$, **ignoring the input completely**.

1. Upon any input $v$, $M'$ erases that input.
2. $M'$ writes $w$ on the tape. (So, $M'$ should have $w$ hard-encoded in its states and transitions.) Up to now, $M'$ should use at most $\max(|v|,|w|)+1$ spaces.
3. $M'$ runs as if it were $M$.
4. If the simulated $M$ accepts/rejects/runs forever/whatever, so does $M'$ respectively.

Let us check the map $\langle M, w\rangle\to \langle M'\rangle$.

* If $\langle M, w\rangle\not\in \text{Accept}$, $M'$ never accepts.
So $\langle M'\rangle\not\in\text{AnySpaceSquare}$.
* Otherwise, $\langle M, w\rangle\in \text{Accept}$.
Let us say $M$ accepts $w$ in $n$ steps. These $n$ steps use at most $n+1$ spaces. Pick any word $v$ that is long enough, $M'$ should accept $v$ within $|v|^2$ spaces. In fact, any word at least $n+|w|+1$ long would be fine.
So, $\langle M'\rangle\in\text{AnySpaceSquare}$.

Hence, if we could decide $\text{AnySpaceSquare}$, we could also decide $\text{Accept}$.

---

Exercise. $ \\{\langle M\rangle\mid M \text{ accepts at least one string }w\text{ in time }|w|^2\\}$ is undecidable.

---
Tags: turing-machines, undecidability
---


# Question
Title: Show the pumping lemma is not a universal method for proving not context-free
I know that the pumping lemma is not powerful enough to prove a language is not context-free, but I don't understand how to show it.

I have the same question as this one Show that the Pumping Lemma for CFLs is not powerful enough to prove that the language L = {aibjck |i ≠j ≠ k ≠ i } is not context free, but I couldn't understand the answer in this.

Please explain to me in detail, how can I show $L = \\{ a^i b^j c^k | i ≠ j ≠ k ≠ i \\}$ satisfy the pumping lemma?

# Answer
Let the pumping length $p=6$.

Let $s=a^ib^jc^k\in L$, $|s|\ge p$.

There are three cases.

* $i=\max(i,j,k)$. We will pump a part of $a^i$.

$3i\gt i+j+k=|s|\ge p=6$. So $i\ge3$.

Among three nonnegative numbers $i-1$, $i-2$ and $i-3$, there is one number that is neither $j$ nor $k$. Suppose it is $i-d$ for some $d\in\\{1,2,3\\}$.

$s=a^{i-d}a^db^jc^k=uvwxy$, where $u=a^{i-d}$, $v=a^d$, $w=x=\epsilon$, $y=b^jc^k$.

+ $|v|=d\ge1$, $|vwx|=|v|=d\le3\lt p$.
    + $uv^0wx^0y = a^{i-d}b^jc^k\in L$. $\quad$(Pumping down is fine.)
    + $uv^nwx^ny = a^{i+(n-1)d}b^jc^k\in L$ for $n\gt1$, since $i+(n-1)d\gt i$. $\quad$(Pumping up is fine.)
* $j=\max(i,j,k)$. We can pump a part of $b^j$ just as the case above.
* $k=\max(i,j,k)$. We can pump a part of $c^k$ just as the cases above.

Hence $L$ satisfies the pumping lemma for context-free language with pumping length $p=6$.

**Exercise**. (easy) Show that the pumping lemma for CFLs is not powerful enough to prove $\\{ a^i b^j c^kd^l \mid i,j,k,l\text{ are pairwise distinct} \\}$ is not context-free.
> 2 votes

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


# Question
Title: Can a complete binary tree have at least two nodes with just one child?
https://en.wikipedia.org/wiki/Binary\_tree#Types\_of\_binary\_trees says

> A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes at the last level h.\[18\] An alternative definition is a perfect tree whose rightmost leaves (perhaps all) have been removed. Some authors use the term complete to refer instead to a perfect binary tree as defined below, in which case they call this type of tree (with a possibly not filled last level) an almost complete binary tree or nearly complete binary tree.\[19\]\[20\] A complete binary tree can be efficiently represented using an array.\[18\]

Does that mean

* a complete binary tree can have at most one node with exactly a child (or can a complete binary tree has at least two nodes with just one child?)
* in a complete binary tree, a node with exactly a child can only have a left child not a right child.
* in a complete binary tree, a node with exactly a child can exist only at the level next to the last one, and at that level, all the nodes left to the node must have two children, and all the nodes right to the node must be leaves?

Conversely, do the above three points characterize a complete binary tree?

# Answer
> 2 votes
Using the definition you cite:

* A complete tree can have at most one node with one child. If there were two such nodes, then the one on the right could shift its child to the left, so the nodes in the last level wouldn't be "as far left as possible".
* Yes, if a node has only one child, it has to be a left child. Again, because otherwise the child would not be "as far left as possible".
* Yes, in a complete tree, a node with one child has to be in the second-last level. Its children are partially filled, so its children must be in the last level. Yes all the nodes to its left in the same level must have two children, and all the nodes to its right in the same level are leaves.

Finally, no, these statements do not completely characterize a complete tree. A complete tree might have no nodes at all with only one child, in which case none of these statements about one-child nodes apply to it at all.

# Answer
> 0 votes
No

A complete binary tree has a parent node with two children.

---
Tags: binary-trees
---


# Question
Title: Does a straightforward algorithm refer to the algorithm which intuitively solves a specific problem?
I'm trying to figure out what is a straightforward algorithm.

The following pseudocode comes from section 4.2 of "Introduction to Algorithms, 3rd Edition By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein"

Is it a straightforward algorithm?

Does a straightforward algorithm refer to the algorithm which intuitively solves a specific problem?

# Answer
> 1 votes
Yes, that is a straightforward algorithm.

There is no special mathematical or computational meaning that is attached to the word "straightforward" here. It just means what it means in plain English, as by Google search by me today,

> uncomplicated and easy to do or understand.

---

To be slightly pedantic, I would avoid saying "a straightforward algorithm refers to the algorithm which **intuitively** solves a specific problem". Usually, we use intuition when we rely on some instinct, heuristics or experience . The algorithm here, which computes the square of a matrix, is implemented strictly according to the definition of matrix multiplication. This implementation is completely mechanical, assuming the ability to transform a specification of a procedure into program.

"Straightforward" is, indeed, the most appropriate word to describe the algorithm.

---
Tags: terminology
---


title: Video compression algorithm

text:
# Question
Title: Video compression algorithm
I am working on a project for my CS subject and the topic is Video compression. After theoretical aspect, I want to implement and describe one algorithm that does video compression. I am not sure if these type of questions are allowed here but: what would be the best (the easiest) algorithm to implement for an entry level?

I was looking for some and couldn't find a lot of scientific papers.

# Answer
> 1 votes
You should check how JPEG works. For video compression, you have to implement how JPEG works on every frame. There is a great video on YouTube by Reducible on how JPEG works under the hood. It explains step by step how the algorithm works but you will have to code it yourself.

---
Tags: data-compression, computer-graphics
---


# Question
Title: Unique combinations of growing collection elements
Initial collection `A = [1,2,3]` should provide such combinations:

```
{(1, 2), (1, 3), (2, 3)}

```

I want to pop the first combination `(1, 2)`, so after this I can pop only from `{(1, 3), (2, 3)}`

Collection A can grow in size. How example:

```
A = [1,2,3] : {(1, 2), (1, 3), (2, 3)}
pop (1, 2) from A combinations -> A = [1,2,3] : {(1, 3), (2, 3)}
add 4 to A -> A = [1,2,3,4] : {(1, 3),(2, 3),(1, 4),(2, 4),(3, 4)}

```

I'm looking for the efficient data structure/algorithm to implement such behaviour. I'll be satisfied with both: single combination pop or iteration of all currently existing combinations. Elements can be unordered, but behaviour like heap would be better. So combination with the greater sum would be ready to be peeked first.

Also there is one optional addition. I want to combine not all elements, but only those which can be combined. In case with numbers, only elements with the same absolute value can be combined. Like `A = [-1,1,2,3] : {(-1, 1)}`. For other type of objects there is a special compare function ofc. And any object can generate all objects it can combined with.

# Answer
> 2 votes
I think you can achieve your minimum requirement by augmenting a doubly-linked list.

### Augmentation

* For each node, in addition to the $next$ and $previous$ pointer, add a new pointer $pair$. Initially, for a node $n$, $n.pair = n.next$.
* Add an $element$ field that will hold the added element to the collection.
* Add a boolean field $completed$ to each node, which is initially set to **false**.
* In addition to the $head$ pointer, add a new pointer $cur$ that initially points to the first node.

### Pop

1. If $cur$ points to the last node, then there are no more elements to pop return $null$.
2. Otherwise, if $cur.completed$ is **true** set $cur.pair$ to $cur.pair.next$ and $cur.completed$ to **false**.
3. Create $p = (cur.element, cur.pair.element)$.
4. If $cur.pair$ is not the last node, set $cur.pair = cur.pair.next$.
5. Else, set $cur.completed$ to **true** and let $cur = cur.next$.
6. Return $p$.

### Add

1. Create a new node containing the added element and add this node to the end of the linked list, updating the $next$ and $pair$ pointer of the previous last node accordingly.
2. Set $cur$ to the first node.

### Analysis

All operations take $O(1)$ time.

You can easily implement iteration with this implementation, which I will leave for you to think about. In case you want to pop a pair based on the order of the elements, maybe you can augment a BST, but I have not considered this much, but updating the $pair$ pointer will be a little tricky, I think.

# Answer
> 2 votes
The data structure stores the last value generated $(i,j)$. In order to generate the next value, iterate over all $i \< k \< j$ (where comparison here refers to the order they appear in $A$) until you find some $k$ which is compatible with $j$. If there is none, advance $j$ to $j'$, and find the first $i' \< j'$ which is compatible with $j'$, if any. If there is none, advance $j'$ again, and try again, and so on, until you run out of elements, in which case you can announce that there is no next value.

Initially, there is no last value generated, so you need a special subroutine to find the first value. This subroutine is really contained in the code for *next* described in the previous paragraph: go over all $j$ in order, and for each, attempt to find a compatible $i \< j$.

---
Tags: data-structures, sorting
---


# Question
Title: Reduction from vertex-cover to system of quadratic equations
Define $$\text{SQE}=\\{S\ |\ S\ \text{is a system of quadratic equations with real solutions}\\}$$ and $$\text{VC}=\\{G\ |\ G\ \text{is a simple undirected graph with a vertex cover}\ \leq k\\}$$

I am trying to prove that SQE is NP-hard via the reduction $VC\leq\_P SQE$.

**My attempt:**

Given a $G=(V,E)$, we want to construct some system of quadratic equations $S$, such that $G\in VC$ if and only if $S$ has real solutions.

For each $u\in V$ introduce the variable $x\_u$. We want $x\_u=1$ represent vertex $u$ being in the vertex cover and $x\_u=0$ to represent it is not. How can we capture, using a quadratic equation, the fact that in a vertex-cover every edge is covered?

For each edge $\\{u,v\\}\in E$ we introduce the following inequality. $$x\_u + x\_v \geq 1$$ However, we are not allowed inequalities. With some thought I came up with the following to replace the inequality. $$x\_u+x\_v-x\_ux\_v=1$$ This is equal to $1$ if and only if either $u$ or $v$ or both are in the vertex-cover.

However, the domain for an $x\_u$ is the reals, but we want to operate in $\\{0,1\\}$, so that each vertex is either chosen or not. Therefore, we can introduce for each $v\in V$ the following equation $$x\_v^2 = x\_v$$ which has solutions $0$ or $1$ only.

Now we just need to limit the number of vertices in the vertex-cover to $\leq k$. Using an inequality this is written $\sum\_{u\in V}{x\_u}\leq k$. I now need some quadratic function $f(x\_{u\_1}, x\_{u\_2}, ..., x\_{u\_n}) = c$ if and only if $\sum\_{u\in V}{x\_u}\leq k$. But I can't figure out what it should look like.

# Answer
Add $k$ Boolean variables $z\_1,\ldots,z\_k$ and the constraint $\sum\_{u \in V} x\_u + \sum\_{i=1}^k z\_i = k$.

(Optimization: add $\ell = \lceil \log\_2 k \rceil$ Boolean variables $w\_1,\ldots,w\_\ell$ and the constraint $\sum\_{u \in V} x\_u + \sum\_{j=1}^\ell 2^{j-1} w\_j = k$.)
> 2 votes

---
Tags: np-hard, polynomial-time-reductions, vertex-cover
---


# Question
Title: Make maze connected by removing internal walls
Recently I've stumbled upon a strange graph problem. Here is a brief description.

> Given $n\times m$ matrix with $2n + 1$ rows such that each row contains $2m + 1$ characters "+", "-", "|", "."
>
> * First, last row, and first, last column are the borders of the maze.
> * Even coordinates, e.g. (0, 0), (0, 2), are filled with "+", which you can't step on.
> * Odd coordinates are filled with ".", which is used normally for the traversal.
> * The rest of the coordinates share "|", "-", "." characters. "|" defines a horizontal wall, whereas "-" defines vertical.

The problem asks to delete a minimal number of walls, i.e. "|" and "-", in order to make the whole maze connected.

The example is given below

## Input

```
2 3
+-+-+-+
|.|...|
+-+-+-+
|.|...|
+-+-+-+

```

## Output

```
2 3
+-+-+-+
|.....|
+.+-+-+
|.|...|
+-+-+-+

```

As you can see two walls are deleted, the vertical wall having the coordinate $(1, 2) $ and the horizontal wall with the coordinates $(2, 1)$.

This problem seems like a perfect application of Disjoint Set Union, but I am not convinced that this is any right approach to this problem. Any help is much appreciated!

# Answer
> 1 votes
You can use a graph traversal algorithm such as BFS/DFS to detect the connected components, and to construct a graph in which the vertices are connected components and the edges are walls adjacent to two connected components. A spanning tree in this graph corresponds to the walls that need to be removed.

---
Tags: graphs, graph-traversal, connected-components, disjoint-sets
---