# Question
Title: Asymptotic notation between two sets of variables
I have problems interpreting the definition of asymptotic notation where the functions involve two different set of variables. I am quite confident with the definition of $f(n) = O(g(n))$ and its extension to the multivariable case ($f(n, m) = O(g(n, m))$). However I don't actually understand the meaning of $f(n) = O(g(m))$ since $f$ and $g$ work with two different variables.

If for example I have that $n = O(m)$, the intuition behind this is that $m$ *upper bounds* $n$ but I'm not quite sure how to apply the formal definition of *big O*. The first idea was to use a *dummy function* approach by defining $f(n, m) = n$ and $g(n, m) = m$ but this does not work out well.

Another idea was to assume that both $n$ and $m$ are a function of some *unknown* variables that depend on the problem at hand. In this case $n = n(x\_1, \ldots, x\_k)$, $m = m(x\_1, \ldots, x\_k)$ and $n(x\_1, \ldots, x\_k) = O(m(x\_1, \ldots, x\_k))$.

Is this right? Am I missing something?

# Answer
> 0 votes
Unfortunately, there is no standard interpretation of $f(n,m) = O(g(n,m))$ in common use in computer science. Here are some possible interpretations:

1. There exists a constant $C \> 0$ such that for all natural $n,m$, $f(n,m) \leq Cg(n,m)$.
2. There exist constant $C,N,M \> 0$ such that for all natural $n,m$ if $n \geq N$ and $m \geq M$ then $f(n,m) \leq Cg(n,m)$.
3. Some combination of the two.

---

In your case, you are describing a different use of asymptotic notation. Suppose that algorithm $A$ works in time $O(n+m)$ (under the first interpretation above).

**Claim.** If $m = O(n)$ then $A$ works in time $O(n)$.

What this really means is the following:

> For every constant $C \> 0$ there exists a constant $D \> 0$ such that if $m \leq Cn$ then algorithm $A$ works in time at most $Dn$.

The proof is quite simple. Since $A$ works in time $O(n+m)$, there exists a constant $E$ such that the running time of $A$ is at most $E(n+m)$. If $M \leq Cn$ then $E(n+m) \leq E(1+C)n$, so we can choose $D = E(1+C)$.

---

This kind of "elided quantifier" is common in theoretical computer science. For example, consider the following statement.

**Claim.** Some Boolean function on $n$ bits requires circuits of size $\Omega(2^n/n)$.

What this statement really means is one of the following:

> There is a sequence of Boolean functions $(f\_n)\_{n=0}^\infty$ such that $f\_n$ is a Boolean function on $n$ bits and if $M(n)$ is the minimum circuit size of $f\_n$, then $M(n) = \Omega(2^n/n)$.
>
> There is an infinite set $N \subseteq \mathbb{N}$, for each $n \in N$ a Boolean function $f\_n$ on $n$ bits, and a constant $c\>0$, such that for all $n \in N$, every circuit for $f\_n$ has size at least $c2^n/n$.

Once you get used to this sort of statement, such interpretations become automatic, though unfortunately, there is often some ambiguity and vagueness involved.

---

Your example of $m = O(n)$ probably comes from the world of graph theory. We say that a graph is *sparse* if $m = O(n)$, where $n$ is the number of vertices, and $m$ is the number of edges. Graph algorithms such as BFS and DFS run in time $O(n)$ on sparse graphs.

What this really means is that if we have a collection of graphs satisfying $m \leq Cn$ or some constant $C$, then BFS and DFS run in $O(n)$ *on this collection of graphs*. For example, it is known that planar graphs contain at most $3n-6$ edges. Therefore BFS and DFS run in $O(n)$ on planar graphs.

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


# Question
Title: Proving that the two definitions of Universal Class of Hash Function are equivalent (as dealt with in CLRS)
I was going throught the text Introduction to Algorithm by Cormen et. al. where I came across the two alternative definitions of *Universal Class of Hash Function*.

The versions are as follows:

> Definition 1: Let $\mathscr{H}$ be a finite collection of hash functions that map a given universe $U$ of keys into the range ${0,1,...,m-1}$. Such a collection is said to be **universal** if for each pair of distinct keys $k,l\in U$, the number of hash functions $h\in\mathscr{H}$ for which $h(k)= h(l)$ is at most $|\mathscr{H}|/m$.

Now in the above definition the authors are using "for each pair of distinct keys $k,l\in U$" to mean that probably we do not leave out any possible key pair for which collision occurs.

> Definition 2: With a hash function randomly chosen from $\mathscr{H}$, the chance of a collision between distinct keys $k$ and $l$ is no more than the chance $1/m$ which is the chance of a collision if $h(k)$ and $h(l)$ were randomly and independently chosen from the set $\\{0,1,...,m-1\\}$.

Through-out the rest of the book the author uses the second definition. I felt like finding the equivalence of the two definitions.

---

## Definition 1 $\implies$ Definition 2

---

Definition $1$ says that for a pair of distinct keys says $k,l$ for the set $A=\\{h \in \mathscr{H} : h(k)=h(l)\\}$ ,

$$|A|\leqslant|\mathscr{H}|/m \tag 1$$

Now if we chose a hash function $h\in \mathscr{H}$ at **random** then for the said pair of distinct keys $k,l$ we have,

$$ Pr\\{h(k)=h(l)\\} = \frac{\text{no. of functions in A}}{\text{no. of functions in $\mathscr{H}$}}=\frac{|A|}{|\mathscr{H}|} \leqslant\frac{1}{m} \quad\text{using (1)}$$

---

I could not quite find a way to show that: $$\text{Definition 2 $\implies$ Definition 1}$$

Or the way I proved the first implication actually proves the equivalent...

Previously I made an attempt but it was wrong as it was pointed out and so that wrong portion has been edited out.

I had found two similar questions  and  but it did not quite seem to answer my query.

# Answer
> 0 votes
Both definitions are equivalent, and I think you have almost specified the reason behind it.

The below equivalence work in both ways.

From Definition 2:

"the chance of a collision between distinct keys $k$ and $l$" $\le$ $1/m$

$\Leftrightarrow$

{note that the "chance" here is about the process of picking $h$ from the class $\mathscr{H}$}

(Number of functions in the class where $k$ and $l$ collide) $/$ (Total functions in the class) $\le$ $1/m$

$|A|/|\mathscr{H}| \le 1/m$

$\Leftrightarrow$

$|A| \le |\mathscr{H}|/m$

(which is the wording used in Definition 1)

---
Tags: hash, hashing, check-my-answer
---


# Question
Title: Textbook on formal syntax (and semantics) of programming languages
I'd like to learn about formal syntax of programming languages: how do we describe the syntax of a programming language and how it should be parsed? How do we assign formal semantics to a parsed program? I've looked at textbooks like this one, but it is very *practical*. I am looking for something more theoretical: an introduction to specifying programming languages fully formally and assigning a fully formal semantics. Is there such a book?

# Answer
> 1 votes
Maybe you will like to book Concrete Semantics (which is freely available as a PDF). It defines the syntax and semantics of an imperative programming language using the proof assistant Isabelle/HOL. In later chapters also types are added to the language and several examples of program analysis are shown.

# Answer
> 1 votes
The book Practical Foundations for Programming Languages might have what you're looking for.

An older version of the book can be read here.

---
Tags: formal-languages, programming-languages, syntax-trees
---


# Question
Title: Constraint on Universal set of hash functions
I was reading hashing from CLRS. In it author says:

> Let $\mathscr{H}$ be a finite collection of hash functions that map a given universe $U$ of keys into the range ${0,1,...,m-1}$. Such a collection is said to be **universal** if for each pair of distinct keys $k,l\in U$, the number of hash functions $h\in\mathscr{H}$ for which $h(k)= h(l)$ is at most $|\mathscr{H}|/m$.

So basically in universal set of hash functions, the number of hash functions a finite collection of hash functions is said to be universal if number of hash functions $h$ for which $h(k)=h(l)$ is at most $\frac{\text{number of hash functions}}{\text{size of hash table}}=\frac{|\mathscr{H}|}{m}$

However next the author says:

> In other words, with a hash function randomly chosen from $\mathscr{H}$, the chance of a collision between distinct keys $k$ and $l$ is no more than the chance $1/m$ of a collision if $h(k)$ and $h(l)$ were randomly and independently chosen from the set $\\{0,1,...,m-1\\}$.

I didnt get the last part "$h(k)$ and $h(l)$ were randomly and independently chosen from the set $\\{0,1,...,m-1\\}$". How $|\mathscr{H}|=$\[$h(k)$ and $h(l)$ were randomly and independently chosen from the set $\\{0,1,...,m-1\\}$\]

# Answer
Let's plug real numbers into the passage:

$|\mathscr{H}|$ = 10;

$m$ (size of hash table) = 100

**In the first statement:**

$\frac{|\mathscr{H}|}{m}$ = $\frac{10}{100}$ = 0.1 = the maximum number of hash functions that will cause a collision. (Assuming the count of functions in $\mathscr{H}$ can be represented as decimals for sake of argument.)

The important thing to note here is that the chance of selecting a collision causing hash function is: $\frac{0.1}{|\mathscr{H}|}$ = $\frac{0.1}{10}$ = 1%.

**In the second statement:**

The argument being made is that the chance of collision "is no more than..":

$\frac{1}{m}$ = $\frac{1}{100}$ = 1% = the chance of generating a hash value $h(key)$ from the set {0, 1..., 99}. AKA the chance of selecting a specific value from 100 values.

**Conclusion:**

So, from our example, a collection of 10 hash functions that map a given universe of keys into the range {0, 1..., 100 - 1} is said to be a *universal collection* if: by randomly choosing a hash function, the chance of collision between distinct keys is no more than 1%.
> 1 votes

# Answer
In the second paragraph:

"In other words, with a hash function randomly chosen from $\mathscr{H}$, the chance of a collision between distinct keys $k$ and $l$ is no more than the chance $1/m$ of a collision if $h(k)$ and $h(l)$ were randomly and independently chosen from the set $\\{0,1,...,m-1\\}$."

Here, "the chance of a collision between distinct keys", is simply specified to be $\le 1/m$.

Further the author says that, this $1/m$ is also the chance (probability) as below:

If two values (here $h(k), h(l)$) are randomly/independently picked from 0 to $m-1$, what is the chance of they being same. This is actually:

(probability that both equal certain value $i$) * (all possible values of $i$)

= $((1/m)\*(1/m)) * m$

= $1/m$

So the author is giving a meaning to the value $1/m$.
> 0 votes

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


# Question
Title: Possible unique paths to reach cell (0,n-1) from cell (0,0) given vector of must visited rows and allowed movement directions
I've been given a matrix path problem to solve and I need some hints / advises. You're given a $m \times n$ matrix where $m$ is number of rows and $n$ number of columns. When you're in a cell $(i,j)$ you can only move to cells $(i,j+1)$, $(i-1,j+1)$ and $(i+1,j+1)$. Three subproblems have to be solved. I solved first two and I'm stuck solving the third one now.

First one is to find all possible paths from $(0,0)$ to $(0,n-1)$, second one is to find all paths with given obstacles. The third one is kind of tricky. You're given a vector of must visited rows while traversing (they don't have to be sorted). For example: if you're given a vector $\[ r\_2,r\_1\]$, you have to find all possible ways to reach row 2, then all possible ways to visit row 1 after visiting row 2 and finally all paths to come to cell $(0,n-1)$ with given restrictions.

