Interpolation on marching cubes algorithm I'm currently learning how isosurfaces are extrated from volumetric data. I already understood the original marching cubes algorithm which is based on 3D-voxel data which stores only values of either 1 or 0. For learning purposes I implemented the easier version of it for 2D-volumetric data called marching squares algorithm. Results are shown below:

After all I read that the marching cubes algorithm can benefit of float values in the voxels instead of the binary values in terms of interpolating the vertices. However I do not understand how this should work simply because I'm missing the rules of which values should only be assumed for the voxels and also how the interpolation based on them would be done.

Could someone give me a fundamental view of how interpolation with the marching cubes algorithm is asumed to work? An example with 2D would be fine but showing how it works in 3D would be even nicer.

PS:
For references, I read such stuff here.

I worked it out on my own. I'm trying to write it down correctly so it's readable for newcomers.

Introduction

First of all, interpolation itself requires that there are float values and not binary values. This gives the ability to create different edge-crossing-vertices. How it's going I'm explaining now.

The interpolation which is needed here is linear interpolation.
For understanding purposes I'll explain it here too.

General Interpolation

After all, what is interpolation? Well good question.
Interpolation is described as name for algorithms which smooth a given input of data e.g. points (with n-dimensions). Simpler there are points searched between the points for a given interpolation value. First it's required to give the points a base so that's clear where points are searched for in between. After that a specific algorithm for the interpolation has to be chosen. There are different kinds of interpolation algorithm out there each for a specific application.
Best known is linear interpolation which results for a value one point on a line which crosses two input points.

The formula for linear interpolation (2D here) is as following (simply maths):
$$
y = y_{0} + (value - x_{0} ) * \frac{y_{1} - y_{0} }{x_{1} - x_{0}}
$$
with $$ value \in   \mathbb{R} \wedge 0 <= value <= 1 $$

After all with this formula it's possible to apply interpolation on the vertices of the marching cubes algorithm which requires following rules.

The voxels must have a floating value instead of a binary value.
The value of the voxels must be only between zero and one
There must be a boundary value be declared which describes whether a voxel is supposed to be in surface.

Looking back to the blog the boundary value is called the iso surface value.
This value describes as explained whether a voxel is being asumed to be in the surface so for acquiring the edge crossing. This is important to know because without it you wouldn't find out where even a edge-crossing computation is needed.

The interpolation is done on each coordinate of the two voxels position where and crossing-edge vertex is.
The implementation is quite easy and looks like this (extracted from here):

/*
   Linearly interpolate the position where an isosurface cuts
   an edge between two vertices, each with their own scalar value
*/
XYZ VertexInterp(isolevel,p1,p2,valp1,valp2)
double isolevel;
XYZ p1,p2;
double valp1,valp2;
{
   double mu;
   XYZ p;

   if (ABS(isolevel-valp1) < 0.00001)
      return(p1);
   if (ABS(isolevel-valp2) < 0.00001)
      return(p2);
   if (ABS(valp1-valp2) < 0.00001)
      return(p1);
   mu = (isolevel - valp1) / (valp2 - valp1);
   p.x = p1.x + mu * (p2.x - p1.x);
   p.y = p1.y + mu * (p2.y - p1.y);
   p.z = p1.z + mu * (p2.z - p1.z);

   return(p);
}

Conclusion

The interpolation of the edge-crossing vertices is a nice feature for smoothing the presentation of voxels.However the interpolation relies on that there are already floating values which means that it cannot smooth your existing binary data. For such cases different algorithms and approaches are needed.


Time complexity of a greedy approach for Independent Set: the Heaviest-First Algorithm The heaviest-first algorithm is a greedy approximation algorithm that finds an independent set $S$ of nodes in a graph $G=(V,E)$, so that the sum of the weights of the nodes in $S$ is as large as possible.

My question is that I want to find the time complexity of the following algorithm (when applied on $N \times N$ grid graphs):

The running time of adding a vertex to the independent set $S$ is $O(1)$ if you use an appropriate set data structure, such as a linked list, an array, or a dictionary. Also, deleting a vertex $v$ from $G$ (once you have identified the vertex) takes time proportional to the number of neighbours, which, in this case, is bounded above by a constant ($4$), so it also takes $O(1)$ time.

The running time of your greedy algorithm will, therefore, be dominated by the costs of the maximum-weight vertex computations. I can think of three ways to implement this operation:

Naive approach - $O(|V|)$: identifying the maximum-weight vertex of a graph takes linear time in the number of vertices if you explore all of them.
Priority queue - $O(log \: |V|)$ : since you are doing repeated maximum computations, it makes sense to use a priority queue, which allows you to extract the maximum element in logarithmic time.
Sorted array - $O(1)$ : the maximum-weight vertex of a graph can be identified in constant time if you sort the vertices by weight beforehand.

The number of times that the algorithm computes the maximum-weight vertex is equal to the number of iterations, which is $O(|V|)$. Therefore, the naive approach takes $O(|V|^2)$ time and the priority queue based solution takes $O(|V| \: log \: |V|)$ time. In the sorting-based solution, each iteration takes $O(1)$ time; however, the overall running time is not $O(|V|)$, but, rather, $O(|V| \: log \: |V|)$ because the running time is dominated by the sorting operation.


Minimum Spanning Tree with diameter 3 I need an $O(|V||E|)$ algorithm to detect if a graph has a minimum spanning tree with diameter 3.
This paper mentions that it is possible for any diameter by finding the vertex 1-center which can be done using Floyd's algorithm, but I need something much simpler only for the case of diameter 3.

Perhaps the following helps:

If a tree has diameter 3 then either it is a single vertex, or there are two neighboring vertices $x,y$ such that every other vertex is a neighbor of either $x$ or $y$.

To see why this is true, consider a tree of diameter 3 with more than one vertex. If all vertices have degree 1, then the tree is of that form. Otherwise, let $x$ be a vertex of degree at least 2. If all neighbors of $x$ have degree 1, then you can designate one of them as $y$ and get the above structure. If $x$ has two different neighbors $y,z$ of degree at least 2 then the diameter is at least 4 (a neighbor $y' \neq x$ of $y$ is at distance 4 form a neighbor $z' \neq x$ of $z$), which is impossible. Therefore $x$ has a single neighbor $y$ of degree at least 2. Every vertex is thus either a neighbor of $x$ or a neighbor of $y$.


Difference in having * inside vs outside of brackets for NFA If you have a question saying "draw the NFA for the following language" what difference does it makes if the language is $(0^* \cup1^*)$ vs $(0 \cup1)^*$ in otherwords what difference does it make for the diagram if the star is on the inside or outside of the brackets?

Let "$\rightarrow$" stand for "denotes". Then we have

$0\cup 1\rightarrow \{0, 1\}$, so
$(0\cup 1)^*\rightarrow \{\epsilon, 0, 1, 00, 01, 10, 11, 000,\dotsc\}$, i.e., all words that can be made by concatenating any number of $0$s and $1$s.
$0^*\rightarrow \{\epsilon, 0, 00, 000, 0000, \dotsc\}$, all words that can be made of just $0$s.
$1^*\rightarrow \{\epsilon, 1, 11, 111, 1111, \dotsc\}$, all words that can be made of just $1$s, so
$(0^*\cup 1^*)$, the union of the two sets above
$\rightarrow \{\epsilon, 0, 1, 00, 11, 000, 111, 0000, 1111, \dotsc\}$.

So in particular $(0^*\cup 1^*)$ will never contain strings with both $0$s and $1$s, whereas $(0\cup1)^*$ will contain all of $(0^*\cup1^*)$ along with lots of other words.


Solving the emptiness problem for a CFG in Chomsky normal form (linear) Given a CFG in Chomsky normal form, is there an algorithm that solves the emptiness problem in linear runtime? I thought about using depth search here, but I think it's a little bit above linear runtime.

Yup, it can be done.  For each nonterminal $A$, introduce a boolean variable $x_A$, with the intent that if $x_A$ is true, that means $L(A)$ is non-empty.  Then you can convert each production into a corresponding Horn clause:

$A \to BC$ becomes $(x_B \land x_C) \implies x_A$
$A \to a$ becomes $x_A$
$S \to \varepsilon$ becomes $x_S$

Let $\varphi$ denote the conjunction of these Horn clauses.  Find the minimal satisfying assignment for $\varphi$; that can be done in linear time.  If this assignment makes $x_S$ true, then the language is non-empty, otherwise it is empty.

Alternatively, if you prefer a more direct algorithm, here is a standard one that you might see in textbooks.

Start out with all nonterminals unmarked. If you see a rule $A \to a$, mark $A$.  If you see a rule $S \to \varepsilon$, mark $S$.  Whenever you mark a nonterminal, check all rules of the form $A \to BC$ where it appears on the right-hand side; if both $B$ and $C$ are marked, mark $A$.  Repeat until convergence.  At that point, all marked nonterminals correspond to nonterminals that generate a non-empty language, so the language is non-empty iff $S$ is marked.

This also runs in linear time.  It takes a little more work to see why, but it's true.  In particular, each nonterminal can only be marked once, and each rule of the form $A \to BC$ will only be checked at most twice (once when $B$ is marked, once when $C$ is marked), so the amount of work you do is $O(1)$ per nonterminal plus $O(1)$ per rule, which is linear in the size of the grammar.  It does require suitable data structures that map from each nonterminal to a list of all rules containing it on the right-hand side, but that can be built in advance in linear time as well.


An ID (auto increment integer) always as primary key for each db-table? Till now, I always gave each db-table an id-column (generally with the table name and an underscore as a prefix, e.g. employee_id), and I also never have seen another approach to unique a db-table-record in practice. But on the other hand during my studies, I often have seen other columns that act as a primary key, for instance: an email/url as priamary key for a table user/photo.

At the moment I'm designing a database that contains a table first_name (because a human can have more than one first name).
The scheme of this table first_name:{[first_name_id:integer,first_name:string]}.
But to avoid duplicate, I would like to use the first_name as a primary key. And I also have a table employee with the column email address that also can be used as a primary key, becuase its unique.

My loss is that I dont know if I should use this approach, becuase its uncommon in practice and maybe it will cause any trouble during the programming part. So my questions is:
An ID (auto increment integer) always as primary key for each db-table?

I assume you are using RDBS.As far as you can set any value as primary key this will not cause strict programming trouble - but will be cumbersome.

What about convention that people use integer?
This comes from two parts:
It is easier to give unique id from autoincremented value.
Second is from relations and optimizations - database internally connects related items, so setting something different will cause overhead.

You should read two pages:
normal forms in database and primary keys.

Normal form is something you should have (at least third level) in your database, it saves programming trouble later like with splitting keys manually.


Dynamic Programming Recursive Algorithm - Number of heads in a series So I have this programming prompt which asks me to figure out how many permutations of a 32 coin toss sequence do not have three or more heads consecutively tossed. We are supposed to use Dynamic Programming to do this and I'm having a hell of a time identifying the recursive algorithm for this.

My first thought was a bottom up approach where I start from a singular toss and then increment a variable whenever I find a sequence that has three heads in a row and then subtract that number from the total number of possible permutations to get the answer but I'm having trouble implementing the logic behind that.

