What if the electricity goes off while a file is being renamed?

Most filesystems and filesystem implementations are designed to be resistant to a loss of power. When you rename a file, with most operating systems, you can expect to always see the file either under its old name or under its new name. If there is any intermediate stage where the file is so to speak half-renamed, the operating system will hide it from you, even if the machine crashes at a bad time. Renaming a file (with most filesystems) is an atomic operation.

The precise method for ensuring atomicity varies from filesystem to filesystem and may also depend on other system components such as the storage hardware and the disk driver. In this answer I'll describe some common techniques at a high level. If you look at an actual filesystem implementation, you're likely to find that things are a lot more complicated.

Most storage media guarantees that writes are atomic at the level of a block. A typical block size is 512 bytes. This is often guaranteed by the disk firmware. Here are some common techniques for noticing or preventing data corruption due to a power failure:

One possibility to protect against power failures is to have a small power reserve that is sufficient to complete the writing of the current block.
Another method is that the disk stores the block content followed by a checksum of the block: if the new content of the block is only half-written, the checksum will be wrong, and the block content is lost but the operating system will not re-read bad data.
A third method is to maintain a dirty bit: flip it from 0 to 1, do the actual write, then flip the bit back to 0, so that if the dirty bit is 0 then the block content is known to be good.

Let's assume for a moment that the file name is stored entirely within one block. Then what the filesystem driver needs to do to rename the file is to update that block with the new name.

If the storage medium guarantees that block writes are atomic, then the filesystem driver simply writes the new block content. If the write goes through, the file will have its new name; if a power failure happens, the file will retain its old name, meaning that the power failure effectively happened before the instruction to rename the file was carried out.
If writing a block may damage it, the filesystem driver creates a new block with the new name. Once that block has been successfully created, the filesystem driver updates the “parent” block that contains the location of the block containing the name to reflect the new location. The location of the parent block must be updated in its parent and so on.
Such a chain has to stop somewhere. One way to stop is to have a block with two possible locations L1 and L2. Maintain a version number for the block, stored inside the block. Increment the version number each time the block is written. At any time, whichever of L1 and L2 has the highest version number is the real location.

In general renaming a file may involve rewriting several blocks. The filesystem must take care in which order these blocks are written. For efficiency, it is often useful to reorder writes. This is often a consequence of caching and buffering: blocks are not actually written to disk each time they are modified, but kept in memory for a little time in case they are modified again. Another reason to reorder writes is that it's more efficient to group consecutive writes together (write block 42 then 43 then 44, even though 43 was modified first, then 42 then 44). The management of this reordering is a very complex part of typical filesystems, because it is very important for both correctness and performance.

One method that is used by many modern filesystems is journaling (in the database world, this is called a log). In addition to the actual data blocks, the filesystem maintains a list of operations that it performs. These operations are stored in strict chronological order. The journal consists of a list of records such as “rename the file from oldname to newname, affecting blocks B1, B2 and B3”. If a power failure interrupts the writing of a journal record, the operation hasn't taken place. The information in the journal duplicates the data which is written as performance permits. If the data isn't written at its final location due to a power failure, the operating system performs a journal replay at boot time: it reads the journal entries, checks whether each operation has taken place and performs the operation if necessary. The operating system also periodically marks journal entries as completed once it knows that the data has been successfully written. In many filesystems, this allows old journal entries to be erased, so that the journal keeps to a fixed size. There are even filesystems that consist solely of a journal, so that a file is defined by pointers to older journal entries that write its contents — this isn't very common though.


Resolution exponential lower bound... alternative proofs?

If you don't like the presentation of Arora and Barak, you can always take a look at Haken's original paper.

The modern approach to Resolution lower bounds is, however, via Resolution width, as worked out in a classical paper of Ben-Sasson and Wigderson. You can also find expositions in various lecture notes, for example by Jakob Nordström.


Proving a sorting operation in type system

Yes, it is possible to express a precise type for a sorting routine, such that any function having that type must indeed sort the input list.

While there might be a more advanced and elegant solution, I'll sketch an elementary one, only.

We will use a Coq-like notation. We start by defining a predicate requiring that f: nat -> nat acts as a permutation on $0..n-1$:

Definition permutation (n: nat) (f: nat -> nat): Prop :=
  (* once restricted, its codomain is 0..n-1 *)
  (forall m, m < n -> f m < n) /\
  (* it is injective, hence surjective *)
  (forall m1 m2, m1 < n -> m2 < n -> f m1 = f m2 -> m1 = m2) .

A simple lemma can easily be proved.

Lemma lem1: forall n f, permutation n f -> m < n -> f m < n.
... (* from the def *)

We define what is the $m$th element of a list having length $n$. This function requires a proof h stating that $m<n$ indeed holds.

Definition nth {A} {n} (l: list A n) m (h : m < n): A :=
... (* recursion over n *)

Given an ordering on A, we can express that a list is sorted:

Definition ordering (A: Type) :=
   { leq: A->A->bool |
     (* axioms for ordering *)
     (forall a, leq a a = true) /\
     (forall a b c, leq a b = true -> leq b c = true -> leq a c = true) /\
     (forall a b, leq a b = true -> leq b a = true -> a = b)
    } .

Definition sorted {A} {n} (o: ordering A) (l: list A n): Prop :=
...

Finally here's the type for a sorting algorithm:

Definition mysort (A: Type) (o: ordering A) (n: nat) (l: list A n):
   {s: list A n | sorted o s /\
                  exists f (p: permutation n f),
                  forall (m: nat) (h: m < n),
                     nth l m h = nth s (f m) (lem1 n f p h) } :=
... (* the sorting algorithm, and a certificate for its output *)

The output type states that the result list s is $n$ elements long, it is sorted, and that there's a permutation of $0..n-1$ that maps the elements in the input list l to the ones in the output list s. Note that we have to invoke the lemma above to prove $f(m) < n$, which is required by nth.

Note however that it is the user, i.e. the programmer, which has to prove their sorting algorithm correct. The compiler will not simply verify that the sorting is correct: all it does is checking a provided proof. Indeed, the compiler can not do much more than that: semantic properties such as "this program is a sorting algorithm" are undecidable (by Rice theorem), so we can not hope to make the proving step fully automatic.

In the far, far future, we can still hope that automatic theorem provers get so smart that "most" practically used algorithms can be automatically proved correct. The Rice theorem only states that this can not be done in all cases. All we can hope for is a correct, widely applicable, but inherently incomplete system.

As a final note, it is sometimes forgotten that even simple type systems are incomplete! E.g. even in Java

int f(int x) {
   if (x+2 != 2+x)
      return "Houston, we have a problem!";
   return 42;
}

is semantically type safe (it always returns an integer), but the type checker will complain about the unreachable return.


In Operating Systems, I can't understand why deadlock happens, why does a process not let go of a resource when it is done using it?

To answer part of your question: Processes are not smart. Processes just execute the code of their program, so if the program of P1 has not been written to release R1 when it's done with it, it won't be released.
Besides, the classical setting in which a deadlock happens does not have to do with processes not releasing resources after they are done with them, but rather with competing processes trying to acquire the needed resources.
Process A needs both R1 and R2 to perform some task, so it starts acquiring them. It acquires R1, and tries to acquire R2.
Just before P1 gets to acquire R1, some process P2 that also needs both R1 and R2 tries to acquire them. This time P2 starts with acquiring R2, and succeeds.
At this point the following two things happen:

P1 tries to acquire R2 which is unavailable, so it waits for R2 be released.
P2 tries to acquire R1 which is unavailable, so it waits for R1 be released.

From this point on both P1 and P2 are stuck waiting for another resource that will never be released, i.e., they are in a deadlock.
Notice that no process ever held a lock on a resource that didn't intend to use.
The problem was that P1 and P2 tried to lock the resources in a different order.
Finally, you might think that when P1 tries to acquire R2, and finds that it is unavailable it could just temporarily release R1 and try to acquire both R1 and R2 at a later time.
However, without additional synchronization, this also doesn't ensure that P1 and P2 will manage to acquire the needed resources. The following could happen:

P1 acquires R1, P2 acquires R2.
P1 tries to acquire R2, and finds that R2 is unavailable.
P2 tries to acquire R1, and finds that R1 is unavailable.
P1 releases R1.
P2 releases R2.
P1 acquires R1 and is about to acquire R2.
P2 acquires R2 and is about to acquire R1.
P1 tries to acquire R2, and finds that R2 is unavailable.
P2 tries to acquire R1, and finds that R1 is unavailable.
....


Is there a non-trivial type which is equal to its own derivative?

