# Question
Title: Why is the number of comparisons in a BST missing key lookup about 2 ln N?
In (An Introduction to the Analysis of Algorithms) by Philippe Flajolet and Robert Sedgewick it's written that: **Insertions and search misses in a BST built from N random keys require ~ 2 ln N (about 1.39 lg N) compares, on the average.** I didn't get it well, even after I read their explanation, can you help to understand it by simplifying the idea to me? I mean why do we have **2 ln N** compares?

# Answer
> 1 votes
This is a late response but my solution is present on this Google Doc. Hopefully people in the future can benefit from my explanation:

Here is the link to the Google Doc I typed up: https://docs.google.com/document/d/16NrVWLNLi1Hxg8gCgkwZbCQ3zLciJOMmA4aU4tiCBDk/edit?usp=sharing

It is a little lengthy yes, but this is because I am explaining, most detailed as possible, the logic and the mathematics involved.

As a side note, readers may want to brush up on integration techniques, specifically partial fraction decomposition.

If there is anything that needs fixing, please comment on the Google Doc.

Happy reading!

# Answer
> 0 votes
The 2 comes from doing 2 comparisons at each node visited by the algorithm. The lg(n) comes from having to examine one node from each generation, or one node at each height in the tree. So, if we need to examine lg(n) nodes, and preform 2 operations at each node, we preform a total of 2lg(n) operations.

# Answer
> -1 votes
You can say that O(2ln(n)) = O(ln(n))

It is easy to show that the search and misses are O(ln(n)).

Consider a binary search tree (BST). If you are searching from root, you either go left or right based on the knowledge of whether your search key is less than or greater than the value at root. So, when you select to go left (or right), you move one level down ignoring the nodes on the right (or left).

This way you will have to cover at most one node at any level. So, the number of nodes you cover in total is O(h) which is height of the tree.

Now, the height of the tree depends on the number of nodes according to:

O(h) = O(ln(n))

therefore, total number of nodes covered is O(h) = O(ln(n))

# Answer
> -2 votes
First, this seems weird, since 2 ln n is nowhere near 1.39 lg n. I'd say it is about 4.6 lg N.

You would need a very detailed analysis of the situation. If the binary tree was built by inserting the nodes in random order, a tree with 255 keys might have a height of 8 if you are extremely lucky, or a height of 255 if you are really unlucky, or anything in between. Then when you search for an item that is in the tree, it might be in the left branch or the right branch, and they will often have different heights, so the number of comparisons is limited by the height of the tree, but also limited by the height of each subtree that you enter.

So to find out why it is 2 ln N (IMPORTANT: There are several logarithms. log n or lg n or log10 n is usually base 10. ln N is usually base e. lb n or log2 n is base 2. In a comment you switched from 2 ln N to 2 lg N, which is something completely different), you have to follow and understand the analysis in that book. I could probably do that analysis for you, but if I had the time to do it, it wouldn't be any easier for you to understand than what two professional authors did.

---
Tags: algorithms, algorithm-analysis, mathematical-analysis, binary-search-trees
---


# Question
Title: Kth largest element of a Min Heap of size K is always root element
Why the Kth largest element of a Min Heap of size K is always root element of the Min Heap ? How to prove this ?

# Answer
Let's assume that the heap $k$-th largest element is unique otherwise your assertion is false (consider an heap consisting of only two identical elements).

The $k$-th largest element of a min-heap of size $k$ is the minimum element and therefore your question is equivalent to "why is the minimum element the root of a min-heap?"

Suppose that the minimum element $e$ was not the root of the heap and let $f$ be the element stored in the parent of $e$. By the heap properties we have $f \le e$ but since $f \neq e$ it must be that $f \< e$, resulting in a contradiction.
> 2 votes

# Answer
Consider the following increasing sorted sequence with size $k=4$ $$ \langle 1,2,3,4 \rangle$$ $1^{th}$ largest element is $4$, and $2^{th}$ largest element is $3$, and $k^{th}$ (i.e. $4^{th}$) largest element is $1$. So for your question, $n^{th}$ largest element for a min-heap $\mathcal{H}$ of size $n$ is equal to $1^{th}$ smallest element in $\mathcal{H}$, because of $\mathcal{H}$ is min-heap, additionally by definition of min-heap, smallest element appear in root of $\mathcal{H}$ , otherwise it contradict with property of min-heap, because it's provable that $k^{th}$ smallest element in $\mathcal{H}$ can go down at most $k$ levels.

**Note that, we can conclude that $k^{th}$ ( $k\leq n$) largest element of a min-heap with size $n$ equal to $n-(k-1)$ smallest element.**
> 3 votes

---
Tags: binary-trees, heaps
---


# Question
Title: Shortest path covering certain nodes in a graph
Consider a weighted graph where each node represents a city. Now a truck starts
from a `city A` and it has to cover a set of cities `B, C, D`.. could be in any order
How to generate an ordering that result in the minimum total distance travelled
while covering all the cities.

# Answer
The problem is NP-hard by a routine reduction, so you won't find an efficient algorithm unless P = NP. If the number of cities is not large, just try all orderings. Otherwise, you can resort to a heuristic (e.g., build the path city-by-city always picking say the one closest to your current location) or a more complex metaheuristic like a genetic algorithm.
> 1 votes

# Answer
Let $G=(V,E)$ be the graph and let $S$ be the set of cities you want to visit.

Since you talk about "covering" all the cities, it might be the case that you are fine with visiting cities more than once as long as all cities in $S$ are visited at least once. The problem is still NP-hard in this case (see Juho's answer), but it can be 1.5-approximated using Christofides algorithm.

To do so you can first compute the metric closure $G'$ of $G$ ($G'$ is a complete graph and the weight of a generic edge $(u,v)$ is the weight of the shortest path from $u$ to $v$ in $G$). Then, you can restrict yourself to the subset of cities of interest, i.e., you can consider the subgraph $H = G'\[S\]$ of $G'$ induced by the vertices in $S$.

Clearly the weight $w^\*$ of an optimal tour is the same on both $G$ and $H$. By running Christofides algorithm on $H$ you obtain a tour $T$ of weight at most $1.5w^\*$.
The tour $T$ can be converted back to a tour on $G$ by replacing each edge $(u,v)$ of $T$ with the shortest path from $u$ to $v$ in $G$. This doesn't change the cost of $T$.
> 1 votes

---
Tags: algorithms, weighted-graphs
---


# Question
Title: P = NP ==> there exists no OWF: proof using NTM and binary tree
I read a proof in my script: If $P = NP\implies $ there exists no OWF $f$. A function $f$ is a OWF $\iff$ $f\in PTIME \space \land$ $f^{-1}\notin PTIME$

Their proof was a bit messy so I want to ask if the following technique (in general) can be used to proof similar problems:

Assume $P = NP$, and a OWF $f$ over $\\{0, 1\\}^n$ (We can transform any alphabet to $\\{0, 1\\}^n$). We have to show that $f^{-1}$ can be calculated in $PTIME$. Assume we are given $y$ and have to calculate $x$ so that $f(x) = y$.

$\exists NTM \space M $, that can check every possible String in $\\{0, 1\\}^n$ in $\mathcal{O}(n)$ time (binary tree). $M$ works like this:

For every $i=1,...,n$ it checks every string $s \in \\{0, 1\\}^n$ with $|s|=i$. So, for $i=2:f(00),f(01),f(10),f(11)$. Because $M$ is non-deterministic, it can traverse every layer of the binary tree simultaneously. If $f(s) = y \implies $ $M$ found the $x$ so that $f(x) = y$.

Therefore, $f^{-1}$ is in NP. If $P = NP$ $\implies$ $f^{-1}$ is in $P$ and there would not exist an OWF.

# Answer
The core idea is good. You might want to elaborate more on how this process is done in detail:

Let us keep in mind that an OWF is a function $F$ that can be computed in $poly(n)$ time but $F^{-1}$ cannot be computed in polynomial time.

Assume that $P=NP$. Therefore, to prove that there is no OWF, we will show that no function $F$ can be a OWF. Notice that it is enough to find for any function $F$ computable in $poly(n)$ time a non-deterministic TM that computes $F^{-1}$ in $poly(n)$ time (since then we could convert this TM to be deterministic).

However, doing that is easy: Let $y$ be the input for that machine. We will non-deterministically guess an $x$, and we will verify that $y=F(x)$. Since we know that $F$ can be computed in polynomial time, then this entire verification process is polynomial as well. Hence, this algorithm is a non-deterministic polynomial algorithm computing $F^{-1}$. From what we said earlier, since we assumed $P=NP$, then $F$ cannot be a OWF, and hence we proved the claim.
> 2 votes

# Answer
$f$ is a one way function if given $x, y = f(x)$ can be calculated in polynomial time in the size of $x$, but given $y$ knowing that $y = f(x)$, $x$ cannot be calculated in polynomial time in the size of $y$.

$NP$ is only about yes/no questions, but if we ignore that then the problem of finding $x$ is (kind of) in $NP$, because all we need to do is guess the right $x$ and verify in polynomial time that $y = f(x)$. However it is not in $P$, because to be in $P$, we would have to be able to find $x$ without any oracle or lucky guesses, and by the definition of "one-way function" we can't do that for one-way functions.

Now in practice we don't require OWF's to be non-polynomial, but just very hard to solve. We might find an $f$ where we can find $x$ from $g(x)$ in $n^{100}$ seconds, where $n$ is the size of $y$. That's "one-way" enough for all practical purposes; you can't even solve this for $n=2$. Such an "OWF" could still exist if $P=NP$.
> 0 votes

---
Tags: turing-machines, p-vs-np, one-way-functions
---


title: Trace minimum spanning tree's path

text:
# Question
Title: Trace minimum spanning tree's path
I have a list of connected rooms, I need to visit each room in the list, but I have to record the exact path to traverse the entire graph.

```
1: [2]
2: [1,2,3]
3: [2]
4: [2]

```

```
output: [1,2,3,4]

```

```
expected: [1,2,3,2,4]

```

I've written a Depth First Search that returns a path of \[1,2,3,4\], what I am looking for is \[1,2,3,2,4\] I'm unsure of how to keep track of the fact that if I visit 3 , I must go back to 2 before I can move to 4. Sorry if I'm not explaining this well, I'm fairly new to cs.

Here is my dfs function.

```
const dfs = (start, visited = new Set(), path = []) => {
  visited.add(start);

  const connectedRooms = mapObject[start].connections;
  if (visited.size === Object.keys(mapObject).length) {
    return getPathDirections(path);
  } else {
    for (const room of connectedRooms) {
      if (!visited.has(room.ID)) {
        path.push(room.ID)
        visited.add(room.ID);
        dfs(room.ID, visited, path)
      }
    }
  }
}

```

# Answer
> 0 votes
Your implementation probably looks somewhat like this:

```
VISITED[1...n] = {false, ..., false}

DFS(v):
   VISITED[v] = true
   Record that v was traversed
   for each neighbor u of v:
      if not VISITED[u]:
         DFS(u)

```

That is you are recording $v$ only when the DFS search starts visiting $v$. You also need to record $v$ when the DFS search comes back to it after having visited one of its children. I.e.:

```
VISITED[1...n] = {false, ..., false}

DFS(v):
   VISITED[v] = true
   Record that v was traversed
   for each neighbor u of v:
      if not VISITED[u]:
         DFS(u)
         Record that v was traversed     //Here we record v, not u!!

```

---
Tags: minimum-spanning-tree, depth-first-search
---


title: Merging Tuples of Intervals

text:
# Question
Title: Merging Tuples of Intervals
Suppose I have a list of tuples. Each tuple contains 2 intervals. The intervals in each tuple have nothing to do with each other. I would like to find a smaller list of tupels that covers all elements in each interval.

Therefore it´s necessary to merge the intervals of the first type and the intervals of the second type separately. It is important to know that the intervals of a tuple have a relationship. Thus, a tuple cannot be merged with another tuple unless both intervals can each be merged separately with the interval belonging to them.

---

An example:

Let valid values for the first elements of the tuples are number intervals. Let valid values for the second elements of the tuples are character intervals.

A valid optimization of `[{[1-3], [a-d]}, {[4-7],[e-f]}]` would be `[{[1-7], [a-f]}`. But it is not possible to simplify tuples like `[{[1-3], [a-d]}, {[7-9], [e-k]}]` because between `1-3` and `7-9` there are still the numbers `{4, 5, 6}`.

