Proving that max flows of undirected graph and equivalent directed graph are equal

If $f_G$ is a valid flow for $G$, then there exists a valid flow $f_H$ for $H$ such that $|f_G| = |f_H|$.  This is true since there is always a flow $f'_G$ for $G$ such that $|f'_G| = |f_G|$ and no edge is traversed in both directions in a flow decomposition of $f'_G$. If some edge $(u,v)$ is traversed by $x$ units of flow from $u$ to $v$ and $y \le x$ units of flow from $v$ to $u$ then you could redefine the flow to only send $x-y$ units of flow from $u$ to $v$. If $(u,v)$ is used from $u$ to $v$ you can then define $f_H(u,v) = f'_G(u,v)$  and $f_H(v,u)=0$. (If $(u,v)$ is unused then $f_H(u,v) = f_H(v,u) = 0$).

If $f_H$ is a valid flow for $H$, then there exists a valid flow $f_G$ for $G$ such that $|f_H| = |f_G|$.
Notice that if $f_H$ uses both $(u,v)$ and $(v,u)$ (assume w.l.o.g., that $f_H(u,v) \ge f_H(v,u)$) then the flow $f'_H$ defined by $f'_H(u,v) = f_H(u,v) - f_H(v,u)$, $f'_H(v,u)=0$, and $f'_H(x,y) = f_H(x,y)$ for $(x,y) \not\in \{ (u,v), (v,u) \}$ is also a valid flow for $H$ and $|f'_H| = |f_H|$. This shows that you can define $f_G(u,v) = f'_H(u,v)$.


MAX-2-XOR-SAT: Why does the special case work?

No, you can't make a substitution like that.  The resulting formula isn't equivalent to the original formula.

Consider

$$(x_1 \oplus x_2) \land (x_1 \oplus \neg x_2).$$

This formula is not satisfiable.  However, if we apply your substitution, we end up with the formula

$$(x_1 \oplus x_2) \land (x_1 \oplus y_2).$$

The resulting formula now has 6 variables and is satisfiable.  For example, you can set $x_1=\text{True}$, $x_2=\text{False}$, $y_2=\text{False}$.

The problem is that your substitution doesn't ensure that $y_i = \neg x_i$, so it doesn't preserve satisfiability.  (If you wanted to preserve satisfiability, you could do that by making your substitution and then adding clauses of the form $(y_i \oplus x_i)$ ... but while that would preserve satisfiability, it wouldn't preserve the maximum number of clauses that can be simultaneously satisfied, so it still wouldn't help for solving MAX-2-XOR-SAT.)


Graph Coloring Problem : How to Think About Algorithms Exer 1.6.2

You're right that the statement is false. The correct statement states that every undirected simple graph in which each node has at most $d$ neighbors can be colored using $d+1$ colors so that each edge connects nodes having different color. Stated in more idiomatic language, every undirected simple graph of maximum degree $d$ can be (properly) colored using $d+1$ colors.


Converting a special case TM to a regular TM

You want to show that this modified Turing machine is equivalent to the standard definition of a Turing machine, that is for every modified Turing machine $T'$ there exists a standard Turing machine $T$ such that $L(T')=L(T)$, and vice versa.
It is easy to show that for every standard Turing machine $T$ there is a modified Turing machine which accepts $L(T)$, just don't use the modified machine's ability to read or write to the input to the right of its head. Then these modified Turing machines are at least as powerful as standard Turing machines.
Now if $T'$ is a modified Turing machine which can read and write to the character immediately to the right of its head, we want to show that there exists a Turing machine $T$ which recognizes the same language as $T'$. Formally this gets a bit messy but the idea is whenever $T'$ would read or write an input from the cell to its right we add a sequence of states and transitions in which $T$ will move back and forth between the cell it is currently over in $T'$ and the cell to its right in $T'$ reading and writing as $T'$ does, then $T$ will move to the position and state specified in the transition function of $T'$. Essentially, if $T'$ reads from the cell to its right, $T$ will move to the right, read the input then move to the left. If $T'$ will would to the cell to its right, $T$ will move to the right, write the same thing $T'$ would have written, then move back, and transition to the same state $T'$ would have transitioned to.


If you believe that a proof or disproof has reasonable length, you could come up with one SAT instance which states $x_1,\ldots,x_n$ encodes a proof of the Riemann Hypothesis, and another one stating $x_1,\ldots,x_n$ encodes a refutation of the Riemann hypothesis. The formula will have size polynomial in $n$, though probably not linear; if you're careful, maybe quasilinear ($n\log^{O(1)}n$). You can then apply your magic SAT solver to find out which, if any, of these options is correct. Don't hold your breath, though – as mentioned in the comments, it is hard to imagine an algorithm which would be efficient enough to handle the required value of $n$ in a realistic amount of time.


$NL = P$ means that every language in $P$ can be decided by a nondeterministic Turing machine using at most $O(\log n)$ space, where $n$ is the size  of the input.

Savitch's theorem states for all $f(n) \in \Omega(\log n)$: $NSPACE(f(n))\subseteq SPACE(f(n)^2)$.

Therefore $NL = P$ implies that every language in $P$ can be decided by a deterministic Turing machine using at most $O((\log n)^2)$ space.


The word $(1,\ldots,1)$ is in your code iff there exists a polynomial $p(x)$ such that $$ \frac{x^n-1}{x-1} = p(x) g(x). $$
Since the code is cyclic, $g(x)$ divides $x^n-1$, and so $(1,\ldots,1)$ is in your code iff there exists a polynomial $p(x)$ such that
$$ \frac{x^n-1}{g(x)} = p(x)(x-1). $$
In other words, $(1,\ldots,1)$ is in your code iff
$$
x-1 \mid \frac{x^n-1}{g(x)}.
$$
I'll let you complete the proof, using the fact that $x-1$ divides $x^n-1$ but not $\frac{x^n-1}{x-1}$.


Computing all paths from root to the leaf nodes in a tree

The problem is that each node is adding its children to the list of paths. Instead, you can modify your recursive function so that each node only adds itself.

That is, $paths(v)$ returns a list $L_v$ of all paths from $v$ to the leaves of the subtree rooted in $v$.

If $v$ is a leaf, then the list $L_v$ returned by $paths(v)$ contains a single path consisting of $v$ itself.

If $v$ is not a leaf and $u_1, \dots, u_k$ are its children, then $paths(v)$ returns the union of $k$ lists $L'_{u_1}, \dots, L'_{u_k}$, where $L'_{u_i}$ is obtained by prepending $v$ to every path in $L_{u_i}$.


First of all, the formula given for the distance between a point and a line is not a definition, it is a calculation. The distance between a point $p$ and a line $\ell$ is the minimum distance between $p$ and a point on $\ell$.

Similarly, if $\ell,\ell'$ are two lines then the distance between them is the minimum distance between a point on $\ell$ to a point on $\ell'$. This is zero unless the lines are parallel, and if they are, say given by $x \bullet w + b = 0$ and $x \bullet w' + b' = 0$, then the distance is (I believe) $|b/\|w\| - b'/\|w'\||$. Again, this is not a formula but rather a calculation.


What are common formal techniques for proving functional code correct?

You can start with

Software Foundations by Benjamin C. Pierce et al.

  Topics include basic concepts of logic, computer-assisted theorem proving, the Coq proof assistant, functional programming, operational semantics, Hoare logic, and static type systems. The exposition is intended for a broad range of readers, from advanced undergraduates to PhD students and researchers. No specific background in logic or programming languages is assumed, though a degree of mathematical maturity will be helpful.

You can skip (or skim) the programming language theory parts and only learn how to deal with formal proofs starting from Preface up to IndPrinciples. The book is really well-written and illuminating.

Then you might want to proceed with

Verified Functional Algorithms by Andrew W. Appel

  In this volume you will learn how to specify and verify (prove the correctness of) sorting algorithms, binary search trees, balanced binary search trees, and priority queues. Before using this book, you should have some understanding of these algorithms and data structures, available in any standard undergraduate algorithms textbook.
  You should understand all the material in Software Foundations Volume 1 (Logic Foundations)

A note of warning: VFA is still in beta-release!


Graph splitting via an algorithm and proof of properties

I'll give you the schema of the proof. You'll have to fill in the blanks on your own. The idea is to prove by induction the following property $P(n)$:

  On a graph $G$ having $n$ vertices, the function $\mathrm{split}(G)$ terminates and returns a partition $V_1,V_2$ of the vertex set of $V$ such that in the subgraphs of $G$ induced by $V_1$ and $V_2$, all vertices have even degree.

First you have to prove the base case $P(1)$. That's quite easy.

Now, for every $n$ you have to prove that $P(n)$ implies $P(n+1)$. To do this, you analyze what happens when $\mathrm{split}$ is run on a graph $G$ having $n+1$ vertices. There are two cases: if all degrees in $G$ are even then it is easy to see that $\mathrm{split}(G)$ terminates with an appropriate partition. Otherwise, $\mathrm{split}$ creates a graph $G'$ on $n$ vertices and runs itself on $G'$. Since $G'$ has $n$ vertices, the induction hypothesis implies that $\mathrm{split}(G')$ with a partition $V'_1,V'_2$ of the vertex set of $G'$ such that the subgraphs of $G'$ induced by $V'_1,V'_2$ have only even degrees. The procedure $\mathrm{split}$ uses $V'_1,V'_2$ to create a partition $V_1,V_2$ of the graph $G$. It thus clearly terminates. To finish the proof, you have to show that the subgraphs of $G$ induced by $V_1,V_2$ have all even degrees.

This is the structure of the proof. All you have to do now is to fill in the blanks.


Smallest possible DFA for a language over {0,1}* with third to last symbol 1 should have 4 states not 8. Where am I going wrong in my DFA?

Try inputting 1100 to your DFA. You get to $q_1$, a non-accepting state.

We can show that 8 states are needed using the Myhill–Nerode theorem. The following table gives words separating any two of $000,001,010,011,100,101,110,111$:
$$
\begin{array}{c|cccccccc}
& 000 & 001 & 010 & 011 & 100 & 101 & 110 & 111 \\\hline
000 & & 00 & 0 & 0 & \epsilon & \epsilon & \epsilon & \epsilon \\
001 & 00 & & 0 & 0 & \epsilon & \epsilon & \epsilon & \epsilon \\
010 & 0 & 0 & & 00 & \epsilon & \epsilon & \epsilon & \epsilon \\
011 & 0 & 0 & 00 & & \epsilon & \epsilon & \epsilon & \epsilon \\
100 & \epsilon & \epsilon & \epsilon & \epsilon & & 00 & 0 & 0 \\
101 & \epsilon & \epsilon & \epsilon & \epsilon & 00 & & 0 & 0 \\
110 & \epsilon & \epsilon & \epsilon & \epsilon & 0 & 0 & & 00 \\
111 & \epsilon & \epsilon & \epsilon & \epsilon & 0 & 0 & 00 &
\end{array}
$$


Running time of algorithm (effect of j*j in for loops) - Theta Runtime

1
For the first case, you had the right idea, but just had some algebra mistakes.
for i=1..n
    j=1
    while j*j <= i:
        j = j + 1

