Example of a false proposition when assuming Type : Type In Type Theory if one allows Type to be a member of itself, it makes the theory inconsistent. I understand it by analogy to Russel's paradox in Set Theory, but would prefer to see it done in Type Theory. Is there a short example of the equivalent in Type Theory?

The relevant literature is the following:

Thierry Coquand A new paradox in type theory (link). He describes his paradox in a system that is somewhat weaker than

Type : Type

But that can be easily transported to the above. The main idea is taking Reynolds proof that there are no models of system F in set theory. That proceeds by building an initial algebra of the form:

$$ A\simeq (A \rightarrow \mathrm{2}) \rightarrow \mathrm{2}$$

Where $\mathrm{2}$ is a set with 2 elements, and deriving a contradiction by a cardinality argument. Coquand shows

You can carry out this reasoning in the above type theory
There is a model of system F in that theory. This yields a contradiction.

The second article is from Antonius Hurkens, and is titled A simplification of Girard's paradox (link). The proof involves a construction of the "type of all well-founded types". I must admit that the general idea seems clear, but the details are quite devilish.

I'm afraid there is no simple, easy to understand contradiction in $\mathrm{Type} : \mathrm{Type}$. However the proof-terms obtained from the contradiction are relatively tractable: only a few lines are sufficient to define them.

Alexandre Miquel, in his thesis dissertation, showed that one could construct a model of naive set theory in these inconsistent type systems by using a pointed graph interpretation of sets. He can then simply apply Russel's paradox directly. Unfortunately the model construction takes a bit of work, and the dissertation is in French.


Optimal prefix code: full binary tree existence I'm ok following the passages generally used to prove this theorem, like in this question concerning the same subject. Anyway i've the unpleasant feeling that the proof lacks something to be completely understood, perhaps because considered obvious by many people.

We know that a binary tree corresponding to the optimal prefix code is full.
To produce a proof you start considering a binary tree $T$ corresponding to optimal prefix code, and suppose it's not full. If it's not full, then it must contains at least a node $u$ with just one child $v$. If you replace $u$ with $v$ you end up with a new tree $T'$ whose leafs in the subtree rooted in $u$ require less bits to be encoded: so the average bits per letter of the prefix code corresponding to $T'$ is smaller and this contradicts the optimality of $T$.

As far i can see, with this proof, we know that if we had the possibility to erase useless nodes we would obtain trees with best encoding, and therefore they must be full. But how do we prove that these trees actually exist?

I think that you can always replace nodes that aren't leafs, as stated by the proof, because they are just "auxiliary": you don't loose any information replacing them as long as the structure of the new tree you obtain is still valid to produce a prefix code. So, starting from a tree $T$ that is not full, $T'$ always exists.

Is this interpretation correct?

You can formulate this proof in completely constructive terms. Starting with any prefix code, consider any node $v$ which has exactly one child $w$, and contract the edge $(v,w)$. Repeat this as long as no node has exactly one child. Since each operation decreases the number of nodes, we know that after finitely many iterations we reach a full binary tree.


techniques for finding relevant words in a huge list of strings I have a huge list of strings. The goal is to make a database of "relevant" words.

Of course in the context of what I work with, "relevance" is something akin to the organization I work with. For e.g. if it is a automobile manufacturing industry they'd buy products like

Automotive assembly equipment
Radial tyres
Etc

If it were an aircraft manufacturing industry:

Fabricated Aluminium Body
Hydraulic Fluid
Skydrol
Jet Fuel
Etc...

Issue is that I might come across so many spelling mistakes, abbreviations, and variations.

So what is a technique I can prepare a database of words like these when I have nothing to start with, except a huge list of strings.

This is still an open problem. You can use some techniques like Stemming the words of the strings and counting them called Bag of Words Approach. Most occurring words comes most of the time are in your relevant words list.

However, you would find that non-informative words like 'the', 'is' are coming most of the time in the answer. Simplest way would be to create a dictionary of stop words of english or of the language that would include words that can be discarded. It can contain prepositions, conjunctions, pronouns, articles or may be frequent verbs, as according to your requirements. You can use a Trie for creating this fast lookup dictionary.

However, there is another approach that would find the words that are most occuring. It is called TF/IDF. This is used when you have different documents/strings to compare to each other. It gives you a value for each word that would be proportional to how much it occurs in this document but not in other documents. So words like 'the', 'is' would have comparatively less value. However, if your strings have words like Aluminium in most of them, it would also be having low value. so use it with caution.

Another thing that i would like to point out about the use of TF/IDF is that you would have to divide your data into some parts, to compare to each other. TF/IDF would give result for each of these parts. Lets say if you take each of your string as one part, then it would give you a huge set of key-words since you have a huge set of strings. It would be better to randomly partition your huge-set-of-strings into say 2 or 4 or 8 parts and then find keywords for each part and then take either intersection or union.

The trick is to use different methods and use one that gives the best results.

For spelling mistake you can create a BKTree, that would allow you to find how much two words differ in their spelling mistakes. If you add this approach, it can give you better or worse results. For e.g. if you allow words with one difference acceptable, it would treat bat and cat the same. But it would also take care of Aluminium and Allminium.


Solving the recurrence $T(n)=T(n-1)*T(n-2)$ I have been trying to solve the following recurrence:

$$T(n)=T(n-1)*T(n-2)$$
The initial conditions are $n \ge 2$ and $T(0) = 2$ and $T(1) = 4$.

I started by taking the $\log_{2}$ of both sides to get

$$\log(T(n)) = \log(T(n-1)) + \log(T(n-2))$$

which looks an awful lot like a Fibonacci recurrence.

So if I set $S(k) = \log(T(n))$, then I have a recurrence of the form
$$S(k) = S(k-1) + S(k-2)$$ with $S(0) = 1$ and $S(1) = 2$.

I can solve this easily using a characteristic polynomial and get

$$S(k) = A*(0.5*(1+\sqrt{5}))^k + B*(0.5*(1-\sqrt{5}))^k$$ where $A$ and $B$ are constants. To get $A$ and $B$ I use the initial conditions for $S$, namely $S(0) = 1$ and $S(1) = 2$.

The problematic part is that I think to get $T(n)$ I just simply raise $2$ to the power of the entire bunch above to get

$$T(n) = 2^{n*A*0.5*(1+\sqrt{5})+n*B*0.5(1-\sqrt{5})}$$.

However, when I plug in some values for n to check I get some different integer values from the original recurrence.

Is my reasoning flawed somewhere in the process or am I just making an algebraic mistake somewhere?

Thanks!

