# Question
Title: Incomplete definition of function- first order logic
> Let $\Sigma=\\{c,f^1,R\_1^2,...,R\_k^2\\}$ where $c$ is constant, $f$ is one argument function, and $R\_i$ are binary relations. Let $\Sigma\_2=\\{c',g^2,R\_1'^1,...,R\_k'^1\\}$ where $c'$ is constant, $g$ is two argument function, and $R\_i'$ are unary relations.
> Show an algorithm that given a formula $\varphi$ above $\Sigma$, returns a new formula $\varphi'$ above $\Sigma\_2$ such that:
> $\varphi$ is satisfiable above $\Sigma$$\iff$ $\varphi'$ is satisfiable above $\Sigma\_2$

Well I have a partial solution, goes as follow:
Consider the next recursive definition:
$c\rightarrow c'$
$f(t)\rightarrow g(t',t')$
$R\_i(t\_1,t\_2)\rightarrow R\_i'(g(t\_1',t\_2'))$

The problem with the definition is that it not complete:
The function $g$ should have two roles:

1. defining the values of $f(t)$
2. Map elements of the form $(t\_1,t\_2)$ in a way that will allow $R\_1'^1,...,R\_k'^1$ to be consistent with $R\_1^2,...,R\_k^2$

I haven't found a way to define $g$, such that second requirement will be met.

Would appreciate help, hints will be helpful as well.

# Answer
> 1 votes
First of all in your above 3 "recursive definitions" linking $\Sigma$ with $\Sigma\_2$, clearly the function $g$ in $\Sigma\_2$ doesn't have any role in defining the values of $f(t)$ in $\Sigma$, the values of $f(t)$ should be already defined in language $\Sigma$.

To check your 3 "recursive definitions" more deeply, it seems here the map from constant $c$ to constant $c'$ is critical since it completely determines your replacement of the argument $t'$ in function $g$. For example, in $\Sigma$ we only have one dimensional information such as coordinate $x$ of the real line. When we try to translate to $\Sigma\_2$ where we may have two dimensional information such as 2-tuple coordinate $(x, y)$ in a plane, then the map from $c$ to $c'$ can be expressed as $m(c)=c \rightarrow (c, 0)$ via an ordered pair in the simplest case. So you may need to further clarify the map from $c$ to $c'$ in order to really find correct arguments for your function $g$ during the translation...

---
Tags: logic, satisfiability, first-order-logic, propositional-logic, logical-validity
---


title: Binary Search return value

text:
# Question
Title: Binary Search return value
Google has the article Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken. Which primarily discusses the overflow on the mid calculation. However, what I found interesting was the return value for when `key` is not found. Initially, I thought the negative indicates the value was not found and `low` indicates where it should be inserted into the array. However, what is the `+1` in `return -(low+1);` doing?

```
public static int binarySearch(int[] a, int key) {
    int low = 0;
    int high = a.length - 1;

    while (low <= high) {
        int mid = (low + high) / 2;
        int midVal = a[mid];

        if (midVal < key)
            low = mid + 1
        else if (midVal > key)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found.
}

```

# Answer
There are multiple ways to handle the case when the key(the searched value) is not found by a binary search. Or any search on elements accessible by indices.

What you see is the Java approach, the approach that has been written by the foremost writer of Java built-in Libraries (also the author of the article in the question) and, henceforth, used by millions of Java developers around the world for about 20 years.

Here is Java official documentation for the method java.util.Arrays#binarysearch(int\[\] a, int key).

> Returns: index of the search key, if it is contained in the array; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the `key` would be inserted into the array: the index of the first element greater than the key, or `a.length` if all elements in the array are less than the specified key. Note that **this guarantees that the return value will be \>= 0 if and only if the key is found**.

That is, the method guarantees that the return value will not be a valid index if and only if the key is not found. This guarantee makes sure the return value is not usable when the key is not found, preventing wrong usage or failing faster.

If `key` is not found and `low` is 0 right before the method returns, the method should not return `-low`, since it is `0`, which is a valid index. So, it returns `-(low + 1)`, which is `-1`, an invalid index.

By the way, to find the insertion point when the key is not found, i.e., when `returned_value < 0`, we can use `-returned_value - 1`.
> 3 votes

---
Tags: binary-search
---


# Question
Title: understanding complexity of a function with defined function
this is the algorithm :

```
F() = {
  count = 0
  n = 1000
  For i = 1 to n Do
   If n Modulo i = 0 Then
     count = count + 1
   end if
  end for
  if count = 2 then
   return prime
  else return prime
}

```

So what i know is complexity of a loop is n and other than loop is some constant

so what i get is O(n)

but my teacher said its O(1) because the n is already defined

is my teacher correct ?

Thank you in advance :) Sorry for my bad english

# Answer
Your teacher is correct. We measure the complexity with respect to *the input*'s size.

Here, you don't have any input to the function, and $n$ is just a constant defined within the function.

Thus, the loop runs only a constant number of times, which is $O(1)$.
> 0 votes

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


title: SAT and Polytime Reductions

text:
# Question
Title: SAT and Polytime Reductions
If an algorithm for $SAT$ runs in $O(n^{\log n})$ time, and if $L$ belongs to $\mathsf{NP}$, is there an algorithm for $L$ that runs in $O(n^{\log n})$ time?

# Answer
As $\mathrm{SAT}$ is $\mathrm{NP}$-complete, we know that there is a polytime reduction from our language $L$ to $\mathrm{SAT}$. However, this reduction can involve a polynomial blowup of the input size. This means that an input $w$ to $L$ could be mapped to a formula $\phi\_w$ such that $|\phi\_w| \approx |w|^k$ for some constant $k$.

Running our hypothetical algorithm for $\mathrm{SAT}$ on $\phi\_w$ takes time $O(|\phi\_w|^{\log |\phi\_w|}) = O((|w|^k)^{\log |w|^k}) = O(|w|^{k^2 \log |w|})$ time. But $O(n^{k^2 \log n}) \neq O(n^{\log n})$.

Thus, there is no immediate reason why the assumption would yield an $O(n^{\log n})$-algorithm for $L$.
> 1 votes

# Answer
Since any input x for L can be reduced to SAT in O(|x|^c) time, the created SAT instance will have size at most n=O(|x|^c). So the n^(lg n)-time algorithm for SAT will be an |x|^O(lg |x|)-time algorithm for L.
> -1 votes

---
Tags: complexity-theory, computability
---


# Question
Title: Complexity of sorting $k$-sorted array using QuickSort and HeapSort
Given a $k$-sorted array where each element in the array is $k$ positions from its correct position, we want to sort such array using quick sort. Generally speaking, I understand that running time is very unlikely to be guaranteed for best case and thus in most cases you would end up with $O(n^2)$ running time though quicksort runs in $O(n\log{n})$ in best case/average case scenario.

---

# QuickSort

**Best case**: I am looking to proof why we get $O(n^2)$ even in average case. If we rewrite the quick sort recurrence as,

$$T(n) = T(k) + T(n-k) + O(n) \tag{1}\label{1}$$

We can see that the depth of the recurrence tree is $\frac nk$, thus $T(n) = O(n^2)$.

**Worst Case**: It's $T(n)=T(1)+T(n-1)$ is clear.

**Problem 1**: how do you interpret please \ref{1} given k-sorted array definition?

**Problem 2**: from \ref{1} I see that the recurrence of quicksort is written by taking each element that is $k$ positions from its correct place in the sorted array as a pivot if I am were right please? So, we split it into two subproblems of size $k$ and $n-k$. However, the resulting elements in the subproblems might have less than $k$ distance from their positions due to divisions of problem into sub problems, so I am just a little bit confused as whether the property that each element is $k$ position from its correct place is invariant or not given we are splitting the array into sub problems.

**Problem 3**: why please the depth of recurrence tree after we do quick sort is $\frac nk$? My interpretation to this does not apply here as I was thinking that the depth of the node represents how far it's from correct position, but still not sure about it.

---

# HeapSort

Let us discuss HeapSort approach and why it's more efficient that QuickSort.

if we use heap sort instead of quicksort and we then take $k+1$ elements and add them in a heap that is sorted (min heap), so once we have $k+1$ elements and we are about to visit $k+2$th element, we pop the min element from heap and add it to the array that will hold sorted elements. So, we can imagine the array as being literally divided into sublists. To formalize this, let $A\[i\] \< A\[i+2k+1\]$.

**Problem 4**: I would like to discuss please $A\[i\] \< A\[i+2k+1\]$. **Approach 1**: It's obvious that each element in the array can be less than at most $n-(k)$ elements or from all elements on the right and all elements on the left $n-(k)$ , so in total we need $n-2k$? Is this is how $A\[i\] \< A\[i+2k+1\]$ was deduced above please? **Approach 2**: The solution I got says that, "because the element at slot $i$ can at most move forwards during sorting to slot $i+k$ and the element at slot $i+2k+1$ can at most move backwards during sorting to slot $i+k+1$." I am having troubles understanding this proposed solution anyway? So please either discuss it or discuss my approach (approach 1).

# Answer
For quick sort, you end up with quadratic runtime only if you use the most stupid method of picking a pivot- by taking the first or last element. Picking the middle element, or the median of first, last and middle element, it will run nicely fast because for all except 2k elements we have just comparisons, and nothing will be moved. Still n log n, but with a small constant factor.

There is a slightly complicated variant of heap sort that works well for mostly sorted arrays, someone might know the name.

PS. In one instance where an array is almost sorted, bubble sort was recommended and worked very well. The situation was a large number of 2d lines, and their intersection with some y-value was needed in sorted order. After a small change in y, the intersections change slightly, so k was very small (less than log n usually) and bubble sort ran in k x n steps. Solution due to Paul Hsieh I think, hope he’s alive and well.
> 0 votes

# Answer
The analysis questioned in `Problem 3` assumes(?) an implementation closer to *ACM Algorithm 64* than to what Sedgewick is getting at (as does "Problem 1"): recursion on *all* partitions, not "iteration on the biggest one".
> 1 votes

---
Tags: algorithms, time-complexity, sorting, quicksort, heap-sort
---


# Question
Title: Using the chromatic number to compute an optimal coloring
Suppose we are given a graph $G$ of order $n$ and a black box that can efficiently (polynomial time) compute the chromatic number $\chi(G)$. I am curious to hear how would one go about in order to construct a proper coloring of $G$, more precisely

> Find an efficient algorithm (polynomial time) to construct a proper coloring of $G$ provided that you can efficiently compute the chromatic number.

Does anybody see a simple algorithm for this purpose?

# Answer
As long as possible, add edges to $G$ which do not increase the chromatic number. You should get a complete multipartite graph which corresponds to an optimal coloring.
> 3 votes

---
Tags: graphs, polynomial-time, colorings
---


# Question
Title: Not understanding step in Karger Algorithm: How to simplify a long product
I'm reading a book on Randomized Algorithms by Raghawan and Motwani and I don't understand the algebra/calculus of a step in the analysis of Karger's algorithm(Randomized min-cut).

They have the following: $$Pr\[\cap\_{i=1}^{n-2} E\_{i}\] \geq \Pi\_{i=1}^{n-2}(1-\frac{2}{n-i+1}) = \frac{2}{n(n-1)}$$

This part in particular: $\Pi\_{i=1}^{n-2}(1-\frac{2}{n-i+1}) = \frac{2}{n(n-1)}$ is hard for me to see when i try to write it out. I know that for example

$$ 1 + 2 + 3 + 4 + \ldots + n = \frac{n(n+1)}{2}$$ which can be figured out by adding two series together. But I actually don't know a lot about long products like $\Pi\_{i=1}^{n-2}(1-\frac{2}{n-i+1})$ is there any good place to start if I had to find $\frac{2}{n(n-1)}$ ?