Any advises or hints for this one?

# Answer
**Subproblem 1:** Find the number of possible paths from $\[i,j\]$ to $\[k,\ell\]$ for all $i,k \in \\{0,\dotsc,m-1\\}$ and $j,k \in \\{0,\dotsc,n-1\\}$. Store them in a table $A$ of size $m$ x $n$ x $m$ x $n$. In other words, an entry $A\[i\]\[j\]\[k\]\[\ell\]$ stores the number of possible paths from $\[i,j\]$ to $\[k,\ell\]$. You can construct this table since this is similar to the second variant of your problem while considering the restrictions.

**Subproblem 2:** Find the number of possible paths from $\[i,j\]$ to $\[k,\ell\]$ that does not goes through the entries: $\[k,0\], \dotsc, \[k,\ell-1\]$, for all $i,k \in \\{0,\dotsc,m-1\\}$ and $j,k \in \\{0,\dotsc,n-1\\}$. Store them in a table $T$ of size $m$ x $n$ x $m$ x $n$. In other words, an entry $T\[i\]\[j\]\[k\]\[\ell\]$ stores the number of possible paths from $\[i,j\]$ to $\[k,\ell\]$ that does not pass through the entries: $\[k,0\], \dotsc,\[k,\ell-1\]$. You can construct this table from the entries of the previous table $A$ but it will require some more work.

**Main Problem:** Suppose the row vector is $(r\_{i\_{1}},r\_{i\_{2}},\dotsc,r\_{i\_{p}})$. Here, I am assuming the $0$ based indexing. In other words, if $r\_{i\_{j}} = 4$, it means it is the fifth row. For sake of better understanding of the solution, let me add $r\_{i\_{0}} = 0$ at the beginning of this row vector. Now, the row vector is $(r\_{i\_{0}},r\_{i\_{1}},r\_{i\_{2}},\dotsc,r\_{i\_{p}})$.

Now, we define a table $R$ of size $(p+1)$ x $n$ such that $R\[t\]\[j\]$ denote the number of possible paths from $\[r\_{i\_{t}},j\]$ (for valid $r\_{i\_{t}}$ and $j$) to the $\[0,n-1\]$ that goes through the row vector $(r\_{i\_{t+1}},\dotsc,r\_{i\_{p}})$

**Output:** The algorithm should output $R\[0\]\[0\]$ since it denote the number of possible paths from $\[0,0\]$ to the $\[0,n-1\]$ that goes through the row vector $(r\_{i\_{1}},\dotsc,r\_{i\_{p}})$

**Induction Step:**

$$R\[t\]\[j\] = \sum\_{\ell = 0}^{\ell = n-1} \Big( T\[r\_{i\_{t}}\]\[j\]\[r\_{i\_{t+1}}\]\[\ell\] \Big)\cdot \Big(R\[t+1\]\[\ell\] \Big) $$

**Base Step:** When $t$ becomes equal to $p$, we get $R\[p\]\[j\]$, which denote the number of possible paths from $\[r\_{i\_{p}},j\]$ to $\[0,n-1\]$ that does not goes through any row vector.

$$R\[p\]\[j\] = A\[r\_{i\_{p}}\]\[j\]\[0\]\[n-1\] \quad \textrm{ for all valid $j \in \\{0,\dotsc,n-1\\}$}$$

---

Since you just asked for hints, this is more than sufficient.
> 1 votes

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


title: complexity - Non Polynomial reduction

text:
# Question
Title: complexity - Non Polynomial reduction
I have a question, does non-polynomial reduction exists for all problems? the issue is only regarding polynomial reductions?

# Answer
You can show that it is not the case that every two languages are reducible to each other using a counting argument. Consider the class of all languages $ 2^{\Sigma^\*}$. If by contradiction every two languages are reducible to each other, then every language is an $2^{\Sigma^\*}$-hard language (in particular, there is a language that all languages reduce to). One can show that there are more languages than reductions. Thus, an $2^{\Sigma^\*}$-hard language must have two different languages that reduce to it using the same reduction, but this is impossible.

More formally, assume by contradiction that there is an $2^{\Sigma^\*}$-hard language $L$. We know that there are $2^{\aleph\_0}$ languages, yet, as there are only $\aleph\_0$ TMs, there are also only $\aleph\_0$ reductions. Then, it follows that there are distinct languages $A$ and $B$ such that $A \leq\_m L$ and $B \leq\_m L$, but the reductions from $A$ and $B$ to $L$ coincide. Denote this reduction by $f$. Since $A\neq B$, there exists w.l.o.g a word $x\in A\setminus B$. Since $f$ is a reduction from $A$ to $L$, we get that $f(x) ∈ L$. But $f$ is also a reduction from $B$ to $L$, and thus we get that $f(x) \notin L$, and we reached a contradiction.
> 1 votes

# Answer
What type of reduction are you are talking about? The statement is false for Karp (many-one) reductions. Take $\mathcal L=\emptyset$. For any language $\mathcal L'\neq \emptyset$, $\mathcal L'$ cannot reduce to $\mathcal L$ by a computable algorithm $f$ because the condition $\forall x\in \Sigma^\*:x\in\mathcal L' \iff f(x)\in \mathcal L$ does not hold as $f(x)\in \mathcal L$ is false but $x\in \mathcal L'$ is true for some $x$.

