The proof makes use of the pigeonhole principle.

First suppose $L(M)$ is infinite. This means that for every $k \geq 0$ there exists a $w \in L(M)$ with $|w| \geq k$. Therefore there must in particular exist a $w$ with $|w| \geq |Q|$. Take the shortest such $w$ and let $w = a_1 a_2 \ldots a_k$. When reading $w$, $M$ will visit $k+1$ states $q_0, q_1, \ldots, q_k$ where $q_0$ is the initial state and $q_k$ is an accepting state. Since $k+1 \geq |Q|$, some state must occur at least twice in this sequence: Now consider the first such repeated pair, $q_i$ and $q_j$. We have that the substring $a_i...a_j$ has length at most $|Q|$. The string $a_1 \ldots a_i \ldots a_j a_i \ldots a_j \ldots a_k$ will be accepted, and its length is at most $2|Q|$.

Next suppose there is a string $w \in L(M)$ where $|Q| \leq |w| \leq 2 |Q|$. Again consider the states that $M$ will visit when reading $w$ and let $w = a_1 a_2 \ldots a_k$. As in the proof of the converse implication above, we notice that when reading $w$, $M$ will visit $k+1$ states $q_0, q_1, \ldots, q_k$ where $q_0$ is the initial state and $q_k$ is an accepting state. Since $k+1 \geq |Q|$, some state must occur at least twice in this sequence. Again, consider the first such repeated pair, $q_i$ and $q_j$. We have that for every $m \geq 0$ that the  string $a_1 \ldots (a_i \ldots a_j)^m a_{j+1} \ldots a_k$ will be accepted, and this proves that $L(M)$ is infinite.


Dana Angluin's L* algorithm - Hypothesis inconsistent

I have no idea what it would mean for a hypothesis to be inconsistent in this context, but the answer to your second question is: No.  You won't receive the same counterexample twice.

The teacher returns a counterexample $w$.  Here a hypothesis is a DFA (a regular language) and $w$ is a word that the DFA gets wrong (either the DFA accepts, but $w$ is actually not in the language to be learned; or the DFA rejects, but $w$ is actually in the language to be learned).  Angluin's L* algorithm constructs a new DFA that is correct on all of the counterexamples that have been returned so far.  Since this DFA is correct on all past counterexamples received from the teacher, we will definitely never get the same counterexample a second time.


Solving linear programming problem with mixed type of constraints

You first need to transform this into normal form. Depending on how you learned it, you need to transform all constraints to the form $a\ge b$, or $a\le b$, where in $a$ you have variables and in $b$ only constants.
Transform $=$ into $\le$ and $\ge$ and from there you can easily transform this into normal form


Suppose the algorithm does less than $\frac{n^2-n}{2}-2(n-1)$ accesses to the matrix, then, there is at least one column (restricted to the upper triangular part of the matrix) such that there are at least two elements the algorithm have never checked.

This can be proved by contradiction, if every column has at most one unchecked element, then the algoritm have done at least $\frac{n^2-n}{2}-(n-1)$, but this contradicts the hypothesis.

Then, supposing every $a_{ij}$ element the algorithm has checked is equal to $0$, whatever the output of the algorithm, it may be wrong. Indeed, if the algorithm sais there are no paths, then, in the "doublely unchecked" column can happen that $a_{ij}=a_{kj}=1$, so there will be a path $i\to j\to k$ whose lenght is two. Otherwise, if the algorithm says there is a path, the matriz could be entirely made of $0$'s.

Note that if the graph is represented with an adjacency list for each vertex the statement does not hold, beacause there is an easy algorithm in $\mathcal{O}(n)$.


Questions regarding CPU scheduling algorithms ( Round Robin and Priority scheduling )

You had to make assumptions. Your problem is that “priority scheduling with round robin for equal priority” is not enough to specify exactly what happens.

Your scheduler will consider a change in the schedule when the running process finishes, when a new process is started with priority same or higher than the currently running process, or if the quantum is elapsed - but it’s not obvious if this is every three seconds, or three seconds after the last change in schedule. And exactly what “round robin” would pick isn’t clear.

You’d need the exact details of the scheduling algorithm.


In an arithmetic I-type command, the IMM-field is treated as a signed number. So if the first bit is 1, the number will be treated as negative (X in your terms.) The number Y is simply too large to be used as argument of an arithmetic I-type command.


Having Moore's law is it worth looking for more algorithms?

Yes.

Better algorithms, that run in less time complexity - work way better than just an increase in constant factor for large enough input, but more transistors is just a constant factor of work.
We have reached the "end" of this "law". Now we are in an era where its hard to make transistors smaller due to quantum effects on them.
Having newer and better algorithms will make programs run faster on current computers, and we wont have to always buy new ones.
Why not have both? more transistors + newer algorithms = even better performance!


computer science vs computer programming?

In some countries, for example in Latinoamerica, I found this "mixing" of terms for careers related to Computer Science, but let's consider that this is not your case and I will venture to pinpoint some differences about CS and CP that you are looking for:

Computer Science refers to the study of the theoretical part of the use of computers. Of course, that it has also its application part, but this is not directly related to programming. If you search for some articles in ACM you will find that there are a lot of authors that state that CS is not necessarily programming. If you choose this path you will be more studying topics more related to algorithms, math in its continuous and discrete flavors, statistics and so on. So I would dare to say that CS is more related to the fields I described before that only to programming.
Computer Programming, as I saw in some Universities as I said before, is more related to the technical field (or IT field according to the ACM standards). For example in a career related to this field, you will learn about the differences between Java, C, Ruby, etc., and you will increase your skills of using those tools, but not necessarily you will get a grasp of the generalities that those languages share (for example in CS you have a course called Programming Languages that deal with that).

So bottom line, CS refers to algorithms, math, theory and applications of this theory; while CP is related to the technical aspects of the different IT tools.


Is arithmetic coding restricted to powers of $2$ in denominator equivalent to Huffman coding?

You can't prove it because it's not true.

Arithmetic coding "degrades" to Huffman coding if all of the probabilities are of the form $2^{-k}$. Or, to put it another way, when the Kraft-McMillan inequality is an equality.


On the complexity analysis of quick-union in Algorithms by Sedgewick and Wayne

Yes, you are correct!
You have identified a typo in that book, Algorithms, the fourth edition by Robert Sedgewick and Kevin Wayne. Please check the errata for the first printing (March 2011) of the fourth edition.

p. 226
Printed:  in the worst case, it needs 2 N + 1 array accesses
Fixed:    in the worst case, it needs 2 N - 1 array accesses
Reported by Victoria Solomon, 15-Sep-11.


Formal definition of an empty stack accepting PDA

When the stack is finished you can go to the specified state which shows the empty stack. In addition, when you reach in a state which you found it's a solution but the stack is not empty, iterate over a "pop" action to empty the stack and finally go the empty stack state.

Hence, you can explain this PD using the defined notation.


Why is adding log probabilities considered "numerically stable"?

A "numerically stable" method calculates a result in a way that will not produce excessive rounding errors.

Given a small number x, let's say x = 0.00079, it is possible to calculate log (1 + x) with much higher precision than 1 + x. (Of course calculating log (1 + x) avoids adding 1 + x). In both cases the relative error will be small and about equal size, but since the logarithm is very small, it's absolute error is much smaller.

So if you want to calculate the product of values $1 + x_i$ for many small i, then you use a clever method to calculate $log (1 + x_i)$, add those values, and calculate the exponential. With probabilities, it is possible that you have say 1,000,000 events each with small probability $p_i$, and the probability that none of the events happens is the product of $1 - p_i$, and calculating that probability is more precisely done by adding logarithms (you would also keep the rounding errors down by always adding the two smallest values).

In other situations, using logarithms can be less precise. For multiplication, the relative error is independent of the size of the numbers. But if you add logarithms, and say their sum is around 100, then each addition loses precision because 7 bits of the mantissa are used to store the 100. The precision of your result will be much less. So it's quite the opposite of numerically stable.

Start with x = 1, y = 0. Then for i = 1 to 100, multiply x by i, and add log i to y. Then for i = 1 to 100, divide x by i, and subtract log i from y. Except for rounding errors, you should end up with x = 1 and y = 0. Check how much the difference is.

PS. How do we calculate log (1 + x) without calculating 1 + x? There is the power series around 1, $ln (x) = (x-1) / 1 - (x-1)^2 / 2 + (x-1)^3 / 3 ...$.  If we substitute 1 + x, then $ln(1 + x) = x / 1 - x^2 / 2 + x^3 / 3 ...$, which is obviously calculated without ever calculating 1 + x.

That's an important lesson: Given a problem that suggests an obvious sequence of steps to solve it, you will very often find a better and less obvious solution. To calculate log (1+x), the obvious sequence of steps is to calculate y = 1+x, z = log (y), but there is a much better solution that completely avoids the first step.


The space complexity of a function that allocates space based on the input value and not size

It is $O(n)$ and, more precisely, $\Theta(n)$.
What might be confusing you is the fact that the length of the encoding of the parameter $n$ will only be $\Theta(\log n)$, meaning that the value of $n$ (and hence the space required by the function) is exponentially larger than the size of the input to function (i.e., the number of bits needed to represent $n$).

To summarize both the following statements are true:

function(n) requires linear space w.r.t. the value of its parameter $n$, i.e., the asymptotic space complexity of function(n) is $O(n)$;
function(n) requires an exponential amount of space w.r.t. the length of the encoding of its input.


Find the intersection point between two sorted arrays with unknown lengths in lesser than O(n)

We need to first find the length of array in long time as it is not given.

Start with length as 1 and increase it as multiple of 2.
Check whether element at length-1 position is positive or not.
If so repeat steps 1 and 2.
If not return the index position it will be the maximum size of the array. As it is mentioned beyond the maximum position element value is negative.
Once the length of array is known simple binary search alto will be applied to search element and it will be searched in both the array and intersection point will be determined.


PCP when upper and lower words have different length

The problem doesn't become any easier.
Suppose we are given an instance $a_1,\ldots,a_n,b_1,\ldots,b_m$ of PCP.
Let $\sigma$ be a new symbol. Add to the first list the words $a'_1 = \sigma a_1,\ldots,a'_n = \sigma a_n$, and to the second list the word $b'_0 = \sigma$.
If the new PCP instance has a solution, then we can obtain a solution of the original PCP instance by removing all occurrences of $\sigma$. Now suppose that the original PCP instance has a solution
$$ a_{i_1} \ldots a_{i_s} = b_{j_1} \ldots b_{j_t}. $$
If $s \neq t$ then this is a solution of the new PCP instance in which $s \neq t$. If $s = t$, then consider the following solution instead:
$$ a'_{i_1} \ldots a_{i_s} = b'_0 b_{j_1} \ldots b_{j_t}. $$


