How to prove every context-free language over a unary alphabet is regular?

The following proof follows Pighizzini, Shallit and Wang, Unary Context-Free Grammars and Pushdown
Automata, Descriptional Complexity and Auxiliary
Space Lower Bounds.

Let $L$ be a unary context-free language. Assume for simplicity that $\epsilon \notin L$, and consider a grammar $G = \langle V,\{a\},P,S \rangle$ for $L$ in Chomsky normal form. Denote $h = |V|$.

In the sequel, whenever we say parse tree, we mean parse tree in $G$.

Let $\Pi$ be the collection of all triples $(U,i,j)$ such that $U$ is a parse tree rooted at some nonterminal $A$ which represents a derivation of the sentential form $a^i A a^j$, where $0 < i+j < 2^h$.

Let $(U,i,j) \in \Pi$, and let $A$ be the label of the root of $U$. Given a parse tree $S$ containing a node $v$ labeled $A$, we can "pump" $S$ by $U$ by replacing $v$ with a copy of $U$, attaching the children of $v$ to the leaf of $U$ labeled $A$.

Lemma. If $\ell > 2^{h-1}$ and $a^\ell \in L$ and $T$ is a parse tree for $a^\ell$, then there exists a triple $(U,i,j) \in \Pi$ and a parse tree $S$ for $a^{\ell-i-j}$ such that $T$ is obtained from $S$ by pumping by $U$.

Proof. Since $\ell > 2^{h-1}$, $T$ must have depth at least $h+1$ (recall that the last level corresponds to productions of the form $A \to a$), and so a path of length $h+1$ edges. This path contains $h+1$ nonterminals, one of which must repeat. Consider such a repetition within the last $h+1$ nonterminals of the path. The repetition corresponds to a triple $(U,i,j) \in \Pi$ (note $i+j < 2^h$ since we chose a repetition within the last $h+1$ nonterminals, and $i+j > 0$ since the grammar is in Chomsky normal form). By "pumping out" this derivation, we obtain the parse tree $S$ for $a^{\ell-i-j}$. $\quad\square$

Corollary. Every parse tree in $L$ can be obtained in the following way:

Start with a parse tree for some $a^\ell$, where $\ell \leq 2^{h-1}$.
Repeatedly pump by $U$ for some $(U,i,j) \in \Pi$.

Using this, we can construct an NFA for $L$:

Guess a parse tree for some $a^\ell$, where $\ell \leq 2^{h-1}$, and read the word $a^\ell$.
Set $X$ to be the set of nonterminals appearing in the parse tree.
Perform the following operation an arbitrary number of times:

Guess $(U,i,j) \in \Pi$ such that the label of the root of $U$ appears in $X$.
Read $a^{i+j}$.
Add all nonterminals in $U$ to $X$.

This shows that $L$ is regular.

Parikh's theorem can be proved in the same way.


How to resolve issue of circular definition for an `If` statement

One general rule of Turing completeness is that you need some form of conditional branching built into your model. A Turing machine, for example, can transition to a new state based on what it sees on the tape. Programming-language-wise, a while loop works, as does an infinite loop with a conditional break statement, or if and goto.

As such, if you have no form of conditional branching built into your model already, you can't create one out of nowhere—if your model isn't Turing complete, you'll need to add something else from outside to the model to make it so.

An "atomic" if statement will do the trick, certainly, as will something like Lisp's conditional. But whatever it is, it'll have to be implemented by the compiler or interpreter, rather than being created within the language itself.


Is changing or appending data an idempotent operation?

An operation $O$ is idempotent if $O(O(x)) = O(x)$. For example, if you update record $R$ to value $T$ and then again update record $R$ to value $T$, then it's the same as if you updated only once. But if you append $T$ to record $R$ twice, it's not the same as appending only once.


Take a moment for yourself to realize that if we can only substract a power of two, and the popcount can't change we have to subtract $01$ in a position where the other number is $10$. The result of that is always $01$ in that position, and the number doesn't change anywhere else.

In other words, the game is a series of swaps of $10 \rightarrow 01$, and the game ends if all ones are on the right hand side. Note that it's impossible for this game to end early - you can not get stuck. You will always end up at a position where all zeroes are on the left, and all ones are on the right.

So the only determining factor in a game is how many swaps it takes to get to the state where all ones are on the right, and there is no winning or losing strategy. The parity of the number of swaps it takes is the only determining factor.

So how many swaps does it take? Note that $1$s can't cross eachother, so if we numbered them and tracked them through swaps they'd remain in the same order in the final state. Each swap brings them one closer to their final position.

So if the $i$th $1$ (counting from the right, the rightmost $1$ is the $0$th $1$) is in position $k$ from the right, it needs $k - i$ swaps to get to its correct position. This gives us an algorithm to count the amount of swaps required:

i = 0
k = 0
total = 0
while n > 0:
    if n & 1:
       total += k - i
       i += 1
    n >>= 1
    k += 1

We now can just look at the parity of total to see who wins. Time complexity is $O(\log n)$.


Complexity calculation using a recurrence relation

Hint: Prove by induction on $n$ that $T(n) = n!$.

Note that a recurrence relation doesn't have a complexity. Rather, it defines a function. In many cases, this function is the running time of some algorithm, and then the time complexity of the algorithm is the solution to the recurrence.


Proof that language is not context-free with Parikh's theorem

If $L$ were context-free then, applying the homomorphism mapping both letters to $a$, also the following language would be context-free:
$$
L' = \{ a^{2n^2+2n} : n \geq 0 \}.
$$
According to Parikh's theorem, a unary language is context-free iff the corresponding subset of $\mathbb{N}$ is eventually periodic. Yet the sequence $2n^2+2n$ has arbitrarily long gaps, since $2(n+1)^2+2(n+1)-2n^2-2n = 4n+4$. Therefore the set $\{2n^2+2n : n \geq 0\}$ is not eventually periodic, and so $L'$ is not regular or context-free.


“Fuzzy” Chinese Remainder Theorem NP-hard?

If you allow arbitrary modulus (so $m_i$ is not required to be prime), your problem is NP-hard.  In particular, it is NP-hard to determine whether there exists any valid solution, even without the upper bound $B$.

To prove this, we can reduce 3SAT to the problem.  Suppose we have a 3SAT formula $\varphi$ over variables $v_1,\dots,v_n$.  Let $p_1,\dots,p_n$ be the first $n$ primes.  Then we will associate one congruence per clause of $\varphi$.  In particular, the clause $v_i \lor v_j \lor v_k$ corresponds to the congruence

$$x \equiv a \pmod{p_i p_j p_k} \text{ where } a \in U$$

and $U=\{c_{001},c_{010},c_{011},\dots,c_{111}\}$ contains seven values, where $c_{def}$ is the unique constant such that $c_{def} \equiv d \pmod{p_i}$, $c_{def} \equiv e \pmod{p_j}$, and $c_{def} \equiv f \pmod{p_k}$.  Do the same for each other clause; e.g., for $v_i \lor v_j \lor \neg v_k$, the set $U$ has the seven values $U=\{c_{000}, c_{010}, c_{011}, c_{100}, c_{101}, c_{110}, c_{111}\}$, and so on.

In this way, we obtain a system of congruences with one congruence per clause of $\varphi$.  We don't need an upper bound on $x$ (you can use the trivial upper bound $x < p_1 p_2 \cdots p_n$ if you like).  Then there exists a solution to this system of congruences iff the formula $\varphi$ is satisfiable. In particular, a satisfying assignment $(v_1,\dots,v_n)$ for $\varphi$ corresponds to a unique value for $x$ that satisfies all the congruences, namely, the value such that $x \equiv v_i \pmod{p_i}$ for all $i$.

This reduction does require the ability to choose moduluses that are not prime.  I don't know if the problem becomes any easier when every modulus is prime.


Having a better complexity / adversary argument for finding if a finite automata accepts a palindrome

You can solve this in $O(n^2)$, where $n$ is the number of states in the original DFA (or NFA), using your idea. Compute the product automaton of the original automaton and its reverse. The new automaton contains $O(n^2)$ states. As to the number of edges, in the original DFA, each state has $|\Sigma|$ outgoing edges, and in its reverse, there are $|\Sigma|n$ transitions overall. Let us denote by $a(q)$ the number of outgoing transitions from $q$ in the original DFA, and by $b(q)$ the number in the reverse DFA. Using $Q$ for the set of states, the total number of transitions in the product automaton is
$$
\sum_{q_1,q_2 \in Q} a(q_1) b(q_2) =
\sum_{q_1,q_2 \in Q} |\Sigma| b(q_2) =
|\Sigma| n \sum_{q_2 \in Q} b(q_2) =
|\Sigma|^2 n^2.
$$
Assuming $|\Sigma|$ is constant, this is $O(n^2)$.
Now check whether some final state is reachable from some initial state, using BFS/DFS, in  time $O(n^2)$.

We can prove an essentially matching lower bound given SETH. Recall that SETH states that for every $\epsilon > 0$ there is $k$ such that $k$-SAT cannot be solved in time $O(2^{(1-\epsilon) n})$, where $n$ is the number of variables. We will show how to reduce $k$-SAT to your problem.

Given a $k$-SAT formula $\phi$ with $n$ variables and $m = O(n^k)$ clauses, consider the following language $L$ of all words of the form $\alpha x \beta \gamma y \delta$, where:

$|\alpha| = |\beta| = |\gamma| = |\delta| = n/2$, $|x| = |y| = m$.
We think of $\alpha$ as an assignment for the first $n/2$ variables. If $x_i = 0$ then $\alpha$ must satisfy the $i$th clause.
We think of $\beta$ as an assignment for the last $n/2$ variables. If $y^R_i = y_{m+1-i} = 1$ then $\beta$ must satisfy the $i$th clause.

Any word in $L \cap L^R$ must be of the form $\alpha x \beta \beta^R x^R \alpha^R$, and so by construction $\alpha\beta$ satisfies $\phi$. Conversely, if $\alpha\beta$ satisfies $\phi$, then we can choose $x$ so that the corresponding word is in $L \cap L^R$, Hence $\phi$ is satisfiable iff $L \cap L^R$ is non-empty.

How many states do we need to accept $L$? We can read and store $\alpha$ using $O(2^{n/2})$ many states. Therefore using $O(2^{n/2} m)$ states, we can verify the second condition (on $\alpha x$). Similarly, we can verify the third condition (on $\beta y$) using $O(2^{n/2} m)$ more states. Verifying the first condition takes $O(n+m)$ more states, for a grand total of $O(2^{n/2} m) = O(2^{n/2 + o(1)})$ states.

If your problem could be solve in time $O(N^{2-\delta})$ (where $N$ is the number of states in the input automaton), then we would get an algorithm for $k$-SAT running in time $O(2^{(1-\delta/2)n + o(1)})$, and so obtain a contradiction if $\delta/2 \geq \epsilon$. This shows that assuming SETH, your problem cannot be solved in $O(N^{2-\delta)}$ for any $\delta > 0$.


According to the Wikipedia article on magic cookie, it was used already in 1979 in the manpage of fseek. The talk page of the Wikipedia article on magic cookie discusses questions regarding the origin and meaning of the word. The following quote of Douglas W. Jones from the talk page nicely summarizes it:

