What is the algorithm for Blockchain's Byzantine Fault Tolerance? This person was asked: "Why is a blockchain implementation different than a distributed consensus system like Raft?"

In part of their answer they replied:

  For one, Raft is not Byzantine fault tolerant, i.e., not designed to account for arbitrary failures. If a participant fails by telling different peers different things, consensus fails. In context of blockchain, this would be equivalent of a malicious consensus participant lying.

Another wrote:

  As others have mentioned, Blockchain has Byzantine Fault Tolerance. Raft and other consensus based systems such as Paxos do not.

My question is: What is the algorithm for Blockchain's Byzantine Fault Tolerance?

Actually the differences are more intricate than that. A problem here might be that the properties of "blockchains" are not very well specified and the term is used for a wide variety of things (going as far as simple databases) for marketing. So let's see what is out there.

When you are designing a fault tolerant system there are multiple properties to take into account. These include:

Crash or byzantine failures

  Should the system be designed to withstand nodes just stopping to do anything (i.e. no messages at all) or should it also consider nodes which exhibit arbitrary behaviour?

Eventual or strong consistency

  Should the system provide certainty, that some state is final and not revertible or are we okay with irreversibility with high probability?

Open or closed membership

  Is it known in advance (and to all nodes) who is participating in the protocol? E.g. a reliable database used by google has a defined number of nodes, which are known to all other nodes. In Bitcoin it is unclear even how many miners are participating in the consensus algorithm.

There are a few more things, but these are the most important ones. I am regularly contacted by people who want to use blockchain technology and the conversations always come down to figuring out what requirements regarding these three properties they have and then I recommend some system.

For the most well known ones the properties are:

Bitcoin / Ethereum: Byzantine failures, eventual consistency, open membership
RAFT / Paxos: Crash failures, strong consistency, closed membership
PBFT / Zyzzyva: Byzantine failures, strong consistency, closed membership

When choosing a system you try to take the easiest one possible, as the stronger models normally come with a large penalty in latency and throughput for transactions.

Crash failures are easier than byzantine failures. This is easy to show, as byzantine failures include crash failures. Most of the algorithms include some kind of voting. Having a majority is sufficient with crash failures to make decisions, while byzantine failing nodes might send different votes to different receivers. This might lead to two honest nodes seeing different results for the overall vote and getting out of sync.

Open membership is much more difficult than closed membership, as sibyl attacks, where an attacker generates many identities need to be counteracted by something like proof-of-work or proof-of-stake. This is the main new thing Bitcoin invented and that created the blockchain hype. A chain of blocks of transactions has existed before, as batched commits of transactions was a standard thing for at least 20 years before Bitcoin.

Applying this to the algorithms I listed:

The overhead of RAFT is small, PBFT and Zyzzyva already have a significant amount of communication overhead ( O(n^2) messages and a large number of signatures). Systems like Bitcoin and Ethereum have latencies in the order of minutes to hours (depending on your required level of security).


Examples of processes / problems that cannot be tackled by Turing Machines I know that there are problems that cannot be solved by any algorithm, such as the Halting problem.
I also know that some processes cannot be even adequately approximated by any Turing Machine (equivalently, any digital computer), meaning that some property of the process cannot be simulated due to its intrinsic nature. An example of this would be Chaos, and its non-periodicity.

My question is: are there any other interesting processes in nature that really are outside the realm of what Turing Machines / digital computers can tackle? Any other interesting problems (outside from the well-known textbook ones) that Turing Machines cannot solve?

The reason why I ask for this is that I'm teaching to computer science students, and I want to make sure they understand that computers are not all-powerful machines, but there are problems and phenomena that lie fundamentally outside the realm of possibilities of any digital computer.
What powerful examples could I use, other than Chaos and the Halting problem, to support my argument?

Thank you!

I'll address as answer only part of the question (see my comments for why not all of it). The interesting phylosophical part of the question is basically asking if the Church-Turing thesis (CTT) describes all that happens in the universe. This is much more a physics question than it really is a CS question. CTT has been extended to the Church–Turing–Deutsch principle to account for quatum computers; it basically states that a quantum computer can simulate any physical process in the universe.

So what about continuous processes that we normally model over $\mathbb{R}$? Well, there are two aspects of this:

Models of computation with infinite-precision real-numbers have been devised. Whether you think such a model is the "right" one for physical processes, depends on physics and...
There are tough issues like the Bekenstein bound, which limit the amount of information that can exist in a finite region of space as we currently understand it. For details on this latter issue, it's much better to ask on our physics sister site.

A bit more info with pointer to additional readings is found at https://mathoverflow.net/questions/54820/physics-and-church-turing-thesis


User level threads are transparent to the kernel? Find whether given statement True or False? Explain.

User level threads are transparent to the kernel?

My attempt :
False. Since, user level threads are managed by a user level library however, they still require a kernel system call to operate. It does not mean that the kernel knows anything about thread management. Not at all, it only takes care of the execution part. the lock of the cooperation between user level threads and the kernel is a known disadvantage.

Somewhere it explain as : "The kernel knows nothing about user-level threads and manages them as if they were single-threaded processes".
I found another statement "User level threads are transparent to OS and kernel level threads are scheduled by OS". It seems correct.
My question is :

Are user level threads transparent to the kernel? What is meaning of transparent here?

As, the linked answers and the explanations provided by your textbooks describe that, user level threads are transparent to the kernel, yes they are indeed.

Kernel Level threads are not transparent to the kernel, but user level threads are. Because you yourself said, that User Level Threads are managed by the User level library, and what happens is, the user level threads can get assigned to one or many kernel threads. About these kernel threads the kernel keeps track of (are not transparent to kernel). But it doesn't know which user threads have got assigned onto these kernel threads and how many.

Say, if five user threads are assigned onto one kernel thread and 4 other user threads are assigned onto another kernel thread, the kernel sees just two kernel threads (requesting execution) and doesn't know that there are altogether 9 threads, but it just knows that the program called the User Level Application(s) is(are) using two of the kernel threads.

I hope this helps. Also, I suggest you read the linked posts carefully. They're pretty explanatory.


A question about parallel algorithm complexity When in a Parallel algorithm we say:

  "This algorithm is done in $O(1)$ time using $O(n\log n)$ work, with $n$-exponential probability, or alternatively, in $O(\log n)$ time using $O(n)$ work, with $n$-exponential probability."

Then Can we Implement this algorithm for a Quad-Core Computer (and just 4 threads) with $n=100,000$?

The other question is what is the "$n$-exponential probability" in this sentence?

Thanks.

You are probably in the realm of asynchronous parallel computations where units of work are performed by processors at their pace and communication is performed explicitly. This model is a good approximation to many real life parallel computers such as PC clusters or multicore CPUs.

You have an algorithm that can be represented as $O(n \log n)$ units of work each taking constant time or as $O(n)$ units of work each taking $O(\log n)$ time.
Here $n$ is a parameter that characterizes the size of the problem.

The units of work can be executed on a parallel computer with a fixed number of sequential processing elements (e.g. processor cores). It depends on the algorithm whether the work units can complete while other work units have not started, or whether the computations will have to interleave.

In a practical computer interleaving can be achieved through pre-emption and context switches.


Conditions for a binary tree being balanced Prove or disprove for each of the following two properties, whether a family of trees that satisfy the property is balanced.
If you disprove, the counterexample should consist of an infinite sequence of trees in the family rather than just a single tree, because the property is asymptotic.
A. There is a constant $c$ so that for each node of the tree, the difference in height between the two sub-trees is at most $c$.
B. There is constant $c$ so that the average height of each node in the tree is at most $c \log n$.

Now I proved A using induction, and I know how to disprove B using a single example, but I don't know how to do so using infinitely many examples.

This is an interesting question. How do we define a family of binary trees is balanced?

A generalized definition of balanced binary trees

One of the most general definitions is that the height of a tree $T$ in the family is $O(\log n)$, where $n$ is the number of nodes in $T$. In other words, there is a constant $c$ such that the height of each tree $T$ in the family is no more than $c\log n$. We call such a family of binary trees balanced. Each tree in the family is called balanced (with respect to the family).

For example, the family of AVL trees is balanced. The family of red-black tree is balanced. For any given $0\lt \alpha\lt1$, $\alpha$-weight-balanced trees are balanced. A family of finitely many trees is balanced.

The family of all degenerated trees is not balanced.

$c$-height-balanced trees are balanced

Let $c$ be a constant. Let $T$ be a binary tree such that for each node of it, the difference in height between the two sub-trees is at most $c$. We call $T$ $c$-height-balanced. The family of $c$-height-balanced trees is balanced, which you have probably proved.

$O(\log n)$-average-height trees may not be balanced.

Let us call a family of trees that satisfies the condition (B) $O(\log n)$-average-height family of trees. Here is an example of an $O(\log n)$-average-height family of trees that is not balanced.

Let us start from a perfect binary tree with node $1,2, \cdots, 2^m-1$, where the children of node $i$ are node $2i$ and $2i+1$. Add node $2^m, 2^m+1, \cdots, 2^m+m^2-m$ to the tree so that the right child of node $j$ is node $j+1$ for all $j\ge 2^m-1$. Denote the tree thus obtained by $T_m$. The number of nodes in $T_m$ is $n=2^m+m^2-m$.

The rightmost nodes of $T_m$, $$2^1-1, 2^2-1, \cdots, 2^m-1, 2^m, 2^m+1, \cdots, 2^m+m^2-m$$ form a linear tree with $m+ m^2-m = m^2$ nodes.

The sum of heights of all nodes is

$$\begin{aligned}
\sum_{1\le i\le 2^m+m^2-m} h(i)
&= \sum_{1\le j\le m-1}\sum_{2^j\le i\le 2^{j+1}-2} h(i) + \sum_{0\le j\le m-1}h(2^{j+1}-1)+ \sum_{2^m\le i\le 2^m+m^2-m} h(i) \\
&= \sum_{1\le j\le m-1}(2^j-1)(m-1-j) + \sum_{1\le k\le m^2}(k-1) \\
&\lt m\sum_{1\le j\le m-1}(2^j-1) + \sum_{1\le k\le m^2}m^2\\
&\lt m2^m + (m^2)^2\\
&\lt 10m2^m\\
&\le 10mn.\\
\end{aligned}$$

So the average height of each node is not greater than $10m \le 10\log_2 n.$

However, the height of node $2^m+m^2-m$ is $m^2-1=\Theta((\log n)^2)$. So the $O(\log n)$-average-height family of trees $T_1, T_2, \cdots$ is not balanced.

Exercises

Exercises 1. Show that the height of a tree $T$ in a given balanced family of binary trees is, in fact, $\Theta(\log n)$.

