Upper bound for set disjointness under product distributions For the set disjointness problem in the 2-party model of communication complexity, Alice is given an input $X$ and Bob is given input $Y$, $X$ and $Y$ are $n$-length bitstrings (sampled from some distribution), which are interpreted as subsets of $[n]$, i.e., $X_i=1$ means the $i$-th bit of $X$ is in the subset. The goal is for Alice and Bob to answer whether the subsets represented by $X$ and $Y$ are disjoint by using as little communication as possible. It is known that $\Omega(n)$ bits are necessary in the worst case for randomized protocols.

I came across this draft of the textbook Communication Complexity by Anup Rao and Amir Yehudayoff, where Exercise 6.8 mentions that 2-party set disjointness can be solved with an expected number of $O(n^{2/3}\log^2 n)$ bits if the inputs of Alice and Bob are sampled independently.

  Consider the following protocol. If there is a coordinate $j \in [n]$ such that $H(X_j)$ and $H(Y_j)$ are both at least $\epsilon$, then Alice and Bob communicate $X_j,Y_j$. They condition on the values that they see and repeat this step until no such coordinate can be found. At this point, Alice and Bob use Shannon’s coding theorem to encode $X$, $Y$. Show how to set $\epsilon$ so that the expected communication can bounded by $n^{2/3} \log^2 n$. Hint: Use the fact that $H(X_j ) \ge \epsilon$ implies that $Pr[X_j = 1] \ge \Omega(\epsilon/(\log(1/ε)))$.

I suppose the idea is to first communicate all indices where $X$ and $Y$ have large entropy and then use the fact that the remaining indices must have small entropy. However, the details of the protocol and where the independence of $X$ and $Y$ is coming in, aren't clear to me.

During the first phase of the algorithm, the players zoom in on a high-entropy coordinate. They exchange $O(1)$ bits, and stop at each step with probability $\Omega(\epsilon^2/\log^2(1/\epsilon))$ (here we use independence). Hence this phase uses up at most $O(\log^2(1/\epsilon)/\epsilon^2)$ bits in expectation. The second phase uses $O(n\epsilon)$ bits. In total, we used this many bits in expectation:
$$
O(\log^2 (1/\epsilon)/\epsilon^2 + \epsilon n).
$$
Choose $\epsilon = 1/n^{1/3}$ to obtain the stated bound.

Without independence, we don't have any control on the stopping probability at each step of the first phase. For example, it could be that $X$ is sampled uniformly at random, and $Y$ is the negation of $X$. In this case the first phase will never stop, and so the protocol will always use $2n$ bits.

As an aside, the upper bound can be improved to $O(\sqrt{n} \log n)$, which almost matches the lower bound $\Omega(\sqrt{n})$ (the gap might have been closed in the literature). See lecture notes of Prahladh Harsha.


Is Graph 2-Coloring NP-Complete? I know there is a polynomial time algorithm for 2-coloring. But should the answer be "No" or should it be "Maybe"?
Since 2-coloring is in NP and we dont know if there is a reduction of any NP-complete to 2-color.

Since graph 2-coloring is in P and it is not the trivial language ($\emptyset$ or $\Sigma^*$), it is NP-complete if and only if P=NP.


Modifying Floyd–Warshall Algorithm for Vertex Weights I was trying to modify the Floyd–Warshall's algorithm to take into account the weights over the vertices, in addition to the weight of the edges, while computing the shortest path. The length of a path from vertex A to an adjacent vertex B, Path(A,B) , is defined as:

     Vertex_Weight(A) + Edge_Weight(AB)

For a vertex A:

      Path(A,A) = 0

I was wondering if the Floyd–Warshall can be modified to handle this, and in particular if the following idea will work:

  The weight on a vertex V can be added to the weights of all the
  outgoing edges from V. Thus new edge weight Edge_Weight' is:

      Edge_Weight'(AB) =  Vertex_Weight(A) + Edge_Weight(AB)

  One can transform the original graph with the vertex weights to a
  graph without vertex weights, where the edge weights are modified as
  above. The normal Floyd–Warshall can be applied now.

If anyone could envisage a scenario where this might not work or if anyone knew of a better way, I would be thankful.

"I was wondering if the Floyd–Warshall can be modified to handle this, and in particular if the following idea will work."

Yes, your cool idea works! In fact, other people have found the same cool technique of including vertex weight in the new edge weight. By the way, I would not say you have modified the Floyd-Warshall algorithm. It is better to say that you have adapted the problem brilliantly so that Floyd-Warshall algorithm can be applied flawlessly.

"If anyone could envisage a scenario where this might not work or if anyone knew of a better way, I would be thankful"

It looks like there is little chance for you to become thankful by that cause.


Which type of computer programs could be called intelligent agents? I know some computer programs can be modeled as intelligent agents, for example a chess program which plays against a human. The environment is the chess board stored in the memory and actuators are commands to move a piece. Another intelligent program may react to the user commands.

My question is could any computer program be regarded as an intelligent agent? for example a media player, or a simple calculator?

If no, which characteristics a program should possess to be called an intelligent agent?

This is (obviously) up for debate. If you speak about agents, one common definition of agents is:

autonomy: agents operate without the direct intervention of humans or others, and have some kind of control over their actions and internal state;
social ability: agents interact with other agents (and possibly humans) via some kind of agent-communication language [Genesereth and Ketchpel, 1994];
reactivity: agents perceive their environment, (which may be the physical world, a user via a graphical user interface, a collection of other agents, the INTERNET, or perhaps all of these combined), and respond in a timely fashion to changes that occur in it;
pro-activeness: agents do not simply act in response to their environment, they are able to exhibit goal-directed behaviour by taking the initiative.

There is also the BDI model using the concepts belief, desire and intention for intelligent agents.

