Is a system of equations derived from mutually recursive ADTs always uniquely solvable? After looking at Can a computer determine whether a mathematical statement is true or not? for a while, I worry we may be into incompleteness/halting problem territory with this question, so an answer on that front, while disappointing, would also be acceptable
I've been interested by ADT equations since I read the linked post, and I've started thinking about them in the context of Coq's inductive types (which essentially permit the usual sum, product, and unitary type constructors).
In particular, I've been considering the correspondence between type definitions and the number of elements inhabiting the type. In particular, solving the type's equation yields the number of elements inhabiting the type, and it seems reasonable to me that, for any so-definded type, this number is at most $\aleph_0$. That is, for any ADT or inductively defined type, the number of inhabitants is at most countably infinite. I'm thinking about how to formulate or prove such a statement in Coq, and in the meantime had some questions. (It seems further natural that such types and numbers are in one-to-one correspondence up to isomorphism between types of the same cardinality, but that might be a step too far).
It seems easy enough to show a type definition containing exactly $n$ elements for any natural $n$, so that gives one direction of a theorem connecting the two. Going the other way, though, seems more difficult, and in either case it woudl be natural to me to rely on a function $C$ from types $\tau$ to numbers (what class of numbers?) $n$ where $C(\tau) = n$ means there are $n$ elements inhabiting the type.
The trouble is, this function doesn't seem computable. If we take the naturals as
Inductive nat: Type :=
  | O
  | S: nat -> nat.

such a function would be required to produce an infinity (namely $\aleph_0$), and thus I don't think Coq could accept such a definition. (Worse, how would the definition know when to return 0?)
So I've come back around to equations. I wondered if I could formulate this idea by constructing for each type $\tau$ (possibly parameterized on other types $\alpha, \beta, \dots$) a polynomial (is this the right term, since it may really be a recurrence?) in the same class of numbers $\tau(\alpha, \beta, \dots) = P(\tau, \alpha, \beta, \dots)$ and proving that all such equations have a unique solution (and herein lies my concern above: would this even be provable?).
This brings me to my main question: I believe that the above statement is true in the absence of mutually recursive types. But mutually recursive types suggest systems of equations, rather than a single equation, and it is well-known that systems do not always have a solution.
But these systems would have some (possibly unique) properties:

they would be polynomial in this class of numbers
each would have the form $\tau_i = P(\tau_1, \dots, \tau_n)$
there would be exactly $n$ equations for $n$ mutually recursive types

Is it possible to prove (or already proven) that such systems are always uniquely solvable in the naturals? I suspect it might be easier to formulate in Linear algebra, but I'm a bit rusty on what it takes to do that here.

The initial assumption about such types having at most countably many elements is false. We can use inductive types to define a non-countable type, namely the countably branching trees:
(* Countably branching trees. *)
Inductive Tree : Type :=
  | Leaf : Tree
  | Node : (nat -> Tree) -> Tree.

Lemma nocycle (t : Tree) : forall (f : nat -> Tree), t = Node f -> forall a, f a <> t.
Proof.
  induction t as [? | f H].
  - easy.
  - intros g E n.
    injection E.
    intro E'; destruct E'.
    intro gN.
    now elim (H n f gN n).
Qed.

Corollary uncountable_Tree :
  ~ exists (f : nat -> Tree), forall t : Tree, exists n, f n = t.
Proof.
  intros [f H].
  destruct (H (Node f)) as [n ?].
  now pose (nocycle (Node f) f eq_refl n).
Qed.

In any case, counting elements of types is a tricky business. Consider the following inductive type:
Inductive cow (P : Prop) : Type :=
  | moo : P -> cow P.

Consider any propostion Q : Prop. If cow Q has zero elements then Q is false, and if it has an element then Q is true. So if we could count the elements of cow, we could also tell whether it has zero elements, and would be able to decide an arbitrary proposition, which would give us excluded middle.
You need to restrict the inductive types quite severaly to obtain a small enough family of them whose sizes can actually be counted.


Alternative algorithm for minimum spanning tree construction Let $\textit{G(V,E)}$ be an undirected connected graph with distinct costs on its
  edges. Initialize $\textit{T}$ to be any spanning tree of $\textit{G}$. Consider an
  algorithm which replaces an edge $\textit{e}$ in $\textit{T}$ by an edge $\textit{e'}$ not in $\textit{T}$, if $\textit{e' < e}$ and replacing it still maintains $\textit{T}$ to be a spanning tree.

I want to prove that this algorithm results in a minimum cost spanning tree of $\textit{G}$.

I am trying to prove this by contradiction - consider that $
\textit{T}$ is the tree which we obtain when the algorithm ends. We assume that there exists $\textit{T'}$ such that $\textit{W(T') < W(T)}$.

