What is the depth of recursion if we split an array into $\log_2(n)$ with each recursive call? We have a function which takes an array as input. It breaks an array into $\log_2(n)$ parts with equal sizes where $n$ is the size of the subarray. It keeps breaking each of the subarrays until there are only two elements left in it.  What is the depth of this recursion?

Example of the process:

First we have $n$ elements and break them up into $\log_2(n)$ parts with equal sizes. Each of these parts has $\frac {n} {log_2(n)}$ elements in it. In the next level of recursion we will break each of the subarrays into $log_2(\frac {n} {log_2(n)})$ parts again with equal sizes. These will now have $\frac {\frac {n} {log_2(n)}} {log_2(\frac {n} {log_2(n)})}$ elements in each one of them. And we keep on breaking the array in this manner until we reach a subarray with only two elements in it.

Let $f(n) = n/\log n$, and denote by $g(n)$ the number of applications of $f$ it takes to get $n$ below some arbitrary constant. On the one hand, $f^{(t)}(n) \geq n/\log^t n$, and so
$$
g(n) \geq \log_{\log n} n = \frac{\log n}{\log \log n}.
$$
To obtain an upper bound, notice that as long as $f^{(t)}(n) \geq \sqrt{n}$, we have $\log f^{(t)}(n) \geq (\log n)/2$, and so it takes at most $\log_{(\log n)/2} n = O(\log n/\log\log n)$ iterations to reduce $n$ to $\sqrt{n}$. The same argument applies for reducing $\sqrt{n}$ to $\sqrt[4]{n}$ and so on, and therefore
$$
g(n) \ll \frac{\log n}{\log\log n} + \frac{\log \sqrt{n}}{\log\log \sqrt{n}} + \frac{\log \sqrt[4]{n}}{\log\log \sqrt[4]{n}} + \cdots.
$$
(Here $\cdot \ll \cdot$ is the same as $\cdot = O(\cdot)$.) Notice that
$\log \sqrt{n} = \frac{1}{2} \log n$. For large $n$, we will have $\log\log \sqrt{n} \geq \frac{2}{3} \log \log n$ (say), and so
$$
\frac{\log \sqrt{n}}{\log\log \sqrt{n}} \leq \frac{2}{3} \frac{\log n}{\log\log n}.
$$
Therefore the sum is majorized by a convergent geometric series, and we conclude that
$$
g(n) = O\left(\frac{\log n}{\log\log n}\right).
$$
In total, we get that
$$
g(n) = \Theta\left(\frac{\log n}{\log \log n}\right).
$$
With more work, we can probably prove a more refined estimate such as
$$
g(n) \sim \frac{\log n}{\log \log n}.
$$


term vs clause in the context of normal forms In the context of disjunctive normal forms, which terminology do you use for the conjunction of atoms? E.g., for the disjunctive normal form $(x₁ ∧ ¬x₂ ∧ x₃) ∨ (¬x₁ ∧ x₂ ∧ x₃)$, how are the constituents "$x₁ ∧ ¬x₂ ∧ x₃$" and "$¬x₁ ∧ x₂ ∧ x₃$" called? Terms or clauses? I saw boths variants as well as "disjunctive clauses", and I wonder which variant is right.

There are lots of non-native English computer scientists around, so please reply only if you are an established computer scientist who actually taught this and have an excellent command of English.

They're often called a "clause", "conjunctive clause", or sometimes a "conjunction" (if it is clear from context what that is referring to).

See, e.g., https://en.wikipedia.org/wiki/Disjunctive_normal_form.


Does MST exclude the edge belongs to the cycle of the graph? For any simple, connected, undirected graph $G(V,E,w)$ with each carrying distinct positive edge weights, is it true that MST will contain all the edges which do not lie in any cycle of $G$?

