Asymptotic notation between two sets of variables I have problems interpreting the definition of asymptotic notation where the functions involve two different set of variables. I am quite confident with the definition of $f(n) = O(g(n))$ and its extension to the multivariable case ($f(n, m) = O(g(n, m))$). However I don't actually understand the meaning of $f(n) = O(g(m))$ since $f$ and $g$ work with two different variables.
If for example I have that $n = O(m)$, the intuition behind this is that $m$ upper bounds $n$ but I'm not quite sure how to apply the formal definition of big O. The first idea was to use a dummy function approach by defining $f(n, m) = n$ and $g(n, m) = m$ but this does not work out well.
Another idea was to assume that both $n$ and $m$ are a function of some unknown variables that depend on the problem at hand. In this case $n = n(x_1, \ldots, x_k)$, $m = m(x_1, \ldots, x_k)$ and $n(x_1, \ldots, x_k) = O(m(x_1, \ldots, x_k))$.
Is this right? Am I missing something?

Unfortunately, there is no standard interpretation of $f(n,m) = O(g(n,m))$ in common use in computer science. Here are some possible interpretations:

There exists a constant $C > 0$ such that for all natural $n,m$, $f(n,m) \leq Cg(n,m)$.
There exist constant $C,N,M > 0$ such that for all natural $n,m$ if $n \geq N$ and $m \geq M$ then $f(n,m) \leq Cg(n,m)$.
Some combination of the two.

In your case, you are describing a different use of asymptotic notation. Suppose that algorithm $A$ works in time $O(n+m)$ (under the first interpretation above).
Claim. If $m = O(n)$ then $A$ works in time $O(n)$.
What this really means is the following:

For every constant $C > 0$ there exists a constant $D > 0$ such that if $m \leq Cn$ then algorithm $A$ works in time at most $Dn$.

The proof is quite simple. Since $A$ works in time $O(n+m)$, there exists a constant $E$ such that the running time of $A$ is at most $E(n+m)$. If $M \leq Cn$ then $E(n+m) \leq E(1+C)n$, so we can choose $D = E(1+C)$.

This kind of "elided quantifier" is common in theoretical computer science. For example, consider the following statement.
Claim. Some Boolean function on $n$ bits requires circuits of size $\Omega(2^n/n)$.
What this statement really means is one of the following:

There is a sequence of Boolean functions $(f_n)_{n=0}^\infty$ such that $f_n$ is a Boolean function on $n$ bits and if $M(n)$ is the minimum circuit size of $f_n$, then $M(n) = \Omega(2^n/n)$.
There is an infinite set $N \subseteq \mathbb{N}$, for each $n \in N$ a Boolean function $f_n$ on $n$ bits, and a constant $c>0$, such that for all $n \in N$, every circuit for $f_n$ has size at least $c2^n/n$.

Once you get used to this sort of statement, such interpretations become automatic, though unfortunately, there is often some ambiguity and vagueness involved.

Your example of $m = O(n)$ probably comes from the world of graph theory. We say that a graph is sparse if $m = O(n)$, where $n$ is the number of vertices, and $m$ is the number of edges. Graph algorithms such as BFS and DFS run in time $O(n)$ on sparse graphs.
What this really means is that if we have a collection of graphs satisfying $m \leq Cn$ or some constant $C$, then BFS and DFS run in $O(n)$ on this collection of graphs. For example, it is known that planar graphs contain at most $3n-6$ edges. Therefore BFS and DFS run in $O(n)$ on planar graphs.


Design the transition function I need to design a Turing Machine that accepts the (context-free) language: $L(M)=\{0^{n}1^{n+1}: n\ge1$}.

$$Q=\{q_0,q_1,q_2,q_3,q_4\} ,Σ = \{0,1\}, Γ =\{0,1,X,Y,B\}, F=\{q_4\}$$

X- processed 0
Y- processed 1
B- blank
P-move right
L-move left
So far I've succeeded to create a table for languages $\{0^n1^n\}$(without the red entry) and $\{0^n1^k:k\ge n\}$.

What should it look for case in which there is minimal superiority of "1's"?

@EDIT

Meanwhile I've finally hit on an idea for L(M)

Is it correct?

If you have managed to solve $0^n1^n$ then $q_4$ should simply proceed to the rightmost bit you haven't processed yet and verify that it's a 1 and that there is nothing following it.


A Good Resource for Christofides' Heuristic Is there an explanation Christofides's Heuristic for solving TSP which does not simply state the algorithm and go ahead to prove the bound?

To be specific:
(Disclaimer : I am an engineer who knows very little about graph theory but need this for a logistics course)

I understand that I first create an MST. So far, so good.
Now, I need to find a perfect minimum weight matching on all odd degree nodes. I have no clue what this is; googling this tells me this is a set of edges containing maximum $n/2$ edges such that no node is shared by 2 sets. I don't see why I am doing this..... I am not even sure I understand what this statement means.
Now, I need to merge the MST and the matchings to create a "multigraph" and then find an Eulerian tour on this. No clue what I am doing here.
Run the shortcut algorithm exploiting the triangle inequality. (No clue what happened till now and this obviously then makes no sense either)

Can someone point me to a good resource with possible examples and illustrations for why Christofides works in a language that isn't full of graph theory terms (or alternately, provide me an answer here)?

I have already looked at :

A Berkeley PDF
Wikipedia

In the long run, it's really better to understand the graph theory terminology, but for now, here is an explanation of Christofides's algorithm. I'm not an expert in this area so I can't offer much by way of intuition. Also, I should note that by now, better algorithms are known for some variants, see for example the recent survey by Vygen.

We denote the sum of costs of a tour or of similar objects by $w(\cdot)$. Fix some optimal TSP tour $H$.

The starting point of the algorithm is a minimum spanning tree $T$. Why do we want a minimum spanning tree? Suppose that instead of a TSP tour, we're interested in a TSP path. A TSP path is a spanning tree, and while it is difficult to find an optimal TSP path, it's easy to find a minimal spanning tree. In the case of a TSP tour, we have $w(T) \leq w(H)$ as well.

If $T$ happens to be a path then, with some luck, we can get a good tour by completing it into a cycle. However, this need not be the case, and $T$ can be a complicated tree. Here we use a trick: Euler proved that every graph with even degrees can be traversed by an Eulerian circuit. While we wanted a tour and not just any circuit, this happens not to matter as we will see below.

How do we make $T$ into a graph with even degrees? The obstructions are the vertices with odd degree, so we'd like to pair them (there must be an even number of them since the sum of degrees in a graph is always even) as cheaply as possible. This is the minimum-weight matching you mentioned. We complete $T$ into an even-degree graph $T'$ by adding a matching $M$ on the odd-degree vertices, which is just a set of edges connecting pairs of odd-degree vertices. For obvious reasons, we want $M$ to have as minimal weight as possible, and such a matching can be found effectively. (As a special case, if $T$ is a path then $M$ connectes its two endpoints, and $T'$ is just a cycle.)

All vertices in $T'$ have even degree, so we can find an Eulerian tour $E$ working its way over all edges of $T'$. However, we wanted a Hamilton cycle (another name for a TSP tour). The idea now is to follow the Eulerian tour. Whenever we're supposed to visit a vertex we have already encountered, we just "skip" this edge. Eventually the tour will reach a new vertex, and then we just connect the previous vertex with the new one. The triangle inequality shows that the resulting TSP tour has weight at most $w(T') = w(T) + w(M)$.

Here is an example: suppose the Eulerian tour starts $a,b,c,a,d$. The constructed TSP tour will start $a,b,c,d$. The cost of the Eulerian tour is $w(a,b)+w(b,c)+w(c,a)+w(a,d)+\cdots$. The cost of the TSP tour is $w(a,b)+w(b,c)+w(c,d)+\cdots$. The triangle inequality shows that $w(c,d) \leq w(c,a)+w(a,d)$, i.e. if we take a detour from $c$ to $d$ via $a$, that can't be shorter than going straight from $c$ to $d$.

We already know that $w(T) \leq w(H)$. What about $w(M)$? Let $v_1,\ldots,v_{2k}$ be the set odd-degree vertices in $T$, in the order in which they appear in $H$ (starting at an arbitrary vertex and an arbitrary orientation). One possible way to match them is $M_1 = (v_1,v_2),(v_3,v_4),\ldots,(v_{2k-1},v_{2k})$. Another possible way is $M_2 = (v_2,v_3),(v_4,v_5),\ldots,(v_{2k-2},v_{2k-1}),(v_{2k},v_1)$. The triangle inequality (again) shows that the edge $(v_i,v_{i+1})$ costs at most as much as the entire stretch of $H$ from $v_i$ to $v_{i+1}$. Now imagine taking $M_1$ and $M_2$, and replacing each edge with the corresponding stretch of $H$. The result is all of $H$, and so $w(M_1) + w(M_2) \leq w(H)$. Since $M$ has minimum weight, $w(M) \leq w(M_1),w(M_2)$ and so $w(M) \leq w(H)/2$. Therefore $w(T) + w(M) \leq (3/2) w(H)$.


Determining if a list contains two numbers whose difference is less than k Given a list with $n$ positive elements and positive number $k$, determine whether there are two numbers whose difference is less than $k$.
The average time complexity should be $O(n)$, and the memory should be $O(n)$ as well.

My attempt: initialize a hash table, and insert every element from the list to the hash, all of this takes $O(n)$ time on average.
Now, scan the list. Say the the elements are $x_1,x_2, \dots, x_n$.
Assume we scan $x_i$ then if we have in the list an appropriate element, it should fulfill $|x_i-x_j|<k$, so I have to check $2k$ different elements, which isn't good enough.
Does anybody have any other idea?

Let $f(x) = \lfloor x/k \rfloor$. Create a hash table which stores $f(x_1),\ldots,f(x_n)$; furthermore, for each $y \in \{f(x_1),\ldots,f(x_n)\}$, count how many elements map to $y$, and what is the minimal element mapping to $y$.

If any of the cells contains more than one element, then these two elements are at a distance of less than $k$. Otherwise, go over all elements, and for each $x_i$, compare $x_i$ to the minimal element mapping to $f(x_i)+1$, checking whether the two elements are at distance less than $k$. If no elements at distance less than $k$ have been found in this way, then no such elements exist.


What is this approximation/error-reduction method called? I'm wondering if anyone could help me find my footing in an approach I am taking with a student in my audio programming class for creating more accurate pitch detection algorithms. But the approach is not limited to pitch detection and in fact seems seems similar to Newton's Method, Euler's Method, Horner's Method, and so on. It is a very simple and general idea, and must have some background in numerical methods. I am looking for pointers to the literature.

Here is the idea. We have a function f which takes a signal and returns the fundamental frequency (such algorithms are close cousins to the Discrete Fourier Transform). In order to test its accuracy, I created simple sine wave signals of precise frequencies and tested the algorithm, and graphed the errors over a particular range; basically a perfect f would be the identity function, so we just had to record the deviation from the identity. The errors are basically sinusoidal. So I stored the errors in an array, and use cubic interpolation to create a continuous error function, and built that into the last stage of the algorithm. Of course, there is a problem, because the errors showed the deviation from a perfect f, and the original f is not perfect, so there would be errors in the errors, so to speak. So I iterated the process, correcting successively for errors in the errors, and the algorithm gets better each time. I have not yet figured out whether it will converge to some minimal error. I also have not tested it in musical settings. But it is very promising, and seems like a generally useful technique.