I see that instead of thinking increasingly large sequences, it would be better to think of each individual toss in the sequence. Mostly what I'm having trouble with is how I should be keeping track of all this.

For example, the first toss is a H, that affects the rest of the sequence because I can't have 2 more H's consecutively, but if the first toss is a T, that doesn't affect the rest of the sequence. So, do I wait till the third toss to tell if I increment? Do I discard the first toss if it's a T? I'm having quite a bit of trouble visualizing and comprehending this problem.

Method 1: DFA. Construct a DFA that accepts the language of valid coin tosses (of any length). Let $A$ be a $Q \times Q$ matrix (where $Q$ is a set of states) such that $A(j,i)$ is the number of symbols that cause the DFA to transition from state $i$ to state $j$. The number of coin tosses that you're after is $1_F A^{32} 1_{\{q_0\}}$, where $q_0$ is the initial state, $F$ is the set of final states, and $1_S$ is the characteristic vector of $S \subseteq Q$.

This method actually works with more general automaton models. For example, you can have a DFA in which some transitions are "missing": when at state $i$, upon reading a symbol $\sigma$ you might just get stuck. More generally, UFAs would work.

Method 2: Recurrence relation. This is a reformulation of the DFA approach without mentioning DFAs. Let $A(n,i)$ be the number of binary words $w$ of length $n$ such that $wH^i \notin L$ but (if $i \neq 0$) $wH^{i-1} \in L$, where $L$ consists of all strings with no three consecutive heads. You're after $B(n) = A(n,1) + A(n,2) + A(n,3)$. These sequences are given by the following recurrence:

$A(0,1) = A(0,2) = 0$, $A(0,3) = 1$.
$A(n+1,1) = A(n,2)$.
$A(n+1,2) = A(n,3)$.
$A(n+1,3) = A(n,1) + A(n,2) + A(n,3)$.

I'll let you figure out where these recurrences come from.

We can also come up with a direct recurrence for $B$:

$B(0) = 1$, $B(1) = 2$, $B(2) = 4$.
$B(n+3) = B(n+2) + B(n+1) + B(n)$.

You can prove this recurrence from the preceding ones for $A(n,i)$, and also directly.

Standard methods show that $B(n) \sim C \alpha^n$, where $\alpha \approx 1.839$ and $C \approx 1.137$. In fact, $B(n)$ can be calculated as the integer closest to $C \alpha^n$ for $n$ larger than some constant.


How to write operational semantics rule for havoc x? If I want to extend a new language by adding a new command havoc x, which
updates the variable x with a non-deterministic value, how to write operational semantics rule for havoc x?
I'm confused about generate a non-deterministic value.
If I write like this:
$$\frac{n = [e]_ {intexp}\sigma}{(\mathrm{havoc}\ x,\sigma)\rightarrow(x:=x+n,\sigma)}$$
is it make sense?

I'm going to assume that all the allowed values for $x$ are (unbounded) integers.

In that case your proposal somewhat makes sense, insomuch as $e$ is some arbitrary well-formed expression (which evaluates to some value in the context $\sigma$). But it's just as easy to write this

$$\frac{n\in\mathbb{Z}}{(\mathrm{havoc}\ x,\sigma)\rightarrow (x:=n,\sigma)} $$

You see that in both cases the result of the evaluation by this rule can non-deterministically give any value in $\mathbb{Z}$ to $x$. In this sense, you have a family of rules, one for each $n\in\mathbb{Z}$.


O(n) time algorithm for maximum earnings There are $n$ plates $p_1$ to $p_n$ each filled with money of value $a_1$ to $a_n$. You can take the money from one or more plates if the sum of the money in them is divisible by three. I need a $\mathcal{O} (n)$ asymptotic time logarithm for finding the maximum earnings that can be achieved. I have no idea for such a fast algorithm, so any help is welcomed.

You can use DP for solving this problem.

Let's iterate $i$ from $1$ to $n$ and calculate next values for each $i$:

$m_{i,0}$ - biggest sum of money from plates $j \le i$ which is divisible by 3
$m_{i,1}$ - biggest sum of money from plates $j \le i$ which have reminder 1 after division by 3
$m_{i,2}$ - biggest sum of money from plates $j \le i$ which have reminder 2 after division by 3

Base case:
$m_{0,0} = 0, m_{0,1} = -\infty, m_{0,2} = -\infty$

Iteration:

$k \in [0, 1, 2]: m_{i, k} = m_{i-1, k}$
$k \in [0, 1, 2], m_{i-1,k} \ne -\infty: m_{i, (m_{i-1,k} + a_i)\%3} = max(m_{i, (m_{i-1,k} + a_i)\%3}, m_{i-1,k} + a_i)$

And result will be $m_{n,0}$.


Given regular grammars (each is either left or right linear), does exist word/string so it can be derived from all regular grammars? Given regular grammars (each is either left or right linear), does exist word/string so it can be derived from all regular grammars, i.e. a word/string that can be derived from each regular grammar.

Suppose that S1, ... , Sn are regular grammars. Then is the following statement is true:

∃w: S1→w ∧ ... ∧ Sn→w ?

In other words:

∃w∀i: 1≤i≤n→(Si→w) ?

Does exist polynomial algorithm (both in time and space) that can find the answer to this question quickly?

EDIT: The language of each given regular grammar is finite and 'w' is a word of length m, where m is natural number given as input to the algorithm.

Also the alphabet of each regular grammar is Σ={0,1} and thus |Σ|=2.

In other words, does exist word of length m that can be derived from each regular grammar, where the language of each regular grammar is finite and alphabet of each regular grammar is {0,1}?

Your problem is PSPACE-complete. Indeed, the easier problem of DFA intersection is already PSPACE-complete, see for example Descriptional and computational complexity of finite automata—A survey by Holzer and Kutrib. For comparable results from the point of view of exponential time algorithms, see Problems on Finite automata and the exponential time hypothesis by Fernau and Krebs.

It is well-known that regular grammars are essentially equivalent in power to NFAs (even considering description complexity), and for this reason your problem is essentially equivalent to the NFA intersection problem, in which you are given a collection of NFAs and have to decide whether the intersection of languages accepted by them is empty — this is the problem considered in the papers above.

The same problem for regular expressions is also PSPACE-complete, see for example Complexity of decision problems for simple
regular expressions by Martens, Neven and Schwentick, which considers restricted cases of the problem.


Derive a Context Free Grammar from a language I am having challenges (in two phases) with creating a CFG.

Derive the CFG for the following language
Show parse trees for the strings cacab and aacabbb obtained from the grammar designed above.

I am getting a bit mixed up by the exercise especially because my CFG appears not to produce a parse tree.

Here is the language:

$$
    L = \{a^n (ca)^m b^{n+1} \mid m \ge 0 , n \ge 0 \}
$$

So far my grammar looks as follows:

$$ \begin{align}
    S &\to Ab \mid Bb \mid Cb \mid b \\
    A &\to aA \mid \epsilon \\
    B &\to caB \mid \epsilon \\
    C &\to bC \mid \epsilon \\
\end{align} $$

You're on the right track: $A$ recognizes $a^*$ (i.e. $\{a^n \mid n \ge 0\}$), $B$ recognizes $(ca)^*$ and $C$ recognizes $b^*$.

You need to assemble them correctly. $Ab | Bb | Cb | b$ recognizes words that are made of something recognized by $A$ followed by $b$, or of something recognized by $B$ followed by $b$, etc. A word in $L$ consists of a part that's recognized by $A$ followed by a part that's recognized by $B$, etc. So the pieces need to be concatenated together: $S_1 \to ABCb$.

$S_1$ recognizes $\{a^n (ca)^m b^{p+1} \mid m,n,p \ge 0\}$. This is too much: $L$ consists only of the words for which $n = p$ in this decomposition. Instead of defining $A$ and $C$ separately, you need to relate them. Whenever you put an $a$ on the left of the $B$ part, put a $b$ on the right.
$$ \begin{align}
  S_2 &\to B \\
  S_2 &\to a S_2 b \\
\end{align} $$
This constraints the number of $a$'s on the left to be equal to the number of $b$'s on the right. The words in $L$ actually have one more $b$ on the right. One way to add that $b$ is to append it at the end:
$$ S \to S_2 b $$
Another approach is to tack on the $b$ to the end of the $B$ part. $S$ and $S'$ recognize the same language, with slightly different parse trees.
$$ \begin{align}
  S' &\to B b \\
  S' &\to a S' b \\
\end{align} $$

To construct the parse trees, work out where each rule is applied to recognize the sample words.


How to build a finite automaton for right quotient of a regular language? Let $L$ be a regular language over $\Sigma=\{a,b,c\}$. Build a finite automaton for $L/\{a\}$.

Because $L$ is regular then a DFA exists for it: $A=(\Sigma, Q, q_0, F, \delta)$.

Let $M$ be a finite automaton, $L(M)=L/\{a\}$.