Once upon a time, I asked Dennis Ritchie about the origin of the term magic cookie as used in the man page for ftell and fseek in the C library. He said that, so far as he knew, the usage in that man page was a new coinage. That man page is not present in V5 UNIX but it is present in the manuals for V7 UNIX and 4.2BSD. I have quoted the relevant sentence from that manual on the Wikipedia page; the wording makes it clear that the meaning is the same as the contemporary meaning for magic cookie (in the broader sense than HTML cookie). Any speculation about derivation from cookie monsters or LSD cookies seems, at this point, irrelevant compared to tracking down the first use of the term in its modern sense. Douglas W. Jones 21:15, 24 February 2017 (UTC)


Binary search with alternative comparison cost

Let's say I told you in advance that $c$ is in the larger half. You still need $\Omega(\log n)$ comparisons, while now every helpful comparison takes $\Omega(n^2)$ cost, so the cost is always $\Omega(n^2\log n)$, which can be achieved with simple binary search.


Let us reduce REACH to TARGET. Given an instance $(G,s,t)$ of REACH, add edges from all nodes other than $s$ to $s$ to form a new graph $G'$. If $t$ is reachable from $s$ in $G$ then it is reachable from all other nodes in $G'$ using the new edges. Conversely, if $t$ is reachable from all other nodes in $G'$, then in particular it is reachable from $s$ in $G'$. Even if this path uses any of the new edges, all they can do is bring it back to the starting point, and so $t$ is reachable from $s$ already in $G$.

Altogether, we have shown that $(G,s,t)$ is a yes instance of REACH iff $(G',t)$ is a yes instance of TARGET.


Complexity of calculating a single model versus all models of a propositional formula with a SAT solver

The worst-case complexity of finding all models of a SAT formula over $n$ variables is roughly $\Theta(2^n)$.  (For instance, consider a formula where all assignments satisfy the assignment; then there are $2^n$ satisfying assignments, so just listing all satisfying assignments takes $\Omega(2^n)$ time.)

Nonetheless, this number probably isn't very useful in practice.  In practice, the running time to find all models depends heavily on the formula and on the number of models.  Standard methods for worst-case complexity don't offer a good way to summarize the time to do this, as the running time practice varies heavily.

So, for your paper, I wouldn't place much stock on this complexity figure.  I just don't think it is very illuminating.


Languages are defines with respect to a finite alphabet. Thus, integers cannot be represents just by giving a triplet as you suggest, you need to encode it.

For convenience, let's assume a decimal encoding, with the "$-$" sign for negation, and the character $\#$ separating the numbers. Thus, for example, the word $8\#12\#-3$ represents the triplet $(8,12,-3)$ (note that usually we would use a binary encoding, but it doesn't really matter). Call our alphabet $\Sigma$.

Now, a word $w$ is in the language you describe iff the following hold:

$w=a\#b\#c$ where $a,b,c$ are either words in {0,...,9}^$\setminus {0}^. That is, they represent positive numbers (we allow leading 0's here, but we could also formulate without them).
There does not exist $x\in \mathbb{Z}_+$ such that $x<a$.

Note that we did not do anything yet, just wrote down the language. In particular, we purposely ignore the fact that condition 2 simply means that $a\le 1$.

The formal complement of your language is the set of words that either don't satisfy condition 1, or don't satisfy condition 2 (or both).

You could write this more succinctly or more explicitly, as words that are either not of the form $a\#b\#c$ with the condition 1 above, or words that are of that form, but where $a$ is not of the form $0^*1$.

It should be mentioned that once you are familiar with the notion of languages, we usually don't dig down to this level of formality, and in fact we would ignore the encoding somewhat. Then, you might see things such as
$\overline{L}=\{(a,b,c)\in \mathbb{Z}: \exists x\in \mathbb{Z}_+ \wedge x<a\}$.

Also note that throughout this answer we do not distinguish between a word and its numeric value, but if you really want to nitpick, then such a distinction should be made.


Placing a fixed number of points on a curve to make the finite second derivative constant

In a nutshell

The problem can be solved algebraically by considering the equations as
defining $y_i=f(x_i)$. This gives $n-1$ equations with $n$ unknowns ($y_i$ for $i\in[2,n-1]$, and the values of $c$ and $u$ defined below),
resulting in the abitrary choice of one value. The answers are given
by the formula
$$x_i=f^{-1}(f(a)-(i-1)u+c\frac{(i-2)(i-1)}{2})$$

and the value of $u=f(a)-f(x_2)$ is determined from that of the
constant finite second derivative $c$, or the reverse, with the linear
relation
$$f(b)=f(a)-(n-1)u+c\frac{(n-2)(n-1)}{2}$$

However I wonder if the formula used is really that of a finite second
derivative.

Full proof

With the formula used, your question seems rather tractable, and solvable algebraically.

Like the previous answer, I note $c$ the value of the constant finite second derivative, as defined in the question (though this is further discussed below).

You should see it as a set of equations in $y$, with $y=f(x)$.
If you note $y_i=f(x_i)$, you get a set of $n-2$ equations
 $$y_{i-1}-2y_{i}+y_{i+1}=c\;\; \text{ for }i\in [2,n-1]$$
with $n-1$ unknown : $y_{i} \text{ for }i\in [2,n-1]$ and $c$, given
that you have $y_1=f(a)$ and $y_n=f(b)

This probably means an infinity of solutions, which may means that you
can choose arbitrarily one of the values, for example that of $c$.
I have not worked out the equations.

However, given the strictly monotonically decreasing function $f$ of your example, you have the
additional constaints that:
$$ \forall i\in[2,n-1], \;\;y_i\in(f(a), f(b)) \;\wedge\; y_i>y_{i+1} $$

One way to start resolving it is by defining $u_i=y_i-y_{i+1}$ and $v_i=y_i-y_{i+2}$ for $i\in [1,n-2]$. Then the equations become
$y_i-2(y_i-u_1)+(y_i-v_i)=c$ which simplifies into
$2u_i-v_i=c$, from which we derive $v_i-u_i=u_i-c$.

From the definition of $u_i$, $u_{i+1}$, and $v_i$, we derive $u_{i+1}=v_i-u_i$. Hence $u_{i+1}=u_i-c$. From this recurrence relation we get $u_i=u-(i-1)c$, where $u$ is defined as $u=u_1=y_1-y_2$.

So we now have the simpler recurrence relation: $y_{i+1}=y_i-u_i=y_i-(u-(i-1)c)$, i.e., $y_{i+1}=y_i-u+(i-1)c$, from which we get
\begin{align}
 y_i&=y_1+\sum_{k=1}^{i-1}{u_k} \\
 &=y_1+\sum_{k=1}^{i-1}{-u+(k-1)c} \\
 &=y_1-(i-1)u+c\sum_{k=0}^{i-2}{k} \\
y_i&=y_1-(i-1)u+c\frac{(i-2)(i-1)}{2}
\end{align}
This last formula is valid for $i\in[1,n-1]$, since the recurrence formula is defined for $y_{i+1}$ and the equations used were defined for all values of $i$ up to $n-2$.
We must now consider $y_n$. Since $v_{n-2}-u_{n-2}=u_{n-2}-c$, we get $y_n=y_{n-1}-(u_{n-2}-c)$.
Since $u_{n-2}=u-(n-3)c$, we finally obtain
$\begin{align}
 y_n&=y_1-(n-2)u+c\frac{(n-3)(n-2)}{2}-u+(n-3)c+c \\
 &=y_1-(n-1)u+c\frac{(n-2)(n-1)}{2}
\end{align}
$

Hence our formula for $y_i$ is correct for all $i\in[1,n]$.

Note: a much simpler technique for $y_n$ would be to consider an extra point at $y_{n+1}$ on the curve, so as to have more equations. But all this was already written when I thought of it.

Considering that we have the last constraint $y_n=f(b)$, we can use it
with the equation for $y_n$ to determine $u=y_1-y_2$ if we wish to
choose $c$, or to determine $c$ if we rather choose $u$.

This is easily rephrased into the result given at the beginning of this answer. Then it should be easy to apply it to the example in the
question.
However, I do wonder whether all this is useful, because I am not sure this is the question you intended to
ask.

The reason is that the formula given in the question is not the formula of the finite
second derivative. The proper formula is something like:
$$4\times\frac{f(x_{i-1})-2f(x_i)+f(x_{i+1})}{(x_{i+1}-x_{i-1})^2}$$

See for example higher-order finite differences in wikipedia. Though I am not sure that even this corrected formula is meaningful as, the formula normally given assumes that $x_i= (x_{i-1}+x_{i+1})/2$. But the expression you use is somewhere between the formulae for forward and backward finite differences, and should thus be usable with some meaning.

Thus, if I am correct, you should edit your question to make it consistent, either by
removing the reference to the finite
second derivative, or by using the proper formula for it.


Sample a scale free subnet from random network

In order to do this, you need high degree nodes in your initial network: since you do not add anything, degree may only decrease, and you want high degree nodes in the end.
Now, assume your initial random network indeed has high degree nodes. Since it is random, choosing random links in it will often lead to high-degree extremities. Indeed, the probability to pick a degree $k$ extremity when you choose a link at random is proportional to $k$.
This property underlies the works conducted to estimate bias in internet measurements. Several works show that power-law networks may indeed be obtained from initially random networks, for instance by taking a BFS tree.
See e.g. On the Bias of Traceroute Sampling; or, Power-law Degree Distributions in Regular Graphs for a formal analysis published in STOC and Journal of the ACM, as well as Relevance of Massively Distributed Explorations of the Internet Topology: Qualitative Results for an experimental work published in INFOCOM and Journal of Computer Networks.


Sorting array containing elements from $\{1,\ldots,k\}$ in place in $O(n\log k)$

Here is an idea. Use a variant of quicksort with a twist:

Find the median $m$ in-place in time $O(n)$ (this could jumble the array).
Partition the array around $m$ using the quicksort partition routine.
Divide the array into three parts: smaller than $m$, equal to $m$, and larger than $m$, and recurse on the first and the last.

Consider a recursion tree for this algorithm. The tree has depth $\log n$ and $k$ nodes. Imagine "compressing" the tree by short-circuiting all nodes having only one child. You get a tree with depth $\log k$. Can you justify this short-circuiting and prove a running time of $O(n\log k)$? Or is there a counterexample?


True or False: If $A \subseteq \{0,1\}^* \Rightarrow A^*$ is semi-decidable

It is not true that every language is recursively enumerable ("type 0").

Proof 1. Every RE language is semi-decided by some Turing machine. There are only countably many Turing machines (each one can be coded as a finite string, or an integer) but there are uncountably many languages.  Therefore, there are uncountably many languages that are not RE.

Proof 2. If a language and its complement are both semi-decidable, they are, in fact, both decidable.  The halting problem is semi-decidable. If the complement of the halting problem were semi-decidable then both it and the halting problem would be decidable. But we know that the halting problem is not decidable. Therefore, the complement of the halting problem is not semi-decidable.


Construct context free grammar from language

You are right, the point is having nonterminals that sheds 0 and 4, or 0 and 3, or 1 and 4, or 1 and 3, switching from one to the other to get the $0^1 1^b$ and corresponding $3^d 4^e$; once you have that, go to one that repeats to make $2^c$ in between. The $5^f$ is easy to append.


Binary-ish search through partially ordered set