This word problem over groupoid is a nice example to show the essence of dynamic programming, the recognition of the subproblems. In other words, how can we define the table or the multi-dimensional array that we should fill?
In general, the subproblems should represent the computations that will be repeated many times in a brute-force algorithm. The subproblems should be refined enough so that we can solve the larger subproblems from the solutions of the smaller subproblems. Please take a moment to appreciate how the subproblems are defined below.
Compute $dp[i][j]$, the set of all possible values of $x_{i}x_{i+1}\cdots x_j$, where $1\le i\le j\le n$.
The goal element $a$ is a possible value of $x$ if and only if $dp[0][n]$ contains $a$.
How to compute $dp[i][j]$?
The base case, $dp[i][i]$ is the set of a single element, $x_i$.
How about the case when $j\ge i+1$? Note a parenthesization of $x_ix_{i+1}\cdots x_j$ means to parenthesize it into two parts, $(x_i\cdots x_t)(x_{t+1}\cdots x_j)$ for some $i\le t\lt j$, followed by a parenthesization of the front part $x_i\cdots x_t$ and a parenthesization of the behind part, $x_{t+1}\cdots x_j$. So $dp[i][j]$ contains all products of the form $f\cdot b$, where $f$ is a possible value of the front part and $b$ is a possible of the behind part. Note both the front part and behind part are shorter than the whole, $x_ix_{i+1}\cdots x_j$.
In other word, in order to compute $dp[i][j]$, we can iterate $f$ through all elements in $dp[i][t]$ and $b$ through all elements in $dp[t+1][j]$, adding the product $f\cdot b$ to $dp[i][j]$.
There are $n(n-1)/2$ choices for $i$ and $j$. There are at most $n$ choices for $t$. There are at most $k$ choices for $f$. There are at most $k$ choices for $b$. Depending on the implementation, it takes $O(k\cdot k\cdot k)$ or much less time to compute product $f\cdot b$ and add it to a set of at most $k$ elements. Hence the time-complexity of the algorithm is polynomial in $n$ and $k$.


How do I do a biased shuffling of a deck of cards?

I needed this same thing, a biased shuffling for local/proximity shuffling, but couldn't find any answers, so this is my attempt to create one.
Pseudocode:
For X passes through the array from 0 to len(array)-1:
    Roll for a 50% chance to swap index and index+1
    Swap direction of array traversal

Python:
import numpy as np
import matplotlib.pyplot as plt

swap_passes = 50

player_count = 100

positions = {}

player = np.arange(1,player_count+1)
for p in player:
    positions[p] = []

for i in range(10000):
    player = np.arange(1,player_count+1)

    for j in range(swap_passes):
        pre_rand = np.random.randint(0,2,player_count)
        if j%2 == 0:
            for i in range(len(player)-1):
                if pre_rand[i] == 0:
                    player[i], player[i+1] = player[i+1], player[i]
        else:
            for i in range(len(player)-1,0,-1):
                if pre_rand[i] == 0:
                    player[i], player[i-1] = player[i-1], player[i]

    for idx, p in enumerate(player):
        positions[p].append(idx)

fcs = [(1,0,0,0.3),(0,1,0,0.3),(0,0,1,0.3),(0.5,0.5,0,0.3),(0,0.5,0.5,0.3)]
plt.figure()
for idx, i in enumerate([1,30,50,70,100]):
    bins = np.arange(0,player_count+1)
    plt.hist(positions[i], bins=bins, fc=fcs[idx])
plt.title('Histogram of indices: 1, 30, 50, 70, 100. 10000 trials, 50 swap passes.')

Results:

Looks roughly gaussian. Increasing the number of passes will increase the spread of the distribution.


Can each VLIW sub-instruction execute any instruction?

Usually, VLIW instruction sets dedicate bit fields to functional units  (not necessary multiples of bytes, or the same width for all units), and when some parts are unused, they are configured as NOPs.

Of course, there are exceptions, sometimes execution units are coupled, or special configurations are provided for long immediates... There is no absolute rule.

You should look at sample implementations, like the 48bits SHARC DSPs, or the ST200 family.


There are several protocols actually:

SPF Sender Policy Framework is used to verify that the e-mail address used to send the message is valid e.g. if the sender had rights to use the given domain.
Recipients can verify this by checking the ips of the agent dropping the mail against the allowed ips listed in the domain DNS records.
DKIM DomainKeys Identified Mail is used to verify that a given message hasn't been tampered in transit.  Recipients can verify this using the public key of a given domain along with the signature included in DKIM signed e-mails.

These are actively used in SPAM filtering.  You can see it in action by looking at the headers of most e-mails today.  You can look for the headers: Authentication-Results, DKIM-Signature, Received-SPF.


Utilization of static evaluation functions in chess

There are simple ways to do so but it may not be a very good heuristic. For example going off of current piece valuation is very simple but leads to poor aggressive behavior. There are many other things to account for in addition to piece valuation like centrality and pawn structure that when included, is subjectively simple. See https://chessprogramming.wikispaces.com/Evaluation for more notes on evaluation and for general chess programming advice.

Regarding your side note: 'Those things' end based on your heuristic function. Yes you get a board valuation that is used to determine how good a move is, guiding your game tree search.


What are the differences between symbolic execution and SAT solvers?

TL;DR: They differ in their basic input and output. SAT and SMT solvers don't know what programs are; they are tools that answer yes or no questions about mathematical formulas. Symbolic execution, on the other hand, is a method of analyzing programs. Symbolic execution usually relies on SAT and SMT solvers, but not the other way around.

SAT and SMT solvers don't directly have anything to do with programs. Instead, a SAT or SMT solver takes as input a mathematically described "formula", and answers, roughly, whether it is true or false. (Often a third option is allowed, unknown, for cases where the solver is unable to figure out an answer.)
For example, a possible input to a SAT solver is (a and not b) or (not a and c). That is, it is a mathematical formula, where a, b, and c here are Boolean (0 or 1) constants. The SAT solver is supposed to decide if it is possible for the formula to be true, by choosing values of a, b, and c. SMT solvers are similar, but a, b, and c would be replaced by more complex formulas using integers, strings, functions, etc., for example x + 3 = y^2.

Symbolic execution is a fancy way of running a program, but not how the program was intended to be run. Instead, the program is run using so-called "symbolic" values, which are kind of like placeholders. For an example of what that means, suppose I have a function like f(x) = if x > 0 then 1 else 0. Now, normally, I would run the program by inputting, say, 3, and get f(3) = 1, since 3 is greater than 0. With symbolic execution, I run the program by inputting a placeholder variable, input, and I evaluate the program to get two cases: either input > 0 and answer = 1 or input <= 0 and answer = 0. This may seem useless, but it ends up being a powerful way of analyzing programs.

The connection between the two is that symbolic execution often relies on SMT solvers during execution, to figure out if a certain path is actually possible, or if it should be discarded. For example, an SMT solver could be used to determine if input <= 0 and answer = 0 is possible (the answer is yes, for example if input = 0).  In this way, SMT is kind of the "driving force" behind what makes symbolic execution feasible.


Decisional problems vs Optimization problems : NP-COMPLETE vs NP-HARD

NP-hardness is a category that applies to both decision problems and optimization problems. In contrast, NP-completeness is a category that applies only to decision problems.

Here are the relevant definitions:

A decision problem is in NP if it is accepted by some polynomial time nondeterministic Turing machine.
A decision problem is NP-hard if all problems in NP can be reduced to it in polynomial time.
A decision problem is NP-complete if it is both in NP and NP-hard.
An optimization problem "max $f(x)$ subject to $x \in X$" is NP-hard if the decision problem "given $x$ and $y$, does there exist $x \in X$ such that $f(x) \geq y$?" is NP-hard.
An optimization problem "min $f(x)$ subject to $x \in X$" is NP-hard if the decision problem "given $x$ and $y$, does there exist $x \in X$ such that $f(x) \leq y$?" is NP-hard.

The decision problems used to define NP-hardness for optimization problems are known as decision versions of the optimization problems.

One could extend the definition of NP to optimization problems in various ways. For example, we could say that "max $f(x)$ subject to $x \in X$" is in NP if its decision version is in NP. This would also allow us to define NP-completeness for optimization problems. But for some reasons these definitions are not standard.

Let me also mention FNP, an extension of NP to functions.


How do we find the optimal modulus q in Rabin-Karp algorithm?

The Rabin-Karp algorithm looks for a substring by computing a rolling hash, of the form $h(a_{n - 1} a_{n - 2} \ldots a_0) = \sum_{0 \le k \le n - 1} a_k q^k$ for a prime $q$. Note that the algorithm works just the same if $h$ is computed modulo the word size, so using e.g. unsigned int in C would be wise. What we'd like is $q^{n - 1}$ not too large (so the needed $q^{n - 1} a_{n - 1}$ doesn't overflow, and computations are in normal unsigned integers). Clearly $n$ (the length of the pattern) is limiting here, so you want a smallish prime. One option is to use the largest prime $q$ such that if $w$ is the word size and $A$ the largest character value (for UTF-8 it's essentially $2^8$)
$$
2^w > q^{n - 1} A
$$
This guarantees no collisions, but is very restrictive.
Perhaps just taking $q = 3$ or $q = 5$ is enough (the hash value is still a full word, so collisions should be rare anyway). As they have just 2 bits one (Fermat primes, next one is 17, then 257), perhaps the compiler (or even the programmer) replaces the multiplication by the constant prime by shift and add, but if that is a net gain depends on architecture...

Note that the cited article says this makes sense only for multiple pattern search, as there are faster alternatives for single patterns.

To really answer you'd have to run tests with representative haystacks and patterns


Why does MergeSort have O(n) space complexity if it splits the array log(n) times?

Yes, you can implement merge sort inefficiently, but you don’t have to.

If you sort an array, notice that you don’t need to create any copies while splitting into subarrays. You only need two integers to identify each of them. Combined with the fact that the number of nodes in the recursion tree is $O(n)$, this gives you $O(n)$ bound on space.


Why does the formula floor((i-1)/2) find the parent node in a binary heap?

Let's assume that each tier of the heap is an array.
T1 [                n0                 ]

T2 [      n1,                n2        ]

T3 [  n3,     n4,       n5,       n6   ]

T4 [n7, n8, n9, n10, n11, n12, n13, n14]

It may not be clear, but I want you to imagine that $n0$ is the parent of $n1$ and $n2$.
Likewise,  $n1$ is the parent of $n3$ and $n4$.
For example, the second tier's length is $2$.
i.e. $[n1, n2]$
Let's say $i$ is the global index of the node in question (i.e. the node's index if the entire tree were to be collapsed within a single array), and
$j$ is the local index of the node, i.e. the index of the node within its tier.
e.g. In the diagram above, if the node in question is $n3$, $i$ is $3$ and $j$ is $0$, because $n3$ is the first element in the 3rd tier.
i = global index of a node n
j = local index of a node n within the tier where the node exists
T = tier

The maximum number of nodes in a certain tier can be expressed by:
$2^T - 1$ // e.g. when you have 3 tiers, you can have at most 7 nodes, as $2 \cdot 2 \cdot 2 - 1 = 7$
This is because there are $2^{T-1}$ nodes in each tier (note: tier numbering in our example arbitrarily starts from $1$, not $0$) and the sum of powers of $2$ up to $n$ is equal to $2^{n+1} - 1$, as you can see here https://math.stackexchange.com/questions/1990137/the-idea-behind-the-sum-of-powers-of-2
This means that the global index of the last node in the tier is:
$i_{last} = 2^T-1-1$
While the local index of the last node in the tier is:
$j_{last} = 2^{T-1} - 1$ // since there are $2^{T-1}$ elements in tier $T$
We can now compute the global index of the first node in the tier by subtracting the local index of the last node in the tier from its global index:
$i_{first} = i_{last} - j_{last}$
$i_{first} = 2^T - 1 - 1 - j_{last}$
$i_{first} = 2^T - 1 - 1 - (2^{T-1} - 1)$
$i_{first} = 2^T - 2^{T-1} - 1$
$i_{first} = 2*2^{T-1} -2^{T-1} - 1$
$i_{first} = (2 - 1)*2^{T-1} - 1$
$i_{first} = 2^{T-1} - 1$
We can now compute the global index of a node $n$ by adding its local index and the global index of the first node in its tier:
$i = i_{first} + j$
$i = 2^{T-1} - 1 + j$
Let's now think about the parent of the node in question.
The parent, n', will be in the previous tier, T-1.
The indices in T-1 will be referred to as i', j', i'_first ...

