If there is an polynomial time approximation to an NP-complete problem, is P approximately NP?

No, it doesn't prove that P = NP.

This has nothing to do with approximations; it has to do with average-case hardness vs worst-case hardness.  The two results are showing that solving the problem for a randomly chosen hypergraph is usually easy; but there exist hypergraphs where the problem is hard.  Presumably, choosing a hypergraph at random is very unlikely to give you one that's hard, but they do exist.

NP-completeness is about worst-case hardness: even if a problem is easy on average, it can still be NP-complete.

I have no idea what "P is approximately NP" would mean in any precise sense.


Proving correctness and optimality of a greedy algorithm

Notation.
Given a binary tree $T$ and vertex $v$ of $T$, let $\ell_v$ and $r_v$ be the left and right children of vertex $v$ in $T$, respectively. Let $T_v$ be subtree of $T$ rooted at $v$.
Let $d_T(v)$ be the weighted distance between the root of $T$ and $v$ and $h(T) = \max_{v \in T} d_T(v)$.
If $(u,v)$ is an edge of $T$, let $w_T(u,v)$ be its weight.
With a slight abuse of notation, define $w(T) = \sum_{(u,v) \in T} w(u,v)$.
Finally, we define the skew of $v$ as $s_T(v) = w_T(v, \ell_v) + h(T_{\ell_v}) - w_T(v, r_v) - h(T_{r_v})$ if $v$ is an interval vertex of $T$ and $s_T(v)=0$ if $v$ is a leaf of $T$.

  1) The resulting tree upon termination of this algorithm is a zero-skew tree (the length from the root to any leaf is the same).

We will show by induction on $i=0,1,\dots$ that, for all trees $T$ with $2^{i+1} - 1$ vertices, the algorithm returns a tree in which all vertices have skew $0$.

The base case $i=0$ is trivially true since $T$ must have exactly one vertex and the algorithm does nothing.

Suppose now that $i>0$ and let $v$ be the root of $T$.
The trees $T_{\ell_v}$ and $T_{r_v}$ have exactly $\frac{(2^{i+1} - 1) - 1}{2} = 2^i - 1$ vertices and, by inductive hypothesis, the recursive calls on $T_{\ell_v}$ and $T_{r_v}$ ensure that all vertices, except possibly $v$, have skew $0$. The reweighing of $(v, \ell_v)$ and $(v, r_v)$ only affects the skew of $v$ and ensures that $s(v)=0$.

  The sum of the edge lengths is minimized with this algorithm.

Let $T'$ be the tree returned by the algorithm. Suppose that an optimal zero-skew tree $T^*$ obtained from the input tree $T$ by lengthening edges is such that $w(T^*) < w(T')$.