Exercises 2. Construct an $O(\log n)$-average-height family of trees such that the height of a tree $T$ is $\Omega(\sqrt {n})$.

Exercises 3. Let $F$ be a family of binary trees such that the ratio between the heights of two subtrees with the same parent node is bounded for all parent nodes of all trees. In other words, there is a constant $c$ such that for every $T$ in $F$, for every node $v$ of $T$, the ratio between the heights of two subtrees of $v$ is at most $c$. In order to avoid dividing by zero, if any subtree of $v$ is empty, the height of that empty subtree is redefined as 1/2. We call $F$ height-ratio-bounded. Is a height-ratio-bounded family balanced?


How to prove this obvious theorem in type theory (LEAN prover) I have the following code:

constant B:Type
constant A:Type
constant P:B → A → Prop
definition F:Type := B → A

axiom a1: ∀b:B, ∃a:A, P b a
theorem thrm1: ∀b:B, ∀a:A, (P b a) → ∃f:F, (f b = a) ∧ ∀bb:B, P bb (f bb) :=
    λ b:B, λ a:A,
    assume h: P b a,

sorry

It should be almost trivial to prove this, yet I'm not sure how to do it in type theory. Perhaps my intuition is implicitly based on some axiom from classical logic?

The informal argument is as follows: If for a particular $b$ and $a$ the property $P \; b\;  a$ holds, then we can consider the equivalence class of functions $f:B \to A$ for which $f \; b= a$. Moreover, since for any $b\in B$, there is an $a\in A$ such that $P \; b \; a$ holds, we can simply pick from this the function $f$ which also assigns for every other $b$ some $a$ such that $P\; b\; a$ holds. Such a function must always exist, since we can freely adjust the output for each input independently.

But how do we formalize this argument in type theory?

If you used Type instead of Prop in the definition of P, then you could easily extract from axiom a1 a function f such that ∀b:B, P b (f b). However, there would be no guarantee that this function would satisfy f b = a for any given a and b that satisfy P b a. Given a decidable equality on B, you could turn the function that a1 gives you into your desired function via λ bb:B, if bb == b then a else fst (a1 bb). Without decidable equality, it's not clear how you would construct a function that you could prove would give a when given b.

As far as your informal argument, the problem is "picking" from the equivalence class. Constructive logic/type theory is compatible with everything being computable. (Formally, this is usually expressed via realizability.) To say that you can "pick" from an equivalence class subject to some constraints means you are providing an algorithm that can somehow "search" through (some representation of) the equivalence class and find an element that satisfies your constraints. However, you don't even know these types are computably enumerable. At any rate, "picking" is rarely "simple".

I'd have to look at the rules of LEAN to be sure, but with P going to Prop, you need the (real) Axiom of Choice to even get the function f at all before you ever got around to constraints. In fact, while I haven't thought about it too much, I believe the statement you give is equivalent to the (real) Axiom of Choice.


Need a hint! Karger's algorithm versus Kruskal, spanning tree distribution Let G = (V,E) be a unit-capacity graph with n vertices and m edges.

Let T denote all the spanning trees in G.

If we run Karger's algorithm, we will get a random spanning tree in T formed by the contracted edges, we denote this distribution of spanning trees by D1.

On the other hand, if we assign a random weight in (0,1) to each edge and compute a minimum spanning tree using Kruskal's algorithm, then another distribution D2 over T is obtained.

Show that the distributions D1 and D2 are identical.

I have no idea where to start. Any hint is helpful!

You should show that at each step, both algorithms select an edge with the same probability distribution. For example, the first edge that is contracted by Karger's algorithm is a uniformly random edge. Similarly, if you choose the weights at random, the first edge that is chosen in Kruskal's algorithm is a uniformly random edge.

What about the next edge? Karger's algorithm selects another uniformly random edge. After removing the first edge, the remaining edges are ordered completely at random. Hence the next edge chosen by Kruskal's algorithm is also uniformly at random.

From the third edge hence, some edge choices would be bad – will close a cycle. However, by design it doesn't happen in both algorithms, and otherwise the chosen edge is uniformly random.

This is the idea of the proof, and it remains to make it formal. That's your task.


How to Modify SAT Solvers to Produce Resolution Refutations for Unsatisfiable Instances? In recent SAT competitions, there is a Certified UNSAT track. The problem instances are all unsatisfiable and the solvers are asked to produce certificates for unsatisfiability. One way is to produce a resolution refutation for the set of clauses in a problem instance. How can a SAT solver, say MiniSAT, be modified to do this? Can this be done for every solver? I searched the Internet and found little information. A reference is good for me.

A clause-learning SAT solver can be described approximately as follows. There is a stash of learned clauses, which starts empty. We run a recursive procedure, which at each point in time, first checks whether the current assignment (initially empty) contradicts an axiom or something in the stash. If so, there is no need to explore this branch. Otherwise, it picks a variable, and tries both assignment recursively. When a recursive call corresponding to a partial assignment $\alpha$ returns, we learn the clause $\lnot \alpha$. At any given point in time we are allowed to forget clauses. (It's important for the proof that each clause is learned, even if we forget it later on).

We now take the transcript of the algorithm and consider the clauses in the order in which they are learned. We prove that whenever a clause $c$ is learned, it can be derived using the rules of resolution from existing clauses or from axioms; in particular, at the very end we derive contradiction.

We allow the weakening rule in the refutation we construct; we can always get rid of weakening later on without increasing the refutation length (exercise).

There are three cases to consider. If the clause $c$ was learned because the corresponding assignment contradicted an axiom $c'$ or a clause in the stash $c'$, then $c$ is a weakening of $c'$. The interesting case is when $c = \lnot \alpha$ was learned since both assignment to some variable $x$ failed to produce a satisfying assignment. These assignments correspond to the learned clauses $c \lor x$ and $c \lor \lnot x$, from which $c$ follows by resolution.

Note that if we never use clauses in the stash then the resulting refutation is tree-like (every clause is used once), assuming we state each axiom whenever it's needed (rather than once and for all). Also, in any case the size (number of lines) of the refutation is the same as the number of recursive calls.


Question about non recursively enumerable language Is every language (including languages over alphabet having infinite symbols) which is not recursively enumerable, uncountable?

In other words, let $R$ be the set of languages (including languages over alphabet having infinite symbols).
For all $L$,  belonging to $R$,  that are not recursively enumerable, can it be said that $L$ is uncountable?

Is any language (in the set $R$ defined above) recursively enumerable and uncountable?

NB : I am asking about the (un)countability of a language (set of strings) and not a set of languages.

Definition: a string over an alphabet $A$ (of finitely many symbols) is a finite sequence of symbols in $A$.
Definition: a language over an alphabet $A$ is a set of strings over $A$.

Is every language which is not recursively enumerable, uncountable?

No. Any language is a subset of the complete language $A_*$, the set of strings over $A$, which is a countable set. So, in fact, any language is a countable set of strings.

Is there any language which is recursively enumerable and uncountable?

No. The reason is the same as above.

The answers and the reasons behind them remain the same even if we allow $A$ to be a countably infinite set.

These two questions are not the same as the questions in Is there a non-recursive and uncountable language L?. However, the answer with its the reasoning are the same as [the answer to that question](https://cs.stackexchange.com/a/55855/91753.

OP just updated the question. So the only case left unanswered is when $A$ is an uncountably infinite set.

In that case, the definition of a language being recursively enumerable such as the one at wikipedia becomes inapplicable since all (common) models of Turing machines require the number of symbols to be finite (or at most countably infinite). To continue the discussion, we will need to make a new list of definitions for the Turing machines of the extraordinary kinds(which is not the Turing machines we usually talk about) or even other kinds of machines for hypercomputation and what is means by a recursively enumerable language with respect to those machines. That would be too large a scope that I would prefer not to go into in this answer.


Printing words starting with a given letter with the least amount of appearances with the print itself being an another appearance I've had problems with this one and was unable to solve it on my Algorithms 1 exam:

Input:
-n words
-k letters

Problem:
For each letter print out the one word which starts with that letter and has the least number of appearances. If there are more than one, write the lexicographically smallest one.
The printing of a word counts as an appearance.

Complexity:
Time: O (nlogn + k)
Space: O ( n + k )

This is the first algorithm I am unable to solve in given time complexity and it is driving me crazy.

Appreciate the help!

Example:

n=6 words:
dog bark dog woof doggy doggy

k=2 letters and corresponding outputs:
d - 2 is the least number of appearances of a word starting with d , dog and doggy - dog is the lexicographically smaller one so we print dog

if we say d again, since we printed out dog, that counts as another appearance so the only word appearing twice is doggy, and we print that one

The following assumes that you can store words in $O(1)$ space and compare them in $O(1)$ time.

For each letter $\ell$ keep:

The number of appearances $n_\ell$  of the word starting with $\ell$ that appears the least amount of times.
A list $L_\ell$ of words starting with $\ell$ that appeared $n_\ell$ times, in lexicographic order.
A list $R_\ell$ of words starting with $\ell$ that appeared $n_\ell + 1$ times and are smaller than the first word in $L_\ell$, in lexicographic order.
A sorted list $S_\ell$ of pairs $(n_w, w)$, where $w$ is a word starting with $\ell$ that appears $n_w \ge n_\ell+1$ times and is not in $R_\ell$. The pairs are sorted in lexicographic order.

Notice that you can construct everything above in $O(n \log n)$ overall time for all the letters $\ell$.

When you have to return a word starting with letter $\ell$, do the following:

Remove the first word $w^*$ from $L_\ell$ and output it.
Insert $w^*$ into $R_\ell$.
Insert all the words $w$ from a pair $(n_w, w)$ of $S_\ell$ such that (i) $n_w = n_\ell + 1$, and (ii) $w$ precedes the smallest word of $L_\ell$, into $R_\ell$. Delete the corresponding pairs from $S_\ell$. Notice that these are always the first elements in $S_\ell$. If $L_\ell$ is empty, then ignore constraint (ii).
If $L_\ell$ is empty, increase $n_\ell$ by 1, swap $R_\ell$ and $L_\ell$, and repeat step 3.

Steps 1, 2, and 4 can be performed in constant time. Step 3 requires a constant amount of time, plus a time proportional to the number of words $w$ moved from $S_\ell$ into $R_\ell$. This second term is upper bounded by $O(n)$ across all letters as this is an upper bound on the number of pairs contained in all $S_\ell$.


TM to detect repeats of any other TM and input value I read a previous question,
Is a secondary TM sufficient to detect all loops?, which asks if there is a TM1 that takes the description and input of any other TM2 to detect if TM2 will loop for the input.

One answer was to run two copies of TM2, the second at 1/2 the speed.If the second machine ever reaches the same configuration as the first, a loop was detected. Seems to me that the process requires a third entity to do the comparison at every step. Since neither copy output their complete configuration, it is not obvious this third entity and the complete system of all three entity can be a TM.
Another easy way is for a second TM2 to keep a list of all configuration of TM1 and check to if there any repeats. This can surely work. But again, what is not obvious is if this complete system of the checking process on TM2, the running of TM1 and outputting TM1's complete state configurations to TM2 can be realized as a TM. TM1 can't output its own states to TM2, so TM2 somehow has to grab these from TM1, not just its output but TM1's complete state information or there has to be a third entity that does the communication.

My question: Can this process be implemented as a Turing machine?

I think you're wondering how one Turing machine can keep track of what another Turing machine is doing, including checking that machine's state and knowing what's on its tape. After all, Turing machines don't have a method for "outputting" a description of what they're doing—they merely run.

But a Turing machine that takes in a description of another Turing machine can simulate that second machine on its tape, the same way that you can simulate running a TM using pencil and paper. The TM writes down the current configuration of the simulation, including what the simulated current state is, what the second machine's tape says, and where the machine's tape head is. It follows rules for moving the tape head, writing to the simulated tape, and changing the simulated current state.

That's how one machine can simulate another. Another helpful trick is that a TM can have any finite number of tapes without affecting its capabilities—a three-tape TM is no more powerful than a one-tape TM. So if it's conceptually helpful, you can give the TM a separate tape for each concurrent simulation.


Using visible line segments to compute a visibility polygon Given a simple polygon $P$ and a point $p$ within the polygon, I want to compute the region in $P$ consisting of all points $q$ visible from point $p$. A point $q$ is visible from point $p$, if the line segment $\overline{qp}$ is completely in the polygon $P$.

As for now, let's ignore the case where a line segment lies completely on the ray.

Now I have a collection of line segments (edges of the polygon) which are visible from point $p$. The problem is that not every line segment in the collection is fully visible which is why I can't simply connect them into a polygon. I first need to compute which part of each line segment is visible and connect those. This last step is what I struggle with.

Here are two examples:

In the left example edge $\overline{AD}$ is partially seen from $p$, in the right example it's $\overline{GH}$ (rest of the edges are completely visible).

For the left example, how can I use the fact that $\overline{EB}, \overline{BC}, \overline{AD}$ and $\overline{DE}$ are visible from point $p$ in order to compute the visibility polygon?

I struggle with finding an algorithm to do this which doesn't fail for every second case I apply it to. Any suggestions?

First, assume we already have a list $L$ with all segments in $P$ that are at least partially visible from $p$, ordered by the smallest angle $\theta$ such that a segment is visible from $p$ at angle $\theta$. (This can be done with a (angular) sweep line algorithm in $O(n\log n)$)

Now, observe that if a line from $p$ to some point on the segment $s_i$ in $L$ intersects some segment of $P$, it must intersect either $s_{i-1}$ or $s_{i+1}$ (be careful to wrap around the ends of the list), i.e. one of the neighbours of $s_i$.

Therefore, we can construct the visibility polygon as follows: iterate over all segments $s_i$ in $L$ and compute the visible sub-segment of $s_i$ using the segments $s_{i-1},s_{i+1}$. (call it $s_i^*$) Add it to your visibility polygon and then add the lines connecting the endpoints of $s_i^*$ with $s_{i-1}^*$ and $s_{i+1}^*$ to the visibility polygon (if they aren't already connected directly).


Time complexity of rotation array m times using temporary array I am new to asymptotic analysis, on solving the array rotation problem on geeksforgeeks the first solution provided was using a temporary array, I tried implementing this logic and found that the space complexity is O(m) where m is the number of times the array needs to be rotated. But the time complexity is given as O(n) where n is the size of the array. But I found that the time complexity should be O(n+m)

Input arr[] = [1, 2, 3, 4, 5, 6, 7], m = 2, n =7
1) Store d elements in a temp array
   temp[] = [1, 2] // It takes m iterations to copy the array
2) Shift rest of the arr[]
   arr[] = [3, 4, 5, 6, 7, 6, 7] // n-m iteration for shifting
3) Store back the d elements
   arr[] = [3, 4, 5, 6, 7, 1, 2] // m iterations for storing the elements back