Based on what we've shown so far, we can say that the global index of the parent node in the previous tier is:
$i_{first}' = 2^{T-1-1} - 1$
Now, for every 2 predecessor(left sibling) of the node $n$ in tier $T$ there will be 1 predecessor(left sibling) of parent node $n'$ in $T-1$. Also, given index $j$ in $T$, we know there are $j$ predecessors(left sibling) of $n$ in $T$ - i.e. the index of a node is equal to the number of its predecessors(left sibling). So we can conclude that:
$j' = floor(j/2)$
Putting it all together, we can conclude that
$i' = i_f' + j'$
$i' = 2^{T-1-1} - 1 + floor(j/2)$
Now let's rework the previous equation for the global index of parent node $n$, $i = 2^{T-1}-1+j$ to the following:
$i + 1 = 2^{T-1} + j$
Finally, let's compare that to the equation of the global index of the left-child node:
$\begin{align}
i' &= 2^{T-1-1} - 1 + floor(j/2)\\
   &= 2^{T-1}/2 + floor(j/2) - 1\\
   &= floor((2^{T-1} + j)/2) - 1\\
   &= floor((i + 1)/2) - 1      \text{//NOTE: Here we use $i + 1 = 2^{T-1} + j$ mentioned above}\\
   &= floor((i - 1)/2)\\
\end{align}$


$x$ and $y$ are elements of a set $S$. For example, if $S = \{1, 2, 3\}$, we can select $x = 1$ and $y = 2$.

EDIT:
As pointed out by David below, $*$ could be multiplication or convolution, it's hard to tell from the context.

$\in$ means 'in', that is, that $x$ and $y$ are in a set. We can write 'x and y are elements of the set $S$ ' in math as:

$x, y \in S$

Again, following my example, that would be $1$ and $2$ are in the set $\{1, 2, 3\}$.

$\forall$ is verbalized 'for all'. It means for every element in the set, something is either true or false. For example:

$\forall x \in S, x < 5$ means that all of the elements in my set $S$ are less than 5.

$I$ is the identity function.

The entire phrase $I: \forall X.  X \rightarrow X$

(EDIT: removed example, as it was misleading)

means the identity function preserves the value of the variable $X$. More concretely, $I$ is the function that maps $X$ to itself. For all values of X, the output of the function is X.

Hope that helps!


Intuitive explanation of Hoare assignment axiom

Hoare Logic proceeds backwards. It is a method to compute a precondition such that the desired postcondition holds. In fact, the inference rules given in your standard Hoare Logic deductions compute weakest preconditions, or the most "specific" precondition that still guarantees that the post-condition holds at the next program point.

I think this is the salient difference. There's no comparable interpretation (of reasoning about the next program point) for backwards predicate transformers because we have to reason about the "state" before an operation given that we know its "state" after. In comparison, the alternative axiom reasons about the postcondition given a precondition.

Now, the two axioms are duals of each other, in the sense that the backwards axiom computes a weak precondition while the forward axiom computes a strong postcondition (most "general" postcondition such that all possible postconditions are subsumed). Logically, they are equivalent. Therefore, not only do we have a singular backwards intuition of the Hoare axiom, but we should also have some sort of connections between the intuitions behind the backwards axioms and those behind the forward axioms.

The intuition behind the backwards axiom: This is actually relatively easy to see, given that you know what the deduction system is doing. Let's look at the Hoare assignment rule:
$$
\frac{}{\{P : Q [x \mapsto e]\} ~x = e ~\{Q\}}
$$
which roughly says that the weakest precondition of $Q$ preceding an assignment $x = e$ is just $Q$ with every occurrence of $x$ replaced by the expression $e$. To see this in action, say you have the goal $Q = (x^2 = 4)$ and you want to see if $x = 3$ satisfies this goal. Well, the assignment axiom tells us that we should transform this post-condition into $(x^2 = 4)[x \mapsto 3] \to (9 = 4) \equiv \bot$, which says that there is no precondition that can get us to the goal. On the other hand, a goal of $Q = (x^2 = 9)$ allows us to compute a weakest precondition of $(9 = 9) \equiv \top$, so any precondition will satisfy this program.
The connection between the forward and backward systems: Recall that we said that the two deduction systems are duals of each other. In other words, given a deduction (in the form of an inference rule) in the forward system, we can infer a similar deduction (in the backward system) by joining the leaves/exit points of this tree together, and inverting the proof. In other words, there's a (rough) correspondence. Suppose that the forward system is characterized by the rule function $F$, such that $F(\{\phi_1, \dots\}) e$ returns the set of propositions that might hold after executing $e$ given that we know $\{\phi_1, \dots\}$ before hand. Similarly, we also have a backwards rule function $B$, such that $B(\{\psi_1, \dots\}) e$ returns the set of propositions that must be true before $e$ so that $\{\psi_1, \dots\}$ holds afterwards. We can see that
$$
Q = B(F(Q))
$$
(though the other direction $Q = F(B(Q))$ does not necessarily hold, since $B$ can produce $\bot$ and $F(\bot) = \bot$)


Lambda Calculus: How do evaluation contexts "work"

The subtlety lies in where the distinction between language and metalanguage is made. As René Magritte put it:

$(\lambda f. \lambda x. f x) ((\lambda y.y) (\lambda  z.z)) (\lambda  w.w)$ is a lambda-term, written in the syntax for lambda-terms. Let's call this lambda-term $t$. Let $M$ be the lambda-term $(\lambda f. \lambda x. f x) ((\lambda y.y) (\lambda  z.z))$. I can write $t = M \, (\lambda w.w)$ (and this is a true equality): all I did was to give a name to a subterm. If you consider the right-hand side of this equality “$M \, (\lambda w.w)$”, it is not written in the syntax of lambda-terms; it is written in a mathematical notation where we allow a letter to stand for a lambda-term.

When we write a rule like
$$
  \frac{e_2 \to e_2'}{v \, e_2 \to v \, e_2'}
$$
it states the following axiom: for any lambda-terms $e_2$ and $e_2'$ and any value $v$, if $e_2$ reduces to $e_2'$ then $v \, e_2$ reduces to $v \, e_2'$. Here we're again using meta-notations (i.e. mathematical notations to reason about a language): the arrow $\to$ to express the reduction relation; metavariables where a letter indicates the sort ($e$ for lambda-terms, $v$ for values) and subscripts and primes distinguish between metavariables of the same sort; the fraction notation to write an inductive axiom.

When we write the rule
$$
  \frac{e \to e'}{E[e] \to v E[e']}
