What problems of procedural programming does OOP solve in practice?

In a procedural language you can't necessarily express restrictions that are required to prove that the caller is using a module in a supported fashion.  In the absence of a compiler checkable restriction, you have to write documentation and hope that it is followed, and use unit tests to demonstrate intended uses.

Declaring Types is the most obvious declarative restriction (ie: "prove that x is a float").  Forcing data mutations to pass through a function known to be designed for that data is another.  Protocol enforcement (method invoke ordering) is another partially supported restriction ie: "constructor -> othermethods* -> destructor".

There are also a real benefits (and a few drawbacks) when the compiler knows about the pattern.  Static typing with polymorphic types are a bit of a problem when you emulate data encapsulation from a procedural language.  For example:

the type x1 is a subtype of x, t1 is a subtype of t

This is one way to encapsulate data in a procedural language to have a type t with methods f and g, and a subclass t1 that does likewise:

t_f(t, x, y, z, ...), t_g(t, x, y, ...)
t1_f(t1, x, y, z, ...)

In order to use this code as it is, you have to do a type check and switch on type of t before deciding the kind of f you will invoke.  You could work around it like this:

type t {
  d : data
  f : function
  g : function
}

So that you invoke t.f(x,y,z) instead, where a typecheck and switch to find the method is now replaced with just having each instance store method pointers explicitly.  Now if you have a huge number of functions per type, this is a wasteful representation.  You could then would use another strategy like having t point to a variable m which contains all of the member functions.  If this feature is part of the language, then you can let the compiler figure out how to deal with making an efficient representation of this pattern.

But data encapsulation is recognition that mutable state is bad.  The object oriented solution is to hide it behind methods.  Ideally, all of the methods in an object would have a well defined calling order (ie: constructor -> open -> [read | write] -> close -> destruct); which is sometimes called a 'protocol' (research: "Microsoft Singularity").  But beyond construct and destruct, these requirements are generally not part of the type system - or well documented.  In this sense, objects are concurrent instances of state machines that are transitioned by method calls; such that you might have multiple instances and use them in an arbitrarily interleaved fashion.

But in recognizing that mutable shared state is bad, it can be noted that object orientation can create a concurrency problem because the object data structure is a mutable state that many objects have a reference to.  Most object oriented languages execute on the thread of the caller, which means that there are race conditions in the method invocations; let alone in non-atomic sequences of function calls.  As an alternative, every object could get async messages in a queue and service them all on the object's thread (with its private methods), and respond to the caller by sending it messages.

Compare Java method calls in a multi-threaded context with Erlang processes sending messages (that only reference immutable values) to each other.

Unrestricted Object Orientation in combination with parallelism is a problem due to locking.  There are techniques ranging from Software Transactional Memory (ie: ACID transactions on in memory object similar to databases) to using a "share memory by communicating (immutable data)" (functional programming hybrid) approach.

In my opinion, Object Orientation literature focuses FAR too much on inheritance and not enough on protocol (checkable method invocation ordering, preconditions, postconditions, etc.).  The input that an object consumes should usually have a well defined grammar, expressible as a type.


Do you know of a brute-force algorithm for optimizing polynomial expressions?

"Brute-force" in the context of factoring polynomials may involve factoring of integers, which is a hard problem. Factoring polynomials is easier, e.g. look up "FACTORING MULTIVARIATE POLYNOMIALS VIA PARTIAL DIFFERENTIAL EQUATIONS" by Gao, and "Factoring Multivariate polynomials over the integers" by Wang and Rothschild.


Converting final state PDA to empty stack PDA

Your description of the construction is wrong. The new automaton has a new initial stack symbol, from the new start state it places the original PDA's initial stack on top of it and moves to the original's start state. The new initial stack can only be removed in a new state that is entered via $\epsilon$ from final states, and in this new state all that is done is to slurp down the stack's contents.

This is activated from any final state, and the automaton can end up with empty input and empty stack only if the original reached the final state at the end of the input.


array median transformation using the min number of steps

In the comments, Wu Yin claimed an upper bound of $\lceil \log_2 n \rceil$, although I think this is only true if the position of the maximum is known. In fact, consider the following argument. Assume $A$ is filled with $N-1$ ones and one maximal element $\max$. Any first step on a subarray $A[x,y]$ of more than 2 elements will necessarily set the subarray to all $1$'s. In particular, if we don't know the position of $\max$, we can only apply a step to subarrays of length 2, or otherwise we run the risk of "destroying" our maximum element. Hence, without knowing the position of our maximimal element, we can only probe the array by consecutively applying the operation to $A[i,i+1]$ for all $i$. This will necessarily create a subarray of length 2 that is filled with $\max$. Recurring leads to a linear time algorithm, which I think is optimal.

Algorithm:

Let $step(x,y)$ denote an operation on the subarray $A[x,y]$ as is defined in the question.

Perform $step(i,i+1)$ for all $0\leq i < N$. After that, there is some 2-length subarray containing only $\max$.
Perform $step(i,i+3)$ for all $0\leq i < N-3$. After that, there is some 4-length subarray filled with $\max$.
Generally, we double in each such iteration the array size in each step. After that, the original array $A$ contains only $\max$.

Running Time:

In the first iteration, we perform $N/2$ steps, in the subsequent one, $N/4$, then $N/8$, etc. The sum over all this is smaller than $N$. I think this is optimal, since without looking at all elements (or at least $N/2$ elements), we don't know where $\max$ is, and can not use any step on any subarray larger than $2$.


No compression algorithm can compress all input messages?

What you are missing is that you need to consider all bits of size 3 or less. That is: if in a compression scheme for bits of size 3 or less we compress one of the 3-bit strings to a 2-bit string, then some string of size 3 or less will have to expand to 3 bits or more.

A losless compression scheme is a function $C$ from finite bit strings to finite bit strings which is injective, i.e., if $C(x) = C(y)$ then $x = y$, i.e., $C(x)$ uniquely determines $x$.

Consider an arbitrary compression scheme $C$ and let $S$ be a set of binary strings. We can express how well $C$ works on $S$ by computing the ratio
$$\text{CompressionRatio}(C,S) = \frac{\sum_{x \in S} \mathrm{length}(C(x))}{\sum_{x \in S} \mathrm{length}(x)}.$$
A small compression ratio is good. For example, if it is $1/2$ that means we can on average compress strings in $S$ by 50% using $C$.

If we try to compress all strings of length at most $n$ then we are in trouble:

  Theorem: Let $S$ be the set of all strings of length at most $n$ and $C$ any compression scheme. Then $\text{CompressionRatio}(C,S) \geq 1$.

So, the best compression scheme in the world is the identity function! Well, only if we want to compress random strings of bits. The bit strings which occur in practice are far from random and exhibit a lot of regularity. This is why it makes sense to compress data despite the above theorem.


How to interprocess communication and scheduling algorithms interact?

Such interaction arises when a high-priority task needs to communicate in some way with a low-priority task. Scheduling algorithms may need to take into account such communication. For example, see http://en.wikipedia.org/wiki/Priority_inversion .


Time complexity of mutually recursive functions

If we set up recurrences, $T_1(n) = T_1(n-1) + T_2(n-1)$ and $T_2(n) = T_1(n-1) + T_2(n-1)$. So from there we can get that $T_1(n) = T_2(n)$, which implies that $T_1(n) = 2T_1(n-1)$. So for this, the two functions would be $O(2^n)$.


How literally is "optimization" or "optimization algorithm" used in CS?

There is no governing body mandating the meaning of terms in computer science. Instead, just like all human language, the meaning of a term is defined implicitly by its use, and could depend on the language community.

In theoretical computer science, optimization is a wide topic that covers many different problems. The most common problem is to find the maximum or minimum of a function subject to constraints. Often one is interested in finding an approximate optimum, or an approximate optimum which only approximately satisfies the constraints (this is known as a bicriteria approximation).

When finding even an approximate optimum turns out to be difficult, it is reasonable to consider finding a local optimum or an approximate local optimum. This happens, for example, in machine learning, and is actively pursued by the optimization community.

Summarizing, there is no official meaning of the term optimization in computer science, any more than there is an official meaning of this term in English. In practice, in the theoretical computer science community, the term is widely used in the more relaxed sense corresponding to your second definition, and beyond.


Is the language of binary representation of perfect squares regular?

We start with a lemma.

Lemma. Let $a>b \geq 4$. If $2^a+2^b+1$ is a square then $a \geq 2b-3$.

Proof. Let $2^a+2^b+1 = x^2$. Clearly $x$ must be odd, say $x = 2y+1$. Then $x^2 = 4y^2 + 4y + 1$, and so $(y+1)y = y^2+y = 2^{a-2} + 2^{b-2} = 2^{b-2}(2^{a-b}+1)$. If $y$ is even then $y+1$ is odd and so $y = 2^{b-2}z$ for some odd $z$, and therefore $2^{a-b}+1 = (2^{b-2}z+1)z \geq 2^{b-2}+1$ and so $a \geq 2b-2$. If $y$ is odd then necessarily $y+1 = 2^{b-2}z$ for some odd $z$, and therefore $2^{a-b}+1 = z(2^{b-2}z-1) \geq 2^{b-2}-1 = 2^{b-3} + 1 + (2^{b-3}-2)$. Since $b \geq 4$, we can conclude that $a \geq 2b-3$. $\square$

Let $L' = L \cap 10^*10^*0001$. According to the lemma, all words in $L'$ are of the form $10^{a-b-1}10^{b-1}1$ with $a-b-1 \geq (b-1)-3$. Moreover, since $2^{2c} + 2^{c+1} + 1 = (2^c+1)^2$, for all $c \geq 3$, $10^{c-2}10^c1 \in L'$.

If $L$ is regular then so is $L'$, say its minimal DFA has $p$ states. Consider the word $10^{p-2}10^p1 \in L'$, and mark the substring $0^p$. The extended pumping lemma shows that for some $0 < q \leq p$, $10^{p-2}10^{p+q(t-1)}1 \in L'$ for all $t \geq 0$. However, according to our lemma, for all $t$ we must have $p-2 \geq p+q(t-1)-3$ and so $1 \geq q(t-1)$, which is false for $t \geq 3$.


How to find the distance between two nodes in an undirected graph, from a neighborhood matrix?

I assume that by distance-$2$ matrix you mean the matrix $A$ such that $A_{ij}=1$ if there is a path of length exactly $2$ between node $i$ and node $j$.

Let us call $B$ the distance-$1$ matrix, then remember that $B^2$ is such that $(B^2)_{ij}$ is the number of paths of legth $2$ between $i$ and $j$. So all you have to do is to check whether an entry of $B^2$ is $0$ or not.


Do all states in a DFA must be connected?

I suspect a trick question in the material you are studying - there are no DFAs with an infinite number of states in the first place.

in fact, the whole point of D/NFAs is their finiteness. if you could have an inifinite number of (reachable) states in your NFA you'd actually be able to recognize any language; just take for every word in your language the trivial deterministic recognizer and connect a global start state with $\lambda$-transitions to the start state of each of these automata.