Consider the finite multisets $\mathbf{Bag}\:X$. Its elements are given by $\{x_1,\ldots,x_n\}$ quotiented by permutations, so that $\{x_1,\ldots,x_n\}=\{x_{\pi 1},\ldots,x_{\pi n}\}$ for any $\pi\in\mathbf{S}_n$. What is a one-hole context for an element in such a thing? Well, we must have had $n>0$ to select a position for the hole, so we are left with the remaining $n-1$ elements, but we are none the wiser about which is where. (That's unlike lists, where choosing a position for the hole cuts one list into two sections, and the second derivative cuts selects one of those sections and cuts it further, like "point" and "mark" in an editor, but I digress.) A one-hole context in a $\mathbf{Bag}\:X$ is thus a $\mathbf{Bag}\:X$, and every $\mathbf{Bag}\:X$ can arise as such. Thinking spatially, the derivative of $\mathbf{Bag}\:X$ ought to be itself.

Now,

$$\mathbf{Bag}\:X = \sum\limits_{n\in\mathbb{N}}X^n/\mathbf{S}_n$$

a choice of tuple size $n$, with a tuple of $n$ elements up to a permutation group of order $n!$, giving us exactly the power series expansion of $e^x$.

Naively, we can characterize container types by a set of shapes $S$ and a shape-dependent family of positions $P$:
$$\sum\limits_{s:S}X^{(P\,s)}$$
so that a container is given by a choice of shape and a map from positions to elements. With bags and the like, there's an extra twist.

The "shape" of a bag is some $n\in\mathbb{N}$; the "positions" are $\{1,\ldots,n\}$, the finite set of size $n$, but the map from positions to elements must be invariant under permutations from $\mathbf{S}_n$. There should be no way to access a bag that "detects" the arrangement of its elements.

The East Midlands Container Consortium wrote about such structures in Constructing Polymorphic Programs with Quotient Types, for Mathematics of Program Construction 2004. Quotient containers extend our usual analysis of structures by "shapes" and "positions" by allowing an automorphism group to act on the positions, allowing us to consider structures such as unordered pairs $X^2/2$, with derivative $X$. An unordered $n$-tuple is given by $X^n/n!$, and its derivative (when $n>0$ is an unordered $n-1$ tuple). Bags take the sum of these. We can play similar games with cyclic $n$-tuples, $X^n/n$, where choosing a position for the hole nails the rotation to one spot, leaving $X^{n-1}$, a tuple one smaller with no permutation.

"Type division" is hard to make sense of in general, but quotienting by permutation groups (as in combinatorial species) does make sense, and is fun to play with. (Exercise: formulate a structural induction principle for unordered pairs of numbers, $\mathbb{N}^2/2$, and use it to implement addition and multiplication so that they're commutative by construction.)

The "shapes-and-positions" characterization of containers imposes finiteness on neither. Combinatorial species tend to organised by size, rather than shape, which amounts to collecting terms in and computing the coefficient for each exponent. Quotient-containers-with-finite-position-sets and combinatorial species are basically different spins on the same substance.


Hint: Suppose that $T(m) \leq Cm$ for all $m < n$, and that $n$ is divisible by $3$. Then
$$ T(n) = T(n/3) + T(2n/3) \leq C(n/3) + C(2n/3) = Cn. $$
Use this to obtain a good bound on $T(n)$ when $n$ is a power of $3$.


Defining the halting problem for non-deterministic automata

There are a few reasons I think we put less effort into  the Halting problem for non-deterministic models.

The first is that there are, in fact, two relevant halting problems for a ND model. Given an input $x$ and a non-deterministic machine $M$:

Does there exist a valid run of $M$ on $x$ which halts?
Does there exist a valid run of $M$ on $x$ which doesn't halt? i.e. do all valid runs halt?

For deterministic machines, these are identical, since there is exactly one valid run of $M$ on an input $x$. But for non-deterministic machines, there might be multiple runs. Which one you're interested in depends on your application.

Secondly, non-deterministic models are already unrealistic: they assume that you either have a magical box telling you which path to take, or that you have some form of infinite parallelism. Since non-deterministic and deterministic Turing Machines are equivalent in power, in most cases you just convert the machine into a determinstic one before you worry about halting.

As an extension of this, we don't care because proving something about a non-deterministic machine is at least as hard as proving something about an equivalent deterministic machine. We already know that there's no solution to the deterministic Halting Problem, so all it's really useful for is proving other problems undecidable through reductions. And it's always going to be less work to reduce to the deterministic halting problem, since it's easier than it's non-deterministic counterpart.


What is the level of the material contained in the book Data Structures and Algorithm Analysis in C++ (4th Ed) by Weiss?

Once I skimmed through a dozen of textbooks, looking for ones better explaining sorting and data structures (i.e. no graphs, string algos and so on).

Weiss was the best one according to my criteria. In particular, it describes more advanced techniques for hash tables, which are heart of most real use cases. Although even this book doesn't include Robin Hood hashing - learn it from Wikipedia pointers.

More info: https://www.quora.com/How-do-I-learn-data-structure-and-algorithm-in-C++-I-know-the-basics-by-myself-Can-you-suggest-any-e-books-for-me-to-use/answer/Bulat-Ziganshin

Another extremely important topic: https://www.quora.com/What-are-good-resources-to-learn-concurrent-programming-in-C++/answer/Bulat-Ziganshin


Why will the Hindley-Milner algorithm never yield a type like t1 -> t2?

In the lambda calculus with no constants with the Hindley-Milner type system, you cannot get any such types where the result of a function is an unresolved type variable. All type variables have to have an “origin” somewhere. For example, the there is no term of type $\forall \alpha,\beta.\; \alpha\mathbin\rightarrow\beta$, but there is a term of type $\forall \alpha.\; \alpha\mathbin\rightarrow\alpha$ (the identity function $\lambda x.x$).

Intuitively, a term of type $\forall \alpha,\beta.\; \alpha\mathbin\rightarrow\beta$ requires being able to build an expression of type $\beta$ from thin air. It is easy to see that there is no value which has such a type. More precisely, if the type variable $\beta$ does not appear in the type of any term variable in the environment, then there is no term of type $\beta$ which is in head normal form. You can prove this by structural induction on the term: either the variable at the head would have to have the type $\beta$, or one of the arguments would have to have a principal type involving $\beta$, i.e. there would be a smaller suitable term.

Just because there is no value of a certain type doesn't mean that there is no term of that type: there could be a term with no value, i.e. a non-terminating term (precisely speaking, a term with no normal form). The reason why there is no lambda term with such types is that all well-typed HM terms are strongly normalizing. This is a generalization of the result that states that simply typed lambda calculus is strongly normalizing. It is a consequence of the fact that System F is strongly normalizing: System F is like HM, but allows type quantifiers everywhere in types, not just at the toplevel. For example, in System F, $\Delta = \lambda x. x \, x$ has the type $(\forall \alpha. \alpha) \rightarrow (\forall \alpha. \alpha)$ — but $\Delta\,\Delta$ is not well-typed.

HM and System F are examples of type systems that have a Curry-Howard correspondence: well-typed terms correspond to proofs in a certain logic, and types correspond to formula. If a type system corresponds to a consistent theory, then that theory does not allow proving theorems such as $\forall A, \forall B, A \Rightarrow B$; therefore there is no term of the corresponding type $\forall \alpha,\beta.\; \alpha\mathbin\rightarrow\beta$. The type system allows one to deduce “theorems for free” about functions over data structures.

This result breaks down as soon as you add certain constants to the calculus. For example, if you allow a general fixpoint combinator such as $Y$, it is possible to build terms of arbitrary type: $Y (\lambda x.x)$ has the type $\forall \alpha. \alpha$. The equivalent of a general fixpoint combinator in the Curry-Howard correspondence is an axiom that states $\forall A, \forall B, A \Rightarrow B$, which makes the logic obviously unsound.

Finding the fine line between type systems that ensure strong normalization and type systems that don't is a difficult and interesting problem. It is an important problem because it determines which logics are sound, in other words which programs embody proofs of theorems. You can go a lot further than System F, but the rules become more complex. For example, the calculus of inductive constructions which is the basis of the Coq proof assistant, is strongly normalizing yet is capable of describing common inductive data structures and algorithms over them, and more.

As soon as you get to real programming languages, the correspondence breaks down. Real programming languages have features such as general recursive functions (which may not terminate), exceptions (an expression that always raises an exception never returns a value and hence can have any type in most type systems), recursive types (which allow non-termination to sneak in), etc.


Try the following algorithm:

For $1 \leq i \leq m$: $C[A[i]] = 0$
For $1 \leq i \leq m$: $C[B[i]] = 1$
Initialize answer to $0$
For $1 \leq i \leq m$:

If $C[A[i]] = 1$ then $C[A[i]] = 2$ and increment answer

Return answer


Name for type of actions that only care for outcome

This doesn't actually answer the question but it fits to be an answer.
What I looked for is idempotent (when I asked this question I was actually looking for this word, but failed to express myself properly).
The definition is quite different from the question asked here:

  In computing, an idempotent operation is one that has no additional
  effect if it is called more than once with the same input parameters.
  For example, removing an item from a set can be considered an
  idempotent operation on the set.

But indeed, any operation that is idempotent will meet the question criteria.


How do I prove that a language is regular?

Here's a hint. Since $L$ is regular, there is a finite automaton $M$ that accepts all and only those strings in $L$. Suppose you only wanted those substrings that start with the same character as a string in $L$. Could you somehow modify $M$ (perhaps by making some states final) so that it would accept all substrings starting with the same character as a string accepted by $L$?

Having done that, could extend this (perhaps with $\epsilon$-moves) so that you could jump from the start state of $M$ to a string along an accepting path in $M$?


Does a pushdown automata exists for the following language?

Your languages are still not context-free.

A string homomorphism is a function $f\colon \Sigma \to \Sigma^*$ that replaces each character in a string with a (possibly empty) string over the same alphabet.  For a string $w=w_1\dots w_\ell$, we define $f(w)= f(w_1)\cdots f(w_\ell)$.  Context-free languages are closed under string homomorphisms.  That is, if a language $X$ is context free, so is the language $\{f(w)\mid w\in X\}$ for any string homomorphism $f$.

So, suppose that either of your languages were context-free, and consider the homomorphism defined by $f(a)=a$, $f(b)=b$, $f(c)=c$, $f(d)=\varepsilon$. We have $f(L_1)=\{a^nb^nc^{2n}\mid n\geq 0\}$ and $f(L_2) = \{a^nb^{2n}c^n\mid n\geq 0\}$. Neither of these is context free, which contradicts the assumption that $L_1$ and $L_2$ are context-free.

Also "a mixture" is not a well-defined context-free operation. In general, you should be suspicious of arguments where the main step is just some hand-wave along the lines of "And, yeah, then surely we can just combine them." If it's easy to explain how to "just combine them", then the argument can easily state that; if it's not easy to explain how, then it certainly needs to be explained!


I think there's a misconception.  DFA by themselves don't return anything.  A DFA is a mathematical model.  You can interpret the current state of the DFA when it hits an accept state as containing a result, but that's an interpretation you are making that's not part of the mathematical notion of a DFA.  Alternatively, you can consider a Moore machine or Mealy machine, which are mathematical models that do produce output; you can think of them as like a DFA but with an extension to allow them to produce output.


Right equivalent elements arising in the proof of the Schützenberger Theorem

As suggested by J.-E. Pin in the comments, this claim is wrong in the general case. To prove this statement a counter-example shall be constructed, but this will be done by a Haskell-program (at the bottom of this answer). But first I want to explain what it should do.
The program looks onto a special kind of maps that map Maybe [-2,-1,0,1,-2] to itself. It suffices to look at maps that only go from [-2,...,2] to Maybe [-2,...,2]. The set of maps that this program looks at is even more limited, because it shall only be those maps, that can be generated by a and b only. The function calculateAll should calculate the all the elements in the monoid generated by these two functions and the identity (this is a rather large monoid with 56 Elements). isAperiodic does what the name suggests, but it does not fail, therefore it is unsafe. Next this program can calculate all the "interesting" candidates, that are those elements of the monoid, whose principal right ideal does not equal the whole monoid and not the principal two-sided ideal. This is done by getCandidates. Then testForOneCandidate generates all the counterexamples for the claim for a fixed element $m$, where only completion with the letter $a$ is considered. This is done as follows:
An element in $m''$, which does not lie in $mM$, but $m''\ast a  \in mM$, is in $M''$. For such an element one only needs to test if $m'' M \neq  mM$. This is what testForOneCandidate does. Retranslating the first result of the call testForOneCandidate (head getCandidates) into potencies of a and b one gets the following in ghci testable counter-example (after loading the code):

*Main> let ba = b `mappend` a
*Main> ba `elem` rightPrincipalIdeal a
False
*Main> let ba2 = ba `mappend` a
*Main> ba2 `elem` rightPrincipalIdeal a
True
*Main> (fromList $ rightPrincipalIdeal ba2) < (fromList
    $ rightPrincipalIdeal a)
True

That is a rather complicated example, but I'm sure that there are simpler ones, it's just the first that I encountered.

Here is the code:

import Data.List (nub,(\\))
import Data.Set (fromList)

data Element = Element (Int -> Maybe Int)

instance Show Element where
  show (Element f) = show (map f [-2..2])

instance Eq Element where
  (==) (Element f) (Element g) = (map f [-2..2]) == (map g [-2..2])

instance Ord Element where
  (<=) (Element f) (Element g) = (map f [-2..2]) <= (map g [-2..2])

instance Monoid Element where
  mempty = Element dropOutside
  mappend (Element f) (Element g) = Element $ \i -> ((f i) >>= g)

-- Helper function
dropOutside :: Int -> Maybe Int
dropOutside i
  | abs (i) <= 2 = Just i
  | otherwise = Nothing

-- First elements that "generate" the monoid
a :: Element
a = Element $ \i -> dropOutside (i+1)

b :: Element
b = Element $ \i -> dropOutside (i-1)

nullElement :: Element
nullElement = Element $ \_ -> Nothing

-- Generates the monoid by the neutral element, a and b.
calculateAll :: [Element]
calculateAll =
  let
      calculateAllRec :: [Element] -> [Element]
      calculateAllRec acc =
          let
              newEs = nub [z| x <- acc, y <- acc,let z = x `mappend` y,z `notElem` acc]
          in case newEs of
               [] -> acc
               _ -> calculateAllRec (acc ++ newEs)
in calculateAllRec [mempty,a,b]

-- Checks whether a given element is aperiodic. (Unsafe)
isAperiodicElement :: Element -> Bool
isAperiodicElement x = isApElRec x x where
  isApElRec x' y'
      | y' == (x' `mappend` y') = True
      | otherwise = isApElRec x' (x' `mappend` y')

-- Checks if the whole monoid is aperiodic. (Unsafe)
isAperiodic :: Bool
isAperiodic = all isAperiodicElement calculateAll

-- Calculates the right ideal generated by a given element.
rightPrincipalIdeal :: Element -> [Element]
rightPrincipalIdeal x = nub [x `mappend` y | y <- calculateAll]

-- Calculates the twosided ideal generated by a given element.
twoSidedPrincipalIdeal :: Element -> [Element]
twoSidedPrincipalIdeal x = nub [z `mappend` x `mappend` y | z <- calculateAll , y <- calculateAll]

-- Calculates all those elements, that generate a right ideal, which is not
-- equal to the whole monoid and the twosided ideal generated by that same element.
-- Results in all elements besides the neutral and the null element.
getCandidates :: [Element]
getCandidates =
  let
      fLcA = fromList calculateAll
  in [x| x <- calculateAll,
         let z = fromList $ rightPrincipalIdeal x,
         z /= fromList (twoSidedPrincipalIdeal x),
         z /= fLcA]

-- Tests for an element m from getCandidates, if there is an element in M withouth mM
-- that reaches mM by adding an a (which amounts to saying that this element m' is in
-- M''). Therefore m'a is in mM. But also m'aM must not be mM.
testForOneCandidate :: Element -> [Element]
testForOneCandidate m =
  let
     mM = fromList $ rightPrincipalIdeal m
     factorsWithA = [m' | m' <- calculateAll ,
                                m' `notElem` mM,
                                let x = m' `mappend` a,
                                x `elem` mM,
                                fromList (rightPrincipalIdeal x) /= mM ]
  in factorsWithA


Something wrong with this definition of factorial with structural recursion?

This definition is correct. The syntax is almost Haskell code, so you can run it in a Haskell interpreter:

foldn (c, h) = g where
  g 0 = c
  g n = h (g (n - 1))

fact = outr . foldn ((0, 1), f)
outr (m, n) = n
f (m, n) = (m + 1, (m + 1) * n)

Usage in ghci:

Prelude> :load fact.hs
[1 of 1] Compiling Main             ( fact.hs, interpreted )
Ok, modules loaded: Main.
*Main> fact 0
1
*Main> fact 1
1
*Main> fact 2
2
*Main> fact 3
6
*Main> fact 4
24
*Main> fact 5
120

I don't know what you mean by “foldn ((0, 1), f) does not comply to its definition. If you mean that it's missing an argument, then this is not a problem. It's a function waiting to be applied. foldn is a curried function: it takes an argument and returns a function, which itself takes an argument and returns something; this makes foldn look like a function that takes two arguments (the first of which is a pair).

You can't evaluate foldn ((0, 1), f) any further (except to replace it by an anonymous function for which there is no source syntax) because its definition is by case on its argument: there's no way to know which one of g 0 = … or g (n+1) = … to use until you know whether the argument is 0.

Once you pass an argument, you can evaluate the call.

foldn ((0, 1), f) 0 = (0, 1)

so

fact 0 = (outr . foldn ((0, 1), f)) 0
       = outr (foldn ((0, 1), f) 0)
       = outr (0, 1)
       = 1

fact 1 = (outr . foldn ((0, 1), f)) 1
       = outr (foldn ((0, 1), f) 1)
       = outr (f (foldn ((0, 1), f) 0))
       = outr (f (0, 1))
       = outr (0 + 1, (0 + 1) * 1)
       = outr (1, 1)
       = 1

I'll let you work out other values by yourself.

The computation always terminates, regardless of the function h (assuming only that h terminates), by a simple induction argument: each nested call to foldn is applied to a smaller integer. For any nonnegative parameter, eventually the argument will be 0 which does not involve recursion.


how can i prove the following algorithm?

To compute $\exp(1)$ it does $0$ multiplications, since it enters the if and returns 2.
Assume that, for all $k<n$, to compute $\exp(k)$ it does no more than $2\log_2(k)$ multiplications.
To compute $\exp(n)$ we have two cases. Either $n$ is even and the number of multiplication is $1$ more than the number done for $\exp(n/2)$, or $n$ is odd and the number of multiplications is $2$ more than the number of multiplications done for $\exp((n-1)/2)$.
In the first case we have that the number of multiplications is no more than $2\log_2(n/2)+1=2\log_2(n)-2+1\leq 2\log_2(n)$. In the second case the number of multiplications is no more than $2\log_2((n-1)/2)+2=2\log_2(n-1)\leq 2\log_2(n)$.
Therefore, the number of multiplications to compute $\exp(n)$ is no more than $2\log_2(n)$.
By induction, this holds for all positive integers $n$.


Algorithm to Minimize a Regular Expression

There is a trivial algorithm to find the minimum regular expression equivalent to a given one:

  Go over all regular expressions in nondecreasing order of length. For each one, check whether it is equivalent to the original regular expression. Return the first one which is.

To check equivalence, convert the regular expressions to NFAs, then to DFAs, then computed the product automaton for the symmetric difference, and check whether any accepting state is reachable from the initial state.

This algorithm isn't very efficient. Indeed, minimizing regular expressions is PSPACE-complete. See for example Gramlich and Schnitger, Minimizing nfa's and regular expressions.


Show that the best case time complexity of Quicksort is $\Omega(n \log n)$

Let us replace $\Theta(n)$ with $n$, for concreteness, and assume a base case of $T(0) = 0$. Let's try to prove inductively that $T(n) \geq cf(n)$, where $f(n) = n\log n$ for all $n$ (where $0\log 0 = 0$).

During the proof, we will need to minimize $f(q) + f(m-q)$ for $0 \leq q \leq m$. Since $f'(n) = \log n + 1$, any minimum point must satisfy
$$
\log q + 1 = \log (m-q) + 1,
$$
that is, $q = m/2$. Since $2f(m/2) = m\log(m/2)$ whereas $f(0) + f(m) = m\log m$, we see that $q = m/2$ is indeed a minimum.

We are now ready to prove inductively that $T(n) \geq cf(n)$. The base case is obvious. For the inductive step, note that for each $q \in \{0,\ldots,n-1\}$,
$$
T(q) + T(n-1-q) \geq c(f(q) + f(n-1-q)) \geq c(n-1) \log((n-1)/2).
$$
Therefore to complete the proof, we need to show that
$$
c(n-1) \log \frac{n-1}{2} + n \geq cn\log n.
$$
This holds trivially for $n=1$, and holds for all $n \geq 2$ when $c = 1/\log 3$.

Altogether, this shows that $T(n) \geq n\log_3 n$.


Minimum distance between two convex hulls maximized

Given a pair of points $A,B$, you can split the the data into the points that are to the left of the line $AB$ (or on the line) vs the points that are strictly to the right of $AB$.  Then you can compute the convex hulls of these two sets and you can find the distance between the convex hulls in $O(n)$ time, for a particular split  (use a Graham scan; pre-sort the points once).  Since there are ${n \choose 2} = O(n^2)$ ways to choose $A,B$, this immediately gives a $O(n^3)$ time algorithm.

In fact, you don't need to compute both convex hulls.  It suffices to find the points that are closest (on each side) to the line $AB$.  It might be possible to do this faster than $O(n)$ time, which would improve the overall running time.  I think it suffices to compute a Voronoi diagram of all the points (a one-time $O(n \log n)$ time cost), then find all Voronoi cells that the line $AB$ goes through.  I don't know whether the worst-case complexity will be less than $O(n)$ but I bet in practice this will often lead to significant speedups.


Is the set of LL(*) grammars the same as the set of CFG grammars?

Static LL(*) grammar analysis is undecidable. In other words, there are some grammars that are LL(*) but we can't figure this out statically. ANTLR v3 fails over to backtracking in this case and therefore can exhibit the PEG A->a/ab problem where ab is dead code in the cases where grammar analysis failed.

In ANTLR v4, I'm introducing adaptive LL(*), which does all grammar analysis at runtime. Because I have an actual input stream in my paw, I can discover every LL(*) decision. I'm also including full LL context (vs Strong LL == SLL context which is weaker). Because I also rewrite all immediate left recursion on-the-fly, ANTLR v4 handles all CFG except for indirect left recursive ones. These are much less common than the immediate left recursive ones like expressions.

e : e '*' e
  | e '+' e
  | INT
  ;

This works fine in v4.  operator precedence is assumed to go from highest to lowest for ambiguous alternatives.


How many independent yes/no questions can be asked about a point in binary space (linear vs nonlinear codes)?

Linear codes which satisfy your requirement are known as linear MDS (maximum distance separable) codes. While there are no non-trivial (in your sense) binary linear MDS codes, there are such codes over larger alphabets. It might be that binary non-linear MDS codes are what you are after. In that case, you might be able to construct some from linear MDS codes over $\mathbb{F}_{2^k}$ for $k>1$.


How to know the width/size of a IR (Instruction Register)

In a typical scalar in-order issue microcontroller, the instruction register holds however many bits are needed to control the data path.
Modern microcontrollers are typically Harvard architectures, with program memory stored in flash, with a modest amount of data/read-write memory on-chip. This means that, unlike traditional scalar CPUs, the bus width of program memory and the bus width of data memory does not have to be the same.
Microcontroller instruction sets are typically designed so that the instruction as a whole can be understood from the first word fetched from flash. Any additional words contain data only, and hence do not need to participate in instruction decoding.
As an example, here is the AVR block diagram from a data sheet that I picked at random:

The instruction register holds whatever comes out of program memory. Since AVR has 16-bit instructions, we would expect it to be a 16-bit register.
Now consider the PIC instruction set. Different models have different instruction sizes, anything from 12 bit to 16 bit. Modern microcontrollers can handle this just fine because, as noted earlier, instruction memory can have a different word size from data memory. This instruction word contains all of the information needed to understand what the instruction needs to do, so this is the size of the instruction register.
A mid-range core PIC has a 14-bit instruction word, so it will almost certainly have a 14-bit instruction register. And if you look at a data sheet, this turns out to be correct, and is even labelled on the diagram:

So in summary: On a typical modern microcontroller, the IR size is one word of program memory, and the instruction encoding is carefully designed so that this word contains all the information that instruction decoding needs.


Does this constraint satisfaction problem have a name

This is a special case of perfect matching in bipartite graphs and could be solved using standard algorithms for that problem  (e.g., the Hungarian algorithm). It is not the perfect matching problem (it looks easier; and it is much more specific), but it is a special case of it.


Equivalent definition of minimal spanning tree

Note: The original answer has a flaw in "without loss of generality". The following one is based on Section 8.2.3 of the book "Computer Algorithms" (3rd edition) by Sara Baase and Allen Van Gelder.

The right part of the theorem is called the MST property.

  MST Property: Let $T$ be any spanning tree. For any edge $e \notin T$, $e$ has the maximal weight on the cycle created by adding it to $T$.

In terms of the MST property, the theorem to prove can be restated as:

  A spanning tree $T$ is an MST $\iff$ $T$ has the MST property.

We first prove the following lemma:

  Lemma: If $T$ and $T'$ are spanning trees that have the MST property, then $w(T) = w(T')$.

Proof: Let $\Delta E = (E(T) \setminus E(T')) \cup (E(T') \setminus E(T))$. That is, $\Delta E$ is the set of edges that are in one of $T$ or $T'$ but not in both. $\Delta E \neq \emptyset$. Let $|\Delta E| = k$.

If $k = 0$, we are done.

Let $k > 0$ and $e$ be a minimum edge in $\Delta E$. Assume that $e \in T \setminus T'$ (the case of $e \in T' \setminus T$ is symmetrical).

