title: Uniform Convergence and VC Theroy

text:
# Question
Title: Uniform Convergence and VC Theroy
I've started reading more about statistical learning theory, specifically this paper right here and I cannot understand the following part:

> It turns out the conditions required to render empirical risk minimization consistent involve restricting the set of admissible functions. **The main insight of VC (Vapnik-Chervonenkis) theory is that the consistency of empirical risk minimization is determined by the worst case behavior over all functions f ∈ F that the learning machine could choose**. **We will see that instead of the standard law of large numbers introduced above, this worst case corresponds to a version of the law of large numbers which is uniform over all functions in F**

The part that is in bold is what I do not get. This part specifically: *"Consistency of ERM is determined by the worst case behavior over all functions in function space F, that learning machine could choose"*. What is exactly meant by the **worse case behavior**? I tried looking into VC theory and could not find the answer.

# Answer
What is considered in VC theory is about the bound of error between empirical risk and real expected risk. Hence, the worst-case function is when the difference between these two risks is maximized.
> 1 votes

---
Tags: machine-learning, learning-theory, vc-dimension
---


# Question
Title: Complexity of $O(\log(n^n))$ vs $O(\log(n!))$
Is $O(\log(n^n)) \< O(\log(n!))$? Is there any good/practical algorithm with this kind of complexity?

And also, to check my understanding of algorithmic complexity, are these two $\> O(n\log(n))$?

I'm just starting with this topic and not really sure if I'm getting it right.

Thanks and stay safe.

# Answer
> 4 votes
$O(\log n^n)$ and $O(\log n!)$ both describe the same set of functions.

Notice that $( \frac{n}{e} )^n \le n! \le n^n$ and hence:

$O(n \log n) = O(n \log \frac{n}{e}) = O( \log ( \frac{n}{e} )^n) \subseteq O(\log n!) \subseteq O(\log n^n) = O(n \log n)$.

This shows that all the above sets coincide.

# Answer
> 0 votes
$n^n$ is a lot larger than n!. The first multiplies n x x n x n x ... x n (n times), the latter multiplies 1 x 2 x 3 x 4 x ... x n. So it is *obvious* that $O(\log(n^n)) \< O(\log(n!))$ is not true. $O(\log(n^n)) \> O(\log(n!))$ is less obvious, but also not true.

That's because we are taking the logarithm on both sides. Taking logarithms changes products to sums and exponents to products (very roughly). And if we take the product for n!, it's obvious that we have n/2 factors greater than n/2, so n! \> $(n/2)^{n/2}$. Taking the logarithm, log n! \> (n/2) log (n/2). For n \> 4 we have n/2 \> $n^{1/2}$, therefore log n/2 \> (log n) / 2, therefore log n! \> (n/2) log (n/2) \> n/4 log n = 1/4 log $n^n$.

So log n! = $\Theta(\log n^n)$.

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


# Question
Title: Is there a Data Structure like Binary Decision Diagrams for Non-Binary Functions
Binary Decision Diagrams (BDD) take a set of binary variables $x\_1, x\_2,..., x\_n$ as input.

Is there a data structure similar to BDDs where each variable takes more than two values? Each variable's values should be independent of every other variable. For example, $x\_i$ could be assigned the three values $\\{0,1,2\\}$ and $x\_j$ could be assigned the four values $\\{0,1,2,3\\}$, where $i \ne j$.

# Answer
Yup. A BDD is just an acyclic finite-state automaton (DFA) that accepts a language $L \subseteq \\{0,1\\}^n$. It represents the function $f(x)= 1$ if $x \in L$ or $f(x)=0$ if $x \notin L$.

You can generalize this to allow an acyclic finite-state automaton over a language over a different alphabet, or indeed, a language $L \subseteq \Sigma\_1 \times \cdots \times \Sigma\_n$ where $\Sigma\_i$ is the set of valid values for $x\_i$. Everything carries over.
> 3 votes

---
Tags: data-structures
---


# Question
Title: Difference between consensus number n and consensus number infinite
In book *Concurrent Programming: Algorithms, Principles, and Foundations* of Michel Raynal, in Section 16.5.1, Theorem 75 says

> Compare&swap objects have infinite consensus number.

and in Section 16.5.2, Lemma 40 says

> The mem-to-mem-swap object type has consensus number n in a system of n processes.

Then, in Section 16.1, author puts in table both Compare&swap and men-to-mem-swap as objects with consensus number infinite.

So, what is the difference between objects with consensus number n and objects with consensus number infinite?

# Answer
The consensus number of an object is the maximum number of concurrent processes that you can synchronize with one such object in a wait-free manner (I won't go into what wait-free means here). For example, a register with only read and write operations doesn't help with wait-free synchronization at all, so it has consensus number 1. A register with a test-and-set operation can be used to synchronize two processes in a wait-free manner, but not three or more, so the consensus number of test-and-set is 2.

$n$-register assignment, where a process can atomically write to multiple registers, allows up to $2n-2$ processes to synchronize wait-free if there are $n$ registers. More processes require more registers. Therefore the consensus number of an objet consisting of $n$ registers that can be assigned atomically is $2n-2$.

A single register with a compare-and-swap operation is sufficient to synchronize any number of processes wait-free. Therefore the consensus number of compare-and-swap is infinite.

Lemma 40 states that a mem-and-swap object allows the wait-free synchronization of all the processes in a system of $n$ concurrent processes, for any number $n$. This means that for any number $n$, the consensus number of mem-and-swap is at least $n$. (Stating that the consensus number *is* $n$ in a system of $n$ processes is a bit of a misnomer since the definition of the consensus number doesn't actually depend on the total number of processes.) Since consensus number of mem-and-swap is at least $n$ for any $n$, it's infinite.

If you prefer another source than Raynal's book, you can read the original paper by Maurice Herlihy.
> 1 votes

---
Tags: concurrency, consensus
---


# Question
Title: How to implement random sampling with continuous variables?
How functions like rnorm in R (and similar functions) create a random sample ? If I want to implement one algorithm to simulate this procedure what can I do? When you have the pdf or pmf of a distribution how can you use this to create a random sample with a computer? Is there some book on this topic?Is this a numerical analysis topic? I searched alot but I couldn't find any information about this.

# Answer
> 2 votes
One standard approach is to use inverse transform sampling: if $F$ is the cdf of the desired random variable and $U$ is uniformly distributed, then $F^{-1}(U)$ has the desired distribution. There are more sophisticated methods for specific distributions; you can find references and links where you can learn more in the linked Wikipedia article.

---
Tags: algorithms, probability-theory, randomness, sampling, books
---


# Question
Title: Proving NP-completeness of a surveilled graph problem
So suppose I have a graph consisting of a tuple $(V,E,A,g)$ where $V$ denotes vertices, $E$ denotes edges, $A$ denotes a subset of $V$ (i.e. $A \subseteq V$), and $g:A\rightarrow\mathbb{N}$ is a function.

We can call this graph instance $\textit{consistent}$ if we can find a subset $B \subseteq V$ \ $A$ such that for any $u \in A$, $ g(u) = |N(u)\cap B|$ (in which $N(u)$ obviously denotes the neighbourhood of vertex $u$).

How would one go about proving that the problem of determining consistency of a graph $(V,E,A,g)$ is NP-complete? Would a reduction from SUBSET-SUM using slack variables of some type work?

Thanks!

# Answer
> 1 votes
Let $\langle \mathcal{S}, \mathcal{I} \rangle$ be an instance of exact cover. Here $\mathcal{I}$ is a set of items and $\mathcal{S} \subseteq 2^\mathcal{I}$ is a collection of subsets of $\mathcal{I}$.

The goal is to decide whether there is a subset $S$ of $\mathcal{S}$ such that every item in $\mathcal{I}$ belongs to exactly one set in $S$. This is a well-known NP-complete problem.

To reduce exact cover to your problem create a graph $G = (V, E, A, g)$ as follows:

* $V = \mathcal{S} \cup \mathcal{I}$.
* $E = \\{ (u,v) \in \mathcal{S} \times \mathcal{I} \mid v \in u \\}$.
* $A = \mathcal{I}$
* $\forall u \in a, g(u)=1$.

If $S$ is an exact cover for $\langle \mathcal{S}, \mathcal{I} \rangle$, then $B=S$ is a solution for your original problem since $S \cap \mathcal{I} = B \cap A = \emptyset$ and each item in $\mathcal{I}=A$ has exactly one neighbor in $S = B$.

On the other hand, a solution $B$ to your original problem is such that $B \cap A = B \cap \mathcal{I} = \emptyset$. Hence $B \subseteq \mathcal{S}$ and eacn item in $A = \mathcal{I}$ has exactly one neighbor in $B$. Therefore $B$ is an exact cover for $\langle \mathcal{S}, \mathcal{I} \rangle$.

# Answer
> 1 votes
Here is a sketch of a direct reduction from 3-SAT to your problem.

Given a formula $\phi$, create a graph that contains:

* For each variable $x\_i$ of $\phi$: a path of length 2 traversing vertices $x\_i, u\_i, \overline{x}\_i$. Vertex $u\_i$ is in $A$ and $g(u\_i)=1$.
* For each clause $C\_j$ of $\phi$, a path of length 2 traversing vertices $v\_j, w\_j, z\_j$. Vertex $w\_j$ is in $A$ and $g(w\_j)=3$.
* For each variable-clause pair $(x\_i, C\_j)$ such that $x\_i$ is a literal in $C\_j$, add the edge $(x\_i, w\_j)$.
* For each variable-clause pair $(x\_i, C\_j)$ such that $\overline{x}\_i$ is a literal in $C\_j$, add the edge $(\overline{x}\_i, w\_j)$.

If there is a solution to the SAT instance, you can obtain a solution to your problem by selecting a set $B$ that contains all true *literals* (i.e., if $x\_i$ is true, add $x\_i$ to $B$, otherwise add $\overline{x}$ to $B$). Now all vertices $u\_i$ have exactly one neighbor in $B$, while each vertex $w\_j$ has $\eta\_i \in \\{1,2,3\\}$ neighbors in $B$. By adding $3-\eta\_i$ vertices from $\\{v\_j, z\_j\\}$ to $B$ you can also satisfy the condition on $w\_j$.

The reverse direction is also true. For each variable $x\_i$ exactly one vertex in $\\{x\_i, \overline{x}\_i \\}$ is in $B$ and this determines the truth value of $x\_i$ in the satisfying assignment. Each vertex $w\_j$ must have at least one neighbor in $B$, showing that clause $C\_j$ is satisfied by the truth assignment.

See the following figure for an example:

---
Tags: complexity-theory, graphs, algorithm-analysis, np-complete, np
---


# Question
Title: Vertex cover problem modification such that every vertex is connected to the set, NP-Hard?
Being new to complexity problems, I've met a question that is quite similar to the Vertex Cover Problem and I am not sure if this one is NP-Hard. We know that the vertex cover problem is the following: given a graph $(V, E)$, selecting a set of vertices $S$ such that every edge $e \in E$ in the graph is connected to some vertices in $S$. The problem of minimizing the vertex cover problem is a well-known NP-hard problem.

My question is the following: given a graph $(V, E)$, selecting a set of vertices $S$ such that every node $v \in V$ is either in $S$ or connected to the nodes in $S$. Is this problem of minimizing the set of $S$ NP-Hard? This problem seems to be quite intuitive after learning the vertex cover problem, but I didn't find a similar question after searching. I apologize if I asked duplicated questions.

# Answer
This is called the Dominating Set problem, and it is indeed NP-hard. In fact, it's in some sense harder than Vertex Cover, since it's not fixed parameter tractable (FPT) with respect to the solution size $k$.
> 4 votes

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


# Question
Title: Does this problem map to the Set Packing problem?
Let $G(m,n)$ be A bipartite graph $G$ with paritions $m$ and $n$ with the property that partition $\mathit n$ has two types of nodes (type1 or type2).

Given $G(m,n)$ and $k \in \mathbb Z+$:

Does $\mathit S\subset \mathit m$ where |$\mathit S$| $=$ $\mathit k$ exist so that none of $\mathit S$'s nodes are adjacent to nodes of type1, but all type2 nodes in $n$ are adjacent to nodes in $S$? ($S$ is a subset of the $m$ partition).

I can see a solution is easily verified by checking that each type2 in $n$ has a neighbor in $S$ and that |$S$| $=$ $k$. This means the problem is in NP.

To reduce the problem of Set Packing to the above, I am thinking to consider the of all of $m$ nodes's neighborhoods as subsets. But from here I am not sure how to proceed with the problem mapping.

# Answer
You cannot reduce set-packing to your problem, unless P=NP.

There is a linear-time algorithm for your problem.

Remove all vertices of type 1 and all their neighbors. Let $m'$ (resp. $n'$) be the set of remaining vertices in $m$ (resp. $n$). If $|m'| \ge k$ and the neighborhood of $m$ contains all the vertices in $n'$, the answer is yes.

If any of the above two conditions is not satisfied then the answer is no:

* If $|m'| \< k$ then any set $S \subseteq m$ with $|S| \ge k$ contains a vertex that is adjacent to some vertex of type 1 in $n$.
* If there is a vertex $v \in n$ of type 2 that is not in the neighborhood of $m'$, then every vertex $u \in m$ that is adjacent to $v$ is also adjacent to a vertex of type 1 in $n$.
> 1 votes

---
Tags: complexity-theory, graphs, np-complete, bipartite-graph
---


# Question
Title: Finding the smallest number that scales a set of irrational numbers to integers
Say we have a set $S$ of $n$ irrational numbers $\left\\{a\_1, ..., a\_n\right\\}$.

Are there any known algorithms that can determine a **scaling factor** $s \in \mathcal{R}$ such that $s * a\_i \in \mathcal{N} \\;\forall a\_i \in S$, assuming that such factor exists? If multiple exist, how about the smallest one?

Moreover, I wonder, under what input conditions could one assume that an algorithm for this problem can't (or can) return a valid scaling factor?

# Answer
I'm assuming that $0 \not \in \mathbb{N}$, otherwise $s=0$ is a trivial solution.

If you input numbers contain at least one positive and one negative number there is no solution. If your input numbers are all negative, either there is a solution but no smallest solution, or there is no solution at all. You can decide which of the two is the case by solving the same problem on with the numbers multiplied by $-1$.

Assume then that all input numbers are positive.

If $s a\_1 = c$ and $s a\_2 = c'$ for $c,c' \in \mathbb{N}$, then $c' = s a\_2 = c \frac{a\_2}{a\_1}$, i.e., $\frac{a\_2}{a\_1}= \frac{c'}{c}$. This shows that you can only find a solution if all your irrational numbers can be obtained by multiplying $a\_1$ by some rational factor.