Separate from a programming trick, I would like to understand some of its properties such as convergence and so on. Anyone have any pointer, keywords, etc. for me to pursue this?  I'm guessing it is a standard technique in numerical methods.

There is a high risk that you are "overfitting": you are fitting to noise, not to signal.  If that's indeed what is happening, your method won't actually be useful.

The way to find out whether your method is actually making any real improvements (or whether you're just fooling yourself) is to have a holdout set: a separate set of signals, that you haven't used during the error correction.  In other words, you have a training set (one set of signals) and a test set (a separate list of signals, with no overlap with the training set).  You do all of the correction, corrections to the corrections, etc., on the training set.  Then, once you've done that, you measure how effective your resulting corrected algorithm is on the test set.  This will give you a sense of how effective your approach is.


Finding a trapdoor function for the 3-partition problem I am working on a cryptography project. Let's say I want to build a public key cryptosystem using the 3-partition problem, which is NP-Complete, as a basis (just like RSA uses integer factorization).

Now, I am having trouble coming up with a trapdoor function that helps me enconde it. Let's say I have $T=\{t_{1}, t_{2},...,t_{3n}\}$ and a solution $S=\{S_{1}, S_{2}, ..., S_{n}\}$, where every $S_{i}$ contains 3 elements of $T$ and $\sum_{k=1}^{3} S_{ik} = \sum_{k=1}^{3} S_{jk}=x$.

Now, let's assume the user creates $T$ and $S$, and of course also knows $x$. He can use either $x$ or $S$, or both, as a private key, and send $T$ and the public key for enconding.

I want to find a "function" that in one way requires finding $S$ or $x$ from $T$, and the other way can be done only with $T$. That is, given a plaintext $p$, $f(p, T)=c$ and $g(c, S)=p$ (I don't know if $f$ and $g$ have to be inverse of each other necessarily).

The cryptisystem does not have to be super-secure or have no flaws, I'm just looking for a function/encoding that does this in whatever way. For example, the MH knapsack cryptosystem uses some kind of alternate way to write the subset sum problem as a sum like $V=a_1x_1,..., a_nx_n$.

Thanks for reading.

As Yuval says, it's an open question whether one can build a public-key cryptosystem whose security is based on the assumption that $\textsf{P} \ne \textsf{NP}$.  There is no known public-key cryptosystem with that property, though many cryptographers have tried to find one.  So, you're trying to solve a problem that is likely to be extremely hard to solve.

Part of the challenge is that NP-complete problems are generally hard, but that's not enough for cryptography.  Public-key cryptography also requires that there be a "trapdoor" that makes them easy.  So, you'll need to find a way to encode a secret trapdoor in the 3-partition instance that makes it easy to solve the 3-partition problem if you know the trapdoor -- but where you can prove that the existence of the trapdoor doesn't make the problem any easier for people who don't know the trapdoor.  It's not clear how to do that.  There are ways to embed a trapdoor, but then they require choosing 3-partition instances with a particular structure/format, and then solving those special instances might be easy (might be doable in polynomial time).

You might be interested in knapsack cryptography (see the knapsack tag on Crypto.SE), Impagliazzo's five worlds, this question on Crypto.SE, and Impagliazzo and Rudich's black-box separation between one-way functions and key exchange, which provides some kind of evidence that it's likely not going to be easy to do what you want (e.g., there's no black-box way to convert a NP-complete problem to a public-key encryption algorithm).


Harvard processor structure In my books it is written that the concept of pipelining can happen only with Harvard structure as CPU can both fetch data from and write back data to memory at the same time my question is how can fetching and writing back be done at the same time when there is only one bus for data just like von Neumann structure? How can using an instruction bus be helpful when it only carries instruction but not data?

So if I want to add 2+5 here 2 and 5 are data but + would be the instruction right?
If I fetch 2 and 5 from data cache and add from instruction cache then execute and again write back the result 7 which would be a data to memory and before the whole process is done fetch another data for example 7 and 6 like in what the book stated according to the picture would it still be fetching (the data 7 and 6) and rewriting the data 7 (result of execution) happen at the same time both these numbers are data and have to be fetched and rewritten using data bus so it still be impossible to fetch and rewrite them at the same time and the instruction bus wouldn't be useful.

This is one of the reasons why most modern general-purpose CPUs have split L1 caches, one for instructions and one for data. (It's not the only reason, of course.)
You see, modern CPU pipelines don't interact with a von Neumann-type bus at all, but directly with cache. As far as the pipeline is concerned, instruction memory and data memory are separate because the caches are separate.


Creating a single layer perceptron for the OR problem I am working on the following problem

Find the linear least squares unit weights for the `OR' problem, ie.
$v_1^T = (0,0), v_2^T = (1,0), v_3^T = (0,1), v_4^T = (1,1)$ and $u_1 = 0, u_2 = u_3 = u_4 = 1$.

Here $v$ represent inputs and $u$ outputs. For problems like this I usually find a matrix $W$ (the weights) such that $$u_i=Wv_i \quad i=1,2,3,4$$ but I think it is obvious a matrix doesn't exist. my reasoning being that the problem is equivalent to finding the matrix $W = \begin{pmatrix} x_1 & x_2 \end{pmatrix} $ such that $$\begin{pmatrix} 0 & 1 & 1 & 1 \end{pmatrix} = \begin{pmatrix} x_1 & x_2 \end{pmatrix} \begin{pmatrix} 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \end{pmatrix}$$ And looking at the two middle columns of the left vector and right matrix we must have $x_1=x_2 =1$ but then we get $1 + 1 = 1$, a contradiction.

In a unit perceptron a function may be applied to the output, and a step function $$f(x) \begin{cases}
0 & x \leq 0 \\
1 & x > 0
\end{cases}$$ would work here.

My question here is, is this correct? I wasn't quite sure if I am answering the right question. I am pretty sure $u_i = f(Wv_i)$ but I am not too familiar with what is meant by "linear least squares unit weights" in this context?

The fact that you mention linear least squares error seems to hint that they want you to use a completely linear model $u_i=Wv_i$ for your perceptron. In this case you won't get exact answers like $0$ and $1$; you will only get approximations with some amount of error.

That said, I don't think a linear model makes sense for this problem, since it is a classification problem with two classes. Using a non-linear step-like function $f$ before the final output of a perceptron classifier is a pretty standard thing to do, so I see no problem with using $u_i=f(Wv_i)$.

Assuming you can use $f$, using the weights $x_1 = x_2 = 1$ as you mentioned solve this problem exactly with zero error.


Given family of grammars, determine if LR(k) Parsing family of grammars, determine if LR(k)

I have the exact same problem, but my reputation is not enough to comment on that thread, plus the OP hasn't been online in 2 years so I can't ask him personally. So I apologize, but I do have to ask for your help!

Would it be enough to show that the formula works for n = 2, n = 3 (by drawing the automata) and deduct that it must work for any n?

As for the second question, could I follow the same strategy?

Thank you for you time.

No, of course not.  If you want to prove that some formula is true for all $n$, it is in general not enough to show that it is true for $n=2$ and $n=3$.  That's just wishful thinking.

Consider, for instance, the claim that $n^2+n+41$ is prime for all $n$.  You can check it for $n=2$ (sure enough, $2^2+2+41=47$ is prime) and $n=3$ (yup, $3^2+3+41=53$ is prime), and it'll be true for both $n=2$ and $n=3$, but that doesn't mean it's true for all $n$.  In fact, it's not true for all $n$: at $n=41$, the corresponding value is not prime (it is divisible by 41).


How to model conditionals with first-class functions? Since languages with recursible first-class functions are Turing-complete, they should be able to express anything expressible in any other programming language. Therefore, it should be possible to model conditional expressions (i.e. if-statements) with first-class functions. Could someone illustrate how to do this?

The usual encoding of booleans, due to Church, is

$$
{\sf true} = \lambda x. \lambda y. x
\qquad
{\sf false} = \lambda x. \lambda y. y
$$

Roughly, "true" is the function which takes two arguments $x,y$ (first takes $x$, then also takes $y$) and returns the first one. Instead, "false" returns the second one.

If-then-else is then encoded as applying an encoded boolean to the "then" and "else" branches. In this way, the boolean chooses the right value to return.

$$
{\sf if}\ b\ {\sf then}\ t\ {\sf else}\ e = b\, t\, e
$$

It is then easy to check the so-called "$\beta$" laws:

$$
{\sf if\ true\  then}\ t\ {\sf else}\ e
= {\sf true}\, t\, e
= (\lambda x.\lambda y.x)\, t\, e
= (\lambda y.t)\, e
= t
$$

and

$$
{\sf if\ false\  then}\ t\ {\sf else}\ e
= {\sf false}\, t\, e
= (\lambda x.\lambda y.y)\, t\, e
= (\lambda y.y)\, e
= e
$$

Essentially, these laws state what happens when you "construct" a boolean (using the constants $\sf true, false$), and then "destruct" it later on (using it in an $\sf if\ then\ else$).

Using functions in this way, one can write encodings for all the usual data types, like naturals, pairs, variants, lists, trees, etc.


A problem in NP but not NP-complete? Graph isomorphisim is not proven to be NP-complete what would it imply if it were possible to prove that there are some problems which are in NP set of problems but not in NP-complete set.

As written, the question is a bit trivial: if NP = NP-complete, then since P $\subseteq$ NP we get P=NP since every problem in P would be NP-complete.

I suspect what's meant, though, is the following:

  Suppose there are no NP-intermediate problems; that is, that every problem in NP is either in P or is NP-complete. What does that tell us about P vs. NP?

This is definitely not trivial, but the answer turns out to be the same: Ladner's theorem says that if there are no NP-intermediate problems then P=NP.

It's worth noting that Ladner's theorem is constructive in that Ladner provides a specific example of a language $X$ such that if P$\not=$NP then $X$ is NP-intermediate. (I'm not making the stronger claim that it doesn't need the excluded middle, although I suspect that's true.) Moreover, the proof is pretty short; see e.g. here.


Iteratively find and modify a certain element in a set in $\log n$ per iteration I've looked around and can't find my answer.

I have a set of $n$ numbers. In each iteration I would like to find an arbitrary number and change it. Is it possible to perform each iteration in $\log n$ time?

There are data structures like a min-max heap which allow insertion and deletion in $\log n$ time, but that only allows deletion on the min/max values.

Yes, you can achieve that running time if you use the right data structure.  You might want to look at some other data structures, such as AVL trees, red-black trees, or other similar techniques.  See, e.g., https://en.wikipedia.org/wiki/Search_data_structure, https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree,  or your favorite data structures book.


How do you implement a language with greater capabilities using subordinate languages? I've heard that C++ and Python where implemented using C. How can someone make an object oriented language out of something that doesn't support objects?

I've read in the book "Math You Can`t Use - Patents, Copyright and Software" that code is considered an equivalent of mathematics because it will eventualy be ran on cirquits that work and interact based on mathematical logic.

If a limited tool like C can produce a tool with further capabilities like C++, does that mean that mathematics can be used to create "better" mathematics? That seems to contradict Gödel's incompleteness theorem.

What is the essence of this trancedance from simple procedural to object oriented? Is there some code written in C that C++ and Python use or are they written in a completely different paradigm from the ground up?

The key point is that essentially all programming languages are equally powerful, and as powerful as we know how to make any computing system. That is, they can all simulate a Turing machine, up to the limitations of the computer they're used on. (Real computers can run out of memory; Turing machines can't.)

The only differences between programming languages is in how convenient it is to express certain ideas. For example, you can implement objects in C using structs containing function pointers, though it's not very convenient because the compiler doesn't help you much so you have to do a lot of things manually that something like C++ would do automatically for you.


How to construct CFG for language We have alphabet $\Sigma = \{ { a, b} \} $.

How to construct CFG for language $\Sigma^{\ast} - \{a^{n}b^{n} | n \ge 0 \}$.

I suggest that is very easy, but I can't invent. I know PDA for this language if it can help.

Split into parts that you can handle. All strings not of the form $a^*b^*$. All strings of the form $a^ib^j$ with $i< j$. Then all strings ....


Selecting k rows and k columns from a matrix to maximize the sum of the k^2 elements Suppose $A$ is an $n \times n$ matrix, and $k \ge 1$ is an integer.  We want to find $k$ distinct indices from $\{1, 2, \ldots, n\}$, denoted as $i_1, \ldots, i_k$, such that

$\sum_{p, q = 1}^k A_{i_p, i_q}$

is maximized. In words, we seek $k$ rows and the corresponding $k$ columns, such that the intersected $k^2$ elements of $A$ have the largest sum.

This problem can be formulated as a quadratic assignment problem, which is NP-hard and admits no polynomial time algorithm with constant approximation bound. I'm just wondering if for this specific problem (as a special case of quadratic assignment), there exists a poly-time algorithm with constant approximation bound. Thank you.

There is an easy reduction from the well-known NP-complete problem MAX-CLIQUE to your problem. Recall that in MAX-CLIQUE we are given a graph $G$ and an integer $k$, and have to decide whether $G$ contains a $k$-clique. We can recast this as an instance of your problem as follows: the matrix $A$ is the adjacency matrix of your graph, and the goal is to determine whether there is a choice of indices for which the sum equals $\binom{k}{2}$.


Time complexity of removing a vertex from a graph represented as collection of adjacency lists I'm trying to reason about the time complexity of removing a vertex from a graph represented as an adjacency list, which has $n$ vertices and $e$ edges. It is a directed graph, and the list associated to any particular vertex $v_i$ contains the vertices directly reachable from $v_i$ (i.e. the edges with origin $v_i$).
Let's assume that the graph is represented as a hash map, which pairs a certain vertex with its adjacency list, which is a linked list. Iterating over a linked list of $m$ elements has a time complexity of $O(m)$, and deleting a node of the list as one iterates over it has constant complexity $O(1)$.
In order to remove a vertex $v_d$ I would need to:

Remove the pair with key $v_d$ from the hash map (which is $O(1)$).
Iterate over the adjacency lists of the rest of the vertices, removing any occurrence of $v_d$.

The second step would mean iterating over each vertex $v_i$ in the key set of the hash map (~$n$ vertices, after having removed one), and for each vertex $v_i$ iterate over its adjacency list, which is of length $e_i$.
Now, it is clear that $\displaystyle\sum_{i=1}^{n} e_i = e$, so my first thought is that the time complexity of the second step is $O(e)$, and so is the total cost of removing a vertex in this situation. Note how this is independent of the number of vertices in the graph.
However, I'm thinking about the case in which there are no edges at all. In that case, step two still requires iterating over the whole list of vertices, so I'm lead to believe that the number of vertices has to play some role inthe time complexity of the method.
What is the actual time complexity in this set up and how can you reconcile the two (apparently contradictory) conclusions I've reached?

In step 2, vertices with no neighbours have an empty adjacency list, but it still takes one time step to realise that the list is empty. So the runtime is $\sum_{i\in[n]\smallsetminus \{d\}} \max(1,e_i)=O(n+e)$.


Trading States for Symbols with a Turing Machine Show that for each string $w ∈ \{0, 1\}^∗$ there exists a stay-put Turing machine

$$M_w = (Q, \{0, 1\}, \Gamma, \delta, s, q_{\mathit{accept}}, q_{\mathit{reject}})$$

with $|Q| ≤ 5$ states that starts on a blank tape in state $s$ and ends in state $q_{\mathit{accept}}$ with the
tape content $w$ beginning in the first cell and the head under that cell.

That is, starting on a blank tape, the machine outputs $w$ and stops in $q_{\mathit{accept}}$.

I know that if there were infinite states then we could put each letter into its own state so that we could print the letter when needed, but I don't know how to reduce it to 5 states.

Here is one idea. Let $|w| = n$. We will have a tape symbol for each number in $\{0,1,\ldots,n\}$, which we will denote by $\langle i \rangle$. The machine starts by writing $\langle n \rangle$ on the tape. Then it repeatedly performs the following steps:

Read $\langle i \rangle$.
Depending on the value of $i$ and on $w$, switch to a write-0 or a write-1 state.
In write-$b$ step, move right until reaching the first blank, write $b$, then move left until reaching a cell of the form $\langle j \rangle$.
Replace $\langle j \rangle$ with $\langle j-1 \rangle$, or terminate if $j = 0$.

The exact implementation of this algorithm depends on your exact model. In your model, you might be able to do it using 5 states. But in any reasonable model, $O(1)$ states are needed, regardless of $w$.


General start rule question for a context free grammar Suppose I have a context free grammar described:

  $S \rightarrow 0SS1$
     $S \rightarrow 1$
     $S \rightarrow \epsilon$

Because the first rule is considered the start rule does that mean that this grammar could never generate a string that starts with 1 or can you apply the second $S$ rule first to generate the string?

Yes you can apply the second rule you have written if you'd like. Since $S$ is your start symbol, you can apply any of its productions when you begin. It might be clearer if you wrote it as follows (where $|$ denotes or):

  $S \rightarrow 0SS1 \; |\; 1 \; | \; \epsilon$


Sequence of total languages whose limit is turing complete First let me clarify what I mean by a number of things.
A language is a decidable set of natural numbers which encode functions from natural numbers to natural numbers $ \mathbb{N} \to \mathbb{N}$. A language is said to be total if it only encodes total functions from naturals to naturals. A language is turing complete if it can encode all functions from natural numbers to natural numbers that a universal turing machine can. Because I can make a turing machine than infinitely loops on some inputs I can encode a non-total function with a turing machine. So being turing complete implies being non-total.

An interpreter of a language $L$ is a function $I_L : \mathbb{N} \to \mathbb{N}$ such that $n \in \mathbb{N} \mapsto I_L(pair(p, n))$ is the same function that $p$ encodes forall $p \in L$. A nice theorem says that if a language is total, it cannot encode such a function.

A while back I was wondering "is there a language that could only be interpreted by a turing complete language". Now the answer seems obvious to me (thanks to some help from stack exchange); no, no such things exists. You can always just add an interpreter for the language to get a total language that can't be interpreted by the previous one.

Clearly this gives raise to a sequence of total languages. Namely the first language you pick, then that language plus its interpreter, then that language plus its interpreter, etc...

But I have no reason to believe that this sequence is even particularly useful. I have some vague intuitive sense of a the limit of this sequence but I can't seem to pin down what a limit of a sequence of languages is. I do not think the limit of this sequence is turing complete. I do think the limit of this sequence is a partial language however. Namely, it seems the limit language should be able to interpret itself (perhaps this is not a good intuition?).

Does such a notion of a limit exist? If it does is there a sequence of total languages whose limit is turing complete? If such a limit exists is it computable? If it is computable, why does no one use such a language?

Bonus: Since we are talking limits anyhow. Is there a topology of languages to be considered here?

I'm not sure I full get your encoding and based on the comments there seem to be some problems with it, but I'll nevertheless provide my answer (or "answer", if you prefer).

A sequence of languages (your terminology) that satisfies your constraints is a sequence where the $i$th element in the sequence runs the Universal Turing machine for $i$ steps or until the machine halts, whichever comes first.

Clearly, each element in this sequence is total, but the limit is a Universal Turing Machine.


Find Minimum number of platforms The questions is as follows with the answer:

  Q) Given the arrival and departure time of various trains in a station. Calculate the minimum number of platforms required such that no train has to wait for another train to vacate the platform. The question basically means calculate the maximum number of trains that would be present in the platform at any given time.

  Answer

  Sort the arrival time and sort the departure time, keep a count initialized to 0. compare the first element of the arrival time with the first of departure, increase the value of count if the value at current Index at arrival is less than the value index at departure and increment the arrival index, and vice versa. Keep the maximum count that you see.

