Building a verifier for sentences involving addition over the natural numbers

$\left(\mathbb{N},+\right)$ is a model of Presburger arithmetic. Persburger arithmetic is a complete theory (see the answer here), so for any model $\mathcal M$ for Presburger arithmetic (lets denote this theory by $T$) and every first order formula $\varphi$ in the language of $T$ it holds that:

$\mathcal{M}\vDash \varphi \iff T \vdash \varphi$

To see why this follows for completeness, assume $M\vDash \varphi$, then obviously $T\not\vdash \neg\varphi$, thus by completeness $T\vdash\varphi$ (the $\Leftarrow$ implication is trivial).

This shows you why your question reduces to finding a decision procedure for Presburger arithmetic. This has a known double-exponential lower bound, you can find a proof in Rabin and Fischer's paper "Super-Exponential Complexity of Presburger Arithmetic". This bound also holds for nondeterminstic algorithms.


Does upgrading after all locks and before all unlocks violate 2PL?

It's allowed.
You can upgrade any locks during the growing phase, and downgrade any locks you want during the shrinking phase, and it's a valid 2PL. What you can't do is release/downgrade during the growing phase, or acquire/upgrade during the shrinking phase, because this breaks the phase ordering rule.
Note that even during the shrinking phase, downgrading breaks strict 2PL, because it releases an exclusive lock. More on this in a moment.
I think the reason why you may be asking is that your example transaction reads Y, then upgrades, then writes Y. You may be wondering what happens if some other transaction holds a shared lock on Y, and also wants to upgrade.
This is a deadlock situation, so one of them wins and the other transaction is aborted, or rolled back to at least the point where the shared lock on Y was acquired. The lock upgrade operation can and does cause aborts. Similarly, downgrading can cause cascading aborts, which is yet another reason why most database systems prefer strict locking.


Considering non negative case we have
$$O(f)=\{g: \exists C>0, \exists N \in \mathbb{N}, \forall n>N, g(n) \leqslant Cf(n)\}$$
From this definition for $\forall C>0,$ we have:
$$ C \cdot O(f)= O(C \cdot f) = O(f)$$
It can be written also as:
$$C \cdot g \in O(f) \Leftrightarrow g \in O(C \cdot f) \Leftrightarrow g \in O(f)$$
without any additional condition.


Perfect Probabilistic Encryption still requires key length about as long as message

It seems you have to use some different approach. There is a hint in Arora/Barak's book. From that hint, I got the following solution.

Again we set $x_0=0^{n+10}$. The algorithm $A$ works as follows. Let $y=E_k(x_b)$ be its input. Let $Y_{x_1}$ denote the set of ciphtertexts $y$ such that there exists some $k$ satisfying $D_k(y)=x_1$ ($D$ is the decryption algorithm). The algorithm $A$ outputs $1$ if and only if $y\in Y_{x_1}$ (so $A$ runs in polynomial time if P = NP). Then we have

$$\mathrm{Pr}_{b \in \{0,1\}, k \in \{0,1\}^n}[A(E_k(x_b)) = b ]=\frac{1}{2}\left(1-\mathrm{Pr}_{k\in\{0,1\}^n}[E_k(x_0)\in Y_{x_1}]\right)+\frac{1}{2}.$$

If this probability is less than $9/10$ for all $x_1\in \{0,1\}^{n+10}$, then we have $\mathrm{Pr}_{k\in\{0,1\}^n}[E_k(x_0)\in Y_{x_1}]>1/5$. This means $\mathrm{Pr}_{k\in\{0,1\}^n,k'\in\{0,1\}^n}[D_{k'}(E_k(x_0))=x_1]>2^{-n}/5$. Note this inequality holds for all $x_1\in \{0,1\}^{n+10}$, which means

\begin{align}
1&=\mathrm{Pr}_{k\in\{0,1\}^n,k'\in\{0,1\}^n}[D_{k'}(E_k(x_0))\in\{0,1\}^{n+10}]\\
&=\sum_{x_1\in\{0,1\}^{n+10}}\mathrm{Pr}_{k\in\{0,1\}^n,k'\in\{0,1\}^n}[D_{k'}(E_k(x_0))=x_1]\\
&>\frac{2^{n+10}\cdot2^{-n}}{5},
\end{align}

a contradiction!


Time complexity of a vertical sweep algorithm with histogram computations

$O(h)$ sounds hard to believe, unless there's some pre computation that's not counted here, as it takes $\Theta(hw)$ time just to read every pixel of the image.

Computing a histogram from scratch can't be done in $O(1)$ time.  But updating a histogram can be done efficiently.  If you already have a histogram for some set of pixels, and then you add or delete one pixel, you can update the histogram in $O(1)$ time.  This kind of idea can be used to speed up the sort of thing you're talking about, because all of the histograms we want are closely related.

In particular, when we increment $l$, we add or delete a row from a histogram.  Thus you can update the histogram more efficiently than computing it from scratch.


Several simple propositions about regular languages

In all following counterexamples, $A$ and $B$ are subset of the full language $F=\{0,1\}^*$. Note that $F$ is a regular language.

  If $A$ is regular pumpable $B\subseteq A$, then $B$ is regular pumpable too.

Counterexample: $A=F$ while $B$ is any non-regular-pumpable language.

(It is taken for granted that a language being regular-pumpable means it is able to be pumped like a regular language. There are different ways to define being able to be pumped like a regular language; however it is defined, $\{0^n1^n\mid n\ge 0\}$ will not be regular pumpable. I made this note since some non-regular languages can be pumped like a regular language. For example, $\{ 01^{n^2} \mid n \ge 1 \} \cup \{ 0^kw \mid k\neq 1, w\in \{1\}^* \}$ is non-regular but can be pumped by the most common version of the pumping lemma for regular languages.)

(In case "regular pumpable" for a language is defined simply as "regular", just let $A=F$ and B be any non-regular language for a counterexample.)

  If $A$ not regular pumpable and $A\subseteq B$, then $B$ is not regular pumpable too.

Counterexample: $B=F$.

  If $A$ is regular and $B\subseteq A$, then $B$ is regular too.

Counterexample: $A=F$ while $B$ is non-regular.

  If $A\cap B$ is regular, then $A$ and $B$ are regular too.

Counterexample: $A$ is not regular while $B=F\setminus A$. $A\cap B=\emptyset$ is regular.

  There is at least one finite language on the alphabet $\{0,1\}$, that doesn't meet the pumping lemma rules.

That is not true. All finite languages are regular and, thus, meeting the pumping lemma rules.

  How do you come to that conclusion?

Mostly experience and knowledge plus a bit of luck. Before proving any proposition, you would like to do some sanity check with some simple and/or extreme cases. For example, you might have noticed that I have used the simple and extreme language $F$ several times.


Writing a program to find polynomial $f(x)$ from $f(1)$ and $f(f(1))$

The conditions $f(1) = p$ and $f(p) = q$ imply the following two equations:
$$
\begin{align}
&\sum_{i=0}^n a_i = p, \\
&\sum_{i=0}^n a_i p^i = q.
\end{align}
$$
When $p < 0$ or $p$ is not an integer, there are no solutions. When $p = 0$, the first equation implies that the polynomial must be $0$ and so $q = 0$.
When $p = 1$, the equations imply that $p = q$, and the first equation implies that the solutions are the polynomials $1,x,\ldots,x^n$. From now on, we assume that $p \geq 2$.

Intuitively, the polynomial minimizing $\sum_i a_i$ under the second constraint above is obtained by writing $q$ in base $p$ notation (first $n$ digits) and putting the rest as a coefficient of $a_n$. Denote this solution by $b_0,\ldots,b_n$. If $\sum_i b_i > p$ then there is no solution. If $\sum_i b_i = p$ then we have found the unique solution. From now on, suppose that $\sum_i b_i < p$; this implies that the base $p$ expansion of $q$ has length at most $n+1$.

The given equations imply more constraints. First of all, $q \geq p$. Second, since $p \equiv 1 \pmod{p-1}$, we must have $q \equiv p \pmod{p-1}$. Starting with the polynomial $g(x) = \sum_{i=0}^n b_i x^i$, we can increase $g(1)$ by applying the update $(b'_{i+1},b'_i) \gets (b_{i+1} - \alpha,b_i + p\alpha)$ (when $b_{i+1} \geq \alpha$); this increases $g(1)$ by $\alpha(p-1)$. We can apply these updates systematically, moving the mass all the way to the polynomial $q$. Since $\sum_i b_i < p \leq q$ and $q \equiv p \pmod{p-1}$, somewhere along the way we will find a (unique) polynomial satisfying both requirements above.

How do we perform this process algorithmically? We go over the indices from $b_n$ to $b_1$ in order. At each point, we subtract from $b_i$ the maximal amount $\alpha$ which keeps the invariant $g(1) \leq p$. After processing $b_1$, we should reach the desired polynomial. (We are basically looking at the base $p-1$ expansion of $p - g(1)$.)


Is it possible to prove that this algorithm is big Omega $n^2logn$ time complexity?

Your recurrence can be written as:
$
T(n) = T(n/2) + f(n)
$, where $f(n) \in \Theta(n^2)$.
Then, by case 3 of the Master theorem, you have $T(n)=\Theta(n^2)$. This means that you won't be able to prove a lower bound of $\Omega(n^2 \log n)$.


Can you automatically generate a parser for a type using type theory some how?

In programming languages, we usually distinguish concrete syntax, where a program is represented as a linear list of symbols, from abstract syntax, where programs have a tree structure.

The vast majority of PL theory, including most type systems, happens after parsing, working with abstract syntax.

So, it's impossible to generate a parser simply from type rules or definitions, because there are arbitrarily many concrete syntaxes that could correspond to any abstract syntax. The choice is a purely human one.

In some languages, like Haskell, the description of a data type can be used to generate parsers and printers for types, using the deriving mechanism of the typeclass system. But it chooses a syntax that corresponds to the Haskell one by convention, and they could have chosen to define it any other way.


Is the number of nodes in an ORBDD 2n + 2?

It doesn't say that. To quote:

  Let us consider the Boolean function $f(x_1,\ldots, x_{2n}) = x_1x_2 + x_3x_4 + \cdots + x_{2n-1}x_{2n}$. Using the variable ordering $x_1 < x_3 < \cdots < x_{2n-1} < x_2 < x_4 < \cdots < x_{2n}$, the BDD needs $2^{n+1}$ nodes to represent the function. Using the ordering $x_1 < x_2 < x_3 < x_4 < \cdots < x_{2n-1} < x_{2n}$, the BDD consists of $2n + 2$ nodes.

It is only talking about that particular function, and demonstrating the difference that different variable orderings can make.

As it says a few lines later:

  There are functions for which the graph size is always exponential — independent of variable ordering.

Bryant [1] proves several functions have exponentially sized OBDDs, regardless of the variable ordering (see for example Theorems 2 and 4 in the paper).

