A silly doubt on Computer Science Objects: Arrays, Lists, Strings, and Vectors, are they the same concept?

The objects you mention are not the same.
In particular, lists and (mutable) strings are dynamic data structures whereas arrays are not; their size is fixed.
Now, whether some set of instances of data structures forms a vector space depends on the underlying types, some do, others do not.
Considering e.g. boolean arrays of fixed size $n$ together with the usual addition/scalar multiplication of $\mathbb F_2^n$ yields a vector space, integer arrays of fixed size $n$ do not yield one with the usual operations.


Is there a name for defining recursive functions as an infinite list of input/output pairs?

Well it's the "set-theoritic" perspective of a function where a function
from A onto B is really just the a subset of A x B where each a in A appears only once.

The problem is that some types are uncountable so enumerating them in this manner isn't possible; for some types a finite member may not be at a finite index.

Consider for example, how you would do this for Double.


Why is the lower bound $m \log n$ for this make-set, union and find-set sequence?

You are asking two questions.

  Is the lower bound only for this specific implementation?

Yes. If you also use path compression, the running time will be $o(m\log n)$.

  The lower bound seems to large to me.

Your mistake is that you assume that there are only $\log n$ UNION operations, whereas there are $2^{\lfloor \log_2 n \rfloor}-1 = \Theta(n)$, as the answer clearly .


If it's Possible to Create the If-Statement from Simpler Primitives

Contrary to what you (and many people) may think, in the field of programming languages, the most primitive control-flow operation is actually pattern matching!

With a simple type system (say the simply-typed lambda calculus) plus unit types and sum types, you can encode the boolean type easily. Let $\mathbf{1}$ be the unit type. The boolean type is simply $\mathbf{1} + \mathbf{1}$, i.e. the sum of two unit types (because each variation has exactly one inhabitant, respectively "true" and "false").

Now, when we get a sum type, we can destruct it by pattern matching. That is, for each branch of the sum type, we return a different expression. This is the most basic control-flow operation! The expression if b then et else ef is simply sugar for:

match b with
| left -> et
| right -> ef

Interesting, isn't it?

Of course, this is not how machines work, but from a lambda-calculus/type theory standpoint, pattern matching is the father of all conditional execution!


If the current state is one of $a,b$, then the following state is one of $b,c$.


In a standard operating system like Unix, no.  You can't directly make multiple requests.  But, you can make one big request for a lot of memory.  The system call lets you request a certain amount of memory, and you choose how much to request.

In practice your program doesn't make that system call every time you want to allocate memory. Instead, you have a standard library function, such as malloc(), which has a pool of available memory.  When you call malloc(), it selects a region of available memory and allocates that to the caller, and keeps track that it has been allocated.  When the available memory runs out, then it uses a system call to ask the operating system for a bunch more memory.  So, it might only need to invoke the system call infrequently, even if you call malloc() a lot.

See https://en.wikipedia.org/wiki/Memory_management#DYNAMIC, https://en.wikipedia.org/wiki/Sbrk, https://en.wikipedia.org/wiki/C_dynamic_memory_allocation, https://en.wikipedia.org/wiki/C_dynamic_memory_allocation.


Finding an index such that $A[i] = i$ in a strictly increasing integer array

Let $B[i] = A[i] - i$. Since $A[i] < A[i+1]$, we have $A[i]+1 \leq A[i+1]$ and so (subtracting $i+1$ from both sides) $B[i] \leq B[i+1]$. In other words, $B[1] \leq \cdots \leq B[k]$ is nondecreasing. Your goal is to find an index $i$ such that $B[i] = 0$, if any such exists. You can use binary search to do this in time $O(\log k)$. In fact, you can even find all such indices (or rather, a succinct representation of them) in that running time.


"Famous logicians have made embarrassing errors here," a line from SICP. What is this referring to?

This is a partial answer: I have no idea about which errors or people SICP is referring to. I can only provide some hints about "why" variable renaming can be painful to handle precisely.

First of all, it does seem trivial to define. For instance, we can rename bound variables in indexed sums

$$
\sum_x e = \sum_y (e\{y/x\})
$$

where $e$ is any expression, and $e\{y/x\}$ denotes the syntactic replacement of each $x$ with $y$. Trivial, right?

Well, if we blindly apply the rule above, we get

$$
\sum_x (x+y) = \sum_y (y+y)
$$

That's not good. We need to add the requirement "$y$ does not occur in $e$", or we get a name clash.

Now, consider this correct renaming

$$
\sum_x \sum_y (x+y) = \sum_x \sum_z (x+z)
$$

if we want to rename $x$ into $y$, by the rule above we can do it on the right hand side, but not on the left hand side. That's inconvenient, since the two differ only by a renaming, so they should be handled in the same way.

A typical approach here is to resort to redefining $e\{y/x\}$ as "capture-avoiding substitution", and relax the requirement "$y$ does not occur in $e$" and use instead "$y$ does not occur free in $e$".

We then define free occurrences:

$$
free(x)=\{x\}
\qquad free(e+t) = free(e)\cup free(t)
\qquad free(\sum_x e) = free(e)\setminus\{x\}
$$

Finally, capture avoiding substitution:

$x\{t/y\}$ is $t$ if $x=y$, and $x$ otherwise.
$(e+e')\{t/y\} = e\{t/y\} + e'\{t/y\}$ (easy case)
$(\sum_x e)\{t/y\} = ??$

The last case is painful. If $x=y$, the substitution is no-op, since we want it to affect free variables only, and $x$ is bound. So the result is just $\sum_x e$.

If $y\neq x$, we would like to say that $(\sum_x e)\{t/y\} = \sum_x (e\{t/y\})$. This however is wrong, in general, since if $x$ occurs free in $t$ we get a capture.

Sigh. So, we let $z$ to be the "first" variable which is 1) not $y$, 2) not free in $t$, and 3) not free in $\sum_x e$. Here, "first" means that we need to well-order the set of variable names (e.g. by picking a bijection between names and naturals). Then, we finally let
$(\sum_x e)\{t/y\} = \sum_z (e\{z/x\}\{t/y\})$.

I hope I got it right. (My first attempt was wrong, by the way)

Some authors consider more cases, but the result is the same "up to renaming".
The choice of the "first" $z$ does not really matter above: any such $z$ would work fine, and lead to the same result (again, up to renaming).

Now, finally, we have a sound definition of renaming ($\alpha$-conversion) and capture-avoiding substitution of a free variable. Above, I considered sums, but they apply to all binders (e.g. $\lambda x$ in the lambda calculus, function definitions in many PLs, etc.).

Now, imagine having to deal with this intricate definition every time we want to prove something in PL theory. We could, but we do not want to. It's boring, tedious, error-prone, clutters the proof and provides no insight to the reader. For this reason, many PL authors simply skip the details by saying (or even taking as granted!) that terms are to be taken "up to variable renaming", that all bound variables are assumed distinct from whatever they need to be distinct from, that we assume the "Barendregt convention", or something to the same effect.

To be brutally honest, this is cheating in proofs. We could also add "wink wink, nudge nudge, say no more!" in the same spirit. We essentially ask for mercy and tell the reader: "look, this is boring, I do not want to do it, you do not want to read it -- we both know that, with a huge effort, we could rewrite this proof to include all the details".

Technically, it is possible to exploit this shortcut to prove a false statement. The experienced proof reviewer, however, knows what is "morally fine" and could made perfect (with great effort), and what is suspicious. The latter could include something which depends on the actual choice of bound names (so we are not really working "up to" as promised!). In those cases, the review will ask for more details, so that (s)he can be convinced.


I mean when some says that an agent, in real world grid, is going to step up by %80 and left/right by %10 each. How did he know that?

There are a couple of scenarios that could lead to an agent stepping up with probability 0.8 and left/right with probability 0.1/0.1. The simplest case, and the one you would likely encounter first is that the agent takes an action determined by the agent's policy but the environment dynamics do not map that state-action pair deterministically to a next state, but to a distribution over possible next states. Then taking the same action in the same state multiple times will not always result in the same transition. The agent may choose to go up, but the environment dynamics assign a small probability that if the agent moves up while in the current state the agent may end up moving left or right instead. The dynamics are a feature of the environment, they are independent of the agent, for example they may be observed probabilities in a video game which was developed by other people than the ones develop the RL algorithm to play it.
Another scenario that could explain the probabilities you asked about is the agent could learn a stochastic policy, meaning instead of using a deterministic policy $$\pi:S\to A$$
The agent uses a stochastic policy $$\pi:S\to prob(A)$$ which maps states to probability distributions over actions. In this case, even if the environment is deterministic the agent may choose to move up with probability 0.8 and left or right with probability 0.1 each.

It should be %25 for each direction!!

This could happen if the environment dynamics did not allow the agent to make a meaningful choice at that state, or the agent's policy assigned each action an equal probability at that state. RL agent's are often explicitly programmed to behave highly randomly in the beginning, maybe even following a uniform random policy, which would assign a probability of .25 for each direction in each state. The amount of random actions the agent takes is then annealed over time as more information is obtained about the environment and the estimate of the value function is refined.


What is the bit complexity of Gaussian eliminaton over $\Bbb F_q$?

The dependence on the field is via the cost of arithmetic operations over the field. Since numbers in $\mathbb{F}_q$ have bit size $O(\log q)$, the cost of each individual operation is polylogarithmic in $q$.


Distances have to be non-negative.  Your distance metric leads to a negative distance value, which is not allowed.  A better distance metric would be "the number of genres where they don't agree, plus the number of actors where they don't agree".

As far as how well this will work, the only way to find out is to try it and see.


If $L_1\in R$ and $L_2$ is non-trivial language then $L_1\leq L_2$

We know there are two $x_1,x_2\in \Sigma^*$ such that $x_1\in L_2$ and $x_2\notin L_2$, since $L_2$ is not trivial. Now, we will build the following reduction:
$f(x)=\cases{x_1 & $x\in L(M_1)=L_1$ \\ x_2 & otherwise}$
Notice that $f$ is computable: calculate $M_1(x)$, and output either $x_1$ or $x_2$ according to the answer you got.


Computing probability of sentence using N-grams

The $N$-gram model assumes a generative model in which the next word generated depends only on the preceding $N-1$ words. Using Bayes' law, we get that the probability of a sentence $w_1,\ldots,w_n$ is
$$
P(w_1\cdots w_n) = P(w_1) P(w_2|w_1) P(w_3|w_1w_2) \cdots P(w_N|w_1\ldots w_{N-1}) P(w_{N+1}|w_2\ldots w_N) \cdots P(w_n | w_{n-N+1}\ldots w_{n-1}).
$$
In the particular cases $N=1,2,3$, this gives
$$
P(w_1\cdots w_n) = P(w_1) P(w_2) \cdots P(w_n), \\
P(w_1\cdots w_n) = P(w_1) P(w_2|w_1) P(w_3|w_2) \cdots P(w_n|w_{n-1}), \\
P(w_1\cdots w_n) = P(w_1) P(w_2|w_1) P(w_3|w_1w_2) P(w_4|w_2w_3) \cdots P(w_n|w_{n-2}w_{n-1}).
$$
This means that your expression for $N=2$ is wrong.

In practice, we don't want to store special tables for the first $N-1$ characters. There are two ways around this. First, we can ignore entirely the first $N-1$ words. This makes sense when the text is very long, and we don't expect the first few words to make a big difference in the resulting probability. Second, we can include a special "blank" symbol and add it to our tables, so that (for example) $P(w_1)$ is stored as $P(w_1|\not{b}\ldots \not{b})$.