MY PROBLEM: I have tried hard but I am not able to get why to sort both arrival and departure timings? As a train is single entity and you sort arrival and departure separately how can we know which train arrival matches with its departure? I am facing the same problem in closest pair problem as why to sort x points and y points separately.

The answer is very simple: try to construct an algorithm which doesn't sort both arrival and departure times, and see if that's possible. If so, then there is an alternative algorithm which indeed doesn't requiring both times. Otherwise, you will understand why this is necessary.

The intuitive explanation of why we sort both arrival and departure times is that we are actually sorting all events. There are two types of events, arrival and departure, and we want to process them as they happen. We don't care about matching departure times with arrival times – that is, for our algorithm to work, we don't need to know which train is involved, only that a train has arrived or has left the station.

This actually suggests a way to restate the algorithm you describe. Sort all events according to time. Now go over them in order of increasing time (we assume for simplicity that all times are distinct). Keep a counter of the number of trains in station. When processing an arrival event, increase the counter; when processing a departure event, decrease the counter. Keep track of the maximal value of the counter.

The algorithm you describe instead sorts the arrival and departure times separately, and then performs an online merge (same algorithm as in merge sort for merging two sorted lists). I don't know why they described the algorithm this way rather than the way I described it.


What is a final state? I am studying DFA's, but I've been struggling to find an explanation of what does the final state mean? I know that it is indicated by double circle on the graph, but what does it imply?

If you want to know what a mathematical object is, you need to read its definition. So, I imagine you've seen the definition of finite automata, and it has something called a "set of final states", and the definition probably doesn't say what that means.

OK, that means that, for now, the author is just giving a name to this set of states. They surely wouldn't bother naming something if it was never going to be used, so we need to keep reading. The very next thing you read is probably a desciption of how an automaton processes its input by moving from state to state as it reads the characters. That doesn't seem to involve the concept of final states, so we keep reading some more. The next thing is probably a definition of what inputs are accepted by the automaton. That definition does involve final states, and it tells you exactly what their role is.

