Recover NLFSR description from given output

Normally we evaluate PRNGs under the model where the source code is available and fully known, and where the output is a deterministic function of the seed.  This leaves multiple possibilities for how to build a NLFSR: we can have a fixed feedback function (hardcoded in the source code), and use the seed to specify the initial state; or we can use part of the seed to generate a feedback function and use the remainder of the seed to specify the initial state.

If the feedback function $f$ is known, it is trivial to predict the next outputs of the NLFSR from the past $n$ bits, where $n$ denotes the width of the state.  Also, it is often possible to predict past output, but this depends on the feedback function and on $n$.

If $f$ is not known but derived from part of the seed, then the procedure depends on the details of how it is derived.  There are $2^{2^n}$ possible feedback functions $f:\{0,1\}^n \to \{0,1\}$.  If we use $2^n$ bits from the seed so we can sample uniformly at random from the set of all functions (i.e., all $2^{2^n}$ functions are possible and equally likely), then the PRNG is not very useful in practice.  After seeing about $O(2^{n/2})$ bits of output, you can usually distinguish the output of the PRNG from true-randomness and predict future outputs, because (by the birthday paradox) it is likely that the internal state will repeat at some point in there and the generator will enter a cycle (of length at most $O(2^{n/2})$).  Of course this design requires more than $2^n$ bits of true randomness as input, and can only produce $O(2^{n/2})$ bits of output before its output is recognizable, so this is a fairly crummy PRNG; you've basically wasted the randomness, and you might as well have just used the true-randomness directly without a PRNG.

Alternatively, perhaps you had in mind that part of the seed is used to select a feedback function $f$, via some algorithmic process -- but not all feedback functions are possible or equally likely.  Then the ability to distinguish, predict future outputs, or recover the seed is dependent upon the details of that algorithmic process.  However, we can say this much.  The output of the PRNG can be distinguished from truly-random after $O(2^{n/2})$ outputs, for reasons sketched above (due to the birthday paradox).

The period of a NLFSR is determined by the function $F:\{0,1\}^n \to \{0,1\}^n$, defined by

$$F(x_1,\dots,x_n) = (x_2,\dots,x_n,f(x_1,\dots,x_n)).$$

Let me mention some typical cases.

