How do I call a system like a grammar, but where a rule has to be applied to all matches at once? For example, given rules $\{ a \to x, a \to y \}$ and input $aa$ , I am usually allowed to derive strings $\{ xx, xy, yx, yy \}$. I would like to restrict this to only performing "consistent" rewrites, so that the language would be like $\{ xx, yy \}$. It is evidently possible to synchronize rewrites in distant parts of a sentence within the usual formal grammar setting, but I wonder if this possibility is better explored under a different name or in a different arrangement.

I notice that context-sensitive grammars pose trouble with this "consistency" condition. For example, given a ruleset $\{ aa \to x\}$ and initial string $aaa$, I am not sure if I should allow anything to be derived. Then again, it is entirely possible that only some rules, and specifically some context-free rules, may be enhanced with consistency.

I am rather sure the system I have in mind defines a language, and even that I could with some thinking propose a formal way to rewrite a given grammar so that some select context free rules are made consistent. But I wonder if this is actually widely known under some other name.

Usually, grammar systems where the rules have to be applied in parallel, are called L systems, after the theoretical biologist Aristid Lindenmayer who observed that development in plants must change cells in parallel.

The first example at wikipedia has rules : (A → AB), (B → A), and the string (= line of cells) develop as follows: A →
AB → ABA
 → ABAAB
 → ABAABABA →  ...

Note that in replacing the letters we actually apply a string homomorphism. I think that formally such a system is called D0L-system, with 0 (for zero) to indicate the rules are applied in a context-free manner, i.e., without looking at the neighbours, and D for determinism, in the sense that the mapping applied is a homomorphism, and not a finite substitution.

If one wants to choose between different homomorphisms at various steps of the derivation, we can choose between different homomorphisms. Such a system is usually called DT0L-system, where the T is for tabled: each homomorphism is a table to choose from.

The first DT0L example I could online find, is from the article L Systems by Kari, Rozenberg and Salomaa. Its tables are Td = [a → b, b → bb, c → a] and Tn = [a → c, b → ac, c → c]. In each step we can choose between the two tables.

Starting with a we get b (in both cases) then bb or ac, then bbbb, acac, ba, cc, then b$^8$, acacacac, baba, cccc, bbb, acc, aa and then cc (but that was already generated). Und so weiter und so fort.

PS. An homomorphism (in language theory) is specified as a letter to string mapping, like [a → c, b → ac, c → bb], and then extended to strings, following the mapping letter-by-letter, so aabac → ccaccbb. A finite substitution axtends this by allowing choice in each of the images of the letters, then a letter (and consequently a string) is mapped to a set of strings. Example [a → aa,c ; b → ε,ac,bb]. Now aba maps to the set aaaa, aac, caa, cc, aaacaa, aaacc, cacaa, cacc, aaabba, aabbc, cbbaa, cbbc. I think.


Steps to convert regular expressions directly to regular grammars and vice versa I came across following intuitive rules to convert basic/minimal regular expressions directly to regular grammar (RLG for Right Linear Grammars, LLG for Left Linear Grammars):

Then I came across many examples that claimed to use these rules to prepare regular grammars from given regex. However I was not able to understand how they are actually using these rules, as they directly gave final regular grammar for given regex. So I decided to try some examples step by step and find whats going on.

Below is one such examples which tries to step by step find RLG and LLG for regex $0^*(1(0+1))^*$. At each step, same color is used to match part of regex getting translated into corresponding part in grammar.

Preparing RLG

Notice that rule in first table says $e^*$ gets translated to RLG productions taking form $S\rightarrow eS | \epsilon$. However in example above, we can see that, to emulate * in regex, we have to put $\epsilon$ in step 2 (green color) as indicated by the rule, but also need to add bunch of other stuff in step 4 (blue color), which are not directly indicated by the rule (though somewhat intuitive extension of the rule).

Preparing  LLG

While preparing LLG also, we can see that, to emulate * in regex, we have to put $\epsilon$ (green colored) in step 1 as indicated by the rule, but also need to add bunch of other stuff in step 2 (green colored), which are not directly indicated by the rule (though again somewhat intuitive extension of the rule).

Apart from star closure, there are many stuff that I dont find straight forward or at least requiring extra awareness (that cannot be easily put in step-by-step procedure) while preparing grammar. For example, while preparing RLG, to emulate $0^*$, I can do $S\rightarrow 0S|\epsilon$ as indicated by first table. But in above example, I have to remain extra aware that there is something more $((1(0+1))^*)$ after $0^*$ which forces me to put $A$ in $S\rightarrow 0S | A | \epsilon$ production in step 2. Other facts I should be aware of:

While preparing RLG, I should start from left of the regex
While preparing LLG, I should start from right of the regex

I observed many more such small points which all I need to be aware at each step of preparing grammar. It makes me feel fuzzy.

Am I going correct with this at all? Is there any book which discuss regex to regular grammar direct conversion, giving clear step by step procedure? Or there is simply no such procedure and I am unnecessarily trying to make it up from examples?

As (briefly) indicated by Raphael in a comment, the only difference between an NFA and a linear grammar is formatting. You can use any algorithm which converts a regular expression to an NFA, and produce a right or left linear grammar instead of the NFA, simply by changing the way you produce output.