$T' + e$ create a cycle $C_{T'}$. There must be an edge $e'$ on the cycle $C_{T}$ that $e' \neq e$ and $e' \in T' \setminus T$ (otherwise $T$ contains the cycle $C_{T'}$).

Since $T'$ has the MST property, $e$ has the maximum weight on the cycle $C_{T'}$. Thus, $w(e') \le w(e)$.
On the other hand, $e$ by definition is a minimum edge in $\Delta E$. Thus, $w(e) \le w(e')$.

Therefore, $w(e) = w(e')$.

Add $e$ to $T'$, creating a cycle, then remove $e'$, leaving a spanning tree $T''$. Since $w(T'') = w(T')$, $T''$ is an MST. However, $T$ and $T''$ differ by $k-1$ edges.

Repeating the procedure above, we will end with an MST, say $T^{k+1}$, such that $T$ and $T^{k+1}$ differ by $0$ edges.

Therefore, we have $w(T) = w(T^{k+1}) = \cdots = w(T'') = w(T')$.

Given the lemma above, we proceed to prove the "$\Leftarrow$" direction as follows:

Assume $T$ has the MST property. Let $T_m$ be any MST. By the "$\Rightarrow$" direction, $T_m$ has the MST property. By the lemma above, $w(T) = w(T_m)$. Thus, $T$ is an MST.


Curry Howard correspondence and Church-Turing thesis

I'm not sure where you see the dissonance.

The Church-Turing thesis is a hypothesis stating that Turing Machines (equiv. Lambda Calculus or Recursive Functions) can do anything that we'd think of as computable.

The Curry-Howard correspondence is a much stronger statement that certain types of intuitionistic logic are structurally identical to things kind of like the Lambda Calculus. It doesn't really say which logic it corresponds to, it just shows that you can map the logical constructions in a canonical way to a (typed) computational model and vice versa. If you take different logics, you get different models and vice versa. The models may or may not be Turing-complete, although if we believe the Church-Turing thesis (it does seem to be doing alright so far), if you get a model that's more powerful than a Turing Machine, then you've got something incomputable in there.

Nonetheless, the logic you deal with does limit what you can compute in the corresponding model. For example, the Calculus of Inductive Constructions, which is a type theory and the basis for Coq, only allows types that it can verify have decreasing definitions (i.e. a recursive destruction of the type will terminate), but there are perfectly computable types which it can't verify, so you're locked out of using them.


Why do computers use binary, instead of ternary, or some other logic system?

3 different voltage levels makes building circuits harder and it is easier for little errors to occur in the signals.
Circuits need complex logic instead of the easy boolean logic which works perfectly.
Ternary is not compatible with binary that all computers use.


Term for most degenerate tree with two children on every inner node

This is a binary tree, when by a binary tree we mean a tree where each vertex has at most 2 children. In other words, you have a tree of maximum degree 3. Also, generally a tree that has a dominating path is a caterpillar.


Which is more fundamental: key-value or subject-predicate-object?

Following your simplicity argument (binary is more fundamental than octal), I'd say that key-value stores are more fundamental.
I think that Subject-Predicate is essentially a 'compound' or 'aggregate' key, so a subject-predicate-object store is a key-value store with additional requirements on the key (namely that it can be split into two).


How many edges before a random graph is connected?

A classical result of Erdős and Rényi states that if $k = \frac{n}{2} (\log n + c)$, then as $n\to\infty$, the probability that the graph is connected tends to $e^{-e^{-c}}$. You can find the proof in any textbook on random graphs.


There could be a few reasonable answers.

The simplest answer is that there are 6 minimum weight spanning trees (MSTs) in the first case and 64 MSTs in the second case. Look, the fact that you have said the same numbers and I can understand you perfectly means that interpretation makes some sense. Indeed, a strict definition/procedure can be given to yield those two numbers, although I will not be doing that here.

Let me proceed with another natural and interesting approach according to the conditions. How can we count distinct distinct MSTs of a given unlabelled weighted graph $G$? Here is one reasonable procedure. Initially we have counted 0 MST. Now someone will present to us the MSTs one at a time together with $G$ to us. Every information that is available should be presented to us accurately, including whether two vertices are connected and what is the weight of each edge and which edge is selected as part of the current MST. How these information will be presented can be arbitrary. Vertices can be labelled arbitrarily. The order of edges presented can be arbitrary. If drawn graphically, the shape of each edge and the location of the each vertex can be arbitrary. Etc. Whenever we can be confident that we are seeing a new MST, we will increase the count by 1. Using this approach, which is probably what you meant by considering "isomorphic MWSTs as a single minimum weight spanning tree", we will count 3 MSTs for the first graph and 20 MSTs for the second graph.

In practice, the second approach is too difficult for us to come up with results that we can understand or that could be beautiful. So, while I like the second approach very much as a challenge, I would suggest that you go with the first approach in a casual setting.

Note that there are a few ambiguities inherent in the question that needs to be defined formally (a.k.a. rigorously) before we can agree what is the way to count. For example, what does it mean by an "unlabelled weighted tree"? Do we require that the same weight be assigned to all edges that could be mapped to each other under an graph isomorphism (which happens to be the cases here)? How will we distinguish two "unlabelled weighted" trees? These questions should have been answered before we can count the number of distinct MSTs in a definitive way.


Let me try to answer your question, I may be mistaken, so check it out first:

Let's first state the definition of foldl:

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl h b x = case x of
                []     -> b
                (x:xs) -> foldl h (h b x) xs

Now, we aim to prove that, given f:: A -> B, g:: A -> C -> A, h:: B -> C -> B, a:: A b:: B, such that:

f a = b
f (g x y) = h (f x) y, for all x, y
f is strict

Then:

f . foldl g a = foldl h b :: [C] -> B

We are going to prove it by induction on the length of the list:

Case 0:

f.foldl g a []   = foldl h b []
f (foldl g a []) = foldl h b []   -- Definition of .
f a              = b              -- Definition of foldl
True                              -- given

Case n => n+1:

let x:xs be a list of length n+1, then xs has length n, the property holds for xs. Let's check it's true for x:xs:

f (foldl g a (x:xs))   = foldl h b (x:xs)
f (foldl g (g a x) xs) = foldl h (h b x) xs  -- Definition of foldl

Now, let's take f' = f, g' = g, a' = g a x, h' = h, b' = h b x

Clearly, f' is strict, also, f' a' = b':

f' a'     = b'
f (g a x) = h b x  -- Opening the '
h (f a) x = h b x  -- Hypothesis
h b x     = h b x  -- Hypothesis

Now, let's check that f' (g' z y) = h' (f' z) y works for any y, z (I changed the x for a z, because we have a fixed x, the head of the list):

f' (g' z y) = h' (f' z) y
f (g z y)   = h (f z) y   -- Opening the '
                          -- OK: hypothesis

Now, since the predicate works for lists of length n, and xs has that length, and also f', g', h', a', b' make the premises true, we have that, for any list of size n, in particular xs:

f' . foldl g' a' xs      = foldl h' b' xs
f  . foldl g  (g a x) xs = foldl h (h b x) xs  -- Opening the '
f (foldl g (g a x) xs)   = foldl h (h b x) xs  -- What we were trying to reach


Definition of Strongly Parsimonious Reduction

A search problem is defined by a relation like $R$. The task is given an input $x$ find a solution $y$ s.t. $R(x,y)$ is true.

A counting problem is defined as counting the number of solutions of a search problem, i.e. given an input $x$ we want to compute the number of $y$s s.t. $R(x,y)$ holds. The counting problem associated with search problem $R$ is denoted by $\#R: \Sigma^* \to \mathbb{N}$, $x \mapsto \#y: R(x,y)$.

A parsimonious reduction $f$ between counting problems only needs to preserve the number of $y$s, i.e. for all $x$,

$$\#y:R(x,y) = \#z:S(f(x),z)$$

A strongly parsimonious reduction has an the extra property that you mentioned. The meaning of the property should become clear if you look at it in the following way:

  Assume that we want to use the search problem $S$ to solve the search problem $R$.
  On an input $x$ for $R$, we first compute $g(x)$ which is an input for $S$.
  Then we use $S$ to find an $S$-solution $y$ for $g(x)$, i.e. $(g(x),y)\in S$.
  Finally we compute $h(x,y)$ to obtain an $R$-solution for $x$.

Now if we want to preserve the number of solutions between these two search problems, we can make sure that for every $x$, the function $h(x,\cdot)$ that computes an $R$-solution for $x$ from an $S$-solution $y$ for $g(x)$ is a bijection.

The difference should be clear now: not only the number of $R$-solutions for $x$ and $S$-solutions for $g(x)$ are equal, there is an efficient bijection between those solutions.


Proof of 0/1 knapsack optimal substructure

Suppose that some $S'\subseteq E-\{x\}$ is a better admissible solution than $S-\{x\}$. Then $S'\not= S$, the value is more, $v(S') > v(S-\{x\})$, and $x\not \in S'$, and $w(S')\leq W-w(x)$, as you indicated. Now add $x$ to $S'$ to obtain $S''=S'\cup \{x\}$. What will be the value and weight of this new subset? And how does it compare to the value and weight of $S$? Let's write it out:

$w(S'') = w(S')+w(x) \leq (W-w(x))+w(x) = W$ so $S''$ weighs less than $W$, so $S''$ is an admissible solution, so it makes sense to compare their values.

$v(S'') = v(S') + v(x)$. By assumption, $v(S')>v(S-\{x\})$, so, adding $v(x)$ to both sides of this last equation, $v(S')+v(x)>v(S-\{x\})+v(x) = v(S)$. Hence $v(S'')>v(S)$. But this is a contradiction, because $S''$ is supposedly a better admissible solution while you had presumed that $S$ was the best admissible solution. $\square$

By admissible I mean that the knapsack weighs less than the maximum weight.


Is the program in secondary memory can be a process?

A process is a technical term that has a well-defined meaning.  You can't just re-define standard terms that have an accepted meaning... or if you do, you should expect it to cause confusion.  My advice is to stick with the standard meaning of this term, and read an operating system textbook to learn what is the accepted notion of a "process".

Wikipedia defines a process as "an instance of a computer program that is being executed".  A process is not some set of lines of code.  A program contains a bunch of machine-level instructions.  (Those machine-level instructions are typically obtained by compiling some source code.)  A process is then a running instance of a program.  The process typically is comprised of multiple resources: some memory (in particular, a region of virtual memory), one or more threads of execution, and some operating system state that is specific to the particular process.

So, no, you can't call "the set of lines of code in secondary memory" a process -- that's not what a process is.  Similarly, when you write "We can call the m lines of code, which are in main memory as process.", my reaction is: no, you can't -- that's not what a process is.


Decide whether a DFA accepts at least two strings

First remove dead states(those which do not lead to accept states). Then run depth first search. If all accepts states are not reachable or there is a single path leading to an accept state then REJECT. If there are two different paths leading to an accept state (or accept states) then ACCEPT. If there is a cycle including a state from which an accept is reachable also ACCEPT.


In some sense, nothing much.  We still have P = NP.  It's possible for there to be statements that are true even though we can't prove them true.
In another sense, something interesting happens: in your scenario, we can explicitly write down a new algorithm that is guaranteed to solve 3SAT in polynomial time, using Levin universal search.  See https://cs.stackexchange.com/a/92095/755.  So, if there is a non-constructive proof that 3SAT is in P, then you can find a constructive proof that 3SAT is in P.
See also Is P decidable?, Assuming P = NP, how would one solve the graph coloring problem in polynomial time?, Explicit algorithms and algorithms involving unknowns.


NP-Completeness: A question about reduction and hardness

As far as I know, the first point is correct. For the second point you missed the fact that "solve $A$ with the given instance iff solve $B$ with the created instance".


Yes, there is a polynomial-time algorithm for solving perfect mazes: depth-first search solves them, and runs in polynomial time.  Actually, depth-first search is more general, as it can handle loops and other structures, too.

Breadth-first search also works, and will give you the fastest way out of the maze, but is only implementable on a computer given the full description of the maze.  In contrast, depth-first search can be implemented by a human with a piece of chalk and a ball of string -- the piece of chalk allows you to mark rooms as visited, and the ball of string lets you simulate the stack.


Need help understanding how to find big theta of a snippet of code

In order to estimate the running time of the code it is enough to count the number of times the two "do-somethings" are executed. Call them do-something 1 and do-something 2 (in their order of appearance). Do-something 2 is executed about $n$ times. As for do-something 1:

If $n < 5$, no times.
If $5 \leq n < (4/3)5$, $5$ times.
If $(4/3)5 \leq n < (4/3)^25$, $(4/3)5$ times.
Generally, if $(4/3)^k5 \leq n < (4/3)^{k+1}5$, $(4/3)^k5$ times.

Be creative and estimate the number of times that do-something 1 is executed in terms of $n$. Conclude the running time of the code snippet.


The GCD can be computed in polynomial time. Strongly Polynomial is a much more restrictive classification. Taking the definition from here:

  An algorithm runs in strongly polynomial time if

  the number of operations in the arithmetic model of computation is bounded by a polynomial in the number of integers in the input
  instance; and
  the space used by the algorithm is bounded by a polynomial in the size of the input.

The input to GCD is two integers. Thus, in order to be solvable in strongly polynomial time, GCD would need to be solvable with a constant number of aritmethic operations since the input size is constant.


Maximizing number of selected squares in a grid

There is a dynamic programming algorithm whose running time is $O(2^{4n})$.

Suppose we have already chosen a configuration for the first $i$ columns.  Mark a cell in the $i$th column as "red" if the cell to its right cannot be selected (i.e., the number of selected neighbors, not counting its right neighbor, is equal to the number in that cell), or "green" if the cell to its right can be selected.

Let $c \in \{R,G\}^n$ be a sequence of $n$ colors, and $x \in \{0,1\}^n$ be a sequence of $n$ bits.  Define $A[i,c,x]$ to be the maximum number of elements in a good selection for the first $i$ columns that induces the coloring $x$ on the $i$th column and where $x$ describes which cells are selected in the $i$th column.  Then it is easy to calculate $A[i+1,c',x']$ from $A[i,c,x]$: we have

$$A[i+1,c',x'] = |x'| + \max_{c,x} A[i,c,x],$$

where the max is taken over all $c,x$ that are consistent with $c',x'$ (i.e., such that it's possible to have a selection for the first $i+1$ columns that has selection $x$ in column $i$, selection $x'$ in column $i+1$, colors $c$ in column $i$, and colors $c'$ in column $i+1$).  To be consistent, we must have  $c_j=R \implies x'_j=0$ for all $j$, and $x_j + x'_{j-1} + x'_{j+1}$ must be at most the number in column $i+1$, row $j$ (and $c'_j=R$ iff they are equal).

This yields a dynamic programming algorithm with $O(n \times 2^{4n})$ running time: we need to fill in $n \times 2^{2n}$ entries of $A[\cdot,\cdot,\cdot]$, and each entry requires us to compute a max over at most $2^{2n}$ numbers.


We can treat the input $x$ as a boolean array. Using an $O(\log n)$ depth sorting network (such as the AKS network), we can sort $x$ in nonincreasing order. Calling the result $y$, using $O(1)$ more depth we can compute $z_i = y_i \land \lnot y_{i+1}$ (extended in the right way to the boundary). The vector $z_0,\ldots,z_n$ is the indicator vector of the Hamming weight of $x$. At this point you can compute any symmetric function using $O(\log n)$ more depth.
This shows that there is a universal constant $C$ such that all symmetric functions can be computed in depth $C\log n$ using constant fan-in circuits.


What is the computational complexity of "real-life" regular expressions?

The following extended regular expression matches the language $\{ ww : w \in \Sigma^* \}$:
$$
\texttt{^\\(.*\\)\\1\\\$}
$$
This language is neither regular nor context-free.
Matching using extended regular expressions is NP-complete; see for example this paper, which discusses efficient algorithms in some special cases.


The Böhm–Jacopini theorem states that everything can be implemented using just IFs and WHILEs. Indeed, your CPU essentially implements an infinite WHILE loop with conditional execution.

Recursion can be simulated iteratively using a stack; this is how recursion is implemented under the hood. Conversely, the same construction as in the theorem shows that everything can be implemented using only tail recursion (which is essentially a WHILE loop). So iteration and recursion are equivalent.


In order to obtain an upper bound on the number of DFA states required to recognize some language, the simplest method is to give a DFA with that (or lower) number of states. In order to obtain a lower bound on the same number, the easiest route is to give $m$ pairwise indistinguishable words. These are $m$ words $x_1,\ldots,x_m$ such that for each $i \neq j$ there exists a word $y$ such that $x_i y \in L$ whereas $x_j y \notin L$, or vice versa. This set of words shows that every DFA for $L$ must contain at least $m$ states (why?).

In your case, the minimal number of states is much smaller than 24, though the exact number depends on the encoding. Instead of solving your question, let me calculate the minimal number of states in a DFA accepting all (non-empty) decimal numbers (encoded MSB to LSB) which are divisible by 6. I claim that this number is 4. For the upper bound, consider a DFA with states $q_0,q_1,q_2,q_A$, where $q_0$ is the initial state and $q_A$ is the accepting states. The transition table of the DFA is
$$
\begin{array}{c|ccccccccccc}
\delta & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\\hline
q_0 & q_A & q_1 & q_2 & q_0 & q_1 & q_2 & q_A & q_1 & q_2 & q_0 \\
q_1 & q_1 & q_2 & q_A & q_1 & q_2 & q_0 & q_1 & q_2 & q_A & q_1 \\
q_2 & q_2 & q_0 & q_1 & q_2 & q_A & q_1 & q_2 & q_0 & q_1 & q_2 \\
q_A & q_A & q_1 & q_2 & q_0 & q_1 & q_2 & q_A & q_1 & q_2 & q_0 \\
\end{array}
$$

You can show by induction that upon reading a word $w$:

If $w = \epsilon$ or $w \equiv 3 \pmod{6}$, the machine is in state $q_0$.
If $w \neq \epsilon$ and $w \equiv 1,4 \pmod{6}$, the machine is in state $q_1$.
If $w \neq \epsilon$ and $w \equiv 2,5 \pmod{6}$, the machine is in state $q_2$.
If $w \neq \epsilon$ and $w \equiv 0 \pmod{6}$, the machine is in state $q_A$.

This easily implies that this DFA accepts our language.

For the lower bounds, we use the set of words $\{0,1,2,3\}$. The following table gives the words $y$ separating each pair of words:
$$
\begin{array}{c|cccc}
y & 0 & 1 & 2 & 3 \\\hline
0 & & \epsilon & \epsilon & \epsilon \\
1 & \epsilon & & 2 & 0 \\
2 & \epsilon & 2 & & 0 \\
3 & \epsilon & 0 & 0 &
\end{array}
$$
(These correspond to the states $q_A,q_1,q_2,q_0$.)


What is a visual bag of words and how is it implemented?

This is the original paper:

Gabriella Csurka, Christopher R. Dance, Lixin Fan, Jutta Willamowski, and  Cédric Bray. Visual Categorization with Bag of Keypoints. Workshop on Statistical Learning in Computer Vision, ECCV, 2004.


Multiple knapsack problem with equal profit and different weight

This problem can be shown to be NP-complete via reduction from PARTITION. Simply take $m=2$, the weights of each item to be the same across both knapsacks, and the capacities of each knapsack to be half the total weight across all items.


The answers are correct, but when proving that a language is not regular, or not context-free, it is not enough to show that one attempt does not work. You have to use tools like pumping lemma. For context-free languages, there is a version of pumping lemma which should work here: http://en.wikipedia.org/wiki/Pumping_lemma_for_context-free_languages

Also it's a detail, but in your last argument, $2i+j+l$ is not any number $>0$, it is at least $5$, since $j>l$ and $i,l,k>0$. So your language is $\{(210)^n : n\geq 5\}$, which is indeed regular.


Let us first look at the total number of hash functions in $H$. Since each key can be mapped to $m$ different indexes and there $n$ different keys. We get:
\begin{align}
|H| = m^{n}
\end{align}
Now, without loss of generality, let us consider the first two keys $x = k_{1}$ and $y = k_{2}$. We will compute the number of hash functions where $x$ and $y$ will collide i.e., $h(x) = h(y) = i$ for any $i \in \{0,\dotsc,m-1\}$.
\begin{align}
|\{h \in H : h(x) = h(y) = i\}| = m^{n-2}
\end{align}
Therefore, summing up for all $i \in \{0,\dotsc,m-1\}$, we get:  $$|\{h \in H : h(x) = h(y)\}| = m^{n-1} = \frac{|H|}{m}$$
Hence, $H$ is a universal hash family.


How to compare the output of a neural network with his target?

The easy answer: Take the predicted class to be the argmax of your output vector.

The longer answer: Since you're doing multiclass classification you should probably be using softmax output units (if I had to guess, I would guess you're using sigmoid output units). If $\mathbf{x} \in \mathbb{R}^n$ is the input to your output units then the softmax for the $i$th output unit is

$$ y_i = \frac{\exp(x_i)}{\sum_{j}\exp(x_j)} $$

This output function is nice for a number of reasons.

since your output vector sums to 1, you can interpret it probabilistically.
the derivative is particularly nice in combination with a log loss function.

Note: the further information I've provided may seen redundant since clearly

$$ \text{argmax}\{\mathbf{x}\} = \text{argmax}\{\mathbf{\sigma(x)}\} = \text{argmax}\{\mathbf{\text{softmax}(x)}\}, $$

where $\sigma$ is the elementwise logistic sigmoid function. The problem with just taking the argmax of what you have is you will likely not be optimizing the function you are actually interested in internally.

On the other hand the choice of loss function for classification isn't as cut and dry as I've made it sound.


Are the definitions of constructs in terms of lambda terms issues in implementation/design or uses of functional languages?

Those features are almost never implemented like the lambda calculus in modern programming language implementation. In some cases, using the lambda calculus representation for datatypes has performance improvements (this is associated with so-called tagless representations). Historically, the Haskell compiler did use this representation early on, but has since dropped it. In either case, it never affected user code, and was an implementation detail.
Unless there's a compelling reason to, most code does not use said representations, so the programmer will never interface with them. So those concepts are generally the same as in imperative languages, although keep in mind that there are differences since most functional languages are expression-oriented; e.g. 'if ... then ... else ...' is an expression which returns a value, rather than a statement.


Use the space partitioning approach to nearest neighbor search.

For instance, one approach is to use a $k$-d tree on on the surface of the sphere.  You can express every point on the sphere using spherical coordinates: every point on the sphere has coordinate $(1,\theta,\phi)$.  Thus, we have a 2-dimensional space with coordinates $(\theta,\phi)$.  Now organize your points using a $k$-d tree, where here we are in $k=2$ dimensions.  There are standard algorithms for nearest neighbor search in a $k$-d tree; heuristically, the expected running time is $O(\lg N)$.

You will have to make small modifications to the data structure to reflect that the coordinates "wrap around" modulo $2\pi$, but this is not hard.  The key subroutine used in nearest neighbor search in a $k$-d tree is: given a point $P$ and a "rectangular" region $R$, find the distance from $P$ to the nearest point in $R$.  In your case, the region $R$ is $[\theta_\ell,\theta_u] \times [\phi_\ell, \phi_u]$, i.e., the set of points $\{(1,\theta,\phi) : \theta_\ell \le \theta \le \theta_u, \phi_\ell \le \phi \le \phi_u\}$.  It is easy to compute the distance from $P$ to the closest point in $R$.  This will then let you use the standard algorithm for nearest neighbor search in a $k$-d tree.

Alternatively, instead of a $k$-d tree, you could use any other binary space partitioning tree, or you could look at metric trees, though I don't have any reason to expect them to be significantly better.


Average Intelligence Quotient of Computer Scientists?

This is not necessarily the most robust estimation, and is just a blog post (hence I'm not sure it's reliable enough to do anything real with), but here is a posting which uses GRE/SAT scores to estimate IQ across different majors. It puts the average IQ of CS students at ~124.

Another blog post uses GRE/SAT scores again to do the estimate, arriving at 128.5 for CS.

Their original data are from here and here, respectively. I haven't puzzled out yet whether they're using the same base data yet.

Undermining these a little is that there are no supporting statistics (again they are just blog posts, not scientific articles).

I would use these results with a great deal of caution. If nothing else, they appear to be heavily biased to the US setting (simply because of the source data), and given the relatively rapid ups and downs of CS popularity, the data for at least one is somewhat old.


What is meant by superlinear speedup? Is it possible to have superlinear speedup in practice?

With equation: not really.

Superlinear speedup comes from exceeding naively calculated speedup even after taking into account the communication process (which is fading, but still this is the bottleneck).

For example, you have serial algorithm that takes $1t$ to execute. You have $1024$ cores, so naive speedup is $1024x$, or it takes $t/1024$, but it should be calculated like in your equation taking into account memory transfer, slight modifications to the algorithm, parallelisation time.

So speedup should be lower than 1024x, but sometimes it happens that speedup is bigger, then we call it $superlinear$.

Where it comes from?
From several places: cache usage (what fits into registers, main memory or mass storage, where very often more processing units gives overall more registers per subtask), memory hit patterns, simply better (or a slightly different) algorithm, flaws in the serial code.
For example, a random process that searches space for a result is now divided into $1024$ searchers covering more space at once so finding the solution faster is more probable.
There are byproducts (if you swap elements like in bubble sort and switch into GPU it swaps all pairs at once, while serial only up to point).

On the distributed system communication is even more costly, so programs are changed to make memory usage local (which also changes memory access, divides problem differently than in sequential application).

And the most important, the sequential program is not ideally the same as the parallel version - different technology, environment, algorithm, etc. so it is hard to compare them.

Excerpt from "Introduction to Parallel Computing" Second edition by Ananth Grama, 2003

  Theoretically speedup can never exceed the number of processing elements $p$.
  If the best sequential algorithm takes $T_s$ units of time to solve a given problem on a single processing element, then a speedup of $p$ can be obtained on $p$ processing elements if none of them spends more than time $T_s/p$.
  A speedup greater than $p$ is possible only if each processing element spends less than time $T_s/p$ solving the problem.
  In this case, a single processing element could emulate the $p$ processing elements and solve the problem in fewer than $T_s$ units of time.
  This is a contradiction because speedup, by definition is computed with respect to the best sequential algorithm.

So the name "superlinear" in this context comes from the definition of speedup.


How strong is an oracle that avoid don't-halt

EDIT: I made a deeply silly mistake in my previous answer. Below what I've done is answered the question, then explained how two variations of the question - which I originally conflated with the actual question - yield a very different answer.

An oracle of the type you describe computes the halting problem (and conversely every oracle computing the halting problem computes an oracle of your type).

Suppose $x$ computes the halting problem. Without loss of generality, we may take $x$ to literally be the halting problem. Then we can compute an $f$ as desired by simply taking an input $e$, asking $x$ whether $T_e(e)$ halts, and (i) if the answer is no, halt and output $0$ and (ii) if the answer is yes, run $T_e$ until it halts and output the result.
Conversely, suppose $f$ has the desired property. There is a total computable function $h$ such that for all $e$ if $T_e(e)$ halts, then $T_{h(e)}(h(e))$ halts and gives the runtime of $T_e(e)$. Now to tell whether $T_e(e)$ halts we simply run $T_e(e)$ for $f(h(e))$-many steps.

Now there are a couple natural variations to the above notion:

What if we demand inequality instead of equality?
What if we restrict attention to machines with binary output?

Both of these variations prevent the argument above from working, the former by preventing us from representing runtimes as outputs and the latter by preventing us from coding literally anything into the output.

It turns out that these notions yield a much weaker complexity class: namely the PA degrees. The original definition was that something is of PA degree if it computes a complete consistent extension of Peano arithmetic (which by Godel must be non-computable), but there are many equivalent definitions. Generally the simplest to work with is:

  A degree ${\bf a}$ is PA iff whenever $X$ is an infinite computable binary tree, ${\bf a}$ computes an infinite path through $X$.

PA degrees can be quite weak, computability-theoretically. While no PA degree is computable, they don't have to compute the halting problem: there are PA degrees incomparable with the halting problem, and there are PA degrees strictly weaker than the halting problem (where strength here is measured by Turing reducibility).

Re: relativization, the answer is no: the proof of the incomputability of all PA degrees relativizes, so no oracle is PA over itself.


Can one have a condition like this in semidefinite programming?

Assuming that a, b, and u are real variables in your semidefinite program, the answer is negative.

The important fact here is that each constraint in a semidefinite program defines a convex set.  Your condition cannot be written as a constraint in a semidefinite program because the set of points (a, b, u) ∈ ℝ3 that satisfy the condition is not convex.  I suggest that you try to prove that this set is indeed not convex, but here is a proof (put the mouse cursor in the box below to show the proof):

   Proof: (a, b, u) = (1, 1, 1) and (a, b, u) = (3, 3, 9) satisfy the condition, but their midpoint (a, b, u) = (2, 2, 5) does not satisfy the condition.


what is the time complexity for binary division by repeated subtraction?

If you calculate Z = floor (X / Y) by repeated subtraction, then you will perform Z subtractions. If you divide exactly n bits by exactly m bits, then there are at least $1/2 \cdot 2^{n-m}$ and at most $2 \cdot 2^{n-m}$ subtractions, so it's $\theta (2^{n-m})$ subtractions.

If you divide at most 2 bits by at most m bits, then Y might be 1 and in the worst case there are almost $2^n$ subtractions, so $O(2^n)$ subtractions.


Are the definitions of recursively enumerate equivalent?

Your two definitions are essentially the same: a $\Sigma_1^0$ formula is one of the form
$$\exists x Q(n,x),$$
where $Q$ is computable and $n$ is the parameter.

Another difference between the two definitions is that the first only defines r.e. sets, i.e. unary relations, whereas the second defines r.e. relations of arbitrary arity. The two definitions coincide in the case of unary relations.


Unary notation representation in Turing Machine

A reasonable convention would be to take any enumeration of the integers and use it. For example, this enumeration
$$
0,1,-1,2,-2,3,-3,\ldots
$$
corresponds to this encoding:
$$
\begin{align*}
0 &\to \epsilon \\
1 &\to 1 \\
-1 &\to 11 \\
2 &\to 111 \\
-2 &\to 1111 \\
3 &\to 11111 \\
-3 &\to 111111
\end{align*}
$$


There is any notation for a language that is empty infinite?

The usual way to describe these properties is by indicating the size of $L$, denoted by $|L|$.

Empty language, the size is zero, $|L|=0$
Finite language, $|L|=c$ or in general, the size in non-infinite, $|L|< \infty$
Infinite language, $|L|=\infty$.


Why does the substitution {x/f(y), y/z} work this way?

Because that's not how substitution is defined.

Seriously, there isn't much more to it than that. In some situations (such as applying a single step of a collection of rewriting rules), having the ability to substitute "each variable once, all at once" like this is important for the correctness of the definition. So substitution is defined so that there is a way to write these definitions correctly.

In other situations (such as the output of a unification algorithm), authors require that substitutions be idempotent, i.e. applying the substitution a second time does not change the result. This prohibits substitutions such as the one in the question, thereby avoiding the issue.


Brute force Delaunay triangulation algorithm complexity

A Delaunay triangulation can be considered as the lower convex hull of the 2d point set lifted to the paraboloid. Thus, if you take your 2d point set and assign to every point $(x_i,y_i)$ a $z$-coordinate $z_i=x_i^2+y_1^2$, then the projection of the lower convex hull into the $xy$-plane gives you the Delaunay triangulation.

Using this perspective, what does it mean for an edge $(p_i,p_j)$ to be illegal? First of all, for every triangulation $T$ we can use the parabolic map to get a 3d (triangulated) surface that projects down to $T$. Of course, this surface is not necessarily convex, if it would be convex, $T$ would be the Delaunay triangulation. Simply speaking, the edge $(p_i,p_j)$ is an obstruction for the convexity of the surface, a concave edge. When flipping this edge we change the situation on the lifted surface only locally. So lets look at the 4 points $p_i,p_j,p_k,p_l$. In 3d they form a tetrahedron, that projects down to quadrilateral. Since the two triangles $p_ip_jp_k$ and $p_ip_jp_l$ define the the concave edge $(p_i,p_j)$, the triangles $p_kp_lp_i$ and $p_kp_lp_j$ define the a convex edge $(p_l,p_k)$. Therefore, flipping an illegal edge corresponds to replacing a concave edge by a convex edge in the lifting. Notice that this flips might turn other convex edges to concave edges.

Remark: The image is not geometrically correct and should only be considered as a sketch.

Let $T'$ be the triangulation after the flip. The lifted surface of $T'$ "contains" the surface of $T$. By this I mean that if you watch the two surfaces from the $xy$ plane you see only triangles from the surface of $T'$ (or triangles that are in both surfaces). You could also say that the surface of $T'$ encloses more volume. Also, the edge $(p_i,p_j)$ lies now "behind" the lifted surface induced by $T'$ when watching from the $xy$ plane.

During the flip sequence we get a sequence of surfaces with strictly increasing volume. Thus, the edge $(p_i,p_j)$ lies "behind" all these surfaces. Hence, it can never reappear during the flipping process. Since there are only $n$ choose 2 possible edges, we have at most $O(n^2)$ flips.


Can x86 Instruction Set be changed with microcode update?

That depends completely on the CPU. Some CPUs don't use microcode at all. Some CPUs use a mixture of hardcoded instructions and microcoded instructions. This mixture can be anywhere between almost all hardcoded and only a few microcoded instructions to almost all microcoded and only a few hardcoded instructions.
For CPUs that have microcode, the microcode could be either modifiable or not modifiable.
If all instructions are microcoded (there are no hardcoded instructions) and the microcode is stored and loaded in such a way that you can load a different one at will, then it would theoretically be possible to load microcode that implements a completely different instruction set.
However, the feasibility of that still depends on the internal design of the CPU. An extreme example would be the Transmeta Crusoe and Efficeon CPUs. These were 128 bit VLIW designs internally, and in order to execute x86 code, they had a software layer called Code Morphing Software, which was essentially an interpreter and JIT compiler from x86 to the internal VLIW code. The Code Morphing Software was running entirely in the standard RAM. This makes it sound like it should have been very easy to just load a different version of the Code Morphing Software and turn the CPU into an ARM or PowerPC or SPARC or MIPS CPU, right?
Well, not according to Linus Torvalds, who worked for Transmeta at the time. He was asked this exact question, and his answer was that the internals of the CPU are so specifically optimized for interpreting x86 code that writing a CMS implementation for, say, MIPS would be no different (and no more performant) than simply writing a MIPS emulator for x86 … which already exist anyway.
On the other hand, the CPUs of the Xerox Alto, Dandelion, Dolphin, and Dorado workstations were explicitly designed to be microcoded for different use cases. They would run completely different microcode depending on whether they were running Interlisp, Smalltalk, or the Star system. For example, the Smalltalk system implemented the most important instructions of their VM in microcode, so that in some sense, the CPU could directly execute (parts of) Smalltalk byte code. You could say that when running the Smalltalk system, Smalltalk byte code was the ISA!


Although determining whether grammars are ambiguous is undecidable, in the case where the  grammar has a rule of the form

$$T\to T\;T$$

then either the grammar is ambiguous or the rule is useless. (Because $T\;T\;T$ can be reduced in two ways.)
Determining the equivalence of two CFGs is also undecidable so there is no general solution to the equivalence question. But you could try to prove that both grammars generate the Dyck language.
A simple deterministic grammar for that language is

$$S\to \epsilon\mid(\;S\;)\;S$$


Finding small node sets that can not be avoided on paths from source to sink

Finding the smallest number of edges instead of vertices is the famous Minimum Cut problem which can be solved using any of the Max-Flow-Min-Cut algorithms. Picking vertices is a specific case of the generalised max-flow-min-cut theorem and similar algorithms can be used to solve it. In any case, it can be formulated as a linear program with polynomial complexity, which can be solved in polynomial time using any of the LP-solvers.


Since you asked for algorithms, I suggest you look at the Hough transform and other techniques for finding lines in an image.  I suspect this will help you determine where the lines are, where the intersections are, and how much to rotate to recover the original image.


One possible approach is to try RANSAC.  RANSAC is applicable where we expect: (a) some fraction of the observations (the rays) are erroneous (outliers) and should be ignored, and (b) the remaining ones are all approximately consistent with some low-dimensional probabilistic model.  The RANSAC method then tries to find the best model that (a) minimizes the number of outliers, and (b) among all such models, is as consistent as possible with the remaining observations.

In your case, RANSAC might work well enough.  Some small fraction of the rays are in a completely wrong direction, and will be ignored as outliers.  The remaining ones should all be roughly consistent.  The model could be (for instance) a two-dimensional Gaussian with diagonal covariance matrix.  Such a model has 4 free parameters, so given 2 or more rays, you can fit a Gaussian to it.  Given a model, you can identify which rays are inliers (plausibly consistent with the model) and which rays are outliers.

Given this, one way to apply RANSAC to your problem would be to repeat the following recipe 1000 times:

randomly pick 5 rays
fit a Gaussian to those 5 rays
for each ray, compute the likelihood that it came from that Gaussian, and throw away all those whose likelihood is below some threshold (these are the outliers)
fit a new Gaussian to all those remaining rays (the inliers)
count how many rays remain consistent with the revised model (i.e., count the number of inliers)

Then keep the model with the largest number of inliers, and use the corresponding Gaussian as your model.  In particular, the mean of that Gaussian is your best guess for the target, and the equal-likelihood contour of that Gaussian (the counter corresponding to 2 standard deviations away from the mean) is your circle.  All of the above constants (1000, 5, 2) can be tuned, and variants of this algorithm can be considered.

Why does this work?  Suppose 80% of the rays are correct and 20% are thrown in the completely wrong direction.  Then a random sample of 5 of the rays will, with probability $0.8^5 \approx 0.33$, contain only good rays, and when you fit a Gaussian to them, will give a reasonable estimate of the target and the surrounding circle.  The remaining 67% of samples will have at least one bad ray, which causes a bad model, but the bad models will be thrown away.

The general idea of this sort of approach is: (1) identify a scoring function, which given a model gives you a score for the model; (2) repeatedly pick a random sample of a few rays, fit a model to that sample, use the model to identify outliers, discard the outliers and fit a model to the remaining inliers, and then compute the score of the resulting candidate model; keep the best model you've ever seen.  You can play with the type of model you allow, and the scoring function you use.

Some form of expectation-maximization (EM) potentially might yield even better results.


DFA Minimization: Finding all equivalence classes of $\mathsf{R_L}$ for language $011(0+1)^*011$

You may want to look at Sipser's "Theory of Computation" for a full explanation.
Technically, you must first define the problem. What do you mean by "find the equivalence classes"? You probably mean that you want to find a representative of each class, or to find an algorithm that given a word, classifies it to a class.

Probably the easiest way to do so, is to construct a DFA for the language, and then minimize it. By the correctness proof of minimization, the states of the minimal DFA correspond to the equivalence classes.

EDIT: The example in the book doesn't show you how to find the equivalence classes algorithmically. It just shows an example of finding them based on intuition and clever thinking (as you would do with a general mathematical problem). There is no general way to do that.

What the example demonstrates is that if you find these classes, then you can construct a minimal DFA. The interesting point is that the converse is also true.


Exercise 11 of section 3.2.2(The art of computer programming)

We have $z^\lambda$ has the form of
  $$f(z)u(z) + p^ev(z) + 1$$
  where $p^{e+1}\mid f(z)u(z),f(z)\mid p^ev(z)$ and $v(z)\not\equiv 0\pmod p\ $  (*)

You misunderstood the definition of $a(z)\equiv b(z)\pmod {f(z)\text { and }m}$. If $z^\lambda \equiv 1 \pmod{ f(z)\text{ and }p^{e}}$, then $$z^\lambda=1 + f(z)u(z) + p^ev(z)$$
for some $u(z), v(z)$. There is no further requirement on $u(z)$ and $v(z)$. It is incorrect to deduce $p^{e+1}\mid f(z)u(z)$. It is incorrect to deduce $f(z)\mid p^ev(z)$.

However, if we also have $z^\lambda \not\equiv 1 \pmod{ f(z)\text{ and }p^{e+1}}$, then we must have $v(z) \not\equiv 1 \pmod{ f(z)\text{ and }p}.$

  Why is the above argument necessary?

Now that you can understand the notation correctly, you can figure it out by yourself.

  Is the Gauss's lemma 4.6.1G the one in Wikipedia?

Yes, lemma 4.6.1G in the book is the same as the Gauss's lemma on Wikipedia.


Examples of NP Complete key exchange algorithms

There are no known public-key cryptographic algorithms that have been proven to be NP-hard to break.  None.  So we can't provide you examples, because none are known.

Answer to your original question:

The analysis at Why hasn't there been an encryption algorithm that is based on the known NP-Hard problems? also applies to public-key exchange.

Cryptography requires average-case hardness.  NP-hardness relates to worst-case hardness; it has no notion of a distribution on inputs, probability, or any kind of "average".  Worst-case hardness does not appear to imply average-case hardness: there are many problems that are believed to be hard in the worst case, but easy in the average case. Status of Impagliazzo's Worlds?
 has some pointers on this topic.


Is the validity of some instance of an equational problem decidable?

This problem is known as rigid E-unification. This problem is NP-complete. The first proof was given by Gallier, Narendran, Plaisted and Snyder [1].

However a related problem, the Simultaneous rigid E-unification that is to find a substitution that simultaneously satisfies several instances of rigid E-unification is undecidable. This result was proved by Degtyarev and Voronkov [2].

References

Jean H. Gallier, Paliath Narendran, David A. Plaisted, Wayne Snyder: Rigid E-Unification: NP-Completeness and Applications to Equational Matings Inf. Comput. 87(1/2): 129-195 (1990)
Anatoli Degtyarev, Andrei Voronkov: The Undecidability of Simultaneous Rigid E-Unification. Theor. Comput. Sci. 166(1&2): 291-300 (1996)


Let $k_P$ and $k_C$ be the maximum length of a Hamiltonian path and cycle, respectively, in the resulting graph $G$ (with $n$ vertices, $n\geq 5$). If the input is given to you, then $4\leq k_P\leq n-1$ and $4\leq k_C\leq n$.

The lower bound can be achieved when vertices $4,\ldots,n$ are all joined to vertices $1$ and $3$. In this case $C=(1,2,3,4)$ and $P=(2,1,4,3,5)$ are longest cycle and path, respectively.

The upper bound can be achieved when vertex $i$ is joined to vertices $i-1$ and $i-2$, $4\leq i\leq n$. In this case you get an outerplanar 2-connected graph, which is Hamiltonian, so $k_P=n-1$ and $k_C=n$.

Not sure how to find $k_P$ and $k_C$ in general since, during the construction, the property that the graph is Hamiltonian (and therefore the length of the longest path/cycle) is changing depending on how edges are added.


The answer to the partial question is no. It’s impossible to be so efficient by a counting argument. First, there are $2^n$ cells, each of which is either colored or not. So there are $2^{2^n}$ possible configurations, each of which has to be represented in polynomial space. This is impossible.


using orientation sensor data to predict image points

It turns out that I had two bugs that broke my experimental results:

Even though the rotation matrix reports the rotation from Earth to Device, I should have been applying the opposite rotation to the point. It took me a day to convince myself of this.  Basically, if you rotate the whole frame about, e.g., $+x$, then coordinates that remained fixed w.r.t. the device will rotate w.r.t. the Device frame about $-x$.
I had a wrong minus sign in the rotation about the y-axis in the experimental results that I reported at the end.  Note that y-axis rotations have a different +/- pattern than x- and z- axis rotations.  See wikipedia for basic rotations.

The method described herein works fine (at least in theory).  I'll post an update after I port my python dummy code into Android and see how it works.


This is the best way to Find $X$. Your algorithm is basically binary search, which is optimal in terms of comparisons.

Let $T(N)$ be the number of ball-drops required in a building with $N$ floors to find $X$.
\begin{align}
T(1) = & 0 & \text{(no balldrop with one floor)}\\
T(N) = & T(\frac{N}{2}) + 1& \text{(drop ball once, repeat on upper/lower half)} \\
      = & T(0) + 1 + \ldots + 1 \in \mathcal{O}(\log n)
\end{align}

Each floor $i$ of the $N$ floors can be represented as binary number with $\lceil \log_2N\rceil$ bits. To identify one number out of a set of $N$ numbers, you have to look at each single bit, hence this takes you $\lceil\log_2 N\rceil \in \mathcal{O}(\log n)$ comparsons. So in terms of complexity, there is no better way to find $X$.

Of course, you could check one floor above as well as one floor under the current floor, which covers the cases $X=\frac{N}{2}+1$ and $X=\frac{N}{2}-1$, respectively. But you this does not improve your algorithm in terms of $\mathcal{O}$ complexity. Furthermore, you can always construct another worst case for you algorithm, since $N$ is unbounded: The improved algorithm performs poorly when $X=\frac{N}{2}-2$ or $X=\frac{N}{2}+2$. So you could add those cases as well. But then $X=\frac{N}{2}-3$ and $X=\frac{N}{2}+3$ becomes a problem ...


How do you represent an r.e. complexity class with a list of TMs?

Its easy to iterate through all turing machines - simply iterate through all strings, and pick the ones that actually represent a TM.

I think its possible to iterate through all $P$ by iterating through all turing machines, and for each one to add a "clock" that counts the number of steps and halts after some polynomial time.


Do I need to consider instance restrictions when showing a language is in P?

I was wondering if my algorithm has to decide whether the input is of the desired instance ON TOP OF actually showing the properties of the language can be done in polynomial time.

Very nice question!

What you are talking about is best characterized as promise problem, "a generalization of a decision problem where the input is promised to belong to a particular subset of all possible inputs". The conventional way to handle promise problem is there are no requirements on the output if the input does not belong to the promise. In particular, if you want to show a promise problem is in P of promise problems, your algorithm do not need to check whether the input is valid or not and your algorithm can behave arbitrarily if the input is invalid.

For an in-depth educational survey on promise problems, you are encouraged to read Oded Goldreich's exposition On Promise Problems, July 11, 2005.

However, if you want to show a promise problem is in P, your algorithm must check whether the input is valid or not and, if the input is invalid, a.k.a as a noninstance, output 0. Here P stands for the complexity class as in the famous P versus NP problem, a.k.a. P of decision problems, i.e. PTIME or DTIME$(n^{O(1)})$ as defined at Wikipedia, or the complexity class P as defined in section 34.1 Polynomial time of the popular textbook introduction to algorithm by CLRS, version 3.

Take 3SAT for an example. An algorithm that show 3SAT is in P (of decision problems) should check whether the input is a formula in conjunctive normal form each of whose clauses contains at most three literals among other restrictions. The algorithm should output 0 if it finds the input is not a valid instance of 3SAT.

It is easy to check whether a problem instance is a valid instance or not for almost all decision problems people have been interested in. It is so easy and so common that people have become so sloppy or efficient that this verification step is usually skipped or even forgotten in the specification of an algorithm. That might be the source of your confusion.

I would recommend beginners to write clearly this verification step for the first few occasions before joining the common practice.


Why do some authors not include summation in the $\pi$-Calculus?

To answer this question, it's best to reflect on the meaning of sums in process calculi. Essentially sums express a lack of knowledge. The process $P + Q$ means something along the lines of "either $P$ or $Q$ is active, but I have absolutely no information which". Note that this is related to, but different from a probabilistic sum like
$P +_{0.5} Q$ which also expresses uncertainty about which process is active, but quantifies the uncertainty by stating that both outcomes are equally likely. So $P+Q$ expresses less information than $P +_{0.5} Q$.

A specific case of using sums to express uncertainty is the input process

$$
   x(v).P
$$

Cleary an process waiting on an input on channel $x$ is uncertain what input will be received, for otherwise there would not be a need to input something. Hence
input can be seen as a sum over all possible inputs, e.g. if we expect to get a natural $n$, then $
   x(v).P
$ really is the sum:

$$
   \Sigma_{n \in \mathbb{N}} xn.P\{n/v\}
$$

Here $xn.P$ is the process that inputs the number $n$ (seen as a constant) on $x$ and becomes $P$.

With this understanding of sums as an expression of uncertainty, the question
whether to include sums, and what kind of sum
 depends what you use the $\pi$-calculus for. There are two main uses.

If you use it as an idealised programming language, then you don't need sums other than the input prefix  $x(v).P$  (and possibly its replicated variant). Indeed what computation would $P+Q$ express?

If you use it to specify program behaviour, then you typically don't want to specify everything and instead express uncertainty by using sums of processes, e.g. $P + Q$. Typically you don't know exactly what the environment of a process is going to do, and use non-determinism to formalise this lack of knowledge.


Are there any known AM-complete problems/is AM-complete well defined?

Since AM = BP.NP, it seems the go to "reduction" to AM relies on randomized reductions to 3SAT rather than the Karp reductions we use for deterministic complexity classes.

This is a wrong intuition. Regardless of how you define your complexity class $\mathbb{C}$, if there exists any problem $\mathrm{A}\in \mathbb{C}$ such that for every problem $\mathrm{B}\in \mathbb{C}$, you have $\mathrm{B} \leq_p \mathrm{A}$, then $\mathrm{A}$ is a many-one complete problem of $\mathbb{C}$.

In fact, even a problem that is complete by randomized reductions for $\mathrm{AM}$ is not known. Put in other word, it seems very hard to just pin down any particular decision problem in $\mathrm{AM}$ so that we can have some non-trivial reduction from other problems known to be in $\mathrm{AM}$.

  See mathoverflow.net/questions/34469 and cstheory.stackexchange.com/questions/1233; in short, the definition of AM relies on a promise, and this makes it tricky to define a reduction. – sdcvvc

That is one of the obstacles on the way to find a complete problem for $\mathrm{AM}$. This is also applicable to $\mathrm{BPP}$, $\mathrm{RP}$, $\mathrm{co}$-$\mathrm{RP}$, $\mathrm{ZPP}$. These classes requires the poly-time probabilistic Turing machine to have bounded error probability on all instances. The situation is much easier for $\mathrm{PP}$, this class does not put any requirement on the error probability, whichever result has the higher probability is the answer of the machine so we can easily catch a complete problem for it, namely $\mathrm{MAJ}$-$\mathrm{SAT}$.


Priority queue for partially ordered priorities with infima

Although the exact problem posed in the original question does seem to be difficult (and I would be interested in a solution to that problem, especially the infima finding part). I just wanted to note that if the partially ordered set indeed consists of vectors using a product order, and if it is sufficient to just have the guarantee that the priority queue returns the values in an order that is "compatible" with the partial order (that is, smaller elements are always returned before larger elements), then there is a fairly easy way to do it.

The idea is essentially to find a topological ordering of the partially ordered set. That is, a total order '$\le_T$' such that $\mathbf{a}\le\mathbf{b}\implies \mathbf{a}\le_T\mathbf{b}$. For vectors using a product order, this is fairly easy: just use a lexicographical order '$\le_S$', where the first "component" is the sum of all the components used for the product order (the rest of the components are essentially arbitrary, so you could also stick to a weak order). We can then see that
$$\mathbf{a}<\mathbf{b}\implies \forall_i(a_i\le b_i)\text{ and }\exists_i(a_i<b_i)\implies(\sum_i a_i)<(\sum_i b_i)\implies\mathbf{a}\le_S\mathbf{b}$$
and
$$\mathbf{a}=\mathbf{b}\implies \forall_i(a_i=b_i)\implies(\sum_i a_i)=(\sum_i b_i)\implies\mathbf{a}\le_S\mathbf{b},$$
and thus that $\mathbf{a}\le\mathbf{b}\implies\mathbf{a}\le_S\mathbf{b}$. We can thus use this order with a priority queue and be sure that smaller elements (in the product order) will always be extracted before larger elements.


Algorithm for ensuring that each element ends up in its specified range when composing a list

Here is my guess at your problem.

There are a bunch of items that you need to place in a vector.

Each item has a set of allowed positions in the vector.

You need to find an assignment of items to positions in the vector.

This is an instance of bipartite maximum matching. On one side you have the items, on the other you have the positions in the vector. You add an edge if the item can be put in the position. A maximum matching is one that puts each item in an allowed position, without collisions.


Creating artificial NP-Complete problems

Dodging any questions about whether this is "interesting" or "artificial" (or whether Computer Science really needs any more NP-complete problems than it already has), the answer is "yes".  Pick a structure-preserving mapping between some set of strings and problem instances of 3SAT.  Show that the mapping can be computed in polynomial time (i.e., it is a polytime reduction).  Then, deciding if a string is in your set of strings is NP-complete.  Repeat as desired (the composition of polytime reductions is a polytime reduction.)

If you wanted to automate this process of creating new NP-complete problems, then it would likely be more efficient to construct the mappings from some base set of polytime mappings, using methods known to preserve polynomial time, rather than picking an arbitrary mapping and proving that it is a polytime reduction.

Note that this is not quite what you suggest in your question.  You can take a logical formula and build a Turing machine corresponding to it, but that in itself doesn't lead to an NP-complete problem.  For instance, 2SAT instances can be decided in polynomial time.  And a particular formula will only correspond to a particular machine, whereas you need a set of formulas (or machines) to define a complexity class; so to make new problems in NPC, you really need to show how one set can be converted into another (i.e. a polytime reduction), even if your sets are sets of logical formulas.