Let $T(n)$ be the time complexity.
$$T(n) = \sum_{i=1}^n\sum_{j=1}^\sqrt{i}1\leq  \sum_{i=1}^n\sqrt{n}=\leq n^{3/2}$$
$$= O(n^{3/2})$$
2
I'm assuming you meant the pseudocode below since it is more analogous to your first case (I believe the pseudocode you posted has the same complexity). You are correct though, it is $O(n\log n)$ for the reason you described.
for i=1..n
    j=2
    while j <= i
        j = j * j


What is the State of The Art of Writer AIs (Deep Learning)?

Researchers are trying it out, but RNNs learn character-by-character (sequences of characters), so it is difficult to get something that resembles a story plot, as a whole. This link by a Stanford researcher explains the current (2015) state of the art. Here is the code and here are some data sets for you to start experimenting with.

Another experiment involving the writing of a travel blog also concluded that you cannot really create a long passage that makes sense at the moment. The recommendation was to look at the word level, rather than character, and focus on something more manageable, such as sentence autocompletion.

When it comes to words, the more unique ones there are in the source data set (for example using the Game of Thrones books), the tougher it becomes to train a good model. Suggestions are to limit input to more basic words (think children's vocabulary) and to have at least a total training sample at least 100 times larger than the desired output.

A trained neural network could perhaps output smaller texts (<10000 words) that make some sense, if they are of a rather structured nature. A whole book needs both a coherent plot from start to finish, as well as twists in-between. As a result, it is still way too difficult.

This guy tried it out and discovered that the AI would get sometimes stuck in loops. Furthermore, the draft produced did not always make sense in terms of the storyline and required heavy human editing.

Here is another example of an LSTM RNN outputting a Harry Potter chapter, where the sentences are grammatically correct, but sometimes make no sense.

If you want to learn more about RNNs, the Deep Learning book by Goodfellow, Bengio, and Courville comes highly recommended and has a relevant chapter.

For something more specific to writing, The Bestseller Code book uses text mining techniques and should be an interesting read.


Every EXP-complete problem is not in P, by the time hierarchy theorem.  Many games are EXP-complete, you can look up some starting from here.

As a concrete example (albeit not a very simple one), you can consider the problem of emptiness of the intersection of deterministic tree automata. Formally, the input consists of $n$ DFTs $A_1,...,A_n$ (deterministic automata over trees), and the problem is to decide whether $L(A_1)\cap...\cap L(A_n)\neq \emptyset$.


Proving DPATH is NP-complete by a reduction from HAMPATH

Remember that given the HAMPATH instance, you are constructing the DPATH instance. As long as

it's a valid instance of DPATH,
it's a Yes-instance if and only if the HAMPATH instance is, and
it's computable in polynomial time,

you can do whatever you want. So in particular, you get to pick how long the sequence is, you can pick any $a_{i}$ to be $s$ or $t$ (though in this case you may want to think carefully how you ensure that these are the first and last vertices in the path - otherwise it might be hard to argue for the Hamiltonian path), you don't even have to have the graph $G$ in the HAMPATH instance be the graph $G'$ in the DPATH instance (I suggest that you look at something very close to it though).

In the spoiler below are some additional hints, but don't use them unless you're really stuck - you learn a lot less if you don't put in the effort and time.

   One thing you have to do is take the HAMPATH graph and make it directed. There is a very simple way to turn undirected graphs into directed graphs, and it can work here. Another is ensuring that $s$ is the start of the sequence and $t$ is the end. I suggest adding new vertices to be $a_{1}$ and $a_{n}$ such that you can only get out of $a_{1}$ and only get into $a_{n}$, but you still have to work out how to connect them into the graph - remember that you don't know whether $G$ has a Hamiltonian path, or where it is even if it does, so you have to take care of all possibilities.


Algorithm to test whether a language is regular

The answer is no. Deciding whether a given context-free grammar generates a regular language is an undecidable problem.

Update. I gave this negative answer to the general question

  Given a language specified in algebraic form, test whether the
  language is regular or not

since context-free languages are solutions of algebraic equations in languages: see Chapter II, Theorems 1.4 and 1.5 in the book of J. Berstel Transductions and Context-Free Languages.

However, the same question is decidable for deterministic context-free languages, a nontrivial result due to Stearns [1] and improved by Valiant [2]:
[1] R. E. Stearns, A Regularity Test for Pushdown Machines, Information and Control  11 323-340 (1967). DOI:10.1016/S0019-9958(67)90591-8.
[2] L. G. Valiant. Regularity and related problems for deterministic pushdown automata J. ACM 22 (1975), pp. 1–10.

There is another positive result, closer to the specifications given in the second part of the question. Recall that the semilinear subsets of $\mathbb{N}^k$ are exactly the sets definable in Presburger arithmetic. There are also the rational subsets of $\mathbb{N}^k$. In particular, a subset of $\mathbb{N}^k$ defined by linear inequations is rational. Now, given a rational subset $R$ of $\mathbb{N}^k$, it is decidable whether the language
$$
  L(R) = \{ u_1^{n_1} \dotsm  u_k^{n_k} \mid (n_1, ...,n_k) \in R \}
$$
is regular. Indeed, it is known [Ginsburg-Spanier] that $L(R)$ is regular if and only if $R$ is a recognizable subset of $\mathbb{N}^k$ and it is decidable [Ginsburg-Spanier] whether a given rational subset of $\mathbb{N}^k$ is recognizable.

S. Ginsburg and E. H. Spanier., Semigroups, Presburger formulas, and languages,  Pacific J. Math. 16 (1966), 285-296.

S. Ginsburg and E. H. Spanier. Bounded regular sets, Proc. of the American Math. Soc. 17, 1043–1049 (1966).

This does not solve the second part of the question, which might be undecidable because of the word variables, but it gives a reasonable fragment to start with.


Source Coding Theorem: what happen when go below N⋅H(x) bits?

For each bit that you compress beyond the entropy limit you lose one bit of information. Keep in mind that this theorem deals with random variables. If you want to know what happens to a specific input then you need a different kind of analysis.


“In object-oriented programming, the program is organized around its data”

procedure oriented programming means you can group some operations to finish a task when you know how to do it，step 1，step 2……
object oriented programming means you can inspect a object from two parts，its features (states or data) and its behavior in different states.


Find the smallest set of strings which "covers" a given set of strings (coverage = containing as substring)

Without loss of generality, we can take $l=k$.  In particular, any solution to $T(k,l)$ can be converted into a solution for $T(k,k)$ by shortening each string that's longer to $k$ to a string of length $k$ (by deleting as many characters from the beginning or end as needed to get down to length $k$, chosen arbitrarily).  So, it will simplify your life to focus on solving $T(k,k)$, i.e., finding a set of strings of length $k$.

Here is one possible approach.  You don't need to exhaustively generate all strings of length $k$.  Instead, you can generate all length-$k$ substrings of words of $S$.  If each word of $S$ has length $\le n$, then there will be $\le (n-k+1) \cdot |S|$ of them.  Then, you could apply some standard set-cover algorithm to that.  So, you don't need to generate exponentially many strings; just polynomially many.

It's possible there may be better algorithms that take into account the combinatorial structure of the strings; I don't know.


Understanding Martin Farach's suffix tree algorithm

Not a complete answer but I hope this helps.

re :

  Creating the odd tree requires sorting every character pair of the string, but the example used, namely g = 121112212221 yields the "sorted" list l = (1,2),(1,1),(1,2),(2,1),(2,2),(2,1), and then taking the ranks of l yields. g' = 2,1,2,3,4,3. I can't see how l is sorted, or why it would help to sort it.

Let,

$l$ - list

$g$ - ranks of elements of $l$ in $sorted(l)$

You can easily recover $sorted(l)$ using $l$ and $g$. You just put $i^{th}$ element of $l$ at position $g[i]$ in some new array $A$, like this,

for i = 0 to len(l):
   A[g[i]] = l[i]

Fill out following $A$ to see it.

l = [3, 2, 4]

g = [2, 1, 3]

A = [ , , ]


The only reasonable definition for a simple path in a finite acceptor would be a finite path in its transition graph, i.e. no vertices (states) may appear twice in that path. This especially excludes paths that use self loops.


Why Is My Proof Of Asymptomatic Time Complexity Of A Dynamic Array Using The Accounting Method Getting A Wrong Answer?

First of all notice that your first aggregate analysis should read $\sum_{i=1}^{\log n} 2^i = 2^{\log n + 1} - 2 < 2n$. (What you have written makes no sense since $\sum_{i=1}^\infty \frac{1}{2^i} \le 1$, which would mean that the aggregate complexity is upper bounded by a constant regardless of the number of operations).

Then in your last analysis you can't just place one extra credit on each element because it would only pay for the first time that such element is copied (i.e., only for the next insertion).


Here is the simplest algorithm, which is efficient when $k$ is much smaller than $n$ relatively.

Input: two positive integers $n$ and $k$ with $k\le n$
Output: a random permutation of $k$ integers from $1,2,\cdots,n$
Algorithm:

Let arr be an array of size $n$ and a default value that is not True.
Let out be an empty array.
Let i be a random integer in $[0,n)$. If arr[i] is not True, append i+1 to out and set arr[i] to True.
Go back to 3 unless we have selected $k$ elements.
return out.

If $k\le n/2$, then the algorithm above runs in $O(k)$ average time. For example, if $n=1000$ and $k=50$, it will use the random number generator less than 55 times in average. This is much better the reservoir sampling that will use the random number generator about 1000 times.

How to speed up the algorithm if $k$ is not much smaller than $n$?

We will let each element in arr be a pair (i, False). After we have selected $n/4$ elemented, we will compactify arr by removing the elements whose second entries have been changed to True. We will set $n$ to $n-n/4$ and $k$ to $k-n/4$. Repeat the algorithm.


A basic question about approximation algorithms for the Traveling Salesman Problem

The misunderstanding comes from two variations of the TSP problem:

The input graph is complete.
The input graph is arbitrary.

The standard proof above must assume the first variation of TSP.  Thus, there is no k-approximation algorithm for the first variation unless $P=NP$.  The same result then follows for the second variation due to the fact that the second variation generalizes the first variation.

To answer the question directly: The input to the TSP variation in question must be a complete graph.

Note: The Wikipedia article states the following: Often, the model is a complete graph (i.e. each pair of vertices is connected by an edge).  If no path exists between two cities, adding an arbitrarily long edge will complete the graph without affecting the optimal tour.


Why not use the channel capacity as the sliding window size?

Sliding windows are used to:

Keep track which packets were sent and received, hence the data transmission is reliable
Keep track of the memory available to the receiver. The receiver may fill its buffers and tell to the sender to slow down (because more packets will simply be dropped, causing the sender to re-send them with a probably bigger delay)

When multiple data streams pass through the same link you wont be able to use 100% of the capacity anyway, and probably more packets will be lost. In this situation sending more data simply means having to re-send the data later. That's why you want to avoid congestion and throttle the speed.

In summary: it is not true that sending data at the possible speed you can will result in the data being correctly transferred in a smaller time. It often simply means that you have to resend the same packets over again because they continue to get lost/dropped by congestioned routers/dropped by congestioned receiver. Sliding window are a way to control this and provide better overall performance.

Note: if you do not want a reliable transmission then sending at the maximum speed is better. However the amount of data that arrives correctly at the receiver may get quite small compared to what was sent.


Single Layer Perceptron vs Multi Layer Perceptron

Your premise is wrong.  A single-layer neural network (perceptron) can use a (nonlinear) activation function.  Nothing prevents you from doing that.

It's common that the last layer of a neural network doesn't use any activation function, and instead is input into a softmax layer.  If there's only one layer, that means that no activation function is used.  But this is just a standard convention.  There's no ironclad law that says you have to do it this way.  You could have an activation function after a single-layer neural network, if you wanted.


The huge difference is that a Turing reduction allows you to call the black-box more than once. Suppose you have the $\mathtt{GraphColor?(G, k)}$ decision problem which tells you if the graph $G$ can be colored with $k$ colors. A Karp reduction only allows you to call this problem exactly once. But a Turing reduction allows you to call $\mathtt{GraphColor?(G, k)}$ a polynomial number of times. So if you want to figure out the chromatic number of the graph, call the function with $k=1, k=2, \ldots$ and so on until you get something that works. To make it more efficient, use binary search instead.


As the name suggests, a many-one reduction can map many instances of $K$ onto a single instance of $A$.  If there are no restrictions on the power of $f$, then you can pick some $a\in A$ and $b\notin A$ and then define
$$f(x)=\begin{cases}
a &\text{ if }x\in K\\
b &\text{ if }x\notin K\,.
\end{cases}$$

However, if $f$ is restricted to be computable then the image of $f$ is necessarily infinite. This is because every finite set is computable so, if the image of $f$ were finite, you'd have a computable reduction from the halting set to a computable set, which is impossible because that would mean the halting set would be computable too.

If $B$ is recursive and $f$ is computable then you can decide whether $x\in f^{-1}(B)$ just by checking whether $f(x)\in B$. If $B$ isn't recursive or $f$ isn't computable, all the bets are off.


reduction of independence problem and cluster problem

If i understand your question correctly, given $G$, build a graph $G'$ where $V(G)=V(G')$ and for every $v,u\in V(G)$, $(v,u)\in E(G')\iff(v,u)\notin E(G)$


What exactly is the semantic difference between category and set?

In brief, set theory is about membership while category theory is about structure-preserving transformations.

Set theory is only about membership (i.e. being an element) and what can be expressed in terms of that (e.g. being a subset). It does not concern itself with any other properties of elements or sets.

Category theory is a way to talk about how mathematical structures of a given type1 can be transformed into one another2 by functions that preserve some aspect of their structure; it provides a uniform language for speaking of a great range of types1 of mathematical structure (groups, automata, vector spaces, sets, topological spaces, … and even categories!) and the mappings within those types1. Although it formalises the properties of mappings between structures (really: between the sets on which the structure is imposed), it only deals with abstract properties of maps and structures, calling them morphisms (or arrows) and objects; the elements of such structured sets are not the concern of category theory, and nor are the structures on those sets. You ask “what is it a theory of”; it is a theory of structure-preserving mappings of mathematical objects of an arbitrary type1.

The theory of Abstract categories3, however, as just stated, totally ignores the sets, operations, relations and axioms specifying the structure of the objects in question, and just provides a language in which to talk about how mappings that do preserve some such structure behave: without knowing what structure is preserved, we know that the combination of two such maps also preserves structure. For that reason, the axioms of category theory require that there be an associative composition law on morphisms and, similarly, that there be an identity morphism from each object to itself. But it does not assume that morphisms actually are functions between sets, just that they behave like them.

  To be worked out: Concrete categories model the idea of adding structure to the objects of a ‘base category’; when this is $\mathsf{Set}$ we can have the situation where we add structure like a group operation to a set. In this case one may have more to say about how structure is added in terms of the specific base category.

As for the implications of your formulations, saying that “$G$ is a group”, that “$G$ is an element of the set of groups” (actually a proper class) or that “$G$ is (an object) in $\mathsf{Grp}$” (or a “$\mathsf{Grp}$-object”) mean the same thing logically, but talking about the category suggests you are interested in group homomorphisms (the morphisms in $\mathsf{Grp}$) and perhaps in what they have in common with other morphisms. On the other hand, saying $G$ is a group might suggest you are interested in the structure of the group (its multiplication operation) itself or perhaps in how the group acts on some other mathematical object. You would be unlikely to talk about $G$ belonging to the set of groups, though you could easily write $ G ∈ S $ for some particular set $ S $ of groups you are interested in.

See also

https://math.stackexchange.com/questions/tagged/category-theory?sort=votes

In particular https://math.stackexchange.com/questions/272875/concrete-category-and-abstract-category#1774821

Abstract and Concrete Categories: The Joy of Cats by Adámek, Herrlich and Strecker
https://en.wikipedia.org/wiki/Category_theory

https://en.wikipedia.org/wiki/Concrete_category

1 Here and passim I do not refer to type in the sense of type theory, but rather a set of properties required of the mathematical objects/structures, i.e. a set of axioms they satisfy. Normally these describe the behaviour of some operations or relations on elements of the sets considered to carry the structure, though in the case of sets themselves ($\mathsf{Set}$) there is no structure beyond the sets themselves. In any case, as said above, category theory ignores the details of this structure.

2 I should perhaps say into all or part of one another: one allows the homomorphism from $ \mathbb Z $ (integers) into $ \mathbb Q $ (rationals) given by $ n \mapsto \frac n 2 $ .

3 Without qualification, ‘category’ normally means ‘abstract category’, introduced, as far as I can see, in 1945 and developed in the 1960’s while Concrete categories seem to appear in the 1970’s.


If the two generals problem is unsolvable how can we human beings agree on things?

I disagree with other answers that the communication channel needs to be modelled differently. Malice is irrelevant, simple lost messages with any non-zero probability are sufficient to create the two generals problem. e-mail and IM, for example, have a low but not zero chance of dropping messages. Phone calls can suffer interference, so as with the two generals problem you need to somehow confirm whether the other person heard what you said, ad infinitum. And yet I frequently use these channels to make agreements with other people.

What the insoluble "two generals" problem fails to solve, is to get guaranteed common knowledge. In real life we don't require formal common knowledge in order to proceed. Therefore the goal in most practical situations needs to be described differently from the goal in the two generals problem.

We settle for agreement being "sufficiently likely". I might not be willing to attack unless I'm certain you will attack, but I'm willing to walk to the coffee shop to meet you provided that the probability of a communications failure isn't grossly higher than the probability of you failing to arrive due to traffic. Unlike the generals, I'll take a chance on you meeting me.

If you've ever had someone explain something three times to you in different ways when you got it the first time, or ever had someone ask you to confirm something that you've already confirmed twice, then it's because you reached your threshold of "sufficiently likely" before they reached theirs.

Take your pick of psychology, philosophy, or evolutionary biology as the correct realm in which to look for an answer to the next question, why we don't really need a full guarantee of common knowledge :-)

It also relates back to practical problems in computing. For example when we use a single-error-correcting code to "validate" that a symbol in a message has arrived correctly, all we're doing is accepting that the probability of a double-error is negligible for the time being. Then later in the protocol we might have a CRC, to further reduce the probability of undetected error. None of this solves the two generals problem, but it is sufficient for me, my bank and a merchant all to "agree" that a credit card transaction has occurred, with a small probability that we disagree.


Does there always exist a reduction between two NP-hard problems?

A decision problem $L$ is NP-hard when for every problem $H$ in NP, there is a polynomial-time reduction from $H$ to $L$. This is important because it does not necessarily go the other way, you can not say there is a polynomial time reduction from $L$ to $H$. This is because a problem can be NP-Hard and not be in NP. If $A$ and $B$ in your question are both not in NP then there may not be a reduction.


How do I solve a maze using velocity and acceleration?

At any point, the state of the system is a pair $(p,v)$ where $p$ is the current position and $v$ is the current velocity vector.  At any state, there are 8 possible actions (transitions out of that state, to another state).  Search over this state space using any algorithm for searching state spaces to find the lowest-cost path from the start state to the desired end state; for example, you could use BFS, A*, etc.  This should solve the problem in a clean, straightforward, and efficient way.


Regular expression that have the same number of 0 and 1

Your $\alpha$ matches all strings, and is certainly incorrect.

The language is a union of two sets, so you can consider the two parts respectively and construct the regular expression with the form $R_1\mid R_2$.

The $\Sigma^*\{00,11\}\Sigma^*$ part is easy.

The $|w|_0=|w|_1$ part is somewhat tricky. You cannot construct a regular expression for $|w|_0=|w|_1$ because this language is not regular. However, You can only care about the set $S=\{w\mid |w|_0=|w|_1\text{but }w\notin\Sigma^*\{00,11\}\Sigma^*\}$ instead of the set $\{w\mid |w|_0=|w|_1\}$. Now try to figure out what $S$ looks like and write a regular expression for it. This is not hard.


What does "AC0 many-one reduction" mean?

An AC0 many-one reduction is a many-one reduction that can be implemented by an AC0 circuit.  It's just like a polynomial-time many-one reduction, except that instead of requiring that the mapping takes polynomial time, we require that the mapping is in AC0.

David Richerby further explains: "AC0 is a very low-complexity class so it can be used, for example, to study reductions between logspace problems, which doesn't make sense with polytime reductions since, then, the reduction would be more powerful than the problem class being studied."  For instance, if problems A,B can be reduced to each other with polynomial-time reductions, then you learn that their complexity can't be exponentially different (if one is polynomial, the other must be too), but it's possible that they still might be fairly different (polynomially different).  If they can be reduced to each other with AC0 reductions, then this has stronger implications about their  complexity (it has to be pretty similar).


If your number $x$ is $n$ bit long, the number formed by the first $k$ is $x/2^{n-k}$, rounded down. The number formed by the last $k$ is the remainder in that division.


Recommendations for machine learning book?

MOOC Course on Machine Learning: https://www.coursera.org/course/ml

Guide to Mathematical Proofs from berkeley: https://math.berkeley.edu/~hutching/teach/proofs.pdf

Enjoy!


What is meant by a full abstract model of a lambda-calculus like language?

In denotational semantics, you want to be able to map each of your language terms to some object in your semantic domain or model. Now, it cannot be any arbitrary domain/model as you like, but, informally speaking, something that gives a good intuition about how the language works (its computational behavior).

Milner tried to formalize what this "intuition" should be and called it full abstraction. Formally, a model is fully abstract if all observationally equivalent terms in the object language represent the same object in the model. Equationally:
$$\text{if }  ⟦t_1⟧ = ⟦t_2⟧  \text{then } t_1 \rightsquigarrow t_2 $$
where $\rightsquigarrow$ represents observational equivalence. In case of lambda-calculus observational equivalence would be $\beta\eta\alpha$ conversions and $⟦\_⟧$ is the denotation function.

There are few papers that you might want to take a look at if you are interested in seeing some full abstract models of lambda like languages:

Plotkin's paper that gives a full abstract model of the lambda like language called LCF
Mulmuley's paper gives a full abstract model of typed lambda calculus.
Hyland and Ong's papers give a full abstract model of PCF using game semantics


Proof of correctness of algorithm to determine whether the elements of an array are repeated an equal number of times

No, your algorithm doesn't work.  Consider if the array A is

A = [1 1 1 1 1 2 2 3 3 3 3 3 3].

Then the array B will be

B = [5 5 5 5 5 2 2 6 6 6 6 6 6].

The sum of B will be 65, and the length of B will be 13, so after division, we'll get the number 5.  This is equal to the first element of B, so your algorithm will output "Yes".  Nonetheless, not all elements of B are the same, and the correct answer is "No".  So, your algorithm gives the wrong output on this case.

Nice try, though!  Figuring out how to build B was probably the hardest part of this problem.

How I found this: I couldn't find a counterexample with two distinct numbers, so next I tried with three distinct numbers.  Let $u,v,w$ denote how often each of those numbers appear.  Then the array will have length $u+v+w$, and B will contain the value $u$ repeated $u$ times, the value $v$ repeated $v$ times, and $w$ repeated $w$ times, so the sum of elements of B is $u^2+v^2+w^2$.  We can find a counterexample if we can find a solution over the positive integers to the Diophantine equation

$${u^2 + v^2 + w^2 \over u+v+w} = u$$

such that $v\ne u$ or $w \ne u$.  This is equivalent to

$$u^2 + v^2 + w^2 = u(u+v+w),$$

where $u,v,w$ are positive integers and either $v\ne u$ or $w \ne u$.  I then picked a few small values of $u$ and tried solving this Diophantine equation using Wolfram Alpha.  The first solution I stumbled across was $u=5$, $v=2$, $w=6$, but there are many others as well.  In retrospect I guess I could have simplified further to

$$v^2 + w^2 = uv + uw$$

but I didn't notice and it turned out not to matter.


The terminology isn't absolute when applied to actual languages. Usually "stateful" refers to holding the "state of the computation" largely in variables of some sort (variables = changeable references to values). These can be ordinary variables (C) or fields of objects (C++, Java). It is possible in many such languages, however, to minimize such state and to program largely with constants only and with parameters of functions and methods. The latter can be variables or constants, depending on the language.

The reason that stateful languages can be programmed this way is that they also employ a run time stack in which values can be maintained.

Stateless programming in most commonly done in functional languages that minimize the use of variables, depending on constants and constant function arguments. The computation "state" is the stack itself. However, most functional languages do have some mechanism for declaring variables (things which vary), though they also tend to call names that refer to constants as "variables" confusing the issue somewhat.

In "pure functional programming" you utilize only constants and immutable function arguments to move values around the computation. The "State of the Computation" is the state of the run time stack. This is true Stateless programming.

Most imperative and OO programming, on the other hand is stateful. The "State of the Computation" is comprised of both the state of the run time stack and the currently referenced values of the variables.

Another way to think of it is that in stateless programming, the state is "implicit" in the stack and the current program pointer. In stateful programming, the state is explicit in the variables and fields (to a large part - there is also the stack).


What's wrong with this problem (Inclusion-Exclusion principle)

Let $A$, $B$, and $C$ be the set of pupils that have access to a PC running Windows, Apple, and Linux, respectively.

We know that
\begin{align*}
  |A \cup B \cup C| &= 120 \\
  |A| &= 80 \\
  |B| &= 40 \\
  |C| &= 10
\end{align*}

As @Tom van der Zanden pointed already pointed out in the comments, the wording of "... running the Apple or Windows operating system" is unclear. Thus I will cover all three interpretations of that wording.

Interpretation 1: "... running the Apple or Windows operating system" means the PC has installed both the Apple and Windows OS.

This means
\begin{align*}
  |A \cap B| &= 30 \\
  |A \cap C| &= 7 \\
  |B \cap C| &= 5
\end{align*}
Using inclusion-exclusion, we come to the result that
\begin{align*}
  |A \cap B \cap C| &= |A \cup B \cup C| - |A| - |B| - |C| + |A \cap B| + |A \cap C| + |B \cap C|\\
  &= 120 - 80 - 40 - 10 + 30 + 7 + 5 \\
  &= 32
\end{align*}
So your calculation is correct and there is a contraction. That means that either

the inclusion-exclusion princliple does not hold in general, or
the exercise description is inconsitent, i.e. some of the cardinalities are wrong.

Since the inclusion-exclusion principle is proven to hold for any arbitrary set of sets, the latter case must be true.

Interpretation 2: "... running the Apple or Windows operating system" means that the PC runs either the Apple or the Windows OS.

We can calculate the cardinalities of the intersections $A \cap B$, $A \cap C$, and $B \cap C$. However, we also run into a contradiction by using this interpretation:

\begin{align*}
  & |(A \cup C) \setminus (A \cap C)| = |A \cup C| - |A \cap C| = |A| + |C| - 2|A \cap C| \\
\implies & |A \cap C| = \frac{|(A \cup C) \setminus (A \cap C)| - |A| - |C|}{-2} = \frac{7 - 80 - 10}{-2} = 41.5
\end{align*}
The above is a contradiction, since the cardinality of a finite set must be a natural number.

Interpretation 3: "... running the Apple or Windows operating system" is a regular logic or.

We have $|A| = 80 > 30 = |A \cup B|$. This is also a contradiction, since the cardinality of a set cannot be greater than the cardinality of its superset.

For either interpretation we show that there is a contradiction, therefore there must be a problem in the exercise description


Hint: For BPP it is the case that $BPP^{BPP} = BPP$. The idea is that given a machine in $BPP^{BPP}$, we simulate each oracle call by a BPP computation, amplified so that the error probability is very small. Since there are only polynomially many oracle calls, overall the error coming from miscalculating the BPP oracle calls is small, and the resulting machine still has bounded error. (For a more complete proof, use your web search skills.) Try to emulate this line of reasoning for RP.


Question on the paper ``Self-Testing/Correcting for Polynomials and for Approximate Functions''

The definition of $g$ should be interpreted in the following way:

  Any function $g$ for which $g(x)$ is a majority value of $\sum_{i=1}^{d+1} \alpha_i P(x+i\cdot t)$ satisfies what follows.

Since it is later proved that $g = f$, it follows that $g(x)$ is always a strict majority (if it weren't, you would be able to define two different realizations of $g$, and prove that both of them are equal to $f$, contradicting their being different).

If you don't like this interpretation, you could fix a tie-breaking rule and use it to define $g$ conclusively. For example, you could take $g(x)$ to be the smallest majority value of $\sum_{i=1}^{d+1} \alpha_i P(x+i\cdot t)$. The exact tie-breaking rule makes no difference, since the proof shows that it is never actually used.

This kind of definition is common in the literature, and it is best to get used to it. Sometimes the authors explicitly mention that ties can be broken arbitrarily, but otherwise it is just implicitly assumed.


Finding rainbow cycle in digraph colored with $\log n$ colors

The idea is to use dynamic programming. For each vertex $v$ and color subset $S$, calculate whether there is a simple path, ending at $v$, and including exactly the colors in $S$. Details left to you.

The main trick here is that we can be sure that the path being constructed is simple since all vertices in it have different colors. We can apply the same idea to uncolored graphs by choosing a random coloring. This is known as color-coding, an idea of Alon, Yuster and Zwick with wide applicability.


Proving that if $\mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})$ then $\mathrm{P}=\mathrm{NP}$