The moral of the tale is that, if you want to know what a mathematical object is, you need to read its definition. If you want to know what it's for, you might have to read a bit more, after its definition. (A good writer will warn you if the point of something isn't going to be revealed for a while.) If you want to know why anyone should care about the object, you might have to do a lot of reading, or find someone (or somewhere! ;-) ) to ask questions.


Concatenation of two Turing machines If I have two Turing machines A and B, and I want to use an output of A as an input to B, how is it going to work? Can I just run A, keep the input tape, and then run B (without affecting the number of states A and B? Or do I have to combine an halting state of machine and an initial state of the other machine?

Given two Turing machines $M_1$ and $M_2$, assume that their state sets are disjoint, i.e, $Q_1 \cap Q_2 = \emptyset$. Define $\Sigma_3 = \Sigma_1 \cup \Sigma_2, Q_3=Q_1\cup Q_2, F_3=F_2$.

Modify $M_1$ so that it prints its output starting from the first (leftmost) tape cell, then move the tape head to the leftmost cell and enter the $M_2$'s start state. This makes sure that $M_2$'s input is the $M_1$'s output. You may also need to add new states to $Q_3$ .


Turing reducibility implies mapping reducibility The question is whether the following statement is true or false:

$A \leq_T B \implies A \leq_m B$

I know that if $A \leq_T B$ then there is an oracle which can decide A relative to B. I know that this is not enough to say that there is a computable function from A to B that can satisfy the reduction.

I don't know how to word this in the proper way or if what I'm saying is enough to say that the statement is false. How would I go about showing this?

EDIT: This is not a homework problem per se, I'm reviewing for a test.
Where $\leq_T$ is Turing reducibility, and $\leq_m$ is mapping reducibility.

The statement is false.

Say B is the Halting problem and $A = \overline B$. Then, given oracle to the halting problem we can easily decide its complement.

However it is not true that $A \le_m B$ since $B\in RE$ and $A\in coRE$ but both are undecidable (i.e., if $A \le_m B$ was true, then $B=HP$ is both in $RE$ and $coRE$, that is,  $B\in R$ which is a contradiction).


Counting trees in a graph I would like to know how to modify DFS/BFS in order to return the number of the trees present in a graph. I know that a tree is an acyclic connected graph, and I think that I have to initialize a counter somewhere, but I don't know where. I made the procedure "is-tree(G)" where G is the graph. It returns true if the subprocedure "is-connected(G)" also returns true and if the number of the arcs in G = number of nodes in G - 1, otherwise the procedure returns false. At this point I don't know how to count all the possibile subgraphs which are also trees.

So here is a pseudo code of what i proposed. Maybe i was not clear.

1) Start with a node (Your start node)

2) For each node from root node, try to find a node (if it exists) that has atleast one node that is not visited. (If the graph is a cyclic, this condition is true). To do this, you may use a hashset of visited children for each iteration.

3) do the above till you reach a node which has no children. Thats the end of the algo where you found 1 tree in the graph. For back tracking i think you want to maintain a hashmap of all the nodes that you started with and the value field contains all the connected nodes to the graph. The point you reach a leaf node without violating point(2), you start back tracking to find the parent of the current node; ie the leaf node to the start node.

Thats your subgraph which is a tree.

PS- Leaf node in this case would be a node which has no nodes connected to it/all the other nodes connected to it are already visited previously/only inward connections


Satisfiability of at least k linear equations over Z2 is NP-hard Given a system of $m$ equations in $n$ boolean variables:

$$\begin{align}
a_{11}x_1 + a_{12}x_2 + \dots +a_{1n}x_n &= b_1\pmod2\\
a_{21}x_1 + a_{22}x_2 + \dots +a_{2n}x_n &= b_2\pmod2\\
&\;\vdots\\
a_{m1}{x_1} + a_{m2}x_2 + \dots +a_{mn}x_n &= b_m\pmod2
\end{align}$$

Where all $a_{ij}, x_i$ and $b_i$ are $0$ or $1$, I want to prove that the decision problem of finding if there is a vector $x$ that satisfies at least $k$ equation, is NP hard.

I was given a hint to reduce from 3-SAT, so I am trying to build from each clause in the 3-SAT formula several equations, such that a constant number of them is satisfied iff the clause is satisfied. But I am not sure how to impose this restriction of a constant number of equations satisfied (for all different truth assignments that satisfy the given clause).

Consider any clause $x \lor y \lor z$, and the following table:
$$
\begin{array}{c|c|c|c}
\text{satisfied literals} & [x]+[y]+[z] & [x\oplus y] + [x\oplus z] + [y\oplus z] & [x\oplus y\oplus z] \\\hline
0 & 0 & 0 & 0 \\\hline
1 & 1 & 2 & 1 \\\hline
2 & 2 & 2 & 0 \\\hline
3 & 3 & 0 & 1
\end{array}
$$
Here $[x]$ is 1 if $x$ is satisfied and 0 otherwise.

The first row sums to 0, and the rest sum to 4 (ignoring the column labeled "satisfied literals"). Can you use this to your advantage?


How to get a base-3 representation of an integer using a stack? Assuming that a stack data structure is available, how can this data structure be used to compute a representation of an integer in base three? For example, the algorithm for printBase3 would return 12020 on input 141.

ok I think I found the solution to my question

So if n = 141, 12020 would be printed to the screen.

Solution:

          public static void printBase3(int n){
           if (n/3 == 0)
           System.out.print(n);
          else{
          printBase3(n/3);
          System.out.print(n%3);
          }
        }


Unbiased random number generator we have  a six-sided dice numbered from  1 to 6, and each has the probability $p =\frac{1}{6}$. My task is to create a unbiased method to generate a random number  from 1 to 10 using the given dice.
I am aware that the method should maps the following set $$ \{1,\dots 6\}^k\mapsto \{1,\dots, 10\}$$, with $k$ is the number of time we throw the dice. For sure not the 36 elements will be mapped into the set  containing  1 to 10. What i mean, the method will use a while loop and only stops if  a certain tuple is found. My task then is the find those tuples and prove each thoese 10 tuples has the probaitly of $\frac{1}{10}.$
I think $k$ should be 2 in this case , but then i am not quite sure how to extract the  10 elements from 36 elements ($6^k$,with $k=2$) and have a probability of $p'=\frac{1}{10}$.
can we maybe also  generalize that for$ n$ elements ?

$$ \{1,\dots 6\}^k\mapsto \{1,\dots, n\}  $$
I will appreciate any good ideas.

Here is the algorithm for $n=10$.

Throw the dice twice to get $(x,y)$.
Compute $r=x + 6(y-1)$. If $r\le10$, return $r$ and stop.
If we have reached here, go back to step 1.

Here is the algorithm for general $n$.

Compute $n=\lceil \log_6k\rceil$.
Throw the dice $n$ times to get $(x_1, x_2, \cdots, x_n)$.
Compute $r=x_1+6(x_2-1)+6^2(x_3-1)+\cdots+6^{n-1}(x_n-1)$. If $r\le k$, return $r$ and stop.
If we have reached here, go back to step 2.

There are many variations, of course.

For example, in step 2 for $n=10$, we can return $r=10 - (x + 6(y-1))\%10$ and stop  when $x+6(y-1)\le30$ instead. This will reduce the chance to go to step 2. Here % is the remainder operator.

For example, here is gnasher729's algorithm for $n=10$. Throw a dice until we get a number $x\not=6$. Throw the dice once more to get another number $y$. Return ((x - 1) * 6 + (y - 1))%10+1$.

(Exercise 1.) (One minute or less) Devise an algorithm for $n=3$.

(Exercise 2.) Devise an algorithm for $n=7$. Try making its expected number of rolls as small as possible.

(Exercise 3.) Prove that the expected number of rolls in gnasher729's algorithm is the minimum among all algorithms.

(Exercise 4.) Given any $n>1$, devise an algorithm with the least expected number of rolls.


Why is $\sum_{i=0}^n\sqrt{i}\log_2^2i \geq \Omega(n\sqrt{n}\log_2n)$? Where $\Omega(f)$ denotes the set of functions with f as lower bound, why is $\sum_{i=0}^n\sqrt{i}\log_2^2i \geq \Omega(n\sqrt{n}\log_2n)$?

How can the function on the left be compared to a whole set? I thought usually a function is an element of the set, i.e. $g\in\Omega(f)$ or it is not, i.e. $g\notin\Omega(f)$.
If it would say $\sum_{i=0}^n\sqrt{i}\log_2^2i \in \Omega(n\sqrt{n}\log_2n)$ instead, I still would not understand why it is true. How do you evaluate the limit of the left side?

The notations $f = \Omega(g)$ and $f \geq \Omega(g)$ are identical. In both cases, they mean that there exists a positive constant $C$ such that for large $n$, $f(n) \geq Cg(n)$.
You can estimate the sum as follows:
$$
\sum_{i=0}^n \sqrt{i} \log_2^2 i \geq
\sum_{i=n/2}^n \sqrt{i} \log_2^2 i \geq
\sum_{i=n/2}^n \sqrt{n/2} \log_2^2 (n/2) \geq
\frac{n}{2} \cdot \sqrt{n/2} \log_2^2 (n/2).
$$
The latter expression is $\Omega(n^{3/2} \log^2 n)$, which is better than what you claim.
You can also estimate the sum by an integral. According to Wolfram alpha,
$$
\int \sqrt{x} \log^2 x \, dx = \frac{2}{27} x^{3/2} (9\log^2 x - 12 \log x + 8) + C.
$$
Since $\sqrt{i} \log_2^2 i$ is increasing, we have
$$
\int_0^n \sqrt{x} \log^2 x \, dx \leq \sum_{i=1}^n \sqrt{i} \log^2 i \leq \int_1^{n+1} \sqrt{x} \log^2 x \, dx,
$$
from which we see that your sum is $\Theta(n^{3/2} \log^2 n)$.


Data structure with search, insert and delete in amortised time $O(1)$? Is there a data structure to maintain an ordered list that supports the following operations in $O(1)$ amortized time?

GetElement(k): Return the $k$th element of the list.
InsertAfter(x,y): Insert the new element y into the list immediately after x.
Delete(x): Remove x from the list.

For the last two operations, you can assume that x is given as a pointer directly into the data structure; InsertElement returns the corresponding pointer for y.  InsertAfter(NULL, y) inserts y at the beginning of the list.

For example, starting with an empty data structure, the following operations update the ordered list as shown below:

InsertAfter(NULL, a) $\implies$ [a]
InsertAfter(NULL, b) $\implies$ [b, a]
InsertAfter(b, c) $\implies$ [b, c, a]
InsertAfter(a, d) $\implies$ [b, c, a, d]
Delete(c) $\implies$ [b, a, d]

After these five updates, GetElement(2) should return d, and GetElement(3) should return an error.

NO.

Fredman and Saks proved that any data structure that supports these operations requires at least $\Omega(\log n/\log\log n)$ amortized time per operation.  (This is reference [1] in the paper by Dietz that you mention in your first comment.)  The lower bound holds in the very powerful cell probe model of computation, which only considers the number of distinct memory addresses accessed by the update and query algorithms.

Without some additional assumptions about the update and query operations, Dietz's data structure is the best possible (at least up to constant factors).


