Doubt regarding Chomsky Hierarchy, CFG and CSG

Note that the Chomsky Hierarchy is nowsadays considered as a hierarchy of language families. For each of the levels we both have suitable grammars and automata to generate and accept the languages in the family. Usually there is a relation between the devices for the different levels, but in some cases we have to be careful about the details.

You are right. The given grammar is context-free, but it is not context-sensitive. The reason is that with CSG we have to restrict the possibility for variables to generate the empty string. Technically the reason for this is that the context-sensitive languages are not closed uner erasing (deleting some letters).

So, any CFG that does not have $\varepsilon$-rules is also a CSG. Usually a CSG is not allowed to have $\epsilon$-rules. Of course that would mean that CSL do not contain the empty string. Well, the empty string can be handles separately if we need it. The same is true for, say, CFG in Chomsky normal form. Strict ChNF does not allow the empty string, but that is not a real restriction. Either we deal with the language without $\varepsilon$, or we have some complicated formulation that will allow generating $\varepsilon$ only in the first step of the derivation.


The set $1^*+0^*$ is composed of two parts: $1^*$ and $0^*$. The first part, $1^*$, is all strings composed entirely of $1$s. The second part, $0^*$, is all strings composed entirely of $0$s. In contrast, $(1+0)^*$ is all strings composed of $0$s and $1$s. Can you now think of a string in $(1+0)^*$ but not in $1^*+0^*$?


Time complexity to find out the number of ways to parenthesize N matrices

These are called Catalan numbers, and the term $\binom{2N}{N}$ is called a central binomial coefficient.

There are several formulas for these numbers which can be used to compute them efficiently, such as the one you present, or

$$C_n = \prod_{k=2}^n \frac{n+k}{k}$$

The problem with writing down the time complexity for computing these numbers is that the Catalan numbers grow exponentially—the number of bits in the output is roughly proportional to the input index. Therefore, the exact time complexity for evaluating these numbers from such a formula is going to depend significantly on the time complexity of your arithmetic operations, especially your choice of multiplication algorithm for large numbers.


Rounding of $2-10^{20}$ in IEEE double precision

Determine the binary exponent of $10^{20}$. From that determine the value of the lowest bit of the mantissa of $10^{20}$. Then ask yourself: How large does a number x have to be at least so that round (x-$10^{20}$) is not $-10^{20}$?


One address addresses one byte. Using 16 bits, you can write 65536 addresses (from 0 to 65535, that's 65536 different addresses), and address 65536 bytes. 65536 bytes is 64kB. In computer science, b is bit, B is byte. The byte is the smallest amount of memory you can address. The question "what is k ?". k is kilo, in international system of units, a kilo unit is 1000 units, but, when dealing with memory, a kilo unit is 2^10=1024 units, (except when dealing with hard drives, for marketing reasons).

64kbps is 64 kilo bits per second. It is a transfer rate, not an amount of memory.

"What is a segment ?" isn't a precise question, segment is a very generic word used in many contexts. I expect that the 8086 segments are accurate in your context, even if it's some 24-bit addresses with 16-bit CPU instead of 16-bit addresses with 8-bit CPU.


Can it be decided whether there exists a string accepted by a given NFA at least k ways?

The idea is to use a construction very similar to the power set construction. In the usual power set construction, each NFA state has two possibilities: unreachable and reachable. In our case, each NFA state has three possibilities: unreachable, uniquely reachable, and multiply reachable. It is straightforward to carry out the construction, and I will not spell it out here. A state in the DFA is accepting if either it contains a multiply reachable NFA accepting state, or it contains at least two uniquely reachable NFA accepting states. There is a word accepted by the NFA using more than one path if the language of the new DFA is not empty. In fact, the language accepted by the DFA consists of all words accepted by more than one path.

Using the same idea, we can compute the language of words accepted by the NFA using exactly, at most, or at least $k$ paths.


Why are so many internet protocols text-based?

When the world was younger, and computers weren't all glorified PCs, word sizes varied (a DEC 2020 we had around here had 36 bit words), format of binary data was a contentious issue (big endian vs little endian, and even weirder orders of bits were reasonably common). There was little consensus on character size/encoding (ASCII, EBCDIC were the main contenders, our DEC had 5/6/7/8 bits/character encodings). ARPAnet (the Internet predecessor) was designed to connect machines of any description. The common denominator was (and still is) text. You could be reasonably certain that 7-bit encoded text wouldn't get mangled by the underlying means to ship data around (until quite recently, sending email in some 8-bit encoding carried a guarantee that the recipient would get mutilated messages, serial lines were normally configured as 7-bit with one bit parity).

If you rummage around in e.g. the telnet or FTP protocol descriptions (the first Internet protocols, the network idea then was to connect remotely to a "supercomputer", and shuffle files to and fro), you see that the connection includes negotiating lots of details we take as uniform,

Yes, binary would be (a bit) more efficient. But machines and memories (and also networks) have grown enormously, so the bit scrimping of yore is a thing of the past (mostly). And nobody in their right mind will suggest ripping out all existing protocols to replace them with binary ones. Besides, text protocols offer a very useful debugging technique. Today I never install the telnet server (better use the encrypted SSH protocol for remote connections), but have to telnet client handy to "talk" to some errant server to figure out snags. Today you'd probably use netcat or ncat for futzing around...


Shortest even path that goes through a vertex

Your remark is true: there might be no simple even path from $s$ to $t$, an even path perhaps includes a cycle of odd length.

The shortest path from $s$ to $t$ via $d$ is the shortest path from $s$ to $d$ plus the shortest path from there to $t$.

To compute even length paths you might consider turning the graph into a bipartite graph using two copies of itself. Double $V$ by adding a copy $V'$. Now duplicate every edge $(x,y)$ into $(x,y')$  and $(x',y)$, where the primes indicate copies in $V'$.
Now the shortest path from $s$ to $t$ will be of even length. (And all paths of even length in the original graph are 'represented' in the new graph.)

Problem: the intermediate node $d$ might be $d'$, its copy in $V'$. Your turn to connect the two requirements 'via $d$' and 'even length'.


One of the main tasks in machine learning is classification. For example, given an image of a digit, which digit it represents? The desired algorithm assigns a label – in this case, a digit, to each sample – in this case, an image.
Supervised machine learning algorithms train classification algorithms using labelled data. The labels in the training set are typically manually generated by humans, who sometimes mislabel data. This is known as label noise. Label noise is usually the result of honest mistakes, but sometimes occurs out of malice. A third possibility is that some samples are genuinely hard to classify. Yet another possibility is that some labels are correct, but for various reasons we do not condone them.
Label noise is an issue since most machine learning models are trained on labelled data, and their performance is closely tied to the quality of the data they are trained on.


Amortized value of dequeue with potential function

The intuition is following: the "bad" case when you have to do expensive operation is when one of the stacks is empty, and the other one is big. You need to compensate its real cost with a potential decrease.  Thus, you can define potential function as $2 \lvert \operatorname{size}(head) - \operatorname{size}(tail) \rvert$.

(For simplicity I represent hard pop as combination of two operations - rearrangement of elements using the third stack and a light pop)

Before the rearrangement, one of the stacks is empty, and other one contains $k$ elements, and right after both contains $\frac{k}{2}$. Therefore, the potential decreases on $2k$ and amortized cost of rearrangement is

$(k + \frac{k}{2} + \frac{k}{2}) + (-2k) = 0 = O(1)$

The amortized costs of light pop and push are clearly $O(1)$ as well as potential increases on $2$ at most.


Monotone boolean satisfiability with at most k 1s is NP-Complete

Let $L'$ be a restriction of $L$, say $L' = L \cap D$. Here $D$ is a restriction on the inputs such as "all clauses have two literals each".

Suppose that $L'$ is NP-hard. Then for every language $M$ in NP, there is a polytime reduction $\varphi$ from $M$ to $L'$ such that $x \in M$ iff $\varphi(x) \in L'$. If $\varphi(x) \in D$ for all $x$, then $\varphi(x) \in L'$ iff $\varphi(x) \in L$, and so $\varphi$ is also a reduction from $M$ to $L$.

Usually NP-hardness proofs go by reduction from some specific NP-complete problem $M$. If the polytime reduction $\varphi$ from $M$ to $L'$ showing that $L'$ is NP-hard satisfies the property $\varphi(x) \in D$ for all $x$ (in other words, its range is [contained in] $D$), then the reasoning in the preceding paragraph shows that $\varphi$ also proves that $L$ itself is NP-hard.

For example, in your case $L$ is the set of pairs $\langle \psi,k \rangle$ such that $\psi$ is a monotone Boolean formula that can be satisfies by setting at most $k$ of the literals to TRUE; $D$ is the set of pairs $\langle \psi,k \rangle$ such that $\psi$ is a monotone 2CNF; and $L' = L \cap D$ is the set of pairs $\langle \psi,k \rangle$ such that $\psi$ is a monotone 2CNF that can be satisfied by setting at most $k$ of the literals to TRUE. Any reduction $\varphi$ showing that $L'$ is NP-complete whose range is $D$ also shows that $L$ is NP-complete.

To check that you understand the argument, try to see what goes wrong when we take $L'$ to be, say, 3SAT, and $L$ to be the language of all 3CNFs.

Finally, here is a trick that you can use to emulate SAT in your setting. Suppose that some CNF $\varphi$ has variables $x_1,\ldots,x_n$, some of them possibly appearing negated. Consider $\psi = \varphi' \land (x_1 \lor y_1) \land \cdots \land (x_n \lor y_n)$, where $\varphi'$ results from replacing $\lnot x_i$ by $y_i$. Then $\varphi$ is satisfiable iff $\psi$ is satisfiable by a truth assignment in which at most (or exactly) $n$ variables are TRUE.


I found out that such a thing is called anti-unification. This problem was addressed by Plotkin and Reynolds. Here is a brief overview.


What exactly (and precisely) is "offset"?

An offset is a difference between two indices, usually memory locations or array indices.

For example, suppose that you have an array $A$ in which each element occupies $x$ bytes. Suppose also that the address of $A$ is $M$. Then the address of the $i$th element (counting from zero) is $M + i \cdot x$. Here $i \cdot x$ is the offset. It's the difference between the address of the $i$th element and the address of the array (which is the address of the zeroth element).


The language you describe is regular (because it's finite), so this can be really straight forward.

You could simple write a 1 and advance to the next state. Create 7 states, one state for each 1.

Consider input\output/direction the syntax for "if input is on the tape write output and move in direction"


Can one build a "mechanical" universal Turing machine?

Sure. Electricity is unrelated to the model of computation.
The only thing you can't actually build is the infinite tape, for obvious reasons. In this sense, anything that can be built is essentially equivalent to a deterministic finite automaton.
Here's a Turing Machine made of wood:
https://www.youtube.com/watch?v=vo8izCKHiF0&ab_channel=RichardRidel


It's not context free for the same reason that $L' = \{w w \mid w \in \Sigma^*\}$ is not context free, and the proof below is a simple adaption of the standard proof for the language $L'$, using the pumping lemma:
Choose the string $0^p1^p1^p0^p0^p1^p1^p0^p$, (which is $\omega \omega^r \omega \omega^r$ where $\omega = 0^p 1^p$). [Note 1] Now any $vwx$ whose length is no greater than $p$ is either entirely within the first half of the string, entirely within the second half of the string, or entirely within the central span of $0^{2p}$. Repeating $v$ and $x$ 0 times -- that is, changing $vwx$ to $w$ -- must make the first half of the string different from the second half, either because only one of the halves is altered, or because changing the suffix of one half and the prefix of the other half renders the two halves distinct. So the result is not in $L$.
Since for any $p$, we can find a string which cannot be pumped, we can conclude that there is no pumping length $p$ for the language. That contradicts the pumping lemma, which states that every context-free language has a pumping length. So the language is not context-free.

You can't “take the first $ww^r$ as $v$” because of the restriction that the length of $vwx$ is no greater than the pumping length $p$. So, whatever $p$ is (if it exists) there is some $ww^r$ which is longer, and for the corresponding string $ww^rww^r$ in $L$, $v$ cannot be $ww^r$.

Notes:

I could have chosen a shorter string, such as $\omega = 0^m1^n$ where $m>0, n>0, 4mn>=p$. But there are no prizes for parsimony here; the string I chose makes the proof less verbose.


"Virtualization" is a broad term that means abstracting away details of the device, and providing a more generic/abstract/higher-level interface or view of the device.  Sometimes it involves pretending that you have a simpler virtual device (with simple commands) instead of the complex physical peripheral you actually have (with its messy interface).

See, e.g., https://en.wikipedia.org/wiki/Storage_virtualization, https://en.wikipedia.org/wiki/I/O_virtualization, https://en.wikipedia.org/wiki/Virtualization, https://en.wikipedia.org/wiki/Virtual_file_system, https://en.wikipedia.org/wiki/Virtual_disk, https://en.wikipedia.org/wiki/Data_virtualization.


Why is a sequence of n Push, Pop, Multipop operations O(n²)?

First, let me comment on 2 misconceptions I see in your question:

Landau notation ('Big $O$ notation') does not exclusively refer to running times, we can use it to describe any function we wish.
The fact that the worst case running time is $O(n^2)$ doesn't mean the running time isn't also $O(n)$.

The second part comes close to the point of this part in the book. The authors first show that a (crude) analysis of executing the multi-pop operation $n$ times: worst case of a single multi-pop is $O(n)$, we pop $n$ times, so we spend at most $O(n^2)$.

However, do all of our $n$ multi-pop operations require $O(n)$ time? The authors continue to show that using the aggregate analysis that this isn't the case, by which they obtain a sharper bound of $O(n)$ for $n$ multi-pop operations.

So, in this section, the authors show the utility of aggregate analysis by the multi-pop example.

As for the part labeled as 'question': yes, the total running time of all $n$ operations is $O(n)$, as the book describes in the next section:

  We can pop each object from the stack at most once for each time we have pushed it onto the stack. Therefore, the number of times that POP can be called on a nonempty stack, including calls within MULTIPOP , is at most the number of PUSH operations, which is at most $n$


What are examples of applications of the tree decomposition of a graph?

An example of an application of the junction tree (or tree decomposition) of graph is described in the paper Junction Tree Variational Autoencoder for Molecular Graph Generation (2019), by Wengong Jin, Regina Barzilay and Tommi Jaakkola.


What combination of data structures efficiently stores discrete Bayesian networks?

The "best" data structure probably depends on what particular problem you're trying to solve with it. Here's one approach that I've seen (and have used myself), which simply stores all the information and leaves it up to the algorithm what to do with it.

First you index the nodes by unique integers, 0 through n-1. Then you simply store, for each node, the list of its parents as an array of integers --- in C++, for instance, you could have a std::vector<std::vector<int> >: first vector over nodes, second vector lists the respective parents). That captures the entire DAG structure.
Furthermore, since each node has exactly one conditional probability table associated with it, you could index those with the same integer IDs. For each probability table you need to store its scope, i.e. the set of random variables its defined over. Secondly you'd probably have one large list of floating point numbers that contains the actual conditional probabilities (and you'll want to make sure you get the indexing right). To give a C++ example again, something like this could do:

struct CondProbTable {
    std::vector<int> scope;    // list of random variables the CPT is defined over
    std::vector<double> table; // appropriately sized and indexed table of
                               // conditional probabilities
};

With that, you could use a std::vector<CondProbTable> to store all your CPTs.

Again, this basically only stores the Bayes net, it does not assume anything about what you want to do with it. Including the CPT scope in CondProbTable is somewhat redundant, since it could be inferred from the list of parent nodes described under point 1.


Why are the total functions not enumerable?

Because of diagonalization. If $(f_e: e \in \mathbb{N})$ was a computable enumeration of all total computable functions from $\mathbb{N}$ to $\mathbb{N}$, such that every $f_e$ was total, then $g(i) = f_i(i)+ 1$ would also be a total computable function, but it would not be in the enumeration. That would contradict the assumptions about the sequence. Thus no computable enumeration of functions can consist of exactly the total computable functions.

Suppose we think of a universal computable function $h(e,i)$, where "universal" means $h$ is a computable binary function and that for every total computable unary function $f(n)$ there is some $e$ such that $f(i) = h(e,i)$ for all $i$. Then there must also be some $e$ such that $g(n) = h(e,n)$ is not a total function, because of the previous paragraph. Otherwise $h$ would give a computable enumeration of total computable unary functions that includes all the total computable unary functions.

Thus the requirement that every function is a system of functions is total is incompatible with the existence of a universal function in that system. For some weak systems, such as the primitive recursive functions, every function is total but there are not universal functions. Stronger systems that have universal functions, such as Turing computability, simply must have partial functions in order to allow the universal function to exist.


Probability of winning a turn-based game with a random element

Let us denote by $\Pr(w, b)$ the probability of P2 winning given its their turn and there are $w$ white stones and $b$ black stones remaining and similarly we write $\overline\Pr(w, b)$ for the probability of P2 winning given it is P1's turn.
From the rules of the game we get that any of the following cases can occur in P2's turn (assuming that enough stones are left):

White is drawn and P2 loses. This happens with probability $w / (w + b)$.
Black is drawn and a white stone vanishes. The probability for this is $b / (w + b) \cdot w / (w + b - 1)$.
Black is drawn and a black stone vanishes. We find the probability for this to be $b / (w + b) \cdot (b - 1) / ( w + b - 1)$.

If it is P1's turn to play we find similar cases:

White is drawn and P2 wins. This happens with probability $w / (w + b)$.
Black is drawn and a white stone vanishes. The probability for this is $b / (w + b) \cdot w / (w + b - 1)$.
Black is drawn and a black stone vanishes. We find the probability for this to be $b / (w + b) \cdot (b - 1) / ( w + b - 1)$.

We can now factor $\Pr$ and $\overline\Pr$ using our case distinctions and some simple probability theory:
$$
\begin{align*}
\Pr(w, b) &= \Pr(\text{Case 1.2}) \cdot \overline\Pr(w - 1, b - 1) + \Pr(\text{Case 1.3}) \cdot \overline\Pr(w, b - 2), \\
\overline\Pr(w, b) &= \Pr(\text{Case 2.1}) + \Pr(\text{Case 2.2}) \cdot\Pr(w - 1, b - 1) + \Pr(\text{Case 2.3}) \cdot \Pr(w, b - 2)
\end{align*}
$$
Note that we can combine these 2 equations to find a recursive formula for $\Pr$ (which I will not type out here for brevity).
Coupling these with the initial values $\Pr(w, b)$ where $w + b \leq 4$ (which can be precomputed) will give us an algorithmic way to find the desired probability.


Dynamic programming algorithms with log in the run-time

One natural example is finding the longest increasing subsequence of a sequence of $n$ numbers. Candidate subsequences can be linked in the input sequence. This is a fairly common exercise, and works for other type of subsequences, too. It is actually the exercise 15.4-6 in the 3rd edition of the Cormen et al. book too. For an algorithm, see Section 2.2 in these notes.


Implementing Queue operations in $\Theta(1)$

The problem can be solved by keeping two deques $Q_1$ and $Q_2$ (implemented, e.g., using doubly linked lists) with the invariant that $Q_1$ always contains the first $\lceil n/2 \rceil$ elements of the queue.

The operations are implemented as follows:

push($x$): push $x$ at the beginning of $Q_1$. If the invariant is violated, then pop the last element $y$ from the end of $Q_1$ and push $y$ at the front of $Q_2$.
get(): return the element at the beginning of $Q_1$.
pop(): pop the the element at the beginning of $Q_1$. If the invariant is violated then pop the first element $y$ from the beginning of $Q_2$ and push $y$ at the back of $Q_1$.
getMiddle(): return the element at the end of $Q_1$.
popMiddle(): pop the element at the end of $Q_1$. If the invariant is violated then pop the first element $y$ from the beginning of $Q_2$ and push $y$ at the back of $Q_1$.


How many size $s$ circuits from $\{0, 1\}^n \to \{0, 1\}$ are there?

Hint: Each of the $s$ gates is connected to two other gates or inputs, for a total of $(s+n)^2$ possibilities. This gives a rough upper bound which isn't tight, but is good enough for many purposes, for example to show that some functions require circuits of size $\Omega(2^n/n)$. See Steurer's notes, for example.


Does the heap property in the definition of binary heaps apply recursively?

I would think that most people would just say that the heap property applies only to a vertex and its immediate children, because it's a sufficient definition to maintain the "recursive" heap property everywhere.  It's a cleaner way to think about it (you only need to check O(1) objects per vertex to verify that a tree is a heap, as opposed to O(n) per vertex).

I don't know if there is exactly a consensus on this, and perhaps some other people think differently.


How to prevent the optimization algorithm from just shrinking the image?

I doubt your question can be answered in any detail without knowing more about what you're trying to achieve with these patterns.  The general answer to "my scoring function rewards something I don't want" is either to fix the scoring function or to add a penalty to counteract it, but I'm sure you were already aware of that.

Depending the optimization method you're using, you could possibly also try biasing your sample generation method away from local optima in the unwanted part of the parameter space, but that's generally only effective if there's some other, better local optimum available elsewhere for the process to converge to instead.  If the unwanted local optimum is actually the global optimum for your scoring function, then any decent optimizer will sooner or later find its way there.  If that's the case, you really do just need to find a way to fix your scoring.

Anyway, since you say in the comments that smaller patterns are objectively better in some sense, I assume they must also have some property that makes them objectively worse in some other way. You might want to think about what exactly that property is, and try to penalize that.


Operation of the Ford–Fulkerson algorithm given an almost maximum flow

You are interpreting the question too literally. The question claims that only one augmentation step will be performed. In your example, we augment $f^*$ by pushing one more unit of flow, and then we reach the maximum flow of the updated network.


Why is the unary representation of a number exponentially larger than a base k representation of it?