Here is a simple algorithm that runs in $O(N^2)$ time and $O(N)$ space, assuming that $f(\emptyset)$, $f(\{1\})$, $f(\{2\})$, $\cdots$, $f(\{N\})$ are given in an array.
The starting idea is about the same as what has been given by the OP in his comment. "We will search on subsets of size K using the lexicographic order, for each $K$ from $0$ to $N$. Retain the one with the best value of $f$."
The problem is then how to search the best value of $f$ on subsets of size $K$, named $b_K$, in $O(N)$ time. Instead of binary search, we will check whether $N$, $N-1$, \cdots, $1$ should be included in the best subset one by one, by taking the real advantage of the lexicographic order on subsets.

Initialize $b_K = f(\emptyset)$. $\ b_K$ will be the best value on subsets of size $K$ at the end of this procedure.
Initialize $count = 0.$ $\ count$ is the number of elements that we have included in the best subset so far.
Check $f(\{N\})$. If $b_K + f(\{N\}) + f(\{1, 2, \cdots, K-count -1\})\le z$, $N$ must be included. Add $f(\{N\})$ to $b_K$ and add 1 to $count$.
Check $f(\{N-1\})$. If $b_K + f(\{N-1\}) + f(\{1, 2, \cdots, K-count-1\})\le z$, $N-1$ must be include. Add $f(\{N-1\})$ to $b_K$ and add 1 to  $count$.
And so on.
Until either we have checked $f(\{1\})$ or $count == K$.

We might wonder, if it will take $O(N)$ to compute each $f(\{1,2, \cdots, K-count-1\})$, computing each $b_K$ alone will take $O(N * N)$ time. However, since $f$ is additive, we can compute all prefix sums of $f(\{1\})$, $f(\{2\})$, $\cdots$, $f(\{N\})$ upfront in $O(N)$ time. Then it takes $O(1)$ to access each prefix sum.
Since searching $b_K$ takes $O(N)$ time, for each $K$ from $0$ to $N$, the total running time is $O(N^2)$.

The description above of the algorithm skips the easiest case when $f(\emptyset)\gt z$. In that case, the algorithm should return that there is no such subset.


Number of permutations of set {1, 2, ..., n} for which insertion sort will perform exactly n permutations

Your analysis looks correct to me. The answer should be N-2, not 2(N-1).

It wouldn't be unheard of for graders/teachers to work with an incorrect solution.


Help needed for understanding proof of No Regret Multi Armed Bandit Algorithm

I don't think you wrote anything incorrect, it's just that you didn't finish your proof yet. How are you going to go from there to an actual bound on the regret? You're going to have to use the regret guarantee of the gradient descent algorithm. But we didn't run Gradient Descent on all of the time steps. We only ran it on the time steps not in $S_T$. So we get a regret bound for the steps not in $S_T$ from gradient descent, which is $O\left(\frac{n}{\delta}\sqrt{T}\right)$. And we have to use a separate bound for the time steps in $S_T$. The proof uses the easiest one: at each such step, at worst, the algorithm has loss $1$ while $i^*$ has loss zero, so the contribution to regret from that step is at most $1$, for a total of $|S_T|$, which in expectation is $\delta T$.

As a sidenote, I am not sure that independence of $i^*$ and $\hat{\ell}_t$ is really being used, maybe it is just linearity of expectation (?).


Data structure and structural relationships