Compare two complexity functions having the same asymptotic complexity For a certain problem two solution algorithms (A1 and A2) with the following execution times have been found:

$A1: T_{A1}(n)=4n^2 +7log(n^2)$
$A2: T_{A2}(n) = 4T(n/2) + log(n)$

Say, technically justifying the answer, which of the two algorithms is preferable for input of size
sufficiently large

Here my solution

For $A1$ there is no recursion, the predominant term is $4n^2$ so we can say:

Complexity of $A1 = O(n^2)$

For $A2$ we do have recursion, Let's use the Master Theorem:

$a = 4$, $b = 2$  and $f(n) = log(n)$

$$f(n) < n^{\log_{b} a}$$
$$log(n) < n^{\log_{2} 4}$$
$$log(n) < n^2$$

Hence, $T_{A2}(n) = \theta(n^2)$

Here comes my question: Which one is preferable and why ?

I'd say there is no difference since both algorithms have an upper bound of $c\cdot n^2$

Although, you cannot find the arbitrary constant c from master theorem, you should check using different size inputs which algorithm is faster, because even though both are upper bounded by c*n^2, if we have 4*n^2 and 1/4*n^2, still 1/4*n^2 is 16 times faster !!

A very important point is that your second algorithm seems to use divide and conquer method. This means that maybe it can be parallelized (in order to use more space but less computing time). For example, assuming an ideal choice of pivots, parallel quicksort sorts an array of size n in O(n log n) work in O(log² n) time using O(n) additional space.


Turing machines: can a machine write to a finite number of memory cells, but not halt? I am trying to reduce the Halting problem to show another problem is undecidable. The problem involves a program that is true if a machine $M$ writes to an arbitrary amount of memory, and false if it writes to a finite amount of memory cells. I am now thinking, is writing to a finite amount of memory cells equivalent to halting, or can there be cases where a machine writes to a finite amount of memory cells without halting?

Thank you in advance!

Consider a Turing machine that repeatedly moves its head right, then left, then right, then left, and so on.


Is there such thing as "sequential types"? I am wondering how you could possibly define the implementation of an imperative function as a type. Is it possible? Currently I only see the input parameters and output result used in the definition of a function type, but how could you also include the implementation in the type definition?

The seminal paper on this topic is Linear Types Can Change the World! by Phil Wadler.
Of course, with a title like that, you know it has to be a Wadler paper. It's a pun, the implication being that linear/uniqueness type system allows you to represent operations which mutate the world state.
You can use linear types today in languages such as Clean. See, for example, Aachen et al, High Level Specification of I/O in Functional Languages.
In logic languages, you can do the same thing with strong modes rather than strong types, such as in Mercury. (Full disclosure: I'm one of the original Mercury developers.) See Fergus Henderson's honours thesis, Strong Modes can Change the World!
EDIT
I think I may have misinterpreted the question, which I thought was about types for imperative code.
The answer to your question is "yes, absolutely". There is a tradeoff between types and programs. At one end of the spectrum, you have a completely dynamic type system, where every program has the same type. At the other end, you have a hyper-static type system, where every type only has one program that is of that type, with the type essentially encoding the program.
In the middle ground, there are many programming languages whose type systems are Turing-complete, including Haskell, Java, TypeScript, and Rust.


Why is left recursion and left factoring no problem in bottom up parsing? i am asking myself why is LR and LF no problem in bottom up parsing. I do know that we do right most derivation and so the right most non terminal is getting reduced.
But why is this then a problem in LL(k) parsing?

LL parsing must predict which production will be used before it starts parsing the contents of that production. (It is a top-down parse — it constructs the parse node and then fills in the children.)

LR parsing is bottom-up; first it lets the children be recognised, and only then does it apply the production and create the parse node. Consequently, it does not need to know which production will be used until the end of the production, so it can handle a grammar where two or more productions start with the same symbols.

Also, since LR parsing does not immediately expand the predicted production onto the stack (or recursively call itself to parse the predicted production) recursive productions are not problematic.


algorithm for finding a straight line to separate class I want create algorithm, which find a straight line which will separate the most objects from the class. The line must be parallel to the X or Y axis. Example:

Above example present two class: circles filled and unfilled. Red line is a solution to the problem. Has anyone the idea how to find such a simple?

First sort data base on their $y$ value. Then find the minimum and maximum value between members of the second class which is denoted by $y_{min_2}$ and $y_{max_2}$, respectively. Then, line with equation of $y = y_{min_2}$ and $y = y_{max_2}$ are candidate. We can count the number of first class member in sides of these two lines in $O(\log(n))$.

Therefore, we find an algorithm which works in $O(n\log(n))$.


Difficulties proving when a language is in P or is NP-complete I have some difficulties in understanding how to prove when a language is in P or is NP-Complete. Specifically, consider the following decision problems w.r.t undirected graphs $G = (V, E)$:

$L_1 = \{ \langle G = (V, E), k\rangle \mid \text{$G$ consists of connected} \\ \text{components of size at most $\log|V|$ each, and has a vertex cover of size $k$}\}$

$L_2 = \{\langle G = (V, E), k \rangle \mid \text{$G$ consists of two connected} \\ \text{ components  of size  $\frac{|V|}{2}$ each, and has a vertex cover of size $k$} \}$

I think that $L_1$ is in $\text{P}$, and $L_2$ is in $\text{NP-complete}$. Am I right? How can I prove that?

The language $L_1$ is in P since you can brute force an optimal vertex cover in each connected component.
The language $L_2$ is NP-hard by reduction from vertex cover. Roughly, given an arbitrary graph, we have to make it connected and to add another connected component, controlling the change of the minimum vertex cover throughout the process.


What's the difference between phi and lambda in regular expression? I've been learning on Formal Languages and Automata of Peter Linz(6th edition).
In the chapter 3 of this book, it explains the primitive regular expression.

But I don't know what is the difference between $\phi$ and $\lambda$.
Of course, I know $\lambda$ means the empty string, so that $\lambda s=s\lambda$.
And the textbook explains the meaning of $\phi$ is the empty set.
And more, the textbook explains that $\phi$ can be accepted by a deterministic finite automata $\left< Q, \Sigma, \delta, q_0 , F \right>$ in which $Q=\{ q_0, q_1 \}$, $\forall a \in \Sigma:\delta(q_0,a)\text{ is not defined}$, and $F=\{q_1\}$.

So, I guess the meaning of the $\phi$ is the rejected string.

But How can the expression $(\phi *)*$ mean $\lambda$?
And what's the meaning of the expression $a\phi$?

You need to distinguish between regular expression syntax and its interpretation aka semantics.

"$\lambda$" is a symbol representing the set that contains only the empty string $\{\varepsilon\}$).
"$\phi$"¹ is a symbol representing the empty set of strings $\emptyset = \{\}$.

The difference becomes apparent when you compute the interpretation $i$ of a regular expression:

$i(a\lambda) = i(a) \cdot i(\lambda) = \{ a \} \cdot \{ \varepsilon \} = \{a\}$

Note: I'm deliberately using $\varepsilon$ to denote the "real" empty string outside of a regular expression. Your source probably uses $\lambda$ for both; that obscures the fact that it's used in two different ways.
$i(a\phi) = i(a) \cdot i(\phi) = \{a\} \cdot \emptyset = \emptyset$.

If you don't follow that last line, revisit the definition of the concatenation of languages:

$\qquad\displaystyle A \cdot B = \{ a \cdot b \mid a \in A, b \in B\}$.

Do they really use $\phi$?


Kolmogorov Complexity proving there exists a constant for when if two strings are equal length When talking about kolmogorov complexity, I understand that it describes true randomness of given (for now) a string $x$, if we can describe x in less than the $|x|$ then its complexity is said to be

$C(x) \leq |x| + c$

my question lies in finding that c for a given problem.
Given this problem

there is a constant $c$ $∈$ $\mathbb{N}$ such that, for $\forall$ x,y ∈ $\{0,1\}^+$ with $|x|=|y|$
$H(x,y)$ is the hamming distance between $x$ and $y$
$ C(y)$ ≤ $C(x)$ $+ 2·H(x,y)·$(1 + $ \lceil log|x|\rceil $)$ + c$

How would I go about mathematically proving there there is a constant $c$ $∈$ $\mathbb{N}$ what does finding a constant tell us

