Difference between centralized computing and distributed computing using Client-Server

As a contrast to "distributed", "centralized" means one computer.  Sometimes (not so much nowadays) this may be a mainframe with multiple "dumb" terminals in which all the work happens on the mainframe and the terminals just take in inputs and display outputs.  If the terminals aren't "dumb", meaning they can do non-trivial computation of their own (and, in particular, maintain state), then this is essentially an example of a distributed, client-server system.  Your description of "distributed" corresponds to a peer-to-peer system which is but one form of a distributed system.

Admittedly, there has been a level shift in the terms, and/or they are applied at a logical level.  For example, Facebook would be considered a "centralized" system insofar as it's controlled by a single entity, as opposed to Diaspora which is decentralized.  I think it has become popular to use the term "distributed" when "decentralized" may be a better term.  Of course, Facebook has many servers spread across the world, and so it's infrastructure is very much distributed.  Similarly, a single data center for Facebook may logically be a single "server" but internally is a distributed system as well consisting of hundreds of physical servers.

Wikipedia does a pretty good job of outlining the key characteristics of a distributed system from a theoretical perspective:

  Three significant characteristics of distributed systems are:
  concurrency of components, lack of a global clock, and independent
  failure of components.

Though I would add to that list that the communication medium is unreliable.  The focus of distributed computing, in both theory and practice, is dealing with various forms of failure.  Wikipedia's use of the more generic term "component" suggest that this notion can be applied at different levels.  For example, you can fruitfully think of the various sub-systems of a single computer (on the motherboard) as forming a distributed system if your focus is on timing and failure issues.  Even single multi-core CPUs are becoming more and more like distributed systems with the cores as the "components".


How exactly does on describe the formal semantics of the Applied $\pi$-Calculus?

You are roughly correct. From an operational point-of-view, applied-$\pi$ is 'just' a $\pi$-calculus where interesting  values (rather than just pure names) can be communicated.

Note that in process theory we usually care about coarser notions of equality, such as observational equivalence. This is defined in Section 4.1. Alas observational equivalence is hard to work with in practise due to the universal quantification over all contexts, so we define a second relation which is easier to deal with, in this case  labelled bisimilarity. In order to do this, we need labelled transitions rather than reductions. We must show that  these two forms of computation coincide.

To make matters even more complicated, Theorem 1 which claims that observational equivalence coincides with labelled bisimilarity is wrong.


Proof that a guard digit bound the error of subtraction

I'll post some elements of answer to my own question from what I understand. Anyone feel free to make a better, less sloppy answer.

First, there are several versions of this document online. They all have some typographic defects at some point. So when in doubt, better check those 3 versions first.

https://www.itu.dk/~sestoft/bachelor/IEEE754_article.pdf
https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html
https://ece.uwaterloo.ca/~dwharder/NumericalAnalysis/02Numerics/Double/paper.pdf

Second, there's a lot of implicit stuff going on with this first actual proof. So let's clarify some of them.

Reachable bound of $y - \bar{y}$

I think that, no, the bound on $y - \bar{y}$ cannot be reached. Let's try to go for the worst case with $k = p+1$. Let's assume $p = 6$ and the radix $\beta = 10$.
\begin{align}
y           & = \overbrace{0.000000}^{k=7}\overbrace{999999}^{p=6} \\
\bar{y}     & = \overbrace{0.000000}^{p+1=7} \\
y - \bar{y} & = 0.000000999999 \\
            & = 9 \times (10^{-7}+\dots+10^{-12}) \\
            & = (\beta - 1)(\beta^{-p-1}+\dots+\beta^{-p-p}) \\
            & \lt (\beta - 1)(\beta^{-p-1}+\dots+\beta^{-p-p}+\beta^{-p-(p+1)}) \\
            & \lt (\beta - 1)(\beta^{-p-1}+\dots+\beta^{-p-p}+\beta^{-p-k})
\end{align}

I had to add an extra term to the sum (i.e. an extra digit) to get the same formula as the paper. Hence the $=$ got transformed to $\lt$.

This exact bound simplify the second case of the proof. Although a looser and simpler bound $y - \bar{y} \lt \beta^{-p}$ would be enough for the first case when $x - y \ge 1$.

No rouding error when $x - \bar{y} \lt 1$

The assertion that if $x - \bar{y} \lt 1$, then $\delta = 0$ seems true. The rounding error $\delta$ is the error we introduce by removing the guard digit to produce the final result. This is sometimes needed because $\bar{y}$ has $p+1$ digits and $x - \bar{y}$ might as well have $p+1$ digits.

For instance:
\begin{align}
x           & = 2.00000 \\
y           & = 0.0123456 \\
\bar{y}     & = 0.012345 \\
x - \bar{y} & = 1.987655
\end{align}
The result has $7$ digits therefore has to be rounded to $6$ digits.

But when $x - \bar{y} \lt 1$ then the result starts with the digit $0$. Meaning that at most only $p$ significant digits remain from the $p+1$ digits used to perform the subtraction. For example:
\begin{align}
x           & = 1.00000 \\
y           & = 0.0123456 \\
\bar{y}     & = 0.012345 \\
x - \bar{y} & = 0.987655
\end{align}
The result $x - \bar{y}$ already has 6 digits. So no rounding error need to be introduced.

However, it is worth noting that this doesn't change anything to the error introduced by truncating $y$ to $\bar{y}$.

Minimum value of $x - y$

When the paper say that the smallest value $x - y$ can take is:
$$1.0 - 0.\overbrace{0 \dots 0}^k\overbrace{\rho \dots \rho}^k$$
there's actually a typo that has been corrected in other documents. What was ment to be written is:
$$1.0 - 0.\overbrace{0 \dots 0}^k\overbrace{\rho \dots \rho}^p$$
which make more sens and is the general formula when $k$ is fixed. Maybe a better form could be:
\begin{align}
x - y & \ge 1.0 - 0.\overbrace{0 \dots 0}^k\overbrace{\rho \dots \rho}^p \\
      & \ge 0.\overbrace{\rho \dots \rho}^k\overbrace{0 \dots 0}^{p-1}1 \\
      & \gt 0.\overbrace{\rho \dots \rho}^k
\end{align}

Which lead naturally to the formula written in the paper.

Third case: $x - \bar{y} = 1$

And finally, another implicit point of this proof (not asked but worth writing down): why would having both $x - y \lt 1$ and $x - \bar{y} \ge 1$ imply that $x - \bar{y} = 1$?

I think the informal answer would be that since $x$ is a float with $p$ digits, then $x - 1$ is also a float with $p$ or $p - 1$ significant digits (if $x >= 2$ or $x < 2$ respectively). Meaning that truncating $y$ to $\bar{y}$ cannot make it less than $x - 1$ since $y > x - 1$ and $x - 1$ is a candidate value for $\bar{y}$ and is less than $y$.

In other words: $x - y \lt 1$ imply that $x - \bar{y} \le 1$. Therefore, having this and $x - \bar{y} \ge 1$ at the same time imply that $x - \bar{y} = 1$.


Some things you could explore are metaheuristics. The following methods don't make assumptions about the function to be optimized, and some are relatively simple to understand and implement.

Some of these mantain a population of possible solutions, recombining them to create new possible solutions and keeping the best ones.

Differential evolution
Particle Swarm
Evolutionary algorithms

There are a lot more, with a lot of published variations.

It is my understanding that they are very capable, you can expect the error to be much smaller to the error margin you mentioned and the acceptable error can be used as a parameter for the halting condition of the algorithm. If the target function is computationally cheap to evaluate these methods should be very competitive.

In particular differential evolution could be a place to start exploring. You can use an already written implementation on scipy's optimize.

There are other approaches, some of which make assumptions about the function to be optimized. You can see some examples on Wikipedia  (Computational optimization techniques section).


Maximize the number of satisfied disjunctions

You are addressing a problem of the same type. if you use De Morgan law your problem will become MIN-SAT which is  NP-HARD

checkout THE MINIMUM SATISFIABILITY PROBLEM


I am reading on how [...] to solve unweighted bipartite graph matching problem. [...] The goal of the problem seems to be to find a maximum matching in a complete bipartite graph

No, the goal of the problem is to find a maximum matching in any unweighted bipartite graph.


Each tweet and each cluster is represented as an $m_k$-dimensional vector. The distance between a tweet $t_k$ and a cluster $\delta$ is then
$$
dis(t_k,\delta) = 1 - \frac{\langle t_k, \delta \rangle}{\|t_k\| \|\delta\|},
$$
where $\langle a,b \rangle = \sum_{i=1}^{m_k} a_i b_i$ is the inner product and $\|a\| = \sqrt{\langle a,a \rangle}$ is the norm. This explains equation (4).

The definition of $P(S_t|w)$ is given below (6):

  $P(S_t|w)$ is the
  probability that a term has a score with the given tweet score.

This is the number of tweets containing $w$ which have score $S_t$ divided by the total number of tweets containing $w$.

The rest of the formula is hopefully self-explanatory ($\times$ is just ordinary multiplication).

If you have any more questions, I suggest contacting the authors.


How does f(n) < cg(n) specify time?

It doesn't. Bachmann-Landau notation is simply a handy way to compare the growth-rate of functions. It doesn't say anything about what those functions mean, and we can be pretty sure that Bachmann wasn't thinking about computers when he came up with it in 1894.
What meaning you assign to those functions is up to you. For example, when analyzing comparison-based sorting algorithms, we typically take $n$ to be the number of elements in the collection and $f(n)$ to be the number of comparisons, or the number of swaps, or the number of comparisons and swaps.
Note also that all of this is always relative to a machine model or a cost model.
As a very simple example, if I were to ask you what is the algorithmic worst-case step complexity for copying a list, you would say $O(n)$. But actually, the correct answer would be "I can't tell you that because you haven't specified the machine model". Because, for example, in a Turing machine, copying a list is $O(n^2)$, because for each element being copied, the head of the TM has to drive further and further and further to reach the end of the list to write the next element.


Represent an octree as a binary tree of thrice the depth?

They're very similar, as you say.  Their asymptotic running time is equivalent; the difference in running time and space usage is at most a small constant.

However, in practice, constants can matter.  In practice, the octree might perform better, due to its better memory locality.  If the depth of the octree is $d$, the depth of your corresponding binary tree will be $3d$.  That means looking up an element requires three times as many pointer indirections in your binary tree.  Pointer indirections are expensive because they typically cause a miss in the cache (they cause random access to memory, which is the worst case for memory hierarchies).  Consequently, in practice, it's possible that the binary tree implementation might be up to three times slower than the octree, due to the increase in cache misses and the poorer memory locality.

Of course, the only way to know for sure is to implement and measure on some benchmarks.  But this is one plausible reason why octrees might be preferable in practice.


Has anyone found polynomial algorithm on Hamiltonian cycle isomorphism?

What follows is taken from Tsuyoshi Ito's comment.

As rizwanhudda said, this problem is a special case of the graph isomorphism problem and therefore it is not known to be NP-complete. We cannot say “this problem can’t be NP-complete” because of that, because the graph isomorphism problem might be NP-complete. However, many complexity theorists believe that the graph isomorphism problem is not NP-complete (and therefore they will believe that your problem is not NP-complete, either) because the NP-completeness of the graph isomorphism problem would contradict the conjecture called “the polynomial hierarchy does not collapse.”


Usually, an operator that's written implicitly by just putting the operands next to each other (e.g., "$xy$" for $x\land y$ in logic or $x\times y$ in arithmetic) has precedence over binary operators that are written out explicitly (e.g., $\lor$ or $\oplus$ in logic, or $+$ in arithmetic). Indeed, any author who uses a different convention to that needs a good stern talking to.  But note that it is only a convention.

