Recursive definitions over an inductive type with nested components Consider an inductive type which has some recursive occurrences in a nested, but strictly positive location. For example, trees with finite branching with nodes using a generic list data structure to store the children.

Inductive LTree : Set := Node : list LTree -> LTree.

The naive way of defining a recursive function over these trees by recursing over trees and lists of trees does not work. Here's an example with the size function that computes the number of nodes.

Fixpoint size (t : LTree) : nat := match t with Node l => 1 + (size_l l) end
with size_l (l : list LTree) : nat := match l with
    | nil => 0
    | cons h r => size h + size_l r
  end.

This definition is ill-formed (error message excerpted):

Error:
Recursive definition of size_l is ill-formed.
Recursive call to size has principal argument equal to
"h" instead of "r".

Why is the definition ill-formed, even though r is clearly a subterm of l? Is there a way to define recursive functions on such a data structure?

If you aren't fluent in Coq syntax: LTree is an inductive type corresponding to the following grammar.

$$\begin{align}
  \mathtt{LTree} ::= & \\
  \vert & \mathtt{list}(\mathtt{LTree}) \\
\end{align}$$

We attempt to define the size function by induction over trees and lists. In OCaml, that would be:

type t = Node of t list
let rec size = function Node l -> 1 + size_l l
and size_l = function [] -> 0
                    | h::r -> size h + size_l r

What works

If you nest the definition of the fixpoint on lists inside the definition of the fixpoint on trees, the result is well-typed. This is a general principle when you have nested recursion in an inductive type, i.e. when the recursion goes through a constructor like list.

Fixpoint size (t : LTree) : nat :=
  let size_l := (fix size_l (l : list LTree) : nat :=
                  match l with
                    | nil => 0
                    | h::r => size h + size_l r
                  end) in
  match t with Node l =>
    1 + size_l l
  end.

Or if you prefer to write this more tersely:

Fixpoint size (t : LTree) : nat :=
  match t with Node l =>
    1 + (fix size_l (l : list LTree) : nat :=
          match l with
            | nil => 0
            | h::r => size h + size_l r
          end) l
  end.

(I have no idea who I heard it from first; this was certainly discovered independently many times.)

A general recursion predicate

More generally, you can define the “proper” induction principle on LTree manually. The automatically generated induction principle LTree_rect omits the hypothesis on the list, because the induction principle generator only understand non-nested strictly positive occurences of the inductive type.

LTree_rect =
fun (P : LTree -> Type) (f : forall l : list LTree, P (Node l)) (l : LTree) =>
match l as l0 return (P l0) with
| Node x => f x
end
     : forall P : LTree -> Type,
       (forall l : list LTree, P (Node l)) -> forall l : LTree, P l

Let's add the induction hypothesis on lists. To fulfill it in the recursive call, we call the list induction principle and pass it the tree induction principle on the smaller tree inside the list.

Fixpoint LTree_rect_nest (P : LTree -> Type) (Q : list LTree -> Type)
                         (f : forall l, Q l -> P (Node l))
                         (g : Q nil) (h : forall t l, P t -> Q l -> Q (cons t l))
                         (t : LTree) :=
  match t as t0 return (P t0) with
    | Node l => f l (list_rect Q g (fun u r => h u r (LTree_rect_nest P Q f g h u)) l)
  end.

Why

The answer to why lies in the precise rules for accepting recursive functions. These rules are perforce subtle, because there is a delicate balance between allowing complex cases (such as this one, with nested recursion in the datatype) and unsoundness. The Coq reference manual introduces the language (the calculus of inductive constructions, which is the proof language of Coq), mostly with formally precise definitions, but if you want the exact rules regarding induction and coinduction you'll need go to the research papers, on this topic Eduardo Giménez's [1].

Starting with the Coq manual, in the notation of the Fix rule, we have the fixpoint definition of $\mathsf{Fix} f_i \, \{ f_1 : A_1 := t_1 \; ; \;\; f_2 : A_2 := t_2 \}$ where:

$$\begin{align*}
  \Gamma_1 &= (x : \mathtt{LTree}) &
  A_1 &= \mathrm{nat} &
  t_1 &= \mathsf{case}(x, \mathtt{LTree}, \lambda y. g_1 (f_2 y)) \\
  \Gamma_2 &= (l : \mathtt{list}\;\mathtt{LTree}) &
  A_2 &= \mathrm{nat} &
  t_2 &= \mathsf{case}(l, \mathtt{list \: LTree}, \lambda h \: r. g_2 (f_1 h) (f_2 r)) \\
\end{align*}$$

In order for the fixpoint definition to be accepted, “if $f_j$ occurs [in $t_i$] then … the argument should be syntactically recognized as structurally smaller than [the argument passed to $f_i$]” (simplifying because the functions have a single argument). Here, we need to check that

$i=1$, $j=2$: l must be structurally smaller than t in size, ok.
$i=2$, $j=1$: h must be structurally smaller than l in size_l, looks ok but isn't!
$i=2$, $j=2$: r must be structurally smaller than l in size_l, ok.

The reason why h is not structurally smaller than l according to the Coq interpreter is not clear to me. As far as I understand from discussions on the Coq-club list [1] [2], this is a restriction in the interpreter, which could in principle be lifted, but very carefully to avoid introducing an inconsistency.

References

Cocorico, the nonterminating Coq wiki: Mutual Induction

Coq-Club mailing list:

[1] Thread “Meta theory: induction over terms with abstract variables”; first message by Robbert Krebbers on 2009-10-21; explanation by Adam Chlipala; counterexample by Bruno Barras; reply by Hugo Herbelin.
[2] Thread “Termination checking with nested recursion”; first message by Gert Smolka; reply by Hugo Herbelin.

The Coq Development Team. The Coq Proof Assistant: Reference Manual. Version 8.3 (2010). [web] ch. 4.

Eduardo Giménez. Codifying guarded definitions with recursive schemes. In Types'94: Types for Proofs and Programs, LNCS 996. Springer-Verlag, 1994. doi:10.1007/3-540-60579-7_3 [Springer]

Eduardo Giménez. Structural Recursive Definitions in Type Theory. In ICALP'98: Proceedings of the 25th International Colloquium on Automata, Languages and Programming. Springer-Verlag, 1998. [PDF]


Regular sets have linear growth? Is it true that the set $\{ 0^{n^2} \mid n \in\mathbb{N} \}$ is not regular because it does not grow linearly?

  Regular sets are called regular because if you have a regular set then you can always pump it up (pumping lemma) in regular intervals and get other things in the set. They string out at very linear intervals. That's why anything that grows in other than linear intervals is not regular.

Therefore, $\{ a^{n^2} b^n \mid n \in\mathbb{N} \}$ is not regular, right? Also, I know that $\{ a^n b^n \mid n \in\mathbb{N} \}$ is not regular, but what about $\{ a^{cn} b^{dn} \mid n \in\mathbb{N} \}$ for any integer coefficients $c$ and $d$?

Is it true that the set $0^{n^2}$ is not regular because it does not grow linearly?

Yes, that's true. That follows from the pumping lemma as explained in the paragraph you quoted.

  Therefore, $a^{n^2} b^n$ ... is not regular?

Yes, that's also true for the same reason.

  Also, I know that $a^n b^n$ is not regular, but what about $a^{cn} b^{dn}$ for any integer coefficients $c$ and $d$?

The language $\left\{a^{cn} b^{dn} \mid n \in \mathbb{N}\right\}$ where $c$ and $d$ are fixed is regular if and only if $c$ or $d$ is equal to 0.


Are there problems that are polynomial-time equivalent to factoring composites? It seems that factoring a number known to be composite is in its own interesting little complexity class, e.g. polynomial time using quantum computing even though no one has proved $\mathsf{P} = \mathsf{NP}$ for quantum computing.

Are there interesting, non-obvious examples of problems with polynomial-time verifiability for solutions, which have been shown to be polynomial-time equivalent to factoring a composite number into primes, under the classical non-quantum computational model?

I assume that you meant to consider the difference between $BQP$ and $NP$ rather than $P$ and $NP$. $P$ is primarily only defined using deterministic time bounded Turing Machines while $BQP$ is specific to bounded error polytime quantum computers.

Factoring is, of course, in $NP$ (function version being in $\mathcal{F}_{NP}$), so it should easily follow that anything polynomial time reducible to factoring is going to have a polynomial time verifier. If you were actually asking if any polynomial time verifiers share the same "hardness" as factoring, then the answer is: no idea. It would require making assumptions about whether or not factoring is in $P$.

I am afraid that I could not find a non-number theoretic set of problems that are known to be polynomial time reducible to factoring. Despite much study, the complexity of factoring is still very open. Knowing where it falls will provide many additional answers to your question. I'll go over what I have:

Two well known ones are computing Quadratic Residuosity and computing the Euler Totient, $\phi (n)$. The equivalence between factoring and Euler totient is very straight forward, especially to those that have ever looked into RSA.

A paper by Tibor Jager and Jorg Schwenk shows that the Quadratic Residuosity Problem and Subgroup Membership Problem are "generically equivalent" to factoring.

It is still open as to whether or not the Discrete Log Problem and the decision version of Composite Residuosity are also equivalent. Though, Pomykała wrote on the polynomial time reducibility of Discrete Log (composite moduli) to Factoring recently and presented a deterministic subexponential time algorithm for just that.

You may have a lot of success researching the Hidden Subgroup Problem. For finite Abelian groups, quantum computers have the advantage of being able to do this in polynomial time via Fourier transforms. Shor uses the fact that Factoring, Discrete Log, and some others are special cases of this problem.


How to the examples for using the master theorem in Cormen work? I'm reading Cormen's Introduction to Algorithms 3rd edition, and in examples of Master Method recursion solving Cormen gives two examples

$3T( \frac{n}{4} ) + n\log(n)$
$2T( \frac{n}{2} ) + n\log(n)$

For the first example we have $a=3$ and $b=4$  so $n^{\log_4
(3)}=n^{0.793}$ and Cormen says that if we choose $\epsilon = 0.207$ then $f(n) = n\log(n) = \Omega(n^{\log_4(3)  + \epsilon})$

How? As I understand it if $\epsilon = 0.207$ then $\Omega(n^{\log_4(3)  + \epsilon})= \Omega(n)$ so we have $n\log(n) = \Omega(n)$  but it's not true; But he proves that $n\log(n) = \Omega( n^{\log_4(3)  + \epsilon} )$

And then he proves that for the second case $n\log(n)$ does not apply to masters method 3-rd case the same way as I prove above.

So could somebody explain me in detail how  the third case of the master's theorem applies to  $3T( \frac{n}{4} ) + n \log(n)$  but not to $2T( \frac{n}{2} ) + n\log(n)$.

First of all, please check what $O$ and $\Omega$ and the other Landau symbols mean; that should remove some of the confusion.

Note that $n \log n \in \omega(n)$, that is $n \log n$ grows properly faster than $n$, asymptotically. This can be seen by

$\qquad \lim_{n \to \infty} \frac{n \log n}{n} = \lim_{n \to \infty} \log n = \infty$.

By the same reasonining, though, $n \log n \in o(n^{1 + \varepsilon})$ for every $\varepsilon \in (0,\infty)$.

Therefore, $n \log n \in \Omega(n^\alpha)$ for all $\alpha \in [0,1]$, so in the example you can choose $\varepsilon$ arbitrarily so that $\varepsilon + \log_4(3) \leq 1$. The authors pick one, namely the largest (up to dropped decimal places).

As has been noted, that does not conclude the proof that case three applies; you still have to check that $a f\left( \frac{n}{b} \right) \le c f(n)$ for some $c>1$ and all $n>n_0$, $n_0$ some natural number.

As for the second example, my above explanation shows that there is no $\varepsilon > 0$ so that $n \log n \in \Omega(n^{\log_2(2) + \varepsilon})$, so case three can not apply here. Note that $o(f) \cap \Omega(f) = \emptyset$ for all $f$.