Here is the solution using padding. Suppose $L \in \mathrm{NTime}(n^{1000})$. Define a new language $L' = \{x0^{|x|^{10}-|x|} : x \in L\}$. Each $x \in L$ corresponds to some $y \in L'$ of length $|y| = |x| + (|x|^{10}-|x|) = |x|^{10}$. Therefore we can decide whether $y \in L'$ in non-deterministic time $|x|^{1000} = |y|^{100}$, i.e. $L' \in \mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})$. In order to decide whether $x \in L$, form $y = x0^{x^{10}-|x|}$ and run the $|y|^{1000} = |x|^{10000}$-time deterministic algorithm for $L'$. We conclude that $L \in \mathrm{DTime}(n^{10000})$.


Write the conjunctive or disjunctive normal form of an expression $f$

As @DavidRicherby said, it's best if you ask who-gave-you-the-question what he meant by $(xyz)_2$.
But if you absolutely can not do that, then you look at the situation mathematically as...

$(xyz)_2$ here is a set $\{000,001,010,011,...,111\}$ of $8$ elements which forms a ring.
In particular, it supports two binary operation $+$ and $\times$ where both operation has identity element, the addition has inverses...

If you can decide the addition table and multiplication table that makes sense in your context, then you're set.
As long as it's a ring, then that polynomial equation makes sense.


