Understanding truncation and rounding error in IEEE floating point system?

As listed your reasoning is indeed circular: you start by assuming $h \approx \sqrt{\epsilon}$, then use the results in point 3 to infer that we should take $h \approx \sqrt{\epsilon}$.  So that's not convincing.  So let's redo the analysis more carefully, then we'll look at the meaning of the constant.

A more careful analysis

As in your analysis, we'll assume $f'(x) \approx 1$ and $f''(x) \approx 1$.

Your analysis of truncation error is fine; the truncation error is indeed $\frac{h}{2} f''(x) + O(h^2)$, which given your assumptions is $\frac{h}{2} + O(h^2)$.  In our analysis $h$ will be small enough that $O(h^2)$is negligible, so we'll call the truncation error $\frac{h}{2}$ for simplicity.

What about rounding error?  The rounding error of representing $f(h)$ in floating point is $\epsilon$ in relative error, where $\epsilon$ is the machine epsilon; in absolute error, that is $\epsilon f(h)$.  Since you assumed $f(h) \approx 1$, that is $\approx \epsilon$.  Similarly, the rounding error of representing $f(x+h)$ is $\epsilon f(x+h)$ in absolute error; since $f(x+h) \approx f(x) \approx 1$, that is $\approx \epsilon$ as well.  Now the absolute error of $f(x+h)-f(x)$ is at most about $2\epsilon + \epsilon (f(x+h)-f(x))$; the $2\epsilon$ comes from the error in each of the two subterms (and the triangle inequality), and the $\epsilon (f(x+h)-f(x))$ comes from roundoff error in representing the result.  Since $f(x+h)-f(x) \approx h f'(x) \approx h$, that means the absolute error of $f(x+h)-f(x)$ is at most about $2\epsilon + \epsilon h$.

