No need to rename a free variable in substitution?

Yes, it is all correct.

Lambda-calculus may be just taken as a formal system, with rules to be
followed. Period.

However, it may be useful to try to understand intuitively why the
rules are what they are.

So the following is very informal and should be taken as an attempt at
answering intuitively.

Consider whether the following expressions are equivalent:

$y$ and $z$ : they are not equivalent because a substitution on $y$ has
no effect on $z$, and conversely. The variables $y$ and $z$ are free
variables. They stand for themselves, or for
whatever value is associated to them in an environment where you
evaluate the expression, or by a substitution. Changing a free
variable for another (it is not renaming in such a case) will change
what you get in the environment, or by applying a substitution (which
amounts to the same).
$\lambda y. (x\,y)$ and $\lambda z.(x\,z)$ : they are equivalent
via alpha conversion. When applied to the same argument, and more
generally when used in the same context, they will always give the
same result. The variables $y$ and $z$ are bound variables. Renaming
a bound variable can be done at any time,
independently of the context, without ever changing the behavior of
the $\lambda$-abstraction.

The renaming in your example $ \lambda y. (x\,y) [x:=y] = \lambda
z.(y\,z)$ is needed because the $y$ in the substitution is a free
variable (possibly taking a value in whatever environment or
substitution may be provided). Without the renaming, it would be
undistinguisable from the bound variable of the $\lambda$-abstraction
once the substitution is performed. To avoid that, the bound variable
is renamed, since renaming it does not matter.

Contrarily, in the expression $(x\,y)[x:=y]$, both occurences of $y$
stand for the same free variable $y$ in the current environment. There
is no reason to try distinguishing them.


What is the name of the problem? (partitioning graph into three covers)

Your problem can be solved in linear time, by reduction to 2SAT. For each vertex $v$ we will have three variables $v_R,v_B,v_G$ and clauses $\lnot v_R \lor \lnot v_B,\lnot v_R \lor \lnot v_G, \lnot v_B \lor \lnot v_G$. These ensure that at most one of $v_R,v_B,v_G$ is true. For each edge $(v,w)$ labeled $R$, we will add the clause $v_R \lor w_R$. If there is a valid vertex coloring in your sense, then it clearly translates to a solution of this 2SAT instance. Conversely, any solution to the 2SAT instance corresponds to a partial coloring in which each edge is incident to a vertex with the same color. Coloring the other vertices arbitrarily, we obtain a valid vertex coloring in your sense.


Is converting boolean formulas to sum-of-products a hard problem?

Your reasoning is correct.  Your "sum-of-products" is more commonly known as disjunctive normal form (DNF).  It is easy to show that conversion from conjunctive normal form (CNF) to DNF is NP-hard, so converting from general Boolean formulas to DNF can't be any easier.


Can you complete a basis in polynomial time?

The result of the Gram-Schmidt can be expressed in determinantal form, see Wikipedia. This shows that the output of the Gram-Schmidt process is polynomial size. This suggests that if you run the classical Gram-Schmidt process, then all intermediate entries are also polynomial size (even in LLL, all intermediate entries are polynomial size). However, even if it is not the case, then using efficient algorithms for computing the determinant (see my other answer), you can compute the Gram-Schmidt orthogonalization in polynomial time.


How to write recurrence relation for backtracking problem?

Recurrence relation is for n*n board $T(n)=n*T(n-1)+O(n^2)$ but  think it should be $T(n)=T(n-1)+O(n^2)$ as if we put the queen anywhere in first row, we are left with $(n-1)*(n-1)$ board and it is sub-problem for T(n-1). But how n gets multiplied is not understandable.

How many cells are there in the first row? $n$. That is where the factor $n$ come from.

We put the Queen in the first cell of the first row. Removing the first row and first column, we then check the remaining $(n-1)*(n-1)$ board.
We put the Queen in the second cell of the first row. Removing the first row and second column, we then check the remaining $(n-1)*(n-1)$ board.
$\vdots$
We put the Queen in the last cell of the first row. Removing the first row and last column, we then check the remaining $(n-1)*(n-1)$ board.


Any significance to why a lot of big names in AI have math PhD?

All computer science is born out of Math.  The are a lot of computer programmers, web designers and the like who may not have math background, but they do not count as as computer scientist.

AI and other machine learning is all based on Math and statistics, so even going for a PhD in AI would mean that would have to learn a significant amount of math anyway.


If $\varepsilon \in L$, then necessarily $\varepsilon \in L^+$ (and the converse as well). This is because $L$ itself is contained in $L^+$ and $L^+$ is defined as the union over the powers $L^i$ of $L$ for $i \in \mathbb{N}_+$. Note $L^+$ is not defined as $L^\ast \setminus \{ \varepsilon \}$; this is a common mistake.

Hence, $\varepsilon \not\in L^+$ holds if and only if $\varepsilon \not\in L$. This is the case for the alphabet $\Sigma$, hence why it is correct in the first case.


Many compilers, gcc included, are divided into two major parts: a front-end and a back-end. The front end is in charge of compiling the input language into some sort of intermediate form, and perform some of the optimization. The back-end takes this intermediate form and generates actual machine code. You only need to construct a new back-end (or even less than that). Luciano in his answer gave you a good pointer regarding that.


Dividing a weighted planar graph into $k$ subgraphs with balanced weight

