The summation rule of the big-O notation;

Given $T_1(n) \in \mathcal{O}(f(n))$ and $T_2(n) \in \mathcal{O}(g(n))$, than $$T_1(n)+T_2(n) \in \mathcal{O}(\max(f(n),g(n)).$$

So, if you call $Func1()$ and $Func1()$ inside of your function $Func()$ only once and there is no other significant computation, $Func()$'s running time is;

$$Func() \in \mathcal{O}(\max(k |M^2|(|L|+|M|\log |M|), k | K | | V | )) $$


PERMUTE-BY-SORTING with similar priorities

The easiest way is to generate a random permutation in $P$. Here is pseudocode:

Initialize $P$ with $P[i] = i$ for $i = 1,\ldots,n$.
Repeat for $i = 1,\ldots,n-1$:

Let $j$ be a random number in the range $i,\ldots,n$.
Swap $P[i]$ and $P[j]$.


A simple algorithm is to iterate over all ways to choose 3 of the points, and test whether those 3 satisfy your criteria (are approximately colinear, have the appropriate distances, etc.).  There are ${n \choose 3}$ such triples, so the running time of this algorithm is $O(n^3)$.

It is possible to improve on that.  Here is an algorithm whose running time is $O(n^2 \log n)$:

For each point $p$:

Sort the points by their slope to $p$.  In other words, for each point $q$, calculate the slope of the line connecting $p$ and $q$, and use this as the key to help you sort the points.
Look for two points $q_1,q_2$ such that the slope of the line connecting $p$ and $q_1$ is approximately the negative of the slope of the line connecting $p$ and $q_2$.  You can check whether such a pair of points $q_1,q_2$ exist by a linear scan over the sorted list built in the previous step.  For each such pair, test whether $q_1,p,q_2$ satisfy your criteria (are approximately colinear, have the appropriate distances, etc.); if they are, output them.

The running time is $O(n^2 \log n)$, since for each iteration of the outer loop you do $O(n \log n)$ work, and the outer loop does $n$ iterations.

The above algorithm sorts the list of points by their slope, to make it easier to find 3 points that are approximately colinear.  You could also sort the list of points by their distance to $p$, to make it easier to find 3 points at the prescribed distances.  It's hard to say a priori which one might work better, but you could certainly try them both.


Proof the number of expected node in a binary using mathematical induction

If the array has length $n = 1$ then the constructed tree consists just of a root. Therefore $a_1 = 0$. Similarly, $a_0 = 0$ (this is a corner case).
Now suppose that $n \geq 2$. Without loss of generality, assume that $x = 1$, and so $y = n$. The array splits into two halves: $1,\ldots,r-1$ and $r+1,\ldots,n$. The first has length $r-1$, and the second has length $n-r$. If $r = 1$ or $r = n$, the one of these halves is empty; this happens with probability $\frac{2}{n}$. So with probability $\frac{n-2}{n}$, the root has two children. Defining $i = r-1$, we see that $i$ is chosen uniformly among the $n$ options $0,\ldots,n-1$, and the two subarrays have lengths $i,n-1-i$. From here it is straightforward to deduce your formula, using linearity of expectation.
Your formula simplifies to
$$
a_n = \frac{n-2}{n} + \frac{2}{n} \sum_{i=0}^{n-1} a_i.
$$
This implies that
$$
(n+1)a_{n+1} - na_n = n-1 + 2 \sum_{i=0}^n a_i - (n-2) - 2 \sum_{i=0}^{n-1} a_i = 1 + 2a_n,
$$
and so
$$
a_{n+1} = \frac{n+2}{n+1} a_n + \frac{1}{n+1} \Longrightarrow a_{n+1} - a_n = \frac{a_n}{n+1} + \frac{1}{n+1}.
$$
Now
\begin{multline}
a_{n+2} - a_{n+1} = \frac{a_{n+1}}{n+2} + \frac{1}{n+2} = \frac{a_n}{n+1} + \frac{1}{(n+1)(n+2)} + \frac{1}{n+2} =\\ \frac{a_n}{n+1} + \frac{1}{n+1} = a_{n+1} - a_n.
\end{multline}
In other words, $a_n$ is an arithmetic progression. You can check that $a_n = \frac{n-2}{3}$ for $n \geq 2$.


Dijsktra's algorithm applied to travelling salesman problem

Dijkstra's algorithm returns a shortest path tree, containing the shortest path from a starting vertex to each other vertex, but not necessarily the shortest paths between the other vertices, or a shortest route that visits all the vertices.

Here's a counter example where the greedy algorithm you describe will not work:

Starting from $a$, the greedy algorithm will choose the route $[a,b,c,d,a]$, but the shortest route starting and ending at $a$ is $[a,b,d,c,a]$.
Since the TSP route is not allowed to repeat vertices, once the greedy algorithm chooses $a,b,c,d$, it is forced to take the longest edge $d,a$ to return to the starting city.


why do CPU architectures use a flags register (advantages?)

In modern micro-architectures with register renaming the implementation cost for flags or not flags is pretty similar.  The main difference I can think of is that some flags indicate the characteristics of a value (Is the value negative?  Is the value zero?  Does the value have even or odd parity?), while some represent an event that occurred during a previous operation (did the add instruction have a carry out or an overflow?)  This led to a less-than-ideal situation on the MIPS when you wanted to simulate 64-bit addition on the 32-bit architecture (or 128-bit addition on the 64-bit architecture.)  On most architectures with a carry flag there is a special add-with-carry instruction, that includes the carry flag from the previous add instruction.  This makes simulating multi-precision arithmetic relatively inexpensive on many architectures with flags registers.

On the flip side, testing an N-bit register for zero or not-zero is actually surprisingly expensive.  To test an N-bit register for zero you need to perform an N-bit NOR operation, which requires $O(\log N)$ levels of logic to calculate.  On architectures with flags registers the extra logic for the zero/not-zero calculation at the end of the ALU stage can cause the clock to run slower (or force the ALU to have two cycle operations.)  For this reason, I think, some architectures, like SPARC had two versions of each arithmetic operation, one that set flags and one that didn't.

But MIPS doesn't save anything here.  They just moved the problem somewhere else.  On MIPS there is a branch-on-equal instruction.  This means that the branch instruction must actually have an ALU stage (including something like a bitwise xor operation followed by a nor to reduce down to the single equal/not-equal bit) before determining which way the branch goes.

The DEC Alpha architecture tried to split the difference by using a trick.  DEC Alpha had no flags registers, but also didn't have a branch-on-equal instruction.  Instead the branch instructions all look at the state of a single general purpose register.  There is branch-on-zero, branch-on-not-zero, branch-on-less-than-zero, etc.  The trick is that you can give every general purpose register an extra 65th bit that tells you whether the other 64 bits are all zero or not.  This makes it more like having a flags register: all the branch instructions look at a single bit (that is already calculated) to make their decision, but now you are back to figuring out how to calculate that extra zero indicator bit during a normal ALU cycle.  (And you still can't do multi-precision arithmetic just by looking at the carry flag from the previous operation.)


Mathematical model for a webpage layout?

At the time of writing, I am not aware of any formal (or at least formalized enough) models for layouts in HTML. All the examples (ALM, etc) indicate, that usually the model is created to guide layout manager's creation. In the case of HTML and web-browsers the development is evolutional and while each web engine contains some sort of algorithmic models to be able to render HTML, nobody (I know of) published underlying math, and nobody "reverse engineered" program code to extract the model.

It should also be noted, that the model could have grown very complex, so any effort to build one retrospectively may be quite costly.

