Using a binary heap to solve an equation

You can generate all possible triples $(x^5 + y^5, x, y): x, y \in \{1, \dots, n\}$. There are $n^2$ of them. Next you can sort them by first component using heap sort or any other sorting algorithm(it will take $\mathcal{O}(n^2\cdot\log_2(n))$). Now we have $k$ subsequences in sorted sequence where all triples have equal first component. Let's denote $i$th subsequence as $S_i$ and their first component as $c_i$. Each $S_i$ gives $\frac{|S_i| \cdot (|S_i|-1)}{2}$ solutions such that $a^5 + b^5 = c_i = c^5 + d^5$. Number of solutions is $\mathcal{O}(|S_1|^2) + \cdots + \mathcal{O}(|S_k|^2) = \mathcal{O}(n^2)$ since $|S_1| + \cdots + |S_k| = n$.

You also can just build heap on the sequence of all triples. And consequentially extract triples with minimum first component from it. While triples have equal first component they are part of some subsequence $S_i$.

To build heap of size $n^2$ we need $\mathcal{O}(n^2)$ and to extract $n^2$ times minimum from it we need $\mathcal{O}(n^2\cdot\log_2(n))$.


Time complexity of an enumeration of SUBSET SUM instances

SUBSET-SUM instances can be encoded in base 3. We have codes for $0,1,\#$. Some codings are invalid, but in that case we can just immediately output $\#\#$ (or $\#$, if we have just written $\#$). Every SUBSET-SUM problem has infinitely many encodings, I hope that's not a problem.

If the input has length $\ell$, then (assuming the tape alphabet has at least 4 symbols) we can do the conversion in time $O(\ell^2)$. I don't know whether this is the "best" time complexity achievable.

Edit: Here is a better encoding. We still have only three input codes, $0,1,\#$. The output string always starts with $1$ and ends with $\#\#$. Further, $\#$ is output as $\#1$. Now each output string is generated once, though several output strings could correspond to the same instance.

As an example, your instance is encoded by "00#0#".


You can use the counter value as the result of the function.

Furthermore, if I understood well your question, a simple way to map $(bool,nat)$ is the following: modify the state transitions of the original automata $A$ to make the counter value equal to $2x$ if the counter of the original A is $x$ and the state is rejecting, $2x+1$ if the counter of the original $A$ is $x$ and the state is accepting.

If the one-counter machine that returns $(bool, nat)$ (with no distinction between accept/reject states, because the accept/reject condition is embedded in the returned value as explained above) is deterministic, then you can decide equivalence using this trick:

Given automata $M_1$, $M_2$ computing $f_1,f_2:\Sigma^* \to N \times \{0,1\}$;  you can transform them back to two standard accept/reject automata $M_1', M_2'$ computing $f_1',f_2':\Sigma^* \to \{0,1\}$.

Expand the alphabet adding an extra symbol $*$; and make $M_1'(x*^k ) = Accept$ if and only if $M_1(x) = k$.

When $M_1', M_2'$ find a $*$ they decrement the counter if it is $>0$, otherwise they enter a permanent reject state. If the counter reaches $0$ after the decrement, then they enter an accept state. If they find another symbol after a $*$ they enter a permanent reject state.

Now you can check language equivalence of the "standard" one-counter automata $M_1', M_2'$ (decidable in the deterministic case, see L.G.Valiant, M.S.Paterson, Deterministic One-Counter Automata, 1975) and by construction $L(M_1') = L(M_2')$ if and only if $f_1 = f_2$.


How hard is it to decide if there exists a strict improvement of a given solution of an NP-complete problem?

Here is a reduction from Set Cover to your problem. Let $(\{S_1,\ldots,S_m\},k)$ be an instance of Set Cover, and let $U = S_1 \cup \cdots \cup S_m$. Let $x_1,\ldots,x_k$ be $k$ new elements, and consider the following instance of your problem:

The sets are $S_i \cup \{x_j\}$ for $i \in [m]$ and $j \in [k]$, together with the set $U$.
The given cover consists of $S_1 \cup \{x_j\}$ for $j \in [k-1]$ together with $U$.

The given cover covers all elements but $x_k$. There is a cover which covers more elements – that is, all elements – iff $U$ can be covered by at most $k$ sets from $S_1,\ldots,S_m$.


Universal quantification in description logic

In Description Logic quantification restrictions define new concepts. The semantics of $\forall R.A$ defined so that $x\in (\forall R.A)^{\mathcal I}$ if and only if for each $y\in\Delta^{\mathcal I}$ where $(x,y)\in R^{\mathcal I}$ we have $y\in A^{\mathcal I}$.

With this definition one can check that your understanding is correct: for an empty role $R$ $\top \sqsubseteq \forall R.\bot$ (all things are  related to no other thing through $R$). I dare say that few practical ontologies ever use empty roles as constructors.


in my opinion, The designer of this question just wanted to make a famous algorithm problem a bit complicated but made it totally nonsense.

This is the famous two egg problem where

  You are given two eggs and access to a 100-story building. Both eggs are identical. The aim is to find out the highest floor from which an egg will not break when dropped out of a window from that floor. If an egg is dropped and does not break, it is undamaged and can be dropped again. However, once an egg is broken, that’s it for that egg.


What does $\omega{(1)}\cdot O(logN)$ mean?

It presumably means a product of the form $f(N)\,g(N)$, where $f(N)\in\omega(1)$ and $g(N) \in O(\log n)$.

However, that's a very strange thing to write, since every well-behaved function $h$ can be written in this way. If $h\in\omega(1)$, write it as $h(N)\cdot1$, which is valid, since $1\in O(\log N)$; if $h\in O(1)$, write it was $N\cdot (h(N)/N)$.


primitive recursive functional equivalence

It is well known that equivalence is undecidable even for CFGs resp. PDAs (see even Wikipedia). This provides a proof that the same property is undecidable for every model of any superset of CFL (by a simple special case reduction).

Since solving the word problem for any given CFL is clearly primitive recursive (by virtue of your favorite parsing algorithm), this includes the set of primitive recursive functions/algorithms.


Your definition is a complicated way to say that $S$ is the set of partial functions $X\to Y$ (the sets $A$ you choose are the domains of the partial functions).

Now, if you want to talk about computability, you have to be more precise on $X$ and $Y$: every element of $X$ and $Y$ have to be finitely described, so that they can be manipulated by algorithms.

We can for instance consider that $X=Y=\mathbb{N}$. Since they are countable and infinite, we just have to apply some bijections to get this.

Now, the framework you define is exactly the one of computability theory, you can define turing machines etc, and find out what the uncomputable are. Go here for more details.

For instance the halting function (which is in fact a function $\mathbb N\to \{0,1\}$) is uncomputable.
As for an example of subset of $S$ which contains only uncomputable functions, it is true as soon as the domain of the function is not a recursively enumerable set.
For instance there is no recursive function $NH\to \mathbb N$, where $NH$ is the set of indices of Turing machines that do not halt on input $0$.


What is an example of a (simple) tail recursive algorithm that doesn't use a helper function?

There's an example staring at you in the face: write a function that takes two arguments a and b and returns the sum of the integers from 0 to a, plus b.

Here's another example: write a function that returns the last element of a list, or a special value if the list is empty.

let rec last l =
  match l with
  | [] -> None
  | [x] -> Some x
  | h::t -> last t

Here's another example, in an imperative language: apply a function to all the elements of a list, in order, without returning a value.

let rec iter f l =
  match l with
  | [] -> ()
  | h::t -> f h; iter f t

So you can see that tail-recursive don't have to take an extra argument. However, taking an extra argument is a common pattern, and there is a deep reason for that.

A common reason to write a recursive function is to traverse a recursive data structure. For example, the list data structure is defined recursively: a list is either the empty list (“nil”), or a pair (“cons”) consisting of an element (“head”) and a list (“tail”). In Ocaml syntax:

type list_of_foo = Foo_nil | Foo_cons foo * list_of_foo;; (* Foo_cons (head, tail) *)

To act on a list, you need to specify what to do on the empty list, and what to do on a non-empty list. To traverse the whole list with a function, you make a recursive call to process the tail in the case of a non-empty list. A generic list traversal is called a fold. Writing a recursive function is one way to write a fold; another way is to call a generic fold function and tell it what to do with nil and what to do with a cons (as a function of the head and the result of processing the tail of the list).

This generalizes to all recursive data structures. A particularity of lists is that there's never more than one sub-list, so the call to process the tail can be a tail call. Contrast with a binary tree, for example:

type btree = Leaf of int | Node of btree * btree

To process a btree, when you reach a Node, you need to process both the first subtree (left child) and the second subtree (right child). They can't both be tail calls. But with lists, the one recursive call can be a tail call.

Integers don't look much like a data structure. But in fact recursion on an integer is typically based on the structure of integers. For example, when you recurse by enumerating integers from 0 to n or from n to 0 (or 1 to n, etc.), you're using the structure provided by the Peano axioms: an integer is either 0 or the successor of an integer.

So you have a recursive function which takes a data structure as an argument. It makes a recursive call, calling itself on a sub-structure of the original data. What does it return? If the recursive call is a tail call, what it returns has to be the value returned in a case where the function doesn't make a recursive call. Often, that's the “starting” case, e.g. 0 for a function that recurses on an integer or the empty list for a function that recurses on a list. What can you return in the starting case? If you return a constant, that's not very interesting. If you want to return something that depends on information collected from the data structure, you need to pass this information through the tail calls. And that's where the extra argument comes from. A tail-recursive function needs an extra argument (in addition to the data structure that it recurses over) to collect data read from the data structure.

In the starting case, you often do want to return a constant. Hence you write a pair of functions: a tail-recursive functions with two arguments (the data structure to traverse and the accumulator), which returns the accumulator when it reaches the end of the data; and an auxiliary function just to give an initial value to the accumulator. This corresponds to the initial value argument for fold functions.


What is an algorithm that maps back and forth from (x,y) coordinates to the index of that point in a space filling curve over a rectangle?

I found the math behind the hilbert curve very interesting (generates the space filling coordinates, with index)
http://www.fundza.com/algorithmic/space_filling/hilbert/basics/index.html

Python package refer,
https://github.com/galtay/hilbertcurve

for rectangles , you need pseudo Hilbert curve generation
https://stackoverflow.com/questions/38463130/hilbert-peano-curve-to-scan-image-of-arbitrary-size

and refer this
https://github.com/jakubcerveny/gilbert


Why do we assume that a nondeterministic Turing machine decides a language in NP in $n^k-3$ in Sipser's proof

The tableau used in the proof has dimensions $n^k \times n^k$. The reason is that each row represents the contents of the tape, and the number of symbols on the tape cannot possibly be more than the runtime of the algorithm. However, in the proof, the first and last cell of each row is a # symbol, and each row also needs one cell to store the current state $q$ of the TM. Thus to be sure we are able to fit the entire contents of the tape and these 3 extra symbols in $n^k$ cells, we must say the runtime (and hence the space used on tape) is bounded by $n^k - 3$.


Big O complexity of algorithm with a nested for loop only running once

Both of you are correct. The algorithm runs in time $O(n^2)$ (where $n$ is the size of numbers), and it also runs in time $O(n)$.

Big O is only an upper bound on the running time. The algorithm also runs in $O(n^3)$, in $O(n\log n)$, in $O(2^n)$, and in $O(f(n))$ for many other (in fact, infinitely many) functions $f(n)$.