References

Randal E. Bryant, "On the Complexity of VLSI Implementations and Graph Representations of Boolean Functions with Application to Integer Multiplication", IEEE Trans. on Computers, 40(2):205-226, 1991.


Which permutations can not be obtained by moving elements through two stacks?

This process is called stack sorting. Wikipedia has a page on the subject.

Here you read that the number of possible sequences when the input is $1,2,\dots,n$ equals the Catalan number $C_n = \frac{1}{n+1} {2n\choose n}$, which differs from your guess.

In fact there is a nice characterization of the orders which are possible, they avoid the permutation pattern $231$. However your problem is "backwards", not the strings that can be sorted using a single stack, but the strings that can be obtained that way.


2-Approximation algorithm for for messages across a cyclic network

Start with an integer program for your problem.
For each $i$, there is a variable $x_i \in \{0,1\}$ which represents which way the $i$'th message is routed. You can express the number of messages going through an edge $e$ as some linear combination $y_e$ of the $x_i$'s. Your goal is to minimize $\max(y_e)$. Equivalently, you want to minimize $m$ under the constraints $m \geq y_e$.
Now consider the LP relaxation. Determine which way to route the $i$'th message by rounding $x_i$.


How to prove the linear context free languages are closed under gsm mapping?

If you know that gsm mappings can be written as a composition of an inverse morphism, intersection with a regular language, and a morphism, then it suffices to observe that the linear languages are actually closed under these operations.


What are the pros and cons of RANSAC versus Hough Transform?

The Hough transform would be a reasonable approach for this.  Another reasonable approach would be to find connected regions of similar hue, and for each, test if it is approximately pool-ball-shaped.

RANSAC doesn't seem like a good tool for this purpose.  RANSAC is commonly used to find, e.g., a line that approximately  goes through a bunch of points (but possibly with a few outliers that might not fit the line).  Here, the pool balls are spheres, not lines.

RANSAC is typically used for other tasks: e.g., for aligning two images.  However, here image alignment probably isn't a good way to find pool balls on a pool table.


Build a histogram from a very large data sample

One reasonable method is to choose a random sample of, say, 1000 items from the array.  This can be done in a single pass (say, using reservoir sampling) or using random access (but here we need only 1000 random accesses, so this is probably faster than a single linear pass through the data).

Compute a histogram of those 1000 items, and use that to select bin ranges.

Then, perform a second linear pass on the entire dataset where you accumulate counts in those bins, using those bin ranges.

This will be efficient (nearly as efficient as the naive approach), and help you avoid degenerate histograms.

There are more sophisticated methods that are possible as well, from the literatures on streaming algorithms.  For instance, you can use a streaming algorithm to estimate the quantiles of the data, which lets you estimate the IQR in a single pass through the data, then you use these estimated information to choose bin boundaries, then perform a second linear pass where you accumulate counts in those bins.    There are also streaming algorithms to estimate the histogram counts, then you can use that to choose bin boundaries, then perform a second linear pass where you accumulate counts in those bins.  There's a beautiful literature on this subject.  See, e.g., Tracking Quantiles of Network Data Streams with Dynamic Operations by Cao et al, Approximate Frequency Counts over Data Streams by Manku et al, and many others.  That said, while this is principled and elegant, it might also be more complex than necessary -- simple random sampling might be good enough for your needs.


Start at the end! There is only one applicable production: #8. $D$ moves backward over the $A$'s turning them into $a$'s. Then use #9, and repeatedly #10.

Please take a piece of paper and count the $a$'s generated. Probably the expression $(n+1)^2 = n^2+2n+1$ is useful.


Approximating sign function by tanh in Multi Layer perceptrons

Here's one solution. The central insight is that your error becomes exponentially smaller as $w^tx$ increases. In particular, $1-tanh(x)$ approximates $1$ exponentially fast. That is, for positive $x$:

$$\frac{1-tanh(x)}{1-tanh(x+1)} \geq \frac{tanh(0)}{tanh(1)} \approx 4.19\ldots = \alpha$$

In fact, its asymptote is at $e^2$. I didn't know that, but Wolfram Alpha did. You can use this fact to estimate your error. Let $\tau = sign(w_1^Tx)$ be the target, and let $E(w_2^Tx)=|\tau-tanh(w_2^Tx)|$ be the error. Figure out a weight vector $w$ that will give you $w^Tx=1$. Then $E(kw^Tx) \geq \alpha \cdot E((k+1)w^Tx)$ for any positive number $k$, because of the exponential improvement we just discovered. This is great; now we've reduced our problem to finding a good $k$. We know that for $k=0$, your estimate is $tanh(0)=0$ so $E(0)=1$, and every time you increment $k$ by $1$, your estimate becomes at least $\alpha \approx 4.19$ times as good. So, we solve the following simple equation:

$$\frac{1}{\alpha^k} \leq \varepsilon, \quad\text{so} \quad k \geq \ ^\alpha log\left(\frac{1}{\varepsilon}\right)$$

Hope this helps.


Is it possible to include numerical values or constants within brackets(time complexity)?

What you read is slightly unusual, but absolutely correct. Follow the definition of Big-O literally: It means there is a c > 0 such that for large n, f(n) <= c * 0.5 * n^2. It’s exactly the same as O(n^2), except that the constant c is different (twice as big will work).

In your example, for n >= 5 we have 5n <= n^2 and therefore 5n^2 + 5n <= 6n^2. So f(n) <= 12 * 0.5 n^2 and f(n) <= 6*n^2, c=12 instead of c=6.


In what sense are dataflow architectures non-deterministic?

Are dataflow architectures non-deterministic in the sense of Non-Deterministic Turing Machine?

In principle one could create a non-deterministic dataflow architecture, but that would be a bit odd.  There is nothing about dataflow that fundamentally requires determinism or non-determinism.

Normally I'd expect that a dataflow architecture would be deterministic in the sense that the result of the computation is a deterministic function of the inputs (in principle it doesn't have to be that way, but that's probably the common case for a dataflow architecture).  Of course, the order in which intermediate values are computed might not be deterministic, even though the result is.  See Why doesn't parallelism necessarily imply non-determinism? for a detailed explanation of that point.

Beware that there are multiple meanings of the word "non-determinism".  One meaning is non-determinism in the sense of a non-deterministic Turing machine, i.e., there can be a choice of transitions and the machine magically makes the best choice at every step; this is not implementable directly in real-world machines, so is purely a theoretical nothing.  Another meaning is that the system is not deterministic, e.g., there are aspects of its behavior that are not specified or random; those are resolved somehow but not necessarily by choosing the best choice.  Occasionally I've seen people use the word "indeterminism" for the latter notion, but that seems to be pretty rare.  See also  Differences and relationships between randomized and nondeterministic algorithms?, https://cs.stackexchange.com/a/38158/755, https://en.wikipedia.org/wiki/Nondeterministic_algorithm, https://en.wikipedia.org/wiki/Indeterminacy_in_computation.


Can I make last part of counting sort become to be starting from lowest index?

Prior to the last loop, c[i] holds the index of last element of bucket i plus 1. It's why when you use c[i] to address items in bucket i you need to go back. But c[i-1] contains index of the first element of bucket i, so you can just use it... except that you need index for bucket 0 too.

So the simplest way is to modify third cycle making it to write initial index of bucket i to c[i]. It may be done f.e. with extra temporary (note that i in revised loop starts from 0):

sum = 0;
for (int i = 0; i <= 5; i++)
{
    sum += c[i];
    c[i] = sum - c[i];
}

Note that since indexes in b starts from 1, you need to pre-increment c[a[i]] in new version of last loop (if indexes in b should go from 0, do post-increment instead):

for (int i = 1; i <= 8; i++)
{
    c[a[i]]++;
    b[c[a[i]]] = a[i];
}


Understanding the reduction of REGULARTM from ATM

Let's look just at $M_2$ for the moment. If $M$ accepts $w$, then $M$ will accept strings of the form $0^n1^n$ in step (1) and everything else in step (2). In other words

If $M$ accepts $w$, then the language $L(M_2)=\Sigma^*$, which is of course regular.

Now if $M$ doesn't accept $w$, then $M_2$ will accept all and only strings of the form $0^n1^n$, so $L(M_2) = \{0^n1^n\mid n\ge 0\}$ and this language is certainly not regular.

The important thing here is that we don't have to run $M$ on $w$ to decide its behavior: the behavior is determined solely by whether $M$ accepts $w$ or not. Since $R$ was assumed to be a decider, it doesn't have to run $M$ to determine whether the language of $M_2$ is regular or not; because $R$ is a decider it is by definition assumed to be able to tell that.


Problem with the pseudo random number generator One-Time-Pad

You seem to have misunderstood what the key is.

In the context of symmetric encryption, the key is a shared secret: something that is known to both the sender and receiver.  For OTP, the key is the entire pad and, if two people wish to encrypt some message using OTP, they must ensure beforehand that they have a long enough pad to do that.

For your proposed "efficient" OTP, the key is the PRNG seed: both parties must ensure beforehand that they know it. Then, they both initialize the PRNG with the same seed and it is guaranteed to produce the same sequence of "random" numbers for each of them.

However, note that this is a massive, massive weakening of OTP.  An actual OTP gives perfect security, as long as the pad is kept secret.  If you intercept the 17-character message

nsmklmfmwnfmngner

you have zero knowledge of whether it is

maketrumpthepotus

encoded with one pad, or

ensureclintonwins

encoded with a different pad. Or

kittensarethebest