Supervised learning with no prior information I am now reading two modern books on machine learning theory. Both of them emphasize that, in order to succeed in supervised learning, one must choose a good hypothesis class. "Good" means that it is sufficiently simple (formally, has a low VC dimension) and that it contains the true hypothesis or sufficiently close hypotheses. One also mentions the "no free lunch theorem", which says that, without such prior knowledge, you cannot have meaningful learning.

But what do I do if I have no prior knowledge? I have no idea how the correct hypothesis looks like, I do not know if it will be simple or complex. All I have is the training data. Isn't there anything useful I can do with them?

I am thinking of a newly born child. He has no prior knowledge, all he has are "training samples" given by his parents/teachers, and it is still sufficient for meaningful learning.  You could say that each child is born with some prior knowledge wired into his brain, but then the question is:  where such prior knowledge comes from? And again, what should a person do in a new situation on which his wired prior-knowledge is useless?

To sum, my question is: what is a supervised learning paradigm that can be applied without any prior knowledge on the set of possible hypotheses?

I think that the success of a newborn child follows from the fact that the phenomena he's trying to learn is describable (or can be sufficiently approximated) by the hypothesis class generated by the learning algorithm which is going on in his brain.

This is of course, not formal in any way, but say a baby is equipped with some neural network (of fixed depth), and upon receiving new data, the weights are updated accordingly using some algorithm.

The choice of neural network doesn't really matter, simply imagine that you have carefully studied the processes going on inside the human brain, and found out that the human learning process is similar to using a neural net.

In that case, the image of the learning algorithm is some class $\mathcal{F}$, say functions expressible by some fixed depth nets, and the success of the baby in learning new things simply means that the phenomena he's trying to learn is captured by $\mathcal{F}$ (so nothing magical/contradicting what you quoted is going on).

To make sure this answer does more than just contain some of my random thoughts, I will add that if you truly know nothing, there is nothing you can hope to learn. The data you're receiving could always be generated from the uniform distribution, i.e. someone is tossing a coin and giving you the outcome. Obviously, in that case, you can not hope for a small generalization error.


Average vs Worst-Case Hitting Time Consider a simple random walk on an undirected graph and let $H_{ij}$ be the hitting time from $i$ to $j$. How much bigger can
$$ H_{\rm max} = \max_{i,j} H_{ij}, $$ be compared to
$$ H_{\rm ave} = \frac{1}{n^2} \sum_{i=1}^n \sum_{j=1}^n H_{ij}.$$ For all the examples I can think of, these two quantities are of roughly the same order of magnitude.

To make this into a formal question, define
$$\phi(n) = \max_{\mbox{undirected graphs with } n \mbox{ nodes }} \frac{H_{\rm max}}{H_{\rm ave}}.$$ How fast does $\phi(n)$ grow with $n$?

The quantity $\phi(n)$ grows like $\Theta(n)$.

For the lower bound, consider the following graph: a clique on $m$ vertices connected to a path of length $k = C\log m$ for an appropriate $C$ (so $n = m + k \approx m$), in which each vertex of the path is also connected to the first vertex of the path (the one incident to the clique). The maximal hitting time is some large number $M = \exp(k)$. The hitting time of two vertices in the clique is around $m \ll M$. The hitting time of a vertex on the path and any other vertex is at most $M$. So the average hitting time is at most roughly $m + \frac{2kn}{n^2} M = O(kM/n)$. In fact, the hitting time of a vertex at distance $t$ from the clique is roughly $\exp(t)$ (for $t \gg \log m$), and if we take this into account then we get an average hitting time of roughly $m + \sum_{t=1}^k \frac{2n}{n^2} \exp(t) = O(M/n)$. This shows that $\phi(n) = \Omega(n)$.

For the upper bound, let $H_{ij}$ be the maximum hitting time. The triangle inequality shows that for each $k$, either $H_{ik} \geq H_{ij}/2$ or $H_{kj} \geq H_{ij}/2$. So at least $n/2$ of the hitting times are at least $H_{ij}$, showing that the average hitting time is at least $H_{ij}/n$. This shows that $\phi(n) = O(n)$.


The amount of ROM needed to implement a 4-bit multiplier? For a 4-bit multiplier there are $2^4 \cdot 2^4 = 2^8$ combinations.

The output of 4-bit multiplication is 8 bits, so the amount of ROM needed is $2^8 \cdot 8 = 2048$ bits.

Why is that?  Why does the ROM need all the combinations embedded into it?

What will be the case with RAM?

As shown in the figure bellow (general architecture of ROM):

to address 8-bit numbers correctly your ROM size should be: $2^8 \times 8$ bits.


Reduce our problem to a known np-complete problem Subgraph isomorphism

We have the graphs $G_1=(V_1,E_1), G_2=(V_2,E_2)$.

Question: Is the graph G_1 isomorphic with a subgraph of $G_2$ ?

(i.e. is there a subset of vertices of $G_2, V \subseteq V_2$ and subset of the edges of $G_2 E \subseteq E_2$ such that $|V|=|V_1|$ and $|E|=|E_1|$ and is there a one-to-one matching of the vertices of $G_1$ at the subset of vertices $V$ of $G_2 f:V_1 \to V$ such that $\{u,v\} \in E_1 \Leftrightarrow \{ f(u),f(v) \} \in E$)

In order to show that the problem is in NP, could we say the following?

A non-deterministic Turing machine can first "guess" which subgraph $G$ of $G_2$ is isomorphic with $G_1$ and then verify that $G$ is isomorphic with $G$ in $O(V_1+E_1)$ steps, since if we assume that the graphs are represented as adjacency lists, $G_1$ will have $O(V_1+E_1)$ elements.

Or could I improve something?

I want to show that the problem is NP-complete, reducing the clique problem to it (Hint: assume that  the graph $G_1$ is complete)

Could you give me a hint how we could reduce the clique problem to our problem in order to show that the latter is NP-complete?

The hint tells you pretty much everything:

Consider an arbitrary graph $G_{2}$ on $n$ vertices.
Also per the suggestion of the hint, let $G_1$ be the complete graph on $k$ vertices, for some $k \le n$.

Is $G_{1}$ is isomorphic to a subgraph of $G_{2}$?

If yes, what does that tell you about $G_{2}$?
How can you use that to solve the max-clique problem?


Mapping between kernel-level thread and user-level thread This is my understanding:

There are two types of processes: user and kernel(OS). Each process can have single or multiple threads. The threads of a user process are called a user-level thread and the threads of a kernel process are called kernel-level threads. Scheduler, dispatcher etc. contains kernel-level threads. Both user-level threads and kernel-level threads can able to run on CPU.

There may be several user-processes in ready queue for execution, scheduler(kernel) decides which user process/ thread to run on CPU, dispatcher(kernel) gives control to the corresponding user-thread on CPU, the corresponding user-thread executes and terminates.

Consider the following statement (From Galvin os textbook):

To run on a CPU, user-level threads must ultimately mapped to an associated kernel-level thread.

My doubt is as follows:

What is the need of such mapping? Where am I going wrong?

I don't know the book, so what follows is only my speculation. Take it as such.

"User vs kernel level threads" might mean two different things. Carefully check your book terminology.

One interpretation is that user level threads are those who execute users' programs, while kernel level threads execute OS code. This is the interpretation you described in your question.

Another possible interpretation is the following. The OS provides processes and threads as usual. Within a OS-provided thread CPU time, user code might choose to run several subroutines concurrently. I.e., within the same OS thread, user code can execute a subroutine for 100ms, and then jump to another one for 100ms, and so on. Essentially, the user code is implementing a scheduler among several sub-threads. These "simulated" threads can be named "user level threads". In practice, some programming language implementations provide these, often called "green threads" or something similar. Note that the OS is completely unaware of those user level threads.

If at that point your book is referring to such threads, then the sentence you quoted simply means that each user thread, to be executed, must be run inside a OS provided thread. A simple implementation is to map N user level threads to a single OS thread, but running N user threads exploiting M OS threads is also possible.