So the expression in the question means $(xy)\oplus z$, unless the person who wrote it hates us. This view is reinforced by the fact that logical and is multiplication modulo 2, and xor is addition modulo 2 and we'd expect multiplication to have precedence over addition.


The language $A = \{ a^n\:b\:c^{2n}\:b^m |\; n ∈ N^{+} ;\; m ∈ N \}$ is not obviously regular since finite automata do not have memory and hence it is not possible for them to determine the relation between $a$ and $c$.

Let us try to construct a Type-2 grammar for this language. Note that Type-2 grammars are of the form  $V\to(V \cup T)^{*}$ where $V$ represents non-terminals and $T$ represents terminals. So our example would lead to something like this:

$S \to a\:A_1\:cc\:A_2 $

$A_1 \to a\:A_1\:cc\;|\;b$

$A_2 \to b\:A_2\;|\;\epsilon$

Hence we see that this is a Type-2 grammar according to the Chomsky hierarchy.


Is $G_2(V_2,E_2)$ a subgraph of $G_1(V_1,E_1)$ given number of vertices and adjacency matrix for both?

This problem is more general form of the graph isomorphism problem. No polynomial time algorithm is known solving it. The state of the art suggests possible approaches.


The string much start with $ bb $ .
There should at least one occurrence of the sub-string $ bab $

Hence, the structure of the regular expression must be something like this:
$$ bb[some \: string]bab[some \: string] $$

and, we can define $ [some \: string] $ something like this:

$$ (a + b)^* $$

which means, there can be any number (including 0) of either a's or b's.
Therefore, the final regex for the word is,
$$ bb(a+b)^*bab(a+b)^* $$


Explanation of a specific recurrence with respect to Master Theorem

Sometimes the master theorem is only given for recursions of the form $T(n) = aT(n/b) + \Theta(n^k)$, but the Wikipedia article includes a more general version which can handle functions of the form $T(n) = aT(n/b) + \Theta(n^k(\log n)^l)$, and even more general ones when $k \neq \log_b a$. The similar Akra-Bazzi theorem handles more general situations.


Are there any problems that require exponential time in quantum computing?

Most problems that require exponential time on a classical computer also require exponential time on a quantum computer.  For example EXPTIME-complete problems will require exponential time on either a classical or a quantum computer.

The class of problems solvable in polynomial time on a quantum computer is called BQP.  It is believed unlikely that BQP contains the NP-complete problems.  Thus the NP-complete problems probably take exponential time on quantum computers.

One of the most interesting problems that is known to be in BQP, but believed not to be in P is the integer factoring problem.  But integer factoring is believed unlikely to be NP-complete.


$O(k)$ Algorithm to find the first $k$ pairs of Magic numbers $a$ and $b$ such that $\sum_{i=1}^{a-1} i = \sum_{k=a+1}^b k $, with restrictions

There are different ways you can use to solve that problem.

One simple but inefficient solution is just that of just computing the two sums in parallel while only keeping track of the difference between their partial sums. I.e., if you added the first $x$ terms of the first sum and first $y$ terms of the second sum, then you'll only remember $x$, $y$, and $\Delta = \sum_{i=1}^x i - \sum_{k=a+1}^{a+1+y} k$.  If $\Delta$ is non-positive, then consider the next term of the first sum (i.e., increment $x$ by one and add $x$ to $\Delta$). If $\Delta$ is positive, then consider the next term of the second sum (i.e., increment $y$ by one and subtract $a+1+y$ from $\Delta$). In this way $|\Delta|$ will never exceed $\max\{a,b\}$.

Another more efficient solution is as follows. Using the summation formula you can write:
$
\sum_{i=1}^{a-1} i = \frac{a(a-1)}{2} = \frac{b(b+1)}{2} - \frac{a(a+1)}{2}
= \sum_{k=a+1}^{b} k$, and some simplifications lead to:
$2a^2 = b(b+1)$.

This means that, once you fix $b$, you can find the corresponding value of $a$ as follows:
$$
a= \frac{1}{\sqrt{2}} \cdot \sqrt{b} \cdot \sqrt{b+1}.
$$

Notice that $\sqrt{b} \cdot \sqrt{b+1}$ must always be greater than $b$ and smaller than $b+1$, meaning that  $\frac{b}{\sqrt{2}} < a < \frac{b}{\sqrt{2}} + \frac{1}{\sqrt{2}}$ and, since $\frac{1}{\sqrt{2}} < 1$, there is at most one integer in that interval, namely $ 1+  \left\lfloor \frac{b}{\sqrt{2}} \right\rfloor = 1+  \left\lfloor \frac{\sqrt{2} b}{2} \right\rfloor $.


Proof: "If the list is then k-sorted for some smaller integer k, then the list remains h-sorted"

the claim follows easily from a careful definition of "k-sorted". define k-sorted as "for all i there does not exist a j > k such that for two elements in the list a[i+j] < a[i]." then if a list is k-sorted, it is h-sorted for h > k.

to look into deeper/ more general theory realize that k-sorted is a "measure of disorder" eg as in question how to measure sortedness. see this paper a survey of adaptive sorting algorithms, / Castro, Wood, measures of disorder, sec 1.2. h-sorted appears to be equivalent to measure #1, Dis, "largest distance determined by an inversion".


In the survey Treewidth, partial $k$-trees, and chordal graphs by Pinar Heggernes, we have the following lemma, whose proof is given as an exercise.

  Lemma. Let $(\{X_i \mid i \in I\}, T = (I, M))$ be a tree decomposition of $G = (V, E)$, and let $K \subseteq V$ be a clique in $G$.  Then there exists an $i \in I$ with $K \subseteq X_i$.

Prove this lemma, and conclude that, as Yuval answered,

  Corollary. For every graph $G$, $tw(G) \geq \omega(G) - 1$.

Conclude that the treewidth is at least three.

The treewidth happens to be at most three as well, but that's a different exercise.


$L_{\geq5}$ is RE. Basically, given a machine $M$, you iterate through all strings, starting with all of length 0, then length 1, etc. You simulate $M$ and test if the current string $s$ is accepted by $M$. If it is, then you increment some counter. If the counter ever hits 5, you accept. There's no guarantee that this will terminate, which is why it's RE and not recursive. There is a guarantee, however, that it will terminate for any input machine $M$ that does accept 5  or more strings.

We know from Rice's theorem that $L_{\geq5}$ is not recursive, and since it is RE, then we know its compliment is not RE. So $L_{<5}$ is neither RE or recursive.

Intuitively, you could iterate through all strings, but there would never be a point where you could say "Based on the strings I've seen so far, I know that this machine accepts less than 5 strings." Even if you accept less than 5 so far, there's no way of knowing that there aren't larger strings which would be accepted.


First, when doing complexity analysis, we usually think in terms of decision problems, i.e. the answer must be yes or no, and here you have an optimisation problem. This is why you are struggling to find a certificate here. If you reformulate your problem as a decision problem with an additional parameter $k$, and the question become "Is there a subset I such that the sum (...) Is greater than k ?", You will easily find the certificate : the list of the vertices in I, you can polynomially check that there are as many elements of V and W, and that the sum has the desired property.

Second, it seems like your are trying to reduce your problem to VERTEX-COVER. However, we already know that's possible because VC is NP-complete. To show that your problem is NP-Hard, you have to reduce a NP hard problem to it.

Finally, the reduction : maybe something from VERTEX-COVER will work : take an instance with a graph G=(V,E), make it complete by adding edges and put their weight to 0 (then your problem will not "try" to get them). If you find a clever way to divide V into V and W, the reduction might work.
However, it seems to me that VERTEX-COVER does not have a condition on sets and partitions, and you might have more luck with Subset-sum or 2-partition.

Edit : after a bit of thinking, If you make 2 copies of G (one becomes your V and the other W), and complete it with 0-weighted edges, you juste have to find the correct value for k... I think that's not too far.

I hope that helps.


DFA multiple accepting states to Regular expression

Your DFA accepts all words not containing $aaa$. Such words are built of the following "building blocks": $b,ab,aab$. Additionally, a word may end with $a,aa$. In total, we get the regular expression
$$
(b+ab+aab)^*(\epsilon+a+aa).
$$


About the first order logic (valid, Unsatisfiable, Syntactically wrong)

1 uses a function symbol Processor which is not in the logic signature. Hence, it's outside the syntax.

4 tries to equate a proposition with Speed(MyPC). You can't equate propositions in FOL. Outside the syntax.

3 is not universally true for every function Speed and every argument MyPC.
For instance interpret MyPC as the natural $0$, and Speed as the successor function to obtain $\mathsf{succ}(0)=0$ which is false. Hence the formula is not valid. However, it is satisfiable: now interpret MyPC as zero and Speed as the identity function to obtain $\mathsf{id}(0)=0$ which is true. The formula has a model and a countermodel: satisfiable and invalid.

2 ∃ x ( Speed(x) = Speed(MyPC) ) is always true, since we can take x to be MyPC. This holds no matter how we interpret Speed and MyPC. Hence is it valid. (Alternatively, we can even show it is a theorem of FOL using a proof system, and then rely on the correctness theorem to claim it is valid.) Since formula 2 is the negation of a valid formula, it is unsatisfiable.


Applications of Lamport's Distributed Mutual Exclusion algorithm

Lamport introduced his distributed mutual exclusion algorithm as an example in

  Lamport, Leslie: Time, Clocks and the Ordering of Events in a Distributed System, Communications of the ACM, 21(7):558-565, 1978.

The link leads to Lamport's personal page, where he has an annotated bibliography of all his work, with PDFs of every paper that has an electronic version.

The paper in question is the one that introduced Lamport timestamps and Lamport clocks.  Here's what Lamport has to say about the distributed mutual exclusion algorithm:

  It didn't take me long to realize that an algorithm for totally ordering events could be used to implement any distributed system.  A distributed system can be described as a particular sequential state machine that is implemented with a network of processors.  The ability to totally order the input requests leads immediately to an algorithm to implement an arbitrary state machine by a network of processors, and hence to implement any distributed system.  So, I wrote this paper, which is about how to implement an arbitrary distributed state machine.  As an illustration, I used the simplest example of a distributed system I could think of--a distributed mutual exclusion algorithm.

The relevance is not that you would use it to protect some kind of centralized resource.  The relevance is rather to show that when you are implementing a distributed state machine, you can actually get all the participants to agree about something, so you don't need centralized resources.


Preforming the proof by induction on the structure of the tree is good way to go about this. I like to think about how I would write a program to remove them because this directly leads to a constructive proof.

Say our regular expressions have the following form

$$
\begin{align}
regex ::=& \,\, regex \,\, regex \\
        |& \,\, regex^* \\
        |& \,\, regex^+ \\
        |& \,\, regex\,? \\
        |& \,\, regex + regex \\
        |& \,\, char \\
        |& \,\, \varnothing
\end{align}
$$

The bases cases are the cases in which the regex is either a character or $\varnothing$

To give an inductive step say we have a regular expression of the form $regex + regex$. We can then recursively convert the two sub parts to regular expressions which either are the empty set or contain no empty set. So we have 4 cases

case 1: Both expressions contain no $\varnothing$ in which case we are done

case 2/3/4: One of the sides (possibly both) is $\varnothing$ so we remove that side. One needs to prove that this is valid but it isn't hard.

all the cases are going to precede as such with different proofs that the empty set can be eliminated.


Are Regular Languages (as we represent by Finite State Machines) Fields?

No, the set of regular languages is not a field, but it is a boolean algebra.  It also qualifies as a field of sets -- but note that the term "field of sets" has nothing to do with the notion of a "field"; it's an unfortunate name collision.  See also https://en.wikipedia.org/wiki/Boolean_algebra_(structure).