Constant is defined as follows
as in what does this given a TM M and universal TM $u$ s.t. there exists a constant $c_M$ s.t. $C_u(x) \leq C_M(x) + c_M$(From Solomonoff and turing's theorem)?

Consider a procedure which has two inputs, $P$ and $DIFF$. Here $P$ is a self-delimiting program, and $DIFF$ is a list of indices, stored in some self-delimiting fashion (we leave the encoding vague for now). The procedure runs $P$, flips all the indices in $DIFF$, and prints the output. Using the invariance property of Kolmogorov complexity, we immediately get that there is a program of length $|P|+|DIFF|+O(1)$ which simulates the procedure above.

Now take any two vectors $x,y$. Let $P$ be a self-delimiting program of size $C(x)$ producing $x$, and let DIFF be the list of differences, which can be encoded using $H(x,y)(1+\lceil \log |x| \rceil)$ bits (this improves on your exercise; we're using the fact that $|x|$ is known by the procedure). It follows that $C(y) \leq C(x) + H(x,y)(1+\lceil \log |x| \rceil) + O(1)$.


Prove ALL$_{\text{TM}}$ is undecidable reduction problem Given ALL$_{\text{TM}}$ = { < M > | where M is a TM and L(M) = $Σ^*$ } show this is undecidable. I'm also told not to use Rice's theorem. I'm having difficulties with reduction type problems. How would you do a proof for this using a reduction of A$_{\text{TM}}$? Any pointers to resources are much appreciated.

You can reduce from $H_{TM}$:

For input $<M,w>$ return (the encoding) for a machine $M_ {M,w}$ such that on input $x$:

Simulate $M(w)$
$Accept$

It’s easy to show
$M_{M,w} \in ALL_{TM} \leftrightarrow <M,w>\in H_{TM}$


pseudo-polynomial reduction from 3-Partition to Partition A problem $\Pi'$ is pseudo-polynomially reducible to the problem
$\Pi$ ($\Pi' \leq_{pp} \Pi$) if, for any instance $I'$ of $\Pi'$, an instance $I$ of $Π$ can be constructed in pseudo-polynomially bounded time, such that, given the solution $S_I$ to $I$, the solution $S_I'$ to $I'$ can be found in pseudo-polynomial time.

It follows that, $\forall \Pi,\Pi' \in NP$, if $\Pi'$ is strongly NP-complete, and $\Pi' \leq_{pp} \Pi$, then $\Pi$ is strongly NP-complete.

And it is easy to show that "3-Partition $\leq_{pp}$ Partition."

Hence, I can conclude that Partition is strongly NP-complete. (However, we already know that Partition problem is ordinary NP-complete.)

Am I missing something!?

The claim

  It follows that, $\forall \Pi,\Pi' \in NP$, if $\Pi'$ is strongly NP-complete, and $\Pi' \leq_{pp} \Pi$, then $\Pi$ is strongly NP-complete.

is wrong (at least for how "pseudo-polynomically reducible" is defined here).

If $\Pi'$ is strongly $NP$-complete, then ``pseudo-polynomially reducible'' is equivalent to polynomially reducible.

Recall that a problem is strongly $NP$-complete if it is $NP$-complete even if we assume all the integers that appear in the input are polynomial in the length of the input.

Recall that an algorithm runs in pseudopolynomial time if it runs in polynomial time in the integers that appear in the input.

So, a pseudopolynomial reduction must run in time polynomial in the integers that appear in the input. Which, for a strongly $NP$-complete problem, can be assumed to be polynomial in the length of the input. Which means the reduction must run in time polynomial in the length of input.

So, if $\Pi'$ is strongly $NP$-complete, $\Pi' \leq_{pp} \Pi$ is equivalent to $\Pi' \leq_p \Pi$. Clearly, the existence of such a reduction does not imply that $\Pi$ is strongly $NP$-hard.

The only place in the literature that I can find any mention of this notion of ``pseudopolynomial reduction'' is in the appendix an OR & Management Science book. I cannot find any other literature mentioning this notion; one would expect to be able to find some mention of it in complexity theory circles.

We should use a different definition for $\leq_{pp}$. A pseudopolynomial reduction should be defined as a reduction, running in pseudpolynomial time, that in addition does not increase integer values in the input more than polynomially. Then the claim would hold true.


How to calculate time complexity of this problem? The problem statement:
Append the length of the string to the string while the length is less than or equal to 10

Input: "a" -> Output: "a12345678910"

Input: "abcde" -> Output: "abcde5678910"

The solution of the problem would require lesser time for a larger input. What should be the time complexity of this?

Given any reasonable computational model, we can provide an algorithm to solve your problem that reads the input (stopping at $10$ symbols should it be longer), stores the length, and while such length is less than $10$, appends the needed symbols and updates the total length.

This algorithm performs a constant amount of work at most $10$ times, which means that there exists a constant $c$ that bounds the running time for any size of input. By definition, such an algorithm has complexity $\Theta(1)$.

Observe that if you require the output to be a copy of the input for strings longer than $10$, then, depending on your computational model, you might need to physically copy the string, which takes time $\Theta(n)$.


A problem solved by weighted median Given a set of $n$ points $p_1,p_2,\ldots,p_n$ on a horizontal straight line (not necessarily in the order from left to right) with associated $x$-coordinates $x_1,x_2,\ldots,x_n$ (not necessarily in ascending orders) and associated weights $w_1,w_2,\ldots,w_n$ such that $\sum_{i=1}^n w_i = 1$. The objective is to find a point $p$ on the straight line such that the sum $\sum_{i=1}^n |x_p-x_i|w_i$ is minimum, where $x_p$ is the $x$-coordinate of $p$.
Prove that the sum $\sum_{i=1}^n |x_p-x_i|w_i$ is minimum at a point $p$, where $p$ is such that $\sum_{x_i<x_p} w_i < \frac{1}{2}$ and $\sum_{x_i>x_p} w_i \leq \frac{1}{2}$.

I am trying to use algorithm Select to prove it. The algorithm divides the x-coordinates into $[n/5]$ sublists such that first $[n/5]-1$ sublists contain exactly 5 elements each, while the remaining one contains $n \pmod 5$ elements. Then we find the median of each sublist. Repeat the same process for each sublist.
But I think I get the gist of the problem, I think it is sufficient to prove that if $q$ is any point on the line such that $q≠p$,then $\sum_{i=1}^n|x_q-x_i| w_i≥\sum_{i=1}^n|x_p- x_i | w_i$, where $x_q$ is the x-coordinate of $q$.
But I am going no where with this. Am I using the wrong approach? Should I be using algorithm Min to get this? If yes, can someone explain how to get it?

I don't see how using the select algorithm, or indeed any algorithm, is useful here. Instead, try to use the following observation:

  Let $I = \{ i : x_i < x_p \}$ and $J = \{ j : x_j > x_p \}$. Then the derivative of your objective function with respect to $x_p$ is $$\sum_{i \in I} w_i - \sum_{j \in J} w_j. $$


Not able to simplify a sum over reciprocals of $\log i$ Every time I solve these questions, I get stuck at the end where I need to find a closed form for the summation.

Here in this case, I have reached until this point:
$$
\begin{align}
T(n) &= T(n-2) + 1/\lg n \\
&= T(n-4)+ 1/\lg(n-2) + 1/\lg n  \\
&= T(n-6) + 1/\lg(n-4) + 1/\lg(n-2) + 1/\lg n. \qquad (1)
\end{align}
$$
Assuming $T(1) = 1$, I put $n - 6 = 1$ and substituted into (1):

$$ T(6) = T(1) + 1/\lg3+ 1/\lg 5+ 1/\lg7.$$

Now at this point I am not able to find out $\sum_{i=1}^n 1/\lg(2i-1)$.

On similar grounds , I become blank for another recurrence relation $T(n) = T(n-1)+1/\lg n$,
and my solution drills down up to here:
$$T(n) = T(1)+ 1/\lg2 + 1/\lg3 + 1/\lg4 + \cdots.$$

How do I evaluate such sums?

The trick to evaluate these sums is integration. We have the following very useful inequality for a non-decreasing $f(i)$:
$$ \int_0^n f(x) dx \leq \sum_{i=1}^n f(i) \leq \int_1^{n+1} f(x) dx. $$
In your case, $f(i)$ is in fact non-increasing, and in that case we have
$$ \int_1^{n+1} f(x) dx \leq \sum_{i=1}^n f(i) \leq \int_0^n f(x) dx. $$
For example, we can estimate
$$ \int_2^{n+1} \frac{dx}{\log x} \leq \sum_{i=2}^n f(i) \leq \int_1^n \frac{dx}{\log x}. $$
Unfortunately, the antiderivative of $1/\log x$ is not an elementary function, but is known as the logarithmic integral $li(x)$. Asymptotically, $li(x) \sim x/\log x$, and so we deduce
$$ \sum_{i=2}^n \frac{1}{\lg i} = \Theta\left(\frac{n}{\log n}\right). $$
In this particular case, we can obtain these bounds directly. Since $1/\lg i \geq 1/\lg n$, we obtain a lower bound of $(n-1)/\lg n$. Conversely, for $i \geq \sqrt{n}$ we have $1/\lg i \leq 1/\lg \sqrt{n} = 2/\lg n$, and so
$$ \sum_{i=2}^n \frac{1}{\lg i} \leq \sqrt{n} \lg 2 + n \frac{2}{\lg n} = O\left(\frac{n}{\lg n}\right). $$
If you want to obtain better estimates on such sums, the way to go is Euler–Maclaurin summation, which can be used to obtain an asymptotic series for $\log n!$, for example.


Context free grammar transformation to Normal Form I found a task where you need to transform context free grammar to normal form.
I'm a High Shcool student at this moment. But my Brother learning this at the university. He don't have much time to explan this, this is why I'm writting this question.
This is the task description: A chainless G grammar equivalent to G' grammar, all symbols of which can be used.
And the task is:
G : S → BC | DB
A → BD
B → b | D
C → CD | BC
D → bC | a | bB

If anybody can help me, please write a comment.
Thanks :)

If you are trying to convert the grammer into Chomsky Normal Form, consider applying this algorithm that can create a new normal grammer from an existing non-normal one.


Kolmogorov complexity of a sequence of prime numbers Let's say $p_1, p_2, p_3, \ldots $ is the increasing sorted sequence of all prime numbers. Prove that there exists a constant $n_0 \in \mathbb{N}$, so that for all $n \ge n_0$:
  $$K(p_n) < \log_2(p_n) − 2.$$
  Hint: Prime number theorem: $p_n \in \Theta (n  \ln n)$.

I think, I could have a program A, which generates $p_n$ in $n\ln n$. I could just give A the index of my prime number and it would generate it.

Another idea of mine was to prove it by contradiction and assume the opposite is true but I can't really make that work.
My biggest problem is that I can't find an upper limit to the representation of prime numbers and start from there. Normally I'd just use the factorization for integers…

Any help is appreciated!

Since we can generate $p_n$ given $n$, $K(p_n) \leq K(n) + O(1) \leq \log_2 n + O(1)$. The prime number theorem implies that $p_n = \Theta(n\ln n)$, and so $\log_2(p_n) = \log_2 n + \log_2\log_2 n \pm O(1)$. You take it from here.


Why LL(1) grammar generate all regular languages? I came across following:

  Every regular language has right linear grammar and this is LL(1). Thus, LL(1) grammar generates all regular languages.

I tried to get that.

Definition: Right linear grammar (RLG)
In right linear grammar, all productions are of one of the following forms: $A\rightarrow t^*V$  or $A\rightarrow t^*$, where $A$ and $V$ are non terminals and $t$ is terminal.

Definition: LL(1) grammar

A grammar $G$ is $LL(1)$ grammar if and only if whenever $A→α|β$ are two distinct productions of $G$, the following conditions hold:

For no terminal $a$ do both $α$ and $β$ derive strings beginning with $a$.
At most one of $α$ and $β$ can derive the empty string.
If $β⇒^*ϵ$, then $α$ does not derive any string beginning with a terminal FOLLOW(A). Likewise, if $α⇒^*ϵ$, then $β$ does not derive any string beginning with a terminal in FOLLOW(A). ($β⇒^*ϵ$ means $B$ derives $\epsilon$)

(Q1.) How definition of RLG ensures condition 1 in the definition of LL(1) grammar.

This answer says:

  All regular languages have LL(1) grammars. To obtain such a grammar, take any DFA for the regular language (perhaps by doing the subset construction on the NFA obtained from the regular expression), then convert it to a right-recursive regular grammar. This grammar is then LL(1), because any pair of productions for the same nonterminal either start with different symbols, or one produces ε and has $ as a lookahead token.

(Q2.) I read somewhere "eliminating left recursion from given grammar does not necessarily make it LL(1)". Then how turning grammar to right recursive will ensure its LL(1) (as stated in above quoted answer)?

(Q3). I didnt get the significance of "one produces ε and has $ as a lookahead token" in above quoted answer.

(Q4.) First quote in this question says right linear grammar is LL(1). How is it so?

(Q5.) This answer says "all regular languages have a LR(0) grammar", I guess its incorrect as LR(0) are DCFLs with prefix property which are not superset of regular languages. Am I right with this?

The quoted answer does not claim that every right regular grammar is LL(1). That statement would not be true.
What the answer claims is that the grammars produced by the indicated algorithm are LL(1). That statement is correct.
So, no-one is saying "every right-linear grammar" satisfies condition 1 (of the LL(1) definition) (your Q1). They don't all do so.
Alos, no-one is saying that just removing left-recursion is sufficient to guarantee LL(1) (your Q2). It isn't.
Finally, no-one is saying that every RLG is LL(1) (your Q4), not even the unattributed quote which starts your question. That quote says that every regular language has at least one RLG which is LL(1). Regular languages have many RLGs, and often not all of them are LL(1). These other RLGs are not relevant to the claim that all regular languages are LL(1).
That leaves your Q3, which is really about how to demonstrate the RLG produced by the algorithm satisfies conditions 2 and 3.
It's clear why that particular RLG passes condition 1. The algorithm starts with a DFA, and the DFA has only one out-transition on each symbol, by definition. One production is generated for each out-transition, whose first symbol is the out-transition's symbol. So it's not possible for two productions starting with the same symbol to be generated for the same state (= non-terminal).
Now, under what circumstances does the algorithm produce productions which derive $\epsilon$? Answer: these productions are generated for final states. @templatetypedef wrote the quoted answer thinking about the augmented grammar/language, in which every sentence ends with an end-marker $ which does not appear elsewhere. [Note 1]
Instead of augmenting the grammar or writing the LRG as implied by the cited answer, we could invent a new state F with no out-transitions on any symbol. We then add the production $A\to F$ to every final state $A$. And we add the production $F\to\epsilon$.
Now condition 2 is met becaus the only unit productions in the grammar are $A\to F$, so no non-terminal derives $\epsilon$ in any way other than directly through $F$. And condition 3 is met rather trivially because $FOLLOW$ of every non-terminal is empty, so no terminal is in any $FOLLOW$ set.
Since conditions 1, 2 and 3 are verified, we know that the grammar produced by converting a DFA is necessarily LL(1).

Notes

This augmented language is prefix-free, since all sentences end with the endmarker. Also, as we'll see, the augmented grammar produced by the algorithm is LL(1) and therefore deterministic. A deterministic prefix-free language is LR(0), which might explain the error you refer to in your Q5. The original unaugmented grammar is not necessarily prefix-free, and therefore might not be LR(0) although it is still LL(1). This is an illustration of why augmented grammars are useful.


Generating constraints to solve dependently-typed metavariables? In dependent-types, Miller pattern unification is used to solve a decidable fragment of higher-order unification. This allows dependently-typed languages to contain metavariables or implicit arguments.

There are many papers which describe, given a unification problem in the pattern fragment, how to find a solution if one exists. Examples include are (Gundry-McBride), (Abel-Pientka), and the original Miller paper.

What I'm wondering is, given a dependently typed program containing metavariables (or implicit arguments), how does one go about generating the problems that are passed to the unification solver?

There's a nice idiom, which is explained more in chapter 22 of Types and Programming Languages (it's used for polymorphism rather than dependent types, but the idea is the same). The idiom is as follows:

  A type checking system can be turned into a type inference system by making the rules linear and adding constraints.

I'll use the application rule as an example. The checking rule in dependent types is this:

$$\frac{\Gamma \vdash t:\Pi x:A.B\quad \Gamma\vdash u:A}{\Gamma\vdash t\ u: B[u/x]} $$

Linearizing this rule requires re-naming the 2 occurrences of $A$, such that we obtain:

$$\frac{\Gamma \vdash t:\Pi x:A_1.B\quad \Gamma\vdash u:A_2}{\Gamma\vdash t\ u: B[u/x]} $$

But this isn't correct anymore! We need to add the constraint $A_1\simeq A_2$:

$$\frac{\Gamma \vdash t:\Pi x:A_1.B\quad \Gamma\vdash u:A_2}{\Gamma\vdash t\ u: B[u/x]}\quad A_1\simeq A_2 $$

Note that $\simeq$ denotes equivalence modulo your conversion relation ($\beta\eta$, typically), just like for the conversion rule, but it is now a unification constraint, since you may have meta-variables in your terms.

In the course of type checking, you'll accumulate constraints like these, to potentially solve them all at once at the end (or earlier for efficiency reasons).

Now things can get trickier, because the type of $t$ itself could be a metavariable in context! A more generally applicable rule would therefore be

$$\frac{\Gamma \vdash t:C\quad \Gamma\vdash u:A_2}{\Gamma\vdash t\ u: B[u/x]}\ C\simeq \Pi x:A_1.B,\ A_1\simeq A_2 $$

Or alternatively, keeping the previous rule and adding the rule

$$\frac{}{\Gamma_1, x:C, \Gamma_2 \vdash x: A} C\simeq A $$

at variable lookup time.

Another useful remark is that in the checking system, the conversion rule only needs to be applied right before applications, and possibly once at the very end of the derivation. Since this rules correspond to a unification constraint in the inference system, this tells you where to place the constraints.


Difference between centralized computing and distributed computing using Client-Server I already understand that Distributed Computing is the breakup of having multiple clients rely on a single source, and having each client utilize other clients for information. But my confusion comes from a type of distributed computing, where one type is the client server model. From what I know, the client server model has multiple clients using a network to access a server. How does this differentiate from calling it centralized computing?

As a contrast to "distributed", "centralized" means one computer.  Sometimes (not so much nowadays) this may be a mainframe with multiple "dumb" terminals in which all the work happens on the mainframe and the terminals just take in inputs and display outputs.  If the terminals aren't "dumb", meaning they can do non-trivial computation of their own (and, in particular, maintain state), then this is essentially an example of a distributed, client-server system.  Your description of "distributed" corresponds to a peer-to-peer system which is but one form of a distributed system.

Admittedly, there has been a level shift in the terms, and/or they are applied at a logical level.  For example, Facebook would be considered a "centralized" system insofar as it's controlled by a single entity, as opposed to Diaspora which is decentralized.  I think it has become popular to use the term "distributed" when "decentralized" may be a better term.  Of course, Facebook has many servers spread across the world, and so it's infrastructure is very much distributed.  Similarly, a single data center for Facebook may logically be a single "server" but internally is a distributed system as well consisting of hundreds of physical servers.

Wikipedia does a pretty good job of outlining the key characteristics of a distributed system from a theoretical perspective:

  Three significant characteristics of distributed systems are:
  concurrency of components, lack of a global clock, and independent
  failure of components.

Though I would add to that list that the communication medium is unreliable.  The focus of distributed computing, in both theory and practice, is dealing with various forms of failure.  Wikipedia's use of the more generic term "component" suggest that this notion can be applied at different levels.  For example, you can fruitfully think of the various sub-systems of a single computer (on the motherboard) as forming a distributed system if your focus is on timing and failure issues.  Even single multi-core CPUs are becoming more and more like distributed systems with the cores as the "components".


Does the Kleene star distribute over each element? (0+1)* = 0* + 1*? Does the Kleene star distribute over each element? Is this true: $(0+1)^* = (0^* + 1^*)$?


Counterexample for equality in Quantified Boolean Formula I'm looking for a counterexample for the following (false) equality. It should exist.

$n$ is an odd integer.

$f(x_1, x_2 .. x_n)$ is a boolean expression in 3 CNF form with boolean variables x.

$A = \exists x_1 \forall x_2 \exists x_3 \forall x_4 ... \forall x_{n-1} \exists x_n: f(x_1..x_n)$

Note that the exists and forall are alternating and that the expression begins and ends with exist.

$B = \forall x_2 \forall x_4 \forall x_6 .. \forall x_{n-1} \exists x_1 \exists x_3 .. \exists x_n : f(x_1..x_n)$

Somehow I have a flawed proof that implies $A=B$. I'm looking for a simple counterexample, a 3 CNF formula with few variables, so I can find the flaw in my proof.

The equality is correct for $n=1$, so let's take $n = 3$. Let $f(x_1,x_2,x_3) = [x_1 \neq x_2]$. Statement $B$ states that for every $x_2$ there exists $x_1 \neq x_2$, which is correct. Statement $A$ states that there exists $x_1$ which is different from all $x_2$, which is incorrect.


Complexity of nearest codeword in cyclic codes Is it $NP$-complete given $c(x),g(x)\in\mathbb{F}_2[x]$ where $g$ generates a cyclic code of length $n$ (so $g\mid x^n-1$), and $\deg c<n$ to find the nearest codeword to $c$?

This is related to the following problem in finite fields: given $\hat{g},\hat{x}\in\mathbb{F}_{2^k}$, find the sparsest polynomial $F\in\mathbb{F}_2$ such that $F(\hat{g})=\hat{x}$.

The general Nearest Codeword Problem problem for an arbitrary code is NP-hard. It is known that the problem is in NP if you only need to check whether there is a codeword within some fixed distance $\delta.$

Moreover there some efficient approximation algorithms given by Alon, Panigrahy and Yekhanin available here.

I am unaware of any work using the cyclicity property. The above apply to arbitrary linear codes.


Count nodes within K-distance from all nodes in a set The problem is - Given an undirected tree with some marked nodes in a set and a positive number K. We need to print the count of all such nodes which have distance from all marked nodes less than K.

My first approach-

I ran bfs on every from each marked node given in the set and takes the intersection of the respective answers. The time complexity of this solution if there are m notes in the set would be O(m*(V+E)).
Can it be further optimized ?

My second approach-

If I find two nodes from set which are maximum distance from each other, I can say that all the nodes which are a distance less than k from these two nodes will also be at a distance less than k from other marked nodes in the set. Now, I have to apply bfs at only those two extreme nodes. But, the problem is How to find two nodes from set which are maximum distance from each other? I can only think of floyd warshall over here but that would be O(V^3).

What would be the most optimal solution to this problem?

Add a new node(let's say s) and connect it to all the marked nodes in the set. Then, find all the nodes which are at a distance less than k+1 from s and subtract number of marked nodes from it. T(n)=O(V+E)

In the second approach, we can actually find the two nodes (let's say uand v) with maximum distance between them in O(V+E). How do we find those vertices? Pick a vertex w and place it in a queue. While the queue is non-empty add the neighbors of the next vertex in the queue to the end of the queue. When the queue is empty, take note of the most recently removed vertex. This will be u. Perform the procedure again and you will have v. Check this link for proof.
https://stackoverflow.com/questions/9951363/finding-the-root-that-minimize-tree-depth


How is Memory Segmentation done in 8086? Basically what I know is that 8086 can address up to 1 MB of locations which are divided in 4 segments(code, data, extra and stack) 64 KB each. But 64 KB * 4 is 256 KB, which doesn't add up to 1 MB(1024 KB). So what about the rest of space.

The four segments you mentioned are not static - these are in fact registers that can point to any 64kb zone in the 1MB memory. By changing the value of these registers we can point to other fragments of the memory.

The exact computation of the effective address is performed using 2 registers: a segment register (CS,DS,SS,ES) and an offset register (usually BX, SI, DI, BP). Each one of those registers is 16bit.
To get the 20bit effective address,
the CPU performs
EA = SEGMENT_REG * 10h + OFFSET_REG (mod 20bits).
It is easy to see that by changing the SEGMENT_REG/OFFSET_REG (0000h-FFFFh), the above equation allows one to span the entire 1MB memory address space  (00000h-FFFFFh).


Recurence for Insertion Sort We can express insertion sort as a recursive procedure as follows. In order to sort $A[1,...,n]$ we recursively sort $A[1,...,n-1]$ and then insert $A[n]$ into the sorted array $A[1,...n-1]$.

How can I write a recurrence for the running time of this recursive version of insertion sort?

Actually, it is pretty simple. Let $T_n$ be the running time for a given array $A[1,...,n]$. As you've mentioned, we first sort $A[1,...,n - 1]$ whose running time is $T_{n-1}$ (since it has $n-1$ elements) and then we inset $A[n]$ to the sorted list, whose running time is $O(n)$ (since we need iterate over the whole array at the worst case).

Therefore, $T_n = T_{n-1} + O(n)$. And do not forget about the base case which is $T_1 = O(1)$.


Does $E_{TM}$ accpets the empty word $\varepsilon$? Let $L = E_{TM} = \left\{  \left<M \right> | M \text{ is a TM and L(M)} = \emptyset   \right\}$.

Does $L$ accepts the empty word $\varepsilon$?

In other words, is $$\varepsilon \in L$$

I'm a little bit confused by this.

My intuition says it doesn't since the empty set rejects every input.

I would answer that no, $\varepsilon \notin L$.

The reason is that the typical definition of a Turing machine is that its representation should contain a non-empty set of states and a non-empty tape alphabet.

In order to represent those, you typically would need a non-empty string.

However, as Yuval points out, you are free to define your own Turing Machine description language, and if you were to say "We use $\varepsilon$ to denote the "empty" TM (with alphabet 0), the TM that runs forever", you are free to do so, in which the answer becomes Yes.

I would go with No, $\varepsilon \notin E_{TM}$.


Copy on write is an interesting idea used on server systems. Does it make any sense on a smartphone? The data pages that are actually modified need to be copied. This approach, called copy on write, improves performance by reducing copying.

According to me it is unnecessary as every process has its own data. (not sure) A third process working with that data is really not possible.

Please tell me if it's possible, if possible then why? Also an example where this will be helpful would help.
Thank you.

Yes, copy-on-write makes sense on smartphones, too.  Smartphones are just computers, packaged to be small.  Smartphones run conventional operating systems, with multiple processes.  For instance, each app typically runs in its own process.  And yes, these processes do use shared memory, shared libraries, fork(), etc., so copy-on-write is useful (and is supported on typical smartphone operating systems).


I want to know where there is the flaw in my argument I came across following problem to finding whether the following language is decidable or semi-decidable or not even a semi-decidable.

$L: \{\langle M\rangle: M\space is\space a\space TM\space and\space |L(M)| \ge3\}$

Now thinking intuitively I conjectured that this language is semi-decidable. We can say yes when the input does belong to $L$. But, we can not say no when the input does not belong to $L$.

Now, I formulated following reduction from complement of halting problem $\overline{HP}$ which is not semi-decidable (non $RE$).

$\overline{HP}: \{\langle M, w\rangle : M\space is\space TM\space and\space it\space does\space not\space halt\space on\space string\space w.\}$

$\tau(\langle M,x\rangle) = \langle M'\rangle$.

$M'$ on input $w$ works as follows. It  erases w, puts $M$ and $x$ on its tape, and runs $M$ on $x$ and accepts if $M$ doesn't halt on x. Otherwise it rejects.

Proof of validity of reduction:

$\langle M,x\rangle \in \overline{HP} \implies M\space does\space not\space halt\space on\space x \implies M'\space accepts\space all\space inputs\space \implies|L(M')| \ge 3\implies M' \in L$

$\langle M,x\rangle \notin \overline{HP} \implies M\space does\space halt\space on\space x \implies M'\space rejects\space all\space inputs\space \implies|L(M')| < 3\implies M' \notin L$

According to above reduction $\overline{HP}$ should be recursively enumerable$(RE)$ which it is not. So, $L$ should not be $RE$ but it indeed is $RE$. So, my reduction must be flawed.

Please point out where I messed up.

accepts if $M$ doesn't halt on $x$

That's not something a Turing machine can do in general: informally, keep in mind that accepting has to happen at some finite stage while we can't in general tell that a program isn't going to halt in finite time (which is why HP is undecidable).

Your $M'$ is implicitly treating a co-r.e. event (non-halting) as r.e. (so that it can wait for it to occur and, when it does, halt and accept).

It's worth noting that we can do this with $HP$ as an oracle, and this shows (correctly) that $L$ is r.e. over $HP$. But we have to be careful about what exactly that means. At first glance we might think that "r.e. over $HP$" implies r.e., since $HP$ itself is r.e., but when a set is presented as an oracle we get both positive and negative information about it. So r.e. over $HP$ - that is, the domain of some $HP$-computable partial function - is not the same as r.e.: for example, $\overline{HP}$ is r.e. over $HP$.

This is a good example of how we have to keep track of the various different reducibilities we might be using, with the relevant ones here being Turing versus many-one: in the context of this question we're interested in many-one reductions but oracles correspond to Turing reducibility.


How can i prove that MAX-CUT is in NP? How can i show/explain/prove that Max-Cut is in NP?
"For a graph, a maximum cut is a cut whose size is at least the size of any other cut. The problem of finding a maximum cut in a graph is known as the Max-Cut Problem."

Thanks!

The decision version of MAX-CUT is as follows:

  Given a graph $G$ and an integer $k$, is there a cut in $G$ containing at least $k$ edges?

This version is clearly in NP.


How to generate (Java) source code in academically acceptable way - using abstract syntax tree? I am trying to do automated programming research: business software generation from the knowledge base that is implemented as Scheme (Lisp dialect) code (in the framework of http://opencog.org/ Atomspace). My question is - how to generate Java source code in academically acceptable way?

I know or I can imagine several ways:

Raw code generation: I can predict what classes and what members can be and create one large literal constant that is the source code.
Find or implement templating engine like Visual Studio's T4 templates
Find something about code generation from the UML models. I don't know yet how MDD tools implement such generation
I can genereate Java Abstract Syntax Tree in my Scheme code and then find tools generate Java source code from Java AST. Actually this could be - in my opinion - the most academically correct way that is also the best integrated in my workflow and that is the most extendable. My OpenCog Scheme Atomspace in effect is large hypergraph and Java AST is (hyper)graph to, so - AST generation reduces to the graph transformation. This seems the path to follow, isn't it?

There are some technical questions as well - are there tools that accept Java AST (in some form) and that generate Java source code? Can such AST-2-code tools be generated from the formal grammar of the programming language (https://docs.oracle.com/javase/specs/jls/se7/html/jls-3.html is example of the specification in the free, readable form)?

So - the question is - what is the best practice of code generation in the computer science academic project?

It highly depends on what is the domain you are working on, i.e. why do you need to generate Java Source code anyway?.

Can you explain better what knowledge do you have stored in your knowledge base?.

The most "formal" method I can think of is by using the Java grammar and generate and abstract syntax tree as you mentioned. But it may or may not be appropriate, it depends on what are the task you want to solve.

If you want to use the grammar approach you may want to check antlr, I've used it to compare AST in plagiarism detection. Here is a repository with the grammars of many languages, including Java: https://github.com/antlr/grammars-v4


Constructing a random Hamiltonian Cycle (Secret Santa) I was programming a little Secret Santa tool for my extended family's gift exchange.  We had a few constraints:

No recipients within the immediate family
Nobody should get who they got last year
The whole thing should be a cycle (Sandy gives to George, George to Tom, Tom to Susan, Susan back to Sandy)

So at this point, I think what I'm looking at is a directed graph, and I want to find a random Eulerian Hamiltonian Cycle.

Naively, I would say:

Start with a random vertex
Randomly choose a neighbour that hasn't been hit yet
Recurse until you reach a cycle (solution) or find a node with no neighbours (backtrack and choose a different random neighbour)

But this doesn't give all permutations equal weight.  Flipping a coin to choose the first neighbour could greatly limit subsequent possibilities, like in the graph below:

A -> [B, C]
B -> [C, D, E]
C -> [A, D, E]
D -> [A, B, E]
E -> [A, B]

If in the example above I start with A, I could choose B or C at 50% probability each.

If I choose B, the only cycle is 1) A->B->C->D->E->A
If I choose C, there are multiple paths: 2) A->C->D->B->E->A, 3) A->C->E->B->D->A