I think MST can take any edge of irrespective of the fact whether it is an edge of cycle (like I simply use Kruskal's), Also I am unable to see Why the above statement should true. Can anyone tell how the statement is true?

I think you need to be more precise in your reading of the statement, though it could be better phrased. A different version is "if $e$ is an edge of $G$ and it is not in any cycle in $G$, it must be in any MST of $G$". This doesn't say that edges that are in cycles can't be in the MST, it just says that any edge that isn't in a cycle must be.

To see why this is true, imagine an edge that is not part of a cycle; it has two endpoints, both of which must be part of the MST (otherwise it wouldn't be spanning). So how do we get to those endpoints? If we don't use that edge, we can't reach one of the endpoints (if we could reach both, then the edge would be part of a cycle), thus that edge must be in the MST.


big-O and Θ notation subset I was reading “Introduction to Algorithms” by CLRS and it says

  Note that f(n) = Θ(g(n)) implies f(n) = O(g(n)) since Θ notation is a stronger notation than O notation. Written set theoretically, we have Θ(g(n)) ⊆ O (g(n)) .

This means that Θ is a subset of O . Both the statements seem contradictory.

Lets refactor and reword these statements for ease of thought.

Let $A(n)$ be $Θ(g(n))$.

Let $B(n)$ be $O(g(n))$.

  Note that $A$ implies $B$ because $A$ is stronger than $B$.

This means for $A$ to be fulfilled we have to fulfill the criteria of $B$ and more. Therefore $A$ being fulfilled implies $B$ must also be.

  Written set theoretically, we have the set of functions that fulfill the criteria of $A$ are a subset of the functions that fulfill the criteria of $B$.

Well this is not contradictory, but actually equivalent in a sense to the last statement which showed that $A$ has the criteria of $B$ and more.

From our understanding of this point we can determine that: All the functions that fulfill the criteria of $A$ fulfill $B$, but not all functions that fulfill the criteria of $B$ fulfill the criteria of $A$.

This is really an equivalent statement to: The functions that fulfill the criteria of $A$ are a subset of the functions that fulfill the criteria of $B$ because the second set contains the first.

And therefore $\Theta(g(n))\subseteq O (g(n))$ is true, and it is equally true that $f(n) = \Theta(g(n))$ implies $f(n) = O(g(n))$ without any contradiction.

Furthermore this makes sense with the definition for $\Theta(g(n))$ which states that:
$f(n)\in \Theta(g(n))$ if and only if $f(n) \in O(g(n))$ and $f(n) \in \Omega(g(n))$. Clearly by this definition, $f(n) \in Θ(g(n))$ does imply $f(n) \in O(g(n))$, and $\Theta(g(n))$ is clearly a subset of $O(g(n))$ as well.


Timing threads in an algorithm This question relates to timing threads to go at a very precise rate. Consider the following scenario; A program creates a series of threads that continually add a random set of elements to their local storage. The program finishes and returns the thread that received the shortest number of elements in its random set. If one thread was to go faster than another, the program would be incorrect. Is there a way to "lock" the threads to go at the same speed? If so would it be possible for someone post a quick python or other language script that performs this task?

If more info is needed, please post

You are probably looking for a barrier synchronization primitive.  Each thread calls into the barrier when it is done creating its set.  Only when all the threads have called into the barrier are any threads permitted to proceed.

If your programming language doesn't include a barrier primitive, then you can fake it, in your example, simply by having the main thread sit in a loop and join with all the children thread as the children finish and return from their computation.  The loop should only exit when it sees every child thread finish.


Examples of simple/common problems with quadratic running time Are there some examples of simple or common problems which have (in a practical sense) quadratic complexity? I would have thought there were a lot of them, but upon further investigation, I can't seem to find any. (see https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations)

Bubble sort / insertion sort are $O(n^2)$ worst-case, but there are tons of simple $O(n \log n)$ sort algorithms
Multiplication of $n$-bit numbers is $O(n^2)$ for the conventional method, but then you have Karatsuba multiplication which is $O(n^{log_2 3} \approx n^{1.58})$
Matrix multiplication is $O(n^3)$ for conventional implementation but in the $O(n^{2.376})$ to $O(n^{2.807})$ range for more clever implementations
Fast Fourier Transform is $O(n \log n)$ instead of the simple $O(n^2)$ DFT
Dijkstra's algorithm was $O(|V|^2)$ but someone thought of a $O(|E|+|V| \log |V|)$ implementation

It is true that many algorithms that have quadratic running time are not the state of the art for their problems today. Among which are quadratic sorting algorithms for example bubble-sort, select-sort and insertion-sort, which are overcome by merge-sort and heap-sort. On a side note, quick-sort, the standard sorting algorithm in different areas, has a worst running time of $O(n^2)$ and is only used because the probability of having bad running time (say worse than a constant factor of $O(n \log n)$ is very small and it has smaller overhead than the other efficient sorting algorithms).
Also solving maximum matching on bipartite graphs by reducing to maximum flow and solving with Ford and Fulkerson's method is $O(nm)$ which is quadratic in sparse graphs, which is again overcome by the algorithm from Hopcroft and Karp with running time $O(\sqrt n m)$.
However, some of the problems with quadratic running time are conjectured to be optimal up to a log factor. These problems are not only interesting because of their quadratic running time and that this time is probably optimal, but also because they lead a list of problems that are either as hard or strictly harder than them.
The 3-sum problem

The problem. Given a set of $n$ integers, find if 3 of them add up to zero.
Quadratic algorithm. Sort the values in the list. For each value $v$ in the list, look if there are two values summing up to $-v$. Such a search can be done in $O(n)$ in sorted array using sliding window technique. Since we do it for every element in the list we get a running time of $O(n \log n + n^2) = O(n^2)$. Note that the $n \log n$ is for sorting the array as a pre-processing step.
Similar problems. The problem has many variants that are equivalent in a sense that have the same running time. Including the version of the problem where repetitions are not allowed or the version where you get three sets of values and you have to choose a value form list to sum up to zero (or to some value $v$). More Interesting are the reductions from the 3-sum problem variants to different Geometry problems as checking a point-set in the plane if three are co-linear. This problem is solvable in quadratic time using the point/line dual construction and is also expected to be optimal by the 3-sum conjecture. Another example is the Geombase problem, where you have a set of points each lying on one of the lines $y=0;y =1$ or $y=2$ and you need to find if there is a non horizontal line crossing three of the points. This problem is also equivalent to three sum in the sense that the reduction can be done in both directions. Similarly, the problem given a set of $n$ lines, do three of them intersect in one point is almost optimal in $O(n^2)$ if 3-sum conjecture is true.

The orthogonal vectors problem.

The problem. Given a set of $n$ vectors of dimension $d$, are two of them orthogonal.
The algorithm. For constant values of $d$, checking all pairs of vectors is in $O(d n^2) = O(n^2)$.
Similar problems. Based on this conjecture, the following problems are almost optimal with a running time of $O(n^2)$. Edit distance, longest common subsequence and graph diameter in sparse graphs.

Here is a brief description for each of these problems:

Edit distance: Given two strings, what is the least number of modifications (deletions, insertions..) are needed to make the strings equal. The problem can be generalized to a set of operations on both or one of the strings and cost for each operation and we want to minimize the total cost.
Longest common subsequence: Given two strings, a subsequence of the string is a string resulting from the original string by deleting some characters. What is the longest string that is a subsequence of both input strings (Note that this problem is a special case of edit distance.
Graph diameter is the longest shortest path in the graph, that means the minimum $d$ such that you can go from any node to any other node in less than $d$ steps.

Note there is a reduction from SAT to Orthogonal vectors proving that if the Orthogonal vectors conjecture fails, then SETH fails as well.


Why aren't computables used for numerical calculations? In programming languages like Haskell you can use lazy evaluation to delay calculations.

Why isn't a similar approach being used for numerical methods (I understand that there would be memory implications).

The approach would be that non-integer values would be stored as how they are calculated, so that the next digit can be found when requested.

This kind of approach should allow every value to be calculated to the correct number of significant figures.

Sorry that this is slightly garbled.

It sounds extremely inefficient compared to floating point. We have a very good understanding of how to control the errors in floating-point calculations (e.g., adding small numbers before large ones, avoiding taking the difference of large numbers and so on) so the only benefit of the methods you're suggesting would appear to be that they offer increased precision. But, for almost all applications, 64-bit floating point is more than enough and the speed of being able to do calculations with single CPU (or GPU!) instructions is a huge win.


Is the set of CFGs that contain all odd and even length words Turing-decidable? $ALLEVEN_{CFG}$ = {M is a grammar, and L(M) includes all strings of even length in $\Sigma^*$} = {(M): ($\Sigma\Sigma$)* ⊆ L(M)}

$ALLODD_{CFG}$ = {M is a grammar, and L(M) includes all strings of odd length in $\Sigma^*$} = {(M): $\Sigma$($\Sigma\Sigma$)* ⊆ L(M)}

Is $ALLEVEN_{CFG} \cap ALLODD_{CFG}$ Turing Decidable?

I thought that this was yes because ALLEVEN would produce strings that are only even in length. ALLODD would produce strings that are only odd in length. The intersection would then be producing strings that are both even and odd in length, which is nothing. This means that we can reduce the problem to $E_{CFG}$ which is a decidable.

However, my professor says that $ALLEVEN_{CFG} \cap ALLODD_{CFG}$ is exactly $ALL_{CFG}$ which is not decidable. I am not sure how he reached the conclusion that it is equal to $ALL_{CFG}$.

The problem is that you interpret e.g. "grammars that generate all even length strings" as "grammars that generate only all even length strings", which is wrong. If you look at it this way, the intersection you are looking for is grammars that generate all even length strings and all odd length strings, i.e., grammars that generate all of $\Sigma^*$


PDA accepting all words not of the form $b^na^n$ I am studying Automata theory. DFAs and NFAs seem pretty straightforward to me, but I don't quite understand how to design push-down automata for context-free languages.
If I have context-free language where the
input  alphabet is $\{a,b\}$
$L = \{w \text{ where }w\text{ is NOT of the form }b^n a^n\}$
How would I design a push-down automata for it? What are the steps I would need to take, and what would it look like (formal description)?

The PDA has two main states:

No $a$ has been encountered.
Some $a$ has been encountered.

While in the first state, it pushes $B$ onto the stack for any $b$ it encounters. It moves to the second state when encountering an $a$, at which point it removes $B$ from the stack for any $a$ it encounters (including the first $a$). If it ever realizes that it has seen more $a$s than $b$s, or if it encounters $b$ again, it can immediately accept (depending on your model, you might have to read the remainder of the input). After finishing reading the entire input, if the stack contains at least one $B$ then it accepts, and otherwise it rejects. You can implement this by requiring the PDA to pop at least one $B$ before accepting.
Formally describing this PDA depends on the exact definition of PDAs in your class, and in any case, it is an exercise which is best for you to do on your own.


If a problem is in P solved via dynamic programming, is it also in NP? So I can solve a given problem using dynamic programming in $O(n^2k^2)$ time complexity. This means that the problem is in P. But I am asked if it is in NP.

My answer is, "Since it is also polynomial time solvable, the problem is also in $NP$".

Is that a correct statement? If not, is a problem in P solved via dynamic programic also NP?

Any problem in P is also in NP

A decision problem that's in P is also in NP, because you can give the verification logic like this: for yes instance x, use empty string as a certificate, and solve x in polynomial time. You get the result that it's yes instance (that's by definition of P) and that means verification is done in polynomial time.

Note that, the order written as $n^2 k^2$ doesn't simply mean the problem is in P (Check "Pseudo-polynomial time" in wikipedia.) For example, Knapsack problem can be solved by the dynamic programming and its order is $O(n W)$ where $n$ is the number of products and $W$ is the maximum weight for the knapsack. But $W$ is actually considered exponential of the input size and Knapsack problem is known to be NP-complete.


Proving the regularity of a certain language I've been fumbling around with this problem for the last hour, and I'm incredibly stumped.

Let $A = \{\; 0^ku0^k \mid k ≥ 1 \text{ and }u ∈ Σ^*\;\}$. Show that $A$ is regular.

The language obviously satisfies the Pumping Lemma, but that is not conclusive for regularity. How on earth do I prove that this language is regular? I'm aware of all the normal methods (closed-under, etc), but I cannot for the life of me figure out the appropriate condition to continue.

It is a trick question. You can find a simpler form to describe the language.


Constructing PDA to accept language { $a^i b^j c^k \mid i,j,k \geq0, i+2k = j$ } I'm trying to understand the approach to constructing a PDA which accepts the language { $a^i b^j c^k \mid i,j,k \geq0, i+2k = j$ }

Hint: The PDA has three phases: an $a$ phase, a $b$ phase and a $c$ phase. Your goal in the $a$ phase is to "compute" $i$ by strong an appropriate load on the stack. Your goal in the $b$ phase is to compute $j-i$. Finally, your goal in the $c$ phase is to compare $j-i$ to $2k$.


What are these questions in the PoplMark challenge asking? I was reading the paper Mechanized Metatheory for the Masses: the PoplMark Challenge by Aydemir et al (PDF) and I found the following three questions on page 13 of the PDF a bit confusing.

  Challenge 3: Testing and Animating with respect to semantics.

  Given $\mathrm{F}_{\texttt{<:}}$ terms $t$ and $t'$, decide whether $t\rightarrow t'$.
  Given $\mathrm{F}_{\texttt{<:}}$ terms $t$ and $t'$, decide whether $t \rightarrow^* t' \not\rightarrow$, where $\rightarrow^*$ is the reflexive-transitive closure of $\rightarrow$.
  Given an $\mathrm{F}_{\texttt{<:}}$ term $t$, find a term $t'$ such that $t\rightarrow t'$.

I think question (3) is saying reduce a term $t$ to $t'$ until which is no longer can be reduced (or become a value). What about question (1), are they just saying check the result if it is equal to some term $t'$? and question (2).

Could someone explain me their differences?

The reduction relation is beta reduction (for term and type variables) as defined in the description of Challenge 2B. It's a single reduction step, not repeated reduction until a value is reached.

(3) says to find a term $t'$ such that $t \to t'$ because if one exists, then there are infinitely many such terms in $F_{<:}$: all the terms in the same alpha equivalence class. Usually we say that beta reduction is deterministic, i.e. $t'$ is unique, but that's because we reason on alpha equivalence classes. PoplMark is concerned with the representation of variable binding, so here terms are a concrete representation where variable binding is treated explicitly. For example, in a nominal representation, $(\lambda \texttt{x}. \texttt{x}) (\lambda \texttt{x}. \texttt{x}) \to (\lambda \texttt{x}. \texttt{x})$, and $(\lambda \texttt{x}. \texttt{x}) (\lambda \texttt{x}. \texttt{x}) \to (\lambda \texttt{z}. \texttt{z})$; (3) allows finding any of these since they are all equally valid.

Similarly (1) asks to check whether $t'$ is a possible result of reducing $t$, not the result: the implementation of the reduction (item (3)) might find a different representative of the alpha equivalence class from the one submitted by the user.

Only (2) is about reducing to a value. It says so explicitly: $t$ reduces to $t'$ in any number of steps, and $t'$ cannot be reduced.


Find permutation minimizing distance You have a square matrix of weights $W$ and a square matrix of distances $D$. You want to find a permutation $\sigma$ minimizing $$\sum_{i,j} W_{i,j} D_{\sigma(i), \sigma(j)}$$

Is there a known algorithm for that? Is the problem NP-complete? Is the optimal solution easily approximable?

Your problem appears to be very close to the minimum quadratic assignment problem, see for example a paper by Hassin, Levin and Sviridenko; your problem is close to the metric variant (since $D$ is a metric). When $D_{i,j} = |i-j|$ we get the NP-hard problem minimum linear assignment, whose best known approximation ratio is $\tilde{O}(\sqrt{\log n})$.


On the fly manipulation of operators Assume that you are writing sorting algorithms, and that you want the ability to select between ascending and descending order. The only change required to do this for comparison sorts is to use the inverse of the comparison operator (for example: > becomes <). This begs the question, why is it not possible to change operators on the fly?

A simple bubble sort for ascending order:

private T[] BubbleAscending(T[] sortMe)
    {

        bool stopMe = true;
        int stopRecurse = sortMe.Length - 1;
        int optimizeMe = stopRecurse;

        for (int i = 0; i < stopRecurse && stopMe; i++)
        {
            stopMe = false;

            for (int j = 0; j < optimizeMe; j++)
            {
                if (sortMe[j].CompareTo(sortMe[j + 1]) > 0)
                {
                    Swap(sortMe, j, j + 1);
                    stopMe = true;
                }
            }

            optimizeMe--;
        }

        return sortMe;
    }

Now we have to have a Bubble sort for descending order:

private T[] BubbleDescending(T[] sortMe)
    {

        bool stopMe = true;
        int stopRecurse = sortMe.Length - 1;
        int optimizeMe = stopRecurse;

        for (int i = 0; i < stopRecurse && stopMe; i++)
        {
            stopMe = false;

            for (int j = 0; j < optimizeMe; j++)
            {
                if (sortMe[j].CompareTo(sortMe[j + 1]) < 0)
                {
                    Swap(sortMe, j, j + 1);
                    stopMe = true;
                }
            }

            optimizeMe--;
        }

        return sortMe;
    }

Now we have to have some logic to allow the user to easily select between them:

public T[] BubbleSort(T[] sortMe, bool descending)
    {
        if (!descending)
            return BubbleAscending(CopyArray(sortMe));

        else
            return BubbleDescending(CopyArray(sortMe));
    }

Wouldn't it be much simpler if we could do this?

public T[] BubbleSort(T[] sortMe, bool descending)
    {
        if (!descending)
            operator comparison = >;

        else if (descending)
            operator comparison = <;

        bool stopMe = true;
        int stopRecurse = sortMe.Length - 1;
        int optimizeMe = stopRecurse;

        for (int i = 0; i < stopRecurse && stopMe; i++)
        {
            stopMe = false;

            for (int j = 0; j < optimizeMe; j++)
            {
                if (sortMe[j].CompareTo(sortMe[j + 1]) comparison 0)
                {
                    Swap(sortMe, j, j + 1);
                    stopMe = true;
                }
            }

            optimizeMe--;
        }

        return sortMe;
    }

Welcome to the wonderful world of functional programming and the lambda calculus!

The answer is, there is no reason that you can't do this, and most sufficiently modern programming language (and some ancient ones i.e. LISP) will let you do this.

In a language with first-class functions, functions are data. You can treat them as variables, pass them as parameters, define them as lambda expressions (i.e. a nameless function). So in most languages, you can do something like this:

if (descending)
  comparison = lambda x y -> x < y
else
  comparison = lambda x y -> x > y

The lambda is just a way of saying "comparison a function which takes two arguments and returns the value after the ->".

Treating functions as data is an idea as old as computer science itself: lambda calculus was developed by Alan Turing's supervisor, Alonzo Church, in the 1930s.

Not being able to do this is a restriction of C and Java (although new versions are introducing lambdas), and a few other languages.

What you've shown is probably not possible because it's hard to parse (most parsers rely on the fact that < and > are special characters), but if you treat comparison as a normal function instead of an infix operator, and use a language that allows for higher-order functions, you can indeed do this, and in many cases it is preferable.


Are Regular Languages (as we represent by Finite State Machines) Fields? I am aware that we can do set operations on them, and sets are fields. Are regular languages also mathematical fields?

No, the set of regular languages is not a field, but it is a boolean algebra.  It also qualifies as a field of sets -- but note that the term "field of sets" has nothing to do with the notion of a "field"; it's an unfortunate name collision.  See also https://en.wikipedia.org/wiki/Boolean_algebra_(structure).


Trying to prove semidecidability of an undecidable language I have been having a hard time understanding whether the set $S = \{ M \mid |L(M)| = 5 \}$ is semidecidable or not, where $M$ is a generic Turing Machine and $L(M)$ the language accepted by such TM, which consists of exactly five strings. Because $S$ is a property of the accepted language (there exists a TM that recognizes $L$), hypothesis of Rice Theorem applies, and because the set is not empty nor it is the set of all computable functions (equally, $S$ is non-trivial), it is undecidable. Yet, is it semidecidable? I was kinda attempting to prove that the complement of $S$ is semidecidable (thus guessing that $S$ is not semidecidable), but couldn't come up with anything useful.

We know that the halting problem is semidecidable, but the non-halting problem is not semidecidable (since otherwise the halting problem would be decidable). Hence one way to show that a language is not semidecidable is by reduction from the non-halting problem.

Let $\langle M,x \rangle$ be an input the the non-halting problem. We construct a new Turing machine $M'$ which on inputs $1,2,3,4,5$ halts, on input $6$ simulates $M$ on $x$, and on all other inputs never halts. Then $M' \in S$ iff $M$ doesn't halt on $x$.

We can also construct another Turing machine $M''$ which on inputs $1,2,3,4$ halts, on input $5$ simulates $M$ on $x$, and on all other inputs never halts. Then $M'' \notin S$ iff $M$ doesn't halt on $x$.

These reductions show that neither $S$ nor its complement are semidecidable.


Is every language over any alphabets is accepted by automata? The answer is no to what i have learned but i am finding difficulties to absorb it reason being . We say for every language we have a grammar as language without grammar makes no sense even in general scenerio also. i have taken this argument as my base for the conclusion of my answer as i found this argument somewhere on stackexchanege please correct me if iam wrong.

coming to point , as there are grammar for every language which also indicate existence of set of rules for the formation of the language. Taking this ahead , i wonder if we can device a set of rules which is indeed a process to derive or generate a solution then why cant we form an automata for the same. Adding more to this point , we know the highest class of automata is turing machines capable of accepting many languages but not all , and we know that the languages not accpeted by turing machines have grammars( as said every language has grammar) means there are some machines automata that does not necessarily satisfies the all the langugaes not accepted by turing machines but do satisfy some but all of them , using this we say there are different classes of machines which are not turing but accept some   languages not accpeted by turing machines if this is not true than there must exist the languages that do not have any grammar but as said every languae has grammar.  adding more woes to this argument , we have not able to identify any machine more powerful then turing , so this means some of the arguments made here are wrong . but i am finding it difficult to understand which one of them is wrong, so please let me know.

Suppose that $\mathcal{M}$ is any kind of machine model in which every machine has a finite description, say as a binary string. The model can be more powerful than mere Turing machines – for example, it could be Turing machines with access to an oracle for the halting problem.

Since every machine has a finite description as a binary string, there are only countably many machines, and so countably many languages they accept. Since there are uncountably many languages, there must be some language not accepted by any $\mathcal{M}$-machine. In fact, most languages aren't, in the sense that a random language would not be accepted by any $\mathcal{M}$-machine.

The only way out is if machines do not have a finite description. But this is not what we usually understand by machine. An example of such a "machine" is one in which an arbitrary language is hardwired. Such machines can, by definition, accept all languages, but they are not so interesting mathematically.


Decidability of equivalence problem with limit I already know, that the language $$L_0 = \{m \mid \text{the Turing machine $m$ does not stop on an empty tape}\}$$ is not decidable.
If I want to know, if $$EQ = \{\langle m, n \rangle \mid L(m) = L(n)\}$$ is decidable I can reduce $L_0$ to $EQ$.
Because $(L_1 \setminus L_2) \cup (L_2 \setminus L_1) = \emptyset$ iff $L_1 = L_2$, $EQ$ is also not decidable.

But what happens if a limit is added? For example the language $$EQ_{\lim} = \{\langle m, n \rangle \mid \exists x_0 \in \mathbb{N}\colon \forall x > x_0\colon m(x) = n(x)\}.$$

Is it (semi-)decidable? I also try to reduce from the halting problem (more specifically the inverse of the halting problem to proof also semi-decidability), but without success.

You can still reduce $L_0$ to $EQ_{\lim}$. Given a Turing machine $m$, construct a Turing machine $m'$ which deletes its input and then transfers control to $m$, and let $n'$ denote a (fixed) Turing machine which halts on no input. Then $m \in L_0$ iff $\langle m',n' \rangle \in EQ_{\lim}$.


number of different undirected graphs? The question is:

How many different undirected graphs are there with n nodes and no parallel edges but may include self-loops?

I've been wracking my brain over this for hours now. Basically, I know that for 1 vertex, there are 2 graphs. For 2 vertices, there are 8 graphs. For 3 vertices, there are 64 graphs. However, I can't connect these numbers without my answer for 1 vertices not working. For example, the equation number of graphs equals $2^{3n-3}$ works for 2 and 3 vertices, but not for 1. Any opinions on the connecting equation?

Undirected graphs with self-loops on $n$ vertices have $\binom{n}{2} + n = \binom{n+1}{2}$ potential edges. Therefore the are $2^{\binom{n+1}{2}}$ different graphs. For $n = 1,2,3,\ldots$, this is
$$ 2^1, 2^3, 2^6, 2^{10}, 2^{15}, 2^{21}, 2^{28}, 2^{36}, 2^{45}, 2^{55}, \ldots $$


Is it possible to build any regular expression in a computer language with just 3 basic operators? Many computer languages have complex regular expressions tools. For example, in Javascript you have global flags, escape characters, whitespace character, assertions, character classes, groups and ranges etc. I'm wondering if using just the 3 basic regular expressions operators as defined in formal languages, that is concatenation, alternation and Kleene star can achieve the same result as any pattern described with more tools as for example in Javascript. Is there a theorem about this?

Regular expressions using only concatenation, alternation and Kleene star describe regular languages. In contrast, extended regular expressions available in modern programming languages can describe non-regular languages. For example, (.*)\1 describes the language $\{ ww : w \in \Sigma^* \}$, which is not even context-free.


How to check equality between any two 2-dimensional arrays (dense matrices) with time complexity less than O(n*m)? Here, n = no. of rows and m = no. of columns

Suppose, there are three matrices - A[3][2] : {{1,2},{3,4},{5,6}} ;
B[3][2] : {{1,2},{3,4},{5,6}} ;
C[3][2] : {{2,1},{3,4},{5,6}} .
Here A=B , A!=C and B!=C .

So, task is to check equality between all possible combinations of 2-dimensional matrices from a given set of matrices with time complexity less than O(n^m) .Here the possible combinations are (A,B) , (A,C) and (B,C).

( As part of the solution :

Matrix to matrix comparison is costly .So these matrices have to be converted into 'something' which results less comparison time . I think if I can convert/represent the matrix as a value/string/1-dimensional array , then equality comparison will be less costlier . My question is how to convert/represent ? If it can be solved by hashing how to solve this exactly ? )

NOTE : No. of 2-dimensional matrices and their sizes are not fixed. In my problem scenario no. of 2-dimensional matrices are been generated gradually which can be of any size. Cant predict how many matrices of which size will be generated . Here my main task is to identify all possible equal matrices among the set of all generated matrices . Main idea is - whenever a new 2D matrix generates, check if it has been already generated or not. If yes , we can say 'identical matrices found'; If no , continue checking for other matrices .

Here my main task is to identify all possible equal matrices among the set of all generated matrices . Main idea is - whenever a new 2D matrix generates, check if it has been already generated or not. If yes , we can say 'identical matrices found'; If no , continue checking for other matrices .

It seems it would be easiest to store the previously seen matrices in a Trie. You can then test whether the given input matrix is equal to any of the previous matrices in $O(nm)$, regardless of how many previous matrices there are. This is the best you can do, since you must examine each element of the matrix at least once. You can't get an individual comparison to run faster than $O(mn)$, but you can test for equality among the entire set faster.


Deadlock prevention by killing a victim In our operating systems class, the teacher told us about deadlocks prevention methods. One of them is that to select as a victim the process which requires the CPU time or one that requires a lot of resources, and remove this process. The next time the algorithm is called, it may be possible that again the same process becomes the victim. This causes starvation.

I'm confused: if the victim process is terminated, then how can it again become part of the deadlock?

The idea is that the process is not terminated: only the current operation is cancelled. The process reacts to the cancellation by trying again. In this model, it is assumed that each process runs something like the following pseudocode:

begin_transaction:
    try:
        acquire(lock_1);
        acquire(lock_2);
        …
        release(lock_2);
        release(lock_1);
    with Cancelled:
        goto begin_transaction

Without any form of deadlock prevention, the processes would get stuck forever. Cancelling one of the processes (in a way that releases its locks) prevents that.

This form of deadlock prevention only works if processes are written in the expected way and can cope with cancellation. It does not generalize to arbitrary programs.


How does sum of first $k$ integers equal $k(k+1)/2$ According to this video, he explains
$$p = k(k+1) / 2$$
Where $p$ is the sum of the first $k$ natural numbers. I understand $k$ means times of repetition and $k+1$ is how it increments, but why does he divide by $2$? I can't justify it.

Here is what the video describes:

for (i = 1; i <= n; i++)
  p += i

$$\begin{array}{|c|c|}
\hline i & p \\
\hline 1 & 1 \\
\hline 2 & 3 \\
\hline 3 & 6 \\
\hline 4 & 10 \\
\hline \vdots & \vdots \\
\hline i & i(i+1)/2 \\
\hline
\end{array}$$

Let me tell you the story of young Carl Friedrich Gauss.

He was six years old and in a small school with one class for everyone from 6 to 16. His teacher needed some quiet time for some job, so he asked the kids to add up the numbers 1 to 1000.

30 seconds later young Carl Friedrich had the answer: 500,500.

How did he do it?

He changed the order and added 1+1000, 2+999, 3+998 up to 500+501. Each sum is 1001, and there are 500 sums, so the result is 1001 * 500. Obviously k=1000, so this is (k+1) * k / 2.

You can use this for adding numbers in any arithmetic progression: sum = (first + last) * count / 2.


Proving bounds for a function I'm kinda confused by Asymptotics, the exercises in the book I'm reading say to prove for example $f(n) = \Omega(g(n))$, and there is something I don't understand about these kind of proofs.
Do I have to prove them algebraically or is it possible to find some constant ($c$) such that this statement holds?
For example would it be correct to write $(n + a)^b = \Omega(n^b)$ since $ (n + a)^b \gg 1 \cdot n^b$?
Any help would be much appreciated.

By definition it's enough to show existence of $c>0$, and, also existence of $N \in \mathbb{N}$, for which $f(n) \geqslant c g(n)$, when $n \gt N$. Of course, if it's possible to find $c$, then proof is also done.
In case of $(n + a)^b = \Omega(n^b)$, assuming $a,b>0$, then choice $c=N=1$ fulfills definition, as we have $(n + a)^b \geqslant  n^b$.
BTW, holds also $(n + a)^b = O(n^b)$, so $(n + a)^b = \Theta(n^b)$.


I don't know how to prove a simple theorem used with fixpoint in Coq I am a beginner in coq and want to prove the following theorem t1. First I used induction i and destruct j, but it got bogged down in the middle.
I would like some hints for this problem.

Function f takes two arguments of nat and returns Prop (e.g., f 2 4 = x 2 ∧ x 3 ∧ x 4 ∧ x 5).

Theorem t1 shows that a head of function f can be cut and concatenated (e.g., x 3 ∧ f 4 7 ⇔ f 3 8).

Parameter x : nat -> Prop.

Fixpoint f (o i : nat) : Prop :=
 match i with
 | S O =>  x (i+o-1)
 | S i' => f o i' /\ x (i+o-1)
 | _ => True
 end.

Theorem t1 : forall i j : nat,
    x i /\ f (S i) j <-> f i (S j).
Proof. Admitted.

You are making your life difficult by defining things in convoluted ways. Here's how a better definition of the same thing makes the proof easy.

Fixpoint f_better n0 len : Prop :=
  match len with
  | 0 => True
  | S k => x n0 /\ f_better (S n0) k
end.

Theorem t1_better: forall n0 len,
    x n0 /\ f_better (S n0) len <-> f_better n0 (S len).
Proof.
  easy.
Qed.

If you really insist on using your version, we can prove that as well, but it'll be painful.


What is the specific name for basic data types? What is the specific name for data types such as integer, string, real (the basic ones)?

They are called primitive data types.

(This is a pretty basic find in Wikipedia's article on data types.)


facts on tree and MST We are given an Undirected, Weighted and Connected Graph $G$, (non-negative weights, all distinct) with one property that shortest path between any two vertexes on this graph is on MST.
The following Facts is False, and True.
$I$) Graph $G$ is a Tree.
                False.

$II$) weight of each ${u,v}$ edge, is at least equal to heaviest edge in shortest path from $u$ to $v$.
                True.

Anyone can describe me why the second fact is hold? Intuitive idea or
example or proof?

Assumption $II$ is true for any general graph with non-negative edge weights, including the graph $G$ with specific properties. To understand this, think about the inverse of the statement.
Let's assume the weight a $u,v$ edge is lighter than edge $e$ on the shortest path. The shortest path is made out of $e$ + $C$ where $C$ is some constant. Because $C >= 0$(non-negative graph) and $e$ < edge between $u,v$, by definition the shortest path we have assumed to be optimal is not(because the edge directly connecting $u$ to $v$ would be shorter).
To your specific graph into this, this lighter edge from $u,v$ cannot exist because if it did, it would have to be part of the minimum spanning tree(and thus part of the shortest path as mentioned in your description).


Data compression - Entropy Let's say I have an alphabet
$$\Sigma = \{A, B, C, D, E\}$$

with probabilities
$$P(A) = P(B) = P(C) = 0.25 \text{ and } P(D)=P(E) = 0.125.$$

I know that the entropy then is:
$$H(\Sigma) = 3 \cdot 0.25 \cdot \log 4 + 2 \cdot 0.125 \cdot \log 8 = 2.25.$$

My question now is: What does this mean in relation to the lower limit of compression? How many bits will I at least need to compress a text that consists of the above alphabet?

The idea is to decode the more frequently used symbols with less number of bits than the less used ones

So ur example means we can compress more if we decode A, B, C in less bits than E, D rather than equiprobable decoding
    By Huffman Coding A, B, C is represented by 2 bits (that's log 4); while D, E  take 3 bits (log 8)
    This way ur expected coding size is minimal (2.25* text length) because u expect ur file to have 0.25 of its characters as A,... 0.125 as E,...

I hope this makes it clear...


Why is the hitting set problem in NP I am citing the definition of the Hitting Set Problem from (Gardy & Johnson, 1979):

  INSTANCE: Collection $C$ of subsets of a set $S$, a positive integer $K$.

  QUESTION: Does $S$ contains a hitting set for $C$ of size $K$ or less, that is, a subset $S' \subseteq S$ with $|S'| \leq k$ and such that $S'$ contains at least one element from each subset in $C$?

The problem definitions from other sources (none of which elaborates on the size of $C$ in relation to $|S|$):

https://theory.stanford.edu/~virgi/cs267/lecture5.pdf

http://cs.indstate.edu/~arash/algo2lec8.pdf

http://www.et.byu.edu/~jka/521/slides/lecture22.pdf

http://www.cs.toronto.edu/~lalla/373s14/assignments/A3Sol.pdf

http://www.cse.iitd.ernet.in/~amitk/SemI-2015/tut12.pdf

Given a set $S$ with $|S| = n$, a collection $C$ of its subsets can have up to $2^n$ elements (where each element is a subset of $S$).

Given a certificate, $S' \subseteq S$, of the Hitting Set Problem, how could we possibly check if $S'$ contains at least one element from each subset in $C$ in polynomial time w.r.t $n$?

You cannot check, in general, whether $S'$ contains at least one element from each subset $C$ in polynomial time w.r.t. $n$.

However, in order to show that the problem is NP it suffices to show that you can check to above condition in polynomial time w.r.t. the instance size, which is in $\Omega( \sum_{X \in C} |X| + \log n)$.


Proof of proposition between Precise Turing Machine and Proper Complexity function In "Computational Complexity" textbook by C. H. Papadimitriou, p. 141, he proved the following claim.

  Proposition 7.1: Let there be a DTM/NDTM M that decides a language L within time/space $f(n)$, where $f$ is a proper function. Then there is a precise TM $M'$ that decides L in time/space $O(f(n))$.

Proof. We start simulating $M'$ on input $x$ by $M_f$ ($M_f$ is same as M, it is TM with proper function $f$ on input $x$). After $M_f$'s computation has halted, $M$ uses the output string of $M_f$ as a "yardstick" of length $f(|x|)$, to guide its further computation. Now, we have two cases depending on the resources: $f(n)$ is time bound or space bound.

For if $f(n)$ is time bound, then $M'$ simulates $M$ on a different set of strings ($x_1, x_2, ...$ where for such i, $x_i$ is an arbitrary string), using the yardstick as an "alarm clock". i.e., it moves its cursor forward on the yardstick after the simulation of each step of M, and halts iff a true blank is encountered in $O(f(n))$ steps. For if $f(n)$ is space bound, then $M'$ simulates M on the quasiblanks of $M_f$'s output string. In either case, the machine is precise.

If M is NDTM, then precisely the same amount of time/space is used over all possible computations of $M'$ (the simulation of $M_f$). In both cases, the time/space is the time/space consumed by $M_f$ plus that consumed by M, and it therefore $O(f(n))$.

What is "yardstick" or 'alarm clock'? Are they the same? It is not clear what is it. Is it indicator to such i, where i is cell in tape in the Turing machine. It seems for me 'alarm clock' looks like a step in $M_f$ of simulation with $M$. So, every step is counted and stop when we simulate $M_f$ by $M$ in $O(f(|x|))$ steps.

It is not clear why do we need exactly to define $M_f$? I mean, we could simulate $M'$ by M directly without $M_f$, don't agree.

NOTE: for definition of precise TM and proper complexity function, please refer to the book pp. 140-141, or look at some slides [4-6] [here 1].

For interested readers, here are some of related definitions.

A function $f : \Bbb N \to\Bbb N$ is a proper complexity function if $f$ is nondecreasing and there is a $k$-string TM Mf with input and output such that on any input $x$,

$M_f(x) = \sqcap^{f(|x|)}$ where $u$ is a tally (“quasi-blank”) symbol,
$M_f$ halts within $O(|x|+f(|x|))$ steps, and
$M_f$ uses $O(f(|x|))$ space besides its input.

Let $M$ be a deterministic/nondeterministic multi-string Turing machine (with or without input and output). Machine $M$ is precise if there are functions $f$ and $g$ such that for every $n\ge 0$, for every input $x$ of length $n$, and for every computation of $M$,

$M$ halts in precisely $f(|x|)$ steps and
all of its strings (except those reserved for input and output
whenever present) are at halting of length precisely $g(|x|)$.

Proposition 7.1 is intuitively simple and clear. If there is such a $M$, we can just extend the computation steps or space used by $M$ to the same limit $g(n)$ for all inputs of the same length $n$, where $g(n)$ is some function large enough but still bounded by $O(f(n))$.

It is not clear why do we need exactly to define $M_f$? I mean, we could simulate $M'$ by M directly without $M_f$.

The issue is how you can make $M'$ precise? For different inputs of the same size, $M$ can halt at different number of steps using different amount of spaces. You must have some reference or standard that can display or communicate the expected number of computation steps or spaces, which $M'$ can look up to and adjust itself to.

What is "yardstick" or 'alarm clock'? Are they the same?

A yardstick is "a fact or standard by which you can judge the success or value of something", according to Cambridge dictionary. That is the "reference or standard" I just said in my last paragraph.
For the sake of simpler explanation, let us assume $M$ is a deterministic $t$-string Turing machine with time bound. Here is how we construct $M'$ in slightly more detail.
Suppose $M_f$ is defined on a $k$-string Turing machine. We will define $M'$ on a $(k$+$t)$-string Turing machine.
Let $x$ be a given input of size $n$, which is given at the start of the first string (tape).
First, $M'$ will copy the input to the start of the $k$+$1$-th string (tape).
Second, $M'$ simulate $M_f$ with input $x$ using the first $k$ strings. Then reset $M'$ state to initial state, without touching the quasi-blanks on the first $k$ strings.
Third, $M'$ simulate $M$ using the remaining $t$ strings, the $k$+$1$-th, $k$+2-th, $\cdots$ and $k$+$t$-th strings. At the same time, whenever $M'$ make one computation step, it will advance its heads on the first $k$ strings once.
Lastly and most importantly, if the simulation of $M$ by $M'$ halts before $f(n)+1$ time, just continue to move the heads on the first $k$ strings until a true blank is encountered, which is an alarm and why this part is referred as "an alarm clock". Then $M$ will halt. This step homogenizes the running time of $M$.
It is possible I miss a detail in a place or two. Besides, there is a problem of choosing which head to move when we stipulate $M'$ to advance its head. I will let you figure out how to fill this obvious loophole. In any case, the idea and concept here are pretty easy to grasp, although the details are long, tedious and error-prone. Just make sure you have convinced yourself and you are confident to convince anybody.

More information can be found in Turing Machines as Clocks, Rulers and Randomizers written by José Félix Costa.


Solve Recurrence for $T(n) = 7T(n/7) + n$ I'm trying to solve the recurrence for $T(n) = 7T(n/7) + n$.
I know using Master Theorem it's $O(n\log_7n)$, but I want to solve it by substitution method.
At level $i$, I get: $7^i T(n/7^i) + (n+7n+7^2n+ \cdots + 7^i n)$
By setting $i = \log_7n$, the above becomes:
$$7^{\log_7n}\cdot T(1) + (n + 7n + 7^2n + \cdots + 7^{\log_7n}n$$
Since $7^{\log_7n} = n$, the above finally becomes
$$n+ (n+7n+(7^2)n+ \cdots + n\cdot n)$$
This solves to $O(n^2)$ to me since $n\cdot n$ dominates, not $O(n\log_7n)$, any idea what's wrong?

Here is what I get:
\begin{align}
T(n) &= n + 7T(n/7) \\ &= n + 7(n/7) + 7^2 T(n/7^2) \\ &= n + 7(n/7) + 7^2(n/7^2) + 7^3 T(n/7^3)
\end{align}
and so on. Each of the summands equals $n$, and there are $O(\log n)$ of them.


Boolean search explained My mother is taking some online course in order to be a librarian of sorts, in this course they cover boolean searches, so they can search databases efficiently, however, she got a question sounding something like this:

The search "x OR y" will result in 105 000 hits, while a search for only x will result in 80 000 hits, and a search for only y will get 35 000 hits. Why does the search "x OR y" give 105 000 hits, when the combined individual searches gives 115 000 hits?

For me this sounded strange, so I tested this myself, using the words bacon and sandwich.

Only bacon yielded 179 000 000 results
Only sandwich yielded 312 000 000 results
bacon OR sandwich gave 491 000 000 results

But for me it adds up: 179 000 000 (bacon) + 312 000 000 (sandwich) = 491 000 000 (bacon OR sandwich)

Why could an OR query result in fewer hits than both individual queries combined?

The counting principle that applies here is inclusion-exclusion.

$$ \left|X \cup Y\right| = \left|X\right| + \left|Y\right| - \left|X \cap Y \right|$$

To make the numbers work out, $\left|X \cap Y \right|$ must be 10000.

A Venn diagram may be more convincing to someone who may be intimidated by the notation.


What is the Relationship Between Programming Languages, Regular Expressions and Formal Languages I've looked around the net for an answer to this question and it seems as if everybody implicitly knows the answer except me. Presumably this is because the only people who care are those who have had tertiary education on the subject. I, on the other hand, have been thrown in the deep end for a high school assignment.

My question is, how exactly are programming languages related to formal languages? Everywhere I read, something along the lines of "formal languages are used for defining the grammar of programming languages" is said.

Now from what I've been able to gather, a formal language is a series of production rules that apply to a specific set of symbols (the language's alphabet). These production rules define a set of transformations, such as:

b -> a

aaa->c

This can be applied such that:

abab->aaaa aaaa-> ca

Just as a side note, if we define that our formal language's alphabet as {a,b,c}, then a and b are non terminals and c is terminal as it can not be transformed (please correct me if I'm wrong about that).

So given all that, how on earth does this apply to programming languages? Often it is also stated that regex is used to parse a language in it's text form to ensure the grammar is correct. This makes sense. Then it is stated that regex are defined by formal languages. Regex return true or false (in my experience at least) depending on if the finite state automata that represents the regex reaches the goal point. As far as I can see, that has nothing to do with transformations*.

For the compiling of the program itself, I suppose a formal language would be able to transform code into consecutively lower level code, eventually reaching assembly via a complex set of rules, which the hardware could then understand.

So that's things from my confused point of view. There's probably a lot of things fundamentally wrong with what I have said, and that is why I'm asking for help.

*Unless you consider something like (a|b)*b*c->true to be a production rule, in which case the rule requires a finite state automata (ie: regex). This makes no sense as we just said that

Whoever told you that regular expressions are used to parse code was spreading disinformation. Classically (I don't know to what extent this is true in modern compilers), the parsing of code – conversion of code from text to a syntax tree – is composed of two stages:

Lexical analysis: Processes the raw text into chunks such as keywords, numerical constants, strings, identifiers and so on. This is classically implemented using some sort of finite state machine, similar in spirit to a deterministic finite automaton (DFA).
Parser: Run after lexical analysis, and converts the raw text into an annotated syntax tree. The grammar of programming languages is (to first approximation) context-free (actually, one needs an even stricter subset), and this allows certain efficient algorithms to parse the lexified code into a syntax tree. This is similar to the problem of recognizing whether a given string belongs to some context-free grammar, the difference being that we also want the proof in the form of a syntax tree.

Grammars for programming languages are written as context-free grammars, and this representation is used by parser generators to construct fast parsers for them. A simple example would have some non-terminal STATEMENT and then rules of the form STATEMENT$\to$IF-STATEMENT, where IF-STATEMENT$\to$if CONDITION then BLOCK endif, or the like (where BLOCK$\to$STATEMENT|BLOCK;STATEMENT, for example). Usually these grammars are specified in Backus-Naur form (BNF).

The actual specifications of programming languages are not context-free. For example, a variable cannot appear if it hadn't been declared in many languages, and languages with strict typing might not allow you to assign an integer to a string variable. The parser's job is only to convert the raw code into a form which is easier to process.

I should mention that there are other approaches such as recursive descent parsing which doesn't actually generate a parse tree, but processes your code as it parses it. Although it doesn't bother to generate the tree, in all other respects it operates at the same level as described above.


weights in a simple neural network I have seen that in the material made by Andrew Ng about neural networks, he uses the following weights:

so when I replace the final values of h_theta(x) in the formula:

I got values near 0 and 1.

The problem that I have is when I use the values that are in the Tom Mithell book about Machine Learning, he uses the values w0=-0.8, w1=w2=0.5. I have performed the calculations and got the values of h_theta(x) as the following:

0.8,0.3,0.3,-0.2

but when I replace these set of values into the formula of the sigmoid function I got:

0.31,0.42,0.42,0.54

that does not differentiate too much about which values are near 0 and which near 1, something that did not occur with the values that Andrew Ng proposed for the weights. Am I missing something? in this case it would be better to select big values for the weights instead of small ones?

Any help for clarifying this is welcome

It's just that the logistic function reaches its saturated regime around +-4.6, as in the image. So, any absolute values of x much lower than this will give you results around 0.5. Increasing the absolute value of the weights (all of them) you'll get nearer the saturated region, resulting in outputs closer to 0 and 1. Nevertheless, if you use the step function at the output layer instead of the logistic, you'll get the correct values exactly for both sets of weights: 0 0 0 1.


What does 'Describe the language of this automaton' mean? I've been asked to do this as part of an assignment. Here is the automaton:

I understood it as describing in terms of the 5 tuples so I wrote:
The states are as follows:  Q = {A, B, C}
The alphabet is as follows: Σ = {0,1}
The start state is A
The accepting state is C
The transition function is as follows:

Is this what is meant by describing the language or am I supposed to answer using different metrics?

The language of an automaton is the language accepted by the automaton, that is, the set of words accepted by the automaton.
Now, certainly, one way of describing the language is as the language accepted by this particular automaton. But the question is asking you to find a simpler description. Here is the set of words accepted by your automaton:
$$
01, \\
001, 101, \\
0001, 0101, 1001, 1101, \\
00001, 00101, 01001, 01101, 10001, 10101, 11001, 11101, \\
\ldots
$$
Can you spot a pattern?


What is structural complexity theory? I am new to complexity theory and want to know what is structural complexity theory? what are problems theorists try to solve in this field and what is its future?
From the wikipedia:

  The structural complexity theory or simply structural complexity is the study of complexity classes, rather than computational complexity of individual problems and algorithms

I did not get the last line "rather than computational complexity of individual problems and algorithms " I mean in complexity theory we focus on complexity classes not on problems.

Thanks in advance

Structural complexity theory studies the relation between different complexity classes, usually uniform ones. The two most famous open questions in the field are:

Is $\mathsf{P} \neq \mathsf{NP}$?
Is $\mathsf{P} = \mathsf{BPP}$?

In the past, a common pursuit in structural complexity theory was coming up with oracles that separate or join complexity classes. For example, people came up with oracles relative to which $\mathsf{P} = \mathsf{NP}$, and other oracles relative to which $\mathsf{P} \neq \mathsf{NP}$. This type of activity seems less popular now. Diagonalization is another common proof technique that used to be more popular in the past, but is somewhat less popular today.
Another common pursuit is proving conditional results. For example, Buhrman, Chang and Fortnow show that if $\mathsf{coNP} \subseteq \mathsf{NP/1}$ then the polynomial hierarchy collapses. Since it is conjectured that the polynomial hierarchy is strict (doesn't collapse), it follows that probably $\mathsf{coNP} \not\subseteq \mathsf{NP/1}$.
What are some similar results that are not considered structural complexity theory? Here are some examples:

Results in circuit complexity. For example, $\mathsf{AC^0} \neq \mathsf{P}$ is not classical structural complexity theory.

Results about specific problems, for example NP-completeness of specific problems.

Other results could in principle be considered structural complexity theory, but because the techniques used are so different than classical results in structural complexity theory, they are not usually thought of as structural complexity theory. Conspicuous examples include:

$\mathsf{IP} = \mathsf{PSPACE}$, which uses algebraization. This is a borderline example.
The PCP theorem, which uses ideas from coding theory.

The above is just my own opinion. Other people might have very different opinions. Structural complexity theory is not a codified area of research.


Explain the difference between Turing Complete and Turing Equivalence I'm not sure if I understand the difference between Turing Complete and Turing Equivalent programming languages.

A computational system that can compute every Turing-computable
function is called Turing-complete (or Turing-powerful).
A Turing-complete system is called Turing-equivalent if every function
it can compute is also Turing-computable; i.e., it computes precisely
the same class of functions as do Turing machines.

I'm not sure if I understand the difference between these two terminologies properly and what "Turing-computable" means. So for example if I have a programming language $X$, it is Turing complete if it can do any and everything that a Turing Machine can do? And it $X$ ends up being Turing complete and it can be shown that all of the functions that it computes are Turing computable, then $X$ is also Turing equivalent?

A system is Turing-complete if it is at least as powerful as Turing machines.
A system is Turing-equivalent if it is exactly as powerful as Turing machines.
An example of a Turing-complete system which is not Turing equivalent is Turing machines with oracle access to an oracle for the halting problem.
One can come up with one additional definition to complete the picture: a system is effective if it is at most as powerful as Turing machines, that is, if every function computed by the system is computable by a Turing machine.


Get up to speed with algorithms Does anyone have any advice about how I can fast track my understanding of what these types of algorithms mean:

http://en.wikipedia.org/wiki/Monad_(category_theory)

I don't want to have to sit 3 years of maths but is there anything I can do for this to make more sense?

I wouldn't have said they were algorithms per se, more a collection of transformations.

If you want to get a theoretical viewpoint on monads, I'd suggest picking up a category theory textbook. You don't need to do "3 years of maths" to understand one, just some set theory (probably) and some dedication.

On the other hand, if you'd prefer a practical handle, I'd learn the Haskell programming language, which uses monads extensively to represent certain types of side-effects. "Learn You a Haskell" is very good. Try and avoid the infamous "monad tutorials" which inevitably over-simplify in order to produce an analogy. I think just reading the monad typeclass, then looking at examples is probably the best advice.


Describe a Turing machine that accepts a word iff there are twice as many 0's as 1's Can anyone help me describe a Turing machine the language of which is the set of the words that have twice as many 0's as 1's? Assume the alphabet is $\{0,1\}$.

Roughly speaking, the machine could act as follows:

Scan the input, looking for a 1 entry.
If no 1 entry is found, check that there are no 0 entries left, and halt at an accepting or rejecting state accordingly.
If a 1 entry is found, erase it.
Look for a 0 entry. if none is found, halt at a rejecting state. Otherwise, erase it.
Repeat step 4 one more time.
Go back to step 1.

When erasing an entry, you should change it to a symbol different from the blank symbol, so that you will be able in the future to scan through the entire breadth of the work.

If you have multiple tapes, you could try the following algorithm instead:

Scan the input. Whenever you see a 0, copy it to auxiliary tape 0. Whenever you see a 1, copy it to auxiliary tape 1.
As long as there are 1s in auxiliary tape 1: erase a 1, and erase two 0s from auxiliary tape 0; if there are not enough 0s, reject.
Accept iff there are no 0s in auxiliary tape 0.

This is a more efficient variant of the first algorithm.


Time complexity of addition Wikipedia lists the time complexity of addition as $n$, where $n$ is the number of bits.

Is this a rigid theoretical lower bound? Or is this just the complexity of the current fastest known algorithm. I want to know, because the complexity of addition, underscores all other arithmetic operations and all algorithms which use them.

Is it theoretically impossible, to get an addition algorithm that runs in $o(n)$? Or are we bound to linear complexity for addition.

If your algorithm uses asymptotically less than $n$ time, then it does not have enough time to read all the digits of the numbers it is adding. You are to imagine you are handling very large numbers (stored for example in 8MB text files). Of course, addition can be done very quickly compared to the value of the numbers; it runs in $\mathcal{O}(\log(N))$ time, if $N$ is the value of the sum.

This does not mean you can speed things up a little; if your processor handles 32 bits each operation, then you use $\frac{n}{32}$ time, but that is still $\mathcal{O}(n)$ and not $o(n)$.


Distance to $k$th nearest neighbor efficiently for arbitrary $k$ Problem.  Given $X$ a finite metric space of cardinality $n$, construct a data structure in subquadratic time such that the query distance to the kth nearest neighbor of x can be resolved in sublinear time (independent of $k$) for arbitrary $k \leq n$ and $x \in X$.
What I have tried. I am aware of the existence of kdtrees, ball-trees, and cover trees. Under some assumptions (which I'm willing to make), I know that these structures can resolve the query distance to the nearest neighbor of x in sublinear time (often $O(\log(n))$), but I haven't been able to find similar results for the $k$th nearest neighbor for arbitrary $k$.
It seems that, often, one is interested in $k$ values that are small compared to $n$, and that, in those cases, the algorithms mentioned in the previous paragraph can be adapted at the cost of a multiplicative constant of the order of $k$. My problem is that I am interested in $k$ values that are potentially of the order of $n$.

For a general metric, you can't.  For instance, one can prove it takes at least quadratic time to answer $\Theta(n)$ queries, in the worst case.
For instance, suppose we have $n/2$ query points that are all very far from each other, and $n/2$ target points.  We'll ask for the $n/4$-th closest neighbor of each query point.  Then each $d(q,t)$ can be set to any distance in $[1/2,1]$ for each of the $n^2/4$ pairs of a query point $q$ and a target point $t$, and each can be chosen independently, and you'll have a valid metric.  Thus you can imagine the distance being specified by a $n/2 \times n/2$ matrix of distances $d(q,t)$.  In $o(n^2)$ time, you can only read $o(n^2)$ of the entries in that matrix, which isn't sufficient to answer all of the queries.  You can prove this with an adversarial argument: consider any $q$ where the algorithm has read $d(q,t)$ for fewer than $n/4$ different values of $t$; then whatever the algorithm outputs as the $n/4$-th nearest neighbor to $q$, we can arrange the other unread distances so that the algorithm's output was incorrect.


Methods of turning a decision problem into finding the certificate? I usually find this in the context of asking about NP-complete problems, but any decision problem works. We start by assuming there's a polynomial time algorithm that gives the yes or no answer. If it's yes, how can we go from that to finding a polynomial-time algorithm that gives the certificate?

For example, let's say I have a CNF formula. Let's assume we have an algorithm that outputs whether a formula is satisfiable, in polynomial time. I want to know what the actual assignment is. So I'd do a for loop (for i from 1 to n, where n is the number of variables). At each step, I can do one more assignment (assign the i'th variable to be true) and check if the new formula with the i'th value set, is still satisfiable. If yes, continue. Otherwise, assign the i'th variable to be false, and then continue. By saving each of these assignments, at the end I can output a list.

My question is, are there some good methods (in general) of finding the certificate? Perhaps some "token problems" where if you know what to do with one problem of that type, you can do all problems of that type (eg, graph theory, network design, sets/partitions, algebra/number theory, satisfiability)?

The main method is self-reducibility. Suppose that your problem is of the form "there exists an object $x$ such that $P(x)$". Consider some partition of the set of all possible objects $O$, say $O = O_1 \cup \cdots \cup O_m$ (here $m$ should be "small", i.e. polynomial in the size of $x$). If the problem "there exists an object $x \in O_i$ such that $P(x)$" can be reduced to your original problem, then you can use a recursive approach for finding some certificate. The reduction should have the property that a witness for the reduced problem implies a witness for the original problem.

SAT, the example in the question, has exactly this property. In this case, $x$ is a truth assignment, and $P(x)$ states that $x$ satisfies some formula. For each variable $x_i$ we can partition the set $O$ of all truth assignments into $O = O_{i,true} \cup O_{i,false}$ according to the value of $x_i$. The problem "there exists a truth assignment $x \in O_{i,val}$ such that $P(x)$" (where $val$ is either $true$ or $false$) is also a SAT problem. We can use this to figure out a truth assignment satisfying $P$.

A more interesting example is 3-colorability. In this case $x$ is a 3-coloring and $P(x)$ states that $x$ is a valid coloring for the input graph. For any two unconnected vertices $v,w$, we can consider the partition $O = O_{v=w} \cup O_{v\neq w}$, according to whether $x(v) = x(w)$ or not. We can reduce the problem "there exists $x \in O_{v=w}$ such that $P(x)$" into an instance of 3-coloring by merging $v$ and $w$. We can reduce the problem "there exists $x \in O_{v\neq w}$ such that $P(x)$" into an instance of 3-coloring by adding the edge $(v,w)$.


What are the closure properties of LL(k) languages? Suppose I have two LL languages $L_1, L_2$, both describable by LL($k$) grammars for the same $k$, and regular language $R$. Which of the following are also LL languages, and can they be described by LL($k$) grammars?

$L_1 \cup L_2$ (union)
$L_1 \circ L_2$ (concatenation)
$L_1^*$ (Kleene star)
$L_1 \cap R$ (intersection with a regular language)

All of these (except possibly Kleene closure) are answered (in the negative) in Rosenkrantz & Stearns, Properties of Deterministic Top-Down Grammars, 1970.
For an example of a language whose Kleene closure is non-deterministic, see this answer by Hendrik Jan.


What is the difference between computational model, model of computation and a computer? I was browsing the forum where i came by this question, it says that rule 110 from {ECA} is a computation model.
What is the difference between a computation model and model of computation and how can we relate them to computers ?

A model of computation is the definition of the set of allowable operations used in computation and their respective costs.

what does it mean to 'define the allowable operations used in computation'?
Can we say that rule 110 or cellular Automata in general are computers ?

A model of computation is an abstract device used to perform computation.

For example, Turing machines are a model of computation.
They allow operations such as reading a symbol on the tape, writing a symbol on the tape, move left/right...
Minsky machines are another model of computation.
They allow operations such as increment a counter, decrement a counter, test a counter for zero.
Models of computation are used to reason about algorithms, to answer questions like: is problem X realizable with the model of computation Y? If so, how many operations would be needed?

Those models are abstract because they do not describe what the available operations are, not how they are realized.
A computer is a realization, an implementation of an abstract model of computation.
To ease their daily use, and to get efficiency from various technologies, computers have various sets of operations, and it is hard to describe an abstract model of computation for them.
Yet, all the operations they perform can be expressed in terms of e.g. Turing machines or Minsky machines operations.

Note that a Turing machine cannot exist for real: a Turing machine has an unbounded tape, so it would not fit in our Universe.
Similarly, the counters of a Minsky machine are supposed to be able to store arbitrarily high numbers.

From a strict theoretical point of view, since a computer has a finite fixed amount of memory, it is nothing more than a finite state automaton (with a large, yet fixed, number of states).
In practice, a computer is rather considered as a Turing machine, with a tape (memory) large enough not to run out.

To conclude, a computational model is a mathematical description of a complex system, often a physical one.
Computational models are mostly intended for simulation, to be run on real computers.


Formally describing a sensor network language I have a language for sensor networks (generates C code) and I want to define the formal semantics of it.

The language has this form:

{STATE name_state:
EVERY time
SELECT {variable [, variable] ...}
[SENDIF send_condition]
[CHANGEIF change_condition GOTO new_state];
} ...

START IN initial_state;

The initial state of the program is specified by the START IN instruction.
Each state is defined by the STATE instruction.
In the specification of each state the clauses EVERY and SELECT are compulsory and the clauses SENDIF and CHANGEIF are optional.
The CHANGEIF clause is only not specified when there is a single state.

What type of formal semantics is more convenient to use?

Backus-Naur form used to be popular for these purposes. Another possibility is Wirth syntax notation. You can find other possibilities in the "see also" section of the article on Backus-Naur form.


How to graph search a LTL-generated Buchi automaton to generate valid execution paths I have a set of tasks, and a LTL specification that describes which orders of the tasks are legal.  I want to find a way to enumerate all permutations of the tasks that meet the specification.

For example, suppose there are two tasks, A and B, and the LTL spec <>(A&<>B) is.  This spec says that A should eventually be done and after A eventually B should be done.  In this case, there is only one legal sequence: (A,B).

We can convert the LTL formula to a Buchi automaton, as shown above. Then since this example is so trivial, it is easy to see that the only legal sequence is A-->B.

But what if we had a more complex LTL formula?  How could we enumerate all legal sequences (permutations) of the tasks that satisfy the spec?  Is there an efficient algorithm to do this?

I would interpret your problem as follows:

Given a non-deterministic Büchi automaton representing some language $L$, you want to enumerate all shortest good prefixes of $L$ such that in every character of the good prefix, only at most one atomic proposition has a $\mathbf{true}$ value.

A good prefix of $L$ is a finite word such that every infinite extension of it is in $L$. I call a good prefix a shortest good prefix if and only if every prefix of the prefix is not a good prefix.
A schedule is typically finite even though LTL and Büchi automaton "talk" about infinite executions. Hence this interpretation of your problem.

Note that this is actually a difficult problem -- take for example two Buchi automata for the languages []<>p and <>[]!p -- you can take their disjunction by merging the state sets and having two initial states. You do not see syntactically that every word is a good prefix.

The best way to enumerate good prefixes would thus be to construct a deterministic automaton over infinite words, such as a deterministic Rabin automaton, and enumerating all paths to a strongly connected component in which every state represents the universal language.

Enumerating the paths can be done by a simple depth first search, where you do not abort the search after you found a path to a state with the universal language. Whenever you found a path to such a component, you print it out, and return to the next recursive step. Along the way, you ignore characters with more than one proposition set.

Now in practice, you may have a good luck using LTL-to-Buchi converters. They typically do not guarantee that they find all simplifications of the LTL formula, but enumerating paths to accepting states may do the trick. Note that for non-deterministic automata, you can get duplicate schedules.
If you use modern tools for LTL-to-deterministic-automaton translation (such as Rabinizer), they should also make sure that states belowing to a strongly connected component for the universal language are self-looping on all characters, which makes them easy to detect. But I don't think they guarantee this.


Homomorphism erasing information I would be grateful if anyone could help me with the tricky exerciese *7.52 from Sipser's Introduction to the Theory of Computation 3rd ed.

I got stuck in proving that, if P is closed under nonerasing homomorphism (replacing all characters with nonempty string), then P = NP.
With nonerasing homomorphism I cannot delete the characters, but I can get rid off the information by overwriting it e.g. with 0s.

I'm trying to complete the following idea:

Checking whether a given assignment to propositional formula makes it true is in P class.

Let s be the 0-1 string encoding both the formula and particular assignement.
I'm trying to find such nonerasing homomorphism H over 0-1 alphabet that H applied to string s will erease (overwrite with something that
will destroy information) the particular variables assignment but I must be able to read off the formula.

Have anyone the idea how such a homomorphism could look like? (only 2 letter alphabet is allowed).

Denote the closure of a class C of languages under log-space many-one reductions by Closure( under log-space many-one reduction of, C), and the closure of a class C of languages under e-free homomorphisms by
Closure( under e-free homomorphisms of, C). So for example

NP=Closure( under log-space many-one reduction of, NP)
NP=Closure( under e-free homomorphisms of, NP)

We want to show:

  If P=Closure( under e-free homomorphisms of, P) then P=NP.

For this, it is sufficient to show

P=Closure( under log-space many-one reduction of, P)
NP=Closure( under log-space many-one reduction of,
Closure( under e-free homomorphisms of, P))

because if P=Closure( under e-free homomorphisms of, P) then
NP=Closure( under log-space many-one reduction of,
Closure( under e-free homomorphisms of, P))
=Closure( under log-space many-one reduction of, P)=P

It is well known how to show (1). For showing (2), it is sufficient to show

NP=Closure( under log-space many-one reduction of, {SAT})
SAT $\in$ Closure( under e-free homomorphisms of, P)

because if X$\subset$Y then Closure( under ... of, X)$\subset$Closure( under ... of, Y).

It is well known how to show (3), which says that SAT is NP-complete under log-space many-one reductions. For showing (4), note that certificates of length O(n) are sufficient for SAT, where n is the length of the input. So we need to show that e-free homomorphisms can erase a certificate of length O(n) from the input, if the certificate is encoded suitably. This is straightforward in a certain sense, but we have to change the alphabet. The letters of the larger alphabet contain both an original input letter, and an additional certificate letter. To "erase the certificate", the homomorphism replaces this pair of "(original letter, certificate letter)" by the "original letter".

If you want to stay with the 0-1 alphabet, then homomorphisms from the free monoid over 0-1 can't erase information selectively enough, because such a homomorphism is already uniquely determined by the image of 0 and 1. But if you look instead at the submonoid of words whose length is a multiple of some number k, then you can easily find suitable homomorphisms.


What different lines of reasoning and traditions lead to the conclusion that Software Engineering is or isn't part of Computer Science? Background: Some people consider Software Engineering as a branch of Computer Science, while others consider that they are, or should be, separate. The former stance seems to be well presented in written works. On Wikipedia, Software Engineering is classified as Applied Computer Science, along with, e.g., Artificial Intelligence and Cryptography. The ACM Computing Classification system places SE under Software, along with, e.g., Programming Languages and Operating Systems. CSAB has also considered SE as part of Computer Science, and considered that

  [...] it includes theoretical studies, experimental methods, and engineering design all in one discipline. [...] It is this close interaction of the theoretical and design aspects of the field that binds them together into a single discipline.
  [...]
  Clearly, the computer scientist must not only have sufficient training in the computer science areas to be able to accomplish such tasks, but must also have a firm understanding in areas of mathematics and science, as well as a broad education in liberal studies to provide a basis for understanding the societal implications of the work being performed.

While the above seems to reflect my own view, there is also the stance that the term Computer Science should be reserved for what is sometimes called Theoretical Computer Science, such as Computability Theory, Computational Complexity Theory, Algorithms and Data Structures, and that other areas should be split off into their own disciplines. In the introductory courses I took for my CS degree, the core of CS was defined via the questions "what can be automated?" (Computability Theory) and "what can be automated efficiently?" (Computational Complexity Theory). The "how" was then explored at length in the remaining courses, but one could well consider SE being so far from these core questions that it shouldn't be considered part of CS.

Even here on CS.SE, there has been debate about whether SE questions are on-topic, reflecting the problematic relationship between CS and SE.

Question: I'm wondering what lines of reasoning and traditions within Computer Science might lead to one conclusion or the other: that SE is, or should be, part of CS or that it is not. (This implies that answers should present both sides.)

(I did some extensive searching and found material that answers my question. I liked Patrick87's answer, but I found this to be more complete.)

The answer to the question lies in a careful examination of the philosophy of Computer Science. In Computer Science, three intellectual traditions meet (or collide, if you wish) in a single discipline: the theoretical tradition; the empirical tradition; and the engineering tradition.

The theoretical tradition concerns itself with creating hypotheses or theorems, and proving them in a mathematical fashion. Its aim is the construction of coherent axiomatic systems of thought.

The empirical tradition concerns itself with forming hypotheses, models, and predictions, collecting data from experiments, and analysing the results. Its aim is to investigate and explain phenomena.

Finally, the engineering tradition concerns itself with stating requirements and specifications, and with designing, implementing, and testing systems based on these requirements and specifications. Its aim is to construct systems and solve concrete instances of problems.

Each of these traditions comes with a set of assumptions about the aims and means of scientific inquiry.

The traditions are not unique to Computer Science; they are general traditions that can be found to differing degrees in other disciplines. Perhaps the clearest examples are mathematics (theoretical tradition), physics (empirical tradition), and construction engineering (engineering tradition). Computer Science, though, operates in the intersection of all three traditions. However, depending on one's particular focus within Computer Science, and one's familiary with other parts of Computer Science, one might emphasize one of these traditions to the degree that the other two appear alien.

As noted in Patrick87's answer, the educational setting can emphasize a certain intellectual tradition which may lead someone to a certain kind of demarcation of Computer Science which either includes or does not include Software Engineering. Similarly, one may later adopt a view of science that includes or excludes one or more of the three traditions, or parts of them. For example, one may consider only the theoretical and empirical traditions to fulfil one's criteria for "science", and consider engineering non-scientific. One may also consider the three traditions to be on a value continuum, with one tradition being superior to the others (e.g. valuing the theoretical tradition most, the empirical tradition less, and the engineering tradition least).

So the lines of reasoning are rooted in the abovementioned traditions. Based on this, the answer to the question is that considering Software Engineering as part or not as part of Computer Science stems from one's understanding of science in general, and of one's understanding of the philosophy of Computer Science in particular.

The following articles go into considerable depth on this issue and summarise a lot of the viewpoints that have been put forward.

  Tedre, Matti (2011) Computing as a Science: A Survey of Competing Viewpoints. Minds & Machines 21(3):pp.361-387.

  Tedre, Matti (2009) Computing as Engineering. Journal of Universal Computer Science 15(8):pp.1642-1658

  Tedre, Matti (2007) Know Your Discipline: Teaching the Philosophy of Computer Science. Journal of Information Technology Education 6(1):pp.105-122.


The definition of weakest precondition for a non-deterministic language In the classical IMP language, the definition of weakest precondition is:

definition "wp c Q s ≡ ∃t. (c,s) ⇒ t ∧ Q t"

This is stating that from state s, after executing c we get to a state satisfying Q. My question comes when handling the IF FI construct in the language of guarded commands (see selection command in Wikipedia). My guess is that in this case one needs to define:

definition "wp c Q s ≡ ∃t. (c,s) ⇒ t ∧ (∀ t'. (c,s) ⇒ t' ⟶ Q t')"

I wonder if this is correct and whether it is the standard way of writing it in the literature.

Currently, I'm having problems proving the weakest precondition definition for the sequential composition of commands:

"wp (c1;;c2) Q s = wp c1 (wp c2 Q) s"

So, I'm beginning to think my definition is wrong. Quoting wikipedia:

  the result of this function, denoted wp(S,R), is the "weakest"
  precondition on the initial state ensuring that execution of S
  terminates in a final state satisfying R.

so termination is required in the definition, and this is not properly imposed so far. There could be non-terminating branches.

First of all, the definition of weakest precondition you've mentioned might be a little bit confusing. Namely, remember that the weakest precondition, designates all states of a program, such that when the given command executes, the given postcondition is satisfied.

Therefore, your initial definition might be a bit confusing, in the sense that the weakest precondition wp(s, Q) is determined really based on a postcondition (which you have as Q) and a command (which you have a c) -- that is all that is needed to define weakest precondition (w.p.).

Having that said, a more natural definition of wp(c, Q) says that:
$$
wp(c, Q) = \{ \sigma \in \Sigma | \text{ex}[c, \sigma]  \models Q \}
$$
the weakest precondition, given c and Q, is a set of all states, such that executing c (denoted simply by ex here) from those states, assuming the execution terminates (we will come back to that later), will lead to some state $\sigma$ for which the postcondition Q is satisfied.

Given that, the weakest precondition you've mentioned, namely

  "wp (c1;;c2) Q s = wp c1 (wp c2 Q) s"

is a valid formulation for w.p. for compositions, as, naturally, executing c1 you want to end up in a state belonging to the weakest precondition of wp(c2, q), which, in turn, means that after further executing c2 (in the sequence) you will have to satisfy postcondition (again, with the assumption that both terminate).

Now, in terms of this weakest precondition formulation, while the quote

  ensuring that execution of S terminates in a final state satisfying R

might confuse you, this does not say that termination is encoded in the w.p. formulation. Specifically, it is not required: the definition of weakest precondition says, that, if the given command executes and terminates, from those states, the postcondition has to hold.

That is why this is part of something traditionally called "partial correctness" and not "total correctness", as it does not prescribe termination (but rather, effectively, works under assumption of termination).


What is a "closed set" in context of AI? How is it different from an open set or a frontier? I am reading some properties on the A* search algorithm on Wikipedia, specifically:

"If the heuristic function h is admissible, meaning that it never overestimates the actual minimal cost of reaching the goal, then A* is itself admissible (or optimal) if we do not use a closed set. If a closed set is used, then h must also be monotonic (or consistent) for A* to be optimal."

But I am not sure I understand what a "closed set" refers to. Is it different than an open set / frontier? If so, why? And why do we use a "closed set" as opposed to an "open set" for A*? Is a priority queue a closed set?

There are two variants of the A* algorithm:

The standard algorithm maintains two sets of vertices.  One called the "open set", and the other is called the "closed set".
An alternative version maintains just an open set, and doesn't use a closed set.  This requires that the heuristic function satisfy some some additional conditions.

See any standard treatment of A* for explanation of how it works and what the closed set is; e.g., A* search.


What is the proof that boolean circuit (no negation gate) can be arranged as alternating OR and AND gates In circuit complexity theory, a branch of computation complexity theory, a theorem is that any Boolean circuit without NOT gates can be written equivalently as a hierarchical structure, in which the first layer consists of OR (or AND) gates, then the second layer consists of AND (or OR) gates, the third layer consists of OR(AND) gates, and so on, what is the proof of this conclusion? Or any reference? I remember the proof that the PARITY problem needs exponential circuit complexity used this fact when using Håstad switching Lemma. Thanks!

Note: we don't need CNF(or DNF) here, because that corresponds to 2 layers and exponential number of gates. In general, the circuit above can be arranged as multiple layers, so CNF(DNF) is not necessary.

Let $r$ be the root of your circuit (without loss of generality, an OR gate), and let $V_i$ consist of those gates at distance $i$ from $r$. Assign (in your mind) a layer for each gate: layer 0 for the root, layer $2i-1$ for an AND gate in $V_i$, and layer $2i$ for an OR gate in $V_i$. The result is almost what you want – the only difference is that edges could span more than one layer.

In order to fix the problem, for each gate $g$, create gates in all layers above it (i.e., with smaller number) of the correct type, and connect them in a path (so all the new gates will have in-degree 1). Now you can arrange that each edge span exactly one layer.

Starting with a circuit of depth $D$ and $n$ gates, we have created a circuit of depth $2D$ and at most $nD$ gates. In particular, if the original circuit had polynomial size then so does the new one (with a different polynomial), and if the original circuit had constant depth (or logarithmic, or polylogarithmic) then so does the new one.


What is the job of Syntax Analyzer in a compiler? What exactly is the job of a syntax analyzer? Suppose I have a mathematical expression. Is it true that the order of execution of the operations is found with the help of syntax analyzer?

Any example on exact jobs of Syntax Analyzer?

The syntax analyser has two main purposes.

It checks if the program to be compiled is syntactically correct.
It converts the program, which is given as a string of characters,
into an abstract syntax tree, which is a representation of the
program that is much easier to use for the code generator.

The second part is not really necessary as one could, in principle,
generate code directly from the input string, but that would be painful,
both in terms of speed of compilation, and complexity of the code generator.


How to determine if this problem is decidable? I am currently stuck on the following problem:

Given a WHILE-program P and the knowledge that all input variales are set to 0, is it decidable if a specific instruction is reached 1000 times?

My intuition is that it is not decidable. Rice's theorem says that a non-trivial property of a program is always undicidable. But I am not sure if "a specific instruction is reached x times" even qualifies as a "property of a program".

I am stuck on this for a while now, so I hope someone can give a hint where to look to find an answer to this problem. Thank you so much! All help is greatly apprechiated.

As Konstantin Vladimirov said in the comment: Consider you have this program. Take any while-program and put any instruction 1000 times just before halt. Next run your program and ask if this instruction will be reached 1000 times. Bingo, halting is solved.


predication execution, branch prediction Below is a paragraph from a book.

  In an ordinary superscalar processor, we would use branch prediction to guess which of the given instructions is to be executed, and go down that path. If the processor guesses wrong, the pipeline must be flushed.

  Predication execute all of instructions and once the values of the predicate registers are known, commit only the results of the valid instructions. Thus we make use of additional parallel execution units to avoid the delays due to pipeline flushing.

So each predication and branch prediction has disadvantage each.
For predication, we have to WAIT until the values of the predicate registers are known.
For branch prediction, if prediction is wrong, the pipeline must be flushed which will cause a DELAY.
Seems like both predication and branch prediction needs delay..
But to me.. prediction has a chance to avoid delays when prediction is correct leading to conclusion that prediction is better..Predication always needs waiting.

So how do I tell which one is better??
Under what circumstance should I use predication and branch prediction?

Thank you in advance.

The quote from the book doesn't describe how predicated instructions work today. It says that predicated instructions are "executed but only committed if the condition is true". But that would be exactly what branch prediction does, and would lead to exactly the same problems.

Instead, a predicated instruction is implemented as an ordinary instruction which just has one more input. It is always executed and always committed, just the effect of the instruction depends on a condition flag. That means all the mechanism to accelerate execution, out of order execution etc. can be used.


Independent set where two vertices need to have distance >= c An independent set (IS) in a graph is a set $V' \subseteq V(G)$ of pairwise non-adjacent vertices.

I am interested in the generalization $c$-IS where two nodes in  $V' \subseteq V(G)$ need to have distance at least $c$ to any other vertex in $V'$.

Has this problem been studied before?

Yes, this is called ruling set.
An $(\alpha,\beta)$-ruling set is a set $S$ such that any two nodes in $S$ are at distance at least $\alpha$ from each other, and, for any node $v \notin S$, there exists a node $u \in S$ such that the distance between $u$ and $v$ is at most $\beta$. So a maximal independent set is a $(2,1)$-ruling set. (This is defined in [1] but there might be prior references.)

[1] Korman et al. Toward more localized local algorithms: removing assumptions concerning global knowledge. PODC '11 Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing
Pages 49-58


Does precedence matter in constructing parse trees of arithmetic expressions for postfix notation? Table 4 in Problem Solving with Algorithms and Data Structures's
 chapter on Infix, Prefix and Postfix Expressions gives the following examples:

Infix Expression: A + B * C + D
Prefix Expression: + + A * B C D
Postfix Expression: A B C * + D +

Why is prefix not:

+ A + * B C D

To show my reason for this question, I'll use lowercase characters combined to represent a completed operation (e.g. + A B becomes ab). Here's my thinking:

+ A + * B C D
+ A + bc D
+ A bcd
abcd

Here's my thinking applied to the answer supplied by the text:

+ + A * B C D
+ + A bc D
+ abc D
abcd

They both work?

I'm making the same mistake with

Infix Expression: A + B + C + D
Prefix Expression: + + + A B C D
Postfix Expression: A B + C + D +

I write postfix as:

A B C D + + +

...which is wrong (but I don't know why).

What you're missing is the associativity of operators. All operators you mention in your examples are binary. An expression of the form $A + B + C + D$ is interpreted by the parser as $(((A+B)+C)+D)$. When converting such a fully parenthesized expression into prefix form, we apply the rule $(\alpha + \beta) \to +\alpha\beta$. Denote this transformation by $T$. Then
$$
T[(((A+B)+C)+D)] = +T[((A+B)+C)]D = ++T[(A+B)]CD = +++ABCD.
$$
In a completely analogous way, the operator $S$ converting into postfix makes the transformation $S[(\alpha+\beta)] = \alpha\beta+$:
$$
S[(((A+B)+C)+D)] = S[((A+B)+C)]D+ = S[(A+B)]C+D+ = AB+C+D+.
$$

The operator $+$ is associative, but imagine what happens with an operator like $-$. The expression $A-B-C$ is interpreted as $((A-B)-C)$, and its prefix and postfix forms are $--ABC$ and $AB-C-$, respectively. Any other conversion would result in an arithmetically inequivalent expression. That's why associativity matters.

Most operators associate to the left, just like $+$. Exponentiation traditionally associates to the right.

On top of this, we also have operator precedence, which leads to the parsing of $A+B*C+D$ as $((A+(B*C))+D)$. If you apply the transformations $T$ and $S$ you will get the expressions given in the book.