Is the reduction for HAMPATH to HAMCYCLE and UHAMPATH to UHAMCYCLE the same?

Your reduction is correct. However, the standard Hamiltonian path problem does not specify the endnodes $s$ and $t$, which is a bit different from your definition. This is possibly why the internet does not use your simple reduction.


Performance of Recursive vs Iterative Solution to "Maximum Depth of a Binary Tree"

The obvious recursive solution (compute the maximal depth of both subtrees, add one for the root) has space complexity $O(\operatorname{depth}(T))$ (i.e., $O(\log n)$  for $n$ nodes). If you write it recursively or do the call stack by hand instead of having the language handle it for you is irrelevant.


Unless I've done this example wrong, this question is asking you to prove something that isn't true. Consider $(x,y) = (381,192) = (3\cdot 127,3\cdot 64)$. What happens when you run the algorithm?

  $(3\cdot127,3\cdot 64,1) \rightarrow (3\cdot127,3\cdot 32,1) \rightarrow \ldots \rightarrow (3\cdot 127,3,1)$
  $ (3\cdot 127,3,1) \rightarrow (3\cdot 126,3,1) \rightarrow (3\cdot 63,3,1) \rightarrow \ldots \rightarrow (3,3,1) $
  $ (3,3,1) \rightarrow (1,0,3) $

So starting with $( 3\cdot (2^k -1), 3 \cdot 2^{k-1}, 1)$, the first set of steps applies the 5th rule $k-1$ times, resulting in $(3 \cdot (2^k-1), 3, 1)$. We then alternately apply the 7th rule and the 6th rule. Each time we do this, we go from $(3\cdot (2^j-1),3,1)$ to $(3\cdot (2^{j-1}-1),3,1)$, until we reach $(3\cdot(2^1-1),3,1)$. This takes $2(k-1)$ transitions. Finally, we apply the 1st rule once, for a total of $3k-2$ transitions. But the original value has $\log_2 \max(x,y) \approx {k}$, so we needed
$3 \log_2 \max(x,y) - C$ transitions total for some constant $C$.

It's certainly true, and not hard to prove, that the algorithm runs in $O(\log \max(x,y))$. But the question has the constant wrong.


Performance impact due to time required for shuffling in Quicksort

The short answer is that the $O(n\log n)$ component dominates the $O(n)$ component, hence the $O(n)$ part can be ignored in the statement of complexity.


You observed correctly that the number of pairs can grow quadratically with input size. In the worst case, the array contains only two types of numbers, but with great multiplicity.

$$[1,1,1,1,1,2,2,2,2,2]$$

Here, each of the five ones can be combined with each of the five twos, thus creating 25 pairs that sum up to three. It is generally impossible to visit each pair once and maintain linear time complexity.

Luckily, it is not neccessary to visit each pair once, as we can calculate the multiplicity of the pair from the multiplicities of its members. In this case:

$$5 \cdot 5 = 25$$

To find all pairs in linear time, run-length encode the array first. So

$$[0,1,1,1,1,1,2,2,2,2,2,3]$$

becomes

$$[(0,1),(1,5),(2,5),(3,1)]$$

Then, apply the two-pointer algorithm and calculate the multiplicity of each resulting pair directly. Here, the result could be a pair of zero and three with multiplicity one, and a pair of one and two with multiplicity 25.

$$[(0,3,1),(1,2,25)]$$

In total, there are 26 pairs.


Maximize cost in graph with variable costs

There's no need to introduce a graph; the problem can be solved by a straightforward dynamic programming algorithm.  The running time will be $O(n)$, where $n$ is the number of days.


Minimizing Turing machine-like automaton with no final states

What exactly is the difference between your machine and a TM? (apart from not having accepting states, which is quite meaningless since you have an output)

It sounds like this is a very powerful model, and its halting problem will be undecidable, let alone minimization.

EDIT: Minimizing TMs is undecidable (actually, not in $RE\cup coRE$). It is easy to reduce the universality problem to it: given a TM, if you could minimize it, then the minimal TM will consist of a single, accepting state iff its language is $\Sigma^*$.


Computing the minimal flexible distance of two vectors using dynamic programming

Since this is a programming assignment, I only show some hints.

Consider two vectors $\vec{a} = a_1 \cdots a_i \cdots a_m$ and $\vec{b} = b_1 \cdots b_j \cdots b_n$.

First, please prove the following

  Observation: $a_m$ must be matched with $b_n$.

Second, consider the following subproblems,

$$D(i,j) \triangleq \text{the optimal (matching) distance between } a_1 \cdots a_i \text{ and } b_1 \cdots b_j.$$

and answer the following question

  Given the observation above, what is the relationship between $D_{i,j}$ and $D(i-1, j)$, $D(i, j-1)$, or maybe $D(i-1, j-1)$?


The first iteration will do will do $n-1$ comparisons, the next $n-2$, the second $n-3$ and so on. In total $n-1$ iterations are done.

Hence, you need to find the sum of $(n-1)+(n-2) + ... + 1$ which is $((n-1)^2+n-1)/2$ which still is $O(n^2)$. So the optimization does not improve the asymptotic running time.

Note that I edited your algorithm slightly: the outer loop is only iterated $n-1$ times. This is because for each iteration, one more element is put into the right place. Hence after $n-1$ iterations, $n-1$ elements will be in the right place and so element $n$ must also be in the right place.


How to interpret "Windows - Virtual Memory minimum too low" from a CS student point of view?

A computer typically has vastly more hard disk space that RAM. To compensate for limitations in the size of RAM, the operating system reserves part of the disk to use as additional RAM. This is called virtual memory. The RAM and the virtual memory are then divided into even chunks called pages. From the programmer's perspective, there is a large amount of memory available. Under the hood, the operating system keeps some of the pages of memory in RAM and leaves the remainder in virtual memory, on the disk. The operating system tries to ensure that the more commonly used pages are in RAM, as this is more efficient. If a program needs to access memory that it stored on disk, the operating system swaps out a page from RAM and swaps in a page from the disk. This is called paging. Paging is expensive, so the operating system tries to reduce how often it occurs.

If the amount of memory demanded by a program (or the collection of running programs) exceeds the amount of virtual memory, it is possible that the operating system increases the amount of virtual memory. As virtual memory is essentially a file, this explains what is going on when "Windows is increasing the size of your virtual memory paging file."

The "process" you refer to could be called "increasing virtual memory". I'm not sure whether it has a special name.


Give an NL-algorithm for complement of 2-SAT

Question1: What is the difference between 2SAT and the complement of 2SAT?

The set of all strings that do not describe satisfiable 2CNF formulas.

  Question2: It is known that NL is contained in P, but what we know about P over NL? can be said that an algorithm that runs in P, uses NL space?

We don't know anything significant beyond that $\mathrm{NL}\subseteq\mathrm{P}$.

It doesn't really make sense to ask if "an algorithm... uses NL space". You can ask if an algorithm uses logarithmic space and if it's nondeterministic, but there's no such thing as "nondeterministic space" per se. By that, I mean that the storage space itself isn't nondeterministic: nondeterminism is a property of the algorithm that uses the space.

It's certainly not true that an algorithm that runs in polynomial time necessarily uses logarithmic space: it could use polynomial space. It's possible that every deterministic algorithm that runs in polynomial time could be rewritten as a nondeterministic algorithm that uses only logarithmic space but we don't know if that's true or not. If it were true, we would have $\mathrm{P}=\mathrm{NL}$.

Note that, formally speaking, $\mathrm{NL}$ and $\mathrm{P}$ are classes of problems, not algorithms.


Is the MinMax/optimization/search variant of a decision problem always easier/equal?

No.  A reduction only proves that it is "at least as hard", not that it is easier.  Normally, the optimization problem is approximately as hard as the corresponding decision version (to within a polynomial factor).

If the decision problem is in P (can be solved in polynomial time), and there's a polynomial time reduction from the optimization problem to the decision problem, then that implies that the optimization problem can be solved in polynomial time.  It's not literally in P, because P is a class of decision problems, but you can think of it as being in some class that is analogous/similar to P.

It's not clear to me what you mean by "the MinMax variant" or "the max-variant", so I can't answer that part.


Do functions with slower growth than inverse Ackermann appear in runtime bounds?