In this case you can consider the set of numbers $\\{1, \frac{a\_2}{a\_1}, \frac{a\_3}{a\_1}, \dots, \frac{a\_n}{a\_1}\\}$ instead. Since they are all rationals you can write them as $\\{1, \frac{b\_2}{c\_2}, \frac{b\_3}{c\_3}, \dots, \frac{b\_n}{c\_n}\\}$, where $b\_i,c\_i \in \mathbb{N}$ and $gcd(b\_i,c\_i)=1$. You can then find the minimum common multiple of the denominators and multiply it by $a\_1^{-1}$.
> 4 votes

---
Tags: number-theory
---


# Question
Title: A question regarding the Layered Architecture
Consider the following general form of a layered architecture :

I need to check my understanding about the second layer from top . More specifically I need to check my understanding the regarding the meaning of "User interface management " . According to my understanding , UI management is the code that underlies the UI , for example it is the code for each button and each UI elements . So for example , let us consider that the user needs to generate a report from a system that uses this layered pattern as its architecture. So what happens is the user press the generate report button then the underlying code of this button knows that it need to run the code of generate report system functionality ( which exists in the third layer). After that the generate report code ( lets assume that it is implemented as a class) will refer to the database to get the required info to generate this report and then the info will "propagates upward" until it reaches the UI again to be viewed by the user. So is this right ? In other words , is this what is the meaning of the User interface management ? and do I understand the mechanism of this architecture ?

# Answer
> 1 votes
"User Interface Management" does not have a standard accepted definition that I am aware of, so you'll have to work out what they mean by it based on context.

# Answer
> 0 votes
It's hard to say precisely what that means, but in most GUI systems, the user interface can be understood as having two broad parts:

1. The part that each program (usually referred to as "the client") manages itself.
2. The part that is managed centrally.

For example, each program is generally responsible for drawing the contents of its own window, but a window from one client can cover the window from another client, and this has to be handled by part of the operating system, usually referred to as the window manager. Similarly, some central component has to handle keyboard and mouse events and decide which application window should receive them.

In Windows NT, the architecture looks like this:

Clients (i.e. applications) use the Win32 subsystem (which is a combination of various shared libraries such as user32.dll) to manage their own windows, but arbitrating between windows and handling the display as a whole is implemented as a system service (win32k.sys).

MacOS has a similar structure, with most applications using Cocoa to manage their windows. The component that handles central management is called Quartz.

And on more traditional Unix systems like Linux, the X Window System has a fairly traditional client/server architecture too.

---
Tags: software-engineering
---


# Question
Title: Dynamic Program to solve an NP-complete partitioning problem
I have this problem for which I am struggling to find an efficient dynamic programming algorithm. Would be thankful for some help!!

Let $A = \\{ a\_1, a\_2, ..., a\_n \\}$ be a set where $a\_i \in \mathbb{N}$ for $i=1,...,n$.

The goal is to determine whether there exist two disjoint subsets $M,N \subset A$ such that the sum of all elements in $M$ is equal to exactly *$\textit{twice}$* the sum of all elements in $N,$ and $M \not = \emptyset$ and $N \not = \emptyset.$

# Answer
Let $\sigma(S)$ denote the sum of all the elements in $S$ and $A\_i = \\{a\_1, \dots, a\_i\\}$.

Given, $i=0,\dots,n$ and $w \in \mathbb{Z}$, define $OPT\[i,w\]$ as the mazimum cardinality of a subset $S \cup S' \subseteq A\_i$ where $S \cap S' = \emptyset$ and $\sigma(S) - 2\sigma(S') = w$. If no possible choice for $S$ and $S'$ exists, then let $OPT\[i,w\]=-\infty$.

According to the above definition: $$ OPT\[0, w\] = \begin{cases} 0 & \text{if } w=0 \\ -\infty & \text{if } w \neq 0 \\ \end{cases} $$

For $i\>0$: $$ OPT\[i, w\] = \max\\{ OPT\[i-1, w\], 1 + OPT\[i-1, w-a\_i\], 1+ OPT\[i-1, w+2a\_i\] \\}. $$

The answer to your problem is true iff $OPT\[n, 0\] \> 0$. Each $OPT\[i, w\]$ can be computed in constant time (if you have already computed the values of $OPT\[i-1, \cdot\]$). Moreover, there are only $O(n)$ possible choices for $i$ and $O(t)$ sensible choices for $w$, where $t = \sum\_{i=1}^n a\_i$. This gives you a dynamic programming algorithm with time complexity $O(n t)$ and space complexity $O(t)$.
> 2 votes

---
Tags: complexity-theory, algorithm-analysis, np-complete, dynamic-programming, efficiency
---


# Question
Title: Proof for LeetCode: 11. Container With Most Water problem
**UPDATE**: I abandoned this initial approach in favor of a more powerful invariant I worked out after posting. I've detailed that one in an answer below.

---

I'm new to algorithm correctness proof-writing but am keen to improve my skill there.

I have a first attempt here, but I think I'm missing a final step. The algorithm is for the *LeetCode: 11. Container With Most Water* problem.

I've shown to my satisfaction that only an "advance the lesser" move at any given point can possibly result in a greater area (water volume), but it feels like I'm missing the part where I can say "therefore this algorithm will always find the maximum".

Any pointers on process, notation, or formalisms is also greatly appreciated. This proof strikes me a bit as "workshop-grade" and I wouldn't mind getting a bit more elegant about it as I do others.

**Problem Statement**:

Given an array of non-negative integers hs (heights) where each represents a point at coordinate (i, hs\[i\]), n vertical lines are drawn such that the two endpoints of line i is at (i, hs\[i\]) and (i, 0). Find two lines, which together with the x-axis form a container, such that the container contains the most water.

Notation:

* H - Height
* W - Width
* A - Area

```
       |--W--|

       |           ___
       |     |      |
       |  |  |  |   H
    |  |  |  |  |   |
    +--+--+--+--+  ---
    0  1  2  3  4

```

For example, a maximal cross-section A of H ✕ W = 3 ✕ 2 = 6 is between offsets 1 and 3. Note there's another one of area 6 for range \[1..4\], so the maximum is not necessarily unique.

The solution approach which seems to work is the following:

1. Create index variables left (L) and right (R) initially positioned at the extreme left (0) and right (|hs|-1) of array `hs`.
2. Calculate the area as A = H ✕ W where H = min(hs\[L\], hs\[R\]) and W = R - L and record it as the maximal area so far.
3. Move the lesser of L or R toward the other.
4. Repeat until R == L, then return the maximum recorded.

Code would look something like this in Python

```
def max_water(hs):
    L, R = 0, len(hs) - 1
    max_A = 0

    while L < R:
        A = min(hs[L], hs[R]) * (R - L)
        max_A = max(max_A, A)
        if hs[L] <= hs[R]:
            L += 1
        else:
            R -= 1

    return max_A

```

My proof approach is to show that only advancing the lesser-height index can possibly increase the current area. The thing I don't quite get is whether this proves correctness; my sense is I'm missing a last step:

**Proof**

There are four possible cases produced by choosing to advance the lesser or greater-height index (toward the middle) and whether the "advanced-to" height is greater or lesser that the prior. For concise expression, I use L and R to represent the heights of those two positions:

Case 1: Advance greater, new height is greater

```
    |-----W-----|

             |
             |  |  ___
    |        |  |   |  H
    |  ...   |  |   |
    +--+--------+  ---
    L  ...   R' R

    L < R, advance R to R', R' > R

    then:

    * H' = H -- because L is unchanged and L = H is still the upper bound.
    * W' < W
    * => H' ✕ W' < H ✕ W
    * => A' < A

```

Case 2: Advance greater, new height is lower (or equal).::

```
    |-----W-----|

                |
             |  |  ___
    |        |  |   |  H
    |  ...   |  |   |
    +--+--------+  ---
    L  ...   R' R

    L < R, advance R to R', R' <= R

    then:

    * H' <= H -- H' cannot be greater than it was because L = H is still an upper bound.
    * W' < W
    * => H' ✕ W' < H ✕ W
    * => A' < A

```

Case 3: Advance lesser, new height is lower (or equal).::

```
    |-----W-----|

                |
                |  ___
    |           |   |  H
    |  |  ...   |   |
    +--+--------+  ---
    L  L' ...   R

    L < R, advance L to L', L' <= L

    then:

    * H' <= H
    * W' < W
    * => H' ✕ W' < H ✕ W
    * => A' < A

```

Case 4: Advance lesser, new height is higher.::

```
    |-----W-----|

                |
       |        |  ___
    |  |        |   |  H
    |  |  ...   |   |
    +--+--------+  ---
    L  L' ...   R

    L < R, advance L to L', L' <= L

    then:

    * H' > H
    * W' < W
    * => H' ✕ W' is either <, =, or > H ✕ W
    * => A' <, =, or > A

```

So the only way an area greater than the current area can possibly be found is by following the "advance the lesser" policy. All the other cases lead to a reduction in area.

What I'm not seeing is how that necessarily guarantees this algorithm will find the maximum.

# Answer
> 2 votes
I would suggest the following $O(n)$ approach using a *monotone stack* which is nothing but a regular stack but also satisifes the invariant that its elements are in monotone order. Say you want to make a strictly monotone stack $S$ which is increasing viewed from the last in to the first out: you would process elements $x$ in order with the following policy: pop $S$ until it is empty, or until the top is $\>x$, then push $x$.

Why might such a structure appear? Let's consider the half-problem where we find the largest container whose right side is smaller. (every container has a small side, which is why this is half a solution). Suppose that when viewed from left to right, we have 2 segments $h\[i\_1\]$ and $h\[i\_2\]$ with height $5$. Then clearly any container whose right and small side ends at $i\_1$, can be extended to end at $i\_2$, and the resulting container is strictly larger. Even further, we see that $i\_1$ is made irrelevant by *any* $i\_2\>i\_1$ and $h\[i\_2\]\geq h\[i\_1\]$. This "being made irrelevant" corresponds to the popping while building the stack, which can be implemented exactly as described above.

So now let's say we went through $i=1$ to $i=n$, and we have our stack. How do we actually calculate the largest containers with segments as the smaller right ends?

Again we go through $i=1$ to $i=n$, but with our stack in hand. Consider $h\[1\]$. Case 1) it is smaller than the top of the stack (call it $j$) then we can ignore it and move on, since the container formed with left side $h\[1\]$ and right side $h\[j\]$ is by definition not the type of container we are considering (we are only looking at right-side-smaller containers). And we can even ignore all containers with left side $h\[1\]$ and right side $h\[j'\]$ for $j'$ under $j$ in the stack (because it is monotone). Case 2) if $h\[1\]\geq h\[j\]$, then $1$ is the best possible left side for a container whose right small side is $h\[j\]$. Ditto with any $j'$ under $j$ in the stack, which satisfies $h\[1\]\geq h\[j\]$. So we pop from the stack until we have some $h\[1\]\< h\[j\]$, calculating the area each time, then continue with $i=2$, etc. It's not hard to prove that the stack empties, and that each time you pop an element from the stack, you have calculated the largest container with that element as its smaller right side.