The base $k$ representation of the number $n$ takes $\log_{k}n$ bits, whereas the unary representation takes $n$, and of course $n = k^{\log_{k}n}$

The gap is more apparent with larger numbers, if we take our normal base 10 system, then writing 1000 takes 4 decimal digits, but writing it in unary takes 1000 ones.


Call by value-result vs. call by reference?

EDIT:
An addendum: if you want to "simulate" call by value-result in Pascal (or in another language that supports only call by reference); you can use this trick:

procedure p(var x, y : Integer); // simulates call by value-result
var
  xtmp, ytmp : Integer;

  procedure p_hidden(var x, y : Integer); // nested "hidden" procedure
  begin
  ... YOUR ORIGINAL CODE HERE ...
  end;

begin
  xtmp := x; ytmp := y; // use auxiliary variables
  p_hidden(xtmp,ytmp);  // call by ref the nested procedure
  x := xtmp; y := ytmp; // copy values before return
end;

A simple method to "visualize" what is happening, is "inserting" the procedure in the point where it is called:

CALL BY REFERENCE:

a := 1; b := 2;
p(a, b)
//// procedure p (var x, y : integer);
//// x is the same as a, y is the same as b
//// begin
  a := a + 2 ;  // a = 3
  a := a * b ;  // a = 3 * 2 = 6
  a := a + 1    // a = a + 1 = 7
//// end;
writeln (a)     // prints 7

CALL BY VALUE-RESULT:

a := 1; b := 2;
p(a, b)
//// procedure p (valres x, y : integer); // by value result
//// x is the same as a, y is the same as b like in a by reference call
  xt := a; yt := b;  // xt and yt are two "new" variables
  //// begin
  xt := xt + 2 ;  // xt = 3
  a := xt * yt ;  // a = 3 * 2 = 6
  xt := xt + 1    // xt = 3 + 1 = 4
//// end;
//// the values of xt and yt are copied back to a and b (x and y) before return
  a := xt;       // a = 4
  b := yt;       // b = 2
writeln (a)      // prints 4


In instructions pipelining, why does register read/write take up only half clock cycle?

By using different phases of a clock cycle for register write and register read, the number of register file ports can be reduced. (This can reduce area and latency.) A two-read and one-write instruction would otherwise require three register file ports (or introduce a structural hazard); by using different phases of the cycle one port can be used for both read and write. This can also facilitate reading from the register file in the same cycle as the value is written, which reduces the number of results that must be managed through the forwarding network.

The fourth instruction (add $14, $2, $2) does not have a data hazard even without forwarding.


Keeping a binary search tree by splitting nodes (like a B-Tree)

1-2 Brother Trees, as in "Purely Functional 1-2 Brother Trees" by Ralf Hinze in some way allow splitting a node. Like in 2-4 trees where nodes have 2 to 4 children, in 1-2 brother trees, nodes have 1 to 2 children.

The advantages are a bit hand-wavey: it is sometimes faster, and sometimes simpler, and sometimes uses less space.


If I understand the question correctly, you are asking why are we bounding the number of configurations, rather than checking for a repeating configuration?

Well, clearly these are equivalent in the sense that in both ways you will detect a repeating configuration.

In the first method, we use the pigeonhole principle, and we say that if we passed a certain number of configurations, then there must be a repetition, since in an LBA the number of configurations is bounded (after fixing the input). In order to detect this, we must keep a counter of the number of configurations we passed. The advantage of this method is that keeping the counter is simple (it takes linear space). The disadvantage is that the loop may have occurred early in the run, and we will only detect it late (after an exponential number of steps).

In the second method, we need to track the configurations we have seen so far, and compare every new configuration to all the configurations we have already seen. The advantage is clear- we will detect the loop immediately when it is caused. But the disadvantage is huge - we need to track all the configurations - this may take exponential space, and in every step we need to compare all the configurations to the current one.

Essentially, the first method solves $A$ in PSPACE, whereas the second solves it in EXPSPACE, so we usually take the first.


Practical communication example for a data rate scenario

4kHz bandwidth and 20dB SNR is telephone communication.
2.4GHz with 64 signaling levels is WiFi with 64QAM if I understood correctly. In that case bitrate is 6 * baud.


Input size of 3-SAT when analyzing complexity

At the most basic level, the size of the input is the length of the string that encodes the input given to the Turing Machine - i.e. the number of cells it takes up on the tape under the chosen encoding scheme.

In practice though, we often measure the size of the input via proxy measurements. So for problems like 3-SAT, we might choose the number of variables or the number of clauses as a proxy for the size of the input. Another example is for many graph based problem the number of vertices is chosen as a proxy for the size of the input, even though the length of the encoding of a graph may be something more like $O(|V|^{2}\log|V|)$. Note that this is polynomial in $|V|$, so when we are considering polynomial time algorithms or reductions, the polynomial factor between the proxy and the actual size poses no problem.


Algorithm for shortest continuous line to join N points

Turns out what I'm looking for is the Travelling salesman problem.


How does a two-way pushdown automaton work?

A two-way PDA can accept the canonical context-sensitive language $\{0^{n}1^{n}2^{n} | n \geq 1\}$. Such an automaton could work by checking whether the largest prefix of the form $0^{i}1^{j}$ had $i = j$, using the stack, after which it could empty the stack, and check whether the largest suffix of the form $1^{j}2^{k}$ had $j=k$, again using the stack. So $CFL \subsetneq L(2PDA)$.

In more detail, the 2-way PDA would read from left to right as many 0 symbols as it finds, pushing a 0 onto the stack for each 0 it reads on the input tape. If it reads any 0 symbols and finds a 2 symbol before finding a 1, it crashes. When it gets to a 1, it changes state, and begins reading all the 1 symbols, until it comes to a 2. If it reads a 0 symbol while doing this, it crashes. It pops a 0 symbol from the stack for each 1 it reads on the input tape. If, when it reaches the first 2, the stack is empty, the PDA moves the tape head to the end of the input tape. Otherwise, it crashes. If it encounters any 0s or 1s, it crashes. It then reads the input tape left to right, pushing a 2 for each 2 it reads on the input tape. When it gets to a 1, it switches states and begins reading 1s and popping 2s. If, when it gets to a 0, the stack is empty, the string is accepted.

The machine would crash if the input string weren't a string of 0s, followed by 1s, followed by 2s; and it would have crashed if the longest prefix of 0s and 1s weren't in the canonical CFL $\{0^{n}1^{n}\}$; and it would have crashed if the longest suffix of 1s and 2s weren't in the canonical CFL $\{1^{n}2^{n}\}$. In this case, the ability to rewind the tape allows you to accept languages which are the intersection of CFLs, by essentially stringing PDAs together, and rewinding the tape in between.

Therefore, the languages accepted by two-way PDAs are trivially closed under intersection, a property not shared by languages accepted by regular PDAs.


How to show working for summing of Big O notation

Summand inside sum is not depend on summation index, then pull it out and you have n−1 before log.


Monotone Frameworks: Transfer functions for flow edges instead of labels

Your formulation is not stated in the way I typically think of it.  Traditionally rather than thinking of looking for a fixed point at each node, we're looking for a solution to a system of simultaneous equations:

$$ x_b = F_b \left( \bigsqcup_{p \in \mathtt{pred}[b]}x_p \right) \; \mathrm{for\:all\:nodes}\:b $$

If $F_b$ has the distributive property over $\sqcup$ then you can simply rewrite this as

$$ x_b = \bigsqcup_{p \in \mathtt{pred}[b]} F_b(x_p) \; \mathrm{for\:all\:nodes}\:b $$

and since you have a function evaluation for every edge $p \rightarrow b$ you might as well just rewrite it as

$$ x_b = \bigsqcup_{p \in \mathtt{pred}[b]} F_{p \rightarrow b}(x_p) \; \mathrm{for\:all\:nodes}\:b $$

If you don't like that handwaving, then here's some more: think of it as taking $F_b$ for every node with one predecessor ($p$) and pushing $F_b$ onto the edge making it $F_{p \rightarrow b}$.  For nodes $b$ with more than one predecessor split them into two nodes, $b$ and $b'$.  The predecessors of $b$ are still the same, then there's an edge $b \rightarrow b'$ and then the successors of the original $b$ become the successors of $b$.  Now the original label $F_b$ becomes $F_{b\rightarrow b'}$.  The join operation still happens on the nodes.

Note that while transfer functions are associated with edges, data flow facts are still associated with nodes.  So the worklist algorithm doesn't really change.  Actually, with the normal (transfer functions on nodes) formulation, the worklist algorithm is really a worklist of edges, not nodes, so nothing changes.  (For an example of this take a look at these slides that came up when I googled for "dominance frontier".  http://www.seas.harvard.edu/courses/cs252/2011sp/slides/Lec04-SSA.pdf.  They give the worklist algorithm on page 7, and it's based on edges.)

A paper using the edge formulation is:

  G. Ramalingam: Data Flow Frequency Analysis. PLDI 1996: 267-277.

(I haven't read the paper beyond the first couple of pages to see that they were using the edge formulation, it's what came up after a bit of Googling.)

I wasn't familiar with the edge transfer function approach until you asked this question.  But I also know of at least two cases where it is important to take edges into account.

The first is when dealing with (post)dominance frontiers.  The natural definition of the dominance frontier of a node is a set of edges, but the original (more complicated) formulation was in terms of nodes.  See for example the (brief) discussion of this in

  Pingali, Keshav; Bilardi, Gianfranco: Optimal Control Dependence Computation and the Roman Chariots Problem, ACM ToPLaS, 19(3):462-491, 1997.

Another example is in the classic

  Knoop, J; Rüthing, O; Steffen, B: Lazy Code Motion, PLDI, 1992.

In Lazy Code Motion you sometimes need to move computations onto edges, but in the original formulation in the paper they were trying to move those computations to different nodes, which gave them trouble with branch nodes that target join nodes.  They called these critical edges and had to add a node along the edge.  This is explained in the following lecture notes by Cooper and Torczon:
https://www.cs.utexas.edu/~pingali/CS380C/2013/lectures/LazyCodeMotion.pdf


How does this non-deterministic algorithm to find if a Hamiltonian path exists work?

There's a couple of bits of information that are key to making this make sense:

Each $p_{i}$ should be a label for a vertex in $G$. Typically $p_{i} \in [1,x]$, but it's not compulsory that you have to label the vertices from 1 to $x$. So the first step is effectively producing a putative list of vertices that could be a path. The rest just checks that it is actually a path (a hence why $(p_{i},p_{i+1})$ could be an edge).
The list is not random. It is selected non-deterministically. This is most definitely not the same as randomly selected. Non-determinism is a special theoretical property where a non-deterministic machine can "guess" a correct answer if it exists, however correct also has a special meaning, in that it selects an answer that will lead to an accepting state if such an answer exists. This may not be the right answer, just one that will make the Turing Machine say Yes - so we still have to check it.

So the algorithm guesses really cleverly a list (in fact an ordering) of all the vertices of the graph, and then checks that it actually makes a Hamiltonian Path from $s$ to $n$.