Yes, a non-deterministic Turing machine can be converted into an equivalent deterministic Turing machine, but it is not known that if a polynomial time non-deterministic Turing machine can be converted into an equivalent polynomial time deterministic Turing machine.

Note "equivalent" only means they accept the same language, it does not mean they run in the same time.


Prove the equivalence of regular expressions

Start with
$$
R^*R^* = \left(\bigcup_{i=0}^\infty R^i\right) \left(\bigcup_{j=0}^\infty R^j\right) = \bigcup_{i=0}^\infty \bigcup_{j=0}^\infty R^i R^j = \bigcup_{i=0}^\infty \bigcup_{j=0}^\infty R^{i+j}.
$$
As $i,j$ go over all pairs of non-negative integers, $i+j$ goes over all non-negative integers, hence
$$
R^*R^* = \bigcup_{i=0}^\infty \bigcup_{j=0}^\infty R^{i+j} = \bigcup_{k=0}^\infty R^k = R^*.
$$


If P=NP, does this imply that all problems are NP-hard?

TL;DR: if $\sf P=NP$ then all languages except $\emptyset$ and $\Sigma^*$ are $\sf NP$-hard. The diagram is perhaps misleading if you consider that it has the implication that there are infinitely many problems outside the $\sf NP$-hard region (which you reasonably could, but I didn't assume that from it).

We assume throughout that $\sf P=NP$.
Recall that "reducible to" means that we need to map a yes-instance to a yes-instance and a no-instance to a no-instance. This rules out $\emptyset$ and $\Sigma^*$ (the set of all strings), as they lack either a yes- and no-instance.
For all other problems $L$ in $\sf NP$, we can choose a yes-instance $y$ and a no-instance $n$. To reduce $M\in \sf NP$ to $L$, we can just compute in polynomial time whether it is a yes- or no-instance and return $y$ or $n$ accordingly. Thus, the problems in $\sf NP\setminus \{\emptyset, \Sigma^*\}$ are $\sf NP$-hard.
Now let's look at the problems which are not in $\sf NP$ (or, equally, $\sf P$). Consider a $\sf EXP$-complete problem. Such a problem is not in $\sf NP(=P)$ because $\sf P\neq EXP$, so it falls outside the inner circle in the diagram. Additionally, it cannot be $\emptyset$ or $\Sigma^*$ because both problems are in $\sf P$, so the problem has a yes-instance $y$ and a no-instance $n$ and thus we can do the same algorithm above to reduce any $\sf NP$ problem to it in polynomial time. So it meets the definition of $\sf NP$-hard.
The diagram on the right is correct that ${\sf NP\neq NP} \text{-hard}$, but there is a technicality that ${\sf P=NP}\not\subseteq{\sf NP} \text{-hard}$ because of $\emptyset$ and $\Sigma^*$. I think the diagram illustrates this by using $\simeq$ rather than $=$ for the text "NP-complete".
I believe your issue was whether it is meant to say that ${\sf NP} \text{-hard} \neq \mathcal P(\Sigma^*)$, the set of all languages, and indeed that is true but only on a technicality: ${\sf NP} \text{-hard} = \mathcal P(\Sigma^*)\setminus \{\emptyset, \Sigma^*\}$. As for whether the diagram implies this or not, that's a matter of interpretation.
The left diagram doesn't have this right diagram's problem because if $\sf P\neq NP$ then $\emptyset$ and $\Sigma^*$ are in $\sf P$, not $\sf NPC$.


Algorithm for real time Coordinate smoothing

A Kalman filter is a reasonable choice for this.  It is useful for tracking the movement of an object, as it can be used with a model for the physics of the movement of an object.


Getting a variable assignment of a Tseitin transformed formula

Given a circuit $C$ on variables $V$ which has gates $G$, the Tseitin transformation produces a formula $T(C)$ on the set of variables $V \cup G$, with the property that the formula holds iff

The value of every gate variable $g \in G$ is exactly the value of this gate given the assignment to the inputs, and
The circuit outputs TRUE.

You can prove property (1) by induction. Property (2) holds since you add a specific clause stating that the top gate in the circuit is TRUE. Given this, there is an assignment causing the circuit $C$ to output true iff $T(C)$ is satisfiable, and moreover you can read this assignment from a satisfying assignment to $T(C)$ — just ignore the gate variables.

The crucial point is that in any satisfying assignment of $T(C)$, the value of the gate variables is completely determined by the value of the input variables.


Little-O: $\forall c \in \mathbb{R^+}, \exists n_0 \in \mathbb{R^+}, \forall n \in \mathbb{N}, n ≥ n_0 ⇒ g(n) \leq cf(n)$

For positive functions $f,g\colon \mathbb{N} \to \mathbb{R}_+$, you can show that

$f(n) = o(g(n))$ iff $\lim_{n\to\infty} \frac{f(n)}{g(n)} = 0$.
$f(n) = O(g(n))$ iff $\limsup_{n\to\infty} \frac{f(n)}{g(n)} < \infty$.

Using this, it is not hard to prove the two statements. Once you have done that, try translating your proofs to the definitions you were given.


Interpretation of "expected cost" of an algorithm

If you have a cost of $1$ with probability one half and $0$ with probability one half, you never reach the expected cost of $\frac{1}{2}$.

But what the expected cost gives you is the average of costs. If you repeat the algorithm and make the average of the cost (after an infinite number of times) you will get an average cost equal to the expected cost.

I hope it's clear ...


Decreasing runs of inner loop in outer loop

When loops are nested, the running time is the amount of time the innermost loop is executed multiplied by the time it takes to execute the body of the loop. In your case, the innermost loop executes $n+n/2+n/4+\dots+1\lt2n$ and we'll assume that computing the $\log$ takes constant time. So the running time is linear in $n$.


Is it possible to construct a finite state automata for a decimal adder?

Interestingly, the question in the body has a negative answer, but the question of the title has a positive answer, if you choose the appropriate representation for the data.
Let me explain this for a binary adder (I let you generalize the argument for a decimal adder). First represent the numbers $x$ and $y$ to be added in reverse binary, with a final $0$ and make sure they have the same length by adding further $0$'s at the end if needed.
For instance, $22 = 2 + 4 + 16$ would be represented by $011010$ and $13 = 1+4+8$ by $101100$. Their sum $35 = 1 + 2 + 32$ is represented by $110001$. Now, just read this data column by column
\begin{matrix}
22 \to &0&1&1&0&1&0\\
13 \to &1&0&1&1&0&0\\
35 \to &1&1&0&0&0&1
\end{matrix}
to get
$(0,1,1)(1,0,1)(1,1,0)(0,1,0)(1,0,0)(0,0,1)$. Taking all representations of the triples $x, y, z$ such that $x + y = z$, you get a regular language on the alphabet $\{0,1\}^3$, recognised by the following automaton

The trick behind this representation is that addition can be obtained by a sequential transducer.


Why use maximum likelihood for word prediction?

That approach is using a score function (in a particular way).  It is also using maximum likelihood.  Both ways of describing the approach are valid.

Why is it useful to think about this in terms of maximum likelihood?  Because it gives a more systematic way to think about this problem and others like it.

If we just want to think about maximizing a score function, the question that raises is -- what score function should we use?  How do we choose one?  It sounds arbitrary.

In contrast, the maximum-likelihood approach gives us a principled way to choose the function.  Here is how to derive that formula, given the maximum-likelihood principle.  First, they have apparently decided to use the following approximation for the probability of seeing $w_t$ as the next word, given history $h$:

$$P(w_t,h) = \exp(\text{score}(w_t,h)).$$

Once you've decided to do that, then by the definition of conditional probability it follows that

$$\begin{align*}
P(w_t|h)
 &= \frac{P(w_t,h)}{P(h)}\\
 &= \frac{P(w_t,h)}{\sum_{w'} P(w',h)}\\
 &= \frac{\exp(\text{score}(w_t,h))}{\sum_{w'}\exp(\text{score}(w',h))}.
\end{align*}$$


How to convert a Complete Binary Tree to a Priority Search Tree in O(n)

No.  If you could, you'd obtain a sorting algorithm that would run in $O(n)$ time (construct the priority search tree, then traverse the nodes in increasing order of key), but you can't sort in $O(n)$ time.


Is there any relationship between time complexity and space complexity of an algorithm?

If algorithm A takes an input of size n, and has a time complexity of O(a^n) and a space complexity of O(1)

First of all we do not know any exponential or sub-exponential time algorithm that requires only $O(1)$ space, having said this, it is difficult to reason about a hypothetical algorithm "A" because the spatial and temporal complexity are closely linked to the functioning of the algorithms and are (generally) proportional to each other, however, the answer to your question is no.

Let's try to reason starting from a $3SAT$ instance. Now we know that $3SAT$ is NP-Complete (best known time complexity for $3SAT$ is currently $O(k^n)$ with $ K=1.439$ for a deterministic algorithm)  and $3SAT$ $∈$ PSPACE , in fact space complexity of $3SAT$ is $O(n)$. Now it is difficult to imagine how increasing the space to a constant $k$ (in your question $k = 2$) may lead to a decrease in the execution time of the algorithm that solves $3SAT$ ... in fact always keep in mind that an increase in space also corresponds to a proportional increase over time.
Let me conclude by recalling the relationships between temporal and spatial complexity classes for which we believe all inclusions to be strict:

$L⊆NL⊆P⊆NP⊆PSPACE⊆EXPTIME⊆EXPSPACE$


What are these tree transformations called?

The Natural Language Toolkit (NLTK) offers binarization: nltk.treetransforms.chomsky_normal_form(). The algorithm in NLTK implements the standard, straight-forward transformation into Chomsky normal form. It assumes the tree was generated via an underlying (context-free) grammar. This results in the deep trees in the bottom row (diagram in the question post). By default, you will get the "right deep" variant, as a consequence of putting the artificial non-terminals on the right of the existing non-terminals ("right factorization") when transforming the production rules. You can change the default parameter factor="right" to factor="left", if you prefer the "left deep" variant.

However, this is not the only way to construct a grammar in Chomsky normal form, since it only requires to have production rules of the form $A\to BC$ (or $A\to a$). You could just as well decide to balance the two sets of children as well as possible and assign them to the artificial nodes on the left and right. Since children can come in odd numbers, you will have to decide to add one more to either side. If you put it on the left, you will get the "left shallow" variant, and the "right shallow" variant otherwise.

For this other algorithm to arrive at a Chomsky normal form (that produces the "shallow" variants) I could not find a term. This is likely because Chomsky normal form comes from the world of theoretical computer science and it is most useful as an existential fact ("there exists a certain normal form, s.t. ...") where the details matter little. I think "balanced factorization" would be an appropriate term for this transformation.

The library Discontinuous Data-Oriented Parsing offers more binarization schemes with a confusing set of options. This includes the algorithm from NLTK and approaches described in two papers. The library deals with natural language parsing via Linear Context-Free Rewriting Systems (LCFRS) (a generalization of Probabilistic Context-Free Grammars (PCFG)),  and a lot of options might related to this specific application. I was not able to get a "shallow"/"balanced" binarization from this library, but it might be possible.


Showing that T(n) = 2 + 2T($\frac{n}{4}$) = O($\sqrt{n}$)

Since the OP made a writing mistake in the question, I will keep the first answer and add onto it the correct one.

For $T(n)=2+2T(n/2):$
I believe that the recurrence relation is not $O(\sqrt{n})$, and in fact is $\Theta(n)$.
We can see this easily using the master theorem, where here $a = 2, b = 2, f(n)= 2$, and then $T(n) = aT(n/b) + f(n)$.
Since $f(n)=O(n^{\log_b (a)})=O(n)$ then by the first case in the master theorem we have $T(n) = \Theta(n^{\log_b (a)}) = \Theta(n)$.