# Answer
> 1 votes
**UPDATE**: Since posting this question I made some progress on my own. Since this question did not attract any other answers I thought I'd add what I came up with.

My conclusion is my original insight into the problem was incomplete. While the "only-advancing-lesser-index-can-increase-area" insight is true, and in the right direction, there is a deeper insight which simplifies the proof substantially.

I won't write it out completely, but I will provide an intuitive sketch.

**Key Insight:** For any given choice of endpoints, the container produced is the *strict maximum* of any other containers formed using the lesser endpoint and moving the other endpoint "inward" toward it. This means all those cases can be excluded without computing their area. Advancing the lesser index at each step is doing just that, skipping checking all the cases known to be lower. This brings the time complexity down from O(n^2) to O(n).

Here's a sketch of a proof:

* `L` and `R` are the heights of the left and right walls respectively. By convention, `L` is the lesser (or equal) of the two. The sequence could be reversed as needed to put the lesser on the right if you wanted and all the argumentation would still hold.
* `H' <= H`. The height of the container can never be greater than it already is because `L` is unchanged. There are two cases:

+ If `R' >= L`, `min(R', L) = L` and so `H'` still equals `L`.
    + If `R' < L`, `min(R', L) = R'` and `H' < H`.
* `W' < W`. Because we are moving `R` "inward", all containers so produced will be narrower.
* =\> `H' ✕ W' < H ✕ W`

=\> `A' < A` for all remaining containers starting at `lidx` and those can be eliminated from consideration.

---
Tags: proof-techniques, correctness-proof, check-my-answer
---


# Question
Title: Proof of greedy algorithm to minimize cost of job assignment over unlimited number of machines
I'm trying to prove a greedy algorithm works for a specific problem:

> You have $n$ jobs and some finite number of machines. (The number of machines doesn't matter; we assume you have enough to run all the jobs.) Each job $j$ has a size $s\_j$. Each machine $i$ has a constant associated with its speed, $p\_i$. The cost of running job $j$ on machine $i$ is simply $s\_j \cdot p\_i$. We can only assign at most $k$ jobs to one machine. How should the jobs be assigned to minimize the sum of the costs on all machines (that have been given jobs)? I.e., minimize $\sum\_{i,j} s\_j \cdot p\_i$ over all assignments of a job $j$ to a machine $i$. (Note that there is no penalty for assigning lots of jobs to a specific machine. We aren't trying to balance out the number of jobs assigned to each machine.)

The simple greedy algorithm is to first sort the jobs from greatest size to least size, and the machines from fastest (least $p\_i$ in this case) to slowest, and then assign the $k$ largest jobs to the fastest machine, second $k$ largest jobs to the second fastest machine, etc. (So in other words, pair off large $s\_j$ with small $p\_i$ and vice versa.)

I'm now trying to prove this algorithm is correct. My first try was to show that the greedy algorithm stays ahead. I reasoned that the optimal algorithm must also use the fastest machines (or else it is trivial to show it isn't actually optimal), and therefore if we look at the machines from fastest to slowest, we can consider the first job for which they differ. But then it isn't necessarily true that the greedy algorithm is doing better at this point as the optimal algorithm could minimize cost for that specific slot by putting in a smaller job (even though it actually hurts it later).

I also tried doing an overall induction on the number of jobs. Say we show it it optimal for $n$ jobs. Can we show it is optimal for $n+1$ jobs given the same options for machines? Again, it isn't clear how to make this argument since we can't just slide in job $n+1$; maybe the optimal assignment suddenly follows a wildly different pattern.

Thanks for the help!

# Answer
It is easy to see the fastest $m=\lceil n/k\rceil$ machines are used. Suppose the speeds of these machines are $p\_1\le p\_2\le\cdots \le p\_m$, then we want to minimize $$p\_1s\_{\sigma(1)}+\cdots+p\_1s\_{\sigma(k)}+p\_2s\_{\sigma(k+1)}+\cdots+p\_2s\_{\sigma(2k)}+\cdots+p\_ms\_{\sigma(n)}$$ over all permutations $\sigma$.

By the rearrangement inequality, the sum above is minimized when $s\_{\sigma(1)}\ge s\_{\sigma(2)}\ge\cdots\ge s\_{\sigma(n)}$, so your greedy algorithm is indeed correct.
> 1 votes

# Answer
I figured it out. Turns out the solution is deceptively simple, but in the details it is somewhat different than proofs I have seen for other greedy algorithms. We basically show that any output besides the one the greedy algorithm returns can be improved further.

To do this, consider two jobs with sizes $s\_j$ and $s\_i$ such that $s\_j \> s\_i$. Furthermore, consider two machines with constants $p\_l, p\_k$ such that $p\_l \> p\_k$. We show that the best way of assigning $s\_j, s\_i$ to $p\_l, p\_k$ is to assign $s\_j$ (the larger job) to $p\_k$ (the faster machine) and $s\_i$ (the smaller job) to $p\_l$ (the slower machine). Since there are only two possible assignments, in other words we want to show $$s\_j \cdot p\_k + s\_i \cdot p\_l \le s\_j \cdot p\_l + s\_i \cdot p\_k$$

To do so we set $s\_i = x, s\_j = x+a, p\_k = y, p\_l = y + b$ for some $x,y,a,b \ge 0$. So equivalently we want to show $$(x+a)\cdot y + x \cdot (y + b) \le (x + a)(y + b) + xy$$

This can be seen simply by simplifying. Thus we have shown that for two jobs and two machines, cost is minimized by assigning the larger job to the faster machine and the smaller job to the slower machine.

It quickly follows that the greedy algorithm is optimal because for any other output, there will be a pair of assignments that don't satisfy the "larger job to faster machine, smaller job to slower machine" rule. And thus by switching the assignments of this pair, we lower the total cost.
> 1 votes

---
Tags: algorithms, algorithm-analysis, optimization, greedy-algorithms, scheduling
---


# Question
Title: Bit representation of the hashing multiplication method
In the picture below from CLRS, I fail to understand **why** exactly $h(k)$ = the $p$ **highest-order** bits of the **lower** **w-bit** half of the product.

For context, this is supposed to compute $h(k) = \lfloor m (k A \\; \text{mod} 1) \rfloor $

---

For further context, CLRS mentions the following, but I still don't quite get why those $p$ **highest-order** bits are the ones we are looking for.

# Answer
> 3 votes
$(kA \bmod 1)$ is in the range $\[0,1)$. So multiplying that by $2^p$ gives a number in the range $\[0,2^p)$. That is:

$$\left\lfloor 2^p (kA \bmod 1) \right\rfloor = \left\lfloor 2^p (kA \bmod 1) \right \rfloor \bmod 2^p$$

Once you've worked that out, it's not too hard to see:

$$\left\lfloor 2^p (kA \bmod 1) \right \rfloor \bmod 2^p = \left\lfloor kA 2^p \right\rfloor \bmod 2^p = \left\lfloor \frac{ks}{2^{w-p}} \right\rfloor \bmod 2^p$$

So you can implement this by taking $ks$, shifting it $w-p$ bits to the right, then taking the lowest order $p$ bits. Which is exactly the same as taking the highest order $p$ bits of the low word.

---
Tags: hashing
---


# Question
Title: How to get an element from an existential proposition in Type theory proof assistant (Lean prover)
I am trying to implement set theory in type theory from scratch, just for self pedagogical purposes. Specifically, I'm using the Lean Prover, and defining the element-of relation from scratch using the symbol $\epsilon$, just for pedagogical purposes.