So with my naive approach, I would choose cycle 1 50% of the time, and 2 and 3 25% of the time each.

The route I ended up taking this year was to shuffle all of the vertices, and then check if it was in fact an admissable cycle.  But this gets less efficient as there are more constraints.

Is there an efficient way to generate a random Hamiltonian Cycle where each cycle has equal probability?

Edit:

By "efficient" I mean more efficient in runtime and/or space than generating the set of every Hamiltonian Cycle, and then choosing one at random.

I'm not sure what you mean by an efficient algorithm, but the problem of finding any Hamiltonian path is NP-complete, which means that it is very unlikely that a polynomial time algorithm exists for your problem.

If the number of people $n$ is small, say less than 10, then it is feasible to solve the problem by brute force. Generate all $n!$ permutations of the people. Remove all permutations from the list that do not form a Hamiltonian cycle and do not satisfy your additional constraints. The time and space complexity is $O(n! n)$. Then pick a random permutation from the list.


Regular expression for binary words with few zeros What is the regular expression for the set of binary strings with the property that

every $0$ is followed by exactly $m$ times $1$ and
every $0$ is preceded by at least $n$ times $1$?

$m$ and $n$ are integers.

@SamM's answer isn't completely right. Yes, it is $(01^m)^*$ for "each zero is followed by exactly $m$ ones", but this can't just be combined with "at least $n$ ones before". And a string of only ones complies always. So consider the ones between two zeroes:

If $m < n$, you can't comply with both conditions, so the language is just $1^n 1^* 0 1^m \mid 1^*$
If $m \ge n$, the only way to comply in between zeroes is to have $m$ ones there, so the language is $1^n 1^* (0 1^m)^+ \mid 1^*$


PRNG for a gaussian distribution? I need suggestions for algorithm for Pseudo random number generators that will produce a near gaussian distribution (bell curve) for automatically generating test data.  I know that PRNG produce recurring 'patterns, but google has revealed none that expressively produce gaussian distributions.  Do you have an recommendations ideally I'd like several suggestions to produce multiple different test datasets usable for automated testing.

You can generate any distribution by using a standard PRNG to choose $X$ uniformly from the interval $[0,1]$ and then returning $F^{-1}(X)$, where $F$ is the cumulative distribution function of the distribution you're interested in.

For the Gaussian distribution, though, it's usually better to use Box–Muller or ziggurat.


Why does the copycat strategy work for two parallel chess games? I'm currently looking into computability logic.
Japaridze explain that a game !P v P like !Chess v Chess is always winnable thanks to the copycat strategy (http://www.csc.villanova.edu/~japaridz/CL/3.html#copycat). However, what guarantees that the environment will play the same moves? One game could be e4 e5, but the other one e4 Nf6, and then the machine won't know what to do, right?

I'm probably not getting something, but I don't know what. Could someone help me?

Thanks.

The setting in the link you gave (where is it referred to as $chess\lor \neg chess$) is that the player is playing on two boards with different colors, and has to win in at least one.

In that case you can win by mimicking your opponent as follows. Let $b_{\text{white}},b_{\text{black}}$ be the boards on which you play white/black correspondingly. Whenever the opponent makes a move $x$ on $b_{\text{black}}$, you play $x$ on $b_{\text{white}}$, similarly when your opponent makes a move $x$ on $b_{white}$ your play $x$ on $b_{black}$. The result is that you are playing the same position on both boards, only with different colors.