For $T(n)=2+2T(n/4)$:
As I have mentioned in the previous proof, the master theorem is useful for solving such recurrence formula. In our case, we have $a=2,b=4,f(n)=2$ and thus $\log_b(a)=\log_4(2) = 0.5$
By the first case of the master theorem, since $f(n)=O(n^{\log_b(a)})=O(n^{0.5})=O(\sqrt n)$ then we will also have $T(n) = \Theta(\sqrt n)$


How to construct an NFA Ai for the given Regular property P1 and P2?

We have several definitions and notations here, let's go through these first:

We are given a set of atomic propositions AP. It is not said here explicitly, but usually this means we are interested in languages that have as alphabet the power set of AP. So for AP = {a,b,c}, our alphabet would be Sigma = { {}, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c} }.

As you can see, writing out this power set alphabet can be a lot of work. For this reason, there is an alternative notation based on propositional formulas. Consider a propositional formula phi over the variables AP. We can take a symbol x from Sigma and in phi set all atomic propositions contained in x to true and all other atomic propositions to false. Then we evaluate phi and it becomes true or false. We can understand phi to refer to all those x from Sigma for which phi evaluates to true.
For example, the formula phi="a and not b" refers to the symbols {a} and {a,c}. The formula phi="a" refers to the symbols {a},{a,b},{a,c},{a,b,c}. The formula phi="not a" refers to the symbols {},{b},{c},{b,c}. The formula phi="not a and not b and not c" refers only to the symbol {}. The formula phi="true" refers to all symbols from Sigma. The formula phi="false" refers to no symbol (not to be confused with the symbol {}). And so on ...
This logic is the notation used on the NFA edges in your example.

We call a language L over finite words "regular" if there is a NFA that accepts L.

We call a language L over infinite traces a "safety property" if every trace not in L has a bad prefix, meaning a finite prefix w, such that no infinite continuation of w is in L.

We call a safety property "regular" if the language of its bad prefixes is regular. Note we are dealing with two different notions of "regular" here, one for languages of finite words and one for safety properties over infinite traces.

General approach
You are dealing with the problem of going from an informal description of a safety property to a formal description of the language of its bad prefixes. There is no general rule for how to do this, but remember that on an intuitive level, a safety property means "some bad event never happens". The language of the bad prefixes is then exactly those finite words for which "the bad event happens at some point". Your approach would therefore be to analyze what the "bad event" is.
(This is a general problem in model checking of course, when going from informal descriptions to a formal model there is a risk of not perfectly capturing the original description.)
Consider P1: The bad event is "a becomes valid and afterwards b is valid only finitely many steps and becomes false before c becomes true". We can turn this into a slightly more verbose description: "a becomes valid, afterwards we see some b's but no c's and then we see no b and no c". We can use this description to derive a formal definition for "the bad event happens at some point". I personally find regular expressions more intuitive than NFAs, so I would first try to build a regular expression and then build the NFA from that afterwards:
(true)* a (b and not c)* (not b and not c) (true)*

This regular expression describes all finite words where at some point the bad event happens. We use the (true)* at the beginnging and the end because we do not care what happens before or after the bad event. The regular expression is already very close the NFA in your example, in general it should be easy to build NFAs from such regular expressions. You can see that the notation based on propositional formulas makes this much more compact compared to writing out the symbols explicitly, e.g. writing "a" is shorter than writing the full regular expression ({a} + {a,b} + {a,c} + {a,b,c}).
This is not the only solution, instead of requiring to see (b and not c)* before seeing (not b and not c), it would also suffice to require to see (not c)* before seeing (not b and not c). This would result in the regular expression:
(true)* a (not c)* (not b and not c) (true)*

The only difference to the first solution would be that instead of requiring to match the first (not b and not c) we see, we could also skip over some (not b and not c)'s because they also match (not c), as long as we match a (not b and not c) eventually. So in a way the first solution is the better one because the resulting NFA is more deterministic.
Consider P2: The bad event would be having two a's such that in between at some point b does not hold. Turning this into a slightly more verbose description, we would get "we see a, afterwards we see some b's without seeing a, then we reach a point where we see neither b nor a, afterwards we see any symbols until we reach the closing a". Turning this into a regular expression for "the bad event happens at some point" gives us:
(true)* a (b and not a)* (not b and not a) (true)* a (true)*

Again this is very similar to the NFA in your example, it should be easy to see how to construct an NFA from such an expression. As before we could also obtain an alternative solution, by relaxing the (b and not a)* to (not a)*, the only difference would be that this would allow to skip over some (not b and not a), as long as we match one eventually. Also, we could strengthen the middle (true)* to (not a)*, requiring us to match the first closing a instead of allowing to skip over some a's before matching the closing a:
(true)* a (not a)* (not b and not a) (not a)* a (true)*

Regarding the number of states
Since you asked about how to know the number of states: I would first try to obtain some NFA and then check if it can be simplified. For the NFAs in your example, I see no way to further reduce the number of states, but in general minimizing NFAs is a hard problem (reference), so there is no efficient algorithm for that. Of course, if you obtain a fully deterministic automaton, you can apply the standard algorithm for minimizing DFAs.


How memory controller reads from RAM with O(1) time complexity?

The RAM makes use of direct-memory-access, briefly this means that

  An element of data or instructions (such as a byte or word) can be
  directly stored or retrieved by selecting and using the
  locations on the storage media.

Now this can be happened with the use of a DMA controller, which bypasses CPU to transfer data directly between I/O device and memory.

If you want to understand precisely how this happens I suggest you read the book

  Operating System Concepts 10th Edition (Chapter 13)

I hope this helped you to understand why RAM gets instant access, comment below if you have more questions.


I'll assume that you are computing the average of the elements of an array of fixed size and that you can change the value at some position at any moment. You want a data structure that supports the following two operations:

Update element at location $i$,
Query sum of elements in range [$i$, $j$].

A binary indexed tree (aka Fenwick tree) performs both in $\cal O(\lg n)$.


There is lots of literature on scheduling, as it is a very important topic. You'd need to make your problem more precise, in particular define your objective and any restictions on the tasks. Note that most such problems are NP complete (no efficient solution likely).

I'd guess that some sort of brute force search is possible, or some sort of dynamic programming solution (but it seems that the restricted subproblems arising are different).


Robustness of non-context-free proof against trivial manipulation

Note $\left\{x^{\mathrm{R}}x\mid x\in\Sigma^*\right\}$ is context free, where $x^{\mathrm{R}}$ means the reverse of $x$.

  Or even worse, there may be some simple manipulation that push $L$ down to CFL again.

So if you consider reversing as a simple manipulation, the answer is indeed yes.


Perfect matching in a graph and complete matching in bipartite graph

These are two different concepts. A perfect matching is a matching involving all the vertices. A bipartite perfect matching (especially in the context of Hall's theorem) is a matching in a bipartite graph which involves completely one of the bipartitions. If the bipartite graph is balanced – both bipartitions have the same number of vertices – then the concepts coincide.

The term bipartite perfect matching is not standard – in fact I just made it up. Usually perfect matching just means a matching involving all the vertices.


Is there a DFA with $k+2$ states which its reverse has $2^k$ states

This is related to the usual NFA to DFA complexity problem. Strings over $\{a,b\}$ such that the $k$-th letter is an $a$.

Precise bounds for a general alphabet $\Sigma$ are given by @AntonTrunov. Then again the minimal DFA for the language has $k+2$ states, whereas the reversal needs $\frac{|\Sigma|^k-1}{|\Sigma|-1}+1$ states, assuming $|\Sigma|>1$.


Equivalent expression in English: Set Notation $\{0,1\}^K$

In set theory $B^A$ denotes the set of functions from $A$ to $B$. Thus, an element $f\in B^A$ is a function $f:A\rightarrow B$.

In your specific case $\{0,1\}^k$ is the set of functions from the natural number $k$ -- a set with $k$ elements -- to $\{0,1\}$. An element $M\in\{0,1\}^k$ is then a $k$-tuple of zeros and ones, i.e., a binary string of length $k$, as said by Yuval Filmus in a comment.

Note that not any combination of 0's and 1's up to length $k$ is valid, but only those with exact length $k$.


How is equation 1 simplified to equation 2 as shown below

I feel like this is basically paraphrasing the explantion in CLRS but maybe it will help.
Let $j$ be the length of the leftmost rod piece in an optimal solution. This piece has a cost of $p_j$ and so it contributes exactly that much to the total revenue. It is easy to see that the remaining part of the rod (of length $n-j$) must be divided up in an optimal manner as well for the whole thing to be optimal
(and thus leads to a revenue of $r_{n-j}$).
Thus, we have $r_n = p_j +r_{n-j} $. Because $r_n$ is the optimal revenue, $r_n \geq \max_{1\leq i \leq n}\{p_i+r_{n-i}\}$. But we also have $r_n = p_j +r_{n-j} \leq \max_{1\leq i\leq n}\{p_i+r_{n-i}\}$.
Putting both ineqalities together gives $r_n = \max_{1\leq i \leq n}\{p_i+r_{n-i}\}$.


What does non-linearity mean in Neural Networks? Why is it necessary?

A neural network, in its simplest form, consists of layers of neurons.
The first layer of neurons are the input, and the last layer forms the output.
A neuron $x$ on layer $i+1$ is connected to several neurons $y_1,\ldots,y_d$ on layer $i$, and it computes the following function:
$$
x = f(\alpha_1 y_1 + \cdots + \alpha_d y_d + \beta),
$$
where $f$ is a fixed function (nowadays often ReLU), and $\alpha_1,\ldots,\alpha_d,\beta$ are parameters which are learned in the training period. (The output layer often uses a different $f$.)
If $f$ is the identity function $f(z) = z$, then each neuron in the output is just an affine function of the input. This means that no matter how many layers the neural network has, all it can do is compute linear functions.
In order to allow the network to compute more complicated functions, we introduce nonlinearity, in the form of a non-linear function $f$ (that is, a function which is not of the form $f(z) = az + b$), such as ReLU, which is $f(x) = \max(x,0)$. This makes the neural network more expressive.


Given a random number generator rand5() generate gen7()

(For some reason, this old question came up first)
rand5()+rand5()*5 would give numbers 0-24, each with a probability of 1/25.  You could use the first 21 of these to return 0-6 with equal probabililty.
Likewise, rand2()+rand2()*2+rand2*4) gives numbers 0-7, each with a probability of 1/8. You could use the first 7 of these to return 0-6 with equal probability.
In pseudocode:

function rand7a() {
  do { rand7 = rand5() + rand5()*5 } while (rand7 >= 21);
  return rand7 mod 7;
}
function rand7b() {
  do { rand7 = rand2() + rand2()*2 + rand2()*4 } while ( rand7 == 7);
  return rand7;
}

EDIT: Elaboration:
1st approach:
rand2() in binary is 000 or 001 with 50-50 probability.
rand2()*2 is         000 or 010 with 50-50 probability.
rand2()*4 is         000 or 100 with 50-50 probability.
So the sum is binary xxx where each x has a 50-50 probability of 0 or 1; so each 000 to 111 has a probablilty of 1/8.

2nd approach: going through each of the 8 possibilities of the 3 rand2()s:
0+0+0 or 1+0+0 or 0+2+0 or 1+2+0 or 0+0+4 or 1+0+4 or 0+2+4 or 1+2+4
all of these with equal probablilty 1/8.