## What I'm trying to do

However, I'm unsure how to even define the notion of **inductive set** in this way. I am using the definition of inductive set:

> a set $S$ is inductive if $\emptyset \in S \land \forall x\in S, x\cup \\{x\\} \in S$. The axiom of infinity then states that there exists an inductive set.

Where I'm getting stuck is at even defining the set $\\{x\\}$ in Lean. I know from the axiom of pairing, that there exists a set, which we denote by $\\{x\\}$, which is shorthand for $\\{x,x\\}$, such that $\forall u, (u\in \\{x,x\\} \iff u = x \lor u = x)$.

## What goes wrong

However, in type theory this axiom doesn't give me the actual set, it gives me an inhabitant of the existential proposition type. I've tried to use the "let" command to extract from this the actual set, but I get the error: "*invalid match/convoy expression, expected type is not known*". This makes me suspect I shouldn't be using this command here at all (I think it's only intended for proofs).

Maybe instead I should be using the axiom of choice?

## My code

```
constant Set : Type
constant In : Set → Set → Prop
infix  `ε`:50  := In

axiom pairing : ∀X:Set, ∀Y:Set, ∃S:Set, ∀u, u ε S ↔ u = X ∨ u = Y
axiom union : ∀X, ∀Y, ∃S, ∀u, u ε S ↔ u ε X ∨ u ε Y
infix `U`:49 := union

definition inductiveset (S:Set) : Prop := ∀x:Set,
let ⟨ (Q:Set), (h: ∀u, u ε S ↔ (u = x ∨ u = x) ) ⟩ := (pairing x x) in
     x ε S → (x U Q) ε S

axiom infinity : ∃S, inductiveset S

```

## Summary

So basically:

* **How do I actually define the inductive set property in Lean?**
* **Can I just extract a function $f:X\to Y$ from proof of a proposition $\forall x:X,\exists y:Y, ...$?**
* **should I use the axiom of choice here?**

## Edit: Defining an operation from an existence theorem.

**unique existence case.** Suppose I have the following:

```
constant T:Type
constants P:T → T → Prop
axiom ....
......
%Now, after 5 pages of lemmas, I prove:
theorem uniqueexistence : ∀t:T, ∃u:T, ( P t u ∧ ∀v:T, ¬v=u → ¬(P t v) )
                        := λ t:T, complicated_proof lemma238 t

```

Suppose I have a Lean file like the one above, How do I then create an operator `F:T → T` together with a theorem that `∀t:T, P t (F t)`?

**nonuniqueness case.** Similarly, if instead I don't have uniqueness, how do I randomly pick such an operator?

```
theorem nonuniqueexistence : ∀t:T, ∃u:T, P t u
                        := λ t:T, complicated_proof lemma238 t

```

How do I randomly (using the axiom of choice) pick an operator `F:T → T` together with a theorem that `∀t:T, P t (F t)`?

# Answer
The existential form of the axioms of set theory is convenient for the meta-theoretic explorations of set theory, such as forcing etc., where it is important to have a minimal language to worry about (only $\in$ relation). But even just stating the axioms of set theory without any constants and operation symbols is pretty haunting, see this gist of mine.

If you want a workable set theory you will have to rephrase your axioms so that they are not existential statements but rather *operations*. For example, define a `union : Set → Set → Set` operation and an axiom which states that `u ε union X Y ↔ u ε X ∨ u ε Y`. Formally, set theory does not have these operations, but every single development of set theory relies on the meta-theorem which says that introducing such constants is conservative (they can be eliminated). Also for the inductive set, introduce a constant `S : Set` and the axiom `inductiveset S`.

As a general advice, when formalizing mathematics in a proof assistants, one has to be quite flexible about organization of material. Traditional organization is good for teaching and writing textbooks, and so it may not align well with the demands of formalization.

For example, it looks to me at first sight that you would benefit by formalizing not only sets, but also classes. The class comprehension notation $\\{ x \mid \phi(x) \\}$ is very expressive and convenient, and easily formalized in terms of propositional functions on $\mathsf{Set}$. With it, you can *define* many operations on classes and then state that they are sets in terms of axioms. For example, rather than axiomatizing a union operation we just define `union X Y` to be the *class* `{u | u ε X ∨ u ε Y}` and then state that this class is a set. I suppose you could look at Von Neumann–Bernays–Gödel set theory.
> 8 votes

---
Tags: type-theory, sets, proof-assistants, automated-theorem-proving
---


# Question
Title: Implementing an efficent priority queue using only stacks
Is it possible to implement an efficient priority queue (as efficient as a heap) only using the stack data structure?

The usual efficiency for a priority queue which is implemented using a heap is :

* get min - $O(1)$
* extract min - $O(\log n)$
* add - $O(\log n)$

Would it be possible to do something with the same complexity using only stacks?

I want to implement A\* (which uses a priority queue to prioritize nodes) as a pathfinding algorithm inside Minecraft, but Minecraft doesn't allow random access, and the most efficent dynamic structure that can be implemented in it is a stack.

# Answer
Unfortunately, it's not possible. The order you extract items from the stack depends only on the order they're pushed, regardless of the values in those items; a priority queue needs items to be removed in an order that depends on the value of the items.
> 2 votes

# Answer
You can do such a perfect representation of priority queues using (binary) heaps data structure, using it you can implement stacks and queues...

In priority queues it's a matter of preference, not FILO principle like in stacks.

You can find all of this in Cormen et al., Introduction to Algorithms, 3rd edition.

okay, implementation of priority queues using heaps is related to the property of the heap, max\_heap or min\_heap so Min\_priority\_queue can be implemented using min\_heap by using the procedures used for heaps like BUILD\_HEAP() first, MAX\_HEAPIFY(), INCREASE\_KEY(), INSERTION and DELETION.

note that (binary)heap itself is an array object can be shown as a nearly complete binary search tree...

for stack implementation (there is psudo code)

```
class Stack
    Inner class Element
       int priority   // priority of the element.
       Key element    // the element it self

    MAX_PRIORITY_QUEUE<Element> queue;
    next_priority = 0;

    void push(Key x) // value of the pushed element
        q.push(Element(next_priority++, x))

    Key pop()
        // as popping some element the next push must take its place
        next_priority--
        return queue.pop().element

```

To implement queue using priority queue(HEAP) the same but the priority decreases one after another.
> 0 votes

---
Tags: stacks, priority-queues
---


title: Tightening application rules for STLC

text:
# Question
Title: Tightening application rules for STLC
The syntax STLC is usually written:

$e ::= x |\lambda x : \tau . e|(e \space e)|c$

However, the application rule appears to accept all expressions on the left hand side. Shouldn't the application rule be written:

$(\lambda x : \tau . e \space e : \tau)$ ?

The only time an application makes sense both intuitively and type-wise is by reducing and abstraction by replacing its variable with an expression. All other cases would be:

$(x \space e)$ makes no sense. By the time application can take place x will be substituted with its bound expression. By this logic it will be either an abstraction, as labeled okay above or something else, discussed below

$(c \space e)$ again, you can't apply to a value.

$((e \space e) \space e)$ this is not an issue because applications resolve to an expression, and following that recursive logic it will resolve to one of the aforementioned cases.

# Answer
> Shouldn't the application rule be written:
>
> $(\lambda x : \tau . e \space e : \tau)$ ?

No, there are at least three problems with this formulation:

* First, it is important that the first time can be a variable. For example, we want to allow the term $$ x \\; y $$ Why do we want to allow this? Well we want to be able to apply a function to an argument. For example, the following lambda term is a function which applies $x$ to $y$: $$ \lambda x: \tau\_1 \to \tau\_2. \lambda y: \tau\_1. (x \\; y) $$
* Second you are assuming the first term has already been reduced. This is not generally true. Although *once reduced,* the term $e\_1$ in $(e\_1 \\; e\_2)$ should usually be a lambda expression (or a variable), this may not hold before it has been evaluated.
* The third problem is really a misunderstanding, not a concrete issue with your formulation: **in STLC, we allow terms that are not well-typed.** For example, if there are base types including numbers and Booleans, then we can write nonsense like $$ \text{true} \\; 3 $$ and this is a valid lambda term, just not a *well-typed* one. So your question seems to want to make sure that the application rules is well-typed, but that will be part of the typing rules, not part of the definition of a lambda term itself.

> The only time an application makes sense both intuitively and type-wise is by reducing and abstraction by replacing its variable with an expression.

That is correct, and this is going to be the motivation for the typing rules. In fact, the typing rule will say this exactly: the term $e\_1 \\; e\_2$ will be well-typed only if $e\_1$ is a function $\tau\_1 \to \tau\_2$ and $e\_2$ is a value of type $\tau\_1$. But for the reasons above, it is important that these restrictions be on the typing level, not baked into the syntax.

> $(x \space e)$ makes no sense.

It does make sense: but only in a context where $x$ is a variable of a function type. Think of a variable that may be assigned to a value; if it is assigned to a value which is a function, then this makes sense.

> $(c \space e)$ again, you can't apply to a value.

It's true that this makes no sense, but we allow it anyway; we just don't say that it is well-typed.

> $((e \space e) \space e)$

As you said this case may resolve to one of the other cases, but we are defining the syntax here, not the semantics. So it doesn't imply that we should rule it out just because resolves to the other cases; it is still a valid lambda term, just one that is not fully reduced.
> 4 votes

# Answer
No, because there are terms of function type $\sigma \to \tau$ which are not $\lambda$-abstractions, and neither is it true that every term of type $\sigma \to \tau$ is equal to a $\lambda$-abstraction – consider a variable of type $\sigma \to \tau$.

It is true that every *closed* term of function type normalizes to a $\lambda$-abstraction, but that is quite irrelevant and plays no importance when we postulate *general* rules that should work on all rules. You are attempting to mix the structural rules governing $\lambda$-calculus with *theorems* about it that cannot be proved without first having such structural rules available in full generality.
> 4 votes

---
Tags: lambda-calculus, type-theory
---


title: Number of sequnces with given value

text:
# Question
Title: Number of sequnces with given value
> Consider a valid string with bitwise operations (AND, OR, XOR), and also placeholders $X$, where each $X$ stands for an arbitrary number from $\\{0,1\\}$. There are $n$ many $X$s, so there are $2^n$ possible sequences. How many out of the $2^n$ strings have value $0$? How many have value $1$?

My approach to this problem was, I assumed that the interpretation of strings is done by associating left-to-right (that is, $0 \oplus 1 \land 0$ means $(0 \oplus 1) \land 0$). I will use $\lor,\land,\oplus$ for OR, AND, XOR.

Let $s$ be an arbitrary string with $n$ many $X$s that evaluates to 0, and let $t$ be an arbitrary string with $n$ many $X$s that evaluates to 1.

Then, the strings with $n+1$ many $X$s that evaluate to $1$ are: $$ t \lor 0, s \lor 1, t \lor 1, t \land 1, s \oplus 1, t \oplus 0. $$ The ones that evaluate to 0 are: $$ s\lor 0, s\land 1, s\land 0, t\land 0, s\oplus 0, t\oplus 1. $$

