Can interval partition solve by sort by different approach

Yes, your approach is correct.

"The interval partitioning problem" is more commonly known as "the interval-graph coloring problem". It is problem 16.1-4 in the book Introduction to Algorithm by CLRS, third edition.

The idea behind the common solution described in the question and your approach is essentially the same. Arguably, your algorithm is simpler than that solution given by many sources. On the other hand, there are many sources that give the roughly the same algorithm as yours such as the article at GeeksForGeeks.

There is one distinction of your algorithm, If time equals, prefer type=end. It turns out this specification is unnecessarily restrictive in the sense that you can break any tie that consists of requests of the same starting time arbitrarily. On first look, it might sound surprising that the algorithm still works when ties are breaking arbitrarily. One might take for granted that scheduling the one request that ends early should yield more room for later scheduling. However, it does not matter which one to schedule out of the requests of the same staring time. I will leave this little enigma as an exercise for readers to ponder and prove.

By the way, there are some sloppiness in the question and the algorithm. In the problem statement, it does not mention explicitly that each request must use one and only one resource all the way from its start time to its end time. That each request can use any resource. It does not specify whether a request that starts at time $t_0$ can use the same resource used by another request that ends at $t_0$, that is, whether those two requests are overlapping at $t_0$. The "total machine" is used suddenly near the end of the question, which should be, for the sake of consistency, "total number of resources". This short answer is written in the hope that
all those ambiguities and sloppiness do not affect the high-level thinking by readers.


Modify max value multiple times of a list

One solution is changing the underlying data structure;

In the binary heaps, Decrease_Key is $\mathcal{O}(\log n)$ cost in the worst case. If you use Fibonacci heaps1, Decrease_Key is  $\mathcal{\Theta(1)}$ in amortized time. With the binary heaps, you will have $\mathcal{O}(m \log n)$ whereas in Fibonacci heaps you will have $\mathcal{\theta(m)}$ in amortized time.

note : Fibonacci Heaps are theoretically better than Binary Heaps. But their the constant factors hidden are very high.

1 Introduction To Algorithms 3rd. Ed. Cormen et. al. at section 19.


Can there be an algorithm for a relation which is not a function?

Your question is very general, especially it is not clear to me what you mean by "algorithm for a relation". I still have some answers.

The difference between (binary) relations and functions is that the former can have several different outputs for the same input. This is just what non-determinism offers us. Thus the theory of computation offers us many models of computation thatcan be seen as computing relations instead of functions.

Further, the input in the most common models of computations has the form of a string. Thus you could compute a relation in the way that string "(x,y)" is accepted iff (x,y) forms part of the relation. This, of course, generalizes to relations of higher order.


Is language $\{a,b\}^*$ same as language $\{xy \in \{a,b\}^* \mid |x|_a = |y|_b \}$?

You can prove this by induction on the length of the string.

The base case of $|z| = 0$ is obvious, we have to take $x=y=\varepsilon$.

The inductive assumption then is that $L =\{xy \in \{a,b\}^{\ast}\mid |x|_{a} = |y|_{b}\}$ contains all strings1 of length at most $n$.

Now we want to show that it contains all strings of length $n+1$.

Let $z \in  \{a,b\}^{n+1}$ and let $z^{-1}$ be $z$ with the final symbol removed. By the inductive assumption $z^{-1} \in L$. The final symbol $z_{n+1}$ in $z$ must be either an $a$ or a $b$.

If $z_{n+1}$ is an $a$, then we can construct an appropriate $x_{z}$ and $y_{z}$ by taking $x_{z} = x_{z^{-1}}$ and $y_{z} = y_{z^{-1}}a$. Then $|x_{z}|_{a} = |x_{z^{-1}}|_{a} = |y_{z^{-1}}|_{b} = |y_{z}|_{b}$, and therefore $z\in L$.
If $z_{n+1}$ is a $b$ we have a slightly more complicated situation, but it's not too difficult. The first symbol of $y_{z^{-1}}$ must also be either an $a$ or a $b$, or $y = \varepsilon$.

If the first symbol is an $a$, then we use the same $x$-$y$ partition as for $z^{-1}$, but we move the first symbol of $y$ to the end of $x$, and add the new $b$ to the end of $y$, then $|x_{z}|_{a} = |x_{z^{-1}}|_{a} + 1$ and $|y_{z}|_{b} = |y_{z^{-1}}|_{b} + 1$.
If the first symbol is a $b$, we do the same as in the $a$ case, but as we're adding a $b$ to $x$ and taking one $b$ away from $y$ but adding another at the end, the number of $a$s and $b$s in $x$ and $y$ don't change.
If $y_{z^{-1}} = \varepsilon$, then we simply choose $x = z$ and $y = \varepsilon$ and again $|x_{z}|_{a} = |x_{z^{-1}}|_{a} = |y_{z^{-1}}|_{b} = |y_{z}|_{b}$ (in fact, they all equal $0$, so $z = b^{n+1}$).

Therefore in all cases $z \in L$, and we are done.

Footnotes

...over alphabet $\Sigma = \{a,b\}$.


Your intuition is correct, though it's probably more useful to think of the statement "[Logic] = [Complexity Class]" as "A property of relational structures can be decided in [Complexity Class] if, and only if, it is definable in [Logic]."

As for the proof, I think you're overthinking it. There's not just a bijection between accepting computations and structures $\cal{A}$ such that $M(\cal{A})=1$ — that's the definition of what it means for $M(\cal{A})$ to be $1$. The property of $\cal{A}$ that the formula verifies is "$\cal{A}$ is a structure accepted by $M$." There's really no difference between the statements (for example), "$\cal{A}$ is a connected graph", "$\cal{A}$ satisfies this formula that defines connectivity", "$\cal{A}$ is accepted by this Turing machine" and "this Turing machine accepts $\cal{A}$."

Perhaps it would help to give some intuition about how the proof works. The point about the linear order is that it lets us use the universe of the structure as digits, to write numbers in base $n=|\cal{A}|$. Since the machine we're dealing with runs in time $n^k$, we can index each time step of its computation by a $k$-digit number in base $n$ and likewise each used cell on its tape (in $n^k$ steps, it can't use more than $n^k$ tape cells).  You can also use base-$n$ numbers (of fixed length) to represent the states of the Turing machine and the characters in its alphabet.  You use this to build up relations that say things like, "At time $t$, cell $i$ of the tape contains character $c$", "At time $t$, the head is at position $p$", "At time $t$, the machine is in state $s$". Now, you write a formula that says:

at time $0$, the tape contains the coding of $\cal{A}$, the head is at position $0$ (and the head is not anywhere else) and the machine is in its start state (and not in any other state) AND
if, at time $t$, the machine is in some configuration, then the configuration at time $t+1$ is what the definition of the machine says it should be AND
at some time $t$, the machine is in an accepting state.

Note that there are various different ways of coding the Turing machine's configuration in relations. For example, since there are only a fixed, finite number of machine states $s_1, \dots, s_\ell$, you could use $k$-ary relations $S_1, \dots, S_\ell$ such that each $S_i$ contains the times at which the machine is in state $s_i$. The tape symbols can be coded similarly.


Computers rely on physics. Transistors have some known characteristics, given some assumptions on making process. Parts that does not meet the exepected characteristics are just trashed (or sold with lower expectations, usually lower max frequency).

This ensure that computations are correct while complying operation conditions (stable power supply, EMC, ...). The whole systems are built to meet those requirements. When you use very cheap equipment (often a cheap power supply), you may face some computer crashes, as you do not meet system requirements (power supply stability) anymore.

Sometimes, external conditions make expectations unreachable. In aeronautic and aerospace, systems have to cope with cosmic rays that may disturb their behavior. In such case, several similar systems are used in parallel, to be able to maintain operation when one system has errors.

Also, some transmissions and storages are known to be unreliable, and Error Correction Codes are used to fix the data after reception.

