# Question
Title: Number of probes in a unsuccessful search in open address hashing
**Theorem**: Given an open-address hash table with load factor $α = n/m \< 1$, the expected number of probes in an unsuccessful search is at most $1/(1−α)$, assuming uniform hashing.

Let us define the random variable $X$ to be the number of probes made in an unsuccessful search, and let us also define the event $A\_i$ , for $i = 1, 2,\cdots,$ to be the event that there is an ith probe and it is to an occupied slot. $X$ is defined in terms of intersection of events $A\_1, A\_2, \cdots, A\_{i-1}$, so $A\_i$ means the event that there is an $i$th probe and it's to and occupied slot. Then $Pr\[X\ge i\] = P\[A\_1 \cap A\_2 \cdots A\_{i-1}\] = Pr\[A\_1\] \times \cdots \times Pr\[A\_{i-1} | A\_1 \cap \cdots A\_{i-2}\]$, so we have

\begin{align} Pr\[X \ge i\] = \frac{n}{m}\times \frac{n-1}{m-1} \times \cdots \frac{n-i+2}{m-i+2} \le (\frac{n}{m})^{i-1} \label{tag1}\tag1\\ \end{align}

**Problem 1**: I have trouble proving the above formula.

The reason we decrease $m$ by $1$ each time above because once we use a slot we can not use it again. $Pr\[X\ge i\]$ means the probability of not hitting a slot as it's already occupied by another item. For example, $Pr\[X\ge 1\]$ means the probability of having at least one collision given $m$ slots.

**Attempt**: I see that for $i=1$ for example, we have

$$Pr\[X \ge 1\] = \frac{n}{m}$$

I am not sure how to get this $\frac{n-i+2}{m-i+2}$ in the formula \ref{tag1}.

**Problem 2**: Why we have $\le (\frac{n}{m})^{i-1}$ above in \ref{tag1} and not $\le (\frac{n}{m})^{i}$ please?

**Problem 3**: Why $Pr\[X\ge i\] = P\[A\_1 \cap A\_2 \cdots A\_{i-1}\]$ and not $Pr\[X\ge i\] = P\[A\_1 \cap A\_2 \cdots A\_{m}\]$? I see that if $Pr\[X\ge 1\] = P\[A\_1 \cap A\_2 \cdots A\_{m}\]$, so I am not sure why it's $P\[A\_1 \cap A\_2 \cdots A\_{i-1}\]$ please? So this means $A\_m$ is the event that we have already searched all slots and arrived at the last slot that is also occupied as I understand based on how $X$ was defined.

# Answer
> 1 votes
Problem 1:

Use induction. Recall $n\<m.$

$$\frac{n(n-1)}{m(m-1)} \leq \frac{n^2}{m^2}\quad\textit{if and only if}\quad n^2 m^2 -n m^2 \leq n^2 m^2 -m n^2$$

if and only if $$n^2m^2-n m^2 \leq n^2 m^2 -m n^2 \quad\textit{if and only if}\quad -m \leq -n $$ which can be checked directly. In fact the inequality is *strict*.

Then assume holds for $i$ prove for $i+1$ since the extra multiplicative factor is surely less than $n/m$.

Problem 2:

There are only $i-1$ terms in the product, so the expression $(n/m)^{i-1}$ after bounding.

Problem 3:

If you fail in the first $i-1$ trials then clearly $X$ is at least $i$.

---
Tags: algorithms, complexity-theory, hash
---


# Question
Title: I want to show, without taking a limit, that $2^\sqrt{2 \log n} \in Ω(\log^2n)$ and $2^\sqrt{2 \log n} \in O(\sqrt{2}^{\log n})$
I want to show, without taking a limit, that $2^\sqrt{2 \log n} \in Ω(\log^2n)$ and $2^\sqrt{2 \log n} \in O(\sqrt{2}^{\log n})$.

I will omit what I have tried as it has not been useful.

# Answer
Note that

$$2^\sqrt{2\log n}=2^{\frac{2\log n}{\sqrt{2\log n}}}$$$$=\left(2^{\log n}\right)^{\frac{1}{\sqrt{2\log n}}}$$

$$=n^{\frac{1}{\sqrt{2\log n}}}$$ $$=\sqrt\[\sqrt{2\log n}\]{n}.$$

Now after taking $\log$ from $=\sqrt\[\sqrt{2\log n}\]{n}$ and $\log^2n$, you get $$\log\left(\sqrt\[\sqrt{2\log n}\]{n}\right)=\Theta\left(\sqrt{\log n}\right).$$ Also $$\log\left(\log ^2n\right)=\Theta\left(\log\log n\right).$$ Since $$\lim\_{n\to \infty}\frac{\sqrt{\log n}}{\log\log n}=\infty$$ So $$2^{\sqrt{2\log n}} \in \Omega(\log^2n).$$

For second problem, note that $$\sqrt{2}^{\log n}=\sqrt{n}.$$ So $$2^{\sqrt{2\log n}} =\mathcal{O}(\sqrt{2}^{\log n}).$$
> 0 votes

# Answer
To prove $2^{\sqrt{2\log n}} \in O(\sqrt{2}^{\log n})$, you should note that $\sqrt{2}^{\log n} = \left(\sqrt{2}^{\sqrt{\log n}}\right)^{\sqrt{\log n}}$.

To prove $2^{\sqrt{2\log n}} \in \Omega(\log^2n)$, you should note that $\log ^2n = 2^{2\log \log n}$.

It will simplify the comparisons you have to do.
> 1 votes

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


title: Disprove sorting in O(log(n))

text:
# Question
Title: Disprove sorting in O(log(n))
Assume an array $X=\[x\_1,...,x\_n\]$ is given, where each $x\in X$ is an integer. Array $X$ is sorted if $x\_1 \le ... \le x\_n$. Typical sorting algorithms have a worst-case performance of $\mathcal{O}(n\log n)$, while in some models of computation, e.g., random-access machines, this can be reduced to $\mathcal{O}(n)$ under specific circumstances.

However, the statement

> There exists an algorithm that sorts any $X$ in $\mathcal{O}(\log n)$ time in the worst-case.

seems like nonsense to me. Is there some **rigorous** refutation of the above statement? I am aware of high-level arguments such as

* "Just reading $X$ takes at least $\mathcal{O}(n)$ time"
* "The sorted array needs $\mathcal{O}(n)$ space, and the runtime of an algorithm is bounded from below by the space it needs"

but these arguments aren't really helpful for a rigorous refutation of the above statement. According to my understanding, such a refutation would need to show that

> for every algorithm $A$ in every reasonable model of computation, there exists an $X$ such that $A$ does not correctly sort $X$ in $\mathcal{O}(\log n)$ time.

This is not homework, and I do not have a source for the above statement.

# Answer
> 2 votes
The first argument *does* help with a rigorous refutation for the statement.

If you want to really be formal, here is how you should approach it (its not a formal proof, but more of a sketch for how you should prove it formally):

Assume towards contradiction there is some algorithm $A$ that solve this question in $o(n)$ time. Since the run-time of $A$ is asymptotically smaller than $n$, then, when taking a big enough $n$, for any $X$ with $n$ elements there must be at least two indices that $A$ doesn't check. Therefore, if we swap the values (or at least, change the values so now any sorted array will have them in opposite order) - since $A$ never checked them, the computation history must be the same, and thus also all swaps it did were the same. However - $A$ never accessed those two indices and hence also never swapped them back to their correct position - which means that either the final array on the original $X$, or on the changed $X$, must be incorrect. Therefore, we get a contradiction to that we assumed $A$ solves this question, and hence $A$ must work in at least $\Omega(n)$ in order to actually sort.

# Answer
> 1 votes
This would depend on context. You can't do a comparison based sort with less than log (n!) comparisons, and that's $\Theta(n \log n)$. But the statement doesn't say "comparisons", it says "time".

With unlimited resources, say with $n^2$ processors that can all run in parallel, it might very well be possible. Finding the maximum of n values in O (log n) is quite easy with n processors. Sorting in O (log n) will be harder and needs more cleverness than I have in 5 minutes, but I wouldn't be surprised if it can be done.

---
Tags: complexity-theory, sorting
---


# Question
Title: find the minimum cost conversion between currencies A and B, given a matrix of currency conversions
Given a matrix of currency conversions, find the minimum cost conversion between currencies A and B (ex. maybe min cost conversion is A-\>C-\>D-\>B)

I was thinking of this as some sort of max flow problem such that A and B are the source and sink respectively, but I can't figure out exactly how to transform the weights of the problem.

# Answer
You can use a pathfinding algorithm for this case:

Create a node for each currency type.

Add an edge between two currency types if you can directly convert between them (in the case of your problem, you always can). For now, lets put the currency conversion rate as the weight of the edge - but this will change later on.

Say you want to convert between currency $A$ and $B$, then you will want to follow the path $p:=v\_0,v\_1,\dots,v\_k$ such that $\Pi\_{i=1}^{k-1} w(v\_i,v\_{i+1})$ is minimized.

Notice that by applying $\log$ on the formula, and using the fact that $log$ is monotonic, we get that this is exactly the path with $\sum\_{i=1}^{k-1} \log(w(v\_i,v\_{i+1}))$ minimized.

Therefore, by changing the weights to their logarithm (the weights will now be $log(conversion\\\_rate(v\_i,v\_{i+1}))$ instead of just $conversion\\\_rate(v\_i,v\_{i+1})$), we get that a shortest path is exactly what you need. You can use here Djikstra, or any other pathfinding algorithm you prefer.
> 1 votes

---
Tags: algorithms
---


title: Upper bound of $nc^n$

text:
# Question
Title: Upper bound of $nc^n$
Is it true that $nc^n \leq (c+1)^n$, where $c$ is a constant? If so, how?

# Answer
It comes from $$\left(\frac{c}{c+1}\right)^n\cdot n \to 0$$ when $n\to \infty$.
> 1 votes

---
Tags: discrete-mathematics
---


title: Subset Sum With Interval Target

text:
# Question
Title: Subset Sum With Interval Target
Define the subset sum with interval target problem (SSITP) as follows:

**SSITP Input**:
A multiset $S = \\{a\_1, …, a\_p\\}$ of positive integers $a\_i$ such that $\sum\_{a\_i \in S} a\_i = T$.

**SSITP Output**:

* True, if there is a subset $S’ \subseteq S$ such that $\sum\_{x \in S'} x \in \lceil \frac{1}{2}T \rceil .. \lfloor \frac{3}{4}T \rfloor$.
* False, otherwise.

Where $a .. b$, for two integers $a$ and $b$, is an integer interval including every integer between $a$ and $b$: $a, a+1, a+2, \dots, b-2, b-1, b$.

Is SSITP NP-hard?
Does introducing negative integers in the multiset $S$ change the hardness of the SSITP?

# Answer
> 4 votes
## With positive integers only

Consider the largest element $a\_m$ in the input. We have the following cases:

1. $a\_m \in \[\lceil\frac{1}{2}T\rceil, \lfloor\frac{3}{4}T\rfloor\]$. We can simply choose $\\{a\_m\\}$ and we are done: the answer is YES.
2. $a\_m \in (\lfloor\frac{3}{4}T\rfloor, T\]$. Any subset that includes $a\_m$ is too large, and taking all the remaining elements together is strictly less than $T-\lfloor\frac{3}{4}T\rfloor = \lceil\frac{1}{4}T\rceil$, which is too small: the answer is NO.
3. $a\_m \in \[\lceil\frac{1}{4}T\rceil, \lceil\frac{1}{2}T\rceil)$. We can always take all elements except $a\_m$ and get a subset in the correct range: the answer is YES.
4. $a\_m \in \[0, \lceil\frac{1}{4}T\rceil)$. We can choose elements in any order, stopping as soon as we get a total in the desired range. To see that this must occur, note that the elements sum to strictly more than $\lfloor\frac{3}{4}T\rfloor$, and for it not to occur would require that choosing some element $a\_i$ takes the sum of elements chosen so far from strictly below $\lceil\frac{1}{2}T\rceil$ to strictly above $\lfloor\frac{3}{4}T\rfloor$ -- but such an element would have to be at least $\lfloor\frac{3}{4}T\rfloor - \lceil\frac{1}{2}T\rceil + 2 = \lfloor\frac{3}{4}T\rfloor + \lfloor-\frac{1}{2}T\rfloor + 2 \ge \lfloor\frac{1}{4}T\rfloor + 1 \ge \lceil\frac{1}{4}T\rceil \> a\_m$, which contradicts the maximality of $a\_m$. So the desired range must be hit, and the answer is YES.

The solution can always be found in linear time by checking all cases, so the problem cannot be NP-complete unless P=NP.

# Answer
> 3 votes
## With negative integers permitted

Unlike the SSITP problem restricted to positive integers, when negative integers are permitted the problem is NP-complete. I'll show this by reduction from ordinary Subset Sum (SS). The idea of the reduction is to append extra numbers that force the target range to collapse to the single value 3, and to mess with the numbers in the original input so that the odd target value can only be achieved in very constrained ways that correspond straightforwardly to solutions to the original instance. I needed to add the "crumb" elements to make sure that when we have an SSITP solution, at least one element from the original SS instance must be chosen.

## Reduction

Given an instance $X = b\_1, \dots, b\_n$ of SS, where each $b\_i$ can be positive, negative or zero and the target value is zero, we construct an instance $Y = a\_1, \dots, a\_p$ of SSITP as follows:

* Set $a\_i = 8nb\_i + 4$ for all $i \in \[n\]$. Call these elements the *meat*, $M$.
* Append $a\_{n+1} = 2-8nU$, where $U = \sum\_i{b\_i}$. (I think of this element as "ballast" -- it exists only to weigh the sum down towards zero.)
* Append $a\_{n+2} = 3-4n$. (I think of this element as the "cornerstone" -- we can show that any solution must contain it.)
* Finally append $n-1$ copies of 4, and $n-1$ copies of -4, as $a\_{n+3}, \dots, a\_{3n}$. Call these elements the *crumbs*, $C$. (So in all there are $p=3n$ elements.)

Appending the extra numbers forces the total $T=\sum\_i^p{a\_i}$ to be 5. This shrinks the "interval" of allowed values to the single value $\lceil\frac{1}{2}5\rceil = \lfloor\frac{3}{4}5\rfloor = 3$.

**$X$ is a YES-instance of SS $\implies$ $Y$ is a YES-instance of SSITP:** For each $b\_i$ in the solution to $X$, choose $a\_i$ for the solution to $Y$. Suppose there are $k \ge 1$ such elements: The sum so far is $8n(0)+4k=4k$. Now choose $n-k$ copies of 4, bringing the sum so far to $4n$. Finally choose $a\_{n+2} = 3-4n$, bringing the total to 3.

**$Y$ is a YES-instance of SSITP $\implies$ $X$ is a YES-instance of SS:** The target is 3, which is odd, so the solution to $Y$ must contain an odd number. The only odd number available is $a\_{n+2} = 3-4n$, so it must appear in the solution. If $a\_{n+1} = 2-8nU$ also appears in the solution, then the remaining elements must sum to $3-(3-4n)-(2-8nU) = 4n+8nU-2$ -- but that number is not divisible by 4, and all other elements are multiples of 4, so this is not possible. Therefore the solution to $Y$ contains only $a\_{n+2} = 3-4n$, in addition to a subset of $M\cup C$ that sums to $4n$. Observe that this subset must contain at least one meat element, since the greatest sum achievable using only crumbs is $4(n-1)$.

We want the $8nb\_i$-terms within the chosen subset of $k \ge 1$ meat elements to sum to zero, so that we can simply choose the corresponding elements $a\_i$ to get a solution to $X$. Suppose towards contradiction that they do not: Then either the chosen subset of $M$ sums to at least $8n + 4k \ge 8n$, or it sums to at most $-8n+4k \le -4n$. In the first case, to reach a total of $4n$ from $8n$ we must use crumbs to subtract $4n$, but the most we can subtract this way is $4(n-1)$, so this case cannot happen. Similarly, in the second case, to reach a total of $4n$ from $-4n$ we must use crumbs to add $8n$, but the most we can add this way is $4(n-1)$, so this case cannot happen either. Therefore the only way that the chosen subset of $M\cup C$ can sum to $4n$ is if the $8nb\_i$-terms of the chosen subset of $M$ sum to zero, as desired. Then we can simply choose corresponding elements $a\_i$ to get a solution to $X$.

We have established that a YES solution to the constructed instance of SSITP $\iff$ the original SS instance has a YES solution, so a NO solution to the constructed instance of SSITP $\iff$ the original SS instance has a NO solution. The construction is clearly polynomial-time, so SSITP with negative integers permitted is NP-complete.

---
Tags: algorithms, np-hard, polynomial-time, subset-sum, integer-partitions
---


# Question
Title: Dynamic Programming: What is a subproblem space? Why do we need varying indexes to characterize a subproblem?
In dynamic programming:
**1.** what is the definition of the space of subproblems? does it have a mathematical definition?

**2.** why is it necessary to have an arbitrary index for the subproblem to vary?

To elaborate on question 2, I've taken the following paragraph from chapter 15.3 in CLRS:

> Conversely, suppose that we had tried to constrain our subproblem space for matrix-chain multiplication to matrix products of the form $ A\_1A\_2... A\_j $ . As before, an optimal parenthesization must split this product between $ A\_k $ and $ A\_{k+1} $ for some $ 1 \leq k \< j $. Unless we could guarantee that $ k $ always equals $ j - 1 $, we would find that we had subproblems of the form $ A\_1 A\_2 ... A\_k $ and $ A\_{k+1} A\_{k+2} ... A\_j $, and that the latter subproblem is not of the form $ A\_1 A\_2 ... A\_j $ . For this problem, $\color{red}{\text{we needed to allow our subproblems to vary at “both ends,” that is, to allow both } } $ $i$ and $j$ to $\color{red}{\text{vary }} $ in the subproblem $ A\_i A\_{i+1} ... A\_j $ .

**2.a.** I don't understand why the subproblem $ A\_{k+1} A\_{k+2} ... A\_j $ is not of the form $ A\_1 A\_2 ... A\_j $ ( $ k+1 $ is considered to be the first index in the problem of finding the optimal parenthization for $ A\_{k+1} A\_{k+2} ... A\_j $ ) whilst $ A\_1 A\_2 ... A\_k $ is considered a correct form ?
**2.b.** is there some sort of universal instantiation I'm missing in-terms of logic? what do variable indexes have to do with the issue In question **2.a.** ?
( I'm think the issue relates to the fact that when we prove a problem has a substructure, we need to prove it for arbitrary indexes, but I'm unable to see the relation between this proof and why $ A\_{k+1} A\_{k+2} ... A\_j $ is not of the form $ A\_1 A\_2 ... A\_j $ if we consider $k+1$ as the first index in the subproblem $ A\_{k+1} A\_{k+2} ... A\_j $ )

# Answer
The essence of dynamic programming is "**it is easier to solve many problems than to solve one problem.**". Sometimes, the more problems the easier. Sometimes, it is impossible with less problems.

The approach of dynamic programming is **finding/inventing** many problems that are similar to each other, solving these similar problems in some order so that we can obtain the solution to the original problem.

---

There is no mathematical definition for "subproblems".

As I understand it in the context of dynamic programming, they just mean the many problems we hope to/should/will find, through the solution to which the solution to the original problem can be obtained. Most of the time, it is immediate to tell if an approach is dynamic programming, as we would deduce/build/find mathematical recurrence relation among the solutions to those "subproblems", which will be used in the code.

---

It is, in fact, not very accurate to call those similar problems "**sub**problems" in the sense that those similar problems

* might be larger than the original problem in the sense of input size or the number of input parameters
* might be larger than the original problem in the sense of output size or the number of output parameters
* might not include the original problem as a special case, or might include the original problem as a special case.

We call those similar problems "subproblems" for some reasons:

* those similar problems are used to solve the original problem,
* those similar problems are similar to the original problem, usually, although not as similar as among themselves,
* those similar problems often include the versions of the original problem with smaller input.
* "subproblems", as a word, is short.

---

"Why are the subproblem $ A\_{k+1} A\_{k+2} \cdots A\_j $ not of the form $ A\_1 A\_2 \cdots A\_j $?"

Sure, the former are of the latter form if you consider that subscript "${}\_1$" in "$A\_1$" means a placeholder for an arbitrary starting index. There is nothing wrong with that.

However, you are supposed to understand (or you are supposed to find the understanding) that "$A\_1 A\_2 \cdots A\_j$" stands for a contiguous sequence of elements in the matrix chain that start from $A\_1$, a fixed element, which implies that it is enough for one number, the value of $j$, to completely specify those elements given the matrix chain. In this sense, "$ A\_{k+1} A\_{k+2} \cdots A\_j $" is not of the form of "$ A\_1 A\_2 \cdots A\_j $", sine two numbers are needed to specify them.

You might have overlooked the extremely obvious simple fact that the number of numbers/values that are needed to specify the input of a particular subproblem is critical. Or the number of input parameters of a function/methods/procedure/problem is critical. You just have to make a clear-cut choice on that number. If one parameter is enough, use one. It one parameter is not enough but two parameter is enough, use two.

In the current case of optimal parenthesization of the matrix-chain multiplication, the "many problems" that we could/should find/invent are the optimal parenthesization of some contiguous elements in the given matrix chain where both ends must vary. If we only allow one end to vary, then we will not have enough subproblems to solve the original problem, in the sense that those subproblems are not similar/close/related enough to each other for us to solve enough more subproblems based on the subproblems that we have solved.

---

For more explanation, read the CLRS book.
Fore more refined and clearer explanation, reach the CLRS book.
(When you do not understand some pieces in that book immediately, continue reading. And read again.)
> 2 votes

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


# Question
Title: Is this variant of the pinwheel scheduling NP-Hard?
I wonder if the following variant of the pinwheel scheduling is NP-Hard. Given a set of *n* radars *S* = {s$\_1$, s$\_2$... s$\_n$} and a set of *m* areas *A* = {a$\_1$, a$\_2$, ... a$\_m$}. Each radar *s* $\in$ *S* can cover a subset of *A* denoted by *A*(*s*) and in each time-unit, a radar can scan one area in *A*(*s*). The problem is, find a schedule for all radars to minimize a number *t*, such that for every *t* time-units, each area in *A* is scanned for at least once?

P.S. The **original** pinwheel scheduling problem: Given a radar *s* and a set of *m* areas *A* = {a$\_1$, a$\_2$, ... a$\_m$}, *s* $\in$ *S* can cover all areas in *A* and in each time-unit, *s* can scan one area in *A*. Now given a hard constraint on the time between repetitions for each area *a* $\in$ *A*, denoted by *R*(*a*). The problem is, is there exists a schedule for *s* such that for each area *a* $\in$ *A*, *a* is scanned for at least once every *R*(*a*) time-units? This problem has been proved to be NP-Hard.

# Answer
The problem can be reduced to the maximum matching problem in polynomial time. Therefore, the problem is polynomial-time solvable.

Let $t$ be the same repeat time for each area $a\_i$ in $A$. Note that in a feasible solution each area must get scanned at least once in the first $t$ time units; otherwise, there would be an area that will be scanned after $t$ time units - an infeasible solution. If a feasible schedule exists for the first $t$ time units, then we can repeat the same schedule for the further $t$ time units and so on.

Now, the new problem is: Is there any schedule for $n$ radars such that in initial $t$ time units, each area is scanned at least once. In other words, is there any schedule that uses $n$ radars at most $t$ times and covers all areas in $A$?

To solve the problem, create a bipartite graph $G = (U,V,E)$, where $U$ is the left partition such that each vertex corresponds to an area in $A$. The partition $V$ contains $n\cdot t$ vertices such that there are $t$ copies for every radar $s\_i \in S$. For each such copy of $s\_i$, there is an edge to area $a\_j$ if $s\_i$ covers $a\_j$, i.e., $a\_j \in A(s\_i)$.

If the graph $G$ has a maximum matching of size $m$, then each area gets covered at least once. And, we only used any radar at most $t$ times, once per each time unit in $(1,\dotsc,t)$. Therefore, a feasible schedule exists. If the maximum matching size is $\<$ $m$, then a feasible schedule does not exist.
> 1 votes

---
Tags: np-complete, np-hard
---


title: Dijkstra Algorithm

text:
# Question
Title: Dijkstra Algorithm
I have couple of questions about Dijkstra algorithm

1. Can the algorithm work if there are negative weights at the starting point?
2. Can we make the algorithm work with negative weights if we add a long long integer at all weights of edges so all the weights will be positive integer?

# Answer
> 1 votes
If the graph is directed and there is no cycle involving the source then the answer for the first question is positive, and Dijkstra's algorithm work. Note that negative edges only leaves the source.

For the second question, the answer is negative and Dijkstra's algorithm doesn't work. Because there is counter example.

---
Tags: dijkstras-algorithm
---


title: Language classification

text:
# Question
Title: Language classification
I am currently taking a computational course as part of my degree in Computer Science, and I would like to understand in depth the differences between these languages and if their belonging to R.

The third language defines a constant Upper bound for the calculation steps of the machine.

While the second language defines a Upper bound according to the word and may enter an infinite loop. (is it true ?)

In addition, what is the difference between the first language and the second language?

# Answer
> 1 votes
> The third language defines a constant Upper bound for the calculation steps of the machine.

There is no **constant** upper bound on the number of steps of $M$ in $L\_3$. $L\_3$ is the language of all machines that halt on at least one word $w$ while performing less steps than the length of $w$. The word $w$ is not fixed, all that is needed to $M$ to be in $L\_3$ is for such a word to exists. The length $w$ must be finite by might be arbitrarily large.

$L\_3$ is not in $R$. If $L\_3$ was in $R$ then you wold be able to decide the halting problem. Given a given Turing machine $T$ and an input $w$, construct a Turing machine $T'$ that simulates $T$ on input $w$ and then accepts. If $T$ halts then it must do so within a certain number $x$ of steps, showing that $T' \in L\_3$ since we can pick $w = 1^{x+1}$. If $T$ does not halt, then $T'$ also does not halt showing that $T' \not \in L\_3$.

> While the second language defines a Upper bound according to the word and may enter an infinite loop. (is it true ?)

I don't know what you mean by "may enter an infinite loop". It makes no sense to say that a language "enters an infinite loop". Moreover, a Turing machine $M$ in $L\_2$ might or might not enter into an infinite loop, depending on its input. However you know for sure that there is *at least one input* to $M$ such that $M$ does not enter an infinite loop (since it must halt in less than $|M|$ steps). Notice that, as before, there is no *constant* upper bound on the number of steps. Rather the maximum number of steps is determined by the length of the encoding of $M$ (which must be finite but can be arbitrarily large).

$L\_2$ is in $R$ since there are at most $|M|-1$ different positions of the input word that can be read by a Turing machine $M$ that halts in less than $|M|$ steps. You can then simulate (all the possible execution paths of) $M$ for $|M|-1$ steps on all possible input words of length at most $|M|-1$ (there are only $|\Sigma|^{|M|-1}$ such words).

> In addition, what is the difference between the first language and the second language?

If you meant the intuitive difference in the definitions of $L\_1$ and $L\_2$, then in the first language the number of steps by which $M$ must halt is specified as part of the word in $L\_1$. Alternatively, you can think of it as being written in unary as a part of the input of a TM that decides $L\_1$. In contrast, the second language specifies the number of steps by which $M$ must halt using the length of the encoding of $M$ itself.

If you meant the set difference then $L\_1 \setminus L\_2 = L\_1$.

$L\_1$ is in $R$. since it suffices to simulate all the (possibly exponentially many w.r.t. $t$) execution paths of $M$ of length at most $t$.

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


# Question
Title: How to encode a Universal Turing machine to an Integer $\in\mathbb{N}^+$?
The proof of Hierarchy Theorems (including space hierarchy theorem, deterministic time hierarchy theorem, nondeterministic time hierarchy theorem) depend on constructing a Universal Turing machine which differs all Turing machines enumerated. But how to encode a Universal Turing machine to an Integer such that this Universal Turing machine is enumerable?

# Answer
There are many ways to encode Turing machines. Essentially, this is possible because a TM $M$ is specified by a finite amount of information just like a computer program is completely specified by its source code which in the end is just some binary string in your computer's memory (and note that we can interpret any binary string as a natural number if we put a $1$ in front to account for leading zeroes). For more information on this I recommend the corresponding section of the first chapter of "Computational Complexity: A Modern Approach" by Arora and Barak as well as the wikipedia article on description numbers which also gives an explicit coding if you are looking for one.

Also note that universal TMs are still "normal" TMs which just happen to satisfy some properties and hence can also be encoded the same way as all other TMs.
> 0 votes

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


# Question
Title: How to arrive at correct preconditions and postconditions?
I read about Hoare's logic and algorithm correctness and how mathematicians prove an algorithm is correct,But I think how does one arrive at the required precondition and postcondition?(Inductive generalization).Please suggest further readings on discovering preconditions and postconditions(theorems),I heard about computational thinking and problem solving ,does reading these topics will help regarding this point?

# Answer
* The postcondition is generally given — it's usually called spec, problem statement etc
* The precondition is also given though usually more implicitly — eg for computing square root, and domain real numbers the input better be non-negative.

Driving the postC **backwards** till you reach the given preC is what the game is about.

If you know your basic axioms of assignment, sequencing and if, and the infra structure of predicate calculus this process too is mechanical *for the most part*.

The one place where this mechanical process gets stuck is loops, where you need cleverness/insight to convert a post-pre pair to loop invariant + variant.

Those insight-heuristics are dealt with in books like
> 1 votes

---
Tags: algorithms
---


# Question
Title: What makes Deep RL "fundamentally/mathematically" advantageous?
Note: I consider myself to be a beginner in the field of Deep RL.

Deep RL has proven tremendous success in recent years like playing atari and beating go champion. Therefore, considerable interest for the use of Deep RL was observed. However, I just do not want to go with this wave naively. I prefer to understand what makes Deep RL "fundamentally" advantageous, on a factual/mathematical/algorithmic level, in terms of the computational performance, optimization, generalization, convergence, etc. Surprisingly when I searched, I could not find any satisfying arguments for this.

If there are any published papers in this respect, it would be much appreciated as the argument would be peer-reviewed.

# Answer
> 1 votes
I'm not sure this will answer your question "mathematically", but it will definitely give you some idea to why it is "advantageous".

---

Usual RL requires to keep in memory a state-value vector. When the number of possible states is large, or even infinite - this is not practical to keep in memory. In addition, the usual RL requirements for convergence require to visit at least a certain number of times each unique state, and having such a large number of states would mean we won't visit most of them, most of the time (and hence you won't really converge. Unless you wait a few thousand years I guess...)