Matching girls with boys without mutual attraction (variant of maximum bipartite matching)

I think it is still the standard bipartite maximum matching problem, which can be solved by the algorithm of Hopcroft and Karp.

You put an edge in the bipartite boys-girls graph, iff you have mutual attraction. Then you maximize your matching and voilà. Notice that if you would never assign a boy to a girl with one-sided attraction, since this does not increase you objective function (# of mutal attractions).

If you want to maximize the number of happy people, then you set the weights of the complete bipartite boys-girls graph as follows

mutual attraction = 2 happy people
one sided attraction = 1 happy people
otherwise = 0 happy people

You then can compute the maximum weighted bipartite matching.


Here's an artificial counterexample:

Define an apparatus "aTM" like a TM, except that any input word which does not start with the symbol $a$ is immediately rejected. For words which do start with $a$, the TM is run as usual (and can accept/reject as usual).

This is clearly not Turing complete since it can't recognize the language $\{b\}$, which is decidable by a TM. Still, the halting problem on aTMs is as hard as the halting problem  for TMs.


Is there any standard for comparing runtimes experimentally?

In addition to elapsed time for each run, report seconds of user & system mode, and total IP packets, and total disk I/Os, if only to verify that some numbers are consistently "low" and have negligible impact on elapsed time.

On https://wiki.freebsd.org/BenchmarkAdvice PHK and others offer good advice, including

  Use ministat to see if your numbers are significant. Consider buying "Cartoon guide to statistics"


Compare two complexity functions having the same asymptotic complexity

Although, you cannot find the arbitrary constant c from master theorem, you should check using different size inputs which algorithm is faster, because even though both are upper bounded by c*n^2, if we have 4*n^2 and 1/4*n^2, still 1/4*n^2 is 16 times faster !!

A very important point is that your second algorithm seems to use divide and conquer method. This means that maybe it can be parallelized (in order to use more space but less computing time). For example, assuming an ideal choice of pivots, parallel quicksort sorts an array of size n in O(n log n) work in O(log² n) time using O(n) additional space.


Given a sorted array with n integers, how to find the element that has no duplicates?

This is a classical problem when the array isn't sorted, which has a surprising, almost magical linear solution.
But here, with a sorted array, your idea is great.
The unique element will have an index $u$, and every element $a[i]$ will be exactly the same as either $a[i-1]$ or $a[i+1]$ (which are different).
Assuming that arrays start at $0$, the shape of the (sorted) array is first a list of elements where $a[2i] = a[2i+1]$, then $a[u]$, then a list of elements where $a[2i-1] = a[2i]$.
So to decide where $u$ is, you can take a random position in the array, and just have to ask whether you're in the first part (where doubles start on even indexes) or the second part (where doubles start on odd indexes).
This takes a constant number of operation by question, and each question reduces the size of the search array by $2$ (if you sample in the middle, of course).
So, to synthesize :

By looking in the middle, you ensure that the next part you have to look at will be as small as possible
This yields a $\log(n)$ algorithm
This approach is probably optimal, but the proof that there isn't something better to do must be quite hard, so I leave it to someone else ^^


adding an edge, Is T still a MST to the new graph?

Let $n=|V|$ and $e=(x,y)$ be the new edge. Let $P$ be the unique path between $x$ and $y$ in $T$. Clearly $C = P + e$ is a cycle in $G+e$.

Let $f^* = \arg\max_{f \in P}{w(f)}$. $T$ is an MST of $G+e \iff w(e) \ge w(f^*)$.

The $\Rightarrow$ part:
If $w(e) < w(f^*)$ then $T - f^* + e$ is a spanning tree of $G+e$ of cost $w(T) - w(f^*) + w(e) < w(T)$, showing that $T$ cannot be a MST of $G+e$.

The $\Leftarrow$ part:
If $w(e) \ge w(f^*)$ then $e$ is one of the heaviest edges of $C$ and, by the cycle rule, there exists a MST of $G+e$ that does not include $e$. In particular, any MST of $G$ will also be an MST of $G+e$ (the converse is not true in general, but it is in your case since you also know that $w(e) > w(f^*)$ and hence no MST of $G+e$ can contain $e$).

A reasonable representation of $T$ will allow you to find $P$ (and hence $w(f^*)$ in time proportional to $|P| = O(n)$).

If you can preprocess $T$, then you can do better. For example you can build a lowest common ancestor (LCA) oracle in $O(n)$ time to find in constant time the LCA $z$ between $x$ and $y$. Then $w(f^*)$ will be the maximum weight between the two heaviest edges in the unique paths in $T$ from $x$ and $y$ to $z$, respectively.
These edges can be found in $O(\log n)$ time after a $O(n \log n)$ time preprocessing. For each vertex $v$ of the tree, and for each $i=1,\dots,\lceil \log n\rceil$ store:

the farthest vertex $u_v^{i}$ in the path from $v$ to the root of $T$, such that $u$ is at a distance of at most $2^i$ from $v$ in $T$; and
the heaviest edge $e_v^{i}$ in the unique path from $v$ to $u_v^{i}$ in $T$.

To report the edge $M(x,z)$ of maximum weight between a vertex $x$ and an ancestor $z$ of $x$, let $\ell$ be the largest power of $2$ that is smaller than or equal to the distance in $T$ between $x$ and $z$. Return the heaviest edge between $e_v^i$ and $M(u_v^{i}, z)$ (if $u_v^{i} \neq z$). Notice that the distance between $u_v^{i}$ and $z$ is at most half the distance between $v$ and $z$, meaning that you will only need to look at $O(\log n)$ edges.


Reducing closed TSP to open with fixed starting vertex

Add two dummy vertices, $d_1,d_2$.  Add edges of weight 0 from all other vertices to $d_1$.  Add an edge of weight 0 from $d_1$ to $d_2$.  Add an edge of weight 0 from $d_2$ to your fixed starting vertex.  (If you need a complete graph, each missing edge can be replaced by an edge with weight $+\infty$ or some very large positive weight.)  Then any Hamiltonian cycle in the resulting graph will correspond to a Hamiltonian path in the graph that starts at your fixed vertex.


Parallel algorithms on a fixed number of processors

There are several models, widely used in practice, that might be of interest to you.  Almost all of them could be viewed as generalizations of Amdahl's law.  They take two parameters, $P$ (number of processing elements) and $N$ size of the input.  Several conferences in which you are likely to find these types of analyses are the ACM Symposium on Parallel Algorithms and Architectures (SPAA), and the ACM SIGPLAN Symposium on the Principles and Practice of Paralllel Proogramming (PPoPP).

The goal with these models is generally to understand the tradeoff, for a specific algorithm, between the increased parallelism available from larger $P$ with the increased synchronization and communication costs that come along with larger $P$.

The first one that got major attention was

  Valiant, Leslie G: A bridging model for parallel computation, Communications of the ACM, 33(8):103-111, 1990.

Valiant assumes that your algorithm moves between phases of completely parallel work, a phase of barrier synchronization during which the processors communicate, and then the next phase of completely parallel work.  For each computation phase you assume it is going to take time inversely proportional to $P$.  For the synchronization phases you usually want to take into account load imbalance, and the latency of the communication phases is going to depend both on the structure of your communication network and how good a job you can do at minimizing the distance between communicating processors.

The paper

  Culler, D; Karp, R; Patterson, D; Sahay, A; Schauser, KE, Santos, E; Subramonian, R; von Eicken, T: $LogP$: Towards a Realistic Model of Parallel Computation, ACM Symp Principles and Practice of Parallel Programming, (PPOPP-4):1-12, 1993.

built on Valiant's model by carefully taking into account the $L$atency between nodes, the $o$verhead of sending a message, and the $g$ap required between send operations (a measure of bandwidth), in addition to $P$.  This is too detailed for some uses, but can be useful in cases where it is important for the algorithm designer to choose between many small messages and fewer long messages.

Finally I'll mention

  Blumofe, Robert D; Leiserson, Charles E: Scheduling Multithreaded Computations by Work Stealing, IEEE FOCS, 1994.

which gives a small generalization of Amdahl's law, pointing out that execution time is bounded (below) by $T_P = O(T_1/P + T_\infty)$, where $T_1$ is the minimum serial execution time and $T_\infty$ would be the minimum execution time with an infinite (i.e., arbitrarily large) number of processors and no communication delays.  (Another way to look at $T_\infty$ is that it is the critical path through the algorithm.)


Different boolean degrees polynomially related?

It is known that
$$ d_f = O_\epsilon(d_{f,\epsilon}^6), $$
for all $\epsilon < 1/2$. This is described in many lecture notes, for example these quantum lecture notes by Montanaro (Theorem 3). It is suspected that the best exponent is $2$. It is known that the exact value of $\epsilon$ only affects the constant.

Since $d_{f,\epsilon} \leq d_{0,f,\epsilon},d_{1,f,\epsilon} \leq d_f$, the other measures are also polynomially related.


You can use the Akra-Bazzi theorem as
$$g(x) = n^3 \in O(n^c), a_1=2, a_2 = 1, b_1 = \frac{1}{3}, b_2 = \frac{2}{3}$$
So, just we need to find $p$ such that:
$$2\left(\frac{1}{3}\right)^p + \left(\frac{2}{3}\right)^p = 1$$
You can find the computation for finding $p$ here. It is around $1.4$. Now, we can write:
$$T(n) \in \Theta\left(n^{p}\left(1 + \int_{1}^{n}\frac{u^3}{u^{1+p}}du\right)\right)$$
To simplify the term, we can write:
$$
\int_{1}^{n}\frac{u^3}{u^{1+p}}du = \int_{1}^{n}u^{2-p}du = \frac{1}{3-p}u^{3-p} |_1^n = \frac{1}{3-p}(n^{3-p}-1)
$$
Now, by substituting this term in the main complexity term, we can conclude that $T(n) \in \Theta(n^3)$.


Queue that can sort by multiple priorities?

Simple solution: use two queues
If you want to keep track of multiple priorities that are unrelated then you'll have to use 2 priority queues.
You don't have to duplicate all the data, because you can just put a reference (pointer) to the data in your queue.
That way you only have 1 location where your object resides and two pointers to it in the two priority-queues.

So the memory load would be $O(nk+2n)$ where $k$ is the length of your object and $n$ is the number of objects.
As long as $k$ is significantly long the $2n$ factor will be insignificant.

Complex solution: intertwine the queues and use COW semantics
If the priorities are related, then you can lessen the memory load by implementing the priority queue as a linked structure where shared items link to the same node.
You'll have to use copy-on-write semantics on the shared nodes for this to work.

For an example see B(+)Trees in databases
Something very similar happens in databases, where the tables are represented as B-trees.
When a change is made a reference to the tree is copied and copy-on-write is applied to all nodes that are changed.
When the change is committed the pointers for the changed tree and the original tree are exchanged.
While the transaction is in progress the old tree and the new tree are intertwined.

Beware the running time of COW
You can do the same to your priority queue, but this only makes sense if most of the data will be the same for the queues or writes are rare, otherwise the copy-on-write semantics will kill your running time.


Does any language need to have a bottom type?

Javascript has no bottom type. It does not even really have types in the sense of type theory. Instead, values are tagged with information that is called "dynamic type".
Programming languages typically do not have the bottom type (it is also called the empty type) because they allow defintion by general recursion, which implies that all types are non-empty. For example, to define a value v of any type T in Java, we can do this:
static T f() { return f(); }
static T v = f();


Prove that the following algorithm has STOP property (number of steps is finite)

You have three possible cases:

$y > 300$. Since $z = 0$ initially, the algorithm terminates.
$y = 300$ and $z = 0$.
You enter the first if and you get $y = 303$ and $z = 1$. Then you enter the second if and you get $y = 301$ and $z = 0$. Since $y > 300$ and $z = 0$  the algorithm stops.
$y < 300$ and $z = 0$.
After $k$ iterations $y = 301$ or $y = 302$ or $y=303$ and $z = k$. By executing the algorithm for each $y$ you can see that $y$ only takes values in a specific range while $z$ is always decreasing and will eventually reach 0 (or it will become less than 0). For example, let $y = 301$ and $z = k$. By executing the algorithm you get the following values:

${\bf y = 301, z = k} \\
y = 299, z=k-1 \\
y=302, z = k\\
y = 300, z = k-1 \\
y = 303, z = k \\
{\bf y = 301, z = k-1}\\
y = 299, z = k-2 \\
y=302, z = k-1\\
y = 300, z = k-2 \\
y = 303, z = k-1 \\
{\bf y = 301, z = k-2}\\$

Obviously each time you reach $y = 301$, z is decreased by 1. After showing that the same thing happens for the other two possible values of $y$ you have proved that for every possible starting value, the algorithm stops after a finite number of steps.


Is there a name and efficient algorithm for this Tree Traversal method?

Here is a simple algorithm using a stable priority queue, where elements of equal priority will exit the queue in the order they are inserted into the queue.

Let the priority of each node be its level, a.k.a. its depth from the root. Lower level means higher priority.
Initialize $Q$ to be a stable priority queue of nodes containing the root.
while $Q$ is not empty:

Take a node $q$ from $Q$.
while $q$ is not a leaf:

Add $q$'s next right sibling, if any, to $Q$.
Replace $q$ by its leftmost child.

output $q$.

This traversal goes level by level, outputting the leftmost leaf of each subtree and keeping track of what to do next in each subtree in the stable priority queue. Note that the traversal uses each edge only once.

Here is a sample run of the algorithm.

1
├──2
│  ├──3
│  │  ├──A
│  │  ├──B
│  │  └──6
│  │     └──C
│  └──8
│     └──E
├──D
└──11
   ├──F
   └──13
      ├──14
      │  ├──G
      │  └──H
      ├──17
      │  └──18
      │     ├──I
      │     └──J
      └──K

Queue is not empty: [1]
1 has no more siblings.

Descending to the first child of 1: node 2
Added 2's sibling D to the queue.
The queue is now: [D]

Descending to the first child of 2: node 3
Added 3's sibling 8 to the queue.
The queue is now: [D, 8]

Descending to the first child of 3: node A
Added A's sibling B to the queue.
The queue is now: [D, 8, B]
Output leaf: A

Queue is not empty: [D, 8, B]
Added D's sibling 11 to the queue.
The queue is now: [11, 8, B]
Output leaf: D

Queue is not empty: [11, 8, B]
11 has no more siblings.

Descending to the first child of 11: node F
Added F's sibling 13 to the queue.
The queue is now: [8, 13, B]
Output leaf: F

Queue is not empty: [8, 13, B]
8 has no more siblings.

Descending to the first child of 8: node E
E has no more siblings.
Output leaf: E

Queue is not empty: [13, B]
13 has no more siblings.

Descending to the first child of 13: node 14
Added 14's sibling 17 to the queue.
The queue is now: [B, 17]

Descending to the first child of 14: node G
Added G's sibling H to the queue.
The queue is now: [B, 17, H]
Output leaf: G

Queue is not empty: [B, 17, H]
Added B's sibling 6 to the queue.
The queue is now: [17, 6, H]
Output leaf: B

Queue is not empty: [17, 6, H]
Added 17's sibling K to the queue.
The queue is now: [6, K, H]

Descending to the first child of 17: node 18
18 has no more siblings.

Descending to the first child of 18: node I
Added I's sibling J to the queue.
The queue is now: [6, K, H, J]
Output leaf: I

Queue is not empty: [6, K, H, J]
6 has no more siblings.

Descending to the first child of 6: node C
C has no more siblings.
Output leaf: C

Queue is not empty: [K, H, J]
K has no more siblings.
Output leaf: K

Queue is not empty: [H, J]
H has no more siblings.
Output leaf: H

Queue is not empty: [J]
J has no more siblings.
Output leaf: J

You can play with a JavaScript implementation by Apass.Jack of this algorithm

The only slowdown for this algorithm is the stable priority queue. Using generic stable priority queue will give you $\mathcal{O}(n \log n)$ total runtime, where $n$ is the size of the tree.

However, it is possible to cut the running time down to $\mathcal{O}(n)$. Note that once we take a node with priority $p$ from the top of the queue, we will then possibly add a node with priority $p$, then descend to the child, then possibly add a node with priority $p+1$ and so on. This gives an idea to implement the priority queue as a linked list:

Each element of the list is a queue of nodes with the same priority.
Top priority is at the head of the list. If we pop last node from the top queue, the head of the list is removed.
When we descend to a child, the (candidate) priority is incremented, so we should move through the list, if necessary.
When we push new node, we either insert new queue into the list, or push the element to existing one.

Here's the states of such a priority queue from the run above (asterisk means current queue for insertion):

Initial:
└─[1] *

After popping node 1 and descending to node 2:
└─[D] *

After descending to node 3:
├─[D]
└─[8] *

After descending to node A:
├─[D]
├─[8]
└─[B] *

Taking D from the top:
├─[8] *
└─[B]

And pushing 11 before [8] because of greater priority.
├─[11] *
├─[8]
└─[B]

Taking 11 from the top and adding 13, which has the same priority as 8:
├─[8, 13] *
└─[B]

Taking 8 from the top:
├─[13] *
└─[B]

Taking 13 from the top:
└─[B] *

Pushing 17 with the same as B priority:
└─[B, 17] *

Added H to after [B, 17] because we descended:
├─[B, 17]
└─[H] *

Took B from the top:
├─[17] *
└─[H]

Added 6:
├─[17, 6] *
└─[H]

Took 17, added K:
├─[6, K] *
└─[H]

Descended to the child:
├─[6, K]
└─[H] *

Added J to a new queue, because we descended:
├─[6, K]
├─[H]
└─[J] *

Exhausting the rest of the queue:
├─[K] *
├─[H]
└─[J]

├─[H] *
└─[J]

└─[J] *


Halting problem of TM which recognize recursive languages is undecidable?

By definition, recursive languages are decideable by Turing machines. Thus for recursive languages the TM will always halt.


Does Paxos consensus algorithm scale linearly?

Apologies if this answer does not belong to this site

According to this paper released in 2013 which compares the performance over scale of Paxos and an optimized version of it Fast Paxos

  Paxos and Fast Paxos are optimal consensus algorithms that are simple and elegant, while suitable for efficient implementation

Reading further section 3.4. Scale Up , you can find two graph plots.

The left plot shows the number of requests served on y-axis and the number of replicas on x-axis.
The right plot displays the average response time on y-axis and the number of replicas on x-axis.

I think it gives an idea about what one should expect.They are optimal choices according to the paper and I don't know of any other

As far as it goes for the running time , I think I read somewhere that it's linear.


Proof for Transitivity of Weak Bisimulation ≈

You are on the right track. It can be useful to prove the following lemma: if $\sim$ is a weak bisimulation, if $P\sim Q$ and if you have a sequence of transitions $P\xrightarrow{w}P'$ for $w\in (Act\cup\{\tau\})^*$ then there must be a sequence $Q\xrightarrow{w'}Q'$ with $P'\sim Q'$ and $w =_{\tau} w'$, i.e., $w$ and $w'$ are "the same modulo $\tau$". This can be done by induction on $w$, and it will come in handy when you deal with transitivity. Check that $u=_\tau u'$ and $v=_\tau v'$ imply $uv=_\tau u'v'$, i.e., that $=_\tau$ is a congruence.