$M=(\Sigma, Q\times\{0,1\}, (q_0,0), \delta', F\times\{1\})$ with the transition function defined below for all $q\in Q, \sigma \in \Sigma$:
$$
\delta'((q,0),\sigma)=(\delta(q,\sigma),0)\\
\delta'((q,0),\epsilon)=(\delta(q,a),1)
$$

The reasoning is that in state $0$ we just read letters in $M$ because those exact letters also exist in $L$. But when we reach end of input in $M$ via $\epsilon$ we still need to read $a$ in $L$. I'm not sure if it's valid to assume that $\epsilon$ means end of input?

First of all, note that you are constructing an NFA, and so $\delta'$ should output a set of possible transitions.

You can prove by induction the following identities:
$$
\begin{align*}
\delta'((q,0),w) &= \{ (\delta(q,w),0), (\delta(q,wa),1)\}, \\
\delta'((q,1),w) &= \begin{cases} \{(q,1)\} & w = \epsilon, \\ \emptyset & w \neq \epsilon. \end{cases}
\end{align*}
$$
In particular, $\delta'((q_0,0),w)$ intersects $F \times \{1\}$ iff $\delta(q_0,wa) \in F$. In other words, $w$ is accepted by your NFA iff $wa \in L$, so your automaton is computing $L/a$.

You can simplify your construction by taking the original DFA and simply modifying the set of accepting states, replacing $F$ with
$$
F' = \{ q : \delta(q,a) \in F \}.
$$
The new automaton accepts a word $w$ iff $\delta(q_0,w) \in F'$ iff $\delta(q_0,wa) = \delta(\delta(q_0,w),a) \in F$ iff $wa \in L$.


Implementing regular expression matching using Brzozowski derivatives I have been taking a language theory class, and we learned about Brzozowski derivatives recently. At class it occurred to me that they could be used to implement a simple regular expression matcher. If you take the derivative of a regular expression with respect to a given string and the resulting expression matches the empty string ($\varepsilon$), then the original expression matches the string used in the derivative:

$$
w \text{ matches } e  \Leftrightarrow \varepsilon \text{ matches } D_w(e)
$$

I did a web search and, as expected, other people had the same idea before. There is an implementation here and another one here. They are short and simple.

Is this used in practice anywhere? I'm not sure, but I believe that most regular expression matchers are implemented using either finite automata or  backtracking algorithms (like Perl regular expressions). Why is this the case? Is the technique I mentioned too slow? Is it missing functionalities? Does anybody know what the complexity of regular expression matching using derivatives is?

Yes.  This approach has been used before.  I've seen it used in a research project, where the goal was to build a regexp matcher that could be formally verified to be correct (with as little effort as possible).  This algorithm was implemented in Coq and then proven correct.  The nice thing is that it is relatively easy to prove correct.  In contrast, a table-driven lexer would be harder to prove correct, because one would have to prove that the table was constructed correctly.

I think that table-driven lexers are often faster in practice.  Your scheme essentially computes the transition table on the fly.  Table-driven lexers involve pre-computing the transition table, and now you only need to do a few instructions per character read from the input (read one character, do a table lookup based on the current state and just-read character, update the current state).  Therefore, their constant factor can be lower.

To be clear, by table-driven lexer, I mean something that converts the regexp to a DFA and then precomputes a table that represents the transition table.  This is useful in cases where the regexp is fixed and known at compile time.  For many regexps seen in practice, the size of the DFA is not too large and so this leads to a fairly efficient matcher algorithm.


Resources about implementing a database table I'd like to understand more how data can be stored on disk so it can be read quickly. I don't want to say database record because I'm not asking how to build a database. My question is closer to how would I build a table.
I'm not asking about indexing. I'm thinking about you have an application that already has some a pointer to a record.
I've been trying to find some references e.g. papers, books, but everything so far focuses on database design as in writing DDL or structures for indexing like B+ trees.
Are there any references that talk about how tables are actually implemented and what are the tradeoffs?

Databases have some issues that "mere mortal" data storage doesn't concern itself with, such as transaction safety and disk failure.
Here are a few classic papers on the topic:

Astrahan et al (1976), System R: A Relational Approach to Data Base Management, ACM TOMS 1:2, pp 97-137.
Stonebreaker et al (1976), The Design and Implementation of INGRES, ACM TOMS 1:3, pp 189-222.
Stonebreaker (1987), The Design of the POSTGRES Storage System, VLDB '87, pp. 289–300.

There are also some good books that cover the relevant topics, such as Database System Implementation by Garcia-Molina, Ullman, and Widom.


Minimum number of transpositions Let's have two permutations $A$ and $B$ of $n$ numbers. What is the minimal number $m$ of transpositions to transform $A$ to B in the worst case? After analysing some algorithms my guess is that $m \sim n^2$ but I cannot find a formal proof.

If your transpositions form a permutation $\pi$ then (using the appropriate convention for multiplication) $A\pi = B$ and so $\pi = A^{-1} B$. This shows that we can assume without loss of generality that $A$ is the identity, and the question now becomes: how many transpositions do we need to multiply in the worst case to get any particular permutation? This might be a question you already know how to answer.


Regular concat with non regular If L is regular and M is non regular; then L.M is necessarily not regular. Is this true or false? And why?

I feel its false

The claim is this:

  If $L$ is a regular language and $M$ is a non-regular language, then the concatenation $LM$ of the two languages is necessarily non-regular.

If this claim is false, all you need to do is to provide one counterexample showing that it's false. If the claim is true, you need to prove that it's true for any languages $L$ and $M$, a much harder task. Fortunately, this claim is not true.

If we let $L = \emptyset$ and let $M$ be any non-regular language, then $LM = \emptyset = L$, a regular language.

Now, if that feels too much like cheating, we can find other examples. Consider this:

$L = \Sigma^*$
$M = \{ww^R \mid w \in \Sigma^*\}$

$L$ is regular, $M$ is non-regular (in fact, it's the language of palindromes, a canonical context-free language). Since the empty word is in $M$, we have $LM = \Sigma^* = L$, so the concatenation is regular.


Proving that a word is *not* generated by a context-free grammar I saw the answer in one of the solutions and I cannot figure out how they got the answer. The question is asked if the word is in the language or not for CNF...

How did they get the answer so that ab is in the language and aaaa is not in the language here ?

S -> aSb |ab

ab     Yes
aaaa   No
aabb   Yes

edit:
is aaaa No because it has b in aSb and ab is yes because obviously ab is there in aSb |ab

also aabb is in the language because of aSb cause you would add same amount of a's and b's to both sides

Let's assume you want to show that some word $w$ of length $n$ is not in the language generated by some grammar context-free $G$.

You can solve the problem algorithmically. There are two approaches:

Enumerate all strings in $L(G)$ of length at most $n$. In order to do that,

transform the grammar in Chomsky normal form and
enumerate all derivations with at most $n$ rule applications.

This works since every rule application adds one terminal symbol in CNF (there are no $\varepsilon$-rules). If your original grammar has this property (as does the one in your question), you can skip the transformation in CNF.

This is tractable for small $n$ and/or grammars with few words per length. As soon as $L(G)$ grows fast with $n$, it breaks down.
Parse $w$, for instance with the CYK algorithm. This runs in time $\Theta(n^3)$ and feasible for most grammars and inputs of reasonable size.

Clearly, the latter is the better option in an algorithmic mindset, but the former might be prudent if you have to make a quick decision given a short word in an exam-like situation.


Different feature sets for training and testing? Is it common to have a different feature set for samples in the train set and in the test set?

My use case is text categorization: when training, I use the words as the features. But when testing, I want to add hypernyms.

For example, if the training set contained the sentence "I eat a fruit", and there is a test sentence "I eat an apple", then I want to have the word "fruit" as a feature of the test sentence, in addition to its words, so that it will be classified positive. However, I don't want to add those hypernyms in the training set - if the training set contained only "I eat an apple", I don't want the sentence "I eat a fruit" to be classified positive.

So, I thought of having a small feature set for training, and a larger feature set for testing.

Is this common? If so, I would be happy to have some references.

The answer to the question in the title is no. Most ML algorithms are built around the assumption that the training and test data are drawn from the same distribution. So you should do the same pre-processing and use the same features at train and test time.

That being said, the procedure you describe sounds more like using background knowledge to make the features in the test set more similar to what you saw during training. This certainly seems like a reasonable thing to do and might fall under the heading of Domain Adaptation, when the distribution of the training and test sets change. Unfortunately I'm not familiar enough with the area to say for sure or give you a reference.


Understanding context free grammars in conjunction with PDA I have read TONS of articles about context free grammars and Pushdown Automata but I think there are things that I dont seem to understand. I am not studying computer science but I am really interested in many of the topics and I hope you can help me realign my knowledge about the CFG and PDA.

So my question is: could you tell me if what im writing here is correct? If not could you tell me what is wrong in my interpretation?

What I think I understood:

A state of a pushdown automata is equivalent to a set of production rules (or is it a production rule?) and these production rules contain replacement rules.

Depending on what character we read from our input we add an appropiate stack character or replace a character in the stack which is defined by one of the replacement rules.

So lets say we have defined the following production rule: a^n b^m : m != n

the replacement rules looks like:

production rule {
    input ; Stack Symbol -> To Do On Stack

    a ; nothing -> A
    a ; A -> AA
    b ; A -> nothing
    emtpy -> #
}

for  every "a" we read we add an A and for every "b" we remove an A.
The stuff what happens in my PDA stack is therefore defined in the replacement rule of my production rule?

Now if I wanted to parse a nested input like: "{hello world {fooBar is cool + 5}}"

I assume I need two production rules each with different replacement rules for our stack:

RULE 1:

{ ; nothing -> O
[a-zA-Z] ; O -> L

ok seriously I have to stop here because I have no idea what im doing.  I would appreciate it if you could tell if my interpretation is wrong and how to handle the last example.

I am sorry if I couldnt be more concise. Im currently a bit confused with this.

A PDA is a machine with a certain set of states and an infinite, initially empty, stack. It also has an input tape with the input word written on it. As long as there's input remaining, the machine reads the next character of input, checks its current state,  and pops off the top character of the stack to read it.  Based on what it finds, the PDA then switches into some new state and pushes a new character onto the stack.

The set of all languages PDAs can recognize is called the context-free languages. They are context-free roughly because what happens next depends only on the character at the top of the stack, rather than all the context beneath it in the stack. A PDA is finished when it goes into a special state for accepting or rejecting the input word. (Some people instead say that a PDA is finished when the stack is empty.) The language of a PDA is the set of all words that it accepts.

A context free grammar is a set of production rules. For simplicity, a production rule looks like $A \mapsto B$ or $A\mapsto BC$ or $A \mapsto \mathtt{a}$ or $A \mapsto \epsilon$. These respectively mean "If you have the symbol $A$, you may replace it with $B$ / $BC$ / the character $\mathtt{a}$ / the empty string."  A production rule is a rule that allows you to transform a symbol. The capital letter symbols are called nonterminals; they are sort of like variables. The symbols like $\mathtt{a}$ are terminals; they are sort of like constants.  There is a special nonterminal symbol called the start symbol, usually denoted $S$. The language of a context-free grammar (set of rules) is the set of all strings of terminals (like $\mathtt{abcde}$) you can make starting from the start symbol $S$ and applying any of the rules until only terminal symbols remain.

It turns out that context-free grammars (CFGs) are equivalent to pushdown automata (PDAs) because they can recognize the same languages. In particular, for every CFG there's a corresponding PDA, and vice versa.

Here's the CFG->PDA recipe. If you have a CFG, make a PDA with one start state and one reject state. Push the start symbol onto the stack. Then, loop: pop off the top symbol of the stack. Nondeterministically pick a production rule with that symbol on the left hand side. Push all the symbols on the right hand side of that rule onto the stack (make sure the leftmost symbol ends upon top). If the symbol at the top of the stack is a terminal character, make sure it matches the next character of input, otherwise reject. If the stack becomes empty, accept.


Dynamic Programming Problem on Tree Given a tree $T$ rooted at $1$. Each node might have more than 2 children. You want to create a tree $S$ where each node have $2$ or less children or a binary tree. For each node $u$ in $T$ which had more than $2$ children. Let $D$ be the number of $u$'s children. You can add $D-2$ node to replace the edge connecting $u$ and its children to form a new tree where $u$ is the root and the leaf nodes are its children. There are many possible ways to create $S$. Find the minimum depth of $S$ where depth is the maximum distance from root to some leaves.

My idea is to use Dynamic Programming approach. Let $dp[u]$ be the minimum depth we can make for subtree which $u$ is the root. Let $v$ be the child node of $u$. My approach is to sort $dp[v]$ in descending order and then use Dynamic Programming on the sorted list in $O(n^3)$. Similar to the solution of Matrix Chain Multiplication. But this approach is too slow. Is there any greedy solution so that I can calculate $dp[u]$ in $O(n)$ or $O(n log n)$?

So the difficulty is to determine $dp[u]$, depth of $u$, starting from the list of its sons depths $L[dp[v]]$.

Once $L[dp[v]]$ is sorted in a heap, you can recursively and greedily pop the 2 minimum values $i$, $j$ and push $1+max(i, j)$.

For instance, $L[dp[v]] = [7,5,5,4,3,2,2]$:

=> [7,5,5,4,3,3]
=> [7,5,5,4,4]
=> [7,5,5,5]
=> [7,6,5]
=> [7,7]

$dp[u] = 8$

This is actually $O(nlog(n))$ due to the heap sort.


Principles of Distributed Computing - "processors" and "states" So I'm learning about distributed computing, and I do understand a lot of the prerequisite material on algorithms and automata and whatnot... but I'm curious about the definitions I'm seeing as I read my textbook.

  A system consists of $n$ processors $p_{0},\dots,p_{n-1}$, where $i$ is the index of the processor $p_i$. Each processor is modeled with a (possibly infinite) state machine with state set $Q_i$. The processor is identified with a particular node in the topology graph. The edges incident on $p_i$ are labeled arbitrarily with the numbers $1$ thru $r$, where $r$ is the degree of the $p_i$. Each state of the processor $p_i$ contains $2r$ special components: $inbuf_i[\mathcal{l}]$ and $outbuf_i[\mathcal{l}]$.

Does this mean that each state of an n-state state machine has a separate inbuffer and outbuffer? Based on the wording of this, it seems to imply that there are n of each buffer, which would say to me that an outbuffer is mapped directly to the inbuffer of another state in another processor.

Based on the wording of this, it seems to imply that there are n of each buffer

Assuming that each edge in the network graph $G=(V,E)$ corresponds to a bidirectional channel, there are $4|E|$ many buffers in total: For an (undirected) edge $(p_i,p_j)$, we have one pair of in/out buffers for $p_i$ and one pair for $p_j$.

  Each state of the processor $p_i$ contains $2r$ special components: $inbuf_i[l]$ and $outbuf_i[l]$.

Let's look at an example to get an intuition for what the above means:
Suppose that we have some network where $p_3$ is connected to $p_1$ and $p_2$.
Let's assume that process $p_3$ sends a message $m$ to process $p_1$ and has received (but not yet processed) a message $m'$ from process $p_2$. Moreover, $p_3$ has a local variable $counter$. Then we could represent the current state $\sigma_3$ of $p_3$ as  $$\sigma_3 = (inbuf_3[1],inbuf_3[2],outbuf_3[1],outbuf_3[2],counter).$$
According to the above example, $m' \in inbuf_3[2]$ and $m \in outbuf_3[1]$. Note that the state of the network is given by $(\sigma_0,\dots,\sigma_n-1)$.


If my computer is a 32 bit system,it has a 32 bit address right?But when i print any memory address in C why do i get a short value? For example

printf("%u",&a);

gives me output
65524

If my computer is a 32 bit system, it has a 32 bit address right?

You should not take it for granted.

Many older processors had external (or internal) buses narrower than 32 bits (thus limiting memory size or demanding more cycles for instruction fetch) but were labeled 32-bit based on the fact that they had 32-bit registers and instructions able to manipulate 32-bit quantities.

Some examples are Motorola 68000 and IBM System/370.

Also a 32 bit system, for backward compatibility, may use a non linear address space (e.g. Intel 80386 fully support the 16-bit segmented address space of its predecessors).

Conversely processors with 32-bit registers and instructions that manipulate 32-bit quantities may have bigger external address bus (e.g. Pentium Pro with 36 bits and a larger address space than 4 GB).

Anyway the correct explanation (educated guess) is in the comments (further details in https://stackoverflow.com/q/5208641/3235496).


Snowball Question FFT http://courses.csail.mit.edu/6.046/spring04/handouts/prac-quiz2-sol.pdf

I'm confused as to the solution for the snowball question. To start with, I have two specific questions:

(1) Each pair $a_i,b_j$ will account for one term (and why ONE term)? What is meant by term here? The coefficient, $c_k$ of the polynomial C? Or maybe the $x$ value at the $kth$ spot?

(2) Why is $c_k$ the number of such pairs?

Here is the idea of the proof. Let $a_i,b_i$ be the distance thrown by the $i$th male/female. Using FFT, we calculate
$$ \left(\sum_i x^{a_i}\right) \left(\sum_j x^{b_j}\right) = \sum_{i,j} x^{a_i+b_j}. $$
Each pair $i,j$ satisfying $a_i + b_j = k$ contributes one term $x^k$ to the polynomial on the right. Hence the coefficient of $x^k$ is the number of pairs $i,j$ such that $a_i + b_j = k$.

If things still aren't clear, I suggest you try a few examples.


BIT: Unable to understand update operation in Binary index Tree I have just read this answer and was very satisfied and it is indeed a fantastic answer. It taught me the working of BIT.

But at the end, the second last paragraph is where I am struggling.
It says,

  Similarly, let's think about how we would do an update step. To do this, we would want to follow the access path back up to the root, updating all nodes where we followed a left link upward. We can do this by essentially doing the above algorithm, but switching all 1's to 0's and 0's to 1's.

But if I see, take some example, it does not work just as by simply switching 1's and 0's, according to me.

e.g. lets take we want to update value at node 5 = 101
Switching 1s and 0s, we get 010...
Now applying the procedure they have given earlier, we will end up updating some other node or so.

I must be getting it wrong. Please correct me.

Thank you in advance.

If you don't stick to the claim of "switching all 1's to 0's and 0's to 1's" (I am also confused) in that post, here is the simple bitwise trick for updating used in the original paper "A New Data Structure for Cumulative Frequency Tables" (Figure 5) by Peter Fenwick (Ix for index).

Repeat:
Tree[Ix] := Tree[Ix] + val;
Ix := Ix + BitAnd(Ix, -Ix);    // add the least-significant one
Until Ix >= TableSize

That is, the nodes accessed via a left link upward from the original node i can be calculated by
i += i && -i.

i && -i is the least significant bit of i. i += i && -i moves you to the ancestor that is closest to the right side of i. This is the next node you will need if you want to add all the nodes to the right of i.

In your example, i = 5_(10) = 101_(2). The first i && -i gives 001 and i + i && -i moves you to node i' = 110_(2) = 6_(10). The second i' && -i' on i' gives 010 and i' + i' && i' moves you to node i'' = 1000_(2) (which is too large).

For an example with 31 nodes and i = 9 = 1001, you will access the following nodes: i' = 1001 + 0001 = 1010, i'' = 1010 + 0010 = 1100, and i''' = 1100 + 0100 = 10000 (which is too large).

By the way, in the case of query, the bitwise trick is simply modified to i -= i && -i. It is easy to verify that this trick agrees with the procedure of "Clearing the rightmost 1 bit". Also see the related post here.


Difference between $\mathsf{SIZE}(n^k)$ vs $\mathsf{P/poly}$ and $\mathsf{SIZE}(n)$ vs linear size circuit? In the Wikipedia page on the Karp–Lipton theorem it is mentioned that $$\Sigma_2\not\subseteq\mathsf{SIZE}(n^k)$$ (which is known) is not same as $$\Sigma_2\not\subseteq\mathsf{P/Poly}$$ (which is open). I was of the opinion $\mathsf{P/Poly}$ referred to polynomial size circuits which seems same as $\mathsf{SIZE}(n^k)$. Why are these circuit complexity classes different? Could someone provide an illuminating example?

Does this mean that $\mathsf{NP}\subseteq\mathsf{P/Poly}$ is possible but $\mathsf{3}$-$\mathsf{SAT}\in\mathsf{SIZE}(n)$ is impossible?

For example in this paper it is shown $\mathsf{PP}$ has linear sized circuits with respect to an oracle but not even a quantum circuit of size $\mathsf{SIZE}(n^k)$. But at $k=1$ linear circuits coincide with $\mathsf{SIZE}(n)$. Correct?

$\mathsf{P/Poly} = \bigcup\limits_{k\in\mathbb{N}}\mathsf{SIZE}(n^k)$.

We don't know if every language in $\Sigma_2$ has a polynomial size circuit, but we do know that we cannot have polynomial circuits of bounded degree,i.e. $\mathsf{SIZE}(n^k)$ for some $k\in \mathbb{N}$, for all languages in $\Sigma_2$ (Kannan's theorem).


About a step in the analysis of Quicksort by Sedgewick and Wayne In the book Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne, when they are analyzing quicksort (page 294), they present the sequence of transformations:
$$\begin{gather*}
C_N = N + 1 + (C_0 + C_1 + \dots + C_{N-2} + C_{N-1})/N + (C_{N-1} + C_{N-2} + \dots + C_0)/N\\
NC_N = N(N+1) + 2(C_0 + C_1 + \dots + C_{N-2} + C_{N-1})\\
NC_N - (N-1)C_{N-1} = 2N + 2C_{N-1}\\
C_N/(N+1) = C_{N-1}/N + 2/(N+1)\\
C_N\sim 2(N+1)(1/3 + 1/4 + \dots + 1/(N+1))\end{gather*}$$

How did they get the last transformation?

It is also written that the parenthesized quantity in the last expression  is the discrete estimate of the area under the curve $2/x$ from $3$ to $N$? How is it related to quicksort?

Let $\rho_N = C_N/(N+1)$. The next to last equation shows that
$$
\rho_N = \rho_{N-1} + \frac{2}{N+1}.
$$
Therefore
$$
\rho_N = \frac{2}{N+1} + \cdots + \frac{2}{2+1} + \rho_1.
$$
Multiplying by $N+1$,
$$
C_N = (N+1) \left(\frac{2}{3} + \cdots + \frac{2}{N+1} + \rho_1\right).
$$
Since $\rho_1$ is a constant whereas $2/3 + \cdots + 2/(N+1) \to \infty$, we deduce that
$$
C_N \sim (N+1) \left(\frac{2}{3} + \cdots + \frac{2}{N+1}\right).
$$
We can estimate this expression in many ways, for example by approximating the series by an integral (this is what the authors suggest when they mention the area under the curve $2/x$). Or we can recognize that it is roughly equal to $2H_{N+1}$, twice the $(N+1)$st harmonic number, and so using the well-known estimate $H_N \sim \log N$,
$$
C_N \sim 2N\log N.
$$

Finally, regarding the relevance to Quicksort, my guess is that $C_N$ is the average number of comparisons performed on a random array of length $N$; but you should be able to tell by reading the book.


Breadth First Search actually require specifically Queue instead of any other type of Collection? As far as I know, Breadth-First-Search [BFS] theory traditionally requires a Queue to process a given level of a graph (i.e: wiki seems to assume so).

But does BFS really actually require a Queue, rather than just any type of Collection?

A Queue is a Collection
A Set is also a Collection, for example

Wiki states that BFS...

  "explores all of the neighbor nodes at the present depth prior to
  moving on to the nodes at the next depth level."

What about that quote requires specifically a Queue?  Why would BFS not work if implemented with any other type of Collection besides a Queue?

It seems to me that as long as any Collection is used to explore "all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level", by storing such neighbor nodes in that Collection and ensuring the entire Collection is emptied (or otherwise completely processed or explored) before moving on to the next depth level, then the level-ordering requirement of BFS is achieved?

I understand that a Queue would ensure a certain order (i.e: left-to-right) while processing/exploring within a given level; but is that ordering within a given level really necessary such that the algorithm still meet the requirements of BFS?  Otherwise why is order within a given level actually necessary?

It doesn't literally have to be a queue. Anything that ensures that one level is completely explored before moving to the next one would suffice. However, the most natural way to do this is with a queue and any other implementation is going to be harder to describe and/or harder to implement than just "use a queue."

As evidence that it's harder to describe, note that your claim in the question that it suffices to ensure that the collection is empty before moving onto the next level is incorrect.  Consider the following tree.

    1
   / \
  2   3
  .   .
  .   .
  .   .

We start searching at node 1. We place its children 2 and 3 in the collection. So the collection isn't empty but it's definitely time to move on to the next level.

OK, how do we fix this? Well, we could have two collections: one for the current level and one for the nodes that need to be expanded at the next level. Each time we process a node at the current level, we add its children to the "next level" collection. When the current level is all done, the "next level" collection becomes the "current level" collection, and we start a new, empty, "next level". OK, that works, but it's harder to describe than using a queue. On the other hand, if you want to claim that it's easier to prove that the two-collection version is correct, you'd have a point. Really, everything is a trade-off.


Dynamic testing of down casts as explained in TAPL On page 195 of Pierce's TAPL book, he states that one can replace a down-cast operator by some sort of dynamic type test. Then he gives the following rules:

T-Typetest:

$\dfrac{\Gamma \vdash t_1:S \;\; \Gamma,x:T \vdash t_2:U \;\; \Gamma \vdash t_3:U}{\Gamma \vdash \text{if } t_1 \text{ in } T \text{ then } x \to t_2 \text{ else } t_3 \to t_3: U}$

E-Typetest1:

$\dfrac{\vdash v_1:T}{\text{if } v_1 \text{ in } T \text{ then } x \to t_2 \text{ else } t_3 \to [x \mapsto v_1]t_2}$

E-Typetest2:

$\dfrac{\nvdash v_1:T}{\text{if } v_1 \text{ in } T \text{ then } x \to t_2 \text{ else } t_3 \to t_3}$

There is no further explanation and I'm unaware of how to interpret these rules. Reviewing them, I realize that the first is a typing rule and the second and third are evaluation rules. However, the syntax is a bit strange. What are the arrows in each branch of the if? Why the if includes the insyntax?

The first rule T-Typetest is a type-checking rule. Let's read it together. Firstly, $\Gamma$ is not important (on a first reading at least). We have the following premises:

$t_1$ has type $S$
if $x$ has type $T$ then $T_2$ has type $U$
$t_3$ has type $U$

The conclusions is, that we get an expression of type $U$ (I think your transcription should have "$: U$" instead of $\to t_3$ the conclusion):
$$\mathrm{if}\; t_1 \;\mathrm{in}\; T \;\mathrm{then}\; x \to t_2 \;\mathrm{else}\; t_3 \tag{1}$$
The meaning of this expression can be undrstood by looking at the other two rules, which are small-step operational semantics. Here is an incorrect explanation, which we will make correct in a moment:

If $t_1$ has type $T$ then (1) evaluates to $t_2$ with $x$ replaced by $t_1$. This is the case of "downcast", i.e., $t_1$ is downcast from $S$ to $T$, the downcast value is bound to $x$ and then $t_2$ is executed.
If $t_2$ does not have type $T$ then (1) evaluates to $t_3$. This is the "default" which we use when the downcast is not possible.

The above explanation is incorrect because we should use $v_1$ instead of $t_1$, by which the author is telling you: first evaluate $t_1$ to $v_1$, and then perform the downcast.

In an imaginary OO language the same thing might be written somewhat like this:

S t1 = ...;
...
if (t1 instanceof T) {
  T x = (T)t1;
  t2;
} else {
  t3;
}


What can be learned from the weights in a neural network? I'm very new to neural networks, and have been trying to figure some things out.  So, let's say you come across a neural network which has 100 inputs, a hidden layer with 200 nodes, and 32 outputs. Let's also say that you, the "discoverer" of this particular instance of a neural network, are able to read the weights of the individual neurons. What could you figure out about it's function?

1) Are you able to determine what the algorithm or logic is contained within the neural network?  Other than feeding in all possible inputs and studying the outputs it produces.

2) If you were given information about the connection of the neural network (maybe the network isn't fully connected), would solving question one above be easier?

It depends. Weights of neural networks can be graphed or visualized for some insight. This is especially useful if the neural network works with visual processing. It is possible to "derive" what low-level inputs to the neural network create particular neurons in higher levels to "fire" by working backwards through the neural network weights— in other words, the problem of finding/deriving the low-level input patterns that maximally excite particular neurons, and graphing the results. A great example of this is the recent breakthrough result by Google in a self-trained visual network that self-organized to find higher-level patterns like cats and human faces, etc. [1],[2],[3]

This is also known as "feature detection" and there is Nobel-prize winning research (1981 Hubel/Weisel) that demonstrates that real brain neurons function in a similar way, to varying degrees. Active research is ongoing/continuing in this area in both biological and artificial systems.

Another way of analyzing neural net weights is to conclude what factors (inputs) affect the neural network and which don't. For example, suppose the neural net is used to predict stock prices and it has various inputs relating to different economic variables such as say GDP, gold prices, DJIA (an index), and interest rates. After the network is trained (successfully!) to predict something (say future prices), one can determine how much effect each one of the input variables has on the final prediction.

Also a determination can be made of basic negative or positive correlation between input and output. In this way neural networks can be used in a manner very similar to statistical techniques like factor analysis.

So the answer is "yes absolutely," but only in the sense that there are different ways to reveal "algorithms" in neural networks via graphical or other "human-readable" representations other than with the typical representation of algorithms, i.e. code. But representing neural network weights in a human-readable way and finding new useful representations is an active area of research.

[1] Google Puts Its Virtual Brain Technology to Work Technology Review

[2] Google’s Artificial Brain Learns to Find Cat Videos
 Wired

[3] How Many Computers to Identify a Cat? 16,000 NYT


Run-time of Sorting Algorithm Problem

Consider the pseudocode for the sort algorithm below, which takes as input an unsorted array $A$ of $n$ integers with no duplicates.

sort(A, i, j)
  if i = j
    return
  m = floor[(i + j)/2]
  sort(A, i, m)
  sort(A, m + 1, j)
  if A[m] > A[j]
    swap A[m] and A[j]
  sort(A, i, j - 1)

Write a recurrence that characterizes the runtime of sort(A, 0, n-1).

Attempted Solution

Let $T(n)$ be the run-time of sort(A, 0, n-1)

if i = j then return $\hspace{0.1cm} = \hspace{0.1cm} O\hspace{0.01cm}(1)$

m = floor[(i + j)/2] $\hspace{0.1cm} = \hspace{0.1cm} O\hspace{0.01cm}(1)$

sort(A, i, m) $\hspace{0.1cm} = \hspace{0.1cm} T(\frac{n}{2})$

sort(A, m + 1, j) $\hspace{0.1cm} = \hspace{0.1cm} T(\frac{n}{2})$

if A[m] > A[j] then swap A[m] and A[j] $\hspace{0.1cm} = \hspace{0.1cm} O\hspace{0.01cm}(1)$

sort(A, i, j - 1) $\hspace{0.1cm} = \hspace{0.1cm} T(n - 1)$

$\therefore T(n) \hspace{0.1cm} = \hspace{0.1cm} 2 \hspace{0.1cm} T(\frac{n}{2}) \hspace{0.1cm} + \hspace{0.1cm} T(n - 1) + \hspace{0.1cm} O\hspace{0.01cm}(1)$

Is this correct? Feedback would be greatly appreciated.

Sort in Action

The sort algorithm actually works. See this example to convince yourself.

https://imgur.com/G5FUewE

This is just Bubble-Sort in disguise. Each time, you get the biggest element pushed to the end of the array, then you sort the remaining of the array.

Your recurrence is correct.

An upper bound would be $T(n) = O(2^n)$.

Proof: For large enough $n$, we have $T(n)\leq 2^n$. This is the base case for induction. Induction hypothesis is $T(n)\leq 2^n$. So, we have $$2\sqrt{2^n}+\frac{2^n}2+O(1)\leq 2^n$$.


Do all languages in $P$ have polynomial proofs that they are in $P$? A proof for a language $L$ belonging to a complexity class $C$ can be framed as there existing a verifier $V$ that accepts this proof as the first part of their input and the language as the second. The verifier verifies this language is a member (a word) in the language representing the complexity class.

Verifier: (Proof for $L$ in $C$, $L$)$\longrightarrow$[0,1]

Do all languages in $P$ have a proof of the fact that they are in $P$ that can be verified in polynomial time? Given a language, determining if an arbitrary $L$ is in $P$ is undecidable; however, given a proof for a language in $P$, can that language be verified to be in $P$ in polynomial time?

Depending on how the language is specified, the answer may be yes or no.  For instance, consider the following language: $L_S = \{0\}$ if statement $S$ is true, otherwise $L_S =$ the language of the halting problem.  Note that if $S$ is true, then $L_S$ is in $P$, otherwise $L_S$ is not in $P$.  Now by Goedel's incompleteness theorem, there exists a true statement $S$ that has no proof that it is true.  Thus, the corresponding language $L_S$ is in $P$ but has no proof that it is in $P$.  You haven't given us enough details about how you propose to represent a language to determine whether your representation is expressive enough to allow defining such a language.  So, the answer is unanswerable as stated.

This highlights why it is crucial to explain how you represent the inputs.  There is no accepted, standard way to represent a language as a finite bit string -- indeed, the set of all languages is uncountable, so for any representation you might have in mind, there will always exist some languages that cannot be represented.  Without this, the question isn't well-posed and can't be answered until you specify this deatil.

As Yuval Filmus explains, the usual understanding of the word "proof" in CS is something that can be verified in polynomial time, so if it has a proof, it has a proof that can be verified in polynomial time.


Why is BNF considered an unsatisfactory technique for describing a language? I was reading the paper Fundamental Concepts in Programming Languages by C. Strachey the other day, wherein I read something that was quite strange to me. Quoting directly (with the strange part highlighted by me):

  Faced with the situation as it exists today, where there is a generally known method of describing a certain class of grammars (known as BNF or context-free), the first instinct of these mathematicians seems to be to investigate the limits of BNF—what can you express in BNF even at the cost of very cumbersome and artificial constructions? This may be a question of some mathematical interest (whatever that means), but it has very little relevance to programming languages where it is more important to discover better methods of describing the syntax than BNF (which is already both inconvenient and inadequate for ALGOL) than it is to examine the possible limits of what we already know to be an unsatisfactory technique.

Is there a specific reason the author considers the BNF to be an unsatisfactory technique for describing languages? Could it be because you can only describe syntax and not semantics with a single BNF grammar (though, you can extend it to describe operational semantics via turning it into an attribute grammar)?

You mention one reason.

The other reason is that the syntax of programming languages isn't context-free, unless you define syntax to be that which can be, or is, described by a context-free grammar.

When Strachey's paper was written, the syntax of a new language, Algol 68, was being defined in a new formalism, two-level grammars, that was used to describe syntactic validity in full, including many things that, brainwashed by the "BNF is the syntax" meme, many of us do not consider part of syntax at all, such as all variables needing to be declared before use.

Most of us won't go that far, but will still agree that non-context-free syntactic features in programming languages exist.


Is O(1) considered polynomial time? I am reading about P and NP and looking at the reduction of a Rudrata/Hamiltonian path to a Rudrata cycle. I think adding an extra node and 2 edges connecting the start, s and the target, t is O(1) time as this doesn't depend on the size of the graph. Algorithms by Dasgupta et al. says that the pre and post processing steps take polynomial time.

One last detail, crucial but typically easy to check, is that the pre- and postprocessing functions take time polynomial in the size of the instance
(G, s, t).

This makes me think that O(1) is polynomial time. Is this incorrect?

Yes, any constant is a polynomial of degree zero.


What would be acceptable size of list for O(n!) algorithm I was wondering what the limitations to an algorithm that runs in O(n!). For example lets take an algorithm that generates all permutations of a list. Now what i am wondering is what the upper bound would roughly be for size of list. I understand that this can vary based on ram/memory. Let's say that this would be ran client side and be expected to work on basically any machine a user would have at his/her home.

Thanks in advance for any insight.

It depends a bit on the constants hidden in the $O$, so no general answer is possible. In my experience you can aim for the low teens. 13! is about six billion. A computer can do about a billion things in a second, so a runtime of a couple of minutes seems reasonable if you only want to enumerate permutations. 15! is already more than a thousand times bigger, so most likely whatever you want to do will take too long.

On my machine counting to 11! in Python takes 14 seconds and counting to 12! takes two and a half minutes. Counting to 13! would hence take about half an hour. Counting to 15! would take about a week.


Prove Σ* is decidable I see that Σ* is claimed to be decidable in many documents, but I have never seen an example or easy demostration that it is decidable.

What is the proof that Σ* is decidable?

Theorem: The set $\Sigma^{*}$ of all words is decidable.

Proof. According to the definition of decidability, we must provide a computable function $d$ which takes a word $w$ and outputs $1$ if $w \in \Sigma^{*}$, and outputs $0$ if $w \not\in \Sigma^{*}$. Such a function is very easily constructed, it is
$$d(w) = 1,$$
That is, because every word is in $\Sigma^{*}$, the decision function always says "yes". QED.


What is a homogenous half-space? I can't think of any definition for half-space that would involve some sort of quantity not being homogenous.
This term is used in the paper Robust Concepts and Random Projection in the following paragraphs:

The next problem we consider is learning an intersection of t half-spaces in Rn, i.e., the positive examples all lie in the intersection of t half-spaces and the negative examples lie outside that region. It is not known how to solve the problem for an arbitrary distribution. However efficient algorithms have been developed for reasonably general distributions assuming that the number of half-spaces is relatively small [8, 44]. Here, we derive efficient learning algorithms for robust concepts in this class.
We assume that all the half-spaces are homogenous. Let the concept class of intersections of half-spaces be denoted by H(t,n). A single concept in this class is specified by a set of t half-spaces P = {h1, . . . , ht}, and the positive examples are precisely those that satisfy hi · x ≥ 0 for i = 1 . . . t. Let (P, D) be a concept-distribution pair such that P is -robust with respect to the distribution D. We assume that the support D is a subset of the unit sphere (and remind the reader that this as well as homogeneity are not really restrictive, as they can be achieved by scaling and adding an extra dimension, respectively; see e.g. [44]).

It's not clear to me from context, not defined in the paper and I haven't been able to find a clear definition from searching for it.

A half-space is said to be homogeneous if the hyperplane that defines it contains the origin.

(Source: S. Vempala, A Random Sampling based Algorithm for Learning Intersections of Half-spaces. Journal of the ACM 57(6) article 32, 2010. PDF.)


The transition function in a Markov decision process A Markov decision process is typically described as a tuple $\langle A,U,T,R \rangle $ where

$A$ is the state space
$U$ is the action space
$T: A \times U \times A \mapsto [0,\infty) $ is the state transition probability function
$R:A \times U \times A \mapsto \mathbb{R}$ is the reward function

What does this $A \times U \times A$ actually mean in terms of the MDP? It  is written in all the papers, but never explained. Does it mean that all the states $a \in A$ are multiplied with all the action $u \in U$? Or something completely different?

The notation $T\colon A\times U\times A\to[0,\infty)$ means a function with three parameters, the first from $A$, the second from $U$, and the third from $A$, which outputs a non-negative real.

It is somewhat strange that the range is stated as $[0,\infty)$ rather than $[0,1]$. In fact, a perhaps better way of thinking of $T$ is as a function from $A \times U$ to the set of distributions over $A$. That is, $T$ gets a state and an action, and outputs a distribution over the set of states.

The semantics of $T$ are as follows: when at state $a$ and performing action $u$, the probability of moving to state $b$ is $T(a,u,b)$. Thus for all $a \in A$ and $u \in U$ we must have $\sum_{b \in A} T(a,u,b) = 1$.


How to generate tree variants of a tree using recursion? I have a tree T, I need to generate all possible variants of T by permuting all its child nodes(please refer the following figure). how can I generate all variants, T, using recursion?

any help is appreciated.

The outline is: You start the function-call at the root vertex. For every child-vertex, you find all permutations of its sub-tree. Then you you find all combinations of these permuations of the children's sub-trees, and for each of them do all permutations of the child-vertices themselves.
The recursion happens where you need the permutations of the sub-trees of the children.
The exit-condition is the call on a leaf.

Set<Tree> perm(vertex x):
    if x is leaf:
        return x
    Let C be the set of all children of x.
    Set<Tree> result <- emptySet
    For all different combinations of perm(c) from the vertices c of C, now called comb:
        For all permutations p of C:
            add to result the graph you get with comb and p.
    return result


Which of the following is a more appropriate complexity for this reccursive function? Given the following recurrence relation:
\begin{gather*}
h(A) =
\begin{cases}
  0,\qquad \qquad \text{ }\text{ }\text{ }A=0\\
  1+h(A-1),\text{ }\text{ }A\text{ is odd} \\
  1+h(\frac{A}{2}),\qquad \text{otherwise}
\end{cases}
\end{gather*}
which of the following choices best describes its complexity?
A) $h(A)\in\theta(\log_2A)$
B) $h(A)\in\Omega(\log_2A),\text{ }h(A)\in\mathcal{O}(A)$
The book that I'm reading has selected choice $A$, however I feel like $B$ should be the answer. We know that the complexity is at minimum $\log_2A$ (best case when it's a power of $2$), but it could be higher than that and have a few more steps depending on what $A$ is. What am I missing here?