# Answer
$$ \begin{align\*} \prod\_{i=1}^{n-2} \left( 1-\frac{2}{n-i+1} \right) &= \prod\_{i=1}^{n-2} \frac{n-i-1}{n-i+1} \\ &= \frac{\color{red}{n-2}}{n} \cdot \frac{\color{blue}{n-3}}{n-1} \cdot\frac{n-4}{\color{red}{n-2}} \cdot \frac{n-5}{\color{blue}{n-3}} \cdots \frac{\color{purple}{4}}{6} \cdot \frac{\color{green}{3}}{5} \cdot \frac{2}{\color{purple}{4}} \cdot \frac{1}{\color{green}{3}}\\ & = \frac{2}{n(n-1)}. \end{align\*} $$

Where we used the fact that the product is telescopic. Notice how, after simplifying, the only surviving terms from the numerators are $2$ and $1$ while the only surviving terms from the denominators are $n$ and $n-1$.
> 3 votes

---
Tags: randomized-algorithms, algebra
---


# Question
Title: Shortest path with forced intermediate nodes
I have a directed graph with roughly 2000 nodes, and roughly 4000 edges. I have created an application so the people that use it can easily see the path drawn on a map, if they e.g. want to find the shortest path between two nodes. And this works as intended. However, this shortests path is based on the weights of each edge. The "problem", as I have been told, is, that sometimes they (who have done this manually for years) know that this route needs to go through a certain node. There are certain reasons for this, but nonetheless, I need to be able to force a path to go through certain nodes.

My first idea was to just run Dijkstra's from `start node` to `intermediate node` and then from `intermediate node` to `end node`, and combine the two. And in some cases, this seems to work. But as you can imagine, sometimes the second path might go through some of the edges/nodes that was used in the first path, which doesn't work.

I could probably make some modified node disjoint path work if there was only ONE intermediate node. But I am afraid that it will get quite complicated if I were to use more than that.

So I am wondering if there might be a better option to still get the shortest path, but with forced intermediate nodes in between ?

It should also be noted that computation time is not really an issue here. Nothing needs to be almost instant, and in general it seems that a graph of this magnitude is quite "small" in terms of computation time.

# Answer
The problem you are trying to solve is $\mathsf{NP}$-Hard. In fact, it is hard to even decide whether any such path exists.\*

Indeed, let $G=(V,E)$ be your graph and $s,t \in V$ be the start and end nodes, respectively. When the set of intermediate nodes is $V \setminus \\{s,t\\}$ the problem is equivalent to finding an Hamiltonian path from $s$ to $t$ in $G$, which is a well-known $\mathsf{NP}$-Hard problem.

* Note that even if you know for sure that the sought path exists in $G$, this still doesn't simplify the problem since you can transform an instance of Hamiltonian-path into an instance of your problem by adding all missing edges and assigning a high cost to them. Then, deciding whether there is an Hamiltoniam path in the original graph corresponds to deciding whether there exists a cheap path from $s$ to $t$ that traverses all vertices in $V \setminus \\{s,t\\}$ in the modified graph.
> 2 votes

---
Tags: graphs, dijkstras-algorithm
---


# Question
Title: Reasoning given with explanation of Halting Problem
I have read (and re-read) the informal proof of The Halting Problem. Can we not make the same argument using only the Program, without the Input {e.g. H(P) rather than H(P, I)}? I am confused by the step where we pass the Program as the Input as well. This seems to be the key since all explanations mention this step without fail.

In my mind whatever argument is being made can also be made by considering only the Program, without considering the Input part. There is obviously something that I am overlooking.

---

**Addendum:** I am referring to the following informal proof in Discrete Math by Rosen, 8e:

> Assume there is a solution to the halting problem, a procedure called H(P, I). The procedure H(P, I) takes two inputs, one a program P and the other I, an input to the program P. H(P,I) generates the string “halt” as output if H determines that P stops when given I as input. Otherwise, H(P, I) generates the string “loops forever” as output. We will now derive a contradiction.
>
> When a procedure is coded, it is expressed as a string of characters; this string can be interpreted as a sequence of bits. This means that a program itself can be used as data. Therefore, a program can be thought of as input to another program, or even itself. Hence, H can take a program P as both of its inputs, which are a program and input to this program. H should be able to determine whether P will halt when it is given a copy of itself as input.
>
> To show that no procedure H exists that solves the halting problem, we construct a simple procedure K(P), which works as follows, making use of the output H(P, P). If the output of H(P, P) is “loops forever,” which means that P loops forever when given a copy of itself as input, then K(P) halts. If the output of H(P, P) is “halt,” which means that P halts when given a copy of itself as input, then K(P) loops forever. That is, K(P) does the opposite of what the output of H(P, P) specifies. (See Figure 3.)
>
> *Now suppose we provide K as input to K*. We note that if the output of H(K, K) is “loops forever,” then by the definition of K, we see that K(K) halts. This means that by the definition of H, the output of H(K, K) is “halt,” which is a contradiction. Otherwise, if the output of H(K, K) is “halts,” then by the definition of K, we see that K(K) loops forever, which means that by the definition of H, the output of H(K, K) is “loops forever.” This is also a contradiction. Thus, H cannot always give the correct answers. Consequently, there is no procedure that solves the halting problem.

# Answer
Consider the "Total Halting" problem: Given the number of a program P, decide that it halts for *every* input. Assume we have a program TH for this. And say it either halts and says the truth, or it doesn't halt.

So what does TH(TH) do? If TH halts for every input, and gives the correct result when it halts, it will say "Yes". If TH doesn't halt for every input, then TH(TH) will either halt and say "No" or it will not halt.

But here is what is lacking: There is no obvious reason here that TH couldn't be built. I don't think it can be built, and I'm reasonably sure that it can be proven, but there is no simple contradiction here.

For a program that takes (program, input) as input, we can suggest that a program H(program, input) exists that decides correctly whether "program" halts on input "input" and cleverly constract a program and input where this fails. With only "program" as input, we have not enough material to produce a contradiction.
> 0 votes

---
Tags: algorithms, computability, undecidability
---


# Question
Title: Find the values for n0 and the constant factor c such that f(n) = n log n is Ω(n)
I was recently introduced to big O and big Omega, as well as big theta. I know that big O is the worse case scenario in terms of runtime, big Omega is the best case scenario, and big theta is in between. However, I'm still confused on how I would use it mathematically to prove that n log n = Ω(n). Also, I get that n0 is the lowest possible number for the equation to work, but where does the constant factor c come in? Any advice and help is greatly appreciated, thanks!

# Answer
> 0 votes
$\log(n) \ge 1$ for any $n\>2$. Hence, if we choose $n\_0=2$, then for any $n\>n\_0$ we have $n\log(n)\ge n\cdot 1 = n$. Thus, by the definition of $\Omega$, we have that $n\log(n) = \Omega(n)$.

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


# Question
Title: Find maximum element in sorted arrays in logarithmic time
Been stuck on this for a while, would really appreciate some help:

> Suppose you are given an array A\[1...n\] of sorted integers that has been circularly shifted k positions to the right. For example, \[35,42,5,15,27,29\] is a sorted array that has been circularly shifted k = 2 positions, while \[27,29,35,42,5,15\] has been shifted k = 4 positions. Give an algorithm for finding the maximum element in A that runs in O(log n) time.

The elements in A are distinct.

---

I understand that to achieve O(log n) time I'll probably have to search through the list by starting at the middle, and then going left or right, then splitting the list in half over and over, but I'm not sure how to attack it beyond that.

# Answer
If the elements need not be distinct, then you cannot have an $O(\log n)$ time algorithm.

Consider the sorted array $\[0,0, \dots, 1\]$ which has been cyclic shifted $k$ (unknown) times and you need to find where the $1$ appears. This needs $\Omega(n)$ time, as you need to examine at least $n-1$ elements.

However, if you assume the elements are distinct, then you can indeed give an $O(\log n)$ time algorithm.

Assume the array was sorted ascending. Once it is cyclic shifted, we will have that, in the rotated array (say $a\[1,2, \dots n\]$), that $a\[1\] \gt a\[n\]$. (It might help to draw a figure here, plotting $i$ on x-axis and $a\[i\]$ on the y-axis).

Now if you pick a $j$, you compare $a\[j\]$ with $a\[1\]$ and move right or left, depending on whether it is greater or lesser, like binary search.
> 10 votes

# Answer
A cyclic shift is just an offset transformation in the array. That is, if $k$ is known, you can define the virtual sorted array $A'$ by

$\qquad\displaystyle A'\[i\] = A\[(i+k) \bmod n\]$

You can use standard binary seach on $A'$, that is replace every array access to element $i$ in the search algorithm by an access to $(i+k) \bmod n$.

The same works for *any* (computable and) known permutation of an array.
> 2 votes

# Answer
Here is one way of finding the max:

Let left and right be the extreme elements of the array.

```
Start at the middle element whose index is e
If A[e] is smaller than the elements surrounding it
    return max(A[e-1], A[e+1])
Else
    If right > left
        Recursively search in right sub-array (A[e] included)
    Else
        Recursively search in left sub-array (A[e] included)

```
> 1 votes

# Answer
the image contain all the answer that how the complexity can be o(long).
> 0 votes

# Answer
I think we could do the follow first, choose the middle number which is 5 and then compere it with the lift term in your case it is 35. If the middle \< left then we can eliminate the right part of the array which is \[5,15,25,29\].

this is the idea but it needs to add some conditions to be more efficient.

Thanks @Baghdadi
> -2 votes

---
Tags: algorithms, search-algorithms, arrays
---


# Question
Title: What is the difference between an algorithm, a language and a problem?
It seems that on this site, people will often correct others for confusing "algorithms" and "problems." What are the difference between these? How do I know when I should be considering algorithms and considering problems? And how do these relate to the concept of a language in formal language theory?

# Answer
> 58 votes
For simplicity, I'll begin by only considering "decision" problems, which have a yes/no answer. Function problems work roughly the same way, except instead of yes/no, there is a specific output word associated with each input word.

**Language**: a language is simply a set of strings. If you have an alphabet, such as $\Sigma$, then $\Sigma^\*$ is the set of all words containing only the symbols in $\Sigma$. For example, $\\{0,1 \\}^\*$ is the set of all binary sequences of any length. An alphabet doesn't need to be binary, though. It can be unary, ternary, etc.

A language over an alphabet $\Sigma$ is any subset of $\Sigma^\*$.

**Problem**: A problem is some question about some input we'd like answered. Specifically, a decision problem is a question which asks, "Does our given input fulfill property $X$?

A language is the formal realization of a problem. When we want to reason theoretically about a decision problem, we often examine the corresponding language. For a decision problem $X$, the corresponding language is:

> $L = \\{w \mid w$ is the encoding of an input $y$ to problem $X$, and the answer to input $y$ for problem $X$ is "Yes" $ \\}$

Determining if the answer for an input to a decision problem is "yes" is equivalent to determining whether an encoding of that input over an alphabet is in the corresponding language.

**Algorithm**: An algorithm is a step-by-step way to solve a problem. Note that there an algorithm can be expressed in many ways and many languages, and that there are many different algorithms solving any given problem.

**Turing Machine**: A Turing Machine is the formal analogue of an algorithm. A Turing Machine over a given alphabet, for each word, either will or won't halt in an accepting state. Thus for each Turing Machine $M$, there is a corresponding language:

> $L(M) = \\{w \mid M$ halts in an accepting state on input $w\\}$.

