How can I make the following grammar unambiguous Given the below ambiguous grammar how can I make it inambiguous and how can I prove the new modified unambiguous grammar is unambiguous? S -> S + S | S − S | S ∗ S | S / S | (S) | x | y
My attempt: The ambiguity can be corrected by
S -> S + T | T , T ->T - M| M, M * N|N , N / Q | Q , Q-> (I) | x| y|
But I'm unsure how to provide a proof for this and I do not know if the |x|y| will have an affect on making this grammar ambiguous. I was thinking I could do an induction proof but I'm unsure how I would begin.

This is a typical ambiguous grammar for arithmetic expressions. You can write different unambiguous equivalent grammars. For example, if you use the traditional precedences and associativities;
$\begin{align*}
   E &\to E + T \mid E - T \mid T \\
   T &\to T * F \mid T / F \mid F \\
   F &\to x \mid y \mid ( E )
\end{align*}$
You could also go the way of APL: All operations the same precedence, associate to the right.
$\begin{align*}
   E &\to T + E \mid T - E \mid T * E \mid T / E \mid T \\
   T &\to x \mid y \mid ( E )
\end{align*}$
The possibilities are almost endless.
To show the above aren't ambiguous isn't so easy.


Nomenclature for deterministic algorithms that might fail What do you call an algorithm which is

Deterministic
When an answer is returned, it is correct
For some input, the algorithm returns no answer (fails, in bounded time).

Such algorithms crop up a lot in cryptographic attacks, for instance, where a
cipher is deemed broken when an attack (provably or demonstrably) works "most
of the time".

I'm working in a different field (coding theory) with an algorithm of the above kind. For
random, uniformly distributed input, the probability that the algorithm fails
seems to be so low that in practice it can be more or less ignored. However, we
have no succinct characterisation of input which cause failure. Previous work on
this algorithm has called it "a probabilistic algorithm" but I find this an
abuse of the term, since the algorithm is deterministic, once the input is
known.

I do not have an authorative answer but two proposals.

Such algorithms compute partial functions, so you could call them partial or partially correct algorithms.

Working off your literature, the class of algorithms you defined is that of Las Vegas algorithms. Even though the implication  is that the algorithm is randomised it certainly need not be; even though you have access to random bits you don't have to use them.
If you want to stress determinism, you can use deterministic Las Vegas algorithm.


Prove correctness for computing the nth Fibonacci number for the pseudo code How do we prove the correctness of this pseudo code by induction?

fastfib(integer n)
if n < 0 return 0;
else if n = 0 return 0;
else if n = 1 return 1;
else a ← 1; b ← 0;
   for i from 2 to n do
       t ← a; a ← a + b; b ← t;
return a;
end

The idea is that at the end of the $i$th iteration, $a = F_i$ and $b = F_{i-1}$. This is something that you can easily prove by induction. (Usually this sort of condition is called a loop invariant.)


How to generate a number which is divisible by all numbers in a given range? Suppose I want to find a number that is divisible by all 3 digit numbers (100-999), how do I write a code for that. I know only "1" can divide all 3 digit numbers, but I just want to know the logic.

The number you see is known as the least common multiple.


Is it possible to build a heap from the root to the leaves? Most books on data-structures will briefly introduce heaps (aka priority queues) and then move to describe the "trick" allowing heaps to be implemented as arrays.
I've been looking for a way to implement a heap as an actual tree (call it pointers to structs, cons cells etc.)  This would also imply building the heap from the root to the leaves (since it won't be practical to hold references to all the leaves).
With some effort I'm able to make the resulting heap to arrange the nodes s.t. the parent is greater than the children, but I cannot think of a way to also balance it.

If you are interested, the motivation for this exercise is: Prolog and its dialects don't really have arrays (they kind of do, but they are almost immutable).  Besides, in languages where persistent data structures are a big deal, the usual construction of heap would be problematic.

Idea #1
I have a feeling that rotating (switching left and right nodes places) may take care of balancing (still need to try this).

Binary heaps are one possible implementations for priority queues. Although their operations are best understood as binary trees, their implementation as arrays is essential. They are stored efficiently, due to the perfect balance you mention, and do not need explicit pointers to children or parent (as these are found by calculating their index in the array).

There is a very cute data structure (on the implementation level) for priority queues that is based on binary trees, has the same heap ordering of keys, but is not perfectly balanced. They are called leftist trees.
Arbitrary leftist trees can be merged efficiently.
This efficiency is obtained by forcing a height balance between the two subtrees of a node. The shortest distance to a leaf is the measure for this balance.

Perhaps these leftist trees are a better binary tree implementation for priority queues than heaps (which are arrays disguised as trees)?


Minimally satisfying multiple qualitative requirements at once I am trying to design an algorithm that will generate the full list of ways to minimally satisfy multiple requirements, given information on how the individual requirements are fulfilled.

For example, let's say you can either have (1) or not have (0) four different foods: Apple, Banana, Carrot, Donut.

Requirement 1 says "You must have an Apple and a Banana." (1,1,0,0) satisfies this. So do (1,1,1,0), (1,1,0,1), and (1,1,1,1), but these are not minimal solutions, since you could take away the Carrot and/or Donut and still satisfy it.

Requirement 2 says "You must have three foods." (1,1,1,0), (1,1,0,1), (1,0,1,1), and (0,1,1,1) are all minimal solutions for this. (1,1,1,1) is not minimal.

I already have ways of generating the minimal satisfying solutions above. They aren't optimal but the search space for each individual requirement is small enough that it doesn't matter. Here's where it gets sticky: generating a list of ways to minimally satisfy both at once.