Here is how I calculated time complexity

=> m+(n-m)+m

=> O(n+m)

Can anyone help me to figure out what I am doing wrong?

$O(n+m)$ and $O(n)$ are the same. $m$ can never be more than $n$, so $n+m\leq 2n =O(n)$.


Explanation for the proof "Every 2-thread consensus protocol has a bivalent initial state" From the book 'the art of multiprocessor programming':

  A protocol state is bivalent if the decision value is not yet fixed:
  there is some execution starting from that state in which the threads
  decide 0, and one in which they decide 1.

  Lemma 5.1.1. Every 2-thread consensus protocol has a bivalent initial
  state. Proof: Consider the initial state where A has input 0 and B has
  input 1.  If A finishes the protocol before B takes a step, then A
  must decide 0, because it must decide some thread’s input, and 0 is
  the only input it has seen (it cannot decide 1 because it has no way
  of distinguishing this state from the one in which B has input 0).

  Symmetrically, if B finishes the protocol before A takes a step, then
  B must decide 1, because it must decide some thread’s input, and 1 is
  the only input it has seen. It follows that the initial state where A
  has input 0 and B has input 1 is bivalent.

I don't understand why it can only output the input it has seen already. And for A why "it cannot decide 1 because it has no way of distinguishing this state from the one in which B has input 0)".

I don't understand why it can only output the input it has seen already.

The reason is simple. Just too simple. Because it cannot output any input that it has not seen deterministically, where the input could take one of two (or more) values randomly.

Let me use an example. Suppose you and I are two travellers (threads) travelling together. Each of us will be given one of two kind of maps to be used for travel, map 0 and map 1 separately. We two might be given the same kind of map. Or each of us might be given a different kind of map. Initially, each of us do not know what kind of map is given to the other one, since we are two separate travellers that have not communicated yet. Now suppose you have to decide which map should be used before you can make a move to know which map is given to me. What can you do deterministically? Since you do not know which map is given to me, the only deterministic decision you can make is to use whichever map given to you.

Had you have a chance to know which map was given to me, you could make a different decision deterministically. However, that is not the current situation.

  for A why "it cannot decide 1 because it has no way of distinguishing this state from the one in which B has input 0)".

That is because A does not know whether 1 or 0 is given to B. Even though the collective state of A and B might be observable/known to a third party, it is not known to A since, at the initial state, by definition, A has not made a move to access any shared object, i.e., A does not know the input to B since it might be 0 and it might be 1.

You will realize, sooner or later, wow, this is just too easy and too simple to understand. It might be fair to say that the lemma 5.1.1 is just too obvious or intuitive to use more than one sentence to explain.

On the other hand, there are lot of pitfalls and counterintuitive phenomenons in multiprocessor programming. Be careful and vigilant.


d-ary heapsort analysis I need to find a tight bound on the number of comparisons in a d-ary heapsort, in terms of d and n (the length of the array we want to sort).

Since inserting n items to a heap takes O(n) , and each delete-min takes O(d log n/ log d), I was thinking the bound is O(n d log n / log d). Am I right? If so, how do I prove that it is indeed a tight bound?

Thanks.

Inserting $n$ items to a heap takes $\Theta(n)$.

You probably mean that "building" a heap takes $\Theta(n)$.

  Each delete-min takes $\Theta(d \lg n/ \lg d)$, I was thinking the bound is $\Theta(n d \lg n / \lg d)$.

I agree with you.

  How do I prove that it is indeed a tight bound?

How tight do you want to prove it is? Do you want to show that the worst-case running time of $d$-ary heap-sort is $\Omega(n d \lg n / \lg d)$? If so, I tend to think it is indeed tight.

For a hint, this paper: The Analysis of Heapsort mentions that (in Abstract)

  The number of keys moved during $2$-ary heap-sort when sorting a random file of $n$ distinct elements is $n \lg n + O(n)$ in the worst case.

It even further proves that (Notice that it is for the best case)

  Theorem 1 (Page 7): Heap-sort ($2$-ary) requires at least $\frac{1}{2} n \lg n- O(n)$ data moves for any heap composed of distinct keys.

Maybe you can adapt it to $d$-ary heap-sort.


Compute e^x given starting approximation I have been looking for an algorithm to calculate $e^x$ to arbitrary precision (millions of digits).  The best way I know is to use Taylor polynomials.  However, the Taylor polynomial algorithm seems to have no way to enhance the precision of already existing estimates of $e^x$.

For example:

I already have an exact approximation for $e^{0.7}$ calculated to 1000 decimal places, but now I want an exact approximation of $e^{0.700000001}$ calculated to 100000 decimal places.

Because $e^{0.7}$ is very close to $e^{0.700000001}$, I should be able to use $e^{0.7}$ as a starting estimate for $e^{0.700000001}$.  However, using Taylor polynomials, I know of no way to input a starting approximation.

Does anyone know of an algorithm that efficiently converges to $e^x$ given an initial estimate?

To clarify, I'm looking for an algorithm that can actually surpass the accuracy of the given estimation.  For example, if I give it an estimate to 1000 digits, it should still be able to converge accurately beyond 10000000 digits.  This rules out the optimization $e^{0.70001} = e^{0.7} \cdot e^{0.00001}$.

The obvious answer to "I have an approximate solution to an equation and I want to improve it" is Newton-Raphson. If you have an approximation $y \approx e^x$ then you can improve it to $$y' = y - \frac{(\ln y) - x}{y^{-1}} = y(1 + x - \ln y)$$

Now you need an efficient way of calculating $\ln y$, but here I note that Wikipedia, commenting on high precision logarithms, says (my emphasis):

  Another alternative for extremely high precision calculation is the formula
  $$\ln x \approx {\frac {\pi }{2M(1,4/s)}}-m\ln 2,$$
  where $M$ denotes the arithmetic-geometric mean of $1$ and $4/s$, and
  $$\displaystyle s=x2^{m}>2^{p/2},$$
  with $m$ chosen so that $p$ bits of precision is attained. (For most purposes, the value of $8$ for $m$ is sufficient.) In fact, if this method is used, Newton inversion of the natural logarithm may conversely be used to calculate the exponential function efficiently.

The references given are Practically fast multiple-precision evaluation of log(x), Sasaki and Kanada (1982), Journal of Information Processing 5(4) pp247–250; and Fast Computations of the Exponential Function, Ahrendt (1999), Stacs Lecture Notes in Computer Science 1564 pp302–312.