or literally anything else. However, using a pseudorandom pad means that only certain pads are possible (maybe there's no key at all that encrypts the kitten message to "nsmklmfmwnfmngner", so you can rule that out).  Anybody who knows the PRNG algorithm can start guessing keys to try to decrypt messages.  Anyone who captures some pad material can start trying to reverse engineer the PRNG.  Anyone who captures encrypted messages can start trying the same.

You really shouldn't call it OTP unless the key material is as long as the message. Your proposal for using a PRNG is just a generic stream cypher.


Can area-partitioning lose included points due to floating point precision?

This is a problem for anyone making graphics cards: To draw an area, it will usually be split into triangles, and for many drawing methods it is important that every point is drawn exactly once.

At some point you'll have use an algorithm that decides whether a point x is on or above a line l, and at some other point you'll have an algorithm that decides whether x is below the line l. For good results, you need to design this algorithm carefully so it is guaranteed to say "YES" once and "NO" once. It doesn't matter too much whether the result is correct (not saying YES when the point is actually just a tiny bit below the curve), what's important is that the answer is "YES" exactly once and not twice.


Minimum depth of addition and multiplication circuit using XOR and AND gates

You can simulate an OR gate using a constant number of AND and XOR gates:

$$x \lor y = ((x \oplus 1) \land (y \oplus 1)) \oplus 1.$$

Consequently, anything you can do in depth $d$ using AND and OR gates, can be done in depth $\le 3d$ using AND and XOR gates.


How to compute $\mathbf{X}^T \mathbf{X}$ efficiently for large $\mathbf{X}$?

"Blocked matrix multiplication" is one way to optimize matrix multiplication for memory access.

From "Using Blocking to Increase Temporal Locality" by Bryant and O’Hallaron (2012):

  Blocking a matrix multiply routine works by partitioning the matrices
  into submatrices and then exploiting the mathematical fact that these
  submatrices can be manipulated just like scalars.

"The cache performance and optimizations of blocked algorithms" by Lam, Rothbrg, and Wolf (1991):

  ...presents cache performance data for blocked programs and evaluates
  several optimizations to improve this performance.

More lecture notes:

Matrix Computations (CS 6210): Week 1 by David Bindel (accessed
Feb 23, 2016)
CS 267 Applications of Parallel Computers Lecture 2:
Memory Hierarchies and Optimizing Matrix Multiplication by James
Demmel (accessed Feb 23, 2016)


Problem with forming a context-free grammar describing a language

$S \to aSb \mid Abb, A \to aaa \mid aab \mid \ldots \mid bbb.$ That's it.
First create an equal number of $a$s and $b$s with $S$. Eventually go to the $Abb$ rule creating two extra $b$s and then terminate with $A$ to any string of length $3$.


The use of multiset ordering in proving termination

As I understand the paper (and I was not familiar with it before) to prove termination of a program using the method of Floyd it is enough to find a function $\tau$ that maps the states of the program into some well-founded set $(S,\prec)$ such that this function is consistent with the program steps. Here consistency means that if a state $s$ follows $s^\prime$, then $\tau(s^\prime)\prec \tau(s)$.

Prior to Manna and Dershowitz the method of Floyd was used by mapping the states into the set of natural numbers or into the set of $n$-tuples thereof with lexicographic ordering (both sets are well-founded). The authors suggest a new source of well-founded sets for the Floyd method, that is the set of multisets of finite structures with multiset ordering and show how this can simplify termination proofs.

Note also that contrary to the sets of natural numbers and lexicographically ordered $n$-tuples, multisets ordering is only a partial ordering.


How to solve recursion T(n)=T(n/2)+T(n/3)+n?

This is a straightforward application of the Akra-Bazzi theorem.

You can also show that $T(n) = \Theta(n)$ by induction. First, clearly $T(n) \geq n$. In the other direction, if we have shown that $T(m) \leq 6m$ for $m < n$, then
$$
T(n) \leq 6(n/2 + n/3) + n = 6n.
$$
Therefore as long as the base case holds, and if we ignore the fact that $n/2,n/3$ are not necessarily integers, we can prove inductively that $T(n) \leq 6n$.


Convoy effect in priority scheduling and SJF (Non preemptive)

Cant comment but here is some clarification. Using the preemptive sjf, a process with a smaller burst can remove a process with a bigger burst that is currently occupying the cpu, this eliminates the convoy effect but can create a starvation effect whereby shorter procesess keep cutting off long and old processes. A priority based sheduling is efficient if it keeps in account how long a process has been waiting in the wait-queue and also its cpu-burst, a good example is the HRRN method, where the priority of a process is calculated taking in account the afore mentioned criterias. So if the priority


How to prove NP-hardness of a Hamiltonian Path problem by reducing longest-path problem?

Suppose you have a graph $G$ of order $n$. $G$ has a simple path of length $\geq n - 1$ if and only if $G$ has a hamiltonian path.


Example of existence proof in dependent typing?

$\Sigma$-types in Haskell appear in various places. Because Haskell is not dependently typed, they often reduce to the non-dependent version of $\Sigma$-types, which are just Cartesian products. So whenever you see an ordered pair, or a record, that is a simple case of a $\Sigma$-type.

At the level of a modules there can be dependencies and so we get actual $\Sigma$-types. For instance, a module which defines a type $T$ and then a value $f$ of type $T \to T$ has the kind $\Sigma_{T : \mathrm{Type}} (T \to T)$. (The module should hide the definition of $T$ in order for this to actually be the case.) Observe that this is a "large" dependent sum because it ranges over "all Haskell types $T$" so I refer to it as a "kind". In fact, the theory of modules is based on the observation that hiding bits of a program behind a layer of abstraction is precisely the same as forming a dependent sum.

Haskell has existential types. These are like depenent sums of the kind I mentioned above. Namely, an existential type

data Calf = forall t . Bull t => Cow(t)

is just a confusing way of writing $$\mathtt{Calf} = \textstyle \sum_{t : \mathtt{Bull}} Cow(t).$$ Strangely, the "forall" keywords indicates the fact that there exists a type $t$ of class $\mathtt{Bull}$ such that $F(t)$. Perhaps some Haskellites can explain the logic behind the notation to me.


Your misunderstanding is:

  'sure' in the sense of being computationally verified by an algorithm

We are not, and we can not be . The question,

  Is this given Turing machine $M$ a universal one?

can not be generally and algorithmically decided for the reasons you state.

However, we can prove for a fixed Turing machine that it is universal -- and that is quite enough.


Find maximal difference between two consecutive numbers

Determine the minimum $a$ and maximum $b$ in a first pass.
Create $n+1$ buckets, each of width $\frac{b-a}{n+1}$, with the first beginning at $a$. We have $n+1$ buckets and only $n$ points, so by the pigeonhole principle, there must be at least one empty bucket. Since we know that the first and last buckets contain at least one point, we know furthermore that there must be an empty bucket with a nonempty bucket somewhere to its left and another nonempty bucket somewhere to its right, implying that the solution must be at least $\frac{b-a}{n+1}$.
This means that no two points within the same bucket can provide the solution, since they must be strictly less than $\frac{b-a}{n+1}$ apart from each other. So, any solution will consist of a pair of points from different buckets.
A valid solution must consist of the rightmost point from some bucket $i$ and the leftmost point from some bucket $j > i$ with all buckets in between (which may be no buckets at all, when $j=i+1$) empty. So it is sufficient to know, for each bucket, its leftmost and rightmost points.
To compute these, iterate through all the points again, updating the leftmost and rightmost positions of the current point's bucket whenever necessary. (For the first point in a bucket, both of these positions will need to be updated.) A point's bucket can be computed by subtracting $a$ and dividing by $\frac{b-a}{n+1}$.
Finally, iterate through all the buckets, keeping track of the rightmost point in the last nonempty bucket seen, and comparing it with the leftmost point in the current bucket: Update the maximum whenever this exceeds the current maximum.


It is no wonder that you are confused.

One characteristic of DP problem is the recurrence relation that combines solutions to subproblems to a solution to larger subproblems. That article presents the following general "recurrence relation".

Any DP problem where A[i] = min(A[j:k]) + C where j < k <= i

However, because the same A appears on both sides of the equation, that "recurrence relation" cannot be specialized/instantiated as the recurrence relation of any problem listed in that article.

Instead of "DP problem", this kind of problem should better called "sliding window problem", or "SW problem".  Basically, a first-in-first-out queue sliding over the given array are used to track the useful entries. We could argue that "SW problem" is a special kind of "DP problem", where the overlapping subproblems are to fill those sliding windows.  Each sliding window will lead easily to a solution for the original problem at one end of a window. Or, if you prefer a visual identification  of the "DP problem" as "table-driven bottom-up memoization", an "SW problem" is supposed to be solved by tracking useful data in a table moving across the given array.

An "SW problem" does not have the usual form of recurrence relation,  as can be checked against all problems listed in that article. Instead of Any DP problem where A[i] = min(A[j:k]) + C where j < k <= i, it should have been something like Any problem to find M[i] where M[i] is defined as something like min(A[j:k]) where j < k <= i given array A.

This technique, "sliding window" is indeed very powerful and easy to use. Except the glaring lapses mentioned above, that article is pretty nice. I encourage you to read the full article, ignoring that summary statement or using my replacement above.


What are the difference and relation between type checking and type
  reconstruction?

Type reconstruction is a class of problem that involves coming up with a type for a term. For example given a term $\lambda x. x$ can you find the type for this term. Or in general answering the question:

Does a $T$ exist such that the judgement $\Gamma \vdash M : T$ is derivable, where
$M$ is the term and $\Gamma$ is the type environment.

Type checking on the other hand is a process where the question is:

Given a $T$ and an $M$ can $\Gamma \vdash M : T$ be a valid judgement.

  Does type checking apply only to terms with explicit type annotations which don't contain type variables?

No. You can have a type checking problem that asks whether $\lambda x. x$ has a type $\tau \to \tau$ where $\tau$ is a type variable.

  Does type reconstruction apply only to terms either without explicit type annotations, or with explicit type annotations containing type variables?

As type reconstruction problem is about computing the correct type for a term, if you have an explicit type annotation for a term, you would classify it as a type checking problem.


Check two balanced binary search trees that sub set of each other

When you try to traverse a tree, you start at the root, and you will have to remember all the nodes that you were visiting, to be able to find the next node. If your tree is balanced, then it contains only O (log n) nested notes, so your space requirement for two trees is only O(log n) + O(log m). Unbalanced trees could be nested up to n levels deep, so you could need up to O(n) + O(m) space to traverse both trees.


Which combinatorial problem is similar to this problem?

In a very literal sense, D.W.'s answer is correct. In the absence of any information about the cost function, there are no alternatives better than simply trying the cost function at each possible input.
However, in real-world applications, we usually know something about the cost function—and as soon as we have a little bit of structure, we can leverage that to create more efficient search strategies.
For example, if the cost function has a relatively simple closed form in terms of the inputs, you may be able to apply an optimizing SMT solver such as the widely-used Z3 from Microsoft Research (interactive tutorial here). These solvers use complex strategies to locate and exploit hidden structure in the input problem and find solutions more efficiently than brute-force search.


Is building this tournament fixture an NP-Hard / NP-Complete problem?

At first glance, even a simple solution would appear to merely be ${\cal O}(n^2)$, which is obviously polynomial time. To make the rest of my answer more readable, I'm going to define the following variables:

numEntrants = the total number of entrants
largestNumEntrants = the number of entrants from the country with the most entrants
numRounds = numEntrants - largestNumEntrants

For the purposes of the rest of my answer, I will assume that numEntrants is even. If it is not even, then some odd number of entrants must have a bye each round and that greatly complicates matters when trying to make sure every entrant plays the exact same number of matches.

As you correctly observed in your question statement, the largest possible number of rounds is the total number of entrants minus the number of entrants from the country with the most. We can quickly observe that numRounds is in ${\cal O}$(numEntrants). Furthermore, the number of possible matches within a round is also in $\cal O$(numEntrants). Specifically, it is exactly numEntrants / 2.

My suggested solution would then be as follows:

Arrange the entrants in an ordered list (which I'll call entrantList) in such an order that all of the entrants from a particular country are adjacent to each other.

for (int round = 0; round < numRounds; round++)
{
    for (int i = 0; i < (numEntrants / 2); i++)
    {
         Match entrantList[i] with
             entrantList[(i + largestNumEntrants + round) % numEntrants] for round.
    }
}

This algorithm clearly runs in $\cal O$(numEntrants$^2$) time and, as far as I understand them, satisfies all of your constraints, at least when numEntrants is even. Obviously, ${\cal O}(n^2)$ means that the problem is in P and is definitely not NP-Hard or NP-Complete.

This algorithm ensures that each entrant plays each other entrant a maximum of 1 time because it simply selects the entrant after the one it was previously matched with on each iteration. It ensures that no entrant from the same country plays another entrant from the same country because all entrants from the same country are adjacent to each other in the list and it starts with an offset of largestNumEntrants.


Competitive ratio of the ski rental problem

I think the first approach can give an arbitrarily bad competitive ratio for any algorithm: if we ski $0$ days, the optimal would be to neither buy nor rent (pay $0$), while any algorithm either buys or rents the skis before the first day (pay something $>0$).

So the problems are different, and for the first problem we cannot have a "good" algorithm.


The $\epsilon$-closure of a state $p$ is the set of all states, including $p$ itself, that are reachable by only by a chain of consecutive $\epsilon$-moves. Transitions on other inputs are not considered when computing $\epsilon$-closure$(p)$. They come in to play in the next step, when you compute the transition function for the equivalent NFA without $\epsilon$-moves.


I would split the language in a part that assures that the number of 1s is odd (like, one 1), and another part of the language that maintains that. Similar to induction. So the first step is to write

$$S \rightarrow A1A$$

This makes sure there is at least one $1$ in our grammar, and $A$ is must maintain that. Any number of $0$s or $2$s have no effect, as well as the empty string:

$$A \rightarrow 0A \mid A0$$
$$A \rightarrow 2A \mid A2$$
$$A \rightarrow \lambda$$

However, if $A$ contains a $1$, it must contain at least another one. How can we enforce this? Simple! We re-use $S$, which already enforces this:

$$A \rightarrow 1S\mid S1$$

Note that I made every rule symmetrical regarding order. This is not a good practice in general when writing grammars for actual parsing, as it leads to highly ambiguous grammars. However here the focus is on getting the requirements right, so having not to worry about order at all makes it a bit easier.


When are range-based for loops better than regular for loops?

In my experience, if you don't need an index variable and don't need to iterate over the objects in a particular order, then range-based for loops can be easier to understand, and less verbose. Outside of those conditions, it's usually a matter of taste. You're basically saying, "for each object in the container, do this," as opposed to saying, "for each index in the container, retrieve the object at the index, and for each object you've retrieved, do this."


If i use other peoples code for my final year project does that come under Plagiarism?

You should clearly talk to your supervisor or advisor about this, however there are some general principles you are often overlooked by students when doing their final year projects in computing disciplines.
Firstly you should be clear what plagiarism really is and fully understand it. Plagiarism is presenting someone else's work as your own to gain credit for it as if you had created it yourself. However, we all use the work of others. We read books, we read tutorials on the Internet, we read things on Stack Exchange. We should, if doing this properly be citing the work of others properly so it is clear when ideas, code, formulas and other elements of our work are attributable to others. If we have properly attributed the work, then those who assess you can clearly see which parts are yours and which are not. Then no plagiarism is involved. A good student will be reading much and citing much and will be including the work of others. It is just they cite it well. A weak student may often be someone who has read little, used little, cites nothing and hands in little. A really bad student would just hand in someone else's stuff. Hopefully the boundaries are a little clearer.
The next element, particularly for Computer based projects, is to realise that we are using the work of others and including it in our project all the time. You will be using an operating system, you will be using a language invented by someone else a compiler built by someone else that interacts with run-time libraries that were supplied with it. Yet, despite doing this all the time students worry little about these elements that were included in their submitted project. Where is the dividing line between the bits that are incorporated in your work and what you did? Who can tell? This is why citing everything you used is important.
The only way to really make the whole project fully self-created, you would in extremis have to start with clean sand, make your own processor chips to your own design, write the operating system and compilers for them to your own design and then use that as a platform for your project. But, of course, that is totally preposterous.
As Isaac Newton is credited with saying, we can see so far because we are standing on the shoulders of giants. You should do the same. Select the best components and use your skill and education to assemble them into the best creation that is your project. All good things are just made from components that are acknowledged and this is not plagiarism. The skill is in using the right components assembled in the right way.
How many of those things should be hand-crafted by you and how many are imported is the guidance you get from your project supervisor.


Generating all the increasing subsequences

Here is an algorithm to generate all increasing sequences of length $4$ of the numbers $1,\ldots,n$:
for d in {4,...,n}:
  for c in {3,...,d-1}:
    for b in {2,...,c-1}:
      for a in {1,...,b-1}:
        output a,b,c,d


Complete Problems for $DSPACE(\log(n)^k)$

A standard proof of the space hierarchy theorem is based on the space-efficient simulation of Turing machines.  If I am not mistaken, this simulation implies that for every space-constructible function f: ℕ→ℕ, the following problem is in DSPACE(f(n)) (where n is the input length):

  Given an encoding of a deterministic Turing machine M with a read-only input tape and a read-write work tape with a fixed work alphabet (such as {0, 1, blank}), a string x, and a tally string 1t, decide whether M halts on input string x before using more than f(t) work space.

This problem is DSPACE(f(n))-hard under log-space many-one reducibility.  Here is a proof in the case of f(n) = lgkn.  For each language L∈DSPACE(logkn), there is a Turing machine M (of the form stated above) which accepts L in c lgkn space for some c∈ℕ.  Modify M to M′ so that when M rejects, M′ goes into an infinite loop instead.  Then given an input string x, let t = |x|c, and we generate the instance (M′, x, 1t) of the problem above.  (I think that the only slightly nontrivial part is that we cannot set t = |x|.)

Therefore this problem is DSPACE(f(n))-complete under log-space many-one reducibility.


Great project!  There are many possibilities.  I suggest reviewing the approaches listed in Dealing with intractability: NP-complete problems and trying as  many of them as possible to see which tends to work best on the kinds of graphs you have to handle in your class.  It will be a fun learning experience, where you get to learn about multiple techniques and get some experience with them.

At minimum, I'd recommend trying some form of local search, such as hill climbing and/or simulated annealing. I have rarely seen situations where genetic algorithms outperform other forms of local search.  I'd also recommend trying integer linear programming (ILP) or possibly MaxSAT.


Combinatorial Problem similar in nature to a special version of max weighted matching problem

Maximum Weight Matching algorithms are incremental, so to achieve a maximum weight matching of a bounded size, just stop after so many iterations. To achieve the other constraint, For each terminal vertex in $\mathcal{V}'$, increase the weight of each incident edge by a huge constant amount $U$. Try to prove that this answers your question (note that edges incident to two terminals have to be increased twice to keep the total increase constant in all valid solutions).
Note. It might help in the proof to distinguish different cases according to the size of $\mathcal{V}'$ compared to $k$ (the size of the matching).


Given that f(n)>0 and constant c>0 Prove that f(n)+c = O(f(n)) or provide a counter-example if it's false

This is false. A counterexample is $f(n)=1/n$ and $c=1$.

If $f(n)+c=O(f(n))$, then there exists $n_0>0$ and $d>0$, for any $n>n_0$,  $f(n)+c\le df(n)$, or $1/n+1\le d/n$. But let $n=\max\{n_0+1,d\}$, the inequality fails obviously, a contradiction.

In fact, any $f(n)$ and $c$ such that $f(n)\to 0$ ($n\to\infty$) and $c>0$ are sufficient.


What does Djikstra mean by "formal techniques" in this essay?

It seems quite clear that Dijkstra did mean what is known today as formal methods. He also had the idea that calculations should replace mathematical proof in prose, which you can find in some of the EWDs. It seems that so far his dream hasn't been realized, and while formal methods are used in some extreme circumstances, the average programmer has no use for them.


Here is one way of thinking about it. You are receiving a sequence of zeros and ones. At each moment the sequence might stop and you need to decide to accept or reject the resulting word. At each point in time, think about what properties of the sequence you need to remember to decide whether to accept a word or reject it. The number of these properties is a proxy for the number of states. The properties also suggest descriptive names of states.

For this problem, you need to know if you have seen exactly one zero, at least two zeros, and if you have seen three consecutive zeros. In case you have seen exactly one zero, you need to know if it is the last character (this gives 2 states). In case you have seen at least two zeros you need to remember the last two characters of the string (this gives 4 states, in principle, but in this case two can be combined for a total of 3). You need to remember if you have seen 3 consecutive zeros (1 more state). You also need a start state for a total of 1 (start) + 2 + 3 + 1 = 7 states.

So you can describe a state by a tuple (a,b), where a is 1 if you've seen exactly one zero so far, and 2 if you have seen at least two zeros, and b indicates the last bits you've seen. You can have the following states:

(0,*) - haven't seen any zeros yet, aka start state

(1,0) - have seen one zero and it is the last character of the string

(1,1) - have seen one zero, but it was some time before, it is no longer the last character

(2,00) - have seen at least 2 zeros, and the last two characters are zeros - DANGER - one more zero and I need to reject

(2,10) - have seen at least 2 zeros, and the last two characters are 10 - we are relatively safe, because we need to see 2 zeros before we decide to reject

(2,*1) - have seen at least 2 zeros, and the very last character is 1 - we are quite safe, we'll have to see 3 zeros before we decide to reject.

All the above states are assuming you have not seen three consecutive zeros. Of course, once you decide to reject due to three consecutive zeros, you always reject - this gives one more state.


If a problem is "not semi-decidable" and "not decidable" can we say it is "undecidable"?

Undecidable isn't wrong: "undecidable" means exactly the same thing as "not decidable". However, your TA is saying that you can make the strictly stronger statement that the set is not even semi-decidable.  This implies that it's undecidable, but isn't implied by "it is undecidable".

Suppose you were, instead in a biology class. You wrote "This is not a lizard" and your TA crossed it out and wrote "This is not any kind of reptile." You're both right, but your TA's version has more information in it.


Is dynamic programming restricted to optimization problems?

Dynamic Programming can be used to solve a problem as long as the problem has a recursive substructure and the sub-structural problems are overlapping. So, as long as a problem has the two properties, DP can be used for solving it. Problems with these properties are definitely not restricted to only optimization problems. So, yes.

Here are some good examples of non-optimization problems which can be solved quickly using DP:

Coin Change Problem
Counting the number of increasing subsequences in a given sequence
If you forget everything, calculating upto the first $n$ Fibonacci Numbers using its recurrence relation can be done using Dynamic Programming.


NP-hardness is usually defined using many-to-one reductions, for various reasons, for example to separate NP from coNP (there was some question about it either here or in cstheory). What you're describing is a specific case of more general Turing reductions, which is more common in classical recursion theory, and it is natural since it has the consequences you mention. Unfortunately, the definition of NP-hardness requires a many-to-one reduction.


How do we know any problem is in NP-complete if we don't know all problems in NP?

We do know all problems in NP. Each problem in NP is given by a non-deterministic Turing machine running in polynomial time. Steve Cook (and, independently, Leonid Levin) proved that SAT is NP-complete by encoding the statement "Machine $M$ accepts $x$ given non-deterministic choices $y$" as a logical formula for every non-deterministic Turing machine; for a machine running in time $T$ and space $S$, the encoding has length roughly $O(TS)$, so when $M$ is polynomial time, the encoding has polynomial length. The corresponding SAT formula states that "for some $y$, machine $M$ accepts $x$ given non-deterministic choices $y$". This formula is satisfiable iff $M$ accepts $x$.

Having proven that one problem is NP-complete, there is no need to do this encoding again. To prove that some other problem $L$ is NP-hard, it is enough to reduce SAT to $L$. Every problem in NP is reducible to SAT, and via the auxiliary reduction, to $L$. This is the way NP-hardness results are proved nowadays, by reducing from some NP-hard problem.


Hint: Let's try to encode the constraints using two types of variables: $a_v$ for each vertex $v$, and $b_{uv}$ for each edge $u,v$. The variable $a_v$ encodes which part of the cut vertex $v$ belongs to. The variables $b_{uv}$ equals 1 if the edge $(u,v)$ is cut.

We want to enforce the following constraints:

$a_s = 0$ and $a_t = 1$.
$b_{uv} = 1$ if $a_u = 1$ and $a_v = 0$ or if $a_u = 0$ and $a_v = 1$.
$\sum_{uv \in E} w(u,v) b_{uv} \leq k$.

Try to encode all these constraints as inequality constraints.


Trouble finding loop invariant for this while loop

Unfortunately, you can't prove partial correctness of your algorithm because it is incorrect.

EDIT: The algorithm provided is indeed correct.

Aditionally, you can't prove that an algorithm is "inductive". You can prove its correctness by using loop invariants,which are quite similar to mathematical inductions.

We must show three things about a loop invariant:

Initialization:

Before you start the loop,check if your initialization is correct.

You want to check if there is an even number of positive numbers in your list A. You set up the variable i to equal 0, therefore your loop begins at the first index of your list.

The variable even is set to True. If it were set to false, and you had 0 positive integers, it would return false, which is incorrect.
Therefore, initialization is correct.

You can see initialization as your base case.

Maintenance:

If your invariant holds from iteration to iteration.

The body of your while loop checks if an integer in index i of your array A is positive. If that condition is true, it sets the boolean variable "even" to "not even".

Since it flips the value of even equal to the amount of positive integers in your list,the maintenance is correct.

Termination:

What happens when the loop is over?

The last step increments the variable i by 1. When the loop ends, i < A.length, which is correct.

The algorithm will return either True or False based on the amount of positive integers. Since initialization and maintenance are correct, the algorithm is correct.


Sliding window protocol when number of packets is equivalent to the window size

Definitely, the window boundaries will be updated, in other words, the window will be shifted regardless of the fact remaining packets are strictly less than window size.

But the main point is after shifting,window will not be fully      occupied.The window in sliding window protocol is a buffer, which stores only those packets whose acknowledgement is not received. But because the packet 1's ack is received, it would no longer remain in the window.


Hint: Define $B[i] = A[i] - i$. What can you say about the array $B$? Use the fact that $A$ contains distinct integers.


How to find the number of discrete states possible by current computers?

Acording to the suggestions that were given in the comments to the question, the number of distinct discrete states possible by a machine are related to the size the machine's of memory (or "stores" space, using Turing's nomenclature).

Since a bit has two distinct discrete states, a byte then have $$ 2^{2^3}=2^8 $$ discrete states.

Two bytes, $$2^{2*2^3}=2^{16}$$

Hence, a commercial availabe 4GB DDR3 RAM machine would roughtly be $$ 2^{2^2*2^{30}*2^3} =2^{2^{35}}=2^{34,359,738,368} $$

Further, today's (March 2017) world fastest computer, Sunway TaihuLight, with more than 1 PB memory, would have rougthlty $$ 2^{2^{50}*2^3}=2^{53}=2^{9,007,199,254,740,992}$$ distinct discrete states.

Correct math if wrong, but the idea is this, taking in account only main memory (disregarding cpu registers, secondary memory and cache, as j_random_hacker stated that could be done).


inclusion and concatenation of languages

The assignment tests basic definitions (and some elementary set theory).

As you know, for arbitrary $L_1,L_2$, you have $L_1\cdot L_2 = \{ x\cdot y \mid x\in L_1, y\in L_2\}$.

Now if $L_1\subseteq L_3$ and  $L_2\subseteq L_4$ then $L_1\cdot L_2 \subseteq L_3\cdot L_4$. This is rather clear, or if you want, can shown with elementary steps. Take any $z\in L_1\cdot L_2$, then $z=xy$ for $x\in L_1$ and $y\in L_2$. However, because of the inclusions, $z=xy$ for $x\in L_3$ and $y\in L_4$, thus $z\in L_3 \cdot L_4$.


How is the directory implementation done using a linear list?

A directory is a collection of files, some of which could be directories. You can store the list of files forming a directory as a linear list. This is somewhat similar to the adjacency list representation of a graph (imagine that the graph were a tree).

Each node in the list contains some sort of information regarding the file, such as the name, size and contents. The contents themselves are not stored at the list, but somewhere else in the filesystem. Each node just contains a pointer to the data, which is what is meant by data blocks. The exact way in which this is implemented depends on the file system – the main issue here is that the file isn't stored contiguously.


How to deal with arrays during Hoare-style correctness proofs

Your axiom is not really an axiom, it's missing hypotheses. Simple presentations of Hoare logic manipulate formulas of the form $\{P\} C \{P'\}$ where $P$ and $P'$ are logical formulas and $C$ is a command. You do need to ensure that $C$ is well-formed. In simple languages such as the ones often used for a first introduction to Hoare logic, well-formedness is syntactic: it's typically a matter of checking that $C$ conforms to a context-free grammar, and possibly that the free variables are within a permitted set. If the language includes constructs that have a semantic correctness, such as accesses to array elements, you need to add hypotheses to express this semantic correctness.