The brute-force approach to minimally satisfying both at once is then easy, as long as no requirement turns from satisfied to unsatisfied by adding a food (i.e. there's no requirement that says "You must not have a Donut"). Simply (first) look at all combinations of successful arrays, one from each requirement, and take the maximum of each element. For example, combine (1,1,0,0) from Requirement 1 with (1,0,1,1) from Requirement 2 to get (1,1,1,1) to satisfy both. Then (second) prune out non-minimal solutions by comparing each array that satisfies all requirements against each other to get the minimal solutions (1,1,0,1) and (1,1,1,0).

But this is very slow! The runtime grows very quickly with the number of requirements, or successful arrays per requirement. And it generates a lot of redundant output before pruning (for example, (1,1,0,0) plus either (1,0,1,1) or (0,1,1,1) both make (1,1,1,1)).

I'm at a bit of a loss as to how to attack this differently so as to avoid searching every combination, and would appreciate any help. I only have minimal theoretical-CS training and feel like there's probably some terminology or analogous known algorithm I'm not aware of.

It depends what you mean by "minimal".  You might mean either of the following two:

you want to minimize the number of foods selected (variables set to true).
you want a set of foods that's a valid solution, but where any subset of that set is no longer a valid solution.

I'll discuss solution to both variants of the problem.

Minimizing the size of the set

If you want to minimize the number of foods selected (the number of variables set to true), the problem is NP-hard, so there is not likely to be any algorithm that is both efficient and always provides the optimum answer for all possible instances.

However, don't give up.  There are reasonable approaches.  Your problem can be formulated as an instance of integer linear programming (ILP), and then you can use an off-the-shelf ILP solver to solve it.  ILP solvers have gotten pretty good so they might be adequate.

You have $n$ zero-or-one integer variables $x_1,\dots,x_n$, corresponding to the $n$ foods.  Each requirement then translates to one (or more) linear inequalities.  For instance, the requirement that you must have food #1 and food #2 corresponds to $x_1=x_2=1$.  The requirement that you must have at least three foods corresponds to $x_1+x_2+x_3+x_4 \ge 3$.  Some kinds of requirements take a bit more work to formulate as linear inequalities; see Express boolean logic operations in zero-one integer linear programming (ILP) for some tools you can use.  Then, you want to minimize the objective function $x_1+x_2+\dots + x_n$ subject to those constraints.  An ILP solver will do that for you.

Alternatively, you could use an off-the-shelf pseudo-boolean satisfiability solver.

The ILP solver will generate one minimal solution.  To generate all of them, there are various ways to do that.  For instance, if you know there's a solution with 3 variables set to true and no solution with 2 variables set to true, then you can add the requirement $x_1+x_2+\dots + x_n=3$ and enumerate all solutions to the corresponding integer linear program.

Minimal sets of foods

Alternatively, suppose you want to enumerate all ways to choose a set of foods that is minimal (no proper subset is a valid solution).  This requires different methods.

One way is to find a valid solution, then start removing foods until you can no longer remove any more.  That will be one minimal solution.  To enumerate minimal valid solutions, you can now look for a new solution that is not a superset of any prior minimal solution.  This could be very slow.  One way to find a valid solution is by using an integer linear program (ILP), as above; you can formulate the constraint that the solution must not be a superset of any prior minimal solution as well.

An alternative approach might be to view this as the problem of converting a Boolean formula to DNF form.  I think that each DNF clause corresponds to one minimal subset of foods (of variables that can be set to true).  There are various methods for conversion to DNF form; e.g., Quine-McCluskey, the Espresso logic minimizer.  I haven't thought about this carefully and I don't know for sure whether this will find all minimal solutions.  It appears that in your specific situation, you have a monotone Boolean formula; I don't know whether there are better algorithms for converting monotone Boolean formulas to DNF form.


Clarifications on primitive recursive function definition I am studying primitive recursive functions and there's something that I don't quite understand: let's take the function that computes $x+y$, then, in order to show that $f(x,y)=x+y$ is primitive recursive, my lecture notes give the following equations:

\begin{cases}
   f(x,0)=x \\
   f(x,y+1) = f(x,y)+1
  \end{cases}
this first bunch makes perfect sense to me, on the other hand, looking at the equations down below, I don't get why a new function $g$ is used and also why does it have three parameters, when the sum clearly has only two? Is that $y$ the variable that supposedly holds (partial) results from computation?

\begin{cases}
   f(x,0)=u^1_1(x) \\
   f(x,y+1) = g(y, f(x,y),x)
  \end{cases}

where $g(x_1, x_2, x_3) = s(u^3_2(x_1, x_2, x_3))$.

The first equation is what you would normally write down as a mathematician if you were to define addition in terms of successor. The second equation is the same thing, except it is written in a precise manner so as to make it obvious that this indeed is a definition by primitive recursion. You have to pay close attention to details.

A function $f$ is said to be defined by primitive recursion if we can write its definition in the following form:
$$f(x_1, \ldots, x_k, 0) = u(x_1, \ldots, x_k)\\
f(x_1, \ldots, x_k, n+1) = v(x_1, \ldots, x_k, n, f(x_1, \ldots, x_k, n)$$
where $u$ is a function of $k$ arguments and $v$ is a function of $k + 2$ arguments. Furthermore, $u$ and $v$ must be known to be primitive recursive alrady.

The first equation in your question is not of this form but the second one is. Concretely:

We cannot write $f(x,0) = x$ because "$x$" is not a primitive recursive function, whereas $u_1^1$ is. Again, it does not matter that $u_1^1(x)$ happens to be the same thing as $x$ because we are doing bureaucracy, and no shortcuts are allowed.
We cannot write $f(x, y+1) = f(x,y) + 1$ because the right-hand side is not in the correct form. For it to be in correct form we need to find a suitable $g$ so that $f(x, y+1) = g(x, y, f(x, y)$. Here $g$ must take $y$ as its second argument, even if it does not need it, otherwise we are not following the correct form. With this in mind it is easy to see that $g(a, b, c) = s(u^3_2(a,b,c))$ does the job.

When you try to show that something satisfies a definition (in this case "is primitive recursive") you have to get it exactly in the correct form. Only later, when you already understand what is going on, can you start to make shortucts and wave your hands, and say "it's obvious". Your professor does not think you are at that stage (and you are not, since you asked this question).


Membership problem for context sensitive languages PSPACE-complete I have read that the membership problem for CSL is PSPACE-complete but I couldn't find the proof anywhere. So I tried it myself.

Let's mark the membership problem for CSL as MEM.
First I have to proof that $ MEM \in PSPACE $.
This should be easy, just take Turing Machine that generate words from L in lexicographic order and check if any is the same as the input word w. We can stop with the Turing machine when we reach length w+1.

Seccond, make a reduction from some PSPACE language. Quantified Boolean formula problem (QBF) seems to be suitable for this reduction. I have seen how to make a reduction from MEM to QBF but here I need the opposite. If I had a word w, I could make a formula based on the configuration I must go through to get w and all those configurations would mean true for the QBF. The representation could be just going from the binary code to some formulas.

But when going from the opposite direction, I don't know how to make CSL work from any given formula.

I'm assuming that the context-sensitive language is given to you as a context-sensitive grammar. Summarizing the Wikipedia article, here is how to show that the word problem for context-sensitive grammars is $\mathsf{PSPACE}$-complete.

First, we show that the word problem is in $\mathsf{PSPACE}$. The productions in a context-sensitive grammar cannot decrease the size of the word. Therefore, given a context-sensitive grammar $G$ and a word $w$, we can repeatedly apply productions in reverse, in the hope of eventually reaching the starting symbol $S$. We also keep a counter, and give up after $|\Sigma|^{|w|}$ steps (this ensures that the machine always halts), where $\Sigma$ contains both terminals and non-terminals; the size of this counter is $|w| \log |\Sigma| = O(n\log n)$ (here $n$ is the input size). This puts the word problem in $\mathsf{NSPACE}(O(n\log n)) \subseteq \mathsf{NPSPACE} = \mathsf{PSPACE}$, using Savitch's theorem.

In the other direction, Kuroda showed how to convert a linear bounded automaton (that is, a machine in $\mathsf{NSPACE}(n)$) to a context-sensitive grammar in such a way that the LBA accepts a word iff the CSG accepts it. Given a language $L \in \mathsf{SPACE}(p(n))$, we consider the language $L' = \{x\#^{p(|x|)} : x \in L \}$ obtained by padding $L$, and note that $L' \in \mathsf{NSPACE}(n)$. Kuroda's theorem gives an equivalent context-sensitive grammar $G'$. In order to check whether $x \in L$, we first compute $x' = x\#^{p(x)}$, and then check whether $G'$ accepts $x'$. This gives a polynomial time reduction from any language in $\mathsf{PSPACE}$ to the word problem for context-sensitive grammars, and so the latter is $\mathsf{PSPACE}$-complete.


Is this problem just an application of traveling salesman? If not is it some other already "solved" problem? Description of the problem in question:

Say I have a complete graph with positive weighted edges. 1 vertex is specified as the "end". A subset of the other vertices are designated as "start" vertices.

I want to find paths from each start vertex to the end vertex with the following conditions:

As input, each path is given a maximum number of vertices it can visit. ie a path with a max of 5 vertices can only visit 5 other vertices before going straight to the end.
Each vertex can only be visited by one path
Each path must visit its max number of vertices, as long as there are unvisited vertices still available.
The total combined cost of the paths should be minimized

Basically, I want to find a path from each start vertex to end vertex that hits as many other vertices as possible, limited by each paths max and that each vertex can only be visited once. So it's possible that not all vertices will be hit or that a path won't visit its max number of vertices.

I want to know if and how this problem breaks down into TSP, or some other problem. In general, I want to figure out how to solve this problem but I'm just looking for a place to start.

Any insight would be greatly appreciated.

Thanks a lot

This problem comes down to a transportation problem (actually the Wikipedia article is not very good), although it is not exactly the problem you are stating. As David Richerby stated in the comments, your problem is formulated contradictory, therefore I would suggest a reformulation, where you fix the number of vertices that each path visits. But while reading yourself into the capacitive transport problem, you will find out yourself what changes fit best for your task.
Solving these problems can indeed, as stated by Raphael, be solved via min-cost max-flow algorithms.
When you decided on a new version I am happy to extend my answer to fit your needs.


If a language has a regular grammar, is it regular? If L has a regular grammar, is L always a regular language?

A regular grammar is a formal grammar that is right-regular or left-regular. Every regular grammar describes a regular language.

So would this answer be true?

A regular language can be defined as "a language with a regular grammar". So, yes, the existence of a regular grammar for $L$ means that $L$ is regular. [Note 1]
That doesn't mean that every grammar for $L$ is regular. That doesn't matter for this purpose.
It's important to keep the distinction between languages and grammars clear. In general, we say that a language is X if it has at least one grammar which is X (deterministic, regular, context-free, etc.).
Sometimes, the categorization of grammars is finer (makes more distinctions) than the categorization of languages. A grammar can be left regular or right regular, but a language is simply regular: if it has a left regular grammar, it must have a right regular grammar, and vice versa. Similarly, a grammar might be LR(1), LR(2), etc., but this distinction doesn't apply to languages because if there is an LR(k) grammar for a language, there is also an LR(1) grammar.
This distinction is very important when discussing the relationship between different categories. Failing to make the distinction correctly leads to confusion, because the contexts are very different. For example, there is a simple linear-time algorithm which will tell you if a grammar is regular. However, there is no algorithm which can tell you whether the language recognised by an arbitrary context-free grammar is a regular language.

Notes

I believe the original definition of regular languages was based on Kleene's regular expressions. The concept of regular grammars comes from Chomsky's seminal work, in which he called them "Type 3 grammars". His 1959 paper which introduces this hierarchy of grammars (and, indirectly, of languages) contains the proof that Type 3 languages are the same as what he called "finite state languages" -- languages which can be recognised by a Finite State Automaton.
This equivalence leads some people to define "regular language" as "a language which can be recognised by a FSA", although that definition fails to justify the use of the word "regular". (It is the definition found in Michael Sipser's Introduction to the Theory of Computation, and also on Wikipedia, for example.)
It is also easy to show that the set of languages which can be described by a regular expressions (in Kleene's sense) is precisely the same as the set of languages which can be described with a regular grammar.


Are there algorithms to exactly minimize NFAs which are sometimes efficient? I'm doing some research with NFAs, and I'm wondering there are algorithms which quasi-efficiently minimize them. I realize that this problem is $PSPACE$ hard, so I'm not looking for a polynomial time algorithm.

What I mean by this is an algorithm which may run in exponential time in the worst cases, but which uses some sort of heuristic to speed up the process, albiet not enough to make it exponential.

I'm only using this to try to get a better idea of what the minimal NFAs of certain languages look like. I'm not using it in any production code, so it doesn't need to be blazingly fast.

For example, the Antichains algorithm for NFAs does equivalence testing which is usually fast but sometimes has exponential explosion. I'm looking for something similar, but for minimization.

Note that I'm NOT looking for things like equivalences, etc. which run efficiently but don't produce a minimal NFA.

Bonus points to anyone who find one with an implementation, and quadruple bonus points if it's in Prolog or Python.
If the tool I'm looking for doesn't exist, I'd be happy if anyone gave any old implementation of NFA minimization.

SAT solvers have been pretty good at this. See [1] for more; the method produces a minimal automaton in almost all cases. Following some references, Tsyganov [2] combined the Kameda-Weiner with local search methods.

I don't know if there are readily available implementations out there, but at least [1] describes the reduction to SAT. One can then use any available SAT solver.

[1] Geldenhuys, Jaco, Brink Van Der Merwe, and Lynette Van Zijl. "Reducing nondeterministic finite automata with SAT solvers." Finite-State Methods and Natural Language Processing. Springer Berlin Heidelberg, 2010. 81-92.

[2] Tsyganov, Andrey V. "Local Search Heuristics for NFA State Minimization Problem." International Journal of Communications, Network and System Sciences 5 (2012).


Tips for teaching using Live Coding I am involved in a first year programming and algorithms course. In a recent lecture, I decided to present the material using live coding, which essentially meant that I sit behind the keyboard and write code and evaluate it, using emacs to facilitate the process.

This was quite successful and students commented on how much they appreciated the more (inter)active format. As this was my first attempt using this teaching format, I know that it did not run perfectly. Some of the problems were related to being not as savvy with emacs as I should be, and others were to do with allowing student questions to take me too far from my script. I know I can do better.

  What are some guidelines for giving lectures (and other demonstrations) using live coding lectures?
  What are the pitfalls to avoid?

Here are some tips and pitfalls I've collected after using live coding for a week, and from talking to a colleague.

DOs

Prepare a script to follow and try to stick to it.
Clear the buffers frequently to focus on relevant part.
Start afresh for each new topic.
Use a bigger font.
Master the tool you are using, to avoid wasting too much time on trivialities.
Have background functions precoded. If not particularly relevant, ensure they
can be imported, rather than appearing in the working file.
Ideally work in a language that give you immediate feedback. Languages with an
interactive shell are best in this regard.
When using a typed, give the expected type of the function you are writing. This
provides a guiding light for the students.
Freely make mistakes (though not too many). Step through how these should be fixed.
Don't forget – a picture paints a thousand words: interleave slides and black/whiteboard
work with your coding session.
Have summary slides for the points you've covered
Sometimes, when modifying code, maybe make a copy and modify the copy.
This provides a point of comparison.
Clean up code periodically.
Accept that you will make mistakes and openly allow students to correct you --- this makes
your job easier and empowers them.
Write code in your own style. For example, you may have copied the code from elsewhere.
But this will be hard to reproduce. Better to write it in your own style.
For instance, I always write curried functions, because I program mostly Haskell.
But Standard ML uses the idiom less frequently. Expecting curried functions is
the most common error I make in class.
Physically, make sure you have your space set up well. Good keyboard, at the right height, cables all in the right places, physical obstacles out of the way, etc. Take a minute before you start to get your space working for you, not against you.
One approach is to write whatever students say, even if it is wrong. This get students to do
the coding, and the fixing. It is a good idea to clean the code up at the end. This approach can
create a classroom model of attention and interaction, because students need to pay attention
to follow what is going on.

DON'Ts

Don't optimise your code on the fly and break it in such a way that you
cannot fix it.
Avoid talking to the computer. Talk to the students!
Avoid too much typing, especially of boilerplate code.
Utilise your environment to help you spit out the templates for you.
If you use a text editor, avoid constantly scrolling around. It will cause motion sickness it those trying to follow.
If you use a text editor, before making radical changes to your code, warn students that you are going to do so, so that they can track what is going on.


Of monotone formulas and same ones satisfying certain properties There is the following theoretical computer science, namely:

  For a particular monotone formula $M$ of size $n$, there's an equivalent formula of depth $\text{O}(\text{ln}\,n)$.

(I am reading the original paper in my library, if I have time later I will scan it and add scans of it to this post. My apologies for being unable to find a copy online.)

However, I'm finding myself going from step to step in the proof without really understanding what's going on, lacking intuition, as the paper is quite short and condensing quite a bit of reasoning and motivation, at least I feel. I was wondering if somebody could offer me their explanation of the proof of this result, hopefully with lots of their intuition thrown in so I and others reading can have a greater understanding of a proof?

Spira's result uses the technique of formula balancing. For simplicity, I describe the non-monotone case, the monotone case being similar.

Let $\phi$ be a formula of size $n$. We can think of $\phi$ as a binary tree. In general, $\phi$ need not be balanced. It is not hard to show that $\phi$ always has a vertex $\psi$ corresponding to a subformula of size between $n/3$ and $2n/3$ (proof: descend from the root until you reach a subformula of size smaller than $2n/3$). Replace $\psi$ with a new formal variable $x$. The original formula is equivalent to the formula
$$
(\psi \land \phi|_{x=1}) \lor (\lnot \psi \land \phi|_{x=0}).
$$
(If $\phi$ is monotone, we don't need $\lnot \psi$.) What have we accomplished? At the cost of slightly increasing the size of the formula, we managed to get the two top levels of the formula balanced: the subformulas at depth 2 all have size between $n/3$ and $2n/3$.

We continue this process recursively with all the subformulas at depth 2. The process stops after $O(\log n)$ steps, since the subformulas at depth 2 decrease at a constant rate. Hence the final formula has depth $O(\log n)$, and so size $n^{O(1)}$. At the cost of polynomially increasing the size, we have ensured that it is balanced.


Simple generator of pseudo-random permutations of variable length short sequence The problem in front of me is to write a function (from scratch) to permute n elements, where n is an argument. I decided to break it down to applying Knuth's shuffles algorithm, therefore I needed to write a pseudorandom number generator.

So now my task is to write a simple function F(seed,n) that will help me generate indices for the pseudorandom permutations of n elements. However, the function has to be extremely simple: My constraint is that I can only use the following operators: +,-,*,/,%, specifically, no address access, binary encoding, bits selection etc. - only arithmetic on numbers. That is fine, I went for linear congruental generators and implemented a (a*x+c)%m procedure.

As I started testing F(seed,2) it immediately went apparent that the results oscilate between zero and one with a period of two.

My problem is: how can I adjust F to avoid that behavior? Maybe I should generate the n-permutations in a different manner?

In practice, I am only interested in n=<32

The low bits of a linear congruential generator are notoriously weak. Try to use only the higher order bits. Normally this is done by bit operations, but you can discard the bottom $b$ bits by dividing by $2^b$ and rounding down.


What is the name of the operator that translates from $X\rightarrow(Y\rightarrow Z)$ to $Y\rightarrow(X\rightarrow Z)$? Is there a standard name for the operator that takes a function $f:X\rightarrow(Y\rightarrow Z)$ and returns the function $f':Y\rightarrow(X\rightarrow Z)$ that satisfies, for every $y \in Y$ and $x \in X$, $f'(y)(x) = f(x)(y)$?

The function $$\lambda f.\lambda x.\lambda y.f\;y\;x$$ of type $$\forall X. \forall Y. \forall Z.(X \to Y \to Z) \to Y \to X \to Z$$ is often called flip. This is the case in Haskell (see here), and in some OCaml libraries as well (see here). According to wikipedia, people call this function (or combinator) $C$ in the context of combinatory logic (that name sounds pretty random though).


Find subgraphs that can only be reached by two nodes I want to find subgraphs in a graph that are only connected to the rest of the graph by two nodes; for example, node A is connected to the rest of the graph, as well as node F, but nodes B-E are only connected to each other and A and F (don't have to be fully connected). Is there a name for this? And is there an algorithm for finding such subgraphs? The distance of A and F is defined by their shortest path: for example, if d=4, I would want to find all subgraphs where the shortest path between A-like and F-like nodes is at most 4.

I don't know if there's a name for such subgraphs, but here's something to get you started.
If you require the subgraphs to be connected
A polytime algorithm for $G=(V,E)$ would be: for every possible unordered pair $(A,F)\in \binom{V}{2}$ consider the connected components of the graph induced by $V\smallsetminus\{A,F\}$. Then consider the classes which contain at least a neighbour of $A$ and one of $F$ (this step is required if the original graph was not connected). Then for each subgraph you found you can "add $A$ and $F$ back in" and look for their distance in the graph.
Let's sketch correctness (only the step about the subgraphs we are looking for being the connected components needs to be verified).

All components are solutions: by construction they only share links with themselves and A and F, and are connected.
All solutions are components: they are connected and only connect to the rest of the graph through A and F.

I am guessing you can do much better in runtime, but your problem seems to be in $P$ at least.
If you don't
You need to also consider combinations of the subgraphs found above, but in terms of the minimum distance it doesn't change much.


Expected space consumption of skip lists What is the expected space used by the skip list after inserting $n$ elements?

I expect that in the worst case the space consumption may grow indeﬁnitely.

Wikipedia says space $O(n)$.

How can this be proven one way or another?

In this paper it is proven that there exists a constant $\alpha$ such that the probability of the space exceeding $\alpha n$, is less than $1/2^{\Omega(\sqrt{n})}$. Thefore, the more elements there are, the less likely it is to exceed this space bound.


Can Hall's theorem be applied to scheduling problems? If I have a scheduling problem, is it possible that Hall's theorem can be applied? I was thinking that the graph representation of the scheduling problem can be the preferences of the people / workers getting scheduled. Is there any such result or counter-claim?

A Characterization of Open Shop Scheduling Problems Using the Hall Theorem and Network Flow, a thesis by Arunasri Chitti may provide what you need.

The abstract reads:

  Open shop scheduling problems are combinatorial problems where jobs
  with certain processing requirements on a number of different machines
  must be arranged in such a way that objectives related to completion
  time are optimized. Such problems have applications over a wide
  spectrum including such as communications, routing and manufacturing.

  Many open shop problems are NP-hard but there are a number of special
  cases which possess polynomial solutions in the case of few machines
  or few jobs or when preemption of jobs is permitted. Many such
  solutions are based in the theory of matching or Hall’s theorem, or
  more generally network flow. The primary focus of this thesis is to
  describe a number of polynomial-time solutions which are constructed
  using these related concepts and methods.

The paper discusses the problem of scheduling resources to needs in a reasonably optimized fashion, Open Shop Scheduling, and how a particular subset of those scheduling problems "are a number of special cases that do have polynomial solutions and those solutions often come from the theory of matching, network flow and Hall’s theorem, which are related concepts and methods." See What is an NP-complete in computer science as well as What are the differences between NP, NP-Complete and NP-Hard?. Also see the Wikipedia topics NP-hardness and NP-completeness.

Scheduling in the context of the paper is defined as:

  Scheduling deals with the arrangement of a given set of jobs, on the
  given machine such that the provided resources are assigned to the
  jobs in an optimal way. Scheduling provides us the starting and the
  completion time for each operation or job.

A Scheduling problems in the context of the paper is defined as:

  According to Peter Brucker [1], a Scheduling problem is defined as
  following: Given m machines Mj (j= 1, 2...m) and n jobs Ji (i= 1,
  2…n), a schedule now is allocation of one or more time intervals for
  each job on one or more machines.

The thesis goes on to demonstrate the use of applying flow theory to a particular subset of matching resources to needs using graphs. The thesis concludes with:

  Open Shop Scheduling problem is different from other scheduling
  problems. This shop problem is very closely related to matching.
  Although, we have surveyed number of problems where Hall technique
  works, yet there are unexplored problems where matching is applied.
  The connection between algorithms of parallel machines and open shop
  are more close than other shop problems. In this thesis, we have
  learnt flow techinques are useful and seem to be one of the strongest
  tools available for non-NP Complete scheduling problem.


Complexity calculation using a recurrence relation I just can't solve this problem, I'm new to reccurences. I have this recurrence

$T(n)=n*T(n-1)$
$T(1)=1$

The second term will be:

$T(n-1)=(n-1)*T(n-2)$

And so on.

It's complexity is O(n!) but i don't know how to solve it.

I hope you can help me with an idea!

Hint: Prove by induction on $n$ that $T(n) = n!$.

Note that a recurrence relation doesn't have a complexity. Rather, it defines a function. In many cases, this function is the running time of some algorithm, and then the time complexity of the algorithm is the solution to the recurrence.


Are there (highly) restricted process calculi? Perhaps similar to formal grammar? I've started to read about process calculi (such as CSP and π-calculus). It seems to me that they are extremely general and can represent pretty much any concurrent system, many of which will be unable to "make progress".

I wondered if there were much more restrictive formalisms for describing concurrent processes? Perhaps something close to formal languages augmented with a parallel composition (a kind of tensor product of the joined languages) might work quite well? Maybe, in particular a Parsing expression grammar.

Process calculi seem to generally have a concept of channels on which synchronous messages are exchanged. The set of allowable messages are known as the alphabet of a process, and it seems analogous to the symbol set of a formal language (you'd need to augment the symbols with a send and a receive label).

The possible traces of a process calculus would be analogous to the possible strings of a language.

So, the actual questions: is there something like this in the research literature? Thanks!

I wondered if there were much more restrictive formalisms for describing concurrent processes?

Petri nets are IMO more restrictive than the process calculus and such. They are state-transition systems, which are pretty much like formal grammars (like parsing expression grammars). They all boil down to states and rules / transitions. Petri nets include parallel composition.


Is this graph problem NP-hard / NP-complete? I have a certain kind of graphs. They are DAGs similar to dependency graphs but strictly hierarchical, that is, each node belong to a certain level in the hierarchy and cannot be moved up or down when the graph is laid out onto a plane. The nodes can be arbitrarily exchanged with others in the same level.

Here's an example:

The problem:

Find an ordering (permutation) of the nodes in each level of the hierarchy such that the total number of edge crossings is minimal.

The problem could be, I suppose, rephrased as a decision problem: Given an ordering of nodes in each level, decide whether that ordering is minimal in terms of number of edge crossings.

For example, in the above graph embedding there are 3 edge crossings, however, by reordering the nodes in a certain way we obtain an embedding that only has 1 edge crossing (I believe this is minimum for this particular graph):

(Nodes that have been moved are highlighted.)

The question:

Is this problem NP-hard? I'm having a hard time finding correspondence to one of the more well-known NP-hard/NP-complete problems but at the same time I'm having a hard time finding a polytime solution.

Turns out this is indeed an NP-complete/NP-hard problem according to wikipedia and Eades et al.


Is a computer without RAM, but with a disk, equivalent to one with RAM? Memory is used for many things, as I understand. It serves as a disk-cache, and contains the programs' instructions, and their stack & heap. Here's a thought experiment. If one doesn't care about the speed or time it takes for a computer to do the crunching, what is the bare minimum amount of memory one can have, assuming one has a very large disk? Is it possible to do away with memory, and just have a disk?

Disk-caching is obviously not required. If we set up swap space on the disk, program stack and heap also don't require memory. Is there anything that does require memory to be present?

Sure.  In principle, given appropriate hardware, you could have just a disk, with everything stored on disk.  Any time the CPU did a load or store instruction, there could be some hardware that turns that into a disk read or write.  It'd be extremely slow: on a magnetic disk, each seek takes about 10ms, so you could do about 100 random-access reads and writes per second.

Some systems have flash memory-mapped into their address space.  Flash memory provides non-volatile (persistent) storage.  So, in some ways this resembles what you mention -- though those systems usually also have RAM as well.


Combine the following IP Addresses into a single block I was asked to combine the ip addresses into a single block:
16.27.24.0/26, 16.27.24.64/26, 16.27.24.128/25

I managed to convert the given ip addresses into binary:
00010000.00011011.00011000.00000000 | 00011010
00010000.00011011.00011000.01000000 | 00011010
00010000.00011011.00011000.10000000 | 00011001

I am not quite sure what needs to be done in order to convert it properly.
I believe that in this link it is explained what is supposed to be done. I should do it the way it is explained there. I am not able to access it, but whatever is shown in the preview, that is probably the way it would be gone about. Please help. Thanks

An ip address has two parts: the address and the netmask.

The address is just a 32-bit binary number. E.g. yours:

00010000.00011011.00011000.00000000
00010000.00011011.00011000.01000000
00010000.00011011.00011000.10000000

However, these addresses are very precise, and without any further information point to exactly one address. But we want to be more general, and be able to talk about a whole group of addresses. That is a block, and what the netmask is for.

When I use a netmask of /n, it means 'only look at the first n bits of this address, those are meaningful, the rest can be anything'. Think of it like this, the address we give is full, but then we strike out the most specific parts that can be anything:

  United States,  Middleberge, Otter Lane 5322

In your case, the first 26 or 25 bits matter, so we strike through the last 6 or 7 bits:

00010000.00011011.00011000.00000000
00010000.00011011.00011000.01000000
00010000.00011011.00011000.10000000

But we still need to combine the blocks. Note that the top two lines have the exact same start, but then one ends in a 0 followed by anything, and the other in a 1 followed by anything. But since that exhaustively covers everything, we can just extend the 'anything' part one up to combine them:

00010000.00011011.00011000.00000000
00010000.00011011.00011000.10000000

Here we can do the exact same:

00010000.00011011.00011000.00000000

We can now convert our IP address back to decimal, giving 16.27.24.0. The netmask is 32 - 8 = 24 (because we strike out 8 binary digits). So the full IP address + netmask is 16.27.24.0/24.


Difference between symbolic execution and reachability analysis Now I am confused about symbolic execution (SE) and reachability analysis (RA). As I know, SE uses symbols to execute some code to reach each branch with branch conditions. And RA can be used to find the reachability of each branch, right? When RA is used, we can extract the branch condition for each branch. If so, what's the difference between them? Can they be swift? Are they all static analysis?

Generally, reachability analysis is a goal (determine which points in the code are reachable), whereas symbolic execution is a specific algorithmic technique (a tool for analyzing code).  You can use symbolic execution for reachability analysis, or for other goals.  Conversely, you can use other algorithms for reachability analysis.

Classically, symbolic execution was a static analysis.  However, recently it has been widely used in a hybrid static-dynamic analysis: see, e.g., concolic execution.  These hybrid methods seem to be very effective, but they are not purely static.


TM with double-infinity tape semi-decides the same languages as classical TM Show that a Turingmachine with tapes that are infinite in both directions semi-decides the same languages as a classical TM. Apart from the entry-word, the tapes are filled with empty spaces and the head's on the first letter of the entry-word

Under "classical" TM we understand a TM that has a tape that starts at the first letter and is infinite at the right side.
I don't quite understand what to prove here. The only difference between the two TM's is that I can/can't hit the left border of the tape. I could make this scenario a rejected state in the double infinite TM because it can't happen on the single infinite TM.
Any tips?

The intent of this assignment seems to be to demonstrate that allowing Turing Machines to treat the tape as infinite in both directions will not increase the computational power of the Turing Machine; in other words, that for any unbounded-tape TM, there exists an equivalent classical TM. This means you can't just "reject if we go too far to the left" on the unbounded-tape TM, because our proof has to be applicable to all unbounded-tape TMs, not just ones that conveniently do this.
Understanding the equivalence of these two definitions of TM is important because both definitions are widely used in the academia, and many proofs using TMs are easier on one of these models over the other. Knowing that they are equivalent allows one to pick the easier model for a given situation.
For a basic idea of how to prove these two models of computation equivalent, consider that shifting the entire contents of the tape to the right can be done by a classical TM, allowing it to dynamically claim more space on the left of existing tape contents as needed. You can utilize this behavior to simulate an unbounded-tape TM in a classical TM.


Genetic Algorithms: Converge to best solution for one, few or many environments? Let's say we take someone's garden (A) as the environment. We want a robot to pick up a series of eggs that chickens have laid in the garden, while covering as little ground as possible (those heavy rover tracks damage the turf, you know). So we evolve a solution whereby the genes representing the robot's behaviour (i.e. we are not just evolving some chain of path states/positions) work great in that garden.

All freshly laid eggs in (A) are collected in record time.
Our algorithm has learned some tricks about navigating gardens; like driving a car for the first time. But there is more.

If I now put the same robot in a different garden (B), it may or may not do OK. It depends, I suppose, on how similar (B) is to (A) in certain key factors, i.e., will any of the tricks learned in (A) apply here? The likelihood is it will need new tricks, so I'm going to have evolve it further in (B) if I want anything like an optimal solution. Yet if I don't, at every iteration, continue to test it in (A) too, then I may be losing fitness for (A) in every new generation, yes?

So if I want a algorithm that performs well under a wide variety of circumstances, I am going to have to test it in all of those N circumstances, for all of the M candidates; will I thus need to run MxN tests on each generation? What about circumstances I didn't cover?

Unless you define "wide variety" very precisely and prove that your algorithm is able to abstract over all varieties in the way you want, then yes, you'll have to test it every time. I think for most interesting problems you won't be able to produce such a proof.

For a related entertaining read, check Neural Network Follies. The author describes a project where a neural network was trained to spot tanks in images. Instead the network learned how to tell whether it's sunny or not.


Notations for dealing with generators in algorithms This question is about generators, which are functions that return an item from a (usually very large or infinite) set on demand, an example from Python is:
def all_natural_evens():
    n = 0

    while True:
        yield n
        n += 2

As can be seen, the above function yields the even number n in an infinite loop, in other words, it yields all positive even numbers, but since they are infinite and computer memory is finite, they generate the numbers one by one, on demand (using next(gen) to get the next number of the generator gen, where gen = all_natural_evens()).
I am using generators to build an algorithm and when writing it in Latex, I didn't know how to express this in the algorithm, for ordinary return values there is return, but with generators in Python there is yield and yield from (yield from works like an intermediary generator, it generates from a generator...clearly). Is there any notation anywhere for dealing with this kind of generators?
At the moment I'm using keywords $\text{yield}$ and $\text{yield from}$ in the algorithm's pseudocode and explaining what they do.

There is no standard way of writing pseudocode. Your main goal when writing pseudocode is that the reader understands it. If you are unsure that the reader will understand yield or yield from, explain what these keywords mean for you, and mention that they are borrowed from Python, to give due credit.


Maximum Flow with Binary Capacities Consider the problem of finding a maximum flow from node $s$ to node $t$ in a directed graph where each link has capacity either $0$ or $1$. What is the state of the art regarding how fast this flow can be found?

It seems that the Dinic Algorithm will accomplish this $O \left( m n^{2/3} \right)$ where $n$ is the number of nodes and $m$ is the number of vertices. From table 1 in this paper, it seems reasonable to guess this was still the state of the art in 2001. Is this the best that is currently known?

According to Goldberg's post on the Fortnow–Gasarch blog from 2012, the best algorithm for unit capacity networks is the Karzaon/Dinic/Even–Tarjan algorithm, which runs in time $O(\min(n^{2/3},m^{1/2})m)$ time. The post came after Orlin's $O(nm)$ algorithm. Goldberg and Rao extended this result to any constant capacity (their running time is linear in the logarithm of the maximal capacity).

There is a more recent line of work which gives an approximation to the maximum flow in time $O(m^{1+o(1)})$, but this doesn't make use of any bound on the capacities.


Example of Dependent Types? Say you have 3 objects, a global MemoryStore, which has an array of MemorySlabCache objects, and each MemorySlabCache has an array of MemorySlab objects. Sort of like this:
class MemoryStore {
  caches: Array<MemorySlabCache> = []
}

class MemorySlabCache {
  size: Integer
  slabs: Array<MemorySlab> = []
}

class MemorySlab {

}

But the thing is, this doesn't capture everything. It also needs to capture the fact that each MemorySlabCache has a size, which is used to tell what size the MemorySlab objects are it contains. So it's more like this:
class MemoryStore {
  caches: Array<MemorySlabCache> = []
}

class MemorySlabCache {
  size: Integer
  slabs: Array<MemorySlab<size>> = []
}

class MemorySlab<size: Integer> {

}

Then we create our caches:
let 4bytes = new MemorySlabCache(size: 4)
let 8bytes = new MemorySlabCache(size: 8)
...
let 32bytes = new MemorySlabCache(size: 32)
...
store.caches.push(4bytes, 8bytes, ..., 32bytes, ...)

Does this count as a "dependent type", "a type whose definition depends on a value"? Since the type of the Array<MemorySlab<size>> is dependent on the value assigned to the size field on MemorySlabCache. If not, what is this? What would make it into an example of dependent types?

So, the answer is arguably "yes," this is an example of dependent types. However, the problem with a lot of simple examples that people create for this is that they don't demonstrate non-trivial aspects of dependent typing.
Arguably yours is better in this respect, because the type in question depends on an arbitrary value in MemorySlabCache. However, you never use a MemorySlabCache without a statically known value. So a more interesting example would be like:
let cacheSize = readInteger(stdin)
store.caches.push(new MemorySlabCache(cacheSize))

So, you allow the user to select a cache size at runtime, but the cache size is still recorded in the type, and the type checker statically ensures that all operations make sense with respect to the size, even though the size is not statically known (which is kind of another problem with your example; nothing in it shows how the tracked size matters subsequently).
A somewhat more minor problem is that integers are too easy a structure to 'fake' dependent types for, so examples with them end up under selling what might be feasible with genuine dependent types. For instance, Haskell with some extensions can encode even something similar to my runtime-cache-size example, even though it does not really have dependent types. You can have statically known type-level integers, and create a function that gives you back an appropriate value for a statically typed value based on a runtime integer. However, languages based on dependent type theory generally let types depend on values of arbitrary types, like function types. For these (and other related features), 'faking' is not really feasible.


Is the language of pairs of words of equal length whose hamming distance is 2 or greater context-free? Is the following language context free?
$$L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^+, |u| = |v|, u \neq v, |x| = |y|, x \neq y\} $$

As pointed out by sdcvvc, a word in this language can also be described as the concatenation of two words of the same length the hamming distance of which is 2 or greater.

I think it's not context free but I'm having a hard time proving it. I tried intersecting this language with a regular language (like  $ \ 0^*1^*0^*1^* $ for example) then use the pumping lemma and \ or homomorphisms but I always get a language that is too complicated to characterize and write down.

Note [2019-07-30] The proof is wrong ... the question is more complicated than it sounds.

After a failed attempt here it is another idea.

If we intersect $L$ with the regular language $L_{reg} = 0^*10^*10^*10^*$ we get a CF language.

Perhaps we can have more luck if we use $L_{reg}' = 0^*10^*10^*10^*10^*$ (a string with exactly 4 1s).

Let $L_1 = L \cap L_{reg}'$, informally $w \in L_1$ if it can be split in two halves, such that one half contains exactly $\{0,1,3,4\}$ $1s$  or both halves contain two $1$s but  their positions don't match.

Suppose that $L_1$ is CF and let $G$ be its grammar in Chomsky normal form, and let

$$w = uv = 0^a 1 0^b 1 0^c 1 0^d 1 0^e \in L_1$$

We have $|u|=|v|$ (even length) and $d(u,v) \geq 2$

If we restrict our attention to the ways in which the four 1s of $w$ can be generated we have the three cases shown at the top of the figure 1. The central part of the figure 1 shows the first case (but the others are similar).

Figure 1 (the full picture can be downloaded here)

If we pick $a=e, c=2a$ and $b,d \gg a$ we see that the zeros between the two pairs of 1s must be independently pumpable (red nodes in the figure): in particular, for large enough $b \gg a$, we get a duplicate nonterminal node on a internal subtree (node X in figure 2)  or a repeated subsequence in the path towards the first or the second 1 (node Y in figure 2). Note that Figure 2 is a little bit simplified: there can be more nonterminal nodes between the two $X$s, and also between the two $Ys$ ($Y\to ... \to Z_i \to ... Y$ but with $Z_i$ that produces only 0s on the right of the first 1).

Figure 2

So we can fix an arbitrary $a = e = k, c = 2a$, then pick large enough $b$ to get an independently pumpable node on the sequence of zeros between first and second $1$. For the sequence of zeros between the third and fourth 1, we can choose $d = b! +b$.
But $0^b$ is independtly pumpable so there is a $p \leq b$ pumpable substring $y$, i.e. such that $b = xyz, |y|=p, |x|\geq 0, |z|\geq 0$ and $xy^iz = b!+b$. The string we get is:

$$w' = 0^k 1 0^{b!+b} 1 0^{2k} 1 0^{b!+b} 1 0^k$$

but $w' \notin L_1$. Thus $L_1$ is not CF and finally $L$ is not CF.

If the proof is correct (???) it can be extended to every language $L_k = \{ uv : |u|=|v|, d(u,v)\geq k\}, k\geq 2$


What are the sufficient conditions for weighted binary code to be self compliementary? I was going through binary codes and found out that if the weighted binary code is self complimentary then it's weights addition will be equal to 9. Is the converse true? If not then what are the sufficient conditions for making a weighted binary code self complimentary. My research was in vain. Please help and clear my doubt.

For example: 3321 is self complimentary code. 3+3+2+1 = 9

You haven't defined your terms, so let me quickly define them:

A weighted binary code $abcd$ is the mapping $C\colon \{0,1\}^4 \to \mathbb{N}$ given by $$C(xyzw) = ax + by + cz + dw.$$
A code $C$ is legal (my term) if $0,\ldots,9$ are all in the range of $C$.
A code $C$ is self-complementing if whenever $C(xyzw) \in \{0,\ldots,9\}$, we have
$$ C(\bar{x}\bar{y}\bar{z}\bar{w}) = 9-C(xyzw), $$
where $\bar{x}$ is the negation of $x$.

Since $\bar{x} = 1-x$, we have
$$
C(\bar{x}\bar{y}\bar{z}\bar{w}) = a(1-x)+b(1-y)+c(1-z)+d(1-w) = a+b+c+d - C(xyzw).
$$
Therefore a legal code is self-complementing iff $a+b+c+d=9$.


How to perform matrix multiplication in Mixing Columns step of AES? I am studying AES and trying to implement it. But I am having difficulty understanding the Mixing Column step. In that step we have to perform matrix multiplication between the state matrix and another fixed matrix. Here is the example given in the material I am studying from:

I am not getting the 03*2F part. How did it turn into (02*2F)xor2F? Is the material correct or does it have some mistake?
Edit:
I got that 3 = 2 xor 1 hence 3 x 2F = (2 xor 1) x 2F = (2 x 2F) xor 2F but what in case if 4 x 2F? 4 = 2 xor 6 so (2 xor 6) x 2F then what?

If you want to implement it, I suggest you read the spec.  The material you were given is probably not enough to implement it.

The reason that looks confusing is that it is not ordinary multiplication; it is multiplication in a finite field.  There are lots of resources where you can learn about finite fields.


determining whether a program halts or not I have difficulty understanding the halting problem. I know that for all possible Turing machines and strings w, we don't have a Turing machine which can decide whether a TM M halts on input w.Now my problem is that if we have a program p that for example solves the Hamiltonian path problem can we conclude from the halting problem that we can't decide whether this program halts or not?

In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running or continue to run forever.

The Halting problem for a specific (narrow) class of programs (Turing machines) may be decidable. But in general, for arbitrary TM $M$and input $w$, the Halting problem is undecidable.


Difference between $F(n)=O(n)$ and $F(n)\le O(n)$? In a research paper I read $F(n) \leq O(g(n))$ and $F(n) \geq \Omega(h(n))$.

Isn't this the same as $F(n) = O(g(n))$ and $F(n) = \Omega(h(n))$?

Is there a difference?

The notations $f(n) = O(n)$ and $f(n) \leq O(n)$ mean the same thing. Sometimes want to emphasize that the asymptotic estimate is coarse, and then you can use $\leq$, for example $\log n \leq O(n)$. This is not too common if all you're doing is just stating a single estimate, but is more common in a long calculation in which some steps are equations and some steps are inequalities, for example
$$ H_n + 5n = \log n + O(1) + O(n) \leq O(n). $$
In this particular example a simple equality would be more common, but in more complicated situations you could see an inequality. It is up to the authors' personal style. As a reader, you can just ignore this distinction.


Minimal class of grammar required to run program In computability we have the hierarchy of grammars "https://en.wikipedia.org/wiki/Chomsky_hierarchy". In this hierarchy we have many classes of grammar. This hierarchy has Turing machines at the top, and weaker machines lower. Machines are able to "recognize" languages within their class, and they are able to "decide" the halt-ability of weaker languages. "http://www.radford.edu/~nokie/classes/420/Chap3-Langs.html". Doing such tasks has different complexity classes based on the class of what is being acted on.

Here is my question: What is the process of determining the minimal class of machine required to recognize, and then decide, on a language. Also what is the cost of this function in relation to the class of machine?

I know that one way is to construct a grammar for a weak machine, see if it accepts, and then if you cant find one work your way up the hierarchy.

I certainly hope there is a solution to this problem besides just brute forcing potentially forever? Thanks!

Determining whether a context-free grammar generates a regular language is undecidable (this is exercise 9.107 in Singh's Elements of computation theory; the reduction is from the Post correspondence problem). So if you are OK with a language being given to you as a context-free grammar, then even determining whether a language is regular or context-free but not regular is undecidable.


Design a data structure with constant insertion and sublinear range maximum query Suppose we have access to a stream of ordered pairs, where the $i^{\text{th}}$ element in the stream is an ordered pair $(a_i, b_i)$, where $a_i$ is a timestamp and $b_i$ is an arbitrary real. How can we design a data structure with the following two methods:

$\mathcal{O}(1)$ insert
Sublinear lookup to determine when, given some timestamp $q$ as an argument, find the maximum value of $b_i$ for all elements $(a_i, b_i)$ already in our data structure with $a_i$ in the range $(q-1, q)$.

Note: The $a_i$'s are not necessarily in sorted order in the stream. There are no additional assumptions about the the distribution of the timestamps or the values $b_i$. While I am looking for a solution with worst-case time complexity for both methods, I would also be interested in seeing if the data structure could be achieved in amortized time complexity for each or both methods.

If they're timestamps, there's a good chance they are approximately randomly distributed across some range, say $[\ell,u]$.  In this case there exist reasonable solution.
You can hash each pair into $k$ equal-width buckets in this range, i.e., using the hash function $h(a,b) = \lfloor N(a-\ell)/(u-\ell) \rfloor$, where $k$ is roughly similar to the number of items seen so far.  Within a bucket, remember the largest value of $b$ of all pairs that hashed into that bucket.  Then insert can be done in $O(1)$ expected time, and lookup can be done in $O(1)$ expected time.
Of course, we won't know $[\ell,u]$ exactly, and $\ell,u,k$ will change over time.  However you can adjust on the fly, by keeping track of the smallest and largest timestamp seen and the number of pairs seen so far.  Every time the number of pairs doubles, you update the hash function and rehash.  Naively, that sounds like it takes $O(n)$ time to rehash, but you can spread that out over the next $n/4$ inserts, maintaining the $O(1)$ expected running time.

If the timestamps aren't uniformly distributed but they come iid from some distribution, and the distribution is "smooth" enough, then I think you can find a similar solution.  Keep track of the integer-percentiles of the $a$ values (i.e., the 0% percentile value, the 1% percentile value, the 2% percentile value, and so on); it is possible to estimate these values using streaming quantile estimation / streaming histogram estimation.  To hash a pair, convert its $a$ value to a percentile (a real number $p$ in the range $[0,1]$), using linear interpolation among these 101 known percentile values; then $p$ will be approximately uniformly distributed on $[0,1]$, and you can hash $p$ into equal-width buckets as before.  If the distribution is smooth enough, linear interpolation will work well and $p$ will be approximately uniformly distributed.  If the distribution is not smooth, this may work poorly.


Is there a name for an "array with no holes"? How would you call an array [1, 2, 3, 4, 5, ...] that has (and ensures) the property of not having any undefined values through all its length.
"Dense" could work but it's not exactly what I mean, as it has more to do with zero/non-zero values.

The data structure itself is unambiguously called a contiguous array. Depending on the context and language I would call it "initialized" or "having only non-null elements" or similar to describe the contents.


Is there a limit to data compression without mentioning Kolmogorov complexity? I want to develop a previous answer to Is there a known maximum for how much a string of 0's and 1's can be compressed?.

I've looked at the Hutter Prize and various compression benchmarks.  The compression records are graphed below over a 12 year period.  The red curve is an exponential fit, which seems to be asymptotic to something much greater than zero (10MB?). The test file (enwik8) is a bulk extract from Wikipedia, and I don't think that Mr Kolmogorov can help us here.

I'm not overtly asking what the limit is. I'm just asking is there (or could there possibly be) a limit to data compression without Mr. Kolmogorov, whilst using contemporary science? Intuitively and as the fitted curve suggests, there must be some limit as the data can't be compressed to 1 bit.  Can anyone expand on any research regarding how close we might be to a minimum value for losslessly compressing enwik8? Is another 25% improvement possible? Is there any active research in this field or is the Hutter team leading the world?

For any fixed piece of data, you can create an encoding where that specific piece of data is encoded by 1 (or possibly zero) bits. So yes you can most definitely compress things down to 1 bit. This is, of course, silly. We want to know how the compression algorithm behaves on multiple pieces of data because we want to use the same algorithm (or the same shared piece of data) multiple times.

Any compression algorithm must be bigger on some inputs than the original data. In fact, if you consider every possible input there is no net compression but there might be a net increase in size. So if we look at everything compression isn't even possible. The trick is that some data is more probable than other data and we can design algorithms that are smaller in the probable case. So each individual algorithm only really has a "compression ratio" if you can give a probability distribution over the inputs, then you can say what the expected output size is or what the expected compression ratio is. If your probability distribution has maximum entropy you'll see an expected compression ratio of at least 1. Importantly the entropy of this distribution tells us how much we can compress this sort of data. You don't get to just throw it out; it always applies.

Shannon's source coding theorem tells us what the theoretical limits are for compression algorithms not just compression algorithms on streams of data of a particular sort. Say you have some data with some distribution then you can compute how "good" this compression algorithm is by sampling data and seeing what the compression ratio is on average. Well, this is the same thing as compressing one giant file that meets Shannon's source coding theorem's requirements! So the entropy of the data still tells us how much we can compress it on average.

If your data is such that it's the concatenation of a fixed number of independent fixed size samples then Huffman encoding is optimal no matter what distribution the fixed size samples come from. 1) these properties seldom hold in practice and 2) when they do the optimality will only kick in for very large data. For instance, say you sample a bunch of IEEE double precision floating point numbers from an approximation of a normal distribution. Huffman encoding is technically optimal in this case but you're unlikely to see the same data more than once unless your data set is huge. I think other compression algorithms are known to be optimal for different groups of distributions over data but you'll have to do some digging to find them; I am not aware of any others off the top of my head. So as long as your data has a certain known distribution that fits one of the cases we know the optimal algorithm for AND your data is sufficiently large (or the entropy of your distribution sufficiently low) so as to have this result even be meaningful.

Generally, we don't even know what the distribution of the data is! We can make statistical inferences based on the data we have but properly fitting a probability distribution is a hard problem. Without specifying a probability distribution we don't have a sensible way to specify how good a compression algorithm is. The quality of practical compression algorithms is basically just due to algorithm designers being good at guessing what sorts of distributions your data might be sampled from and also being good at fitting which specific distribution it was sampled from in cases where that makes sense. For instance, the gzip algorithm effectively wagers that your data will have repeated values in it (especially after some transformations are performed on it). This is clearly just a guess the designers made but it happens to be a damned good guess in practice. If you assume that your data is a stream of independently sampled symbols from the same distribution then you can fit the distribution and construct a Huffman encoding for the data; this has a lot of flaws in practice but it's a lot better than nothing in practice as well. There is no reason in general that that has to be true.

So is there a limit? Well given the only consistent notion of a "compression ratio" that I know of the answer is given by Shannon's source coding theorem.


What will happen to NP-Hard problems if P=NP I was going through the lecture of  prof. Erik Demaine and he said that a problem X is NP-Hard if it is at-least as hard as every problem Y that belongs to NP class.

He further said that if we can prove that there exists a problem that belongs to NP but not to P, then we can absolutely be sure that NP hard problems don't belong to P class.

Here is my question... What happens if P=NP. Thus it mean that all NP-hard problems become polynomially solvable? Will all NP hard problems reduce to polynomial order if P=NP?

No. A problem is Np-Hard if all NP problems are reducible to an instance of that problem in polynomial time. Some NP-Hard problems cannot be solved in nondeterministic polynomial time, and are not in NP. Then these problems will not be polynomial time solvable regardless of whether or not P=NP.


why is $O(t(n)b^{t(n)}) = 2^{O(t(n))}$ I have a question about simplifying O-notation. Specifically, why is $O(t(n)b^{t(n)}) = 2^{O(t(n))}$ where $t(n)$ is the running time of an algorithm?

I think I solved my problem...

Just as a simple numerical example: $2^6 = 2^{2\cdot3} = (2^{2})^3 = (2^{3})^2$

So if we have $2^{ct(n)}$ for some positive integer $c$ (as in the definition of O-notation) then we can choose a different base s.t. it is a power of two to the $t(n)$ power:
\begin{equation}
  2^{ct(n)} = (2^{c})^{t(n)}
\end{equation}

Then clearly, we can choose $c$ s.t. $2^c \geq b$. Hence:
\begin{equation}
  b^{t(n)} \leq (2^c)^{t(n)}
\end{equation}

Now multiplying the LHS by $t(n)$ does not matter because I can still easily choose $c$ s.t:
\begin{equation}
  t(n)b^{t(n)}  \leq (2^c)^{t(n)}
\end{equation}

Finally, we see that: \begin{equation}
ct(n)b^{t(n)}  \leq (2^c)^{t(n)}
\end{equation}

because we can still easily choose $c$.

EDIT I made a mistake with thinking of the $t(n)$ term in front of $b^{t(n)}$ as a coefficient... Anyway, here is a revised solution:

\begin{align*}
O(t(n)b^{t(n)}) =& 2^{O(t(n))} \\
ct(n)b^{t(n)} =& 2^{ct(n)} \\
ct(n)b^{t(n)} =& (2^c)^{t(n)} \\
2^{\log_2(ct(n))}b^{t(n)} =& (2^c)^{t(n)}
\end{align*}
Now suppose $b=2$. Then we can see that the term $2^{\log_2(ct(n))}$ is dominated by $2^{t(n)}$. i.e.
\begin{equation}
  2^{\log_2(ct(n))}2^{t(n)} = 2^{\log_2(ct(n)) + t(n)} = 2^{O(t(n))}
\end{equation}
Now, for $b\geq 2$ we know the $2^{\log_2(ct(n))}$ is negligible and so we are left with:
\begin{align*}
 O(b^{t(n)}) =& 2^{O(t(n))} \\
 cb^{t(n)} =& (2^c)^{t(n)}
\end{align*}
I think these two are asymptotically equivalent in the sense that $b$ is fixed and then we can choose some $c$ to satisfy the above, but what happens to the $\leq$ in the definition of $O$-notation?

Is this revision correct?
How does one read the original expression intuitively? Usually if you have $f(n) = O(g(n))$, we can think that $f$ is "bounded by" or "at most" $g$. In this scenario we have another $O$-notation as an exponent.


File systems and writing one I am going through the following series of lectures on OS development .

http://www.brokenthorn.com/Resources/

In the fourth tutorial , I came across the term " OEM" parameter block that stores the windows MBR and the Boot-record information whose soul purpose is to describe the file system on the disk .

And then  on moving to the following tutorial ,by taking the authors promise to explain about it at a later opportune point , I came across the term "FAT" file system . And I could see that there were few terms in the parameter block  like "bpbNumberofFATS" and "bpbsectorsperFAT" .
"FAT" stands for "File Allocation Table" and it is a again a "filesystem" .

This got me confused as "OEM" parameter block is used to describe the filesystem on a disk . And if "FAT" itself is a file system , then that means and surely there are other file systems ,which could have been on that disk . Why will the "OEM" block predefine the file system in terms of "FAT".

On reading a bit about other file systems , I came across statements like "FAT was written by .." . And it further piqued me to ask , what does it mean to write a filesystem ?

So , basically I am confused about :

What exactly is a filesystem ? (Is it a kind of coordinate system to provide information about the storage of the contents of the file ?)
How is a file system written ?

There are a lots of other file systems , OEM is used to describe the file system on a disk , so why OEM has parameters concerned about FAT's ? And who sets the filesystem of a disk and how ?

The MBR refers to the format used by (many but not all, and slowly being replaced by GPT) disk to identity partitions. A partition is simply a contiguous range of blocks on the disk. A partition is often used to store data, in the form of files and directories. But of course a disk knows nothing about files and directories. A file system is a system that controls how your data is stored on the disk. A file system is really two things:

it specifies how the data is organized and accessed (directories, files, links, permissions, encryption, ...): this is the logical aspect
it specifies how this data is encoded on the disk: this is physical aspect

There exists many file systems: FAT, exFAT, NTFS, ext, btrfs, HFS, XFS,  ISO 9660 and others. FAT is a file system invented by Microsoft. What this means is that they designed the logical and physical aspects of it, and they applied and were granted a few patents on it. They also wrote the Windows driver for FAT, but note that anyone can do that (assuming the file system is properly documented and ignoring royalties issues) and indeed linux and MacOS have their own driver which follows Windows's specification.

Now as I explained a file system specifies how the data is encoded on the disk and FAT is not exception. The first sector of a FAT partition (also known as the boot sector, or super block) is what is described in the link you gave: is starts with 3 bytes for a jump instruction and is followed by the BIOS/OEM Parameter Block (which has a different format on FAT12, FAT16 and FAT32). This OEM block is specific to FAT and does not exist on other file systems. Other file systems use a different format. I might add that calling this the OEM/BIOS block was very unfortunate because it really has little to do with BIOS or OEM, but that was the name Microsoft came up with. It should really be called the FAT Parameter Block.

To finish, designing a good file system is hard because they are many trade-offs to make. FAT is simple and relatively robust, but sucks at about everything else if I may say. Sadly it is also the only file system that all OSes support and so is the de facto standard for interoperability.


How can I verify a solution to Travelling Salesman Problem in polynomial time? So, TSP (Travelling salesman problem) decision problem is NP complete.

But I do not understand how I can verify that a given solution to TSP is in fact optimal in polynomial time, given that there is no way to find the optimal solution in polynomial time (which is because the problem is not in P)?

Anything that might help me see that the verification can in fact be done in polynomial time?

The crux is that you have to consider the decision problem:

  Travelling Salesman Problem (Decision Version). Given a weighted graph G and a target cost C, is there a Hamiltonian cycle in G whose weight is at most C?

For a 'yes' instance, the certificate is just some Hamiltonian cycle whose weight is at most C. If you could solve this problem efficiently, you could find the cost of a minimum tour by binary search, starting with the weight of the entire network as an upper bound.


Fast algorithms that work on some large percentage of possible inputs I've been wondering if research of these algorithms exists. An example, let's say I'm fine with $p$% of possible inputs of size $n$ to be unsorted. Is there an algorithm that would allow me to sort $n$ integers in sublinear time with a guarantee that $(100-p)$% of all possible inputs will be sorted.

Algorithms don't have to be linked the sorting, let's say it's optimization, is there an algorithm that will find the optimal tour for 1% of all TSP inputs of size $n$ really fast and what that algorithm is?

Is there a fundamental reason why these algorithms shouldn't exist or are hard to analyze?

Not quite what you're looking for but the concept of a randomized approximation scheme (RAS) is closely related and very widely studied.  This is an algorithm for computing a (numerical) quantity $f(x)$ given an input $x$ and an error tolerance $\varepsilon$. With probability at least $\tfrac23$, the algorithm returns a value $\hat{f}$ such that $(1-\varepsilon)f(x)\leq\hat{f}\leq(1-\varepsilon)f(x)$. With probability at most $\tfrac13$, the algorithm either returns an answer outside that range or says, "Uh, I dunno." If the algorithm runs in time polynomial in $|x|$ (the length of the input) and $\varepsilon^{-1}$, it's called a fully polynomial randomized approximation scheme (FPRAS).

Only succeeding with probability at least $\tfrac23$ sounds pretty terrible – "Oh, wow, it's wrong one time out of every three!". However, it's easy to boost that to any satisfactory probability by running the algorithm repeatedly and taking the median answer (counting, "Uh, I dunno" as $\infty$).  By a Chernoff bound, taking the median of $O(\log |x|)$ runs gives failure probability polynomial in $|x|^{-1}$ and taking the median of polynomially many runs gives exponentially small failure probability.


How to estimate the complexity of sequential algorithm given that we know the complexity of each step? First case:
I was stumble upon a two step sequential algorithm where the big O complexity of each step is $O(N^9)$.
Second case:
Also if the algorithm have three steps where the complexity of step 1 is $O(N^2)$, the complexity of step 2 is $O(N^3)$ and the complexity of step 3 is $O(N^9)$
What would be the complexity of the first case and second case ?

In the first case, we have $O(n^9)+O(n^9)$ and according to it's summation properties we have $O(n^9)+O(n^9)=O(2n^9)=O(n^9)$.
For the second case, both $n^2$ and $n^3$ are smaller than $n^9$, so we have $O(n^2)+O(n^3)+O(n^9)=O(n^2+n^3+n^9)<O(n^9+n^9+n^9)=O(3n^9)=O(n^9)$
In the general case, if we have time complexities $t_1,t_2,...,t_k$, then $O(t_1)+...+O(t_k)=O(max\{t_1,...,t_k\})$


A tree which each node selected as a root results in a different topology? Show that, for every n >= 7, there exists a tree of n non-labeled nodes such that picking each of the n nodes as a root results in a different rooted tree.

Here is a hint. If the tree has size $> 1$ it will have to have a vertex with degree $\ge 3$ as otherwise it would be in a line and the two ends would be equivalent. So consider a tree with a vertex having 3 branches out of it. The branches will have to have different lengths or the end vertices of equal length branches would be equivalent.

What's the smallest number of vertices in a tree of that form? Can you see how to expand the tree maintaining the required property?

Also note that this approach proves that the sizes of trees having the mentioned property are 1 and $\ge 7$.


virtual machine based programming languages vs low level I took programming lecture it was about C/java and how to build compilers, so I wanted to know.
As far I see, languages like Java/C# are developing their virtual machine CLR/JVM with good base and are improving repeatedly to increse its speed and their JIT compiler.
So I was wondering, is it possible in near future that languages such as JAVA or C# to be faster than C++ ? Or is it logically impossible ?

It is impossible for one language to be faster than another language, period.
A programming language is a set of abstract mathematical rules and restrictions. It is an idea. A piece of paper. You cannot run a language, therefore, you cannot measure its performance.
What you can do is run a particular piece of code written in one language using a particular version of a particular implementation of that language with a particular set of command line flags in a particular environment and compare its performance to a different piece of code written in a different language run with a different version of a different implementation configured with a different set of flags in a different environment.
But with all those differences, it will then be impossible to tell which of all of those differences actually caused the difference in performance. Was it the different benchmark programs? The different configuration options? The different versions? The different implementations? The different environments? Was the difference in performance caused by the language or by the quality of the implementations? Was it maybe caused by the difference in how much money was invested in optimizations?
I am willing to bet that for every set of environments and implementations that you can present me where language A is faster than language B, I can find a different set of environments and implementations where for the same two pieces of code, language B outperforms language A.
For example, there are Java implementations that are really fast. There are C++ implementations that are really slow. All I need to do is run my benchmarks using those two implementations, and I will have "proven" that Java is much faster than C++.
In the YARV Ruby VM, the Hash class is implemented in C. In the Rubinius Ruby VM, the Hash class is implemented in Ruby. Benchmarks that make heavy use of Hashes run faster on Rubinius than on YARV. Does that prove that Ruby is faster than C?


Getting started with Compiler Design This is the first time I will be studying compilers in depth. Can someone point me to best online resources (courses, articles, tutorials, video etc ) and books?

My main aim will be to do some practicals instead of just reading theory.-something where theory practical goes in parallel. So the reference must fulfill this expectations.

Alex Aiken's Coursera course on compilers is very nice. I suggest to take it
and do all exercises. Another interesting looking online course can be found here, although I have not checked it out in detail (I would be interested in opinions about it).

As to books, here are a couple.

Modern Compiler Implementation in Java (second edition) by Andrew
Appel and Jens Palsberg.
Engineering a Compiler, by Keith Cooper, Linda Torczon.
Basics of Compiler Design by Torben Mogensen. It's free.


Hash functions producing uniform outputs I've seen this question in a past exam paper, and I know that the answer given is (b), but I'm not sure why.

  Which one of the following hash functions on integers will distribute keys
  most uniformly over 10 buckets numbered 0 to 9 for i ranging from 0 to
  2020?

  (a) h(i) = i2 mod 10

  (b) h(i) = i3 mod 10

  (c) h(i) = (11 i2) mod 10

  (d) h(i) = (12 i) mod 10

I understand the number of buckets relating to the modulus, but not how the factor or power of i affects the uniformity of the distribution.

What are the quadratic residues in $\mathbb{Z}_{10}$? What about the cubic residues? What are the orders of $[11]$ and $[12]$ in the group $(\mathbb{Z}_{10}, +)$?

A brief solution follows.

For the sake of clarity, we rename the four functions $a, b, c, d$. Let's analyze their range. Because of the closure properties of the modulo operation, we may do so in the ring $(\mathbb{Z}_{10}, +, \cdot)$. We will prove that $a, c, d$ have a range that is a strict subset of $\mathbb{Z}_{10}$, and can not therefore be uniform, while $b$ is a permutation of $\mathbb{Z}_{10}$.

Since we are working over a finite ring, we could compute each of the functions on each element of $\mathbb{Z}_{10}$ and prove our claim by exhaustion. Even though that's probably what the exercise wanted you to do, and what you should fall back on if you don't understand what follows, a true gentlemen never does that. Let's work out a more elegant way.

To begin with, we observe that $a(i) = i^2$ cannot be injective, and therefore, by piegonhole, not even surjective modulo any $m > 2$ as $[1] \neq [-1]$ but $[1]^2 = [1] = [-1]^2$. This also rules out $c$, since $[11] = [1]$ in $\mathbb{Z}_{10}$.

$d$ has to go as well; this stems from the more general fact, which I leave for you to prove, that if $\gcd(k, m) \neq 1$ then $f(i) = ki$ cannot be injective modulo $m$. (Hint: use the Bezout identity).

Now all is left is to prove that $b(i) = i^3$ is a permutation of $\mathbb{Z}_{10}$. First of all, we observe that the ring $\mathbb{Z}_{10}$ is isomorphic to the direct sum of $\mathbb{Z}_5$ and $\mathbb{Z}_2$. Since $b$ is clearly a permutation of $\mathbb{Z}_2$, if we prove that it's also a permutation of $\mathbb{Z}_5$ we are done. But $5$ is prime, so $i^3 \equiv i^{-1}$, which proves our claim.


Could the execution of a Haskell program be considered as a proof using equational reasoning Could the execution of a Haskell program be considered as a proof in equational reasoning. This follows on from my earlier question on Haskell and inductive proof. Currently I am stuck between morally yes, but technically perhaps no. Below are two Haskell programs together with what I consider to be paper based equational proofs of very simple theorems. I imagine that Haskell cannot do any form of symbolic proof (e.g. id a == a), so the proofs use ground terms or values.

-- Prog 1 non-recursive
x,y,z:
x = 1
y = x + 2
z = x + y
theoremZ = z == 4
-- Paper based equational proof of Prog 1
[1]: (z)
---> (x + y)
[2]: (x + y)
---> (1 + y)
[3]: (1 + y)
---> (1 + (2 + x))
[4]: (1 + (2 + x))
---> (1 + (2 + 1))
[5]: (1 + (2 + 1))
---> (1 + 3)
[6]: (1 + 3)
---> (4)

-- Prog 2 recursive
data Vector  = Empty | Add Vector Int
size Empty  = 0
size (Add v d)  = 1 + (size v)
theoremSize =  size (Add (Add Empty 1) 2) == 2
-- Paper based equational proof of Prog 2
[1]: (size (Add (Add Empty 1) 2))
---> (1 + (size (Add Empty 1)))
[2]: (1 + (size (Add Empty 1)))
---> (1 + (1 + (size Empty)))
[3]: (1 + (1 + (size Empty)))
---> (1 + (1 + 0))
[4]: (1 + (1 + 0))
---> (1 + 1)
[5]: (1 + 1)
---> (2)

"Equational logic" has a fairly specific meaning, while you seem to be vaguely referring to the notion of "equational reasoning" which makes your question not meaningful. If we tried to take your question at face value, we immediately run into issues. Before we can talk about whether computation corresponds to proof in the logic, we'd first need to be able represent Haskell programs as terms in the logic! That can't be done, at least, not in a naive way. To handle binding forms and beta reduction, would require something like nominal/higher-order equational logic or utilizing explicit substitutions. This is just the beginning. Another question is: what do you want to constitute a Haskell program? Haskell is a Church-style language, meaning you need the type information to execute the code, i.e. a Haskell program has no meaning without type information. So does "Haskell program" mean some representation with all type information included, or do you intend to model type inference equationally somehow? Once you figure all that out, you then need some equations for your equational logic, at which point you run into another problem: Haskell has no formal semantics.

Let's step way back. For just plain arithmetic, how do we show that $2+2=1+3$? One answer is that we have an equational logic with equations like $2 = 1+1$, $3=1+(1+1)$, $(x+y)+z=x+(y+z)$, $x+y = y+x$, $0+x = x$. We might prove the equality then by using $2=1+1$ twice to get $(1+1)+(1+1) = 1+3$ then use associativity to get $1+(1+(1+1))$, and then $3 = 1+(1+1)$ to get $1+3 = 1+3$ which is then true by reflexivity. There are many other proofs besides this one that could be formulated. Just given a list of equations gives you no guidance on the proof approach, i.e. which equations to apply when and in which direction. Furthermore, if you fail to find a proof, you don't know if that's just because you weren't clever enough, or if there actually is no proof (i.e. the expressions are not equal). Both of these problems are solved by formulating a notion of "normal form" and a rewrite system that takes any term to its normal form. This is what Knuth-Bendix completion and its successors do1. In this case, each rewrite rule is derived from an equational proof, and the sequence of steps can be interpreted as stitching together these proofs with transitivity.

But this is not what people are thinking when they compute by hand, it's not what your calculator/computer is doing, and it's not even what automated theorem provers/proof assistants are typically doing2. Typically this is turned around: we have an algorithm for addition, and two expressions are considered equal when the algorithm produces the same result for both of them (where "the same" here means syntactically identical). In other words, computation comes first and "equality" is a derived concept.

For arithmetic, one might argue about which perspective is more "fundamental", but for a programming language it's clear computation is the fundamental notion. This computational approach frees us to use any representation of "terms" we want and any algorithmic approach we want as long as it's (ultimately) deterministic. Of course, this presumes that normal forms exist and are computable. For a general programming language, neither statement is true. Computing a normal form is then usually semidecidable, and the "equality" gets weakened to a partial equivalence relation. Most proof assistants avoid this issue by restricting to strongly normalizing languages. Computational Type Theory/NuPRL takes a very different approach. It exposes the operational semantics of its built-in notion of computation and gives the user some control over that computation process, e.g. "perform one beta reduction". We can then define "equality" as $x = y$ iff $x \leadsto^* x'$ and $y\leadsto^* y'$ and $x' =_\alpha y'$ where $\leadsto^*$ is the reflexive, transitive closure of the one-step reduction relation. This captures the previous notion when $x$ and $y$ have normal forms, but it allows equating expressions that lack normal forms as well, as long as they reduce to a common expression. This casts us back into the world where there's no obvious strategy, and we can't in general be sure whether two expression are unequal or we have simply failed to find a proof. That's unavoidable, since this notion of equality is not decidable.

Unsurprisingly, the steps of your "equational proofs" don't directly have to do with equality, but are, instead, sketches of proofs that e.g. $1+(2+1)\leadsto^* 4$ with respect to a hypothetical operational semantics for Haskell.

1 For just checking whether two ground terms are equal, a simpler algorithm called congruence closure can be used.

2 It (or congruence closure) is what most automated theorem provers are doing if you do literally present a series of equations and then ask if two expressions are equal, but not if numbers are built-in nor, more for proof assistants, if you define addition algorithmically. More generally, many proof assistants have built-in notion of computation, and many automated theorem provers heavily rely on decision procedures.


Route planning for a car driver picking up people using public transport We just had an interesting though for a routing algorithm for people carpooling. Imagine the following situation:

Person 1 is driving with his car from the south of city A to city B far in the north. He is picking up person 2 who is starting in the west of city A and person 3 who is starting in the east of city A. Person 2 and 3 only use public transport. Most likely, the optimal solution will be that they meet somewhere in the center or north part of city A and then drive on from there.

Any hints on an algorithm to find that solution?

A generalized version of this problem is likely $NP$-complete, however given that very few people are sharing the same car, you can probably get away with an exact, exponential time algorithm.

Assuming your road network is given as a graph, for every node you will want to store:

The earliest time each person using public transport can get to that node
For every subset of people sharing the car, what is the earliest time the car can get to that point with that subset of people in it

Basically, if you have $n$ persons and one car, you would get a graph with $2^n+n$ "layers" (one layer for each subset and one layer for each person using public transport).

You can use a Dijkstra-like algorithm to compute these values. You do a multi-start search, starting from the homes of all the people involved. Whenever the car gets to a new node you check whether any people are ready to join the car, if so, you branch (the car continues without picking them up, but also moves to any layers in the graph that can be reached by picking people up). Whenever a person gets to a new node, you check whether the car has already reached that node (and also branch).

Note it is not really branching, but rather pushing more nodes on to the priority queue.


What advantage does Tangaroa offer over PBFT? Tangaroa is a relatively new project adding Byzantine fault-tolerance to the Raft consensus protocol using techniques that were already used in the PBFT algorithm. What are the advantages, when should I use Tangaroa and when PBFT?

The notion of perfection in consensus:

Tangaroa is a BFT flavored Raft usually consisting of 3 - 5 systems in a cluster and can tolerate failure of up to 1/2 of the node count with a concept of "randomization in election of leadership".

PBFT is the "practical" BFT system designed for more deterministic behavior with a concept of "eventual leadership".
However, I came across this research (https://www.zurich.ibm.com/~cca/papers/sieve.pdf) mentioning "Fault-tolerant execution on multi-core servers poses a new challenge, even for deterministic applications,
because thread-level parallelism may introduce unpredictable differences between processes." in Related Work.

Choosing which one?
I'd leave that to you once you'll be able to determine the nature of the state machine you'd like to see operational.

Hope this helps :)
Comments and corrections,(if any) are most welcome!


Prove that if f ∉ ω(g) →f∈O(g) I am trying to prove the statement in the title. I have a hard time proving it is true. The way I go about it is by using the definition of $\omega$:

$c\times g(n) < f(n)$; So that if $f \notin \omega(g)$, then $\mathrm{NOT} (c\times g(n)<f(n))$ means that $c\times g(n) \geq f(n)$. And that by definition is Big-Oh.

Is this a correct way of proving the statement in the title?

Thanks,
Lukasz

Remarks:

The definition of $\omega$ is that $f(n)$: for all constants $c > 0$, there exists a constant $n_0>0$ ...

So, the negation of that would be: There exists $c\times g(n) \geq f(n)$, correct? Can you think of an example that would disprove the statement?

Note to the comments:

I think I understand what you are saying. Since the definition states that "for all $c>0$, there exists a constant $n$ ..." The negation of that is: "There exists a constant $c>0$, for which this is not true..."

However, for any $c>0$ there is a constant $n$ big enough that will make the statement true. Am I wrong?

The claim is not true (unless you add some "nice" conditions on the functions).

Take, for example, the functions $g(n)=n$, and consider the following function $f$: on the even numbers, we'll take $f(n)=n^2$, and on the odd numbers, take $f(n)=n$.

Since $n\notin \omega(n)$, then the assumption holds (that is, $f(n)\notin \omega(g(n))$), but since since $n^2\notin O(n)$, we also have that $f(n)\notin O(g(n))$.