MST: Prim's algorithm complexity, why not $O(EV \lg V)$?

The complexity is derived as follows. The initialization phase costs $O(V)$. The $while$ loop is executed $\left| V \right|$ times. The $for$ loop nested within the $while$ loop is executed $degree(u)$ times. Finally, the handshaking lemma implies that there are $\Theta(E)$ implicit DECREASE-KEY’s. Therefore, the complexity is: $\Theta(V)* T_{EXTRACT-MIN} + \Theta(E) * T_{DECREASE-KEY}$.

The actual complexity depends on the data structure actually used in the algorithm.
Using an array, $T_{EXTRACT-MIN} = O(V), T_{DECREASE-KEY} = O(1)$, complexity is $O(V^2)$ in the worst case.

Using a binary heap, $T_{EXTRACT-MIN} = O(\log V), T_{DECREASE-KEY} = O(\log V)$, complexity is $O(E \log V)$ in the worst case. Here is why: since the graph is connected, then $\left| E \right| \ge \left| V \right| - 1$, and $E$ is at most $V^2$ (worst case, for a dense graph) . Probably, you missed this point.

Using a Fibonacci Heap,  $T_{EXTRACT-MIN} = O(\log V)$ amortized, $T_{DECREASE-KEY} = O(1)$ amortized, complexity is $O(E + V \log V)$ in the worst case.


This is a nice exercise.  I'll give you a series of hints.  Click on each hint only after you've spent a good amount of time thinking on the previous one.  You'll get the most value by solving this on your own.

Hint #1:

   Add extra variables.

Hint #2:

   Use the Tseitin transform.  Review to convert CircuitSAT to SAT.

Hint #3:

   Introduce a boolean variable $x_v$ for each node $v$ in the BDD.

Hint #4:

   The idea is that $x_v$ should be true iff the path you follow goes through $x_v$.  Can you write clauses to ensure all of this?


It's much better to understand what this marking means. Rather than just follow an algorithm blindly, it's preferable to understand what's going on.

Let us say that two states $q_1,q_2$ are equivalent if $\delta(q_1,w) \in F$ iff  $\delta(q_2,w) \in F$ for any word $w$. The simplest case in which two states are inequivalent is when $q_1 \in F$ but $q_2 \notin F$ (or vice versa). When this happens, we can mark this pair of states as an inequivalent pair of states. This is what happens in Step 2.

In Step 3, we make the following observation. Suppose that $q_1,q_2$ are inequivalent, and that $\delta(r_1,\sigma) = q_1$, $\delta(r_2,\sigma) = q_2$. Then $r_1,r_2$ are also inequivalent (why?). Accordingly, if $r_1,r_2$ is an unmarked pair (not known to be inequivalent) and $\delta(r_1,\sigma),\delta(r_2,\sigma)$ (known to be inequivalent) then we can mark $r_1,r_2$ as inequivalent as well.

You can show inductively that at the end of Step 3, a pair of states is marked if and only if the two states are inequivalent. Therefore we can merge any pair of unmarked states, obtaining in Step 4 a minimal DFA (again, there is something to prove here).


Why do people insist to use the term "multilayer perceptron" instead of "multilayer perceptron network"?

Personally, I've seen "multilayer neural network" used more commonly than "multilayer perceptron".  If you like the former term better, use it.

That said: multilayer perceptron is an accepted term of art.  Your criticism is not unreasonable, but it is what it is.  Language exists to help us communicate... so pick terms that will help you communicate your intended meaning to your intended audience as effectively as possible.

If it helps you come to some kind of acceptance for this usage, you can think of "multilayer perceptron" as a single term that has a particular definition: don't think of "multilayer" as an adjective modifying "perceptron", but thik of "multilayer perceptron" is a single atomic phrase that has a particular definition.  For example, some mathematics textbooks define the term "ring" in a way such that a "commutative ring" is not actually a "ring"; that's just how it is, so just go with it and don't let it throw you.  As another example, an "algebraic integer" is not an "integer"; it's a complex number with some special properties.  This kind of situation appears all over the place in mathematics.

Ultimately, it's just a convention.  And that's ultimately what language boils down to: a convention.  These conventions sometimes can look a bit inconsistent or "improper", but if they are widely understood, then they still serve the ultimate goal, of clear and concise communication among folks who are knowledgeable in the field.

Bottom line: don't let a sense of what is "proper" overcome the real goal.  Keep in mind the real purpose of these kinds of terms: namely, effective and efficient communication.


Here is some pseudocode that illustrates the recursive idea.

If you choose to take this element, then you have to skip ahead 6 steps.
Otherwise you skip this element and go to the next.

def solve(array, index):
    if index >= len(array):
        return 0
    this_one       = array[index]             # the value x_i
    opt_five_steps = solve(array, index + 6)  # the opt of array[i+6:]
    opt_successor  = solve(array, index + 1)  # the opt of array[i+1:]
    return max(this_one + opt_five_steps,
               opt_successor)

Clearly, this can be turned into a DP algorithm, or memoized as is.


Algorithm for generating all unlabeled trees with n nodes?

Here is some python code
https://gist.github.com/hagberg/7979081

I would start with all the trees size N-1 appending a new node to each of the nodes
The tricky part is to identify whether each new tree is truly new and not isomorphic to previously generated trees. I'm guessing you need a system to code this topologies to detect symmetries.
I'd try to find the longest path
Longest path in an undirected tree with only one traversal
and find a deterministic way to represent the graph

This now gone project to verify the graceful Tree conjecture contains some c++ code that might help you
https://web.archive.org/web/20120729224449/http://www.eleves.ens.fr/home/wfang/gtv/index_en.html


So basically there are three questions involved.

I know that $E(X_k)=\tbinom{n}{k}\cdot p^{\tbinom{k}{2}}$, but how do I prove it?

You use the linearity of expectation and some smart re-writing. First of all, note that
$$ X_k = \sum_{T \subseteq V, \, |T|=k} \mathbb{1}[T \text{ is clique}].$$
Now, when taking the expectation of $X_k$, one can simply draw the sum out (due to linearity) and obtain
$$ \mathrm{E}(X_k) = \sum_{T \subseteq V, \, |T|=k} \mathrm{E}(\mathbb{1}[T \text{ is clique}]) = \sum_{T \subseteq V, \, |T|=k} \mathrm{Pr}[T \text{ is clique}]$$
By drawing out the sum, we eliminated all possible dependencies between subsets of nodes. Hence, what is the probability that $T$ is a clique? Well, no matter what $T$ consists of, all edge probabilities are equal. Therefore, $\mathrm{Pr}[T \text{ is clique}] = p^{k \choose 2}$, since all edges in this subgraph must be present. And then, the inner term of the sum does not depend on $T$ anymore, leaving us with $\mathrm{E}(X_k) = p^{k \choose 2} \sum_{T \subseteq V, \, |T|=k} 1 = {n \choose k} \cdot p^{k \choose 2}$.

How to show that for $n\rightarrow\infty$: $E(X_{\log_2n})\ge1$

I am not entirely sure whether this is even correct. Applying a bound on the binomial coefficient, we obtain

$$E(X_{\log n}) = {n \choose \log n} \cdot p^{\log n \choose 2} \leq \left(\frac{n e p^\frac{(\log n)}{4}}{\log n}\right)^{\log n} = \left(\frac{ne \cdot n^{(\log p) / 4}}{\log n}\right)^{\log n}.$$
(Note that I roughly upper bounded $p^\frac{-1 + \log n}{2}$ by $p^\frac{\log n}{4}$.) However, now one could choose $p = 0.001$, and obtain that $\log_2 0.001 \approx -9.96$, which makes the whole term go to $0$ for large $n$. Are you maybe missing some assumptions on $p$?


Existence of Hamiltonian cycle in a 3-regular $C_n$-free graph

Have a look at this paper "Not Being (Super)Thin or Solid is Hard: A Study of Grid Hamiltonicity" Theorem 6.1 states that HCP (Hamiltonian Cycle Problem) for planar graph of maximum degree $3$ and girth $g$ (i.e. $C_{g-1}$-free) is $NP$-complete, for arbitrary $g>6$ (i.e. $g\geq 6$ in your notation).

So, in your notation, we are left with the undetermined cases of $g=4,5$.

So if you are willing to relax $3$-regular to $\Delta(G)=3$, then $g$ (actually $g+1$ for the girth value) can be arbitrarily large.


What is the appropriate algorithm for bipartite matching with constraints?

The problem as described still seems amenable to doing a bipartite matching with weighted edges if you adapt the graph setup as follows.

If an employee must do four jobs, represent the employee with four vertices in the graph.  Each job should be represented as four vertices in the graph, one for each needed skill level plus one repeated skill level.  Connect each employee vertex with the job vertex corresponding to the highest skill level the employee is capable of performing.  Don't connect an employee to more than one skill level within a job.  Example: if a job has two high skill phases, connect all the employee vertices for a given qualified employee to one phase or the other, not both.  The edge weights between the employee and job vertices should be the employee preference score for the job.

With this graph, a maximal bipartite matching should produce proper job assignments maximizing employee preferences while matching skills.


Describe a data structure to track visitors

The idea is to keep a sorted list of non-empty "buckets". Each bucket $v$ is associated to a certain number $n_v$ of people that wish to visit some city and contains all the cities $c$ that wish to be visited by exactly $n_v$ people.
By keeping a suitable set of pointers cities can be moved from one bucket to the next in constant time. To perform a Favorite($k$) operation it suffices to look at the "last" buckets in the sorted list.

The data structure consists of:

A doubly-linked list $L$. Each node $v$ of $L$ is associated to an integer $\eta_v$ and to a (pointer) to an inner list $\ell_v$ of cities $c$ such that exactly $\eta_v > 0$ people want to visit $c$. The integers $\eta_v$ are appear in increasing order when traversing $L$.

An array $N$ of $n$ elements. The $i$-th element $n_i$ of $N$, if initialized, is the number of people that want to visit the $i$-th city.

An array $P^L$ of $n$ elements. The $i$-th element $p^L_i$ of $P^L$, if initialized, is a pointer to the node $v$ of $L$ such that $\eta_v = n_i$.

An array $P^\ell$ of $n$ elements. The $i$-th element $p^\ell_i$ of $P^\ell$, if initialized, is a pointer to the node containing the $i$-th city in the list $\ell_v$, where $v$ is the node of $L$ pointed by $p^L_i$.

Init$(n)$:

Create an empty list $L$. Allocate (but do not inizialize) the arrays $N$, $P^L$, and $P^\ell$ in $O(1)$ time.

Visit$(\cdot,i)$:

If $n_i$ is initialized, delete (in constant time) the node pointed by $p^\ell_i$ from the list $\ell_v$ where $v$ is the node of $L$ pointed by $p^L_i$. If $\ell_v$ is empty, delete $v$ from $L$.  Increment $n_i$.

Otherwise, if $n_i$ is not initialized, set $\eta_i=1$.