Probability Distributions and Computational Complexity This question is about the intersection of probability theory and
computational complexity. One key observation is that some
distributions are easier to generate than others. For example,
the problem

  Given a number $n$, return a uniformly distributed number $i$ with $0 \leq i < n$.

is easy to solve.  On the other hand, the following problem is or
appears to be much harder.

  Given a number $n$, return a number $i$ such that $i$ is  (the
  Gödel number of) a valid proof of length n in Peano arithmetic.
  Moreover, if the number of such proofs is $pr(n)$,
  then the probability to get any specific proof of length $n$
  should be $\frac{1}{pr(n)}$.

This suggests to me that probability distributions come with a notion
of computational complexity. Moreover, this complexity is probably
closely related to the underlying decision problems (whether sub-recursive,
e.g. $P$, $EXP$, recursive, recursively enumerable, or worse).

My question is: how does one define the computational complexity of probability distributions, especially where the underlying decision problem is not decidable. I'm sure this has been investigated already, but I'm not sure where to look.

The complexity of probability distributions
comes up particularly in the study of distributional problems like
DistNP in Levin's theory of average case complexity theory.

A distribution is P-computable if
its cumulative density function can be evaluated in polynomial time.

A distribution is P-samplable if
we can sample from them  in polynomial time.

If a distribution is P-computable then it is P-sampable.
The reverse is not true if certain one-way functions exist.

You can extend the definitions to other complexity classes.

Oded Goldreich has a nice introductory notes on the topic
that you may want to check.


Showing that the pumping lemma cannot prove that some language is not regular I have this language $ L = a^* \cup \left \{ a^mb^n|m>n\geq 0  \right \}^* $ I have to prove that this language is not regular but still satisfies the pumping lemma for regular languages (Since the pumping lemma is a necessary but not sufficient condition for a language to be regular).
First I made the leap that $L$ is equivalent to $L' = \left \{ a^mb^n|m>n\geq 0  \right \}^*$ since this language already contains $a^*$(I hope it's correct).
My question is: to prove that the pumping lemma holds is sufficient to prove that exists a word in this language that satisfies the lemma or that must hold for all words in the language?   For example in this case we could consider the word $aaa$ it's easy to say how this word satisfies the pumping lemma because $aa^ia \in L' \space \forall i \geq 0$.
This means that proving the pumping lemma holds for a language is easy (must find an instance in whitch it holds) but proving it doesn't hold is harder (must prove that it doesn't hold for all instances of the language).

The idea of this exercise is to show that the pumping lemma is not a sure-fire method to prove that a language isn't regular. To show that, we need to come up with a language that (i) isn't regular, but (ii) cannot be proved not regular using the pumping lemma. This is the goal of your exercise.

The "pumping lemma method" for proving that a language $L$ isn't regular is a sort of game:

The adversary gives you an integer $p$.
You come up with a word $w \in L$ of length at least $p$.
The adversary partitions the word into $w = xyz$, where $|xy| \leq p$ and $|y| \geq 1$.
You come up with an integer $i$ such that $xy^iz \notin L$.

If you win this game then you have shown that $L$ is not regular. In order to show that the pumping lemma cannot be used to prove that $L$ is regular, you have to show that the adversary wins the game.

A winning strategy for you is, for each $p$, a word $w \in L$ of length at least $p$, and for each legal partition $w = xyz$, an integer $i$ such that $xy^i z \notin L$. This is how you apply the pumping lemma. A winning strategy for the adversary is an integer $p$ such that each word $w \in L$ of length at least $p$ can be legally partitioned as $w = xyz$ in such a way that $xy^i z \in L$ for all $i \geq 0$. This is your goal in this exercise.

If the pumping lemma doesn't work, what does work? There is a generalization of the pumping lemma in which you mark $p$ locations of the word $w$, and then the adversarial partition $w = xyz$ must satisfy (i) $xy$ contains at most $p$ marked locations, (ii) $y$ must contain at least one marked location. Sometimes this generalized version works when the usual one fails, but not always.

One method which is guaranteed to always work is the Myhill–Nerode criterion. If a language is not regular, you can always prove it (in principle) using the Myhill–Nerode theorem. In many cases it is also easier to apply than the pumping lemma, even when the latter does work. What pity that it is beyond the curricula of many courses!


CYK result de-transformation Suppose we have a rules derived from a treebank.
And in order to get a syntax tree of a given sentence we use the cyk algorithm.
In order to use the cyk we should convert the rules into chomsky normal form,
Such that all of my rules are A -> B C or A -> a (A,B,C are non-terminals and a is a terminal).
From the cyk we get the most probable tree, constituted from the cnf rules.
But what if we want to de-transform the tree to be constituted from the original rules?
We can expand very easily the Binary rules into the original.
But what about unit productions? for example; A->B->a transformed into A->a in cnf, how do we get the original unary rules path A->B->a?
Any ideas will be helpful.

I don't think you can recover a unit production, unless (and this is probably the common case) the unit production is unambiguous. If there is only one derivation from a non-terminal to a particular terminal -- and it should be easy to figure that out while you are doing the transformation to CNF -- then you can record that derivation and reinsert it when you find the collapsed derivation in the CYK parse.


Why there is no direct connection between the data bus and the accumulater register In the data bus all the registers are connected in and out with the data bus but the AC don't have it only out also the memory don't have a direct connection with it ?
Please explain if you know

The answer as in many cases: Someone thought it was a good idea.

Someone may have evaluated cost and benefits and may have decided that the benefits were not worth the cost.


Show that language generated by grammar is regular We have grammar with nonterminals $ X_1,...X_n$ terminals $V_t$ and rewriting rules of form:

$X_i  \rightarrow a \in V_t   $

$X_i \rightarrow X_jX_k, \  i \ge j  , \ i > k  $

How can I show that language generated by this grammar is regular?

I don't think this is duplicate question, because:

I don't have concrete language, but set of nonterminals and set of terminals
I have to show, that for every possible combination of terminals and nonterminals I get only language which is regular

If I had been given particular language, I could prove it by giving DFA, showing that rules are only of linear type,etc....

Prove by backwards complete induction that each $X_i$ generates a regular language (backwards induction means that you first prove it for $X_n$, then for $X_{n-1}$, and so on, until you reach $X_1$; complete induction means that when proving this for $X_i$, you can use the induction hypothesis for all of $X_{i+1},\ldots,X_n$).

Perhaps the easiest way to carry out the inductive proof is to give a regular expression for the language generated by each $X_i$.

The only non-trivial part is handling productions of the form $X \to XY$. Here you need to use Arden's rule, which states that if the only productions having $X$ at the left-hand side are $X \to XY \mid Z$ then
$$ L(X) = L(Z)L(Y)^*, $$
where $L(X)$ is the language generated by $X$.


Formal Grammar: derivation form posted on Wiki? Wiki describes the binary relation $\underset{\mbox{G}}{\implies}$ as "G derives in one step".  I have a question on the condition when there are multiple productions for a single non-terminal.
Wiki defines $G = (N, \Sigma, P, S)$ and $\underset{\mbox{G}}{\implies} \subset (\Sigma \cup N)^* \times (\Sigma \cup N)^*$ where:
$(\underset{\mbox{G}}{x \implies y}) \iff \exists u,v,p,q \in (\Sigma \cup N)^* : (x = upv) \land ((p, q) \in P) \land (y = uqv)$
Then
$(\overset * {\underset{\mbox{G}}{x \implies y}})$ is defined as the refexive transitive closure.  Therefore applying $\underset{\mbox{G}}{\implies}$ multiple times results in the language of the grammar:
$\{w \in \Sigma^* | (\overset * {\underset{\mbox{G}}{S \implies w}})\}$
QUESTION
For the form $(\underset{\mbox{G}}{x \implies y})$ I consider the case of multiple rules $(p,q_0), (p, q_1) \in P$ for a non-terminal $N$.  If solving for $y$, $y$ will result in the string with only a single rule applied.  How should the derivation happen with multiple production rules?
I can see that supplying both arguments $(\Sigma \cup N)^* \times (\Sigma \cup N)^*$ to $\underset{\mbox{G}}{x \implies y}$ will yield all derivations.

You seem to be looking for a deterministic procedure that isn't there.
With multiple production rules, you solve in every possible way.  For instance, for the grammar
$S \rightarrow a \\ S \rightarrow aS$
we have
$
\underset{G}{S \implies a}, \\
\underset{G}{S \implies aS}, \\
\underset{G}{aS \implies aa}, \\
\underset{G}{aS \implies aaS}, \\
\ldots
$


Calculating miss rates of word-addressable and direct-mapped cache This a problem in a computer architecture course that's giving me some trouble:

You have an application whose memory access pattern is a stream and its entire data set is 128kB. The data cache in  your machine has a capacity of 64kB. It is word-addressable and direct-mapped with 32B lines. It is able to fetch one line at a time.

Given the access pattern: 0, 4, 8, 12, 16, 20, 24, 28, 32, 36, 40, …, 32768, where each access is a 4B word.

What is the miss rate?
Can the miss rate be reduced by using a larger cache?
Can the miss rate be reduced if the size of the data set were reduced?

Here's what I think is going on:  The cache is initially empty, meaning each access will result in a compulsory miss.  So would this mean the miss rate is 100%, since no data is initially loaded and the pattern doesn't hit any address twice?

Any help understanding this would be much appreciated!

It seems you don't understand how cache lines work. A cache line is a contiguous chunk of memory. In this example, the cache line size is 32 bytes. This means that 32 contiguous bytes are always loaded into the cache at a time, namely whenever a miss occurs.

So if we initially assume the cache is empty (or "cold"), then the first access will be a miss. However, the first 28 bytes will be loaded in. This means that in addition to loading word 0 into the cache, the words at addresses 4, 8, 12, 16, 20, 24, and 28 will also get loaded into the cache. Conveniently, this is how your example program accesses data (linearly), so we will get a cache hit for all of those words. When we hit the word at address 32 we will again get a miss and the process repeats. Thus, our miss rate is 1/8, once for every 32 byte block.

Since we are never accessing the same data more than once, the size of the cache itself is irrelevant, i.e. all we need is for the cache to be able to hold a single line. Thus, we can not reduce our miss rate with a larger cache.

And finally, as shown from the analysis, the size of the data set is irrelevant. It doesn't matter if we're reading in 1 Kilobyte or 1 Gigabyte, the miss rate is the same.


How do computers create 'randomness'? I have just used a function 'rand()' in my algorithm. In fact, it was arc4random() that I used. However, it got me thinking, how is randomness created in a computer system?
Can anything ever truly be random when it is produced by a computer?