Fixing a sequence of operations, let $S(n)$ be the number of strings with $n$ many $X$s that evaluate to 0 with the given operations, and let $T(n)$ be the number that evaluate to 1.

Denote the $i$'th operation by $O\_i$. Then, just counting the combinations in the previous paragraph for each operator, I get the following recurrence relations: $$ \begin{align} &S(1)=T(1)=1 \\ &S(n+1),T(n+1) = \begin{cases} S(n), S(n)+2T(n) & \text{if } O\_{n+1}=\lor \\ 2S(n)+T(n), T(n) & \text{if } O\_{n+1}=\land \\ S(n)+T(n), S(n)+T(n) & \text{if } O\_{n+1}=\oplus \end{cases} \end{align} $$

> What should I do if my assumption was wrong, that is, if the sequence could contain parentheses, e.g. $(X \lor (X \oplus X))$?

# Answer
You should first build the binary expression tree of the given boolean expression. You can then do a Depth First Search on this tree, and start computing the answers from the leaves to the root (bottom to top), similar to the way you've done in your approach.

But instead of $S(i)$ denoting the number of assignments of the first $i$ $X$s which evaluate to 0, it will now be $S(u)$ denoting the number of assignments of the $X$s which lie in the subtree of $u$, which evaluate the expression until $u$ to be 0. Here $u$ refers to a node in the tree. Similarly $T(u)$ is defined for evaluation to 1.

The base case would be when $u$ is a leaf (which would happen when it corresponds to an operand), and both $S(u)$ and $T(u)$ would be equal to 1 in that case. Else, if $u$ is an internal node (which corresponds to an operator), you compute the $S$ and $T$ values by looking at the $S$ and $T$ values of its children, $c\_1$ and $c\_2$, and applying recursion similar to what you had in your answer:

If $u$ is an OR node,

$S(u) = S(c\_1) S(c\_2)$

$T(u) = S(c\_1) T(c\_2) + T(c\_1) S(c\_2) + T(c\_1) T(c\_2)$

If $u$ is an AND node,

$S(u) = S(c\_1) T(c\_2) + T(c\_1) S(c\_2) + S(c\_1) S(c\_2)$

$T(u) = T(c\_1) T(c\_2)$

If $u$ is an XOR node,

$S(u) = S(c\_1) S(c\_2) + T(c\_1) T(c\_2)$

$T(u) = S(c\_1) T(c\_2) + T(c\_1) S(c\_2)$

And the final answer would be $S(\mathit{root})$ and $T(\mathit{root})$.
> 1 votes

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


# Question
Title: Usual distances on DFAs (Deterministic Finite Automata)?
I've been searching in the literature for examples of **distances defined on the set of the DFAs (or on the set of minimal DFAs) that are defined on a given alphabet sigma**.

Since the languages they describe (regular languages) can potentially have an infinite size, defining a distance is not a trivial matter.

Nevertheless, having a distance on these objects can be useful, in order to fit these in metric spaces, which allows for a range of things (in my case to assess the performance of an algorithm).

My only consistent idea so far is to create a distance similar to the edit-distance in labeled graphs on the minimized DFAs.

Does someone have ever heard of other distances ?

# Answer
There are many possible distance metrics, and without any criteria, we have no basis to choose. Here are two plausible ones.

Let $L\_1,L\_2$ be the languages of the two DFAs. Let $L$ be the symmetric difference of those languages (i.e., $(L\_1 \setminus L\_2) \cup (L\_2 \setminus L\_1)$).

One dissimilarity measure is $d(L\_1,L\_2) = 2^{-n}$ where $n=\min\\{|x| : x \in L\\}$, i.e., $n$ is the length of the shortest word in $L$. This is not a distance metric, because it does not satisfy the triangle inequality.

Another possibility is to use the density of $L$, i.e.,

$$d(L\_1,L\_2) = \sum\_{n=0}^\infty {|L \cap \Sigma^n| \over 2^n |\Sigma|^n}.$$

This one *is* a distance metric.

These can be computed given DFAs for $L\_1,L\_2$. You can easily compute a DFA for $L$. Then, it is easy to find the length of the shortest word in $L$ using breadth-first search.

Computing the density is a bit trickier, but can be done efficiently using a little more math. Let $A$ denote the transition matrix of the DFA for $L$, i.e., $A\_{ij}=1$ if there is a transition (on any input symbol) from state $i$ to state $j$, or $A\_{ij}=0$ if not. Let $s$ denote the one-hot vector indicating the start state, i.e., $s\_i=1$ iff $i$ is the start state, and $f$ denote the one-hot vector indicating the final states, i.e., $f\_i=1$ iff $i$ is an accepting state. Now $|L \cap \Sigma^n| = s^\top A^n f$, so the distance is given by

$$d(L\_1,L\_2) = \sum\_{n=0}^\infty {s^\top A^n f \over 2^n |\Sigma|^n} = s^\top C f$$

where

$$C = \sum\_{n=0}^\infty B^n = {1 \over I - B} = (I - B)^{-1}$$

where $B={1 \over 2|\Sigma} A$ and $I$ represents the identity matrix. This can be computed in time proportional to the cube of the number of states in the DFA for $L$ using standard algorithms for matrix inversion.
> 4 votes

# Answer
I finally found in the literature a paper answering my question precisely, as well as providing a framework to define distances between languages.

The method is very similar to the one explained by @D.W in his answer (it is based on defining a distance by computing a density on the symmetric difference), it only provides a slightly more formal and more general framework, and also provides several examples of possible metrics.

The paper can be found here, it is **'Approximate Language Identification' by R.M. Wharton (1974)**.
It is one of the founding papers for grammatical inference of languages though probabilistic language models.
> 0 votes

---
Tags: finite-automata, edit-distance
---


# Question
Title: Proving that a language satisfies the pumping lemma condition
I have to proof that $L = \\{ a^{2i} b^{2j} \mid i,j \in \mathbb{N} \\}$ is a regular language, and how it meets the Pumping Lemma condition.

For the PL, there is a string $xyz \in L$ such that $y \neq \epsilon$ and any string $xy^nz$, for any $n \ge 0$, is in $L$.

From what I understand, I cannot use the pumping lemma to prove that a language is regular.

I am a bit puzzled how I have to show that this $L$ meets this condition. Do I have to divide a string into $xyz$ again?

# Answer
The language is regular since it is the language of the regular expression $(aa)^\*(bb)^\*$.

Every regular language satisfies the conditions of the pumping lemma – this is precisely the statement of the pumping lemma! So one way to show, from first principles, that this language satisfies the conditions of the pumping lemma would be to just repeat the proof of the pumping lemma.

However, in this case we can show this more directly. We will show that the pumping lemma holds with a pumping constant of $p = 2$. Suppose that $w = a^{2i} b^{2j} \in L$. Note that $|w| \geq 2$. We consider two cases:

* Case 1: $i \neq 0$. In this case, we can break $w$ in the following form: $x = \epsilon$, $y = a^2$, $z = a^{2(i-1)} b^{2j}$. We have $w = xyz$, $|xy| = 2 \leq p$ and $y \neq \epsilon$. For every $n$, $xy^nz = a^{2(i-1+n)} b^{2j} \in L$.
* Case 2: $i = 0$. In this case, $j \neq 0$. We break $w$ into $x = \epsilon$, $y = b^2$, $z = b^{2(j-1)}$. The rest of the proof is very similar.
> 2 votes

---
Tags: formal-languages
---


title: Feeling guilt tripped in linked list

text:
# Question
Title: Feeling guilt tripped in linked list
Okay, so I have been doing competitive programming for the past few days in C++. And day before yesterday, I stumbled upon this concept of linked list.

Now, what I do while implementing most problems pertaining to linked list is that I store all the values of the linked list nodes in a vector, and do operations on them which has been asked as per the question, then refill the nodes with the newly updated values of the vector. Now, most of the questions can be done by me really easily, as I am pretty comfortable with using vectors now. I just wanted to ask this community if this was a bad approach towards using linked list, and should I stop using it altogether.

I will give an example to sort a linked list in $O(N\log N)$ time, which I used. Following is a function that sorts a linked list-

```
ListNode* Solution::sortList(ListNode* A) {
    vector<int> vect;
    ListNode* temp=A;
    while(A!=NULL)
    {
        vect.push_back(A->val);
        A=A->next;
    }
    A=temp;
    sort(vect.begin(), vect.end());
    for(int i=0; i<vect.size(); i++)
    {
        A->val=vect[i];
        A=A->next;
    }
    return temp;
}

```

# Answer
> 2 votes
Let's show that $\\{a^n b^n : n \geq 0\\}$ is not regular using Myhill's criterion (there are infinitely many equivalence classes):

> The pumping lemma shows that $\\{a^n b^n : n \geq 0\\}$ is not regular. According to Myhill's criterion, if a language is not regular then it has infinitely many equivalence classes. Therefore the language has infinitely many equivalence classes, and consequently, by Myhill's criterion is not regular.

This may sound silly, but it is very similar to how you are using vectors to solve questions "using linked lists".

The alternative is to look for algorithms that can be implemented directly on linked lists. For example, one sorting algorithm which can be implemented directly is *merge sort*. Merge sort consists of the following operations:

* Divide the input into two sublists of nearly equal size. Easy to do on a linked list using a simple scan.
* Recursively sort each sublist.
* Merge the two sorted sublists. The merge algorithm is also easy to implement on a linked list.

In contrast, an algorithm like quicksort seems hard to implement directly without having random access.

---
Tags: algorithms, time-complexity, data-structures, optimization, linked-lists
---


# Question
Title: Why DCFL is not closed under kleene star?
I have read somewhere that DCFL is not closed under kleene star. but I haven't found any example

# Answer
The language $\\{a^nb^nc^k \mid n,k \ge 1\\} \cup \\{a^nb^kc^n \mid n,k \ge 1\\}$ I believe is a standard example of a non-deterministic context-free language. At least intuitively it is clear that we can push the $a$'s, but we do not know when to pop (compare with $b$'s or with $c$'s?)

The language $L = \\{ a^nb^nc^k \mid n,k \ge 1\\} \cup \\{d\\;a^nb^kc^n \mid n,k \ge 1\\}$ however, *is* deterministic. The $d$ prefix gives away which part we are in.

Now consider $(\\{d\\} \cup L)^\*$.
> 8 votes

# Answer
### Disclaimer

This is a hopefully improved version of the answer of @RAGHAVAMAJJARI. I wrote it to understand what is going on in the proof.

### Claim

The Kleene closure of a deterministic context free language DCFL is not a DCFL.

### Proof