Difficulty in updating the balance factor of nodes in AVL tree

The reason that the number of possible values for the balance factors at $y$ and $z$ is limited is not only the fact that the tree has been AVL before insertion, but also the precise location where the rotation is performed in an ex-AVL tree.

Rebalancing is only needed at the lowest position where the balance becomes $\pm 2$ where below had balance factors $0$. All those $0$ balance factors have been changed into $\pm 1$ depending on the side where the key has been entered. The short reason for this is that when a node has originally balance factor $0$ and one of its subtrees becomes taller after insertion, not only the balance factor becomes $\pm 1$ but also the total length of the tree at that node becomes one taller, so we have to consider its father.

If that father has balance $0$ it will become $\pm 1$, the tree is taller, and we proceed    up again [diagram b)].
If the father has balance $\pm 1$ we may happen to improve the
balance to $0$, and we stop, no rotation needed  [diagram a)].
If the balance becomes $\pm 2$ we rebalance at that point using the
proper rotation. After rotation the tree at that point has the same
height as originally, so we do not have to consider balance factors higher up
in the tree.  [diagram c)]

So the issue here is to determine the context where the rotation takes place. This is determined by following the insertion process bottom-up, from the leaf where the key was added.

The precise type of rotation (single/double, left/right) is determined by the insertion path that was followed below the node where we rotate.

In the single rotation case we have left-left insertion from $x$ so $y=-1$ (longer to the left, my balance factors are opposite to yours). The value at $z$ is not important, its complete subtree is copied during the single rotation at $x$.
In the double rotation case we have left-right insertion from $x$ so again $y=-1$. At $z$ we might have any value: $\pm 1$ depending on whether the key went left/right at $z$, but even $0$ in the special case $z$ itself was inserted!


Determine whether a system of $n$ linear equations has solutions in $\{0, 1\}^n$ in polynomial time

1-IN-3SAT is the following problem: given a collection of 3-clauses (just like 3SAT), decide whether there is a truth assignment which satisfies exactly one literal in each clause. 1-IN-3SAT is known to be NP-complete, see for example here. You can reduce 1-IN-3SAT to your problem – I'll let you work out the details.


Minimum number of vertices to remove to bound the largest connected component of a graph

The optimization version of this problem is known as Graph Integrity, which is unfortunately NP-Hard problem:

  The integrity of a graph G, denoted $I(G)$, is defined by:
   $I(G) = min\{
 |S| + m(G − S) : S \subset V (G) \}$ where $m(G − S)$ denotes the maximum
  order of a component of $G − S$;


Shifting subset sum solution by constant positive integer

Your error is that you add your constant to the left-hand side of the equality multiple times, and only once to the right side. For example, $1+1=2$ clearly holds. If you add $8$ to both sides of it, you get $1+1+8=10$ which also holds. Erroneously you might add it twice to the left hand side and get $9+9=10$, which does not hold.

In your case, $0$ should not become $8$, but instead $8 \cdot 5 = 40$. Now a solution exists again.


Multiple production rules for expressions of the same type?

In one word - ambiguity.

Sometime you don't want your grammar to be ambiugous.

For example, for parsing. Ambigous grammar can't have a $LR(K)$ grammar (you can think of ambiguity as non determinism). $LR(K)$ parser handle determinstic grammars.

Example for the ambiguity of your grammar:

The sentence a * b + c can be derived in two different ways.


non-binary locality-sensitive hashing with random projections

Let $h_r(x)$ be a hash function that hashes a point $x$ to a one-bit hash output.  Then you can construct a hash function that gives you a $b$-bit hash output, by concatenating $b$ independent one-bit hashes:

$$h_{r_1,\dots,r_b}(x) = (h_{r_1}(x), \dots, h_{r_b}(x)).$$

For example, you can pick $b$ random hyperplanes; then the $i$th bit of the hash will indicate where the point falls relative to the $i$th hyperplane.

This avoids the need to invent new LSH functions.


Generation regular languages by context free grammar

The question is poorly worded. Here is what they probably meant to ask:

  Is the language generated by a context-free grammar always regular?

Clearly, the answer is negative.

However, this is just a guess, since the question isn't really clear. I suspect ignoring questions which are not clearly stated. If you encounter such a question in an exam, ask the setter to rephrase the question using proper English.


k-enclosing rectangle in two-colored point set

Ok as you have a working solution but seem concerned by optimization, I will detail here how to do it very efficiently. I assume that your rectangle has to follow the discretized grid (I now have a doubt on it reading your question).

Let's build 2 $n \times m$ count arrays $NB$ and $NW$ which are the number of respectively black and white points in each cell. You can fill these arrays in $O(p)$ as you just have to consider any point and decide which value of the array you increment.

Then you build the 2 $n \times m$ accumulator arrays $RB$ and $RW$. $RB[i, j]$ and $RW[i, j]$ are the number of respectively black and white points in the rectangle (left=0, up=0, right=$j$, down=$i$). You can fill these arrays with a very simple DP using $NW$ and $NR$, in $O(nm)$. Note that computing row after row, and in the row looping on elements, you can break the latter loop whenever $RB > k$.

The overall time complexity will be $O(max(p, nm))$.


I assume $n$ takes only positive values. By the definition of Big-Omega you could prove it by showing the following

$$\lim_{n \rightarrow \infty}\frac{\frac{n}{100}}{n} >0$$

The rest is a simple exercise.


Asymptotic calculation check for triple-nested for-loops

As Yuval Filmus and gnasher729 have pointed out my original equation for the repetition structure is indeed wrong. I believe this to be the true correct answer:

$\sum_{i=1}^{n} (\sum_{j=1}^{i^2} j)$

$= \sum_{i=1}^{n} (\frac{i^4+i^2}{2})$

$= \frac{1}{2} \sum_{i=1}^{n}i^4 + \frac{1}{2} \sum_{i=1}^{n}i^2$

$\approx \frac{n^5}{10} + \frac{n^3}{6}$

$\therefore runtime \in O(n^5)$


Is two-coloring parts of a bipartite graph so that for each uncolored vertex, the incoming edges from each color are roughly equal NP-complete?

Your bipartite graph describes a set system whose elements are the vertices in $V_1$ and whose sets are the vertices in $V_2$. Your condition is the same as asking whether the discrepancy is at most $1$.

If all sets have even size (i.e., all vertices in $V_2$ have even degree), then the discrepancy is always even, and so you are interested in whether a given set system in which each set has even size has discrepancy zero. It turns out that this is NP-hard even if all sets have size 4. This problem is known as Max-2-2-Set-Splitting.

There are much stronger NP-hardness results on discrepancy, such as Tight hardness results for minimizing discrepancy by Charikar, Newman and Nikolov. You can find pointers on Max-2-2-Set-Splitting there.


Maximize length of side of triangle from points on a circle

You could transform the question into finding the biggest minimum angle of the triangle vertices relative to the centre.
Preparatory work:

Find centre $(x_C, y_C)$, if not already known (intersect bisectors of randomly-chosen pairs of points). $o(1)$

a) Make list of angle position for each point, $a_i = \text{atan2}(y_i-y_C, x_i-x_C)$. $o(n)$
b) Sort angle list. $o(n \log n)$

Main determination:

In succession for each point:
a)  find points closest to $\pm 120^\circ$ points  from the list, $o(\log n)$ per point
b) record max minimum angle with this point, update overall maximum if needed. $o(1)$ per point

Post process

Convert angle back into distance (either directly or by retrieving the indices of the appropriate points). $o(1)$

Explaining #3 a little more: you should find four points from the two binary searches, one either side of the $+120^\circ$ & $-120^\circ$ points. That gives you four triangles to examine for angles (differences), composed of the base point plus choices from left/right of each of the $\pm 120^\circ$ lines.  (If any of the points are the same (few/crowded points) , there will be fewer triangles to check).

For convenience you might add extra copies of the points either side of the wraparound $0^\circ=360^\circ$ to avoid special cases in the search - eg. duplicate the point at (say) $+358^\circ$ to also be seen at $-2^\circ$.


I had a course held by Jiri Srba a few years ago on basic complexity and computability theory is good, I would say. The second part (Lecture 9 to 15) goes through time and space complexity, shows some important results on the field and has pdf's of both exercises and solutions for each lecture.
It is based on the book "Introduction to the Theory of Computation" by Michael Sipser, which also has a good walkthrough of both topics in general.

Link: https://intranet.cs.aau.dk/education/courses/2010/cc/course-plan/ (owned by Aalborg University)

Good luck!


Finding a 5-Pointed Star in polynomial time

If $G=(V,E)$ is a graph, how many subsets of $V$ of size $5$ exist?

If there is a 5-clique, one of this subsets is a clique.

Spoilers below:

   There are ${|V| \choose 5}$ possible subsets to check, that is, at most $|V|^5$ options, which is polynomial in the input. This is NOT the case for an arbitrary $k$, since $|V|^k$ might be exponential in the input, and this is why $\text{CLIQUE} \notin P$ (unless P=NP, agghh.).


How does automatic differentiation work?

The function is given as a "decorated" tree. Your sample function has a root node decorated "+", with one child representing $x^2$ and the other $yx$. The first child has root node "^", with children "$x$" and "2", both leaves. The second child has root node "*" with children "$y$" and "$x$".

In principle, automatic differentiation just applies the rules of differentiation recursively. In your case, we start with $\partial f/\partial x = \partial(x^2)/\partial x + \partial (yx)/\partial x$. To compute $\partial (yx)/\partial x$, we use the product rule:
$$ \frac{\partial(yx)}{\partial x} = y \frac{\partial(x)}{\partial x} + \frac{\partial(y)}{\partial x} x. $$
For variables we know that $\partial x/\partial x = 1$ while $\partial y/\partial x = 0$, and simplification (one of the basic building blocks in any computer algebra system) gives $\partial(yx)/\partial x = y$. It is similar for $x^2$, though here the rule is more complicated: $(f^g)' = f^g (gf'/f+g'\log f)$.

In practice, there are probably some optimizations. Using pattern matching techniques (that is, by having specific rules) we can, for example, recognize $x^2$ for what it is, and directly calculate $\partial(x^2)/\partial x = 2x$. Similarly, if there is a subtree not depending on $x$, we could directly conclude that its derivative with respect to $x$ is zero.


Is it "valid" for semantic functions to query outside of the grammar in attribute grammars?

The sum function of your example itself is already stepping out of the strict scope of the grammar. Or you'd have to to explicitly include all the machinery used in your attributed grammar into it, in which case nothing forbids adding (some formalization of) SQL and a database to it.


Useful functions between polylogarithmic and polynomial?

According to Wikipedia (which attributes the following result to Knuth), the running time of the mixed-level Toom–Cook algorithm for integer multiplication is
$$ \Theta(n\log n \cdot 2^{\sqrt{2\log n}}). $$
The function $2^{\sqrt{2\log n}}$ is super-polylogarithmic but sub-polynomial.


If a one-way functions (OWF) exist, then there exits a OWF that is computable in quadratic running time by a padding argument

When we talk about quadratic running time, we mean $O(n^2)$ running time where $n$ is the length of the input -- i.e., the running time is a constant times the square of the length of the input.  Make sure you understand what the length of the input is here.  By padding the input, we've made the input longer.  Even though the overall running time doesn't change, the size of the input is larger, so relatively speaking, the running time is now a slower-growing function of the input size.

For instance, suppose $f$ can be computed in cubic time: in $O(k^3)$ time, where $n$ is the length of the input to $f$.  Now consider the padded function $f'$, which has been padded out to the length $k^{1.5}$.  What is the running time of $f'$?  Its running time remains $O(k^3)$, but now the input is of size $k^{1.5}$.  Re-expressing the running time of $f'$ as a function of its input size, we let $n=k^{1.5}$ be the length of the input to $f'$, and then notice that $k^3=n^2$, so the running time of $f'$ is $O(n^2)$: quadratic in the size of its input.

On your specific question: yes, the $O(n^2)$ seems unnecessarily loose.  Your argument that the running time of $f'$ is $O(n)$ (linear in the length of its input) looks right to me.  I don't know why they mentioned $O(n^2)$ as opposed to $O(n)$.


Algorithm to determine two binary expression trees will give the same result based on associative and commutative properties of some operators

Note that if you just want to know if two equations without variables have the same result, then just evaluate them already.  But it's more tricky with variables:

I assume that you are basically just functionally rearranging lists (ie: like Python/JavaScript/Lisp code).  For associative binary operators, it's convenient to make them have n operands to avoid a re-association pattern matching mess.  A sum or product of one operand is a redundant parenthesis.  Because they happen to be commutative, have the sum and product objects consistently sort their operands if you want them to be efficiently comparable (ie: define a canonical form that everything should reduce to).

It is harder if variables are involved though.  The equals sign can be treated as just another binary operator to create new expressions, where you do things like:  a, (a=(b*2)), ((a=(b*2))+6), ((a+6)=(b*2)+6), ((a+6)=(2*b)+6).  At that point, you construct new expressions like:  equate(expr,expr), add(expr,expr), mul(expr, expr), ldistribute(expr,expr), rdistribute(expr,expr), commute(expr), etc.

Some of the rules are obvious like distributing multiplication over addition, or additive or multiplicative cancellation; and usually go in one direction (like automatic differentiation).  But there will be other times where you will need to do a more clever search (like a chess engine), doing things like multiply an expression times 1, and equate it with a new variable divided by itself, etc.  One of the more tricky things in an algorithm for solving is that some operations like division add new logical constraints.  If you construct  div(add(a,b),x), you implicitly construct a logical constraint for x!=0; and you need to work these constraints in so that the search for the solution doesn't generate nonsense.

These kinds of programs are usually written as pattern matching and rewriting, with provisions made to not go in infinite loops.


I think that you are interested in MFC - Multiple Foreground Cosegmentation.
MFC article

Awesome material:
Articulated Motion and Deformable Objects : 5th International Conference, AMDO 2008, Port d'Andratx, Mallorca, Spain, July 9-11, 2008, Proceedings

In advance I warn you, these are not all out of the box working solutions, but with small changes all can do segmentation so if first link is what you have expected treat these below as starting point to work your own way.

Every "one object only in the foreground" can start iterative scheme: find first, cut, colour it with backgroundish color (presumably gray darker then mean luminance of the image), cut next.

When some classifiers are used, or patterns are known it is easier, but when background is complex and you want just regions there are oldschool ways: use Otsu, or modified K-Means clustering, try region growing, edge detection, make decision from colour or shadows.
In the end you will find yourself in situation that there are some components, now it is time to decide which is background (darker; connected with all edges of the image; bigger? Every of those could fail).

Image segmentation is based on some kind of connecting self similar regions, cuts them by edges even follows perspective lines if possible.

Foreground - Background separation is the most of the time asuming that foreground is smaller, better exposed. Very rarely there is perspective reconstruction and from one image it is virtually impossible (for street views we can detect lines and follow to horizon, but other types fail).

Below are additional links. If nothing helped write me a comment and describe more details.

Examples are connected in this paper but it works for separate objects: automatic foreground extraction