Given the logical address, how to extract the page number? I am studying Computer Systems. I have th following question and its answer:

  Given the logical address 0xAEF9 (in hexadecimal) with a page size of
  256 bytes, what is the page number?

  Answer: 0xAE (I found this answer in the web, but I want to know how can I
  figure it out myself?

How can I figure out the page number for a given logical address?

Your logical address is made of 16 bits, that means you have a addressable space of $2^{16}$ bits. The page size is typically a power of 2, $2^n$, in this case $2^n = 256 \Rightarrow n = 8$.

The page number is calculated by substracting $n$ from the size of your logical address: $16 - 8 = 8$, so the first 8 bits of the address are your missing page number, that is 0xAE


social network graph problem Here is the problem:

There are connected graph with nodes representing a number of people. Each node/person has an opinion on a topic e.g. trump vs clinton, paper books vs kindle, etc

The goal is make every node in a graph share the same opinion, by selecting a specific subset of nodes, in a particular sequence.

If majority of a person A's friends support trump, but person A supports clinton. if person A is selected, his/her opinion will change to trump.

If person's friends opinions are equally divided, then you can decided the selected person's opinion.

I am running out of ideas as how to proof this is achievable. Maybe some of you can give me some pointers.

This is known as majority dynamics. Usually the assumption is that all nodes adopt the majority opinion simultaneously, and this is known as the synchronous model. For an arbitrary tie-breaking rule, this converges either to a fixed point or to a cycle of length 2; see for example pages 5-6 of Ginosar and Holzman's The majority action on in nite graphs: strings and puppets. If you break ties in a biased way, then the dynamic probably always converges.

What you describe is the asynchronous model, in which the majority rule is applied in sequence rather than in parallel. In that case the process always converges. See for example Tamuz and Tesler, though their methods are probably overkill for you, since in your case you get to choose the sequence, whereas in their case the sequence is chosen at random.


Check whether an undirected graph contains a simple cycle of length four using the "Squares" method The following problem is exercise 4.3 of the book "Algorithms" by S. Dasgupta, C. Papadimitriou, and U. Vazirani.

  Squares. Design and analyze an algorithm that takes as input an undirected graph $G = (V,E)$ and determines whether $G$ contains a simple cycle (i.e., a cycle which does not intersect itself) of length four in $O(|V|^{3})$ time.

This can be solved by checking for each pair of vertices $u$ and $v$ whether they share at least two common neighbors; see the answer.

However, in the book, the authors gave a single-word hint: Squares.

Following the hint, I square the adjacency matrix $M$ of $G$ twice (i.e., $M \to M^2 \to M^4$) and check whether $M^4[i][i]$ is true for some $i$. But this attempt fails because it produces "false positives" by treating $a-b-a-b-a$ or $a-b-c-b-a$ as cycles of length four.

How to fix the "false positives" in the squaring method above?

Square $M$, to get $M^2$.  Write $M^2 = D + P$, where $D$ is the diagonal part (all non-diagonal entries are zero) and $P$ is the non-diagonal part (all diagonal entries are zero).
Compute $Q=P^2$.  Note that $Q_{aa}$ counts the number of ways to start at $a$ and end at $a$, excluding cycles of the form $ababa$ and $abaca$ etc., but not avoiding cycles of the form $abcba$.
Now compute $R = MDM - D$.  Note that $R_{aa}$ counts the number of cycles of the form $abcba$ where $c \ne a$.
Let $S = Q-R$.  We find that $S_{aa}$ counts the number of simple 4-cycles that start and end at $a$.  Thus, the graph has a simple 4-cycle if and only if one or more of the diagonal entries of $S$ are non-zero.


Fast algorithm to find points on one side of hyperplane? Given $n$ points $x_1, x_2, ..., x_n \in \mathbb{R}^k$, where $\mathbb{R}^k$ can be high dimensional. Is it possible to devise a fast algorithm

(1) Preparation: first take the n points as an input, do whatever preprocessing necessary.

(2) Query: for each query $f_i = w^\top x$ being a hyperplane and a constant $b$, find the subset of points $\{x_i | w^\top x_i \geq b\}$.

such that the asymptotic complexity for the query is less than $\Theta(k \cdot n)$ ?

The keywords you may be looking for are simplex range searching and half-space range searching. See chapter 16 of Computational Geometry: Algorithms and Applications. If you are interested in general simplices (intersections of multiple half-planes), then there are two data structures in particular that might interest you: partition trees and cutting trees.

In the following paper describing partition trees, we have query time of $O(n^{1-1/d}(\log n)^{O(1)})$, preprocessing time of $O(n \log n)$, and space requirement of $O(n)$.

Matoušek, Jiří. "Efficient partition trees." Discrete & Computational Geometry 8.1 (1992): 315-334.

In a cutting tree, you consider the dual case (each point in your input is represented by a line in the dual plane) and you tradeoff space for query time. You get $O(\log n)$ query time at a cost of $O(n^{2+\epsilon})$ space.

However, if you really only care about a single half-plane in your query, you can do better. In The Power of Geometric Duality, Chazelle gives an optimal data structure for half-space range queries with $O(\log n + k)$ query time and $O(n)$ space.


Inducing a context free grammar I have a file containing a subset of possible strings from a context free language. I am looking for a mechanism to induce the grammar from this information. Is that possible?

If you have only positive examples (strings that are in the language), in principle, no, you cannot infer the grammar.  For all you can tell, the language might be $\Sigma^*$: no matter how many example strings you have, you'll never be able to rule that out as the language.

However, if you have a little more information, there are known solutions.  You can take a look at Angluin's algorithm.  If you need a software implementation, take a look at LearnLib.  See also Wikipedia's page on grammar induction for other approaches.

Another approach is to try to find the smallest context-free grammar that can generate every string in your set of examples, and nothing else.  Finding the absolute smallest CFG is probably hard, but there are known heuristics that tend to give a good solution in practice.  I'd recommend the Sequitur algorithm, if you need something in practice and have only positive examples.  This gives up generalization -- there might be an even simpler/smaller CFG that can generate every one of your example strings as well as some others -- but for some applications it works reasonably well in practice.


If $f(n) = O(g(n))$ then $\log\lfloor f(n) \rfloor = O(\log \lfloor g(n) \rfloor)$? I need to prove that $\log\lfloor f(n)\rfloor = O(\log\lfloor g(n) \rfloor)$ if $f(n) =O(g(n))$.
I know that if $f(n) = O(g(n))$ then $\log f(n) =O(\log g(n))$, but I can't prove the current statement because it involves the floor function.

Let's attempt to prove your original statement, that if $f(n) = O(g(n))$ then $\log f(n) = O(\log g(n))$.
According to the definition, there exist $C,N>0$ such that if $n \geq N$ then $f(n) \leq Cg(n)$. Taking the logarithm of both sides, if $n \geq N$ then
$$ \log f(n) \leq \log C + \log g(n). $$
Is this enough to imply that $\log f(n)= O(\log g(n))$? Not in general. For example, $2 = O(1)$ but $\log 2 \neq O(\log 1)$. However, it suffices to assume that $g(n) \geq 2$ for all $n \geq N$, since this implies that
$$
\log f(n) \leq \log C + \log g(n) \leq (\log C + 1) \log g(n),
$$
using $\log g(n) \geq 1$.
Now back to your case. Since $\log \lfloor f(n) \rfloor \leq \log f(n)$, it suffices to show that $\log f(n) = O(\log \lfloor g(n) \rfloor)$. For this, it suffices to show that $\log g(n) = O(\log \lfloor g(n) \rfloor)$. Indeed, recall that by assumption, $g(n) \geq 2$ for all $n \geq N$. We will show that if $x \geq 2$ then $\log x \leq \frac{\log 3}{\log 2} \log \lfloor x \rfloor$. Therefore $\log g(n) = O(\log \lfloor g(n)\rfloor)$.
It remains to show that $\log x \leq \frac{\log 3}{\log 2} \log \lfloor x \rfloor$. Let $\rho(x) = \frac{\log x}{\log \lfloor x \rfloor}$. Our goal is to show that $\rho(x) \leq \frac{\log 3}{\log 2}$ for all $x \geq 2$. Fixing $\lfloor x \rfloor = m$, it is clear that $\rho(x) \leq \frac{\log (m+1)}{\log m}$, hence it suffices to show that $\frac{\log(m+1)}{\log m} \leq \frac{\log 3}{\log 2}$ for all integer $m \geq 2$. This can be shown in various ways. For example, the function $\frac{\log(x+1)}{\log x}$ is decreasing for $x \geq 2$ by calculus: its derivate is
$$
\frac{x\log x - (x+1)\log(x+1)}{x(x+1)\log^2 x},
$$
which is clearly negative for $x \geq 1$ (since $x\log x$ is increasing – its derivative is $\log x + 1$).


Number of IEEE 754 doubles between two adjacent single-precision floats Between an adjacent pair of nonzero IEEE single precision real numbers, how many IEEE double precision numbers are there?

I was also wondering if this question has something to do with the hidden bit.

Can anyone help me?

Let's consider two made-up number systems: 2-dec and 3-dec. In 2-dec, numbers are specified to two decimal points (in decimal). In 3-dec, it's three. Between, say, 1.2 and 1.3, which are adjacent in 2-dec, we have 1.21, 1.22, 1.23, 1.24, 1.25, 1.26, 1.27, 1.28, 1.29 in 3-dec.

Hope this helps.

As an aside, the answer might potentially depend on whether the numbers are denormalized or not.


Finding a minimum weight perfect matching in Christofides TSP algorithm Context: After creating the minimum spanning tree, the next step in Christofides' TSP algorithm is to find all the N vertices with odd degree and find a minimum weight perfect matching for these odd vertices. N is even, so a bipartite matching is possible.

When the N odd-degree vertices are found, there are $n \choose \frac{n}{2}$ possible ways to split them into two sets. Does Christofides' algorithm really need to run a min-weight bipartite matching for all of these possible partitions? Or is there a better way?

I realize there is an approximate solution, which is to greedily match each vertex with another vertex that is closest to it. However, if the exact solution is to try all possible partitions, this seems inefficient.

There is the Blossom algorithm by Edmonds that determines a maximal matching for a weighted graph.


What is the Space Complexity of Tail Recursive Quicksort? Looking at the following tail recursive quicksort pseudocode

QuickSort(A[1, ..., n], lo, hi)
Input: An array A of n distinct integers, the lower index and the higher index
         // For the first call lo = 1 and hi = n
Output: The array A in sorted order

If lo = hi return
         // The array A is already sorted in this case
If lo > hi or indices out of the range 1 to n then return

Else
      Pick an index k in [lo,hi] as the pivot
              // Assume that this can be done using O(1) cells on the stack
      i = Partition(A[lo, ..., hi], k)
              // Use in-place partitioning here so assume that this can be done
              // using O(1) space on the stack

If i - lo <= hi - i
      QuickSort(A, lo, i-1) // sort the smaller half first
      QuickSort(A, i+1, hi)
Else
      QuickSort(A, i+1, hi) // sort the smaller half first
      QuickSort(A, lo, i-1)

Assuming that the pivot is chosen adversarially each time I analyzed that it should have a space complexity of O(logn) [which I am not entirely sure is correct], but how would the space complexity be affected if the pivot is then chosen uniformly at random? I am fairly new to understanding space complexity over time complexity, so any feedback is appreciated!

If you either use a compiler that supports tail recursion, or make the small change not to use recursion for the larger partition at all, the recursion depth depends on the sizes of the smaller intervals.

The worst case for recursion depth is the case that each partition divides your subarray exactly in half, making the depth $log_2 (n)$. The best case for recursion depth is the case that each partition divides your subarray into n-1 and 1 items, recursion depth = 1 (obviously the absolutely worst case for execution time).

So this is a bit paradoxical: Best case space complexity = worst case time complexity. But on the other hand, worst case space complexity = log n is so little that nobody cares about the space complexity. As long obviously as people don't make the mistake of sorting the larger partition first.

Without eliminating the recursion for the larger half, the worst case for recursion depth is n, and the order of the calls doesn’t matter.

Usually you can’t make an assumption that values would be different, so the quality of your partition function is important. Some will misbehave with many identical values.


Finding minimum number of edges such that when adding into the graph, the graph is a 2-connected graph Given is a undirected and 1-connected graph G=(V,E). Between every two node b=(u,v) in graph G there is a cost c_b to build another edge(Regardless of whether (u,v) ∈E or not). We use a C={c_b |c_b∈Z^+,b∈V×V} to represent costs between every node regardless of whether (u,v) ∈E or not. Now, we want to add some edges M⊂E into the graph G which makes graph G^'=G+M is a 2-connected graph (G^' allow the appearance of multiple edges while graph G is not) such that weights of edge set of M is minimize.

$2$-connectedness is the same as bridgeless.

So $M$ must be the set of bridges in $G$ no matter how large or small their sum is.


Running Time of naive implementation of Dijkstra's Algorithm Here is the "naive" implementation of Dijkstra's algorithm that the professor uses:

For a directed graph $G = (V,E)$ as input
Initialize:

$X = \{s\}$   (the vertices processed so far)

$A[s] = 0$   (computed shortest path distance)

$B[s] = empty path$  (computed shortest path)

Main Loop:
While $X \neq V$:

Among all edges $(v,w) ∈ E$ with $v ∈ X$, $w \notin X$, pick the one that minimizes $A[v] + \ell_{vw}$, where $\ell_{vw}$ is the length of the edge between $v$ and $w$. Call this edge $(v^*,w^*)$ .

Add $w^*$ to $X$.

Set $A[w^*] = A[v^*] + \ell_{u^*w^*}$.

Set $B[w^*] = B[v^*] \cup \{(v^*w^*)\}$.

The running time for this is given as $O(nm)$, where $n = |V|$ and $m = |E|$. I don't fully understand why. He says $n$ is the number of loop iterations, which I understand, but that $m$ is the work per iteration (a linear scan through edges to compute the minimum). But if it's doing $m$ work per iteration, that would imply that it's looking at every single edge in the graph, when it should only be looking at edges that cross the "frontier" between $X$ and $V - X$. Can someone clear up my confusion?

In each iteration we need to go over all edges crossing the cut $(X,V\setminus X)$. The algorithm doesn't explain how we do that, so it is difficult to analyze the exact running time, though $O(m)$ per iteration is definitely an upper bound. A naive implementation will presumably go over all edges, checking which of them cross the cut, and for this implementation, the running time will indeed be $\Theta(m)$ per iteration.


Universality of NOT and CNOT I'm trying to figure out why NOT and CNOT gates are not sufficient to create all bijective functions in classical circuits. I have been struggling on this for hours, and just can't make sense of it.

I feel it has something to do with the Toffoli gate, as it contains an (implicit) AND operation, and I feel that's what missing in the NOT and CNOT gates. However I can't find a proper way to actually 'show' this.

Edit: This is a proof for the non-quantum version.

Suppose we want to compute $x \land y$ from $x,y,0,1$ using the operations NOT and CNOT (=XOR). Prove by induction that any such expression is equal to one of the following forms:
$$ 0,1,x,y,\lnot x, \lnot y, x\oplus y, \lnot(x\oplus y). $$
It is more helpful to write it in the form $ \alpha \oplus (\beta \land x) \oplus (\gamma \land y)$, where $\alpha,\beta,\gamma \in \{0,1\}$. Yet more helpful is to switch notation so that this expression is written $\alpha + \beta x + \gamma y$; this should be suggestive enough.


Variant of the Knapsack Problem I've got problem on integer programming, specifically with the following knapsack problem. I'd be happy to get some suggestions on how to solve the problem in a time efficient way.