You can show that if the binary expansion of $A>0$ contains $N_0$ zeroes and $N_1$ ones then $h(A) = 2N_1 + N_0$. Since $N_0 + N_1 = \lfloor \log_2 A \rfloor + 1$, this shows that $h(A) = \Theta(\log A)$.


Seeking "gold standard" to evaluate accuracy of network clustering algorithm I'm currently looking at network clustering algorithms (we're currently looking at both directed and undirected, unweighted networks).  The algorithms we've tried produce visually nice clusters.  However, we would like to evaluate them against some "gold standard" -- a collection of networks in which the clusters have already been identified (and are more-or-less regarded as the clusters by the complex network's research community).

  Question: What are the gold standards for network clustering algorithms?  Where can I access them?

There are a couple of test sets mentioned in Stochastic blockmodels and community structure in networks by Karrer and Newman. One of them is the Karate Club Network, which is rather small, and the other is the Political Blog Network which is bigger. As far as I know, there is no gold-standard for testing clustering algorithms.


What is an Efficient Algorithm? From the point of view of asymptotic behavior, what is considered an "efficient" algorithm?  What is the standard / reason for drawing the line at that point?  Personally, I would think that anything which is what I might naively call "sub-polynomial", such that $f(n) = o(n^2)$ such as $n^{1+\epsilon}$ would be efficient and anything which is $\Omega(n^2)$ would be "inefficient".  However, I've heard anything which is of any polynomial order be called efficient.  What's the reasoning?