Let $\newcommand{\lang}{\mathcal L}\lang = \lang\_1 \cup \lang\_2 = \newcommand{\set}\[1\]{\left\\{#1\right\\}}\newcommand{\Nset}{\mathbb N}\set{c a^n b^n \mid n \in \Nset\cup\set 0} \cup \set{ a^mb^{2m} \mid m\in\Nset}$, which is a deterministic context free language thanks to the letter $c$ in front of every word in $\lang\_1$. If $\lang^\ast$ is the Kleene closure of $\lang$, any string $x\in\lang^\ast$ should be a concatenated permutation of words $y\_i \in \lang$, with the concatenation repeated numerably many times, zero included.

Now let $y\_1 = c$ and $y\_2 = ab^2$, which are both clearly in $\lang$. This can be seen by letting $n = 0$ and $m = 1$ in the sets $\lang\_1$ and $\lang\_2$. Because of this, the word $cab^2$ is in $\lang^\ast$, which can again be seen by in the first iteration taking $c$ and on the second iteration taking $ab^2$ from the set and forming a concatenation of these two words.

As both parts of the union that form $\lang$ are DCFLs, they are both recognized by the deterministic pushdown automata (DPA) $A\_1$ and $A\_2$, which are shown in the two below images respectively. In order to recognize the word $y\_1y\_2 = cab^2$, you would have to form a new automaton $A = A\_1A\_2$, by connecting the individual automata appropriately. However, this connection cannot be made deterministically.

Suppose it could. But as demonstrated in the below picture, the only way to recognize the word by combining the two automata $A\_1$ and $A\_2$ would be to either have a spontaneous transition $\newcommand{\trans}\[1\]{\overset{#1}{\longrightarrow}} s\_1\trans{\epsilon, \sqcup/ \epsilon}t\_0$ (where $\sqcup$ is the base symbol used to initialize the stack), or $s\_1 \trans{\epsilon, \epsilon / \epsilon} t\_1$. This is not deterministic behaviour, as now there is an empty transition out of a state that already has a non-empty transition out of it. This is a contradiction.

Therefore the set of DCFLs is not closed under the Kleene closure. We are therefore done with the proof.
> 3 votes

# Answer
proving kleene closure of DCFL is not DCFL
> -2 votes

---
Tags: formal-languages, context-free, closure-properties, pushdown-automata
---


title: NRU: Page fault on writing?

text:
# Question
Title: NRU: Page fault on writing?
I am trying to understand the concept of NRU from the following link. I have got some problem in understanding the text below:

NRU page replacement Algorithm

> If the hardware does not have these bits, they can be simulated as follows. When a process is started up, all of its page table entries are marked as not in memory. As soon as any page is referenced, a page fault will occur. The operating system then sets the R bit (in its internal tables), changes the page table entry to point to the correct page, with mode READ ONLY, and restarts the instruction. If the page is **subsequently written on, another page fault will occur**, allowing the operating system to set the M bit and change the page's mode to **READ/WRITE.**

I have bolded the text. I have two problems: Page fault occurs if the page is not in memory but the above text says that (a)the page fault occurs at the time of modifying or writing the page? I can’t understand that. (b) Also I cant understand the text “, allowing the operating system to set the M bit and change the page's mode to READ/WRITE.” What is meant by READ/WRITE? If we are setting the M bit then it should be WRITE mode only? Why the text says READ/WRITE mode. Somebody please guide me.

# Answer
The idea is to mark a read/write page as read-only when loading it into memory (or after writing it out). If it is written to, a fault will occur. When handling the fault, the operating system looks at it's tables, and notices it should be writeable. So it can record it as "written to" (modified) in it's tables, make it read/write, and allow the operation to proceed. Later writes just add insult to injury, no need to keep track of them.
> 1 votes

---
Tags: operating-systems, page-replacement
---


# Question
Title: Why is $FOLLOW$ not necessary for $LL(1)$ grammars with no $\epsilon$ transitions?
I'm aware of how $FIRST$ and $FOLLOW$ sets are used to construct a parsing table for $LL(1)$ grammars.

However, I've encountered this statement from my notes:

> With $\epsilon$ productions in the grammar, we may have to look beyond the current non-terminal to what can come after it

In my opinion, this suggests that $FOLLOW$ is not necessary for $LL(1)$ grammars that have no $\epsilon$ transition. Am I wrong? And if I'm not, why is this the case?

Thanks

# Answer
> 3 votes
That's correct for $LL(1)$: if there are no $\epsilon$ productions, the $LL$ parser-generation algorithm will never consult $FOLLOW$, because it only does that if it finds $\epsilon$ in the $FIRST$ set for the first non-terminal in the right-hand side of a production. (So it might not need the $FOLLOW$ sets even if there are some $\epsilon$ productions, provided that none of those productions occur at the beginning of a right-hand side.)

The observation doesn't generalise well to other values of $k$. You'll need $FOLLOW\_k(\alpha)$ if any production can derive a string whose length is less than $k$.

---
Tags: formal-languages, formal-grammars, compilers, parsers, lexical-analysis
---


title: Is this a valid DFA for (a|b)*abb?

text:
# Question
Title: Is this a valid DFA for (a|b)*abb?
I'm trying to come up with an alternate DFA for accepting `(a|b)*abb` than the one present in the dragon book. Here's the one I tried:

It seems valid to me but I'm not sure. Also, is there a way to check for validity of automatons so that I don't end up bugging you guys next time?

# Answer
Your DFA does not recognize $(a|b)^\*abb$. For example it does not recognize $abb$.
> 2 votes

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


# Question
Title: Algorithm for finding "mean center" of unweighted graph
I have a large sparse unweighted undirected graph (20M vertices, 60M edges) and would like to find what I'm calling the "mean center" (the vertex w/ shortest mean distance to all other vertices. Does this already have a name?). I know of an $O(N^2)$ solution: Starting at every vertex: BFS to calculate the mean distance to all other vertices, choose the minimum. But $N^2$ is too slow for a graph this size, is there any way to calculate the "mean center" in faster than $N^2$ time? Are there any good approximation algorithms? Or more efficient algorithms which find some similar "center" of a graph?

# Answer
Another heuristic idea: Find a long shortest path, and pick the vertex halfway along it.

Pick a vertex and run BFS from it. For some small $k$, take the $k$ furthest vertices from the original vertex that the BFS determines, and repeat the process on each of them, keeping the $k$ overall furthest vertices each time. Repeat a few times.

If the graph is a tree, this is in fact guaranteed to find the longest path with $k=1$ after the second iteration! For a general graph, I don't know of any such guarantee -- but you are likely to find a reasonably long shortest path.

Once you have a sufficiently long path, pick the vertex halfway along it. (This is uniquely determined if the path has an odd number of vertices; if it has an even number, you could choose arbitrarily, or run BFS again from the middle two vertices, and pick whichever scores higher.)
> 2 votes

# Answer
After a bit of reading through literature I've come upon "closeness centrality" which is the reciprocal of what I'm calculating (mean distance, which they call "farness" in the article). But I still haven't found any algorithms for finding the "closeness center" (node with maximum closeness centrality) that is faster than $O(N^2)$.

As a heuristic, I have found a very effective $O(N)$ approximation algorithm though:

* For some $k$, randomly choose $k$ start nodes from the graph.
* Run BFS simultaneously around all $k$ start nodes. For each start node $s$, build up sets $N\_s(d)$ of all nodes distance $d$ or less from node $s$ (the $d$-neighborhood of $s$) iteratively starting at $d = 0$.
* For all nodes $n$, keep track of $C\_n(d) = \\#\\{s | n \in N\_s(d)\\}$ the "count" of how many neighborhoods $n$ is in.
* Iteratively increase $d$ until there exists some node $n$ such that $C\_n(d) \> k / 2$. In other words, until you find the smallest distance $d$ such that there exists a node $n$ which is within $d$ distance from a majority of the original points.

As $k \to N$, I think this will find the "median center" (or centers). In other words the nodes with minimum (median distance to all other nodes). This tends to be similar (if not identical) to the "mean center" and is definitely close enough to my intention.

There are generally many of these points at the last step and you can test them all to find which has the min (mean distance) / max closeness centrality. And likewise can run this simulation multiple times to get more candidates to test.

Still gladly looking for any other ideas anyone else has!
> 1 votes

---
Tags: graphs, graph-traversal, network-analysis, social-networks
---


# Question
Title: How Do You Design an Algorithm for This Graph
# Introduction

I'm not really understanding my algorithms class. One of our HW assignments is to design an efficient algorithm for this graph

### Questions

1. Give an efficient algorithm to find the fastest route for Alice to leave home, reach some gas station, then get to work.
2. On her way home, Alice wants to visit both a grocery store and a hardware store (in some order). Give an efficient algorithm to find the fastest route for Alice to leave work, visit both stores, and get home.

### Thoughts

I was thinking something along the lines of A\* search and make Gas Stations have a 0 heuristic, or something like create a list of the shortest paths and choose the shortest path with a gas station?

Honestly, I don't know how to implement this. How do I go about reasoning about this?

For example, how would I implement my second solution?

# Answer
> 2 votes
Both questions can be solved in time $O(m + n \log n)$, where $n$ and $m$ are the the number of vertices and edges of the input graph graph $G$.

For question $1$: Create a directed graph $G'$ consisting of two copies of $G$ (you can think of $G$ as directed by replacing each undirected edge $\\{u,v\\}$ with the two directed edges $(u,v)$ and $(v,u)$).

For each vertex $v$ that represents a gas station in $G$, let $v\_1$ and $v\_2$ be the vertices corresponding to $v$ in the first and second copy of $G$ in $G'$, respectively, and add the directed edge $(v\_1, v\_2)$ to $G'$. The weight of $(v\_1, v\_2)$ is $0$. Finally, find the shortest path $P$ from home (in the first copy of $G$) to work (in the second copy of $G$). The length of $P$ is exactly of the shortest route from home to work that passes through a(t least one) gas station.

Question $2$ can be solved similarly. First, guess the order in which the stores are visited (there are only $2$ possible choices). Then, create a graph $G'$ with 3 copies of $G$. Intuitively, going from the first copy to the second copy means visiting the first store, and going from the second copy to third copy means visiting the second store.

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


# Question
Title: Data structure for finding nearest squares from current square
For my project I can have 0-500 moving squares. The largest possible square width is at most 3 times longer than the smallest possible square width. The squares can move up to 3 of their own body's width per second. About 1 square is added and about 1 square is deleted every second.

What I'm trying to implement now is a neural network to drive the speed and direction of the squares. Each square will have their own neural network which will take the x and y position of the 5 nearest squares to it. To find the nearest squares, I will be taking the euclidean distance from the center of their squares bodies.

My problem is that calculating the distance of each square to every single other square - to find its 5 nearest other squares - is going to make my program run at a snail's pace.

So what is a good data structure I could use to reduce the number of checks I'm performing?

Also I heard that kd-trees were good at finding the nearest neighbor. However, because the squares are going to be moving a lot I'm not sure if it'd actually be the best data structure to use.

# Answer
> 2 votes
Since you only measure distances from the centers of the squares, you can restate your problem as follows: Maintain a dynamic collection $X$ of $n$ points in Euclidean space so that you can quickly find the $k$ nearest neighbors in $X \setminus \\{p\\}$ of a query point $p \in X$.

Using the data structure described here you can maintain such a collection in $O(\log^3 n)$ expected amortized time per insertion and $O(\log^6 n)$ expected amortized time per deletion, after a preproessing requiring $O(n \log^2 n)$ expected time.

The data structure supports nearest neighbor queries (given a point $q$, report the point in $X$ that is closest to $q$) in $O(\log^2 n)$ worst-case time. Then, you can report the $k$ nearest neighbors of $p \in X$ in $O(k \log^6 n)$ expected amortized time as follows:

* Delete $p$ from $X$ in $O(\log^6 n)$ expected amortized time.
* Repeat $k$ times:
    + Query the data structure for the nearest neighbor $p' \in X$ of $p$ in $O(\log^2 n)$ worst-case time.
    + Report $p'$ as one of the $k$ nearest neighbors of $p$.
    + Delete $p'$ from $X$ in $O(\log^6 n)$ expected amortized time.
* Reinsert all deleted points in $X$ in $O(k \log^3 n)$ expected amortized time.

# Answer
> 0 votes
You may be able to borrow from methods for n-body simulation, such as the Barnes-Hut method. It sounds like it relies on an octree (or quadtree). You can update a quadtree or octree efficiently and use it to speed up nearest-neighbor queries, and it is simple to implement.

It suffices to store the centers of the squares in the data structure. Their width is irrelevant for purposes of finding the 5 nearest squares.

You can find an overview of algorithms for nearest neighbor search here: https://en.wikipedia.org/wiki/Nearest\_neighbor\_search

---
Tags: data-structures
---


title: Decryption of RSA

text:
# Question
Title: Decryption of RSA
How can we decrypt an RSA message if we only have the public key?

For example, Message: `21556870,12228498` Public Key: `(e = 15852553, n = 44331583)`

I know that these formulas exist:

```
gcd(e, φ(n)) = 1
ed mod φ(n) = 1

```

so my idea was that i could put the value of e in the first formula, then derive d that is a part of the private key. However, I don't think it's mathematically possible to find `φ(n)` here. So, how else can I decrypt an RSA message with only the public key?

# Answer
"How can we decrypt an RSA message if we only have the public key?"

Well, *we have to find the private key from the public key*. This should be too hard to do in practical situations in general, since RSA algorithms are time-tested field-tested security algorithms, and people are using it carefully with long-enough bits in general.

However, the exercise assigned to you is designed for you to practice RSA algorithm. The numbers used are not large enough to prevent you from obtaining the private key given the public key. *You should be able to do all the computations by simple programming using your favorite programming language and computer.*

Try harder before looking at the answer below.

---

Public Key: `(e = 15852553, n = 44331583)`

Let us factor `n`. Here is a simple Python program.

```
def factor(n):
    for i in range(2, n-1):
        if n % i == 0:
            print(str(n) + " = " + str(i) + " * " + str(n // i))
            break

```

Running `factor(44331583)`, we obtain that `44331583 = 5003 * 8861`.

So `φ(n) = (5003 - 1) * (8861 - 1) = 44317720`

---

Find the inverse of `e` modulo `φ(n)`. Here is a simple Python program.

```
def inverse(e, phi):
    """ display the inverse of e modulo phi """

    for i in range(1, phi):
        if i * e % phi == 1:
            print(str(e) + " * " + str(i) + " = 1 (mod " + str(phi) + ")")
            break

```

Running `inverse(15852553, 44317720)`, we obtain that `15852553 * 1951097 = 1 (mod 44317720)`. That is, the inverse of `e` modulo `φ(n)` is `d=1951097`.

So, the corresponding private key is `(d = 1951097, n = 44331583)`.

---

Compute `m**d (mod n)` to decrypt an RSA message (a.k.a. ciphertext) `m`. Here is the popular modular-exponentiation function.

```
def modulo_pow(base, exponent, modulus):
    """ display the result of base ** exponent % modulus """

    exp = exponent
    result = 1
    b = base % modulus

    while exp > 0:
        if exp % 2 == 1:
            result = (result * b) % modulus
        exp = exp >> 1
        b = (b * b) % modulus

    print(str(base) + " ** " + str(exponent)
          + " = " + str(result) + " (mod " + str(modulus) + ")")

```

Running `modulo_pow(21556870, 1951097, 44331583)` and `modulo_pow(71, 15852553, 44331583)`, we obtained, respectively,

```
21556870 ** 1951097 = 71 (mod 44331583)
12228498 ** 1951097 = 111 (mod 44331583)

```

Hence, the decrypted message is `71,111`. Can you find what it means?
> 1 votes

# Answer
You'll need to factor the base of the RSA public key to be able to decrypt. That is the whole point: cracking RSA is equivalent to factoring, and factoring is (presumed to be) very hard.
> 3 votes

---
Tags: computer-networks, cryptography, security, mathematical-analysis, encryption
---


# Question
Title: What does Bellantoni-Cook say about Cook-Reckov?
In implicit complexity theory they construct natural programming languages that are complete for various complexity classes.

An example, while there are many others, is Bellantoni-Cook where they show that FP can be characterized by such a language (called system B).

What I'm wondering is what do successes such as Bellantoni-Cook in implicit complexity say about Cook-Reckov?

Cook-Reckov: There exists a polynomially bounded propositional proof system iff NP = coNP.

Are these languages not proof systems? Where the outputs are the propositional tautologies (or something like this).

Why does the successful construction of these languages not prove, by the Cook-Reckov theorem, that NP = coNP?

PS you could ask the same thing of descriptive complexity... why don't constructions like FO(LFP) (first-order logic with a least fixed point operator added to it, on ordered structures), by, again, the Cook-Reckov theorem, prove P=coNP? As P can be described as the problems expressible in FO(LFP) and it is a propositional proof system--how is this not the same thing as FO(LFP) is a polynomially bounded propositional proof system?

Thank you!

# Answer
A polynomially bounded proof system is a function $M$ computable by an FP machine with the following properties:

* For any $x$, the output $M(x)$ is a propositional tautology.
* There exists a polynomial $p(n)$ such that for any propositional tautology $y$ there exists $x$ of size at most $p(|y|)$ such that $M(x) = y$.

Now suppose that you found a sophisticated way to describe all functions in FP, call it System R. This lets you come up with the following equivalent definition.

> A polynomially bounded proof system is a function $M$ expressible in System R with the following properties:
>
> * For any $x$, the output $M(x)$ is a propositional tautology.
> * There exists a polynomial $p(n)$ such that for any propositional tautology $y$ there exists $x$ of size at most $p(|y|)$ such that $M(x) = y$.

As you can see, nothing has really been gained. We only changed "computable by an FP machine" with "expressible in System R".
> 2 votes

---
Tags: complexity-theory, polynomial-time, descriptive-complexity
---


# Question
Title: Algorithm to output all instances of stable matching
So the Gale-Shapley algorithm is just one way to output one stable matching instance. Is there any algorithm that can allow us to output all stable matching solutions ? Thanks

# Answer
> 2 votes
Dan Gusfield gave such an algorithm in his paper Three Fast Algorithms for Four Problems in Stable Marriage. The algorithm uses $O(n^2)$ space, and takes time $O(n^2 + nS)$, where $S$ is the number of stable matchings.

---
Tags: algorithms
---


# Question
Title: CFG for $w\#x$ where $|w| = |x|$ and $w \neq x^R$
How do I construct a context-free grammar for the following language?

$$L = \\{w\\#x \mid w, x \in \\{0, 1\\}^\*, |w| = |x|, w \neq x^R \\} $$

# Answer
A word belongs to your language if it has one of the following forms: $$ \Sigma^i 0 \Sigma^j \\# \Sigma^j 1 \Sigma^i \\ \Sigma^i 1 \Sigma^j \\# \Sigma^j 0 \Sigma^i $$ Given this, you should be able to construct a context-free grammar for $L$.
> 1 votes

---
Tags: context-free
---


title: Type inference with overloading

text:
# Question
Title: Type inference with overloading
I am working on a type system supporting overloading. I have a rough idea of how type inference is usually implemented in such a scenario, but I am wondering how - after type inference is completed - the correct implementation of an overloaded operator can be chosen. Or, in other words, how the inferred type can be passed back down the syntax tree to the operator.

For a small example, consider the expression `(x + y) + 1` where `x :: N | S, y :: a, + :: (N -> N -> N) | (S -> S -> S), 1 :: N`. `::` stands for *type of*, and `a | b` stands for type `a` *or* type `b`.

The way, I assume, type inference would now work, is to traverse the syntax tree, and for each node return a type constraint:

```
(x + y) + 1 => ((N & (N[a=N] | S[a=S])), (N & N) -> N) | ((S & (N[a=N] | S[a=S])), (S & N) -> S) => N[a=N]
  1         => N
  +         => (N -> N -> N) | (S -> S -> S)
  x + y     => ((N & (N | S)), (N & a) -> N) | ((S & (N | S)), (S & a) -> S) => N[a=N] | S[a=S]
    x       => N | S
    y       => a
    +       => (N -> N -> N) | (S -> S -> S)

```

`a & b` in this example stands for *unifying* the types `a` and `b`, `[a=T, b=U]` is a set of equality constraints for type variables.

As expected the return type of the given expression is inferred as `N[a=N]`, that is `N` where the type variable `a` is expected to be `N`.

Therefore, of the two provided implementations for the `+` operator (`N -> N -> N`, `S -> S -> S`), `N -> N -> N` should be used. In the given example, the resulting type is inferred, but not the type of the overloaded operator. My question is if there is a common pattern that is used to inform the `+` node in the syntax tree of the used implementation.

# Answer
> 1 votes
You could organize type inference as follows.

Suppose your input syntax has type `Input`. Define output syntax `Output` to be like `Input` but with explicit type annotations on all variables. The type inference would have type

```
infer : Input -> List (Output * Type)

```

That is, given some input `e`, it returns a list of possible answers. Each answer is a pair `(e', t)` where `e'` is `e` with variables annotated by types, and `t` is the inferred type of `e`.

You can view this as all happenning in the nondeterminism monad. Whenever you need to infer the type of a variable `x`, you look up its possible types `S | T | ...` and branch on each one of them. This way you do not have to "pass back" any information to sub-expressions. Instead, each sub-expressions already comes annotated, in all possible ways.

---
Tags: programming-languages, type-theory, type-inference
---


# Question
Title: Algorithms: Determining Asymptotic Notation from a given execution time
I'm studying for an Algorithms and Data Structure test. There is a type of question that is usually always asked by my professor but I don't know how to answer/solve it.

**Question 1:** An Algorithm with an worst-case execution time of 3n\*(log n), being n the number of elements in the input, is:

* a) An algorithm with an execution time of type Θ(n log n).
* b) An algorithm with an execution time of type O(n log n).
* c) An algorithm with an execution time of type O(n^2).
* d) None of the above.

**Question 2:** An Algorithm with an execution time of 2^100 + (1/3)\*n^2 + 100n, being n the number of elements in the input, is:

* a) An algorithm with an execution time of type Θ(n^2).
* b) An algorithm with an execution time of type O(2^n).
* c) An algorithm with an execution time of type Θ(2^n).
* d) None of the above.