There are 120 items $i$, each with weight $w_i$ and the value $v_i$. Each item can be selected only once (or zero times). For each of them one has to chose a quality level ($a$, $b$, $c$, $d$ or $e$).
The higher the level, the higher is its weight and its value. Both are precalculated for all items and stored in matrix.

Now the question is, given a capacity $W$, how to get the optimal levels for each of the items. Since the item set is relatively huge, the aspects of computational complexity might be of special relevant, I guess.

Can you tell me which algorithms can be use for this variant of the knapsack problem? Thanks a lot!

If you set both the values and the weights of each item corresponding to the lowest four levels to $0$, this problem is exactly the standard knapsack problem, so it is no easier than the standard knapsack problem, i.e. it is NP-hard.

You can use the dynamic programming algorithm for the standard knapsack problem to solve this problem, except that you should consider six cases instead of two: the item is not chosen, or its level $a,b,c,d$ or $e$ is chosen, then take the maximum value. The complexity is $O(nmW)$ where $m$ is the number of levels.


Prove that A* is the smallest reflexive and transitive set containing A I'm trying to learn automata theory on my own and I am running into an issue with the second part of the question:

We say B is transitive if $BB\subseteq B$ and reflexive if $\epsilon \in B$

  Show that A* is a reflexive and transitive set containing A and if B is any other reflexive and transitive set containing A, then $A^*\subseteq B$.

I've shown that Kleene star satisfies these two conditions. I've tried partitioning B into two sets with $A = B \cup C $ and trying a constructive proof but this hasn't led any where. I also am considering a proof by contradition but don't know where to start.

Can you help me with a hint on how to approach this problem?

Hint: Try the usual approach to show set inclusion! That is, pick $w \in A^*$ and show that $w \in B$.

Next hint:

   Apply transitivity of $B$ repeatedly.

More elaborately:

   If $w \in A^*$ then either $w = \varepsilon \in B$ or there are $w_1, \dots, w_k \in A \subseteq B$ with $w = w_1 \cdot \dots \cdot w_k$. Now, because $BB \subseteq B$ we have $w_2' = w_1 w_2 \in B$. For the same reason, $w_2' w_3 \in B$. And so on. Perform induction for the general proof.


Is $L_p$ decidable when p is a trivial property? If

$\qquad\displaystyle L_p = \{ \langle M \rangle : p \in P(L(M)) \text{ s.t. } p \text{ is a specific trivial property} \}$,

where a trivial property is a property that is shared by all recursively enumerable languages or is not a property of any recursively enumerable language, is it implied that $L$ is decidable?

If $p$ is a trivial property of r.e. languages, it either applies to all r.e. languages or applies to no r.e. language. That means that either

$L_p$ is the set of all TM descriptions or
$L_p=\emptyset$.

In the first case, a decider for $L_p$ ignore the input $\langle M\rangle$ and immediately accept and in the second case, a decider would similarly reject. In either case, $L_p$ is clearly decidable. While we don't necessarily know which decider is the right one to use, that doesn't matter, since the existence of a decider is all that we need.


Vertex deletion to perfect matching You are given a Graph G and an integer k.

The question is: Does G contain a vertex set X of size at most k such that deleting X results in a graph of degree at most 1?

Design an FPT (or a kernelization) algorithm for this problem and argue why it is correct.

Hint: Observe that vertices of higher degree must be "dealt with" somehow.

I do not exactly know where to start. I suppose that some reduction rules can be applied first, but not so sure what those can be (probably something that "deals with" vertices of higher degree.

Any ideas?

I'm not sure about the FPT algorithm, but I have an idea for the kernelization.

All vertices with degree > k + 1 must be in X, since otherwise you would have to pick all but one of its neighbours which would make |X| > k. So you can delete a vertex with degree > k + 1 and rerun the algorithm with the remaining graph and k = k - 1.

You can also delete any vertices with degree 0, as their deletion doesn't change the degree of any other vertices.


Sorting an array where the largest element appears once, the second largest appears twice and in general the $k$-th element appears $2^{k-1}$ times I need to find a sorting algorithm to sort an array where the the $k$-th element appears $2^{k-1}$ times in $O(2^k)$.
It also given there are $k$ distinct elements in the array, hence there are $1 + 2 + 2^2 + \dots + 2^{k-1}=2^k-1$ elements in the array. So I actually need to sort the array in $O(n)$ where $n$ is the array size.
Not sure how to use the known quantity of each element to sort faster.
Any help is appreciated.

If I understand correctly the title (which is a bit clearer than the post itself), an example of such an array would be $[1, 4, 1, 2, 1, 2, 5, 2, 1, 1, 4, 1, 2, 1, 1]$.
If that's the case, you can:

Count the number of occurrences of each value, with a hashtable for example;
Sort the unique values with descending order of occurrences;
Recreate the sorted array by repeating each value by the number of occurrences.

This algorithm is indeed in time complexity $O(n)$, since the array contains only $\log_2 (n+1)$ unique values. That means that even the worst case of operations in the hashtable is in complexity $O((\log n)^2)$, and sorting the unique values array can be done in $O(\log n \log \log n)$. The last step is done in $O(n)$.


Proof for Turing Machines being able to simulate any algorithm in the same time complexity I have always read that Turing machines can simulate any algorithm, without changing the time complexity of the algorithm, and hence it is easier to study the Turing machine equivalent of the algorithm while doing proofs.

However, I am unable to find a proof for this statement. Is there a formal proof of why the Turing Machine model should be able to simulate any algorithm within the same time complexity?

This is not a formal statement, but either a definition or an empirical observation. The full claim is something like the following:

"A reasonable model of computation (for discrete data) together with a reasonable notion of time complexity will have the property that it can be simulated by a Turing machine with at most polynomial increase in time complexity."

The two occurances of "reasonable" here are generally not seen as formal notions, but rather as informal notions. We can trivially define models of computation with notions of time complexity not having the property above, but these models do appear artificial. On the other hand, models people actually want to use have the property.

Any attempt to formally define what a "reasonable model of computation with time complexity" is would probably include the possibility of polytime-simulation by a TM as an axiom.


Regular Language $a^n b^m c^k$ to Context free grammar I am trying to convert a regular language to a context free grammar. The language is $L=\{a^n b^m c^k |n=m\ or\ m\le k\}$, my solution is: assume $m,n,k\ge0$

$S\to AS|BS|\lambda$

$A\to aAb|Ac|ab$

$B\to Bc|Bbc|aB$

Is this correct? Can somebody explain  why it is correct or not correct?

Let us get things straight...the language $L$ is not regular (you can check using Pumping lemma) Although the language is Context Free as it is the union of two CFLs.

The grammar does not correspond to the language since the non-terminal $B$ can not be terminated. So  only way to termiante it and get a word of the language is $S=A^*$. But $A=aAb=aAcb=aabcb\notin L$

Correct grammar should be

$$S\to A|B$$
$$A\to Ac|aAb|\lambda$$
$$B\to aB|bBc|Bc|\lambda$$

Two non terminals $A$ and $B$ for the two CFLs whose union is $L$.


Given a complete, weighted and undirected graph $G$, complexity of finding a path with a specific cost Given a fully connected graph $G$, suppose that we are searching for a simple path $P$ with a specific cost $c$.

Is answering to that problem yes or no equivalent to subset-sum problem?
What would be the complexity of finding such path?

I have made a reduction from subset-sum problem:

If each number in a set $S$ is a vertex of $G$ and weight of $<i,j>$ is $|i-j|$, then answering the question above yes or no is the same as solving the sumbet-sum problem.

P.S. The initial vertex I have visited is added to the cost.

Edit: Edge weights

Given an instance $\langle \{s_1,\ldots,s_n\}, T \rangle$ of subset sum, construct the following weighted graph. The vertices are
$$ v_0,v_1,\ldots,v_n,u_1,\ldots,u_n. $$
Connect $v_{i-1}$ and $v_i$ with an edge of weight $s_i$. Connect $v_{i-1}$ to $v_i$ via $u_i$ (i.e., add the edges $\{v_{i-1},u_i\},\{u_i,v_i\}$) with zero weight edges. There is a simple path of total cost $T$ iff there is a subset of $\{s_1,\ldots,s_n\}$ summing to $T$. This shows that your problem is NP-hard, and in fact NP-complete, since it's clearly in NP.


Longest path in DAG or finding DAG diameter A directed acyclic graph (DAG), is a directed graph with no directed cycles.

That is, it consists of vertices and edges, with each edge directed from one vertex to another, such that there is no way to start at any vertex v and follow a consistently-directed sequence of edges that eventually loops back to v again.

we have several algorithms to finding shortest path from one vertex to another(Dijkstra algorithm and Bellman-ford algorithm)
or such algorithms to find shortest path from every to vertices( floyd-Warshall algorithm and Johnson algorithm)

But which method could help us to find the maximum path between all two vertices and pick the maximum one as graph Diam.

here we have a DAG so there is no cycle with
Positive edge weight to drop in infinite loop for finding longest path. and we could use many other features in DAG.

Is any polynomial time order algorithm for this problem....?

thanks

But which method could help us to find the maximum path between all two vertices and pick the maximum one as graph Diam.

That's not how the diameter is usually defined; it's rather the maximum distance, i.e. the length of the longest shortest path. As such, any general-purpose APSP algorithm helps you find the diameter of DAGs.

  here we have a DAG so there is no cycle with Positive edge weight to drop in infinite loop for finding longest path.

Infinite loops are not the problem; finding longest paths is NP-hard in general graphs.

  Is any polynomial time order algorithm for this problem....?

As explained on Wikipedia [1], the Longest Path problem can indeed be solved efficiently on DAGs by finding the shortest path in the graph obtained by multiplying all weights by $-1$.

Algorithms by R. Sedgewick and K. Wayne (2011)


Show that for any real constants $a$ and $b$, where $b > 0$, $(n + a)^b = \Theta(n^b)$ I'm currently studying growth of function chapter in Introduction to Algorithm. In exercise 3.1-2 the question is:

  Show that for any real constants $a$ and $b$, where $b>0$,
  $(n + a)^b = \Theta(n^b)$.

I understand I need to find constants $c_1$, $c_2$, $n_0 > 0$ where

  $0 \leq c_1n^b \leq (n+a)^b \leq c_2n^b$ for all $n \geq n_0$.

But I don't understand what should I do after above step. Looking at the solution, it shows

  $n + a \leq n + |a|$
  $n + a \leq 2n$, when $|a| \leq n$

and

  $n + a \geq n - |a|$
  $n + a \geq \frac{n}{2}$ , when $|a| \leq \frac{n}{2}$

How did they come up with $n + a \leq n + |a|$ and $n + a \geq n - |a|$ just from $0 \leq c_1n^b \leq (n+a)^b \leq c_2n^b$ ? Are they derived from $0 \leq c_1n^b \leq (n+a)^b \leq c_2n^b$  ? Or are they just a general knowledge that can help solve this problem?

Please help me to understand them.

Thank you!

UPDATE:
I have updated the question to be more specific.

I understand I need to find constants $c_1$, $c_2$, $n_0 > 0$ where
$0 \leq c_1n^b \leq (n+a)^b \leq c_2n^b$ for all $n \geq n_0$.
But I don't understand what should I do after above step.

The approach you would like to use here is "going backwards from the target".
Suppose we do have $c_1n^b \leq (n+a)^b$ for some constant $c_1\gt0$ when $n$ is large enough. What can we understand or deduce from it? What is needed to make it true?
Since the exponent is the same, we can use the law of same exponent, $(x/y)^m = x^m/y^m$ to simplify that inequality so that we will have the appearances of our variable $n$ closer to each other.
$$  c_1\leq \frac{(n+a)^b}{n^b}=\left(\frac{n+a}n\right)^b$$
Raising both sides to the power of $\frac1b$, we have
$$  (c_1)^{\frac1b}\leq \left(\frac{n+a}n\right)^{b\,\frac1b}=\frac{n+a}n = 1+\frac an$$
(Another way to obtain $(c_1)^{\frac1b}\leq\frac{n+a}n$ is to raise both sides of $c_1n^b \leq (n+a)^b$ to the power of $\frac 1b$.)
Since $c_1$ is a positive constant, $(c_1)^{\frac1b}$ is also a positive constant. To make the above inequality hold, we would like to make $\left|\frac an\right|$ small enough.  For example, we can require $\left|\frac an\right|\le \frac12$. That is why you see the following condition.
$$|a|\le\frac12 n$$
What is nice here is that we can reverse the above argument to obtain a wanted constant $c_1$. Note that it is just as fine if we choose a different condition such as $|a|\le\frac13 n$ or  $|a|\le\frac1{2019}n$ or infinitely many others.
If we start from $(n+a)^b \leq c_2n^b$, we could arrive at $|a|\le n$.

Are they derived from $0\le c_1n^b\le(n+a)^b\le c_2n^b$ ? Or are they just a general knowledge that can help solve this problem?

Yes, they are derived as you have just seen. You could say that they are general knowledge that helps solve this problem. You could also say that we just discovered some specific facts that help solve this problem.


Understanding a formula on article I just read an article  "Statistical approach for figurative sentiment analysis on Social Networking Services: a case study on Twitter", which provide an algorithm to analyze tweets, and this article includes 2 formulas which I don't really understand.

Link to the article

I hope maybe someone here can help me.

The first formula is the (4) formula (Page 5)
The second formula is the (6) formula (Page 8)

I will be very thankful if someone will help me with this.

Examples will be most welcome! :)