Your reasoning is perfect. To wit, here is what you get if you don't make any mistakes in your algebra. As you mention, $S(n)$ satisfies the Fibonacci recurrence, and furthermore $S(1) = 2 = F_3$, $S(0) = 1 = F_2$. We conclude that $S(n) = F_{n+2}$. Therefore $T(n) = 2^{F_{n+2}}$. The first few values are
$$
2, 4, 8, 32, 256, \ldots
$$
To get a closed formula, note that
$$
F_n = \frac{1}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^n - \frac{1}{\sqrt{5}} \left(\frac{1-\sqrt{5}}{2}\right)^n.
$$
Therefore
$$
\begin{align*}
S(n) &= \frac{1}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^{n+2} - \frac{1}{\sqrt{5}} \left(\frac{1-\sqrt{5}}{2}\right)^{n+2} \\ &=
\frac{3+\sqrt{5}}{2\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^n - \frac{3-\sqrt{5}}{2\sqrt{5}} \left(\frac{1-\sqrt{5}}{2}\right)^n \\ &=
\frac{5+3\sqrt{5}}{10} \left(\frac{1+\sqrt{5}}{2}\right)^n + \frac{5-3\sqrt{5}}{10} \left(\frac{1-\sqrt{5}}{2}\right)^n,
\end{align*}
$$
using the fact that $(1\pm\sqrt{5})/2$ are roots of $x^2=x+1$.


Reducing Exact Cover to Subset Sum Show that the subset sum problem (Given a sequence of integers $S=i_1, i_2, \dots , i_n$ and an integer $k$, is there a subsequence of $S$ that sums to exactly $k$?) is NP-complete.
Hint: Use the exact cover problem.

The exact cover problem is the following:
Given a family of sets $S_1, S_2, \dots , S_n$ does there exist a set cover consisting of a subfamily of pairwise disjoint sets?
First of all, to show that this problem is in $\mathcal{NP}$ do we have to do the following?
A nondeterministic Turing machine can first guess which the subsequence of that we are looking for is and then verify that it sums to exactly k in linear time.
Is this correct?
To show that it is NP-complete how could we reduce the exact cover problem to subset sum? Is it as follows?
The exact cover problem has a solution iff every element is in exactly one set.
We consider the set $S$ and the number $k$ such that each number corresponds to a set of elements and $k$ corresponds to the whole set. Suppose there are $n$ elements and $k$ different sets.
We replace each set S with a number that is $1$ in its ith position if i is in S and has a $0$ in its ith position otherwise.
We set k to a number that is $n$ copies of the number $1$.

Basic idea: In the exact cover problem, each element is reduced to a number. Then, each set is reduced to the sum of the numbers it covers. Finally, set $k$ to be the sum of all numbers.

This reduction always works one way: If a solution exists for the exact cover problem, a solution also exists for the subset sum problem.

The hard part is to prove the other way. Trivial numbers don't work. Suppose the elements are reduced to $1,2,3,4$, and the sets are

$S_1=\{3,4\}$
$S_2=\{3\}$

The reduction to subset sum is the numbers $7,3$ and $k=10$, which return YES but there's no solution to the exact cover problem!

We need to be smarter in choosing the numbers. Noticed the flaw in the previous numbers is that $3$ can replace $1,2$. We don't want any number to be replaced. Hence, we want the numbers to have sufficiently large gaps. Suppose in an exact cover problem of $n$ elements, the first element is reduced to $1$. How large should the second number be? There are $2^{n-1}$ sets that can include the first number. So, the second element should be reduced to a number larger than $2^{n-1}$ such that no matter how many times $1$ appears, it cannot replace the second number. Let's just reduce the second element to $2^n$. The same argument applies to the third argument, so we reduce it to $2^n\times 2^n=4^n$.

In conclusion, the $i$-th element in the exact cover problem has a value of $2^{in}$. Each set is reduced to the sum of numbers it covers.

Now we showed that exact cover is in NP-Hard. We need to prove that it is also in NP in order to show that it is NP-Complete. I think that's relatively simple. If you need help for that, I'll provide some hints for you.


Can we remove duplicates faster than we can sort? The problem is (integer) duplicate removal, which can also be perceived as producing the image of an evaluated function (of integers):

  Given a sequence $S_\text{in}$ of $n$ integers, produce a sequence $S_\text{out}$ of elements such that any element in $S_\text{in}$ also appears in $S_\text{out}$, and all elements in $S_\text{out}$ are distinct.

Ignoring some details regarding the elements' size in bits, this can be done by sorting in $O(n \log n)$ time; or by hashing in expected time $O(n)$.

Given that we don't require $S_\text{out}$ to be sorted - is it possible to do better than sorting in the worst case?

Notes:

Some dependence on the output size (let's call it $m$) rather than $n$ is an improvement, but I'm mostly interested in getting closer to linearity in $n$.
The details I've ignored may not be so insignificant.
Algorithms need not be restricted to algebraic computation, i.e. you can tear into the bit representation if it helps.
We cannot make any assumptions regarding the input distribution.

It is a classical result that the element distinctness problem requires $\Omega(n\log n)$ comparisons in the comparison model (the one used to analyze sorting algorithms); in fact, it also requires $\Omega(n\log n)$ time in stronger models such as algebraic decision trees, in which we are allowed to compute the sign of arbitrary bounded degree polynomials (rather than just $x_i - x_j$).

The element distinctness problem asks whether all elements in the input are distinct. This is clearly easier than your problem, since you can just compare the sizes of the input and output arrays. Hence in these computation models, you cannot do asymptotically better than $n\log n$.


How to write a grammar for this language? Given the alphabet $Λ = \{a, b, c\}$, i need to write a grammar for this language:

$$L=\{α \mid α∈Λ^+ ∧ aaa \notin α\}$$

I know that in my language the sequence of three consecutive $a$ cannot occur in any string, but how do I make a grammar of it? I'd need the thinking behind the construction of the grammar (like what's the first thing you should consider?), because so far I only manage to go by instinct and this doesn't always work.

Your language is regular, and so one way to construct a context-free grammar for it is to first consider a finite state automaton, and then convert it to a grammar. Of course, this methodology only works for regular languages, and is not necessarily the easiest way in every case.


How do we find the optimal modulus q in Rabin-Karp algorithm? I asked a similar question here on Rabin Karp algorithm. My present question is, how do we find the best $q$ (i.e modulus)? What is the criterion? We need to choose a $q$ which will be quick to calculate and also must result in lesser number of spurious hits, right?

Wow do we ensure these things?

The Rabin-Karp algorithm looks for a substring by computing a rolling hash, of the form $h(a_{n - 1} a_{n - 2} \ldots a_0) = \sum_{0 \le k \le n - 1} a_k q^k$ for a prime $q$. Note that the algorithm works just the same if $h$ is computed modulo the word size, so using e.g. unsigned int in C would be wise. What we'd like is $q^{n - 1}$ not too large (so the needed $q^{n - 1} a_{n - 1}$ doesn't overflow, and computations are in normal unsigned integers). Clearly $n$ (the length of the pattern) is limiting here, so you want a smallish prime. One option is to use the largest prime $q$ such that if $w$ is the word size and $A$ the largest character value (for UTF-8 it's essentially $2^8$)
$$
2^w > q^{n - 1} A
$$
This guarantees no collisions, but is very restrictive.
Perhaps just taking $q = 3$ or $q = 5$ is enough (the hash value is still a full word, so collisions should be rare anyway). As they have just 2 bits one (Fermat primes, next one is 17, then 257), perhaps the compiler (or even the programmer) replaces the multiplication by the constant prime by shift and add, but if that is a net gain depends on architecture...

Note that the cited article says this makes sense only for multiple pattern search, as there are faster alternatives for single patterns.

To really answer you'd have to run tests with representative haystacks and patterns


When do type systems start needing a logic engine? I've noticed that some languages include a logic engine as part of their type system (e.g. Shen, Typed Clojure).

Other languages have a much more direct type checking algorithm (e.g. Haskell / Hindley-Milner).

What specific features of a type system make it necessary to include a logic engine?

I'm not sure where you would draw the line between "direct type checker" and "logic engine". In a deep sense every type checker for a modern type system is a theorem prover (or proof-checker; more on this in a moment). The theorem to be proven is "the program is well-typed", or "this function has type X".

Modern type systems and their checking/inference algorithms tend to be specified in terms of logic; typically intuitionistic typed logic (a.k.a. Martin-Löf theory). If you have a look at, say, the paper for the standard Hindley-Milner type inference algorithm [1], you'll see that it's specified abstractly in terms of logic. Let-polymorphism also relies on the Robinson unification algorithm, famously used in Prolog.

I'm going to go out on a limb here and suggest that the degree to which a type inference algorithm resembles a "logic engine" (however you define it) depends on how "decidable" the rules are, and how much "inference" you need to do (as opposed to merely "checking"). The type system of the simply-typed lambda calculus is intuitionistic logic (and I do mean it really is the same thing; this is the famous Curry-Howard correspondence), so you'd think that any type checker for that system is a "logic engine" in any reasonable sense. But because you only need to "check" rather than "infer", it's a proof checker rather than a theorem prover.

The standard introductory reference on this topic is TaPL [2]. If you're at all interested in this topic, it's well worth a read; any well-stocked university library should have a copy.

Principal type-schemes for functional programs by Damas and Milner (1982).
Types and Programming Languages by Benjamin C. Pierce.


The most efficient algorithm for computing cardinality of sumset Let A and B be two finite non-empty sets of positive integers. Their sumset is the set of all possible sums a + b where a is from A and b is from B. For example, if A = {1, 2} and B = {2, 3, 6} then A + B = {1 + 2, 1 + 3, 1 + 6, 2 + 2, 2 + 3, 2 + 6} = {3, 4, 5, 7, 8}.

As we can see, cardinality #(A + B) is less than sum of cardinalities #A + #B. So i wonder whether we can calculate #(A+B) faster than just calculating all #A + #B sums and inserting them in some set-like data structure.

I've tried searching "sumset cardinality algorithm" and so on but didn't succeed.

P.S. We may assume that there is some constan K, not very lare - for example 10^5, such that 1 <= #A, #B <= K and all the elements of A and B are between 1 and K

Use the FFT.  The characteristic vector of $A+B$ is the convolution of the characteristic vectors for $A$ and for $B$.  Convolutions can be computed efficiently using a FFT.  As long as every element of $A,B$ is not too large, this will be efficient: the running time will be approximately $O(n \lg n)$ if $A,B \subseteq \{1,2,\dots,n\}$.


Graphs of maximum degree three I'm learning an algorithm for graphs of maximum degree three.

My question is: should the graph of that type have at least one vertex with degree three.

For example if the maximum degree of some graph is 2, can we say that this graph is maximum degree three.

Thank you

In general it is impossible to tell. When people say that a graph has maximum degree 3, they could mean two different things:

The maximal degree of a vertex in the graph is 3.
All vertices in the graph have degree at most 3.

Similarly, a function of degree $d$ sometimes means a function of degree exactly $d$, and sometimes a function of degree at most $d$. In many contexts, the difference is immaterial. For example, a graph of maximum degree 3 on $n$ vertices has at most $1.5n$ edges – and this holds for both meanings.

If the difference is pertinent, then one would hope that you could tell which meaning is intended from context. For example, if we are trying to understand how large the maximum degree can be under some constraints, then probably we refer to the first meaning; and if we have an inductive argument which removes edges, then we might refer to the second meaning.


Can a Turing Machine decide if a regular expression matches all strings of exactly some length $l \geq 1$? Earlier I asked the question: Can a Turing Machine decide if an NFA accepts a string of prime length?. The answer introduced me to Parikh's theorem, which I've been reading about. The concept of Parikh's theorem, if we apply it to regular expressions, allows us to break down a regular expression into expressions that only have one level of Kleene-star nesting.

So: $aa(b(cc)^*)^*$ can have a list of expressions created using the same methodology as Parikh's theorem where none of the new expressions in the final list has nested Kleene-stars. The linear subsets will use starred expressions

To make it more clear, I'm referencing this paper: http://people.inf.ethz.ch/torabidm/par-ext.pdf.

I'm not too concerned with it actually being a regular expression, DFAs or NFAs would work fine. It seems easier to work with as an RE.

I want to know if the problem is decidable:

Instance: A regular expression $R$

Question: Does there exist some length $l \ge 1$ such that $R$ accepts every string of that length (ie. if its alphabet is $\Sigma$, it accepts $\Sigma^l$, for some $l \ge 1$.

I'm pretty sure the problem actually is decidable but it's a tough one. I've enjoyed pondering it so far and would love to see what someone more experienced than myself can come up with.

I think this procedure should work...

First, construct a DFA for the language. Now, start tracing all possible paths of length $k$ (start with $k = 1$). Call $S_k$ the set of states reached by strings of length $k$.

If at any point you find $S_k \subseteq A$, the set of accepting states, the answer is yes, and return.

If, on the other hand, you find that $S_{k} = S_{k'}$, where $k' < k$, before you find an $S_k$ that works, you know that you'll never find an $S_k$ that works, and you can stop looking. The reason is that the next length you try, $k + 1$, will yield $S_{k+1} = S_{k'+1}$, another set that didn't work... and so on.

Note that this procedure is guaranteed to terminate since there are a finite number of possible $S_k$; since they're subsets of the set of all states, $S$, there are no more than $2^{|S|}$ of them. By the pigeonhole principle, if you've tried enough candidates, you'll either have already found one that worked, or you'll have tried some set more than once.

Apologies in advance if this is completely missing the point of the question, blatantly wrong or intellectually hilarious.


Shortest path problem where edge weight depends on path taken I am attempting to find the most efficient route to get from a source to a destination in a bus network. Each stop is a vertex in a graph, and each edge between vertices represents a route between stops.

The weights of the edges represents how long it takes to complete a particular journey between stops. For example, if the next bus for a particular route is 10 minutes away, and the journey takes 5 minutes, then the edge weight for that route would be 15.

However, in order to know the amount of time until a particular bus arrives at a stop, it is necessary to know the current time—defined as the sum of the weights of the edges previously taken, plus the time at which the journey started.

What algorithm would allow me to know what vertices have been previously visited, so I can compute the sum of the edge weights? Obviously I could compute every single possible path in the graph, but that seems terribly inefficient.

Don't do that.  Instead, change the way you model the problem as a graph problem.

One crude approach: Rather than having a vertex for each bus stop, introduce one vertex for each pair of a bus stop and a time.  For instance, if $s$ is a bus stop and $t$ is a time, then $(s,t)$ is a vertex.  If we have a bus that goes from $s$ to $s'$, takes 5 minutes, and departs every 20 minutes, then we'd have edges $(s,0) \to (s',5)$, $(s,20) \to (s',25)$, $(s,40) \to (s',45)$, etc.  You can take it from here.  (Test for understanding: see if you can work out what the running time of finding the shortest path to some destination is.)

A smarter approach: Fix an original vertex $v_0$ (the starting point of all trips).  For each vertex $v$, compute $d(v)$, which is the time it takes to get from $v_0$ to $v$.  How do you compute $d(v)$?  Use dynamic programming.  If you know $d(u)$ for all predecessors $u$ of $v$, then you should be able to work out an easy way to compute $d(v)$.  Also, if you've studied shortest-paths algorithms, you should be able to find an ordering for assigning $d(\cdot)$ values.  This will provide an efficient algorithm.


Reduction from Exact Cover to Fixed Exact Cover I am trying to reduce Exact Cover to Fixed Exact Cover to show that Fixed Exact Cover is NP-Hard.

Exact Cover

Input

S = {x1, x2, ..., xn} (set)

P = {P1, P2, ..., Pm} (subsets of S)

Decision problem: Is there a subset {Pi1,Pi2,...,Piq} of P such that every element of S belongs to exactly one of the Pij:s?

Fixed Exact Cover

Input
S, P from Exact Cover, and an integer K

Decision problem: Is there a subset {Pi1,Pi2,...,Pik} of P of size K such that every element of S belongs to exactly one of the Pij:s?

Given hint: K = n + 1

My initial reaction is to iterate through each element in S, and for each element create a subset for P. However, that will result result in K being one too small. I have tried many things, but I just can't seem to figure it out.

EDIT

Sorry I should have added this in the original question:
(All the Pij :s are assumed to be distinct.)
Furthermore, (we can define an instance (S′,P′,K=n+1) of FSEC. S′ will be S ∪ A and P′ will be F ∪ G where A and G are ”dummy” sets disjoint from S and P and such that the elements of G are subsets of A. If A and G are chosen in a clever way (S,P) will have an exact cover if and only if (S′,P′) has a n+1 size cover)

Example

S = {1,2,3,4}

P = {{1}, {2,3}, {2,4}, {4}}

Solution

{{1}, {2,3},{4}} (size 3)

K = 5

S' = {1,2,3,4,5,6,7,8}

P' = {{1}, {2,3}, {2,4}, {4}, {5}, {6},{7},{8}, {5,6},{5,6,7}, {5,6,7,8}}

Solution = {{1}, {2,3}, {4}, {5,6,7}, {8}} (size 5)

Add $n$ empty sets, and choose $K = n + 1$. Every solution for the original problem is (without loss of generality) of size between $1$ to $n$, so using the empty sets you can complete it to a solution of size exactly $K$.

If you're determined to have your collection duplicate-free, add $n$ new elements $y_1,\ldots,y_n$, and the following sets:
$$
\{y_1\},\{y_2\},\ldots,\{y_n\},\{y_1,y_2\},\{y_1,y_2,y_3\},\ldots,\{y_1,\ldots,y_n\}.
$$
There are exact covers of the new elements of any size from $1$ to $n$.


Least number of temporary variables required to create three address code in static single assignment form for the expression $p+q*r-s/(q*r)$ I found a question.

  Least number of temporary variables required to create three address code in static single assignment form for the expression $p+q*r-s/(q*r)$

My attempt:

  $t_1 = q*r$
    $t_2 = s/t_1$
    $t_3 = p + t_1$
    $t_4 = t_3 - t_2$

So, I got $4$ variables but their answer is $5$. Am I missing something? Where I am being wrong?

You used the optimisation of calculating q * r only once. Maybe someone considered that "cheating" and is insisting that it must be calculated twice. I wouldn't agree with that at all, but it would explain the different answers.


Calculate the complexity of an algorithm I have an algorithm here and it wants me to calculate the complexity:

for (i=1;i<n;i++)
  for (j=1;j<i*i;j++)
    if (j%i==0)
       for (k=0;k<j;k++)
          sum++;

First of all, I think that i have different complexities for best, average and worst case but I don't know how to find them. I have one though and I said that in the best case I will have the 2 fors and count as operation the 'if'. So i have a double sum (ΣΣ 1) with bounds being the values of i,j in the for loops. That's all i did.

The number of times that the if is executed is
$$
\sum_{i=1}^{n-1} (i^2-1) = \Theta(n^3).
$$
The number of times that sum is incremented is
$$
\sum_{i=1}^{n-1} \sum_{\substack{1 \leq j < i^2 \\ i \mid j}} j =
\sum_{i=1}^{n-1} \sum_{k=1}^{i-1} ki = \sum_{i=1}^{n-1} i \binom{i}{2} = \Theta(n^4).
$$
Altogether, we get a running time of $\Theta(n^4)$.


What is a good algorithm for generating random DFAs? I am generating random DFAs to test a DFA reduction algorithm on them.

The algorithm that I'm using right now is as follows: for each state $q$, for each symbol in the alphabet $c$, add $\delta (q, c)$ to some random state.  Each state has the same probability of becoming a final state.

Is this a good method of generating unbiased DFAs?  Also, this algorithm doesn't generate a trim DFA (a DFA with no obsolete states) so I'm wondering if there is a better way of generating random DFAs that can somehow ensure that it is trim?

Check out [1] and the discussion in Section 4, Random Automata Generation. The paper benchmarks different DFA minimization algorithms. A uniform random generator is used that produces canonical string representations of complete DFAs with $n$ states and $k$ symbols. They also discuss other methods.

[1] Almeida, M., Moreira, N., & Reis, R. (2007). On the performance of automata minimization algorithms. Logic and Theory of Algorithms, 3.


adder in logisim using only 2-input-NAND gates I want to build an adder in logisim only with 2-input-NAND gates. The adder consists of 2 inputs (1 x constant 1 and 1 x arbitrary number) and an output.

The first thing which came into my mind is a 8-bit full adder but maybe there is an easier solution for this (because of the constant 1). Has anyone an idea? THX

If I understand your question right, you want to build an incrementor.

First you need to build a halfadder. If you do not can or want to design it, you can ask logisim to do it.

choose project/analyse circuit. add two inputs (a,b) and two outputs (o,c).

then fill in the logic table for the half adder.

a b | o c
...............
0 0 | 0 0
0 1 | 1 0
1 0 | 1 0
1 1 | 0 1

then push build circuit and check both options (2 input gates only and nand only)

logisim wil build the circuit:

then you can connect 8 halfadders to build a 8 bits incrementor.


Hardness of approximation statement clarification? In the paper I'm reading, there is a hardness of approximation result for an algorithm proved using a reduction to set cover. Roughly, the claim states that if there existed an algorithm that solved this problem considered in the paper with an approximation ratio less than or equal to $(1 - \alpha)( 1 + \log x)$ for any $\alpha > 0$, the result for set cover would be contradicted. $x$ is a quantity that is shown to satisfy $x \leq n$. The set cover result is that set cover is NP-hard to approximate within $(1 - \alpha) \log n$.

My confusion stems from the fact that $(1 - \alpha)( 1 + \log x) \leq (1 - \alpha)( 1 + \log n)$ is not less than $(1 - \alpha) \log n$.

Can we just disregard this constant additive factor of $(1 - \alpha)$? What if the approximation ratio had a constant multiplicative factor? Like it would something like $(1 - \alpha)( 1 + \log x) (1 + \beta)$, where $\beta > 0$?

Since $1 + \log n = (1 + o(1)) \log n$, for every $\beta < \alpha$ you can find $N$ such that for $n \geq N$,
$$ (1-\alpha)(1 + \log n) \leq (1-\beta) \log n. $$
This suffices to reach a contradiction.


Are there real lexers that use NFAs directly instead of first transforming them to DFAs? I am taking the Coursera class on compilers and in the lesson about lexers it is hinted that there is a time-space tradeoff between using non-deterministic finite automaton (NFA) and deterministic finite automaton (DFA) to parse regular expressions. If I understand correctly, the tradeoff is that a NFA is smaller, but is more time consuming to traverse because all possible states have to be regarded at the same time and therefore it is most of the time transformed into a DFA.  Are there any lexers that use NFAs instead of DFAs in "real"-life i.e. some compiler that is used in production and not a just a proof of concept?

I see only two applications of using an NFA (or rather its power automaton without writing it down) instead of a minimized DFA:

Homoiconic languages, where you may want to modify your lexer frequently
Strange syntax that may blow up your DFA like

identifier := [a-z][a-z0-9_]*
indices := [0-9_]{1,256} //up to 256 times
var := identifier "_" indices | identifier

If you take the last rule as a precedence, your lexer has to check whether an identifier contains "_" within the last 256 symbols and shorten it in this case.


How can i draw a general resource graph which cannot be completely reduced but which is free from deadlock? How can i draw a general resource graph which cannot be completely reduced but which is free from deadlock?

A general resource graph which can be completely reduced and hence is free from deadlock is shown below.

As depicted above, R1 and R2 are resources and P1 and P2 are processes.

A general resource graph which cannot be completely reduced but which is free from deadlock is illustrated below.

R1 and R2 are reusable resources, and P1 and P2 processes.


Finding valid permutation using a graph Let $A$ be a set of integers: $A=\left \{ x_1, x_2...x_n \mid 10<x_i<100\right \}$

A valid permutation $x_{i_1}x_{i_2}...x_{i_n}$ is a permutation that holds the following property:

For every adjacent numbers $x_{i_j}x_{i_{j+1}}$, the unit's digit of $x_{i_j}$ is equal to the ten's digit of $x_{i_{j+1}}$.

For example, if $A=\left\{ 24,87,48,12 \right \}$ then $12-24-48-87$ is a valid permutation, whereas if $A=\left\{ 46,83,58 \right \}$, there is no valid permutation of $A$.

Now, given such a set $A$, I need to find an algorithm that prints a valid permutation if such exist, otherwise, it returns that there is no valid permutation of $A$.

I need to solve it using a graph, with a reasonable complexity, and I've been instructed to use some of the Eulerian path's properties, so it might play some role in getting the solution to that problem.

This is what I have in mind so far:

Setting a directed graph $G=(V,E)$ with: $V=\left\{ x_1, x_2...x_n\right \}$, and $E$ will contain all the arcs $(x_{i_j}, x_{i_{j+1}})$ s.t. $x_{i_j} x_{i_{j+1}}$ is valid (i.e the unit's digit of $x_{i_j}$ is equal to the ten's digit of $x_{i_{j+1}}$).

Now, if a valid permutation of $A$ exist, there is a path in $G$ that travel through every vertex only once.

There are two things that troubles me with this thought. First of all, it has nothing to do with Eulerian path, or Eulerian graph, or Eulerian anything, which makes me believe I'm way off target here. Second, the complexity of such algorithm is a nightmare: creating $G$ alone is $O(|V|^2)$, but that's nothing compared to finding some path in $G$ that traverse through all vertices only once, considering that I can't determine at which vertex to start the search.

Does anyone have an idea on how to approach this problem? Are there any observations I fail to see? Maybe searching the graph differently, or maybe even setting the graph in some other configuration?

Hint: Let the vertices be the digits $0,\ldots,9$, and let the given integers be the edges.


Average case lower bound for sorting The $\Omega(n\lg{n})$ lower bound for sorting in the comparison model is well known.  Is there a similar average case lower bound for sorting in the comparison model and if so, which random distributions does it apply to?

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

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


Shortest path with a start vertex that touches all nodes at least once with repeats allowed I tried looking this problem up for quite a bit now, but can't seem to find a whole lot of discussion about this. At first it sounded like the TSP to me, but I don't think so (it's much harder to do I believe). Maybe I am over thinking this though? I'm not looking for the fastest solution, but I fear a brute-force algorithm may take an extremely long time to perform this on a undirected graph with say 30 nodes. I'm personally trying to figure out on a video game the fastest way to traverse through every spawn point of a monster on a given zone (with a start point of course) so I can find him faster. I've already constructed a graph and figured out the distances assuming a complete graph. I guess on my part, one way to reduce the run time of such an algorithm is to remove realistically what edges wouldn't and probably wouldn't be included in a optimal path. I assume adding lots of constraints could help too. Might anyone know if there's a specific name for this problem, or if there is a simpler approach aside from just the standard brute-force? Thank you!

Your problem is just a TSP in disguise.

1. Dealing with "visit each node at least once"

First, compute a modified distance matrix $D(i,j)$, $i,j=1,...,n$ using an all-pairs shortest path algorithm, such as the Floyd-Warshall algorithm. That is, you want $D(i,j)$ to be the shortest path length from node $i$ to node $j$. Using Floyd-Warshall you also compute a matrix $S(i,j)$ that gives the successor of $i$ on the shortest path from $i$ to $j$.

Now apply a TSP algorithm to the distance matrix $D$. This will give you a tour $T$ that goes through each node exactly once. You now expand each step of $T$ into a shortest path (you can do this using the matrix $S$). That is, if some step of $T$ goes from $i$ to $j$, you expand it into the shortest path from $i$ to $j$. Concatenating all these paths gives a tour $T'$ that visits each node at least once, with possible repeats. If $T$ is optimal for $D$, then $T'$ must be optimal for the original graph.

2. Dealing with "the tour does not need to return to the starting node"

Preprocess your graph as follows. Add a dummy node, node 0, such that the distance from 0 to the starting node $s$ is 0 and the distance from node 0 to any other node is $M := n \cdot \max_{i,j} D(i,j)$.

Now find a TSP tour on the modified graph using your TSP algorithm of choice.
Because the value of $M$ is so large, any optimal TSP tour will be of the form
$$ 0, s, \pi(1), ..., \pi(n-1), 0$$
where $\pi$ is some permutation of the nodes excluding the start node and node 0. Then the sequence $s, \pi(1), \ldots, \pi(n-1)$ represents your solution.

3. Exact vs heuristic

You can use any algorithm for the symmetric TSP problem. If $n$ is about 30, you will probably not be able to apply an exact (= optimal) TSP algorithm such as the Held-Karp dynamic programming algorithm. A very simple yet reasonable  heuristic you might want to try is 2-OPT, which is straightforward to program. A branch-and-bound approach might also work well in practice.


How to generate stereo image pair from a stationary mono camera? I have a stationary mono camera which captures a single image frame at some fps. Assume the camera is not allowed to move,how do i generate a stereo image pair of the acquired frame? Is there any algorithms exists for this? If so, do they available in Open-CV?

You can't.  You have video of the scene from a single vantage point.  Without depth information, you can't infer what the scene would look like from another vantage point.


Convolutional Neural Network Example in Tensorflow I want to ask the dimension change in different convolution and max-pooling layer. I am referring to the example in TensorFlow tutorial:

http://tensorflow.org/tutorials/mnist/pros/index.html#deep-mnist-for-experts

The original image is a 28x28x1

The first convolutional layer:

apply convolution to a 5x5 patch with 32 features -> 24x24x32
apply max-pooling 2x2 -> 12x12x32

Second convolutional layer:

apply convolution to a 5x5 patch with 64 features -> 8x8x64
apply max-pooling 2x2 -> 4x4x64

But it said "Now that the image size has been reduced to 7x7" but my calculation seems to claim that it is a 4x4

Did I miss some concept? I am new to CNN so it may be a beginner question.

Thanks

Your calculation would be correct if the example were following the "usual" approach of having convolution chop off the edges.

Instead the example you pointed to says:

  How do we handle the boundaries? What is our stride size? In this example, we're always going to choose the vanilla version. Our convolutions uses a stride of one and are zero padded so that the output is the same size as the input.

So they are:

zero-padding the 28x28x1 image to 32x32x1
applying 5x5x32 convolution to get 28x28x32
max-pooling down to 14x14x32
zero-padding the 14x14x32 to 18x18x32
applying 5x5x32x64 convolution to get 14x14x64
max-pooling down to 7x7x64.

They probably have an option to turn the zero padding off.  In other infrastructures I've used zero padding is not the default.  (In several of the infrastructures I've used zero-padding isn't even possible.)


Maintaining balanced BSTs in order to get $\frac{n}{2}$ largest elements in constant time I wonder what is the best data structure I can use in order to achieve the following:
Given a data structure based on a balanced BST, I would like to get a tree with the $\lfloor\frac{n}{2}\rfloor$ greatest values in $O(1)$.
I thought about maintaining another balanced BST and a variable containing the middle value, but I don't think it's a good idea, since the root of a balanced BST might not divide the tree into 2 halves so that the $\lfloor\frac{n}{2}\rfloor$ largest elements are to the right (the tree might be right heavy).
Another idea was to use heap, but I don't see how it can help me.
Do you have any idea how to implement it? What do you think about mine?

Maintain two BSTs $T_1$ and $T_2$ such that $T_2$ always contains the largest $\lfloor n/2 \rfloor$ elements, and $T_1$ contains the remaining elements.
Insertions and deletions can be implemented in $O(\log n)$ time by performing the corresponding operation in a suitably chosen tree and then moving at most one element from one tree to the other.
For example, to insert an element $x$ proceed as follows:

Find maximum element $m$ of $T_1$
If $x \le m$:

Insert $x$ in $T_1$
If $|T_2| \neq \lfloor n/2 \rfloor$:

Delete $m$ from $T_1$
Insert $m$ in $T_2$

Otherwise:

Insert $x$ in $T_2$
If $|T_2| \neq \lfloor n/2 \rfloor$:

Find the minimum element $m'$ of $T_2$
Delete $m'$ from $T_2$
Insert $m'$ in $T_1$

Deletions are handled similarily.
The same approach also works if you maintain two heaps (a max-heap and a min-heap) instead of two BSTs.
See also this answer that uses a similar idea.


What does canonicity property mean in Type Theory? The "Computational Component" section of the Type Theory - Wikipedia (as well as a few papers about cubical type theory and 2d type theory) talk about canonicity property.

Would you please explain exactly what this property is and what does
it mean in type theory?
Why and how is it lost in the Homotopy Type Theory with the univalent axiom?

There are potentially multiple ways of presenting canonicity (and I think complications depending on the theory). However, I think the simplest way to think about it is from the perspective of a programmer wanting to use the type theory to compute something. For instance, we might want to compute some natural number satisfying some specification we've come up with. So we define:

data ℕ : Type where
  zero : ℕ
  suc : ℕ → ℕ

These constructors we've used have meaning to us, and we want the answer to be written in terms of them. So, for instance, suc (suc (suc zero))) is a valid, meaningful result of our computation.

Canonicity says essentially that every closed computation of type ℕ we write is able to be reduced to such a meaningful numeral. Or, if we don't want to talk about 'reduction', it is "convertable" or "judgmentally equal" to such a numeral, or similar. But of course, if we're programmers, we probably want that convertability to eventually turn into reduction for at least some stuff.

The reason homotopy type theory (at least, at the time of the book) does not have this property is that there was no known computational behavior for univalence; it was just added to the theory as an 'axiom,' and you could then use it in ways where computations would just get stuck. So, in that situation, you can sometimes write closed terms of type ℕ that might look like

J (...) (ua ...) ...

But do not compute further than that, because J has no way of reducing when applied to ua .... So you can write terms that don't give you a meaningful answer.

A simpler example is, I think, also mentioned in that article. You can add some variety of excluded middle to have a 'classical' type theory. To do this, we can add an axiom like:

exm A : A + ¬ A

that says that every type either has a value or is empty. However, unless your types are quite simple, it is impossible to accurately decide such a thing, so this axiom will not be able to compute to either inl x or inr y, and case analysis on it will just get stuck.

This may not be a problem if you are just using type theory in a way analogous to formal logic. You can add axioms that get stuck, and add more axioms about the things that get stuck to prove specific things you desire, but those will also get stuck. For instance perhaps we could add:

uaId : ua id ≡ refl
uaAp : subst (λ A → A) (ua f) x ≡ f x

And so on. These will allow us to manually prove certain reduction rules, so that we can manually prove that some expression we've written is (according to our axioms) the same as some concrete number. However, for someone who desires to treat type theory more like executable mathematics that will automatically compute answers, canonicity is an important property.


Standardizing Data for Neural Networks Let's say we have a data set with following features
[age, sex, country, city, annual income]
[35, male, USA, New York, 73000].

I came across the article which explains how to deal with strings as an NN input.

Article example showing how to standardize data:

[0] 30  male    38000.00  urban     democrat
[1] 36  female  42000.00  suburban  republican
[2] 52  male    40000.00  rural     independent
[3] 42  female  44000.00  suburban  other

[0] -1.23  -1.0  -1.34  ( 0.0   1.0)  (0.0  0.0  0.0  1.0)
[1] -0.49   1.0   0.45  ( 1.0   0.0)  (0.0  0.0  1.0  0.0)
[2]  1.48  -1.0  -0.45  (-1.0  -1.0)  (0.0  1.0  0.0  0.0)
[3]  0.25   1.0   1.34  ( 1.0   0.0)  (1.0  0.0  0.0  0.0)

Now let's try to use this approach in our example where we could end up with thousands of different cities. We would have to create at least N vectors size of [1 ... N]. That approach just does not seem to be very efficient when we have unlimited number of possibilities.

That was a brief explanation of standardizing data problem. Now let me expand it to my specific NN task. I have a data set with 30+ features. Features consist of real numbers, decimal numbers, strings. All of them are relevant.

I have to transform non-computable data into numeric, NN computable form. The question is how to standardize a set of data with many features of different types (strings and numbers)?

You can distinguish between the following types of data (source, see Level of measurement for something similar):

Nominal: You can't calculate with them. They only support checks for identity, e.g. names.
Ordinal: You can order them, but not compare the distance. Examples are grades or sizes for cloths.
Interval scaled: Additionally to identity checks and ordering it supports addition. Examples are temperature in °C / °F
Ratio scaled: They support multiplication in addition to the ones before. Examples are mass and length.

For neural networks, ratio scaled feature make most sense. You can sometimes change your view on things to get it, but most of the time you cannot simply transform an ordinal scaled feature to be ratio scaled.

Two tricks for your example come to my mind:

1-hot encoding: Instead of using one number for the country (e.g. 1 for Australia, 2 for Austria, 3 for France, 4 for Germany, ...) you should use a 1-hot encoding (e.g. one bit per country, the bit is only set if it is this country). I am pretty sure this will work much better, although your feature vector will get much bigger. (Attention: Depending on how much data you have, you might suffer from overfitting. You could also partition your dataset according to this feature. So, for example, you might have a lot of data for the US, for France and Germany. But you only have a little data for african countries. Then you could simply have one bit for each of US, France, Germany and complete Africa)
Latitude / Longitude: Instead of using the citys directly, you can use the citys coordinate. This makes your feature even more meaningful and you have two floats for it which are ratio scaled.

You might also think about transforming the country to something more meaningful for your problem (e.g. membership in an organization like OECD).

You could also combine different classifiers. So you could use the "bad scaled features" for a decision tree and feed the result into a NN.


Why IS is not in NL, only in NP? All we need to do is guess $k$ vertices. We look at vertex $v_1$, and make sure $v_1$ is not connected to $v_2...v_k$. Then, we "throw" $v_1$, and look at $v_2$. We do this to all vertices.

Meaning that we only need to guess $k$ vertices, and in our working memory (which determinates NL or NP) we only need to keep 2 vertices.

Where is my mistake?

First, $NL\stackrel{?}{=} NP$ is still open, so $IS\in NL$ is possible (within our current knowledge, though we believe that they are different).

The problem with your proof, is that when you "guess $k$ vertices", you have to write them in your memory (when we say "guess", we mean that we write a vertex in the working tape, where at each step our machine writes either $0$ or $1$). Keeping $k$ vertices simultaneously (where $k$ is part of the input), requires more than logarithmic space.


What is an efficient algorithm to see if a set of nodes ultimately depend on a certain node in a DAG? Hopefully this question makes sense. Basically, given a DAG, a set of nodes A, and another node b, I'd like to know if node b is an ancestor of any of the nodes in A in that graph.

This is my current implementation:

def is_ancestor(graph, A, b):
    nodes_visited = set()
    frontier = list(A)
    while frontier:
        node = frontier.pop()
        if node not in nodes_visited:
            if node == b:
                return False
            nodes_visited.add(node)
            # add immediate predecessors to the frontier
            frontier.extend(graph.predecessors_iter(node))
    return True

However, in the worst case this is O(|graph|), and this would be a function I would need to call very often, so I'm wondering if I'm missing anything that might make this run faster, preferably without requiring quadratic memory, because then I could just store everything and get O(1).

As far as I know, it is an open problem whether one can do significantly better (in an asymptotic sense).

This is known as the reachability query problem for DAGs.  You want to do some precomputation, after which you can answer queries of the form Reachable$(u,v)$ (which should return true if $v$ is reachable via some path from $u$, i.e., if $u$ is an ancestor of $v$).

There are two trivial algorithms:

With no precomputation, you can answer each reachability query in $O(|V|+|E|)$ time by just using DFA.
With a $O(|V| \cdot |E|)$-time precomputation and $O(|V|^2)$ space, you can precompute the transitive closure of the DAG and then answer each query in $O(1)$ time.

Apparently it is an open problem to do significantly better than this: e.g., to precompute something with less than $O(|V|^2)$ space that enables you to answer reachability queries efficiently.  See https://cstheory.stackexchange.com/q/25298/5038 and https://cstheory.stackexchange.com/q/21503/5038.


Longest simple walk below a certain weight Given a directed graph G and a starting vertex $v$ and a cutoff weight $w$, I want to find a simple walk with net weight < $w$ that visits as many nodes as possible. Currently, I have a recursive function which is incredibly slow, is there some sort of heuristic function for such a problem?

For my particular purposes, I am looking at superpermutation graphs for k letters, $S_k$, with only 1-edges and 2-edges. $S_k$ is vertex transitive, with each vertex having one 1-edge (weight 0) and one 2-edge (weight 1).

Without the "vertex-transitive" restriction, the problem is NP-hard, by reduction from Hamiltonian path.

Without the "vertex-transitive" or "number of neighbors" restrictions, the reduction is easy: set $w$ equal to the number of vertices minus one, and assign weight 1 to all edges.  To accommodate the restriction on the number of neighbors, replace each node with a network of nodes shaped like two trees connected at their roots; each in-edge connects to a leaf of the first tree, and each out-edge connects to a leaf of the second tree, and put weight 0 on all the tree edges.

I don't know if this reduction can be extended to handle the case of vertex-transitive graphs as well.


Showing the language of TMs that halt on a decidable set of words is not in RE I need to show that the following language, L = {$\langle M \rangle$ | The set of words which M halts on is decidable}, is not recursively enumerable. In the instructions they advise thinking of a reduction that is similar to the one used in the proof for Rice's Theorem in Sipser's 3rd edition (page 243). I couldn't think of a proper proof by myself. I assume L $\notin RE\cup CO-RE$ so there's no point in trying to prove $\bar{L}$ is in RE to show L is not in RE. Can anyone help?

Here is a reduction from coHALT (given a Turing machine, determine whether it doesn't halt on the empty input) to $L$. Given a Turing machine $M$, construct a new Turing machine $M'$ which acts as follows:

Run $M$ on the empty input.
If $M$ halts, interpret the input as a Turing machine and run in on the empty input.

If $M$ doesn't halt on the empty input, then the set of words on which $M'$ halts is the empty set, which is decidable, and so $M' \in L$. If $M$ does halt on the empty input, then the set of inputs on which $M'$ halts is HALT, which is not decidable, and so $M' \notin L$.


How to denote the space complexity in terms of output Normally the space complexity of an Algorithm $A$ is denoted $\textrm{SPACE}(A)$, which means how much space is needed by the computation itself. I would however like to also describe how much storage an algorithm needs, i.e. if I have a Turing Machine with three tapes, one for the input, one for the computation, and one for the output, I would like to express the size of each one of them.

Is there a standard way of doing so? If so, is there a reference?

Currently I am using the symbol $\textrm{DATA}$. As an example consider function $list(n) = (1,\dots,n)$. The respective algorithm $List$ for computing the function $list$ is s.t. $\textrm{TIME}(List(n)) \in \mathcal{O}(n)$, since we need to write $n$ symbols, $\textrm{SPACE}(List(n)) = \mathcal{O}(1)$, since we only need to store the current symbol, and $\textrm{DATA}(List(n)) = \mathcal{O}(n)$, since the output is a vector of length $n$.

If your algorithm/TM is called $A$ and the input $x$, it is customary to denote the size of the output by using function and string notation, that is $|A(x)|$.


Computational complexity of calculating mean vs median? Suppose we have a list $L$ consisting of $N$ numbers (may include repetitions).

I am curious which is more computationally intensive to calculate, the mean or the median?

Naively, I would suppose calculating the mean involves summing up the $N$ numbers and then dividing by $N$, hence it has linear $O(N)$ complexity.

Computing the median would need to perform some sort of sorting algorithm, https://en.wikipedia.org/wiki/Sorting_algorithm, it seems the best algorithm performs at $O(n\log n)$ complexity.

Hence, for general $N$, it is more computationally intensive to calculate median? Is my reasoning correct?

Thanks for any help.

You can find the median in linear time using the linear time selection algorithm. There are also faster randomized algorithms such as quickselect and Floyd–Rivest.

The two tasks are really incomparable, since computing the mean requires arithmetic (mainly addition) whereas computing the median requires comparisons.


Why isn't the class of Turing-Recognizable languages closed under Complement? I'm studying Turing Machines and I've already showed how Turing-Decidable is closed for the operations of Union, Intersection, Concatenation, Complement and Kleene Star. Next I did some demonstrations to show how T-Recognizable languages are closed for Union, Intersection, Concatenation and Kleene Star.

Now I'm trying to answer a question to show why the classe of T-Recognizable languages are not closed for the operation of Complementation, but I cannot understand it. Could someone please explain this?

Hint:
Suppose it was.  Let $L$ be a recognizable language and let $\overline{L}$ be its complement.  If $\overline{L}$ was recognizable as well, let $M_1$ and $M_2$ be recognizers of $L$ and $\overline{L}$, respectively.

Can you now use $M_1$ and $M_2$ to construct a decider for $L$?  What does this mean for undecidable and recognizable problems like the halting problem?


Clearing a Confusion regarding the Proof of equal no of a's and b's not being a regular language I was wondering about its proof. The direct use of pumping lemma here is not a viability. So a certain teacher of mine proved this with the notion that $a^{n}b^{n}$ being a subset of this language $L=\{w\mid\#_{a}(w)=\#_{b}(w)\}$ and non-regular (simple proof using pumping lemma) implies that the language $L$ can therefore not be regular!
The proof sounds alright initially but it got messy as I thought more on it!
I read in the books that the subset property of a regular language is not closed under regular languages. So, how can the proof be correct because for all I know L is a regular language that a non-regular language $a^{n}b^{n}$ as its subset. How does it say anything more?

I do know ofcourse that $L$ here is not regular and can draw production rules for it(CFG)! But, I need to clear this confusion I have above! Some help me here.

Here is what your teacher meant. Let $M=\{a^nb^n:n\geq0\} $. We know $M$ is not regular. Since the intersection of regular languages is regular, if $L$ were regular then so would $L\cap a^*b^*=M$ be, reaching a contradiction. This shows that $L$ cannot be regular.


Variable Length Encoding of Integers Using a Modulus Algorithm Continuing on the theme from my last question Variable Length Encoding of Integers, I have come up with a simple encoding scheme, but for which an efficient algorithm eludes me.

The constraints are simple enough: no (binary representation) number is allowed where it is divisible by 3, or a subset (prefix) of that representation is divisible by 3.

To terminate the number two bits are added so that the number is divisible by 3.

For example 1101 is allowed since neither 1101, 101, 01 nor 1 are divisible by 3.

However, 1011 is not allowed since 11 is divisible by 3.

The representation 1101 would then have 10 prepended to make it divisible by 3 (101101).

All this allows a stream of bits to be read, at each point testing to see if the number is divisible by three. If not, keep reading the next bit, until it is divisble by three. Hence allowing for a (unique) variable length encoding.

My question is about the mapping of integers on to this encoding scheme. However hard I try I can't seem to create a straightforward algorithm to do the mapping. Is there one?

Clarification

The examples above are to be read in the order right to left. So any prefix is on the right. So the stream of bits will be read right to left.

The first step is counting the number of strings of length $n$ in which no non-empty prefix is divisible by $3$. Surprisingly enough, these are given by Fibonacci numbers $F_n$ for $n > 0$ (exercise). I will show how to map the natural numbers to strings of these forms, from which your encoding will follow. Divide the natural numbers into parts of lengths $1,F_1,F_2,F_3,\ldots$. Using the formula $F_1+\cdots+F_n = F_{n+2}-1$, we see that numbers $m$ in the range $F_{n+1} \leq m < F_{n+2}$ will be encoded using strings of length $n$; additionally, $0$ will be encoded by the empty string. Given $m$, it should be straightforward to find $n$, for example using the Fibonacci recurrence or the approximate formula $F_n \approx \frac{1}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^n$.

Suppose $m > 0$, and let $x = m - F_{n+1}$, so that $0 \leq x < F_n$. It remains to encode $x$ as a string of length $n$ in which no non-empty prefix is divisible by $3$. The idea is to interpret the recurrence $F_n = F_{n-1} + F_{n-2}$ accordingly. There are many ways of doing it, here is one. There are $F_{n-1}$ legal strings of the form $0s$, and $F_{n-2}$ legal strings of the form $1\alpha s$, where $\alpha$ is determined so neither $\alpha s$ nor $1\alpha s$ are divisible by $3$. We can encode the first $F_{n-1}$ values of $x$ using strings of the form $0s$, and the latter $F_{n-2}$ values of $x$ using strings of the form $1\alpha s$. To determine $s$ itself, we run this procedure recursively. The base case is the unique string of length $1$, namely $1$.

To illustrate the entire procedure, let us show how to encode $m = 7$. First we find that $F_5 = 5 \leq 7 < F_6 = 8$, and so $n = 4$ and $x = 7 - 5 = 2$. We write $F_4 = F_3 + F_2 = 2 + 1$, so that the encoded string is of the form $s_4 = 1\alpha_4 s_2$. The string $s_2$ itself is the encoding of $x - F_3 = 0$ of length $2$. Writing $F_3 = F_2 + F_1 = 1 + 1$, we see that $s_2$ has the form $s_2 = 0s_1$. The string $s_1$ itself is the encoding of $0$ of length $1$, which is $s_1 = 1$. Therefore $s_4 = 1\alpha_4 s_2 = 1\alpha_4 0s_1 = 1\alpha_4 01$. If $\alpha_4 = 0$ then $1001$ would be divisible by $3$, so $\alpha_4 = 1$ and the output is $1101$.


The significance of bounded parameters in complexity A lot of complexity results are given with respect to bounded cases where results are more favourable.

For example, the graph isomorphism problem — which is GI-complete in general — is known to be tractable in cases where degree is bounded.

But every time I see such a result, I have a nagging voice in my head telling me that for any input graph the degree must be bounded. I find it hard to intuitively resolve the resulting cognitive dissonance.

I understand that bounding a parameter allows for considering it as a constant rather than a variable in the complexity analysis. But that seems almost like a semantic game since you can still define the bound to be arbitrarily large so long as it's fixed.

Perhaps the message to be gleaned from these bounded results is that if you assume the parameter in question to generally be small, the worst case is more favourable. But this seems rather vague to me since one can define "small" arbitrarily.

The nagging voice tells me I'm still missing something ... that something hasn't clicked.

To distil a question out of this: when one sees such a bounded-parameter result, what should one intuitively conclude about the problem in practice with respect to that parameter?

What is the importance of such a result?

When you see that a parameter is bounded, you shouldn't think of the value of the parameter of a single graph, but of a class of all graphs that satisfy the bound on the parameter.

So, to say that graph isomorphism is in polynomial time for bounded degree graphs really means that, for every $d$, there is a polynomial time algorithm $A_d$ that decides graph isomorphism on the class of all graphs of degree at most $d$.  However, the running time of $A_d$ depends on $d$.

And, yes, the take-home is generally that there are decent algorithms as long as the parameter is small. What counts as decent will depend on your circumstances: what sorts of inputs you need to deal with and how much computing time you have available.


Is finding a solution of a satisfiability problem harder than deciding satisfiability? Is the problem of determining whether or not a given Boolean expression is satisfiable computationally distinct from actually finding a solution to the expression?

In other words, is there another way of finding that a given expression is satisfiable without explicitly determining the 'right settings' for the Boolean variables? Or do all possible proofs reduce in polynomial time to the 'right settings'?

Forgive my ignorance, I am only an engineering student. Wikipedia seems to imply that the act of just finding SAT or UNSAT is NP-complete.

As mentioned in a comment, any method of determining satisfiability of a Boolean formula can be easily converted into a method for finding the satisfying variable assignment.  This is because all NP-complete problems are downward self-reducible.

From Wikipedia:

Self-reducibility

The SAT problem is self-reducible, that is, each algorithm which correctly answers if an instance of SAT is solvable can be used to find a satisfying assignment. First, the question is asked on the given formula $Φ$. If the answer is "no", the formula is unsatisfiable. Otherwise, the question is asked on the partly instantiated formula $Φ$$\{x_1=TRUE\}$, i.e. $Φ$ with the first variable $x_1$ replaced by $TRUE$, and simplified accordingly. If the answer is "yes", then $x_1=TRUE$, otherwise $x_1=FALSE$. Values of other variables can be found subsequently in the same way. In total, $n+1$ runs of the algorithm are required, where $n$ is the number of distinct variables in $Φ$.


Show that moving one symbol to the end still makes a regular language Question
For any string $\sigma$ over alphabet $\Sigma$, we define the operation $\texttt{MOVE}$ as following

For $\sigma = aw$ ($a \in \Sigma, w\in \Sigma^*$), $\texttt{MOVE}(\sigma)=wa$

This is equivalent to moving the starting symbol to the end. For example, $\texttt{MOVE}(10110)=01101$.
Show that for a regular language $L$, the language $\texttt{MOVE}(L) = \{\texttt{MOVE}(\sigma): \sigma \in L\}$ is also regular.
My Attempt
After reading this post, I know I could prove a language $L$ is regular by showing that $L$ could be expressed as a DFA, NFA, or regular expression.
I tried different (vaguely related) directions

I have proved that: if $L$ is regular, then its reverse $L^R$ is also regular. However, in terms of $\texttt{MOVE}(L)$, only one symbol is reversed while the order of others is preserved.
$\texttt{MOVE}(L)$ seems to be related to converting between left and right quotients. But I do not how to proceed as quotients are defined upon two languages rather than one.

$$
L_1/L_2 = \{w\vert \exists x: x\in L_2 \wedge wx \in L_1\}\\
L_1\backslash L_2 = \{w\vert \exists x: x\in L_2 \wedge xw \in L_1\}
$$
Except these attempts, I do not know how to approach this problem. It would be great if anyone provide some pointer for me.

Consider a DFA for the original language with states $Q$, initial state $q_0$, final states $F$, and transition function $\delta$. We construct an NFA for the new language which operates roughly as follows:

It first guesses the initial symbol $a$.
It then reads the word $w$.
A state is accepting if $wa \in L$.

To implement this, the set of states will be $\Sigma \times Q$, that is, the set of pairs $(a,q)$ where $a \in \Sigma$ and $q \in Q$. The initial states are $(a,\delta(q_0,a))$. A state $(a,q)$ is final if $\delta(q,a) \in F$. Finally, the transition relation is $\delta((a,q),b) = (a,(q,b))$.

You can solve this in many other ways. One of the simplest is using closure properties. Let $a^{-1}L = \{w \in \Sigma^* : aw \in L\}$, which is a quotient $L \setminus \{a\}$ per your definition. Then
$$ \texttt{MOVE}(L) = \sum_{a \in \Sigma} (a^{-1}L)a. $$
You can even implement this using regular expression. Given a regular expression for $L$, construct a regular expression for $a^{-1}L$ using the following rules:

$a^{-1} \emptyset = a^{-1} \epsilon = \emptyset$.
$a^{-1}a = \epsilon$ and $a^{-1}b = \emptyset$, where $b \neq a$ is a symbol.
$a^{-1}(r_1+r_2) = a^{-1}r_1+a^{-2}r_2$.
If $r_1$ doesn't generate $\epsilon$ then $a^{-1}(r_1r_2) = (a^{-1}r_1)r_2$.
If $r_1$ does generate $\epsilon$ then $a^{-1}(r_1r_2) = (a^{-1}r_1)r_2 + a^{-1}r_2$.
$a^{-1}(r^*) = (a^{-1}r)r^*$.

You can determine whether $r$ generates $\epsilon$ recursively. Denoting this predicate by $E$,

$E(\emptyset) = E(a) = F$, $E(\epsilon) = T$.
$E(r_1+r_2) = E(r_1) \lor E(r_2)$.
$E(r_1r_2) = E(r_1) \land E(r_2)$.
$E(r^*) = T$.

This gives a mechanical procedure to compute a regular expression $a^{-1}r$ satisfying $L[a^{-1}r] = a^{-1}L[r]$. We can then define
$$ \texttt{MOVE}(r) = \sum_{a \in \Sigma} (a^{-1}r)a, $$
which satisfies $L[\texttt{MOVE}(r)] = \texttt{MOVE}(L[r])$.


What is Herbrand interpreration and model? I was reading the book "Foundations of Logic Programming" written by J.W. Lloyd. In the book, there were definitions of interpretation and model, and when it comes to herbrand interpretation and model, I am having difficulties. It provided an example, but I did not understand it.

Example. Let $S$ be $\{ p(a), \exists x \lnot p(x) \}$. Note that the second formula $S$ is not a clause. We claim that $S$ has a model. It suffices to let $D$ be the set $\{ 0,1\}$, assign 0 to $a$ and assign to $p$ the mapping which maps 0 to true and 1 to false. Clearly this gives a model for $S$.
However, $S$ does not have an Herbrand model. The only Herbrand interpretations for $S$ are $\emptyset$ and $\{ p(a)\}$. But neither of these is a model for $S$.

In my understanding, by assigning 0 to $a$ and 1 to $x$ to the formulas of $S$ make them true:

$$ p(0) = true $$

$$ \exists x \lnot p(x)[x/1] = \lnot p(1) = true $$

Therefore, $\{ 0,1\}$ is a model for $S$
But I did not really understand how do we know $[a=0,x=1]$ is not a herbrand model for $S$.

I asked the question in Theoretical Computer Science section, however was advised to post in CS. Could anyone explain it to me?
Thanks in advance.

Herbrand models have special domains. The domain of every Herbrand model for $S$ (which is a set of formulas of $L$) is the Herbrand universe $U_L$ for $L$. The set $U_L$ cannot be $\{0, 1\}$, it has a totally different form, see the definition of Herbrand universe in Chapter 1 “Preliminaries”, §3 “Interpretations and models”. The set $U_L$ can contain $p(a)$, $p(b)$, $p(f(g(a)))$ where $a$ and $b$ are constants of $L$, $p$ is a predicate symbol of $L$, $f$ and $g$ are function symbols of $L$, such things. It cannot contain $0$ or $1$.


Meaning of the adjacency matrix product Let $A$ be an adjacency matrix of a directed graph. What's the meaning of the $(i,j)-$entry of the matrix $((A^T)^{7} \cdot (A^{7}))$ ?

My initial interpretation is that $(i,j)$ of this matrix is zero whenever nodes $i$ and $j$ have no 7-length in-coming paths from a common source. Is that right? Any attention is appreciated!

This is answered on  Math.SE; see also  MathWorld .

Briefly,the $(i,j)$-th entry in $A^n$ gives the number of directed walks from vertex $i$ to $j$ that have length $n$. Also, given another adjacency matrix $B$, this entry in the product $(AB)$ gives the number of directed walks from vertex $i$ to $j$ , that walk first along an edge of the first graph and then along an edge of the second.Putting these two together would give you an interpretation to the product of 7th powers in your question.


Formally proving properties of fold function Recall the fold function for lists:

$fold(f,z,[x,xs]) = fold(f,f(z,x),xs)$

$fold(f,z,[]) = z$

I want to formally proof that if $f$ is associative, commutative and idempotent (meaning $f(x,y) = f(x,f(x,y))$ and we have to lists $l_1$ and $l_2$ such that their contents  are equal then $fold(f,z,l_1) = fold(f,z,l_2)$.

What I've tried

I've tried double induction on the sizes of the list but this doesn't clarify much the problem.
I've figured out a procedure that would leave me with a list of non-repeating elements. I take each element of the $f(f(f(\cdots)))$ list and take it to the outside thanks to associative and commutative property. En each step I make sure that if I find two equal elements I remove them using idempotence. The basic rules are as follows:

$f(f(z,x),y) \text{ push x out, push y in} = f(y,f(z,x)) = f((y,z),x) = f(f(z,y),x)$

$f(f(z,x),x) = f(z,x)$

The actual transformation to the list would look like this:

     def transform[A](l: List[A]) := l match {
        case Nil() => Nil()
        case x :: Nil() => x :: Nil()
        case x :: x :: xs => transform(x :: xs)
        case x :: y :: xs  => y :: transform(x :: xs)
     }

My first problem is how to write the predicate to say that this algorithm gives a list with non-repeating elements. I do it like this:

$\forall x,y. x \in l \land y \in l \land x = y \implies index(x) = index(y)$

But I don't how to proof that my algorithm guarantees that this property holds.

The idea is that if I can proof that this transformation does not leave repeating elements then it would be easy to show that the lists end up with equal lengths and for each first element of one list I could transform the second list to get the very first element and I could apply induction to show that the statement holds.

So in short, if you think my approach is efficient and correct do you know how to solve the problems I got? And if you think you have better ideas can you give me any hints?

Edit

Just realized that my function only eliminates one repeating sequence. So adapt the argument...

"contents are equal" implies that their lengths are equal, so you don't need double induction.  Instead, try single induction.  A straightforward induction argument on the length of the list should suffice.

I wouldn't suggest trying to remove repeated elements.  That is not necessary, and it is an unnecessary complication that turns a simple induction into something really complicated and messy (as you have discovered).


Complexity of list coloring $K_n$ with $n$ colors The list coloring problem is, given a set $L(v)$ colors for each vertex $v \in G$, is there a proper vertex coloring, $c$, of $G$, such that $c(v) \in L(v), \forall v$.

I was wondering, for complete graphs $K_n$, is list coloring NP-complete? Does this change if $\bigcup_{v \in K_n} L(v) = \{1,2\dots n\}$?

Consider list coloring the complete graph, where the available colors for vertex $v$ are $L(v)$.

Form a bipartite graph in which the left-hand side corresponds to vertices and the right-hand side corresponds to colors. Connect $v$ on the left-hand side to all colors in $L(v)$ in the right-hand side.

There is a list coloring iff there is a matching saturating the left-hand side. You can decide whether this is the case by running an algorithm for bipartite perfect matching.


Do Oracles run in O(1) or O(n) time? The common understanding of what oracle does is that it answers a question after a single operation.  So at first glance, it runs in $O(1)$.  But, doesn't it need to actually read the input?  Wouldn't this take at least $n$ steps?  If so then wouldn't an oracle run in $O(n)$?

The oracle runs in a single step. Yes, it would take an ordinary Turing machine some number of steps to read the input but an oracle isn't an ordinary Turing machine – that's almost the whole point of using them. Also, the time taken for the oracle to read its input is essentially accounted for by the time it took the calling machine to write that input.  So, oracles return in $O(1)$ steps. More precisely, they return in exactly one step.

Also, it's not quite clear what you mean by "$O(n)$ steps". $n$ usually denotes the length of the input we're trying to compute on, which would be the input to the calling machine, not the oracle. The input to the oracle could be arbitrarily long.  For example, you could have a machine that takes an input $x$ and calls an oracle to ask if the string consisting of $2^{2^{2^{|x|}}}$ zeroes is in the language decided by the oracle. Moral of the tale: don't write functions of $n$ without saying what $n$ is.


how to formally arrive at a correct EBNF grammar of a language I am trying to write a mini parser for a simple language whose specification is as follows:

A search term is represented by. Both searchkey and searchvalue is a word formed by using alphanumeric characters.

<searchkey> <searchoperator> <search value>

: represents the exact match(similar to "=").
ex :

response:success

multiple search terms can be combined with AND & OR operator.
ex.

response:sucess AND extension:php

By default AND has higher precedence than OR but this can be changed by grouping the search terms in a round bracket.
ex:

response:sucess AND (extension:php OR extension:css)

along with : other valid operators search operators are >, >=, <, <= .
ex.

time >= 2020-01-09 AND response:success OR os:windows

A search term could be preceded with NOT keyword to do the negation.
ex.

response:success AND NOT os:windows

I have written this grammar in ebnf notation :

<exp> ::= <exp> " OR " <exp> | <logical_and>
<logical_and> ::= <exp> " AND " <exp> | <logical_not>
<logical_not> ::= " NOT " <logical_not> | <term>
<term> ::= "(" <exp> ")" | <atom>
<atom> ::= <word> <op> <word>
<op> ::= ">" | ">=" | ":" | "<" | "<="
<word> ::= ("a" | "b" | "c" | "d" | "e" | "f" | "g"
                      | "h" | "i" | "j" | "k" | "l" | "m" | "n"
                      | "o" | "p" | "q" | "r" | "s" | "t" | "u"
                      | "v" | "w" | "x" | "y" | "z")+

But originally I had come up with this grammar.

<expr> ::= <or>
<or> ::= <and> (" OR " <and>)*
<and> ::= <unary> ((" AND ") <unary>)*
<unary> ::= " NOT " <unary> | <equality>
<equality> ::=  (<word> ":" <word>) | <comparison>
<comparison> ::= "(" <expr> ")" | (<word> (" > " | " >= " | " < " | " <= ") <word>)+
<word> ::= ("a" | "b" | "c" | "d" | "e" | "f" | "g"
                      | "h" | "i" | "j" | "k" | "l" | "m" | "n"
                      | "o" | "p" | "q" | "r" | "s" | "t" | "u"
                      | "v" | "w" | "x" | "y" | "z")+

is there any difference if I choose one over another? Can there exist multiple grammars for a language?
Is there any formal way to generate grammar for a language? this is a small language so its easy to get the grammar intuitively by tweaking it but what if the langue specification is huge?

Your informal description of your language could certainly be made more precise, in the same way as you could make the description of any (mathematical) set more precise until you've written the description out in mathematical notation. In that sense, EBNF is similar to what you get when you recast an informal description of a language into a mathematical formalism. (EBNF doesn't quite qualify, but the BNF formalism which inspired EBNF is a precise formalism.)

In between the formal description of a language and the practical question of building a parser for the language, a number of practical issues need to be dealt with, many of them having to do with the way a string of characters is grouped into meaningful tokens in the concrete representation of the language. In other words, questions like "where can spaces and newline characters be placed?" "Can I insert comments into an expression?" and so on. It's possible to write these into a formal description of a language, but the end result is often not particularly useful for the casual reader because the high-level structure of the language is overwhelmed by pesky details.

I note in passing that your grammar requires that AND and NOT appear with precisely one space preceding and following, while no spaces are allowed around the >= operator (and friends). That means that several of your examples don't match the EBNF. For example, time >= 2020-01-09 would have to be written as time>=2020-01-09 and response:success AND NOT os:windows as response:success AND  NOT os:windows (with two spaces between AND and NOT). I doubt that was your intent, and I don't say this to criticise; just to point out how tricky it can be to get the details right, so that it can actually be used to construct a concrete parser, and still make the grammar usable for human readers. The usual approach is to separately formalise the division of the text into lexemes ("tokens") and the syntactic structure of the language, which treats the inputs as a stream of tokens rather than as a stream of undifferentiated characters. That's by no means formally necessary, and a lot of the applications of EBNF do in fact attempt to be precise to the character level, but a close examination of these EBNF applications might reveal the practical limitations of this strategy.

As I said in a comment, for any language for which a context-free grammar exists, there are an unlimited number of other context-free grammars which derive the same language. However, the question of whether two context-free grammars derive the same language is undecidable; no algorithm exists which can always correctly make that determination. Consequently, it is also impossible to enumerate all the grammars which could derive a given language (however that language is given).

In addition, there are competing mathematical formalisms which could be used to describe a language. After all, a language is a set, and any mathematical expression which precisely defines a set is a possible formal language description. (Some of these will be more practically usable than others.) So there's no way to say whether a procedure exists to generate a description in one formalism from a description in another formalism without know what, exactly, the nature of the two formal systems is. Sometimes it will be possible, other times not.

If you only want to know if a given text is in a language, then any of the unknowable infinitude of possible grammars for that language will suffice, although it's better if the grammar formalism used is computationally tractable. But most of the time, you don't just want to know that a text is in a language. (A C "compiler" whose only possible output is one of the messages "yes, that is a well-formed C program" and "no, that is not a well-formed C program" is unlikely to attract many paying customers, even if its judgement is 100% correct.) In most applications, you want to parse the language in order to reveal the syntactic structure of a valid text. To do that, your grammar should reflect the syntactic structuring you have in mind, and not all of the possible grammars for the language do.


Divide an integer into the sum of consecutive positive numbers Today I am trying to solve an classical problem:

  For any $n\in \Bbb{N}^+$, If it can be represent as the sum of consecutive positive numbers, find out them.

For example:

$$15 = 1+2+3+4+5$$
$$15=4+5+6$$
$$15=7+8$$

And I have an ugly method, its time complexity is: $O(n^2)$. I use two for loop to exhaustion all possibilities.

for(int i=1;i<n;i++)
{
    for(int j=i;j<n;j++)
    {
        sum+=j;
        if(sum==n)
        {   //print out the answer
            for(int l=i;l<=j;l++)
            {
                cout << l << "+ ";
            }
            cout << endl;
            break;
        }
    }
    sum = 0;
}

I think there may be exist a more effective solution, But I am failed until now.  Please help me.

for i from 1 to n
{
   for j from i to n
   {
       sum <- sum + j
       if sum equal n
       {
          print the result
       }
   }
   sum <- 0
}

Here's an alternative way of viewing D.W.'s hint. Using the formula $\sum_{i=1}^m i = \frac{(m+1)m}{2}$,
$$ \sum_{i=a+1}^b i = \sum_{i=1}^b i - \sum_{i=1}^a i = \frac{b^2+b}{2} - \frac{a^2+a}{2} = \frac{(b-a)(b+a+1)}{2}. $$
Given a factorization $2n = xy$, we can solve the system $x = b-a$, $y = b+a+1$. The result is $b = (y+x-1)/2$, $a = (y-x-1)/2$. So we want $x,y$ to have different parities (this is only a restriction if $n$ is even) and $y \geq x+1$. Also, $b \neq a+1$ corresponds to $x \neq 1$.

For example, for $n = 15$ we have $2n = 30 = 2 \cdot 15 = 3 \cdot 10 = 5 \cdot 6$. These correspond to the following pairs $(a,b)$:
$$ (6,8),(3,6),(0,5). $$
These, in turn, correspond to the representations
$$
15 = 7+8 = 4+5+6 = 1+2+3+4+5.
$$

This leads to an $O(n)$ algorithm (in the appropriate computation model). I'll let you work out the remaining details.


Church-Turing and physical PDEs When I read about the Church-Turing thesis it seems to be a common claim that "physical reality is Turing-computable." What is the basis for this claim? Are there any theoretical results along these lines?

For context, I am a researcher who works on physical simulations, so of course I'm aware that many partial differential equations (PDEs) that would arise in nature (e.g. the heat equation, wave equation, etc) can be approximated by numerical methods like finite elements, and that for many PDEs a solution can be estimated to arbitrary accuracy given enough computation (by decreasing the space and time step sizes).

However, I also know that proving convergence of finite element methods is notoriously difficult for PDEs of any appreciable complexity, even "easy" PDEs like the mean curvature flow that describes the shape of a soap film. I also know that many "Zeno-type" situations arise in practice in physical systems, such as Euler's disk or inelastic collapse. Is there reason to believe that the solutions to all PDEs, or at least all PDEs that would arise in nature, are Turing-computable?

The branch of mathematics and computer science that studies these questions is computable mathematics. The general answer is that things tend to be computable. I would add to that the observation that it often takes some work to establish computability. For instance, you mention finite element methods and the problems with their convergence. This proves absolutely nothing about computability of PDEs because there are, or might be, other methods for solving PDEs.

Some references that migth interest you, in order of relevance:

H. Zenil (editor): A computable universe, Word Scientific, 2012.
The nLab has a page on computable physics.
K. Weihrauch: Computable analysis - An introduction, Springer, 2000.


Is developing an OCR considered a research project? Is developing an optical character recognition system for an alphabet which has no previous ocr considered a reputable conference or journal worthy research project, given the fact that there are so many commercial ocr system? Though, lots of conference proceeding and journal entries shows up when googled, but most of them are old and are about performance of a specific algorithm. There are also research on ocr for cursive alphabets which are hard to segment, like Arabic. The alphabet I am developing ocr for is of Indic origin and cursive as my final year undergraduate thesis. So, I'm wondering if it's a good research project.

Rifat, you have to ask your supervisor.  If (s)he accepts, then go for it, otherwise go back to the drawing board.

If this is, as you say, an area for which an OCR does not yet exist, then it sounds perfectly fine for an undergraduate project, but do not expect any reputable conference or journal to publish your results.


Convert (x + y = z) to propositional logic formula for 8-bit numbers (Note: this was asked in the cstheory stackexchange, but I was told this is a more appropriate place for it.)

I have three 8-bit 2's-complement numbers (X, Y, and Z). I want to find a propositional logic formula using only the variables (x1, x2... x8, y1... y8, z1... z8), where xi is the ith bit of x which expresses the concept that X + Y = Z. How would I go about doing this?

You can obtain a formula in CNF form by writing down a truth table (with $2^{24}$ rows) and then converting each row to a single clause.  This will yield a formula with $2^{24}$ clauses, but the method is straightforward.

If you want a shorter formula, I suggest using logic synthesis, e.g., Quine-McClusky, Espresso.

The usual path to get a small formula is to allow introduction of additional variables, build a circuit (e.g., an adder circuit followed by a comparator), then convert to a formula using the Tseitin transform.  This yields much smaller formulas, but it requires introducing extra variables, which you said you don't want.


Decide whether this language is regular Decide whether the language $L$, defined by the following grammar is regular or not:
$S \rightarrow aab$
$S \rightarrow aacSb$
$S \rightarrow acSab$
$S \rightarrow acSacSb$
Where should I start?
I have tried defining a new language $L' = \{(aac)^n\ w\ b^n | w \in L\}$, which should be non-regular, because of dependency on $n$ with different left and right sides and since $L' = L$, $L$ has to be non-regular too, but I'm not sure whether this technique is valid.

The first step is to show that
$$
L \cap (aac)^*aabb^* = \{ (aac)^n aab b^n : n \geq 0 \}.
$$
Given that, you argue as follows: If $L$ were regular, then $L \cap (aac)^*aabb^*$ would also be regular. You can show in various ways that $\{ (aac)^n aab b^n : n \geq 0 \}$ isn't regular. It follows that $L$ isn't regular.


Why cannot match $ Bool \equiv Bool $ with $ refl $ while $1 \equiv 1$ can? This code depends on agda-stdlib:

{-# OPTIONS --without-K #-}
open import Data.Nat
open import Data.Bool

open import Relation.Binary.PropositionalEquality

-- this code doesn't check, cannot match e with refl
why : (e : Bool ≡ Bool) -> ℕ
why refl = zero

but-why : (e : 1 ≡ 1) -> ℕ
but-why refl = zero

I know K-rule means I cannot match $ \forall a.a \equiv a $ with $ refl $, but if $a$ is a concrete value, it can (i.e. $1 \equiv 1$ can be matched with $refl$).
But why I cannot match $Bool \equiv Bool$ with $refl$? Why is type and value treated differently in a dependently-typed programming language?

(Maybe related: What does it mean if we disable K-rule in Agda?)

From the perspective of Homotopy Type Theory (HoTT), i.e. if we have the Univalence Axiom, there are definitely values of Bool ≡ Bool that are distinct from refl. Because Agda without Axiom K is compatible with univalence, it can't then assume that refl is the only value of type Bool ≡ Bool.

ℕ, on the other hand, is an h-set in HoTT (see Section 2.13 of the HoTT book). This is to say that Axiom K restricted to ℕ does hold. This is related to the fact that ℕ is inductively defined (with no parameters or indices) while Set is not.

I don't know the exact logic Agda uses. Presumably, it is something like it knows that nullary constructors of an inductive type are identified with themselves in only one way (which wouldn't be true for higher inductive types), and it knows suc is injective.


Whether assigning of single precision IEEE754 float to double is reversible? Using the IEEE754 standard, let's assign single precision variable s to double precision variable d and then assign d to single precision variable s'.

Is this operation is reversible (lossless) for any value that can be represented in IEEE754, including NaN, infinity, etc.?  In other words, is it guaranteed that s = s' for all possible s?

On my processor NaN is not reversible (01 00 80 7f != 01 00 c0 7f).  Brute force shows that NaN is not reversible, but this might be implementation dependent, so please answer within the scope of IEEE754 standard.

Maybe this will help. This is not full answer - just information to think.

  5.3 Floating-Point Format Conversions
  It shall be possible to convert floating-point numbers between all supported formats. If the conversion is to a narrower
  precision, the result shall be rounded as specified in Section 4. Conversion to a wider precision is exact.

IEEE Std 754-1985


Finding an element in a sorted array with at most three queries to larger elements Given a sorted array A, we have to find the position of an element m in it. (It is also given that the element exists in the array.)

However there is a constraint. Like in a game you have 3 lives. If you probe any element x > m in the array you will lose one life. You can probe as many elements you want which are smaller than m. If you find m, you win.

The solution to this should not be in linear time.

What I tried:

I will drop eggs from floors 1, 2, 4, 8..
And in log n time, I will find a sub-array in which m exists (at cost of 1 life). But this sub-array was of size at most n/2. I cannot repeatedly apply this process since, I have limited number of lives.

My thoughts

I am thinking that a solution does not exist to this problem which is faster than linear. How to prove this (if this is the case)? Can I create a contradiction from the assumption that a solution exists?

If you have only one life only safe way is to check every element starting from minimal. It's $O(n)$

If you have two lives and limited with $k + 1$ comparisons the minimal element of array you can check first has index $k$, so we still have $k$ comparisons to check all previous elements one by one, if no lives was lost than next element to check has index $k + (k - 1)$ so total numbers of elements we can check is that way $n = k + (k-1) + (k-2) + ... + 1 = \frac{k(k+1)}{2}$ So if you have two lives you can find target element for ($k = \frac{1 + \sqrt{1 + 8n}}{2}$) $+1$ comparisons.
It's $O(\sqrt n)$

So if we have three lives and $k + 2$ comparisons first we should check element of index $\frac{(k + 1)(k)}{2}$ than if we will lost life we will be able to check all earlier elements for $k + 1$ comparisons. So in full analogy $n = \frac{(k+1)(k)}{2} +   \frac{(k)(k-1)}{2} +  \frac{(k-1)(k-2)}{2} + \frac{(k-2)(k-3)}{2} +... + \frac{3\cdot2}{2} + \frac{2\cdot1}{2} = \frac{1}{6}(k+2)(k+1)(k)$

Therefore $n> \frac{1}{6}(k)^3$ and $k < \sqrt[3]{6n}$

So we can solve this for $O(\sqrt[3]{n})$

This is variation of quite known skyscraper and glass or crystal balls puzzle, though I may be didn't find correct name for it in English.


Algorithms for Connect 4? Im designing a program to play Connect 6, a variation of connect 4. I have narrowed down my options to the following:

1) Minimax with Alpha-Beta Proning

2) A Neural Net

3) Machine Learning

My program has one second to make a move, so I can only branch out 2 moves ahead with Minimax. Which solution would best perform under 1 second?

I looked around the web, but couldn't find anything relevant.

Also, are there any other additional resources you suggest I have a look at?

Connect Four was solved in 1988. The first solution was given by Allen and, in the same year, Allis coded VICTOR which actually won the computer-game olympiad in the category of connect four.

I would suggest you to go to Victor Allis' PhD who graduated in September 1994. You can get a copy of his PhD here. In Section 6.3.2 Connect-Four (page 163) you can actually read the following:

"In September 1988, James Allen determined the game-theoretic value through a brute-force search (Allen, 1998): a win for the player to move first. A few weeks later, in October 1988, connect-four was solved through a knowledge-based approach, resulting in the tournament program VICTOR (Allis, 1988; Uiterwijk et al., 1989a; Uiterwijk et al., 1989b). Recently John Tromp has calculated the game-theoretic value for all 8-ply connect-four positions (Tromp, 1993)."

You will find all the bibliographical references in the Bibliography chapter of the PhD in case you need further information. Of these, the most relevant to your case is Allis (1998). A Knowledge-Based Approach of Connect-Four. The Game is Solved: White Wins. M.Sc. Thesis, Faculty of Mathematics and Computer Science, Vrije Universiteit, Amsterdam. Go to Chapter 6 and you'll discover that this game can be optimally solved just by considering a number of rules. And this take almost no time!

So, my first suggestion would be for you to consider none of the approaches you mention but a knowledge-based approach instead. From what I remember when I studied these works, most of these rules should be easy to generalize to connect six though it might be the case that you need additional ones. However, if all you want is a computer-game to give a quick reasonable response, this is definitely the way to go.

Additionally, in case you are interested in trying to extend the results by Tromp that Allis mentions in the exceprt I was showing above or even to strongly solve the game (according to Jonathan Schaeffer's taxonomy this implies that you are able to derive the optimal move to any legal configuration of the game), then you should read some of the latest works by Stefan Edelkamp and Damian Sulewski where they use GPUs for optimally traversing huge state spaces and even optimally solving some problems.

Hope this helps,


Does selecting the same arm has the same reward? In multi-armed bandit problem, we have a set of $K$ arms. In each round $t$, a bandit selects an arm $k$ and receives a reward $r_{kt}$. The objective is to maximize the rewards after $T$ rounds.

My question: Does selecting the same arm in two different rounds leads to the same reward? Or the rewards are completely different?

It is surprising to me if one could select the same arm but receives a different reward and still has a sublinear regret.

In the version of the Multi-Armed Bandit problem I'm familiar with, there is a fixed list of distributions $B = R_1, R_2 \cdots R_n$, and the reward for pulling lever $k$ is chosen from the distribution $R_k$.

So pulling the same lever twice might lead to different rewards, but the rewards are connected through the distribution $R_k$.


Partial recursive function with no total recursive extension We define a partial recursive function $f:\{0,1\}^* \longrightarrow \{0,1\}^*$ to be semi-good if we can define a total recursive function $g:\{0,1\}^* \longrightarrow \{0,1\}^*$ from $f$, such for all $x \in \{0,1\}^*$ either $f(x) = g(x)$ or $f(x)\uparrow$.

Now I want to prove that there exists a partial recursive function that is not semi-good.

I must make a partial recursive function that is not semi-good for example $f_1$ ,but my problem is that I must show that I can not define any total recursive function $g:\{0,1\}^* \longrightarrow \{0,1\}^*$ from $f_1$.

I don't have any idea how can I show this. Can I use the fact that a specific language like $L$ is not recursive so its characteristic function $\mathcal{X}_L$ is not total recursive function? How can I make the partial function from this fact?

Take the function that interprets its input as the description of a Turing machine, and outputs the number of steps it takes the machine to halt, if it halts, and is undefined otherwise. This function is clearly partially computable, but it has no computable extension, since you could use any such extension to solve the halting problem (why?).

Exercise for the reader: convert this construction to a Boolean function.


Co NP problem correponding to SAT I've been reading lately about SAT problem, NP and co-NP.

Many sources say that the SAT problem is co NP, though, I can't find a co-NP problem equivalent to SAT.

Does anyone have any idea about this ? (Or could lighten my misunderstandings)

If SAT is in coNP then NP=coNP, which is believed to be false. However, coSAT, the language of unsatisfiable CNFs, is coNP-complete.