I want to know how I can think about these problems in order to solve them. Any help is welcome (even by just giving the solution to these two questions). Thanks.

# Answer
> 1 votes
Assuming that $f(n)$ and $g(n)$ are asymptotically positive (as it is usually the case) you can use the following sufficient condition to determine the asymptotic relation of $f(n)$ and $g(n)$.

If $\lim\_{n \to \infty} \frac{f(n)}{g(n)}$ exists and is $c \in \mathbb{R\_0^+} \cup \\{+\infty\\}$, then:

* If $c\< +\infty$ then $f(n) = O(g(n))$ (and $g(n) = \Omega(f(n))$). In particular:

+ If $0 \< c \< +\infty$ then $f(n) = \Theta(g(n))$ (and $g(n) = \Theta(f(n))$).
    + If $c=0$ then $f(n) = o(g(n))$ (and $g(n) = \omega(f(n))$).
* If $c \> 0$ then $f(n) = \Omega(n))$ (and $g(n) = O(f(n))$). In particular:

+ If $0 \< c \< +\infty$ then $f(n) = \Theta(g(n))$ (and $g(n) = \Theta(f(n))$).
    + If $c = +\infty$ then $f(n) = \omega(g(n))$ (and $g(n) = o(f(n))$).

Moreover, in computing the limit, you can replace $f(n)$ with a function $h(n)$ such that $h(n) \sim f(n)$ (see, e.g., this page on Wikipedia). The same holds for $g(n)$. For polynomials this amounts to taking the monomial of highest degree. Moreover, since scaling $c$ by a (positive) constant does not change the asymptotic relation between $f(n)$ and $g(n)$, you can also drop any multiplicative constant (which will always be positive since $f(n)$ and $g(n)$ are asymptotically positive).