---

I am looking for efficient algorithms to simplify this kind of list of tuples that contains intervals.

A simple solution would be to simply check all combinations. But how can large datasets be optimized? Checking all combinations would cost to many ressources.

So my questions are:

* **Are there well-known (efficient) algorithms for such tasks, such as approximation algorithms?** I'm looking for a kind of merge intervals algorithm, but for tupels. It should optimize both attributes so that one gets fewer elements in the tuples list.
* **Is this a well-known problem?** (Is there a reduction from some NP-complete problem?) I guess my problem is somehow related to the set cover problem? Am I right?

Thanks for any help!

# Answer
Consider the greedy algorithm that iteratively searches for two distinct pairs of intervals that can be merged, merges them, and repeats until no more merges are possible.

We need to show that this algorithm is optimal. Notice that, at each point in time during the algorithm, we can associate the generic $i$-th pair $\mathcal{I}\_i$ with a set $P\_i$ containing all the original pairs that were ultimately merged into $\mathcal{I}\_i$.

Similarly, consider an optimal solution $\mathcal{I}^\*\_1, \mathcal{I}^\*\_2, \dots, \mathcal{I}^\*\_\ell$ and define $P^\*\_1, \dots, P^\*\_\ell$ as the corresponding sets of original pairs. Let $k$ be the number of intervals returned by the greedy algorithm. We want to show that $k \le \ell$ (which implies $k = \ell$).

We start by showing that the final sets induced by an execution of the greedy algorithm must be a refinement of $P^\*\_1, \dots, P^\*\_\ell$. Suppose that this is false and pick the first point in time at which the greedy algorithm merges two pairs $\mathcal{I}\_i$ and $\mathcal{I}\_j$ associated with sets $P\_i$ and $P\_j$ where $P\_i \subseteq P^\*\_h$ and $P\_j \subseteq P^\*\_z$ with $h \neq z$. Since $\mathcal{I}\_i$ can be merged with $\mathcal{I}\_j$, $\mathcal{I}^\*\_h$ contains $\mathcal{I}\_i$, and $\mathcal{I}^\*\_z$ contains $I\_j$, we must have that $\mathcal{I}^\*\_h$ can be merged with $\mathcal{I}^\*\_z$ contradicting the optimality of $\mathcal{I}^\*\_1, \mathcal{I}^\*\_2, \dots, \mathcal{I}^\*\_\ell$.

Suppose now that $k \> \ell$. Then there is some set $P^\*\_h$ that is partitioned into $m \ge 2$ sets $P'\_{1}, \dots, P'\_{m}$ from $\\{P\_1, \dots, P\_k\\}$. Let $\mathcal{I}'\_i$ be the pair corresponding to $P'\_i$. The merge operation that resulted in $P^\*\_h$ can be described as a binary tree $T$ in which each leaf represents a pair in $P^\*\_h$, every internal node $v$ represents a merged pair $\mathcal{I}(v)$, and the root $r$ represents $\mathcal{I}(r) = \mathcal{I}^\*\_h$. Let $P(v)$ be the set corresponding to $\mathcal{I}(v)$. Locate the deepest vertex $v$ in $T$ such that its two children $u$ and $w$ satisfy $P(u) \subseteq P'\_i$ and $P(w) \subseteq P'\_j$ for $i \neq j$. We must have that $\mathcal{I}'\_i$ contains $\mathcal{I}(u)$ and $\mathcal{I}'\_j$ contains $\mathcal{I}(w)$. Therefore, since $\mathcal{I}(u)$ and $\mathcal{I}(w)$ can be merged into $\mathcal{I}(v)$, the pairs $\mathcal{I}'\_i$ and $\mathcal{I}'\_j$ can also be merged. This contradicts the stopping condition of our greedy algorithm.

To implement the greedy algorithm efficiently you can first transform the input instance so that two pairs can be merged if and only if their intervals intersect. Then interpret the intervals in a pair as the sides of a rectangle.

Use a data structure $D$ that is able to (i) maintain a dynamic collection of rectangles and (ii) report all rectangles intersecting with a given query rectangle. For example, you can use a dynamic range tree that supports each of the above operations in $O(\mathrm{polylog}\\, m)$ amortized time, where $m$ is the number of stored rectangles.

Repeat the following:

* For each input pair $\mathcal{I}$:
    + While $D$ contains some pairs (rectangles) that intersect with $\mathcal{I}$.
        - Delete all such pairs from $D$ and let $\mathcal{I}$ be the pair obtained by merging $\mathcal{I}$ with all of them.
    + Insert $\mathcal{I}$ into $D$.

At the end of the algorithm, the contents of $D$ are exactly the final set of pairs. To analyze the time complexity of this algorithm notice that each original pair is inserted at most once into $D$ and can be associated to exactly one query to $D$ that does not satisfy the condition of the while loop. Moreover, the number of merged pairs is at most $n-1$, where $n$ is the number of pairs in input. Each merge inserts at most one pair into $D$ and is respondible for one query. The number of pairs deleted from $D$ is upper bounded by the number of insertions. Overall we perform $O(n)$ operations on $D$.

The overall time needed is then $O(n \\, \mathrm{polylog} \\, n)$.
> 2 votes

---
Tags: complexity-theory, optimization, efficiency, intervals
---


# Question
Title: Misunderstanding about a problem in algorithms
> Consider the following sequence $$\mathcal{S}=\langle3,1,4,1,5,9,2,6,5,3,8,9,7,9,3,2,3,8,4,6,2,7,9\rangle$$ We can imagine some adjacent elements of $\mathcal{S}$ as a number. For example, $5$, and 3 and $8$ form the number $538$. We say two number in above format is disjoint, if there is nothing common element between them. With respect to $\mathcal{S}$, what is the maximum number of disjoint numbers we can make such that have increasing order from left to right?

I think if we consider only numbers with $1$ digit, then we have at most nine numbers that have no common element and sorted in increasing order from left to right. But the answer is $10$ numbers. Maybe i have a misunderstanding about the problem, so any one have a idea to clarify me that why answer become $10$?

# Answer
The problem is probably asking you to select a collection of numbers that can be formed from pairwise disjoint contiguous groups of $k$ digits from $\mathcal{S}$ and such the obtained numbers are **non-decreasing** (and not **increasing** as written in the statement!) when the associated groups are considered from left to right. The goal is to select as many numbers as possible.