Foreground prediction

Must read:
Otsu image segmentation
Region-based
Graph based

When you expect some objects:
Blobs

Sequence of images:
Kalman filter
Background/Foreground


Find the sum of numbers from an array closest to a number, where repetition of the numbers are allowed

This problem is NP-hard by a reduction from partition.
Let $X = \{x_1, \dots, x_n\}$, be an instance of partition and let $2M = \sum_{x \in X} x$ (assume that $M$ is an integer as otherwise the instance is trivial).
Assume that each $x_i$ is positive and let $\ell = \lceil \log 2M \rceil$.

I will now construct some values based on $X$. I will denote a generic value by a tuple $v$ of $n+2$ entries $(v^{*}, v^{(0)}, v^{(1)}, \dots, v^{(n)})$, where all entries $v^{(i)}$, $i=0,\dots,n$ are between $0$ and $2^\ell - 1$.
The tuple $v$ will actually correspond to integer whose binary representation is obtained by encoding $v^{*}$ in binary (using a variable number of bits), each of $v^{(0)}, \dots, v^{(n)}$ using $\ell$-bits, and finally concatenating the resulting bitstrings, in order.
An example of the tuple $v=(5, 2, 7, 9)$ with $\ell = 4$ is as follows:
$$
(\underbrace{101}_{v^*}
\underbrace{0010}_{v^{(0)}}
\underbrace{0111}_{v^{(1)}}
\underbrace{1001}_{v^{(2)}})_2 = (21113)_{10}
$$

Notice that the value obtained in this way has an encoding of polynomial length w.r.t. the length of the encoding of the original partition instance, as long as $v^{(*)}$ is small enough (as will be the case). The sum of two tuples is the tuple whose integer value equals the sum of the integer values of the summands.

Let then $y_i = (1, x_i, 0, \dots, 0, 1, 0, \dots, 0)$, where the second entry set to $1$ is $y_i^{(i)}$.
Similarly, let $z_i = (1, 0, 0, \dots, 0,1,0, \dots, 0)$, where $z_i^{(i)} = 1$.

The instance of the problem in the question consists of the set of numbers $S = \{y_i  : x_i \in X\} \cup \{z_i  :  x_i \in X\}$ and of the target value $T=(n,M,1, \dots, 1)$.

Given a solution $X' \subseteq X$ to the partition problem, it is easy to construct a solution $S' \subseteq S$ for our problem such that $\sum_{x \in S'} x = T$. Simply select $S' = \{ y_i : x_i \in X'\} \cup \{ z_i : x_i \in X \setminus X' \}$ (notice that it suffices for $S'$ to be a set rather than a multi-set).

I will now argue that if a (multi-)set $S' \subseteq S$ such that $\sum_{x \in S'} x = T$ exists, then the partition instance $X$ has answer "yes".
From now on let $S'$ be such a set and notice that, by our choice of $T$, the overall multiplicity of all the elements of $S'$ cannot be larger than $n$ (as otherwise $T^{(*)}$ would be exceeded).

Claim: Let $m(x)$ be multiplicity in $S'$ of $x \in S$.
$\forall i=1,\dots,n$ we have $m(y_i) + m(z_i) = 1$.

Proof:
If $m(y_i) + m(z_i) = 0$ then, since $T^{(i)}=1$, $S'$ must contain at least $2^\ell \ge 2M > n$ elements $y_j$ or $z_j$ such that $j > i$, contradicting $\sum_{x \in S'} m(x) \le n$.

Assume then that $m(y_i) + m(z_i) > 1$, and consider the tuple $h$ corresponding to the sum of exactly 2 copies of $y_i$ and/or $z_i$ in $S'$.
We have $h^{(i)}=2$ and, since $T^{(i)}=1$, we conclude that there must be at least $2^\ell - 2$ other copies of some $y_j$ or $z_j$ for $j \ge i$ in $S'$.
The total multiplicity of the elements in $S'$ is therefore at least $2 + 2^\ell - 2 > n$, a contradiction. $\;\; \square$