Randomness is a philosophical concept (though there are several mathematical definitions as well). There are two aspect to randomness generated by a computer, unpredictability and pseudorandomness, which correspond to two different demands from a randomness source:

Data produced by the randomness source should be unpredictable, even in principle.
Data produced by the randomness source should "behave" as a truly random source.

The approach taken by computers to generate randomness is a combination of both of these flavors. Randomness is generate using a pseudorandom number generator, which is an algorithm designed to churned up numbers which "look random", in the sense that any program employing a randomness source will behave the same regardless of it being given a truly random source or the output of the pseudorandom number generator. ARC4 (usually known as RC4) is such an algorithm, though the first few random bits are known to be somewhat problematic.

A pseudorandom number generator (PRNG) is seeded by initial randomness, known as either a seed or a key. Sometimes we want to fix this initial randomness, for example when debugging a program which uses the PRNG. Other times, it is important that this initial randomness be unpredictable - this is the case in cryptographic applications. It used to be the case that PRNGs are seeded using the exact time-of-day as kept by the computer clock. Nowadays systems are more sophisticated, and harvest random bits from other sources such as keystrokes, CPU, internal devices and network usage, commonly known as an entropy pool. Therefore modern systems are capable of producing unpredictable random numbers.

If it is important to generate truly random numbers (or rather, numbers which are even less predictable), one can resort to hardware number generators, which usually measure thermal noise generated by electric components such as diodes (in the form of voltage or current fluctuations). However even this random output needs to be filtered (through a randomness extractor) to result in a sequence of independent fair coin flips.


Is Wadler's 'Theorems for Free' as general as Design By Contract for establishing correctness? Philip Wadler has written a brilliant paper called 'Theorems for Free'. The big idea is that you can use types to reason about your program, and even prove simple theorems about your program.

We see these ideas about types applied in the Haskell language.

At very roughly the same time period - we have an idea from Betrand Meyer called 'Design By Contract'- which is most notably implemented in the Eiffel Language. This has the following features:

routine preconditions
routine postconditions
class invariants
check instructions (like assert)
loop invariants

The idea behind Design by Contract is software designers should define formal, precise and verifiable interface specifications for software components, which extend the ordinary definition of abstract data types with preconditions, postconditions and invariants.