That depends on context. In theoretical computer science, usually every polynomial time algorithm is considered 'efficient'. In approximation algorithms for example a runtime of $n^{1/\epsilon^{1/\epsilon}}$ would be considered efficient, even though it won't be usable in practice for any reasonable value of $\epsilon$. An algorithm for SAT that runs in $n^{2^{100}}$ would be an amazing breakthrough.

In classic algorithmics, i.e. algorithms from the 80's and before, runtimes below $n^3$ or so (think matrix multiplication, min cost matching, flows, linear programming) are considered efficient. They still are considered efficient by most people, I'd say. Of course a $n^2$ algorithm is not considered efficient if a $n\log n$ algorithm is known, as for sorting for example.

Nowadays there is a trend towards sublinear algorithms or streaming algorithms that are able to deal with terabytes of data. Try using matrix multiplication to compute the page rank of all pages in Google's index. That won't work.

Of course, while certainly useful, the asymptotic runtime of an algorithm doesn't tell the whole story. There are algorithms that have good asymptotic runtime, but constants that are so huge that they effectively can't be used. Ever. Lipton calls them Galactic Algorithms. Robert Sedgewick even states that worst case bounds are "often useless for prediction, often useless for guarantees" and "worst-case analysis is useless for predicting performance" in his talk Putting the Science Back Into Computer Science.