Then, for $k=1$, a feasible solution (I didn't check if it is optimal) selects $10$ numbers, highlighted in bold:

$$ \langle 3,\textbf{1},4,\textbf{1},5,9,\textbf{2},6,5,\textbf{3},8,9,7,9,\textbf{3},2,\textbf{3},8,\textbf{4},\textbf{6},2,\textbf{7},\textbf{9}\rangle $$
> 0 votes

---
Tags: algorithms
---


# Question
Title: Why is $\log n+\log \frac{n}{2}+\log \frac{n}{4}+\log \frac{n}{8}+\cdots+\log \frac{n}{n}=\Theta (\log^2 n)$?
$$\log n+\log \frac{n}{2}+\log\frac{n}{4}+\log\frac{n}{8}+\cdots+\log\frac{n}{n}=\Theta (\log^2n).$$

The sum of logarithms is the logarithm of the product $n\cdot\frac{n}{2}\cdot\frac{n}{4}\cdot\frac{n}{8}\cdots\frac{n}{n}$. This equals $n^{\log n}$ divided by what? If the product would just be $n^{\log n}$, then this would make perfect sende since $ \log(n^{\log n})=\log(n)\cdot\log(n)=\log^2 n$. But the divisor equals $\frac{1}{2}\cdot\frac{1}{4}\cdot\frac{1}{8}\cdot\frac{1}{16}\cdots\frac{1}{n}$ so I don't get it.

# Answer
Assuming $n$ is a power of $2$, you have: $$ \sum\_{i=0}^{\log n} \log \frac{n}{2^i} = \sum\_{i=0}^{\log n} \left( \log n - i \right) = \sum\_{i=0}^{\log n} i = \frac{(\log n)(\log n+1)}{2} = \Theta(\log^2 n). $$
> 7 votes

# Answer
Suppose $n=2^k$, and we define $T(n)= \sum\_{i=1}^{\log n}\log \left(\frac{n}{2^i}\right)$:

First we must find out number of logarithm terms in form $\log \frac{n}{2^k}$, that told us, because of $k=\log n$ then number of logarithm terms is $\log n$.

So we can act as follow $$ \sum\_{i=1}^{\log n}\log \left(\frac{n}{2^i}\right)\leq\sum\_{i=1}^{\log n}\log \left(n\right)=\mathcal{O}(\log^2n)$$ So the upper bound is $$T(n)=\mathcal{O}(\log^2n).$$

On the other hand to finding lower bound we act as follow:

$$\log\left(\frac{n^{\log n}}{2^{2\log n}}\right) \leq\sum\_{i=1}^{\log n}\log \left(\frac{n}{2^i}\right) $$

$$=\hspace{4pt}\log\left(\frac{n^{\log n}}{n^2}\right)\leq \sum\_{i=1}^{\log n}\log \left(\frac{n}{2^i}\right)$$

$$=\hspace{4pt}\log\left(n^{\log n-2}\right)\leq \sum\_{i=1}^{\log n}\log \left(\frac{n}{2^i}\right)$$ $$=\hspace{4pt}(\log n-2)\log n\leq \sum\_{i=1}^{\log n}\log \left(\frac{n}{2^i}\right)$$

So according to the left side of inequality our lower bound is $$T(n)=\Omega(\log^2 n)$$ Finally $$ T(n)=\theta(\log^2 n).$$
> 0 votes

---
Tags: runtime-analysis, performance
---


# Question
Title: What are the minimum functions, services, or features of a software to be called as an operating system?
When can we say that a software is an *operating system* and not a *firmware*, in terms of what it can do?

I know that firmware is usually stored in ROM and OS is stored on HDD/SSD, but technically you can also store OS on ROM, so the way of storage is not what exactly distinguishes between an OS and a firmware.

So what can an operating system do that a firmware cannot?

Is it the fact that we can create apps on top of an operating system, but not on top of a firmware?

# Answer
That depends on your definition of "operating system". Some authors define that as the kernel (i.e., Linux, providing process control, a filesystem and simple/controlled access to devices), others add in all sorts of userland applications (i.e., "go to your vendor, ask for an operating system; whatever they give you is an operating system", this can include not only tools for managing your machine but all sorts of application tools and even development suites).

There are operating systems managing user-oriented machines, others handle e.g. huge farms of machines for Google and their ilk, and the computer controlling your car probably has one handling low-level details while most of the interesting stuff is done by "userland" programs.

Check out e.g. FORTH systems, on the microcomputers of the day they were all that ran e.g. on an Apple \]\[. Very minimalistic, to say the least, at a few KiB in all. On the other end of the spectrum consider e.g. the Debian distribution: A slew of gigabytes of software at your fingertips.
> 2 votes

---
Tags: operating-systems, software-engineering, os-kernel
---


title: Some questions about `RANDOM(a, b)`

text:
# Question
Title: Some questions about `RANDOM(a, b)`
This is a question from CLRS:

> Describe an implementation of the procedure RANDOM(a, b) that only makes calls to RANDOM(0, 1). What is the expected running time of your procedure, as a function of $a$ and $b$?

Here RANDOM(a, b) is a random number in the range $a, \ldots, b$.

Here is the answer:

```
RANDOM(a, b)
range = b - a
bits = floor(log(2, range)) + 1
result = 0
for i = 0 to bits - 1
    r = RANDOM(0, 1)
    result = result + r << i
if result > range
    return RANDOM(a, b)
else return a + result

```

Now I have some questions: Why has the book used the term randomized algorithm(expected running time which is for randomized algorithms)? Apparently, we call an algorithm randomized when there's some pseudorandom number generator in some part of it. So why has it called this algorithm itself randomized? As a result of `RANDOM(0, 1)`? what's the exact definition of a randomized algorithm? Is it possible that this algorithm doesn't terminate ?

# Answer
Here is an algorithm that outputs a uniformly random number in the range $0,1,2,3$ given two uniformly random numbers in the range $0,1$:

```
RANDOM4(r0, r1):
    return r0 + 2*r1

```

In contrast, there is no algorithm that outputs a uniformly random number in the range $0,1,2$ given $N$ uniformly random numbers in the range $0,1$, for *any* value of $N$. The reason is that the probability that such an algorithm outputs $0$ is of the form $a/2^N$ for some integer $a$, and this cannot be equal to $1/3$.

However, given an infinite supply of uniformly random numbers in the range $0,1$, we can generate a uniformly random number in the range $0,1,2$ using a technique known as *rejection sampling*:

```
RANDOM3(r):
    for t in ℕ:
        a = r(2*t) + r(2*t+1)
        if a < 3:
            return a

```

Each iteration succeeds with probability $3/4$, and so the expected number of iterations is $4/3$. However, it is potentially unbounded.

Your algorithm also uses rejection sampling. The success probability is always more than $1/2$, so the expected number of iterations is less than $2$.
> 2 votes

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


# Question
Title: GroupBy key a sequence of ordered key values
I have a sorted (by key) sequence of key value pairs:

```
< (1,"A"),(1,"C"),(1,"G"),(1,"B"),(2,"D"),(2,"F"),(3,"E") >

```

And I have to produce a sequence of tuples like this:

```
< (1,< "A","C","G","B" >),(2, <"D","F">),(3, <"E">) >

```

Where the second element of the tuple is a sequence with the values corresponding to the key.

I am working on haskell, under the hood I have a Seq that is a Vector, but a pseudocode solution is OK.

I have this algorithm that will run in parallel in $O(\lg n)$, but cost of work is too high (more than $O(n)$):

```
comb :: Seq s => ((a, s b) -> (a, s b) -> Bool) -> s (a, s b) -> s (a, s b) -> s (a, s b)
comb f sl sr | lengthS sr == 0 = sl
             | lengthS sl == 0 = sr
             | f (nthS sl ((lengthS sl) - 1)) (nthS sr 0) =  let
                                                                 (cl, vl) = (nthS sl ((lengthS sl) - 1))
                                                                 (cr, vr) = (nthS sr 0)
                                                                 union = singletonS (cr, appendS vl vr)
                                                             in appendS (appendS (takeS ((lengthS sl) - 1) sl) union) (dropS 1 sr)
             | otherwise = appendS sl sr

groupDyC :: Seq s => ((a, s b) -> (a, s b) -> Bool) -> s (a, b) -> s (a, s b)
groupDyC f seq = reduceS (comb (f)) emptyS (mapS (\x -> singletonS x) (mapS (\(c, v) -> (c, singletonS v)) seq))

```

Where `lengthA`, `nthS` are $O(1)$ and `appendS` is linear to the size of both sequences.

My problem is that the solution has to have work in $O(n)$ and parallel cost (S) $O(lg n)$. How could I create an algorithm that runs on that cost with these operations:

Thank you very much.

# Answer
> 1 votes
Since the input is sorted, the elements are essentially already grouped, you just need to find the "boundaries" between the groups. By boundary, I mean the index where a run of the same key starts.

You can find the boundaries by filtering the indices where adjacent keys don't match. For example on input `< (1,"A"),(1,"C"),(1,"G"),(1,"B"),(2,"D"),(2,"F"),(3,"E") >` the boundary indices are 0, 4, and 6.

The boundary indices tell you how big each group is (by subtracting adjacent boundaries). Now, you just have to construct the output groups. For each group, do a tabulate, where you offset the index by the boundary. Specifically, the $i$th element of the $j$th group is `input[boundary[j] + i]`.

In total, that's $O(n)$ work for the filter and maps/tabulates. The parallel time is dominated by the filter, costing $O(\log n)$.

---
Tags: algorithms, parallel-computing, haskell
---


# Question
Title: Can any finite problem be in NP-Complete?
My lecturer made the statement

> Any finite problem cannot be NP-Complete

He was talking about Sudoku's at the time saying something along the lines that for a 8x8 Sudoku there is a finite set of solutions but I can't remember exactly what he said. I wrote down the note that I've quoted but still don't really understand.

Sudoku's are NP complete if I'm not mistaken. The clique problem is also NP-Complete and if I had a 4-Clique problem is this not a finite problem that is NP-Complete?

# Answer
> 15 votes
If a finite problem is NP-complete then P=NP, since every finite problem has a polynomial time algorithm (even a constant time algorithm).

When we say that Sudoku is NP-complete, we mean that a generalized version of Sudoku played on an $n^2 \times n^2$ board is NP-complete.

Finally, the 4-clique problem, while not a finite problem (the input graph has unbounded size), is an easy problem which has a polynomial time algorithm.

# Answer
> 6 votes
The statement of your teacher is incorrect or probably you did not hear him correctly. The correct statement is

> Any finite language $L$ with $|L| \geq 1$ cannot be NP-Complete unless $P = NP$.

That is because we still don't know (as on year 2016) if $P \neq NP$. Also $|L|\>1$ is important because $\emptyset$ (the empty language) can never be NP-complete whether $P=NP$ or $P \neq NP$.

Sudoku or chess in not NP-complete (as Yuval has pointed out), because their input is finite size 9x9 or 8x8 board (I am talking about the decision versions, whether sudoku has a solution or whether chess has a winning strategy). In chess, I am assuming if you repeat a position, it is considered a draw.

# Answer
> 1 votes
Theorem. Any finite language L is in P. Proof. Let M be a Turing machine which has all strings of L on its tape. When given an input it checks whether the input is on its tape. This is O(1) time clearly.

Theorem. If and only if P=NP, then every L in P (including thus all finite languages) are NP-Complete. Proof. Recall that a language is NP-Complete iff there exists a reduction in polynomial time of every NP problem to it. If P=NP, then for any NP problem including NPC problems, there is a polytime algorithm for deciding it. Let A be NP-Complete and L be any language in P. Let x be a satisfiable instance of L.

Algorithm. Solve A in polynomial time. Print x.

QED.

This trivially holds because of the weakness of the reduction.

If you heard right, unless your lecturer has a correct proof that P=/=NP, then he does not know and so cannot be taken to be correct.

Though it seems all that he simply meant was that particular sizes of NP-Complete problems are not NP-Complete, but the whole class as parameterized by n. No instances are NP-Complete themselves. (For eg. in a lecture in Alg Lower Bounds: Fun with Hardness Proofs series, Demaine makes a statement to such an effect.)

# Answer
> 0 votes
Recall: A problem X is NP-complete iff it satisfies two criteria:

a) It is in NP - I.e any guessed solution of X can be verified in polynomial time.

b) It is complete for NP - I.e Every problem Y in NP has a polynomial-time reduction which translates an instance of Y to an instance of X (so that any polynomial-time program which solves X would also solve Y in polynomial-time).

We can agree that a 9x9 Sudoku satisfies (a). It is (b) where things fall down. More generally - Problems (in NP or otherwise) typically have instances of size N *for arbitrarily large values of N*; certainly this is true for the known problems in NP. A reduction from such a problem to one which has a maximum possible problem size couldn't possibly be a valid instance-to-instance reduction, because the former always has (infinitely) more instances than the latter. That's why Sudoku has to be generalized to NxN matrices before one can consider NP-completeness.

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


# Question
Title: how can turing machines be universal models of computation if they can't perform binary search?
I have searched around and it seems like it is impossible for a Turing machine to implement binary search for an arbitrary sized array. How can a turing machine be called universally computable if it can't perform a simple operation other models of computation can do with ease?

# Answer
> 6 votes
Turing Machines can simulate binary search, in the sense that they can compute whatever you can compute using binary search. You seem to be confusing computability and complexity, which are two different things.

Roughly speaking, computability is about what we are able to compute in a given model of computation. We believe Turing machines to be an universal model of computation. All powerful-enough (i.e., Turing complete) models are equivalent to a Turing Machine.

Complexity is about how long it takes to compute something (actually, this is not restricted to time). Different models of computation are not necessarily equivalent complexity-wise.

---
Tags: turing-machines, turing-completeness, binary-search
---


title: data transfer minimization problem

text:
# Question
Title: data transfer minimization problem
You have $2$ computers denoted by $C\_1$ and $C\_2$ and $n$ missions $M\_1,M\_2, \dots M\_n$. Doing the $i$-th mission on $C\_1$ (resp. $C\_2$) costs $a\_i$ (resp. $b\_i$). Moreover if you do $M\_i$ and $M\_j$ are done on different computers. you incur an additional cost of $d\_{i,j}$. I need to find an efficient algorithm that minimizes the cost needed to do all missions.

I know how to solve this problem if all $d\_{i,j}$s are $0$.

I think the solution should use either flow networks or minimal spanning trees.

Thanks in advance.

# Answer
Create an undirected weighted graph $G=(V,E)$ where $V=\\{C\_1,C\_2,M\_1, \dots, M\_n\\}$. For each $i=1,\dots,n$ add the edge $(C\_1, M\_i)$ of weight $a\_i$ and the edge $(C\_2, M\_i)$ of weight $b\_i$. For each pair of distinct indices $i,j=1,\dots,n$ add the edge $(M\_i, M\_j)$ of weight $d\_{i,j}$.

You are looking for a $C\_1$-$C\_2$-cut of minimum weight, namely a partition of $V$ into $A$ and $B$ such that $C\_1 \in A$, $C\_2 \in B$ and the weight of the edges in $E \cap (A \times B)$ is minimized.

Intuitively, $M\_i \in A$ means that $M\_i$ is assigned to $C\_2$ and $M\_i \in B$ means that $M\_i$ is assigned to $C\_1$. To find $(A,B)$ you can use your favorite flow algorithm to compute a maximum flow between $C\_1$ and $C\_2$ in $G$.
> 2 votes

---
Tags: algorithms, graphs, network-flow
---


# Question
Title: Find an upper bound for $T(n)=T(\sqrt{n})+10\log\log n$
I need to find an upper bound for $T(n)=T(\sqrt{n})+10\log\log n$.

I thought first to make a substitution: $m=\log n$. Then: $$ T(2^m)=T(2^{m \over 2})+10\log m $$ Let $S(m)=T(2^m)$: $$ S(m)=S\big({m \over 2}\big)+10\log m $$

Now we can use Master theorem.

Suppose it's the case when $f(m)=O(m^{\log\_2 1-\epsilon})=O(m^{0-\epsilon})$. Let $\epsilon=0.5$ then: $$ \lim\_{n\to \infty}\frac{10\log m}{m^{0.5}}=0 $$ Hence according to the Master theorem $T(m)=\Theta(m^0)=\Theta(1)$.

Am I in the right direction?

# Answer
> 3 votes
We can expand the recursion (ignoring the constant 10) as follows: $$ \begin{align\*} T(n) &= \log \log n + \log \log n^{1/2} + \log \log n^{1/4} + \log \log n^{1/8} + \cdots \\ &= \log \log n + \log \frac{1}{2} \log n + \log \frac{1}{4} \log n + \log \frac{1}{8} \log n + \cdots \\ &= \log \log n + (\log \log n - \log 2) + (\log \log n - \log 4) + (\log \log n - \log 8) + \cdots \end{align\*} $$ At this point, let us notice that the number of terms is roughly the value of $k$ satisfying $n^{1/2^k} = \Theta(1)$, which translates to $\frac{\log n}{2^k} = \Theta(1)$ and so $\log n = \Theta(2^k)$, implying $k \approx \log\_2 \log n = (\log \log n)/\log 2$. Keeping $k$ symbolic at first, we have $$ \begin{align\*} T(n) &= k \log\log n - (\log 2)(0 + 1 + 2 + 3 + \cdots + (k-1)) \\ &= k \log\log n - \frac{\log 2}{2} k(k-1) \\ &\approx k \left(\log\log n -\frac{\log 2}{2} k \right). \end{align\*} $$ Substituting our approximation for $k$, we deduce $$ T(n) \approx \frac{\log \log n}{\log 2} \left(\log\log n - \frac{\log\log n}{2}\right) = \frac{(\log \log n)^2}{2\log 2}. $$ In particular, $T(n) = \Theta((\log \log n)^2)$.

# Answer
> 5 votes
An alternative solution still using domain transformation/change of variables.

$$T(n) = T(\sqrt{n}) + \log \log n$$

### 1. Let $m = \log n$

We can then define a new function $S$ based on how $m$ changes in $T$ and expand it:

$$\begin{align} S(m) &= S\left(\frac{m}{2}\right) + \log m\\ &=S\left(\frac{m}{4}\right) + \log m -1 + \log m\\ & \vdots\\ & = \log^2 m - \sum\_{i = 1}^{\log m} i \\ & = \Theta(\log^2 m) \implies T(n) = \Theta((\log \log n)^2) \end{align}$$

### 2. Let $k = \log \log n$

We can then define a new function $R$ based on how $k$ changes in $T$ and expand it:

$$\begin{align} R(k) &= R(k - 1) + k\\ & = R(k - 2) + k - 1 + k\\ & \vdots\\ & = \Theta(k^2) \implies T(n) = \Theta((\log \log n)^2) \end{align}$$

# Answer
> 1 votes
Suppose $n=2^k.$

By substitution method we can extend the recurrence relation as follow: $$T(n)=T(\sqrt{n})+\log\log n$$ $$=\hspace{4pt} T\left(\sqrt{\sqrt{n}}\right)+\log\log n+10\log\log\sqrt{n}$$ $$=\hspace{4pt} T\left(\sqrt{\sqrt{\sqrt{n}}}\right)+\log\log n+\log\log\sqrt{n}+\log\log\sqrt{\sqrt{n}}$$

$$\dots =\hspace{4pt}T\left(n^{\frac{1}{2^k}}\right)+\log\log n+\log\log\sqrt{n}+\log\log\sqrt{\sqrt{n}}+\dots+\log\log n^{\frac{1}{2^{k-1}}}$$

After simplifying the logarithm terms: $$\dots =\hspace{4pt}T\left(n^{\frac{1}{2^k}}\right)+\log\log n+\log\left(\frac{\log n}{2}\right)+\log\left(\frac{\log n}{4}\right)+\dots+\log\left(\frac{\log n}{2^{k-1}}\right)$$ Next step is trying to find the value $k$: $$ n^{\frac{1}{2^k}}=\mathcal{O}(1)\implies k=\log\log n$$ (In essence, we need the height of recursion tree $\mathcal{T}$ that you can define the height $\mathcal{H}(n)$ of $\mathcal{T}$ as a recursion formula $\mathcal{H} (n)=\mathcal{H} (\sqrt{n})+1$, after solving it you get $\mathcal{H}(n)=\mathcal{O}(\log \log n).$

Finally we can write $T(n)$ as a summation: $$T(n)=\mathcal{O}(1)+\sum\_{i=0}^{\log\log n} \log \left(\frac{\log n}{2^i}\right)$$ $$=\hspace{4pt} \mathcal{O}(1)+\sum\_{i=0}^{\log\log n} (\log \log n- i)$$

$$=\hspace{4pt} \mathcal{O}(1)+\sum\_{i=0}^{\log\log n} i=\theta(\log^2\log n)=\theta(\log\log n)^2$$

---
Tags: asymptotics, recurrence-relation, check-my-answer
---


title: Memory Address Lines

text:
# Question
Title: Memory Address Lines
I am reading a text book by David Tarnoff and there is something I do not understand, the section is on CPU and memory. The book states that the number of address lines going into a memory device determines the number of addresses which makes sense to me, as it says for $n$ address lines going into the device there will be $2^n$ addresses.

What doesn't make sense is this:

> a memory device with 28 address lines going into it has $2^{28}$ = 256 Meg locations. This means that 28 address bits from the full address must be used to identify a memory location within that device. All of the remaining bits of the full address will be used to enable or disable the device.

I do get the concept of the full address but I do not understand how if there are only 28 address lines and each carries one bit, and its a 28 bit address how there can be any more data because there are no more address lines to carry the bits used to enable or disable the device?

In the previous chapter the books also talks about a chip select being used to activate a memory device, but now says that part of the full address is used for this `All of the remaining bits of the full address will be used to enable or disable the device.`

Could somebody help me understand this please?

# Answer
> 1 votes
`if there are only 28 address lines and each carries one bit how there can be any more data?`
I don't read *28 address lines **all told***, but *28 address lines going into one specific memory device*.

`where are the 4 address lines to carry [the 4 bits out of 32 that are used to activate the memory device]?`
There are two answers on the conceptual level:

* A\> Those are the most significant bits
* 1\> As long as the "gaps" in the address space that are *not* handled by the device when not addressed by *contiguous least significant bits* are handled properly, it doesn't matter.
For details on why and how this may be done purposefully, read up on *memory controllers* and interleaved memory.

---
Tags: computer-architecture, cpu, memory-allocation
---


title: FPT algorithm for Knapsack

text:
# Question
Title: FPT algorithm for Knapsack
I tried to search whether Knapsack (the decision version) has a FPT algorithm, but didn't find anything on the topic. Can someone help with a reference?

# Answer
> 3 votes
The reference you should have found is \[1\], where the authors consider several parameters and also higher dimensional knapsack problems (see e.g., Table 1 for a list of running times for different parameters). A non-paywalled version is on arXiv.

---

\[1\] Gurski, Frank, Carolin Rehs, and Jochen Rethmann. "Knapsack problems: A parameterized point of view." Theoretical Computer Science 775 (2019): 93-108.

---
Tags: complexity-theory, np-complete, knapsack-problems, parameterized-complexity
---


title: Hitting set approximation

text:
# Question
Title: Hitting set approximation
I'm having a small problem understanding what is the result of the 4-approximation polynomial-time algorithm for 4-Hitting Set.

What I mean is that by solving 4-Hitting set I get a group X such that all subsets in the universe have a common element with X.

What can I say that the result of the approximation algorithm?

# Answer
Intuitively, the problem here is a minimization problem ("can I find a small bunch of guys from the universe of elements so that it hits all the sets of the input"?) so a 4-approximation will guarantee that the solution set, say $H$, that you find is is at most 4 times larger than the optimal solution. So if the optimal solution was of size 10, then $H$ has size at most 40.

To summarize (based on your comments), if there is no valid solution, the approximation algorithm can't output a valid solution (of any size) either. Otherwise, if there is a solution, the approximation algorithm will output a solution that is *at most* four times the optimal. Note that it is perfectly possible that the solution outputted is optimal, twice the optimal, thrice the optimal, or whatever. The guarantee is that it is *at most* four times the optimal.
> 1 votes

---
Tags: algorithms, approximation
---


title: What is T-star packing

text:
# Question
Title: What is T-star packing
What is a T-star packing and what is Proper Maximal 3-Star Packing? I read some definitions and can't understand

"By a T-star we mean a complete bipartite graph K1,t for some t ≤ T. For an undirected graph G, a T-star packing is a collection of node-disjoint T-stars in G."

# Answer
> 1 votes
So a $t$-star is the graph you get by taking one central node and connecting $t$ neighbors to it. Equivalently, a $t$-star is the complete bipartite graph $K\_{1,t}$ if you wish to express it like that as your definition does.

A *$t$-star packing* then is a bunch of such $t$-stars found from some graph $G$ so that their nodes don't overlap. As a simple example, consider the 4-cycle. You can find a 1-star packing of size 2 in it: take one edge as the other 1-star, and the other edge as the other 1-star.

The packing described above is *maximal*: you can't extend it by adding a new member (i.e., a third 1-star) into it. It also happens to be *maximum*, i.e., it is the largest such packing you can find. I encourage you to think about what the difference between a *maximal* and *maximum* packing is, i.e., find an example where they differ.

I don't what *proper* here means, but it is likely defined in your source.

---
Tags: parameterized-complexity
---


# Question
Title: please help me understand the algorithm for building the KMP failure function
I am struggling to grasp the algorithm for building the KMP failure function. The bulk of what is making my understanding incomplete concerns the line `length=PI[length-1]`. There is the psuedo code for the algorithm below. Here are my questions:

1.) How do we know that in the event `s[i] != s[length]`, the best possible option for our candidate prefix length is `PI[length-1]`?

2.) If the candidate `PI[length-1]` fails, and on the next iteration of the while loop, we must go to `PI[PI[length-1]-1]` how do we know that the best possible candidate length is not actually BETWEEN `PI[length-1]` and `PI[PI[length-1]-1]`?

3.) When `s[i]!=s[length]` how do we know there does not exist a suffix(that matches a prefix) that ends at `s[i]` and that begins at a point in the string PRIOR to `i-length`?

I think my confusion could best be cleared by short informal proofs.

```
function f(string s):

PI = an array of integers with size equal to length of s

length=0
i=1

while i < the length of the s:
    if s[length] == s[i]:
        length+=1
        PI[i]=length
        i+=1
    else:
        if length!=0:
            length=PI[length-1]
        else:
            PI[i]=0
            i+=1
return PI

```

Thank you!

# Answer
The failure link at a certain position $k$ in the string points to the longest prefix of the string which is also a suffix of the string *before* the position $k$.

The first observation we need is that in fact *all* the prefixes that are suffixes at that point can be found using repeatedly following the failure links. This implies that there are no positions in between.

