You are absolutely, completely on the wrong path here.

Predicated instructions are used to avoid branching. A predicated instruction avoids the cost of a branch plus possible penalty for a mispredicted branch.

If you have 100 instructions on the if and the else side, then you would need 200 predicated instructions instead of 100 unpredicated instructions to save a branch and possible mispredicted branch penalty. 200 vs. 100. That's not going to save you anything.

What on earth makes you think you would have 200 predicated instructions, and 300 unpredicated instructions on each path? I'd say you are completely misunderstanding what your professor is saying there.

I strongly suggest that you download an Intel or ARM instruction manual and study what predicated instructions are doing, because right now I have the impression that you are operating blindly without any understanding.

Maybe it would help if you wrote down how you would (in an assembly language of your choice, or an invented one) translate "if x > 0 then y = 1 else z = 2" using a conditional branch, and using predicated instructions.


Fastest nth root algorithm to a lot of digits?

An iterative method may be as follows:

$x_2=\frac{x_1(n-1)+\frac{x}{x_1^{n-1}}}{n}$

where $n$ is the root desired, $x_1$ is a guess of the root of $x$  and $x_2$ is a better guess.

The iterative method is given in the book The Art of Programming Embedded Systems by Jack G. Ganssle.


Reference asking: phase transition in SAT

The two most relevant rigorous results are:

Ehud Friedgut, Sharp thresholds of graph properties, and the $k$-SAT problem. This paper (with an appendix by Jean Bourgain) shows that $k$-SAT exhibits a sharp threshold. However, a priori this threshold could depend on $n$ (i.e., this method cannot show that $\alpha$ is constant).
Jian Ding, Allan Sly, Nike Sun, Proof of the satisfiability conjecture for large $k$. The authors determine the exact value of $\alpha$ for $k \geq k_0$. This value of $\alpha$ had been calculated by physicists using the cavity method, but their arguments are not rigorous.

Related work discusses the geometry of the solution space of $k$-SAT around various thresholds. See for example Dimitris Achlioptas, Amin Coja-Oghlan, Federico Ricci-Tersenghi, On the solution‐space geometry of random constraint satisfaction problems.


The number of words of given length in a language is a very natural parameter. Here are some examples to pique your interest:

The density of $(1+01)^*$ is the Fibonacci sequence.
The density of a regular unary language is eventually periodic.
The density of a regular language is of the form $\Theta(n^k \lambda^n)$ for some integer $k \geq 0$ and real $\lambda \geq 0$.

The parameter $E_L(n)$ measures the entropy per character of a random word of length $n$ in $L$, chosen uniformly at random. For example, if $L$ consists of all binary words containing $\lfloor pn \rfloor$ ones (where $n$ is the length of the words), then $E_L(n)$ converges to $h(p)$, the binary entropy function.


Most research does not actually publish the type checking algorithms for full blown programming languages. You will find some formalisations of a large part of the type systems for full programming languages, such as the work done by Drossopoulou and Eisenbach for Java or Nipkov et al's work on C++. More often, though, you will only find the type systems for some core part of the language (Featherweight Java is one example) or for the core concepts of a language such as the local type inference approach of scala.

In conferences such as POPL and ICFP you will find many type checking algorithms for specific kinds of type systems, and novel approaches such as bidirectional and tridirectional type checking.

More generally, you probably need to know about the Damas-Milner algorithm, local type inference, bidirectional and tridirectional type checking, and expand from there, by following references in the papers and by using google scholar to find which papers cite these and build on the approaches described. Also, as suggested above, conferences such as POPL, ICPF, ESOP and even ECOOP and OOPSLA will have papers relevant to your quest.


What are the options of head movement for a Turing machine?

You are right to be confused! The problem is that different authors disagree on the definition of a Turing machine. There is actually no one "right" answer. Some authors define that the machine moves L / R; but others define that it moves L / S / R, as you have pointed out.
This is not the only thing that different definitions of a Turing machine disagree on. For example, some authors say that a Turing machine has a "halt" state, and some say that it has an "accept" and a "reject" state. Additionally, some authors say that a Turing machine's tape is "doubly infinite", meaning that it extends to infinity in both directions. But other authors say that a Turing machine's tape is "singly infinite", meaning that it only extends to infinity in one direction, and in the other direction it stops.
So what should you do about this? Well...

If you are a student or learning from a book: take a look at your textbook to see which definition they use. That definition is the "correct" one for the purposes of working through specific exercises.

If you are trying to understand the "bigger picture": then realize that it actually doesn't matter which definition you use! It turns out that all the different definitions are equivalent. So, which definition is picked is more a matter of convention, kind of like how we choose to say that $1$ is not a prime number, even though historically many mathematicians said that it was.

If you a researcher: Just pick whichever one is convenient to you or makes sense to you, and stick to it, and make sure you are consistent within your own paper or writing material to always use the same definition.

Which one is correct?

To reiterate: neither is correct; they are just different conventions. It doesn't really matter which you pick, because it turns out they are all equivalent.


Define $r_i=a_i/b_i$.  Sort the vectors in increasing order of $r_i$.  Let's assume (wlog) the $r_i$'s are in increasing order, i.e., $r_1 \le r_2 \le r_3 \le \cdots$.  Let $R=\{r_1,r_2,\dots,r_n\}$.

Notice that your objective function is differentiable at all $x$ such that $x \notin R$.  In fact, it is linear on each open interval $(r_i,r_{i+1})$.  It follows that it attains a maximum at one of the values $r_i$.

So, it suffices to try each of $r_1,r_2,\dots,r_n$ as possible values for $k$, and see which minimizes the objective function.  This leads to a simple $O(n^2)$ time algorithm.  With some optimization and clever tricks you can get this down to $O(n \lg n)$ time, by avoiding re-computing the objective function from scratch each time and re-using work.


Computational complexity vs other complexities

I wouldn't call communication and sample complexities "common". Space and time complexities apply to all algorithms, but the other complexities only apply to certain classes of algorithms. Hence, only space and time complexities should be deemed "common" and thus no others deserve such description.

There isn't any theory that covers all these complexities.


Predecessors(B) is just the set of direct predecessors of B.  The "fathers", not the more distant ancestors.

Dominance frontier nodes must be join points in the graph, and a node can only be a join point if it has more than one predecessor.


Recursive function calculating number of ways to sum $a + 2 b + 3 c = x$

