Fast hashing: combination of different techniques to identify changes in a file?

There are two sides to your coin:

if you want to do it secure, you will need to use a cryptographically secure hash like SHA256 (crypto-hashes are meant to be fast, but tend to be a bit slow due to security constraints),
things like CRCs are definitely quicker, but will never be able to offer the same kind of security (especially when we’re talking about .

Option 1: CRCs — Doing it quickly at the price of security:

If you're just after the detection of changes, go for a checksum instead of a hash. That's what checksums were made for: quickly detecting changes in a file or data-stream. But keep in mind that CRC was designed to prevent transmission errors, not malicious action!

Practically, CRC32 is the most obvious candidate (but even an additive CRC8 would do the job if you only want to detect if something has changed and don't expect anything else than that from the CRC.)

Option 2: Beyond CRCs — Doing it rather quickly while enhancing change-detection:

Other valid options (looking at @poncho's comment) are indeed to simply check the last-mod timestamp.

Or, you combine both (to prevent bottlenecks), using something like this pseudo-code shows:

if(LastMod != knownLastMod) { CreateNewCRCandCompare(FileName, knownCRC) };

But does this offer any real security? No. Same goes for your…

  Why I consider checking the tail is:
   - MP3 has the tag information there
   - EXIF adds custom data at the end if I'm right

Again, it depends on how much security you expect. You have to realize that an adversary will surely manipulate the file to keep (or copy-and-paste) any old ID3 and EXIF data… as anyone (with appropriate RW file-access rights) can modify that. Same goes for the Last-Modification timestamp, frame rates, resolution, last change date, and even the  (file) length. Depending on that “additional”  and “modifiable” data — which can be modified and removed by anyone with enough file-access rights — would introduce a security flaw.

But you do expect security, don't you? After all, that's the reason why you're thinking about all this in the first place. Well, then there is not way around using crypto-secure hashes…

Option 3: Cryptographically Secure Hashes — Doing it securely at the price of speed:

If you expect real security, you will have to rely on hashing; to be more precise: cryptographically secure hashing (using a hash which is not known to produce collisions). It takes time (a few microsecs per MB) but it's worth it.

My 2 (personal) cents:

Try to live with the fact that hashing costs time and hash the whole files with a cryptographically secure hash. Because, when stuff starts hitting the fan… you're better off being slow, instead of being sorry.

EDIT based on your EDIT…

If cryptographic security isn’t your main focus, you could look at MD5 or SHA1. Both MD5 and SHA1 are “cryptographically broken” because collisions have been detected… yet for the change-detection purposes you describe (especially after your EDIT), the likely-ness of hitting such a collision should be minimal enough.

Looking at everything again (including your EDIT), I personally would most probably use MD5, because it offers a usable collision resistance (for change-detection purposes) while still being fast enough to completely hash multi-gigabyte files.

If that still doesn’t satisfy you in a “speed” sense or if your hardware resources are really that limited, you have to try to balance collision-resistance/change-detection with speed. Meaning…

Take the individual timestamp, the individual filename, and hash the header (length depends on media type and used file format) as well as a good chunk from the middle and a good chunk of the tail (= file end). Combine those 5 and you should be able to roughly filter out most

  I'd be ok with a ~80% chance of having the correct bookmarks. How many hash pieces should I put together and where in the file would that be?

That’s more of a personal opinion, as it depends on a whole truckload of details (media type, file format, available resources, expected change-detection ratio, file similarity, etc.) so will have to balance that out yourself depending on your personal expectations, your implementations, and local results due to hardware and/or software bottlenecks.

Let me try to provide you with some guidance nevertheless:

If hashing the complete file isn’t an option for whatever reasons, I would – at least – take: the header (and maybe a few KBs more), a good chunk from the middle (at least the size of the “header & co.” part), and a good chunk from the file end (again, at least the size of the “header & co.” part).

The more resources you can invest (or are willing to invest), the more chunks you can take and/or the bigger those chunks can be. If you think your resources/feel/whatever still offers room for more, increase the size of the chunks you hash and/or increase the number of chunks you hash.

Increasing the number of chunks is easy: as all you need to do is to take care of an equal distribution (by dividing the filesize accordingly, resulting in same-size chunks you extract from equally-spaced parts over the whole file-length).

And if you’re asking yourself “Why equally distributed and not random chunk-positions?”, let me simply note that picking random chunk positions might practically render your change-detection efforts void since it incorporates the risk of skipping some important parts media where you would normally detect the chances you are aiming to detect. Choosing an equal distribution is – simply said – more neutral.


Lambda calculus outside functional programming?

You are asking for an application outside of computer science and logic. That is easily found, for example in algebraic topology it is convenient to have a cartesian closed category of spaces, see convenient category of  topological spaces on nLab. The formal language corresponding to cartesian closed categories is precisely the $\lambda$-calculus. Let me illustrate with a very simple example how this comes in handy.

First, as a warmup exercise, suppose someone asks you whether the function $f : \mathbb{R} \to \mathbb{R}$ defined by $f(x) = x^2 e^x + \log (1 + x^2)$ is differentiable. You do not actually have to prove that it is, you just observe that it is a composition of differentiable functions, therefore differentiable. In other words, you made an easy conclusion based on the form of definition.

Now for the real example. Suppose someone asks you whether the function $f : \mathbb{R} \to \mathbb{R}$ defined by
$$f(x) = \left(\lambda f : \mathcal{C}(\mathbb{R}) . \int_{-x}^{x} f(1 + t^2) dt\right)(\lambda y : \mathbb{R} . \max(x, \sin(y + 3))$$
is continuous. Again, we can immediately answer "yes" because the function is defined using the $\lambda$-calculus and starting from continuous maps $\max$, $\int$, $\sin$, etc.

Various extensions of the $\lambda$-calculus make it possible to do the same sort of thing in other areas. For example, because a smooth topos is a cartesian closed category, any map which is defined using the $\lambda$-calculus, starting from derivatives and the ring structure of the reals (and you can throw in the exponential function if you wish) is automatically smooth. (Actually, the main thrust of the smooth topos is the existence of nilpotent infinitesimals which allow you to meaningfully say things like "we disect a disc into infinitely thin isosceles triangles".)


How to think when devising a TM that decides if a DFA rejects some string?

The problem with your approach is that there are infinitely many strings in $\Sigma^*$. If the automaton keeps accepting and accepting, how would you know hen to stop?

Instead, consider how an automaton can reject: it rejects by getting to a rejecting state.


How do I show T(n) = 2T(n-1) + k is O(2^n)?

In this case, your best bet is to just solve the recurrence by direct substitution.

$$\begin{align*}
T(n) &= 2T(n-1) + k \\
     &= 2\big(2T(n-2) + k\big) + k \\
     &= 2\big(2\big(2T(n-3) + k\big) + k\big) + k\\
     &= \cdots\\
     &= 2^rT(n-r) + k\sum_{i=0}^{r-1} 2^i\\
     &= 2^rT(n-r) + k(2^r-1)\,.
\end{align*}$$

Putting $r=n$ gives
$$\begin{align*}
T(n) &= 2^nT(0) + k(2^n-1) \\
     &= 2^n(T(0) + k) - k \\
     &= O(2^n)
\end{align*}$$
since, although you forgot to define $T(0)$, it is a constant and so is $k$.


I will leave the actual drawing up to you, but I will describe it here. You can draw a directed graph, with a start state that follows the input #feature to another node which follows an edge to #: to #op to #( to #feature to #). The node that we land on after #) is the accept state. If it any point, we read some input that does not allow us to follow that path, we immediately travel to another state (in this case, a designated reject state) with no output paths.

Our accept state will only have one out edge, which we follow on the input #feature. This takes us back to where we traveled after our start state. If we read any other input from our accept state, we move to the designated reject state.


Does any graph based optimization problem, which have a greedy algorithm, has guarantee that there exist an order which give the optimum

Yes, for every simple graph problem I can think of it's pretty simple to come up with some greedy strategy that gives the optimum if you order your vertices correctly.
Take for example Independent Set. The simplest strategy imaginable for finding an independent set is to fix some ordering $(v_1,\ldots,v_n)$ on the vertices of your graph $G$, putting vertex $v_i$ into your independent set $I$ if it has no neighbors among the vertices that have been put into $I$ so far. This always leads to a maximal independent set, and it's easy to see that every maximal independent set (including those of maximum size) can be generated this way, by just taking an ordering where evey vertex in the set comes before every vertex not in the set.
This strategy also works for other vertex subset problems like Feedback Vertex Set or Dominating Set. Unfortunately, it is pretty uninteresting and unlikely to give much insight into these problems. It's potentially more interesting when such strategies can be devised for more complex problems like Treewidth.


Are Turing machines more powerful than pushdown automata?

You can't go to the bottom of the stack without "forgetting" the rest of the stack. With a Turing machine you can easily go back and forth on the tape.

This simple task cannot be done with a pushdown transducer (roughly the same thing as the pushdown automata, but that can write things at each step), but can easily be done with a tape:

  Read a string $w$ and then write the string twice: $ww$

If you don't want to hear about transducers, the similar problem is for you: this language is easily recognized by a Turing machine, but not with a pushdown automaton:

$$L = \{ ww \mid w \in Σ^* \}$$

but I think with a transducer you get a grasp of the difference.


Hash multiple integers directly using FNV-1a

It's not equivalent, and I suspect there will be a loss of statistical randomization/mixing.

The core step that offers mixing of the bits is multiplication by FNV_PRIME modulo $2^{32}$.  The original version (operating on bytes) does this once for each byte of the input.  The alternative version (operating on integers) does this once for each integer, i.e., once for each four bytes.  Thus, the alternative version does only one-fourth as many of these mixing operations.

For these reasons, I anticipate that the alternative version will provide poorer mixing of the bits and might offer poorer statistical properties or weaker collision resistance.

For instance, here is one weakness of the alternative version that isn't present in the original version.  Suppose you simultaneously flip the high bit of i and j.  Then it turns out that the output (the hash value) will remain unchanged, with the alternative version.  This is a weakness in a hash function.  The original version doesn't have this weakness: there's no simple set of bit flips you can do to the input that will have a similar effect.  This is a result of the fact that the alternative version only does the multiplication-based mixing one-fourth as much as the original version.

Now, don't take this the wrong way.  This doesn't necessarily mean that the alternative version is flawed or useless.  The alternative version might still be good enough for applications; that will depend on the distribution of integers that you hash and the needs of the particular application.  But you can't make an equivalence argument that it's "just as good" as the original version.


That is an interesting question since there is no proof that one way functions exist. There is a lecture about this from Cornell's Cryptography course by Rafael Pass  which can be found here

To summarize the lecture:

If one way functions exist then $P\neq NP$.
There exists a function $f_{UNIV}$ such that if there exists any one-way function, then $f_{UNIV}$ is a one-way function.  Thus $f_{UNIV}$ can be considered a universal one-way function.
$f_{UNIV}$ works by acting on all Turing machines after $n^2$ steps of execution.  It is defined as

$$f_{UNIV}=M_1^{(|x|^2)}(x)||M_2^{(|x|^2)}(x)||\dots M_{|x|}^{(|x|^2)}(x)$$

where $M_{i}^{(|x|^2)}(x)$ denotes the output of Turing machine $M_i$ on input $x$ right after $|x|^2$ steps of computation.
If a one way function $f$ exists it can be solved by a Turing machine $M$, which will be polynomial solvable by $f_{UNIV}$.

Caution: the construction of $f_{UNIV}$ is in no way practical.  This is about asymptotic complexity, not practical security.


How to resolve a recurrence relation in the form of $T(n) = T(f(n))*T(g(n)) + h(n)$

If you have a recurrence involving only multiplication, take the logarithm:
$$
\log T(n) = \log T(n^2-n) + \log T(n/2).
$$
This converts it into an additive recursion. In your case this is not really a recursion since it defines $T(n^2-n)$ in terms of $T(m)$ for $m < n^2-n$, but not every integer is of the form $n^2-n$.

Regarding your original question, try to relate it somehow to binary trees, which are known to be counted by the Catalan numbers.


Multi-dimensional Knapsack with Minimum Value constraints for Dimensions

Your intuition is right on.  If I understand correctly, when $V_1=\cdots=V_d=0$, then your problem becomes exactly the ordinary knapsack problem.  So, the knapsack problem is a special case of your problem.  That means that your problem is at least as hard as the knapsack problem, i.e., your problem is NP-hard.
You can prove this formally by exhibiting a reduction that converts a knapsack problem to an instance of your problem by setting $V_1=\cdots=V_d=0$; thus any algorithm that can solve your problem can be used to solve the knapsack problem, too.


Proof: Kolmogorov complexity of string concatenation

Kolmogorov complexity = length of shortest program to generate a string. Take the program generating x, add the fixed size code that makes it continue with a second program instead of halting, then add the second program generating y.


Shortest path between 2 vertices using at most K edges using Bellman-Ford

The bellman ford algorithm presents to us the cost of all the shortest paths from a source vertex to all the other vertices . For constructing the path we reconstruct it after the algorithm has terminated and returned to us the cost. We backtrack on our solutions and reconstruct the path so don't get confused if you don't get the correct path at an intermediate step of the algorithm.
(Just for some additional information while coding the algorithm you might have notices the use of an two dimensional array which stores solution at each step . the same is used to reconstruct the path.)

The recursive definition of the algorithm is

$\delta^{k+1}(v) = \min \Big(\delta^{k}(v), ~ \min_{x\in\mathbb{N} - \{v\}} (\delta^k(x) + w(x, v) ) \Big) $

For the example which you have presented

When the edge budget is $0$ :

The shortest path from S to T is $+\infty$.

When the edge Budget is $1$ :

we till have the cost to be $+\infty$.

When the edge budget gets $2$ :

We update the cost of our path to : $7$

When the edge budget is $3$:

We now get the following : $\min ( 7 , \min (6))$

Hence giving the final cost as $6$.


Prove that in an optimal code, if the letter frequencies are increasing, the encoding lengths are monotonically decreasing

I have come up with a solution.

To show that the old $B(A)$ is larger than the new $B(A)$, it is necessary to show that

$$\text{f}(x_1)\times\text{c_len}(x_1) + \text{f}(x_2)\times\text{c_len}(x_2) > \text{f}(x_1)\times\text{c_len}(x_2) + \text{f}(x_2)\times\text{c_len}(x_1)$$

($\text{f}(x)$ = frequency of $x$, $\text{c_len}(x)$ = length of $x$'s encoding.)

By moving terms over and using distributive law:

$$\text{f}(x_1)(\text{c_len}(x_1) - \text{c_len}(x_2)) > \text{f}(x_2)(\text{c_len}(x_1) - \text{c_len}(x_2))$$

Since $\text{c_len}(x_1) < \text{c_len}(x_2)$,
$$\text{c_len}(x_1) - \text{c_len}(x_2) < 0$$

Therefore dividing both sides by $\text{c_len}(x_1) - \text{c_len}(x_2)$ leaves:

$$\text{f}(x_1) < \text{f}(x_2)$$

Which is true as it is a premise.

Correct me if I have made a mistake.


What time complexity is more significant?

You are asking for a practical answer, so you need a practical problem.

State your practical problem. Then examine what would be the effect of using one implementation vs. the other. Based on this examination, you can choose which implementation is more acceptable to you.


What does "prompt collection" mean in the context of memory management?

Do computer scientists use the term "prompt" in this context and, if so, what do they mean by it?

What is meant by prompt, is that it is guaranteed to be deleted and more importantly, destructed, when it goes out of scope. The main point of this, is to take advantage of the mainly-C++-ish paradigm of Resource Acquisition Is Initialization.

Look at the following program in pythonish:

def procedure():
  f = open('path')

  ... #use f

def main():
  procedure()
  #f *might* still be alive here, which means it is hogging a file resource

So, languages like python therefore must supply some manual cleanup methods. One is supposed to call f.close() before leaving procedure(). However, this can be error prone, because of early-return (you must remember to close at every return, and remember this when changing code later; it is very cumbersome) and exception safety (what if somewhere before returning, something throws an exception?, then your f.close();return isn't called at all).

The C++ solution to this is very elegant; when things go out of scope, they are guaranteed to call a destructor. The destructor of a resource object will/should clean up the resource. So you have the following code in C++:

void procedure(){
  std::ofstream f("path");
  ... //do stuff with f
  // we *can* call f.close(), but we don't have to, because f::~() (the destructor) will clean it up, and it is guaranteed to be called when going out of scope.
}

The python solution to this is to use the finally exception block like so:

def procedure():
  f = open('path')
  try:
    ... #use f
  finally:
    f.close()
def main():
  procedure()

Alternatively, there is some syntax sugar for some special resource classes (you can add this to any custom class as well) that accomplishes the same thing:

def procedure():
  with open('path') as f:
    ... #use f
  #f.close() is called once out of "scope" of the with; it is essentially the same as the finally block.
def main():
  procedure()

So it is simply two different paradigms; C++'s concept of the "on-the-stack" objects allows self-cleanup, python and most other languages require manual cleanup, but enjoy garbage collection.

Now, the issue is, pointers don't have destructors; they are essentially POD (plain old data). Therefore, if you want to keep an object around longer, you would allocate it on the heap, and save a pointer to it, but you must manually call the destructor (via delete ptr;), but only when you "know" you are done with it. In many situations, it is hard to know when you are done with a pointer, for example, if it is used in many places ("shared ownership"); therefore a reference counter such as shared_ptr can be used, and the underlying objected that is pointed to will be destructed (the destructor will be called) "promptly" when it goes out of scope, ie. when the last user gets rid of the pointer.

  More concretely, I once studied the behaviour of various OCaml and F# programs and found that they often collect values before they fall out of scope and, therefore, more "promptly" than scope-based reference counting.

This is probably not guaranteed though. A garbage collector can decide to clean things up whenever it wants to, they usually don't take resources other than memory into consideration, and AFAIK, never provide any such guarantees. C++, and the finally blocks provide guarantees of resource cleanup.


Shouldn't every algorithm run in pseudo-polynomial time?

The running time is always considered with respect to the length of the input.

If the input is a natural number $N\in\mathbb{N}$, then the length of the input is $n=\log N$. In that case, running time of $\Theta(N)$ is actually exponential in the length of the input, $n$.

Suppose now that we're dealing with a problem where the input is a collection of $n$ elements. For simplicity, assume each member in the collection can be represented by a constant number of bits, independent of the input. Lets denote this constant by $c$, so the number of bits required to represent this collection is at most $cn$. In that case, if upon receiving a collection with $n$ elements (which is a $cn$ length input) you preform only $O(n)$ operations, then the running time is linear.

When saying the input is a number $N$, or a list of size $n$, we already talk about the semantics of the input (how we intend to interpret the given sequence of bits). You can count the running time in terms of those "interpretations", e.g. $O(N)$ for naive primality testing, or $O(n)$ for finding a maximum in a list, but in the end you have to remember how those objects relate to the actual input's size. If we denote the length of the input by $l$, for primality testing we have $l=\log N$, so $T(l)=N(l)=2^l$, and for finding maximum $T(l)=n(l)=\frac{1}{c}l$.


Can a Turing Machine simulate every possible Turing Machine?

Your conclusion "this Turing Machine must have infinite data on its tape" is not accurate.  Everything up to that point is basically fine, but that one statement is not correct.

Turing machines never have an infinite amount of data on the tape at any one time.  At any point in time, they have a finite amount of data on the tape.  However, this amount might increase over time without limit.  That's not the same as saying that at any point the amount is infinite.

An analogy: imagine I start counting out loud 1, 2, 3, 4, 5, 6, etc., without ever stopping.  At any point in time, the number I said aloud is finite.  However, there is no fixed upper bound on these numbers; they increase without limit.

It's the same with such a Turing machine.  Call this machine $M$.  It simulates all Turing machines in parallel, but crucially, each simulation proceeds at a reduced speed.  $M$ itself will be one of the machines being simulated, but at a reduced speed: say, 1000x slower (just to make up a number).  So, $M$ is simulating $M$ running 1000x slower.  That means it is also recursively simulating $M$ running 1000000x slower, and so on.  (And because the simulated $M$ is running slower, it writes to the tape more slowly, so the size of the tape grows slower.)


The wave is the whole curve: you shouldn't think of your first diagram as showing "four waves" as if you were counting waves from the sea hitting the beach. Although your graphs aren't labelled, the horizontal axis is likely intended to be time, not distance, and the graph shows the oscillation of a single particle over time.  So the dashed line shows the movement of the particle over time: think of it as moving up and down.

The sampling frequency is the number of times per second that you measure the particle's position. In the first diagram, the measurements all happen when the particle is in the same place so sampling at that particular frequency causes you to believe that the particle isn't moving at all (the orange line). In the second diagram, we're sampling $3/2=1.5$ times more often so, now we see the particle in different positions and, in particular, we see that it's not stationary.

Note that the two diagrams are drawn at different scales, which isn't very helpful.


Big O notation question for set insertion with sequential scan?

First of all, let's get some things straight. Big-Oh notation is just a notation for describing the asymptotic behavior of any mathematical function (well, at least those defined on the real numbers). It is not tied to algorithm analysis.

Performing algorithmic analysis on a program $p$ that takes input $x$, you want to find a function $f(n)$ so that, for every input $x$ of size $n$, one has $T(p(x)) \leq f(n)$, where $T(p(x))$ denotes the run-time of a program. That is, we are finding the worst-case bound on the run-time of $p$.

Now, it may very well be the case that

$$T(p(x)) \leq e\times n^{3/2} + 2.73 \log_{\pi} \sqrt n \times + .23432342 $$

However, this is not very useful. It's difficult to conceptualize the growth of this function. That is one reason we use asymptotic bounds (the other being it is often easier to determine the asymptotic behavior than the exact behavior). It is much more approachable to write

$$ T(p(x)) = O(n^{3/2}) $$

Anyway, to answer your question: you'll note here that $p$ is an arbitrary program. You can take that program to be whatever you like, including "insert $n$ elements into the set". No one can tell you what to analyze.


An obvious function is
$$
f(n) = \begin{cases}
n \log n & \text{if $n$ is even}, \\
0 & \text{if $n$ is odd}.
\end{cases}
$$

It's in $O (n \log n)$, it's not in $o (n \log n)$ and not in $\Theta(n \log n)$.

By the way: Every function in $\Theta(f(n)))$ is in $O(f(n))$, just take the larger constant from the $\Theta$ definition. And every function in $o(f(n))$ is also in $O(f(n))$, choose $c = 1$ and make $n$ large enough. But not the other way around.

$O(f(n))$ contains functions that have infinitely many values between $c_1 f(n)$ and $c_2 f(n)$, but also infinitely many small values. So a function $g(n) = f(n)$ for infinitely many $n$, and $g(n) = 0$ for infinitely many $n$ where $f(n) \ne 0$ is in $O (f(n))$, but not in $\Theta(f(n))$ and not in $o (f(n))$.


Your main observation is correct - in order to be able to express all Boolean functions, we need not stick to a certain set of connectives. All we need is a complete set of connectives, which is defined by just this property. There are infinitely many such sets of connectives. One such example is given by NOR (or NAND) and the constant $0$ (or $1$). You can probably do with just one ternary connective, but I'll let you figure that out.

Why are we taught AND, OR and NOT? Because these are familiar and useful. It is also common to define propositional logic using the connectives IMPLIES and NOT. It's just a matter of convenience. It is also a matter of convenience that all usual connectives are nullary, unary and binary - already ternary connectives are more awkward to write, functional notation being necessary.

In general, given a set of connectives, you can define the set of all Boolean functions definable from them. Then you can define the concept of equivalent sets of connectives. For example, XOR and NOT is equivalent to XNOR, and $0$ and NOT is equivalent to $1$ and NOT. You can easily prove that two sets $A,B$ of connectives are equivalent if each connective in $A$ can be expressed using connectives in $B$ and vice versa. You can even define an order relation expressing that one set of connectives is at least as expressive as another set of connectives.

One relevant mathematical area is universal algebra. For an application to computer science, you can have a look at Schaefer's theorem and its modern descendants, which form a very active research area. Another connection to computer science is Reckhow's theorem that shows that every formula written using one complete set of connectives can be rewritten using any other set of connectives with only polynomial blowup, and furthermore proofs in any complete propositional proof system can be converted to any other (with a different set of connectives), again with only polynomial blowup.


Is there a mapping reduction for every two language $A$ and $B$ to some language $C$?

The definition of the reduction is wrong.
We actually need to define two reductions: from $A$ to $C$ and from $B$ to $C$. The reduction from $A$ to $C$ maps $w$ to $0w$. The reduction from $B$ to $C$ maps $w$ to $1w$.


In the Miller-Rabin primality test, for a composite number, why are at least $\frac{3}{4}$ of the bases witnesses of compositeness?

Here are the three tests you're (implicitly) considering:

Fermat: test whether $a^{n-1} \equiv 1 \pmod{n}$
Solovay-Strassen: test whether $a^{(n-1)/2} \equiv \left( \dfrac{a}{n} \right) \pmod{n}$ (where $\left( \dfrac{a}{n} \right)$ is a Jacobi symbol, which can be calculated using quadratic reciprocity via a GCD-like algorithm)
Miller-Rabin: suppose $n-1 = 2^k m$. Test whether the list $a^m,a^{2m},\ldots,a^{2^km} \pmod{n}$ consists of a (possibly empty) string of $-1$s followed by a string of $1$s

Each test is stronger than the previous one: if $a$ passes Fermat's test, it will satisfy Solovay-Strassen, and if it passes Solovay-Strassen then it passes Miller-Rabin. In the first two tests, the set of $a$ which pass the test form a group. Therefore, unless all $a$s pass the test, at most half of them do. For Solovay-Strassen, one can show that if $n$ is composite, then some $a$ (which can be constructed explicitly) doesn't pass the test.

For Miller-Rabin, the argument is more complicated. The most difficult case turns out to be $n = pq$, where $p,q$ are different primes. The argument uses the Chinese Remainder Theorem to consider what happens modulo $p$ and modulo $q$ separately. For $a$ to pass the test, it must behave in exactly the same way under both primes, and that's the intuitive reason that makes it harder to pass the test. For a proof, check Schoof's paper, for example.


Language to Generate Powers of 2 Using a Language Containing Decimal Numbers

L is not context-free
Periodicity for context-free languages of bounded growth: Let $w_n$ be the number of words of length $n$ in a given regular language. If the sequence $w_1, w_2, \cdots$ is bounded (bounded growth), then it is eventually periodic.
Proof: This follows from the fact that every context-free language of bounded growth is a union of paired loops, which is the theorem 2.1 in the paper On a conjecture about slender
context-free languages by Lucian Ilie, 1994.

Let $w_n$ be the number of words of length $n$ in $L$. $w_n=\#\{k\in\Bbb N\mid n-1\le k\log_{10}2 \lt n\}$. Since $\log_{10}2$ is irrational, the sequence $w_1, w_2, \cdots$ cannot be eventually periodic. So $L$ is not context-free. Hence, it is not regular, either.
As rici pointed out, it is not difficult to prove that $L$ is not context free by applying the pumping lemma to any word in $L$ that is long enough. The above more conceptual proof is presented in the hope that it might raise more interest and more questions.
$L$ is context-sensitive
According to rici's comment, we can write a context-sensitive grammar which multiplies a decimal number by two. Use marker tokens which move right to left over the number; you'll need two of them because of the possibility of carry. As with many other cases of context-sensitive grammars, the actual construction might be apt to get lengthy and tricky, sometimes even debatable.
Another conceptual way to see $L$ is context-sensitive is using linear bounded automaton (LBA) that accepts a context-sensitive language. It is easy to see that we can divide by 2 repeatedly using a linear bounded automaton. More specifically, we can design a LBA such that given an input of $S m E$, where $m$ is a sequence of decimal digits and where $S$ and $E$ are start marker and end marker respectively, it will output $S1\square\square\cdots\square E$, where $\square$ stands for the special blank symbol if and only if $m$ is the decimal representation of some power of 2.
An exercise
Let language $L_U$ over $\Sigma=\{0,1,2,3,4,5,6,7,8,9\}$ be the language of words which are positive integers whose prime factors belong to a finite set $U$ of prime numbers when they are treated as decimal numbers. Show that $L_U$ is context-sensitive but not context-free.


In fact, your result is correct and that reference solution is wrong!

Here is where that reference solution goes wrong.

  Since we view the candidate ranking as reading an random permutation, this is equivalent to the probability that a random permutation is a decreasing sequence followed by an increase, followed by another decreasing sequence.

A permutation that leads to hiring of two candidates if and only if the first candidate is not the best candidate and is better than all others candidates that come before the best candidate. There is no requirement of sequences being decreasing or increasing.

(There is a minor typo in your case 2. You meant 3/4 instead of 1/4.)

I would not say your reasoning is fully correct yet, though you have got the correct result, since I have not found a natural way to explain rigorously your way of computing the probability of each case by a product of probabilities. I am even more far away from being certain that your reasoning is wrong. It looks like you shared my feeling as well.

There are better or more rigorous ways to produce the correct result. I will let you think about it.


is determinism = non determinism for one counter automata?

You are right: the language $L$ from your question is accepted by a (nondeterministic) one-counter automaton.

Now for the deterministic case. Counter automata are a special case of push-down automata, where one only uses a single stack symbol (apart from a bottom-of-stack). Every (deterministic) one-counter language is also a (deterministic) push-down language. So in order to demonstrate it is not a deterministic one-counter language, I show a stronger result: it is even not accepted by a deterministic PDA.

According to Ogden, in his paper introducing Ogden's Lemma, that same language $L$ is inherently ambiguous context-free, meaning that every possible context-free grammar for the language is ambiguous, i.e., it has a string with two different succesful derivation trees.
On the other hand, it is known that every deterministic PDA can be transformed into a non-ambiguous CFG. In fact I believe the standard construction PDA to CFG does the trick (but that is not obvious).
Hence as there is no non-ambiguous CF grammar for $L$ (Ogden), there can be no deterministic PDA for $L$, and in particular no deterministic one-counter automaton.

Conclusion: for one-counter automata determinism is less powerful than the general model, using your example.

(In an edit I moved info from comments into this text.)
Reference, see also Wikipedia: Ogden, W. (1968). A helpful result for proving inherent ambiguity. Math. Syst. Theory 2, 191–194.


Finding the dichotomy that maximizes information gain for a classifier?

As in the discussion, there are too many "features" for this to be in interesting question. In particular, letting $A = C^{-1}(1)$, the set of positive examples, then $H(C|A) = H(C|C) = 0$ so information gain is $H(C)$, which is maximal.

This is obvious in retrospect, in order to decrease the entropy maximally, make $C$ deterministic on $A$ and $A^c$.

For decision trees, the point is that we have a limited collection of features, specifically excluding C, to split our data set around.


0/1 Knapsack problem with overlapping items

Calling this a variant of Knapsack is a bit confusing, since it's more like maximum-weight independent set. Bags are nodes, bags that share a type of coin have an edge between them, and the number of coins in each bag is the weight of the node. Going the other way is annoying, translating unweighted MIS into this problem is easy though.

Anyway here's a direct ILP formulation of the coins/bags thing:

maximize sum of take_bag[i] * size[i]
s.t.
∀c: sum[i | c ∈ bag[i]] of take_bag[i] ≤ 1
take_bag[i] ∈ { 0, 1 }

You could use the linear relaxation of that to do branch & bound, which you can stop early when you're happy enough with the gap between the best found solution and the objective value of the linear relaxation. Or check the literature for MWIS solving. There are many approximation algorithms as well.

Taking into account the capacity constraint, the ILP model becomes

maximize sum of take_bag[i] * size[i]
s.t.
∀c: sum[i | c ∈ bag[i]] of take_bag[i] ≤ 1
sum of take_bag[i] * size[i] ≤ W
take_bag[i] ∈ { 0, 1 }


A code is prefix-free if there does not exist any distinct two values v, w such that encode(v) is a prefix of encode(w).  So, to prove that your encoding is prefix-free, you start by considering two arbitrary distinct values v, w and demonstrate that encode(v) is not a prefix of encode(w).

I suggest you use proof by induction on the "size" of the largest value, so you'll consider two arbitrary values v, w that are both of size at most $n$.  In this case, a reasonable choice for the "size" is the number of times the recursion was applied, i.e., the number of cells in the list.  Your inductive predicate $P(n)$ states that for every pair of distinct values v, w both of whose size is at most $n$, encode(v) is not a prefix of encode(w).  You want to prove $P(n)$ for all $n$.  To do that using the principle of induction, you need to prove $P(0)$ and prove $P(n) \implies P(n+1)$.  Here $P(0)$ is trivial, so we can focus on the inductive step $P(n) \implies P(n+1)$.

For your example of the list data structure, that shouldn't be too hard.  You'll just case-split on the size and structure of v, w.  There are four cases:

case (a): v has size $\le n$, w has size $\le n$
case (b): v has size $\le n$, w has size $n+1$
case (c): v has size $n+1$, w has size $\le n$
case (d): v has size $n+1$, w has size $n+1$

Case (a) is already covered by $P(n)$, so you only need to reason about the three other cases.  Each one can be handled by using the induction predicate.

I'll describe how to prove case (d).  You should be able to see how to handle the other cases similarly.  Let a = hd(v) and k = tl(v), so that v == a::k.  Similarly let b = hd(w) and l = tl(w) so that w == b::l.  We can see that

encode(v) == encode(1) <> encode(a) <> encode(k)
encode(w) == encode(1) <> encode(b) <> encode(l)

Now we assumed that v, w are distinct, i.e., v != w.  It follows that either a != b or k != l.  If a != b, the fact that encode is prefix-free on ground terms implies that encode(a) is not a prefix of encode(b), which in turn implies that encode(v) is not a prefix of encode(w).  If a == b and k != l, the inductive hypothesis $P(n)$ implies that encode(k) is not a prefix of encode(l) (since both k and l have size one less than v, w, i.e., size $n$), which in turn implies that encode(v) is not a prefix of encode(w).

Ultimately, once you've handled all four cases, you'll have proven that encode(v) is not a prefix of encode(w) for an arbitrary pair of distinct values v, w of size $n+1$, from which $P(n+1)$ follows.

The same techniques can be applied to any algebraic data types that is formed as a recursive combination of products and co-products.


How to divide a line of numbers into N groups such that the sums of each group are closest to their mean using dynamic programming?

Fortunately you can calculate the group average that you are aiming for (sum of numbers, divided by the number of groups). In your case, you want the groups close to 18 1/3.

So using dynamic programming, you solve "How do I split the first m numbers into n groups, minimizing abs (sum of numbers in group - 18 1/3)", for 0 ≤ m ≤ M, and for 1 ≤ n ≤ N. You solve this by putting 0 ≤ k ≤ m items in the last group, calculating the penalty for the last group and adding the solution for n-1 groups made from the first m-k items, picking the best choice.

It feels a bit weird, because the solutions you find on the way are awfully bad. Splitting the first 0 numbers for example into 3 groups creates 3 empty groups, with a total sum of 3 * (18 1/3) = 55, but it works. What you find for N groups from M numbers is optimal.

This works easily on O (M^2 N). You can do this faster by first finding a reasonably good solution, and then excluding everything that isn't as good as the best solution.

Example: First, make each group as large as possible without the first n groups exceeding n * 18 1/3, that is (1 2 3 4 5) (6 7 8) (9 10) with penalties 3 1/3, 2 2/3, 2/3, total 6 2/3. Now we only care for 1 group with a penalty ≤ 6 2/3, then for 2 groups with a penalty ≤ 6 2/3 etc.

But also, if the remaining M-m items that need to go into N-n groups have a sum of S, they must have a penalty of at least abs (S - 18 2/3 * (N - n)), so the penalty for the first n groups plus this extra penalty must be ≤ 6 2/3. This will help if you have thousands of items.


Overlap between theory and systems fields in CS

I can see a lot of overlap in the field of Cloud Computing or Distributed Computing
- being that it relies heavily on process scheduling and parallel processing on the operating systems side and optimization algorithms to both traverse data across multiple nodes (servers) and optimize hardware resources on the network grid. Graph theory and NP issues come up often when trying to reconcile issues concerning "Big Data" within the distributed computing space.

The software engineering CS component arises when developing designs for new operating system based applications like system monitors that help stabilize and secure distributed computing systems.

From this example, one can see much of the overlapping of said disciplines that go into Cloud Computing.


Proof of Brzozowski's algorithm for DFA minimization?

The proof of Brzozowski's result is technical, but not very complicated.
In fact we only have to consider one sequence of reversal-determinization, to obtain the minimality result we want. (The first sequence of reversal determination leads to a deterministic FSA for the reversal of the original language; the minimality proof is for the second reversal-determinization.)

First one needs some good view of the different automata involved.
And nerves of steel.

The construction of Brzozowski.
Let $A = (Q, \Sigma, \delta, q_0, F)$ be a deterministic automaton for the language $L=L(A)$. We assume that all states of $Q$ are reachable from the initial state $q_0$.

In the first step one reverses the automaton: all edges are inverted, and inital and final states are swapped. Informally we get the automaton $\mathrm{rev}(A) = (Q, \Sigma, \delta^{-1}, F, q_0)$.

In the second step one determinizes the automaton so obtained, by the standard construction, but keeping only reachable states. We get $A'= \mathrm{det}(\mathrm{rev}(A)) = (Q', \Sigma, \delta', q'_0, F')$.
The states of $A'$ are sets of states for $\mathrm{rev}(A)$: $Q'\subseteq 2^Q$;
the initial state consists of the initial states for $\mathrm{rev}(A)$, which are final states in $Q$: $q'_0 = F$;
the final states in $A'$ are the states that contain a final state for $\mathrm{rev}(A)$: $U\in F'$ iff $q_0\in U$.

The key of the proof is the following important relation between automata $A$ and $A'$.

  Basic Observation: $q\in \delta'(X,w^R)$ iff $\delta(q,w) \in X$.

Proof (one side only). $q\in \delta'(X,w^R)$ iff there exists a state $p$ in $X$ and a path from $p$ to $q$ in $\mathrm{rev}(A)$ with label $w^R$. But that means there is a path from $q$ to $p$ with label $w$ in $A$, or $\delta(q,w) = p$; thus $\delta(q,w) \in X$. end-of-proof.

As announced, this is used to prove the essential property we need.

  Property: $A'$ is minimal (and deterministic for $L^R$).

Proof. Let $U$ and $V$ be two states in $A'$ that cannot be distinguished. This means that for any string $w^R$ we have $\delta'(U,w^R) \in F'$ iff $\delta'(V,w^R) \in F'$. We show that now $U$ and $V$ are equal.

By the construction of $F'$ we can rephrase indistinguishability as $\delta'(U,w^R) \ni q_0$ iff $\delta'(V,w^R) \ni q_0$.

Apply the Basic Observation, and we have $\delta(q_0,w) \in U$ iff $\delta(q_0,w) \in V$.

From this equality $U=V$ follows, as all states in $Q$ are assumed to be reachable, thus for any state $p$ in $U$ or $V$ there is a string $w$ such that $p = \delta(q_0,w)$.
end-of-proof.

But even after proving, the result is still real magic!


NP ≠ NP hard.

NP means: For every perfect number, there is a certificate that lets you prove in polynomial time that it is perfect.

And that is clearly the case. For every perfect number, I can give you the factorisation, plus for all large prime factors a proof that these large factors are primes, and then you can quite easily check that the number is perfect.

NP hard means: If you can solve this problem, then you can solve any problem in NP. I don't see this. Especially since perfect numbers are so rare. (Why does it make it unlikely that this is NP hard? Polynomial time reduction means: If you take a problem in NP, then for any instance with answer "Yes" there is a perfect number so that the fact that this number is perfect proves the answer to your problem is "Yes". For different instances I'd expect different perfect numbers to be needed. But there are so few known...)


Regular expression for a palindrome of finite length?

Sticking $w$ with its reverse together usually is not a regular language and therefore there is no natural concise way to represent that using regular expressions (at least to my knowledge)

Im not really sure why you would like to find a regular expression for this language, since - as you have stated - this language is finite, and therefore regular (if you want a proof for this claim, it is here)


Trapdoor functions that depends only on NP-hard?

The crux of the problem lies in worst to average case reductions. The standard construction of a function which is average case hard is taking a function which is worst case hard and applying all kinds of fancy error correcting codes on its truth table. See Ta-Shma's notes sketching the STV construction. As far as I know, we don't know how to do that for NP (STV starts with a PSPACE hard function).
Even worse, we believe this can't be done for NP. See Bogdanov Trevisan, where it is shown that if an NP complete problem has a worst to average case reduction then the hierarchy collapses. Your problem is not exactly worst to average case reduction, but reducing an NP hard problem to inverting a one way function. However, these are related and Trevisan's paper also rules out such non-adaptive reductions.
More directly related to your question is AGGM, which also rules out adaptive reductions for the case where the size of the inverse image is easy to compute. You might also want to check out this paper. These results are 10-15 years old (STV is around 20), I have no idea if anything stronger was proven since.


Running time function for an algorithm with while and for loop

For each value of $i$, the inner loop runs $i$ times, and so the running time of the body of the outer loop with a given value i is in $\Theta(i)$. The values of i, as you mention, are $n, \lfloor n/2 \rfloor, \lfloor n/4 \rfloor, \cdots, 1$, and so the overall running time is
$$ \Theta(n + n/2 + n/4 + \cdots + 1) = \Theta(n). $$
Here we use the fact that the infinite series $1 + 1/2 + 1/4 + \cdots$ converges (to $2$).


Can other models of computation equivalent to Turing machines also recognize the same languages?

Two models of computation are equivalent iff they can compute exactly the same set of functions. So the answer to your question is yes, they can recognize the same languages. The definition of "accept" has to be altered a bit to fit the new model, of course, since for example in the lambda calculus you have no states that you could mark as accepting.


Assuming that you mean the usual bin packing problem, your question is answered on Wikipedia, on the page on strong NP-completeness.

A problem is strongly NP-complete exactly when it remains NP-complete even when the weights are assumed to be of polynomial size (this is not an informal definition, so this should be regarded as an informal notion). Another way to put this is that the problem remains NP-complete even when weights are encoded in unary (the two formulations might not be formally equivalent, but they are morally equivalent). Bin packing is one of the standard examples of a strongly NP-complete problem.


When are two simulations not a bisimulation?

Because a CCS process is worth a thousand pixels – and it is easy to see the underlying LTS – here are two processes that simulates each other but are not bisimilar:

$$P = ab + a$$
$$Q = ab$$

$\mathcal{R_1}=\{(ab+a, ab), (b, b), (0,b), (0, 0)\}$ is a simulation.

$\mathcal{R_2}=\{(ab, ab+a), (b, b), (0,0)\}$ is a simulation.

$P\ \mathcal R_1\ Q$ and $Q\ \mathcal R_2\ P$ but $P$ and $Q$ are not bisimilar. Why not? Because $P\stackrel{a}→0$ and the only $Q'$ such that $Q\stackrel{a}→Q'$ is $b$ ... and $0$ is not bisimilar to $b$.

Why can they simulate each other, then? Because $P$ simulates $Q$ since it can do everything $Q$ does. And $Q$ simulates $P$ because even if $P$ can go in one $a$-step to a program that does nothing, $Q$ can still do that $a$-step, and that's all it takes to simulate something. The key difference with the bisimulation is really that, as Charles said, you have to relate the same processes with both simulations. (i.e. $\mathcal R$ such that both $\mathcal R$ and $\mathcal R^{-1}$ are simulations)


Number of spanning arborescences with a specific root in a directed graph

It seems that Kirchhoff's theorem can be used:

Kirchhoff's theorem can be modified to count the number of oriented spanning trees in directed multigraphs. The matrix Q is constructed as follows:
The entry i, j for distinct i and j equals −m, where m is the number of edges from i to j;
The entry i, i equals the indegree of i minus the number of loops at i.
The number of oriented spanning trees rooted at a vertex i is the determinant of the matrix gotten by removing the i-th row and column of Q.


Proving that $f(n) = o(g(n))$ implies $2^{f(n)} = o(2^{g(n)})$

Hint:

We want to prove $2^{f(n)} = o(2^{g(n)})$. This is equivalent to $\lim_{n\to\infty} \dfrac{2^{f(n)}}{2^{g(n)}} = 0$.
We can rewrite the expression inside the limit as $2^{f(n)-g(n)}$, and, exploiting the hypothesis $f(n) = o(g(n))$, we have $\lim_{n\to\infty} f(n)-g(n) = \cdots$


Intuitively speaking, a non-terminating program needs either:

a combinator such as $Y$ which, when applied, reduces to a larger expression containing itself;
or two combinators such as $S$ which, when applied, replicate at least one of their arguments: one to do the initial replication and one to be replicated.

Unlambda lacks a combinator of the first type, but has two combinators of the second type: $S$ and $C$.

In the SKI-calculus, following the intuition above, a non-terminating term needs to somehow apply $S$ with the first argument being $S$. So it would have to be of the form $Swx(Syz)$, i.e. ```swx``syz in Unlambda). This suggests that $SII(SII)$ is minimal. (Note that I've only given an intuition, I haven't proved it!)

However Unlambda also includes c (call/cc), and this is a very powerful operator in terms of replicating its argument. A term of the form $Cfx$ applies its own continuation $\phi$ to the function $f$; if $f \phi$ itself arranges not to destroy its context, then the term won't terminate. For example, $CI(CI)$ is non-terminating (exercise: work it out). ``ci`ci is known as the Yin-Yang puzzle. To see it in action, make it print a trace of its execution: ``.@`ci`.*`ci.

Because $S$ requires 3 arguments and $C$ requires 2, intuitively, there can't be a non-terminating 3-combinator term, so the 4-combinator term we found above is minimal.

Here's a quick-and-dirty bash script that enumerates all possible Unlambda terms of up to 4 combinators (i.e. 3 application nodes) and prints out the ones that take more than 1 second to terminate. I omitted the I/O primitives which reduce like i, as well as e (exit) which obviously wouldn't help to make a program non-terminating. This is an experimental way to list the non-terminating terms — the terms not printed here are guaranteed to be terminating (assuming a correct implementation), and the terms printed here are likely to be non-terminating.

for a in s k i c d v; do
  for b in s k i c d v; do
    for c in s k i c d v; do
      for d in s k i c d v; do
        for p in @$a$b @@$a$b$c @$a@$b$c @@@$a$b$c$d @@$a@$b$c$d @@$a$b@$c$d @$a@@$b$c$d @$a@$b@$c$d; do
          p=${p//\@/\`}
              timeout 1 unlambda <<<$p || echo $p
        done
      done
    done
  done
done

The result of the experiment is that only the following terms are potentially non-terminating:

```scc?
``c?`c?

where each ? can be independently i, c or d. In other words, the non-terminating combinator terms are $SCCx$ and $Cx(Cy)$ (or so the experiment suggests, but it happens to be correct).

Exercises:

Work out the reductions for these terms and check that they are indeed non-terminating. Do they loop or do they grow forever?
Prove that all smaller terms terminate. (I don't think there's anything more interesting than a long case enumeration.)
How does $SCCI$ relate with my intuition above concerning the minimum content of a non-terminating term — the $S$ replicates only $I$?
Prove or disprove that there is no smaller non-terminating SKI term than $SII(SII)$. Are there others of the same size?


If $A$ is computable and $B$ is any nontrivial language (that is, $B \neq \emptyset,\Sigma^*$) then $A \leq_m B$. Indeed, pick $x \in B$ and $y \notin B$, and construct a computable reduction which decides whether its input is in $A$ or not, and outputs $x$ or $y$ accordingly.

Another issue you seem to be confused about is the meaning of context-free. The fact that a language is context-free doesn't preclude it from being regular. On the contrary, all regular languages are context-free.


What is the relation between word size and size of internal register of a processor?

The term "word size" is defined in different ways by different sources, but almost everybody agrees that it is architecture dependent.

In the definition you quote: "number of bits processed by a computer's CPU in one go" it is not clear what "processed" refers to.

(Sorry about using ancient example, but I have not really looked at hardware specs for ages)

For example: The 486DX processor can add 32 bit integers for a 32-bit result (plus carry).  It can multiply 32 bit integers for a 64-bit result.  It can add or multiply 80-bit floating-point numbers for 80-bit results.

It has 32-bit integer registers and 80-bit floating-point registers.  The 64-bit int multiplication stores in result in two registers.

I won't even start on the various physical and virtual memory address sizes.

The integer multiply instruction 32x32 -> 64 is an oddity, most integer instructions can only process 32 bits.

Now, what is the word size?

It all depends on your definition.


Polynomial time optimisation algorithm for a poly-time computable function with bounded number of maxima?

Hint: Consider a function that is increasing, except in the small interval $[a,a+\varepsilon]$, where it decreases slowly.  Assume $\varepsilon>0$ is very small and the value $a$ is not known a priori.  Can you find the maxima in polynomial time?


Is there a CPU architecture which allows early register access?

You are describing pipeline forwarding for data hazards. Here is a wikipedia article about it:
https://en.wikipedia.org/wiki/Operand_forwarding

This is a common feature of in-order processors (such as MIPS32). Since they are not operating out-of-order, the data hazard detection logic detects that the result will not be available during the clock cycle immediately after the instruction executes. The pipeline scheduling logic could either stall the pipeline or forward the result from the arithmetic unit (e.g., the multiplier) directly into where the next instruction would expect the result (e.g., one of the inputs to the ALU for example).

The compiler isn't required to be aware of this feature, however, in some scenarios it can optimize for these types of architecture features.

I won't say it is impossible or even say it isn't performed, but doing this in an out-of-order processor is much harder because the instruction window is tracking dependencies of each instruction via register indices. The control logic for the instruction window is significantly more complex if it is allowed to detect all possible data hazards opportunistically.


Is this problem a variant of TSP problem? if not, what is it called?

TSP assumes you go through a hamiltonian path.

This problem looks more like a simple a path search with some added restrictions and it's solvable with A*.


I'm not sure what you mean by "all relations are inverted" (what's the relation of a tree?), but perhaps I can provide some insight.

In Haskell, one might write the type of binary trees as such:

data Tree = Leaf | Node Tree Tree

in the terminology of the paper, the type of "incomplete trees" would then be

data ITree a = Leaf | Node ITree ITree | Var a

allowing for an "incomplete" tree with holes marked by an instance of Var a. The paper observes that the type ITree a forms a monad, where a Var a can be "substituted" with f a given a suitable function f :: a -> ITree b.

Now our intuition is that the type Tree is the type of finite, or well-founded binary trees, of which an example is

 myTree :: Tree
 myTree = Node (Node Leaf Leaf) (Node Leaf Leaf)

However, it is untrue in a language like Haskell that all trees are of this form. Indeed, following definition is perfectly acceptable:

infTree :: Tree
infTree = Node infTree infTree

intuitively, this tree represents the infinite "full" binary tree. So really the type Tree may contain either finite binary trees, or trees which may contain infinite paths. Such trees are called non-well founded trees.

So, in Haskell, the type Tree is in reality the type of co-trees, which allows such elements as infTree. This may be a bit confusing, since we rarely think about such elements when considering that type.

Hopefully this provides useful intuition.

The main observation of the paper, is that the type of co-trees has a construction dual to that if ITree, which one might call DTree, defined as

 DTree a = DLeaf a | DNode a (DTree a) (DTree a)

such that we can define a comonad structure:

extract :: DTree a -> a
extract (DLeaf a) = a
extract (DNode a _ _) = a

duplicate :: DTree a -> DTree (DTree a)
duplicate (DLeaf a) = DLeaf (DLeaf a)
duplicate (DNode a l r) = DNode (DNode a l r) (duplicate l) (duplicate r)

The paper goes on to explain some intuition about this structure and why it should be considered as interesting.

Oh by the way, the paper you are reading seems pretty heavy in abstract nonsense, and if you're coming from the CS side of things, you might want to take a look at these blog posts first:

https://bartoszmilewski.com/2013/06/10/understanding-f-algebras/

http://5outh.blogspot.com/2013/01/comonads.html


Is running AES NI in parallel possible (one encryption per core/thread)?

It depends mostly on the memory bandwidth. Each core contains the dedicated AES hardware, but the CPUs need to obtain the data to encrypt or decrypt somehow. Even with a single core you have to be careful about how you dispatch instructions to get maximal performance, see Intel's white paper, page 48 bottom.

If you already have the machine, you can always try it out and let us know how it went.


How to create an algorithm when given the invariant

Observations:

For $i=0$, you don't know anything about the array.
For $i=n$, the array is sorted.

So the idea is to go from $i=0$ to $n$ while maintaining the invariant. This is similar to an inductive proof; in fact, you'll get an inductive algorithm.

Start with the input array and $i=0$; clearly, the invariant is maintained.
For some $i \geq 0$, assume that the invariant holds. What do you do to ensure the invariant holds for $i+1$?

I'll let you take it from here.


can virtual address map any on virtual memory on disk?

My question is, does each page tabe entry(PTE) need to be match the same offset one in disk?

No. They can map to anywhere in physical memory and they can map to anywhere on the disk. If they had to map to the same offset, there would be no point using virtual memory.


interval scheduling variant: 1 machine with 2 tasks need to complete only

Let $max$ be the maximum period of the tasks we have checked so far. Let $max2$ be the maximum sum of two non-overlapping tasks we have checked so far. Both of them are 0 initially.

Sort all start times and end times of the given tasks. Iterate over them, from the smallest to largest.

A start time is encountered. If the sum of the period of the corresponding task and $max$ is greater than $max2$, update $max2$.
An end time is encountered. If the period of the corresponding task is greater than $max$, update $max$.

Now $max2$ is what we wanted. The algorithm runs in $O(n\log n)$.

The above algorithm does not specify what to do when multiple times are encountered at the same time. That part should be easy for you to fill in.


For a cycle with $n$ vertices, how many distinct chords are possible?

A chord consists of a vertex $i$ and a different nonadjacent vertex $j$. There are $n$ options for $i$, and $n-3$ options for $j$ (since we can't choose $i$ or any of its two adjacent vertices). Since we can switch $i,j$ and get the same chord, we have to divide by 2. Overall, we get that the number of chords is $$ \frac{n(n-3)}{2}. $$
When $n=3,4,5,6$, this gives $0,2,5,9$, matching your values.


Is every subset of a RE language also RE, in general?

No, it is not true that every subset of a recursively enumerable (RE) language is also RE. In fact, it make sense to say that a subset of a RE language is not RE more often than not.

For an example, let us consider the RE language, $\Sigma^*$ that contains all words. It is the language of the Turing machine which always halts and accepts in its first step. Note that every language is a subset of $\Sigma^*$. Every language that is not RE is an example.

Here are a few exercises for you to check.

Exercise 1. Is every subset of a regular language regular?

Exercise 2. Is every subset of a context-free language context-free?

Exercise 3. Is every subset of a recursive language recursive?


Is this algorithm actually a graph-traversal algorithm?

There seems to be a bug in the first algorithm which is fixed in the second algorithm, namely the first EXPLORE explores only the starting vertex and its neighbors, but nothing beyond that. However, the first algorithm at least explores the entire graph; the second one only explores the connected component of $s$. The second one also doesn't bother to initialize the array visited.

I strongly suggest that you try and understand what these algorithms are doing. It could help running them manually on a few examples. You could also program them and have the programs print out the actions performed by the algorithms.


How to Optimise my Time Optimisation Algorithm

You're trying to solve a knapsack problem – you're trying to choose items of maximum value, given a constraint on their total size. These problems are NP-complete but can be solved reasonably efficiently in practice. The standard technique is to use dynamic programming. This gives a solution in time polynomial in $N$ and $T$. This is still, technically, an exponential-time algorithm (since an input of length $\ell$ could give $T$ as large as $2^\ell$) but it works well in practice.

I won't give details of how to do the dynamic programming, since knapsack is one of the standard examples of the technique so it's easy to find the details online and in textbooks.


In C++ how does "sizeof(array)/sizeof(array[0])" give the number of elements in an array? Why isn't it affected by the length of each element?

C and C++ are low-level languages that give the programmer precise control over the memory layout. Each object takes a constant amount of memory which is fully determined (on a given implementation) by its type. The sizeof operator lets programs know this size.
An object may contain pointers. The data that the pointers points to, if any, is not part of the object. The size of an object is what some higher-level language might call the “shallow” size: it only considers the object itself, not other objects that the object references.
For example, an object of type std::string has a certain size. This size is independent of the content of the string. This means that the only way to implement std::string for strings of unbounded length is for the std::string object to contain a pointer to the actual content of the string. sizeof(std::string) is the size of this pointer plus other data that the std::string type keeps track of (that would typically be the length of the string, the size allocated for the string, a pointer to the class's method table). It has no relation with the length of the string.
An array is an object which consists of several objects of the same type. Since the elements of the array all have the same type, they all have the same size.


set with maximum sum consisting of mutually co-prime numbers

Project Euler asks you to solve the problems yourself, without help. So dont read on if you want to submit a solution for Project Euler; that would be cheating.

Since the numbers are mutually co-prime, each prime number p is a factor of at most one element of S. On the other hand, if p is small enough then a number could have a factor $p^2$, $p^3$, $p^4$ and so on. We also know that every prime number p ≤ N is used (if p is not used as a factor of any number in the set then we just add p). And don't forget to include the number 1 in the set S :-)

A number x ≤ N cannot have two prime factors greater than $N^{1/2}$. Therefore the set S contains among other numbers one number $x_p$ ≤ N which is a multiple of a prime $p > N^{1/2}$. That's a good start for finding the optimal set S. We then take the primes $q ≤ N^{1/2}$, and either multiply one of the numbers $x_p$ by a power of q, or we add a new number $x_q$ which is some power of q.

In the Project Euler project with N = 200,000, there are fewer than 90 primes $q ≤ N^{1/2}$. We can take each of these primes q in turn, and either multiply one of the existing $x_p$ by a power of q, or add a new number $x_q$. We would try to do this achieving the highest possible increase in the sum. If no two q, q' achieve the highest increase in the same way, we can pick the optimal way for each.

In the example N = 30, we would start with $x_p$ = 7, 11, 13, 17, 19, 23, 29. We can use q = 2 to change 7 -> 28. q = 3 -> 27, q = 5 -> 25. The gains are 21, 27, 25. Each gain is > N/2. So an optimal solution cannot include a number created by two or more of the q's - that number would be ≤ N, but we would give up two gains > N/2, so this wouldn't be optimal. So in the simple example, we multiply 7 by $2^2$ and add $3^3$ and $5^2$.

With N = 100, we would have $x_p$ = 11, 13, 17, 19, 23, ... and q = 2, 3, 5, 7. q = 2: 11 -> 88 gains 77. q = 3: 11 -> 99 gains 88. q = 5: 19 -> 95 gains 76. q = 7: 13 -> 91 gains 78. Unfortunately we have a conflict; q = 2 and q = 3 would both use $x_{11}$. If we use 11->88 (gain 77), then q = 3: 31->93 with a gain of 62; total gain 139. If we use 11->99 (gain 88) then q = 2: 23->92 (gain 69) has a total gain of 157. So optimal for N = 100 is

S = { 1, 99, 91, 17, 95, 92, 29, 31, 37, 41, ,,, }

So here is the algorithm: Start with $x_p$ = primes > $N^{1/2}$. Find the primes $q ≤ N^{1/2}$. For each q, find the maximum gain that can be achieved using q: Either $q^k$ by adding the number $q^k$, or $p * (q^k - 1)$ by multiplying $x_p$ by $q^k$. If each optimal gain is achieved in a different way, and each gain is ≥ N/2, then we found the optimal solution.

Otherwise, we choose one set of q's that use the same $x_p$. For each of these q's: We assume that this q uses $x_p$, find the optimal solution under the restriction that no other q uses this $x_p$, and choose which q using $x_p$ gives the best total.

If there is a case where the two smallest gains add up to less than N, ask someone for a more complex solution :-)


Confused about constructing the "failure table" in Knuth-Morris-Pratt algorithm

A proper prefix, which is also a suffix of the same string, is usually called border.

The condition you're asking about basically says this:

If $W[1..i-1]$ has a border of length $j$ and $W[j+1] = W[i]$, then $W[1..i]$ has a border of length $j+1$.
If $W[1..i-1]$ has no border of length $j$ such that $W[j+1] = W[i]$, then the length of the maximal border of $W[1..i]$ is $0$.

Both points follow directly from definition of string equality and definition of borders.

What you need to prove is that the while-loop indeed enumerates all possible borders in descending order.


simple uniform hashing: unclear definition of probability

First, the outcome of a situation being deterministic doesn't mean we will necessarily assign a probability of $1$ or $0$ to it. If I say I'm going to flip a coin, but it is actually a double-sided coin meaning both sides are heads or both sides are tails, the probability that it comes up heads is still $0.5$. Indeed, with respect to classical mechanics, the outcome of a normal coin flip is a deterministic function of the state of the universe, and even quantum mechanics would at best predict near certainty of the classical outcome. But you are correct, that if we knew $h$ and $k$ and $\ell$, then $h(k)=\ell$ would be either a logical tautology or a logical contradiction, and thus of probability $1$ or $0$ respectively.

We could consider any of $h$, $k$, or $\ell$ to be random variables, but the most natural choice would be $k$. I'll write $K$ for the random variable of the keys and reserve $k$ for some particular key. We have $$P(h(K)=\ell)=P(K\in h^{-1}(\ell)) = \mu_K(h^{-1}(\ell))$$ where $\mu_K$ is the probability measure corresponding to $K$. The simple uniform hashing assumption (SUHA) states that $$\mu_K(h^{-1}(\ell))=\frac{1}{m}$$ for every $\ell\in\{0,\dots,m-1\}$. This is simply a constraint on the probability measure $\mu_K$. There is no assumption that $K$ is "uniformly distributed" in any (other) sense. $K$ could be wildly "non-uniform" and still satisfy SUHA. Indeed, it would have to be for some hash functions, $h$.

For example, let's say $m=2$ and $h^{-1}(0)=\{k_0\}$ and thus $h^{-1}(1)=X\setminus \{k_0\}$ where $X$ is the domain of $h$. Let's further say $|X|=101$. Then for this $h$ to satisfy SUHA, it must be the case that $P(K=k_0)=\frac{1}{2}$. For $k\in X\setminus \{k_0\}$, it could be the case that there's a $k_1\in X\setminus \{k_0\}$ such that $P(K=k_1)=\frac{1}{2}$ and thus if $k\neq k_1$ then $P(K=k)=0$. Or maybe, $P(K=k)=\frac{1}{200}$ for any $k\in X\setminus \{k_0\}$. In fact, any distribution over the elements of $X\setminus \{k_0\}$ that sums to $\frac{1}{2}$ will suffice.

Typically, we would specify a distribution for $K$ and then SUHA would constrain what $h$ could be. The point is that the hash function is "well matched" to the distribution of keys whatever that is. There is no sense in stating a hash function satisfies SUHA without specifying the distribution of keys, but we can say a pair of a hash function and a distribution of keys satisfy SUHA while giving the details of neither. This is all that is needed to prove many results about hashing. We don't want to limit ourselves to only talking about "uniformly" distributed keys. A hash table will still gave the same performance guarantees for "non-uniformly" distributed keys as long as the hash function is chosen to "compensate" for the "non-uniform" distribution, i.e. to satisfy SUHA.


Changing a complete undecidable turing machine language

Well, lets start with your $L$ first. Claim: $L$ is undecidable.#

Clear: $L$ is not empty (there exist TM that accept that input) and not trvial (there exist a input w on some $M$ where $w \notin L(M)$ by definition of $L$. Thus, $L$ ist not trival and no property of $M$, so by Rice'S Theorem $L$ is not decidable.

For your $L^C$ the argumentation is basically the same, it is also undecidable.

To make a language r.e (recursive enumerable), in your terms co-recognizable we need a aditional property:

Termination properties of your TM
For the recursive languages, we need this also, because REC is a subclass of RE.

A language $L$ is r.e. iff. for each $w \in L$ there exists a TM M, such that M halts and accepts. For recursive language you need more, here the TM must even halt and decline the input if it is not part of the language.

A recursive language would be:

$L_{rec} = \{<M> |$ for each input $w$ M halts and accepts, if $w = 101$, otherwise M halts and declines. $\}$

EDIT: Language is not reursive (but r.e). If $L_{rec}$ would be recursive, it would be co-recognizable.
Given a word $x = <U>w$ (coding of U and input word w for U). Chose $U$ as a TM that never halts and $w=101$.

Assume there exists a TM $M$ which could compute that $<U>w \notin L_{rec}$. That is if $U$ does not halt. So, $M$ has to know if $U$ halts and thus never halts (it always waits for U to stop). A contradiction.

I will let this answer stay here to clarify the pitfall between decidability and recognizability. Recognizablity is a weaker property of a language then decidability.


How to use Parallel Semaphores for Dining Philosophers Problem

Assume we have 4 processes p[0], p[1],...,p[3] and 4 mutexes m[0],m[1],...m[3]. Now in order to solve the dining philosophers problem, we only need to make one of the philosopher (one of the processes) to take the folk (one of the mutexes) in reverse direction than the other philosophers. Note that by doing this, we are trying to avoid deadlock.

So in practice, we need to make all processes to follow certain implementation, except one.
All processes (philosophers) should follow this implementation:
while(1)
{
   down(m[(i+1) % 4]);
   down(m[i]);

   'critical section'

   up(m[i]);
   up(m[(i+1)%4]);
}

except one process should follow this:
while(1)
{
   down(m[i]);
   down(m[(i+1) % 4]);

   'critical section'

   up(m[i]);
   up(m[(i+1)%4]);
}

Note by down we mean taking the folks and by up we mean releasing the folks, and note how both implementations differ. For example, we made one of the philosopher to take the fort (down) in reverse order than the others.
I hope this could help.


What is the complexity of Array[n] and Object.value

If you have CPython in mind then yes, the both are $O(1)$.
To get array by index the address is calculated as pointer to first element + index * size of element, and for object, which uses struct it is pointer to struct + offset, where offset is calculated at compilation.

The general runtime of operations depends solely on data structure used internally by given implementation of language (please note that language itself might not indicate what structure must be used and the very same language might have different structures using different vendors). It may be offset table, hash table, balanced tree etc.


Given CFG generates all words with equally many 0s and 1s

One direction is easy. To prove that $L(G) \subseteq L$, we prove by induction on the length of the derivation that every word generated by $G$ has an equal number of 0s and 1s. This amounts to proving the following statements:

$\epsilon \in L$.
If $x,y \in L$ then $xy \in L$.
If $x \in L$ then $0x1,1x0 \in L$.

The other direction, proving that $L \subseteq L(G)$, is more challenging. We have to show that every word in $L$ is generated by $L(G)$. The proof is by induction on the length of the word. The base case, which is the empty word, is easy. Now consider any non-empty words $w = \sigma_1 \ldots \sigma_n \in L$. Let $\delta(i) = \#_1(\sigma_1 \ldots \sigma_i) - \#_0(\sigma_1 \ldots \sigma_i)$. The sequence
$$ \delta(0), \ldots, \delta(n) $$
starts and ends with $0$, and each element differs from the preceding one by $\pm 1$. Suppose that $\delta(1) = 1$, hence $\sigma_1 = 1$. Let $i$ be the minimal index $i > 0$ such that $\delta(i) = 0$ (such an index exists since $\delta(n) = 0$). Then $\delta(i-1) = 1$, hence $\sigma_i = 0$. You can check that $x = w_2 \ldots w_{i-1}$ and $y = w_{i+1} \ldots w_n$ are both in $L$. By induction, $S \Rightarrow^* x,y$. Therefore $$S \Rightarrow SS \Rightarrow 1S0S \Rightarrow^* 0x1y = w.$$
If $\delta(1) = -1$ then instead we use the rule $S \Rightarrow 0S1$.


Why are struct and class essentially the same in C++?

Bjarne Stroustrup writes in his The Design and Evolution of C++ book (item 3.5.1):

  At this point, the object model becomes real in the sense that an object is more
  than the simple aggregation of the data members of a class. An object of a C++ class with a virtual function is a fundamentally different beast from a simple C struct.
  Then why did I not at this point choose to make structs and classes different notions?

  My intent was to have a single concept: a single set of layout rules, a single set of lookup rules, a single set of resolution rules, etc. Maybe we could have lived with
  two sets of rules, but a single concept provides a smoother integration of features and
  simpler implementations. I was convinced that if struct came to mean "C and compatibility" to users and class to mean "C++ and advanced features" the community would fall into two distinct camps that would soon stop communicating. Being able to use as many or as few language features as needed when designing a class was an important idea to me. Only a single concept would support my ideas of a smooth and gradual transition from "traditional  C-style  programming," through  data abstraction, to object-oriented programming. Only a single concept would support the notion of "you only pay for what you use" ideal.

  In retrospect, I think these notions have been very important for C++'s success as a practical tool. Over the years, just about everybody has had some kind of expensive idea that could be implemented "for classes only," leaving low overhead and low features to structs. I think the idea of keeping struct and class the same concept saved us from classes supporting an expensive, diverse, and rather different set of features than we have now. In other words, the "a struct is a class" notion is what has stopped C++ from drifting into becoming a much higher-level language with
  a disconnected low-level subset. Some would have preferred that to happen.


Addition modulo 2 notation (Quantum Computing)

The definition shows how $U$ is defined on the standard basis (that is, when $\psi$ and $\phi$ are pure states). You can extend it to general states in a linear way.

Two more comments:

$\psi$ could be one qubit, but it could also be longer.
$f$ is probably a deterministic function.


Unrecognizable languages relationship to NP-hard languages

There are NP-hard languages arbitrarily high in the arithmetical hierarchy.

To answer your specific question, the complement of the halting problem is NP-hard and it's in $\mathrm{coRE}\setminus\mathrm{R}$. To see this, let $M$ be a Turing machine that tries all variable assignments for a $\mathrm{SAT}$ instance.  Let it loop forever if it finds a satisfying assignment and let it halt if it doesn't, or if the input isn't a valid encoding of a $\mathrm{SAT}$ instance.  Now, for any string $x$, $x\in\mathrm{SAT}$ iff $\langle M\rangle,x\in\overline{\mathrm{HALT}}$ so we have a reduction from $\mathrm{SAT}$ to the complement of the halting problem.


how to understand the occurrences of free variables?

A possible definition (From Lambda-Calculus and Combinators):

  Definition 1.11 (Free and bound variables) An occurrence of a variable
  $x$ in a term $P$ is called:

  bound if it is in the scope of a $\lambda x$ in $P$
  bound and binding, iff it is the $x$ in $\lambda x$
  free otherwise

Let's define the set of free variables $FV$:

The free variables of $x$ are just $x$, that is $FV(x) = \{x\}$
$FV(\lambda x. P) = FV(P) \setminus \{x\}$ (since $x$ is bound)
$FV(st) = FV(s) \cup FV(t) $

And maybe you just need some examples:

$y$ is free in $y$
$x$ is free in $(\lambda x.x)x$ (Try to work out why)
$y$ is free in $(yy)$.


By definition, for every Turing machine $M$, $L(M) \in \mathsf{RE}$. Therefore your language can be rewritten as
$$
\{ \langle M_1 \rangle \langle M_2 \rangle : M_1,M_2 \text{ Turing machines} \}.
$$
This obviates some of the steps in your oddly named machine $M_{12}$.


Why/how does the definition of PCP use randomness?

The way a PCP works is like so: in order to verify some property, the prover presents a proof P which is "easily testable". The way to test it is to query the proof at a small number $q(n)$ of points. We want the PCP to satisfy two properties:

If the property actually holds, the verifier should always (or almost always) accept.
If the property doesn't hold, then the verifier would notice with some constant probability.

Now if the proof is long and the verifier only looks at a small number $q(n)$ of them, then they better be random! Otherwise it's very easy to fool the verifier. That should answer your first and third questions.

How are the random coins used? In an arbitrary way. The verifier chooses $r(n)$ random coins, and based on them queries the proof at $q(n)$ points. Then she applies a test which always succeeds in YES instances (the property holds), but fails with constant probability (over the coin tosses) in NO instances (the property doesn't hold). That should answer the second question.

Since there are $r(n)$ coins, there are $2^{r(n)}$ different outcomes for the coins, and so the verifier in total queries the proof in at most $2^{r(n)}q(n)$ different places. That answers your fourth question.

What's the point of a PCP? We can encode the verifier as a CNF whose variables are the bits of the proof: for each of the $2^{r(n)}$ coin tosses, there are clauses encoding that the $q(n)$ bits sampled pass the verifier's test. If it's a YES instance, then this CNF is satisfiable. If it's a NO instance, then the verifier fails with some constant probability, and so a constant fraction of the clauses in the CNF are always unsatisfied.

The PCP theorem gives a PCP for 3SAT with $q(n) = O(\log n)$ and $r(n) = O(1)$. That means that given a 3CNF, we can come construct a new CNF of length $O(2^{q(n)}) = n^{O(1)}$ using the construction outlined in the preceding paragraph such that (i) if the original 3CNF formula is satisfiable, so is the new one, (ii) otherwise, at most $1-\epsilon$ fraction of the clauses can ever be satisfied in the new CNF. That gives a hardness of approximation result for 3SAT.

Using Raz's parallel repetition theorem, Håstad obtained a construct in which in case (ii), at most $7/8+\epsilon$ of the clauses can be satisfied, thus obtaining an optimal inapproximability result. (It's optimal since a random assignment satisfies $7/8$ of the clauses; this algorithm can be derandomized using the method of conditional expectations.)


Deleting edges such that largest connected component has at most $n/4$ nodes

One naive thought would be that we can maintain the list of the size of current connected component. After removing an edge the content of the list will be changed and when the max member of this list decreased to no more than $n/4$ we can terminate and output the edge. However, simulating such process seems inefficient.

Though removing edge is somehow hard for us to maintain the size of connected component, adding edge is not.

We can consider the problem reversely:

Initially, there is no edge in graph $G$, then we add edge in the order of $e_n,e_{n-1},\cdots,e_1$ and at the end of this process $G$ is connected. Therefore there an edge $e_i$ such that just before adding $e_i$, every connected component of the graph has at most $n/4$ nodes, but after adding $e_i$, the graph has at least one connected component with more than $n/4$ nodes.

Obviously, such $e_i$ is just the edge we want for the origin problem.

We can use Union-Find Algorithm to maintain the size of each connected component. When adding an edge$(u,v)$, first check whether $u,v$ are in different connected components. If yes, then we get a bigger connected component and the size of it will be the sum of size of those two components, otherwise we do not need to do anything.

Once we find adding $e_i$ results in a connected component bigger than $n/4$, we can terminate and output it.

The overall time complexity is $  O(m\alpha (n)) $


Devise algorithm to travel destinations in a way that you always have enough money for the next destination (getting paid at each destination as well)

The algorithm that you suggested using a queue does not seem to be linear-time with respect to $n$, because you did not prove that each restaurant gets pushed in the queue only once (or at most a constant number of times). I suppose there are cases where a restaurant gets pushed into the queue nearly $n$ times.

However, there is a simple algorithm for this problem and I got the idea based on a similar question in `Introduction to Algorithms' by Cormen et al. The main idea is to start from the first restaurant and fly as much as possible, until we run out of money. If we reached the end, then that was the starting point, otherwise, we can start from the place where we run out of money. It is easy to see that the next starting point is exact the place where we run out of money (because previous restaurants did not pay enough money for sustaining).

Let $i \gets 1$;
While ($i \leq n$)
$~~~~$ Let $money \gets m_i$;
$~~~~$ Let $starting \gets i$;
$~~~~$ While ($money \geq 0$)
$~~~~~~~~$ Let $money \gets money - c_i$;
$~~~~~~~~$ Let $i \gets i + 1$;
$~~~~$ EndWhile;
EndWhile;
Output $starting$;

The main idea behind the proof is mentioned in my second paragraph. Once you start from a restaurant $b_i$ and run out of your money in a restaurant $b_j$, you can make sure that none of the restaurants $b_i$ to $b_{j-1}$ are not good starting points.

How to prove that such $starting$ exist? It is possible to show that by contradiction. We know that:

$$\sum_{1 \leq i \leq n} m_i = \sum_{1 \leq i \leq n} c_i,$$

which is equivalent to:

$$\sum_{1 \leq i \leq n} m_i - c_i = 0.~~~~(Eq. X)$$

Let us assume that there is no such $starting$ for which the person can start from restaurant $b_{starting}$ and visit all restaurants maintaining a positive amount of money in his pocket. We know that starting from restaurant $b_i$, if we run out of money in restaurant $b_j$, this means that for every restaurant $b_k$ ($i \leq k < j$) there is no way to pass restaurant $b_j$ (because we will definitely run out of money). Given our assumption that no such $starting$ exist, this means that we will have a bunch of pairs $(b_{i_1}, b_{j_1}), \cdots, (b_{i_m}, b_{j_m})$ ($i_{x+1} = j_{x}$) that all result in running out of money. This means that for every pair $(b_{i_x}, b_{j_x})$ we have,

$$\sum_{i_x \leq y \leq j_x} m_{i_y} - c_{i_y} \leq 0,$$

which results in either of the following two cases: (1) The money becomes zero and the critic does not have money to catch up with the next flight and cannot continue flying, (2) The overall summation becomes negative, which is in clear contradiction with our very initial assumption in Eq. (X).


Algorithm for breaking a graph into sub-graphs based on an attribute

This seems to be the "minimum weight orthogonal partition problem", which has been studied among others by Zheng et al. [1]. Computer scientists have also studied it under the name "colourful components", though it sometimes refer to an unweighted variant. The problem is known to be NP-hard, and some approximations exist [2]. There are probably more recent results, these two references should help you find them.

[1]: Chunfang Zheng, Krister M. Swenson, Eric Lyons, David Sankoff:
OMG! Orthologs in Multiple Genomes - Competing Graph-Theoretical Formulations. WABI 2011: 364-375 -- http://albuquerque.bioinformatics.uottawa.ca/kms/files/papers/2011-ZhengOMG.pdf

[2]: G. He, J. Liu and C. Zhao: Approximation Algorithms for Some Graph Partitioning Problems. Graph Algorithms and Applications 2, pp. 21-31 (2004) -- https://www.researchgate.net/publication/220639657_Approximation_Algorithms_for_Some_Graph_Partitioning_Problems


Well, any true statement implies every other true statement, so in that vacuous sense, I suppose one implies the other.

But no, I wouldn't say that Carroll's paradox implies Rice's theorem in any interesting or meaningful way.  Carroll's Paradox is an explanation of why we need modus ponens as an inference rule in propositional logic and can't replace it with a finite list of axioms.  It's nothing fancier than that.  As such, it refers to what is true in a logical theory.  It refers to what inference rules or axioms we need.

Rice's theorem is different.  It talks about what is decidable, not what is true.   It talks about what can be computed on a Turing machine, not about the inference rules or axioms we need.

Rice's theorem doesn't say "it's not possible to formalise the demonstration of a non-trivial property of a recursively enumerable language within the same given language".  It has nothing to do with "within the same given language" (it's not even clear what that would mean; a language is a subset of $\{0,1\}^*$ and doesn't demonstrate anything), but rather with that can be computed with a Turing machine.  Rice's theorem talks about what a Turing machine can decide.

Rice's theorem doesn't say "you will necessarily need a metalanguage to define modus ponens".  (I don't even know what a metalanguage would mean in this context.)  It has nothing to do with what you can define.  Rather, it has to do with what a Turing machine can decide.

In general, I warn you against trying to reason about mathematical statements using English language and analogies.  That is notoriously error-prone.  Rice's theorem is a mathematical statement with a precise mathematical meaning.  At a suitable level of imprecision and vagueness, I suspect everything can seem similar and connected -- but when you look at the specifics, the situation often becomes richer and more interesting than that.


How to convert the left recursive grammar into right recursive grammar

Consider where "a" terminals can appear in a string produced by this grammar. Based on that, you should be able to split the "A" nonterminal up to make a right-recursive grammar that matches the same strings.

(Also, your "B" nonterminal appears to be missing...? Or just has no productions?)


Recursion is orthogonal to side effects.

You can have a recursive function with side effects, or without.  You can also have a non-recursive function with side effects, or without.  It's a matter of opinion and taste whether it's better to avoid side effects in any particular situation.  As far as I know, there is no scientific evidence to support a claim that "you should always avoid side effects in any recursive function".

There are reasons to be wary of side effects.  They make programs more complex to reason about.  This doesn't mean you should never use side effects, but they have tradeoffs.  Perhaps one could argue that recursive functions are especially tricky to code and thus one should be especially wary of recursive functions with side effects -- personally, I don't know that I'm particularly persuaded by it.  Ultimately, I think it's a matter of taste and judgement, and it's unlikely that any "one-size-fits-all" rule will be scientifically justified.


An algorithm to find the maximum profitable assignment

Your problem is known as the assignment problem.


You've basically got it. The reason why the a loops is because whichever state you were in, you can end up in any one of them (if you were in 0, maybe you took the looping a and ended up in 0).

The way I think of it is, with the NFA, you are maintaining a list of states you are in at any one point. When you convert to DFA, we have a state for any set of states we can be in (the power set of all the states in the NFA). We can tidy this up if we want (removing inaccessible nodes etc.) but that is the basic principle.

So with yours, you state in state 0. Then we read an a and at this stage we could be in {0, 1}. Then we read in another a and now we could have done:

Been in state 0 and stayed in state 0
Been in state 0 and advanced to state 1
Been in state 1 and advanced to state 2

Therefore we could now be in any of {0, 1, 2} so that's the node we go to in the DFA.


I'm not familiar with the topic, so all I can do is give a few pointers.
Manipulating partitions of finite sets is known by several names:

union-find when you start with singletons and progressively merge sets;
partition refinement when you start with a single set and progressively split it;
union-split-find when sets can be both merged and split as in your case.

Katherine J. Lai's discusses the union-split-find problem and proposes an algorithm using B-trees that double as finger trees to represent each set. Each element is represented by a distinct integer; using consecutive values for elements that are likely to remain together is more efficient. To merge two sets, split them into non-overlapping intervals that are entirely contained in one of the sets, and join the pieces together. See her thesis for details.


Algorithmic challenge: generate a list of random non overlapping squares

You could perhaps use a 2 dimensional k-d tree to store the set of free positions $(x, y)$ where the left upper corner of a new square could be chosen without overlapping the existing squares. Each node of the tree covers a region in the area $a$ and you can decorate this node with this region's coordinate and the number of free positions that it contains. At the top of the tree, you can read the total number of available slots and simply choose a random number to get the index of that slot. By walking downwards in the tree, you can find which slot corresponds to this random number, then update the tree accordingly to add a new square.
My intuition is that the amount of data contained in the tree is approximately proportional to the number $k$ of squares already chosen and that the addition of a new square should be proportional to $\log k$ on average.
Edit: I wrote a working implementation in python 3 by using a tree structure. I'm not sure about the performance for large $n$ but it could  already be measured experimentally. I didn't make any effort to balance the tree but as new squares are chosen randomly, this randomness should balance the tree on average.
Here is a link to the program. I don't know if I can paste it in this post. It chooses randomly at most 10 squares that don't touch each other. Here is an example output


How to tell if a language is recognizable, co-recognizable or decidable?

L is recognizable

A language $L$ is recognizable if and only if there exists a verifier for $L$, where a verifier is a Turing machine that halts on all inputs and for all $w \in \Sigma^*$, $w \in L \leftrightarrow \exists c \in \Sigma^*. V\text{ accepts }\langle w, c\rangle$. Commonly, $c$ is thought of as a "certificate" or "proof" that $w$ is in $L$ and the verifier $V$ checks whether $c$ is a valid proof of $w$ being in $L$. (Note that this definition is equivalent to the recognizer definition because we can construct a recognizer for a language from a verifier for that language). Now to determine whether or not a language is in RE we can ask the following question:

  Given a string $w \in L$, could you prove that $w \in L$?

For example, consider $HALT = \{\langle M, w\rangle\ |\ M\text{ is a TM that halts on }w\}$. $HALT$ is recognizable because to prove to you that $M$ halts on $w$, I can just tell you the number of steps you should run $M$ for and if $M$ does halt after that many steps, you would be convinced that $\langle M, w\rangle \in HALT $.

L is co-recognizable

Similarly, a language $L$ is co-recognizable if and only if its complement is recognizable, or in other words if there exists a verifier for $\overline{L}$. Thus to see if a language is in co-RE, we can ask:

  Given a string $w \not\in L$, could you prove that $w \not\in L$?

Taking again the example of $HALT$, we can use this intuition to show that $HALT$ is not co-recognizable. This is because if I told you that some machine $M$ does not halt on input $w$, there isn't really anything I can tell you to convince you of that fact. I could run $M$ on $w$ but even if we've been watching $M$ run and haven't seen it halt yet, we don't know that it won't go and halt sometime in the future.

L is decidable

Finally, a language $L$ is decidable if both $L$ and $\overline{L}$ are recognizable. So if the answer to both of the above two questions is yes, then the language is decidable.

As an example, consider $L = \{a^nb^n\ |\ n \in \mathbb{N}\}$. Given a string $w \in L$, could I prove to you that $w \in L$? Sure, I could count up the number of $a$s and the number of $b$s and show that they're equal, so $L$ is recognizable. What about if $w \not\in L$? I could prove that a string is not in $L$ by showing that it's either not of the form $a^nb^m$ or that there's a mismatch in the number of $a$s and $b$s. Thus, $L$ is co-recognizable. Since it's both recognizable and co-recognizable, $L$ is also decidable.

Reference: I'm a TA for an intro computability/complexity theory class at my university and my professor made this really helpful animated guide for reasoning about regular, decidable, and recognizable languages.