Let $(u,v)$ be an edge of $T$ (where $u$ is the parent of $v$) such that
$w_{T^*}(u,v) < w_{T'}(u,v)$ and the depth of $u$ is maximized.

Since  $s_{T^*}(u)=0$ and since $h(T_v^*) \ge h(T_v) = h(T'_v)$,
the sum of the weights in $T^*$ on each path from $v$ to a leaf in $T_v$
must have increased by at least $w_{T'}(u,v) - w_{T^*}(u,v)$.
Consider the subgraph of $T^*_v$ induced by the edges whose weight has not been increased w.r.t. $T$ and let $C$ be the connected component containing $v$.
Let $E$ be the set of edges with one endpoint in $C$ and the other in $T^*_v \setminus C$. Let $\Delta = \min_{(x,y) \in E} \{ w_{T^*}(x,y) - w_T(x,y) \}$.

Consider a new tree $T''$ that is obtained from $T'$ by reducing the weight of all edges in $E$ by $\Delta$ and increasing the weight of $(u,v)$ by $\Delta$.
The tree $T''$ is a feasible solution to your problem and weighs $w(T^*) - |E| \Delta + \Delta < w(T^*)$ (since $|E|\ge 2$). This is a contradiction.


You say

$\langle M \rangle$ should accept all the inputs, and if one of the inputs rejected it's not $L(M)=\Sigma^∗$.

The above two statements are true, but you are not handling all behaviors of $M$.
In particular you are not considering that $M$ could never halt on some input $x$. In that case $L(M) \neq \Sigma^*$.
In short, your observation do not imply the existence of a Turing machine that accepts on input $M$ whenever $L(M) \neq \Sigma^*$, which would show $\overline{L_{\Sigma^*}} \in \mathsf{RE}$.
In fact, you can formally prove that $\overline{L_{\Sigma^*}} \not\in \mathsf{RE}$ by reducing from the halting problem:
for any Turing machine $T$ you can construct another machine $M_T$ that simulates $T$ and then accepts.
If $\overline{L_{\Sigma^*}}$ were in RE, then there would be a Turing machine $T^*$ that accepts iff $M_T \in \overline{L_{\Sigma^*}}$, i.e., iff $T$ does not halt.
Interleaving the execution of $T^*$ with that of $T$ itself allows  you to solve the halting problem.


Let's start with some definitions:

A literal is either a variable (a positive literal) or the negation of a variable (a negative literal).
A clause is a formula which is equivalent to a disjunction of literals.
A Horn clause is a formula which is equivalent to a disjunction of literals, at most one of which is positive.

Your formula $(P \to Q) \to W$ is not equivalent to a disjunction of literals. Indeed, if it were, since it depends on all variables $P,Q,W$, it would have exactly one falsifying assignment (with respect to $P,Q,W$). Yet it has three: $(P,Q,W)=(F,F,F),(F,T,F),(T,T,F)$. So it is not a clause, and in particular not a Horn clause.


The answer goes something like this

S->ε/ aSb

S->A

A->ε/ aAa / bAb

here is a sample string for the above with proof

aabaabbb

S=>aSb

S=>aaSbb

S=>aaAbb

S=>aabAbbb

S=>aabaAabbb

S=>aabaεabbb

S=>aabaabbb

here above symbol ε is epsilon


Hex Bit Pattern to IEEE 754 standard Floating Point Number

A good start is to expand the hex representation into binary like how you did it.

  0000 1100 0000 0000 0000 0000 0000 0000

Then parse the word:

the left-most bit is the sign bit
the next 8 bits represent the biased-exponent
the last bits represent the fractional part with the "hidden one"

  0 | 00011000 | 00000000000000000000000

Then, follow:

s represents the sign bit
evaluate the binary representation of the exponent to decimal
subtract the bias from the exponent (bias for single-precision is 127 and 1023 for double-precision)
evaluate the normalized form to decimal and you have your floating point decimal number

I hope this helps. It took me a while to understand encoding and decoding using IEEE-754. Slow and steady wins the race.


Confusion converting BNF to regular expression

There are two ways of interpreting 'the first rule can be represented with a regular expression'; you should review this 'mark scheme' to determine which applies.  One possibility is that the first rule is being treated as defining a language over its own terminals and non-terminals, without ever expanding the non-terminals.  I.e, think of treating the tokens 'title', 'name', and 'endtitle' as single characters of the 'language' of 'fullname' (along with the space-char).  Then it is easy to see that that is a regular language - there are only four strings in it!

The other possibility is what you assumed, i.e that non-terminals are to be expanded.  In this case your observation that 'name' is recursive is misplaced.  The issue is not whether the set of productions for that non-terminal is regular, the issue is whether the set of strings generated from that non-terminal is regular.  For 'name' the answer is yes: The set of strings generated from 'name' is seen, with a little thought, to be simply a sequence of one or more 'word'-s separated by spaces, for which a regular expression is easy to construct [given a regular expression for 'word', of course].  So yes, in this case 'fullname' generates a regular language.

[P.S. Note: Your 'word' is missing a production for a single 'char']


Help in understanding exactly how lattices used as one way functions for hashing

You have several confusions regarding cryptography. First, the nature of hash functions. The non-cryptographic use of hash functions is to hash long messages into shorter ones in a "uniform" fashion. So we expect there to be many collisions, by design. Cryptographic hash functions have the additional properties that collisions are hard to find (there are several, inequivalent ways of stating this). Therefore, while it is possible to find collisions even for cryptographic hash functions (simply because the range is smaller than the domain), this should be difficult. Such hash functions can be used in various ways in cryptography, for example in digital signatures: you sign on the (small) hash rather than the (large) message.

Second, encryption is a different primitive from hash functions. Encryption itself comes in two main kinds, symmetric and public key, which are rather different, and there are many other cryptographic constructions out there. There are reductions between some of the cryptographic "primitives" (hash functions, one-way functions and the like), for example you can use them to construct HMACs (message authentication codes) and PRNGs (pseudorandom number generators), but perhaps not encryption schemes.

Regarding the matter at hand: the idea of Ajtai's hash function is to use a random lattice $A$, the hash function being $x \mapsto Ax \pmod{q}$, for some prime $q$. Here $x$ is a binary vector in $\{0,1\}^m$, embedded into $\mathbb{Z}_q^m$. The parameters here are important — the size of $A$ and $q$ — but I'll ignore them here. In order to show that this is cryptographically secure, under one definition we need to show that it is difficult to find a collision, that is two messages $x,y$ with the same hash. Such messages would satisfy $A(x-y) \equiv 0 \pmod{q}$, and so $x-y$ would be in the dual lattice $A^{\perp}$. Now $x-y \in \{-1,0,1\}^m$, so (for the correct choice of parameters) it is "short", and finding it is conjectured to be difficult. This shows the (conditional) security of the scheme.

Lattice-based encryption can also be used for public-key encryption (Regev's scheme) and for homomorphic encryption. These schemes rely on a different problem, LWE (learning with errors), which is similar to CVP (closest vector problem). The details are more complicated &mdash you can have a look at Regev's scheme in Section 5.4 of his survey with Micciancio, though it could be hard to glean from there why exactly the scheme works. Perhaps this is explained later in your course, and if you need more explanations, you can ask another question here.


How to impose Euclidean distance constraint in a constraint satisfaction problem without quadratic constraints?

You can't. You can't express this without using quadratic constraints.  Your requirement is about Euclidean distance.  The Euclidean distance is inherently quadratic.  To be more precise about that: the problem cannot be expressed using solely using linear constraints, as the Euclidean distance is non-linear.

That said, you can solve your one-sentence question directly, if you remove the requirement to use constraint programming.  The basic technique is to use triangulation.  I'll illustrate this below.

Suppose that you know point $p_1$ is at $(0,0)$ and point $p_2$ is at $(0,5)$, and you know $d(p_1,p_4)=r$ and $d(p_2,p_4)=s$ where $r,s$ are given; you want to find the location of $p_4$.  This can be found using some simple algebraic manipulations.  Let $p_4$ be at coordinates $(x,y)$.  Then by the definition of the Euclidean distance, we have

$$\begin{align*}
r^2 &= x^2 + y^2\\
s^2 &= x^2 + (y-5)^2.
\end{align*}$$

Subtracting the two equations, we get

$$r^2 - s^2 = y^2 - (y-5)^2.$$

Simplifying the right-hand side and then solving for $y$, we find

$$y = (r^2 - s^2 + 25)/10.$$

Plugging this into the definition of $r$, we also find

$$x = \pm \sqrt{r^2 - y^2}.$$

Thus, in this way you can compute the coordinates $(x,y)$ of $p_4$ (up to reflection) from the distances $r,s$ using a bit of simple algebra.

So, if you have a point $p_4$ at some unknown location, and you know its distance to two other points at known locations, you can find the location of $p_4$ using triangulation.  Strictly speaking, we have found two possible candidates for the location of $p_4$ (modulo a reflection across the line from $p_1$ to $p_2$), but if we know the distance from $p_4$ to any third point we can try both possibilities and figure out which one of those two candidates is correct.

The same techniques can be used to solve your "very short version of the question".  We know the location of $p_1,p_2$, and for each other point, we know its distances to $p_1$ and $p_2$, so we can calculate its location.  Again, the problem becomes simple if we are allowed to use algebraic manipulations, rather than being forced to express it as a constraint system.

Your "detailed version of the problem" is a different problem entirely.  If you have a complete graph -- or you have three points that are connected to all other points -- you can use the techniques outlined above.  (You can fix locations for those three points, and then derive the location of all other points using the methods above.)

But if you have an arbitrary graph, the above techniques might not be enough.  I don't believe your general problem can be expressed as a constraint program with only convex constraints: I think it's a non-convex problem.  I don't have a proof of that, though.


Core algorithms like DPLL and its refinements like CDCL are completely deterministic.

Note that non-determinism doesn't necessarily mean that an algorithm may lead to a wrong result. For example we can distinguish between

Monte Carlo algorithms, which are randomised algorithms whose output may be incorrect with some probability.
Las Vegas algorithms, which are are randomised algorithms whose output  is always correct, but the algorithms 'gamble' with the resources used in the computation, e.g. running time on identical inputs may vary.

At the other extreme are probabilistic algorithms for solving $k$-SAT such as Schöning's [ 1 ] which is Monte-Carlo, and remarkably effective in practise given its utter simplicity. Interestingly Schöning's algorithm can be completely derandomised without losing (much of) its effectiveness [ 2 ].

In practise, industrial SAT-solvers always employ some degree of randomness, so as to 'escape' from the bad (= exponential) worst-case behaviour of DPLL-based algorithms.  MiniSat is a highly configurable and evolving piece of software. That said, MiniSat is not completely deterministic: the choice of branching variable is sometimes randomised, depending on command line options. (The default is that  2% of branching variables are chosen randomly IIRC.) Likewise, MiniSAT has the option of initialising the VSIDS scores randomly. (VSIDS is a heuristic for 'measuring' the influence a variable has.)

U. Schöning, A Probabilistic Algorithm for $k$-SAT Based on Limited
Local Search and Restart.
R. A. Moser, D. Scheder, A Full Derandomization of Schöning's
$k$-SAT Algorithm.


Why is data in computer science considered to be discrete?

Answer

  why was the data considered to be a discrete mathematical entity rather than a continuous one

This was not a choice; it is theoretically and practically impossible to represent continuous, concrete values in a digital computer, or actually in any kind of calculation.

Note that "discrete" does not mean "integer" or something like that. "discrete" is the opposite of "continuous". This means, to have a computer that is truly able to store non-discrete things, you would need to be able to store two numbers a and b where abs(a-b) < ε for any arbitrarily small value of ε. Sure, you can go as deep as you want (by using more and more storage space), but every (physical) computer always has an upper bound. No matter what you do, you can never make a (physical) computer that stores arbitrarily finely resolved numbers.

Even if you are able to represent numbers by mathematical constructs (for example π), this does not change anything. If you store a graph or whatever that represents a mathematical formula, then this is just as discrete as anything else.

Addendum

The rest is just a little perspective beyond the field of computer science. As the comments have shown, the physical topic is not undisputed, and as you can see I have formulated my next paragraph in a way that is rather uncommitted to whether it's true or not. Take it more as a motivation that the concept of "continuum" is not a trivial one. The answer given above does not depend on whether space is discrete or not.

Note that all of this is not so much a problem of computers, but a problem with the meaning of "continuous". For example, not everyone even agrees, or did agree in the past, that the Universe is continuous (e.g., Does the Planck scale imply that spacetime is discrete?). For some things (e.g., energy states of electrons and many other features in Quantum (sic) Mechanics) we even know that the Universe is not continuous; for others (e.g., position...) the jury is still out (at least regarding the interpretation of research results...). (Notwithstanding the problem that even if it is continuous, we could not measure to arbitrary precision => Heisenberg etc.).

In mathematics, studying the continuum (i.e., the reals) opens up a lot of fascinating aspects, like measure theory, which makes it utterly impossible to actually store a "continuous" kind of number/data.


Examples for CFG that cannot be expressed by regular language

Theoretically, you can nest sentences arbitrarily depth, by using subclauses and this excluded any finite state mechanism. The inventor of the phrase structure grammars himself looked at finite state languages, and compared them with the model of phrase structure grammars. The abstract of his paper Finite State languages reads:

We find that no finite-state Markov-process [...] can serve as an English grammar [...]

The idea to use finite Markov processes, which came down to finite automata in Chomskys work, go back to ideas of Shannon (see his seminal work A mathematical theory of communication). If this caught your interest, you might also take a look at the two works Three models for the description of language and Syntactic structures by N. Chomsky, where he further discusses the adequacy of grammars and finite state processes for language description (or production thereof).
Later, these ideas, which originally came from linguistics and where therefore closely related to research on natural languages, where later adapted by computer scientists to describe programming languages. I refer to the seminal papers Two families of languages related to ALGOL by Ginsburg and Rice or Revised Report on the Algorithmic Language Algol 60, where the BNF was introduced, the first papers using this phrase structure (or nowadays context free) grammars to describe programming languages.
But on the other side, you seldom find "arbitrary" complex nested sentences, as, in general, the "cognitive" system could not handle them, or said differently this could be conceived as a finite state systems. I refer, for example, to the famous paper The magical number seven, plus or minus two by G. Miller, which states that for numbers the human brain can only store a finite number $7 \pm 2$ of digits. Similar restrictions might hold for language processing, see the textbook The psychology of language by T. Harley.


Shortest Path in a Directed Acyclic Graph with two types of costs

This answer is mostly based on my earlier comments.
It is unlikely that there is an algorithm that works in $O(|E|^{2 - \varepsilon})$ time for all graphs. It is still possible that there are faster algorithms for dense graphs ($E = \Omega(V^2)$) or somehow dense graphs ($E = \Theta(V^\alpha)$ for some $\alpha > 1$), but an algorithm that works in $O(|E|^{2 - \varepsilon})$ time for sparse graphs ($E = O(V)$) would contradict so called $k$-cycle hypothesis
(you can check this paper and this paper for more details on the statement and its applications to lower bounds for dynamic shortest path and other graph problems).
The reduction
I prefer to state the $k$-cycle hypothesis in the following way, which is equivalent to the way it is usually stated (for more details, see the last section):

For any $\varepsilon > 0$, there is a positive integer $k$, such that there is no $O(|E|^{2 - \varepsilon})$ algorithm for checking whether there is a closed walk of length exactly $k$ in the given directed graph.

Let's reduce the problem of finding a closed walk of length $k$ in a given directed graph $G(V,E)$ to the problem in question for a slighty larger graph. Construct a new graph $H$ ($H$ will be a DAG), whose vertex set consists of a source vertex $s$, a sink vertex $t$ and vertices $(v, \ell)$ for each $v \in V, \ell \in [1, k + 1]$ ($k + 1$ layers, each being a copy of $V$).
Each edge $u \to v$ of the original graph splits into $k$ edges in $H$: $(u, \ell) \to (v, \ell + 1)$ for each $\ell \in [1, k]$, with each of those edges having $w$ and $p$ parameters set to $0$. Also, there will be $|V|$ edges from the source to the first layer ($s \to (v, 1)$ with parameters $w := v$ and $p := 3|V| - 2v$ for each $v \in V$; here I assume that vertices of $G$ are numbered from $0$ to $|V| - 1$). Similarly, there will be $|V|$ edges from the last layer to $t$ ($(v, k + 1) \to t$ with $w := v$, $p := 3|V| - 2v$).
Clearly, $H$ has $(k+1)|V| + 2$ vertices and $2|V| + k|E|$ edges.
Now, each $s \to t$ path $s \to (v_1, 1) \to (v_2, 2) \to \ldots (v_{k + 1}, k + 1) \to t$ in $H$ corresponds to a walk of length $k$ in the original graph ($G$). The corresponding walk is closed if and only if $v_1 = v_{k + 1}$. The main idea is that we have chosen the parameters $w$ and $p$ to ensure that paths with $v_1 = v_{k + 1}$ have the smallest possible cost.
Indeed, the cost of $s \to (v_1, 1) \to \ldots \to (v_{k + 1}, k + 1) \to t$ path in $H$ is $v_1 + v_{k + 1}  + \max(3|V| - 2v_1, 3|V| - 2v_{k+1}) = v_1 + v_{k + 1} + 3|V| - \min(v_1, v_{k + 1}) = 3|V| + |v_1 - v_{k + 1}|$. Hence, the shortest $s \to t$ path in $H$ has cost $3|V|$ if and only if the original graph $G$ contained a closed $k$-walk. Therefore, under k-cycle hypothesis, there is no $O(|E|^{2 - \varepsilon})$ algorithm for problem in question.
Can we do better for dense graphs?
Honestly, I don't know. Proving lower bounds for dense graphs seems to be difficult, because the problem is strictly simpler that dynamic shortest paths. Hence, the only
simple "vector of attack" is to try using the same methods that are used for dense graphs and hope that they will work even for the simpler problem. Maybe future answerers will be more succesful here?
As for faster algoritms, an existence of $O(VE)$ algorithm sounds plausible. The only thing that I managed to come up with is the following algorithm, whose complexity is a bit hard to estimate, but I suspect that it still should take $\Omega(E^2)$ time in the worst case:

Find some shortest ($s \to t$)-path in the original graph with respect to sum of $w$'s, breaking ties by minimizing the maximum of $p$'s (it is possible to do this by dynamic programming in $O(|E|)$ time). Let's say that the largest value of $p$ for edges on the chosen path is $P$. Then, all edges $e$ with $p_e \geqslant P$ can't appear in a path with a smaller cost (because otherwise the chosen path was not shortest with respect to sum of $w$'s). Therefore, we can delete all such edges and repeat the process.

Why did I choose an uncommon statement of k-cycle hypothesis?
Usually, it is stated in the terms of finding a simple cycle of length $k$, but for fixed $k$ finding a simple cycle can be reduced to finding a closed walk in (larger) graph by known techniques like color coding. All these techniques require blow up the size of the graph exponentially with respect to $k$ (otherwise we could solve Hamiltonian Cycle in subexponential time), but we can handle this, because $k$ is fixed and small.
Intuitively speaking, for small $k$, the "main problem", asymptotically speaking, is not ensuring that all vertices of the cycle are different, but remembering where the cycle started.
Because the problems are equivalent, I chose the one which is easier to work with. Moreover, apart from having a theoretical reduction, we also have a practical reduction now. For example, if we assume that there is no way to check whether a graph with $10^6$ edges has a closed walk of length $k = 6$ in under $10$ minutes on a normal computer (I would say, that this is a huge understatement, considering the large constant factors of graph searches; though I would be very positively surprised to be wrong), then there is no way to solve the problem in question for graphs with $10^6 / (k + 2) = 1.25 \cdot 10^5$ edges in under $10$ minutes, e.t.c. The point is, that the constant factors involved in the reduction are reasonably small.


Formal defintion of SET-PARTITION as a language

The set partition problem asks whether there exists a 2-partition of a multi-set such that sum of numbers in one set is equal to the sum of numbers in the other set.

Note the phrase whether there exists; if you are already being given the partition in the input $\langle S,A,B \rangle$ then the problem becomes whether the given partition is valid and sum of elements of $A$ and $B$ are equal. This problem is easy and can be solved in polynomial it time.

However, Set Partition is NP-Complete, which seems unlikely to be solved in polynomial time.


Why $T(n)=6T(n-1) + n^3$ has such a mess solution?

I'm not sure why you think this solution is invalid. It implies that
$$
\sum_{i=0}^n 6^i(n-i)^3 \sim \frac{366}{625} 6^n,
$$
and in particular,
$$
\sum_{i=0}^n 6^i(n-i)^3 = \Theta(6^n).
$$
You can also check it for particular values of $n$.

For example, when $n = 0$ you clearly get zero, and for $n = 1$ you get
$$
\frac{-125-450-630+366 \cdot 5}{625} = 1 = 6^0 (1-0)^3 + 6^1 (1-1)^3.
$$


What is the name for the comparison used in C's memcmp?

The question is about a three-valued function in a situation where a boolean is often used (eg <=).  I personally refer to this as the sign or signum: the sign of the difference of the comparands.  However I have not seen a widely-used term; the best supportable answer I can give is that there is none.

In Quicksort, when a three-way partition (based on this "signum") is used instead of two-way, it's called ternary (and there are ternary search trees based on the same distinction), but that's about as specific as it gets.

My reasoning behind my naming this quantity signum is that comparison is often implemented as subtraction; the CMP instruction is essentially a SUB instruction that discards the actual result but retains the sign and zero flags.

Strings are obviously not numbers, but they have a commonly-used embedding into [0,1) that makes lexicographic comparison equivalent to subtraction and signum extraction.

As to the idea of a two-valued (==, !=) predicate, there is some precedent for this idea in contexts where the signum may not be obtainable.  Fagerbergh, Pagh et al. construct what they call a "unordered trie" on hashed string values, where the original order of the strings is obscured due to hashing, but the position where they first disagree is still known.  This practice also has some use in applying collations, where only the branching character needs to be looked up to get the collated order (the equal prefix is skipped).


What is the name of this function of a tree?

This is basically the Strahler number, which is great because now I can call my function ComputeStrahlerNumber instead of keeping the profane function name I was using as a placeholder.


Prime attribute dependant on another prime attribute allowed under BCNF?

By definition, a relation is in BCNF if and only if, for every non trivial functional dependency, the left hand part is a candidate key.

So, if you have a dependency A → B where both A and B are prime attributes, this dependency violates the Normal Form only if A is not a candidate key, but a part of some candidate key.

Note that in that case, the dependency does not violates the 3NF.


Validity of self refering state with linear temporal logic 'X' connective

Your textbook correctly states that

$\pi \models X\phi$  iff $\pi^2 \models \phi$

under the assumption that $\pi$ is a word/trace of the transition system and the characters of the word are numbered starting with 1.

So the question that you should ask is how an infinite trace from state $s_2$ would look like and then evaluate the formula on that trace. LTL is only defined on infinite traces, so these are the ones that you should be looking at.

Note that checking if

$M, s_2 \models Xr$

holds does not make sense (in general), as LTL is defined over traces, but from a state in a labeled transition system, there could be multiple traces. So it is not clear what $M, s_2 \models Xr$  should mean - does it mean that it's defined on any trace or every trace? This syntax seems to come from computation tree logic (CTL).


Partition array - elements non-negative and negative. Minimal number of replacements of elements

Hint:

Create a new array $B=[]$ where $B[i]=1$ if  $A[i]<0$ and $2$ elsewhere.
You can prove that sorting $B$ is same as performing said operation on $A$

So now, We have to sort an array which only contains two values.
You can do this by a greedy algorithm, whose proof you can obtain by the principle of Induction.

As an extra hint: Let $B=[1.....1,2.....2,1,........]$. where  C is another segment of the array. You have to do something now.

Trust me this is great help. You can continue from here.

As for why it requires fewer(or equal) than $n/2$. The proof is quite easy, once you've devised the algorithm.


What is the practical purpose of an epsilon NFA?

Purely convenience.  It's like, in a programming language, why have for loops, if every for loop could alternatively be written as a while loop?  Convenience.  It's sometimes convenient to be able to use epsilon-transitions, when defining NFAs.  For instance, when converting a regexp to a NFA, the construction is arguably a bit simpler (easier to understand) if you allow yourself to use epsilon-transitions.


How many different (full/complete) in-order binary-trees do exist?

Q1: How many different binary-trees do exist?
A1: c(n) = (2n)! / ((n + 1)! * n!) → c(4) = 14

Q2: How many different complete binary-trees do exist?
A2: Exact one:

;       (3)        L0: full
;      / | \
;   (2)  |  (4)    L1: full
;   /|   |   |
; (1)|   |   |     L2: not full (Node 2 is missing right child)
;  | |   |   |
;  1 2   3   4     Complete?: Yes, because all (but last) levels are full.

Q3: How many different full binary-trees do exist?
A3: If n is odd: c((n-1)/2) else 0. n = 4 therefore 0. Reference

Thanks to YuvalFilmus for the help!


No, you don't need to specially add any such clause.

Here's where I think you might have gone wrong.  The result is not 3 clauses (3 conjunctions).  The result is a bunch of clauses.  We get one clause of the form $\neg Shaves(Barber, x)\  \lor\ \neg Shaves(x, x)$ for each $x$, one of the form $Shaves(Barber, x)\  \lor\ Shaves(x, x)$ for each $x$, and one last clause $Shaves(Someone, Barber)$.  Thus, if there are $n$ people ($n$ possible values of $x$), the CNF form has $2n+1$ clauses in it.

Finally, note that the Barber is one of those $n$ people.  Thus, for the clauses corresponding to the case $x=Barber$, we get a clause $\neg Shaves(Barber, Barber)\  \lor\ \neg Shaves(Barber, Barber)$ and a clause $Shaves(Barber, Barber)\  \lor\ Shaves(Barber, Barber)$.  Now you should be able to find a contradiction in there.


Why is $O(\log_{M/B} N/M)$ the same as $O(\log_{M/B} N/B)$?

Your construction will work just fine:
$$\begin{align}
\log_{M/B}\frac{N}{M}&=\log_{M/B}\frac{NB}{BM}=\log_{M/B}\frac{N}{B}\cdot\frac{B}{M}\\
 &= \log_{M/B}\frac{N}{B}+\log_{M/B}\frac{B}{M}\\
 &= \log_{M/B}\frac{N}{B}-1
\end{align}$$
Since the two terms differ by 1, they're asymptotically equal.


Enforcing application layer consensus on top of a distributed consensus protocol

You've asked multiple questions here.  I'll answer the first one.

Typically consensus means that all the honest participants have the same view of the state of the system.  There's not necessarily a guarantee that this state is "correct" in any sense (some protocols might also provide that guarantee, but it is in some sense a separate or additional request).

Often there are some rules about what kinds of state changes are "valid" or "allowed", and the honest participants are also tasked with ensuring that every state transition is valid; they won't generate or request transitions that aren't valid, and they won't accept transitions from others that are invalid.  If you do this right then you get the additional guarantee that all the honest participants have the same view of the state of the system, and this state is valid.

There are multiple ways to define which states or transitions are valid.  One way is by defining a state machine (like a DFA) that represents which state changes are valid; then the protocol provides a distributed implementation of the state machine.

I'm not an expert, but if you want to get a more authoritative answer, you could read the literature about state machine replication.  It's probably worth reading the PBFT paper, which is presented as an instance of state machine replication.


is it possible to determine using a single depth-first search, in O(V+E) time, whether a directed graph is singly connected?

I just realized, a single call to DFS is not sufficient, since the conjecture I asked about is not true. Here is a counterexample. Suppose DFS first visits all nodes in a tree rooted at $u$, and $v$ is a descendant of $u$. Then suppose an unvisited vertex $w$ has both $u$ and $v$ in its adjacency list. Then, $w$ would not be in the same tree as $u$ and $v$, but there would be cross-tree edges $(w, u)$ and $(w, v)$, and hence there would be more than two paths from $w$ to $v$, making the graph not singly connected.
However, we cannot modify the algorithm to also look for cross edges between trees, since if we removed the $(w,u)$ edge from the example above, then it's still possibly for it to be singly connected even though there's a $(w,v)$ cross edge.


Is decimal number 8 represented as 3 bits or 4 bits in computer?

$b$ bits have a total of $2^b$  distinct bit-patterns. To store 8 distinct values, you need at least 3 bits.

This does not tell you on its own how many bits are required to store the number 8, because it depends on the way that you assign numbers to bit patterns.

A typical "unsigned integer" uses $b$ bits to represent the numbers 0, 1, ... 2^b-1. In that format, you would need 4 bits to represent 8, because $2^3-1<8<2^4-1$.

A typical "two's complement integer" uses $b$ bits to represent the numbers $-2^{b-1}$ to $2^{b-1}-1$. In this format, you would need 5 bits to represent 8, since $2^{4-1}-1<8<2^{5-1}-1$.

If you're only interested in representing powers of two (perhaps because you doing something hardware or memory related, where divisions such as alignment are only ever powers of two), you use fewer bits; for example, if 00 is 1, 01 is 2, 10 is 4, and 11 is 8, you only need 2 bits to represent 8.


How do Hard Drives Send and Recieve Data?

As it stands, this isn't a Computer Science question. Actually, it's several questions, some of which could be phrased of as computer science questions.

Disk-like devices (these days we'd include flash memory) do not understand the concept of a "file" or "directory". You can think of a disk as a big array of fixed-size blocks. The two basic operations are "read a block" and "write a block". Files are an abstraction on top of this implemented by the operating system.

All of this is explained in any operating systems course. But if you just want the short version, I recommend Maurice Bach's classic book The Design of the UNIX Operating System. It doesn't reflect modern operating systems or filesystems that well, but it will give you a good idea about what operating systems do and what they expect of a disk device. If that wasn't enough for you, Practical File System Design by Dominic Giampaolo is a whole book which gives an in-depth look at a more modern filesystem design.

The hardware that sits between there and the disk is a topic all by itself. On a modern system, disks can be connected to a computer using a variety of different hardware connection (e.g. USB, SATA, SCSI), and a modern operating system needs to both be able to talk to the host controller for this bus, but also be able to tell what is attached to the bus. For some busses (e.g. USB) there may be a complex topology for the operating system to discover; the disk may be connected via a hub, for example.

The final link in the chain is what lies between the bus and the storage medium itself, and this is presumably what you're interested in.

My suggestion, if hardware engineering is what you're most interested in, is to hook a simple computer (e.g. a microcontroller) up to a simple storage device (e.g. MMC) and see what you can do. You will learn a lot this way.

As a final comment, there is a book by Jan Axelson called USB Mass Storage: Designing and Programming Devices and Embedded Hosts. I can't recommend it because I haven't read it, but it looks like the sort of thing you might want to know. If I'm reading the table of contents correctly, it looks like it gives you everything you need to know to build a USB flash drive. That sounds like a fun project to me.


How to represent OOP concepts in algorithms in a standard way?

Generally there is no unified to present algorithms. Each researcher should use/introduce notation with which he is most comfortable with.

If you look at some algorithmic books writers have different approach to this manner.

For instance:

CLRS book gives no types for functions arguments
Tel's "Introduction to distributed algorithms" gives types
Sedgewick's "Algorithms" gives code in Java (which is not very good solution IMO)

On the other hand any object can be represented as tuple of base data types, eg binary tree can be presented as:

(5,(3,(1,NIL,NIL),(4,NIL,NIL)),(6, NIL, NIL))

Which might corresponds to

5
|\
3 6
|\
1 4

But the first notation is not very readable, so its easier to relate so such tuple as Node.

Additionally algorithms representation depends on field on which they are presented. If you assume that algorithm should be more or less translatable from pseudo code to actual code then you should introduce hints and notation to your algorithm presentation which allow this. But if that is not the case and you want to focus mainly on algorithm idea, or some other complexity value then, time then mathematical notation might become handy. In the end as previously stated it depends on needs.

If you look closely on various papers and books you can see that types of arguments are either obvious from context, or explained in algorithm description.

I suggest you to get familiar with $\LaTeX$ Algorithms module.


Plain-language example of how a functional style makes parallel programming easier

I'm not sure functional programming does make parallel programming any easier, when taken in the round.
If you program in a "functional style" (including all so-called good practices), then converting certain steps of a serial program to parallel execution (and getting results that are equivalent to the serial execution) may not usually involve much further difficulty, but that is primarily because all the difficulty has already been imposed in drafting the program in a form where it doesn't matter whether many steps are executed serially or in parallel.
Moreover, functional programming does not claim to guarantee that a serialised execution of a program actually produces "correct" (i.e. intended) results for all inputs, only that parallelised execution will involve no additional error.
In general, business systems have an irreducible need to mutate state and shared data, so any benefit or guarantee that depends in theory on not mutating state at all, can be dismissed out of hand as almost worthless to real-world development.
If the point at which state is mutated is seen as a boundary across which the guarantees of functional programming cease to apply, then the vast majority of programs can get almost nothing done before having to cross a boundary and step outside such guarantees.
Many people seem to over-estimate how much error actually occurs in systems due to race conditions etc. involving unnecessary mutations, rather than errors which involve the necessary mutations of shared data that must occur equally in functional programs as in non-functional ones.
Arguably, a real benefit of functional programming is that it allows certain kinds of functionality (especially complex calculations) to be implemented more quickly or to a more complex extent, at the price of a higher initial learning curve.
In other words, it will allow the best programmers to work a little faster once experienced, or get a little further than before with the most complex systems, at the expense of requiring far more training and experience to begin with, and excluding third-rate programmers from getting anywhere at all.
This, however, is not the typical understanding people have of the word "easier", or of a tool that "makes things easy". I contend that functional programming may improve productivity in some cases, but it does so by increasing the threshold of difficulty in many respects.


Why the time complexity of Prim's algorithm is not $|V||E|lg|V|$ but $|E|lg|V|$?

The pseudocode for Prim's algorithm, as stated in CLRS, is as follows:

MST-PRIM(G,w,r)
1   for each u ∈ G.V
2      u.key = ∞
3      u.π = NIL
4   r.key = 0
5   Q = G.V
6   while Q ≠ ∅
7      u = EXTRACT-MIN(Q)
8      for each v ∈ G.Adj[u]
9         if v ∈ Q and w(u,v) < v.key
10           v.π = u
11           v.key = w(u,v)

The loop in line 6 will execute exactly $|V|$ times, since $Q$ starts with $|V|$ elements and we remove one each iteration. For each node $u$, the loop in line 8 will execute $\text{deg}(u)$ times, so the DECREASE-KEY operation (lines 10 and 11) will execute at most $\text{deg}(u)$ times.

In total, the loop in line 8 will be executed $2|E| = \sum_{u \in G.V} \deg(u)$
times, and DECREASE-KEY $O(|E|)$ times.

I would suggest you to grab a piece of paper, draw a graph, and run the algorithm on it while counting how many times you do the DECREASE-KEY operation.


Median of medians confusion -- the "approximate" median part

Median-of-medians is a recursive algorithm which solves the more general selection problem: given an array $A$ of length $n$ (which we assume, for simplicity, has distinct elements) and an integer $k$, find the $k$'th smallest element (where $1 \leq k \leq n$). It works as follows:

If $n \leq K$ (where $K$ is some constant), solve the problem by brute force.
Otherwise, find an approximate median $x$ of $A$ in $O(n)$. By approximate median, we mean that $x$ is the $m$'th smallest element in $A$, where $\alpha n \leq m \leq (1-\alpha) n$ for some constant $\alpha < 1$.
Use $x$ to split $A$ into elements smaller than $x$, comprising an array $A_{<x}$ of length $m-1$, and elements larger than $x$, comprising an array $A_{>x}$ of length $n-m$.
If $m = k$, then output $x$. If $m > k$ then output the $k$'th smallest element of $A_{<x}$. If $m < k$ then output the $(k-m)$'th smallest element of $A_{>x}$.

The running time of the algorithm satisfies the recurrence $T(n) \leq T(\alpha n) + O(n)$, whose solution is $T(n) = O(n)$.
The algorithm finds the exact median, but it does so by repeatedly finding approximate medians.


why is the max number of Nodes mod(N/m) + mod(N/m^2) + 1 in R-tree?

Here is the relevant excerpt of that paper.

  The height of an R-tree containing $N$ index records is at most $\lceil\log_m N\rceil$, because the branching factor of each node is at least $m$. The maximum number of
  nodes is $\lceil\frac Nm\rceil + \lceil\frac N{m^2}\rceil + \cdots + 1$. Worst-case space utilization for all nodes except
  the root is $\frac mM$.

The paper you saw is so fuzzy that you mistook the formula as $|\frac Nm| + |\frac N{m^2}| + 1$.

How to explain the correct formula? Since all leaves are on the same level and each leaf-node contains at least $m$ index records, there are at most $\lceil\frac Nm\rceil$ leaf nodes. The number of the parents of all leaf nodes is at most $\lceil\frac{\frac Nm}m\rceil=\lceil\frac N{m^2}\rceil$. And so on.

Here is a copy of that paper that is more legible.


Is the Clique Problem polynomial time reducible to the graph-Homomorphism Problem and if so what does the reduction look like?

The $k$-clique problems asks whether there is a homomorphism from the $k$-clique to a given graph. Therefore in principle, given an instance $\langle G,k \rangle$ of $k$-clique, you can just output $\langle K_k, G \rangle$, which is an instance of graph homomorphism.

However, in general $\langle K_k, G \rangle$ could be much larger than $\langle G,k \rangle$, since encoding $k$ takes $\Theta(\log k)$ bits, whereas encoding $K_k$ probably takes $\Theta(k^2)$ bits (depending on your encoding). Assuming that graphs are encoded as adjacency matrices, the solution is to compare $k$ to the number of vertices in $G$. If $k$ is larger than the number of vertices in $G$, then the answer is No, and so you can output a fixed No instance (say $K_2,K_1$). Otherwise the size of the output instance is polynomial in the size of the input instance, and so there is no problem.


You need to read all items in the worst case. Assume you have written some algorithm which reads items in any order and processes them with any amount of cleverness. And I'm your opponent and try to make you read as many items as possible.

Here's what I do: Whenever your algorithm reads an item I store an "X" just before you read it. I do that except when you have read one array completely, which consists of all X, and you are reading the last item of another array, in which case I store a value that makes this row different from all other rows that were read completely. When you read the very last item, I can decide to store a value that makes all arrays unique, or I store another X and you have two arrays that are identical.

Whatever you do, until you read the very last item you don't know whether two arrays are identical or all arrays are unique.


Upper bound on the number of triangles in a planar graph

Presumably you have to show that if you triangulate an arbitrary planar graph then you get an Apollonian network. Then you have to show that the triangulated graph contains more triangles than the original one. This will complete the proof.


How many zeros should be in front of two's complement model?

Two's complement is a representation of a number. Using different bases, encodings, a number (as a mathematical object) can be represented in many ways.

There is no "specified number of zeros". It is rather than, if you have 10 bits, they can represent 1024 values.
It can be unsigned numbers between 0 and 1023
It can be signed numbers between -512 and +511 if you use two's complement.

"0100000000" is indeed 256 both as unsigned and two's complement signed 10 bits numbers.


Basically this is shortest path problem in polygon with holes. There is no constraint in taking $E_i$ as a path of negligible width.

If you just want to connect internal holes to outside boundary without caring about the path length, then just take any point on the boundary of interior hole and calculate a path to any point on the outer boundary. I don't know your application, but probably you are looking for minimum link rather than minimum euclidean distance, in that case minimum link path would be better.

References:
1) S. K. Ghosh and D. M. Mount. An output-sensitive algorithm for computing visibility graphs. SIAM Journal on Computing archive
Volume 20 Issue 5, Oct. 1991
Pages 888-910   (for shortest paths among obstacles)
2) J. Hershberger and S. Suri. Efficient computation of Euclidean shortest paths in the plane. In Proc. 34th Annu. IEEE Sympos. 1993.
3) Joseph S. B. Mitchell, Günter Rote, and Gerhard Woeginger: Minimum-link paths among obstacles in the plane. Algorithmica 8 (1992), 431-459.

However, I should warn you, all the implementations for shortest path, or shortest link path use triangulation for which the optimal algorithm is not very practical. You can however use any sub-optimal algorithm which may be more efficient for your purpose.

The above algorithms are all polynomial in input size.


For a logic gate to be universal, must it necessarily be able to perform duplication?

I'm not sure what you're asking, precisely, but it's certainly not true that a reversible universal gate requires the number of set bits in the output to be the same as in the input. Toffoli gates do not have that property, for example.
EDIT
Thanks for the clarification. The answer to your question is that any reversible circuit must have at least as many output lines as input lines. As an exercise, prove this. Try using the pigeonhole principle.
So what happens if you need a reversible circuit with fewer output lines than input lines? You just add output lines, the values of which are irrelevant. The circuit still computes what you need it to, it also happens to compute more stuff that you don't care about.
So what I think you're asking about duplication is can there be more output bits than input bits? The answer is "kind of", and it comes down to what model of reversibility you care about.
Such a circuit can clearly be logically reversible. But can it be physically reversible? I'm not a hardware designer, and I don't know.


Simple algorithm to generate a linear extension from partial order set

No, there is no simpler way.  Topological sorting is exactly the problem of generate a linear extension from a partial order.  There are several standard algorithms for topological sorting; they are already pretty simple, and there's no reason to expect anything simpler.


For each given set choosing either it or its complement such that their union exactly has a given size

This problem can be solved in polynomial time.

If $k=|U|$, this problem is exactly another wording for SAT where each clause contains all variables. More precisely, for each element $j\in U$, let $l_{ij}=b_i$ if $j\notin A_i$ while $l_{ij}=\neg b_i$ otherwise. The problem is exactly to satisfy the clauses $l_{1j}\vee l_{2j}\vee\cdots \vee l_{nj}$ for all $j$. If all possible clauses are involved in, the answer is certainly NO. Otherwise, without loss of generality, say one missing clause is $b_1\vee\cdots\vee b_n$, we can set $b_1=\cdots=b_n=0$ to satisfy all other clauses, thus the answer is YES.

If $k<|U|$, then at least one element should not be included in the union. We can test for each element: if this element is not included in the union, we can determine for each set whether it or its complement should be chosen, then we can see whether their union exactly has size $k$.


How can we reduce variables when converting from 3-SAT to 4-SAT?

The paper Effective Preprocessing in SAT through Variable and Clause Elimination covers the variable elimination techniques used in Minisat.  Broadly, variables can be eliminated by

Substitution, in which a variable to be removed is defined in terms of other variables in the formula and the definition is substituted everywhere in place of the variable.  Automatic Extraction of Functional Dependencies describes how to efficiently find (some of) these variable definitions.
Distribution, in which all clauses containing a negated literal of $x$ are resolved against all clauses containing a positive literal of $x$.  The produced resolvents are kept (minus any tautological clauses) and the original clauses containing $x$ are discarded.  The resulting formula is satisfiable iff the original formula was satisfiable.

The overall goal of the techniques described in the Minisat paper is to optimize the formula for exploration by a CDCL solver by reducing the total number of clauses and strengthening (decreasing the length of) the clauses that remain.
 You could of course (with exponential effort) eliminate all the variables, eliminating all the clauses as well if the formula was satifiable or leaving one or more empty clauses if formula was unsatisfiable.


The DAG represents the covering relation $\lessdot$ of a partial order $<$, also known as its Hasse diagram. An element $y$ covers an element $x$, in symbols $x \lessdot y$, if $x < y$ and no $z$ satisfies $x < z < y$.

Suppose that $Y$ is a non-empty set of elements in the partial order which is upwards closed (if $z \in Y$ and $u > z$ then $u \in Y$), and in which any two elements have a join. Let $y \notin Y$ be such that $Y \cup \{y\}$ is also upwards closed. Then for all $z \in Y$,
$$
z \lor y = \min_{y \lessdot u} z \lor u,
$$
if the minimum exists.
(This is Lemma 1 in Fast recognition of rings and lattices by Goralcik, Goralcikova, Koubek, and Rodl.)

This suggests the following algorithm for finding whether any two elements have a join (we can similarly determine whether any two elements have a meet):

Arrange the elements in decreasing topological order $x_1,\ldots,x_n$.
For $i=1,\ldots,n$, attempt to compute $x_j \lor x_i$ for all $j < i$.
Return TRUE if all attempts were successful.

In order to compute $x_j \lor x_i$, we use the following algorithm:

Let $u_1,\ldots,u_m$ be the elements covering $x_i$.
Set $a \gets x_j \lor u_1$.
For $i=2,\ldots,m$, check whether $x_j \lor u_i \leq a$ (i.e., if $(x_j \lor u_i) \lor a = a$), and if so, set $a \gets x_j \lor u_i$.
Verify that $a \leq x_j \lor u_i$ (i.e., that $a \lor (x_j \lor u_i) = x_j \lor u_i$) for all $i=1,\ldots,m$.
If verification was successful, return $a$.

Finding a topological ordering takes time $O(n+|E|)$.
If we denote by $C(x)$ the number of elements covering $x$, then the rest of the algorithm runs in time proportional to $\sum_{i=1}^n iC(x_i) \leq n|E|$, since $\sum_i C(x_i) = |E|$. In total, we get a running time of $O(n|E|)$.

It is known that the covering relation of a semilattice contains $O(n^{3/2})$ edges (see Statement 3 in the paper mentioned above). Hence we can abort the algorithm if $|E|$ is larger, and otherwise we can assume that $|E| = O(n^{3/2})$, and so the algorithm above runs in time $O(n^{5/2})$. This is Theorem 2 in the paper mentioned above.

Concluding, we can determine whether a DAG is the covering relation of a lattice in time $O(n^{5/2})$. A recent survey by Freese, Algorithms for finite, finitely presented and free lattices mentions obtaining faster algorithms as an open problem (Problem 1 in the survey).


What is the complexity of the following problem?

As Ariel explained in the comments:

"then $a$ indeed represents a valid computation of $M$ on $w$ since the Cook Levin reduction is parsimonious" - This has nothing to do with the reduction being parsimonious, this is a result of the specific construction of the reduction. Also, you don't have to appeal to Cook-Levin to encode computations of a Turing machine, there is no real reason to talk about assignments for boolean formulas in this context. You can simply say that $a$ is a description of $M$'s tape, state, and head location during some prefix of its computation.

Additionally, the input should consist of $M,w$ alone, you don't have any information about $M$'s running time from its encoding (how would you know if the machine actually runs in exponential time?). Now, the problem is trivially solvable in polynomial time by reading $a$ and checking that any configuration is reachable from its predecessor by one of $M$'s transition functions.


Complexity and hardness of undirected path

The undirected version of PATH, usually known as USTCON, is in L due to Reingold's theorem.

USTCON is trivially complete for L with respect to logspace reductions. I don't know if it is L-complete with respect to weaker reductions such as $\mathsf{AC}^0$ reductions; see this question.


Reasons for choosing register number and address sizes in an Instruction Set

Two bits for the register and ten bits for the address makes sense when you have ~four registers and ~1024 words of memory. Any more and you can't address it all (how would you access register #5, or memory address #1025?); any less and you're wasting precious bits in every instruction (why use two bits for the register when there's only two registers to choose from?).

Generally, the purpose of a cache is to make things faster without changing the underlying model. In other words, if you don't care how fast your code is, you can just pretend the cache isn't there. Everything will work the same either way.

P.S. You can address more memory than this using various tricks like "bank switching", but I doubt you're concerned with those yet.


Which has optimum performance? raw core or multithreaded

There's no real way to answer this without a lot of details about both the code to be executed, and the micro-architecture of the CPU executing the code.
A CPU that can execute multiple threads per core will typically start with a pool of instructions, decoded and ready to execute. As instructions enter the pool, a scoreboard1 gets updated to reflect inputs to an instruction, execution resource(s) needed by that instruction, and the output of the instruction.
So you might have an instruction like add r0, r1, r2, meaning add register 0 to register 1 and put the result in register 2. The inputs are registers 0 and 1, the execution resource needed is an integer adder, and the output is register 2.
Then there's a scheduler that looks at the resource usage and tries to find instructions that don't conflict, and each clock cycle, tries to find as many of those as possible to execute. As it does so, it updates the scoreboard so the next clock cycle, it'll know what resources are in use now.
That all leads to the basic question: given the parallel resources provided by this CPU, and the instructions in the streams to be executed, what is the average level of conflict between instructions?
The drastically simplified answer is that more often than not, executing two independent streams of instructions will result in more instructions that can execute with fewer conflicts, so overall speed will increase much more often than not. It's rarely a question of which is faster--only of how much speed you'll gain by executing more threads in parallel, and whether that gain is enough to justify the extra labor to make that work, or whether you'd have gained more by expending more the CPU budget on other things that could have made an even bigger difference (e.g., bigger cache, better branch prediction, etc.)
Goal
There's also room for a bit of question about your goal here. A single core executing two threads will typically execute each thread a little slower than that thread would execute on a core by itself. On the other hand, the overall throughput of the system will be somewhat greater than if you ran only one thread at a time.
For example, if you had a CPU that was split almost perfectly between two threads, each might run at 60% of the speed it would if it was the only thread running on a core.
So, if you really care almost exclusively about the performance of one thread, then running only one thread per core may well improve the speed of a thread when it is running.
At the same time, if you have two threads each running at 60% the speed it would on its own, your overall speed is 120% of what it would be with each thread running on its own, meaning you're getting about 20% more work done per unit time.
In a game (for one example) it's pretty common to have one thread that really matters, so you really want to optimize performance for one thread. If that's your case, you probably only want one thread per core.
On the other hand, with something like a server you often have lots of requests happening all the time, and one major concern is maximizing overall throughput. In such a case, more threads per core can make a lot more sense (but also note that total throughput isn't usually the only concern even in this case).
CPU Utilization
Since "CPU Utilization" was mentioned in a comment, I'll comment on it a bit as well. Generally speaking, when an operating system reports something like percentage of CPU utilization, it's basically irrelevant to questions like this.
An OS is basically just reporting what percentage of CPUs have threads assigned to execute on them at any given time. For example, if a single-threaded CPU executes an instruction to read from main memory, it could easily take 50-100 clock cycles to execute a single instruction. According to the OS, that's keeping the CPU 100% busy for those clock cycles--but most of the CPU's actual resources would be available, so it could perfectly well execute other instructions during that time.

Well, the early versions were called "scoreboards". More recently there are more complex structures with other names, but I'm going to call all of them scoreboards to keep things simple.


In perfect hashing, why does a secondary hash table that is quadratic in size leads to no collisions?

If $n_j$ keys hash to slot $j$ of the first-level hashtable, and if $n_j > 1$, we will need to use a second-level hashtable for that slot. Theorem 11.9 helps us in the sense that, if we keep this second hashtable size as $n_j^2$, then atleast 1/2 of the hash-functions in any universal-class (which all hash to range 0 to $n_j^2-1$) must give no collisions for the $n_j$ keys.
We can NOT conclude that if we pick any random function from this class, we will have a collision-free case. We will need to do some trials, and can hope to succeed for this set of $n_j$ keys very soon, due to the 1/2 probability provided by Theorem 11.9.
Please also refer below answer for details:
https://cs.stackexchange.com/a/134386/123596.


Image Comparison tuned to Human Perception

Unfortunately there is not likely to be any good general algorithm for this.  Human perception is extremely complex.  The best you can do is find algorithms that will sometimes recognize two images as perceptually similar, but there will inevitably be some pairs of images that humans would classify as perceptually similar but your algorithm won't detect as similar.

Your best bet is probably to try to find out exactly what minor differences tend to be introduced by these particular platforms, and then try to devise an algorithm that is tuned to those particular kinds of differences -- you'll probably have better luck than that than with any general algorithm.

One very simple algorithm is to align the two images (e.g., using SIFT/SURF/etc.), add a bit of Gaussian blur to the two images, downscale, and then compare using a L2 norm.  Another simple algorithm is to align the two images with SIFT/SURF/etc., and then compute a metric based upon the number of inliers vs outliers in the feature points (how well the set of feature points from the first image match up with the set of feature points from the second image).  However, it's hard to know how well this will work for your particular application, without knowing the details of the differences that tend to arise in your situation.


In Agda's GADT, are "parameterized" and "indexed" different semantically?

The following explanation lacks mathematicial precision but should explain what is going on.

A GADT is a special case of a recursive type. A recursive type $T$ is a solution of a type equation of the form
$$T = \Phi(T).$$
(If this is not clear, please ask.)
Sometimes $\Phi$ depends on a parameter $p : P$ of some given type $P$, so we have a parameterized equation
$$T = \Phi(p, T).$$
Now the solution $T$ is not just a type, because it depends on $p$, so we get a dependent type $T : P \to \mathsf{Type}$ such that
$$T(p) = \Phi(p, T(p))$$
for all $p : P$.

We may also consider recursive equations in collections other than $\mathsf{Type}$. For example, an equation in $\mathsf{Type} \times \mathsf{Type}$ is a mutual recursive type
$$(T_1, T_2) = \Phi(T_1, T_2).$$
The types $T_1$ and $T_2$ can be arbitrarily entangled, i.e., there is no guarantee that we can separate the equation into two equations
$T_1 = \Phi_1(T_1)$ and $T_2 = \Phi_2(T_2)$. If we could separate like that, we would be back to the previous case of a parameterized fixed-point equation (the parameters ranging over $\{1, 2\}$).

We could similarly solve simultaneously for three, four, etc. types. In general, given any type $I$, we can solve an equation which is simultaneous in $I$-many types $T_i$, one for each index $i : I$, which gives us an indexed equation
$$(T_i)_{i : I} = \Phi((T_i)_{i : I}).$$
The above notation is a bit ugly and it would be better to write
$$T = \Phi(T)$$
where it is understood that the uknown $T$ is a dependent type $T : I \to \mathsf{Type}$ indexed by $I$. Again, there is no guarantee that we can disentangle the equation into $I$-many separate equations of the form $T_i = \Phi_i(T_i)$.

The two kinds of equations translate back to recursive and inductive type definitions. Let us write $\mathsf{rec}_U\,\Phi$ for the solution of a fixed-point equation $X = \Phi(X)$, where $X : U$ and $\Phi : U \to U$. We now have:

Given a map $\Phi : A \to \mathsf{Type} \to \mathsf{Type}$, the type family $R : A \to \mathsf{Type}$ given by
$$R = \lambda a : A \,.\, \mathsf{rec}_{\mathsf{Type}}\,(\lambda X : \mathsf{Type} \,.\, \Phi(a, X))$$
is a recursive type with a parameter $a : A$, as in the first case.
Given a map $\Psi : (A \to \mathsf{Type}) \to (A \to \mathsf{Type})$, the type family $Q : A \to \mathsf{Type}$ given by
$$Q = \mathsf{rec}_{A \to \mathsf{Type}}\,(\lambda F : A \to \mathsf{Type} \,.\, \Psi(F))$$
is a recursive type with index $a : A$, as in the second case.

It should be clear that $R$ and $Q$ are not the same thing. In $R$ we solve one fixed-point equation in $\mathsf{Type}$ for each parameter $a : A$, whereas in $Q$ we solve a single fixed-point equation in $A \to \mathsf{Type}$.
As a sanity check you should try to translate your examples to the above notation.

Lastly, the indexed recursive types are more general than the parametrized ones. Indeed,
$$R = \lambda a : A \,.\, \mathsf{rec}_{\mathsf{Type}}\,(\lambda X : \mathsf{Type} \,.\, \Phi(a, X))$$
can be written as
$$
R = \mathsf{rec}_{A \to \mathsf{Type}}\,(\lambda F : A \to \mathsf{Type} \,.\, \lambda a : A \,.\, \Phi(a, F(a))).
$$
In the other direction, an indexed recursive type $Q$ as above may be converted to a parameterized one precisely when $\Psi$ can be separated, which means that it has the form $\Psi(F) = \lambda a : A \,.\, \Psi'(a, F(a))$ for some $\Psi' : A \times \mathsf{Type} \to \mathsf{Type}$, in which case we have
$$Q = \lambda a : A \,.\, \mathsf{rec}_{\mathsf{Type}} (\lambda X \,.\ \Psi'(a, X )).$$


Can the shortest simple cycle between two given nodes be found in polynomial time?

The problem isn't NP-hard, one way to solve it is to treat the graph as a flow network where each edge has capacity $1$ and cost $1$, and set $s$ as the source and $t$ as the sink, if you find a minimum-cost flow of $2$, you have two edge-disjoint paths from $s$ to $t$ (just finding a flow of 2 or more gives disjoint paths - this is basically Menger's Theorem - the min-cost part will lead to shortest cycles).

Of course what we really want is vertex disjoint paths, rather than edge disjoint. If we treat the input graph $G$ as a digraph $D$, replacing each edge $uv$ with two edges $(u,v)$ and $(v,u)$, we can create a new graph $D'$ by splitting each vertex $v$ into $v_{1}$ and $v_{2}$ with the edge $(v_{1},v_{2})$ with cost zero, and any edge $(u,w)$ in $D$ becomes $(u_{2},w_{1})$ in $D'$. Then edges disjoint paths in $D'$ correspond to vertex disjoint paths in $D$ (and hence $G$).

Now we only need to solve the min-cost part. Suurballe & Tarjan (Networks 14(2), pp. 325–336, 1984) give an algorithm to do this with running time $O(m\log_{1+m/n}n)$ where $m$ is number of edges and $n$ the number of vertices, which is somwhere between $O(n^{2})$ and $O(n\log n)$, depending on how dense the graph is.

This may not be the fastest though: Bjorklund, Husfeldt & Taslaman (published at SODA '12, the linked version is a preprint) give a randomised FPT algorithm for finding the shortest cycle that includes a set of $k$ specified vertices, but in the introduction they also mention a (deterministic) linear time algorithm for $k=3$, which suggests $k=2$ should be quicker than the older algorithms suggest too.

What is NP-hard is finding long cycles (the  extreme case is Hamiltonian Cycle).


0-1 ILP formulated as:
Does there exist a vector $\mathbf{x}$, subject to constraints:
$$
  \left.\begin{array}{rrrrr|rr}
     a_{11} x_1 & + &a_{12} x_2 & ... + & a_{1n} x_n\le b_1 \\
     a_{21} x_1 & + &a_{22} x_2 & ... + & a_{2n} x_n\le b_2 \\
     ...\\
     a_{m1} x_1 & + &a_{m2} x_2 & ... + & a_{mn} x_n\le b_m \\
  \end{array}\right.
$$
Domain of x: $\forall_{x_j \in \mathbf{x}} x_j\in \{0,1\}$
Reduction to k-sat:
First reduce to circuit sat:

Start with the first row, create a boolean variable for representing each bit in $a_{1j}$ and one boolean variable for $x_j$. Then make variable for $b_1$. Make an addition circuit (pick your favorite) adding the row up.

Then make a comparison circuit, declaring the sum to less than $b_1$ (with a lightbulb that lights up if they are).

Convert these two circuits to CNF, filling in the $a_{1j}$ variables and $b_1$ since they are given.

Repeat for all rows, but reuse the $x_j$ variables between them.

Take all the comparison bulbs and AND them together to get a single lightbulb as output. The SAT problem would now be "what inputs for all $x_j$ will make this final ANDed lightbulb light up"

The final CNF will contain all the constraints.


Using a greedy algorithm to find a cut S which at least half of the edges cut

List the vertices in some order, $v_1,\ldots,v_n$. Put $v_1$ in an arbitrary side of the cut. For each of the vertices $v_2,\ldots,v_n$, put it in the side of the cut which maximized the number of edges cut (only counting edges involving vertices which have already been processed). Since there are only two sides, each time you cut at least half the edges.


In-place algorithm for interleaving an array

Here is the answer which elaborates upon the algorithm from the paper linked by Joe: http://arxiv.org/abs/0805.1598

First let us consider a $\Theta(n \log n)$ algorithm which uses divide and conquer.

1) Divide and Conquer

We are given

$$a_1, a_2, \dots , b_1, b_2, \dots b_n$$

Now to use divide and conquer, for some $m = \Theta(n)$, we try to get the array

$$ [a_1, a_2, \dots , a_m, b_1, b_2, \dots, b_m], [a_{m+1}, \dots, a_n, b_{m+1}, \dots b_n]$$

and recurse.

Notice that the portion $$ b_1 , b_2, \dots b_m, a_{m+1}, \dots a_n$$ is a cyclic shift of

$$ a_{m+1}, \dots a_n, b_1 , \dots b_m$$

by $m$ places.

This is a classic and can be done in-place by three reversals and in $\mathcal{O}(n)$ time.

Thus the divide and conquer gives you a $\Theta(n \log n)$ algorithm, with a recursion similar to $T(n) = 2T(n/2) + \Theta(n)$.

2) Permutation Cycles

Now, another approach to the problem is the consider the permutation as a set of disjoint cycles.

The permutation is given by (assuming starting at $1$)

$$ j \mapsto 2j \mod 2n+1$$

If we somehow knew exactly what the cycles were, using constant extra space, we could realize the permutation by picking an element $A$, determine where that element goes (using the above formula), put the element in the target location into temporary space, put the element $A$ into that target location and continue along the cycle. Once we are done with one cycle we move onto an element of the next cycle and follow that cycle and so on.

This would give us an $\mathcal{O}(n)$ time algorithm, but it assumes that we "somehow knew what the exact cycles were" and trying to do this book-keeping within the $\mathcal{O}(1)$ space limitation is what makes this problem hard.

This is where the paper uses number theory.

It can be shown that, in the case when $2n + 1 = 3^k$, the elements at positions $1$, $3, 3^2, \dots, 3^{k-1}$ are in different cycles and every cycle contains an element at the position $3^m, m \ge 0$.

This uses the fact that $2$ is a generator of $(\mathbb{Z}/3^k)^*$.

Thus when $2n+1 = 3^k$, the follow the cycle approach gives us an $\mathcal{O}(n)$ time algorithm, as for each cycle, we know exactly where to begin: powers of $3$ (including $1$) (those can be computed in $\mathcal{O}(1)$ space).

3) Final Algorithm

Now we combine the above two: Divide and Conquer + Permutation Cycles.

We do a divide and conquer, but pick $m$ so that $2m+1$ is a power of $3$ and $m = \Theta(n)$.

So instead on recursing on both "halves", we recurse on only one and do $\Theta(n)$ extra work.

This gives us the recurrence $T(n) = T(cn) + \Theta(n)$ (for some $0 \lt c \lt 1$) and thus gives us an $\mathcal{O}(n)$ time, $\mathcal{O}(1)$ space algorithm!


This is equivalent to an operation known as boolean convolution. See Models of Computation page 419 defn 9.6.3.

Dunne states (p5):

  Weiss 1984 and Blum 1984b obtained lower bounds for the n-point boolean convolution function which is closely related to integer multiplication.

Models of computation
Relationships between monotone and non-monotone network complexity, Dunne
Blum, N. (1984b) An $\Omega(n^{4/3})$ lower bound on the monotone network complexity of n-th degree convolution; Theoretical Computer Science, 36, 59-70


Proving the correctness of an algorithm, which computes the connectivity of a directed graph

Suppose that the algorithm is incorrect. We can slightly modify the algorithm by moving lines 8,12 just after the inner loop. If the algorithm returns $k$ incorrectly at the end of step $i$, then there must exist vertices $v_s,v_t$, for $s,t>i$, and a set $S$ of size $k-1$ not containing $v_s,v_t$, such that after removing $S$ there is no path from $v_s$ to $v_t$. I claim that $v_1,\ldots,v_i \in S$: if $v_j \notin S$ for some $j \leq i$, then since $S$ does not disconnect $v_j$ from any other vertex, we would have a path $v_s \to v_j \to v_t$. Since $v_1,\ldots,v_i \in S$, in particular $|S| \geq i$. Stated differently, $k-1 \geq i$. So if $i > k-1$, this is impossible.

My proof, if correct, shows that you can actually use the weaker condition $i > k-1$ in lines 8,12.


When is a root node an articulation point in a graph?

In the example above running DFS rooted at 0 the vector 0 will only have one tree link as the algorithm will follow the route: 0 -> 1 -> 2 -> 0
Since the edge 0-2 is considered a back link and not a tree link 0 is not considered an articulation point.


Optimal prefix code: full binary tree existence

You can formulate this proof in completely constructive terms. Starting with any prefix code, consider any node $v$ which has exactly one child $w$, and contract the edge $(v,w)$. Repeat this as long as no node has exactly one child. Since each operation decreases the number of nodes, we know that after finitely many iterations we reach a full binary tree.


Since $p$ and $p\to q$, we have $q$ by modus ponens.
Since $q$ and $r$, we have $q \land r$ by definition of conjunction.
Since $q \land r$ and $(q \land r) \to s$, we have $s$ by modus ponens.


Why multiple rotations might be needed after deletion in an AVL tree if after insertion there can be at most one needed?

Adding one element to a set, versus deleting one element from a set, are indeed rather symmetric operations. You are right.

However, in the case where the sets are represented by a tree, the two operations turn out to be asymmetric. When adding an item one branch may be too long, and one well-chosen rotation will rebalance. When deleting an item one branch may be too short, and the local rotation needed to rebalance will change the height of the current tree, so we may be forced to repeat rotating at other spots.

So it seems that "too long" and "too short" are not symmetric for tree rotations.

There are various other set representations that are not symmetric with adding and deleting.

We can keep sets as unordered arrays. Adding is easy, just put a new item at the end. Deleting is slightly harder. Assuming we have actually found the item, it is removed in the array, and then the last item is moved to the open spot.

We can also keep sets as hash-tables, with open adressing. Then adding has a standard solution, but deleting is hard, as doing it in the naive way may make other items untraceable (when we have a method other than linear probing).


Counting letter frequency in array in O(1) with hash function

The complexity is $O(n)$. What is $O(1)$ is the time it takes to access a cell in the hash table.
By the way, assuming that each character is a byte, you can just use a plain old array of length 256.


Can a public key be used to decrypt a message encrypted by the corresponding private key?

Q: If you pedal backwards on a fish, does it go backwards?
A: ???

A fish is not a bicycle. Similarly, you cannot use a private key to encrypt a message or a public key to decrypt a message. They don't have the right equipment.

With RSA, which is a popular public-key cryptosystem but not the only one, the private key and the public key have the same mathematical properties, so it is possible to use them interchangeably in the algorithms. (They don't have the same security properties, however — the public key is usually easily guessable from the private key.) You can take an RSA encryption algorithm and feed it a private key, or an RSA decryption algorithm and feed it a public key. However, the results are not meaningful according to standard algorithms.

This symmetry between public keys and private keys does not extend to most other public-key cryptosystems. In general, the public key isn't the right type of mathematical object to use for the decryption algorithm, and the private key isn't the right type of mathematical object to use for the encryption algorithm.

This being said, public-key cryptosystems are based on the concept of trapdoor functions. A one-way function is a function that is easy to compute, but whose inverse is hard to compute. A trapdoor function is like a one-way function, but there is a “magic” value that makes the inverse easy to compute.

If you have a trapdoor function, you can use it to make a public-key encryption algorithm: going forward (in the easy direction), the function encrypts; going backward (in the hard direction), the function decrypts. The magic value required to decrypt is the private key.

If you have a trapdoor function, you can also use it to make a digital signature algorithm: going backward (in the hard direction), the function signs; going forward (in the easy direction), the function verifies a signature. Once again, the magic value required to sign is the private key.

Trapdoor functions generally come in families; the data necessary to specify one particular element of the family is the public key.

Even though public-key encryption and digital signatures are based on the same concepts, they are not strictly identical. For example, the RSA trapdoor function is based on the difficulty of undoing a multiplication unless you already know one of the factors. There are two common families of public-key encryption schemes based on RSA, known as PKCS#1 v1.5 and OAEP. There are also two common families of digital signature schemes based on RSA, known as PKCS#1 v1.5 and PSS. The two “PKCS#1 v1.5” are of similar designs, but they are not identical. This answer by Thomas Pornin and this answer by Maarten Bodewes go into some details of the difference between signature/verification and decryption/encryption in the case of RSA.

Beware that some layman presentations of public-key cryptography masquerade digital signature and verification as decryption and encryption, for historical reasons: RSA was popularized first, and the core operation of RSA is symmetric. (The core operation of RSA, known as “textbook RSA”, is one of the steps in an RSA signature/verification/encryption/decryption algorithm, but it does not constitute in itself a signature, verification, encryption or decryption algorithm.) They are symmetric from the 10000-foot view, but they are not symmetric once you go into the details.

See also Reduction from signatures to encryption?, which explains that you can build an encryption scheme from a signature scheme, but only under certain conditions.


With 4 bits you can represent 16 different values: 0,1,...,15. If you want to allow negative exponents it makes sense to take (approximately) half of the possible values to mean a negative exponent. By adding 7 to the exponent you map the values -7,-6,...,0,1,...,8 to the representable range. You might also want to look up two's complement.


Why is push_back in C++ vectors constant amortized?

The important word here is "amortized". Amortized analysis is an analysis technique that examines a sequence of $n$ operations. If the whole sequence runs in $T(n)$ time, then each operation in the sequence runs in $T(n)/n$. The idea is that while a few operations in the sequence might be costly, they can't happen often enough to weigh down the program. It's important to note that this is different from average case analysis over some input distribution or randomized analysis. Amortized analysis established a worst case bound for the performance of an algorithm irrespective of the inputs. It's most commonly used to analyse data structures, which have a persistent state throughout the program.

One of the most common examples given is the analysis of a stack with a multipop operations that pops $k$ elements. A naive analysis of multipop would say that in the worst case multipop must take $O(n)$ time since it might have to pop off all the elements of the stack. However, if you look at a sequence of operations, you'll notice that the number of pops can not exceed the number of pushes. Thus over any sequence of $n$ operations the number of pops can't exceed $O(n)$, and so multipop runs in $O(1)$ amortized time even though occasionally a single call might take more time.

Now how does this relate to C++ vectors? Vectors are implemented with arrays so to increase the size of a vector you must reallocate memory and copy the whole array over. Obviously we wouldn't want to do this very often. So if you perform a push_back operation and the vector needs to allocate more space, it will increase the size by a factor $m$. Now this takes more memory, which you may not use in full, but the next few push_back operations all run in constant time.

Now if we do the amortized analysis of the push_back operation (which I found here) we'll find that it runs in constant amortized time. Suppose you have $n$ items and your multiplication factor is $m$. Then the number of relocations is roughly $\log_m(n)$. The $i$th reallocation will cost proportional to $m^i$, about the size of the current array. Thus the total time for $n$ push back is $\sum_{i=1}^{\log_m(n)}m^i \approx \frac{nm}{m-1}$, since it's a geometric series. Divide this by $n$ operations and we get that each operation takes $\frac{m}{m-1}$, a constant. Lastly you have to be careful about choosing your factor $m$. If it's too close to $1$ then this constant gets too large for practical applications, but if $m$ is too large, say 2, then you start wasting a lot of memory. The ideal growth rate varies by application, but I think some implementations use $1.5$.


Consistent theory based on L and not(A->A) is a theorem

I'll assume that we're working in the context of classical propositional logic.
The first thing to point out is that $\lnot(A \rightarrow A)$ leads to a contradiction: ($A \land \lnot A$). Since propositional logic itself is consistent, it is impossible to derive a contradiction, so $\vdash \lnot(A \rightarrow A)$ is impossible.
So perhaps your intention was $T \vdash \lnot(A \rightarrow A)$. This can only happen if $T$ is itself inconsistent.
Given that $T$ is inconsistent, $T$ is vacuously complete (since an inconsistent theory can prove any formula) and decidable (for the same reason). As for soundness, it's a property of the logical system, not any particular theory like $T$. Propositional logic is sound.


There is clearly no sublinear-time algorithm; any algorithm needs to look at all words in the input to have a hope of being correct.

There is a straightforward algorithm to construct a trie that recognizes these words in linear time.  The trie is a DFA, but not a minimal DFA.

The trie is acyclic, and apparently there are algorithms for minimizing an acyclic DFA in linear time, so this yields a linear-time algorithm to construct such a minimal DFA.  See for example

Johannes Bubenzer.  Minimization of Acyclic DFAs.  Proceedings of PSC 2011.


What is meant by 'simultaneously computing' all partial derivatives of an arithmetic circuit?

The new circuit will have multiple output gates, each one computing a different partial derivative. See for example Definition 2.1 and the ensuing proof in lecture notes of Wigderson.


Understanding when to count key comparisons

I'll answer some other question first: Why do we count key comparisons?

When analysing the runtime of an algorithm it can be tedious to count all the operations (even more so, if we notice they don't all take the same time). So it is convenient to identify those operations that dominate the runtime and only analyse those.

In the case of searching the dominant operation are key comparisons, in the case of sorting, they are key comparisons and swaps. Furthermore, most sorting algorithms will only swap elements that they have compared just prior. Thus the number of comparisons gives an upper bound for the number of swaps as well. So we can get away with counting the number of comparisons in order to get an idea of how the (worst-case) runtime of an algorithm behaves.

Now to your actual question:

If key comparisons are the dominant operation, e.g. in an algorithm that combines sorting and searching, then it is useful to count all key comparisons, if we want to get an idea of the runtime.

If, on the other hand the key comparisons are dominated by some other operation, then it might make more sense to count those other operations and not count any key comparisons.

Or the key comparisons are one of several operations, neither of which dominates the others, then we count all of those. Or in one part of the program key comparisons are dominant, while in another part they are not. Or ...


Why do we need a separate notation for П-types?

I think we just need to get some things straight here:

In the expression $\lambda a : \mathsf{type} . \lambda x : a . x$ the variable $a$ is bound (by the outer $\lambda$). The expressions $\lambda a : \mathsf{type} . \lambda x : a . x$ and $\lambda b : \mathsf{type} . \lambda x : b . x$ are $\alpha$-equal.
The expression $\lambda a : \mathsf{type} . \lambda x : a . x$ is the identity function, it is not the "signature of the identity function".
If by "signature of the identity function" you mean to say "the type of the identity function", then it would be something like $\Pi_{a : \mathsf{type}} . (a \to a)$, or if you want only product types, then it is $\Pi_{a : \mathsf{type}} \Pi_{x : a} a$.

Is there still a question?
Maybe this will help:

the type of the identity function $\lambda x : a . x$ is $a \to a$
the type of the identity function $\lambda y : b . y$ is $b \to b$
the functions $\lambda x : a . x$ and $\lambda y : b . y$ are different
the types $a \to a$ and $b \to b$ are different
the type of the polymorphic identity function $\lambda c : \mathsf{type} . \lambda z : c . z$ is $\Pi_{c : \mathsf{type}} . c \to c$.
the functions $\lambda a : \mathsf{type} . \lambda x : a . x$ and $\lambda c : \mathsf{type} . \lambda z : c . z$ are $\alpha$-equal
the types $\Pi_{a : \mathsf{type}} . a \to a$ and $\Pi_{c : \mathsf{type}} . c \to c$ are $\alpha$-equal.

Supplemental: After talking to Alex Simpson over a cup of tea, there is one more thing I can say. We don't need separate $\lambda$ and $\Pi$ constructors, as they both have precisely the same syntactic shape (take two arguments, bind one variable). In fact, if my memory serves me right, Automath used the same notation for $\lambda$-abstractions and $\Pi$-types. But the point is that we want to use two different constructors because they denote different concepts.


Why is there no permutation in Regexes? (Even if regular languages seem to be able to do this)

The fundamental theorems of formal language theory are that regular expressions, regular grammars, deterministic finite automata (DFAs) and nondeterministic finite automata (NFAs) all describe the same kinds of languages: namely the regular languages. The fact that we can describe these languages in so many completely different ways suggests that there's something natural and important about these languages, in the same way that the equivalence of Turing machines, the lambda calculus and all kinds of other things suggests that the computable languages are natural and important. They're not just an artifact of whatever random decisions the original discoverer made.

Suppose we add a new rule for creating regular expressions: if $R$ is a regular expression, then $\pi(R)$ is a regular expression, and it matches every permutation of every string matched by $R$. So, for example, $L(\pi(abc)) = \{abc, acb, bac, bca, cab, cba\}$. The problem is that this breaks the fundamental equivalences described above.  $L\big(\pi((ab)^*))\big)$ is the language of strings that contain an equal number of $a$s and $b$s and this isn't a regular language. Compare this with, for example, adding a negation or reversal operator to regular expressions, which doesn't change the class of languages that are accepted.

So, to answer the title question, regular expressions can't do permutations and we don't add that ability because then regular expressions wouldn't match regular languages. Having said that, it's possible that "regular expressions with permutations" would also be an interesting class of languages with lots of different characterizations.


For any language $L$, $$\emptyset⋅L=\emptyset$$.

Therefore,
$$L_1\cdot L_2^* = \emptyset \cdot L_2^* = \emptyset$$

And thus $$L_1\cdot L_2^*\cup L_1^* = \emptyset \cup L_1^*= L_1^* = \{\epsilon\}$$.


Why is this expression (A and ¬A |= C) entailed?

The statement $X\vDash Y$ means "every assignment to the variables that makes $X$ true also makes $Y$ true." Or to put it another way, "There is no assignment of variables that makes $X$ true but fails to make $Y$ true." Well, there's no assignment of variables that makes $A\land\neg A$ true, so there's certianly no assignment that makes $A\land\neg A$ true and also makes $C$ false.  So $A\land\neg A\vDash C$ is a true statement.

False entails anything is a rule, analogous to false implies anything.


Can a machine choose whether or not to accept a state in a FSM

The diagram appears to be of a Nondeterministic finite automaton, or NFA. A NFA is a model of a theoretical machine that accepts a given string if any path through the NFA for that string can end up at an accepting node.

So the simple answer to the question in the title is "yes, if you're talking about NFAs". (As opposed to Deterministic finite automata, or DFAs, which must have a unique outgoing edge for each character at a given node)

One traditional way to write a program to check if a string is accepted by an NFA is to keep track of all the states that the machine could be in after seeing a particular character, and then at the end declare that the string is accepted if one of the states we could be in now is an accepting state.

For example, consider the input string abbbbb.

At the start, the machine can only be in state $S_0$, so the set of states it can be in is $\{S_0\}$.

After a, the machine can now only be in $S_1$, so $\{S_1\}$.

After ab, the machine could be in $S_1$ or it could be in $S_3$, so $\{S_1, S_3\}$.

After abb, the machine's set of possible states is $\{S_1, S_2, S_3\}$.

After abbb, the machine's set of possible states is $\{S_1, S_2, S_3\}$.

After abbbb, the machine's set of possible states is $\{S_1, S_2, S_3\}$. You should see a pattern by now.

And in fact, at the end of the whole input string abbbbb, the machine's set of possible states is $\{S_1, S_2, S_3\}$, and that contains an accepting state ($S_3$), so the string is accepted.

The regular expression should now be easily readable from the machine: ab*(a|b)


How to describe algorithms, prove and analyse them?

There is a huge variety of feasible approaches. Which is best suited depends on

what you are trying to show,
how much detail you want or need.

If the algorithm is a widely known one which you use as a subroutine, you often remain at a higher level. If the algorithm is the main object under investigation, you probably want to be more detailed. The same can be said for analyses: if you need a rough upper runtime bound you proceed differently from when you want precise counts of statements.

I will give you three examples for the well-known algorithm Mergesort which hopefully illustrate this.

High Level

The algorithm Mergesort takes a list, splits it in two (about) equally long parts, recurses on those partial lists and merges the (sorted) results so that
the end-result is sorted. On singleton or empty lists, it returns the input.

This algorithm is obviously a correct sorting algorithm. Splitting the list and merging it can each be implemented in time $\Theta(n)$, which gives us a recurrence for worst case runtime $T(n) = 2T\left(\frac{n}{2}\right) + \Theta(n)$. By the Master theorem, this evaluates to $T(n) \in \Theta(n\log n)$.

Medium Level

The algorithm Mergesort is given by the following pseudo-code:

procedure mergesort(l : List) {
  if ( l.length < 2 ) {
    return l
  }

  left  = mergesort(l.take(l.length / 2)
  right = mergesort(l.drop(l.length / 2)
  result = []

  while ( left.length > 0 || right.length > 0 ) {
    if ( right.length == 0 || (left.length > 0 && left.head <= right.head) ) {
      result = left.head :: result
      left = left.tail
    }
    else {
      result = right.head :: result
      right = right.tail
    }
  }

  return result.reverse
}

We prove correctness by induction. For lists of length zero or one, the algorithm is trivially correct. As induction hypothesis, assume mergesort performs correctly on lists of length at most $n$ for some arbitrary, but fixed natural $n>1$. Now let $L$ be a list of length $n+1$. By induction hypothesis, left and right hold (non-decreasingly) sorted versions of the first resp. second half of $L$ after the recursive calls. Therefore, the while loop selects in every iteration the smallest element not yet investigated and appends it to result; thus result is a non-increasingly sorted list containing all elements from left and right. The reverse is a non-decreasingly sorted version of $L$, which is the returned -- and desired -- result.

As for runtime, let us count element comparisons and list operations (which dominate the runtime asymptotically). Lists of length less than two cause neither. For lists of length $n>1$, we have those operations caused by preparing the inputs for the recursive calls, those from the recursive calls themselves plus the while loop and one reverse. Both recursive parameters can be computed with at most $n$ list operations each. The while loop is executed exactly $n$ times and every iteration causes at most one element comparison and exactly two list operations. The final reverse can be implemented to use $2n$ list operations -- every element is removed from the input and put into the output list. Therefore, the operation count fulfills the following recurrence:

$\qquad \begin{align}T(0) = T(1) &= 0 \\
T(n) &\leq T\left(\left\lceil\frac{n}{2}\right\rceil\right) + T\left(\left\lfloor\frac{n}{2}\right\rfloor\right) + 7n\end{align}$

As $T$ is clearly non-decreasing, it is sufficient to consider $n=2^k$ for asymptotic growth. In this case, the recurrence simplifies to

$\qquad \begin{align}T(0) = T(1) &= 0 \\
T(n) &\leq 2T\left(\frac{n}{2}\right) + 7n\end{align}$

By the Master theorem, we get $T \in \Theta(n \log n)$ which extends to the runtime of mergesort.

Ultra-low level

Consider this (generalised) implementation of Mergesort in Isabelle/HOL:

types dataset  =  "nat * string"

fun leq :: "dataset \<Rightarrow> dataset \<Rightarrow> bool" where
   "leq (kx::nat, dx) (ky, dy) = (kx \<le> ky)"

fun merge :: "dataset list \<Rightarrow> dataset list \<Rightarrow> dataset list" where
"merge [] b = b" |
"merge a [] = a" |
"merge (a # as) (b # bs) = (if leq a b then a # merge as (b # bs) else b # merge (a # as) bs)"

function (sequential) msort :: "dataset list \<Rightarrow> dataset list" where
  "msort []  = []" |
  "msort [x] = [x]" |
  "msort l   = (let mid = length l div 2 in merge (msort (take mid l)) (msort (drop mid l)))"
by pat_completeness auto
  termination
  apply (relation "measure length")
by simp+

This already includes proofs of well-definedness and termination. Find an (almost) complete correctness proof here.

For the "runtime", that is number of comparisons, a recurrence similar to the one in the prior section can be set up. Instead of using the Master theorem and forgetting the constants, you can also analyse it to get an approximation that is asymptotically equal the true quantity. You can find the full analysis in [1]; here is a rough outline (it does not necessarily fit the Isabelle/HOL code):

As above, the recurrence for the number of comparisons is

$\qquad \begin{align}f_0 = f_1 &= 0 \\
f_n &= f_{\left\lceil\frac{n}{2}\right\rceil} + f_{\left\lfloor\frac{n}{2}\right\rfloor} + e_n\end{align}$

where $e_n$ is the number of comparisons needed for merging the partial results². In order to get rid of the floors and ceils, we perform a case distinction over whether $n$ is even:

$\qquad \displaystyle \begin{cases}
f_{2m}   &= 2f_m + e_{2m} \\
f_{2m+1} &= f_m + f_{m+1} + e_{2m+1}
  \end{cases}$

Using nested forward/backward differences of $f_n$ and $e_n$ we get that

$\qquad \displaystyle \sum\limits_{k=1}^{n-1} (n-k) \cdot \Delta\kern-.2em\nabla f_k = f_n - nf_1$.

The sum matches the right-hand side of Perron's formula. We define the Dirichlet generating series of $\Delta\kern-.2em\nabla f_k$ as

$\qquad \displaystyle W(s) = \sum\limits_{k\geq 1} \Delta\kern-.2em\nabla f_k k^{-s} = \frac{1}{1-2^{-s}} \cdot \underbrace{\sum\limits_{k \geq 1} \frac{\Delta\kern-.2em\nabla e_k}{k^s}}_{=:\ \boxminus(s)}$

which together with Perron's formula leads us to

$\qquad \displaystyle f_n = nf_1 + \frac{n}{2\pi i} \int\limits_{3-i\infty}^{3+i\infty} \frac{\boxminus(s)n^s}{(1-2^{-s})s(s+1)}ds$.

Evaluation of $\boxminus(s)$ depends on which case is analysed. Other than that, we can -- after some trickery -- apply the residue theorem to get

$\qquad \displaystyle f_n \sim n \cdot \log_2(n) + n \cdot A(\log_2(n)) + 1$

where $A$ is a periodic function with values in $[-1,-0.9]$.

Mellin transforms and asymptotics: the mergesort recurrence by Flajolet and Golin (1992)
Best case: $e_n = \left\lfloor\frac{n}{2}\right\rfloor$
Worst case: $e_n = n-1$
Average case: $e_n = n - \frac{\left\lfloor\frac{n}{2}\right\rfloor}{\left\lceil\frac{n}{2}\right\rceil + 1} - \frac{\left\lceil\frac{n}{2}\right\rceil}{\left\lfloor\frac{n}{2}\right\rfloor + 1}$


is there a sorting algorithm of order $\log n!$

By Stirling's approximation, $$\log(n!) = n\log n - n + O(\log n) = \Theta(n\log n)\,,$$
so, yes, there are lots of sorting algorithms that run in time $O(\log(n!))$.