(The same works with $\mathcal L=\Sigma^\*$ and $\mathcal L'\neq \Sigma^\*$.)
> 1 votes

---
Tags: complexity-theory
---


# Question
Title: A language is decidable iff it is Turing-recognizable and co-Turing-recognizable (WHY?)
I am trying to understand the proof for this theorem (theorem 4.22 of the book 'An introduction to the theory of computation'):

```
A language is decidable iff it is Turing-recognizable and co-Turing-recognizable.

```

The first direction is OK. But the other is not, namely:

What I don't understand is why the author assumed that M will halt. We have that A is Turing-recognizable, and thus we are not sure we have a machine that decides it (and thus halts). Same for the complement of A which is also Turing-recognizable.

Thanks in advance

# Answer
> 0 votes
Since both $A$ and $\overline A$ are *recognizable*, you know that for any input $x$, either

1. $x \in A$, which means that $T\_A$ will halt on input $x$, or
2. $x \notin A$, which means that $x \in \overline A$ which means that $T\_{\overline A}$ will halt on input $x$.

The "trick" here is to run $T\_A$ and $T\_{\overline A}$ "simultaneously", which means that if any of $T\_A$ or $T\_{\overline A}$ halts after $k$ steps, then your new machine will halt after $2k$ steps.

---

If you don't like "simultaneously", you can for each integer $i$ from 0 and up, run $T\_A(x)$ for $i$ steps, then run $T\_{\overline A}(x)$ for $i$ steps.

The latter is simpler to "program" on a single-taped Turing machine, but the former is quite okay to implement on a two-taped Turing machine.

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


title: Relation is in 2NF or not?

text:
# Question
Title: Relation is in 2NF or not?
Consider a relation R(A,B,C,D,E) and the only FDs,

ABD-\>C

BC-\>D

CD-\>E

These are the only 3 FDs. I want to know if the above relation is in 2NF or not.

According to the definition of 2NF, a relation to be in 2NF, it should be in 1NF and it should not have partial dependency.

But I'm not getting the partial dependency concept.

Somewhere it's written that when a proper subset of a key determines a non-prime attribute then it is partial dependency.

Somewhere it's written that when a prime attribute which is not a key determines a non-prime attribute then it is partial dependency.

Because of these 2 different definitions I'm getting confused.

Please help.

# Answer
> 0 votes
Second normal form means that each non prime attribute must not depend on a proper subset of a candidate key.

In your example, assuming that the given FDs are a cover of the FDs of the relation, you have two candidate keys, `ABC` and `ABD`. Moreover, the attribute `E` depends on `BC`, which is a proper subset of the candidate key `ABC` (you can verify this by computing the closure of `BC`, `BC+`, and see that `E` belongs to that closure).

So the relation is not in 2NF.

---
Tags: database-theory, databases, normal-forms, functional-dependencies
---


# Question
Title: What is the Number of epochs with no improvement after which training will be stopped.?
I am trying to make a Convolutional neural network. Training the images of different brands of Logos. Have 100 images per class and there are 40 classes. I have trained the model now want to check that model is overfitted or not . What should be the number of epochs we will se that with no improvement after which training will be stopped . Should I see after 2, 3 or which number ?

# Answer
> 1 votes
The number of iterations with no improvement is a hyperparameter. Scikit-learn has a default value of 10 in the MLPClassifier but of course you can select one depending on your problem. You can also do a grid search over all your model's hyperparameters.

Another advice I would give is that you could first train the model experimentally for a lot of epochs. If you see it getting stuck for a lot of iterations and then increasing after a halt, then it's better to set a higher value. On the other hand if after a lot of time you don't see it improving you should set the max number of iterations with no improvement to a smaller value.

---
Tags: algorithms, optimization, machine-learning, trees, neural-networks
---


title: Lower bound on multiplication

text:
# Question
Title: Lower bound on multiplication
I was told that the fastest possible algorithm for integer multiplication is $O\left(n{\log}(n)\right)$. Why would this so?
Can you please show why the fastest multiplication algorithm would have such a time complexity?

# Answer
Multiplication of n-bit integers can be done in $O (n \log n)$ if you are a bit careless in calculating the complexity, for example using convolution and FFT. You need $O (n \log n)$ floating point operations, but as n grows larger, you need to increase (very slowly) the precision of the floating-point operations, which will increase the complexity a little bit.

It is very well possible that no algorithm can be faster than $O (n \log n)$. It is a bit more possible that we will never find such an algorithm. However, I'm not aware of anything coming even close to a proof.

Proofs for lower bounds that turn out to be actually achieved are usually either very simple or nonexistent. For example the proof that sorting n items using comparisons takes $O(n \log n)$ is quite simple. When someone writes "multiplication cannot be done faster than $O(n \log n)$", that most likely means "I have not the slightest idea how this could be done".
> 1 votes

# Answer
There is a lower bound for multiplication of $\Omega(n\log{n})$ conditional on a conjecture in network coding. There is also an algorithm matching this bound.
> 3 votes

---
Tags: algorithms, runtime-analysis, multiplication
---


# Question
Title: Optimization problem over bidirectional connected graph
A company has several automatic vertical warehouses (called *elevators*). Each elevator have several *trays* and each *tray* has several *slots*. A slot contains a given quantity of a given article. Elevators, trays and slots are identified by unique IDs and slot also have access to the ID of their own article. In the same tray there can be multiple slots with the same article.

# Example:

*tray A* contains

* *slot SA1* with 5 items of article *X*;
* *slot SA2* with 10 items of article *Y*;
* *slot SA3* with 3 items of article *Z*

*tray B* contains

* *slot SB1* with 12 items of article *Y*

tray C contains

* *slot SC1* with 4 items of article *X*;
* *slot SC2* with 15 items of article *Z*;
* *slot SC3* with 8 items of article W

trays A, B and C belong to the same elevator.

——————————————————

I have to design an algorithm which, given an order list (we can model it as a dictionary with articles' IDs as key and quantity needed as values), returns the **minimum list of trays needed to satisfy the order**. That is, find the smallest (in terms of cardinality) set of tray whom slots contain a sufficient quantity of each articles listed in the order.

This is quite different from a standard warehouse optimization problem because we are not considering the physical distances between each tray, since the elevators are automatic and they give us the tray, while in the classical problem is the human who moves toward the tray to pick the item from it.

After reading through articles about warehouse optimization, I've decided to take an heuristic approach.
I've modeled a sort of euclidean space, with an axes for each article contained in the order. Then we can consider a tray as a point on that space, with coordinates for each axes equal to the quantity that tray has of the article corresponding to that axes. In the same way we can imagine our order as a point.
Then I've create a heuristic function, **$f(order\ o, tray\ t)$**, which returns the "euclidean distance" from *point-tray* $t$ to the *point-order* $o$. The idea is that the more a tray is "near" the order, the more article we can pick out of it.

So, to satisfy the order, I simply compute **$f(order\ o, tray\ t)$** for each tray in every elevator. Then I order it by descending value and finally I ***greedily*** take a tray with the minimum distance from the order. This will be repeated until we collect enough articles to satisfy the order.

I've tried to build a graph in which each node is a tray and is connected to each of the others by a directed edge. The weights of the edge from node $i$ to node $j$ will be equal to the heuristic function computed on tray $j$.

$w\[i, j\] = f(order, j)$

This results in a fully-connected, bidirectional graph (each node linked with each other node by both an incoming and an outgoing edge). I want to apply some algorithm of shortest path (or any other useful algorithm) taken from graph theory on this graph but I couldn't find anything really helpful.

Is there any algorithm I can apply on such a graph? Or maybe the graph is not the right structure to represent my problem. I'm open to new solutions.

# Answer
This is the special case of the multidimensional knapsack problem where each item (tray) has the same value (consider the set of trays you *don't* select). It presumably remains NP-hard, but can be solved by a number of methods. Probably the easiest to try first is to formulate this as an instance of integer linear programming and then apply an ILP solver to it.
> 2 votes

---
Tags: algorithms, graphs, data-structures, optimization, heuristics
---


# Question
Title: For s set $S\subseteq RE$, so call feature of language $S=\emptyset$ vs. $S=\{\emptyset\}$
I'm trying to understand what's the difference between $S=\emptyset$ and $S=\\{\emptyset\\}$
The diffenition that I found for $L\_S=\\{\langle M\rangle\ | L(M)\in S \\}$
I understood that $S=\emptyset$ and $S=RE$ are trivial and
$S=\emptyset \Rightarrow L\_\emptyset=\emptyset\in R$
$S=RE \Rightarrow L\_{RE}=\Sigma^\*\in R$

But can't understand what's going with $S=\emptyset$ and $S=\\{\emptyset\\}$

# Answer
> 1 votes
Assume that all languages are over the alphabet $\Sigma$. What you have here is a bit of ambiguity in the meaning of $\emptyset$ (recall that the emptyset is defined w.r.t a universal set, and here $\emptyset$ is used w.r.t different universal sets). Indeed, $S = \\{ \emptyset\\}$ refers the set of languages containing only the empty language, that is, in this case, $\emptyset\subseteq \Sigma^\*$. Also, $S = \emptyset$ refers to the empty set of languages, that is, in this case $\emptyset\subseteq 2^{\Sigma^\*}$.

As you noted, if $S = \emptyset$, then $L\_S = \\{ \langle M\rangle: L(M)\in \emptyset\\} = \emptyset \in \text{R}$. Now if $S = \\{ \emptyset\\}$, then $L\_S = \\{ \langle M\rangle: L(M)\in \\{\emptyset\\}\\} = \\{ \langle M\rangle: L(M) = \emptyset\\} = E\_{TM}$ which is known to be in $\text{coRE}\setminus \text{R}$.

---
Tags: complexity-theory, formal-languages, computability
---


title: Is $E^{quasiP}$ equal $E$ or larger?

text:
# Question
Title: Is $E^{quasiP}$ equal $E$ or larger?
Let $quasiP$ be the quasipolynomial time complexity class.

1. Is $E^{quasiP}=E$ false?
2. Is $E^{DTIME(2^{(\log n)^k})}=E$ false at every $k\>1$?

# Answer
> 0 votes
Suppose that $T(n) = n^{\omega(1)}$, and consider the complexity class $\mathsf{E}^{\mathsf{DTIME}(T(n))}$. Given a Turing machine $M$ and an input $x$ of length $n$, an $\mathsf{E}^{\mathsf{DTIME}(T(n))}$ machine can write $1^{2^n}$ and then ask the oracle whether $M$ halts on $x$ within $T(2^n)/\log T(2^n) = 2^{\omega(n)}$ steps. This cannot be done in $\mathsf{E}$ according to the time-hierarchy theorem.

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


# Question
Title: What's the average number of transistor switches needed to do an N-bit x N-bit multiply?
I want to know how switch-efficient a multiplier can be. If I need to do many $N$-bit by $N$-bit multiplies, and each bit is determined by flipping a coin, what's the average number of transistor switches that will be required per multiply, in terms of $N$?

# Answer
> 1 votes
I haven't edited my question, but in case others are here: this thesis addresses the question I was intending (https://core.ac.uk/download/pdf/52104064.pdf), finding e.g. 1189 average transitions required for a certain architecture for a 16-bit by 16-bit multiply that's completely random bits. \

---
Tags: algorithms, computer-architecture, logic, arithmetic, boolean-algebra
---


title: How to avoid monochromatic cycles?

text:
# Question
Title: How to avoid monochromatic cycles?
I am working on the following exercise:

> Consider a simple and connected undirected graph $G(V,E)$. Show that one can colour the edges of $G$ in polynomial time and with as few colours as possible such that there is no monochromatic cycle in said colouring of $G$.

EDIT 1: OK, my approach turned out to be false. I will leave it here for the sake of completeness. Now I have no idea how to solve this exercise. I guess the following theorem might be helpful:

> Theorem: For any undirected simple graph $G(V,E)$ we can decide whether the edge chromatic number is less than $3$ and if yes we can find this optimal colouring in polynomial time.

EDIT 2: I have reread my lecture notes. This exercise is probably meant to be solved with tools from matroid theory. I just do not see how.

---

My WRONG approach:

I think that 2 colours should be sufficient. (Remember that this is not the classical edge colouring problem, we just want to avoid monochromatic cycles.) My first idea is to formulate a simple greedy algorithm:

1. Colour all edges in red.
2. Check the graph for cycles. If there is a cycle delete one edge of the cycle from the graph. Repeat this step until there are no more cycles in $G$.
3. Colour the deleted edges in blue.

However, the problem with this approach is that the blue edges may form a cylce as the example below shows. While the example below can easily be fixed by recolouring two edges I am not sure if this fix works in general. Could you please give me a hint?

# Answer
> 2 votes
What you are trying to do is find the arboricity of the graph, or equivalently compute the minimum partition into independent sets in the graphic matroid. This problem (for a general matroid) is known as the Matroid partitioning problem, for which polynomial-time algorithms exist.

You can find more details in Harold N. Gabow and Herbert H. Westermann, Forests, frames, and games: Algorithms for matroid sums and applications.

---
Tags: graphs, colorings
---


# Question
Title: How can a deterministic or non-deterministic automaton accept the language of square strings?
I don't know how to prove or show the following fact.

$\quad$ $\\{xx|x \in \Sigma^\ast\\} $ can be accepted by a queue automaton.

If it would be possible, show by deterministic queue automaton. If not, by non-deterministic queue automaton.

If it's not that hard and if I can, please give me a hint.

# Answer
> 1 votes
Working with a queue automaton for me is intuitively equivalent to working with a circular tape.

Read the input $w$ from the automaton, and put it on the tape. Add two markers $A$ and $B$, so we obtain $Aw\_1Bw\_2$. Now we can one by one eat a letter after $A$ and one after $B$.

For the deterministic variant it suffices to put $B$ exactly in the middle of the input string. That position can be found using a method similar to this: How to find middle element of linked list in one pass?

---
Tags: turing-machines, automata, nondeterminism
---


# Question
Title: NSA Recommended Cryptography Algorithms changes from a single paper
I know that the NSA has recommended cryptography algorithms, such as their A/B suite algorithms and their Commercial National Security Algorithms Suite. I also know that they change their recommendations for key size, an example being in 2019 when they changed the key size recommended for RSA and Diffie Hellman from 2048 to 3072.

Are there any examples of changes like this that have been directly prompted by the publication of a mathematical paper or the creation of an algorithm? When people ask me about the applications of prime numbers to cryptography I want to be able to cite a specific time where math has changed real word cryptography recommendations.

# Answer
> 1 votes
There are *many* examples in cryptography. Much of progress in cryptography is driven by academic research.

The Advanced Encryption Standard (AES) was a result of a request for research from the National Institute of Standards and Technology. Two cryptographers proposed a new algorithm, which was eventually adopted as the standard. A bit over a year ago NIST released a report estimating that there was $250 billion in economic benefit from the AES standard. This can be directly traced back to academic research. This doesn't involve prime numbers or number theory, though.

Key sizes and algorithm design typically comes out of academia. The RSA algorithm was created by academics who published a research paper proposing the algorithm (which in turn built on prior research from others, such as Hellman and Diffie), and has been extremely widely used to protect digital infrastructure -- including secure browsing and other uses.

Research has played a major role in setting parameters and key sizes for cryptographic algorithm; see, e.g., https://en.wikipedia.org/wiki/Key\_size for a number of examples.

Caveat: many of the researchers doing this work might self-identify as computer scientists more than mathematicians. But the lines between theoretical computer science and applied mathematics in this area are blurry.

---
Tags: cryptography
---


# Question
Title: How to prove the optimality of the "patience sort" algorithm?
I was trying to understand how we can solve the Longest Increasing Subsequence (LIS) problem in O(N log N) time. I came across a sorting algorithm called the **patience sort** algorithm. To learn it I was going through this document:

https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/LongestIncreasingSubsequence.pdf

I couldn't understand how the optimality was proved - i.e. why this algorithm leads to a minimum number of piles and correspondingly why it leads to the maximum length increasing subsequence.

In the above document from the **weak duality** principle (see pg. 5) we can understand that the **number of piles ≥ length of any increasing subsequence**.

Weak duality principle:

How can we use the above principle to prove the **strong duality** principle (see pg. 6)? If we can prove this, we will have proved the optimality.

Strong duality principle:

Thanks for the help.

# Answer
The weak duality principle says that given any play of patience solitaire, the number of piles (at the end) is no less than the length of any **I**ncreasing **S**ubsequence (IS) of the initial sequence of cards.

In particular, the min number of piles is no less than the length of the longest IS of the initial sequence of cards. That is, the weak duality implies the following direction of the strong duality:
$\quad$ Min number of piles $\ge$ max length of an IS.

---

**Claim**: We have
$\quad$ Min number of piles $\le$ max length of an IS.
**Proof**. Instead of proving using variables that represent general situations, I will use proving by illustration, which should convince a reasonable human.

Look at this picture, which is also embedded in the question. It shows the situation at the end of patience solitaire using greedy algorithm, starting with sequence 6,3,5,10,J,2,9,A,K,7,4,8,Q of spades.

Consider the queen of spades. At the time when it was to be placed on the last pile, it must appear later than all cards in the previous piles in the initial sequence (since cards were dealt in order). We must also have verified that it was larger than all uncovered cards in the piles before the last pile. In particular, it must be larger than the uncovered card in the second last pile, which was the 8 of spades. So, we have
$\quad$ $8,$ Q
as an IS of the initial sequence.

Consider the 8 of spades. At the time when it was to be placed on second to last pile, it must appear later than all existing cards in the piles to its left in the initial sequence (since cards were dealt in order). We must also have verified that it was larger than all uncovered cards to its left. In particular, it must be larger than the uncovered card immediately to its left, which was the 7 of spades. So, we have
$\quad$ $7, 8$
as an IS of the initial sequence.

Consider the 7 of spades. At the time when it was to be placed on third to last pile, it must appear later than all existing cards in the piles to its left in the initial sequence (since cards were dealt in order). We must also have verified that it was larger than all uncovered cards to its left. In particular, it must be larger than the uncovered card immediately to its left, which was the 5 of spades. So, we have
$\quad$ $5, 7$
as an IS of the initial sequence.

And so on.

In the end, combining all ISs obtained, we will have,
$\quad$ $3,5, 7, 8,$ Q,
as an IS of the initial sequence.

We can see that every pile contributes exactly one item to the IS. Hence, the number of piles is the same as the length of that IS. So, the number of piles (at the end of greedy algorithm) is at most the length of the longest IS of the initial sequence.

So, the min number of piles for all playing strategies, including the greedy algorithm, is at most the length of the longest IS of the initial sequence. $\quad \checkmark$.

The proof above is basically an expansion of the instruction, "follow pointers to obtain IS whose length equals the number of piles" in the lecture note from Princeton quoted in the question. By the way, we can also use the subsequence $3,5,10,$ J, A or one of many other subsequences to the same effect.

---

Combining both "$\ge$" and "$\le$", we should obtain the equality in the strong duality. Moreover, the proof above shows the greedy algorithm finds both numbers (or, that one number).

---

**Exercise** (easy): Let $P\_1, P\_2, \cdots, P\_k$ denote the piles we have obtained at the end of the greedy algorithm in its natural order. Show that card $c$ is in $P\_i$ iff the longest IS of the initial sequence that ends at $c$ is of length $i$.
> 4 votes

---
Tags: sorting, correctness-proof
---


# Question
Title: reduction from SET-COVER to VERTEX-COVER
I've come with an idea for reduction from the set-cover problem to the vertex-cover problem, But I'm not sure if this reduction is correct. I saw in this post's comments that "There cannot be a nice reduction of this sort".

Consider the set of $S$ to be $S\_1,...,S\_n$ where the element of $S$ is $s\_1, ..., s\_m$. In the graph $G=(V,E)$ for each $S\_i$ there is a vertex, and an edge from $S\_i$ to $S\_j$ will be iff there is some element $x\in S\_i \land x\in S\_j$.

is this reduction even right?

# Answer
No, since  $\\{\\{0,1\\},\\{1\\}\\}$  and  $\\{\\{0,1\\},\\{1,2\\}\\}$  yield isomorphic graphs.

But the sizes of their minimum set covers are different.
> 5 votes

# Answer
Another reason which may help understanding why this reduction (from Set Cover to Vertex Cover) is not possible is as follows. See the slide below (taken from Kleinberg, Tardos).

Here, a single element (represented as an edge) appears in exactly two sets (nodes). If this was not the case (and an element appeared in less than or more than two sets), drawing such a graph would not be possible (an edge can only have exactly two ends (nodes)).

Going from Vertex Cover to Set Cover is easy because Vertex Cover is applied on a graph that already exists (we do not need to draw a graph).

**Edit** (by Discrete lizard): Constructing such a graph from arbitrary sets is possible, but then there must be multiple edges representing the same element. The construction of a graph fails for another reason: there may be at most one edge for every pair of nodes, which need not be the case for arbitrary sets.
> 1 votes

# Answer
A special case of set cover problem is able to do this reduction.

Let 2SC be the Set Cover problem restricted to instances where each item appears in at most two sets.

Given instance $\langle U,S={S\_1,S\_2,\ldots}\rangle$, reduction from 2SC to vertex cover: create an edge for each elements in U where each edge in $S\_i$ share a common endpoint $v\_i$. Then, U is transformed to the universal set of edges, $S\_i$ is the adjacent neighbors of $v\_i$. Pick $S\_i$ in 2SC is equivalent to pick $v\_i$ in vertex cover.

Actually, 2SC and VC are equivalent.
> 0 votes

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


# Question
Title: Non-trivial difference(s) between Computer Algebra System and Proof Assistant
Disclaimer: I am not even an expert *user* of these two kinds of software.

I understand that the trivial difference between proof assistants and CAS is that in proof assistants, the goal is to show that the given proposition reduces to a tautology. Whereas CAS are used to perform various transformations on mathematical expressions to find results that are useful.

When we are doing mathematics on paper, the techniques used while deriving something are not all that different from the techniques used while proving something. In each case, we start with an expression, and apply one (previously established) rule after another, until we reach our goal. As far as I know, the rules that are applied in derivations are exactly the same as the rules applied while proving something. Looking at it in another way, the *human* skills honed on derivations are perfectly applicable while performing proofs.

When comparing computer systems, the list of computer algebra systems has no titles in common with the list of proof assistants. From my lay perspective, to name a specific example, I think we can use CAS to derive the roots of a generalized quadratic equation, but only when we have the formula, can we use a proof assistant to verify it.

So, given the vast amount of mathematical knowledge encoded in the libraries of both CAS and proof assistants, why can't we use a CAS to perform proofs, and why can't we use proof assistants for deriving anything beyond tautologies?

# Answer
> 4 votes
There are two major differences: CAS and proof assistant tend to focus on different application domains, and they tend to take a different position on correctness vs ease of deriving results.

Most CAS focus on scientific calculations: calculations that are useful to physicists, to chemists, to mechanical engineers, to roboticists, etc. Proof assistants tend to focus on mathematics, computer science and software engineering.

In a proof assistant, it is crucial that you can only derive true propositions. That's the whole point. In contrast, CAS usually have hidden assumptions. For example, you might derive equations that are only true if one of the variables is nonzero, or if some intermediate result is nonnegative. These assumptions are not always explicit. When modelling a real-world problem, these assumptions are usually justified by the physics – if `T` is a temperature, there's no point in wondering what the equations would look like for `T < 0 K`.

Some systems can be classified as both CAS and proof assistants because they make all such assumptions explicit.

There's a good reason why CAS take shortcuts: it makes them easier to use for their application domain. When you work in a proof assistant, you often spend a lot of effort directing the computer to the "interesting" path. You have to figure out that at this step, `x>=3`, so you guide the proof by telling the proof assistant to consider the cases `x<3` and `x>=3` separately, then you repeat with `y+z>x`, and so on. A proof assistant gives results that are true for all inputs, but the cost of that is that you have to make the proof work for all inputs. A CAS can give results for *general* inputs, which is generally good enough for physics and physical engineering (basically, anywhere that's modelled by continuous mathematics – as opposed to software engineering which is typically modelled by discrete maths and there's no such thing as general inputs).

---
Tags: proof-assistants, computer-algebra
---


title: Algorithm for sorting within windows

text:
# Question
Title: Algorithm for sorting within windows
I am writing an app which displays speeches on various topics, with each speech having a number of attributes. I want to give the user the choice to sort a list of speeches by an attribute, even within a previously sorted list of speeches.

**Consider for example**: Suppose the previous list had been sorted by the attribute: *"speaker's name"*, and there were three different speakers (so the list was split into three windows with each window consisting of the same *speaker*). Now, the user wants to sort the speeches based on the attribute: *"length of the speech"* such that the new list would now be sorted by *speaker's name*, and within each window of the *speaker's name*, the speeches would be sorted by the *length* (creating a new window within this window for each length of speech in the speaker's window).

I would like to give the user the ability to do this with an arbitrary number of attributes. How can I go about doing such sorting, preferably in the most efficient way?

P.S: I am just a teenage programmer who has been programming for a few years and can understand algorithms in concrete steps - I have not taken college classes in CS, so please keep that in mind when explaining the algorithms.

# Answer
What you require is the **lexicographic** ordering. Let me describe this.

Suppose the speeches have two attributes. The first one is "*speaker's name*" and the second one is the "*length*". For simplification, let me define the *speaker's name* by the integer value instead of a character string. Now, suppose the speeches are represented using the following tuples: $(0,0)$, $(1,2)$, $(0,3)$, $(1,4)$, $(2,3)$, $(2,4)$, and $(1,1)$. Here, the second speech has the speaker's name: $1$, and length $= 2$.

**Requirement 1:** You simply want to sort the speeches by the "*speaker's name*".

Just consider the first attribute for comparing any two speeches and apply any sorting algorithm. You will get the following ordering: $(0,0)$, $(0,3)$, $(1,2)$, $(1,4)$, $(1,1)$, $(2,3)$, and $(2,4)$.

**Requirement 2:** You want to sort first by the "*speaker's name*" and then by the "*length*". This is the requirement that you have mentioned in your question.

Now, define a *new* comparison operation between two tuples as follows: $(a,b) \< (c,d)$ if and only if $(a\<c)$ or $(a = c$ and $b\<d)$ Here, we are comparing by giving the "first attribute" more priority. And if the first attribute value is the same, we compare based on the "second attribute".

Smilarly, you can define $(a,b) \> (c,d)$ if and only if ($a\>c$) or ($a = c$ and $b\>d$).

Now, you can simply use any sorting algorithm by replacing the standard comparison operation with the above-defined comparison operation.

You will get the following ordering: $(0,0)$, $(0,3)$, $(1,1)$, $(1,2)$, $(1,4)$, $(2,3)$, and $(2,4)$.

**Requirement 3:** Suppose, you want to sort by the *length* and then by the *speaker's name*

Simply, define the comparison operation between two tuples as: $(a,b) \< (c,d)$ if and only if $(b\<d)$ or $(b = d$ and $a\<c)$. Now, again you can use any standard sorting algorithm by replacing the standard comparison operation with this comparison operation.

You will get the following ordering: $(0,0)$, $(1,1)$, $(1,2)$, $(0,3)$, $(2,3)$, $(1,4)$, and $(2,4)$.

---

Similarly, you can define a new comparison operation for the multiple attributes based on your requirements.
> 1 votes

---
Tags: algorithms, sorting, algorithm-design
---


# Question
Title: A question about the work per recursive call in FPT vertex cover of size k algorithm
I have been looking at the FPT(Fixed Parameter) algorithm for checking if a vertex cover of size k exists.The algorithm goes as follows:

VertexCoverFPT$(G, k)$

if $G$ has no edges then return true

if $k=0$ then return false

let $uw$ be some edge of $G$

if VertexCoverFPT$(G-u, k-1)$ then return true

if VertexCoverFPT$(G-w, k-1)$ then return true

return false

Its said that this algorithm has $2^k$ recursive calls each with $O(n)$ of work in each recursive call. My question is how is it that there is only $O(n)$ work in each recursive call when we need to create the 2 graphs ${G-u}$ and ${G-v}$ (u and v are the vertices we are currently checking) which takes $O(V+E)$ time (Doing a deep copy of graph G excluding the node and the edges connected to it). Is there a more efficient way than constructing ${G-u}$, ${G-v}$ from G or am I missing something?

# Answer
> 2 votes
You do not need to create any new graph.

You can simply maintain an additional array $VT$ of size $|V| = n$ such that $VT\[i\] = 1$ if the vertex $i$ is deleted from the graph. Otherwise, $VT\[i\] = 0$.

While accessing an edge $(i,j)$, first the algorithm can check if $VT\[i\]$ and $VT\[j\]$ are both $0$ or not. If both are $0$ then the algorithm access that edge. Otherwise, it does not.

In addition to it, maintain the count of edges a vertex $i$ is currently connected to. Suppose the count is stored in an array $C$ of size $n$. In the beginning of the algorithm $C\[i\]$ is initialized to the $degree(i)$.

---

**Accessing an Undeleted Edge:** Go to the adjacency list of that vertex which has $VT\[i\] = 0$ and $C\[i\] \neq 0$. Since we know that at least one edge in the list is not deleted, the algorithm will find an undelete edge in $O(n)$ time. Updating the count array after deleting a vertex takes $O(n)$ time. Overall operation is $O(n)$ time.

---
Tags: graphs, vertex-cover
---


# Question
Title: How to position images within a canvas while avoiding overlapping
I have a canvas. On this canvas, I want to position 1, 2 or 3 images. The images can be positioned anywhere on the canvas just as long as they're within the canvas. The images move by their top-left corner. To make sure that the images do not leave the canvas, I am doing this:

```
image_topLeft_x_position = random.randint(0, (canvas_width - logo_width))

image_topLeft_y_position = random.randint(0, (canvas_height - logo_height))

```

I can save these locations in a list of tuples like this:

```
locations = [(image_topLeft_x_position, image_topLeft_y_position)]

```

After saving a location, I want to generate new locations within the canvas that don't overlap with the previous ones. However, I've been stuck on this problem for well over a day. Any help is appreciated.

# Answer
If there is a place for the new image to fit, there must be a place where the left edge of the new image is aligned with either the left edge of the canvas or of some previous image. The same true for the top edge of the new image. So, if you've already placed 2 images, you only have to try 3 possibilities for the left edge and 3 possibilities for the top edge, or a total of 9 candidate positions in total. Given a candidate position, you should be easily able to test whether a new image can be placed there without overlapping any prior image.
> 1 votes

---
Tags: algorithms, randomness, python
---


# Question
Title: RSA Encryption for specitic messages x with x = ap mod pq for ap-bq=1
I want to make a following proof but I got some difficulties with it. Would be super if you people have any tips / advises.

**Introduction:**

Let (N,e) be our public key and (N,s) our private key with $N=pq$ and $ggT(\varphi(n),e)=1$, as well as $es\equiv 1\mod N$.

I want to show that since Lemma of Bézout shows, that there are $a,b\in \mathbb{N}$ so that $ap-bq=1$, the message of $x=ap\mod N$ is equal to the encrypted message $y=x^e \mod N$.

**My Plan:**

I started by using the Chinese remainder theorem. To show $x\overset{!}{=}y=x^e\mod N$ we need to show, that $x\overset{!}{=}x^e\mod p$ and $x\overset{!}{=}x^e\mod q$. I could also use the Chinese remainder theorem on $x=ap\mod N$.

So I need to show, that $ap \mod p=(ap)^e\mod p$. Since ap is a multiple of p, it should be $ap\equiv 0\mod p$ and so $(ap)^e=0\mod p$. It follows that $ap\mod p=(ap)^e\mod = p= 0 \mod p$.

I now need to show, that $ap\mod q=(ap)^e\mod q$. This is the part I am struggling with. I know that $ap-bq=1$ but I have no glue how this is going to help me. I was thinking about something like $ap=(bq+1)\mod q$ but i am not sure if this works / what to do next.

# Answer
> 0 votes
You can show that $ap\mod q =(ap)^e\mod q$ by using the fact, that $ap-bq=1\Longleftrightarrow ap=bq+1$.

You know that $q|bq$ and therefor $ap\mod q = bq+1\mod q \equiv 1\mod q$.

This implicates that $(ap)^e\mod q = (bq+1)^e\mod q \equiv 1\mod q$. Therefor $ap\mod q \equiv (ap)^e\mod q.$

Now with the chinsese remainder theorem we know that $ap\equiv\_N(ap)^e$.

---
Tags: primes, modular-arithmetic, encryption
---


# Question
Title: 2-3 tree: Sum of leaves in a given range
I am implementing a `2-3 tree`, where every leaf has a unique key and a value, and I need to write an algorithm which finds the sum of values of the leaves which their key is within a given interval. The time complexity of the function needs to be $O(\log n)$.

I thought about saving for each internal node the sum of the leaves in its subtree, but I don't know how to continue from there.

# Answer
Storing the sum for internal nodes is a good plan.

For every query you also need to search for the two bounds of the interval, and find the leftmost and rightmost leaf with elements in the interval. (The bounds themselves do not need to be in the tree.) The two search paths will split a a certain node. Continue there. While searching for the leftmost leaf you include all sums to the right.
> 1 votes

---
Tags: algorithms, trees
---


# Question
Title: How can recursion tree split a problem into smaller pieces that do not add up?
If I have a recurrence equation: $$T(n) = 3T\big(\frac{n}{4}\big) + cn^2$$

It says it splits a problem of size n into 3 subproblems of size n/4. Then it keeps splitting it until the problem size at the leaves is 1 or less. The first part that does not make sense to me is how can you split a problem of size n into 3 problems of size n/4. To me it seems that there are now 3 problems of size n/4, but where is the remaining 1/4 of n? Who is solving that?

Also, the number of leaves is $$n^{\big(\frac{loga}{logb}\big)}$$ Assuming n=1000, it can be calculated that there are 235 leaves. So 235 problems of size 1 are solved, how are the rest of 765 solved?

I have a feeling that I have misunderstood some principle, but I do not know what exactly.

# Answer
Here is a very simple example: binary search.

We are looking for an element $x$ inside a sorted array $A$. We compare $x$ to the element at the middle $m$ of $A$. If $m = x$, we're done. If $m \> x$, we recurse on the left half, and if $m \> x$, we recurse on the right half. The recurrence for the worst-case running time is $$ T(n) = T(n/2) + O(1), $$ whose solution is $T(n) = O(\log n)$.
> 1 votes

---
Tags: recurrence-relation
---


# Question
Title: Characterization of computationally universal functions
Is it correct to state that $u$ is a universal function if and only if

$$ \forall f : \text{RE} \quad \exists g : \text{R} \quad \exists h : \text{R} \quad f = h \circ u \circ g $$

where RE is the set of recursively enumerable functions and R is the set of recursive functions? (Should R be replaced with something like PR?) If so, does anyone know of a reference that states universality in this generic form?

### Defining "universal function"

I suppose we could define "universal function" itself as follows: Let $\phi : \mathbb{N} \rightarrow \mathbb{N} \rightharpoonup \mathbb{N}$ be an enumeration of all partial computable functions $\mathbb{N} \rightharpoonup \mathbb{N}$. Let $\psi : \mathbb{N} \rightharpoonup \mathbb{N}$ where

$$ \psi(n) = \phi(\pi\_1(n))(\pi\_2(n)) $$

where $\pi\_1, \pi\_2 : \mathbb{N} \rightarrow \mathbb{N}$ are the first and second Cantor *un*pairing functions. Then $u : A \rightarrow B$ is universal if and only if

$$ \exists g : R \cap (\mathbb{N} \rightarrow A) \quad \exists h : R \cap (B \rightarrow \mathbb{N}) \quad \psi = h \circ u \circ g $$

This resembles a definition of computable functions given in page 24 of Cutland's *Computability: An Introduction to Recursive Function Theory*.

### Addendum

In a sense, I'm looking for a definition of universality that is more "axiomatic", "abstract", and "generic" than the definition that is usually given, which pertains to partial functions **from naturals to naturals** specifically. My candidate definition requires only that RE be defined/understood over the relevant domain. (From that, co-RE and therefore R fall out automatically.)

To give an example of what I mean from a different area of mathematics, the reals can be *constructed* as Cauchy sequences or Dedekind cuts of rationals. However, they can also be *directly axiomatized* as the (unique) Dedekind-complete ordered field.

I can try to bootstrap the definition of universality from the naturals-to-naturals case, but doing so requires more artificial machinery and is less elegant. I'm wondering whether there's a more "direct" approach. That's why I'm asking for references that discuss how universality is defined in more general domains (than naturals-to-naturals) directly.

Notions like the effective topos and realizability might be relevant.

# Answer
> 1 votes
Several authors have considered this question. If you look at some recent work, it will cite older work. The most recent I am aware of is Pieter Hofstra's and Robin Cockett's work on *Turing categories*, see Definition 3.1 in their Introduction to Turing categories.

---
Tags: computability, undecidability, semi-decidability, primitive-recursion
---


# Question
Title: Counterexample to greedy solution for set cover problem
I am looking for the answer to the exercise 1-6 in "The Algorithm Design Manual" book. it is stated as follows:

> 1-6. The set cover problem is as follows: given a set of subsets $S\_1,\dots,S\_m$ of the universal set $U = \\{1,\dots,n\\}$, find the smallest subset of $T \subset S$ subsets such that $\cup\_{t\_i \in T} t\_i = U$. For example, there are the following subsets, $S\_1 = \\{1,3,5\\}$, $S\_2 = \\{2,4\\}$, $S\_3 = \\{1,4\\}$, and $S\_4 = \\{2,5\\}$. The set cover would then be $S\_1$ and $S\_2$.
>
> Find a counterexample for the following algorithm: Select the largest subset for the cover, and then delete all its elements from the universal set. Repeat by adding the subset containing the largest number of uncovered elements until all are covered.

My answer is as follows:

> $S = \\{\\{1, 2\\}, \\{3, 4\\}, \\{2, 5\\}, \\{5\\}\\}$, $U=\\{1,2,3,4,5\\}$.
>
> The algorithm will use the following sets: $\\{\\{1, 2\\}, \\{3, 4\\}, \\{2, 5\\}\\}$, while {{1, 2}, {3, 4}, {5}}$. would be more minimal.

Do you think its correct? I assume here that algorithm minimizes number of uncovered elements in each iteration and not the entire size of set to choose – that's why it might choose $\\{2,5\\}$ instead of $\\{5\\}$.

I have found this answer online:

> One counter-example consists of a series of subsets that increases in size exponentially, plus 2 additional subsets that each cover half of the elements. Example:
>
> $S\_1 = \\{1,2\\}$
>
> $S\_2 = \\{3,4,5,6\\}$
>
> $S\_3 = \\{7,8,9,10,11,12,13,14,15,16\\}$
>
> $S\_4 = \\{1,2,3,4,5,6,7,8\\}$
>
> $ S\_5 = \\{9,10,11,12,13,14,15,16\\}$
>
> The greedy algorithm will choose $S\_3,S\_2,S\_1$, while the optimal solution is simply $S\_4,S\_5$.

My understanding is that the algorithm would choose $S\_3,S\_4$ and not $S\_3,S\_2,S\_1$, since $S\_4$ has more uncovered elements than $S\_2$.

# Answer
> 7 votes
Usually the set cover problem is formulated such that the quantity to be minimized is the number of sets one picks rather than the sum of the numbers of elements of the sets picked. Unfortunately, this means that your example does not prove that the given greedy algorithm fails to find optimal solutions as the cover it produces consists of 3 sets, which is minimal for your instance.

A valid (and perhaps minimal?) counterexample would be $\mathcal U = \\{1, 2, 3, 4, 5, 6\\}$ with $\mathcal S =\\{\\{1, 2, 3\\}, \\{4, 5, 6\\}, \\{2, 3, 4, 5\\}\\}$, which works similarly to the one you found. The minimal cover consists only of the first two sets (these two must be in every cover since there is no other way to account for $1$ and $6$ otherwise) whereas the greedy algorithm will choose the last set first (since it covers 4 rather than 3 elements) and hence picks all sets, leading to a cover of size 3 which is not optimal.

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


title: Reassigning BT root and its children

text:
# Question
Title: Reassigning BT root and its children
Given the root of a binary tree, for instance below, I am running the following tests in Python:

```
     1
    / \
   2   5
  / \
 3   4

```

Test 1:

```
cur = root
root = None
print(root, cur)
None, node 1

```

Test 2:

```
cur = root
root.left = None
print(root.left, cur.left)
None, None

```

In both tests cur and root point to the same memory location. In test 1, why changing root to None did not modify cur? But in test 2 when I assign root.left to None, cur.left is also changed?

# Answer
> 1 votes
Variable cur and root points to the same object at the start. Think of it as assigning an object two names - root and cur.

In test1 you changed the object pointed to by root. This means that the name root has been assigned to a different object. However, cur remains to be the name of the object at the start. So now root and cur do not point to the same object.

In your test2 you did not change the object pointed by root, but you modified the object shared by both cur and root, through root so changes to this shared object will be reflected in both.

Try to read this for more info https://realpython.com/python-variables/

---
Tags: binary-trees, python
---


# Question
Title: Find the set of all edges which there is a cycle such that for every $e' \in C, e'\neq e$ : $w(e')\leq w(e)$
> Given an undirected graph $G=(V,E)$ and weight function: $ w: E \rightarrow \\{1,2,...,10\\}$.
> Describe an algorithm that finds the set of all edges $e\in E$ for which there is a cycle $C$ in $G$ that contains $e$ such that for every $e' \in C, e'\neq e$ : $w(e')\leq w(e)$.

I thought maybe because the weights are bounded I can run Kruskal multiple times and each time delete edges with a specific weight, and that without changing the complexity. Would appreciate your help:)

# Answer
> 1 votes
Suppose $E\_{i}$ be the set of all edges that have weight $i$. Now, we want to check if any of these edges are part of the solution or not. Note that, we can simply delete all the edges from the graph of the weight strictly greater than $i$ since they should not come in a cycle containing $e \in E\_{i}$. Let $G\_{i}$ be the new graph after deletion of these edges. Now, we just have to solve the following new problem:

**Updated Problem:** Find all the edges in $E\_{i}$ that form a cycle in $G\_{i}$

Try solving this new problem on your own. In case, you need any help, check this link for the solution to this problem in $O(|V|+|E|)$ time.

Since there are only $10$ such graphs $G\_{i}$. The overall time would remain $O(|E|+|V|)$.

---
Tags: algorithms, graphs, minimum-spanning-tree
---


# Question
Title: How fast we can run 128-bit LCG generator?
Let's consider some 128-bit LCG generator mod $2^{128}$, with some random 128-bit multiplier and increment. How fast we can run it using the same tricks like in AES:

https://crypto.stackexchange.com/questions/44927/how-long-does-a-good-aes-encryption-take

They use there some hardware instruction/hardware acceleration and it is absurdly fast. Can we do the same thing with LCG? If we run pure LCG in C it could be several dozen of GB/s. But can we do it faster in some easy way?

# Answer
> 1 votes
If you have a linear congruential random number generator X, then applying X say 8 times is another LCG whose constants are easy to find. If X calculated a series a0, A1.a2 etc. then you can calculate a0 to a7, and then apply Y to all 8 numbers in parallel, assuming this takes a lot less than eight times the effort.

I hope you know how to calculate *the same* LCG many times without divisions.

---
Tags: high-performance-computing
---


title: What exactly is label noise?

text:
# Question
Title: What exactly is label noise?
I've been doing research on precollege summer programs, and one ongoing project that has come up is "Improving Label Noise Robustness with data Augmentation and Semi Supervised Learning". So, could someone break this down for me? What is a label, what is label noise, and why is it such a large issue?

# Answer
> 2 votes
One of the main tasks in machine learning is *classification*. For example, given an image of a digit, which digit it represents? The desired algorithm assigns a *label* – in this case, a digit, to each *sample* – in this case, an image.

Supervised machine learning algorithms train classification algorithms using labelled data. The labels in the training set are typically manually generated by humans, who sometimes mislabel data. This is known as *label noise*. Label noise is usually the result of honest mistakes, but sometimes occurs out of malice. A third possibility is that some samples are genuinely hard to classify. Yet another possibility is that some labels are correct, but for various reasons we do not condone them.

Label noise is an issue since most machine learning models are trained on labelled data, and their performance is closely tied to the quality of the data they are trained on.

---
Tags: machine-learning
---


# Question
Title: Is there a way to measure the maximum random bits of the outputs of a generator?
I want to give examples to explain want I want to know first. Let $G \colon s \mapsto G(s)$ be a PRG.

1. Let $F\_{1} \colon s \mapsto G(s) \Vert b$, where $b = \bigoplus\_{k = 1}^{|G(s)|} G(s)\[k\]$. Obviously, $F\_{1}$ is not a PRG, since the last bit can be predicted. But if we remove the last bit, it is a pseudorandom string.
2. Let $F\_{2} \colon s \mapsto G(s) \Vert G(s)$, $F\_{2}$ cannot be PRG, too. but if only choose $|G(s)|$ bits properly, it can be pseudorandom.

So, if $F \colon \\{0,1\\}^l \to \\{0,1\\}^n$ is a polytime deterministic generator. Perhaps, $F$ is not a PRG, but $F$ may be closed to a PRG. Namely, there exists a compression algorithm $A \colon \\{0,1\\}^{n} \to \\{0,1\\}^m$, where $n \geq m \> l$, such that $A \circ F$ is a PRG. Is it well-defined? Can we use something like $n - \min\_{A} m$ to measure how is $F$ closed to PRGs? Is there a standard way to measure the maximum random bits of all the outputs of $F$?

# Answer
You might be looking for computational min-entropy.
> 3 votes

---
Tags: randomness, pseudo-random-generators
---


title: Symmetric functions in NC¹

text:
# Question
Title: Symmetric functions in NC¹
A boolean function $f \colon \\{0,1\\}^n \rightarrow \\{0,1\\}$ is symmetric if $f(x)$ depends only on the number of $1$s in $x$. It is known that every boolean function is in $\mathrm{NC}^1$, i.e. there is a circuit of depth $O(\log n)$ computing it.

What is known about the constant inside the $O()$ notation? Specifically, can one construct, for every $c$, a symmetric function requiring a circuit of depth at least $c \log n$? Or there is some constant $c\_0$ such that every symmetric function has a circuit of depth at most $c\_0\log n$?

# Answer
> 1 votes
We can treat the input $x$ as a boolean array. Using an $O(\log n)$ depth sorting network (such as the AKS network), we can sort $x$ in nonincreasing order. Calling the result $y$, using $O(1)$ more depth we can compute $z\_i = y\_i \land \lnot y\_{i+1}$ (extended in the right way to the boundary). The vector $z\_0,\ldots,z\_n$ is the indicator vector of the Hamming weight of $x$. At this point you can compute any symmetric function using $O(\log n)$ more depth.

This shows that there is a universal constant $C$ such that all symmetric functions can be computed in depth $C\log n$ using constant fan-in circuits.

# Answer
> 1 votes
Fix a circuit of depth $c\log n$ computing the majority function $\def\M{\mathrm{Maj}}\M\_{2n+1}\colon\\{0,1\\}^{2n+1}\to\\{0,1\\}$. (For example, the construction of Valiant gives $c\<5{.}3$.) Then for any $k\le n+1$, the threshold function $$\theta^n\_k(x\_0,\dots,x\_{n-1})=\begin{cases}1&\bigl|\\{i\<n:x\_i=1\\}\bigr|\ge k\\0&\text{otherwise}\end{cases}$$ can be defined by the circuit $$\M\_{2n+1}(x\_0,\dots,x\_{n-1},\underbrace{0,\dots,0}\_{k},\underbrace{1,\dots,1}\_{n+1-k})$$ of depth $c\log n$, and an arbitrary symmetric function $f\colon\\{0,1\\}^n\to\\{0,1\\}$ can be written as $$f(\vec x)=\bigvee\_{k\in I}\bigl(\theta^n\_k(\vec x)\land\neg\theta^n\_{k+1}(\vec x)\bigr)$$ for some $I\subseteq\\{0,\dots,n\\}$. Arranging the large $\bigvee$ as a balanced binary tree of disjunctions, this gives a circuit of depth at most $(c+1)\log n+2$. (E.g., using Valiant’s construction, every symmetric function has a circuit of depth $\<6{.}3\log n$.)

---

Concerning lower bounds, the only applicable lower bound I am aware of is that formulas over the De Morgan basis $\\{\land,\lor,\neg,0,1\\}$ computing Parity need size $\Omega(n^2)$, which implies that any De Morgan circuit for Parity has depth $\ge2\log n$ up to an additive constant. (This bound is tight for Parity, but presumably not for all symmetric functions.)

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


title: Direct vs. Random Access

text:
# Question
Title: Direct vs. Random Access
Would someone please clarify for me the difference between direct and random access?

Specifically, why does this Wikipedia article on Direct Access Storage Devices distinguish between the two:

> The direct access capability, occasionally and incorrectly called random access (although that term survives when referring to memory or RAM),

whereas this article on random access doesn't:

> In computer science, random access (sometimes called direct access) is the ability to access an element at an arbitrary position in a sequence in equal time, independent of sequence size.

# Answer
When you speak about *direct access* in small amount of time that could also be logarithmic, you speak about *secondary devices*, so hard disks, floppys, USB flash drives, etc.

When you speak about random access you mean that access time to any part of memory **is constant**. This is very hard to achieve with secondary devices, but easier with primary ones.
> 2 votes

# Answer
The Wikipedia article about direct access storage devices contrasts two access methods to information stored on physical devices: sequential access and direct access. Sequential access is exemplified by tape drives used for backups. Direct access, which is synonymous with random access, is much more common.

The difference between sequential access and direct or random access is quantitative rather than qualitative. Magnetic hard drives are considered random access although data access involves moving the read-and-write heads, which could be quite slow compared to other types of memory. In contrast, modern RAM often provides truly direct access, in the sense that accessing two locations in memory has the same cost whatever the difference in address (disregarding difference between the logical model in which RAM is byte- or word-addressable, and the physical model in which data is transferred in larger cache lines).
> 1 votes

# Answer
Both seems same. We use `Random Access` when for primary memory (RAM) and `Direct Access` for secondary storage.

For Direct Access Storage Device, this is written

```
The access methods for DASD are Sequential, Indexed and Direct.

```

So, here `Direct` means `Random` only
> 0 votes

# Answer
Random access memory basically store information temporarily while direct access memory store information permanently.
> 0 votes

---
Tags: memory-allocation, access-control
---


# Question
Title: Given a list of vertices in a binary tree output minimal sublist with the same lowest common ancestor
The input: a binary tree and a list $L$ of vertices in that tree.

The output: a sublist of $L$ of minimal length that has the same lowest common ancestor as $L$. If there is several sublists of minimal length it is OK to output any one of them.

We could just check all the possible sublists of $L$ but that seems inefficient.

Is there an algorithm for this problem whose running time grows polynomially with respect to the length of $L$?

One idea that doesn't work is checking for each vertex in $L$ whether removing it changes the lowest common ancestor and then simply removing the "useless" vertices. If it worked the running time would be linear.

Another idea that might work but I haven't verified in detail is to pick one vertex removing which doesn't change the lowest common ancestor, then remove it and again pick one vertex etc. This has a quadratic time.

# Answer
> 1 votes
Consider your binary tree as a binary search tree on the integers $1$ through $n$ to find that the answer for some given list $L \subseteq \[1, n\]$ will be $\\{\min L, \max L\\}$. In case you are not given a BST, you can traverse the given tree in-order to find those values in linear time (though that might be dependent on the data structure used to store $L$).

# Answer
> 0 votes
Suppose $v$ is the lowest common ancestor of the given list of vertices $L$. Let $T\_{\ell}$ denote the subtree rooted at the left child of $v$, and $T\_{r}$ denote the subtree rooted at the right child of $v$.

> **Observation**: There are two vertices $x$ and $y$ in $L$ such that $x$ belongs to $T\_{\ell}$ and $y$ belongs to $T\_{r}$.
>
> **Proof:** For the sake of contradiction assume that the above fact is not true. Now, without loss of generality, we can assume that there is no vertex in $L$ that belongs to $T\_{r}$. In this case, the left child of $v$ can act as an ancestor of $L$. Moreover, it appears in the tree at a lower level than $v$. This contradicts that $v$ is the lowest common ancestor of $L$.

Based on the above observation, we can further say that $v$ is the lowest common ancestor of $x$ and $y$. Because if this is not the case, $x$ and $y$ would have appeared in the same subtree $T\_{\ell}$ or $T\_{r}$.

Now, your algorithm just needs to output these two vertices $x$ and $y$ since these vertices are the minimal vertices that have the same ancestor as $L$. This gives the following linear time algorithm for the problem.

**Algorithm:**

1. Find the lowest common ancestor of $L$ in $O(n)$ time. Suppose $v$ is this ancestor.
2. If $v \in L$, output $v$.
3. If $v \notin L$, perform a DFS in $T\_{\ell}$ and $T\_{r}$. Find any vertex $x \in T\_{\ell}$ that belongs to $L$, and any vertex $y \in T\_{r}$ that belongs to $L$. Output $x$ and $y$. This step takes $O(n)$ time.

---
Tags: algorithms, complexity-theory, graphs, time-complexity
---


title: Bellman Ford Source & Negative Cycles

text:
# Question
Title: Bellman Ford Source & Negative Cycles
I’m having some troubles with Bellman Ford Algorithm in the following exercise

My guess is that at the end the algorithm should detect the negative cycle BD DF FG GB since B is decreasing at Vth (i.e. 7th) iteration. However changing the distance of the source does not make much sense to me. Is the source to be considered at fixed distance 0 or it can change as well as all the other vertices? Or is it correct to assume, as I did, that the algorithm will detect a negative cycle in the end?

Moreover, assuming to proceed with the computations, it is not clear to me the order I should follow. Being Vertex A not connected, should I go on relaxing from C (I guess not since it is not directly connected to B)? Or should I go on from D, which is the first vertex in alphabetic order directly connected to B? Thank you

# Answer
> 1 votes
The source distance does not need to be treated specially. It can change like any other vertex. In this scenario, it'll be updated to -1 by the end of the fourth round. The weights into and out of B will never become quiescent: either B's distance will be more than 2 greater than G's distance, or (say) A's distance will be more than 5 greater than B's distance. So the cycle will still be detected.

Now, if you ever find yourself reducing the source distance below zero, you immediately know that there's a negative cost cycle, and can terminate early. But there's no need to do so for the algorithm to work.

---
Tags: algorithms
---


# Question
Title: What does Dijkstra's algorithm become, when you replace path cost with edge cost?
Consider a variant of Dijkstra's algorithm (for a directed graph) where nodes are visited not in order of total path cost, but in order of incoming edge cost. (Assume here that all edge costs are positive and distinct). Nodes are never re-visited. What can we say about the resultant paths?

One obvious result is that they are minimax paths (that is, the maximum edge cost of a path found is the minimum of that of any path to that goal). But the condition seems to be stronger than that: An edge pair will tend to have a large number of tied minimax paths (since only one edge really constrains the path), but this algorithm seems to robustly prefer paths with fewer high-cost edges.

What I *think* is going on is, the edge costs for the found path from `a` to `b`, if sorted in descending order, produce a sequence that is the lexicographic minimum over all paths from `a` to `b`. In a sense, it's more "strongly" minimax, with ties broken by the second-highest-cost edge, and so on. But I can't prove this to myself, even informally.

Is this a known algorithm? Does it actually have that property?

# Answer
> 1 votes
The following answer assumes that you know the working of Dijkstra's algorithm. Here, we are working with a variant of Dijkstra's algorithm as mentioned in the question. Hope it will be helpful.

Suppose $s$ is the source vertex and $v$ be any vertex in $V$.

**Statement**: Dijkstra's algorithm outputs the lexicographically smallest path from $s$ to $v$ if all the edge weights in the graph are positive and distinct.

**Proof:** Suppose $p = (s,u\_{1},\dotsc,u\_{q},v)$ is the lexicographically smallest path from $s$ to $v$. For the sake of contradiction, assume that the algorithm outputs $p' = (s,w\_{1},\dotsc,w\_{r},v)$ and $p' \neq p$. Let $(w\_{i},w\_{i+1})$ be an edge in $p'$ that act as a tie breaker when we compare the orderings of $p$ and $p'$. In other words, every edges in $p'$ that has the higher weight than the weight of $(w\_{i},w\_{i+1})$ does also appears in $p$. Let $E\_{h}$ be the set of edges in $p'$ that have weight higher than the weight of $(w\_{i},w\_{i+1})$.

> **Claim:** There is an edge $e$ in $p$ such that $e \notin E\_{h}$ and $weight(e) \> weight(w\_{i},w\_{i+1})$.
>
> **Proof**: I will assume that you are familiar with the fact that the algorithm maintains a cut $(S, V \setminus S)$ such that all the vertices in $S$ are declared visited and the shortest path to them has been found. Now, suppose that just before the algorithm adds $(w\_{i},w\_{i+1})$, the cut is $(S\_{i}, V \setminus S\_{i})$. It implies that for all $j \leq i$, $w\_{j} \in S\_{i}$ and for all $j \> i$, $w\_{j} \in V \setminus S\_{i}$. Also, $s \in S\_{}$ and $v \in V \setminus S\_{i}$. Now, consider path $p$. Since $p$ is a path from $s$ to $v$, there is an edge $e$ in $p$ that is also present in the cut $(S\_{i}, V \setminus S\_{i})$. Firstly, we will show that $e$ does not belongs to $p'$. For the sake of contradiction assume that $e$ also belongs to $p'$. Therefore, let us define $e$ to $(w\_{t},w\_{t+1}) \in p'$.
>
> Case $1$: $e$ appears before $(w\_{i},w\_{i+1})$ in the path sequence $p'$. It means $w\_{t}$ and $w\_{t+1}$ belongs to $S\_{i}$. It contradicts that $(w\_{t},w\_{t+1})$ belongs to the cut $(S\_{i},V \setminus S\_{i})$.
>
> Case $2$: $e$ appears after $(w\_{i},w\_{i+1})$ in the path sequence $p'$. Let $(S\_{t-1},V \setminus S\_{t-1})$ be the cut just before $(w\_{t-1},w\_{t})$ was added to the solution. We know that $w\_{t-1} \in S\_{t-1}$ and also $w\_{t} \in S\_{i} \subset S\_{t-1}$. Therefore, it contradicts that $(w\_{t-1},w\_{t})$ belongs to the cut $(S\_{t-1},V\setminus S\_{t-1})$.
>
> From the above two cases, we can say that $e \notin p'$ and therefore $e \notin E\_{h}$. Also, note that the edges $e$ and $(w\_{i},w\_{i+1})$ both belongs to the cut $(S\_{i},V \setminus S\_{i})$, and the algorithm chooses $(w\_{i},w\_{i+1})$ over $e$. Therefore, the weight of $e$ is greater than the weight of $(w\_{i},w\_{i+1})$. This proves the claim.

The above claim implies that $p'$ is lexicographically smaller than $p$. Therefore $p = p'$. It contradicts our initial assumtion that $p \neq p'$. Hence proved.

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


# Question
Title: Given an array of integers and a value k, find the length of the longest subarray with max-gap no more than k
I'm struggling with this problem: you are given an array $A$ of $n$ integers and a number $k \in \mathbb{N} : k \neq 0$. The problem asks to find an algorithm that runs in $\Theta(n)$ that returns the length of the longest subarray $A'$ in $A$ s. t. $\max(A')-\min(A') \leq k$.

For example, in the array $A = \\{6, 5, 9, 10, 7, 13, 8, 7, 5, 15\\}$ with $k = 6$ the algorithm must return 6, because the subarray $A' = \\{9, 10, 7, 13, 8, 7\\}$ has length 6 and the difference between its maximum and its minimum is no more than 6.

Another example, with $A = \\{1, 3, 5, 2, 3, 1, 7\\}$ with $k = 2$ the result is 3, because the subarray $A' = \\{2, 3, 1\\}$ has length 3 and the difference between its maximum and minimum is less or equal than 2.

So far I tried to build an algorithm that goes like this (it may be buggy, it's just a draft to make my idea of solution clear):

```
int test(int* arr, int len, int k) {
    int minIndex = 0;
    int maxIndex = 0;
    int start = 0;
    int end = 0;
    int maxLength = 0;
    for (int i = 1; i < len; i++) {
        end = i;
        // Update the minimum and maximum if necessary while scanning the array
        if (arr[i] < arr[minIndex])
            minIndex = i;
        if (arr[i] > arr[maxIndex])
            maxIndex = i;
        // Check the new maximum/minimum doesn't make the subarray invalid
        if (arr[maxIndex] - arr[minIndex] > k) {
            // We broke the subarray, check the length of the longest subarray until now
            if (end - start > maxLength)
                maxLength = end - start;

            // Restart from the second element, then the third, and so on
            start++;
            maxIndex = minIndex = start;
            i = start;
        }
    }

    return maxLength;
}

```

The main problem with this algorithm is that in the worst case it runs in $\Theta(n^2)$, which doesn't comply with the problem's requests.

# Answer
> 4 votes
Basic idea: Use 2 pointers to traverse the array: **start** and **end**. Both start at the beginning of the array. Try moving **end** one position at a time and track the maximum subarray length, until the gap is too large. When that happens, move **start** towards **end** until you have smaller gap or you meet with the **end** pointer (the subarray becomes empty).

How to evaluate the gap: by definition max - min of current subarray. So we keep track of min and max.

Have a min deque where you keep elements in ascending order, so that the *head* of the queue will be the current minimum. When encountering a new element: remove all elements larger than it from the *back* of the queue, then add the new element to the *back* of the queue. This guarantees ascending ordering.

Have a max deque where you keep elements in descending order, so that the *head* of the queue will be the current maximum. When encountering a new element: remove all elements smaller than it from the *back* of the queue, then add the new element to *back* of the the queue. This guarantees descending ordering.

**NB**: You don't keep the elements themselves in the min and max queues; instead, keep their indices in the original array! This way you have both position and value, which is important for the following step.

When the gap becomes too large: obviously you cannot increase **end** before first bringing **start** closer to it. So increate **start** by one. Now check the head of both queues: they are the indices of current min and current max. If any (or both) these indices are now lower than **start**, then they don't belong to the current subarray anymore. Drop them, the head of the queue will be the new min/max.

Continue until **end** reaches the end of the array.

This gives you linear complexity: each element is processed once, and added and removed at most once from each queue.

Java implementation:

```
public int find(int[] numbers, int maxGap) {
    int best = 0;
    int bestStart = 0, bestEnd = 0;

    Deque<Integer> minQueue = new LinkedList<>();
    Deque<Integer> maxQueue = new LinkedList<>();

    int start = 0, end = 0;

    while (end < numbers.length) {
        int x = numbers[end];

        // add end to the minQueue keeping increasing order
        while (!minQueue.isEmpty() && numbers[minQueue.peekLast()] >= x) {
            minQueue.removeLast();
        }
        minQueue.addLast(end);

        // add end to the maxQueue keeping decreasing order
        while (!maxQueue.isEmpty() && numbers[maxQueue.peekLast()] <= x) {
            maxQueue.removeLast();
        }
        maxQueue.addLast(end);

        // minimum is at the front of minQueue
        int minIdx = minQueue.peekFirst();
        int minVal = numbers[minIdx];

        // maximum is at the front of maxQueue
        int maxIdx = maxQueue.peekFirst();
        int maxVal = numbers[maxIdx];

        // check
        if (maxVal - minVal > maxGap) {
            start++;
            if (start > minQueue.peekFirst()) {
                minQueue.removeFirst();
            }
            if (start > maxQueue.peekFirst()) {
                maxQueue.removeFirst();
            }
        } else {

            // track progress
            if (end - start + 1 > best) {
                best = end - start + 1;
                bestStart = start;
                bestEnd = end;
            }

            end++;
        }
    }

    // debug
    for (int i = bestStart; i <= bestEnd; i++) {
        System.out.print(numbers[i] + " ");
    }
    System.out.println();

    return best;
}

```

# Answer
> 0 votes
If the gap of $A\[i\ldots j\]$ is no more than $k$, then so is $A\[(i+1)\ldots j\]$. So you don't need to set `i` back to `start` in the line `i = start;`. As a result, the running time is reduced to $O(n)$.

A notable thing is the tricky of efficiently computing `minIndex` and `maxIndex` for a range. This can be done by range minimum (maximum) query. It takes $O(n)$ preprocessing time and each query takes constant time.

# Answer
> 0 votes
There are two things to do:

For each start pointer find the maximal end pointer. Note that end is increasing so it's just O(n) iterations.

At each iteration, maintain the minimum and maximum value. This can be done with heaps and sets (or hash maps). The amortized complexity is O(log(k)). You may have O(log n) if you don't use hash maps.

The final complexity is thus O(n log n), and if you allow the hash maps to be O(1), O(n log k).

@xskxzr proposes an alternative way to compute the range minima and maxima, so the problem is indeed O(n). However I think the algorithm is quite complicated with Cartesian trees so O(n log k) seems to be a simpler solution.

# Answer
> 0 votes
```
def pickingNumbers(a):
    a.sort()
    c=[]
    i=0
    while (i<len(a)):
        c.append(0)
        for j in range(0,len(a)-i):
            if a[i+j]-a[i]>1:
                break
            else:c[i]+=1
        i+=1
    return max(c)

```

---
Tags: algorithms, time-complexity, optimization, arrays, substrings
---


# Question
Title: Best approach to resource allocation problem
## Problem

> The enemy army has taken $n$ of our cities. In each city $i$ the enemy has placed $e\_i$ soldiers. We have $n$ teams, each team $j$ with $d\_j$ soldiers. If we place more soldiers in a city than the enemy, we retake the city. Our aim is to distribute our teams so that we maximise the number of retaken cities if:
>
> 1. We can only place one team per city
> 2. There is no limit to the number of teams we can play in each city.

## Question

I'm trying to figure out which **approach** might be best for each option (greedy algorithm, divide-and-conquer, dynamic programming, backtracking). I'm not necessarily looking for the particular algorithm, although I'd be happy to get it too.

## Previous work

### One team per city

The best approach would be a greedy algorithm, which would assign to each city the smallest team which can defend it, starting from the smallest team. If at some point the smallest remaining team cannot take the smallest remaining city, we can simply dump that team.

### No restriction for the number of teams per city

I can think of a greedy algorithm similar to the previous one, in which we assign the smallest teams to the smallest city until it's defended, and then move to the next one. However, I am not certain this would lead to an optimal solution, unlike the previous case. Backtracking explores the solution space exhaustively, so it would work but it's ineffective. Dynamic programming looks promising, as this superficially looks like a variation of the knapsack problem, but I know that generalisations/variations might not necessarily be tackled with the same approach.

# Answer
The second variant of your problem can be also stated as a Bin covering problem and vice-versa. Let us see how.

You can assume $n$ bins of capacities: $(e\_{1}+1)$, $\dotsc$, $(e\_{n-1}+1)$ and $(e\_{n}+1)$. And, $n$ items of sizes: $d\_{1}$, $\dotsc$, $d\_{n-1}$ and $d\_{n}$. The *bin covering problem* asks you to maximize the number of bins filled such that the total size of items packed in a bin is at least the capacity of that bin. Therefore, this problem is equivalent to the second variant of your problem. You can carry out a similar reduction in the reverse direction also, which proves that both the problems are equivalent.

---

Since the *Bin covering problem* is known to be *strongly* $\mathsf{NP}$-hard (see Section 2 on page 7 of this research paper.), it implies that the second variant of your problem is also *strongly* $\mathsf{NP}$-hard. Therefore, there is no *polynomial* or *pseudo-polynomial* time algorithm for your problem assuming $\mathsf{P} \neq \mathsf{NP}$. This closes the open problem posed by Watercrystal.
> 1 votes

# Answer
Let us first show that your proposed greedy algorithm for the second restriction is not optimal. For this, consider a scenario with $e\_1 = 1, e\_2 = 3$ and $e\_3 = 4$ as well as $d\_1 = 1, d\_2 = 2$ and $d\_3 = 3$. The greedy algorithm would assign $d\_1$ and $d\_2$ to the first city and $d\_3$ to the second one, leading to only one city being retaken. However, if we assign $d\_2$ to the first city and $d\_1$ and $d\_3$ to the second one we could retake both of them and hence, the greedy algorithm is not optimal.

As for algorithmic approaches, note that your problem given the second restriction (let's denote it by $L$) is $\mathsf{NP}$-complete which can be shown by reducing $\mathrm{Partition}$ to $L$: For a $\mathrm{Partition}$ instance given by a multiset $S$ of integers define an $L$-instance where the multiset of the $d\_i$s is given by $S$, i.e. for every element of $S$ we create a team of the same size. Denote by $X$ the sum of the elements of $S$ and set $e\_1 = e\_2 = X/2 - 1$ as well as $e\_i = X + 1$ for all $i \> 2$. Now note that we can retake at most $2$ cities (as we don't have enough forces to retake any city which is held by at least $X$ soldiers) and we can only retake both of them if we can split our forces exactly in half, sending $X/2$ soldiers to the first and second city, respectively. It follows that $S$ is a yes-instance of $\mathrm{Partition}$ if and only if we can retake 2 cities in our constructed $L$-instance (I left out some technical details but this reduction should work out just fine).

Assuming $\mathsf{P} \neq \mathsf{NP}$ this result implies that $L$ has no (deterministic) polynomial time algorithm. For some further lower bounds, see the other answer.
> 2 votes

---
Tags: optimization, greedy-algorithms, backtracking, resource-allocation, optimal-strategy
---


# Question
Title: Book CS:APP, using bit set and bit clear
Okay so I'm going through a book CS:APP.

I'm in chapter 2. And problem 2.13 talks about how the Digital Equipment VAX computer used bis (bit set) and bic (bit clear) instead of Boolean operations AND and OR.

Both instructions take a data word x and a mask word m. They generate a result z consisting of the bits x modified according to the bits of m. With bis, the modification involves setting z to 1 at each position where m is 1. With bic, the modification involves setting z to 0 at each position where m is 1.

Now you're given x and y. And you're allowed to use bis and bic to recreate x | y. And x ^ y.

Now I have already tried looking at the answers to understand what's going on. But I don't understand it.

If I literally look at explaination for bis and bic I would say bis just copies the mask and leaves x unused. And for bic it goes opposite of m, but also without using x. If I try to interpret it differently I end up with questions like what does bic do (for example) when m is 0?

The answers are for x | y: bis(x, y) where y becomes m... so a relatively simple answer. And for x ^ y (xor): bis(bic(x, y), bic(y, x)) where y and then x becomes m

So basically anything that could clarify what's going on here would be much appreciated!

And aside from this question, I also would like to ask if this is the right place for questions about a specific CS book? Because I'm teaching myself and don't have a teacher or someone to ask questions to and seeing with the previous exercise I also had a question it's possible that I might get a lot. But I can't find anything when searching on CS:APP (Computer Systems: A Programmer's Perspective) and yeah don't know where else to turn to. The book was recommended through teachyourselfcs.com if anyone was wondering.

# Answer
If $z=\mathrm{bis}(x,m)$ then $$ z\_i = \begin{cases} x\_i & \text{if } m\_i = 0, \\ 1 & \text{otherwise}. \end{cases} $$ This is exactly bitwise OR.

If $z=\mathrm{bic}(x,m)$ then $$ z\_i = \begin{cases} x\_i & \text{if } m\_i = 0, \\ 0 & \text{otherwise}. \end{cases} $$ This is bitwise AND of $x$ and the *bitwise complement* of $m$.

In order to see how $\mathrm{bis}(\mathrm{bic}(x,y),\mathrm{bic}(y,x))$ computes bitwise XOR, we just need to compute the truth table: $$ \begin{array}{c|c|c|c|c} x & y & \mathrm{bic}(x,y) & \mathrm{bic}(y,x) & \mathrm{bis}(\mathrm{bic}(x,y),\mathrm{bic}(y,x)) \\\hline 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 0 & 0 \end{array} $$ Another way of seeing this is replacing $\mathrm{bis}(x,y)$ with $x \lor y$ (read: $x$ *or* $y$) and $\mathrm{bic}(x,y)$ with $x \land \lnot y$) (read: $x$ *and not* $y$): $$ (x \land \lnot y) \lor (\lnot x \land y), $$ which is one of the standard formulas for XOR. In C, it would look as follows: `(x & ~ y) | (~x & y)`.
> 0 votes

---
Tags: bit-manipulation
---