Usually one stores not the actual probabilities but rather their logarithm. The reason is that adding numbers is faster than multiplying them. As an added benefit, you don't have to worry about the dynamic range of the floating point data type you use (the actual probability could be rather close to 0 and could cause underflow, but this is unlikely for its logarithm).

Another thing to keep in mind is that the results are more meaningful as the text becomes longer. Your example is very short and doesn't serve as a good test case.


Why do we need double-rotations to rebalance AVL trees?

I think you are right for this example. But the title of your question is misleading. Let me explain.

After insertion the tree can be rebalanced with one (single or double) rotation at the lowest node $x$ where unbalance occurs. There are four cases, as you mention. If the key has been inserted in a left-left or a right-right subtree we do a single rotation to the right or to the left, and if it was the left-right or right-left subtree we do a double rotation at $x$ (in suitable direction).
In general a single rotation will not work.

Back to the example you show us. The lowest point of unbalance is $T$. From $T$ the new key $W$ was added right-right. That means a single rotation left at $T$. As far as I see the result of this is exactly what you have drawn in your diagram.

To close, your title is misleading, as we do not need double rotation here, but we need one in other situations.


find an element in array that appeared at least 51% times

If element appears more than 50% of time, you can use Median of medians algorithm by Blum et. al. It is not deterministic though.

Or use specialized algorithm by Boyer and Moore called "Majority vote algorithm". It works by keeping counters of seen element, incrementing on the same symbol and decrementing otherwise. If counter drops to zero, the next symbol is picked.

The trick is that number of increments (and decrements for other symbols) will leave the most frequent item at the end. The second pass is required, because algorithm always terminates with some symbol, which is either the most frequent symbol or some random one (if the most frequent item - the mode - occurs below 50%, there is no guarantee it will be returned).

Here is old-school animation of the majority vote algorithm at authors webpage.


Decrease space complexity, how will time complexity increase?

It depends on the problem.  There's no general rule.

The running time could be as low as $O(n+m)$: for some problems, there exists an algorithm with running time $O(n+m)$ and $O(1)$ space.  (Think about finding the maximum of an array with $n+m$ elements, for example.)

The best possible running time could also be as arbitrarily large.  For instance, think of analyzing connectivity in graphs: given a graph and two vertices $s,t$, determine whether there's a path from $s$ to $t$.  Let $n$ denote the number of vertices and $m$ the number of edges in the graph.  There is a simple algorithm with running time $O(n+m)$ and space complexity $O(n)$, namely, depth-first search.  However, there is no known algorithm whose running time is polynomial in $n$ and $m$ and that uses only $O(1)$ space.

See also https://cstheory.stackexchange.com/q/4556/5038 and https://cstheory.stackexchange.com/q/832/5038 for more technical details on this.

Terminology nitpick: problems have a complexity; algorithms have a running time.  the complexity of a problem is the running time of the best algorithm for that problem.


You can think of $X,Y$ as $n\times n$ matrices with rows $a_1,\ldots,a_n$ and $b_1,\ldots,b_n$, respectively. Then $X = Y$ iff
$$
a_1 \oplus \cdots \oplus a_n = b_1 \oplus a_2 \oplus \cdots \oplus a_n = b_1 \oplus b_2 \oplus a_3 \oplus \cdots \oplus a_n = \cdots = b_1 \oplus \cdots \oplus b_n.
$$


How optimal is Lempel-Ziv at reaching the Shannon limit?

If you apply the LZ77 algorithm twice, it doesn't find any new repeat patterns the second time. You can show that if there were any repeat pattern present after the LZ77 algorithm has been applied. this would have arisen from a repeat pattern in the original data which LZ77 would have found.

The DEFLATE algorithm follows LZ77 with Huffman coding, and does better for finite strings than LZ77 alone. So LZ77 can be improved upon for finite strings fairly easily, just not by using another iteration of LZ77.

However, the Huffman algorithm doesn't use repeat patterns. If you're asking the question of whether, for finite strings, the LZ77 algorithm does as well as any other algorithm based solely on finding repeat patters, I don't know if anybody has looked at this. The problem isn't quite well-defined as stated, but somebody might be able to prove some interesting theorems about this.


How to check ambiguity of a specific grammar

The grammar is ambiguous. The word $abbabb$ can be derived in at least 3 ways:

$$S \Rightarrow SaSMSM \Rightarrow^2 SaMM \Rightarrow SaSMSMaMM \Rightarrow^7 abbabb,$$
$$S \Rightarrow SaSMSM \Rightarrow^2 aSMM \Rightarrow aSMSMSaMM \Rightarrow^7 abbabb,$$
$$S \Rightarrow SaSMSM \Rightarrow^2 aMSM \Rightarrow aMSMSaSMM \Rightarrow^7 abbabb.$$

I found this by thinking about how words in the language might be parsed. My first observation was that if a word ends with $a$, the derivation must have started with the last rule for $S$. If it ends with $b$ or $c$ one of the other non-$\epsilon$-rules must have been used in the first step.

In order to distinguish these two rules, I looked at the preceding symbol, which is $S$ for both rules. The symbol before that differs again. So if we could uniquely identify the word resulting from the $S$ we could determine the initial rule unambiguously. If we furthermore could uniquely identify which subword results from which symbol of the rule in each case, we would get a procedure that yields a unique parse tree for each word, proving unambiguity.

Alas, I noted that it is not possible to uniquely determine the yield of the rightmost $S$. But now I had a better idea, how an ambiguous word should look like.


When can you ignore certain numbers in a recurrence relation?

It depends on what you want to reach and on the recurrence relation.

For example, consider the following recurrence relation
$$T(n) = T(n/2 - 1) + 6n,  T(1) =1$$
and assume we are interested on its asymptotic growth.
If we remove the factors $\frac{1}{2}$ in $T(n/2 - 1)$ and $6$ from $6n$ then we have the following relation

$$T(n) = T(n-1) + n$$
that is a closed formula for the sum of the first $n$ positive integers and is $\Theta(n^2)$.

If we omit only $-1$, then we are left with
$$T(n) = T(n/2) + 6n$$
which is $O(n)$. Thus, omitting factors may result in asymptotically different recurrence relations.

As for your examples, $T(n) = 3T(n/3 - 2) + n/2$ is clearly less than or equal to $T(n)=3T(n/3) + n$, so in order to obtain an upper bound for $3T(n/3 - 2) + n/2$ you can use the later relation, but their exact values for each $n$ is certainly differ. However, I don't see any meaning in the relation $T(n) = T(n) + n^2$ unless $n=0$.


Understanding this explanation about Big O notation

The best way to look at big $O$ notation is the following: $f(x)$ and $g(x)$ have the same $O$ complexity if you can find a positive constants $c_1, c_2 \in \mathbb{R}$ such that $f(x) \leq c_1 \cdot g(x)$ and $g(x) \leq c_2 \cdot f(x)$ for all $x$.

So, for example $4x$ and $10x$ are both in the same complexity class because $4x \leq 1 \cdot 10x$ and $10x \leq 3 \cdot 4x$. We name the complexity class they belong to $O(x)$, because $x$ is the simplest of all expressions of the form $c \cdot x$ so we use it as a representative.

Also, one can write equalities with big $O$;
$$O(4x) = O(10x) = O(x) = O(192839182x) \neq O(x^2) $$

Some basic complexity classes are (in order of complexity, from lower to higher):

$O(log n)$
$O(n)$
$O(n log n)$
$O(n^2)$
$\ldots$
$O(n^k)$
$\ldots$
$O(2^n)$
$\ldots$

and every complexity class on this list is not equal to any other.


What is the time complexity of this Factorization program?

Your algorithm takes $O(X^{1/2})$ in the worst case, which isn't too bad, but it also takes $\Theta(X^{1/2})$ in the best case. That's because you always test divisibility by all numbers up to $X^{1/2}$ even when it is clear that you found all factors of X already.

The loop testing acc % i = 0 is negligible, because X has at most $\log X$ factors.


How to prove $\{ a^ma^lcb^{m+l}\mid m,l \in N \}$ is not regular using the Pumping Lemma?

First of all I would like to write  $M= \left\{ { a }^{ m }{ a }^{ l }c{ b }^{ m+l }\mid m,l \in N \right\} $ as $ M = \left\{ { a }^{ 2n }c{ b }^{ 2n }\mid n \in  N \right\} $. Is this possible?

We have $a^ma^\ell cb^{m+\ell}=a^{m+\ell}cb^{m+\ell}$ so you can certainly write that as $a^ncb^n$ for some $n\geq 2$. But you can't write it as $a^{2n}cb^{2n}$ because $m+\ell$ isn't necessarily even.

The question originally contained a typo, as follows. I've kept my answer to that version of the question because it illustrates a common mistake, so will probably be useful to somebody.

  First of all I would like to write  $M= \left\{ { a }^{ m }{ a }^{ l }c{ b }^{ m+1 }\mid m,l \in N \right\} $ as $ M = \left\{ { a }^{ 2n }c{ b }^{ 2n }\mid n \in  N \right\} $. Is this possible?

No, you can't do that. Let $M=\{a^ma^\ell cb^{m+1}\mid m,\ell\in\mathbb{N}\}$ and $M'= \{a^{2n}cb^{2n}\mid n\in\mathbb{N}\}$. Any $a^{2n}cb^{2n}\in M'$ can be rewritten as $a^{(2n-1)}a^1cb^{(2n-1)+1}\in M$ (i.e.,  we can set $m=2n-1$ $\ell=1$), so $M'\subseteq M$.  However, take $m=2$, $\ell=1$ and we get $a^3cb^3\in M$, but this string is not in $M'$, which means that $M'\neq M$.

You've tried to prove that $M'$ is non-regular but that doesn't prove that $M$ is non-regular. For example, pick your favourite non-regular language $L$ over your favourite alphabet $\Sigma$. $L\subsetneq\Sigma^*$ but the fact that $L$ is non-regular certainly doesn't mean that $\Sigma^*$ is non-regular!

  Proof.

Your proof that $M'$ is non-regular is basically correct except for two small mistakes. First, you can't assume that $x$ and $y$ have even length: they need to have length $i$ and $j$, rather than $2i$ and $2j$. Remember that you need to show that every partition of the string as $xyz$ fails the pumping property, not just the ones where $x$ and $y$ have some particular property. Second, in your sentences about $xy^0z$, some of the $i$s should be $j$s.


Complexity of finding factors of factors of N number

For each value of $j$, the inner loop runs for $O(N/j)$ iterations. Fixing $i$ and varying over all $j$ in the middle loop, the total number of iterations in the inner loop is
$$
O(N/i + N/(2i) + N/(3i) + N/(ki)) = O(N\log k/i),
$$
where $ki$ is the maximal multiple of $i$ which is at most $N$. We can bound $k$ by $N/i$, and so the expression above equals $O(N\log (N/i)/i) = O(N\log N/i)$. Summing over all $i$ from 1 to $N$, we get $O(N\log^2 N)$.

Using rudimentary calculus (approximating the sum by an integral), you can show that if you sum $N\log (N/i)/i$ over $i$ from 1 to $N$ then you still get $\Theta(N\log^2 N)$, and so the bound above should be tight.


Every graph with $\delta(G) \ge 2$ has a cycle of length at least $\delta(G)+1$?

If $\delta(G) \geq 2$ every vertex is connected to at least 2 others. This invariably leads to a cycle in any finite graph.