Your citation is incorrect--this is on page 232 in 3rd edition, not 252 (first paragraph of "Information Structures", chapter 2.1.
Based on having the chapter available, Knuth is talking about data structures in general. I agree the with suggestions above--just ignore this paragraph if it doesn't make sense or seems obvious. I personally agree that it does not seem to define anything or communicate anything clear to me.


Fastest algorithm to find whether a list contains a word?

If you are given an unordered list and asked to test whether just one item is in the list then a sequential check of each item in the list is the best you can do.

If you want to carry out multiple tests (but you do not know all the test items in advance) then it is worth the initial overhead of sorting the list, creating a hash table, or creating a search tree.


In which paper is written that you can transform one problem to another to show NP-completeness?

If I may make an assumption, you want such a reference to be able to put it in one of your works, right ? I don't why you would wanna do that as if you have a problem A, reducting a NP Hard problem to problem A quite clearly shows that A is NP Hard. No one bothers proving it as it's such a straightforward and fundamental result. If you need to prove it for some reason you can do it in two lines. If you still want a reference for a reader to read about NP in general then just quote Arora and Barak's book on complexity theory.


SVMs - Fat (Margin) Boundary: Why is $\max\frac1{||\theta||}=\min \frac{ ||\theta||^2}{2}$?

Minimizing $\|\theta\|$ is equivalent to minimizing $\|\theta\|^2/2$, in the sense that the minimum is achieved for the same value of $\theta$.  Since our goal is primarily to find $\theta$, this substitution is not unreasonable.
Why was the substitution done?  I don't know.  Perhaps because it makes the resulting optimization easier; or just because it seemed simpler.  Note that while $\|\theta\|$ might look "simpler", in some sense it is an uglier function, as it involves a square root, which can be messy to deal with.  The way to figure out would be to understand the basic derivation using $\|\theta\|^2/2$, and then try replacing with $\|\theta\|$ and see if the same logic goes through or if there is a barrier.


Combinatorial optimization algorithm with constraints and objective function

You can indeed formulate an Integer Linear Program. Let $x_i \in \{0,1\}$ denote whether you select item $i$. For each item $i$ define $f_a(i)$,  $f_b(i)$, and $f_c(i)$ as the integer values for the properties $A$, $B$, and $C$.
Then we define the objective function as maximizing $\sum_{i = 1}^{m} f_a(i) \cdot x_i$, given $m$ items in total.
Your constraints are very similar as well, namely $\sum_{i = 1}^{m} f_b(i) \cdot x_i \geq 50$, and $\sum_{i = 1}^{m} f_c(i) \cdot x_i \geq 60$.
Since you can select at most $n$ of those $m$ items, you need to following constraint: $\sum_{i = 1}^{m} x_i \leq n$.
You can then easily recover the solution from your variables. Simply check whether $x_i = 1$, and if so, add item $i$ to your solution.


Reducing the halting problem for a language with strings that include at least one 1

Original Question:

$L_1 = \{w \in \{0|1\}^* | \text{ w is a sequence of one or more 1's } \}$

$L_2 = \{\langle M \rangle | \text{ Turing machine } M \text{ decides } L \}$

prove that $L_2$ is undecidable.

Answer:

For first part you are correct.
First language $L_1$ is indeed decidable. Actually it is regular as represented by regular expression $1^+$.

Now coming to second one $L_2$. This language is as you said undecidable. And you can prove it by reducing halting problem which is known to be undecidable to this problem.

For doing this you have to create an instance of problem in question such that solving it gives us solution of halting problem.

Now formally we can define turing machine $\tau\langle M, w\rangle =M'$. Where $M'$ is a turing machine which started on input $x$ checks if $x$ is of form $1^+$. If no then it rejct it immediately. Otherwise it erases $x$ from it's tape then copies $M$ and $w$ on its tape and simulates $M$ on $w$. If $M$ stops then it accepts $x$(which it have erased).

Proof of validity of reduction:

$M$ halts on $w$ $\implies$ $M'$ accepts  all and only strings of form $1^+$.

$M$ does not halt on $w$ $\implies$ $M'$ accepts empty set. In particular it does not accept strings of form $1^+$.

So now if there would be any turing machine that decides $L_2$ then we can use it to find whether $M'\in L_2$ or not? If it outputs yes then we infer that original $M$ halts on $w$. Otherwise we infer that $M$ does not halt on $w$.

And because we know that halting problem is undecidable we conclude that no such turing machine exists which can decide $L_2$ and consequently $L_2$ is undecidable.

Hence proved.


What are the first computer science papers that used asymptotic time complexity?

with history questions there are typically subtle nuances and its not easy to determine a particular paper that introduced a particular concept because it tends to be spread over many contributors and is sometimes rediscovered independently when obscure early references dont necessarily disseminate (fundamental ideas are like that). but the history basically goes something like this: Landau notation is an old mathematical formalism (1894/ Bachman)[1] which was imported into CS as a "key concept" around the early 1970s. by the mid 1970s this was somewhat accepted as in your Knuth reference and Knuth himself was involved in spreading this concept.

interestingly its import into CS was probably closely related to the P vs NP vs Exptime distinctions uncovered in early 1970s which were highly influential/ heralded in the field. it was Cobham/ Edmonds who started to define the class P in early 1970s.[3] there were early proofs about Exptime and Expspace by Stockmeyer/ Meyer.[2] the Cook-Levin theorem[4] (1971) showed the core relevance of P vs NP time, immediately supported by Karp[5] (1972).

an early mathematician who worked in number theory but also on the edge of computer science was Pocklington. as in [3] it points out:

  However, H. C. Pocklington, in a 1910 paper,[11][12] analyzed two algorithms for solving quadratic congruences, and observed that one took time "proportional to a power of the logarithm of the modulus" and contrasted this with one that took time proportional "to the modulus itself or its square root", thus explicitly drawing a distinction between an algorithm that ran in polynomial time versus one that did not.

another early pioneer in analyzing complexity of machine-based algorithms for number theory, ie factoring, was Derrick Lehmer, professor of mathematics at University of California, Berkeley, and built/ analyzed factoring "algorithms" (sieve based implementations) as early as the 1920s and its possible he may have described something like computational complexity wrt factoring in an informal way.[6]

yet another case is a "lost" 1956 letter by Godel to von Neumann talking about complexity measurements of steps f(n) of a machine to find proofs of size n.[7]

[1] Big O notation history / wikipedia

[2] Word problems requiring exponential time. / Stockmeyer, Meyer (1973)

[3] P time class history / wikipedia

[4] Cook-Levin theorem / wikipedia

[5] Karps 21 NP complete problems / wikipedia

[6] Lehmer factoring machine/ sieve / wikipedia

[7] Godels lost letter / RJLipton


Of course "instinct"always helps, but writing a grammar is more or less writing a program, but with limited resources.

Your example matches a regular language. Those languages can be defined using right-linear grammars but I prefer finite state automata. Programming linear grammars (and finite state automata) requires thinking in states. What is the characteristic information about the string I have seen so far.

In your example the "state" consists of the last letter read. OK, since your task is to avoid reading a letter twice. In other examples you might want to do some counting ("if the string contains exactly four $a$'s it ends in $b$") or modulo counting ("the number of $a$'s is even"). Perhaps you want to do a kind of pattern recognition ("words that do not contain $00110$") and you keep track of the part of the pattern you have just seen.

Sometimes the requirements consist of a Boolean combination of properties. Then you keep track of both of them in the state and react on what you know.

You see: just like programming.

If the grammar is more complicated, like context-free you probably want to think in terms of trees. That is the structure they use to derive strings.


Polynomial generator required to detect single bit error in Cyclic Redundancy Check codes

You just need to concentrate on the polynomial division here. First consider the case where we need to detect one - bit error . For this case

$ e(x) = x^k $

we can choose any polynomial with terms >=2 , since it will not divide the error polynomial completely .

Next let us see the case of odd number of errors. Notice how this is different from one bit error. This is a burst error. Consider the polynomial

$ g(x) = (x+1) $

If we multiply this polynomial with any other polynomial the number of terms we get as a result is always even. This result in general is true you can try this for assurance.

Consider any error polynomial with odd number of errors . This polynomial will have odd number of terms in the polynomial. example :

$e(X) = x^3 + x^2 + x $

Now

$\nexists p(x)   \quad  such\quad that \quad  p(x) * g(x) = e(x) $

In other words no polynomial could be fund which gives odd number of terms when multiplied by x+1 . This observation suggests x+1 should be a factor of our generator function in order to catch odd- number of errors. As 1 - bit error is an odd-bit error x+1 also detects one - bit errors. Both books are correct in their reasoning.


How would one implement a Frequently Used algorithm?

You are running into a situation where the task is not "here is a specification of what constitutes a good value, find the best one", but "find a result that is as useful as possible to the user, with no clear specification what 'useful' means".

It's a difficult problem. You can't even ask the users what they think is most useful - because they don't know, and even if they have an opinion what they think is most useful, that doesn't necessarily agree with reality.

You might also consider that changing the set of emojis is of slight negative value because it's harder to find one if the set is changing. On the other hand, emojis that are easy to find anyway (for example smileys that come first in the ordinary list) are less useful. And you might consider context, a user might use different emojis depending who is going to receive the message. Imagine the software knows the receiver, and knows it is their birthday, and suddenly the set of "most useful" emojis totally changes.

I'm not sure if I would count this under "algorithm", because the real problem is not the algorithm, but producing heuristics what makes a good set of useful items.


I will try to answer to your question with an example.
Consider the following time complexity: $f(n)=2^\frac{n}{1000}$.

It is clearly exponential in $n$, but look at the plot.

For $n \in [0,80]$:

From this perspective it looks constant, right?

For $n \in [0, 1.5 \cdot 10^4]$:

From this perspective everything changes.

What I want to show, is that inferring the complexity just looking at the runtime with different inputs size is not possibile.


Why is a (collision-less) hashtable lookup really O(1)?

The hash function doesn't return some string such as mkwer. It directly returns the position of the item in the array. If, for example, your hash table has ten entries, the hash function will return an integer in the range 0–9.


What is the name for this search algorithm?

You may be interested to a related algorithm, known as Interpolation Search, which achieves on average the complexity of $O(\log \log n)$ for searching $n$ keys. This is the usual search you do when you scan a phone book for example.

This paper discusses the algorithm, which was originally introduced earlier (1957) by Peterson.

Related data structures: dynamic interpolation search and interpolation search for non independent data.


Collision resistant Hash function in chaos cryptography

Chaos-based encryption ain't an active area of research among the best crypto researchers; it's looking like a dead end.  You might find papers published on the topic, but they're generally in lower-reputation conferences.  Why is it a dead end?  Because it doesn't seem to work.  The schemes typically end up being either insecure, or worse than existing algorithms (e.g., slower).  Basically, it initially sounded like an intriguing idea, but at this point I would advise you that studying chaos-based cryptography appears to be a waste of your time, if you want to accomplish something useful or practical.  (See also https://security.stackexchange.com/q/31000/971, though it doesn't really address this point.)

You can't prove collision-resistance.  Even the state-of-the-art hash functions don't come with a mathematical proof of collision-resistance.  See https://crypto.stackexchange.com/q/18730/351 and https://crypto.stackexchange.com/q/26094/351 and https://security.stackexchange.com/q/5101/971.


Check whether loop invariants are correct?

Rather than telling you whether your specific invariants are correct, let me teach you the procedure for how you can check whether your invariants are correct on your own.

Basically, you break it down by looking at each chunk of code separately.  For each chunk of code, you look at the invariant before it and after it and see whether they're consistent with that chunk of code.  If this check passes for all of the chunks, you're done: you're entitled to conclude that your program is "correct".  The beauty of this is that this helps you break down the task into small manageable pieces.  You never have to think about the entire program as a whole -- you only look at one chunk, in isolation, at any given time.

The way you verify a chunk of code depends on what kind of statement it contains.  There are only a few cases you need to worry about:

Straight-line code. Suppose you have a statement with no branching, e.g.,

{P}
stuff;
{Q}

What you need to do is check that if P is true before the statement, then after executing the statement, Q will surely be true.  In other words, if all we know about the state of the program is that P is true, and then we execute stuff, then afterwards it is guaranteed that Q will be true.

Notice that you check this by looking only at P, Q, and stuff: you shouldn't need look at any code in the rest of the program.  If you find yourself trying to think about what the rest of the program is doing or ways you might be able to reach this chunk of code, you're doing something wrong, and probably you need to strengthen P (add some additional clauses that record more information about what states of the program are possible at that point).
Loops.  Suppose you have a while-loop, e.g.,

{P}
while (e) {
    {Q}
    stuff
    {R}
}
{S}

Then you need to check four things.  First, you need to check that the path that skips the loop entirely is valid, i.e., check that P && !e implies S.  Second, you need to check that, on the first iteration of the loop, the loop invariant will hold: i.e., check that P && e implies Q.  Third, you need to check that on any iteration of the loop, the following is valid:

{Q}
stuff
{R}

Fourth, you need to check that R && e implies Q.  Fifth, you need to check that on the last iteration, S is enforced, i.e., that R && !e implies S.  If all of these checks pass, then your invariants for the while-loop are OK.

Here's a different way to think about it that might feel more intuitive.  You can try to find an invariant T that lets you annotate the loop with

{T}
while (e) {
    {T && e}
    stuff
    {T}
}
{T && !e}

All you need to check is that the following code block is valid:

{T && e}
stuff
{T}

If that code block is valid, then the entire while-loop construct is acceptable.
Conditional statements. If statements can be handled similarly, but are a bit easier than while-loops.  For instance, if you have

{P}
if (e) {
    {Q}
    stuff
    {R}
}
{S}

then you need to check both the false-path and the true-path through the conditional.  To check the false-path, check that P && !e implies S.  To check the true-path, check that P && e implies Q, that R implies S, and that the following is valid:

{Q}
stuff
{R}

In this way, you should be able to check all of your invariants step-by-step.  The only two things you need to know how to do are: (1) check whether one logical formula implies another, and (2) verify invariants for straight-line code.  Everything else reduces to those operations.

With practice, you'll find that this becomes pretty mechanical.  And with practice, you'll find that many of these invariants can be omitted (if it's straightforward for a reader to re-derive them), but when you start out, it's best to be verbose and include them all, without trying to omit stuff.


How can this grammar parse such an input?

In an attribute grammar one assigns values to the nonterminals of the grammar. This is to help evaluating parts of a grammar that are not context-free. One of the simple types is inherited attributes, these are assigned bottom-up in the derivation tree.

The indexes $S_0$ and $S_1$ are used here to distingish different occurrences of the nonterminal $S$ in the grammar. A good choice for an attribute here would be the difference of the number of occurrences $b$ and $a$. This number should never be negative according to your specification. I do not know how you are supposed to denote this, but assume the attribute is called $N$. For the rule $S_0 \to S_1 a$, the value of $N$ for $S_1$ determines the value of $N$ for $S_0$: $S_0.N = S_1.N - 1$ (since $S_0$ has one more $a$ than $S_1$.

Similarly for the other rule that introduces a $b$.

Now we have to introduce another attribute. In the end we should test whether the last symbol derived is a $b$. So the attribute should remember that letter and test it in the last step $V\to S$ (this is the last step in a bottom-upevaluation).

Again: check your class notes on how to specify alle these details.

Your examples are not clear: $aa$ does not end in a $b$ and neither has it at least as many $b$'s (?!)


Every CPU has, at the very least, some internal registers: a program counter, a register storing flags, and in some architectures, an accumulator (though the latter isn't strictly required).

As you mention, registers are important for speed reasons. CPUs are designed with efficiency in mind. There are no drawbacks to having (external) registers, so I conjecture that all CPUs have them.


A criterion for the planar graph to have unique dual

First let me mention that the definition of being uniquely embeddable requires ANY graph isomorphism (e.g. just renaming symmetric vertices or any other automorphism permutation) to be (not necessary uniquely) extendable to topological (or combinatorial) one (see Diestel Graph Theory chapter about planar graphs for these definitions) in contrast to usual understanding of this definition that for any two planar embeddings there EXISTS some topological (or combinatorial) isomorphism. Difference between the topological and combinatorial isomorphism definitions is negligible for 2-connected planar graphs (see Diestel book). This particularly means that if we reflect or twist some symmetric graph (as done in the proof of necessity of the aforementioned criterion "subdivision of 3-connected planar graph if and only if condition to be embeddable" in the book "Planar Graphs: Theory and Algorithms") we get topologically non-isomorphic graph in general. Though $K_{2,3}$ graph witnesses that the necessity proof here is wrong but the sufficiency is hold.

What I mean by complex-based isomorphism is just combinatorial one from Diestel book.

If we allow my unusual definition of uniqueness that any two embeddings are topologically isomorphic then there is an example of 2-connected non-subdivisions that are uniquely embeddable.

As for aforementioned paper "Uniquely embeddable planar graphs" the special definition which is given there is tougher (not robust to transposition of symmetric vertices) (but close to as Yuval assumed) than topological isomorphism according to its Theorem 3.5.


Is there an approximation algorithm for Minimum Test Collection Problem?

Yes, there are approximation algorithms for this problem.

If $k$ is the upper bound of the test case, the authors of http://repository.cmu.edu/cgi/viewcontent.cgi?article=1397&context=tepper
constructed a $O(\log{k})$-approximation algorithm
Another approximation algorithm of the same complexity is derived here:
https://link.springer.com/chapter/10.1007/3-540-44676-1_13

Hope that helps!


requirement for pumping lemma in regular language

$|vx| < p$ mean that $x$ is short and it is at the beginning of $w$. If you were to remove that constraint, all regular languages would still satisfy the lemma, but more irregular ones would too. For example $L = \{a^n \mid n ~\text {is not prime}\}$, when $n = m \cdot k $ can be pumped by taking $x = a^k$.


Yes! Various languages and APIs often specify the precision you are guaranteed.  If the underlying hardware doesn't offer that precision, they must emulate it with extra work.  For instance, some machine instructions that compute transcendental function (sin, cos, exp, log, ...) only offer a limited accuracy. Library implementations that guarantee a certain accuracy must execute extra instructions to accomplish that by correcting the error and improving the approximation.

As a concrete example, consider the native_sin function in OpenCL.  The error is "implementation defined." On the other hand, the regular sin function promises a certain accuracy and implementation of OpenCL must make that happen regardless of the extra work.


Why this pattern matching fails in Agda?

First, let's desugar the withs.

First definition:

wa''-aux : ∀ m n -> n + m ≡ m + n -> wa (m + n) ≡ wa (n + m)
wa''-aux m n refl = ?  -- cannot unify n + m with m + n

wa'' : ∀ m n -> wa (m + n) ≡ wa (n + m)
wa'' m n = wa''-aux m n (comm n m)

Second definition:

wa''-aux : ∀ m n w -> w ≡ m + n -> wa (m + n) ≡ wa w
wa''-aux m n .(m + n) refl = ?

wa'' : ∀ m n -> wa (m + n) ≡ wa (n + m)
wa'' m n = wa''-aux m n (n + m) (comm n m)

When checking that refl is a valid case, we must unify the two sides of the equation it is supposed to be a proof of. Remember that refl : {x : ℕ} → x ≡ x, so we must find a single value x that is βη-equal to both the left-hand side and right-hand side.

In the first case, this means unifying n + m with m + n, and in the second case, this means unifying w with m + n. The latter is obviously possible, where we assign w ↦ m + n and note that we have done this with the dot pattern .(m + n) in w's place. The former is not obvious. How should we unify n + m with m + n? n ↦ m would be wrong: note, for example, that 2 + 3 ≡ 3 + 2, but 2 does not unify with 3.

In general, things are made difficult by the fact that Agda can't show that _+_ is injective. This is for the good reason that it isn't (as our example showed). Agda can show that constructors are injective, justified by the fact that Agda has no quotient types or the like. This is why suc m and suc n will unify. Agda does not try to show that any defined functions are injective, though it in principle could (by getting the user to supply a proof, for example).


Why do we still use a Von Neumann Architecture in modern computers?

So why do we still use this architecture in the majority of modern
  computing?

The assumption itself, first clause: Modern Computer <= Von Neumann

Firstly, do note that the Von Neumann architecture is not used exclusively: almost any current "Von Neumann" machine except for very small microcontrollers (which are occasionally Harvard machines) features several important extensions to the original architecture, from DMA to MMUs.

Specialized coprocessors are very popular - most notably, GPUs.

Those work very well in conjunction to a Von Neumann machine.

The assumption itself, second clause:  Von Neumann <= Modern Computers

The limitations of the Von Neumann architecture and the need for non-Von Neumann architectures for certain applications is well recognized in the scientific community, most importantly whenever "[general] artificial intelligence" of interest, see for example this very recent paper, which continues the line of work started by Carver Mead, who envisioned one of the most radical departures from "classical" architectures in 1989, in the form of analog, time-continuous, highly parallel "neuromorphic" chips.

Your premise is thus, in a way, flawed, unless it is implied that you're referring purely to industrial applications (read on for that part).

On the notion of efficiency

Note that Mead himself had envisioned his architecture as complementary to a traditional Von Neumann machine.

Why?

This brings us to another important point: you mention "more efficient architectures", but efficient for which sort of workload?

Sontag and Siegelmann have famously proved that a feed forward neural network is Turing-complete, as is, of course, the Von Neumann architecture, and if we accept Church's thesis (which has never been seriously challenged in quite a while) that this amounts to the ability to compute all computable functions, they're theoretically interchangeable and unsurpassed in their abilities.

However, leaving aside for a moment the issue of practicality, they are not as efficient for the same applications.

I'm guessing that a neuromorphic chip such as Carver Mead's would make for a terrible Excel machine.

So why mostly Von Neumann in industrial applications?

But yes: even if research has branched in other directions and has gotten to the status of prototypes and early industrial devices Von Neumann architectures are still the bread and butter of industrial applications (and a good foundation to extend with coprocessors and specialized optimizations).

It's safe to assume that the reason is practical:

They're universal -- i.e. "good enough" in the broadest possible sense: they are Turing complete and sufficiently close to some theoretical models such as the TM itself or the URM; it is safe to assume that the ubiquity of the Von Neumann machine has influenced developement of theory as well.
They're tolerably easy to reason about and very well understood by engineers and developers
They work very well for existing industrial workloads that drive the demand for hardware R&D; there is 60 years' worth of algorithms and software for Von Neumann machines.

Von Neumann closed under copper cable?

Finally - and only partly tongue-in-cheek: do note that it is very easy to obtain a decidedly non-Von Neumann machine from off-the-shelf parts: just buy two laptops and connect them with an UTP cable and you have a very strange machine where you don't have uniform, synchronized access to a single mutable storage or a single clock.


The analysis of the approximation algorithm (join all min-cuts between a terminal and the contraction of the remaining terminals, excluding the heaviest cut) starts on slide 13. So there's nothing to compute, simply assume that $A^*$ is the optimal solution with cuts $A_i^*$ separating terminal $i$ from the rest of the graph. To see the argument spelled out more explicitly read e.g. chapter 4 of Vazirani's "Approximation Algorithms".


Prove vertices of polygon are endpoints of disjoint line segments

Here is a simple counter example :

You most join the two leftmost vertices to the two middle vertices, and both ways to do that don't work.


RSA Decryption from Simple Public Key Values

If you want to decode a message encoded with RSA, you need to get the private key. The "simplest" method is to find the primes $p,q$ with $n=p\cdot q$.

In your case, $n=18209$ is the product of the primes $131$ and $139$. Now, you can follow the value of Euler's phi function for $n$, which is $\varphi(18209)=130\cdot138=17940$.

The private key $d$ suffices the following equation

$b\cdot d\equiv 1\mod\varphi(n)$.

To get $d$ with this property, you can use the extended euclidean algorithm for $b$ and $\varphi(n)$, which produces $x$ and $y$ with

$1=x\cdot b+y\cdot\varphi(n)$

Now, the value $x$ is your private key $d$. In your case, I get $d=4621$.
To finally decode the message $m$, you have to compute

$m^d\mod n$


Intrinsic matrices in stereo camera calibration

You are correct: during stereo calibration the parameters of both cameras are optimized simultaneously, which is why you get the discrepancy.

When you calibrate a single camera, you are minimizing the reprojection errors  from projecting the checkerboard points into that one camera. When you calibrate a stereo pair of cameras, you are minimizing the reprojeciton errors from projecting the checkerboard points into both cameras. Since you are minimizing different functions, the results will not be the same. However, the difference should be small.


How to be sure of a good solution in hyperparameter optimization

The short answer: You can't.  These are heuristics.  There are no guarantees.  They might fail badly; and there's no reliable way to detect that.


$k$th Largest Algorithm in a range $[k, k+c]$

Step 1. Use QuickSelect to find the $k$th largest number in the array.  Call it $x$.

Step 2. Use QuickSelect to find the $k+c$th largest number in the array.  Call it $y$.

Step 3. Find all elements in the array that are at least $x$ and at most $y$.  This can be done by simply iterating over the array and comparing each element to $x$ and $y$.

Each step can be done in $O(n)$ time.  Therefore, the total running time is $O(n)+O(n)+O(n) = O(n)$ time.


Your confusion is that you're using $\phi$ to denote two different mappings. The first one maps its input $v$ to the vector $\begin{pmatrix} v & \mathbf{1} \end{pmatrix}$, and the second one maps it to $\begin{pmatrix} \mathbf{1} & v \end{pmatrix}$. In the same way we can prove that $-1$ is the square of a real number: $-1 = x \cdot x = (-1) \cdot (+1)$.


What happens when an internet connection is faster than the storage write speed?

Many protocols, including TCP which is most widely used protocol on the Internet, use something called flow control. Flow control simply means that TCP will ensure that a sender is not overwhelming a receiver by sending packets faster than it can empty its buffer. The idea is that a node receiving data will send some kind of feedback to the node sending the data to let it know about its current condition. So, two way feedback allows both machine to optimally use their resources and prevent any problems due to mismatch in their hardware.

https://en.wikipedia.org/wiki/Flow_control_(data)


Conflicting definitions of language accepted by Turing Machine?

The two definitions are in fact equivalent. Both halt and accept when the word belongs to the language. One is more restricted for strings outside of the language: it is not allowed to halt. Every Turing machine in the "classic" definition (which allows halting with "no") can be changed into a non-halting one easily. Just when the old machine wnat to stop in a no-state, its restricted equivalent moves into a no-sate that actually does not stop but instead keeps walking to the right (or the left, what you want). Both versions of the machine will accept the same language.

Thus, both versions define the class of recursively enumerable languages. Or partially decidable or Turing-acceptable, but I prefer the old terminology.

In conclusion, Papademitriou has a slightly non-standard definition, which is nevertheless equivalent to the commonly used one.


How do neural networks create results like its inputs?

These are known as Autoencoders. As you said, these neural networks are trained to produce output that is similar to the input, rather than output a classification of some kind.

Internally, they do not differ much from other neural net designs. Simply, the expected output is the input (or a slight variant of the input), rather than a classification.

One difference however is often the level of depth. Networks designed to replicate sequences, like writing jazz music, need to remember a sequence throughout training and prediction. This is where deep learning succeeds better than other methods.

This paper briefly discusses one type of an auto-encoding network and how it's used to produce music. I think you will find the design is very similar to a traditional neural network.


Two Problems in understanding the algorithm for computing shortest paths in undirected graphs with possibly negative edge weights

An answer to the second problem:

Problem: Each circuit in $S$ must have total weight zero. Why?

Proof: By contradiction.
Suppose that some circuit $C$ in $S$ have nonzero total weight.
Because $G$ has no negative cycles, $C$ has positive total weight.
Note that $C$ does not contain $s$ or $t$. Therefore, the edges of $C$ are all $5$-edge gadgets; see step 2.
Then we can construct another perfert matching on $C$ whose total weight is zero by choosing the middle edge with weight $0$ of each $5$-edge gadgets and the edges between $v$ and $v'$ (for each $v$ in $C$; see step 1) also with weight $0$.
This contradicts the assumption that $M$ is a minimum perfect matching.


Minimum number of cuts to divide a rectangle

Each edge of an inner rectangle that (that isn't on the exterior of the big rectangle) is a line segment.  Your problem now becomes: given a collection of line segments, find the minimum number of lines to cover all of the line segments (and nothing more).

This problem can be solved as follows.  For each line segment, extend the line as far as you can in both directions, until it no longer is touching any line segment.  Add that line to your collection of lines.  Repeat until you've covered all of the line segments.  In other words, merge two line segments if they are touching and go in the same direction (since in that case they can be merged into a single line that covers both).  Repeat until you can't merge anything any longer.


About a universal (functionally complete) function producing a constant

The claim is false if you're allowed to use constants. Take $f(x,y,0,0) = f(x,y,1,1) = 1$ and $f(x,y,0,1) = f(x,y,1,0) = x \text{ NAND } y$. If you're not allowed to use constants, then every function that you can get by composing $f$ with itself will have the property that if all inputs are 1, then so is the output. NAND doesn't have that property.


No, it is not necessarily recursively enumerable.  There are languages that are recursively enumerable but not recursive.  Thus, their complement is not recursively enumerable.  From that, you should be able to prove that the answer to the question in the final sentence of your post is no (I'll let you fill in the details from there).


Optimal clustering with optimal number of clusters as well as max and min cluster size constraints

Answer 1. There are various clustering algorithms depending on different requirements. You can employ $k$-means clustering method since it is fast, simple, and popular.
Answer 2. If you do not know the number of clusters, employ Elbow method. That is, first cluster the data for $k = 1$. Then cluster the data with $k = 2$, then $k = 3$ and so on. Initially, the cost of the clustering will decrease rapidly with increase in $k$. Once the $k$-means cost starts to appear constant with increase in $k$; that value of $k$ is the desired number of clusters.
Answer 3. When there are constraints on the size of clusters, the problem is (informally) known as the balanced clustering problem or capacitated clustering problem. The Wikipedia article does contain a few links of its implementation. This is a research paper for the balanced $k$-means problem. You might have to do some more research on this topic to find the perfect answer as per your requirement.

Note: The clustering problem that minimizes the $k$-means objective is $\mathsf{NP}$-hard. Therefore, you can expect to find an optimal solution to your problem in polynomial time.


Creating a one-to-one mapping between a N-length list and M workers?

Sure.  Give the $i$th worker the range of items at indices from $\lfloor Ni/M \rfloor$ to $\lfloor N(i+1)/M \rfloor - 1$.

Here I assume indices range from $0$ to $N-1$, and workers are indexed by $i$, where $i$ ranges from $0$ to $M-1$.  Also, the notation $\lfloor x \rfloor$ represents the result of rounding $x$ down to the nearest integer.

This ensures that there are no overlaps, and the list is split evenly among the workers (as evenly as possible: each worker receives either $\lfloor N/M \rfloor$ items or $\lfloor N/M \rfloor + 1$ items).


Optimizing coin splitting - Is this algorithm as fast as I think?

You have made significant progress on this problem. Your final conclusion, "the overall algorithm asymptotically requires $\Omega(n^2)$ steps" is likely to be correct as well.

Analysis of Your Argumentation

Here are some unclear or unconventional or inconsistent notations found in your post, which makes it difficult to understand or justify your arguments about time-complexity.

Does "$n|2$" mean $n$ is even? The standard convention for for "$a$ divides $b$" is $a|b$ according to math stackexchange answers and my years of practicing number theory. So $2|n$ is the prefered notation for $n$ is even. Anyway, in current case, I strongly prefer the plain English, $n$ is even.
"use tuples to denote ranges of values. $(i,j)$ specifies the value range $v_i,\cdots,v_j$.". People use $(i,j)$ generally to mean the pair of elements $i$ and $j$ or an open interval with ends $i$ and $j$. I would suggest you use $v_{i..j}$, where the two-dot notation $i..j$ are the convention for an integer interval.
"create a DAG $G = (V, E, \gamma)$". Do you mean an edge-weighted DAG?
"Create a vertex $v$ named $(1,n)$", which does not sound like English. It is better to write "Create a vertex $v$ that represents $1..n$".
"Create or refer to the previously created vertices $v_1,v_2,v_3$, named $(2,n−1),(3,n),(1,n−2)$ respectively". Although I can probably guess your intention, I am puzzled by the notations. Did you not notice that $v_1, v_2, \cdots, v_n$ appears as the coin values in the quoted problem? It looks like you want to use "$(2,n-1)$" as a name, which would be very confusing, since I have never seen any name of a person, a item, a variable or whatever starts and ends with a parenthesis for years except for very few social online accounts.
"Create the edges $e_1=(v,v_1),\gamma(e_1)=v_1$ and $e_2=(v,v_2), \gamma(e_2)=\max\{v_1,v_n\}$ and $e3=(v,v_3),\gamma(e_3)=v_n$". Now I am more into the wanderland. Is the codomain of $\gamma$ the vertices or the indices or the coin values?
"Iterate through the vertices $v_{\lbrace 1,2,3\rbrace}$". It is better to just write $v_1, v_2, v_3$.
"the sequence of coins denoted by the $v$". Didn't you say $v$ is a vertex?

Now Let us check your computation of the time-complexity.

"The number of edges in the created graph is bounded as follows: $|E|\le3|V|$. The number of vertices is denoted by the following sum:  $1 + \sum_{i=0}^{\frac{n}{2}} 2i + 1 \leq n^2$". It looks like your estimates are correct, even though they can be tighter.
"We can determine the maximum score for player 1 by 'backpropagating' the edge weights through the graph, which takes $| V | * | E |$ steps. This makes the overall algorithm asymptotically require $\Theta(n^2)$ steps". Since it is not clear how your backpropagating works exactly, it is hard to justify the number of steps. However, since $| V |* | E | \le |V| * (3 |V|) \le 3 n^4 $, you can only say that your algorithm takes $O(n^4)$ time.

In summary, even assuming that your algorithm is indeed a correct way, there is not enough clear information to fully justify or disprove your time-complexity argumentation. There are quite some room for you to improve the description of your algorithm and the time-complexity argumentation.

A Reference Solution

For simplicity, I will assume $n$ is even. Let $f(i,j)$ be the maximal score reachable by the first player if the two players start the game with the coins sequence $v_i, v_{i+1}, \cdots, v_j$.

Then we have the base cases,
$$f(i, i+1)=\max(v_i, v_{i+1})$$
and recurrence relation
$$ f(i,j) =\max(v_i+\min(f(i+2,j),\ f(i+1,j-1)),\ v_j +
\min(f(i+1,j-1),\ f(i,j-2)))$$

The parameter pair $(i,j)$ of any $f(i,j)$ that appears in the course of computation of $f(1,n)$ will be such that $1\le i\le j\le n$ and $(i-1)+(n-j)$ must be even. The number of all such parameter pairs are $n^2/4$. The base case and the recurrence relation together shows that we need some $O(1)$ operations to obtain $f(i,j)$ for a new parameter pair $(i,j)$, assuming that the usual memorization technique in dynamic programming is used. So the time-complexity of computing $f(1,n)$ is $\Theta(n^2/4)=\Theta(n^2)$.


How to prove Big-O when $F(N)$ is even or odd

you have to do for both expressions. But in this case, one expression is strictly smaller than the other one, so you can do it just for the $3n^2+2$ and say $4n+1<3n^2+2$ and therefore also $4n+1<cn^2$.


Algorithm to determine whether a given graph is a caterpillar tree

When considering such recognition algorithms, it is sometimes helpful to consider equivalent characterizations of the graph in question. Your observations and ideas are valid.

In other words, we can first prove that caterpillars are such trees that when you delete all the leaves and incident edges, you are left with a path graph. This immediately suggest a simple linear time algorithm: check that your input graph is a tree, remove all the leaves, and check that you have a path.

In fact, I suggest you divide your problem into 3 subtasks you can work on independently:

Implement a function that outputs YES/NO based on whether the input graph is a tree.
Implement a function that removes all the leaves and the edges incident to them from the input graph.
Implement a function that outputs YES/NO based on whether the input graph is a path.


Propbably you should read the citation as: "The problem is that the c (which separates the two parts of the language) is at the extreme right and not at the extreme left, where we start parsing."

Therefore it is of no help (unlike the case where you start reading at the right), and therefore there is no LR-grammar for this language. Neither with the c nor without.


The amount of ROM needed to implement a 4-bit multiplier?

As shown in the figure bellow (general architecture of ROM):

to address 8-bit numbers correctly your ROM size should be: $2^8 \times 8$ bits.


What is the reason behind a specific ordering of the rows in the generator matrix for Hamming codes?

If a single-bit error correction is attempted, the ordering presented in the example guarantees that the syndrome vector (the result of the multiplication of the checking matrix and the received data), if interpreted as an integer, will indicate the position of the error. Otherwise, a lookup table would have to be used.


The C3 linearization algorithm for method resolution in multiple inheritance OO languages: Looking for a justification for some implementation detail

Without the last list:

merge(<B,D,O>, <C,F,O>, <D,O>) =
  <B,D,C,F,O>

With the last list:

merge(<B,D,O>, <C,F,O>, <D,O>, <B,C,D>) =
  <B> + merge(<D,O>, <C,F,O>, <D,O>, <C,D>) =
  <B,C> + merge(<D,O>, <F,O>, <D,O>, <D>) =
  <B,C,D,F,O>

Without the last list:

merge(<B,D,C,O>, <C,F,O>, <D,O>) =
  <B,D,C,F,O>

With the last list:

merge(<B,D,C,O>, <C,F,O>, <D,O>, <B,C,D>) =
  <B> + merge(<D,C,O>, <C,F,O>, <D,O>, <C,D>) =
  no-merge

Intuitively, the last list forces the final result to be compatible with the ordering <B1,...,Bn>. That might change the order, or make the merge fail.


Better way to formulate these constraints?

Here is a different way to formulate the situation, which is simpler conceptually and which might be implemented more easily, although the number of variables is still the same (which can be not reduced fundamentally, anyway).

"Once job $i$ is assigned to a machine, it must be assigned using the same processor on that machine". It looks like it is assumed that a processor is attached to the same machine regardless of the job or time. That means there is only one degree of freedom about the variable $j$ and $k$.

Let us use a new index $p=(j,k)$ to denote a pair of machine and a processor on it. Let binary variable $x_i^{pt}$ be $1$ iff job $i$ is assigned to processor $p$ at time $t$ (the index $t$ and $p$ is put together since they represent the resources). Then we can express the constraints as a single inequality,
 $$x_i^{pt}+x_i^{p't'}\leq 1\quad \text{ for all }p\neq p',t,t', i$$

In the actual programming, we can pack $j$ and $k$ side by side to form $p$ as the union structure in C/C++. For example, let $p$ be a 32-bit unsigned integer whose upper 16 bits is $j$ and whose lower 16 bits is $k$. We can also use a hash table with $p$ as keys and $(j,k)$ as values.


Improving time complexity from O(log n/loglog n) to O((log ((nloglog n)/log n))/loglog ((nloglog n)/log n))

Here are the functions.
$$f(n) = \frac{\log(n)}{\log\log(n)}$$
$$h(n)=\frac n{f(n)}=\frac{n\log\log(n)}{\log(n)}$$
$$g(n)=f(h(n))=\frac{\log(\frac{n\log\log(n)}{\log(n)})} {\log\log(\frac{n\log\log(n)}{\log(n)})}$$

  Is $g(n) < f(n)$ in fact true (starting from some $n$)?

Yes, here is a proof.

Let us compute the derivative of $f(x)$ with respect to $x$ as a real variable.

$$\frac{df}{dx}
=\frac{\frac{\log\log x}{x}-\frac{\log x}{x\log x}}{(\log\log x)^2}
=\frac{\log\log x-1}{x\ (\log\log x)^2}$$

So $\frac{df}{dx}\gt0$ when $e^e <x$. That means, $f(x)$ is strictly increasing once $e^e\lt x$.

If $n$ is large enough, $e^e\lt h(n) \lt n$, which implies $f(h(n)) < f(n)$, i.e., $g(n) < f(n)$.

If we want to be specific, we can show that $e^e\lt h(n) \lt n$ when $n > e^{e+2}$.

  Is $g(n)$ asymptotically better the $f(n)$, i.e. is $g(n) = o(f(n))$?

No, $g(n) = \Theta(f(n))$. In fact, $\displaystyle\lim_{n\to\infty}\frac{g(n)}{f(n)}=1$

  Assuming this is asymptotically better, I can do ...

Well, that assumption is invalid.

Here are two exercises.

Exercise 1. Show that $\displaystyle\lim_{n\to\infty}\frac{g(n)}{f(n)}=1$ using the following hint or steps.

Recall that $\log(n) < n^\epsilon$ for any constant $\epsilon>0$ when $n$ is large enough.
Show that $\displaystyle\lim_{n\to\infty}\frac{\log(\frac{n\log\log(n)}{\log(n)})}{\log(n)}=1$.
Show that $\displaystyle\lim_{n\to\infty}\frac{\log\log(\frac{n\log\log(n)}{\log(n)})}{\log\log(n)}=1$.

Exercise 2. Show that $g(n)−f(n)=O(1)$. (This exercise might be hard.)


Name of BFS variant with multiple queues with different priorities

I don't think this particular implementation has a name, but there is a slightly different implementation that achieve the same goal and has a name: BFS 0-1.

Let me briefly describe the algorithm, and then let's solve your problem using this algorithm. For more complete description use previous link or Google about, it has a name.

Suppose you have a general graph (a tree will also work) where each edge has a weight, but the weight can only be 0 or 1. You are given a source node and should find minimal distance to every other node in the graph. This can be easily solved with Dijkstra's algorithm but complexity worsens. Instead of using Dijkstra, let's use BFS, with a deque (in the place of the queue). When we are traversing an edge with weight 0 we add this node to the beginning of the deque, otherwise you add it at the end.

Without going too much into the details of BFS 0-1 I'll apply it to your problem. Suppose that every time you are visiting an unvisited parent you add it to the end of the deque, and when you are visiting an unvisited child you add it to the front of the deque. The order in which you will visit the nodes in your file system will be the one desired. Notice now, that we are treating edges going to a parent as if they have weight 1, and edges going to children as if they have edge 0 (graph is obviously directed, since each edge has different weight when direction changes). The distance to each node from the source will be the distance to the closest common ancestor in the initial tree.

This is not exactly the same algorithm you were proposing, but notice that using the idea of two queues, is the same as having the deque and inserting from the beginning or from the end, so we can say both algorithms are basically equivalent. It can be naturally extended following your idea to support graphs were edges has weight such that they are numbers between $0$ and $k - 1$, using $k$ queues, however it is more tricky and out of the scope of this question.


Is it possible to come up with a graph instance that would force Dijkstra to perform a decrease key on every single edge?

Yes!

A bit convoluted example is the following:

Suppose you have $n+1$ nodes and you run djikstra from $a_{0}$
Let $A=[a_{0},a_{1},a_{2}.....,a_{n}]$ the final result of the algorithm(i.e the nodes of the graph sorted by their distance from $a_{0}$)

We will now create a graph which will require every edge to be updated:

First of all add edge $e_{i}=(a_{i} , a_{i+1})  $   with $cost(e_{i})=0$ for every $i<n$

Let $M$ be a really Big Value.

For every $i<n$ and $j>i+1$ add the edge $e_{ij}=(a_{i},a_{j})$ with $cost(e_{ij})=M-i$

At every step $i$ of the algorithm ALL values of the nodes will be updated.

ex.  $M=100,  n+1=5$

Distance matrix for $A$

step 0: [-,0,100,100,100,100]

step 1: [-,-,0 , 99, 99 ,99]
and so on....


Is there a naming convention for the left child of a right child (and vice versa)?

You can use 'sibling' (or 'brother'/'sister' if you prefer to gender the vertices). It's somewhat commonly used, but you may want to redefine it quickly when using it extensively.

NB: this terminology can be used for non-binary tree, the sibling of a vertex is any other vertex with the same parent/father.

While you may want to find a more reliable source, Wikipedia agrees with me at the moment: https://en.m.wikipedia.org/wiki/Tree_structure


Why is $FOLLOW$ not necessary for $LL(1)$ grammars with no $\epsilon$ transitions?

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

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


Solving Recurrence Equations containing two Recursion Calls

Yes, recursion trees do still work!  It doesn't matter at all whether the base case occurs at $T(0)$ or $T(1)$ or $T(2)$ or even $T(10^{100})$.  It also doesn't matter what the actual value of the base case is; whatever that value is, it's a constant.

Seen through big-Theta glasses, the recurrence is $T(n) = 2T(n/2)+T(n/3)+n^2$.

The root of the recursion tree has value $n^2$.
The root has three children, with values $(n/2)^2$, $(n/2)^2$, and $(n/3)^2$.  Thus, the total value of all children is $(11/18) n^2$.
Sanity check:  The root has nine grandchildren: four with value $(n/4)^2$, four with value $(n/6)^2$, and one with value $(n/9)^2$.  The sum of those values is $(11/18)^2 n^2$.
An easy induction proof implies that for any integer $\ell\ge 0$, the $3^\ell$ nodes at level $\ell$ have total value $(11/18)^\ell n^2$.
The level sums form a descending geometric series, so only the largest term $\ell=0$ matters.
We conclude that $T(n) = \Theta(n^2)$.


Why larger input sizes imply harder instances?

Is it the case that time complexity is always an increasing function
  in the input size? If so, why is it the case?

No.  Consider a Turing machine that halts after $n$ steps when the input size $n$ is even, and halts after $n^2$ steps when $n$ is odd.

If you mean the complexity of a problem, the answer is still no.  The complexity of primality testing is much smaller for even numbers than for odd numbers.


Trouble understanding how to create a grammar parse tree

Before expanding a grammar into a parse tree, we should first try to understand it at a higher level.

<list> -> <item> , <list> | <item>
<item> -> <left> <item> <right> | <left> <right>
<left> -> A| B | C
<right> -> x | y | z

First, <list> is a list of <item>, separated by commas if there are multiple ones.

Second, an item is either a pair of alphabets (the left is one of A | B | C; the right is one of x | y | z) or recursively, an item surrounded by such a pair.
Thus, an <item> is a word composed of, say $n$, upper-case alphabets from A | B | C, followed by the same number, $n$, of lower-case alphabets from x | y | z.

  $Q_1$: Choose a string that is in this language and create a parse tree that demonstrates that your claim is true.

ABCxyz,ACyz is in this language; can you generate a parse tree for it?

  $Q_2$: Identify another string that contains some of these terminals symbols but is not in the language.

AyCz is not in this language; can you explain why?

In addition, when you are searching for any string in a grammar by expanding the grammar into a parse tree, you can push the tree into its leaves as fast as you can, by choosing the non-recursive rules whenever possible.


Is there any rich problems that can be solved using several algorithm techniques?

I suggest the longest increasing subsequence problem: Given an input sequence of length $n$, find the length of the longest increasing subsequence in the input sequence.
A naive dynamic programming-based formulation will lead to an $O(n^2)$ running time. The Wikipedia link provided above uses a binary search-based formulation to speed it up to $O(n \log n)$-time. Fredman '75 suggested in his paper another approach based on dynamic programming that obtains the same $O(n \log n)$ time bound, and established a lower bound in terms of the number of comparisons, proving his algorithm is the best possible.
But this is not the end of story, yet. There are various other algorithms that solve LIS. Using advanced data structures, Crochemore and Porat gives a priority queue-based algorithm for solving LIS in $O(n \log \log k)$-time on a word RAM. Yet other techniques exist, such as reduction to range maximum queries and then solving the problem via tournament trees 1, and using van Emde Boas trees. Finally, there is also a divide and conquer-based algorithm that solves LIS by Alam and Rahman, running in the same $O(n \log n)$ time bound.
The LIS problem also has connections in mathematics, it is related to a combinatorial structure called the Young tableaux (https://en.wikipedia.org/wiki/Young_tableau; in particular; the maintenance of the principle row of the Young tableaux is essentially solving for longest increasing subsequence) and the Robertson-Schensted correspondence.
Plenty of other problems in string pattern matching also have produced a rich body of results; I'm sure you'll find an abundance of other problems that are close in richness to longest increasing subsequence.


If the computer starts in the middle of the stream, it has no way to know—it will be completely confused.

Fortunately, that's not how the protocol works. The computer and terminal have to sync up before they can communicate. There are a few different ways of doing that, but once they're in sync (which includes agreeing on how long each 1 or 0 should last), they both follow a set pattern.

In this example:

The terminal starts out holding the line high (sending constant 1s) to indicate that it has nothing to say.
When the terminal has something to say, it brings the line low for a moment (sending a 0). That's the "start" bit.
The terminal then sends seven bits for the character: always exactly seven, since it's using ASCII, which is a seven-bit encoding.
After those seven bits, it sends one additional bit for error checking. This is a 1 if there were an odd number of 1s in the character, and a 0 otherwise. This is the "parity" bit.
Finally, it pulls the line high again to indicate that it once more has nothing to say.

The computer keeps track of which "mode" the connection is in at all times. If it sees a zero, it might record it as part of the data, or might switch from "idle" mode to "start listening for data" mode, or check the parity: it all depends on what it's seen before.


Z Notation: sequence of sequences - find sum

I am not aware of the Z notation but here's what you have to do:
step 1: initialize a variable total to 0
step 2: loop through all queues
step 3: add the length of every queue to total


Prove that the language { uw : |u| =2 |w| } is regular

Any string of the form $uw$ where $|u| = 2|w|$ is a string whose length is a multiple of $3$. We are therefore considering the language of strings over some alphabet $\Sigma = \{ a_1, \ldots, a_k \}$ (not specified in the question). whose length is a multiple of $3$. Let $\Sigma$ be the regular expression $a_1 + \cdots + a_k$. Then a regular expression descring the language in question is

$$(\Sigma\Sigma\Sigma)^*$$


Heap sort best case time - $\mathcal O(n)$?

Big O is for measuring the worst case time complexity, and in this case it is $O(n)$. The best case is written as $\Omega$.  Here is a paper describing the reasoning for the best case. We generally do not consider the case of having only identical elements in the list.


The EDVAC employed a 44 bit word with a 4 bit op code and 4 10 bit address fields.

While the use of the fields varied a lot, the ADD instruction was typical. The memory location in field 1 was added to the memory location in field 2 and the result placed into the memory location in field 3. Execution of code then continued at the location addressed by field 4.

Thus we can summarize C = A + B; GOTO D

As for simulation with pseudo codes, we can deduce that for the Accumulator + One address machines popular at the time, the C = A + B would be simulated with three instructions and the GOTO part would be omitted. Thus three-plus-zero. It might look something like (stylized not actual code):

; ADD A,B,C
LD Acc, A
ADD Acc, B
ST Acc, C

For more on EDVAC please see:

https://babel.hathitrust.org/cgi/pt?id=mdp.39015002095639;view=1up;seq=87


Why is the name half-adder used to represent the half-adder?

With a full adder, you can get all outputs from (0,0) to (1,1). With a half adder, you can never get (1,1), which makes it, in a way, incomplete.

Also, in practice a full adder is used more than a bare half adder. For example, addition of binary numbers (one of the most common operations needed by a microprocessor) is done by chaining full adders:

(4-bit adder, taken from Wikipedia)

In the end, since full adders are the ones used for adding, we call them "full" adders.

And since a full adder can be made by joining up two half adders with an OR gate, the half adder becomes "half" an adder.


Bisimilarity and Trace Equivalence in Labelled Transition Systems

The answer is that the LTS on the left isn't deterministic, as the label (or action) open_door doesn't go to a single state and hence that action is non-deterministic.

This example shows that determinism is indeed required for trace equivalence and bisimilarity to be equivalent.


How does a computer distinguish two separate transmissions on a wire

On a wire you encode bits by changing the voltage, for example +5V could mean 1 and -5V could mean 0. If you do this naively you get problems with long sequences of 1's or 0's. For example you mentioned clock drift, i.e. when do I know that one 1 ended and the next 1 starts? But it's also problematic to have one voltage for a long time, because charge could build up at one end that needs to be dissipated somewhere.

So instead of using a naive encoding, we use a trick. For each bit we use two clock cycles, and encode the bit as the change in voltage. This way we implicitely also transmit our clock down the wire, the receiver can synchronise their clock using the same edge detection algorithm that they use to read the bits. This scheme is called Manchester code.

If you use more voltage levels to encode multiple bits at a time, the same basic idea can be applied. Instead of encoding the bits naively, we ensure that there is enough change in the data so that we can keep the clocks synchronised and the voltage on average 0. Check the related articles in the Wikipedia, for example 8b/10b encoding.


How undecidable is it whether a given Turing machine runs in polynomial time?

The answer is $\bf 0''$ (and so in particular computation in the limit - which corresponds to $\le_T\bf 0'$ - is not enough). And this stronger result is also folklore (I was assigned it as an exercise way back when).

As an upper bound we just check quantifier complexity: $\Phi_e$ runs in polynomial time iff there exists some polynomial $p$ such that for every input $n$ we have $\Phi_e(n)[p(\vert n\vert)]\downarrow$ (that final clause only uses bounded quantifiers). So running in polynomial time is a $\Sigma^0_2$ property.

Now we just need to show optimality. We'll actually show a bit more: not just that the Turing degree is $\bf 0''$, but that the set is $\Sigma^0_2$-complete. Supposing $$A=\{x:\exists y\forall z\theta(x,y,z)\}$$ (with $\theta\in\Delta^0_0$) is any other $\Sigma^0_2$ set, we want to reduce $A$ to the set of programs running in polynomial time.

So fix an instance $i$. We'll say $m$ is $s$-bad for $i$ if $m<s$ and there is some $n<s$ such that $\neg\theta(i,m,n)$. Let $t_i(s)$ be the least $m$ which is not $s$-bad for $i$. Now we'll whip up a stupid program $\Phi_{e_i}$ as follows: on input $s$, $\Phi_{e_i}(s)$ runs for ${\vert s\vert}^{t_i(s)}$-many steps and then halts and outputs $0$. The point is that if $i\in A$ then $t_i(s)$ stabilizes and so $\Phi_{e_i}$ runs in polynomial time, and otherwise $\Phi_{e_i}$ does not run in polynomial time.

Now the map $\mu: i\mapsto e_i$ is computable, so we get a many-one reduction of $A$ to our set.

As a quick comment, note that we only used one property of polynomial time above: that there is no biggest polynomial time bound. This let us keep pushing up the runtime bit by bit (each time $t_i(s)$ goes up) while preserving the possibility of still running in polynomial time. By contrast, "halts within seven steps on all inputs" (say) is merely $\Pi^0_1$-complete. Basically, whenever we have a concrete resource-bounded complexity class with no "maximal bound," being in that class will be $\Sigma^0_2$-complete. In particular, this applies to NP, EXPTIME, PSPACE, ...


Formally describing a sensor network language

Backus-Naur form used to be popular for these purposes. Another possibility is Wirth syntax notation. You can find other possibilities in the "see also" section of the article on Backus-Naur form.


The round trip time is the time required to go and return, so it must be measured from the start of the transmission to the start of the reception of the response. If you measure from the end of the packet to the end of the ACK, you are subtracting the package length and adding in the length of the acknowledgement's package (the ACK could be piggibacked on any package doing the back trip). This can very well be measured during a stream of data (and it is done so by your neighborhood TCP stack to tune timeouts and so on).


Analyzing space complexity of passing data to function by reference

All the computations of complexity depend on your model of computation, in other words on what you would like to count.
You may, as you say, only count memory that your code itself allocates. You should be aware that this way of counting space used can become useless easily. You can modify any algorithm to delegate all allocation to the caller. It is not very informative to say that you can solve any problem in constant space.
Another possibility is to count all memory space that gets accessed. If an algorithm accesses all the memory to store the input, do we count it? Some people do.
A more common way to define memory complexity is to measure the memory that the program modifies. Whether the program allocates it or the caller does, it doesn't matter in this case.
Relevant to the computation is also the units in which the memory is measured. You could count bits. This assumption leads to the claim that storing an integer $n$ will require $O(\log(n))$ of space. But this is not the only model used. You could assume that your model of a computer stores integers. In this model storing an integer requires just one unit of space. This is common when the size of the integers involved at not going to be large compared to other sizes of the inputs. These assumptions are relevant to the discussion in the comments. You both are right, but are using different units to quantify memory. These are not even the only options. Some models assume that a unit of memory can store an infinite precision real number, for example.
There are other aspects that sometimes are also taken into account. For example, in real world computers not all memory is the same. In some models memory is separated in a hierarchy. For example, according to response time. Registers and cache are faster than hard drive or magnetic tape. The space complexity can take into account how much of the different  types of memory is used.
It is very common to just mention an $O$ class to which the amount of space used, as a function of some size of the input, belongs. To not be wrong it is better to clarify what is being counted and in what units.


Does it matter for this function if the set we check membership of is finite?

You can solve this problem in a straight-forward way: give an algorithm that (semi-)computes $H_1$.

Here is a rough sketch that you have to expand into appropriate detail in the model you want to work with and then show correctness and computability.

Let $M_B$ be a semi-decider for $B$.

Compute $\Phi(x,x)$ and $M_B(x)$ simultaneously.
If $\Phi(x,x)$ terminates first, return $1$.
If $M_B(x)$ terminates first (and accepts), return $0$.
Otherwise, loop.

Hints

   In step 1, use dovetailing.

   Steps 2 and 3 can not disagree.

   Step 4 only happens when it should.

You can show the necessary lemmas using the assumptions on $B$.

As you see, we don't care at all if $B$ is finite as we do not care what $M_B$ looks like; we just use it as a black box.

Aside: I am not sure that infinite $B$ with all the properties as listed in the question exist. We can ignore this, though: the problems is stated such that we show something for each such $B$ -- if there is none, we are good.


Why isn't there a .= operator? (or ->= etc)

IMO, the biggest reason is that identifiers are not first class values in programming languages and "." is not a real operator like + or - are. For example, you can't convert

var foo = variable.bar()

into

var name = bar
var foo = variable.name()

The same way you can convert

var foo = 1 + 10

into

var x = 10
var foo = 1 + x

In more technical terms, in most languages x + y is an expression, while x, x.y and x[i] are identifiers.

Summing up, when using your hypothetical .=, the right hand side needs to be interpreted as a field name, not an expression. This leads to unintuitive results - the following two lines look very similar but do wildly different things.

x += bar() // calls the bar() global function and add its value to x
y .= bar() // calls y's bar() method, and sets `y` to its result.

Additionally, as Guy Coder pointed out, when using +, -, etc its guaranteed that the type of the resulting expression is the same as the arguments so += always makes sense. On the other hand, we can have y.bar() return a type different from y, in which case .= bar() would make no sense.


How to perform AND on binary "recursive repeating sequences"?

Let $A,B$ be the two recursive repeating sequences, where $|A| = |B|$. If $|A| = |B| = 1$ then there is nothing to do. Otherwise, either $A$ is of the form $A_1A_2$ or of the form $(A')_k$, where $k > 1$. In the second case, we can write $A = A' (A')_{k-1}$, which is also of the form $A_1A_2$. Thus it suffices to explain how to compute $A_1 A_2 \land B$ (here $\land$ means AND). We will show that we can find two recursive repeating sequences $B_1B_2$ such that $B=B_1B_2$ and $|A_1|=|B_1|$, $|A_2|=|B_2|$. We can then compute $A \land B = (A_1 \land B_1) (A_2 \land B_2)$.
Given a recursive repeating sequence $B$ and a number $\ell$, we have to break $B$ into $B_1B_2$, where $|B_1| = \ell$. We consider two cases:

$B = C_1 C_2 \dots C_r$. We can find $t$ such that $|C_1 C_2 \dots C_t| \leq \ell < |C_1 C_2 \dots C_t| + |C_{t+1}|$. If $|C_1 C_2 \dots C_t| = \ell$ then we can take $B_1 = C_1 C_2 \dots C_t$ and $B_2 = C_{t+1} \dots C_r$. Otherwise, we break $C_{t+1}$ into two parts $D_1D_2$, where $|D_1| = \ell - |C_1 C_2 \dots C_t|$, and take $B_1 = C_1 C_2 \dots C_t D_1$ and $B_2 = D_2 C_{t+2} \dots C_r$.

$B = (C)_r$. We treat this as an explicit description of the preceding case, where $C_1 = \cdots = C_r = C$. We use division with remainder to find $t$ efficiently. In the easy case we take $B_1 = (C)_t$ and $B_2 = (C)_{r-t}$, and in the complicated case we take $B_1 = (C)_t D_1$ and $B_2 = D_2 (C)_{r-t-1}$.


Proof for optimal interval scheduling using a Greedy Approach

Let's consider two jobs in the sequence you obtained:

$A$, of weight $w_A$ begins at $t_0$ and finish at $t_0 + s_A$
$B$ coming just after $A$, of weight $w_B$ begins at $t_0 + s_A$ and finish at $t_0 + s_A + s_B$

If we compute only $K_{A, B}$ the contribution of $A$ and $B$ in $K = \sum_j w_j C_j$:

$K_{A, B} = w_A (t_0 + s_A) + w_B (t_0 + s_A + s_B)$

If A and B are inversed in the sequence, we have $K'_{A, B}$:

$K'_{A, B} = w_A (t_0 + s_A + s_B) + w_B (t_0 + s_B)$

The difference is:

$\Delta K_{A, B} = K'_{A, B} - K_{A, B}$

$= w_A s_B - w_B s_A$

$= (w_A/s_A - w_B/s_B) \times (s_A s_B)$

The switch should be done if and only if $\Delta K_{A, B}$ is negative in order to minimize $K$. Only the approach 3 provides you a sequence where no more switch is worth.

If two jobs have the same $w/s$ ratio, just take them in any order, the final $K$ would remain unchanged.


What are the guidelines/tips for calculating the complexity of a chained-recursive function?

I cant think of one simply way to solve such questions, but I can show you a way to start tackling the questions and making them simpler.
In such cases, that $f$ recursively calls itself with their own return value, the running time of $f$ might depend heavily on its output. So contrary to usual complexity computation tricks, here we want to know precisely what the output of $f$ is. For example, we can prove by induction that f1 will always output 1.
Now, replace each inner recursive call to $f$ with the value it returns. In the f1 case, we replace f1(f1(n/2) + f1(n/3) - f1(n/5)) by f1(1+1-1) which is simplified to f1(1). This means that we did a total of 4 calls to $f$, and for each call to $f$ we know exactly what the input was. Here, in this example, the inputs are $n/2,n/3,n/5,1$.
Finally, we can start calculating the time complexity: since we know how many recursive calls happened and what input was there for each recursive call, we can build a recursive formula for the time complexity. In the case of f1, it will be: $T(n)=T(n/2)+T(n/3)+T(n/5)+T(1)+c$, since we add a recursive call with the input of f1 for each time f1 was invoked.
This can be solved using traditional techniques, such as the master theorem.


Are grammars corresponding to DFAs unambiguous and those to NFAs ambiguous?

Let us consider the following construction of a regular grammar from an NFA. We will have a non-terminal $S_q$ for each state $q$. The starting symbol is $S_{q_0}$. If there is a transition from $q$ to $q'$ upon reading $\sigma$ (possibly $\sigma = \epsilon$), then we add the transition $S_q \to \sigma S_{q'}$. If $q$ is an accepting state, we add the transition $S_q \to \epsilon$. Whether the result is a regular grammar or not depends on your definition of a regular grammar (and on whether you allow $\epsilon$ transitions), but let's ignore this aspect.

You can check that this grammar is unambiguous if and only if, each word $w$ accepted by the NFA has a unique accepting path in the NFA, where an accepting path is something that looks this way:
$$
q_0 \xrightarrow{\sigma_0} q_1 \xrightarrow{\epsilon} q_2 \to \cdots \to q_f,
$$
where $q_f$ is an accepting state, and the symbols on top of the arrows spell $w$. Such an NFA is known as a UFA (U stands for Unique).

Every DFA is a UFA since every word has a unique path through the DFA (or, depending on your exact definition, at most one path). Some NFAs are UFAs, others are not.


Constructing PDA to accept language $L=\{a^i b^j c^k \mid k\geq \min(i,j)\}$

Your idea to differentiate between $i<j$ and $i >j$ is good.
To help you building the PDA, note that $L = \{a^ib^jc^k | k \geq i\} \cup \{a^ib^jc^k|k\geq j\}$.
I hope that hint is enough.