Deep RL tackles this problem by introducing a continuous function that is supposed to predict the "value" of a state given some representation of the state. This means we don't have to store a huge array mapping states to their values, and as such it means its far more practical.

Its also capable of "generalizing" the value of a certain state to other similar states, instead of computing it independently for them.

---

I hope this gave you some intuition on why Deep RL is so popular and powerful :)

---
Tags: optimization, reinforcement-learning
---


# Question
Title: Definition of position for List ADT (singly linked list implementation)
`Chapter 2: Basic Abstract Data Types` of the book Data Structures and Algorithms by Aho, Hopcroft & Ullman states the following:

> If the list is a1, a2, ... , an, . . . For singly-linked lists, it is convenient to use a definition of position that is somewhat different . . . Here, position i will be a pointer to the cell holding the pointer to ai for i = 2, 3 , ... , n.

There is absolutely no explanation as to why this representation of list position is "convenient".

Why not just have position i directly as the pointer to ai for i = 2, 3 , ... , n?

Any insight would be appreciated.

# Answer
> 1 votes
Suppose the linked list is composed of three elements: $a$ $b$ $c$.

Suppose, we are asked to delete the second element, i.e., $b$. Then, to carry out the deletion operation it is convenient to keep the pointer to $a$ since the algorithm would need to update its $next$ pointer to $c$. Keeping the pointer at $b$ would not help update $a$'s pointer. Therefore, to manipulate the pointers pointing to $b$, and from $b$, it is always better/convenient to focus on the cell that appears before $b$, i.e., cell $a$.