If the graph is sparse, may be it's also bounded tree width. Then we can find the optimum cut by using dynamic programming for graphs of bounded treewidth1. To check whether it's a bounded tree-width or not there are some tools and you can use them. On the other hand, one (may be good) heuristic approach is finding maximum spanning tree. This can be done by negating edge weights and running Kruskal algorithm to find MST. Because the graph is sparse then heaviest cuts along this tree are not bad, also good cut for tree can be found by bottom up dynamic programming approach. (I think it's in factor of at most 5 with high probability in most cases).

1: I didn't think about it, but seems to be as usual.


NP is a class of decision problems, while #P is a class of functions. If a function $f$ is in #P then the decision problem $L = \{ x : f(x) > 0 \}$ is in NP.

As far as I know, it is not expected that for every $f$ in #P, the decision problem $L = \{ (x,y) : f(x) = y \}$ is in NP. In particular, it is not clear how you would verify non-deterministically that a given non-deterministic machine has exactly $y$ (or even at most $y$ or at least $y$) accepting paths (where $y$ is encoded in binary; if it's encoded in unary, then the task is perfectly possible). Do you have any suggestions?


minimum moves for Knight on a infinite chessboard

With obstacles, you can use an algorithm as it is used for routing the shortest car distance. The idea is that you perform a search not breadth first, but with moves first that get you closer to the target. And you start from both ends and meet in the middle.

Define the "optimal distance" between points as the distance given by the algorithm for lowest number of moves without obstacles. At the starting point, find all neighbouring points, and for each calculate a lower bound for the number of moves to the target: One initial move, and the moves for the closest distance to the target. Then the same from the other end. Next you examine those points with the lowest lower bound. All moves are eventually evaluated, bot you tend to check those first that get you closer to the target.


Unsupervised anomaly detection: assigning the clusters to normal and anomaly

The radius depends on the number of clusers you choose. The more clusters, the smaller the radius.

If you have labelled data, you could eliminate the outliers/anomalies for determining the threshold radii for your clusters. For example you could take the greatest distance from the cluster center to its members (smaller radius for higher detection rate as stated in your question).

This question is closely related to the question Anomaly/outlier detection using fuzzy clustering. I am reposting my answer:

As far as I know there is no unique definition for what is an outlier/anomaly. Therefore you'll have to decide by yourself what the characteristics of outlying data points in your data set are. This could be for example: distance to the cluster center (threshold), local neighbourhood (a data point that has no/few data points in its neighgbourhood might be an outlier) or statistical characteristics (an outlier doesn't 'fit' to the distribution of a cluster, e.g. Grubbs' method). You can find a survey of outlier detection methods in A Survey of Outlier Detection Methodologies by Hodge and Austin (2004).


Maximum flow in a graph, and conservation of flow

The definition given in the lectures you've seen is the usual, which can be seen as the conservation of flow through a node, as it follows that flow exiting the node is equal to the flow entering the node. The expression doesn't only consider outgoing flow, as the equation $f(u,v) = -f(v,u)$ means that incoming flow can be described as 'negative' outgoing flow.

Your expression currently just says 'the flow through $u$ is the flow through $u$', which doesn't restrict the flow at all.

A better version of the expression you try to pose is the following:

$\begin{equation}
\sum_{v\in V_{in}(u)} f(v,u) = \sum_{v\in V_{out}(u)} f(u,v),
\end{equation}$

where $V_{in}(u)$ is the set of nodes $v$ that such that $v\rightarrow u$ is an edge and $V_{out}(u)$ the set of nodes $v$ such that $u\rightarrow v$ is an edge.

It can be easily shown that this equation is equivalent to $\sum_{v\in V} f(u,v) = 0$ when $f(u,v)= -f(v,u)$ for all $u,v\in V$.


I think I see your confusion.  The TLB and the data cache are two separate mechanisms.  They are both caches of a sort, but they cache different things:

The TLB is a cache for the virtual address to physical address lookup.  The page tables provide a way to map virtualaddress $\mapsto$ physicaladdress, by looking up the virtual address in the page tables.  However, doing the lookup in the page tables is slow (it involves 2-3 memory loads).  If the processor had to do this lookup every time any instruction accessed memory, this would cause a substantial slowdown.

Therefore, the TLB acts as a dedicated cache for this lookup.  The TLB has a few TLB entries, where each TLB entry contains both a virtual address and its corresponding physical address.

The TLB lets the processor very quickly convert virtual addresses to physical addresses.  If an instruction asks the processor to do some memory operation on a (virtual) address, the processor first checks to see whether the TLB contains an entry for that virtual address.  If it does, then that's called a "cache hit" for the TLB lookup, and since the TLB entry also contains the translated physical address, the processor immediately knows what physical address to use.  If it doesn't, that's a cache miss for the TLB lookup, and the processor has to laboriously do the virtual-to-physical conversion by walking the page table.  (Once it finishes doing that conversion, it adds an entry to the TLB so that future conversions of that virtual address will happen much more quickly.)
The data cache is a cache for the contents of memory.  Main memory lets you specify a physical address and read the value at that physical address.  However, main memory is slow.  If we had to go to main memory every time we wanted to do any memory operation, our processor would be very slow.

Therefore, the data cache acts as a dedicated cache for memory reads.  The data cache has some cache entries, where each cache entry contains a physical address and the value of memory at that address.

The data cache lets the processor very quickly read from memory.  When the processor wants to read memory at some (physical) address, it first checks the data cache to see whether it contains a cache entry for that address.  If it does, this is known as a "cache hit" (in the data cache), and the processor can immediately use the data value stored in that cache entry, without needing to contact main memory.  If it doesn't, then this is a "cache miss" (for the data cache), and the processor needs to go to main memory.  (After the processor receives the value at that address from main memory, it adds a cache entry to the data cache so that attempts to read that same address will hit in the data cache.)

They are both caches, but they serve a different purpose.  The processor uses both for each memory operation: it first uses the TLB to convert from virtual address to physical address, then it checks the data cache to speed up the process of reading the value stored in memory at that address.

For more details, you can read the Wikipedia article on TLBs.  If you do a search, there is a lot of other information available on TLBs and data caches. I suggest searching for "TLB" and for "L1 cache" or "L2 cache" (the latter 2 are kinds of data caches).

(For future reference: we expect you to do some research on your question before asking here, and to check standard Internet sources.  If the answer can be found in Wikipedia, you haven't done enough research on your own.  You might have had better luck if you'd checked Internet sources for information on how
TLBs before asking here.  See also How much research effort is expected of Stack Overflow users?.  So, take the opportunity to use this as a lesson for how you can improve your own research skills -- something that will be valuable to you throughout your career.)


Can a simulation be conducted in which the inhabitants would observe infinite time divisibility?

Yes, you can compute over continuous quantities. Calculus is an example.

If it was actually impossible to compute how a continuous system would behave, then how did this physicist end up believing reality is continuous? How did they make predictions that were confirmed by experiment, scientifically justifying their belief, if they weren't able to calculate any predictions?


What does superscript + mean in relational algebra?

I got the answer.  $A^+$ represents the set of attributes that $A$ functionally determines.


Without primes in $P$ does integer factorization lie in $coNP$?

First of all, you're misstating integer factorization: your version is completely equivalent to primality.

Second, there were primality certificates which could stand for a polytime primality testing algorithm. These are polytime verifiable certificates of primality.


term vs clause in the context of normal forms

They're often called a "clause", "conjunctive clause", or sometimes a "conjunction" (if it is clear from context what that is referring to).

See, e.g., https://en.wikipedia.org/wiki/Disjunctive_normal_form.


Time series probability and mutual information

Entropy is, in your case

probs = [p_0 p_1 p_2];
logProb = log(probs);
entropy = -1 * dot(probs, logProb);

You'll have to let us know what two random variables you want to calculate the mutual information of, but with your library it looks like you just need to call mutualinfo(vec1,vec2).


Special term for a cycle containing a single vertex and edge

It is generally called a Self Loop.

It refers to an edge that connects a vertex to itself.


NP-completeness of triangle removal problem

Your current attempt (at the time of writing this answer at least) is on the right track, it just needs one more step.

To help understand one way of relating the problems to each other, consider the following alternative way of defining a vertex cover; a vertex cover is a set of vertices whose removal leaves a disconnected graph.

So Vertex Cover is the problem of selecting vertices to remove that gets rid of all edges, whereas your problem is selecting vertices to get rid of triangles.

Thus to convert Vertex Cover to Triangle Removal we need to turn edges in the original graph intro triangles in the new graph (or at least, one sensible way - there could be many reductions).

Hence your construction of adding a vertex for every edge in the graph and making a triangle is heading in the right direction, the only problem is that we could remove the new vertices, and that may mess up our answer (it certainly makes it harder to argue about what the vertex cover should be in the original graph). What we need is a way of preventing the added vertices being selected for removal. To do this, instead of adding a single new vertex, add $k+1$ new vertices!

More precisely (but not completely precisely), given $G$ we construct $G'$ as follows:

For every vertex $v \in V(G)$, there is a vertex $v' \in V(G')$
For every edge $uv \in E(G)$, there is an edge $u'v' \in E(G')$.
For every edge $uv \in E(G)$, there are $k+1$ vertices $\{w_{1},\ldots,w_{k+1}\} \subseteq V(G')$ with the edges $u'w_{i}$ and $v'w_{i}$ in $E(G')$ for all $i$.

I won't go through the full proof that this works, but the general gist is that if we want to get rid of all the triangles attached to $u'v'$, it doesn't really help to take any of the $w_{i}$ vertices as there are too many of them, we eventually have to take at least one of $u'$ or $v'$, but once we take one of those, it deals with all the triangles, so any answer that takes a $w_{i}$ vertex must also take $u'$ or $v'$ (or both) and can be replaced by a smaller solution that takes only $u'$ or $v'$ (or both), so we only have to consider solutions of that form, but then we're basically done - as each edge has triangles, one of the two "original" vertices must be in the triangle removing solution for each edge, and hence is also a vertex cover.

Really you can make the same argument with your construction, but the additional vertices force things and make the argument clearer (you don't have to deal with arguing for alternative solutions and vertex swapping etc. etc.)


In s-t directed graph, how to find many small cuts?

Are you familiar with the randomized contraction algorithm also known as Karger's algorithm? The algorithm basically works by selecting edges uniformly at random and contracting them with self-loops removed. The process halts when there are two nodes remaining, and the two nodes represent a cut. To increase the probability of success, the randomized algorithm is ran several times. While doing the runs, one keeps track of the smallest cut found so far.

What I suggest now is that you run the randomized contraction algorithm several times. Each time the algorithm outputs a cut, decide whether or not to keep it by checking if it is small enough. Naturally you can halt when you have produced enough of these small enough cuts. Depending on the size of your input, this might even work quite well in practice.


Intuitively, a kernelization algorithm is an algorithm which in polynomial time preprocesses a given instance and outputs an instance whose size is bounded in the parameter.  The goal of kernelization is (at least) two-fold.  We get provable performance guarantees, i.e., we can prove upper bounds on the output instance, which has applications both in the design of algorithms, and also as a complexity measure.

More formally a kernelization algorithm (often referred to as the kernel), is an algorithm for a problem which on an input $(G,k)$ outputs an equivalent
  instance $(G',k')$ with $\max\{|G'|,k'\} \leq f(k)$ for some function $f$.
Furthermore, the algorithm needs to run in polynomial time.

The following result shows that the power of kernels is, so to speak, equivalent to the power of fixed parameter tractability (PDF)

Theorem (Folklore).  A problem is fixed parameter tractable if and only if it admits a kernel and  is decidable.

Although the notion of kernel coincides with fixed parameter tractability, there is a stronger version of kernelization where we demand the function $f$ above to be a polynomial.

If you want to see the original definitions, I advice you to pick up Downey and Fellows' book on parameterized complexity, or start from Niedermeier's Habilitation thesis mentioned above.  There is also a Wikipedia article on Kernelization.


Clarifying the definition of reduction with regards to NP-complete problems

A problem $L$ is $\text{NP}$-complete if $L$ is in $\text{NP}$, and $L$ is $\text{NP}$-hard (that is, $A\leq_p L$ for all $A\in \text{NP}$ ). Consider the following claims.
Claim 1: if $L$ is $\text{NP}$-complete and $L\in \text{P}$, then $\text{NP} \subseteq \text{P}$ (that is, all problems in $\text{NP}$ can be solved in deterministic polynomial time).
Claim 2: If $ A \leq_p B$, then $B\in \text{P} \to A \in \text{P}$.
What you asked about is claim 1. To begin with, its correctness follows from claim 2. Indeed, if $L$ is $\text{NP}$-complete, then for every $A\in \text{NP}$, it holds that $A\leq_p L$. Thus, if we assume that $L\in \text{P}$, then we get by claim 2 that $A\in \text{P}$, and therefore $\text{NP} \subseteq \text{P}$. So what is missing for you is the proof of claim 2, and a sketch of its proof goes as follows. If $M_f$ is a TM that computes a polynomial time reduction $f$ from $A$ to $B$, and $M_B$ is a TM that decides $B$ in polynomial time, then a TM $M_A$ that decides $A$ in polynomial time operates as follows. On input $x$, $M_A$ computes $y = M_f(x)$, then $M_A$ runs $M_B$ on $y$, and answers the same. What is left to show is that $M_A$ decides $A$ in polynomial time, and I leave that to you (use the fact that |y| is polynomial, and the fact that a composition of polynomials is a polynomial).


Relative efficiency of n tasks in 1 loop vs. 1 task each in n loops?

Collecting the information in a single iteration would be way better, but you'll only notice the difference if your array contains a large number of numbers. On a small scale, it just won't make a difference.


Minimum cost of "signal" cover in a tree with DP

Let $T$ be your tree, and root it in an arbitrary vertex $r$.
Given a vertex $v$, let $T_v$ denote the subtree of $T$ rooted at $v$.
For simplicity, let $f(0, v) = 0$.
For $i \ge 0$, define $D[v,i]$ as the minimum cost needed to cover the subtree rooted at $v$ if all the nodes at distance smaller than $i$ from $v$ are always considered as covered.  Intuitively this means that the signal "coming into $T_v$" is strong enough to cover all vertices of $ T_v$ at distance at most $i-1$ from $v$.
For $i \ge 0$, define $U[v,i]$ as the minimum cost needed to cover the subtree $T_v$ rooted at $v$ with the constraint that the selected signal strengths should also be a feasible solution for the tree obtained by appending a path of $i$ vertices to $v$. Intuitively this means that the signal "outgoing from $T_v$" is strong enough to cover all vertices of $T \setminus T_v$ at distance at most $i$ from $v$.
Notice that, by definition, $D[v,i] = U[v,i]$.
If $v$ is a leaf of $T$, then
$$
D[v, i] =
\begin{cases}
f(v, 0) & \mbox{if } i=0 \\
0 & \mbox{if } i>0 \\
\end{cases},
$$
and
$$
U[v, i] = f(v, i).
$$
If $v$ is not a leaf of $T$, then let $C_v$ be the set of children of $v$.
For $i=0, \dots, n-1$:
$$
U[v, i] = \min
\begin{cases}
U[v, i+1] & \mbox{only if $i \neq n-1$}\\
f(v,i) +  \sum_{u \in C_v} D[u, i]    \\
\min_{z \in C_v} \left\{ U[z, i+1] +  \sum_{u \in C_v \setminus {z}} D[u, i] \right\}  & \mbox{only if $i \neq n-1$}
\end{cases},
$$
and, for $i=1,\dots,n$:
$$
D[v, i] =
\min
\begin{cases}
D[v, i-1] \\
\sum_{u \in C_v} D[u, i-1]
\end{cases}
$$
You can then compute all values $U[v, i]$ and $D[v,i]$ where $v$s are considered in postoder w.r.t. $T$ and the order of subproblems for a fixed vertex $v$ is $U[v,n-1], \dots, U[v,1], U[v,0] = D[v,0], D[v,1], \dots, D[v,n]$.
As far as the computational complexity is concerned notice that there are $O(n^2)$ subproblems.
The overall time needed to evaluate the second argument of the minimum of $U[v,i]$ and $D[v,i]$ is $O(n^2)$ since, for each value of $i$, computing $\sum_{u \in C_v} D[u, i]$ takes time proportional to $|C_v|$ and $\sum_v |C_v| = O(n)$.
Suppose then that all the values $\sum_{u \in C_v} D[u, i]$ are known for free (since the time needed to compute them has already been accounted for).
The overall time needed to evaluate the third argument of the minimum of $U[v,i]$ is again $O(n^2)$ since, for each value of $i$, $\sum_{u \in C_v \setminus {z}} D[u, i]$ can be found in time $O(1)$ by difference, and the inner minimum ranges over $|C_v|$ elements. Once again  $\sum_v |C_v| = O(n)$.


Showing an equivalent definition of $CO-RE$

Equivalently: $\overline{L_1}$ is RE iff there is some $\overline{L_2}$ that is $R$ so that $\overline{L_1}=\{u  | \exists v : <u,v>\in \overline{L_2}\}$ is RE.

$\Rightarrow$

Take $\overline{L_2}=\{<u,v> | v\text{ represents an execution accepting u in the MT accepting }\overline{L_1}\}$. It's R because you just simulate the MT following v and it'll either work or not. And it vefiries the property $\overline{L_1}=\{u  | \exists v : <u,v>\in \overline{L_2}\}$ because a word is accepted iff some execution accepts.

You could also take $\overline{L_2}=\{<u,n> | u\text{ is accepted by an execution of size} n\}$.

$\Leftarrow$

Enumerate all $v$, for each, test is $<u,v>\in\overline{L_2}$ and if it is, accept. If the word is in $\overline{L_1}$ then some $v$ will work so it'll be accepted. So $\overline{L_1}$ is indeed RE.

Your property says is that being RE is the same thing as being the projection of a R set.


Let $L$ be a language in $\mathrm{TIME}(2^{2^n})$ but not in $\mathrm{TIME}(o(2^{2^n}/2^n))$ (such a language exists by the time hierarchy theorem). Define $U = \{1^n : n \in L\}$. Using an algorithm for $L$, we get that $U \in \mathrm{TIME}(2^n + O(n^2))$. Running the same argument backwards, we see that $U \notin \mathrm{TIME}(o(2^n/n))$ (here we use that $O(4^n) \ll 2^{2^n}/2^n$).


The method itself is (or at least can be made), though the question is somewhat ill posed. What do you mean by deterministic?

The algorithm cannot be run on an NFA or DFA, so it's not deterministic/non-deterministic in that sense.

In most cases, the algorithm will run on a Turing Machine, or some similar model (RAM machine, programming language, lambda calculus, etc.).

It's known that any non-deterministic Turing Machine can be simulated by a deterministic one, using backtracking. So in this sense, the algorithm certainly can be made deterministic.

Is it possible to define the powerset construction in such as way that it's non-deterministic? Yes. There's some element of choice in which states you process first, which NFA states you choose to expand, whether you look breadth-first or depth-first, etc.

But it's trivial to remove these choices, either by resolving them arbitrarily, or by making the choice with some heuristic.


Let us consider the more general case in which you have $n$ vertices, and you connect $x,y$ if $x-y \equiv a \pmod{n}$ (in your case, $n = 7$ and $a = 3$).
Your graph is a union of disjoint cycles. When $n$ is prime (as in your case), it is a single cycle. Hence if you want to get from $x$ to $y$, either you keep adding $a$ (modulo $n$), of you keep subtracting $a$ (modulo $n$). If you add $m$ times the value $a$ (where $m$ is possibly negative) then $x+ma \equiv y \pmod{n}$, that is, $ma \equiv y-x \pmod{n}$. Let us now assume that $(a,n) = 1$ (for example, $n$ is prime and $1 \leq a \leq n-1$). Then $m \equiv a^{-1}(y-x) \pmod{n}$.
Solving the equation above (assuming $x \not\equiv y \pmod{n}$), there will be one solution $m_+$ in the range $1,\ldots,n-1$ and another $m_-$ in the range $-1,\ldots,-(n-1)$. The distance is $\min(m_+,-m_-)$.
In your case, $n = 7$ and $a = 3$. We can compute $a^{-1} = 5$. If $x = 0$ and $y = 1$ then $a^{-1}(y-x) = 5$, and so $m_+ = 5$ and $-m_- = 2$. So the shortest path goes backwards for two steps: $0 \to 4 \to 1$.


Convolutional Neural Network for Insects

The training set needs to have the same distribution of images as whatever you will be applying your classifier to.  So, if you'll be running the classifier on some images of houseflies and some images of other insects (not house-flies), your training set needs to contain both kinds of images.  If there are many other kinds of non-housefly images you'll be running the classifier on, the training set should contain images of those same kinds of insects, in a similar frequency to the frequency they'll occur when you use the classifier.

I encourage you to read about object classification vs object recognition vs object detection.  See, e.g., https://stackoverflow.com/q/31750076/781723.  The simplest kind of classifier takes an image of a single insect and outputs "housefly" or "not housefly".  That kind of classifier will be trained on images of single insects -- and should only be expected to work correctly if you apply it to images of a single insect.  However, you can also find techniques in the computer vision literature for recognizing the location of the insect in the image and dealing with multiple insects; read about object recognition and detection.

I'm not sure where you got the idea that the default is 2 convolutional layers followed by 2 fully connected layers, but there is no such default and no such rule.  I'm not saying that's an unreasonable starting point, but there are no hard-and-fast rules that tell you how many layers to pick.  Instead, you'll probably need to try several different possibilities and see how well they work.  If you can find papers in the research literature that solve a similar problem, you can sometimes use them as guidance for a good network architecture, but if you're not aware of anything like that, you'll just have to experiment on your own.


Complexity of K-Colorful Coloring Problem for a Hypergraph

A strong k-coloring of a hypergraph assigns distinct colors to every member of a hyperedge and uses $k$ colors. When the hypergraph is $k$-uniform, this problem is equivalent to the problem you describe. Further, this problem is NPC as shown by Colbourn, Jungnickel and Rosa [1].

You can also prove yourself that this problem is NPC by a straightforward reduction from chromatic number. Essentially, you can add enough vertices around every edge and make them into cliques and you can make the reduction work.

[1] Colbourn, Charles J., Dieter Jungnickel, and Alexander Rosa. "The strong chromatic number of partial triple systems." Discrete applied mathematics 20.1 (1988): 31-38.


Recusively Enumerable or Recursive dependent on whether P=NP

The language $L = \emptyset$  is indeed a recursive set.


Importance of recursion in computability theory

In the 1920's and 1930's people were trying to figure out what it means to "effectively compute a function" (remember, there were no general purpose computing machines around, and computing was something done by people).

Several definitions of "computable" were proposed, of which three are best known:

The $\lambda$-calculus
Recursive functions
Turing machines

These turned out to define the same class of number-theoretic functions. Because recursive functions are older than Turing machines, and the even older $\lambda$-calculus was not immediately accepted as an adequate notion of computability, the adjective "recursive" was used widely (recursive functions, recursive sets, recursively enumerable sets, etc.)

Later on, there was an effort, popularized by Robert Soare, to change "recursive" to "computable". Thus we nowadays speak of computable functions and computably enumerable sets. But many older textbooks, and many people, still prefer the "recursive" terminology.

So much for the history. We can also ask whether recursion is important for computation from a purely mathematical point of view. The answer is a very definite "yes!". Recursion lies at the basis of general-purpose programming languages (even while loops are just a form of recursion because while p do c is the same as if p then (c; while p do c)), and many fundamental data stuctures, such as lists and trees, are recursive. Recursion is simply unavoidable in computer science, and in computability theory specifically.


What is the definition of Computer Science, and what is the Science within Computer Science?

Computer science is a misnomer - there is actually no "science" in computer science, since computer science is not about observing nature. Rather, parts of computer science are engineering, and parts are mathematics.

The more theoretical parts of computer science are purely mathematical. For example, what is a good algorithm for sorting? How do we define the semantics of programming languages? How can we be sure that a cryptographic system is secure?

When computer science gets applied, it becomes more like engineering. For example, what is the best way to implement a matrix multiplication algorithm? How should we design a computer language to facilitate writing large programs? How can we design a cryptographic system to protect online banking?

In contrast, science is about laws of nature, and more generally about natural phenomena. The phenomena involved in computer science are man-made. Some aspects of computer science can be viewed as experimental in this sense, for example the empirical study of social networks, the empirical study of computer networks, the empirical study of viruses and their spread, and computer education (both teaching computer science and using computers to teach other subjects). Most of these examples are border-line computer science, and are more properly multidisciplinary. The closest one gets to the scientific method in computer science is perhaps the study of networks and other hardware devices, which is mainstream in the subarea known unofficially as "systems".

These examples notwithstanding, most of the core of computer science is not science at all. Computer science is just a name - it doesn't need to make sense.

As for the scope of computer science, the best definitions is perhaps: that which computer scientists do. Computer science, like every other academic discipline, is a wide area, and it is difficult to chart completely. If you want a sampling of what people consider computer science, you can look at the research areas of your faculty.


Your problem belongs to the family of problems known as fixed interval scheduling. For a recent survey, see Kovalyov et al. A classical paper of Arkin and Silverberg solves the problem when all sizes or capacities are the same, and shows that if you generalize the notion of size then the problem of deciding whether all jobs (i.e., items) can be scheduled (i.e., stored) is NP-complete, though it has an $O(n^{k+1})$ solution, where $n$ is the number of jobs and $k$ is the number of machines (i.e., containers).

Your problem is easier than the NP-complete variant considered by Arkin and Silverberg:

Your constraints on which jobs can be scheduled on which machines are not arbitrary – they depend on the notion of size.
Your timeframe is short.
You are guaranteed a solution. (Though this doesn't usually make the problem any easier.)

The literature on the problem is probably vast, so perhaps someone already considered your particular variant.


Lempel-Zilv-Welch Algorithm Decoding Question

Let us look at the very first line. There is a 104 at the end of the line. Where does that 104 come from? It is the first number of the number(s) that are represented by 104 in the next column. Since 104 is in the 0-255 range, 104 just represents itself.

The same procedure happens on the line at the end of which you see a 106. Where does that 106 come from? That 106 is the first number of the number(s) that are represented by 256 in the next column. How? Since 256 is outside of 0-255 range, we have to consult the dictionary we have built. As given by the last column of the first line, 256 represents for two numbers, 116 104, of which 106 is the first one.

I will let you figure out why the above procedure is correct, where 101 on the last line come from and why the numbers in the output column are correct.

By the way, it should be helpful if you can also take a look at the encoding procedure at the nearby lines when you try to understand the decoding procedure.


Let's say that a class $\cal C$ is closed under "reverse quadratic padding" if for any language $L$, if $Q(L) = \{\langle |x|, 0^{|x|^2} \rangle : x \in L \}$ belongs to $\cal C$ then $L$ also belongs to $\cal C$.

The class $\mathsf{NL}$ is closed under reverse quadratic padding: if $Q(L) \in \mathsf{NL}$, then we can decide $L$ itself in $\mathsf{NL}$ by simulating the decider for $Q(L)$. For that we use our ability to count up to $n^2$ (here $n$ is the input length), noticing that $O(\log(n^2)) = O(\log n)$.

In contrast, the class $\mathsf{DTIME}(n^2)$ isn't closed under reverse quadratic padding. Indeed, use the time hierarchy theorem to find a language $L \in \mathsf{DTIME}(n^3) \setminus \mathsf{DTIME}(n^2)$. Then $Q(L) \in \mathsf{DTIME}(n^2)$, whereas $L \notin \mathsf{DTIME}(n^2)$.


Karp hardness of a guarding set in digraph

It is NP-complete (it is obviously in NP) by reduction from the dominating set problem.

Given an instance $G=(V,E)$ of the dominating set problem, split each vertex $v$ into two vertices $v_{\mathrm{in}}$ and $v_{\mathrm{out}}$, and for each edge $(u,v)\in E$, construct two edges $(u_{\mathrm{out}},v_{\mathrm{in}})$ and $(v_{\mathrm{out}},u_{\mathrm{in}})$. We claim that $G$ has a dominating set of size $k$ iff the newly-constructed graph (say $G'$) has a guarding set of size $2k$.

If $G$ has a dominating set $S$ of size $k$, easy to see $\{v_{\mathrm{in}}\mid v\in S\}\cup\{v_{\mathrm{out}}\mid v\in S\}$ is a guarding set of $G'$, which has size $2k$.

On the other hand, suppose $G'$ has a guarding set $S'$ of size $2k$. Let $S'_{\mathrm{in}}=S'\cap\{v_{\mathrm{in}}| v\in V\}$ and $S'_{\mathrm{out}}=S'\cap\{v_{\mathrm{out}}\mid v\in V\}$, then either $S'_{\mathrm{in}}$ or $S'_{\mathrm{out}}$ must has size at most $k$. Without loss of generality, say $\left|S'_{\mathrm{in}}\right|\le k$, then $S=\left\{v\mid v_{\mathrm{in}}\in S_{\mathrm{in}}'\right\}$ is a dominating set of $G$. This means $G$ has a dominating set of size $k$.


Classifying infinite languages of encodings of halting Turing machines

There are certainly examples for all "levels":

It is easy to give an infinite set of encodings that is decidable.

   Consider all programs of the form f(x) = x + i -- definitely an infinite and decidable set.

Classic examples (think Halting problem) are semi-decidable but not decidable.

   $L = \{ \langle M \rangle \mid f_M(\langle M \rangle) = 1\}$

Other classic examples (think complement of Halting problem) are not semi-decidable.

    $L = \{ \langle M \rangle \mid f_M(\langle M \rangle)\uparrow \}$


Can the program determine the frequency of the CPU or is it impossible?

In these days of superscalar, multicore, virtualisation, power scaling, managed operating systems, and so on, what does "CPU frequency" even mean?

Note that it may be possible for Alice to convince Bob that she has compute power capable of performing X operations of a known type in a given time, as you find in a proof-of-work system. If it is a problem for which parallel algorithms are believed not to be feasible, he may be convinced that it happened on a single compute device, and not (say) a cloud or cluster.

But for all Bob knows, Alice may have an asynchronous device which doesn't even have a clock speed.


Can a context-senstive gramma contains production rule $cB\rightarrow Bc$?

Your confusion is not unexpected. That grammar is not a context-sensitive grammar in its usual strict sense.

However, that grammar can be considered as a context-sensitive grammar in some situations. The Wikipedia entry on context-sensitive grmmar reads the following.

  Some definitions of a context-sensitive grammar only require that for any production rule of the form $u \to v$, the length of $u$ shall be less than or equal to the length of $v$. This seemingly weaker requirement is in fact weakly equivalent, see Noncontracting grammar#Transforming into context-sensitive grammar.

You may want to double check the definition of CFG and exposition thereafter in the textbook you mentioned.


Does rice theorem applies to languages only or does it apply to machines as well?

The Rice's theorem can also be stated in terms of index sets of TMs.

Lets start with a basic definition of a property of a language. A property of a language is a set of languages. For example $$P_{reg} = \{L \mid L \text{ is regular } \}$$ and $$P_{fin} = \{L \mid L \text{ is finite } \}$$ are properties of languages.

We also define a language of indexes as
$$L_P = \{\langle M \rangle\ \mid L(M) \in P\}$$
In simple words, a set of TM indexes such that the language recognized by $M$ belongs to the property $P$. Now, the Rice's theorem states that if $P$ is nontrivial then the problem whether $n \in L_P$ is undecidable, i.e., $L_P$ is undecidable.

However, we cannot apply it to the following sets
$$L_1 = \{\langle M \rangle\ \mid M \text { has } 5 \text{ states} \}$$
and
$$L_2 = \{\langle M \rangle\ \mid M \text { never writes to the tape} \}$$
since they talk about properties of Turing machines and not languages (we cannot say a language $L$ has 5 states). They may be decidable or not which may be proved the other way (not using the Rice's theorem). For example, $L_1$ is decidable since you simply count the number of states of a TM.

So, the answer to your question

  does this theorem applies to machines

depends on what set of TMs you are talking about. If this is a set of TMs whose recognizing languages belong to some nontrivial property of a language then the answer is "yes", otherwise the answer is "no".


Proof of $\mathsf{NP}^\mathsf{BPP} \subseteq \mathsf{BPP}^\mathsf{NP}$

Suppose that $M$ is a machine in $\mathsf{NP}^\mathsf{BPP}$ accepting some language $L$. We can think of $M$ as accepting an input $x$ and a witness $y$. The machine $M$ runs a polytime algorithm, and has oracle access to $\mathsf{BPP}$. We can further assume that the witness contains, for each oracle call to $\mathsf{BPP}$, both the input and the output — the witness might be longer, but it still has polynomial length. Denoting the pairs by $z_i,w_i$ and the $\mathsf{BPP}$ languages by $L_i$, we thus deduce that there is a polytime machine $A$ such that
$$
x \in L \Leftrightarrow \exists y,\vec{z},\vec{w},\vec{L} \; A(x,y,\vec{z},\vec{w},\vec{L}) \land \bigwedge_i L_i(z_i) = w_i,
$$
where the quantification is over polynomial length strings. (We elide the issue of how $L_i$ is represented.)

Suppose furthermore that $L_i$ is computed by some $\mathsf{BPP}$ machine $A_i$ with small error probability. We can think of $A_i$ as accepting two inputs: the actual input $z_i$, and a randomness string $r_i$.

This suggests the following $\mathsf{BPP}^\mathsf{NP}$ machine for $L$. The machine gets input $x$ and randomness string $\vec{r}$. Using a single oracle call to $\mathsf{NP}$, it checks whether there exist $y,\vec{z},\vec{w},\vec{L}$ such that
$$
A(x,y,\vec{z},\vec{w},\vec{L}) \land \bigwedge_i A_i(z_i,r_i) = w_i.
$$

If $x \in L$, let $y,\vec{z},\vec{w},\vec{L}$ the $M$-witness for it. For the vast majority of randomness strings $\vec{r}$, we will have
$$
A(x,y,\vec{z},\vec{w},\vec{L}) \land \bigwedge_i A_i(z_i,r_i) = w_i,
$$
and so our machine will accept $x$.

The other direction is a bit more subtle, and I'll let you work it out carefully. It requires the $\mathsf{BPP}$ machines to have really small error, which can be achieved via repetition.


Train a neural network to play tic tac toe using a genetic algorithm

this is an unusual assignment or exercise for several reasons. tic tac toe is not a complicated game, there is not a large "state space" so an optimal algorithm is possible even by eg a "relatively small" finite state machine. so even a genetic algorithm or neural network alone would be sufficient (in fact, capable of playing a perfect game) and also, from a practitioner pov, overkill. it suffices as a "toy problem" but almost even too simple to fully demonstrate these techniques. breaking down the problem into a machine learning approach aka "decomposition" is part of the art/ science of the field. here are a few relatively basic/ straightforward possibilities.

genetic algorithm alone: let the candidate solutions aka chromosomes be represented as strings with alternating moves. the fitness function evaluates who wins and if the strings represent valid moves between the two players. it will not take long to find/ enumerate all possible game sequences.
neural network alone: input is (an encoding of) the opponents move, output is the computers move. a data generator must pick valid moves by the opponent.
combination (even bigger overkill): a common scenario in NN+GA technology is for the GA to be used to generate NN architectures. the GA string determines the NN architecture. eg size and possibly connectivity of the different layers. the fitness function is the results of training/ evaluating the NN on the particular GA architecture (ie chance of the computer winning).

and of course there are many other ways to combine NNs+GAs and other ways to decompose the problem into NNs or GAs alone.


A Question related to the method of find lower bound : Trivial lower bounds

The trivial bound assumes that the program has to read the entire input. This is usually, but not always, the case. Similarly, it assumes that the program has to write each output item separately. This is usually, but not always, the case.

Since the program has to read the entire input, it has to do some operation for each input item. Similarly, it has to so some operation for each output item. This gives you the trivial bound, in terms of the number of basic operations.

Since we are usually only interested in complexity up to constant factors (big O complexity), the actual time that a basic operation takes doesn't enter the picture at all.


Theorem Prover for complexity theoretic reductions

This is certainly possible, and the language of higher order functions makes this quite nice. If you're doing a Turing/Cook reduction, you can basically just write a function that takes an oracle as a parameter.

For example, to show that Graph Coloring is NP-hard, you could write something like this (pardon my terrible Coq-like pseudocode)

Theorem reduction:
  (forall (k:Nat) (g:Graph), Decidable (Coloring g))
  -> (forall (f:BoolFormula), Decidable (Model f))

What gets tricky is proving that your reductions are polynomial-time. There are ways to do this, such as with a time-tracking monad. This example verifies the time complexity of a sorting algorithm, and gives some hints as to how to model this. Basically, for whatever operation you're counting as $O(1)$, you require that it be performed in the monad, as well as calls to your oracle. Then you write a proof of some polynomial bound on the number of operations performed in the monad (which can keep track of them by encapsulating state).


Why are decision problems easier than the equivallent optimization problems?

If the objective function $f$ is easy to compute, you can use a solution to $OPT$ to solve $L_{OPT}$: find some $x$ which maximises the objective function; compute $f(x)$ and output "yes" if it meets or exceeds the threshold $u$ (output "no" otherwise).

That is, $L_{OPT}$ reduces to $OPT$ (for some suitable definition of the reduction type), and is in this sense easier.

If we let $OPTVAL$ be the function problem of computing the optimal value, but not the solution which has this value, $OPTVAL$ reduces to $L_{OPT}$ via binary search.  (Also $OPTVAL$ reduces to $OPT$: compute the optimal solution, then compute its value.)

Note that the reduction in one direction is a member of a smaller class of reductions than in the other: when solving $L_{OPT}$ via $OPT$ you have the reduction $r$ and some post-processing $p$ such that for every instance $i$, the answer to $L_{OPT}$ equals the output of $p(OPT(r(i))$.  That is, it's a one-call reduction (but not tail call, which it can't be due to a type mismatch).  The reduction from $L_{OPT}$ to $OPTVAL$ is a multi-call reduction (with binary search it will make a logarithmic number of queries).

It's not clear to me that you can reduce $OPT$ to $OPTVAL$, not even with multiple calls: given an oracle which tells you what the optimal value is, how to you compute a solution with that value, generically?

However, most "natural" problems will probably let you do this.  For instance, if we represent a graph $G$ as the number of vertices followed by an enumeration of the complement of the edge set and want to compute the chromatic number (smallest $k$ such that the graph is $k$-colourable), we can let $G'$ be $G$ with an edge added and ask our $OPTVAL$-oracle what the optimal value is.  Whenever such a change doesn't increase the number of colours required, we learn of an additional constraint we can impose.  Do so until it's no longer possible (at most polynomially often); now each vertex is adjacent to every vertex of any different colour, i.e. $u$ and $v$ have the same colour for every $(u, v) \in (V \times V) \setminus E$. Assign a colour to an uncoloured vertex, apply this rule and repeat until the graph is $k$-coloured.

One could generalise this: let solution-extractable optimisation problems be those such that with oracle access to the optimal value on smaller instances and the given instance, you can compute the optimal solution.  Then you can multi-call reduce $OPT$ to $OPTVAL$ on solution-extractable problems (by construction).  Of course, you can also compute optimal solutions to the smaller instances, since they are instances of a solution-extractable problem by assumption; maybe that helps to extract the optimal solution to the bigger instance.

It would be nice to have some generic constructions that enable this.  Here's one idea:

Given some optimisation problem $P$ with a bound $k$ on the solution length, let instances of $Q$ be triples $(x, 1^{2k-l}, p)$ where $x$ are $P$-instances and $p$ has length $l$ be the problem of finding optimal solutions to $P$ which have $p$ as a prefix. If you can solve $OPTVAL_Q$ then $P$ is solution-extractable: whenever $OPTVAL$ of $Q$ goes down both when you extend $p$ with a $0$ and when you extend it with a $1$, $p$ is a longest optimal solution; otherwise, extend $p$ with any value which doesn't decrease the objective function.  Note that padding the problem with a number of ones equal to two times the bound on the solution length, we make the self-reductions downward when extending $p$.

Probably bit-by-bit solution extraction can be extended to chunk-by-chunk extraction if chunks have length at most $O(\log n)$ (since there's only polynomially many values to try out).


I am not sure what you mean by "language-agnostic definition of this concept in CS"; such notions are rarely (if ever) rigorously defined. Someone uses them first, others pick them up and eventually they become standard vocabulary. That's ho we get conflicting notation all the time.

In this case, I don't see an either-or. Both makes sense, depending of how you look at it. The semantics of the language control the flow of execution, i.e. determine which statement is executed next. But as this control -- once it is implemented in a processor -- only looks at the current statement, it flows along, that is control flows.


When proving NP-completeness do I only need one instance of a problem or all of them?

When you reduce Hamiltonian-Path (HP) to Spanning-Tree-with-inner-degree-$k$ (ST), you show that if you could solve ST then you could solve HP, and moreover in a specific way. If the resulting tree is not completely general, say it is always a Hamiltonian path with attached leaves, then you are actually proving the stronger result that the corresponding promise problem is already NP-hard.

A promise problem is one in which it is guaranteed that the input is either a Yes instance or a No instance, and the task is to distinguish only those two cases. In your case, the promise version is defined in this way:

Yes instance: the graph contains a spanning tree formed by a Hamiltonian path backbone and $k-2$ leaves attached to all internal vertices;
No instance: the graph contains no spanning tree in which the degrees of all internal vertices are $k$.

If a graph falls into neither class, we don't care what the answer is. Your proof shows that it is NP-hard to distinguish the Yes instances from the No instances.

We usually don't formulate NP-hardness results this way since it is more cumbersome, but you're right that the proof shows something more. However, if you only cared about the NP-hardness of ST, then there is no need for the reduction to potentially produce all Yes instances of ST. This is because the proof that the reduction implies NP-hardness of ST doesn't require this feature. Here is the proof:

  Suppose $A$ is NP-hard, and $f$ is a polynomial time reduction from $A$ to $B$ such that $x \in A$ iff $f(x) \in B$. Since $A$ is NP-hard, for every $L$ in NP there exists a polynomial time reduction $g$ such that $x \in L$ iff $g(x) \in A$, and so $x \in L$ iff $f(g(x)) \in B$. Since $x \mapsto f(g(x))$ is also polynomial time, this shows that $B$ is NP-hard.

At no point of this proof do we use anything about the possible instances produced by $f$.

Another situation in which we can conclude an improved result is when the instance (rather than the solution) has a specific form. Suppose, for example, that we were able to reduce HP to ST, and the resulting graph never has triangles (I'm not claiming that this is possible; this is just for illustration). In this case, we could conclude also that ST-for-triangle-free-graphs is also NP-hard. It still remains true that ST itself is NP-hard; if a special case is NP-hard, then the general case is a fortiori NP-hard.


Halting problem vs. automated theorem proving?

The notion of automating mathematics is a vague one, and that's accounting for the discrepancy here.

One interpretation would be: to automate mathematics would be to produce a machine $M$ which could tell whether or not a given sentence is true (or, more weakly, provable from some agreed-upon set of axioms like $\mathsf{ZFC}$). Even the weaker version is ruled out by the incomputability of the halting problem.

Another interpretation is: to automate mathematics is to produce a machine $M$ which will find proofs of all provable (again, from that agreed-upon set of axioms) sentences. Note that $M$ is not required to determine whether a sentence is provable in the first place, merely to find a proof if such a proof exists at all. This is possible via brute force search.

Of course that second type of automation is highly infeasible - in general, it will take ridiculously long to find proofs of theorems. But that doesn't impact its in-principle-possibility. This is really the starting point of automated theorem proving: trivially brute-force-proof-search is possible, and trivially it's horrible in general - can we find clever proof search strategies in some cases of interest? (And this is where complexity theory enters the picture.)


Complexity analysis using big - O, Omega and Theta notation

When $d = \Theta(n^\alpha)$, we have $\log_d n = \Theta(1)$, and so there is no difference between $d^2\log_d^2 n$ and $d^2\log_d n$ (or rather, the two differ only by a constant factor).

When $d$ is polylogarithmic in $n$, $\log_d n = \log n / \log d = \Theta(\log n/\log \log n)$, and so $\log^2_d n = \Theta((\log n / \log\log n)^2)$ is asymptotically larger than $\log n$.

For what values of $d$ are $\log^2_d n$ and $\log n$ asymptotically the same? We need $\log^2n/\log^2d = \Theta(\log n)$, and so $\log d = \Theta(\sqrt{\log n})$, i.e., $d = 2^{\Theta(\sqrt{\log n})}$. This is more than polylogarithmic but less than polynomial in $n$.


How does the 3-opt algorithm for TSP work?

You missed the footnote — these ways are "not including the connections being identical to a single 2-opt move". Indeed, there are only two permutations in $S_3$ without fixed points (also known as derangements), namely $(123)$ and $(132)$. More generally, for a $k$-opt move it is enough to consider permutations without fixed points, since those with $t$ fixed points are $(k-t)$-moves.

The algorithm for $k$-opt local search is as follows. Start with some initial solution, say the one produced by Christofides's algorithm. Repeatedly try to improve it by performing a $k$-opt: choose $k$ edges and reconnect them in a different way (this time it's OK if the move is also an $\ell$-move for some $\ell < k$) that results in a shorter tour.

The way this is implemented is by going over all sets of $k$ edges and over all ways of reconnecting the edges, perhaps in some intelligent order, and computing the difference in length (there is no need to recompute the length of the entire tour, just the different of length; that takes $O(k)$ instead of $O(n)$); if an improvement is found, we make the switch and repeat from the beginning. We continue like that until we get stuck.

A different variant is to always try all possibilities, and use the one that results in the best improvement. There are also other variants which you can probably find in the literature.


What is the runtime of Mergesort if we switch to Insertion Sort at logarithmic depth?

You know that MergeSort has a complexity of $O(n\log n)$. Why? We can write a recurrence for the running time of MergeSort:
$$ T(n) = 2T(n/2) + Cn, \quad T(1) = D. $$
(Assume for simplicity that $n$ is a power of 2.) The solution is $T(n) = O(n\log n)$. Why? Since we can write
$$ T(n) = 2T(n/2) + Cn = 4T(n/4) + Cn + Cn = 8T(n/8) + Cn + Cn + Cn = \cdots = (\log n)Cn + Dn. $$
That is, at each internal level the total complexity is $Cn$, there are $\log n$ levels, and at the bottom the complexity is $Dn$. It is instructive to rewrite it in terms of $n = 2^k$:
$$ T(2^k) = 2^1T(2^{k-1}) + C2^k = 2^2T(2^{k-2}) + C2^k + C2^k = \cdots. $$
In your case, you want to stop the recursion at depth $k/2$, and instead of expanding $2^{k/2}T(2^{k/2})$ using the recursion, apply the $En^2$ insertion sort algorithm. What would you get? (that's a question for you)


Check whether an interval is contained in a union of intervals

The problem requires $\Omega(n)$ time. Consider the interval $[A,B] = [0,N]$ and an algorithm for the problem. Whenever the algorithm queries $[S_{i1},S_{i2}]$, it gets the answer $[i-1,i]$. If the algorithm queries all intervals, then it knows that they cover $[A,B]$. Otherwise, the algorithm cannot tell. Indeed, suppose that it doesn't query $[S_{i1},S_{i2}]$, and that all other intervals are of the indicated form. If $[S_{i1},S_{i2}] = [i-1,i]$ then they cover $[A,B]$, but if $[S_{i1},S_{i2}] = [i-1/3,i-2/3]$ then they don't. Note that both inputs are legal (satisfy the constraint $S_{11} \leq S_{21} \leq \cdots \leq S_{n1}$).


As it is stated in "Computers and Intractability: a Guide to the Theory of NP-Completeness" A pseudo-polynomial-time algorithm will display 'exponential behavior' only when confronted with instances containing 'exponentially large' numbers, which might be rare for the applications we are interested in. If so, this type of algorithm might serve our purposes almost as well as a polynomial time algorithm.”

You can consider knapsack as a good example of weakly-Np Complete problem. In this case the complexity of the dynamic programming solution is $O(nW)$ which is well in most practical cases.

It is known that there is no pseudo-polynomial time algorithm for Strong NP-Complete problems (like Steiner Tree) unless P=NP.


Dominating set in bounded degeneracy and bounded degree graphs

No it does not. The problem DOM considered by the paper seems to be the enumeration of minimal, not minimum dominating sets. Usually minimal means a solution $X$ such that there is no other solution $X'$ with $X' \subsetneq X$. The solution $X$ is not necessarily the minimum size. While minimal dominating sets can be enumerated with polynomial delay in bounded degeneracy graphs, there seems to be no guarantees that this enumeration finds the minimum dominating set before enumerating an exponential number of dominating sets that are minimal, but not minimum.


Let me start with your third question. It seems that you don't quite understand the definitions of $\mathsf{UP}$ and $\mathsf{US}$, so let me repeat them here.

Definition of $\mathsf{UP}$. Property U. A non-deterministic Turing machine has property U if every input has at most one accepting path. The language accepted by such a machine consists of all inputs which do have an accepting path.
The class $\mathsf{UP}$ consists of all languages accepted by non-deterministic Turing machines having property U and running in polynomial time.
Definition of $\mathsf{US}$. U-acceptance. The language accepted by a non-deterministic Turing machine consists of all inputs which have an accepting path. In contrast, the language U-accepted by a non-deterministic Turing machine consists of all inputs having exactly one accepting path. Any input having either no accepting path or at least two accepting path does not belong to the language U-accepted by the machine.
The class $\mathsf{US}$ consists of all languages U-accepted by non-deterministic Turing machines running in polynomial time.

As for your second question, to show that $\mathsf{coNP} \subseteq \mathsf{US}$ it suffices to reduces $\mathsf{coSAT}$ to $\mathsf{US}$. Given a SAT instance $\phi = C_1 \land \cdots \land C_m$, let
$$\psi = (v \lor C_1) \land \cdots \land (v \lor C_m) \land (\lnot v \lor x_1) \land \cdots \land (\lnot v \lor x_n),$$ where $v$ is a new variable and $x_1,\ldots,x_n$ are the original variables. Then $\psi$ has a unique satisfying assignment (in which all variables are true) iff $\phi$ is unsatisfiable.
As for your first question, if $\mathsf{P} = \mathsf{NP}$ then $\mathsf{P} = \mathsf{UP} = \mathsf{US}$, so no unconditional separation is currently known. If you're interested in conditional separations, I suggest asking a new question focused just on that issue.


Term of System F whose type-erasure is $2(2)$

Consider the System F version of two:

$$ T = \Lambda \alpha.\lambda f:\alpha\to\alpha. \lambda x:\alpha. f(f(x))$$

We can then search for a term $M$ of the form

$$ M = \Lambda \alpha. T \tau_1 (T \tau_2) $$

and try to find types $\tau_1,\tau_2$, possibly depending on $\alpha$, such that $M : \forall \alpha. (\alpha\to\alpha)\to(\alpha\to\alpha)$. Surely $M$ becomes $2(2)$ after type erasure.

I'll leave finding $\tau_1,\tau_2$ as an exercise. Think about what is the type of $M$, and require it to be the wanted one: this provides $\tau_1$. After that, choose $\tau_2$ so that $M$ is well-typed.


Contraint with three variables into three binary constraints

Good question.  Your instinctive reaction is quite valid: if you stick with the variables $A,B,C$, there is no way to introduce some set of binary constraints that will be equivalent to $A+B=C$ (where each constraint is only allowed to mention two of $A,B,C$).

The trick is to introduce new variables, or change the set of variables.  If you do that, it can be done.  For instance, see the reference that hengxin suggests: http://ktiml.mff.cuni.cz/~bartak/constraints/binary.html.  However, it would be understandable if you feel that this is in some sense "cheating"... which might be why you didn't think of this approach.


Shortcut for "in the worst-case, with high probability"?

Your second example looks fine to me. "In the worst case, phase A takes time/space X whp" is even shorter.


That's probably a typo or poor wording -- in the quote, "has" should be "is".


Is it possible to tell if two sequences of assembly instructions are semantically equivalent?

If you restrict to programs of some fixed, finite length then yes, this is decidable. There are only a finite number of possible programs so there is a finite list of which ones are equivalent to one another. A program that is hard-coded with that list can answer the question just by looking up the two programs.

However, if you don't restrict the length of the programs, the problem becomes undecidable: if it were decidable, you could solve the halting problem ("Does program $P$ halt with input $I$?") by rephrasing it as "Is the program that simulates $P$ running on input $I$ equivalent to this trivial program that always halts?"

As an aside, why do you feel that a compiler would need to do this? Compilers just take a program represented in one form (source code) and translate it into another form (the executable image). The translation process guarantees that the two are semantically equivalent, so there's no need to check.


I don't have time for an elaborate answer right now, so here is just a quick braindump: Program logic does not restrict to concrete programs. Given e.g. a pair $(A, B)$ of pre/post-conditions, you can think of this pair as defining a set of programs

$$
\{ P \ |\ P\ \text{is a programs such that}\ \models A[P]B \}
$$

Here are a couple other references that might be useful.

J. Von Neumann, Theory of Self-Reproducing Automata.
F. Cohen, Computer Viruses - Theory and Experiments.
S. Kramer, J. C. Bradfield, A general definition of malware.
G. A. Kavvos, Theories of Computer Viruses: 30 Years Later.
L. M. Adleman, An abstract theory of computer viruses.
G. Jacob, E. Filiol, H. Debar, Formalization of viruses and malware through process algebras.
J. L. England, Statistical physics of self-replication.

As the kind of program you envision is a form of meta-programming, I suggest also to look at this field (which is primarily implementation-driven and lacks substantial theory as of 2017). Here are some references, none of which is likely to be directly relevant, but will eventually lead to research that should be:

M. Berger, L. Tratt, Program Logics for Homogeneous Meta-Programming
S. N. Artemov, L. D. Beklemishev, Provability Logic.
G. Japaridze, D. de Jongh, The logic of provability.
S. Artemov, Explicit Provability And Constructive Semantics.
J. Alt, S. Artemov, Reflective λ-Calculus.


Designing less than and less than or equal operators for Map with value being a Set

I think that actual code is off-topic here.
In general you can define a strict total order relation on (sub)sets of a known universe $U$: pick an arbitrary order for the elements of $U$ then, given two distinct subsets $X,Y$ of $U$, you can compare $X$ and $Y$ by first sorting the elements of $X$ (resp. $Y$) and then comparison the sorted version of $X$ with the sorted version of $Y$ lexicographically.
In your particular example the sets seem to contain integers, so you can just sort the set using the standard "less than" relation between integers.
To extend this total order to a map you can notice that a map is essentially a container of pairs of the form (key, value). We just defined a linear order over the values (sets), and you probably already have a natural order over the keys. Then two (key, value) pairs can be again compared lexicographically.


k-polynomial time approximation algorithm for set cover (k = max size of subsets)

Let $A = \{ i : x_i \geq 1/k \}$. By construction, $|A| \leq k \sum_i x_i \leq k \mathrm{OPT}$. The set $A$ is a set cover, since if $S_j = \{i_1,\ldots,i_\ell\}$ (where $\ell \leq k$) then $x_{i_1} + \cdots + x_{i_\ell} \geq 1$, and so $\max(x_{i_1},\ldots,x_{i_\ell}) \geq 1/\ell \geq 1/k$.


Normal assembly for if/then/else looks like:

JMP_FALSE <condexpr> elselabel
<thenstmt>
JMP endlabel
elselabel:
<elsestmt>
endlabel:

(You can substitute mnemonics as appropriate for your instruction set.)

This "backpatch" term is probably something specific to some specific code that your professor wrote, or the author of the textbook that you're using. In either case, it's not a promising term.

The "truelist" and "falselist" likely refer to definite assignment (and definite unassignment) tracking; most modern languages keep track of what variables (aka registers) have been definitely assigned (for at-least-once purposes) and some, like Java, keep track of what variables are definitely unassigned (for at-most-once purposes, like Java "final"). Having implemented this a few times, I've used both a non-sparse (custom bit array/set) and a sparse data structure for tracking assignment impact within a scope; in Java, the language is simple enough that register assignment can occur before definite assignment analysis, so the bit array works beautifully (since you can know the zero-based register numbers and use them as the bit indexes).

The "N" probably refers to the unconditional jump to end of if/then/else statement. Again, it's not a promising term, since it implies a number, and IR/assembly should never be dealing with a number when a label will do.

The "quad" term is another made-up term specific to whomever wrote the material that you are working from.

Also: s/them/then


Dealing with intractability: NP-complete problems

There are a number of well-studied strategies; which is best in your application depends on circumstance.

Improve worst case runtime
Using problem-specific insight, you can often improve the naive algorithm. For instance, there are $O(c^n)$ algorithms for Vertex Cover with $c < 1.3$ [1]; this is a huge improvement over the naive $\Omega(2^n)$ and might make instance sizes relevant for you tractable.
Improve expected runtime
Using heuristics, you can often devise algorithms that are fast on many instances. If those include most that you meet in practice, you are golden. Examples are SAT for which quite involved solvers exist, and the Simplex algorithm (which solves a polynomial problem, but still). One basic technique that is often helpful is branch and bound.
Restrict the problem
If you can make more assumptions on your inputs, the problem may become easy.

Structural properties
Your inputs may have properties that simplify solving the problem, e.g. planarity, bipartiteness or missing a minor for graphs. See here for some examples of graph classes for which CLIQUE is easy.
Bounding functions of the input
Another thing to look at is parameterised complexity; some problems are solvable in time $O(2^kn^m)$ for $k$ some instance parameter (maximum node degree, maximum edge weight, ...) and $m$ constant. If you can bound $k$ by a polylogarithmic function in $n$ in your setting, you get polynomial algorithms. Saeed Amiri gives details in his answer.
Bounding input quantities
Furthermore, some problems admit algorithms that run in pseudo-polynomial time, that is their runtime is bounded by a polynomial function in a number that is part of the input; the naive primality check is an example. This means that if the quantities encoded in your instances have reasonable size, you might have simple algorithms that behave well for you.

Weaken the result
This means that you tolerate errorneous or incomplete results. There are two main flavors:

Probabilistic algorithms
You only get the correct result with some probability. There are some variants, most notable Monte-Carlo and Las-Vegas algorithms. A famous example is the Miller-Rabin primality test.
Approximation algorithms
You no longer look for optimal solutions but almost optimal ones. Some algorithms admit relative ("no worse than double the optimum"), others absolute ("no worse than $5$ plus the optimum") bounds on the error. For many problems it is open how well they can be approximated. There are some that can be approximated arbitrarily well in polynomial time, while others are known to not allow that; check the theory of polynomial-time approximation schemes.

Refer to Algorithmics for Hard Problems by Hromkovič for a thorough treatment.

Simplicity is beauty: Improved upper bounds for vertex cover by Chen Jianer, Iyad A. Kanj, Ge Xia (2005)


Searching in sorted array with $O(\log n)$

You can answer the first question with binary search. Lets consider you're now discussing the interval $[l, r]$, and $m = \frac{(l + r)}{2}$. If $A[m] = m$, you have found an answer and you shall stop the search. If $A[m] < m$, then the answer must be in the interval $[m + 1, r]$, because if $i \le m$, then $A[i] \le A[m] - (m - i) < m - (m - i) = i$ (since the array is sorted in strictly ascending order and the elements are integers), thus no $i \in [l, m]$ can be the answer. Otherwise, if $A[m] > m$, then the answer must be in the interval $[l, m - 1]$, because if $i \ge m$, then $A[i] \ge A[m] + (i - m) > m + (i - m) = i$.
And I don't think you can solve the other tasks in $O(lg(n))$ using binary search. Consider these two examples :
$A = [5, 6, 12, 14, 15]$
$B = [4, 9, 12, 14, 17]$
As we know, binary search initially examines the middle element, in these cases, $12$. $12 \ne 3 \times 3 + 2$, thus the search has to continue. In both cases, decision must be the same, since the middle element is the same, therefore, if the algorithm decides to check the interval $[4, 5]$, the algorithm will respond NO to the array $A$, although $5 = 3 \times 1 + 2$, and if the algorithm decides to search the interval $[1, 2]$, it yields NO to the array $B$, while $17 = 3 \times 5 + 2$.
It is also true about the third task, with examples :
$A = [13, 49, 51, 52, 180]$
$B = [12, 48, 51, 52, 193]$
I hope my answer was helpful.


Complexity of algorithm to find number of elements > element index i in an array

Your problem is very related to that of computing the number of inversions in a permutation, or (equivalently) the Kendall tau distance between two permutations; this is the sum of your vector. In fact, your vector (with a very superficial change in the definition) is known as the inversion vector.

There is a classical data structure of Dietz that can be used to compute the inversion vector in time $O(n\log n/\log\log n)$; the $O(n\log n)$ solution you mention is the baseline here. Fredman and Saks proved a matching lower bound showing that the time complexity of Dietz's data structure is optimal. Computing the insertion vector can however be done faster: Chan and Pătraşcu give an $O(n\sqrt{\log n})$ algorithm (see under "Offline dynamic ranking and selection").


Distinguishing between uppercase and lowercase letters in the "move-to-front" method

Though for us, human beings, m and M are the same, for a computer these are two distinct symbols that have no relation whatsoever.

The answer actually depends on the application:

If your application is not case-sensitive, this separation does not matter, and the encoding is correct.
If the application is case-sensitive there must be a distinction between lower case and upper case.

It seems to me that the encoding is more efficient as the number of symbols is smaller, thus maybe it is better to encode upper and lower case as an additional bit rather than having the list to contain 26x2 symbols, but this depends on the distribution of the text you are encoding.


Why does Banded Needleman-Wunsch give alignments with no more than d base pairs of indels?

You are correct, the number of insertions/deletions $d$ is not constrained (only) by the bandwidth.

However, the algorithm only uses the fact that if we know $d$, then the path must stay within the $2d+1$ band. This band does not have to be tight: a zigzag path would indeed fit within a much narrower band.

You may wonder why the smallest bandwidth (which is indeed equal to the maximum sum over prefixes of your list $L$) isn't used as a parameter instead of $d$. Since $d$ is related to the similarity of the strings, it isn't unreasonable that an upper bound of $d$ is known in some applications. The smallest bandwidth doesn't seem to correspond to a 'natural' parameter in the context of similarity as $d$ does, so it doesn't seem reasonable that it is known and can be used in the algorithm.


Prove that different definitions of big-Oh with n>=1 or n>N are equivalent

Assume definition $1$ holds. Then we have identified a $c$ that works for all but finitely many $n$. For each of the remaining finitely many $n$, we can check if $f(n)< cg(n)$ holds. If it does, then continue on. If it doesn’t, we can always find a $c’$ such that $f(n)<c’g(n)$ holds for that particular $n$. $c’>c$, so this will also hold for all the previously examined $n$. Iterate this through all the finite many $n$ and take the largest value of $c’$. Then definition $2$ holds.

The other direction is really easy. Try to think about it a bit more, because if you think about it in the right way it’ll be obvious.


Number of ways an integer $n$ can be split into a product of $k$ distinct integers given a prime factorization

I'll show how to solve the case $k=2$ and without the constraint that all factors have to be distinct, and let you generalize and take care of the constraint. Each decomposition corresponds to a choice of non-negative integers $b_1,c_1,b_2,c_2,\ldots,b_i,c_i$ such that $a_j = b_j + c_j$. The number of such decompositions is thus $(a_1+1)\cdots(a_i+1)$.

There might be a slight problem with that, depending on what you mean by decomposition. Consider for example $n=2$. According to the count above, we get the two decompositions $1 \cdot 2$ and $2 \cdot 1$. Perhaps we want to count them as the same decomposition. In this case, we need to roughly divide the count above by 2. Why only roughly? Since if $n = m^2$, then the decomposition $n = m \cdot m$ only appears once. So if $n$ is a square, we need to divide the count above by 2, and add 1/2 (why?).

If we want to count the number of decompositions in which both factors are distinct, we need to check whether $n$ is a square, and then adjust our counts accordingly. Details left to the reader.

For general $k$, if you are OK with ordered decompositions (and ignoring the constraint that all factors be distinct), then all you need do is figure out how many non-negative integer solutions exist for the equation $a = b_1 + \cdots + b_k$. If you care about unordered decompositions (so $1\cdot 2$ and $2\cdot 1$ are considered the same) or require all factors to be distinct, you have more work to do. Inclusion-exclusion type formulas could be helpful.


Is the 0-1 Knapsack problem where value equals weight NP-complete?

Yes, this is called the subset-sum problem and is NP-Hard.


For counting many types of combinatorial objects, like trees in this case, there are powerful mathematical tools (the symbolic method) that allow you to mechnically derive such counts from a description how the combinatorial objects are constructed. This involves generating functions.

An excellent reference is Analytic Combinatorics by the late Philipe Flajolet and Robert Sedgewick. It is available from the link above.

The late Herbert Wilf’s book generatingfunctionology is another free source.

And of course Concrete Mathematics by GKP is a treasure trove.

For binary trees it goes like this: First you need a clear definition of the tree.

A binary tree is a rooted tree in which every non-leaf node has degree 2 exactly.

Next we have to agree what we want to call the size of a tree.

On the left all nodes are equal. In the middle we distinguish the leaves and non-leaves. On the right we have a pruned binary tree where the leaves have been removed. Notice that it has unary branches of two types (left and right)!

Now we have to derive a description of how these combinatorial objects are built. In the case of binary trees a recursive decomposition is possible.

Let $\mathcal{A}$ be the set of all binary trees of the first type then symbolically we have:

It reads as: “An object of the class of binary trees is either a node or a node followed by two binary trees.” This can be written as equation of sets:

$$\mathcal{A}=\{\bullet\}\cup\bigl(\{\bullet\}\times\mathcal{A}\times\mathcal{A}\bigr)$$

By introducing the generating function $A(z)$ that enumerates this class of combinatorial objects we can translate the set equation into an equation involving the generating function.

$$A(z)=z+zA^2(z)$$

Our choice of treating all nodes equally and taking the number of nodes in the tree as notion of its size is expressed by “marking” the nodes with the variable $z$.

We can now solve the quadratic equation $zA^2(z)-A(z)+z=0$ for $A(z)$ and get, as usual, two solutions, the explicit closed form of the generating function:

$$A(z)=\frac{1\pm\sqrt{1-4z^2}}{2z}$$

Now we simply need Newton’s (generalized) Binomial Theorem:

$$(1+x)^a=\sum_{k=0}^\infty\binom{a}{k}x^k$$

with $a=1/2$ and $x=-4z^2$ to expand the closed form of the generating function back into a power series. We do this because, the coefficient at $z^n$ is just the number of combinatorial objects of size $n$, typically written as $[z^n]A(z)$. But here our notion of “the size” of the tree forces us to look for the coefficient at $z^{2n+1}$. After a little bit of juggling with binomials and factorials we get:

$$[z^{2n+1}]A(z)=\frac{1}{n+1}\binom{2n}{n}.$$

If we start with the second notion of the size the recursive decomposition is:

We get a different class of combinatorial objects $\mathcal{B}$. It reads: “An object of the class of binary trees is either a leaf or a interal node followed by two binary trees.”

We can use the same approach and turn $\mathcal{B}=\{\square\}\cup\bigl(\{\bullet\}\times\mathcal{B}\times\mathcal{B}\bigr)$ into $\mathcal{B}=1+zB^2(z)$. Only this time the variable $z$ only marks the internal nodes, not the leaves, because the definition “the size“ is different here. We get a different generating function as well:

$$B(z)=\frac{1-\sqrt{1-4z}}{2z}$$

Extracting the coefficient yields

$$[z^n]B(z)=\frac{1}{n+1}\binom{2n}{n}.$$

Class $\mathcal{A}$ and $\mathcal{B}$ agree on the counts, because a binary tree with $n$ internal nodes has $n+1$ leaves, thus $2n+1$ nodes in total.

In the last case we have to work a little harder:

which is a description of non-empty pruned binary tries. We extend this to
$$\begin{align}\mathcal{C}&=\{\bullet\}\cup\bigl(\{\bullet\}\times\mathcal{C}\bigr)\cup\bigl(\{\bullet\}\times\mathcal{C}\bigr)\cup\bigl(\{\bullet\}\times\mathcal{C}\times\mathcal{C}\bigr)\\\mathcal{D}&=\{\epsilon\}\cup\bigl(\{\bullet\}\times\mathcal{C}\times\mathcal{C}\bigr)\end{align}$$

and rewrite it with generating functions

$$\begin{align}C(z)&=z+2zC(z)+zC^2(z)\\D(z)&=1+zC^2(z)\end{align}$$

solve the quadratic equations

$$\begin{align}C(z)&=\frac{1-2z-\sqrt{1-4z}}{2z}\\D(z)&=\frac{1-\sqrt{1-4z}}{2z}\end{align}$$

and get yet again

$$[z^n]C(z)=\frac{1}{n+1}\binom{2n}{n}\quad n\ge1 \qquad [z^n]D(z)=\frac{1}{n+1}\binom{2n}{n} \quad n\ge0$$

Note that the Catalan generating function is

$$E(z)=\frac{1-\sqrt{1-4z}}{2}$$

it enumerates the class of general trees. That is the trees with no restriction on the node degree.

$$\mathcal{E}=\{\bullet\}\times\mathrm{SEQ}(\mathcal{E})$$

It reads as: “An object of the class of general trees is a node followed by a possible empty sequence of general trees.”

$$E(z)=\frac{z}{1-E(z)}$$

With the Lagrange-Bürmann Inversion Formula we get

$$[z^n]E(z)=\frac{1}{n+1}\binom{2n}{n}$$

So we proved that there are as many general trees as there are binary trees. No wonder there is a bijection between the general and binary trees. The bijection is known as the rotation correspondence (explained at the end of the linked article), that allows us two store every general tree as a binary tree.

Note that if we do not distinguish the left and right sibling in class $\mathcal{C}$ we get yet another class of trees $\mathcal{T}$:

the unary binary trees.
$$\mathcal{T}=\{\bullet\}\times\mathrm{SEQ}_{\le2}(\mathcal{T})$$
They have a generating function too
$$T(z)=\frac{1-z-\sqrt{1-2z-3z^2}}{2z}$$
however their coefficient is different. You get the Motzkin numbers
$$[z^n]T(z)=\frac{1}{n}\sum_k\binom{n}{k}\binom{n-k}{k-1}.$$

Oh and if you don’t like generating functions there are plenty of other proofs too. See here, there is one where you could use the encoding of binary trees as Dyck words and and derive a recurrence from their recursive definition. Then solving that recurrence gives the answer too. However the symbolic method saves you from coming up with the recurrence in the first place, as it works directly with the blueprints of the combinatorial objects.


Describe construction of finite automata that accepts the language Double-Letter(L)

The idea is to start with an automaton for $L$, and replace each transition labeled $\sigma$ by a path of length 2 both of whose edges are labeled $\sigma$. In order to make it a DFA, we also add a sink state. (This might be unnecessary in your definition of DFA.)

In more detail, suppose we start with a DFA $(Q,q_0,\delta,F)$ for $L$ (here $Q$ is the set of states, $q_0$ is the initial state, $\delta$ is the transition function, and $F$ is the accepting states). We construct a DFA whose set of states is $Q \cup Q \times \Sigma \cup \{q_{\mathit{sink}}\}$, where $\Sigma$ is the alphabet. The initial state is still $q_0$, and the accepting states are still $F$. The transition function $\delta'$ is defined as follows:

$\delta'(q,\sigma) = (q,\sigma)$ (this is a member of $Q \times \Sigma$).
$\delta'((q,\sigma),\sigma) = \delta(q,\sigma)$.
$\delta'((q,\sigma),\tau) = q_{\mathit{sink}}$ if $\tau \neq \sigma$.
$\delta'(q_{\mathit{sink}},\sigma) = q_{\mathit{sink}}$ for all $\sigma \in \Sigma$.

A simpler way of proving that the regular languages are closed under Double-Letter is using regular expressions: given a regular expression for $L$, simply double each letter. This is a special case of closure under homomorphism and regular substitution.


Maximum bipartite matching when some nodes must be matched

Assume the maximum matching problem is $U-V$ matching, and $S\subset U$.

Find maximum $S-V$ matching. If the result equals $|S|$, then it is a feasible matching in original $U-V$ matching problem. Othewise, no matching meets the requirement.
Using the feasible matching got in previous step as basis, improve it by augmentation, thus computing maximum $U-V$ matching.

Since an augmenting path never turns a matched vertex into unmatched vertex, the maximum matching found by above algorithm meets the requirement.

Using Hopcroft Karp algorithm, the complexity is $O(m\sqrt{n})$.

I don't know if the $O(n^{\omega})$ or $\tilde{O}(m^{10/7})$ algorithm works. But basically any maximum matching algorithm that based on augmentation works. And for those unit capacity network flow algorithms, it also works as long as it accepts an initial feasible flow and arguments along it, taking the lower capacity bound into account. (ie. never augment back through edges $s \to x (x\in S)$)


Difference between *device descriptor* and *device handler*

Where did you find that terminology? Check how it is defined there.

If it was up to me, a "device descriptor" would be a way to describe a device, perhaps a data structure giving details on it (or some sort of reference to it, like a pointer or an index into an array of the above).

As you state, in my book a "device handler" would be some sort of routine (or a set of routines) to manage it, a driver.


What is the decidable language in $P/poly$ but not in $P$?

Take a language $L$ which is not in $\mathsf{E} = \bigcup_{c=1}^\infty \mathsf{TIME}(2^{cn})$. Now consider the language
$L' = \{1^m : m \in L\}$.
Then $L'$ is clearly in $\mathsf{P/poly}$, but it's not in $\mathsf{P}$: if it were decidable in time $O(m^k)$, then we could decide $L$ in time $O((2^n)^k)$, and so $L$ would be in $\mathsf{E}$. Our decision procedure works as follows: on input $m$ of length $n = \log m$, we run the algorithm for $L'$ on the input $1^m$. This runs in time $O(m^k) = O((2^n)^k)$.

It remains to ensure that $L'$ is decidable. To that end, all we need to do is to choose some $L \notin \mathsf{E}$ which is decidable, for that makes $L'$ trivially decidable: given an input, if it's not of the form $1^m$, reject; otherwise, answer according to whether $m \in L$.

The existence of a decidable language $L \notin \mathsf{E}$ is guaranteed by the time hierarchy theorem.


Closure of context-free languages under regular quotient

Let me prove the following more general statement:

  Every full trio is closed under right quotient by a regular language.

Let $\mathcal{L}$ be the full trio, let $L \in \mathcal{L}$ be a language over $\Sigma$, and let $R$ be a regular language over $\Sigma$. Let $\Sigma' = \{ \sigma' : \sigma \in \Sigma \}$. Define the homomorphism $h\colon \Sigma \cup \Sigma' \to \Sigma$ by $h(\sigma) = h(\sigma') = \sigma$, and define the homomorphism $k\colon \Sigma \cup \Sigma' \to \Sigma$ by $k(\sigma') = \sigma$, $k(\sigma) = \epsilon$. Then
$$
L/R = k(h^{-1}(L) \cap \Sigma^{\prime *} R).
$$


Why is binary search using this weird thing to calculate middle?

Because left + right may overflow. Which then means you get a result that is less than left. Or far into the negative if you are using signed integers.

So instead they take the distance between left and right and add half of that to left. This is only a single extra operation to make the algorithm more robust.


If you don't know any bounds on the coefficients beforehand, then you cannot give them any bound without $d$ queries. Suppose you have made queries of $f(x)$ on $x=x_1,\ldots,x_{d-1}$, and claim that the coefficients of $f(x)$ are all at least $-b$. However, a different monic polynomial $f(x)-N(x-x_1)\cdots(x-x_{d-1})$ has the same evaluation on all the $d-1$ queries, and when $N$ is large enough the coefficient of $x^{d-1}$ in this polynomial must be smaller than $-b$, leading to a contradiction.


Prove/disprove: If $_1$ is a finite language but not empty and $_2$ is NOT regular then $_1 \circ _2$ is NOT regular

$L_1\circ L_2$ can certainly still be non-regular. For example, when $L_1$ contains exactly one word.

However, $L_1\circ L_2$ can be regular, too. Here is an example. Let $L_1=\{\epsilon,0\}$. Let $L_2$ be the complement of $\{ 0^n1^n \mid n \gt 0 \}$.
As the complement of a non-regular language, $L_2$ is not regular while $L_1\circ L_2$, the set of all words over $\{0,1\}$, is regular.

Here are three similar exercises.

Exercise 1. Construct examples when the alphabet contains exactly one letter.

Exercise 2. Prove or disprove: If $L_1$ is a finite language but not empty and $L_2$ is not context-free, then $L_1\circ L_2$ is not context-free.

Exercise 3. Prove or disprove: If $L_1$ is a finite language but not empty and $L_2$ is not recursive, then $L_1\circ L_2$ is not recursive.


Does Dijkstra’s assumes that the weights of edges in a graph searched by it are positive integers?

Dijkstra’s shortest path algorithm works for non-negative numbers. The Bellman-Ford algorithm works in the general case, i.e. works for the negative numbers, too.

  Does Dijkstra’s assumes that the graph searched by it is free of cycles.

In an undirected graph, If there is no cycle, it is a Tree, not necessarily rooted. The paths are unique. Dijkstra’s algorithm can work with cycles.

You probably mean that free of negative cycles; If there is a negative cycle and the source can reach it, then the cost of path has not defined.

  Relaxing an edge is same as setting its weight to 0.

Relaxation is historical naming, the correct name is tighten. Relaxation tests an edge wheater in can improve the current estimate of a node.

  Does Dijkstra’s yields only costs of shortest paths, requiring lot of extra computation to find the intermediate vertices on shortest paths.

Actually, it yields the shortest paths tree with their values, the running time is $\mathcal{O}((V+E)\log V).$ If you look at the algorithm, it considers only the current neighbors while constructing the shortest path tree. The bottleneck is the extract-min operation on the Heap. For a theoretical speed up, one can use Fibonacci Heaps that yield $\mathcal{O}(V \log V + E)$

During the relaxation process, the predecessors updated only if there is a need for relaxation. When the Dijkstra's algorithm finishes, the shortest path tree is ready.

  Dijkstra's useful only when edge weights are geographical distances along paths traversed on ground or water.

Remember, Dijkstra's algorithm can find one-to-all shortest path if the Graph is weighted and directed. It doesn't care where the map is taken as long as it is modeled as a Graph. However, if the graph is an actual map and/or there is also a heuristic distance information one can achieve better than Dijkstra's algorithm, see A* and this comparison article Engineering Route Planning Algorithms.


Is the multiplicative constant in the Big O notation are ignored because of Linear Speed-Up theorem?

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.


I'm assuming $n$ is the accuracy needed (in bits). Assuming that your starting point is reasonable, you converge in $O(\log n)$ iterations, just as in Newton's method. The absolute number of iterations is smaller than in Newton's method — Newton's method converges in $\log_2 n$ rounds, Halley's in $\log_3 n$ rounds (roughly speaking). However, this difference is lost in big O notation. For this reason, when analyzing methods like this, it is more meaningful to count function evaluations, keeping in mind that derivatives (and second derivatives in the case of Halley's method) may have a different complexity than the function itself.


Read the definition of NP and co-NP. By that definition, every problem in P is automatically both in NP and co-NP. There’s nothing to prove, that’s how they are defined.


Is the language of all deciders recognizing empty language decidable?

$E_{decider}$ is even unrecognizable.

Suppose a TM $E$ recognizes $E_{decider}$, we construct a TM $N$ recognizing $\overline{H}=\{\langle\langle M\rangle, w\rangle\mid M(w) \text{ doesn't halt}\}$, which is known as unrecognizable, thus a contradiction. $N$ works as follows.

On input $\langle\langle M\rangle, w\rangle$:

Construct a TM $M_w$ working on input $x$ as follows

Run $M$ on $w$ with at most $|x|$ steps.
If $M$ halts, loop; otherwise, reject.

Run $E$ on $\langle M_w\rangle$.
If $E$ accepts, accept; otherwise, reject.

If $M$ halts on $w$, then there exists some $x$ such that $M_w$ does not halt on $x$, which means $M_w$ is not a decider. Therefore $E$ does not accept $M_w$, so $N$ does not accept $\langle\langle M\rangle, w\rangle$.

If $M$ does not halt on $w$, then $M_w$ halts and reject any string $x$. Therefore $E$ accepts $M_w$, so $N$ accepts $\langle\langle M\rangle, w\rangle$.

Now the proof is complete.

In addition, your argument about $A_{decider}$ is wrong, because the TM in input may not be a decider and you should reject (not loop) on such case. In fact, you can prove $A_{decider}$ is also unrecognizable using similar technique.


If I understand you correctly, a minor modification of the absolute value should work, where you do digit-wise absolute difference and keep the magnitude:
$$
\sum_i \left| x[i] - y[i] \right| \cdot 10^{i}
$$
or in Python:
def dist(x, y):
    xs, ys = str(x), str(y)
    l = len(xs)
    diff = lambda a, b, i: abs(int(a[i]) - int(b[i])) * 10**(l-i-1)
    return sum(diff(xs,ys,i) for i in range(len(xs)))

To illustrate with your examples:
dist(111111, 111152) = 41 > dist(111111, 111125) = 14

dist(111000, 110999) = 1999 > dist(111000, 111001) = 1

You say (south v north) that this should be a very large diff, and that it is:
dist(123456, 223456) = 100000


Possible error in Computer Networks, V Edition by Tanenbaum & Wetherall

I don't have a copy of this book to confirm the context, but I suspect that the sentence as written was intended to be interpreted as:

Multimedia applications in particular, often need the network to provide guarantees of a certain minimum throughput and maximum latency to work.

In other words, in order for a multimedia application to function, the channel must ensure at least a certain throughput and at most a certain latency—exactly what is written.
The key word to notice here is the indefinite article "a". Both of the following sentences are correct, with different meanings:

Multimedia applications often need a minimum throughput and maximum latency to work.
Multimedia applications benefit from maximum throughput and minimum latency.

To further confuse matters, the following sentence means the same thing as 2.

Multimedia applications benefit from a maximum of throughput and a maximum of latency.

Isn't English grand?