LTL to automaton translation that can only read disjunctions of labels per transition

The models of an LTL formula $\varphi$, with atomic propositions $P$, are infinite words $w = \sigma_0\sigma_1\ldots$, where each $\sigma_i$ is a subset of $P$. To recognize such words, the edges of an automaton recognizing the language of $\varphi$ generally have to be labeled by symbols in $2^P$ (i.e. subsets of $P$).

Often multiple transitions are grouped by labeling edges in the automaton with boolean formulas over $P \cup \tilde{P}$, where $\tilde{P}$ is the set of negated atomic propositions. The edge label $f$ then stands for all models of $f$. In nondeterministic Büchi automata we can restrict $f$ to be a conjunction, as disjunction in the label can be modeled by introducing another transition.

Universal automata are the dual of nondeterministic automata, so to accept a word $aw, a \in \Sigma, w \in \Sigma^{\omega}$ from a state $q$, $w$ has to be accepted from all $a$-successors of $q$. Combining universal and nondeterministic branching one gets alternating automata. In universal automata for LTL formulas you can restrict the edge label to be a disjunction over $P \cup \tilde{P}$, as you can model conjunction in the label by introducing another transition.

With the right acceptance universal automata are as expressive as LTL, for example co-Büchi universal automata can recognize all $\omega$-regular languages.

Edit: I don't think this is a good answer after second thought. The reason is that grouping transitions in this way makes no sense for universal automata, unless the formulas on the labels have disjoint models.
Example:
Splitting $x \xrightarrow{a \land b} y$ into $x \xrightarrow{a} y$ and $x \xrightarrow{b} y$ adds the possibility to move to $y$ when only satisfying $a$, which was not possible before.
I don't see any natural way of having an automata with only disjunctive boolean formulas as edge labels, however you can get rid of the formulas entirely on the edge labels by just using symbols in $2^P$.


Suggest how to allocate and deallocate storage for elements within the hash table itself by linking all unused slots into a free list

Practical implementations that I have seen worked like this:

In a hash table, a slot is either used (contains a hash value and a value), has been never used, or has been used and emptied, and we need to distinguish this. With no additional space if at all possible.
If the values are pointers, and neither “all bits zero” nor “all bits one” are valid pointers, then we store “all bits zero” or “all bits one” as data to mark a “never used” or “not used anymore” slot.
If (2) doesn’t work: There are many more possible hash values than slots. Therefore most hash values never happen. We pick two random hash values which we store as the hash value to represent “empty” and “not used anymore” slots. As long as these are not used, fine. If they are used, we pick two different random hash values and modify the table accordingly (number of slots used should be less than the square root of possible hash values).

I’ve never seen a “free list” being used, because the hash value determines where an entry needs to be stored. Everyone just uses an array.


What is the complexity of deciding if the intersection of a regular language and a context free language is empty?

The answer depends on how the two languages are given to you; I will assume that the context-free language is given as a CFG, and that the regular language is given as a DFA/NFA. Beigel and Gasarch show how to compute a CFG for the intersection in polynomial time. You can then check whether the resulting language is empty using grammar simplification (described in any decent textbook).


Find the fixed point $(x_l,y_l)$ just to the left of your $x$-value, and the fixed point $(x_r,y_r)$ just to the right of your $x$-value.  Then use the line between those two fixed points to interpolate.

To find the fixed point to the left and the fixed point to the right, store the fixed points in sorted order (sorted by their $x$-coordinate).  Then you can use binary search to find the fixed point to the left and to the right.

To deal with wrap-around, take the left-most fixed point and add a wrapped-around copy above the upper limit, and similarly add a copy of the right-most fixed point.  For instance, suppose the limit is 0..100, and the left-most fixed point is $(5,20)$ and the right-most fixed point is $(98,3)$.  Then you should add the two additional points $(105,20)$ and $(-2,3)$.  Now apply the algorithm above.


Efficiently compute a complete set of representatives of cyclotomic cosets of $2$ modulo $2^n-1$

You can use simple enumeration.  This will be about as fast as you can achieve, for a modulus of the form $2^n-1$.

Namely, for each possible $k$, you check whether $C_k$ is a new set (distinct from the ones you already know about).  If it is, you add it to the set; if it isn't; you skip it and move onto the next $k$.

This gives an algorithm like the following:

Set $S := \emptyset$ and $A := \emptyset$.  ($A$ holds the set of representatives; $S$ holds the set of elements covered by one of the corresponding cyclotomic classes.)
For each $k=1,2,\dots,2^n-1$:

If $k \notin S$, add $k$ to $A$ and set $S := S \cup C_k$.

The running time of this algorithm will be $\Theta(2^n)$.

This is also within a $\Theta(n)$ factor of optimal.  In particular, any algorithm must have running time at least $\Theta(2^n/n)$.  The reason is that, for a modulus of the form $2^n-1$, the output size of any correct algorithm must be $\Theta(2^n/n)$: there are $\Theta(2^n/n)$ distinct cyclotomic classes.  Therefore, no algorithm can run faster than $\Theta(2^n/n)$ time, since it will take at least $\Theta(2^n/n)$ time to print/construct the desired output.

Why is the output size $\Theta(2^n/n)$.  Well, for the specific modulus $2^n-1$, it is guaranteed that each cyclotomic class has size $n$.  (Proof: $2^n \equiv 1 \pmod{2^n-1}$, so no cyclotomic class can have size larger than $n$.  Also $2^j < 2^n-1$ when $j<n$, so $2^j \not\equiv 1 \pmod{2^n-1}$ when $j<n$.  Therefore each cyclotomic class has size exactly $n$.)  This result is specific to the particular kind of modulus you are focusing on.


First, notice that $3 > \ln 7$. You can prove this formally using the Taylor expansion of $e^x$:
$$
e^3 = \sum_{n=0}^\infty \frac{3^n}{n!} \geq 1 + 3 + \frac{9}{2} = 8.5 > 7.
$$
Monotonicity of $\ln$ implies that indeed $3 > \ln 7$.

Armed with this knowledge, we deduce that for $n \geq 1$,
$$
n^3 = n^{3 - \ln 7} n^{\ln 7} \geq n^{\ln 7}.
$$
This shows that $n^{\ln 7} = O(n^3)$, using the definition of big O.

For your other question, try using $8^{\log_2 n} = n^3$ and induction. The idea is that as you increase $n$ by 1, the value of $n^3$ hardly increases, whereas $5^n$ increases by a factor of 5.

Finally, let me say that there is absolutely no reason to be so formal. It's enough to go through the formalities once, just to get convinced that they work, and afterwards you can just use well-known facts such as $n^k = o(c^n)$ for all $c > 1$.


find the strong component containing the vertex v

Since you are not trying to write an optimal algorithm, like this one or that one, I suggest you do not try to optimize space usage too much, especially if the optimization only diminish the multiplicative constant, but not the asymptotic space complexity.
All your ideas are sound. During a BFS, since you need to check if vertices are seen or not, the common way to do it is to use a boolean array. Now for a strongly connected component, you will run two BFS's, and use two boolean arrays. The intersection can be computed by a index-wise AND.


How do we know INVERSIONS-COUNT algorithm implemented in balanced tree really works?

At step $i$, the rank of $L[i]$ in $T$ is the number of elements in $L[i],\ldots,L[|L|-1]$ which are at most $L[i]$. Taking into account the $-|L|$ in the beginning, we see that the algorithm counts the number of pairs $i<j$ such that $L[j] \leq L[i]$, which is exactly the number of inversions (assuming all elements are distinct).


Overall time complexity of Heuristical Algorithm for travelling salesman problem [TSP]

Any algorithm that first does $A$ of work and then $B$ of work will have done a total of $A+B$ of work. It doesn't matter what the algorithm is, or what $A$ or $B$ are.

You might be getting confused by steps that look complicated and/or by the fact that $A$ and $B$ are expressed in terms of $\Theta$. For this reason and in general, it is a good idea to try to compute $A+B$ as well as possible, and then finally expressing the sum in terms of Big Oh. Otherwise, you run the risk of performing voodoo, and not really understanding what $\Theta$ means.


What is the complexity of this matrix transposition?

You can also "transpose" a matrix in $O(1)$ time and space. Maintain a bit $t$ for your matrix $M$. Whenever $M$ is transposed, flip $t$. Now, consider accessing an entry in $M$. If $t$ is set to true, return $M[j,i]$ instead of $M[i,j]$. This trick is arguably cheating, but not always is the matrix actually needed to be transposed. This might work nicely depending the situation.


How are kernels (and operating systems in general) written in C?