Intersection of two generative neural networks I have an input x (a word), and I have a neural network Y such that Y(x), which is an image always satisfies F(x), and another neural network Z such that Z(x), which is also an image, always satisfies G(x).  Is there any way to turn this into a neural network Q where Q(x), which is also a image, satisfies "F(x) ∧ G(x)"?

Thanks!

No, not in general.  It's possible that $G(x)=\neg F(x)$, for instance.


Number of vertices and edges lies on the boundary of bounded cells in line arrangement I am learning computational geometry by myself using these lecture notes from ETH Zurich. Here is an exercise (8.9) I have been stuck for a few days:

For a line arrangement $A$ of a set of $n$ lines in $R^2$, let $F$ denote the union of the closure of all bounded cells. Show that the complexity
(number of vertices and edges of the arrangement lying on the boundary) of $F$ is
$O(n)$.

My intuition is to use induction, proving that when a new line $l$ is added, the number of added edges is a constant. This is similar to how we proved the zone theorem. However, I cannot figure it out. Can someone provide me with some hints?

Consider 3 additional lines such that their arrangement consists of a single bounded (triangular) cell $C$ and $F \subset C$. Then every edge of $F$ belongs to a zone (using a terminology from your textbook) of at least one of the 3 added lines. And all 3 zones of 3 added lines contain at most $30n$ edges according to Zone Theorem. So $F$ has no more than $30n$ edges which is $O(n)$.


Bellman-Ford without getting stopped by negative cycles Let $s$ be the source vertex. In the standard Bellman-Ford algorithm (e.g. the version found in CLRS), when there is a negative cycle reachable form $s$, the algorithm will return that a negative cycle is found.

But let's say I am interested in the shortest path from $s$ to some vertex $a$, and it might be that there is a negative cycle reachable from $s$, but it could also be that no such negative cycles have a path to $a$. So technically there is still a shortest path from $s$ to $a$. But Bellman-Ford would still say "negative cycle detected" although it is irrelevant! How might Bellman-Ford be modified to still spit out either the shortest path or that there is no shortest path?

Attempt: At first I saw thinking of running Bellman-Ford until $2n$ (or some large number) and then seeing if the value for $s$ to $a$ stays stable, but I found an example that invalidates this. It appears that I must find all negative cycles reachable from $s$ and check if each of them can reach $a$. That seems like an immense amount of work! So is there any clever way to do this?

Solution 1: First pre-process the graph to remove all vertices that cannot reach $a$.  This can be done using depth-first search (backwards in the graph; i.e., in the reverse graph), in linear time.  You can also pre-process the graph to remove all vertices that are not reachable from $s$, again in linear time.