First, if $f$ satisfies $f(0,x_2,\dots,x_n)=f(1,x_2,\dots,x_n) \oplus 1$ for all $x_2,\dots,x_n$, then $F$ will be bijective, the period of the NLFSR will typically be about $2^n$ (if $f$ has no other regularities), and given about $2^n$ bits of output you'll be able to predict all future outputs (since it cycles) or recover the original seed.  Also, you'll be able to distinguish the output of the NLFSR from truly random with about $O(2^{n/2})$ bits of output (by the birthday paradox, a true random stream will have some $n$-bit value repeat twice within that range, but that'll never happen in the output from this type of NLFSR).

Second, if $f$ has no regularities or patterns and is basically random, then $F$ will fail to be bijective, and the period will typically be about $2^{n/2}$.  So, after $O(2^{n/2})$ bits of output you'll be able to predict all future outputs (since it cycles), and you'll be able to distinguish the output of the NLFSR from truly random with about $O(2^{n/2})$ bits of output (a true-random stream won't cycle but this NLFSR will).

If the feedback function $f$ is chosen randomly from a small list of possibilities (e.g., the ones listed in the paper you cited), then it is easy to recognize output from such a PRNG: just try each possibility in turn, and use the method described for the case where $f$ is known.  If there are $m$ possibilities for $f$, then $n+\lg m+O(1)$ bits of output suffice to infer which possibility is correct and verify that the output is consistent with such a NLFSR with high probability.

What this fails to account for is other attacks, which try to take advantage of structure in $f$.  For instance, suppose $f$ is chosen to have small circuit size.  Then it may be possible to recover $f$ with many fewer than $2^n$ bits of input: each consecutive $n+1$ bits of output gives us a known input-output pair $(x,y)$ for $f$ (namely, $x = $ the first $n$ bits, and $y =$ the $n+1$st bit), and given many such pairs, we can try to find a function $f$ that is consistent with all the pairs and has low circuit complexity.  That might be enough to uniquely determine the function $f$; if so, it may or may not be possible to recover it explicitly within a reasonable amount of computation (e.g., with BDDs, Karnaugh maps, or other methods).

Since the question is rather vague, that makes it rather hard to assess the possibilities for the latter kind of method.  So, I'll just end with a disclaimer that the analysis above might overestimate the number of bits of output needed to recognize/detect this kind of LFSR.


What is the difference between these terms?

Let $A,B\subseteq \Sigma^*$ be languages.

Many-to-one: A (computable) function $f:\Sigma^*\to \Sigma^*$  such that $\forall x\in \Sigma^*$, $x\in A\iff f(x)\in B$.
The names "Mapping reduction" and "Karp reductions", to my knowledge, refer to "Many to one".
The "Many to one" means that $f$ may not be injective.

Turing reduction: we say that $A\le_T B$ if, given an oracle to the language $B$, we can use it to solve $A$. The word "solve" here should be in the context of a specific complexity/computability class.

Turing reductions are weaker than many-to-one reductions. The latter can be viewed as Turing reductions where we are only allowed to call the oracle once - at the very end of the run.

polynomial time many-to-one reductions - simply adding a constraint that the reduction $f$ is computable in polynomial time.

polynomial time Turing reduction (= Cook reduction) - add the constraint that the oracle machine runs in polynomial time, counting each oracle call as $O(1)$.


Background first, too: I am currently third-years student in Information and Computer Science at a Chinese university.

I think most of your problems can be solved by common algorithms. For example, Sudoku game, can be solved by searching, or DLX(Dancing links and X algorithm) if you wanna improve the performance.

I think you can do some exercises to improve your basic skills. Some online judge services are suggested, such as Codeforces, SPOJ, poj.org, etc. There's an interesting game on a contest few days before. codeforces->contest->346->problem->A

Some of AI algorithms are based on searching. To improve the performance, we have some optimizing skills such like evaluation function(e.g. A* algorithm) or randomization(e.g. GA or Simulated annealing). Another part is base on learning, responses of a quest are according to large amount of data(e.g. ANN, and some algorithms for classifying).

Huge amount of code cannot be avoided. And some Lisp symbolic programming languages are good at such things. You can learn it if you're interested.

So just enjoy playing with what you make!


Does FOL extended with least-fixed points satisfy the Compactness Theorem?

No, it does not satisfy compactness anymore.
Least fixed point operators can let us define, for example, the standard part of a model of $\mathsf{PA}$. The standard part of a model $\mathfrak{A}=(A;+^\mathfrak{A},\times^\mathfrak{A},0^\mathfrak{A},1^\mathfrak{A})$ of $\mathsf{PA}$ is just the smallest subset of $A$ containing $0^\mathfrak{A}$ and closed under $n\mapsto n+^\mathfrak{A}1^\mathfrak{A}$. But this is exactly a least fixed point definition: the standard part of $\mathfrak{A}$ is the least fixed point of the operator $$\Phi(P): x=0\vee\exists y(P(y)\wedge y+1=x).$$
This in turn lets us pin down the standard model of $\mathsf{PA}$ up to isomorphism by the theory $\mathsf{PA}$ + "Every element is standard." But this contradicts compactness: no compact logic can ever pin down an infinite structure up to isomorphism (this is really just the observation that the upwards Lowenheim-Skolem theorem is just a compactness corollary).


Effect of Copy-On-Write on 2 processes sharing address space

The fork primitive makes a copy of the process. From within the processes, the parent and the child are almost identical; the few differences are the return value of the fork primitive and a few characteristics such as the process ID.

Copy-on-write is an implementation optimization. It isn't visible from inside the process. You'd need to look inside the kernel to see it, or use some reporting tools that expose this information. For example, you can observe it indirectly through memory usage statistics.

What you're printing out are the virtual addresses of the variables. They're the same: that's the whole point of fork — it creates a (near-)identical copy of the process.

Under the hood, when the child modifies the value of a, the kernel makes a copy of the page that contains it. Before that point, the variable a in the parent process and in the child process are stored in the same memory. After that point, they are stored in different memory: the parent and the child now each have their own page. But the two processes map their respective pages at the same address — the address of a variable doesn't change (it can't change, because that's how the code locates the variable).


Deriving the exact number of execution times

Hint: Summation. Also note you can optionally reorder the (non-dependent) loops.

Spoiler (mouse over):

   So what you normally do: the inside of a nested loop will run the $\text{number of loops of the outer loop} \times \text{the number of loops of the inner loop}$. It can also be done with repeated addition of the number of loops of the inner loop (after all multiplication can be done with repeated addition). In this case, one of the inner loops is dependent on the outer loop, so you can't just multiply them. You must add it more "manually". If you do this, you will see something like this: $ 1 + 2 + 3 ... n $, this can be done with summation, which in this case $\sum_{i=1}^n i = \frac {n\cdot\left(n+1\right)} {2}$. And multiplying the additional $\#n$-loop loop (you can reorder $k$-loop to the outside to make this simpler, after that you can calculate the two inner-loops, $i$ and $j$) , you get $n\cdot\frac {n\cdot\left(n+1\right)} {2} =\frac {n^2\cdot\left(n+1\right)}{2}$.

 So step by step:

 1. First let's decide the two outer loops: the outer loop, $i$ will run $n$ times.

 2. The $j$ loop will run $1...i$ each time. The first time it will run $1$ time, then $2$ times, then $3$ ... finally $n$ times, totaling $1 + 2 + 3 + ... + n$ times. That means the $j$ loop will run a total of $\frac{n\cdot\left(n+1\right)}{2}$ times, after calculating the summation (see linked wikipedia page on summation).

 3. For each time the $j$ loop runs, the $k$ loop will run $n$ times, thus we simply multiply the summation result by $n$ for $\frac{n^2\cdot\left(n+1\right)}{2}$.


If $F$ is valid then $F \cup \{res(C_1,C_2,A_i)\}$ is valid

Since you are only asking for a hint:

You have to prove that, for any interpretation I, if it satisfies all
the clauses in $F$, then it also satisfies the resolvant
$res(C_1,C_2,A_i)$, and hence it satisfies all the clauses in $F'$.

From that you can infer the result to be proved, with some universal quantification.

Note on terminology and notations:

I would rather say that, when $F$ is valid, every interpretation
satisfies it. It is $F$ that is to be satisfied, not the interpretation. Or more generally, it may also be a clause $C$, a literal $A_i$, or a set of clauses $F$ that may (have to) be satisfied.
$F$ is valid iff for any interpretation $I$, $I(F)=1$.
You should not say "for any interpretation $I(F)$", since as you noted yourself, $I(F)$ is a truth value. An interpretation in propositional logic is (usually) an assignment of truth values to the symbols used in the clauses, i.e. a mapping of the set of symbols to the set of truth values. It also implies interpreting logical connectives in the usual way, and sets of clauses as a conjunction of the clauses. Then, truth tables allow you to associate truth values to each construct, up to the whole set of clauses, which is what is meant by $I(F)$. The interpretation is $I$. while $I(F)$ is the truth value it gives to the set $F$ of clauses.

Interpretation may be defined in a more general way, but the above should be enough here.


Arbitrary precision integer square root algorithm?

One of the problems with Newton's method is that it requires a division operation in each iteration, which is the slowest basic integer operation.

Newton's method for the reciprocal square root, however, doesn't. If $x$ is the number for which you want to find $\frac{1}{\sqrt x}$, iterate:

$$r_{i+1} = \frac{1}{2} r_i (3 - x r_i^2)$$

This is often expressed as:

$$w_i = r_i^2$$
$$d_i = 1 - w_i x$$
$$r_{i+1} = r_i + \frac{r_i d_i}{2}$$

That's three multiplication operations. The division by two can be implemented as a shift-right.

Now the problem is that $r$ is not an integer. However, you can manipulate it as such by implementing floating-point manually, and doing a bunch of shift operations to compensate when appropriate.

First, let's rescale $x$:

$$x' = 2^{-2e} x$$

where we would like $x'$ to be greater than, but close to, $1$. If we run the above algorithm on $x'$ instead of $x$, we find $r = \frac{1}{\sqrt x'}$. Then, $\sqrt{x} = 2^e r x'$.

Now let's split $r$ into a mantissa and exponent:

$$r_i = 2^{-e_i} r'_i$$

where $r'_i$ is an integer. Intuitively, $e_i$ represent the precision of the answer.

We know that Newton's method roughly doubles the number of accurate significant digits. So we can choose:

$$e_{i+1} = 2e_i$$

With a little manipulation, we find:

$$e_{i+1} = 2e_i$$
$$w_i = {r'_i}^2$$
$$x'_i = \frac{x}{2^{2e - e_{i+1}}}$$
$$d_i = 2^{e_{i+1}} - \frac{w_i' x'_i}{2^{e_{i+1}}}$$
$$r'_{i+1} = 2^{e_i} r'_i - \frac{r'_i d_i}{2^{e_i + 1}}$$

At every iteration:

$$\sqrt{x} \approx \frac{r'_i x}{2^{e + e_i}}$$

As an example, let's try calculating the square root of $x = 2^{63}$. We happen to know that the answer is $2^{31}\sqrt{2}$. The reciprocal square root is $\frac{1}{\sqrt{2}} 2^{-31}$, so we'll set $e = 31$ (this is the scale of the problem) and for our initial guess we'll pick $r'_0 = 3$ and $e_0 = 2$. (That is, we pick $\frac{3}{4}$ for our initial estimate to $\frac{1}{\sqrt{2}}$.)

Then:

$$e_1 = 4, r'_1 = 11$$
$$e_2 = 8, r'_2 = 180$$
$$e_3 = 16, r'_3 = 46338$$
$$e_4 = 32, r'_4 = 3037000481$$

We can work out when to stop iterating by comparing $e_i$ to $e$; if I've calculated correctly, $e_i > 2e$ should be good enough. We'll stop here, though, and find:

$$\sqrt{2^{63}} \approx \frac{3037000481 \times 2^{63}}{2^{31+32}} = 3037000481$$

The correct integer square root is $3037000499$, so we're pretty close. We could do another iteration, or do an optimised final iteration which doesn't double $e_i$. The details are left as an exercise.

To analyse the complexity of this method, note that multiplying two $b$-bit integers takes $O(b \log b)$ operations. However, we have arranged things so that $r'_i < 2^{e_i}$. So the multiplication to calculate $w_i$ multiplies two $e_i$-bit numbers to produce a $e_{i+1}$-bit number, and the other two multiplications multiply two $e_{i+1}$-bit numbers to produce a $2e_{i+1}$-bit number.

In each case, the number of operations per iteration is $O(e_i \log e_i)$, and there are $O(\log e)$ iterations required. The final multiplication is on the order of $O(2e \log 2e)$ operations. So the overall complexity is $O(e \log^2 e)$ operations, which is sub-quadratic in the number of bits in $x$. That ticks all the boxes.

However, this analysis hides an important principle which everyone working with large integers should keep in mind: because multiplication is superlinear in the number of bits, any multiplication operations should only be performed on integers which have the roughly the magnitude of the current precision (and, I might add, you should try to multiply numbers together which have a similar order of magnitude). Using integers larger than that is a waste of effort. Constant factors matter, and for large integers, they matter a lot.

As a final observation, two of the multiplications are of the form $\frac{ab}{2^c}$. Clearly it's wasteful to compute the all the bits of $ab$ only to throw $c$ of them away with a right-shift. Implementing a smart multiplication method which takes this into account is also left as an exercise.


Finding a maximal set of nonintersecting line segments in a unit circle

For intervals we have got a similar problem.

In the case of interval two intervals $(x_i,y_i)$ and $(x_j,y_j)$ are intersecting if $x_i  \leq y_i \leq x_j \leq y_j $ or $x_j \leq y_j \leq x_i \leq y_i$ is not true.
The problem for intervals is discussed in Maximum non-overlapping intervals in a interval tree.

In your case however lines are intersecting only if you have $x_i \leq x_j \leq y_i \leq y_j \leq x_i$ in circular order. Here $x_i$ and $y_i$ are the circumference distance from a fixed point say the top point.

As suggested in the solution  for intervals you can either apply dynamic programming or the greedy algorithm.


Macros vs lazy evaluation in scheme inspired language

If lazy only gives you the option of either evaluating or ignoring each argument, then you can't implement macros like cond with it, since neither ignoring the predicate of a (pred expr) argument nor calling it as a function is the right thing to do. If lazy allows you to inspect the arguments in other ways then it essentially is a macro system.
If you want your language to support compilation then you'll have to put limits on where lazy can appear, or else pay a significant code size and efficiency penalty for every application of a function that can't be identified at compile time. If the language is purely interpreted then you don't really have that problem, but you still may want to think about the implications of allowing callers to inspect the implementation details of functions by passing lazys to them where they expect lambdas.


Optimal algorithm for finding the girth of a sparse graph?

See Optimal algorithm for finding the girth of a sparse graph from cstheory.SE which has an accepted answer.


Calculating the Transfer Time for a Hard Disk

Sectors are usually 512B to 4KB. In your case, it seems that the actual time it takes to read the sectors is negligible compared to seeking (verify this!), and this could be what is meant by the following line:

  Since a sector is very small, ignore the time to rotate it through under the head.

To be sure, make the calculation with respect to the largest sector size (4KB), and check that the data transfer time is negligible. If it isn't, you are indeed missing a data point.


In "multi hop" network, is computer => computer 0 hop or 1 hop?

As stated on this site:

  A hop is a computer networking term that refers to the number of routers that a packet (a portion of data) passes through from its source to its destination. Sometimes a hop is counted when a packet passes through other hardware on a network, like switches, access points, and repeaters. This isn't always the case and it depends on what role those devices are playing on the network and how they're configured.

So as there are no routers showed between the two workstations, I'd say this is a point-to-point connection (layer 2 link with only two devices) with no hops in between.


Turing recognizable -decidable languages-

There are two directions here. One is trivial: if $C$ is indeed of the above form, then it is clearly recognizable: given $x$ just run $D$ on all possible $y$'s in a dovetailing manner (see, e.g., here, or search in this site).

The other direction is less obvious, but also not too difficult: Assume that $C$ is recognizable. Then, there exists a machine that halts and accepts any $x\in C$. Thus, you can write the sequence of configurations of $M$ on input $x$, and this sequence is finite! This sequence will be the $y$ that exists if $x$ is in the language. You should be able to complete the details from here.


Delete rows or columns of matrix containing invalid elements, such that a maximum number of valid elements is kept

Here is a solution based on back-tracking. You probably need to double check but it seemed ok on my side. Should take 1h on a 30x900 matrix, but you can use multi-threading in the bottom for loop to speed it up.
import numpy as np
from tqdm import tqdm

def hash_list(l1, l2):
    return str(sorted(l1)) + str(sorted(l2))  # could be faster

def max_matrix(a):
    # the process:
    # we construct list of rows and columns to select, which keep only valid values (a[rows, columns] = 1 everywhere)
    # at each step, for each other row/column, if it can be added in a valid way, we carry on deeper
    # when it's not possible to extend anymore
    # we backtrack to where we were and try to add the next possible row/column.
    # we store in res the visited valid rows/columns, which prevents most redundant computations
    res = {}
    M, N = a.shape

    def make_grow(a, sel_columns, sel_rows, other_columns, other_rows, d='right'):
        assert len(sel_columns) + len(other_columns) == M
        assert len(sel_rows) + len(other_rows) == N
        h = hash_list(sel_columns, sel_rows) + d
        if h in res: # we went through this already
            return

        # attempting to add a column
        if d == 'right':
            for i in other_columns:
                if 0 not in a[i, sel_rows]:
                    # we can append it: let's try to go left or right from there
                    other_columns.remove(i)
                    sel_columns.append(i)
                    make_grow(a, sel_columns, sel_rows, other_columns, other_rows, d='left')
                    make_grow(a, sel_columns, sel_rows, other_columns, other_rows, d='right')

        # attempting to add a row
        else:
            for j in other_rows:
                if 0 not in a[sel_columns, j]:
                    # we can append it: let's try to go left or right from there
                    other_rows.remove(j)
                    sel_rows.append(j)
                    make_grow(a, sel_columns, sel_rows, other_columns, other_rows, d='right')
                    make_grow(a, sel_columns, sel_rows, other_columns, other_rows, d='left')

        # this position has been visited.
        res[h] = (sel_columns, sel_rows)

    # now launching from all possible first positions.
    for i in tqdm(range(M)):
        for j in range(N):
            if a[i, j] == 1:
                make_grow(a, [i], [j], [elt for elt in range(M) if elt != i], [elt for elt in range(N) if elt != j], d='right')
                make_grow(a, [i], [j], [elt for elt in range(M) if elt != i], [elt for elt in range(N) if elt != j], d='left')

    return res

if __name__ == '__main__':
    a = np.random.uniform(size=(30, 900))
    a[a > 0.3] = 1
    a[a <= 0.3] = 0
    a = a.astype(np.uint8)
    print(a)
    res = max_matrix(a)

    # just looking through the results to see the best configuration. (all valid configurations are stored btw)
    res_max = 0
    l1_max, l2_max = [], []

    for _, (l1, l2) in res.items():
        if len(l1) * len(l2) > res_max:
            res_max = len(l1) * len(l2)
            l1_max = l1
            l2_max = l2
    print(res_max, l1_max, l2_max)


What is the name of this prime number algorithm?

O'Neil [1] call this the "unfaithful sieve". It's much slower than the sieve of Eratosthenes.

For each prime $p$ you do work $\sim p/\log p$ and so the total number of divisions up to $x$ is roughly $x^2/(2\log^2 x)$ if you assume composites are free. (That's essentially true: they take at most $2\sqrt x/\log x$ divisions each for a total of at most $2x^{3/2}/\log x$ divisions.)

Divisions take longer than unit time, so the total bit complexity is about $O(x^2\log\log x/\log x)$.

[1] Melissa E. O’Neill, The Genuine Sieve of Eratosthenes


Why are syntax trees used in genetic programming?

In short: AST representations of programs are more easily analyzed,
manipulated, and transformed, while preserving and enforcing the existence of a
formally defined program meaning through the transformations.

I am asssuming that the reader knows already what is an abstract syntax tree (AST), and does not need to be shown examples.

The question is an issue about abstract objects (semantics) and their
representations (syntax). We are usually interested in the semantics,
applying transformations to entities to change or combine their
meanings, their semantics, which can belong to all kinds of domains.
But semantics is elusive, mathematical abstraction, and all we can
actually manipulate to express our intent is syntax representations.

That is the basis of all programming, but is also to be found in
logic, proofs, and finally all of mathematics. That is what makes the
choice of representations and notations often so important. Good choice
of representation will lead to easier, possibly more perspicuous or
intuitive understanding of the problem and be better adapted at
expressing answers, and proofs, for given questions.

The point is well known to programmers, as they are taught that it is essential to
choose the right data structure in order to implement an algorithmic
solution to a given problem. The choice of data structure is the choice of
representation.  And I just made a similar answer to a question on
constructing (programming?) Turing Machines.

Note that there is a partially ambiguous use of the word syntax, which
can be any concrete representation of an abstraction, or can be
intended to mean only textual representation as strings (we are
getting close to Turing machines), possibly structured by some logical
system (a context-free (CF) grammar for example that specifies what
are the legitimate strings, the well-formed-strings.

In fact, the existing parsing-unparsing technology, especially for CF
grammars, makes it generally easy to switch between textual and an
associated tree representation, to the point that they are often not
distinguished much. Actually, mathematicians have been using tree
representation (formally defined as Algebras), long before that
technology existed, and this is what lead to using the representation of AST
in manipulating programs.

So what was so convenient about these tree (or AST) representations?

The key points are:

it is very convenient for associating precisely
semantic meaning to syntactic constructs, in a compositional way, by means of a simple
mathematical concept: the homomorphism;
it provides and enforces a syntactic type system (statement, expression, ...) that preserve the existence of some meaning when the program representation is transformed in a way that preserves the syntactic typing constraints;
it is easily manipulated to actually perform analysis and transformations;
it is easy to decorate it with localized information to help or guide these analyses and transformations.

First, if you take a string representation of a program, without
further structural information, there is no simple way to delimit
substrings that have naturally a meaning of their own (I am saying
naturally, because some people may always try to play at abstracting
syntactic context or indulge in syntactic (text oriented) continuation games - ignore this if
you do not get it).

The idea of a tree structure, with nodes labeled with operators, possibly
restricted by syntactic types (statement, expression, variable, ...)
is that they naturally decompose the syntactic structure into subparts
(the subtrees) that can have fairly naturally, and perspicuously with
respect to computational concepts, a semantic meaning of their own.

Then, if we associate a semantic function to each operator, we can get
the meaning of a tree representation by applying the semantic function
of the root operators to the semantic meaning of each of its subtrees.
If we also provide some semantics to leafs operators (which may be
defined as a mapping from syntactic representations to some semantic
domains possibly by other means, for example associating the integer
23 to the string "23"), we know how to define simply the semantics
of any well-formed tree, whether complete program or well-formed
program fragment. This is the basis of what is known as denotational semantics.

In other word, the homomorphism thus defined gives a rather simple and
tractable way to associate meaning to well-formed program fragments, by composing the meanings of its well-formed sub-fragments (this is known as semantic compositionality).
Then, it becomes much easier to attempt defining semantically
meaningful transformations. And semantics, what the program (fragment)
does is what we really care about.

Furthemore, AST are fairly easy to manipulate by programs to express these transformations that somewhat respect the semantic structure (as they manipulate subtrees that are semantically meaningful), which initially justified their use in program editors, program manipulation systems, and programming environment.

Actually, the concept of AST in programming appeared with the language
Lisp (and its ability to manipulate Lisp programs syntactically) in
the very late fifties. But it developed mostly in the seventies (Emily, Cornell synthesizer, Mentor/Centaur), and further in the eighties, at the
same time as denotational semantics (which is based on the above
approach), and most likely under the influence of denotational
semantics. The early work (LCF) on automated proofs about computation may also have been influencial.

From the point of view of genetic programming, the use of AST both facilitates and enforces the
creation of syntactic structures that are more likely to have some
meaning. Manipulating unstructured string representations  would be
likely to result in being swamped with string representations to which
no meaning can be associated.

Another advantage of AST representations is that they are fairly easy
to decorate with additional information: precomputed semantic
properties, weights, or whatever is deemed useful for the intended
program transformation or manipulation, including genetically programed transformations.

A detailed example

This section has been added later to answer some comments.

I will try to work out one example in some details to explain the
relation between manipulations on the AST and their semantics
conterpart.

We take a very simple example of crossover between two ASTs:
T1=foo(exp1,exp2) and T2=bar(exp3, exp4). I keep it small for
readability. Actually, exp1 to exp4 are meant to be subtrees of
some AST, while you may also see what is around them as standing for
the rest of some AST (or some AST subtree) that is the context in
which they occur.

We suppose first that the language does not have typing (in the usual
sense of programing languages), and accept any value in any context
expecting a value, so that any expression can legitimately replace any
other.

Then given T1 and T2, it is legitimate to apply a crossover that swaps
exp1 and exp4, thus producing T1'=foo(exp4,exp2) and
T2'=bar(exp3, exp1). Note that the algorithm could also consider
only one of these two trees (I am incompetent regarding genetic
splicing strategies).

Now, let us see what can be said about semantics, without getting too
much into details.

Let $S$ be the semantic function, $V$ the domain of values, $M$ the
domain of environments that map identifiers to values. The semantics
$S$(exp) of an expression exp is a function $e: M\to V$ that takes
an environment $m$ as argument (so that we have values for
identifiers) and returns the value of the expression in that
environment.

Now, if the operators foo and bar are supposed to compute
respectively two functions $f$ and $b$ on their arguments,
the semantics of T1, for example, will be defined as

$S$(foo(exp1,exp2))=$S$(foo)($S$(exp1),$S$(exp2))=$\lambda m.f(e_1(m),e_2(m))$

You notice that the semantic function is not necessarily easy to define in the
complex case of a programming language, since for foo we have here
$S$(foo)=$\lambda e, e', m\,.\, f(e(m), e'(m))$.

This complexity results from the choice of the Abstract Syntax, that
considers here foo and bar as AST operator nodes. Instead, the AST
could have a call operator that has several daughters, for example
as in call(foo, exp1, exp2). Then the complexity of dealing with the
environment $m$ would be factorized in the semantics of call, while
the semantics of foo would simply be the function $f$.

Sorry for this complexity.

The whole point is that we can define the semantics of an AST subtree
such as exp1 independently of any context, but as a
function $e_1$. Whatever information it needs from the context to be
evaluated is summarized in the arguments (here the environment $m$)
that are passed to its semantics. And this information is in turn
passed to the semantic functions associated to subexpressions.

So now we know that a subtree of AST can have a well defined
semantics, independently of its context.

But what about the context? Does it have a well defined semantics when
a subtree is missing. The nice point is that it does.

If you consider the context foo(??,exp2), what can its semantics be.
The natural answer is that it is whatever semantics it would have if
you provided the missing part. In other words, it is a functional
semantics that takes as argument the semantics of the missing part.
This is very similar to the semantics of the complete expression
$S$(foo(exp1,exp2)) that we defined above, except that the missing
exp1 must be accounted for with an argument $e$ standing for the
semantics of whatever expression could replace exp1.

We had $S$(foo(exp1,exp2))=$\lambda m.f(e_1(m),e_2(m))$

So, without going into further details, you have

$S$(foo(??,exp2))=$\lambda e.\lambda m.f(e(m),e_2(m))$

Then, given that $S$(exp1)=$e_1: M\to V$,
we have
$S$(foo(exp1,exp2))= $S$(foo(??,exp2))($S$(exp1))

which is precisely what we would like: syntactic abstraction directly
translate into semantic abstraction.

Then we also have, of course:

$S$(foo(exp4,exp2))= $S$(foo(??,exp2))($S$(exp4))

In other words, both AST subtrees and AST contexts (of subtree) have
well defined semantics, that do not change, and they compose to give
the semantics of the whole AST tree when a subtree is placed in a
permitted context.

But of course: $S$(foo(exp1,exp2)) $\neq$ $S$(foo(exp4,exp2))

I hope this explains how things work. Using well-formed AST will
ensure that you are actually manipulating semantic fragments that
compose meaningfully.

Actually, things may be a bit more complicated, because you want to
include in the process what is usually called static semantics,
i.e. constraints on the AST that are usually checked at compile time.
The best known examples are type constraints for statically typed
languages, or declaration of identifiers when that is required.  Thus
you may want to decorate ASTs with this statically computable
information, and use splicing techniques that will incrementally
preserve the information and check the required constraints on the AST, so that you produce only programs that at least compile.

Then as a last comment, I would like to remarks that linear genetic
programming seems to be doing pretty much the same, but restricts
splicing to sequences of statements, so that there is always some
executable semantics preserved. But I am not specialist of that.


Why are the two random variables independent in the analysis of Randomized Selection algorithm in CLRS?

The two random variables $X_k$ and $T(\max(k-1, n-k))$ are independent because in each recursive call to RANDOMIZED-SELECT() we invoke RANDOMIZED-PARTITION(), a pivot is randomly selected, and the choice of the pivot in one recursive call is independent from the choice of the pivot in another recursive call. Remember that in the analysis we assume that the elements are distinct, so that each element in a particular subarray has the same probability of being selected as the pivot. Moreover, simply stated, the value of $\max(k-1,n-k)$ does not depend on $X_k$: it is the same independently of $X_k$ being equal to zero or one.


An algorithm to find the area of intersection between a convex polygon and a 3D polyhedron?

You have a 2D convex polygon $G$, and a 3D polyhedron $H$.  Let $P_G$ denote the plane that the polygon is contained in.  The following should work:

Their intersection is a 2D polygon.  You can find the edges of the intersection as follows:

For each triangle of $H$:

If the triangle intersects $G$, output this intersection.

This procedure outputs the edges of a 2D polygon, and now you want to compute its area.  To do this, compute a triangulation of it (which apparently can be done in linear time), then sum up the area of the resulting triangles.

You can test whether a triangle intersects $G$ as follows: compute the intersection of the triangle with $P_G$; call the result $R$.  Typically, $R$ will be a point or line.  $R$ can be computed efficiently.  Then, compute the intersection of $R$ with $G$.  This is purely a 2D problem.  There are standard algorithms for solving this; see, e.g., https://en.wikipedia.org/wiki/Line_clipping or http://geomalgorithms.com/a13-_intersect-4.html.


Calculating probability of reaching state in DTMC

The answer to your question very much depends on the values of the probabilities $a_{ij}$. If all are non-zero, then the DTMC forms one single strongly connected component and the probability of reaching $x=3$ is therefore $1$ (it is $1$ for any state in such a case in fact). This result comes from the Long-run theorem, which says that any finite DTMC eventually reaches a bottom SCC and visits all its states infinitely often.

Have a look at the lecture slides and notes of a course on probabilistic systems. Especially the third and fourth lecture.

In a general case, you would find with a graph analysis states that reach $x=3$ with probability $1$ denoted $S_1$ and those with probability $0$ denoted $S_0$. Then you have a set of states $S_?$ for which you don't yet know the probability. For them you construct a matrix $\mathbf{A}$ of transition probabilities (it will be a square matrix of size $|S_?|\times |S_?|$). Then you construct a vector $\mathbf{b}$ with one-step probability to reach $x=3$. A solution to $\mathbf{A}\cdot \mathbf{x} = \mathbf{b}$ gives you the probabilities for states in $S_?$.


How much space an ascii character really takes on a 64 bit word addressable memory?

It depends.  A program can store 1 ASCII character in each 64-bit word, or 8 ASCII characters in each 64-bit word.  It's up to each individual program to decide how it wants to store and format its data in memory.  The latter would probably be more typical.


Some terminologies in Wirth's book and the satisfying of deterministic algorithm

The definition of start symbol that you quote has nothing to do with the definition of start symbol in the context of deterministic grammars. Here is a correct definition:

  A terminal $a$ is a start symbol of a sequential form $\alpha$ if $\alpha \Rightarrow^* aw$ for some $w \in \Sigma^*$.

In words, $a$ is a start symbol of $\alpha$ if $\alpha$ generates some word starting in $a$.

In your example, $Aa$ generates the word $ba$, and so it shares a start symbol with $b$.

Why is sharing a start symbol bad? Suppose you are trying to parse $A$, and are encountering $b$. Which production do you choose? $Aa$ or $b$? It is impossible to tell without looking ahead. The deterministic algorithm considered by Wirth has no lookahead, and so this situation is problematic for it.


Expression Problem – looking for a similar standard problem

I'm not sure that the problem is formulated quite as nicely, but the problem of implementing concurrency in an efficient manner has occupied at least as much effort as the expression problem, and prompted a number of solutions, including the use of semaphores and software transactional memory.

I'm certainly not an expert, but I believe the problem of concurrency can be formulated in a similar manner to the expression problem: create language constructs which allow us to simultaneously:

Have sufficient expressivity to create complex concurrent programs, say, a web server.
Be able to have a reasonable assurance that these complex programs will not incur deadlock.


Determine deadline for periodic task that enter ready queue in RTOS

You can't generate a deadline from nothing. That doesn't make sense.

Some tasks must be completed by a certain time, or they are useless.  Only the programmer who writes the task knows whether this is the case, and if so, knows when they have to be completed by.  That's not something that the OS can infer, because it depends on what the task is doing and why.

For instance, a task that adjust the jet engine's power level in response to pilot commands might need to respond rapidly to make sure that safety requirements are met.  However, a task that displays frames of a movie on the passenger's entertainment system is probably less critical; if the next frame of video doesn't get displayed or is delayed, there's no great harm done.  The OS cannot distinguish those two cases.  Only the software developer can.

Therefore, in a real-time OS that tries to meet task deadlines, the deadlines come from the software developer.

For periodic tasks, we might not have a fixed deadline, but we might have requirements on how often they run (e.g., must occur at least two times per second).


Is it possible to use a copy-on-write strategy to modify a B+ tree?

Yes it is. The trick is to use the size of file (where is the tree stored) as the means of calculating offset of the new root. In other words, when one modifies a leaf, most of the tree wont change and the blocks which do change get appended at the end, with root coming last.

More here: http://www.bzero.se/ldapd/btree.html


Why do we reject turing machines that use space less than the log of the length of the input?

Consider any program in high-level language that has a loop going over all items:

for i from 1 to n
    do something
end for

Implementing this loop takes $O(\log n)$ work space, since the variable $i$ takes $O(\log n)$ bits to store. If you're not allowed to use even that much memory, then you have to be very careful when implementing any non-trivial algorithm, if it is possible at all; for instance, any results will be highly dependent on the exact definition of the model of computation.

Arora and Barak don't want to focus on such issues, so they just assume that you are given at least logarithmic space.  There are enough interesting things to say without having to worry whether some general reduction can be carried out in sublogarithmic space.  (And if you want to study regular languages -- languages that can be recognized with constant space -- you don't need complexity theory.)


Turing machine for which it is impossible to decide if it halts?

A turing machine must exist for which it is not possible to decide if it ever halts or not.

This is an incorrect conclusion. For some ordering of $f$ and $t$, it could be that $f_n$ correctly solves all $t_i$ for $i < n$, i.e. every $t_m$ is solved by $f_{m+1}$. This would still not give a complete solution to the halting problem, as long as the function $n \mapsto f_n$ is not computable.


Turing-completeness, Conway's Game of Life and Logical Gates

A form of conditional repetition or conditional jump (while, for, if and goto)
A way to read and write to some storage mechanism

The computer you typed this message onto is Turing Complete (well, sort of), yet the only tool it uses is logic gates.  I can give you a simple(ish) example of each:

For the first requirement, processors can use multiplexers to create conditional jump options.  Multiplexers are basically just a bunch of AND gates.

Number 2 is a bit more complex.  Computer memory consists of logic gates that feed back into themselves.  If you study memory, you begin by studying latches and flip-flops.  Here is a simple latch that stores which of the two input lines on the left turned on most recently:

Thus, it stands to reason that, if you can imitate logical gates, you can create a Turing-Complete machine just as you would if you could simulate a Turing Machine.  So, it may be that you don't need to show how to simulate a TM in GoL nodes, but instead take a step to show that logical gates are sufficient to be Turing Complete.

I have one further thought for you that might make your life simpler.  You don't need every gate.  NAND and NOR are each sufficient, on their own, to create every other logic gate.  You can easily do a search like "nand logical completeness" to find the logic gate diagrams to show this.


Longest path in a directed acyclic graph with constraints

You can solve this problem in time $O(|V|+|E|)$ by using dynamic programming. Thirst you order nodes in topological order. Let $v_i$ be the $i$-th node in topological order. Let $E_i$ be the set of edges ending in $v_i$.

If $|E_i\setminus D'| = 0$ then:
$$
d[v_i][0] = 0
$$

otherwise:
$$
d[v_i][0] = 1 + \max_{(v_j, v_i) \in E_i}(d[v_j][0]_{(v_j, v_i) \not\in D'})\\
$$

If $|E_i| = 0$ then:
$$d[v_i][1] = -\infty$$
otherwise:
$$d[v_i][1] = 1 + \max_{(v_j, v_i) \in E_i}(d[v_j][0]_{(v_j, v_i) \in D'}, d[v_j][1]_{(v_j, v_i) \not\in D'})
$$

It's easy to see that $d[v_i][0]$ is equal to length of longest path ending in $v_i$ without edges from $D'$ and $d[v_i][1]$ is equal to length of longest path ending in $v_i$ with exactly one edge from from $D'$. After that you need to find largest of $d[v_i][1]$. You can also store the id of the node for which we found the maximal value during dynamic programming to recreate the path.


Can the isomorphic graph problem be solved in deterministic polynomial time?

Your approach sounds intuitively appealing on first glance, but it doesn't work.  It's not enough that each edge in $G$ has a matching edge in $H$, when taken one at a time.  There has to be a way to provide a single matching (isomorphism) that matches every edge of $G$ to a (different) edge of $H$, in a way that preserves the connectivity.

Examples:

Suppose you discover that it is possible to match edge $(a,b)$ from $G$ with edge $(u,v)$ from $H$; and you also discover that it is possible to match edge $(c,d)$ from $G$ with $(u,v)$ from $H$.  This doesn't mean there will necessarily be a way to stitch this into a complete isomorphism that describes how all vertices and edges are matched.  For instance, trying to simultaneously match both $(a,b)$ and $(c,d)$ to the same edge $(u,v)$ does not correspond to any legal graph isomorphism (different vertices have to map to different vertices, and different edges to different edges).
Suppose you discover that it is possible to match edge $(a,b)$ from $G$ with edge $(u,v)$ from $H$; and you also discover that it is possible to match edge $(b,c)$ from $G$ with $(w,x)$ from $H$, where $v \ne w$.  This doesn't mean there will necessarily be a way to stitch this into a complete isomorphism that describes how all vertices and edges are matched.  For instance, trying to simultaneously match $(a,b)$ to $(u,v)$ and $(b,c)$ to $(w,x)$ doesn't work, since you need $b$ to be consistently matched to the same vertex in both (e.g., either to $v$ both times, or to $w$ both times).

For these reasons, your approach will indeed run in polynomial time but will not compute the correct result: there will be some graphs $G,H$ where your algorithm outputs "isomorphic" but where the correct answer is "not isomorphic".

If we try to fix this problem, the naive approach is to try to find all ways to match the set of $n$ vertices in $G$ to a re-ordering of the set of vertices in $H$ (i.e., a matching that simultaneously describes what every vertex in $G$ corresponds to, in $H$).  However, there are $n!$ such candidates to try, and $n!$ is exponential in $n$, so this leads to an exponential-time algorithm.  It's a famous open problem whether the graph isomorphism problem is in P or not.  See https://en.wikipedia.org/wiki/Graph_isomorphism.


I feel there are multiple questions in your post. I will attempt to answer the first -
"...The clock period is set such that the other circuitry (NAND gate in my case) has the time to stabilize during the cycle. This is the contract. But how is it achieved?
Shown below is a transistor level circuit of the D flip-flop shown in the picture in your post.
If you replace your D-ff schematic with the above picture, you can see how the signal propagates from the D input to the Q output.
Your second question is
How can one implement this basic circuit to allow the logic to distinguish between signal and noise?
Logic does not distinguish signal from noise. Noise is a signal. It is an (usually) unwanted signal, but a signal all the same. It is the job of the designer to ensure that noise from various sources does not pollute the actual signal so much that it results in an incorrect reading at the Q output.
Circuits have some amount of noise immunity. Chips and cell libraries are designed such that the noise does not cross the specified noise immunity of the circuit.


Memory Hierarchy and storing data in caches

There's probably a typo there: it's not 16 bits but rather 16 bytes. Each 32 bit integer takes 4 bytes, so 16/4 = 4.


One candidate approach: for each color $c \in \{\text{green}, \text{blue}, \text{purple}\}$, try to define a distance heuristic $f_c(\cdot)$ that approximates the distance to the specific goal of getting all tiles to be the color $c$.  For instance, if $s$ is a state, then $f_\text{green}(s)$ should be an estimate of the distance to the all-green state.

Next, given these heuristics, define a distance heuristic

$$f(s) = \min(f_\text{green}(s), f_\text{blue}(s), f_\text{purple}(s)).$$

Then you could use $f$ as your distance heuristic with $A^*$.

I leave it up to you to see if you can find a suitable definition of $f_c(s)$.  One candidate would be the number of tiles in $s$ whose color is not $c$, but that's probably not going to work; you'll probably need something smarter.

If you're willing to use something other than the $A^*$ algorithm, there is an elegant solution to this problem using linear algebra.

Identify the colors red, green, blue, purple with the integers $0$, $1$, $2$, $3$, taken modulo 4 (so you are working in $\mathbb{Z}/4\mathbb{Z}$).  Now you can solve the problem using linear algebra.  In particular, the state $s$ is a $N^2$-vector over $\mathbb{Z}/4\mathbb{Z}$.  Clicking on a tile at position $i,j$ corresponds to updating the state from $s$ to $s+v_{i,j}$, where $v_{i,j}$ is a fixed $N^2$-vector over $\mathbb{Z}/4\mathbb{Z}$.  Thus, you can get from state $s$ to state $s'$ if and only if $s'-s$ is in the linear span of the $v_{i,j}$.  If it is in the span, then find coefficients $c_{i,j} \in \mathbb{Z}/4\mathbb{Z}$ such that

$$s' - s = \sum_{i,j} c_{i,j} v_{i,j},$$

and this will give you a solution method: for each $i,j$, click on tile $i,j$ exactly $c_{i,j}$ times (order is irrelevant).  You can use generalized Gaussian elimination to check whether $s'-s$ is in the span, and if so, to find the coefficients $c_{i,j}$.


Why are there $(2kn+1)^{kn}$ Turing Machines with $k$ symbols and $n$ states?

Perhaps they are counting the number of Turing machines with at most $n$ states. In any case, it's not a big difference. Usually one is only interested in an upper bound, and from that perspective there is no difference between the two expressions.


Prove that $L=\{x\mid K(x) \leq |x|-c\}$ is recognizable, where $x \in \{0,1\}^*$

The flaw in your argument is that Turing machines don't always halt. However, if a Turing machine does halt and prints $x$, then it gives you an upper bound on the Kolmogorov complexity.


Running Build-Heap Algorithm on given numbers

It appears you're building a max-heap, where every element is greater than or equal to its child elements (if any). With that understanding, let's trace the action. First, the parent node of $A[j]$ will be $A[j/2]$ (integer division: discard any remainder) so we'll have
$$\begin{array}{r|cccccccc}
j & 1 & 2 & 3 & 4 & 5 & 6 & 7 & \dotsc\\
parent(j) & \_ & 1 & 1 & 2 & 2 & 3 & 3 & \dotsc
\end{array}$$
To keep things simple, we'll let the initial array be $[3,4,5,13]$:

Insert at $i=2$.

$A[parent(2)]=A[1]=3 < 4=A[2]$ so we swap $A[1]$ and $A[2]$, giving us the array
$$
[4,3,5,13]
$$

Insert at $i=3$.

$A[parent(3)]=A[1]=4 < 5=A[3]$ so we swap $A[1]$ and $A[3]$, giving us the array
$$
[5,3,4,13]
$$

Insert at $i=4$.

$A[parent(4)]=A[2]=3 < 13=A[4]$ so we swap $A[2]$ and $A[3]$, giving us the array
$$
[5,13,4,3]
$$
and now $j=parent(4)=2>1$ so we see if we need another swap.

$A[parent(2)]=A[1]=5 < 13=A[2]$ so we swap $A[1]$ and $A[2]$, giving us the array
$$
[13,5,4,3]
$$
and we're done, the array is now a max-heap.

The runtime of this algorithm is no worse than a multiple of $n\log n$ since none of the elements are further than $\log_2n$ from the root at $i=1$ so you'll need at most $\log n$ swaps for each of the $n$ elements. This, by the way, is not as good as possible: there's different algorithm that builds a heap in no more than a multiple of $n$ time.


Turing machine for $u<v$ with $u$ and $v$ positive binary numbers

So, firstly let's define the input tape.
Let's say it looks like "10101<00101" i.e. "number1< number2" and accepts only if the expression is true. Also, let the head in the start be on the most left meaningful character. The idea of the algorithm is just to scan two numbers from the left (assuming big-endian encoding for the numbers), if noticed that there is 0<1 accept immediately, if 0<0 or 1<1 then continue working, if 1<0 then reject.

So, TM sketch:

alphabet is $\{0,1,*,<\}$ with empty symbol $\epsilon$.

Record the most left bit of the first number
If it is 0 you change you state to something like num1_0 which means number 1 had the leftmost digit 0. Then you go to the right and look for the leftmost digit for the second number. If it is greater than do no accept else move the head to the left most and start from the beginning. Also, when compared two bits just change them to * , so you know where to compare next.

The tape progression looks like this:

101<111

*01<*11

**1<**1

***<***

accept.

Using this simulator I have come up with the following code:

name: Accepting when num1<num2
init: s0
accept: sfin

//main program
s0,0
s1_0,a,>

s0,1
s1_1,a,>

//uncomment this to allow equality
//s0,<
//sfin,<,-

//s1_b means we read the leftmost symbol and it was b
s1_0,0
s1_0,0,>

s1_0,1
s1_0,1,>

s1_0,<
p0,<,>

s1_1,0
s1_1,0,>

s1_1,1
s1_1,1,>

s1_1,<
p1,<,>

//pb means the symbol read from the left number was b and we are looking for the digit from the right number
p0,b
p0,b,>

p1,b
p1,b,>

//COMPARISON LOGIC HERE

//if 0<0 continue exploring
p0,0
goleft,b,<

//if 0<1 immedaitely report yes
p0,1
sfin,b,-

//if 1<1 continue exploring
p1,1
goleft,b,<

//goleft state simply tells to go until reached a to start over
goleft,b
goleft,b,<

goleft,0
goleft,0,<

goleft,1
goleft,1,<

goleft,<
goleft,<,<

goleft,a
s0,a,>

This accepts only when the input tape has the true expression number1< number2 like

  100100<100101

and it is limited to compare only the numbers of equal length (easy fix if needed to compare with different length, think about adding zeros to the first number until it matches the length of the second or reject if the length of the first number is greater).


Removing vertices that belong to a given set from a graph

Yes, this can be done on an adjacency list representation in $O(|V|+|E|)$ time.  Looping over all the edges can be done in $O(|V|+|E|)$ time.  As you look at an edge, you can check both endpoints; if either one is in $B$, you can delete it.  Afterwards, you can iterate through the vertices and remove the vertices in $B$ (their adjacency lists will be empty, so no need to do anything with their adjacency lists); this takes $O(|V|)$ time.  The entire process takes $O(|V|+|E|)$ time.


Third Normal Form and Boyce Code normal form

$S_1:$ If relation R is in 3NF and every key is simple, then R is in
BCNF.
$S_2:$ If relation R is in 3NF and R has only one key, then R is in BCNF

Both statements are correct.
Your counterexample is as follow:
$R(A,B,C,D)$ where fds that hold are $FD = \{AB \rightarrow CD, C\rightarrow B\}$.
Now, this example does not satisfy premice of any of the statement because there are two candidate keys i.e $\{AB\}, \{AC\}$.


When do we use parallel algorithms for enumerating combinations?

I have found one.
A parallel algorithm for finding small sets of genes that are enough to distinguish two biological states

But if you found others, I would like to know.


Use closure properties to transform languages to $L := \{ a^nb^n : n\in \mathbb N \}$

Regular languages are closed under intersection. This often allows to cut away all parts of a language that are not needed to show non-regularity. Complementation serves a similar purpose: if the original language is "complicated", the complement may be simpler so work with (in terms of other closure properties).

Hints:

   For $L_a$, the part right of $c$ is sufficient; try to intersect with a regular expression that gets rid of the clutter. Note that the part right of $c$ is close to $L$. Maybe another regular expression can help?
 For $L_b$, note that we get $n$ times $a$ and $b$ (in the last block), respectively, if we replace $\exists \dots i_j \neq j$ with $\forall \dots i_j=j$.

Complete solution for $L_a$:

   Let $L_a' := L_a \cap \mathcal{L}(ca^*b^*) = \{ ca^nb^n \mid n \in \mathbb{N} \}$. Then, with homomorphism $\phi : \{a,b,c\} \to \{a,b\}^*$ defined by

 $\qquad \displaystyle \phi(w) = \begin{cases} \varepsilon &, w = c \\ w &, \text{ else} \end{cases}$

 we have $\phi(L_a') = L$.

Complete solution for $L_b$:

   In order to get rid of the pesky $\exists$, we can complement. That introduces lots of words we do not want, i.e. such that don't have the $(ab^*)^*$ structure, so we can intersect with exactly that regular expression to get structure back:

 $\qquad \displaystyle L_b' := \overline{L_b} \cap \mathcal{L}((ab^*)^*) = \{ abab^2ab^3\dots ab^n \mid n \in \mathbb{N} \}$.

 Note that words in $L_b'$ contain exactly $n$ times the symbol $a$; if we can get rid of all blocks of $b$ but the last, we have $L$. This is possible by (nondeterministic) finite state transduction which $\mathsf{REG}$ is closed under. The transducer removes all $b$ until it decides on an $a$ that is was the last one. After that it emits the input and accepts if no further $a$ is encountered.

 Note that if we reverse $L_b'$, we can cut away the excess $b$ with a deterministic transducer and reverse again to obtain $L$.


Can there be a language not Context free but still PDA acceptable?

It is proven in your nearby language theory textbook (like Hopcroft, Motwani, Ullman "Introduction to automata theory, languages, and computation" (3rd edition, Pearson) that the languages accepted by (nondeterministic) PDAs are exactly the context free languages (generated by context free grammars).


Prove that the number of full nodes plus one is qual to the number of leaves in a nonempty binary tree

Well, an induction proof consists of a base case and an induction step. For trees that is usually structural induction, based on inductive ways trees are built.

The base case considers the smallest binary tree, which cannot be composed further. Show that one has the Property.

The induction step argues that the Property is true for any tree $T$ assuming the Property holds for its subtrees $T_{\textrm{left}}$ and $T_{\textrm{right}}$. That assumption is called the induction hypothesis.

There is another approach, induction based on the number of (full) nodes, called natural induction. Base case has a single full node. Induction step argues Property is true assuming Property holds for any tree having less full nodes.


Why are all polymorphic functions between functors natural transformations?

I think the easiest thing is to refer you to the famous Theorems for free! paper, which explains the intuition behind the use of the Reynolds parametricity theorem.

Intuitively, in System $\mathrm F$ a function $\alpha$ of type $\forall X. F\ X \rightarrow G\ X$, is so polymorphic, that $X$ can be instantiated by a morphism $f$ rather than just types. When one makes this precise, one sees that an arrow $F\ f\rightarrow G\ f$ can only be a commuting square, which exactly expresses the fact that $\alpha$ is a natural transformation.

The proof itself can be derived from Reynolds' classic result from Types, Abstraction and Parametric Polymorphism, which builds a model of System $\mathrm F$ where every type is interpreted by a relation over programs.


Turing machine that applies homomorphism on input string

I could really use some help conceptualizing this problem and how to think about Turing machines in general.

Turing Machines are formal logical models that can express computation. You can think of them as mechanical machines that perform read and write operations on one or more tapes containing symbols. These operations are not performed randomly but based on a table (called the transition function)
which is the true essence of the Turing Machine, without it the machine could not even move from the initial state.
This table specifies what the machine must do in each state, based on the 'settings' of the "machine world state", for example:

If the machine is in state $q_1$ and it reads a '$1$' on the input tape, then write a '$0$' on the working tape and move left on the same tape.
If the machine is in state $q_3$ and it reads a '$0$' on the input tape, then go to state $F$ (HALT).

These are some basic description of a TM, if you want to know them better (and I believe it is mandatory to master them if you want to continue with this discipline). Then you need to open a textbook and dig into these concepts.
Now going back to your problem, you might find it useful to throw down a high-level description of an algorithm (turing machine) that performs the required transformations on the input string; then you can proceed from here, after you have learned how to formally define a turing machine, and draw your model.

Possible algorithm:

start reading input tape
if input at position $i = 1$, then write a $1$ on the working tape at position $i$ and a $1$ at position $i+1$, then move right on the input tape.
if input at position $i = 0$, then write a $1$ on the working tape at position $i$ and a $0$ at position $i+1$, then move right on the input tape.

To this you need to add the implementation for adding '$01$' at the start of the string.


MST with half the edges the maximum weight

If the answer is "yes", then there is an easy algorithm: just compute any MST and report the number of edges with weight $C$.  If they all have the same number of edges with weight $C$, then the particular MST you compute won't change the answer.

So now you want to know whether the answer is yes.  To see that it is, observe that each MST is constructed by running the greedy algorithm on a specific linear extension of the partial order induced by the weights.  In your case, the edges $E$ partitioned into sets $E_{<C}$ and $E_C$, and every edge in $E_{<C}$ comes before any edge in $E_C$ for all of these linear extensions.  That tells you that every MST is made of a spanning forest $F$ on the subgraph induced by $E_{<C}$ and some edges from $E_C$; since all the choices for $F$ have the same size, we are done.


In computation, time consume depends deeply on the algorithm we choose. Since the search time consumes log2(N) and insertion  time consumes N/2, the insertion time increases sharply as compared to the search time. The only thing is that they depend on size of the symbol table, not the initial size because insertion and search time depend on the actual size of data set.

The chart below shows Percentage of Insertion Time over Search Time in your case.


Are you allowed to change the specifications of a problem when doing reductions?

It doesn't matter what B exactly is, it could be graph problem or something else. Nobody cares as long as you construct its instance in polynomial time and it has a solution precisely when the instance of A has. Maybe you need to use some structure of A to construct B, but maybe some parts of A don't need to be used at all, who knows.

So precisely what you must do is follow the definitions, and then everything is fair game with no authority setting any special rules.


This problem was basically made for dynamic programming (DP). Just review it and follow a couple of examples and solving this problem is straight-forward.

Your simple greedy approach does not always work. Consider:

[ begin ] [  2 ]
[ 3 ]     [ 10 ]
[ 1 ]     [ -1000 ]
[ 1 ]     [ end ]

The optimal solution would be to go right, down, left, down, down, right.


Algorithm that finds the number of simple paths from $s$ to $t$ in $G$

Your current implementation will compute the correct number of paths in a DAG. However, by not marking paths it will take exponential time. For example, in the illustration below, each stage of the DAG increases the total number of paths by a multiple of 3. This exponential growth can be handled with dynamic programming.

Computing the number of $s$-$t$ paths in a DAG is given by the recurrence,
$$\text{Paths}(u) = \begin{cases}
    1 & \text{if } u = t \\
    \sum_{(u,v) \in E} \text{Paths}(v) & \text{otherwise.}\\
\end{cases}$$

A simple modification of DFS will compute this given as

def dfs(u, t):
    if u == t:
        return 1
    else:
        if not u.npaths:
            # assume sum returns 0 if u has no children
            u.npaths = sum(dfs(c, t) for c in u.children)
        return u.npaths

It is not difficult to see that each edge is looked at only once, hence a runtime of $O(V + E)$.


Simulating continuous time semi-Markov state machine and changing transition probability on the fly

As it happens, recalculating the event time is exactly the right thing to do.  This follows from the fact that the exponential distribution is memoryless; or from the fact that exponential distribution is the time until the next event in a Poisson process.  I realize this might sound miraculous and unbelievable, so let me explain why, in detail.

Let's suppose that at time $t_0$ you have lambda equal to $\lambda_0$; then at time $t_1$, lambda changes to the value $\lambda_1$.  In other words, at every point in the time interval $[t_0,t_1)$, the value of lambda is $\lambda_0$; at every point in the time interval $[t_1,t_2)$, the value of lambda is $\lambda_1$.

You are simulating a Poisson process with parameter lambda.  During the time interval $[t_0,t_1)$, the Poisson process has parameter $\lambda_0$.  During time interval $[t_1,t_2)$, the Poisson process has parameter $\lambda_1$.  You want to simulate this process.  In particular, you want to simulate the time of the first event.

The brute-force way to simulate this process would be to divide time up into very small increments, say of length $\epsilon$, so that time is broken up into small intervals $[t_0,t_0+\epsilon)$, $[t_0+\epsilon,t_0+2\epsilon)$, $[t_0+2\epsilon,t_0+3\epsilon)$, ..., $[t_2-\epsilon,t_2)$.  In each interval, you have a value for lambda: its value is $\lambda_0$ for the first $(t_1-t_0)/\epsilon$ small intervals and $\lambda_1$ for the next $(t_2-t_1)/\epsilon$ small intervals.  In each small interval, you draw from a Poisson distribution with parameter $\lambda \epsilon$ (i.e., $\lambda_0 \epsilon$ or $\lambda_1 \epsilon$, depending upon whether the small interval falls before or after $t_1$).  Because $\lambda_i \epsilon$ will be a very small value, this is essentially equivalent to flipping a biased coin for each small interval; with probability $\lambda_i \epsilon$, you say that the event has happened in that small interval, and with probability $1-\lambda_i \epsilon$ nothing happens in that small interval.

Thus, this gives you a brute-force strategy to simulate your process.  This brute-force strategy will give you the right distribution of events.  However, it has the disadvantage that it is computationally expensive: it requires $(t_2-t_0)/\epsilon$ coin flips.

Fortunately, there is an equivalent way to do it that yields the same distribution of events, but is much more computationally efficient.  Here is the optimized strategy for how to simulate the time of the first event:

Randomly draw a value $d$ from the exponential distribution with parameter $\lambda_0$.  If $d<t_1-t_0$, then output that the first event happens at time $t_0+d$.
Otherwise (if $d \ge t_1-t_0$), randomly draw a value $d'$ from the exponential distribution with parameter $\lambda_1$ (independent of $d$).  Now, if $d'<t_2-t_1$, then output that the first event happens at time $t_1+d'$; otherwise, output that no event happens during $[t_0,t_2)$.

This optimized strategy lets you simulate the time of the first event.  (If you want to simulate the time of all events in the interval $[t_0,t_2)$, you can simulate the time of the first event, if any, and then iterate to figure out the time of the next event if there was a first event, repeating until done.)  It is efficient, as you can see.

Moreover, this optimized strategy gives the correct distribution.  It is  equivalent to the brute-force method described above: it gives the same distribution on the time of the first event (as $\epsilon \to 0$).  The equivalence follows from the fact that, if you have a Poisson process with parameter $\lambda$, then the time of the first event is exponentially distributed with parameter $\lambda$.  (See Wikipedia.)

Finally, you can note that my optimized strategy is exactly equivalent to recalculating whenever lambda changes.  It follows that recalculating whenever lambda changes does give you the right answer.  Amazing, huh?

Don't expect this to work for all distributions.  This is a special property of the exponential distribution.


Space complexity of string indices: O(1) or O(log|S|)?

These are correct (unless you explicitly specify a non-standard model of computing):

$O(1)$ space,
$O(1)$ words of space,
$O(\log|S|)$ bits of space.


Is converting an ambiguous grammar to an unambiguous grammar computable?

I assume that question is about derivation, otherwise the outcome does not change, but please read Yuval's comment for further details.

No it is not computable in the domain of your choice. There are inherently ambigous grammars, which are subset of context-free grammars. For the subset without inherently ambigous ones it is computable.

I like to point to thesis about ambiguous grammars, which is consistent with what I wrote, contains the same proof as TCS topic.

Since the problem of finding out whether grammar is inherently ambiguous is undecidable then you cannot build halting Turing Machine for such task. And yes, if you could built one it would be decidable.


A word in $L$ must either be of the form $b^i a^j$ with $i \neq j$ or it must have $ab$ as a substring.
Therefore you can write a context-free grammar $G$ for $L$ as the union of two context-free grammars $G_1$ and $G_2$ for $L_1 = \{b^i a^j \mid i \neq j\}$ and $L_2 = \{w \in \{a,b\}^* \mid ab \mbox{ is a substring of } w\}$.
It is easy to come up with a context-free grammar $G_2$. In fact, it is even easy to come up with a regular expression for $L_2$: $(a \mid b)^*ab(a \mid b)^*$. Therefore I will only focus building $G_1$.
A word in $w=b^ia^j \in L_1$ can be written as $w = b^k \alpha a^k$, where $k = \min \{i,j \}$ and $\alpha$ is a non-empty string containing only $a$s or only $b$s. Conversely, all words of the form $b^k \alpha a^k$ belong to $L_1$. Then, this is a valid grammar $G_1$:
$$
\begin{align*}
S &\to bSa \mid A \mid B \\
A & \to aA \mid a \\
B & \to bB \mid b
\end{align*}
$$


DFA complexity of reverse of language recognized by "maximal" DFA

Maximality implies that every state is reachable. Let $w_q$ by a word such that $q_0 \cdot w_q = q$.

Since $L$ is non-empty and its complement is also non-empty, there must be some accepting state $q_1$ and some non-accepting state $q_2$. For every subset $A \subseteq Q$, let $w_A$ be a word such that $q \cdot w_A = q_1$ for $q \in A$ and $q \cdot w_A = q_2$ for $q \notin A$.

I claim that if $A \neq B$ then $w_A^R$ and $w_B^R$ are not equivalent modulo $L^R$. Indeed, suppose (without loss of generality) that $q \in A \setminus B$. Then $w_A^R w_q^R \in L^R$ since $q_0 \cdot w_q w_A = q \cdot w_A = q_1$, whereas $w_B^R w_q^R \notin L^R$ since $q_0 \cdot w_q w_B = q \cdot w_B = q_2$. The result immediately follows.


Question about the difference between radix trees and patricia trees

Quoting Wikipedia:

  PATRICIA trees are radix trees with radix equals 2, which means that each bit of the key is compared individually and each node is a two-way (i.e., left versus right) branch.

According to Wikipedia, Patricia is just a "brand name" coined by Donald R. Morrison, standing for Practical Algorithm To Retrieve Information Coded In Alphanumeric.

Patricia trees thus accept their input in the form of binary strings. If the input is a word, then it is first encoded in binary.

As for the smile/smiled/smiles example, it is explained in the linked post – each of these words is encoded as a binary string, and this is what the Patricia tree sees. It is completely unaware of the semantic interpretation of the bitstring as an alphanumeric word.


General algorithm to find a minimal branching program

I'm assuming you mean branching programs in the sense of generalized binary decision diagrams (see here).

Now the question is whether by "length", you mean "size" or "depth". I will answer the "size" version here, as you will most likely mean that (and the depth version has some intricacies).

We can represent a smaller solution in space not larger than the input size. Furthermore, checking two branching programs to be equivalent is a problem contained in the complexity class co-NP.

Hence, we can define an algorithm in $\Sigma^P_2$ (see here) for finding if there exists a smaller equivalent branching program by letting it first guess a smaller solution, and then verify it to be correct using the co-NP equivalence checking oracle.

Note that this may not be an algorithm that is complexity-theoretically optimal. However, the existence of this algorithm answers your question with a "yes".


Problem with proving that $RP \subseteq NP$ : a non-deterministic TM for a language $L \in RP$

Fix some $L\subseteq RP$. Then:

if $x\in L$ then $P_y[T(x,y)\text{ accepts}]\ge {1\over2}$, therefore exists some $y$ where $T(x,y)$ accepts.
if $x\notin L$ then $P_y[T(x,y)\text{ accepts}]=0$, therefore for every $y$ we have $T(x,y)$ rejects.

Thus, by definition of $NP$, $L\in NP$.
As you can see from this proof, you are correct: $NP$ requires one path while $RP$ requires at least half of the paths


What is a real-world use-case/need for a left-recursive grammar?

There are probably better reasons than this, but one nice thing about left recursion is you get parse trees that naturally represent left associativity. You expect 5 + 3 + 2 to be evaluated as (5 + 3) + 2, but when parsed with the right recursive transformation you show, the parse tree would be the opposite.

This doesn't seem to matter until you start thinking about type coercion (Right word?). Consider 1u / 2u / 1.0f in C. (1 / 2) / 1.0 = 0 / 1.0 = 0.0 but 1 / (2 / 1.0) = 1 / 2.0 = 0.5.


Data structure or algorithm for quickly finding differences between strings

My solution is similar to j_random_hacker's but uses only a single hash set.

I would create a hash set of strings.
For each string in the input, add to the set $k$ strings.
In each of these strings replace one of the letters with a special character, not found in any of the strings.
While you add them, check that they are not already in the set. If they are then you have two strings that only differ by (at most) one character.

An example with strings 'abc', 'adc'

For abc we add '*bc', 'a*c' and 'ab*'

For adc we add '*dc', 'a*c' and 'ad*'

When we add 'a*c' the second time we notice it is already in the set, so we know that there are two strings that only differ by one letter.

The total running time of this algorithm is $O(n*k^2)$.
This is because we create $k$ new strings for all $n$ strings in the input. For each of those strings we need to calculate the hash, which typically takes $O(k)$ time.

Storing all the strings takes $O(n*k^2)$ space.

Further improvements

We can improve the algorithm further by not storing the modified strings directly but instead storing an object with a reference to the original string and the index of the character that is masked. This way we do not need to create all of the strings and we only need $O(n*k)$ space to store all of the objects.

You will need to implement a custom hash function for the objects. We can take the Java implementation as an example, see the java documentation. The java hashCode multiplies the unicode value of each character with $31^{k-i}$ (with $k$ the string length and $i$ the one-based index of the character. Note that each altered string only differs by one character from the original. We can easily compute the contribution of that character to the hash code. We can subtract that and add our masking character instead. This takes $O(1)$ to compute. This allows us to bring the total running time down to $O(n*k)$


Yes, you can match the eigenvalues.  It is easy to construct a matrix with any desired eigenvalues: for instance, create a diagonal matrix and put the desired values on the diagonal.  Thus, you can get an exact match, not just an approximate match.  Nothing fancy is needed.

No, matching the eigenvalues doesn't imply that the eigenvectors of $B$ are somehow related in any way to the eigenvectors of $A$.

Given a value $n$ you can easily construct a matrix $B$ whose spectral norm is $n$, so that too can be exactly matched.

You don't need the Johnson–Lindenstrauss lemma for these results.


This is a cascade classifier. Of course you can do that, but the main disadvantage (that you have to keep in mind) is that your error propagates along your cascade classifiers. So even if you have a very good classifier somewhere towards the end of your cascade, if you feed it with weak features (i.e., the output of the previous layer which was not so good) you should not expect to get a reasonable answer. There is generally another common problem with this method and that's the well-known overfitting effect. However, since you are using different subsets of data to train each classifier it shouldn't be a problem in your case I guess.


What's an efficient algorithm to calculate line breaks (word wrap) for balanced widths (minimum raggedness)?

Have you considered using the total-fit line breaking algorithm(a) used by TeX(b) and developed by Donald Knuth and Michael Plass?

Donald Knuth and Michael Plass. "Breaking Paragraphs into Lines".

https://github.com/jaroslov/knuth-plass-thoughts/blob/master/plass.md
https://github.com/baskerville/paragraph-breaker
https://cs.uwaterloo.ca/~dberry/ATEP/StudentLectures/Ananya.pdf
https://news.ycombinator.com/item?id=1134342
https://www.tug.org/TUGboat/tb21-3/tb68fine.pdf

Remco Bouckaert. "A Probabilistic Line Breaking Algorithm".

Edit:

The total-fit line breaking algorithm has already been implemented in many languages, including Java:

"Knuth & Plass line-breaking Revisited" in Java
"The linebreaking algorithm of Knuth and Plass" in Java (via Generalized Knuth-Plass Linebreaking Algorithm)
"rosettacode: Word wrap" has implementations of the Knuth Plass algorithm in a variety of languages


Generate numeric or string ID for a sequence of elements

If you don't care about the length of the id, sort the list and use that as the id.

If you do care about its length, sort the list and then use the SHA256 hash of the sorted list as the id.  It is believed to be infeasible to find collisions for SHA256, so you shouldn't have to worry about collisions.  If you find one, publish it and you'll be famous (briefly).


What is the intuition behind a Free-Choice Petri Net?

The literature on Petri nets has many papers that really aim to teach the concepts used.

In the case of free-choice Petri net, such an introduction can be found in the paper Structure Theory of Petri Nets: the Free Choice Hiatus by Eike Best, in the ACPN (Advanced Course on Petri Nets) 1986. (An online copy is here.)

If anywhere, the intuition behind free-choice nets should be explained there, but that doesn't really happen, and I haven't seen such an explanation elsewhere, either.

As far as there is an intuition behind free-choice nets, it is expressed by their name: whenever there is a choice, say, between step B or step C (that is to say: we have a place A with an arc to transition B and an arc to transition C), then that choice is free, that is to say, neither B or C are subject to any other additional conditions (that is to say, they cannot have additional input places).

Rather than focusing on intuition, the paper describes free-choice nets as follows, and I think this is the standard way to explain them:

One of the reasons Petri nets interest us is that they offer descriptions of concurrent system behaviour that can be statically analyzed. We can prove certain properties of the behaviour of Petri nets.
However, for unrestricted Petri nets, certain important properties are extremely hard to analyze; for instance, the question whether the net is live, or whether a given marking can be reached. So it is interesting to study restricted forms of Petri nets for which such analysis is easier.
One possible restriction is to say: no place may have more than one input transition, or more than one output transition. This type of Petri net is called an S-net. This eliminates parallelism and basically turns the net into a state machine. For instance, we can no longer write down a process in which the first thing to happen is A, then B and C in whatever order, and, finally, D. We can't put B and C in parallel.
Another restriction is the reverse: no transition may have more than one input place or more than one output place. This type of Petri net is called a T-net or marked graph. Now, we do have parallelism, but we no longer have choice. For instance, we can no longer write down a process in which the first thing to happen is A, then either B or C, and, finally, D. We can't have a choice between B and C.
Both restrictions are very severe, so it's interesting to look at compromises. Free-choice nets are just that: to quote Wikipedia, they are the nets in which every arc from a place to a transition is either the only arc from that place or the only arc to that transition. I.e. there can be both concurrency (parallelism) and conflict (choice), but not at the same time. So this is a proper generalization of S-nets and T-nets.
Certain properties of the behaviour of Petri nets that are hard or impossible to decide for arbitrary Petri nets become doable for free-choice Petri nets.

So the prime motivation for free-choice nets is not any particular intuition, but the fact that they allow certain forms of static analysis of behaviour.


Explanation of a simple algorithm's Big O complexity

The inner loop is $O(\sqrt{i})$, you are correct. Since $i\leq n$, then $\sqrt{i}\leq \sqrt{n}$, and we have
$n\times\sqrt{i}\leq n\times\sqrt{n}$. Hence the complexity is  $O(n\sqrt{n})$.


Does the empty language have a CFG in CNF?

Note that every context-free language has a grammar in CNF (that is proven) and $\emptyset$ is context-free, so the answer is clearly: yes!

Do you get from $S \to S$ to it, using the normal transformation algorithm? No, because the usual algorithm requires a reduced, chain-rule free grammar as input; yours does not fit.

Approach one: use the algorithms (from lecture or textbook) to remove the chain rule, and try again!

Approach two: start with another grammar that fulfills the criteria!

   Approach two is doomed to fail for most grammars: in order for a grammar to derive not a single word, it can not have any rules that are not thrown out by reducing.

 Thus, the only (kind of grammar) that works is $(\{S\}, \Sigma, \emptyset, S)$, that is a grammar with no rules at all. Note that it is in CNF.


Why does Prim's algorithm keep track of a node's parent?

Keeping the parent of each vertex is not a requirement to get the minimum spanning tree. For example, the algorithm as described on Wikipedia does not do this.

However, it's worth noting that there is more than one representation of an MST. In certain applications, it might be useful to quickly find the parent of a particular vertex.


From the comment above:

Before processing the stream, allocate $\lceil \log_2 n \rceil$ bits, in which you write $x:= \bigoplus_{i=1}^n \mathrm{bin}(i)$ ($\mathrm{bin}(i)$ is the binary representation of $i$ and $\oplus$ is pointwise exclusive-or). Naively, this takes $\mathcal{O}(n)$ time.

Upon processing the stream, whenever one reads a number $j$, compute $x := x \oplus \mathrm{bin}(j)$. Let $k$ be the single number from $\{ 1, ... n\}$ that is not included in the stream. After having read the whole stream, we have
$$ x = \left(\bigoplus_{i=1}^n \mathrm{bin}(i)\right) \oplus \left(\bigoplus_{i \neq k } \mathrm{bin}(i)\right)
= \mathrm{bin}(k) \oplus \bigoplus_{i \neq k } (\mathrm{bin}(i) \oplus \mathrm{bin}(i)) = \mathrm{bin}(k), $$
yielding the desired result.

Hence, we used $\mathcal{O}(\log n)$ space, and have an overall runtime of $\mathcal{O}(n)$.


Is the difference between two regular expressions a new regular expression?

Regular languages are closed under relative complement. Since regular expressions encode exactly the regular languages, you can always find a regular expression that matches the relative complement of two other regular expressions.


Missing part of the proof of Master Theorem's case 2 (with ceilings and floors) in CLRS?

As you said, the book does not include a proof for $g(n) = \Omega(n^{\log_b a}{\log_bn})$. There is no need to.

Recall that part of proof is to show the upper bound of $f(n)$, when $f(n)$ is defined by the following recurrence relation using the ceiling function, which is the formula 4.25 in CLRS.
$$T(n) = aT(\lceil\frac nb\rceil) + f(n)$$
Noting that the lower bound for $T(n)$ "is routine, since we can push through the bound $\lceil\frac nb\rceil\ge\frac nb$", the book proceed to prove an upper bound for the above $T(n)$, where we only need to show an upper bound for $g(n)$.

What you meant might be the corresponding situation in the case when $f(n)$ is defined using the floor function as the formula 4.26 in CLRS,
$$T(n) = aT(\lfloor\frac nb\rfloor) + f(n)$$
in which case, we will defined $h(n) = \sum_{j=0}^{\lfloor \log_b n \rfloor-1} a^jf(n_j)$ and $n_j = \begin{cases}
n,  & \text{if j = 0} \\
\lfloor n_{j-1}/b \rfloor, & \text{if j > 0}
\end{cases}$.

Note that the definition of $h(n)$ is not the same as that of $g(n)$, although the two are almost the same.

I will leave as an exercise for you to prove a lower bound for the above $T(n)$ using $h(n)$. In particular, you will need to show that in case 2, i.e., when $f(n)=\Theta(n^{\log_b a})$,
$$h(n) = \Omega(n^{\log_b a}{\log_bn}).$$

Hint, as said in the last statement of section 4.6.2 and by Yuval's comment, the proof of the lower bounds is similar.


By definition, PSPACE consists of all languages decided by some Turing machine using polynomial space. So every language in PSPACE can be decided by some Turing machine using space $O(n^\ell)$ for some $\ell$. The space hierarchy theorem ensures moreover that for any $\ell$ there is a language in PSPACE which requires space $\Omega(n^\ell)$.

Any PSPACE-hard language requires space $\Omega(n^k)$ for some $k$, since otherwise any language in PSPACE would be decided by a Turing machine using subpolynomial space, and this contradicts the space hierarchy theorem.

For any $k > 0$ there is a PSPACE-hard language which can be decided in space $O(n^k)$. Indeed, take any PSPACE-complete language $L$. It can be decided using space $O(n^\ell)$ for some $\ell$. Consider now the language $L' = \{(x,0^{|x|^{\ell/k}}) : x \in L\}$, which is PSPACE-hard by reduction from $L$. An algorithm for $L$ can be converted to one for $L'$ which uses $\log n$ space to verify the input structure and $O(|x|^\ell)$ for the rest. Since $n \geq |x|^{\ell/k}$, $O(|x|^\ell) = O(n^{(k/\ell)\ell}) = O(n^k)$.


Determining if $L$ = {$ { a^nsb^n : s \in L(a^*b^*) ,\ n \ge 1 } $} is not a regular language using Pumping Lemma?

Your language is equal to $L(a^+b^+)$ (why?).


An algorithm to specifically remove cycles can be adapted from the more general algorithm to reduce a grammar to its Chomsky normal form. Specifically, it is the elimination of unit productions, usually abbreviated as UNIT, which is responsible for breaking cycles. Really what follows is a explanation (in fact two, the second being more refined) of how UNIT works, as far as I understand it. The best thing to do is probably to work through the example I gave in the question.

For the S production I have:

S -> Xb | Y

   = Xb | X | a   [replace Y with X | a]

   = Xb | a | c   [replace X with c]

Note that X is replaced with just c and not its full right hand side S | c, presumably to avoid introducing the cyclic unit production S->S. Note also that the X is effectively moved to the end during the process of eliminating it (I am unable to work out why this should be the case and would love it if someone could tell me).

For the Y production I have:

Y -> X | a

   = a | S | c   [replace X with S | c]

   = a | c | Xb  [replace S with Xb]

Note again that the unit productions are effectively moved to the end during the process of elimination. And again note that S is replaced with Xb and not Xb | Y, presumably for the aforementioned reason of not introducing the cyclic unit production Y->Y.

For the X production I have:

X -> S | c

   = c | Xb   [replace S with Xb]

Note here that S is replaced with Xb rather than Xb | Y. The reason for this is that the production S->Y has already been used up, so to speak, and therefore should not be introduced again.

This last step, although it now seems to make sense, confused me at first. In what follows the same algorithm is refined further in order to highlight these kinds of steps. It is also closer to a real implementation. I'll work on a different grammar, this one:

S -> Xb | Y

Y -> X | a

X -> Z | d

Z -> Y | c

I start by dividing up the grammar into non-unit and unit productions:

*******
S -> Xb
Y -> a
X -> d
Z -> c
*******

S -> Y
Y -> X
X -> Z
Z -> Y

I keep the list of non-unit productions fixed, and work on the stack of unit productions. As I create new unit productions, I add them to the top of the stack, effectively replacing the old ones. However, I keep the old ones, they remain above the dashed line (ideally I wish I could cross them out), so I have a record of unit productions that I must not re-introduce. At the same time, as I create new non-unit productions, I put them to one side in a new list and do not pollute the original list. I'll write the stack and list next to each other.

So, I eliminate S->Y, adding a new non-unit production S->a and a new unit production S->X, which I get from applying the unit production Y->X that can be found lower down in the stack to the right hand side of S->Y:

1

  S -> Y    S -> a   [from Y->a in the list of non-unit productions]
  ------
  S -> X             [from applying Y->X from further down the stack]
  Y -> X
  X -> Z
  Z -> Y

I'll continue with the process only adding qualifications occasionally when new points crop up...

2

  S -> Y    S -> a
  S -> X    S -> d
  ------
  S -> Z
  Y -> X
  X -> Z
  Z -> Y

3

  S -> Y    S -> a
  S -> X    S -> d
  S -> Z    S -> c   [no more to do, S->Y has been eliminated already]
  ------
  Y -> X
  X -> Z
  Z -> Y

4

  S -> Y    S -> a
  S -> X    S -> d
  S -> Z    S -> c
  Y -> X    Y -> d
  ------
  Y -> Z
  X -> Z
  Z -> Y

5

  S -> Y    S -> a
  S -> X    S -> d
  S -> Z    S -> c
  Y -> X    Y -> d
  Y -> Z    Y -> c
  ------
  X -> Z
  Z -> Y

6

  S -> Y    S -> a
  S -> X    S -> d
  S -> Z    S -> c
  Y -> X    Y -> d
  Y -> Z    Y -> c
  X -> Z    X -> c
  ------
  X -> Y
  Z -> Y

7

  S -> Y    S -> a
  S -> X    S -> d
  S -> Z    S -> c
  Y -> X    Y -> d
  Y -> Z    Y -> c
  X -> Z    X -> c
  X -> Y    X -> a
  ------
  Z -> Y

7

  S -> Y    S -> a
  S -> X    S -> d
  S -> Z    S -> c
  Y -> X    Y -> d
  Y -> Z    Y -> c
  X -> Z    X -> c
  X -> Y    X -> a
  Z -> Y    Z -> a
  ------

I hope these steps are clear. Finally, collating we get:

S -> Xb | a | d | c

Y -> a | d | c

X -> d | c | a

Z -> c | a

The astute may notice that the cycle is in fact X->Z->Y->X, S plays no part. It is possible to detect cycles, or more correctly strongly connected components, as a preliminary step, and then apply UNIT only to these components, which would no doubt make for a more efficient algorithm.


Why DCFL is not closed under kleene star?

The language $\{a^nb^nc^k \mid n,k \ge 1\} \cup \{a^nb^kc^n \mid n,k \ge 1\}$ I believe is a standard example of a non-deterministic context-free language. At least intuitively it is clear that we can push the $a$'s, but we do not know when to pop (compare with $b$'s or with $c$'s?)

The language $L = \{ a^nb^nc^k \mid n,k \ge 1\} \cup \{d\;a^nb^kc^n \mid n,k \ge 1\}$ however, is deterministic. The $d$ prefix gives away which part we are in.

Now consider $(\{d\} \cup L)^*$.


Is relative regularity distinct from regularity?


Extended Compact Genetic Algorithm question

Read the answer from a thread on Google,
thanks to Jeremy P. Harford. (Posted with permission.)

...You can!  Standardized algorithms can always be altered to better fit your needs.  They're generalized forms, and specific applications will often have better fits.
But when you start talking about likeliness, be careful.  Leveraging Bayes requires recursive optimization regarding which there are (too many) patent trolls and a performance pitfall that can be tricky to avoid.  Plus, further empirical sampling can invalidate your algorithm.
And when I say there are too many patent trolls, understand that people who know nothing about Bayesian statistics nor programming are granted patents by other people who know nothing about Bayesian statistics nor programming.  It's a mess.
In this case, applying Bayes can create two tiers of algorithms that don't always complete.  Depending upon your use case, that can get rather hairy.  It's usually a good idea to implement the generic algorithm first, and then alter it as needed -- kind of like when you replace standard containers with use case optimized custom containers.


Why translating a program from one high-level programming language directly into another is difficult?

The task is simple. Here are two naive strategies.
Say we want to compile from A to B.

Pick a language C for which you have a compiler A $\to$ C and an interpreter for $C$ in $B$.
Create a new program in B that includes the compilate (in C) as string and the code of the interpreter.

Compile code in A to machine code or intermediate language. Translate line by line to B.

Both give horrible programs -- but you did not require anything fancy.
The more theoretical answer is: we know that effective (i.e. Turing-computable) compilers exist between any two Turing-complete languages, since such define nothing but an admissible numbering.


How can I see which language type will result from the union or intersection of different language types?

This notion is clalled closure property. A family $\mathcal F$ of languages is closed under (binary) operation $\#$ if $K\# L$ is in $\mathcal F$ for all $K,L$ in $\mathcal F$.

There are no general rules: context-free $\mathsf{CF}$ is closed under union $\cup$, deterministic context-free $\mathsf{DCF}$ is not. However there are resources that list the known closure properties for important families, especially the Chomsy hierarchy.


Algorithm to compute decomposition of a union of sets to a disjoint union of intersections

No, not $O(n)$.  Suppose $0.9n$ are nested and $0.1n$ are not nested (and are unrelated).  Then there can be at least $2^{0.1n}$ different pieces, which is not $O(n)$.

You can find the nesting structure in $O(n^2)$ time by testing all pairs of sets to see which are subsets of the other.


Language Accepted by a Turing Machine with a Useless State?

The definition of the language accepted by a Turing machine is valid for all Turing machines, whether they have useless states or not. Absolutely nothing changes. If there is a useless state, removing it wouldn't change the language accepted by the machine, as does adding another useless state.

Consider a similar question about C programs. What if I have a function which is never called? Does this affect the way the program executes? It doesn't.1 The same holds for Turing machines.

1Actually it might, since you might run out of memory a tiny bit faster.


Can Real-Time Strategy games be ever solved?

It looks like there are elements of (pseudo)randomness in StarCraft.

Of course, this does not seem like a major property and you can ask for solving the game without this feature. Then you end up with a very deep game tree that probably does not have any nice mathematical property or symmetry that would help you to effectively handle it. This is where it differs from the trees that arise from mathematical games.

You can use game theory to play StarCraft well (Monte Carlo, maybe?), but unless there is some strong form of rush that would quickly cut complexity of the tree, I am skeptical about solving it.