(There's a subtle difference between Turing Machines that halt on all inputs and halt on yes inputs, which defines the difference between complexity classes $\mathsf{R}$ and $\mathsf{RE}$.)

The relationship between languages and Turing Machines is as follows

1. Every Turing Machine accepts exactly one language
2. There may be more than one Turing Machine that accept a given language
3. There may be no Turing Machine that accepts a given language.

We can say roughly the same thing about algorithms and problems: every algorithm solves a single problem, but there may be 0, or many, algorithms solving a given problem.

**Time Complexity**: One of the most common sources of confusion between algorithms and problems is in regards to complexity classes. The correct allocation can be summarized as follows:

* An algorithm *has* a time complexity
* A problem *belongs* to a complexity class

An algorithm can have a certain time complexity. We say an algorithm has a worst-case upper-bounded complexity $f(n)$ if the algorithm halts in at most $f(n)$ steps for any input of size $n$.

Problems don't have run-times, since a problem isn't tied to a specific algorithm which actually runs. Instead, we say that a problem belongs to a complexity class, if there exists *some* algorithm solving that problem with a given time complexity.

$\mathsf{P}, \mathsf{NP}, \mathsf{PSPACE}, \mathsf{EXPTIME}$ etc. are all complexity classes. This means they contain problems, not algorithms. An algorithm can never be in $\mathsf{P}$, but if there's a polynomial-time algorithm solving a given problem $X$, then $X$ can be classified in complexity class $\mathsf{P}$. There could also be a bunch of other algorithms runs in different time complexity will also be able to solve the problem with the same input size under different time complexity, i.e. exponential-time algorithms, but since there already exists a single polynomial-time algorithm accepting $X$, it is in $\mathsf{P}$.

# Answer
> 0 votes
Even more TLDR:

Problem: Given an input return an output related to the input in some way. Decision problems answer yes/no questions related to the input Optimization problems seek to minimize or maximize some property related to the input. Algorithm: a specific instance of solving a problem. Problems may have many algorithms that solve the problem Language: formalization of the problem (in decision format). That is, the set of all strings spelled from an alphabet for which the problem is true (in the case of a decision problem).

---
Tags: algorithms, complexity-theory, formal-languages, terminology, reference-question
---


# Question
Title: Edmonds-Karp bound doesn't seem to be tight
The proof that the Edmonds-Karp algorithm will require at most $O(|V||E|)$ uses the fact that when an augmenting path has critical edge $(u, v)$, $\delta\_f(u)$ strictly increases. Therefore, that particular edge can only be critical at most $|V|$ times and the total number of augmenting paths until the max flow is at most $|E| * O(|V|) = O(|V||E|)$.

But consider that vertex $u$ and all its outgoing edges. The sum of the times those outgoing edges are critical must be $O(|V|)$ by a similar reasoning. Couldn't we then take this fact and say the number of augmenting paths will be at most $|V| * O(|V|)$, by summing over the vertices (instead of summing over the edges like the textbook proof)? This would give $O(|V|^2)$ as the bound on the number of augmenting paths.

Put another way, consider the sum $\sum\_{v \in v} \delta\_f(v)$. This sum is at most $|V|^2$, but is strictly increased after every augmentation, so $O(|V|^2)$ augmentations will be required.

Is there any flaw in this reasoning? We know that $O(|V|^2|E|)$ is possible using Dinic's, but if Edmond's-Karp requires at most $O(|V|^2)$ augmentations we would get this same bound.

I tried searching for this and found this post, but I do not understand the response or comment discussion. Maybe someone can rephrase it?

# Answer
> 1 votes
Here are two papers giving examples that show that the analysis of the Edmonds–Karp algorithm is tight:

---
Tags: network-flow
---


# Question
Title: How is Gene sequence files i.e FASTA files so compressible?
Why are Gene squencing file i.e FASTA files so compressible. It was stated on a site that few compression algorithms are capable of compressing these files to Gigabytes (from Terabytes).
And is it possible to convert binary data to FASTA file for high compression.
Is there any difference between algorithms used in compression of FASTA files and normal binary files.

# Answer
> 2 votes
As the comments have rightly pointed out, you can't get around the pigeonhole principle. Given any compression algorithm, half of all possible files of a randomly chosen length cannot be compressed by even one bit.

(On the other hand, of course, no file needs to be *expanded* by more than one bit, because you can always store it verbatim.)

If you understand the nature of the data that is being represented in FASTA files, and how it is represented, you will be able to see why it should be very easy to compress them.

FASTA files are plain-text, designed for easy processing using text-based tools. So there is opportunity for some compression already there. Here is an example of the start of one:

```
>NC_045512.2 Severe acute respiratory syndrome coronavirus 2 isolate Wuhan-Hu-1, complete genome
ATTAAAGGTTTATACCTTCCCAGGTAACAAACCAACCAACTTTCGATCTCTTGTAGATCTGTTCTCTAAA
CGAACTTTAAAATCTGTGTGGCTGTCACTCGGCTGCATGCTTAGTGCACTCACGCAGTATAATTAATAAC
TAATTACTGTCGTTGACAGGACACGAGTAACTCGTCTATCTTCTGCAGGCTGCTTACGGTTTCGTCCGTG
TTGCAGCCGATCATCAGCACATCTAGGTTTCGTCCGGGTGTGACCGAAAGGTAAGATGGAGAGCCTTGTC
CCTGGTTTCAACGAGAAAACACACGTCCAACTCAGTTTGCCTGTTTTACAGGTTCGCGACGTGCTCGTAC
GTGGCTTTGGAGACTCCGTGGAGGAGGTCTTATCAGAGGCACGTCAACATCTTAAAGATGGCACTTGTGG
CTTAGTAGAAGTTGAAAAAGGCGTTTTGCCTCAACTTGAACAGCCCTATGTGTTCATCAAACGTTCGGAT
GCTCGAACTGCACCTCATGGTCATGTTATGGTTGAGCTGGTAGCAGAACTCGAAGGCATTCAGTACGGTC
GTAGTGGTGAGACACTTGGTGTCCTTGTCCCTCATGTGGGCGAAATACCAGTGGCTTACCGCAAGGTTCT

```

The first line is a header (denoted by the `>` character) which describes the sample that follows. In FASTA, this is free-form text, but in practice, they often follow a standard, starting with a machine-readable symbol (in this case, an accession number) and human-readable text following.

Following that header line is the data. FASTA files can contain a number of types of data, such as DNA, RNA, and protein sequences. It can be used to store anything from collections of raw reads out of a sequencing machine, to assembled genomes. There are also ways to encode methylation. But for this use case, we are talking about fully assembled genomes, so let's stick to that.

For reference genomes, there are exactly five possible characters that can occur: A, C, G, T, and N, with the first four representing the four nucleotides and N meaning unknown.

The line length in the data section is not semantically important, and so does not need to be preserved.

Now let's look at a more complex example of a eukaryote, which has multiple chromosomes. The FASTA data will typically look like this:

```
>NC_000001.11 Homo sapiens chromosome 1, GRCh38.p13 Primary Assembly
NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN
NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN
NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN
[many lines of N deleted]
NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNTAACCCTAAC
CCTAACCCTAACCCTAACCCTAACCCTAACCCTAACCCTAACCCTAACCCTAACCCTAACCCTAACCCTA
ACCCTAACCCTAACCCTAACCCTAACCCAACCCTAACCCTAACCCTAACCCTAACCCTAACCCTAACCCC
TAACCCTAACCCTAACCCTAACCCTAACCTAACCCTAACCCTAACCCTAACCCTAACCCTAACCCTAACC
CTAACCCTAACCCCTAACCCTAACCCTAAACCCTAAACCCTAACCCTAACCCTAACCCTAACCCTAACCC
[etc etc]
>NC_000002.12 Homo sapiens chromosome 2, GRCh38.p13 Primary Assembly
NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN
NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN
[more lines of just N deleted]
NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNCGTATCCCAC
ACACCACACCCACACACCACACCCACACACACCCACACCCACACCCACACACACCACACCCACACACCAC
ACCCACACCCACACACCACACCCACACCACACCCACACACCACACACCACACCCACACCCACACACACCA
CACCCACACACCACACCCACACACACCCTAACCCTAACCCCTAACCCCTAACCCTAACCCTACCCGAACC
CTAACCCTAACCCTAACCCCTAACCCTAACCCCTAACCCTAACCCTAACCGTAACCCTAACCCTTTACCC
TAACCCGAACCCCTAACCCCTAACCCCTAACCCTTAACCCTAACCCTTAACCCTGACCCTGACCCTGACC
[lots of lines deleted]
>NC_012920.1 Homo sapiens mitochondrion, complete genome
GATCACAGGTCTATCACCCTATTAACCACTCACGGGAGCTCTCCATGCATTTGGTATTTTCGTCTGGGGG
GTATGCACGCGATAGCATTGCGAGACGCTGGAGCCGGAGCACCCTATGTCGCAGTATCTGTCTTTGATTC
CTGCCTCATCCTATTATTTATCGCACCTACGTTCAATATTACAGGCGAACATACTTACTAAAGTGTGTTA
ATTAATTAATGCTTGTAGGACATAATAATAACAATTGAATGTCTGCACAGCCACTTTCCACACAGACATC
ATAACAAAAAATTTCCACCAAACCCCCCCTCCCCCGCTTCTGGCCACAGCACTTAAACACATCTCTGCCA
[more lines deleted; you get the idea]

```

Within one organism, the headers are extremely predictable. There is a record number, which is a closed vocabulary, followed by text which is also highly regular. This suggests separating the headers and the data payloads and compressing them as separate streams.

When `N`s occur, they overwhelmingly occur in long runs in specific places; in this case, at the start of the chromosomes (though not the mitochondrion; chloroplasts in plants would be similar). This is because chromosomes have a 3D shape, and some parts are more difficult to "access" than others, such as the centromere. As such, they are not only much harder to sequence, they also play essentially no known role in biology apart from geometric.

After the run of `N`s, we have a section that is highly repetitive, and therefore highly compressible. This is known as the telomere, and it plays a vital function: it is a kind of redundant code that signals that this is the end of a strand, rather than a break, so the cell's DNA repair mechanisms don't try to repair it.

It's not obvious from this sample, but A, C, G, and T do not occur with equal probability. In *homo sapiens*, the "GC content" (i.e. the proportion of nucleotides that are G or C) is between 38% and 48%, depending on the chromosome.

So what I hope you can see here is that there is a *lot* of things that can be exploited in compressing the data payload.

Finally, and perhaps most crucially, as the comments rightly point out, when you are storing a library of human genomes (and the same reasoning applies to human genetic disease samples, or human cancer samples), samples from different organisms tend to have a lot in common, so it makes sense to either store differences from a single reference, or combine as many references as possible into a single model (e.g. a k-mer set or de Bruijn graph; note that it may be efficient to use a different model for each type of chromosome) and use that for compression.

These models can be stored using extremely compact representations. See, for example:

Given such a model, you can use this to compress sequences using a method like PPM.

So what I hope you can see from all this is that there is a lot of information that we can exploit to compress DNA reference sequences. FASTA files are designed for tool convenience, not compact storage, so even standard text compression techniques work reasonably well. But you can get even more compression using domain-specific information, including knowledge of biology.

Final thing: In the interest of full disclosure, I'm a co-author of one of the papers cited above.

---
Tags: binary
---


# Question
Title: Dijkstra's Algorithm Same Node Added Multiple Times to Priority Queue
In the this discussion of Dijkstra's Algorithm appear the following comments:

```
# Nodes can get added to the priority queue multiple times. We only
# process a vertex the first time we remove it from the priority queue.

```

I'm curious as to under which circumstances a node would be added to the priority queue multiple times. My understanding was that once a node had been processed, it's min-distance was determined and we could forget about it.

Here's the full code for reference:

```
import heapq

def calculate_distances(graph, starting_vertex):
    distances = {vertex: float('infinity') for vertex in graph}
    distances[starting_vertex] = 0

    pq = [(0, starting_vertex)]
    while len(pq) > 0:
        current_distance, current_vertex = heapq.heappop(pq)

        # Nodes can get added to the priority queue multiple times. We only
        # process a vertex the first time we remove it from the priority queue.
        if current_distance > distances[current_vertex]:
            continue

        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight

            # Only consider this new path if it's better than any path we've
            # already found.
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    return distances

example_graph = {
    'U': {'V': 2, 'W': 5, 'X': 1},
    'V': {'U': 2, 'X': 2, 'W': 3},
    'W': {'V': 3, 'U': 5, 'X': 3, 'Y': 1, 'Z': 5},
    'X': {'U': 1, 'V': 2, 'W': 3, 'Y': 1},
    'Y': {'X': 1, 'W': 1, 'Z': 1},
    'Z': {'W': 5, 'Y': 1},
}
print(calculate_distances(example_graph, 'X'))
# => {'U': 1, 'W': 2, 'V': 2, 'Y': 1, 'X': 0, 'Z': 2}

```

# Answer
Consider what will happen for the following graph.

```
 counterexample_graph = {
    'U': {'V': 6, 'W': 7},
    'V': {'X': 10},
    'W': {'X': 1},
 }

```

Suppose `U` is the starting vertex. You can check that vertex `X` is added to the priority queue

1. by route `U -> V -> X`, yielding a distance of 16,
2. then by route `U -> W -> X`, yielding a shorter distance of 8.
> 2 votes

---
Tags: priority-queues, dijkstras-algorithm
---


# Question
Title: Proof the recurrence relation of order statistics using induction
I read order statistics from the book The Design and Analysis of Computer Algorithms", by Aho, Hopcroft, Ullman, Addison-Wesley

As per the algorithm the recurrence relation given

T(n)\<= cn for n\<=49 .....1

T(n)\<= T(n/5) + T(3n/4) + cn for n\>=50 .....2

How can I prove it by induction T(n)\<= 20cn?

I have two more questions

For the 1st equation why they define n\<=49 and for the 2nd equation n\>=50

Thank you.

# Answer
The first equation is the *base case* for the recurrence. The second equation represents the *recurrence formula*, on everything that **isn't** a base case.

Now, you can prove by induction this statemen, simply by using complete induction as follows:

The base case is obviously correct. For the induction hypothesis, assume correctness for any $k\<n$.

Now, for $T(n)$, we can use the recurrence formula to get $$T(n)=T\left(\frac{n}{5}\right) + T\left(\frac{3n}{4}\right) + cn$$ And notice that $\frac{n}{5},\frac{3n}{4}\<n$, and hence we can use the induction hypothesis on them. Doing so, will yield: $$T(n)\le \frac{20cn}{5}+\frac{20c\cdot 3n}{4}+cn=4cn+15cn+cn=20cn$$ And hence we also proved that $T(n)\le 20cn$ and with that we completed the induction proof.
> 1 votes

---
Tags: algorithms, asymptotics, sorting
---


title: Where does tag directory is stored

text:
# Question
Title: Where does tag directory is stored
I am studying direct mapping in cache. I understood the concepts like dividing into blocks and lines , tag directory etc. When solving numerical problems of finding main memory size or tag directory size I have no problem. What I understood is that, in cache we have a tag associated with each cache line ( neglecting valid/invalid and other bits ) and size of each line is equal to block size.

So size of cache should be - Tag Directory Size + Size of each line * No of lines .

But when the guy( here ) is not adding tag directory size to cache size. Why is it so? Or I misunderstood the concept?

# Answer
> 2 votes
The term "cache size" generally refers to its data capacity, not to the sum of the data capacity plus all the other stuff as well. Similarly, the "state" bits, masks, LRU indicators, ECC bits, and so on, wouldn't be included in the "cache size", because they don't add capacity. It's similar to how a 1L bottle really takes up more physical space than 1L, the 1L refers to how much fluid the bottle can contain, not to the "total size". Of course the other things are stored somewhere too, and you could add up all the sizes, but that's not what is typically meant by "cache size".

While the tags and data could be put into one big SRAM array (and abstract diagrams usually show it that way), often they're stored separately.

---
Tags: computer-architecture, cpu-cache
---


# Question
Title: Do I have the right definition of VC dimension?
I am having some trouble understanding the notion of the VC dimension. The definition I have is the following:

> The VC dimension of a set of hypothesis functions $H$ is the cardinality of the largest set which $H$ can shatter. We say that $H$ shatters some set $S \subseteq \mathcal{X}$ if we can realise any labelings on $S$ using functions from $H$.

To me, this means that for any (countable) set of labels $L \subseteq \mathbb{Z}$, there is some $h \in H$ that provides a surjection $h: S \mapsto T$, where $T \subseteq \mathcal{X}$ with $|T| = |L| \leq |S|$. (There is then a trivial bijection from $T$ to $L$.)

**Is this the correct interpretation?**

The reason I ask is because the above interpretation leads me to think that the singleton set $H = \\{h\\}$ has $VC(H) = 1$, since it always sends a single point to a single point, so we can get any labelling we like on this single point by a trivial bijection.

That is, suppose we wanted to label the point $x \in \mathbb{R}$ as $l$, then $h: y \in \mathbb{R} \mapsto 0$ will do since we can just change the name of 0 to $l$. Note that this chosen $h$ does not shatter a two-set from $\mathbb{R}$, since we can only label the points in one distinct way.

However, I have read that the VC of a singleton is 0. I don't understand this.

(I see hypothesis functions $g: \mathcal{X} \to \\{1, \dots, n\\}$ as belonging to an equivalence class of functions that sends $\mathcal{X}$ to any set of size $n$. Please correct me if this is the wrong intuition.)

# Answer
> 4 votes
A family of hypothesis functions on domain $\cal X$ is a subset of $\\{0,1\\}^{\cal X}$. A family $H$ *shatters* a set $S \subseteq \cal X$ if for every subset $T \subseteq S$ there exists a function $h \in H$ such that $h(s) = 1\_{s \in T}$ for all $s \in S$, that is, $h(s) = 1$ if $s \in T$ and $h(s) = 0$ if $s \in S \setminus T$.

A singleton family $H$ cannot shatter any non-empty set $S$. Indeed, suppose that $H = \\{h\\}$ shatters $S \neq \emptyset$, and take any $s \in S$. Taking $T = \emptyset$, we see that $h(s) = 0$, whereas taking $T = S$, we see that $h(s) = 1$.

# Answer
> 0 votes
I'm not sure when you mean that the VC dimension of a singleton is 0? I have always thought it was 1. How I think about it is that given some $H$ of classifiers, I will pick any one point in the domain space $\mathcal{X} = \mathbb{R}$. Then an adversary will have to label it whichever way he wants. And if one of my classifiers in $H$ is able to classify correctly the points no matter how the adversary labels the points, then we say that $H$ shatters 1 point and should have at least VC dimension of 1.

So let the classifier set be $H = \\{ h\_i \\}$ where $h\_i(x) = 1$ if $x=i$ and 0 otherwise, for all $i \in \mathbb{R}$. So say for instance, I pick the point at $x=6$. The adversary comes in to label it with a 1, then I can provide the adversary with a classifier that labels this point with 1 (i.e. $h\_6$). If he labels the point with 0 instead, then I instead give him another classifier that is not $h\_6$ (that will label it 0 for sure).

So now, we check if $H$ can shatter two points. Apparently if we picked two points $x\_i,x\_j \in \mathbb{R}$, then the adversary will just label both with 1s and thus I am unable to find a classifier in $H$ that labels both with 1s. I try to give him $h\_i \in H$ but that labels $x\_i$ with 1 and $x\_j$ with 0. I could try giving him $h\_j \in H$ but $x\_i$ labelled with 0 and $x\_j$ with 1 (i.e. none of the classifiers in $H$ can give me a (1,1) labelling due to the nature of the singleton property).

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


title: Boolean formula for graph 3COL

text:
# Question
Title: Boolean formula for graph 3COL
For a given undirected graph $G=(V,E)$ I'm trying to construct a boolean polynomially computable formula $\varphi$ with the following property: $\varphi$ is satisfiable $\iff$ vertices of $G$ can be colored in $3$ colors with the following condition: For any edge $(u, v)\in E$, if $u$ and $v$ have different colors, then there exists $w\in V$ such that $(u, w)\in E$, $(v, w)\in E$, and $w$ has the third color (different from both $u$ and $v$). Here it is ok that two vertices of the same color may be connected by an edge.

# Answer
Here is one possible formula: $\texttt{true}$. Indeed, every graph admits a coloring that satisfies your requirements: simply color all vertices with the same color.
> 2 votes

---
Tags: graphs, satisfiability, boolean-algebra, colorings
---


# Question
Title: PAC Learnability of Infinite Hypothesis Classes
Is it true that for a finite or a countably infinite hypothesis class $\mathcal{H}$, then it is going to be PAC-learnable (and vice-versa)? And what about if we change the cardinality of the hypothesis space to be an uncountably infinite? Does that mean it will not be PAC learnable?

Please correct me if I'm wrong, thank you so much.

# Answer
Every finite hypothesis class $\mathcal{H}$ is PAC-learnable. Indeed, $VCdim(\mathcal{H})\le |\mathcal{H}|\<\infty$ (one can even create a more strict bound, but this is irrelevant for now). Hence, $\mathcal{H}$ is PAC-learnable.

Infinite classes however, can either be PAC-learnable or not. Being a countable, or an uncountable class does not matter here. For example, the class of all rectangles centered at the origin of $\mathbb{R}^2$ is PAC-learnable (has VCdim $2$ if I remember correctly), while it is an uncountable class.

Another example, of a *countable* class being **not** PAC-learnable, is the following:

$$\mathcal{H}:=\\{f:\mathbb{N}\rightarrow \\{0,1\\}\mid \text{the number of $1$'s in $f$ is finite}\\}$$

Which I will leave for you to verify that it is countably infinite, still has an infinite VCdim: Any finite $C\subset \mathbb{N}$ can be shattered, since we can "extend" every $f\in C\rightarrow \\{0,1\\}$ into a function $f\_{\mathbb{N}}:\mathbb{N}\rightarrow \\{0,1\\}$ in the following way:

$$f\_\mathbb{N}(n)=\begin{cases}f(n)&n\in C\\0&n\notin C\end{cases}$$

And indeed when we restrict $f\_{\mathbb{N}}$ into $C$, we get $f$. But $f\_{\mathbb{N}}\in \mathcal{H}$, and thus we showed that every finite $C\subset \mathbb{N}$ is shattered by $\mathcal{H}$ \- which means that $VCdim(\mathcal{H})=\infty$.

---

To summarize, we do know that being finite means that we are PAC-learnable, but when we are infinite - countably, or uncountably - we cannot be sure.

Additionally, this means that if you know that $\mathcal{H}$ is PAC-learnable, you cannot conclude anything about its size - it could be finite, countably infinite, or even uncountably infinite.
> 1 votes

---
Tags: machine-learning
---


title: Why is SAT based on the CNF?

text:
# Question
Title: Why is SAT based on the CNF?
I have been reading up on Boolean logic and, specifically, the Boolean satisfiability problem. I have seen several people mention that the expression must be converted to conjunctive normal form (CNF) before it can be solved. Why is this the case?

I understand that propositional formulae would be quite "chaotic" if not in a standard form, but why specifically CNF? Or, more specifically, has CNF been proven to be the best form to solve in? Or, has a better form merely not been found? It is possible there is a better form left undiscovered?

# Answer
We like conjunctive normal form because all circuits can be transformed into conjunctive normal from in linear time via the Tseitin Transformation. It's a clean, normalized data structure for solver implementation. CNF conversion without Tseitin variables may lead to exponential expansion.

That's the standard answer, but, as you see, there are nuances. Firstly, does the Tseitin transform introduce unnecessary complexity into the solving process? Secondly, why does conjunctive normal form not dualize to disjunctive normal form if the two are related only by negation? Thirdly, are we discarding important information from this one-way conversion of circuit to conjunctive normal form?

If the worst-case complexity of the solver is exponential as conjectured by $P \neq NP$, then one might anticipate the Tseitin transformation to drastically reduce solver efficiency.

Consider a formula $F$ defined by a circuit with $n$ inputs and $m$ internal gates. The circuit's boolean outcome is determined uniquely from assignments to the $n$ inputs, but, after the conversion, the CNF instance contains $n + m$ variables. The space of possible decision branches has been transformed from $2^n$ to $2^{n+m}$.

An astute person would recognize that not all $2^{n+m}$ decision branches are interesting for the solver. For any assignment of the original set of $n$ variables, the additional $m$ Tseitin variables are uniquely determined. In practice, a boolean satisfiability solver handles the added complexity of Tseitin variables by trivial unit propagation, a linear operation to the instance's matrix complexity. So, at least from a practical perspective, applying conjunctive normal form transformations does not change the runtime complexity of satisfiability procedures. You can even apply the Tseitin transform in multiple iterations - beginning with a formula, converting to conjunctive normal form, taking that to be a new formula, converting to conjunctive normal from again, etc. - and the impact on runtime complexity is negligible. Conflict-driven clause learning procedures are very good at zeroing-in on the problems fundamental constraints as opposed to definitional complexity.

Secondly, the relation of CNF and DNF normal forms arise from quantification. If $F$ is some formula and $T$ is some other formula not containing $x$ (Tseitin subformula), consider the instance that binds $x$ to the result of $T$:

$$(\exists \dots)\ \exists x\text{ st. } F \land (x \leftrightarrow T)$$

Assume that all the variables other than $x$ are given assignments, then consider cases for $x$. If $x$ is assigned to be inconsistent with $T$, then the conjunction fails and the entire instance is unsatisfiable. Otherwise, the right side of the conjunction is always satisfied and $x$ agrees with $T$. For the instance to be true, $x$ must be consistent with $T$.

You can define a dual transform over DNF and universal variables like so.

$$(\forall \dots)\ \forall x\text{ st. } F \lor !(x \leftrightarrow T)$$

Similar logic applies for universal quantification: if $x$ is inconsistent with $T$, then the right hand side dominates and the formula is trivially satisfiable. Otherwise, $x$ is bound to $T$ over $F$. Again, for the instance to be (universally) true, $x$ must be consistent with $T$ within $F$.

As far as Tseitin variables are concerned, existential quantification is inextricably bound to conjunction and universal quantification likewise to disjunction. Since SAT solvers only use existential quantification, such a construction is only possible to do in CNF.

QBF solvers use both universal and existential quantification, so the distinction between normal forms for them is less rigid. Any QBF circuit can be transformed to CNF, DNF, or a mixed combination of the two, depending on the quantifications you choose for the Tseitin variables. In QBF solving, there is an alternative standard problem format, called QCIR, that maintains the original formulaic structure. See: Non-CNF QBF Solving with QCIR

Last but not least, is there extra information relevant to the instance that isn't sufficiently captured by CNF? The answer to this is probably yes. If we consider resolution as a standard proof procedure for unsatisfiable SAT outcomes, then there exist counterexamples - namely the pigeonhole problem - where the size of the proof scales exponentially. Tseitin introduced a new system called "extended resolution" that nullified the exponential proof argument on the pigeonhole problem.

The basic idea behind extended resolution is to add extra constraints to the CNF, $x \leftrightarrow a \lor b$. These constraints are effectively just new Tseitin variables, except they eliminate exponential blowup in the resolution proofs instead of CNF conversion of the original circuit. It is unknown whether extended resolution admits polynomial-size proofs of unsatisfiability in general. That would show $\text{NP} = \text{co-NP}$. I mention it because the extra constraints added by extended resolution could be considered to be a stronger form of CNF.

Edit: I should also add, on the last point, that resolution proofs in SAT are inextricably bound to CNF in the unsatisfiable case. Each branch of a resolution proof is a CNF clause, or subset thereof, of the original problem instance. DRAT, the proof standard of real SAT solvers, also operates closely on the CNF form. In the satisfiable case, you can interpret the set of variable assignments as being a singular DNF clause. That is to say, these clausal normal forms are relevant not just to circuit specification, but also to the verifiable justifications for the positive and negative solver outcomes.
> 1 votes

# Answer
Conjunctive normal form first appears, in this context, in Davis and Putnam's *A computing procedure for quantification theory*, in which they describe a primitive form of the DPLL algorithm (which appears in a follow-up work of Davis, Logemann, and Loveland, and is the basis of all modern SAT solvers). They explain that one key property of CNF is that *any* formula can be efficiently converted to an equi-satisfiable CNF, which does not appear to be the case for DNFs, for example; so assuming that the formula is in CNF is "without loss of generality". The DPLL algorithm could in principle work on more general CSPs (conjunctions of arbitrary constraints), though I'm not sure that the important modern technique of *clause learning* generalizes to this setting.

Cook's *The complexity of theorem-proving procedures* proves the NP-completeness of SAT and 3SAT, which indicates that satisfiable of CNFs, and even 3CNFs, is a "hardest" problem, and a good candidate for a problem not solvable in polynomial time. As shown in Karp's *Reducibility among combinatorial problems*, and in more modern work on fine-grained complexity, it is also a good starting point for NP-hardness reductions.

Is CNF the "best" representation? This depends on what problem you're trying to solve. If you're trying to solve linear equations, then representing the problem as a set of linear equations is far superior. SMT solvers, heavily used in verification, also use a richer representation. Sometimes an integer program is the best way to formulate a problem. Nevertheless, the ubiquity of SAT solvers shows that in practice, CNF is often a highly useful normal form from a practical point of view.
> 6 votes

# Answer
It's because this is close to how real-world problems tend to be expressed.

SAT has a lot of practical applications, from controlling power grids to integrated circuit layout. In pretty much every case, the problem is that you have a bunch of complex constraints that all need to be satisfied.

However you express each constraint, they ultimately get joined together with a logical "and". That's what "they all need to be satisfied" means.

For comparison, consider DNF. A sat problem expressed in DNF is, when you think about it, actually the *answer* to a SAT problem. Each conjunct is an assignment of variables joined together with logical "or", meaning that any one of those assignments solves the problem.

Many SAT solver front-ends will convert more complex constraints to CNF, but ultimately, all of the constraints have to be conjoined together.
> 4 votes

---
Tags: satisfiability, boolean-algebra, propositional-logic
---


# Question
Title: The Turing Machine in the proof of Time Hierarchy Theorem
In the proof of the Time Hierarchy Theorem, Arora and Barak writes:

Consider the following Turing Machine $D$: “On input $x$, run for $|x|^{1.4}$ steps the Universal TM $U$ of Theorem 1.6 to simulate the execution of $M\_x$ on $x$. If $M\_x$ outputs an answer in this time, namely, $M\_x(x)\in \\{0,1\\}$ then output the opposite answer (i.e., output $1−M\_x(x)$). Else output $0$.” Here $M\_x$ is the machine represented by the string $x$.

What if we give the encoding of $D$ as input to $D$? Then $D$ will accept exactly when $D$ will reject. So such a $D$ cannot even exist. Am I missing something?

# Answer
> 1 votes
There will be no contradiction, since $D$ doesn't run in time $n^{1.4}$. In fact, what the proof of the time hierarchy theorem shows is that no *equivalent* Turing machine can run in time $n^{1.4}$, precisely because this will result in a contradiction. In other words, the language computed by $D$ lies outside of $\mathrm{DTIME}(n^{1.4})$. On the other hand, $D$ can be computed in time $O(n^{1.4} \log n)$. This shows that $$\mathrm{DTIME}(n^{1.4}) \subsetneq \mathrm{DTIME}(O(n^{1.4} \log n)).$$

(Usually $\mathrm{DTIME}(f(n))$ is defined as the class of problems which can be solved in time $O(f(n))$ rather than $f(n)$, the latter being the intended interpretation above. In that case the separation is between $\mathrm{DTIME}(f(n))$ and $\mathrm{DTIME}(n^{1.4} \log n)$ for any $f(n) = o(n^{1.4})$.)

---
Tags: complexity-theory, formal-languages, turing-machines, time-complexity, computability
---


title: Proof of Calculating VC-Dimensions

text:
# Question
Title: Proof of Calculating VC-Dimensions
I still have some doubts for finding the VC-dimension. Suppose $\mathcal{H}$ has VC-dimension $n$. This is the process of how I think about it: (1) Show that there is a set of $n$ points that can be shattered by $\mathcal{H}$; and (2) No set of $(n+1)$ points is shattered by $\mathcal{H}$. For (2), I just gotta show that for any set of $(n+1)$ points in the $\mathcal{X}$ space I pick, then there would be at least one configuration of labellings by an adversary where none of my classifiers in $\mathcal{H}$ can correctly classify them. For (1), please correct me if I'm wrong somewhere:

1. I choose any set of $n$ points I want in the space.
2. An adversary labels those $n$ points with labels $\mathcal{Y} = \\{ 0,1 \\}$ it no matter which way he wants.
3. I pick a classifier from $\mathcal{H}$ that correctly labels those points based on the labellings provided by my adversary.
4. If I can find one such classifier from $\mathcal{H}$, then $\mathcal{H}$ can shatter $n$ points and has at least VC-dim of $n$. The next step is to show that it cannot be done with $(n+1)$ points.

So I guess my confusion is in Step 1 here. Do I get to pick any set of points I choose, OR should it be any set of points in the space? The former implies an existence where as long as I can find one (so i.e. I will have to find the best set of points that will work in my favor); while the latter implies universality where I my choice is less flexible.

Here's an example of what I mean. So say we have some hypothesis class $\mathcal{H}$ where $h\_t(x) \in \mathcal{H}$. We say that $h\_t(x) = 1$ if $x \leq t$ and $x$ lies within a *positive even* unit-lengthed interval (i.e. $\[2,3)$, $\[10,11)$, $\[100,101)$ are examples of such intervals) and $h\_t(x) = 0$ otherwise. Note there that the threshold $t$ is a positive integer and that our domain $\mathcal{X}$ are the real numbers. So say if I want to find its VC-dim, I check first if it can shatter one point. If Step 1 in the above is existential, then I can say that I'll always pick any point that lies within this positive even unit-lengthed interval (because those points can get a chance to be labelled 1 or 0 by the adversary and we can label those accordingly based on the threshold $t$ that we set). All other intervals outside positive even unit-lengthed interval cannot be labelled 1 unfortunately so it doesn't make sense to pick any points within those intervals. However, if we say that Step 1 is a universality, then clearly $\mathcal{H}$ fails to shatter a single point because all points outside the positive even unit-lengthed interval cannot be labelled with 1 by the classifiers whatsoever.

So that's where I'm having doubts with finding the VC-dimension. But in the example, had it been an existence for Step 1, it can shatter one point but not two (just cause I can pick any two points that lie within the positive even unit-lengthed interval and if my adversary labels them with the first point in the left with a 1 and the second point in the right with a 0, then there is no classifier with a threshold $t$ that would be able to classify this correctly). So VC-dim is 1. But if it was a universality for Step 1, then VC-dim is 0.

Any thoughts on this? Thank you!

# Answer
> 1 votes
The VC-dimension of a hypothesis class $\mathcal{H}$ is the maximal size of a set shattered by $\mathcal{H}$, if such a maximal size exists, and $\infty$ otherwise. Therefore to prove that the VC-dimension of $\mathcal{H}$ is $d \< \infty$, you need to show that $\mathcal{H}$ shatters some set of size $d$, but no set of size $d+1$.

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


title: Is there a book with 100 reductions?

text:
# Question
Title: Is there a book with 100 reductions?
In a lecture I'm taking about complexity theory a professor said, there are infinite many NP-complete problems.

#### Question:

I was wondering if there exists something like a database or a book with some known reductions (or with maybe more than only the NP-complete ones) and the proofs for them? I know there is a very nice database for Rings, but I couldn't find something similar for reductions.

# Answer
The classical reference on NP-completeness is Garey and Johnson's Computers and Intractability, which contains a compendium of over 300 NP-complete problems, with links to papers proving their NP-hardness. The only downside is that the book is quite old, dating from 1979.
> 3 votes

---
Tags: reductions, reference-request, books, polynomial-time-reductions
---


# Question
Title: Is the transformer SLiM compatible with ALBERT?
My question is about the article Sub-Linear Memory: How to Make Performers SLiM.

It is written in the article "our algorithm is compatible with distillation (Sanh et al., 2020)".

Now I would like to know if SLiM is compatible with parameter sharing...

Is SLiM compatible with ALBERT and with ELBERT?

P.S. I am asking this question because the flow of the input through the encoder is different for BERT (and for DistilBERT too, because DistilBERT uses different loss for compreessing BERT...), ALBERT and ELBERT, look the image below taken from ELBERT:

# Answer
> 2 votes
I'm one of the authors of the SLiM-Performer paper. Yes, SLiM Performer is compatible with ALBERT-style weight sharing across layers, we mention that in Section 3.1 of the arXiv manuscript. In this case, the vector of parameters $\theta$ only stores parameters for one layer, which are retrieved by $F^{(r)}$ and $G^{(r)}$ functionals (using paper's notation).

It's also easy to see that SLiM Performer is compatible with the mentioned ELBERT model. For that, simply redefine the loss $\mathcal{L}^{(n)}$ as a "cascading" loss from ELBERT.

---
Tags: algorithm-analysis
---


# Question
Title: algorithm to check the existence of $b-1$ in $(n)_b$?
Given an integer number $n$ (in base 10) and a base $b$, determine whether the representation of $n$ in base $b$, $(n)\_b$ has a coefficient with value of $b-1$.

```
Examples
- n=21914, b=6
(21914)6 = 245242 => we have b-1=5 in the representation of (n)b
- n=50673, b=9
(50673)9 = 76453 => we don't have b-1=8 in the representation of (n)b

```

Is it possible to find a necessary and sufficient condition for existence of $b-1$ in $(n)\_b$? Is there a fast algorithmic way to find the answer?

## My try

If $b-1$ is in the coefficients of $(n)\_b$ then there should be two integers $p$ and $r$ such that:

$(b-1)b^p + r = n$

we can convert this to Diophantine equation for $r$ and $q=b^p$:

$(b-1) q + r = n$

we can solve Diophantine equation and see if $q=b^p$ has an integer solution for $p$. But I am not sure if this is a sufficient condition for the original problem!?

# Answer
The fastest way is likely going to be to compute the base-$b$ representation of $n$, and then scan over it to see whether it contains the desired digit. That is a linear-time algorithm.

Solving a Diophantine equation is far harder.
> 1 votes

---
Tags: algorithms, number-theory, base-conversion, diophantine-equation
---


# Question
Title: How the out-of-sample problem is solved in the article "One Loss for All Deep Hashing with a Single Cosine Similarity based Learning Objective"?
My question is about the article One Loss for All Deep Hashing with a Single Cosine Similarity based Learning Objective.

I would like to know how to solve the out-of-sample problem: given a new code how to find its corresponding orthogonal target?

Tell me the time complexity how many ms the algorithm demands for solving the out-of-sample problem.

# Answer
thanks for your interests in our work. I am one of the author for this work.

During training mode, our model learns to output orthogonal codes for every class (highly discriminative binary codes), very similar to discriminative face recognition model (e.g., CosFace). Hence for out-of-sample, we just compute the hash codes of any given input.

For out-of-sample problem, there will be two case:

1. The data is within trained class: The algorithm will retrieve the images with nearest hash codes. In our algorithm, the trained model is used to extract representative hash code for the query image. This will take not more than 10ms on decent GPU. Then, we compute the hamming distance with all other hash codes in the database to find nearest match (which has shortest distance). This will take not more than 5ms on decent CPU using `faiss` library with `IndexBinaryFlat`, at 100k scale database. Further, for larger scale data (e.g. 1B scale), Approximate Nearest Neighbour search would be useful (see `IndexBinaryIVF` in `faiss` library).
2. The data is out of trained class: As other supervised method, the algorithm is suboptimal on non-trained class. The time complexity is similar to previous case.

Hope this answer your questions.
> 1 votes

---
Tags: hashing
---


# Question
Title: Proof that any algorithm who builds a spanning tree using Cut and Cycle properties is an MST
The Kleinberg and Tardos Algorithm makes the following claim without proof:

> Any algorithm that builds a spanning tree by repeatedly including edges when justified by the Cut Property and deleting edges when justified by the Cycle property - in any order at all - will end up with a minimum spanning tree.

Is there any proof for this claim? Intuitively, of course, it seems right. I haven't been able to find a proof however when searching online.

# Answer
> 3 votes
Call the algorithm in that claim CC algorithm.

### Assuming all edge costs are distinct

Here is CC algorithm in detail.

Given a weighted connected undirected graph, CC algorithm builds a set of edges by repeating the following step until all edges have been inspected.

* select an arbitrary uninspected edge.
    + either it satisfies the Cut property, it will be included in the set.
    + or it satisfies the Cycle property, do nothing (i.e., do not include it in the wanted set of edges).
    + Mark it as inspected.

**Claim 0**: There is a unique MST.
**Proof**: By common knowledge. It is also exercise 8 of chapter "Greedy algorithm", 2005 edition.

**Corollary**: Every edge either satisfies the Cut property and it is in the unique MST, or it satisfies the Cycle property and it is not in the unique MST.

**Claim 1**: CC algorithm produces an MST (or, the MST).
**Proof:** Clearly, CC algorithm includes every edge that satisfies the Cut property and excludes every edge that satisfies the Cycle property. So, it produces the unique MST.

---

### What if all edge costs are not distinct?

Here is CC algorithm in detail, not assuming all edge costs are distinct.

Given a weighted connected undirected graph, CC algorithm builds a set of edges by repeating the following step until all edges have been inspected.

* select an arbitrary uninspected edge.
    1. if there is some cut such that the edge is the only uninspected edge among all edges that satisfies the Cut property for that cut while no edges included so far satisfy the Cut property for that cut, it will be included.
    2. else if there is some cut such that the edge satisfies the Cut property for that cut while no edges included so far satisfy the Cut property for that cut, throw a random coin and, include the edge if we get head of the coin.
    3. Mark the edge as inspected.

That this general version of CC algorithm produces an MST can be proved by mimicking the steps in section "Eliminating the Assumption that All Edge Costs Are Distinct" of that book.

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


title: $\Sigma_3$-completeness of REG

text:
# Question
Title: $\Sigma_3$-completeness of REG
> Show the the following language is $\Sigma\_3$-complete: $$ \mathrm{REG} = \\{ \langle M \rangle \mid L(M) \text{ is regular}\\}. $$

Using the quantifier method I figured out that REG is in $\Sigma\_3$, but how do I prove that it is $\Sigma\_3$-hard?

# Answer
Let COF consist of all Turing machines which halt on all but finitely many inputs. It is known that COF is $\Sigma\_3$-complete, see here for example.

Given a machine $M$, whose inputs we identify with $\mathbb{N}$, we can construct another machine $M'$, defined as follows:

* If the input is not of the form $1^{n\_1} 0 1^{n\_2} 0 \cdots 0 1^{n\_m}$ for some arbitrary $m$ and naturals $n\_1 \< \cdots \< n\_m$, then halt.
* Run $M$ in parallel on $n\_1,\ldots,n\_m$, and halt whenever one of the copies halts.

The *complement* of the language of this machine consists of all strings of the form $1^{n\_1} 0 1^{n\_2} 0 \cdots 0 1^{n\_m}$, where $n\_1 \< \cdots \< n\_m$ are non-halting inputs of $M$. Denote the complement by $L$.

If $M$ belongs to COF then $L$ is finite, and so regular. If $M$ doesn't belong to COF then we can use the Myhill–Nerode theorem to show that $L$ is not regular: indeed, if $n\_i \neq n\_j$ are two non-halting inputs of $M$, then $1^{n\_i} 0$ and $1^{n\_j} 0$ are inequivalent modulo $L$. This shows that $L(M) \in \mathrm{COF}$ iff $L(M') \in \mathrm{REG}$ (since regular languages are closed under complementation), and so REG is $\Sigma\_3$-hard.
> 1 votes

---
Tags: computability
---


# Question
Title: How to show counting number of 1s in a binary word is under NC^2
A computational problem is said to be in the class $NC^K$, if the result $f(x)$ can be computed in time $O((\log |x|)^k )$ on a multi-processor computer, while the total number of operations remain polynomial in the input size $|x|$, i.e. number of bits in $x$. Show that counting the number of 1’s in a binary word $x \in \left\\{0,1\right\\}^{n}$ is an $NC^2$ problem. Hint: You may use a one-bit adder as a unit of counting.

# Answer
> 1 votes
Your function is in fact in $\mathsf{NC}^1$.

It is well-known that threshold functions are in $\mathsf{NC}^1$ (see for example this question on *cstheory*). In particular, the function $\sum\_i x\_i = w$ is in $\mathsf{NC}^1$ for all $w$. By computing these functions for all $w$, you can easily compute your function in $\mathsf{NC}^1$.

---
Tags: complexity-theory
---


# Question
Title: Prove complement a^nb^nc^n is contextfree
So the complement of L1 = $\\{a^{n}b^{n}c^{n} \mid n \geq 1\\}$ would be L2 = $\\{a,b,c\\}^\* \setminus \\{a^{n}b^{n}c^{n} \mid n \geq 1\\}$.

In other words, any combinations of a,b and c where we dont have an equal number of all three letters and w = $\varepsilon$ is also legit.

However, while I'm certain that there should be a contextfree grammar for L2, I can't seem to find a grammer that allows you to generate the terminals freely without allowing $a^{n}b^{n}c^{n}$ with n $\geq$ 1.

My attempt was to make a starting Rule S -\> $Q\_{\_{a}}$ ; $Q\_{\_{b}}$ ; $Q\_{\_{c}}$ ; $\varepsilon$ so that the individual Q rules would make it possible for two of the terminals a, b and c to have an equal number, but not for the third. (in $Q\_{\_{a}}$, a is restricted by max(b,c), in $Q\_{\_{b}}$, b is restricted by max(a,c), in $Q\_{\_{c}}$, c is restricted by max(a,b) so that the restricted terminal can never show up as often as the unrestricted terminal with the highest count)

The rules I set up though, only allow to have unlimited numbers of unrestricted terminals in any order. I'm not sure how to implement a rule for the restricted terminal, without allowing it to have as high a count as the unrestricted ones, if the unrestricted ones have the same count.

here's my P for G$\_{\_{L2}}$ so far

S $\rightarrow$ $Q\_{\_{a}}$ ; $Q\_{\_{b}}$ ; $Q\_{\_{c}}$ ; $\varepsilon$

$Q\_{\_{a}}$ $\rightarrow$ $Q\_{\_{a}}$b $Q\_{\_{a}}$ ; $Q\_{\_{a}}$c $Q\_{\_{a}}$ ; $\varepsilon$

$Q\_{\_{b}}$ $\rightarrow$ $Q\_{\_{b}}$a $Q\_{\_{b}}$ ; $Q\_{\_{b}}$c $Q\_{\_{b}}$ ; $\varepsilon$

$Q\_{\_{c}}$ $\rightarrow$ $Q\_{\_{c}}$a $Q\_{\_{c}}$ ; $Q\_{\_{c}}$b $Q\_{\_{c}}$ ; $\varepsilon$

These are still missing the rules for the individual restricted variable. In what fashion can I add those, without breaking the \[ $a^{n}b^{n}c^{n}$ | n = 0 \] rule?

Edit: it occured to me that I could refine the restricting rules, such that the restricted terminal can be derived from a rule if, and only if one (and only one) of the unrestricted ones is always created with it. For example:

S $\rightarrow$ $Q\_{\_{a}}$ ; $Q\_{\_{b}}$ ; $Q\_{\_{c}}$ ; $\varepsilon$

$Q\_{\_{a}}$ $\rightarrow$ $Q\_{\_{ab}}$b $Q\_{\_{ab}}$ ; $Q\_{\_{ac}}$c $Q\_{\_{ac}}$

$Q\_{\_{ab}}$ $\rightarrow$ $Q\_{\_{ab}}$b $Q\_{\_{ab}}$ ; $Q\_{\_{ab}}$c $Q\_{\_{ab}}$ ; $Q\_{\_{ab}}$ a $Q\_{\_{ab}}$ b $Q\_{\_{ab}}$ ; $Q\_{\_{ab}}$ b $Q\_{\_{ab}}$ a $Q\_{\_{ab}}$ ; $\varepsilon$

$Q\_{\_{ac}}$ $\rightarrow$ $Q\_{\_{ac}}$b $Q\_{\_{ac}}$ ; $Q\_{\_{ac}}$c $Q\_{\_{ac}}$ ; $Q\_{\_{ac}}$ a $Q\_{\_{ac}}$ c $Q\_{\_{ac}}$ ; $Q\_{\_{ac}}$ c $Q\_{\_{ac}}$ a $Q\_{\_{ac}}$ ; $\varepsilon$

At this point my brain starts running in circles. Would this set me on the right path?

# Answer
You're overcomplicating. There is no need for the grammar to be deterministic, so it's OK for cases to overlap.

Say $\omega \in \overline{L\_1}$. At least one of the following statements must be true:

* $\omega = a^ib^j\nu \text{ where } i \ge 1, j\ge 0 \text{ and } i \ne j, \text{ and } \nu \text{ does not start with } b$
* $\omega = a^ib^jc^k \text{ where } i, j, k \ge 1, \text{ and }j \ne k$
(I don't require $i = j$, although if $i \ne j$ then the first condition *also* applies.)
* $\omega \text{ does not start with } a$
* $\omega \text{ contains } ba, ca \text{ or }cb$

These all have reasonably simple grammars.

---

Just in case it's not obvious, there are a few ways to do $a^jb^k | j\ne k$. One simple one:

$$\begin{align} S &\to A \mid B \\ A &\to aC \mid aA \\ B &\to Cb \mid Bb \\ C &\to \epsilon \mid aCb \end{align} $$

$C$ is a balanced sequence of $a$ and $b$, $A$ has more $a$s, $B$ has more $b$s, and $S$ has either more $a$s or more $b$s.
> 1 votes

# Answer
Informally let us first see the structure of the language.

$$L\_2= \Sigma^\* \text{\\\} \\{a^nb^nc^n | n \geq 1\\}$$

This language has all strings which :

1. starts with $b$.
2. starts with $c$.
3. starts with $a$ and have the form $a^i b^j c^k . (a+b+c)^\*$ where $\lnot((i=j) \land (i=k) \land (j=k)) \equiv ((i\neq j) \lor (i\neq k) \lor (j\neq k))$. Now strings of this form can be represented as follows: $$(a^ib^jc^\* + a^i b^\* c^j + a^+b^ic^j). (a+b+c)^\*, \text{where $(i\neq j)$}$$
4. starts with $a$ and have the form (to handle strings such as $abcabc$ for instance): $$(a^+b^+c^+)((a^++b^+)^+c^\*)(a+b+c)^\*$$

Cases 1,2,4 are regular and case 3 is the one which requires stack. So we can easily create a PDA out of this. It shall be NPDA I guess, because on seeing we should work in parallel in two possible path ways, (3 and 4).
> 0 votes

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


# Question
Title: Print all nodes which are the endpoint of the diameter of a tree
Given a tree with n nodes, Print all nodes which are the endpoint of the diameter. 1\<= n \<=100000.

E.g.

For Above tree answer would be A,B,F,G

I tried the O(n2) approach (Running Dfs from each node) but need a solution better than it.

# Answer
> 2 votes
One-line takeaway: **a tree has either one center or two adjacent centers, which are shared by all diameters.**

---

The clue to solve the problem faster is sort of hidden in the symmetric tree given in the question. You can observe that the node D is the center of the tree. Every endpoint of a diameter is 2 edges away from D.

However, all trees are not symmetric. For example, we can remove node B from the given graph. Well, node D remains to be "the center".

In general, if a diameter of a tree is of even length, that diameter has a node at its center. For example, the diameter
$\quad\quad$ A - C - D - E - G $\quad\quad$
has node D as its center node. Moreover, **that center node is the center node of every diameter of the tree**. So in this case, we can locate the center. Then breadth-first (level-by-level) search starting from the center. The nodes we will visit at the furthest level will be all endpoints of all diameters.

Another case is when diameters are of odd length. Then each diameter has two nodes in the middle. For example, imagine node F and G are removed. Then node C and D are the center nodes. Moreover, **those two center nodes are the centers nodes of every diameter of the tree.** In this case, we will locate the centers. Imagine the edge between the two centers is broken. Then we can do two breadth-first (level-by-level) search, each time starting from one of the two centers. The nodes we will visit at the furthest level in either BFS will be all endpoints of all diameters.

Let $n$ be the number of nodes in the tree.

* It takes $O(n)$ time to find a diameter, either by one DFS or two DFS.
* It takes $O(n)$ time to locate the center or centers of a diameter.
* One BFS in the case of one center or Two BFS in the case of the two centers will find all the endpoints of diameters. This takes $O(n)$ time. (Instead, we could also do one DFS, keeping track of the distance and, in the case of two centers, which side of center the node is in. This also takes $O(n)$ time.)

So, the whole algorithm takes $O(n)$ time.

---

**Exercise**. Show that all diameters of a tree share their centers, whether there is one center or two centers.

---
Tags: algorithms, data-structures, trees, depth-first-search, breadth-first-search
---


# Question
Title: Learnability of singleton in realizable case
I am required to show that the class of singletons $H\_{sing}$ is learnable in the realizable case (without invoking the VC-dimension).

$H\_{sing}$ is defined as $H\_{sing} := \\{h \in \\{0, 1\\}^X : |\\{x \in X : h(x) = 1\\}| \le 1\\}$

Also I need to prove if this class also learnable if $X = R$?

Can someone please help ?

# Answer
First, let's see what a learning algorithm looks like. It takes as input samples $(x\_1,y\_1),\ldots,(x\_m,y\_m)$, where $x\_i \in X$ and $y\_i \in \\{0,1\\}$, with the promise that $y\_i = h(x\_i)$ for some $h \in H\_{\mathit{sing}}$. It should output some $h' \in H\_{\mathit{sing}}$.

Second, let's see when a learning algorithm is successful, according to the definition of PAC learning. Here is what we need: for every $\epsilon,\delta\>0$ we need there to be an $m = m(\epsilon,\delta)$ such that for every distribution $\mathcal{D}$ on $X$ and any $h \in H\_{\mathit{sing}}$, if we feed the learning algorithm $m$ samples $(x\_i,h(x\_i))$, where $x\_i \sim \mathcal{D}$, then with probability $1-\delta$ (over the choice of samples), the algorithm must output $h' \in H\_{\mathit{sing}}$ such that $\Pr\_{\mathcal{D}}\[h' \neq h\] \leq \epsilon$.

What can the learning algorithm do? It depends on what it sees. If $y\_i = 1$ for some $i \in \[m\]$, then the learning algorithm can recover $h$. If $y\_1 = \cdots = y\_m = 0$, then the learning algorithm doesn't know anything about $h$, and so it might as well output $0$. This is the only reasonable learning algorithm. It remains to prove that for every $\epsilon,\delta$ you can find $m = m(\epsilon,\delta)$ for which the definition above is satisfied. This is your task.
> 1 votes

# Answer
The VC-dim seems to be finite for $X = N$ (thus is PAC-learnable). So what about for $X = R$? It feels like the VC-dim is still the same in that case, so can we assume it's still PAC-learnable right?
> 0 votes

---
Tags: machine-learning
---


title: Difference between (0)* and (0*)*

text:
# Question
Title: Difference between (0)* and (0*)*
I know that,

`0*` generates, `NULL, 0, 00, 000, 0000, ... and so on`.

But how does `(0*)*` actually work? Does it generate even length 0's?

Like this, `NULL, 00, 0000, 000000...`

or it generates strings same as first expression? What I thought is that if it has 2 star means, that it will multiply any string inside, regardless of odd or even length and the output will be even eventually? Am I going correct?

# Answer
> 3 votes
They generate the same set of strings. In fact, for any set of strings $A$:

$${A^\*}^\* = A^\*$$

I am going to use lower-case lambda $\lambda$ to denote the zero-length string; some textbooks use epsilon: $\epsilon$ or $\varepsilon$. This is what you called `NULL`, but it is more common to reserve that word for the null set or empty set, usually denoted $\emptyset$.

Intuitively, $A^\*$ means $\lambda \cup A \cup AA \cup AAA \cup \cdots$.

Then:

$${A^\*}^\* = \lambda \cup A^\* \cup A^\*A^\* \cup A^\*A^\*A^\* \cup \cdots$$

We could expand this, but don't have to. What I want you to notice is that there is a set of strings $B$ such that:

$${A^\*}^\* = A^\* \cup B$$

Or, to put it another way, $A^\*$ is a *subset* of ${A^\*}^\*$. Every string in $A^\*$ must also be in ${A^\*}^\*$.

To show that ${A^\*}^\* = A^\*$ would also require showing that ${A^\*}^\*$ is a subset of $A^\*$, and I'll leave that as an exercise if you're interested. But this is enough to show that every string in $\mathbf{0}^\*$ is also in ${\mathbf{0}^\*}^\*$, including those with odd length.

The Kleene star operator is sometimes easier reason about if you use subsets rather than equalities. See Kleene algebra for more on this.

---
Tags: regular-languages
---


# Question
Title: How can I develop an algorithm to schedule production?
Given an an table that contains products I am selling with the dates, and given a table that contains the possible work orders with each work order, arrange the work orders such that all items are filled. (assume a starting stock of 0)

What I can produce per day:

| Item1 | 30 |
| --- | --- |
| Item2 | 20 |
| Item3 | 25 |

Sales Orders:

| Item | Day | Quantity |
| --- | --- | --- |
| Item1 | 1/1/2021 | 40 |
| Item2 | 1/1/2021 | 15 |
| Item3 | 1/2/2021 | 20 |
| Item2 | 1/5/2021 | 18 |
| ... | ... | ... |
| Item2 | 12/31/2021 | 14 |

The efficiency of the solution can be judged by the standard deviation of the stock quantity.

For example if I have 100 of Item1 and 0 of Item2 the solution is inefficient. If I have 50 of each the solution is optimal.

I can't think of a way to calculate it other than to iterate through all possible configurations, leaving me with a runtime on $n!$

# Answer
> 0 votes
I made a mistake in my question. Since order does not matter the complexity is simply $n\cdot m$ where $n$ is the amount of days and $m$ is the amount of items. Since this drastically reduces the complexity I consider this an answer. I will leave this open if others can provide an optimization.

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


# Question
Title: Adding a finite set to a non-regular language
Suppose $A = \\{0^{n}1^{n} \mid n \ge0\\}$, which is not regular, and let $B$ be a finite subset of $\Sigma^\* \setminus A$. Is $A \cup B$ regular?

# Answer
Note the closure properties of regular languages. What is $(A \cup B) \setminus B$? What does that imply about $(A \cup B)$ since we know $B$ is regular (due to being finite)?
> 6 votes

---
Tags: regular-languages
---


# Question
Title: Is set of all RE languages $\subseteq\\$ $\Sigma^{*}?$
We know that any languages $\subseteq\\\\\$ $\Sigma^{\*}.$ Because any language collection of string over alphabet. And we know that set of all languages is $2^{\Sigma^{\*}}$ which doesn't $\subsetneq\\\\\$ $\Sigma^{\*}.$ But I have couple of smalls confusion are that

$A.$ Set of all regular languages $\\{L\_1,L\_2,L\_3................\\}$ is $\subseteq\\\\\$ $\Sigma^{\*}$ or not?

$B.$ Set of all context free languages $\\{L\_1,L\_2,L\_3................\\}$ is $\subseteq\\\\\$ $\Sigma^{\*}$ or not?

$C.$ Set of all recursive enumerable languages $\\{L\_1,L\_2,L\_3................\\}$ is $\subseteq\\\\\$ $\Sigma^{\*}$ or not?

$D.$ Any not recursive enumerable language $L$ is $\subseteq\\\\\$ $\Sigma^{\*}?$

# Answer
> 1 votes
The set $\Sigma^\*$ consists of all words over $\Sigma$.

A language over $\Sigma$ is not a word over $\Sigma$. Hence no language is a member of $\Sigma^\*$, and no set of languages is a subset of $\Sigma^\*$.

---
Tags: formal-languages, computability, regular-languages, context-free, enumeration
---


# Question
Title: How to solve $T(n) = 2T(n/4) + n \log n$ with substitution method?
I am trying to solve this recurrence with substitution method. I guess $T(n) = \Theta(n \log n)$ (with Master Theoreme). Can someone show me how to demonstrate the upper bound $T(n) = O(n \log n)$?

# Answer
Use complete induction. The base case is obvious, and here is the induction step:

$$T(n)=\\2T\left(\frac{n}{4}\right)+n\log(n)\le\\ 2c\cdot\frac{n}{4}\log\left(\frac{n}{4}\right)+n\log(n)\le\\\frac{2c}{4}n\log(n)+n\log(n)=\\\left(\frac{2c}{4}+1\right)n\log(n)$$

So by choosing any $c$ such that $\frac{2c}{4}+1\le c$, you can guarantee that $$T(n)\le \left(\frac{2c}{4}+1\right)n\log(n) \le c\cdot n\log(n)$$ As required to show.
> 1 votes

---
Tags: recurrence-relation, master-theorem
---


# Question
Title: What could be the most efficient algorithm to compare two unsorted arrays?
I have two arrays A and B of the same length n. I am looking to swap such that all the elements of array A are less than each element of B. Elements in A and B can be unsorted.

Example Inputs: `A = [2,5,1,8], B = [9,3,6,10]`

Expected Outputs: `A = [2,5,1,3], B = [9,8,6,10]`

I solved using brute force way that takes `O(n^2)` but I am wondering if it can be solved in a better way in terms of time complexity?

# Answer
You can use quickselect, which has expected linear time complexity. (There's a version using the median-of-medians partitioning algorithm which has worst-case linear time complexity, but it's usually a lot slower in practice.) Note that if there are duplicate elements in the two arrays, it might not be possible to satisfy the strict less-than constraint without modifying the lengths of the two result arrays.

A simple in-place quickselect solution would be to consider the two input arrays $A$ and $B$ as a single contiguous array $\overline{AB}$ by using the indexing function

$$\begin{equation}\overline{AB}\_i = \begin{cases}A\_i, &\text{ if }i\le|A|\\ B\_{i-|A|}, &\text{ otherwise } \end{cases} \end{equation} $$

You then run quickselect on $\overline{AB}$ for element $|A|+1$. (That assumes that indexing starts at 1. If you're used to 0-based indexing, adjust as necessary.) This takes expected time $O(|A|+|B|)$ and does not require $A$ and $B$ to be the same length.

If you require the outputs to be stable, as shown in your example (so that the elements in each output array preserve their original order from the original arrays), then you can use quickselect as above to find $p=\text{element }|A|+1\text{ of }\overline{AB}$, as above, but working on a copy of the concatenation of the two arrays (because quickselect is an in-place algorithm which modifies its input). You then do a final $O(|A|+|B|)$ scan over the two arrays simultaneously, looking for an element in $A$ which is greater than $p$ and an element in $B$ which is less than $p$. Swap these two elements and continue the scan. (If duplicate elements are allowed and $p$ happens to be a duplicate, then some adjustment will be needed.)
> 2 votes

# Answer
You could sort them and then iterate over them. Sorting is $n\log n$ and then it would only take one more pass to go check them because once you've passed an element, you know you've done all the swapping you need for that element.
> 1 votes

# Answer
Concatenate A and B into one array C with a total length of 2n. You start with the partition \[1, 2n\] of C with the goal to make the first l items less than the last r items, l = r = n initially.

As long as your partition has length 2 or more: Pick a random pivot element. Partition into two partitions of length x and y, like in quick sort. If x \<= l then you remove the first x items from the partition, and subtract x from l. If y \<= r then you remove the last y items from the partition and subtract y from r. Since x+y = l+r, either x \<= l or y \<= r must be true; both if you are lucky. So you repeat until the length of the remaining partition is 1, and you are done.

Proof of correctness: At each step, the items left of the partition are smaller than the ones inside or to the right of the partition, and the ones right of the partition are greater than the ones inside or to the left of the partition.

Average time is O(n).

And must have gone straight over someone's head :-)
> -1 votes

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


title: Is $O(\log x) = O(1)$?

text:
# Question
Title: Is $O(\log x) = O(1)$?
A colleague recently brought up this argument when we were talking about big-O runtime analysis and I've been unable to find why it is incorrect:

Informally, the argument goes like this:

> "If the runtime of all logarithms of any base are supposed to be equivalent, there is nothing that keeps us from saying $O(\log x) \equiv O(\log\_x x) \equiv O(1)$, so either the upper bound of logarithmic growth is constant (which it evidently is not) or all logarithms are, after all, not equal in runtime."

We recalled the reasoning behind the accepted $ O(\log\_a x) \equiv O(\log\_b x)$ from the lemma that allows us to calculate logarithms of arbitrary base, i.e.

$$ \log\_a x = \frac{\log\_b x}{\log\_b a} $$ where, since $a,b$ are constant also $\frac{1}{\log\_b a}$ is constant, and hence $ O(\log\_a x) \equiv O(\log\_b x)$ holds.

I argued that since $x$ is decidedly not a constant, his conjecture would also be false as no constant factor could be extracted from the lemma.

The counterargument quickly followed, stating that since $ O(\log\_a x) \equiv O(\log\_b x)$ holds $\forall a,b \in \mathbb{R^+}$ it must not only hold in $a =x$ or $b = x$, but also in $a=1$ and $b=1$ and consequently $ O(\log x) \equiv O(\log\_1 x) = O(0) \equiv O(1)$ breaking the original lemma not only for the base $x$ but also base $1$, where $1$ is about as constant as it gets. \<- beer induced math fail

At that point in conceded that I could not find a flaw in the argumentation and as such I am turning to you: What's going on here and where are we wrong?

# Answer
Let me emphasize some flaws in argumentation:

1.

> $O(\log x) \equiv O(\log\_x x)$

is false because on left hand base of logarithm is constant, but on right hand not.

2.

> $ O(\log\_a x) \equiv O(\log\_b x)$ holds $\forall a,b \in \mathbb{R^+}$

is false, because there should be additionally $a,b \> 1.$
> 2 votes

# Answer
Let's generalize the argument. It is well-known that $O(f(n)/C) = O(f(n))$. Now let $f(n)$ and $g(n)$ be arbitrary functions. Then $$ O(f(n)) = O(f(n)/f(n)) = O(1) = O(g(n)/g(n)) = O(g(n)). $$ What goes wrong here? We only have $O(f(n)/C) = O(f(n))$ for *constant* $C \> 0$.

Similarly, we only have $O(\log\_a n) = O(\log\_b n)$ for *constant* $a,b\>1$.
> 1 votes

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


title: Introductory books on Computer Networks

text:
# Question
Title: Introductory books on Computer Networks
While I have come to learn some computer science, I find that I have next to no knowledge on computer networks.

Are there any good books at a basic level that cover some of the fundamental topics? Ideally something that doesn't overwhelm a newcomer and provides a good jumping-off point to get started with.

If it helps, my own background is primarily in mathematics, although I have covered a few topics in computer science, namely algorithms and computer graphics.

# Answer
> 0 votes
Try this one out: https://hpbn.co/

It's concerned more with connection optimization however it still introduces a lot of concepts in a top down approach, meaning, starting from the application layer moving into the transport layer, HTTP -\> TCP, as opposed to a lot of networking books which will start from a bottom up approach, twisted pair cables/signal encoding -\> HTTP. I.E physical layer up to application layer.

---
Tags: computer-networks, books
---


# Question
Title: How does a hash table not require all the keys to be looked through to find a value, i.e. O(N)?
Before starting, I want to say that I understand time complexity, and I understand how a hash table is considered O(1) vs an array having a time comp. of O(N) in terms of what you learn. What I don't understand is *why* looking up something in a hash table is not O(N).

Surely, just because you know the `key`, you still have to look your way through the data structure to find it. An analogy might be to knowing someone's name in order to find their phone number in a phone book: you can't just open the book **exactly** on their name; you still have to work your way through to find their location.

*Tl;dr: I want to know *how* a hash table can retrieve a `value` without having to look for said `value` through all the `keys`:`values` before it.*

# Answer
> 3 votes
The thing is, a hash table opens the "book" **exacty** (or at least close by, in some terms) where it needs to.

The better analogy is like accessing a list of values with an index: If you have a book list of $100$ people and their phone numbers, and you want the $37$'th person's number, you know exactly where to search it in the book - you don't have to go through all of it.

This is exactly what a hash table does: it encodes the "name" into an index using a hash function.

# Answer
> -1 votes
In a hash table, we take the key, and then from the key we calculate at which place in the table it should be stored. So you just look at that single place, and usually that's where the key is stored.

It's a bit more complicate. Since there are more possible keys than entries in the table, there must be keys that "should" be stored in the same place. So it is possible that a different key is stored in that place. So there is a second formula that calculates alternative places for the key, and they will be visited until the key is found or an empty space (which means the key is not there).

If you make the table large enough compared to the number of keys stored, you will have an average of two or less accesses.

---
Tags: time-complexity, data-structures, hash-tables
---