Each tweet and each cluster is represented as an $m_k$-dimensional vector. The distance between a tweet $t_k$ and a cluster $\delta$ is then
$$
dis(t_k,\delta) = 1 - \frac{\langle t_k, \delta \rangle}{\|t_k\| \|\delta\|},
$$
where $\langle a,b \rangle = \sum_{i=1}^{m_k} a_i b_i$ is the inner product and $\|a\| = \sqrt{\langle a,a \rangle}$ is the norm. This explains equation (4).

The definition of $P(S_t|w)$ is given below (6):

  $P(S_t|w)$ is the
  probability that a term has a score with the given tweet score.

This is the number of tweets containing $w$ which have score $S_t$ divided by the total number of tweets containing $w$.

The rest of the formula is hopefully self-explanatory ($\times$ is just ordinary multiplication).

If you have any more questions, I suggest contacting the authors.


When a NPDA is constructed from CFG, how many internal states will be used for accepting any string from the grammar? Options given were:

  (a) 2  (b) 3  (c) 4  (d) 5

This question was a part of my assignment. I think the answer is 2 internal states - one start state and the other end state/acceptance state, but I am not sure whether it is correct or not.
Please correct me if I am wrong.
Thanks.

The answer depends.

For every CFG we can construct an equivalent PDA with empty stack acceptance that has just a single state.

The construction is mentioned in wikipedia. We have single state $1$. For every grammar production $(A\to \alpha)$ add an pda instruction "expand" $(1,\epsilon,A,1,\alpha)$ which means "pop $A$ and push $\alpha$ without reading input". Additionally we have "match" instructions $(1,a,a,1,\epsilon)$ which means "when symbol $a$ is on top of the stack, we must read it from the input, while popping it from the stack".
The initial stack symbol is $S$, the axiom of the grammar.

If we instead want final state acceptance then we need to distinguish a final state, so it is necessary to use two states.

Use a new initial stack symbol $Z$ to mark the bottom of the stack.
Just add two instructions, one to push $S$ on the stack $(1,\epsilon,Z,1,SZ)$, the other to move to the accepting state $f$ when the empty stack is reached $(1,\epsilon,Z,f,\epsilon)$.

This however assumes the automaton model that I was brought up with. Certain books do not agree, and consider PDA that start with an empty stack (brrr). In that case an additional state is used to start and push $Z$ onto the stack, so we need three states.


Relating memory complexity and decidablity Given a language $L_u$, about which we know that there exists a non-deterministic turing machine which accepts it (as in, implying $L_u \in RE$) with memory complexity of $c^{p(n)}$, where $c$ is a constant and $p(n)$ a polynomial, can we decide whether $L_u \in R$ or not?

Memory complexity represents the largest difference of indices of used slots of the tape. So I believe $L_u \in EXPSPACE$, although here it is defined using a constant, whereas most articles use a 2 to the power of some polynomial. This is why I'm not sure about that fact.

Basically, what I'm asking is:

Is $L_u \in EXPSPACE$?

If it is, can this fact be used to derive whether $L_u \in R$, and how?

If not, how can the fact that $L_u \in RE$ and that the turing machine has a memory complexity of $c^{p(n)}$ be used to determine whether $L_u \in R$, and how?

Any language accepted by a non-deterministic Turing machine is decidable, since non-deterministic Turing machines can be simulated by deterministic Turing machines. See for example the Wikipedia article.

There is some subtlety you might be worried about: the non-deterministic Turing machine might always halt (on a given input), but its running time could be unbounded, and then the trivial simulation which just tries all possible guesses wouldn't halt. Fortunately, König's infinity lemma shows that if the running time is unbounded, then there is some infinite computation, so the running time must be bounded.


why don't we use machines with random access memory as our basic model of computation? Turing machines are perhaps the most popular model of computation for theoretical computer science. Turing machines don't have random access memory, since we can only do a read where the slider is currently located.

This seem unwieldy to me. Why don't theoretical computer scientists use a model with random access memory, like a register machine, as the basic model of computation?

Why don't theoretical computer scientists use a model with random access memory, like a register machine, as the basic model of computation?

The short answer is that this model is actually more complicated to describe and prove things about. "Jumping" from one place in memory to another is a more complex operation. Note that it requires:

Reading an address (requires that we define how the address is written on the tape)
Jumping to where that address says on the tape

Alternatively I'm not sure what you have in mind by "register machine", but this also requires care. How large can the registers be? And the machine then has separate mechanisms for how it accesses/modifies the registers, and how it accesses/modifies main memory.

In sum, it's a more complicated model and Turing machines are easier to deal with.

However, the long answer is that theoretical computer scientists do use a model with random access memory, in real practice: it's called the RAM (Random Access Machine) model. The Turing machine is not considered to be a good model for so-called "fine-grained complexity" (e.g. whether a problem can be solved in $O(n^2)$ or $O(n)$ time), and so this requires more careful models. The RAM model is standard and perhaps, arguably, more accepted than the Turing machine as a model of how real computers work, despite being more complicated.

For example, we can show that for a Turing machine to decide if two strings are equal requires $O(n^2)$ time. But this of course does not hold in more accurate models of computation like the RAM model, where it will take $O(n)$. Therefore:

If you just care about whether a problem can be solved at all (or whether it can be solved in polynomial time), Turing machines are considered sufficient.
But if you care about exactly how difficult it is to solve, then you have to resort to a more complex model, such as RAMs.


Set Intersection with asymmetric set sizes I'm looking for an algorithm to perform set intersection where set $N_1$ is very small and set $N_2$ is very large.

Due to the constraints of the problem I am solving, I cannot rely on an algorithm which sorts or depends on sorted elements.  Further, the simple method of performing $N_1$ hash look ups in a hash table of size at least $N_2$ will also not work.

Are there any non-naive approaches to this problem that I am missing?
They do not have to be as efficient as either approach, but obviously the more performant the better.

Edit:  Since my constraints were a bit vague, I'll go ahead and spell them out.

The application I have in mind is one type of MPC. Here, I would like to perform a set intersection while neither party reveals anything about the elements that are not in the intersection. One party will be performing the comparisons, and the other party will be transmitting the elements of their set in an encrypted format.

Sorting is out because an encrypted value cannot be evaluated for anything besides equality. Doing so would either reveal more about the elements in the set or would come with significant computational overhead.

Hash table look ups have great promise, but all approaches involving them require that both parties pretend they have a set size of $max(N_1, N_2)$. The most effective way to optimize the communication between the parties is hash tables, but privacy requires inserting enough false elements so that each bin of the hash table has the same number of items.

Bloom filters also suffer from similar problems as hash tables.  To be correct and secure, the size of the smaller bloom filter must be large enough to fit the larger set.

I'm really just looking for a fundamentally different algorithm that I can use to design a different approach to the problem. I would like for the communication and computation to be dominated by the size of the smaller set. I recognize that this is a research problem that no one will have a perfect solution to. Instead, I am trying to find different types of structure that can be used to improve on the naive approach.

If you have exactly one intersection to compute, building a hash table from $N_1$ and doing $N_2$ lookups goes through the same number of hash operations as building one from $N_2$ and doing $N_1$ lookups.


Arithmetical Hierarchy, show $\Sigma_1$ is Turing recognizable I'm new learning Arithmetical Hierarchy, my question ask to show that $\Sigma_1$ is Turing recognizable.
I'm not sure what's the general way to approach this, but I noticed $A_{TM}$ is in $\Sigma_1$ by described in follows.

First note $\Sigma_1$ = the language of the form $\{x | \exists y R(x,y)\}$, where $R(x,y)$ is decidable predicate.

$A_{TM}$ = $\{\big \langle M, w \big \rangle| \exists t [M \text{ accept $w$ in $t$ steps}]\}$, where $M \text{ accept $w$ in $t$ steps}$ is decidable predicate.

$A_{TM}$ = $\{\big \langle M, w \big \rangle| \exists t T(\big \langle M \big \rangle, w, t)\}$

So we show that $A_{TM} \in \Sigma_1$, but does it sufficient to show that $\Sigma_1$ is in r.e.? Any suggestion?

Suppose that $L = \{x \mid \exists y R(x,y)\}$, where $R(x,y)$ is a decidable predicate.

To recognize $L$, given an input $x$, enumerate all possible $y$, and check whether $R(x,y)$ holds for at least one of them. This will halt iff $x \in L$.


Questions about an answer to a pumping lemma question for CFLs In the answer to this question, I'm not understanding how the string is derived for a given $l$.

For example,

  Case 1: $vx = a^i$ where $i > 0$. Choose $l = 2$ to get $a^{n+i} b^{n+1} c^{n+1} d^n \notin L$.

Why is $l = 2$ chosen and how is $a^{n+i}b^{n+1}c^{n+1}d^n$ derived from $l = 2$?

Also, how can $vx$ be chosen instead of $vwx$ as the OP chose? What do we do about $w$? Is it the empty string?

The essential idea is that pumping lemma tells you about string $uv^lwx^ly$ with $l \geq 0$. That is, you can "pump" to $uwy$, if $l = 0$, that way shortening the initial string.

The answer considers the string $a^n b^{n+1} c^{n+1} d^n$. Removing a single $b$ or inserting a single $a$ would move the string out of the language. Removal and insertion correspond to $l = 0$ and $l = 2$.

The answer only considers $vx$, because $w$ does not matter - it will not be pumped.

If $v$ or $x$ contains any $a$s, double them to get more $a$s then $c$s. If $v$ or $x$ contains any $b$s, remove them to get fewer $b$s than $d$s. $v$ and $x$ will never contain both $a$s and $c$s, because $|vwx| \leq n$. Same is true about the other pair of symbols.


Using diagonal argument to prove that $H(x) = \mu y T(x,x,y)$ has no total computable extension Hello everyone just like the title says I want to prove that $H(x) = \mu y T(x,x,y)$ has no total computable extension such that if we had a function $BIG(x)$ that is both total and agrees with $H(x)$ whenever $H(x)$ is defined, then $BIG(x)$ is not computable. This is a homework question so I don't want a full solution just some help!

$\bf{NOTE}:$ The predicate $T(y,x,z)$ means that it holds iff program $y$ takes an input $x$ (could be $n$-ary) and has a computational history z! This is supposed to be the Kleene T predicate basically.

