CISC and RISC - synchronous and asynchronous

I think that all the instructions in a RISC take the same time what
  makes me believe RISC is associated with synchronous.

It's not true that all instructions in a RISC CPU take the same time. Even in the classic RISC pipeline, the pipeline will stall in some circumstances. Pipeline interlocks and control hazards are the ones that Hennessy and Patterson go into some detail about, but they also mentioned data cache misses.

Even if you ignore those complications, it's unrealistic to design a general-purpose CPU where every instruction takes the same time these days. Programmers want floating point, and SIMD operations, and so on.

  Can you tell me if RISC is associated with asynchronous and CISC is
  associated with synchronous?

On, that's easy: They're not.

Truly asynchronous CPUs are rare, for a few reasons. One of them is that you can't (currently) prototype asynchronous logic on a FPGA, and it's much harder to express in Verilog or VHDL than synchronous logic.

Having said that, it is easier to implement a RISC pipeline in asynchronous logic than a CISC pipeline (e.g. Sproull's Counterflow Pipeline). However, event his is a bit misleading because the boundary between RISC and CISC is quite fuzzy these days. Most modern CISC CPUs use RISC cores internally, and dynamically translate the CISC instruction stream into RISC code. The main reason for this is that the same features which make RISC attractive (e.g. fixed-size instructions which can be buffered) are also the ones which make superscalar execution work.

So to the extent that asynchronous logic works, modern CISC CPUs can benefit almost as much as RISC CPUs can.


Correctness proof: 2-approximation of greedy matching-algorithm

Let $M$ be a maximal matching in the graph $G$. Let $M'$ be the matching returned by our approximation algorithm (obviously this algorithm returns a valid matching).

For all $e\in M'$ let $M_e\subseteq M$ be the set of edges in $M$ who have common vertices with $e$, meaning all $e_M\in M$ such that $e_M\cap e\neq\emptyset$. Obviously $\forall e\in M': |M_e|\le 2$, since at the worst, $e=(u,v)$ and both $u,v$ are matched to some other vertex in $M$.

Note that $M=\bigcup\limits_{e\in M'}M_e$. To see why, suppose for the purpose of contradiction that there exists $e\in M$ with no common vertices with any $e'\in M'$. This means that our algorithm could have added $e$ to $M'$, contradiction. So we have:

$|M|\le\sum\limits_{e\in M'}|M_e|\le 2|M'|$.


The language $L$ is not decidable, this is an immediate consequence of Rice's theorem (you can instead try and prove that $L$ is not decidable directly using reductions). To begin with, there are two machines $M_1$ and $M_2$ such that $L(M_1)\in coRE$ and $L(M_2)\notin coRE$. For example, $M_1$ can be a machine that accepts all inputs, and $M_2$ can be a machine that recognizes the language $Halt_{TM} = \{\langle M, w\rangle: \text{ $M$ halts on $w$ }  \}$ which is known to be in $RE\setminus coRE$. So the property $P = \{ M: \text{$M$ is a TM, and $L(M)\in coRE$}\}$ is a non-trivial property. Also, for every two machines $M_1$ and $M_2$ with $L(M_1) = L(M_2)$, it holds that $L(M_1)\in coRE$ iff $L(M_2)\in coRE$. Thus, either both $M_1$ and $M_2$ are in $P$, or both are not in $P$. Hence, the property $P$ is also semantic, and so by Rice's theorem $L$ is not decidable.
Maybe you saw the claim suggesting that $L' = \{ \langle M\rangle:  \text{ $M$ is a TM, and $L(M) \in RE$}  \}$ is decidable, and this follows simply from the fact that $L'$ is the language of all legal encodings of TMs.


Yes, it is.

This scanned chapter 3 from Garey-Johnson classic book describe a parsimonious reduction from 3SAT to 3DM. And X3C is a generalization of 3DM. So, the same reduction can be used to parsimoniously reduce 3SAT to 3DM.

Thus, $\mathrm{UNIQUE-3SAT}$ many-one reduces to $\mathrm{UNIQUE-X3C}$. As a consequence, $\mathrm{UNIQUE-X3C}$ is $\mathrm{US}$-complete.


How to reduce MAX-2SAT problem to finding a cut in a graph

Idea: Have two vertices $x,\bar{x}$ for each variable, and connect them with an edge with some large weight which will force any maximal cut to put them in different parts of the cut. The idea is that for any two variables $x,y$, $x$ and $y$ get the same truth value iff the vertices $x,y$ are in the same part of the cut. This way you encode a truth assignment.

For each clause $x \lor y$, we would like to do something of the following sort: add a vertex $\varphi_{x \lor y}$ and connect it to both $x$ and $y$. In order to guarantee that $\varphi_{x \lor y}$ is in some specific part of the cut, add a new vertex and connect it to all "clause" vertices with an edge having some large weight. This idea doesn't quite work since the value of the cut depends on how many literals satisfy the clause. Find a way to fix it.


Is this an LL(1) grammar? How to solve First - Follow conflict?

Your factoring is wrong. It should be (written as regular espressions):

$\begin{align*}
  R
    &\to (L \mid \operatorname{num}) (+ R)^*
\end{align*}$

Thus the grammar with left recursion fixed is:

$\begin{align*}
   S  &\to L = R \\
   L  &\to * L \mid \operatorname{id} \\
   R  &\to L R' \mid \operatorname{num} R' \\
   R' &\to + R R' \mid \varepsilon
\end{align*}$

You can check that this doesn't have conflicts.


How to prove the equivalence of two CFG for balanced parentheses?

But I can't prove the reverse i.e. $(1)\subseteq (2)$.

Indeed, that direction of inclusion is somewhat harder to prove.

Let us prove all following 3 context-free grammars are equivalent

$G_1$: $S \rightarrow  SS \mid (S) \mid \epsilon$
$G_2$: $S \rightarrow S(S)S \mid \epsilon$
$G_3$: $S \rightarrow  (S)S \mid \epsilon$

Proof.

$L(G_1)\supseteq L(G_2)$:
$S\Rightarrow_{G_1}SS\Rightarrow_{G_1}SSS\Rightarrow_{G_1}S(S)S\,.$
$L(G_2)\supseteq L(G_3)$:
$S\Rightarrow_{G_2}S(S)S\Rightarrow_{G_2}(S)S\,.$
$L(G_3)\supseteq L(G_1)$:

Let $B$ be the language of balanced parentheses, i.e.,
$$\{x\in\{(,)\}^*\}:|x||_(= ||x||_) \text { and, }\text{if } f\text{ is a prefix of } x,\,|f||_(\ge ||f||_)\}\,.$$ It is immediate to see that $L(G_1)\subseteq B$ by structural induction.

Let $P(n)$ be the proposition that all words in $B$ not longer than $2n$ are in $L(G_3)$.

$P(0)$ is true since the only word not longer than 0 is $\epsilon$.
Assume $P(k)$ is true. Let $w\in B$ with length $2(k+1)$. $w$ must start with left parenthesis, "(". If we count the number of "("s and the number of ")" in $w$ starting from the beginning "(", there will be a time the number of ")"s catches up with the number of "("s. Consider the first time that happens, which must at a ")" in $w$. So $$w=(w_1)w_2$$ for some $w_1,w_2\in B$. By IH, $S\leadsto_{G_3}w_1$ and $S\leadsto_{G_3}w_2$. Hence
$$S\Rightarrow_{G_3}(S)S\leadsto_{G_3}(w_1)w_2=w$$
which shows $P(k+1)$ is true, completing mathematical induction.

All $P(n)$ tell that $L(G_3)\supseteq B$.

Exercise.  Let $G_4$ be the grammar $S \rightarrow  S(S)\mid \epsilon$. Show that $G_4$ also generates the language of balanced parentheses.


How to reduce halting problem to the problem of whether a Turing Machine accepts infinitely many inputs?

If it is decidable, let $M$ decide it.

Construct a decider $D$ that works on input $\langle w_1,w_2\rangle$ as follows:

Construct $M_w$ (as well as its encoding $w$) that works on input $x$ as follows:

Run $M_{w_1}$ on $w_2$.
Accept.

Run $M$ on $w$.
If $M$ accepts, accept; otherwise, reject.

We can see $D$ accepts if and only if $M$ accepts $w$, i.e. $M_w$ accepts infinitely many inputs, which means $M_{w_1}$ halts on $w_2$. Therefore $D$ is a decider for the halting problem, a  contradiction.

Hence the language given in OP is undecidable.


First of all, anything in $P$ is also in $NP$, so proving that it's not in $NP$ will be an exercise in futility. I'm also going to change your variable names a bit to make them clearer; the letters I use stand for base, exponent, and modulus.

What you seem to be looking for is a modular exponentiation algorithm. In other words, a way to compute $b^e \mod m$ in polynomial time. Several of these exist, but here's the simplest one I know of:

function modular_exponent(b, e, m):
    z ← 1
    b ← b % m
    for i ← 1..e:
        z ← (b × z) % m
    return z

The number of multiplications and modulus operations we do is linear in $e$, and the operands to those operations are never larger than $m$. So the runtime is $O(e (\log{m})^2)$ (assuming multiplication runs in log-squared and modulus runs in logarithmic time; in practice you can make this even a bit more efficient using something like Karatsuba multiplication, but that doesn't matter for this problem).

This is clearly a polynomial runtime, so the modular exponentiation decision problem ("for given $b, e, m, z$, is $b^e\cong{}z \mod m$?") is in $P$.


Describe a TM through denotation of the transition function

You are making way too many guesses, and seem to be confused on the difference between words (elements of $\Sigma^*$, or $\Gamma^*$) and letters (elements of $\Sigma$ or $\Gamma$). This is basic stuff and need to be understood before even pretending to think about transition functions.

Indeed, the Turing machine gets a string on its input tape (with letters from $\Sigma$) flanked by $\Box$'s. To be precise $w$ is not an element of the tape alphabet, but a string over the input alphabet $\Sigma$. The tape alphabet equals $\Gamma = \{ 0,1,\#,\Box \}$ plus all the additional symbols that you need for the task you have to perform.

The task is: check whether the input is in fact a string of the form $w\#w$, i.e., two copies of the same string separated with $\#$. The Turing machine may write on the tape and use a little bit of memory, but cannot read stings $w$ in one go (which is what your question suggests). It makes steps on single letters like $(p,0,p_0,\bar 0,R)$: "in state $p$ I read letter $0$, switch to state $p_0$ [to remember $0$] write $\bar 0$ on the tape [replacing $0$ to indicate I have seen it] and move to the position on the right". (Now you have to add $\bar 0$ to $\Gamma$.)

So check your lecture notes on the technical details again, and start thinking how to do the comparison letter-by-letter. It is not that hard: just pretend you are the machine and analyse your steps on a simple example input.


Your answers seem correct.
As for 2: one way is to simply check, a quicker way is to observe that all states go to A upon reading 1, so the sequence 001 ends in A, and A satisfies "red".

3 can be solved by the test "blue" (without any moves) and 4 can be solved with the test "red".

As for 5: in order to show that no test can differentiate B and D, observe that for the letter 1, both go to A, for the letter 0 both go to C, and both have the same light (blue). Thus, you can say that the "language" of both state is equal.


Merge-by-weight to solve reachability problems in trees and DAGs

There are two (equivalent) ways to fix the argument:

Start by not eliminating duplicates. Then the argument works. Then argue that removing duplicates can only decrease the running time.
Count elements with multiplicity, that is, consider each set $S(x)$ as a multiset.

Both of these arguments require a slight modification of the algorithm: for each vertex $x$, you keep track of the size of the subtree, and use this to select the heaviest child rather than the number of distinct colors.

This argument breaks down for a DAG since a vertex can have multiple parents.


How to prove the correctness of the binary tree inversion algorithm?

It might be surprising to you, but "the mirror reflection of the right subtree around the center of the root tree is a combination of moving the subtree from root.right to root.left and inverting the subtree around the center of the subtree itself" could be, in fact, part of the definition of "a mirror reflection of the right subtree around the center of the root tree"!
Note that the following definition of "the inversion of a binary tree", as given in the question, does not define what is the "mirror reflection of the original tree's right subtree". Although that mirroring is pretty intuitive for a human to understand accurately, given the accompanying illustrations, it is, in fact, not defined/specified clear enough to enable you to prove the correctness of the algorithm formally.

Define the inversion of a binary tree as the tree whose left subtree is a mirror reflection of the original tree's right subtree around the center and right subtree a mirror reflection of the original tree's left subtree.

So, here is the real question.
How do we define mirror reflection formally?
Here is a recursive definition. (This can be seen as taking the given algorithm as the definition basically.)
Given a binary tree $T$ or an empty graph, its mirror reflection $T'$ is another graph such that

$T'$ is empty if $T$ is empty.
$T'$ is a single node that is the same as $T$'s single node if $T$ is a single node.
Otherwise, $T'$ is also a binary tree such that

the root of $T'$ is the same as the root of $T$ and
the left subtree of $T'$ is a mirror reflection of the right subtree of $T$ and
the right subtree of $T'$ is a mirror reflection of the left subtree of $T$.

When $T'$ is a mirror reflection of $T$,  we also say $T'$ is a mirror reflection of $T$ along/around the center of $T$, or any imaginary line that goes from root to a leaf.

Here is a non-recursive definition, that is equivalent to the above.
Given a binary tree $T$ or an empty graph, its mirror reflection is any graph that is isomorphic to the graph $T'$ defined below.

If $T$ is empty, so is $T'$.
Otherwise, let $V$ be the nodes of $T$. Let $V'$ be a copy of $V$; that is, for each $v\in V$, there is unique node in $V'$ that corresponds to $v$. Call that unique node $v'$.

For any two nodes $p, c\in V$ such that $c$ is the left child of $p$, we let $c'$ be the right child of $p'$.
For any two nodes $p, c\in V$ such that $c$ is the right child of $p$, we let $c'$ be the left child of $p'$.

The OP also proposes the following geometric/graphical definition of "inversion of a tree".

Let $(a,b)$ be the coordinate of the node at depth $a$ that is the $b$-th node from the imaginary center line. If $b$ is negative then the node is to the left of the line. Then the inversion can be defined as the resulting tree if we map $(a,b)$ to $(a,-b)$ and keep the edges accordingly.

The definition above, although graphically clear to a human, might not be very friendly for rigorous reasoning. For example, "the b-th node from the imaginary center line" requires further non-trivial clarification.

With either of my definitions above, it will be rather easy to prove the correctness of the algorithm.
You might have noticed by now that inversion of a binary tree means exactly the same as its mirror reflection!


Find a lambda term satisfying two equations

This is not directly a consequence of Böhm's theorem. Böhm's theorem states that for any strongly normalizing $A$ and $B$ that are not $\beta\eta$-convertible, there exists $\Gamma$ such that $\Gamma A = K$ and $\Gamma B = S$. You don't get to constrain $\Gamma = A$ or the required form $\lambda x. x U V$. There may be a way to use Böhm's theorem on a different term, but this particular system of equations can easily be solved manually.

If such a term exists then $\Delta K = K U V = U$, so to satisfy the second equation it is necessary that $U = S$.

Then $\Delta \Delta = (\lambda x. x S V) (\lambda x. x S V) = S S V V = S V (V V) = \lambda y. V y (V V y)$.
To satisfy the first equation, $V y (V V y) = K y = \lambda z. y$. One way to satisfy this is to take $V = \lambda y z z'. y$.

Finally, verify that $\Delta = \lambda x. x S (\lambda y z z'. y)$ satisfies the two equations.


GOTO statement in programming environments for beginners?

This doesn't seem like a good idea. Normally, we teach people using a system with restrictive safety features and only remove those safety features when the learner has demonstrated competence: consider training wheels on a bike, children's safety scissors and so on. You're suggesting that we teach using a "dangerous" system (goto) and then remove the dangerous parts once the learner has demonstrated competence.

Also, I don't see how using goto would help the transition to modular programming. Modular programming doesn't tend to use goto, so it seems you're trying to aid the transition from A to B by introducing something that doesn't help with B. To use a rather melodramatic analogy, it's like proposing to help somebody transition from a tricycle to a bicycle by giving them a pair of scissors to use while riding: it introduces a dangerous habit that doesn't even contribute to the desired goal.


The algorithm you're describing is basically correct.
To summarize in one sentence: "If the current value is less than $x$, turn back."
The reason it has the desired time complexity is because the set of the nodes you are visiting is precisely:

the root node
all the nodes which are direct descendants of the nodes in the output (since every node has no more than two children, there are no more than $2k$ of these)

So the total number of times the body of your function gets executed is no more than $2k+1$.


find number in array divided into k parts

Choose an arbitrary representative from each part. Using binary search, you can find the two representatives which bracket the given element. You can then look for your given element in the $2k$ elements comprising the two parts that the representatives belong to. This algorithm takes time $O(\log(n/k) + k) = O(\log n + k)$, interpolating between the cases $k=1$ (sorted array, $O(\log n)$) and $k = n$ (unsorted array, $O(n)$).


How to calculate an accurate estimated reading time of text?

There is a similar question, so I will add a bit over the answer.

There are too many factors independent of language but solely based on individual reading abilities that such estimate would not be possible.
I assume perfect text without spelling errors and unclear grammar.

Giving it a try:
People can read 20, 50, 200, 2000... pages per hour, it depends on reading skills - only prescreening test will give you answer to that: give 2 pages, measure time, or use eye tracker and do the same.

This depends on language used, but the reading speed is measured in native language, so the differences are in the next point as for language (or decrease the speed for non-native by... proficiency at that language).

People use Cohorts imagine that the dictionary forms trie, and the speed of recognizing given word depends on amount of words with the same prefix.
Cognitive Psychology: A Student's Handbook, fifth edition by Michael W. Eysenck,Mark T. Keane, page 347.

For example: "Av..." What are possible words?
Average, Avalanche... Avengers if someone seen the movie, comics or ads.
"Ave.." - word on it's own, Average fits, Avengers also.
If person reads about statistics, "average" is already good choice, about Roman Empire - Ave it is, about movies played - Avengers.
But reading continues to the next syllabe.

It depends on mood, recent readings, coherence of text, familiarity with topic, recent topics seen (not only read).

About topic: reading novel is faster than technical text. Technical text for someone proficient will not decrease reading speed.
So the task given is important, if someone is checked for understanding text, reading speed decreases.

The language itself is not a factor, you should not take mean reading speed but median of your target group.
Yes age is factor, but not that usable as it gives fraction of other factors.

With dyslexia the decrease also vary per person, $30%$ decrease is very optimistic case.

Theory and Research in Learning Disabilities by J.P. Das, R.F. Mulcahy and A.E. Wall, page 179.

I would take into account understanding of text, with dyslexia simple, short statements are easier to cope than longer sentences.

In any case taking syllabes count, average sentence length, topic, statistical occurence of word in e.g. books, magazines, movies, spoken language, difficulty of text (taken as topic and uncommon words).

There are a lot more factors, but giving the general idea that it is not sufficient to just calculate it from text is presented.

The best estimate for personalised result - measure per person and store the result, honestly the best you can do.

You can try The Psychology of Reading by K. Rayner and A. Pollatsek.


What is the difference between a Standardization and a Specification?

You ask for the definition of "specification".  Here's one: https://en.wikipedia.org/wiki/Specification_(technical_standard).  You asked for the definition of a standard.  Here's one: https://en.wikipedia.org/wiki/Technical_standard.


Show that a circuit of size $s$ can be converted to a DeMorgan circuit computing the same function of size at most $2s$

The idea is to "move backwards" all the not gate. Assume you have some circuit, for example $(\cdot,\cdot)\rightarrow AND\rightarrow NOT\rightarrow OUTPUT$
Can be converted to:
$(\cdot \rightarrow NOT,\cdot \rightarrow NOT)\rightarrow OR\rightarrow OUTPUT$
Doing this without thought can increase the circuit size exponentially. So, when you see two $NOT$ gates one after another - cancel both of them out. I guarantee you this will work, but I wont prove it to you (this is your task)


There is a function with degree $3^n$ and maximum sensitivity $6^n$, known as Kushilevitz's function. See page 14 of this survey.

We do know that average sensitivity is bounded by the degree. This is because average sensitivity is the same as total influence, and an easy computation shows that total influence is at most the degree.


How do we construct reductions for NP-Completeness

You reduce Independent set to Vertex cover. You want to say that the vertex cover is atleast as hard as Independent set. One could way to remember is you are using a subroutine for vertex cover to solve Independent set. Since Independent set is Np-C you know you know the subroutine you used can't be polynomial. If you do the other way around using a subroutine of Independent set to solve Vertex cover. This does not say anything, as there might be a better way to solve vertex cover and does not show anything.


Existence of non-context free but decidable languages

You could simply consider the language $L = \{a^k | k \text{ is a prime number }\}$.
This is not a context free language, but surely this is decidable by a Turing Machine that checks if the length N of the input is not divisible by any number between 2 and N-1 .


How to estimate maximum n given complexity and amount of time?

You can't.  Mathematically, you can't conclude anything about the running time for all $n$, given just two points (given the running time at just two values of $n$).  There are many possible curves that might go through those two curves; two points aren't enough to determine a curve.  The running time might be something like

$$\frac{1}{2^{100}} 2^n + n^2.$$

Or, it might be something like

$$\frac{1}{2^{95}} 2^n + \frac{1}{10000} n.$$

Or, the running time might be

$$\frac{1}{100000000} n^2.$$

Or any number of other possibilities.

That said, in practice it seems very unlikely that you have an algorithm whose running time on all instances of size $n$ is $\Theta(2^n)$... and yet for $n=100,000$ it completes in 16 seconds.  That's a bit silly.  In practice, it could happen if the algorithm is sufficiently weird, but not bloody likely in practice.


How to prove $\Theta(g(n))\cup o(g(n))\ne O(g(n))$

Consider the function
$$
f(n) = \begin{cases} g(n) & \text{if $n$ is even}, \\ g(n)/n & \text{if $n$ is odd}. \end{cases}
$$


The notation $\{ x_1,x_2,x_3,\ldots,x_n \}$ means "the set of elements $x_1,x_2,x_3,\ldots,x_n$". In particular, all elements in the set are listed. If an element isn't listed, it doesn't belong to the set. For example, $\epsilon$ is not an element of $\{ab,b\}$. There is absolutely nothing special about $\epsilon$. It is a bona fide word, and undergoes no special treatment. It is not an element of $\{ab,b\}$ just as $abba$ is not an element of $\{ab,b\}$.
As for your second question, here is a family of sets indexed by $I = \{a,b,c\}$:
$$ B_a = \{a,ba\}, B_b = \{b,ba\}, B_c = \{\epsilon,aa,bbb\}. $$
The union of this family is
$$ \bigcup_{i \in I} B_i = B_a \cup B_b \cup B_c = \{\epsilon, a, b, aa, ba, bbb \}. $$
The set $I$ is completely arbitrary. It could be the empty set, it could be a singleton, it could be a larger finite set, it could be an infinite set. For example, we can define a family of sets indexed by the natural numbers (including zero): for every $n \in \mathbb{N}$, $S_n = \{n,-n\}$. The union of this family consists of all integers: $\bigcup_{n \in S_n} S_n = \mathbb{Z}$,


Examples of Analysis of Branch and Bound Method

Branch-and-bound is a heuristic.  In this context, my impression is that typically analysis of the worst-case running time of such heuristics is not enlightening: the worst-case running time is typically exponential.  On some problems in practice branch-and-bound may run significantly faster than that, but my sense is that worst-case running time analysis usually isn't very helpful for predicting when that will happen.


How can I argue that $3\mathsf{SAT}\leq_p \mathsf{IndSet}$ is polynomial in time?

You are given a formula, and you will construct a graph. You can argue the reduction is polynomial time by analyzing the time you need to construct the graph. The transformation is an algorithm: write each step down, and analyze them. If every step takes polynomial time, you have shown the reduction runs in polynomial time.

Scan the clauses of the formula in time that is linear in the number of clauses. Scan the 3 literals in every clause. Build 3 vertices, with labels corresponding to the literals in a clause. This you can do in constant time, clearly. Once you have built a triangle, add it to your graph. With reasonable assumptions, you can do this in linear time, but details naturally depend on the way you represent your graph. Nevertheless, the time taken will be polynomial.

Finally, you only need to add edges between any two complementary literals from different triangles. Scan your triangles. For every literal in the triangle, scan through every other triangle, and see if there is a complementary triangle. If so, add an edge. This process takes polynomial time; for every triangle you are scanning every other triangle, so think of something quadratic. After every triangle has been scanned, $G_\phi$ has been built.


Computing automaton for $L(A) / L(B)$ gives ones for $A,B$

This answers a different version of the question, in which the language in question is $L(A) \setminus L(B)$.
Here is an algorithm for deciding $L$:

Use the product construction to construct a DFA $C$ whose language is $L(A) \setminus L(B)$.
Let $D$ be a DFA whose language is $0^*1^*$.
Use the product construction again to construct a DFA $E$ whose language is $L(C) \Delta L(D)$.
Check (using BFS/DFS) whether some final state of $E$ is reachable from its initial state.
Output "yes" if no final state is reachable from the initial state. Otherwise output "no".

As you can see, whether the languages encountered along the way are finite or infinite makes absolutely no difference for this algorithm.


You are asking several question. I will only answer one. If you start with a set of size $n$ and you repeatedly reduce it to at most $rn$ elements, then after $t$ steps, you will have at most $r^tn$ elements. If $r^tn < 1$, then after $t$ steps you will have no elements. This happens for $t > \log_{1/r} n$. This explains where $\log_{3/2} n$ and $\log_2 n$ come from.


Every non-negative real number can be represented in any integer base $b \geq 2$ as a string of the form
$$
x_{n-1} \ldots x_0.x_{-1} x_{-2} \ldots,
$$
where $x_i \in \{0,\ldots,b-1\}$, and the string is interpreted as having the value
$$
x_{n-1} b^{n-1} + \cdots + x_0 b^0 + x_{-1} b^{-1} + x_{-2} b^{-2} + \cdots.
$$
For example, 251.5625 in base 10 is the number
$$
2 \times 10^2 + 5 \times 10^1 + 1 \times 10^0 + 5 \times 10^{-1} + 6 \times 10^{-2} + 2 \times 10^{-3} + 5 \times 10^{-4}.
$$
(You can extend this to negative numbers as well by allowing negation, e.g. -3.)

It is a basic result of arithmetic that every non-negative real number has a base $b$ expansion. In general, every number has infinitely many expansion: for example, 251.5625 can also be written as 0251.5625 or as 251.56250. If we don't allow leading and trailing zeroes then some numbers have a unique expansion, for example 0.33333…, and some numbers have two expansions, for example 251.5625 = 251.562499999….

A number is of the second form (has two expansions) if and only if it has a terminating expansion, that is one which is finite (for example 251.5625). The only number in base $b$ with this property are those of the form $N/b^k$ for integers $N,k \geq 0$. For example, 251.5625 = 2515625/104.

In your case, notice that 251.5625 = 4025/24. This shows that your number has a terminating expansion in any even basis, and in particular in base 8 (octal) and base 16 (hexadecimal). There are known algorithms to convert between bases, that you can find off the internet.

If you already know how to convert integers among bases, then you really also know how to convert non-integers, as long as they have a terminating expansion in the target base. To illustrate the method, consider the number 2.25. We want to convert it to base 4. Note that 2.25=9/4. Now 9 in base 4 is 214 (the subscript is how we indicate the base), and so 9/4 in base 4 is 2.14, since moving the decimal mark one digit to the left (from 21. to 2.1) is tantamount to dividing by the base (similarly, moving it to right corresponds to multiplying by the base).

Hopefully this theoretical information suffices for your problem.


Using a counting semaphore as a binary semaphore

A binary semaphore is just a semaphore whose values are limited to 0 and 1 (locked and unlocked; when locked there can be an unlimited queue of tasks waiting). When using such a semaphore you have to be careful never to increment it past 1. The point is that if the values are thus limited, some tricks are possible that speed up the implementation quite a bit, and this is also the most common use (think using the semaphore as a mutex). There is no real conceptual difference involved.

If you want a detailed discussion of the use of semaphores and other synchronization primitives (with some implementation discussion) see Downey's "Little Book of Semaphores". The Linux kernel used to have highly optimized semaphore implementations for contemplation, but they were removed a while back.


What is the time complexity of finding the FIRST and FOLLOW sets?

$\mathbf{first}_1$ and $\mathbf{follow}_1$ as relations over the symbols of a grammar $\mathcal{G}$ can be computed for a given non-terminal in $\Theta(|\mathcal{G}|)$, wnere the size of $\mathcal{G}$ is defined in a an intuitive way (basically, the sum of the lengths of the productions).

It's clear that $|\mathcal{G}|$ is a lower limit since no algorithm could work without considering every symbol of every production of the grammar. An algorithm which takes time linear to the size of the grammar (with a proof of time complexity) is provided in section 5.5 of Parsing Theory, Vol. 1 (S. Sippu & E. Soisalon-Soininen, 1988). (If $k\gt 1$, a polynomial term is introduced because of the size of the $FIRST_k$ sets.)

Thus, to compute the entire relation requires $O(|\mathcal{G}|\cdot|T|)$, where $T$ is the set of terminal symbols in $\mathcal{G}$. The $|T|$ factor (which could, in the worst case, be $O(|\mathcal{G}|)$) is the result of having to perform set union operations on sets of up to $|T|$ elements. In practice, there is no advantage to attempting to compute the $FIRST$ and $FOLLOW$ sets for an individual non-terminal; there is a lot of overlap in the individual computations.

These results were not new; the bibliography credits Donald B. Johnson & Ravi Sethi (1976) A characterisation of LL(1) grammars, but a paywall impedes my verification. The algorithms are also cited in Hunt, Szymanski & Ullman (1977) Operations on Sparse Relations, which refers to a 1974 paper by the same authors, with roughly the same name (paywalled, but you might be able to find it).

By way of a side note, the framework of relational expressions developed and used by Sippu & Soisalon-Soininen throughout the two volumes of Parsing Theory is a thing of beauty which for me was sufficient to justify my investment in the textbook. But you might be able to find it in a good academic library.


Which Is a Better Way of Obtaining Scales, Gaussian Blur or Down Sampling?

Down sampling may discard relevant features, while blurring should not.

As a toy example, a down sample may remove a pixel which is a local maxima, while a blur operation will preserve the maxima by increasing the values of nearby pixels. If the local maxima corresponds to an interesting feature, it may still be discernible by the human eye after blurring.

From a computational sense, Laplacian pyramids are able to reconstruct an image precisely because a blur-subtract operation preserves the "information" in the scene.


Proving the algorithm that orders an array according to the specified positions

You can't prove a false statement to be true :P

Consider this example:

a = [1, 2, 0]
b = ['a', 'b', 'c']

Output should be:

b = ['c', 'a', 'b' ]

But your algorithm will output:

b = ['c', 'b', 'a']

This because when you swap an element in its "final" position a[i] it's possibile that in one of the next loops that element will be swapped again.

To solve this problem think about swapping a[ ] elements too. :)


Time complexity of the fast exponentiation method

Instead of time complexity, it is much simpler here to count multiplications; I'll leave you to figure out the relation between multiplications and time complexity (the exact relation depends on the computation model).

Denote the number of multiplications when computing $x^n$ using your algorithm by $S(n)$.
Let's consider your cases from bottom to top:

Calculating $x^n$ for $n = 0$. The answer is $1$, so no multiplications are needed: $S(1) = 0$.
Calculating $x^n$ for $n$ odd. In this case we first calculate $x^{n-1}$ using the same method, which takes $S(n-1)$ multiplications by definition. Then we multiply the result by $x$, which uses up one multiplication. This gives $S(n) = S(n-1) + 1$ in this case.
Calculating $x^n$ for $n>0$ even. In this case we first calculate $x^{n/2}$ using the same method, which takes $S(n/2)$ multiplications by definition. Then we multiply the result by itself, which uses up one multiplication. This gives $S(n) = S(n/2) + 1$ in this case.

In total, we get the following recurrence for the number of multiplications:
$$
S(n) = \begin{cases}
0 & n = 0 \\
S(n-1) + 1 & n \text{ odd} \\
S(n/2) + 1 & n>0 \text{ even}
\end{cases}
$$
We can improve on the algorithm slightly using the identity $x^1 = x$. This gives the following alternate recurrence:
$$
S'(n) = \begin{cases}
0 & n \leq 1 \\
S'(n-1) + 1 & n>1 \text{ odd} \\
S'(n/2) + 1 & n>0 \text{ even}
\end{cases}
$$


Can Haskell ensure a Functor (or other typeclasses) satisfies its law?

So, while this question seems Haskell specific at first glance, I think it touches on enough aspects of modern Programming Languages theory and research that there's a good CS-general answer here.

As DW says, it's impossible to automatically verify that an implementation satisfies the Functor laws, by Rice's theorem.

However, strongly-typed languages give you several methods for proving properties of programs, so there are several approaches that work:

Refinement Types. These are a lightweight form of dependent types, where you can refine a type by a predicate that values of that type must satisfy. This lets you model things like the type of non-zero integers. These are implemented in LiquidHaskell, and there's an upcoming accepted paper where they extend techniques like this to verify typeclass laws. This is implemented as a checker on top of Haskell, so you can write normal Haskell code and get all the inference you normally would, but you add annotations that get checked using SMT.
Pseudo-dependent types. Haskell has GADTs, data-kinds, type families, and multi-parameter typeclasses, all of which let you reason about properties of types. The trick is that these tools can't do much to reason about values, so you end up "promoting" your functions to the type level (i.e. writing your functions as type families aka functions  on types) and proving about them. With these, you get some inference, but not quite as much as you do when writing normal functions.

In the long run, Dependent Types are coming to Haskell, but probably not in as full a way as you see in Idris or Agda.
Full dependent types. This is what Agda and Idris and Coq get you, and often in those languages, writing proofs that your instances satisfy typeclass laws is required. Types can depend on values, functions can return types, everything is merge. You have the full power of higher-order logic here, so if you can prove it, almost always you can prove it in these systems.

The tradeoff is that the inference in the languages is limited: you need to annotate nearly every function definition with its type, and in general, these languages add a degree of complexity above what Haskell has. And, all the proofs are explicit: you have to write the proof yourself that your programs fulfill your laws. Tactics can help to automate this process, but it ends up generally being rather tedious.


Proof that finite automata is closed under intersection

A possible source of your confusion is that the transition functions of $M_1$, $M_2$ and $M$ are different functions, yet you call all of them $\delta$. If instead you use $\delta_1$ resp. $\delta_2$ for the transition function of $M_1$ resp. $M_2$, the definition of $\delta$ changes to $\delta((p,q),\sigma)=(\delta_1(p,\sigma),\delta_2(q,\sigma))$. You should be able to add the subscripts in the appropriate positions of your partial proof yourself.

Now, after noting that $\delta_1^*(p,x)\in Q_1$ and $\delta_2^*(q,x)\in Q_2$, the proof can be completed by a straightforward application of the definitions of $\delta$ and $\delta_i^*$.


Definition from Wikipedia:

If a language L is context-free, then there exists some integer p ≥ 1 (called a "pumping length"[1]) such that every string s in L that has a length of p or more symbols (i.e. with |s| ≥ p) can be written as
s = uvwxy
with substrings u, v, w, x and y, such that

|vwx| ≤ p,
|vx| ≥ 1, and
$uv^nwx^ny$ is in L for all n ≥ 0.

k is called the pumping length and it's a positive integer. (it can be equal to 1).
k is NOT an arbitrary integer and every CFL is guaranteed to have one.
They chose the string w, since it's a contradicting example. (it's not a unique contradicting example)
I advise you to separate the string w (s in the definition) to different cases for-each position of v and x might be (which satisfy (!) the properties in the definition) and see if choosing some n (0 ... inf) creates a word that is not in L.
If w is in L and don't satisfy the pumping lemma (all the possible cases resolved in contradictions) -> L is not a CFL.
[Note that n=0 will remove x and v from the string, which sometimes help]
[Notice that w (in your example) is $\geq$ k, that's why you can use the pumping lemma. For strings that are shorter, you can't use it.]
For example (1 case): if v and x consists only of 'b', choosing n = 2 will create a string with number of 'b' strictly larger than 'a' which is not satisfying L properties.
k has no relation to n and m, it's a constant. For each CFL you are guaranteed to have one.
Hint for your homework : a possible contradicting example choice is very similar to your example.


If the algorithm terminates at all then $A[i] = i$ for $i \leq n-1$, and so $A$ is sorted. Hence it suffices to show that the algorithm terminates. Furthermore, when reaching $i = i_0$, we know that $A[j] = j$ for $j < i_0$, and so $A[i_0],\ldots,A[n]$ is a permutation of $i_0,\ldots,n$, which is a smaller instance of the same problem. Hence it suffices to show that the inner while loop terminates when $i = 1$.
Suppose that the inner while loop never terminates when $i = 1$. Let $j$ be the maximal value which appears infinitely many times as $A[1]$. After finitely many iterations, $A[1] \leq j$ always. Since $A[1] = j$ infinitely many times, there must be some subsequent iteration in which $A[1] = j$. After that iteration, $A[j] = j$. In all subsequent iterations, $A[1] \leq j$, which ensures that $A[j]$ stays $j$, guaranteeing that $A[1]$ never equals $j$ again. However, this contradicts the definition of $j$.
The maximal number of iterations of the inner loop is A000375. There is no known formula!
I couldn't find the sequence for the maximal total number of iterations of the inner loop (over all $i$) on OEIS.


I don't know if it has a name but it's NP-hard. Just take $K=1$, give every edge and vertex weight $1$ and ask if there's a solution with vertex reward $|V|$ and edge cost at most $|V|-1$. This happens if, and only if, there's an $s$–$t$ Hamiltonian path.  The decision version "Can I get reward at least $R$ with cost at most $C$" is NP-complete.


You can instead subtract $N-K$ and test if you go negative and then add $N$ again. Or test the number against $N/2$ and if greater subtract $N-K$ otherwise add $K$.

With 94 symbols you only need 7 bits. If you go with the post check you'll need to add a bit to account for overflows for certain values of input and $K$.


It sounds like you might be trying to re-invent double-hashing.  I recommend reading up on standard strategies for hash tables, including open addressing, closed addressing, cuckoo hashing, 2-choice hashing, and so on.


If dynamically typed languages are truly statically typed, unityped languages, what is the (finite) type expression of the one type?

This is entirely dependent on the language, and even on the implementation. The type would typically include entries for primitive functions, external library bindings (e.g. file handles), byte-compiled functions, etc. in addition to the data types of the language.

You can see a type like this in an interpreter for a dynamically-typed language written in a statically-typed language.

Here's an example of a type that's sufficient for a Logo value, showing that you don't need much to get started. Logo's values have a very simple structure: the only primitive type is the string, and the only structured type is the list. I use OCaml notation for the type.

 type logo_value =
   | Scalar of string
   | List of logo_value list

For example the logo value [3 [4 5]] is represented by the OCaml value List [Scalar "3"; List [Scalar "4"; Scala "5"]]

Here's an example of a type for an interpreter for a fragment of Scheme, again written in OCaml notation. Scheme is a larger language, with a range of primitive and structured types, functions as first-class values, and input/output objects.

type scheme_value =
  | Boolean of bool                (* #f, #t *)
  | Exact of Num.num               (* integers and rational numbers *)
  | Inexact of Complex.t           (* reals and complex numbers *)
  | Char of int                    (* Unicode characters *)
  | String of string               (* Strings (mutable, fixed-size) *)
  | Symbol of string               (* Symbols (immutable) *)
  | Cons of scheme_cons            (* Pair (mutable) *)
  | Vector of scheme_value array   (* Vectors (mutable, fixed-size) *)
  | Primitive of scheme_value list -> scheme_value   (* Primitive function *)
  | Lambda of string list * scheme_value             (* (argument names, body forms) *)
  | Port_in of in_channel          (* I/O port (input) *)
  | Port_out of out_channel        (* I/O port (output) *)
  | Eof                            (* (eof-object) *)
 and scheme_cons = {mutable car : scheme_value; mutable cdr : scheme_value}


Problem A is polynomially reducible to problem B... what can we say about A and B?

Your intuition about "relative hardness" is correct, the underlying mathematics is why III. is true. However your justification about I. is a little off (not wrong, but the reasoning is possibly not accurate).

It might help to think about reductions in these terms (everything I'll talk about here will be polynomial time, so I will leave that out just so I don't have to type it over and over); a reduction (from A to B) is just an algorithm that turns an instance of A into an instance of B, with the special property that if we know/can figure out/can use magic to find out the answer to the instance of B, we know the answer to the original instance of A. This gives us a way of solving problem A if we already know how to solve B.

This is why we say things like "B is at least as hard as A", because any algorithm for B immediately gives an algorithm for A. To flip it around, if we knew B was "easy", then A must also be "easy" (for some notion of "easy").

Notice that this relationship is not symmetric - knowing how to solve A doesn't tell us anything about how to solve B (given that all we have is the single reduction). If we had more information, maybe it would, maybe it wouldn't, but from the reduction alone we get nothing in that direction.

So then for I., we know we can turn an A into a B, and that we can solve an A, but this tells us nothing about B.

For III., we already know that A is hard (NP-hard!), and the reduction tells us that B is at least as hard as A, so B must also be NP-hard. The formal truth behind this intuition comes from the definition of NP-hardness. Remember that A being NP-hard means every single problem in NP has a reduction to A. We also know that A reduces to B, so how does this show B is NP-hard? We can compose the reductions. For every C in NP, we can reduce every instance of it to an instance of A, then take that instance of A and use our new reduction to turn it into an instance of B (as an exercise you might want to think about why we still know this is all polynomial time etc.). So this gives us a way of turning every problem C in NP into problem B, which is the definition of NP-hardness.

Coming back to II., this one again relies on definitions. NP-completeness is NP-hardness, plus the additional property that the problem is in NP. So saying problem A is NP-complete means problem A is NP-hard and A is in NP. We've just seen that the reduction to B tells us that B is NP-hard, so we have that part, but just like part I., where A being in P didn't tell us whether B was in P or not, A being in NP doesn't tell us whether B is in NP or not. It might be, but the reduction doesn't give us this information.


Empty intersection of longest path in connected graph

You need not find a vertex that does not appear in all longest paths (in fact you can't). This is neither sufficient nor necessary. It is sufficient to prove that for each vertex $v$, there exists a longest path that does not contain $v$.

Easy to see the length of the longest path is 10. For convenience, let's encode the vertices as follows.

     1
     2
    3 4
   5   6
  7 8 9 10
11        12

Then for vertices 1,2,7,11,10,12, for example, 1, there is a longest path 11-7-8-4-6-5-3-9-10-12 that does not contain 1.

For vertices 3,4,5,6,8,9, for example, 3, there is a longest path 1-2-4-6-5-7-8-9-10-12 that does not contain 3.


Constructing a DFA

There is an algorithm to construct a minimal DFA for a regular language. In this case, it isn't too hard to come up with a DFA with $z(z+1)/2$ states.

Observe that $L_z = \{\epsilon, abc, aabbcc, \ldots, a^{z-1}b^{z-1}c^{z-1}\}$. Once you know the number of $a$'s at the beginning of the word, you know how many $b$'s and $c$'s to expect. Here's a simple DFA built from this observation (with $z' = z-1$):

[source]

Following the usual convention, if there is no transition for a particular letter from a particular node, the automaton goes to a sink state.

This automaton has $n$ states reached after reading $0$ to $z-1$ letters a ($k,0,0$ for $0\le k\le z-1$), and branches of length $2k$ for $0 \le k \le z-1$ to read the right number of b's and c's ($k,i,0$ and $k,k,i$ for $1 \le i \le k \le z-1$). That's a total of $z + \sum_{k=0}^{z-1} (2k) = z^2$ states, plus one to account for the implicit sink state.

It's possible to compress this automaton a bit.

   Notice that every side branch finishes by counting the c's. Instead of tracking how many c's have already been seen, think in terms of how many c's are left to read. You can merge all the states of the form $k,k,k-n$, for all $k \ge 1$, into a state $-,n$ from which $n$ occurrences of c must be read. In particular, there will be only two final states: one for the empty word, and one after reading the right number of c's. In this automaton, the $k$th side branch has $k$ edges to read the b's (so $k-1$ states, as the start state belongs to the a trunk, and the end state belongs to the c collector), and there are $z-1$ transitions to count the c's (so $z$ states, corresponding to $0$ through $z-1$ c's left).

The total number of states in this automaton (including the sink state) is $z + \sum_{k=1}^{z-1} (k-1) + (z-1) + 1 = z(z+1)/2 + 1$.

Constructing an NFA

In other words, $n_z$ is the number of states in a minimal NFA that recognizes $L_z$. If you have a DFA with $N$ states, that's an NFA with $N$ states. So $n_z \le z(z+1)/2+1$. For most languages, a minimal NFA is smaller than a minimal DFA: nondeterminism adds expressive power in terms of how much you can accomplish with a number of states.

In this particular case, it happens that the minimal DFA above is also a minimal NFA (if I didn't make a mistake). Here's an informal proof.

   Consider the states in the middle of reading the b's. When reading $a^k b^i | b^{k-i} c^k$, where $|$ represents the current position, the state must account for both $k$ and $i$, to remember both the number of seen a's (which is necessary, because we'll need to count the c's later) and the number of seen b's (or, equivalently, the number of b's still required). This requires distinct states for every $(i,k)$ such that $1 \le i \lt k \le z-1$. In addition, there must be $z-1$ states to count the a's at the beginning, and $z-1$ states to count the c's at the beginning, plus a sink state. That's a total of $z(z+1)/2+1$ states.


probability wheel, redistribution of probabilities

This can be easily achieved by an  array $A$ and an additional variable $m$. The entry $A[i]$ stores the probability of $i$ times $m$.

In your example you start with

A=[1,1,1], m=3

The you increase the probability of the second element by 1/3. This can be carried out by setting $A[2]=4$ and $m=6$, which gives

A=[1,4,1], m=6

In general you could set the probability of element $k$ to $p$ by solving the system
$$\sum_i A[i] = m \text{ and } A[k]=p\cdot m,$$
for the unknowns $A[k]$ and $m$.

So all you need to do is to set $m$ to
$$ m = \frac{\sum_{i\neq k} A[i]}{1-p},$$
and $A[k]=p\cdot m$ for the new $m$.


Why is CNOT the only non-trivial reversible gate for two input bits?

The CNOT gate is definitely not the only non-trivial reversible gate on two input bits. For example, you could switch the order of inputs or the order of outputs. What Wikipedia means is that CNOT is the only non-trivial reversible gate up to some allowed operations, which consist of permuting the inputs and outputs, and applying reversible one-bit gates on the inputs and outputs.
If a two-input gate $G$ is reversible, then it is a permutation on $00,01,10,11$. By possibly negating the inputs (or the outputs), we can assume that $G(00) = 00$. By possibly switching the order of the inputs, we can assume that in $G(01) < G(10)$. We are left with three possibilities:
$$
00 \to 00 \quad 00 \to 00 \quad 00 \to 00 \\
01 \to 01 \quad 01 \to 01 \quad 01 \to 10 \\
10 \to 10 \quad 10 \to 11 \quad 10 \to 11 \\
11 \to 11 \quad 11 \to 10 \quad 11 \to 01
$$
The first possibility is the identity, which is trivial. The second possibility is CNOT. The third possibility is CNOT with outputs swapped.


Reduction from $A$ to $B$ as execution of Turing machines

What confuses you is that the words in the languages are encodings of machines that simulate runs of other machines, but at the end of the day, these are just words. Specifically,
given input $x = \langle M, x\rangle$ for the reduction, the reduction itself does not simulate the run of $M$ on $x$, the reduction only outputs $f(x) = \langle M'\rangle$ which is an encoding of a machine. The machine $M'$, by definition, simulates the run of $M$ on $x$, given any input $w$ for $M'$. You can think of this reduction as a python code $f$ that is given as input another python code $M$ and an input $x$ for $M$. Then, $f$ halts and outputs a python code $M'$. Note that $M'$ may never halt on any input $w$, but this is okay as $f$ never runs $M'$.
Please note that the first attached figure is irrelevant here as it does not describe how the reduction operates (how $M_f$ computes $f(x)$, given $x$), it only describes how you can define a machine $M_A$ for $\overline{HP}$ assuming that you already have: 1) a machine $M_B$ for $L_2$, and 2) a machine $M_f$ that computes the reduction $f$.


Looking for an example of proving space upper bounds for computing functions on a DTM

Perhaps the simplest way to show that a certain task can be done with small space is writing C-like pseudocode for it. If you are only using a constant number of variables, and each variable is exponentially bounded in terms of the input length (i.e. $|x| = O(k^n)$ for fixed $k$), then the resulting computation uses at most linear space. You can use the fact that addition, multiplication and division can be done in linear space ($O(n)$), as well as operations like determining the input length.

As an example, here is pseudocode for your algorithm:

f(x) {
  l = |x|;
  y = l * l;
  for i from 1 to y do:
    output 0;
}

The variables here are $l,y,i$ ($x$ is on the input tape so doesn't count). All operations are in linear space (as long as the inputs are small enough), $l \leq n$ and $y,i \leq n^2$, so the algorithm uses linear space.

If the bounds on the variables are polynomial ($O(n^k)$) rather than exponential ($O(k^n)$), then the resulting program is logspace (uses $O(\log n)$ space); all operations mentioned can be implemented in logspace. Indeed, since the bounds in your case are polynomial, your algorithm is logspace; the fact that the output is larger doesn't matter, since we only count space on the work tape.


Can we find size of total interval in O(N)

There is a simple $O(n\log n)$ algorithm based on sorting all the endpoints of the intervals. I will describe a more sophisticated algorithm, which outputs the union of the input intervals as a union of internally disjoint intervals (they may have overlapping endpoints). Denote the input intervals by $[s_i,t_i]$.

Initialize a variable $a$ to 0. This variable counts the number of active intervals.
Let $x$ go over the sorted order of the $s_i,t_i$:

If $x = s_i$ and $a = 0$, record $s_i$ as the starting point $s$ of the current interval.

If $x = s_i$ (regardless of $a$), increase $a$ by one.

If $x = t_i$, decrease $a$ by one. If now $a = 0$, output $[s,x]$.

It is not hard to modify this algorithm to output a union of truly disjoint intervals.

This algorithm runs in $O(n\log n)$, the running time being dominated by the cost of sorting the endpoints of the intervals. If the endpoints are integers and we can only access them using comparisons, then there is a simple $\Omega(n\log n)$ lower bound obtained by reduction from element uniqueness. Given a list of integers $x_1,\ldots,x_n$, form intervals $[3x_i,3x_i+1]$; I'll let you take it from here. This might look like cheating (since we assume that the endpoints are integers, and use arithmetic operations in the reduction), but it does rule out certain kinds of algorithms from achieving $o(n\log n)$ performance.


How does pre-training help with semantic segmentation with U-net

The procedure you described is how to do fine-tuning of a network for object classification.  There are two standard techniques: (1) freeze all but the last few layers, replace the last layers with new layers of the appropriate size and random weights, and train them; or (2) train all of the layers, starting from the weights of the pre-trained model as your initial weights, but use a very low learning rate.  You can also do (1) then (2).  See https://datascience.stackexchange.com/q/28383/8560 for a nice overview.

I'm not an expert on u-nets, but it appears they are used for image segmentation rather than object classification.  Therefore, the same approach of freezing the last few layers probably isn't suitable here.  You can still use method (2), i.e., fine-tuning using stochastic gradient descent with a very low learning rate.  If your task is similar enough to the task the pre-trained network was trained for, that might be effective.

I can't see any way to use a pre-trained model for object classification (like VGG16), as they use a different architecture.  Rather, you'd probably have to start with a pre-trained model for segmentation (i.e., a pre-trained U-net model).  The U-net paper says that they make pre-trained models available on their website, which perhaps you could use as a starting point.


You have 5 bits for the offset. Assuming byte addressed memory, you'll need four memory addresses to construct a word. So take two bits from the offset. Now you are left with 3 bits in the offset, hence a cache line would have 8 words.

9 bits for have been used for the index, therefore 2^9 cache blocks are present. Since its a two way assoc, each block contains 2 cache lines.

data storage =
(2^9 cache blocks
* 2 cache lines in a block
* 8 words per cache line
* 32 bits in a word) bits
= 262,144 bits

Now the rest is bit tricky as the question does not provide what other bits are available. Assuming there is a valid bit present,

per cache line we need 1 bit for valid bit + 18 bits of tag data = 19 bits of "meta" data

512 cache blocks * 2 lines per block * 19 bits = 19,456
So the total size in bits = 262,144+ 19,456 = 281,600

If there is also a dirty bit present, equations changes to

 per cacheline,
 1 bit for valid bit + 1 bit for dirty bit + 18 bits of tag data = 20 bits of "meta"data

For the second part, get the binary representation of the address. Break it into tag, index and the offset. Fill up the cache based on the tag and the index. See what happens.


Number of final states in minimal DFA for $a^*b^*+b^*a^*$

Here are the Myhill–Nerode classes of your language:

$\epsilon$
$a^+$
$b^+$
$a^+b^+$
$b^+a^+$
Everything else.

To show this, you have to do two things:

Show that when in a specific class and reading a specific letter, you go to another specific class. This essentially amounts to constructing a DFA whose states are the classes.
Show that all the classes are distinct. You do this by giving separating words for every pair of classes.

After that, all that remains to be done is counting how many of these classes correspond to words in the language.


I'll give you a recipe for constructing automata for $\Sigma^* \setminus F$ for any regular $F \subseteq \Sigma^*$.

Construct a (complete) DFA $A_F$ for $F$.
Construct the complement automaton $\overline{A_F}$.
Optional: minimise.

The first step is particularly easy (if maybe time consuming) for finite $F$. The second one is standard (flip accepting and non-accepting states) and should be covered by any textbook on this subject.

Of course, step 1 may blow up the size of the automaton (going from an easy-to-design NFA to DFA); this can in particular be the case for finite sets. In your particular case, though, you never get more than five states.


Language theoretic comparison of LL and LR grammars

There are numerous containments known. Let $\subseteq$ denote containment and $\subset$ proper containment. Let $\times$ denote incomparability.
Let $LL = \bigcup_k LL(k)$, $LR = \bigcup_k LR(k)$.
Grammar level
For LL

$LL(0) \subset LL(1) \subset LL(2) \subset LL(2) \subset \cdots \subset LL(k) \subset \cdots \subset LL \subset LL(*)$
$SLL(1) = LL(1), SLL(k) \subset LL(k), SLL(k+1) \times LL(k)$

Most of these are proven in Properties of deterministic top down grammars by Rosenkrantz and Stearns. $SLL(k+1) \times LL(k)$ is a rather trivial exercise. This presentation by Terence Parr places $LL(*)$ on slide 13. The paper LL-regular grammars by Jarzabek and Krawczyk show $LL \subset LLR$, and their proof trivially extends to $LL \subset LL(*)$
For LR

$LR(0) \subset SLR(1) \subset LALR(1) \subset LR(1)$
$SLR(k) \subset LALR(k) \subset LR(k)$
$SLR(1) \subset SLR(2) \subset \cdots \subset SLR(k)$
$LALR(1) \subset LALR(2) \subset \cdots \subset LALR(k)$
$LR(0) \subset LR(1) \subset LR(2) \subset \cdots \subset LR(k) \subset \cdots \subset LR$

These are all simple exercises.
LL versus LR

$LL(k) \subset LR(k)$ (Properties of deterministic top down grammars plus any left recursive grammar)
$LL(k) \times SLR(k), LALR(k), LR(k-1)$ (simple exercise)
$LL \subset LR$ (any left recursive grammar)
$LL(*) \times LR$ (left recursion versus arbitrary lookahead)

Language level
For LL

$LL(0) \subset LL(1) \subset LL(2) \subset \cdots \subset LL(k) \subset \cdots \subset LL \subset LL(*)$
$SLL(k) = LL(k)$

Most of these are proven in Properties of deterministic top down grammars. The equivalence problem for LL- and LR-regular grammars by Nijholt makes references to papers showing $LL(k) \subset LL(*)$. The paper LL-regular grammars by Jarzabek and Krawczyk show $LL \subset LLR$, and their proof trivially extends to $LL \subset LL(*)$
For LR

$LR(0) \subset SLR(1) = LALR(1) = LR(1) = SLR(k) = LALR(k) = LR(k) = LR$

Some of these were proven by Knuth in his paper On the Translation of Languages from Left to Right in which he introduced LR(k), the rest are proven in Transforming LR(k) Grammars to LR(1), SLR(1), and (1,1) Bounded Right-Context Grammars by Mickunas et al.
LL versus LR

$LL \subset LR(1)$ (containment follows from the above, $\{ a^i b^j | i \geq j \}$ is the canonical example for strict containment)
$LL(*) \times LR$ (the language $\{ a^i b^j | i \geq j \}$ shows half the claim, and the introduction of The equivalence problem for LL- and LR-regular grammars by Nijholt makes references to papers showing the other half)
$LR(1) = DCFL$ (see e.g. reference here).


Why can't we replace Dijkstra's priority queue with a regular queue?

The whole point of Dijkstra is that you visit the nodes in order of their distance from the source. If you use a queue that isn't a priority queue, then you visit the nodes in whatever "random" order the implementation happens to enqueue them.


Problem 1

The case of $(x\rightarrow y \vee \overline y)$ should be a "non conditional variable" with respect to $x$ (ie. that $\overline x$ should now be inserted into $W$). If this is not true, then your algorithm needs an extra step to infer this. Assuming $(x\rightarrow y \vee \overline y)$ is a "non conditional variable", we continue.

Problem 2

NOTE: this is one problem I noticed; there may very well be other problems.

The problem is with the "empty OR implication" split into two algorithms, is that in its current form, the split does not cover all cases. In particular:

You start with $(x \vee c \rightarrow y)$, then $c$ is removed and we are left with an empty OR implication of $(x \vee [] \rightarrow y)$. You suggest now splitting it into two new problems and solving each of them; one with $x=T\wedge y=T$ and one where $y=T$. But this does not cover all cases. What about the case when $x=F\vee y=F$. However, your algorithm never considers the possibility that $y$ is false.

I think you might be able to fix this by formulating the two new problems as one with $y$ and one with $\overline x$.

Problem 3

What happens when you are left with a bunch of clauses in the form:

$$(a\wedge b \rightarrow c)$$

or

$$(a \rightarrow b \vee c)$$

After reducing everything, these clauses will remain, and you won't be able to test their satisfiability easily.

Analysis

Note: This "O" notation, $\mathcal{O}(something)$ etc., is called Big O notation. $\Omega(something)$ is called Big-omega.

Supposing the algorithm did work in general, it would run in time of $\Omega(2^m)$ worst case, $m$ being the number of variables. The reason is, each splitting of problem into problems of similar size means that the algorithm runs in exponential time. To visualize this concept, look at the following image of a full binary tree (image from here):

Now imagine the original problem is the node on top. We split the problem into two problems on the second level, but they are of similar size (we only get rid of one variable, $x$ or $y$ from the empty OR implication, so we will still have lots of empty OR implications to do each level). We will potentially have to split the problem $\mathcal{O}(m)$ times to get rid of $m$ variables. This means we will have to deal with a tree with $m$ levels. A tree with $m$ levels has $2^m$ leaf nodes (nodes at the bottom). This is called exponential time, and is informally somewhat on-par with all known boolean satisfiability algorithms. But so is brute force: there are $2^m$ possible assignments of the variables, so by brute force you can guess each assignment and check for satisfiability with similar performance!


Machine epsilon vs least positive number

Machine epsilon is the relative error (the error independent of what exponent you are currently using.)

It tells you the maximum error in the mantissa after a given operation.  For example take sqrt(2.0) and sqrt(2048.0) = sqrt(2.0)*32.0.  In IEEE 754 double precision (53-bit mantissa) the maximum error in the mantissa for this result will be $2^{-53} \approx 1.11\times10^{-16}$.

Put another way, to quote Wikipedia, the machine epsilon is

  the maximum spacing between a normalised floating point number, $x$, and an adjacent normalised number is $2 \epsilon \times |x|$.

The least positive number in a floating point system includes the exponent.  In double precision IEEE 754 the smallest normalized number is $2^{-1022} \approx 2.225 \times 10^{-308}$.  The smallest denormalized number is $2^{-52}\times 2^{-1022}=2^{-1074}\approx 4.941\times 10^{-324}$.


Is it possible to obtain dynamic tree with two dimensions in big matrix

Yes.  Use a persistent data structure.  Build a tree data structure to answer queries of the form $q(i,0)$.  Then, advance $j$, updating the persistent tree data structure as you do.  This will build a data structure of size $k$ and let you answer queries in $O(\log k)$ time, where $k$ is the number of non-zero entries in the matrix.


Algorithm to sort n size input with k distinct elements

It is not possible. As if $k = \Theta(n)$, Hence you can not find a linear algorithm. Anyhow, you can find an algorithm in $O(n + k\log(k))$.

Find maximum in $O(n)$. Then create a hash table to find the $k$ distinct values is $O(n)$. Then sort the $k$ values in $O(k\log(k))$. Notice that the space complexity in this algorithm is $O(\text{largest value})$. However, the time complexity would be $O(n + k\log(k))$.


Kolmogorov complexity of a decision problem

We can view of a language $A$ as an infinite binary string (the infinite binary string corresponding to the characteristic function of $A$) and then use the notion of Kolmogorov complexity for such strings.

Google for: Kolmogorov complexity infinite words


You are underselling the "G or G*" part. This suggests a proof of the form:

"assume G isn't Hamiltonian ... prove G* must be". So try that route.

To give a further hint, I remind you of the Dirac theorem:

If a connected graph G has n >= 3 vertices and the degree of each vertex is at least n/2, then G has a Hamiltonian cycle (if it has a cycle, obviously it also has a path, you just remove an edge from the cycle).
Additionally, an n-vertex r-regular graph with r >= n/2 must be connected (assume it is not connected - what is the minimum number of vertices each connected component must have? Can there be more than 1 such component?)

I think these should give you the idea how to prove it for n >= 3.

Then it just remains to prove it for n = 2, which is trivial (the only reason it isn't included in above theorem is that it only has a path, not a cycle).

Note: because I am not sure a complement is even defined on a non-simple graph, I am assuming G is simple. But if it wasn't, the statement-to-prove couldn't be true, even if you defined a complement in any way that makes sense - what would be the complement of this graph, and how could either have a Hamiltonian path:


Prove that the depth function of a Binary Search Tree is $O(\log n)$ on average

If your input binary search tree is like the one given below  then no matter what the program does, the depth function will return $n-1$ (because the depth  is $n-1$, in this case). And it will take $n$ operations if  the program does not know the depth beforehand or by some trickery, or the depth is not stored, say, in nodes.

You are confusing three things in your question:
(1) depth function returns $d$, the depth of the tree, which is fixed for a given tree.
(2) depth function the way it is defined will always run in $O(n)$ time for any tree, skewed or balanced.
(3) the average depth $E(d)$ of a random binary search tree (which is got by randomly inserting $n$ uniform random values) is $O(\log n)$.


Sizing a Cuckoo filter for a subset of elements

As discussed in the comments it turns out that, yes, I need to size my Cuckoo filter for the set of every existing name. That being said, it is not much of a problem in the end if I only send the buckets with fingerprints in it, which shouldn't be more than 600.

In addition to that, my attempt at a self answer was very wrong. The probability that there is another name colliding with the name Anna is actually:

$$P\left(\bigcup_{i = 1}^n A_i\right) =  \sum_{k = 1}^n (-1)^{k+1} \sum_{1 \le i \lt j ... \lt k \le n} P(A_i \cap A_j ... \cap A_k)$$

This is the inclusion-exclusion principle. Because of my hypotheses, the probability can be simplified as:

$$P\left(\bigcup_{i = 1}^n A_i\right) =  1 - (1 - p)^n$$

As highlighted in the original paper, we also have to take into account that $$2b/2^f \le \epsilon$$.


Are there any problems that reduce to the halting problem?

Trivially every computable problem is reducible to $A_{TM}$. On the other extreme, there are plenty of problems which are $A_{TM}$ "in disguise," which is to say that they are Turing-equivalent to $A_{TM}$ - for example, it's a standard exercise to show that $$\{\langle M\rangle: M\mbox{ halts on input $0$}\}$$ is Turing-equivalent to $A_{TM}$.

A more interesting situation arises when we ask about strict reducibility:

  Is there a problem $X$ such that $(i)$ $X$ is not computable, $(ii)$ $X$ reduces to $A_{TM}$, but $(iii)$ $A_{TM}$ does not reduce to $X$?

The answer to this question was shown to be yes by Kleene and Post, although interestingly no natural examples are known (and indeed it's generally believed that none exist). This led to a natural follow-up question ("Post's problem"):

  Is there a computably enumerable $X$ with the above properties?

This turned out to be much harder to solve, and wound up taking more than a decade; Friedberg and Muchnik independently introduced the priority argument to show that the answer is yes.

Today priority arguments - indeed, ones vastly more complicated than the original Friedberg/Muchnik theorem - are one of the main techniques in computability theory. They originally went by excitingly violent names: finite injury (Friedberg/Muchnik falls into this category), infinite injury (introduced by Sacks), and monstrous injury (introduced by Lachlan). While the first two terms are still in use, the third is not, and we categorize priority arguments more complicated than "basic infinite injury" according to the complexity of an associated set (the "true path"); in particular monstrous injury arguments are now called 0'''-arguments.


Whether the given language is a CFL or not?

The language is context-free.

The statemant of the pumping lemma claims "there exists a $uvwxy$-division", so in order to show a language non-context-free, you have to check that every possible division leads to a pumping contradiction. Your mistake is that you only checked one division.


CPU Usage is how much your processor is running; of the available cycles to compute, how many are actually being used. On the left it shows the current value, and on the right it shows your history. The two graphs are because you have two CPUs (well, two cores in one CPU.)

Page File is something used when your RAM is filled up. All the data in your computer, while it's being used by a program, has to be "kept alive" somewhere, and this is what RAM is built for. When that's full, though, Windows will start using your hard drive instead. This is much, much slower to access than RAM, and will wear out your hard drive somewhat more quickly. I might recommend adding more RAM or closing unneeded processes.

In "Totals" you see:
- Handles, which is resources that a program is using - for instance, a program might have on handle to keep track of a file, one handle to check your registry for settings, and many many others.
- Threads, which is one part of a program that can run by itself. For instance, a simple video game will usually contain at least one thread for running the game, one thread for drawing graphics, and one thread to pay attention to mouse clicks or button presses.
- Processes, which is generally speaking "programs". Some programs, like Google Chrome or Metasploit, will keep many processes open at a time. Each process corresponds to one .exe file, although several instances of the same file could be loaded as separate processes. If you change tabs in Task Manager, you can see a list of all processes, and how much they're each using up resources on your computer.

The other three boxes, "Physical Memory", "Commit Charge", and "Kernel Memory", refer to different parts of RAM & Page File.
- Physical Memory refers to actual RAM (not page file!) being used by anything; right now you have 1.52GB out of 3.14GB of RAM available.
- Commit Charge refers to Physical Memory and Page File, collectively. Right now you are using 1.77GB, out of a total possible of 5.07GB.
- Kernel Memory refers to memory being used by Windows itself, and not by any particular process. Unlike closing a program, which frees its memory, kernel memory is almost impossible to free up.


How to Define an Efficient, Optimal or Suboptimal Parallel Algorithm?

The word "correct" is misplaced, what you should be asking is whether those definitions are meaningful / express the notion of "efficient" that you (or the author) had in mind.

The notion of efficient might vary depending on the context, so there is no "correct" definition. For example, in sequential computing, polynomial time is usually considered efficient. One of the reasons to use polynomial time is because polynomials have nice properties that cause our definition to well-behave, e.g. an efficient algorithm which uses another efficient algorithm as a subroutine is still efficient (this is because polynomials are closed under composition).

With this in mind, I'll try to give a few reasons as to why these definitions might be useful or reflect what you imagine that an efficient parallel algorithm will be.

First, it obviously holds that $w(n)=\Omega(T(n))$, since a sequential algorithm can simulate the parallel one by doing the work of all processors one by one, which takes $p(n)t(n)=w(n)$ time. Here I assumed that $T(n)$ is a lower bound on the time required for a sequencial algorithm to preform the given task. This explains your notion of optimallity, one cannot do better then $w(n)=O(T(n))$.

As for efficient, requiring the running time for each processor to be $O(\log^c n)$ results in exponential speedup over a sequencial algorithm, since $T(n)=\Omega(n)$ (the sequencial algorithm must at least read the entire input), and thus $T(n)=\Omega\left(2^{[t(n)]^{\frac{1}{c}}}\right)$.

The additional requirement of $w(n)=T(n)O(\log^c n)$ means that the overall number of operation does not increase too much (you pay in processing power for better computation time). So in this case, the overall number of operations for the sequencial/parallel algorithm is equivalent up to polylogarithmic factors.


How to use succinct circuits to construct an EXPTIME complete problem?

Since you're having trouble getting hold of Papadimitriou's classic textbook Computational Complexity, let me suggest another resource: Papadimitriou's paper with Yannakakis, A note on succinct representations of graphs. They prove the following general result:

  Suppose that $L$ is a P-complete problem, and that there is a polytime reduction $f$ from the Circuit Value Problem to $L$ in which, given an input $x_1\ldots x_n$ of size $n$, the $j$th bit of $f(x)$ is, irrespective of $x$, either constant of equals some input bit or its negation. Then the succinct version of $L$, which consists of pairs $\langle n,C \rangle$, where $C$ is a circuit on $\lceil \log_2 n \rceil$ inputs, such that $C(0) \ldots C(n-1) \in L$, is EXPTIME-complete.

The hard part of the proof uses the construction in the Cook–Levin theorem.


Is this clique algorithm in polynomial time correct or might it have another time complexity?

Your analysis of the time complexity is wrong. Specifically this statement:

In every loop we have less n s-clique where every s-clique might have maximum s(n−1) adjacent nodes to look at.

In fact you can have up to $\binom{n}{s}$ $s$-cliques.
You approach is essentially enumerating all cliques of size up to $k-1$. So you cannot hope to have a running time better than $\Omega\left( \sum_{s=1}^{k-1} \binom{n}{s} \right)$.


Why is it called 'throwing' an exception?

As far as I know, and Wikipedia confirms, exceptions in the software sense originated in Lisp. There's a good summary in A Pattern of Language Evolution by Gabriel and Steele. Exceptions (which were not yet called exceptions) arose from the need to specify the behavior of a program if an error occurs. One possibility is to halt the program, but this is not always helpful. Lisp implementations traditionally have had a way to enter the debugger on an error, but sometimes programmers wanted to include error handling in their program. So 1960s Lisp implementations had a way to say “do this, and if an error occurs then do that instead”. Originally errors came from primitive functions, but programmers found it convenient to deliberately trigger an error in order to skip some part of the program and jump to the error handler.
In 1972, the modern form of exception handling in Lisp appeared in MacLisp: throw and catch. The Software Preservation Group lists a lot of material on early Lisp implementations, including The MACLISP Reference Manual Revision 0 by David Moon. The primitives catch and throw are documented in §5.3 p.43.

catch is the LISP function for doing structured non-local exits. (catch x) evaluates x and returns its values, except that if during the evaluation of x (throw y) should be evaluated, catch immediately returns y without further evaluating x.
catch may also be used with a econd argument, not evaluated, which is used as a tag to distinguish between nested catches. (…)
throw is used with catch as a structured nonlocal exit mechanism.
(throw x) evaluates x and throws the value back to the most recent catch.
(throw x <tag>) throws the value of x back to the most recent catch labelled with <tag> or unlabelled.

The focus is on nonlocal control flow. It's a form of goto (an upward-only goto), which is also called a jump. The metaphor is that one part of the program throws the value to return to the exception handler, and the exception handler catches that value and returns it.
I don't know when software people started using “raise” for exceptions, or for that matter when they started calling them “exceptions”. I think both terms originated from hardware, but I don't know for sure. They were well-established by the mid-1980s, for example it's the terminology used in ML (see Monahan's thesis Data Type Proofs using Edinburgh LCF, 1984) and in Ada (defined in 1983).


What subset of TMs are there where the halting problem is decidable?

If you don't look at turing machines in particularly: Sometimes you can make an argument "if it halts at all, then it must halt within x steps" where x can be calculated, so you decide the halting problem by calculating x and performing x steps.
One particular case: A program with nested loops, where an upper limit for the number of iterations of each loop can be calculated before the loop is executed, will halt. And if you take such a program and insert identifiable "non-halting" constructs, like "for (;;) {}" in a C program, then the halting problem is decidable.


What do the terms 'Sample' and 'Sampling' mean in the discussion of Pattern Recognition and Machine Learning?

Suppose that you're a pollster. You're trying to understand who will win the elections in Mars. What do you do? You sample a few eligible voters from the voter population, ask them for their preferences, and tally their votes.
Sampling is not trivial, however, since your sample might not be representative, and so you might need to add in some weights when you tally the votes.

Here is another example. You're trying to understand the connection between lifestyle and longevity. You sample a few random people from the general population, and give them a questionnaire. Your goal is to create a formula that predicts life expectancy given some features of the person's lifestyle, such as whether they smoke or not.

The second example demonstrates the sort of problem that machine learning algorithms solve. Hopefully these examples give you enough hints to understand what sample and population mean in your context.


More than one NFA accepting a given language

There are many, many different NFAs accepting a particular language, or DFAs for that matter. You can just add branches that lead into dead ends at will, for example. Or add detours that give the same result as the main road, like in your automaton adding a new state $r$, with transitions from $p$ to $r$ on 1, and then from $r$ to $r$ on 0 and 1, and finally from $r$ to $q$ on 1.

In the given case, omitting the transition from $p$ to $p$ on 0 gives another language. You should convince yourself that the modified NFA doesn't accept anything containing zeros.


How to show that given language is unambiguous

To show a grammar is unambiguous you have to argue that for each string in the language there is only one derivation tree.

In this particular case you can observe that $A$ only generates $0$'s, so the $1$ generated by the start symbol $S$ must be the first $1$ in the string.

Any grammar can be made ambiguous by adding chain productions like $S\to S$.


Intuitive proof for Floyd's cycle detection algorithm

By definition, $x_0,\ldots,x_{\mu+\lambda-1}$ are all distinct, and for $i \geq \mu$, we have $x_{i+\lambda} = x_i$. Now let us prove the claim:

  Let $i \geq 1$. Then $x_i = x_{2i}$ if and only if $i \geq \mu$ and $i = k\lambda$ for some $k \geq 1$.

$\Longleftarrow$ Suppose that $i \geq \mu$ and $i = k\lambda$. Since $i \geq \mu$, we have $x_{i+t\lambda} = x_i$ for all $t \geq 0$. In particular, choosing $t := k$, we get $x_{2i} = x_{i+k\lambda} = x_i$.

$\Longrightarrow$ Suppose that $x_i = x_{2i}$. If $i < \mu$ then $x_j = x_i$ if and only if $j = i$. Since $2i \neq i$ (as $i \neq 0$), this contradicts the assumption $x_i = x_{2i}$, showing that $i \geq \mu$.

Since $i \geq \mu$, $x_i = x_{\mu + [(i-\mu) \bmod \lambda]}$. Similarly, $x_{2i} = x_{\mu + [(2i-\mu) \bmod \lambda]}$. Since $x_\mu,\ldots,x_{\mu+\lambda-1}$ are all distinct, it follows that $i-\mu \bmod \lambda = 2i-\mu \bmod \lambda$, and so $i$ is a multiple of $\lambda$.


Finding missing range in multidimensional domain

This problem is known in computational geometry as Klee's measure problem.

The solution to this problem in 2D case is based on an approach known as Sweep Line Algorithm and is know as Bentley's algorithm.

Conceptually, it is as easy as sweeping the plane by a vertical line from left to right. An intersection of a vertical line with a set of rectangles is a set of one-dimensional ranges. That way, a two-dimensional problem is reduced to $O(N)$ one-dimensional problems.

Here is an overview:

Represent each rectangle as a pair of vertical ranges. One range on the left-hand side of it and one range on the right-hand side of it.
Sort vertical ranges by their $x$ coordinate. That should take $O(N \log N)$ time.
Scan the resulting $2N$ vertical ranges in increasing order of $x$ coordinate while maintaining a set of active ranges. When encountering a left-hand side of the rectangle the corresponding range is added to the set, crossing a right-hand side removes the corresponding range.
As you finish processing updates to the set at the given $x$ coordinate verify that the current set of active ranges covers your $y$ range completely.

An efficient implementation of this algorithm maintains a set of ranges in a data structure that supports $O(\log N)$ update and query operations. It can be implemented by building a Segment Tree for all different $y$ coordinates and maintaining a total covered range in that segment tree.

It gives an overall $O(N \log N)$ complexity for a 2D algorithm.

This algorithm can be generalized to higher dimensions with $O(N^{d - 1} \log N)$ complexity. However, there are better algorithms for $d > 3$. You can find references in the Wikipedia article for Klee's measure problem.


Algorithm to generate combinations of n elements from n sets of m elements

If you have $n$ sets of $k$ elements, your problem is equivalent to that of generating all numbers with up to $n$ digits in base $k$ (where the $i$-th digit of a number represents the index of the element to select from the $i$-th group).

This can easily be done by starting from the number $(00\dots000)_k$ and iteratively adding $1$. Let $d_i$ be the $i$-th least significant digit. Start from $i=1$ and do the following: if $d_i < k-1$ the next number is obtained by increasing $d_i$ by $1$. Otherwise set $d_i =0$, increase $i$ by $1$ and repeat. When $i$ reaches $n+1$ you know that you have already generated all the numbers and you can stop.

This procedure takes $O(k^n)$ time (assuming that $k$ fits in a constant number of memory words). To see this notice that you need to update $d_1$ every time you increment the number, $d_2$ changes only every $k$ increments, etc. In general $d_i$ changes every $k^{i-1}$ increments.

Since the total number of increments is $k^n$, the total number of operations is:
$$
O\left(\sum_{i=1}^n \frac{k^n}{k^{i-1}} \right) =
O\left(\sum_{i=1}^n k^{n-i+1} \right) =
O\left(k \cdot \sum_{i=0}^{n-1} k^i \right) =
O\left(k \cdot  \frac{k^n - 1}{k-1} \right) =
O(k^n).
$$

This time complexity is asymptotically optimal because $\Omega(k^n)$ is a trivial lower bound (as there are $k^n$ distinct combinations to return).

A pseudocode:

A = An array of n integer elements, indexed from 1;
for i=1,...,n: A[i]=0;

while true:
    //A contains a n digit number in base k. Do something with it

    i = 1;
    while i<=n and A[i]==k-1:
        A[i]=0;
        i=i+1;

    if i>n:
        return;  //We have already seen all n-digits numbers in base k
    else:
       A[i]=A[i]+1;


If you are referring to the problem of deciding whether a formula given in $2-DNF$ form is satisfiable, then it is in $P$, as well as general $DNF$ satisfiability. Indeed, such a formula is satisfiable iff there is a clause that does not contain an inner contradiction. That is, a clause that does not contain both $p$ and $\neg p$ for some atomic proposition $p$. This can be checked in linear time.

Perhaps you are referring to $2-CNF$? (which is also in $P$, but it's less trivial).


How many satisfying assignments are there in a set of 3-CNF clauses where no clause share the same variable?

As you noted, for every clause there are $2^3$ possible assignments. Exactly one of them does not satisfy the clause: it's the one that has false for all variables that appear in the clause as a positive, and true for the variables that appear as a negative. In your example it is $001$. The rest of the assignments satisfy the clause. Therefore there are $2^3 - 1 = 7$ satisfying assignments for each clause, which means there are $7^k$ possible assignments in total.


Difference between memory access and write-back in RISC pipeline

In a classic 5-stage RISC pipeline, WB writes a value into a register. If the instruction doesn't write a value into a register (e.g. store), then that stage isn't used.

I1 stores a result into a register (namely R1), so it uses WB.

I2 stores a result into a register (R1) so it uses WB.

I3 does not store a result into a register, so it doesn't use WB.

You basically got it with I3: the store instruction stores to memory, so the "write" is performed inside MA.

Incidentally, on "real" RISC machines, MA tends to be more complex (and multi-cycle) because of multi-level caches and virtual memory. A store instruction may cause a page fault, so in a sense it has a "result" that isn't just the memory access.


How can I prove that a build max heap's amortized cost is $O(n)$?

I assume that the operation build just turns an array into a heap by repairing the heap-property for every subtree bottom-up (let the operation for a single repair step called heapify).

It is not so hard to see, that heapify takes $O(h)$ steps, where $h$ is the height of the subtree to repair.  We set $k=\lfloor \log n \rfloor $ as the height of heap. Notice that we have no more then $2^{(k-h)}$ subtrees of height $h$. So we can simply add up the costs as follows (we slightly abuse the big-O notation):

$$ \sum_{h=1}^k O(h) 2^{k-h} = 2^k \sum_{h=1}^k O(h)/2^{h}. $$

Since $\sum_{h=1}^\infty O(h)/2^{h}$ converges, we can upper bound the sum $\sum_{h=1}^k O(h)/2^{h}$ by a constant $C$. Thus we have that the running time for built is less than $C\cdot 2^k\le C \cdot n = O(n)$.


Local property - a property that relates to a specific vertex and its near neighbors. For example, the number of neighbors or 2nd order neighbors a vertex $v$ has. "locally looks like a tree" more formally could be written as the sub-graph of vertices with distance $k$ or less of the vertex $v$ is a tree.

Global property - a property that relates to the graph, like its diameter, average degree, number of connected components or even its size.


What is meant by interrupts in the context of operating systems?

When the OS runs a process such as "init", it would have sent signals to other sub-systems/device managers etc, like the memory, I/O devices, etc. The interrupt is just a way of telling the processor or the OS that it is ready, or it has new input, etc. So sometime during init, the OS is waiting for sub-systems to be ready, and an interrupt from these sub-systems would indicate exactly that. So that is what the "event" relates to.

In regard to hardware or software interrupts, hardware interrupts are those which come from the hardware. Eg. I/O devices like keyboard, etc. A hardware interrupt causes the processor to save its state and begin execution of interrupt handler. On the other hand, software interrupts are instructions in the instruction set, which causes the processor to change its privilege level from user-supervisor, also known as context-switch. These details will be covered later on in the text book.


Why do public key systems involve private keys?

Public key cryptography means that the entire communication between both parties is public, including the setup. Contrast this with the case of two parties $A,B$ meeting in secret, agreeing on some keyword, and using this keyword to encrypt future communications.
Clearly, if $A,B$ decide on the encrpyption scheme in public, something has to be kept private (otherwise you could decipher the messages just like the parties involved). This is the private key, so the flow is something along the following lines: $A$ and $B$ publicly discuss and share some information with each other and the world, then they do something in private and send each other encrypted messages. Witnesses to the public exchange alone can't recover what is being said.
The child version of such scheme which I like is the following. Suppose $A$ and $B$ want to agree on some secret color, only known to  them, however the entire exchange must be public. Under the assumption that mixing colors is easy, but given a mixture recovering its components is hard, then they could do the following: $A$ and $B$ each choose a secret (private key) color denoted by $a,b$. Then $A$ sends $B$ the color $c$ (public key), and the mixture $(a,c)$. $B$ now creates the mixture $(b,c)$ and sends it to $A$, and also mixes $(a,b,c)$ and keeps this compound to himself. Finally, $A$ adds $a$ to $(b,c)$ and is now also in the possession of the secret mixture $(a,b,c)$, known to $A,B$ but unknown to anyone who solely witnessed the interaction between them.


Can 2-philosophers problem be analogous to dining philosophers problem?

Short answer: yes, though it could be considered a "degenerate case" (that is, a case that ends up being somewhat different from most others).

Long answer: the Dining Philosophers problem is really about having $n$ philosophers, and coming up with an algorithm that works for any $n$. A good algorithm should work for even "degenerate cases" like zero philosophers or one philosopher—by hard-coding them if necessary ("if there's only one philosopher, eat whenever you feel like"). So $n=2$ is a perfectly valid Dining Philosophers problem.


How to design a simpler Version of CARDIAC (Cardboard Illustrative Aid to Computers)?

You want to make a binary adder. You can make one out of boolean logic gates. Your register will be based on your binary adder. It is not a more simple computer than the CARDIAC computer, because the CARDIAC works with base ten and the beginner does the arithmetic by hand. Boolean logic is taught much later in school than addition in base ten.


Expected behavior of an algorithm to minimize rankings

Finding the minimum matching is known as the assignment problem, and it has efficient solutions.
Your exact problem has been considered by Parviainen, Random assignment with integer costs — it's his "Case I". Parviainen showed that the expected value is between $\frac{\pi^2}{6} n$ and $2n$, and his simulation results suggest an intermediate value $cn$, where $c \approx 1.830$. See also the survey by Krochmal and Pardalos, Random assignment problems.


Understanding why ALL_nfa is in co-nspace

To show that $ALL_{\mathsf{NFA}}$ is in $\mathrm{co-NSPACE}(n)$, we must show that the complement $\overline{ALL_{\mathsf{NFA}}}$ is in $\mathrm{NSPACE}(n)$.

The complement is

$$\overline{ALL_{\mathsf{NFA}}} = \{ \langle N \rangle \mid N \text{ is an NFA where } L(N) \neq \Sigma^* \}$$

To show that $\overline{ALL_{\mathsf{NFA}}}$ is in $\mathrm{NSPACE}(n)$ we therefore need to devise a Turing machine that, given an NFA description $\langle N \rangle$ can tell us if there exists an input that $N$ will not accept.

Essentially, the machine will nondeterministically guess a string $w$ and verify that this string is not accepted by $N$.  Our machine may guess the wrong string, but remember that the machine is nondeterministic -- as long as it is possible to guess a string with this property, the machine will accept $\langle N \rangle$.

To guess such a string $w$ and check that the NFA does not accept it, we need to explore all the possible computations of $N$ on $w$ and show that none of them will lead to an accepting state. This does not require us to construct an equivalent DFA using the subset construction; doing this would require more than linear space. However, even just storing all of the computations of $N$ on $w$ on the Turing machine tape will require more than $n$ tape cells.

The trick is to guess the string symbol by symbol and keep track of the sets of states that $N$ could possibly be in after it has read a symbol. If $N$ has $q$ states, there are $2^q$ such sets of possible states. We start with the set $\{ q_0 \}$ and guess a sequence of $2^q$ symbols. For each symbol that we guess, we record the subset of states that can be visited from any of the states that $N$ could be in now. We can keep track of this subset of possible current states using $q$ bits (represented as $q$ cells on the tape). This is linear in $n$ where $n$ is the length of $\langle N \rangle$. This description must at the very least list the states of $N$, so $q = O(n)$.

If the set of possible current states that we are now in does  not contain an accept state, then we have found a string that cannot be accepted by $N$. We may have to guess $2^q$ symbols, since each symbol could in principle lead us to a new set of possible current states that had not been seen before. But once all sets of possible current states have been examined, we can stop. We can count to $2^q$ in binary using no more than $q$ bits. Again this requires no more than $O(n)$ bits.


In the TSPLIB norm, the travel cost between each pair of cities is the Euclidean distance between the points rounded to the nearest integer (not the distance rounded to two decimal places).


Are there algorithms with proven upper bounds but no proven lower bound (above constant time)?

To try and answer your question:

Yes. generally lower bound is much harder to prove than upper bound.
That is, to prove an upper bound, you must only show one algorithm that solves problem $A$ in $t_1(n)$ time.

To prove a lower bound $t_2(n)$ for the same problem $A$, you must show that ANY algorithm that solves $A$ MUST work in at least $t_2(n)$ time.

Take the median for example (under the comparison model). There is a recursive algorithm that solves the median problem in $O(n)$ time. That means any greater upper bound is moot, and any greater lower bound is wrong.

However a precise lower bound for the median is an open question. The algorithm mentioned above performs $c*n$ comparisons, where $c$ ~ $17$. It has been proven that for selection of median, a total of $\Omega(\frac{3n}{2})$ comparisons is required (which means a better algorithm does not exist).

However, we don't know if a greater lower bound exist. Proving a $\frac{5n}{2}$ comparisons lower bound is an open question!