Formally, you can add judgements to express the correction of expressions and commands. If expressions have no side effects, they need no postconditions, only preconditions. For example, you can write well-formedness rules such as
$$
\dfrac{\{P\} \;\; E \text{ wf}}
      {\{P \wedge 0 \le E < \mathrm{length}(A)\} \;\; A[E] \text{ wf}}
\qquad
\dfrac{\{P\} \;\; E_1 \text{ wf} \qquad \{P\} \;\; E_2 \text{ wf}}
      {\{P\} \;\; E_1 + E_2 \text{ wf}}
$$
and only allow well-formed expressions in commands:
$$
\dfrac{\{P[x\leftarrow E]\} \;\; E \text{ wf}}
      {\{P[x\leftarrow E]\} \;\; x := E \{P\}}
$$

A different approach is to treat all expressions as well-formed, but to make any expression involving an ill-formed calculation have a special value $\mathbf{error}$. In languages with run-time bounds checking, $\mathbf{error}$ means “this program raised a fatal exception”. You would then keep track of whether a program errored out through a logical predicate $\mathbf{Error}$; a program is only valid if you can prove that its postcondition implies $\neg\mathbf{Error}$.
$$
\dfrac{}
      {\{P[x\leftarrow E]\} \;\; x := E \;\; \{P \vee \mathbf{Error}\}}