The function $H(x)$ I believe returns the smallest computational history $y$ such that a program $\{x\}(x)$ (program takes input of its own configuration and runs) runs and halts, since $\mu y R(x,y)$ means the smallest $y$ such that $R(x,y)$ holds. Maybe I am not quite clear what it means for $BIG$ to agree with $H(x)$ or what it's own input. I think I need to create a diagonal function that uses $BIG$ if $BIG$ was computable and show that if I had some program $e$ then it must agree with $BIG$ but based on my definition of that diagonal function it isn't. If you are reading this you might see the mess of my thinking, any help would be greatly appreciated!

(This answer assumes my conjectural interpretation of the predicate $T$.)
The function $H(x)$ is given by
$$
H(x) = \begin{cases} t & \text{if program $x$ run on input $x$ halts after $t$ steps} \\ \bot & \text{if program $x$ never halts when run on input $x$} \end{cases}
$$

Hint: Given a total computable function extending $H$, show how to solve the halting problem. There is no need to use diagonalization – this is already taken care of in the proof that the halting problem is undecidable.


How to detect infinite loop exist in linear bounded automata (LBA)? The following theorem from Michael Sipser's book "Introduction to the Theory of Computation" states:

  $A_{\textrm{LBA}}= \{ \langle M, w \rangle \mid \text{$M$ is an LBA that accepts string $w$} \}$.

  THEOREM: $A_{\mathrm{LBA}}$ is decidable.

On the proof part, it states:

  The idea for detecting when $M$ is looping is that as $M$ computes on $w$,
  it goes from configuration to configuration. If $M$ ever repeats a
  configuration, it would go on to repeat this configuration over and
  over again and thus be in a loop.

I do not understand this:
"If $M$ ever repeats a configuration, it would go on to repeat this configuration over and over again". What if $M$ only repeat one configuration, then halts?

The machine $M$ is deterministic. This means that, if $M$ is in a certain configuration $c$, then there is a single fixed configuration $c'$ (determined by the rules of $M$) which the execution of one step will lead it to. If $M$ ever reaches the configuration $c$ again, then the configuration $c'$ will follow no matter what. Hence, if the computation of $M$ causes it to be assume configurations $c_1, \dots, c_n$ and $c_n = c_1$, then $M$ will repeat the loop $c_1, \ldots, c_n$ indefinitely.


Is a perfect matching's weight less than MST of a metric graph? This is part of a bigger proof I'm trying to solve, which eventually came down to one thing:

Let $G=(V,E)$ an un-directed, complete, metric graph (maintains the triangle inequality) with an even number of vertices. Let $PM$ denote a minimum-weight-perfect matching on $E$ and let $MST$ denote a minimum-spanning-tree of $G$.

Is it true that $w(PM) \leq w(MST)$ ?

I'm not sure if the fact that the graph is metric is useful, but I have pointed that out any way.

I know $PM$ and $MST$ do not necessarily share all edges, but maybe some of them? I was trying and couldn't find a counter-example to disprove this.

My gut says it's true, but I cannot find a definitive way to prove it.

Given any spanning tree, here is how to construct a perfect matching with weight no larger. We consider two cases.

Case 1. The tree has some leaf $\ell$ which is an only child of its "parent" $x$. In this case we add $(\ell,x)$ to the matching, delete the vertices $\ell,x$, and continue.

Case 2. The tree has some leaf $\ell_1$ which has a sibling $\ell_2$. Let the common "parent" be $x$. The triangle inequality shows that $w(\ell_1,\ell_2) \leq w(\ell_1,x) + w(\ell_2,x)$. Accordingly, we add $(\ell_1,\ell_2)$ to the matching, delete the vertices $\ell_1,\ell_2$, and continue.

At each point in time, the remaining graph is always a tree, and the removed vertices are covered by a matching. Furthermore, the cost of the matching is always at most the cost of the edges removed from the tree. Eventually all the vertices will be exhausted, and we will be left with a perfect matching whose cost is at most the cost of the tree.


Finding an instance of an n-element set cover Below is a homework problem where we have been asked to alter a greedy algorithm to return n element instance of a set problem. The original algorithm is also below. I was thinking that I could alter line 3 so that it would run until the size of C was equal to n, and change the logic in line 4 so that it would pick and remove vertices until the size of n. A vertex would be removed when the size of C doesn't equal to n but the cover is complete. I can't really think of any other way to do it. The real problem is that I'm not entirely sure how to make the algorithm run in exponential time like they are asking.

  GREEDY-SET-COVER can return a number of different solutions, depending on
  how we break ties in line 4. Give a procedure BAD-SET-COVER-INSTANCE.n/
  that returns an n-element instance of the set-covering problem for which, depending
  on how we break ties in line 4, GREEDY-SET-COVER can return a number of
  different solutions that is exponential in n.

  $X$ — some finite set
  $F$ — a family of subsets of $X$
  $C$ — cover being constructed

  GREEDY-SET-COVER($n$)
  1    let $U = X$
  2    let $C = \varnothing$
  3    while $U \ne \varnothing$
  3a            select an $S \in F$ that maximizes $\left|S \cap U\right|$
  3b            set $U = U \setminus S$
  3c            set $C = C \cup \{S\}$
  4    return $C$

Could it be said that since the number of subsets a set has is $2^n$ and that in the worst case this algorithm will end up finding all of those subsets before settling on an n-instance set to return?

I think you are being confused by the way the question is phrased. The question asks for a sequence of instances $I_n$, consisting of triples $\langle X_n,F_n \rangle$, such that $|X_n| = n$ and GREEDY-SET-COVER$(X_n,F_n)$ could have $C^n$ many results, for some constant $C>1$. These results come from the fact that at step 4 there could be many sets that are eligible.

For some reason, the question asks you for an algorithm which generates the sequence: given $n$, it should output $\langle X_n,F_n \rangle$. Since the instances you are going to construct will be pretty simple, you should have no problem writing an algorithm that generates them, but in fact no one cares about this algorithm; the point is only that these "bad" instances exist (they're not actually bad, mind you).

The easiest way to construct these instances is to use a gadget, say $F_3 = \{(1,2),(1,3),(2,3)\}$. You can check that running the greedy algorithm can result in three different covers. I'll let you continue from here.


Remove x last elements of an array and reinsert them before position y I am looking for an algorithm to move a subarray in before an element (which is not part of that subarray) in the same array where the last element of the subarray is the last element of the array with O(1) extra space and O(n) runtime.

e.g. where *p1 = 5 and *p2 = 3:

1 2 5 6 7 3 4

becomes

1 2 3 4 5 6 7

This is what I have so far (written in C programming language). Trouble arises when p1 reaches p2.

void swap(long* p1, long* p2, long* array_end) {
  long* p2_i = p2;
  while (p1 < array_end) {
    if (p2_i > array_end) {
      p2_i = p2;
    }

    // swap *p1 and *p2_i
    long* temp = p1;
    *p1 = *p2_i;
    *p2_i = temp;

    ++p1;
    ++p2_i;
  }
}

We can assume without loss of generality that $y$ is the first position, and that the first position is zero. Suppose that there are $n$ elements in the array. Then we want to apply the permutation $\pi(i) = (i+x) \pmod n$. Two elements $i,j$ are in the same cycle of $\pi$ if $i \equiv j \pmod {(n,x)}$, which means the the cycle leaders (minimum elements of each cycle are $0,\ldots,(n,x)-1$. In other words, for each $j < (n,x)$, we need to consider the elements
$$
A[j],A[j+x],A[j+2x],\ldots,A[j+(n/(n,x)-1)x]
$$
and rotate them one step to the right. This can be done using constant memory, and takes time $O(n/(n,x))$. Overall, the running time will be $O(n)$.

You don't actually need to determine $(n,x)$. Instead, you can simply count how many elements were touched. For example, you can consider the following pseudocode:

touched = 0
current = 0
while touched < n:
    origin = current
    element = A[current]
    repeat:
        current = (current + x) mod n
        swap A[current] and element
        touched = touched + 1
    until current = origin
    current = current + 1
end while


Proof of P-Hardness by reduction I want to proof the P-Hardness of a language. Why is it enough to make a reduction-proof from an other, already P-Complete known language?

By definition, a language $L$ is P-complete if for every language $M \in P$ there is a logspace reduction $f_M$ such that $x \in M$ iff $f_M(x) \in L$. Now suppose that $L$ is P-complete and that for some language $L' \in P$ there exists a logspace reduction $g$ such that $x \in L$ iff $g(x) \in L'$. Then for every language $M \in P$, $x \in M$ iff $g(f_M(x)) \in L'$, and so $L'$ is P-hard since the composition of logspace reductions is a logspace reduction.

Generalizing, this sort of argument always works as long as the composition of two legal reductions is a legal reduction. This is the case for both polynomial time reductions and logspace reductions.


Connection between vertex cover and P=NP I read about vertex cover and i can't understand why the following occurs. Tried to look and research on the site and in other places but still can't understand it.

In an undirected graph $G(V,E)$, vertex cover is a set of edges U so that every Edge in E has at least one end at U.

Defining the following function: $f(G,v)$ equals to the minimal vertex cover that v belongs to.

Why if it is possible to calculate in a polynomial time  the function $g(G,v)$ and it is guaranteed that $f(G,v) -5 \leq g(G,v) \leq f(G,v) +5$ then P=NP?

(Meaning if we can estimate f in a constant boundary of +5 in a polynomial time, then P=NP?)

What i think:since vertex cover is an NP-COMPLETE language, and so is the minimal vertex cover, if it is bounded by +-5, a linear bound. then if known that $g(G,v)$ can be calculated in polynomial time and we can also show that it's boundaries are $f(G,v) - 5$ and $f(G,v)+5$, then P = NP.

So regarding minimal vertex cover, the problem is $min(f(x)| x \in vertexcover(G))$. so an algorithm for minvertexcover is: initialize {cover<-0, Edges<-0}; until there are no more edges $e \in E$ in G: 1)add u,v to cover; 2)add $e_i$ to Edges; 3)remove u,v from G and adjacent edges.

Now, since $|Edges = 2 * cover|$, then for a possible solution, meaning vertex cover that covers all the edges, that possible solution will be more than Edges, so that possible solution will be bigger than 2 * Edges.

Since that possible solution $\geq 2 * Edges$, it means that the possible solution is $\geq f(G,v) + 5$, so it is bounded. now if we can calculate $g(G,v)$ in a polynomial time, it means we can calculate the possible solution in at least 2 * polynomial time, which is still polynomial. so it means that if $g(G,v)$ can be calculated in polynomial time, and the given +-5 boundary exists, then P=NP.

How to prove it correctly and efficiently? spent long days on it and would appreciate seeing how to do it correctly

I will assume that $g(G, v)$ computes a valid vertex cover, so it can never report a more optimal solution, and does so in polynomial time.
We know that vertex cover is NP-hard to approximate within a factor below 1.36: http://annals.math.princeton.edu/wp-content/uploads/annals-v162-n1-p08.pdf. Since $g(G, v)$ reports a solution at most 5 more than optimal, we can scale the graph such that $(f(G,v) + 5) / f(G, v)) \leq 1.36$, which results in $f(G, v) \geq 14$.

Furthermore, vertex cover is fixed parameter tractable in the solution size. In other words, we can compute whether $G$ admits a vertex cover of a fixed size in polynomial time. Hence, we apply the fixed parameter tractable algorithm up to $k = 13$. If no solution has been found, use $g$. We now have a polynomial time algorithm that can solve any set cover instance within a factor below 1.36 times the optimal solution, which is a contradiction unless P = NP.

Corollary: it is impossible to have a computable algorithm that outputs a vertex cover of size at most $OPT + c$, where $c \geq 0$ is a constant, in polynomial time, unless P = NP.


Expressing a logical constraint in integer programming Let $x$ be an integer such that $x \in [ - 10,10]$ and $b$ a binary variable. Apply integer programming to express $b = 1 \leftrightarrow x \ge3$

My work:

\begin{equation}
    \begin{cases}
      \text{if}\,\,\,\,\ b = 1, & \text{then}\,\,\,\,\,\,\ x \ge3 \\
      \text{if}\,\,\,\,\ x \ge3, & \text{then}\,\,\,\,\,\,\ b = 1
    \end{cases}
\end{equation}

I got the following encoding $$3 + {M_1}(1 - b) \le x \le 2 + {M_2}b$$where $${M_1} \le- 13{\text{ and }}{M_2} \ge8$$

Checking:

Case: $b = 0$
$$3 + {M_1} \le x \le 2$$For  ${M_1} \le - 13$, we have $x =  - 10, - 9, \ldots ,2$

Case: $b = 1$
$$3 \le x \le 2 + {M_2}$$
For  ${M_2} \ge 8$, we have $x =  3, 4, \ldots ,10$

Thus, by choosing $b = \{ 0,1\} $ we can force $x$ to take any value from its domain.

Let $x \in [-10,10] \cap \mathbb Z$ and $y \in \{0,1\}$. Suppose that

$$y = \begin{cases} 1 & \text{if } x \geq 3\\ 0 & \text{if } x \leq 2\end{cases}$$

To ensure that $y \neq 0$ when $x \geq 3$, use

$$y \geq \frac{x-2}{8}$$

To ensure that $y \neq 1$ when $x \leq 2$, use

$$y \leq \frac{x+10}{13}$$

Pictorially,

The trivial inequality constraints are $-10 \leq x \leq 10$ and $0 \leq y \leq 1$. Lastly, the integrality constraints $x, y \in \mathbb Z$ should not be forgotten.


Is there an FPRAS for the number of min st cuts in general graphs? Provan and Ball [1] showed that the problem of counting the number of minimum st cuts is #P-Complete. What is known about the problem of approximating the number of min st cuts? Is it possible to get a Fully Polynomial Randomized Approximation Scheme for it?

[1] Provan, J. Scott, and Michael O. Ball. "The complexity of counting cuts and of computing the probability that a graph is connected." SIAM Journal on Computing 12.4 (1983): 777-788.

The Provan and Ball paper actually shows a 1-1 reduction from bipartite independent sets (BIS) to min st cuts. So an FPRAS for min cuts would imply an FPRAS for #BIS. However, #BIS is not known (and thought unlikely) to have an FPRAS [1][2].

[1] Dyer, Martin, et al. "On the relative complexity of approximate counting problems." International Workshop on Approximation Algorithms for Combinatorial Optimization. Springer, Berlin, Heidelberg, 2000.

[2] Dyer, Martin, Leslie Ann Goldberg, and Mark Jerrum. "An approximation trichotomy for Boolean# CSP." Journal of Computer and System Sciences 76.3-4 (2010): 267-277.


Conditions for string substitution commutativity Let's say I have two substitutions given [a:=b] and [c:=d]. What are some conditions that hold for a,b,c,d ∈Σ* iff forall s∈Σ* s[a:=b][c:=d]=s[c:=d][a:=b]

Also you can assume that a,c≠ but you cannot assume so for b and d.

It's really simple. Just build two finite state transducers A and B , one for each substitution, then perform their composition A○B and B○A check if they are equivalent. Checking equivalence of transducers is undecidable, but in this case the transducers should be functional and equivalence in this special case is decidable.


New Assembler in compiler I'm currently developing my degree thesis, and the lab's idea is to design a new micro architecture, and then, be able to compile stuff for this architecture. So the question is, how do you instruct a compiler to generate your new assembler???
The general idea is to be able to compile with gcc and run netbsd or similar kernel with this new architecture.
Well, thanks a lot!

Many compilers, gcc included, are divided into two major parts: a front-end and a back-end. The front end is in charge of compiling the input language into some sort of intermediate form, and perform some of the optimization. The back-end takes this intermediate form and generates actual machine code. You only need to construct a new back-end (or even less than that). Luciano in his answer gave you a good pointer regarding that.


Calculate the number of combinations of a sequence of numbers in a particular order I have a problem solving coding challenge when I have to calculate the number of combinations, numbers from 0 to 9, with the length n, with 2 rules -

- The first number cannot be 0

- Every other number can be 0 or must be divisible by the previous number (number 1 can not be used as divisor), for example [5.0], [1,0] or [2,8], [4,8], [3,6]

For example, if the length n were 2, number of combinations would be 23 - [1,0]...[9,0] + [2,4], [2,6], [2,8], [3,6], [3,9], [4,8] + [2,2]...[9,9]

The resulting response can be code in some programming language or a formula to calculate answer

Can you solve the problem for $n=1$?
Can you deduce the answer for $k+1$, if you know the answer for $k$?
(hint: you need an $n\times 10$ table, the $k$-th row devoted for problem size $k$, the columns for partial answers...)

ps: I think that the answer is $9+0+1+1+2+1+3+1+3+2=23$ for n=2 (and 125 for $n=3$)

0: 10,...,90
1: -
2: 22
3: 33
4: 24,44
5: 55
6: 26,36,66
7: 77
8: 28,48,88
9: 39,99


Perceptron and non linearly seprable data I was asked in an interview question, can a perceptron classifier ever reach 100% accuracy on some kind of non linearly seprabale training data in 2D.
I said that no it can't because the data is not linearly seprabale.
We then proceed to the next question, but maybe its just me, but from the look of the interviewr, I'm
not sure that was the right answer.
Am I missing something or just paranoid? Can the perceptron reach 100% accuracy on any training data?
Thanks!

A single-layer perceptron can only learn linearly separable patterns (with 100% accuracy), as noted in the Wikipedia article on perceptrons.  (Advice for the future: check standard references before asking here.)
A multilayer feedforward neural network (sometimes called multilayer perceptron) can learn other patterns.
If someone just says "perceptron", in my eyes it is at least a little ambiguous whether that means a single-layer perceptron or possibly could encompass multi-layer networks.


How to compute a level set $A=\left\{ \theta:f\left(\theta\right)\geq a\right\} $ I have a real function $f:\mathbb{{R}}^{d}\mapsto\mathbb{R}$, where
$d>1$. The question is how to compute the level set $A=\left\{ \theta:f\left(\theta\right)\geq a\right\} $.
I am a statistician knowing very few things about computer science.
I would appreciate very much if anyone could suggest some reference, methods
and/or alogirthms.