So systems are designed to prevent errors to happen in almost every cases, using a broad range of dedicated methods. Working in consumer electronics, I have some failure rates on the hardware around 10 faulty parts per million in the first year of use. This is much better than the mechanical parts or the software, but not perfect (even if it's too good for the consumer market. Average return rate on consumer products is around 1%, 100 faulty parts per million would be acceptable on this market).


It all depends what you consider "computer science."

For what I would call "classical computer science" i.e. the theory of Algorithms, Turing Machines, etc. it can all be modelled in set theory.

A Turing Machine is just a tuple (which can be modelled using sets): a set of states, a tape-alphabet set, a transition function, etc. All of these are set-theoretic constructs, and even with nondeterminism, we replace the transition function with a relation, which is again set theoretic.

Similarly, we can define the semantics of programming languages using sets. Usually this just boils down to a big-step or small-step operational semantics, which again, is just defining relations.

Where things get iffy is with the so-called "alternate foundations of mathematics". This includes things like:

Martin-Lof type theory
Coqand's Calculus of Constructions
Homotopy type theory

They provide alternate sets of axioms from which mathematics can be built up. For example, the usually discard excluded middle and axiom of choice. Homotopy type theory, for example, introduces the Univalence Axiom.

These systems tend to be heavily oriented towards computation through the Curry-Howard Correspondence, so that a proof can "run" on a computer. So they don't quite fit into ZFC, but are generally considered part of computer science.


In most type systems, the type rules work together to define judgements of the form:

$$\Gamma\vdash e:\tau$$

This states that in context $\Gamma$ the expression $e$ has type $\tau$.
 $\Gamma$ is a mapping of the free variables of $e$ to their types.

A type system will consist of a set of axioms and rules (a formal system of rules of inference, as Raphael points out).

An axiom is of the form

$$\dfrac{}{\Gamma \vdash e:\tau}$$

This states that the judgement $\Gamma \vdash e:\tau$ holds (always).

An example is

$$\dfrac{}{x:\tau\vdash x:\tau}$$

which states that under the assumption that the type of variable $x$ is $\tau$, then the
expression $x$ has type $\tau$.

Inference rules take facts that have already been determined and build larger facts from them. For instance the inference rule

$$\dfrac{\Gamma\vdash e_1:\tau\to\tau' \quad \Gamma\vdash e_2:\tau}{\Gamma\vdash e_1\ e_2:\tau'}$$

says that if I have a derivation of the fact $\Gamma\vdash e_1:\tau\to\tau'$ and a derivation of the fact $\Gamma\vdash e_2:\tau$, then I can obtain a derivation of the fact $\Gamma\vdash e_1\ e_2:\tau'$. In this case, this is the rule for typing function application.

There are two ways of reading this rule:

top-down - given two expressions (a function and another expression) and some constraints on their type, we can construct another expression (the application of the function to the expression) with the given type.
bottom-up - given an expression that is, in this case, the application of a function to some expression, the way this is typed is by first typing the two expressions, ensuring that their types satisfy some constraints, namely that the first is a function type and that the second has the argument type of the function.

Some inference rules also manipulate $\Gamma$ by adding new ingredients into it (view-ed bottom up). Here is the rule for $\lambda$-abstraction:

$$\dfrac{\Gamma x:\tau\vdash e:\tau'}{\Gamma\vdash \lambda x.e:\tau\to \tau'}$$

The inference rules are applied inductively based on the syntax of the expression being considered to form a derivation tree. At the leaves of the tree (at the top) will be axioms, and branches will be formed by applying inference rules. At the very bottom of the tree is the expression you are interested in typing.

For example, a derivation of the typing of expression $\lambda f.\lambda x.f\ x$ is

$$\dfrac{\dfrac{}{f:\tau\to\tau',x:\tau\vdash f:\tau\to\tau'} \qquad \dfrac{}{f:\tau\to\tau',x:\tau\vdash x:\tau}}
{\dfrac{f:\tau\to\tau',x:\tau\vdash f\ x:\tau'}{
\dfrac{f:\tau\to\tau'\vdash \lambda x.f\ x:\tau'}{\vdash \lambda f.\lambda x.f\ x:\tau'}}}$$
Two very good books for learning about type systems are:

Types and Programming Languages by Benjamin Pierce
Practical Foundations for Programming Languages by Robert Harper

Both books are very comprehensive, yet they start slowly, building a solid foundation.


Minimum number of comparision to find the third largest element in an array of distinct integers?

For the problem of computing the $k$-th rank element, a lower bound of $n-k+\log \binom{n}{k-1}$ can be proven with decision trees.
For simplicity this proof assumes that the element set $X$ is of size $n$ and its elements are distinct (which makes the problem harder). Moreover, the algorithm may only compare any two elements, and conclude one is either smaller or greater than the other.

First, let us claim the following:

For computing the $k$-th rank element (denoted $x_k$) (using comparisons only), every other element $x_i$ must be involved in a comparison that sets it lesser or greater than the $k$-th rank element.
Formally: for any $x_i$ lesser than $x_k$, $x_i$ must be involved in a comparison of the sort $x_i < x_j \leq x_k$. For any $x_i$ greater than $x_k$, it must be involved in the comparison $x_i > x_j \geq x_k$

The proof by contradiction: Suppose $x$ was not involved in either those comparisons. Then $x$ can be either greater or smaller than $x_k$, which means the $k$-th rank element can change depending on $x$.

Let $\mathcal{T}$ be a decision tree that finds the $k$-th rank element. We will show $\mathcal{T}$ has at least $2^{n-k} \binom{n}{k-1}$ leaves.
Now, suppose $T_1$ is another decision tree, that knows the set of elements greater than $x_k$, denoted by $K_1$. It means $T_1$ does not need to compare any elements of $K_1$, and thus performs $n-k$ comparisons, or has $2^{n-k}$ leaves.
Because of the claim we made earlier, we know $\mathcal{T}$ must have performed the comparisons in $T_1$, hence for each leaf in $T_1$ there is a corresponding leaf in $\mathcal{T}$. Moreover, in each of these leaves, the element $x_k$ defines the set $K_1$, which are all the elements greater than $x_k$.
How many trees like $T_1$ are there? As many as the different choices you can make for the set $K_1$, which is selecting $k-1$ elements out of $n$, which is exactly $\binom{n}{k-1}$. And for each of these trees, there are at least $2^{n-k}$ leaves in $\mathcal{T}$, which are essentially distinct, since they define distinct sets $K_i$.
It follows that $\mathcal{T}$ has at least $2^{n-k} \binom{n}{k-1}$ leaves, therefore the lower bound is $\log$ of the same:
$$n-k+\log \binom{n}{k-1}$$


Minimum number of processes for the deadlock?

I agree that no deadlock is possible here. If there are three or fewer processes, there clearly cannot be a deadlock because there are enough resources for every process to just hold two resources the whole time.

So any deadlock must have at least four participating processes.  To participate in a deadlock, a process must hold at least one resource. Further, a process cannot hold more than two resources so a process that currently has two resources can definitely run until it frees at least one of those resources. Therefore, if there is a deadlock, it must involve four processes, each holding exactly one resource. This means that there are two resources free so any process that requests a resource will be granted it and will then run until it releases one or both of the resources it holds. Out of our set of four supposedly deadlocked processes, at least one is always runnable, so there is no deadlock. (In fact, at least two are runnable at all times.)

Perhaps the question-setter had the following situation in mind. Suppose processes 1 and 2 are using two resources each and processes 3 and 4 are using one resource each. Now, if 3 and 4 each request one more resource, they will block. But this is not deadlock because the situation can be resolved by either one of the two runnable processes (1 and 2) giving up one of their resources. Deadlock is the situation where every one of a set of processes is blocked and the only way to resolve the situation is for one of those blocked processes to give up resources, which it can't do because it's blocked.


There are no general tricks for proving self lowness, note that the classes that you yourself mentioned are very different in nature. Recall that $L\in P/poly$ iff there exists a Turing machine $M(x,y)$, which runs in time polynomial in $|x|$, and an advice sequence $\{\alpha_n\}_{n\in\mathbb{N}}$, such that for all $x\in\Sigma^*$ it holds that:

$x\in L \iff M\left(x,\alpha_{|x|}\right)=1$

$L\in P/poly^{P/Poly}$ if the machine $M$ above can also query membership to some other language $O\in P/Poly$, so there exists a machine $M_O(x,y)$ which satisfies the above conditions with advice sequence $\beta_n$.

To show that $L$ lies in $P/Poly$, the natural approach would be to use $M$ with the same advice sequence $\alpha_n$. The problem arises when $M$ queries its oracle $O$ on some string $s$, what do we do then? Here the natural approach would be to simulate $M_O$ on $s$, but what advice should we feed to $M_O(s,\cdot)$ ? Suppose $M$ runs in time $n^c$, then on a length $n$ input, $M$ can only query its oracle on strings of length $\le n^c$. This leads to the following solution, on length $n$ inputs, your $P/Poly$ machine for $L$ would use the advice $\left(\alpha_n,\beta_0,\beta_1,...,\beta_{n^c}\right)$, and simulate $M$ on the input with advice $\alpha_n$. Whenever $M$ queries the oracle on a string $s$, simulate $M_O(s,\beta_{s})$ to obtain an answer, and continue executing $M$.


Checking whether there is k circles with common area

This problem and related problems have been studied in the paper "Bajaj, C., & Li, M. (1983). On the duality of intersections and closest points. Cornell University."

They call a common area for $k$ circles a '$k$-intersection'. The paper gives an $O(n^2\log n)$ algorithm for the problem of finding a $k$-intersection when the circles have different radius. (Theorem 13) It is not clear to me from the paper how that bound is achieved, but I do see how to achieve $O(n^3)$ time with their approach.

Algorithm

The main idea is to construct the following (directed) planar intersection graph $G=(V,E,F)$: The vertices $V$ of this graph are all intersection points of the circles and the edges $E$ are the circle arcs connecting those intersection points. The direction of the edges is counterclockwise on the circle, such that the interior of the circle it is part of lies to the left of the edge. We also keep track of the faces $F$ of this planar graph, which are the regions enclosed by the edges $E$.

Note that each region of circle intersections corresponds to a face of this planar graph and that the number of circles that contain the region is equal to the number of clockwise boundary edges of the corresponding face. If we have computed $G$, then we can maintain a counter for each face in $F$ and traverse the graph to visit all edges and increase the counter of face left of each edge. Then, after we have traversed the edges, each face has the number of circles that contain it stored in the counter.

Complexity

Since there can be at most $O(n^2)$ intersections of $n$ circles, $|V|=O(n^2)$. Since $G$ is a planar graph, $|E|\leq 3|V|-6 =O(n^2)$. So, traversing the graph takes $O(|V|+|E|)=O(n^2)$ time.

As for constructing the graph, the authors claim that this graph can be constructed in $O(n^2\log n)$ time by sorting the edges. I did not see any further explanation of this in the paper and do immediately see how to achieve this. (in particular, it would be helpful to know on what they sort.)

I do see how to do this in $O(n^3)$: The vertices and edges of the graph can be constructed in $O(n^2)$ time by iteratively adding new circles. When a new circle is added, we add the new intersection points and subdivide some of the existing edges.

Adding the faces is more complicated and I currently only see the naive method of for each edge $e$, traversing all edges that are on the boundary of the two faces adjacent to edge $e$. This takes $O(n)$ per edge, so $O(n^3)$ in total. It does seem like we can do better here, but I currently don't see how.

$O(n^2\log n)$ is good, but can we do better? For the case where the circles all have the same radius, this is possible: Chazelle and Lee have found an $O(n^2)$ time algorithm based on an implicit traversal through the intersection graph ("Chazelle, B. M., & Lee, D. T. (1986). On a circle placement problem. Computing, 36(1-2), 1-16."). Whether $O(n^2)$ is possible for the case with circles of different radius they leave as an open problem, which has remained open for now, as far as I'm aware.


How does an operating system create entropy for random seeds?

The title and the body of your question ask two different questions: how the OS creates entropy (this should really be obtains entropy), and how it generates pseudo-randomness from this entropy. I'll start by explaining the difference.

Where does randomness come from?

Random number generators (RNG) come in two types:

Pseudo-random number generators (PRNG), also called deterministic random bit generators (DRBG) or combinations thereof, are deterministic algorithms which maintain a fixed-size variable internal state and compute their output from that state.
Hardware random number generator (HRNG), also called “true” random number generators, are based on physical phenomena. “True” is a bit of a misnomer, because there are no sources of information that are known to be truly random, only sources of information that are not known to be predictable.

Some applications, such as simulations of physical phenomena, can be content with random numbers that pass statistical tests. Other applications, such as the generation of cryptographic keys, require a stronger property: unpredictability. Unpredictability is a security property, not (only) a statistical property: it means that an adversary cannot guess the output of the random number generator. (More precisely, you can measure the quality of the RNG by measuring the probability for an adversary to guess each bit of RNG output. If the probability is measurably different from 1/2, the RNG is bad.)

There are physical phenomena that produce random data with good statistical properties — for example, radioactive decay, or some astronomical observations of background noise, or stock market fluctuations. Such physical measurements need conditioning (whitening), to turn biased probability distributions into a uniform probability distribution. A physical measurement that is known to everyone isn't good for cryptography: stock market fluctuations might be good for geohashing, but you can't use them to generate secret keys.

Cryptography requires secrecy: an adversary must not be able to find out the data that went into conditioning. There are cryptographically secure pseudo-random number generators (CSPRNG): PRNG algorithms whose output is suitable for use in cryptographic applications, in addition to having good statistical properties. One of the properties that make a CSPRNG cryptographically secure is that its output does not allow an adversary to reconstruct the internal state (knowing all the bits but one produced by a CSPRNG does not help to find the missing bit). I won't go into how to make a CSPRNG because that's the easy bit — you can follow recipes given by professional cryptographers (use a standard algorithm, such as Hash_DRBG, HMAC_DRBG or CTR_DRBG from NIST SP 800-90A) or the ANSI X9.31 PRNG. The CSPRNG requires two properties of its state in order to be secure:

The state must be kept secret from the start and at all times (though exposure of the state will not reveal past outputs).
The state must be linear: the RNG must never be started twice from the same state.

Architecture of a random number generator

In practice, almost all good random number generators combine a CSPRNG with one or more entropy sources. To put it succintly, entropy is a measure of the unpredictability of a source of data. Basing a random number generator purely on a hardware RNG is difficult:

The raw physical data is likely to need conditioning anyway, to turn probabilistic data into a uniform distribution.
The output from the source of randomness must be kept secret.
Entropy sources are often slow compared with the demand.

Thus the RNG in an operating system almost always works like this:

Accumulate sufficient entropy to build an unpredictable internal state.
Run a CSPRNG, using the accumulated entropy as the seed, i.e. as the initial value of the internal state.
Optionally, periodically mix additional entropy into the internal state. (This is not strictly necessary, since entropy is not “consumed” at any measurable rate. It helps against certain threats that leak the RNG state without compromising the whole system.)

A random number generation service is part of the job of an operating system, because entropy gathering requires access to hardware, and entropy sources constitute a shared resource: the operating system must assemble them and derive output from them that will suit applications. Pseudo-random conditioning of the entropy sources is required in the operating system; it might as well be cryptographically secure, because this isn't fundamentally harder (and it is required on operating systems where applications do not trust each other; on fully cooperative systems, each application would have to run its own CSPRNG internally if the operating system didn't provide one anyway).

Most systems with persistent storage will load an RNG seed from disk (I'll use “disk” as an abbreviation for any kind of persistent storage) when they boot, and overwrite the seed with some fresh pseudo-random data generated from that seed, or if available with random data generated from that seed plus another entropy source. This way, even if entropy is not available after a reboot, the entropy from a previous session is reused.

Some care must be taken about the saved state. Remember how I said the state must be linear? If you boot twice from the same disk state, you'll get the same RNG outputs. If this is a possibility in your environment, you need another source of entropy. Take care when restoring from backups, or when cloning a virtual machine. One technique for cloning is to mix the stored entropy with some environmental data that is predictable but unique (e.g. time and MAC address); beware that if the environmental data is predictable, anyone in possession of the stored VM state can reconstruct the seed of a forked VM instance.

Entropy sources

Finding (and correctly using) entropy sources is the most challenging part of random number generation in an operating system. The available entropy sources will necessarily be dependent on the hardware and on which environment the hardware runs in.

If you're lucky, your hardware provides a peripheral which can be used as an entropy source: a hardware random number generator, either dedicated or side-purposed. For example:

thermal noise
avalanche noise from an avalanche noise
various types of (combinations of) oscillators, such as ring oscillators
radioactive decay
various quantum phenomena that I couldn't explain
acoustic noise
camera noise

NIST SP800-90B provides design guidelines for hardware RNG. Evaluating a hardware RNG is difficult. Hardware RNG are typically delicate beasts, which need to be used with care: many types require some time after boot and some time between reads in order to destabilize, they are often sensitive to environmental conditions such as the temperature, etc.

Intel x86-64 processors based on the Ivy Bridge architecture provide the RdRand instruction which provides the output from a CSPRNG seeded by thermal noise. Most smartphone processors include a hardware entropy source, though Android doesn't always use it.

Systems that lack a strong entropy source have to make do with combining weak entropy sources and hoping (ensuring would be too strong a word) that they will suffice. Random mouse movements are popular for client machines, and you might have seen the security show by certain cryptography programs that ask you to move the mouse (even though on any 21st century PC operating system the OS will have accumulated entropy without the application needing to bother).

If you want to look at an example, you can look at Linux, though beware that it isn't perfect. In particular, /dev/random blocks too often (because it blocks until enough entropy is available, with an overly conservative notion of entropy), whereas /dev/urandom is almost always good except on first boot but gives no indication when it doesn't have enough entropy. Linux has drivers for many HRNG devices, and in accumulates entropy from various devices (including input devices) and disk timings.

If you have (confidential) persistent storage, you can use it to save entropy from one boot to the next, as indicated above. The first boot is a delicate time: the system may be in a fairly predictable state at that point, especially on mass-produced devices that essentially operate out of the factory in the same way. Some embedded devices that have persistent storage are provisioned with an initial seed in the factory (produced by a RNG running on a computer in the factory). In virtualized server environments, initial entropy can be provisioned when instantiating a virtual machine from the host or from an entropy server.

Badly-seeded devices are a widespread problem in practice — a study of public RSA keys found that many servers and devices had keys that were generated with a poor RNG, most likely a good PRNG that was insufficiently seeded. As an OS designer, you cannot solve this problem on your own: it is the job of the entity in control of the deployment chain to ensure that the RNG will be properly seeded at first boot. Your task as an OS designer is to provide a proper RNG, including an interface to provide that first seed, and to ensure proper error signaling if the RNG is used before it is properly seeded.


Example of reduction in communication complexity

Assume that each player gets a number in $[n]$, and they can compute $h_n(x,y)$. Each player knows $n$, so if $h_n$ is computable with less than $log(n)$ communication, they can compute $h_n(n-x,y)$ in under $log(n)$ bits of communication. Since you have $h_n(n-x,y)=1 \iff x=y$ then you managed to compute $\delta_{x,y}$ in sub logarithmic communication, contradiction.


First off, you're absolutely right: you're on to a real concern.  Formal verification transfers the problem of confidence in program correctness to the problem of confidence in specification correctness, so it is not a silver bullet.

There are several reasons why this process can still be useful, though.

Specifications are often simpler than the code itself.  For instance, consider the problem of sorting an array of integers.  There are fairly sophisticated sorting algorithms that do clever things to improve performance.  But the specification is fairly simple to state: the output must be in increasing order, and must be a permutation of the input.  Thus, it is arguably easier to gain confidence in the correctness of the specification than in the correctness of the code itself.
There is no single point of failure.  Suppose you have one person write down a specification, and another person write the source code, and then formally verify that the code meets the spec.  Then any undetected flaw would have to be present in both the spec and the code.  In some cases, for some types of flaws, this feels less likely: it's less likely that you'd overlook the flaw when inspecting the spec and overlook the flaw when inspecting the source code.  Not all, but some.
Partial specs can be vastly simpler than the code.  For instance, consider the requirement that the program is free of buffer overrun vulnerabilities.  Or, the requirement that there are no array index out-of-bounds errors.  This is a simple spec that is fairly obviously a good and useful thing to be able to prove.  Now you can try to use formal methods to prove that the entire program meets this spec.  That might be a fairly involved task, but if you are successful, you gain increased confidence in the program.
Specs might change less frequently than code.  Without formal methods, each time we update the source code, we have to manually check that the update won't introduce any bugs or flaws.  Formal methods can potentially reduce this burden: suppose the spec doesn't change, so that software updates involve only changes to the code and not changes to the spec.  Then for each update, you are relieved of the burden to check whether the spec is still correct (it hasn't changed, so there's no risk new bugs have been introduced in the spec) and of the burden to check whether the code is still correct (the program verifier checks that for you).  You still need to check that the original spec is correct, but then you don't need to keep checking it each time a developer commits a new patch/update/change.  This can potentially reduce the burden of checking correctness as code is maintained and evolves.

Finally, remember that specs typically are declarative and can't necessarily be executed nor compiled directly to code.  For instance, consider sorting again: the spec says that the output is increasing and is a permutation of the input, but there is no obvious way to "execute" this spec directly and no obvious way for a compiler to automatically compile it to code.  So just taking the spec as correct and executing it often isn't an option.

Nonetheless, the bottom line remains the same: formal methods are not a panacea.  They simply transfer the (very hard) problem of confidence in code correctness to the (merely hard) problem of confidence in spec correctness.  Bugs in the spec are a real risk, they are common, and they can't be overlooked.  Indeed, the formal methods community sometimes separates the problem into two pieces: verification is about ensuring the code meets the spec; validation is about ensuring the spec is correct (meets our needs).

You might also enjoy Formal program verification in practice and Why aren't we researching more towards compile time guarantees? for more perspectives with some bearing on this.


Robert Israel's answer on Math Overflow provides the key insight:

If $S$ is the set of players remaining alive and it is player $j$'s turn, player $j$ should shoot at the player $k$ such that, if $k$ dies, the remaining set gives $j$ the best survival chances.

This enables us to build a dynamic programming algorithm, as Robert Israel states.  I'll explain in a bit more detail how that works.

Represent a configuration of the game by $(S,j)$, where $S$ is the set of players remaining alive and $j$ is the player whose turn it is to shoot next.
Define $f_i(S,j)$ to be $i$'s probability of survival, under the equilibrium strategy for all (under optimal play), in configuration $(S,j)$.  Then the insight above means that in configuration $(S,j)$, player $j$ should shoot at the player $k$ such that $f_j(S\setminus\{k\},j+1)$ is as large as possible.

(As a conventional notation, when I write $(S,j+1)$, you should interpret $j+1$ as the next person to shoot after $j$, given that players $S$ are alive.)

Based on this, we can write recursive equations for $f$:

$$f_i(S,j) = p_j \cdot f_i(S \setminus \{g(S,j)\}, j+1) + (1-p_j) \cdot f_i(S,j+1)$$

where

$$g(S,j) = \arg \max_k p_j(S \setminus \{k\}, j+1).$$

We'll start by calculating the values of $f_i(S,j)$ and $g(S,j)$ for all $S$ where $|S|=1$.  Then, we'll calculate the values of $f_i(S,j)$ and $g(S,j)$ for all $S$ where $|S|=2$.  Then, we'll calculate the values of $f_i(S,j)$ and $g(S,j)$ for all $S$ where $|S|=3$.

At the $k$th stage, to calculate the $f$-values, we solve a system of linear equations in $k^2 \times {n \choose k}$ unknowns.  (The unknowns are the terms $f_i(S,j)$ where $|S|=k$ and $i,j \in S$.  Note that at this point $f_i(S \setminus \{\text{anything}\},j$ is known, since the first argument to $f$ will be a set of size $k-1$, which we've already calculated in the previous stage.)  In your problem, $n=10$, so the $k$th stage involves solving a system of linear equations in $k^2 \times {10 \choose k}$ unknowns.  This has a maximum at $k=6$, where we have 7560 unknowns.  The system of linear equations can be solved using Gaussian elimination, which takes cubic time.  In particular, Gaussian elimination on a $7560 \times 7560$ matrix is entirely feasible on a computer (probably it will take at most seconds).

Therefore, this should provide an efficient algorithm to compute the survival probabilities and strategy you are looking for.


Does entangling 100 qubits require a 2^100 X 2^100 Hadamard gate?

It does require that, but you get it for free.

When you apply a 2x2 gate to a single qubit, the gate you are applying to the $n$-qubit system that qubit is in is automatically $2^n$ x $2^n$. If you apply an $H$ to the third qubit out of six, then the operation you applied to the six qubits is $I_2 \otimes I_2 \otimes H \otimes I_2 \otimes I_2 \otimes I_2$. That's a 64x64 matrix; exactly what you needed.

So performing a Hadamard transform on $n$ qubits is actually very easy, even though some very large matrices are being thrown around if you think about what's happening in that way. Just independently hit each qubit with the usual single-qubit $H$ gate.

Note that Hadamarding each qubit doesn't entangle them, though. It puts them in a superposition, but the state still factors. If you want to entangled all the qubits, you could instead hit one of them with a Hadamard then use Controlled-Nots to toggle each of the other qubits based on that Hadamard'ed qubit.


Quoting from the Wikipedia page:

  According to the ISO 14977 standard EBNF is meant to be extensible, and two facilities are mentioned. The first is part of EBNF grammar, the special sequence, which is arbitrary text enclosed with question marks. The interpretation of the text inside a special sequence is beyond the scope of the EBNF standard.


Analysis of a randomized algorithm for independent set construction

You can obtain a weak upper bound by resorting to the Markov inequality instead. Specifically, let random variable $\small Z$ be the size of the independent set remained. We have then
\begin{align}
\small
\Pr\left[Z \leq \frac{n(1 - \epsilon)}{6}\right] \leq&~\small\Pr\left[X - Y \leq \frac{n(1 - \epsilon)}{6}\right] \\
=&~\small\Pr\left[n - (X - Y) \geq n - \frac{n(1-\epsilon)}{6}\right] \\
=&~\small\Pr\left[n - (X - Y) \geq \frac{(5 + \epsilon)n}{6}\right] \\
\leq&~\small \frac{5n / 6}{(5 + \epsilon) n/ 6} = \frac{5}{5 + \epsilon}
\end{align}
where the last inequality is by Markov inequality and $\small \mathbb{E}[n - (X - Y)] = \frac{5n}{6}$.

Though the bound is weak, we can reduce it by repeating your algorithm multiple times (e.g., $\small \ell$) and then selecting the independent set with maximum size. The probability that the resultant size is still smaller than $\small \frac{n(1- \epsilon)}{6}$ then is at most $\small \left(\frac{5}{5+\epsilon}\right)^\ell$.


Is this problem NP-hard? select k sets from a collection of sets such that each selected set has an empty intersection with the non selected ones

Your problem can be solved in polynomial time.  Form an undirected graph where each set is a vertex, and there is an edge between two sets if they have a non-empty intersection.  Decompose it into connected components, and let the sizes of the connected components be $n_1,\dots,n_t$.  Then there exists a solution to your problem if and only if there is a subset of the integers $n_1,\dots,n_t$ that sums to $k$.  This is the unary subset-sum problem, and it has a polynomial-time algorithm (via dynamic programming).  Consequently, your problem can be solved in polynomial time, too.

In contrast, set packing (does there exist a way to select k sets so that each selected set has an empty intersection with all the other selected ones?) is NP-hard.


How do these additional cases fit into this Theorem about the optimal substructure of a longest common subsequence?

If $x_m = y_n$ then any longest common sequence must end with $x_m = y_n$. This is what the first item covers.
If $x_m \neq y_n$, then there are three types of longest common sequences:

Longest common sequences ending in $x_m$.
Longest common sequences ending in $y_n$.
Longest common sequences ending in neither.

These are all the cases. There is no other case.


Is there a fundamental CS problem in ORMs that leads to N+1?

Challenge #1: Imperative code

You've shown code that is in a nicely functional form.  But in many languages, in many cases, the code won't be in that nice form.  Imagine if instead of

var filtered = scores.Where(x => x.Article.Title != "trash").ToList();

the code is instead

var filtered = new List();
for (x in scores)
    if (x.Article.Title != "trash")
        filtered.append(x);

Now you're hosed: you're stuck with n+1 queries, and there's no hope for the ORM to avoid that.  In many (imperative) programming languages, you'd be lucky for the code to show up in the former form; it'll more typically be in the latter form.

Challenge #2: Static analysis of code

Let's go back to your original example:

var filtered = scores.Where(x => x.Article.Title != "trash").ToList();

How can the ORM transform this into a single SQL query?  To do that, it would have to do non-trivial static analysis of the source code.  This can't be handled just through a simple library.

From the ORM's perspective, it is passed a function that determines which articles should be kept; it knows nothing about what the function does -- it can just call the function.  That's not enough to do the transformation you want.  To do the transformation you want, one would have to inspect the code of that function and figure out what it is doing and then somehow turn that into a SQL query.  That is decidedly non-trivial (and might require both compiler support and non-trivial static analysis algorithm).

Put another way, from the ORM's perspective, the above code is equivalent to

var filtered = scores.Where(f).ToList();

where the ORM knows nothing about what f does; all the ORM can do is invoke f on values of its choice.  When you don't know what f does, there's no way to transform that into a single SQL query.

Fixing this would require a way to take code written in the underlying language and compile it to SQL.  That basically means building a second compiler for the underlying programming language, and it's not easy.

In some languages, the ORM library actually obtains more than just a black-box function f: by using support for domain-specific languages or reflection, the ORM library might be able to obtain a parse tree for f.  In this case, the ORM library has more to work with, and in principle the ORM library could use static analysis of the parse tree of f to try to compile it to a single SQL query.  It will be language-dependent whether an ORM library can do this, purely as a library, without compiler support.  So in some languages achieving what you want will be easier than in others.


What graph theory algorithm(s) would help solve this problem?

Given two progenitor vertices $u$ and $v$, the following "modified flood fill" builds a set $P$ of additional vertices to include:

While a vertex $x$ exists whose parents are both in the set $\{u, v\} \cup P$:

Add $x$ to $P$.

This will halt with $\{u, v\} \cup P$ being the largest possible set of vertices for the given pair of starting vertices.  You want the subgraph this vertex set induces: To get that, just include every original edge that links two vertices in the set.

To do this reasonably efficiently, you could maintain 3 vertex sets $V_0, V_1, V_2$, where $V_i$ contains every vertex with exactly $i$ parents in $\{u, v\} \cup P$. Whenever some vertex $x$ is added to $P$, all of its neighbours in $V_0$ or $V_1$ are promoted to the next higher set (e.g., if some neighbour $y$ was in $V_1$, it is moved to $V_2$).  These updates can be done in constant time per neighbour by using three doubly linked lists for $V_0, V_1, V_2$, as well as a length-$|V|$ array $A$ of pairs $(i, p)$: $A[u].i$ is the current set number (0, 1 or 2) for vertex $u$, and $A[u].p$ is a pointer to its linked list node.  The main loop just reads from $V_2$ until no unread vertices remain.  Each vertex and edge in the graph is processed only once, so the overall time for a single starting vertex pair is $O(|V|+|E|)$.

Thanks to D.W. for catching a problem in my first algorithm.


Computational indistinguishability for any distribution using a Chernoff bound

How the Chernoff bound is applied
What does it mean for $D$ and $D'$ to be indistignuishable by a circuit $C$? It means that
$$
|\Pr_{x \in D}[C(x) = 1] - \Pr_{x \in D'}[C(x) = 1]| \leq \epsilon.
$$
Let $x_1,\ldots,x_w$ be the sampled elements. Then
$$
\Pr_{x \in D'}[C(x) = 1] = \frac{X_1 + \cdots + X_w}{w},
$$
where $X_i$ is the indicator of $C(x_i) = 1$. If we sample $x_1,\ldots,x_w$ at random, then $X_1,\ldots,X_w$ are independent Bernoulli random variables whose expectation is $\Pr_{x \in D}[C(x) = 1]$. Chernoff's bound shows that their average is concentrated around their expectation.
Applying the union bound
The probability that a choice of $x_1,\ldots,x_w$ is bad for a specific circuit $C$ is $e^{-\epsilon^2 w}$. The probability that a choice of $x_1,\ldots,x_w$ is bad for one of $N$ different circuits is at most $Ne^{-\epsilon^2 w}$. Hence if $Ne^{-\epsilon^2 w} < 1$, the probability that a choice of $x_1,\ldots,x_w$ is good to all $N$ circuits is positive, hence there exists such a choice which is good to all $N$ circuits.
Since $w$ is in the exponent, the minimal $w$ needed to satisfy $Ne^{-\epsilon^2 w} < 1$ scales only logarithmically in $N$.


Linear time algorithm for least positive integer missing from array

Hint (if extra memory is allowed): It is enough to determine which of the elements $1,\ldots,n$ are in the input array. Using an auxiliary array, you can accomplish this in $O(n)$.


Total functional computable real numbers

The set of higher-order primitive recursive reals is essentially the class of functions $\mathbb{N}\rightarrow\mathbb{N}$ which can be represented by a term $\mathrm{Nat}\rightarrow\mathrm{Nat}$ in Gödel's system T.

Since every such function is total, and every well-typed term in the system can be enumerated effectively, there is a relatively easy proof by diagonalization that there is some computable real which cannot be represented.


https://www.cs.kent.ac.uk/people/staff/sjt/TTFP/ - This book.

A type for a parameter is like a precondition, and a type for a return value is like a postcondition.  Structs function as an AND operator, and Unions function as an OR operator.  When you say

performTransaction(x : DollarAmount) : Result

If x had to be constructed as a valid DollarAmount type, then this function is only callable if that was possible.  Also, the Result type is guaranteed to have some fields on it (error codes, transaction id, etc); and performTransaction has to construct the object to give it to you.  So, if you view statements like "x : int" as "x is proven to be an integer", then it is not a stretch to have something more elaborate like:  " x : int, x > 0, x < MAXINTEGER " to assert that x is a positive integer (a DependentType is a type that depends on the value, typically notNull, notZero, etc).

You can make functions take in very specific types that indicate an initial state, and return new types that indicate new states; and use types to enforce constraints on following a state machine - at compile time in many cases.


Finding a tight bound for a recurrence relation

You just need to expant it (suppose $n$ is even) and using mathematical induction:
$$T(n) = n + (n-2) + T(n-4) = n + (n-2) + (n-4) + \cdots + 4 + 2 = $$
$$2 ( 1 + 2 + \cdots + \frac{n}{2}) = 2\frac{\frac{n}{2}(\frac{n}{2}+1)}{2} = \frac{n(n+2)}{4} = \Theta(n^2)$$


I think the LHS is assumed by argument to be: $d[v_{i}]= \Sigma_{j=1}^{j=i} w(v_{j-1},v_{j})$. Since $d[v_{i-1}]= \delta(s,v_{i-1})$ = $min$$\{w(p) : s \rightsquigarrow^p v_{i-1}\} $  on the RHS, where $w(p)= \Sigma_{j=1}^{j=k}w(x_{j-1},x_{j})$ for any path $p: x_{0}=s, ... ,x_{k}=v_{i-1}$, we have the inequality $d[v_{i}]\geq d[v_{i-1}]+w(v_{i-1},v_{i})$.


Correspondence between automata and formal grammars?

The expression "one-to-one correspondence" seems a little too strong for me. It suggests that for every grammar there is a specific automaton. It should be read as: for every grammar an automaton can be constructed for the same language and vice-versa.

Context-sensitive languages are accepted by linear bounded automata and generated by context-sensitive grammars.
Context-sensitive grammars have productions of the form $\beta A \gamma \to \beta\alpha\gamma$ where $A$ is a nonterminal and $\alpha$ is nonempty. They are equivalent to length-increasing (more properly noncontracting, or monotone) grammars, which have the form $\alpha\to \beta$ where $|\alpha| \le |\beta|$ (usually $\alpha$ is assumed to include at least one nonterminal).

The languages of Turing machines are generated by unrestricted, or type-0, grammars. See Chomsky Hierarchy.


The accounting method relies on two arguments. The first is that in any sequence of $n$ operations, you never run out of coins. That is, however you choose to distribute the coins and pay for the operations, no sequence of operation will lead your scheme to a negative balance. The question remains of what this has to do with running time. Now the second argument comes into play, you want the running time to be bounded by the number of chips spent (without this claim, we have nothing relating the amortized running time with our chips distribution scheme). We can conclude that if you have devised a scheme satisfying those two properties, in which $C$ is the maximal amount of chips drawn in a single operation (where the maximum is taken over different types of operations), then the amortized running time is bounded by $C$.
This sheds some light on how to choose the number of chips per operation. I want to draw, for some element $x$, a number of coins that will suffice for all future operations involving $x$ (think of the insertion of $x$ as an element being born, and you attempt to compute how much money you will need from childbirth all the way to college). The tricky thing is that $x$ can be involved in an unbounded number of operations. Each extension of the array requires moving $x$, so I don't know how to determine the number of coins that will suffice to put $x$ through its entire existence. We can overcome this by having each element pay for his part in the first extension after its insertion.
Suppose that you just extended your array from size $k$ to size $\lceil(1+\alpha)k\rceil$. You would need to add an additional $\lceil(1+\alpha)k\rceil - k$ elements before the next extension, which will require $\lceil(1+\alpha)k\rceil$ operations. Let us try to construct our distribution scheme in such a way that only those new elements would pay for the next extension. Let $C$ be the number of coins requested for each insertion which allows this. It suffices that $C\cdot \left(\lceil(1+\alpha)k\rceil - k\right)\ge \lceil(1+\alpha)k\rceil$, or equivalently $C\ge\frac{\lceil(1+\alpha)k\rceil}{\lceil(1+\alpha)k\rceil - k}$. Since $\frac{\lceil(1+\alpha)k\rceil}{\lceil(1+\alpha)k\rceil - k}\le 1+\frac{k}{\lceil(1+\alpha)k\rceil - k}\le 1+\frac{k}{(1+\alpha)k-k}=1+\frac{1}{\alpha}$, it suffices to ask for $1+\frac{1}{\alpha}$ coins. Recalling that you also need a coin for the insertion itself yields the desired result of $2+\alpha^{-1}$.


How many recursively enumerable sets are there?

Countably infinite. Each RE set corresponds to a TM $M$ recognizing that RE set, where the set of all TMs is countably infinite.


Good motivation for parallel data structures and algorithms

The quintessential example is large-scale physics simulations, say "electronic" wind tunnel or protein folding (i.e. "finding new medicines"). Both are hugely expensive in terms of computation cost, but yield themselves well to parallelization.

Another area in which parallelization is important is "big data", say search engines. When dealing with big data you need to divide the work among many processors. However often in these cases, most of the work is done in an "embarrassingly parallel" fashion, in which each processor does its share of work, and everything is combined in the end; you could (but don't have to) argue that this is not an interesting example for parallel algorithms.

Yet another example is computer animation, say for the movie industry. This example probably has the same shortcoming as the previous one.

What is common to all three examples is that computation is very costly, and cannot be executed sequentially within a reasonable span of time. Hence the need to distribute the work among several computers (or processors, or cores).

Another possible use case is when you want answers really fast. Here an example could be real-time cryptanalysis during a war: you want your answers in one hour rather than one day, and it makes a big difference. A similar example is real-time TV studios, which probably benefit from distributed computing as well. Chess-playing machines and the like also belong to this category. Big data also shows up in this category – when interactively exploring data, you would like queries to run in reasonable time.


One systematic way to analyze these problems is to rewrite the function in continuation-passing style. For our purposes this means that the function takes an extra argument which is another function describing the postprocessing that is to be applied to the returned value. Your third function F in continuation-passing style would look like
fn F(x, k):
  if p(x):
    return F(a(x), k ∘ h)
  else:
    return k(b(x))

where ∘ denotes function composition. Note that F is now tail recursive.
You can then look for alternate (more efficient) representations of the continuation argument. In this case, the continuation always has the form $k_0\circ h\circ\cdots\circ h = k_0\circ h^i$ where $k_0$ is the continuation passed by the external caller. This can be represented by two arguments, $k_0$ and $i$:
fn F(x, k0, i):
  if p(x):
    return F(a(x), k0, i+1)
  else:
    x = b(x)
    repeat i times:
      x = h(x)
    return k0(x)

If you convert this to an iterative function in the usual way, and assume the caller always passes the identity function and zero for the second and third arguments, you get your iterative version of the function.
Usually you won't find such a concise encoding for the continuation. But quite generally the continuation will either be the original continuation, or one of a finite number of other functions that contains the previous continuation as a free variable (and possibly some other free variables). You can represent this as an array with one element for each "level", each element being a function number and the values of the non-continuation free variables. When you recurse downward you push another element, and when you return upward you pop an element. This gets you a stack-array-based iterative algorithm with the same space and time complexity as the original algorithm, but probably better constant factors.


Determine whether a sorted array contain at least 4 distinct elements in O(log n) time

Here is a cleaner and better way to solve the problem.
# Return the smallest index where the element is bigger than `A[start_index]`.
# If `len(A)` is returned, no element is bigger than `A[start_index]`.
def next_bigger_element(start_index, A):
    lo, hi = start_index, len(A)
    while lo + 1 < hi:
        mid = (lo + hi) // 2
        if A[mid] == A[start_index]:
            lo = mid
        else:
            hi = mid
    return hi

def distinct_elements_at_least(k, A):
    if len(A) == 0:
        return k <= 0
    index = 0
    count = 1
    # keep finding the next bigger element until `k` elements have
    # been found or we have reached the end of the array.
    while count < k and A[index] != A[-1]:
        index = next_bigger_element(index, A)
        count += 1
    return count >= k

To find whether A contains at least 4 distinct elements, just call distinct_elements_at_least(4, A).
This program works correctly for any given number k. For example, it can be used to check whether A has 0 element  or whether A has 7 distinct elements. For any fixed k, it works in $O(\log n)$ time as at most k binary searches on an interval of size at most n are done.

If you do not mind import bisect, you may prefer the following shorter code, since method next_bigger_element is no longer needed.
from bisect import bisect_right

def distinct_elements_at_least(k, A):
    if len(A) == 0:
        return k <= 0
    index = 0
    count = 0
    while index < len(A) and count < k:
        count += 1
        index = bisect_right(A, A[index], index + 1)
    return count >= k


How to Compute the Fixed Point on a DataFlow Lattice

You don't compute the least fixpoint of a lattice; you compute the least fixpoint of a function $f$.  The standard method is to use a method called chaotic iteration, which is exactly the iterative algorithm described in your quote: set $x_0 := \bot$, $x_1 := f(x_0)$, $x_2 := f(x_1)$, etc., and keep iterating until you reach $i$ such that $x_i = x_{i+1}$; the resulting $x_i$ is the least fixpoint of $f$.

In some cases it is possible to speed this up for a particular function $f$, but don't worry about this at this stage.

It's possible to view the process above as in some sense simulating the execution of the program, but I find it likely that this viewpoint is going to lead to confusion, so I'm not sure I would recommend trying to understand it that way.  Iteratively evaluating $f$ is not the same as iterating through the program points of the program.

Talk about splitting the program up is largely irrelevant to your question about how to compute a least fixpoint.  There are two steps: convert the program to a function $f$; find the least fixpoint of $f$.  The business about dividing up the program is relevant to how you convert the program to $f$, but not relevant to how you compute the fixpoint of $f$ (at least, not at the basic level).


Worst Case running time of the Minimum Vertex Cover Approximation algorithm

It depends on which data structure you use to store the graph.

For example, suppose the nodes are represented as $0,\ldots,n-1$, and the edges are stored as a list of pairs of nodes. We can build an boolean array $\mathrm{arr}$ of length $n$ initialized with all $\texttt{true}$s, and when a node $i$ is deleted, we simply mark $\mathrm{arr}[i]$ as $\texttt{false}$. Each time we deal with an edge, we first check if any of its endpoints is deleted to see if the edge has already been covered. With such data structures, your algorithm runs in $O(n^2)$.


Transition and configuration of Turing machine

Notations vary, but "$0, 1 \rightarrow R$" can be short for "$0 \rightarrow R$ and $1 \rightarrow R$."

A configuration is a way of writing the current state of the TM, the symbols on the tape and the current position of the tape. Here's a common way to write a configuration: if the state is $q_0$, the tape has $101$, and the head is pointing at $0$, write $1q_001$.


Sliding Window Dictionary String Matching

The set of all $k$-length strings that contain every pattern in $\Pi$ is regular; call it $L$.  (It is $(\Sigma^* \pi_1 \Sigma^* \cap \dots \cap \Sigma^* \pi_m \Sigma^*) \cap \Sigma^k$.)  From this, you can form a nondeterministic finite-state automaton (NFA) that recognizes $\Sigma^* L$.  Next, convert this to a DFA.  Finally, run the DFA across the input string $s$.  You can then obtain all locations in the string where the DFA is in an accepting state; each such location  is an index $i+k$ so that $s[i:i+k]$ matches all patterns in $\Pi$.

The running time will be linear in $|s|$ and the size of the DFA.  I expect the size of the DFA to be exponential in $\Pi$ and $k$, but independent of $|s|$.  So, if you only care about the dependence on $|s|$, this algorithm might meet your requirements.  If you additionally care about the dependence on $\Pi$ and/or $k$, I do not expect this will meet your requirements.


The set of valid sentences in FO is not decidable as a consequence of rec. inseparability

The chosen finite axiomatization of $\mathbb N$ is consistent, since $\mathbb N$ is a model for them. Hence, any sentence provable from it must be satisfiable (e.g. by $\mathbb N$).

From this, we get that the set of provable sentences is disjoint from the set of unsatisfiable formulas.

Hence, the set of unsatisfiable formulas must be undecidable, otherwise we would have separability (taking $R$ to be the set of unsatisfiable formulas), and we would contradict the theorem.

Hence, the set of valid formulas must be undecidable as well, since we have the reduction "$P$ unsatisfiable $\iff \lnot P$ valid" (also mentioned by SimonJ above).


How is the implementation of pipes in a OS

Like message passing.  The kernel allocates a private buffer for storing the data that has been sent and is waiting to be delivered to the recipient.

For more details, see:

http://www.slideshare.net/divyekapoor/linux-kernel-implementation-of-pipes-and-fifos
http://linux.omnipotent.net/article.php?article_id=12504&page=-1

In the future, please do more research before asking.  We expect you to do some serious research before asking.  The links above showed up in the first few responses to my first Google search, which is a hint that you should have done more research on your own.


Frigo's cache-oblivious algorithms paper

The version of the paper I am reading does not contain that statement on page 3 that you quote, "An $s \times s$ submatrix is stored in $\Theta(s+s^2/B)$ cache lines." However, it does state that the authors are going to consider matrix multiplication in the case the matrix is stored in row-major order.

In that layout, matrix location $(i,j)$ is stored at memory location $m*i + j$, where $m$ is the number of columns in the matrix. If $m \geq B$ where $B$ is the cache line size, successive rows of an $s \times s$ submatrix will occupy distinct cache lines.

As such, there are at least $s$ lines occupied. As you noted, there are at least $s^2/B$ cache lines occupied, since there are $s^2$ elements and only $B$ fit in a cache line. So, the value is $\Theta(\max(s, s^2/B))$ when $m \geq B$, and in Landau notation, maximum and sum are interchangeable.


Good characterization of unsatisfiable Horn3SAT formula?

You should not expect a proof that is asymptotically shorter than the formula itself.  For instance, consider

$$(x_1 \implies x_2) \land (x_2 \implies x_3) \land \dots \land (x_{n-1} \implies x_n) \land x_1 \land \neg x_n.$$

This formula is not satisfiable, but any proof of unsatisfiability will need to have size $\Omega(n)$.

If you're willing to accept a "proof" of size $n$, then the formula itself arguably qualifies as a proof (as it's easy to check that a given formula is not satisfiable).

Alternatively, any chain of deductions that ends in a contradiction qualifies as a proof, where each step in the chain is a variable and its inferred truth value, as justified by a clause in the Horn3SAT formula and previously inferred variable truth values.  If the formula is not satisfiable, then there must exist such a chain of deductions of size $O(n)$.  The chain of deductions is easily verifiable and thus constitutes a proof of unsatisfiability.  In other words, we derive a directed implication graph from the input Horn3SAT formula; the proof of unsatisfiability is then a directed path in the graph from some $x_i$ to $\neg x_i$.

If none of these meets your needs, you'll need to define what you're looking for more carefully.


Is “Find the shortest tour from a to z passing each node once in a directed graph” NP-complete?

If I understood well the question, things are clearer if you draw the graph in this way:

And you can use the following polynomial time greedy algorithm to find an Hamiltonian path from the two endpoint nodes of the bottom line.

Suppose that the nodes on the bottom line are $B_1,B_2,...,B_n$ and the nodes on the upper line are $U_1,U_2,U_m$. You need to find an Hamiltonian path from $B_1 \to B_n$.

If you are on node $B_i$, move to the first node $U_j$ linked to it (first means leftmost in the upper chain), then scan $U_{j+1}, U_{j+2},...$ until you find a link from $U_{j+k}$ to $B_{i+1}$ and such that if $j+k<m$ there is another link from $B_{i+l}, l>i$ to $U_{j+k+1}$ (that will allow you to complete the upper line). If such $U_{j+k}$ exists, add edges $B_{i}\to U_{j} \to ... \to U_{j+k} \to B_{i+1}$ to the final path, delete those nodes from the set and repeat the procedure from $B_{i+1}$.
If such $U_{j}$ doesn't exist, add the edge $B_{i} \to B_{i+1}$ and repeat the procedure from $B_{i+1}$.


Research work on computational models for a "specific" person's behaviors

this is a broad area now overlapping with big data and (mass) surveillance technology. here are a few refs with scientific elements/ angles/ leads/ papers/ books etc. and reference to a new field of "social physics"

‘Social Physics’ Harnesses Big Data to Predict Human Behavior / Leopold
'Big data' reveals human interests, behavior / Kullman, physorg
What Can Big Data Ever Tell Us About Human Behavior? / Zwilling, Forbes


I'll be using the solution to $Q = \alpha Q \cup \beta$ given by $Q = \alpha^* \beta$, essentially as you would go solving a system of linear equations by hand:

$$
\begin{align*}
Q_0 &= a Q_0 \cup b Q_1 \cup \epsilon \\
Q_1 &= (a \cup b) Q_1 \cup \epsilon
\end{align*}
$$
From the first equation you have $Q_0 = a^* (b Q_1 \cup \epsilon)$, the second one reduces to $Q_1 = (a \cup b)^* \epsilon = (a \cup b)^*$. Replacing $Q_1$ in $Q_0$ gives:
$$
Q_0 = a^* (b (a \cup b)^* \cup \epsilon)
    = a^* b (a \cup b)^* \cup a^*
$$


Example divide and conquer algorithm with recurrence T(n) = T(n/2) + O(n)

Bottom-up heap construction. Choose one application of sift-down as your unit of measurement. Then the recurrence is $T(n) = T(n/2) + n$.

If you want to go beyond that, you can say that choosing sift-down as a unit for measurement isn't quite accurate, and its runtime depends on the height $h$ of heap being sifted down in. But you can show that bottom-up heap construction is still $O(n)$ due to

$$0\cdot n + 1\cdot \frac{n}{2} + 2\cdot \frac{n}{4} + \cdots + h\cdot 1 = \sum_{h=0}^{\lg n} h\frac{n}{2^h} < n\sum_{h=0}^\infty \frac{h}{2^h}$$

and showing (or simply stating without proof in case you feel the students are not ready yet) that $\sum_{h=0}^\infty \frac{h}{2^h}$ converges to a constant.


Solving recurrence relations with two variables

The standard technique is to notice that your recurrence is just Pascal's identity, and so
$$
T(n,k) = \binom{n}{k}
$$
is a solution to the recurrence. There are other solutions, for example $T(n,k) = 2^n$, and multiples of both.

In your case, the binomial coefficient satisfies the initial conditions, so it is the solution.

Now, let's solve it using generating functions. Let
$$
f(x,y) = \sum_{n,k} T(n,k) x^n y^k.
$$
The initial conditions imply that $T(0,0) = 1$ and $T(0,k) = 0$ for $k > 0$. Also, $T(n,0) = 1$ for all $n$. Applying the recurrence for all $n,k>0$ and using these base cases, we get
$$
\begin{align*}
f(x,y) &= \sum_{n=0}^\infty x^n + \sum_{n,k>0} [T(n-1,k-1)+T(n-1,k)] x^n y^k \\ &=
\sum_{n=0}^\infty x^n + \sum_{n,k} T(n,k) x^{n+1} y^{k+1} + \sum_{\substack{n \geq 0\\k>0}} T(n,k) x^{n+1} y^k \\ &=
\sum_{n=0}^\infty x^n + xyf(x,y) + xf(x,y) - \sum_{n=0}^\infty x^{n+1} \\ &=
1 + (x+xy) f(x,y).
\end{align*}
$$
Therefore
$$
f(x,y) = \frac{1}{1-x-xy}.
$$
The coefficient of $x^n y^k$ is the number of walks that start at $(0,0)$, end at $(n,k)$, and at each step, either move right or diagonally. Clearly they have to move right exactly $n-k$ times (so if $n < k$ the coefficient is zero) and diagonally exactly $k$ times, but the order is not important. Therefore the number of walks is $\binom{(n-k)+k}{k} = \binom{n}{k}$.


This is dominating set, not vertex cover.

The graph has the set of intervals as vertices and two vertices are adjacent if the corresponding intervals overlap. Such a graph is known as an interval graph, which is a special case of intersection graphs (vertices are sets of some kind, and two vertices are adjacent if their sets intersect).

You're looking for a minimum-sized set $S$ of intervals such that every other interval intersects at least one interval in $S$. In the interval graph, this means that you're looking for a minimum-sized set $S$ of vertices such that every other vertex is adjacent to $S$: this is a dominating set.

The problems of omputing minimum vertex covers and minimum dominating sets are both NP-hard on general graphs. However, on interval graphs, both problems can be solved in polynomial time, by

M.V. Marathe, R. Ravi and C. Pandu Rangan, Generalized vertex covering in interval graphs.  Discrete Applied Mathematics, 39(1):87–93, 1992.
K.S. Booth and J.H. Johnson, Dominating sets in chordal graphs. SIAM Journal on Computing, 11(1), 191–199, 1982.

In the former case, a $2$-vertex cover is an ordinary vertex cover; in the latter, the algorithm actually works for all for all directed-path graphs, and every interval graph is a directed-path graph.


How to prove that $3$-Spanning-Tree decision problem is $NP$-Complete

Reduce from Hamiltonian path, attach a dummy vertex to each original vertex. After removing dummy vertices, each original vertex would have degree at most $2$ in the (remaining) of the spanning tree. A connected graph every vertex of which has degree at most $2$ is a path or a cycle.


Why is there no deterministic algorithm for determining the majority vote of a recursive 3 branch tree without inspecting all the leafs?

Yes, you are misunderstanding the algorithm. While I explain your misunderstanding below, in general, when such a misunderstanding occurs, see if you understand what the algorithm is trying to do, and then try to match your understanding with what is written.

While there are numerous errors in textbooks, usually they are slight and easy to correct. Whenever an error seems to have occurred (which doesn't seem to be the case here), see if you can try to correct it by making some small change to the argument.

In this case, the first ancestor of the second leaf which has at most one sibling determined is the leaf itself, which has one sibling determined. According to the strategy, our answer to the second leaf would be complementary to our answer to the first leaf.

Your misunderstanding might stem from the fact that for you a node is not considered its own ancestor. However, for this strategy to work, a node must be considered its own ancestor, as your example shows. Presumably the text defined ancestor correctly to include the node itself, but even if it doesn't you could correct the proof by changing slightly the meaning of ancestor. This demonstrates my points above regarding reading mathematical texts.


Is smn theorem the same concept as currying?

Yes, it is the same thing.

Currying is a concept from $\lambda$-calculus. It is a transformation between $A \times B \to C$ and $A \to (B \to C)$. Think of this as "if we have a function of two arguments of types $A$ and $B$, then we may fix the first argument (of type $A$), and we will get a function of the remaining argument (of type $B$)". In fact, this transformation is an isomorphism. This is made mathematically precise by mathematical models of (typed) $\lambda$-calculus, which are cartesian closed categories.

There is a category of numbered sets. A numbered set is a pair $(A, \nu_A)$ where $A$ is a set and $\nu_A : \mathbb{N} \to A$ is a partial surjection, i.e., a map from numbers onto $A$, which may also be undefined. If $\nu_A(n) = x$ then we say that $n$ is a code of $x$. In computability theory there are many examples. Whenever we encode some information with a number we get a numbered set. For instance, there is a standard numbering $\varphi$ of partial computable functions, so that $\varphi_n(k)$ is the number computed by the partial computable function encoded by $n$ when applied to $k$. (The result may be undefined.)

A morphism of numbered sets is a realized map $f : (A, \nu_A) \to (B, \nu_B)$, which means that there exists $n \in \mathbb{N}$ such that $f(\nu_A(k)) = \nu_B(\varphi_n(k))$ for all $k$ in the domain of $\nu_A$. This looks complicated, but all it says is that $\varphi_n$ does to codes what $f$ does to elements. It is the mathematical way of saying that "program $\phi_n$ implements function $f$".

Here is the punchline: the category of numbered sets is cartesian closed. We may therefore interpret the typed $\lambda$-calulus in it, and ask what program implements the currying operation. The answer is: the program given by the s-m-n theorem.


Understanding implemetation of the Toffoli gate using other gates

When applying quantum operations you always:

Simplify everything down to individual self-contained cases.
Apply the operation separately to each case.
Recombine the answers.

So, in the case of applying a CNOT to the state $|1\rangle \otimes (H \cdot |1\rangle)$, you:

Simplify things. We don't want that $H$ in the way. Apply it. The state is $|1\rangle \otimes (\frac{1}{\sqrt 2}|0\rangle - \frac{1}{\sqrt 2}|1\rangle)$.
Separate things. Distribute the tensor product over the subtraction. The state is $\frac{1}{\sqrt 2}|1\rangle \otimes |0\rangle  - \frac{1}{\sqrt 2}|1\rangle \otimes |1\rangle$. Or, for short, just $\frac{1}{\sqrt 2}|10\rangle  - \frac{1}{\sqrt 2}|11\rangle$.
Apply the operation separately to each case. If the second bit is our control, then in $|10\rangle$ the control isn't satisfied and nothing happens while in $|11\rangle$ the control is satisfied and we toggled to $|01\rangle$. Apply that to each part of $\frac{1}{\sqrt 2}|10\rangle  - \frac{1}{\sqrt 2}|11\rangle$ and you end up with $\frac{1}{\sqrt 2}|10\rangle  - \frac{1}{\sqrt 2}|01\rangle$.
None of our output cases overlapped when being added together, so there's no need to combine anything.

You might get a sense of this by adding state displays to Quirk while it cycles through the inputs into your Toffoli circuit.


How to show that a "reversed" regular language is regular

So given a regular language $L$, we know (essentially by definition) that it is accepted by some finite automaton, so there's a finite set of states with appropriate transitions that take us from the starting state to the accepting state if and only if the input is a string in $L$. We can even insist that there's only one accepting state, to simplify things. Then, to accept the reverse language, all we need to do is reverse the direction of the transitions, change the start state to an accept state, and the accept state to the start state. Then we have a machine that is "backwards" compared to the original, and accepts the language $L^{R}$.


Boat riddle as a combinatorial optimization problem?

The river crossing problem using integer programming is solved by Börndorfer et al. in [1].

[1] Borndörfer, Ralf, Martin Grötschel, and Andreas Löbel. Alcuin's transportation problems and integer programming. ZIB, 1995.


Finite automaton for all words whose length $n$ satisfies $\operatorname{gcd}(n,504) \geq 6$

The number $504$ has $4\cdot3\cdot2=24$ divisors:
$$1,
 2,
 3,
 4,
 6,
 7,
 8,
 9,
 12,
 14,
 18,
 21,
 24,
 28,
 36,
 42,
 56,
 63,
 72,
 84,
 126,
 168,
 252,
 504$$
Out of these, $20$ are at least $6$:
$$
 6,
 7,
 8,
 9,
 12,
 14,
 18,
 21,
 24,
 28,
 36,
 42,
 56,
 63,
 72,
 84,
 126,
 168,
 252,
 504$$
For an integer $n$, $\operatorname{gcd}(n,504) \geq 6$ iff $n$ is a multiple of one of these numbers. To check this, we don't really need to go over all $20$ possibilities. For example, if $n$ is divisible by $12$ then it is also divisible by $6$, so we can remove $12$ from the list. The list narrows down to only $4$ options:
$$
6,7,8,9
$$
That is,
$$
\operatorname{gcd}(n,504) \geq 6 \Leftrightarrow 6 \mid n \text{ or } 7 \mid n \text{ or } 8 \mid n \text{ or } 9 \mid n
$$
You can check the condition on the right using an NFA with $6+7+8+9 = 30$ states (or $31$ states if you do not allow multiple initial states).


A memoryless channel is one where the probability of an error at a particular bit is independent of what happened at all prior bit positions.  A channel can have memory if errors are correlated across bit positions.

For instance, consider the following simple binary channel: if there was no error in the prior position, then there is a probability of 0.1 that this position and the next 7 positions are all flipped (have an error); otherwise (with probability 0.9) this position is not flipped (no error).  This would be an example of a channel with memory, because the probability of error for a particular bit depends upon the location of previous errors.  Slightly more generally, bursty errors are an example of a channel with errors.

Note that the question of whether the channel has memory is independent from whether the code has memory.  You can use a memoryless code with a channel that has memory; or use a code with memory with a memoryless channel.


What is the meaning of this pseudo-code function?

"Implies" in the English language indicates that there is room for subjectivity. But this is not standard English you're looking at. When you read A⟹B as "A implies B" in Discrete Mathematics, it is just another way to say, "If A is true, then B is true." Formally, this is called material implication.

So the two ways you thought to read it are the same - as far as Comp.Sci. goes. Left to right and minimal imagination it reads (out loud),
"Return the truth of this assertion: For all q-sub-i that are members of subtreeNodes of q, isLeaf of q-sub-i implies eof of T-sub-sub-i."


Yes, that is exponential. Something is exponential if it is $2^{O(n^k)}$ for some $k$. You can write $3^{n/3}$ as $2^{n\frac{\log 3}{3 \log 2}}$, so it fits.

It would be more common to write $(3^{1/3})^n \approx 1.44^n$.


LALR(1) parsers and the epsilon transition

Your states and itemsets are not quite correct. The epsilon production must appear in relevant itemsets, and you have combined two states into one, which would produce a shift-reduce conflict if the epsilon production were added to the itemset (which should be done).

The following was generated with bison (using the --report=all command-line option); it differs from the theoretic model because the grammar has been "augmented" with an extra start symbol and an explicit end-of-input marker ($end). Also, it has done some table compression, so in the action tables, you can think of $default as meaning "either a or b".

It is worth explaining how State 0 comes about, since it shows how epsilon productions are handled (no differently from other productions).

We start with $accept: . S $end, by definition. ($accept is the starting state). Then the closure rule is applied as long as possible. Remember that the closure rule is: If any item in the itemset, the . is immediately before a non-terminal, add all the productions for that non-terminal with an initial .. Hence we add:

S: . A

continuing with A:

A: . B 'b'

continuing with B:

B: . B 'a'
B: .

We can't apply closure any longer, so we're done. Since the state now has an item with the dot at the end (the epsilon production for B), a reduction is possible.

State 0
    0 $accept: . S $end
    1 S: . A
    2 A: . B 'b'
    3 B: . B 'a'
    4  | .

    $default  reduce using rule 4 (B)
    S  go to state 1
    A  go to state 2
    B  go to state 3

State 1
    0 $accept: S . $end

    $end  shift, and go to state 4

State 2
    1 S: A .

    $default  reduce using rule 1 (S)

State 3
    2 A: B . 'b'
    3 B: B . 'a'

    'b'  shift, and go to state 5
    'a'  shift, and go to state 6

State 4
    0 $accept: S $end .

    $default  accept

State 5
    2 A: B 'b' .

    $default  reduce using rule 2 (A)

State 6
    3 B: B 'a' .

    $default  reduce using rule 3 (B)

In State 0, the closure rule has added the epsilon production (line 4). Furthermore, no item in the state 0 itemset has the point before a terminal. So with any lookahead, the parser is forced to reduce the epsilon production, after which it will use the goto function for state 0 to decide to move to state 3. (In your state machine, states 0 and 3 are conflated, but I do not believe this is correct.) State 3 will definitely shift a terminal; with the input ab$end, it will shift the a and move to state 6, which will then reduce a B. And so on.


Set of $\mathsf{NP}$-hard languages closed under set inclusion?

Indeed, if NP=P then every nontrivial problem is NP-hard, and in particular every nontrivial subset of an NP-hard problem (thus closing it to inclusion).


$\newcommand{\norm}[1]{\left\lVert#1\right\rVert}$
Denote the support of $f$ by $f_1\le f_2\le...\le f_s$. Given a frequency sequence $f$, denote by $E_{f,a}$ the random variable $\hat{f}_a$ where the stream frequencies are given by $f$ (the evaluation depends on the inner randomness of the sketch and the input stream).
The probability that the hash of one of the top $\ell=1/\epsilon^2$ elements collides with the hash of some given element $a$ is bounded by $\frac{\ell}{k}$ (union bound). Conditioning on the event that such a collision did not occur, the evaluation $\hat{f}_a$ does not depend on the top $\ell$ entries, as they do not affect the hash entry of $a$. More formally, conditioned on the event $C=\bigcap\limits_{i=0}^{\ell-1}\mathbb{1}_{h\left(f_{s-i}\right)\neq h(a)}$, $E_{f,a}$ and $E_{f^{res(\ell)},a}$ are equally distributed. This yields:
$$\Pr\left[\left|\hat{f}_a-f_a\right|\ge \epsilon\norm{f_{-a}^{res(\ell)}}\right]=
\Pr[C]\cdot \Pr\left[\left|\hat{f}_a-f_a\right|\ge \epsilon\norm{f_{-a}^{res(\ell)}}\big| C\right]+\\
\left(1-\Pr[C]\right)\Pr\left[\left|\hat{f}_a-f_a\right|\ge \epsilon\norm{f_{-a}^{res(\ell)}} \big|\overline{C}\right]\le\\
\Pr\left[\left|\hat{f}_a-f_a\right|\ge \epsilon\norm{f_{-a}^{res(\ell)}}\big| C\right]+\frac{1}{6}$$
Since $E_{f,a}, E_{f^{res(\ell)},a}$ are equally distributed (conditioned on $C$), the left hand term equals $\Pr\left[\left|\hat{f}_a-f_a\right|\ge \epsilon\norm{f_{-a}}\right]$, which you can bound by $1/6$ with your original result.


Hint. Your answer is plain wrong. First, it trivially does not work if $n$ is odd. But it is also wrong if $n$ is even (except for $n = 2$). Just compute the minimal automaton of $\{aabb,abab,abba,baab,baba,bbaa\}$ to be convinced. Your formula gives $3\cdot 2^2 - 1 = 11$ states but the minimal automaton only has $10$ states.


Representing Negative and Complex Numbers Using Lambda Calculus

First encode natural numbers and pairs, as described by jmad.

Represent an integer $k$ as a pair of natural numbers $(a,b)$ such that $k = a - b$. Then you can define the usual operations on integers as (using Haskell notation for $\lambda$-calculus):

neg = \k -> (snd k, fst k)
add = \k m -> (fst k + fst m, snd k + snd m)
sub = \k m -> add k (neg m)
mul = \k m -> (fst k * fst m + snd k * snd m, fst k * snd m + snd k * fst m)

The case of complex numbers is similar in the sense that a complex number is encoded as a pair of reals. But a more complicated question is how to encode reals. Here you have to do more work:

Encode a rational number $q$ as a pair $(k,a)$ where $k$ is an integer, $a$ is natural, and $q = k / (1 + a)$.
Encode a real number $x$ by a function $f$ such that for every natural $k \in \mathbb{N}$, $f k$ encodes a rational number $q$ such that $|x - q| < 2^{-k}$. In other words, a real is encoded as a sequence of rationals converging to it at the rate $k \mapsto 2^{-k}$.

Encoding reals is a lot of work and you do not want to actually do it in the $\lambda$-calculus. But see for example the etc/haskell subdirectory of Marshall for a simple implementation of reals in pure Haskell. This could in principle be translated to the pure $\lambda$-calculus.


How to draw Turing machine for multiplying a number by 2 in base 10

To elaborate on the method described by Yuval in the comment, first, construct a DFA with output as follows: Let the state space be $Q=\{q_i \mid 0 \le i \le 9\}$, and input and output alphabet be $\Sigma = \{i \mid 0 \le i \le 9\}$. The initial state would be $q_0$. Let the DFA read the decimal number in reverse. For any state $q_i$, on reading $d$, you move to state $q_j \in Q$ and output $k \in \Sigma$ if $10j + k = 2d + i$ (Why can you always find such $j,k$?).
Basically, you are trying to store the carry while outputting the least significant digit of the multiplication of the current digit by 2 after adding the last carry, just as the grade-school multiplication.
Then, you can readily create a TM using this DFA with output that does the required multiplication.


When a computer reads a PDF...
You can take several perspectives.

From Acrobat reader, it asks the operating system to read a file, copies it to memory then interprets drawing commands. From applications POV, caches don't exist.

Of course, there is nowadays a disk cache in RAM, where the last used sectors are kept for shorter access time. Some OS even trick the MMU between the disk cache and application address spaces so that data is not even copied. That cache is not visible to applications (which can also have their own caching, for example pre-rendered pages...)

From the operating system, CPU caches needs sometimes to be manually managed, on some platform, particularly when there are peripherals that are modifying memory without CPU intervention ("non coherent DMA"). It could be the disk controller reading that PDF file. On current high performance CPUs, the kind you find in computers or tablets where Acrobat can be installed, the CPUs practically manage their caches transparently.

So, CPU caches are mostly hidden to software.

Cache are made of two parts : the datas, and the tags.
Datas contains a portion of RAM area.
Tags indicate which part of the RAM is in the cache.
Data is grouped in chunks ("cache line"), usually 32 to 128 consecutive bytes.

When a CPU accesses its caches, it lasts usually less than 5 cycles for L1 caches, and less than 20 cycles for L2 caches.
Accesssing DRAM can waste hundreds of cycles.
Despite being very small (for example 32kB L1 compared to 4GB DRAM), they are incredibly efficient, because, in reality, accesses are often grouped, or consecutive, or repetititve, so that the same parts of main memory are accesses several times.


Normalizing edge weights and the effect on Dijkstra's algorithm

Your idea does not work. Adding an absolute value to every edge wont preserve shortest paths. To see this take this graph:

u------v
|      |
|      |
a------b

with all edge weights 1 except for $uv$ where the weight is 4. The shortest $uv$ path goes via $u \to a \to \to b \to v$. But if you add a +2 to every edge, the sortest $uv$ path is $u\to v$.

There is however a reweighting scheme that works. Check out Johnson's algorithm, which is built around this. Simply speaking: add a dummy vertex $x$ connected to all other vertices with a zero weight edge and add to every weight of an edge $(i,j)$ the value $d(x,i) - d(x,j)$.


When does an extendible 1:1 p.c. function have a 1:1 computable extension?

Here is an example of an extendible, non-injectively-extendible p.c. function $\psi$ which nonetheless satisfies your conditions (and I think indicates in general that any sufficient condition will be quite complicated):

Let $\langle\cdot,\cdot\rangle$ be your favorite computable bijection $\mathbb{N}^2\rightarrow\mathbb{N}$. We define $\psi$ as follows (with the role of "$2^k$" being  merely to control the range of $\psi$, and consequently show that just demanding that the range be "small" won't yield a sufficient condition):

Suppose $k$ is even. Let $a_k, b_k$ be the unique natural numbers such that $k=2\langle a_k,b_k\rangle$. We define $\psi(k)$ to be $2^k$ if $\varphi_{a_k}(a_k)$ halts strictly before $\varphi_{b_k}(b_k)$ does, and we let $\psi(k)$ be undefined otherwise.
Suppose $k$ is odd. Let $a_k, b_k$ be the unique natural numbers such that $k=2\langle a_k,b_k\rangle$+1. We define $\psi(k)$ to be $2^{k-1}$ if $\varphi_{b_k}(b_k)$ halts strictly before $\varphi_{a_k}(a_k)$ does, and we let $\psi(k)$ be undefined otherwise.

$\psi$ is clearly 1-1, p.c., of co-infinite range (indeed, the range is "computably coinfinite" in the sense that the complement of the range contains an infinite computable set; in jargon, the range of $\psi$ is non-simple), and extendible: it is extended by the function $x\mapsto 2^{2floor({x\over 2})}$. However, it's easy to show that it's not extendible to a 1-1 total computable function, essentially since such an extension would have to always guess correctly whether one program halts before another does.


First-order mutual-recursive functions Turing-complete or incomplete?

Roughly speaking, as a heuristic, if your language includes primitives of unbounded size as well as standard control structures (e.g., loops and conditional statements), the language is likely to be Turing complete.  (Credits: I'm just expanding on Dmitry's observation.)  I'll show a few examples below.
If your language doesn't have loops, you can simulate them with recursion.
Linked lists
If your language includes linked lists, it will be Turing-complete.
In particular, you can encode a Turing machine with two linked lists.  You split the tape into two pieces, the part to the left of the head and the part to the right of the head.  Let $L$ be a linked list of the symbols on the tape to the left of the head, and $R$ the symbols to the right.  The linked list should start with the symbols closest to the head and go outward.
Now you can simulate each of the individual operations of the Turing machine using a few lines in your programming language.  For instance, shifting the tape head to the right can be done by popping an item $x$ from the front of $L$, then pushing $x$ onto the front of $R$.  The finite-state control works on finite data and so can be expressed as a finite number of simple operations.  Now put an infinite loop around this, with each iteration of the loop simulating one step of the Turing machine, and you have built an interpreter for a Turing machine in your language.
Bigints
If your language includes bigints (i.e., integers that can be of unbounded size) and basic operations on them (e.g., add, multiply, compare, divide), then it will be Turing-complete.
In particular, you can simulate linked lists of items over a fixed alphabet using bigints.  Suppose you want to encode a linked list of bits.  Then you can encode this as a bigint by treating the sequence of bits in the linked list as the binary representation of an integer (the least significant bit is the first bit in the linked list, and so on).  Basic operations on the linked list can then be translated into operations on the integer.  For instance, popping a bit from the head of a linked list can be expressed as $b := L \bmod 2, L := (L-b)/2$; pushing a bit can be expressed as $L := 2L+b$; and so on.  More generally, if you have a linked list where each item is in the range $\{0,1,\dots,k-1\}$ (e.g., a tape alphabet of size $k$), then this can be viewed as an integer in base $k$.  There are some details -- for finite lists, you probably want to have one reserved symbol to indicate the end of the list -- but they don't change the general picture.
Now you can use this to simulate linked lists, and then use the construction above to simulate a Turing machine.


Meaning of this python modulo operator exercise?

Briefly, if $a$ is an integer and $b>0$ is a positive integers then you can find an integer $m$ and an integer $r \in \{0,\ldots,b-1\}$ such that
$$
a = mb + r.
$$
We say that $m$ is the quotient and $r$ is the remainder. For example, if $a=2$ and $b=4$ then $m=0$ and $r=2$.

When $b$ is allowed to be negative, the exact meaning is language-specific. You can work out the case of python by trying a few examples.


Not able to simplify a sum over reciprocals of $\log i$

The trick to evaluate these sums is integration. We have the following very useful inequality for a non-decreasing $f(i)$:
$$ \int_0^n f(x) dx \leq \sum_{i=1}^n f(i) \leq \int_1^{n+1} f(x) dx. $$
In your case, $f(i)$ is in fact non-increasing, and in that case we have
$$ \int_1^{n+1} f(x) dx \leq \sum_{i=1}^n f(i) \leq \int_0^n f(x) dx. $$
For example, we can estimate
$$ \int_2^{n+1} \frac{dx}{\log x} \leq \sum_{i=2}^n f(i) \leq \int_1^n \frac{dx}{\log x}. $$
Unfortunately, the antiderivative of $1/\log x$ is not an elementary function, but is known as the logarithmic integral $li(x)$. Asymptotically, $li(x) \sim x/\log x$, and so we deduce
$$ \sum_{i=2}^n \frac{1}{\lg i} = \Theta\left(\frac{n}{\log n}\right). $$
In this particular case, we can obtain these bounds directly. Since $1/\lg i \geq 1/\lg n$, we obtain a lower bound of $(n-1)/\lg n$. Conversely, for $i \geq \sqrt{n}$ we have $1/\lg i \leq 1/\lg \sqrt{n} = 2/\lg n$, and so
$$ \sum_{i=2}^n \frac{1}{\lg i} \leq \sqrt{n} \lg 2 + n \frac{2}{\lg n} = O\left(\frac{n}{\lg n}\right). $$
If you want to obtain better estimates on such sums, the way to go is Euler–Maclaurin summation, which can be used to obtain an asymptotic series for $\log n!$, for example.


Proving that a property is k-inductive with an SMT solver (parametric resettable counter)

I don't see any gap in your understanding.  What you wrote looks correct to me.

Perhaps the author meant to use the property $P := c \le n+1 \land n \ge 1$.  I think with that modification, $P$ becomes 1-inductive but not 0-inductive.  I suspect the author was looking for a simple example of a property that is 1-inductive but not 0-inductive, and missed a small detail.

Good job catching this!


Is there any difference between Time Complexity and Running time?

The terms, as they are used in computational complexity theory are different.

Running time is a property of an algorithm. It is the maximum number of steps the algorithm can run for, as a function of the length of the input.

Time complexity is a property of a computational problem. It is, essentially, the running time of the fastest possible algorithm for that problem.

Thus, we might talk about the time complexity of the sorting problem, and the running time of heapsort.  Informally, people often refer to the "time complexity" of an algorithm. Strictly speaking, this is incorrect, but there's only really one thing it could mean.

Note that we usually only quote the asymptotic behaviour of running times and time complexities, since we're usually not interested in the exact function, and it's usually too hard to figure out, anyway.

Note also that, in applied computing, "running time" may refer to the time taken for some program to run, as you might measure with a stopwatch.


Which of the following languages is accepted by this Pushdown Automaton?

I think the answer is a, $\{a^n b^{2n} | n > 0\}$.

First, the machine pushes $a$'s onto the stack until the first $b$. Then, for every two $b$'s in the string, it pops off one $a$. Then, if the machine is at the end of the string and the stack is empty, it accepts.

If the stack of $a$'s runs out while the machine is still popping pairs of $b$'s or there are $a$'s left in the stack when the last $b$ is popped, then the machine rejects.

  I am struggling to get my head around the concept of a PDA.

Notation varies, but in the diagram you provided, I think nop means "read the thing on top of the stack and leave it there" and pop means "read and remove the thing on top of the stack".

For more info, you could read the chapter on PDA's in Michael Sipser's book Introduction to the Theory of Computation.


Mapping many transition functions into two transition functions

Suppose that you have three options $o_1,o_2,o_3$.

You first guess whether to apply $o_1$ or not; if not, you stay in place.

If you didn't apply $o_1$, you guess whether to apply $o_2$ or $o_3$.

Here is how to implement it using transitions, using your example:
$$
\begin{align*}
&\delta_1(q_1,a) = (q_2,b,R) \\
&\delta_2(q_1,a) = (q_s,a,R) \\
&\delta_1(q_s,\sigma) = (q_t,\sigma,L) \\
&\delta_2(q_s,\sigma) = (q_t,\sigma,L) \\
&\delta_1(q_t,a) = (q_3,c,L) \\
&\delta_2(q_t,a) = (q_4,d,R)
\end{align*}
$$
Here $q_s,q_t$ are new states, and $\sigma$ is any tape symbol.


Your proposed approach doesn't work.  For some directed graphs there is no single vertex you can split to turn it into a DAG.  An algorithm only qualifies as a solution to the Hamiltonian Cycle problem if it solves the problem for all graphs.  It's not enough to solve the problem for a subset of "easy" graphs.


Construct a proof tree in Hindley-Milner with function overload

After some time I realized that is not possible to proof
\begin{align*}
\vdash (over\: eq:: Eq\: \alpha\: in\: inst\: eq :: Eq\:Int \:=\: eqInt\: in\: eq\:1\:2)::Bool
\end{align*}
 without suppositions about $1$, $2$ and $eqInt$ ( $\emptyset$ as the context). They need to be bound to the context , because they should be seen as build in
to the system. In alternative I could create new rules (like $const$ rules) for the integer numbers ($1$, $2$...) and for $eqInt$, that don't insert stuff to the context.

So, my final result is this proof tree:

I'm not sure if I can use $weakening$ in the context, but I did.

I hope that some one could comment something about my answer. If I'm right or if I created some non-sense.