Similarly, suppose you want to add an element at second position in the list , i.e., before $b$. Then, it is convenient to keep pointer at $a$ since its next pointer will be updated to the newly inserted element. Furthermore, from cell $a$, you can manipulate $b$'s pointer but not vice-versa (unless it is a doubly linked list).

In other words, when we need to manipulate some element $a\_i$, we might require to make changes to the pointer pointing to it. Therefore, it is convenient to define position $i$ as the pointer to the cell before it, i.e., $a\_{i-1}$.

# Answer
> 0 votes
It means that in practice, the linked list will ve fragmented in the memory, instead of being a contiguous array.

Say, for example, you want to delete an item. Using a regular list implementation, you will need to do $O(n)$ work - since you have to "move" all elements in the list so there won't be any "gaps".

However, using a linked list, since it is not contiguous in memory - we can implement the delete operation in $O(1)$.

That being said, linked lists aren't that useful, and usually are taught as "intermidiate objects" before teaching more complex structures that build up on the idea of pointers - such as binary trees, heaps, etc.

---
Tags: data-structures
---


# Question
Title: How does concept of "redirection" works in ICMP?
I am trying to understand this figure, what it is trying to say?

**What I already know?**

Routing table is updated dynamically. However, for efficiency, hosts do not take part in the routing update process because there are terrible number of hosts. (Can you explain this with figure? What does it mean by host don't take part in routing update process?)

Hosts thus use static routing. Host usually know only 1 IP address of router, the default router. Thus host may send datagram to wrong router.

Solution is that router send redirection message back to host.

**But how is this working in this figure?**

Say at first,host A sends datagram to R1. Turns out it was the wrong router. So it sends redirection message to A. Now, A learns that it send message to wrong router.

Now what? A only knows about R1, it doesn't have information about R2, how will it send data to R2? I am really confused about this.

If R1 sends the message to R2, what is the point of R1 sending redirection message to A? I mean what difference would it make here if there was no redirection message?

Please clarify the doubts.

# Answer
> Now what? A only knows about R1, it doesn't have information about R2, how will it send data to R2?

R1 sends R2's IP address in the Redirect Message to A. That is the whole point of the Redirect Message: to tell the host where to redirect the datagram to.

This is all pretty well explained in RFC 792 *Internet Control Message Protocol*:

> ```
>  0                   1                   2                   3
>  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> |     Type      |     Code      |          Checksum             |
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> |                 Gateway Internet Address                      |
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
> |      Internet Header + 64 bits of Original Data Datagram      |
> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
>
> ```
>
> \[…\]
>
> # Description
>
> The gateway sends a redirect message to a host in the following situation. A gateway, *G1*, receives an internet datagram from a host on a network to which the gateway is attached. The gateway, *G1*, checks its routing table and obtains the address of the next gateway, *G2*, on the route to the datagram's internet destination network, *X*. If *G2* and the host identified by the internet source address of the datagram are on the same network, a redirect message is sent to the host. The redirect message advises the host to send its traffic for network *X* directly to gateway *G2* as this is a shorter path to the destination. The gateway forwards the original datagram's data to its internet destination.
> 1 votes

---
Tags: computer-networks, ip
---


# Question
Title: How to convert Bipartite Perfect Matching to SAT?
SAT is $NP$-complete while Bipartite Perfect Matching is in NC under derandomization assumptions. How to convert Bipartite Perfect Matching from balanced bipartites to SAT without Cook-Levin?

# Answer
> 2 votes
Since 3-SAT is NP-complete you can take any algorithm that decides bipartite perfect matching and use the construction from Cook-Levin's theorem. A direct construction is as follows.

Let $G=(U+V, E)$ be the bipartire graph with $|U| \le |V|$ and no isolated vertices. Create a boolean variable $x\_e$ for each edge $e \in E$. Intuitively, $x\_e$ is set to true iff $e$ is selected in the matching.

Then, for all (unordered) pairs of distinct edges $\\{e, f\\}$ such that $e$ and $f$ share an endpoint, add the clause $(\overline{x}\_e \vee \overline{x}\_f)$. These clauses ensure that the selected edges form a matching.

Finally, for each vertex $u \in U$, create a new clause $\bigvee\limits\_{ e=(u,v) \in E} x\_e$. Intuitively, this clause is satisfied iff $u$ is matched.

The SAT formula $\varphi$ obtained as the conjunction of all the above clauses is satisfiable iff $G$ admits a perfect matching. To obtain a 3-SAT formula you can apply the standard transformation from SAT to 3-SAT. Essentially, you can suitably duplicate and pad clauses with less than $3$ literals, while a generic clause $(\ell\_1 \vee \ell\_2 \vee \dots, \ell\_k)$ with $k \> 3$ literals can be replaced by the two clauses $(\ell\_1 \vee \ell\_2 \vee y) \wedge (\overline{y} \vee \ell\_3 \vee \ell\_4 \vee \dots \vee \ell\_k)$, where $y$ is a new variable. Repeat the above transformation until all clauses have exactly 3 literals.

---
Tags: reductions, np, satisfiability, bipartite-matching, 3-sat
---


# Question
Title: Difference between Caching and Slab Allocator
I've seen the term caching allocator and slab allocator used in discussions about allocation strategies, and would like to understand the difference between them.

I can see some resources on slab allocators, but nothing on caching allocators. What is a caching allocator and how is it different from a slab allocator?

Also, if you can point me to some resources on allocators in general that would be useful.

# Answer
> 2 votes
A caching allocator is an allocator that keeps a cache of released objects for later allocation.

When an object is needed, memory is allocated and then an object is initialised, or constructed, in that area of memory. When an object is no longer needed, it is usually destroyed and then freed.

If this is a type of object that is frequently allocated/deallocated, and the type of object has an expensive constructor or destructor, then it makes sense to keep a cache of objects in their constructed state.

The slab allocator is one specific implementation of a caching allocator.

---
Tags: memory-allocation
---


# Question
Title: my dsa teacher gave a assignment which is really confusing (i asked my teacher about it but she said just google it and find it out yourself)
Write best case, worst case and average case time complexity of following categories of algorithm–

a. Constant time

b. Linear time

c. Logarithmic time

d. Polynomial time

e. Exponential time

(this question which is where I am mostly confused as like if she had asked best case, worst case and average case of like a linear search thats easy but what this question is trying to ask is the question for me and yes i did as my teacher as said in the title)

(sorry my knowledge in dsa is quite low rn as i keep on getting 5 to 6 assignments per week and have very little time for self study)

# Answer
> 2 votes
Adam, the answer is that if this is indeed what your "teacher" is asking, then he doesn't have a clue. It's like "how many miles per gallon can a car do if it has (a) four gears (b) five gears (c) automatic drive" - it doesn't make any sense at all.

A correct answer would be: When we say for example that an algorithm is a "linear time algorithm", this means that the time to solve the worst case of any problem instance of size N is $\Theta(N)$, unless something else is said. For an "at most linear time algorithm" it will be $O(N)$.

This doesn't tell us anything about the best and average case, except it must be in $O(N)$ as well.

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


# Question
Title: Which is faster "Sorting strings in ascending order" or "Counting the frequency of all strings "?
I have a binary file with lots of 128 bit strings:
For Example Line 1. 1000101001000100001111001010.....
Line 2. 011010010101001001010..... and many more.
I want to sort them in ascending order, and I know that counting the frequency of all strings would be as good as sorting them (as original order does not matter).
But I don't know which is faster : sorting the file or counting the frequency of strings.
So, I want to know which option will be faster ?

# Answer
Asymptotically speaking, both tasks can be performed in time $O(n)$ (which is also a trivial lower bound) since there can be only finitely many distinct binary strings.

I don't know which of the two approaches is faster since it depends on the specific implementation details of the data structures used so you might try both of them. In practice I would implement the two approaches as follows:

To sort the strings use radix sort where each binary string is written some base $b$ which is a power of $2$. Chose $b$ to be a good trade-off between the memory you need to allocate (i.e., $\Theta(2^b)$ words) and the number of iterations of radix sort (i.e., $\lceil 128/b \rceil$). You could start, e.g., with $b=16$. This will require linear time in the worst case.

To count the number of occurrences use an Hashmap pre-sized to a capacity $\alpha n$, where $\alpha$ depends on the load-factor of the Hashtable's implementation (the idea here is to prevent re-hasing). The keys of the hashmap are the strings, and the associated values are their number of occurrences. This will require linear time in expectation.
> 0 votes

---
Tags: binary
---


# Question
Title: I want to know the difference between DFA and FSA
Taking a class named Theory of Computation. Learned about Deterministic Finite Automata and just got introduced to Finite State Automata. I can't figure out the difference, are they just synonyms?

https://www.tutorialspoint.com/automata\_theory/deterministic\_finite\_automaton.htm https://www.geeksforgeeks.org/introduction-of-finite-automata/#:~:text=The%20finite%20automata%20or%20finite,abstract%20model%20of%20digital%20computer.

# Answer
> 3 votes
FSA just means "finite state automaton" and it doesn't specify whether we are talking about deterministic automata or non-determinsitic automata.

DFA is a shorthand for deterministic FSA. FSA and DFA can be used as synonyms if it is clear from the context that we are dealing with deterministic automata.

---
Tags: finite-automata
---


# Question
Title: Graph cycle basis and odd cycle transversal
I have a graph $G$ and an its fundamental cycle basis $B$.

The question: is an odd cycle transversal of $B$ an odd cycle transversal of $G$?

# Answer
> 2 votes
No. Consider the following counterexample. Consider a complete graph $G$ on four vertices $V = \\{ v\_1,v\_2,v\_3,v\_4 \\}$.

Let spanning tree $T$ of this graph be composed of edges $(v\_1,v\_2), (v\_2,v\_3), (v\_1,v\_4)$. Then, the fundamental cycle basis $B$ is composed of cycles: $(v\_1,v\_2,v\_3)$, $(v\_1,v\_2,v\_4)$, and $(v\_1,v\_2,v\_3,v\_4)$. The basis $B$ has an odd cycle traversal $\\{v\_2\\}$. But $v\_2$ does not hit the odd cycle $(v\_1,v\_3,v\_4)$ of graph $G$.

---
Tags: graphs
---


# Question
Title: Can possiblity of hash collision be "zero" when we hash same file in different formats?
Let's say I have a file A, which is any normal file (pdf, jpeg, mp3 etc.)
Now I get the binary dump of file, say another file B{A}.
And the hexdump of file say, file H{A}.
Now I hash all the three files with any 256 bit HASH (SHA256, BLAKE256 etc.)
I want to know that :
1. What is the possiblity of hash collision in this case (Considering if somehow I find a collison in case of file A, I still can generate the hex and binary dump of that file to see if hashes of B{A} and H{A} matches or not).
2. Will it still be 1/256\* 256\* 256? Or
3. Will there be 0 collision ? (Considering collision between exactly same size of files)

# Answer
Approximating a Hash function $h$ as a function that maps each word in $\\{0,1\\}^\*$ to a word in $\\{0,1\\}^{256}$ chosen uniformly at random, you can find the probability that at least one of the events:

* $h(A)=h(B\\{A\\})$,
* $h(A)=h(H\\{A\\})$,
* $h(B\\{A\\})=h(H\\{A\\})$

is true by looking at the complementary probability. The probability that $h(A)$, $h(B\\{A\\})$, and $h(H\\{A\\})$ are all distinct is $1 \cdot (1 - \frac{1}{2^{256}}) \cdot (1 - \frac{2}{2^{256}})$. Then, the probability of having at least one collision is then: $$ 1- \left(1 - \frac{1}{2^{256}}\right) \cdot \left(1 - \frac{2}{2^{256}}\right) \approx 2.6 \cdot 10^{-77}. $$
> 0 votes

---
Tags: hash, binary
---


title: Connectivity in Directed Graph

text:
# Question
Title: Connectivity in Directed Graph
Connectivity in undirected graph can be easily identified using Disjoint Union Set (Union Find). Is there any way to check connectivity in a directed graph efficiently other than doing Depth First search or Breadth First Search? Is there any data structure that solves this problem efficiently.

For Example :

```
a -> b -> c
e -> b -> c

hasPath(a, c) => true
hasPath(e, c) => true
hasPath(e, a) => false
hasPath(c, a) => false

```

# Answer
The problem that you stated is known as the Graph Reachability Query problem. You may want to check this paper: An Efficient Algorithm for Answering Graph Reachability Queries, and the references therein.

The paper discusses the previously known results as well as optimizes both on the space complexity and the query complexity. The algorithm takes $O(n^2 + bn \cdot \sqrt{b})$ pre-processing time and $O(bn)$ space, where $b$ is the width of the graph, defined as the size of the largest subset $U$ of $V$ such that for every pair of nodes $u, v \in U$, there does not exist a path from $u$ to $v$ or from $v$ to $u$. The query complexity of the algorithm is $O(\log b)$.

Note that the value of $b$ could actually be $\Theta(|V|)$, for example, take a star graph on $n$ vertices. Therefore, the algorithm might be more useful for dense graphs, for which $b$ is usually small.
> 2 votes

---
Tags: union-find, depth-first-search, directed-graphs, breadth-first-search
---


# Question
Title: Proving existence of an optimal substructure for the DP problem "Equal" from HackerRank
**Q: How one would prove the existence of an optimal substructure for the following DP problem "Equal" from HackerRank?**

**Problem statement:**

---

---

**My attempt:**
Let $ A = \[ a\_1,a\_2,...,a\_n \] $ be our initial list where for all $ 1 \leq i \leq n $, $i$ is the $ith$ person and $ A\[i\] $ is the number of chocolates the $ ith $ person has.
Denote $ chocolate\_{list} = \[ 1,2,5\] $. Suppose that in order to optimally distribute the chocolates in $ A $ there exists $ 1 \leq k\_1 \leq m $ s.t. there exists $ 1 \leq q\_1 \leq 3 $ s.t. we distribute $ chocolate\_{list}\[ q\_1 \] $ to all workers except the $ k\_1 th $ worker. Denote this newly created list as $ \hat{ A } $. Note that the number of ways to distribute the chocolates in $ \hat{ A } $ \[by the rule that we distribute to all workers except one \] is itself the optimal number of ways to distribute the chocolates. Otherwise, we'd have $ 1 \leq k\_2 \neq k\_1 \leq n $ or $ 1 \leq q\_2 \neq q\_2 \leq 3 $ and distribute the chocolates in $ A $ \[ according to the rules given in the problem description \] and denote this new array as $ A^{'} $ . \[ I stopped here because I'm not sure how to continue to find a contradiction \].

**Q: Does this DP problem even have an optimal substructure? If so what is the proof for the existence of it?**

**Notes:**
**Reminder** to the steps used when showing the existence of optimal substructure ( from CLRS ) :

> 1. You show that a solution to the problem consists of making a choice, such as choosing an initial cut in a rod or choosing an index at which to split the matrix chain. Making this choice leaves one or more subproblems to be solved.
> 2. You suppose that for a given problem, you are given the choice that leads to an optimal solution. You do not concern yourself yet with how to determine this choice. You just assume that it has been given to you.
> 3. Given this choice, you determine which subproblems ensue and how to best characterize the resulting space of subproblems.
> 4. You show that the solutions to the subproblems used within an optimal solution to the problem must themselves be optimal by using a “cut-and-paste” technique. You do so by supposing that each of the subproblem solutions is not optimal and then deriving a contradiction. In particular, by “cutting out” the nonoptimal solution to each subproblem and “pasting in” the optimal one, you show that you can get a better solution to the original problem, thus contradicting your supposition that you already had an optimal solution. If an optimal solution gives rise to more than one subproblem, they are typically so similar that you can modify the cut-and-paste argument for one to apply to the others with little effort.

**( since it might help, i'm providing an example for proof of the existence of optimal substructure of different problem: )** Example of proving the existence of an optimal substructure for the matrix parenthization problem ( CLRS , chapter 15.2 ):

Thanks in advance for any help!

# Answer
> 1 votes
Let $\langle o\_1, o\_2, o\_{m+1}\rangle$ be a non-empty optimal sequence of operations that distributes the chocolates evenly, i.e., such that the final distribution is $\[k,k,k, \dots, k\]$.

Let $\alpha\_i$ be the number of candies given to the $i$-th person by operation $o\_{m+1}$ and consider the subsequence of operations $\langle o\_1, o\_2, \dots, o\_m\rangle$. We need to show that $\langle o\_1, o\_2, \dots, o\_m\rangle$ is an optimal sequence of operations to obtain the final distribution $\[k-\alpha\_1, k-\alpha\_2, \dots, k-\alpha\_n\]$.

The proof is by contradiction. Suppose that $\langle o\_1, o\_2, \dots, o\_m\rangle$ is not optimal, hence there is some sequence of operations $\langle o'\_1, o'\_2, \dots, o'\_\ell \rangle$ that yields the final distribution $\[k-\alpha\_1, k-\alpha\_2, \dots, k-\alpha\_n\]$ and such that $\ell \< m$. Therefore, the sequence $\langle o'\_1, o'\_2, \dots, o'\_\ell, o\_{m+1} \rangle$ yields the distribution $\[(k-\alpha\_1) + \alpha\_1, (k-\alpha\_2) + \alpha\_2, \dots, (k-\alpha\_n) + \alpha\_n\] = \[k, k, \dots, k\]$. The number of operations of the above sequence is $\ell + 1$ and, by the optimality of $\langle o\_1, o\_2, \dots, o\_{m+1}\rangle$, we know that $\ell+1 \ge m+1$ since every sequence that yields $\[k,k,\dots,k\]$ must consist of at least $m+1$ operations.
This results in the contradiction $m+1 \le \ell+1 \< m+1$.

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


# Question
Title: Is my regular expression and finite automata diagram for this state table correct?
So i have some theory of computer science homework and I'm struggling with this question currently. I am given the following automaton:

* $Q = \\{q\_0,q\_1\\}$.
* $\Sigma = \\{a,b\\}$.
* $q\_0 = q\_0$.
* $F = \\{q\_0\\}$.
* $\delta(q\_0,a) = \delta(q\_0,b) = q\_1$, $\delta(q\_1,a) = \delta(q\_1,b) = q\_0$.

I have to do two things: draw a state diagram, and write an equivalent regular expression. For now, these are my answers. I think my diagram is correct, but I'm not sure about the regular expression.

My regular expression for now is $(a+b)^\*(a+b)$. Any help is very much appreciated.

# Answer
> 0 votes
Your automaton accepts all words of even length, whereas your regular expression accepts all words of positive length. The most common way to express the language of all words of even length as a regular expression is $(\Sigma\Sigma)^\*$, where $\Sigma$ is a common shortcut for an arbitrary letter of the alphabet (in your case, $\Sigma$ stands for $a+b$).

# Answer
> 0 votes
Let $r$ be regular expression of your automaton, so $$r=\lambda\cup\left((a\cup b)(a\cup b)\right)^+.$$

---
Tags: finite-automata
---


# Question
Title: Printing actual solutions for the coin exchange problem
As I teach myself dynamic programming, I have learned about the coin exchange problems. Specially this site: https://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/ provides great insight about it. Specifically, the following implementation of a tabulated-DP-based solution for this problems is presented as follows:

```
def count(S, m, n ):
    # If n is 0 then there is 1
    # solution (do not include any coin)
    if (n == 0):
        return 1
    # If n is less than 0 then no
    # solution exists
    if (n < 0):
        return 0;
    # If there are no coins and n
    # is greater than 0, then no
    # solution exist
    if (m <=0 and n >= 1):
        return 0
    # count is sum of solutions (i)
    # including S[m-1] (ii) excluding S[m-1]
    return count( S, m - 1, n ) + count( S, m, n-S[m-1] );

```

However, this only counts the number possibles solutions.

**Question**: How can I actually save these solutions for post-processing?

**Previous research**: In this very helpful video: https://www.youtube.com/watch?v=ENyox7kNKeY they explain how to use an array of parent pointers, to generate the actual solutions, however, I am having issues with implementing this approach with the previous tabulated solution. Any hint?

# Answer
Assuming that you want the minimum number of coins to achieve a desired value and that you have a sufficient number of coins of every value we have this relation of recurrence:

Let $S(i,k)$ be the minimum number of coins to achieve the value $k$ considering the first $i$ coins. Also, let $V\[i\]$ be the value of the $i$-th coin.

So:

$$S(i,k) = \begin{cases} 0 & i = 0 \land k = 0\\ -\infty & i = 0 \land k \> 0\\ S(i-1,k) & i \> 0 \land V\[i-1\]-k \< 0\\ \max(S(i-1,k),S(i,k-W\[i-1\])) + 1 & \text{otherwise} \end{cases}$$

* Case 1 = Base case, considering the first 0 coins and the value 0 you pay 0 coins.
* Case 2 = Base case, considering the first 0 coins and a value greater than 0 you cant pay the value.
* Case 3 = Considering the first $i$ coins you can pick the solution to pay the value $k$ without considering the $i$-th coin, which is in $S(i-1,k)$.
* Case 4 = Considering the first $i$ coins, you should maximize between the solutions considering the $i$-th coin and not considering it. If the i-th coin is considered, you increment the number of coins in the solution, because you used the $i$-th coin.

A recursion based solution follows in verbatim from this relation of recurrence, but in Dynamic Programming you will replace a recursive call by a table lookup. So basically, where is $S(a,b)$ you will replace by a table access $S\[a,b\]$.
> 1 votes

# Answer
I think the answer is: “You write code to do it”. You have a solution for a similar problem, so you work to understand it, and then you modify it to do what you want.
> 0 votes

---
Tags: dynamic-programming, coin-change
---


title: (How) Can I remove a word from a DFA?

text:
# Question
Title: (How) Can I remove a word from a DFA?
As the title says, is it possible to remove a word from a DFA? One obvious way is to calculate the language without the word that I want to remove and then construct the DFA for the updated language. What I am interested in is whether there is a way to just update the original automaton without constructing another automaton from scratch.

For example, suppose that I have the automaton

And I want to remove *bab*, but words such as *baab* should still be accepted. Obviously removing any of the transitions directly would cut a lot more words than what I intend and a solution doesn't seem obvious. Are there any known algorithms for this?

# Answer
> 6 votes
Given the regular languages $L, L'$, based on the DFA for $L,L'$ we can:

1. make an DFA for the complement of a language $\overline L$, and
2. construct a DFA for the intersection $L \cap L'$.

The first is done by converting all the accepting states to non-accepting and vice-versa. The second can be done by calculating the intersection of two DFA's.

This gives an algorithmic way to express a DFA for your DFA $L\_1$, and the language $L\_2=\\{bab\\}$, by calculating the automata for $L\_1\cap \overline{L\_2}$.

The only thing left to do is construct a DFA for the $L\_2$ and follow the procedure.

# Answer
> 3 votes
Here is an algorithm that should work (unfortunately, I don't know how to write a satisfactory proof):

The idea is to create a bad path through the graph so that the specific word you want to remove does not end up in a final state. Care must be taken so that this path is not reachable from any other state other than the initial one (i.e. for each state in the bad path, there is *exactly one* in-edge to it, which is coming from another state in the bad path; except for the initial state, which has no in-edges).

1. * set the current state, $crt$, to be the initial state
    * set the previous state $prev$, to $null$
    * set the current symbol, $sym$ to be the first symbol of the word you need to eliminate (or the special value $\\\\$$ if it's the empty word)$^1$
    * set the previous symbol, $psym$, to $null$.
2. make a copy of the current state;
    * if the current state was the initial state, the copy is now initial, the original one becomes non-initial
    * if $prev$ and $psym$ are not $null$, draw an edge from $prev$ to the copy, on the symbol $psym$.
3. if $sym$ = \\$:
    * make the copy non-final; for each symbol in the alphabet draw an edge from the copy to the destination of $state$; DONE
    * otherwise preserve its finality.
4. For each symbol $\sigma$ in the alphabet:
    * if $\sigma \neq sym$: draw a $\sigma$ edge from the copy to the same destination as $crt$
    * else:
        + $prev \leftarrow state$
        + $psym \leftarrow sym$
        + set $state$ to be the destination of $\sigma$ from $state$
        + set $sym$ to be the next symbol (or the special value $\\\\$$ if the end was reached).
5. goto 2

For your example you'd end up with:

---

$^1$ $\\\\$$ is useful to generalize for the case of the empty word; $\\\\$$ should be a symbol that is not part of the DFA's alphabet.

---
Tags: finite-automata
---


# Question
Title: Why some codes can be executed by creating an object file through compiler while some codes need an interpreter to be executed?
We can execute a c/cpp file by creating an object file through compilatio.But why do we need to pass java bytecodes through an interpreter to execute them?Or why we can execute python/bash files by directly interpreting them? What's the differentiating feature that makes interpreter necessary to execute java bytecodes/python files/bash files etc?

# Answer
> 2 votes
Interpretation and compilation are simply two different ways of implementing a programming language. They are *not* a property of the programming language.

Every programming language can be implemented by an interpreter and every programming language can be implemented by a compiler.

Case in point: there are interpreters for C and there are native code compilers for Java and for JVM byte code.

However, it is important to understand that *all a compiler does* is translate a program from one language to another language. That's it. That's all it does.

*Only* an interpreter can actually execute code.

So, your statement

> We can execute a c/cpp file by creating an object file through compilatio.

is *false*. You *cannot* execute a C program by compiling it. You can *only* execute something through interpretation. If you compile a C file into, say, an x86 native object code executable file, you *still* haven't executed the program. You *still* need an interpreter to execute the program. This interpreter could be a physical CPU, but it could also be something like JPC, which is a PC emulator written in Java, running on a Java Virtual Machine, or JSLinux, which is a PC emulator written in ECMAScript, running in the browser.

> But why do we need to pass java bytecodes through an interpreter to execute them?

There are two possible answers to this, depending on what, *exactly* you mean by that statement.

The first possible answer is: because, as I explained above, *everything* needs to be interpreted in order to execute it. If you want to execute JVM bytecode, you need an interpreter for JVM bytecode. If you want to execute x86 native machine code, you need an interpreter for x86 native machine code.

Note that this interpreter can be a piece of software or a piece of hardware. As mentioned above, there are software interpreters for x86 native machine code (JPC, JSLinux, QEmu, Bochs). There are also CPUs which execute JVM bytecode directly (picoJava, Jazelle DBX).

The second possible answer is: you *don't* have to!

You don't have to execute JVM bytecode at all. You can *compile* it to some other language. For example, there are compilers that can compile JVM bytecode to CIL bytecode, or to x86 native machine code (Excelsior JET, GCJ).

Furthermore, many modern JVMs (including Oracle's HotSpot and Eclipse/IBM's J9) include a native code JIT compiler, so the JVM bytecode is not necessarily interpreted. Both HotSpot and J9 with default settings will interpret the same piece of code only a limited number of times, and when that threshold is reached, instead compile it to native machine code.

> Or why we can execute python/bash files by directly interpreting them?

We can execute Bash files by directly interpreting them, because someone wrote an interpreter that interprets Bash files. Nobody has written a compiler for Bash *yet*, but that doesn't mean it is impossible. It just means that nobody has done it yet.

Note that your characterization of Python is not actually correct. There is *no* Python interpreter in existence at the moment. All widely-used mainstream Python implementations have compilers:

* CPython compiles Python to CPython byte code (which it then interprets),
* Jython compiles Python to JVM byte code,
* IronPython compiles Python to DLR Trees,
* GraalPython is a strange one, it parses Python into Truffle ASTs, and then interprets the Truffle ASTs with a *specializing interpreter*, which is essentially equivalent to compiling the Truffle ASTs (it's related to Partial Evaluation and Abstract Interpretation (aka Supercompilation)),
* PyPy is another strange one, it compiles Python to PyPy byte code, interprets that PyPy byte code, and uses a tracing compiler to compile a specialized version of the interpreter which can only interpret that one program, which is essentially equivalent to compiling the PyPy byte code (it's related to Partial Evaluation and Abstract Interpretation (aka Supercompilation)).

> What's the differentiating feature that makes interpreter necessary to execute java bytecodes/python files/bash files etc?

You need an interpreter to execute something. Period. There is no way around that. Even if you just read the source code and figure out the result by hand, you are interpreting the code in your head: *you* are the interpreter. For native machine code, the CPU is the interpreter.

You *cannot* execute code without interpreting it.

If you have a program written in some language **X**, and you want to know what the result of that program is, there are only two things you can do:

* Interpret the program with an interpreter for language **X**, or
* Compile the program with a compiler from **X** to **Y** to some other language **Y**, for which you have an interpreter.

Note that you can construct a longer chain if necessary: If you have a program written in **X**, and you have a compiler from **X** to **Y**, but no interpreter for **Y**, but instead you have an interpreter for **Z** and a compiler from **Y** to **Z**, you can

1. Compile the program from **X** to **Y**, then
2. Compile the program from **Y** to **Z**, then
3. Interpret the program using your **Z** interpreter.

This is actually fairly common. Many new language implementations start out with a compiler from that new language to (a subset of) C, then compile C to native machine code using one of the many existing C compilers, and then execute the native machine code on the CPU.

In fact, YARV's (the most widely-used implementation of Ruby) JIT compiler is based on generating C source code, so when you "interpret" Ruby using YARV, what is *actually* happening is that YARV *compiles* Ruby to YARV bytecode, then interprets *that bytecode* (not Ruby). In parallel, it also keeps a counter, and when it has interpreted the same bytecode a certain number of times, it will pass the bytecode to the JIT compiler, which first compiles the bytecode into its own internal representation, then compiles that internal representation into C source code, then calls GCC, which in turn compiles that C source code into assembly code (going through a couple of additional steps actually, it first compiles C to GENERIC, then GENERIC to GIMPLE, then GIMPLE to RTL, and then RTL to assembly), then calls GAS, which compiles that assembly code into native machine code. All of that is happening when you do what you call in your question "directly interpreting code".

Whether to implement a language with a compiler, an interpreter, both, or a combination is simply a question of preference. Sometimes, the author is experienced in writing compilers but not interpreters, or the other way around.

I wrote some more about this stuff on SoftwareEngineering.SE, if you are interested: *Understanding the differences: traditional interpreter, JIT compiler, JIT interpreter and AOT compiler*.

# Answer
> 2 votes
gcj compiles Java straight to machine code. PyPy compiles Python to machine code.

I think that a compiler for Bash would be pointless, because it's a terrible language for large-scale programming, and any Bash script that reaches the point of needing a compiler should be rewritten in some other language for reliability and maintainability as well as performance reasons. But pointless isn't the same as impossible.

There are C and C++ interpreters, but I have no experience with them.

The reason Java has a standard bytecode format is not that the language can't work without bytecode. It's that it was designed to support running untrusted code delivered over the Internet, and a standard, manifestly type-safe bytecode was an efficient way to do that. (JavaScript, a totally unrelated language, never had a standard bytecode format, and it's delivered as source code instead, which adds some compilation overhead on the client side.)

Some languages are *easier* to compile than others. Python is pretty bad for this, because so many things are changeable at run time in ways that can't always be detected at compile time. PyPy proves properties of programs when it can; when it can't prove something, it guesses, and inserts code to check at runtime if the guess is wrong, and fall back on slower generic code. This is very complicated and makes writing a compiler for Python a daunting project. But PyPy does exist and it works. JavaScript is hard to compile for similar reasons, but good JavaScript compilers exist because there's an economic incentive for companies like Google to make them.

---
Tags: compilers, interpreters
---


# Question
Title: Flow-based vs. Reactive programming paradigms
I am reading Concepts, Techniques, and Models of Computer Programming and came across **Flow-based (FBP)** and **Reactive programming** paradigms. Now I have found the following article from *J. Paul Morrison*, the person who invented FBP. I am also some what familiar with Reactive programming. But I am having hard time to differentiate this two paradigms. Both belong to Declarative and also under Dataflow paradigm. But **what** really sets them apart? I would like a concise answer with greatest distinction between these two approaches outlined.

# Answer
The best distinction I've found (which also makes sense) is in this quote from @chipsy from HN (brackets and emphasis mine):

> FRP **\[Functional Reactive Programming\]** is very similar in nature to FBP **\[Flow-Based Programming\]**. (even the acronyms are similar) The main difference is in **packaging**.
>
> The original FBP systems were still 70s-style near-metal code within the component design, but the architecture described a protocol just sufficient for statically and asynchronously connecting the components together, and a runtime method that is amenable to the simplistic approach of having each component run round-robin until all return a "finished" signal. It's very much an "industrial engineering" perspective.
>
> FRP, on the other hand, comes from the traditions of functional programming, and so the evaluation order computation is given a more academic treatment, and the languages are given more explicit syntax, where FBP doesn't aim to describe itself much more deeply than the flowcharts. **Both FRP and FBP have purity and immutability as core concepts.**
>
> So as I see it: **different starting point, different packaging, same conclusions.**

Source: https://news.ycombinator.com/item?id=6267892

"Functional reactive programming (**FRP**) is a programming paradigm for **reactive programming** (asynchronous dataflow programming) using the building blocks of functional programming (e.g. map, reduce, filter)." wikipedia

Also, for reference, the definitions:

* "**FBP** is a particular form of dataflow programming based on bounded buffers, information packets with defined lifetimes, named ports, and separate definition of connections." wikipedia
* "In computing, **reactive programming** is a declarative programming paradigm concerned with data streams and the propagation of change." wikipedia

My current understanding:

**Flow-Based Programming** approaches seems more concerned with architecting an application based on **data processing pipelines**, especially oriented towards processing **large data sets** (think distributed MapReduce):

> NoFlo is a JavaScript implementation of Flow-Based Programming (FBP). Separating the control flow of software from the actual software logic. Helping you organize large applications easier than traditional OOP paradigms, especially when importing and modifying large data sets.

> With NoFlo, your application consists of **independent components** that are connected together in a **graph**. This makes it possible to split your problem in logical areas that make sense, and to see how they connect with each other.

> The MIT-licensed NoFlo library can either be used to run full **flow-based applications** or as a library for making complex workflows or asynchronous processes more manageable. It **can also be used as an Extract, Transform, Load (ETL) tool** in business applications.

Source: https://noflojs.org/

> **FBP** is a special case of dataflow programming characterized by asynchronous, concurrent processes "under the covers", Information Packets with defined lifetimes, named ports, "bounded buffer" connections, and definition of connections external to the components ...

Source: https://jpaulm.github.io/fbp/index.html

Useful references used here, and for further reading:
> 1 votes

---
Tags: programming-paradigms
---


# Question
Title: Proving existence of an optimal substructure for the DP problem "Sherlock and Cost" from HackerRank
Problem statement from HackerRank ( source: https://www.hackerrank.com/challenges/sherlock-and-cost/problem ) :

> In this challenge, you will be given an array $ B $ and must determine an array $ A $ . There is a special rule: For all $ i$, $ A\[i\] \leq B\[i\] $ , . That is, $ A\[i\] $ can be any number you choose such that $ 1 \leq A\[i\] \leq B\[i\] $ . Your task is to select a series of $ A\[i\] $ given $ B\[i\] $ such that the sum of the absolute difference of consecutive pairs of $ A $ is maximized. This will be the array's cost, and will be represented by the variable $ S $ below.
> The equation can be written: $ S = \sum\_{i=2}^{N}{ | A\[i\] - A\[i-1\] |} $
> For example, if the array $ B = \[1,2,3\] $ , we know that $ 1 \leq A\[1\] \leq 1 $ , $ 1 \leq A\[2\] \leq 2 $ , and $ 1 \leq A\[3\] \leq 3 $ . Arrays meeting those guidelines are:
> \[1,1,1\], \[1,1,2\], \[1,1,3\] \[1,2,1\], \[1,2,2\], \[1,2,3\]
> Our calculations for the arrays are as follows:
> |1-1| + |1-1| = 0 , |1-1| + |2-1| = 1, |1-1| + |3-1| = 2
> |2-1| + |1-2| = 2 ,|2-1| + |2-2| = 1 ,|2-1| + |3-2| = 2
> The maximum value obtained is 2.

**My attempt for proving the existence of an optimal substructure:**
Denote $ SEQ $ as the set of all sequences $ A $ s.t. $ \forall 1 \leq i \leq n $, $ 1 \leq A\[i\] \leq B\[i\] $. For all $ A \in SEQ $ define $ S\_A = \sum\_{i=2}^{n}{ | A\[i\] - A\[i-1\] |} $ .

Let $ \hat{A} \in SEQ $ s.t. for every $ \hat{A'} \in SEQ $, $ S\_\hat{A'} \leq S\_\hat{A} $. Thus, there exist a sequence of optimal choices $ \langle o\_1,o\_2,...,o\_n \rangle $ s.t. for all $ 1 \leq i \leq n $ we chose $ 1 \leq \alpha \leq B\[i\] $ s.t. $ \alpha \in B $ and we define $ \hat{A}\[i\] = \alpha $, and this is the $ o\_i $ choice.
Looking at the sequence of choices $ \langle o\_1,o\_2,...,o\_{n-1} \rangle $ and looking at the sequence $ \tilde A $ that derives from these choices, $ \tilde A $ must be optimal. Otherwise, there exist a sequence of choices $ \< o\_1,...,o\_l \> $ s.t. $ l \< n-1 $ and note that the sequence of choices $ \< o\_1,...,o\_l, o\_n \> $ give $ \hat{A} $. Notice that we have $ l+1 $ choices in the sequence $ \< o\_1,...,o\_l \> $ and notice that $ \langle o\_1,o\_2,...,o\_n \rangle $ is an optimal sequence of choices, but $ l+1 \< n $ and since every sequence of choices that yields $ \hat{A} $ must have at-least $ n$ choices, this means $ n \leq l+1 \< n $ , a contradiction.

**What do you think about this attempt? how would you prove the existence of an optimal substructure?**

Thanks in advance for any help!

# Answer
Your attempt sounds specious since your proof does not use any specific property of the objective function, $ S = \sum\_{i=2}^{n}| A\[i\] - A\[i-1\]| $. Had your proof been correct, there would have been an optimal substructure for any arbitrary objective function we could have defined for $A$, which does not make sense.

---

To prove the existence of an optimal substructure, we had better state what is the optimal structure of the subproblems of the given problem. To accomplish that, we have to state

* what are the overlapping subproblems and
* how to obtain the optimal solution of a larger subproblem by using optimal solutions to smaller subproblems.

The overlapping subproblems are $P(e, t)$ for $1\le e\le n$ and $1\le t\le B\[t\]$, the problem of choosing sequence $A\[0\], A\[1\], \cdots, A\[e\]$ such that

* $1\le A\[i\]\le B\[i\]$ for all $1\le i\lt e$ and
* $A\[e\]=t$ and
* that sequence reaches the maximum $S =\sum\_{i=2}^{e}| A\[i\] - A\[i-1\] |$ among all sequences that satisfy the two conditions above.

Since the order of summation does not matter, we know that the following optimal substructure.

* if $A\[1\], A\[2\], \cdots, A\[e+1\]$ for $1\le e\le n-1$ is a solution to $P(e+1, A\[e+1\])$ , then $A\[1\], A\[2\], \cdots, A\[e\]$ must be a solution to $P(e, A\[e\])$.
* Given $1\le t'\le B\[e+1\]$ where $1\le e\le n-1$, we can consider sequences $A\[1\], A\[2\], \cdots, t, t'$ for all $t$ with $1\le t\le B\[e\], $ where $A\[1\], A\[2\], \cdots, A\[e\]$ is a solution to $P(e, t)$. The sequence with the maximum $S =\sum\_{i=2}^{e+1}| A\[i\] - A\[i-1\] |$ among them will be a solution to $P(e+1, t')$.
* The solution to the original problem is the sequence with the maximum $S =\sum\_{i=2}^{n} | A\[i\] - A\[i-1\] |$ among solutions to $P(n, t)$ where $1\le t\le B\[n\]$.

Note that in the explanation here, finding the sequence with the maximum value is the goal instead of just finding the maximum value. There is not much difference in the explanation had the maximum value been used as the goal.

---

The collection of overlapping subproblems is not necessarily unique. There could be many choices of them.

In fact, there is a simpler set of overlapping subproblems, which leads to the simple solution in Python below. Can you find it?

---

The indices start at 1 in the explanation above. They start at 0 in the program below.

```
def cost(B):
    max1 = 0    # choose 1
    maxB = 0    # choose B[i]
    for i in range(1, n):
        new_max1 = max(max1, maxB + B[i-1] - 1)
        maxB = max(max1 + B[i] - 1, maxB + abs(B[i]- B[i-1]))
        max1 = new_max1
    return max(max1, maxB)

```
> 1 votes

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


# Question
Title: Reduction of K-Vertex-Cover to SAT: How to define the constraint?
Overall, one would naturally think that with n different nodes, and for x(1) for example representing node 1, it would be like:

x(1)+x(2)+x(3)...+x(n) \<= k

This would mean that for every possible solution of k-vertex-cover, the maximum amount of literals being true has to be lower or equal to k. So much for understanding.

The problem however is, that a logic formula is needed for description of the constraint and logic doesn't have addition or comparison.

My only idea up to now is that I could use the logic formula of Adders and Comparators to simulate an addition and a comparison in logic, but that only works out for some solutions. I need a general logic formula. Does anyone have another idea or maybe a simpler method which could be used in general?

The reduction has to be done in polynomial time.

# Answer
> 2 votes
In "Efficient CNF encoding of Boolean cardinality constraints" the paper's authors offer a way of encoding *at least* and *at most* cardinality constraints using unary values. An advantage of this encoding over chains of adders and a comparator operating on a binary constraint is the immediate generation of conflict clauses when the constraint is violated during search and the immediate generation of unit clauses when the assignment of more of the constrained variables would exceed the constraint. This plays into the strength of modern DPLL-based SAT solvers optimized for speedy propagation of unit clauses. Though fairly complex in implementation the encoding is a nice compromise between the hideously inefficient naive encoding and the simple but search-inefficient adders+comparator encoding.

---
Tags: reductions, satisfiability, vertex-cover
---


# Question
Title: Check if there is a subset of coordinates where each coordinate in the subset is diagonal to each other
## Problem Statement

Given a list of XY coordinates of length **N** ( e.g. `[(1,2),(3,4)]` ) check if there is a subset of coordinates of length **S** where each coordinate of this subset is **diagonal** to each other. More details below:

* Coordinate **A** and Coordinate **B** are diagonal to each other if **A**'s XY values are different to **B**'s XY values. For example, (1,1) is diagonal to both (2,2) and (4,3), but not diagonal to (1,2)
* I don't need to find the specified subset of length **S**, I only need to say if it's possible or not given the list **N**
* If **S**=1, then every subset is valid.
* **N**, **S** \> 0
* **N** \>= **S**

For example, given the following list of length **N**=4 `[(1,2), (2,2), (3,1), (4,5)]`, the following statements are true:

* `[(2,2), (3,1), (4,5)]` is a valid subset of length **S**=3 where every coordinate is diagonal to each other.
* `[(2,2)]` is a valid subset of length **S**=1.
* `[(1,2), (2,2)]` is not a valid subset of length **S**=2.

## The Issue

A brute-force approach would be to iterate through all possible subset combinations of length **S** until we find one that fulfills the criteria from the problem statement. In the worst case scenario when **N**=**S**, this would have a complexity of O(n!), which is way too inefficient I think.

Is there an an O(n^2) or better solution to this problem? This was a problem that a colleague came up with, so I'm not sure if this is a known problem with an efficient solution.

# Answer
One way to solve this optimally is to model it as a maximum cardinality matching problem in a bipartite graph whose two parts consist of the occupied rows $r\_i$ and the occupied columns $c\_i$, where the edge $r\_ic\_j$ is present whenever $(c\_j, r\_i)$ appears in the input. A matching in this graph having $k$ edges maps a subset of $k$ rows to $k$ distinct columns, which is the same as choosing $k$ pairwise diagonal coordinate pairs from the input. Iff the largest possible matching has at least $S$ edges, the answer is YES.

Each input coordinate pair increases the number of occupied rows and columns by at most 1 each, so there are at most $n$ occupied rows and at most $n$ occupied columns. There are just $n$ edges (thanks Inuyasha Yagami for noticing this), so solving the problem using the $O(|E|\sqrt{|V|}))$-time Hopcroft-Karp algorithm will take $O(n^{1.5})$ time.
> 3 votes

# Answer
The problem can be solved in $O(n^2 \log n)$ time by reducing the problem to the maximum independent set problem on claw-free graphs.

**Reduction:** For every XY coordinate $(x\_i,y\_i)$ in the list, create a vertex $v\_i$ in the graph $G$. Two vertices $v\_i = (x\_i,y\_i)$ and $v\_j = (x\_j,y\_j)$ share an edge if and only if $x\_i = x\_j$ or $y\_i = y\_j$. Now, the problem is to simply find an independent set (or stable set) of size **S** in $V$. Also, note that the graph is claw-free. The proof is simple, as follows:

> For the sake of contradiction assume that there is a claw in the graph. That is, there are four vertices $\\{v\_1,v\_2,v\_3,v\_4\\}$ and the subgraph spanned by these vertices only contain the edges: $(v\_1,v\_2), (v\_1,v\_3),$ and $(v\_1,v\_4)$. Without loss of generality, assume that $x\_1 = x\_2$. Then $x\_1$ must not be the same as $x\_3$ and $x\_4$; otherwise there would be an edge $(v\_2,v\_3)$ or $(v\_2,v\_4)$ in the graph. Therefore, $y\_1 = y\_3$ and $y\_1 = y\_4$. In that case, there would be an edge between $v\_3$ and $v\_4$. It contradicts that $\\{v\_1,v\_2,v\_3,v\_4\\}$ forms a claw.

**Solution:** On the claw-free graphs, the maximum independent set problem can be solved in polynomial time. The current best polynomial-time algorithm is due to Nobili and Sassano. Here is the published and the arxiv version of the paper. The running time of the algorithm is $O(n^2 \log n)$.
> 2 votes

---
Tags: algorithms, graphs
---


title: What does x sign mean in functions

text:
# Question
Title: What does x sign mean in functions
I came across this cross sign when reading a book. Does anyone know what does this mean in the context of a function?

# Answer
As @zkutch says, this refers to the cartesian product of two sets.

Its definition has to do with sets, not with functions. The formal definition is as follows:

For two sets $A,B$ we define $$A\times B:= \\{(a,b)\mid a\in A, b\in B\\}$$ Which is the set of all tuples from A and B.

In the context of functions, it might be simpler to think of this as: a function $f:A\times B \rightarrow C$ essentially takes two arguments $a,b$ and spits out a $c$. This will now be written like that:

$$f(a,b)=c$$

Essentially its the same as accepting a tuple $(a,b)$, so you can rest assured this is exactly the formal mathematical definition for set cartesian product here.
> 1 votes

---
Tags: algorithms, discrete-mathematics, notation, mathematical-foundations
---


title: What is the need for Kernel threads?

text:
# Question
Title: What is the need for Kernel threads?
I'm a bit confused about *kernel-threads*, I searched a lot at the Internet, SOF and here but found very diverse and conflict answers. What is the need for Kernel threads? Are they threads that are only responsible for responding to system calls? Or they are threads that are encapsulating User threads and execute the user threads code? When there are **X** user threads and **Y** kernel threads in the System, can we say we have **X + Y** actual threads or only **Y** actual threads? When **N** user threads are mapped to a **one** kernel thread, does only one of these user thread are running and the others are waiting to execute?

# Answer
> 1 votes
> What is the need for Kernel threads?

There is no need for Kernel threads. There are plenty of Operating Systems that don't have them and work just fine, so they are clearly not needed.

> Are they threads that are only responsible for responding to system calls?

That depends on the specific Operating System, mostly. For some, the answer may be Yes, for others, the answer may be No.

> Or they are threads that are encapsulating User threads and execute the user threads code?

That depends on the specific Operating System, mostly. For some, the answer may be Yes, for others, the answer may be No.

> When there are **X** user threads and **Y** kernel threads in the System, can we say we have **X + Y** actual threads or only **Y** actual threads?

That depends on how, *precisely*, you define the terms "user threads", "kernel threads", and "actual threads".

> When **N** user threads are mapped to a **one** kernel thread, does only one of these user thread are running and the others are waiting to execute?

Most likely, yes. However, in such a case, an N:1 threading model is uncommon. More common is an N:M threading model where N user threads are scheduled by a user space scheduler to M kernel threads (which are then, in turn, scheduled by the kernel scheduler).

Note that what is meant by the term "kernel thread" differs wildly between different OSs.

---
Tags: operating-systems, threads, os-kernel
---


# Question
Title: Algorithm to get maximum value of tuples from two sets
I have two sets *A* and *B*. Each tuple from *A x B* has a score associated to it. E.g.:

* **I:** (A1, B1) -\> 5
* **II:** (A1, B2) -\> 7
* **III:** (A2, B1) -\> 3
* **IV:** (A2, B2) -\> 4

I now want to get the combination of tuples that has the highest value. However, every item can only be used once. So in this case the possible combinations would be:

* (I, IV): 5 + 4 = 9
* (II, III): 7 + 3 = 10 So in this case the highest achievable score when only using each item once would be 20.

*A* and *B* are distinct and possibly have a different size.

Can anyone think of a smarter way than just brute forcing this? What's a similar problem I can take a look at?

# Answer
> 3 votes
You're looking for a maximum-weight matching in a bipartite graph. You could model it like this:

* **Nodes**: $A \cup B$
* **Edges**: all combinations in $a, b \in A \times B$ with their respective weights $\mu(a,b)$

This graph will be bipartite, and the *combination of tuples* you were refering to would be a matching in that graph. A *matching* refers to a set of edges in the graph where no two edges have a common adjacent node. Since you didn't state whether there should be exactly two tuples or not, this matching could either be capped at 2 or get larger and become maximal.

Since you want to get a combination that yields the highest value (in our case the largest total weight), we need a maximum-weight matching – which we'll call $M$. *Maximum-weight* is just another way to say that we can't find a different matching $M'$ where $\sum\_{e \in M} \mu(e) \le \sum\_{e \in M} \mu(e)$.

As for it's complexity, our graph has $O(n)$ nodes, where $n$ is the larger of $\lvert A \rvert$ and $\lvert B \rvert$. Further, we have $O(n^2)$ Edges. You can have a look on Wikipedia to read about possible solutions. The reference algorithm would run in $O(n^3)$ in our case, which is better than brute forcing by a factor of $n$. NetworkX also seems to implement an algorithm with this complexity.

# Answer
> 2 votes
Lets define the following bipartite graph:

The nodes in the first group, will be the elements from $A$, and the nodes in the second group will be the elements from $B$.

Add an edge between every element $a\in A$ to every element $b\in B$, and put a weight on that edge equal to the value of $(a,b)$.

Now, each tuple will correspond to a particular edge in the graph, and hence any matching (or independent set) will be a valid "set of tuples" (since no item is used twice).

Now your question boils down to finding a maximal matching, which can be solved quickly

---
Tags: algorithms
---