title: Removing a character from a string

text:
# Question
Title: Removing a character from a string
I am asked the following:

```
def myRemove( str, ch ):
 # Return a new string with the first occurrence of ch removed.  If there is none, return str.

```

Sample run

```
>>> myRemove( "abcdabcd", "a")
'bcdabcd'
>>> myRemove( "abcdabcd", "x")
'abcdabcd'
>>> myRemove( "abcdabcd", "d")
'abcabcd'

```

I have tried a few different methods but have not been able to figure the problem out. Here is my attempt:

```
def myRemove( str, ch ):
    for num in range (0, len(str)):
        if (str[num] == ch):
            return str[0:num] + str[num + 1:]
        else:
            return str

```

There is also an extension to this problem which asks : `Return a new string with all occurrences of ch removed. If there are none, return str.` However, since I have not been able to solve the first part, naturally I was not sure how to solve the second. Would appreciate any guidance.

# Answer
> 2 votes
Notice that the loop will only occur once! In the beginning `num` will be 0. At this point, we enter the `if` statement:

* if we got that `str[0] == ch` (notice that `num==0` and thus `str[0]==str[num]`), then we return some string
* otherwise we return another string

The important thing here, is that no matter what - we will quit in the first iteration of the `for` loop.

To fix this, consider placing the `return str` outside the `for` loop (without `else` as well)

---
Tags: python
---


title: Reductions versus generalizations

text:
# Question
Title: Reductions versus generalizations
I am reading **Chapter 8 NP-complete problems** in *Algorithms* by Dasgupta et al and looking at some questions at the end of the chapter.

My own questions are below (after the image with the textbook questions). Note that I am not asking what the solutions are (those may be for separate questions) but rather the approach that makes the solutions right compared to what is in the chapter. My confusion is in the difference between reductions and generalizations.

1. In the questions above, we are saying that a **special** case of any of the problems above are NP-complete complete. This seems like a misnomer though. Shouldn't this be a **specialization** rather than a **generalization**?
2. Another part of my confusion is how these so-called generalizations compare or contrast to reductions. Are we saying that some (special) version of a problem is NP-complete and therefore all the other instances are NP-complete? I thought that we needed to show that all instances of the problem are the NP-complete problem.
3. Regarding the direction of reductions: we reduce from a NP-complete problem (the hard problem) to the problem that we have at hand. For example, in the reduction from `3SAT` to `independent set` we reduce from `3SAT` that we know is NP-complete to what we have at hand, the `independent set` \- did I misunderstand? Are these reductions generalizations? I thought that they were for all instances of the `independent set`.
4. Are generalizations reductions?

# Answer
> In the questions above, we are saying that a special case of any of the problems above are NP-complete complete. This seems like a misnomer though. Shouldn't this be a specialization rather than a generalization?

No. The problem you are proving NP-complete is a generalization of a known NP-complete problem. E.g. the MAX-SAT example contains Boolean satisfiability; just set $g$ large enough to demand satisfaction of all the clauses.

> Another part of my confusion is how these so-called generalizations compare or contrast to reductions. Are we saying that some (special) version of a problem is NP-complete and therefore all the other instances are NP-complete? I thought that we needed to show that all instances of the problem are the NP-complete problem.

No, we're saying that if an NP-complete problem can be specified using the rules that describe a different problem without changing those rules, then that different problem is NP-hard, and is also NP-complete if that different problem is in NP.

> Regarding the direction of reductions: we reduce from a NP-complete problem (the hard problem) to the problem that we have at hand. For example, in the reduction from 3SAT to independent set we reduce from 3SAT that we know is NP-complete to what we have at hand, the independent set - did I misunderstand? Are these reductions generalizations? I thought that they were for all instances of the independent set.

No, you should just think of reductions as reductions. A generalization of an NP-complete problem contains that problem as a special case within the generalized problem. A reduction provides a way to go from an instance of one problem to an instance of another without regard to whether one problem is a special case of another.

> Are generalizations reductions?

No, they are an expansion of the original problem that still contains the original problem. E.g. Boolean satisfiability is a generalization of 3-satisfiability because 3SAT is contained within the expanded problem set.
> 4 votes

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


# Question
Title: Relevance of depth for $NP$-completeness of fan-in $2$ and fan-out $1$ modest depth circuits?
Let $\mathcal C$ be a circuit of $m=f(n)$ input wires

1. where every input is taken in the set $\\{x\_1,x\_1',\dots,x\_n,x\_n'\\}$ where $x\_n\in\\{0,1\\}$ and $x\_n+x\_n'=1$ holds (not all $x\_i,x\_i'$ necessarily needs to be utilized if $f(n)=o(n)$)
2. where every layer of the circuit is all $AND$ or all $OR$ gates having fan-in $2$ and fan-out $1$, and the AND and OR layers alternate
3. depth of the circuit is $\leq\log^kn$ at a $k\geq0$

(essentially an $NC^k$ circuit having gates of fan-out $1$).

The question is whether $\exists x\_1,\dots,x\_n\in\\{0,1\\}:\mathcal C(x\_1,\dots,x\_n)=1$.

Usual $NP$-completeness is for $CIRCUITSAT$ where depth can be $poly(n)$ without restricting to fan-out $2$ and fan-in $1$. If depth is $k=O(\log n)$ do we still get $NP$-completeness if gates are fan-in $2$ and fan-out $1$ and number of input wires $poly(n)$?

> Is it $NP$-complete at all fixed $k\geq1$ if $f(n)=poly(n)$?

If $k=0$ the problem is in $P$ because the number of input wires is $O(1)$.

> Is there a complexity class for the problem if $0\<k\<1$ holds?

# Answer
Circuits with fan-out 1 are called *formulas*.

Polynomial-size fan-in 2 formulas of arbitrary depth can be rebalanced to depth $O(\log n)$ by Spira’s lemma, hence they compute exactly nonuniform $\mathrm{NC}^1$. (The restriction that layers alternate between AND and OR is immaterial, as one can always insert dummy nodes to make it true, while at most doubling the depth.) Thus, your model with $k\ge1$ collapses to $k=1$.

Satisfiability is NP-complete already for 3-CNF. These can be written as depth $O(\log n)$ fan-in 2 formulas by arranging the outer conjunction as a balanced binary tree. (Again, one might insert dummy OR gates to make the connectives alternate if desired.)

For $k\<1$, the formula only depends on $2^{(\log n)^k}$ variables, and therefore its satisfiability is computable in time $2^{O(2^{(\log n)^k})}$. Thus, it cannot be NP-complete unless ETH fails. There is no special complexity class for it, it is just NP scaled down to inputs of size $2^{(\log n)^k}$.

Better, satisfiability of circuits of depth $(\log n)^k$ for $k\<1$ is not NP-complete unless P = NP: if it is NP-complete, then there exists a poly-time reduction $f$ of CIRCUIT-SAT to itself that maps a circuit of size $n$ to a circuit of size $2^{O((\log n)^k)}$. Using $\log\log\log n/\log(k^{-1})$ iterations of $f$ (which are computable in polynomial time), we reduce CIRCUIT-SAT to satisfiability of a constant-size circuit, which is trivial to decide.
> 2 votes

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


# Question
Title: Would a parser for this left-recursive grammar require infinite input?
I am considering this left recursive language grammar production rule:

```
Expr = Expr, "a" ;

```

As a production rule, I believe that this can be used to produce an infinite sequence of `aaa` by describing the rule like this:

> Given a non-terminal `Expr`, expand it to `Expr` followed directly by the literal `a`.
>
> Example: if `Expr` is initially `b`, it may be expanded to `ba`. `Expr` is now `ba`, and may be expanded again producing `baa` and this process repeats infinitely to produce `ba`, `baa`, `baaa`, and so on.

I have tried to visualize this grammar as follows:

I believe the grammar cannot terminate in its production, as it requires infinite recursion (in theory.)

Given that this is a valid production rule, I would believe that it is possible this grammar could also then be used as the definition to write a parser. I would describe that parser as:

> It accepts any sequence of non-terminals (the `Expr`) followed by an infinite sequence of `a`.

However, what is not clear to me is if a parser for this language would *require* an infinite sequence of `a` or if a finite sequence of `a` would be admissible: would `baa` *actually* be a valid input, or would a theoretical machine parser for this effectively produce an error saying:

```
baa
   ^ found termination, expected "a"

```

Appreciate any guidance you can provide me in thinking about this problem.

# Answer
> 1 votes
Your grammar captures the empty language. To see this, you need to use the definition of a language described by a context-free grammar.

A context-free grammar is a tuple $(T,N,S,P)$, where $T$ is the set of terminals (a non-empty finite set), $N$ is the set of nonterminals (a non-empty finite set disjoint from $T$), $S \in N$ is the starting symbol, and $P$ is a collection of productions $A \to \alpha$, where $A \in N$ and $\beta \in (N \cup T)^\*$.

In your case, $T = \\{a\\}$, $N = \\{\mathrm{Expr}\\}$, $S = \mathrm{Expr}$ (you are not stating this explicitly, but this is the only choice), and $P$ consists of the single rule $\mathrm{Expr} \to \mathrm{Expr} \\, a$.

We say that $\beta$ produces $\gamma$ in one step, in symbols $\beta \Rightarrow \gamma$, if there exists a production $A \to \alpha \in P$ and two strings $\lambda,\mu \in (N \cup T)^\*$ such that $\beta = \lambda A \mu$ and $\gamma = \lambda \alpha \mu$.

We say that $\beta$ produces $\gamma$, in symbols $\beta \Rightarrow^\* \gamma$, if either $\gamma = \beta$, or $\beta \Rightarrow \delta \Rightarrow^\* \gamma$ for some $\delta \in (N \cup T)^\*$. This is the reflexive-transitive closure of $\Rightarrow$.

Finally, the language produced by the grammar is $\\{ w \in T^\* : S \Rightarrow^\* w \\}$.

In your case, a simple induction shows that $\mathrm{Expr} \Rightarrow^\* \alpha$ iff $\alpha = \mathrm{Expr} \\, a^n$ for some $n \in \mathbb{N}$. Since $\mathrm{Expr} \\, a^n \notin T^\*$, we conclude that the language produced by your grammar is the empty language.

---
Tags: formal-languages, parsers, left-recursion
---


title: Data model and database schema

text:
# Question
Title: Data model and database schema
I need to test my understanding of the difference between the data model and database schema. According to my understanding, the data model is a description of how the data will be stored and the relationships between the data. While the schema is very similar to a database model and according to the book "Database Management systems " by Raghu and Johannes " A description of data in terms of a data model is called schema" and it's a template of how the data will be stored. Is that right?

# Answer
> 1 votes
A data model is set of general abstraction mechanisms: for instance you have the relational data model, with mechanisms as the relation, primary and foreign keys, etc. Or an object oriented data model with mechanisms like classes, aggregation, generalization, etc.

The schema instead is the description of a particular slice of reality for modeling purposes, for instance to build a database, expressed using a specific data model.

---
Tags: database-theory, databases
---


# Question
Title: How to solve recurrence of a binary tree
I'm trying to solve this recurrence of a function of a binary tree with a recursive tree. But I can't find any pattern to solve it.

This function calculates both the height and if its a balanced tree.

```
template <typename T>
std::pair<bool, int> balanced_height(const BinTree<T> &tree) {
  if (tree.empty()) {
    return {true, 0};
  } else {
    auto [bal_left, height_left] = balanced_height(tree.left());
    auto [bal_right, height_right] = balanced_height(tree.right());
    bool balanced = bal_left && bal_right && abs(height_left - height_right) <= 1;
    int height = 1 + std::max(height_left, height_right);
    return {balanced, height};
  }
}

```

And the recurrence, $n$ is the number of tree nodes. I think that $n\_l$ and $n\_r$ should decrease in each call by 1.

$$ T(n) = \begin{cases} T(n\_l)+T(n\_r) + 1 & \text{if } n \gt 0, \\ 1 & n = 0 \\ \end{cases} \\ \text{Given that }n\_l+n\_r+1=n $$