Seth Pettie came up with an algorithm for computing the sensitivity of a minimum spanning tree in time $O(m\log \alpha(m,n))$, improving on an algorithm of Tarjan which computes the same in time $O(m\alpha(m,n))$. (Compare this to Chazelle's $O(m\alpha(m,n))$ algorithm for computing the minimum spanning tree itself.) The sensitivity problem asks to compute, for a given graph and a given minimum spanning tree, by how much each edge weight can change without changing the minimum spanning tree.

(Thanks to Tsvi Kopelowitz for this reference.)


Subgraph isomorphism reduction from the Clique problem

The decision version of the clique problem asks whether a given graph $G$ contains a complete graph with $k$ vertices as subgraph. The wikipedia article just explains why the decision version of the clique problem is a special case of the subgraph isomorphism problem. Namely if the graph $H$ is the complete graph with $k$ vertices, then the answer to this special subgraph isomorphism problem is just the answer to the decision version of the clique problem.

This shows that subgraph isomorphism is NP-hard, since the clique problem is NP-complete. But the subgraph isomorphism is obviously in NP, since it a given monomorphism from $H$ to $G$ can efficiently be checked to be a monomorphism. So we can conclude that subgraph isomorphism is NP-complete.


Dimension Reduction - Which feature should remove to reduce the dimension of the matrix

In the first table, X2 is an unnecessary feature. You can check that for any row, the value of Y that you obtain after reversing the value of X2 is always unaffected. Instead, X1 and X3 are both individually necessary; this can be seen for example by comparing the first row with the fifth row (for X1) and with the second row (for X3).

In the second table, X1 is an unnecessary feature. The value of Y is solely determined by whether X2 is large or small; say, larger or smaller than 0.5. Hence a linear classifier based on X2 can predict Y with full accuracy. Instead, no linear classifier based on X1 only can correctly predict Y; for example, the value of Y is 1 for X1=0.6931, becomes 0 for X1=0.7465, and becomes 1 again for X1=2.7361.

For the first type of problem, you can look at each feature individually and check whether the results indeed depend on it or not, by comparing corresponding rows as I did in the example.

For the second type of problem, you can look for non-monotonicity (as I did in the example with the X1 feature), in which case you can exclude the non-monotone feature, at least if you are looking for a linear model.


What's wrong with the following argument that $NP \subset coNP$?

This is not true:

  Then if $z \in \bar{L}$ then $N$ will not have accepted $z$ after any number of steps, so $z \in L(H)$.

It might be $z \in \bar{L}$, but the machine will not be stopped anytime!


There are (at least) three algorithms that convert a regular expression to an equivalent finite-state automaton:

Thompson's construction (see e.g. the Wikipedia article)
McNaughton and Yamada's construction
Glushkov's construction (see e.g. the Wikipedia article)

Büchi automata enter the picture if you are working with $\omega$-regular expressions. See e.g. this description of the algorithm for constructing an equivalent Büchi automaton from an $\omega$-regular expression.


A language which is neither r.e. nor co-r.e

Recall that a language is r.e. iff its complement is co-r.e. It follows that a language is neither r.e. nor co-r.e. iff its complement is neither r.e nor co-r.e., just like a language is recursive iff its complement is.

The language $L_{\exists}$ is recursively enumerable, though not recursive. To enumerate it, simulate all Turing machines on all possible inputs, and output a Turing machine whenever it halts on some inputs. To see that it's not recursive, reduce the halting problem to it.

Your other example $L_{\forall}$, usually known as TOT, is indeed neither r.e. nor co-r.e. In fact, it is $\Pi_2$-complete. You can prove that it is neither r.e. nor co-r.e. directly, by finding appropriate reductions from the halting problem.


Relationship between RAM size and 32-bit vs 64-bit word size

x86 is a 32-bit processor.  Memory addresses for x86 are 32 bits.  Each byte has a different address, so a 32-bit address means that you can only address up to $2^{32}$ bytes of memory.  $2^{32}$ bytes is 4GB.  That's why 32-bit processors are limited to 4GB of memory (per application).  In particular, each application can use only 4GB of memory.  (Technically, due to the way paging works, you can have more than 4GB of physical memory, but each application will still be limited to 4GB of physical memory.)

In contrast, a 64-bit processor can use 64-bit memory addresses, which allows addressing a huge amount of memory.  This has freed computers up to have more memory: they are no longer limited to 4GB of addressable memory.  (Technically, x86_64 has 48-bit addresses -- the high 16 bits of the 64-bit address basically can't be used -- but $2^{48}$ bytes of memory is still a humongous amount of memory, about 256 TB of memory.  That's more than anyone is likely to want to buy for now.)


Showing that the entropy of i.i.d. random variables is the sum of entropies

Your attempt at the proof does not take into account any natural order on $\Sigma^n$. While it may still work, it seems difficult.

A much easier proof can be given by induction over $n$. The base case is trivial ($H(X)=H(Y)$) for $X=Y$.
Then, denote $X=X_1\cdots X_n$ and $X'=X_1\cdots X_{n-1}$, so you have

$$H(X=w)=-\sum_{w\in\Sigma^{n-1}}\sum_{\sigma\in \Sigma}Pr(X=w\sigma)\log Pr(X=w\sigma)$$
$$=-\sum_{w\in\Sigma^{n-1}}\sum_{\sigma\in \Sigma}Pr(X'=w)Pr(Y=\sigma)\log Pr(X'=w)Pr(Y=\sigma)=$$
$$=-\sum_{w\in\Sigma^{n-1}}Pr(X'=w)\sum_{\sigma\in \Sigma}Pr(Y=\sigma)(\log Pr(X'=w)+\log Pr(Y=\sigma))=$$
$$=-\sum_{w\in\Sigma^{n-1}}Pr(X'=w)\left(\sum_{\sigma\in \Sigma}Pr(Y=\sigma)\log Pr(X'=w)+\sum_{\sigma\in \Sigma}Pr(Y=\sigma)\log Pr(Y=\sigma)\right)=$$
$$=-\sum_{w\in\Sigma^{n-1}}Pr(X'=w)\log Pr(X'=w)\sum_{\sigma\in \Sigma}Pr(Y=\sigma)+\sum_{w\in \Sigma^{n-1}}Pr(X'=w)\sum_{\sigma\in \Sigma}Pr(Y=\sigma)\log Pr(Y=\sigma)=$$
$$=H(X')+H(Y)=(n-1)H(Y)+H(Y)=nH(Y)$$


The deletion process has two phases, one for each condition.

Delete the specified node and all nodes that have a directed path to it.
Delete all nodes that have no incoming edges anymore and are no sources (iterate).

There are two imporant observations that make this correct:

During phase two, we create no new nodes with dangling outgoing edges, that is we do not break more dependencies that would cause nodes to be removed by condition 1.
Phase two is a fixed-point iteration.

How you would implement this depends on your graph representation. For example, if graphs have a node list, a list of sources and every node has lists of incident nodes via incoming (pred) and outgoing (succ) edges, respectively, you can do it like this:

  void removeFancy(g : Graph, n : Node) {
    rem = collectReverse(g,n)
    g.removeAll(rem)
    removeRedundant(g)
  }

  Node[] collectReverse(g : Graph, n : Node) {
    result = [n]
    foreach ( n' in n.pred ) {
      result ++= collectReverse(g,n')
    }
    return result
  }

  removeRedundant(g : Graph) {
    oldSize = 0
    while ( oldSize != g.size ) {
      oldSize = g.size
      for ( n in g.nodes ) {
        if ( n.pred.empty? && !g.sources.contains(n) ) {
          g.remove(n)
        }
      }
    }
  }

You can also do it in a more recursive fashion:

  void removeFancy(g : Graph, n : Node) {
    for ( n' in n.pred ) {
      removeFancy(g, n')
    }

    succ = n.succ.copy
    g.remove(n)

    for ( n' in succ ) {
      if ( n'.pred.size == 0 ) {
        removeFancy(g, n')
      }
    }
  }

Here it is more challenging to see correctness because the two phases are interleaved. The essential argument is that nodes deleted in the second loop never cause new dependency breaks, therefore all nodes that have to be deleted because of condition 2 are identified thus by recursion spanned by the calls in the first loop.

If you apply any of those to your second example, you will see that in addition C, F, A and G also D will be deleted, but no other nodes.


Transport Triggered CPU Architecture MOV and Turing Completeness

For a CPU designed to use a TTA (Transport Triggered Architecture), one way to implement conditional branch could use a couple of addresses for these purposes:

BRANCH_ADDRESS: stores the location to branch to
BRANCH_ZERO: Sets PC to BRANCH_ADDRESS when value written is 0. Otherwise does nothing.

This could be used to implement a 'branch-if-zero'. You could also add additional addresses that implement other branch modes, including those ithat hook into flags/state of other components hooked up to the TTA CPU, such as an ALU.


What are the purposes of Reply messages in Lamport Algorithm for Mutual Exclusion?

I believe the purpose is to fulfill the first condition of entering the critical section (site $S_i$ must receive a message from all other sites with timestamp greater than its own request) in case some other site never requests to enter the critical section.

If $S_i$ sends a critical section request to $S_j$, but $S_j$ never requests the critical section and doesn't send a reply, $S_i$ will never receive a message from $S_j$ thus causing it to wait forever to enter the critical section. In this scenario, $S_i$ cannot know for sure that $S_j$ does not have a pending request with a timestamp lower than $S_i$'s request.


An interesting metric space related to Turing machines

Edit: removed hints, posted my solution.

Here is my solution. We're going to pick a reference point $x$ where $f(x) \in L$ and consider the universe from $x$ and $f(x)$'s points of view. It turns out that every "neighborhood" of a point corresponds to a recursive language. So $L$ is a neighborhood around $f(x)$, and there will be some neighborhood around $x$ that maps to it; this neighborhood is a recursive language.

Lemma. In this space, a language is recursive if and only if it is a neighborhood of each of its strings.

Proof. First, fix a recursive language $L$ and let $x \in L$. Let $K$ be the minimal index of a decider for $L$. Then we have that if $y \not \in L$, $s(x,y) \leq K$, so $d(x,y) \geq 1/2^K$. Thus $d(x,y) < 1/2^K$ implies that $y \in L$.

Second, let $x$ be an arbitrary string and fix $\varepsilon > 0$; let $K = \lfloor \log(1/\varepsilon) \rfloor$. Let $L_K = \{y : d(x,y) < \varepsilon\}$; then $L_K = \{y : s(x,y) > K\}$. Then we can write

$$L_K = \{ y : (\forall j=1,\dots,K) |L(T_j) \cap \{x,y\}| \neq 1\}.$$

But $L_K$ is decidable: On input $y$, one may simulate the first $K$ deciders on $x$ and $y$ and accept if and only if each either accepted both or rejected both. $~\square$

Now we're almost done:

Prop. Let $f$ be continuous. If $L$ is recursive, then $f^{-1}(L)$ is recursive.

Proof. Under a continuous function, the preimage of a neighborhood is a neighborhood.

Interestingly, I think that in this space a continuous function is uniformly continuous:  Let $f$ be continuous, so for each point $x$, for each $\varepsilon$ there exists a corresponding $\delta$. Fix an $\varepsilon$ and let $K = \lfloor \log(1/\varepsilon) \rfloor$. There are a finite number of balls of size $\varepsilon$: there is $L(T_1) \cup L(T_2) \dots \cup L(T_K)$; then there is $\overline{L(T_1)} \cup L(T_2) \dots \cup L(T_K)$; then $L(T_1) \cup \overline{L(T_2)} \dots \cup L(T_K)$, and so on. $f$ associates to each of these languages $L_i$ a preimage language $L_i^{\prime}$ with associated diameter $\delta_i$. For each $x \in L_i^{\prime}$, $d(x,y) \leq \delta_i \implies d(f(x),f(y)) \leq \varepsilon$. So we can take the minimum over these finitely many $\delta$s to get the uniform continuity constant $\delta$ associated with this $\varepsilon$.


How can I efficiently find the largest positive interval in an unsorted array?

Hint, scan the array from left to right, keeping track of the smallest number so far and using that number to compute the largest interval whose right endpoint is the number just scanned.

Here is the Python code for the simple linear algorithm hinted. Hit the "run" button to see a couple of test result.


Calculate boolean matrix multiplication (BMM) using transitive closure

Let us build the tripartite graph $G = (S := U\dot\cup V \dot\cup W, E)$, where $U := \{u_1, \dots u_n\}$ and similarly $V := \{v_1, \dots v_n\}$ and $W := \{w_1, \dots w_n\}$. Define $E$ as follows:
For $i, j \in [n]$, we add $(u_i, v_j)$ to $E$ for $u_i \in U$ and $v_j \in V$, if and only if $X_{ij} = 1$. Similarly we add $(v_i, w_j)$ to $E$ for $v_i \in V$ and $w_j \in W$ if and only if $Y_{ij} = 1$.

Let $G^T := (S, E')$ be the transitive closure of $G$. This means $(x, y) \in E'$ if and only if there is a path from $x$ to $y$ in $G$.

Claim. Let $Z := X \cdot Y$ be the matrix resulting from the multiplication. We claim that $Z_{ij} = 1$ if and only if $(u_i, w_j) \in E'$.

Proof. $Z_{ij} = 1$ if and only if $\bigvee\limits_{k=1}^nX_{ik}\land Y_{kj}$ if and only if there is a $k\in [n]$ such that $X_{ik} = 1$ and $Y_{kj} = 1$ which is the case if and only if there is a $k\in [n]$ such that $(u_i, v_k) \in E$ and $(v_k, w_j) \in E$ which is the case if and only if$^{(*)}$ there is a path in $G$ from $u_i$ to $w_j$ and hence $(u_i, w_j) \in E'$.

Try to prove $(*)$ as an exercise. Hint: for the harder direction use the fact that the graph is directed.


You cannot say that every total function is computable, since that is not true. For example, the function $f(n)$ which returns $1$ if the $n$'th Turing machine halts and $0$ otherwise is not computable.

However, the question is much simpler. The definition of a PRC class specifies several closure properties, of the form: if so-and-so belong to the class, then such-and-such also belongs to the class (these include the "axioms", in which the premise is empty). Since the class of all (total) functions contains all functions, it automatically satisfies these constraints.


Can properties such as memory usage of a function be expressed in a dependently typed language?

Yes, it can.  While conceptually it's not that difficult, it hasn't been studied all that much.  One aspect of the field is cost semantics such as the research done by Guy Blelloch.

In the vein of the video Anton mentioned is Daniellson's work in Lightweight Semiformal Time Complexity Analysis for Purely Functional Data Structures.  This does indeed use a monad to carry around a cost per operation.  A similar monad, at the semantic level, is used in Denotational cost semantics for functional languages with inductive types.  Here's a 2016 paper doing something similar in Coq, A Coq Library For Internal Verification of Running-Times.

The NuPRL people have also long been interested in doing things like this.  In Expressing Computational Complexity in Contstructive Type Theory, which basically amounts to calculating over a structured operational semantics.  Where it gets a bit more interesting is that you can reflect the language semantics into the language.  The example in the final section, section 12, of Naive Computational Type Theory illustrates and discusses this sort of thing.


When problem A reduces to problem B, which problem is more complex?

When we reduce $A$ to $B$, we are saying "If I could solve $B$ in some model of computation, then I could solve $A$ in that model, too" (as long as the reduction is sufficiently simple that it can be performed within the relevant model of computation).

This means that $B$ is at least as hard as $A$. But $A$ could be easier – much easier. For example, let $A\in$ P and let  $B$ be any EXP-complete problem. Because $B$ is EXP-complete, every problem in EXP reduces to $B$ so, in particular, $A$ reduces to $B$. But we know that $A$ is strictly easier than $B$ by the time hierarchy theorem.


Prove if $L = \{0^m1^n \mid m \neq n\}$ is regular or not

You don't need to invoke the PL directly here. Instead, we'll do a proof by contradiction. Suppose $L$ was regular, then, since regular languages are closed under complement, $\overline{L}$ is regular (where the overbar represents complement), and since regular languages are closed under intersection, $\overline{L}\cap 0^*1^*$ would be regular (where the regular expression denotes the language $0^*1^*=\{0^n1^m\mid n,m\ge 0\}$), but $\overline{L}\cap0^*1^*=\{0^n1^n\mid n\ge 0\}$, which you likely know is not regular, establishing the contradiction we needed. Thus your language isn't regular.

In answer to your other question, the PL generally applies only to infinite languages since you don't know what the PL integer $p$ is, so absent other information, you need an infinite language to be sure that there is some string of length $\ge p$ in the language, regardless of how large $p$ is.


Why divide by $b-1$ when computing size of a tree

There are $b^i$ nodes at depth $i$, and so the total number of nodes is
$$
1 + b + b^2 + \cdots + b^d = \frac{b^{d+1}-1}{b-1},
$$
using the formula for the sum of a geometric progression.


Existence of boolean function with exponential average case hardness

Let $C$ be a fixed function, and let $f$ be a random function. For $z \in \{0,1\}^n$, let $X_z = 1$ if $C(z) = f(z)$, and $X_z = -1$ otherwise. Thus
$$
2^{-n} \sum_z X_z = \Pr[C(z) = f(z)] - \Pr[C(z) \neq f(z)] = 2\Pr[C(z) = f(z)] - 1.
$$
Therefore $\Pr[C(z) = f(z)] \geq 1/2+\delta$ iff $2^{-n} \sum_z X_z \geq 2\delta$. According to Bernstein's inequality,
$$
\Pr\left[2^{-n} \sum_z X_z \geq 2\delta\right] \leq \exp \left(-\frac{42^n\delta^2}{2(1+2\delta/3)}\right) \leq e^{-2^n\delta^2}.
$$
(The true exponent is more like $-2^{n+1}\delta^2$.)
The number of (de Morgan) circuits of size $s$ is at most roughly $e^{2s\log s}$ (according to notes of Trevisan; the bound is not tight). According to the union bound, the probability (over $f$) that some circuit $C$ of size $s$ satisfies $\Pr[C(z) = f(z)] \geq 1/2+\delta$ is at most $e^{2s\log s} \cdot e^{-2^n\delta^2}$. If $2s\log s < 2^n\delta^2$ then this probability is less than $1$, and so there exists some function $f$ such that $\Pr[C(z) = f(z)] < 1/2+\delta$ for all circuits of size $s$.
You're interested in the setting $\delta = 1/s$. The argument works as long as $2s^3\log s < 2^n$, and in particular, when $s\approx2^{n/3}$.


As @vonbrand suggested, using one automata (without attempting to combine them) is sufficient. Combining them will prove to be more work than it's worth.

Basically, here's the idea:

If you get an $a$, begin looping on $a^nb$. If you get a $b$ after this, accept. But anything further goes to the trash can.
If you get a $b$, accept for $a^0b$. If you get another $b$, you can then loop on $b$ under $b^na$. At any point in the loop, if you get an $a$, accept. But if you get anything after that $a$, go to the trash can.

Here is a textual representation (t is the "trash can" or trap state; + represents an accept state).

  | 0   | 1   | 2+  | 3+  | 4+  | 5
a | 1   | 1   | 4   | t   | t   | 4
b | 2   | 3   | 5   | t   | t   | 5

And here is a generated visual version:

(I'm not 100% sure this is minimal, but if it's not, it's a good exercise.)


How are prime implicates of HORN-Formulas defined?

This equivalence is a somewhat folklore idea in papers about prime implicants. A small proof is presented in the "Definitions" section of this paper.
The idea behind the equivalence is that, if $C$ is not a prime implicant for $\varphi$, then there is a proper subset $C'$ of $C$ (identifying clauses with the set of literals they force) such that $C'$ is an implicant of $\varphi$. But if this is the case, then you can fill $C'$ with the literals in $C \setminus C'$ until it has size $|C| - 1$, and thus, you obtain an implicant that is $C$ minus exactly one literal you "dropped". The other direction of the equivalence is trivial: if no proper subset of $C$ is an implicant, then dropping any literal of $C$ gives you something that is not an implicant.
I don't see the relation with Horn formulas, as the equivalence is about definitions for prime implicants of any formula.


Why do P-class problems not require a witness like NP?

If we look at decision problems, then a problem is in P if for "YES" instances "I think the answer is YES" is a witness that can be checked in polynomial time :-)


Making a NFA for accepting a string only if it contains the given substrings

Given an alphabet $\Sigma = \{\sigma_1,\ldots,\sigma_n\}$, let us consider the problem of matching all strings which contain all of the letters as substrings, i.e. all the strings $\sigma_1,\ldots,\sigma_n$ as substrings. An NFA with $N$ states accepting this language can be converted to a context-free grammar in Chomsky normal form of size $O(nN)$ (this is the total size of all rules). It is known that any context-free grammar in Chomsky normal form for this language must have exponential size $\tilde{\Omega}((3/2^{2/3})^n)$ (see Theorem 9 here; we gain a quadratic factor since our grammar is in CNF), and so $N = \tilde{\Omega}((3/2^{2/3})^n)$.

Note that this is only an exponential lower bound, whereas the obvious construction has factorial complexity. However, you can improve on this construction. Given $n$ words, the idea is to guess which $n/2$ words will appear first and which $n/2$ words will appear last, and to recurse on each half. We obtain the recurrence
$$ T(n) = \binom{n}{n/2}\cdot 2T(n/2) \leq 2^n T(n/2). $$
Expanding the recurrence and using a trivial base case $T(1) = 1$, we get
$$
T(n) \leq 2^{n+n/2+\cdots} < 4^n,
$$
which is only exponential. In actuality, $T(1)$ is the size of the largest word to be matched, so the bound above should be multiplied by that.


Algorithm for printing all accepted strings (to an upper bound if infinite amount) from a given DFA

The simplest one is to generate all strings up to length n and test them against the DFA.

The next option is a Breadth first traversal over the DFA (emitting the string each time you encounter a final state) however this can need a lot of memory. In the worst case all you need to keep all of length n in memory.

Next is a depth first traversal up to length n. Keep a counter of how long the string would be and backtrack when you exceed n.

To instead get the first n strings you run one of the above algorithms with a certain length and if it generates not enough strings you increment n until it does.


Understanding Return Oriented Programming on Harvard Architecture

I believe the architecture you're interested in - the AVR - is actually a modified Harvard architecture, whereby instruction memory can be accessed by instructions as if it were data.  (I haven't used the AVR in a while, so I don't recall if you can execute instructions out of RAM.)

The ARM Cortex M processors (perhaps others) are similar.  There aren't too many pure Harvard architectures in new designs these days.

By the way (since you tagged your question with "atmega"), there is a good paper by Francillon and Castelluccia (PDF from ACM Proceedings) regarding code injection attacks on (modified) Harvard architecture devices, including the AVR.


DFA - Accept all strings that does not contain a certain substring

This is the inverted DFA of Image 2 which should accept all string combinations of the language{a,b,c} that do not contain the substring "abc"
Final Automaton


How does maths consistency impacts on computer science?

Absolutely nothing will happen. Computers will still work, experts in machine learning will continue perfecting their tools, and even theoretical computer scientists will go on happily proving their theorems. Most mathematicians will also not feel much difference.

While we are trained to think that we are carrying out our proofs in ZFC, in practice proofs in mathematics and computer science are almost always carried out in English. Even if a contradiction is discovered in set theory, it is extremely likely that the axioms can be amended in such a way that the contradiction disappears and no proofs are affected apart from those in very specialized fields of a foundational nature.

More controversially, one can argue that most mathematicians argue in a nebulous system which actually does not rely on ZFC at all. Indeed, the average mathematician and nearly all computer scientists have little recourse to ZFC during their research life. Making this claim less nebulous, one can (and people do) argue that virtually all proofs in non-foundational fields can be carried out in weak subsystems of ZFC that are in less danger of being shown to be inconsistent. A nice reading in this general direction is McLarty's What does it take to prove Fermat's last theorem.


Proof of NP Completeness of set-partition problem

No, your can't arbitrarily choose $t$ so your proof is incorrect.

In fact, you have build a reduction from the following variant of subset sum problem to partition problem:

  Given a set $S$ of integers whose sum is $s$, is there a subset of $S$ whose sum is $s/2$?

This variant is different from the normal subset problem, and you cannot assert it is NP-complete (though it in fact is), so your proof is incorrect.

You can find a complete proof here.


Do Turing machines assume something infinite at some point?

A Turing machine does not have the ability "to compare numbers of arbitrary size through the <= comparator" because a Turing machine does not have a "<= comparator". A Turing machine has a fixed, finite set $Q$ of states and a fixed, finite tape alphabet $\Sigma$. At each step of the computation, the Turing machine looks at its current state and the symbol under its read/write head and decides what to do next: which state to enter, which symbol to write to the tape and which way to move the tape head.

Because of this, a Turing machine cannot compare arbitrarily large numbers in a single <= instruction. Using the state, it can remember at most $|Q|$ different numbers and, using the alphabet, it can write at most $|\Sigma|$ different numbers in a single tape cell (using each possible symbol to represent one number).  As such, to compare arbitrarily large numbers on a Turing machine, you must write each number as a sequence of digits on the tape and write an algorithm that will take multiple steps to compare those two numbers.  As you can imagine, this makes writing Turing machine programs a rather fiddly endeavour.

Turing machines don't really "deal with infinity": they deal with unbounded finite things, at least in their standard definition.  The input is a finite string and, after any finite number of steps, the machine has only examined or written to a finite number of tape cells. There is no bound on the size of the input or the number of computation steps but, the input is finite and, after any finite number of steps, only a finite amount of output has been produced.


Is this set semi-decidable? A set of all  that M is a TM halts on all input strings w such that w <= q(M) where q(M) is the number of states in M

To show that $\overline{A}\notin RE$ you want to show that another language $B\notin RE$ is reducible to it.

First, the complement of $A$ is the set of all $\left< M \right>$, where $M$ is a Turing machine, and $\exists w$, $|w|<q(M)$ s.t. $M$ doesn't halt on $w$.

Remember that you can add unreachable states to a Turing machine, therefore increasing $q(M)$. The next step would be picking a language who is known to be not decidable (e.g. the complementary of the halting language $\overline{H}$), and think of a reduction to $\overline{A}$.


What is the formal statement of the dining philosopher's problem?

In most models of concurrency, each participant performs one elementary action at a time. This applies both to philosophers and to forks. So if two philosophers try to grab the same fork around the same time, one of them will make the attempt first.

Concurrency models usually do not have a global time, so there is no concept of actions happening “at the same time” if they don't involve the same object. Each participants sees events according to its own notion of time. If an action happens which doesn't involve a particular participant, that participant only learns about it later when it receives some message informing it that the action has taken place.

Think of the participants as nodes in a network (which they often are). If two actions happen on different nodes, it doesn't matter whether they're “exactly” simultaneous. And physically speaking, they wouldn't be exactly simultaneous: without perfectly synchronized clocks, there's always some slight measurement error or reaction delay that means that you can't distinguish perfectly simultaneous actions from actions that happened within an extremely small time frame.

Each philospher decides to pick up and set down forks at their own pace. One philosopher may pick up a fork, eat and set it down before his neighbor has lifted a finger. Or they may race for the same fork, but only one of them will manage to grab it. Meanwhile the other philosophers are doing whatever they please.

Having one timeline per participant, rather than a global timeline, both simplifies the model and makes it closer to the reality of most concurrent systems. The model is simpler because there's never any reason to treat actions as simultaneous, and never any reason to care about the exact order of actions happening in different places. It's closer to the reality of concurrent processes and distributed systems because each thread or each network node does have its own perception of when actions take place.

An exception is the modeling of circuits where all actions happen on a clock cycle. This is one of the fundamental ways in which parallelism differs from concurrency. In a circuit, it often does make a difference that two actions happen at different parts of the system on the same clock cycle (e.g. two inputs change simultaneously), rather than on distinct clock cycles.


Improving copy cost of a bit array by using big-endian Patricia Trees (or similar)

Yes, you can use standard techniques for persistent data structures to make a version of Patricia trees that has the properties you want.  See also What classes of data structures can be made persistent? and persistent-data-structure on this site.


There is no such way.

This paper shows

  that any comparison-based randomized algorithm for finding the

  median requires $\Omega(n \log \log_{\hspace{.02 in}S} n)$ expected time in the RAM model

  (or more generally in the comparison branching program model),

  if we have S bits of extra space besides the read-only input array.

  This bound is tight for all $S\gg \log n$, and remains

  true even if the array is given in a random order.

$n^{1/\left((\hspace{.02 in}\log(n))^{\hspace{.02 in}\Omega(1)\hspace{-0.03 in}}\right)} \; = \; 2^{\left((\hspace{.02 in}\log(n))^{1-\Omega(1)}\hspace{-0.04 in}\right)}$
and
$\operatorname{polylog}(n) = 2^{\log(\hspace{.02 in}\operatorname{polylog}(n))} = 2^{O(\hspace{.02 in}\log(\hspace{.02 in}\log(n)))} \subseteq 2^{\left((\hspace{.02 in}\log(n))^{\hspace{.02 in}o(1)}\hspace{-0.03 in}\right)} \subseteq 2^{\left((\hspace{.02 in}\log(n))^{1/2}\hspace{-0.03 in}\right)}$

so since

$2^{\left((\log(n))^{1-\Omega(1)}\hspace{-0.04 in}\right)} \: \cdot \: \operatorname{polylog}(n) \;\;\; \subseteq \;\;\; 2^{\left((\log(n))^{1-\Omega(1)}\hspace{-0.04 in}\right)} \: \cdot \: 2^{\left((\hspace{.02 in}\log(n))^{1/2}\hspace{-0.03 in}\right)}$

$= \;\;\; 2^{\left((\hspace{.02 in}\log(n))^{1-\Omega(1)}+\hspace{.02 in}(\hspace{.02 in}\log(n))^{1/2}\hspace{-0.03 in}\right)} \;\;\; = \;\;\; 2^{\left((\log(n))^{1-\Omega(1)}\hspace{-0.04 in}\right)}$

and

$\Omega \hspace{-0.04 in}\left(n\log \log_{2^{\left((\log(n))^{1-\Omega(1)}\hspace{-0.04 in}\right)}} n\right) \;\;\; = \;\;\; \Omega \hspace{-0.04 in}\left(n\cdot \left(\log(\hspace{.02 in}\log(n))-\log \left(\log \left(2^{\left((\log(n))^{1-\Omega(1)}\hspace{-0.04 in}\right)}\right)\right)\right)\right)$

$= \;\;\; \Omega(n\cdot ((1\cdot \log(\hspace{.02 in}\log(n)))-((1-\Omega(1)) \cdot \log(\hspace{.02 in}\log(n)))))$

$= \;\;\; \Omega(n\cdot (1-(1-\Omega(1))) \cdot \log(\hspace{.02 in}\log(n))) \;\;\; =$

$\Omega(n\cdot \Omega(1) \cdot \log(\hspace{.02 in}\log(n))) \;\;\; = \;\;\; \Omega(n \log \log n)$

and

pointers can be represented with  O(log(n))  bits

,
even when one measures with polylog(n)-bit machine words and assumes that

input-elements fit into such words, comparison-based selection algorithms

that use at most    $2^{\left((\hspace{.02 in}\log(n))^{1-\Omega(1)}\hspace{-0.04 in}\right)}$  $\Big($equivalently,  $n^{1/\left((\hspace{.02 in}\log(n))^{\hspace{.02 in}\Omega(1)\hspace{-0.03 in}}\right)}\Big)$    space

require  $\Omega(n \log \log n)$  comparisons on average,

even if the array is given in a random order.


What is the reason for writing parallel programs?

Because the technology to extract paralellism automatically from sequential programs is still woeful... yes, some compilers/languages do take a stab at the problem, but for really demanding applications it still pays off to do the job manually.


How to correctly describe this action, deleting an edge that "shortcut" some vertices

Your operation replaces your graph with one of its directed spanning trees. See for example lectuire notes of Uri Zwick.


Computer security (especially, military-oriented branches of it) has the concept of red/black separation, with accepted definitions of what is red and what is black.


Is w ∈ L(M ) ⟹ ww ∈ L(M) co-semi-decidable?

You can show that this language $L$ is not co-RE in the following way:

Assume $L$ was co-RE, that is you have a semi-algorithm $A$ to decide given an input machine $M$ whether there exists a word $w\in L(M)$ such that $ww\notin L(M)$.

We show that we can build a semi-algorithm to decide the complement of the halting problem (on empty input), which is impossible.

The algorithm goes like this, on input $M$:

Build a machine $M'$ that

simulates $M(\varepsilon)$ on input $00$ and accepts if $M$ halts,
accepts on input $0$,
and accepts on all other inputs.

Run algorithm $A$ on $M'$.

Now $A(M')$ will answer yes iff $M'$ accepts $0$ but rejects $00$, meaning iff $M$ does not halt on empty input. Hence we have constructed an algorithm that semi-decides the complement of the Halting problem, which is a contradiction (it is not possible).


Your algorithm does not yield the solution. An extension of your algorithm that follows will provide a solution.
You need to mark the extremes of consecutive 1's in the flag array (an obvious observation ). For example, the flag array is 1111101111 then you need to mark 0,5,9 indices (zero based) and for every pair of extremes you need to find the difference computed in prefix sum array. The number of marker indices are of the order of n. So number of pairs are of the order n^2.


In a gist LZW is about frequency of repetitions and Huffman is about frequency of single byte occurrence.

Take the string 123123123.

(The following is an oversimplification but will make the point) LZW will identify that 123 is repeated three times and essentially create a dictionary of codes for sequences. It will esentially say when I say A I mean 123 here is AAA (or three bytes).

Huffman will detect the frequency of bytes (let's assume the text above is ASCII or UTF-8 (which will make ABC all single byte code points), so A=3, B=3, C=3 and there are no other items, so I can use 1.5 bits (well a 1 and 2 bit combo) to represent all characters. So let's say A=0, B=10, C=11. Huffman will encode the text ABCABCABC as (in bits) 010110101101011 (or 15 bits) or since we are usually limited to bytes 2 bytes.

What if we used Huffman on the LZW result?

Well AAA can be represented with a single bit (Let's choose 0) so 000 (3 bits or 1 byte rounding up).

The unfortunate part here is that Huffman and LZW require some info to decode so it won't quite be as awesome as sending a 0 and saying go decode with Huffman, then LZW, but in essence this combination results in very good compression results with real-world payloads that aren't already compressed (A JPG or ZIP file is unlikely to be compressible with this, but a .docx, xml doc, txt file, etc (the longer and more verbose and repetitive the better) will do. awesome!

If you look at the characteristics of the algorithms and have awareness of the data you will see that order of algorithms and repetition may well make a difference. Think of a doc 1TB in size of all "A"s and apply the above and think what would do better. Frankly a naive SingleByteUsageEncoder would do best as the minimal info here is what char how many times. Huffman would max out at approximately 1/8 (1 byte to one bit) LZW would do muuuuuuuch better. However if you had a doc with ever possible permutation of a sequence of letters then generally Huffman would do better. I think if you think carefully about this you will recognize that LZW is generally more helpful, but combos often achieve best results (assuming your goal is smallest size, not best performance).


Are there any paradigms that describe how to save program state checkpoints that can be restored later?

In general you cannot do this. The state of your application might depend on the state of external systems, and you won't be able to go back. For example you can't go back to a previous saved value of time if your systems requires that your clock should be within a small value compared to other machines in the network.

So its not always possible, and when it is, it is definitely application specific.


Proving that EXP doesn't have polynomial-size circuits

You can consider a circuit as a directed graph where nodes are inputs and gates. For a circuit of size $n^k$ on input of size $n$, there are at most $(n+n^k)^2$ edges, and each node (gate) has three possibilities, so the number of such circuits is at most

$$3^{n^k}\cdot2^{\left(n+n^k\right)^2}=O\left(2^{n^{2k+2}}\right).$$

So you need only to enumerate at most $O\left(2^{n^{2k+2}}\right)$ functions. In addition, checking whether a circuit of size $n^k$ calculates a function costs $O(n^{2k}2^n)$ time since computing on each input costs $O(n^{2k})$ time (here we compute the running time under a RAM rather than a TM without loss of generality) and there are $2^n$ inputs. Note for each function, you need to go through all circuits, and for each circuit, you need to check whether it calculates the function, so the total running time of the RAM on input of size $n$ is

$$ O\left(2^{n^{2k+2}}\right)\cdot O\left(2^{n^{2k+2}}\right)\cdot O(n^{2k}2^n)=O\left(2^{n^{2k+4}}\right). $$

So the language decided by this RAM is in $\mathrm{EXP}$ (note $k$ is a fixed constant). Obviously no family of circuits of size $n^k$ decides this language by the construction of the RAM.


How to prove that 3-coloring is decidable?

It depends entirely on what level of formality you're aiming for. The informal description of an algorithm in your question is quite enough to convince me that 3-colourability is decidable. If you wanted to be a bit more formal, you could give pseudocode. If you wanted to be more formal still, you could describe a Turing machine in English. If you wanted to be even more formal, you could write down the full description of the Turing machine and prove that it really does decide 3-colourability.

Having said that, of the options I've listed, it's way more likely that there'd be an error in the description of the Turing machine or in its correctness proof! So it's not clear which proof would be the most believable.


Solving recurrence relation with square n

The thing to point out is that the $\sqrt{n}$ in the recurrence relation should be interpreted correctly - either you view $T$ as a function defined on $\mathbb{R}_{\geq 1}$, which is bounded near $1$, or you actually understand the $\sqrt{n}$ as the integral part, i.e. $[\sqrt{n}]$.

In the first case, you fix a small neighborhood of $1$ on which the function $T$ is bounded by a fixed constant, and the recurrence stops when $n$ falls into this neighborhood; in the second case, the recurrence simply stops at $n = 1$.

Here I give a solution using the first understanding:

Put $m = \log(n)$ and rewrite the relation as:

$$ S(m)=\begin{cases}\theta(1) & m = 0 \text{ (or better: $m \rightarrow 0$)};\\ S(m/2) + \theta(m) & m > 0, \end{cases} $$
where $S(m)$ is the function defined by $S(\log(n))=T(n)$.

This translates to the following: we have constants $r$, $c$, $d$, such that:

$S(m) \leq c$ for all $0 \leq m < r$;
$S(m) \leq S(m/2) + d \cdot m$ for all $m \geq r$.

It is then easily proved using induction that we actually have $$ S(m) \leq \max(2c/r, 2d) \cdot m $$ for all $m \geq r/2$. (First note that it is true for $m$ in the interval $[r/2, r)$, and then show that if it is true on the interval $[x/2, x)$, then it is also true on the interval $[x, 2x)$.)

So finally we get $T(n) = \theta(\log(n))$.


Understanding the "ordering of the four types of edges" in DFS

I have reviewed section 22.3, "Depth-first search" a couple of times.

"What does it mean by "the ordering of the four types in the classification scheme"? In particular, what does the "ordering" refer to?

While quoting the textbook, You have used 1, 2, 3 and 4 to label the four cases in the classification scheme. That is an ordering. All it means is that $1 \prec 2 \prec 3 \prec 4$. In other words, tree edges precede back edges, which precede forward edges, which precede cross edges.

What is supposed to prove?

Suppose we have done a depth-first search $S$ on an undirected graph $G$ that has produced the depth-first forest $G_\pi$ as describe in the textbook.
An edge $e=\{u,v\}=\{v,u\}$ can be represented by either the directed edge $(u,v)$ or the directed edge $(v,u)$. Note that $(u,v)\not=(v,u)$. Both $(u,v)$ and $(v,u)$ will be explored during $S$. There are two methods to classify $e$ with respect to $S$.

$e$ is classified as the earliest type of edge (according to that ordering) which either $(u,v)$ or $(v,u)$ can be classified as.
More specifically, if either $(u,v)$ or $(v,u)$ is classified as a tree edge, then $e$ is classified as a tree edge. Otherwise, $e$ is classified as a back edge. Note that at least one of $(u,v)$ and $(v,u)$ must be classified as either tree edge or back edge (theorem 22.10 of the book).

If $(u,v)$ is discovered earlier than $(v,u)$, then $e$ is the same type of edge as $(u,v)$. If $(v,u)$ is discovered earlier than $(u,v)$, then $e$ is the same type of edge as $(v,u)$.

That exercise asks readers to prove the above two classifying methods are equivalent. That is, $e$ is classified as type $X$ by the first method if and only if $e$ is classified as type $X$ by the second method, given any edge $e$ and any type $X$.
(Somewhat informally, an edge is a tree edge if it appears in the resulting tree; otherwise it is a back edge. This seems to be the simplest way to label edges in an undirected graph with respect to a DFS.)

Let us take a look at the example given in the question.
Here is the relevant part of running DFS-VISIT $(G,u)$.

$u.d = 1$
$x.\pi = u$
$x.d = 2$
$v.\pi = x $
$v.d = 3$
Now we discover edge $(v,u)$, which connects $v$ to $u$, which is an ancestor of $v$ since $v.\pi=x$ and $x.\pi = u$. That is, $(v,u)$ is a back edge. This is the first time edge $e$ is discovered. So $e$ is a back edge according to second classifying method.
$v.f = 4$
$x.f = 5$
Now we discover edge $(u,v)$, which connects $u$ to its descendant $v$. This edge $(u,v)$ is classified as a forward edge. Since $(v,u)$ is classified as a back edge, a type of edges that precedes a forward edge, $e$ is a back edge according to the first classifying method.
$u.f = 6$

We just saw that $e$ is classified as the same type of edge according to either classifying method. That exercise asks readers to prove that is not a coincidence.


One possible approach which does not require any hairy arguments is to come up with a "nicety" measure, find a range of offsets, and choose the best one. Usually rounding errors are accounted for by taking a $\pm 1$ (in your case $\pm 5$) modification from the starting point. In your case, you would calculate the nicety measure for both $5$ and $10$, and if your nicety measure is reasonable, choose $10$ over $5$.


Is this partitioning problem NP-complete?

This problem can be solved in polynomial time with dynamic programming. Let $A[i]$ be the maximum value you can achieve with the points $x_1, \dots, x_i$.

You can compute $A[i]$ by choosing the maximum of $A[k]$ + $f(x_{k+1}, x_{k+2}, \dots, x_i)$ from all $k < i$. Then $A[n]$ contains your answer.


Is implication(function) more fundamental than lets say conjunction(product) in type theory?

For Agda, I think, as stated in the other question, that the fact that function types (or rather Π-types) are built-in while pairs (or even Σ-types) aren't so much is a reasonable argument that they are more fundamental in Agda. That said, even there it's not completely clear cut. For example, Σ-types/pairs are introduced in Agda via inductive data type declarations which are largely unrelated to Π-types. On the other hand, you could Church-encode pairs in terms of Π-types but to actually push this all the way through you'd need universes (which Agda does have) so it's not Π-types alone that do it.

I find comparing "how fundamental" things are very ambiguous and usually not useful. Something being "more fundamental" means it's "closer" to some foundations (fundament). In the context of a specific foundational system, e.g. Agda, that can be reasonably clear, but in general things that are fundamental in one foundation may be derived in another. More generically, "fundamental" has connotations that can easily pull in opposite directions. On the one hand, if I can derive $X$ from $Y$ but not vice versa, it would seem $Y$ is "more fundamental" in some sense. On the other hand, "fundamental" has connotations of simplicity, minimality, and a kind of unavoidability. If given all of $X$, $Y$, and $Z$ I can derive $W$, but given just $W$ I could derive each of $X$, $Y$, and $Z$, is $W$ more fundamental or less fundamental than $X$? Maybe $W$ is just a complex composite of $X$, $Y$, and $Z$. Because $X$ is derivable from $W$, that means $X$ is a more omnipresent concept; $X$ can exist even if $W$ does not but not vice versa.

At any rate, let's move to some more technical goodness that talks about how pairs and functions relate without trying to rank them. Unsurprisingly, category theory provides a good vantage point for gaining insight on these types of questions, though it is important to compare what the category theory suggests to what the type theorists actually do because these don't always line up. It can be quite interesting on both sides to see what is needed to make them line up.

Arguably the simplest example is cartesian closed categories. A cartesian category is one that has finite products, this means (the existence of terminal objects and) $\text{Hom}(A,B)\times\text{Hom}(A,C)\cong\text{Hom}(A,B\times C)$ (natural in $A$, $B$, and $C$). This is a characterization of binary products. A cartesian closed category additionally has $\text{Hom}(A\times B,C)\cong\text{Hom}(A,C^B)$ characterizing exponents in terms of products. This is to say a (parameterized) adjunction $-\times B\dashv (-)^B$. Hagino's Categorical Programming Language (CPL) described in his thesis allows declaring the function type constructor just this way (see sections 3.3.2 and 3.3.3). The type theoretic view of this is the simply typed lambda calculus (STLC) with products. But the STLC is usually not presented with products, or at the very least they are optional. So how are function types described in STLC without products? Usually by the following two rules (or some variation on them):$$\cfrac{\Gamma, x\!:\!A\vdash M:B}{\Gamma\vdash(\lambda x\!:\!A.M) : A\to B}\to\!\!I\qquad\cfrac{\Gamma\vdash M : A\to B\qquad \Gamma\vdash N:A}{\Gamma\vdash (M\,N) : B}\to\!\!E$$ This characterizes function types without any reference to product types. This is typical in modern type theory; type constructions are characterized without referencing other type constructions so that you can build type theories a la carte. In tihs sense, product types and function types are somewhat orthogonal.

Why does the categorical approach need products? Roughly speaking, an arrow $t\in\text{Hom}(A,B)$ corresponds to a term $x\!:\!A\vdash t:B$. So the issue is simply that we need some way of talking about arrows with more than one input. Products are one way, but an alternative, more direct approach would be to use (cartesian) multicategories. However, a more common approach is to split the adjunction characterizing function types in terms of product types into two adjunctions. Instead of having $-\times B\dashv (-)^B$ as described earlier, we can split this into $\Sigma_B\dashv p^*\dashv \Pi_B$ where $p : [\Gamma,B]\to [\Gamma]$ and $p^* : \mathcal{E}_\Gamma\to\mathcal{E}_{\Gamma,B}$. Here $\mathcal{E}_\Gamma$ can be thought of as a category of terms in context $\Gamma$. The machinery to do this is indexed or mostly equivalently fibered categories. $p^*$ is called a weakening functor and it corresponds to adding an unused variable (of type $B$) to the context. Now we can consider indexed-/fibered-categories where only one or the other (or neither or both) of those adjunctions hold. A simpler but less general approach to this is to use polycategories as Hasegawa does in Decomposing typed lambda calculus into a couple of categorical programming languages. A polycategory, $\mathcal{C}[x:B]$, is a category, $\mathcal{C}$, that has a terminal object and to which an arrow $x : 1 \to B$ is freely added. We of course have an inclusion of $\mathcal{C}$ into $\mathcal{C}[x:B]$, and this inclusion takes the place of $p^*$. When this perspective is related back to type theory, we end up splitting the lambda calculus into the kappa calculus and the zeta calculus. The kappa calculus captures a first-order notion of multi-parameter functions. The zeta calculus captures the higher-order aspect of the lambda calculus, but the result is quite strange and awkward. Either way, these approaches place product types and function types on somewhat even ground.


Why do we have free variables in mu-calculus?

If you define the $\mu$-calculus to not allow free variables, you would have the problem that the components of a well-formed formula are not again well-formed formulas.

Consider a well-formed formula "$\mu Z . \varphi$", such that $Z$ occurs freely in $\varphi$ and $\varphi$ has no other free variables. If you were to exclude formulas with free variables from your definition, $\varphi$ would not be a well-formed formula.

This would make structural induction on formulas more complicated. For example the semantics of formulas (the set of states in which the formula holds) is usually defined inductively: You define the semantics of "$\mu Z . \varphi$" in terms of the semantics of $\varphi$. If your definition says $\varphi$ is not a well-formed formula, you would have to extended the induction to also cover these non-well-formed cases. If you have to consider these cases every time you do structural induction, you haven't really gained anything from excluding them in your definition.


Given a bitstring generate all bitstring with n flipped bits

Let your initial bit string be x.

For all numbers b with k bits set (i.e. where k bits are 1), output x xor b.

Finding all numbers with k bits set is described elsewhere, for example here


Is there a binary tree structure with fast access to recently accessed elements and worst $O \left( \log n \right )$ complexity?

The amortized cost of entering an element to splay tree is $O(\log n)$ so in the worst case $n$ operations would do $O(n\log n)$ steps. There is a conjecture about splay tree that says that it is as optimal as a binary search tree up to constant factor called Dynamic optimality conjecture.

Tango trees are online, self adjacent trees that achive $O(\log \log n)$ competitive ratio compared to offline optimal binary search tree which is the best known.


What is the reasoning behind magic constancs in hash code calculations found in programming practice?

XOR is not a good method, because then the hash of $(a,b)$ will be equal to the hash of $(b,a)$.  Also, the hash of $(a,a,c)$ will be equal to the hash of $(b,b,c)$ and to the hash of just $c$.  That's not good.

A better method is to make the hash of $(a,b)$ be equal to $H(H(a) || H(b))$, where $H$ is your hash function on basic objects (ints, strings, etc.) and where I am using $||$ to represent concatenation of bit strings.  This avoids all of those degeneracies.

The particular constructions you mention can be viewed as instances of that approach:

The first link basically proposes using $H(a) + 37 \times H(b) \bmod 2^{64}$.  That's equivalent to the construction $H'(H(a) || H(b))$ where $H'$ is a standard Rabin-Karp hash function.
The second link is $1013 \times H(a) \oplus 1009 \times H(b) \bmod 2^{64}$.  That has the form $H''(H(a) || H(b))$ where $H''(x||y) = c_1x \oplus c_2y$, which is also a reasonable hash function (though it takes a little bit of algebra to prove it).
The third link is $(c \times H(a)) \oplus H(b) \bmod 2^{64}$ where $c$ is a prime.  That's the same as the previous one, but with $c_2=1$.  It also turns out to be a reasonable hash function.

Does the constant multiplier (e.g., 37) need to be prime?  No, it only needs to be relatively prime to the modulus.  If the modulus is a power of two (as in these cases), it only needs to be odd.  A prime is sufficient but not necessary.  To obtain provably good results, the constant multiplier should be chosen at random; in practice, we fix a particular value and hope that will be close enough for practical purposes.

Another reasonable method is to use $H_1(a) + H_2(b)$ or $H_1(a) \oplus H_2(b)$ as the hash of $(a,b)$, where $H_1,H_2$ are two independently chosen hash functions.  This also works.. but is a little more annoying to implement, because it requires us to have multiple hash functions.

Is there some theory here?  Yes, you can prove that if $H_1,H_2$ are drawn uniformly at random from a 2-universal hash family, and $+$ is a group operator, then $H_1(a)+H_2(b)$ will be a 2-universal.  The same is true for $H_1(H_2(a)||H_2(b))$.  I am not sure about what one can prove about $H(H(a)||H(b))$; I suspect it's not provably good in a generic sense, but is normally fine in practice.


Claim: Red-black trees can be arbitrarily un-$\mu$-balanced.

Proof Idea: Fill the right subtree with as many nodes as possible and the left with as few nodes as possible for a given number $k$ of black nodes on every root-leaf path.

Proof: Define a sequence $T_k$ of red-black trees so that $T_k$ has $k$ black nodes on every path from the root to any (virtual) leaf. Define $T_k = B(L_k, R_k)$ with

$R_k$ the complete tree of height $2k - 1$ with the first, third, ... level colored red, the others black, and
$L_k$ the complete tree of height $k-1$ with all nodes colored black.

Clearly, all $T_k$ are red-black trees.

For example, these are $T_1$, $T_2$ and $T_3$, respectively:

[source]

[source]

[source]

Now let us verify the visual impression of the right side being huge compared to the left. I will not count virtual leaves; they do not impact the result.

The left subtree of $T_k$ is complete and always has height $k-1$ and therefore contains $2^k - 1$ nodes. The right subtree, on the other hand, is complete and has height $2k - 1$ and thusly contains $2^{2k}-1$ nodes. Now the $\mu$-balance value for the root is

$\qquad \displaystyle \frac{2^k}{2^k + 2^{2k}} = \frac{1}{1 + 2^k} \underset{k\to\infty}{\to} 0$

which proves that there is no $\mu > 0$ as requested.


Sorting Algorithm which prevents strings with at least one identical char from being next to each other

Think of this like a chess board.  Visit all of the white squares first (in a left-to-right, top-to-bottom scan).  Then visit all of the black squares (in a similar order).


The answer is no. Whilst the language is finite and therefore regular the grammar itself is not regular. I think you already knew this as you said that this grammar's production rules are not of the form of a regular grammar.

The point here is that just because a grammar isn't regular doesn't mean the language it generates must not be regular.


Yes, this can be solved with dynamic programming.  In fact, it can be done in linear time.

I'll assume there is a single source $s$ and a single sink $t$ (if not, add $s$ and edges with score 0 from $s$ to each original source; and similarly for $t$).

Then, let $f(v)$ denote the sum of the scores of all paths from $s$ to $v$, and $f'(v)$ denote the number of such paths.   You can compute both of them using dynamic programming.  For instance,

$$f(v) = \sum_u f(u) + s(u,v)$$

where the sum is over all vertices $u$ such that $(u,v)$ is an edge in the graph, and where $s(u,v)$ denotes the score on the edge $(u,v)$.  If you topologically sort the graph, then you can fill in the $f(v)$ values using the above recurrence in linear time.  Similarly,

$$f'(v) = \sum_u f'(v)$$

which gives a way to fill in the $f'(v)$ values in linear time as well.

Let $g(v)$ denote the sum of the scores of all paths from $v$ to $t$, and $g'(v)$ the number of such paths.  You can fill in these values similarly.

Finally, you can compute the marginal probability of an edge $(u,v)$ as

$$\Pr[(u,v)] = {f(u) g(v)  +  s(u,v) f'(u) g'(v) \over f(t)}.$$

The numerator has the total score of all paths that go through $(u,v)$, and the denominator has the total score of all paths in the graph.


I believe this is done to illustrate two things.

(i)
The small probability, that $P$eggy ($P$rover) might be lying. If she really does not know the magic word and $V$ictor ($V$erifier) sees her taking Path $A$, he would always ask her to come back via path $B$, thus the probability of $P$ succeeding when cheating is $0$.

However, $ZKP$s usually involve a small chance of $P$ succeeding while cheating, which is illustrated by $V$ not seeing the path $P$ takes to get to the magic door.

(ii) $V$ does not learn the secret. If $V$ stands at the crossroad of the paths $A$ and $B$, while $P$ walks to the magic door to say her magic word, it might be conceivable for $V$ to be able to hear $P$ saying her secret word. The only way to make sure that $V$ does not learn the magic word, is for him to wait outside of the cave, until $P$ has chosen a path.


How to prove that a language is not context-free?

To my knowledge the pumping lemma is by far the simplest and most-used technique. If you find it hard, try the regular version first, it's not that bad. There are some other means for languages that are far from context free. For example undecidable languages are trivially not context free.

That said, I am also interested in other techniques than the pumping lemma if there are any.

EDIT: Here is an example for the pumping lemma: suppose the language $L=\{ a^k \mid k ∈ P\}$ is context free ($P$ is the set of prime numbers). The pumping lemma has a lot of $∃/∀$ quantifiers, so I will make this a bit like a game:

The pumping lemma gives you a $p$
You give a word $s$ of the language of length at least $p$
The pumping lemma rewrites it like this: $s=uvxyz$ with some conditions ($|vxy|≤p$ and $|vy|≥1$)
You give an integer $n≥0$
If $uv^nxy^nz$ is not in $L$, you win, $L$ is not context free.

For this particular language for $s$ any $a^k$ (with $k≥p$ and $k$ is
a prime number) will do the trick. Then the pumping lemma gives you
$uvxyz$ with $|vy|≥1$. Do disprove the context-freeness, you need to
find $n$ such that $|uv^nxy^nz|$ is not a prime number.

$$|uv^nxy^nz|=|s|+(n-1)|vy|=k+(n-1)|vy|$$

And then $n=k+1$ will do: $k+k|vy|=k(1+|vy|)$ is not prime so $uv^nxy^nz\not\in L$. The pumping lemma can't be applied so $L$ is not context free.

A second example is the language $\{ww \mid w \in \{a,b\}^{\ast}\}$. We (of course) have to choose a string and show that there's no possible way it can be broken into those five parts and have every derived pumped string remain in the language.

The string $s=a^{p}b^{p}a^{p}b^{p}$ is a suitable choice for this proof. Now we just have to look at where $v$ and $y$ can be. The key parts are that $v$ or $y$ has to have something in it (perhaps both), and that both $v$ and $y$ (and $x$) are contained in a length $p$ substring - so they can't be too far apart.

This string has a number of possibilities for where $v$ and $y$ might be, but it turns out that several of the cases actually look pretty similar.

$vy \in a^{\ast}$ or $vy \in b^{\ast}$. So then they're both contained in one of the sections of continguous $a$s or $b$s. This is the relatively easy case to argue, as it kind of doesn't matter which they're in. Assume that $|vy| = k \leq p$.

If they're in the first section of $a$s, then when we pump, the first half of the new string is $a^{p+k}b^{p-k/2}$, and the second is $b^{k/2}a^{p}b^{p}$. Obviously this is not of the form $ww$.
The argument for any of the three other sections runs pretty much the same, it's just where the $k$ and $k/2$ ends up in the indices.

$vxy$ straddles two of the sections. In this case pumping down is your friend. Again there's several places where this can happen (3 to be exact), but I'll just do one illustrative one, and the rest should be easy to figure out from there.

Assume that $vxy$ straddles the border between the first $a$ section and the first $b$ section. Let $vy = a^{k_{1}}b^{k_{2}}$ (it doesn't matter precisely where the $a$s and $b$s are in $v$ and $y$, but we know that they're in order). Then when we pump down (i.e. the $i=0$ case), we get the new string $s'=a^{p-k_{1}}b^{p-k_{2}}a^{p}b^{p}$, but then if $s'$ could be split into $ww$, the midpoint must be somewhere in the second $a$ section, so the first half is $a^{p-k_{1}}b^{p-k_{2}}a^{(k_{1}+k_{2})/2}$, and the second half is $a^{p-(k_{1}+k_{2})/2}b^{p}$. Clearly these are not the same string, so we can't put $v$ and $y$ there.

The remaining cases should be fairly transparent from there - they're the same ideas, just putting $v$ and $y$ in the other 3 spots in the first instance, and 2 spots in the second instance. In all cases though, you can pump it in such a way that the ordering is clearly messed up when you split the string in half.


The minimum weight connected subgraph that includes all the blue vertices is known to be a tree, called a Steiner tree.  A depth-first search of the tree will give you a route that visits every blue vertex and whose length is twice the weight of the Steiner tree, since you walk along each edge of it exactly twice.  Hence, DFS of a Steiner tree is at most twice the length of the shortest route.

However, computing Steiner trees of general weighted graphs is NP-hard (the decision version was one of Karp's 21 problems). Sanjeev Arora has shown there's a polynomial time approximation scheme for the the Euclidean version of the problem, which is close to the case you're interested in: paper. The Euclidean version corresponds to your version where every possible edge is present (i.e., you have a collection of points in the Euclidean plane and there's an edge between every pair of points, with the weight of the edge equal to the distance).


Just put the value of $x=10$ then

$$10^3+1=1001$$


Multiple rounds of bipartite matching problem

You can solve this by a mild extension of the standard reduction to network flow: increase the weight of the edges touching the source and the sink to $r$. Any integer flow corresponds to a union of $r$ matchings:

An integer flow corresponds to a bipartite graph of maximum degree $r$.
We can complete this bipartite graph to an $r$-regular bipartite graph by adding vertices and edges:

Add vertices so that both sides have the same number of vertices.
If the graph is not $r$-regular, then there must be two vertices $x,y$ (one on each side) with degree less than $r$. Add $r$ new vertices $x_1,\ldots,x_r$ and $y_1,\ldots,y_r$ to each side (respectively), and connect all of them except $x_1$ and $y_1$. Connect $x$ to $y_1$ and $y$ to $x_1$. This reduces the overall deficiency of the graph $\sum_v (r - \deg(v))$ by 1.

Repeated applications of Hall's theorem shows that the new graph can be decomposed into $r$ perfect matchings.
Restricting these matchings to the original vertices and edges, we obtain a union of $r$ matchings.

Schrijver mentions this problem in his Combinatorial Optimization (Vol 1):

  Corollary 21.4b. Let $G = (V,E)$ be a bipartite graph and let $k \in \mathbb{Z}_+$. Then the maximum size of the union of $k$ matchings is equal to the minimum value of $k|V \setminus X| + |E(X)|$ taken over $X \subseteq V$.

This follows by an application of the min cut max flow theorem.