Recursion is a pretty bad choice here, but here is the recursion you could use:
$$
f(n) = \begin{cases} 0, & n < 0, \\ 1, & n = 0, \\ f(n-1) + f(n-2) + f(n-3), & n > 0.\end{cases}
$$
For example,
$$
\begin{align*}
f(-2) &= 0, \\
f(-1) &= 0, \\
f(0) &= 1, \\
f(1) &= f(0) + f(-1) + f(-2) = 1, \\
f(2) &= f(1) + f(0) + f(-1) = 2, \\
f(3) &= f(2) + f(1) + f(0) = 4.
\end{align*}
$$
The dynamic programming approach implied by this example is a much better idea; it can be implemented in constant space and linear time, whereas the recursion will take linear space and exponential time. You could also use matrix powering to compute $f$:
$$
f(n) =
\begin{bmatrix} 1 & 0 & 0 \end{bmatrix}
\begin{bmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 1 & 1 \end{bmatrix}^n
\begin{bmatrix} 1 \\ 1 \\ 2 \end{bmatrix}.
$$
The generating function is
$$
\sum_{n=0}^\infty f(n) x^n = \frac{1}{1-x-x^2-x^3}.
$$
Finally, you can also find an explicit solution:
$$
\begin{align*}
f(n) &= \mathrm{round}(Cx^n), \\
C &= \frac{1}{3} + \frac{\sqrt[3]{847+33\sqrt{33}}}{66} + \frac{4}{3\sqrt[3]{847+33\sqrt{33}}}, \\
x &=
\frac{1 + \sqrt[3]{19-3\sqrt{33}} + \sqrt[3]{19+3\sqrt{33}}}{3}.
\end{align*}
$$
This explicit solution isn't very helpful since you need a lot of precision, but it does give you the correct asymptotics; note $C \approx 0.6184199223$ and $x \approx 1.839286756$.


Overhead cost of spawning child processes

The (non-negligible) cost is the set up of the in-kernel structures to keep track of the new process (setting up page tables and so on).
You can easily measure it: Write a small program just like the one you have:
#include <unistd.h>

/* Define FORK for forking version */

#ifdef FORK
#define ROUNDS 10000
#else
#define ROUNDS 10000000
#endif

int main(void)
{
        for(int i = 0; i < ROUNDS; i++) {
#ifdef FORK
                if(fork() == 0) /* Child */
                        return 0;
#endif
        }
}

and run it under time(1). Here I get (Intel(R) Core(TM) m5-6Y57 CPU @ 1.10GHz,   Fedora 32, kernel 5.7.15-200.fc32.x86_64, gcc-10.2.1-1.fc32, no optimization; just checked that the non-forking code does it's rounds) for non-forking:
real    0m0.027s
user    0m0.024s
sys     0m0.004s

For forking:
real    0m0.436s
user    0m0.016s
sys     0m0.414s

Very definitely not advisable.


If P = NP, why does P = NP = NP-Complete?

If $P=NP$ then every non-trivial language $L$ is NP-hard, where non-trivial means that $L$ is neither the empty language nor the language of all words. This follows immediately from the definition of NP-hardness (exercise!). In particular, every non-trivial language in NP is NP-hard, and so NP equals NPC plus the two trivial languages.


Büchi automaton to Linear Temporal Logic

Since Büchi automata are strictly more expressive than LTL, such a translation is not possible in the general case.

For instance, the language $L = \{w_0 w_1 w_2 \ldots \in (2^{\{a\}})^\omega \mid \exists^\infty i \in \mathbb{N}. w_{2i} = \{a\} \}$ is representable by a Büchi automaton with 3 states, but is not expressible in LTL as it is a counting language.


Meaning of , and ; in relation to defining context

You'd have to check whatever you're reading, but the way I've most commonly seen it used is to separate different contexts.  The rules will then behave differently if a variable or formula is in one context versus another.  mobileink mentioned substructural logics which are often formulated with a context for linear variables and a different context for non-linear variables.

However, ; could simply be being used to separate other things so you don't confuse it with context extension.  Or it could just be part of a term.  Or it could be some operator on contexts distinct from context extension.  Or it could just be this author decided to use ; instead of , for context extension.  Again, what it means is whatever it is defined to mean, which may be nothing on its own.  For example, used to separate different contexts, it's just part of the syntax of a judgement, e.g. the judgement may be 3-ary relation $(-);(-)\vdash (-)$ in which case it makes no more sense to ask what ; means than it would to ask what $.$ means in $\forall x.P(x)$.  See my answer to a similar question for more elaboration on this.


It's not possible. You propose a root node with degree 4 and size 7 (including itself).

From CLRS 3ed pp 525:

  Lemma 19.4

  Let $x$ be any node in a Fibonacci heap, and let $k = x.degree$. Then $size(x) \geq F_{k + 2}$.

$$
\begin{align}
k & = 4\\
F_{6} & = 8\\
7 & \ngeq 8\\
\end{align}
$$


Defining the polynomial hierarchy using $\Pi_i^p$ instead of $\Sigma_i^p$

It is a direct consequence of the definition of $\textsf{PH}$.

Remember:

$\qquad \Sigma_i^P = \textsf{NP}^{\Sigma_{i-1}^P}$

$\qquad \Pi_i^P = \textsf{coNP}^{\Sigma_{i-1}^P} $

What we want to prove is:

$\qquad \bigcup_{i>0}\Sigma_i^P = \bigcup_{i>0}\Pi_i^P $

We have:

$\qquad \Sigma^P_i \subseteq \textsf{coNP}^{\Sigma^P_i} = \Pi_{i+1}^P$

$\qquad \Pi^P_i \subseteq \textsf{NP}^{\Pi^P_i} = \textsf{NP}^{\Sigma_i^P} = \Sigma^P_{i+1}$

Taking the union yields:

$\qquad \bigcup_{i>0} \Sigma^P_{i} \subseteq \bigcup_{i>0} \Pi^P_{i} \subseteq \bigcup_{i>0} \Sigma^P_{i}$

which is exactly our goal.


Enumerating all set covers when knowing one set at least

The first step is to eliminate the known set $s$. The idea is to find all covers of $S \setminus s$ using at most $k-1$ sets, and then augment the solution by adding all subsets of $s$ to all sets in any given cover in all possible ways. Details omitted.

For the new problem, it is enough to find all covers of $S$ of size exactly $k$ which don't use $S$ or $\emptyset$. In fact, we can ignore these restrictions, and just drop the (relatively) few solutions using these sets. We will generate them ordered, incurring a factor of $k!$ in efficiency; I'm sure that can be avoided, but I'll leave the details for you. Consider the sets $S_1,\ldots,S_k$ in order, and suppose that they cover $a_1,\ldots,a_k$ "new" elements, that is $|S_1| = a_1$, $|S_2 \setminus S_1| = a_2$ and so on. Then $a_1 + \cdots + a_k = |S|$, and we can enumerate over all such sequences (including zeroes). For each sequence, we can enumerate over the new elements themselves. Finally, we enumerate over all possible ways of adding "old" elements to sets, for example $S_3$ could additionally to $a_3$ new elements contain any subset of $S_1 \cup S_2$.


No of ways in which n indistinguishable items can be placed in m indistinguishable boxes

The number of partitions of $n$ with exactly $k$ parts is the coefficient of $x^n y^k$ in the generating series
$$ \prod_{l=1}^\infty \frac{1}{1-x^ly}. $$
Asymptotically, this is probably $\Theta_k(n^{k-1})$ (i.e. the constant depends on $k$).

The number of partitions of $n$ in which each part is at least $k$ is
$$ \prod_{l=k}^\infty \frac{1}{1-x^l}. $$
Asymptotically, my guess is that it's $\Theta_k(p(n))$, where $p(n)$ is the number of all partitions of $n$.

We can write a recurrence relation for $p(n,k)$: $p(0,k) = 1$ and for $n > 0$,
$$ p(n,k) = \sum_{t \leq \lfloor n/k \rfloor} p(n-kt,k+1). $$


For final state acceptance one needs two states in general. The reason is simply that one needs to distinguish accepted and not-accepted strings. That is why single state PDAf are not a very useful concept. But if you have one, the prefix of every accepted string will itself be also accepted. These languages are prefix-closed.

If a deterministic automaton with empty stack acceptance indeed accepts a string, there is no longer string that can be accepted. The reason is that with empty stack in the classical model of Hopcroft&Ullman the automaton blocks, no steps are possible. Here determinism is important because nondeterministic automata just may have alternative computations on the same string. These languages are prefix-free.

Let me summarize.

The answer to question 1, question 3 and question 7 [single state with final state acceptance] is "no" as not every (D)PDA language is prefix closed, for example regular $(aa)^*$, or in fact finite $\{a,aa\}$.

The answer to question 2 [single state, deterministic, empty stack] is "no", as not every DPDA language is prefix-free, examples as before.

The answer to question 4 and question 5 [two states] are "yes", see Yuval's answer. These results are 'classic'. Perhaps you want to know the deterministic version of these results?

For question 8 observe that DPDAe's can accept 'any' regular language when the end of the string is marked by a special symbol. This makes the language immediately prefix-free.


Substring in a infinite sequence of numbers

Your algorithm is not correct. Consider 21:

21 = [(2, 1), (21)]

First we find 2 in (1-9): 123456789. However, a 3 follows, so it's not a solution.

Then we try to find 21 in (10-99). This finds a solution, but it's 21. However there is an earlier solution:

123456789101112131415161718192021

So the solution is not correct.

The sequence you're after is A229186, but no simple formula is posted there.


Hard computational problem on special class of bipartite graphs

Given a 3-regular graph $G = \{V,E\}$ you can build a bipartite graph $G'$ with the required properties picking $X = V$ and $Y = E$ and for every edge $e_k = (u_i,u_j) \in E$ add edges $(u_i, e_k), (e_k, u_j)$. So I think that you can find some hard problems starting from hard problems on 3-regular graphs.

For example SUBGRAPH ISOMORPHISM is NP-hard for your class of graphs.

The reduction is from Hamiltonian cycle on 3-regular graphs: given a 3-regular graph $G$, build the corresponding $G' = \{X \cup Y, E'\}$ and check for a subgraph $H'$ which is a closed simple cycle of length $2|V|$. $G'$ has a subgraph isomorphic to $H'$ if and only if $G$ has an Hamiltonian cycle.


At the end of the algorithm, the value of $A[n]$ is the parity of the number of divisors of $n$ (TRUE means odd parity). The divisors of $n$ come in pairs $i,n/i$. Most of these pairs consist of two distinct values, but if $n$ is a square, then when $i = \sqrt{n}$, both elements are equal. This shows that $A[n]$ is TRUE if and only if $n$ is a square.


Making a recursive formula for finding amount of ways to spend money on beer

The $n$-the beer has price $p_n$. You can use $k$ items of beer $n$, provided $k\cdot p_n\le C$. The remaining money can be used for beers $1$ to $n-1$. That gives a recursive approach.


Given n sets of points in the plane find the shortest path which passes from exactly one point from each set

This problem is a generalization of TSP known as Set TSP. Not surprisingly, it is both NP-complete and well-studied.


Can someone explain this diagram about Slab Allocation?

I can see why you're confused. The diagram is a bit confusing, and may actually be incorrect.

First off, let's think about why a kernel needs a memory allocator below the level of pages. This is probably already stuff that you mostly know, but I'll go through it for completeness.

Pages are the typical "unit" of memory operations. When a user-space application allocates memory, or memory-maps a file, or something like that, it typically gets a multiple of the machine page size. There are notable some exceptions; Windows uses 64k as the virtual memory allocation unit no matter what the page size of the CPU is. Nonetheless, let's think of it this way.

On a modern CPU, as far as user-space code is concerned, it has a flat address space. This is actually an illusion provided by the virtual memory system. The OS provides pages from anywhere in RAM (or possibly not in RAM at all, in the case of swapped memory or memory-mapped files) and maps them into a contiguous virtual address space.

The point of all this is that apart from a few special cases for the operating system itself (perhaps DMA buffers, maybe some special data structures set up at boot time, oh and the kernel image itself), the operating system kernel probably never has to manage any block of RAM bigger than a page. This simplifies things enormously, because it means that as far as pages go, every allocation and deallocation is the same size. It also effectively eliminates external fragmentation at the macro level.

However, kernels also need to implement some data structures of their own, and for that, they need a different kind of memory allocator. These data structures can usually be thought of as a collection of individual objects (e.g. an object may be a "thread" or a "mutex"). The size of these objects are typically far smaller than a page in size.

So, for example, an object which represents the security credentials of a process (think of the user id and group id in POSIX, say) might only be 16 bytes or so, whereas a "process" or "thread" might be up to 1kb in size. Clearly you don't want to use a whole page for these small records, so the idea is to implement an allocator on top of pages.

The lower-level allocation system has to satisfy many of the same issues as the page-level allocator: it has to be reasonably fast (including on multicore systems), you want to minimise fragmentation, and so on. But more importantly, it should be tunable and configurable depending on what kind of data structure you're storing.

Some data structures are inherently "cache-like". For example, many operating systems maintain a cache of path names to filesystem objects to avoid long chains of directory lookup (called the "name cache" or "namei cache" in Unix-speak). These objects are only needed for performance, not correctness, so you could (in theory) just forget a whole page full of entries if memory is tight and you need to free a page frame quickly.

Other data structures could be swapped to disk if memory is tight and you don't need them soon. But you don't want to do that with data structures which control swapping or the virtual memory system!

Some data structures can be moved around in memory with no penalty (e.g. if nobody refers to them with a pointer), so could "compact" themselves to avoid fragmentation if needed.

So the main idea of the slab allocator is that a page should only store data structures of the same "type". This ticks all the boxes: each object in a page is the same size, so there's no external fragmentation. Objects of the same "type" have the same performance requirements and the same semantics.

Incidentally, it's a similar story with allocation. For some types of object it's probably okay to wait if there's no memory immediately available to allocate that object. An object which represents an open file might be one example; opening a file is an expensive operation at the best of times, so waiting a little longer won't hurt that much.

For other types of object (e.g. an object which represents a real-time event that must happen a certain time from now), you really don't want to wait. So it makes sense for some types of object to over-allocate (say, have a few free pages in reserve) so that requests can be satisfied without waiting.

What you're basically doing is allowing each type of object to have its own allocator, which can be configured for the needs of that object. These per-object allocators are confusingly called "caches". You allocate one cache per type of object. (Yes, you'd typically implement a "cache of caches" as well.) Each cache only stores objects of the same type (e.g. only thread structures, or only address space structures).

Each cache, in turn, manages "slabs". A slab is a page frame which contains an array of objects of the same type. Slabs may be "full" (all objects in use), "empty" (no objects in use), or "partial" (some objects in use).

Partial slabs are probably the most interesting, since the slab allocator maintains a free list for every partial slab. (Full slabs and empty slabs need no free list.) Objects are allocated from partial slabs first (and probably from the "most full" partial slabs first) to try to avoid allocating pages that aren't needed.

The nice thing about slab allocation is that all of these allocation policy options (as well as the memory semantics) can be tuned for each kind of object. Some caches might retain a pool of empty slabs and some might not. Some might be able to be swapped to secondary storage and some might not.

Linux has has three different kinds of slab allocator, depending on whether or not you need compactness, cache-friendliness, or raw speed. There was a good presentation on this a couple of years ago which explains the tradeoffs well.