Valid method to prove NP completeness of a problem?

No, they're not. NP-completeness is defined using many-one reductions and you've used a Turing reduction.  The difference, in a nutshell, is that for a many-one reduction, you're only allowed to make one call to the function you've called hpn, and you must return its result as your result.  Schematically, your reduction needs to look like:

Compute a graph G' and vertices x and y from the input graph G;
return hpn(G',x,y);


Counting substrings with a given number of different characters in O(N)

You can solve this in $O(n)$ time using two (well, three) pointers that both move leftward.

Let $S$ be the string.  We'll let $i$ range from $n$ down to $1$, and for each value of $i$, we're going to count the number of substrings that start at position $i$.

For each $i$, find the smallest $j_\text{min} \ge i$ such that $S[i..j_\text{min}]$ has exactly $k$ unique characters as well as the largest $j_\text{max} \ge i$ such that $S[i..j_\text{max}]$ has exactly $k$ unique characters.  You can do this efficiently, by keeping an array (or hashtable) with character counts for $S[i..j_\text{min}]$ and one with character counts for $S[i..j_\text{max}]$; you'll update these each time you decrement $i$, $j_\text{min}$, or $j_\text{max}$.  (In addition to the array/hashtable, also keep track of the number of of characters with non-zero count, and update this each time you update the array or hashtable.)  When you decrement $i$, you can update the array/hashtable with character counts for $S[i..j_\text{min}]$, then use that to see whether you need to decrease $j_\text{min}$ and by how much (updating the array/hashtable each time you decrement $j_\text{min}$).  Same for $j_\text{max}$.

Finally, sum up the counts you get for each value of $i$.

Note that $j_\text{min}$ starts out at $n$ and only ever decreases: when you decrement $i$, $j_\text{min}$ can only ever get smaller (but not bigger).  So, you'll only need to decrement $j_\text{min}$ (and update the array/hashtable) at most $n$ times: it starts out at $n$, and only ever decreases, and never gets smaller than $1$, so it can only be decreased at most $n$ times.  The same is true for $j_\text{max}$.  Consequently, we do at most $O(n)$ updates to the array/hashtable (summed up over all the steps of the algorithm), so the total running time of this algorithm is $O(n)$.

Credit: Thanks to @aaaaajack for a major improvement to my algorithm, and to @Raphael for further improvements.


Prolog: Deletion of all appearances of an element in a list

There are some rules of thumb I follow when writing prolog. Two of them are:

Use dif instead of \=. From the reference manual: "To make your programs work correctly also in situations where the arguments are not yet sufficiently instantiated, use dif/2 instead."

Avoid unnecessary variables and always get rid of the "Singleton variables: [X]" error. It makes the code much more readable.

When I rewrite your code accordingly, your
my_delete(X, L, R):- [] = L, [] = R
my_delete(X, L, R):- [Y|K] = L, [Y|M] = R, my_delete(X, K, M), (Y \= X)
my_delete(X, L, R):- [X|K] = L, [Y|M] = R, my_delete(X, K, R), (Y \= X)

becomes
my_delete(A, [], []).
my_delete(X, [Y|K], [Y|M]):- my_delete(X, K, M), dif(X, Y).
my_delete(X, [X|K], R) :- my_delete(X, K, R).

which is not only concise and more readable, but it already seems to work.
As for your particular case, I think it has to do with the quote in the first rule of thumb above. Your X and Y are not sufficiently instantiated, so it is no surprise for me, that your program does not work correctly.
But the "dif vs. \=" issue is probably not a problem in this case. I replaced dif(X, Y) with X \= Y in the code I suggested above, and it still works. (It may be causing a problem in your code though. I don't know if this is the case.)
Just using dif instead of \= is not a solution either. After replacing the \=s with dif in your code, it still does not work correctly. If the element to be removed is at the last position, it does not work. my_delete(baz, [baz], X) fails, for example.
So what is the problem? It seems to me that you've made two mistakes in your last line. You've put an unnecessary (Y \= X). Line 3 was supposed to be the case in which L starts with X. So the inequality check there should probably be an equality check. And secondly, you probably shouldn't have splitted R into [Y|M].
You can try the code here: https://swish.swi-prolog.org/p/myClMmML.pl
Swish has a great debugger as well. Check out its help.


Does undecidability ever imply unmeasurability and make a notion of probability ill-defined?

The space of possible inputs of a Turing machine is countable, so all its subsets are measurable. Same for outputs.
However, it's possible that this probability is not computable. In particular, you may want to look up Chaitin's constant. It isn't exactly what you are talking about, but closely related.


How to prove the following xor equation?

(I use the symbol $\oplus$ here because $\wedge$ is mathematically used for conjunction ("and") instead of exclusive-or)

First we rearrange the terms,
\begin{align}
 x_1 \oplus x_2 \oplus x_3 \oplus x_4 &= 0 \\
 x_1 \oplus x_3 \oplus x_2 \oplus x_4 &= 0 \\
 x_1 \oplus x_3 &= x_2 \oplus x_4
\end{align}
Then use $a \oplus b = a' \oplus b'$ to get (C).
$$ x_1' \oplus x_3' = x_2' \oplus x_4' $$


Has this model of random directed graphs been studied?

It is very easy to say something about the expected length before you get stuck in a loop: if there are $n$ videos, it will (starting from a random video) take in expectation $\Theta(\sqrt{n})$ videos before you loop around (the actual value is around $1.25\sqrt{n}$). This is effectively the birthday problem, since each time you draw a video at random.

Since each video in the chain of $\Theta(\sqrt{n})$ videos is equally likely to be the one you loop back to, the average length of a loop is also $\Theta(\sqrt{n})$ videos (actual value $0.625\sqrt{n}$).

This gives the expected length of the loop you end up in after starting from a random video. This means that a loop with many videos leading to it is counted more strongly. If instead you want to know the expected length of a loop if you pick a random loop, this may be found as $T(1)$, where

$$T(i)=\frac{n-i}{n}T(i+1)+\frac{i}{n}\frac{i+1}{2}$$

and $T(n)=\frac{n+1}{2}$. Computing the values of $T$ experimentally it seems to match up with $0.625\sqrt{n}$, so both ways of counting the expected loop length are the same.

Computing the expected number of cycles seems to be a harder problem. We start by counting the expected number of cycles of a given length. The probably that a node is part of a length-1 cycle is $\frac{1}{n}$, so there are in expectation $1$ length-1 cycles. The probability that a node is in a length-2 cycle is $\frac{n-1}{n}\frac{1}{n}$, so there are in expectation $\frac{1}{2}\frac{n-1}{n}$ length-2 cycles. In general, the number of cycles of length $l$ is $\frac{1}{l}\Pi_{i=1}^{l-1} \frac{n-i}{n}$.

We can obtain a crude upper bound on the number of cycles by considering $\Sigma_{i=1}^n \frac{1}{i} = H_n$ which is $O(\log n)$. Unfortunately the number of cycles doesn't seem to converge to $\log n$ so this bound is not tight.


This is a simple Interval Scheduling Maximization problem, which can be solved in O(n log(n)) time via a simple greedy algorithm. The trick is to sort performances according to end time and not start time.

Here is the description of the solution found on the Wikipedia page I linked:

Several algorithms, that may look promising at first sight, actually do not find the optimal solution:

Selecting the intervals that start earliest is not an optimal solution, because if the earliest interval happens to be very long, accepting it would make us reject many other shorter requests.
Selecting the shortest intervals or selecting intervals with the fewest conflicts is also not optimal.

Greedy polynomial solution

The following greedy algorithm does find the optimal solution:

Select the interval, x, with the earliest finishing time.
Remove x, and all intervals intersecting x, from the set of candidate intervals.
Repeat until the set of candidate intervals is empty.

Whenever we select an interval at step 1, we may have to remove many intervals in step 2. However, all these intervals necessarily cross the finishing time of x, and thus they all cross each other. Hence, at most 1 of these intervals can be in the optimal solution. Hence, for every interval in the optimal solution, there is an interval in the greedy solution. This proves that the greedy algorithm indeed finds an optimal solution.

A more formal explanation is given by a Charging argument.

The greedy algorithm can be executed in time O(n log n), where n is the number of tasks, using a preprocessing step in which the tasks are sorted by their finishing times.


PL: What solves the type isomorphism $X \cong (X \rightarrow \mathbf{2})$?

To say that we cannot solve $X \cong (X \to 2)$ in sets means that we have to do it in another category. And because we're talking programming languages, we should be looking for one in domain theory. The buzzword to look for is recursive domain equation.

There are several kinds of domains, but to give you an idea of what they are, perhaps we can recall the definition of $\omega$-cpos. An $\omega$-cpo $(P, {\leq})$ is a set $P$ with a partial order $\leq$ which has a least element $\bot \in P$ and such that every increasing sequence $x_0 \leq x_1 \leq x_2 \leq \cdots$ in $P$ has a supremum.

In the particular case we look for a domain $X$ which satisfies
$$X \cong [X \to 2_\bot]$$
where:

the domain $2_\bot = \{0, 1, \bot\}$ is ordered by $\bot \leq 0$, $\bot \leq 1$ (i.e., $\bot$ is below $0$ and $1$, and $0$ and $1$ are incomparable). The domain $2_\bot$ corresponds to the datatype bool: $0$ and $1$ are the boolean values, while $\bot$ represents a non-terminating program.
the domain $[E \to D]$ is the domain all all continuous maps from $E$ to $D$, where a map is said to be continuous if it is monotone and it preserves suprema of increasing chains.

Now, the reason why an equation such as $X \cong [X \to 2_\bot]$ has a solution is complicated. Figuring out that soultions exist when we take a good enough notion of "domain" was done in the early 1970s, with poineering work of Dana Scott and several other people. It takes a short course on domain theory to get to the point where the construction of solutions becomes explainable.

Perhaps I can comment on why domain theory avoids the usual problem from set theory, where Cantor's diagonal argument shows that $X$ always has fewer elements than $X \to 2$. In domain theory $[X \to 2_\bot]$ is not the set of all maps, but just the continuous ones, and there are many fewer of those.

Let's attempt a more familiar setup. Consider the real number $\mathbb{R}$ and the Sierpinski space $\mathbb{S}$, which just the set $2 = \{0, 1\}$ with the topology in which the open sets are $\emptyset$, $\{1\}$ and $\{0, 1\}$. It is well known that the set of continuous maps $\mathcal{C}(\mathbb{R}, \mathbb{S})$ is in bijective correspondence with the open subsets of~$\mathbb{R}$, of which there are $2^{\aleph_0}$, and so we have "solved" $X = X \to 2$ in sets by restricting to continuous maps:
$$\mathbb{R} \cong 2^{\aleph_0} \cong \mathcal{C}(\mathbb{R}, \mathbb{S}).$$
This is not a solution, however, because the bijection between $\mathbb{R}$ and $\mathcal{C}(\mathbb{R}, \mathbb{S})$ can never be a homeomorphism.

Sometimes we can actully solve a recursive equation with much less work. For instance, working in topological spaces, we have
$$\mathbb{N} \cong 2^{2^\mathbb{N}}$$
because $2^{\mathbb{N}}$ is the Cantor space, whose set of clopen sets is countable and discrete (under the compact-open topology), therefore homeomorphic to $\mathbb{N}$.

Yet another example comes from ordinal arithmetic (not cardinal arithmetic!) where have $2^\omega = \omega$, so that is maybe the closest to what you're asking for.


Radix, merge, counting sort and when to use

The idea seems wrong at its core. The missing parts are: what is the distribution and range of the data. How many items do you have? (You may not know this in advance, but it renders some algorithms useless).

The counting sort works well when the range is compact, it gives good memory requirements and the mere array traversal is not computationally expensive. In the case of floating-point numbers, when you multiply decimal part to make full integers the range may be huge, in that case $n$ may be small but $k$ is huge.
Instead of multiplying them out the better idea is to round them and store only decimal part. This idea would not blow up the range and after counting you are left with small bins to sort. To give more or less answer to $p$ parameter, it really depends on scarcity of data and number, but say, if you really want to multiply them by $10^p$ in many cases for $p \ge 3$ it seems like bad idea.

The radix sort depends on $d$ which is the number of digits, here it doesn't matter where is the decimal point, but with bigger $p$ the $d$ is bigger, which kills the performance (unless bigger radix is used for decimal part only).

Merge sort, the natural variant, is $\mathcal O(n)$ but this property is not that important to choose, it effectively says that the algorithm terminates sorting early when it gets sorted data. The best case for sorting (when applicable by algorithm properties) must be $\Omega(n)$ to at least read the input and check whether consecutive numbers obey order.
Merge sort runtime does not depend on $p$, as far it is some built-in type, unless the float is stored as the string, but this on its own may be problematic and performance killer. The access to decimal digits in case of some floating-point number requires conversion, which takes time or additional memory.

To choose sorting algorithm the first step is to match inherent properties with data, use (or add if you have to) properties like stability of sorting, understand what asymptotic notation mean, look at average case and test with your real data.

Why $n$ is important here? Because if it is small (10-20) Bubble sort is faster on average than other algorithms (short of counting sort with extremely tight range), because it has small hidden constant and for non-artificial data it does rarely encounter bad case. The situation gets more complicated when actual data is bigger, but in the case of smallish data, say 1000 – 20000 items, the hidden constant still matters.

For data in your format (3 digit decimals with $p$ decimal places) if you know distribution, it may be beneficial to use distribution sort or counting sort, rounding numbers beforehand. Back to your question, the decision to select one of given algorithms doesn't solely depend on $p$.


Is a "tree" with $0$ vertices, $0$ edges or $1$ vertex, $0$ edges considered a valid tree?

Here are a few properties of trees which can be relevant:

A tree on $n$ vertices has $n-1$ edges. Works for (2) but not for (1).
A graph has no cycles iff it is a disjoint union of trees. Works for both (1) and (2), unless you require the decomposition into trees to be unique, in which case it works for (2) but not for (1).
A tree is either a single vertex or a bunch of disjoint trees connected to a common vertex. Works for (2) but not for (1).

These examples suggest that the commonsense definition of tree should include (2) but not (1). Indeed, oftentimes it seems that the graph on no vertices is a pointless concept; see the classical discussion of Harary and Read, who present arguments for both sides of the issue.

Practically speaking, you should probably assume that (1) is not a legal graph, unless it makes sense in your application, and then you should explicitly mention the fact.


Question about big O notation for function

The denominator is just a constant so $O(\cdot)$ doesn't care about it.  For all $n\geq 0$, $\tfrac14n(n-3)\leq 1\cdot n^2$ so $\tfrac14n(n-3)\in O(n^2)$.


Confusion regarding the Definition of 2 Way Finite State Automata?

Unlike ordinary finite automata, a 2DFA needs only a single accept state and a single reject state.

Finite automata do not need more accepting states. Well, non-deterministic FA don't; just add two final states and appropriate $\varepsilon$-transitions. Deterministic FA, though, need multiple final states; above construction doesn't work, and Myhill-Nerode tells us that we indeed get multiple final states for some languages.

  Unlike ordinary finite automata, a 2DFA needs only a single accept state and a single reject state.

If you add rejecting states to finite automata (an easy enough exercise), neither do finite automata. Consider, for instance,

$\qquad L_0 = \{ w \mid w_1 = 0 \} \cap L$

for any regular $L$. Then, a finite automaton for $L_0$ can reject immediately if the first symbol is not a $0$.

In summary, I think the authors try to read meaning into arbitrary syntactical differences.

That said, note how 2DFA need a rejection state for the stated reason: there is no natural "end of computation".


PDA - Sum of Two Characters = Sum of Two Other Characters

You can probably build a PDA for the language $\{p^nq^n\mid n \ge 0\}$. If so, you're almost there. Just treat the a's and b's as if they were all p's and the c's and d's as if they were q's, like this (with details elided):

Count the a's and b's by pushing a marker on the stack for each one (making sure that all the a's precede any b).
Match them up with the c's and d's: for each one seen, pop a marker off the stack (again, making sure that the input is correctly formed).
If the stack is empty after having read all the input, accept.


Minimum distance of nodes from a set of two nodes

You can do this with only one BFS and the solution is very simple.

I will assume that you have as input a graph $G = (V, E)$. Let $dist$ be a vector which stores the distance of all nodes of your graph to node $v \in V$.

You must run a BFS algorithm starting on node $v$ and store the distance from each node to $v$ in $dist$. This value can be simply obtained during the BFS execution. Then, you can iterate through this vector marking (or deleting) all nodes $i$ such that $dist[i]$ < $dist[w]$.

The overall complexity of this algorithm is $\mathcal{O}(V + E + V)$. In a tree, we have that $|E| = |V|-1$. Thus, the complexity is $\mathcal{O}(3 V) = \mathcal{O}(V)$.


Why computer science papers rarely use advanced mathematics?

There are many reasons that you may not see a lot of complex mathematics in the papers you are reading.

First, the tools used depend on the task at hand. If a task is simple, a simple tool might be adequate. Also, if the task runs on a simple system, a simple tool is often best.

Second, usually in Computer Science, the goal is usually to make things usable to a layprogrammer; therefore, it would be detrimental to make something depend on an advanced or abstract concept that few people understand. Often, the proofs sections of algorithms papers have much more advanced mathematics than the rest of the paper; the assumption is that anyone who wants to verify the correctness of the algorithm or its complexity can invest the time in understanding the proof, but that that is not essential to use the results.

Finally, some of this has to do with a lack of familiarity; people who spend their lives reading and writing computer science papers might never have the time to learn about new, highly complex mathematics. Actually, a great way to expand the field is to introduce a concept that many mathematicians understand in a way that it is accessible to and usable by computer scientists. (For instance, I have a friend whose PhD work applied known concepts of Control Theory to problems in Motion Planning. He did very little new work, but he did advance Motion Planning.)


Searching a value in a "piecewise" ordered array

It should be possible to do this with $O(\sqrt{N})$ comparisons, saving an $O(\log N)$ factor over the straightforward "binary search each subarray".

The last condition, that the lengths of the subarrays strictly increases, makes things messy.  The analysis of $M$ subarrays, each of length $M$, is easier and it should be straightforward to extend the method to increasing-length subarrays.
Note that $\log M = O(\log N)$.

Also complicating things are the strict inequalities; it is easier to work with non-strict inequalities (which are also more general).

Finally, the conditions ensure that in subarray $A(i)$, the first element $A(i,1)$ is the minimum value and the last element $A(i,M)$ is the maximum value, so there is no need to deal with these elements explicitly.  This yields the simplified problem

there are $M$ subarrays of equal length $M$, and
for all $i,j$

[monotonicity across subarrays] $A(i,j) \le A(i+1,j)$,
[adjacent subarrays overlap] $A(i+1,1) \le A(i,M)$, and
[monotonicity within subarrays] $A(i,j) \le A(i,j+1)$.

If there is $u$ such that $A(u,1) \le n < A(u+1,1)$,
then only the first $u$ subarrays need to be considered,
and similarly for $v$ such that $A(v-1,M) < n \le A(v,M)$ focuses attention on the last $v$ subarrays; together their intersection defines a set of subarrays that must contain $n$.  The rest of the subarrays can be ignored.
This preprocessing can be done in $O(\log N)$ steps.

Then $A(i,1) \le n \le A(i,M)$ is guaranteed for each remaining $i$ in the range $M-v+1$ to $u$, otherwise $n$ is not in the array.  For the remainder, suppose that the preprocessing did nothing, so $u=v=M$ (this is the worst case). Run binary search on the middle subarray $w=\lfloor M/2\rfloor$; this determines that $A(w,j) < n < A(w,j+1)$; (if equality holds then $n$ has been found).

By monotonicity across subarrays, $A(i,j) \le A(w,j) < n$ for all $i \le w$ and similarly $n < A(w,j+1) \le A(i,j+1)$ for all $i \ge w$.

Now we need to recursively search about half of the remaining elements, considering the two rectangular blocks $A(1,j+1)..A(w-1,M)$ and $A(w+1,1)..A(M,j)$ in turn.  There are $M$ calls to check a block, but successive calls receive exponentially smaller blocks to work with.  Amortising the work across calls, the total work is $O(\sqrt{N})$ steps as each leaf of the search tree only does a constant amount of work.  More precisely this relates to solving the recurrence $f(n) = 2f(n/4) + \log n$ for which $f(n) \in O(\sqrt{n})$.

So overall, $O(\sqrt{N})$ steps suffice.

Note that the overlap of adjacent subarrays may be of use when extending to increasing-length subarrays, or in improving the algorithm, but isn't used here.

As far as I can tell, $\Omega(\sqrt{N})$ is also a lower bound.  A handwaving argument is that in the worst case, when all the values are close except for a single missing value, that value could be hidden in any of the rows and each row must be examined at least once.


Find 8 numbers whose sum is closest to a defined value

Dynamic programming

One approach is to use dynamic programming.  If you have $n$ numbers ($n$ rows in the file), and each number is in the range $1..m$, then the obvious dynamic programming algorithm has running time about $8mn$.  For your parameter size, this might be adequate.

In particular, let $A[1..n]$ be an array of your $n$ numbers.  Define $T[x,i,j] = 1$ if there is a way to write $x$ as a sum of $j$ numbers from among $A[1..i]$, or 0 if not.  Now we have the relation

$$T[x,i,j] = T[x,i-1,j] \lor T[x-A[i],i-1,j-1]$$

(with the convention that $T[x,i,j]$ always evaluates to 0 if $x$ is negative).  Consequently, you can compute all of the $T[x,i,j]$ values iteratively.  There are $8mn$ values to compute, so this takes $8mn$ time.

Once you have filled in the $T$ table, now you can answer any query quickly.  Suppose you want to find the closest number to $q$ that can be written as a sum of 8 numbers.  Then you should scan $T[q,n,8]$, $T[q+1,n,8]$, $T[q-1,n,8]$, $T[q+2,n,8]$, $T[q-2,n,8]$, etc., until you find the first entry that is one.  This takes at most $m$ iterations.

In total, the running time is $O(mn)$, where the constant hidden by the big-O notation is small.  The space required is $O(mn)$ as well, but this can be reduced to $O(m)$ if you fill in the $T$ table in the right order and discard entries once they are no longer needed.

Two-way merge

There's an alternative algorithm that will probably be significantly faster for your specific problem.  The basic idea is to first find an algorithm that works for sums of 2 numbers, then apply that repeatedly.

Let $S$ be a set of numbers.  Define $S \bowtie S$ to be the set

$$S \bowtie S = \{s+t : s, t \in T\}.$$

In other words, $S \bowtie S$ is the set of all possible sums of two values from $S$.  In our case, we're going to represent $S$ as a sorted list of numbers.

It turns out you can compute $S \bowtie S$ from $S$, using a FFT-based convolution procedure.  Let $N$ be the smallest power of two that is larger than $2m$.  Define a $N$-vector $v$ whose $i$th coordinate is 1 if $i\in S$, or 0 otherwise.  Compute $v \otimes v$, the convolution of $v$ with itself.  It turns out that $v \otimes v$ is the $N$-vector for $S \bowtie S$, so you can recover $S \bowtie S$ from $v \otimes v$.  Also, you can compute the convolution $v \otimes v$ using a discrete FFT over the $N$th complex roots of unity: you take the FFT of $v$, square every entry, then take the inverse FFT.   The running time of the FFT is $O(N \lg N)$.  Since $N=O(m)$, it follows that the running time of this procedure is $O(m \lg m)$.

Now we repeat this recursively three times.  In other words, we let $S = $ the set of numbers in the original file, compute $T = S \bowtie S$ (the set of 2-way sums), compute $U = T \bowtie T$ (the set of 4-way sums), and then compute $V = U \bowtie U$ (the set of 8-way sums).  This gives us the set of all numbers that can be represented as a 8-way sum.

If you like, a more elegant way to compute the set of 8-way sums is as follows: let $N$ be the smallest power of two that is larger than $8m$, form a $N$-vector $v$ where $v_i=1$ if and only if $i$ is part of the original file, take the discrete FFT of $v$ (over $N$th complex roots of unity), raise each entry to the 8th power, then take the inverse FFT.  This gives you a $N$-vector that has a 1 in its $i$th coordinate if and only if $i$ is an attainable 8-way sum.

Finally, given a query $q$, we can quickly look it up in $V$ (using binary search, say) and find the nearest number to $q$ that's in $V$.

The total running time will be $O(m \lg m)$, and the total space will be $O(m)$.  For your parameter settings, this should be extremely fast, given that $m$ is no larger than 10,000.  However, the implementation complexity is much higher, since you need to implement a FFT, worry about round-off error and precision for complex numbers, and so on.


How is the complexity/size of a problem (for instance SAT) determined?

The complexity of SAT relates to the number of arguments to the Boolean function (i.e. the "distinct literals" in the expression), not the number of terms in a particular normal form.

The complexity of an algorithm which solves SAT is related to the size of the input that you give it. So if the input is the Unicode string (x1∨x2∨¬x3)∧(x1¬∨x2¬∨x4)∧(x2∨x3∨x5), then the size of that is the number of Unicode codepoints (or bytes or bits used to encode those codepoints).

The subject of SAT is the function, not the representation of the function. The complexity class (i.e. the complexity of any solver which is optimal for its computer) is the same whether functions are written as product-of-sums or a sum-of-products. This complexity varies with the number of arguments to the function.

The input to a SAT solver is the representation of the function. Your example is in the product-of-sums normal form, which is a common way to express SAT problems. This is not a coincidence — SAT is solved mindlessly if you instead give it a sum-of-products expression! The brute-force method of solving SAT is to enumerate the sum-of-products, where each term either contradicts itself (b ¬b) or represents a satisfied piece of the function's domain. This simple approach doesn't trivialize SAT because going from one normal form to the other causes a combinatorial explosion. The size of the domain of a function of $n$ Boolean arguments is $2^n$.

Thus, feeding a gigantic problem description into a simple algorithm may have the same computational (and space) complexity as feeding a simple but equivalent description into a sophisticated algorithm. For brevity, we tend to prefer to imagine the description to be simple and the algorithm to be complicated.


Prove that the next multiple of 4 is obtained using the next formula

Suppose that $s = 4a+b$, where $0 \leq b < 4$; by assumption, $b \neq 0$. If the numbers are $n$ bit long, then $\lnot s = 2^n - s = 4(2^{n-2}-a) + (4-b)$. Since $b \neq 0$, the last two bits of $\lnot s$ will be $4-b \in \{1,2,3\}$. Therefore $(\lnot s) \land (11)_2 = 4-b$. Adding this to $s$, we get $4a+b+4-b = 4(a+1)$.


Is the intersection of infinitely many recursive sets recursive?

For each $i\in \mathbb{N}$, take $S_i = \mathbb{N}\setminus \{i\}$. You can now build any set you want as $X = \bigcap_{i\notin X}S_i$.

Similarly, an easier proof that a union of recursive sets can be anything at all is to let $T_i=\{i\}$ and now any set $X$ is $X = \bigcup_{i\in X}T_i$.


What use are groups, monoids, and rings in database computations?

The main answer is that by exploiting semi-group structure, we can build systems that parallelize correctly without knowing the underlying operation (the user is promising associativity).

By using Monoids, we can take advantage of sparsity (we deal with a lot of sparse matrices, where almost all values are a zero in some Monoid).

By using Rings, we can do matrix multiplication over things other than numbers (which on occasion we have done).

The algebird project itself (as well as the issue history) pretty clearly explains what is going on here: we are building a lot of algorithms for aggregation of large data sets, and leveraging the structure of the operations gives us a win on the systems side (which is usually the pain point when trying to productionize algorithms on 1000s of nodes).

Solve the systems problems once for any Semigroup/Monoid/Group/Ring, and then you can plug in any algorithm without having to think about Memcache, Hadoop, Storm, etc...


How can i design this function using only NAND and XOR gates?

I have assumed that only 2 input NAND gates are available.

For $\overline {AB}*\overline {CD}$

Take A and B as input and feed them to a NAND gate. U will get $\overline {AB}$.
Similarly u can get $\overline {CD}$.

Now feed $\overline {AB}$ and $\overline {CD}$ as input to another NAND gate . U will get AB + CD using demorgan law.

For ABCD take $\overline {AB}$ and complement it using a NAND gate to get AB.
Take $\overline {CD}$ and complement it to get CD. Now feed AB and CD to NAND gate. You will get $\overline {ABCD}$.

Now feed (AB+CD) and (ABCD)' to NAND gate. U will get $\overline{(AB+CD)\overline{(ABCD})}$.Apply demorgan law. U have ur answer.

The trick is to express the function as a sum of products which u already have. Now derive the complement of each product term. When all product terms have been derived then feed then to a NAND gate. This final NAND gate will complement the already complemented product terms and add them thus giving the desired answer.


Find all intervals that are contained in a query interval

You were too quick to reject interval trees and segment trees.  You can search an segment tree for all intervals that are contained in a query interval $q=[\ell_q,u_q]$, using a straightforward recursive procedure:

Any node $v$ of a segment tree has a corresponding interval $\text{Int}(v)$.  Do a recursive search of the tree, except that you only visit nodes $v$ such that $\text{Int}(v)$ overlaps $q$.  Each such node stores a list of intervals from $S$.  For each such node, if $\text{Int}(v)$ is contained in $q$, check all of the intervals stored with $v$ is contained in $q$.

That's all you need to do.  Just because a data structure is designed to support one kind of operation doesn't mean it's unable to support other operations, too.

That said, one challenge with segment trees is that it's not clear how to update them dynamically (to add new intervals).

I think similar ideas can also be applied to interval trees, too.  The root of an interval tree has a value $x$.  Now do a case analysis:

If $x$ is to the left of $q$ (i.e., $x < \ell_q$), then you only need to look at intervals that are completely to the right of $x$, so you just recurse to the right child of the root.
If $x$ is to the right of $q$ (i.e., $x > u_q$), then you only need to look at intervals that are completely to the left of $x$, so you just recurse to the left child of the root.
If $x \in q$ (i.e., $\ell_q \le x \le u_q$), then you recurse to the left child and output all matches found there; recurse to the right child and output all matches found there; and finally, find all intervals that contain $x$ and are contained in $q$.  The latter can be done by scanning the list of intervals associated with the root (which is a list of intervals that contain $x$), to see which meet your condition.

I suspect there might be other approaches as well.  For instance, you could build a $k$-d tree, with $k=2$ dimensions, where the interval $[\ell,u]$ is represented as the point $(\ell,u)$.  Then given a query interval $q=[\ell_q,u_q]$, you want to do a range search to find all points $(x,y)$ such that $x \ge \ell_q$ and $y \le u_q$.  That should be a straightforward recursive search in a $k$-d tree.  Or, you could build a quadtree.


What do CPUs do when a program aborts with an error?

CPUs don't have a notion of “program aborting”. Some CPUs have features that help operating system manage separate programs, but the concept of separate programs exists primarily at the level of the operating system.

The specification of the CPU specifies what happens for each instruction for all data. For example, it might specify that div r1, r2, r3 divides the integer value stored in r2 by the integer value stored in r3, stores the result into r1, and then moves the instruction pointer to the next instruction. It might furthermore specify that in case r2 is zero, the CPU executes a trap — this is what most CPUs do on a division by zero. Typically, on a trap:

The CPU saves the current value of the program counter into a register assigned to this purpose.
The CPU sets the reason for the trap (a constant that means “division by zero”) into a register assigned to this purpose.
The CPU reads an address from somewhere and sets the program counter to this address. This address is called the trap vector. This “somewhere” is usually either a register, or a memory location which is calculated from a value in a register.
The CPU switches to a privileged mode (e.g. kernel mode, ring 0).

(Note that details vary from CPU to CPU, I am only describing typical behavior.) Traps are very similar to interrupts; the difference is that a trap is due to an event happening in the CPU whereas interrupts are triggered by external events.

The operating system decides what happens when a trap occurs by providing some code and setting the trap vector to its address. The trap handling code typically analyses the reason for the trap and decides what to do, which may or may not include terminating the current process. For example, some operating systems allow application code to react to trap (e.g. with signal handlers on Unix) — then the kernel's trap handler looks up the address of the application trap handler in some internal kernel data structure and jumps to that after setting the processor in the appropriate mode.

An example of a trap which often doesn't result in the death of the application is a memory fault, when the application tries to access a virtual address which is not mapped in the MMU. On operating systems that implement swap, the trap handler looks up the virtual address to see if there is actually data that is mapped there in the application but that is currently swapped out to disk. If that is the case, the trap handler loads the content of the page from disk and updates its memory management data structures. Then it jumps back to the application, arranging to cause the application to execute the memory access instruction again. This time the instruction will succeed, and the application is unaware that the first attempt fails (except via some indirect means such as timing).

If the trap handler decides to terminate the program, it does so in pretty much the same way as if the program had called the exit system call: it frees the resources allocated to the process, then invokes the scheduler to execute whatever other threads have something to do.


How does the function to curry and uncurrying another function work?

The meaning of curry can be easier to be seen when the type signature is written as

curry :: ((a, b) -> c) -> (a -> b -> c)

that is, a function taking a single parameter of type (a, b) and yielding a result of type c is turned into a function taking two separate values of types a and b yielding the same result type c.

We might define curry for this signature like this:

curry f = g

where f :: ((a, b) -> c) and g :: (a -> b -> c).

f is passed by the user, but how do we get g? We know g is a function taking two parameters and yielding a result type, so it must structurally look like \x -> \y -> z, where x :: a, y :: b, and z :: c (\v -> e is the syntax for lambda-expressions in Haskell). We now have to find a way to get the result z from x and y such that the types work out correctly.

As both result types c must be the same, the only way to get z is to use f and apply it to a value of type (a, b). So we know z = f (?, ?) where (?, ?) must have type (a, b). Where do we get values of these types from? Again, as the types must match exactly, the only option is to use x and y here. We get

curry f = g
    where g = \x -> \y -> f (x, y)

This would be a proper implementation for curry. One that is easier to read is to inline g:

curry f = \x -> \y -> f (x, y)

As Haskell allows us to define functions with multiple parameters, we can resolve the lambda-expression and simplify this to

curry f x y = f (x, y)

which is (beside different variable names) the same implementation as in your question.

For uncurry the procedure is similar (note that you had missing parentheses in the type signature for uncurry in your original question which lead to a different type).

From

uncurry :: (a -> b -> c) -> ((a, b) -> c)

we conclude

uncurry f = g
    where g = \(x, y) -> z

with f :: (a -> b -> c), g :: (a, b) -> c, x :: a, y :: b and z :: c. Following the types, z can only be defined by z = f x y. From that we get

uncurry f = g
    where g = \(x, y) -> f x y

and after inlining g and removing the lambda

uncurry f (x, y) = f x y


Compute the mode of an array concurrently

Since you asked for a hint:

   Partition the array.

Think about that for a while.  If you need more of a hint:

   If you partitioned the array into $p$ partitions and assigned each partition to a single processor, could you compute the mode of the numbers within a particular partition efficiently?  Would that help get you closer to a solution to what you want to achieve?


circle packing algorithm used by Percolator

Since I created this I probably can explain it best ;-):

the first step is to calculate an image segmentation which will combine small areas of similar colors into bigger chunks. The tolerance values of that segmentation will influence how big the biggest circles can become (higher tolerance => bigger areas => bigger circles)
You proceed by processing each of the found areas individually:
calculate an euclidean distance map for the area. This map will tell for every pixel the distance to the nearest edge. Find the maximum value in that map. This is the pixel that has the furthest distance from an edge. Conveniently that distance will be the radius of the biggest circle that you can fit into that area. Add that circle (center position + radius) to a list. Now you subtract that circle from the area - subtract in this case means that if the original area is all white pixels surrounded by a black border you simply draw a black circle over it. Recalculate the distance map for the remaining white area pixels repeat the above process until there are no more distances bigger than some chosen threshold (the smallest radius you want to display).
the last part is to calculate the pie charts for all the circles you have collected. In order to do that you accumulate all the pixel colors of the original image that are lying under a circle and calculate a color quantization for them. In the Mona Lisa example all the colors are reduced to the 7 most representative. In order to calculate the pie ratios you simply count for each of the 7 representative colors how many of the original colors are their nearest neighbors. The only thing left to do is to draw a pie chart using the ratios and colors at the stored circle position.


Term clarification: Establishing a domination

We say that $A$ dominates $B$ if $A \geq B$ (or, more generally, if $A \succeq B$ in some partial order). To establish a domination means to establish that something dominates something else. I'll let you figure out which domination is meant in your context.


CFG problem solved with PDA - looking for alternative solution

First assume $n\ge m$.
Then we can take $i=n-m$ and we have $i+k =l$, so strings are of the form

$ a^i a^m b^m c^k d^k d^i$.

You can do a CFG for that.

Then consider $n\le m$.


use Binary Index tree, segment tree for the range-value-sum it is the easiest way to do so and for range-2-max use a linear search to keep track of two maximums.For range-2-max you can also use min-heap(this can help you to find range-N-max).

BinaryIndexTree(fenwick tree) has many online tutorials read them and see this visualizer for understanding it.
http://visualgo.net/bit.html

Hope this clears or solve your problem.


Can weighted problem have polynomial complexity if non-weighted problem is NP-complete: hitting set

The unweighted case is a special case of the weighted case, corresponding to all weights being equal. Therefore the unweighted case is easier or as hard as the weighted case. The reason is that given an algorithm for the weighted case, you can use it to solve an unweighted problem by endowing the relevant objects with unit weight.


The  assertion is not correct in general, as you have discovered.

However, here is what is correct:  $\gcd(x+y,n)$ is a factor  of $n$, and $\gcd(x-y,n)$ is a factor  of $n$.  Why?  Well, this is trivial: $\gcd(\text{anything},n)$ is always a  factor of $n$.  Of course, the gcd might be 1, but that's still a divisor of $n$.

We can say even more.   If we let $r=\gcd(x+y,n)$ and $s=\gcd(x-y,n)$, then their product is a multiple of $n$: i.e., $rs$ is a multiple of $n$.  Thus, you can replace $s$ with $s'=n/r$ and now $r,s'$ will have the property you want: both $r$ and $s'$ are divisors of  $n$, and $rs'=n$.  (Why is $rs$ a multiple of $n$? Because if  $x^2  \equiv y^2 \pmod n$, then it follows that $x^2 - y^2 \equiv 0 \pmod n$.  Now $x^2-y^2 = (x-y)(x+y)$, so it follows that $n$ divides $(x-y)(x+y)$, i.e., $n$ divides $rs$.)

This makes this method useful for factoring.  However, beware that there is no guarantee that get a non-trivial factor out of this.  For instance, consider $n=15$.   Then if $x=8$ and $y=7$, we have $x^2 \equiv y^2 \equiv 4 \pmod n$, but $\gcd(x-y,n)=1 $ and $\gcd(x+y,n)=15$, so we obtain that $15 = 1 \times 15$ -- true, but not very useful for factoring $n$.  What we can say is that if $n$  is the product of two large primes, and if you can randomly sample  two $x,y$ such that $x^2 \equiv y^2 \pmod n$, then with probability about $1/2$, $\gcd(x-y,n)$ and $\gcd(x+y,n)$ will give you the full factorization of $n$.

If you want us to comment on an assertion it helps to give a reference for it.  My guess would be that there is additional context you are not  providing, such as the assumption that $n$ is a product of two primes.


In the Sedgewick-Bentley talk "QUICKSORT IS OPTIMAL" they give an (informal) proof that Quicksorts average case is optimal.

So the average case lower bound for sorting is $\Omega(n\lg{n})$.


You cannot prove it in "vanilla" Coq, because it is based on intuitionistic logic:

  From a proof-theoretic perspective, intuitionistic logic is a restriction of classical logic in which the law of excluded middle and double negation elimination are not valid logical rules.

There are several ways you can deal with a situation like this.

Introduce the law of excluded middle as an axiom:

Axiom excluded_middle : forall P:Prop, P \/ ~ P.

There is no more need to prove anything after this point.
Introduce some axiom equivalent to the law of excluded middle and prove their equivalence. Here is just a few examples.

Double negation elimination is one such axiom:

Axiom dne : forall P:Prop, ~~P -> P.

Peirce's law is another example:

Axiom peirce : forall P Q:Prop, ((P -> Q) -> P) -> P.

Or use one of the De Morgan's laws:

Axiom de_morgan_and : forall P Q:Prop, ~(~P /\ ~Q) -> P \/ Q.


Algorithms: Determining Asymptotic Notation from a given execution time

Assuming that $f(n)$ and $g(n)$ are asymptotically positive (as it is usually the case) you can use the following sufficient condition to determine the asymptotic relation of $f(n)$ and $g(n)$.

If $\lim_{n \to \infty} \frac{f(n)}{g(n)}$ exists and is $c \in \mathbb{R_0^+} \cup \{+\infty\}$, then:

If $c< +\infty$ then $f(n) = O(g(n))$ (and $g(n) = \Omega(f(n))$). In particular:

If $0 < c < +\infty$ then $f(n) = \Theta(g(n))$ (and $g(n) = \Theta(f(n))$).
If $c=0$ then $f(n) = o(g(n))$ (and $g(n) = \omega(f(n))$).

If $c > 0$ then $f(n) = \Omega(n))$ (and $g(n) = O(f(n))$). In particular:

If $0 < c < +\infty$ then $f(n) = \Theta(g(n))$ (and $g(n) = \Theta(f(n))$).
If $c = +\infty$ then $f(n) = \omega(g(n))$ (and $g(n) = o(f(n))$).

Moreover, in computing the limit, you can replace  $f(n)$ with a function $h(n)$ such that $h(n) \sim f(n)$ (see, e.g., this page on Wikipedia). The same holds for $g(n)$.
For polynomials this amounts to taking the monomial of highest degree. Moreover, since scaling $c$ by a (positive) constant does not change the asymptotic relation between $f(n)$ and $g(n)$, you can also drop any multiplicative constant (which will always be positive since $f(n)$ and $g(n)$ are asymptotically positive).

For example, instead of comparing $f(n) = 3n^2 + 2n +50$ with $g(n) = 5n^5 + 4n^3 - 2^{10}$, you can compare $x^2$ with $x^5$ instead. This immediately shows that $c$ exists and is $0$, therefore $f(n) = O(g(n))$
 and, in particular, $f(n) = o(g(n))$.

While the above rules will probably work for the vast majority of the functions you will encounter, they can't always be used. Consider, for example, $f(n) = 2 + \sin(n)$ and $g(n) = 1$. Here $f(n) = \Theta(g(n))$ but $\lim_{n \to \infty} \frac{f(n)}{g(n)}$ does not exist.


Finding a small element in a changing array

Here is an amortized solution to the problem in which updates may only increase values:

Maintain:

A linked list of some of the items less than the median
A linked list of all items greater than the median (and some items less than it)

To return a small item, return an item from #1.

To update an item greater than the median, change its key in #2.

To update an item less than the median, remove it from #1 and add it to #2. If this makes #1 empty, rebuild both lists using a linear-time partitioning algorithm.

Update takes amortized constant time, using physicists argument and a potential function of twice the size of list #2 or the bankers argument and two coins on each item in list #2.

Here is an amortized solution in which updates may increase or decrease values:

To start, build three linked lists of size $n/3$. All items in list #1 should be less than all items in list #2, and all items in list #2 should be less than all items in list #3. One more list will be maintained; I'll call it the junkyard.

To change the key of an item:

When increasing the key of an item in #1, move it to the junkyard.
When decreasing the key of an item in #3, move it to the junkyard.
When changing the key of an item from #2, move it to the junkyard.
When changing any other key, do not remove it from or add it to any list.

The junkyard is called "full" when it has size $n/6$. Until then, all items in #1 are less than the median. Once the junkyard is full, rebuild.

The amortization argument works the same, but now the potential is six times the size of the junkyard, or, equivalently, each move to the junkyard requires 6 coins.

Here is a complete deamortized solution:

All operations can be done in constant time using a technique called incremental global rebuilding.

Maintain three copies of the second version of the structure designed above, along with three pointers to them, called PAST, PRESENT, and FUTURE. If a structure is pointed to by A and we want to point to it from B, we call that "renaming A to B".

We will proceed in four stages. After stage 4, we will rename PRESENT to PAST, rename FUTURE to PRESENT, and point the FUTURE pointer at empty space (or the null pointer). Then we will start with stage 1 all over again.

Each stage lasts $n/36$ updates. Queries are always answered from PRESENT

Stage 1:

When this stage starts:

We will never query the structure pointed to by PAST again. It is dead, so we don't really care about its contents.
PRESENT's junkyard has at most $2n/36$ items in it.
FUTURE is just a null pointer.

During this stage, updates are performed on PRESENT as usual, but for each update, we perform 36 steps of destructing PAST. As a result, by the end of this stage, $n$ destructing steps have been performed on PAST and it is empty, using no memory.

At the end of this stage, PRESENT's junkyard might be as large as $3n/36$.

Stage 2:

When this stage starts, we allocate an empty linked list that we call FUTURE.

During this stage, for each update to PRESENT we also copy 36 items into FUTURE. Also, for each item that is updated, we update its key in FUTURE if it already has been copied. Note that the update in FUTURE doesn't touch any junkyards, since FUTURE is just a linked list at this point.

At the end of this stage, PRESENT's junkyard might be as large as $4n/36$, and the items in PRESENT and FUTURE are identical.

Stage 3:

When this stage starts, we allocate an empty queue that can hold representations of update operations (for instance, as a pair containing a pointer to the item and its new value).

During this stage, for each update to PRESENT we also enqueue a representation of that update into the update queue, and we perform 36 steps of the initialization of FUTURE into the structure described in section 2 above. As a result, by the end of this stage, $n$ initialization steps have been performed on FUTURE and it is completely initialized, with a junkyard size of 0. However, because updates were queued, it does not hold the same data as PRESENT, which we will have to fix in Stage 4.

At the end of this stage, PRESENT's junkyard might be as large as $5n/36$ and the queue has size $n/36$.

Stage 4:

During this stage, for each update to PRESENT we also enqueue a representation of that update into the update queue and dequeue two operations to play back in FUTURE. During this stage the queue grows by $n/36$ operations and shrinks by $2n/36$, leaving it empty at the end of the stage.

At the end of this stage, PRESENT's junkyard might be as large as $6n/36$ and FUTURE's junkyard might be as large as $2n/36$. We now switch names as described above, renaming PRESENT to PAST, FUTURE to PRESENT, and pointing FUTURE at the null pointer. The prerequisites for Stage 1 are now met, and at no point did PRESENT have more than $n/6$ items in its junkyard.


Ordering of operations in a DAG of git commits

What exactly is an operation in your model?  If two concurrent operations commute, then any topological sort of your DAG will give the same result (cf. Strong Eventual Consistency).  If two concurrent operations are independent of one another it's likely they commute (or can be made to commute); otherwise, if there is a deterministic way to prioritise them, then do that (as in CRDTs).  I can't be more specific without understanding what an operation is.