In my problem, $f\left(\theta\right)=\sum_{i=1}^{N}\log g\left(\mathbf{z}_{i};\theta\right)$,
where $g\left(\mathbf{z}_{i};\theta\right)$ is a probability density
function of $\mathbf{z}_{i}$ parameterized by a vector of parameters
$\theta$. $\mathbf{z}_1,\ldots, \mathbf{z}_N$ are observed samples. For example, $g\left(\mathbf{z}_{i};\theta\right)$ is the density function of
a normal distribution with variance $1$
$$
g\left(\mathbf{z}_{i};\theta\right)=\frac{1}{\sqrt{2\pi}}\exp\left(-\frac{\left(y_{i}-\mathbf{x}_{i}'\theta\right)^{2}}{2}\right).
$$
Here $\mathbf{z}_{i}=\left(y_{i},\mathbf{x}_{i}\right)'$.

We can compute
$$ f(\theta) = -N\log (2\pi)-\frac{1}{2}\sum_{i=1}^N (\langle x_i,\theta \rangle -y_i)^2. $$
Expanding this out, we get that $f(\theta)$ is some quadratic form:
$$ f(\theta) = \theta' A \theta + v'\theta + C, $$
where $A$ is symmetric.
The next step is to get rid of the linear term. Let $\theta = \psi + \epsilon$. Then
$$ \theta' A \theta + \langle v,\theta \rangle + C =
\psi' A \psi + (2\epsilon' A + v') \psi + (\epsilon' A \epsilon + v'\epsilon + C).
$$
So choosing $\epsilon' = -v' A^{-1}/2$ (assuming $A$ is invertible), we get
$$ f(\psi + \epsilon) = \psi' A \psi + C'. $$
The theory of quadratic forms tells us that if $A$ is invertible then we can write $A = P'DP$, where $D$ is a diagonal matrix with $\pm 1$ on the diagonal and $P$ is invertible. If $\psi = P \chi$ then
$$ f(P^{-1} \chi + \epsilon) = \chi' D \chi + C' = \sum_{i=1}^k \delta_i \chi_i^2 + C', $$
where $\delta_i \in \{\pm 1\}$. Suppose for example that the first $k_+$ are $+1$ and the rest $k_- = k - k_+$ are $-1$, and write $\chi = [\chi_+\;\chi_-]$. Then
$$ f(P^{-1} \chi + \epsilon) = \|\chi_+\|^2 - \|\chi_-\|^2 + C'. $$
If $k_+ = 0$ or $k_- = 0$ then the level sets are spheres or cospheres, up to an affine transformation of course. Otherwise it gets more complicated.

In your case, however, it is clear from the function $f$ itself then the quadratic form $A$ is negative semidefinite, probably in fact negative definite. In other words, $k_+ = 0$. So the sets you're after are affine transformations of cospheres. In other words, they are "outsides" of ellipsoids.

The only non-trivial step is finding the matrix $P$. Since your matrix is negative definite, you can use Cholesky decomposition.


Maximizing the sum from m stacks using k pop's Assume you have m stacks each some elements within it. If you are allowed to do k pops , the objective is to maximize the sum(sum increases by the value of the popped element). What is the best algorithm which would be able to solve this problem.
Can the complexity be improved if the details of the elements in each stack is known beforehand.

You can use dynamic programming to solve this problem in polynomial time.
Create a table $A[i,l]$ with $0\le i \le m$ and $0\le l\le k$, where $A[i,l]$ reprensents the optimal allocation using at most $l$ pops among the first $i$ stacks. We initiate by $A[.,0]=A[0,.]=0$ and we have the following inductive step :
$$
A[i+1,l]=\max\left\{A[i,l-t]+(t \text{ pops from stack } i+1), 0\le t \le l\right\}
$$
We can compute $A[m,k]$ in time $O(k^2m)$.


Show that 0^n1^n is decidable I would like to know how would one go about and answer this question. I know that a language is decidable if a turing machine exists that accepts the strings in that language, and rejects otherwise. Would I need to create a turing machine to show this or is it enough to create a PDA and claim a TM can be created from a PDA such that it accepts and halts all strings in it and rejects otherwise. Also, if anyone can refer a good post to learn how to create a PDA from CFL would be greatly appreciated. Thanks!

If a language decidable by a PDA then it is also decidable by a TM. In other words TM are more computationally powerful than PDA, i.e., the class of languages decidable by PDA is a proper subclass of the class of languages decidable by TM. You can also easily simulate a PDA on a TM.

However not all languages are decidable by PDA. So your approach does not work in general.

As to CFG to PDA conversion I would recommend the textbook by Sipser (pg 116). Google search for "CFG to PDA" also gives a good result.


Image registration using gradient descent I have a target image $f(x,y)$ (where $x \in [0, 250]$ and $y \in [0,300]$), and a source image $g(x,y)$

I want to align $g$ to $f$ using the transformation :
$$\Psi(x,y;t_x, t_y, \theta) = \begin{pmatrix}\cos(\theta) & -\sin(\theta) & t_x \\
\sin(\theta) & \cos(\theta) & t_y\end{pmatrix}\begin{pmatrix}x \\ y \end{pmatrix}$$

I'm trying to do this by minimizing the squared error :
$$l(p) = \sum_{x,y}{(f(x,y) - g(\Psi(x,y;p))}^2$$

I first computed the gradients :
$$
\begin{align}
\frac{\partial l(p)}{\partial t_x} & = \sum_{x,y}\left(2(f(x,y) - g(\Psi(x,y;p))
\left(\frac{\partial }{\partial t_x}g(\Psi(x,y,p))\right)\right) \\
& = 2\sum_{x,y}\left((f(x,y) - g(\Psi(x,y;p))
\left(\frac{\partial }{\partial t_x}g(\Psi(x,y,p))\right)\right) \\
& = 2\sum_{x,y}\left((f(x,y) - g(\Psi(x,y;p))
\left(\frac{\partial }{\partial \Psi_x}g(\Psi(x,y,p))\frac{\partial \Psi_x}{\partial t_x}\right)\right)\\
& = 2\sum_{x,y}\left((f(x,y) - g(\Psi(x,y;p))
\left(\frac{\partial }{\partial \Psi_x}g(\Psi(x,y,p))\right)\right)\\
\frac{\partial l(p)}{\partial t_y} & = 2\sum_{x,y}\left((f(x,y) - g(\Psi(x,y;p))
\left(\frac{\partial }{\partial \Psi_y}g(\Psi(x,y,p))\right)\right)
\end{align}
$$
However, for $\theta$, I find this :
$$
\begin{align}
\frac{\partial l(p)}{\partial \theta} & = \sum_{x,y}\left(2(f(x,y) - g(\Psi(x,y;p))
\left(\frac{\partial }{\partial \theta}g(\Psi(x,y,p))\right)\right) \\
& = 2\sum_{x,y}\left((f(x,y) - g(\Psi(x,y;p))
\left(\frac{\partial }{\partial \theta}g(\Psi(x,y,p))\right)\right) \\
& \text{by chain rule } \frac{\partial}{\partial \theta}g(\Psi(x,y,p))
= \frac{\partial}{\partial \Psi_x}g(\Psi_x(x,y;p), \Psi_y(x,y;p))\frac{\partial \Psi_x}{\partial \theta} + \\
& \frac{\partial}{\partial \Psi_y}g(\Psi_x(x,y;p), \Psi_y(x,y;p))\frac{\partial \Psi_y}{\partial \theta} \\
& = 2\sum_{x,y}\left((f(x,y) - g(\Psi(x,y;p))
\left(\frac{\partial }{\partial \Psi_x}g_\Psi\frac{\partial \Psi_x}{\partial \theta} + \frac{\partial }{\partial \Psi_y}g_\Psi\frac{\partial \Psi_y}{\partial \theta}\right)\right)
\end{align}
$$

Since $\frac{\partial \Psi_x}{\partial \theta} = -x\sin(\theta) - y\cos(\theta)$, it can reach high values such as $300$ (depending on $\theta$).
This means that $\frac{\partial l(p)}{\partial \theta}$ have values way bigger than $\frac{\partial l(p)}{\partial t_x}$ for instance, which feel quite wrong.

I think I did a mistake calculating the gradient, but I don't understand where?

It doesn't feel wrong to me.

A rotation by a small amount, say one degree, changes the location of an object in the image by many pixels.  For instance, suppose you have a 1000x1000 image, and you rotate it by one degree around the upper-left corner.  Then an object near the upper-right corner moves upward/downward by about 17 pixels.  There is "leverage" proportional to the size of the image; rotate a long lever by a small rotation, and the end of the lever still moves a large way.

In contrast, a translation by a small amount, say one pixel, changes the location of an object in the image by only a little.  For instance, if you have that same image and you translate by one pixel, then the object moves by only 1 pixel.

So it is not surprising (to me) that the gradient in the first case might be much larger than the gradient in the second case.


How do RNN's handle providing output with different dimension than input It seems like an RNN has to have the ht-1 needs to be the same size as the input vector since they're being added to one another, but if you're doing something like modeling to another language or classification, how would you handle this?  I'd imagine you'd just have a fully connected layer that would predict the output, but I was wondering if there is a standard convention?

So Basically what happens is the input x is multiplied by a hidden layer U to yield a state vector s, which transforms it to a new dimensionality.  Then The recurrent layer W is always a square matrix to maintain the dimensions of s.  Lastly, the output matrix V is multiplied to update the matrix to the output dimensionality.

So if you had a vector that was 5 dimensions, and you wanted to multiply it into a state vector of 20 dimensions and an output vector of 2 dimensions, your dimensions would be:

x is 5x1
s is 20x1
y is 2x1

U is 20x5
W is 20x20
V is 2x20

and your formula is:

s = Ux + W*s_(t-1)
y = Vs


Direct construction of NFA for the difference of regular languages Let $A$ and $B$ be regular languages. Let $C$ be their difference, i.e $C = B \setminus A$.

Given NFAs for $A$ and $B$, is it possible to directly construct an NFA for $C$ without (implicitly or explicitly) converting them to DFAs first?

The short answer is "yes".

Probably the easiest way to explain it is with an example; turning this into a formal algorithm should be straightforward.

The first NFA, $M$, accepts the language $(a\cup b)^*$:

$$q_0 = \epsilon \cup a q_0 \cup b q_0$$

with the start state being $q_0$.

This is probably not notation that you're used to, but the reason for using this will become clear soon; it's basically saying the same thing as the context-free grammar:

$$ S \rightarrow \epsilon $$
$$ S \rightarrow a S $$
$$ S \rightarrow b S $$

You can see how this is also a description of a NFA. Each term on the right-hand side is either a transition $aq_i$, which means read an $a$ and go to state $q_i$, or $\epsilon$ which means that the state is a final state.

The second NFA, $M$, accepts the language $(a\cup b)^*aa(a\cup b)^*$, that is, any string which contains $aa$. The start state is $q_1$; I've used unique state names for reasons that will become obvious in a moment. I deliberately picked an NFA which has some nondeterminism just to show that this works for that case.

$$q_1 = a q_1 \cup b q_1 \cup a q_2$$
$$q_2 = a q_3$$
$$q_3 = \epsilon \cup a q_3 \cup a q_3$$

We would like to construct a NFA which accepts the language:

$$Q_0 = q_0 \setminus q_1$$

expanding one level gives:

$$Q_0 = (\epsilon \cup a q_0 \cup b q_0) \setminus (a q_1 \cup b q_1 \cup a q_2)$$
$$ = \epsilon \cup a (q_0 \setminus (q_1 \cup q_2)) \cup b (q_0 \setminus q_1)$$
$$ = \epsilon \cup a Q_1 \cup b Q_0$$

where:

$$Q_1 = q_0 \setminus (q_1 \cup q_2)$$

Note that we already had a state which handled the $b$ transition correctly. For the $a$ transition, we didn't, so we introduced one.

We continue:

$$Q_1 = q_0 \setminus (q_1 \cup q_2)$$
$$= (\epsilon \cup a q_0 \cup b q_0) \setminus (a q_1 \cup b q_1 \cup a q_2 \cup a q_3)$$
$$= \epsilon \cup a (q_0 \setminus (q_1 \cup q_2 \cup q_3)) \cup b (q_0 \cup q_1)$$
$$= \epsilon \cup a Q_2 \cup b Q_0$$

where:

$$Q_2 = q_0 \setminus (q_1 \cup q_2 \cup q_3)$$

continuing again, going a little more slowly this time:

$$Q_2 = q_0 \setminus (q_1 \cup q_2 \cup q_3)$$
$$= (\epsilon \cup a q_0 \cup b q_0) \setminus ((a q_1 \cup b q_1 \cup a q_2) \cup (a q_3) \cup (\epsilon \cup a q_3 \cup b q_3))$$
$$= a (q_0 \setminus (q_1 \cup q_3)) \cup b (q_0 \setminus (q_1 \cup q_3))$$
$$= a Q_2 \cup b Q_2$$

Note that we used the fact that $\epsilon \setminus \epsilon = \varnothing$.

So in summary, we have the following NFA with start symbol $Q_0$:

$$Q_0 = \epsilon \cup a Q_1 \cup b Q_0$$
$$Q_1 = \epsilon \cup a Q_2 \cup b Q_0$$
$$Q_2 = a Q_2 \cup b Q_2$$

You can verify for yourself that this accepts the language.

There are several things to notice about this.

First off, the process must terminate; there are only a finite number of possible transition states which could be created.

Secondly, the running time could be exponential in the worst case; each transition state is of the form $\bigcup_i q_i \setminus \bigcup_j q_j$ where the left-hand side of the set minus is a subset of the states from the first machine and the right-hand side is the same for the second machine. There is a finite number of such subsets, but there could be exponentially many in general, and sometimes there will be. And the reason is...

...the final answer is a DFA! It's not hard to see that this will always be the case. Your question only asked for a method that didn't convert the two NFAs to DFAs first, and you never said anything about not constructing a DFA for the final answer.

Basically what we've done here is folded the NFA-to-DFA conversion algorithm together with the DFA difference algorithm, so one algorithm does both. I think this satisfies the requirements of your question.


Maximum Sum SubArray - Naive Implementation I am looking at a problem that is often asked in interview settings. The problem statement is:

  Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

I want to talk about the naive solution, where we generate all contigous subarrays, take their sums, and find the maximum sum. Here is an implementation of the naive solution:

function maxSubArray(arr) {
  let max = null;

  for (let i = 0; i < arr.length; i++) {
    const startIdx = i;

    for (let j = i; j < arr.length; j++) {
      let sum = 0;

      for (let k = i; k <= j; k++) {
        sum = sum + arr[k];
      }

      if (max === null || max < sum) {
        max = sum;
      }
    }
  }

  return max;
}

I know that this solution runs in O(n^3), but I do not understand why that is the case. If we "generate" all possible contigous subarrays, I can explain why that is an O(n^2) operation:

  Let's say that our input array is 4. We can create 1 contigous subarray of length 4; 3 contigous subarrays of length 3; 3 contigous subarrays of length 2, and 4 contigous subarrays of length 1. In other words, the number of contigous subarrays for an array of length n is the sum of 1 to n, or (n * (n + 1)) / 2. In asymptotic analysis, that is O(n^2).

Now, I understand that summing up each individual subarray is **not* free, but here is where I am stuck. I do not know how to "add the work that we do to get the sum of each subarray" to my existing time complexity of O(n^2).

An implementation that I wouldn't call naïve but criminally stupid would calculate the sum of elements in each subarray by adding up the elements. You are summing from 1 to n elements for each of n^2/2 subarrays, which makes it $O (n^3)$ (proving that this is a lower bound needs a bit more care).

Of course a naïve but not stupid implementation would calculate the sums for all subarrays starting with the first element using only one extra addition for each sum.


Where can I find a short and 'easy' peer reviewed paper on something from computability, decidability or complexity? It's a homework assignment, we were asked to read, understand, and present to our colleagues a short paper/article (suggested 4-6 pages) for our Computability, Decidability or Complexity class.

The articles I was able to find in the past couple days using google scholar a way over what we were taught, plus, 50-100+ pages is way over the scope of my assignment. In class, we were provided with an introduction to the three topics, complexity classes, relations between them, and (mostly informal) proofs for the most representative problems from each class by modelling them using all kinds of Turing Machines.

Any possible solutions? It's the first time in my life I'm touching anything related to research, I can barely understand even the scope of most papers I find.. I guess any advice would be welcome.

"By definition" recent research papers usually contain non-trivial results and they often (always?) require a deep knowledge of the argument in order to be well understood, so if you pick a paper at random you'll probably find a bunch of obscure signs in your hands :-)

So my suggestion is to look at "old" research papers (but not "too old"):

pick a particular argument/theorem that you think you have understood informally (or an argument that intrigues you);
read more about it on a theory of computation book or on Internet (for example start from Wikipedia and look at the references at the bottom, or search it on Google adding the keywords "introduction" or "lecture notes");
finally search the paper in which that argument/theorem was originally published and read it;

For example one of the fundamental basic results in computational complexity is the (deterministic) Time Hierarchy theorem. Very informally the theorem says that given more time, a Turing machine can solve more problems. You can start reading the Wikipedia article, then pick a lecture note with a more formal proof Googling around (for example pick this one by Arora). Finally when you think that you've understood the proof well download and read the original paper R. Stearns and J. "Hartmanis paper On the computational complexity of algorithms", 1965. You'll find that it contains even more details and is more formal.