To see why, try to construct a path without a cycle from a graph with $\delta(G) \geq 2$. Every vertex you add is connected to either a previously added vertex (forming a cycle), or an other vertex. However, in turn, that vertex is connected... Since the graph is finite you will at some point run out of vertices to add which you haven't seen already, forcing you to form a cycle.


Changing variables in recurrence relations

It's certainly not cheating. Think in calculus how substitution may be used to solve a tricky integral. The substitution makes the equation more manageable for manipulation. Additionally, substitution may transform somewhat complex recurrences into familiar ones.

This is exactly what occurred in your example. We define a new recurrence $S(m)=T(2^m)$. Remember that $T(2^m) = 2T(2^\frac{m}{2}) + m$. Notice that, $S(m/2) = T(2^\frac{m}{2})$. If this particular point is still unclear, let $k =m/2$ and notice all we are doing is this $S(k) = T(2^k)$. Now, we can express $S(m)$ by expanding it to:
$$ S(m) = 2S(m/2) + m.$$ Solving for $S$ we see that it resolves to our familiar friend $O(m \log m)$.  Now that we've solved $S$ we want to express this in terms of $T(n)$. To do this, merely plug back in our original value for $m$ and we have $T \in O(\log n \log \log n)$.


Are there languages generated by linear grammar which aren't regular?

Of course. Look at the first example on Wikipedia:

$\qquad S \to aSb \mid \varepsilon$

is linear and generates $\{a^nb^n \mid n \in \mathbb{N}\}$, a non-regular language.

If you mean left-linear, or right-linear, then no - they are equivalent to REG.


one-to-many matching in bipartite graphs?

This problem is called the B-matching problem. Where you are given a function $b:V \rightarrow \mathbb{N}$ that assign a capacity to each vertex and a function $u:E \mapsto \mathbb{N}$ that assigns a weight to each edge.

The problem is solvable in polynomial time. An easy solution is to reduce the problem to minimum weight maximum matching. Create $b(v)$ copies of each vertex  $v$ and connect each of them to all neighbors of the original vertex v. We get a polynomial time reduction, since for $b(v) \geq \mathrm{deg}(v)$ we can set $b(v) := \mathrm{deg}(v)$ since we can not match $v$ with more vertices than its neighborhood anyway and that each of its neighbors is matched with at most one vertex in your special case.


How to construct this generalized xor without needing an extra vector?

The most common definition of xor is $a\oplus b=(a+b)\bmod 2$, on vertices applied to every coordinate seperately of course. In base-10 case, you have to introduce two operations: $a\oplus b=(a+b)\bmod 10$ and $a\ominus b=(a-b)\bmod 10$. (Notice that in base-2 case they coincide). Now you have

$$c=a\ominus b \quad\text{for coding}\quad\text{and}\quad a=c\oplus b \quad\text{for decoding.}$$

Actually, you can use $\ominus$ for both operations, just a bit cleverer:

$$c=b\ominus a \quad\text{for coding}\quad\text{and}\quad a=b\ominus c \quad\text{for decoding.}$$

This works because $a=b\ominus c=(b-c)\bmod 10=(b-(b\ominus a))\bmod 10 $ $= (b-(b-a)\bmod 10)\bmod 10=a\bmod 10=a$.


As far as I can see, "sort the rows of the matrix, with respect to their columns" means that you're supposed to sort the rows lexicographically. That is, the row
$$a_1\ a_2\ \ldots\ a_n$$
comes before
$$b_1\ b_2\ \ldots\ b_n$$
if and only if there's some $i$ such that $a_j=b_j$ for $j<i$ and $a_i<b_i$.

As far as the divide and conquer goes, it doesn't matter that it's a two-dimensional matrix. You're trying to sort a collection of "things" according to some ordering on "things". These "things" happen to be the rows of some array but that doesn't make any difference to the algorithm.


How does the strong form of the PCP theorem imply the inapproximability of Max-XORSAT?

Theorem 11.4 states that for every $\delta > 0$ there is a polytime computable function that on input $\varphi$ outputs a PCP (of a certain form) such that (i) if $\varphi$ is satisfiable then the cost of the PCP (to be defined) is at least $1-\delta$, and (ii) if $\varphi$ is unsatisfiable then the cost of the PCP is at most $1/2+\delta$.

The PCP consists of a distribution over quadruples $(i,j,k,b)$ where $i,j,k$ are indices in the range $1,\ldots,N$, for some $N$ depending polynomially on the size of $\varphi$, and $b \in \{0,1\}$. The value of an assignment $\alpha\colon \{1,\ldots,N\} \to \{0,1\}$ is equal to $\Pr[\alpha(i) \oplus \alpha(j) \oplus \alpha(k) = b]$, and the value of the PCP is the maximum value of an assignment.

(The version in which $b = 0$ always is easy to solve – the zero assignment has value 1. Similarly, when $b = 1$ the one assignment has value 1.)

Furthermore, the distribution is generated using $t = O(\log n)$ random bits. We can think of $i,j,k,b$ as functions of the randomness $r$.

Consider now the MAX-XORSAT instance
$$
\bigwedge_{r \in \{0,1\}^t} (x_{i(r)} \oplus x_{j(r)} \oplus x_{k(r)} = b(r)).
$$
Since $|\{0,1\}^t| = 2^t = 2^{O(\log n)} = \mathit{poly}(n)$, this instance has size polynomial in the size of $\varphi$.

The maximum fraction of constraints satisfied by this MAX-XORSAT instance is exactly the same as the value of the PCP. Hence if $\varphi$ is satisfiable, at least a $1-\delta$ fraction of constraints can be satisfied, whereas if $\varphi$ is unsatisfiable, at most a $1/2+\delta$ fraction can be satisfied.

An approximation algorithm for MAX-XORSAT with ratio strictly better than $1/2$ can distinguish between the two cases (for small enough $\delta$), and so can find out whether $\varphi$ is satisfiable or not. In other words, such an algorithm can be used to solve SAT.


Which pass do you look at for Radix Sort stability?

Radix sort always uses the results of the previous pass, not the original array.  It does not attempt to store the original value of the array.  You can find a description of radix sort at Wikipedia or in standard algorithms textbooks, and you'll see that it has this property.

As Wikipedia describes, radix sort is stable if you sort the digits starting from least significant and moving on to most significant.


Formulating a recursion using mathematical notation

Abbreviating partDist to $D$, you are looking for a formula for $D(w_1,w_2)$. Given the form of the recursion, it will be easier to state a formula for $D(x_1\sigma_1,x_2\sigma_2)$, where $\sigma_1,\sigma_2$ are symbols (i.e., characters) and $x_1,x_2$ are strings; additional base cases will cover the cases in which $w_i$ cannot be decomposed as $x_i\sigma_i$. The formula will be a minimum of two or three terms, depending on whether $\sigma_1 = \sigma_2$ or not.

Alternatively, you can write a recursion for
$$ D(x_1x_2\ldots x_n,y_1y_2\ldots y_m). $$
Here the base cases would be $n=0$ and $m=0$, and in the recursive case you will have to distinguish between $x_n = y_m$ and $x_n \leq y_m$. Here all the $x_i$ and $y_j$ are symbols.


algorithm for correctly rounded floating point radix conversion

In the worst case, you may need very high precision intermediate results. If your problem is limited, for example p ≤ 50 and e ≤ 1,000, it will be possible to prove how much precision is needed at most - with $1000 \cdot 10^{50}$ possible values to convert, 200 bits precision are likely enough.
In practice, some values can be calculated with correct rounding by calculating them with a single floating point operation with exact operands. Many other values can be calculated rounded correctly (including proof) with just a bit of extra precision. So you can do the calculation with relatively few extra bits of precision, check if you have a proven correctly rounded result, and do the same calculation with more bits if needed.
Example: 10.00073 = 1,000,073 / 100,000 Is the quotient of two exact numbers and therefore correctly rounded. 1e30 = 1e15 x 1e15 = product of two exact numbers. 1,000,000,000,000,000,123,456,789,012,345 = FMA (1e15,1e15, 123,456,789,012,344) = fused multiply-add of there exact numbers.


Which of the common sorting algorithms can be parallelized?

Check this link.
Parallelism can be achieved by using  pipeline of processing units or using multiple processor link.

For comparison based sorting lets take an example of quick sort , in quick sort after we find the pivot then we can process two parts in parallel.

quicksort(A)
if |A| = 1 then return A
i := rand int(|A|)
p := A[i]
in parallel do
 L := quicksort({a : a ∈ A | a < p})
 E := {a : a ∈ A | a = p}
 G := quicksort({a : a ∈ A | a > p})
return L ++ E ++ G

Another example we can take is of Radix sort which does not directly compare keys to determine ordering.The basic radix sort algorithm (whether serial or parallel) examines the keys to be sorted one “digit” position at a time, starting with the least significant digit in each key.For implementation in parallel see this tutorial Parallel In-Place Radix Sort


What is considered being proficient in a programming language?

I wouldn't go with your definition:

that one can write a fully functional program without consulting any references

"Hello World" and Deep Neural Networks are both fully functional "programs". The complexity matters..

In the office nobody expects you to handle a program from beginning to end. Depending on the size of the office and their assembly line your assignments will vary a lot. For most of the time, you'll be implementing methods within a larger program.

It is a normal practice to use the documentation ("reference") even if you're on a senior position you're not supposed to remember everything by heart. Every developer I know spends at least  30 min on Stack Overflow every working day.

What is perhaps more valued is a solid foundation, understanding how the language works under the hood, ability to write clean readable code and be a team player.
Beyond a certain level of proficiency, it is not a criterion anymore because if you have a solid understanding of the language you can learn how to implement any complex algorithm or data structure in a reasonable amount of time.
You can never LEARN the whole language, you learn the Grammar...


Probability that two elements are compared in randomized quicksort

The idea of the proof is to compute, for any two elements $x,y$ in the array, the probability that they are compared in the algorithm. This probability could potentially depend on the entire array. However, it turns out that you can compute it only given the order statistics of $x,y$, that is, their relative order in the sorted array. If you know that $x$ is the $i$th smallest element in the array and that $y$ is the $j$th smallest element in the array, then the probability that $x,y$ are compared is $\frac{2}{|j-i|+1}$.

This is not a special case – every element $x$ in the array is the $i$th smallest element, for some value of $i$. This is just the pertinent information that allows us to calculate the probability that $x$ and $y$ are compared.


Difference between the two regular expression

Your regular expression (a+ba*b)* won't match the string a which contains zero b's, an even number.  It also won't match the strings bb or bbbb, because the expression requires one or more a's before any occurring b's and requires at least one a between any two pairs of b's.

The regular expression a*(ba*ba*)* is the correct solution.  It allows any number of leading a's and then demands that there if there are b's present there be at least two b's among the remaining a's.  Thereafter b's are matched in groups of two among the a's and matching will fail if a b occurs outside such a pair.

The regular expression a*(ba*b)* is wrong because it won't match strings with a's between pairs of b's, such as the string bbaabb.


Find value of $a$ or $b$ of two XOR equations

No. $a\oplus b = c$ and $c\oplus b = a$ are just rearrangements of the same equation, since

$$a\oplus b = c \iff (a\oplus b)\oplus b = c\oplus b\iff a=c\oplus b\,.$$


Changing AVL's balance factor to some other $s>2 \in \mathbb{N}$

If the maximal branch is of height $h$ then you know that all the other branches have at least height $h-s$.

Lets consider $n$ the number of nodes in the two extreme case:

All branches of height $h$: $n=2^h$
One branch of height $h$ the others of height $h-s$: then $n=2^{h-s}+s$

Hence $ 2^{h-s}+s=\frac{2^h}{2^s}\leq n\leq 2^h$ since $s$ is a constant the height is still logarithmic in the number of nodes.

I think this answer your other questions too.


Can a regular language enforce a length limit AND disallow consecutive characters?

You are not wrong. In fact, any finite language $L$ over a finite alphabet $\Sigma$ is regular. If $L$ is finite, there must be an integer $d$ such that for all $x \in L$ it holds that $|x| \le d$. Let $|\Sigma| = s$ and construct a complete $s$-ary tree of depth $d$, where each edge from a node to one of its children is a transition associated to some $c \in \Sigma$.

We can see that such a tree enumerates all the strings over $\Sigma$ of length at most $d$; this means that each string of $L$ must correspond to some node of the tree. Marking as an accepting state every such node yields a DFA for $L$.

Notice that the resulting DFA may be very ugly, but it's a valid DFA nonetheless, and that is sufficient if we are only concerned with regularity.


What exactly is going on in a proof by induction of a recurrence relation?

What are boundary conditions?

Given a recurrence/function $f$ boundary conditions are simply a few points, usually small points such as 0,1 or 2, at which $f$ is specified. For example, in the Fibonacci sequence $$F(n) = F(n-1) + F(n-2), F(0) = F(1) = 1$$
$F(0),F(1)$ are boundary conditions. In other words initial conditions, base conditions.

The excerpt you posted proves the upper bound for the recurrence relation $2T(\lfloor n/2 \rfloor) + n$. It is done using substitution method for solving recurrence relation where you first guess the solution (involving constant(s)) and then find constant(s) that would satisfy boundary conditions.

After you guessed the solution you get an explicit (as in your example) equality/inequality of the form $T(n) \leq cg(n)$ which you have to prove in order to establish the upper bound for the recurrence relation $T(n)$. That is usually done using induction. However, the original boundary conditions may fail when you use it with your guessed function $g(n)$ like in the example: $T(1) = 1$, but $c\log(1) = 0$. At this point you should kind of select new boundary conditions (initial points) to prove the inequality $T(n) \leq cg(n)$. Without base step you cannot complete induction proof.

So the example "overcomes this obstacle" by choosing a new value $n_0$ for the inductive proof. However, $T(1) = 1$ is still kept but it is removed from the inductive proof. The example then introduces new boundary conditions $T(2)$ and $T(3)$ instead of $T(1)$. Given $T(1)= 1$, we have $T(2)= 4$ and $T(3)=5$ and so for some constant  $c \geq 2$ the following conditions hold $T(2) \leq c2\log(2)$, $T(3) \leq c3\log(3)$.

Now you can prove that $T(n) < cn\log(n)$ using induction by taking base step $n=2$ and $n=3$ ($n \geq 2$).

  How do we know the base case?

If base case (boundary conditions) of the original recurrence relation fails, you can just remove them from the new equation/inequality and introduce new base case for which the equation/inequality holds.

  I don't understand what the paragraph is getting at.

This paragraph is just one simple example demonstrating how a new substitution function fails at the original boundary conditions and how to overcome that problem.

  How do we determine the base case in the general case?

There is no a standard way to do that, use you intuition, guess, and check if it works. You should choose your boundary conditions carefully. In the example you in your post $T(2)$ and $T(3)$ are chosen as new boundary conditions since values of $T(2)$ and $T(3)$ directly depend on the value of $T(1)$ which is troublesome. So we just put $T(2)=4$ and $T(3)=5$ without using $T(1)$.

Making a good guess

  Unfortunately, there is no general way to guess the correct solutions
  to recurrences. Guessing a solution takes experience and,
  occasionally, creativity. Fortunately, though, you can use some
  heuristics to help you become a good guesser.

  Is this acceptable, or would that constitute a sloppy proof?

This inequality should be proven. Assume that our claim is true for all integers less than or equal to $n$. We need to show that the inequality is true for $n+1$.

$$ T(n+1) = 2T((n+1)/2) + (n+1) \leq 2c\frac{n+1}{2}\lg{\frac{n+1}{2}} + (n+1) = c(n+1)\lg{\frac{n+1}{2}} + (n+1)=(n+1)(c\lg{\frac{n+1}{2}} + 1) \leq (n+1)(c\lg{\frac{n+1}{2}} + c) = c(n+1)(\lg{\frac{n+1}{2}} + 1) = c(n+1)(\lg{\frac{n+1}{2}} + \lg2) = c(n+1)\lg{(n+1)}$$


The acronym DAG stands for directed acyclic graph. In other words, a DAG is a (finite) digraph without directed cycles. A digraph is a DAG if and only if it has a topological ordering.

In your example you have a labeled DAG. The labels do not constitute a topological ordering of the DAG, but the underlying digraph is still a DAG.


It is considered tail recursion if there is no computation between the recursive call and the return.

In your example there is no computation, only an assignment.

It would depend  on the actual compiler if code for an optimised tail recursive call was made at this point, but yes some compilers could treat this as a tail recursive call.


Hint: map $1,2$ to $a$ and $3,4$ to $b$.


If you are willing to introduce additional variables, you can convert from DNF to CNF form in polynomial time by using the Tseitin transform.  The resulting CNF formula will be equisatisfiable with the original DNF formula: the CNF formula will be satisfiable if and only if the original DNF formula was satisfiable.  See also https://en.wikipedia.org/wiki/Conjunctive_normal_form#Conversion_into_CNF.

If you don't want to allow introduction of additional variables, converting from DNF to CNF form is co-NP-hard.  In particular, testing whether a DNF formula is a tautology is co-NP-hard.  However, testing whether a CNF formula is a tautology can be done in polynomial time (you just check separately whether every clause is a tautology, which is easy as each clause is a disjunction of literals).  Therefore, if you could convert from DNF form to CNF form in polynomial time, without introducing new variables, then you would obtain a polynomial-time algorithm for testing whether a DNF formula is a tautology -- something which seems unlikely, given that we expect P is not equal to co-NP.  Or, to put it another way, converting from DNF to CNF form without introducing additional variables is co-NP-hard.

This is the difference between equivalence vs equisatisfiability.  Equivalence requires the two formulas to have the same set of solutions (and thus does not allow introducing additional variables).  Equisatisfiability only requires that either both formulas are satisfiable or both are unsatisfiable (and thus does allow introducing additional variables).


P class definition in Garey and Johnson's Computers and Intractability

The definition given is the standard one.  Before reading the rest of this answer, I recommend that you carefully go over the definition again. A lot of what you're asking is "What does the definition say?" and you'll probably understand it better if you figure it out yourself. The rest of your question is, "Why did we choose that definition?"

The definition is equivalent to the following. A Turing machine $M$ "runs in polynomial time" if there is some polynomial $p$ such that $M$ halts in at most $p(n)$ steps for all inputs of length $n$. A language is in P if it is the set of strings accepted by some Turing machine that runs in polynomial time.

  Does this mean that their P complexity class contains only languages that are composed of yes-instances, i.e. languages recognised by $M$, consisted of $x$ strings such that $M$ always halts in accepting state for every of them as an input?

Yes, that's what the definition says. It also says a little more: the language recognised by $M$ doesn't include any of the "no" instances.

  What about input that also causes halting, but in rejecting state $q_{n}$?

If a machine runs in polynomial time, it halts for all inputs. Thus, for any given input, the machine either accepts or rejects. The whole point is that the Turing machine tells you exactly which inputs are in the language and exactly which inputs are not.  If the machine rejects an input, that input isn't in the language.

  Shouldn't these be also in PTIME?

This is a category error. P is a class of languages, not inputs.

However, you might be thinking of the following. We could also define a language that is the set of strings rejected by some Turing machine that runs in polynomial time. Perhaps you're wondering why that language isn't in P? Well, it is, because it's also the set of strings accepted by some polynomial-time Turing machine. Just take the machine that defines the language by rejecting and modify it so that every instruction "go to the accepting state" becomes "go to the rejecting state" and vice-versa.  Now you have a Turing machine that defines the language you're interested in, but defines it by acceptance.


Why is computation of this function numerically unstable?

The question has been changed since this answer.

Another alternative is
$$\begin{align}f(x)&=\frac{\sqrt{x+h}-\sqrt{x-h}}{2h}\\
&=\frac{\sqrt{x+h}-\sqrt{x-h}}{2h}\cdot\frac{\sqrt{x+h}+\sqrt{x-h}}{\sqrt{x+h}+\sqrt{x-h}}\\
&=\frac{1}{\sqrt{x+h}+\sqrt{x-h}}\end{align}$$

Now, even if $h$ becomes very small, the value approaches $$\frac{1}{2\sqrt{x}}$$ as it should.


How to calculate the number of invalid strings given a constraint system on alphabet, word blacklist, and string length