Let $X' = \{x_i : y_i \in S' \}$ and call $h = \sum_{x \in S'} x$. Since there can be at most one copy of each $z_i$ in $S'$ (see the above Claim), the only way to affect $h^{(0)}$ is through the values $y_i \in S'$. Since there can be at most one copy of each $y_i$ in $S'$ (see the above Claim), we must have $\sum_{x_i \in X'} x_i = \sum_{y_i \in S'} y_i^{(0)} = h^{(0)} = T^{(0)} = M$.


Show that the Laplace smoothing for bigrams is a valid probability distribution

First, let me rewrite your formula:
$$
\Pr_L[w_j|w_i] = \frac{\#(w_i,w_j)+1}{\#w_i+|\Sigma|}.
$$
The quantity $\#w_i$ should be defined so that $\sum_j \#(w_i,w_j) = \#w_i$ (so we should ignore the final character when calculating $\#w_i$). Therefore
$$
\sum_{w_i \in \Sigma} \Pr_L[w_j|w_i] = \frac{\sum_{w_i \in \Sigma} \#(w_i,w_j) + \sum_{w_i \in \Sigma} 1}{\#w_i + |\Sigma|} = \frac{\#w_i + |\Sigma|}{\#w_i + |\Sigma|} = 1.
$$


You have correctly identified your alphabet, but your verbal description is, indeed,complex.  Your NSA would accept any string with at least 2 as.

There are many ways to describe NSAs. A regular expression or a regular grammar could be appropriate here. If this is for class, I would ask your professor what format he or she prefers.


The alphabet for this language is $\Sigma=\{0,1\}$. We also have that $x_i,y_i,z_i\in\Sigma$. So, notice that
$$\sum_{j=0}^{n-1}x_j2^j$$ is simply the decimal equivalent if we assume that the symbols of $x$ are expressed as a number in binary. Similar can be said for $y$ and $z$.
Using this, one can see that the language is effectively the those strings such that if you take every third symbol and form $x,y,z$, the numerical equivalent adds up.
For this to be true, for every $x_i,y_i$ and carry from the past additions, the corresponding $z_i$ should be the correct symbol. If it were not so, then irrespective of the future symbols, we cannot have $x+y=z$, and the string can never be accepted.
So, at each iteration, the DFA needs to remember the current values of $x_i,y_i$ and the current carry. If the corresponding $z_i$ is correct and the carry is $0$, it can return to the start state and continue, as this is not going to affect future considerations in any way. This is a final state as at any point when the DFA is in this state, the current sets of $x_i$s, $y_i$s, and $z_i$s are such that the string would be accepted.
If the value of $z_i$ is correct but the carry is not $0$, then the DFA goes to a different state corresponding to carry being $1$. This is not a final state as if the carry was $1$ at the end, it would imply that $x+y\ne z$ as $x,y,z$ must have the same number of symbols.
If the value of $z_i$ is incorrect, then the symbol at that "bit" can never be corrected in the future, and the DFA can be sent to a sink state where the string is rejected irrespective of the remaining symbols.
Using the above, the DFA I have drawn (using JFLAP) is as follows:

The first column is when $x_i,y_i,z_i$ have been received. $q_0$ corresponds to a carry of $0$ and is that start and final state. $q_7$ corresponds to a carry of $1$. The second column is the set of states when $x_i$ has been received, and the third is when $y_i$ has been received. Then, when $z_i$ is received, if it matches $z_i=x_i+y_i+\text{carry}$, the DFA goes to state $q_0$ or $q_7$ depending on the carry. Else, it goes to $q_{14}$, which is a sink.


Is (λx.FV(A)) and (λx.FV(B)) β-equivalent?

Free variables have a "meaning" in the sense that two free variables (as opposed to two bound variables) are not $\alpha$-equivalent -- and that's precisely why your first reduction is not correct: We are not allowed to do "free renaming", only bound renaming!
Capture avoiding substitution is defined as

If $x \neq y$ and $y \in FV(N)$ and $x \in FV(P)$, then, where $z \not \in FV(N) \cup FV(P)$:
$(\lambda y.P)[N/x] = \lambda z.(P[z/y][N/x])$

Capture avoiding substitution happens only when a variable occurring free in $N$ is bound by lambda abstraction in the term to substitute ($y \in FV(N)$) and there are actual occurrences of $x$ in $P$ to substitute ($x \neq y$ and $x \in FV(P)$). In that case, we rename the bound variable in the term that undergoes substitution (the function body), i.e. $(\lambda y.P) \rightsquigarrow \lambda z. (P[z/y])$, then perform the actual substitution of $N$ for $x$ in $P'$. We do not rename free variables, and we do not perform renaming in the argument.
In your example, beta-reducing $(λx.λz.y x) y$ means to replace every free occurrence of $x$ in $\lambda z. yx$ by $y$ provided that $y$ is free to substitute. y will not be captured by anything: As you observe, $y$ is free in $\lambda z.yx$, and that's precisely why there is no capturing and thus no capture avoiding to perform, and the substitution can be done directly. Thus the correct reduction is

$\newcommand{\bred}{\triangleright_\beta}
\phantom{\triangleright_\beta} (\lambda x. \lambda z. yx)y\\
\bred (\lambda z.yx)[y/x]\\
= \lambda z. (yx[y/x])\\
= \lambda z. (y[y/x])(x[y/x])\\
= \lambda z. yy$

De Bruijn indexing on this term is vacuous, because there are no pairs of binding and bound variables ($\lambda z$ does not bind any occurrences of $z$, and the two occurrences of $y$ are not bound by any abstraction $\lambda y$).

A case where capture avoiding substitution would be needed is if the argument $y$ were bound in the function body, e.g. if instead of the vacuous abstraction $\lambda z$ there were $\lambda y$:

$(\lambda x. \lambda y. yx)y\\
\bred (\lambda y.yx)[y/x]\\
= \lambda z. (yx[z/y][y/x]) \quad \text{(avoiding catpure of $y$)}\\
= \lambda z. (zx[y/x])\\
= \lambda z. zy$

Re. notation and implementation:
It depends a bit on how you define it, but the way I used it above (which is the approach chosen in e.g. Hindley & Seldin (see below):
When bound renaming has to happen to avoid variable capture, then this is part of the definition of substitution, i.e. the result of $(\lambda y.P)[N/x]$ with $y$ free in $N$ syntactically identical ("$=$", rather than just $\alpha$-equivalent) to $\lambda z.P[z/y][N/x]$.
To express $\alpha$-equivalence in the sense that a pair of terms only differs in their bound variable names, you can write $\equiv_\alpha$.
Alternatively, one could define beta reduction such that substitution can only be performed if no variable conflict occurs, and if it does, one has to prepend a step of $\alpha$-renaming before $\beta$-reducing.
"not $FV(A) \cup FV(B)$" is just the set-theoretic complement relative to the set of all variables, $VAR - (FV(A) \cup FV(B))$. To implement a choice of "the first variable not in $FV(A) \cup FV(B)$" you need to presuppose an ordering of variables such as $x < y < z < x_1 < ... x_n$ and then do something like $min\{x: x \in VAR \land x \not \in FV(A) \land x \not \in FV(B)\}$. The set of free and bound variables is defined by straightforward recursion on the structure of the lambda term.
Furthermore, for a precise notation in the implementation one may want to distinguish between an atomic beta reduction/variable renaming step vs. reducibility/equivalence through a chain of reductions/renamings, as well as $\beta$-reducibility monotonously downwards from $A$ to $B$ as opposed to $\beta$-equivalence by finding a common term both reduce to.
For variables you should use $x, y, z, u, v, w, x_1, x_2, \ldots$; wheras $a, b, c, \ldots$ are more typically understood as constants.
Constants is also what objects and functions interpreted "by context" such as $*, +, sqrt$ would naturally be treated as; their meaning is "fixed from the outside" and you can combine lambda reduction with custom inference steps like $(\lambda x.+xx)(2) \bred +22 =_\mathbb{N} 4$.
You can find the notation I used and all the definitions necessary for rigorously implementing substitution etc. in (amongst others)
J. R. Hindley & J.P. Seldin (2008), Lambda calculus and combinators: an introduction.
Another classic is
H. Barendregt (1992), Lambda calculi with types.


What's the correct algorithm to filter accumulating string concatenations?

Store them in a heap or priority queue, keyed on the size of the message.  This way, if you want the $k$ largest messages, you can keep track of that as each message arrives.  This will require $O(k)$ space to keep track of the $k$ largest messages at each step, and $O(\log k)$ time per message that arrives, so it should be pretty efficient.


What is the "continuity" as a term in computable analysis?

Different people have different views on what the definition of continuity should be, but the way I see it, we should define continuity to be computability relative to some oracle. For example:
Definition: A function $f : \mathbf{X} \to \mathbf{Y}$ is continuous, if there is a computable partial function $F :\subseteq \mathbf{X} \times \mathbb{N}^\mathbb{N} \to \mathbf{Y}$ and some $p \in \mathbb{N}^\mathbb{N}$ such that $f(x) = F(x,p)$.
So the most primitive concept in handling a space is what representation we are using for it, which then yields the notion of computability, and from that we get the notion of continuity.
So far, the definition of continuity seems rather unrelated to continuity from topology, and one may wonder why that term has been chosen. One reason is that we usually use admissible representations, which have the characterization that the functions between them which are continuous in the computable analysis definition are exactly the functions which are continuous in the topological sense.
If we have an admissible representation $\delta : \subseteq \Sigma^\mathbb{N} \to \mathbf{X}$, we get the topology on $\mathbf{X}$ as the final topology along $\delta$, i.e. a set $U \subseteq \mathbf{X}$ is open iff there is a set $W$ of finite words such that $\delta^{-1}(U) = \operatorname{dom}(\delta) \cap \bigcup_{w \in W} w\Sigma^\mathbb{N}$. Matthias Schröder has shown that the topological spaces which have admissible representations are exactly the $T_0$ quotients of countably-based spaces.
Now to slowly come back to the starting point of your question, what prevents us from using the discrete topology on the reals? The reason we cannot do that is that every countably-based space is separable, ie has a (countable) dense sequence. Taking quotients preserves being separable, so every topology associated to a representation is necessarily separable. A discrete space is separable iff it is countable, so we cannot get the discrete topology on the reals.
There is a way to get an admissible representation of $\mathbb{R}$ that makes $\mathbb{Q}$ a discrete subspace (essentially, treat $\mathbb{R}$ as $\mathbb{N}^{*} \cup \mathbb{N}^\mathbb{N}$), but as you have argued in the question, that makes addition uncomputable (and overall, has very little resemblance to the reals as we would want them).
On a side note, that we cannot avoid getting stuck without even recognising it when accidentally trying to divide by $0$ is a significant obstacle if we are trying to do linear algebra with real numbers.
References:
Pieter Collins:
Computable analysis with applications to dynamic systems. Math. Struct. Comput. Sci. 30(2): 173-233 (2020)
Martín Hötzel Escardó:
Synthetic Topology: of Data Types and Classical Spaces. Electron. Notes Theor. Comput. Sci. 87: 21-156 (2004)
Takayuki Kihara, Arno Pauly: Dividing by Zero - How Bad Is It, Really?. MFCS 2016: 58:1-58:14
Arno Pauly: On the topological aspects of the theory of represented spaces. Computability 5(2): 159-180 (2016) arXiv
Matthias Schröder:
Extended admissibility. Theor. Comput. Sci. 284(2): 519-538 (2002)


Finding a function which is a mapping reduction of A to B

The answers are as follows, just functions with input w:

f(w) = 0w
f(w) = 0w
f(w) = w
f(w) = 00

Basically make sure all scenarios which occur in A are mapped to B and that all which are not, do not map to B


How to decompose a unit cube into tetrahedra?


How does BFS guarantee the minimum path for this problem?

BFS (or Breadth-First Search) from its name implies that it will search for the destination along the breadth. That means it looks at all the current possible routes ie nodes connected to the current one and divides itself into all of those. Basically, at every junction, it divides itself and continues down that path until it encounters the destination node.
So effectively, it can be said that it checks for all the paths of length len from the source node starting len from 0 and incrementing it by 1 until it reaches the destination.
Let's say it got to the destination with length 7, now this means that it tried all the paths of length 0, 1, 2 ... 6 but was not able to get to the destination.
So, this means that whenever BFS finds a path, it already tried all paths of length (or cost) lower than the current one but was able to find a complete path that reaches the destination. Which means it always finds the shortest (or cheapest) path.


How do POMDPs and Dynamic Influence Diagrams differ?

I'll quote from the paper "Interactive Dynamic influence diagrams" (DIDs) by Polich and Gmytrasiewicz (AAMAS 2007):

  A dynamic influence diagram is a computational representation of a POMDP.

They continue soon afterward:

  DIDs perform planning using a forward exploration technique known as reachability analysis. This technique explores the possible states of belief an agent may be in in the future, the likelihood of reaching each state of belief, and the expected utility of each belief state. The agent then adopts the plan which maximizes the expected utility. DIDs provide exact solutions for finite horizon POMDP problems, and finite look-ahead approximations for
  POMDPs of infinite horizon.

To me this suggests that DIDs are, as the authors state, one possible representation of a POMDP, to which a specific look-ahead type solution method is related to. As look-ahead is limited to approximate solutions for infinite horizon POMDPs, this also suggests that DIDs can not represent every POMDP.


Covering a graph with non-overlapping cliques

Thus I'm still curious if there are other more efficient approaches to solving the problem.

If you take the complement graph $\overline{G}$, then your problem corresponds to a coloring problem.  Cover by cliques in $G$ is the same as covering by independent set in $\overline{G}$.

The problem is para-NP-hard in the unweighted case and the problem is just hard no matter what you do.

There is an algorithm computing the chromatic number in time $O^*(2^n)$ using exponential space, and in time $O(2.2461^n)$ using polynomial space.

The fastest algorithm I know to get the coloring runs in time $O^*((1+\sqrt[3] 3)^n) = O(2.4423^n)$.

[1] Fomin, F. V., & Kratsch, D. (2010). Exact exponential algorithms. An EATCS Series — Texts in Theoretical Computer Science.  Springer.


Seems like NP cannot equal coNP by the definition of NP

This kind of argument presupposes that the only way to (for example) prove that a SUBSET-SUM instance is not solvable is by going over all subsets and checking that their sum doesn't match. This isn't true — a meet-in-the-middle algorithm works in time $O(\sqrt{2}^n)$ rather than $O(2^n)$, where $n$ is the number of sets.

Furthermore, consider the analog of this question for polynomial space rather than time. In this case it does hold that NPSPACE=coNPSPACE, for the simple reason that PSPACE=NPSPACE.


Regex for strings with even number of 1's and number of 0's divisible by 5

Your last idea is good, but insufficient. Also there is not the right number of zeros. Now let's try to decompose the problem:
Let's consider $L_0=\{1^i01^j01^k01^l01^m01^n,i+j+k+l+m+n \text{ is even}\}$.
Your (corrected) idea was $e_1 = (11)^*0(11)^*0(11)^*0(11)^*0(11)^*0(11)^*$, but this only generate words of $L_0$ where $i, j, k, l, m, n$ are all even. You need now to consider other possibilities. For example, if $j$ and $m$ are odd and the rest are even, we get the regular expression:
$$(11)^*0(11)^*10(11)^*0(11)^*0(11)^*10(11)^*$$
There are a total of $\binom{6}{0} + \binom{6}{2}+\binom{6}{4}+\binom{6}{6} = 32$ expressions to consider all possibilities (choice of an even number of indices that are odd among the 6).
The final regular expression will then be $\left(e_1+e_2+…+e_{32}\right)$.
Now you need to do the same thing with a language $L_1$ containg an odd number of $1$'s, and construct the regular expression for your language with both $L_0$ and $L_1$.
This sure is ugly as hell, but hey, it works! There may be a simpler way to write it, but I'm not so sure.


prove that l={w ∈ {0, 1}*: n0(w) ≠ n1(w)} is a non regular language?

There are two easy proofs that I will let you work out on your own. The first uses the fact that regular languages are closed under complement, the other uses the Myhill–Nerode criterion.

You can also prove that this language is not regular using the pumping lemma, but the proof is a bit tricky. Let $p$ be the pumping length, and consider the word $w = 0^p1^{p!+p} \in L$. The pumping lemma gives us some decomposition $w = xyz$ with $y = 0^i$ for $1 \leq i \leq p$. Then $xy^{1+p!/i}z = 0^{p!+p} 1^{p!+p} \notin L$.


Can you take classical code and compile it to quantum code?

Doubly-controlled NOT gates are universal  with respect to classical functions. Quantum computers can perform doubly-controlled NOTs. So even a quantum computer not allowed to perform fancy operations involving superposition, and not allowed to perform irreversible operations such as measuring or clearing a bit, can perform any classical computation.

For example, a quantum computer can basically directly run the gates making up a VanRentergem addition circuit:

Quantum computers are actually slightly better at reversible computation than classical computers. Classically you sometimes need an extra scratch bit to compute a function, because of permutation parity issues, but quantum shenanigans get that down to zero. Though of course emulating irreversible functions still requires introducing new scratch bits each time.


The difference between a bit and a Qubit

Probably the easiest analogy is to probabilities. If your computer can flip fair coins, you can think of each coin being in state Tails with probability 1/2 and in state Heads with probability half. So it's appropriate to think of a coin not as a bit but as a vector of two elements $(p_T, p_H)$, where $p_T$ is the probability of tails, $p_H$ is the probability of heads and we have that $p_T \geq 0$, $p_H \geq 0$, and $p_T + p_H = 1$. Once we sample a coin its state "collapses" to either tails or heads.

Just about the same happens with qubits. You can also think of quibit as being "in between" two states. It's also easiest to think of qubit not as a bit but as a vector of two elements $(q_0, q_1)$. Now, however, we allo $q_0$ and $q_1$ to be negative, and even further, to be any two complex numbers, as long as $|q_0|^2 + |q_1|^2 = 1$. Just as with sampling coins, once you measure a qubit, it collapses to either $0$ or $1$, and in fact you get $0$ with probability $|q_0|^2$ and $1$ with probability $|q_1|^2$. However, and this is the crucial part, these quantum probabilities can be made to cancel each other because they take negative values; this cannot happen with classical probability. This is the power of qubits.

BTW these complex valued quantities describe amplitudes and are related to the wave-particle duality, i.e. the discovery that particles in fact behave as waves, until you measure them, and then they behave as particles. The cancelation I am talking about is in fact interference between waves. So another answer to your question is that a qubit is not a discrete object that's either in one state or not, it's a wave..until  you measure it.


$(i,j,k)$ is not a specific OPT. It's three variable names that you can use to talk about the key. The question is just asking, "Given all possible three-character OTPs, how many valid English plaintexts are there for the ciphertext CJU?"

In other words, how many different values are there for the triple $(i,j,k)$ such that "CJU" decrypts to an actual English word.