Attempt: I tried considering an edge $\textit{e}$ to be the lowest cost edge which is in $\textit{T'}$ but not in $\textit{T}$ (there is at least one since both are different spanning trees). We add $\textit{e}$ to $\textit{T}$ - thus, creating a cycle (since $\textit{T}$ was a spanning tree). There are two possible cases:

$\textit{e}$ is smaller than all the edges of the cycle it induced. But, in this case, the algorithm would not have stopped at $\textit{T}$, it would have replaced one of the edges of the cycle by $\textit{e}$.
$\textit{e}$ is larger than all the edges of the cycle it induced. I suppose this should contradict the minimality of $\textit{T'}$.

Am I anywhere on the right track? I don't know if considering the cycle is the way to do this.

It is not immediate to see whether OP’s approach can be adapted easily to a full proof.

Here is an answer to the same question but phrased differently, a local minimum in the graph of spanning trees is a (global) minimum spanning tree.

I will present  another proof, which is more flexible and probably easier to understand.

Let $G$ be an undirected connected (finite) graph with distinct costs on its edges, as in the original question. Consider the delete-heaviest-edge algorithm on $G$, which removes the heaviest edge in a cycle until no cycle remains. Just to be clearer, let me call the remaining edges at the end of the algorithm $H$. Let us show that $H$ is the minimum cost spanning tree (MST) of $G$.

$H$ is a spanning tree of $G$ because of the following.

$H$ is connected,  since $G$ is connected and all we have done is breaking cycles.
$H$ is has no cycle since the algorithm ends only if there is no cycle.
$H$ has all vertices of $G$ since no vertex of $G$ has ever been deleted.

Because of the the cycle property, any edge in any minimal cost spanning tree (MST) of $G$ is never deleted. So all edges of any MST of $G$ remain in $H$. However, any spanning tree of $G$ has the same number of edges, so $H$ must be the unique MST of $G$. (Yes, we have also proved that there is only one MST of $G$, thanks to the distinctness of the costs).

So we have proved that the delete-heaviest-edge algorithm finds the MST. The flexibility of that algorithm is that in each step we can choose any particular cycle.

Following the OP, let $T$ be the spanning tree which we obtain at the end of OP's algorithm. Initialize $G'$ to be a copy of $G$ and $T'$ is the spanning tree of $G'$ that corresponds to $T$. Let $e'$ be an edge in $G'$ but not in $T'$. If we add $e'$ to $T'$, we will create a cycle since $T'$ is spanning. Note that $e'$ must be the unique heaviest edge in that cycle; otherwise, we can substitute $e'$ for that unique heaviest edge, which is in $T'$, to get a lighter spanning tree, which means the OP's algorithm must not end with $T$, a contradiction. Let us run the delete-heaviest-edge algorithm on $G'$ in the following way. We choose that cycle and delete $e'$ from $G'$. Repeat until all edges in $G'$ but not in $T'$ are deleted. What remains is exactly $T'$. Since $T'$ has no cycle, we have actually run the delete-heaviest-edge algorithm to the end. As we have proved, $T'$ is the MST of $G'$. That is, $T$ is the MST of $G$.


solving a number theoretical problem In mathematics, the greatest common divisor (gcd), also known as the greatest common factor (gcf), highest common factor (hcf), or greatest common measure (gcm), of two or more integers (at least one of which is not zero), is the largest positive integer that divides the numbers without a remainder. For example, the GCD of 8 and 12 is 4.

Given an integer N. Now Find how many GCD(A,B)=B Where 1≤A≤B≤N
For example,for N=3 the result will be 5.It can be found in the following way.

GCD(1,1)=1 OK

GCD(1,2)=1

GCD(1,3)=1

GCD(2,1)=1 OK

GCD(2,2)=2 OK

GCD(2,3)=2

GCD(3,1)=1 OK

GCD(3,2)=1

GCD(3,3)=3 OK

Here we get 5 combination where GCD(A,B)=B
But how can I calculate it for 1≤N≤10^9 efficiently?

Hint: $\mathrm{gcd}(a,b) = b$ iff $b|a$. Since you're only looking for pairs in which $a \leq b$, this forces $a = b$.


Find the shortest sub-tree with node deletion Let $T=(V,E)$ be a tree rooted in $r$ and let $L$ denotes the set of leaves of $T$. For a given $v \in V$, let $C(v)$ be the out-neighors of $v$ i.e. its children in $T$ and $p(v)$ be its in-neighbor i.e. its predecessor in $T$. We have a metric $d : V \times V \rightarrow \mathbb{R}^+$ (respecting the triangular inequality). The length of the tree is then $\sum_{u \in V} d(u,p(u))$.

For a subset of internal non-root nodes $V' \in V \setminus (L \cup \{r\})$,  the rooted "sub-tree" $T'$ corresponds to the tree we get after removing each $v\in V'$ and connecting its parent $p(v)$ to all $C(v)$. An example:

My problem is to find the subset of internal $V'$ to remove such that the sub-tree $T'$ has the minimum length. Below are some observations I made (maybe the problem is well-known but if it's not then they may provide some insight). Any remark/reference is most welcome!

Steiner tree related problem?

My first thought was that this problem is a special case of the Steiner tree problem. We can construct a graph $G=(V,A,d)$ with $A = \{(u,v) \in V \times V : u  \text{ is an ancestor of } v \text{ in } T\}$, edge length $d$ and $L$ as the set of terminal nodes. However a Steiner tree of $G$ may correspond to solutions that are impossible to get via node removal on $T$. Indeed, node removal preserves the siblings relations existing in $T$. This may not the the case for Steiner trees in G.

That being said I would be interested to know the complexity of the Steiner tree problem for graphs constructed like G. I suspect the problem to still be NP-hard.  Note that the approximate solution obtained by taking a minimum spanning tree according to shortest-paths distances would be the star graph connecting the terminal nodes to $r$ (since $d$ respects the triangular inequality).

Iterative/Recursive solution or approximation?

Assuming $T$ is of height $2$, we only need to check if each internal node $u$ respects the inequality

\begin{equation}
\sum_{l \in C(u)} d(l,r) > d(u,r) + \sum_{l \in C(u)} d(l,u) \text{        (Ineq. 1)}
\end{equation}

and add it to $V'$ if it does not. In the general case, a possible approach is therefore to iteratively remove the nodes that do not respect the Ineq. 1. However, such "local" approach may lead to the best solution. For example assume the distances $d$ for the example in Figure 1 are (sorry for the formatting):

   d(.,.) | r | a | b | l_(1,2,3) | l_4 | l_5 |
   ____________________________________________
   r      | 0 | 2 | 2 | 1         | 3   |   1 |
   a      |   | 0 | 1 | 2         | 1   |     |
   b      |   |   | 0 | 1         |     |     |

Here Ineq. 1 is respected for both internal node $a$ and $b$. However, the shortest tree is the one obtained after the removal of both nodes.

I therefore tried to apply Ineq. 1 in a recursive fashion. I check it not only for the direct parent but for all the ancestors. The procedure is as follow:

Procedure ShortestSubTree$(T,u,d)$:

For $v \in C(u) \setminus L$ do

ShortestSubTree$(T,v,d)$

$a \leftarrow p(u)$
While $a$ is defined do

If $\sum_{v \in C(u)} d(a,v) \leq d(u,a) + \sum_{v \in C(u)} d(u,v)$ then

remove $u$ from $T$
stop

$a \leftarrow p(a)$

However it seems that ShortestSubTree removes too many nodes. In some experiment, the "iterative" approach can produce shorter sub-trees.

This can be solved with dynamic programming.

Define $A[u,v]$ as follows.  Consider all trees obtainable by starting with the subtree rooted at $v$, removing some of the nodes, and making $u$ be the parent of all of the nodes with no parent.  (Or, to put it another way: all of these trees are a subset of the subtree rooted at $u$; they contain $u$ as their root; and every node in them other than $u$ is either $v$ or a descendant of $v$.)  Then $A[u,v]$ is defined to be the length of the minimal-length tree of this sort.

Notice that we have a recursive relationship for $A[u,v]$.  In particular, if $w_1,\dots,w_k$ denote the children of $v$, then we have

$$A[u,v] = \min(d(u,v) + A[v,w_1] + \dots + A[v,w_k], A[u,w_1] + \dots + A[u,w_k]).$$

(Here the first term in the $\min$ corresponds to the case where $v$ is included in the tree, and the second term where $v$ is not included.)

As a result, we can compute all of the $A[u,v]$ values using dynamic programming.  There are at most $O(|V|^2)$ many values to compute, and each one can be computed in $O(k)$ time where $k$ is the maximum degree of the tree, so the total running time is $O(|V|^2 k)$.


Indexing a random permutation I am curious if there exists a method for specifying a permutation $F_k: X \to X$ with a small(ish) $k$.

Something that comes very close to my goal is a block cipher, say AES. But block ciphers have fixed block size (e.g. 64, 128 bits), and I want something with parameterizable (and smaller) "block size" $\log_2 |X|$. I also don't need many characteristics of block ciphers (e.g. $k$ secrecy, etc.), only the permutation part.

Something else that is quite close is the Lehmer code. However, this takes into consideration all possible permutations $|X|!$, and would need the index (or "key") $k$ to be as large as $|X| \log_2 |X|$. I am happy with only $K << |X|!$ possible permutations (so long as $K$ is "big enough").

You can build a block cipher with any desired block size, using a method called "format preserving encryption".  The block size doesn't have to be limited to 64 bits or 128 bits.  This will provide a reasonable solution to your problem.

See Bijective algorithm(s) that can shuffle a range of numbers back and forth, Pseudo random, unqiue integer numbers in a given range, Invertible function that randomizes order, Efficiently generating a uniformly random list of unique integers in a range, Lazily computing a random permutation of the positive integers.


on-the-fly decompress a flat-file database I'm facing the following problem. I have a flat-file database (e.g. CSV).
Since it's relatively large to store in memory, I'd like to compress it.

Given a key, I need to return the uncompressed text (record of values).

So one naive idea is to tokenize the text into words and to have the mapping $\text{word} \mapsto \text{codeword}$

Of course, this naive idea lacks of understanding of statistical properties in the data, that other compression algorithms exploits.

So the next thing I thought about is Huffman code. The problem I'm facing is that I'd like to find the optimal tokenization for the text. Let's say that one column in the CSV file contains only the text "the fox jumped over the lazy dog", it reasonable to want that the algorithm would tokenize this string as one token.

but then again, going over all possibilities isn't a feasible task.
Are there any algorithms that deals with this problem?

So to summarize, I need to:

Compress my data once and to decompress on demand
Return the requested value (a record) for a given key
Decompression should be "fast enough"

Which algorithms fit my problem?

In particular, I'd like to know if Huffman code is a good option, and if so, how to tokenize the text.

Thanks!

What is "too large to fit in memory"? Current operating systems can handle processes with GiB of memory, if you use e.g. mmap(3) on Unix/Linux, you can work as if you had the whole file in memory and access it at random. That might be much faster than compressing/uncompressing on the fly. And (if I understand your question correctly) you want to access individual records (i.e., rows) by key, so you will have to compress only the remaining row and keep the key, working one row at a time (you don't want to have to uncompress from the start to be able to access row 102354 each time, don't you?). That will severely limit the compression gain.

If you can preprocess the data (a given, since you talk about compressing it), perhaps an even better bet is to use a simple(ish) database to store it, like Berkeley DB, the Unix standard DBM or it's GNU take GDBM or other, more modern, for performance tuned ones like Lightning Memory-Mapped Database LMDB.


On the complexity analysis of quick-union in Algorithms by Sedgewick and Wayne I am currently studying Algorithms, Fourth Edition by Sedgewick et al. On page 226, there is an analysis of the quick-union algorithm's find() method's worst case.

This is the algorithm:

  private int find(int p)
  { // Find component name.
      while (p != id[p]) p = id[p];
      return p;
  }

Suppose we have originally an array from 0 to N-1. Now I count N comparisons in total (inside the while) plus N-1 accesses (last comparison is false) to rewrite the value of p. This would give me 2N - 1 accesses to the array. The textbook however says there are 2N+1 accesses.
What am I doing wrong?
Thanks for your time.

Computational complexity is being measured by the number of accesses to the array that we use to model which site belongs to which component. Suppose we want to connect the site labeled 3 with the site labeled 1. In order to do that we just make sure id[3]=1.  The find() method exists to give us the  component to which an element belongs. If we now connect 1 to 4, then we just make id[1] = 4. Now find(3) will be 4, because 3 points to 1 which in turn points to 4.

Yes, you are correct!
You have identified a typo in that book, Algorithms, the fourth edition by Robert Sedgewick and Kevin Wayne. Please check the errata for the first printing (March 2011) of the fourth edition.

p. 226
Printed:  in the worst case, it needs 2 N + 1 array accesses
Fixed:    in the worst case, it needs 2 N - 1 array accesses
Reported by Victoria Solomon, 15-Sep-11.


What are common techniques for reducing problems to each other? In computability and complexity theory (and maybe other fields), reductions are ubiquitous. There are many kinds, but the principle remains the same: show that one problem $L_1$ is at least as hard as some other problem $L_2$ by mapping instances from $L_2$ to solution-equivalent ones in $L_1$. Essentially, we show that any solver for $L_1$ can also solve $L_2$ if we allow it to use the reduction function as preprocessor.

I have performed my share of reductions over the years, and something keeps bugging me. While every new reduction requires a (more or less) creative construction, the task can feel repetitive. Is there a pool of canonical methods?

What are techniques, patterns and tricks one can regularly employ for constructing reduction functions?

This is supposed to become a reference question. Therefore, please take care to give general, didactically presented answers that are illustrated by at least one example but nonetheless cover many situations. Thanks!

The Special Case

Assume we want to show $L_1 \leq_R L_2$ with respect to some notion of reduction $R$. If $L_1$ is a special case of $L_2$, that is quite trivial: we can essentially use the identity  function. The intuition behind this is clear: the general case is at least as hard as the special case.

In "practice", we are given $L_2$ and are stuck with the problem of picking a good reduction partner $L_1$, i.e. finding a special case of $L_2$ that has proven to be $R$-hard.

Simple Example

Assume we want to show that KNAPSACK is NP-hard. Luckily, we know that SUBSET-SUM is NP-complete, and it is indeed a special case of KNAPSACK. The reduction

$\qquad f(A,k) = (A, (1,\dots,1), k, |A|)$

suffices; $(V,W,v,w)$ is the KNAPSACK instance that asks whether we can achieve at least value $v$ with item values in $V$ so that the corresponding weights from $W$ remain beneath $w$ in total. We don't need the weight restrictions for simulating SUBSET-SUM, so we just set them to tautological values.

Simple exercise problem

Consider the MAX-3SAT problem: given a propositional formula $\varphi$ and integer $k$, decide whether there is an interpretation of $\varphi$ that fulfills at least $k$ clauses. Show that it is NP-hard.

   3SAT is a special case; $f(\varphi) = (\varphi, m)$ with $m$ the number of clauses in $\varphi$ suffices.

Example

Assume we are investigating the SUBSET-SUM problem and want to show that it is NP-hard.

We are lucky and know that the PARTITION problem is NP-complete. We confirm that it is indeed a special case of SUBSET-SUM and formulate

$\qquad \displaystyle f(A) = \begin{cases}
  \left(A, \frac{1}{2}\sum_{a \in A} a\right) &, \sum_{a \in A} a\mod 2 = 0 \\
  \left(A, 1 + \sum_{a \in A} |a|\right) &, \text{else}
\end{cases}$

where $A$ is the input set of PARTITION, and $(A,k)$ is an instance for SUBSET-SUM that asks after a subset of $A$ summing to $k$. Here, we have to take care of the case that there is no fitting $k$; in that case, we give an arbitrary infeasible instance.

Exercise Problem

Consider the problem LONGEST-PATH: given a directed graph $G$, nodes $s,t$ of $G$ and integer $k$, decide whether there is a simple path from $s$ to $t$ in $G$ of length at least $k$.

Show that LONGEST-PATH is NP-hard.

   HAMILTON-CYCLE is a well-known NP-complete problem and a special case of LONGEST-PATH; $f(G) = (G,v,v,n)$ for arbitrary node $v$ in $G$ suffices.
 Note in particular how reducing from HAMILTON-PATH requires more work.


Is a device with restrictive execution policies Turing-complete? There are devices that do not allow users to load any application they want on it, only run a limited class of applications approved by the device vendor.

Take an iPhone as an example where new applications are loaded (solely) from app-store and programs that would allow execution of arbitrary code by user (without permission of Apple) are not permitted (e.g. Flash).

Are such machines where users cannot execute arbitrary code on themselves still Turing-complete computers? Can they still be considered as universal Turing machines?

First, Apple may wish to restrict applications, but in practice, all versions of the iPhone can be jailbroken: you can then upload arbitrary machine executables. Whether the phone vendor likes or dislikes that you jailbreak the phone is immaterial to evaluating its computing power. But, for the same of the argument, let's add the hypothesis that the iPhone is not jailbroken, and more generally that you only use the iPhone in ways that are approved by Apple.

Whether you can load your code without Apple's approval or not is not relevant. The iPhone is Turing complete if there is some way of programming every computable function and of encoding arbitrarily long inputs and outputs. Turing completeness doesn't say that the encoding has to be what you consider the most natural, which is to install arbitrary machine code.

There is a killer argument which shows that the iPhone, like any other computer, is not Turing-complete: it only has a finite amount of memory. Therefore, the class of computing power is that of a finite automaton, no more.

If the iPhone was allowed to rely on an external storage medium that allowed to store an arbitrarily large amount of data (finite, but whose length is not bounded by the input size), and if network access was allowed, then it would be Turing-complete. One way would be to browse a website containing a Turing machine emulator or other Turing-complete computation mechanism, with input being defined as typing in a form and output being defined as changing the content of the page.

There are other ways of encoding Turing machines that don't require network access or non-default apps to begin with. You would need an iPhone augmented with an infinite tape to pull it off, though, so such an encoding would have to specify how the tape is used in addition to the use of actual iPhone features.

For example, you can type arbitrary JavaScript in bookmarklets in the web browser. If we ignore the problem that a concrete physical device has a finite amount of memory, JavaScript is a Turing-complete language. If you treat the bookmarklet arguments as input and the target URL as output, you can implement a universal Turing machine. JavaScript cannot i
nteract with all hardware devices, but as far as pure computing power is concerned, it is sufficient to perform any calculation.


Number of DFAs of only one state If I have a DFA with only one state that is not an accept state, it accepts only the empty set.

I get confused when if the DFA of one state is an accept state. Does this mean it accepts everything? Or could you have it only accept "a" and not "b". I guess I don't understand if not having an arrow out implies there is a second "invisible state"

In other words, for a DFA of one state, are there 2 or 4 distinct machines?

Thanks!

First let $\Sigma = \{a,b\}$.

Assuming that you're taking a strict approach, there has to be a transition from every state for every symbol in the alphabet, then you have only two possible DFAs (that accept $\emptyset$ and $\Sigma^{\ast}$ respectively).

If you allow a partial transition function, where missing transitions imply rejection (note that this can still be interpreted deterministically), then there are five different languages that can be accepted (strictly there's seven automata): $\emptyset$, $\{\varepsilon\}$, $a^{\ast}$, $b^{\ast}$ and $\Sigma^{\ast}$.

With a larger alphabet, in the partial function case, you get more of course. With $|\Sigma| = n$ there are $2^{n} + 1$ possible languages, from $2^{n+1}$ different automata (half produce the same language). You get $2^{n}$ from each possible choice of which symbols will have a transition in the case where the state is accepting, and the $+ 1$ from the case where the state is non-accepting (it doesn't matter what transitions you have then, the languages are all $\emptyset$).


What does it mean if we disable K-rule in Agda? TL;DR: Can I say, "K-rule in Agda enables people to match $ \forall a.a \equiv a $ with $ refl $"?

In https://agda.readthedocs.io/en/v2.5.4.1/language/without-k.html#without-k, K-rule is introduced as an implicit rule and it's defaultly enabled. If I understand it correctly, it means parameter of type $ \forall a.a \equiv a $ can be matched with $ refl $. If we disable K-rule, what will happen? What kind of codes is it going to prevent me writing? Because we can always construct $ \forall a . a \equiv a $, even without K, we can always get an instance of $ T $ by passing $ refl $ to any functions with type $ \forall a.a \equiv a \rightarrow T $.

Agda's doc has given me an example which indeed shows a circumstance that can only work with K:

K : {A : Set} {x : A} (P : x ≡ x → Set) →
    P refl → (x≡x : x ≡ x) → P x≡x
K P p refl = p

In this code, if we can pattern match x≡x with refl, P refl can be trivially equivalent to P x≡x (but without K, we can't).

So does that mean: "K enables people to match $ \forall a.a \equiv a $ with $ refl $"? I didn't find the answer on the Agda doc.

If we disable K, will the semantic of Agda's equality type (CH-ISO) change?

Axiom K is related to "Uniqueness of Identity Proofs", which says is that any two proofs of equality are themselves equal to each other (i.e. are both Refl). Agda doesn't include K as an axiom, but it (and UIP) can be proved as a theorem using Agda's dependent pattern matching.

Axiom K is inconsistent with homotopy type theory, where the univalence axiom provides ways of constructing equalities other than refl. For example, if there are two functions that are pointwise equal, univalence asserts that there is an equality term equating them, but it cannot be refl if the functions have different implementations.

All removing K from Agda does is add restrictions to pattern matching, making fewer matches typecheck. The runtime semantics are unchanged, and no new programs typecheck.

For some excellent introductions on the subject, I recommend:

Pattern Matching without K

Unifiers as Equivalences

Both of these have more detailed versions in JFP if you have access to a subscription.


Building a finite state transducer I know it's possible to build a Finite State Transducer for converting numbers from base 2 to base 4 or 8 or other powers of 2 (translating from base N to base N^M is easy). However I've never seen a FST that can convert numbers from base 1 to base 2 or viceversa. Can a FST even do this? If so, can you please give some hints on building such a FST?

In my opinion, such transducers does not exist.

It is not possible to convert from base 2 to base 1, since the regular language $\{10^n\ |\ n \in \mathbb{N}\}$ would become $\{1^{2^n}\ |\ n \in \mathbb{N}\}$, which is nonregular. However, regular languages are closed under the translation by the finite state transducer.

On the other hand, I was not able to find such a straightforward proof for the opposite case (that does not mean that such a proof does not exist). But I am inclined to believe that it is not possible as well. The reason is that the transducer would have some transitions writing $\varepsilon$ and some transitions writing non-$\varepsilon$ words. However, since the length of the image of $w, |w| = n$ is $O(\log n)$, the transitions writing non-$\varepsilon$ words are used significantly less (but nonconstant number of times) than the $\varepsilon$-transitions on all inputs. However, for a finite state transducer, a transition is either used a constant number of times, or there exists an input such that the number of uses of that transition is at least $\frac{1}{m} n$, where $m$ is number of transitions and $n$ is the length of the input (this is not so hard to prove). Moreover, clearly, such input exists for arbitrarily large $n$. Therefore, we get a contradiction.


How can I solve a recursive equation with a summation notation? Consider the following formula:

$T(n) = n + \sum_{k=1}^{n-1} [T(n-k) + T(k)], T(1) = 1$

What is the order of T?


What algorithm do SVMs use to minimize their objective function? Support Vector Machines turn machine learning linear classification tasks into a linear optimization problems.
$$ \text{minimize } J(\theta,\theta_0) = \frac1n \sum_1^n \text{HingeLoss}(\theta,\theta_0) + \frac{\lambda}{2} ||\theta||^2 $$
My question is, what linear programming runs on the background for the minimization of the objective function $J$. Is it Simplex?

The SVM problem (and other related problems) can be described as a minimization \ maximization of a quadratic function.
This can be easily solved with the gradient descent algorithm, however I recommend using the SMO algorithm since it is a direct solution (to the dual of the SVM problem), and can be also used for kernelized SVMs


Does Max-SNP hard imply NP-hard I have difficulties understanding the definition of the class Max-SNP (optimization variant of strict NP), thus I have to following basic question:

If a problem is known to be Max-SNP hard, does this imply NP-hardness of the problem?

$\newcommand{\maxsnp}{\mathsf{Max}\text{-}\mathsf{SNP}}$The definition of $\maxsnp$ gives us the ability to define:

Universal ($\forall$) and existential ($\exists$) quantifiers over variables
Existential quantifiers over relations

With this definition we can define $\mathsf{Max}$-$\mathsf{SAT}$:

$$\exists x, \forall y \text{ such that } |\psi(y)| \leq |\psi(x)|$$ where $|\psi(x)|$ is the number of clauses satisfied in formula $\psi$ under assignment $x$.

Given that $\mathsf{Max}$-$\mathsf{SAT}$ is $\mathsf{NP}$-$\mathsf{Hard}$, we see that $\mathsf{NP}$-$\mathsf{Hardness}$ is implied from $\maxsnp$.


Why is quicksort better than other sorting algorithms in practice? In a standard algorithms course we are taught that quicksort is $O(n \log n)$ on average and $O(n^2)$ in the worst case. At the same time, other sorting algorithms are studied which are $O(n \log n)$ in the worst case (like mergesort and heapsort), and even linear time in the best case (like bubblesort) but with some additional needs of memory.
After a quick glance at some more running times it is natural to say that quicksort should not be as efficient as others.
Also, consider that students learn in basic programming courses that recursion is not really good in general because it could use too much memory, etc. Therefore (and even though this is not a real argument), this gives the idea that quicksort might not be really good because it is a recursive algorithm.
Why, then, does quicksort outperform other sorting algorithms in practice? Does it have to do with the structure of real-world data? Does it have to do with the way memory works in computers? I know that some memories are way faster than others, but I don't know if that's the real reason for this counter-intuitive performance (when compared to theoretical estimates).

Update 1: a canonical answer is saying that the constants involved in the $O(n\log n)$ of the average case are smaller than the constants involved in other $O(n\log n)$ algorithms. However, I have yet to see a proper justification of this, with precise calculations instead of intuitive ideas only.
In any case, it seems like the real difference occurs, as some answers suggest, at memory level, where implementations take advantage of the internal structure of computers, using, for example, that cache memory is faster than RAM. The discussion is already interesting, but I'd still like to see more detail with respect to memory-management, since it appears that the answer has to do with it.

Update 2: There are several web pages offering a comparison of sorting algorithms, some fancier than others (most notably sorting-algorithms.com). Other than presenting a nice visual aid, this approach does not answer my question.

Short Answer

The cache efficiency argument has already been explained in detail. In addition, there is an intrinsic argument, why Quicksort is fast. If implemented like with two “crossing pointers”, e.g. here, the inner loops have a very small body. As this is the code executed most often, this pays off.

Long Answer

First of all,

The Average Case does not exist!

As best and worst case often are extremes rarely occurring in practice, average case analysis is done. But any average case analysis assume some distribution of inputs! For sorting, the typical choice is the random permutation model (tacitly assumed on Wikipedia).

Why $O$-Notation?

Discarding constants in analysis of algorithms is done for one main reason: If I am interested in exact running times, I need (relative) costs of all involved basic operations (even still ignoring caching issues, pipelining in modern processors ...).
Mathematical analysis can count how often each instruction is executed, but running times of single instructions depend on processor details, e.g. whether a 32-bit integer multiplication takes as much time as addition.

There are two ways out:

Fix some machine model.

This is done in Don Knuth's book series “The Art of Computer Programming” for an artificial “typical” computer invented by the author. In volume 3 you find exact average case results for many sorting algorithms, e.g.

Quicksort: $ 11.667(n+1)\ln(n)-1.74n-18.74 $
Mergesort: $ 12.5 n \ln(n) $
Heapsort:  $ 16 n \ln(n) +0.01n $
Insertionsort: $2.25n^2+7.75n-3ln(n)$

[source]

These results indicate that Quicksort is fastest. But, it is only proved on Knuth's artificial machine, it does not necessarily imply anything for say your x86 PC. Note also that the algorithms relate differently for small inputs:

[source]
Analyse abstract basic operations.

For comparison based sorting, this typically is swaps and key comparisons. In Robert Sedgewick's books, e.g. “Algorithms”, this approach is pursued. You find there

Quicksort: $2n\ln(n)$ comparisons and $\frac13n\ln(n)$ swaps on average
Mergesort: $1.44n\ln(n)$ comparisons, but up to $8.66n\ln(n)$ array accesses (mergesort is not swap based, so we cannot count that).
Insertionsort: $\frac14n^2$ comparisons and $\frac14n^2$ swaps on average.

As you see, this does not readily allow comparisons of algorithms as the exact runtime analysis, but results are independent from machine details.

Other input distributions

As noted above, average cases are always with respect to some input distribution, so one might consider ones other than random permutations. E.g. research has been done for Quicksort with equal elements and there is nice article on the standard sort function in Java


Lower bound on comparison-based sorting I have a question from one of the exercises in CLRS.

Show that there is no comparison sort whose running time is linear for at least half
of the $n!$ inputs of length $n$. What about a fraction of $1/n$ of the inputs of length $n$?
What about a fraction $1/2^n$?

I have arrived at the step where for a linear time sorter, there will we $2^n$ nodes in the decision tree, which is smaller than the $n!$ leaves so this is a contradiction but I am unsure of how to formally write out the proof and extend it to the other fractions? The question also states that "for at least half of the $n!$ inputs of length $n$". I do not quite understand how it affects the number of leaves in the decision tree as any input of length $n$ will have $n!$ possible permutations.

If there is a comparison sort whose running time is $f(n)$ on $g(n)$ of the inputs, then there are at least $g(n)$ leaves at depth at most $f(n)$, and so $g(n) \leq 2^{f(n)}$.


Is it possible to prove EQTM is undecidable by the Rice theorem? Given the problem $EQ_{TM} = \{ \langle M_1,  M_2\rangle \mid M_1 \text{ and } M_2 \text{ are } TM, L_{M_1} = L_{M_2}\}$, is it possible to prove that this is undecidable by using (a variant of) Rice theorem?

I have proven this problem by reduction to $E_{TM}$, but was wondering if it was easier to do with Rice.

You can reduce it to a problem about single Turing machines by fixing one of the inputs. For example, you can take $M_2$ to be some Turing machine which accepts nothing. This shows that $EQ_{TM}$ is at least as hard as deciding emptiness.

Another approach is to encapsulate the pair of Turing machines $M_1,M_2$ in one Turing machine $M$, which upon input $0x$ will simulate $M_1$ on $x$, and upon input $1x$ will simulate $M_2$ on $x$ (on the empty input it can arbitrarily halt). There is a simple reduction showing that $EQ_{TM}$ is equivalent to the corresponding problem for $M$, and then you can apply Rice's theorem.


Are there name and literature for this SAT-like problem? Given $f : \{0,1\}^* \to \{0,1\}$ and $n \in \mathbb{N}$,
we define $\textsf{Prob}(f,n)$ as the following problem:

  Find an $x \in \{0,1\}^n$ such that $f(x) = 1$.

A machine solving $\textsf{Prob}(f,n)$
would have $f$ encoded as a bit-string representing another machine computing $f$
and would have $n$ encoded in binary.

$\textsf{Prob}(f,n)$ generalizes some problems. For example:

If $f$ is a Boolean logical proposition with $n$ variables,
then $\textsf{Prob}(f,n)$ would be the search problem that corresponds to the SAT of $f$.
If $f$ is the decider for a language,
then $\textsf{Prob}(f,n)$ would be the problem of finding
an $n$-bit string in that language.

Has $\textsf{Prob}(f,n)$ been studied in the literature (presumably with another name)?
Is there already a name for this problem?
What would be a good starting point to find papers on this problem in the research literature?

What problems are similar to this problem?

Is there linear-time $f$ such that
$\textsf{Prob}(f,n)$
has no better algorithm than brute force?
Formally, is there $f$ such that
evaluating $f(x)$ is in $\textsf{DTIME}(O(\lvert x \rvert))$
and $\textsf{Prob}(f,n) \in \textsf{DTIME}(\Omega(2^n))$?

The problem, as specified, takes at least exponential time to solve: merely outputting a string $x$ that satisfies $f(x)=1$ takes $\Theta(n)$ time (since $x$ is $n$ bits long), and this is exponential in the length of the input in the worst case (if $f$ has a short description, then the input length is $\Theta(\lg n)$ bits.  This is a consequence of the fact that $n$ is specified in binary.

If $n$ is specified in unary and the running time of $f$ is guaranteed to be polynomial in $n$, the problem is NP-hard, and the corresponding decision problem is NP-complete.  It is at least as hard as SAT, because any SAT formula can be encoded as a program $f$.  Also, it is no harder than SAT, as any program whose running time is polynomial in $n$ can be expressed as a circuit of size polynomial in $n$; then the problem becomes equivalent to CircuitSAT, which is also NP-complete by a standard reduction (basically, the Tseitin transform).

So the unique aspects of this problem come from (a) the fact that $n$ is expressed in binary, and (b) the lack of any guarantee on the running time of $f$.

For your last question, you have to be a little bit careful.  If you fix $f$ and specify $n$ in unary, the problem seems unlikely to require $\Omega(2^n)$ time.  In particular, there is an infinite advice string $A$ such that the answer to the input $n$ is $A_n$.  This shows that there is a non-uniform polynomial time algorithm for this problem, if you fix $f$ and express $n$ in unary (i.e., the problem is in P/poly); this would be surprising, as it implies NP is contained in NP/poly, which is not expected to occur.  To avoid trivial situations like this, you might want to treat the description of $f$ as part of the input, rather than fixing $f$.

This suggests we ask whether there exists a class of functions $f$ such that the problem requires $\Omega(2^n)$ time, yet where every function $f$ in the class can be computed in $O(n)$ time.  I suspect the answer to that is likely to be yes if the strong exponential time hypothesis is true; simply take as your class of functions the set of SAT formulas of size $O(n)$.  Note that this doesn't follow immediately from the strong exponential time hypothesis, due to the extra restriction that the formulas have size $O(n)$, but I would venture a guess that this restriction does not help algorithms solve SAT more efficiently.  That said, the strong exponential time hypothesis is a very strong assumption.

Also, if we could prove that the answer to this question is yes, then I suspect we'd obtain a proof that the strong exponential time hypothesis is true.  In particular, since $f$ can be computed in $O(n)$ time, there is a circuit that computes it in $O(n)$ time, so it can be expressed as a SAT formulas with $O(n)$ variables (using the Tseitin transform).  If we knew that there was no algorithm to solve the resulting class of SAT instances in $O(2^n)$ time, then we'd know there is no algorithm to solve all SAT instances in $O(2^n)$ time, which implies the strong exponential time hypothesis.  I think.


Does Quicksort always have quadratic runtime if you choose a maximum element as pivot? If you have a quick-sort algorithm, and you always select the smallest (or largest) element as your pivot; am I right in assuming that if you provide an already sorted data set, you will always get worst-case performance regardless of whether your 'already sorted' list is in ascending or descending order?

My thinking is that, if you always choose the smallest element for your pivot, then whether your 'already-sorted' input is sorted by ascending or descending doesn't matter because the subset chosen to be sorted relative to your pivot will always be the same size?

The worst case complexity for quicksort is $\Theta(n^2)$. This is achieved by picking pivots that divide the set such that one group has only a single member. With a bad pivot picking algorithm, this can easily be achieved by picking one end of a sorted set. Your assumption is correct.


Whether the given language is a CFL or not? Let $L$ be a language defined over $\Sigma = \left \{ a, b \right \}$ such that
$L = \left \{ x\#y \mid x,y \in \Sigma^*, \# \text { is a constant and } x \neq y \right \}$
State whether the language L is a CFL or not? Give valid reasons for the same.

Now, I think that the given language is not a CFL. I have used the pumping lemma test for showing that L is not CFL.
Specifically, I have done the following-

Consider a string $w = abb\#aab$. Obviously, $w \in L$.

Let, $u = \epsilon \\ v = a \\ w = bb\#aa \\ x = b \\ y = \epsilon$

Here, $|vx| \geq 1$

But, $uv^2wx^2y = aabb\#aabb \notin L$
Therefore, pumping lemma test result is negative. Therefore, we can conclude that the given language is not a CFL.

Now, I have a doubt regarding the above method-
 I know that given a CFL, if we want to perform the pumping lemma test for the CFL, we must always use strings which are of length greater than or equal to the minimum pumping length. In fact, this also confirms to the condition that the length of the string $w$ used for the pumping lemma test (denoted by $|w|$) must be greater than or equal to n.

Therefore, when I use $w = abb\#aab$ for doing the pumping lemma test, I implicitly make the assumption that 7 is greater than or equal to the minimum pumping length (if $L$ were to be a CFL). Am I correct or incorrect in doing so?

The language is context-free.

The statemant of the pumping lemma claims "there exists a $uvwxy$-division", so in order to show a language non-context-free, you have to check that every possible division leads to a pumping contradiction. Your mistake is that you only checked one division.


Minimal Spanning Tree vs Minimum Spanning Tree I got confused about minimal and minimum in context of graph theory.
Although, I have understanding that minimal means more than one minimum i.e. none qualifies as actual minimum so we say them minimal.
What exactly does minimal spanning tree mean? Also, what exactly does 'minimal edge' mean?
How do they differ from minimum spanning tree?
How are 'minimal edge' different from minimum edge?
This doubt arose due to the statement:
S: There exists a minimum weight edge in G, which exists in every minimum spanning tree of G.
Can we say on using word 'minimum' it's implied that there is only one minimum weight edge. Besides, statement used "exists" which is singular.

A minimum weight edge is an edge whose weight is minimal among all edges. There can be more than one minimum weight edge. All minimum weight edges have the same weight.
Similarly, a minimum spanning tree is a spanning tree whose weight is minimal among all spanning trees. There can be more than one minimum spanning tree. All minimum spanning trees have the same weight.
In some cases, there is a distinction between minimum and minimal. For example, a minimum vertex cover is a vertex cover whose weight is minimal among all vertex covers. In contrast, a minimal vertex cover is a vertex cover, any proper subset of which isn't a vertex cover. Finding a minimal vertex cover is easy – start with the set of all vertices, and repeatedly remove a vertex as long as it is possible to do so while maintaining the property of covering all edges. In contrast, finding a minimum vertex cover is expected to be hard (the corresponding decision problem is NP-hard).
The same property of being minimal doesn't make much sense for edges and spanning trees. When people say minimal edge or minimal spanning tree, they probably mean minimum (weight) edge and minimum spanning tree.


Using B-method, and formal methods in general, to model and verify a reverse linked list I am trying to do some formal modeling of a linked list, however instead of referencing the next block, each block needs to reference the previous block instead.

Is there already any formal methods or any formal for doing this ?

Exactly the same as a normal linked list but when a new block (value etc) is added this references the past value (much like the bitcoin blockchain).

I have modeled a normal linked list (Data queue) modeled in the b method

MACHINE DataQueue ( DATA , anydata , maxqueue )

CONSTRAINTS anydata E DATA /\ maxqueue > 0
SEES Bool TYPE
SETS TOKEN
PROPERTIES card ( TOKEN ) = maxqueue
VARIABLES TokenSeq , TokenMap

INVARIANT
TokenSeq E iseq ( TOKEN ) /\
TokenMap E TOKEN -|-> DATA /\
dom ( TokenMap )=  USED
INITIALISATION
TokenSeq , TokenMap : [] , {}

OPERATIONS
success , token <-- AddItem( item )  =^
PRE E item DATA THEN
CHOICE
ANY new token WHERE new_token  E TOKEN_USED
THEN
TokenSeq := TokenSeq <-- new token ||
TokenMap ( new token ) := item ||
success , token := TRUE , new token
END
OR
success := FALSE || token :E TOKEN
END
END ;
DEFINITIONS
USED =^ ran ( TokenSeq )
END

There are many approaches for verifying linked structures---arguably, more suitable than the B method---that you might want to use, depending on the language and properties you want to verify. Most of the approaches rely on separation logic (which was in big part motivated for verification of linked structures).

Some tools include:

Full Functional Verification of Linked Data Structures -- where you write Java code with specifications in classical higher-order logic, while the verifier uses integrated reasoning of multiple different provers
Linked list, imperative separation logic in Isabelle -- uses separation logic in Isabelle theorem prover (other similar data structure examples might be found in the archive of formal proofs)
Dafny: A Language and Program Verifier for Functional Correctness -- which allows specifying and verifying wide range of data structures in C# (many examples for linked lists exist, e.g. this one)

To quote this answer (which answers a very similar question), even though you did not give details about what are you trying to verify, it seems that properties you might want to prove about the "reverse linked list" might be formulated as properties for a regular linked list. (If the reverse list requires some additional (non-standard) implementations, not already declared for the linked list, you might be able to model those in addition.)

I am not sure what was the purpose of your example, but your code seems similar to an example of modelling a linked list with B (which includes other standard operations) method in Program Development by Refinement Case Studies Using the B Method.


In Amortized Analysis, can we chose how big $n$ is? Suppose I want to show by contradiction that the amortized cost of a data structure with some operations cannot be less then $\Theta(k)$. I assume for the sake of contradiction that it is possible. Can I then choose an $n$, large enough, and a special sequence of operations and show that they take $\Theta(nk)$ and conclude that the amortized cost has to be at least $\Theta(k)$? Or does my counter example must be for any chosen size of $n$ sequences?

In other words, I want to show that for any large $n$ that satisfies $\frac{n}{2}>2^k-1$, the counter example works. Is this sufficient?

Edit: To show what I mean here is an example:
I have a binary counter that supports the option INCREMENT and DECREMENT. It starts at all zeros at the start. I wanna show that the ammortized cost cannot be less than $\Theta(k)$.

So I assume the opposite. And I first do $2^k$ increment operations so that I have [1(k-1 zeros)] as the binary counter. Then I do $m$ DEC INC operations in succession where each of them will take $\Theta(k)$.

here we have $n=2^k+m$. Choosing $m=2^k$, we get $n=2^{k+1}$ so $m=\Theta(n)$. So we get total amount of work $\geq km=k\Theta(n)=\Theta(nk)$ so the amortized time is $\Omega(k)$.

However, the above argument only holds if $n\geq 2^{k+1}$, does this constitute a proof?

It depends a bit on what you mean with "choose an $n$". If you pick a fixed $n$, say a million, then no, that's not enough. Asymptotic notation already means "for sufficiently large inputs, the runtime is...". So a counterexample of any fixed size won't do.

If however you show a method that for an infinite number of sufficiently large $n$ produces a counterexample, then this is valid.


Validity of CTL formula $s_0 \models EG\ AF\ p$ in given model I have been learning Verification by model checking recently and I get the following question:

  Is the CTL formula $s_{0} \models EG\ AF\ p$ valid in the following model?

I think it is incorrect because there is a deadlock or infinite loop about $s_0$ after the state is starting from $s_0$, which make it invalid under $EG\ AF\ $ condition.

Am I correct? How can I prove it (or give a counterexample)?

You're correct. Another way to see would be to consider the de-morgan equivalent: $\neg (AF~EG~\neg p)$. To show this invalid, we can show its negation $AF~EG~\neg p$ is valid, which is easier: The formula $AF~EG~\neg p$ says on all paths starting at $s_0$, we eventually get to a state such that there is a path where $\neg p$ holds forever. And indeed that is true in the path $s_0 \rightarrow s_0 \rightarrow\ldots~.$ Since we established the negation, your original formula is invalid as you yourself concluded.

Thinking about CTL can be tricky. A good way is to always double-check using a CTL model checker, like the following:

MODULE main()
  VAR
    state: {s0, s1, s2, s3};

  ASSIGN
    init(state) := s0;
    next(state) := case
                     state = s0: {s0, s1, s3};
                     state = s1: s2;
                     state = s2: s1;
                     state = s3: s2;
                   esac;

  DEFINE
    p := (state = s1) | (state = s3);
    r := (state = s0) | (state = s1) | (state = s2);
    q := (state = s2) | (state = s3);
    t := (state = s1);

  SPEC EG AF p;

Using nuSMV (http://nusmv.fbk.eu/), I get:

-- specification EG (AF p)  is false
-- as demonstrated by the following execution sequence
Trace Description: CTL Counterexample
Trace Type: Counterexample
  -> State: 1.1 <-
    state = s0
    t = FALSE
    q = FALSE
    r = TRUE
    p = FALSE

Which is NuSMV's way of saying you can simply stay in the starting state and it would be a counter-example to your property.


An edge that connects more than two nodes in a graph? Is there a way to create a single edge on a graph that connects 3 or more nodes? For example, let's say that the probability of Y occurring after X is 0.1, and the probability of Z occurring after Y is 0.001, but the probability of Z occurring after both X and Y occur is 0.95. If the probabilities are assigned to each edge as weights, how can I make this happen?

$$X _\overrightarrow{0.1} Y$$

$$Y _\overrightarrow{0.001} Z$$

$$\overrightarrow{X \underrightarrow{} Y \underrightarrow{0.95}} Z$$

When edges connect more than two nodes, you don't have a graph, you have a hypergraph. More precisely, since transitions are oriented (you're starting from a digraph) and there are probability on each transition, you have a weighted hyperdigraph. I'm not sure having this term will help you that much: as data structures go, this isn't that much of a classic.

Transitions with multiple origins rather remind me of Petri nets. If your probabilities are rational numbers and there are no loops, you can scale them to integers. Otherwise you would need to reach for probabilistic Petri nets, I think.


What is the relation between the compatibile features and the state features in Actor Critic Algorithm? According to Actor-Critic algorithm, $\psi_{\theta}=\nabla_{\theta}\ln \mu_{\theta}(s, a)$ where $\mu_{\theta}(s, a)$ is the policy followed by the actor and $\psi_\theta$ is the compatibile features space.
The updates for the actor and critic parameters are as follows:

For critic with the parameter w:
$w_{t+1} = w_t + \beta_t\delta_t^{\mu_{\theta}}\phi(s_t)$
where $\phi(s_t)$ is the feature vector of state $s_t$
For actor with the parameter theta:
$\theta_{t+1}=\theta_t + \alpha_t\delta_t^{\mu_{\theta}}\psi(s_t, a_t)$
where $\psi(s_t, a_t)$ is the compatible feature vector of state $s_t$, with action $a_t$.

I am trying to understand the relation between $\psi(s_t, a_t)$ and $\phi(s_t)$, any pointers would be appreciated.

$\phi(s)$ is the representation of the state, and $\psi$ is the gradient (of the log) of the policy. Essentially, those two don't really have any connection, except for that the input to the policy is the state's representation. That is, the policy will compute the appropriate action distribution according by using its model (say a neural network) when applied on the representation of a state.


Hamming error correction with non-uniform error correction capability If I understood correctly, Hamming codes assume the uniform correction among all the bits. This means all the bits have the same weight in terms of correction.

Are there any error correcting codes out there that assume non-uniform error correction probability among the bits? For example, I want a error correcting code that corrects the first bit all the time, but it is fine to correct the second bit 90% of the time.

The topic you want is Unequal Error Protection (UEP) codes. There are a number of constructions in this area and a google scholar search yields quite a few hits.

Intuitively, imagine partitioning your code into disjoint point clouds, where cloud centres are chosen by the more important bits, thus intra-centre distance is high, hence those bits are more robust to noise.

Some references:

On linear unequal error protection codes, B Masnick, J Wolf - IEEE Transactions on Information Theory, 1967.

Multilevel codes for unequal error protection
AR Calderbank, N Seshadri - IEEE Transactions on Information Theory,  1993.

A more information theoretic perspective is the Borade et al paper here on the arXiV.

Lastly, Prof. Lloyd Welch published a nice paper on "Codes correcting selected error patterns", which I can't seem to find a reference to.


Small world theorem for set constraints Let $S_1,\dots,S_n$ be variables representing unknown sets.  A set expression has the form $S_i$, $\overline{E}$ (the complement of $E$), or $E \cap E'$, where $E,E'$ are set expressions.  A constraint has the form $E = \emptyset$ or $E \ne \emptyset$, where $E$ is a set expression.  Given a conjunction of constraints, the problem is to determine whether they are satisfiable, i.e., whether there is an assignment from variables to sets that makes all of the constraints hold.

Conjecture: if there exists a satisfying assignment, then there is a satisfying assignment where all sets are subsets of a universe $U$ with $k$ elements, where $k$ is the number of constraints of the form $E \ne \emptyset$.

Is this conjecture true?

I suspect it is, but I can't seem to prove it.  I can prove it if there is no complement operator, but my proof strategy seems to go awry if there are complements.  (Proof strategy: suppose the constraints are $E_1 \ne \emptyset$, .., $E_k \ne \emptyset$, and suppose we have any satisfying assignment. Let $x$ be the smallest element of $E_1 \cup \dots \cup E_k$, where $x$ is an element of $E_i$; then add $x$ to $U$, discard $E_i$, and repeat.  Once this is finished, replacing each set $S_i$ with $S_i \cap U$ still leaves all constraints satisfied.)  If this conjecture is true, it is a sort of "small-world theorem", which says that a not-too-large universe suffices for checking satisfiability.  These kinds of theorems are helpful for improving the performance of constraint-solving algorithms.

The conjecture is true, and the proof strategy listed there can be made to work.

Let $s = (s_1,\dots,s_n)$ be a satisfying assignment for the variables that makes all of the constraints hold.  We'll write $E(s)$ for the result of evaluating the expression $E$ with the variables $S_i$ set to $s_i$.  In the following, define $U$ by the procedure listed in the question:  let $E_1 \ne \emptyset$, ..., $E_k \ne \emptyset$ be the constraints of second type; pick any element of $E_1(s) \cup \cdots \cup E_k(s)$, call it $x$; add $x$ to $U$; delete all of the constraints $E_i \ne \emptyset$ such that $x \in E_i$; and repeat.  Define $s'_i = s_i \cap U$.

Now I claim that $s'_1,\dots,s'_n$ is also a satisfying assignment that makes all of the constraints hold.

First, let's consider the constraints of the form $E = \emptyset$.  I claim that if $E(s) = \emptyset$, then $E(s') = \emptyset$.  In particular, I claim that $E(s) \cap U = E(s') \cap U$ for all set expressions $E$.  The proof is by recursion: by definition of $s'$, we have $S_i(s) \cap U = S_i(s') \cap U$; also if $t \cap U = t' \cap U$, then $\overline{t} \cap U = \overline{t'} \cap U$; and if $t_1 \cap U = t'_1 \cap U$ and $t_2 \cap U = t'_2 \cap U$, then $(t_1 \cap t_2) \cap U = (t'_1 \cap t'_2) \cap U$.  So this means that $s'$ satisfies all of the constraints of the first type (all of the constraints of the form $E = \emptyset$), since $s$ does.

Next, consider the constraints of the form $E \ne \emptyset$.  We know $E(s) \ne \emptyset$.  Therefore, there was a step in the iterative definition of $U$ when we chose some element $x \in E(s)$ and added it to $U$.  We proved earlier that $E(s) \cap U = E(s') \cap U$.  Since $x \in E(s)$ and $x \in U$, it follows that $x \in E(s') \cap U$, and thus $E(s') \ne \emptyset$.  This means that $s'$ satisfies all of the constraints of the second type, too.

We've shown that if there is any satisfying assignment for all constraints, then there exists a satisfying assignment where all sets are subsets of $U$.  This completes the proof of the conjecture.


Finding the lower bounds of an algorithm I am struggling to calculate the lower bounds of an algorithm. What is the right way to proceed.

For eg, I have the following algorithm

For i=1, 2,...,n
    For j=i+1, i+2,...,n
        Add up array entries A[i] through A[j]
    Store the result in B[i, j] Endfor
Endfor

How do I calculate the lower bounds of this algorithm

Hint: The complexity is proportional to the number of reads from the array $A$.


Weird "proof" recursion Assume we have some statement called $\alpha$. We will define a new statement $P(\alpha):="(\alpha\text{ can be proved})\lor(\lnot\alpha \text{ can be proved})"$
I claim that $P(P(\alpha))$ is always correct (that is, we can always prove\disprove whether a statement can be proved or not).
The following is a "proof" for that:
Assume towards contradiction that $P(P(\alpha))$ is not correct. Then, there is no proof for $P(\alpha)$ and also there isn't a proof for $\lnot P(\alpha)$.
Lemma: If $\alpha$ can be proved, say using some proof $p_\alpha$, then this $p_\alpha$ also proves that "$\alpha$ can be proved", hence $p_\alpha$ proves that $P(\alpha)$ is also true.
Use this lemma again and get that $P(P(\alpha))$ is true.
If $\alpha$ cannot be proved, then either that $\lnot\alpha$ can be proved or not. If it is possible to prove $\lnot \alpha$, then by the lemma we know that $P(\lnot\alpha)$ can be proved. But notice that by the definition of $P$ we have $P(\alpha)\equiv P(\lnot \alpha)$, so also $P(\alpha)$ can be proved, and once again, using the lemma we get that $P(P(\alpha))$ is true.
If its also impossible to prove $\lnot\alpha$, then by the definition of $P(\alpha)$ we have $P(\alpha)$ is false. However the "proof" up until this point proves that $P(\alpha)$ was false, since we assumed that there is no proof for $P(\alpha)$ but in every other case there was a proof. Thus, a contradiction - and hence $P(P(\alpha))$ must be true in this case as well.
My question

Is this idea "correct"?
If it is "correct", then is it possible to formalize it? how would it look like?

I feel like there is a kind of circularity in the last part of your argument (and I think the conclusion is wrong, there are undecidable problems which we cannot prove to be undecidable).
You are basically making a case distinction:

if $\alpha$ can be proved or $\neg \alpha$ can be proved: Then $P(\alpha)$ can be proved and thus $P(P(\alpha))$ is true. (I agree here)
if neither $\alpha$ nor $\neg \alpha$ can be proved: Then $\neg P(\alpha)$ can be proved and thus $P(P(\alpha))$ is true. I disagree here. The correct assumption to make this conclusion would be: "if we can prove that neither $\alpha$ nor $\neg \alpha$ can be proved".

Note that you cannot in general prove that you are in the second case. You say you can because otherwise you could prove that you are in the first case. But what you need is to be able to prove that you cannot find a proof that you are in the first case, which is a different thing.


Finding one of 2/3 of all array elements in constant expected time How do I go about designing a constant time algorithm which satisfies the following I/O requirements:

Input: an array $A$ of length $3n$, containing $2n$ values of the symbol $X$ and $n$ of the symbol $Y$
Output: a number $i$, such that $A[i]=X$

It is clear that the naive linear scan approach is $O(n)$. Is there any good algorithm, potentially randomized, that has a constant number of expected operations $O(1)$?

One approach would be to randomly pick a large constant $k$ indices and test them. The exact probability of at least one of them being $A[i] = X$ would be:

$$\begin{align}
P(\text{at least }1\; X) &= 1 - P(\text{all are } Y)\\
& = 1 - \left(\frac{n/3}{n}\cdot \frac{n/3-1}{n-1}\cdot \ldots \cdot \frac{n/3 - (k-1)}{n - (k-1)}\right)\\[0.5em]
& \geq 1 - 3^{-k}
\end{align}$$
This inequality holds as $n$ approaches $\infty$ for some constant $k$ because:
$$\lim_{n\to\infty} \frac{n/3 - k}{n - k} = \frac{1}{3}$$
Even for some small $k$ like 10, the probability of finding an index $i$ such that $A[i] = X$ is:
$$\begin{align}
P(\text{at least }1\; X) &\geq 1 - 3^{-10}\\
& \geq 0.99998
\end{align}$$


Assignment problem for multiple days I have a problem that can be reduced to an assignment problem.
(In a previous question i found out how to do that.)

Which means we have a set $A$ of agents and a set $T$ of tasks as well as a cost function $c(i,j)$. We need to find an assignment so that the total cost is minimal.

The hungarian algorithm can find an optimal solution in at least $O(n^4)$. Which sounds good to me.

My new Problem is:
There is a given number of days. I have to solve the assignment problem for each day so that every task is done every day and no agent does the same task twice.

What I have tried:
We could run the hungarian algorithm separately for each day and limit the number of possible combinations based on the result of the previous day. But this would get us into trouble at some of the later days, where most likely it will be impossible to find a feasibly solution.

Another idea is to somehow integrate local search to change decisions made at a previous day. But I think we can't rely on this.

The problem instances I have to face will be somewhere around $|A| = |T| = 500$. The cost matrix $C(i,j)$ will have lots of same values (E.g. mostly 1 or infinity, only some 2 or 3). So during the hungarian algorithm there is a lot of space to create different optimal solutions for a single day.

I'd be glad to hear some ideas or advises how to find a good solution for the problem.
Thanks in advance.

There's a way to this in polynomial time. I'll sketch the algorithm (in reverse order ... do step 2 first and step 1 second).

if we can find a set of $nk$ agent-task pairs $(i,j)$ such that each task is in exactly $k$ pairs, each agent is in exactly $k$ pairs, and no pair appears more than once, then we can find $k$ assignments that together cover these $nk$ agent-task pairs. We do this by repeatedly using a maximum bipartite matching algorithm to find a perfect matching in the corresponding bipartite graph, and removing that assignment from the graph. Hall's marriage theorem guarantees we can do this.
We can find the minimum-cost set of $nk$ agent-task pairs as in step 1 by using min-cost flow. Consider a network with a source $s$, a sink $t$, and nodes for each of  the agents and each of the tasks. Connect the source to each agent with an edge of capacity $k$ and cost $0$. Connect each task to the sink with an edge of capacity $k$ and cost $0$. Now, connect agent $i$ to task $j$ with an edge of capacity $1$ and cost $c(i,j)$. The  minimum-cost flow in this network is guaranteed to be integral (because all capacities are integral, and there is a theorem saying that this implies that there is an optimal integral min-cost flow), so the flow on each agent-task edge is $0$ or $1$. The edges $(i,j)$ with flow $1$ form the set of pairs in step 1.

There are lots of algorithms that can solve min-cost flow; it's a special case of linear programming. For your size problem, the algorithm I sketch should not just be polynomial-time, but also practical.


What classes of data structures can be made persistent? Persistent data structures are immutable data structures. Operations on them return a new "copy" of the data structure, but altered by the operation; the old data structure remains unchanged though. Efficiency is generally accomplished by sharing some of the underlying data, and avoiding full copying of the data structure.
Questions:

Are there results about classes of data structures that can be made to be persistent (while keeping the same or very similar complexities)?

Can all data structures be made persistent (while keeping the same or very similar complexities)?

Are any data structures known to be unable to be made persistent (while keeping the same or very similar complexities)?

Positive result: persistence does not cost too much. One can show that every data structure can be made fully persistent with at most a $O(\lg n)$ slowdown.

Proof: You can take an array and make it persistent using standard data structures (e.g., a balanced binary tree; see the end of this answer for a bit more detail).  This incurs a $O(\lg n)$ slowdown: each array access takes $O(\lg n)$ time with the persistent data structure, instead of $O(1)$ time for the non-persistent array.  Now take any imperative algorithm whose running time in the RAM model is $O(f(n))$, where $n$ denotes the amount of memory used.  Represent all of memory as one big array (with $n$ elements), and make it persistent using a persistent map.  Each step of the imperative algorithm incurs at most a $O(\lg n)$ slowdown, so the total running time is $O(f(n) \lg n)$.

Apparently it is possible to do a bit better: apparently one can reduce the slowdown factor to $O(\lg \lg n)$ (expected, amortized time), using the techniques in the Demaine paper cited below -- but I am not familiar with the details of that work, so I cannot vouch for this myself.  Thanks to jbapple for this observation.

Negative result: you cannot avoid some slowdown, for some data structures. To answer your third question, there exist data structures where it is known that making them persistence introduces some slowdown.

In particular, consider an array of $n$ elements.  Without persistence, each array access takes $O(1)$ time (in the RAM model).  With persistence, it has apparently been shown that there is no way to build a persistent array with $O(1)$ worst-case complexity for accessing a random element.  In particular, there is apparently a lower bound showing that fully persistent arrays must have $\Omega(\lg \lg n)$ access time.  This lower bound is asserted on p.3 of the following paper:

Confluently Persistent Tries for Efficient Version Control.  Erik D. Demaine, Stefan Langerman, Eric Price.  Algorithmica, volume 57, number 3, 2010, pages 462–483.

The lower bound is attributed to Mihai Patrascu, but there is no citation to a source that gives the details of the proof of this asserted lower bound.

A rich area of research.  If we take an arbitrary data structure or algorithm, it's a bit of a delicate question whether you can make it persistent with at most $O(1)$ slowdown or not.  I don't know of any general classification theorem.  However, there is a lot of research into ways to make specific data structures persistent, in an efficient way.

There is also a strong connection with functional programming languages.  In particular, every data structure that can be implemented in a purely functional way (with no mutations) is already a persistent data structure.  (The converse is not necessarily the case, alas.)  If you want to squint your eyes, you could take this as some weak sort of partial classification theorem: if it is implementable in a purely functional programming language with the same time bounds as in an imperative language, then there is a persistent data structure with the same time bounds as the non-persistent one.  I realize this probably isn't what you were looking for -- it is mostly just a trivial re-phrasing of the situation.

How to make a persistent array. I won't try to describe the construction for how to build a fully persistent array with $O(\lg n)$ worst-case access time.  However, the basic ideas are not too complicated, so I'll summarize the essence of the ideas.

The basic idea is that we can take any binary tree data structure, and make it persistent using a technique called path copying.  Let's say we have a binary tree, and we want to modify the value in some leaf $\ell$.  However, for persistence, we don't dare modify the value in that leaf in place.  Instead, we make a copy of that leaf, and modify the value in the copy.  Then, we make a copy of its parent, and change the appropriate child pointer in the copy to point to the new leaf.  Continue in this way, cloning each node on the path from the root to the leaf.  If we want to modify a leaf at depth $d$, this requires copying $d$ nodes.

If we have a balanced binary tree has $n$ nodes, then all leaves have depth $O(\lg n)$, so this operation on the binary tree takes $O(\lg n)$ time.  There are some details I'm skipping -- to achieve $O(\lg n)$ worst-case time, we may need to rebalance the tree to ensure it remains balanced -- but this gives the gist of it.

You can find more explanations, with pretty pictures, at the following resources:

Read the sections labelled "Binary search trees" and "Random-access structures" (specifically, the tree method) at http://toves.org/books/persist/index.html.
Or, read http://netcode.ru/dotnet/?artID=6592#BinaryTrees and some of the subsequent sections.
Or, read the sections labelled "Functional data structures" and "Path copying" (starting on p.4) of the Demaine paper cited above: http://erikdemaine.org/papers/ConfluentTries_Algorithmica/paper.pdf

That will give you the main idea.  There are extra details to take care of, but the details are out of scope for this question.  Fortunately, this is all standard stuff, and there is lots of information available in the literature on how to build such data structures.  Feel free to ask a separate question if the above resources aren't enough and you want more information about the details of building a persistent array data structure.


Easy proof for context-free languages being closed under cyclic shift The cyclic shift  (also called rotation or conjugation) of a language $L$ is defined as $\{ yx \mid xy \in L \}$. According to wikipedia (and here) the context-free languages are closed under this operation, with references to papers from Oshiba and from Maslov. Is there an easy proof of this fact?

For regular languages the closure is discussed in this form as "Prove that regular languages are closed under the cycle operator".

You can try to use pushdown automata. Given a pushdown automaton for the original language, we construct one for the cyclic shift. The new automaton operates in two stages, corresponding to the $y$ and the $x$ part of the word $yx$ (where $xy$ is in the original language). In the first stage, whenever the automaton would like to pop a non-terminal $A$, it can instead push a non-terminal $A'$; the idea is that at the end of the first stage, the stack would contain, in reverse order, the symbols that are found in the stack after reading $x$ by the original automaton. In the second stage (the switch is non-deterministic), instead of pushing a non-terminal $A$, we are allowed to pop a non-terminal $A'$. If the original automaton can indeed generate the stack upon reading $x$, then the new one would be able to exactly pop the entire stack.

Edit: Here are some more details. Suppose we are given a PDA with alphabet $\Sigma$, set of states $Q$, set of accepting states $F$, non-terminals $\Gamma$, initial state $q_0$, and a set of allowable transitions. Each allowable transition is of the form $(q,a,A,q',\alpha)$, meaning that when in state $q$, upon reading $a \in A$ (or $a = \epsilon$, in which case it's a free transition), if the top-of-stack is $A \in \Gamma$ (or $A = \epsilon$, which means stack is empty), then the PDA can (it's a non-deterministic model) move to state $q'$, replacing $A$ with $\alpha \in \Gamma^*$.

The new PDA has a new non-terminal $A'$ for each $A \in \Gamma$. For every two states $q,q' \in Q$ and $A \in \Gamma \cup \{\epsilon\}$, there are two states $(q,q',1),(q,q',2,A)$. The starting states (the actual starting state is chosen non-deterministically among them via $\epsilon$-transitions) are $(q,q,1)$. For each transition $(q,a,A,q',\alpha)$ there are corresponding transitions $((q,q'',1),a,A,(q',q'',1),\alpha)$ and $((q,q'',2,B),a,A,(q',q'',2,B),\alpha)$. There are other transitions as well.

For each transition $(q,a,A,q',\alpha)$, there are transitions $((q,q'',1),a,B',(q',q'',1),B'A'\alpha)$, where $B \in \Gamma \cup \{\epsilon\}$ and $\epsilon' = \epsilon$. For every final state $q \in F$, there are transitions $((q,q'',1),\epsilon,A,(q_0,q'',2,\epsilon),A)$, where $A \in \Gamma \cup \{\epsilon\}$.

For every transition $(q,a,\epsilon,q',\alpha)$, there are transitions $((q,q'',2,A),a,B',(q',q'',2,A),B'\alpha)$, where $A \in \Gamma \cup \{\epsilon\}$. For every transition $(q,a,\epsilon,q',A)$, there are transitions $((q,q'',2,B),a,A',(q',q'',2,A),\epsilon)$, where $B \in \Gamma \cup \{\epsilon\}$. For every transition $(q,a,A,q',B)$, there are "generalized transitions" $((q,q'',2,C),a,B'A,(q,q'',2,C),\epsilon)$; these are implemented as a sequence of two transitions through an intermediate new state. Transitions $(q,a,\epsilon,q',\alpha)$ with $|\alpha| \geq 2$ are handled similarly. For every transition $(q,a,A,q',A)$, there are transitions $((q,q'',2,A),a,B,(q',q'',2,A),B)$, where $B \in \Gamma' \cup \{\epsilon\}$. Transitions $(q,a,A,q',A\alpha)$ are handled similarly. Finally, there is a sole final state $f$, and transitions $((q,q,2,A),\epsilon,\epsilon,f,\epsilon)$.

(There might be a few transitions that I missed, and some of the details that I'm omitting are somewhat messy.)

Recall we're trying to accept a word $yx$, where $xy$ is accepted by the original PDA. A state $(q,q',1)$ means that we're at stage 1, at state $q$, and the original PDA is at state $q'$ after reading $x$. A state $(q,q',2,A)$ is similar, where $A$ corresponds to the last $A'$ that was popped. At stage 1, we are allowed to push $A'$ instead of popping $A$. We do that for each non-terminal that is produced while processing $x$, but only popped while processing $y$. At stage 2, we are allowed to pop $A'$ instead of pushing $A$. If we do this, then we have to remember that the top-of-stock is really $A$; this only applies when there are no "temporary" things on the stack, which in the simulated PDA is the same as the top-of-stack being $\epsilon$ or of the form $B'$.

Here is a simple example. Consider an automaton for $x^n y^n$ that pushes $A$ for each $x$, and pops $A$ for each $y$. The new automaton accepts words of two forms: $y^k x^n y^{n-k}$ and $x^k y^n x^{n-k}$. For words of the first form, stage 1 consists of pushing $k$ times $A'$, stage 2 consists of popping $k$ times $A'$, pushing $n-k$ times $A$, and popping $n-k$ times $A$. For words of the second form, we first push $k$ times $A$, then pop $k$ times $A$, push $n-k$ times $A'$, transition to stage 2, and pop $n-k$ times $A'$.

Here is a more complicated example, for the language of balanced parentheses of various types ("()","[]","<>") such that the immediate descendants of each type of parentheses must belong to a different type. For example, "([]<>)" is OK but "()" is wrong. For each "(", we push $A$ if the top-of-stack isn't $A$, for each ")", we pop $A$. Similarly $B$,$C$ are associated with "[]" and "<>". Here is how we accept the word ">)([()]<". We consume ">)", pushing $C'A'$, and transition to stage 2. We consume "(", popping $A'$ and remembering the top-of-stack $A$. We consume "[()]" , pushing and popping $BA$; when pushing $B$, we are aware that the "real" top-of-stack is $A$, and so square brackets are allowed (we wouldn't be fooled by ">)(()<"); when pushing $A$, since the top-of-stack is $B$ (which is not $\epsilon$ or of the form $X'$), then we know that $B$ is also the "real" top-of-stack, and so round parentheses are allowed (even though the shadow top-of-stack is $A$). Finally, we consume "<" and pop $C'$.


turing machine logic instead of something Lets assume I have this turing machine:

And I have a $\Sigma = \{0,1,2,3,4,5\}$.

Now my question is can I simplify the transaction from $A$ to $B$ ?

Is there any way so I can write - when the read value is not $2$, write $x$ and move to right?

You could write $\neq 2 \to x,R$, but you might have to explain somewhere that by that you mean that the transition is taken as long as the symbol read is not $2$.

More generally, you can use whatever notation you want as long as you explain it and it's unambiguous.

This is the answer of a practical mathematician. Your professor could have different ideas.


What is the practical relevance of textbook mutual exclusion algorithms? There's been a fair amount of research on mutual exclusion algorithms - e.g. a lot of it is presented in classic textbooks such as The Art of Multiprocessor Programming, where an entire chapter is devoted to them.

I'm wondering what are the practical situations where one might need these algorithms during engineering of a concurrent system, rather than use typical language- and OS-provided synchronization primitives (say, provided by the pthread library)?

I can think of many special cases where I'd imagine the standard primitives are not specifically tuned for them, e.g. "one frequent reader and one infrequent writer", or vice versa, or "exactly one write operation, many readers", etc. - are any of the textbook mutual exclusion algorithms significantly better in practice in such situations?

To put it shortly: Which mutual exclusion algorithms are of practical relevance to an engineer who already has a typical language-provided library of concurrency primitives at their disposal?

Answer: none.  That's not what those sections of Herlihy and Shavit's The Art of Multiprocessor Programming are about.  In the chapters on mutual exclusion Herlihy and Shavit are not giving you alternatives to the pthread library, they are showing you how it is implement the equivalent of the pthread library.

Chapter 2 of Herlihy and Shavit is titled "Mutual Exclusion." It gives a variety of classic algorithms for implementing the equivalent of pthread_mutex_lock() with only sequentially consistent shared memory.  My answers https://cs.stackexchange.com/a/12632/7459 and https://cs.stackexchange.com/a/30249/7459 discuss the importance of these implementations, and have a pointer to one that is practical for use on machines that have no built-in hardware synchronization operations.  (Lamport's 1987 paper in ACM Trans. on Computer Systems).

Chapter 7 of Herlihy and Shavit gives a variety of spin and queue lock implementations of the equivalent of pthread_mutex_lock(), and Chapter 8 expands to discuss pthread_cond_t (condition variables), pthread_rwlock_t (reader/writer locks), and briefly touches on semaphores.  There may be situations in which pthread_rwlock_t could be used as an alternative to pthread_lock_t for performance reasons (but usually not) and in Posix you need to use semaphores for inter-process synchronization.

Chapters 9 through 16 are mostly discussing applications (various kinds of concurrent containers).  Chapter 17 briefly discusses the equivalent of pthread_barrier_t.

All that said, Herlihy and Shavit are two of the most vocal proponents of transactional memory and a variety of kinds of non-blocking (and wait-free) synchronization.  These techniques are intended as alternatives to mutual exclusion in certain cases.  Herlihy and Shavit sprinkle various non-blocking implementations throughout Chapters 9 through 16, and then go into detail on transactional memory in Chapter 18.

Transactional memory and other non-blocking synchronization techniques are intended to deal with the problem that some poorly designed algorithms require threads to hold their critical sections for a very long time.  Transactional memory and truly non-blocking synchronization are not currently practical alternatives in any real situation, but the techniques for transforming blocking data structures into non-blocking data structures are useful in practice for minimizing the amount of time a blocking data structure stays in its critical section.  (Often you can reduce the size of the critical section down to just a couple of machine instructions.)


Express XOR with multiple inputs in zero-one integer linear programming (ILP) In the below post, it is explained how to express xor of two variables as linear inequalities.

Express boolean logic operations in zero-one integer linear programming (ILP)

Naturally, the xor of multiple variables can be expressed using a sequence of multiple 2-input xors but my question whether there is a smarter way to do it?

Here is another way you could try.  To express $y=x_1 \oplus x_2 \oplus \dots \oplus x_n$ (the exclusive-or of $x_1,\dots,x_n$), try the following constraints:

$$y = x_1 + x_2 + \dots + x_n - 2t$$
$$0 \le y \le 1$$

where $y$ and $t$ are constrained to be integers.

There are no guarantees this will work better than a sequence of 2-input xors or a tree of 2-input xors.  Generally, the only way to discover what will work best with an ILP solver is to try each of the operations and see how fast the ILP solver runs.

Caution: If your problem has a lot of XORs, integer linear programming might not be the best tool for the job.  A SAT solver might be more effective.  See also CryptoMiniSat, which is a SAT solver optimized to deal well with XORs.


How to extract a set $C$ that contains $N$ subsets of a set $B$, covers all elements of an external set $A$, but $N$ is minimal? Let $A$ denote a set that contains a relatively large number of different strings. Let $S_i$ denote these strings.

Let $B$ denote a set of sets such that each subset contains a (relatively small, usually not greater than 100) number of different strings. Let $B_i$ denote these subsets.

The problem is the following: is it possible to have an efficient way to obtain a set $C$ that contains a minimal number of different subsets of $B$, but for each $n$, a subset of $B$ that contains a string $S_n$ will be present as a subset of $C$?

Example:

A = ["a", "b", "cd", "e", "eeff", "x", "y", "xyz"];
B = [
["aa", "dce", "n", "e", "f", "y"],
["aa", "b", "n", "e", "f", "y"],
["uxb", "k6", "n", "s", "e", "ffa", "y", "cd"],
["b", "t", "a", "h22", "z"],
["i", "cd", "le8", "a", "t", "eeff", "f"],
["aaa0", "x", "b", "a", "t1", "s"],
["xyz", "a", "n"],
["b", "xyz", "n"],
["eeff", "xyz", "dce", "aa"],
],

We can find multiple possibilities here, e.g. a set with five subsets:

C = [
["aa", "dce", "n", "e", "f", "y"],
["uxb", "k6", "n", "s", "e", "ffa", "y", "cd"],
["b", "t", "a", "h22", "z"],
["aaa0", "x", "b", "a", "t1", "s"],
["eeff", "xyz", "dce", "aa"],
]

(note that for each $x$ such that $0 \le x \le 7$, there is an element of $C$ that contains $A_x$), but the possible solution allows to have only four elements in $C$:

C =
["aa", "b", "n", "e", "f", "y"],
["aaa0", "x", "b", "a", "t1", "s"],
["uxb", "k6", "n", "s", "e", "ffa", "y", "cd"],
["eeff", "xyz", "dce", "aa"]
]

Is it possible to have a relatively efficient method of solving such a problem? I only see a factorial-level complexity (testing each possible combination), which quickly becomes physically impossible to implement. But if $A$ contains millions of elements, and $B$ contains billions of elements, we need another solution...

If you delete all subsets in $B$ that contain no string from $A$, then this is exactly the (Minimum) Set Cover problem, which is NP-hard, meaning that almost certainly no efficient (that is, polynomial-time) algorithm exists.

Testing each possible combination can be done in $O(m2^n)$ time if there are $n$ sets in $B$ and $m$ elements in $A$, which is better than factorial time.  (We don't care about the order of the subsets we select.)


Do you know of a brute-force algorithm for optimizing polynomial expressions? For instance, given the polynomial expression $xy + x + y + 1$ it will output $(x+1)(y+1)$.

Thanks!

"Brute-force" in the context of factoring polynomials may involve factoring of integers, which is a hard problem. Factoring polynomials is easier, e.g. look up "FACTORING MULTIVARIATE POLYNOMIALS VIA PARTIAL DIFFERENTIAL EQUATIONS" by Gao, and "Factoring Multivariate polynomials over the integers" by Wang and Rothschild.


How to convert an NFA with overlapping cycles into a regular expression? If I understand correctly, NFA have the same expressive power as regular expressions. Often, reading off equivalent regular expressions from NFA is easy: you translate cycles to stars, junctions as alternatives and so on. But what to do in this case:

[source]

The overlapping cycles make it hard to see what this automaton accepts (in terms of regular expressions). Is there a trick?

Rather than "reading off" you should employ one of several canoncial methods to do this. By far the nicest I have seen is one that expresses the automaton as equation system of (regular) languages which can be solved. It is in particular nice as it seems to yield more concise expressions than other methods.

I wrote this document explaining the method for students last summer. It directly relates to a specific lecture; the reference mentioned is typical definition of regular expressions. A proof of Arden's Lemma (a needed result) is contained; one for correctness of the method is missing. As I learned of it in lecture I don't have a reference, sadly.

In short: For every state $q_i$, create the equation

$\qquad \displaystyle Q_i = \bigcup\limits_{q_i \overset{a}{\to} q_j} aQ_j \cup \begin{cases} \{\varepsilon\} &,\ q_i \in F \\ \emptyset &, \text{ else}\end{cases}$

where $F$ is the set of final states and $q_i \overset{a}{\to} q_j$ means there is a transition from $q_i$ to $q_j$ labelled with $a$. If you read $\cup$ as $+$ or $\mid$ (depending on your regular expression definition), you see that this is an equation of regular expressions.

Solving it (using Arden's Lemma) yields one regular expression $Q_i$ for every state that describes exactly those words that can be accepted starting in $q_i$; therefore $Q_0$ (if $q_0$ is the initial state) is the desired expression.

Application to the given automaton is left as an exercise; a complete example is included in above linked document.

See also here where I posted a similar answer.


Why is subarray $A[p..k-1]$ empty when $k=p$? I'm working through a proof of correctness for merge sort.

I'm given a loop invariant for a for loop, which makes reference to a subarray $A[p..k-1]$. During the initialization step of the correctness proof, my textbook says "Prior to the ﬁrst iteration of the loop, we have $k=p$, so that the subarray $A[p..k-1]$ is empty".

In other words we're saying $A[p..p-1]$ is empty. Suppose $p=1$, then it's saying $A[1..0]$ is empty. Why is this considered empty? Is it just an axiom that subarray $A[a..b]$ is empty if $a>b$?

It's a convention. One reason for the convention is that the length of an array $A[i..j]$ is $j-i+1$, so if $j=i-1$, we should get an array of length zero. Due to this reason, we sometime consider $A[i..j]$ to be undefined when $j < i-1$; in other cases, the issue does not arise, and $A[i..j]$ is just the empty array whenever $j < i$. In yet other cases, we do not want to allow empty arrays, and then $A[i..i-1]$ is undefined as well.

Since these conventions are not standard (indeed, they are conflicting), if one of them is used, it should be announced beforehand, or when it occurs.


Alternatives to Unit Testing? During a technical interview I was asked about ways to make sure code/software design is functional before deploying to any servers and the only thing I could think of was unit testing. My interviewer pressed me for other ways but I couldn't come up with any alternatives.

There are several ways to ensure product/code quality and functionality before deployment:

Basic functionality testing
Code Review
Static code analysis
Unit Testing
Single user performance testing


Making sense of asymptotic notation Let $W(n)$ and $A(n)$ denote, respectively, the worst case and average case running time of an
 algorithm executed on an input of size $n$.
 Which of the following is always true?
(A) $A(n) = \Omega(W(n))$
(B) $A(n) = \Theta(W(n))$
(C) $A(n) = O(W(n))$
(D) $A(n) = o(W(n))$

Answer: (C).

  What do all these options "mean"?
  I find it hard to reconcile the graphs exemplifying asymptotic notation and abstract situations such as this one.

The easiest way to remember asymptotic notation is to memorize the following table:
$$
\begin{array}{cc}
o & < \\
O & \leq \\
\Theta & = \\
\Omega & \geq \\
\omega & >
\end{array}
$$
For example, if $f(n) = O(g(n))$ then asymptotically and up to a constant multiple, $f(n) \leq g(n)$; formally, there exists a constant $C > 0$ such that $f(n) \leq Cg(n)$ for large enough $n$. In your case, clearly the average case is at most the worst case, and so $A(n) = O(W(n))$.


Are two terms where one is without a $\lambda\beta$ normal form unconvertible in $\lambda\beta$? I know that if you try and make the theory

$$\lambda\beta+\{s = t\ |\text{ s, t are terms without }\lambda\beta\text{ normal forms}\}$$

then that theory becomes inconsistent. Are two terms where one is without a $\lambda\beta$ normal form also unconvertible in $\lambda\beta$, ie can it ever be true that $\lambda\beta \vdash s=t$ if $s$ dosen't have a normal form?

It is trivially the case that two terms can be $\beta$-convertible even though they do not have a normal form.

Consider:

$$((\lambda x.x)\ (\lambda x.x\ x))\ (\lambda x.x\ x)$$

and

$$(\lambda x.x\ x)\ (\lambda x.x\ x).$$

In one step we have
$$((\lambda x.x)\ (\lambda x.x\ x))\ (\lambda x.x\ x)\to (\lambda x.x\ x)\ (\lambda x.x\ x)$$


implementing ExtractMin on a Max-heap in O(log(n)) time Is it possible to implement extractMin on a Max-Heap in O(log(n)) time, and if so how? Or do you need a more elaborate structure like a max-min heap?

Suppose that there is an algorithm that examines a complete max-heap (i.e. one in which all leaves have the same depth) and outputs the minimum without accessing all leaves. Whenever the algorithm examines the value of an internal node, hand it the value 2, and whenever it examines the value of a leaf, hand it the value 1. The algorithm misses at least one leaf $\ell$, and so cannot tell the situation in which all leaves have the value 1 from the situation in which all leaves but $\ell$ have the value 1, and $\ell$ has the value 0.


$st$-path with fewest leaving edges Given an undirected unweighted  multigraph $G=(V,E)$ and $s,t \in V$ find a simple $st$-path $P$ s.t. the number of edges leaving $P$ (i.e. the edges with exaclty one endpoint in $P$ ) is minimized.

Does anybody have any idea how to solve this?
I first thought about replacing edges by two arcs and weight them according to some node degrees but the edges staying in $P$ make life difficult.

Suppose input graph is simple (without parallel edges), now, If you solve your problem, you can check existence of Hamiltonian path, actually if s-t path of cost zero for some pair exists means there is Hamiltonian path and you can check this for all pair of vertices as (s,t), so you are unlucky to have polynomial time algorithm except $P=NP$.


Misunderstanding the Church-Rosser property I am contemplating the Church-Rosser property and I clearly misunderstand it, but I do not exactly know why. If $x$ and $y$ are such that $x \overset{*}{\leftrightarrow} y$, then $x \overset{*}{\rightarrow} y$ and since $y \overset{*}{\rightarrow} y$, we have that both $x$ and $y$ reduce to $y$ (or $x$, for that matter). So, $x \downarrow y$. I am obviously making a mistake, but where?

$\rightarrow$ is an abstract relation on some set ("reduction"). $\overset{*}{\rightarrow}$ is its reflexive transitive closure, $\overset{*}{\leftrightarrow}$ is the associated reflexive transitive symmetric closure, $\downarrow$ is confluence.

If $x$ and $y$ are such that $x \leftrightarrow^* y$, then $x \rightarrow^* y$

This is not true in general. It is not even true if $\rightarrow$ is confluent!

For example, consider the lambda calculus with for $\beta$ reduction. $(\lambda x. x) y \rightarrow y$, therefore $(\lambda x. x) y \leftrightarrow^* y$, but it is not the case that $y \rightarrow^* (\lambda x. x) y$ ($y$ does not reduce to any term).

The statement $x \leftrightarrow^* y$ means that there exists a chain of reductions $x \leftarrow \rightarrow \leftarrow \leftarrow \leftarrow \rightarrow \ldots \rightarrow \leftarrow \leftarrow y$, indiscriminately mixing “reduces to” and “reduced from”. This is a lot coarser than the statement that $x$ and $y$ converge, which is usually written $x \rightarrow^* \leftarrow^* y$. A relation is Church-Rosser if for all $x$ and $y$ such that $x \leftrightarrow^* y$, it is the case that $x \rightarrow^* \leftarrow^*$. Church-Rosser means that whenever there is a chain of reductions in arbitrary directions, then there exists another chain of reductions where all the $\rightarrow$ arrows are to the left of all the  $\leftarrow$ arrows.

  it just seems to me that the reflexive transitive closure of any relation trivially has the C-R property

No. Taking the reflexive transitive closure doesn't help Church-Rosser along. Church-Rosser is in fact a property of the reflexive closure of a relation (if two relations have the same reflexive closure, then one is CR iff the other is) — you can see in the definition that arrows in the same direction are always taken in a group.

For example, a partial order is not in general confluent. Confluence, for a partial order, is the existence of a least upper bound.