$$
then again $E[\cdot]$ is a meta-notation, part of the metalanguage and not of the lambda-term syntax. The rule means: for any lambda-terms $e$ and $e'$ and any evaluation context $E[\cdot]$, if $e$ reduces to $e'$ then $E[e]$ reduces to $E[e']$.

If we call the context $(\lambda f. \lambda x. f x)[\cdot] (\lambda w.w)$ by the (meta-)name $E_t$, then $t = E_t[(\lambda y.y)(\lambda z.z)]$. Again, this is an equality between two lambda-terms, i.e. the same lambda-term is on both sides of the equal sign. What we have on the left and on the right are two different meta-notations for the same lambda term $(\lambda f. \lambda x. f x) ((\lambda y.y) (\lambda  z.z)) (\lambda  w.w)$: one that uses a name that we gave to it, another that's a bit more complicated involving a context that we gave a name to.

Given the term $t$, how do you find how it can reduce?

With the notation using multiple rules, you have to find a deduction tree (in general — here the derivation is linear, so you merely have to find a chain leading to an axiom).
With the notation using evaluation contexts, you have to find a suitable evaluation context.

The grammar of evaluation context follows the structure of the evaluation rules, so these are in fact not really two methods but two different ways of expressing the same definition.

To understand this, I strongly recommend the following exercise: in your favorite language, implement lambda-term call-by-value evaluation in a straightforward way, with a type representing lambda-terms and a function performing one reduction step.


Proving a DFA recognizes a language using induction

The induction you probably want is to show that a string $w$ ends in state $q_i$ iff it satisfies the property associated to that state.

The basis then is that the empty string, which must end in $q_0$, satisfies the property there.

You should be more precise in some of your properties. In $q_4$, the string ends in 01 as you state, but has never seen any of the special strings, in particular it did not end in 101.


Can we derandomize subexponential algorithms given P=BPP?

Derandomization results transfer "upwards" using the technique of padding. Assume $\mathsf{P}=\mathsf{BPP}$. Suppose that some problem $A$ can be solved in randomized superpolynomial time $t(n)$ (which is time-constructible). Let $A'$ be the same problem, but with inputs padded to length $t(n)$. Then $A' \in \mathsf{BPP} = \mathsf{P}$. The following algorithm then solves $A$ in deterministic time $t(n)$: pad the input to length $t(n)$, then apply the polynomial time algorithm for $A'$.

Conversely, it is possible (given the current state of knowledge) that subexponential time algorithms can be randomized, but polynomial time algorithms can't (and it might be possible to construct a relativized world in which this happens unconditionally). That is, results don't transfer "downwards".


What is the difference between $\log^2(n)$, $\log(n)^2$, $(\log n)^2$, $\log (n^2)$ and $\log \log n$?

For the first one, you can find an answer here:

  (log(n))² means log²(n)

And from this question for example you can guess that:

  log(n)² = (log(n))²

So both the first and the second essentially mean

  (log(n)) × (log(n))

(Unfortunately, not with more reliable sources than stackexchange...)


Why can't we round results of linear programming to get integer programming?

In $\mathbb R$, one can simply round down or round up to obtain an element of $\mathbb Z$. Only two choices!

However, in $\mathbb R^n$, one has $2^n$ ways of rounding to obtain an element of the integer lattice $\mathbb Z^n$. For example, if $n=100$, one has $2^{100} \approx 10^{30}$ possible ways of rounding.

Of course, one can round all entries of an $n$-dimensional vector down or up, but do note that the Euclidean distance between the two farthest vertices of the hypercube $[0,1]^n$ is $\sqrt n$. If $n=100$, then $\sqrt{100} = 10$.

Unfortunately, to the best of my knowledge, there is no guarantee that the solution to the integer program will be found via one of the $2^n$ possible rounding schemes.

Fortunately, some linear programs have integer solutions and, thus, no rounding is required.


Compute relational composition in $O(|E||V|)$

Theorem 2.29 on page 60 of Parsing Theory of Sippu and Soisalon-Soininen gives an algorithm for computing (among other operations on relations) the composition of two relations. The algorithm runs in $O(t(|V|+|E|))$ time, where $t$ is the time needed to perform union or assignment operations on sets of vertices. The result of this operation is a set of vertices per vertex representing its neighbors. This algorithm works on arbitrary graphs, not just acyclic ones.


As explained in enumerating all connected induced subgraphs (on TCS.SE), there is an algorithm whose running time is polynomial in the number of connected subgraphs.  Therefore, if you know that the number of connected subgraphs is polynomial in the input size, there is an algorithm that is polynomial in the size of the input.  The polynomial might be fairly high degree, so I don't know whether the algorithm will be efficient in practice, but you could try it out and see.

See also https://stackoverflow.com/q/15658245/781723.


Given a simple graph G, what's the quickest known way to sample one of its spanning trees at random?

I recommend Wilson's Algorithm. It is proven to select spanning trees uniformly at random. In worst case scenarios it can have complexity $n^3$, but in practical usage it often runs much faster, I believe typically $n log(n)$. I am part of a large research project at Duke and this is the algorithm we use. The current algorithm you have while faster, does not accurately sample randomly, one simple counter-example would be a star graph with an extra edge.

At the start, you have one visited vertex, and one exploring vertex (both randomly chosen). You start a random walk from the exploring vertex, until you hit a visited vertex. When the random walk makes a loop, you delete the loop from your walk, and carry on. When you hit a visited vertex, you append the vertices of your current walk to the visited vertices, and save the edges of the walk to the tree you will return. Then, you choose a new exploring vertex, and do another random walk, repeating until all vertices are visited vertices.

Here's a paper on Wilson's Algorithm and it's predecessor, the Aldous-Broder Algorithm. (which is worse in practice usually)


Complexity of Problems and Ease of Verification

Trivial arbitrarily hard example based on the existence of an one-way function $f : \mathbb{N}^k \to \{0, 1\}$. The problem:

  Given a set $S$ of size $n$, can we choose a tuple $t$ formed from $k$ elements of $S$ such that $f(t) = 1$?

Since $f$ is one-way you must check all $n^k$ possible $k$-tuplets of elements from $S$, but checking whether a proposed solution is correct is simply $O(1)$ time.

However, if you're looking for interesting or deep results, I'm afraid you're out of luck. Forget "at least this hard to compute but easy to verify", we barely even have "at least this hard to compute" for almost anything. See this scarce list here.

Why are lower bounds so scarce? Because they essentially require omniscience in a certain subject area. You must prove that no matter how smart, doing better than the lower bound is impossible. It's as if you're simultaneously exploring every possible algorithm, finding their time complexities and showing that they're bigger than the lower bound. It's nearly impossible, which is why we barely have any proofs that go beyond some version of "you must read all input".


Sorting strings with "before" and "after" constraints

Construct a directed graph in which $a \to b$ if $a$ is constrained to appear before $b$. Run a topological search. If it finds a directed cycle, there is no solution. Otherwise, it gives you some canonical solution.


TM to detect repeats of any other TM and input value

I think you're wondering how one Turing machine can keep track of what another Turing machine is doing, including checking that machine's state and knowing what's on its tape. After all, Turing machines don't have a method for "outputting" a description of what they're doing—they merely run.

But a Turing machine that takes in a description of another Turing machine can simulate that second machine on its tape, the same way that you can simulate running a TM using pencil and paper. The TM writes down the current configuration of the simulation, including what the simulated current state is, what the second machine's tape says, and where the machine's tape head is. It follows rules for moving the tape head, writing to the simulated tape, and changing the simulated current state.

That's how one machine can simulate another. Another helpful trick is that a TM can have any finite number of tapes without affecting its capabilities—a three-tape TM is no more powerful than a one-tape TM. So if it's conceptually helpful, you can give the TM a separate tape for each concurrent simulation.


Is {a^n: n is a product of exactly two primes} regular?

Just pump up $(M+1)$ $y$'s. Now you get $xy^{M+1}z=a^{(M+1)j+M-j}=a^{M(j+1)}$. Since $M$ is a product of two primes, $M(j+1)$ is a product of at least 3 primes, so $a^{M(j+1)}\notin L_1$, which proves $L_1$ is not regular by the pumping lemma.


Intuition for convolution in image processing

I think the simplest way to think of Convolution is as a method of changing a pixel's value to a new value based on the weight of nearby pixels.

It's easy to see why Box Blur:

_____________
|1/9|1/9|1/9|
|1/9|1/9|1/9|
|1/9|1/9|1/9|
-------------

works. Convolving this kernel is the same as going through every pixel of a photo and making the new value of the pixel the average of itself and the eight surrounding pixels.

If you get that, you can see why Gaussian Blur works:

_____________________
|.01|.04|.07|.04|.01|
|.04|.16|.26|.16|.04|
|.07|.26|.41|.26|.07|
|.04|.16|.26|.16|.04|
|.01|.04|.07|.04|.01|
---------------------

It's basically the same thing, except the averaging is weighted more strongly toward pixels that are closer. The function that defines how quickly the weights fall off as you move further away is the Gaussian Function, but you don't need to know the details of the function in order to use it for blurring.

The edge detection kernel in the linked article makes sense if you stare at it long enough too:

__________
|-1|-1|-1|
|-1|.8|-1|
|-1|-1|-1|
----------

It's basically saying that the value of any pixel starts at 8/9ths of it's original value. You then subtract the values of every pixel around it to arrive at your new pixel.

So if the value of a pixel is high and the value of the pixels around it are high too, they will cancel each other out. If the value of the pixel is low and all of the pixels around it are low as well, they will also cancel each other out. If the value of the pixel is high and the value of the pixels around it are low (as in a pixel on the edge of an object) the new pixel value will be high.


is a deterministic algorithm for breadth-first traversal possible (binary heap)

Binary trees can have different structures. Every node can have at most two children. At most means you might have 2 children, you might have one child or no child. This leads to different structural possibilities for the binary tree.

There is no definite pattern to tell how to find a particular node. Closest you can get to a pattern is when you have a binary heap, but in a heap it is fix that the binary tree will be complete binary tree i.e. all the internal nodes will have two children and the leaf nodes at the last level will be as left as possible. For a heap you can determine the left child as $2*i + 1$ and right child as $2*i+2$ where $i$ is the index of node and $i = 0$ for root node.

In the worst case a binary tree can degenerate to a linked list which means you would have to proceed linearly to find the element you want. So, we can say how will the search of a node proceed totally depends on the structure of the binary tree.

To find a node basically traverse the tree with any of DFS or BFS.


How many prefix code we can find for a given distribution of probability?

There are infinitely many prefix codes over $\{a,b,c\}$ containing 5 elements, for example $a,ba,b^2,b^3a,b^{4+n}a$ for all $n \geq 0$. I'm assuming the question is concerned with "saturated" or "minimal" prefix codes, which are prefix codes which satisfy one of the following equivalent conditions:

Each string in $\{a,b,c\}^\omega$ contains some codeword as a prefix.
Kraft's inequality is tight.
The ternary tree corresponding to the code is full, that is, each internal vertex has exactly three children.

It's not hard to check that all such codes containing 5 codewords must look as follows:
$$
\alpha, \beta, \gamma\alpha, \gamma\beta, \gamma\gamma.
$$
For such a code to be optimal for your particular distribution, a necessary and sufficient condition is that $\alpha,\beta$ are assigned to the heavy elements and $\gamma\alpha,\gamma\beta,\gamma\gamma$ to the light elements. You can check it by direct calculation (there are only 3 options, up to symmetry), or by noticing that if a code uses a length-1 codeword for a light element and a length-2 codeword for a heavy element, then switching them reduces the average codeword length.

Indeed, if we fix the codewords, then it is easy to assign them to symbols. The more difficult task is to find the optimal set of codewords. In this case, there is only one set of codewords, so there is no need to run any fancy algorithm such as Huffman's.


Star notation for context-free language alphabet?

It is equivalent (usually, otherwise it would be explicitly stated).
The "star-operation" is called a Kleene-star, and it is an operation that basically takes the set and creats the set of all combinations of items from the original set. In the example of $\{0,1\}$, we would have that $\{0,1\}^*=\{0^{k_1}1^{k_2}0^{k_3}\dots\mid k_1,k_2,\dots\in \mathbb{N}\}$, and intuitively speaking, this is the set of all words created from the alphabet $\{0,1\}$. This obviously is also true for any other alphabet $\Sigma$ you would want.


Calculating Frequency of Terms with Zipf's Law

The question gives you enough information to deduce $N$ and $s$.
You are given $f(1,s,N)$ and $f(2,s,N)$. Note that
$$
\frac{f(1,s,N)}{f(2,s,N)} = \frac{1/1^s}{1/2^s} = 2^s.
$$
Hence you can find $s$. In order to calculate $f(3,s,N),f(4,s,N)$ you don't really need to find $N$, since,
$$
\frac{f(1,s,N)}{f(3,s,N)} = 3^s, \quad
\frac{f(1,s,N)}{f(4,s,N)} = 4^s,
$$
using calculations similar to what we had before.

Notice that in order to solve this exercise, we had to know absolutely nothing about the Zipf law other than the formula. Stated differently, what you need in order to solve this exercise is not knowledge (apart from the formula for $f(k,s,N)$) but rather problem solving skills. One of the main goals of the undergraduate degree is to develop such skills.


Difficulty in understanding few steps in the proof: "The class $\mathscr{H}_{p,m}$ of hash functions is universal"

We want to show that if $k_1\neq k_2\in\mathbb{Z}_p$ then
$\Pr\limits_{(a,b)\in\mathbb{Z}_p^*\times\mathbb{Z}_p}[ak_1+b\equiv ak_2+b \pmod m]\le\frac{1}{m}$.
Where both addition and multiplication are preformed in $\mathbb{Z}_p$.
We start by showing that if $a\sim U(Z_p^*)$ and $b\sim U(Z_p)$ then for all $k_1\neq k_2\in \mathbb{Z}_p$, $(ak_1+b,ak_2+b)$ is uniformly distributed over $\{(x,y)\in\mathbb{Z}_p^2| x\neq y\}$ (i.e. $h(k_1)$ and $h(k_2)$ are jointly uniform over pairs with different entries, where the randomness is over the choice of $h$). This is immediate from the fact that for all $(c_1,c_2)\in\mathbb{Z}_p^2$ with $c_1\neq c_2$, the following system of linear equations:
$
\begin{align*}
& ak_1+b=c_1 \\
& ak_2+b=c_2
\end{align*}
$
has a unique solution over the variables $(a,b)\in Z_p^*\times\mathbb{Z}_p$. Subtracting the second equation from the first yields $a(k_1-k_2)=c_1-c_2$, since $k_1-k_2$ is nonzero we can multiply both sides by its inverse and obtain $a=(k_1-k_2)^{-1}(c_1-c_2)$. If $c_1\neq c_2$, then this is a nonzero solution for $a$, and we can extract $b$ from any of the two equations. Thus, for each pair $(c_1,c_2)$ with $c_1\neq c_2$ there are unique $(a,b)\in Z_p^*\times\mathbb{Z}_p$ such that $\big(h_{a,b}(k_1),h_{a,b}(k_2)\big)=(c_1,c_2)$. This settles your first question.
Now, divide $\mathbb{Z}_p$ into $\lceil p/m\rceil$ buckets, $b_1,...,b_{l=\lceil p/m\rceil}$ as follows: $b_1=\{0,1,...,m-1\}, b_2=\{m,m+1,...,2m-1\}$,...,$b_l=\{m\lfloor p/m\rfloor, m\lceil p/m\rceil+1,...,p-1\}$. Note that each bucket except the last is of size $m$, and no two elements in the same bucket are equivalent modulo $m$. We conclude that the number of different pairs in $\{(x,y)\in\mathbb{Z}_p^2| x\neq y\}$ that are equivalent modulo $m$ is at most $p(\lceil p/m\rceil-1)$, since after choosing the first element, you are left with $\lceil p/m\rceil-1$ elements to choose from (you must pick a different bucket and each bucket provides at most one candidate). Recall that $\big(h_{a,b}(k_1),h_{a,b}(k_2)\big)\sim U(\{(x,y)\in\mathbb{Z}_p^2| x\neq y\})$, so we can finally conclude:
$\Pr\limits_{(a,b)\in\mathbb{Z}_p^*\times\mathbb{Z}_p}\left[h_{a,b}(k_1)=h_{a,b}(k_2)\pmod m\right]=\frac{p(\lceil p/m\rceil-1)}{p(p-1)}\le \frac{1}{m}$
Note that allowing $a$ to take the value $0$ only makes our analysis easier, since now $\big(h(k_1),h(k_2)\big)$ is jointly uniform over $\mathbb{Z}_p^2$, but there is an additionaly probability of $\frac{1}{p}$ that $a=0$ and our hashes will be equivalent modulo $m$, so in this case we will have to settle for an $O(\frac{1}{m})$ bound on the collision probability.


How to implement a maximal munch lexical analyzer by simulating NFA or running DFA?

There are two ways to handle this issue:

The most common implementation (the one used in lex, flex and other similar scanner generators) is to always recall the last accept position and state (or accept code). When no more transitions are possible, the input is backed up to the last accept position and the last accept state is reported as the accepted token.

If you're trying to do streaming input, you will need a fallback buffer to handle this case.
Alternatively, if the scan reaches an accepting state but another transition is available, we can start performing two scans in parallel: one on the assumption that the transition will be taken, and the other on the assumption that it will not. The second thread may need to fork again, although there is a maximum number of forks, as with generalised LR parsing. In this model, we need to keep a buffer of possible "future" tokens which will be processed if the optimistic thread fails.

I don't know of a practical implementation of the second strategy in a general purpose scanner generator, although there are some papers about how you might do it. Apparently it can be done in time and space linear to the size of the input, which is (in theory) better than the quadratic time consumption of backtracking.

However, it is pretty rare that you find a token grammar which needs to allow unrestricted backtracking. The most common cause of unrestricted backtracking is failing to take into account the fact that things like quoted strings might not be correctly terminated in an incorrect program, so you end up with just the rule:

["]([^"]|\\.)*["]   { Accept a string }

instead of the pair of rules

["]([^"]|\\.)*["]   { Accept a string. }
["]([^"]|\\.)*      { Reject an unterminated string. }