If you go further away from "agents" (this term has a specific meaning in computer science as it's also part of a software engineering paradigm) to "what makes a piece of code intelligent?" You'll see that every research area will give you a different answer. Artificial intelligence distinguishes between hard and soft AI. Neuroinformatics takes its answers from cognitive science, importing the definitions that biopsychology and neuro science give about cognition and what makes a being "intelligent". A philosopher will also have a different definition.

These definitions all have some common ground but in the end there is no ultimate definition everybody can agree on.


Designing CFG that accepts $b^m a^n$ ($m ≤ n$) I am trying to design a CFG that generates the language $\{a^k b^m a^n a^k \mid m \leq n\}$. However, I am having trouble with the $b^m a^n$ where $m \leq n$. How do I solve this?

You can write this language as
$$
\{ a^k b^m a^m a^\ell a^k \mid k,m,\ell \in \mathbb{N} \}.
$$
This description easily lends itself to conversion into a context-free grammar.


How to define an approximation algorithm when it fails? I have an NP-hard problem P where we are trying to minimize some objective function subject to some constraints. Problem P is very hard in the sense that even finding a feasible solution is NP-hard! (i.e., finding a solution that satisfies the constraints is NP-hard).

Let OPT denotes the optimal algorithm for P. That is, OPT will return, given an instance of P, the best possible solution, or will report none exist. Now, suppose I designed an approximation algorithm, denoted ALG, that solves P (of course not to optimality).

Given an instance I1 of P, ALG may fail to find a feasible solution when actually one exists and of course OPT finds it. So, if I would like to measure the performance of ALG in terms of its approximation ratio, how would I do that? Should I ignore the instance I1? As far as I know, an approximation algorithm, by definition, must return, for any instance of the problem, a solution that has a bounded value compared to the optimal value. But in this case, given an instance of P, ALG may not be able to find any value and hence reports none.

For short, if an algorithm fails to find a solution to a problem, how do we measure its performance ratio? Is it even considered an approximation algorithm? Is there something related to this in the literature?

The usual way out in such circumstances is bicriteria approximation algorithms. Suppose that given a set of possible solutions $S$, a constraint function $f$, and an objective function $g$, your goal is to find a solution $x \in S$ such that $f(x) \leq 1$ minimizing $g(x)$. A bicriteria approximation algorithm will find a solution $x \in S$ such that $f(x) \leq \alpha$ and $g(x) \leq \beta \mathrm{OPT}$, where OPT is the optimal solution to the original problem.

The quality of bicriteria approximation algorithms is thus measured by two parameters. The parameter $\beta$ corresponds to the approximation ratio, and $\alpha$ controls by how much the solution violates the constraints.


BosonSampling: $\# P \subseteq FBPP^{{NP}^{\mathcal{O}}}$ implies $P^{\#P}\subseteq BPP^{{NP}^{\mathcal{O}}}$ I am a complexity beginner, actually a quantum physicist.

In their famous BosonSampling paper, Aaronson and Arkhipov show amongst other things a polynomial time machine solving the problem of BosonSampling exactly, would result in the collapse of the Polynomial Hierarchy.

If you are not familiar with BosonSampling or any quantum physics at all, do not bother, it won't be necessary for this question: I am interested in one particular aspect of the argument, that I do not understand because of my lack of background: It seems to have to do with the relation of function/search problems and corresponding(?) decision problems.

Specifically, on page 33, in the the proof of Theorem 1, they show that a #$P$-hard problem is also contained $FBPP^{{NP}^{\mathcal{O}}}$ where $\mathcal{O}$ is an oracle to some problem called BosonSampling. From there, they immediately seem to get that
$$P^{\#P}\subseteq BPP^{{NP}^{\mathcal{O}}}$$

My question is: How? I understand that there is a difference between counting/function problem complexity classes like $\#P$ or $FBPP$ and classes for decision problems. But how to relate the results? In particular, why is it $P^{\#P}$ on the left?

I'm not an expert, and I have one blank space in my answer, hope someone might fill it in.

  $FBPP$ is the class of search problems $R = (B_x)_{x\in\{0,1\}^*}$ for
  which there exists a probabilistic polynomial-time algorithm $A$ that, given $\langle x, 0^ {1/\varepsilon}\rangle$ as input, produces an output $y$ such that $Pr [y \in B_x] ≥ 1 − \varepsilon$, where the probability is over $A$’s internal randomness.

Suppose that $L$ is a $\# P-$hard problem, and $L \in FBPP^{NP^{\mathcal{O}}}$. Then, $$P^{\# P} \subseteq P^{L} \subseteq P^{FBPP^{NP^{\mathcal{O}}}} \subseteq BPP^{NP^{\mathcal{O}}}$$

The second inclusion is clear. The first inclusion: suppose $L_1 \in P^{\# P}$. It means that there exists some polynomial algorithm $\mathcal{A}$ which makes queries to some functions $f_1, f_2, \ldots$ from $\#P$. By the definition of $\#P-$hard problems, $f_i \in FP^{L}$, where $FP$ is the class of polynomially computed functions $f:\{0,1\}^*\rightarrow \{0,1\}^*$. It means that every $\mathcal{A}$'s query to $f_1, f_2, \ldots$ can be replaced by a polynomial program with (at most polynomial) number of queries to $L$, or simply speaking  $\mathcal{A}$ is equivalent to some polynomial program $\mathcal{B}$ with queries to $L$. We've shown
$$P^{\#P} \subseteq P^{FP^{L}} = P^L$$
We see that $P^{FP}$ can be replaced by $P$.

The third inclusion: again, the same trick: here $P^{FBPP}$ turns to $BPP$. Suppose $L_2 \in P^{FBPP^{NP^{\mathcal{O}}}}$ and $\mathcal{A}$ is the corresponding algorithm for $L_2$. $\mathcal{A}$ makes at most $p(n)$ queries to the probabilistic polynomial programs $A_1, A_2, \ldots$ which solve some search problems. $\mathcal{A}$ uses randomness, but always gives the right answer. One can supposedly make $A_1, A_2\ldots $ a part of $\mathcal{A}$; the resulting probabilistic polynomial algorithm $B$ with queries to $NP^{\mathcal{O}}$ never errs and belongs to $BPP^{NP^{\mathcal{O}}}$.

The only doubt that I have here is that there might be a polynomial number of queries to different functions $FBPP$, and $\mathcal{B}$ is supposed to know all the algorithms for them. It is widely known that if $\mathcal{C}$ is a complexity class with a complete problem $\mathcal{L}$, then $A^{\mathcal{L}} = A^{C}$ for class $P$. However, $BPP$ doesn't have complete problems, and I'm not sure about $FBPP$.


Is s-grammar powerful enough to generate all possible DCFL? In s-grammar all productions are in form of A →  , A∈V , a∈T , ∈V*

  "... and any pair (A, a) occurs at most once in P." [P. Linz, 6th ed. , p. 144]

s-grammar is Unambiguous and i think (not sure) we can describe all Unambiguous-CFL by s-grammar. I want to know can s-grammar describe all possible DCFL or not ? according to this sentence, I think we can't do it but i'm not sure about that:

  Unfortunately, not all features of a typical programming language can be expressed by an s-grammar. [P. Linz, 6th ed. , p. 152]

but all languages which described by an s-grammar is Deterministic.

I say this, because we can made 2-state DPDA for any simple-grammar with this definition:

R ≝ Production Rules of CFG
(x,y,"LBL") is a labeled-edge between x and y with “LBL” as a label
∀r∊R: r= (A,aⱰ) ( A∊V ⋀ a∊T ∧ Ɒ∊V*) add (q,q,"a,A/Ɒ") to E
Add (q,q,"ε,z/Sz′") to E
Add (q,f,"ε,z′/z′") to E

if there is any DCFL that we can not provide an s-grammar for it , show me that please and correct me if i'm wrong.

Thanks.

Actually the example of a language not accepted can be quite simple, due to a technicality. The language $a^*$ is not generated by a s-grammar.

In fact, an s-grammar cannot generate $\varepsilon$. In order to remove $S$ from the stack we have to apply at least one production, and any production will produce a terminal symbol.

But even if we see this as a technicality, we cannot generate two strings, one of which is the prefix of another. If we can generate a string $\alpha$ which then is accepted because all veriables have been rewritten (the stack only contains the new $z'$), then how would we generate a longer string $\alpha\beta$? It must follow the same computation initially.

This is the case because the PDA you produce is actually a PDA with empty stack acceptance: when the stack is empty (or actually only has $z'$) we must accept. It is well known that deterministice PDA with empty stack acceptance can only generate prefix-free languages. Addingan end-of-string marker is usually the remedy.

The real-time property (reading a symbol every step) is a larger problem.
Consider the language $\{ a^i b^j c^i \mid i,j \ge 1\} \cup \{ a^i b^j d^j \mid i,j \ge 1\}$. It can be accepted by a DPDA. push $a$'s, push $b$'s. Then when reading a $c$ we pop the $b$'s and compare the $a$'s and $c$'s. Otherwise when reading a $d$ we compare the $d$'s with the $b$'s using the stack. Thus you need popping of stack symbols without reading input. A real-time PDA cannot do that (and neither the s-grammar). The source I know for this refers to Autebert, Berstel, Boasson: Context-Free Languages and Pushdown Automata in the Handbook of Formal Languages.

Of course the PDA has only a single state. I do have to check: it seems that also the single state restriction reduces the languages accepted.


decision tree redundancy optimization First question in the computer science section. I am currently working on a solution that optimizes decision tree redundancy.

the following is an example of optimization:

|  D1   |   D2   | Outcome |
| true  |  false |   Yes   |
| false |  false |   No    |
| true  |  true  |   Yes   |
| false |  true  |   No    |

when optimized gives:

|  D1   |   D2   | Outcome |
| true  |   -    |   Yes   |
| false |   -    |   No    |

I need to program this optimization. My decision tree will be different from the one that is shown here. I will have a string outcome, that is in no way a function of the input, and my input will contain 5 different possible inputs. boolean, string, int, double and datetime data types will also be present. Data in the input fields will be expressed using FEEL format.

What I want to know is if there already is a known algorithm for optimizing decision tables like these, or should can I expect to work this out by myself. I don't want to reinvent the wheel here, since this is quite a challenging project. An answer from the stackexchange forum suggested that I post here. He suggested that I start with the Quine–McCluskey algorithm. I looked into this, but it seems like that it's calibrated for boolen based decision tables.

Currently I am considering an approach like the flowing:

If there are no duplicate outcomes, stop process
Select rules with duplicate outcomes
See which decisions are redundant by grouping/merging them
etc

I am to write the code in C#

EDIT:
Most inputs will be comparable to a degree. For instance, a string input will be one from a set of strings, and number values will fall in a certain range. But there is no guarantee they always will be.

The ID3 algorithm is one standard way to construct a decision tree.  You can also look at successors like C4.5 and others.  These aren't guaranteed to give the smallest possible decision tree (that is known to be NP-hard) but the decision tree it outputs is often fairly reasonable.


Return course order with class prerequisites Question:
Given Input: Courses and their dependencies(prerequisites)
such as A < B; A < C; B < D; C < D return course order in the order a student can take. i.e answer should return A, B, C, D or A, C, B, D

I solved the problem, but the running time is very slow, I cannot seem to figure out how to improve my algorithm. FYI: This isn't for schoolwork or project, just curious.

Answer:

  function getCourseOrder(input) {
  let result = [];

  while(Object.keys(input).length !== 0){
    for (let item in input) {
        let depencies = input[item];

        if (!depencies || depencies.length === 0) {
          delete input[item];
          result.push(item);
          continue;
        }

      let hasAlreadyTakenClasses = depencies.every((currentValue) => {
        return result.indexOf(currentValue) > -1;
      })

      if (hasAlreadyTakenClasses) {
        delete input[item];
        result.push(item);
      }

    }
  }

  return result;
}

var input =  {a: [], b: ['a'], c: ['a'], d:['c','b'] }

As pointed out in a comment, the problem you are trying to solve is an instance of the more general problem of finding a topological sorting of a particular set.
In your case, the ordering is given by the "being a prerequisite of" relation.
At the implementational level, switching your dictionary with an adjacency matrix may improve the runtime.


Kolmogorov complexity of a decision problem What's the definition of Kolmogorov complexity for a decision problem? For example, how to define the length of the shortest program that solves the 3SAT problem? Is it the "smallest" Turing machine that recognizes the 3SAT langauge?

We can view of a language $A$ as an infinite binary string (the infinite binary string corresponding to the characteristic function of $A$) and then use the notion of Kolmogorov complexity for such strings.

Google for: Kolmogorov complexity infinite words


On the hardness of satisfying K number of linear constraints Background: Normally in linear programing we have some objective function
$$\text{maximize}\sum_{i = 1}^n a_i x_i $$
$$\text{subject to} \sum_{i =1}^n b_{ji}x_i \leq c_j \text{ for all } 1 \leq j \leq m$$
where $a_i, b_{ji}, c_j$ are all constants given in the problem statement and each $x_i$ is an optimization variable which we may choose the value of. Note that the above problem may not have a feasible solution if all of the linear constraints cannot be satisfied at the same time. Determining if the constraints are satisfiable and optimizing the objective function can both be done in polynomial time.

Problem Statement: Consider a slightly modified version of the above problem where we don't care about the optimization function and are just given the set of constraints

$$\sum_{i =1}^n b_{ji}x_i \leq c_j \text{ for all } 1 \leq j \leq m $$
We are interested in answering the question "can at least $k$ of these constraints can be satisfied?".

This feels NP-Hard as it it seems to amount to a combinatorial selection problem in the sense that we are now selecting a specific set of $k$ items out of $n$ possible items, and there could only be one such set of $k$ items that works.

Question: Is this problem NP-hard, what if we impose $0\leq x_i \leq 1$ for all $i$? If so, what problem could be used to construct a good reduction?

As j_random_hacker suggested, we can reduce MAX-2-SAT to this problem.

Given an instance of MAX-2-SAT with $n$ variables $x_1,\ldots,x_n$ and $m$ clauses, we can encode it as the following constraints:

For each variable $x_i$, add $m$ identical constraints: $x_i\le 0$ (if identical constraints are not allowed, we can use $x_i\le 0,x_i\le 0.1,x_i\le 0.01,\ldots$ instead) and $m$ identical constraints: $x_i\ge 1$.
For each clause, say $x_i\vee x_j$, add a constraint $x_i+x_j\ge 1$. If a negative literal is involved, for example, $x_i\vee\neg x_j$, then the constraint becomes $x_i+(1-x_j)\ge 1$.

Now we can conclude that there exist $nm+k$ constraints that can be simultaneously satisfied if and only if there exist $k$ clauses that can be simultaneously satisfied in the MAX-2-SAT instance.


Why is Scale Space Needed to Detect Scale Invariant Features? I have been doing research on the SIFT (scale invariant feature transform) algorithm, and while I have repeatedly read that in order to detect image features that do not vary with respect to scales of visual perspective, a scale space must be constructed from the source image using repeated Gaussian smoothing and taking differences of those Gaussians. Then local extrema are found in the four dimensional scale space which are designated as scale invariant key points. How this process is performed seems straightforward, but my question is why does this process work at all? What is special about the Gaussain blur that allows us to do this? In the publications that I am reading (listed below), the reason this works is not clear to me.

Lindeberg, Tony. “Detecting Salient Blob-like Image Structures and Their Scales.” Scale-Space Theory in Computer Vision (1994): 249-70. Web.
http://www.nada.kth.se/~tony/abstracts/Lin92-IJCV.html

Lindeberg, Tony. “Scale-space.” Encyclopedia of Computer Science and Engineering. Vol. 4. N.p.: n.p., n.d. 2495-504. Web. 16 Oct. 2016.
ftp://ftp.nada.kth.se/CVAP/reports/Scale-Space-EncCompSci.pdf

Lowe, David G. “Distinctive Image Features from Scale-Invariant Keypoints.” International Journal of Computer Vision 60.2 (2004): 91-110. Web.

EDIT

I have read many high level explanations of this concept, which generally say that as the sigma of the Gaussian increases, fine grained features should be suppressed and that coarse grained features should be generalizations of fine grained features. But I am looking for a more rigorous and possibly mathematical explanation of why this is the case.

If a maximum is found at a given octave X in the original image, then, if we have the scale-invariant property, this maxima will be found on the zoomed down (downscaled) image at octave X-1.


Evaluation of $\beta$-Reduction with Parentheses in $\lambda$-Calculus I'm studying $\lambda$-calculus, and had a question regarding an exercise I came across. I understand that $\lambda$-calculus uses three main strategies of evaluation, but I'm having trouble applying it. Specifically $\beta$-reduction.

For example, for $1 + 2$:

\begin{align}
1 + 2 & = \lambda n.\lambda m.\lambda s. \lambda z. m\ s\ (n\ s\ z)\ 1\ 2 \\
& = \lambda s. \lambda z.\ 2\ s\ (1\ s\ z) \\
& = \lambda s. \lambda z.\ 2\ s\ ((\lambda s. \lambda z.s\ z)\ s\ z) \\
& = \lambda s. \lambda z.\ 2\ s \ (s\ z) \\
& = \lambda s. \lambda z.(\lambda s. \lambda z. (s\ (s\ z))\ s\ (s\ z) \\
& = \lambda s. \lambda z.s\ (s\ (s\ z)) \\
& = 3
\end{align}

The particular part that I'm having trouble understanding is the $\beta$-reduction at the last step before deriving the final $\lambda$ expression. More specifically, how $\lambda s.\lambda z. (s\ (s\ z))\ s\ (s\ z)$ reduces to $s\ (s\ (s\ z))$.

My understanding is that in order to perform $\beta$-reduction, we need to identify redexes of the form $(\lambda x.e_1)\ e_2$. Using this understanding, my initial approach would be:

\begin{align}
\lambda s. \lambda z. (s\ (s\ z))\ s\ (s\ z) & = [\lambda s. \lambda z. (s\ (s\ z))\ s]_{redex}\ (s\ z) \\
& = \lambda z. (s\ (s\ z))\ (s\ z) \\
& = [\lambda z. (s\ (s\ z))\ s]_{redex}\ z \\
& = s\ (s\ (s\ z))
\end{align}
Is my approach correct? If so, is it valid for me to drop the parentheses arbitrarily as I did in the third line?

You are missing one important pair of parentheses, around an expression for $2$. It should be
$$\bigl(\lambda s. \lambda z. (s\ (s\ z))\bigr)\ s\ (s\ z)$$
Then we reduce by replacing $s$ with $s$ and $z$ with $(s\ z)$, obtaining
$$(s\ (s\ (s\ z)))$$

On the other hand, $\lambda s. \lambda z. (s\ (s\ z))\ s\ (s\ z)$ doesn’t reduce any further because it has no redex. It is just a $\lambda$-abstraction with variables $s,z$ and body $(s\ (s\ z))\ s\ (s\ z)$. Abstraction always goes as far right as possible.

Generally, when we have a name for expression (e.g. $2$, $myexp$,...) within some larger expression, we must surround it with parentheses when we expand it to its true lambda form, to avoid confusion regarding applications.
Just like you did with $1$ in the third row.

You can explore $\lambda$-calculus reductions, test your ideas and see how various expressions are implemented with this interpreter.


Algorithm Analysis of Three nested loop I'm trying to figure out Time function and Big O of a nested loop code,

public static int example5(int[ ] first, int[ ] second) { // assume equal-length arrays
  int n = first.length, count = 0;
  for (int i=0; i < n; i++) { // loop from 0 to n-1
    int total = 0;
    for (int j=0; j < n; j++) // loop from 0 to n-1
      for (int k=0; k <= j; k++) // loop from 0 to j
      total += first[k];
  if (second[i] == total) count++;
}
  return count;
}

According to my calculations the time function should lie in $n^4$, but the right answer is $n^3$.
Here are my solution steps,

Constant operations = 2 times
i-loop = 0 to n-1 = n times (although it's 2n+2, but I would pick the most higher order term)
Constant operation = 1 time
j-loop = 0 to n-1 = n x n times = $n^2$ times
k-loop = 1+2+3+...+n-1+n = n x n x $n\frac{n+1}{2}$ times = $\frac{n^4 + n^3}{2}$ times

What I'm doing wrong, can someone please point out.

Three for loops gets you to n^3.

EDIT:

for (int i=0; i < n; i++) // first n
..etc..
for (int j=0; j < n; j++)  // second n
...etc...

Outer two are n, that makes n^2 so far. Next look at inner loop:

for (int k=0; k <= j; k++) // third n

Innermost counts as another n for big O purposes even if running k to j instead of k to n. You're still on the order of n^3.

For that inner loop you're doing 1 + 2 + 3 ... loops as j iterates, so strictly speaking it's not exactly n^3 iterations, but n * n * (n+1)/2, but for big O purposes don't let that throw you off, it's n^3, the (n+1)/2 piece is just another layer of n. If n was 1,000,000 you'll end up with "on the order of" 10^18 loops.

Hope this helps.


Turing machine decides languages in RE Given this language:
$$L_{s_1,s_2} = \{ \langle M_1 \rangle \langle M_2 \rangle | L(M_1) \in S_1 \text{ and } L(M_2) \in S_2 \}$$
I want to prove that for $S_1=RE$ and  $S_2=RE$, then $L_{S_1,S_2} \in R$.

The way I started was by trying to build a Turing Machine that decides $L_{S_1,S_2}$:

Let $M_{12}$ be that Turing machine.

For each input word $w$:
If $w$ cannot be decoded as $\langle M_1 \rangle \langle M_2 \rangle$ then halt and reject.
Run $w$ on both $M_1$ and $M_2$.
If one of the two machines above halted, then $M_{12}$ halts and accepts $w$.

And here I got stuck:

What if the two machines didn't stop over $w$? how should I halt and reject $w$ in $M_{12}$?

By definition, for every Turing machine $M$, $L(M) \in \mathsf{RE}$. Therefore your language can be rewritten as
$$
\{ \langle M_1 \rangle \langle M_2 \rangle : M_1,M_2 \text{ Turing machines} \}.
$$
This obviates some of the steps in your oddly named machine $M_{12}$.


Number of ways to bicolor a graph with some constriants Given a graph G, I need to find the number of ways to color it using two colors Black and White.
Constraints:

G will already have some nodes colored Black.
Every node of color White needs to have one or more Neighbors of color Black.

The nodes that are colored Black will always be leaf nodes.
Vertices<=32
Edges<=Vertices^2

If you only care about graphs with at most $32$ vertices then just list all possible colorings. They are only a constant number ($2^{32}$). For each of them you can decide in constant time whether it is valid according to your constraints.
If you care about graphs with any number of vertices, then the problem is a generalization of the problem of counting the number of dominating sets in a graph, which is #P-complete even for special classes of graphs.


Are cache contents specific to a process? Suppose the L1 cache is filled up with data from some process. Now CPU loads another process. Does the new process share cache contents? Or the cache has to be invalidated completely in each context switch?

It depends, there are several kinds of caches.

Some caches, known as PIPT (physically indexed, physically tagged) operate entirely on the physical address. The cache subsystem is independent of virtual memory, so it doesn't matter which process is accessing the cache: all processes share all cache entries.

Some caches, known as VIVT (virtually indexed, virtually tagged) operate entirely on the virtual address. In this system, a cache entry is only valid for a given process. There are several ways to ensure that a cache entry will not be used in the wrong process:

The operating system may flush the cache at each context switch. This requires no hardware support but is obviously inefficient unless context switches are rare.
The operating system may assign disjoint sets of addresses to distinct processes. This again requires no hardware support, but is a heavy burden on the operating system (it means that the MMU is effectively as a mere MPU (memory protection unit)).
The MMU and cache may contain an extra label which is set by the operating system to an identifier for the process that owns each page or cache entry. ARM and Intel call this label ASID (address space ID). Each cache entry is only valid for a virtual address with the matching label.
There are also VIPT caches (virtually indexed, physically tagged). The physical tagging ensures that the cache entry will only be served to a request for the correct chunk of memory. The virtual index means that if a page is shared at different addresses in different processes, the cache entries will not be shared.

See the “Address translation” section in the Wikipedia article for more information on these kinds of caches.

Cache types typically vary between processor families within the same processor architecture. Even on a given processor, data and instructions caches may have different types, as can L1 vs L2 (and more) caches.


Halting problem in EXP-complete I have some troubles understanding why the halting problem is in EXP.
In Wikipedia the following is written:

  It is in EXPTIME because a trivial simulation requires O(k) time, and the input k is encoded using O(log k) bits which causes exponential number of simulations. It is EXPTIME-complete because, roughly speaking, we can use it to determine if a machine solving an EXPTIME problem accepts in an exponential number of steps; it will not use more.

Why does encoding in $O(\log k)$ makes it exponential?
How can we reduce the other problems to our halting problem?

You are referring to the following problem:
$$H = \{ (\langle M \rangle, w, t) \mid \text{$M$ accepts $w$ in time at most $t$} \}$$
where $t$ is binary encoded. You should note this is not the (classical) halting problem, but, rather, the bounded version of the halting problem. The halting problem itself cannot be complete for $\mathsf{EXP}$ (or any other subclass of the recursive languages).

Now, to answer your question. First, notice that, because $t$ is encoded in binary, the input has length $|\langle M \rangle| + |w| + \log t$. To simulate $M$ on $w$ for $t$ steps we can use a universal TM, which takes time $O(t \log t)$. Since we are doing a worst-case analysis, we can afford to view $|\langle M \rangle|$ as constant. Also, because $t \in O(2^{p(|w|)})$ for some polynomial $p$, $\log t \in O(p(|w|))$. Hence, the input has size $O(|w| + p(|w|))$ while our simulation takes time $O(t \log t) \subset O(p(|w|) 2^{p(|w|)})$ and, in turn, $p(|w|) 2^{p(|w|)} \in 2^{\textrm{poly}(|w|)}$. This proves $H \in \mathsf{EXP}$.

Reducing a problem $P \in \mathsf{EXP}$ to $H$ is also very simple: If $P$ is decidable by $M$ in time bounded by a function $f \in 2^{\textrm{poly}(n)}$, then any instance $x$ of $P$ is a yes-instance if and only if $(\langle M \rangle, x, f(|x|)) \in H$, where $f(|x|)$ is given binary encoded. The time taken by this reduction is dominated by computing $f(|x|)$, which can be performed in time polynomial in $|x|$ (by first converting it to binary and then computing $f(|x|)$ in polynomial time).


How to prove that Inner product of two $n$ dimensional vectors requires at least $n$ many multiplications? Input : Two matrices $A$ and $B$ of size $n$ X $n$.

Compute : Matrix product $A$ X $B$.

Some of the known results about matrix multiplication are given below.

Brute Force : $O(n^3)$.

Nader H. Bshouty : at least $2.5$ $n^2 -$$o( n^2 )$ [over binary field] multiplications. A lower bound for matrix multiplication

A paper by Yijie Han :  Matrix Multiplication Algorithm by Yijie Han

After reading the paper above I come to know that lower bound for matrix multiplication reduces to the problem of finding inner product of two vectors. I know how to compute a inner product of two vector in a brute force way. So my question is

Question  : How to prove that Inner product of two $n$ dimensional vectors requires at least $n$ many multiplications ?.

Here is a proof in the real case. For general fields, this only gives a lower bound of $\lceil n/2 \rceil$, though the correct lower bound should indeed be $n$. For more, take a look at the monograph Algebraic complexity theory by  Bürgisser, Clausen and Shokrollahi.

Model

It will be easier to give a lower bound on computing the inner product of a vector with itself; this is a potentially easier task. Consider an arithmetic "straight-line" program for computing the squared norm $\sum_{i=1}^n x_i^2$. Such a program consists of the following operations: addition, subtraction, multiplication, division, all of which of the form $a \gets b \circ c$. We are also allowed to "load" input variables and arbitrary field constants. The final answer must be found in some variable. Since we don't care about space, we can assume that every operation assigns its output to a new variable.

For simplicity we will not allow division in what follows, though divisions can always be eliminated (this is a famous result of Strassen), without too much trouble.

Here is an example of such a program:

  $t_1 \gets x_1 \cdot x_1$

  $t_2 \gets x_2 \cdot x_2$

  ...

  $t_n \gets x_n \cdot x_n$

  $s_2 \gets t_1 + t_2$

  $s_3 \gets s_2 + t_3$

  ...

  $s_n \gets s_{n-1} + t_n$

The variable $s_n$ contains the inner product.

Normal form (1)

The first step is coming up with a program in normal form. Let $t$ be a variable occurring in the program. The value of $t$ is always a fixed polynomial in the inputs (if we allowed divisions, it could be a more general power series). We write $t$ as a sum $t = t^{(0)} + t^{(1)} + t^{(2)} + t'$, where

$t^{(0)}$ is a constant.
$t^{(1)} = \sum_i c_i x_i$.
$t^{(2)} = \sum_{i \leq j} d_{ij} x_i x_j$.
$t'$ consists of all monomials of degree larger than 2.

We will convert an arbitrary program into one which computes only the parts $t^{(0)},t^{(1)},t^{(2)}$, and furthermore contains no more "essential" multiplications than the original program; a multiplication is not essential if one of the operands is a constant. Since the output variable $o$ satisfies $o = o^{(2)}$, the new program also computes the squared norm.

The base cases are when $t$ is constant or an input variable. In both cases no computation is needed, since each part is either zero, a constant, or an input variable.

We replace the operation $a \gets b + c$ with the sequence $a^{(0)} \gets b^{(0)} + c^{(0)}$, $a^{(1)} \gets b^{(1)} + c^{(1)}$, $a^{(2)} \gets b^{(2)} + c^{(2)}$. Subtraction is similar.

The most interesting operation is $a \gets b \cdot c$, which we replace by the sequence

  $a^{(0)} \gets b^{(0)} \cdot c^{(0)}$

  $a^{(1')} \gets b^{(0)} \cdot c^{(1)}$

  $a^{(1'')} \gets b^{(1)} \cdot c^{(0)}$

  $a^{(1)} \gets a^{(1')} + a^{(1'')}$

  $a^{(2')} \gets b^{(0)} \cdot c^{(2)}$

  $a^{(2'')} \gets b^{(1)} \cdot c^{(1)}$

  $a^{(2''')} \gets b^{(2)} \cdot c^{(0)}$

  $a^{(2'''')} \gets a^{(2')} + a^{(2'')}$

  $a^{(2)} \gets a^{(2''')} + a^{(2'''')}$

The only essential multiplication is involved in computing $a^{(2'')}$.

It is routine to check that the new program indeed computes $t^{(0)},t^{(1)},t^{(2)}$ correctly for all $t$ occurring in the original program.

Normal form (2)

Consider the new program. It is not hard to prove by induction that for each original variable $t$,

$t^{(0}$ is a constant.
$t^{(1)}$ is a linear combination of inputs, i.e. of the form $\sum_i c_i x_i$.
$t^{(2)}$ is a linear combination of the results of essential multiplications (multiplications of the form $s^{(1)} \cdot r^{(1)}$).

In particular, if there are $m$ multiplications in the original program then there are $m$ essential multiplications in the new program, and so it is semantically equivalent to the following program:

Compute $2m$ linear combinations $\ell_1,\ldots,\ell_{2m}$ of the inputs.
Compute $m$ essential multiplications $p_i \gets \ell_{i_1} \cdot \ell_{i_2}$, for $1 \leq i \leq m$.
Output a linear combination $\sum_{i=1}^m c_i p_i$.

In fact, without loss of generality we can assume that $c_i = 1$.

Rank lower bound

Given a program computing the inner product $\sum_{i=1}^n x_i y_i$ using $m$ multiplications, we have shown how to obtain a representation
$$
\sum_{i=1}^n x_i^2 = \sum_{j=1}^m \ell_j r_j,
$$
where $\ell_j,r_j$ are linear combinations of the $x_i$. Replace $\ell_j,r_j$ with coefficient vectors of length $n$, say column vectors. The representation then implies the matrix identity
$$
I_n + S = \sum_{j=1}^m \ell_j r_j^T,
$$
where $S$ is a skew-symmetric matrix (we get $S$ since $x_ix_j$ can be represented in two ways for $i \neq j$). If we are working over the reals, then all eigenvalues of $S$ are either zero or pure imaginary, and so $I_n + S$ has full rank. The right-hand side implies that the rank is at most $m$, and we conclude that $m \geq n$.

When working over the complex numbers, we can have shortcuts such as
$$
(x_1 + ix_2)(x_1 - ix_2) = x_1^2 + x_2^2.
$$
The same method still shows that $n/2$ multiplications are needed, and indeed the optimal number of multiplications to compute the squared norm is $\lceil n/2 \rceil$.


How to apply the pumping lemma to $\{0^m 1^n \mid 2n \leq m \leq 3n, m,n \geq 0 \}$? I'm not really sure the how you would go about proving this language isn't regular with the pumping lemma:

$L= \{0^m 1^n | 2n \leq m \leq 3n, m,n \geq 0   \}$

Does this indicate that $S = 2$, so we start by by using a string $\geq 2$?

For pumping lemma proofs, we have to remember that only strings longer than the pumping length are guaranteed to be "pumpable" (if the language is regular). Unfortunately we don't (typically) know what the pumping length is, so we have to work a little more abstractly than picking a fixed length string.

In this case, given pumping length $p$, we can take the string $s=0^{3p}1^{p}\in L$ (i.e. we choose the string where $n=p$ and $m=3n=3p$). Now if $L$ were regular, we'd be able to divide $s$ up into three parts $s=xyz$ where:

$|xy|\leq p$
$|y| > 0$
$xyz \in L \Leftrightarrow xy^{i}z\in L $ for all $i\in\mathbb{N}$

So with our $s$, we know that $y$ must be a string of $0$'s, as $y$ is non-empty and is a subtring of the first $p$ characters.

Then if we pump up (never forget that pumping down is also a possibility - consider $0^{2p}1^{p}$) we get the string $s'=0^{3p+|y|}1^{p}$. As $|y|>0$, clearly $s' \notin L$, which contradicts the pumping lemma, therefore $L$ cannot be regular.


How can I take advantage of the capabilities of a cluster I'm developing a model in C, and I need to run a couple of simulations (lengthy, and heavy ones). I seem to have a cluster at my disposal, but I'm not very familiar with the concept. I understand that there are different "nodes" ? My program is not designed to take advantage of this individually - it can't event take advantage of multiple processors, because the calculations have to be done in sequence. But I have to run multiple instances of the program, and I was hoping there'd be a way to run them on separate "nodes" (?) to avoid them having to share CPU time too much.

What I know : the cluster runs Red Hat Enterprise Linux for Servers 5.3.

Can anyone help?

According to my experience, clusters usually work like this: you submit a job to it (a program), and it allocates a node to run your job. You don't worry about allocating the nodes yourself.

So in your case, simply submit multiple jobs (usually they provide some method to submit batch jobs), and the cluster will allocate different nodes to each of them.


Choosing $n$ points to get the closest sum Let's say there is a set of $N$ real numbers, $x_i, i\in\{1,2,...,N\}$, and we would like to choose $n$ points out of them to get the sum of the chosen points as close as possible to a certain number, $y$, i.e. minimising
$$
f(J) = \left[y - \sum_{j\in J}x_j \right]^2 s.t. ~J \subset \{1,2,...,N\} ~\mathrm{and}~ |J| = n
$$
To get the exact solution, I think this is an $NP$ problem, so is there any random algorithm to find the (approximate) solution reasonably fast?

Round the $x_i$ into multiples of $(\epsilon/n) N$ (for a parameter $\epsilon > 0$ of your choice) which we will denote by $y_i$, and use dynamic programming to solve your problem for the $y_i$ in time $O(n^2N/\epsilon)$, coming up with a set $J$. Since $\sum_{j \in J} |x_j - y_j| \leq \epsilon N$, this will go you the correct answer up to an additive error of $\epsilon N$.

(Ricky Demer suggested the same solution in the comments to the post.)


Different between left-most and right-most derivation I am a beginner started learning theoretical computer science. I just came through context-free grammars.

So my question is: what is the different between left-most and right-most derivation?

Because both of them gave me the same parse tree.

Given a derivation tree for a word, you can "implement" it as a sequence of productions in many different ways. The leftmost derivation is the one in which you always expand the leftmost non-terminal. The rightmost derivation is the one in which you always expand the rightmost non-terminal.

For example, here are two parse trees borrowed from Wikipedia:

The leftmost derivation corresponding to the left parse tree is
$$
A \to A + A \to a + A \to a + A - A \to a + a - A \to a + a - a
$$
The rightmost derivation corresponding to the left parse tree is
$$
A \to A + A \to A + A - A \to A + A - a \to A + a - a \to a + a - a
$$
The leftmost derivation corresponding to the right parse tree is
$$
A \to A - A \to A + A - A \to a + A - A \to a + a - A \to a + a - a
$$
The rightmost derivation corresponding to the right parse tree is
$$
A \to A - A \to A - a \to A + A - a \to A + a - a \to a + a - a
$$


Least squares fit of a 1D lattice of points to a 2D dataset Given a set of data points (shown in red), it is possible to fit a line $y = mx + c$ through the points using linear least squares regression.

I would like to modify this to fit a 1D lattice (grid) along the line such that $d$ is the offset of the the grid along the line and $i$ is the interval between neighboring grid points along the line.

An additional constraint is that more or less the same number of data points should be in the neighbourhood for each grid point in order to prevent picking an arbitrarily small $i$ and overfitting the data.

I believe that calculating the mean square error on a solution can be simple. The squared distances of all of the data points in the neighbourhood of the grid point would be:

$$mse = \sum_{j = 0}^{g} \sum_{k = 0}^{h} distance^2(\vec{latticePoint_j}, \vec{dataPoint_{j,k}})$$

(Where $g$ is the number of clusters and $h$ is the number of points inside the grid point's neighborhood.)

However, I'm not sure how to go about solving for all four variables $m$, $c$, $d$ and $i$ since I'm left with a discrete function. My hope is that since $i$ is fixed and points are distributed reasonably evenly among the clusters this could be done without invoking an overly complicated clustering algorithm.

The number of clusters are not known ahead of time and may contain outliers. Any help is much appreciated.

Define an objective function $\Psi(m,c,d,i)$ that specifies how "bad" a particular choice of values for $m,c,d,i$ are.  Then, use any standard black-box optimization algorithm (e.g., gradient descent) to find $m,c,d,i$ that minimize the objective function.  You might choose the initial values of $m,c$ based on a least-squares fit, and choose the initial values $d,i$ based on a best guess (maybe by projecting the points to the line $y=mx+c$ and then taking a FFT and looking for peaks, to try to find the periodicity), and then run gradient descent from there.

So, it all reduces to choosing an objective function $\Psi(m,c,d,i)$ that captures what you want.  We can't give that for you, since you haven't fully specified the problem.  For instance, you say you want "more or less the same number of data points" in each cluster, but you haven't specified how to trade off the errors: of course, we can't achieve this exactly, so we need some way to measure and compare different candidate solutions.

For instance, given a set $P$ of points, you might use an objective function like

$$\Psi(m,c,d,i) = \sum_{p \in P} d_{m,c,d,i}(p)^2$$

where $d_{m,c,d,i}(p)$ is the distance from $p$ to the nearest grid point on the line $y=mx+c$, i.e.,

$$d_{m,c,d,i}(p) = \min\{\sqrt{(p_x-x)^2 +(p_y-(mx+c))^2} : x=d + ij, j \in \mathbb{Z}\}$$

where $p=(p_x,p_y)$ in $(x,y)$-coordinates.

This doesn't do anything special about outliers; they incur a very large penalty.  That might be undesirable -- it might lead to poor results in the presence of outliers.  There are various methods for dealing with outliers.  One simple one is to fit a line using a robust least-squares fit, find outliers and remove them as part of a pre-processing step, and then run the procedure on the result.

Also, you mention fear of overfitting the data set. Another way to avoid overfitting is to add a regularization term that penalizes values of $d,i$ that are considered a priori unlikely.  For instance, you might add a penalty term that is proportional to $1/i$ or to $-i$.  The penalty term gets added to the objective function.  Then, when you minimize the objective function, this will exert some pressure to avoid choosing small values of $i$.


Evaluation functions of Minimax algorithm Let's say we have the following relationship between $f_1$ and $f_2$:

$$f_2(s) = \sqrt{1 + f_1(s)}$$

And $f_1$ returns a positive value. Why is it that minimax search using $f_2$ is guaranteed to the same action as using $f_1$ but is not guaranteed to return the same action as $f_1$ when used in expectimax search?

I understand that expectimax takes into account the weight of the arcs to compute the possible path. But I am still not able to understand how the aforementioned conclusion is being made.

An example for Expectimax (root node is a Max node):

(image from CSE AI Faculty / Dan Klein, Stuart Russell, Andrew Moore)

changing the evaluation function changes the action taken.

For Minimax, since $f_1(s_i) \ge f_1(s_j) \implies f_2(s_i) \ge f_2(s_j)$, the best node (action taken) doesn't change (Minimax is insensitive to monotonic transformations):


Ternary decision tree for the lower bound of comparison sort with 3-way comparisons All the proofs I've seen about the Ω(nlgn) lower-bound for comparison sorts use binary decision tress like this (from CLRS textbook)

Now what if each comparison yields strictly 3 outcomes, i.e. <, =, >? (the input array is allowed to contain repeated elements)

The bound is probably still Ω(nlgn), but I'm not sure how one would draw the (not necessarily full) ternary decision tree (still with unique leaf nodes); this kind of tree is mentioned in the proof of the water jug problem.

The proof would be exactly the same, using a ternary tree (where each internal node has three children) instead of a binary tree. A ternary tree of depth $d$ has at most $O(3^d)$ notes, so a sorting tree would have to satisfy $n! = O(3^d)$, which implies that $d = \Omega(n\log n)$.


Computing the closest point inside an intersection of half-spaces Is there an efficient way to compute, given a point, the closest point to it that's on the inside of an intersection of half-spaces?

For example, given the half-spaces a & b, the closest point to p that's "inside" the half-spaces is x. + denotes which side is "inside" the half-spaces a and b.

.p
       ^
       |
       |
       | x
   <---.--------------> b
       |       +
       |
       | +
       |
       v a

I'm particularly interested in an algorithm for half-spaces in 3D (planes)

My current line of thinking leads me to have to compute intersections of each half space, and then find the shortest point by picking from the shortest distance to each half-space and each intersection (line, point) that's within all the half-spaces. Is there a better way?

This can be modeled as a convex program
$$\begin{align}
\text{min.} \qquad & ||x-p||_2^2,\\
\text{s.t.} \qquad & Ax\leq b,\\
& x\in\mathbb{R}^3.
\end{align}$$
and solved (in reasonable time) by standard solvers. Here's example code in julia

using Convex, SCS

# generate random problem data
m = 5;  n = 3
A = randn(m,n); b = randn(m,1); p=randn(3,1)

# define problem
x = Variable(n)
problem = minimize(sumsquares(x-p), [A*x<=b])

# solve
solve!(problem, SCSSolver())
println("Status $(problem.status) distance $(problem.optval)")


How memory controller reads from RAM with O(1) time complexity? I am trying to understand how a RAM memory controller gets data with instant access while reading through the memory. Let's say initially, ram gets the data at address 0 and then to get the data at some random location like 1234, does it not have to loop through the first 1233 addresses before reaching 1234? Please explain. Thank you!

The RAM makes use of direct-memory-access, briefly this means that

  An element of data or instructions (such as a byte or word) can be
  directly stored or retrieved by selecting and using the
  locations on the storage media.

Now this can be happened with the use of a DMA controller, which bypasses CPU to transfer data directly between I/O device and memory.

If you want to understand precisely how this happens I suggest you read the book

  Operating System Concepts 10th Edition (Chapter 13)

I hope this helped you to understand why RAM gets instant access, comment below if you have more questions.


Reducing A(TM) to some decidable problem We know that A(TM) is undecidable, what if we reduce A(TM) to A(DFA) which is decidable? How will we prove that A(DFA) is decidable?

I couldn't find an example or theory.

Thanks

$A(TM)$ is undecidable because a Turing machine can fail to halt on its input. $A(DFA)$ is decidable since a DFA must always halt on any input. We can always decide whether a DFA accepts some string just by running the DFA on the string and seeing whether the DFA ends up in an accepting state. Not so with a Turing machine.

It is extraordinarily unlikely that there is a valid reduction of $A(TM)$ to $A(DFA)$; that would be a bit like effectively demonstrating that triangles have actually always had 3.5 sides, not 3. If you've got such a proof you should buy as many futures in mops as you can, since there will be a lot of brain matter to clean up after all the computer scientists' and mathematicians' heads explode.

I suspect the real question may really be more about whether proofs of the form "A reduces to B. B is decidable. Therefore, A is decidable." are valid. The answer is that, as you probably expect, of course they're valid: if you ever find yourself needing to prove a problem is decidable, this is the gold standard way to do it. If you've never seen a proof like this, per se, the reasons could be either that the default assumption is that problems are decidable until proven otherwise, or because this proof method is tantamount to just designing an algorithm to solve the problem (in which case, it might not appear to be a proof of anything so much as a description of an algorithm).

To give an example: consider Bubble Sort. This can be viewed as a proof that the Sorting problem is decidable, since it reduces $Sort$ to $\{GreaterThanOrEqualTo, Swap, Loop\}$, which we know are decidable. All right, there's some hand-waving there, but you get the idea.


why DFA to regex by two different methods differ I was learning converting DFA to regex.
I came across Arden's method which solve given DFA as follows:

Ardens method

Let us form the equations

$q_1 = q_10 + q_30 + є$

$q_2 = q_11 + q_21 + q_31$

$q_3 = q_20$

Solving the eq_uations

$q_2 = q_11 + q_21 + (q_20)1 = q_11 + q_2(1 + 01)$

$q_2 = q_11 (1 + 01)^*$

So, $q_1 = q_10 + q_30 + є$

$q_1= q_10 + q_11(1 + 01)^*00 + є$

$= q_1(0 + 1(1 + 01)^*00) + є$

$= є (0 + 1(1 + 01)^*00)^*$

$q_1=(0 + 1(1 + 01)^*00)^*$

So the regular expression for the given automata is $=(0 + 1(1 + 01)^*00)^*$

When I solved above using state reduction method I got different answer:

State Reduction method

So final regex was $0+11^*0(11^*0)^*0$

However this is different from what we get from Arden's method. Am I making any mistake?
Or both are correct?
If correct, is there any way to get same regex as Arden's using state reduction?
Does Arden's method gives shortest regex?
Any other observations about two methods?

No, these methods are not guaranteed to yield the shortest regexp.  Therefore, there's no reason to expect them to necessarily yield the same regexp.

Given a regexp $R$, finding the shortest regexp $R'$ that is equivalent to $R$ is known to be PSPACE-complete, by a result of Meyer Stockmeyer.  Consequently, none of these procedures can be expected to yield the shortest regexp.  If they did, then we could just take $R$, convert it to a NFA, then convert it back to a regexp $R'$ using that method, and we'd have an efficient way to find the shortest regexp, implying that P = PSPACE -- something that is not believed to be true.

(In fact, it's even hard to approximate, i.e., to find a regexp that is close to the shortest.)

To learn more, see On Learning Regular Languages on the CSTheory.SE blog.


Proving correctness of the algorithm for convex polygon minimum cost triangulation I have read many solutions for the minimum cost of triangulation problem and intuitively get the idea , however I am struggling to figure out how to prove it formally. I kind of feel that it has to be proven by induction but I struggle at choosing the right quantity to look at and also at the inductive step portion of the proof.

For example, can you provide a formal proof for the algorithm described here (page 5 problem 6.12).

There are two parts to understanding here.

The algorithm is a straight-forward implementation of equation (5) using memoisation.
Equation (5) is correct, that is $A[i,j]$ is

  the minimum cost triangulation of the polygon spanned by vertices
    $i,i+1,...,j$

as the author claims. They give a reasoning right there:

  Formulating the subproblem this way we are enumerating all the possible
  diagonals such that the diagonals do not cross each other. Since we are
  only considering in clockwise directions, diagonals generated by the
  subproblems can not cross each other.

They argue that

all feasible solutions are considered and
all considered solutions are feasible.

If this is true, then choosing the minimum out all considered solutions is clearly the correct answer. Proving the bullets now needs insight into the problem, and the author gives the basic idea.

In terms of an induction, what I sketch above amounts to the inductive step. The anchor is trivial and covered in the text. The induction hypothesis has to be phrased such that you know for $i,j$ fixed that all $A[i,k]$ and $A[k,j]$ for $k=i,\dots,j$ are optimal.


An algorithem for finding the number of primes of the form 4k+3 under some n I was given the task to make an algorithem that can compute the number of prime's of the form 4k+3 under some n, it should be able to compute how many number's of this type are there under 10^8 (100 million) in less than 10 minutes, any ideas?
Iv'e tried using variation's on the Sieve of Eratosthenes and lagranages method but the first was too slow and i didnt manage to have the second count only primes of the form 4k+3.

Here is a simple algorithm in Python that count the primes of the form $4k+3$ that are less than a positive integer $n$. It uses the standard sieve of Eratosthenes.
import math

def number_of_primes_4kp3(n):
    is_prime = [True] * n

    for p in range(2, int(math.sqrt(n)) + 1):
        if is_prime[p]:
            for j in range(p * p, n, p):
                is_prime[j] = False

    count = 0
    for i in range(3, n, 4):
        if is_prime[i]:
            count += is_prime[i]

    return count

print("n    ", "number of primes 4k+3")
for i in range(1, 9):
    count = number_of_primes_4kp3(10 ** i)
    print("10**" + str(i), count)

It takes about 20 seconds for the Python program above on an old Mac computer of mine to compute number_of_primes_4kp3(10 ** 8), returning 2880950.
When I use Java instead and only compute is_prime for odd numbers (which doubles the performance roughly), it takes less than half a second.


Solve Hamilton Circuit with Hamilton Path I want to show the reduction $HC \leq HP$.
Let $G=(V,E)$ be my undirected graph.

My idea is: For each edge $e=(u,v) \in E$ check whether $(V,E\backslash\{e\})$ has a Hamiltonian Path. If this is true for all edges, we have a Hamiltonian circuit in $G$.

It is pretty trivial to proof the first direction (when we have a Hamiltonian circuit in $G$, we will always have a Hamiltonian path in $(V,E\backslash\{e\})$ - independent from the edge we choose).

I really have trouble finding a formal proof for the other direction (either

$\forall e\in E$ Hamiltonian path exists in $(V,E\backslash\{e\})$  $\Rightarrow$ Hamiltonian circle exists in $G$ or
There is no Hamiltonian circle in $E$ $\Rightarrow$ $\exists e \in E:$ $(V,E\backslash\{e\})$ has no Hamiltonian path

Does a graph have a hamiltonian cycle if for anyone of its edges, it has a hamiltonian path after the removal of that edge?

Note that any hypohamiltonian graph must be such a graph. Is it even true that every hypohamiltonian graph has a hamiltonian cycle?

Not necessarily.

A counterexample is the Peterson graph, which is hypohamiltonian but not hamiltonian.


DFA of (aa+bb)(a+b)* + (a+b)*(aa+bb)? Our class teacher gave us a descriptive definition of a language in a Quiz today and ask us to make its DFA. In the middle of quiz he also told us the Regular Expression(RE) of that language but we still didn't make its DFA.

I am trying to make Deterministic Finite Automata (DFA) of this lang which is defined on alphabet={a,b} and all strings present in this language are either start or end on double letter i.e aa or bb. The RE is given in title.

I made a DFA by using Kleene Theorems but its pretty complex. How i can directly make a DFA.

The DFA starts by reading the first two characters. If they happen to be the same, then it goes to an accepting state and just stays there. Otherwise, it keeps track of the last two characters of the word being read, being in an accepting state whenever they are the same.

Instead of writing a state diagram, here are the Myhill–Nerode equivalence classes of your language (given as regular expressions), which can be converted into a DFA with the same number of states as the number of equivalence classes:

$q_0$: $\epsilon$.
$q_1$: $a$.
$q_2$: $b$.
$q_3$: $(aa+bb)(a+b)^*$.
$q_4$: $(a+b)^*aa \setminus (aa+bb)(a+b)^*$.
$q_5$: $(a+b)^*ab \setminus (aa+bb)(a+b)^*$.
$q_6$: $(a+b)^*ba \setminus (aa+bb)(a+b)^*$.
$q_7$: $(a+b)^*bb \setminus (aa+bb)(a+b)^*$.

The initial state is $q_0$, and the accepting states are $q_3,q_4,q_7$.

Here is the transition function:
$$
\begin{array}{c|cccccccc}
& q_0 & q_1 & q_2 & q_3 & q_4 & q_5 & q_6 & q_7 \\\hline
a & q_1 & q_3 & q_6 & q_3 & q_4 & q_6 & q_4 & q_6 \\
b & q_2 & q_5 & q_3 & q_3 & q_5 & q_7 & q_5 & q_7
\end{array}
$$


What is uniformity in Boolean circuits exactly? I have two questions on Kaveh's answer to Definition of uniform boolean circuit :

Kaveh mentions that the input is in unary encoding. In the definition it says the input is $1^n$, afaik $1^n$ is  a sequence of 1's repeated n times, but unary encoding is a sequence of 1's  and ends with 0 there is no power of 1 that gives 0... So how is $1^n$ a unary encoding?
Why do we use a unary encoding and not the binary encoding of n? what happens if we use binary instead?

Here is the binary encoding of 5: $$101$$ And here is its unary encoding: $$11111$$ Hopefully the difference is apparent.
Let's see what happens if we switch to binary encoding in the context of the linked question. Given the binary encoding of $n$, we need to produce a circuit, operating on $n$ bits, in logspace, and so in polynomial time. How much time do we have? The binary encoding of $n$ has length roughly $\log n$, so we have time $O(\log^C n)$, which isn't enough to produce a circuit which reads all input bits.
In contrast, if we use unary encoding, then the length of the input is $n$, and so we have time $O(n^C)$, which is more reasonable (in addition, we are only allowed to use $O(\log n)$ space).


How do the following Hash Functions compare? Consider the two hash functions used to map IP addresses. $x_i$ represents a octave (or "bit field") of the address.

Hash Function 1:
$$h_a(x_1, x_2, x_3, x_4) = \sum^{4}_{i=1} a_ix_i \bmod n$$

Where $n$ is a prime number closest to the total number of IP addresses being mapped. The probability of two IP addresses being mapped to the same bucket is $\frac{1}{n}$ using this hash function.

Hash Function 2:

$$h_a(x_1, x_2, x_3, x_4) = \sum^{4}_{i=1} x_i \bmod n$$

What would the probability to two IP addresses being mapped to the same bucket be using the second hashing function?

Your question is a bit confusing. These two "hashes" are incomparable.

The reason is that your second function is a specific hash function, while the first formulation is a family of hash functions  (indexed by $a$).

How can you compare the two? Choose $a$ in random and compare the two instances? Compare for the best/worst $a$, maybe? Compare on average (for a uniform $a$)?

Remark: Just to complete the details: Usually (at least, within the crypto-community), when people say "hash function" they actually mean a family of hash function, out of which you pick one instance uniformly. The properties of the hash function is (also) over the probability of selecting the specific function out of the family

As for your other question, the answer is no, in the second hash, the probability is not equal $1/n$ to be in each bucket. Assume that each $x_i$ is uniform in [0..255], then $x_1+x_2$ is not uniform in [0..510]. For instance $P(0)=1/256^2$ (both are 0) while $P(4) = P(0,4) + P(1,3) + P(2,2) + P(3,1) + P(4,0) = 5/256^2$. There's no reason that the sum will be uniform $\mod n$.

Last comment: As explained above, for the first hash, a probability of $1/n$ is over the choice of $a$.


Is this an unambiguous CFG that is not LR(k) for any k? The grammar is this:
$$S  \rightarrow  a B c $$
$$B  \rightarrow  b B b $$
$$B  \rightarrow \epsilon $$
The LR(1) states that I worked out were these
$$(1)$$
$$S \rightarrow .aBc$$
$\\\\$
$$(2)$$
$$S \rightarrow a.Bc$$
$$B \rightarrow .bBb$$
$$B \rightarrow .\epsilon $$
$\\\\$
$$(3)$$
$$B \rightarrow b.Bb$$
$$B \rightarrow .bBb$$
$$B \rightarrow .\epsilon$$
$\\\\$
$$(4)$$
$$B \rightarrow \epsilon.$$
$\\\\$
$$(5)$$
$$B \rightarrow bB.b$$
$\\\\$
$$(6)$$
$$B \rightarrow bBb.$$
$\\\\$
$$(7)$$
$$S \rightarrow aB.c$$
$\\\\$
$$(8)$$
$$S \rightarrow aBc.$$
The trouble seems to come primarily from state (3). In state (3) there is an S-R conflict on the lookahead of b. Also I feel that it makes the entire grammar not belong to any LR since on any lookahead of b...b, the same S-R conflict will exist. Is my reasoning correct?

Just as a slight nit, those aren't $LR(1)$ item sets, because they don't include the following terminal symbol
With that proviso, your reasoning looks good to me. Of course, the language is not inherently nondeterministic because you can rewrite $B$ as:
$$B \rightarrow \epsilon\,|\,Bbb$$
The palindrome language $L = \left\{ w w^R\,|\,w \in \Sigma^* \right\}, \left| \Sigma\right| > 1$ is the classic example of an inherently nondeterministic language. There exists an unambiguous grammar for $L$, but there is no $LR(k)$ grammar for any $k$.


If dynamically typed languages are truly statically typed, unityped languages, what is the (finite) type expression of the one type? Some claim that dynamically typed languages are in reality statically typed, unityped languages. This would imply to me that this one type should be expressible as a static, finite type expression, so can anyone provide such an expression? You can make whatever assumptions you need to make about the base types in the language, but please make sure the language would support types of unbounded size, e.g., lists, recursive types. It would also be nice if it supported records and variants, but whatever helps to illustrate the point will work. I'm also assuming that the language will be required to support some form of sum type, right?

This is entirely dependent on the language, and even on the implementation. The type would typically include entries for primitive functions, external library bindings (e.g. file handles), byte-compiled functions, etc. in addition to the data types of the language.

You can see a type like this in an interpreter for a dynamically-typed language written in a statically-typed language.

Here's an example of a type that's sufficient for a Logo value, showing that you don't need much to get started. Logo's values have a very simple structure: the only primitive type is the string, and the only structured type is the list. I use OCaml notation for the type.

 type logo_value =
   | Scalar of string
   | List of logo_value list

For example the logo value [3 [4 5]] is represented by the OCaml value List [Scalar "3"; List [Scalar "4"; Scala "5"]]

Here's an example of a type for an interpreter for a fragment of Scheme, again written in OCaml notation. Scheme is a larger language, with a range of primitive and structured types, functions as first-class values, and input/output objects.

type scheme_value =
  | Boolean of bool                (* #f, #t *)
  | Exact of Num.num               (* integers and rational numbers *)
  | Inexact of Complex.t           (* reals and complex numbers *)
  | Char of int                    (* Unicode characters *)
  | String of string               (* Strings (mutable, fixed-size) *)
  | Symbol of string               (* Symbols (immutable) *)
  | Cons of scheme_cons            (* Pair (mutable) *)
  | Vector of scheme_value array   (* Vectors (mutable, fixed-size) *)
  | Primitive of scheme_value list -> scheme_value   (* Primitive function *)
  | Lambda of string list * scheme_value             (* (argument names, body forms) *)
  | Port_in of in_channel          (* I/O port (input) *)
  | Port_out of out_channel        (* I/O port (output) *)
  | Eof                            (* (eof-object) *)
 and scheme_cons = {mutable car : scheme_value; mutable cdr : scheme_value}


How to create an LR($k$) grammar for a given language? How can I construct an LR($k$) grammar (which $k$ is not really of interest for now) for a given language, say:

$$L=\left\{w \in \{a, b\}^\star \ | \ \exists u \in \{a, b\}, v \in \{a, b\}^\star: w = vu \wedge |w|_u \operatorname{mod} 2 = 0\right\}$$

($|w|_u$ denotes the number of $u$'s in $w$).

Please note that I don't want a right or left linear grammar although I KNOW that the language is regular. I am interested in the process of creating an LR($k$) grammar for an arbitrary, in general more complex language. (Feel free to ignore this example.)

You question is very strangely stated. The answer is however very
trivial. Your language $L$ is a regular language, hence recognizable
by a DFA. It does not even need a pushdown stack. Hence it has to be
LR(k). Indeed, the lookahead is necessary only to make the recognition
deterministic, but in this case, it is deterministic to start with if
you use the DFA (this is a bit tautological, since building the LR
parser involve in general building a DFA, if my memory does not fail me)

You can get the LR grammar (if one dares calling it that, trivial as it is) just by taking the right-linear grammar
corresponding to the transitions of the DFA.

BTW, it is not easy to decide whether a given grammar is LR(k) for some unknown k, it is undecidable. But it is decidable when k is given, you just try to build the tables.

To answer your question about a procedure to build a LR(k) grammar for a given CF language, the answer is "sorry: not in this universe".

The reason is that it is undecidable whether a given CF language is deterministic or not. Since any deterministic CF language has a LR(k) grammar, if a procedure existed to produce a LR(k) grammar for a language, when possible, that would be a procedure to decide whether the language is deterministic. Since no such procedure can exist, we have no systematic way of obtaining an LR(k) grammar for the language.


A linear time algorithm to find the array of indices of bigger numbers Suppose you have an array nums of integers, unsorted, containing the values from 1 to n.  You have a second array, call it firstBigger, initially empty, which you want to populate with integers such that firstBigger[i] contains j if j is the least index such that i < j and nums[j] > nums[i]. A brute force search of nums runs in $O(n^2)$ time. I need to find a linear time search.

For example, if
nums        = [4,6,3,2,1,7,   5] and we use 1-indexing, then
firstBigger = [2,6,6,6,6,None,None].

I have considered first computing the array of differences in linear time. Certainly anywhere in the array of differences with a positive value, this indicates a place in firstBigger where it should store $i+1$. But I'm not seeing how to fill any other coordinates efficiently.

I might have gotten close when I started thinking of analyzing the array end-to-start.  The last $n$th coordinate of firstBigger is going to be None, the $n-1$th has to be directly compared to the $n$th. As we proceed backward, if the number at $i$ is smaller than at $i+$1 we make this assignment. Otherwise we look up the first number bigger than the one at $i+1$. If that's still too small, again look up the first number bigger than that.

On average this does better than the naive algorithm, but in the worst case it's still $n^2$.  I can't see any room to optimize this.

Let $A$ be an array with indizes $1$ to $n$.
We first build the array $B$ where $B[i] = j$ indicates that index $j$ has the highest value $A[j]$ in the first $i$ entries of $A$.
Then we build a list $L$ which has the numbers from $B$ in the same order but without duplicates in it.
Then we define the function $f$ as $f(i) = L[i+1]$ or none if $L[i+1]$ does not exist.
The final result is applying $f$ to $B$.

Let's look again at your example $A = [4,6,2,3,1,7,5]$.
Then $B = [1,2,2,2,2,6,6]$ and $L = [1,2,6]$.
Hence the function $f$ is $1 \mapsto 2, 2 \mapsto 6, 6\mapsto \textrm{none}$.
Applying $f$ to $B$ gives us $[2,6,6,6,6,\textrm{none},\textrm{none}]$.

Computing $B$ and $L$ runs clearly in linear time (for $L$ we only need to append values to a list at its end).
Applying $f$ takes linear time too, if done correctly:
Either you have an look up table as array of length $n$ (or hash map if you're ok with expected worst-case analysis).
Or you use the monotonicity of $B$ and use the list $L$ which you traverse in lock-step when traversing $B$.
This approach has the benefit that it uses less space in some instances and cache efficiency may be better since the relevant information is stored next to each other in consecutive order (worst case is still $n$).


For Loop Range with Smaller Number on Right Simple question from an algorithm noob...

If $i=1$ then the inner loop will include what I believe to be an invalid range. Is this acceptable pseudocode?

For i=1 to n
  For k=1 to i-1
    ...

It is acceptable.

The loop says “do something for each integer $k$ in some range”. If there is no integer in that range, the loop just won’t do anything.


Solving a recurrence of uneven subproblems without Akra-Bazzi I encountered the following recurrence relation in homework, for which we need to find its asymptotics: $$T\left(n\right)=T\left( \frac{n}{3} \right) + T\left( \frac{n}{6} \right) + 1$$
I observed it is possible to approach this relation with the method of Akra-Bazzi, however this method was not taught in class. Akra-Bazzi gives the result of  $\theta(n^p)$ where $p$ is the unique solution to $$\frac{1}{3^p}+\frac{1}{6^p}=1$$
However, since this was not taught, I would like to ask if there's a different method to tackle this exercise, or a way to find its asymptotics more constructively.

You could use "guess-and-check": guess the solution to the recurrence, then use induction to prove that it is a solution, i.e., to prove that your solution satisfies the recurrence.
In your case, since you know Akra-Bazzi, your "guess" can actually be obtained through Akra-Bazzi, but you don't have to tell anyone that's how you obtained your guess.


Does an ADT have multiple or only one representations/implementations? Section 24.2  in Types and Programming Languages by Pierce defines ADTs in existential types:

  A conventional abstract data type (or ADT) consists of (1) a type name A, (2) a concrete representation type T, (3) implementations of
  some operations for creating, querying, and manipulating values of
  type T, and (4) an abstraction boundary enclosing the representation
  and operations. Inside this boundary, elements of the type are viewed
  concretely (with type T). Outside, they are viewed abstractly, with
  type A. Values of type A may be passed around, stored in data
  structures, etc., but not directly examined or changed—the only
  operations allowed on A are those provided by the ADT. ... We ﬁrst
  create an existential package containing the internals of the ADT:

counterADT =
{*Nat,
{new = 1,
get = λi:Nat. i,
inc = λi:Nat. succ(i)}}
as {∃Counter,
{new: Counter,
get: Counter→Nat,
inc: Counter→Counter}};

> counterADT : {∃Counter,
{new:Counter,get:Counter→Nat,inc:Counter→Counter}}

  We can open it for example

let {Counter,counter} = counterADT in
counter.get (counter.inc counter.new);
> 2 : Nat

Does the highlighted sentence in the following quote say that a ADT can have multiple representations/implementations?

  A key property of the kind of information hiding we are doing here is
  representation independence. We can substitute an alternative
  implementation of the Counter ADT—for example, one where the
  internal representation is a record containing a Nat rather than just
  a single Nat,

counterADT =
{*{x:Nat},
{new = {x=1},
get = λi:{x:Nat}. i.x,
inc = λi:{x:Nat}. {x=succ(i.x)}}}
as {∃Counter,
{new: Counter, get: Counter→Nat, inc: Counter→Counter}};

> counterADT : {∃Counter,
{new:Counter,get:Counter→Nat,inc:Counter→Counter}}

  in complete conﬁdence that the whole program will remain typesafe,
  since we are guaranteed that the rest of the program cannot access
  instances of Counter except using get and inc.

Do the highlighted sentences in the following two quotes say that an ADT can have only one representation/implementation?

On p377:

  In summary, the single representations of ADTs directly support
  binary operations, while the multiple representations of objects give
  up binary meth- ods in return for useful ﬂexibility. These advantages
  are complementary; nei- ther style dominates the other.

From a reply to my previous question:

  ADTs are entirely public about their unique representation. Belonging in the ADT means satisfying said representation, and so binary methods can rightfully assume that both operands have that exact representation.

Why is the inconsistency?

Thanks.

ADT is a specification. It can have many implementations. For an example, see this answer.


Static prediction of branch prediction If we have a static implementation of branch prediction and we always fetch the next sequential instruction isn't inefficient to do that if we, at a future point verify if the prediction was correctly done? We just evaluate the branch in future... Why don't we just simply verify this thing every time we encounter a branch and not just execute what we think it's correct? I see here a delay because we double check the incorrect situations. 10 predictions, 4 wrong => 14 evaluations instead of 10. I know I'm wrong but I can't figure it why.

You are missing a fundamental detail: modern processors are pipelined. What it means in a nutshell is that instruction $I_{n+1}$ is fetched from memory and begins being processed way before instruction $I_n$ has been executed completely. But if $I_n$ is a conditional branch, we have no way to know for sure whether or not the jump will happen: we would have to stop fetching instructions until we finish evaluating $I_n$.

Branch prediction doesn't come from theory but from a strictly practical observation: it is better to be sometimes wrong, but decide quickly than to be always correct but slowly.

A classical example is the following:

for (i <-- 0 to 1,000,000) do {
    ...
}

If we just take the "loop continues" branch every time, we will be wrong once but correct the other $999,999$ times, yielding a better average running time in practice.


Making feature vector from Gabor filters for classification My aim is to classify types of cars (Sedans,SUV,Hatchbacks) and earlier I was using corner features for classification but it didn't work out very well so now I am trying Gabor features.

code from here

Now the features are extracted and suppose when I give an image as input then for 5 scales and 8 orientations I get 2 [1x40] matrices.

1. 40 columns of squared Energy.

2. 40 colums of mean Amplitude.

Problem is I want to use these two matrices for classification and I have about 230 images of 3 classes (SUV,sedan,hatchback).

I do not know how to create a [N x 230] matrix which can be taken as vInputs by the neural netowrk in matlab.(where N be the total features of one image).

My question:

How to create a one dimensional image vector from the 2 [1x40] matrices for one image.(should I append the mean Amplitude to square energy matrix to get a [1x80] matrix or something else?)
Should I be using these gabor features for my purpose of classification in first place? if not then what?

Thanks in advance

Well I figured it out myself that making a 1D vector of [1x80] by appending two [1x40] array worked and my classifier works very fine now


Can we make a non-regular language regular via concatentation? My question is basically given three languages A, B and L, where L is A and B concatenated together and B is proven to be non regular, is it possible to find an A that makes L regular?

Yes this is possible. Consider the example given below:

Let $B = 1^p$ where $p$ is prime. This is non regular.
Let $A = 1^n$ where $n \in \mathbb{N}$. This is regular.

$AB$ will simply give us $1^n$ with $n > 2$ and this is regular since any number greater than $2$ can be reprsent as $2+x$ where $x > 0$


Which word could I use for the pumping lemma? I have a problem to start my proof because I do not find a word $w$ where I can use the pumping lemma.

Task:

Be
$\sum { =\left\{ a,b,c \right\}  } $ and $S=\left\{ bx{ c }^{ m }|x\in { \left\{ a,b \right\}  }^{ * }\wedge m\in N\wedge { |bx| }_{ a }-{ |bx| }_{ b }>m \right\} $

Proof with the the pumping lemma, that S is no regular language.

What I know is, that the word has to start we one $b$ following from n times $a$ or $b$ but $w$ needs to have one more $a$ than $b$ in it and $w$ also needs to have one more $b$ than $c$ in it to  fulfill the condition.
So it has to be something like this $W=b{a}^{2m+2}b^mc^m$?
This language is very difficult for me, hope you see more than I.

P.S. Please no complete solutions of the full task.

So it has to be something like this $w=b{a}^{2m+2}b^mc^m$.

$b{a}^{2m+2}b^mc^m$ is not the general form for $w=bxc^m\in S$. If $x$ must be in the form of $a^*b^*$, $w$ will be something like $b{a}^{m+n+k+2}b^nc^m$ for some $n,k\ge0$. Just for completeness, $w$ could be like $baba^{m+1}c^m$ or  $baba^{m+1}a^kb^kc^m$ or many other forms. Of course, it is totally fine if you just meant to choose one word so as to apply the pumping lemma.

Can you check word $ba^{p+2}c^{p}$, assuming the pumping length is $p$? This word is about as simple as you could get.

Exercise 1. Assuming the pumping length is $p$, can we pump $ba^{p+3}bc^p\in S$?

Exercise 2. Assuming the pumping length is $p$, can we pump $ba^{2p+2}b^pc^p\in S$?


Context-freeness of $\{a^nb^mc^k \mid n \leq m \leq k\}$ and its complement Was analysing old exam, still, even in home condition can answer this:

Determine which of the following languages over the alphabet $\{a,b,c\}$ are context-free. Prove the claim.
(a) $L_1 = \{a^nb^mc^k \mid n \leq m \leq k\}$,
(b) $L_2 = \{a,b,c\}^* \setminus L_1$, that is, $L_2$ is the complement of $L_1$ from (a).

Any help would be appreciated, it doesn't seem like CFL to me, but I struggle to apply pumping lemma here.

The language $L_1$ is not context-free, and you can show this using the pumping lemma. Try to pump the word $a^nb^nc^n$ where $n$ is large enough.

The language $L_2$, in turn, is context-free. This is because we can write it as a union of context-free languages:

Words not of the form $a^*b^*c^*$.
Words of the form $a^nb^mc^k$ where $n>m$.
Words of the form $a^nb^mc^k$ where $m>k$.


Does $P \neq NP$ imply $NP \neq PSPACE$? Is it true that
$\mathsf{P} \neq \mathsf{NP}$ implies $\mathsf{NP} \neq \mathsf{PSPACE}$?

I have here some problem that is in $\mathsf{PSPACE} \setminus \mathsf{NP}$ if $\mathsf{P} \neq \mathsf{NP}$. Since I cannot find a fault in my proof, I wanted to be sure, if the upper implication holds or not.

We know that $\mathrm{L}\subseteq\mathrm{NL}\subseteq\mathrm{P}\subseteq\mathrm{NP}\subseteq\mathrm{PSPACE}$ and at least one of those inclusions is strict, since $\mathrm{L}\subsetneq\mathrm{PSPACE}$ by the space hierarchy theorem. As far as I'm aware, any nonempty subset of the inclusions being strict would be consistent with our current state of knowledge so, in particular, it is not known that $\mathrm{P}\neq\mathrm{NP}$ implies $\mathrm{NP}\neq\mathrm{PSPACE}$.


Corner cases in the Interleave Lower Bound for BSTs The Interleave lower bound is a lower bound for the amount of operations any Binary Search Tree needs to make for a sequence of accesses. It is used in the construction of Tango Trees, and is based on Wilber's lower bound.
The Interleave lower bound is proved by defining a Transition Point for every node $y$ in a static tree $P$.
See Demaine, Erik D., et al. "Dynamic optimality-almost." SIAM Journal on Computing 37.1 (2007): 240-251: Section 2 and Appendix A.

I see a problem with the definedness of the transition point for nodes in the tree that don't have a right subtree, such as leaves, for which there doesn't exist a path from the root that contains both elements from the left subtree + $y$ and from the right subtree of $y$.

Does it constitute a problem to the analysis of the bound?
It certainly seems to weaken Lemma A.1. For any node y in P and any time i, there is a unique transition point for y at time i.
If we consider the transition point of such nodes in $P$ to be themselves in $T_i$ then there is a problem with Lemma A.3. At any time i, no node in T_i is the transition point for multiple nodes in P.

Can the analysis and the bound be kept by not counting the interleaving through the leaves (and possibly their parents), and thus avoiding the need to refer to their transition points?

Leaves have no interleaving since they only have left sub-trees. Therefore you should apply the bound to all non-leaves, in which case the lemmas in the appendix go through. The resulting lower bound should be exactly the same.

The paper in question appeared first in a conference (FOCS) and then in a special issue dedicated to papers from the conference. Usually the conference reviewers are recruited to do the journal reviews as well, in the case of a special issue. This lowers the standard for reviews, since conference reviews are often not very exacting, and when reviewing the same paper for the journal, the reviewers won't bother to read the paper again. Exacerbating this phenomenon is the fact that the lower bound appears in an appendix.

The experts probably realized this inaccuracy right away, and knew that it wasn't a real problem, so didn't bother to comment about it if they noticed it at all.


Asymptotic bound of a heap's height Today I was taught that since the height of a heap cannot exceed $\log n$, it is $O(\log n)$; height in my class was defined as the maximum number of steps in a simple path from a leaf to the root. That is fine, but I think we should further specify it as $\Theta(\log n)$ since it, at that same time, must be greater than $\log n - 1$, and hence also fits $\Omega(\log n)$. I suggested this after class, but I was repeatedly told that $O(\log n)$ was correct, and the correctness of $\Theta(\log n)$ was not explicitly confirmed.

Is $\Theta(\log n)$ correct? If so is there a common reason / justification to just use $O$ instead, and possibly even to avoid using $\Theta$?

Clarification: it's a binary heap.

Yes $\Theta(logn)$ is correct. By the definition of $\Theta$ notation we can say that some function $g(n)$ is at least $k_1⋅f(n)$ and also it is at most $k_2⋅f(n)$ for considerably large $n$ and $k_1 > 0$ and $k_2 > 0$. If you apply this definition to the heap's height, you will find that the heap's height satisfies this. So, $\Theta(logn)$ is totally correct.


Where does LL parser belong in the top-down parsers classification There are four types of top-down parsers according to this answer:

recursive descent backtracking
recursive descent predictive
table-driven with backtracking
table-driven predictive.

Also the author says that:

  All top down parsers are LL

However, in this answer the author seem to associate the LL parser with table-driven parsers:

  LL is usually a more efficient parsing technique than
  recursive-descent.

And the OP:

  [one category]... seem to be the LL parser (using stack/parse table)

Also this article states:

  LL parsers are also called predictive, because it's possible predict
  the exact path to take by a certain amount of lookup symbols, without
  backtracking.

which associates LL parsers with predictive parsers, which can be either recursive descent or table-driven.

So I'm at loss here. Can you guys help?

First let's make some general remarks about nomenclature.  They are not all relevant here, but they may help you in the future.

not all authors are using the same precise definition.  Sometimes the differences are irrelevant for the current points, sometimes one wonder way such different things are named in the same way by different authors.  Sometimes authors give the definition they are using, but that's not always true.  Sometimes there are well accepted definition that you can take for granted in about any context, sometimes every group tend to have its own and you have to know of which group the author is a member. (Ask a Java and a ML programmer what polymorphism is)
Nomenclature are about classification.  Classification is emphasizing some aspects while ignoring other, even if you think it should be (For instance L. Cardelli and P. Wegner do not consider the static or dynamic aspect in their analysis of polymorphism)

Now you are somewhat lucky, as some of the terms here have quasi-universal definitions  (that is not that some are not using other one, especially in blogs and QA sites, but they are trying to intuit a definition from the terms instead of looking at the definitions given by text books).

A top-down parser is a parser which start from the start symbol, guess which production to use, and then repeat the process for a non terminal symbol.  If it is able to second guess its choice, it is also a back-tracking parser.  If it never second guess its choice, it is a deterministic parser.

A LL(k) parser is a deterministic top-down parser which will always determine the production to use for the left-most non-terminal not yet determined (that's what the second L means) and will consider only the text from left to right (that's what the first L means) and will never use more than $k$ terminal symbols not predicted.

Thus

  There are four types of top-down parsers:

  recursive descent backtracking
  recursive descent predictive
  table-driven with backtracking
  table-driven predictive.

deterministic seems more common than predictive but that division seems correct.  I'll emphasize the fact that the division backtracking/predictive characterizes the algorithm, while the division recursive/table-driven characterizes the implementation.  So although the classification is correct, it is mixing different aspects something which tend to introduce confusion.

  All top down parsers are LL

That is false.  Some are not deterministic (the recursive descent backtracking one of your first list).  Some are scanning the text from right to left (AFAIK, the only interest is academic here but it would not surprise me that there is someone somewhere which found a use for it).  Some are trying to determine the production to use for another non-terminal than the next one (it's a formalization of the good old find the next matching parenthesis before trying to parse what is between them).

  LL is usually a more efficient parsing technique than recursive-descent.

LL can be implemented as recursive-descent (and is the easiest way to do so), opposing the two does not really make sense to me.  Recursive/table driven is an implementation choice.  (I've written both, I'd use the table driven approach only as part of a parser generator but I'll never say they are different algorithms).

  LL parsers are also called predictive

This could be misleading.  They are not the only class of parser which could be called predictive.


Can number of states in DFA be greater than $2^n$ when language-equivalent NFA has $n$ states? As title says, can the number of states in DFA be greater than $2^n$ when language-equivalent NFA has $n$ states - that is if the NFA recognizes the same language as the DFA and has $n$ states, can DFA have more than $2^n$ states?

I think it is, and this is trivially. However Wikipedia seeems to write that it is not possible to have more than $2^n$ states. So comes the question.

it surely can, but it needs not. Using the powerset construction you can convert any $n$-state NFA into a DFA with at most $2^n$ states.


Is every decidable language recognizable by a Turing Machine space-bounded by some f(|w|)? The negative answer to decidable = non-contracting grammar? suggests the following question:

Is there a decidable language that can be recognized only by a space unrestricted Turing Machine (i.e. with infinite tape but in finite time)?

This is, are there words, w, in a decidable language for which cannot be determined a bound f(|w|)?

Consider a Turing machine which reads its input and then immediately stops. This Turing machine always halts on every input, but the running time is unbounded: the machine runs for $n$ steps on an input of length $n$.
In fact, most halting Turing machines have unbounded running time: if the running time of a Turing machine is bounded by $T$, then the language it decides can only depend on the first $T$ symbols of the input.
If a Turing machine always halts on any input, then there is a function $f(n)$ such that the Turing machine always halts within $f(n)$ steps on an input of length $n$. You can take as $f(n)$ the maximal time it takes the Turing machine to halt on an input of length $n$. Since there are only finitely many words of length $n$ (recall that the input alphabet is fixed), this is well-defined.
Furthermore, if a Turing machine always halts on any input, the function $f(n)$ defined in the preceding paragraph is always computable. You can compute it by simulating the machine on all possible inputs of length $n$.
Space works exactly the same way.


Regular and Non-Regular Language My friends and I are taking a formal languages class and for one of our homework questions we have to prove if these languages are regular:

1) L = {apaqi : p and q are fixed integer values, i >= 0}

2) L = {apbq : p and q are fixed integer values}

For (1), we know it is regular because we can make a DFA out of it, but what we are not sure how exactly the DFA should look like. Should it not be consist only of one state, say q0, and it acts as both the initial and final state, with a loop of "a" moves going through it? Our line of thought is because p and q could be any integers, so whatever p and q would be, we would always end up with a certain number of a's, but we are not sure we are 100% correct.

For number (2), we say it is not regular because p and q could be infinite, thus making the language automatically irregular.

We are still quite confused on which concepts are correct. This is still a very abstract concept for all of us and any guidance would be appreciated. Thank you!

Think of it this way. Fix $p$ and $q$ arbitrarily – for example, take $p = 4$ and $q = 5$. Then
$$
\begin{align*}
L_1 &= \{ a^4 b^{5i} : i \geq 0 \}, \\
L_2 &= \{ a^4 b^5 \}.
\end{align*}
$$
Now try to answer your question. The answer will be the same no matter what values you choose for $p$ and $q$.


E-Unification: “Goal seeking” pattern matching between directed trees Preamble

Suppose we have some symbols x, y, ... and wildcards (ξ), (ζ), ... which have any meaning. Wildcards are said to ‘match’ any symbol: wildcard (ξ) matches symbol x under the mapping {(ξ): x}. Now suppose we can construct directed trees from these symbols and wildcards. The notion of matching should extend to these trees, like this:

  x                 x
 / \               / \
a   y   matches  (ξ)  y   under the mapping {(ξ): a, (ζ): b}.
   / \               / \
  z   b             z  (ζ)

It is easy to implement an algorithm which takes two trees like those above and gives the necessary mapping. (Does it have a name?)

I want to introduce certain ‘equivalence relations’ <n> between trees. For instance, if I wanted to capture the notion of the symbol f being commutative and associative, I could write:

       f         f
<1>:  / \   =   / \     # commutativity f(ξ, ζ) = f(ζ, ξ)
    (ξ) (ζ)   (ζ) (ξ)

        f         f
       / \       / \
<2>:  f  (χ) = (ξ)  f   # associativity f(f(ξ, ζ), χ) = f(ξ, f(ζ, ξ))
     / \           / \
   (ξ) (ζ)       (ζ) (χ)

This is where things get interesting, because I now want to implement a more intelligent matching algorithm which, given a set of equivalence relations like those above, is able to perform ‘indirect’ matches like this:

  f                          f
 / \  (indirectly) matches  / \  under the mapping {(ξ): x}...
y   x                     (ξ)  y

                f  <1>  f                            f
   ...because  / \  =  / \  which directly matches  / \ .
              y   x   x   y                       (ξ)  y

Question

How would one go about finding an algorithm which is able to transform a given tree (via given rules) so that it ‘matches’ another tree?

Is there a name for this kind of problem?

More examples

Matches aren’t always unique. Ideally, the algorithm should be able to find all of them.

   f                 f
  / \               / \
 x   f   matches   f  (ξ)  under {(ξ): y, (ζ): z} or {(ξ): z, (ζ): y}...
    / \           / \
   y   z        (ζ)  x

         ...using rules <1> and <2>.

A quintessential demonstrative example:

For brevity, define the symbols 1, 2, 3, ... in terms of 0 and a unary symbol s:

1 = s(0), 2 = s(s(0)), 3 = s(s(s(0)))...

Now, define two transformation rules s(n) = +(n, 1) and s(+(n, m)) = +(n, s(m)):

       +      s
<1>:  / \  =  |
    (n)  1   (n)

     s       +
<2>: |  =   / \
     +    (n)  s
    / \        |
  (n)  (m)    (m)

Check this out:

            +
5 matches  / \  under {(ξ): 2}, because...
          3  (ξ)
                     <1>          <2>
...5 = s(4) = s(s(3)) = s(+(3, 1)) = +(3, s(1)) = +(3, 2) which matches 5 with {(ξ): 2}.

   (as trees:)
       s   s  <1>  s  <2>   +       +                  +
...5 = | = |   =   |   =   / \  =  / \  which matches / \  with {(ξ): 2}.
       4   s       +      3   s   3   2              3  (ξ)
           |      / \         |
           3     3   1        1

(I apologise for the size of this question. I don’t have a background, so feel free to improve this post.)

Perhaps you can direct me to some reading, or set me off in the right direction? Thanks heaps!

This is called unification.  There is a one-to-one correspondence between terms and trees; the tree is the parse tree of a corresponding term.  It sounds like you want the most general unifier.  There are standard algorithms for solving this.  However, this doesn't handle equivalence relations like commutativity or associativity.  E-unification might be what you are looking for.