\qquad
\dfrac{P[x\leftarrow E] \implies E \not\rightarrow \mathbf{error}}
      {\{P[x\leftarrow E]\} \;\; x := E \;\; \{P\}}
$$

Yet another approach is to consider a Hoare triple to hold only if the program terminates correctly. This is the usualy approach for nonterminating programs: the postcondition holds when the command terminates, which might not always happen. If you treat run-time errors as non-termination, you sweep all correctness issues under the hood. You will still need to prove the correctness of the program somehow, but it need not be in Hoare logic if you prefer some other formalism for that task.

By the way, note that expressing what happens when a compound variable such as an array is modified is more involved that what you wrote. Suppose $P$ was, say, $\mathrm{IsSorted}(A)$: the substitution $A[i]\leftarrow E$ would not change $P$, yet the assignment $A[i] \leftarrow P$ might invalidate $P$. Even if you restrict the syntax of predicates to only talk about atoms, consider the assignment $A[A[0]-1] := A[0]$ under the precondition $A[0] = 2 \wedge A[1] = 3$: you cannot make a simple substitution to obtain the correct postcondition $A[0] = 1 \wedge A[1] = 1$, you need to evaluate $A[0]$ (which can be difficult in general, since the precondition might not specify a single possible value for $A[0]$). You need to perform the substitution on the array itself: $A \leftarrow A[i\leftarrow E]$. Mike Gordon's lecture notes have a good presentation Hoare logic with arrays (but without error checking).


Prove that Language is not Regular using closure(s)

What is your " ' " operator? Could it perhaps be the homomorphism $0\rightarrow a, 1\rightarrow a, 2\rightarrow b$? If not, consider this as a hint, since regular languages are closed under homomorphisms.


Job scheduling with a bottleneck problem

This looks like the so called master-slave scheduling model introduced by Sahni. In particular, your problem falls under the Single-Master Master-Slave Systems. You can distinguish several cases:

1) If you do not add any additional constraint on the order of job execution (as in your case), the problem is called unconstrained minimum finish time problem (UMFT) and has been shown to be NP-hard;

2) Same Pre- and Postprocessing Orders: it is possible to design an $O(n \log n)$ algorithm to construct an order preserving minimum finish time (OPMFT) schedule;

Therefore, in case 1 your problem is $NP$-hard, while it is in $P$ in case 2.

Additional related problems are:

3) Reverse Order Postprocessing: For any given preprocessing permutation, $σ$ , it is possible to construct a reverse-order schedule, referred to as canonical reverse order schedule (CROS). Given a preprocessing permutation $σ$ , the corresponding CROS is unique. It is easy to establish that every minimum finish-time reverse order (ROMFT) schedule is a CROS.

4) no-wait-in-process constraint:

a) [MFTNW] Minimize finish time subject to the no-wait-in-process constraint;
b) [OP-MFTNW] This is the order-preserving version of MFTNW. That is, minimize finish time
subject to the no-wait-in-process and order-preserving constraints;
c) [RO-MFTNW] Minimize finish time subject to the no-wait-in-process and reverse-order
constraints.

Problems $a$ and $b$ are NP-hard, while $c$ admits a polynomial time solution.

Additional details in Handbook of Scheduling, chapter 17.


Does MST exclude the edge belongs to the cycle of the graph?