(Maximal munch will guarantee that the second rule will only be used if the first rule cannot match.)

So while the second strategy may have some theoretical appeal, it seems to me that it's of little practical use. Flex even has some options which will help you to identify rules which could backup on failure, and this can help you craft your lexical grammar to avoid the problem. It's not always easy to eliminate 100% of backing up (although it often is, and if you manage to do so, flex will reward you by generating a faster lexer), but it's pretty rare to find a lexical grammar which requires more than a few characters of back-up, and the cost of a small fallback buffer is really not worth worrying about, in comparison with the complexity of the alternative (which, of course, also needs extra memory.)

I have seen intermediate strategies for particular grammars. If you know your grammar well enough, you could hand-build the speculative tokenisation in order to avoid backing up. I've seen that, years ago, in SGML lexers which eliminate the rescan of > following a tagname by including a redundant rule which recognised a tag immediately followed by a > and handled both tokens at once. That must have saved a few cycles, but it's hard to believe that it really made a huge difference, and the difference would likely be even less significant today. Still, if you are the type who obsesses about saving every possible cycle, you could do it.


Your code has worst-case complexity $\Omega(n^{1.5})$. Consider a tree of height $h$ which is composed of a "backbone" of $h$ nodes, out of the $i$th of which (counting from the root) there is a path to the right ending at depth $h$. As an example, here is the case $h=4$:

The height is computed along the entire backbone. The subtree rooted at the backbone node of depth $h-\ell+1$ has $\binom{\ell+1}{2}$ nodes (where $\ell=1$ corresponds to the backbone's leaf), and so computing the height of all subtrees along the backbone takes time proportional to
$$
\sum_{\ell=1}^h \binom{\ell+1}{2} = \binom{h+2}{3} = \Theta(h^3).
$$
In contrast, the tree contains $\binom{h+1}{2} = \Theta(h^2)$ nodes, so the running time in this case is $\Omega(n^{1.5})$ (in fact, it is $\Theta(n^{1.5})$ in this particular case).


What is the difference (if any) between transition systems and finite automata?

Yes, did you try wikipedia?

To quote the second paragraph [in transition systems]:

  The set of states is not necessarily finite, or even countable.
  The set of transitions is not necessarily finite, or even countable.
  No "start" state or "final" states are given.


What undecidable language $B$ is reducible to its complement?

Let $H$ be the language of all Turing machines that halt on empty input.
Clearly $H$ is undecidable.
Let $L = \{ (1,T) : T \in H \} \cup \{ (0,T) : T \not\in H \}$.
Clearly $L$ is undecidable. If $L$ were decidable, then a Turing machine $M$  for $L$ would also imply the existence of a Turing machine $M'$ that decides $H$. $M'$ with input $T$ simply simulates $M$ with input $(1,T)$.
Moreover, for a Turing machine $T$ and $x \in \{0,1\}$ we have:
$$
(x, T) \in L \iff (1-x, T) \not\in L \iff (1-x, T) \in \overline{L}.
$$
This, combined with the fact that we can decide whether a given word encodes a valid Turing machine, shows that $L$ is reducible to $\overline{L}$.


Single-source shortest path algorithm for graphs representing stacked behavior

Yes.  You want CFL-reachability.

You put a left-parenthesis on each call edge and a right-parenthesis on each return edge (with a different kind of parenthesis for each function).  Then, you look for a path where the sequence of symbols along the edges in the path form matched parentheses.

This is basically the intersection of a context-free language (CFL) with a graph reachability problem (finite state automaton), and as you know, the intersection of a CFL and a regular language is itself a CFL.  As a result, there are efficient algorithms for CFL-reachability.

There's also lots of theory and work on algorithms to make this as efficient as possible.  You can even find existing tools for this sort of thing.

I'd suggest you start by looking at the following papers:

Thomas Reps.  Program Analysis via Graph Reachability.  Information and Software Technology, vol 40 no 11-12, Nov/Dec 1998, pp.701--726.

Thomas Reps, Susan Horwitz, Mooly Sagiv.  Precise interprocedural dataflow analysis via graph reachability.  POPL '95.

Thomas Reps, Stefan Schwoon, Somesh Jha, David Melski.  Weighted Pushdown Systems and their Application to Interprocedural Dataflow Analysis.  Science of Computing Programming, vol 58 no 1-2, Oct 2005, pp.206--263.

The first two consider only the reachability problem (is there a path from $s$ to $t$?). The third can be used for the shortest paths from (find the shortest path from $s$ to $t$).


Grammars: is there some connection between non-terminals $S$ and $S'$?

$S'$ is just another nonterminal.

The reason $S'$ is used instead of, say, $T$, is that $S$ has been established as standard  for the start symbol of a grammar. Now, if you are talking about an algorithm that transforms a grammar (e.g. into a normal form), you will need to distinguish between the start symbol of the original grammar and that of the transformed grammar. In order to indicate that both are start symbols, it has become the norm to use $S'$ for one of them (usually the latter).


How to speed up process of finding duplicates/similar items in a large amount of strings?

Edit distance is definitely not the way to proceed. The standard approach toward near-identical document deduplication is to compute hashes of shingles. Here's one way to do it:

Compute a set of k-shingles (say 30 char shingles) for each document
Compute min-hashes for the documents
Use locally-sensitive hashing to look-up similar documents when inserting into the database

Here's a great article that explains how this can be done: http://deduplication.tumblr.com/

And you can pick up an existing tool do this, for example Solr: https://wiki.apache.org/solr/Deduplication


Difference between read-only Turing machine and non-erasing Turing machine

A non-erasing TM has a tape alphabet $\{0,1\}$ where $0$ acts as blank. The $0$ can be rewritten into $1$, but that symbol cannot be "erased", i.e., written back into $0$.

This restriction seems to be equivalent to symbols that can be rewritten only a finite number of times. TM's do have the capability of interpreting a finite segment of tape as one symbol. Then $0000$ can be rewritten into $0001$ then into $0011$, into $0111$, into $1111$. A little modulo counting interprets these segments as $0,1,0,1,0$.

Recall that a TM is equivalent to a finite state machine that has a queue as basic datastructure. It can read and delete on one side, and write on the other. To see that this is equivalent to a TM a rotation trick is done: the queue holds the tape in a circular fashion, but can only move on the tape in one direction. To move into the other direction just move all the way.

This rotation trick can also be done on the tape of a TM, and needs only finite rewrites on the same position. One needs to be able to rewrite the tape from $Ax$ into say $xB$ where $A,B$ are symbols and $x$ is a string.


How to detect facial landmarks - using haar and other way?

There is a recent survey paper on exactly this topic: Wu & Ji, Facial Landmark Detection: A Literature Survey, International Journal of Computer Vision 127:2, February 2019, pp 115-142. That should give you pointers to everything you might want to know.

If you don't have access to Springer, here's the copy on arXiv.


Combinatorics: how many ways can we mark nodes in a DAG as black or white, if every node downstream of a black node is also black?

Your problem is #P-complete. The set of solutions can be identified with the set of antichains with the poset corresponding to the DAG (the correspondence identifies a coloring with the black vertices that have no black parents), counting the number of which has been shown to be #P-complete by Provan and Ball in The complexity of counting cuts and of computing the probability that a graph is connected.


How to find closed form solution of linear recursion using recursive tree method


Solving a T(n) recursion without Master Theorem

Start with
$$T(1)= 1$$
$$T(21)= T(1)+\log(21)$$
$$T(41)= T(21)+\log(41)$$
$$\dots$$
$$T(20k+1)= T(19k+1)+\log(20k+1)$$
Then move $T(i)$s from the right side to the left side
$$T(1)= 1$$
$$T(21) - T(1) = \log(21)$$
$$T(41) - T(21) = \log(41)$$
$$\dots$$
$$T(19k+1) - T(18k+1) = \log(19k+1)$$
$$T(20k+1) - T(19k+1) = \log(20k+1)$$
And sum the left and right sides

$$T(20k+1) = 1 + \log(21) + \dots + \log(20k+1) \leq 1 + \sum_{i=1}^{k}{\log(21i)} = $$
$$1 + \sum_{i=1}^{k}{[\log(21)+\log(i)]} \leq 1+ \sum_{i=1}^{k}{\log(21)}+ \sum_{i=1}^{k}{\log(k)} = $$
$$1 + k\log(21) + k\log(k)$$ which is $O(n\log{n})$. This was only upper bound.

More general case

There is nothing special with the integers 1 and 20. You could take any positive integers instead of 1 and 20 and solve the relation

$$T(b) = c$$
$$T(n)= T(n-s) + \log{n}$$
as
$$T(b) = c$$
$$T(s+b) = T(b) + \log{(s+b)}$$
$$T(2s+b) = T(s+b) + \log{(2s+b)}$$
$$\dots$$
$$T((n-1)s+b) = T((n-2)s+b) + \log{((n-1)s+b)}$$
$$T(ns+b) = T((n-1)s+b) + \log{(ns+b)}$$
which gives
$$T(ns+b) = c + \log{(s+b)}+\log{(2s+b)}+\dots + \log{(ns+b)}$$

Is $n\log{n}$ a lower bound for this relation?

UPDATE: Omar's post attempts to establish a lower bound.


Optimal way to find maximal sum (with constraints) of array elements

This is a classic Dynamic Programming problem. Basically, dynamic programming is a way of turning a recursive algorithm into an iterative one with better runtime, by saving previous results that we might need again.

In this case, we can write the problem as two recursive functions:

maxSumSubtractFirst(startIndex):
    if startIndex is past the end of the array:
        return 0
    return max( # Two options: take whichever is better
        -A[startIndex] + maxSumAddFirst(startIndex+1), # Use this one
        maxSumSubtractFirst(startIndex+1) # Skip this one
    )

maxSumAddFirst(startIndex):
    if startIndex is past the end of the array:
        return 0
    return max( # Same as above
        A[startIndex] + maxSumSubtractFirst(startIndex+1),
        maxSumAddFirst(startIndex+1)
    )

In other words, we have two choices for each element: either include it (and flip the sign for the next one), or skip it (and keep the sign the same).

Now, we could run maxSumSubtractFirst(0) and get the answer that way, but this could take $O(2^n)$ in the worst case. We can do better.

Since each function will always return the same output given the same input, we can make two arrays the same length as our input, then store the results of maxSumSubtractFirst in one, and maxSumAddFirst in the other. If we start from the end (the largest index) and work backward, we'll never have to recurse at all: just look up the results in the array, which takes $O(1)$.

Now we can take the first element in the maxSumSubtractFirst array, and that's our answer. We've only had to call each function $n$ times, and each call takes $O(1)$, so this version of the algorithm runs in $O(n)$—a significant improvement over $O(2^n)$!

(Note that, as written, this only gets you the value of the sum, not the sequence of choices that led to it. But that's easy to change: make additional arrays to hold the choices, and fill them in with each call to maxSum*First.)


Checking each of the possible proofs takes time $O(2^r\cdot poly)$, so checking $2^{2^rq}$ of them would take how much?


Undecidability of telling if a program returns true or false

Assume you have a function like the one you described:

def haltify(f):
    # Never fails to halt.
    # If 'f' halts, returns f().
    # If 'f' doesn't halt, anything could be returned.
    ... magic ...

But then someone comes along and does this:

def evil():
    return not haltify(evil)

See the problem?

If haltify(f) is guaranteed to halt for all f, then evil is also guaranteed to halt because it just calls haltify on a specific f and inverts the output.
Since evil halts, haltify(evil) must evaluate to the same thing as evil().
So not haltify(evil) simplifies to not evil() and that's what evil() returns.
That's a problem, because there's no x satisfying x == not x. Evil's result is contradictory.
Therefore one of the assumptions we used is wrong: either haltify isn't guaranteed to halt, or it isn't guaranteed to return f() when passed a halting f.

Bonus exercise: why doesn't the function def good(): return haltify(good) cause problems for haltify, despite apparently simplifying to the infinite loop def good(): return good()?


How does C++'s type checking work when passing overloaded or templated functions as parameter

Type checking occurs when the template is instantiated, so the compiler knows the types by then.

Overload resolution happens at call site. The sub-expressions are the arguments, when their types is known the resolution can occur, hence giving the type of the call expression (that is, the return type).

Neither templates nor overloaded functions are first-class citizen constructs than can be passed around, so I am not sure what you mean by "such a function".


Devising a way to spot a contradiction given a set of statements using graphs

First, you can consider only the equality relationships and build an undirected graph with each edge representing each equality relationship. Then you can simply apply BFS or DFS to partition this graph into connected components.

Next you can consider the "<" and ">" relationships. You can treat each connected component as a vertex and add directed edges so that $(u,v)$ represents the relationship $u<v$. Then you can detect if there is a cycle in the directed graph by DFS again. If there is cycle, there is a contradiction among these relationships; otherwise the relationships we processed so far are consistent.

At last you can consider the "$\neq$" relationships. You can simply check for each relationship $a\neq b$ if $a$ and $b$ belong to the same connected component. If $a$ and $b$ belong to different connected components for all relationships $a\neq b$, then all the relationships are consistent; otherwise there is a contradiction.


The rule from Troelstra and Schwichtenberg that you call multiplicative, namely
$$\frac{\Gamma \vdash A \Rightarrow B \qquad \Delta \vdash A}{\Gamma \cup \Delta \vdash B} \tag{1}$$
is equivalent to the additive formulation because we have weakening. More precisely, the multiplicative and the additive formulations prove the same judgements. In one direction, it is obvious that the additive version
$$\frac{\Theta \vdash A \Rightarrow B \qquad \Theta \vdash A}{\Theta \vdash B} \tag{2}$$
follows from the above multiplicative one, just take $\Gamma = \Delta = \Theta$. In the other direction we can use weakening: assuming there are derivations of
$$\Gamma \vdash A \Rightarrow B \qquad\text{and}\qquad \Delta \vdash A$$
then by weakening there are derivations of
$$\Gamma \cup \Delta \vdash A \Rightarrow B \qquad\text{and}\qquad \Gamma \cup \Delta \vdash A$$
and then by the additive rule (2) we get the desired conclusion
$$\Gamma \cup \Delta \vdash B.$$
So for the most part the difference in formulation is largely stylistic, although the difference may matter when we consider proof complexity, and other apsects of derivations, apart from just derivability.

Let me also say that from the semantic point of view it is a bit simpler to give the semantics of the additive formulation than the multiplicative one. In the additive rule one has to cope with the question on how the meaning of $\Gamma \vdash \mathcal{J}$ for some judgement $\mathcal{J}$ relates to $\Gamma \cup \Delta \vdash \mathcal{J}$. No such consideration is necessary in the additive formulation.


Is L = {  | M is a TM and L(M)={w}} turing recognizable? And its complement?

Intuitively, $L$ is not recognizable as given $\langle M, w\rangle$, to know Whether $M$ accepts $w$ we need to simulate the run of $M$ on $w$, but $M$ need not to halt on $w$, so the simulation may not halt. This obviously smells like the halting problem. Even if we somehow know that $M$ accepts $w$, how can you check whether $w$ is the only word in $L(M)$? What about the other infinite words over $M$'s alphabet? It seems impossible to go over all of these words and verify that all of them are not in $L(M)$ and then halt.
If you consider the complement of $L$, $\overline{L} = \{ \langle M, w\rangle: L(M)\neq \{w\} \}$, you get the same problamatic issue. How can you check whether $L(M)$ does not include $w$?
So intuitively, both $L$ and $\overline{L}$ are not recognizable. Formally, to show that a language $B$ is not recognizable, we show that there a non-recognizable $A$ that reduces to $B$. We consider the non-recognizable language $A = \overline{Halt_{TM}} = \{ \langle M, w \rangle: \text{M does not halt on w}\}$, then we show that there are mapping reductions, one from $A$ to $L$, and the other is from $A$ to $\overline{L}$:

$\overline{Halt_{TM}} \leq_m \overline{L}$: we need to show that there is a reduction from $\overline{Halt_{TM}}$ to $\overline{L}$. Consider the reduction that operates as follows. On input $\langle M, w\rangle$, the reduction outputs $\langle K, w\rangle$, where $K$ is a machine that operates as follows. On input $x$ for $K$, the machine $K$ simulates the run of $M$ on $w$. If $M$ halts on $w$ (if the simulation halts), then $K$ accepts $x$ only if $x = w$, and otherwise $K$ rejects $x$. If $M$ does not halt on $w$, that is the simulation does not halt, then clearly $K$ does not halt.
The reduction is correct: if $\langle M, w\rangle \in \overline{Halt_{TM}}$, then $M$ does not halt on $w$. Hence, $K$ does not halt on any input $x$, and thus $L(K) = \emptyset \neq \{w\}$. Meaning that $\langle K, w\rangle \in \overline{L}$. Conversely, if $\langle M, w\rangle\notin \overline{Halt_{TM}}$, then  $M$ halts on $w$. Hence, $K$ halts on every input $x$, but accepts only if $x = w$, and so $L(K) = \{ w\}$. Thus, $\langle K, w\rangle \notin \overline{L}$.

$\overline{Halt_{TM}} \leq_m L$: we need to show that there is a reduction from $\overline{Halt_{TM}}$ to L. Consider the reduction that operates as follows. On input $\langle M, w\rangle$, the reduction outputs $\langle K, 1\rangle$, where $K$ is a machine that operates as follows. On input $x$ for $K$, the machine $K$ checks whether $x = 1$. If $x = 1$, $K$ accepts. If $x\neq 1$, $K$
simulates the run of $M$ on $w$. If $M$ halts on $w$ (if the simulation halts), then $K$ accepts $x$. If $M$ does not halt on $w$, that is the simulation does not halt, then clearly $K$ does not halt.
The reduction is correct: if $\langle M, w\rangle \in \overline{Halt_{TM}}$, then $M$ does not halt on $w$. Hence, for every input $x\neq 1$ for $K$, $K$ does not halt, and thus $L(K) = \{1\}$. Meaning that $\langle K, 1\rangle \in L$. Conversely, if $\langle M, w\rangle\notin \overline{Halt_{TM}}$, then  $M$ halts on $w$. Hence, $K$ halts on every input $x$ (as when $x\neq 1$, the simulation of the run of $M$ on $w$ halts), and accepts. Hence, $L(K) = \Sigma^* \neq \{ 1\}$. Thus, $\langle K, 1\rangle \notin L$.

Final note: I have assumed w.l.o.g that $\overline{L}$ does not contain words that are not a description of a pair $\langle M, w \rangle$. This is okay, as a reduction (a machine) can easily check whether an input is of the form $\langle \text{ machine, word}\rangle$. If the input of the reduction is not of this form, then the reduction outputs some constant word that is in the language that we're reducing to. So for readability issues, I sticked to this assumption.


If $\log xy=\log x+\log y$ then why multiplication is harder than addition?

Logarithms were used to make computation easier at a time when computers were not available.  Even in the twentieth century, when mechanical machines became available to do arithmetics with much precision, they remained so expensive, and often cumbersome, that most people did not use them. The mechanical hand held calculator doing the four arithmetic operations did not appears before the end of the second world war
(this machine, called the Curta, was actually designed in a concentration camp, which saved some lives).
Since most calculations did not require too much precision, many people simply used slide rules, or tables of logarithms. The typical cartoon of a scientist or engineer whould show him with the slide rule in his front pocket.

I am old enough that I did not have hand calculators at school (computers still used more space than my classroom). What I
had was a slide-rule, which is based on logarithms. It did not give a
very high precision (at best something like $10^3$, i.e., 3 decimal digits),
but it was invaluable to do problems in physics.  Numbers were read
directly on the slide rule, that essentially can add lengths.

For more précision, we would use tables stored in books. That gave 4
digits, plus one with interpolation (as I recall). We also has direct
table for logarithms of trigonometric functions.

This was well organized, and the cost of computing logs and
exponentials with the tables was nothing compared to the savings of
not doing multiplications by hand. It was actually free, with direct
reading of graduations, on the slide-rule.

This was not a mathematician viewpoint, but a physicist viewpoint,
or that of any person having to do much calculation involving
multiplications, such as astronomers, or people mapping the land
(which probably took several centuries).

I did not check, but I would guess that numerical algorithmic design
at the time must have been much influenced by the idea of minimizing
translation to and from logarithms. I would guess we were told in class to be careful about that.

Considerable effort was also spend in building very precise tables. By
hand, of course, at least until mechanical arithmetic machines became available. According to wikipedia, despite a large number of earlier prototypes, the calculator industry did not start before the middle of the 19th century.

This all started with the invention of logarithm by John Napier at the
beginning of the seventeenth century. His contact with astronomer
Tycho Brahe who was at the time mapping very accurately the motion of
celestial bodies (so that Kepler and Newton would have the data for
the work that made them famous), and other such person, may not have
been foreign to his invention of this most remarkable computation
tool.

The fact that logarithms can make multiplication easy was certainly
one very important factor in the development of science and
technology for nearly 3 centuries.
But not knowing exactly who used it and when, I cannot make a more
precise statement.


Can a non-regular language be made regular via concatenation when they don't share characters?

First, the equality $L = AB$ is correct. Next, if you know that $B$ is non-regular, you can prove that $L$ is non-regular as follows.

Suppose that $L$ is regular. Then $(00)^{-1}L = \{0^n1^m2^m \mid n \geqslant 0, m>1\} = 0^*B$ is regular. It follows that $0^*B \cap \{1,2\}^* = B$ is regular. Contradiction.


$n=2^k$ is a simplifying assumption that ensures binary search "goes through" properly. If the array has a length that is not a power of two, you have to break ties when choosing middle elements, "halves" are not equally large and not all decisions lead to the same number of steps.

The worst-case number of steps on an array of size $n$ can certainly bounded from above by the maximum number of steps on an array of size $2^k$, $n \leq 2^k$. If we choose $k$ as small as possible, we obtain $k = \lceil \log n \rceil$.

With $\lceil \log n \rceil \leq \log(n) + 1$ we see that the worst-case number of steps is indeed asymptotically equal to $\log n$.


Possibly it's not for each $n$, but for each $i$.

First, try to calculate $m$ for each specific $i$:

 i | m
-------
 1 | 3
 2 | 5
 3 | 7
 4 | 9
   :
 n | 2n+1

$m$ increased by two for each loop of for i = 1 to n. Therefore $m = 2i+1$ for each $i$ in the loop.

And this is repeated from $i = 1$ to $i = n$, so in total,

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


What category does questions like "Given n points on 2D plane find ..." belong to

Combinatorial geometry.

http://mathworld.wolfram.com/CombinatorialGeometry.html

Computational geometry.

https://en.m.wikipedia.org/wiki/Computational_geometry


Example of a non-context free language that nonetheless CAN be pumped?

The classical example is $L = \{ a^i b^j c^k : i,j,k \text{ all different} \}$. Wise shows in his paper A strong pumping lemma for context-free languages that neither the Bar-Hillel pumping lemma nor Parikh's theorem (stating that the set of lengths of words in a context-free language is semi-linear) can be used to prove that $L$ is not context-free. Other tricks like intersecting with a regular language also don't help. (Ogden's lemma, a generalization of the Bar-Hillel pumping lemma, does prove that $L$ is not context-free.) He also provides an alternative pumping lemma which is equivalent to context-freeness (for computable languages), and uses it to prove that $L$ is not context-free.

Wise's pumping lemma states that a language $L$ is context-free if and only if there is an (unrestricted) grammar $G$ generating $L$ and an integer $k$ such that whenever $G$ generates a "sentential form" $s$ (so $s$ can include non-terminals) of length $|s| > k$, we can write $s = uvxyz$ where $x,vy$ are non-empty, $|vxy| \leq k$, and there is a non-terminal $A$ such that $G$ generates $uAz$ and $A$ generates both $vAy$ and $x$.

By repeatedly applying the condition in the lemma, Wise is able to prove that $L$ is not context-free, but the details are somewhat complicated. He also gives an even more complicated equivalent condition, and uses it to prove that the language $\{ a^n b a^{nm} : n,m > 0 \}$ cannot be written as a finite intersection of context-free languages.

If you cannot access Wise's paper (it's behind a paywall), there's a typewritten version which came out as an Indiana university technical report.

A non-context-free language which satisfies the pumping condition of Ogden's lemma is given by Johnsonbaugh and Miller, Converse of pumping lemmas, and attributed there to Boasson and Horvath, On languages satisfying Ogden's lemma. The language in question is
$$ \begin{align*}
L' &= \bigcup_{n \geq 1} (e^+a^+d^+)^n(e^+b^+d^+)^n(e^+c^+d^+)^n
\\ &\cup (a+b+c+d)\Sigma^* \cup \Sigma^*(a+b+c+e) \cup \Sigma^*(ed+d(a+b+c)+(a+b+c)e)\Sigma^*.
\end{align*} $$
We can write $L' = L_1 \cup L_2$, corresponding to the two different lines. Note that $L_1 \cap L_2 = \emptyset$ and that $L_2$ is regular. Ogden's lemma can be used to prove that $L_1$ is not context-free, and so neither is $L'$, but it cannot be used directly to show that $L'$ is not context-free.


Algoritm to sample an even subgraph of a graph

Based on this answer from Math.SE you can construct a simple algorithm for uniformly sampling an even spanning subgraph.
Assume without loss of generality that $G$ is connected (otherwise you can apply the sampling algorithm to each connected component and return the union). Let us denote $G$'s vertices by $v_1,...,v_n$, and given $i>1$ let $P_i$ be some simple path from $v_1$ to $v_i$ (such path exists since $G$ is connected).
Given $A\subseteq\{2,..,n\}$ and some spanning subgraph $H$, define $H^A$ to be the graph obtained from $H$ by flipping the edges in each $P_i$ for $i\in A$, i.e. if $H$ is represented by $x_H\in\mathbb{F}_2^{|E|}$, and $P_2,...,P_n$ are represented by $x_2,...,x_n\in \mathbb{F}_2^{|E|}$, then $H^A=x_H\oplus\left(\bigoplus\limits_{i\in A} x_i\right)$. Note that for $A\neq B$ we have $H^A\neq H^B$. $H^A=H^B$ for some $A\neq B$ iff there exists nonempty $A\subseteq\{2,...,n-1\}$ such that $\bigoplus\limits_{i\in A}x_i=0$ (i.e. the vectors $x_i$ are dependent). Suppose $i\in A$, and let $G_A$ denote the spanning graph represented by $\bigoplus\limits_{j\in A}P_i$. Flipping the edges of any path $P_j$ only changes the parity of the degrees of $v_1$ and $v_j$. Thus, as $G_A$ is obtained by starting with the empty graph and flipping the edges of every $P_j$ with $j\in A$, $deg_{G_A}(v_i)$ is odd, which means $G_A$ is not the empty graph.
Now we can define the following equivalence relation on subgraphs of $G$, $H_1\sim H_2\iff\exists A\subseteq\{2,..,n\}:H_2=H_1^A$. Based on the previous observation, each equivalence class contains $2^{n-1}$ different elements.
The second key observation is that each equivalence class contains a unique even subgraph of $G$. Given a subgraph $H$, for any vertex $v_{i>2}$ with odd $deg_H(v_i)$ flip the edges in $P_i$. This only changes the parity of the degrees of $v_1,v_i$ in $H$. Proceed in this manner until $deg_H(v_2),...,deg_H(v_n)$ are all even. Since the sum of the degrees is always even, $deg_H(v_1)$ must now be even too, which means that the newly obtained equivalent graph $H'$ is an even spanning subgraph. For uniqueness, suppose for the purpose of contradiction that $H\sim H'$ are two different equivalent even spanning subgraphs of $G$, i.e. $H'=H^A$ for some non empty $A\subseteq\{2,..,n\}$. Let $i\in A$ be some path index in $A$, then clearly $deg_{H'}(v_i)$ is odd, since $deg_{H}(v_i)$ is even and its parity is only changed while flipping the edges of $P_i$.
This was covered in the linked answered by Yly. Now you have a simple sampling algorithm that requires $O(|V|+|E|)$ preprocessing time. Execute BFS from $v_1$ to obtain the paths $P_2,...,P_n$. Sample uniformly a spanning subgraph $H$, now for each $v_i$ with odd $deg_H(v_i)$ flip the edges of $P_i$. In this manner you find the unique even spanning subgraph in $[H]$, using $O(n^2)$ time. Uniformity follows from the fact that all equivalence classes have the same size, and each contains a unique even spanning subgraph.


Is star closure of reverse of language equivalent to reverse of closure of that language

Take any $w\in {(L^*)}^R$. Then $w$ can be writen as $w=(u_1\cdot u_2\cdots u_n)^R$, with $u_i\in L$. We have

$$
w =(u_1\cdot u_2\cdots u_n)^R =u_n^R \cdot u_{n-1}^R \cdots u_1^R,
$$

and therefore $w\in (L^R)^*$.

Assume now that  $w\in {(L^R)}^*$, then by the same argument
$$
w =u_1^R \cdot u_{2}^R \cdots u_n^R= (u_n\cdot u_{n-1}\cdots u_1)^R ,
$$
and hence $w\in {(L^*)}^R$.

As a consequence ${(L^*)}^R={(L^R)}^*$


Prove, a^2+b^2=c^2,there exists only 1 case such that a,b,c are consecutive non negative integers(3,4,5)

$n^2 + (n + 1)^2 = (n + 2)^2 \Rightarrow n^2 + n^2 + 2n + 1 = n^2 + 4n + 4 \Rightarrow 2n^2 2n + 1 = n^2 + 4n + 4 \Rightarrow n^2 - 2n - 3 = 0 \Rightarrow n = -1, 3$

Therefore, 3 is the only plausible solution.


What's the difference between a binary search tree and a binary heap?

Heap just guarantees that elements on higher levels are greater (for max-heap) or smaller (for min-heap) than elements on lower levels, whereas BST guarantees order (from "left" to "right"). If you want sorted elements, go with BST.by Dante is not a geek

  Heap is better at findMin/findMax (O(1)), while BST is good at all finds (O(logN)). Insert is O(logN) for both structures. If you only care about findMin/findMax (e.g. priority-related), go with heap. If you want everything sorted, go with BST.

by xysun


Not in any straightforward way, because a tree transducer only accepts a single input, while an interpreter needs two inputs.

An interpreter needs two inputs: a transducer $R$ and a tree $T$, and would output the $R(T)$.  But a tree transducer can only accept one input.

Consequently, there appears to be no way to build such an interpreter (unless you accept some crazy way of pre-processing the inputs to bring them into a form that they can be provided to a tree transducer -- but it's hard to see how to define that in a way that rules out trivial solutions where it's the pre-processor that's actually doing all the interpreting).


Recursive algorithm for finding a common ancestor between two nodes in a tree, if it exists?

The algorithm in the (edited) answer has worst-case quadratic time complexity. (An worst-case example is a tree where there are just two strands and the given nodes are the two leaves.)

A (non-recursive) $O(n)$ time and $O(1)$ space algorithm, assuming that nodes have parent pointers:

Compute the height of both target nodes.
Until the heights are equal, replace the deeper node with its parent.
Until the two nodes are the same, replace both nodes with their respective parent.

The time complexity of this solution is actually $O(h)$ where $h$ is the maximum height of the tree; by the same token, the time complexity of the solution in the question is $O(h)^2$. If the tree is known to be (somewhat) balanced, then $h = O(\log n)$. Even so, $O(\log n)$ is probably better than $O((\log n)^2)$.


What are the uses of multi-dimensional arrays?

One could just as easily ask "what are the uses of multidimensional spaces?"  After all, with space-filling curves, all we really need is one dimension.

But a single dimension, even if it's sufficient, does not always yield useful models.  For example, a 2-dimensional euclidean line would be non-continuous when mapped to a space-filling curve.

It's the same with multi-dimensional arrays -- they're used not because they're inherently necessary, but because they're a useful model.

For example, let's take a look at how one might model a movie.

A movie is nothing more than a time-varying sequence of images -- i.e., an array of images.
Each image is a two-dimensional array, with each element of the array representing a color.
A color has three components:

Red
Green
Blue

So a movie can be modeled as a multidimensional array.


Finding subset such that one sum is more than target and another sum is less

Consider what happens if you set $a_i=b_i$ for all $i$.  I expect you should be able to take it from there...


Are those definitions of universal hash family equivalent?

I'm assuming that the cardinality of Key is bigger than the size of the hashtable m

There are still families with collision probability less than $1/m$, e.g., with three keys and two buckets,

$$\{(2, 1, 1), (1, 2, 1), (1, 1, 2)\}$$

has collision probability $1/3 < 1/2$, and there are other counterexamples for all other parameter settings. The most plausible path to your intuition being true would be if $h(k)$ and $h(l)$ were necessarily independent, but they're not and can in fact be anti-correlated.


Randomly partition an rectangle into N smaller rectangles

Here's a simple idea that I believe can generate all partitions.  There are two types of subdivisions:

Given a rectangle, randomly generate a horizontal or vertical line to partition it into two subrectangles.  (The usual "split in two" rule.)
Given a rectangle, randomly generate a rectangle that fits inside it.  Consider the 4 corners of this inner contained rectangle: for each of them, flip a coin and draw a line from this corner outwards towards the outer containing rectangle, with the direction of the line (horizontal or vertical) being determined by what the coin says.  Regardless of the directions of the 4 lines, the result will always be 5 rectangles.  (Some partitions that can be generated by rule 1 can also be generated this way -- in fact, only 2 of the 16 possible configurations of lines will produce partitions that could not be produced by rule 1.)

At any point in time you will have a set of rectangles (initially, just the original one).  Randomly choose one to subdivide (or you could, e.g., choose the biggest, etc.), flip a coin to decide which of the two rules to apply to it, and then apply that rule; keep doing this until you have $n$ rectangles.

Disclaimer: I have no idea how to even think about the set of all partitions, let alone whether the above procedure generates them all with equal probability...  Probably not.


Understanding context free grammars in conjunction with PDA

A PDA is a machine with a certain set of states and an infinite, initially empty, stack. It also has an input tape with the input word written on it. As long as there's input remaining, the machine reads the next character of input, checks its current state,  and pops off the top character of the stack to read it.  Based on what it finds, the PDA then switches into some new state and pushes a new character onto the stack.

The set of all languages PDAs can recognize is called the context-free languages. They are context-free roughly because what happens next depends only on the character at the top of the stack, rather than all the context beneath it in the stack. A PDA is finished when it goes into a special state for accepting or rejecting the input word. (Some people instead say that a PDA is finished when the stack is empty.) The language of a PDA is the set of all words that it accepts.

A context free grammar is a set of production rules. For simplicity, a production rule looks like $A \mapsto B$ or $A\mapsto BC$ or $A \mapsto \mathtt{a}$ or $A \mapsto \epsilon$. These respectively mean "If you have the symbol $A$, you may replace it with $B$ / $BC$ / the character $\mathtt{a}$ / the empty string."  A production rule is a rule that allows you to transform a symbol. The capital letter symbols are called nonterminals; they are sort of like variables. The symbols like $\mathtt{a}$ are terminals; they are sort of like constants.  There is a special nonterminal symbol called the start symbol, usually denoted $S$. The language of a context-free grammar (set of rules) is the set of all strings of terminals (like $\mathtt{abcde}$) you can make starting from the start symbol $S$ and applying any of the rules until only terminal symbols remain.

It turns out that context-free grammars (CFGs) are equivalent to pushdown automata (PDAs) because they can recognize the same languages. In particular, for every CFG there's a corresponding PDA, and vice versa.

Here's the CFG->PDA recipe. If you have a CFG, make a PDA with one start state and one reject state. Push the start symbol onto the stack. Then, loop: pop off the top symbol of the stack. Nondeterministically pick a production rule with that symbol on the left hand side. Push all the symbols on the right hand side of that rule onto the stack (make sure the leftmost symbol ends upon top). If the symbol at the top of the stack is a terminal character, make sure it matches the next character of input, otherwise reject. If the stack becomes empty, accept.


Tighter analysis of modified Borůvka's algorithm

It is possible to craft test cases for general graphs where your Borůvka's step wouldn't
halve the number of edges in each step, even though it halves the number of vertices.
An interesting note is that the optimization that you suggest works for planar graphs. This is because
for planar graphs $|E| \leq 3*|V|-6 $ i,e $|E| = O(|V|)$. And in general it leads to a
speed up for the class of minor closed families of graphs.

Reference:

Masters thesis, Claude Anderson (on page 100 the worst case input for Borůvka's algorithm
is described). [link]
"Two linear time algorithms for MST on minor closed graph classes". Archivum mathematicum 40 (3): 315–320, 2004. [link]


Why do relational databases use 2PC for distributed transactions over the likes of Paxos?

One of the reasons is the message complexity. For N nodes, 2PC will require 3N to be exchanged whereas Paxos requires 4N. Also, Paxos adds sequence numbers to each message which adds a significant overhead to the overall execution.


The answer is correct. Let's verify it

$\log_{10}n $ and $\log{n}$ belong to the complexity class $O(\log{n})$, because they differ by a constant factor, hence $\log_{10}n \asymp \log{n}$.

$n^{0.8} \succ \sqrt{n}$, because $0.8 > \frac{1}{2}$. The last pair $n\log{n}$ and $n\log{n}^2$ belong to the complexity class $O(n\log{n})$ because they also differ by a constant factor ($n\log{n^2} = 2n\log{n}$), hence  $n\log{n} \asymp n\log{n^2}$. Finally we'll show that $\sqrt{n} \succ \log{n}$ and $n\log{n} \succ n^{0.8}$. The last one is obvious and I'll leave to you to prove that $\sqrt{n} \succ \log{n}$ (I claim that is true, if you face problems with it I'll expand the answer with proof).


Given a regular language $U$, when does there exist $V$ such that $U^\omega$ = $\lim V$?

Consider the language $$U = U_1 \mid U_2 = a\Sigma^* \mid (\Sigma \setminus \{c\})^* b$$ for the alphabet $\Sigma = \{a,b,c,d\}$.

Let $\mathcal{A}$ be a deterministic Büchi automaton for the language $U^\omega$ with $n$ states. For every $n \in \mathbb{N}$, the word $w_1 = a(b^n c)^\omega$ should not be accepted, but the word $w_2 = a(b^n c)^m b^\omega$ should be accepted for every $m \in \mathbb{N}$.

The word $w_1$ should not be accepted because $U_1$ can only be used once (as there is only one $a$ in $w_1$), so in order for $w_1$ to be be accepted by $U^\omega$, a subword match with $U_2$ has to occur infinitely often -- but $U_2$ cannot accept subwords with a $c$.

The word $w_2$ should be accepted because $U_1$ accepts $a(b^n c)^*$, and $(U_2)^\omega$ accepts $b^\omega$.

Now by a pumping argument, we can see that from a prefix trace for a, when reading $b^n$, an accepting state in the Buchi automaton should be visited at least once, as otherwise we have a rejecting loop for the word $ab^\omega$. But then an accepting state is visited at least once for $ab^nc$. By an induction argument, we can then show that for every $m \in \mathbb{N}$, a trace for $a(b^nc)^m$ needs to visit accepting states at least $m$ times. Similarly, a trace for $a(b^nc)^\omega$ visits an accepting state infinitely often, even though this word is not in $U^\omega$. Hence, the assumption that $U^\omega$ can be represented as a deterministic Büchi automaton is false.


Questions about Randomized Median algorithm?

Let's start with your second question. A random running time is a running time which is a random variables. As a simple example, consider an algorithm which tosses a fair coin until it come up heads. The running time is a random variable whose distribution is, roughly speaking, geometric. This is not so different from the randomized median algorithm: every run of the median algorithm is like a coin toss, and you iterate running it until it comes up "heads" (succeeds).

Now, for the name iterative algorithm. Here is the algorithm you describe:

repeat
  run Algorithm 3.1
until the algorithm succeeds

This is the epitome of iteration – the algorithm consists of a single loop.

You write

  In order to get an iterative algorithm, then the algorithm must call itself and must have a logarithmic running time.

I'm not really sure why you think that an iterative algorithm should call itself. Indeed, algorithms calling themselves are usually known as recursive algorithms. (As an aside, an iteration of the form considered here is a special case of recursion known as tail recursion.)

Also, I'm not really sure why the algorithm should have a logarithmic running time. The standard algorithm for summing an array is iterative and runs in linear time.


Cutting yarn into integer-length pieces to maximize profit based on known prices for each length

This answer isn't really helpful for your assignment and isn't framed in terms of dynamic programming. It's just about solving the problem fast.

This problem can be solved in $O(n \lg^2 n)$ time by using iterative max-convolution on the prices.

Max-convolution takes an array $a$ and tells you $\max_j^d (a_j + a_{d-j})$ for each starting offset $d$. By being clever you can do it in $O(n \lg n)$ time instead of $O(n^2)$, kinda reminiscent of the convolution theorem.

edit: but see @Kaban-5's important caveat in the comments, about this algorithm depending on random inputs instead of random choices!

The key thing to realize is that, if the price for a piece of length $d$ is less than the price of a piece of length $d-j$ plus a piece of length $j$, then the effective price for a piece of length $d$ should increase to the sum of those two prices. And if we keep looking for these pricing inefficiencies and fixing them, we'll converge on the true optimal selling price for each length.

A single max-convolution will replace every price with the maximum you can get by splitting a piece into up to two pieces and selling all the pieces. A second max-convolution will be searching through all splits into up to 4 pieces. The third goes up to 8. And so forth until we hit up-to-$n$ after the $\lg n$'th max-convolution.

Here's the algorithm:

def bestSplitPrice(prices):
    """
    Assuming you have a piece of yarn of length len(prices)+1, find
    the best price you can get by cutting it and selling the pieces
    at the given prices-per-length.
    """
    prices = [0] + prices #A zero-length piece costs nothing
    for i in range(ceil(lg2(prices))):
        prices = max_convolve(prices, prices)[:len(prices)]
    return prices[-1]

And here's an example:

prices = {1:1$, 2:3$, 3:3$, 4:4$, 5:5$, 6:5$, 7:7$}
# array-ify, including 0-length price
prices = [0, 1, 3, 3, 4, 5, 5, 7]
# max-convolve lg2(8) = 3 times
prices = [0, 1, 3, 4, 6, 6, 7, 8]
prices = [0, 1, 3, 4, 6, 7, 9, 10]
prices = [0, 1, 3, 4, 6, 7, 9, 10]

The best piece-price for length-7 is 10$

Here's how the max-convolutions play out if only the 1$ piece is given a price:

prices = [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
prices = [0, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
prices = [0, 1, 2, 3, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
prices = [0, 1, 2, 3, 4, 5, 6, 7, 8, 7, 7, 7, 7, 7, 7, 7]
prices = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15]

Notes:

I suspect this can be cut to $O(n \lg n)$ by having the max-convolutions double-hitting exponentially larger and larger sections of the array.


To detect isomorphic graphs Is it enough to check if they have the same number of same degree vertices?

No. If two graphs have different degree sequences, they are definitely not isomorphic, so the algorithm "half-works". But consider a six cycle versus two three-cycles. Both graphs have six vertices, all of degree two; they are not isomorphic.  Indeed, this counterexample shows that nothing based solely on degrees can work.


How are data types related to information theory?

Interpretation: The Link Between Data Types and Information Theory
I believe the missing link between these two topics, information theory and data types, is interpretation. Interpretation is essentially the "input-output function" for which output (meaning) is derived from input (data). Whether the interpretation is being performed by a computer, at compile-time or run-time, or a human is relative to the task at hand.

At any rate, data types are language-defined/user-defined interpretations of an input alphabet to an output alphabet. Also, language-defined data types usually have a direct relation to the size of storage locations on a computer.

Probabilistic vs. Deterministic "Mapping"
When determining the output based on a given input, is the output definite (deterministic) or is the output uncertain/ambiguous (probabilistic)?

Memory vs. Memoryless "Mapping"
When determining the output based on a given input, does the determining process require memory?