The Solaris slab allocator (see the paper for details) has a few more details to squeeze even more performance. For a start, in Solaris, everything is done with slab allocation, including page frame allocation. (This is Solaris' solution for allocating objects that are larger than half a page in size.) It manages smaller objects by nesting slab allocators in slab-allocated space.

Some objects in Solaris require complex and expensive construction and destruction (e.g. objects which have a kernel lock), and so they could be "partly free" (i.e. constructed but not allocated). Solaris also optimises free slab allocation by maintaining free lists on a per-CPU basis, ensuring that some operations are completely wait-free.

To support general-purpose allocation (e.g. for arrays whose size is not known at compile-time), most macrokernel-type operating systems also have caches which represent object sizes rather than object types. FreeBSD, for example, maintains caches for unknown objects whose sizes are powers of 2 bytes, from 4 to 256.

What I hope you can see is that slab allocation is a very flexible framework which can be tuned for the needs of different kinds of data. It doesn't compete with paging, but complements it (although in Solaris, page frames are allocated with slabs).

I hope this helps. Let me know if anything needs clarification.


The Church-Turing thesis and Hyper-computation

The Church–Turing thesis is about physically realizable machines. To the best of our knowledge, hypercomputation models cannot be realized in the physical world. They are a figment of our imagination.
If someone would find a new law of physics which enables solving the halting problem, that would make a big fuss in the world of science. But I am not holding my breath.


Representation of 8-Puzzle for (A*) Search Algorithm in C

First of all, the $N$-puzzle is hard to solve with A$^*$ using the Manhattan distance. Instead, we use IDA$^*$. To see the technical details involved in the design of IDA$^*$ specifically for solving the 15-Puzzle see Korf, Richard E. Depth-First Iterative-Deepening: An Optimal Admissible Tree Search, 27 (1985), 97-109. Artificial Intelligence. As a matter of fact, Richard Korf provided a wonderful implementation of his algorithm where he used various tricks to make his solver really fast: a pre-computed table stores the results of all operators to all states; another table stores the variation in the value of the Manhattan distance for each operator, and such. His implementation is publicly available here and you are very welcome to use it provided that you preserve the name of its author, Richard Korf, along with the copyright notice.

If you insist in using A$^*$ for solving the $N$-puzzle then see Matthew Hatem, Ethan Burns, and Wheeler Ruml, Problem Solving with Heuristic Search and Java, IBM developerWorks, July, 2013. The source code is publicly available here. True, their implementation is in Java and their solution considers various issues which are not straight forward in C such as templates. However, most of the ideas are generically discussed (and, indeed, various issues regarding the open and closed lists are considered to a large extent) so that an implementation in C should not be hard.

Finally, let me stress that Manhattan distance is a rather poor heuristic for this domain. On one hand, it can be significantly enhanced with the so called conflict-based heuristic. On the other hand, Pattern Databases are a wonderful means for efficiently solving even the 25-Puzzle (even if some instances can take hours to be optimally solved).

Hope this helps,


Advantage of byte addressable memory over word addressable memory

For 32-bit addresses and 32-bit words, the benefit of being able to address a larger memory is relatively minor, adding only two generations of Moore's Law to the lifetime of the architecture. Compared to a transition from 16-bit addresses to 32-bit addresses (sixteen generations), this is a relatively minor extension.

For the CDC 6600, having 18-bit addresses and 60-bit words and targeting technical computing, the use of word addressing made more sense. Technical computing emphasizes performance over price (so wasting some memory was less important than fast memory access) and has less use for finer-grained accesses.

Many 16-bit DSPs use word addressing. This more significantly increases addressing range than for a 32-bit processor and the benefit of finer-grained access is much smaller for the targeted workloads.

For business and general purpose computing, system cost is a more significant consideration and data element size is more variable. The cost of memory provides an incentive to use smaller data elements. Not supporting direct access to such elements not only increases instruction count (which somewhat directly relates to performance) but code size (which increases memory pressure).

Having a single flat address space simplifies software development. If sub-word addressing requires special handling, this has an effect similar to segmentation where some accesses have to be treated differently than others. Even if such is handled by the compiler, such makes performance less transparent (as well as making compiler development more complex, reducing the resources spent on other features).

Word addressing also requires the use of atomic read-modify-write operation to support simple sub-word stores. (The atomicity requirement may only be with respect to interrupts, but this does add complexity.) A further complication occurs for memory-mapped I/O, where read-modify-write cannot be used since accesses can have side effects. While this issue can be managed by having regions that translate word addresses to specific sub-word granularities, such is an awkward solution. This was how the Alpha 21064 handled byte I/O addresses without byte loads or stores (also 2-byte I/O accesses). (Some 32-bit microcontrollers use bit-banding regions, where an address region uses bit-granular addressing.)

A large part of the reason that byte-addressing (with 8-bit bytes) is popular is, in fact, historical. Not only did IBM's S/360 have a strong influence on the de facto standardization on byte addressing and 8-bit bytes, but the IBM's choice of Intel's 8088 further solidified this trend. With early microprocessors, 8-bit processors would naturally use 8-bit word addressing, maximizing the use of existing software (often written in assembly language) would increase the incentive for using byte-addressed memory. (Note: Reasonable alternatives to the 8086/8088 also used byte-addressing, though IBM's requiring a cheaper and more compatible 8-bit interface may also have been a significant factor. I am not suggesting that word-addressing was only avoided because of the choice of Intel's 8088 for the IBM PC.)

As noted, compatibility with existing I/O interfaces can be particularly problematic.

As Richard L. Sites notes in "Alpha AXP Architecture" (PDF) perhaps more significant benefits of word addressing are avoiding extra shifting of the load result and supporting moderate overhead ECC in a fast writeback cache. Traditional SECDED ECC would require 7 extra bits over 32-bit granules (22% overhead) versus 4 extra bits over 8-bit granules (50% overhead). (Sites' argument about library writers being lazy and using simplistic byte-based string operations is less convincing; forcing extra effort may encourage a moderate addition of effort for higher performance code but it may simply annoy programmers.)

A similar issue applies to unaligned memory accesses. Architecturally disallowing unaligned accesses can simplify hardware but makes some not uncommon operations significantly more complex. Even with MIPS-like load/store unaligned, software must special case unaligned accesses since such instructions increase dynamic instruction count and should not be used if the accesses are known to be aligned. Support for unaligned memory accesses can be particularly beneficial for short vector operations where the individual elements might be properly aligned (e.g., 16-bit elements aligned at 16-bit granularity) but the start of the vector might not be aligned. (This is effectively the same problem as string handling.)

It might be worth noting that software-based pointer compression has some popularity. On a 64-bit architecture, software can choose to use simple 32-bit pointers or even exploit structure alignment to store larger pointers in 32-bit memory locations. (A similar software technique uses bits that can be ignored based on known alignment to store metadata. SPARC even architecturally defined such use by supporting tagged arithmetic operations. Storing metadata in the more significant bits of a pointer is also a common technique. ARM's AArch64 allows the most significant 8 bits to be used for metadata without requiring extra masking, and Azul Systems' Vega processor used the most significant 16 bits for metadata.) In pointer-intensive programs, the reduction in cache misses may justify the additional left shift when loading a pointer. Obviously, this technique has limited use since it requires knowing that the data set will fit within the smaller region and that the objects will be aligned. These factors are easier to enforce at the application or even virtual machine software level than at the architectural/hardware level, especially for a merchant processor (a processor sold to various system vendors).

(Using segments identified by the least significant two bits might be better than word addressing. Like word addressing, such would extend the reach of 32-bit pointers by exploiting structure alignment but it would allow further reach by changing segment addresses. This would require special instructions to distinguish dynamic segment specification (which masks out two bits) and static segment specification (which allows byte granular addresses). HP PA-RISC used a similar segmentation system, but used the most significant two bits to identify the segment — allowing simple byte-granular addressing in dynamically specified segments within a GiWord region but making the 64-bit transition messier than if the least significant bits were used. This choice may hint at how important byte granular addressing is for general purpose computing.)


Yes, $ n\log n = \Omega(n) $ is true.

To see why, note that for this to be true, we have to show that $ n\log n \ge cn$ for all $n \gt n_0 $ and $ \exists c \gt 1 $. If we take $ c = 1 $ then, we get $n\log n \ge n$ for all $n \ge 2$. This shows that $ n\log n = \Omega(n) $ is true.


Using closure properties to show that $a^n b^m a^{n+m}$ is not regular

That line of reasoning can work in principle; you are trying to use closure properties of REG for a proof of contradiction. Make sure you understand that that's what you're doing.

Unfortunately, you do not get $\{a^nb^n\}$. For instance, $a^3 b^4 \in \overline{L} \cap a^*b^*$. Check out our reference question for more techniques you can try.


How to balance doing a literature review and just solving the problem yourself

Before trying to solve the problem yourself, it is always a good idea to search the literature, to see if somebody else has already solved it, or at least has worked on something similar.  This is especially true in computer vision.  A good strategy is to allocate some reasonable amount of time to read papers. If you find nothing useful in that time, then you give up and try to come up with your own solution.

Yes the number of computer vision papers published every year is staggering. So a good strategy is to try to keep up with a few top conferences, such as CVPR, ICCV, ECCV, and BMVC, and a few top journals, such as PAMI and IJCV.

Also, it is good to find researchers and research groups who are working in your particular area of computer vision, and follow their progress, and the papers which cite them.


While you will need fewer 80-based numbers than 2-based numbers (bits) to encode the same file, the only way to store these 80-based numbers on a computer is to encode them as bits. So you do not gain anything.

In fact you actually lose space, since 80 is not a power of 2: You will need 7 bits for each 80-based number, but in these 7 bits you could instead encoed 128 different states, if you used them directly.


How to build a parser for syntactic analysis of regular expressions?

It is absolutely possible and you are on the right track.  You will need to make sure your grammar is %100 correct and probably LL(1), from there you can choose one of many algorithm examples that are out there or write your own.

See https://en.wikipedia.org/wiki/Top-down_parsing and https://en.wikipedia.org/wiki/LL_parser

Word of warning: The tricky part won't be the implementation but getting your grammar right.


Proof that $\{0^i1^{i^2}:i\in\mathbb{N}\}$ is not context free

The simplest way to show that your language is not context-free is by reduction to unary alphabet. Suppose that your language were context-free. Then the language obtained by applying a homomorphism which deletes all $0$'s would also be context-free. This language is the unary language $L' = \{ 1^{i^2} : i \notin \mathbb{N} \}$. It is known that a unary language is context-free iff it is regular. You can prove that $L'$ isn't regular in any number of ways (for example, it is finite but its limiting density is zero).

If you are hell-bent on using the pumping lemma, then the following argument works. As you mention, the only interesting case is Case 3, in which $x = 0^i$ and $z = 1^j$. According to the pumping lemma, for every $t$ the word $ux^{1+t}yz^{1+t}v = 0^{p+ti} 1^{p^2+tj}$ must belong to $L$, that is, $p^2+tj = (p+ti)^2$. But $(p+ti)^2 = \Theta(t^2)$ whereas $p^2+tj = \Theta(t)$, so for large $t$ the two cannot be equal.


Generating all words of length n in a CFG

I can suggest one possible algorithm based on memoization of a rather naive recursive algorithm, with some corner cases cleaned up.  I don't know if there might be a better approach.

Convert the grammar to Chomsky normal form.  Let $L(A,\ell)$ denote the set of words of length $\ell$ in $L(A)$ (i.e., all words of length $\ell$ that can be derived from $A$).  We'll construct an algorithm to compute $L(S,n)$ recursively, where $S$ is the start symbol of the grammar.

The recursive algorithm for computing $L(A,\ell)$ works as follows. If we have a rule $A \to \varepsilon$ and $\ell=0$, add $\varepsilon$ to the output; for each rule $A \to a$, if $\ell=1$, add $a$ to the output; for each rule $A \to BC$ and each $0 \le i \le \ell$, add $uv$ to the output for each $u \in L(B,i)$ and $v \in L(C,\ell-i)$.

Memoize this algorithm.

As an optimization, when considering a rule $A \to BC$, only iterate over $i$ such that $0 \le i \le \ell$ and $L(B,i)$ is non-empty and $L(C,\ell-i)$ is non-empty.  This prevents generating a long list of candidate values for $u$ that you'll never use.  (You can precompute whether $L(A,i)$ is empty or not, for each symbol $A$ and each $0 \le i \le n$, in $O(n^2 |G|)$ time using dynamic programming, where $|G|$ is the number of rules in the grammar.)  Or equivalently, when you implement the recursive algorithm, implement it using lazy lists, so that the output of $L(A,\ell)$ is a lazy list with elements generated on demand.

With this optimization, I think the total running time of this algorithm should now become something like $O(m n^2 |G|)$, where $m$ is the total number of words of length $n$ in $L$ and $|G|$ is the number of rules in the grammar.  Maybe there is a tighter bound on the running time: this might be pessimistic.


Partition problem with distinct integers

Here is an outline of a reduction from PARTITION to UNIQUE PARTITION. Suppose the original numbers are $x_1,\ldots,x_n$ and the target is $T$. I assume that all $x_i$ are positive integers. The new numbers are going to be $2^n x_i + i$, as well as $1,2,4,\ldots,2^{n/2}$, and the new target is $2^n T + 2^{n/2}$. (The numbers $2^n,2^{n/2}$ are quite arbitrary and could be made much smaller.)


What is the Big-Ω of the following function?

$$\begin{align}
\sum_{x=1}^{2n}(x+x^2) \gt \sum_{x=1}^{2n}x^2 \gt \sum_{x=n+1}^{2n}x^2\gt\sum_{x=n+1}^{2n}n^2= n^3
\end{align}
$$

So the function is $\Omega(n^3)$. You have shown it is $O(n^3)$. So the function is $\Theta(n^3)$.

Although $n^3$, the asymptotic lower bound ignoring a constant factor is the same as the asymptotic upper bound ignoring a constant factor in the current case, it is not always true because some functions fluctuate. For example,
$$f(n)=\begin{cases}1 \quad \text {when }n\text{ is odd,}\\ n \quad \text{when }n\text{ is even.}\end{cases}$$ $f(n)=O(n)$ and $f(n)=\Omega(1)$. Both bounds are tightest.

Exercise. Show that $$\sum_{x=1}^{m}(x+x^2)=\frac{m(m+1)(m+2)}{3}$$


alphabet of a single tape turing machine that simulates a multitape TM

(I successfully downloaded the image).

It is not clear in the picture what is the difference between $\Sigma$ and $\Sigma_A$, however looking at the definition of Exercise 4.12 I think that the author simply distinguishes the input alphabet $\Sigma_A$ from the working alphabet $\Gamma_A$ (tape alphabet); so in order to simulate:

the input tape of A (with symbols from $\Sigma_A$) plus the $k$ tapes of A (with symbols from $\Gamma_A$)

it uses $\Sigma_A$ in the first term of the Cartesian product.

Be careful that you didn't copy exactly the $\Gamma_B$ of the book (you wrongly put a $\cup$ where the book puts a $\times$):

$\Gamma_{B} = (\Sigma_{A} \cup \{¢,␣ , \$ \})\times \{\uparrow, ␣ \} \times (\Gamma_{A}\times \{\uparrow, ␣\})^{k} \cup \Sigma_{A} \cup \{¢\}$

The final $\Sigma_A$ is probably used to represent the initial input of the multitape machine A "as-is" (and satisfies the requirement that the input alphabet must be a subset of the working alphabet); but I think it is a little bit confusing (and perhaps the $ symbol should also be included with the final ¢)

The first steps of the simulation of B should be: copy the input to the  "hypotethetical" track 0 of B, initializing the head pointers of the "hypothetical" tracks 1,..,k of B.


Hint: Think of a value $n$ such that the transition from $n$ to $n+1$ and back is very costly.


Do most computational efficiency increases due to increased transistor count in the last 70 years depend on some kind of parallelism?

There are at least 3 architectural tricks by which an increased number of transistors can lead to higher performance.

One of them is parallelism, as you point out.

A second technique trading off more transistors for performance is speculation.  Often speculative execution of some kind is combined with parallelism, and this kind of performance optimization happens at all levels.  For example:
A carry-select adder compputes both a+b+0 and a+b+1 and then selects the correct answer when the carry bit becomes available.
In predicated execution we might execute instructions before we know their results are needed, and then commit the results to the register file only once we know the computation was needed.
In checkpoint repair we speculatively execute instructions that follow an instruction that might (but probably won't) cause an interrupt.  And similar approaches can be used to speculatively execute the instructions that follow a branch instruction.  Prefetching uses extra transistors to fetch data or instructions that might (but won't necessarily) be needed in the future.

Both branch speculation and prefetching are often augmented with even more transistors to predict what intructions/data has the highest probability of being useful in the future.

A third approach for trading off transistors for performance is caching.  A cache is a (usually small and fast) memory used to store the results of expensive work, so that if an identical request is made in the future the result can be returned from the cache rather than by recomputing the result.


Functional Programming and Category Theory

These colleagues of yours, would they happen to be Haskell aficionados?
They might have told you that Hask was a category made from Haskell, but that is a lie, notheless a very useful one that inspires new programming techniques.
If you would like to find out how category theory informs functional programming, I can recommend Bartosz Milewski's Category theory for programmers.
There is also the older Category theory for computer science by Michael Barr and Charless Wells, which is more of a straight introduction to category theory. It might be a good book for functional programmers who only ever learned the bastardized category theory through functional programming.


Data structure for sparse matrices for an online problem

In low dimension, Seidel's algorithm can be useful: if we have the optimal solution to $m$ constraints in $d$ dimensions, and you add one more constraint, then the amortized cost to find the optimal solution to those $m+1$ constraints is $O(d!)$, assuming the constraints are being presented in a random order.

(It is usually presented in the following form: if we have $m$ constraints, and we add them one-by-one, updating the optimal solution after each constraint is added, then the total running time to do this is $O(d!m)$ using Seidel's method.  But that's equivalent, if we assume constraints are added in a random order.)

In high dimension, I don't know of any good method.  There is a trivial observation that if $x^*$ is the optimal solution to the constraints, and we add a new inequality, and $x^*$ satisfies this new inequality, then $x^*$ remains the optimal solution, so there's no need to re-solve the LP.  This condition can be tested in $O(d)$ time.  However, if $x^*$ doesn't satisfy the added inequality, I don't know if there's anything better you can do than solve the new LP from scratch.  Same for changing or removing an existing inequality, or changing the objective function.

I'm not sure your question about data structures is well-defined.  Data structures are chosen based upon the set of operations you intend to perform on them.  In this kind of problem, it's usually the algorithm that is the more important part.  You start with the algorithm, then choose a suitable data structure.  But my impression is that with LP, the hard part is the algorithms, and the data structures tend to be comparatively simple.  So asking about sparse matrix data structures  for your problem seems to be putting the cart ahead of the horse.


Is the ambiguity of a regular tree grammar decidable?

Start by considering regular string grammars. We can determine whether one such grammar $G$ is ambiguous by constructing the intersection of the grammar with itself, with a direct product construction. The nonterminals are pairs $(A,B)$ of nonterminals from the original string grammar $G$. The new grammar of course also derives the original language $L(G)$, but the new grammar has a nonterminal $(A,B)$ with $A\neq B$ in a succesful derivation, iff $G$ is ambiguous. It is decidable whether any given nonterminal occurs in a succesful derivation, so ambiguity is decidable for regular grammars.

The same is true, mutatis mutandis, for regular tree grammars.


Can't understand why the DP Subset Sum algorithm is not polynomial

The reason is that you have to take into account the binary encoding of numbers.  The input size $m$ is really the total number of bits, so if your instance is $a_1,\ldots, a_n, T$, then $m = \log T + \sum_{i\in [n]} \log a_i$.

In particular, $T$ can be super-polynomial in $m$, so the dynamic programming algorithm's runtime can be made super-polynomial as well, since it needs to take one step to build every cell of its table. (The quantity $nT$ can be made $\Omega(2^{m/3})$ for example.)

On the other hand, when all the numbers in the instance are restricted to be "small" (i.e., polynomially bounded in $m$), the SUBSET-SUM becomes tractable.  (Notice that the usual reduction from 3SAT has very large numbers in it.)

A problem is strongly NP-Complete when it remains NP-Complete even when all the numeric values are polynomial in the input length. SUBSET-SUM isn't (it's called weakly NP-Complete).

The kind of running time that is polynomial in the numeric values in the input is known as pseudo-polynomial.


Can you specify a programming language without implementation?

Usually, implementing a programming language is at least giving a interpreter in a language (or a compiler to a language) that is no more than Turing-complete.

Using this "definition" we can specify a programming language like this:

there only one possible program that is HALT;
specification of HALT: it is a function that solve the halting problem.

Implementing this programming language requires solving the halting problem with the implementation. (Which is impossible since our implementation should not be more powerful than a Turing machine).

Specification handles logic and thus can ask for a lot more. Another specification that will be impossible to implement is "false". (Or any contradictory sentence in the specification) But this does not feels like a specification, which is why I used the halting problem example.


An "edge hop" is the "act" of crossing an edge. It's a figurative term. The entry $[A^k]_{ij}$ counts how many paths there are from $i$ to $j$ of length $k$. A path of length $k$ entails traversing $k$ edges, hence the $k$ edge hops.


How to compute (x MOD y) with just SUM and MULT gates?

Turing machines and circuits are very different models of computation: Turing machines are a uniform model and circuits are a non-uniform model. Turing machines accept inputs of an arbitrary length, whereas circuits accept inputs of a fixed length. We can convert Turing machines to equivalent circuits in which the properties of the machine we started with are reflected. For example, a Turing machine running in polynomial time can be converted to a sequence of circuits of polynomial size.

If we have a sequence of circuits, one for each possible length of input, we can interpret the sequence as computing a function. As mentioned above, one way of generating such a sequence of circuits is from a Turing machine. Circuits which can be generated by a Turing machine, which accepts $n$ as input and outputs the circuit handling inputs of length $n$, are known as uniform circuits. (There are various more refined notions of uniformity, in which the Turing machine has some resource restrictions.) However, not all sequences of circuits arise in this way. For example, if $L$ is any length in which membership depends only on the length of the input, then $L$ can be computed by a sequence of circuits. However, $L$ need not even be computable. For example, consider the language of all inputs of length $n$ such that the $n$th Turing machine halts on the empty input.

You say that $\{SUM,MULT\}$ is Turing-complete, but there are a few problems with this statement. First, you seem to think of SUM and MULT as gates, which are components of circuits. As explained above, a model for circuits can't really be Turing-complete, though a set of gates can be complete in the sense that using it you can compute any function. Second, we usually (but not always) think of circuits as Boolean-valued. You haven't explained what the domain of SUM and MULT is, but I suspect that it is not $\{0,1\}$. In that case you have to explain exactly what circuit model you are interested in, and what notion of completeness you are interested in: while Boolean circuits can compute all functions $\{0,1\}^n \to \{0,1\}$, the same doesn't necessarily hold in other circuit models such as algebraic circuits.


TAPL: Explanation and example(s) for satisfied

One way of reading the definition of satisfied that might help is to change

  A rule is satisfied by a relation if, for each instance of the rule, either the conclusion is in the relation or one of the premises is not.

to the logically equivalent statement

  A rule is satisfied by a relation if, for each instance of the rule, if all the premises are in the relation, then the conclusion is in the relation.

Thus if  the rule says, for instance,

$$
\dfrac{A \to B \quad B\to C}
{A\to C}
$$

Then binary relation $R$ satisfies this rule whenever for each instance of the rule, such as

$$
\dfrac{a \to b \quad b\to c}
{a\to c}
$$

if $(a,b)\in R$ and $(b,c)\in R$, then $(a,c)\in R$.

Another way of stating this is that $R$ is closed by the rule (though this probably doesn't make it clearer).

Now let's return to the original statement. What

  A rule is satisfied by a relation if, for each instance of the rule, either the conclusion is in the relation or one of the premises is not.

is saying is that is it okay to have $(a,c)$ in the relation without the premises, but if all of the premises are in the relation, then  $(a,c)$ must be. That is, it is okay to have not all of the premises in the relation, without imposing any additional constraint.

Personally, I think that thinking about this definition in terms of an implication is simpler, so I help this explanation helps.


Confusion related to calculating time complexity

Let $T(i)$ be the running time of opt(i) then we have
$$ T(i)= \sum_{k=i}^n T(k+1).$$
You have not specified a recursion anchor, but I guess it is something like $T(n+1)=1$. Write down the series $T(n),T(n-1),T(n-2),\dots$ and you get the impression that $T(i)=2^{n-i}$. This guess can be proven by induction, since assuming that $T(i)=2^{n-i}$, we have
$$ T(i-1)= \sum_{k=i-1}^n T(k+1)= T(i)+\sum_{k=i}^n T(k+1)= 2 T(i) = 2^{n-(i-1)} .$$

Thus, $T(0)= 2^n$ and therefore it is not in $O(n^2)$.

PS I assumed that in the recursion the value of opt is never stored and will always be recomputed.


Floating Point Arithmetic with 3 bits mantissa

The problem is underspecified, but I'll assume IEEE 754 default behavior.
In IEEE 754, at least in space-constrained floating-point formats, a bit is saved by not storing the leading bit of the mantissa, which is always 1. So the representation of the number 1 would have 000 in the three mantissa bits.
The next largest representable number is 1.001 in binary (001 in the mantissa bits). The next smallest representable number I'll leave for you to figure out (it's not 0.111).
In IEEE 754, addition works by calculating the exact sum of the addends over the reals (infinite precision), then rounding to a representable floating-point number. In the default mode (round to even), you round to the nearest representable value, or if you're exactly halfway between representable values, the tie is broken in favor of the one with 0 in the least significant mantissa bit.
If $a$ is the next smallest representable number below 1, and $b$ is 1.001, then sums in the interval $\left[\frac{a+1}2, \frac{1+b}2\right]$ will be rounded to 1. (It's closed on both ends because round-to-even breaks the tie in favor of 1.) From there it's easy to answer the question.


What is the minimum pumping length of the following languages?

I understand that a pumping length for a language $K$ is a constant $c_K$ such that each string that has at least that language can be pumped within the language. Here "pumped" can remain somewhat abstract: it may be regular or context-free "uvwxy" pumping for instance.

It is clear that we can take $c_{K\cup L}\le \max\{c_K,c_L\}$. Any string in $K\cup L$ of at least this length can be pumped within either $K$ or $L$ depending or where it comes from.

It seems we cannot say more than that. The main reason is that we can pump one language into the other. Look at a variant of your last example. If $K$ is finite, say it contains all words shorther than $m$, then $c_K = m$, as no word in $K$ can be pumped. Let $L$ be the complement of $K$ containing all words of length at least $m$. Then $c_L = m+1$ (assuming that pumping incluses "pumping down" where we obtain shorter strings). However $c_{K\cup L}=c_{\Sigma^*}=1$.

I am afraid that for concrete examples you have to do a separate analysis.


Can a RAM calculate its own Gödel number?

Consider the computable function $Q\colon \mathbb{N}\times\mathbb{N}\to\mathbb{N}$ given by $Q(x,y) = x$.  By Kleene's second recursion theorem, there is some $p$ such that the program with Gödel number $p$ computes the function $f(y) = Q(p,y)=p$, i.e., a program which outputs $p$ for every input. This is exactly the program you're looking for: for any input, it outputs its own Gödel number.

Such a program is known as a quine, and they exist in any Turing-powerful model of computation.


A minimal automaton for a language quotient $w^{-1}L$ if $L$ is regular

Now that the question is clarified, I transform my comment into an answer and improve the construction. Our goal is to construct a minimal automaton for $w^{-1}L$ given a minimum automaton $A$ for $L$ and $w$.

It is known that $A$ is isomorphic to the automaton where the state correspond to quotients of $L$. This is the minimal automaton that you describe in your question.

Observe that the quotients of $w^{-1}L$ are also quotients of $L$ since $u^{-1}(w^{-1}L) = (wu)^{-1}L$. Thus, intuitively, you have in $A$ all the states that you need for constructing a minimal automaton for $w^{-1}L$.

First, we claim that the automaton $A$ where we change the initial state to be $w^{-1}L$ recognize $w^{-1}L$. Indeed, by reading $v$ from $w^{-1}L$, you end up in the state $v^{-1}w^{-1}L$. We have then $v \in w^{-1}L$ if and only if $\epsilon \in v^{-1}w^{-1}L$ iff $v^{-1}w^{-1}L$ is final.

Now we have two things to do: first, find the state in $A$ that corresponds to $w^{-1}L$: it is easy, it is the state reached by reading $w$ from $q_0$. Second, we have to minimize this automaton. We claim that if we only keep states that are reachable from state $w^{-1}L$ then we will have a minimal automaton for $w^{-1}L$. Indeed, this automaton still recognize $w^{-1}L$ as we only removed dead state. Moreover each remaining state represents a non-empty quotient of $w^{-1}L$ and two states represent two different quotients. Thus, it has the required minimal size.

To summarize the algorithm:

read $w$ in $A$ and reach state $q$
remove states that can't be reached from $q$
set $q_0 := q$.


Can a Turing Machine decide if a regular expression matches all strings of exactly some length $l \geq 1$?

I think this procedure should work...

First, construct a DFA for the language. Now, start tracing all possible paths of length $k$ (start with $k = 1$). Call $S_k$ the set of states reached by strings of length $k$.

If at any point you find $S_k \subseteq A$, the set of accepting states, the answer is yes, and return.

If, on the other hand, you find that $S_{k} = S_{k'}$, where $k' < k$, before you find an $S_k$ that works, you know that you'll never find an $S_k$ that works, and you can stop looking. The reason is that the next length you try, $k + 1$, will yield $S_{k+1} = S_{k'+1}$, another set that didn't work... and so on.

Note that this procedure is guaranteed to terminate since there are a finite number of possible $S_k$; since they're subsets of the set of all states, $S$, there are no more than $2^{|S|}$ of them. By the pigeonhole principle, if you've tried enough candidates, you'll either have already found one that worked, or you'll have tried some set more than once.

Apologies in advance if this is completely missing the point of the question, blatantly wrong or intellectually hilarious.


Don't understand one step for AVL tree height log n proof

You can continue as same as line 4 the process like that:

$$ N_h > 2N_{h-2}> 2(2 N_{h-4})>2(2(2 N_{h-6}))>\cdots$$
As you can see, the indexs are decreasing by substracting $2$ in each step when you use the inequality. So, the process stops when the index $h$ takes $0$, but from the indexs behavior the half of $h$ (floor) will be the quantity of times that we substract $2$ from $h$.

$$ N_h > 2N_{h-2}>\cdots>2(2(2(2(2h^{h-10}))))> 2^{\frac{h}{2}}$$


Performance gain by implementing streamlined simplex

By "streamlined", I assume you are talking about a minimum cost flow algorithm, and you have been using the standard LP solver from Coin-OR. Then I would advise using the solver from the Lemon library (from Coin-OR as well). It has Python bindings.

As for the performance, I never benchmarked it myself. Given the algorithms involved, however, just the datastructure specialization may well be a 10x improvement. For some problems, I guess the difference may well be orders of magnitude.

I don't think Coin-LP detects the network structure - I'm pretty sure neither it nor GLPK does.

There are algorithms specialized for transportation problems (even more specific than MCF), but here you'd probably have to reimplement them, and not gain as much as going from generic simplex to minimum cost flow.

While looking for benchmarks, I just found two other solvers linked from this blog post, with performance claims: Google OR-tools and PyMCFSimplex.


Increasing Cache Line and Programs with bad Spatial Locality

There will be minimal, to no effect on the miss rate of a program with low spatial locality.


What is minimization (μ-function) in layman tems?

This is minimization in Python:
def mu(p):
    n = 0
    while not p(n):
        n += 1
    return n

It is a slightly more complicated exercise to convert a while to $\mu$, but essentially, $\mu$ performs a search for the first (minimal) number satisfying a given condition, where there is no guarantee that the search will succeed.


Is function with finite amount of $\Phi_x(x+1)$ occurrences Turing computable?

You can compute this function using a table of size 51. More generally, if $f$ is a function which differs from a computable function $g$ on a finite number of inputs, then $f$ is computable as well. In our case, $g$ is the constant zero function, which is trivially computable.


Start with $5|E(G)|$ variables $x_{e,i}$, one for each $e \in E(G)$ and $i \in \{1,2,3,4,5\}$. Intuitively $x_{e,i}$ means that edge $e$ is colored with color $i$.

A CNF formula $\phi$ can be obtained by the logical and of the following sub-formulas.

Each edge must have exactly one color:

At least one color, for each $e \in E(G)$:
$(x_{e,1} \vee x_{e,2} \vee x_{e,3} \vee x_{e,4} \vee x_{e,5})$
At most one color, for each $e \in E$, and $i,j \in \{1,2,3,4,5\}$ with $i<j$:
$(\overline{x_{e,i}} \vee \overline{x_{e,j}})$

The coloring must be proper:

For each pair $e,f \in E(G)$ of adjacent edges and for each $i \in \{1,2,3,4,5\}$:
$(\overline{x_{e,i}} \vee \overline{x_{f,i}} )$

If $e=(u,v)$ is an edge of $G$, let $f^e_1,f^e_2$ be the two edges other than $e$ that are incident to $u$, and $f^e_3,f^e_4$ be the two edges other then $e$ that are incident to $v$.

For each $e \in E(G)$ add a new variable $r_e$. This will encode "if $e$ is not rich, then $r_e$ is true": Notice that if $e$ is rich then $r_e$ can always be set to false.
For every $i \in \{1,2,3,4,5\}$, every $j \in \{1,2\}$, and every $k \in \{3,4\}$:
$(r_e \vee \overline{x_{f^e_j, i}} \vee \overline{x_{f^e_k, i}})$
For each $e \in E(G)$ add a new variable $p_e$. This will encode "if e is not poor, then p_e is true". Notice that if $e$ is poor then $p_e$ can always be set to false.
For every ordered tuple $(j, k, h)$ of $3$ distinct elements from $\{1,2,3,4,5\}$:
$( p_e \vee \overline{x_{f_1,j}} \vee  \overline{x_{f_2,k}} \vee \overline{x_{f_3,h}})
\wedge
( p_e \vee  \overline{x_{f_1,j}} \vee  \overline{x_{f_2,k}} \vee \overline{x_{f_4,h}})
\wedge
( p_e \vee  \overline{x_{f_1,j}} \vee  \overline{x_{f_3,k}} \vee \overline{x_{f_4,h}})
\wedge
( p_e \vee \overline{x_{f_2,j}} \vee  \overline{x_{f_3,k}} \vee \overline{x_{f_4,h}})
$

Finally, this will encode "e is rich or e is poor":

For every $e \in E(G)$: $(\overline{r_e} \vee \overline{p_e})$

If you have a satisfying truth assignment for $\phi$ then you can color edge $e \in E(G)$ with color $i$ iff $x_{e,i}$ is true.

If you have a coloring then let $c(e) \in \{1,2,3,4,5\}$ be the color of edge $e$. You an get a satisfying truth assignment for $\phi$ by setting:

$x_{e,c(e)}= \top$, and $x_{e,j} = \bot$ for $j \in \{1,2,3,4,5\} \setminus \{ c(e) \}$,
$r_e = \bot$ iff edge $e$ is rich,
$p_e = \bot$ iff edge $e$ is poor.


Expressing properties of elements of the universe in first order logic is mostly achieved through defining appropriate relations. So for this you might like to consider relations like:

$P(x)$ - $x$ is a person,
$C(x)$ - $x$ is a course,
$Pre(x,y)$ - $x$ is a prerequisite of $y$ (note that this doesn't actually say that $x$ and $y$ are courses),
$Pass(x,y)$ - $x$ has passed course $y$.

(The parentheses are just included for clarity - you may have seen different notation where relations are written without.)

Then the rest is just building the logical formula, which in this case should be fairly obvious.

   $notready(x,a) \equiv P(x) \wedge C(a) \wedge \exists y(C(y) \wedge Pre(y,a) \wedge \neg Pass(x,y)) $


What graph data structure works fastest with Dijkstra's algorithm?

Implementing Dijkstra's algorithm with a Fibonacci-heap gives $O(|E|+|V|\log |V|)$ time, and is the fastest implementation known.

As for the representation of the graph - theoretically, Dijkstra may scan the entire graph, so an adjacency list should work best, since from every vertex the algorithm scans all its neighbors.


Problem to understand a Bellman Ford algorithm exercise

The only way to understand it is to break it down.

Given a weighted, directed graph $G=(V, E)$ with no negative-weight
cycles, let $m$ be the maximum over all vertices $v \in V$ of the
minimum number of edges in a shortest path from source $s$ to
$v$. (Here, the shortest path is by weight, not the number of edges.)

Okay, so $s$ is fixed, and let us suppose you have a vertex $v$.
Now we look at all the cheapest paths from $s$ to $v$ and we take the
path that has the fewest edges; this number of edges we refer to as $m_v$.
If we repeat this for every vertex $v \in V$, then we get one $m_v$ for
each $v$.  The value $m$ is the maximum of all $m_v$s, or $\max_{v \neq s}m_v$.
Or in other words, over all cheapest paths starting in $s$, let us look at
the vertex with the longest shortest.  It has length $m$.
It is confusing because we want the longest shortest over all the cheapest.


Why does x86 has explicit register definitions, and RISC's doesn't?

The main historical trend that accounts for the change in instruction sets is the dropping cost of memory.  The x86 instruction set derives from the 8080, which derived from the 8008.  The 8008 was first sold in 1972, when the cost of memory was about US\$0.05 per bit.  1 MByte would have cost about US\$400000, and even a KByte cost about \$400.    Now you can get 4GB of DRAM for less than $40 (US\$0.00000000125 per bit) so the price has dropped by a factor of about 40 million in 40 years. (I may have missed a decimal place somewhere, and it also doesn't account for inflation (another factor of 5 or 6).  But you get the idea.)

Expensive memory meant you needed to try to make the instructions as small as possible.   There are a couple of ways you can do that.  One way is using variable length instructions. The 8008 and 8080 had 1 byte instructions.  If an instruction needed immediate data, the constant would be stored in the following byte (or bytes for 16-bit constants in the 8080).  So instructions could vary between 1 byte and 3 bytes.

Another is to make the register operands implicit.  The 8008 and 8080 each had 8 registers, so to specify two source registers and a destination register would have consumed 9 bits (already more than a byte!)  Instead of having three operands, you can try to get away with 2.  Most x86 instructions have 2 operands, one is the destination and also one of the sources, while the other is a source.  But you can do still better.  By assuming that all arithmetic instructions use the accumulator register as both the first source and the destination you only need to specify a single source operand.  Similarly if you assume that all the stack manipulation instructions work on a specific stack register you can get away with not specifying the register holding the stack pointer.  Similarly with loop counter increments and tests you can get away with no register specifiers if you have a dedicated loop counter.

Instruction compression of this kind is good but it comes at a couple of costs.  The most important cost is that the instructions are variable length and hard to decode.  The 8080 took several cycles to decode each instruction.  By the 1980s the cost of memory had come down considerably, and people started to realize that by making instructions easier to decode it would be easier to design high-performance pipelined processors.  RISC instructions are designed to be easy to decode (and to not have more than one memory operation so that they can be pipelined).

Instruction set design still has a small effect, mainly seen in power consumption.  In general the decoders on x86 machines consume more area, and also more power, per instruction decoded than do machines with RISC instruction sets.  On the other hand the x86 power consumption can be reduced somewhat during tight loops by caching a small number of decoded instructions.  Additionally the number of instructions to encode a program in x86 is about half that to encode the same program with a RISC instruction set, so the instruction fetch bandwidth (and thus the power consumption for instruction fetch) is a bit lower with x86 than it is with RISC instruction sets.


I bought that set for my grand son (nice and cheap Ikea product, kids love it from 18 month to 80 years, though not rcommended before 3 years of age), so I am very experienced with the
problem.

For the uninitiated, the tracks are oriented because they connect with a hole on one end and a hooking tongue on the other end. So curved tracks have to be placed with one side or the other up, depending on which way you want to turn. The Ikea picture does not make it obvious: the little plastic pieces are actually glued as tongue on one end of a track, but the curves track have grooves for the wheels on both sides.

Counting the configurations

I will use the word configuration for a way of putting the track
elements together. It seems more appropriate than the word
"permutation" which has a precise technical meaning.

The first analysis, described in this section, consist in evaluating
the total number of possible configurations. This will help us to
actually enumerate them in the next part.

You have 16 track elements, including 4 straight and 12 curved.

If you consider your 16 elements in succession, you have $\binom {16} 4
=\frac{16!}{4!\times 12!} $ ways of choosing a combination of
positions for the 4 straights tracks, among 16.

Now, if you consider the curved tracks, they can be placed either as
left curve or as right curve. For 12 tracks that makes $2^{12}$
possibilities (using train tracks to implement binary numbers makes
for heavy duty computers).

So the total number of "permutations" (that use of the word does not
seem too appropriate) is the product of the two numbers, since they
correspond to independent choices, i.e.,
 $$\frac{2^{12}\times 16!}{4!\times 12!} $$

But this answer may not be quite correct: if you have a closed circuit, you can consider it to start with any of the track elements, so that it counts for 16 "permutations", though one might consider it should count for 1. Hence, it might be appropriate to substract 15 from the result for each closed circuit that can be constructed. Geometric analysis of the shape of track elements shows that there are several closed circuits that can be constructed. Note that, except for the eight shape with crossing
tracks, circuits are oriented, and each shape must me counted twice.

Other closed circuits are possible with with less track elements, in particular with exactly 8 curves, and 0, 2, or 4 straight. But we now ignore the issue of closed curves.

If you consider $n$ elements, $8\leq n\leq 16$, of which $m$ are straight, with $0\leq m\leq 4$, the number of circuits is
$$\frac{2^{n-m}\times n!}{m!\times (n-m)!}$$

Thus, for all possible values of $m$, with a number $n$ of elements, including at most 12 curved, the total number of circuits is:
$$\sum_{m=\max(0, n-12)}^{m=4}\frac{2^{n-m}\times n!}{m!\times (n-m)!}$$

Finally, considering all possible values of $n$ in $[8,16]$, we get the
number of circuits:
$$\sum_{n=8}^{n=16} \sum_{m=\max(0, n-12)}^{m=4}\frac{2^{n-m}\times n!}{m!\times (n-m)!}$$

Then there is the small number of cases when the circuit is closed, which one can analyse to count all their starting element variants as the same circuit.
Note that when the track does not cross itself, each closed shape comes in two variants: clockwise and counter-clockwise. But should I go in so many details.

Enumerating the configurations

The analysis used for counting configurationscan be repeated
identically to enumerate them.

We consider $n$ track elements, of which $m$ are straight and $p$ are
curved: $n=m+p$. We want to enumerate all the circuits that use all
these elements.

First, we want to place the $m$ straight track in the sequence of $n$
track element position. For this you must enumerate all combinations
of $m$ integers among the first $n$ integers. Algorithms already
exists to enumerate these conbinations, available in wikipedia, or
fromn other sources, so there is no point in developing that further
here.

Then, for each such combination, you simply try all possible
combinations of left or right positionning of curved track elements,
which you can do by enumerating all possible sequences of$0$ and $1$,
hence simply using a counter to enumerate in binary all integers from
$0$ to $2^p-1$. It is advisable to use the fast changing bits in the
enumeration on the end side of the configuration, in order to factor
the beginning of computations that might be used to check whether the
configurations give a closed circuit.

Of course, this can be repeated for other values of $m$ and $p$. But
configurations for smaller values are just prefixes of the
configurations for the maximum values of $n$ and $m$. So, doing it only for the maximum values should be enough to observe on the fly whatever we are interested in regarding smaller configurations. THis is detailed regarding closed circuits in the next section.

Checking a configuration

Given a configuration for a sequence of track elements, and starting
from porition (0,0), and direction angle 0, one can compute the
position and direction at the end of the first track element, then
propagate to the end of the second, and so on till the last. The
circuit is closed if the end of the last track element is in position
(0,0) with direction angle 0.

The shape of the track elements is determined by the fact that 8
curves make a full circle, and 12 cuves and 4 straight make an eight
shaped curve. One can use the radius of the circle as distance unit,
Then the staight track elements have a length of 1 radius.

For simplification, one can also take$45^o$ as the angle unit, so that
each curved track changes the orientation by plus (left) or minus
(right) one unit, and 8 units make a full circle. Hence orientation can be represented byrf an integer modulo 8.

Positions of track elements ends should not be computed as real
numbers, but as expression using integers and $\sqrt 2/2$, of the form $a+b\sqrt 2/2$, a bit like
complex numbers where $i$ is replaced by $\sqrt 2/2$. That makes the computations much cheaper, based on integer arithmetics on pairs $(a,b)$, and the
$\sqrt 2/2$ ultimately cancel each other for closed circuits.

Actually, to explain it formally, plane coordinates reachable from the
origin with straight and curved track elements are all expressible as
$a+b\sqrt 2/2$. Hence, since 2 coordinates are used on the plane, and
since $1$ is incommensurable with $\sqrt 2$, plane coordinates can be
seen as a 4-dimensional vector space over the field $\mathbb Q$ of
rationals, or better, since we use only integer coordinates in that
vector space, as a 4-dimensional module over the ring $\mathbb Z$ of
integer. See this mathematics question which is a followup to the question answered here.
Hence following track element by track element the configuration of a
circuit, for the purpose of checking whether it is closed, can be done
using only integer addition and substraction.

A circuit starts at the origin with orientation $0$. The circuit is
closed when it ends also at the origin with orientation $0$. In the
four dimensional space, the coordinates of the origine are $(0,0,0,0)$

I guess any reader can further develop the computation details, for
each type of track element. (this answer is already very long).

As explained in the previous section, doing the enumeration for maximum values of $n$ and $m$ will include smaller configurations as prefixes. In particular,
if you are looking for closed circuits of all sizes, the simplest is
to compute all configurations with the maximum values of $n$ and $m$,
and check closure not just at the end, but at every step of the
computation of track elements positions. However, there is a
possibility for some optimization in performing these checks, as no closed circuit can be found
with less than eight curved track elements.


Kurki-Suonio has shown some helpful properties [1]:

  Theorem 1
  Each LL(k) grammar is unambiguous.

That means any inherently ambiguous language is not LL(1).

  Theorem 9
  For any $k>1$ the grammar $G$:

  $\qquad \begin{align}
  S &\to aSA \mid \varepsilon \\
  A &\to a^{k - 1} b S \mid c
\end{align}$

  generates an LL(k) language which is no LL(k-1) language.

There you have another concrete example by setting $k=2$.

As for your language $L$, assume $L$ is LL(1) and consider the language

$\qquad \displaystyle L' = \{ a^nb^m \mid n < m \land m > 0 \}$.

We make the following observations:

$L'$ is LL(1) by the grammar

$\qquad \begin{align}
    S &\to AbB \\
    A &\to aAb \mid \varepsilon \\
    B &\to bB \mid \varepsilon
  \end{align}$
Neither $L$ nor $L'$ is regular (by Pumping Lemma).
$L \cap L' = \emptyset$.
$L \cup L' = \{a^nb^m \mid n,m \in \mathbb{N}\} \in \mathsf{REG}$.

In unison, these facts contradict this theorem [2]:

  Theorem 9
  If the finite union of disjoint LL(k) languages is regular, then all the languages are regular.

Thus, $L$ can not be LL(1) (and in fact not LL(k) for any k).

Notes on top-down languages by R. Kurki-Suonio (1969)
Properties of deterministic top-down grammars by D.J. Rosenkrantz and R.E. Stearns (1970)


Since $ab$ is a DCFL, your result would imply that DCFLs are closed under concatenation, which they aren't. So your result can't hold.


Quick sort, Hoare's partition algorithm. Is there a mistake in CLRS?

The problem statement is correct.
I think you getting confused about: repeat $j \gets j-1$ until $A[j] \leq x$. It means that if $A[j]>x$ then do $j \gets j-1$.
Similarly, loop $8-10$ means that if $A[i]<x$ then do $i \gets i+1$.
Therefore, the algorithm executes in the following way on $A = [1,2]$:

After the loop $5-7$, $j$ becomes $1$ since $A[2] > x$.

After loop $8−10$, $i$ becomes $1$ since $A[1] = x$.

Since $i = j = 1$, the algorithm terminates and returns $1$.


Solution 01) Analysis what code does.

Your code execute the first loop n times.

And for each executions on first loop it will execute n times.

So the result will be n * n = n^2

Solution 02)
Try to count how many times execute the instruction

def f(n):
count = 0
i = 0
  while i < n:
   j = 0
     while j < n:
      j = j + 1
      print("execute:" + count)
      count = count + 1
 i = i + 1


Equivalence of Context-Free-Grammar and Context-Free-Grammar in CNF

Chomsky normal forms are not unique. If they were, we'd have an algorithm for deciding whether two CF grammars are equal. But equivalence of CF grammars is undecidable.


A reflexive, symmetric and transitive relation $R$ on $O$ is the same as a partition of $O$. If $(o_i,o_j) \in R$ then $o_i,o_j$ are in the same partition, and so can be merged. If $(o_i,o_j) \notin R$ then $o_i,o_j$ are not allowed to be in the same partition. After merging, we reach the following problem:

  Given a graph, partition the set of vertices so that each partition is an independent set.

Equivalently (up to a permutation of colors):

  Given a graph, find a proper coloring.

Intuitively, it seems that a random partition will have many parts, so you can try to generate a random sample in the following way. Greedily sample a "small" independent set whose size you choose in advance as a Poisson random variable with constant expectation, remove it from the graph, and repeat. Of course, this won't be a uniform sample. You can gather statistics in some small cases to see what is a good choice of parameters in this procedure, and whether the results are good enough for your purposes.


Why the alphabet of the digital information is composed of 2 elements?

You are really asking three different questions:

Why are computers based on binary?
Why did Boole use a binary system?
What does all of this have to do with entropy?

The answer to the first question, as you suspect, relies on implementation details; see for example this question. In other circumstances, such as wired or wireless communication, information is transmitted in larger chunks, what is known as modulation.

The answer to the second question is simpler: Boole was formulating the laws of thought, that is logic, in which each statement is either true or false. That's your binary distinction.

Finally, I can't really follow your third question. According to Shannon's source coding theorem, you can optimally compress information using any channel. Text is usually stored as text since it's easier to process that way, but we can compress it to reduce its size to roughly the entropy. In some sense, text is stored using an alphabet of size roughly 64, including lower and uppercase letters, digits and punctuation marks. Other data is stored in bytes, which is an alphabet of size 256. All of this has nothing to do with entropy, rather it's ease of processing. These are just some thoughts, since I can't really understand this question.


Algorithm for fewest moves in 1's, 10's, 100's, etc

You can construct a graph with vertices $0,1,2,3,4,\dots,10000$, two vertices are adjacent if you can construct a number with a single operation from another one. A single operation is either adding or subtracting $1,10,100,1000,\dots$. For example,$N(46) = \{45, 47, 36, 56, 146, 1046,\dots\}$. Then the minimum number of operations required to construct a number $x$ is the shortest path from $x$ to 0. Since graph is undirected, you can run a single one to all algorithm (Dijkstra,BFS) and obtain all distances from 0 to any other vertex. Also the graph is pretty sparse, hence Dijsktra with heap will nail it. An implementation might no need to construct the whole graph, since neighborhoods are small and easily computable on the fly.

EDIT:
if you take Dijkstra code from Geeks, you can construct graph as

for(int v1 = 0; v1 < V; ++v1)
   for(int v2 = v1+1; v2 < V; ++v2)
      if(v2 - v1 == 1 || v2 - v1 == 10 || v2 - v1 == 100)
         g.addEdge(v1,v2,1);
 g.shortestPath(46); // gives 8 to 121


Are fractions more computationally "expensive" than whole numbers?

This link below compares all arithmetic operations between floating point and integer variables on various architectures and processors.

With the general conclusion drawn that additions and subtraction are roughly equal, the performance impact arises in multiplication and division operations; with integer being faster. (Except for x86-64 AVX and POWER8 AltiVec where it is faster in the former for floating point and equal in the latter.)

Integer and Floating-Point Arithmetic Speed vs Precision: http://nicolas.limare.net/pro/notes/2014/12/12_arit_speed/


Decidability of a Turing machine which always halts in at most ten steps

Consider the following hint:

If $M$ is a TM, and it is given an input of length $12$ (for example), but you only allow $M$ to operate for $10$ steps,
what can it do with the input?


Bare Metal Operating Systems in High Performance Computing

The Return Infinity site you linked claims that BareMetal is an Exokernel.

Exokernel was an MIT research project from the mid to late 1990s which is still widely studied.  The philosophy behind Exokernels was that they would provide just mechanism and all policy would move to user-level libraries.  In later papers they more specifically said that the kernel provides protection and the libraries provide management.  The idea was to avoid expensive abstraction layers that are actually unneeded by certain applications.

In hindsight, it is probably not unfair to claim that the main achievement of the Exokernel research project was to invent a number of very clever techniques to make a microkernel OS perform better than a monolithic OS in some cases.  The key, I think, was finding ways to avoid kernel-boundary crossing costs.  One way they did this was through judicious and careful mapping of kernel data structures into an application's memory space.  This allows large amount of data to be transferred across the kernel/user boundary with fewer system calls and address space changes.  They also came up with several techniques for describing network and file system policies with tiny languages that could be easily checked and safely checked inside the kernel.  (So the core filesystem and network handling in Exokernel is actually done inside the kernel, rather than from a user-level service across an isolation boundary like it might be in a naive microkernel.)

The canonical paper on Exokernels is (IMHO) one of the best systems experience papers I've ever read.  It's been quite a while since I read it, but I recall it as being quite honest about both strengths and weaknesses of the approach.

Kaashoek, M. Frans; Engler, Dawson R.; Ganger, Gregory R.; Briceño, Héctor M.; Hunt, Russell; Mazières, David; Pinckney, Thomas; Grimm, Robert; Jannotti, John; Mackenzie, Kenneth: Application Performance and Flexibility on Exokernel Systems, Proceedings ACM Symposium on Operating Systems Principles, (SOSP-15):251-266, 1995.  (That's a Citeseer link and the Citeseer server is often down, so here also is the ACM link (paywalled).

The wikipedia article on Exokernels is not terrible, and gives a reference to at least one other (later) research project, Nemesis from Cambridge University.  Another efficient microkernel project that was being worked on around the same time as Exokernel was the L4 microkernel by Jochen Liedtke.


Finding two words of lengths that are relatively prime in a regular language?

Consider a minimal DFA for $L$. Each state in the DFA has one outgoing edge, so the DFA looks like a path entering a cycle. That means that $W = \{ n : a^n \in L \}$ is eventually periodic: for some $k,l$, for all $n \geq k$ it holds that $n \in W$ iff $n + l \in W$. We are now left with a problem in number theory, which I leave for you to ponder. (Try a few examples to see when an eventually periodic $W$ can fail to satisfy the property you're looking for.)


Reducing independent set to triangle-free subgraph

Let $\langle G=(V, E), k \rangle$ be an instance of Independent Set, and call $n=|V|$.
Let $N$ be a set of $n+1$ new vertices (not in $V$), and construct a new graph $G' = (V', E')$ where $V' = V \cup N$ and $E' = E \cup (N \times V)$.

If $G$ has an Independent Set $S$ of size at least at least $k$ then $G'$ has a Triangle-Free set $S'$ of size at least $n+k+1$.

Select $S' = S \cup N$.
To see that the subgraph of $G'$ induced by $S'$ is triangle free consider any triple $(a,b,c)$ of distinct vertices in $S'$.
Clearly, if more than one of $a$, $b$, and $c$ is in $N$, the triple cannot induce a triangle since $G'$ has no edges between vertices in $N$. On the other hand, if at least two distinct vertices $u,v \in \{a, b, c\}$ are in $S$, then $(u,v) \not \in E$ and hence $(u,v) \not\in E'$.

If $G$ has a Triangle-Free set $S'$ of size at least $n+k+1$ then $G'$ has an Independent Set $S$ of size at least at least $k$.

Let $S=S' \setminus N$.
Since $|S| \ge n+k+1$ and $|N|=n+1$, the cardinality of $S$ is at least $k$.
To see that $S$ is an Independent Set of $G$ notice that $S' \cap N \neq \emptyset$ and let $v \in S' \cap N$. Let $a$ and $b$ be any two distinct vertices in $S$. Since the subgraph of $G'$ induced by $S'$ is triangle free and $\{(v,a), (v,b) \} \subseteq E'$, we must have $(a,b) \not\in E' \supseteq E$.


Is it possible to prove Language L context-free?

S → AB
A → aAb | ε
B → bBa | ε

This will be the Grammar for that language which follows the context free grammar rules, so the language generated will be CFL.


Your program is not a SAT solver.    A SAT solver takes as input a SAT formula and outputs whether it is satisfiable or not.  Your program doesn't take as input a SAT formula, so it isn't a SAT solver.

Yes, there are multiple ways of reducing Sudoku to SAT.

With standard Sudoku puzzles, we are promised that there exists exactly one valid solution.  With SAT, there might be 0, 1, 2, or more satisfying assignments, and we are asked to determine whether there exists 0 satisfying assignments or 1+ satisfying assignments.  Valiant and Vazirani considered the following problem: given a SAT formula with the promise that it has either 0 or 1 satisfying assignments (not more than 1), determine whether it has 0 satisfying assignments or 1 satisfying assignments.  They showed a randomized polynomial-time reduction showing that this problem is at least as hard as SAT (specifically, there is no polynomial-time algorithm for this problem either, unless NP=RP).

More generally, we could ask about the following problem: given a SAT formula with a promise that it has exactly 1 satisfying assignment, find the satisfying assignment.  This problem is the analogue of Sudoku (where we're given a Sudoku puzzle with the promise that it has exactly 1 valid solution, and we're asked to find that solution).  It follows from Valiant and Vazirani's result that this problem is at least as hard as SAT under randomized polynomial-time reductions; if you could solve this problem in polynomial time, you could solve SAT in (randomized) polynomial time.  So, the promise that a SAT formula has exactly 1 valid solution doesn't make it any easier to find the solution.

Further reading: UniqueSAT and UnambigousSAT at https://en.wikipedia.org/wiki/Boolean_satisfiability_problem#Extensions_of_SAT, https://en.wikipedia.org/wiki/Valiant%E2%80%93Vazirani_theorem, https://cstheory.stackexchange.com/q/1639/5038, Unique SAT complexity clarification, Proof of SAT is randomly reducible to UNIQUE-SAT, https://cstheory.stackexchange.com/q/22093/5038.


Constraint on Universal set of hash functions

Let's plug real numbers into the passage:

$|\mathscr{H}|$ = 10;

$m$ (size of hash table) = 100

In the first statement:

$\frac{|\mathscr{H}|}{m}$ = $\frac{10}{100}$ = 0.1 = the maximum number of hash functions that will cause a collision. (Assuming the count of functions in $\mathscr{H}$ can be represented as decimals for sake of argument.)

The important thing to note here is that the chance of selecting a collision causing hash function is: $\frac{0.1}{|\mathscr{H}|}$ = $\frac{0.1}{10}$ = 1%.

In the second statement:

The argument being made is that the chance of collision "is no more than..":

$\frac{1}{m}$ = $\frac{1}{100}$ = 1% = the chance of generating a hash value $h(key)$ from the set {0, 1..., 99}. AKA the chance of selecting a specific value from 100 values.

Conclusion:

So, from our example, a collection of 10 hash functions that map a given universe of keys into the range {0, 1..., 100 - 1} is said to be a universal collection if: by randomly choosing a hash function, the chance of collision between distinct keys is no more than 1%.


Finding vertices for which there either exists a path to all other vertices or other vertices have a path to them

We can assume that the DAG is connected, since otherwise the solution is trivial. Consider some topological ordering of the vertices. A vertex $v$ satisfies your condition if (1) $v$ can be reached from all vertices preceding $v$ in the ordering and (2) all vertices following $v$ in the ordering are reachable from $v$. We can check conditions (1) and (2) separately.

To check condition (2), traverse the topological ordering in order, and for each vertex encountered, remove the vertex. Since this is a topological ordering, when a vertex is removed, it is a source, that is, it has no incoming edges. Condition (2) is satisfied for the vertex iff it is the unique source at that point. Condition (1) can be checked similarly by traversing the topological ordering in reverse.


How does one go about designing a system that never crashes?

It wasn't possible back then, in the absolute sense. What you're essentially looking for when you say "never crashes" is a system that always makes progress towards its goals. Today, we can prove that a computer program does that, but the relevant methods to construct such proofs were only developed starting in the 70's - years after the Apollo Guidance Computer was developed.

Practically speaking, today we would formulate the requirements on the guidance computer using a formal specification language. In particular, we'd identify each task of the computer, and specify that each task finishes n a bound number of steps. We also define a task scheduler that never halts and chooses the right tasks for each stage of the mission. With a bit of work, we then prove that every task that needs to be executed is executed on time. We then transform the specification into code, in a way that allows us to verify the proof still holds.


Prove or disprove the following proposition $L_1^*∪L_2^*⊆(L_1∪L_2)^*$

This is true.
You only have to prove the following staments:

if $A\subseteq B$ then $A^{*} \subseteq B^{*}$,
If $A\subseteq C$ and $B\subseteq C$ then $A \cup B \subseteq C$.

We know $L_1 \subseteq L_1 \cup L_2$ for 1. we can conclude $L_1^{*} \subseteq (L_1 \cup L_2)^{*}$, analogously $L_2^{*} \subseteq (L_1 \cup L_2)^{*}$. For 2. we can conclude $L_1^{*} \cup L_2^{*} \subseteq (L_1 \cup L_2)^{*}$.


Show that recurrence is $O(\phi^{\log n})

Your sequence (shifted by 1) is known as Stern's diatomic sequence, or the Stern–Brocot sequences. The usual recurrence is:
\begin{align}
&a(0)=0 \\ &a(1)=1 \\ &a(2n) = a(n) \\ &a(2n+1) = a(n) + a(n+1)
\end{align}
The recurrence suggests that the answer has something to do with binary representation, so one might be prompted to look at the maximal value of $a(n)$ among numbers of length $m$ in binary:
$$
1,2,3,5,8,13,\ldots
$$
This is the Fibonacci sequence. (One can check that the first maxima are attained at $(2^n-(-1)^n)/3$.)

From here, one immediately sees that the rate of growth is $O(\phi^{\log_2 n})$.

More can be said. For example, Coons and Tyler determined the best possible constant in front of $\phi^{\log_2 n}$ in their paper The maximal order of Stern's diatomic sequence.

You can find many more links in the OEIS entry A002487.


Longest common subsequence solution reconstruction during DP is wrong

Programming questions are off-topic here.
Anyway your matrices table and solution are not properly initialized as they contain references to the same objects. Try:
    table = [[0]*(m+1) for j in range(n+1)]
    solution = [ ["" for i in range(m+1)] for j in range(n+1) ]

Moreover, the returned string should be solution[n][m] and not solution[n-1][m-1].


Is the language $L=\{a^nb^mc^k | k \ge max (m,n) \}$ CF

Your intuitive argument is wrong. If you print a $c$ for every $a$ or $b$ you see, then the language will have $k\ge m+n$ rather than $k\ge \max\{m,n\}$.


Yes, you can obviously solve it like that.

If you are dividing the array into two parts, than the maximal sub-array can be completely in the left half, completely in the right half, of it starts in the left and ends in the right half.
The first two cases you will find using the recursive calls.
For the third case, you have to do a little bit of work:

In that case the maximal subarray consists of two parts, a suffix from the left half of the array, and a prefix of the right half of the array. Either both products are positive, or both negative. It's obvious that you want their absolute value as big as possible, therefore you need to know the largest and smallest suffix from the left half, and the largest and smallest prefix from the right half. You can compute both in $O(n)$ time, which gives you the recurrence relation $T(n) = 2 T(\frac{n}{2}) + O(n)$ which gives you $T(n) = O(n \log n)$ by the master theorem.

Notice, you can also compute these values during the recursive calls, which gives you $T(n) = 2 T(\frac{n}{2}) + O(1)$, and this gives you the final complexity $T(n) = O(n)$.


Are any problems in P known to have logarithmic-time-verifiable certificates?

The question here is that in the certificate definition of $\mathsf{NP}$, what is more important is the size of the certificate (in the size of the input), the complexity class that  the certificate verifier belongs too is less important. In fact you can take the verifier to be in $\mathsf{AC^0}$ as long as the size of the certificates are polynomial in the size of the input and you will still get the whole problems in $\mathsf{NP}$. $\mathsf{AC^0}$ is a very small complexity class that is included in almost every complexity class you have heard of.

To obtain smaller classes you also need to restrict the way the certificate verifier accesses the certificate. One kind of restriction that is considered is restricting the number of times  the verifier can read the input using a log-space verifier. Something similar may work to capture $\mathsf{P}$, but just capturing it in this way is not interesting. The certificate definition should be nice and interesting so that it would give us some insight about $\mathsf{P}$. The certificate definition of $\mathsf{NP}$ is interesting because it is an exceptionally nice, it is even more intuitive than the original definition using non-intuitive non-deterministic machines. It allows us to cast the question regarding $\mathsf{P}$ vs. $\mathsf{NP}$ as "efficient solving vs. efficient verifying". Just having a certificate definition by itself is not very interesting.


You have been going well. Yes, $L_3=L_1\cap L_2\in\text{ RE} $.

Could it be that $L_3$ is recursive?

The answer is not necessarily. There are several cases here.

If $L_1$ is a recursive language as well, then $L_3$ is also recursive.
If $L_1$ is not a recursive language, then $L_3$ may or may not be recursive.

For example, let $L_2$ be the languages of all words. Then $L_3=L_2$ is not recursive.
For example, let $L_2$ be the language that does not contain any word. Then $L_3$ is also the language that does not contain any word, which is recursive.

Exercise 1. Show that if both $L_1$ and $L_2$ are recursive, then $L_1\cap L_2$ is recursive.

Exercise 2. Construct two languages $L_1$ and $L_2$ that satisfy all following conditions.

$L_1$ is recursively enumerable.
$L_2$ is recursive and $L_2$ is not the language of all words.
$L_1\cap L_2\subsetneq L_1$ is recursively enumerable but not recursive.