I think you need to be more precise in your reading of the statement, though it could be better phrased. A different version is "if $e$ is an edge of $G$ and it is not in any cycle in $G$, it must be in any MST of $G$". This doesn't say that edges that are in cycles can't be in the MST, it just says that any edge that isn't in a cycle must be.

To see why this is true, imagine an edge that is not part of a cycle; it has two endpoints, both of which must be part of the MST (otherwise it wouldn't be spanning). So how do we get to those endpoints? If we don't use that edge, we can't reach one of the endpoints (if we could reach both, then the edge would be part of a cycle), thus that edge must be in the MST.


Simplest way to check edge set for transitivity

There's a very simple algorithm for this:

for each edge (u,v) in the graph:
    for each edge (v,w) in the graph:
        if (u,w) is not in the graph, return "Not transitive"
return "Transitive"

Basically, if the graph is not transitive, then you can always find some path of length two $u\to v \to w$ such that the edge $u \to w$ is not present in the graph.  If the graph is transitive, there won't be any such path of length 2.  So, just check this condition.


Show that a function belongs to grade of incline

The term of $O(...)$ means representation of the performance of a solution. It is not entirely clear what you see under the expression n ^ 7. And because it is a representation of the complexity of the algorithm is needed to know how this power will count. There can be several calculation algorithms, each of which will have a different expression of the complexity. If you used the algorithm to multiply numbers, then you can, for example, the multiplication using konvolučního algorithm for the discrete Fourier transform. Performance of such algorithm is the maximum $O(7\cdot n \cdot log\space n)$, where n is the number of components of the vector needed for representation of numbers using the discrete Fourier transform.
Otherwise, if this is just a number, then I can also provide your own custom algorithm that takes advantage of the symmetry of the multiplication, exponentiation, and in case there is no need to perform a transformation for the convolution and there would be performance requirements could be smaller.


How to tell if a minimax search tree is computationally feasible using parallel computing

Plainly, evaluating $10^{19}$ positions is not going to be feasible in 7200 seconds.  But if you use alpha-beta to prune the search tree and have perfect move ordering you can get that down to around $10^{10}$, a number that looks much more reasonable given that chess engines on PC hardware can do a couple million nodes per second easily.  Since alpha-beta is a serial algorithm, you'll have to do more than just naively divide the search tree among processors to reap its benefits, but there has been a great deal of research in this area: start here.


one solution might be Van Emde Boas layout (vEB). It is used in a hierarchical memory to optimize the number of cache misses (since it is a cache-oblivious method).

Here is how we lay a complete binary tree that has $N$ nodes in an array: split the tree in the middle (i.e. at height $h/2$ where $h= \log N + 1$). This breaks the tree into a top subtree $T_0$ of height $\lceil h/2  \rceil$ and several bottom subtrees $T_1,...,T_k$ of height $\lfloor h/2 \rfloor$, each dangling from a leaf of $T_0$.
Now store $T_0$ in the first part of array and the bottom subtrees next to it, in the order from left to right. You need to store each $T_i$ recursively, i.e. beaking into smaller subtrees until the subtrees contains only one node.

http://erikdemaine.org/papers/BRICS2002/paper.pdf


Lambda calculus as the language of universal logic - connectives vs functions in lambda calculus?

You are on your way to discovering the Curry-Howard correspondence.


Exhaustive search algorithm solving vertex cover of size $k$ in time $2^{k}n^{O(1)}$?

The search with the running time of $2^kn^{O(1)}$ is a different one. Personally, I would not have chosen to call it an exhaustive search. Not that it is incorrect, but as the question shows it may be misleading.

The classic algorithm goes as follows:

If all edges are covered, succeed.
If you already have chosen $k$ vertices, fail.
Consider the first uncovered edge.
One of its endpoints must be in the vertex cover. This leads to two possibilities, on which you recurse. In each branch of the recursion, continue at 1.

The recursion has depth $k$ and branches binarily. Thus there are $2^k$ paths in the search tree. Each step can be processed in polynomial time.

[EDIT]

Success in Step 1 means that the current candidate set is indeed a vertex cover, so the algorithm may accept.

Failure in Step 2 means that the current candidate set cannot be extended to a vertex cover of size $k$, so the search must continue in another branch.

Also, thanks to chi for pointing out an ambiguity.


Turing machine that accepts L = {#a != #b}

You dont need to keep track of them. At each iteration you have three possibilities. Either you first see an A, or a B or a nothing. If nothing accept. If an A first, replace it with some special character and search for a B. If you see one replace that one as well with some special character go back to beginning but if you dont just reject. Do the same for B first. After you cross our 2 characters loop back to beginning. It is actually very similar to $a^nb^n$.

The TM design should be straightforward actually. Similar to $a^nb^n$ but considers $b$ first option as well at each iteration.


First, some remarks. Using only the core typed lambda calculus it's not possible to obtain 'a -> 'b because the typing system is in correspondence (via the Curry Howard isomorphism) to intuitionistic logics, and the corresponding formula A → B is not a tautology.

Other extensions such as tuples and matchings/conditionals still preserve some logic consistency adding product types * which correspond to the logical connective and, and sum types | which correspond to the or. Again, don't expect them to produce that 'a -> 'b type, as it would allow one to prove some formula which is not a tautology.

So your only chances are using other constructions which escape from the logics like raise (but you're not allowed to in this case)… or let rec! Recursion allows to build programs which never terminate, and their results can be given an arbitrary return type as they will never be produced. Now if you think about the most trivial non terminating function (the one which directly calls itself to return a result):

let rec f x = f x

You'll notice that its type is exactly 'a -> 'b: whatever is the provided argument, the result (which will never be computed) can be assumed to have any type.

Of course this f is not an interesting function, but that's the point. In OCaml, any function whose type does not look like a valid formula is a suspicious function.


Why is the consensus number for test-and-set, 2?

Just to make sure we are on the same page, first let us consider these three definitions:

Definition. Test-and-set is a read-modify-write instruction on some binary register (let's just say that 0 and 1 are possible values) where a thread obtains the old value and writes 1.

Definition. Consensus is reached between $n$ threads iff all $n$ threads decide on the same value (the consistency requirement) and all threads decide on a value that was actually proposed by one of the threads (the validity requirement).

Defintion. A consensus protocol is wait-free iff every method call finishes in a finite number of steps.

Now follow two proof sketches.

Claim 1. The consensus number of test-and-set is at least 2. Proof. Suppose that we have two threads 0 and 1 that need to reach consensus. We could do this by letting each thread follow the consensus protocol below:

Write your proposed value to $A[t]$, where $t$ is the thread id and $A$ is an array of size 2.
Perform the test-and-set instruction on some register $R$, with $R$ initialised to 0.
If the return value is 0, you were first: return $A[t]$. Otherwise, you were second: return $A[|t-1|]$.

You can verify yourself that consensus and wait-freeness are satisfied. $\square$

(For the next proof, I will nest some proofs and definitions because I think it will make it easier to follow.)

Claim 2. The consensus number of test-and-set is at most 2. Proof. By contradiction. Suppose we have three threads $A$, $B$ and $C$ that wish to decide on values $a$, $b$ and $c$, respectively, and that we have some valid wait-free consensus protocol that is implemented using test-and-set (and atomic reads and writes).

We can visualise the consensus process as a directed tree, where:

The root is the state where none of the threads have 'made a move';
The left child of a node represents the state that results after a move by $A$, the middle child represents the state that results after a move by $B$, and the right child represents the state that results after a move by $C$;
A leaf node represents a state in which all threads have finished. Associated with a leaf node is a value $a$, $b$, or $c$, where the value depends on which value was decided on for that particular execution.

Definition. Let a state be multivalent if the outcome of the consensus process is not yet determined. In other words, not all possible interleavings of the remaining moves lead to the same result. Let a state be univalent when the outcome of the consensus process is determined.

The root is multivalent. Proof. If only one thread $X$ is active and the other threads lie dormant forever, then $X$ will finish in a finite number of steps (guaranteed by the wait-freeness assumption) and it will decide $x$ (for it has only access to this value and its decision will satisfy the consensus validity requirement). So for our situation, $a$, $b$ and $c$ are all possible outcomes. $\square$

Definition. Let a critical state be a state which is multivalent, with the additional property that a move by $A$ will determine $a$, and a move by $B$ will determine $b$.

There exists a critical state. Proof. From above we know that we start in a multivalent state. Let $C$ make no move at all. As long as either $A$ or $B$ does not force the tree into a univalent state, let it make a move. Wait-freeness guarantees that the tree is finite, so at some point a critical state must be encountered. $\square$

Now consider a scenario where we are in a critical state. There are at least two possibilities:

1) $A$ makes its move (thereby determining $a$) and halts. $B$ then makes its move and halts. Next $C$ runs until it finishes, eventually deciding $a$.

2) $B$ makes its move (thereby determining $b$) and halts. Next $C$ runs until it finishes, eventually deciding $b$. $A$ does not make a move.

Since atomic reads and writes have consensus number 1, $A$ and $B$'s moves had to be test-and-set instructions on the same register (if the registers are different, then $C$ would not be able to tell the order in which $A$ and $B$'s moves happened). From $C$'s perspective, then, scenarios 1 and 2 are indistinguishable, so we must have that $C$ decides both $a$ and $b$. This is impossible. $\square$

That the test-and-set instruction has consensus number 2 follows from both Claims 1 and 2.


Computing number of block reads given relational algebra statement

select * from R1 Where B=1

You don't have any index on a search field (B), hence you have to do a full table scan. It means that you fetch all relation's blocks one by one and take the records which satisfy the condition B=1. (Cost - 200000/200 = 200 blocks)

select * from R2 Where C=1

There is not enough information - you have to know(at least approximately) how many records in R2 satisfy the condition C=1.
For example in case that all the records in R2 have C=1 you'll do the full table scan like above (cost - 45000/4500 = 10 blocks)
On the other hand if you have only one record with C=1 you'll read 3 blocks of index and another one from disk(cost 3 + 1 = 4 blocks)


Not all non-regular languages fail the test of the pumping lemma. Wikipedia has an annoyingly complex example of a non-regular language which can be pumped. So even if a language is non-regular, we may not be able to prove this fact using the pumping lemma.

But it turns out we can use the pumping lemma to prove your first language is not regular. I'm not sure about the second.

Claim: $L_1$ is non-regular.

Proof: By the pumping lemma. Let $p$ be the pumping length. (I'm going to use the alphabet $\{a,b\}$ rather than $\{0,1\}$.) If $p = 1$, then take the string $abbaa$, which is in $L_1$ and pump it to $aabbaa$ which is not in $L_1$, so $L_1$ would not be regular.

If $p > 1$, then take the string $a^pbba^{N}$. (We'll figure out what we want $N$ to be later.) Then consider any division of the string into $xyz$ where $x=a^{p-k}$, $y=a^k$, and $z=bba^{N}$.

Now let's pump this string $i$ times. (We'll figure out what we want $i$ to be later.) We get the string $xy^iz$, which gives $a^{p-k}a^{ik}bba^{N} = a^{p-k+ik}bba^{N}$.

Now let's back up. First, we picked $N$. Then, some choice of $k$ was made. Then, we picked $i$. We want to figure out what $N$ to pick so that, for any choice of $k \in [1,p]$, we can choose an $i$ that makes this string a palindrome by making the number of $a$s on the left equal the number on the right. (It will always have even length.)

So we want to always get that $p-k+ik=N$. If we play around with the math, we find that we should pick $N=p+p!$ and pick $i=p!/k+1$.

So to recap, we picked $N=p+p!$ and chose the string $a^pbba^N$. Then some choice of $k$ was made so that the string was made up of $a^{p-k}ybba^N$ where $y=a^k$. Then we picked $i=p!/k + 1$. We pumped the string to get $a^{p-k}y^{i}bba^N = a^{p-k}a^{ik}bba^N = a^{p-k+ik}bba^N$.

But we know that $p-k+ik = p-k+(\frac{p!}{k}+1)k = p-k+p!+k=p+p!$. And $N=p+p!$. So the number of $a$s on both ends is the same, so the string is an even-length palindrome, so it's not in $L_1$, so $L_1$ is not regular.  $\square$


Coding for data compression with large target's symbol set (where the target symbol set is larger than the source symbol set)

Both arithmetic coding and asymmetric numeral systems can be done in arbitrary base $b$.

  Is it a right assumption that when the target symbol size is larger, the goal is to find a map from a subset of source symbols to one target symbol?

The above algorithms do not work by finding a 'mapping' from source to target symbols. Such a mapping doesn't deal well with fractional 'bits' - where an event has a probability that does not fit nicely in the output size.

Instead these algorithms work conceptually by dumping buckets of entropy from source symbols into a single uniform pool of entropy (in arithmetic coding this is a single fractional number, in asymmetric numberal systems this is a single large number), while scooping out entropy on the other side with output symbols. The trick is that the 'bucket size' of source symbols and output symbols do not have to have the same size at all.


When do we need to change the state of a push down automata?

As Renato suggests, you never need to change state in a PDA. Even without useing a CFG as an intermediate, we can take a PDA and construct another that does the same job with using only a single state (a proof can be found here). The basic trick is to use the tape alphabet to encode the state of the original machine (and part of the transition). This works perfectly well for both deterministic and non-deterministic PDAs.

This is a little unsatisfying however, as a single state machine with a huge tape alphabet is not a particularly natural way to design a PDA (at least if you're like most humans I have met, there might be someone who thinks that way, if so, well done[!|?]). One intuitive reason to change state is as you suggest, because the machine is meant to be doing something different. Analogously to how we would talk about what we as humans are doing, for example, when we're working. We might break a task into steps, and perform them in a "sensible" sequence. The idea is the same with designing PDAs, break the recognition task into a series of steps, and change state when you move from one step to another.

As an example, consider the canonical non-regular context free language $\{a^{n}b^{n}\mid n\in\mathbb{N}\}$. In processing this language, we might have a starting state, a state for processing $a$s, a state for processing $b$s and an accept state. We move from the start state to the "$a$" state by pushing a botoom-of-the-stack symbol, then process the $a$s (probably by pushing a symbol for each $a$), then move to the "$b$" state using a $\varepsilon$-transistion, process the $b$s (popping off the symbols we put on for the $a$s), then move to the accept state if we have reached the end of the input and can see the bottom-of-the-stack symbol.

This is not the only way to build a PDA for this language, but the changing of states has a natural, intuitive meaning that is useful to us as humans in the design process (and for others trying to understand or implement it).

Unfortunately there's no simple "this is when to change states" rule. As the single state example shows, you can design things in a very arcane, incomprehensible manner, but they are still correct. Like a number of things in maths, CS and programming, you really have to just practice it a bit, look at other solutions and develop your own intuition. It is in many ways like programming (funnily enough) - there's lots of ways to solve a problem, only some are good ways, but there is at best only general guidelines to what to do when and where.


Advantage of the Monte Carlo method over a regular periodic sampling

If you use a fixed seed then Monte Carlo is also repeatable. Monte Carlo sampling has the advantage that the expected number of points inside your figure is proportional to the area, which is not necessarily the case for a grid — you can come up with a contrived figure in which the grid is off by a lot, whereas random points are impossible to "fool" this way.


Rice's theorem application on a language that resembles ETM

First of all, note that there are undecidable languages where Rice's theorem cannot be applied. In your third paragraph one may suggest that it would work that way. But in fact, for $E_{TM}$ you can apply the theorem.

$X$ is not the same language as $E_{TM}$ but it is a proper subset of $E_{TM}$. E.g. the TM $M_0$ that prints $0$ (reject) immediately after the start for any input and halts after that is in $E_{TM}$ but not in $X$. However, Rice's theorem is applicable for $X$. You have to find a proper, non-empty subset of all computable functions $\mathcal{R}$ that contains precisely the function computed by the TM in $X$. Let $$\mathcal{S} = \{f_M \mid f_M(x) = \bot \text{ for all } x \in \{0, 1\}^\ast\},$$ where $\bot$ means "never halt". Then

$\mathcal{S} \neq \varnothing$ as the function of the Turing machine that immediately goes in an infinite loop is in $\mathcal{S}$,
$\mathcal{S} \neq \mathcal{R}$ as $M_0$'s function (see above) is not in $\mathcal{S}$.

Obviously, the set of all Turing machines that compute a function from $\mathcal{S}$ coincide with $X$. Thus, $X$ is undecidable following Rice's theorem.

Note that Rice's theorem can be stated in different ways but it should look like this when speaking about TMs.


Why should one not use a 2^p size hash table when using the division method as a hash function?

Refresh your knowledge of binary! The $p$ lowest-order bits of $k$ are the last $p$ bits when $k$ is written out in binary (i.e., the $p$ rightmost bits). For example, if $p=3$ and $k=17$ then $k$ is $10001$ in binary and the three lowest-order bits are $001$.

The point is that, in general, computing $k \bmod m$ is a relatively expensive operation.  However, if $m=2^p$ is a power of two, the remainder operation is to just look at the $p$ lowest-order bits. That can be done in a single instruction, by taking the bitwise AND with $2^p-1$.

If it's easier, consider the decimal case. If I ask you what is $8237643\bmod 1034$, your response will be to reach for your calculator; if I ask you what is $8237643\bmod 1000$, you'll tell me that it's $643$ with barely a thought.  This is because $1000=10^3$ is a power of ten, whereas $1034$ is not.  (There's no immediate equivalent of the bitwise AND trick for decimal.)


how to understand time complexity from a plot?

No, you can't prove asymptotic properties from finite samples. See here and here for more on this.

Plots can give you hints towards the real properties of the running-time function, though, which you can then go ahead and try to prove.


Understanding the P2||CMax scheduling problem

Taking apart the notation, here is what we have:

Two identical machines.
$n$ jobs with equal duration $p$.
No release dates or deadlines, i.e. $r_i = 0$ and $d_i = \infty$ for all $i$.
No extra features.
Objective function is maximum completion time.

It is true that all schedules without idle time have the same completion time in this setting. However, it still takes linear time to actually write down a schedule.

I guess this an easy exercise that is supposed to get you accustomed to notation and working in the model, and will maybe be extended to more complicated $\beta$.

Also, algorithms for this problem may be used as a subroutine, for instance for computing lower bounds in branch-and-bound algorithms for $P_2 \mid \beta \mid C_\max$ problems with non-trivial $\beta$.

Note: The number of processors can make the (conjectured) difference between polynomial and NP-complete complexity.


Can you solve 2-sat problem when truth assignments of some variables are determined

First set all literals $x$ to $1$ if they appear in a clause $0 \vee x$, and set $\bar x$ to $0$. If that requires you to set some $x$ to both $0$ and $1$, it's unsatisfiable. Iterate this until you don't have to set any more literals to $0$. If you get this far without finding out that the formula is unsatisfiable, remove all clauses that contain a $1$. Now you either have no clauses left - then it's satisfiable - or some 2-CNF formula to which you can apply Krom's algorithm.

Alternatively, remove all clauses $1 \vee x$ and replace all clauses $0 \vee x$ by $(y \vee x) \wedge (\bar y \vee x)$ for a newly introduced variable $y$. You can directly apply Krom's algorithm (or more likely, a linear-time algorithm like that of Aspvall, Plass, Tarjan) to the formula you get this way.


Why can't fibers utilize multiple processors?

The main distinction, as you point out in your question, is whether or not the scheduler will ever preempt a thread.  The way a programmer thinks about sharing data structures or about synchronizing between "threads" is very different in preemptive and cooperative systems.

In a cooperative system (which goes by many names, cooperative multi-tasking, nonpreemptive multi-tasking, user-level threads, green threads, and fibers are five common ones currently) the programmer is guaranteed that their code will run atomically as long as they don't make any system calls or call yield().  This makes it particularly easy to deal with data structures shared between multiple fibers.  Unless you need to make a system call as part of a critical section, critical sections don't need to be marked (with mutex lock and unlock calls, for example).  So in code like:

x = x + y
y = 2 * x

the programmer needn't worry that some other fiber could be working with the x and y variables at the same time.  x and y will be updated together atomically from the perspective of all the other fibers.  Similarly, all the fibers could share some more complicated structure, like a tree and a call like tree.insert(key, value) would not need to be protected by any mutex or critical section.

In contrast, in a preemptive multithreading system, as with truly parallel/multicore threads, every possible interleaving of instructions between threads is possible unless there are explicit critical sections.  An interrupt and preemption could become between any two instructions.  In the above example:

 thread 0                thread 1
                         < thread 1 could read or modify x or y at this point
 read x
                         < thread 1 could read or modify x or y at this point
 read y
                         < thread 1 could read or modify x or y at this point
 add x and y
                         < thread 1 could read or modify x or y at this point
 write the result back into x
                         < thread 1 could read or modify x or y at this point
 read x
                         < thread 1 could read or modify x or y at this point
 multiply by 2
                         < thread 1 could read or modify x or y at this point
 write the result back into y
                         < thread 1 could read or modify x or y at this point

So to be correct on a preemptive system, or on a system with truly parallel threads, you need to surround every critical section with some kind of synchronization, like a mutex lock at the beginning and a mutex unlock at the end.

Fibers are thus more similar to asynchronous i/o libraries than they are to preemptive threads or truly parallel threads.  The fiber scheduler is invoked and can switch fibers during long latency i/o operations.  This can give the benefit of multiple simultaneous i/o operations without requiring synchronization operations around critical sections.  Thus using fibers can, perhaps, have less programming complexity than preemptive or truly parallel threads, but the lack of synchronization around critical sections would lead to disastrous results if you tried to run the fibers truly simultaneously or preemptively.


I think your reasoning is in principle correct. Perfect hashing is an alternative to Bloom filters. However, classical dynamic perfect hashing is rather a theoretical result than a practical solution. Cuckoo hashing is probably the more "reasonable" alternative.

Note that both dynamic perfect hashing and standard cuckoo hashing performance is only expected amortized (you might need to rebuild the data structure completely from time to time). Also Bloom filter are easier to implement. This might be arguments for using a Bloom filter, especially if you can live with false positives.


Why does induction with big-O lead to paradoxes?

You have to carry around the big-O constant. Suppose that we are trying to prove that $T(n) \leq Cn$. In the inductive step, we have
$$ T(n) \leq 3C\lfloor n/3 \rfloor + 2n \leq (C+2)n. $$
So we are not able to maintain the constant $C$. Let's have another go, with $T(n) \leq C_nn$. The argument above shows that we can put $C_n = C_{\lfloor n/3 \rfloor} + 2$, and so $C_n = O(\log n)$ works, and we get the correct asymptotics $O(n\log n)$. (To know that this is tight, we would also need a lower bound, proved in much the same way, with some minor technicalities stemming from the floor.)


Find both lower and upper asymptotic bounds for $T(n) = 2T(\frac{n}{2})+n^4$

It seems that you have overlooked the fact that $f(n) \in \Theta(n^4)$ already implies both an upper bound of $f(n)\in O(n^4)$ and a lower bound of $f(n)\in \Omega(n^4)$. Intuitively, $\Theta$- notation says that a function grows "as fast as" another function, which means both "at most as fast" and "at least as fast".


$\log(n)-k$ is const $\implies$ $2^{\log(n)-k}$ is const $\implies O(2^{k} \cdot \log(n)) = O(2^{\log(n)-k} \cdot 2^{k} \cdot \log(n)) = O(2^{\log(n)} \cdot \log(n)) = O(n \cdot \log(n))$


Calculating product of totient functions

Let $p=500009$ and $m=12p+1$. One possibility is to use the fact that $\phi(m) \equiv 0 \pmod{p}$, and hence it's enough to pre-calculate all values up to $m$. Storing each answer in a 32-bit integer, this is a table of size 24MB.

If you don't like pre-calculating everything, you can use in some other way the fact that only numbers below $m$ need to be considered. Be creative.


Fundamentally, a logic consists of two things.

Syntax is a set of rules that determine what is and is not a formula.
Semantics is a set of rules that determine what formulae are "true" and what are "false". To a model theorist, this is expressed by relating formulas to the mathematical structures that they're true in; to a proof theorist, truth corresponds to provability from a chosen set of axioms with a chosen set of proof rules (techniques).

The difference between different logics is, most simply, in the choice of syntax and semantics. Most logics are extensions of propositional logic or first-order logic. In a sense, you can see these extensions as "adding more features" to the logic. For example, temporal logics deal with truths that can vary over time.

In general, these features could be expressed in a simpler logic, at the cost of having to write longer formulas. For example, the temporal concept "$\varphi$ is true from this point for eternity" can be expressed in a first-order way by adding a time parameter to all your propositions and saying "For all times $t$, if $t$ is greater than or equal to the current time, then $\varphi$ is true at time $t$."  In a sense, you can think of these logics as adding libraries to a basic programming language so you can say things more easily.

Since pretty much all logics are based on propositional and first-order logic, I'd recommend learning about those first.


How is Memory Segmentation done in 8086?

The four segments you mentioned are not static - these are in fact registers that can point to any 64kb zone in the 1MB memory. By changing the value of these registers we can point to other fragments of the memory.

The exact computation of the effective address is performed using 2 registers: a segment register (CS,DS,SS,ES) and an offset register (usually BX, SI, DI, BP). Each one of those registers is 16bit.
To get the 20bit effective address,
the CPU performs
EA = SEGMENT_REG * 10h + OFFSET_REG (mod 20bits).
It is easy to see that by changing the SEGMENT_REG/OFFSET_REG (0000h-FFFFh), the above equation allows one to span the entire 1MB memory address space  (00000h-FFFFFh).


Turning my comment into an answer for the question in the title, the Immerman-Szelepcsényi Theorem says that NL = coNL.  This means it's enough to show that FPATH is in coNL.  For that, observe that the path $a_1,a_2,\ldots, a_n$ is not in $G$ if and only if some edge $a_ia_{i+1}$ is not present.  Since you just need to guess $i$, that's all you need to write down.


The arrow is going from $A$ to $B$. It means you are solving problem $A$ using problem $B$. So, it is a reduction from $A$ to $B$


This depends entirely on convention; with respect to a (proper) formal definition, the expression is invalid as it not properly parenthesised. I'd say that typically, the order is (from stronger to weaker binding)

Kleene Star/Plus (also finite versions),
concatenation,
alternative.

Note that this corresponds (visually) to exponentiation over multiplication over addition in basic arithmetics, so it's probably the natural way.

That is,

$10^*1$ is read as $1(0)^*1$ and
$10|01|11$ as $(10)|(01)|(11)$.

Note that I still drop parentheses due to associativity of concatenation and alternative.


Given an array of integers and a value k, find the length of the longest subarray with max-gap no more than k

Basic idea:
Use 2 pointers to traverse the array: start and end. Both start at the beginning of the array. Try moving end one position at a time and track the maximum subarray length, until the gap is too large. When that happens, move start towards end until you have smaller gap or you meet with the end pointer (the subarray becomes empty).

How to evaluate the gap: by definition max - min of current subarray. So we keep track of min and max.

Have a min deque where you keep elements in ascending order, so that the head of the queue will be the current minimum.
When encountering a new element: remove all elements larger than it from the back of the queue, then add the new element to the back of the queue. This guarantees ascending ordering.

Have a max deque where you keep elements in descending order, so that the head of the queue will be the current maximum.
When encountering a new element: remove all elements smaller than it from the back of the queue, then add the new element to back of the the queue. This guarantees descending ordering.

NB: You don't keep the elements themselves in the min and max queues; instead, keep their indices in the original array! This way you have both position and value, which is important for the following step.

When the gap becomes too large: obviously you cannot increase end before first bringing start closer to it. So increate start by one. Now check the head of both queues: they are the indices of current min and current max. If any (or both) these indices are now lower than start, then they don't belong to the current subarray anymore. Drop them, the head of the queue will be the new min/max.

Continue until end reaches the end of the array.

This gives you linear complexity: each element is processed once, and added and removed at most once from each queue.

Java implementation:

public int find(int[] numbers, int maxGap) {
    int best = 0;
    int bestStart = 0, bestEnd = 0;

    Deque<Integer> minQueue = new LinkedList<>();
    Deque<Integer> maxQueue = new LinkedList<>();

    int start = 0, end = 0;

    while (end < numbers.length) {
        int x = numbers[end];

        // add end to the minQueue keeping increasing order
        while (!minQueue.isEmpty() && numbers[minQueue.peekLast()] >= x) {
            minQueue.removeLast();
        }
        minQueue.addLast(end);

        // add end to the maxQueue keeping decreasing order
        while (!maxQueue.isEmpty() && numbers[maxQueue.peekLast()] <= x) {
            maxQueue.removeLast();
        }
        maxQueue.addLast(end);

        // minimum is at the front of minQueue
        int minIdx = minQueue.peekFirst();
        int minVal = numbers[minIdx];

        // maximum is at the front of maxQueue
        int maxIdx = maxQueue.peekFirst();
        int maxVal = numbers[maxIdx];

        // check
        if (maxVal - minVal > maxGap) {
            start++;
            if (start > minQueue.peekFirst()) {
                minQueue.removeFirst();
            }
            if (start > maxQueue.peekFirst()) {
                maxQueue.removeFirst();
            }
        } else {

            // track progress
            if (end - start + 1 > best) {
                best = end - start + 1;
                bestStart = start;
                bestEnd = end;
            }

            end++;
        }
    }

    // debug
    for (int i = bestStart; i <= bestEnd; i++) {
        System.out.print(numbers[i] + " ");
    }
    System.out.println();

    return best;
}


How to use c-gap problems to prove inapproximability?

One way to show that there is no polynomial time approximation algorithm with ratio $c$ for a certain problem X (assuming P≠NP) is to give a reduction $f$ from an NP-hard problem Y to X such that:

If $x$ is a Yes instance then the optimal value for X is at least $\beta(x)$, where $\beta(x)$ can be computed from $x$ in polynomial time.
If $x$ is a No instance then the optimal value for $X$ is less than $c\beta(x)$ (for the same $\beta(x)$).

Any approximation algorithm for X whose approximation ratio is $c$ can be used to solve Y via the reduction $f$. Therefore, there cannot be any such efficient approximation algorithm unless P=NP.

I'll let you figure out the proof of these two statements.


If in all satisfying assignments all pair of variables can take all possible values is this tautology?

The VC dimension of a set $S \in \{0,1\}^n$ is the maximal $d$ such that for all $i_1 < \cdots < i_d \in \{1,\ldots,n\}$ and all $b_1,\ldots,b_d \in \{0,1\}$, there is a point $x \in S$ such that $x_{i_1} = b_1,\ldots,x_{i_d} = b_d$. Your condition states that the VC dimension of the set of satisfying assignment of a formula is at least $2$. The formula is a tautology if the VC dimension is $n$. There are sets of arbitrary VC dimension, so even if you replace pairs by larger tuples, your conclusion would still be wrong.


You need to get an algorithm polynomial in $n$ where $n = \log N$ is the size of your input, i.e. the binary representation of $N$ (naive factorization algorithms are $O(N^2)$ which is of course exponential).

Given dec(k, x) solving the decision factoring problem, let's write a procedure to find the smallest prime divisor of $x$ using a dichotomy to keep logarithmic the number of steps.

sp(x):
  min = 2
  max = x - 1
  while (max >= 1 + min):
    k = floor ((min + max) / 2)
    if dec(k, x):
      max = k
    else:
      min = k + 1
  if x % (min + 1) == 0:
    return (min + 1)
  else if x % min == 0:
    return min
  else:
    return 1

The procedure above calls dec $O(\log x)$ times and find the smallest prime number that divides $x$, or 1 if it does not exist. Now we can easily define the following factoring function:

factor(x):
  p = sp(x)
  if (p == 1):
    print x
  else:
    print p
    factor(x / p)

Factor is called less than $\log x$ times (since $p ≥ 2$) so the number of calls to dec is bounded by $\log^2 x$ times on values less than $x$. If the complexity of dec is polynomial, let's say bounded by an increasing $P(n)$, then the complexity of factor is still polynomial, bounded by $n^2P(n)$.


Your grammars for $A_1$ and $A_2$ seem correct. Since you want to compute the concatenation of $A_1$ and $A_2$, you just need to express this fact with the start symbols of $A_1$ and $A_2$.
$S \rightarrow S_1S_2$ is a way to do it.
You can check by computing the derivation that creates the word $001110$.