For example, instead of comparing $f(n) = 3n^2 + 2n +50$ with $g(n) = 5n^5 + 4n^3 - 2^{10}$, you can compare $x^2$ with $x^5$ instead. This immediately shows that $c$ exists and is $0$, therefore $f(n) = O(g(n))$ and, in particular, $f(n) = o(g(n))$.

While the above rules will probably work for the vast majority of the functions you will encounter, they can't always be used. Consider, for example, $f(n) = 2 + \sin(n)$ and $g(n) = 1$. Here $f(n) = \Theta(g(n))$ but $\lim\_{n \to \infty} \frac{f(n)}{g(n)}$ does not exist.

# Answer
> 0 votes
Check the definitions. You'll see that as it is talking about the worst case of the algorithm, $\Theta(\cdot)$ is probably out. Think Bubblesort, with worst time complexity $\Theta(n^2)$ but best case $\Theta(n)$. In any case, if $T(n) = \Theta(n \log n)$, then certainly $T(n) = O(n \log n)$ (remember $T(n) = \Theta(g(n)$ if both $T(n) = \Omega(g(n))$ and $T(n) = O(g(n))$). Next, $3 n \log n = \Theta(n \log n)$, but we must consider it is only worst case $3 n \log n$, so you have $O(n \log n)$. But $3 n \log n = O(n^2)$ too.

The last two ones are right, the first one might be.

---
Tags: algorithms, asymptotics, runtime-analysis, big-o-notation
---


# Question
Title: Is the powerset of a regular set also a regular set?
If so, where can I find a proof of it? If not, is there a counterexample?

By powerset of a regular language I mean the set of all subsets of a regular language.

Thank you, Marcus.

# Answer
No. In computer science, a *language* is normally defined to be a subset of $\\{0,1\\}^\*$. If $L$ is a language, then the powerset $2^L$ is not a subset of $\\{0,1\\}^\*$, so it is not a language.

(See e.g., https://en.wikipedia.org/wiki/Formal\_language#Definition.)

If $L$ is finite, then the powerset $2^L$ is finite, so as Emil Jeřábek points out, there is a way you can encode it so its encoding is a regular language, since all finite languages are regular.

If $L$ is infinite, then as Yuval Filmus points out, the powerset $2^L$ is not countable, so there is no way to encode it as a language. Thus, when $L$ is an infinite regular language, then the answer to your question is "no, not even if you're allowed to choose a reasonable encoding".
> 4 votes

---
Tags: regular-languages, sets
---


# Question
Title: Two regular languages over the same alphabet, regular or not regular?
> TRUE or FALSE:
>
> Let $L\_1, L\_2$ be any two regular languages over the same alphabet $\Sigma$, then the language $L=\\{w\in\Sigma^\* \mid w\in L\_1 \text{ or } w\notin L\_2\\}$ is regular.

So we have to determine whether $L\_1 \cup \overline{L\_2}$ is regular or not.

Proof:

First attempt:

First we have to prove that a complement of a regular language is also regular: the complement of a language $L$ with respect to an alphabet $\Sigma$ such that $\Sigma^\*$ is $\Sigma^\*-L$. Since $\Sigma^\*$ is surely regular the complement of a regular language is always regular.

Let's prove that the union of two regular languages is also regular: For example, let $\Sigma = \\{a,b\\}$. Assume $L\_1 = \\{a\\}$ and $L\_2 = \\{b\\}$ so they are regular language. Then the union: $\\{a\\} \cup \\{b\\} = \\{ab\\}$ is also regular. Since $\\{a\\}$ is regular , $\\{a\\}^\*$ is also a regular language.

After these two proofs we can say that the statement above is True.

Second attempt:

A regular language is regular iff there is a finite state machine recognizing it. Let $L\_1 = \\{S\_1,\Sigma,\delta\_1,s\_0^1, F\_1\\}$ and $L\_2 = \\{S\_2,\Sigma,\delta\_2,s\_0^2, F\_2\\}$ be two automata. First we have to take the complement of $L\_2$. The complement of $L\_2$ is the set of states without the set of final states: $\overline{L\_2} = \\{S\_2,\Sigma,\delta\_2,s\_0^2, S\_2-F\_2\\}$. Then we can create the product automaton of the two languages which is: $L = \\{S\_1 \times S\_2,\Sigma,\delta\_1 \times \delta\_2,s\_0^1 \times s\_0^2, F\_1\ \times (S\_2-F\_2)\\}$. The final states of the language $L = L\_1 \cup \overline{L\_2}$ is the set of states where $F\_1$ or $S\_2 - F\_2$ is final. Since there exists a finite state machine that recognizes the language $L$, we can say that $L$ is a regular language.

Can somebody please correct me? Maybe I made a mistake.

# Answer
> 8 votes
I see several problems.

In your first part you say that, given a regular language $L$, $\overline{L}$ is regular since $\Sigma^\*- L$ is also regular. This is true, but it is implicitly using the fact that regular languages are closed under difference. It is not clear if you're allowed to use that fact as a black box (since it is a more general statement than the one you're trying to prove).

In your second part you are not giving a proof. You are just showing that $L\_1 \cup L\_2$ is regular when $\Sigma=\\{a,b\\}$, $L\_1 = \\{a\\}$ and $L\_2 = \\{ b \\}$. What if $\Sigma \neq \\{a,b\\}$? What if $L\_1 \neq \\{a \\}$? Your proof needs to work for all possible choices of $\Sigma, L\_1,$ and $L\_2$.

Moreover, $L\_1 \cup L\_2 \neq \\{ab\\}$ contrarily to what you claim.

Finally, you say that since $\\{a\\}$ is regular then so is $\\{a\\}^\*$. This is true but it is unclear why you need this.

# Answer
> 6 votes
> Since $\Sigma^∗$ is surely regular **the complement of a regular language is always regular**.

This is exactly what you want to prove! You can't use it in its own proof! If you can use the fact that $$\text{If $L$ and $L'$ are regular, then}~L\setminus L'~\text{is regular}.$$ then, for $L = \Sigma^\*$ and $L' = L\_2$, you get that $\overline{L\_2} = \Sigma^\* \setminus L\_2$ is regular, since $\Sigma^\*$ and $L\_2$ are regular.

Also, your proof about the union of two regular languages being also regular is not correct, because you need to show that this holds for *any* two regular languages and not just for the specific ones that you chose ($\\{a\\}$ and $\\{b\\}$).

In general,

* If you are given a regular language, you can assume that there is a DFA or NFA or regular expression that describes it.
* To prove that a language is regular, you need to show that there is a corresponding NFA, DFA or regular expression.

Here, you are given two regular languages $L\_1$ and $L\_2$. Assuming you have an NFA for each, can you construct an NFA for $L\_1 \cup \overline{L\_2}$?

# Answer
> 2 votes
You can make your life here quite easy by considering that a language is regular if and only if there is a finite state machine recognizing it.

Let's say you have n regular languages $L\_1$, $L\_2$, ..., $L\_n$. For each there is a finite state machine recognising it: Processing a string, each FSM goes through a sequence of states, and the string is part of the language if and only if we end up in an accepting state.

Now create a state machine where each state is a vector of n states of the n original state machines. We move from one state to the next by changing the i-th component of the state according to the i-th original state machine.

When the complete string is processed, we have a vector of n values which are either "accepted" or "not accepted". There are $2^n$ possible outcomes. There are $2^{2^n}$ functions mapping each possible outcome to either "accepted" or "not accepted".

If we apply each of these functions, we get a new finite state machine defining a new language, one for each possible set operation on the n languages.

For two languages L and M, there are 16 possible set operations. Six are trivial, giving all strings, the empty set, L, M, the complement of L or the complement of M. The others are L or the complement of L intersected with M or the complement of M (four languages), the union of L or the complement of L with M or the complement of M (four languages), the strings that are either in L or M but not both, and the strings that are either both elements of L and M, or elements of neither. All these 16 languages are regular.

Out of three regular languages, we can produces 256 regular languages. Out of four regular languages, we can produce 65,536 regular languages, and out of five regular languages, about 4 billion.

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


title: Minimize the sum of gaps

text:
# Question
Title: Minimize the sum of gaps
I have a set of $n$ objects $\\{1,2,\ldots,n\\}$ where object $i$ has weight $w(i)$ and we have a capacity $W$. I would like to pick a subset $S=\\{a\_1,\ldots,a\_m\\}\subseteq \\{1,2,\ldots,n\\}$ of the objects in order to minimize $$\sum\_{j=0}^m(a\_{j+1}-a\_{j}-1),$$ (assuming that $a\_0=0$ and $a\_{m+1}=n+1$) while respecting the capacity, i.e., $$\sum\_{j=1}^mw(a\_j)\leq W.$$

The objective is like the sum of gaps between chosen objects.

Is this problem NP-hard or can we find a polynomial time algorithm?

# Answer
For every $k$ and $\sigma$, let $A(k,\sigma)$ be the minimum of $\sum\_{j=1}^m w(a\_j)$ over all subsets $a\_1,\ldots,a\_m$ of $\\{1,\ldots,k\\}$ containing $k$ such that $\sum\_{j=0}^m (a\_{j+1} - a\_j - 1) = \sigma$; note that there are $O(n)$ choices for each of $k$ and $\sigma$. You can compute $A(k,\sigma)$ for all $k,\sigma$ using dynamic programming, and use it to solve your problem in polytime.
> 1 votes

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