Now many claim that using 'Types' in your programs leads to 'more correct programs' (via the Howard Curry Correspondence).  From what I can see - even the most advanced use of Dependent Typing in Idris and Scala is limited to Sum Types and list lengths (correct me if I'm wrong).

By contrast - the power of 'Design By Contract' in establishing the correctness of my program is more general and more powerful. (Albeit not necessarily at compile-time - but at test time). I can for example establish in my banking program that all deposits are positive, and all reported account balances are positive.

The point being - types have a fascinating future of possibilities, and are enormously powerful and compile time - but right now their practical application seems limited.

My question is: is design by contract of more general application than using theorems from types to reason about the correctness of my program at present? (Or are we just talking about two different things)

"Theorems for free" are so-called because they follow from the type of the program, without looking at the the program code!

"Contracts" are clearly not free theorems, because they depend on the code of the program, not merely the type.

However, the connection you do want to make is between types and specifications.  Specifications are in a way "more detailed" types.  Or, state the other way, types are more basic specifications.  Martin-Lof type theory is precisely about fusing the two ideas into one.


Dynamic Programming - Print all paths from (0,0) to (n,n) in Grid/Lattice I'm trying to write an algorithm to print all the paths from point (0,0) to (n,n) in a grid.
The only possible moves are right and up.
Also, you can't move below the diagonal y=x. e.g if you're at (1,1) you can only move to (1,2), but not to (2,1), since it's below the y=x diagonal.

I wrote an algorithm that calculates the number of possible paths from (0,0) to any given (x,y), such that the above limitations are held, but I can't find a way to print out the paths that give these numbers.

The algorithm I wrote is a bottom-up one, as follows:

JUMP(x, y)
1.  M[x-1,y+1] ← 1
2.  for i=0 to x+1
        M[i,y+1] ← 0
3.  for i=0 to y+1
        M[x+1,i] ← 0
4.  for j=0 to y-1
        for i=j+1 to x
            M[i,j] ← 0

5.  for j=y to 0
        for i=j to 0
            M[i,j] ← M[i+1,j] + M[i,j+1]

6.  return M[i,j]

Please advise on this.

You can solve this problem using a recursive formulation of print all paths from a point $(i,j)$ to the target $(n,n)$ in the grid. I call this function $f(i,j)$. So the all paths will be in $f(0,0)$ call.

$f(i,j) = \begin{cases}
\emptyset & if\ \ {i>j}\\
\emptyset & if\ \ \neg( {0\leq i\leq n\ \wedge 0\leq j\leq n) }\\
\{(n,n)\} & if \ \ i = n \wedge j = n\\
\bigcup_{p\,\in\, f(i+1,j)\,\cup\,f(i,j+1) } \ \ \{(i,j)\}\cup p & \text{otherwise}
\end{cases}$

By example, two of all paths from $f(0,0)$ when $n=4$ are:

blue path = {{0, 0}, {0, 1}, {1, 1}, {1, 2}, {2, 2}, {2, 3}, {3, 3}, {3, 4}, {4,
  4}}

red path = {{0, 0}, {0, 1}, {0, 2}, {1, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 4}, {4,
  4}}

So, although programming is not in the scope of this site, I think is good to see a implementation for a memoization version of the above algorithm.
asdf

from functools import wraps

def memo(func):
    cache = {}

    @wraps(func)
    def wrap(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    return wrap

@memo
def f(i, j):
    global n
    if i > j:
        return []
    if not (0 <= i <= n and 0 <= j <= n):
        return []
    if i == n and j == n:
        return [[(n,n)]]
    alls = []
    for path in f(i, j+1)+f(i+1, j):
        if len(path) > 0:
            alls += [[(i,j)] + path]
    return alls

n = 4
for path in f(0,0):
    print path


Finding optimal multiplication order and optimal binary tree I have to determine the Optimal Multiplication Order for above matrices using Dynamic Programming approach and also present that sequence (i.e. optimal order) in Binary Tree.

Consider the following five matrices A, B, C, D and E along with their dimensions;
A=(6×5)     B=(5×1)     C=(1×7)     D=(7×4)     E=(4×2)

After two hours, I have calculated the final cost matrix as

0   30   72   82   85
    0    35   48   53
         0    28   43
              0    56
                   0

and the split k values that led to a minimum m[i, j] value

0   1   2   2   2
    0   2   2   2
        0   3   4
            0   4
                0

Now I don't know how to calculate optimal order for multiplication from the above table. And also don't know to draw optimal tree for that sequence. Kindly someone help me at this point.

This is the classic problem of matrix chain multiplication.

Here is the pseudocode in Java from Wikipedia, which computes, for each $2 \le k \le n$, the minimum costs of all subsequences of length k using the costs of smaller subsequences already computed. It runs in $O(n^3)$, where $n$ is is the number of matrices, assuming the number of rows and columns in all matrices are bounded by a constant.

// Matrix A[i] has dimension dims[i-1] x dims[i] for i = 1..n
// The first index for dims is 0 and the first index for m and s is 1.
MatrixChainOrder(int dims[])
{
    // length[dims] = n + 1
    n = dims.length - 1;
    // m[i,j] = Minimum number of scalar multiplications (i.e., cost)
    // needed to compute the matrix A[i]A[i+1]...A[j] = A[i..j]
    // The cost is zero when multiplying one matrix
    for (i = 1; i <= n; i++)
        m[i, i] = 0;

    for (len = 2; len <= n; len++) { // Subsequence lengths
        for (i = 1; i <= n - len + 1; i++) {
            j = i + len - 1;
            m[i, j] = MAXINT;
            for (k = i; k <= j - 1; k++) {
                cost = m[i, k] + m[k+1, j] + dims[i-1]*dims[k]*dims[j];
                if (cost < m[i, j]) {
                    m[i, j] = cost;
                    s[i, j] = k; // Index of the subsequence split that achieved minimal cost
                }
            }
        }
    }
}

You can check that Wikipedia page for more information. In particular, there is a ready-make java implementation. There is also explanation to a much more complicated algorithm that runs in $O(n\log n)$ time.


Resending old frame when a damaged frame has been received in one bit sliding window protocol I'm reading Tanenbaum's and Wheterall's book on Computer Networks.
I'm trying out some examples of situations that can occur in the one bit sliding window protocol for a datalink layer.

The code for the protocol can be found here on page 214.

The situation I was investigating was the following:
Let's say client A successfully sends a frame to client B. Client B then sends his frame containing data along with the acknowledgement (ACK) that he received client A's frame correctly (piggybacking). Now somewhere along the way this frame gets damaged. Therefore, in the code, a chksum_err event occurs. Then the exact same frame client A sent before is sent again. Why? Shouldn't it be the case that client A now sends a frame with the sequence number inverted, new data but the acknowledgement is not inverted? This way, assuming nothing special happens along the way, client B correctly receives a new frame (instead of a duplicate) and client B knows that the frame he sent was damaged so he needs to send it again.

Isn't this the beauty of the protocol? Is the code wrong or what am I missing?

Shouldn't it be the case that client A now sends a frame with the sequence number inverted, new data but the acknowledgement is not inverted?

This could indeed be done when the error occured in the data. i.e. you're sure that it wasn't the acknowledgement or sequence number that was damaged. In that case, sender A could indeed send a new frame as described and avoid sending unnecessary duplicates.

However, although an error can be detected, it can not be detected where the error occured (in the data, acknowledgement or sequence number). If the error occured in the aknowledgement number then the client may unrightfully think that his previously sent frame was received correctly while it actually wasn't received correctly and so, if he sents a new frame with new data as proposed in the question, a client will miss a frame!


Converting If-else condition to Linear Programming I have a constraint in a linear programming formulation with two variables: $X \ge Y$

To which I want to apply the following if-else conditions:

if Y=1:
    X=1
else:
    X=0

Where $X$ and $Y$ are binary.

How can I fit this if-else into linear programming? Do I need to define another variable? It looks as an AND operation, between $X$ and $Y$.

This can be expressed with just the equation $X=Y$.  Since $X,Y$ are zero-or-one variables, the only possible assignments that are consistent with your condition are $X=Y=0$ and $X=Y=1$.

See Express boolean logic operations in zero-one integer linear programming (ILP) for many more boolean conditions and how to express them as linear inequalities.


Is there any study or theory behind combining binary search and interpolation search? I just read Can this algorithm still be considered a Binary Search algorithm? and recalled that a few years back I wrote an indexer/search for log files to find log entries in large plain text files by date/time window.

Whilst doing this, I decided to try interpolation search (I didn't know that was what it was called, I kind of stumbled across the idea by myself). Then for some reason I continued to the idea of alternating interpolation steps with binary split steps: On step 0 I would interpolate to decide test point, then step 1 I would take the exact midpoint etc.

I then benchmarked the system using pure interpolation search, pure binary search and my combination attempt. The alternating approach was a clear winner, both in time and number of tests required before finding a set of randomly chosen times.

Inspired by the linked question, I just made a quick search for "alternating interpolation search and binary search" and found nothing. I also tried "hedged interpolation search" as suggested on my comment on one of the answers.

Have I stumbled across a known thing? Is there any theoretical justification for it being faster for certain types of data? The log files were typically large for the time (e.g. 1-2 GB of text with maybe 10 million rows to search), and the spread of dates/times in them was complex with heavy bursts of activity, general peak times and quiet times. My benchmark tests sampled from an even distribution of target times to find.

Interleaving two algorithms to get the best of both worlds is a known technique, though it is usually stated as running them in "parallel" and returning an answer as soon as either terminates.

Though theoretically faster, interpolation search has two disadvantages compared to binary search:

It has terrible (linear) worst case performance
The overhead of computing the midpoint is rather large; a binary search iteration is hundreds of times faster than an interpolation search one

I would expect that an approach where you do interpolation search while the range is large and switch to binary search when the range becomes small is the most efficient. It would be nice if you could try this experiment.

As your dataset becomes small, the difference between $\log n$ and $\log \log n$ becomes insignificant; $\log n$ is already really small, and $\log \log n$ couldn't possibly be much smaller. At this point, the overhead of doing interpolation search is not worth it compared to the iterations you might save.

I think that your results can be explained by two phenomena:

Combining with binary search allows you to avoid the worst-case behavior
The positive effect of switching to binary search on a small dataset


Why can't hash coding be reversed? Why is it impossible to reverse a hash code? There could be some way to crack this coding?

Because, in general, hashing is not injective.

Being injective is a property of a function which states that each distinct element of the domain is mapped to distinct element of codomain. It means that given a value of a function, you will (if it is a valid value) know from what it came from. For more on this, see injective function.

Therefore, if hashing function $h$ is not injective, it can happen that two elements $A,B$ could be mapped to $H =: h(A) = h(B)$ and from knowing only $H$ you cannot determine whether it is the result of hashing $A$ or $B$.

But, there is a concept of perfect hashing which is injective.

If your question is about cryptographic nature of hashing, then the reason is the same as why any good cipher is "unbreakable". It is not that it is impossible to decrypt it (it surely cannot be the case, because then the reciever of cipher could not do it), but is just very very time consuming without knowing the key. You can find out more on that at Cryptography Stack Exchange.


Algorithm for identifying correct subset My raw data is composite, but for simplicity sake let's say they consist of three elements. One might consider a sample set thusly.

[A,a,1]
[A,b,1]
[B,b,1]
[B,b,2]
[C,b,3]
[A,c,3]

I need to create a subset that satisfy two key criteria.

All combinations of the two last columns is represented (lower case and numeric)
All upper case (first column) is represented at least once.

... in as few rows as possible. The data is not evenly distributed, meaning that e.g 80 percent of the rows in the input data may have b,1.
If that was the case, it would be wasteful to include  A,b,1 row, because I would have to include A,a,1 as well in order to make sure that a,1 combination is represented.

Though large data, the data is in memory. Accessing and iterating is relatively cheap. The data is static and may be processed over multiple passes .

Language is C#.

I'm not too happy about the title of this question, so if there is any key term that better describes this problem, feel free to comment/edit.

You can solve this by looking for a maximum cardinality matching in a bipartite graph, then covering remaining vertices arbitrarily.

Make a bipartite graph:

In the left part of the graph, make a vertex for every capital letter.
In the right part of the graph, make a vertex for every combination of lowercase letter and number.
For each record, make an edge (which necessarily goes from a vertex on the left to one on the right) corresponding to the two vertices covered by the record.

Now run an algorithm for finding a maximum cardinality matching in a bipartite graph, such as the Hopcroft-Karp maximum flow algorithm.  This picks a subset of edges (records) that together cover the most possible distinct combinations of capital letter and (lowercase letter + number).  That is, each chosen record hits both a capital letter, and a (lowercase letter + number) pair that are not hit by any other chosen record.

If the matching saturates (touches) every vertex, you have a "perfect" solution!  Otherwise, for each remaining vertex, you need to pick a record incident on that vertex -- it doesn't matter which record you pick, because it definitely won't be incident on any untouched vertices on the other side (if it was, then it would have been included in the matching already).


Determine whether given f is shortest path function I have the following question:
Let $G = (V,E)$ be a directed graph  with a weight function $w:E\rightarrow \mathbb{R}^+$, and let $s \in V$ be a vertex such that there is a path from $v$ to every other vertex, i.e $0\leq dist(s,v) < \infty$. Let $f\colon V \to \mathbb R$ a given function. Describe an algorithm that runs in $O(|V| + |E|)$ that determines wethter this given $f$ is the shortest path function from $s$, i.e $\forall v \in V :f(v)=dist(s,v)$.

What I thought about was to check for every $v \in V$  whether $f$ fulfill the two following demands:

$f(s)=0$
$f(v) \leq f(u) + w(uv)$ for all $u \in V$ and $uv \in E$

This runs in the proper complexity. I thought to prove it by showing that $f(v) \leq dist(s,v) \land f(v) \geq dist(u,v) \Rightarrow f(v) = dist(f,v)$

I proved that $f(v) \leq dist(s,v)$, but I am stuck at proving that $f(v) \geq dist(s,v)$.

Your conditions are not enough. For example, the function $f(v) \equiv 0$ satisfies them, but is (usually) not the shortest distance function.

You need to strengthen your second condition.


Explanation of O(n2^n) time complexity for powerset generation I'm working on a problem to generate all powersets of a given set. The algorithm itself is relatively straightforward:

def power_sets(A):
    """Returns the power set of A as a list of lists"""

    if len(A) == 0:
        return [[]]

    else:
        ps_n1 = power_sets(A[:-1]) # Powerset of set without last element
        # Add nth element to each subset of the powerset of n-1 elements
        ps_n = [sub + [A[-1]] for sub in ps_n1]

        # Combine the two sets and return
        return ps_n1 + ps_n

It's clear that the space complexity is $O(n2^n)$, since there are $n$ items in the set, and each element is in half of the $2^n$ sets.

However, the book that I'm working from says the time complexity is also $O(n2^n)$, which makes perfect intuitive sense, but I'm having a hard time justifying it mathematically.

Other than by saying "there are x number of items to mess with, so time complexity is at least as much", can anyone offer an explanation of the runtime analysis based on the runtime of the statements in my algorithm?

This answer pretty much only says that the runtime is such because of the space complexity (not very satisfying, but as an aside--can the runtime ever be better than the space complexity?)

I saw this answer, but to be honest it is a bit difficult to understand. It seems to suggest in the last line that the runtime is $O(n^2*2^{n!})$ (since (I think) $|P_i| = 2^i$), and that doesn't seem right either.

I tried drawing out the call tree and that didn't help, as there are only $n-1$ recursive calls made, and from what I can tell each spends $O(n^2)$ time.

Anyway, can someone offer a compelling explanation for this runtime?

Observe that:
$T(N) = 2T(N-1) + 2^{N-1}$
$T(1) = 2$
Note that the entire runtime, our algorithm only spends time generating more data. Therefore, our function T represents both the amount of time that the function spends running on an input of size N, and also the amount of data it generates from an input of size N.
We have $2T(N-1)$ because we first make the recursive call, and the following line makes a copy of all that data again in preparation to tack on the element we left out in the recursive call. We tack on exactly $2^{N-1}$ copies of the element we intentionally left out so that's where the last term comes from. Finally, T(1)=2 because with 1 element, we return 2 possible subsets (the entire set and the empty set).
Unrolling this recurrence we have:
$T(N)=2T(N-1)+2^{N-1}$
$\quad \quad =2(2(T(N-2)+2^{N-2})+2^{N-1}$
$\quad \quad =2(2(2(T(N-3)+2^{N-3})+2^{N-2})+2^{N-1}$
$...$
$\quad \quad = 2^N + (N-1)*2^{N-1}$
$\quad \quad = O(N*2^N)$


Lower the frechet distance between two curves Fréchet distance tells how similar two curves are. Now let's say I have two curves A and B, both represented in several discrete coordinate x, y points. And the fréchet distance between A and B is d. What technique can I employ to find another curve that has d/2 fréchet distance from both curves and has a total euclidean distance which is in the range [min(|A|, |B|), max(|A|, |B|)], where |A| is the total euclidean distance of the curve A and |B| is the total euclidean distance of the curve B? I know that there is probably not a single curve, any one curve will be great help for me. Thanks in advance.

Raichel and Har-Peled wrote a paper, The Frechet Distance Revisited and Extended, which explains how to compute various curves.
This might implicitly give you the answer.


Is there a reasonable and studied concept of reduction between regular languages? Have been any interesting formulations for the concept of reduction between regular langauges, and if so -- are there regular-complete languages under those reductions?

Barrington, Compton, Straubing and Thérien showed, in their paper Regular languages in $\mathsf{NC^1}$, that if the syntactic monoid of a regular language contains a nonsolvable finite group then the language is $\mathsf{NC^1}$-complete with respect to $\mathsf{AC^0}$-reductions (these are reductions computed by polynomial size, constant depth circuits with unbounded fan-in). Barrington's theorem implies that all regular languages are in $\mathsf{NC^1}$, and so such regular languages are complete for the set of regular languages under $\mathsf{AC^0}$-reductions.

Since we know that $\mathsf{AC^0} \neq \mathsf{NC^1}$ (for example, the parity function is in the latter but not in the former), regular languages in $\mathsf{AC^0}$ cannot be complete. For example, the language $a^*b^*$ isn't complete. Similarly, $\mathsf{AC^0}[p] \neq \mathsf{NC^1}$, showing that the language $(aa)^*$ isn't complete.

The simplest example of a language which satisfies the condition above is the language of all words over $S_5$ (the symmetric group on 5 elements) which multiply to the identity. The syntactic monoid of this language is $S_5$, which is a nonsolvable finite group. The slightly smaller alternating group $A_5$ would also work.


Why is adding log probabilities faster than multiplying probabilities? To frame the question, in computer science often we want to calculate the product of several probabilities:

P(A,B,C) = P(A) * P(B) * P(C)

The simplest approach is simply to multiply these numbers, and that is what I was going to do. However, my boss said it's better to add the log of the probabilities:

log(P(A,B,C)) = log(P(A)) + log(P(B)) + log(P(C))

This gives the log probability, but we can get the probability afterwards if necessary:

P(A,B,C) = e^log(P(A,B,C))

Log addition is considered better for two reasons:

It prevents "underflow" whereby the product of probabilities is so small that it gets rounded to zero. This can often be a risk since probabilities are often very small.
It is faster because many computer architectures can perform addition more quickly than multiplication.

My question is about the second point. This is how I have seen it described, but it doesn't take into account the added cost of getting the log! We should be comparing "cost of log + cost of addition" to "cost of multiplication". Is it still smaller after taking that into account?

Also, the Wikipedia page (Log probability) is confusing in this respect, stating "The conversion to log form is expensive, but is only incurred once." I don't understand this, because I think you would need to take the log of every term independently before adding. What am I missing?

Finally, the justification that "computers perform addition faster than multiplication" is kind of vague. Is that specific to the x86 instruction set, or is it some more fundamental trait of processor architectures?

Also, the Wikipedia page (https://en.wikipedia.org/wiki/Log_probability) is confusing in this respect, stating "The conversion to log form is expensive, but is only incurred once." I don't understand this, because I think you would need to take the log of every term independently before adding. What am I missing?

If you just want to compute $P(A_1)\ldots P(A_n)$ once, then you are right. You will have to compute $n$ logarithms and $n-1$ additions, whereas the naive method requires $n-1$ multiplications.

However, it is very common that you want to answer queries of the form:

  Compute $\prod_{i \in I} P(A_i)$ for some subset $I$ of $\{1, \ldots n\}$.

In that case, you can preprocess your data to compute all $\log P(A_i)$ only once, and answer each query by doing $|I|$ additions.

  Finally, the justification that "computers perform addition faster than multiplication" is kind of vague. Is that specific to the x86 instruction set, or is it some more fundamental trait of processor architectures?

This is a broader question. In general it is (probably?) harder to compute multiplication than addition. Computing $a+b$ is linear in the size of $a$ and $b$ (using the trivial algorithm), whereas we currently don't know how to compute $a\times b$ with the same time complexity (check the best algorithms here).

Of course there is no definitive answer: for instance if you deal with integers only and you multiply by powers of $2$, then you should rather compare shift with add operations.

Nevertheless this is a reasonable statement on all common computer architectures: multiplication on floating-point numbers will be slower than addition.


The underlying type theory of HOL/Isabelle Is there a good source on the type theory of HOL/Isabelle/other HOL-based LCF-style theorem provers?

I don't think Isabelle's implementation manual is a good place to look at this. It may certainly contain links to the explanation but you can find instead a pedagogical introduction in section 2 of this thesis.


How to generate an instance for an NP_hard proof, where each element has two inputs? I want to prove the NP-hardness of an scheduling problem. The problem seems to be NP-hard in the ordinary sense, so I am trying with the Partition Problem, precisely the Equal Cardinality Partition (ECP). So we have:

(ECP): Let $X = \{x_1, x_2, \dots, x_{2n}\}$ be a set of positive integers, does there exist a partition of $X$ into two subsets $X_1$ and $X_2$, such that $\sum_{x_i \in X_1}x_i = \sum_{x_i \in X_2}x_i = B$, where $B$ is a positive integer, and such that $|X_1|=|X_2|$?

The inputs for my scheduling problem are a set of $n$ jobs, where each job has a processing time $p_i$ and a due date $d_i$. So, my instance has jobs where processing times are linked to the integers from the Partition problem, i.e. $p_i=x_i$.

The issue that I have is this:
If I assign a common due date for all jobs, i.e. $d_i=d$, then the problem is not NP-hard. So, how I can generate the instance with non-equal due dates? For example, can I use the same integers $x_i$ for the due dates (e.g. $d_i=B-x_i$)? Is it Ok if I use the job id ($i$) in the due dates (e.g. $d_i=B-2i^2$)?

p.s. I realized that I cannot use the $x_i$ of one job in the due date of another job, as then those jobs will be related to each other thai is not correct. Actually, that makes even very simple problems to be NP-hard.

As you noted yourself, the problem in general is NP-hard.  You can reduce from Partition by letting due date $d = B = (\sum X)/2$, where $X$ is the input to Partition, and let there be two processes.

The proof is quite straight forward and left as an exercise.


What are the prerequisites for instruction pipelining to work? When can it be applied? When can it not be used? I get the general idea but not what it takes to make it work.

The main use case for pipelining is when your latency is large, but actual work is small. You hide the latency by scheduling many operations such that the latencies overlap but the actual work does not.

It can't be used if the latencies are not independent. An example is calling people from a phone just to say "yes". The actual work is very small, the latency is very large, however your phone can only call one person at a time so you can't actually apply pipelining.

If you had multiple phones however you could start dialing the next person while the previous phone is still ringing.


Is np-complete an equivalence class? So, there are multiple possible definitions of "np-complete", two of which being:

A decision problem $L$ is np-complete if and only if:  $L \in \text{NP}$  and  $\forall L' \in \text{NP}: L' \preceq_{p} L$
A decision problem $L$ is np-complete if and only if:  $L \in \text{NP}$  and  there exists a np-complete problem $L \in \text{NP}$ such that: $L' \preceq_{p} L$

My question is, why are those two definitions equivalent, or put differently, (why) is np-complete an equivalence class?

If it is an equivalence class I can understand equivalence of the above two definitions, but I fail to see why this is the case, since the (one-to-many) poly-time reduction $\preceq_{p}$ is not symmetric... :-/

The second definition isn't valid, since it's self-referential. Given the first definition, the second statement is an easy theorem that follows from the first definition.

Indeed, suppose we define NP-completeness using the first definition. Let's see that the second definition is true.

$\Longrightarrow$ If $L$ is NP-complete then for all $L'$ in NP, $L'$ reduces to $L$. In particular, SAT reduces to $L$. Since SAT is NP-complete by Cook's theorem, there exists an NP-complete problem $L'$ (namely SAT) that reduces to $L$.

$\Longleftarrow$ Suppose $L$ is in NP and some NP-complete problem $L'$ reduces to $L$. We will show that every problem $M$ in NP reduces to $L$, and so $L$ is NP-complete. Given a problem $M$ in NP, since $L'$ is NP-complete, $M$ reduces to $L'$. Since $L'$ reduces to $L$, $M$ also reduces to $L$, and we're done.

The proof used two properties: (1) there exists some NP-complete problem, (2) reducibility is transitive: if $A$ reduces to $B$ and $B$ reduces to $C$ then $A$ reduces to $C$.

Finally, any two NP-complete problems reduce to each other (via the definition), and in this sense they form an equivalence class of the reduction relation.


Algorithm notation between two functions I have two functions,
$$ f = n^{1.6} $$
$$ g = n^{1.5} $$

I thought this is $ f=\theta(g) $, since $ f $ is asymptotically tight bound of $ g $, if $ n $ goes to infinity. However, the answer is  $ f = \omega(g) $.
Can anyone explain why it is $ f = \omega(g) $ ?
Thanks in advance!

$\frac{f(n)}{g(n)} = \frac{n^{1.6}}{n^{1.5}} = n^{0.1}$ is unbounded. Hence, for any $c > 0$ there is $n_0 \in \mathbb{N}$ such that $n^{0.1} > c$ for all $n > n_0$. As a result, for any $c > 0$, we have $n^{1.6} = n^{0.1} \cdot n^{1.5} > c n^{1.5}$ for all $n > n_0$.

Notice this does not really make use of $1.5$ and $1.6$ other than $1.6 > 1.5$. In fact, using the same method and the fact that $n^\varepsilon$ is unbounded for any $\varepsilon > 0$, you can prove the more general bound $n^a \in \omega(n^b)$ for any $a > b \ge 0$.


Is there a name for this traversal-optimized representation of a binary tree data structure? I have used a purely functional binary tree structure in which there is a single node that is "marked". It allows for $O(1)$ access and modification of the marked node's value, as well as $O(1)$ traversal upwards and downwards.

It is represented as a pair $(M, P)$, where $M$ is the marked sub-tree and $P$ is a list of parent segments. For example, in the following tree

, the blue subtree is "marked". Groups of nodes joined by solid lines are parent segments, and parent segments are separated by dotted lines.

The marked subtree could be represented as follows (where Terminal represents the absence of such a node in the diagram):

(Tree 17
    (Tree 19 Terminal Terminal)
    (Tree 23 Terminal Terminal))

The parents could be represented as:

[ (Right 13
      (Tree 29 Terminal Terminal))
, (Right 11
      (Tree 31 Terminal
          (Tree 37
              (Tree 41 Terminal Terminal)
              Terminal)))
, (Left 2
      (Tree 3
          (Tree 5
              (Tree 7 Terminal Terminal)
              Terminal)
          Terminal))
]

The marked node's value can be accessed and modified in $O(1)$ because it is at the top of the marked subtree.
Traversal downwards can be done by choosing one subtree and turning the previous node into a Left- or Right-valued tree that stores the other child, which is added to the list of parents.
Traversal upwards can be done by converting the most direct parent from a Left- or Right-valued tree to a full tree by filling in the other side, and then using the result as the new marked subtree.

I used the term AccessTree for this representation of the tree, but I decided the name was unclear.

Has this representation of a tree ever been given a name? If so, what is it?

This representation is known as a "zipper" and is described by Gérard Huet in his paper "The Zipper":

  The basic idea is simple: the tree is turned inside-out like a returned glove,
  pointers from the root to the current position being reversed in a path structure. The current location holds both the downward current subtree and the upward path. All navigation and modification primitives operate on the location structure. Going up and down in the structure is analogous to closing and opening a zipper in a piece of clothing, whence the name.


how can i prove the following algorithm? Exp(n)
  if n == 1
    return 2

  If n == 0
    Return 1
  End If

  If n%2==0
    temp = Exp(n/2)
    Return temp × temp
  Else //n is odd
    temp = Exp((n−1)/2)
    Return temp × temp × 2
  End if

how can i prove by strong induction in n that for all n ≥ 1, the number of multiplications made by Exp (n) is ≤ 2 log2(n).
ps: Exp(n) = 2^n or Power(2, n)

To compute $\exp(1)$ it does $0$ multiplications, since it enters the if and returns 2.
Assume that, for all $k<n$, to compute $\exp(k)$ it does no more than $2\log_2(k)$ multiplications.
To compute $\exp(n)$ we have two cases. Either $n$ is even and the number of multiplication is $1$ more than the number done for $\exp(n/2)$, or $n$ is odd and the number of multiplications is $2$ more than the number of multiplications done for $\exp((n-1)/2)$.
In the first case we have that the number of multiplications is no more than $2\log_2(n/2)+1=2\log_2(n)-2+1\leq 2\log_2(n)$. In the second case the number of multiplications is no more than $2\log_2((n-1)/2)+2=2\log_2(n-1)\leq 2\log_2(n)$.
Therefore, the number of multiplications to compute $\exp(n)$ is no more than $2\log_2(n)$.
By induction, this holds for all positive integers $n$.


Relation between Russellian type theory and type systems I recently realized that there is some sort of relation between Russellian type theory and type systems, as found e.g. in Haskell. Actually, some of the notation for types in Haskell seems to have precursors in type theory. But, IMHO, Russell motivation in 1908 was to avoid Russell's paradox, and I am not sure how that is related to type systems in computer science.

Is Russell's paradox in one form or another something that we would have to worry about, for example, if we didn't have a good type system in a given language?

``Type theory" in the sense of programming languages and in the sense of Russell are closely related.  In fact, the modern field of dependent type theory aims to provide a constructive foundations for mathematics.  Unlike set theory, most research in type theory based math is done in proof assistants like Coq, NuPRL, or Agda.  As such, proofs done in these systems are not only "formalizable" but actually fully formal and machine checked.  Using tactics and other proof automation techniques we try to make proving with these systems "high level" and thus resemble informal mathematics, but because everything is checked we have much better guarantees on correctness.

See here

Types in ordinary programming languages tend to be more limited, but the meta theory is the same.

Something similar to Russell's paradox is a major issue in dependent type theory.  In particular, having

Type : Type

usually leads to contradiction.  Coq and similar work by nesting universes

Type_0 : Type_1

but in Coq by default these numbers are implicit as they normally don't matter for the programmer.

In some systems (Agda, Idris), the type in type rule is enabled via a compile flag.  It makes the logics inconsistent, but often makes exploratory programming/proving easier.

Even in more mainstream languages, Russell's paradox occasionally shows up.  For example, in Haskell, an encoding of Russell's paradox combining impredicativity and open type case is possible, allowing one to build divergent terms with out recursion even at the type level.  Haskell is ``inconsistent" (when interpret as a logic in the usual way) since it supports both type and value level recursion, not to mention exceptions.  None the less, this result is rather interesting.


Is it always possible to convert a k-tape Turing machine to a single-tape one without increasing its running time complexity exponentially? I am studying the past exam paper of course Theory of Computation. I know it is always possible to convert a k-tape Turing machine to a single-tape one, but how will the running time complexity be changed?

It actually depends on the way you implement a k-tape Turing Machine as a single-tape one.

Using the standard implementation, you can prove that the single-tape machine will take quadratically more computation time.


Genetic algorithm: What is the expected number of strings that are explored? My question concerns genetic algorithm searching along bit strings.

Given:

$N$ = population size
$l$ = length of bit strings
$p_c$ = probability that a single crossover occur (double crossover never occur)
$p_m$ = probability for a given bit that a mutation occur

$w(x)$, the fitness function is equal to the number of 1 in the strings. Therefore, the fitness can take any integer value between 0 and $l$ (the length of the strings).

My question is (three ways of formulating the same question):

What is the expected total number of possibilities explored in $G$ generations?

or

What is the expected proportion of the total possibility space (which equals $2^l$) that is explored in $G$ generations?

or

What is the expected size of the subset of strings that have ever existed in the population during a simulation that last $G$ generations?

Secondary questions:

How does the frequency distribution - of the total number of possibilities explored in $G$ generation - looks like?

is it a normal (Gauss) distribution?
Is it skewed?
...

I don't quite know how complex is my question. Here are two assumptions that one would like to consider in order to ease the problem.

one might want to assume that the population at start is not randomly drawn from the possibility space. He could assume that the whole population is made of identical strings (only one instance). For example, the string 000000000 (which length equals $l$).
one might want to assume that $p_c = 0$

As I pointed out in the comments, the primary feature of interest for understanding how a genetic algorithm (or evolution, even) explores the fitness landscape is the fitness function. In this case, you specified an extremely simple fitness function with no epistasis. This was a standard assumption for analytical tractability when biology first started out (i.e. most analyses that have Fisher somewhere in the name probably assume no epistasis), but it is seen as less reasonable now. Hence, if your goal was to gain biological intuition, this question will not provide it. Since landscape with epistasis have qualitatively different dynamics.

Finally, you don't specify a selection function, so to give you a heuristic answer I will assume one that has strong selection.

First note, that at any given time, the number of genotypes you explore is bounded above by the trivial bound of $GN$. To start building a better bound, lets look at Wilf & Evans (2010) that analyzed a no-epistasis model under strong selection is a sexual population (i.e. with recombination). They showed, that it converges to equilibrium (the all $1$s string in your case) in $\Theta(\log l)$ (they actually showed a tighter characterization with a careful analysis of radix-sort, but I will leave that exploration upto you) generations (I think we have to assume that $N \in \omega(l)$). Thus, you will reach the peak very quickly.

On the way to the peak, you will explore $O(N \log l)$ genotypes. In fact, if the selection strength is very high, then we can assume that the population remains close-to monomorphic in terms of the phenotype specified as "number of ones in the genome" although polymorphic in terms of the genotype. This can give us a bound of about $O(l^2 \log l)$.

Once you reach the peak, strong selection will keep you there, and any mutants will go extinct after each generation. This means that from there on out, the population will just stay at the string $1^l$ with transient (single-generation) mutants of Hamming-distance one.

This gives us a pretty ridiculous bound $\min (O(GN), O(l^2 \log l))$. In other words, as long as you look at generations $G \in \Omega(\log l)$ you will only end up sampling an exponentially small fraction of the genome space $O(\frac{l^2 \log l}{2^l})$.


Where do the length restrictions of the pumping lemma come from? For a language $L$ with pumping length $p$, and a string $s\in L$, the pumping lemmas are as follows:

Regular version:
If $|s| \geq p$, then $s$ can be written as $xyz$, satisfying the following conditions:

$|y|\geq 1$
$|xy|\leq p$
$ \forall i\geq 0: xy^iz\in L$

Context-free version:
If $|s| \geq p$, then $s$ can be written as $uvxyz$, satisfying the following conditions:

$|vy|\geq 1$
$|vxy|\leq p$
$ \forall i\geq 0: uv^ixy^iz\in L$

My question is this: Can someone give a concise and clear explanation of how regularity (context-freeness) imply the first and second conditions above? The pumping length is determined by (finite) properties (finite number of states or finite properties of production rules, respectively), the third properties guarantee that a state (production rule) can be skipped or repeated arbitrarily many times, but where do the first and second conditions originate? How are they justified?

The first condition, i.e. $|y| \geq 1$, is clearly necessary if you want to say something interesting: for $y = \varepsilon$, $xy^iz \in L$ trivially and always holds.

The second condition, i.e. $|xy| \leq p$, is "arbitrary": the lemma still says something interesting if you drop it, and it is still true because the statement becomes weaker.

But remember what we want to use the pumping lemmas for: we want to find a (sufficiently long) word such that all valid decompositions into $x,y,z$ fail to pump. Therefore, it is useful to allow as few such decompositions as possible. Lucky as we are, the proof of the pumping lemma readily yields a strong restriction, namely that there has to be a pumpable decomposition with $|xy| \leq p$ with constant $p$.

Now we have to refute only finitely many prefixes $xy$ (with possibly infinitely many different continuations, of course). If you look at example applications, you will see that they make heavy use of this restriction.


Finding a Hamilton path in a Complete Euclidean Graph is in P How is it possible to prove that this assert is not true?

This assertion is, in fact, true. A complete graph (which doesn't even have to be Euclidean) always has a Hamiltonian path: number the vertices in an arbitrary order, start at the first one, then proceed in order to the last (and then back to the first to make a cycle if you want). Since the graph is complete, the edges you need will always exist.

Thus, the problem can be decided in $O(1)$, which is polynomial, so it is in $P$. The algorithm is trivial:

define doesThisCompleteGraphHaveAHamiltonianPath(G):
    return Yes


Which theoretical parallel model is closest to CUDA? Which theoretical parallel model is closest to CUDA/OpenCL programming model?

For example, it fits at some degree to the generic Parallel Random Access Machine (PRAM) model. However, that is too generic, since it makes abstraction of various memory access latencies and synchronization issues.

My question is which is the theoretical model that CUDA architecture fits closest (having in mind the hierarchical parallelism of threads and blocks of threads that cooperate)?

To the best of my knowledge, it may be the Queuing Shared Memory (QSM) model, even though hierarchical parallelism of threads is not taken into account. However, accesses to local memory and global memory (different bandwidth), and bulk synchrony (in which threads can work asynchronously beetween barrier synchronizations) are considered.


What's the time complexity bound for the Knapsack with real weights? Let's start with the formalism:
Let $W$ be the total weight of our bag, $1,...,n$ be our elements, $w_1,...,w_n$ their corresponding weights, and $v_1,...,v_n$ their corresponding values.

As is known, the knapsack problem for integer weights can be solved by dynamic programming (or equivalently, using recursion + memoization), with time complexity of $\mathcal O(nW)$, where $W$ is the total weight our bag can hold, and $n$ is the number of items.

However, for real numbered weights, the algorithm fails (just imagine a billion items with weight $<1$, and $W=1$). We probably can round them in a clever way and then scale them up to be integers again, but that'd blow the size of the problem up in an inacceptable way.

Another approach would be to use recursion instead of dynamic programming, because the idea behind the algorithm still works out - either the $n$'th item is in the optimal solution, or not.

However, even with memoization, we can easily choose our weights in a way so that all sums
$$\sum_{
\begin{align}
 i&\in M\\
M&\subseteq \{1,..,n\}
\end{align}} w_i$$

are distinct, leaving us with $2^n$ weight-sums to memoize.

Is there any optimal algorithm that manages to keep the time complexity pseudopolynomial?

If you have n random real numbers, then you have 2^n possible real sums. If your knapsack has size S, you would expect 2k different sums in an interval $S-k\cdot 2^{-n}, S+k\cdot 2^{-n}]$, in other words calculating sums with a precision of $k\cdot 2^{-n}$ isn't enough to give the optimal sum.

With random integers, you can find an optimal sum because of the $2^n$ possible sums, there will be gazillions getting the same result. You wouldn't be able to list all choices that fill the knapsack exactly because there are to many of them, but you can find one.

You can most likely solve the problem "find items that fit in the knapsack, and have a total size at most eps less than the optimal size".