Solution 2: Run Bellman-Ford for $2n$ iterations and see if the value from $s$ to $a$ stays stable for the last $n$ iterations.  This should work: any simple path (with no cycle) from $s$ to $a$ must use at most $n-1$ edges, and if there is a non-simple path from $s$ to $a$ traversing a negative-weight cycle, then there is one with at most $2n-1$ edges.  You might want to double-check your example; maybe you made a mistake when simulating Bellman-Ford by hand.


Algorithm to find sequence of minimum moves to sort 13 card hand Just for fun I am trying to write a program to sort the 13 cards (from a standard pack of 52) in a Bridge hand by performing human-like moves on the hand.

A sorted bridge hand is arranged by suit, with alternating colors of suit (if possible), and the cards are sorted by decreasing rank within each suit. For example

♣QJ3♥K4♠AQ974♦K76 is a sorted hand
♥K4♣QJ3♠AQ974♦K76 is not a sorted hand because the two black suits are touching
♣QJ♥K4♠AQ974♦K76♣3 is not a sorted hand because the clubs are not together
♣3JQ♥K4♠AQ974♦K76 is not a sorted and because the clubs are not sorted in decreasing rank.

The goal is to sort the 13 randomly dealt cards using the least number of the following human-like moves:

A card can be temporarily removed from the hand and inserted back somewhere else. For example the ♣3 in ♣QJ♥K4♠AQ974♦K76♣3 can be inserted after the second card to sort the hand.
Any number of consecutive cards can similarly be removed from the hand and inserted back somewhere else. For example the ♣QJ3 in ♥K4♣QJ3♠AQ974♦K76 can be moved to the front. This is considered one move.

What is an efficient algorithm to find the sequence of the minimum number of such moves to sort the hand?

This problem is harder than you might think.  Your operation of removing a block of adjacent cards and re-inserting the block somewhere else is known as a transposition.  Sorting by transpositions has been studied in the context of bioinformatics and is known to be hard.  Of course, if you limit the length to 13 cards, then efficiency becomes much less of a concern--even an exponential algorithm is likely to be fast enough.

I recommend breaking the problem into two related parts.  The first, lower level, is to write an algorithm for sorting by transposition on an array of integers, more specifically, on an array that is a permutation of the numbers 1..N.  This may be inefficient, but for small N, should be fast enough.

The second, higher level part, is to consider the possible arrangements of suits (clubs-hearts-spades-diamonds, ...).  There are at most 8 legal arrangements of suits, and fewer if one or more suits are missing.  For each arrangement of suits, it is easy to calculate, for each of the 13 cards, what position it should end up at, giving you an array of the numbers 1..13.  Then you can call the first part above as a subroutine.


Which is faster operations on register operands or immediate operands? I am reading the book Computer Organization and Design. It compares instructions on memory and instructions on registers but doesn't say anything about the speed of instructions when the source operand(s) is/are constants. In that case which will be faster register operands or immediate(constant) operands ?

It depends.

Like AProgrammer said, it depends on the processor.

We are in an age where there are many limiting factors based on physics in CPU construction. This means that distance traveled for an instruction and heat generated by a gate cause latency. In theory, this means that for a pipeline where the bottleneck is the decoding stage, this matters. With immediate operands, you would not need to travel to the register to grab the values, which is additional clock cycles and distance traveled. This would decrease latency, and thus increase speed.

However, in real world applications, this is very likely NOT the bottleneck, and so there will be little to no increase (if mandatory register access stages exist) in speed.


What is a list of "reasonable but undecidable" theorems? There are some theorems that go along the lines of "all reasonable properties of <math subject> are computationally undecidable." Here are two examples:

Rice's Theorem: "all reasonable semantic properties of programs are undecidable."
Adian–Rabin Theorem: "all reasonable properties of finitely presented groups are undecidable."

Even though I only know of two examples, I suspect that there are many theorems like these. Is there a list of these kinds of theorems?

Godel's First Incompleteness Theorem: "Any consistent formal system within which a certain amount of elementary arithmetic can be carried out is incomplete."
"A certain amount of elementary arithmetic" can be considered as reasonable properties of... well all math.
Incompleteness can also be seen as a form of undecidability.


How to shift a matrix by x rows and y columns in the most efficient way? My objective is to shift rows by x and columns by y in a 2d matrix. My problem is to solve this objective in an efficient manner.

x and y could be negative or positive. Negative would mean up/left and positive would mean down/right.

My current solution is something like this:

def rotate_columns(col, y):
    new_col_position = col+y if y < 0 else (col+n-y)
    return new_col_position
def rotate_rows(row, x):
    new_row_position = row+x if x < 0 else (row+m-x)
    return new_row_position

def shift(x,y):
    N = M.copy()
    for col in range(n):
new_col_position = rotate_columns(col)
        for row in range(m):
            N[row][new_col_position] = M[row][col]
    for row in range(m):
        new_row_position = rotate_rows(row)
        for col in range(n):
            N[new_row_position][col] = M[row][col]

An example:
Say, a given matrix is:

1 2 3
4 5 6
7 8 9

with x = 2, y = 1, it would be:

6 4 5
9 7 8
3 1 2

Is there a better way to solve this? By better, I mean better time complexity.

I could think of a time-efficient solution which is not good in terms of memory.

We will carry out duplication of the given array.

For eg.

Initial Array:

We can have 4 duplicate copies of the same array, each attached to form a huge square.

Big Array looks like:

Within this Big Array, let me call my result as the Result Array.

Initially, when we have no rotation involved, the result array looks like:

The Blue colored box represents the result array.

The top_left_index of the result array = (0, 0). [Image above]

After that, suppose we rotate 1 row, the blue colored box shifts down as follows:

The top_left_index of the result array = (1, 0). [Image above]

After that, suppose we rotate 1 column, the blue colored box shifts right as follows:

The top_left_index of the result array becomes = (1, 1). [Image above]

After that, suppose we rotate 1 row, the blue colored box shifts down as follows:

The top_left_index of the result array becomes = (2, 1). [Image above]

After that, suppose we rotate 2 cols, the blue colored box shifts right as follows:

The top_left_index of the result array becomes = (2, 3). [Image above]

This is how the entire logic works.

We just need to store the top left index of the blue box. Whenever asked for the result, we can display the elements of the blue-colored box.

So, the entire problem boils down to calculating the top left index of the blue box.

Time Complexity of changing the index: O(1)

Space complexity: O(n^2)

However, there exist corner cases that need to be handled. Once such corner case is as below:

Handling this corner case is not difficult. In case we feel that the resultant array's bounds are overflowing the boundary of the Big array, we need to reduce the value of our top_left_index such that the entire square fits in the array.
For eg.,

In the above image, the top_left_index (2,4) overflows the bounds of Big Array.

We simply reduce the overflowing index by the respective dimension of our original array and make it:

(2, 4 - 3 ) = (2, 1).

Now, things look beautiful again.


Curry–Howard correspondence and functional programming "reliability" The first time I heard about functional programming, someone told me "it's more reliable to code in a functional style because your type system is like a proof of correctness".
I recently learnt about the Curry-Howard (CH) correspondence and I think this is what he was using as a basis for his assertion about functional languages.
However, I have trouble understanding how far this leads to "more reliable programs".
Especially, here is my understanding:

In the CH view, a function type A -> B is the same as an implication $A \implies B$ in some constructive view of logic, and so on... (union type, product of type, etc.)
So if we end up being able to build an instance t of a type T it means we used only the available function types / implications using the available variables / assumptions.

Still, there are many ways a program written this way could be incorrect :

If I have several variables a, b, c, ... of the same type A available, I may use a transformation A -> B on the wrong one.
I may have different functions with the same signature A -> B but different use cases, and the type system won't be able to detect if I use the wrong one.

My questions are:

In practice, do functional programming languages enforce things like "there should be no more than one instance of a type" or some variant to avoid those kinds of errors ?
Is there a theoretical background in which we enforce more restrictions on functional languages and give the "more reliable" a stronger meaning ?

The dependent types allow you to specify what properties your function should have, not just what its domain and codomain are. This way it becomes impossible to accidentally use the wrong function.
For example, suppose we want a function that sorts lists (of integers). In ordinary programming we would ask for a value of type List → List, and then we would write documentation in English that says "and it is supposed to sort lists".
With dependent types, we would write down a fancier type:
Σ (f : List → List) Π (lst : List) isSorted(f lst) × isPermutation(lst, f lst)

(See below how one defines isSorted and isPermutation.)
An element of this type is a pair (f, p) such that f :  List → List and p is a function which takes as input any list lst and outputs a pair (q, r), such that: q is the proof that isSorted f lst and r is the proof that lst is a permutation of f lst. In other words, p proves that the output of f lst is precisely the sorted list lst.
If you think about it, it is impossible to accidentally use a non-sorting function. If you do, then you will not be able to also write down the proof that it really sorts lists.
In ordinary programming we are used to write down data and functions into the source code, but keep their properties in our heads. In dependent programming the properties are part of the source code, and so are the proof that those properties are satisfied.
P.S. We define isSorted : List → Type as
isSorted nil = True
isSorted (x :: lst) = (Π (y : int) . elementOf y lst → x ≤ y) × isSorted lst

It is a bit more annoying to define isPermutation, so I will not do it here.


What is the difference between Coding and Programming? In our daily life we use both coding and programming for the same meaning. I want to know the difference between these terms (If any).

If they are used for different meanings than please anyone can aware us about it, So we can correct ourselves.

They are mostly synonymous. In that profession you can be called, or call yourself, a coder, a programmer, a software developer, or a software engineer. They all do the same job. If you call yourself an "engineer", then in many jurisdictions you would have to have training, pass some stringent exams, and may have legal responsibilities for the results - people calling themselves "software engineers" usually ignore that.

The name used usually goes with some expectations. Someone called a "coder" or "programmer" is usually expected to write code (also called programming), with no expectations of the actual outcome. A "software developer" is someone who is expected to produce complete, working, usable software as the result of his work. A "software engineer" is usually someone who fancies a nice title.

"Coder" is often used as a pejorative. Usually by people who couldn't do it themselves if their life depended on it.


If $\{ww^R \mid w \in L\}$ is regular, is $L$ itself regular? If $L$ is some language and
$\{ww^R \mid w \in L\}$
is a regular language then does $L$ have to be a regular language?