So, if $k$ points to $t\_0$ then the string indicated by $(0)$ in my diagram is the prefix/suffix at $k$. The next prefix that is also a suffix at $k$ is $t\_1$ the failure link at $t\_0$. The reason is that the two strings $(1)$ at the prefix match (by definition of failure link at $t\_0$) but can also be found as $(1')$ at the end of the suffix. Thus, any prefix/suffix at $t\_0$ must also be a prefix/suffix at $k$.
> 2 votes

---
Tags: algorithms, strings, string-matching
---


title: array empty cell search algorithm

text:
# Question
Title: array empty cell search algorithm
I'm Telecommunication student so I don't have Computer Science background, just in case if my question looks stupid.

Here is my scenario:

1. Consider an empty array named `ARR` with size `N`, we also have an array named `MAP` with size `N` that stores the state of `ARR` cells, `ON` for filled, `OFF` for empty, initially `ARR` is empty so every corresponding cell in `MAP` is set to `OFF`.
2. we keep the next empty cell index in a variable named `NEXT`, initially since `ARR` is empty, `NEXT` is set to 0. `NEXT` always point to the first index `i` in the array `MAP` such that `MAP[i]` is `OFF`, if any exists.
3. a function named `add(element)` always adds element into `ARR` at index `NEXT`, sets corresponding cell in `MAP` to `ON`.
4. a function named `insert(element, index)` adds element into `ARR` at index specified by user, sets corresponding cell in `MAP` to `ON`.
5. a function named `delete(index)` removes element from `ARR` at index specified by user, sets corresponding cell in `MAP` to `OFF`.

My question: How to update `NEXT` variable so it points to next empty cell index in `ARR`.

I know I can run a search on `MAP` from 0 to N and stop at the first occurrence of `OFF` and store its index as `NEXT`, but from what I read from online sources it has O(N) performance which is not great, I want to know if there are any better algorithms for this job or not, if not, can I design one myself? which books/online doc should I look into?

Thanks.

# Answer
> 2 votes
I'm assuming that you're on a RAM machine with word size $\Theta(\log N$). Keep a van Emde Boas tree $T$ storing the empty positions (integers from $1$ to $N$).

Whenever you insert an element $i$, delete $i$ from $T$ (in $O(\log \log N$) time) and set `NEXT` to the minimum element in $T$ (in $O(1)$ time).

Whenever you delete an element $i$, insert $i$ to $T$ and set `NEXT` to the minimum between the current values of `NEXT` and $i$.

This requires $O(\log \log N)$ time per operation but would require time $O(N \log \log N)$ to build the tree. To improve the construction time to $O(N)$ you can start with a tree containing only the index $1$. Then during the first $N-1$ operations do the following: before the $i$-th operation is performed check if `MAP[i+1]=OFF`. If this is the case, then add $i+1$ to $T$. Proceed with the operation normally. This is taking advantage of the fact that, after the $i$-th operation is performed, we must necessarily have `NEXT<=i+1`.

You can't get much better solutions since you essentially need to solve the predecessor problem which admits a lower bound of $\Omega( \frac{\log \log N}{\log \log \log N})$ for a word size of $\Theta(\log N)$.

For a slower but easier to implement solution replace the van Emde Boas tree with an AVL tree. The initial tree can be built in $O(N)$ time (the keys are sorted) and each operation requires $O(\log N)$ time.

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


# Question
Title: Sum of squares of length of longest common prefix for all pairs in given strings
Given a list of unique strings, how can I find the sum of squares of longest common prefixes length for all pairs? I think a trie will be useful but I'm not sure how to calculate the final result.

For example, if given strings are **and**, **anacron**, **anagram**, **build** and **buffer**

Then possible pairs are (and, anagram) which will give 2 as the length of common prefix and squaring it we will get **4** similarly, for (anagram, anacron) we will get 3 common prefixes and we will add **9** and (and, anacron) will give **4**, (build, buffer) will give **2** Other possible pairs will have 0 common prefixes hence they do not contribute. So the final answer will be 4+9+4+4 = 21.

I assume adding the length of squares and not the original length is a key to calculate the result.

# Answer
> 2 votes
I'm assuming you are interested in going over all unordered pairs of distinct words in your given set of words $S$, a collection I denote by $S\_2$.

You can augment a trie for $S$ with a count of the words extending each node. Suppose that a node $v$ corresponds to a prefix of length $|v|$, and has $n(v)$ words extending it. Using $v \preceq x$ to denote "$v$ is a prefix of $x$" and $c(x,y)$ to denote the size of the largest common prefix of $x,y$, for any function $f\colon \mathbb{N} \to \mathbb{R}$ we have $$ \sum\_v f(|v|) \binom{n(v)}{2} = \sum\_v \sum\_{\substack{\\{x,y\\} \in S\_2 \\ v \preceq x,y}} f(|v|) = \sum\_{\\{x,y\\} \in S\_2} \sum\_{v \preceq x,y} f(|v|) = \sum\_{\\{x,y\\} \in S\_2} \sum\_{\ell=0}^{c(x,y)} f(\ell). $$ In your case, you are interested in finding a function $f$ such that for all $n \in \mathbb{N}$, $$ \sum\_{\ell=0}^n f(\ell) = n^2. $$ Clearly $f(0) = 0$ and for $\ell \> 0$, $f(\ell) = \ell^2 - (\ell-1)^2 = 2\ell-1$.

---
Tags: data-structures, strings
---


# Question
Title: Satisfiable CNFs where each clause contains logarithmically many different literals
Studying for my finals in Complexity theory. This question comes up in different variants and it requires to use probability.

A side note before, to be more clear: A CNF clause consists of $n$ clauses $C\_i$, so $\varphi=C\_1\wedge\dots \wedge C\_n$, and each $C\_i$ has some amount of literals $l\_1^i,\ldots ,l\_m^i$, so $C\_i=l\_1^i\vee\dots \vee l\_m^i$, and each $l\_i$ is some variable $x$ or its negation $\lnot x$.

> Let $L$ consist of all satisfiable CNFs $\varphi$ such that each clause of $\varphi$ contains at least $\log\_{2}\left(|\varphi|\right)$ different literals.
>
> Prove that $L\in P$.

I know that we could write a Turing machine $M$ on $\langle \varphi\rangle$ go over each clause in $\varphi$ and count the number of literals. If it's less than $\log\_2\left(|\varphi|\right)$ then reject. Otherwise accept. Of course this machine is polynomial. But we need to prove: $L(M)=L$.

Over the course, they showed a way to use probability. A similar question was given:

> Given a 3CNF clause $\varphi$ **in which every clause consists of different variables**, at least $\frac{7}{8}$ of the clauses can be satisfied simultaneously.
>
> This idea was used to prove that the language $L'$ of all $\varphi\in 3SAT$ in which each clause contains different variables such that there exist an assignment that satisfies $7/8$ of the clauses is in $P$.

So I tried to prove my main task and I would love some feedback.

We want to calculate the probability of $\varphi\in CNF$ so each clause in it, contains **exactly** $\log\_{2}\left(|\varphi|\right)$ literals, to be satisfied.

We will define a probability space where each assignment for $\varphi$'s variables is selected with a uniform probability. For each clause $C\_k$ we will define the following indicator: $$ \mathbb{I}\_{k}\triangleq\begin{cases} 1 & z\left(C\_{k}\right)=T\\ 0 & \text{otherwise} \end{cases} $$ So we get: $$ E\left(\mathbb{I}\_{k}\right)=0\cdot P\left(\mathbb{I}\_{k}=0\right)+1\cdot P\left(\mathbb{I}\_{k}=1\right)=P\left(\mathbb{I}\_{k}=1\right) $$ Let's calculate the probability of $P\left(\mathbb{I}\_{k}=1\right)$. Let's look at $C\_{k}=\left(l\_{1}^{k}\vee\ldots\vee l\_{\log\_{2}\left(|\varphi|\right)}^{k}\right)$ where **all the literals are independent** and we will calculate the probability of $z$ being $z\left(C\_{k}\right)=T$.

Let's define $\Omega$ to be all the possibilities. So we get $|\Omega|=2^{\log\_{2}\left(|\varphi|\right)}=|\varphi|$ (since the literals are independent).

Let's define $A$ to be all the possibilities so we get true. This means that at least one of the literals should return true. So we get $|A|=|\varphi|-1$.

Since this is an equal probability space we will get: $$ P\left(A\right)=\frac{|A|}{|\Omega|}=\frac{|\varphi|-1}{|\varphi|} $$

Now we get $P\left(A\right)\leq P\left(\mathbb{I}\_{k}=1\right)$ (since literals are not necessarily independent). Then we get: $$ E\left(\mathbb{I}\_{k}\right)=P\left(\mathbb{I}\_{k}=1\right)\geq\frac{|\varphi|-1}{|\varphi|} $$ Lets mark $t$ to be the number of clauses in $\varphi$. Also, lets mark $X=\sum\_{k=1}^{t}\mathbb{I}\_{k}$ So we get: $$ E\left(X\right)=E\left(\sum\_{k=1}^{t}\mathbb{I}\_{k}\right)=\sum\_{k=1}^{t}E\left(\mathbb{I}\_{k}\right)\geq\sum\_{k=1}^{t}\frac{|\varphi|-1}{|\varphi|}=\frac{|\varphi|-1}{|\varphi|}t=t\cdot\left(1-\frac{1}{|\varphi|}\right) $$

From this we can conclude that there is necessarily an assignment that satisfies $t$ clauses from $\varphi$ and therefore it satisfies $\varphi$, i.e. $\varphi \in SAT$.

Since this question comes very often in the finals, I want to make sure I understand each step. So the things I'm not sure about:

1. I'm not sure that my statement of $P\left(A\right)\leq P\left(\mathbb{I}\_{k}=1\right)$ is being true. I'm not sure how to calculate the probability if the literals are not independent. From the question, they should be different, but I could have $x$ and $\lnot x$ in the same clause, and they are of course dependent.
2. The question asks about "at least $\log\_{2}\left(|\varphi|\right)$" and I talked about "exactly $\log\_{2}\left(|\varphi|\right)$".
3. What do I actually get out of proving that $E\left(X\right)\geq t\cdot\left(1-\frac{1}{|\varphi|}\right)$?

# Answer
The claim is false.

Let $\varphi = (x\_1 \vee x\_2) \wedge (\overline{x}\_1 \vee x\_2) \wedge (x\_1 \vee \overline{x}\_2) \wedge (\overline{x}\_1 \vee \overline{x}\_2)$. Here $|\varphi|=4$, each clause in $\varphi$ contains exactly $\log\_2 |\varphi|=2$ distinct literals, yet $\varphi$ is not satisfiable. (This is also a counterexample if $|\varphi|$ denotes the number of variables).

You have an error in your proof when you observe that $$ \mathbb{E}\[X\] \ge |\varphi| \cdot \left(1-\frac{1}{|\varphi|}\right) = |\varphi|-1, $$ and use it to conclude that there must be a truth assignment that satisfies all the $|\varphi|$ clauses. You can only conclude that there must be a truth assignment that satisfies $|\varphi|-1$ clauses (you are using the fact that $\max \\{y\_1, \dots, y\_k\\} \ge \frac{1}{k} \sum\_{i=1}^k y\_k$, this is false in general if $\ge$ is replaced with $\>$).
> 3 votes

# Answer
You haven't explained what $|\varphi|$ is, so let's guess that it is the number of clauses. So you are given a CNF $C\_1 \land \cdots \land C\_n$ in which each clause contains at least $\log\_2 n$ distinct literals.

Any clause which contains both a variable and its negation is always satisfied, so we can remove such clauses; call them *spurious*. Suppose that the remaining clauses are $C\_1,\ldots,C\_m$, where $m \leq n$.

If you choose a random truth assignment, then the probability that it falsifies a non-spurious clause containing $k$ different literals is exactly $2^{-k}$. This means that a random truth assignment falsifies each of $C\_1,\ldots,C\_m$ with probability at most $2^{-\log\_2 n} = 1/n$, and applying a union bound, this shows that the probability that a random truth assignment falsifies at least one of $C\_1,\ldots,C\_m$ is at most $m/n$. If $m \< n$, this means that the CNF is satisfiable, since a random truth assignment satisfies it with positive probability.

If $m = n$ then this argument no longer works, and indeed you can construct counterexamples, such as: $$ x\_1 \land \lnot x\_1 \\\(x\_1 \lor x\_2) \land (\lnot x\_1 \lor x\_2) \land (x\_1 \lor \lnot x\_2) \land (\lnot x\_1 \lor \lnot x\_2) $$

First of all, let us note that if *any* of the clauses $C\_1,\ldots,C\_n$ contains more than $\log\_2 n$ variables, then the argument above does show that a random truth assignment satisfies the CNF with positive probability. Hence $k = \log\_2 n$ must be an integer, and each clause contains *exactly* $k$ literals. Thus the probability that a random truth assignment falsifies each of $C\_1,\ldots,C\_n$ is exactly $1/n$, and so the expected number of falsified clauses is exactly $1$.

Since the expected number of falsified clauses is exactly $1$, the CNF is unsatisfiable iff *every* truth assignment falsifies *at most* one clause. Equivalently, the CNF is unsatisfiable iff every two clauses $C\_i,C\_j$ cannot be falsified simultaneously. A short argument reveals that the latter condition holds precisely when there is some literal $\ell \in C\_i$ such that $\lnot \ell \in C\_j$, a condition which is easily checked.
> 3 votes

---
Tags: complexity-theory, logic, probability-theory, polynomial-time
---


title: Convert the given NFA to DFA

text:
# Question
Title: Convert the given NFA to DFA
I am trying to find an DFA for the regular language given by the expression $L\left( aa^{\ast }\left( a+b\right) \right)$.

First simplifying $L\left( aa^{\ast }\left( a+b\right) \right)$ we get

$L\left( aa^{\ast }\left( a+b\right) \right)$ $= L\left( a\right) L\left( a^{\ast }\right) L\left( a+b\right) $

Then I constructed an NFA for it , which is given below :

But I am not able to simplify the above NFA to a DFA as the state $q\_1$ has two $\lambda$ transitions and I am not understanding how to deal with them .

# Answer
> 2 votes
After simplifying $L(aa^∗(a+b))$ to $ L(a^+(a+b))$ you can draw below $DFA$ for $L$.

# Answer
> 0 votes
See this page.

Essentially, create a new DFA $D$ in which the set of states $Q$ is the powerset of the set of states of your NFA $N$. For $q \in Q$ and $a \in \Sigma$, add transition $\delta(q,a) = q'$ to $D$, if and only if, the set of states of $N$ that are reachable (in $N$) from at least one state in $q$ by reading character $a$ is exactly $q'$.

Mark a state of $q \in Q$ as a final state in $D$ if and only if $q$ contains a final state of $N$. If $q\_0$ is the initial state of $N$, then the initial state of $D$ is the set of states if $N$ that are reachable by $q\_0$ using only $\varepsilon$-transitions.

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


# Question
Title: What is the primary reference for the observation/discussion of how neural networks struggle with ambiguous training datasets?
It is known that neural networks, such as convolutional neural networks, struggle with pattern recognition if training sets contain ambiguities (i.e. several labels can correspond to one and the same pattern). However, I struggle to locate the paper that directly discusses this issue, or demonstrates it for the first time, etc. If anybody can point me to the paper(s), that would really help. Thanks!

# Answer
Traditional *single-label* classification implies disjoint labels. To the extent that labels are *not* disjoint or distinct within a single-label classification task, the problem is one of the definition of distinct *concepts*. This problem has been discussed as early as 1984 in Valiant's "A Theory of the Learnable" where he identified the theoretical limits of a class of learnable concepts that can be approximated in polynomial time via a deductive procedure.

On the other hand, labels can have a many-to-one relationship for images in *multi-label* datasets. The use of the word "ambiguities" implies incorrect, incomplete, or indeterminate mapping of labels in the training dataset. Note: A probabilistic or hierarchical label assignment is often used to quantify or qualify the class status and thus reduce errors related to labeling.\[1\]

Two of the main sources of label ambiguity can generally be divided into *label noise* and *label redundancy*.

**Label noise** refers to errors in labeling or the description of instances. "Classification on Soft Labels is Robust against Label Noise", (Thiel, 2008) includes several references to the problem in CNNs. An earlier paper "Reducing correspondence ambiguity in loosely labeled training data" (Barnard and Fan, 2007) addresses the issue of correspondence ambiguity and the use of *soft labels*:

> The training data available for a specific classification task must not necessarily be labeled hard. That is, a training sample might belong, to different degrees, to multiple classes simultaneously. For example, multiple experts might not agree on the diagnosis for the sample, or hear different emotions in a spoken sentence. In fact, problems in the field of medical or life sciences, like predicting the secondary structure of proteins, often produce and require soft labels.

The theoretical consequence of label noise on generalization error was given by Vapnik and Chervonenkis (1971) in the Universal Estimate Rate bound. For $f$ features of $m$ data points in a $L$ learner applied to a training set $S$:

> *With high probability, the generalization error of the hypothesis $h = L(S)$, given by $L$ applied to $S$ (unrestricted to any feature subset), is bounded by:*
>
> $$ \epsilon(\hat{h}) \leq \epsilon\_g (f) + \mathcal{O} \Big( \sqrt{\frac{f\_{VC}}{(1-2\eta)^2m}\Big(log \frac{m}{f\_{VC}}+1\Big)} \Big) $$ \[...\] *when the training data have independently been corrupted at some noise rate $\eta$ \[...\]*.

**Label redundancy** is first mentioned by Zhao (2008) in "Adding Redundant Features for CRFs-based Sentence Sentiment Classification". *Label semantic redundancy* (eg, *cat* and *kitten* often refer to the same thing) is addressed in several papers related to multi-class classification. For example, it can be exploited by joint image/label embedding.\[3\]
> 2 votes

---
Tags: data-structures, machine-learning, reference-request, neural-networks, ambiguity
---


# Question
Title: M does not accept [M] | 'Correction' of proof possible?
The language $D=\\{\[M\]|M(\[M\])=0\\}$ is not decidable because of the following argument:

Suppose there was a $TM \space M\_D$ that decides $D$. Then if we gave $M\_D \space \[M\] $, there would be two possible outcomes:

**1.** $M\_D(\[M\_D\])=1 \text{ (accepts)}\implies M\_D \text{ does accept }M\_D $, contradiction, because then $M\_D(\[M\_D\])=0$ must be true.

**2.** $M\_D(\[M\_D\])=0 \text{ (does not accept})\implies M\_D \text{ does accept }M\_D $, contradiction, because then $M\_D(\[M\_D\])=1 $ must be true.

Anyways, I think most people are familiar with the proof.

**My question is:**

Where does the following argument fail? (I think this is important to understand other proofs where diagonalization is involved)

Suppose we have a $TM$ $M\_D$ that decides if another $TM \space M$ does not accept $\[M\]$. What if we just restrict $M\_D$ so that it decides D for **almost** every other Turing Machine? So in this case we could say: $M\_D$ does not decide for itself if $M\_D$ accepts $\[M\_D\]$, but it decides for every other Turing Machine.

Is this restriction useless because then it is possible to construct infinitely many Turing Machines for which $M\_D$ can not decide whether they accept 'themselves'?

# Answer
Even with your restriction $D$ is undecidable. You can still reduce the halting problem of a TM $A$ on a word $x$ to $D$. Construct a TM $B$ that simulates $A$ on $x$. If $A$ halts, $B$ accepts its input. Otherwise $B$ runs forever. Clearly then $A$ halts on $x$ iff $B \not\in D$. Note that you can always construct $B$ such that $B \neq M\_D$ by performing additional, irrelevant steps.
> 1 votes

---
Tags: turing-machines, undecidability, proof-techniques, decision-problem, diagonalization
---


title: Why is the manifold hypothesis true?

text:
# Question
Title: Why is the manifold hypothesis true?
The manifold hypothesis is the statement that real-world high dimensional data (such as images) lie on low-dimensional manifolds embedded in the high-dimensional space. It has been tested to be true quite extensively. So could someone explain or give some intuition why it is true? Why doesn't real world data such as dogs form manifolds of same dimension as the image space?

# Answer
Presumably you don't *really* get a manifold.

For one thing, there's probably a nonzero chance of any particular coordinate being perturbed arbitrarily -- an impurity in a crystal, a grey hair on a head of brown ones, etc. -- so you'd really get something more like a probability distribution concentrated near a lower dimensional platonic ideal.

Second, there are probably all sorts of behaviors going on that aren't allowed in a manifold, like self-intersections, edges, and components of different dimensions.

That said, simple statements like "the left side of someone's face usually looks about like the mirror image of the right" cut the dimensionality of the space nearly in half. Add enough such independent conditions and you whittle things down quite a bit.
> 9 votes

# Answer
You know what they say about big hands? Big feet!

Correlations abound in real high-dimensional data. For instance, if our data set were 206 "length" measurements of human bones, we would definitely discover a correlation between the features.

In terms of images, similar colors tend to be around similar pixels, with "zero-dimensional" borders being the exception (zero-dimensional wrt to image, in that a border is a line in a plane). Consider that a random image would be static. In other words, the implicit organization of data that we are interested in forms a manifold in its space.
> 6 votes

# Answer
The manifold hypothesis is perhaps best seen as a *heuristic*. The practical observation is that dimension reduction often works well, particularly with sufficiently dense samples.

Intuitively, **extrinsic dimensionality** of a dataset often exceeds **intrinsic dimensionality** of an underlying phenomena. We tend to collect more data than is needed to identify a pattern. For example, one can often recognize a friend from far away, just based on a single feature, such as their posture or clothing style alone.

See Mathew Bernstein's post "Intrinsic dimensionality" for an explanation. An explanation of manifold learning in the context of neural networks is available at Colah's blog.

You mentioned it has been tested to be true extensively. A mathematical proof *under certain strict conditions* was given in "Testing the Manifold Hypothesis", a 2013 paper by MIT researchers, where the statistical question is asked

> What is the number of samples needed for testing the hypothesis that data lie near a low dimensional manifold?. The desired result is that the sample complexity of the task depends only on the "intrinsic" dimension, volume, and reach, but not the “ambient” dimension. We approach this by considering the empirical risk minimization problem.
>
> \[...\] The answer to this question is given by Theorem 1 in the paper. The proof of the theorem proceeds by approximating manifolds using point clouds and then using uniform bounds for k-means (Lemma 6 of the paper).

The results of this proof of course do not imply that every pattern can be seen in any lower dimensional representation. Rather, the hypothesis is merely intuitively apparent when the number of degrees of freedom exceeds the empirically determined intrinsic dimensionality.
> 4 votes

# Answer
The low dimensional structures come from constraints of physical world / physics laws. So Nature is helping us a lot...

Can we consider manifold hypothesis to be a mathematical conjecture?
> -2 votes

---
Tags: neural-networks
---


# Question
Title: Showing asymptotic lower bound on log of recurrence
I'm trying to prove a lower bound on some computational problem, but in order to do it, I need an $\Omega(n\log(n))$ lower bound on $\log(T(n))$, where $T(n)$ is a recurrence defined as follows:

$T(1) = 1$

$T(n) = \sum\_{k=1}^{n-1} T(k)T(n-k)$

Does this recurrence have a known solution? If not, just giving a lower bound on $\log(T(n))$ would suffice for me. Optimally, I would want an $n\log(n)$ bound, but I don't know if its possible to achieve. So, any lower bound bigger than a linear one would be appreciated! Thanks in advance for helping me out!

# Answer
> 2 votes
Your sequence $T(n)$ is, in fact, the Catalan numbers, as show on *the On-Line Encyclopedia of Integer Sequences*. You can also take a look at the Wikipedia article on Catalan numbers, which shows its many applications in combinatorics.

$$T(n)=C(n-1)=\frac{(2(n-1))!}{n!(n-1)!}\sim \frac{4^{n-1}}{n^{3/2}\sqrt{\pi}}.$$

In particular, $$\log T(n) = (n-1)\log 4 - \frac32\log n - \frac12\log\pi + o(1),$$ or,$$\log T(n) \sim n\log 4.$$

# Answer
> 1 votes
The lower bound of your recurrence is not $\Omega(n\log n)$, because:

1. We prove that the lower bound of your recurrence is $\Omega(2^n).$

Suppose $T(n)\geq c2^n$. Then:

$$ \sum\_{k=1}^{n-1} T(k)T(n-k)\geq c2^n$$ $$=\sum\_{k=1}^{n-1}\hspace{4pt} c2^kc2^{n-k}\geq c2^n$$ $$=\sum\_{k=1}^{n-1}\hspace{4pt} c^22^n\geq c2^n$$ $$=\hspace{4pt} (n-1)c^22^n\geq c2^n.$$

So the lower bound of your recurrence $T(n)=\Omega(2^n).$ Consequently, $$\log T(n)=\Omega(n).$$

Because of your recurrence relation is $C\_{n-1}$ nth Catalan number of Catalan numbers, then by reading this post we can find the exact solution of your recurrence is:

$$C\_{n-1}=\frac{1}{n}\binom{2n-1}{n-1}$$

That $$C\_{n-1}\leq 4^n$$ So $\log 4^n=\mathcal{O}(n).$

---
Tags: recurrence-relation, lower-bounds
---


# Question
Title: Understanding IBM370 Relaxed Memory Consistency
In the report "Shared Memory Consistency Models: A Tutorial" (https://www.hpl.hp.com/techreports/Compaq-DEC/WRL-95-7.pdf), the authors explain the difference between IBM370, Total Store Ordering, and Processor Consistency via Figure 10 (shown below).

I do not understand why the results for (a) are not possible with IBM370. The report mentions that

> these models ... allow a read to be reordered with respect to previous writes from the same processor

(with different addresses). The IBM370 model

> prohibits a read from returning the value of a write before the write is made visible to all processors.

I think this means that for the program in (a), P1's read on A must wait for P1's earlier write to A to become visible to P2 before returning. I do not understand how this prevents P1's write to register2 to be reordered to execute before P1's write to Flag1 (which makes the result possible), as described by Figure 10's caption.

# Answer
Good question.

So with TSO loads to a different address can't be reordered (in the global memory order) unless the earlier load can be satisfied by a store in the store buffer and the second load can't. Keep in mind that a load can only be ordered in the global memory order (globally performed) after the store it reads from.

Let have a look at this simple example.

```
A=B=0

CPU1:
   A=1
   r1=A
   r2=B

CPU2
   B=1
   r3=B
   r4=A

```

Is it possible to end up with r1=r3=1 and r2=r4=0?

Yes, because the load of r1 is a load which can be satisfied from the store buffer and the load of r2 from the cache. So they can be reordered in the global memory order. And the same goes for r3/r4.

With IBM 370 a load that could be satisfied by a store in the store buffer needs to wait for the store to be globally visible. Of course the load will still see the same value as with TSO; so what is the point? Well, it will make sure a subsequent load that is loaded from the cache, is globally ordered after the earlier load that could have been satisfied from the store buffer.

```
A=B=0

CPU1:
   A=1
   r1=A
   r2=B

CPU2
   B=1
   r3=A
   r4=B

```

As a consequence: with IBM 370, the loads can't be reordered. And it is impossible to end up r1=r3=1 and r2=r4=0.

So TSO will give a total order over the stores. I believe that IBM 370 will also give you a total order over the loads; the order of loads in the memory order is consistent with the order of loads in the program order.

Lets go back to the example (a). For TSO this would be a possible memory order that explains the results.

1. P1:register2=flag2 (0)
2. P2:register4=flag1 (0)
3. P1:flag1=1
4. P1:A=1
5. P1:register1=A (1)
6. P2:flag2=1
7. P2:A=2
8. P2:register3=A (2)

The trick is with the 2 loads at the end of P1/P2. They have been ordered to the beginning of the memory order since they have a preceding loads that can be satisfied by the store buffer.

With IBM 370 load/load reordering isn't possible. So it is impossible to find a memory order that will be consistent with IBM 370.

PS: I'm no authority, so best to recheck my answer :) I'm also studying this part myself.
> 1 votes

---
Tags: computer-architecture, shared-memory
---


title: "Polynomial Counter" Turing Machine

text:
# Question
Title: "Polynomial Counter" Turing Machine
I need some help with this question:

Definition: A Turing-machine that is a counter for the language $L$ is called *'polynomial counter'* if there exists a polynomial $p$ s.t. **every** word $w\in L$ appears on the machine's tape starting from the $p(|w|)$ cell at most (that is, the first letter of $w$ is at cell $p(|w|)$ or before it).

Assuming that $P\neq NP$ prove/refute the following statement: If $L\in P$ then there exists a polynomial counter for $L$.

My intuition was to prove this due to the fact that we can arrange all words of $\Sigma^\*$ in a lexical order and then in a polynomial time (since $L\in P$) check if $w \in L$. However, it is just a basic intuition.

Thank you

PS: it is worth mentioning that for a counting Turing Machine there is an output tape which is a write only tape and thus the words of L keeps accumulating on this tape one after the other.

# Answer
Assuming words cant overlap, we will prove that the statement is false. Lets try to think about $\Sigma^\*$ and see what happens (since as you said, it could be used to create a polynomial counter for all other languages in $P$).

Without loss of generality, we can assume that the polynomial counter will contain the words in increasing lexicographical ordering (why? try to prove this fact!)

So, let us take a look at a word $w$ with length $k=|w|$. We know that all words $w'\preceq w$ ($w'$ is lexicographically smaller than $w$) must come *before* $w$ on the tape. How many of them are there? at least $2^{k-1}$ such words exist (since $2^{k-1}$ is the number of words with length $k-1$). Even if all of those words were by any chance one letter long (which they aren't, they are $k-1$ letters long), that will still take up an entire $2^{k-1}$ cells. Therefore, $w$ can appear *only after* at least $2^{k-1}$ cells.

Clearly, $2^{k-1}$ is **not** polynomial in $k=|w|$, and hence there doesn't exist a polynomial counter for $\Sigma^\*$
> 1 votes

# Answer
The following assumes that words cannot overlap on the output tape.

Let $\Sigma=\\{0,1\\}$, pick $\Sigma^\* \in \mathsf{P}$ as your language and suppose that there is a polynomial counter $T$ for $\Sigma^\*$. Let $p(|w|) = |w|^{c\_1} + c\_2$ with $c\_1, c\_2 \ge 0$ be a polynomial for such that a word $w \in L$ starts in position at most $p(|w|)$ on the output tape of $T$.

Let $W= \langle w\_1, w\_2, \dots, \rangle$ be the list of the distinct words from $L$ that are written on the tape by $T$, in order.

For every $h = 0, 1, \dots$ let $L(h) = \sum\_{i=1}^{h} |w\_i|$. We must have: $$ p(|w\_h|) \ge L(h-1). $$

Suppose that, for some indices $i \<j$, we have $|w\_i| \> |w\_j|$. Then by swapping $w\_i$ and $w\_j$ in $W$ we would still obtain a list $W'$ that satisfies the above property. Formally, let $w'\_h = w\_h$ if $h \not\in \\{i, j\\}$, $w'\_i = w\_j$, $w'\_j = w\_i$, and let $L'(h) = \sum\_{i=1}^{h} |w'\_i|$. For $h \< i$ we have $L'(h)=L(h)$, for $h=i, \dots, j-1$ we have $L'(h) = L(h) - |w\_i| + |w\_j| \< L(h)$, and for $h \ge j$ we have $L'(i)=L(i)$. Therefore, for $h \not\in {i,j}$: $$ p(|w'\_h|) = p(|w\_h|) \ge L(h-1) \ge L'(h-1). $$ Moreover, since $i\<j$: $$ p(|w'\_i|) = p(|w\_j|) \ge L(j-1) \ge L'(j-1) \ge L'(i-1). $$ Finally: $$ p(|w'\_j|) = p(|w\_i|) \ge p(|w\_j|) \ge L(j-1) \ge L'(j-1). $$

This allows us to assume, without loss of generality, that the words in $W$ appear in non-decreasing order of their length. Since $W$ must contains all words from $\Sigma^\*$, the length of $w\_h$ and the length of the $h$-th word from $\Sigma^\*$ (in lexicographic order) must coincide.

Let $\ell \> 2$ be a sufficiently large integer and define $k = 2^\ell$.

There are $2^0 + 2^1 + \dots + 2^{\ell-1} = 2^\ell - 1 = k-1$ words of length at most $\ell-1$ in $\Sigma^\*$, and their total length is: $$ \sum\_{i=0}^{\ell-1} i \cdot 2^i = \ell \cdot 2^\ell - 2 \cdot2^{\ell} + 2 \> 2^{\ell}. $$

The length of the $k$-th word $w'$ in $\Sigma^\*$ is $\ell$. Therefore we must have also $|w\_k| = \ell$ and we can write: $$ \ell^{c\_1} + c\_2 = p(\ell) = p(|w\_k|) \ge L(k-1) = \sum\_{i=1}^{k-1} |w\_i| = \sum\_{i=0}^{\ell-1} i 2^i \> 2^\ell. $$

By choosing a sufficiently large value of $\ell$ you get a contradiction.
> 1 votes

---
Tags: complexity-theory, turing-machines, time-complexity, polynomial-time, p-vs-np
---


# Question
Title: Finding an unknown point on an infinite number line
Given a number line from $-\infty$ to $\infty$, there exists a point $P$ on the line. We need to find the minimum number of steps to get to $P$ subject to the following constraints:

1. The value of $P$ is not known.
2. At a time you can only move one step either backward or forward. For example: if you are currently at 1, you can either go to 0 or 2 but not to -1 or 3 directly.

According to me, if $P$ were known then we could see what indices are reachable from $P$, and then choose the one that is closest to it. But because this is an infinite number line, and since we don't know what the value of $P$ is, I am not able to come up with any suggestions and would appreciate if I could get some tips.

# Answer
Your problem is known as the cow path problem. You can find many online resources explaining how to solve it, for example this page on *Algorithms Notes*.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Finding an optimal solution in a tile painting game
## The Problem

Find the shortest sequence of moves that makes up the optimal solution of a level. If there is more than one optimal solution, just find one of them.

## Game Rules

The game level is made up of two types of tiles: walls and floors. The player's task is to paint the whole level using a ball that can be moved in four directions (up, down, left, right). When a direction is chosen, the ball will move in the indicated direction until it hits the wall (it cannot be stopped midway).

The tile the player starts on is automatically painted at the beginning of the game.

There are many games of this type on the Google Play store like *Amaze!* by *Crazy Labs* or *Roller Splat!* by *VOODOO*.

Here's one you can play in a browser.

## Example

Here is an example of a very simple game level.

The optimal solution requires 3 moves: ↓, →, ↑.

## Helper Graph

For each level it is possible to create a graph showing in which positions the player can find themselves after a move and in which directions they can move the ball.

For the level above, the graph looks like this, where S is the initial position.

This is how a graph looks overlaid on a level.

These graphs are directional, you can't always go directly back to the previous position.

In the example below, if the player moves the ball to the right and then moves left, they will find themselves at a different vertex of the graph than the initial one.

## Solution attempt

The simplest solution is to search all possible paths and choose the shortest one. The maximum length of the solution must be limited to avoid an infinite loop.

Using the DFS algorithm, search through all possible paths:

1. Starting from the spawn position, branches are created to look for a solution in every possible direction.
2. A branch reaches a vertex of the graph, chooses one of the possible directions to go and continues exploring. From the same vertex new branches that will look for a solution in every other possible direction are created.
3. When a branch passes through all the floor tiles of the level, it ends its exploration. The solution found is saved if it is better than the previous best solution.
4. If the length of the branch's solution exceeds the length limit, it gets disposed of.

This algorithm allows to find a solution of levels, but only with a length limit of no more than 12 steps. The complexity of this solution is O(3^n) (because after each step there may be 3 directions to choose from).

By applying a number of optimisations, the computation time for this algorithm can be significantly reduced.

## Optimisations

1. **Marking unidirectional vertices as fully visited.**
If a vertex has only one edge, we can be sure that once it has been visited once, it will definitely not need to be revisited.
2. **Mark vertices with fully visited neighbours as fully visited.**
Edges leading to fully visited vertices need not be taken into account when choosing the next solution step. If a vertex has only one edge that does not lead to fully visited vertices, it can be treated as unidirectional, i.e., it can be marked as fully visited.
3. **Removing unnecessary loops.**
If the branch finds itself in a previously visited vertex, and has not painted any additional tiles since visiting it, the solution is bound to be suboptimal. This is the most effective of the presented optimisations, it reduces the number of branches needed to find a solution by 5-30 times, depending on the level layout.
4. **Removing branches that are too long.**
Branches longer than the current best solution found can be discarded.

Applying these optimisations allows us to find a solution for levels requiring up to 20 steps (which take about 5 minutes to compute on my computer). Extending the maximum length by each additional step increases the number of branches needed by 1.2 to 2 times (depending on the level layout).

## Suggested further optimisations

Further optimisations can be added to this approach, e.g:

1. Using Tarjan's algorithm to split the level into strongly connected components. Once all the floor tiles in a connected component have been painted, the whole component can be marked as fully visited.
2. Earlier discaring of branches that have no chance to paint all remaining tiles in fewer moves than the current best solution.

Certainly such optimizations would speed up the algorithm, but will not overcome its geometrically increasing complexity.

Can you propose a different approach, that could find the optimal solution with a lower complexity, or another optimization that can speed up this approach?

# Answer
> 3 votes
This is the Hamiltonian path problem on partial grid graphs (i.e., graphs which are arbitrary subgraphs of grids) which is known to be NP-complete. Thus, no polynomial algorithm exists unless P = NP.

A good bet here would be to try heuristics and (exact) algorithms designed for Hamiltonian path. In particular, if you model the problem as an instance of Boolean SAT, feed it to a state-of-the-art SAT solver, you might be amazed.

---
Tags: graphs, graph-traversal, computer-games
---


# Question
Title: Show that $P^A \neq EXP^A$ for all oracles A
I knew that $P \neq EXP$ by Time Hierarchy Theorem. But, I'd like to show that $P^A \neq EXP^A$ for all oracles A. How can I do it?

I knew that If I make A=EXP, PSPACE, NP, and many others, then this would show that the inequality holds. But, how can I prove it for all oracles? Can you give me hints?

Notes: I don't think that there exists some oracle that $P^B = EXP^B$ for some oracles B since it seems to me that $P \neq EXP$ using THT relativizes. But I don't know why it relativizes? Consider this as a minor question of the above question.

# Answer
*Why does the proof of the time hierarchy theorem relativize?* The time hierarchy theorem is proved by diagonalization. Such proofs tend to relativize. In order to know for sure, all you have to do is to repeat the proof of the time hierarchy theorem, when all concerned Turing machines are oracle Turing machines having access to the same oracle. If the proof still goes through, then it relativizes.
> 3 votes

---
Tags: complexity-theory, relativization
---


title: PCP undecidability

text:
# Question
Title: PCP undecidability
There is a popular proof for the undecidability of the PCP (Post correspondence problem), which is outlined here:

https://en.wikipedia.org/wiki/Post\_correspondence\_problem

I'll assume whoever will answer the question will be familiar with this proof.

---

I have seen this proof elsewhere and this kind of proof always mentions that if the $TM \ M$ halts we can solve the instance of the PCP. So far so good.

Now I was thinking about the case when the $TM \ M$ does not halt on input $w$. Then out total number of tuples/pairs ($\small{(a\_i,b\_i)}$, which get passed onto the PCP) should be countably infinite.

How can we even try to solve the PCP at this point ? Or do we implicitly think: "Thats impossible !" and say "There is no solution!" ?

This part confuses me very much because for the case that the TM halts we construct such a complex method and it seemed "cheap" to just throw the towel for the case when it would not halt.

I hope I could make my thoughts understandable, without much formality.

Any help is appreciated.

# Answer
> 5 votes
An instance of PCP consists of a finite list of tiles. The proof that PCP is undecidable consists of a computable reduction $f$ with the following properties:

* The input to $f$ is a Turing machine $M$ and a valid input $w$ to $M$.
* The output of $f$ is an instance of PCP (i.e., a finite list of tiles).
* The PCP instance $f(M,w)$ is a Yes instance iff $M$ halts on $w$.

A further property of the reduction is that the number of tiles depends only on $M$, though the contents of one of the tiles depends on $w$.

Let us denote the tiles by $(a\_1,b\_1),\ldots,(a\_n,b\_n)$. When $M$ halts on $w$, there exists a number $N$ and a sequence $i\_1,\ldots,i\_N \in \\{1,\ldots,n\\}$ such that $$ a\_{i\_1} a\_{i\_2} \ldots a\_{i\_N} = b\_{i\_1} b\_{i\_2} \ldots b\_{i\_N}. $$ When $M$ does not halt on $w$, no such $N$ exists. However, there does exist an *infinite* sequence $i\_1,i\_2,\ldots$ such that $$ a\_{i\_1} a\_{i\_2} \ldots = b\_{i\_1} b\_{i\_2} \ldots, $$ where both sides are *infinite* words. Perhaps this is what you meant by "total number of tiles". The actual number of tiles is always finite, and independent of the input. The number of instances of tiles required to "solve" the PCP instance could be finite or infinite; but we only consider finite solutions as valid.

# Answer
> 2 votes
> Then out total number of tuples/pairs ((ai,bi), which get passed onto the PCP) should be countably infinite.

I'm not entirely sure what you are trying to say here, but it sounds like this statement is the flaw in your reasoning. The number of pairs is always finite, regardless of whether the Turing machine halts or doesn't halt. Since you haven't provided any justification for this claim, it's not clear why you think it is true or what your specific confusion is, but this claim is false.

# Answer
> 0 votes
The total number of tile pairs is finite, the reason is: The number of the states of Turing machine M, the length of its input string w and the number of the tape alphabet are all finite, thus the number of their combinations, which are basically the tile pairs, is finite.

---
Tags: reductions, undecidability
---


# Question
Title: Find all $k$ such that $X_1+kY_1,\ldots,X_n+kY_n$ are all equivalent modulo $M$
> Let $n, M$ be integers. Given two arrays $X$ and $Y$ of $n$ elements.
>
> For each $i \leq n$, we define arithmetic progression $X\[i\] + kY\[i\] \pmod M$, where $0 \leq k \leq M$.
>
> Find all $k$ such that for all $i$, $X\[i\] + kY\[i\]$ has the same value.
>
> **Example**
>
> Let $n = 3$ and $M=6$.
>
> Let $X=\\{1,3,5\\}$ and $Y=\\{2,1,0\\}$.
>
> Then,
>
> $$k = 2, X\[0\]+2Y\[0\] = X\[1\] + 2Y\[1\] = X\[2\]+2Y\[2\] = 5 \pmod 6. $$ $$k = 5, X\[0\] + 5Y\[0\] = X\[1\]+5Y\[1\] = X\[2\] + 5Y\[2\] = 5 \pmod 6. $$
>
> So we have two values $k$.

**My thoughts.**

We can check the modulo equation of pair of elements $(0,1)$.

$$X\[0\] + kY\[0\] = X\[1\] + kY\[1\] \pmod M$$ or $$k(Y\[0\]-Y\[1\]) = X\[1\] - X\[0\].$$

Solve this equation we can get value $k$.

Similarly, we can get $k$ with pairs $(0,2), \dots, (0,n-1)$.

But I get stuck with this brute force way:

1. When $n$ becomes large (more than 50000), the run time is slow.
2. With the case $0k = 0 \pmod M$, it means that all $k$ of $\[0,M)$ satisfy. So, it does not reduce ranges in the equations.

How do I solve this problem efficiently?

Edit: change to base-0 as suggestion.

# Answer
You've made a good start. Here is an algorithm that is quite efficient (I used more variables and equations than really needed for even somewhat greater efficiency), even for relatively large $n$ (e.g., more than $50000$ you mention) and large $M$. First, if $n = 1$, then all $k$ work. Otherwise, using $0$-based indices, set up an array or list of objects, with each object containing the $2$ values

$$(Y\[0\] - Y\[i\]) \bmod{M} \tag{1}\label{eq1A}$$

$$(X\[i\] - X\[0\]) \bmod{M} \tag{2}\label{eq2A}$$

for $1 \le i \le n - 1$. Note $a \bmod{M} = b$ means $M \mid a - b$ and $0 \le b \lt M$.

Next, sort this array or list into increasing values of \eqref{eq1A}. Now, I'll use $1$-based indices. Have $C\[i\]$ refer to the $i$'th object element of the sorted array or list, with $C\[i\].y$ being the value from \eqref{eq1A} and $C\[i\].x$ being the value from \eqref{eq2A}. Thus, as you've indicated, the modular equation to solve for each $i$ is

$$k(C\[i\].y) \equiv C\[i\].x \pmod{M} \tag{3}\label{eq3A}$$

Next, set up an initially empty set, call it $D$, to contain the currently possible values of $k$ going from $0$ to $M - 1$ (note since $0 \equiv M \pmod{M}$, the $M$ value is equivalent to $0$) once the first non-$0$ $C\[i\].y$ value (if any) is handled. Initialize $p \leftarrow -1$ (i.e., previous congruence is not yet set). Start with $i \leftarrow 1$ and follow these steps:

1. If $C\[i\].y \neq 0$, then go to step #2. Otherwise, if $C\[i\].x \neq 0$, then there are no values of $k$ which work, so exit these steps. Increment $i$. If $i = n$, then all values of $k$ work, so also exit these steps. Otherwise, repeat this step.
2. If $p = C\[i\].y$, then go to step #$3$. Otherwise, set $p \leftarrow C\[i\].y$. Use the Extended Euclidean algorithm to compute values of $c$, $d$ and $g = \gcd(p, M)$ which satisfy $$cp + dM = g \tag{4}\label{eq4A}$$ Next, define $$e = (c \bmod{M}), \\; \\; h = \frac{p}{g}, \\; \\; s = \frac{M}{g} \tag{5}\label{eq5A}$$ Dividing both sides of \eqref{eq4A} by $g$ gives $$ch + ds = 1 \\; \\; \to \\; \\; eh \equiv 1 \pmod{s} \tag{6}\label{eq6A}$$ Go to step #$3$.
3. If $g \not\mid C\[i\].x$, then there are no $k$ which work, so exit these steps. Otherwise, set $$f = \frac{C\[i\].x}{g} \tag{7}\label{eq7A}$$ Dividing both sides of \eqref{eq3A} by $g$, plus using \eqref{eq5A}, \eqref{eq6A} and \eqref{eq7A}, gives $$kh \equiv f \pmod{s} \\; \\; \to \\; \\; k(he) \equiv fe \pmod{s} \\; \\; \to \\; \\; k \equiv fe \pmod{s} \tag{8}\label{eq8A}$$ Next, define $$r = (fe \bmod s) \tag{9}\label{eq9A}$$ This then gives that the set of valid values of $k$ which work are $$E = \\{r + ts, \\; 0 \le t \le g - 1\\} \tag{10}\label{eq10A}$$ If $D$ is the empty set, then have $D \leftarrow E$, else have $D \leftarrow (D \cap E)$. If $D$ is now an empty set, then there are no values of $k$ which work, so exit these steps. Otherwise, increment $i$. If $i \lt n$, then go to step #$2$. Otherwise, exit these steps, with the values in $D$ being those $k$ which work.
> 2 votes

---
Tags: algorithms
---


# Question
Title: Is this way to combine two functions into a new function called a function product?
I have been looking for a maths operation that allows me to combine functions in a specific way. For example if we have functions f and g both with single mappings from o to e and v to c respectively, and we want to achieve whats below.

f ? g = {o -\> e} ? {v -\> c} = {(o,v) -\> (e,c)}

I have been told that what I'm looking for is called a function product. I can't find anything about this, also does it have a another name?

I've been told this is how to compute it, where X is called the function product.

(f X g)(x,u) = (f(x), g(u))

Which works, but I cant find anything about it online.

# Answer
This operation is known as the cartesian product for functions. This product is not limited only to functions, but can *usually* be applied to almost every mathematical object.

But the "usual" notion of "function product" is referring to function composition, which is a totally different thing. It is calculated like that: $$(f\circ g)(x)=f(g(x))$$ While the cartesian product is calculated like that: $$(f\times g)(x,y) = (f(x),g(y))$$
> 1 votes

---
Tags: sets, functional-programming
---


# Question
Title: Clarification on the algorithm for finding a majority element
Here's a question about using a divide and conquer approach to find a majority element in an array. It's taken from *Algorithms* by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, Question 2.23. I'm not convinced why this algorithm should work.

It seems to give no direction on what to do with the element that is left unpaired when the array size is odd. Take for example $A = \[1, 1, 1, 2, 3\]$.

Suppose we keep that unpaired singleton element at each step. For example, if we pair them up as $\[1, 1\], \[1, 2\], \[3\]$, then after keeping $1$, discarding $1, 2$, and keeping $3$, we're left with $1, 3$. Then we discard both since they're different, so we're left with no majority element.

Suppose we don't keep that unpaired singleton at each step. If we pair them up as $\[1, 2\], \[1, 3\], \[1\]$, then we must discard all of them, so again we're left with no majority element.

Where is the flaw? Can someone clarify whether this algorithm keeps or discards the unpaired singleton?

# Answer
> 3 votes
The algorithm as written assumes that $n$ is a power of 2. But you can adjust it to support odd-length arrays, while still completing in $O(n)$ time, as follows:

Suppose that at some given point in time, the array has odd length. Let $x$ be the last value in the array. You can determine whether $x$ is the majority element in $O(n)$. If so, return it. If not, then after discarding the last value in the array, it still has the same majority element, but now the number of elements is even.

# Answer
> 1 votes
> When the size of your problem reduced to 2, it's the base case of your recursion, it's false that we pair up two remaining elements. so it's sufficiently, first count number of occurrence of two remaining elements in $A$.
>
> for your problem we act as follow:
>
> we check the whole array to count number of occurrence $A\[i\]=3$, and number of occurrence of $A\[i\]=1$ and then if number of occurrence $3\geq \frac{n}{2}+1$ or if number of occurrence $1\geq \frac{n}{2}+1$, we print it.

but the main problem is we must prove the correctness and running time of algorithm.

Suppose $\mathcal{X}$ is a majority element, because of, $\mathcal{X}$ is majority element, then the number of occurrence of it, is grater than $\frac{n}{2}$, so after pair up, at least there is one pair that elements are $\mathcal{X}$, otherwise it contradict with this fact that $\mathcal{X}$ is majority element.

On the other hand, at most all elements of array $A$ be $\mathcal{X}$, so both elements of a pair be equal, as a result at most half of the elements remain in each recursion.

Therefore one of the at most $\frac{n}{2}$ elements be $\mathcal{X}$. And we do our divide an conquer the problem until remain only two element.

Our statement holds only if $A$ contains $\mathcal{X}$. So after we get base that $n=2$, it's sufficient to for each of two remaining elements we check number of occurrence it.

Suppose the remaining elements is a,b:

```
    A,B=0
  for i = 1 to n
     if (a==A[i])
      A++
     if (b==A[i])
      B++

 if(a> n/2)
   print a
 else if (b> n/2)
   print b
 else
   print "there is no majority in the array"

```

Because of at each iteration at most half of the elements remain $$T(n)=T(\frac{n}{2})+O(n)$$ $$=O(n)$$

**Note that at each iteration pairing up of $n$ elements need $O(n)$ time.**

# Answer
> 1 votes
Not pointed out yet, but there is an **online** solution to the problem, even if it is not so easy to prove:

```
def majority(A):
  x:=A[1]
  c:=1
  for k from 2 to n:
    if A[k]=x:
      c++
    else:
      c--
      if c=0:
        x:=A[k]
        c:=1
  return x

```

To prove it correct, imagine that you maintain a set S of duplicate elements, and each time you see a new one you add it to S if it is another duplicate otherwise you pair it off with an element in S (and delete both). The above algorithm does that except by using a counter instead of actually keeping duplicates. Clearly, if an element m occurs more than half the time, it cannot be completely paired off, and so must remain undeleted at the end.

The algorithm is online because you can replace the array `A` by a generator (e.g. Python generator) and take only constant space.

---
Tags: algorithms, divide-and-conquer
---