# Answer
> 1 votes
There are several slightly different ways of defining binary trees. You seem to be using the following: a binary tree is either a leaf, or an ordered pair of binary trees.

Your recursive procedure actually computes two different functions: the first output is a Boolean function $b$ which measures whether the tree is balanced, and the second is an integer-valued function $h$ which computes the height of the tree.

The height function $h$ is defined as follows: if $T$ is a leaf then $h(T) = 0$, and if $T = (T\_\ell,T\_r)$ then $h(T) = 1 + \max(h(T\_\ell),h(T\_r))$. This function computes the height of the tree.

The balancedness function $b$ is defined as follows: if $T$ is a leaf then $b(T) = \mathsf{true}$, and if $T = (T\_\ell,T\_r)$ then $b(T) = b(T\_\ell) \land b(T\_r) \land |h(T\_\ell) - h(T\_r)| \leq 1$. In words, a tree is balanced if in every internal note $v$, the heights of the left and right subtrees differ by at most one.

As you can see, the argument of both functions is a *tree*.

Your recurrence describes the worst-case running time of the procedure as a function of the number of nodes. The base case is $T(1) = O(1)$ (when the tree is a leaf), and when $n \> 1$, $$ T(n) = \max\_{\substack{n\_\ell,n\_r \geq 1 \\ n\_\ell+n\_r+1=n}} T(n\_\ell) + T(n\_r) + O(1). $$ The solution is $T(n) = \Theta(n)$. You can prove this by induction. In particular, if you replace $O(1)$ by $1$, a simple induction shows that $T(n) = n$.

In fact, it is not hard to check that your procedure has running time $\Theta(n)$ on *any* tree having $n$ nodes, since the recursive calls "visit" every node in the tree, and do $O(1)$ processing per node.

---
Tags: asymptotics, recurrence-relation, big-o-notation
---


# Question
Title: Not satisfiable 3SAT instance implications
Suppose we have an instance of *3SAT* that is NOT satisfiable and we say $S$.

If in $S$ there are the following $8$ clauses

$\left(a\vee b\vee c\right)\wedge\left(a\vee\bar{b}\vee c\right)\wedge\left(a\vee b\vee\bar{c}\right)\wedge\left(a\vee\bar{b}\vee\bar{c}\right)\wedge\left(\bar{a}\vee b\vee c\right)\wedge\left(\bar{a}\vee\bar{b}\vee c\right)\wedge\left(\bar{a}\vee b\vee\bar{c}\right)\wedge\left(\bar{a}\vee\bar{b}\vee\bar{c}\right)$

we have that anyway we set the Boolean value of the variables $a,b,c$, there is a clause that is *false*.

If in $S$ instead of $a \vee \bar{b} \vee \bar{c}$ we have

$\left(a\vee e\vee f\right)\wedge\left(a\vee\bar{e}\vee f\right)\wedge\left(a\vee e\vee\bar{f}\right)\wedge\left(a\vee\bar{e}\vee\bar{f}\right)$

this implies that anyway we set the Boolean value of the variables $a,b,c,e,f$, there is a clause that is *false*.

In the first case, we have

$\left(a\vee b\vee c\right)\wedge\left(a\vee b\vee\bar{c}\right)\Rightarrow \left(a\vee b\right)$
$\left(a\vee \bar{b}\vee c\right)\wedge\left(a\vee \bar{b}\vee\bar{c}\right)\Rightarrow \left(a\vee \bar{b}\right)$
$\left(\bar{a}\vee b\vee c\right)\wedge\left(\bar{a}\vee b\vee\bar{c}\right)\Rightarrow \left(\bar{a}\vee b\right)$
$\left(\bar{a}\vee \bar{b}\vee c\right)\wedge\left(\bar{a}\vee \bar{b}\vee\bar{c}\right)\Rightarrow \left(\bar{a}\vee \bar{b}\right)$
and
$\left(a\vee b\right)\wedge\left(a\vee \bar{b}\right)\wedge\left(\bar{a}\vee b\right)\wedge\left(\bar{a}\vee \bar{b}\right)$
is NOT satisfiable.

In the second case, we have

$\left(a\vee e\vee f\right)\wedge\left(a\vee \bar{e}\vee f\right)\Rightarrow \left(a\vee f\right)$
$\left(a\vee e\vee \bar{f}\right)\wedge\left(a\vee \bar{e}\vee\bar{f}\right)\Rightarrow \left(a\vee \bar{f}\right)$
and
$\left(a\vee f\right)\wedge\left(a\vee \bar{f}\right)\Rightarrow a$
and
$a\Rightarrow\left(b\vee c\right)\wedge\left(\bar{b}\vee c\right)\wedge\left(b\vee\bar{c}\right)\wedge\left(\bar{b}\vee\bar{c}\right)$
and this last conjunction is NOT satisfiable.

The question is: given a NOT satisfiable *3SAT* instance, if we apply all possible implications and make the conjunction of the right side of the implications, we get a 2SAT instance (the right side of these impliacations is either the conjunction of two variables or a singol variable); is this 2SAT instance not satisfiable? If it isn't, can you give me an example?

# Answer
You are describing the Resolution refutation system, which is complete in the sense that if a CNF is unsatisfiable, then it can be proven using Resolution. Resolution is also implicitly used in most SAT solvers.

The *width* of a Resolution refutation is the maximal number of literals in a clause encountered during the refutation. There are 3CNFs on $n$ variables which require width $\Omega(n)$, for example Tseitin contradictions on 3-regular expanders; see for example Massimo Lauria's lecture notes. This means that *every* Resolution refutation of these 3CNFs *must* contain a clause having $\Omega(n)$ literals.
> 3 votes

---
Tags: combinatorics, satisfiability
---


# Question
Title: If $A$ is c.e.-complete then the join of $A$ and $A^c$ isn't c.e
Let $A\subseteq\\{0, 1\\}^∗$, and let $A^c = \\{0, 1\\}^∗ \setminus A$ be the complement of $A$. Prove: If A is $\le\_m$-complete for CE, then $A$ join $A^c$ is neither c.e. nor co-c.e.

c.e --\> Computably enumerable

The join of two languages $A, B \subseteq \\{0, 1\\}^∗$ is defined by: $\\{x0 \mid x\in A\\} \cup \\{y1 \mid y \in B\\}$.

# Answer
Let $B$ be $A$ join $A^c$, for the concept of *join* defined in your question. Consider the language $H = \\{\langle T \rangle \\, \mid \\, \text{$T$ is a Turing Machine that halts on empty input}\\}$.

Let $f$ be $m$-reduction from $H$ to $A$. Given word $w \in \\{0,1\\}^\*$ (think of this word as a Turing Machine), $w \in H \iff f(w) \in A \iff f(w)0 \in B$. Similarly, $w \not\in H \iff f(w) \not\in A \iff f(w)1 \in B$.

Suppose towards a contradiction that $B \in \mathsf{CE}$. Construct a Turing machine $M^\*$ that simulates, in parallel, two executions of a Turing Machine $M$ that recognizes $B$ until one of them halts and accepts. One execution of $M$ has input $f(w)0$ and the other has input $f(w)1$. If $M(f(w)0)$ halts and accepts then $M^\*$ accepts. If $M(f(w)1)$ halts and accepts, then $M^\*$ rejects.

Since $f(w)0 \in B \iff f(w)1 \not\in B$, at least one of $M(f(w)0)$ and $M(f(w)1)$ eventually halts and accepts. This shows that $M^\*$ decides $H$ and provides the sought contradiction ($H$ is a well-known undecidable language).

Suppose towards a contradiction that $B \in \mathsf{\text{co-CE}}$. Construct a Turing machine $\overline{M}^\*$ that simulates, in parallel, two executions of a Turing Machine $\overline{M}$ that recognizes $\overline{B}$ until one of them halts and accepts. One execution of $\overline{M}$ has input $f(w)0$ and the other has input $f(w)1$. If $\overline{M}(f(w)0)$ halts and accepts then $\overline{M}^\*$ rejects. If $\overline{M}(f(w)1)$ halts and accepts, then $\overline{M}^\*$ accepts.

Since $f(w)0 \in \overline{B} \iff f(w)1 \not\in \overline{B}$, at least one of $\overline{M}(f(w)0)$ and $\overline{M}(f(w)1)$ eventually halts and accepts. This shows that $\overline{M}^\*$ decides $H$ and provides the sought contradiction.

Therefore we must have $B \not\in \mathsf{CE}$ and $B \not\in \mathsf{\text{co-CE}}$
> 2 votes

# Answer
Suppose, for example, that $A$ join $A^c$ is c.e. Since $A$ is c.e.-complete, $A$ join $A^c$ reduces to $A$. In particular, $A^c$ reduces to $A$. Show that this leads to a contradiction.

The proof that $A$ join $A^c$ isn't co-c.e. is similar.
> 1 votes

---
Tags: computability
---


# Question
Title: Is the union of computable enumerable sets computably enumerable
Let $\\{A\_n : n \in \mathbb{N}\\}$ be a collection of c.e. (computably enumerable) sets. Is $\bigcup\_n A\_n$ c.e.?

That is, is the union of c.e. sets c.e.? Otherwise, under what conditions will this be true?

# Answer
Every language can be written as a countable union of singletons $\\{x\\}$.

On the other hand, the union of *finitely* many c.e. languages is c.e.
> 2 votes