Specifically, when you are producing an NFA (with any algorithm) you will perform a series of steps of the form "Add a transition labeled $a$ between $P$ and $Q$", where $a$ is either a terminal or $\varepsilon$, and $P$ and $Q$ are states. To "directly" produce a right linear grammar, implement the above step by producing the production $P\to a Q$ if $a$ is a terminal, or
$P\to Q$ if $a$ is ε. Also, implement the step "Mark $Q$ as a final (accepting) state" by outputting the production $Q\to\varepsilon$. (Alternatively, don't put $Q$ in the productions produced for transitions, if you know in advance that $Q$ is a final state.)

If you want to produce a left linear grammar, you need to work with incoming transitions instead of outgoing transitions; for the $a$-transition from $P$ to $Q$, write $Q\to P a$ unless $P$ is the start state, in which case you just use $Q\to a$. (Again, ε transitions are handled by omitting $a$.)

If the unit productions bother you, use an algorithm which produce an ε-free NFA, or produce the NFA and then do an ε closure to eliminate the ε transitions before printing out the grammar.

Any correct regular expression to linear grammar algorithm will be some version of the above procedure (since you could produce the transition table instead of the grammar by once again changing the print format).


Speech vs Music classification I want to determine which parts of an audio file contain speech respectively music.

I hope someone has a made something like this or can tell me where to start. Can you please suggest some method or tutorial for doing the same?

The appropriate technique is machine learning. Some keywords you could search for are "music speech discrimination", and you could look at this survey. (These pointers came from Vor's comment.)


Register model of computation It consists of one read only input memory and write only output medium. The computation proper takes place in a working memory of limited size. When stating that a problem can be solved with a certain number of bits, what we mean is that the working memory consists of that many bits. The input and working memories are divided into words of $w$ bits for a fixed parameter $w$. Random access to to input and working memory is provided. In the context of $n$ words, assume as is common , that $w = \theta(\log{n})$.

Question : What it means "In the context of $n$ words, assume as is common , that $w = \theta(\log{n})$.
"

Link : " Space-efficient Basic Graph Algorithms Link"

The word RAM is a model of computation in which basic operations operate on words. For example, adding two words costs $O(1)$ in this model. In algorithms class, it is often tacitly assumed that basic operations on indices and on data cost $O(1)$. For example, consider the following program for computing the maximum of an array:

calculate-max(A, n):
max = A[1]
i = 2
while i <= n:
  if A[i] > max:
    max = A[i]
  i = i + 1

This program is usually assumed to run in $O(n)$. This means that the following operations should all cost $O(1)$:

Assignment of data points (max = A[1], max = A[i])
Assignment of indices (i = 2, i = i + 1)
Comparison of indices (i <= n)
Comparison of data points (A[i] > max)
Arithmetic on indices (i + 1)

In order to accommodate this in the word RAM model, we need to assume that words have length at least $\Omega(\log n)$, since this is the length of indices such as i above. Usually words of length $\Theta(\log n)$ are enough for performance of an algorithm in the word RAM to match its performance as perceived by the algorithm designer. Therefore the most common word RAM model is the logarithmic cost word RAM, in which words have length $\Theta(\log n)$ (the constant doesn't matter since it only affects the running time by a constant factor).

The only remaining question is – what is $n$? It is usually assumed that $n$ is such that the input is $n$ words long. This definition is a bit circular (since the length of a word depends on $n$), but usually works out nevertheless.


Nodes in a binary search tree that span a range I have a binary search tree of height $h$ with an integer in each leaf.  I also have a range $[\ell,u]$.  I want to find a set of nodes that span the range $[\ell,u]$, i.e., a set $S$ of nodes such that the leaves under $S$ form all (and only) those leaves containing integers in the range $[\ell,u]$.  How large does $S$ need to be, in the worst case, as a function of the height $h$?  How do I find such a set explicitly?

I'm assuming you have parent pointers, you can probably avoid them by maintaining a couple stacks though.

Find the extremal two nodes $\ell \leq p \leq q \leq u$ and their common ancestor $a$ in $O(h)$ time. If nodes $p$ and $q$ are the same, return $S = \{p\}$.

While $p$ is the left child of its parent and its parent is not the common ancestor, let $p := \text{parent}(p)$. Similarly for $q$ but with being the right child as criterion.

Now if $p$ and $q$ are both the direct children of $a$ let $S = \{a\}$ and you are done. Otherwise initialize $S = \{p, q\}$ and repeat:

$p := \text{parent}(p)$
If $p = a$ break.
Add the right child of $p$ to $S$.

And to finish up, do the same for $q$ but adding the left children instead. Note that the first iteration of the above loop can add $p$ or $q$ to the set while it is already in it. If you use an array instead of a proper set you want to make a special case for the first iteration.

In the worst case this adds $2h + O(1)$ elements to $S$. This can be necessary too, consider a full binary tree where the range includes all but the smallest and biggest node.


Analog circuits for neural networks? Neural networks in machine learning are inherently a continuous model of computation. Yet we use digital logic circuits with floating point numbers to "emulate" this continuity.

I am wondering: is there a possiblity to develop an analog-based ASIC for neural networks, which might fit them well due to their inherent continuity. Neural networks are relatively robust to errors anyway, so the error-proneness of analog circuits shouldn't be a problem.

Is there a possibility to develop an analog-based ASIC for neural
  networks?

This had been already implemented a long time ago.

I guess, no one ever seriously supposes that this is impossible. There're many implementations in papers since 70th. They're still not of industry-standard quality, and with some limitations. However, they're real prototypes among them.

  error-proneness of analog circuits shouldn't be a problem

Unfortunately, it's and it's just one of a bunch of issues.

A general view of this field. Analog ASICs is one of the existed hardware bases for implementing neural networks along with digital ASICs, FPGAs, custom on-chip implementations, massive-parallel computers, general-purpose CPUs and GPUs. Moreover, it's not the most popular approach, currently, because of its limitations in precision and storing data overhead. Also, the analog computations aren't the mainstream, so, there's a lack of development and specialists. Analog computational elements are a kind of different world with specific problems for engineers. Hence, their cost-efficient parameters are far behind even common general purpose CPUs and they are in a narrow use.

However, the analog ASICs have positive sides - yes, on a hardware components level, they are immensely close to the neural networks (biological) which have deeper parallelism than mainstream implementations.

A lot of references for further reading can be found here: Omondi, Amos R., eds. FPGA implementations of neural networks. Vol. 365., Springer, 2006.


STCON is NL complete - but why is the reduction in L? I saw the proof for STCON being NL complete here : https://en.wikipedia.org/wiki/St-connectivity

I understand the reduction, but how is it logspace?

I understand each state is of $O(\log(n))$ space. What I don't understand is how I can create the graph in logspace.

I tried to do some kind of DFS, but remembering the states looks like it'd take $\log(n) * \log(n)$ because the longest path is $\log(n)$ and it costs $\log(n)$ to remember each one?

EDIT: to make sure, I do understand the why the language is in NL, but I don't understand how the reduction from lanuage L in NL to STCON is logspace.

You don't need to do DFS. Each branch on the nondeterministic TM corresponds to each possible path from $s$ to any node $v$ of length at most $n$. You also maintain the index of the vertex it is at which takes $O(\log{n})$ space. If at some step the NDTM has reached the node $t$ then you it halts with ACCEPT. If the NDTM has checked $n$ nodes and it has not reached the node $t$ then it REJECTs. So, if $t$ is reachable from $s$ then there is a path from $s$ to $t$ which would correspond to some branch on the NDTM. In this case the NDTM will halt with ACCEPT.

In simple words, each branch of computation needs to maintain a constant number of variables of size $\log n$: current node, counter for number nodes explored so far, etc. We don't care which nodes we have visited, the only thing we care about is the current node and the number of nodes we have visited in order to stop as soon as we visit $n$ nodes (all nodes).

In order to prove that STCON is NL-complete, given a string $w$ we need to convert it into STCON instance using log-space. Let $M$ be a log-space NDTM accepting $L$. We convert the configurations of computation of $M$ on $w$ into a directed graph. Each node corresponds to a single configuration and if there is a legal transition from a configuration $C_{i}$ into a configuration $C_j$ there is an edge between $C_{i}$ and $C_j$. The size of each configuration is $O(\log{|w|})$ since $M$ computes using $O(\log{|w|})$ space. Generating all possible configurations (nodes) and verifying that $C_i$ yields $C_j$, i.e., adding edge, take $O(\log{|w|})$ space.

Note also that we could generate all possible nodes/configurations of length $\log{|w|}$ by going through all possible strings of length $\log{|w|}$ and test if the generated string is a legal configuration. If it is legal then the TM writes it to its output tape. All this is done in $O(\log{|w|})$ space. Similarly you could generate all pairs $(C_i, C_j)$ and check if $C_i$ yields $C_j$. If $C_i$ yields $C_j$ then write it to the output tape as an edge of the output graph. This also takes $O(\log{|w|})$ space.

The key thing is that you don't need to worry about the time complexity whether it takes linear or exponential time. The output space isn't restricted to $O(\log{|w|})$ space either. Once you convert $w$ to an instance of STCON problem, STCON can decide if this instance belongs to $L_{STCON}$.


Enumerate all paths of length 3 in a given tree T Kind help with an algorithm or any refrence to enumerate all paths of length 3 in a given tree T in the shortest possible time.

Let $T$ be a tree on $n$ vertices. Root $T$ in an arbitrary vertex $r$ and let $p(v)$ denote the parent of vertex $v \neq r$ in $T$. For $v \in V$, let $C(v)$ denote the children of $v$ in $T$.

A path $\langle v_1, v_2, v_3, v_4 \rangle$ of length $3$ in $T$ is of exactly one of the following two forms (when the path's traversal direction is ignored):

Type A: $p(v_1) = v_2$, $p(v_2) = v_3$, $p(v_3) = v_4$, or
Type B: $p(v_1)=p(v_3)=v_2$ and $p(v_4)=p(v_3)$.

To enumerate all paths of type $A$ it suffices to perform a DFS visit of $T$. When a vertex $v$ at depth at least $3$ is encountered, return the path $\langle v, p(v), p(p(v)), p(p(p(v))) \rangle$.
This takes $O(n)$ time overall.

To enumerate all paths of type $B$, perform a DFS visit of $T$ and when a vertex $v$ at depth at least $2$ is encountered, return all the paths of the form $\langle v, p(v), p(p(v)), u \rangle$ where $u \in C(p(p(v))) \setminus \{ p(v) \}$.
This requires time $O(n + P)$, where $P$ is the number of paths of type $B$ in $T$.

Overall you can enumerate all the paths of length $3$ in $T$ in time $O(n + P)$.

Notice that $\Omega(n)$ is a lower bound on the time needed by any algorithm since you need to read the input tree. A bad case in which $P=0$ but you still spend $\Theta(n)$ time is a star.


Regular expression for even/odd string on alphabet Given the alphabet $\{ a,b \}$, if I want to build the regular expression for even/odd lenght strings, I can think that an even lenght string is given by some combination of $a$'s and $b$'s, and the letters can be paired, so there are four possibilities: $aa,ab,ba,bb$, the regular expression(for even lenght strings) so is:
$(aa+ab+ba+bb)^* $
But can I write this in this other (more compact) way?
(Using, e.g., the notation of Hopcroft-Motwani-Ullman) given a language $L$,
we write $L^i:=\{ w_1w_2...w_i \ \ \ s.t. w_1,w_2,...,w_i \in L  \}$
Then given that $(a+b)$ is (as a regular expression) the notation for the strings formed by one symbol, $a$ or $b$, then $(a+b)^2$ as in the notation above is
$\{w_1w_2  \ \ \ s.t. w_1,w_2 \in (a+b)\}=\{aa,ab,ba,bb\}$
So i can rewrite the notation for the regular expression for even lenght words as:
$((a+b)^2)^*$
But this holds in general, so if I want the strings of lenght a multiple on $n \in \mathbb{N}$, I can consider:
$((a+b)^n)^*$
As the regular expression.
I feel like this is somehow cheating and that this argument is not valid, but to me it seems correct: because it is true that exponentiation is not an operation in the language of regular expressions, but it is also true that in reality here exponentiation is only the concatenation $n-$times of the regular expression $(a+b)$, so $(a+b)^2=(a+b)(a+b)$, $(a+b)^3=(a+b)(a+b)(a+b)$, which is always a valid operation for regular expressions.

So my question is: Is the first way in which I have expressed the
regular expressions for even-lenght words the most concise way to
write it? And if the second way in which I have expressed it is
correct, can this be generalised for $n$ generic (as I proposed)?

How about an expression for even strings $((a+b)\cdot(a+b))^*$ and deriving the one for odd strings from it: $((a+b)\cdot(a+b))^*\cdot(a+b)$?


What do two non-terminal symbols on the left hand side of a BNF grammar mean? I'm learning BNF, and the text I'm using gives a simple grammar for integer expressions like this:

<expression> ::= <number> | <expression> <operation> <expression>
<operation> ::= + | - | x
<number> ::= <digit> | <digit> <number>
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

This makes sense to me, but then it goes on to show that you can have two non-terminal symbols on the left hand side of expression like this:

e,f ::= n | (e o f)
o ::= + | - | x
n ::= d | d n
d ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

I don't understand what it means to have both e and f on the left hand side: what does it mean and what is the point of it?

That seems unorthodox to me, but I'm certainly not current with all the formal language theory textbooks being used these days.

The point is that in

$$\langle expression\rangle :=\langle number\rangle \;| \;\langle expression\rangle\langle operation\rangle\langle expression \rangle$$

the two instances of $\langle expression\rangle$ on the right-hand side are unrelated to each other. In a derivation, they are derived independently and nothing constrains their derivations. Sometimes we need to refer to them (for example, when we get to semantic analysis) and then it might be convenient to give them different spellings.

I would normally use subscripts:

$$\langle expression\rangle :=\langle number\rangle \;| \;\langle expression_1\rangle\langle operation\rangle\langle expression_2  \rangle$$

but your professor seems to want to be able to say that $e$ and $f$ are aliases for the same non-terminal (but not the same derivation). This seems confusing to me. Is it really so hard to write:

$$e \Rightarrow n \; | \; e_1\; o \; e_2$$


Polytime and polyspace algorithm for determining the leading intersection of n discrete monotonic functions Some frontmatter: I'm a recreational computer scientist and employed software engineer. So, pardon if this prompt seems somewhat out of left field -- I routinely play with mathematical simulcra and open problems when I have nothing better to do.

While playing with the Riemann hypothesis, I determined that the prime gap can be reduced to a recurrence relation based on the intersection of all $n-1$ complementary functions formed by the multiples of each previous prime number (keen observers will note this is a generalization of the Sieve of Eratosthenes). If this makes absolutely no sense to you, don't worry -- it's still frontmatter.

Seeing how these functions related, I realized that the next instance of each prime can be reduced to the first intersection of these functions, recurring forward infinitely. However, I could not determine if this is tractable in polytime and polyspace. Thus: what I'm looking for is an algorithm that can determine the first intersection of $n$ discrete (and, if applicable, monotonic) functions in polynomial time and space. If no such algorithm currently exists or can exist, a terse proof or reference stating so is sufficient.

The closest I can find so far is Dykstra's projection algorithm (yes, that's R. L. Dykstra, not Edsger Dijkstra), which I believe reduces itself to a problem of integer programming and is, therefore, NP-hard. Similarly, if one performs a transitive set intersection of all of the applicable points (as they're currently understood to be bounded), we must still constrain ourselves to exponential space for our recurrence due to the current weak bound of $\ln(m)$ primes for any real $m$ (and therefore, $e^n$ space for each prime $n$).

Globally, I'm wondering if my understanding of the reduction of the problem is wrong. I don't expect to solve the Riemann hypothesis (or any deep, open problem in this space) any time soon. Rather, I'm seeking to learn more about it by playing with the problem, and I've hit a snag in my research.

Determining whether two monotone functions given as programs intersect is non-computable. Similarly, determining the first intersection under the promise that it exists is "arbitrarily hard" (definitely not polytime).

Given a program $P$, define a function $f_P$ which, for input $n$, is $1$ if $P$ stops after $n$ steps or less. The first intersection of $f_P$ and the constant function $1$ is the running time of $P$, if $P$ halts. So no program can decide whether $f_P$ and $1$ intersect.

Similarly, the time hierarchy theorem shows that for no recursive time bound $T$, the first intersection point can be found in time $T$, even under the promise that it exists. Using the space hierarchy theorem, you can get the same for space.


Difference between 2f+1, 2f and 3f+1 I am currently reading the Practical Byzantine Fault Tolerance paper. I am unable to completely understand the difference between 2f and 2f+1. If 2f+1 means that a majority of the nodes are non-faulty then what does 2f represent?

$2f$ and $2f + 1$ are just numbers. A set of $2f + 1$ nodes has a majority of non-faulty nodes, as you say; a set of $2f$ nodes can be deadlocked between the non-faulty and faulty nodes. A total of $3f + 1$ nodes are needed in the system to be able to construct a set of $2f + 1$ nodes when up to $f$ nodes are not responding (as outlined in section 3).


How do you prove two languages are equivalent using the definition of acceptance? I need to prove that $L(f(M)) = L(M)\cup \{\varepsilon\}$
where $M$ is a DFA and $f$ is the function $f(M) := (Q\cup \{q_f\}, \Sigma, \delta', q_f, F\cup\{q_f\})$ and $q_f$ is a new state not in $Q$ and

$\delta'(q,a) =
      \begin{cases}
        \delta (q,a)  & \text{if }q\in Q\\
        \delta (q_0,a) & \text{if }q= q_f.
      \end{cases}$

I'm assuming I need to use induction but I'm not sure how to go about it

I don't think you need to use induction, a simpler case analysis will suffice, along with a couple of central observations about the new DFA $f(M)$:

$q_{f}$ is the new start state,
$q_{f}$ is also an accepting state,
$\delta'$ is almost exactly the same as $\delta$ (in a very specific way of course), and
there's no transitions into $q_{f}$.

From this you can argue what happens on input $x$ in two cases:

$x = \varepsilon$, and
$x$ is anything else.


How to derive dependently typed eliminators? In dependently-typed programming, there are two main ways of decomposing data and performing recursion:

Dependent pattern matching: function definitions are given as multiple clauses. Unification ensures that all omitted cases are impossible, and an external solver ensures that recursion is well-founded.
Eliminators: Each inductive datatype $D$ has an associated constant $E_D$, which acts as an induction principle, and as recursive function that decomposes values of type $D$. These are more verbose, but have the advantage of being total (all cases are covered by $E_D$) and terminating by construction.

I've seen eliminators for common datatypes, like $Nat$, where the eliminator is basically mathematical induction, or $List$, where the eliminator is basically a fold.

I've been reading several papers on dependent pattern matching, and many refer to type theories in which datatypes can be defined, and eliminators are provided by the theory. For example, Eliminating Dependent Pattern Matching describes how UTT is based on eliminators, and how pattern matching can be converted to elimination in the presence of axiom $K$. My understanding is that, once a datatype is defined, the theory provides the eliminator.

What I haven't found (or at least, haven't recognized if I've seen it) is a good description of how one can derive the eliminators, both their types and their semantics.

Can someone point me to a reference that describes how one can obtain an eliminator from the definition of a datatype?

The canonical reference for this is Peter Dybjer, Inductive Families, which gives a pretty comprehensive treatment of inductive families based on eliminators.


Given language consisting Turing machines is decidable or not? $$L=\{M\mid \text{there exist }x,y\in\Sigma^* \text{ s.t. }x \in L(M)\text{ and } y \notin L(M)\}\,.$$

I think it's not recursively enumerable because this language reduces to complement of the membership problem. $\langle M,w\rangle$ would be input where $y$ would become $w$ and $x$ belongs to $L(M)$.

Please tell me whether I'm correct or not, and help to solve if I'm wrong.

In other words, $L=\{\langle M \rangle:L(M)\notin \{\phi,\Sigma^*\}\}$. you can show explicit reduction from a language you already know is not in $RE$. for example $\overline{HP}$ (it is a very standard reduction).
or you may use the rice theorem to show that.

I did not understand the reduction you suggested.
The reduction from the language you suggested could be as follows:
$$f(\langle M \rangle,x)=\langle M_x \rangle$$

$M_x$ on input w:

run $M$ on x for |w| steps.
if $M$ accepted then reject, otherwise accept.

Note that $\epsilon \in L(M_x)$ in anycase, so $L(M_x)\neq \phi$. and $L(M_x)\neq\Sigma^{*}\iff x\in L(M)$. the correctness follows.


What does floating point biased notation have to do with 2's complement? During lecture the professor talked about Integer Compare for floats and kept mentioning two's complement.

What's the relation between them?

All I understand is that two's complement can take us from a number to its negative.

IEEE 754 Floating point is a standard way of representing fractions in binary which does not use two's complement.  There's a discussion here about why that is.


Hamming Distance, Bit message My professor told us to try and remember the equation used for an upcoming exam, however I'm struggling to fit the equation into the question:

http://i.stack.imgur.com/RoPYG.png
(need a high reputation to post image)

From the above information can anyone tell me how I'm supposed to slot in values in order to work out the following practise question:

Sixteen-bit messages are transmitted using a Hamming code. How many check bits are needed to ensure that receiver can detect and correct single-bit errors?

Answer given to us is "5 check bits for a total of 21 bits".

Can anyone help me out with this please, as I expect it will come up on the exam, bu with another bit message size.

The professor is asking you to find the lowest r such that the equation is true. At $r=1$, $2^1<17+1$,
$r=2$, $2^2=4<17+2=19$...
$r=4$, $2^4=16<17+4=21$
 and finally $r=5$, $2^5=32\geq17+5=22$.


Why is it that the flow value can increased along an augmenting path $p$ in a residual network? I was learning about Max Flow and Residual Graphs and was wondering if there was a formal proof for the statement:

  the flow value can increased along an augmenting path $p$ in a
  residual network

I was reading the slides linked at the end of question and they seem to omit the most important part of the algorithm which is proving the above claim!

Recall how a residual network is built (which can be referenced on chapter 26 of CLRS):

$$c_f(u,v) = \begin{cases}
      c(u,v) - f(u,v) & if (u,v) \in E, \\
      f(v,u) & if (v,u) \in E \\
      0 & otherwise.
   \end{cases}
$$
also recall that because we don't allow self loops of length 1 or 2 (i.e. if $(u,v) \in E \implies (v,u) \not \in E$, exactly one case in the above definition of residual capacity applies.

I understand that intuitively, the first case encompasses the idea of the additional flow that we can increase in the original graph (since it encompasses the amount of extra flow we can increase) and the second case is suppose to be included for allowing our algorithms to decrease the flow.i.e. sometimes it may be necessary to actually decrease the flow in some edge(s) (or increase the flow in the opposite direction) so that the overall flow increases.

Even though this ideas are clear to me, its not clear how its guaranteed that we can actually increase the overall flow in the original graph $G$ if we choose say, the minimum residual capacity in an augmenting path. In particular, its clear to me if the path only contains edges of case 1 (since increasing the flow along such a path just means increasing the flow such that we are still bellow the capacity, so its trivial to increase the flow), but the second type of edge make it confusing for me. How is it that those edges guarantee the following:

The flow increases overall
No conservation law is broken (flow in = flow out is still obeyed)
No capacity constraint in the original graph is obeyed.

Not sure if there are other properties to check but those are the ones I was able to think of.

This is what I have so far:

Let the smallest residual capacity be $c_f(p) = \min_{(u,v) \in p} \{ c_f(u,v) \}$. If we increase the flow according to it then its clear no capacity constraint is violated. Why? There are only two type of possibilities the edge could have come from:

1) The difference between a capacity and a flow
2) The opposite direction of a flow already on the network.

Consider case 1 first. If we increase the flow, then it means that we decrease difference of the capacity and a flow (i.e. the residual capacity). If this is the case, since we choose the smallest residual capacity as the amount to make the decrease, we don't risk increasing the flow to much because an increase will correspond to a increase in flow such that the flow is less that the capacity on the real network.

If on the other hand, if the edge came because it corresponded to the opposite direction of flow of an edge, then its even easier, because that means that the flow on the original graph will correspond to a decrease not an increase. Since we are decreasing we cannot violate a capacity constraint. Furthermore, since we are choosing the smallest decrease to be made, there is not risk of the flow randomly becoming negative in the original graph (which would correspond to non-sense). Hence, this can't happen either.

Therefore, the capacity constraints are not violated by this choice of change of flow on the network.

The other two conditions, seem a little harder to check. I am sort of stuck on the other two but will keep trying and if I make progress (or not) update the question.

I am learning flow form the following slides based on CLRS:

https://stellar.mit.edu/S/course/6/sp15/6.046J/courseMaterial/topics/topic2/lectureNotes/Network-Flow-Spring15-trunc/Network-Flow-Spring15-trunc.pdf

https://stellar.mit.edu/S/course/6/sp15/6.046J/courseMaterial/topics/topic2/lectureNotes/Network-Flow-II-Spring15/Network-Flow-II-Spring15.pdf

Instead of giving a formal proof I will present some intuition on why augmenting paths increase the flow. Look at the picture below. Let's go through some augmenting path, for example the one painted in black. It increases the flow by some $x$. Then go through another one (that has $c_f(p) = y$) that contains an edge which pulls back some flow (edge $(u, v)$ is present only in residual network). When the red path enters $u$, it increases the flow that comes into $u$ by $y$, but then pulls $y$ units of flow back to $v$, so $v$ can use edge from red path to push those $y$ units somewhere else. So you see that $y$ units came to $u$, $y$ units was withdrawn from $u$, $y$ units came back to $v$ and then $y$ units went through the red path. The property that income flow equals the one that goes out is preserved. Capacity constraints (flow through an edge is not greater than capacity of this edge) are also preserved, because $y$ is the smallest edge weight on the red path. As you can see, going through the red path increases overall flow by exactly $y$, because augmenting path  doesn't decrease the flow anywhere, it rather redirects it in the manner described above. It's like vertex $u$ saying to vertex $v$ "Oh hey, the red path gave me some flow, maybe you ($v$) would take back some of the one you gave me and send it to someone else?". I'd say that adding "redirecting" word somehow to "augmenting path" would clear some misunderstanding about this concepct.

Having this intuition, I think that making a formal proof from it should be fairly easy.


Contrast vs. Brightness question As part of my homework I need to prove (or disprove) that changing the contrast and, then, changing the brightness is (or isn't) the same as changing the brightness and, then, changing the contrast.

Let's assume that we are using gray-scale.

Brightness: the mean of the gray levels.
Changing brightness: adding or decreasing a constant value from every pixel.
Contrast: max - min of the gray-scale levels.
Changing the contrast: stretching the gray levels around the mean.

I understand that you need to disprove it, but I don't know how to do it in a formal way.

Write down brightness and contrast as functions that act on a single gray-scale pixel. As you said, brightness is $b(x) = x + \alpha$ and contrast is $c(x) = \beta(x - x_\text{mean}) + x_\text{mean}$ or something similar. Now all you need to show is that $b \circ c \neq c \circ b$.


How can Chomsky hierarchy be applied to languages with alternated letters? I have the following grammar, which I know it is regular because it can be represented by a finite state automata:
\begin{array}{l}
\mathrm{S} \rightarrow \mathrm{X} \mid \mathrm{Y} \\
\mathrm{X} \rightarrow \mathrm{a} \mathrm{Y} \mathrm{b} \mid \mathrm{ab} \\
\mathrm{Y} \rightarrow \mathrm{b} \mathrm{X} \mathrm{a} \mid \mathrm{ba}
\end{array}
According to Chomsky hierarchy:

Type-3 grammars generate the regular languages. Such a grammar
restricts its rules to a single nonterminal on the left-hand side and
a right-hand side consisting of a single terminal, possibly followed
by a single nonterminal (right regular). Alternatively, the right-hand
side of the grammar can consist of a single terminal, possibly
preceded by a single nonterminal (left regular).

However, I do not find the hierarchy applied to the grammar. Am I missing something?

Every regular grammar produces a regular language.
But:
Not every grammar for a regular language is regular.
In other words, a regular language can be described by any of an infinitude of grammars, some of which are regular and some not.
In this case, you can easily create either a left- or a right-regular grammar for your language. For example:
\begin{array}{l}
\mathrm{S} \rightarrow \mathrm{X} \mid \mathrm{Y} \\
\mathrm{X} \rightarrow  \mathrm{X}  \mathrm{a}\mathrm{b} \mid \mathrm{ab} \\
\mathrm{Y} \rightarrow \mathrm{Y}   \mathrm{b}  \mathrm{a} \mid \mathrm{ba}
\end{array}
Of course, that transformation only preserves the language parsed, not the induced parse trees.


Why the given lexical specification will not process the following strings? I'm taking a Compiler MOOC on my own time. The class is self paced. An answer was given to a question but I can't understand the answer. In fact I'm not even sure how to interpret the question.
Here is the question:

Given the following lexical specification:
$(00)^*$
$01^+$
$10^+$
Which strings are NOT successfully processed by this
specification?

$0111110$
$01100110$
$0001101$
$01100100$

The correct answers are 1 and 2. But I can't figure out why. How do I interpret this lexical specification? Can someone help me out with this.

The strings not processed successfully are 1, 2, and 3. Only string 4 is processed successfully.

I think your problem is not with interpreting the meaning of regular
expressions, but in understanding the process of lexical analysis, at
least as intended in your course.

Normally, a regular expression is supposed to match a string from
beginning to end. But when doing lexical analysis of a program, you
are supposed to cut the program text in small chunks coresponding to
the lexical elements of the language, which in turn can be taken (up
to some details not relevant here) as the terminal alphabet of the
(usually Context-Free) grammar used to define the language you are parsing.

So, during lexical analysis, you have nothing to indicate the end of a
lexical element, as the program text goes on to give the next lexical
element. For example, if you are scanning the string $foobar$, is it
the identifier $f$ followed by $oobar$, or $foo$ followed by $bar$, or
$fo$ followed by $oba$ and $r$. For a strict lexical point of view,
all these possibilities would be correct ... though the grammatical
parser that will use the lexical element can be unhappy with some
choices.

To simplify matters, a simple rule is often followed by scanners performing lexical analysis, called maximal munch rule, or longest match rule. It works as follows:

While recognizing a lexical element, the lexical analyzer
will keep reading the input string as long as it is reading a prefix
of a lexical element, according to the lexical specification, and will
halt when the next symbol to be read would no longer constitute such a
prefix if added to the part of the input already scanned. At that
point, if the scanned string corresponds to a complete lexical element
(i.e. the scanning automaton is in an accepting state), this lexical
element has been recognized. If it is only a prefix of a lexical
element that cannot be completed with what follows into a proper
lexical element, you have a lexical analysis error.

Thus with your example 1, $0111110$, the lexical analyser will start
recognizing the second regular expression $01^+$, and will scan
$011111$ as one lexical element. Then it is left with only $0$ which
is the prefix of a word in the first two regular expression $(00)^*$
and $01^+$. But then the string stops, so that it cannot be part of a
complete lexical element. hence the lexical analysis fails with an
error at that point.

You could say that if you had stopped the first lexical element one
symbol earlier, thus recognizing $01111$. Then you would be left with
$10$ which is recognizable by the third regular expression $10^+$. But
that is not how things work. There is no backtracking (actually, some scanners have more complex rules allowing for some backtrack, for example for the programming language C). Allowing this
would also make thigs a lot more ambiguous as I explained in the
$foobar$ example.

In the second example $01100110$, you get $011$, then $00$, and you
are left with $110$. The first $1$ is a prefix for the regex $10^+$,
but it should then be followed by at least one $0$, which is not
there. Hence lexical analysis fails.

However, the third example $0001101$ should fail too. The reason is
that symbols are read one by one. The first $0$ is a prefix for both
regex $(00)^*$ and $01^+$. But, on scanning the second $0$, we know we
are looking for a lexical element defined by the forst regex
$(00)^*$. Then the third $0$ is ok too, since $000$ is a prefix of
$0000$ which is recognized by the first regex. So it is scanned. But
now we need a $0$, and we find a $1$. So the lexical analysis fails.

My guess is that the designer of the exercise recognize too quickly
that it could work, by stopping one $0$ early (and I did too the first
time I read this). But the computer does not have this global
perception, and proceeds one symbol at a time.

The fourth example $01100100$ works fine, yielding $011$, $00$, and $100$.

If backtracking were allowed, all four strings could be scanned into
lexical elements.

But the fourth string could then be scanned as:

$011$, $00$, $100$, or
$01$, $10$, $01$, $00$

Though you can use a rule that you backtrack only in case of failure,
to avoid such an ambiguous situation.

Of course, there is the possibility that your instructor defined things differently, but this is the best I can do with the information I have.


Does $(a \mid b)^*$ match $a^n$ and $b^n$? I am getting confused by the regular expression $(a\mid b)^*$ as it for sure matches $aab$ and $ab$.

Does $(a\mid b)^*$ also match strings like $aa$, $aaaa$, $bb$ or $bbb$, that is those that use only $a$ or $b$?

Yes: $(a\mid b)^*$ is the concatenation of any number of $a$'s and $b$'s, so the expression matches $a^n$ and $b^n$.

As you can read more about on Wikipedia, the vertical bar $\mid$ is the boolean "or" relation (one or the other must be included in the regular expression), while the asterisk $^*$ indicates that the preceding element is repeated zero or more times. Hence:

$(a\mid b)^*$ is equivalent to $(a\;|\;b)(a\;|\;b)(a\;|\;b)\cdots$ repeated any number of times (even zero).

For each term, you can select either $a$ or $b$, so strings like $aa$, $aaaa$, $bb$ and $bbb$ are valid.  In particular, this expression matches the empty string $\epsilon$, which has zero $a$'s and zero $b$'s.


Definition of space complexity when algorithm cycles. I'm reading side by side my class notes and Papadimitrious' Computational Complexity book. At this point they are talking about space complexity. They give rules for computing space employed in an algorithm that runs on a multi-tape Turing machine:

We count the cells used.
If we don't write in the input, this cells don't count.
If the output cells are written from left to right, they don't count.

The final requirement is expressed differently in Papadimitrious' and my notes. In the books it is written:

  The cursor of the input string does not wander off into the blank
  symbols after the end of the input. It is a useful technical requirement, but not necessary.

In my notes:

  In an algorithm where space is counted, there can exist computations
  that never end, but one can always transform the algorithm into
  another that doesn't cycle.

So how does one measure the space complexity of an algorithm that may cycle forever? Are this statement equivalent to each other?

So how does one measure the space complexity of an algorithm that may cycle forever?

When we say that some language $L$ belongs to some complexity class it is assumed that a TM (algorithm) decides $x \in L$ in finite space and time amount. In other words, the TM/algorithm terminates, i.e. it may not cycle forever. However, an algorithm that loops forever may use finite space,  but it still cannot decide.

But I don't understand the following statement

  In an algorithm where space is counted, there can exist computations that never end, but one can always transform the algorithm into another that doesn't cycle.


Is there a generally accepted name for creating types that select a subset of other types? Tl;Dr;

Given:

type A = { int: foo, int: bar }
type B = select foo from A

What is the name of the typing relationship between A and B?
What is the name of the operation of deriving type B from type A?

Long Version

When we talk of subtyping in programming we typically think of it in terms of whether a new subtype B of a type A is able to substitute for A. However, when you think of it in terms of implementation what you are actually saying is that B can do everything that A can. Typically B does more. It might implement the interface and add new fields and methods of its own.
So despite 'sub' sounding like 'subset' the relationship is more like the subtype enriching the supertype.
We derive the subtype from the supertype. I'm curious about deriving a new type by selecting a subset instead.

Consider two structures:

A = { int: foo, int: bar }
B = { int: foo }

The fields of B are a subset of the fields of A.

Is there a proper name for this relationship?
I would say A includes B.

You could implement A by embedding an instance of B. As in:

C = { B, int: bar }

In a language like Go, C is the same as A. In other languages you need to reference B to get to foo. i.e. C.B.foo rather than C.foo

Another kind of subset relation is subranging. For instance limiting a integer to a range of 0-10.

Q = int
P = int[0..10]

P is a subset of Q as before. You can still say Q includes P.
subranges are a special case of refinement types.

The main language I can think of where creating subsets is central is SQL.
We could define B as:

B = select foo from A

So selection is probably a better term to use than "sub-setting"?
B is not a subtype of A is it cannot be used as a substitute for A.
A is a subtype of B because it can be.
So B is a supertype of A.
I think this misses the essential distinction that we are deriving B from A
rather than the other way around. i.e. the process has a direction:

B = f(A) , where f = selection and B is a supertype of A

vs

subtype = g(supertype), where g is derivation/inheritance.

We also have intersection types which combine two types by producing the subset they have in common. SQL does this with joins. Unification in prolog has a similar effect. Selection is via intersection with a second type. You could view selecting the fields as constructing a set of selectors and which is then intersected with the original set. I'm not sure this is the correct way to look at it though. selection and intersection are not the same. An intersection ignores fields that are not common a selection operation should treat that as an error.

There is also destructuring (assignment) as in:

let x = { 10, 1 }
{y, z} = x

But this has to do with values more than types and the isomorphism between a structure and a generic tuple.

My question is:

Is there a generally accepted name for this kind of 'selection'?
What would you call a type system supporting this kind of relationship?

Bonus discussion questions:

Why is 'selection' not more common in general purpose programming languages as opposed to query languages? Surely they complement each other well?
Are there any interesting languages supporting this? How successful is the feature? (linq is very successful in C# for example)

First, the field-subset model of subtyping, while uncommon in OO languages, is common in PL theory for modelling subtyping. It's often called row subtyping.

I'm not sure if there's a general name for all the other things you've described, but I think the closest fit is refinement types, which come in many flavours.

Liquid types refine types by a boolean predicate, i.e. you can make a type which contains all values from another type satisfying a certain predicate. For example, you could have $\{ i : Int \mid 0 < i < 10 \}$ as a refinement of $Int$.
Datasort Refinements are similar to liquid types, but they constrain a type by the shape of its values. So, you can refine $(List\ Int)$ to  $ T = Cons(Int, Cons(Int, List))$, and $T$ is then the type of all $Int$-containing lists of length 2 or more.

More generally, Set-theoretic types  describe a system where can form types using intersection, union, and negation operations on existing types. Here, there is a close correspondence between subtyping and the subset-relationship between values in a type.

A general comment is that I think you need to be careful distinguishing terms from types. While you're describing sensible operations on types, the SQL example and the Prolog unification example are both operations on terms, and not on types, so they're really something different from what you're describing.

I don't think destructuring assingment has anything to do with the other things, it's just a shorthand for pattern-matching, either where there's only one case, or where we throw an error in all but one case.

Bonus Discussion

Why is this not common? Type-checking is performed often, and adding too many features makes it undecidable. The refinement-types I listed above depend on SMT-solvers for typechecking, since they require solving logical constraints.

Are there langauges that support these? The main ones I can think of are Liquid Haskell and Dependent ML. I'm not sure how often they show up in an object-oriented context, because these are areas under active research, and functional languages are generally faster to incorporate bleeding-edge ideas from PL research.


Why is the period of Mersenne Twister prng $2^{19937}-1$ and not $2^{19968}$? For the Mersenne Twister prng, wikipedia, I feel the period exponent should be the size of the MT array,
$32\cdot 624 = 19968$.

How come the exponent is 19937 instead?

Here is the one-line explanation.

The number of effective bits in MT19937 is 624*32-31=19937. They cannot be all 0. So the period of MT19937 is $2^{19937}-1$.

All notations if not introduced below come from this Wikipedia article. The parameters for MT19937, (w, n, m, r) = (32, 624, 397, 31) will be used from time to time.

Explanation from the recurrence

  The series $x$ is defined as a series of w-bit quantities with the recurrence relation:
  $$x_{k+n}:=x_{k+m}\oplus \left(({x_{k}}^{u} \mid\mid {x_{k+1}}^{l})A\right)\qquad \qquad k=0,1,\ldots$$

Note the lower part of the lowest term $x_k$, ${x_k}^l$ is not used in the recurrence relation. Hence the number of effective bits used by the recurrence is $(k+n-k)w-r=nw-r$. Since 0 is excluded, the theoretical limit of period of Mersernne Twister is $2^{nw-r}-1=2^{19937}-1$.

Detailed explanation.

The above explanation is not rigorous enough because of a lack of proper reference. To convince myself, I followed the established pseudocode implementation.

// Generate the next n values from the series x_i
function twist() {
  for i from 0 to (n-1) {
    int x := (MT[i] and upper_mask)
              + (MT[(i+1) mod n] and lower_mask)
    int xA := x >> 1
    if (x mod 2) != 0 { // lowest bit of x is 1
         xA := xA xor a
    }
    MT[i] := MT[(i + m) mod n] xor xA
  }
  index := 0
}

The code above shows that the internal state of a Mersenne Twister is kept in MT[0], MT[1], ..., MT[n-1], which is an array of n values of w bits each. It seems that the period of a Mersenne Twister should be $2^{nw}=2^{19968}$.

Let us check the situation closely.

Every call to twist() will update the internal state. After each call to twist(), function extract_number() will be called $n$ times, each time extracting from MT[index] one word of w bits to output where index is one of 0, 1, ..., n-1.

How does twist() update the internal state?

the upper w-r bits of MT[0], the lower r bits of MT[1], and all bits of MT[317] are used to update MT[0].
the upper w-r bits of MT[1], the lower r bits of MT[2], and all bits of MT[318] are used to update MT[1].
the upper w-r bits of MT[2], the lower r bits of MT[3], and all bits of MT[319] are used to update MT[2].
...
the upper w-r bits of MT[306], the lower r bits of MT[307], and all bits of MT[623] are used to update MT[306].
the upper w-r bits of MT[307], the lower r bits of MT[308], and all bits of the updated MT[0] are used to update MT[307].
the upper w-r bits of MT[308], the lower r bits of MT[309], and all bits of the updated MT[1] are used to update MT[308].
...
the upper w-r bits of MT[622], the lower r bits of MT[623], and all bits of the updated MT[315] are used to update MT[622].
the upper w-r bits of MT[623], the lower r bits of updated MT[0], and all bits of the updated MT[316] are used to update MT[623].

Note that all bits in the array MT at the start of twist() are used except the lower r bits of MT[0]. So an effective internal state of MT is r bits less than all bits in array MT.  Since an effective internal state can never be all 0, the number of effective internal states is at most $2^{nw-r}-1=2^{19937}-1$, which is the theoretical limit of the period for a linear-feedback shift register like Mersenne Twister.

It is another level of interesting mathematical reasoning how MT19937 attains that theoretical limit of its period.

Another explanation by pseudocode

The following pseudocode is another implementation of Mersenne Twister.

Note the code MT[0] := MT[0] and upper_mask and MT[0] := MT[1] and upper_mask, which limits the number of effective bits in MT[0] to w-r. There are (n-1)w bits in MT[1], MT[2], ..., MT[n-1]. In total, there are (w-r)+(n-1)w = nw-r bits in the (effective) internal state of a Mersenne Twister.

// Adapted from https://en.wikipedia.org/w/index.php?title=Mersenne_Twister&oldid=896072298#Pseudocode by Apass.Jack

// Create a length n array to store the state of the generator
int[0..n-1] MT
int index := n+1
const int lower_mask = (1 << r) - 1 // That is, the binary number of r 1's
const int upper_mask = lowest w bits of (not lower_mask)

// Initialize the generator from a seed, which must be done once before repeated calls to next().
function seed_mt(int seed) {
    index := n
    MT[0] := seed
    for i from 1 to (n - 1) { // loop over each element
        MT[i] := lowest w bits of (f * (MT[i-1] xor (MT[i-1] >> (w-2))) + i)
    }
    MT[0] := MT[0] and upper_mask
}

function temper(int y) {
    y := y xor ((y >> u) and d)
    y := y xor ((y << s) and b)
    y := y xor ((y << t) and c)
    y := y xor (y >> l)

    return lowest w bits of (y)
}

function twist() {
    int x := MT[0]
              + (MT[1] and lower_mask)
    int xA := x >> 1
    if (x mod 2) != 0 { // lowest bit of x is 1
        xA := xA xor a
    }
    x := MT[m] xor xA

    MT[0] := MT[1] and upper_mask
    for i from 1 to (n-2) {
      MT[i] := MT[i+1]
    }
    MT[n-1] := x
}

// Generate the next value from the series MT[]
function next() {
    twist()
    return temper(MT[n-1])
}


Time-constructible functions definition A function $T: \mathbf{N} \rightarrow \mathbf{N}$ is time constructible if $T(n) \ge n$ and there is a Turing Machine $M$ that computes the function $x \mapsto \lfloor T(|x|) \rfloor$ in time $T(n).$

Here $\lfloor m \rfloor$ denotes the binary representation of $m$ for a natural number $m$.

I understand that $T(n) \ge n$ is required in order to give the $M$ sufficient time to read its input. About the mapping $x \mapsto \lfloor T(|x|) \rfloor$: since $x$ is a natural number, does this mean $|x|$ is the number of digits in the decimal representation of $x$?

As an example, let's forget about the the requirement that $T(n) \ge n$. Suppose $T(n) = \log_2 n$. Then, for example, $T(2^{100}) = 100$, but what is $T(|2^{100}|)$ in this case?

$|x|$ here means the length of the string $x$ over an alphabet $\Sigma$. Note that $x$ does not need to be a natural number.

So, $|2^{100}|$ is $100$ (but do remember that you MUST understand that you are encoding the natural number $2^{100}$ into string over finite alphabet) if we want to encode a natural number in binary. Therefore, $T(|2^{100}|) = T(100) = \log_2100$.

It would be type-safer to write $|\lfloor{2^{100}}\rfloor|$


The running time of the knapsack problem is $O(n\cdot \min(B,V))$ and is not polynomial, why? My question is why the dynamic programming of the knapsack problem does run in polynomial time? The question is answered here Why is the O(nW) algorithm for the Knapsack problem not a polynomial one?

I understand the argument of the answer above. Also the answer is given in this book ''The Desing of Approximation Algorithms'' that I am reading. In [pp. 67, §2], the authors said:

  Algorithm 3.1 takes $O(n\cdot \min(B, V))$ time. This is not a
  polynomial-time algorithm, since we assume that all input numbers are
  encoded in binary; thus, the size of the input number  $B$ is
  essentially $\lg B$, and so the running time $O(n\cdot B)$ is
  exponential in the size of the input number $B$, not polynomial.
  $\cdots$

I understand that $O(n\cdot B)$ is exponential in the size of the input number $B$, but also, in my point of view (which is wrong), $O(n\cdot B)$ is exponetial in the size of the input number $n$, i.e., the size of the input $n$ is $\lg n$. Why not? (If I were to represent $n$ in binary I would take $\lg n$ size, no?)

$n$ is not part of the input, $n$ denotes the number of objects in the input.

The input consists of the capacity of the knapsack, a list of objects, each with a value and weight. If there are $n$ objects in the instance then the size of the instance is at least $n$ since each object needs to be represented (with at least one bit). Therefore $n$ is polynomial in the size of the input.

In general, the size of the input (if all weights and values are at most $B$) will be $O(n \log B)$, since there are $n$ objects to represent and representing an object (which is two numbers at most $B$) will take around $2\log B$ bits.


Sensitivity and block sensitivity of specific problem, is there an errata? Arora-Barak exercise 12.4 There's an exercise in Arora-Barak on sensitivity and block sensitivity. The statement of the problem is:

  Let $f$ be a function on $n = k^2$ variables that is an OR of $k$ applications of $g: \{0, 1\}^n \rightarrow \{0,1\}$, all $k$ blocks of variables are disjoint. $g(x_1, \ldots, x_k) = 1$ if there exists $i \in [k-1]$ s.t. $x_i = x_{i=1} = 1$ and $x_j = 0$ for all $j \neq i$. Prove that $s(f) = \sqrt{n}, bs(f) = n/2$.

I am confused about $x_{i=1} = 1$. Is there a typo and should it be $x_{i-1} = 1?$ If it is the case, what about $i=1$? Or is it simply $x_1 = 1?$

Another question is whether $g = 1$ iff the condition holds, or if it is only a sufficient condition.

The definition of $g$ should be: $g(x_1,\ldots,x_k) = 1$ if there exists $i \in [k-1]$ such that $x_i=x_{i+1}=1$ and $x_j = 0$ for $j \neq i,i+1$.

As for your question, whether $g=1$ iff the condition holds, or whether it is just a sufficient condition: in mathematics, when we define something, we use the word "if" to mean "iff". Check your favorite textbook, monograph or paper for many examples.


$L = \{ a^{j!} \mid j \geq1\}$ is not context free by pumping lemma How I use the pumping lemma to prove that the language $L = \{ a^{j!} \mid j \geq1\}$ is not context-free?

Suppose $L$ is context free. Then, by pumping lemma, there exist two integers $h \ge 1$ and $1 \le x \le \min\{h!, c_L\}$, where $c_L$ is a constant depending on $L$, that satisfy the following:

$a^{h!} \in L$
$a^{h!-x} a^{xn} \in L$ for every $n \ge 0$.1

Now you only need to show that, for some value of $n$, $a^{h!-x} a^{xn} \not\in L$.
Equivalently, you want to find a value of $n$ (possibly depending on $h$) such that
$h! + (n-1)x$ cannot be written as $j!$ for any integer $j \ge 1$.

For example, if $h = 1$ then $x=1$ so you can pick $n=0$ to obtain $h! + (n-1)x = 0$.

When $h \ge 2$, you can pick $n=2$ so that $h! + (n-1)x = h! + x$, which is not a factorial of an integer as the following inequalities show:
$$
h! < h! + x \le 2 \cdot h! < (h+1)!
$$

1. This is a consequence of the general form of the pumping lemma and of the fact that all the words in your language contain only the character a.


Discrete fourier transform of a polynomial whose degree is not a power of 2 I need to evaluate a polynomial of degree n at the n cube roots of unity. Simple evaluation would take $O(n^2)$ time. I know that polynomial evaluation can be done in $O(n\log n)$ time using FFT.

But the problem that I am facing is this. FFT only works when $n$ is a power of 2. If I extend my polynomial by appending zeroes at the end, that would not solve my problem because then I would be evaluating my polynomial at cube roots of $m$ (where $m$ is a power of $2$ greater than $n$) which I don't want.

Any ideas on this?

There are FFT algorithms for prime sizes such as Rader's algorithm. Given a factorization of $n$ as a product of (not necessarily different) primes, you can compute the DFT by running Rader's algorithm for each prime, in the same way that the usual FFT works by in effect computing FFTs of size $2$. You can read the details in a paper by Frigo and Johnson which describes the FFTW library, which computes length $n$ DFTs in $O(n\log n)$ for all $n$. You can also just use the library if all you really need to do is compute FFTs (rather than solve some programming exercise in some course).


What is pass-by-value-result and its advantage and disadvantage? I have searched on Google, but I can't quite understand what is pass-by-value-result. What is the advantage and disadvantage of using pass-by-value-result?

If I have a program code like this, what will be the result when parameters are passed by value-result?

#include <stdio.h>

int a=2;
int b=1;

void fun(int x, int y) {
    b=x+y;
    x=a+y;
    y=b+x;
}

void main() {
    fun(b,b);
    printf("%d %d\n",a,b);
}

Note: parameter passing by xxx is sometimes called "pass by xxx" and
sometimes "call by xxx".  I will use both expressions indifferently.

Parameter passing by value-result consists in passing by value when the
subprogram (whatever it is) is called, and then, when it terminates,
assign the current value of the formal parameter in the subprogram
back to the actual parameter if it is a mutable entity, such as a
variable or an array entry. Of course, no such assignment may occur if
the actual parameter is a non mutable value providing entity such as
an expression, a function call, a constant (though some old versions
of Fortran have been known to assign values to constants, so that
printing 3 could actually print 5).

Afaik, fortran was first to use this mechanism (I do not know for
Cobol). It is also available in Ada. Actually, Ada has call by value
(IN parameter) and call by result (OUT parameter). OUT parameters are
not initialized at call, but assign current value of formal parameter
to the actual parameter upon return. Parameter passing by value-result
(IN OUT) is the combination of both. Actually, the case of Ada is more
complicated (at least in its initial versions) because it was
explicitly allowed to implement these parameter passing mechanism with
a call by reference. I am not sure of the current status of the
language. This of course muddles the discussion below.

Comparing parameters passing mechanisms is dependent on the language
considered.

Issues you may want to consider are cost in time or space, readability
and maintenance, compiling issues such as efficiency and optimization,
and also semantics such as determinacy of programs, and also programming
convenience. (I may have forgotten some).

Many of these issue are stongly impacted by aliasing
phenomena. Whenever the same mutable entity (possibly a simple
variable) can be accessed in different ways, it becomes harder to
analyse the program, determine what parts of the computation may
interfere with other parts. When there are several threads of
computation, this may cause race conditions making the computation
dependent on timing. When compiling program, aliasing may make it harder
to get a reliable definition-use relation for performing some
otpimizations.

Hence,I would consider aliasing problems a major issue when comparing
computing mechanisms.

Since you need ways to communicate in programs, assessing a parameter
passing mechanism can only by comparing to alternatives.

Regarding pass-by-value-result, the are only two that I see:

Doing nothing on exit.
Then you can pass information back to the caller only as function
result, or by assigning a global variable visible from both callee
and caller.
Using pass by reference.
Then the formal parameter becomes just
another name, an alias, for the actual parameter, so that the actual
parameter has the value of the formal one upon exit (as well as
before exit).

Issues

Time and space cost

One advantage of call by reference over call by value-result is that
it is often cheaper, especially if the data to be passed is large
(time/space costs of copying). Call by reference may have a time cost
because of indirect addressing, though that can sometimes be optimized
out.

Aliasing

The major drawback of call by reference is all I said about
aliasing. So that may be considered a very good point for
pass-by-value-result.

Side effects and evaluation order

Then call by value-return has a problem when returning the values, as
in your example. If two formal parameters (x and y in the example)
actually get the same actual parameter (b in the example) then the
actual parameter will take on return a value that depends on the order
chosen for returning values. Hence, it is essential to define it.  In
any case, such a situation is a sure indicator of bad programming
practice.

This problem does not exists with call by reference. But call by
reference is a completely different kind of computation, as shown by
executing your example in call by reference.

Returning values is a side-effect on the actual
parameters. Computations with side-effects always raise issues of
order dependence. If the evaluation of actuall parameters entails some
side-effects (for example by calling a function with side-effects),
then the order of evaluation of arguments may have an impact on the
computation. That is why side-effect are to be avoided, or at least
carefully managed.

Objects identity

If you have a language that allows to distinguish identity and
egality, the call by reference wil preserve identity, while call by
value will not.  For example, when you copy an integer (for example by
assignment), there is no way you can distinguish the new copy from the
old one.  But Object-Oriented (OO) languages could let you make a
difference, and have a test for equality (same value) and a test for
identity (same reference).

Well definedness of call by value (irrespective of result)

Another problem is that call by value may not be well defined. You
have to determine what a value is. How deep do you copy an object
implemented with references (pointers) when doing call by value.
When a reference is not followed for copying, it is an open door for
aliasing problems.

I am not saying these issues are untractable, but only that you have
to deal with them consistently throughout the language (consistency
with assigment in particular). And that does not make for a clearcut
answer, independently of the rest of the language, and the style of
programming it supports.

Running the example in call by value-result and call by reference

Notation

    a<==b  a becomes aliased to b
    a==b   a is alias of b  (reminder)
    a<-3   a is assigned the value 3

Call by value-result:

    Call of fun(b,b): x<-1 y<-1 b<-2 x<-3 y<-5 return print 2 (3 or 5)

unpon returning, b ends up with 3 or 5 depending on the order of argument return.

Call by reference:

    Call of fun(b,b) x<==b y<==b b==b<-2 b==x<-4 b==y<-8 return print 2 8


Undecidable definition of pure function? I am trying to come up with a formal definition for functional purity in a simple programming language (think JavaScript). What I've got so far is this:

  DEFINITION: A statement is impure if

  it is an assignment, unless it assigns to a local variable
  OR, it evaluates a call to a function, unless that function is pure
  OR, it is a block containing an impure statement

  DEFINITION: A function is pure if it doesn't contain any impure  statement.

For simplicity, let's ignore assignments altogether and assume that a block is simply an ordered set of statements. (it shouldn't make a difference)

Now, this definition seems to work great until somebody defines a function that refers to itself, e.g.

function fibonacci(n)  {
    if(n == 0)
        return 0;
    else if(n == 1)
        return 1;
    else
        return fibonacci(n - 1) + fibonacci(n - 2);
}

or

function f() { return g(); }
function g() { return f(); }

By the proposed definition, to prove that fibonacci is pure, you need to prove that fibonacci is pure. Similarly in the second example. Thus, the purity of fibonacci, f and g is undecidable, yet intuitively we know that all 3 of these are pure, so this definition must be flawed.

How would I modify this definition to be decidable (and give the intuitively expected answer) even in the presence of recursion?

This question refers to some definitions of functional purity, but they don't seem formal enough to be used as a base for further reasoning.

On undecidability

You attempt to prove that fibonacci is pure in a particular way, and you fail to do so. This does not prove that purity is an undecidable property. All it shows is that this particular way of determining the purity of fibonacci doesn't work.

A property is undecidable if no matter what method you use to calculate it, there is a parameter for which it fails. The possible methods are algorithms implemented on a Turing machine or any equivalent framework (recursive functions, etc.).

Purity is undecidable in general, but you need more language constructs than what you showed. For example, it is easy to reduce purity to halting, which is a well-known undecidable problem:

f;
global := 3;

This code is pure iff global := 3 is never executed, which is equivalent to saying that f doesn't terminate. So if you can decide purity, you can decide halting.

On recursive definitions

Your definition of purity is incomplete. You need to explain in more detail how to deal with recursive functions. To illustrate this, let's consider the following axioms for a property which I'll call cuteness:

If A and B are cute then A; B is cute.
If A, B and C are cute then if A then B else C is cute.
If A, B1, …, Bn are cute then A(B1,…,Bn) is cute.
+, -, == are cute.

Is fibonacci cute? If the list of axioms above is complete, then no, fibonacci is not cute, because a recursive function definition is not cute. All of the axioms above work if I replace “cute” by “terminating”, which shows that adding recursive functions to the mix can radically change the definition.

If I add the following axiom:

If A is cute then function f () { A } is cute.

Then all cute functions are, in fact, pure in the sense of not having assignments as side effects. The axioms above in fact completely capture a strong notion of purity, i.e. if a function is pure then you can prove it using these axioms. The notion of purity defined here forbids all assignments, even if they don't escape their scope.

On defining purity

If you want to allow internal side effects, you need a more complex definition, with a context. Above all axioms were of the form “if these programs have the property then that program has the property too”. More complex properties need to consider programs in context, to describe the variables, types, memory locations, etc. used in the program. The following rules capture purity in a context which defines what variables are allowed to be modified:

If A and B are pure in the context Γ then so is A; B.
If A, B and C are pure in the context Γ then so is if A then B else C is cute.
If A, B1, …, Bn are cute in the context Γ then so is A(B1,…,Bn).
+, -, == are pure in any context.
If A is pure in the context Γ then A is also pure in any superset of Γ.
If A is pure in the context Γ, x1,…,xn then function f (x1,…,xn) { A } is pure in the context A.
If A is pure in the context Γ then x := A is pure in the context Γ, x.

A better way to say “A is pure in the context Γ” might be “Γ captures all the side effects of A”. A program is pure if the empty context captures its side effects.


Why does the given solution to this problem works? How can it's correctness be proven? This is a question asked in Adobe interview:

  Given heights of n towers and a value k. We need to either increase or
  decrease height of every tower by k (only once) where k > 0. The task
  is to minimize the difference between the heights of the longest and
  the shortest tower after modifications, and output this difference.

Link of problem and it's solution: solution and problem

Solution posted at the website(click on the link above):

// C++ program to find the minimum possible
// difference between maximum and minimum
// elements when we have to add/subtract
// every number by k
#include <bits/stdc++.h>
using namespace std;

// Modifies the array by subtracting/adding
// k to every element such that the difference
// between maximum and minimum is minimized
int getMinDiff(int arr[], int n, int k)
{
    if (n == 1)
       return 0;

    // Sort all elements
    sort(arr, arr+n);

    // Initialize result
    int ans = arr[n-1] - arr[0];

    // Handle corner elements
    int small = arr[0] + k;
    int big = arr[n-1] - k;
    if (small > big)
       swap(small, big);

    // Traverse middle elements
    for (int i = 1; i < n-1; i ++)
    {
        int subtract = arr[i] - k;
        int add = arr[i] + k;

        // If both subtraction and addition
        // do not change diff
        if (subtract >= small || add <= big)
            continue;

        // Either subtraction causes a smaller
        // number or addition causes a greater
        // number. Update small or big using
        // greedy approach (If big - subtract
        // causes smaller diff, update small
        // Else update big)
        if (big - subtract <= add - small)
            small = subtract;
        else
            big = add;
    }

    return  min(ans, big - small);
}

// Driver function to test the above function
int main()
{
    int arr[] = {4, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 10;
    cout << "\nMaximum difference is "
        << getMinDiff(arr, n, k);
    return 0;
}

After trying for around an hour. This is the solution I came up with:

  Sort the array in non decreasing order.
  Initialise two pointers, one at the starting(0th index) and other at the end(n-1 th index) of the array. If the difference between the
  values at the two pointers is greater than or equal to twice of k,
  then increment the value at the left pointer by k and decrement the
  value at the left pointer by k. Get the difference between the new
  values and update the variable that stores the minimum answer.
  Increment left pointer and decrement right pointer.
  Repeat steps 2 and 3 until left and right pointers converge to the same address.

But the algorithm I wrote only passed sample test cases. When I looked at the editorial, I could not understand why the solution works the way it does. Can anyone break it down step by step.

Also I read in comments it can be solved in O(N). Would be thankful if someone can put insight if that's possible and how. Also where can I practice similar questions?

There's a simple $O(n\log n)$ solution. It also sounds plausible that there is a linear time solution, but it seems to require a bit of case analysis.

First of all, instead of either decreasing by $k$ or increasing by $k$, we can first decrease all values by $k$, and then either not change the value or increase it by $\Delta := 2k$.

Suppose now that the sorted list is $x_1 < \cdots < x_n$. We first show that without loss of generality, an optimal solution increases a prefix of the sorted list. Indeed, consider a solution $y$ which increases $x_{i+1}$ but not $x_i$. Let us consider an alternate solution $z$ which doesn't increase $x_{i+1}$. Denote by $s(y),s(z)$ the span of the solution, which is the objective we're trying to minimize. If $s(y) \neq s(z)$ then $s(z)$ involves $z_{i+1}$, and so $z_{i+1}$ is an extreme point of $z$. Since $z_i < z_{i+1}$, necessarily $z_{i+1}$ is a maximum. Let $z_j$ be the other extreme point of $z$. Since $y_j = z_j$, we see that $s(y) \geq y_{i+1} - y_j = z_{i+1} + \Delta - z_j = s(z) + \Delta$, and so $z$ improves over $y$. We conclude that any optimal solution which increases $x_{i+1}$ must also increase $x_i$, and so also $x_{i-1},\ldots,x_1$, and generally increases a prefix of $x$.

The $O(n\log n)$ algorithm first sorts the list, and then considers all possible increases of prefixes. The idea is to consider what happens when not changing the list, when increasing $x_1$, then $x_1,x_2$, then $x_1,x_2,x_3$, and so on. At each point of this process, we need to know the span of the solution under consideration. When increasing $x_1,\ldots,x_i$, the minimum is always $x_{i+1}$ (there is no need to consider the case $i=n$). We can determine the maximum in an online fashion: if the maximum is $M$ before increasing $x_i$, then after increasing $x_i$ it is $\max(M,x_i+\Delta)$.

Here is the resulting algorithm, which assumes that we have already sorted the list.

Set $M \gets x_n$ (current maximum).
Set $O \gets x_n - x_1$ (smallest span currently known).
For $i=1,\ldots,n-1$:

Set $M \gets \max(x_i+\Delta,M)$.
Set $S \gets M-x_{i+1}$ (current span).
Set $O \gets \min(O,S)$.

Return $O$.


Bubble sort complexity So I have this code:

  done <- false                                     [1]
  n <- 0                                            [1]
  while (n < a) and (done = false)                  [(n+1)(1+1+1)]
    done <- true                                    [n]
    for m <- (a- 1) downto n                        [n(1+1+1+1)]
       if list[m] < list[m - 1] then                [n]
         tmp <- list[m]                             [n]
         list[m] <- list[m-1]                       [n]
         list[m - 1] <- tmp                         [n]
         done <- false                              [n]
       n <- n + 1                                   [1]
  return list                                       [1]

Am I doing this right? My conclusions are that the inne for-loop runs (n^2 + n) / 2 times and the outher while-loop runs n+1 times. I don't know how to properly argue for that the bubble sort has the complexity O(n^2)

There is just one loop in for, so the number of steps here will be proportional to n not n^2. The outer loop is running in a n proportional number of steps too. So The complexity of your algorithm is n^2.
N.B. : When speaking complexity, you don't have to state (n^2 + n) / 2,just say n^2 because they are the same for big ns.


Is the longest Hamiltonian cycle NP-complete? As I understand it to prove something is NP-complete you have to show that it's NP-hard by reducing and a known NP-complete problem to your problem and also prove that it is in NP which you do showing that an answer can be verified to be correct in polynomial time.

Now for the longest Hamiltonian cycle in a weighted graph, I know how the reduction would work, but I'm confused about how to verify a solution in polynomial time. To verify that the cycle is Hamiltonian is easy but how would I know if a cycle I'm looking at really is the longest?

Any help would be appreciated!

Usually, when we talk about the complexity of an optimisation problem (a problem where want to maximise of mininise some value, here the length of a Hamiltonian cycle), we actually look at the complexity of the decision version of that problem.

Here, the decision version is:

  Does the weighted graph $G$ have a Hamiltonian path with total weight at least $x$?

For this problem, verification of the witness (=solution) is easy: we can easily check whether the solution path has weight at least $x$. So, the decision version is in NP.

To understand why we look at the decision version, first note that NP is a class of decision problems, so only a decision problem can be NP-complete. (although we can construct an analogue of NP for optimisation problems, as in this answer). Solving the optimisation version also solves the decision version, so the optimisation version is at least as hard as the decision version. Since the theory gets easier when working with decision problems, focusing on the decision version is often helpful.


Describing the Bool-And monoid in terms of categories Normally I put the question before the context, but in this case I want to admit
the possibility that the context and my understanding nullify the question.
Plus it helps me think through my question.

I recently started reading Category Theory for Programmers (Bartosz
Milewski), and this is my
understanding of categories: they are "algebraic structures" which consist of
objects and arrows/morphisms between those objects. The morphisms have to obey
the laws of associativity, so

$$ a \rightarrow ( b \rightarrow c ) = ( a \rightarrow b ) \rightarrow c $$

And there must be an identity morphism for each object.

Now, Milewski goes on to explain that monoids (which I'm pretty comfortable with
in the set-theoretic sense) are also viewable as categories. This is the part I
am having trouble with. One of the exercises in the book is to consider the
Boolean-and monoid (booleans with the and operator) as a category:

  Represent the Bool monoid with the AND operator as a category: List the
  morphisms and their rules of composition.

I want to give some examples, which I'll do in a SML (though I'll borrow Haskell names).

The monoid could be described set-theoretically with the following signature:

signature MONOID = sig
  type m
  val mempty : m
  val mappend : m -> m -> m
end

Further, the monoid for booleans with the and operator would be given as

structure BoolAnd : MONOID = struct
  type m = bool
  val mempty = true
  fun mappend x y = x andalso y
end

So, here is my understanding of this monoid as a category and its morphisms: is
it correct?

The objects in the category are booleans (true and false) and functions from
booleans to booleans
BoolAnd.mappend is a morphism from the former to the latter
mappend true is an identity morphism for the function objects in the
category (I say "an" because isn't the actual identity function fun id x = x
also an identity morphism for the functions, thanks to polymorphic types? Or
does that not count in category-land? I know that mappend true is equivalent
to the identity function under composition of functions with type bool -> bool.)
the identity morphism for boolean objects appears to be just fun id (b:bool) = b
the given identity morphisms should be associative:

(* example, not proof *)
- open BoolAnd;
- (id o (mappend true)) o not;
val it = fn : bool -> bool
- it false;
val it = true
- id o ((mappend true) o not);
val it = fn : bool -> bool
- it false;
val it = true

The rules of composition seem to be that mappend true is the identity, while
mappend false is a "sink" of sorts, causing the resulting function to always
return false. But id and mappend don't directly compose, because the types
do not align (when id is specialized to booleans, as in the bullets above).

Am I missing something? Is something wrong? Did I give too much detail (there
seems to be an emphasis on avoiding digging in to the objects too much)?

I ask this both to confirm my understanding so that I have a good foundation for
the remainder of the book and also because it took me a long time to identify
the objects and morphisms at work; some of them I am still shaky about.

Monoids are one-object categories. The elements are morphisms, monoid multiplication is composition and the monoid identity is the identity morphism.

In the case of Booleans-with-AND the monoid is $M = (\{\top, \bot\}, \land, \top)$. The category therefore has a single object (we could call it $M$) with two morphisms $\top : M \to M$ and $\bot : M \to M$. Composition is given by $\land$ and the identity morphism is $\top$.

To give a little more context, there is a way to view a monoid in such a way that the objects are the elements of the monoid: as a discrete (no non-identity morphisms) monoidal category. Category Theory for Programmers covers the topic of monoidal categories in Chapter 22, "Monads Categorically".


Find pair of complex numbers with maximal sum Given two lists of complex numbers, is there an efficient algorithm to choose one element from each list such that the magnitude of their sum is maximal?

Observations:

The pairing mechanism creates the Minkowski sum of the two sets.
The convex hull of the Minkowski sum is the Minkowski sum of the convex hulls. (See e.g. previously linked Wikipedia article).
Given a set of points in the plane, the point furthest from the origin must be a vertex of the convex hull.
The convex hull of a set of $n$ points can be found in $O(n \lg n)$ time. (In fact in $O(n \lg h)$ time, where $h$ is the number of points on the convex hull).

  For two convex polygons P and Q in the plane with $m$ and $n$ vertices, their Minkowski sum is a convex polygon with at most $m + n$ vertices and may be computed in time $O(m + n)$ by a very simple procedure...

given in the Wikipedia article.

Combining these observations gives an $O(n \lg n)$ algorithm.


Efficient Algorithms for Destroyed Document Reconstruction I am not certain this is the proper site for this question however I am mainly looking for resources on this topic (perhaps code). I was watching TV and one of the characters had a lawyer who destroyed his documents using a paper shredder. A lab tech said that the shredder was special.

I am not familiar with this area of computer science/ mathematics but I am looking for information on efficient algorithms to reconstruct destroyed documents. I can come up with a naive approach that is brute force fairly easily I imagine but just going through all the pieces and looking for edges that are the same but this doesn't sound feasible as the number of combinations will explode.

Note: By destroyed documents I am talking about taking a document (printed out) and then shredding it into small pieces and reassembling it by determining which pieces fit together.

Your problem is NP-Complete, even for strips (n strips yields (2n)!)  used, so people use heuristics, transforms like Hough and morphological filters (to match continuity of text, but this heavily increases complexity for matching) or any kind of genetic / NN search, Ants Colony Optimization.

For summary of consecutive steps and various algorithm I recommend An Investigation into Automated Shredded Document Reconstruction using Heuristic Search Algorithms.

The problem itself may end up in nasty cases, when document is not fully sharp (blurred, printed with low resolution) and strips width is small and cut by physical cutter with dulled edges, because standard merging methods like panorama photo sticher gets lost and yield improper results. This is due to lost information by missing small strips, otherwise if you have full digital image cut into pieces, it is as hard as Jigsaw puzzle, non-digital image falls into approximate search.

To make algorithm automatic another problem is pieces feeding, rarely you can give axis aligned strips, so to start process it is nice to input all stripes as one picture with pieces lay by hand, this imposes another problem (this one is easy) to detect blobs and rotate them.

By special shredder instead of stripes yield very small rectangles. For comparison, P-1 class shredder gives stripes 6-12mm wide of any length (about 1800mm^2), class P-7 gives rectangles with area less than 5mm^2. When you get rectangles instead of stripes, problem yields (4n)! permutations, assuming one one-sided document, if there are lots of shreds from unrelated documents (no pictures, text only) in one bag, problem is not really tractable.


Complexity of minimizing the maximum inter-cluster distance? Given $n$ non overlapping points $x_i \in \mathbb{Q}$, and an integer $k\geq 2$, what is known about the complexity of finding $k$ means ($a_1, a_2, ..., a_k$) that minimize the maximum inter cluster distance:
$$\min_{a_1, ..., a_k \in \mathbb{Q}}\max_{1\leq j \leq k} \sum_{x_i \in C_j}||x_i-a_j||^2$$

Do we have any polynomial time algorithms for general $k$?, specific $k$ (say $k=2$)? Does the problem have a special name?

Because you are working in one dimension, there's a polynomial-time algorithm, using dynamic programming.  Assume $x_1,\dots,x_n$ are sorted in increasing order.  Notice that each cluster must contain a contiguous sequence of $x$'s, say $x_i,x_{i+1},\dots,x_j$.  Let $f(n_0,k_0)$ denote the minimum of the maximum inter cluster distance for dividing the points $x_1,\dots,x_{n_0}$ into $k_0$ clusters.  Then you can express $f(n_0,k_0)$ in terms of $f(m,k_0-1)$ for $m<n_0$:

$$f(n_0,k_0) = \min_m \max(f(m,k_0-1), \text{variance}(x_{m+1},x_{m+2},\dots,x_{n_0})),$$

where $m$ ranges over $m=1,2,\dots,n_0-1$.

Consequently, you can evaluate $f(\cdot,\cdot)$ at all $O(nk)$ inputs in $O(n^2k)$ time.  You can improve this to $O(nk)$ time by setting $g(n_0,k_0)=\min(f(1,k_0),\dots,f(n_0,k_0))$ and noting

$$\begin{align*}
f(n_0,k_0) &= \max(g(m,k_0-1), \text{variance}(x_{m+1},x_{m+2},\dots,x_{n_0}))\\
g(n_0,k_0) &= \min(g(n_0,k_0-1), f(n_0,k_0)).
\end{align*}$$

You will need to use the fact that you can compute the mean and variance of $x_{m+1},\dots,x_{n_0}$ from the mean and variance of $x_1,\dots,x_m$ and the mean and variance of $x_1,\dots,x_{n_0}$.  You can compute the mean and variance of $x_1,\dots,x_{n_0}$ for all $n_0$ in $O(n)$ time by maintaining a running sum and running sum of squares.


Best design of a software controlled page table: to echo the TLB? I am building some simple system software for the Microblaze FPGA (actually being run on OVPsim at least for now).

The system is to experiment with various memory management regimes.

The first system I want needs to have a very simple paging mechanism and so I want to build a software controlled (only option on a Microblaze) page table.

Is the easiest option just to echo the TLB hardware design - this might waste a few bits but given there are no special circuits optimising this, the simplicity of matching TLB entries to the page table seems like a pretty good choice to me. Is there any reason why I shouldn't do that?

Are there other designs for software controlled page tables that I should look at? (Any papers etc?)

Page table structure (and especially page table structure for software managed page tables) was a hot area of research in the mid 1990s.  At its root this is just the problem of creating a data structure to represent a map from one set of integers (the keys (virtual addresses)) to another set of integers (physical addresses).  So you should expect the answer to have something to do with hash tables or search trees or both.  The "best" choice depends on:

how large your virtual address space is (e.g., 32 vs. 64 bit)
how large your physical address space is
how sparse or dense your mapping is (what fraction of the virtual address space you expect an individual process to use)
how clustered your mapping is (you may only be using 1/10th of 1% of the address space, but all the virtual addresses cluster into one of a few dense regions/segments (the code segment, the stack segment, ...)
the "natural" page sizes supported by your tlb
whether you have address space identifiers (ASIDs), and how big they are (thus dictating how frequently they need to be reused.)
whether you need to be able to use a shared memory abstraction to share data between different processes
whether you have multiple tlbs that need to be kept coherent with some kind of tlb shootdown
whether you have a single process and just need to virtualize that single process's address space over a backing store, or whether you are using paging to provide protection between multiple processes
where and how you are going to store information about pages that have been moved to backing store
(and more, like how you want to choose pages to replace)

Here are some good things to read:

  Huck, Jerry; Hays, Jim: Architectural Support for Translation Table Management in Large Address Space Machines, Int'l Symp Comp Arch (ISCA-20):39-50, 1993.  doi:10.1145/165123.165128.

For machines with virtual address spaces that are much larger than the physical address space the inverted page table is the traditional solution.  The inverted page table has exactly as many entries as there are physical pages.  The entry records the virtual address mapped to that physical address, and also includes a link pointer.  You look up a virtual address by hashing it to find a starting entry in the inverted table, then searching the linked list starting at that entry until you either find the virtual address in question, or find the end of the list.

There are a number of problems with inverted page tables.  They don't handle having multiple virtual addresses mapped to the same physical address, it is expensive to find all of the physical pages that have been mapped for a particular process (you need to walk the entire table looking for entries with that process's ASID), and you need a different data structure to record information about virtual pages that have been moved to backing store.  From a performance perspective the inverted page table does poorly at leveraging spatial locality because adjacent pages hash to disparate locations in the inverted page table.  The Huck and Hays paper suggests variations on the inverted page table to address some of the inverted page table's shortcomings.

  Talluri, Madhusudhan; Hill, Mark D; Khalidi, Yousef A: A new page table for 64-bit address spaces, ACM Symposium on Operating Systems Principles (SOSP-15):184-200, 1995. doi:10.1145/224056.224071.

This paper suggests a different approach to dealing with the locality problems of the inverted page table.  Essentially the inverted page table is used for super-blocks made up of some number (16 in the paper) of normal pages.  Thus you get the nice behavior of the inverted page table (proportional to the size of physical memory) but get some locality benefits because subsequent tlb misses tend to be for other pages in the same super-block.

  Bala, Kavita; Kaashoek, M Frans; Weihl, William E: Software Prefetching and Caching for Translation Lookaside Buffers, USENIX confernce on Operating Systems Design and Implementation (OSDI-1):18, 1994.

This paper suggests that no matter what structure you use for the page table, you should augment the hardware TLB with a large, direct-mapped, software tlb.  The hardware tlb usually needs to be quite small so suffers from capacity misses.  You try to cover a large percentage of the capacity misses by finding the appropriate entry in the direct-mapped software tlb.  The hope is that the software tlb is relatively quick and covers most accesses, and then you can use a more complicated structure (like a forward-mapped page table) for the few remaining misses.

So there are lots of choices, and there are lots of variables to consider.  The best data structure choice really depends on the characteristics of your particular machine and your particular workload.  You are trying to optimize for a sparse, but chunky, mapping function, trying to make sure you can handle operations beyond just lookup efficiently, and trying to leverage the spatial locality in the address stream to minimize cache misses while accessing the page table.


Why do source and sink have to be distinct in Ford-Fulkerson? Recently I have been studying the Ford-Fulkerson algorithm for determining max flow. I do not see why it is not allowed to have the source vertex be the same as the sink vertex. From what I have heard, doing this allows infinite flow. However if you take a graph where the source (which equals the sink) has no arcs leading into it shouldn't the max flow be $0$?

In a flow network, the source and sink are "special".  The source is defined to have infinite incoming capacity, and the sink is defined to have infinite outgoing capacity -- they are different from all the other networks.  For any node with no incoming edges other than the source, it's true that the flow through that node has to be zero -- but the source is different, because it is special.

Why can't the source and sink be the same node?  Basically, because then you get a different problem with different characteristics.  That other problem is called the circulation problem, and there are algorithms for it.  They are a bit different, though, and your teacher probably doesn't want to confuse you by adding unnecessary complications.