Let $A = \{ww^R \mid w \in L\}$, and suppose that $A$ is regular. What can we say about $L$?
For a word $w \in \Sigma^*$, let $E(w) = \{x : wx \in A\}$. Since $A$ is regular, there are only finitely many different $E(w)$.
Say that $w \in L$ is self-terminating if it has no extension in $L$. If $w \in L$ is self-terminating then $E(w)$ is finite, and the unique longest word it contains is $w^R$. Therefore if $w_1 \neq w_2$ are both self-terminating words in $L$, then $E(w_1) \neq E(w_2)$. Consequently, there are only finitely many self-terminating words in $L$. Let $L'$ result from removing them and all their prefixes. Thus every word in $L'$ has infinitely many extensions in $L'$.
Say that $w \in L'$ is creative if there are two different letters $\sigma,\tau$ such that both $w\sigma$ and $w\tau$ have extensions in $L'$. If $w \in L'$ is creative then we can recover $w$ from $E(w)$ by taking the longest common suffix which appears infinitely often. This implies that there are only finitely many creative words in $L'$. Let $L''$ result from removing all creative words in $L'$ and their prefixes. Thus every word in $L''$ has infinitely many extensions in $L''$, and all of them are prefixes of a single $\omega$-word.
Let $x$ be an $\omega$-word that $L''$ has infinitely many prefixes of, and choose the shortest such prefix $w_x$. We can recover $x$ from $E(w_x)$ in the following way: the first $\ell$ letters of $x$ are the reverse of the suffix of length $\ell$ of all long enough words in $E(w_x)$. It follows that $L''$ consists of prefixes of finitely many $\omega$-words.
Let $x$ be one such $\omega$-word. By the pigeonhole principle, there exist $n_1 < n_2$ such that $x_1 \ldots x_{n_1},x_1 \ldots x_{n_2} \in L$ and $E(x_1 \ldots x_{n_1}) = E(x_1 \ldots x_{n_2})$. Since all long enough words in the former start with $x_{n_1+1} \ldots x_{n_2}$, it follows that $x_{n_2+1} \ldots x_{n_2+(n_2-n_1)} = x_{n_1+1} \ldots x_{n_2}$, and continuing in this way, we see that $x$ is eventually periodic, say $x=yz^\omega$.
The number of words of given length in a regular language is eventually periodic. It follows that we can modify $L''$ to another language $L'''$, differing in finitely many words, such that $L'''$ also consists of prefixes of finitely many $\omega$-words, and furthermore there exists a modulus $m$ such that for each $a \in \{0,\ldots,m-1\}$ and each $\omega$-word, either all prefixes of length $nm+a$ are in $L'''$, or none of them. Up to finitely many words, for each $\omega$-word $x = yz^\omega$, these prefixes are of the form $y' (z')^*$.
Every two $\omega$-words in $L'''$ differ in some symbol. It follows that for each such word $x$, and for each $a$, we can use regular closure operations to isolate the corresponding subset of $A$, which is of the form
$$ \{ ww^R \mid w \in y z^* \} = \{ y z^n (z^R)^n y^R \mid n \geq 0 \}. $$
We can further use regular closure operations to isolate
$$ \{ z^n (z^R)^n \geq 0 \}. $$
Applying the pigeonhole principle to the sets $E'(z^n)$ (where $E'$ is the analog of $E$ to the new language), we see that $E'(z^{n_1}) = E'(z^{n_2})$ for some $n_1 < n_2$. Since $(z^R)^{n_1} \in E'(z^{n_1}) = E'(z^{n_2})$, it follows that $z^{n_2}(z^R)^{n_1} = z^{n_1} (z^R)^{n_2}$, and so $z = z^R$.
We conclude that there exist $a,b \in \mathbb{N}$, words $w_1,\ldots,w_a,y_1,\ldots,y_b$, and palindromes $z_1,\ldots,z_b$, such that
$$
L = \sum_{i=1}^a w_i + \sum_{j=1}^b y_j z_j^*.
$$
The corresponding language $A$ is
$$
A = \sum_{i=1}^a w_i w_i^R + \sum_{j=1}^b y_j (z_j z_j)^* y_j^R.
$$


simple question about epsilon and estimation turing machines i am getting really confused by it. i got to a point i had to calculate the lim when $n \rightarrow \infty$ for an optimization problem, and i got to the point that i had to calculate a fairly simple limit: $lim_{n \rightarrow \infty} {3-\frac{7}{n}}$.

now i used $3 - \epsilon$ and i am trying to show that  there can't be any $\epsilon>0$ so that the estimation of the algorithm is $3-\epsilon$, because there exists a "bigger estimation" - and this is the part i am not sure about, what is the correct direction of the inequality? $3-\frac{7}{n} > 3 - \epsilon$ or the opposite? i am trying to show that the estimation ration is close to 3.

i think that what i wrote is the correct way, but not sure. would appreciate knowing what is correct in this case. thanks.

Suppose there exists $k>0$ such that $\lim_{n\to\infty} \left(3-\frac7n\right)=3-k$.

By the definition of a limit,
$$\lim_{n\to\infty} f(n)=L\Leftrightarrow \forall\epsilon>0,\exists N>0,n>N\implies |f(n)-L|<\epsilon$$

Here, we need to check:
$$\lim_{n\to\infty} \left(3-\frac7n\right)=3-k\Leftrightarrow \forall\epsilon>0,\exists N>0,n>N\implies \left|k-\frac7n\right|<\epsilon$$

Now, disproving this just requires a suitable choice of $\epsilon$. Consider $\epsilon=\frac k2$. We have for all $n>\frac{14}{k}$, $\left|k-\frac7n\right|>\frac k2$. So, there does not exist any $N>0$ satisfying the condition, and as  a result, no such $k>0$ can exist.


Context Free Grammar to Regular Expression? I want to learn whether I can create regular expressions from the given Context Free Grammar. I found some examples that can be translated to regular expressions. However, all of them were like this: "S-> aB | bC". Whereas my example is like: "S-> AB | BC". Here is my example:

Can I create RE's from this? What is the reason? I want to fully understand why I can and why I cannot. Thank you.

The set of all regular languages is a subset of context free languages. So if you have a context free grammar (CFG) that generates a regular languages, you most certainly can convert it to a regular expression (RE), regular grammar (RG), or finite automata (FA).
Before I go further with your example, I will simplify it so that we only deal with 3 terminals (instead of 8). In the example below, the terminals a,b,c will be represented by the single terminal a, the terminals x,y,z will be represented by x, and the terminals p,q will be represented by p.
S -> N V
N -> a N | N N | N a | x
V -> N V | p

There is no real procedure in converting it, so we will take it step by step. First we need to see what kinds of strings the variable N can produce.
We can see that for every N introduced, it terminates with x. The a's can be on either side of x and repeat as many times as needed. This entire pattern can be repeated as many times as needed, but be produced at least once. So N generates the same strings as $(a^*x^+a^*)^+$ RE.
Next we look at V. It can produce any amount of N's but must terminate with a single p. So we have $((a^*x^+a^*)^+)^*p = (a^*x^+a^*)^*p$.
Finally, S produces NV which is similar to our RE for V. Note that there is at least one N produced. So that CFG is converted to $(a^*x^+a^*)^+p$.
To put it in terms of your original grammar, it would look something like this $((a|b|c)^*(x|y|z)^+(a|b|c)^*)^+(p|q)$. Again, because of the amount of terminals in the original grammar, it is easier to simply things to help see the pattern the grammar is actually showing.
As a disclaimer, this is not a proof, but it shows the reasoning as to how I created an RE from the CFG you provided. To know if this is correct, you would need to know the exact language the CFG produces. Unfortunately, the grammar is not easily recognizable.
I used the following CFG Developer tool to help see a pattern from your grammar.


Creating a numbered list, divided into types, without need for shifting or re-ordering - is this a re-occuring problem My question is not for a solution to the problem, though I do need to put thought into it but rather my question is if this conceptual problem has a name or has been addressed at already in computer science.

I want to create a list of numbered defines, each uniquely mapped, and divided into groups based on type. The goal is a design that does not require renumbering or shifting when reaching the end of the previously allotted space for a certain type. An example may help

    // Dogs (1 to 3 available)
    define DOG_1            1
    ....
    define DOG_3            3

    // Cats (4 to 6 available)
    define CAT_4            4
    ....
    define CAT_6            6

    // Pigs (7 to 10 available)
    define PIG_7            7
    ...
    define PIG_10           10

Now if I want to add space for more dogs it requires shifting etc.

This problem seems similar to something found in memory allocation/fragmentation. I want to find literature that addresses the problem if it exists.

Thanks,
Godrick

You might be  looking for an enum.  See https://en.wikipedia.org/wiki/Enumerated_type.


How to pick w for the Pumping lemma if the language has no clear pattern? I'm trying to understanding using the pumping lemma to prove that a language is not regular. I sort of understand how it works when the language describes strings with a particular form, like in this example, but what do you set w to if there isn't a particular form.

The particular problem I'm trying to prove isn't regular:
The language is the set of strings that is composed of 60% or more As and Bs with the alphabet {A, B, C, D}

Because the form of the strings is indeterminate (i.e. it doesn't follow a pattern like a^i b^i, I'm not sure how to divide the strings into a w and x, y, z.

I think your confusion lies in the fact that the language is not given in more "structured" form. Even if the language is not given as such, you are free to choose any string from the language which is more "structured" and allows you to disprove that language is regular.

Take $w=C^{2N}A^{3N}$ (or $A^{3N}C^{2N}$) where $N$ is the pumping length and $w$ is a string in your language, and then follow the proof in similar lines as in  How to prove that a language is not regular?.

You should prove by yourself that above string $w$ can not be pumped.


How to Identify which instructions are represented by this microcode I'm having issues with a question how to identify which instruction  are represented by this microcode.
The pc starts at 5000 and 7000 and 7001 have values 31 and 64 - I'm really confused how to approach this wouldn't each line be an instruction?

 MAR = PC, PC+1, Assert MAR
 IR = MBR, decodes IR
 put addr 7000 into MAR, Assert MAR
Move MBR to R1
MAR = PC, PC+1, Assert MAR
IR = MBR, decodes IR
 put addr 7001 into MAR, Assert MAR
 Move MBR to R2
 MAR = PC, PC+1, Assert MAR
  IR = MBR, decode IR
 R1 = R1 + R2
MAR = PC, PC+1, Assert MAR

Microcode instruction sets typically have more fields than ordinary instruction sets.

Sometimes this is called wide word, as a very long instruction can offer access to multiple hardware components in the same cycle for many operations to be performed in parallel.

In simpler microcoded systems, instead of being wide in the extreme, the numerous (smaller) fields offer access to simple operations (though still in parallel), like read from memory, write, transfer one register to another, etc..

We also generally won't see overlapping fields in microcoded instruction sets, like we do with normal instruction sets.   Look at MIPS for example, which has half a dozen different instruction forms, like J-type and R-type where the fields overlap and the hardware decides how the fields are to be interpreted based on the instruction type.

In microcode, you just use the fields you need in each microcoded instruction, instead of choosing a different instruction type.  This keeps the micro-machine simpler, at an expense of either needing a wider microcoded instruction set, or having fewer micromachine features, like fewer micromachine registers and/or hardware units (like adders).

Because of the large number of instruction fields in each microcoded instruction, we can expect multiple operations per instruction.

In your example, I think we can assume the following are all encoded in a single instruction:

MAR = PC       // transfer PC to address bus
PC = PC + 1    // increment PC register
IR = MBR       // transfer data bus to IR register
Assert MR      // assert memory read

And it looks like the "put addr 7000 into MAR, Assert MAR" is a programming comment associated with this instruction.

N.S. Matloff
 has a description of a 32-bit microcoded instruction set that looks roughly like what you're showing.  You can see the large number of fields, and also that by comparison to a normal instruction set.  There are fields of the instruction for branching, fields for alu operation, register source & target, memory access, etc..  These fields exist in every instruction; there are no overlapping fields as there is only one instruction type.