The language of valid strings is regular.  Build a DFA to recognize the language, then use standard techniques to count the number of words accepted by the DFA (see Why isn't it simple to count the number of words in a regular language? or https://cstheory.stackexchange.com/q/8200/5038).

How do you build a DFA to recognize the language?  Via a product construction.  Let $L_a$ denote the set of all words that don't have $n+1$ $a$'s in a row, and let $L_\rho$ denote the set of all words that aren't in the blacklist.  Then your language is $\Sigma^{\le m} \cap L_\rho \cap L_a \cap L_b \cap \cdots$.  You can easily build DFAs for each of the individual languages, and then use the product construction to build a DFA for their intersection.

Warning: the size of the DFA can potentially blow up exponentially in $|\Sigma|$.  However, this will remain polynomial in $n$, $m$, and $|\rho|$.


What is softmax in reinforcement learning?

Ok, I have read a very good explanation to what softmax is.
A dog is programmed to walk through a maze. One start point has very few walls. The way it is programmed with the epsilon greedy algorithm, the dog will sooner or later start to walk mostly to the right or mostly to the left. That is a problem because it at some point might just walk in a circle the entire time. To get that out one could make it choose left or right randomly from time to time - but that is not really a good approach for obvious reasons.
So instead you use something called softmax. Softmax just smoothens the decision process: like taking out the walking-left or walking-right.


The state of affairs as of 2013 is described in Mertens and Moore, The Complexity of the Ferminonants and Immanants of Constant Width. Let $\lambda$ be the partition corresponding to $\chi$.

Immanants are easy if the leftmost column of $\lambda$ contains $n - O(1)$ boxes (Barvinok; Bürgisser).
Immanants are hard if $\lambda_i - \lambda_{i+1} = \Omega(n^\delta)$ (Brylinsky and Brylinsky, improving on results of Hartmann and Bürgisser which applied only to hooks and rectangles).
The problem of computing the $\lambda$-immanant given $\lambda$ is hard even if $\lambda$ is restricted to have width 2, and promised to have at least $n^\delta$ boxes in the second column (Mertens and Moore; de Rugy-Altherre).

The paper of de Rugy-Altherre is subsequent to Mertens–Moore.


Find multiple duplicates in $n$ size data set in linear time

This can't be done in constant space.

Let's think first about algorithms  that read the entire input array before producing any output.  Note that there are exponentially many possible outputs.  In particular, the output might include up to $n/2$ different numbers that are "multiple duplicates".  Thus, there are at least ${n-1 \choose n/2}$ different possible outputs, and ${n-1 \choose n/2}$ is $\Theta(2^n/\sqrt{n})$.  Now the state of the algorithm (the values of all variables, etc.) before producing output must uniquely determine the output, so that means there must be at least ${n-1 \choose n/2}$ possible states.  It requires $\lg {n-1 \choose n/2}$ bits to store that state.  It follows that any algorithm that reads all input before producing all output must use at least $\lg {n-1 \choose n/2}$ bits of space; and this is $\Theta(n)$.  So any such algorithm must use linear space.

What about algorithms that might produce output as they go?  It's still not possible in constant space; such algorithms still need linear space.  Consider an input where the first half of the array has no duplicates, and think about the intermediate state of the algorithm at that point.  That state must contain enough information to deduce the set of numbers in the first half of the input array (if two such input arrays that differ in their first half produce the same state at this point, then we can construct a way to fill in the second half so that the algorithm is wrong for at least one of those -- just pick a number that appears in the first half of one of those inputs but not the other, and make sure it appears exactly once in the second half).  It follows that there must be at least ${n-1 \choose n/2}$ possible states after reading the first half of the input array.  As before, it then follows that the algorithm needs $\Theta(n)$ bits of space.  So producing output as you go doesn't help -- it still can't be done in constant space.


Approximately sorting integers by many criteria

I don't know if there is an efficient algorithm that will always produce the optimal solution.  I would suggest looking at heuristics that hopefully will often work well, even if they don't come with guarantees.  One plausible approach would be to use simulated annealing, or some other form of local search.  At any point, you can pick a pair of random indices $i,j$ and consider would happen to $r$ if you swap the items at those two locations; then the simulated annealing algorithms describes the conditions under which you apply that swap vs not.  Repeat until convergence.  There are no guarantees this will give the global optimum -- it get stuck in a local optimum -- but it could be worth a try.

If you are OK with maximizing $\sum_i r_i$ instead of maximizing $\sum_i r_i^2$, the following might work.  You might be able to reduce this to the assignment problem and then apply a standard algorithm for the assignment problem.  In particular, for each item $i$ and each rank $j \in \{0,1,2,\dots,n\}$ create an edge from item $i$ to rank $j$ whose cost is $\sum_k 6(j-R_k(i))^2/n(n^2-1)$.  Then, use an algorithm for the assignment problem to find an assignment that assigns a unique rank to each item.   The sum of the costs of the selected edges will be equal to $k-\sum_i r_i$, so minimizing the sum of the costs will maximize $\sum_i r_i$.  Assigning each item to a unique rank is equivalent to sorting the items; you just put the items in order of their rank.  The assignment problem ensures that no two items will receive the same rank, and every item will receive some rank.

I'm not sure if this works or not.  At one point I thought this would work; then at another point I thought it wouldn't work (but I can't remember why not); and now I'm thinking again that this should work, and give a polynomial-time algorithm to find the exact solution for maximizing $\sum_i r_i$.  As you can see, I've gotten myself totally mixed up here, so I don't trust my thought process.  Double-check all of my reasoning here before placing any reliance on it.  (Even if this doesn't give the optimal answer, it's also possible that it provides a useful initialization for simulated annealing.)


What is the lower bound for finding the third largest in a set of $n$ distinct elements?

Answer my own question:

At the end of "Lecture 28: Adversary Arguments" by Jeff Erickson, I found

  A similar argument implies that at least $n - k + \lceil \lg {n \choose k-1} \rceil = \Omega \big( (n - k) + k \log (n / k) \big)$ comparisons are required to find the $k$-th largest element in an $n$-element set. This bound is tight up to constant factors for all $k \le n/2$; there is an algorithm that uses at most $O \big( n+k \log(n/k) \big)$ comparisons. Moreover, this lower bound is exactly tight when $k = 1$ or $k = 2$. In fact, these are the only values of $k \le n/2$ for which the exact complexity of the selection problem is known. Even the case $k = 3$ is still open!

Therefore, the current answer to the question is that it is still unknown.


What is a difference between cross-lingual IR and multi-lingual IR?

In this paper they differentiate between these two terms as follows:

  While CLIR is concerned with retrieval for given language pairs (i.e.
  all the documents are given in a specific language and need to be
  retrieved to queries in another language), MLIR is concerned with
  retrieval from a document collection where documents in multiple
  languages co-exist and need to be retrieved to a query in any
  language. MLIR is thus inherently more difficult than CLIR.


Trouble understanding this dynamic programming solution

The problem is to count the subtrees of an undirected tree that have at
most k outgoing edges to the rest of the tree.

The idea of the algorithm is a divide and conquer plus dynamic programming technique. For a
tree T, you divide it into 2 subtrees, and for each you compute all
subtrees that have i outgoing edges for each i less than or equal to
k. There is however a little twist to allow the recurrence step to
work. The divide and conquer part is not really necessary, but it does allow a simpler organization.

I agree that the explanation of the algorithm that you were given is somewhat obfuscated.

small-boundary trees are what you called valid trees,  with at most
k out-going edges.

Consider your tree T.

Though in your undirected tree T all nodes are born equal, you choose
to distinguish a root v.

The idea is to count the number of subtrees for each value of the
number of outgoing edges, an also separate those that contain the root
v from those that do not.

Hence you have two vectors Tv+ and Tv--, for the subtrees including v and
for the subtrees not including root node v.
Tv+[i] is the number of subtrees including V that have i outgoing
edges.
Tv-[i] is the number of subtrees not including V that have i outgoing
edges.

The sum of these two vectors will give you the number of subtrees with i outgoing edges for each value of i less than or equal to k. At this point the distinction into two vectors has not been useful, but it is needed for the recursion.

Before using them, you have to compute these two vectors.

For that purpose, you choose an edge e={v,w}, which cuts your tree T in
two subtrees L and R, respectively rooted in v and w as shown on the figure

|\         /|
| \   e   / |
|L v-----w R|
| /       \ |
|/         \|

Suppose you have computed the vectors Lv+, Lv-, Rw+ and Rw-, then you
can use the results in those 4 vectors to compute Tv+ and Tv- as
explained in the document.

Subtrees that include v consist of a subtree in L that includes v,
plus optionally e and a subtree in R that includes w.

translates into :

Tv+[i] = Lv+[i-1] + sum (Lv+[j] * Rw+[k]) for all (j,k) such that j+k=i , for i>0

Tv+[0] = 1    Only the whole tree T contains v and has no outgoing edges.

The i-1 in Lv+[i-1]is to account for the added outgoing edge {v,w}

The sum of products is for all subtrees that include the edge {v,w}, and thus have a
part in L and another in R.

Subtrees that don't include v consist of either a subtree in L that
doesn't include v, or a subtree in R (double counting the empty tree).

translates into :

Tv-[i] = Lv-[i] + Rw+[i-1] + Rw-[i]  for i>0

Tv-[0] = 1  for th empty tree {}

The i-1 in Rw+[i-1] is for the fact that subtrees counted in Rw+ get an extra edge {v, w} in the recurrence step since v is not included

There is empty tree in Lv-[i] and another in Rw-[i], but it does not matter as empty trees are considered  in the case i=0.

hoping I did not miss anything.

Is this enough to get you started, or do you need more?

One last point. The description of the algorithm starts by saying that it will consider the count of small-boundary trees, which I believe are your valid trees. If you know in advance the value of k (defining them) that you do not wish to exceed,
then you vectors need only have length k+1. For example, if k=1, the vectors should be of length 2 (for zero edges and for 1 edge). Any subtree that exceeds k edges will be useless for the rest of the algorithm (the count cannot go down)
and can thus be forgotten.

Note that, as described, the original algorithm uses variable size arrays, only as long as needed for the subtree at hand. That is required if you do not fix k in advance. If you do, you just use length k+1 as I said.

But this is a personnal remark that you may or may not trust. It is not in the algorithm you have been given.


Lower bound of a summation with an exponential


Simple proof that circuit satisfiability problem is NP-Hard

The (very) simplified version is that they convert any verification algorithm $A$ for a language $L \in \text{NP}$ into a circuit.

What they end up with is a circuit $C$ that, given a (binary) string $x$ is satisfiable (i.e. $C(x)=1$) if and only if $x \in L$ (i.e. there exists a certificate $y$ such that $A(x,y) = 1$).

They do this by encoding the working of the algorithm embodied by some Turing Machine (i.e. the transition function) as a circuit $M$. The total circuit $C$ is then a series of concatenations of $M$, where the input values to each iteration of $M$ is a binary encoding of the state of the TM embodying $A$.

As every bit of this (including the number of steps $A$ takes) is polynomially bounded by the size of $x$, the circuit can be constructed in polynomial time.

So what they give overall is a polynomial time way to construct a circuit simulating $A$ set by step that is satisfiable if and only if we can find some certificate that $x \in L$. Then if we could decide in polynomial time if $C$ is satisfiable we'd know that there's some certificate which proves $x \in L$, hence deciding $L$ in polynomial time.


Are multiple interrupts generated when I hold down a key on my keyboard?

TL;DR: No.

It depends on the OS and the keyboard. I'll show you how to determine this yourself on a Linux machine. I'm using Ubuntu 16.04 on an x86 processor. So if you are using a fairly modern version of Linux and an x86 processor, then the steps will be pretty much the same. I have a USB keyboard (and mouse) and almost everyone else does.

Open a new terminal and execute the following command:

watch -n0.5 "cat /proc/interrupts"

This enables you to monitor hardware interrupts in real time. Examine the last column and look for the lines that contain ehci_hcd:usbN where N is some small number. On my system, there are two such line:

            CPU0       CPU1       CPU2       CPU3
 16:         17          3          0          9  IR-IO-APIC  16-fasteoi   ehci_hcd:usb1
 23:         88      72272     101007    1327899  IR-IO-APIC  23-fasteoi   ehci_hcd:usb2

The first column shows the interrupt request signal number (IRQ). It identifies a physical bus on the motherboard that is used by the I/O device to interrupt the processor. The four columns in the middle show the number of interrupts handled by each core. There are four (logical) cores on my system. Notice how the overall number of interrupts from IRQ 23 is very large while the number of IRQ 16 interrupts is almost zero. This is a strong indication that the keyboard and mouse both use IRQ 23 to send interrupts to the processor. In general, though, the mouse and keyboard may use different IRQs depending on the USB port they are connected to. Some USB ports may share the same IRQ line1.

Now you can observe what happens to the interrupt counts when using the keyboard. Hold the mouse still (so that the mouse does not generate any interrupts) and press some keys on your keyboard. When a keyboard key is pressed, the interrupt count on one of the CPUs will increase by exactly one. When a key is released, the interrupt count will also increase by one. In addition, you can see that, while the key is held down, the interrupt count does not change. Therefore, the keyboard does not send interrupts for the key held down. Instead, Linux uses a software keyboard repeat mechanism, by default, for USB keyboards. As long as the keyboard has not yet sent an interrupt indicating that the key has been released, Linux knows that it is held down.

Software keyboard repeat is implemented by using a timer interrupt. There are two parameters involved, both are configurable. The first is called the typematic repeat rate (also called autorepeat rate), which specifies the rate at which the keydown event should be repeated in terms of the number of characters per second. The second is called the typematic delay, which specifies how long a key must be held, in milliseconds, before it begins to repeat. You can print the current values of these parameters using sudo kbdrate. On modern versions of Linux, it prints:

Typematic Rate set to 10.9 cps (delay = 250 ms)

You can also modify these parameters using the same tool, and then observe the effects using /proc/interrupts as discussed above.

Since software keyboard repeat relies on the timer interrupt, it can support a wider range of typematic repeat rates and shorter typematic delays. This is in contrast to hardware keyboard repeat, which is the default mode for AT and PS/2 keyboards in old versions of Linux. People who used to suffer issues from hardware keyboard repeat were advised to use atkbd.softrepeat=1. Most keyboards are configurable regarding keydown repeat behavior.

For more information, you can refer to /include/linux/input.h and /include/linux/input.c of the Linux source code as a starting point.

Footnote 1:

You can determine with certainty which IRQ line the USB keyboard and mouse are connected to by executing the following command:

lsusb -v

This will print a list of all USB ports and controllers on the PCIe interconnect. On my system, all USB ports are either on Bus 001 or Bus 002. In /proc/interrupts, these are named ehci_hcd:usb1 and ehci_hcd:usb2, respectively. So, for example, if lsusb tells you that the keyboard is on Bus 001, then the keyboard uses IRQ 16. When a key is pressed or released, the scan code of the key is simply stored in the keyboard buffer and the keyboard controller then raises an interrupt to one of the CPUs (as specified by I/O APIC interrupt affinity). Then the target CPU gets interrupted, calls the interrupt handler mapped to the IRQ, which in turn reads the scan code from the keyboard controller buffer and stores it into the kernel's keyboard buffer for further processing.


Abstract Syntax Tree of Pure Lambda Calculus

I would like to know if/how evaluation strategies affect the structure of ASTs, how order of operation is reflected in the AST of an expression

They don't, and it isn't. Evaluation strategies are functions which take ASTs as arguments, and return ASTs (or possibly only normal forms), so you can have different evaluation strategies working on the same AST.

  I think if I could just get some practice with the AST representation of some non-trivial functions in any language, I will be okay.

See e.g. this Stack Overflow question:

data Exp = Var String
             | App Exp Exp
             | Lam String Exp

In the case of pure lambda-calculus, there is no Constant Int, and and would look like

Lam "a"
  (Lam "b"
     (App
        (App
           (Var "a")
           (Var "b"))
        (Lam "t"
           (Lam "f"
              (Var "f")))))


(I think by pointers you mean the "pebbles" that are described in Kozen's Automata and Computability.)

The language $L'$ is regular.

You can prove that as follows: Consider the DFA $D_1 = (Q, \delta, F, q_0)$ for $L$. We will create another automata $D_2 = (Q \times Q \times Q \times \{0,1\}, \Delta_2, F_2, I)$.

$I = \{(q_0, q, q, 0) : q,q_0 \in Q\}$

$F = \{q, q_F, q, 0 : q_F \in F, q \in Q \}$

Let's first understand the intuition before defining the transition function $\Delta_2$:

We are constructing two layers: all the transitions in the first layer will be to some state in the second layer, and all those in the second layer will be toward the first layer.
On reading an alphabet when on a state of the form $(q_1, q_2,q_2, 0)$, the state in the first entry will change as per the transition function of $D_1$. The state in the second entry will also follow $D_1$, but it will be symbol agnostic, in the sense that it can change to any state irrespective of the symbol. The third entry will remain the same. (It is used to save the state at which we started the second pebble). The fourth entry will change from 0 to 1 which is equivalent to moving from one layer to another.
When on a state of the form $(q_1, q_2,q, 1)$, all the transitions are $\epsilon$ transitions and move us back to $(q_1, q_2',q_2, 0)$ where $q_2'$ is a state which is reachable from the state $q_2$ in $D_1$.

So in this automata, we first non-deterministically choose a start state of the form $(q_0, q, q,0)$. The state $q$ is the state from which we are reading $\beta$, and from $q_0$ we are reading the actual input $\alpha$. As the automata reads the word, for each letter of $\alpha$, we non-deterministically choose two letters for $\beta$ and run the same automata from that state in the second component. If on reading $\alpha$ we end up in the state we started reading $\beta$ (which is chosen non-deterministically), and the second component reaches a final state in $D_1$, then it means that the $\exists  \beta : \alpha \beta \in L$. And hence we accept.

Formally,
\begin{equation}
\Delta_2((q_1, q_2, q, 0),a) = \{(\delta_1(q_1, a), \delta(q_2, x), q, 1) : x \in \Sigma)\}\\
\Delta_2((q_1, q_2, q, 1),\epsilon) = \{(q_1, \delta(q_2, x), q, 0) : x \in \Sigma)\}
\end{equation}.

There is an easier way (as OP described):
Let $D_1'$ be the NFA obtained by reversing all the transitions in $D_1$ and allowing all symbols for each transitions (i.e., make it symbol agnostic). Take the states to be 3-tuples from $Q \times Q \times \{0,1\}$. Start from $(q_0, q_f, 0)$ where $q_f \in F$. On reading a letter, move from state $q_0$ as per $D_1$, and move two steps from $q_f$ according to the $D_1'$. The final states can be $(q,q,0)$ where $q\in Q$.

You can try figuring out why this works.


How would you implement truly random hash functions in practice?

The number of bits required to describe a function from $[U]$ to $[m]$ is $m \times 2^U$. This is exponential in $U$.


Gyorgy E. ReveszExercise 1.1: Show the grammar $G$ generates the language $L$

Generally speaking, you need to do two things:

Prove that every word generated by $G$ is in $L$.
Prove that every word in $L$ can be generated by $G$.

Hints for (1): Prove by induction on the length of the derivation.

Hints for (2): Prove by induction on $i$.


If a decision problem $A \in \text{NP}$ and there exists reduction so that $A \leq_p B$, for decision problem B, what can be deduced about B?

$B$ cannot be the language $\emptyset$ or the language $\Sigma^*$.  Apart from that, you can conclude absolutely nothing about $B$.

So, the given condition doesn't rule out anything useful about $B$; just about everything remains possible.  $B$ could be in $P$, or it could be in $NP$, it could be harder than anything in $NP$; you can't rule any of those out.


Show that the following construction is not a correct proof for Context Free Grammars

$ S\to aSb \mid \varepsilon $.

Hint (due to Klaus Draeger): Consider what happens when you apply transformation (ii) to this grammar. Does the resulting grammar $G'$ satisfy $L(G')=L(G)^*$?

Explanation: The point is that the $S\to SS$ production can be used "inside" the grammar, not just on the "top-level" where it is intended. We can derive $S\to^* aSSb \to^* aababb$ which is of the wrong form. (And the grammar has $S\to\varepsilon$ anyhow.)


Can you recognize or decide if a Turing Machine has an infinite sized language?

To elaborate somewhat on Yuval's comment:

(1) Some languages have an infinite number of strings, some do not. This makes the property non-trivial, and Rice's theorem says that recognizing whether the language of a Turing Machine has a non-trivial property is undecidable. This problem is undecidable.

(2) All languages are countable; none are uncountable. This makes the property trivial. Deciding whether the language of a TM has a trivial property is always decidable: if it's a property all languages have, then answer yes; if it's a property no languages have, answer no.

(A word of general caution, though it doesn't apply here. Rice's theorem applies only to properties of languages themselves, not properties of the TMs that might accept them. This is an important distinction. Rice's theorem only works for properties that have to do with the language and strings it contains.)

For reference: Rice's Theorem


similar language by two DFA then why wrong answer

First DFA does not accept $\epsilon$ which has 0 number of $b$'s which is divisible by 3 (0 is said to be divisible by 3). So first answer is incorrect, where as second is correct.


What is the complexity of a variation of the Coupon collector's problem?

When $m$ is much larger than $n$, the expected number of trials is basically linear in $n$.  We can make this more precise, as shown below.

Let $T_n$ be the random variable which counts the number of trials up to seeing $n$ different elements, where the elements are picked uniformly at random from a set of size $m$.

You can write $T_n$ as the sum of geometric random variables

$$T_n=1+G\left(1-\frac{1}{m}\right)+G\left(1-\frac{2}{m}\right)+...+G\left(1-\frac{n-1}{m}\right)$$

where $G(p)$ is a geometric random variable with parameter $p$ (number of trails up  to the first success, where success happens with probability $p$ (I leave it to you to prove the equivalence).

Using linearity of expectation:

$$\begin{align*}
\mathbb{E}\left[T_n\right]&=\sum\limits_{i=0}^{n-1}\mathbb{E}\left[G\left(1-\frac{i}{m}\right)\right]\\
&=\sum\limits_{i=0}^{n-1}\frac{m}{m-i}\\
&=m\left(\frac{1}{m}+\frac{1}{m-1}+...+\frac{1}{m-n+1}\right)\\
&=m\left(H_m-H_{m-n}\right)
\end{align*}$$

where $H_k$ is the harmonic sum, which satisfies $\frac{1}{2(k+1)}\le H_k-\ln k - \gamma\le \frac{1}{2k}$, where $\gamma$ is the Euler–Mascheroni constant (see Wolfram's page on harmonic numbers). Using these bounds for harmonic numbers we have:

$$\begin{align*}
\mathbb{E}\left[T_n\right]&\le m\left(\frac{1}{2m}+\ln m +\gamma -\left(\frac{1}{2(m-n+1)}+\ln(m-n)+\gamma\right)\right)\\
&\le m\left(\frac{1}{2m}+\ln\frac{m}{m-n}\right)=\frac{1}{2}+m\ln\frac{m}{m-n}.
\end{align*}$$

Note that $m\ln\frac{m}{m-n}=m\ln\left(1+\frac{n}{m-n}\right)\approx n$ when $n\ll m$, so for $m$ much larger than $n$, the expected number of trials is linear in $n$.


Proof of a lower bound of the recurrence relation (the CLRS's 4.6-2 exercise)

All we need to prove is the following, where $b>1, k\ge 0$ and $k$ may or may not be an integer.
$$\sum_{j=0}^{\lfloor\log_b n\rfloor} \left(\log_b\left(\frac n{b^{j}}\right)\right)^k=\Omega((\log_b n)^{k+1})$$

In order to show the idea of the proof clearly, assume that $n = b^m$. The above estimate is
$$\sum_{j=0}^{m} (m-j)^k=\Omega(m^{k+1})$$

Here is the proof.

$$\sum_{j=0}^{m} (m-j)^k=\sum_{i=1}^m i^k\ge\sum_{i=1}^m \int_{i-1}^{i} u^k du=\int_{0}^{m} u^k du = \left.\frac{u^{k+1}}{k+1}\right |^m_0= \frac{m^{k+1}}{k+1} $$


Partition a bipartite graph to a complete matching and an independent set

This question was subsequently posted on Math.SE. It received a complete answer by Zur Luria which I am quoting here.

I think I can prove your conjecture using Hall's theorem.
First of all, any perfect matching is also an envy-free matching, so if $G$ satisfies Hall's condition then there is an envy-free matching.
Otherwise let $S \subseteq X$ be a maximal subset such that $|N(S)|<|S|$. If $S=X$ then any $y$ that isn't in $N(S)$ isn't wanted by any $x$. If $|S|<n$ then the subgraph of $G$ on the vertices$X\smallsetminus S,Y \smallsetminus N(S)$ satisfies Hall's condition (otherwise we can make $S$ larger), and so it has a matching that matches all of the vertices in $X\smallsetminus S$. This matching is envy-free.


How does TCP manage to discard segment received from a source other than the one with which the connection has been established?

"Stripped away" is not strictly correct. A TCP packet is an IP header followed by the TCP-specific data. The IP-level information is needed, and used. In particular, the source IP address is needed (as you say) to decide which currently open TCP conversation should receive the packet that has just arrived.


References on teaching introductory programming courses

Here's a survey paper and there are others.

You might want to consider the inverted method also known as outside-in, which differs from the traditional bottom-up approach.

This article on the application of problem-based learning to first year programming reports some successful results, mainly in terms of secondary skills learned by students. The cost is a major investment and restructuring by those involved.


Steps to create a heuristic for solving a problem

There is no general method. Like all mathematics, algorithm design, programming, etc., coming up with heuristics is a creative act which requires you to use your intelligence and understanding of the problem domain.


How to find longest recurring pattern from lage string data set?

This problem is well-studied; it's aptly called longest repeated substring problem.

It can be solved in linear time by creating a suffix tree with Ukkonen's algorithm; the longest repeat corresponds to the labelling of the longest path from the root to an inner node which you find using breadth-first search.

This does not exclude overlapping substrings. Keep track of the smallest $m$ and largest $M$ starting index of sequences nodes represent while creating the tree; a node at depth $n$ (counted in symbols on the path) represents a non-overlapping repeat if and only if $M - m \geq n$.


What is the use case of multi-type-parameters generic interface?

The most typical usecase I've encountered is generic idea of container, parameterized by both the container type and contained type. F.e. you can describe generic type class of containers providing get/set/delete operations for arbitrary types providing hash() operation.

Even more complicated usecase is type+container+monad, involving concrete monad where all update operations on the container occur, but this is mainly interesting in the Haskell realm.


error computation in multi layered perceptron

How do we get that $\delta_{ok}$?

You calculate the gradient of the network . Have a look at "Tom Mitchel: Machine Learning" if you want to see it in detail. In short, your weight update rule is

$$w \gets w + \Delta w$$
with the $j$-th component of the weight vector update being
$$\Delta w^{(j)} = - \eta \frac{\partial E}{\partial w^{(j)}}$$
where $\eta \in \mathbb{R}_+$ is the learning rate and $E$ is the error of your network.

$\delta_{ok}$ is just $\frac{\partial E}{\partial w^{(o,k)}}$. So I guess $o$ is an output neuron and $k$ a neuron of the last hidden layer.

Where does the chain rule play a role?

The chain rule is applied to compute the gradient. This is where the "backpropagation" comes from. You first calculate the gradient of the last weights, then the weights before, ... This is done by applying the chain rule to the error of the network.

Note

The weight initialization is not only small, but it has to be different for the different weights of one layer. Typically one chooses (pseudo)random weights.

See: Glorotm, Benigo: Understanding the difficulty of training deep feedforward neural networks


What does this mean: "The compile-time and load-time address-binding methods generate identical logical and physical addresses"?

What your TB says is absolutely correct & the answer is the latter i.e. the second interpretation.
More particularly:

The logical address & the physical address generated in the compile-time address binding scheme are the same.
The logical address & the physical address generated in the load-time address binding scheme are the same.

Why?
Context:

Definition of Logical address: A logical address or virtual address is an address that is generated by the CPU during program execution. - afteracademy

Definition of Physical address: physical address refers to a memory address or the location of a memory cell in the main memory - Techopedia

The compile-time binding is used when the base address of the process memory allocation is known before hand i.e. " a priori ". This never happens in real-life because you never know any mechanism/system to predict what the addresses will be at the time of writing the program itself.
However, in case that really happens (How? Static allocation / magic), the address generated by compiler (i.e. the logical address/virtual address) is indeed the actual physical address because the programmer hard-coded the addresses.
Similar (but not same) is the case with Load-time binding.


k-th smallest element in sliding segment

Maintain an AVL tree $B$ that stores the elements in $l$.
In addition, for each element $a$ in $l$, keep a pointer $p_a$ to the corresponding node in $B$.

When an element $x$ is added to $l$, then simply insert a new node $v$ representing $x$ into $B$ and make $p_x$ point to $v$.

When the first element $y$ of $l$ needs to be removed, delete (the node pointed by) $p_y$ from $B$.

To report the $k$-minimum element in $l$, simply look for the minimum element in $B$ (i.e., the one stored in the leftmost node). This can be done in $O(\log n)$ time by just keeping, in each node $v$, the size of the subtree of $B$ rooted in $v$.

By combining the above operations, each turn of your problem will require $O(\log(1 + |l|)) = O(\log n)$ time.


Designing CFG that accepts a^n b^m (n<m<2n)

Try this to remove the two cases the first time :

$$S\to aAb$$
$$A\to aCbb$$
$$C\to aCb|aCbb|\lambda$$

If you go to $A$ you cannot have $a^nb^{2n}$ and while going from $A$ to $aCbb$ you are removing the possiblity to get $a^nb^n$.


Big O notation is nothing other than dividing functions into classes based on their asymptomatic growth behavior. What those functions are a measure of is entirely independent of Big O.

Big O is most commonly used to classify the function that maps an input size to the longest time an algorithm runs on any input of that size. But it could be used instead for average running time or shortest running time, or to measure space usage, cache misses, messages sent over the network, etc.

We use big O because we don't generally care about the exact value of these functions, just about how fast they grow. It's an abstraction that lets us see the general pattern but omits constant and lower order factors.


Dijkstra's algorithm for edge weights in range 0, ..., W

This is the algorithm I know of that is $\mathcal{O}(|E| + W|V|)$. Some things to note:

$C$ is defined as the maximum cost of any shortest path that leaves $s$ (the source). It is at most $W|V|$.
Each $L[i]$ is a doubly-linked list. The $L[i]$ keep track of all vertices that are currently at distance $i$ from the source.
$d[v]$ is the shortest distance (so far) from the source to vertex $v$

Each edge and vertex of the graph will be visited only once, and the outer loop runs in time $\mathcal{O}(C)$, therefore the complexity of the algorithm is $\mathcal{O}(|E| + |V| + C)$. Since $C \leq W|V|$, this reduces to $\mathcal{O}(|E| + W|V|)$.

L[i] <- {}, 0 <= i <= C
L[inf] <- {}
L[0] <- {s}

for v in V do
    push v into L[inf]
    d[v] <- inf
end

d[s] <- 0
p <- 0
while p < C do
    while L[p] != {} do
        pop v from L[p]
        for (v, u) with d[u] > d[v] + w(v, u) do
            remove u from L[d[u]]
            d[u] <- d[v] + w(v, u)
            push u in L[d[u]]
        end
    end
    p <- p + 1
end


Assumption of a generation of the dataset by a probability distribution

The main takeaway from this paragraph is that the authors assume that the training data and test data are sampled i.i.d. from the same distribution, because then if we are able to estimate some statistic of the distribution we sample the training data from, we will be able to do the same on the test data.

As for your specific points:

  1) How probability distribution is generating a dataset?

We sample from a large set according to some distribution. The precise method depends on the problem.

  2) Are the generation process and probability distribution the same?

No, the generation process provides a sample from a distribution. A probability distribution is an abstract mathematical object, while a generation process is a specific algorithm that provides a dataset. In a way, the distribution provides a probabilistic description of what the generation process should return.

  3) What is the sample space and random experiment for the underlying probability distribution?

The sample space depends on the problem in question. I'm not sure what you mean by 'random experiment', but the definition of the random distribution is problem-specific.


Traversing the edges of a labeled 2-regular graph based on a binary string

Note that a 2-regular graph is a disjoint union of cycles. Since you have a designated starting vertex $v$, you can disregard all cycles not containing $v$. Put differently, we can assume that the input graph is a single cycle (whose edges are labeled with zeros and ones).

Your current $\Theta(\ell)$ solution is optimal since even reading the input requires time linear in $\ell$, i.e., there exists no faster algorithm.

As a side note, the problem of finding an alternating 01-path is NP-hard for the general graph. Indeed, looking for such a path of length $m = |E|$ is equivalent to finding an alternating Hamiltonian path which is known to be NP-hard. This problem is easy for cycles of course.


"
    Pre: stack is empty or contains only integers
    Post: Stack top is non-negative Integer
    P:  Stack top is an Integer   ( P is the invariant )
    BB: Stack top is negative
    T:  Stack size
"

" Establish P "
stack size > 0 or: [stack push: 0].
[ stack top negative
] whileTrue:
    [ " reduce T "
      stack pop.
      " restore P "
      stack size > 0 or: [stack push: 0]
    ]
" P && non BB => Post "


Why is unification so important to inference engines?

Unification is such a fundamental concept in computer science that perhaps at time we even take it for granted. Any time we have a rule or equation or pattern and want to apply it to some data, unification is used to specialize the rule to the data. Or if we want to combine two general but overlapping rules, unification provides us with the most general combined rule. Unification is at the core of

Theorem provers and proof assistants, include some based on higher-order unification.
Prolog implementations (as Resolution).
Type inference algorithms.
Computational linguistics/natural language processing.
Term rewriting systems such as Maude,  which can be used as the basis of programming language semantics.
Deductive databases.
Expert systems or more generally Artificial intelligence.
Computer algebra systems.
Pattern matching in functional languages (at least in part ... only matching).
Some parsing approaches.
Some query languages, especially involving the Semantic Web.


Comparison Procedure in Robinson's Unification Algorithm

It looks like the answer is that, to be syntactically valid, composite types must be fully parenthesized.

In particular, $a \to b \to c$ is not a syntactically valid type (per definition 2A1).  2A1.1 introduces "syntactic shorthand": when they write something like $a \to b \to c$, it should be understand that they actually mean $(a \to (b \to c))$.

The Note appears to be valid when we restrict to syntactically valid types.  Thus, your example is not actually a counterexample.


The slides are correct: remember that we are trying to find a bound on the optimal value of $f$, which is defined as
$$\Phi_\mbox{min}({\cal Q}_\mbox{init}) =\min_{x\in{\cal Q}_{\tiny\mbox{init}}}f(x)$$

To find that minimum, we approximate it by upper and lower bounds $\Phi_\mbox{ub}$ and $\Phi_{\mbox{lb}}$. Let's concentrate on $\Phi_{\mbox{ub}}$. Note that if ${\cal Q}={\cal Q}_1\cup{\cal Q}_2$, then both
$$ \min(\Phi_{\mbox{ub}}(\cal Q_1),\Phi_{\mbox{ub}}(\cal Q_2))\geq\Phi_\mbox{min}(\cal Q)$$
and
$$ \max(\Phi_{\mbox{ub}}(\cal Q_1),\Phi_{\mbox{ub}}(\cal Q_2))\geq\Phi_\mbox{min}(\cal Q)$$

But we might as well take $\min$, since that is the value that is closer to the global minimum $\Phi_\min(\cal Q)$!

In fact, taking the minimum is going to be necessary if we want the branch and bound method to converge to the minimum as we sub-divide $\cal Q$ into smaller and smaller pieces.


Is finding cache size possible with information given?

An n-way set associative cache can store n different entries for a given index in the cache array.  So the 8-way acts like an 8x multiplier as compared with a direct mapped cache (1-way set associative).

So, I would take it that the line size of 24 with 26 lines per set and 23-way set associative is 213 or 8k bytes.

A next question might be how big are the tags that are stored in the associations?   22 (from the address space) - 4 (for cache line size) - 6 (the number of entries in the array), means that a tag size of 12 bits is needed.


Compute e^x given starting approximation

The obvious answer to "I have an approximate solution to an equation and I want to improve it" is Newton-Raphson. If you have an approximation $y \approx e^x$ then you can improve it to $$y' = y - \frac{(\ln y) - x}{y^{-1}} = y(1 + x - \ln y)$$

Now you need an efficient way of calculating $\ln y$, but here I note that Wikipedia, commenting on high precision logarithms, says (my emphasis):

  Another alternative for extremely high precision calculation is the formula
  $$\ln x \approx {\frac {\pi }{2M(1,4/s)}}-m\ln 2,$$
  where $M$ denotes the arithmetic-geometric mean of $1$ and $4/s$, and
  $$\displaystyle s=x2^{m}>2^{p/2},$$
  with $m$ chosen so that $p$ bits of precision is attained. (For most purposes, the value of $8$ for $m$ is sufficient.) In fact, if this method is used, Newton inversion of the natural logarithm may conversely be used to calculate the exponential function efficiently.

The references given are Practically fast multiple-precision evaluation of log(x), Sasaki and Kanada (1982), Journal of Information Processing 5(4) pp247–250; and Fast Computations of the Exponential Function, Ahrendt (1999), Stacs Lecture Notes in Computer Science 1564 pp302–312.


Find a continuous path filling whole 3xN grid going through certain points in given order

Hint: if this is a homework problem that comes up in a chapter on graphs, you might want to consider forming a graph.

A common pattern in applications of graphs is to let each node in the graph represent the "state" of the world at some point in time, and then use that graph somehow.

Suppose you're following some continuous path through this grid, and at some point in time in the middle of your traversal, I yell "freeze!", temporarily pause time, and look at the state of the world at that point in time (ignoring past or future).  What information do I need to record, to fully describe the state of the world (where you are) at that point in time?  How many different possible states are there?  Now create a graph where ..., and.....  (you fill in the rest)


Time complexity of quicksort for arrays in increasing or descreasing order

Quicksort is just an idea. There are algorithms and implementations.

Only stupid implementations will run in O(n^2) for sorted or reversed sorted arrays. Good sorting implementations actually check for elements in ascending or descending order at the beginning and end of the array and will handle either case in O(n), because wanting an array sorted without checking that it is sorted before is such a common case. Such implementations will fall back on Quicksort for handling the more difficult parts.

(It’s not just sorted arrays. You can have a general algorithm that sorts the concatenation of two sorted arrays in O(n), or a sorted array with fewer than O(n / log n) random elements added, or a sorted element with one random element changed).


If the grammar is not LL(1), can we say that grammar is ambiguous?

Euh, no. A grammar is unambiguous if for every word in its language there exists exactly one derivation-tree for it in the grammar.

Parsing is a way to find that derivation, given the string, preferably in some efficient way. Several classes of grammars were defined that have efficient parsing methods, for example LL(1) grammars.

A grammar can be non-LL(1), and still be unambiguous. For instance when we reverse an LL(1) grammar (that is, take the mirror image of the RHS of every production) the result still is unambiguous: mirroring the original unique derivation trees. But it cannot be parsed in an LL fashion, rather its reverse...


Some questions regarding decidability and semi-decidability of $A/B = \{ w \text{ | }\exists z \in B, wz \in A\}$

Let $\Sigma$ be your alphabet. You want to design a Turing machine $T$ such that, given any word $w \in \Sigma^*$, $T(w)$ accepts if and only if $w \in A / B$. Notice that since you only want to prove that $A/B$ is semi-decidable, $T(w)$ is not required to reject when $w \not\in A / B$.
Since $A$ and $B$ are decidable, you know that there are two Turing machines $T_A$ and $T_B$ such that that $T_A(x)$ (resp. $T_B(x)$) accepts if $x \in A$ (resp. $x \in B$) and rejects otherwise.
You can then design $T$ as follows:

For each word $z \in \Sigma^*$:

If $T_B(z)$ accepts and $T_A(wz)$ accepts:

Accept.


Proving $\{ a^n b^m \mid n \leq m^2 \}$ is not context-free using pumping lemma

When $vwx = a^j b^k$, there are two possibilities:

$v$ contains both $a$s and $b$s, or $x$ contains both $a$s and $b$s. In this case $uv^2wx^2y \notin a^*b^*$, and in particular $uv^2wx^2y \notin L$.
$v = a^s$ and $x = b^t$, where $s,t>0$ and $s+t \leq p$ (since $|vwx| \leq p$). In this case, $uv^0wx^0y = a^{p^2-s}b^{p-t}$, and so $p^2 - s \leq (p-t)^2 \leq (p-1)^2$, which translates to $s \geq 2p-1$, which is impossible, since $s \leq p-1$.


The definition of weakest precondition for a non-deterministic language

First of all, the definition of weakest precondition you've mentioned might be a little bit confusing. Namely, remember that the weakest precondition, designates all states of a program, such that when the given command executes, the given postcondition is satisfied.

Therefore, your initial definition might be a bit confusing, in the sense that the weakest precondition wp(s, Q) is determined really based on a postcondition (which you have as Q) and a command (which you have a c) -- that is all that is needed to define weakest precondition (w.p.).

Having that said, a more natural definition of wp(c, Q) says that:
$$
wp(c, Q) = \{ \sigma \in \Sigma | \text{ex}[c, \sigma]  \models Q \}
$$
the weakest precondition, given c and Q, is a set of all states, such that executing c (denoted simply by ex here) from those states, assuming the execution terminates (we will come back to that later), will lead to some state $\sigma$ for which the postcondition Q is satisfied.

Given that, the weakest precondition you've mentioned, namely

  "wp (c1;;c2) Q s = wp c1 (wp c2 Q) s"

is a valid formulation for w.p. for compositions, as, naturally, executing c1 you want to end up in a state belonging to the weakest precondition of wp(c2, q), which, in turn, means that after further executing c2 (in the sequence) you will have to satisfy postcondition (again, with the assumption that both terminate).

Now, in terms of this weakest precondition formulation, while the quote

  ensuring that execution of S terminates in a final state satisfying R

might confuse you, this does not say that termination is encoded in the w.p. formulation. Specifically, it is not required: the definition of weakest precondition says, that, if the given command executes and terminates, from those states, the postcondition has to hold.

That is why this is part of something traditionally called "partial correctness" and not "total correctness", as it does not prescribe termination (but rather, effectively, works under assumption of termination).


Is there evidence that using dynamic languages has an impact on productivity?

While I'm not aware of research on productivity, there's been research on comprehension. Philip Wadler has been collecting links to papers on this topic: see this post and this one.


the height of a tree given n nodes and a condition

The height of a tree is 1 + the height of its highest subtree. Which way of distributing the nodes to the subtrees will allow you to maximize that parameter?

   Put $\frac 13 n$ nodes into the left tree and $\frac 23 n$ into the right one (or vice versa).

If you apply this recursively, what do you get for the height?

   You get the recurrence $h(1) = 1$, $h(n) = 1 + h(\frac 23 n)$, $n>1$. This solves to
 $h(n) = 1+\log_{\frac 32}n$.


Increased rounding relative error when subtracting

On the other hand, $x−y$ has increased relative error.

The correct conclusion should be $x-y$ may have increased relative error. In other words, $x-y$ may have decreased relative error.

Let us review what is absolute error and relative error in scientific computing.

The absolute error in approximating $x$ by $\hat x$ is $e = e_x= e_{x, \hat x}= \hat x − x$. The relative error is $\epsilon =\epsilon_x=\epsilon_{x,\hat x}=\dfrac ex$, a dimensionless measure of error which is usually considered more informative.

Yuval has shown an extreme example where the relative error becomes 0. Here are a few more examples on the relative error of approximating $d=x-y$ by $\hat d =\hat x-\hat y$.

$x=2$, $\hat x=2.04$, $y=1$, $\hat y = 1.03$. Then $\epsilon_x = 0.02$, $\epsilon_y=0.03$, $d=1$, $\hat d=1.01$, $\epsilon_d=0.01$.
$x=4$, $\hat x=4.04$, $y=1$, $\hat y = 0.95$. Then $\epsilon_x =0.01$, $\epsilon_y=0.05$,  $d=3$, $\hat d=3.09$, $\epsilon_d=-0.03$.
$x=21$, $\hat x=21.4$, $y=20$, $\hat y = 20.2$. Then $\epsilon_x \approx 0.019$, $\epsilon_y=0.01$,  $d=1$, $\hat d=1.2$, $\epsilon_d=0.2$.
$x=2100$, $\hat x=2140$, $y=2098$, $\hat y = 2096$. Then $\epsilon_x \approx 0.019$, $\epsilon_y\approx0.00095$,  $d=2$, $\hat d=44$, $\epsilon_d=22$.

We can make several observations.

The example 1 shows the relative error of the difference can be smaller than both original relative errors while example 2, 3 and 4 demonstrate the absolute value of the relative error can be bigger than one or both of the original relative errors. In particular, the example 4, where $\epsilon_d = 2310\max(\epsilon_x, \epsilon_y)$ illustrates the relative-error explosion where the relative error can go wildly larger when the two original values, which are 2100 and 2098 here, are near to each other.

Exercise 1. Let $x=cy$ for $x, y>0$. Let $\hat x=x(1+\epsilon_x)$, $\hat y = y(1+\epsilon_y)$. Let $d=x+y$ and $\hat d=\hat x+\hat y$. Then $$|\epsilon_d|\le\max(|\epsilon_x|,|\epsilon_y|)$$

Exercise 2. Let $x=cy$ for $x, y>0, c>1$. Let $\hat x=x(1+\epsilon_x)$, $\hat y = y(1+\epsilon_y)$. Let $d=x-y$ and $\hat d=\hat x-\hat y$. Then $$|\epsilon_d|\lt \frac {2c}{c-1}\max(|\epsilon_x|,|\epsilon_y|)$$


Uniformly random efficient sampling of shortest s-t paths, with optimal random bits

D. W. computes for each node $v \in S$ the number of paths $n(v)$ from $v$ to $t$. Using this information, it is easy to decode a number in the range $[0,n(s))$ to a unique path from $s$ to $t$ in $S$ (and so in the original graph). More generally, at each node $v$ we will come up with a procedure to map $[0,n(v))$ to a unique path from $v$ to $t$. Let the children of $v$ be $v_1,\ldots,v_k$. The idea is to write
$$ [0,n(v)) = [0,n(v_1)) \cup [n(v_1),n(v_1)+n(v_2)) \cup \cdots [n(v_1)+\cdots + n(v_{k-1}), n(v_1)+\cdots+n(v_k)), $$
and use the $i$th component to encode paths going through $v_i$. By subtracting $n(v_1) + \cdots + n(v_{i-1})$, we then reduce the problem to decoding a number in $[0,n(v_i))$ to a unique path from $v_i$ to $t$. Pseudocode left to the reader.


How do I solve these questions regarding homomorphism?

Notice the abuse of notation used. The quote overload symbol $f$ with three meanings which I will now denote differently with $f,f',f''$.
First is map from alphabet to words $$f: \Sigma \rightarrow \Gamma^*$$.
The second is the map between words $$f':\Sigma^* \rightarrow \Gamma^*$$.
The third is the map between languages $$f'':\mathbb{P}(\Sigma^*) \rightarrow \mathbb{P}(\Gamma^*)$$.

The The main point of the quote is that given $f$ there is the particular way to construct the corresponding $f'$ and $f''$. So, what one might call homomorphisms between languages $f''$ is specified by just giving map from alphabet to words $f$. And $f$ is usually easier to describe directly than $f''$.

Another important observation is that not all function of type $$\mathbb{P}(\Sigma^*) \rightarrow \mathbb{P}(\Gamma^*)$$ is a homomorphism of languages. (Because it doesn't "preserve structure" w.r.t. concatenation operation languages are equipped with.) However, the said construction is special in that given any $f$ with the correct type, $f''$ will be a valid homomorphism of languages.