Today, you can definitely write an OS in C because you have compilers readily available on some OSes. You just have to decide with what executable format you are going to go and then parse it from a bootloader like a UEFI bootloader which has to be written in C as well. Linux is compiled to an ELF executable which is then compressed. Linux follows the multiboot specification (https://www.gnu.org/software/grub/manual/multiboot/multiboot.html) which allows one bootloader (GRUB) to boot the Linux kernel by following the specification.

Am I right in thinking that fork, malloc, etc. are wrapper methods that call the Kernel?

You are quite right. For example, when you write a C app on Linux, you are probably using gcc to compile your app. gcc comes with glibc which is the library implementation of the C standard on Linux. You can look at the source code of glibc (https://github.com/lattera/glibc) to look at the implementation.
For example, malloc is in malloc/malloc.c. Its definition is a one liner like strong_alias (__libc_malloc, malloc) (https://code.woboq.org/userspace/glibc/malloc/malloc.c.html#malloc). I didn't study the source code much but I think this means that a malloc call is a __libc_malloc call. The link I provided is good because it has the function definitions to the right that you can click on to go to the line.
__libc_malloc definition
void *
__libc_malloc (size_t bytes)
{
  mstate ar_ptr;
  void *victim;
  void *(*hook) (size_t, const void *)
    = atomic_forced_read (__malloc_hook);
  if (__builtin_expect (hook != NULL, 0))
    return (*hook)(bytes, RETURN_ADDRESS (0));
#if USE_TCACHE
  /* int_free also calls request2size, be careful to not pad twice.  */
  size_t tbytes;
  checked_request2size (bytes, tbytes);
  size_t tc_idx = csize2tidx (tbytes);
  MAYBE_INIT_TCACHE ();
  DIAG_PUSH_NEEDS_COMMENT;
  if (tc_idx < mp_.tcache_bins
      /*&& tc_idx < TCACHE_MAX_BINS*/ /* to appease gcc */
      && tcache
      && tcache->entries[tc_idx] != NULL)
    {
      return tcache_get (tc_idx);
    }
  DIAG_POP_NEEDS_COMMENT;
#endif
  if (SINGLE_THREAD_P)
    {
      victim = _int_malloc (&main_arena, bytes);
      assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
              &main_arena == arena_for_chunk (mem2chunk (victim)));
      return victim;
    }
  arena_get (ar_ptr, bytes);
  victim = _int_malloc (ar_ptr, bytes);
  /* Retry with another arena only if we were able to find a usable arena
     before.  */
  if (!victim && ar_ptr != NULL)
    {
      LIBC_PROBE (memory_malloc_retry, 1, bytes);
      ar_ptr = arena_get_retry (ar_ptr, bytes);
      victim = _int_malloc (ar_ptr, bytes);
    }
  if (ar_ptr != NULL)
    __libc_lock_unlock (ar_ptr->mutex);
  assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
          ar_ptr == arena_for_chunk (mem2chunk (victim)));
  return victim;
}

__libc_malloc calls _int_malloc which does the main work. It is very long so you can browse it on the link I provided. It is defined as:
/*
   ------------------------------ malloc ------------------------------
 */
static void *
_int_malloc (mstate av, size_t bytes)

I'm pretty sure that this is the malloc you are looking for. In _int_malloc there are these lines:
/* There are no usable arenas.  Fall back to sysmalloc to get a chunk from
     mmap.  */
  if (__glibc_unlikely (av == NULL))
    {
      void *p = sysmalloc (nb, av);
      if (p != NULL)
        alloc_perturb (p, bytes);
      return p;
    }

If there are no usable free chunks in already allocated memory, fallback to mmap to get more memory. sysmalloc is again very long but it calls mmap as a macro defined like:
#define MMAP(addr, size, prot, flags) \
 __mmap((addr), (size), (prot), (flags)|MAP_ANONYMOUS|MAP_PRIVATE, -1, 0)

Do the OS components' code call the Kernel the same way you would call a library? Is it more like it's a microservice you make calls to? When we say that Windows provides a 'hosted' implementation of C, is this what the methods are doing under the hood?

When you write a C app on Linux, you include headers from glibc to use the standard functions like malloc, fork etc. When you compile your app, you either compile it statically or dynamically. When you compile it statically, you include all the kernel code in the executable like mmap's code. Basically, when mmap is called from your main function, the CPU jumps to the function which is mapped in virtual memory. Where it "stops" including the code, is when you jump to kernel code using int 0x80 on older x86 32 bits processors. I don't know about the system call convention for x86-64 honestly. It is probably similar. When your code calls int 0x80 on x86, it interrupts the CPU and it jumps to shared-by-all-processes kernel code. This kernel code cannot be included in your executable because it is interrupt code. So mmap is included in your executable up until the system call. The rest of the work is done in the interrupt handler and then returns to mmap which now has the new address of the allocated memory chunk. mmap then returns to the glibc caller which, like you said, is a wrapper around kernel code calls. When you link dynamically, it is the same except linking happens just before runtime.

When you have a 'freestanding' implementation of C, are the standard libraries written in Assembler, but have C headers?

You don't need to write the implementation of C in assembly. glibc is written completely in C. Most of the Linux kernel is also written in C. Some parts of the kernel code needs to be written in inline assembly. For example, the system calls need to be done with a int 0x80 call that you can't make from pure C.

Are the freestanding components of a hosted C implementation implemented the same way they would be if they were freestanding?

This is a lot of terminology and I don't get what you mean by freestanding and hosted here. A freestanding implementation means that you use only the base of C because you don't have access to library functions like you would in a development environment like Windows or Linux. For example, an OS needs to be written in static, freestanding C because you need all code to be included in the final executable and because you can't depend on a runtime which includes things like standard libraries, system calls and other stuff like that. Actually, freestanding means that you really use only the components of C that you know are going to be included in the final executable and which are going to be compiled to assembly which doesn't depend on a particular runtime.

How do you implement memory and process management in C, what is exposed to allows you to do this in the language? (what do you call to interact with memory / devices / interrupts?)

C includes pointers which allow to do all that and more. In a freestanding environment (like when you develop an OS), you can just use absolute addresses and it just works because you don't have things like memory protection. You do have memory protection but you are the one in control of it. If you just type something like int* pointer = (int*) 0x8000;, you have a pointer of type int which points to 0x8000. If you type *pointer = 0x34, then at the address 0x8000 is now 0x00000034. That is because an int is 4 bytes. If you type unsigned char* pointer = (unsigned char*) 0x8000, and then *pointer = 0x34, at the address 0x8000 is now 0x34. That is because a char is one byte. You see that you can control memory pretty easily in C. You can put whatever values you want at the byte level. You can even work at the bit level using bitwise operators.
Today, most devices have memory mapped registers. By accessing memory using pointers, you can write commands to the registers of these devices and tell them to do stuff. If you ever need to access some IO ports or to do a system call like with int 0x80 then you have inline assembly from C which allows to do it. Also, the BIOS builds ACPI tables in RAM in conventional position which allows the OS kernel to find the location of the different registers.
Hope this answers your questions.


In the dual boolean algebra, NOT is the same NOT operation we have in the original boolean algebra.

Your book does not say anything to handle NOT because there's nothing that needs to be done. Simply leave the NOTs unaffected in your formula.


Is there any importance in problems whose witness for membership in a set, cannot be bounded by a polynomial?

If we remove the condition on the size of the witness, then a problem is in the resulting class NANY iff it is recursively enumerable.

Indeed, if $L$ is in NANY, then given $x$, we can go over all possible $y$, and for each of them run the machine that decides whether $y$ is a witness for $x \in L$.

In the other direction, suppose that the Turing machine $M$ halts on $x$ iff $x \in L$. We can use the transcript of a halting computation as a witness that $x \in L$.


Which would be the most purely functional equivalent to generators?

Functional programming does not have to be pure or stateless.  There's no strict rule.  Languages that are designed to support first-class functions and higher-order functions can still be considered functional languages.  For instance, Standard ML has support for mutable variables but is still considered a functional language.

Also, functional programming can be considered a style of organizing your program rather than a property of a programming language.  So, it is possible to use Python in a functional way.

A Python generator can be written in a way so that it is purely functional: e.g., it produces a lazy list/stream and operates in a purely functional way.  Internally, generators might be implemented in a way that involves state, but from the outside (from the perspective of code that invokes a generator), I think it is possible to write the generator so it behaves in an observationally pure way (i.e., observationally indistinguishable from pure).

I'm not sure what you mean by "purely functional alternatives for having a construct similar to generators" so I don't know how to answer that part.


Suggest a data-structure that supports the following operations with time complexity of $ O(log(n)) $

AVL tree - it does support the basic methods with this complexity, but in order to find which elements are larger, I need to search through all tree which can cost more than log(n).

Not quite. In order to change all those entries, yes; but by searching for $x$ you can identify all nodes that have greater values: all nodes you visit and have key $> x$, namely those where you go left, and their right subtrees.

  Further more, I can mess the tree up if I for instance make a left son be larger than it's parent.

No, and that may be the key insight. If we increase all keys $>x$ by some constant we maintain the search-tree property! In particular, you never increase a left son and not its parent!

These two observations lead us to the idea: use AVL-trees (or any balanced search tree, I daresay) and execute key increments lazily. For that, add to every node an integer inc that is initially $0$.

Now, a call updateKeys(x,v) proceeds as follows.

Search for x using usual BST search.
Whenever you go left at some node y,

increase y.key by v and
increase y.right.inc by v.

This adds at most constant overhead per visited node, so it has the same $\Theta$-running-time as search.

We execute the updates whenever we traverse the tree anyway. That is, augment all four operations so that when they access some y.key they execute this first (if y.inc > 0):

y.left.inc  += y.inc
y.right.inc += y.inc
y.key       += y.inc
y.inc        = 0

This adds at most a constant amount of effort per visited node for all the operations, so it does not change their $\Theta$-bounds on time. We do need a linear amount of extra memory, but that seems to be allowed.

Detailed pseudocode and proofs of correctness are good exercises.


What is a "closed set" in context of AI? How is it different from an open set or a frontier?

There are two variants of the A* algorithm:

The standard algorithm maintains two sets of vertices.  One called the "open set", and the other is called the "closed set".
An alternative version maintains just an open set, and doesn't use a closed set.  This requires that the heuristic function satisfy some some additional conditions.

See any standard treatment of A* for explanation of how it works and what the closed set is; e.g., A* search.


Can you operate on and draw conclusions on functions described asymptotically?

For some operations, such as addition, multiplication, you can operate directly on the asymptotic notation. For example, if $\small g(n) = \mathcal{O}(n^2)$ and $\small f(n) = \mathcal{O}(n^2)$, then $\small g(n) + f(n) = \mathcal{O}(n^2)$ and $\small g(n) \cdot f(n) = \mathcal{O}(n^4)$. For some other operations, such as division, it depends then. For example, for $\small g(n) = \mathcal{O}(n^2)$ and $\small f(n) = \mathcal{O}(n^2)$, it is not correct to say $\small \frac{g(n)}{f(n)} = \mathcal{O}(1)$ (consider $\small g(n) = n^2$ and $\small f(n) = n$). However, if $c$ is a fixed constant, then $\small \frac{g(n)}{c} = \mathcal{O}(n^2)$.


What is the distribution of Garden of Eden patterns in cellular automata with increasing pattern size?

as said by vzn, any pattern containing a Garden of Eden pattern is itself a Garden of Eden Pattern, the probability that a random nxn pattern is actually GoE goes to 1 as n goes to infinity (in the case of a non-surjective CA of course, otherwise it's 0). More precisely, it is lower bounded by $1 - \alpha^{n²}$ for some $0<\alpha<1$.
Indeed, consider a fixed GoE pattern P of size $k\times k$, then the probability for a random pattern of size $n\times n$ to be a GoE is at least $1 - (\frac{1}{q^{k^2}})^{(\frac{n}{k})^2}$, where $q$ is the number of states of the CA.
you can generate all the possible pre-image of a given pattern in finite time and you can also test whether a pattern is a GoE so your problem is clearly decidable. It's polynomial-time decidable in 1D and NP-hard in 2D.

in the 1D case, a CA can be seen as a finite state transducer. So the language $L_{GoE}$ of all GoE patterns is a regular language because it is the complement of $T(Q^\ast)$ (where $T$ is the transducer and $Q$ the set of states of the CA) which is itself a regular language as the image of a regular language by a transducer. Then $T(L_{GoE})$ is also regular and its the set you asked.
in the 2D case, I think we can show that it is NP-hard using the classical simulation of Turing machines by Wang tiles. The rough idea is the following. Consider any NP-complete problem $L$ and take a Turing machine $T$ which is a polynomial time verifier for the problem. Then construct a CA that basically checks that the input, if written in some special alphabet $A$, encodes a successful computation $T(x,y)$ of $T$ working on input $x$ and witness $y$. If so erases everything with a special state $a\not\in A$, but keep the input x. If some error is detected produce some special state $b\not\in A$. Finally, the CA does nothing on states which are not in $A$. Now consider a pattern formed by an input $x$ surrounded by many $a$. The pattern as always itself as a preimage, but it as a GoE preimage if and only if there is some $y$ such that $T(x,y)$ says "yes", i.e. iff $x\in L$. CQFD
At the time of writing I don't see how to prove that the problem is NP

as pointed-out Turing-universality is still possible without GoE patterns (in reversible CA for instance). But intrinsic universality requires GoE patterns. This comes from the fact that, first, a surjective CA only admits surjective CA as subautomata, and, second, grouping and iterating a CA doesn't change its surjectivity.


A binomial random number generating algorithm that works when $Np$ is very small

If $Np$ is small then the distribution is very close to Poisson, which is easier to generate, especially when the expectation is small.

In your specific case, most of the time the result is zero, and the probability that this happens can be calculated exactly. This optimization will probably result in a speed-up of $10^3$.


defining a programming language grammar for doing arithmetic

With Num you can only generate digits, so the only choice left is (starting with Exp) to produce Exp Op Exp. However, Exp and Op must both produce at least one symbol each (i.e., producing the empty word is not allowed). Hence, even if you replace Op with -, you get Exp - 1 and Exp must produce another valid expression (or number), so you cannot get -1 on its own.

  Also could you show me how I could modify the above grammar to add the ability to group operations, and start with a -1?

There are several ways of doing so. Check out, for instance, how Java does it (the "Expression3" there is roughly equivalent to your Exp).

  Finally, I'm told that a grammar is a set of symbols, rules, and an initial symbol? But I'm struggling to find more info on what an initial symbol is/should be.

The initial symbol is an arbitrary non-terminal symbol. Read more here on what terminal and non-terminal symbols are.


The idea is to extract a pair of 1s one by one, so the key grammar is

\begin{align}
S&\rightarrow S_01S1S_2 \\
S&\rightarrow S_0S_2
\end{align}

where $S_0$ represents $0^*$ and $S_2$ represents $2^*$.


Without the mod p, the running time to check the condition would be exponential, which is unacceptable.  Also, it would require exponential space to store $w_3$ and to check the condition.
Also, the procedure involves choosing an integer $z$ uniformly at random from $\>0,\dots,p-1\}$.  You can choose an integer uniformly at random from $\{0,\dots,p-1\}$, but you can't choose it uniformly at random from the set of all integers.  So, you'd have to think about exactly what alternative approach you had in mind if you wanted to omit the mod p.


In your case finding the witness is easy. We know that for all $x \geq 0$, $2^x \leq 3^x$. Also, for $x \geq 3$, $17 \leq 3^x$. So for $x \geq 3$, $2^x+17 \leq 2\cdot 3^x$.

There is no particular method at work here – just problem solving.


Decomposing an Algorithm into Local Transformations/Perturbations

there are several ways to measure this "local vs global" decomposition dichotomy of problems which does show up in a wide variety of CS contexts.

how many local minima there are versus a global minimum for optimization problems. if there are many local minima it is harder to find the global minimum. roughly this is also a measure of how effective greedy algorithms are on that problem.
algorithmic speedup due to parallelism. this metric is sensitive to both the problem and the algorithm chosen. for example the problem may not be very "decomposable", or a problem may be decomposable but it is not solved with a most efficient algorithm. for more decomposable problems, algorithmic speedup is nearly linear in increasing processors. for less decomposable problems, it is more an asymptotic sub-linear relationship.
communication overhead of parallel processing. the decomposability is known as "granularity". for problems that are not as granular, there is more communication required between separate parallel threads or processors. problems with very "fine" granularity ie not requiring much or any communication between processors are called embarrassingly parallel.
NC is the class of efficiently parallelizable algorithms. NC=?P is an open question. ie in short are all P-time algorithm efficiently parallelizable, or not?

one paper that does attempt to study these concepts more formally/systematically within the context of parallel computing is Landscape of parallel computing, the view from Berkeley. see eg "7+ dwarves" for the basic algorithmic patterns that seem to appear in practice and commentary on their decomposability wrt parallelism.

another influential researcher recently looking into the inherent limits/ceilings/gains of parallelism in CPU design (ie multicore) which relates to the general decomposability of everyday running code is Esmaeilzadeh.


Line smoothing algorithm that perserve data uniformity

Here are two suggestions for you to try.

Suggestion 1: Use a linear filter. Instead of computing the average $x_{2n},x_{2n+1} \mapsto (x_{2n}+x_{2n+1})/2$, try averaging over a larger sequence, e.g. $y_n = (x_{2n-1}+2x_{2n}+2x_{2n+1}+x_{2n+2})/6$.

Suggestion 2: Use a conditional filter: if $x_{2n} < x_{2n+1} > x_{2n+2}$ or $x_{2n-1} < x_{2n} > x_{2n+1}$, then let $y = x_{2n+1}$ or $y = x_{2n}$, respectively, and similarly for local minima; otherwise use the average (or a linear filter) as before.


A genetic algorithm modified for a specific problem

Start with a population, where every candidate is "good", where "good" means they contain at least one occurrence of substrings "01" and "011".

For the mutation operator, flip a coin. If the result is heads, choose a random substring of length 2 and change it to "01". If the result is tails, choose a random substring of length 3 and change it to "011".

For the crossover operator, let $A$ and $B$ be two parents. Find say the first occurrence of substring "01" or "011" from $A$, that occurs starting from index $i$. Check if in $B$ there is an occurrence of "01" or "011" before $i$. If so, choose $i$ as your crossover point. If not, find the next occurrence from $A$, and repeat. This process will terminate at some point, because you start out with individuals containing "good" substrings, and your operators maintain an invariant that all individuals are "good".

Please note that this only really answers your question of "how do I modify my GA", and does not address whether this works performance-wise. However, this should give you ideas as to what kind of operators you can experiment with.


To start with an important side note: what are the inputs for $X$ and $Y$ that they will halt on? you need to specify a specific input for the machines in order for the question to be well-defined (for example, the question could be "given $X,Y$ where exactly one terminates on $\epsilon$, find who halted." Or maybe, "given ... where exactly one always halts on itself as an input...")
I see what confused you there. The problem is indeed solvable: in $P$ emulate both $X$ and $Y$ and answer whoever halted first.
The problem in your solution is that an input to $P$ must be $X,Y$ where exactly one of them halts, and the other doesn't.
So, a proper input to $D$ must be a proper input to $P$. Now notice you called $D(D,S)$. To make sure that $D$ will return a correct output, we must have proper inputs: only one of $D$ or $S$ halts! But... If $S$ halts then your $D$ also halts and this is not a proper input to $P$, and therefore also not a proper input to $D$. Thus you cannot rely on output from $D(D,S)$ as it may not be correct


The basic objective of a Turing test is to come up with such an intelligent machine, which actually mimics the human way of communicating.
For that purpose, we'll carefully need to think about what normal humans would like to talk about, in a casual manner. Starting the talks with a friendly, informal manner may be a good thing. After that, you might want to know about the interests of the person you're talking to; you might start with...say, football, or cricket, economical crisis, united nations; there are literally a lot of topics.
 Look up for the common trends in the humans...these can include some recent famous political scandals (I don't want to mention Panama Leaks here). Questions can be about the current good movies (hits and flops). You may even come up with a religious, or a philosophical discussion if that helps.
 Incomplete questions, and then stating "you know the rest" after a half phrase can also be a good practice, because of the common sense the humans have to infer the essence, and background meaning of the question.
 Last, but not the least, if you're going to ask the question from a chat-bot, then it is a real good thing that you place intentional grammatical mistakes, typos, and unclear phrases, that only a real human would be able to understand, because it's a natural thing for the humans to commit a mistake. Questions about past memories are also a good thing, especially when they are slightly offensive; discussing relationships, frustration, failures, fears etc. Emotion-based questions have more tendency to crack up the game.


What's the directory structure on disk that keeps the information of all files?

Your intuition is mostly correct. I believe the description is not really sufficient. Directory entry should at least be able to allow the OS to be able to locate some parts the file on disk for I/O operations. File System is divided into some fixed size partitions of available space ranging from 1-16KB. For efficient implementations a file is not necessarily written in contiguous blocks therefore the challenge is mostly having an efficient way of determining which blocks belong to which file without giving up on too much space and being efficient at the same time. Similarly other meta information should also be kept such as user permissions, hard links and so forth.

Currently Unix inode system is an efficient implementation. An other example would be maintaining a FAT (File Allocation Table) which is less efficient. I believe reading about Inodes would be great place to start.


Recursion Time Complexity (Half n' Half)

I can offer one simple optimizations to your code.

At the moment your code will take $\Omega(n^2)$ time even on a string in which each symbol appears at least $k$ times. This can be avoided using counting sort: using a single pass, you can compute how many times each letter appears. If every letter appears either 0 or at least $k$ times, then the current string is good. This takes linear time.

(This uses the fact that it is known that all letters of the string are lowercase letters. If the letters are arbitrary, you can still speed this up by sorting the array.)

Even after this optimization, your code suffers from a problem. Suppose that $k = n/2 + 1$, and let the string consist of $n/2$ copies of a followed by $n/2$ copies of b (as an aside, you can immediately return 0 in this case – a further optimization). Your code will recurse on the substring $s_2,\ldots,s_n$, the on the substring $s_3,\ldots,s_n$, and so on, not giving up at any point. Therefore it will take time $\Theta(n^2)$ (or, without the first optimization mentioned above, $\Theta(n^3)$).

In order to avoid this, suppose that you found out that $s_i$ appears fewer than $k$ times. Find all occurrences of $s_i$, partition the string accordingly, and recurse on each such substring. This will guarantee that each substring won't have the letter $s_i$. Each time you recurse, you have one fewer letter appearing, and so the depth of the recursion tree is at most 26. Therefore the algorithm will run in linear time.


Efficient algorithm to simulate dealing cards from a large deck of cards?

In the special case of two players and two card types, this is exactly the hypergeometric distribution. More accurately, the number of cards of the first type that the first player gets is distributed hypergeometrically; and the rest of the deal can be deduced from that.

Conversely, you can simulate the entire dealing process by sampling appropriate hypergeometric distributions. Indeed, the number of cards of the first type that the first player gets had hypergeometric distribution. After deciding that amount, remove these cards and reduce the number of cards that remain for the first player and repeat, until you have detail the first player their entire hand. Then repeat with the other players.

The two problems are thus equivalent. Presumably there are online resources, and probably even libraries, for sampling hypergeometric random variables efficiently.


Efficient way to implement periodic events

A standard approach for scheduling is a priority queue of future jobs: each job has a time at which it should be dispatched, and that time is the key for the priority queue.

When a new job arrives, pick a random time within its period, and schedule it to occur at that period.  For instance, if a job arrives with a period of 75 seconds, pick a random number $t$ in the range [0,75), then schedule it to be first dispatched $t$ seconds from now.  To schedule it, add it to the priority queue with its dispatch time as the key.

Each second, retrieve all jobs scheduled to be dispatched in this second, delete them from the priority queue, and dispatch them.  Also schedule each to occur at a time in the future based on its period (thus inserting it back into the priority queue with a later dispatch time).

The randomization should ensure a reasonable balance of jobs, especially when you have a large number of jobs to schedule, and the priority queue should make it efficient to insert, delete, and dispatch jobs.  In particular, all of those operations can be done in $O(\log n)$ time, where $n$ is the number of jobs.

You could check whether that will meet your requirements.  If not, that should help clarify your specific requirements.


Can any algorithm efficiently be implemented as a SIMT problem?

No, efficiency cannot be strictly worse, for trivial reasons.  For instance, you can have all $n$ threads independently compute the same thing -- each doing the same thing that the sequential computation would have done.

This is not very interesting or useful in practice, for a number of reasons: (1) in practice, in SIMT architectures each individual compute element is typically less powerful than the compute element in a sequential system; (2) we care not just about compute time but about energy usage, and wasting energy on pointless computation would be, well, pointless.

At the same time, it is true that there are computational tasks that are inherently sequential: they cannot be sped up on a parallel processor (including a SIMT machine).  See, e.g., Which algorithms can not be parallelized?, https://crypto.stackexchange.com/q/606/351.


the area seems to be "mature" in the sense that garbage collection theory/ dynamics is relatively well understood, surveys that come up in searches are years old and many state-of-the-art algorithms are now implemented, and maybe research in the area is far less common or active. also hardware assisted garbage collection seems an uncommon combination theoretically (also/ incl operating system aware/ crosscutting such as algorithms that intentionally mesh well by design with caches, paging, virtualization, etc). speaking as a practitioner in the field, garbage collection algorithms tuned with hardware features or OS mechanisms seems a promising idea that hasnt been explored much.

here is one survey turned up of 3 state of the art algorithms from 2013 and there is a hardware mechanism on the 1st (for reference counting).

Low Pause-Time Garbage Collection
Written Preliminary Examination II / DeLozier


Maximal number of rotations after deleting a node in an AVL tree

Note: This does not answer the question exactly. However, it would be helpful for further study.

Quoted from Section 6.2.3 (entitled "Balanced Trees") of TAOCP "Sorting and Searching", 2nd Edition:

  In order to figure out the running time of Algorithm A (for AVL search and insertion; [emphasis mine]), we would like to know the answers to the following questions:

  How many comparisons are made during the search?
  How much adjustment is needed in step A6?
  How often do we need to do a single or double rotation?

Before going into details, it summarizes:

  It is not difficult to derive upper bounds on the worst case running time, using Theorem A, but of course in practice we want to know the average behavior.
  No theoretical determination of the average behavior has been successfully completed as yet, since the algorithm appears to be quite complicated, but several interesting theoretical and empirical results have been obtained.

You would probably be interested in Theorem A mentioned above:

  Theorem A (Adelson-Velsky and Landis). The height of a balanced tree with
  $N$ internal nodes always lies between $\lg(N + 1)$ and $1.4404 \lg(N + 2) -
0.3277$.

You can also find many empirical results (and some theoretical results) in the following paragraphs.


In short, the greedy algorithm works, where in each step you find the largest number in $A$ and subtract it from $b$. If $b$ becomes zero, you get a solution. If you reach a point where all numbers in $A$ are greater than $b$ output no.

In the following I list a formal description of the algorithm and a proof of correctness.

Here is a formal description of the algorithm. Let $A_0 = A, b_0 = b$ and $b_i$ be the value of $b$ after the $i$-th iteration. Let $A_i$ be the numbers left in $A$ after the $i$-th iteration. Then the algorithm goes as follows. In each step $i = 1,\dots$ find the largest number $a_j$ in $A_{i-1}$ not greater than $b_{i-1}$. If no such number exists output no. Otherwise, set $b_{i} = b_{i-1} - a_j$ and $A_i = A_{i-1} \setminus \{a_j\}$. If $b$ becomes equal to zero then output yes, else iterate.

Claim 1. The previous algorithm output the correct answer of the given instance of the restricted case of the subset sums described in the question.

Before we prove the claim we prove an auxiliary claim.

Claim 2. Let $a_1, \dots a_n$ be the numbers in $A$ in ascending order. Then $\sum\limits_{i=1}^{k-1}a_i < a_k$ for all $k \in [n]$.

Proof.(Claim 2). Proof with induction over $k$. For n = 1, the sum is empty. Now we prove it for $k$.
$$\sum\limits_{i=1}^{k-2}a_i + a_{k-1} < 2a_{i-1} \leq a_i,$$
 where the first inequality holds due to the induction hypothesis and the second one holds by assumption since $a_{k-1}$ divides and is smaller than $a{k}$.

Proof.(Claim 1) If the algorithm outputs yes, then it is clearly a yes-instance, since it only chooses numbers from the given sets and subtract there values from $b$.

Now we prove that, if our algorithm outputs no, the given instance is a no-instance. To this end we prove that if at step $i$ we choose an element $a_j$, then any solution of the given instance must contain this element. We prove this by induction over $i$. Note that any $a_j', j'>j$ is strictly greater than $b_i$ and hence can never be included, assuming by induction hypothesis, all previous selections of $a$ were a part of a solution if there exists one. Now using Claim 1, $\sum\limits_{i=1}^{j-1}a_j$ < $a_j$ and since we only remove elements, $A_i$ contains no other elements smaller than $a_j$ and hence, if we do not choose $a_j$ choosing all smaller elements will not suffice to get a sum equal to $b$. Hence, we have to choose $a_j$.


Non-reducible Unsatisfiable 3SAT instance example

Resolution is a complete proof system for contradictions: if a given set of clauses is contradictory, then this fact is provable using resolution.

Since Resolution exactly corresponds to your "simple reduction", it follows that your question cannot be answered.


Can any finite problem be in NP-Complete?

If a finite problem is NP-complete then P=NP, since every finite problem has a polynomial time algorithm (even a constant time algorithm).

When we say that Sudoku is NP-complete, we mean that a generalized version of Sudoku played on an $n^2 \times n^2$ board is NP-complete.

Finally, the 4-clique problem, while not a finite problem (the input graph has unbounded size), is an easy problem which has a polynomial time algorithm.


If every interval begins immediately after the previous one ends, then you only need to store the start point of each interval (and the endpoint of the very last interval), which you can do with a self-balancing binary search tree.  Inserting and deleting intervals is then $O(\log n)$-time, and identifying the intervals overlapping a query interval is $O(\log n + k)$-time, if the answer includes $k$ intervals.


Optimization problem vs decision problem - reduction

There are a few conditions you would need to specify for this to even work, most importantly, that your function does have a maximum, otherwise you could try all k and end up going off into infinity. Likewise, you'd probably need to assume that f is only producing outputs on the integers or some other countable set.

If we're doing any sort of binary search, I think it is going to be exponential in the worst case unless we know an upper bound to start with. Assuming f returns numbers, finding the upper bound is going to be linear in terms of the maximum value. However, that means it's exponential in terms of the string-representation of the maximum value.

If we know an upper bound for the maximum of f, I can't see any reason why you couldn't do binary search to find it, but even then, it is polynomial in the upper bound, and could still be exponential in the length of the input, as opposed to the output.


Minimize $f(r,X)$ over all sets $X$ using Dynamic Programming

Main idea: Instead of finding $X$ itself, find the minimum value for $f(r,X)$. After you do this, it is easy to find a minimal $X$. Simply greedily add elements to an interval until the sum of the interval is too large - once this happens, create a new interval at that position.
Finding the minimal value for $f(r,X)$ is a classic (maybe prototypical) binary search problem. The algorithm is as follows: binary search over the answer. Within your binary search, greedily add elements to an interval until the sum of the interval is higher than the answer - once this happens, create a new interval. (Note that this is the same method as is used to construct $X$.) At the end, check how many intervals you have formed - if it is $\leq r$ then it is possible to divide the array into $r$ intervals such that $f(r,X) \leq ans$. The time complexity is $O(NlogS)$, where $S$ is the sum of all $a_i$.
Although binary search does work for all practical values, your statement does state $\mathbb{N}$ as the possible size of elements. If elements can be arbitrarily large, we can use DP as you mentioned, fairly similar to the DP that you use. $best(p,q)$ can be the minimum $f(\cdot)$ taking $q$ intervals from the first $p$ elements. By transitioning in the same way as your statement, we get a trivial $O(N^3)$ solution.
We can also optimise this DP. One optimisation: $best(x,q)$ is monotonically increasing as $x$ increases, but $dist(x,p)$ is monotonically decreasing. So, we can use binary search to find the intersection of the two lines. The transition is now $O(logN)$ and the overall complexity is $O(N^2logN)$.
Important thing to note: this DP avoids the issues with your DP because it doesn't store the actual $X$ within the DP itself.


How to remove 'skip' edges from a DAG? (How to find only the longest path from each node to each of its sinks?)

On the question from title

For fixed sink $s \in S$ you can find maximal distance from each vertex to this sink by running dynamic programming on topological order:
$$
d(v)=
\begin{cases}
0\text{ if } v = s\\
-\infty \text{ if } v \not= s \land v \in S\\
1 + max_{(v, u) \in E} d(u)
\end{cases}
$$
You can run this algorithm for every $s \in S$ to get the solution for whole problem.

On your problem

Unfortunately your approach won't work, look at this graph:

A
|\
B |
| D
C |
|/
E

If you would look only for longest path to E from A, you would ignore existence of node D. So unfortunately I think you need to go with more "brute force" approach where you will have to run BFS/DFS from every node in the graph and check the number of reached nodes.


Topological sort where some nodes can't come in between two other nodes

EDIT: As pointed out in the comments this doesn't work!
Copy your graph into $G'$ and for every triple of nodes $(u,v,w)$, if NotBetween$(u,v,w)$ then add the edges $v\rightarrow u$ and $w\rightarrow v$ to $G'$ (if they don't exist already). If the graph has a cycle the problem is infeasible. Otherwise the topological sort on this new graph $G'$ is a valid topo sort for $G$ respecting NotBetween.
This is clearly $O(V^3)$ because you can implement this with 3 nested loops, then resulting graph has at most $O(V^2)$ edges, and the topological sort of $G'$ will take time $O(V^2)$.
If your relation NotBetween is not a black box and actually has some "known shape" you might be able to skip some triples and do better.


DFA that accepts strings with last character being repeated at least 1 time before

I would write out a description of this machine rather than drawing it.

States ($Q$): the states of this machine are five-tuples $(\alpha, \beta, \gamma, \delta, \sigma)$: alpha, beta, gamma, and delta are in $\{0,1\}$ and record whether or not the corresponding symbol has been seen before, while sigma is in $\Sigma \cup \textrm{Nothing}$ and indicates the last symbol read.
Alphabet ($\Sigma$): the alphabet, as you specified, is $\{a,b,c,d\}$.
Start ($q_0$): the starting state is $(0,0,0,0,\textrm{Nothing})$. In other words, we've seen no symbols yet, and the previous symbol read was nothing.
Final States ($F$): a state is final if the last symbol read was seen before. For example, the state $(1,\#,\#,\#,a)$ is final, regardless of what those $\#$s in the middle are.
Transition function ($\delta$): this is the trickiest part. If we're in a state $(\alpha, \beta, \gamma, \delta, \sigma)$ and see the symbol $s$, we want to go to the state where $s$ has been seen, and where $s$ is the last symbol read. If we see $a$, for example, we go to state $(1, \beta, \gamma, \delta, a)$: we mark that $a$ has been seen, don't change $\beta$, $\gamma$, or $\delta$, and record $a$ as the most recently read symbol.


What is a good algorithm for generating random DFAs?

Check out [1] and the discussion in Section 4, Random Automata Generation. The paper benchmarks different DFA minimization algorithms. A uniform random generator is used that produces canonical string representations of complete DFAs with $n$ states and $k$ symbols. They also discuss other methods.

[1] Almeida, M., Moreira, N., & Reis, R. (2007). On the performance of automata minimization algorithms. Logic and Theory of Algorithms, 3.


The "CPS" approach has done great harm to performance in SML/NJ; reasoning desired

At first approximation, there is a difference in "locality" of memory access, when a programm just runs forward on the heap in CPS style, instead of the traditional growing and shrinking of stack.  Also note that CPS will always need GC to recover your seemingly local data placed on the heap.  These observations alone would have been adequate 10 or 20 years ago, when hardware was much simpler than today.

I am myself neither a hardware nor compiler guru, so as second approximation, here are some concrete reasons for the approx. factor 100 seen in Isabelle/HOL:

Basic performance loss according to the "first approximation" above.
SML/NJ heap management and GC has severe problems to scale beyond several tens MB; Isabelle now uses 100-1000 MB routinely, sometimes several GB.
SML/NJ compilation is very slow -- this might be totally unrelated
(note that Isabelle/HOL alternates runtime compilation and running code).
SML/NJ lacks native multithreading -- not fully unrelated, since CPS was advertized as "roll your own threads in user space without separate stacks".

The correlation of heap and threads is also discussed in the paper by Morriset/Tolmach PPOPP 1993 "Procs and Locks: A Portable Multiprocessing Platform for Standard ML of New Jersey" (CiteSeerX) Note: PDF at CiteSeerX is backward, pages from from 10-1 instead of 1-10.


Expected Linear time Minimum Spanning Tree algorithm

Nothing in particular happens if there is an isolated vertex. The algorithm is correct even if $H$ consists of no edges, or if it consists of all edges. The algorithm proceeds by finding a minimum spanning forest on $H$, and using it to prune the contracted graph. IF $H$ consists of no edges, then nothing is pruned, but the algorithm remains correct - this only affects the running time.

Note also that the algorithm is for the more general minimum spanning forest problem. Hence there is absolutely no problem if the graph is not connected. The algorithm will find a minimum spanning tree in each connected component.


How can I check that the language of one context-free grammar is a subset of a second context-free grammar?

Here you have a couple of salient points. Firstly, the grammars are right linear (strictly $G_{1}$ needs some small changes, but they're trivial). This means that the two languages are regular. Given this fact, there's an automated way of determining whether $L(G_{1}) \subseteq L(G_{2})$ or not.

In this case however, things are fairly simple, and we can show a simple mapping between the non-terminals, with only the transitions $A \to abC$ and $B \to acE$ causing a small amount of trouble. If you draw out the finite automata though, you should be able to see the mapping. Doing so, it should be fairly clear that $S_{1}$ maps to $S_{2}$ (obviously), $K$ to $X$, $C$ to $Z$ and $E$ to $Y$. $A$ maps to the pair $U,P$. $U \to aP \to abZ$, and $Z$ already maps to $E$, so you can see the rule is essentially the same in both grammars, just split in $G_{2}$ into an intermediate step. The same observation applies to $B$ and $V,Q$.

Note that in general, we need the fact that $L(G_{1})$ and $L(G_{2})$ are regular, deciding containment for context free languages is undecidable.


How do you protect an AI from a human doing "illogical" moves?

In principle, the problem of building an AI where this can never happen seems equivalent to the problem of building an AI that plays perfectly.

More precisely: If the AI can perfectly evaluate the value of each board position, then it is also able to play perfectly even if the adversary plays imperfectly.  Conversely, if there is a situation where the AI can be tricked by playing an inferior move, then that means there is a board position that the AI evaluates incorrectly.

So avoiding this situation seems as hard as building an AI that never makes the wrong decision.  If we knew how to do that, we would have a perfect solution to the game.  There are some games (e.g., tic-tac-toe, Connect 4) where we do know how to achieve perfect play, but for more challenging games (e.g., chess), we don't know how to achieve perfect play.  As I result, it seems likely there exists a board position where playing an inferior move helps you win where you otherwise wouldn't have.

This means that we need to focus on solutions that reduce the risk/likelihood of this bad situation, as we cannot eliminate it entirely.

When the AI is trained using statistical machine learning (as AlphaGo and AlphaZero are), you can think of this as avoiding overfitting -- you don't want to overfit to any one opponent strategy.  One way that AlphaZero is trained is to play simulated games against multiple opponents -- not just against itself, but against multiple versions of itself, including older (and presumably inferior) versions of itself.  This helps avoid getting stuck in a narrow portion of the space, e.g., where white always plays the Ruy Lopez opening and black always plays the Morphy defense.  This may partly help make the AI more robust against inferior moves, but it is not a complete solution.

In Monte Carlo tree search (MCTS), the algorithm considers random moves for the opponent.  These are drawn from a random distribution that is biased towards moves the algorithm thinks is better, but there is definitely a significant chance during any playout that we'll simulate what happens if the opponent makes a move we consider detrimental/inferior.  This helps MCTS be robust against even inferior moves.  It's not perfect, but it's already baked into the MCTS algorithm.


Soft Margin Loss and Conditional Probabilities

It is not possible to consistently estimate $P(y \mid x)$ if you are learning with hinge loss. Strictly proper losses, also known as strictly proper scoring rules, are the subclass of loss functions that are consistent for probability estimation. There is now a comprehensive and rich theory of proper losses, the larger class containing strictly proper losses. Without getting far into the theory of these losses, I'll give some examples/non-examples and some properties that strictly proper losses have.

The following are strictly proper losses: squared loss (least squares), log loss (logistic regression), exponential loss (boosting). The following are not strictly proper nor even proper losses: absolute loss, hinge loss (SVM).

One reason proper losses are so important is that if a loss is proper, then it is possible to map the edge $y f(x)$ to a class probability in a consistent way (if we ignore regularization). This can be done by appealing to a link function corresponding to the proper loss. In the binary classification setting, a link function maps from the interval $[0, 1]$ to the "edge space" inhabited by $y f(x)$. Given an edge $y f(x)$, the inverse link can be used to get a probability. For strictly proper margin losses (any of the strictly proper losses listed above), you can get the link function from Corollary 14 of this paper: http://jmlr.org/papers/volume11/reid10a/reid10a.pdf. This paper also discusses the problem with hinge loss for class probability estimation.

Briefly, the problem with absolute loss and hinge loss are that if a learning algorithm believes $P(Y = 1 \mid X = x) > 0.5$, then both these losses are minimized by maximizing the edge $y f(x)$. In contrast, for squared loss and other strictly proper losses, the loss is minimized when the edge (after passing it through the inverse link function) corresponds to Learner's believed $P(Y = 1 \mid X = x)$.


Can a classical supercomputer solve a large Max-Cut Problem?

It's not that straightforward. NP-hardness means worst case intractability. This means that there are plenty of easy instances of Max-Cut with a huge number of vertices (i.e. much more than just one thousand), but also rather tiny instances that are extremely hard in practice. So you can't measure hardness by the size of an instance.
If you want to see examples & runtimes, have a look at the results from the yearly competitions around the Boolean satisfiability problem (SAT).


Inserting NOPs is the stall. It delays execution until the result is ready.

A simple pipelined CPU will have a instruction decoder that controls the entire CPU at a low level setting control lines to each functional unit to control how it behaves. Including whether to pull in a new instruction.

The decoder checks dependencies between instructions and when it sees it needs to delay it will stop pulling in new instructions until it can start the new one.

More advanced CPUs with out-of-order execution (every non-mobile/non-embedded CPU nowadays) will pull in a few more instructions and only start those that don't need to wait on data. The details of out of order execution is too complex to fully explore in this answer.


Where do transformational grammars stand in the Chomsky Hierarchy?

I was taught in linguistics class that Chomsky abandoned his original arbitrary transformations after they were found to produce Turing completeness. See e.g. the Oxford Handbook of Linguistic Interfaces, p. 543; I am unable to locate the original reference.

He subsequently developed a formalism with more restricted transformations; the version I was taught was called Government and Binding Theory.

Some details are in Wikipedia under Transformational grammar.

While searching for references, I ran into a highly readable article on this matter by Geoffrey Pullum, which rejects Chomsky's original notion of transformations for purely linguistic reasons.


I think that answer is clear (although of course I would do, because I wrote it).

What it says is:

  if you find

$$nonterminal\; TERMINAL$$

  in any production, then you add the precedence relations $TRAIL \gtrdot TERMINAL$ for every $TRAIL$ in $Trailing(nonterminal)$. Similarly, every occurrence of

$$TERMINAL\; nonterminal$$

  generates the relationships $TERMINAL \lessdot LEAD$ for every $LEAD$ in $Leading(nonterminal)$.

So in $'(' expr ')'$, you have both an instance of $TERMINAL\; nonterminal$ and an instance of $nonterminal\; TERMINAL$, and you need to deal with both of them independently.


What is difference between architecture and microarchitecture?

The term architecture was popularized by the paper "Architecture of the IBM System/360", IBM Journal of Research and Development, 8(2):87-101, April 1964 by Gene M Amdahl, Gerrit A Blaauw, and Frederick P Brooks, Jr.  They say,

  The term architecture is used here to describe the attributes of a system as seen by the programmer, i.e., the conceptual structure and functional behavior, as distinct from the organization of the data flow and controls, the logical design, and the physical implementation.

According to the Wikipedia page on computer architecture the terminology was probably introduced inside IBM in 1959.

Today we would use the term instruction set architecture to describe the syntax and semantics of the interface of a computer, including the type and size of the operands, programmer visible register state, the memory model, how interrupts and exceptions are handled, the available instructions and the meaning of each instruction.  The instruction set architecture is the boundary between software and hardware, and is the contract between the programmer and the hardware designer.

The term microarchitecture is used to refer to the organization, or highest level of implementation, of a particular processor.  The study of microarchitecture would include topics like pipelining, instruction-level parallelism, out-of-order execution, speculative execution, branch prediction and caching.

I'm not sure about the etymology of microarchitecture.  I can find it used as early as 1975 (in the title of the EUROMICRO Workshop on the Microarchitecture of Computer Systems), but it could certainly be older than that.

Currently the term computer architecture or just architecture typically encompasses both instruction set architecture and microarchitecture, as well as broader system-level issues like network connectivity on multiprocessors.


Number of words in $\{pi,po\}^*$ of length at most 9

Here are all words in $L^*$ of length at most 9:
$$
\epsilon, \\
pi, po, \\
pipi, pipo, popi, popo, \\
pipipi, pipipo, pipopi, pipopo, popipi, popipo, popopi, popopo, \\
pipipipi, pipipipo, pipipopi, pipipopo, pipopipi, pipopipo, pipopopi, pipopopo, popipipi, popipipo, popipopi, popipopo, popopipi, popopipo, popopopi, popopopo.
$$
In total, there are 31 words.

More generally, suppose that we have $m$ distinct words of length $\ell$. Then the total number of words of length at most $n$ is
$$
\sum_{r=0}^{\lfloor n/\ell \rfloor} m^r =
\frac{m^{\lfloor n/\ell \rfloor+1}-1}{m-1}.
$$
In our case, we get $\frac{2^{\lfloor 9/2 \rfloor + 1}-1}{2-1} = 2^{4+1}-1 = 31$.


Can hypercomputation compute all kinds of incomputable numbers/functions/problems…etc?

It is a little hard to say for sure since since one has not found a final Theory Of Everything in physics. Mostly it seems that hypercomputation is physically impossible.

On the other hand, an amusing development is the work of Nemeti et al. on using time travel (closed timelike curves) to do hypercomputation.

The so-called Malament-Hogarth spacetimes are known for exactly this --- that one can compute forever in them and thus solve the halting problem.

Hogarth worked on this in the 90s and Welch showed that even a larger class of problems than those solvable using the halting problem (all hyperarithmetic problems) can be solved in MH-spacetimes. This does not include all oracles though, as there are uncountably many oracles and only countably many hyperarithmetic ones.

(As for things that are logically impossible, like Russell's set, they are also physically impossible since "physics obeys logic".)


Pulled from: http://www2.math.uu.se/~svante/papers/sjN6.pdf (definition D5).

A probabilistic version of $\mathcal{O}$ that is frequently used is the following:
$X_n = O_\text{P}(\alpha_n)$ if for every $\epsilon > 0$ there exists constants $C_{\epsilon}$ and $n_{\epsilon}$ such that $\mathbb{P}(|X_n| \leq C_{\epsilon}\alpha_n) > 1 − \epsilon$ for every $n \geq n_{\epsilon}$. In other words, $X_n/\alpha_n$ is bounded, up to an exceptional event of arbitrarily small (but fixed) positive probability. This is also known as $X_n/\alpha_n$ being bounded in probability.

So combining this and D.W.'s answer we get:

$X_n \in \tilde{O}_{\text{P}}(\alpha_n)$ means for every $\epsilon > 0$ there exists constants $C_\epsilon$ and $n_{\epsilon}$ such that $\mathbb{P}(|X_n| \leq C_{\epsilon}\alpha_n n^{\gamma}) > 1 - \epsilon$ for every $n \geq n_{\epsilon}$ and for all $\gamma > 0$.

An looser terms $X_n \in \tilde{O}_{\text{P}}(\alpha_n)$ means $X_n$ is bounded by $\alpha_n$ within a polynomial factor with high probability.


Flawed argument in the proof of function extensionality in cubical type theory?

The expression:

\(a : A) -> (p a) @ 0

parses as:

\(a : A) -> ((p a) @ 0)

So this is applying p a : Path B (f a) (g a) to the 0 point. This reduces to f a, because it is the beginning point of the path. It's essentially doing the same thing as the earlier step, which beta reduced the (<i> ...) @ 0 to (...)[i := 0], except p a looks abstract to us, but that doesn't matter, because we know what it reduces to when applied to 0 (or 1) based only on its type.

So, it's not using function extensionality to prove extensionality. What it's doing is taking advantage of the fact that Path types are similar to function types, and that the two Path types in funExt are 'just' functions with different argument order (so it flips them).


What does $\text{dom}(\Gamma)$ mean in the context of an inference rule?

There are various ways to define contexts in type theories. In this style, we assume there is some infinite set of variable names $V$ and define the context $\Gamma : V \rightharpoonup S$ as a partial function from the set of variable names to the set of types. $\mathrm{dom}(\Gamma)$ is then the subset of $V$ on which $\Gamma$ is defined, i.e. the variables in the context $\Gamma$. To require that $x \notin \mathrm{dom}(\Gamma)$ is asking for $x$ to be a fresh variable for the context $\Gamma$.


For what kind of data are hash table operations O(1)?

Hash table lookup can always be $O(1)$ for static sets, see the 2002 paper by Arne Andersson and Mikkel Thorup: Dynamic ordered sets with exponential search trees

  Firstly, we give the ﬁrst deterministic polynomial-time (in n)
  algorithm for constructing a linear space static dictionary with $O(1)$
  worst-case access cost (cf. perfect hashing). As mentioned earlier, a
  linear space data structure that supports member queries (neighbor
  queries are not supported) in constant time can be constructed at a
  worst-case cost $O (n^2 W)$ without division [30]. We show that the
  dependency of word size can be removed.

In the general case, Andersson et al provide an algorithm for hash-indexed data structures that support lookups and updates in $O(\sqrt{\log n / \log \log n})$. Furthermore, they prove that this bound is optimal. So we know exactly how close we can get to $O(1)$ in the general case.


Algorithm to find whether there is a path (any path) above length X between two vertices

If you allow duplicate vertices on your path, you can make a network from your graph by giving each edge weight $-1$. Then, use Bellman Ford to find the shortest path and see if it has length $-X$ or less.

If you don't allow repeats, then the problem is NP hard, since finding the longest simple path between two vertices tells you whether there is a Hamiltonian path or not.


How do we distinguish NP-complete problems from other NP problems?

To provide the flip side of 042's answer: it's important to understand that if $P=NP$ then every problem in $NP$ is $NP$-complete (caveat: under the usual poly-time reductions): $NP$-complete simply means 'every problem within $NP$ can be solved in polynomial time with an oracle for this problem'.  But if every problem in $NP$ can be solved in polynomial time—that is, if $P=NP$—then the second part of that statement is vacuous.

On the other hand, if $P\neq NP$ then it's known that the problems that are in $NP$ but not in $P$ have a very rich structure - in particular, there have to be 'intermediate' problems that aren't in $P$ but also aren't $NP$-complete, and in fact an infinite number of distinct ones (that is, such that at least one can't be reduced to the other).  For more details on this result (Ladner's Theorem), you might start with Lance Fortnow's notes on the topic.


When using resolution variable elimination to simplify a cnf, does that change the truth values of the other variables?

Yes, you can.  Any satisfying assignment for the simplified formula can be extended to a satisfying assignment for the original formula, by setting appropriate values to the eliminated variables (but not changing the values of the remaining variables), and vice versa.


Ignore the software reliability for now, and only focus on the machines.

In case 1 there is only one machine that can fail, and it fails 1% of the time.

In case 2 there are two machines that can fail. However, even if just one fails the service goes down. The chance that at least one machine fails is $1 - 0.99^2 = 1.99\%$. So instead of spreading the risk we've just made our service more liable to fail.

There are two components to making a system reliable despite hardware failure:

Spreading out risk of failure across multiple machines.
Making the system robust to failure of some machines.

In the exercise we do have #1 but are missing #2.


Is there any published paper about automated planning software used in the ESA Rosetta mission?

Well, as far as I can tell, there was no specific automated planning tool for the Rosetta mission as we understand automated planning systems in ICAPS, which is the most prominent conference on Automated Planning and Scheduling.

The hardest part was to plan the journey from earth to a common location where both the spacecraft and the comet could meet and this was done mainly in two stages: one making the spacecraft orbit around some bodies to save energy (cruise phase) and this was mainly done with astronomical computations; after hibernating for a good number of years, it had to wake up and fly (now using its own power) to meet the comet. There was, additionally, another scheduling problem in the final landing operation of Philae. The last two operations were self-automated.

I asked someone with a better knowledge of Rosetta and this person told me (right now) that there were mainly scheduling systems (as they are also called in the paper you mention) and that most of the operations were self-automated (ie., the main difficulty was that Rosetta was so far that it had to be able to take some decisions on its own, but still it received orders from the ground segment chiefs in ESTEC, Germany).

This said, I do not think we will ever see a paper about how to use PDDL (Planning Domain Definition Language) for Rosetta, or how to use LAMA, Fast-downward, FF (or any temporal PDDL planner) or anything of the kind (I mean, the kind of research we all do at ICAPS) but something instead far more domain-dependent.

On the other hand, it is rather unusual for engineers and scientists at ESA to publish papers at scientific venues such as ICAPS, ECAI (European Conference on Artificial Intelligence), AAAI (Association for the Advancement of Artificial Intelligence), IJCAI (the International Joint Conferences on Artificial Intelligence). They instead submit their papers to the SpaceOps symposium. I found a number of papers there:

Geurts K., Fantinati C., Ulamec S., Willnecker R. Rosetta lander: On-comet operations preparation and planning. 13th International Conference on Space Operations, SpaceOps 2014; Pasadena, CA; United States; 5 May 2014 through 9 May 2014

Haddow, CR., Werner D. Mission planning framework - Building the rosetta and bepicolombo planning systems. 13th International Conference on Space Operations, SpaceOps 2014; Pasadena, CA; United States; 5 May 2014 through 9 May 2014

Moussi, A. Fronton JF., Gaudon P., Hallouard D., Mangeret M., Delmas C., Lafaille, V., Durand J. PHILAE lander: A scheduling challenge. 13th International Conference on Space Operations, SpaceOps 2014; Pasadena, CA; United States; 5 May 2014 through 9 May 2014

Eiblmaier MG., Blake R., Williams A., Lodiot S., Godfrey J., Bartesaghi M. Automating ESA's planetary missions: From concept to conclusion. 13th International Conference on Space Operations, SpaceOps 2014; Pasadena, CA; United States; 5 May 2014 through 9 May 2014

Hope this helps,


How to show that this variation of the algorithm (that runs until it finds a solution) still has linear expected running time?

I'm assuming you're referring to this as your source.

Short answer: The algorithm terminates in linear time. This does not mean it identifies a median in linear time.

The text first proves, by Theorem 3.9 on page 54, that the algorithm terminates in linear time.

Then it proves, by Theorem 3.13 on page 57, that the probability of failure is bounded by $n^{-1/4}$.

Then the text mentions (page 57):

  By repeating Algorithm 3.1 until it succeeds in finding the median, we can obtain an iterative algorithm that never fails but has a random running time. The samples taken in successive runs of the algorithm are independent, so the success of each run is independent of other runs, and hence the number of runs until success is achieved is a geometric random variable. As an exercise, you may wish to show that this variation of
  the algorithm (that runs until it finds a solution) still has linear expected running time.

The algorithm merely terminates in linear time, making it a Monte Carlo Algorithm. Although by successive runs and a bound on the probability of failure, we can guarantee a success at some point, making it a Las Vegas Algorithm. This successive trial algorithm is what you would attempt to show has an expected linear running time, by working on the geometric random variable represented by $k$ successive trials with bounded failure probability $n^{-1/4}$.


Given $n$ unique items and an $m^{th}$ normalised value, compute $m^{th}$ permutation without factorial expansion

Well, from the clarifications made in the comments, then this could be a solution.
I haven't checked for correctness. Specifically the requirement of choosing the closest label to the one input. I think I am taking the one immediately below the number input. Probably that can be fixed by using closest integer, instead of floor below.
Let $L=L_1$ be the input label, which is a real number. Maybe we can just assume that it is in $[0,1]$.
We begin with the full collection of numbers say $C_1=\{1,2,3,...,n\}$ from where one will be eliminated at each step.
In the first step we compute $a_1=\lfloor L_1\cdot n\rfloor$. We pick the $a_1$-th element $p_1$ of $C_1$ to be the first element of the permutation and remove it form $C_1$. So, define $C_2=C_1\setminus\{p_1\}$. Define $L_2=L_1\cdot n-a_1$.
Continue in this way, in the $k$-th step, for $k=2,3,...,n$, put $a_k=\lfloor L_k\cdot (n-k+1)\rfloor$, take $p_k$ to be the $a_k$-th element of $C_k$ and define $C_{k+1}=C_k\setminus\{p_k\}$ and $L_{k+1}=L_k\cdot(n-k+1)-a_k$.
Finish when there are no more elements in $C_k$, or maybe when there is just one which will be forced to be the last element in the permutation.

See also factorial number system. Since this is essentially what we are doing.


Free description of the Kameda-Weiner algorithm?

Brzozowski's paper on arXiv might have a full account of the algorithm. He's one of the pioneers in what I've termed the "algebraic approach" for formal language and automata theory - best known for invoking the "Brzozowski derivative" (aka left-quotient) to describe the state transition of a regular language in algebraic terms. It's the same operation that we used in producing a dramatically simpler proof of Parikh's theorem in 1999. For commutative Kleene algebras, the operator actually is a derivative operator complete with its own version of Taylor's Theorem.
In the paper, https://arxiv.org/abs/1301.5585, Brzozowski brings the derivative/quotient infrastructure to bear; but from a casual reading of the paper, I can't tell if he's described the Kameda-Weiner method in full generality or not.


Proof Review: Integer Factorization is in NP

You are missing something.

If you are given what is supposed to be a factorisation of a number x, it's not enough to show that the product of those numbers is x. You also have to prove that all the numbers in the purported factorisation are primes.

Fortunately there is theorem that for every prime number, there is a polynomial time proof that it is a prime.


Segmenting an English string with no spaces using dynamic programming

I'm assuming your quality function measures something similar to the likelihood of the string being a word. The problem with your algorithm is that it makes a hard decision about where the first space should go before considering where the other spaces go. If you make a suboptimal decision for where the first space goes it will mess you up later on.

The dynamic programming algorithm for this problem is called the Viterbi algorithm. https://en.wikipedia.org/wiki/Viterbi_algorithm You have to keep a table of the highest quality segmentations seen so far as you process the string from left to right. When the algorithm finishes you will be left with a ranked list of the highest quality segmentations.


Variation to edit distance depending on position still a metric?

Here is why the usual edit distance is a metric:

$d(w,w) = 0$ since no operations need to be performed to get from $w$ to $w$.
$d(x,y) = d(y,x)$ since given a sequence of operations for transforming $x$ to $y$, we can perform it in reverse to transform $y$ to $x$ at the same cost. This shows that $d(y,x) \leq d(x,y)$, and similarly $d(x,y) \leq d(y,x)$.
$d(x,y) \leq d(x,z) + d(z,y)$ since if $\alpha$ transforms $x$ to $z$ and $\beta$ transforms $z$ to $y$ then $\alpha\beta$ transforms $x$ to $y$, and moreover the cost of $\alpha\beta$ is the sum of the costs of $\alpha$ and $\beta$.

Now you're in a position to answer your question yourself.


$A$ nonregular language, is $A\cup B$ nonregular?

Here is one result in the direction you're looking into:

  Suppose that $A,B,C$ are languages such that $A$ is a non-regular subset of the regular language $C$, and $B$ is disjoint from $C$. Then $A \cup B$ is non-regular.

For the proof, consider the intersection of $A \cup B$ and $C$. Details left to the reader.

The question you link to concerns the language
$$
\{ a^p : p \text{ is prime} \} \cup \{ w : |w| \text{ is even} \} =
\{ a^p : p \text{ is an odd prime} \} \cup \{ w : |w| \text{ is even} \}.
$$
We can write this in the form $A \cup B$, where $A = \{ a^p : p \text{ is an odd prime}\}$ and $B = \{ w : |w| \text{ is even}\}$. Let $C = \{ w : |w| \text{ is odd} \}$. Applying the result above, we deduce that $A \cup B$ is non-regular (assuming we already know that $A$ is non-regular).


An explanation for Barendregt use of Y combinator in an equation

The Y combinator satisfies the equation $Y f = f(Y f)$. Hence $g = Yf$ solves the equation $g = f g$. In your case, the function $f$ is $\lambda g x.Sgx$.


Reducing randomness needed by turing machine

Here is another way of looking at $p_A$ and $p_B$. We can think of $B$ as a deterministic algorithm which accepts an additional input $r$ representing the randomness. This input is drawn from some distribution $R$. Also, denote by $P(x)$ the correct answer. Then
$$
p_B(x) = \Pr_{r \sim R} [B(x,r) = P(x)].
$$
Let $M = O(n\delta^{-2}\log m)$, and sample $r_1,\ldots,r_M \sim R$. The algorithm $A_i$ simply runs $B$ with randomness $r_i$, that is $A_i(x) = B(x,r_i)$. We can define another algorithm $A$ which first choose $i \in \{1,\ldots,M\}$ uniformly at random, and then runs $A_i$. The success probability of $A$ is
$$
\begin{align*}
p_A(x) &= \Pr_{i \in \{1,\ldots,M\}} [B(x,r_i) = P(x)] \\ &= \Pr_{r \in \{r_1,\ldots,r_M\}} [B(x,r) = P(x)].
\end{align*}
$$
Thus in $B$, the randomness is chosen according to $R$, whereas in $A$, the randomness is chosen uniformly from a set $\{r_1,\ldots,r_M\}$. If we choose $r_1,\ldots,r_M \sim R$, then we expect the performance of $A$ to be very similar to that of $B$, and this can be quantified using Chernoff's inequality.

The probability $p_A(x)$ itself depends on the choice of $r_1,\ldots,r_M$. What may confuse you is how we conceive of this two-step random process. We first choose $r_1,\ldots,r_M$, and this gives us the function $p_A(x)$, which is a random function depending on the choice of $r_1,\ldots,r_M$. Note that we don't take probability over the choice of $r_1,\ldots,r_M$ – if we did, we would just get $p_B(x)$.


How to write a closed term with this type?

Whenever a new type constructor is defined, it comes with introduction and elimination terms. These are part of the definition.

In the case of sums, the following are part of the definition of what it means to have $X + Y$:

given types $X$ and $Y$ there is a type $X + Y$
given a term $e : X$ there is a term $\mathsf{inl}(e) : X + Y$
given a term $e' : Y$ there is a term $\mathsf{inr}(e') : X + Y$
(there is also an eliminator and equations which I am not writing down here)

So I think this is the point you missed: we do not just say "there is a type $X + Y$" without anything else, as that would be completely useless. We also provide ways of constructing (introducing) and deconstructing (eliminating) terms of the new type.

Now that we know that $\mathsf{inl}$ and $\mathsf{inr}$ are there by definition of sum types, it is easy:
$$\lambda x : X . \lambda y : Y . \langle \mathsf{inr}(y), y\rangle.$$
By the way, Haskell's djinn package can help you with this (I'd show a demo but OSX El Capitan broke cabal).


Why does Lamport clocks increment on both message received and sent?

From Leslie Lamport Time, Clocks, and the Ordering of Events in a Distributed System:

The space-time diagram of Figure 1 might then yield the picture in Figure 2. Condition C 1 means that there must be a tick line between any two events on a process line, and condition C2 means that every message line must cross
a tick line.

I think my confusion was on what actually is an event.
In Lamport's paper and in Wikipedia, sending and receiving the messages are the events. In that case, incrementing the counter both when sending and receiving a message make sense, to ensure that a clock tick separate those events.
In my case, the data structure modification are the events. The message passing between the processes is irrelevant. In that case, I believe that incrementing the counter only when the data change make sense.
Now, if applying this Lamport clocks principle this way still qualify as Lamport clocks and holds all the related properties, I do not know.


Is emptiness of the intersection of the languages of two TMs decidable?

Assuming you have a decider $R$ for DISJOINT, you could use this to make a decider D for $E_\text{TM} = \{\langle M\rangle\mid L(M)=\emptyset\}$ as follows:

D(<M>) =
   return R(<M>, <A>)

where $A$ was a TM, selected in such a way that $\langle M\rangle\in E_\text{TM}$ if and only if $(\langle M\rangle, \langle A\rangle)\in\text{ DISJOINT}$. All that's left for you is to find the $A$ and show that it satisfies the needed conditions. (There are a couple of ways to make this choice.)


To show countability we need not alway show one-to-one onto mapping to $\cal N$. We can instead show a one-to-one onto mapping to a subset of $\cal N$.


Proof with induction even number of letter

The proof is by induction on the length of $w$. If $|w| \leq 2$ then necessarily $w = a$ or $w = b$, and in both cases $w$ doesn't contain any $d$'s. If $|w| \geq 3$ then necessarily $w$ is of the form $ducvd$, where $u,v \in L$ are shorter words. By induction, each of $u,v$ contains an even number of $d$'s. It follows that $w$ also contains an even number of $d$'s: if $u,v$ contain $2s,2t$ many $d$'s (respectively), then $w$ contains $2s+2t+2=2(s+t+1)$, which is also even.


What mathematical terminology exists for "embellished trees"?

A good framework for reasoning about this is research on "ornaments" which were introduced by Conor McBride here: https://personal.cis.strath.ac.uk/conor.mcbride/pub/OAAO/Ornament.pdf .

The idea of ornamentation is that you start with a simple algebraic data type and then you have a separate "ornamented" version of it where the constructors might have more information, which is especially useful in dependently typed programming because a lot of times you want to "adjoin" invariants to a datatype. For more on this, there is another article in the JFP: https://josh-hs-ko.github.io/manuscripts/JFP17.pdf

However, it seems like you are not interested in dependent type theory and have noticed that ornaments arise naturally in everyday programming. For that I would recommend reading about the work on using ornaments in OCaml, specifically this paper (http://pauillac.inria.fr/~remy/ornaments/mlorn-2017-09.pdf) which also has a tutorial for the library here: http://pauillac.inria.fr/~remy/ornaments/ocamlorn/doc/tutorial.html