Then we divide by $h$.  The absolute error becomes $2\epsilon/h + \epsilon$, plus a term due to representing the result in floating point; that extra term is $\epsilon ((f(x+h)-f(x)/h)$, and since $(f(x+h)-f(x)/h \approx f'(x) \approx 1$, we see that the extra term is $\approx \epsilon$.  Therefore the absolute error in computing $(f(x+h)-f(x)/h$ is about
$2\epsilon/h + \epsilon + \epsilon$.  So, the total roundoff error is about $2\epsilon/h + 2\epsilon$, in absolute error.

The total error is at most the sum of the truncation error and the roundoff error, or about
$$\frac{h}{2} + {2\epsilon \over h} + 2\epsilon.$$
We want to know what value of $h$ minimizes this expression.  We can figure that out by letting $g(h) = \frac{h}{2} + 2\epsilon/h + 2\epsilon$ and minimizing $g(h)$; the minima must be at a point where the derivative is zero.  So, differentiate:
$$g'(h) = \frac{1}{2} - {2\epsilon \over h^2}.$$
Setting $g'(h)=0$ and solving for $h$ yields $h^2 =4 \epsilon$, i.e., the function $g(h)$ is minimized at $h=2\sqrt{\epsilon}$; at that point, we have a total (absolute) error of at most $g(2\sqrt{\epsilon}) \approx 2 \sqrt{\epsilon} + 2 \epsilon \approx 2\sqrt{\epsilon}$.

The summary: assuming $f(x)\approx 1$ and $f'(x) \approx 1$, the total error is minimized when you choose $h$ to be about $h\approx 2\sqrt{\epsilon}$.  If you choose $h$ too much larger than that, the truncation error increases and starts dominating.  If you choose $h$ too much smaller than that, the roundoff error increases and starts dominating.

So, if you know $f(x)\approx 1$ and $f'(x) \approx 1$, then it's reasonable to choose $h\approx 2\sqrt{\epsilon}$.

The constant

Now, you might be wondering a bunch of things.  Why the constant 2?  Where did that come from?  How critical is it for the constant to be 2?  What if I use $h \approx \sqrt{\epsilon}$ instead of $h \approx \sqrt{2\epsilon}$?

Well, if you redo the calculation with a different value of $h$, you'll see that the total error is not too sensitive to the constant 2.  For instance, if you choose $h=\epsilon$, then the total error will be at most about $g(\epsilon) \approx  2.5 \sqrt{\epsilon} + 2 \epsilon \approx 2.5 \sqrt{\epsilon}$, which is not that different.  So don't worry too much about the exact value of the constant.

Where did the constant 2 came from?  Well, partly it is coming from the fact that we are doing multiple operations, and you can get a little bit of roundoff error from each operation, so the error can accumulate.  And, partly it is coming from the assumptions that $f'(x) \approx 1$ and $f''(x) \approx 1$.  Of course, those assumptions are pretty sketchy.  In practice, we don't know what $f'(x)$ is before doing the computation (that's the whole point of this computation; we are trying to estimate/compute $f'(x)$), and we don't know what $f''(x)$ is.  So, that assumption also looks circular.

But here's why in this case it might be OK.  You could redo the calculation with different assumptions, e.g., $f'(x) \approx 2$ and $f''(x) \approx 3$.  If you do that, you'll find a slightly different optimal value of $h$; instead of $2 \sqrt{\epsilon}$, you'll have a slightly different constant replacing the 2.  So we can see that the 2 comes from the assumptions about the magnitude of $f'(x)$ and $f''(x)$.  But, crucially, if $f'(x)$ and $f''(x)$ aren't too large or too small, then the resulting constant in the optimal choice of $h$ won't be too different.  It might be $5 \sqrt{\epsilon}$ or $0.5 \sqrt{\epsilon}$, but that's not so bad.

And, in practice, we're often dealing with smooth functions where the derivatives don't get too large, so while we don't know exactly what $f'(x)$ or $f''(x)$ are, we might be able to assume they won't be too large.  As a result, taking $h \approx c \sqrt{\epsilon}$ for some small value of $c$ will be optimal.  We don't know what the optimal value of $c$ is exactly, but we can just heuristically pick a small value for $c$, like $c=1$ or $c=2$, and even if that's not exactly optimal, we'll probably do reasonably well -- it won't be too much worse.

So, the final answer is: no, the 2 is not essential.  It's perfectly reasonable to use $h = \sqrt{\epsilon}$ instead of $h = 2 \sqrt{\epsilon}$ -- but you probably want to choose $h$ somewhere in that neighborhood.


Why does the app I downloaded say that 1 in binary is 00110001?

The app you have converts strings in the ASCII character set to their binary representation.  This representation assigns eight bits for each character in the string. For example, the word "cat" is composed of characters number 99, 97 and 116, which is 01100011 01100001 01110100.

What your app is doing is converting the string "1" into its binary ASCII representation. "1" is character number 49 in ASCII, which is 00110001, and it's pure coincidence that this ends in a 1.

You're completely correct that, as a number, 1 in decimal is 1 in binary.


Consider the general problem of maximizing such function $f$ on a domain $V$. Now suppose there is a graph $G=(V,E)$ on $G$. A local maximum is a vertex $v$ such that $f(v) \geq f(u)$ for all neighbors $u$ of $v$. A global maximum is a vertex $v$ such that $f(v) \geq f(u)$ for all $u \in V$. Hill climbing can get stuck at a local maximum which isn't a global maximum. Perhaps you can construct such an example yourself.

In the 8-queens problem, the domain $V$ is the set of chess boards with k non-conflicting queens on them for $k=0$ to $k=8$. There is an edge between two such boards if you can reach one from the other by placing one queen. The fitness function is simply the number of queens on the board. Simple hill climbing gets stuck if it ends up in a board with fewer than eight queens where no more queens can be placed, because there is no edge that goes to a board with more queens on it.


Non-Midpoint Segment Splitting in Ruppert's Delaunay Triangulation Refinement Algorithm

In Rupert's refinement algorithm, if the circumcenter of a "skinny" (poor quality) triangle were inside the domain and its location is "sufficiently" far away from other points in the triangulation, the algorithm terminates. When the circumcenter is inserted, it is at least a certain distance from all other points (equal to the circumradii), so it will eventually run of space to add more points. Luckily, the ratio of the circumradii and length of the smallest side of a triangle is a function of the smallest angle in the triangle. Therefore, if a skinny triangle is defined as a triangle whose ratio is greater than 1 (corresponds to a minimum angle of 30 degrees), the algorithm is guaranteed to terminate.

But what if the circumcenter is outside the domain? That is when the midpoint on the "nearest" boundary edge is inserted. When the midpoint is inserted, it introduces two short edges whose length is equal the half the length of the original edge. In addition, all points within the diametrical circle of the original edge are deleted so that there are no "even-shorter" edges introduced. And because these two new edges may be shorter than the previous shortest edge in the mesh, during the next step, we should introduce the circumcenter only if the ratio (cumcumradii : shortest length) is greater than some quantity that is strictly greater than 1. In the pdf you shared, it is shown that the ratio should be $\sqrt2$.

If you inserted a point not on the midpoint, but somewhere else on the edge, you will create an edge shorter then half the length of the boundary edge. This edge may be much shorter than the current shortest edge in the mesh. So the ratio that guarantees termination will be greater $\sqrt2$.

To answer your specific questions:
1. Implication: weaker termination guarantee
2. The length of new edges created should be considered. If they all happen to be large, you can happily add a non-midpoint vertex into the mesh. If the boundary edge is a light year long, and other mesh edges are orders of magnitude shorter, you can split the edge almost anywhere ... almost (see below).
3. Yes, splitting on non-midpoints affects termination guarantees.

BUT .....

Alper Ungor's paper attempts to insert off-circumcenter points instead of the circumcenter.

And this paper also allows for insertion of non-midpoint vertices into the mesh. But in the limiting case, it reverts to mid point insertion.


What is the meaning and significance of a Turing machine taking a description of itself as input?

We can then think of the machine description $\langle M \rangle$ as the source code of $M$. If we do this, then the Halting Problem is really concerned with the decision problem

Given the source code of a program and an input string, will the program halt if fed the string as input?

There are many programs that take program code as input. A compiler is a well-known example; a specialized text editor is another.

If the Halting Problem were decidable, there would be a predictor program that could correctly predict the behaviour of any given program, given its source code. We could then modify the predictor program such that it would always behave differently from the program that it was analyzing. But then we could of course feed this modified predictor program its own source code and predict how it would react. And the conclusion would be that its behaviour would be different from its own behaviour -- and this is of course a contradiction.


Kleene star of an infinite unary language always yields a regular language

Suppose there are two words in the language whose lengths are relatively prime. Let these lengths be $x$ and $y$. We know (see this) that by adding these numbers to each other repeatedly, we can get any number greater than $(x - 1)(y - 1) - 1$. So if $x$ and $y$ are $13$ and $7$, we can write any number greater than $72$ as a linear combination of $7$ and $13$. What this means for us: $L_2^*$ consists of some arbitrary finite language (regular, as all finite languages), in union with the language $\{w \in a^* \mid |a| > (x-1)(y-1)-1\}$. This language is regular since it is the language of all words with a finite set of words removed. Since $L_2^*$ is a union of regular languages, it must also be regular.

If all words in $L_2^*$ have lengths which share a greatest common factor (call this common factor $m$), then repeat the above argument, but instead of using string lengths, use string lengths divided by $m$. In this case, $L_2^*$ will be the concatenation of an arbitrary finite language (regular) and the language $\{w \in (a^m)^* \mid |w| > m^2[(x/m - 1)(y/m - 1) - 1]\}$, also regular (since $(a^m)^* is regular and we are removing finitely many words from it).

For example, suppose all words in $L$ have a GCF of 2, and the language contains the words $a^4$ and $a^{10}$. We have $m = 2$, $x/m = 4/2 = 2$, and $y/m = 10/2 = 5$, which are relatively prime. Therefore, we know that we can get any word whose length is multiple of $m$ if the length is greater than $m^2[(x/m - 1)(y/m - 1) - 1] = 2^2[(2 - 1)(5 - 1) - 1] = (4)(3) = 12$ by concatenating $a^4$ and $a^{10}$.


Due to the path

<E>  ->  <T>  ->  <F>  ->  <id>,

you can completely circumvent the "check" for whether there are *.

Think about it in a bottom up manner: only if there's no * nearby can you parse a +.


The paper

  Torbjörn Granlund and Peter L. Montgomery; "Division by Invariant Integers using Multiplication", Proceedings of the ACM SIGPLAN '94 conference on Programming Language Design and Implementation (PLDI):61-72, 1994.

gives the method used, in practice, to calculate (exact) integer division by producing an appropriate reciprocal (accurate to $n$ bits) of the divisor and also a shift amount.  The division is then done by multiplying the dividend by the reciprocal and shifting.

The reciprocal can be found by Newton's method or Goldschmidt's method, as @Yuval stated in the comments.  Those methods produce the reciprocal accurate to $n$ bits in $O(\log n)$ iterations.  Each iteration requires a constant number of multiplications, and once you have the reciprocal you need one more multiplication to multiply the reciprocal by the dividend.

As pointed out by @gnasher729 in the comments, however, you don't need to do each iteration with full precision.  Newton's iteration doubles the number of useful digits each iteration.  So you can use, for example, 32 bit multiplies in the firsts iteration, 64 bit multiplies in the second, etc.  Since that's a geometric sum it sums to a constant and you get $O(M(n))$.


What are the advantages of cuckoo hashing over dynamic perfect hashing?

Dynamic perfect hashing in the sense of Dietzfelbinger et al. only needs 2-independent hashing. While there are some results on simple hashing for cuckoo hash tables, such as twisted tabulation hashing and "Explicit and Efficient Hash Families Suffice for Cuckoo Hashing with a Stash", the original dynamic perfect hashing is more robust in some sense.


Can the runtime of functions with no loops change with the number of calls?

Depends on what something and do this are. In particular, do we have to assume global (or object) state?

Consider this:

int switch(int param) {
  if ( !set.contains(param) )
    set.add(param);
  else
    set.remove(param);
}

Now the runtime clearly depends on the implementation of set and the number of entries it has when switch is called. Calling switch $n$ times starting with an empty set and using pairwise distinct parameters, you might get $\omega(n)$ runtime in total, hence not all calls run in time $O(1)$.

On the other hand, if somefunction does not access state outside of its scope -- assuming that the function itself does not have persistent state -- the runtime can only depend on param. That does not mean runtime is in $O(1)$ -- something and do this may still do non-constant things. Call methods, recurse, etc.

Note that depending on the cost model you use, even adding two numbers has non-constant cost.


premiss of reduction rule (abst) of pure type systems

There are two issues here.

The first most obvious one, is that if there is no rule $(s_1,s_2,s)$ in the pure type system, then there is no way to get from the hypotheses
$$ \Gamma \vdash t_1:s_1$$
and
$$ \Gamma, x:t_1\vdash t_3:s_2$$
to the conclusion
$$ \Gamma\vdash (x:t_1)\rightarrow t_3 : s$$
You can see that if there is no such rule, then your hypothesis is insufficient for forming the product type, and therefore you shouldn't be able to form terms of that type. Note that in the Calculus of Constructions, any $s_1, s_2$ has a corresponding $s$ ($=s_2$), so the premisses are sufficient for the conclusion in all cases.

Another, more subtle issue is that even the fact
$\Gamma, x:t_1\vdash t_3:s_2$ for some $s_2$ is not obvious from the fact
$$\Gamma, x:t_1\vdash t_2:t_3 $$
While actually true, this fact can be subtle to prove depending on how you set up your rules.

The rule you give minimizes the hassle, as it gives you directly the hypothesis that the product is well-formed without having to prove it after the fact.


Asymptotic Question - Determining average case runtime of linear search with summation formula

Suppose that it can be any element of your array. You'll have to consider, for $ 1 <= i <= n $ , what will be the cost if the searched element were at position $i$. If the element were in first position, it would cost $1$ iteration, at second $2$ iterations, and so on. So, if it were at position $i$, it would cost $i$ iterations. In addition, we have $n$ elements, with same chances, so the average cost is the average of the costs that's we have calculated. That's why it's $(1 + 2 + ... + n) / n$.

If you know about probabilities, costs for each element represent a discrete probability distribution, and the average cost is the expected value.


What is the difference between a tight Big $O$ bound, a tight Big $\Omega$ bound and a Big $\Theta$ bound?

$O$ and $\Theta$ refer to different properties of some function. In a sense, we know more of a function when we can describe it with $\Theta$ than with $O$.

However, usage of $O$ or $\Theta$ doesn't imply tightness of a bound. You have some function $f(n)$ that is a bound which you could either describe with $f(n)\in O(g(n))$ or $f(n)\in \Theta(g(n))$, but whether the bound is tight depends on the actual bound $f$.

So, as a tight bound means simply that there is no 'better' bound for all cases, a tight asymptotic bound (either in $O$ or $\Theta$, or even $\Omega$), simply means that there is no better asymptotic description of a bound.

An example of a tight bound with only $O$ is the time complexity of finding an element in an unordered list of size $n$. This complexity is bounded by $O(n)$ and this is tight. The complexity is not $\Theta(n)$, as there are cases when we find the element without scanning the entire list. (The asymptotic complexity of the worst case is $\Theta(n)$, though)

For more reading on bounds with Landau ('big $O$') notation, see the reference question How does one know which notation of time complexity analysis to use? and its answers.


Showing a language is context free. Use PDA or CFG?

For this problem, it's easier to come up with a CFG than it is to invent a PDA. First, notice that the strings should all be of even length, otherwise it's not clear what "middle two symbols" should mean. Here are some hints to get you going.

Hint 1. Could you have grammar rules $T\rightarrow (something)$ which would generate all strings $xx$, where $x$ is a symbol from your alphabet?

Hint 2. If you had a start variable $S$, could you make productions of the form $S\rightarrow (symbol_1)\; S\; (symbol_2)$ that would generate all sentential forms $\alpha\;S\;\beta$ where $\alpha$ and $\beta$ can be any strings over your alphabet and have the same length?

If you can do these two tasks, the CFG is easy.


The time complexity for finding the kth smallest number in a min-heap

There is an $O(k)$ algorithm [1].

[1] Frederickson, G. N. (1993). An optimal algorithm for selection in a min-heap. Information and Computation, 104(2), 197-214.


Apply the transformation $w \mapsto (m+1)w + 1$ to all weights (where $m$ is the number of edges in the graph), and find the minimum weight cut in the new graph. This will give you the minimum weight cut with the minimum number of edges. By computing the value modulo $m+1$, you can determine the number of edges.


Not "it is said", in IPv4 the "host part all zeros" address defines the (sub)net (and isn't available as host address), the "host all ones" address is broadcast for the (sub)net (and also isn't available as host address). All other addresses can certainly be used (and given that IPv4 addresses ran out, there is a lot of pressure to use all).


What is the difference between a Transition System and a Program Graph? (model checking)

You did not provide any particular resources for neither transition system nor program graph. My answer below is based on the book "Principles of Model Checking" by Christel Baier and Joost-Pieter Katoen (The MIT Press).

For completeness, I first present the definitions of both transition system and program graph in this book. (Keep the numbering of the definitions in the book.)

Definition of transition system:

  Definition 2.1 (Transition System $TS$)

  A transition system $TS$ is a tuple $(S, Act, \to, I, AP, L)$ where

  $S$ is a set of states,
  $Act$ is a set of actions,
  $\to \subseteq S \times Act \times S$ is a transition relation,
  $I \subseteq S$ is a set of initial states,
  $AP$ is a set of atomic propositions, and
  $L : S \to 2^{AP}$ is a labeling function.

Definition of program graph:

  Definition 2.13. (Program Graph $PG$)

  A program graph $PG$ over set $Var$ of typed variables is a tuple $(Loc, Act, Effect,
\hookrightarrow, Loc_0,g_0)$ where

  $Loc$ is a set of locations and $Act$ is a set of actions,
  $Effect : Act \times Eval(Var) \to Eval(Var)$ is the effect function,
  $\hookrightarrow \subseteq Loc \times Cond(Var) \times Act \times Loc$ is the conditional transition relation,
  $Loc0 \subseteq Loc$ is a set of initial locations,
  $g_0 \in Cond(Var)$ is the initial condition.

First of all, the program graph consisting of locations as nodes and conditional transitions as edges is not a transition system, since the edges are provided with conditions.

However, each program graph can be interpreted as a transition system. Particular, the underlying transition system of a program graph results from unfolding: a state of the transition system is composed of a location $l$ of the program graph and an evaluation $\eta$ of the variables. Formally,

  Definition 2.15. Transition System Semantics of a Program Graph

  The transition system $TS(PG)$ of program graph $PG = (Loc, Act, Effect, \hookrightarrow, Loc_0, g_0)$
  over set $Var$ of variables is the tuple $(S, Act, \to, I, AP, L)$ where

  $S = Loc \times Eval(Var)$
  $\to \subseteq S \times Act \times S$ is defined by the rule
  $$\frac{l \hookrightarrow^{g:\alpha} l' \land \eta \models g}{\langle l, \eta \rangle \to^{\alpha} \langle l', Effect(\alpha, \eta) \rangle}$$
  $I = \{ \langle l, \eta \rangle \mid l \in Loc_0, \eta \models g_0 \}$
  $AP = Loc \cup Cond(Var)$
  $L (\langle l, \eta \rangle) = \{ l \} \cup \{ g \in Cond(Var) \mid \eta \models g \}$.


3-partition problem: why $b/4 < x_i < b/2$?

The 3-PARTITION problem is NP-complete even without this condition. It is a stronger result that 3-PARTITION is NP-complete even with this condition. The condition presumably comes from the reduction used to prove that 3-PARTITION is NP-hard.

The fact that 3-PARTITION is NP-complete even when all integers are bounded in $(B/4,B/2)$ can be helpful when using 3-PARTITION to prove that other problems are NP-hard.


In the general case a problem like this is NP, however in the vast majority of real cases it should be easy.

20 points make 1140 triangles so it shouldn't be hard to pick out the triangles most similar to your basic shapes (unless the shapes can be more complicated). A little ugly backtracking may be needed when the top scoring triangles overlap.

Also, if most magnets move continuously, you can easily map old points to new points and old triangles to new triangles.

What I'm talking about are fairly obvious methods. There may be smarter ways to do this, but you don't necessarily need them.


Does modern type theory include specifications and implementations?

A type $T$ is a specification. A term $t$ of type $T$ is an implementation together with a proof of correctness.

Dependent types are more expressive than simple types found in programming languages. Via the propositions-as-types correspondence they allow us to express logical statements which comprise a specification, rather than just "bare" typing information.

For instance, the type
$$\prod_{k : \mathbb{N}} \sum_{m : \mathbb{N}} \mathsf{prime}(m) \times (k < m)$$
can be read in any of the following ways:

As a proposition: for every natural number $k$ there is a prime $m$ larger than $k$.
As a type: the type of functions which take as input a number $k$ and output a triple $(m, p, q)$ where $m$ is a number, $p$ is a proof that $m$ is prime, and $q$ is a proof that $k < m$.
As a specification: implement a function which takes a number and returns a prime larger than it.

Fancier specifications can be expressed just as well. For instance, we can express the specification for a dictionary as a dependent sum (or a record type if it's available)
$$\sum_{D : \mathsf{Type}}
  \sum_{K : \mathsf{Type}}
  \sum_{V : \mathsf{Type}}
  \sum_{\mathsf{empty} : D}
  \sum_{\mathsf{add} : K \to V \to D \to D}
  \sum_{\mathsf{lookup} : K \to D \to 1 + V}
  \cdots
$$
which is read as follows: we need to specify the type of dictionaries $D$, the type of keys $K$, the type of values $V$, the empty dictionary, and the addition and lookup functions. The $\cdots$ would express the required properties of dictionaries, i.e., logical statements governing the behavior of a dictionary.


What is the time complexity for division by repeated subtraction?

Your algorithm makes exactly $\lfloor\frac{a}{b}\rfloor$ iterations of while loop.

If we suppose that the size of the inputs is $n=max\{a,b\}$ then your algorithm will make at most $n$ iterations; when $a=n$ and $b=1$.

Therefore, with this notation, your algorithm (on a high level) runs in $O(n)$ time complexity.

If you want to analyze it deeper, including the complexity of addition and subtraction which are $\Theta(n)$ for $n$-digit numbers, things get more complicated because $n$ we defined above was not the number of digits (decimal representation) but a value (unary representation).
As it can be shown, the base in which we represent numbers is not relevant, so the overall analyzed algorithm, having in mind also the properties of big-O and big-Theta runs in $O(n^2)$ where $n$ is the number of digits (in any base).


A two-tape deterministic Turing machine that recognizes an exponential string

To expand fade2black's answer; this is a simple proof by induction that the following TM

State    Symbol    Write  Move   Newstate
start    0         1      L      tolsb
start    1         0      R      carry

tolsb    _         _      R      start
tolsb    *         *      L      tolsb

carry    0         1      L      tolsb
carry    1         0      R      carry

performs a binary count from $0^n$ to $1^n$ in less than $2^{n} + n^3$ steps.
Initially the head is placed on the LSB (which, we assume, is on the left part of the input string).

You can view a simulation of the Turing machine here.

We prove by induction that starting on the leftmost $0$, it counts up to $1^n$ and, at the end, the head is still placed on the LSB.

case $n = 1$:

Immediate

 _ 0    start
   ^
 _ 1    step 1
 ^
 _ 1    step 2
   ^

case $n$: suppose that it holds for $n-1$; i.e. it can count up from $0^{n-1}$ to $1^{n-1}$ in less than $2^{n-1} + (n-1)^3$ steps;

Then after less than $2^{n-1} + (n-1)^3$ steps the head is on LSB:

   1 2 3 ...   n
 _ 1 1 1 ... 1 0
   ^

It will convert all $1$s to $0$ and propagate the carry to the MSB and convert the MSB to $1$ in $n$ steps:

   1 2 3 ...   n
 _ 0 0 0 ... 0 1
             ^

Then it will go back to the LSB in $n$ steps

   1 2 3 ...   n
 _ 0 0 0 ... 0 1
   ^

Then it will count up to $1^n$ using less than $2^{n-1} + (n-1)^3$ steps.

   1 2 3 ...   n
 _ 1 1 1 ... 1 1
   ^

The total number of steps is less than:

$$2^{n-1} + 2^{n-1} + 2(n-1)^3 + 2n \leq 2^n + n^3$$

So if we have as input $w = a^{2^n}$; we can perform a binary count (on the second tape) in linear time $O( |w| )$.


Proving that a class of languages is a subset of RE for Rice Theorem

You missed a tiny detail when defining $C$: all those languages are RE by assumption; no other language can be an $L(M)$!

Let us again look at the language you want to say something about:

$\qquad L = \{ \langle M \rangle \mid M \text{ is a TM}, L(M) \subseteq L\bigl(\, 0(0\cup1)^* \,\bigr) \}$.

We see that $L \subseteq \Sigma^*$ for some alphabet $\Sigma$ that depends on the TM encoding $\langle \_ \rangle$.

Now recall the statement of Rice's theorem: the index set

$\qquad \Phi(X) = \{ \langle M \rangle \mid  M \text{ is a TM}, L(M) \in X \}$

of a language class $X$ is undecidable if $\emptyset \subsetneq X \subsetneq \mathrm{RE}$.

Now, it is obvious (read: very easy to prove -- your exercise) that $L = \Phi(C)$ with

$\qquad C = \{ Y \in \mathrm{RE} \mid Y \subseteq L\bigl( 0(0+1)^* \bigr) \}$;

the requirement $\emptyset \subsetneq C \subsetneq \mathrm{RE}$ is likewise trivial.

We don't get to "just say" anything; we have to prove all three conditions -- $L = \Phi(C)$, $\emptyset \subsetneq C$, and $C \subsetneq \mathrm{RE}$ -- but it so happens that all three proofs are very easy here since $L$ has been defined in a very suitable way. For other languages, the proofs can be more intricate (or impossible; then Rice's theorem does not apply).

Side note: If we consider

$\qquad C' = \{ Y \in \Sigma^* \mid  Y \subseteq L\bigl( 0(0+1)^* \bigr) \}$

then we also get $\Phi(C') = L$! While there are non-RE $X$ in $C'$ (a simple if non-constructive argument is that there are uncountably many such $X$), $\Phi$ "ignores" them. However, $C'$ does not fulfill the conditions of Rice's theorem so we can not use it.


How to iterate through all values of an array?

There are several approaches.  I will use 0-based indexing (so array elements are in the range 0 .. MAX-1) rather than 1-based indexing (range 1 .. MAX), for ease of notation.

Treat as an integer

You can treat the contents of an array as an integer in the range 0 .. MAX^SIZE - 1, expressed in base MAX.  For example, the array with contents [0, 3, 1] corresponds to the integer 0 * MAX^2 + 3 * MAX + 1.  Conversely, each such integer corresponds to an array.

Of course you can iterate through these integers by starting at 0 and incrementing until you reach MAX^SIZE - 1.  Now by expressing that integer in base MAX, you can convert the integer to an array, and thereby iterate through all possible values of the array.

Depth-first search

You can view this as a complete tree of depth SIZE, where each internal node has branching factor MAX.  Each leaf of the tree corresponds to a value of the array.  Then, you can iterate through the leaves of the tree following any standard tree traversal algorithm.

Direct iteration

To iterate through these arrays, it suffices to create an order on the arrays and build an algorithm to advance from one array to the next-largest array.  For this, you can use lexicographic order.  The smallest (first) such array is the all-zeros array [0, 0, ..., 0].

Given an array A, you can advance to the next array in lexicographic order via a simple procedure.  Basically, you increment the last element of the array; if that becomes too large (equal to MAX), it wraps around to 0, and then you increment the next-to-last element of the array (continuing if it wraps around).  If you think about it a bit, this is basically equivalent to the "treat as an integer" solution.

Running time

All of these methods have basically the same running time.  Asymptotically they all require approximately MAX^SIZE operations.  Depending on representation and implementation details, direct iteration might be slightly faster, but the differences are likely to be minor.

(The fine print: depending upon implementation details, the running time of the "treat as an integer" method might be more like SIZE * MAX^SIZE.)

There's no algorithm that can iterate through all values of the array in less than MAX^SIZE operations (as the number of possible arrays is a lower bound on the time to iterate through them all), so there's no hope for an algorithm that is significantly better.


Design a Turing Machine which accepts strings $x \# y$ where $x \ge y$

zigzag left most side and compare each input to compare the 1's with each other.

That is the right idea -- comparing the input one character at a time will work.

However we should be careful that we are comparing the right digits. For example, we don't want to say that 11 is bigger than 101 just because we compared the first two digits only, and said that 11 is bigger than 10. So, maybe it would be helpful to have, as a first step, to see which of them has more digits. Make sure that you ignore leading zeros when doing this.

  but i think i'm way off

Not at all, you have the right idea.


Draw a function by only using two input NOR gates

Yes, looks like you understood the question correctly and are implementing only using NOR-gates.

I also see correct usage of DeMorgan's Theorem.

Your answer seems to be correct. Good luck!


Designing a parallel algorithm to find the second largest item in an array

I'll sketch informally one obvious variant, assuming some model with shared memory and unbounded parallelism (I'm not going to discuss the synchronization issues, though). Lets denote the size of the original array as $n$.

Divide your array into $k$ subarrays of approximately equal sizes $s_i$, such that $s_i \approx \frac{n}{k} \wedge s_i \ge 2$, then assign each subarray to a thread or whatever you use, lets call it "process". This assignment procedure can be (should be) implemented in a way such that its time complexity is $O(1)$.
Then $i$-th parallel process finds the largest $M_i$ and the second largest element $m_i$ of $i$-th subarray sequentially. It's an easy linear complexity algorithm, which works in one go through all the elements of the input. So, time complexity of this step is $O\left(\frac{n}{k}\right)$. $i$-th process will store the results in the first two elements of $i$-th subarray, so you won't need to send $M_i$ and $m_i$ anywhere and resolve the synchronization issues connected with sending/receiving. That's why we need $s_i \ge 2$, and if there is not enough elements then it is not worth to process it in parallel.
Wait until all processes finish (its called a barrier). At this point you have an array of all the results ($M_i$ and $m_i$) of all processes. Now, simply use the sequential algorithm again. The resulting $m$ will be the answer for the whole original array. Time complexity of this step is $O(k)$.

The overall time complexity of our algorithm is $O\left(\frac{n}{k} + k\right)$. Under this very simplistic model it's better to have the number of parallel processes $k \sim \sqrt{n}$ to make the overall time complexity minimal: $O \left( \sqrt{n} \right)$. This result can be easily obtained using differential calculus. Of course, this result is very far from the reality of practical parallel computing: we don't have unbounded parallelism in practice and we need to consider the parallel processing management overhead.


Is the reversal of a minimal DFA also minimal?

The minimal DFA accepting the reversal of the language can be smaller. Consider the finite language
$$ L = (0+1)^22+(0+2)^21+(1+2)^20. $$
The words $\epsilon,0,1,2,00,01,02,11,12,22,000,001$ are inequivalent, so any DFA for $L$ requires at least 12 states; in fact there is a DFA with exactly 12 states. The reverse language
$$ L^R = 2(0+1)^2 + 1(0+2)^2 + 0(1+2)^2 $$
is accepted by a DFA with only 9 states: an initial state, states corresponding to initial $0,1,2$, states corresponding to initial $0(1+2),1(0+2),2(0+1)$, an accepting state and a fail state; this is also the optimal DFA, since $\epsilon,0,1,2,01,12,20,011,000$ are inequivalent.

Summarizing, the minimal DFA for $L$ requires 12 states, while the one for $L^R$ requires only 9 states.

As jmite mentions in their comment, for NFAs with multiple starting states this phenomenon can't happen, since if you flip the direction of all arrows in a NFA for $L$ then you get a valid NFA for $L^R$.


Period of a pseudo-random sequence generated using an LFSR

The LFSR that you give is really of length $4$ rather than $5$, since $b_1$ never gets used. The correct way to implement a "Fibonacci" LFSR is explained in the Wikipedia article: $b_1$ should be the leftmost bit rather than the rightmost bit.

There is also an alternative kind of LFSR knows as a "Galois" LFSR, also described in Wikipedia, which is dual to a Fibonacci LFSR: at each point, the contents of the register is shifted, and if the bit which is shifted out is 1, then a mask is XORed to the contents. In both types of LFSR, the resulting sequence has maximum period iff the feedback polynomial is primitive.

The polynomials that you give as examples are known as trinomials, polynomials with three non-zero monomials. Not all trinomials are primitive. There are algorithms for deciding whether a trinomial, or any other polynomial, is primitive. As far as I know, there is no explicit construction of primitive polynomials.

How do we test whether a given polynomial $P$ of degree $n$ is primitive? The first step is verifying that it is irreducible. The second step verifies that $x^{(2^n-1)/p} \not\equiv 1 \pmod{P}$ for every prime divisor $p$ of $2^n-1$ – this step requires factoring $2^n-1$. A list of primitive polynomials can be found on Wikipedia.


Why are Linearly Bounded Turing Machines more powerful than Finite State Automata?

The linear bounded Turing machine is restricted to a tape whose length is a linear function of the length of the input.

If the length limit were a constant, then the machine would be no more powerful than a DFA. However, a DFA cannot grow more states to cope with a longer input, which in effect the LBTM can do (taking the state to be the entire machine configuration.) So the LBTM is strictly more powerful.


Your problem is an instance of the following problem:

VECTOR-MINIMIZATION:
Input: vectors $v,w \in \mathbb{R}^m$, a threshold $\gamma \in \mathbb{R}$
Goal: minimize $v \cdot x$, subject to $w \cdot x \ge \gamma$ and $x \in \{0,1\}^m$

In your problem, $v=(v(t_1),\dots,v(t_m))$ and $w=(w_1,\dots,w_m)$ where $w_i = \sum_{t_i \in r_j} 1/|r_j|$, where the sum is over all $j$ such that the set $r_j$ contains the element $t_i$.

So, your problem is an instance of VECTOR-MINIMIZATION.  In turn, VECTOR-MINIMIZATION is basically an instance of the knapsack problem (it is at least as hard as knapsack, and thus NP-hard).

That raises the question, is your problem any easier than the general VECTOR-MINIMIZATION problem (or knapsack)?  In your problem, each $w_i$ has a special form: it is a sum of a polynomial number of reciprocals of polynomial-size integers.  I don't think there's any way to use the special structure of the $w_i$'s (and there are exponentially many possible values for the $w_i$'s), so I think your problem is NP-hard, but I don't have a proof at the moment.

That said, you can still use the standard algorithms for knapsack-like problems: e.g., integer linear programming (ILP).


How to prove that $L_1=1^*\cup \{0^i 1^{j^2}|i\ge 0,j\ge 0\} $ is irregular?

You don't need to use the pumping lemma to prove that $L_1$ is irregular. You can also make use of the closure properties of the regular languages.

We know that regular languages are closed under intersection. That is, if $L_1$ and $L_2$ are regular languages then $L_3 = L_1\cap L_2$ is also a regular language.

A nice way to prove that a language is irregular is to assume that it is regular and reach a contradiction using the closure properties of the regular languages.

For example consider the language $L_p = \{1^p: p\text{ is prime}\}$ we know that this is an irregular language. Let's consider $L_q = L_p \cup 0^*$. How can we prove that this language is irregular?

Let us assume for the purpose of contradiction that $L_q$ is regular, hence $L_q\cap 1^*$ is also a regular language since $1^*$ is a regular language. But wait.. The intersection is $L_p$ (the primes) which is not a regular language. Contradiction. So $L_q$ is irregular.

Your problem can be solved along the same lines.


Complexity/Hardness of a generalization of an Inclusion/Exclusion problem

For each element in $S$, count the number of times it is a member of $A_i$, $1\le i\le n$. If that number is $m$, we add 1 to the tally. The final tally is what we wanted.

The above algorithm takes $O(tn)$ time if the computational cost to check membership is $O(1)$. It takes $O(ttn)$ time if the computational cost to check membership proportional to the size of the set, which is at most $t$.

So you can see the problem is in $P$. It has nothing to do with that general inclusion–exclusion principle.


Hint. For any language $L$, $$A^* = L \cup (A^* - L).$$
Now, choose an appropriate language $L$ to solve your problem.


$A, B$ --- enumerable sets, is $A \times B$ enumerable?

There are many ways you could solve this, so here's a hint. $A$ and $B$ are enumerable, which means that injections

$$ f : A \rightarrow \mathbb{N} \quad \text{and} \quad g : B \rightarrow \mathbb{N}$$

exist. Now, given a tuple $t \in A \times B$, how can you map it to a unique element in $\mathbb{N} \times \mathbb{N}$ using $f$ and $g$?

   Since $f$ and $g$ are injections, their product must also be an injection (prove this). So the function $h : A \times B \rightarrow \mathbb{N} \times \mathbb{N}$, defined as $(a, b) \mapsto (f(a), g(b))$. Is an bijection on a subset of $\mathbb{N} \times \mathbb{N}$ (because it is an injection on $\mathbb{N} \times \mathbb{N}$).

A subset of an enumerable set is always countable, so this concludes the proof.


What is the relation between the compatibile features and the state features in Actor Critic Algorithm?

$\phi(s)$ is the representation of the state, and $\psi$ is the gradient (of the log) of the policy. Essentially, those two don't really have any connection, except for that the input to the policy is the state's representation. That is, the policy will compute the appropriate action distribution according by using its model (say a neural network) when applied on the representation of a state.


Software or program, what is the difference?

Expanding Pradhyuman's answer. From Wikipedia:

Software Engineering can be divided into ten subdisciplines that correspond to distinct phases of the software development process. They are:

Software requirements: The elicitation, analysis, specification, and validation of requirements for software.
Software design: The process of defining the architecture, components, interfaces, and other characteristics of a system or component. It is also defined as the result of that process.
Software construction: The detailed creation of working, meaningful software through a combination of coding, verification, unit testing, integration testing, and debugging.
Software testing: The dynamic verification of the behavior of a program on a finite set of test cases, suitably selected from the usually infinite executions domain, against the expected behavior.
Software maintenance: The totality of activities required to provide cost-effective support to software.
Software configuration management: The identification of the configuration of a system at distinct points in time for the purpose of systematically controlling changes to the configuration, and maintaining the integrity and traceability of the configuration throughout the system life cycle.
Software engineering management: The application of management activities—planning, coordinating, measuring, monitoring, controlling, and reporting—to ensure that the development and maintenance of software is systematic, disciplined, and quantified.
Software engineering process: The definition, implementation, assessment, measurement, management, change, and improvement of the software life cycle process itself.
Software engineering tools and methods: The computer-based tools that are intended to assist the software life cycle processes, see Computer Aided Software Engineering, and the methods which impose structure on the software engineering activity with the goal of making the activity systematic and ultimately more likely to be successful.
Software quality: The degree to which a set of inherent characteristics fulfills requirements.

...

As you can see, programmers are mainly required for software construction and maintenance.

A software engineer should have strong knowledges of all the software development phases and should be a good programmer, too (actually most programmers employed in big companies are engineers :-).

Obviously for small software projects some phases may overlap (or may be ignored) and programmers may be involved directly in many of them. For large software projects (like an operating system) there can be hundreds (thousands) of software engineers and programmers involved.


Rigorous error bounds for eigenvalue solvers

It might suffice to ask the solver to give you both the eigenvalue $\lambda$ and the corresponding eigenvector $v$.  Then you can verify for yourself how much error there is.  Note that if $\lambda$ is the eigenvalue corresponding to eigenvector $v$, for matrix $M$, then we have $Mv=\lambda v$.  So if you know $M$ and $v$ exactly, and you have a claim that $\hat{\lambda}$ is within $\epsilon$ of the true eigenvalue $\lambda$, it suffices to check that

$$(\hat{\lambda}-\epsilon)v \le Mv \le (\hat{\lambda}+\epsilon)v$$

where $\le$ is to be interpreted separately for each index, i.e., you should check that $(\hat{\lambda}-\epsilon)v_i \le (Mv)_i \le (\hat{\lambda}+\epsilon)v_i$ holds for each index.

If there is some error in the eigenvector $\hat{v}$ returned by the solver, then there is the possibility that the above check might fail, even if $\hat{\lambda}$ is indeed a true eigenvalue of the matrix.  I don't know whether there's a nice way to adapt the above calculation to address this issue.  If the operator norm $\|M\|_1$ is small, then it might work to check that

$$(\hat{\lambda}-\epsilon)\hat{v}_i -c \le M\hat{v} \le (\hat{\lambda}+\epsilon)\hat{v} + c$$

where $c = \|M - \hat{\lambda} \text{Id}\|_1 \times c'$ and $c'$ is an upper bound on the amount of error in $v$ (measured in $L_1$ distance) that you're willing to tolerate.  I'm not sure if this is exactly right; there might be issues in this last criterion, so check it yourself before believing in it.


Computing min and max using median of 3 elements

Let the list be $x_1,\ldots,x_n$. The algorithm is as follows:

Let $S = \{x_1,x_2\}$.
For $i = 3,\ldots, n$:

Add $x_i$ to $S$.
Compute the median of $S$, and remove it from $S$.

Output $S$.

I'll let you figure out why this works.

Note that we cannot possibly tell which is the minimum and which is the maximum. Indeed, $\operatorname{median3}$ works the same for both the original order and its reverse.


Running Time of naive implementation of Dijkstra's Algorithm

In each iteration we need to go over all edges crossing the cut $(X,V\setminus X)$. The algorithm doesn't explain how we do that, so it is difficult to analyze the exact running time, though $O(m)$ per iteration is definitely an upper bound. A naive implementation will presumably go over all edges, checking which of them cross the cut, and for this implementation, the running time will indeed be $\Theta(m)$ per iteration.


Amortized analysis of base Fibonacci counter

As far as I know, there's no general method for designing a potential function, which makes sense when you consider that they can be used for different purposes. I've been trying on and off for 20 years, and to this day, I have no idea how Sleator and Tarjan came up with the function they used to prove the optimality (with respect to an arbitrary PDF) of splay trees.

Having said that, it often helps to work backwards. I'm going to show you what I mean for the algorithm for incrementing binary numbers. This should give you some ideas about how to proceed.

Let's start by simply checking the number of bit-flips required to increment numbers, starting with zero:

+--------------+---------+
| Bit sequence | # flips |
+--------------+---------+
|            1 |       1 |
|           10 |       2 |
|           11 |       1 |
|          100 |       3 |
|          101 |       1 |
|          110 |       2 |
|          111 |       1 |
|         1000 |       4 |
|         1001 |       1 |
|         1010 |       2 |
+--------------+---------+

So that's the ruler function, which you may recognise as being the solution to the Tower of Hanoi problem. It satisfies the recurrence:

$$a(2n) = 1$$
$$a(2n+1) = 1 + a(n)$$

But that's neither here nor there. What's interesting is that as you go on, the average number of flips per increment seems to trend towards 2; you can write a little program yourself to verify this, or you can note that half the increments flip one bit, a quarter flip two bits, and in general $\frac{1}{2^i}$ of them flip $i$ bits for $i>0$. Do the sum yourself.

So we need to design a potential function so that each increment "costs" two flips. If the increment only flips one bit, we want to put another flip in the bank, as it were, so we can withdraw it later. If the increment flips two bits, we want the potential function to be the same, and so on.

Recall that for an operation which transform the state $S_b$ into the state $S_e$:

$$T_{\hbox{amortised}}(S_b \rightarrow S_e) = T_{\hbox{actual}}(S_b \rightarrow S_e) + \Phi(S_e) - \Phi(S_b)$$

In our case, we want all increments to have their amortised time to be at most 2. So:

$$2 \ge T_{\hbox{actual}}(0 \rightarrow 1) + \Phi(1) - \Phi(0) = 1 + \Phi(1) - \Phi(0)$$
$$2 \ge T_{\hbox{actual}}(1 \rightarrow 10) + \Phi(10) - \Phi(1) = 2 + \Phi(10) - \Phi(1)$$
$$2 \ge T_{\hbox{actual}}(10 \rightarrow 11) + \Phi(11) - \Phi(10) = 1 + \Phi(11) - \Phi(10)$$

And so on. This gets us somewhere, because it gives us some bounds on what the potential function might be.

There are a number of potential functions which could satisfy these constraints. In this case, however, there's a straightforward optimal solution. Setting $\Phi(0) = 0$ and making the inequalities equalities gives us the potential function:

$$\Phi(0) = 0$$
$$\Phi(1) = 1$$
$$\Phi(10) = 1$$
$$\Phi(11) = 2$$
$$\Phi(100) = 1$$

There's no obvious pattern so far, but if you extend this on, you'll find that $\Phi(S)$ is the number of 1's in $S$ (i.e. the Hamming weight of $S$). This makes intuitive sense, when you think about it: Incrementing a zero takes only one flip, but incrementing a one takes more than one. So the number of ones in the string is a measure of how "hard" it will be to increment it in the future. It's a reasonable analogue of "potential energy".

Now that we've identified a candidate potential function, we can now work forward again to try to prove the result.


How would a Turing Machine recognize n consecutive characters

What answer I came up with would be this. We would use a TM with 2 tapes, t1, t2 and 2 headers h1, h2.

P0. Scan the first tape with the input, if a character ∉ {a, b}
REJECT.
P1. Write "#" and n character of "1" on t2, the head remaining
in the right extremity.
P2. Read characters on t1 and while they are "a" repeat P3, P4.
P3. Move h1 to the right
P4. Read the character on t2 and if it's "1" move h2 to the left, if it's "#" move h2 to the right extremity.
P5. If the read character on t1 is "b" repeat P6
P6. Read the character on t2, if it's "1" move h2 to the right extremity, if it's "#" ACCEPT
P7. Getting at the end and not accepting means we REJECT

I had no example so I am not sure this is 100% correct but it's what I came up with after few hours of thinking. Hope it helps someone and please correct me if it's wrong.


No, it is not symmetric.

Here's my counter-example: Consider the language $L_1 = \{A:A'| A'$ is $A$  sorted$\}$
and $L_2 = \{A:a| a$ is the largest element in $A\}$.

We can solve the max-element problem with a constant number of calls to a machine solving sorting. Just sort $A$ then take the first element. But we can't solve sorting with a constant number of calls to a machine solving max-element (otherwise, we could sort in $O(n)$, which is known to be impossible).


What is the complete version of the paper: "How to Generate and Exchange Secrets (extended abstract)" by Andrew Yao?

Garbled circuits were only implied by the extended abstract. They were only explicitly introduced in the talk given by Andrew Yao at the conference.

This is clear from a footnote on the Turing Award Page:

  The first of these two papers introduces secure function evaluation, and gives a > protocol for the famous Millionaires’ Problem. In talks related to these papers > Yao introduced a technique for secure computation known as garbled circuits.

which may be found here: http://amturing.acm.org/bib/yao_1611524.cfm#bib_6

Credit is due to Wandering Logic for giving this very helpful answer in the comments above.


Your language is in P; try to figure out why. If P=NP, all non-trivial languages in P are NP-complete, and in particular this one.


A question on decidable formal languages and turing machines

A counterexample is choosing L' as the empty language. That can be decided faster than most other languages.


Algorithm with no closed-form exact complexity

The runtime of an algorithm that computes the Ackermann function can't be expressed using primitive recursive functions. All commonly known named functions (well, besides the Ackermann function) are primitive recursive as far as I know.


Asymptotic relationship of logarithms in different bases

We'll show two results. The first is that for any positive constant $k$, we'll have
$$
k\cdot f(n) = O(f(n))
$$
To see this, recall what it means for $g(n)=O(f(n))$: this is true when we can find two constants $c>0, N\ge 0$ such that $g(n)\le c\cdot f(n)$ for all $n\ge N$. If we choose $g(n)$ to be $k\cdot f(n)$ then we have just what we need: we'll just use $k$ for our constant $c$ and select any $N$ we want. It's trivial to adapt this argument to big-$\Omega$, and so it also holds for big-$\Theta$ as well.

In simple terms: Asymptotic notation ignores constant multiples.

The second result we need is that logs to different bases are always going to be constant multiples of each other, namely
$$
\log_ax=(\log_ab)\log_bx
$$
This is easy to see: just raise $a$ to each side power and you'll wind up with equal results.

In the problem stated, assuming that $\lg n$ is $\log_2n$, we'll have
$$
\lg n=(\log_2 8)\log_8n=3\log_8n
$$
and the two logs will differ only by a multiple of 3, which as we showed above, means that $\lg n$ and $\log_8n$ are the same function, as far as big-whatever notation is concerned.


I will try to answer your question limiting to Datalog without recursive predicates. Indeed, I suspect that recursive predicates are beyond conjunctive queries (conjunctive queries are a subset of FOL, and Datalog with recursion can compute Transitive Closures, which are impossible to express in FOL). Furthermore, I will assume that all derived datalog predicates have been unfolded.
As you probably know, a conjunctive query CQ1 contains CQ2 if you can establish an homomorphism of terms from CQ1 into CQ2. Hence, a possible reduction into SAT can be done by considering a boolean variable v for each pair of terms from Terms(CQ1)xTerms(CQ2). Intuitively, the meaning of such variables would be "we map term t1 to term t2". Then, we must ensure that the set of all variables "v" that evaluates to true encodes a correct homomorphism.
More formally, the reduction can be done as follows:

For each term $t^1_i \in Terms(CQ1)$, and for each term $t^2_j \in Terms(CQ2)$, consider a boolean variable $v_{t^1_i, t^2_j}$. Note that all the boolean variables evaluating to true encodes a mapping.
The encoded mapping must be functional. That is, for each term $t^1_i$, we need a constraint to state that $t^1_i$ is mapped to one term, and only one. Hence, we should add, for each term $t^1_i$, a constraint $(v_{t^1_i, t^2_1} \lor v_{t^1_i, t^2_2} \lor ... \lor v_{t^1_i, t^2_n})$, and for each triple of terms $t^1_i$, $t^2_j$, $t^2_k$ (with j!=k), $(\neg (v_{t^1_i, t^2_j} \land v_{t^1_i, t^2_k}))$
The encoded mapping must preserve constants. Hence, for each constant term $t^1_c$, we add the constraint: $(v_{t^1_c t^2_c})$
The encoded mapping must be a homomorphism. To do so, for each literal $L^1 \in Literals(CQ1)$, let $\{L^2_1 ... L^2_n\}$ be the set of all literals from $Literals(CQ2)$ with the same predicate. Then, we must ensure that, when mapping the terms of $L^1$ we obtain one literal from $\{L^2_1 ... L^2_n\}$. To do so, we build a disjunction where each disjunct $i$ means "$L_1$ is mapped to $L_i$". In particular, each one of these disjuncts can be built by iterating all the variables from $L^1$ and mapping them to $L^2_i$ variables. For instance, consider $L^1$ to be  $P(x, x, y)$, and considere $\{L^2_1 ... L^2_n\}$ to be $\{P(a, b, a), P(c, c, d)\}$; in this case we would build the constraint: $(v_{x a} \land v_{x b} \land v_{y a}) \lor (v_{x c} \land v_{x c} \land v_{y d})$

This reduction is polynomial. Indeed, the number of boolean variables is quadratic (w.r.t. the number of terms in CQ1 and CQ2), and all the constraints considered can be built with a several (nested) foreach loops that iterates the conjunctive queries terms and literals.


Occurrences notation in "Compiling Pattern Matching to Good Decision Trees"

I will try to illustrate the concept more intuitively and informally by representing
terms as trees.

A term can be represented as a rooted tree, where the leafs are atomic
operands (literals, or variables) and the other nodes are
operators. Typically abstract syntax trees can be built on that model
as this example (taken in another answer), for which I am giving both the textual syntax and the
tree representation.

if (x > y) {
   if (y < a) {
     x:= a
     y:= b
   } else {
    x:= b;
   }
 }
              if
     ________/|\________
    /         |         \
   >          if        :=
  / \    ____/|\____   /  \
 x   y  /     |     \ x    b
       <     :=     :=
      / \   /  \   /  \
     y   a x    a y    b

But the concept is used in a lot of different contexts, with different
kinds of operators. The example term above could also be written as in the
text of your question in function call style:

if(>(x,y),if(<(y,a),:=(x,a),:=(y,b)),:=(x,b))

where the operators are if, >, <, and :=.

Whatever the kind of term you are interested in, an occurrence is a
position in the tree (to which we can associate corresponding
positions in any of the strings representation).

A subterm corresponds to a subtree, and an occurrence is the location
of the main operator of a subterm, i.e. its root.

A simple way to designate unambiguously an occurrence is to give the
path to access that occurrence from the root of the tree. The path is
simply a string of integers that tell you at each node which of the
daughter you should consider.

So the empty word $\Lambda$ correspond to the root itself (the top
if in my example), since there is no path to be followed.

The string $2\;1\;2$ tell you to go to the second daughter, then to
the first, then the second again. So it is an occurrence corresponding
to the position of the leftmost a.

That in particular is useful to distinguish the two occurrences of
a, the other one being  $2\;2\;2$.

An the occurrence of the term :=(y,b) is $2\;3$.

Of course, an occurrence is meaningful only with respect to a term,
and that is why your document systematically associate the reference
term with the path, i.e. string, denoting an occurrence in that term.

Actually, the notation used in your document is a bit abusive, though
it is common, because an occurrence is really a position in the term,
where some subterm occurs, but it is not that subterm (though it is
sometimes taken as such if the context makes it unambiguous).

To get the subterm, you should normally explicitly apply a function
that  takes an occurrence as argument and returns whatever subterm is
found there.


Can we show that non-determinism adds no power, for some specific running time?

If $\mathsf{NTIME}(n^k) \subseteq \mathsf{TIME}(n^\ell)$ for any $k,\ell$ then $\mathsf{P} = \mathsf{NP}$. Indeed, any problem $L \in \mathsf{NP}$ can be solved in non-deterministic time $O(n^r)$ for some $r$. Consider now the problem $L' = \{0^{|x|^{r/k}}1x : x \in L\}$. Clearly this problem is still in $\mathsf{NP}$, and furthermore the previous algorithm solves it in non-deterministic time $O(n^k)$. Therefore $L'$ has a deterministic algorithm running in time $O(n^\ell)$, implying that $L$ has a deterministic algorithm running in time $O(n^{r(\ell/k)})$.

This trick is known as padding.


Are regular languages and their regular expressions part of computer science?

There are several things that are all called regular expressions. The answer to your question is different depending upon which thing you want to talk about.

The three relevant distinctions for this question in my opinion are as follows:

First

The notion of regular languages and related things like recursive enumerability.

Individual regular languages are isomorphic, (i.e. able to be losslessly transformed to and from,) to deterministic finite automata and reducing something to a regular language demonstrate results about that thing's computablity,
so I would argue it is part of computing science.

If linguistics folks find the notion or regular languages useful, however, then we can share it. Human languages are (generally?) not regular languages but something more complex, so I would be surprised if that was the case.

I think most interested people would give the same answer to whether regular languages are invented or discovered as they would about mathematics.

Second

The particular notation for describing regular languages, in the formal literature, developed by Kleene and others.

This is clearly invented. There's no particular reason we have to have used * and + in particular to represent those ideas. If you want to assign this notation to one or more fields, I would argue it belongs to any field that publishes papers using it.

Third

Computer programs which take as input an expression in a language and produce an automata or something resembling one and that result can then be used to perform operations on a different input including search and replace.

The languages these programs define which usually contains some form of the Kleene Star and Kleene Plus, along with several other more complicated but useful constructions, which are generally absent from formal regular language literature to my knowledge. Backreferences would be one example of this. These programs are invented, as are their particular sets of notations. They are also instances of computer engineering rather than computing science per se. Although of course they are building on at least a certain amount of computing science results, and computing science results can be stated about these programs. For example, it is possible to construct regular expressions of this sort that produce exponential running times, and subsets of those notations can be defined where that is impossible.


recursive language and computable function

The question is about the relation between a computable function $f$ and its graph (here denoted by $L_f$).
Since the function is total, the function is computable if and only if its graph is recursive (in case $f$ is a partial computable function, $f$ is computable if and only if its graph is r.e.).

So, your guess is right, and the correct answer is A.
To compute $f$ from the characteristic function of the graph, you need to use a generate and test technique, progressively trying all possible outputs y for a given input x (using the characteristic function as tester), until you find the correct pair x#y. Since such a pair must exist, your algorithm is terminating.


Space requirement of a universal Turing machine

The constant depends on the size of the respective tape alphabets. If the two are the same and you're very careful, you can probably make do with only $n + O(1)$ space, where the constant only depends on the simulated machine. The idea is to store the tape of the simulated machine from the point of view of the cell pointed to by the head, interleaving both sides of the tape. This is not the most time-efficient simulation, but the blow-up in time is still only polynomial.


In the Hopcroft-Karp algorithm, what is the purpose of the breadth first search?

Vertex-disjoint means that no vertex appears in two augmenting paths.  The paths have to be disjoint so that all can be used.  If we have two augmenting paths, P1 and P2, and we augment the matching using using P1, is P2 still an augmenting path for the augmented matching?  Yes, if P1 and P2 are vertex disjoint.

As for minimum length, it has the practical implication that we spend the shortest time looking for augmenting paths, but there is a technical matter, too.  Augmenting paths found this way are guaranteed to be vertex-disjoint.  Look at this text.


Hint: Replace a singleton clause $a$ with $a \lor b$ and many copies of $\lnot b \lor c$, $\lnot b \lor \lnot c$.

Reductions without extra variables don't work even when singleton clauses are allowed. There are five types of clauses: $\ell_1,\lnot \ell_1, \ell_1 \lor \ell_2$, $\ell_1 \lor \lnot \ell_2$, $\lnot \ell_1 \lor \lnot \ell_2$. Suppose that $k$ of $\ell_1,\ell_2,\ell_2$ are true. The probability that a random clause of each type is true is:
$$
\begin{array}{c|cccc}
k&0&1&2&3\\\hline
\ell_1 & 0 & 1/3 & 2/3 & 1 \\
\lnot \ell_1 & 1 & 2/3 & 1/3 & 0 \\
\ell_1 \lor \ell_2 & 0 & 2/3 & 1 & 1\\
\ell_1 \lor \lnot \ell_2 & 1 & 1/3 & 1/3 & 1\\
\lnot \ell_1 \lor \lnot \ell_2 & 1 & 1 & 2/3 & 0
\end{array}
$$
We would like to take a convex combination of these rows which is of the form
$$ \begin{array}{cccc} \alpha & \beta & \beta & \beta \end{array} $$
However, all such convex combinations have $\alpha = \beta$.


Are there BBP formulas for all computable numbers?

You can easily use diagonalization to construct a computable real which is not of this form. Fix some enumeration of all triplets $(b,p,q)$. I will describe a process that generates binary digits of a real number.

The process goes over all triplets $(b,p,q)$ in the fixed order. Suppose that it's time to handle $(b_i,p_i,q_i)$, and that currently we have generated the digits $\beta_1 \dots \beta_n$. The process evaluates the corresponding sum $S(b,p,q)$ to such a precision that the first $n+1$ binary digits can be gleaned for it. It outputs $\beta_{n+1}$ so as not to equal to $S(b,p,q)$.

The argument as stated is not 100% correct, and I'm leaving it to the reader to discover where I cheated and to fix the proof.


How does in-order traversal in Binary search tree works (recursion)

Consider indorder as a command in military. Let the binary tree be the hierarchy among the soldiers.

The general shouts "inorder!" and that means, when a subordinate receives the order, he tells it to his "left" subordinates. If he has no subordinates on the left side, then he yells out his name, and only then he commands his right subordinate to execute the order.

  Inorder! command means "tell your first subordinate, do it yourself, and then tell your right subordinate. Afther you are
  finished, report to your superior."

The general is the root of the binary tree.
He shouts out "inorder!"

That means his left subordinate gets the order, and shouts out "inorder!" himself. This process goes on until the order reaches to a soldier who has no left subordinate. Then, he yells out his name and gives the order to his right subordinate.

After all his right subordinates are done, he reports back to his immediate superior. The superior, like him, yells out his name and gives the order to his right subordinate.

When all the left side is done, the general (root of the binary tree) yells out his name and gives the order to his right side.

Now, consider this tree
(taken from https://www.geeksforgeeks.org/tree-traversals-inorder-preorder-and-postorder/):

The general is 1. He shouts "inorder!"

2 recieves the order, and he shouts "inorder!"

4 receives the order. He has no left child, and thus shouts his name: 4

He has also no right child, and thus reports to 2.

Left side of 2 is done, and this 2 shouts his name: 2, and then gives the order to the right side.

This process goes on, until the root is notified a second time.


What does Lambda Calculus teach us about data?

You should turn the question around and ask what is not data. After all, code is just more data, is it not?

Perhaps a useful view from a programming point of view is that of a value. Say that in a programming language a value is a piece of information or data which can be stored, passed around as arguments and results of functions, they can be dynamically generated at runtime, etc.

Typical types of values are int, char, bool, various arrays of these, lists, trees, etc. In many languages functions are not values. For instance, in C you cannot pass a function as an argument or return it as a result. (Caveat: a pointer to a function is not a function!) Programming languages in which functions are values are called functional programming languages. Examples include Haskell, OCaml, SML, scheme, racket, javascript, and many others.

We can reformulate "there is no difference beween code and data" as "functions are values". So it really is a design choice as to whether code should be considered data. In functional programming languages this is the case, while in many others it is not.


How to understand the analysis of expected running time of randomized quick-sort in this paper?

The root node corresponds to a subproblem of size $n$. This is larger than $(3/4)^1 n$ and at most $(3/4)^0 n$, so the root node lies in group $0$.

Given any element $x$ and any integer $i$, the expected number of subproblems of group $i$ containing $x$ is at most $2$. This is because if $P$ is a subproblem of group $i$ containing $x$ and $Q$ is its child subproblem containing $x$, then $Q$ is of group $i+1$ with probability at least $1/2$. (Some calculation is needed here.)

Linearity of expectation shows that the expected total size of all subproblems of group $i$ is at most $2n$ — we get this by summing the expected number of subproblems of group $i$ containing $x$ over all possible elements. (You can only understand this if you know what linearity of expectation is.)


In applications to time complexity of algorithms, you are often only interested bounding the growth (i.e., $O(), \Omega()$ asymptotics), and often the initial values incide as multiplicative factors to the solution (or their influence is swamped by the growth of terms that don't include them). So you'll often see sloppy statements that omit initial values.


Succinct bounded-sum array with $O(1)$ access

Raman, Raman, and Rao is a standard reference for rank/select in O(1) time.  This solves your problem for the special case of a static array, i.e., you can retrieve $A[i]$ in $O(1)$ time, but not update $A$: see the third bullet item in their abstract.  The rank operation can be used to determine membership, and the select operation retrieves the $i$th element of the array.  Their data structure requires $o(n)+O(\lg \lg m)$ extra space beyond the minimum.

The conclusion of their paper also mentions a lower bound if you want to support insert, delete, rank, and select.  I don't know if that's applicable here.


Theorem: The set $\Sigma^{*}$ of all words is decidable.

Proof. According to the definition of decidability, we must provide a computable function $d$ which takes a word $w$ and outputs $1$ if $w \in \Sigma^{*}$, and outputs $0$ if $w \not\in \Sigma^{*}$. Such a function is very easily constructed, it is
$$d(w) = 1,$$
That is, because every word is in $\Sigma^{*}$, the decision function always says "yes". QED.


Solving $T(n)= 3T(\frac{n}{4}) + n\cdot \lg(n)$ using the master theorem

If our recurrence takes the form $T(n) = aT(n/b) + f(n)$, then to use the "third case" of the Master method we must have the following hold:

  $f(n) = \Omega(n^{\log_b a + \epsilon})$ for some $\epsilon > 0$ and if $a f(n/b) \leq c f(n)$ for some constant $c < 1$ and all sufficiently large $n$, then $T(n) = \Theta(f(n))$

Our recurrence is defined as $$T(n) = 3T(n/4) + n \log n.$$

By definition we have, $a = 3, b = 4, f(n) = n \log n$.

We now need to show that $f(n)$ is polynomially larger than $n^{\log_b a}$. That is the "$f(n) = \Omega(n^{\log_b a + \epsilon})$" part from above. Defining $\epsilon \approx 0.2$ achieves this. The reason being that $\log_4 3 \approx 0.793$ and $f(n) = \Omega(n^{0.793 + \epsilon})$.

We are left to show that $f(n)$ satisfies the regularity condition. That is the "$a f(n/b) \leq c f(n)$ for some constant $c < 1$ and all sufficiently large $n$" part.

We simply plug in our values of $a,b$ to get: $$a f(n/b) = 3(n/4) \log (n/4).$$ All we did was take the "$n$" in $f(n)$ and plug in "$n/4$".

To make this easier to see, let $k = n/4$ and observe that $a f(k) = a k \log k$. Swapping $k$ with $n/4$ we have $$3(n/4) \log (n/4) \leq (3/4)n \log n = c f(n)$$ where $c = 3/4$.

This finishes our necessary requirements and we have that $T(n) = \Theta(n \log n)$.


Explaining the difference between computer science and computer literacy

How about an automotive analogy?

uses computers and maybe "is good with computers" :: a driver (can drive and refuel safely) and maybe a car enthusiast (can jump start a car; is familiar with many makes and models; knows techniques like using windshield treatment to keep rain from reducing visibility).
programmer :: an automotive mechanic or technician. Knows how cars work. Can repair and modify cars and even build kit cars. Ought to know how to debug/diagnose problems by using the scientific method. Might not be aware of relevant theory and thus might write O(n2) loops.
software engineer :: an automotive engineer. Designs cars, engines, and other components that you can entrust your life with, and does it within schedule, cost, manufacturability, and other constraints. Knows how to apply the relevant theory/math such as finite element analysis.
computer scientist :: an automotive scientist. Researches new ideas in vehicles, human-machine interfaces, and propulsion. Does computational crash test modeling. Adds to the body of theory and experimental results.

So for people who equate all “computing” with “proficient in using some software package,” that's like equating driving proficiency with the ability to design antilock brakes that we trust lives to, that are manufacturable with consistent high quality and low cost, and work for years in extreme weather. Or equating driving proficiency with researching what kind of radar-triggered braking features will avoid collisions without freaking the driver into swerving into another lane.

Perhaps lay people confuse these terms because "computer science" classes teach computer use skills, programming, theory, or engineering. All that stuff (arguably not the first part) fits in the curriculum of computer science. None of it is the end-all "content" of computer science, just as English classes are learning on the way to an English major (a fuzzier concept).


Does a coin tossing algorithm terminate?

The formal, unambiguous way to state this is “terminates with probability 1” or “terminates almost surely”. In probability theory, “almost” means “with probability 1”.

For a probabilistic Turing machine, termination is defined as “terminates always” (i.e. whatever the random sequence is), not as “terminates with probability 1”. This definition makes decidability by a probabilistic Turing machine equivalent to decidability by a deterministic Turing machine supplied with an infinite tape of random bits — PTM are mostly interesting in complexity theory. In applied CS, though, computations that always give the correct result but terminate only with probability 1 are a lot more useful than computations that may return an incorrect result.


Why is Hamming Weight (in the CRC context) independent from the data?

Let us call a data vector of some fixed length together with its CRC a codeword. Since CRC is a linear code, the set of codewords is closed under XOR (this is the definition of linear code).

Let $x$ be a codeword, and suppose that $y$ is a noisy version of $x$ which is also a codeword. Since CRC is linear, $x \oplus y$ is also a codeword. If $D$ is the minimum Hamming weight of a non-zero vector in the code, then the Hamming weight of $x \oplus y$ is at least $D$, that is, $y$ differs from $x$ in at least $D$ positions. This shows that at least $D$ errors need to occur in order for the errors to go undetected.

Conversely, let $w$ be a codeword of Hamming weight $D$. Then $y = x \oplus w$ is another codeword which differs from $x$ in $D$ positions. That is, $D$ errors (in appropriate locations) are enough for an error to go undetected starting from $x$. Note that $x$ here is completely arbitrary. This is why the minimum number of errors is independent of the data.


Complexity for finding a ball that maximizes the number of points lying in it

It looks like a sublinear algorithm for the Ball Range Counting Problem isn't known for now.

However, if you could accept a non-exact answer then you could approximate a disk by a set of squares with different orientation. For each orientation you'll have to build a Range Tree, which will allow you to count all points inside a square in $O(log^2(n)+k)$ time (k - a number of resulting points).

Each range tree will require $O(n \cdot log(n))$ memory, the better approximation you want the more orientations you should use. For example, two orientations will give you an octagon, which approximates a disk with area error less than 6%.


Recall that if a TM $M$ doesn't halt on input $x$, then $x \notin L(M)$

Your mistake is in (1), if $M$ doesn't halt on $x$, then $M'$ doesn't halt too (since the simulation of $M$ on $x$ doesn't halt). so  $M'$ doesn't accept any input, that is $L(M')=\phi$.


Context free grammar for nested arrays separated by commas

your current implementation doesn't enforce the first condition "A pair of square bracket tokens [] surrounding zero or more values separated by commas" as an empty string or a NUMBER on its own would be accepted by the grammar.

You could use the following CFG to maintain the integrity of the constraints

array ::= [ ] | [ element ]

element ::= value | value , element

value ::= array | NUMBER

To derive [NUMBER, [NUMBER, NUMBER], NUMBER]

Start with array -> [element]

[ element ]
[ value, element ]
[value, array ]
[value, value, element ]
[value, array, value]
[value, [element], value]
[value, [value, element], value]
[value, [value, value], value]
[NUMBER, [NUMBER, NUMBER], NUMBER]

The grammar rules provided for JSON here might also be a useful reference: http://json.org/


It is correct.

Every infinite set has an undecidable subset, you can use the cardinality argument: $\aleph_0\leq C \implies \aleph_0 < 2^C$. In fact most of its subsets are undecidable (and you can replace undecidable with any countable class of languages, e.g. c.e., arithmetical, analytical, ...).

The bad thing about this argument is that it doesn't give any information about how difficult the subset is. We usually want a subset which is as easy as possible. One way to get this is using a diagonalization similar to the cardinality argument using the fact that $C$ is decidable:

Define $D = \{ i \in C \mid i \notin W_i \}$, where $W_i$ is the $i$th c.e. set. Obviously $D \subseteq C$. Moreover $D$ can be solved with an oracle for $C$ and $K = \{ i \mid i\notin W_i\}$. So if $C$ is decidable then $D$ is a co-c.e. language.


Why does Union-Find have time complexity O(N + M lg* N) with the "log star N"?

Check out the analysis of path compression in Union-Find by Seidel and Sharir "Top-Down Analysis of Path Compression", SIAM Journal of Computing 34:3 (2005), pp 515-525. Somewhat heavy going, the result you cite is a step on the way to the best-possible bound by their method.


One approach is to compute the distance $d(u,v)$ between each pair $u,v$ of vertices using an all-pairs shortest paths algorithm, such as Floyd-Warshall.  Then, if $d(v,v) < 0$, you know that there exists a cycle through $v$ that doesn't add to zero.  You can explicitly find one such cycle by augmenting the shortest-paths algorithm with predecessor links to keep track of an example shortest path from $v$ to $v$.  Then you know that at least one of the edges along that cycle has an error.

Unfortunately there doesn't appear to be any way to uniquely determine which edges are in error.  For instance, consider a graph with edge $a \to b$ of weight $1.01$ and edge $b \to c$ of weight $-1.48$ and edge $c \to a$ of weight $0.50$; you know that at least one of those edges has an error, but there's no way to know which one; it could even be all of them that have an error.


How to use stable matching algorithm in order to determine optimal schedule?

we could simply create an array with the all the ports and then upon each encounter of a port we'd check if it's already been visited by another ship: if not then we leave the ship for maintenance at the port; if it's already been visited then we keep going forward until we encounter a previously unvisited port.

The following is a counterexample to your algorithm:

  Ship 1: Port 1, at sea, Port 2, at sea, Port 3, at sea

  Ship 2: at sea, Port 1, at sea, Port 2, at sea, Port 3

  Ship 3: Port 2, at sea, Port 3, at sea, Port 1, at sea

This has the solution where Ship 1 stays at Port 3, Ship 2 stays at port 2, and Ship 3 stays at Port 1.

But your algorithm does the following:

Day 1:

Ship 1 arrives at Port 1. Port 1 hasn't been visited so it stays for maintenance.
Ship 3 arrives at Port 2. Port 2 hasn't been visited so it stays for maintenance.

Day 2:

Ship 2 arrives at Port 1 where Ship 1 is already staying, which isn't allowed (and you're not allowed to not have Ship 2 not arrive at Port 1 given the rules described in the end of the problem's 3rd paragraph).

If we add to your algorithm your unjustified assumption that ships can't stay for maintenance at the first port they visit, then your algorithm does the following:

Day 1:

Ship 1 arrives at Port 1. It's not allowed to stay at the first port it visits.
Ship 3 arrives at Port 2. It's not allowed to stay at the first port it visits.

Day 2:

Ship 2 arrives at Port 1. It's not allowed to stay at the first port it visits.

Day 3:

Ship 1 arrives at Port 2. Port 2 hasn't been matched yet so it stays there.
Ship 3 arrives at Port 3. Port 3 hasn't been matched yet so it stays there.

Day 4: Ship 2 arrives at Port 2 where Ship 1 is already staying.

As for the question of how to solve this using stable matchings, here's a hint: you're trying to find a matching between ships and ports (where they stay for maintenance), such that the following is impossible:

Ship A is matched to Port A
Ship B is matched to Port B
Ship A arrives at Port B before it arrives at Port A (it's not yet on maintenance when it gets to Port B)
Ship A arrives at Port B after Ship B does (so Ship B is already staying there for maintenance)

How can you translate that into preferences for ship-port pairs so you can apply Gale Shapley matching?


Decidability of the language of DFAs accepting only odd-length strings

Every DFA can be simplified by a Turing Machine, so you can simplify the DFA you receive as input and compare it to the simplified DFA that accepts odd-length strings.

On input $M$:

Simplify $M$. Remove every unreachable state and transition from $M$ (disjoint from start state)
If the start state of $M$ is reject, and the only other state in $M$ is accept, and for every $w \in \Gamma, \exists$ a $w-arrow$ from accept to reject and from reject to accept, then accept. Otherwise reject.


Difference between regular expressions: $(0^*1^*)^*$ and $(0+1)^*$

The language of both regular expressions is the same, $L((0+1)^*)=L((0^*1^*)^*)$. This follows from the following three claims:

Claim 1:

  if $L_1 \subseteq L_2$, then $L_1^* \subseteq L_2^*$.

Claim 2:

  $L(0+1) \subseteq L(0^*1^*)$

Claim 3:

  $ (0^*1^*)^* \subseteq (0+1)^* \equiv \Sigma^*$

The 2nd and 3rd claims are trivial. Prove the first claim and you're done.

Note however, that the two regular expressions are not the same (ie., they are different!). They are equivalent in the sense of the language they generate. They are different in the way they generate it.


Types and Programming Languages - proof for theorem about principles of induction of terms

While you should get in the habit of providing definitions so your question is self-contained, especially when the original text is not easily accessible, the first thing to note is that the theorem doesn't actually depend at all on what "terms" are or how "depth" is defined.

Given any set $S$ and any function $f:S\to\mathbb N$, the theorem will hold. That is, $$(\forall s\in S.(\forall r\in S.f(r) < f(s) \to P(r))\to P(s))\to \forall s\in S.P(S)$$

How useful this theorem is depends on $f$. For example, if $f$ is a constant function then this theorem simplifies to $(\forall s\in S.P(s))\to(\forall s\in S.P(s))$ which isn't very useful.

To prove this via complete induction, you should, as is always a helpful strategy, write out the definitions, in this case, of complete induction. Complete induction states: $$(\forall n\in\mathbb N.(\forall m\in\mathbb N.m < n\to Q(m))\to Q(n))\to\forall n\in\mathbb N.Q(n)$$

So the bulk of the task is choosing an appropriate $Q$ to get the result that you want. As the hint states, the fairly obvious choice is $Q(n)\equiv\forall s\in S.f(s)=n\to P(s)$. If you stick this $Q$ into the formula for complete induction, you can simplify it into the first formula. All the work comes down basically to showing that $\forall n\in\mathbb N.\forall s\in S.f(s)=n\to P(s)\iff\forall s\in S.P(s)$ which is a simple and  purely logical exercise. Indeed, we don't even need the fact that $\mathbb N$ is the naturals to prove this lemma, though we do need that fact to apply complete induction for the theorem overall.


Why can't we just use preorder traversal to check if a tree is subtree of binary tree?

Because different trees can have the same pre-order label sequence (easy exercise).

To check equality, recurse on both trees at the same time. That gives you a simple (if not terribly efficient) algorithm for checking whether a tree is a subtree of another one.


Binary Floating Point Range/Precision for 4-bit Mantissa and 4-bit Exponent

Yes, that is correct. Your mantissa has only three magnitude bits, so you can only represent numbers from -8 to 7, multiplied of course by any power of 2 from $2^{-8}$ to $2^7$. 11 is impossible to represent, because any positive exponent gets you multiples of 2, any negative exponent gets you numbers less or equal to $7*2^{-1}=3.5$, and exponent 0 is just numbers from -8 to 7.


Improvement of algorithm due to constrained graph

Edmonds-Karp algorithm works by building successive flows $f_0, \dots, f_n$ where each flow $f_{i+1}$ can be obtained by combining $f_i$ and a path in the "residual graph" $G_{f_i}$ obtained through a BFS (the residual graph is just the original graph where we removed full edges).

Now, the idea of the proof in Introduction to Algorithms is to introduce a distance $\delta_f(s,v)$ from the source node $s$ to all nodes $v\in V$ in the graph $G_f$. Then they prove 4 things:

$\delta_{f_i}(s,v)$ can only increase with $i$ (i.e. $\delta_{f_i}(s,v)\leq \delta_{f_{i+1}}(s,v)$) that is their lemma 26.7;
if an edge $(u,v)$ is not saturated by a flow $f_i$ (i.e. $(u,v)$ is not saturated in $f_{i-1}$ but is in $f_i$) and then unsaturated in the flow $f_j$ with $j>i$ then $\delta_{f_j}(s,v)-\delta_{f_i}(s,v)\geq 2$. That means an edge can become saturated at most $1+|V|/2$ times (since $\delta_{f}(s,v)\leq|V|$);
at each BFS, an edge become saturated.

By combining these, we have that each edge can be saturated at most |V|/2+1 times ($\delta_{f}(s,v)\leq |V|$) and that the Edmonds-Karp algorithm is in $O(E×(E×V))$ where $O(E)$ is the time taken for one BFS and $O(E×V)$ the number of BFS (i.e. the maximum number of times an edge can become saturated).

For you the complexity is O(K×V×E) : finding a path is in $O(E)$ and you might have to find $(|V|/2+1)×K$ times an augmenting path where $K$ is the number of edges that can become saturated (i.e. $K=V$ for you thus $O(E×V^2)$).


Fastest way to compute a path from a known cycle with unordered edges and vertices

I understand your question this way:

There is given a graph with nodes and edges. There might or might not be one or more circles in that graph. And there is given a certain start-node within the set of nodes.

You ask, if this start-node is part of at least one circle, and you ask, which nodes (of which one is the given start-node) and edges form the smallest circle.

If this was your question, then I have an answer:

DFS is not the best choice. BFS is. BFS = Breadth-first-search. There is an wikipedia-article that describes this algorithm.

The idea of this algorithm is to begin to test all nodes at the end of the edges that are directly connected with the given node. This gives you a list of all direct neighboring nodes of the start-node. I call them the level-1-neighbors.

In the next step you repeat this search for each level-1-neighbors, but now you ignore all edges that directly lead back to where you did come from. The result are the level-2-neighbors. And then you repeat this for the level-n-neighbors to get the level-(n+1)-neighbors.

This transforms your graph into a new graph, which is a tree. The start-node is the root of this tree, the level-1-neighbors are the roots children, level2-neighbors are children of those children.

If your original graph contains a circle, then nodes will appear twice (or more often) in the resulting tree, because there are (at least) two different ways, that you can move through the circle to reach nodes in the circle (clockwise and counter-clockwise).

So, if a certain node appears a second time in the graph, then you have found a circle. The circle is the path starting at one representation of that node, going up till you reach the first common ancestor of both representations and then go down to the second representation.

If the common ancestor is the root node, you found the circle with the least number of nodes that goes through the given node. If the common ancestor is not the root, then you just have found a circle, that is connected with the given node by a side-arm. In this case you must go on searching.

There is an easier (but longer) algorithm for the case that there are directed edges: Use BFS until you hit the start-node for a second time. Then the path from the root to the second representation of the start-node is the shortest circle. This is simpler (you need not compare every new node with any node you already passed, but only with the root), but probably needs more resources because the tree you have to build will be deeper.

In both versions of the algorithm you must pay attention not to get lost in loops (again and again walking through circles that are not the needed circle)


Computational complexity of Bell numbers

Yes, the $n$th Bell number is exponential in $n$.  Wikipedia lists the following relation:

$$B_{n+1} = \sum_{k=0}^n {n \choose k} B_k.$$

It follows that

$$B_{n+1} \ge B_n + n B_{n-1} \ge n B_{n-1},$$

so

$$B_{n+1} \ge n(n-2)(n-4)\cdots \ge (n/2)^{n/4},$$

which is exponential in $n$.

This fact has little or nothing to do with NP-hardness; it is just unconditionally true, regardless of whether P = NP or not.

If you have a problem for which every algorithm takes $\Omega(B_n)$ time, then the problem is not in P; it requires exponential time.  It might or might not be in NP.

If you have a problem where the obvious algorithm takes $\Theta(B_n)$ time, that proves nothing (maybe there is some other algorithm you haven't thought of yet that is faster).


Note that FACTOR isn't known to be NP-complete.


First, let's give your productions a number.

  1 $S \to AaAb$
  2 $S \to BbBa$
  3 $A \to \varepsilon$
  4 $B \to \varepsilon$

Let's compute the first and follow sets first. For small examples such as these, using intuition about these sets is enough.

$$\mathsf{FIRST}(S) = \{a, b\}\\
\mathsf{FIRST}(A) = \{\}\\
\mathsf{FIRST}(B) = \{\}\\
\mathsf{FOLLOW}(A) = \{a, b\}\\
\mathsf{FOLLOW}(B) = \{a, b\}$$

Now let's compute the $LL(1)$ table. By definition, if we don't get conflicts, the grammar is $LL(1)$.

    a | b |
-----------
S | 1 | 2 |
A | 3 | 3 |
B | 4 | 4 |

As there are no conflicts, the grammar is $LL(1)$.

Now for the $SLR(1)$ table. First, the $LR(0)$ automaton.

$$\mbox{state 0}\\
S \to \bullet AaAb\\
S \to \bullet BbBa\\
A \to \bullet\\
B \to \bullet\\
A \implies 1\\
B \implies 5\\
$$$$\mbox{state 1}\\
S \to A \bullet aAb\\
a \implies 2\\
$$$$\mbox{state 2}\\
S \to Aa \bullet Ab\\
A \to \bullet\\
A \implies 3\\
$$$$\mbox{state 3}\\
S \to AaA \bullet b\\
b \implies 4\\
$$$$\mbox{state 4}\\
S \to AaAb \bullet b\\
$$$$\mbox{state 5}\\
S \to B \bullet bBa\\
b \implies 6\\
$$$$\mbox{state 6}\\
S \to Bb \bullet Ba\\
B \to \bullet\\
B \implies 7\\
$$$$\mbox{state 7}\\
S \to BbB \bullet a \\
a \implies 8\\
$$$$\mbox{state 8}\\
S \to BbBa \bullet \\
$$

And then the $SLR(1)$ table (I assume $S$ can be followed by anything).

    a     | b     | A | B |
---------------------------
0 | R3/R4 | R3/R4 | 1 | 5 |
1 | S2    |       |   |   |
2 | R3    | R3    | 3 |   |
3 |       | S4    |   |   |
4 | R1    | R1    |   |   |
5 |       | S4    |   |   |
6 | R4    | R4    |   | 7 |
7 | S8    |       |   |   |
8 | R2    | R2    |   |   |

There are conflicts in state 0, so the grammar is not $SLR(1)$. Note that if $LALR(1)$ was used instead, then both conflicts would be resolved correctly: in state 0 on lookahead $a$ $LALR(1)$ would take R3 and on lookahead $b$ it would take R4.

This gives rise to the interesting question whether there is a grammar that is $LL(1)$ but not $LALR(1)$, which is the case but not easy to find an example of.


Find a maximum sum in matrix, subject to special constraint

This can be solved in $O(NM)$ time using dynamic programming.

Given any solution, let $s$ denote the smallest index $s$ such that $a[s][1]$ is selected.  (It follows that $a[1][1],\dots,a[s-1][1]$ are not selected and that $a[s][1],\dots,a[N][1]$ are selected.)  This partitions solutions based on the value of $s$, i.e., based on which entries from the first column are selected in that solution.  There are only $N$ possible values for $s$.

Now define $f(s,t)$ to be the largest sum that is possible by selecting some entries from the submatrix $a[1..N][t..M]$, subject to the restriction that you choose all of $a[s..N][t]$ and don't choose any of $a[1..s-1][t]$.  You can easily find a recurrence relation that expresses $f(s,t)$ in terms of a few values of the form $f(s',t+1)$.  This immediately yields a simple dynamic programming algorithm with running time $O(NM)$.


Decidability of bitstring languages with no ones' complements

I don't think there exist recognizable-but-undecidable OCA languages, because if we have a Turing machine M that recognizes a given OCA language, then we can create a derived Turing machine that incrementally simulates M on both its input and its one's-complement (flipping back and forth, trying a finite number of steps in each simulation) until one input or the other has been recognized.

(Note: the derived Turing machine will also need to be given specific logic to decide the empty string; but that's obviously possible to do for any given language.)

Therefore, you can't construct any reduction mapping that would let you prove the existence of recognizable-but-undecidable OCA languages.


Allocating tasks among two people equitably

Suppose that the time for completing task $i$ is $a_i$ for $A$ and $b_i$ for $B$. Let $S$ be the set of tasks performed by $B$. The total time required is
$$
\sum_i a_i + \sum_{i \in S} (b_i-a_i).
$$
Your goal is then to find a subset $S \subseteq [2n]$ of size $n$ which maximizes $\sum_{i \in S} (b_i - a_i)$. You take it from here.


What does "deterministic" mean in the context of memory management?

So what does "reference counting is deterministic" mean, if anything?

It means it is deterministic in the absence of multiple threads. Threads almost always ruin this sort of determinism, with or without a race condition, memory collection or whatnot: in one run, thread A, can be scheduled first a bit, then another thread, B gets scheduled a bit; in a second run, the OS can schedule the threads to run in the opposite order, thus almost all threaded programs  inherently lose this determinism.

Therefore "race condition" and "threads" usually put a procedure out of the scope of this use of this meaning of determinism.


Binary tree algorithm asymptotic analysis problem

They're not the same thing.  Consider some node $x$.  Ask yourself how many times the algorithm does the operation "iterate through all the ancestors of $x$".

The first algorithm does this operation once.  The second algorithm does this operation $k$ times, where $k$ is the number of descendants of $x$.  So, it's no surprise that the second algorithm takes longer: it's doing a lot more repeated work.


The property that makes a binary tree a binary search tree is that for every branch labeled $x$, all of the labels in the left subtree are smaller than $x$ and all of the labels in the right subtree are greater than $x$.

If you look at your tree, that property is violated in many places. For example, $5$ is in the right subtree of the node labeled $15$, yet $15 \not < 5$.


Is union of context-free and non-context-free languages non-context-free?

Not in general. Consider a language $L$ over some alphabet $\Sigma$ such that neither $L$ nor its complement $\overline{L}$ is a decidable language. It is obvious that neither of these languages can be context-free. But $L \cup \overline{L} = \Sigma^*$, which is a context-free language.

And consider $\emptyset$, which is trivially a context-free language. Clearly $L \cup \emptyset = L$ is not a context-free language.


Total number of bits of storage for direct mapped cache

I'll give these hints without actually solving it for you

1) You do not need to provide tags for all memory, only for the memory that is in the cache.

2) As the block (cache line) is 16 bytes, you only need one tag for each of these.

3) The valid bit are also only for the cached I guess.