Even though it is not done yet, it does not mean it is impossible. As more rigorous approaches are being applied to web programming (e.g., recent release of Ur/Web - typesafe approach spanning from database to client-side interactions), modelling HTML5 layout management may be on the horizon, especially, as we witness more formal approach in the recommendations for new HTML5/CSS features (for example, http://www.w3.org/TR/css3-flexbox/), because having formal model may help proving consistency of the additions (analogously to formal grammar, which greatly facilitates making additions to the programming language syntax).


How does one find a non-quadratic residue modulo $p$?

You are completely right, and your algorithm is a randomized polynomial time algorithm for finding a quadratic non-residue modulo a prime. A major open question in algorithmic number theory is finding a quadratic non-residue deterministically in polynomial time. This is possible assuming the generalized Riemann hypothesis, but unknown unconditionally. It is also equivalent to extracting square roots modulo a prime. This is all explained in notes by Booher.


Practical exponential time algorithms for polynomial-time solvable problems

The simplex method for linear programming has worst case exponential time complexity but is widely used in practice instead of the polynomial algorithms (which do exist).


Efficient search algorithm for a monotonic boolean array wherein the probability of target's location is available apriori

If you knew the distribution of $n^*$, you could find an optimal binary decision tree (there are several $O(n\log n)$ algorithms) in terms of expected number of queries (you can't beat binary search if you care about worst case). There are also two simple algorithms which are nearly optimal. I will describe them as algorithms for locating $n^*$ given queries of the form "$n^* \leq x$", which you can easily implement by checking $f(x)$. We assume that the probability that $n^* = i$ is $p_i$.

Gilbert–Moore algorithm: Partition the unit interval $[0,1]$ into intervals of length $p_i$, and let $x_i$ be the midpoint of the $i$th interval. We locate $n^*$ by doing binary search on $[0,1]$. For an interval $I \subseteq [0,1]$, denote by $X(I)$ the midpoints $x_i$ which are found in $I$. We first ask whether $n^* \in X([0,1/2])$. Depending on the answer, we ask whether $n^* \in X([0,1/4])$ or whether $n^* \in X([1/2,3/4])$; and so on. Eventually we reach an interval $I$ such that $X(I)$ is a singleton, and we have found $n^*$.

Horibe's algorithm: Find $x$ that minimizes $|\Pr[n^* \leq x] - 1/2|$, and ask whether $n^* \leq x$. Denote by $I$ the values of $n^*$ conforming to the answer. Find $x$ that minimizes $|\Pr[n^* \leq x \mid n^* \in I] - 1/2|$, and ask whether $n^* \leq x$. Update $I$, and repeat until $I$ becomes a singleton.

Both algorithms find $n^*$ using at most $H(n^*)+2$ queries on average (where $H(n^*)$ is the entropy of $n^*$), compared to the trivial lower bound $H(n^*)$, so they're pretty good.

In your case, you don't know the distribution of $n^*$, but you can make a guess, use one of these algorithms, and hope for the best. If you have several distributions in mind, you can choose one of them to construct an algorithm, and then check their performance on the other distributions, comparing the expected number of queries to the trivial lower bound.

You could also want to optimize some other quantity – for example, the 99th percentile of the number of queries. In that case the algorithms described above will probably still be pretty reasonable.


the number of arrangements of N players around a round table, where each player can sit on one of 3 contiguous chairs

Consider the variant of the problem in which the people are arranged in a segment instead of circle and let $S(n)$ be the number feasible arrangements for $n$ people.
Now lets go back to your original problem, and let's name $C(n)$ the number of feasible arrangements of $n$ people.
Clearly $C(0)=C(1)=1$ and $C(2)=2$, so we will henceforth suppose that $n \ge 3$.
Let's name the people $p_1, \dots, p_n$ where the assigned position of $p_i$ is $i$.
If $p_1$ is sitting in position 1 then the number of possible arrangements of $p_2, \dots, p_n$ is exactly $S(n-1)$.
Otherwise, $p_1$ is sitting either in position $2$ or in position $n \neq 2$. We will only consider the former case since the latter one is symmetric.
Clearly $p_2$ cannot sit in position $2$, so he/she must either sit in position $1$ or in position $3$. If $p_2$ is sitting in position $1$, then the number of possible arrangements of $p_3, \dots, p_n$ is exactly $S(n-2)$.
Otherwise, $p_2$ must be sitting in position $3$, which means that $p_3$ must be sitting in position $4$ (since position $2$ and $3$ are occupied) and, in general, $p_i$ must be sitting in position $(i \bmod n) + 1$. Since this completely determines everyone's position, this case only contributes $1$ to the total number of configurations.
To summarize, we have that:
$$
C(n) = S(n-1) + 2(S(n-2)+1) = S(n-1) + 2S(n-2) + 2.
$$
We are left with figuring out what $S(n)$ is. Clearly $S(0) = S(1) = 1$, so we consider $n \ge 2$.
In this case $p_1$ can only sit in position $1$ or $2$.
If $p_1$ is sitting in position $1$ then there are $S(n-1)$ possible arrangements of $p_2, \dots, p_n$. If $p_1$ is sitting in position $2$, then $p_2$ must be sitting in position $1$ (as it is the only other person that can sit there) and there are $S(n-2)$ possible arrangements for $p_3, \dots, p_n$.
We hence have:
$$S(n) = \begin{cases} 1 & \mbox{if } n \in \{0,1\} \\ S(n-1) + S(n-2) & \mbox{otherwise} \end{cases} = \mathcal{F}_{n+1},$$
where $\mathcal{F}_{i}$ denotes the $i$-th Fibonacci number. Substituting back, we obtain:
$$
C(n) =
\begin{cases}
1 & \mbox{if } n \in \{0,1\} \\
2 & \mbox{if } n = 2 \\
\mathcal{F}_n + 2 \mathcal{F}_{n-1} + 2 & \mbox{otherwise}
\end{cases}.
$$


No, that's not what the author means. The author means the specific sequence of characters the user will actually type. If the user is about to write a letter to Al that might be:

'D'::'e'::'a'::'r'::' '::'A'::'l'::rest

The point is that you conceptually have "all" of the characters, and you can (with a bit of care) process this list like any other list.


For $L_1$, consider a computation $T(w)$ of a Turing machine $T$ that never moves its head to the left with input $w$. Let $\Gamma$ be the tape alphabet (including the blank symbol) and $Q$ be the set of states of $T$.
Notice that, at any given step during the computation, the future behavior of $T(w)$ is completely determined by:

The current state.
The tape symbol in the current cell.
The contents of the (infinitely many) tape cells on the right of the head.

There are $|Q|$ choices for 1, $|\Gamma|$ choices for $2$, and $\max\{|w|,1\}$ choices for 3 (since the contents of the tape to the right of the head are always a suffix of $w$ distinct from $w$, followed by infinitely many blank symbols).
To decide $L_1$ it suffices to simulate $T(w)$ for $\eta = |Q| \cdot |\Gamma| \cdot \max\{|w|,1\} + 1$ steps. If $T(w)$ moves its head to the left during the simulation, then reject. Otherwise accept. To see that accepting is the correct choice notice that if $T(w)$ does not terminate within $\eta$ steps, then a state must be repeated at least twice, implying that $T(w)$ is in some loop. This loop can only involve states that appeared at least once during the first $\eta$ steps, showing that $T$'s head will never move to the left.
For $L_2$ see this question.


Assuming you're referring to how out of order execution can resolve a lack of resources. As resources are used and code is executed temporally, by reordering the code, the usage of resources can be rearranged in time, benefiting execution by a more efficient (less time waiting, more time using) use of resources.

I'm not a big fan of examples but let's suppose two super scalar pipelines want to use resources A, B, C and D, at the same time:

time = 0 | A | A
time = 1 | B | B
time = 2 | C | C
time = 3 | D | D

The CPU can reorder these instructions

time = 0 | B | A
time = 1 | C | B
time = 2 | D | C
time = 3 | A | D

Another example:
Suppose one instruction pipeline has the following instructions:

multiply_then_add
add_then_multiply
do_something_else

Then the usage of resources might look like this:

time = 0 | M |   |
time = 1 |   | A |
time = 2 |   | A |
time = 3 | M |   |
time = 4 |   |   | D

where M = multiplier, A = adder, and D = Doing something else. As you can see, the two add instructions back to back are an issue, if they were separated by a gap we could shorten the time taken, and out of order execution can resolve this:

multiply_then_add
do_something_else
add_then_multiply

time = 0 | M |   |
time = 1 |   | A |
time = 2 |   |   | D
time = 3 |   | A |
time = 4 | M |   |

Which can be optimised:

time = 0 | M |   |
time = 1 |   | A |
time = 2 |   | A | D
time = 4 | M |   |


Non-termination of types in Martin-Löf's Type:Type?

Short answer: yes.

Long answer: For $\mathrm{Type}:\mathrm{Type}$, non-termination at the type level is trivial. You can take a constant $X:\mathrm{False}\rightarrow \mathrm{Type}$. Then if you take the inconsistent term $\bot : \mathrm{False}$ you have
$$ X\ \bot : \mathrm{Type}$$
Which is non-terminating at the type level. You might complain that this has a head normal form, which isn't what usually leads to inconsistency in type theory. In this case you can remember that
$$ \mathrm{False}\equiv \forall X.\ X$$
and so
$$ \bot\ \mathrm{Type}:\mathrm{Type}$$

Which has no head-normal form. In general, in this system the types and terms are so intertwined that the non-termination always seeps at the type level.

However, there is another system, called $U^-$, also described by Girard in his thesis, which was discovered to be inconsistent by Coquand (A New Paradox in Type Theory). This system is terminating at the type level, as it only has $\mathrm{system}\ F$ types at the kind level, and we know that terms are normalizing in that system (also a result of Girard!).

This means that non-termination at the type level is not necessary for having an inconsistent pure type system (a fact that I found out somewhat painfully after having proven an open question while depending on this fact).


What is the complexity of the algorithm to calculate power set of a set?

The running time of step 6 depends on the size of subset_of_subset.

The reason is that the final list needs to contain both the original subset and the subset with last_element added to it. This requires copying the subsets, which takes time linear in its size.

Consequently, the running time of the algorithm scales at least as the total size of all subsets, which is $n2^{n-1}$.


Difference between the languages accepted by two DFAs with different initial state/accepting states?

Since $A,B$ are strongly connected, then if $q_1\neq q_2$, there exist words $p_1,p_2$ such that $\delta(q_1,p_1)=q_2$ and $\delta(q_2,p_2)=q_1$.

Consider case 2, then $w\in L(A)$ iff $p_2w\in L(B)$, and $x\in L(B)$ iff $p_1 x\in L(A)$. So you can add a prefix to switch between languages.

Consider case 3, then again - by strong connectivity there at most $|F_1|$ words $s_1,...,s_k$ such that for every $q_i\in F_1$ you have that $\delta(q_i,s_i)\in F_2$, and similarly for the other direction (from $B$ to $A$).

Thus, you can compose suffixes to switch between languages.

Combining these you can characterize the differences using prefixes and suffixes.
For example, in case 4, $w\in L(B)$ iff $p_1 w s_i$ in $L(A)$ for some $s_i$ in a predetermined finite set.

In fact, you can even say something interesting about these words: define $C$ to be the DFA where $q_1$ is the initial state and $q_2$ is the final state, then in case 2 you have $L(B)=L(C)\cdot L(A)$ (and similarly for the other direction).

As for the suffixes, things are more involved, since you cannot predetermine in which final state you will end. I'm not sure you can write this as a concatenation, but you can write $L(B)=\bigcup_{q\in F_1}L(A_q)\cdot L(E_q)$ where $A_q$ is the DFA obtained from $A$ be setting $F=\{q\}$, and $E_q$ is a DFA that starts in $q$ with final states $F_2$.

For case 4 you can combine the two.

You may be concerned that this is not a real answer, but rather just a characterization of properties using words rather than states, but this is a typical answer in this field (similarly to the Myhill-Nerode theorem).


Why is the minimum height of a binary tree $\log_2(n+1) - 1$?

I'm assuming that by $n$, you mean the total number of nodes in the binary tree. The height (or depth) of a binary tree is the length of the path from the root node (the node without parents) to the deepest leaf node. To make this height minimum, the tree most be fully saturated (except for the last tier) i.e. if a specific tier has nodes with children, then all nodes on the parent tier must have two children.

So a fully saturated binary tree with $4$ tiers will have $1+1\cdot2+1\cdot2\cdot2+1\cdot2\cdot2\cdot2$ nodes maximum and will have a depth of $3$. Thus if we have the depth of a binary tree, we can very easily find the maximum number of nodes (which occurs when the tree is fully saturated). If you recall from your algebra classes this is just a geometric series and can therefore be represented like this:

$$
\text{nodes}=1+2+2^{2}+2^{3}+...+2^{\text{depth}}=\sum_{k=0}^{\text{depth}} 2^{k}=\frac{1-2^{\text{depth}+1}}{1-2}.
$$

So let's rearrange:
$$
\text{nodes}=2^{\text{depth}+1}-1,
$$
then solve for the depth:
\begin{eqnarray}
\text{nodes}+1&=&2^{\text{depth}+1}\\
\log_{2}(\text{nodes}+1)&=&\log_{2}(2^{\text{depth}+1})=\text{depth}+1\\
\log_{2}(\text{nodes}+1)-1&=&\text{depth}.
\end{eqnarray}
and there's your formula. Now keep in mind this only yields integer values when the every tree is completely filled up (a 'perfect' binary tree) so if you get a non-integer value, remember to round up.


How many languages are described by a regular expression?

Every regular expression describes one language --- the language of words matched by the regular expression, or, in other words, the language of words accepted by the finite automaton corresponding to the regular expression.


This all deals with one of the major, and complex tasks in any processor. Namely decoding instructions. On a simple conceptual level, this may be viewed as taking the contents of the instruction register and translating this into logic commands to the various functional units of the processor to perform the desired action and then fetch the next instruction into the instruction register and repeat.

Traditionally there are two competing camps called Random Logic and Microcode.

The random logic camp tends to look at the task as a sort of huge logic problem. Given an input (the instruction set), what outputs are needed (the instruction implementation). The result tends to look like a huge array of gates, flip-flops etc arranged in a non-intuitive (looking random, but no actual randomness here).
Needless to say, for any non-trivial processor, this can be really complex.

The microcode camp on the other hand, maps each instruction to a stored program for a very simple but fast processor. Often, the microcode program is stored in very wide memory so that many program units can be simply connected to fields in the microcode with little or no additional decoding. In a sense, the microcode is implementing the random logic's output by table lookup.

These views are a gross simplification. Almost all random logic designs have small memory elements in them to simplify the state machines that are part of all processors, like the instruction fetch, operand decoding, or responding to interrupts. Likewise, almost all microcode machines employ some logic to speed up the decoding of the microcode to avoid needing insanely wide microcode memory. In addition, logic is often employed to allow the microcode to loop or branch to create more complex behaviour.

While microcode is extremely difficult to write, when an error is found, the code "simply" needs to be updated (assuming that you don't run out of microcode space, then well, problems) When a bug is found in the random logic decoder, it is not uncommon for the whole logic formulation to be affected. This can make random logic designs very hard to get right. The Z-8000 used random logic and its design was plagued by bugs in the instruction decoder. On the other hand, the simpler MC6809 also used random logic decoding and was highly successful.

The advantage of random logic is that it avoids the overhead of fetching the microcode from it's storage. In simpler processors avoiding this overhead can result in savings of silicon (that is money) and clock cycles (that is time).

RISC computers have much simpler instruction sets than CISC machines. This is a major reason why the random logic decoder is so often associated with RISC chips. CISC chips have intricate, complex instruction sets, so microcode is highly favoured for those designs.

I understand that most modern processors use a hybrid approach. Random logic for the simple and/or highly time critical stuff and microcode for the more complex behaviour and/or exception handling.


How to show that a language {w|ww^R in A} is regular, A being regular?

You might want to study If $L$ is a regular language then so is $\sqrt L=\{w\mid ww∈L\}$.

The solution is to simulate the DFA in parallel with itself, from both sides of the string. For each letter one step forward (for $w$) and one step backward (for $w^R$). If the forward state reading $w$ reaches the same state as the backward simulation, both parts joined form a computation on $ww^R$.


Is type inference done by an interpreter static or dynamic?

Typically , type inference in interpreted languages happens after parsing (because type inference works on ASTs) but before interpretation (= execution). Both compilers and  interpreters have a phase distinction between type inference, and the execution. The former happens strictly before the latter.

BTW, it's wrong to say that an "interpreter does the jobs of both compilation and execution". An interpreter does not do compilation.

A compiler is a meta-program that takes as input a program and outputs another program (the executable). It is this output that is executed.
An interpreter is a meta-program that takes as input a program and executes it.

Maybe the following picture clarifies the issue.


Is it immediately true that the class of P is a subset of the class NP?

P problems are a subset of NP problems. For a problem to be in P it must be decidable in polynomial time. For a problem to be in NP, it must be verifiable in polynomial time. If a problem is decidable in polynomial time, it is clearly verifiable in polynomial time as it can simply be verified by deciding it a second time. Therefore, all P problems are in NP.

I think that the fundamental component that you may not be remembering is that P and NP refer to specific time complexity classes of decision problems. Decision problems can't return general solutions. They can return yes (accept), no (reject), or never return.


How to fill cell-network partition matrix of a function?

You're pretty close.

I don't think that's what they intended as the partition matrix.  Instead, I think they intended the following matrix:

         x3
x1 x2 \  0 1
       -----
 0  0  | 0 0
 0  1  | 0 0
 1  0  | 0 0
 1  1  | 0 1

That's slightly different from what you have written.  In particular, the partition matrix will have $2^{k-1}$ rows and 2 columns.

It's best to think of the first sentence as one paragraph, and the remaining sentences as a second disconnected paragraph that is trying to explain a taxonomy for classifying a column of this matrix.  The author is proposing to classify every column into one of three types: all-zeros, all-ones, or contains both a 0 and a 1.  The paper represents an all-zeros column by 0, an all-ones column by 1, and the third case by X.  Thus, X is used to represent any column that contains at least one 0 and at least 1, i.e., any column that is not all-zeros and not all-ones.

By this classification, the partition matrix above would be of the form 0X: the first column is all-zeros (type 0), and the second column is type X.


GATE CSE 2009, Which of the following is FALSE?

A is true, but I don't find your argument convincing (it simply restates the claim). See this question for example.
B is not the correct answer to this problem, because as you say it's true. Your reasoning isn't very formal though, and swaps some reduction orders. A correct reduction would be NFA → (superset construction)→ DFA → (trivial) → PDA.
C seems fine to me.
D is indeed left over, and is indeed false. Inherently ambiguous context-free languages can be recognized by nondeterministic PDAs, but not by deterministic PDAs.


vector hashing function having collisions for permutations

With your limitations, you put all values into about 166,000 or so buckets, so yes, easily. If x, y, z are arbitrarily large, of course not.


Confusion about the Time Hierarchy Theorem and relativization

It is not true that for $A$ being $\sf EXP$-complete ${\sf DTIME}^A(n^k) = {\sf EXP}$, but you are right with ${\sf P}^A={\sf EXP}$.

Here is the reason for this. In order to make use of the oracle you have to transform your problem via a reduction. This reduction is a polynomial reduction. The running time of this particular reduction might need $\omega(n^k)$ steps. In this case you cannot use the oracle in the desired way.

As you already observed ${\sf DTIME}^A(n^k) \neq {\sf EXP}$ because this would imply  for all $k,j$ that ${\sf DTIME}^A(n^k)={\sf DTIME}^A(n^j)$, which cannot be true since the time hierarchy theorem relativizes.


Prove that $ T(n)=5^n+3T(\lfloor n^\frac{2}{5}\rfloor) $ is $O(5^n)$

Assume that $n \ge 4$ (the induction step is only handling $n \ge 10$ anyway), then $n-n^\frac{2}{5} > n - \sqrt{n} \ge 2$ and you have:
$$
\left( 1 + \frac{3c}{5^{n-n^\frac{2}{5}}} \right) \cdot 5^n \ge
\left( 1 + \frac{3c}{5^2} \right) \cdot 5^n =
\left( 1 + \frac{3}{25} c\right) \cdot 5^n.
$$
The latter term is not larger than $c \cdot 5^n$ whenever $1 + \frac{3}{25} c \le c$, i.e., when $c \ge \frac{25}{22}$.
Pick $c$ large enough to satisfy $c \ge \frac{25}{22}$ and the base cases, and you're done.


Why does higher-order abstract syntax need an inverse to define catamorphisms?

By being corecursive between the types, you indeed get a representation of a grammar, and it does have binding. But now you've sort of "baked in" the unembedding by making it "definitionally id". (This is similar to the Place constructor in Fegaras and Sheard).

So you can evaluate to Value. But what if you want to evaluate to anything else? You can't, unless it is something that "passes through" Value. So consider writing an "abstract interpreter" for your language (i.e., where you evaluate only to the "type" of the expression but without computing, or where you only "count the reductions" without computing). You can't, because you need to pass through having concrete elements of Value to go under lambdas.

You can fix this by having both Place and also a normal HOAS binding form, as in the above paper. But then that still doesn't suffice, for reasons they explain (and similar to what I've described -- see section 2) and so you make Place go further abstract by parameterizing over it, etc. Follow your nose further and you'll hit free monads. I got an intuition for this stuff from Edward Kmett's phoas post.


Can Turing machines simulate the unbounded minization operator applied to a partial function?

Unsafe $\mu$ is strictly stronger than partial TMs.

Indeed, define $f$ such that $f(x,0)=1$ if the $x$-th Turing machine halts on empty input, let $f(x,0)$ be undefined otherwise, and let $f(x,n)=1$ for all $n>0$. Then $f$ is a computable partial function. Let $g:=\mu(f)$. Then $g(x)=0$ if the $x$-th Turing machine halts and $g(x)=1$ otherwise. Hence $\mu(f)$ is not computable.

[EDIT]

The closure of partial recursive functions under unsafe $\mu$ seems to be the arithmetical hierarchy. (In order to make that statement precise, we have to translate between partial functions and subsets of $\mathbb N$.)


Is there a recommended process for designing CSGs (other than intuition)?

The hint by Yuval in his comment is the right one. An approach to writing context-sensitive grammars is to design them like a machine. Send messages over the string. This is very close to writing a linear bounded automaton (or linear space Turing machine). In such a machine the reading/writing head scans over the tape while updating the string. This head (with the machine state) can be modelled by a production, like $ap\to qb$ for "in state $p$ while reading $a$, write $b$ and move left, changing state to $q$", where we assume the state is written to the right of the position of the head.

There are differences. The CSG is more flexible as one can insert letters in the middle of the string, and moreover there can be parallel processes going on at the same time. The latter can be a nuisance when arguing the approach is correct.

Lets see how the messages work in an example:
$L = \{ww\mid w\in\{a,b\}^*, |w|\ge 1 \}$, or squares.

Start with left and right sides of the string with the rule $S\to LR$. As markers and messengers cannot disappear in a CSG they must represent a letter in the final string. This letter can be $a$ or $b$ so we have two rules instead: $S\to L_aR_a\mid L_bR_b$. Now the left marker generates new letters and a messenger that becomes a copy at the other half of the string. $L_\sigma\to L_\sigma aM_a\mid L_\sigma bM_b$. Everywhere in these rules $\sigma,\tau$ may take the values $a,b$.
Messengers move over other letters: $M_\sigma\tau\to \tau M_\sigma$. At the beginning of the second half write the letter: $M_\sigma R_\tau \to R_\tau \sigma$.

We should end the derivation by removing the boundary markers $L_\sigma\to\sigma$, $R_\sigma\to \sigma$. We have a problem when the right marker is gone, while there is still a messenger under way. This can be solved by extra symchronization. However, no terminal string will be generated this way; the drivation is lost, so there is no real problem.

I tried a similar approach here  for the language $\{a^ib^jc^{ij} \mid i,j\ge 1\}$. Here a hint for squares (numbers) $\{a^{n^2} \mid n\ge 1\}$.  As you see, I practise a lot.

PS. I hope you mean a monotonic grammar rather than a "real" context-sensitive one. Those are harder, but there is a standard (boring) transformation.


Possible to get the Sum x with maximal two summands?

If the numbers have a limit on their value, i.e. all numbers are smaller than $m$, then you can get runtime of $O(n + m)$: in an array $t$ of size $m$, for each number $a$ in the set of summands, check if $t[x - a] > 0$: if yes, then the answer is $(a, x - a)$. If not, set $t[a] = 1$ and continue with the next number.

This can be slightly improved with assigning values in buckets, but the worst time complexity will be $O(nm)$.

Otherwise, $O(n \log n)$ is the optimal complexity.


Is matching with mismatches a special(parametrized) case of Closest String problem?

In the latter you are given the string $s$ that you are looking for in the former.

An algorithm for the first one is to search for a string $s$ (try all strings) and run the latter procedure and verify that the set you get is the entire set.


Proving a Greedy Algorithm is Incorrect by Providing Counter Example and Coming up with another correct algorithm

The fact that you have several potential ways you can move in this problem should be an indicator of how to come up with a counterexample such that using the "greedy" strategy of simply going as far right as possible doesn't yield an optimal solution.

Consider the array, $A = \{1, 2, 1, 3, 2\}$

By the greedy strategy you would end up making the moves in this series:

$1 \xrightarrow{} 1 \xrightarrow{} 3 \xrightarrow{} 2$
$(3$ total moves$)$

However, the optimal strategy would be to make the moves:

$1 \xrightarrow{} 2 \xrightarrow{} 2$  $(2$ total moves$)$

Edit: I guess the question was edited as I was answering the question/after I answered it and we ended up with the same example..? Anyway here's another below:

Consider another counterexample (where backtracking produces a better solution):

$A = \{2, 1, 4, 6, 1, 5, 0, 10, 9, 8, 6\}$

The greedy strategy would yield the path: $2 \xrightarrow{} 1 \xrightarrow{} 1 \xrightarrow{} 5 \xrightarrow{} 0 \xrightarrow{} 10 \xrightarrow{} 9 \xrightarrow{} 8 \xrightarrow{} 6$
$(8$ total moves$)$

Whereas the series of moves: $2 \xrightarrow{} 1 \xrightarrow{} 1 \xleftarrow{} 6 \xrightarrow{} 6$ $(4$ total moves$)$

There's another series of moves resulting in a length $4$ path as well.

Since making the "locally optimal" decision for this problem at each step doesn't yield the optimal solution for the overall problem, this looks like a problem that could be solved using dynamic programming.

Look at it in a top-down fashion. What is the last move we'd want to make to get to the final element of the array, i.e., $a_n$. Recurse on that subproblem. Find a way to develop a solution using memoization (to avoid solving the same subproblem multiple times) or solve it iteratively, in a bottom-up manner. DP can be a bit difficult.


Which potential function does this algorithm minimize or maximize?

It takes at most $|A \cup B|$ iterations until convergence. Consider the directed graph $D(V,E)$ with a vertex $v \in V$ for each point
 $p_v \in (A \cup B)$ and a directed edge $(u,v) \in E$ such that $p_v, v \neq u$ is the nearest point to $p_u$ (connect each point to its nearest neighbour point).

If points $p_u$ and $p_v$ are each other's nearest then
 $(u,v),(v,u) \in E$. On the other hand, there is no cycle consisting of more than two edges. For contradiction assume the corresponding points in such a cycle as $p_0,p_1,...,p_k,p_{0}$. Since each $p_{((i+1) \bmod k)}$ is the nearest point to $p_i$ the distances decrease as we go along the cycle. This means that $p_k$ is closer to $p_0$ than $p_1$ and by construction this is not possible. A cycle of length three or more could cause an infinite chain of label changes (switching between labels $A$ and $B$).

The out degree of vertices in $D$ is exactly one, and in any path the last vertex have an out edge to its previous vertex in that path (because they are mutually each other's nearest). So the last vertex change label at most once, in the first iteration. Then its label propagates backward along all the path ending at this vertex until all the vertices in those paths receive this label.

Therefore, at each iteration, at least one vertex in any path gets its final label. So the number of iterations is the length of the longest path in $D$  which is at most $|V|-1$.


How to draw a parsing tree according to syntax diagram?

That diagram describes a language, a set of words over some alphabet.

Intuitively, this language contains all the words that can be obtained traveling over the diagram from the beginning (on the left) and following the arrows.

If we take the upper route, we build a word starting with $x$, then continuing with any string (or at least that's how I read that "String" box), and then ending with another $x$.

If we take the lower route, we form the word $x$, only.

To solve the exercise, you have to find a route which can generate the given string $xxyxx$. When doing so, you have to note down what parts of your string correspond to the nodes in the diagram (e.g. what correspond to the "String" box).

Note that this diagram is somewhat simple, in that it has no loops, so the parse tree is also simple. With loops, it could be more complex.

The last part of the exercise asks you to find a word which can not be generated following the diagram.


I've found a survey on natural-language generation approaches by Albert Gatt, Emiel Krahmer, 2018. According to that, my question is about linguistic realization. And the paper mentions three most common ones:

human-crafted templates
human-crafted grammar-based systems
statistical approaches

If I remember correctly, there may also be rules-based NLG systems, which may be overlapping with the grammar-based in the above classification.

And I am sure there may be more approaches.


Proving that if coNP $\neq$ NP then P $\neq$ NP

It is maybe easier to consider the contrapositive, that is ${\sf P}={\sf NP} \Rightarrow {\sf NP}={\sf coNP}$.

So assume ${\sf P}={\sf NP}$, then

for every $L\in {\sf NP}$, we have $L\in {\sf P}$, and since the languages in ${\sf P}$ are closed under complement,  $\bar L\in {\sf P}$ and therefore $L\in {\sf coNP}$.
for every $L\in {\sf coNP}$, we have $\bar L\in {\sf P}$, and since the languages in ${\sf P}$ are closed under complement,  $ L\in {\sf P}$ and therefore $ L\in {\sf NP}$.

Remark: Note that if ${\sf P}={\sf NP}$ the polynomial time hierarchy collapses to the lowest level, which implies that ${\sf P}={\sf NP}={\sf coNP}={\sf PH}$.


There is a problem which is both NP-hard and in coNP if and only if NP = coNP.

If NP = coNP, than NP-complete problems (like 3-SAT) are both NP-hard and in coNP.

On the other hand, if any NP-hard problem is in coNP, then all problems in NP are reducible to it, so all problems in NP are in coNP so NP ⊆ coNP. Now, since the complement of NP is coNP, and vice versa, we also have  coNP ⊆ NP. This means NP = coNP.

The question of whether NP = coNP is open, but most theoretical computer scientists do not think it is very likely.


There is no single standard implementation of JavaScript, so if you want to know what happens in a particular implementation, you should use your web search skills, focusing your efforts on that particular implementation. That said, a cursory web search reveals two main points:

Arrays can be implemented simply as associative arrays (also known as hash tables or, in python, dictionaries). This is appropriate if the array is sparse (contains only few non-zero values).
Arrays can be implemented as dynamically sized arrays, which are appropriate for the dense case. These are stored as classical C/Fortran arrays with a certain "extent". Once their length exceeds their extent, they are extended (say by doubling the extent) by allocating a new array the size of the new extent, copying the old values to the new array, freeing the old array, and changing the appropriate pointer to reflect the new location in memory. Arrays can potentially shrink as well according to a similar scheme.

Associative arrays are also dynamically sized, so in any case the second paradigm is being used.

Since the extent of the arrays increases exponentially, the average overhead is bearable, though once in a while, an operation may take a long time to perform (due to an array being resized). So such arrays are not a good choice for real-time systems.


Is the sum $f+g$ of two one-way-functions a one-way-function?

The answer is no.

Given $f$ one-way, consider $g(x) = -f(x)$. $g$ is then also one-way, because inverting $g$ would imply inverting $f$.  In particular, supposing $g$ is not one-way, one can invert $f(x)$ simply by negating it and applying the inverter for $g$ (and the success probability is even equal).

In this setting, $h(x) = f(x) - f(x) = 0$ is not one-way as it can be.


Database tables are not just files. In a way, they are also abstract entities. During the process of normalization of an existing dataset, a foreign key must coexist with the table to which it refers, so that referential integrity is never relaxed. In practice, this is not possible, but any intermediate steps should be considered only as implementation level issues.

That said, I can't see why creating the secondary table before updating the "old" table would be counterintuitive.

For the sake of intuitiveness, you can say that the "old" table will disappear, after the normalization process has been finished. Only new tables will be there, including a new version of the old table, with the foreign key already in place, and filled with data.


Problem in computational complexity (superior class)

The proof of the time hierarchy theorems can be paraphrased like this. We want to show that $\mathsf{X} \subsetneq \mathsf{Y}$ for appropriate $\mathsf{X},\mathsf{Y}$. The idea is to construct a diagonalizing machine $M \in \mathsf{Y}$ (slight abuse of notation here) whose language is different from all languages in $\mathsf{X}$. On input $x$, the machine $M$ runs $x$ on $x$ up to some specified time bound, and then answers the opposite. If the simulation is efficient enough, $M \in \mathsf{Y}$.

Your question is very similar. Go over the proof of the time hierarchy theorems, and check whether the diagonalizing machines there fit your bill.


In general, a general MILP was proved to be NP-Hard. This is a well-known proof and can be easily found in any textbook (or even on Wikipedia).
However, you can see one specific MILP problem as an 'instance' of the general MILP problem. Thus, you still need to show its complexity.

In fact, several MILP problems are NP-Hard:

Elementary Shortest Path (if the graph has negative cycles)
Degree-constrained Minimum Spanning Tree
Vehicle Routing Problem

However, many others are shown to be solvable in polynomial-time:

Job scheduling
Minimum Spanning Tree
Aircraft scheduling problem

You can demonstrate that a MILP problem is NP-Hard in the same way you do with any other optimization problem.

All you need to do is to reduce an NP-Hard optimization problem $\sigma$ to your MILP, construct a solution for MILP, and shows a polynomial-time transformation of your obtained solution to a solution of $\sigma$.

Sadly, there is no standard technique or proof method that can be applied to show the complexity of any MILP problems and you need to use your creativity (and mathematical skills, in many cases) to proof the complexity of your problem.


Describe an algorithm for painting cards in the following game

The Ray-Chaudhuri–Wilson theorem states that the number of cards is at most the number of objects. See for example a paper of Noga Alon (in your case, $L = \{1\}$).


What precisely/concisely is the "head" of a singly linked list? I ask bc of ambiguity online

You're right, there are many different definitions of a List/Linked List. No one definition is correct nor incorrect. This answer is a bit long-winded, but having a backstory on the logic behind lists is worthwhile.

History of Lists

Let's start with the definition of a List, in Computer Science, as described by the developers of the structure (Newell, Shaw, and Simon [1]) for their Information Processing Language [1] in 1957. It was initially developed as a method for flexible memory assignment in the Logic Theory Machine.

Definition of Lists (1957)

  $Lists$ : Lists are the general units of information in the memory. A list consists of an ordered set of items of information. Any item on a list may be either a list or an element, and these are fundamentally different types of unit. [1]

Formation of Lists

  To form a list, we use a set of location words, each containing two addresses. One address locates an item on the list, the other address locates the next location word. [1]

Location words are JOHHNIAC [2][3] words that contain two addresses.

  The left address is the address of the next location word, the right address is the address of the item on the list. [1]

Here is an example of a List containing three elements:

[1]

You can see in this example, the items link to nothing. This is why items are "on the list", they are attached to the list but not a direct piece of the list. Saying the first element is the "head" of a list makes no sense in this context. They are not part of the list at all.

The Head of a List

Newell and Shaw describe the head of a list as the first location word in the list [1]. Thus, in a strict sense, the head has an address to the first element on the list, while itself is the first location word in the list.

This representation of a list was traditionally followed. This can even be seen in the LISP [4] programming language invented by John McCarthy. Also check the LISP 1.5 Programmer's Manual [5].

Definition of Lists (1964)

Soon came along the idea of putting "symbols" in the list, rather than attaching them on the list. Wilkes [6] describes the registers (nodes) of a list as having two parts (similar to Newell, Shall, and McCarthy) in his paper Lists and why they are useful [6]:

The CAR, left free, and may be used to hold a symbol. Alternatively, can store an address memory.
[6]
The CDR (pronounced "cudder") contains an address pointing to the next register in the list.
[6]

Here is a simple example of a list under Wilkes' definition, with symbols in the list:

[6]

Head of a List

  A list must start somewhere, and the address of its first register is stored in a sequence of fixed memory registers known as base registers. [6] Normally, it is not necessary to show the base registers in diagrams of lists. [6]

With Base registers [6]:

Typical representation without base registers [6]:

In this definition, the head of a list is more in line with your first picture, it is an external register, not part of the list itself that merely contains the address to the first register in the list.

You may be wondering why I chose these examples instead of giving you the simple wiki definition [7]:

  The head of a list is its first node.

This definition is left ambiguous most likely intentionally because there are many different implementations. We can now discuss the head in regards to the two examples I presented.

The Sentinel Node (wiki [8])

Of these two examples, the latter is a list using a sentinel node (the base registers), the former does not. When using a sentinel, the head is the sentinel, the first node in the list, even though the sentinel contains no elements or addresses to elements. Clearly without a sentinel, the head is simply the first node in the list.

Internal vs External Storage (wiki [9])

Of these two examples, the latter is an example of internal storage, the former is an example if external storage. With internal storage you could attempt to think of the head as the first element in the list (though I wouldn't recommend it, because it contains also the address of the next node), because the element is in the node. With external storage, the head contains a pointer (memory address) to the first element of the list and a pointer to the next node in the list.

Nodes vs Elements

Much of the confusion about lists comes from the fact that many people mix up an element of a list with a node of a list. To prevent any confusion, whether you're using internal/external storage or a sentinel node or not, in my opinion, it's best not to refer to the elements (data stored in the list) as nodes of the list. Conceptually they are distinct.

The node of a list should thus contain two parts (as previously mentioned), the element or address, and an address to the next node. In programming, even if the two are not separated in code, conceptually they should be. Therefore when Wikipedia refers to the head of a list, it refers to the first node in the list. That node, then contains element data and an address to the next node.

Programming the logic theory machine by A. Newell and J. C. Shaw (1957, pp. 233)
The History of the JOHNNIAC by F. J. Gruenberger (1968) (available here for free, no sign-in required)
Johniac by E. Thelen (accessed Oct 29, 2017, last updated Aug 6, 2015)
LISP I Programmer's Manual by J. McCarthy et al. (1960)
LISP 1.5 Programmer's Manual by J. McCarthy et al. (1962, 2nd ed)
Lists and why they are useful by M. V. Wilkes (1964, pp. 1-5)
https://en.wikipedia.org/wiki/Linked_list#Basic_concepts_and_nomenclature (accessed Oct 29, 2017)
https://en.wikipedia.org/wiki/Linked_list#Using_sentinel_nodes (accessed Oct 29, 2017)
https://en.wikipedia.org/wiki/Linked_list#Internal_and_external_storage (accessed Oct 29, 2017)


What makes type inference for dependent types undecidable?

For a rather simple version of dependent type theory, Gilles Dowek gave a proof of undecidability of typability in a non-empty context:

Gilles Dowek, The undecidability of typability in the $\lambda\Pi$-calculus

Which can be found here.

First let me clarify what is proven in that paper: he shows that in a dependent calculus without annotations on the abstractions, it is undecidable to show typeability of a term in a non-empty context. Both of those hypotheses are necessary: in the empty context, typability reduces to that of the simply-typed $\lambda$-calculus (decidable by Hindley-Milner) and with the annotations on the abstractions, the usual type-directed algorithm applies.

The idea is to encode a Post correspondence problem as a type conversion problem, and then carefully construct a term which is typeable iff the two specific types are convertible. This uses knowledge of the shape of normal forms, which always exist in this calculus. The article is short and well-written, so I won't go into more detail here.

Now in polymorphic calculi like system-F, it would be nice to be able to infer the type abstractions and applications, and omit the annotations on $\lambda$s as above. This is also undecidable, but the proof is much harder and the question was open for quite some time. The matter was resolved by Wells:

J. B. Wells, Typability and type checking in System F are equivalent and undecidable.

This can be found here. All I know about it is that it reduces the problem of semi-unification (which is unification modulo instantiation of universal quantifiers, and is undecidable) to type checking in System F.

Finally it is quite easy to show that inhabitation of dependent families is undecidable: simply encode a Post problem into the constructor indices. Here are some slides by Nicolas Oury that sketch the argument.

As to whether there is a "limit", it much depends on what you are trying to do with your dependent types, and there are many approximations which try to be either decidable, or at least close enough to be usable. These questions are still very much part of active research though.

One possible avenue is the field of "refinement types" where the language of expression of type dependencies is restricted to allow for decidable checking see, e.g. Liquid Types. It's rare that full type inference is decidable even in these systems though.


If you are trying to prove $NP$-Hardness of that problem, you need a reduction from (not to).

Anyway, I don't think this is $NP$-hard (unless $P = NP$, of course)

Suppose the $S_i$ are sorted.

Suppose you decide that element $x \in S_j$ will be minimum. Now in each other set, you can find the smallest element greater (or equal to) $x$ using binary search, and take the maximum among those.

Do this for each of the $mn$ numbers, assuming it is the minimum. Pick the best set you get. This gives you a polynomial time algorithm: $m \log n$ time for each of the $mn$ elements, giving an $O(m^2n \log n)$ time algorithm.


You're just a step away from the answer.

Delete all intervals in $S$ which are contained in another interval in $S$. Now $S$ is totally ordered, i.e. for any two interval $[l,r]$ and $[l',r']$, either $l<l'$ and $r<r'$ or $l>l'$ and $r>r'$. Now it's not hard to find the first interval $[l,r]$ s.t. $l\ge i$ and the last interval $[l',r']$ s.t. $r'\le j$, and a range-max of length array on the interval $[l, l']$ gives you the answer.


Variant of bipartite matching, with real capacities from source and to sink, all others unlimited

Looks like the answer I was looking for was something like Dinitz's algorithm with dynamic trees. There are some implementation optimizations that can be added since we know it's a bipartite graph.


Heap down - What is math logic and intuition behind $\sum_{i=1}^{\log n}(\log n - i) \times 2^i $

So I guess you are showing that a complete binary tree can be made a heap in linear time.

$(\log n - i)$
counts the maximum number of swaps that a node may require, starting at level $i$, and descending to its final level; at most it could become a leaf. For instance if it starts at level $0$, then it could possibly require $\log n$ swaps; this would happen if the node placed at the root position becomes a leaf, since $\log n$ is the full height of the binary tree. And since level $i$ has up to $2^i$ nodes, $(\log n - i)2^i$ counts the maximum number of swaps for all nodes from level $i$, and $\sum\limits_i (\log n - i)2^i$ counts the maximum number of swaps for all nodes in the tree.
$2n-2$ is asymptotically $\leq 2n$ and $\geq n$; for instance $n\geq 2$ suffices. This is exactly the definition of $\Theta$.


What is the notation for bounding running time in worst case with concrete example resulting in that worst case running time

In words, such a bound is called a tight bound. In the specific case of Landau notation, $\Theta$ can be used to indicate a tight bound.
You have to be somewhat careful about your wording, though:

"The runtime of quicksort is in $O(n^2)$," is a correct statement (but somewhat imprecise).
"The runtime of quicksort is in $O(n^2)$, and this bound is tight," is correct and expresses, what you want to express.
"The worst-case runtime of quicksort is in $\Theta(n^2)$," is equivalent to the previous statement.
But "The runtime of quicksort is in $\Theta(n^2)$," is not correct, since this statement implies that quicksort takes quadratic time on every input.


There are (at least) four reasons.

They do not start at the same time. Before the second executeEvery is even found by the interpreter, the first one may already have executed some steps!
You don't even know if the platform supports parallelism. So you can only expect one move to be computed after the other; you may be able to control the relative speed (see below).
The threads themselves don't have any control over this (on most machines).
Either a virtual or the actual machine runs a scheduler that decides which process or thread runs when. For the programmer, the only robust way to deal with this is by assuming non-determinism (i.e. arbitrary order).
wait(10) won't wait for exactly 10ms. Even active waiting can get you only so close to the exact time frame.

If you want to execute the updates simultaneously -- in the sense that both boxes make their $i$th move before they do their respective $(i+1)$th -- you will have to use means of synchronisation, e.g. a barrier.


You can use a two pass approach:

In the first pass, identify all the different strings appearing in your input. (This can be done in various ways, e.g. hashing, trie, BST)

For the second pass initialize a Disjoint-set data structure with the strings found in the first pass and perform a union operation for each pair in the input.


How to prove that a language $A$ is decidable?

You know that a language $L$ is decidable if there is a TM, $M$ which when given a word $w$ as input always halts and accepts if $w\in L$ or halts and rejects if $w\notin L$. Here are some hints to get you started.

($\Rightarrow$) This is easy. If $L$ is decidable by a TM $D$, you can make an enumerator TM $E$ by trying all possible inputs in order. For word $w_i$ in that order $E$ will run $M$ on $w_i$ and write $w_i$ if $M$ accepts.

($\Leftarrow$) Suppose you had an enumerator $E$ that lists all $w\in L$ in lexicographic order. Use that to construct a decider $M$ which when given $w$ as input, runs $E$ until it finds $w$ among the enumerated strings or fails to find $w$. Your task is to show that it will always either find $w$ or decides it does not appear on the enumeration in a finite amount of time.


Show that if A is regular, then the subset containing only even language strings, is also regular

Could you make a FA that accepts all and only even-length strings? What do you know about the intersection of two regular languages?


Here are some thoughts about the task.

Let us start with reducing all power of 2 from N.
If $N=2^kM$ then we can first apply $$Y=2Y-0$$ $k$ times.

Now you have new task of reaching smaller number $M$ starting with $X=0$ and $Y=1$.

$X\le 0$ and $Y>0$ holds after every transformation. So if $N$ is positive we will reach it with $Y$ and if $N \le 0$ we reach it with $X$.
Replacing $X$ with $X'=-X$ may help thinking.
$$ X' \to 2X'+Y $$
$$ Y \to 2Y+X' $$
looks simpler and is equivalent to the original task.
Applying one operation $k$ times we get
$$ Y \to 2^kY+(2^k-1)X' $$
Another nice representation of the operations:
$$ X' \to X'+(X'+Y)$$
$$Y \to Y + (X'+Y)$$
From 5. after $k$ steps sum of the numbers becomes $2^k$ and we actually add $2^{k-1}$ to one of numbers.
Solution. There is always only one way to reach $N$. Number of operations is $log_2N$. Imagine $N=101110001$ in binary form. Then we go from right to left and change X when there is 0 and Y when there is 1 in binary representation. In this way we finally construct $Y=101110001$ and almost inverted X=010001111. There is only one peculiarity. When we start for the first bit Y is already 1 and we need to apply X transformation instead of Y.


If $L=\big\{\langle M_1,M_2\rangle\mid M_1, M_2\text{ are TM and } L(M_1)\cup L(M_1)=\Sigma^* \big\}$ is in $RE$ or $coRE$ or not in $RE\cup coRE$?

Your proof is not very clear to me. In your description of $M'$ I don't understand what $M_1$ and $M_2$ are, or why they have the properties you claim they do.

A typical reduction proof looks like:

You have some language $L$ which you wish to prove is, say, not $RE$.
You have a language $L'$ which you know is not $RE$.
Suppose there exists a TM $D$ which recognizes $L$
Construct a TM $D'$ to recognize $L'$. Usually $D'$ will take some input $x$ and transform it into an input $y$ for $D$, such that $D'$ accepts $x$ if and only if $D$ accepts $y$

So let's do the same thing for this problem. We'll reduce $TOTAL$ (which is neither $RE$ nor $co-RE$) to $L$.

Suppose $D$ recognizes $L$. Let $D'$ be the TM:

TM $D'$ on input $\langle M \rangle$:

Let $M'$ be the TM that acts as $M$ but inverts the output
Run $D$ on $\langle M, M' \rangle$
Accept if $D$ accepts, reject if $D$ rejects.

Now we want to prove that $D'$ recognizes $TOTAL$. This is straightforward. $\langle M, M' \rangle$ is in $L$ if and only if $L(M) \cup L(M') = \Sigma^*$. But $L(M') = \overline{L(M)}$. So $D'$ accepts $M$ if and only if $M$ either accepts or rejects every input, which is precisely what it means for $M$ to be in $TOTAL$!

So we have shown that no TM can recognize $L$, so $L$ isn't $RE$.

To show that it's not $co-RE$ either we take $D$ to recognize $\bar{L}$ instead, and define $D'$ just as above. So now $D'$ accepts $M$ if and only if $\langle M, M' \rangle$ is not in $L$. The same argument above shows us this is exactly true when $M$ is not in $TOTAL$.


On which stage (lexical analysis, syntax analysys, and so on) is most of the compilation time spent?

For a few compilers I've seen compilation times was reduced 3+ fold when optimization was disabled, so otherwise they spent most time on optimization passes.


Are there any articles or software which can infer original shapes from overlapping shapes?

I'd suggest you start with image segmentation, to identify each of the separate (potentially occluded) shapes in the image.

If there was no occlusion, the problem would then be easy.  For each shape in the image, you could compare it each possible shape in your library of shapes and see if it's a match.  If you don't have to deal with pose/rotation, only possible variation in the size and location of the shape, that will be easy to do: given a shape $S$ from the image and a shape $S'$ from your library of shapes, you first normalize their sizes, then check if they are a match using normalized cross-correlation or something similar.  If you do have to deal with variation in pose/rotation as well, you could use something like SIFT to align $S$ to $S'$, then proceed from there.

However in your example you have to deal with occlusion, and it's occlusion that makes the problem more challenging.  So, let's re-formulate the problem.  You get a bunch of partial shapes $S_1,\dots,S_k$ from your image.  For each $S_i$, you can also derive an occlusion mask $M_i$ that indicates which pixels were occluded by other shapes.  Now you want a way to test whether $S_i,M_i$ is a match to some shape $S'$ in your library.  How to do this?

If you only had to deal with variation in location but not rotation/size/pose, then this would be easy.  It basically comes to checking that $S_i$ matches $S'$ at the non-occluded pixels (they don't have to match at the pixels indicated by $M_i$, but they do have to match elsewhere), i.e., whether $S_i \lor M_i = S' \lor M_i$, where $\lor$ denotes bitwise OR.

So the remaining challenge is how to deal with variation in size and/or rotation/pose.  One approach that might work is to extract all the points on the boundary of $S_i$ (ignoring "boundaries" caused by occlusion) and all points on the boundary of $S'$, and then see if there's a way to make them line up.  Note that we'll have to allow an incomplete match, because the occlusion may mean that the inferred boundary of $S_i$ is incomplete.  One approach for finding a match might be to use RANSAC to estimate a homography between the two sets of points.  (This is vaguely reminiscent of SIFT, but we're using the points on the boundary as the keypoints rather than using SIFT's methods to derive keypoints.)

If you have to deal with more complex images, more complex shapes, or other more complex situations, you could look at the literature on shape analysis and shape context.


How likely is it that a computer miscalculates 1+1?

The probability of read error is bigger than write error, so there is a chance for bitflip on either of $1$ which might occur anywhere.
I can offer description of JVM attack which is not exactly the answer, but shows how much effort is needed to induce bitflips, tells about softerrors and a very successful attack on JVM, given good heat ;).

The probability of error grows the most related with heat dissipation problems, and making chip smaller include it's higher efficiency (performance per watt).

Anyway there is bad assumption - making chip smaller gives more errors - if this were true over time CPUs would generate noticeable amount of errors today.

Please check also this error rate study. With calculating probability of error there is a problem - this is hardware dependent and the most of hardware actually has errors, but they get corrected at several levels, so they do not occur for user, and with invalid / broken piece machine crashes are to often to perform test.


Inapproximability result implies apx-hardness?

If P$=$NP then there is a polytime algorithm for any NP optimization problem, and so every problem is APX-hard. So from now on, suppose that P$\neq$NP.

We can associate with any decision problem $L \in NP$ an optimization problem $o_L$ by defining $o_L(x) = 1$ if $x \in L$ and $o_L(x) = 2$ otherwise. Suppose $o_L$ reduces to $o_M$ via a PTAS reduction $(f,g,\alpha)$ (notation as in the Wikipedia article). Let $C = 1+\alpha(1/2)$. Thus if $y$ is a $C$-approximation to $o_M(f(x))$ then $g(x,y,1/2)$ is a $3/2$-approximation to $o_L(x)$, from which we can determine whether $x \in L$ or not. Altogether, this gives a polytime reduction from $L$ to $M$. Now take any NP-complete language for $L$ and any NP-intermediate language for $M$ (such a language exists because of Ladner's theorem). On the one hand, since $M \notin P$, you cannot 2-approximate $o_M$. On the other hand, $L$ doesn't reduce to $M$ (since that would apply that $M$ is NP-complete), and so $o_L$ doesn't reduce to $o_M$. We conclude that $o_M$ is not APX-hard.


While your algorithm is visiting a node $v$, if it detects a back edge $(v,u)$ then it backtracks until it reaches $u$, using the parent information stored in pi, counts the number of edges,  and then decides if it is bipartite or not. In this case your edges and nodes are visited at most two times (once when you move forward and once when you backtrack) which is still linear, i.e. is $O(V + E)$.

As for average and amortized case analysis I have never done such a thorough analysis of dfs but my guess is both are $O(V+E)$.


Is it possible to build short proofs of arbitrary folds over a huge list?

Yes, there is a generalization of the construction you mentioned.  However, it's utility depends on the function F.  The guarantees you get are meaningful only if F is robust, in the sense that you have to change a large fraction of the dataset to make any (meaningful) change to the output of the computation.

Suppose we have an untrusted agent Agatha who is going to do the computation for us and try to prove that she did it correctly.  She'll build a Merkle tree in the same way, with one leaf per prefix of the list, and the leaf holding (the hash of) the intermediate state of the fold after processing that prefix.  Thus, a list with $n$ items will involve construction of a Merkle tree with $n$ leaves.  Agatha will send the hash at the root of the Merkle tree.  She will also send the value at the rightmost leaf and a witness to its value.  $\newcommand{\pl}{\operatorname{polylog}}$

Agatha will do $O(n)$ work to compute the fold and build the Merkle tree.  We want the verifier to be able to verify the correctness of the result, using only $o(n)$ time and $o(n)$ communication with Agatha.

How will the verifier check Agatha's claimed result?  The verifier can pick two adjacent leafs at random, ask Agatha to send a witness to the values at those two leaves, and re-apply F to check that the second was correctly obtained from the first.  The verifier can repeat this many times.  In each round, Agatha sends $O(\lg n)$ bits, and the verifier does $O(\lg n)$ work.

Now suppose Agatha cheats on at least a $p$ fraction of the F applications.  Will this be detected?  Well, each round has at least a  $p$ chance of detecting Agatha's malfeasance.  Thus, after $100/p$ rounds, there is a $(1-p)^{100/p} \approx e^{-100} < 2^{-128}$ chance that Agatha's malfeasance goes undetected.  In other words, $O(1/p)$ rounds suffice to detect Agatha if she cheats on at least a $p$ fraction of the applications of F.

On the other hand, if Agatha cheats on only a single application of F (say), she has a good chance of getting away with it; the verifier has no good way to detect this.

So, this construction is only useful if F is such that cheating on a small number of applications of F is harmless.  This is closely related to the notion of a robust function, from robust statistics, which is about functions where changing a small number of inputs makes only a negligible change to the final output.  For instance, since the sum, max, and min are not robust, this construction is not useful for computing the sum, max, and min.  However, the median is robust, and the median can be computed securely via such a tree.  As a simpler example, consider counting the number of entries in the database that match some pattern; this can be done securely via such a tree.  In particular, Agatha can cheat on at most a $p$ fraction of nodes, and we can arrange that this changes the final count by at most $pn$.  If that bound on the (additive, absolute) error is good enough, then we can achieve acceptable security.

In practice you probably typically don't want to use this kind of general construction.  You can often do better by building a protocol that is specialized or customized for the particular function F you are dealing with.  You can find many papers on this topic in the research literature, under names like "secure aggregation" or "outsourced computation" or "resilient aggregation".  I've seen papers in the database literature, the cryptography literature, and the sensor network literature.

For example, if F is associative and commutative, and if the fold is robust, then we can obtain a secure Merkle tree scheme, where each internal node in the tree holds the result of the fold on a sublist corresponding to the subtree rooted at that internal node.  (This is a bit different than the prefix construction mentioned earlier, and offers better security when F satisfies this property.  The verifier needs to pick a random node and check that it was constructed correctly, rather than picking a random leaf.)

The preceding paragraph immediately lets you compute the "count" operator securely, up to an additive error of $\pm pn$.  If we want to compute the median, Agatha can first compute the median offline, say $m$, then report $m$, and use a count query to count the number of data items that are $\le m$.  The verifier can verify this count query up to an additive error of $\pm pn$, which proves that $m$ isn't "too far" from the true median (its rank differs from the rank of the true median by at most $\pm pn$, which in practice means it'll be quite close to the true median).

There's lots more one can say, and I've probably made oversimplifications at multiple points in this exposition, but hopefully this gives you some ideas and an entry point to the research literature on this subject.


Is transfer learning applied on only similar datasets only?

Let me start by making an acknowledgement that in machine learning intuitions can be wrong and it is not possible to know beforehand what would work and what wouldn't work. That's why machine learning is very much an experiment based method.
Having made this acknowledgement let me tell you my intuition. If you transfer learning from image processing problem to a different image processing problem then it shouldn't hurt if your network is deep enough. Most likely, a convolutional network's earlier layers find simple features that are useful to describe any image. Like horizontal lines and diagonal lines. Then, the deeper layers vary according to specificity of the dataset to find more complex features.
Even if you are working on a wildly different image problem, what you can try to do is keep the earlier layers constant during the learning and just learn the deeper layers. After some learning you can allow the earlier layers to change as well to do some fine tuning.


What's the difference between physically based rendering and global illumination?

The two terms are, in a sense, orthogonal.

Global illumination refers to any process which simulates indirect lighting. Indirect lighting occurs when light bounces off surfaces or through media. The opposite of global illumination is local illumination, where only illumination directly from light sources is taken into account.

Physically-based rendering is a loosely-defined term, but the general idea is to model lighting, surfaces, and media in a way that is physically plausible. This includes, for example, ensuring conservation of energy, so that the solution to the light transport equations don't blow up.

Generally speaking, PBR can be thought of as a type of GI, but this isn't always the case; it's possible to use physically-based rendering without trying to solve the whole rendering equation. Moreover, PBR doesn't always try to model light exactly; quantum mechanical phenomena such as coherence and polarisation aren't commonly modelled (or are only coarsely modelled) in typical rendering methods.


Is the language of all $a^n$ for which $n$ has an even number of digits in 10-base system regular?

A slightly simpler way is to say that if you consider a string $x\in
L$ of size $p$, then there is a non-empty substring $v$ of $x$ that
you can pump without getting out of the language, if it is
regular. Then you can pump it in $x$ until it exceeds a size
$10^{2m}$, which has to be greater than $p$, such that
$10^{2m+1}-10^{2m} > |v|$. And you necessarily get the wrong number of digits.

In other words, you try to find in the sequence of possible sizes a gap
that is too wide to be jumped by pumping a constant pumping
size $|v|$.

This very simple reasonning also works with the context-free pumping
lemma.

Wide gaps, that cannot be pumped exist as soon as empty gaps can
increase in size beyond any bound. This depends on the definition of
the language.

But using the pumping lemma is often a bit more sophisticated.


Complexity of deciding the satisfiability of a quasi-monotone CNF formula

Obviously this can be solved with the same complexity as boolean SAT. The question is, can we do better. The answer is no: this problem is NP-complete.

You can show it is NP-complete by reducing a regular CNF formula to "quasi-monotone" CNF, as follows:

Since you cannot use positive terms in general, what you want is a new, equivalent, variable in-place of the positive terms. So let $\Phi = {\LARGE\bigwedge}C_i$ be a general boolean sat formula. We will replace all non-negated $x_j$ terms with new variables called $\neg n_{x_j}$. Then, we need to constrain $n_{x_j} = \neg x_j$; so we introduce the following clauses:

$$\left(n_{x_j} \implies \neg x_j\right) \wedge \left(\neg x_j \implies n_{x_j}\right)$$

This essentially means that $n_{x_j} = \neg x_j$. Written in CNF:

$$\left(\neg n_{x_j} \vee \neg x_j\right) \wedge \left(x_j \vee n_{x_j}\right)$$

These two clauses will effectively allow you to replace all your other non-negated terms, and they only leave behind a single non-negated term for each literal (within these clauses), which is allowed in "quasi-monotone" CNF as defined by the question.


How is $ n^{log(n)} > n^c $ always for any c?

In these exercises, you are asked to compare functions only according to their asymptotic behavior.

In this case, $c$ is a constant function of $n$, while $\log(n)$ is a function of $n$ that approaches $+\infty$ when $n$ becomes large.

So, $c > \log(n)$ can only hold for finitely many values of $n$.


What complexity class is this set of grammars? In between NL and P?

This appears "almost P-complete".

I think this is existential and P-complete is universal.

This problem corresponds to, "given (1) a SAT problem, (2) a candidate solution, and (3) a variable A, does (A imply (not A))?" This problem shows the existence of a contradiction (for a single variable).

P-complete corresponds to "given (1) a SAT problem, and (2) a candidate solution, does there exist a variable X such that (X implies (not X))?" By showing there exists a solution, you show the non-existence of a contradiction (for all variables).

Sometimes it's easier to find a contradiction than a solution. Consider a Horn-SAT problem containing the clauses A and (not A). You don't need to check the other clauses.

This assumes the original question is equivalent to finding an "all-in-path" in a "3-digraph" (See: Is there a name for this directed graph and path concept? 3-digraph and all-in-path?

Given a 3-SAT instance S, candidate solution Candidate and a target variable, X, does X imply not X?

We will construct a 3-digraph:

For each literal A and its negation nA, in S, create a vertex.

Rewrite each or-clause in S:

(A or B or C)

((A or B) or C)

(not(not((A or B))) or C)

(not(not(A) and not(B))) or C)

(not(A) and not(B)) implies C)

Since there are 6 permutations of A,B,C, there are 6 rewrites. For each rewrite, add 2 directed edges: nA->C and nB->C.

Create a new vertex, Candidate. For each literal A in Candidate, add a directed edge Candidate->A.

Create a new vertex, XContradiction. Add directed edges X->Xcontradiction nX->Xcontradiction.

(After adding edges, ensure this is a trigraph.)

Is there an all-in-path from S to Xcontradiction?

If we show the non-existence of an all-in-path for each literal (and not just X), then we have decided the corresponding P problem (does Candidate satisfy).


FInding number of ancestors at given depth

We do a dfs starting from the root. we save the entry-time and exit time of each vertex. We build a list containing (height(v),entrytime(v)). Where entrytime is the time in the dfs where we first reached vertex v.

we now sort our list lexicographically (this takes time $\mathcal O(n\log(n))$ ) . Inside this order, the vertices at height $h$ that are ancestors of a vertex $v$ are the elements in the list that are between $(h,entrytime(v))$ and $(h,exittime(v))$.

So the problem is essentially reduced to the following:

Suppose we have an array of integers $a_1,a_2,\dots, a_n$, given $x$ and $p$ how can we find the number of elements in the range $a_1,a_2,\dots, a_p$ that are greater than $x$? (we just need $p-k$).

Various efficient solutions to this are discussed here:


Leftist Tree initialization in O(n) time

The succession $a_i = 2^{-i}i$ is absolutely convergent.

In more elementary terms:

$$
\frac{n}{2} \le \sum_{i=1}^{\log n} \frac{ni}{2^i} \le n\sum_{i=1}^{\infty} \frac{i}{2^i} = n\sum_{j=1}^{\infty} \left( \frac{1}{2^j}\sum_{i=1}^{\infty}  \frac{1}{2^i} \right) = 2n
$$


Is applying a formula a kind of reasoning?

You describe what is called expert system in AI. As such, they are artifacts of articial intelligence research.

As far as the Wikipedia definition goes,

  a reasoning system is a software system that generates conclusions from available knowledge using logical techniques such as deduction and induction,

which is vague enough to cover expert systems.

Is there any "intelligence" or independent reasoning in these systems? Certainly not; they are "stupid" in the sense that they just look up values in a table; no learning happens.

You will have to decide which frame of terminolgy reference you want to apply: academic AI or common sense?


Properties of language that can be enumerated in a finite amount of time with an enumerator?

If the language can be enumerated in finite time, then the language itself is finite. Almost all natural classes of languages include all finite languages: they're regular, context-free, decidable, recursively enumerable, co-RE, ...

I'm not sure what else you'd want to say about finite languages compared to RE languages. It's enough to say that the language is finite; for any property you might be interested in, it's usually very straightforward to prove that finite languages do or do not have that property.


Correct application of the CFL Pumping Lemma

The pumping lemma for CFL states that if $L$ is a CFL, there exists a constant $N \ge 1$ such that for all $\omega \in L$ with $\lvert \omega \rvert \ge N$ there is a division $\sigma = u v w x y$ with $\lvert v w x \rvert \le N$ and $v x \ne \varepsilon$ such that $u v^k w x^k y \in L$ for all $k \ge 0$.
(The pumping lemma for regular languages is similar, the discussion below applies with minor changes).
You want to prove by contradiction that $L$ is not a CFL. So you assume $L$ is a CFL, and get a contradiction to the lemma. This means, in detail:

As $L$ is a CFL, it satisfies the lemma. In particular, there is a constant $N$ such that...
As the lemma states all long strings in $L$ can be divided, you are free to pick one that is easy to work with.
The lemma states there is some division of $\omega$ such that.... for all $k \ge 0$...; to contradict the lemma you have to prove no division works. In practice, you take a given division of your $\omega$ (any division) and for it pick some $k$ for it that doesn't give a string in the language. You might need to divide this into cases.

What happens for strings that don't belong to the language, or are shorter than $N$, is completely irrelevant. It might be that some strings can be pumped, that some values of $k$ work for all strings, ... What is crucial is that for one string $\omega$ (the one you picked) no division works with one value of $k$ (again, the one you picked). As the lemma asserts it works for all long enough strings, with some division for all $k$, one counterexample is enough. Infinite examples prove nothing.


asymptotic tight bounds for quadratic functions

I think I can suggest more easy way. Having $a>0$ in $f(n)=an^2+bn+c$ we can take any $a_1<a$ and then show that $a_1n^2 < an^2+bn+c$ for some $N_1,n>N_1$ , because it is same as $a_1 < a + \frac{bn+c}{n^2}$.
Same we can make for any $a<a_2 \Rightarrow an^2+bn+c < a_2n^2$ for some $N_2,n>N_2$ because it is same as $a + \frac{bn+c}{n^2}< a_2$.
At last we will have $a_1n^2 <an^2+bn+c < a_2n^2$.


Relation between the "Point-Cover-Interval" problem and the "Interval Scheduling" problem

Here is a proof that the two numbers are equal:

  For every interval $I$ consider the largest set of disjoint intervals
  with $I$ as the rightmost interval. This has a size, say $D_I$.

  Now if $D_I = D_J$, then $I$ and $J$ have to intersect, so the set of
  intervals with equal $D_I$ values all pairwise intersect each other, and so have a
  common point (by the 1D version of Helly's theorem, or by just considering the intervals arranged in order of their left endpoints).

  Now if $d = \max D_I$ (the size of the largest set of non-intersecting
  intervals), then we have $D_I$ taking all the values $\{1, 2, \dots, d\}$,
  and thus $d$ points are enough to cover all the intervals, and we need at least $d$ to cover the largest set of disjoint intervals.

For some related reading, look at Mirsky's theorem, which is a dual of Dilworth's theorem.

  Dilworth's theorem says that in a set of elements with a partial order defined on them, the size of the largest antichain
  (antichain is a set of elements not comparable to each other) is same
  as the size of the smallest partition into chains (each set of the
  partition is a total ordered set).

  Mirsky's theorem says that the size of the largest chain is the same as the smallest number of antichains into which the set might be
  partitioned.

In this case defines your order relation as follows:

$$I = (i,j) \lt I' = (i', j') \iff j \lt i'$$

Basically, two disjoint intervals are comparable, with the left one being smaller.

Because of Helly's theorem, the two numbers you are computing are exactly the numbers in Mirsky's theorem, which is defined as the height of the the partial order (Dilworth's theorem defines the width).


Separate Chaining hashing: time complexity of successful search

The expected length of a chain when the $i$th element is added is $\frac{i-1}m$. So if we mentally re-order the elements in the hash map to be in order of insertion, we can calculate the expected length of a chain $E[l]$ when performing a search with $n$ elements in the map:

\begin{align}
E[l]&=\frac{1}{n}\sum_{i=1}^n \frac{i-1}m = \frac{1}{nm}\left(-n + \sum_{i=1}^n i\right) = \frac{1}{nm}\left(-n + \frac{1}{2}n(n+1)\right)\\
E[l] &= \frac{1}{m}\left(-1 + \frac{1}{2}n+\frac{1}{2}\right) = \frac{n}{2m} - \frac{1}{2m}
\end{align}

Now you can substitute $\alpha = \frac n m$ and find $E[l] = \frac \alpha 2  - \frac{\alpha}{2n}$.


Semidecidability/Decidability for strings seperated by a non alphabet symbol

First, a few things that may or may not help:

Def: A language $L\subseteq \Sigma ^*$ is Recursive (R) if there is some algorithm that, when given $u\in \Sigma^*$, will return $1$ iff $u\in L$ and $0$ iff $u\not\in L$.
Def: A language $L\subseteq \Sigma ^*$ is Recursively enumerable (RE) if there is some algorithm that, when given $u\in \Sigma^*$, will return $1$ iff $u\in L$. (If $u\not\in L$, ir may return $0$ or loop forever)
Prop: A language $L$ is RE iff there is some algorithm that enumerates $L$. One way to formalize "$\mathcal A$ enumerates $L$" would be to say that the algorithm $\mathcal A$ takes an integer $n\in \mathbb N$ and returns some $\mathcal A(n)\in L$ for each $n$, and that for any $u\in L$ there is at least one $n$ so that $\mathcal A(n)=u$ (i.e. if you look at the algorithm as a function $\mathcal A:\mathbb N \to L$, it is surjective).
Remark: Even though the notins of R and RE seem to depend on the alphabet, they do not. If you have an algorithm $\mathcal A$ that takes a word $u\in \Sigma$ as input, you create the one that takes $u\in \Sigma'^*$ by returning $0$ if $u\not\in \Sigma$ (which is decidable) and then running $\mathcal A$. And in the other direction, you can just reuse the same algorithm.

Now, take some alphabet $\Sigma$ so that $;\not\in\Sigma$ and let $\Sigma':=\Sigma\sqcup \{;\}$.

To show that your $L'$ is indeed RE, just take the algorithm $\mathcal A$ that proves that $L$ is RE. When given $x\in \Sigma^*$, you want to know if there is some $y\in \Sigma^*$ so that $x;y\in L$. The problem with simply trying for each $y\in \Sigma^*$ is that your first call to $\mathcal A$ may never terminate and you'll have looped on a possibly positive instance. What you want to do instead is this: for $n$ from $0$ to $+\infty $, for each word $y\in \Sigma^*$ of size $|y|\le n$, run $\mathcal A$ on $y$ for $n$ steps (or seconds) and if it returns $1$, return $1$. So you're trying bigger a bigger $y$ while giving more and more time to $\mathcal A$ to finish. If there is some $y$ so that $x;y\in L$, then you'll eventually try for this $y$ and give $\mathcal A$ enough time to tell you it's the corect $y$. And if it answers yes, then clearly, there is some $y$ so that $x;y\in L$. So we just proved that $L'$ is RE.

Using the property I gave above, there is another simpler proof. You suppose that you can enumerate $L$ and want to enumerate $L'$. Well clearly, you just have to enumerate $L'$ and drop the $;$ and whatever is after it.

If you suppose that $L$ is R then $L'$ may not be R. Recall that the halting problem $HALT=\{\langle M,w\rangle|M\text{ halts on input }w\}$ is undecidable (i.e. $HALT\not\in R$). Let $BHALT:=\{\langle M,w\rangle;n|M\text{ halts on input }w\text{ in at most }n\text{ steps}\}$. Clearly $BHALT\in R$: you can just simulate $M$ on $w$ for $n$ steps and then check if the last state is final. But if you take $L=BHALT\in R$, then $L'=HALT\not \in R$.


Is the language that consists of machine configurations whose language is a subset of even palindromes semi-decidable?

What you have shown is that the language of Turing machines accepting at least one even palindrome is semi-decidable. However, your question is interested in the language of Turing machines accepting only even palindromes, which is rather different. The complement of this language is the language of Turing machines accepting at least one word which isn't an even palindrome, and so the complement is semi-decidable according to your argument. This still leaves open the question of whether the original language is semi-decidable (and so decidable).


How are programming languages and foundations of mathematics related?

[Note: this paragraphs is now outdated.] The title of your question contains an unwarranted assumption, namely that programming languages are "based on foundations of mathematics". This is generally not the case, although the two areas do have important relationships. A more accurate statement would be that (some) programming languages were designed using foundational techniques. A better question to ask would be "how are programming languages and foundations of mathematics related?"

The most general connection is embodied in the slogan proofs-as-programs, which can be made to work in several ways. The Curry-Howard correspondence is the most obvious one. With it we relate at once type theory, logic, and programming. But it should be emphasize that the Curry-Howard correspondence does not work very well in the presence of general recursion (because every type becomes inhabited), which every general-purpose programming language supports.

A subtler way of making the slogan proofs-as-programs work is to use realizability. Here too we relate proofs and programs, but now the direction goes from proofs to programs: every proof gives a program, but not every program is necessarily a proof.

The main example of a programming language based on a foundation is Agda, which simply is an implementation of dependent type theory. However, Agda is not a general-purpose programming language because it does not support general recursion. Every function in Agda is total, and there are computable functions which cannot be implemented in Agda. In practice programmers won't notice this, but they will notice that Agda does not allow undefined values, for example infinite loops.

Coq is not a programming language but rather a proof assistant. However, it too has extraction capabilities which give programs from proofs. Proof assistants and programming languages should not be confused with each other.

We should not forget that prolog and other logic programming languages take their inspiration from the idea that computation is proof search. This of course relates them closely to logic.

Haskell is a general-purpose programming language which is based on domain theory. That is to say, its semantics is domain-theoretic because it has to account for partial functions and recursion. The Haskell community has developed a number of techniques inspired by category theory, of which monads are best known but should not be confused with monads. More generally, advanced programming features are usually treated with a combination of domain theory and category theory, but this is not something that the Haskell programmer in the street is adept at. The so-called "syntactic category" of Haskell types is a lay man's view of how Haskell and category theory correspond to each other.

Set theory (classical or constructive) seems to inspire ideas in programming language to a lesser extent. Of course, constructive set theory has its connection to programming through constructive logic. One important application of intuitionistic set theory to programming languages was given by Alex Simpson who used it to make synthetic domain theory work. But this is quite advanced stuff, maybe see these slides. Jean-Louis Krivine has developed a very interesting brand of realizability for classical set theory. This seems a good way to relate classical set theory and programming.

In summary, the theory of programming languages uses foundational techniques. This is not surprising, as we consider computation to be a fundamental concept. But it is too naive to say that programming languages are "based" on a certain foundations. In fact, the trichotomy of foundations "set theory -- type theory -- category theory" is again just a useful high-level observation that can be made mathematically precise in various ways, but there is nothing necessary about it. It is a historic accident.


Augmenting a tree such that we preserve the insertion operation optimal runtime

I think you mean $successor$ & $predecessor $.

Formally:
$predecessor(v): x  $ s.t $ x \leq v$ (or smaller if your keys are distinct) and no $y$ exists in your structure s.t $y \leq v$ and $y > x $

Symmetrical definition for $successor(v)$.

You can apply several methods for each node to know its $successor/predecessor $ in $O(1)$ time. A simple option is pointers - you "pay" $log(n)$ while inserting, pay another $log(n)$ to find $successor/predecessor$, and update the corresponding fields.

A doubly linked list would work just as well (in which case you save pointers to the list in the tree nodes, from which you can go to next or previous list node for successor/ predecessor respectively)

btw, your example is wrong. the key '77' cannot be in the right subtree of '80'


Are there peer-reviewed papers studying the pros and cons of functional programming?

There is a famous paper "Why Functional Programming Matters" by John Hughes. The main argument of this paper is the modularity of functional programs.

Also, the work by Chris Okasaki about functional data structures is very interesting. The article "Red-Black Trees in a Functional Setting" provides a very clear implementation of red-black trees using functional programming language, which is much simpler than their imperative implementation in the book "Introduction to Algorithms" by Tomas H. Cormen et al.


The bounded halting problem is decidable. Why doesn't this conflict with Rice's theorem?

The language

$\qquad \{(α,x,n):M_α \text{ accepts } x \text{ in less than } n \text{ steps}\}$

is not an index set, that is it is not of the form

$\qquad L_P = \{ \langle M \rangle \mid M \text{ is TM},\ \exists\, f \in P.\ f_M = f \}$

for some set of (partial recursive) functions $P$, with $f_M$ the (partial) function computed by TM $M$. Rice's theorem makes statements only about such $L_P$; many "intuitive" rephrasings are not helpful. See also here.

Note that this is not only a technical detail here. Rice's theorem does not apply to

$\qquad L = \{ \langle M \rangle \mid M \text{ accepts } \langle M \rangle \text{ in less than } \langle M \rangle \text{ steps} \}$,

either. Can you see why?

   For every machine in $L$ you can easily construct many machines that accept the same language but run for more than $\langle M \rangle$ steps, and thus are not in $L$. Thus, $L$ is not an index set.

$L$ is decidable, using the same argument as for the original language we're discussing.


What would be the time complexity for following recurrence?

You asked for a solution with the Master Theorem, so let's have a look;

Define your Function as $T(n) = a \cdot{} T \left( \frac{n}{b} \right) + f(n)$. Here you have $a = 1$, $b = 2$ and $f(n) = 2^n$.

Master Theorem has 3 main cases (e.g. shown here):

Case 1 - $f(n) \in \mathcal{O} \left( n^{\log_b(a)-\epsilon{}} \right)$ with $\epsilon > 0$

Case 2 - $f(n) \in \Theta \left( n^{\log_b(a)} \log^k n \right)$ with $k \geq 0 $

Case 3 - $f(n) \in \Omega \left( n^{\log_b(a) + \epsilon}  \right)$ and $a \cdot f \left( \frac{a}{b} \right) \leq c \cdot f(n) $ for large $n$ and some constant $c < 1$

Let's check, which one applies: Inserting $a$ and $b$ into $\log_b(a)$ gives $\log_2(1) = 0$ we get $n^{\log_b(a)} = n^0 = 1$ resulting into $f(n) \in \Omega \left( n^{\log_b(a) + \epsilon}  \right)$.

The other precondition also holds obviously (just put in the numbers for $a$ and $b$ and find a $c$ for yourself).

This results in the 3rd case of the Master Theorem, giving $T(n) \in \Theta (f(n)) = \Theta (2^n) $.


Is there a way to efficiently parse this grammar?

The grammar is ambiguous: (I used | for a and * for b because I find it easier to read.)

||*|*||*|*||
((*(*))*(*))
((*)*((*)*))

However, you can use an Earley grammar to find all possible parses in worst-case cubic time. (As long as you are satisfied with a graph representation of "all possible parses" since the maximum number of parses of a string of a given size is exponential.)

I found this example by using a bison GLR grammar and iterating over inputs until I found one which produced an ambiguity. Out of laziness, I produced the list of inputs by generating all strings consisting of $n$ | and $n$ *| where the first element is |. Most of these inputs are syntax errors, but for small $n$ it doesn't matter.

Here's a simpler approach, using Python to generate valid inputs:

def gen(s, n):
  """Generate left-most derivations of 's' with maximum length 'n'"""
  if n > 0:
    i = s.find('T')
    if i == -1:
      yield s
    else:
      yield from gen(s[:i]+'|*|'+s[i+1:], n)
      yield from gen(s[:i]+'|T*|'+s[i+1:], n-1)
      yield from gen(s[:i]+'|*T|'+s[i+1:], n-1)
      yield from gen(s[:i]+'|T*T|'+s[i+1:], n-2)

If this function generates the same string twice, that string is ambiguous since it has two left-most derivations.