# Answer
For any c.e. collection of c.e. sets, the union is c.e., however if the collection itself is not c.e, then not (a counterexample is $S\_x = \\{x + n : n \in \mathbb{N}\\}$, then $\bigcup\_{x\in\mathbb{R}} S\_x$ is not c.e. even though it's a union of only c.e. sets).

To see the above by explicit construction, first if you allow duplicates in your enumeration (this isn't strictly the union of sets) then we have an explicit map from $\mathbb{N} \to \mathbb{N}^2$. See for example the inverse of the Cantor pairing function. Then we can first select which c.e. set to pick, and then which element from that set. You can explicitly filter out the duplicates afterwards to get a proper enumeration.
> 0 votes

---
Tags: automata, enumeration
---


# Question
Title: What are the exponential alternatives that are skipped in dynamic programming for longest increasing subsequence?
I am trying to wrap my head around how dynamic programming helps avoid all possibilities that are exponential after reading **Chapter 8 NP-complete problems** of *Algorithms by Dasgupta et al.* where it says:

> So far in this book we have seen the most brilliant successes of this quest, algorithmic techniques that defeat the specter of exponentiality: greedy algorithms, **dynamic programming**, linear programming (while divide-and-conquer typically yields faster algorithms for problems we can already solve in polynomial time).

Going back to **Chapter 6 Dynamic programming**, I followed along the *longest increasing subsequence problem* that this video also shows how to solve. It seemed to me that we were considering all other choices in the solution for the sequence $3, 4, -1, 0, 6, 2, 3$, but only did this with $n^2$ time.

What are the other possible subsequences that would reveal that this problem is exponential in nature without dynamic programming? I can see that in the `0-1 Knapsack problem` there are $2^n$ possibilities to consider but can't see the exponential counterpart of the `longest increasing subsequence problem`.

# Answer
> 3 votes
Go over all $2^n$ subsequences. For each one, check whether it is increasing.

There are two meanings of subsequence: *contiguous* subsequence and *arbitrary* subsequence. For example, $1,3$ is a non-contiguous subsequence of $1,2,3$.

Formally, a subsequence of $a\_1,\ldots,a\_n$ is a sequence $a\_{i\_1},\ldots,a\_{i\_m}$ for some $1 \leq m \leq n$, where $1 \leq i\_1 \< \cdots \< i\_m \leq n$. A subsequence is contiguous if it is of the form $a\_i,a\_{i+1},\ldots,a\_j$, that is, if it contains all elements from $a\_i$ to $a\_j$.

A sequence of length $n$ has $2^n-1$ subsequences, only $\binom{n+1}{2}$ of which are contiguous.

For example, here are all subsequences of $a,b,c$: $$ a \\ b \\ c \\ a,b \\ a,c \\ b,c \\ a,b,c $$ Of these, only $a,c$ is not contiguous.

---
Tags: np-complete, dynamic-programming, subsequences
---


title: Does this data structure already exist?

text:
# Question
Title: Does this data structure already exist?
I was working on a problem for some time now, and I made a data structure to solve it. To my surprise, I could not find any instance of this data structure on the internet (though I am certain someone has thought of this).

Put simply, it is a sorted linked list and a sorted array, with the array pointing to spots a fixed distance apart in the linked list:

```
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10
|                   |                   |

```

where the gap between elements $g = c\*log\_2(n)$

To find an element, just binary search the array and then go to that spot in the linked list, traverse the list until the element is found or greater than the target, return true or false respectively.

To insert you do much the same: traverse and insert before the first largest element.

Of course this by itself is not sufficient as our performance will rapidly degrade over time from $log\_2(n)$ to $n$. To fix this, I came up with a very simple solution: as you are traversing the list to find / insert the element, every $g$ elements ($g$ is the gap size) you just move the next "pole" (poles are the items in the array) over to the current element. If there is no next pole, add a pole to the end of the array:

```
insert(6.5) called (before, gap size = 4)
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10
|                                  |
(after)
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 6.5 -> 7 -> 8 -> 9 -> 10
|                   |                     |

```

Surprisingly, I could not find a way to permanently degrade the *average* performance to $n$: it would always average out to $log(n)$. The intuitive logic is that every time an adversarial user would attempt an insert/find that is relatively expensive (that is when the gap grows large, which happens when the order of insertion is reversed ie. inserting decreasing elements), they are pushing this gap further to the right, until it gets pushed to the end and new poles are inserting, bringing the performance back down to $log\_2(n)$.

My analysis was this: lets say you insert $n$ elements at the front. Now the list is doubled in size, and all the poles are bunched on one end. The next find call could be made a worse case $n$ operations, which would shift all those poles to the front. You could do this one more time, which again is $n$, and this time there are no poles in front, so you add them, approximately doubling the number of poles, bringing the worst case performance back down to $log\_2(n)$.

Note that you can't create gaps *and* make expensive calls one after the other: every expensive call fixes the list more and more, so you can either make a large gap and exploit it some number of times, or you will spread the poles out and the performance will level out (I think, I am no expert at this).

In general, if you insert $n/q$ elements in the front (which is the worse case), you will be able to incur a $n/q$ cost another $(q+1)/q$ more times, which makes the total cost average out to $log\_2(n)$:

$\frac{n/q\*log\_2(n/g) + ((q+1)/q)\*(n/q)}{2\*n/q} = \frac{log\_2(n/g)}{2} + \frac{1}{2} + \frac{1}{2q} = O(log\_2(n/g)) + g \approx O(log\_2(n))$

Removing items is a bit annoying. The simplest way is to leave deleted elements in the list and mark them as deleted, performing a clean up every time $n/d \geq 0.5$. This is amortized $log\_2(n)$, same as above. This does waste space, however.

My implementation and benchmarks are here (along with some bugs most likely ): https://github.com/Kh4n/teleport-list

For the regular linked list version, I used two arrays, one that "caches" the linked list values to improve the binary search speed, and the other which contains the actual pointers.

It beats the built in multiset implementation easily, which is a red-black tree. The unrolled version (which uses an unrolled linked list instead of a regular linked list) is particularly fast. Nevertheless, I am not certain if it is $log\_2(n)$. This is something I would like verification of.

Advantages:

* Fast and simple to program
* Good cache usage
* Very low space overhead when compared to other $log(n)$ data structures
* Can easily trade space/speed to tune the structure to your needs
* Trivial bulk insertion methods
* Can be combined with other data structures easily
* Excellent performance for long increasing/decreasing runs of data
* Good for primitive types

Disadvantages:

* I don't think it is viable for multithreaded usage. Although the whole array only needs to be locked when growing in size, finds and inserts might not be performant when the indices are locked (I have not tested this)
* Amortized performance means that there can be high variance from call to call
* Deletion wastes space (I cannot find a way to make deletion space efficient, though by rebuilding more often you can trade performance for memory efficiency)

Edit: the amortization calculation above is not correct (it is an underestimate), this is the right one:

$\frac{n/q\*log\_2(n/g) + ((q+1)/q)\*(n/q)}{n/q + (q+1)/q} = \frac{n\*log\_2(n/g) + n\*((q+1)/q)}{n+q+1} \approx log\_2(n/g) + \frac{q+1}{q} = O(log\_2(n))$

# Answer
I believe you have discovered a variant of "dynamic fractional cascading", which is closely related to skip lists.
> 2 votes

---
Tags: data-structures, amortized-analysis
---


# Question
Title: Knapsack on two kinds of objects, where you cannot choose type 2 objects on their own
I had an online round at a company where I was asked this question.

There are $N$ items, and you have to choose some items from them such that the total weight does not exceed $W$.

Each item has three properties, weight, profit and type. There are only two types of objects.

Type 0 item can be selected independently own their own.

A type 1 item cannot the selected on its own and needs another item of type 1.

> Note: The problem does not say if this means what we have to select at least two type 1 items to select any at all, or that all the type 1 items must be in pairs.

**Constraints**:

* $N \< 10^3$
* $W \< 10^5$
* $\mathit{weight}, \mathit{profit} \< 10^5$

This is obviously (?) related to the knapsack problem, as without the restriction on the type 1 objects, it would actually be the 0-1 knapsack problem. How do I go about doing this? Any help and general ideas are extremely appreciated.

# Answer
> 2 votes
I think this can be solved the same way that knapsack problem is solved using dynamic programming.

I present the problem for the case where type 1 items are to be selected in pairs, but the other case is solvable in a similar way.

Suppose the weights are $\\{w\_1, …, w\_n\\}$, the profits are $\\{p\_1, …, p\_n\\}$ and the types are $\\{t\_1, …, t\_n\\}$. Let's define, for $w\in \[\\!\[0, W\]\\!\], i \in \[\\!\[1, n\]\\!\], j\in\\{0,1\\}$, $K(w, i, j)$ representing the maximum profit using a knapsack of capacity $w$, using items $1, …, i$, with a parity of type 1 items equal to $j$.

We want to determine $K(W, n, 0)$. Using this definition, we can calculate $K(w, i, j)$ by distinguishing if we take or not the $i$-th item:

$K(w, i, j) = \max(K(w-w\_i, i - 1, j \oplus t\_i) + p\_i, K(w, i - 1, j))$ (where $\oplus$ is the addition modulo 2)

With this formula, we can then compute $K(W, n, 0)$ in time complexity $O(nW)$.

In the case you just need to pick at least two items of type 1 if you want any, $K(w, i, j)$ could represent the maximum profit with $j\in \\{0, 1,2\\}$ representing respectively exactly zero type 1 item, exactly one type 1 item or at least 2 type 1 items.

---
Tags: dynamic-programming, knapsack-problems
---


# Question
Title: Machine Learning vs System Identification?
Could anyone explain to me the differences & similarities between machine learning and system identifications? Are these just two names of the same thing? In this page, they say:

> Machine learning and system identification communities are faced with similar problems where one needs to construct a model from limited or noisy observations.

I've also read the early chapters of the famous book Pattern Recognition and Machine Learning by Christopher M. Bishop. So far, my conclusion is that the problem that system identification is trying to solve is a subset of what machine learning is trying to solve.

# Answer
System identification is the science of constructing dynamical models from observed data. There are two main approaches: Prediction Error Identification (PEI) and Subspace Identification (SID). Both of them are delivering a so called parametric model, that is to say, a model of a fixed structure. Usually it is the case that the user selects the structure of the underlying system (especially in the PEI methods) or at least the order of the system (in both methods). Even though it is not necessary, a low order system is sought (that is to say, the number of the basis coefficients is relatively small) because it is often used for control purposes, so we have to keep it as simple as possible to avoid computational issues etc. This model can be used to make predictions about the future behaviour of the system given some inputs.

On the other hand, machine learning (ML) has two main branches, classification and regression algorithms. The latter ones are also used for prediction purposes. Two of the most famous approaches in machine learning are Support Vector Machines (SVM) and Gaussian processes (GP). The main difference with the system identification techniques is that the ML techniques are delivering a non-parametric model. The latter means that the prediction for a new input is given as a function of the data points used for the "training" (learning, identification) of the model. Therefore, if we used N=1000 data points for the training, then the prediction would be expressed as a function of these data points. ML methods are more flexible since they don't require any structure selection from the user, but they face other limitations (e.g. computational effort).

Until recently the ML and the system identification techniques were developing independently. But in the latter years there is a great effort to establish a common ground (e.g. see the paper "Four encounters with system identification" from Ljung)
> 6 votes

# Answer
Context: SysID and controls guy who got into ML.

I think user110686's answer does a fair job of explaining some differences. SysID is **necessarily** about dynamic models from input/output data, whereas ML covers a wider class of problems. But the biggest difference I see is to do with (a) memory (number of parameters); (b) end use of the "learned" model . System Identification is very much a signal processing approach considering frequency domain representations, time-frequency analysis etc. Some ML folks call this "feature engineering".

**(a) Memory:** SysID became prominent long before ML as a research field took shape. Hence statistics and signal processing were the primary basis for the theoretical foundations, and computation was scare. Hence, people worked with very simple class of models (Bias-Variance tradeoff) with very few parameters. We are talking at most 30-40 parameters and mostly linear models even for cases where people clearly know the the problem is non-linear. However, now computation is very cheap but SysID hasn't come out of its shell yet. People should start realizing that we have much better sensors now, can easily estimate 1000s of parameters with very rich model sets. Some researchers have attempted to use neural networks for SysID but many seem reluctant to accept these as "mainstream" since there aren't many theoretical guarantees. For anything not linear, its going to be hard getting guarantees anyway, so I am curious as to how the field will proceed.

**(b) End use of learned model:** Now this is one thing SysID got very correct, but many ML algorithms fail to capture. It is important to recognize that for the target applications, you are necessarily building models that can be used effectively for **online optimization.** These models will be used to propagate any control decisions made, and when setting this up as an optimal control problem, the models become constraints. So when using an extremely complicated model structure, it makes the online optimization that much more difficult. Also note that these online decisions are made in the scale of seconds or less. An alternative proposed is to directly learn value function in an off-policy manner for optimal control. This is basically reinforcement learning, and I think there is good synergy between SysID and RL.
> 4 votes

# Answer
I'd like to add that there are also non-parametric approaches to system identification. See MATLAB's SysId toolbox or Ljung's book for details. Non-parametric approaches are often used to first identify the class of models for later parametric studies. Also, it is important to separate the estimation problem from the control problem (think OODA loop). In identifying a system it is often the goal simply to characterize the system without any specific control inputs of the type that will be designed later (but this is not always possible). Finally, I think it is helpful to realize that a system is from a mathematical point of view an operator that maps a function space to a function space. Hence differential equations are often the kinds of things identified and these map functions to functions. The functions in SysID are often continuous functions of time, aka continuous-time signals. (But they can be discrete-time as well.) Thus, SysID is not just attempting to map real numbers (or vectors) to real numbers (or vectors); it seeks to identify the best operator (LTI, LTV, non-linear, etc.) that maps input signals to output signals.
> 2 votes

# Answer
This is murky indeed. I can't say I agree with the distinctions mentioned about parameterization. I think there are parametric and non-parametric examples of both. My 2 cents: a major distinction is the direction of causality in the system. In ML the "real-world" direction of causality can go in either direction x-to-y or y-to-x, but the model always has y (the "target") at the output and x (the "observation") at the input. In sys ID, x tends to drive the system, thus generating y.
> 1 votes

# Answer
Machine Learning: modeling for static model and dynamic model , System Identification: focus on dynamic model or dynamic process
> -2 votes

---
Tags: machine-learning
---


# Question
Title: Two "bubble" loops in pseudocode; would they return the same thing?
I am trying to create a new form of a bubble loop and want to see if they would return the same truth values during runtime. Could I get a second pair of eyes to confirm if this is the case?

Note: prod is equal to a target product of a sequence.

```
Code #1
For c = 1 to x
For d = 1 to c - 1
If (a,c * a,d = prod) return True
End For

Code #2
For c = 1 to x
For d = c + 1 to x
If (a,c * a,d = prod) return True
End For

```

I did data collection and found that in each case, the return true value would be the same. Is this always the case? If so, is this just because our index is simply starting at the second to the beginning as compared to skipping the end?

# Answer
In the first code, the values taken by $(c, d)$ are in the set $\\{(c, d)| 1 \leq d \< c \leq x\\}$. In the second code, the set is $\\{(c,d)|1\leq c \< d \leq x\\}$. Since $c$ and $d$ play symmetrical roles in the boolean test, it is expected that you obtain the same result.

Note that if $c$ and $d$ would not play symmetrical roles, the result could be different (for example, if the test was `a, c * d, a = prod`).
> 2 votes

---
Tags: logic, pseudocode
---


# Question
Title: Is the multiplicative constant in the Big O notation are ignored because of Linear Speed-Up theorem?
I just want to know if Big O notation was used as a consequences of the Linear speed up theorem or not. For me I guess the answer is yes.

For example, if we didn't have a linear speed-up theorem, then does it mean that we would have a different measure of time/space complexity? i.e. multiplicative constants does makes different. For example, $f(n) = 100 n$ isn't the same as $g(n)=10^{82}n$. Therefore, in this regard, Big O notation is not useful. So, probably we have another way to measure algorithms.

# Answer
> 1 votes
Please note that the big O notation was invented before the proof of the linear speedup theorem, and even before Turing machines.

Also, the big O notation often gives an information independant of the multiplicative constant: "if I multiply the input by $k$, then the total computing time will not be multiplied by more than …".

Finally, keep in mind that the linear speedup theorem gives a way to reduce the number of steps in the execution of a Turing Machine, but if you implement it on a real computer, it often also means that each step may be longer, so the real total time may not decrease.

The big O notation is a convenient way to compare asymptotic time complexity, but it is not always sufficient. For example, mergesort have an asymptotic complexity $\Theta(n\log n)$, but considering the multiplicative constant, it is often better to use insertion sort to sort small data, even if the asymptotic complexity of insertion sort is $\Theta(n^2)$ in average. Another example are Fibonacci heaps.

---
Tags: complexity-theory, time-complexity
---


title: Number of Comparisons in an Algorithm

text:
# Question
Title: Number of Comparisons in an Algorithm
The number of comparisons in the following algorithm is supposed to be $3n/2 - 3/2$ if $S$ is odd. I understand that the for loop is $3n/2$ comparisons, but I fail to see where the $-3/2$ comes from.

```
if (n % 2 == 0):
    if (S[0] > S[1]):
        Largest = S[0]
        Smallest = S[1]
    else:
        Smallest = S[0]
        Largest = S[1]
    I = 3
else:
    Smallest = Largest = S[0]
    I = 2

for (i=I; i<=n-1; i+=2):
   if S[i] < S[i+1]:
     if S[i] < Smallest:
      Smallest = S[i]
     if S[i + 1] > Largest:
      Largest = S[i + 1]
   else:
     if S[i + 1] < Smallest:
      Smallest = S[i + 1]
     if S[i] > Largest:
      Largest = S[i]

```

# Answer
If $n$ is odd, no comparison involving elements of $S$ is performed outside of the for loop.

Moreover, each loop iteration performs exactly $3$ comparisons involving some element in $S$. The number of iterations is the minimum integer value of $k$ such that $2+2k \> n$, i.e., $k=\left\lceil \frac{n-2}{2} \right\rceil = \frac{n-1}{2}$.

Therefore, the total number of comparisons involving some element in $S$ is $3 \cdot \frac{n-1}{2} = \frac{3n}{2}-\frac{3}{2}$.
> 1 votes

---
Tags: algorithm-analysis
---


title: Raising to the T in machine learning

text:
# Question
Title: Raising to the T in machine learning
What does it mean when in a machine learning paper there is $(arg)^{T}$, what does the T does to an arg in this 3b1b video on neural networks he puts the: $(w^{l-1})^{T}$

# Answer
The notation $A^T$ stands for the transpose of a matrix. It is not specific to machine learning, but rather standard notation in linear algebra. Other notations are sometimes used, for example $A'$.

A related operation is the adjoint $A^\*$. The transpose and adjoint are equal for real matrices.
> 4 votes

---
Tags: machine-learning, artificial-intelligence, lambda-calculus, neural-networks, notation
---


# Question
Title: while loop for bitwise conversion program
```
int counter(char c){
    int count = 0;
    while (c!=0){
       if((c & 1) !=0)
         count++;
       c = c >> 1;
}
}

```

I am trying to understand a program that counts the number of 1s in the binary representation of the input character. While I understand the & part and the count part, I don't get why we're checking for c!=0 in the while loop. I know each character is 8 bits. For instance, if the input character is "2" then the binary representation is 10. The count will be 1. So we start by checking the first binary number "1". Then we shift by 1 and it becomes 01? So then do we check 1 again? Or do we check 0? But if we check 0 then does the while loop not run at all?

An example of the steps would be really helpful.

# Answer
> 2 votes
The `&` operator is a bitwise "AND". Since the binary representation of 1 consists only of a 1 on the least significant bit, the operation `c & 1` checks if $c$ contains a 1 on the least significant bit. Another way to say it is that `c & 1` is the remainder of $c$ modulo 2, that is 0 if $c$ is even and 1 if $c$ is odd.

The `>>` is a logical shift right, that is the deletion of the least significant bit.

For example, if $c = 26 = (11010)\_2$, the steps are:

* `c & 1 = 0` so `count` is not modified. $c$ becomes $1101$;
* `c & 1 = 1` so `count` is incremented. $c$ becomes $110$;
* `c & 1 = 0` so `count` is not modified. $c$ becomes $11$;
* `c & 1 = 1` so `count` is incremented. $c$ becomes $1$;
* `c & 1 = 1` so `count` is incremented. $c$ becomes $0$.
* `c != 0` is not true so the algorithm stops. `count` was incremented thrice, and three is indeed the number of 1's in the binary representation of $c$.

---
Tags: algorithms, programming-languages, integers, binary, bit-manipulation
---


# Question
Title: find the strong component containing the vertex v
I'm trying to solve this question for practising purposes:

> "Describe a linear-time algorithm for computing the strong component containing a given vertex v. On the basis of that algorithm, describe a simple quadratic-time algorithm for computing the strong components of a digraph."

The question can be found here . It is question 31.

They give a couple of hints:

> "Partial solution: To compute the strong component containing s
>
> * Find the set of vertices reachable from s
> * Find the set of vertices that can reach s
> * Take the intersection of the two sets

> Using this as a subroutine, you can find all strong components in time proportional to t(E+V), where t is the number of strong components."

**My thoughts so far:**

1. In order to find the vertices reachable from s, I can to DFS (or BFS, but will stick with DFS) from s. If n is the number of vertices and m is the number of edges this takes O(n+m) time, which seem fine for the purpose. I need to safe every discovered vertex somewhere. Not sure which datastructure works best for this. I will come back to this problem later.
2. In order to find all vertices that can reach s, I could bild/compute the reverse of the graph and to another DFS from a again. Computing the reverse of the graph should be O(n+m) and the DFS is O(n+m). So in total I have 3\*O(n+m) which is just O(n+m). Of course the discovered vertices also need to be safed.
3. I'm not sure about how to build the intersection. Of course this is going to depend on how I saved the nodes before. So here are my ideas:

Building the intersection:

* If I saved the nodes in two separate arrays (one for the first DFS and one for the second) I possibly could use a Hash-Table. This should be O(|firstNodes| + |secondNodes|) time. Maybe this would be ok, since O(|firstNodes| + |secondNodes|) is smaller than O(n+m), but it doesn't seem optimal to me and it need extra space.
* What if I mark the nodes I discoverd with the first DFS. Then I do the second DFS and check if nodes are already marked. If yes, I mark them "special" as belonging the the strong component? I wouldn't have a list afterward that gives me the vertices of the strong component s belongs to but the strong component is still computed? For this approach I would need extra space at every node (in order to mark it).
* In order to find all strong compoonents in time proportional to t(E+V) I could then to the same procedure on a vertex that is not yet marked as belonging to a strong component -\> as long as there are such vertices, therefore t times. I would need to make sure, that every strong component is marked differently (e.g. increaing integers) and that the "I fould you" marks from the DFS are gone after each iteration (but not the marks for the strong components).

What do you think? What have I missed?
Thank you and happy Easter!

# Answer
Since you are not trying to write an optimal algorithm, like this one or that one, I suggest you do not try to optimize space usage too much, especially if the optimization only diminish the multiplicative constant, but not the asymptotic space complexity.

All your ideas are sound. During a BFS, since you need to check if vertices are seen or not, the common way to do it is to use a boolean array. Now for a strongly connected component, you will run two BFS's, and use two boolean arrays. The intersection can be computed by a index-wise AND.
> 1 votes

---
Tags: data-structures, hash-tables, depth-first-search, connected-components
---


title: Write the Context free Grammar

text:
# Question
Title: Write the Context free Grammar
What will be the context-free grammar of $B= A\_1.A\_2 $ when $A\_1 = \\{0^n1^n|n\geq 0\\}$ $A\_2 = \\{1^n0^n|n \geq 0\\}$ Also verify using a string.

if the Grammar for $A\_1$: $S\_1 \rightarrow 0S\_11 | \varepsilon$

$A\_2$: $S\_2 \rightarrow 1S\_20 | \varepsilon$

I am stuck with the value of $S \rightarrow$ ?

# Answer
Your grammars for $A\_1$ and $A\_2$ seem correct. Since you want to compute the concatenation of $A\_1$ and $A\_2$, you just need to express this fact with the start symbols of $A\_1$ and $A\_2$.

$S \rightarrow S\_1S\_2$ is a way to do it.

You can check by computing the derivation that creates the word $001110$.
> 2 votes

---
Tags: automata
---


# Question
Title: Algorithmic information theory with stochastic algorithms?
Suppose we define a class of algorithms that is allowed to sample i.i.d. Bernoulli bitstrings of arbitrary length, and use these to generate outputs. If we are allowed to use algorithms like this, then intuitively, "white noise" images like this one are easy to generate (i.e they have a low description length algorithm allowing random noise, even though it is essentially maximum k-complexity), namely we just run a for loop width x height times and pick black/white randomly.

I've tried to look online for "stochastic algorithmic complexity" and some other keywords, but haven't found anything relevant. **Is there a term that I can search for to read about this idea, of defining an algorithmic complexity measure of objects/classes of objects using algorithms that are allowed to use randomness?**

# Answer
One possible direction is looking at the (computational) hardness of distributions. For example, a family of distributions $\\{\mathcal{P}\_n\\}\_{n\in\mathbb{N}}$ where $\mathcal{P}\_n$ is a distribution over $\\{0,1\\}^n$ is called polynomialy-samplable (you can substitute here any other type of time/space restriction) if there exists a probabilistic polynomial time algorithm $A$ such that $A(1^n)\sim \mathcal{P}\_n$. Your white noise example translates in this case to the uniform distribution being easy (samplable). These notion often arise in average case complexity, where one cares about the average hardness of computing a function relative to some backgroud distribution over the inputs. A straightforward generalization of this would be to restrict the distance (total variation/KL) between $A(1^n)$ and $\mathcal{P}\_n$.

In any case, whenever one is interested in computational hardness, you would probably have to introduce a family of objects rather than talk about the complexity of a specific member.
> 2 votes

---
Tags: terminology, reference-request, information-theory, kolmogorov-complexity
---


# Question
Title: Language of decimal encodings of cubes is not regular
> Prove that the language that consists of cube numbers as strings is not regular.

I wanted to use pumping lemma but couldn't $$0, 1, 8, 27, 64, 125, 216, \dots$$

# Answer
> 1 votes
Denote your language by $L$. Suppose that the pumping length is $p$. Consider $$ N = (10^{p+1} + 1)^3 = 10^{3p+3} + 3 \cdot 10^{2p+2} + 3 \cdot 10^{p+1} + 1, $$ whose decimal encoding is $$ w = 1 0^p 3 0^p 3 0^p 1 \in L. $$ According to the pumping lemma, we can write $w = xyz$ so that $|xy| \leq p$, $y \neq \epsilon$, and $xz \in L$. Since $|xy| \leq p$, the part $xy$ lies within the prefix $10^{p-1}$. If $y$ contains $1$ then $xz$ has a leading zero, which is impossible (if you allow leading zeroes, consider $L \cap (1+9)(0+9)^\*$ instead), so $y$ consists only of zeroes. Hence $$ xz = 10^q 30^p 30^p 1, $$ for some $q \< p$, which encodes the number $$ n = 10^{2p+q+3} + 3 \cdot 10^{2p+2} + 3 \cdot 10^{p+1} + 1. $$ If $xz \in L$ then $n$ is a cube. Since $n$ ends with $1$, necessarily $n = 10m + 1$ (you can check this directly by considering $0^3,1^3,\dots,9^3$), and so $$ 10^{2p+q+3} + 3 \cdot 10^{2p+2} + 3 \cdot 10^{p+1} + 1 = 1000 m^3 + 300 m^2 + 30m + 1, $$ which implies that $$ (10^{p+q+2} + 3 \cdot 10^{p+1} + 3) 10^p = (100 m^2 + 30 m + 3) m. $$ Clearly $100m^2 + 30m + 3$ is divisible by neither $2$ nor $5$ (its units digit is $3$), and so $10^p$ must divide $m$. In particular, $m \geq m\_0 := 10^p$. However, this is impossible, since $N = (10m\_0 + 1)^3$, and $n \< N$.

---
Tags: regular-languages, automata
---


# Question
Title: Changing a matrix to become an ancestry matrix
An ancestry matrix $M$ for rooted tree $T$ is defined as $M\[ij\] = 1$ iff node $i$ is an ancestor of node $j$. Suppose we are given a matrix $X$. We can easily check that if $X$ is compatible with some rooted tree (and create the tree) or not.

The question is if $X$ is not an ancestry matrix, how hard is the problem of modifying elements of $X$ so that it becomes an ancestry matrix. The aim is to modify as few elements as possible.

**Note 1**: Stated problem can be seen as using Hamming distance on the matrices. A related problem would be: "For what metrics on the matrices this problem can be solved efficiently?"

**Note 2**: $X$ can be assumed to be a matrix containing only 0 and 1 elements. But a more general form of $X$ is more desirable!

**Note 3**: Any results about some characteristic matrix like adjacency matrix instead of ancestry matrix would be appreciated!

# Answer
> 1 votes
**TL;DR:** I prove the variant of this problem in which we can only change matrix entries from 1 to 0 is NP-complete. (I think the original version is NP-complete too, but haven't proved this.)

## Rooted Transitive Tree Editing

Another way of stating this problem is to ask for the minimum number of edge changes (additions of new edges or deletions of existing edges) needed to change a given digraph into the transitive closure of a rooted tree -- that is, a rooted tree augmented with all edges $uv$ whenever there is a path from $u$ to $v$. Let's call this graph a *rooted transitive tree*, and the decision form of this problem "Rooted Transitive Tree Editing":

Given a digraph $G=(V',E')$ and an integer $q$, is it possible to turn $G$ into a rooted transitive tree with at most $q$ edge edits?

I'll call the variant of the problem in which we are only permitted to delete edges "Rooted Transitive Tree Deletion". In the language of the original problem, in this variant we are only allowed to flip matrix entries from 1 to 0. **This deletion variant of the problem is NP-complete** by reduction from a slightly restricted form of Partition Into Triangles (PIT), as I'll show below. I suspect the full editing version can be shown to be NP-complete using a similar reduction, probably involving making the "handle" gadgets longer paths -- suggestions/extensions welcome!

The basic idea is to create a "triangle handle" vertex for each of the $O(n^3)$ triangles in the input graph, make each input vertex a descendant of the handle of every triangle it belongs to, and then look for a way to keep only the edges from the input graph that are used in a partition into triangles, and only the edges to handle vertices of triangles in this partition, deleting all other edges.

## Partition Into Triangles

In Partition Into Triangles, we are given an undirected graph with $3n$ vertices, and ask whether it is possible to partition the vertices into triangles. P. 192 of "Computers and Intractability: A Guide to the Theory of NP-Completeness" (Garey and Johnson, 1979) indicates this problem is NP-complete. Here we need a slightly restricted form of the problem in which every vertex is covered by some triangle. The following simple reduction from the general problem shows the restricted version is still NP-complete. Attach a separate "diamond" to each vertex -- that is, for each $v\_i, 1 \le i \le |V|$, add the vertices $x\_i$, $y\_i$ and $z\_i$, and the edges $v\_ix\_i$, $v\_iy\_i$, $x\_iy\_i$, $x\_iz\_i$ and $y\_iz\_i$. Every vertex in the modified graph is covered by a triangle, and since the only triangle covering $z\_i$ is $x\_iy\_iz\_i$, it must always be chosen, leaving $v\_i$ available as before.

## Construction

Let $G=(V,E)$ be the input PIT instance, with $|V|=3n$. Let $t$ be the number of triangles in $G$. Note that $t \le {|V| \choose 3}$ and can be computed in polynomial time. We construct an instance $R=(V', E', k)$ of RTTD as follows:

* Create a "plain" vertex $v\_i'$ for every vertex $v\_i \in V$.
* Create the directed "plain" edges $u\_i'v\_i'$ and $v\_i'u\_i'$ for every undirected edge $uv \in E$.
* For the $j$-th triangle $v\_av\_bv\_c$ in $G$:
    + Create a "handle" vertex $h\_j$.
    + Create the directed "handle" edges $h\_jv\_a'$, $h\_jv\_b'$ and $h\_jv\_c'$.
* Create a root vertex $r$, and directed edges from it to every other vertex.
* Set the threshold parameter $q$ to $3t+2|E|-2|V|$.

**$G$ is a YES-instance of PIT $\implies$ $R$ is a YES-instance of RTTD.** First notice that between any two adjacent vertices $u'$ and $v'$, at least one of the two opposite-pointing directed edges must be deleted. Also, for any triangle $v\_iv\_jv\_k$ in $G$, 3 of the 6 resulting directed edges in $R$ can be deleted so as to produce a transitive 3-path, e.g.:

```
vj
| \      Edges are directed from high to low
|  \
|   vi
|  /
| /
vk

```

A partition into triangles uses exactly $|V|$ edges in $G$. Given a partition of $G$ into triangles, we delete all $2(|E|-|V|)$ of the directed edges in $R$ corresponding to edges not used by the partition. For each triangle, we also delete 3 of the 6 directed edges so as to produce a transitive 3-path as shown in the above figure (the order of the vertices in the path is unimportant) -- this deletes a further $|V|$ edges. Finally, we delete directed edges from handle vertices to plain vertices for all unused triangles: There are $t-|V|/3$ unused triangles, each of which has 3 such edges. The final digraph is a rooted transitive tree, and we have deleted in total $2(|E|-|V|)+|V|+3(t-|V|/3)=3t+2|E|-2|V|=q$ directed edges, so $R$ is a YES-instance of RTTD.

**$R$ is a YES-instance of RTTD $\implies$ $G$ is a YES-instance of PIT.** We know there exists a subset of at most $q=3t+2|E|-2|V|$ directed edges, the deletion of which from $R$ yields a rooted transitive tree $R'$.

No directed edge from the root $r$ to any handle vertex can be deleted, since that handle vertex would then become a second vertex with indegree 0 (in addition to $r$), and a rooted transitive tree must have exactly one such vertex. Nor can a directed edge from $r$ to a plain vertex $v\_i'$ be deleted, since by the assumption that every vertex is covered by a triangle, $v\_i$ has some handle vertex $h\_j$ for an ancestor, and the deletion of $rv\_i'$ would imply the deletion of $rh\_j'$, which fails as just described.

The budget of directed edge deletions must therefore be allocated between handle edges and plain edges. If a vertex in $G$ participates in multiple triangles, its corresponding plain vertex in $R$ will have multiple handle vertices as ancestors -- but since no handle vertex is the ancestor of any other handle vertex, each plain vertex can choose at most one handle vertex to be its parent in the edited digraph $R'$, and must delete directed edges from all other handle vertices. Thus at most $|V|$ handle edges can survive, meaning that at least $3t-|V|$ handle edges must be deleted in any solution.

We now wish to show that plain edges will be deleted so as to ensure that each handle vertex is either totally "full" or totally "empty" -- that is, that for any handle vertex, either all 3 of its out-edges are preserved, or all 3 are deleted. Say that a vertex in $G$ is *assigned to triangle $j$* if $h\_jv\_i'$ is preserved in $R'$ (not deleted). Each triangle is assigned between 0 and 3 vertices, inclusive. We will show that any *valid* assignment -- that is, an assignment in which every triangle is assigned either exactly 0 or exactly 3 vertices -- preserves strictly more plain edges, and thus requires strictly fewer deletions of these edges, than any assignment in which some triangle is assigned 1 or 2 vertices.

A valid assignment preserves $|V|$ plain edges, meaning that $2|E|-|V|$ plain edges must be deleted, which together with the $3t-|V|$ handle edges that must be deleted requires a total of $3t+2|E|-2|V|$ edges.

Notice that for any pair of vertices assigned to distinct triangles, there must be no directed edges between their corresponding plain vertices in either direction in $R'$, so if these 2 directed edges exist (i.e., if the vertices are adjacent in $G$) they must both be deleted. IOW, triangle assignments group plain vertices into connected components in $R'$.

Take the assigned vertex counts of the $t$ triangles and sort them in decreasing order. Doing so with a valid assignment produces a list $L^\*=333\cdots3000\cdots0$, with $|V|/3$ 3s followed by $t-|V|/3$ 0s. Suppose we have an invalid assignment, producing a list $L$ containing at least one 1 or 2. We will walk along these 2 lists 3 or 6 *vertices* at a time, comparing the number of preserved plain edges.

* Each triangle assigned 3 vertices preserves 3 plain edges (see ASCII art diagram).
* Each triangle assigned 2 vertices preserves 1 plain edge.
* Each triangle assigned 1 or 0 vertices preserves 0 plain edges.

The longest common prefix of $L$ and $L^\*$, consisting of 3s, preserves an equal number of plain edges. Following this, $L$ continues with one of the following cases (with cases having trailing 0s promoted to equivalent cases having trailing 1s):

1. 111: Preserves 0+0+0=0 edges (vs. 3 edges for the corresponding 3 from $L^\*$).
2. 21: Preserves 1+0=1 edge (vs. 3 edges for the corresponding 3 from $L^\*$).
3. 2211: Preserves 1+1+0+0=2 edges (vs. 6 edges for the corresponding 33 from $L^\*$).
4. 222: Preserves 1+1+1=3 edges (vs. 6 edges for the corresponding 33 from $L^\*$).

Each case preserves strictly fewer edges than does the valid assignment, and any subsequent cases are at least as bad due to the decreasing order. Thus any invalid assignment requires strictly more plain edge deletions and at least as many handle edge deletions, so a solution with $3t+2|E|-2|V|$ edge deletions implies a valid triangle assignment, from which a solution to the original PIT instance can be immediately read off.

The above establishes NP-hardness of the RTTD problem. Clearly the construction takes polynomial time, so the problem is furthermore NP-complete.

---
Tags: algorithms, graphs, np-complete, trees, open-problem
---


title: Stack without duplicates

text:
# Question
Title: Stack without duplicates
I was thinking about the implementation of a DFS on graphs, and particularly about space complexity. The DFS algorithm can be implemented with a stack data structure. When a vertex $v$ is met during the exploration of the adjacency list of a vertex $w$, if $v$ has not already been processed, then $v$ is added to the stack. A vertex is marked a processed when it exits the stack (contrary to BFS, where a vertex is marked as seen when it enters the queue).

That way, the stack may contains duplicates during the execution of the DFS. Since each vertex is processed at most once, the size of the stack for a graph $(V, E)$ is $O(|V| + |E|)$.

Since I wondered if it was possible to get $O(|V|)$ space memory for the DFS, I tried to find a data structure of stack without duplicates. I found a solution for the DFS (given as an answer to this question), but the structure I found has restrictions: it works in space $\Theta(n)$ in the case I know in advance that the values entering the stack will be in $\[\\!\[0, n-1\]\\!\]$.

My question is: is there a more efficient way to implement a stack without duplicates (in a stack without duplicate, if I push an element already in the stack, then this element is put at the top of the stack, and the duplicate is deleted), in the general case where I don't know in advance the values entering the stack? The time complexity for operation of pushing/popping should be in $O(1)$ worst case, amortized or average case (in this order of preference). Also, is there a way to use $\Theta(n)$ space memory, $n$ being the current size of the stack (and not the maximal size).

# Answer
> 1 votes
Here is the solution I found. I suppose here that the values entering the stack will be in $\[\\!\[0, n-1\]\\!\]$. For that, I create an array $a$ of size $n$ that will implement a kind of doubly linked list: it is such that for $i \in \[\\!\[0, n-1\]\\!\]$, $a\[i\] = (p\_i, n\_i)$ where:

* if $i$ is not in the stack, $(p\_i, n\_i) = (-2, -2)$;
* if $i$ is in the stack, $p\_i$ (previous) is the value that is above $i$ in the stack ($-1$ if $i$ is the top of the stack) and $n\_i$ (next) is the value that is below $i$ in the stack ($-1$ if $i$ is the bottom of the stack).

The stack is then a couple $(i\_0, a)$, where $i\_0$ is the top element of the stack ($-1$ if the stack is empty).

That way, the usual operations on stack can be done in $O(1)$ worst case:

* testing emptyness: just check if $i\_0 = 1$ or not;
* pushing element $i$:
    + if $a\[i\] = (-2, -2)$, $a\[i\] \leftarrow (-1, i\_0)$ then $i\_0 \leftarrow i$
    + if $a\[i\] = (p\_i, n\_i)$ (duplicate case), then $a\[p\_i\] \leftarrow (p\_{p\_i}, n\_i)$, $a\[n\_i\] \leftarrow (p\_i, n\_{n\_i})$ (only if $p\_i/n\_i\neq -1$), $a\[i\] \leftarrow (-1, i\_0)$ then $i\_0 \leftarrow i$
* popping element: $i\leftarrow i\_0$, $i\_0 \leftarrow n\_{i\_0}$ $a\[i\] \leftarrow (-2, -2)$, return $i$.

In the case of the DFS, one can also add the case $a\[i\] = (-3, -3)$ to differentiate vertices that already exited the stack from the $a\[j\] = (-2, -2)$, vertices that have not already entered the stack. The array a can then replace the boolean array usually used.

---
Tags: graphs, data-structures, graph-traversal, stacks
---


# Question
Title: Distribution of $(X_1,X_2)$ if $X_1\pm X_2$ are two independent $N(1,4)$
$X\_1+X\_2$ and $X\_1-X\_2 $ are *i.i.d.* $N(1,4)$. What is the distribution of $X = (X\_1,X\_2)^T$?

I know *i.i.d.* is an independent and identically distributed random variable but I don't know how to use it to solve this problem that contains a column vector.

# Answer
> 1 votes
Let $Y = (Y\_1,Y\_2)$ be two i.i.d. $N(1,4)$ variables. Then $Y$ is a multivariate normal distribution, and so any affine transformation of $Y$ is a multivariate normal distribution. In particular, if we define $X\_1 = \frac{Y\_1 + Y\_2}{2}$ and $X\_2 = \frac{Y\_1 - Y\_2}{2}$ then $X = (X\_1,X\_2)$ is a multivariate normal distribution which satisfies $X\_1 + X\_2 = Y\_1$ and $X\_1 - X\_2 = Y\_2$. In other words, it is the random variable you're interested in.

It is routine to calculate $$ (X\_1,X\_2) \sim N\left(\begin{pmatrix} 1 & 0 \end{pmatrix}, \begin{pmatrix} 2 & 0 \\ 0 & 2 \end{pmatrix}\right), $$ that is, $X\_1 \sim N(1,2)$ and $X\_2 \sim N(0,2)$, and $X\_1,X\_2$ are independent.

---
Tags: probability-theory
---


# Question
Title: Irregularity of $\{ w_1 aa w_2 \mid |w_1| \neq |w_2| \}$
I'm currently struggling to come up with a proof that the following language is irregular: $$L\_2 := \\{w\_1aaw\_2 \in \Sigma^\* \mid w\_1, w\_2\in\Sigma^\* \land |w\_1| \ne |w\_2|\\}$$ where $\Sigma = \\{a, b\\}$.

Now quite intuitively, the language needs to know what $|w\_1|$ was in order to compare against $|w\_2|$, so it has to be irregular, but I'm failing to formally prove that.

I was able to solve the previous problem from the book, which was proving that (similarly) $$L\_1 := \\{w\_1aaw\_2 \in \Sigma^\* \mid w\_1, w\_2\in\Sigma^\* \land |w\_1| = |w\_2|\\}$$ is irregular, which was relatively simple using the pumping lemma.

So I thought maybe there was some kind of connection between the two problems, given that $L\_1\cup L\_2$ is regular, but there doesn't seem to be any kind of closure property I can robustly employ in order to prove that $L\_2$ is irregular.

Any ideas are welcome and many thanks in advance!

# Answer
> 7 votes
For $i \ge 0$ define $w\_i = b^i aa$. For any $i,j \ge 0$ with $i \neq j$ you have that $b^i$ is a distinguishing extension for $w\_i$ and $w\_j$. Indeed, $w\_i b^i \not\in L\_2$ but $w\_jb^i \in L\_2$.

Then the number of equivalence classes of the set $\\{ w\_i \mid i \ge 0\\}$ with respect to the equivalence relation "having a distinguishing extension" is not finite and, by the Myhill-Nerode theorem, $L\_2$ is not regular.

---

Here is an alternative solution that uses closure properties and the pumping lemma following the hint of Hendrik Jan.

Suppose that $L\_2$ is regular. Then so is $L' = \overline{L}\_2 \cap \\{b^i aa b^j\\} = \\{b^i aa b^i\\}$, which is easily shown to be non-regular using the pumping lemma.

Indeed, suppose that $L'$ was regular, and let $p$ be its pumping length. For some $k \in \\{1, \dots, p\\}$, the word $b^p aa b^p \in L'$ can be written as $b^k b^{p-k} aa b^p$ such that $b^{ki} b^{p-k} aa b^p \in L'$ for every $i \ge 0$. Nevertheless, for $i=0$ we have $b^{p-k} aa b^p \not\in L'$, yielding a contradiction.

# Answer
> 2 votes
You can also use the pumping lemma directly. Let $p$ be the pumping length, and consider the word $w = b^paab^{p+p!} \in L\_2$. According to the pumping lemma, there is a decomposition $w = xyz$ such that $|xy| \leq p$, $y \neq \epsilon$, and $xy^tz \in L\_2$ for all $t \geq 0$. Thus $y = b^q$ for some $q \in \\{1,\ldots,p\\}$. If we take $t = 1 + p!/q$ then $xy^tz = b^{p+p!}aab^{p+p!} \notin L\_2$.

---
Tags: regular-languages, finite-automata, pumping-lemma
---


# Question
Title: Is memorization necessary in learning computer science?
## Backgrounds

Hi guys, I am now trying to teach myself some basic computer science theories. Specifically, I am using the book, CSAPP (computer systems, from a programmer’s perspective) and 15-213 taught by CMU

## Question

My question is whether I need to memorize all the details covered in such theoretical courses (eg. the structure of an ELF file, the process of linking). If not, what is the methodology in approaching computer science theories.

This becomes even confusing when we have got searching engines now, considering we can always search for the facts that we need. If so, what is the purpose of learning? What shall we learn?

# Answer
> 2 votes
It's hard to answer what you "need", as that depends on your purpose, and hard to answer this question concretely, as it is very broad. I recommend you focus on learning concepts and ideas, as these are more likely to be of lasting use. Sometimes, though, to understand how some interesting capability is achieved, you will need to understand the details of how it is implemented. In general, if you pick a good textbook, then it's likely that there will be a lot of worthwhile material in there. Saying much more might require getting into specifics.

---
Tags: learning-theory, theory
---


title: Proof that a relation is in FP

text:
# Question
Title: Proof that a relation is in FP
How we can prove that the relation: $R= \left\\{0,1\right\\}^\*\times \left\\{0,1\right\\}^\* \in FP$
I understand that we need to find a polytime algorithm to decide whether $(x,y) \in R$ since $(x,y)\in R= \left\\{0,1\right\\}^\*\times \left\\{0,1\right\\}^\*$
How can we find this? And this is enough to prove that $R \in FP$?

# Answer
> 0 votes
To show that $R \in \mathsf{FP}$ you need to show that there is a deterministic poly-time algorithm $A$ that takes $x$ as input and outputs a $y$ such that $(x,y) \in R$.

A possible choice of $A$ is the algorithm that outputs $\varepsilon$ (the empty word) regardless of $x$. Indeed, $(x, \varepsilon) \in R$.

---
Tags: complexity-theory
---


# Question
Title: How can I make my algorithm more efficient?
I came across an algorithmic problem. I do not know how to do it optimally.

The problem is as follows:

> 1. There is an increasing array $A$ of size $n\_1$
> 2. There is an array $M$ of queries of size $n\_2$
>
> where $1 \le n\_1, n\_2 \le 10^7$
>
> For each query element $m \in M$, it is required to find the count of elements in array $A$ that are strictly less than the query element $m$.
> For example:
>
> > $A = \[1,2,3,5\]$
> > $M = \[4,2\]$
> > for $m = 4$ answer $3$
> > for $m = 2$ answer $1$

My idea works for a $O(nlogn)$. The algorithm is simple; for each request I do a binary search in array $A$. But can it be faster? Maybe B-tree?

# Answer
> 2 votes
If values in both arrays are positive integers, there is an algorithm in $O(n\_1 + n\_2 + \max(A))$. This algorithm is interesting if those three values are of the same order of magnitude.

The steps are as follow:

* check last element of $A$ to know $\max(A)$;
* create an array $B$ of size $\max(A)$;
* browse $A$ and modify $B$ so that $B\[i\]$ represents the smallest index $j$ such that $A\[j\] \geq i$ (that means the number of elements of $A$ that are $\<i$);
* browse $M$; for $m \in M$, if $m \> \max(A)$, return $n\_1$, else return $B\[m\]$.

---
Tags: trees, binary-search
---


# Question
Title: Is there a bound on possible Dead state in a minimized DFA
I want to know if a DFA is minimized, is there an upper bound on how many dead states are possible when it is in its minimal form, in terms of number of states, etc?

Intuitively, I am thinking that it is at most one, because if other state is there from where accept state is not reachable, the minimization would merge the states, because it is serving no more purpose than the other dead state. Is my intuition true?

# Answer
> 2 votes
If you allow the DFA to be trimmed, then you can delete ALL dead states. If you want the DFA to be complete, then the minimized DFA will indeed have at most one dead state.

The reason is that minimizing leads you to merge nondistinguishable states, that is equivalent states in the Myhill-Nerode equivalence relation (here the definition is given for words and languages, but it can be extended to automata).

Two states $q\_1, q\_2$ are distinguishable if there exists a word $u$ such that $\delta^\*(q\_1, u)$ is final and $\delta^\*(q\_2, u)$ is not (or the converse). If $q\_1, q\_2$ are two dead states, then $\delta^\*(q\_1, u)$ can never be final (and same for $q\_2$), so $q\_1, q\_2$ will never be distinguishable.

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


# Question
Title: Theta bound for runtime analysis of nested while loops
I am trying to fully analyze the running time of $\texttt{nestedLoops}$ in terms of $n$ with a Theta bound.

The Java code I have is as follows:

```
public void nestedLoops(int n) {
     int i = 1;
     while (i < n) {
          int j = i;
          while (j > 1) {
               int k = 0;
               while (k < n) {
                    k += 2;
               }
               j = j // 2
          }
          i *= 2
     }
}

```

I know that the innermost while loop has an obvious runtime of $\lceil \frac{n}{2} \rceil$. But I get stuck on the next while loops. I think the middle while loop has a runtime of $\lfloor \log\_2\texttt{i} \rfloor$, but that is very confusing for me.

Any help would be taken with much gratitude.

# Answer
The innermost loop has running time $\Theta(n)$. The middle loop runs for $\Theta(\log i)$ iterations. If $2^m \< n \leq 2^{m+1}$, this means that the total running time is proportional to $$ n (\log 1 + \log 2 + \cdots + \log 2^m) = n \log 2(0 + 1 + \cdots + m) = \Theta(n m^2) = \Theta(n\log^2 n). $$
> 0 votes

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


# Question
Title: NOT satisfiable 3SAT instance certificate
Given a NOT satisfiable 3SAT instance, that we say $S$. Suppose that $M$ is a minimal subset of clauses of $S$ such that $M$ is NOT satisfiable. Say $X$ the subset of variables of $S$ that belong to the clause of $M$. For each Boolean values combination of the variables of $X$, we have a clause of $M$ that is *false*, because $M$ is NOT satisfiable.

The question is: is $M$ a polynomial certificate that $S$ is NOT satisfiable? I mean: if we have $M$, we can check that, for each possible Boolean value of the variables that are in $X$, there is a *false* clause in $M$. This means that $M$ is a certificate that $S$ is NOT satisfiable. Because each clause is *false* for only one Boolean value of the variables that are in the clause and becasue $M$ is minimal, the number of cases, that we have to check to verify that $M$ is NOT satisfiable, is the cardinality of $M$ (i.e. the number of clauses in $M$). Threfore the complexity of the certificate is linear on the number of clauses of $M$ (therefore linear on the number of clauses of $S$).

Here an example.
If $X=\left\\{a,b,c\right\\}$, $M$ contains all possibile combinations, three by three, of $\left\\{a,b,c,\bar{a},\bar{b},\bar{c}\right\\}$ ($9$ literals in all), without that a variable and its negation appear in the same clause (it would be a tautology). Therefore the number of clauses of $M$ is exponential on the number of the variables of $X$, but the number of clauses of $M$ is at most the number of clauses of $S$. In other word we have $cardinality(X)=O(\log(numberClauses(S)))$.

# Answer
A CNF which is not satisfiable is usually called *unsatisfiable*. A CNF which is unsatisfiable but becomes satisfiable if we drop any clause is *minimally unsatisfiable*.

Papadimitrious and Wolfe constructed, in their paper The complexity of facets resolved (Lemma 1), a polynomial time reduction $f$ from CNFs to CNFs such that:

* If $\varphi$ is satisfiable then $f(\varphi)$ is satisfiable.
* If $\varphi$ is unsatisfiable then $f(\varphi)$ is minimally unsatisfiable.

It is likely that this can be extended to a reduction from 3CNFs to 3CNFs.

This reduction shows that the minimally unsatisfiable case is the "hardest". In particular, if there is an efficient way to check that a minimally unsatisfiable CNF is unsatisfiable, then P=NP.
> 5 votes

---
Tags: complexity-theory, satisfiability, 3-sat
---


title: Count the possible plans for nurses

text:
# Question
Title: Count the possible plans for nurses
I am new to Algorithms and Competitive Coding. I read an exercise paper given by my teacher as below:

> The director of a hospital want to schedule a working plan for a nurse in a given period of N consecutive days 1,..., N. Due to the policy of the hospital, each nurse cannot work all the days 1,..., N. Instead, there must be days off in which the nurse need to take a rest. A working plan is a sequence of disjoint working periods. A working period of a nurse is defined to be a sequence of consecutive days on which the nurse must work and the length of the working period is the number of consecutive days of that working period. The hospital imposes two constraints:
>
> Each nurse can take a rest only one day between two consecutive working periods. it means that if the nurse takes a rest today, then she has to work tomorrow (1)
>
> The length of each working period must be greater or equal to K1 and less than or equal to K2 (2)
>
> The director of the hospital want to know how many possible working plans satisfying above constraint?
>
> input
>
> 6 2 3
>
> output
>
> 4

I have thought a lot and just give an initial idea: I will use an 1-D array to represent a schedule from day 1 to day N. for each day (ith day), I have two choices: the nurse will work this day or the nurse will not work on this day.

If the nurse does not work on the ith day, the ways for this case is the total ways of the ith-2 day. (Because she must have a day off on the previous day.

Else, the ways for this case will be the sum of total ways of the ith-j day, with j in \[K1, K2\].

However, I do not know why I am wrong and which way will be the correct answer. I really need your help to derive an appropriate algorithm

# Answer
> 0 votes
You can solve this problem with dynamic programming. Your states are dp\[day\_number\]\[worked\_sofar\]. here is a recursive implementation:

<pre><code>#include<bits/stdc++.h>

using namespace std;

vector<vector<int> > dp;
int n, k1, k2;
int solve(int day, int sofar){
    if(day > n || sofar > k2)return 1;
    if(dp[day][sofar] != -1)return dp[day][sofar];
    int ans = solve(day + 1, sofar + 1);
    if(sofar >= k1)ans += solve(day + 1, 0);
    return dp[day][sofar] = ans;
}

int main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    cin >> n >> k1 >> k2;
    dp.assign(n + 1, vector<int>(k2 + 1, -1));
    cout<<solve(1, 0);
    return 0;
}

```
</code></pre>

# Answer
> 0 votes
The above answer from @Usman is almost right, except for the return condition part.

The `sofar` part needs to be exactly $0$ (if the nurse takes a day off) or in between $k\_1$ and $k\_2$.

Here is the correct version:

```
if (sofar > k2) return 0;
if (day >= 2) {
    if (sofar == 0 || sofar >= k1) return 1;
    else return 0;
}

```

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


# Question
Title: Closure of regular languages under interchanging two different letters
Given any deterministic finite state automata $M$ over any alphabet, I need to construct an FSA $M'$ that accepts the set of strings $M$ accepts, but with two different letters interchanged. For example, if $M$ only accepts $101$, $M'$ should only accept any element from $\\{011, 110\\}$.

Suppose a string accepted by $M$ has $n$ letters, I tried to construct an FSA with a parallel structure, with initial state $q\_0$ that has $\epsilon$ transition to $M\_1, M\_2, \dots, M\_{\binom{n}{2}}$, where each $M\_i$ accepts strings with two letters at two unique positions interchanged. The final states should be $F\_1, F\_2,\dots,F\_{\binom{n}{2}}$. Then I may claim that $M'$ should accept their union.

But I am not sure how to construct this parallel structure. Specifically, how should I construct the transition function of this parallel structure that restricts a single interchange only for any $M\_i$?

# Answer
Suppose that you guess that $\sigma$ and $\tau$ should be exchanged, where $\sigma$ appears before $\tau$ (in the original word).

You start reading the input word, letter by letter. When you encounter $\tau$, you can optionally act as if you read $\sigma$. Later on, when you encounter $\sigma$, you can optionally act as if you read $\tau$. From that point on, you accept the word if the original DFA accepted it.

Here is how to implement this in an NFA. Let the original DFA have states $Q$, initial state $q\_0$, final states $F$, and transition function $\delta$. We construct a new NFA whose states are $\Sigma \times \Sigma \times Q \times \\{0,1,2\\}$. The initial states are $\\{(\sigma,\tau,q\_0,0) : \sigma \neq \tau\\}$. The final states are $\Sigma \times \Sigma \times F \times \\{2\\}$. The most complicated bit is the transition function $\delta'$:

* For $\kappa \neq \tau$, $\delta'((\sigma,\tau,q,0),\kappa) = \\{ (\sigma,\tau,\delta(q,\kappa),0) \\}$.
* $\delta'((\sigma,\tau,q,0),\tau) = \\{ (\sigma,\tau,\delta(q,\tau),0), (\sigma,\tau,\delta(q,\sigma),1) \\}$.
* For $\kappa \neq \sigma$, $\delta'((\sigma,\tau,q,1),\kappa) = \\{ (\sigma,\tau,\delta(q,\kappa),1) \\}$.
* $\delta'((\sigma,\tau,q,1),\sigma) = \\{ (\sigma,\tau,\delta(q,\sigma),1), (\sigma,\tau,\delta(q,\tau),2) \\}$.
* $\delta'((\sigma,\tau,q,2),\kappa) = \\{ (\sigma,\tau,\delta(q,\kappa),2) \\}$.
> 1 votes

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


# Question
Title: Are there decidable non-trivial properties of a LBA's accepted language?
The halting problem and therefore the acceptance problem are decidable for LBAs, but are the infinite extensions of these problems decidable?

Given a LBA, can you decide whether there exists an input on which the LBA halts? Given a LBA, can you decide whether the LBA accepts a certain non-empty, non-finite language?

# Answer
Given a Turing machine $M$, you can construct an LBA $A$ that given as input a word of length $n$, it simulates $M$ on the empty tape as long as $M$ uses up to $n$ space, and the moment $M$ exceeds space $n$, it enters an infinite loop. In contrast, if $M$ ever halts, then $A$ also halts. Thus $A$ halts on some input iff $M$ halts on the empty input.

You can try to show that the second property is undecidable using a similar argument.
> 1 votes

---
Tags: undecidability, linear-bounded-automata
---


title: Is it decidable whether a TM is a LBA?

text:
# Question
Title: Is it decidable whether a TM is a LBA?
Given an arbitrary TM, can you decide whether it's a LBA?

# Answer
An LBA is limited to working only on the space defined by the input. That means it won't ever move right on reading a blank space (if your model doesn't allow writing blank, only a fake blank, that is). That is easy to check by looking at the transitions of the TM.

To check if the language is accepted by an LBA is undecidable by Rice's theorem.
> 1 votes

# Answer
No, assume towards contradiction you would have been able to solve it, with some Turing machine $M$. Notice, that it's easy to check given an LBA whether it halts or not (there are a finite number of total possible states) and let's call a TM that solves this by $M'$.

Now, let us construct the new Turing machine $\hat M$ that will solve the halting problem: Given $\langle T,x \rangle$ we want to decide if $T$ halts on $x$.

* Run $M$ with input $\langle T\_x \rangle$, where $T\_x$ is a Turing machine that ignores the input and computes $T(x)$.
* If the answer is false, then also return false.
* If the answer is true, then we know that $T\_x$ is an LBA, and use $M'$ to decide whether it halts or not.

I will leave verifying this proof and completing it to you.
> 0 votes

---
Tags: turing-machines, linear-bounded-automata
---


title: If a point is a vertex of convex hull

text:
# Question
Title: If a point is a vertex of convex hull
The exercise is

> Given a set of point $S$ and a point $p$. Decide in $O(n)$ time if $p$ is a vertex of convex polygon formed from points of $S$.

The problem is I am a little bit confused with time complexity $O(n)$. The more naive solution would be to construct convex polygon in $O(n\log n)$ and test if $p$ is one of the vertices.

# Answer
> 8 votes
Hint: the point $p$ is a vertex of the convex hall iff there are two half-lines from it such that all points fall inside the angle created by them.

Here is an idea for an algorithm based on this hint:

> Design an algorithm with two variables $q$ and $r$ (input points). The algorithm will examine each of the input points and will update $q$ and $r$ so that all points checked so far fall inside the wedge $\angle qpr$.

# Answer
> 8 votes
The problem is to find a line that passes through $p$ and has all the other points in $S$ on one side. This is a two-dimensional linear-programming problem, so it can be solved in $O(n)$ time using textbook geometric algorithms. But let me describe a self-contained solution.

---

To simplify notation, translate all the points so that $p$ is the origin $(0,0)$, and let $Q = S\setminus\\{p\\}$. Then we want to determine if there is a real number $m$ such that either (1) $y \< mx$ for all $(x,y)\in Q$ or (2) $y \> mx$ for all $(x,y)\in Q$. In the first case, $p$ is a vertex of the upper hull of $S$; in the second case, $p$ is a vertex of the lower hull of $S$. I'll describe an algorithm for the first case; the other case is symmetric.

If any point in $Q$ lies directly above $p$ (that is, if any point in $Q$ has coordinates $(0,y)$ for some $y\>0$), then $p$ cannot lie on the upper hull. It is easy to check this condition in $O(n)$ time.

So assume no points in $Q$ lie directly above $p$. The $y$-axis splits $Q$ into two subsets $L$ (left) and $R$ (right). Points in $L$ have negative $x$-coordinates, and points in $R$ has positive $x$-coordinates. (Points directly below $p$ don't matter; just ignore them.) Let $$ m\_L = \min\_{(x,y)\in L} \frac{y}{x}, \quad M\_R = \max\_{(x,y)\in R} \frac{y}{x}, \quad \text{and} \quad m = \frac{m\_L + M\_R}{2}. $$ Now there are three cases to consider:

* If $m\_L \< M\_R$, then every point in $Q$ lies strictly below the line $y = mx$, so $p$ is a vertex of the upper hull.
* If $m\_L = M\_R$, then the line $y=mx$ passes through a point in $L$ and a point in $R$, and no point in $Q$ is strictly above that line. So $p$ lies on an edge of the upper hull, but it is not a vertex.
* If $m\_L \> M\_R$, then at least one point in $L$ and at least one point in $R$ lie strictly above the line $y=mx$. So $p$ lies strictly below the upper hull.

It is easy to compute $m\_L$ and $M\_R$ in $O(n)$ time. We don't actually need to compute $m$.

# Answer
> 1 votes
I think that the accepted answer is too sketchy, and the answer by Jeff Erickson is too complex - so my two cents are below.

For all points $q \in S$ calculate an **oriented** angle between the basis vector $e\_x=(1,0)$ (or any other non-null vector - it's your choice) and the vector $\vec {pq}$. These angles will be in the $\[0, 2\pi)$ semi-closed interval. Find minimum $\alpha\_{min}$ and maximum $\alpha\_{max}$ for all such angles. The point $p$ belongs to the convex hull of the set $S$ if and only if the difference $\alpha\_{max}-\alpha\_{min} \< \pi$. Obviously all that can be done in $O(n)$ time.

---
Tags: algorithms, computational-geometry
---


# Question
Title: How do Kruskal's and Prim's algorithms compare to each other?
I understand that both of them are used to find minimal spanning trees, and I've seen their implementations, but I don't understand how both of them compare to each other, and how they differ in complexity.

# Answer
A tree in a graph is a connected acyclic subgraph. A spanning tree in a graph of order $n$ is a connected acyclic subgraph of order $n$ or equivalently a connected acyclic subgraph with $n-1$ edges.

Prim's algorithm consists of building a spanning tree by adding edges (and corresponding vertices), always keeping the **connected** and **acyclic** property, until the tree contains all vertices. The complexity of the algorithm is detailled here: it is $O(|E|\log |V|)$ with binary heaps, and $O(|E| + |V|\log |V|)$ (which is slightly better in general case) with Fibonacci heaps, a complicated data structure.

Kruskal's algorithm consists of building the spanning tree by adding edges always keeping the **acyclic** property, until there are $|V|-1$ edges. Its complexity is detailled there. It is $O(|E|\log|V|)$, but if the edges can be easily sorted, you can reach $O(|E|\alpha(|V|))$ with improved union-find data structure ($\alpha(x)$ is in practice very small, that is $\leq 4$ even if $x$ is the number of particles in the universe).

Both of them are greedy algorithms, but the property you keep invariant is not the same.
> 2 votes

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


# Question
Title: How to find the largest power of two divisor of a given integer?
Given an integer $x$, I need to find the largest power of two $p = 2^n$ that divides $x$ such that the remainder is zero.

When $x$ is zero, the algorithm should return zero. For odd numbers, it should return one, since the largest power of two that divides these numbers is $2^0$.

How to write an algorithm for this? (any programming language would do, or pseudocode)

# Answer
After reading through your question carefully, it is clear that this is not actually the Find First Set-operation as others have answered as Find First Set would give you the largest value $n$ for which $p = 2^n$ is a factor of your number, whereas what you where asking for was the corresponding $p$.

This is good as the final step from your question to FFS is the most complicated part.

Assuming that your numbers are in a normal two's-complement encoding, the result should be a number with the same trailing zeroes and lowest one bit (if present) as $x$ and the remaining bits set to zero.

Using a few bit-twiddling hacks we can find the result in just a few steps:

* Take the bitwise inverse of $x$ to get a number that has all bits set differently.
* Add one to the inverse to restore only the trailing zeroes and the lowest one.
* Take the bitwise and between this value and the original number to set all bits not affected by the previous step to zero.

As these are very simple instructions they should exist in pretty much any language you can think of, and they usually look the same.

For example this is how it looks in C, C++, Python, Java, and Javascript: `p = x & (~x + 1)`

If anyone has an example of a language where it looks different, please add a comment.

**Edit**:
A simplification that was previously overlooked is using that `-x` in two's complement is defined as `~x + 1` giving the even shorter code of `p = x & -x`.
> 10 votes

# Answer
You just need to count the number of $0$ at the end of the binary encoding of $x$.
> 12 votes

# Answer
Your operation is known as find last set, count trailing zeroes, bit scan forward, and possibly other names. Many modern CPUs support it natively. On Wikipedia you can find several fast implementations.
> 7 votes

# Answer
This really depends on your computing platform and how your integer is represented (and how big it might be). If we're talking about an integer which fits into a single register of your real-world computer, then as @YuvalFilmus writes, there are often assembly language instructions like "find first set" or "count trailing zeros" which perform this computation directly. If you're using a compiler like GCC or clang, and a C-like/C-friendly language, you can use these via a compiler builtin, e.g. `__builtin_ffs()`/`__builtin_ffsl()` etc. See:

for their exact semantics.

However, if your integer is of arbitrary length, things are different... if it's still in binary representation, then - you're essentially looking for the first non-zero byte or word; and within that word you're back to the previous case. This takes $O(n)$ operations, naturally.

If the representation is available more opaquely (e.g. you are only allowed to perform arithmetic operations on it, as in the Blum-Shub-Smale model) then again things are different - and perhaps slightly more interesting: You could then try a binary search for the power $n$ of the greatest power-of-two divisor. That should take $O\\!\left(\log(n)\right)$ operations.

On the other hand, if the representation is in a non-power-of-2 basis, you might be in a bit of a bind, and I'm pretty certain it would be an $\Omega(n)$ algorithm. A straightforward thing to do would be changing the base of $x$ to base 2 (and I'm not sure you can do much better).
> 5 votes

---
Tags: bit-manipulation
---


# Question
Title: What is name of type " Function->Value->Bool = if (Bool) Function (Value) " in Category theory?
I am very new to functional programming so sorry if the question is stupid.

Having this function

```
const noname = func => val => bool => bool? func(val) : val

```

And following situation

```
// if event.target has css class 'draggable-box' , add drag listener to it, using event
compose(
    noname( add_drag_listener )(event),
    elem_has_css_class('draggable-box'),
    prop('target'),
)(event)

```

In Category theory, what is the correct name for the `noname` function? Is there such a type?

# Answer
I don't believe that there is a standard category theory name for this, because of the Boolean argument. So what this function means would depend on how that is constructed.

In what follows, I'm going to change the argument order by putting that Boolean first.

If you encode the Boolean using Church encoding, the function would look like this in lambda calculus:

$$\lambda b. \lambda f. \lambda x. b\\,(f\\,x)\\,x$$

This doesn't look especially standard to me. In Haskell, the function is called `applyWhen`.

Interpreting the Boolean as a subobject classifier in an elementary topos is left as an exercise.
> 1 votes

# Answer
Maybe currying is the syntax you refer, and passing arguments as functions:

```
const sum = (a, b, c) => a + b + c;
const partial = a => b => c => sum(a, b, c);

console.log(partial(1)(2)(3));          // 6
```
> 0 votes

---
Tags: functional-programming, category-theory
---


title: FPT algorithm for 1-BDD

text:
# Question
Title: FPT algorithm for 1-BDD
Given a graph $G = (V,E)$ and an integer $k$, the 1-BDD problem asks if there exists a subset $D$ of at most $k$ vertices such that the degree of any vertex in $G\[V \setminus D\]$ is at most one.

Is there any FPT algorithm for the above problem running in time $O^\*(2^k)$?

# Answer
Let $v$ be an arbitrary vertex in your graph, of degree $d$. In any solution $D$, either $v \in D$, or at least $d-1$ of its neighbors are in $D$. In this case, we have one branch with parameter $k-1$, and $d$ branches with parameter $k-(d-1)$ (which is progress as long as $d \geq 2$).

If $d = 1$, then we can say more. Let $u$ be the unique neighbor of $v$. If $D$ is any feasible solution, then so is $D \setminus \\{v\\} \cup \\{u\\}$. In other words, we can assume without loss of generality that any solution does not contain $v$. Any such solution either contains $u$ or all neighbors of $u$ apart from $v$. If $u$ also has degree $1$ then there is clearly a solution not containing either $u$ or $v$, so we can assume that in this case $u$ has degree at least $2$. In this case, we have one branch with parameter $k-1$, and one branch with parameter $k-(d-1)$.

Denoting by $T(k)$ the worst-case size of the search tree when the parameter in $k$, our ideas so far show that $$ T(k) = T(k-1) + \max\_{d \geq 2} (dT(k-(d-1)). $$ Unfortunately, if we choose $d = 2$ then we get $T(k) \geq 3T(k-1)$, whose solution is $T(k) = \Omega(3^k)$.

We can improve on this algorithm by noting that if all vertices have degree $2$ then the problem is easy to solve, since the graph is a union of disjoint cycles, and a cycle of length $\ell$ requires spending $\lceil \ell/2 \rceil$ vertices of $D$. Hence either $v$ has degree at least $3$, or $v$ has degree $1$ (and $u$ has degree at least $2$). This leads to the improved recurrence $$ T(k) = T(k-1) + \max(T(k-1),\max\_{d \geq 3} dT(k-(d-1))). $$ Unfortunately, if we choose $d = 3$ then we get $T(k) \geq T(k-1) + 3T(k-2)$, whose solution is $T(k) = \Omega(\bigl(\frac{\sqrt{13}+1}{2}\bigr)^k)$, with a base of roughly $2.3$.

We can improve on this as follows. We can assume that the minimum degree is $2$. Let $v$ be a vertex of degree $d \geq 3$. Any solution either contains $v$, or all of its neighbors, or it contains all but a single neighbor $w$, and all the remaining neighbors of $w$. This leads to one branch with parameter $k-1$, one branch with parameter $k-d$, and $d$ branches with parameters at most $k-d$. Thus $$ T(k) = T(k-1) + \max(\max\_{d \geq 1} T(k-d), \max\_{d \geq 3}(T(k-d) + \max\_{e\_1,\ldots,e\_d \geq 2} T(k-(d-1)+(e\_1-1)) + \cdots + T(k-(d-1)+(e\_d-1)))). $$ Using monotonicity, this reduces to $$ T(k) = T(k-1) + \max(T(k-1), \max\_{d \geq 3} (d+1)T(k-d)). $$ Using base case of $T(0) = 1$, we can prove by induction that $T(k) = 2^k$. The lower bound is clear. For the upper bound, we need to prove that $(d+1) 2^{k-d} \leq 2^{k-1}$ for all $d \geq 3$, which reduces to $d+1 \leq 2^{d-1}$, an inequality which can be checked directly.
> 4 votes

---
Tags: algorithms, graphs, parameterized-complexity, vertex-cover
---