Find the node $v'$ of $L$ such that such that $\eta_{v'}=n_i$, if it exists. Notice that $v'$ can only be the node of $L$ following (the possibly just deleted) node $p^L_i$ in $L$.

If $v'$ did not exists, then create it (in constant time).

Add city $i$ to a new node $z$ of $\ell_{v'}$.

Make $p^L_i$ point to $v'$.

Make $p^\ell_i$ point to $z$.

Favorite$(k)$:

Let $v$ be last node of $L$.
While $k>0$ and $v$ exists:

Let $x$ be a pointer to the first node of $\ell_v$
While $k > 0$ and $x$ exists:

Return the city stored in $x$.
Set $x$ to the vertex following $x$ in $\ell_v$ (possibly none).
Decrement $k$

Set $v$ to the vertex preceding $v$ in $L$ (possibly none).


Non-brute force algorithm for a Eulerian like path

Regarding the problem of visiting as many vertices/edges as possible without using any edge twice: one can look at this problem as the problem of finding an Eulerian subgraph with a maximum number of vertices/edges.  Or alternatively, as the problem of deleting a minimum number of vertices/edges so as to make a graph Eulerian.
You might be interested in the following paper, which studies the complexity of such problems in detail.  In particular, they show several polynomial-time solvable or fixed-parameter tractable cases.  In particular, the edge deletion problems are solvable in n^3 time if a constant number of edge deletions is sufficient.
https://doi.org/10.1007/s00453-012-9667-x


How can you convert the depth of a boolean circuit to its size?

First of all, there are several types of (Boolean) circuits:

Circuits with unbounded fan-in. These are circuits with AND, OR, and NOT gates, where the AND and OR gates can have arbitrarily many inputs.
Circuits with bounded fan-in. These are circuits with AND, OR, and NOT gates, where the AND and OR gates have exactly two inputs.
Formulas, which are circuits with bounded fan-in and fan-out. You can think of formulas either as expressions using the operators binary AND, binary OR, and unary NOT, or as circuits with AND, OR, and NOT gates, where the AND and OR gates have exactly two inputs, and the output of each gate is used only once.

(There are even more types of circuits. For example, we could vary the set of gates. But such circuits are less commonly encountered.)
For circuits with unbounded fan-in, not much can be said about the relation between depth and side, since there are depth 1 circuits of arbitrary size.
For circuits with bounded fan-in, we can say that a circuit of depth $d$ has size at most roughly $2^d$. It also has size at least roughly $d$. Both of these are tight: a circuit whose shape is a depth $d$ complete binary tree and whose gates are AND computes the AND of $2^d$ inputs in depth $d$ and size roughly $2^d$, and in contrast, you can construct a "path" (a tree where the left child of every internal node is a leaf) which computes the AND of $d$ inputs in size and depth both roughly $d$.
For formulas you cannot improve on these relations, but you can there is another important property: a formula of size $s$ can always be converted to a formula of size $s^{O(1)}$ and depth $O(\log s)$, an operation we call balancing. It is conjectured that the same cannot be said for circuits (this is one interpretation of the $\mathsf{NC^1}$ vs $\mathsf{P}$ question), though every circuit of size $s$ can be converted to depth $s/\log s$.


When solving dynamic programming in a grid, how do you recognize whether the solution should start at the bottom-right of the table or top-left?

If a cell depends on cells to its left and bottom, the solution should start at the bottom-left. And so on for all other combinations of left/right and top/bottom.


Where is the OS when a process is running?

The question is mixing up who's in control of the memory and who's in control of the CPU. The wording “running” is imprecise: on a single CPU, a single task is running at any given time in the sense that the processor is executing its instructions; but many tasks are executing in the sense that their state is stored in memory and their execution can resume at any time.

While a process is executing on the CPU, the kernel is not executing. Its state is saved in memory. The execution of the kernel can resume:

if the process code makes a jump into kernel code — this is called a system call.
if an interrupt occurs.

If the operating system provides preemptive multitasking, it will schedule an interrupt to happen after an interval of time (called a time slice). On a non-preemptive operating system, the process will run forever if it doesn't yield the CPU. See How do modern operating systems like linux handle multitasking? for an explanation of how preemption works.

Tasks such as process management and device management are triggered by some event. If the event is a request by the process, the request will take the form of a system call, which executes kernel code. If the event is triggered from hardware, it will take the form of an interrupt, which executes kernel code.

(Note: in this answer, I use “CPU” and “processor” synonymously, to mean a single execution thread: a single core, or whatever the hardware architecture is.)


LTL properties in bounded model checking via assertions

The property "always eventually main terminates" should be expressible and verifiable in a bounded model checker. For such properties, the model checker would either verify the property or find a "acceptance cycle" that shows that there exists a loop in an execution trace that does not satisfy the property (by considering execution traces of bounded lengths).

For example, the given property can be expressed in the SPIN model checker with:

int a;
bool end;

proctype thread1() {
  a = 1;
}

init {
  a = 0;
  end = false;
  run thread1();
  do
  :: (a == 0) -> skip;
  od;
  end = true;
}

ltl prop { always (eventually end) }

The code follows the given C code, where do simulates checking the condition with while loop. When checking if prop holds, SPIN will find an "acceptance cycle" that shows that main might get constantly scheduled for execution and starve thread1, thus refuting the formula. If a "fair" scheduler is assumed (e.g. with enforcing "weak fairness" SPIN reference), the property will be proven correct.

Note that although such (liveness) properties should be supported, by expressing them in LTL (or other logics like CTL), it is not clear how could they be expressible only with assertions (since assertions state something about the state at particular program point).


Chernoff-like Concentration Bounds on Permutations

Chernoff's bound applies to negatively correlated random variables, such as your hypergeometric distribution. You can find a full treatment in Dubhashi and Panconesi's very useful monograph Concentration of measure for the analysis of algorithms, as well as in many lecture notes, such as this one by Hariharan Ramesh.


$\newcommand{\R}{\mathbb{R}}$
Let's consider a special case of the problem where vertex has negative weight and edges have positive weight.
So $w_v: V\to \R^-$ and $w_e: E\to \R^+$.

Finding the heaviest induced subgraph is equivalent to a min-$st$-cut computation on a suitable graph. We will refer to the slides about densest subgraph in this presentation.

Indeed, minimizing $w_e(E(V'))+w_v(V')$ is equivalent to minimizing $(-w_v(V')) + \frac{1}{2} w_e(E(V',\bar{V'})) + \frac{1}{2} \sum_{v\in \bar{V'}} \deg(v)$. (Note the degree here are weighted degree, that is $\deg(v) =\sum_{e:v\in e} w_e(e)$)
The derivation of the above fact is similar to slide 21.
Then, this can be solved easily by modeling it as a min-$st$-cut in some other graph (see slide 22). It is crucial to have negative vertex weights and positive edge weights for the reduction to work.


Probability distribution of runs given k bits set in an n-bit circular buffer

Note first that there is no need to randomly select a location in the buffer – we can fix one as we please. From that location, the probability that a run will be at least $t$ long is the probability that the $k$-set includes the first $t$ locations, which is
$$
\Pr[R \geq t] = \frac{\binom{n-t}{k-t}}{\binom{n}{k}}.
$$
Similarly, the probability that a run will be exactly $t$ long is the probability that the $k$-set includes the first $t$ locations but not the one after it, which is
$$
\Pr[R = t] = \frac{\binom{n-t-1}{k-t}}{\binom{n}{k}}.
$$

The expectation of $R$ is
$$
\mathbb{E}[R] = \sum_{t \geq 1} \Pr[R \geq t] = \frac{\sum_{t \geq 1} \binom{n-t}{n-k}}{\binom{n}{k}} = \frac{\binom{n}{n-k+1}}{\binom{n}{k}} = \frac{k}{n-k+1},
$$
using the formula $\sum_{x=r}^m \binom{x}{r} = \binom{m+1}{r+1}$.


Efficient algorithm for conversion of hexadecimal fraction to decimal fraction

You can do better than quadratic in the length of the fraction, but doing so requires fast (subquadratic) multiplication algorithms such as Karatsuba or Schönhage-Strassen. First, multiply by a suitably large power of 10 to obtain an integer (note that the exponent of this power is at most linear in the length of the fraction). The problem is now to convert a hexadecimal integer to decimal.

Suppose multiplication of two $n$-bit integers takes $M(n)$ time ($O(n\log n\log \log n)$ with Schönhage-Strassen).

Conversion between (general) bases can be done using divide and conquer. Given a hexadecimal integer $k<10^n$, recursively compute decimal representations of $\left \lfloor{\frac{k}{10^{\left \lfloor{n/2}\right \rfloor}}}\right \rfloor$ and $k\textrm{ mod }10^{\left \lfloor{n/2}\right \rfloor}$. The decimal representation of $k$ can then be found by concatenating the two recursively computed representations.

Since division and mod can both be done in $O(M(n))$ time, on an $n$-bit integer this algorithm has running time $T(n)=2T(n/2)+O(M(n))$. For Schönhage-Strassen multiplication, this evaluates to $O(n\log n\log n\log \log n)$.


Equality of cardinality of maximum matching and minimum vertex cover in general

Let $M$ be a maximum matching. Any vertex cover must contain at least one vertex out of each edge in the matching. Hence the size of a minimum vertex cover equals the size of the maximum matching if there's a vertex cover consisting of one vertex out of each edge of $M$.

Denote the edges of $M$ by $e_1 = (x_1,y_1),\ldots,e_m = (x_m,y_m)$, where $m = |M|$. Let $v_i$ be a Boolean variable which determines which of $x_i,y_i$ we pick. We can express the constraint that an edge not in $M$ is covered as a disjunction of two literals. Hence we can express the existence of a vertex cover of size $M$ as a 2CNF. Since 2SAT is solvable in polynomial time, we can determine whether such a vertex cover exists.


Subsequence of one string but not of others

Mistakes

First of all, in the comments I made a few mistakes: Both the original claim I made about interleaving, and the comment "correcting" it (now deleted) were wrong, and separately my claim that trying all possible interleavings must yield an optimal solution was also wrong (I give a simple counterexample below).  Finally, my suggestion to set $x^+ = z_j$ and iterate, or use beam search, is actually also not helpful: Whatever answer could be produced by doing this and applying Aryabhata's DP can never be better than using the original $x^+$, since all it does is reduce the size of the solution set from which the DP can pick.  Sorry!  Hopefully the improved version below contains no further problems...

I also noticed two mistakes in Aryabhata's DP as well.  Fortunately they can both be easily repaired (see my comments on that post).

A heuristic solution using random interleavings

If you don't need absolutely the shortest subsequence, you could use the fact that, if a string $s$ is a subsequence of some $x^-_i$, then it is also a subsequence of every possible interleaving of all the strings $x^-_i$.  Turning this around, if $s$ is not a subsequence of some particular interleaving of all the strings $x^-_i$, then it is not a subsequence of any individual $x^-_i$.

So you could try many different ways of randomly interleaving the $n$ strings $x^−_i$ into a single string, and for each such interleaving $y_j$, look for the shortest subsequence $z_j$ of $x^+$ that avoids being a subsequence of $y_j$ using Aryabhata's nice DP algorithm for the two-string case, and pick whichever $z_j$ is shortest over all interleavings you tried.

Caveat: No guarantee of optimality even if we try all interleavings

Surprisingly (to me at least), even if you repeat the above procedure for all possible interleavings, you are not guaranteed to find the optimal solution: Consider the instance in which $x^+ = aaa$, $n=2$, and $x^-_1 = x^-_2 = a$.  Then $aa$ is an optimal solution with length 2, but the shortest solution found by trying all interleavings of $x^-_1$ and $x^-_2$ is $aaa$, with length 3.


How to understand a equation related to speaker recognition?

$N_z$ is number of frames in the utterance, it is exactly time dimension. Instead "number of features" they should say "number of feature vectors".


What is the difference between finite automata and finite state machines?

As far as I understand, both have "states", and "actions" that make the machine move from one state to another upon an input signal. Thus the conceptual ideas are the same. There is some difference in the details.

In FSM for circuit designs the input signal is mostly assumed to be a bit (binary), whereas in finite state automata one can have a general "abstract" alphabet of input symbols. Second, a FSM also generates an output, associated to the state reached, also binary. In automata terminology this 'extension' is called a Moore machine. Automata however have final (or accepting) states, that signal a favourable input read. Finally, FSM are mostly deterministic, i.e., for each input in a certain state there is one next state. In automata theory one also considers the nondeterministic variant where one might have choice in where to move.


How to evaluate a Kleene's Closure through CFG and attribute grammars

Any "interesting" regular expression (i.e., one that includes Kleene star) represents an infinite set. Thus to "calculate the set of all strings" won't work so well. In a sense, the regular expression is a compact description of the language. What other kind of description do you expect to construct?
It is rather easy to construct regular expressions that represent very complex languages, that the reader needs to descypher to make sense of it.


How to handle horizontal lines in the Polyfill Algorithm?

See Polygon Filling. It gives one method to deal with edges parallel to scanline. It says that it is imperfect, but you can ignore the horizontal edges. Other solution is to take either left or right endpoint of horizontal edge (any one point only). Yet another solution is to take right or left endpoint depending on the situation, so that whole edge is filled.

If you ignore horizontal lines you should get something like the following:


The numbers in the table are not times; they're the rough sizes of the input $n$, for which the algorithm would take the amount of time in the column labels to run.

i.e. you'd need to give an algorithm of logarithmic complexity input of size on the order of $2$ to the something enormous in order to get it to run for a century, but for an algorithm of complexity $O(n!)$ you only input of size ~10 to make it run for that long.

One of the main things to take away from this table is how the numbers grow as you go across some row, and compare this growth rate for different rows.

For example, for logarithmic complexity the size of the input grows exponentially with the increase in time, while for exponential and factorial complexities the input size grows sublinearly with the time increase (though this is a bit obscure just from the table because the time scale is not linear).


How many restricted length strings are there without significant repetitions

For each particular $c,N,M$, this can be solved explicitly by constructing a DFA accepting the language. The general case may also be approached heuristically, though the dependency structure makes heuristic estimates harder to make.

The case $N = 1$ can be solved explicitly. Suppose that the alphabet is $\{0,\ldots,c-1\}$. Represent each word $w_1\ldots w_n$ as the sequence of differences $x_1\ldots x_n$, where $x_1 = w_1$ and $x_i = w_i - w_{i-1} \pmod{c}$ for $i > 1$. Your language then becomes
$$
\epsilon + \{0,\ldots,c-1\}((\epsilon + 0 + \cdots + 0^{M-1})\{1,\ldots,c-1\})^*(\epsilon + 0 + \cdots + 0^{M-1}).
$$
The corresponding generating function is
$$
1 + cx \cdot \frac{1}{1-\frac{x^M-1}{x-1}\cdot(c-1)x} \cdot \frac{x^M-1}{x-1} =
\frac{x^{M+1}-1}{cx-1-(c-1)x^{M+1}}.
$$
The asymptotic growth of the number of words is controlled by the smallest (in modulus) root of $(c-1)x^{M+1}-cx+1$. If this modulus is $\alpha$, then the growth rate of the sequence (under reasonable assumptions) is $\Theta((1/\alpha)^n)$.

Plotting a few of the polynomials $(c-1)x^{M+1}-cx+1$ reveals that there are two real roots in $[0,1]$. We are interested in the one near $1/c$. Suppose that $x=(1+\epsilon)/c$ is a root. Then
$$
1 = cx - (c-1)x^{M+1} = 1+\epsilon - \frac{c-1}{c^{M+1}} (1+\epsilon)^{M+1},
$$
and so
$$
\epsilon = \frac{c-1}{c^{M+1}} (1+\epsilon)^{M+1}.
$$
This shows that $\epsilon$ is exponentially small in terms of $M$, and so we can approximate $(1+\epsilon)^{M+1}$ by $1+(M+1)\epsilon$ to obtain the equation
$$
\epsilon \approx \frac{c-1}{c^{M+1}}(1 + (M+1)\epsilon)
$$
whose solution is
$$
\epsilon \approx \frac{\frac{c-1}{c^{M+1}}}{1-(M+1)\frac{c-1}{c^{M+1}}} = \frac{c-1}{c^{M+1}-(c-1)(M+1)} \approx \frac{c-1}{c^{M+1}}.
$$
Since $1/x = c/(1+\epsilon) \approx (1-\epsilon) c$, altogether we obtain that the number of words of length $n$ in which no symbol repeats $M$ times is $\Theta(\alpha^n)$, where
$$ \alpha \approx c - \frac{c-1}{c^M}. $$

Carrying this sort of analysis for $N > 1$ seems significantly more difficult.


Program that generates a regular expression from an FA

Here's one resource on the matter:
www.cs.dartmouth.edu/~ac/Teach/CS39.../lec09dfa2regexp.pdf

There's a commonly known Dynamic Programming algorithm which can do it. The link I send outlines the algorithm, though it doesn't convert to code. The DP algorithm is pretty common (I think it's usually used in the proof that DFA and RE are equivalent) so if you're looking for the code, it's probably out there somewhere.


What is the problem with this Busy Wait solution for two threads?

Your approach works fine providing assignment operations are atomic. But I cannot see any concurrency in your approach. $P_2$ always waits until $P_1$ produces and reaches the upper limit, for example until it completely fills the buffer. Then it triggers $P_2$ to consume and waits until $P_2$ consumes all items, for example empties the buffer. So the algorithm can be rewritten as

doStuff()
  loop-forever
    produce(F) # N items
    consume(F) # N items
  end
end

In fact the consumer(s) consumes as soon as the producer(s) produces items. In this case you would have to use synchronizations techniques such as mutexes.

Also (from here)

  The producer–consumer problem, particularly in the case of a single producer and single consumer, strongly relates to implementing a FIFO or a channel.

So there is no point to try and use a concurrent algorithm for this problem.  But if your model is multi producer/consumer model then your approach may lead to the race condition.


Survival algorithm for Network deterministic failures

Part b
Suppose $t(e_1)>t(e_2)>\cdots$, what you want is $e_i$ such that the graph with $e_1,\ldots,e_i$ is connected. Part a checks the graph with $e_1,\ldots,e_m$, then the graph with $e_1,\ldots,e_{m-1}$, and so on. This process can be improved by binary search, i.e. checking the graph with $e_1,\ldots,e_{m/2}$, then graph with $e_1,\ldots,e_{m/4}$ or with $e_1,\ldots,e_{3m/4}$ depending on the result of the first check, and so on.
Part c
You don't need to check all spanning trees. You only need to find the spanning tree of whose edges the earliest failure time is maximized. This is known as a minimum bottleneck spanning tree (cost of an edge is the negative of its failure time).


The iteration results in :

(R^2*C + R^1*B + R^0*A + some constant)mod(M) for the string ABC, the value inside the brackets is a base 16 representation of CBA plus some constant value.


We can control tcp/udp traffic using router. Then why is it in Network layer and not transport layer?

Because routers are real concrete devices, not theoretical constructs.  They aren't limited by layering diagrams.  Layering is a form of abstraction, which is a convention; there's nothing that prevents a device from inspecting and acting on the rest of the packet.

Separately: layering diagrams are a model, but not a perfect one.  Real devices violate layering from time to time.  The OSI 7-layer model is especially approximate -- don't take it too seriously.  See, e.g., Till which layer does the loopback packet goes? and can network layers communicate between each other?.


Exact Value of Denormalised number related to floating point numbers

Some -- not all but the most common one are -- binary floating point representations are using a trick to get one more bit of precision.  First, let's define the normal representation for non-null floating point values as the representation where the exponent is chosen so that the most significant bit of the value is the most significant bit of the value is the most significant bit of the significand (also known as mantissa).  The trick is to notice that when the normal representation is used, the most significant bit of the significand is always set for non null values, and thus those format mandate the representation to be normalized so that they can avoid to represent it in the format.

This has two undesirable characteristics.

Some values which would have been representable if normalization was not mandated are now no more representable as normalization would implies a non representable exponent.
The difference between 0 and the first representable value is bigger than the difference between the next representable value and the first.

Some formats (again not all but the most common one are) are trying to avoid those properties by allowing non-normalized values if normalization is not possible.  Those are called denormal or subnormal.

So when a computation result in a number which is smaller (in absolute value) to the smallest normal representation -- also known as underflow --, the main choices are:

use as result a denormal if the representation allow it and the number is not smaller than the smallest denormal
use zero as result

Note that some other possibilities exist:

use as result a NaN marking the result as underflow
generate an exception or an interrupt of some sort
set a sticky bit somewhere meaning that an underflow has been met in addition to returning one value of some kind.

Underflow are usually considered as too common for those other possibilities, excepted the last one, to be considered as useful for most code.


How to rank search results of short string lists

Although i dont really know how a result is better. I guess what you are doing is fine (And perhaps the best possibly you can get). Just one note to be more precise, you should be ranking a node $u$ based on the size of the subtree rooted at $u$ (not on the number of leaves in that subtree, or children of $u$). This is better (and more general).

But one way to solve issues like this in general is to give score to each node in your tree (a weight). The higher the score, the more it will be ranked above. Then, you will be looking for the subtree with highest weights. You compute this by summing the weights of all nodes in a subtree.

Example of weights (just to help you a bet):

closeness to search term (use hamming distance for example, or other metrics [e.g. look how spelling suggestion algorithms work.]
If this is a website of recipes for example, the nodes may be recipes and the weight of a node is how many "likes" it received from the website.

In conclusion, I guess what you are doing is the best approximation to have.  Adding the weights is a heuristic to give you perhaps better results.


Can languages with infinite strings be recursively enumerable?

As you state, the standard definition of TM acceptance requires that the TM halts after finite time.

It is still possible for a TM to accept languages that contain infinite words, if they can accept without reading the entire word. For example the language of all (finite and infinite) words that contain at least one $0$ is semi-decidable, since if there is a $0$, the TM will encounter it after a finite amount of time and can then accept the word.
The complement of this language however is not semi-decidable, since it is not possible to read an infinite input in finite time (and it is not possible, in the general case, to know that there is no $0$, without reading the whole input).


How static Bayesian networks are stored? Like Hugin etc

For anyone who shares this same query. I have found a link that answers it. Further, found a implementation as well.


Computer vision: Why do random filters perform similar to edge detectors?

Intuition, for a small case

Why?  Let's look at the simplest possible case, where the kernel is 1x2 (i.e., two pixels wide and one pixel high).

Here's a kernel matrix for an edge detector that detects vertical edges:

$$E_1 = [-1 \; +1]$$

Here's another matrix for an edge detector that also detects vertical edges:

$$E_2 = [+1 \; -1]$$

In particular, convolution with $E_1$ responds strongly to edges that are vertical and where the right side of the edge has higher intensity and the left side has lower intensity (whiter on the right, blacker on the left).  $E_2$ responds strongly to vertical edges with the opposite intensity variation (whiter on the left, blacker on the right).

We can see that the same is true for other examples.  For instance, consider

$$E_3 = [+1.7 \; -1.7]$$

This behaves almost identically to $E_2$, except for rescaling at its output.

For simplicity, let's focus on convolution kernels that have been normalized so their entries sum to zero.  (Many convolution kernels we use in practice have this form, because they have nice properties.)

What about a random 1x2 matrix?  Well, if it has been normalized, then it will necessarily have the form

$$M = [+\alpha \; -\alpha]$$

for some constant $\alpha$ (where $\alpha$ is random).  Regardless of what $\alpha$ is, we see that this behaves like either $E_1$ or $E_2$.

Conclusion: a random, normalized 1x2 convolution filter behaves like a vertical edge detector, with high probability.

Bigger cases

This can be generalized to other sizes of kernels.  For a random, normalized 2x1 kernel, we'll basically get a horizontal edge detector.  A random, normalized 2x2 kernel will likely respond to edges in some direction (maybe at some angle; the specific direction will depend on the entries of the matrix).

As the matrix gets larger and larger, this effect diminishes (I think).  However, typically in practice we use a relatively small convolution kernel (a fairly small receptive field), so we really care mostly about the behavior with small convolution kernels.

Normalization

What about normalization?  So far I've been talking about matrices that were generated randomly and then normalized to sum to zero.  What if we skip the normalization step?

Well, this doesn't change very much.  Without normalization, a $m \times n$ random matrix $M$ can be decomposed into $M=M' + c \cdot A$ where $M'$ is normalized so its entries sum to zero, $c$ is a constant, $A$ is the matrix containing $1/(mn)$ in every entry.

Convolving the input image with $M'$ has a good chance of being basically applying an edge detector filter to the input image (as discussed above).  Convolving the input image with $c \cdot A$ will basically blur the image and then multiply by $c$.  Thus, the output image is the (weighted) sum of these two: the (weighted) sum of an edge detector filter plus a blurred version of the image.

For a random matrix, there's a decent chance that $c$ will be relatively small (since the mean of the sum of a bunch of random variables is often fairly small), so multiplying by $c$ makes the output image be determined more by the edge detector than by the blurring.  If $c$ is small, we can basically ignore the second term of the sum and approximate the output image as the result of an edge detector filter.

That's why convolution with a random matrix has a decent chance of looking like applying some kind of edge detector to the input image.

Looking at the example images on those pages, to my eyes the first one looks more or less like an edge detector, and the second one looks more or less like a blur operator.  This is consistent with the analysis above.


if A is decidable then B is decidable too

By definition, a language $L$ is decidable if there exists a TM $M\mid L = L(M)$ deciding it. Consider a TM that rejects on all inputs (for example, one where $q_o = q_{\text{rej}}$). The language of this TM is $\emptyset$, so $L=\emptyset$ is decidable.
With reductions, in general if $A\leq B$ ($A$ reduces to $B$), then $B$ is at least as hard as $A$ with respect to decidability. An undecidable language $A_{TM}$, regardless of what it actually is, is harder to decide than the decidable language $\emptyset$ by definition. The specifics of the reduction don't matter; the only information we needed was given in the problem statement (that $A$ is reducible to $B$).


Finding a subset of objects with max value with constraints

Yes sure. You can solve this problem using Minimum Cost Maximum Flow technique. With this algorithm you can find the maximum flow in a network with weighted edges that have minimum total weight (weights can be negative). So let's build the model that fits our problem best.

Build the following graph

There are $n$ nodes in the set $A$ that represent each person.
There are $m$ nodes in the set $B$ that represent each type of object.

The set $A$ and $B$ are full connected the edge $e_{i,j}$ that connects node $A_i$ and $B_j$ has:

capacity: 1 (It can be taken at most once)
cost: $-w_{i,j}$ (We are looking maximum which is the same as minimize the negation of each value)

Source node $S$ is connected with an edge to each node in the set $A$.

capacity: $p$ (each person can carry at most $p$ objects)
cost: 0

Nodes on set $B$ are connected to target node $T$.

capacity: $p$ (each object can be carried by at most $p$ persons)
cost: 0

Maximum flow in this graph is $m * p$ since there is an answer where each object is taken exactly $p$ times.
Minimum cost is the negation of the answer you are looking for.

This problem is in P.


Cryptosystems whose hardness depends on solving the halting problem?

For any reasonable public key cryptosystem that I can think of, no, this is not possible. You cannot base a practical public key cryptosystem on any complexity class larger than EXPTIME.
If the private key is linear in the size of the public key (i.e. if the public key is $b$ bits in size, then the private key is no larger than $\alpha b + \beta$ bits for some constants), then you can test all possible private keys (in exponential time) and see which one decrypts a message.


Where does the need for conditionals (if, switch, jump tables, etc...) truly arise?

It is certainly possible to avoid all conditionals, but most programmers get majorly annoyed if they try to use functional style on a very large program.

But then, no one ever programs anything serious directly in a Turing machine either.


I suspect the book's English explanation is probably a simplification (or maybe it has adopted the standard convention of adding an extra dimension to x that holds a constant value $1$).  It seems like most likely you've already given the explanation; it's adding the bias value.


Understanding a few intricacies related to two naive algorithms to compute the convex hull of a set of points

A1) You're right, the algorithm description sounds kind of weird. A naive algorithm that takes exponential time would rather be something like

foreach (R in S.subsets)
  if (R.isConvexHull(S))
    return R

However, the method for checking whether R is a convex hull needs $n$ time, so we obtain a runtime of $n2^n$.

A2)
Your premise is missing some quantifiers. I think, what you wanted to say is

"$\forall s, $ if $\forall p,q,r \in S, s \not \in \triangle(p,q,r),$ then $s$ is on the convex hull."

Furthermore, go through your example again. You understood it wrong. If you check triangle (1,2,3), you see that 4 is not in the triangle. Hence, 4 might still be on the convex hull (but it doesn't have to). On the contrary, if you check the triangle (4,3,2), you see that 1 is on the interior. Therefore, 1 is definitely not on the convex hull.

This still does not give you a convex hull algorithm though, since the points still have to be sorted by the end. However, this is no problem, since the rest of the algorithm already needs $\mathcal{O}(n^4)$ time.


Is there a connection between the Undecidability Theorem and "software complexity"?

The author is here referring to the Halting problem, and possibly also Rice's theorem (without putting words into their mouths).
It says indeed that it's not possible to decide in advance whether a Turing machine will halt on any given input or not, thus it makes it impossible to decide in advance what the actual output of the machine will be.
This is the fundamental theorem of the field known as recursion theory, more known in these days as computability theory.
The computability theory comprises infinitely many complexity classes, which we are familiar with from complexity theory, but computability theory typically concerns itself with the complexity classes on the decidable/undecidable level: primitive recursive, through the computable class, to the recursively enumerable, and going infinitely beyond to the highly undecidable problems as can be studied via the arithmetical hierarchy.
There are many connections to our "normal" complexity theory, and indeed a very nice analog can be found from the arithmetical hierarchy to the polynomial hierarchy.


Algorithm to find shortest path between two nodes

It is $NP$-complete, and thus it is unlikely that a polynomial algorithm ("better than brute force") exists. Proof is by reduction from Hamiltonian $s-t$-Path:

Every edge in the input graph $G=(V,E)$ is given weight $1$. The graph is then duplicated, and special (weight 0) edges are added between corresponding vertices in the two graphs. We thus get two copies of the original graph, and the copies are linked by $|V|$ special edges between the two copies of the same vertex.  Call these new edges the 'copy' edges.

$|V|$ vertices are added to the graph and connect in a chain with $|V|-1$ new special (weight) 0 edges. Another special (weight 0) edge is added to connect the end vertex to $s$.  Call these new edges the 'chain' edges.

Partition the $2|V|$ new edges into $|V|$ edge sets that each consist of one copy edge and one chain edge.

We now try to find a shortest path between the start of the chain and vertex $t$ that satisfies your requirement of traversing either all or none of the edges from each edge set.
Such a path must start by traversing the full chain, so it must contain all chain edges, so it must contain all copy edges, so it must visit every vertex of the original graph; therefore, omitting all special edges from it will produce a Hamiltonian path from $s$ to $t$, if one exists.

Deciding whether a Hamiltonian path between arbitrary edges $s$ and $t$ exists is known to be $NP$-complete, so your problem is $NP$-hard: if you can find a polynomial algorithm for it (such as Dijkstra's), you will have proved $P=NP$.


How does "Greedy Stays Ahead" Prove an Optimal Greedy Algorithm?

What we are saying is that if A is not optimal, then the number of jobs in A (let it be k) should be less than the number of jobs in O ( let it be m).

That means, there must be (k+1)-th job in O, while the k-th job is the last job in A.

Since (k+1)-th job in O must start after k-th job in O, and we know that any i-th job in A finishes earlier than i-th job in O, that means k-th job in A finishes earler than k-th job in O.

That means, the (k+1)-th job in O can be added to A, which contradicts that A only has k jobs. Hence, A must be optimal and it must have m items.


Show that a language cannot be generated by linear grammar

Your grammar is right-regular and can thus be used to prove that $L \in \mathrm{REG}$. Since every regular grammar is linear, your claim is impossible to prove.


Must a function in lambda-calculus which inputs a boolean function be defined in a certian way?

If we assume that $g$ normalizes when applied to any Boolean input, then we can apply it to true and false, and then we can can compute any Boolean function of those two values. That is, we can readily produce all $16$ possible set theoretic functions, $2^{2^2}$. Your schemas only cover $6$ of those.

But the story goes further, your definition of $f\in(Bool\to Bool)\to Bool$ does not require that $f$ only apply its argument to Booleans. Similarly, $g\in Bool\to Bool$ does not restrict $g$'s behavior for all other inputs. At this point, there are all kinds of additional possibilities (even when restricting to $Bool\to Bool$ inputs) where $f$ applies its argument to other things and performs some other calculation to ultimately produce a Boolean. So there are many other potential terms. If you want tighter guarantees, you may want to consider looking at typed lambda calculi.

(As a tangent, but an interesting tangent, is the class of sequentially realizable functionals. These include functions which are mathematical functions but which aren't implementable in a "pure" way, i.e. they require things like exceptions or mutable state to be implemented.)


Time complexity of euler totient function

The cost inner loop if $n$ is equal to $P_1^{a_1}P_2^{a_2}\cdots P_k^{a_k}$, should be run in $\log_{P_1}n + \log_{P_2}n + \cdots + \log_{P_k}n$ totaly which is $O(k\log(n))$.Notice that, these computation is computed over the outer loop and summation of all iterations of the outer loop.

To more scrutinizing, as the maximum asymptotic number of primes less than $x$ is $\frac{x}{\log x}$, size of $k$ would be $O(\frac{\sqrt{n}}{\log\sqrt{n}})$. Hence, The complexity of the problem would be:
$$O(\sqrt{n} + k\log(n))=O(\sqrt{n} + \frac{\sqrt{n}}{\log\sqrt{n}}\log(n)) = O(\sqrt{n}+\frac{\sqrt{n}}{2})=O(\sqrt{n})$$


How to check for ambiguous grammar if you don't know the string

You cannot tell that a context-free grammar is ambiguous, since the problem is undecidable. This can be proved by a straightforward reduction from the Post correspondence problem, for example. What this means is that there is no algorithm that, given a context-free grammar, decides whether it is ambiguous or not.


We don't know what the best complexity for the 3SUM problem is. First of all, we can improve on your $O(N^2\log N)$ algorithm to an $O(N^2)$ algorithm by carefully scanning the two arrays in tandem, thus obviating the binary search. Until very recently, it had been conjectured that there is a corresponding $\Omega(N^2)$ lower bound, and on this basis the complexity of many other problems, especially in computational geometry, had been "determined". However, very recently Grønlund and Pettie gave an $O(N^2/(\log N/\log\log N)^{2/3})$ algorithm, so we know that the $O(N^2)$ algorithm is not optimal. It is still conjectured that 3SUM requires $\Omega(N^{2-\epsilon})$ time for every $\epsilon > 0$.


Why is the throughput (performance) of the Slotted Aloha protocol ≈ 0.36

Unlike in the regular ALOHA protocol, where other nodes can send messages that interfere with ours at any time, in the Slotted ALOHA protocol, the only other time a message can be sent to interfere with ours is if it's sent at the exact time ours is sent (since in Slotted ALOHA messages can only be sent at specific intervals, like every 5 seconds for example)

Therefore, the probability that our message will be the only one, and have no interference is the probability (in a Poisson Process) that only 1 message on the system (ours!) is sent on the mark

$$P[(N(t + 1) - N(t)) = 1]  = \frac{{e^{ - \lambda\tau } (\lambda\tau) ^ 1 }}{{1!}}  = \lambda\tau e^{ - \lambda\tau} = \lambda e^{ - \lambda}$$

This gives us a function of the throughputs for all $\lambda$s.

To find the $\lambda$ with the highest throughput (that is, what expected rate gives us the highest throughput) we take the derivative and set to zero:

$$e^{-\lambda} - \lambda e^{-\lambda} = e^{-\lambda} (1 - \lambda) = 0  $$

$$\therefore \lambda = 1$$

In other words, when $\lambda$ is $1$, our throughput is highest. How high exactly? Just plug it back into the function we came up with, $\lambda e^{ - \lambda}$ and get:

$$ 1 * e^-1 = \frac{1}{e} = 0.36787....$$

Here's nice graph comparing the two ALOHAs, made by Reuven Cohen.


Complexity of a Turing Machine when changing its alphabet to binary

The first part the proof reads "To simulate one step of $M$, the machine $M^{\sim}$ will: (1) ... (2)... (3)... (4) and (5) ....". Can you see the factor of 4?

You have a good understanding regarding the factor $\log|A|$.  Let us take a close look at the steps in each stage of $M^{\sim}$ above. There are $\log|A|$ steps in stage (1) and in stage (5). However, there is only one step in stage (2) or stage (3) or stage (4). So there are less than $2\log|A|$ steps in stage (2), (3) and (4) combined, assuming $\log|A|\gt1$. If $\log|A|=1$, we can just let $M^\sim$ be $M$ and we are done. So there are less than $\log|A|+\log|A|+2\log|A|=4\log|A|$ steps of $M^\sim$ for one step of $M$.

The second part of the proof is justifying that the stage (2), (3) or (4)  can be done in one step of machine $M^{\sim}$. It explains the power of larger registers. It points out that we can use more states in $M^\sim$ to identify the possibly much more situations ("states" could have been a better word had we not reserved that word for Turing machine) of the machine. Take your time. You will understand.


Maximum number of different substrings in big string

Here is a general solution for an alphabet of size $d \geq 3$ and a string of length $n$.

Every string of length $n$ has $n-\ell+1$ substrings of length $\ell$. Hence the number of different substrings, of any length, is at most
$$
\sum_{\ell=1}^n \min(n-\ell+1,d^\ell).
$$
Consider now an infinite de Bruijn sequence, in which each prefix of size $d^r + r - 1$ is a non-cyclic de Bruijn sequence for length $r$. When $d \geq 3$, such sequences exist, as shown by Becher and Heiber, On extending de Bruijn sequences. Truncate such a sequence to length $n$. We leave the reader to show that the truncated sequence achieves the bound stated above.


How to apply the pumping lemma for CFGs to languages that contain the empty string

The pumping lemma requires the word $w$ you start with to be large enough — larger than the pumping lemma constant $p$.

However, this doesn't really answer your question, which is how to ensure that the string given to the pumping lemma is not empty. Here you are very lucky — you are the one choosing the string! The pumping lemma only states that whatever string $w$ you choose from the language (as long as it is long enough), it can be decomposed as $w = uvxyz$ so that $uv^ixy^iz$ is in the language for all $i \geq 0$, $vy \neq \epsilon$, and $|vxy| \leq p$.


It will iterate $n-4$ steps if $n>4$ . If  $n\leq4$  there will be no iteration since the condition is not satisfied. The important thing is that the linear search runtime grows like the sequence size in the worst case. The notation we use for works like $c_1.n+c_2$ is Θ (n).


The last rule is necessary for languages containing $\epsilon$. A context-free grammar in which $S$ does not generate $\epsilon$ can be converted to Chomsky normal form without the rule $S \to \epsilon$. Conversely, simple induction shows that all other rules do not generate $\epsilon$, so this rule is needed for languages generating $\epsilon$.

The rule arises during the $\epsilon$-elimination step. For each non-terminal generating $\epsilon$, we "optionally" delete it from any production containing in in the right-hand side, and continue the process inductively (eliminating one non-terminal overtly generating $\epsilon$ may reveal that under generates $\epsilon$). Finally, it could happen that $\epsilon$ is pushed all the way to the starting symbol $S$; there is no way to eliminate it there.


Can quick sort time complexity be $\Theta(n\sqrt n)$ for some inputs?

Assume the array is sorted. If you always pick the element at n/2 as pivot then the time is O(n log n). If you always pick the first or last element it’s $O(n^2)$.

So which pivot gives you $O(n^{1.5})$?


Micro-optimisation for edit distance computation: is it valid?

I don't think that the algorithm is flawed. If two strings are matched, we compare first its last two characters (and then recurse). If they are the same, we can match them to get an optimal alignment. For example, consider the strings test and testat.
If you don't match the two last ts, than one of the ts remains unmatched, since otherwise your matching would look like this:

This is impossible, since the arrows are not allowed to "cross". The matched t induces several inserts (green boxes in the figure), as depicted on the left:

But then you can simply find an equally good alignment, depicted on the right. In both cases you match a t and you have two inserts.

The argument for a substitution of one of the last ts is the same. So if you substitute one of the last ts, then you can instead match the last two t, and get a better alignment (see the picture).


You should really work this out yourself, but here are a few hints.

Define P-completeness just as you say, by taking the definition of NP-completeness and changing NP to P. Then ask yourself which problems are P-complete. For a problem to be P-complete it must be in P. What about the other condition? Can you come up with a problem in P which you'd conjecture shouldn't be P-complete under your definition?

Once you've answered part 2, you will be able to answer part 3, so don't despair if you have no idea what they want in part 3 right now.


Register images containing objects with varying distance to the cameras

Yes, if there is a lot of variability in the distance to the objects in the scene, then global registration will work poorly.

Let me back and give some background on how global image registration works.  It tries to align the two images.  In its simplest form, the only transformation that is allowed is translation: it tries to find a way to shift all the points in the left image in a constant direction, to make it match the right image as much as possible.  In other words, it looks for a translation $T$ such that $T(I_1)$ matches $I_2$ as much as possible, where $I_1,I_2$ are the two images.

With this background, you can see why global image registration won't work well for scenes with objects at multiple distances, when you have two pictures taken from a different point.  Imagine taking one picture, then moving left one mile, then taking another picture.  Objects that are far away won't shift their location in the image very much, but images that are close will shift to the right a lot in the second image.  Global image registration tries to find a constant translation that makes everything match up in the two images, but there is no single translation that will work well.  To make the distant objects match up, you'd need a small translation; to make the nearby objects match up, you'd need a large translation; and there is no way to reconcile these differences.

This is the major problem you're seeing.  There are other problems as well, due to the fact that the image is only a 2D representation of a 3D scene.  For instance, if you take two photographs from two different positions, then not only will the location of the objects in the images shift, but also you'll be viewing them from two different angles.  Global image registration can't un-do that, because it can't see around corners.  Look at the two images of the statue.  Imagine that the statue had a little bit of bird dropping on the left side of the person's nose (our left; the person's right).  Then the bird dropping might be visible from the second photograph, which is taken straight-on, but might not be visible from the first photograph, which is taken from an angle.  Alignment can't fix this, as it can't magically make up for things that aren't visible in the photograph.

This answer talks about global image registration based purely on translation.  In general global image registration typically allows a broader set of transformations: a typical example might be something that allows translation, scaling (zoom in or out), and rotation; or translation, scaling, and skew; or an arbitrary linear/affine transformation; or an arbitrary homography / projective transformation.  Unfortunately, none of these really help with the problems outlined above.  In general, no rigid transformation will eliminate the problems I've sketched in this answer, so this answer is pretty general.  In principle, non-rigid transformations might be more effective at handling variation in depth; I don't have any experience with that form of image registration.


Problem regarding Turing Machine notation

Unless I'm misunderstanding the diagram, the way to replace it is with a transition for every letter in your tape alphabet.

Say your tape alphabet $\Gamma = \{ 0,1,2,3 \}$, plus the blank symbol. Then you would have a transition from $R$ to $La$ when reading 0, another when reading 1, another when reading 2, another when reading 3, but NOT one when reading a blank.

You are right in your intuition that this is just syntactic sugar. What it is really doing is using one transition to represent several.