If $R(x,y)$ is a recursive relation, then $\exists y\leq 2$ such that $R(x,y)$ is recursive The theorem says: If $R(x,y)$ is a recursive relation, then  there exists $y\leq2$ such that $R(x,y)$ is recursive.

Here is my attempt of proof:

Since $R(x,y)$ is recursive, we can construct a partial recursive function $f:\mathbb{N}^2\rightarrow\mathbb{N}$ be such that $f(x,y)=1$ if $(x,y)\in R$ and $f(x,y)=0$ if $(x,y)\notin R$.

Let $y=2$. Then either $(x,y)\in R$ or $(x,y)\notin R$. So we can just construct a partial recursive function $f'$ that fixes $y=2$ and takes an input $x\in\mathbb{N}$ and runs $f$ on $(x,2)$.

Is this enough? Can I generalize this for any values of $y$ or does this only apply for when $y\leq 2$?

Fixing $y$ in $R(x,y)$ results in a special case of the problem "whether $\langle x,y \rangle \in R$", and hence the latter should be no more harder than the general problem of deciding if $\langle x,y \rangle \in R$. So, intuitively if $R(x,y)$ is a recursive relation then $R(x,y_0)$ should also be recursive for some fixed $y_0$.

Formally, recall that a relation $R(x,y)$ is recursive if its characteristic function

$$ c_R(x,y) =  \begin{cases}
      1  & \text{ if } \langle x,y \rangle \in R \\
      0 & \text{ if } \langle x,y \rangle \notin R
\end{cases}
$$
is recursive.

Now assume that $R(x,y)$ is recursive. Then $c_R(x,y)$ is also recursive. Let $M(x,y)$ be a TM computing $c_R(x,y)$. For a fixed $y_0$ our new TM $M'(x)$ will take $x$, call $M(x, y_0)$ and return its value. Since $M(x,y)$ computes a recursive function (always returns $0$ or $1$), $M'(x)$ also computes a recursive function, namely $c_R(x,y_0)$. Thus $R(x,y_0)$ is recursive.


How do I find the intersection of subgraphs in a directed acyclic graph efficiently? I have a directory structure in which each directory can have multiple parents (IOW, a cd .. is ambiguous).  AFAICS this means this is equivalent to a directed acyclic graph.

Now, a set of directories (aka vertices) is given.  I need to know all directories which are below all of those given directories.  Thus, I need the intersection of subgraphs.

In my case, getting the set of sub-directories is a rather costly operation.  However, I can do it in parallel, i.e. I can do ls on multiple directories at the same time.

While one can easily think of a brute-force algorithm to do that (collect all vertices in sets, find the intersection of the sets) I wonder whether these is a more efficient algorithm.

The more efficient algorithm you're looking for is breadth/depth-first search.


Print to video permutations You want to print vectors with n elements, where:

the first element can have the values: e1.1, e1.2, e1.2;
the second element can assume the values: e2.1, e2.2, e2.3;
...;
...;
the nth element can assume the values: en.1, en.2, en.3.

I should print all possible vectors; eg:

{e1.1, e2.1, en.1 ...};

{e1.2, e2.1, en.1 ...};

etc. etc.

Someone could indicate an algorithm making use of while/for loop to print these vectors?

Thanks so much!

The idea is to think of your output as representing a number in a mixed base. The $i$th digit has base $b_i$, where $b_i$ is the number of options for the $i$th element. You can then print all possible vectors essentially by implementing a counter. I'll let you work out the details.


Simplification of regular expression and conversion into finite automata This is a beginners question. I and reading the book "Introduction to Computer Theory" by Daniel Cohen. But I end up with confusion regarding simplification of regular expressions and finite automata. I want to create an FA for the regular expression

$\qquad \displaystyle (a+b)^* (ab+ba)^+a^+\;.$

My first question is that how we can simplify this expression? Can we we write the middle part as $(ab+ba)(ab+ba)^*$? will this simplify the expression?

My second question is whether the automaton given below is equivalent to this regular expression? If not, what is the mistake?

This is not a homework but i want to learn this basic example. And please bear me as a beginner.

At the point of writing, your NFA is still a bit off. One version of a correct answer looks like this:

So this NFA is design in an ad hoc manner, but there's still some basic organisation to it. You can see that there's three basic bits, the $a,b$ loop on the start state, a forced $ab|ba$, followed by two 2-step loops, then a forced $a$ to the final state, with an $a$ loop. The first loop takes care of the $(a+b)^{\ast}$, the next little clump does the $(ab+ba)^{+}$, then the tail end does the $a^{+}$.

The key thing to practice when doing things this way is breaking the RE down into a sequence of smaller REs, that you then stick together. This is essentially a 'casual' version of the systematic method.

The systematic way is simple, but a bit fiddly. It's a relatively long explanation as to how to do it systematically, and as you haven't reached that bit in your reading yet, I'll refrain from working through the details here, however just as a quick reference, this explanation is pretty thorough and reasonably well explained.


A* to find the longest path in a directed cyclic graph I have written an A* algorithm to find the shortest path through a directed cyclic graph.  I am trying to modify it to find the longest path through the same graph.

My attempt was to write it so that all I change is [1] the weights per edge (making them negative instead of positive) and [2] the heuristic function.

I seem to be having trouble getting it to do this. It is pretty good at finding the longest path sometimes, but it is not guaranteed.

It seems that the problem lies with [2] the heuristic -- for shortest path an L2 norm is a good optimistic way to get it to head towards the goal, but for longest path I want the heuristic to point it at paths that are further from the goal to continue to increase total length.

If I set the heuristic to return 0 so that it's a Dijkstra's search, it's less predictable as there's no incentive to search from nodes further away (using [1] negative weights per edge).

I think if I keep the weights positive and try to maximize the score instead of minimize it may work, but I was attempting to do this without changing the algorithm, only the edge weights and the heurstic.

I have found similar posts on stackExchange but they don't answer my specific questions:

Q1) Can this be done with A*

Q2) Is setting the weights negative the right thing to do

Q3) Is the only way to do this is to set the heuristic to zero and keep the weights positive and try to maximize the score instead of minimize it?

First of all, bear in mind that the Longest Path Problem (LPP) is a NP-complete problem whereas finding the Shortest Path Problem (SPP) is a problem known to be in P. The proof for the NP-completeness of LPP is trivial and consists of a reduction from the Hamiltonian Circuit (HC) problem which is already known to be NP-complete.

In other words, if you could find a simple way (in the sense of the modifications taking only polynomial time) to modify A* to solve the LPP problem you would actually make a nice discovery! :)

This is not to say that A* can not be used, but it should be expected to take longer. I recently co-authored a paper about the "Target Value Search Problem" with other two people. This problem is stated as follows:

Given a graph $G(V,E)$ and a natural number $T$ find the path between the vertices $s, t\in V$ whose cost (or length in case of unary costs) is as close as possible to the given target value $T$.

Obviously, if $T=+\infty$ then you are seeking the longest path between any arbitrary pair of vertices, $s, t$. If, in addition, $s=t$ then you are looking for the longest path that joins both vertices. You can verify in $O(1)$ whether the length equals the number of vertices. If so, you found a Hamiltonian path.

Regarding your questions:

Q1: Can this be done with $A^*$? Certainly yes (indeed, we modified A* to get T*, our implementation of the Target Value Search problem that can be used to solve this variant) but you should not expect for it to be as fast as when solving SPP. As a matter of fact, we provided a simple modification of A$^*$ that can be used to solve the LPP as well (and it is certainly complete but terribly inefficient)
Q2: Is setting the weights negative the right thing to do? Well, the real problem is that you need a heuristic function that returns an upper bound on the path to the goal $t$ instead of a lower bound (as when solving the SPP) and these sort of heuristics seem particularly hard to derive (how would you do it? there is no concept such as "relaxation" here, maybe you should constraint the problem further to derive a heuristic)
Q3: Is the only way to do this is to set the heuristic to zero and keep the weights positive and try to maximize the score instead of minimize it? Well, you can do it but that is just a brute-force approach. Note that this approach forces you to consider all paths. Even if you find a path which seems to be too large you are still forced to expand other nodes in OPEN until you CLOSE them all. In the absence of a heuristic that is all you can do. This is, indeed, what our variant of A* for the Target Value Search problem does if $T=+\infty$ ---however $T^*$ is more efficient even to solve LPP.

Hope this helps,


Why don't most websites I visit seem to use TLS with Ephemeral Diffie-Hellman? When I click "view certificate," under Public Key Algorithm it usually says "RSA Encryption" or "Elliptic Curve Public Key." I assume this is the algorithm used to agree on a premaster secret (symmetric keys) between the client and server, or steps 4-6 in the image below. Why not use Diffie-Hellman then? Doesn't ephemeral Diffie-Hellman provide forward secrecy?

TLS handshake

The typical process to establish a secure channel uses asymmetric cryptography for two purposes: to allow the parties to authenticate each other, and to establish a shared symmetric key (in TLS, that's the premaster secret). At least one of the sides needs to authenticate the other, otherwise the two sides could each establish a secure channel with a man-in-the-middle. The shared symmetric key must be established in such a way that a man-in-the-middle cannot find it out. There are many different ways to do this, and I'll focus on ways that are actually used in TLS.

Most TLS connections do authentication and shared key establishment independently. This is the only way in TLS 1.3 (except with pre-shared symmetric keys), and it's the most common way in previous TLS versions.

To establish a shared key, each side creates an ephemeral Diffie-Hellman key (usually elliptic-curve DH, but it can also be finite-field DH) and sends the public key to the other side. Each sides receives the other side's public key, calculates the shared secret, and discards the ephemeral DH key. Thanks to the security properties of Diffie-Hellman, it's impossible to reconstruct the shared secret by observing wire traffic: an adversary would also need to have one of the private DH keys. Hence this method guarantees perfect forward secrecy.

For authentication, the client authenticates the server. (The server can optionally authenticate the client, but having one side do authentication is enough to prevent active man-in-the-middle attacks.) The way this works is that the server sends a digital signature (RSA, DSA or ECDSA) of the handshake, i.e. of the packets that both sides have either read or written so far, and the client verifies this signature. The client either already knows the server's public key (public key pinning or raw public keys, both rare settings), or far more commonly verifies a certificate chain from a root certificate authority trusted by the client to the server's public key.

The authentication process has no impact on the shared key establishment. That's why you don't find anything about Diffie-Hellman in the certificate information: it isn't involved in that part of the protocol. The algorithms mentioned in the server certificate are the one used to sign the handshake (subject public key algorithm) and the one used by the CA to sign the certificate (certificate signature algorithm).

By the way, “PKCS#1 v1.5 RSA Encryption” in X.509 certificates is called this for historical reasons, but it's actually a PKCS#1 v1.5 RSA signature.

TLS ≤1.2 also has cipher suites that use static Diffie-Hellman (also called non-ephemeral Diffie-Hellman). With these cipher suites, DH also provides the authentication part of the process. The server always uses the same DH key. The client verifies that the DH public key that it receives from the server is the one that it expects. If an adversary tries to impersonate the server and sends the legitimate server's public key, they won't be able to calculate the shared secret because they don't have the private key. If an adversary tries to impersonate the server and sends their own public key, the client will abort the connection because it sees a public key that is not the expected one. Static Diffie-Hellman does not provide forward secrecy, since obtaining the server's static private key is enough to decrypt all past recorded traffic.

Just like with signature-based cipher suites, the client doesn't actually need to know the server's public key in advance. The client can use a public key infrastructure to validate the server's public key: it checks that the server's public key comes in a certificate that has been signed by a (chain of) CA that the client trusts. An X.509 certificate can contain a signature of an (EC)DH public key. It's rarely done in practice, because it only has a marginal performance benefit, it's less secure (no forward secrecy), and there's a self-reinforcing loop that almost nobody does it (because there's no reason to) so almost nobody implements support for it (because there's no demand) so almost nobody does it (because there's no software support).


Classification when some classes are dependent I think my problem can easier be explained via an example: Assume we have a dataset containing the images of 10 different mammals, let's say lion, elephant, cat, ... and horse. We have a 20-class image classification task where we want to detect whether an image belongs to lion-male or lion-female or cat-male or cat-female or ... horse-male or horse-female. As you see, the classes can be simply clustered into 10 mammal classes, i.e., (some) classes are highly dependent.

This example is a kind of made up. Two strategies, imaginable to solve this problem is either we ignore this dependency and treat it as a 20-class classification task or use a hierarchical structure to first classify them into 10 class of mammals and then into male or female. The later however, ignores the fact that there might be (and in fact is) some shared properties in all males or in all females that can be used to discriminate them.

I was wondering if there is a methodological way to address this type of classification tasks. I'm looking for a keyword to google it.
Thanks

I'm afraid there is no exact answer to your question.
In the scenario you described above male and female mammals are very similar, similar enough that the average person wouldn't notice the difference.
In such a case, I would suggest going with the first option of classifying into 10 classes of mammals and then building 10 classifiers of male-female.

This of course isn't an answer that applies to all cases, it is strongly dependent on a few factors, mainly on the classification scenario at hand.
The size of the dataset is also a significant parameter.
Unfortunately I don't think there is a methodological way to address this issue, only experience can point you towards the best solution.


Is there an algorithm that provably exists although we don't know what it is? In mathematics, there are many existence proofs that are non-constructive, so we know that a certain object exists although we don't know how to find it.

I am looking for similar results in computer science. In particular: is there a problem that we can prove it is decidable without showing an algorithm for it? I.e. we know that it can be solved by an algorithm, but we don't know what the algorithm looks like?

The simplest case I know of an algorithm that exists, though it is not
known which algorithm, concerns finite state automata.

The quotient $L_1/L_2$ of a language $L_1$ by a language $L_2$ is
defined as $L_1/L_2=\{x \mid \exists y\in L_2 \text{ such that } xy\in L_1\}$.

It is easily proved that regular set are closed under quotient by an
arbitrary set.  In other words, if $L_1$ is regular and $L_2$ is arbitrary (not necessarily regular), then $L_1/L_2$ is regular, too.

The proof is quite simple. Let $M=(Q,\Sigma,\delta,q_0,F)$ be a FSA
accepting the regular set $R$, where $Q$ and $F$ are respectively the
set of states and the set of accepting states, and let $L$ be an
arbitrary language. Let $F'=\{q\in Q\mid \exists y\in L \;\;\delta(q,y)\in
F\}$ be the set of states from which a final state can be reached by
accepting a string from $L$.

The automaton $M'=(Q,\Sigma,\delta,q_0,F')$, which differs from $M$
only in its set $F'$ of final states recognizes precisely $R/L$.  (Or see  Hopcroft-Ullman 1979, page 62 for a proof of this fact.)

However, when the set $L$ is not decidable, there may be no algorithm
to decide which states have the property that defines $F'$. So, while
we know that the set $F'$ is a subset of $Q$, we have no algorithm to
determine which subset. Consequently, while we know that $R$ is
accepted by one of $2^{|Q|}$ possible FSA, we do not know which it is.
Though I must confess we know to a large extent what it looks like.

This is an example of what is sometimes called an almost constructive
proof, that is a proof that one of a finite number of answers is the
right one.

I suppose an extension of that could be a proof that one of an
enumerable set of answers is the right one. But I do not know any. Nor
do I know a purely non-constructive proof that some problem is
decidable, for example using only contradiction.


What does the 2 in a 2-approximation algorithm mean? Does the 2 in a 2-approximation algorithm mean the solution is within 2*OPT or OPT/2?

Typically, we use $\alpha < 1$ for maximization problems, and $\alpha > 1$ for minimization problems, where $\alpha$ is the approximation guarantee. So, a $2$-approximation algorithm returns a solution whose cost is at most twice the optimal. But as always, to be absolutely sure, go back to the definitions of the text you are reading (if a definition is not available, assume this).


Two dimensional 3 bit parity check Can someone explain how do we find these parity bit errors?

I'm assuming that your code works in the following way:

The input is an $n \times m$ bit matrix.
You add a parity bit to each row, chosen so that the parity of the new row is even.
You add a parity bit to each column, chosen so that the parity of the new column is even.
You end up with an $(n+1) \times (m+1)$ bit matrix in which the parity of each row and column is even.

Suppose now that between 1 and 3 errors occurred. There must be either a row or a column in which exactly 1 error occurred (I'll let you figure out why). This row or column will have odd parity, and so you will be able to detect that an error occurred.


Training a neural network by classifying its own output The usual way one trains a neural network is to give it some input and provide the correct classification.

But what about letting the neural network produce its own inputs, and then classifying those?

Imagine the following "algorithm".

Use a neural network to generate 2 images (random at the beginning)
Let the user pick which one is more "interesting"
Update the neural network based on the choice

Do you think that as a general principle this might make sense, i.e. there might be an approach that generates more "interesting" images over time? Has something similar been done until now? What approaches/papers/libraries might best help one achieve such a goal?

No, that doesn't seem likely to be a very useful direction.

Neural networks are a form of statistical machine learning.  The premise behind all statistical machine learning schemes -- including neural networks -- is that the instances in the training set need to come from the same distribution as the instances that you will apply the classifer to (i.e., the instances in the test set).

If you artificially generate instances via some arbitrary procedure, they might not come from the right distribution.  That will invalidate the core assumption behind statistical machine learning and may make the classifier perform poorly.

Your approach would only work if we knew that the neural network was able to generate images that come from the right distribution (i.e., the distribution on natural images that you'll want to classify).  But there's no reason to believe that will be the case.  In particular, I suspect it most likely won't be the case.

Or, to put it another way, your approach would only work if we had a way to characterize the probability distribution on natural images and sample from this distribution.  However, this appears to be as hard as building a classifier, or even harder.  So, there is no free lunch.

You might interested in the distinction between discriminative vs generative models.  Standard neural networks are discriminative models, and thus don't provide any (direct) way to generate images.  It is also possible to build generative models, which can generate images.  However, building a generative model is believed to be at least as hard as building a discriminative model, and probably even harder.  So, your proposal amounts to saying: "if I had a generative model, I could use that to build a training set to train a discriminative model".  But if building a generative model is likely even harder than building a discriminative model, so this doesn't seem to help much.  There's no free lunch.

Separately: You don't say how you plan to use a neural network to generate images.  Neural networks are a classifier, so they can classify an existing image, but not generate a new image.  You have to do something special to generate images from a neural network.


Turing Machine notation I'm a bit confused on some of the notation being used for turing machines in one of our exercises in class.

The question gives us a string $\alpha \in \{0,1\}$* and the function $\mathsf{int}(\alpha)$ that changes a binary number to its base 10 form. (example, $\mathsf{int}(00010) = \mathsf{int}(10) = 2$)

Now comes the tricky part:
Define the language $L ⊆ \{0, 1, \#\}*$  by:

$L = \{\alpha\#\beta | α, \beta ∈ \{0, 1\}$* and $|\beta| ≥ \mathsf{int}(\alpha) ≥ 1 $ and $\beta \{ \mathsf{int}(\alpha) \} = 1 **\}$.

This bolded section is confusing me, and it seems like there are different variations of T.M. notation as well...

Could someone give me a rough approximation of what this might mean?

Extra:
Examples for language $L$:
 $\#111 \notin L$
$00010\#11100 \in L$
$00011\#010111 \notin L$
$00011\#11 \notin L$
$1\#\#1 \notin L$

Thanks in advance.

The function $\mathsf{int}$ actually doesn't change a binary number to its base 10 form. Rather, it takes a string encoding some number $n$ in binary, and outputs $n$. When we write the output, we use decimal (base 10), but the output is just a number. It's us who use base 10.

The language $L$ consists of all strings $\alpha\#\beta$, where $\alpha,\beta \in \{0,1\}^*$, such that

$\alpha$ encodes (in binary) an integer $a$ in the range $1$ to $|\beta|$, where $|\beta|$ is the length of $\beta$.
The $a$th bit of $\beta$ is $1$.

It's difficult to say what the $a$th bit of $\beta$ is, since there are several possible conventions:

The "first" bit could be bit number $0$ or bit number $1$; in this case it seems like the first bit should be bit number $1$.
We could be counting bits from the left or from the right; the usual convention is from the left, though if you think as a string as encoding a number, it is more natural to count from the right.

Assuming we are counting bits from the left and starting with $1$, $L$ consists of strings $\alpha\#b_1b_2\cdots b_n$ where $\alpha$ encodes a number $a$ in the range $1 \leq a \leq n$ and $b_a = 1$. This interpretation also matches your examples.


Proof that uniform circuit families can efficiently simulate a Turing Machine Can someone explain (or provide a reference for) how to show that uniform circuit families can efficiently simulate Turing machines? I have only seen them discussed in terms of specific complexity classes (e.g., $\mathbf{P}$ or $\mathbf{NC}$). I would like to see how uniform circuit families is a strong enough model for universal, efficient computation.

Here is the basic idea. We'll take P as an example.

Given a Turing machine running in polynomial time, we construct, for each input length, a layered circuit in which each circuit represents the current configuration of the Turing machine:

For each cell, the contents of the cell.
For each cell, whether the head is there.
The current state of the machine.

The number of layers is the same as the polynomial upper bound on the running time, and the width of each layer (number of cells) is the maximum space used by the machine.

The initial layer is initialized directly from the input. Each other layer is constructed from the preceding layer (using the convention that once the machine halts, its configuration remains static). Finally, the output is extracted from the last layer. The construction is uniform, as the description hopefully makes clear.

This shows that you can convert Turing machines running in time $T(n)$ and space $S(n)$ to uniform circuits of size $O(T(n)S(n))$. This can likely be improved.


What are some problems in $\mathrm{P}$ with time complexity of high-degree polynomial? What are some problems that are in $\mathrm{P}$ but the best known algorithm has a high-degree polynomial ($\ge 3$) time complexity?

Concrete example: Thorup's $O(n^{120})$ time algorithm to recognize half-squares of planar bipartite graphs.

https://arxiv.org/abs/1804.05793

Parameterized problem: Some parameterized $NP$-complete problems have arbitrarily large polynomial time algorithms. Like, finding a $k$-clique in a graph can be solved by $\Theta(n^k)$ algorithm. And we do not know how to do much better. There might be some improvement but in general when the parameter increases the degree of the polynomial run-time bound increases also.

Computational geometry problems parameterized with the number of dimensions $d$ can be seen as a special case in this group.

Some other $NP$-complete problems (like Vertex Cover in the comment of kne below) have parameterized version with linear-time algorithm for each parameter value. So, it takes some careful investigations before naming a hard parameterized problems.


Polynomial Identity Testing Evaluating a polynomial on a circuit Say I have a polynomial over $Q$. Let it be given in the form of arithmetic circuit family ${C_n}$. The randomised poly time algorithm evaluates the polynomial at a random point. What if the number of bits required for the intermediate calculations is too high i.e How can we guarantee that the evaluation does not require more than polynomial bits (polynomial in the size of the circuit) ?

If you're working over $\mathbb{Z}/p\mathbb{Z}$, you don't have to do anything: the intermediate results can't get larger than $p$.

If you're working over $\mathbb{Z}$, the standard trick is to pick a random $k$-bit prime $p$ and then reduce everything modulo $p$, so you are effectively working over $\mathbb{Z}/p\mathbb{Z}$.  One can show that the probability of getting a wrong answer using this method is exponentially small in $k$ (using the prime number theorem).

If you're working over $\mathbb{Q}$, you can reduce this to working over $\mathbb{Z}$ by clearing all fractions.


Grammar in formal languages versus programming language theory Grammars seem to be used for different purposes.  In formal languages, they are used to describe sequences of symbols.  In programming language theory, they are used to describe objects in a term algebra (possibly enriched with some implicit, extra structure such as variable scoping rules).  My question is, are these two kinds of grammars the same notation reused for unrelated purposes, or are they describing the same things?  If they are unrelated, then do we have nomenclature to distinguish them?

For instance, the grammar

e ::= 1 | e e

could be describing a set of strings that includes "1", "1 1", and "1 1 1", or it could be describing a set of terms that includes "1", "1 1", "(1 1) 1", and "1 (1 1)".

Programming language theory usually does not care about parsing: it does not address this problem. So when you have this grammar in programming language theory:

e ::= 1 | e e

it does mean the same thing as in formal language theory but programming language theory really only talks about the generated syntax trees. However it is much better to have a non-ambiguous grammar. For example in the lambda-calculus, the grammar is written like this:

$$M ::= x ∣ λx.M ∣ M M$$

and things like $L M N$ have several meanings as you pointed out. Usually the author/context makes it non-ambiguous like this: he says the application case is left-associative, authorizes parentheses, or sometimes changes $MM$ into $(MM)$ and says "we omit parentheses when unnecessary" or several other ways.

In conclusion it may generates the same string for different trees but programming language theory only applies on the latter.


Is matrix multiplication cheaper than inverse? In wiki, it is shown that the time complexity of matrix multiplication and matrix inverse is similar. But people always to argue it is easier to do matrix multiplication rather than inverse. Is this claim true? Maybe we need to consider various computation platform, CPU or GPU.

Matrix multiplication and matrix inverse have the same asymptotic running time. If we denote the running time of multiplying two $n \times n$ matrices by $T_1(n)$, and that of inverting an $n \times n$ matrix by $T_2(n)$, then this means that there exist constants $A,B$ such that
$$ T_1(n) \leq AT_2(n) \\ T_2(n) \leq BT_1(n). $$
However, the constants $A,B$ can be significant. (Also, numerical stability might be an issue.)

Checking your claim is, however, very easy in practice. Choose your favorite matrix library (e.g. LAPACK), and you can determine empirically $T_1(n),T_2(n)$ for the values of $n$ that you are interested in, on the hardware platform that you are interested in.


High-level description of aTM If I have language:

L = {x | x = n^2 for some integer n}

How can I give a high-level description of Turning Machine  that decides on the language?

Perhaps the simplest way is to implement the following algorithm:

Initialize $y$ to 0
Initialize $n$ to 0
Compare $y$ to $x$; if $y = x$, accept; if $y > x$, reject; otherwise, continue
Add $2n+1$ to $y$
Increment $n$ by 1
Jump to 3

The idea is that $y = n^2$ always. This is ensured using the formula $(n+1)^2 = n^2 + (2n+1)$.


What exactly is a logic? An apology might be in due for asking another question about prerequisites, but I was confused about the starting points.
I have come across various terms such as "Modal Logic", "Temporal logic", "First -order Logic", "Second order Logic" and "Higher order logic".

What exactly does "Logic" mean in this context? How do we rigorously define the word "Logic"?

After going through the beginning pages of few books I can roughly conclude that
a "Logic is a way to decide what follows from what and is significant in designing programming languages as it dictates and facilitates designing of programs to automatically reason and understand programs.
I want to understand about the second point in a bit elaborated manner.

Now coming to these logics.

Are all these logics, "temporal Logic", "Modal Logic", "First order Logic", "Higher order Logic" independent of each other or we need to understand few of these logic to understand a few others in this group? In a nutshell, what will be the prerequisites for them? (It will be great if I can get suggestions on some materials also.)

P.S : Thanks a ton for your kindness

Fundamentally, a logic consists of two things.

Syntax is a set of rules that determine what is and is not a formula.
Semantics is a set of rules that determine what formulae are "true" and what are "false". To a model theorist, this is expressed by relating formulas to the mathematical structures that they're true in; to a proof theorist, truth corresponds to provability from a chosen set of axioms with a chosen set of proof rules (techniques).

The difference between different logics is, most simply, in the choice of syntax and semantics. Most logics are extensions of propositional logic or first-order logic. In a sense, you can see these extensions as "adding more features" to the logic. For example, temporal logics deal with truths that can vary over time.

In general, these features could be expressed in a simpler logic, at the cost of having to write longer formulas. For example, the temporal concept "$\varphi$ is true from this point for eternity" can be expressed in a first-order way by adding a time parameter to all your propositions and saying "For all times $t$, if $t$ is greater than or equal to the current time, then $\varphi$ is true at time $t$."  In a sense, you can think of these logics as adding libraries to a basic programming language so you can say things more easily.

Since pretty much all logics are based on propositional and first-order logic, I'd recommend learning about those first.


Is $L = \{ a^ib^j : 0 < j < i < 2j\}$ context free? How can it be shown? Is $L = \{ a^ib^j : 0 < j < i < 2j\}$ context free?
If so, can there be a pushdown automaton described for it?
If not, does the pumping lemma apply?

What's the smallest possible j, and which i goes with it (to allow j < i < 2j). So that's the minimum number of a's and b'. Beyond that, you need one or two a's for every additional b.
That should be enough to find a grammar.


Relationship between height and depth of a binary tree The wikipedia says that the number of nodes n in a full binary tree, is at least $n=2^h-1$ and at most $n=2^{h+1}-1$, where h is the height of the tree.

The following binary tree is full according to the wikipedia definition (every node has 0 or 2 children), n = 11, h = 4 but n is not greater than $2^4 - 1 = 15$.

Am I missing something?

                        .
                       /  \
                      a    .
                          / \
                         b   .
                            / \
                           .   .
                          / \ / \
                         c  d e  f

You're not missing anything: it's a typo, which I've fixed. The page gives two separate definitions of "full binary tree" (a recursive one and the one you quote) and both of them include the following trees, which have even fewer nodes than yours ($2n-1$, to be precise):

  o
 / \
o   o
   / \
  o   .
       .
        .
         \
          o
         / \
        o   o


Having trouble with turing machine over language $L = \{0^n 1^m 0^n 1^m \mid m,n \geq 0\}$ I am having trouble giving the description of a Turing machine that goes for
$L = \{0^n 1^m 0^n 1^m \mid m,n \geq 0\}$. What I have so far is:

If we start with a blank, the string is empty and it should accept, if not, start reading $0$s and I thought marking the $0$s with $X$ and the $1$s with $Y$ would be OK. After we reach a $1$, start marking $0$. Now comes the part I'm worried about, what do I do when the 2nd round of $0$s comes? How will I check if there are equal amounts of $0$s and $1$s?

Thanks in advance

What I tend to do when it comes to counting with a tape is to go back and forth on the tape, marking the relevant portions of the tape as I'm reading new input.

Example
To recognize the language $0^n1^n$ with a Turing machine (not that you'd need the power of a Turing machine, but for illustrative purposes), you can read the first $n$ $0$s, and then when you read the first $1$, mark that $1$ (write $1'$ in that cell), then go back all the way to the first $0$ and mark that, too (writing $0'$). Then go back to the next $1$ (the one to the right of the cell with the $1'$) and write $1'$, go back to the next $0$ that is not marked, and mark that. When you run out of $1$s to read/mark, you have to go back and make sure that all $0$s have been marked. If this is the case, accept the language. If not, or if any other deviation has occurred during the operation of the machine (e.g. encountered some input symbol other than a $0$ or a $1$, read and marked a $1$ but there were no $0$s left to mark; these are treated like undefined transitions), you must reject the language.

Say you are given the string $0000111$ as input.
After counting two $1$s:

  $0' 0' 0 \,0 \,1' 1' 1\,$

After counting three $1$s:

  $0' 0' 0'0 \,1' 1' 1'$

Now there is one $0$ left that is not marked; reject the language.

For your language, it is simple (but, like the above, pretty tedious) to use this strategy to recognize the language. The variation comes in keeping track of what parts of the previous input to mark, and how to get back to the next input cell to read.

Aside: This can be generalized to multiplication, for example to recognizing the language $0^n1^m0^{n \cdot m}$.


Programming languages for genetic engineering I'm interested in getting a Ph.D. and would love to work on a project such the GEC project at Microsoft Research, which studies the application of programming languages for synthetic biology and genetic engineering. What groups are doing work like this in a university setting?

I choose to reply in an answer rather than a comment because I think
that is actually the proper answer to your question (and it is too
long for a comment anyway).

Style

If you intend to do research and write papers for an audience, then
you should learn to be easy to read. Any improvement costs only once
to you, and saves time and energy to each one of your readers. That
includes giving web references that  can be clicked, rather than
having to be cut and pasted in a browser window. That also include
briefly telling your readers what the reference is about, so that
they do not have to jump into unknown territory. (this is a comment on
the original version of your question, before the friendly editing of
David Richerby).

The same is actually true for programs. It is not enough to write a
program that solves the problem, you should also make sure that it is
easy to understand and to use, so as to spare aggravation to your
users.
Substance

Getting a Ph.D entails doing a fair amount of research. The very
first step is to find litterature that is relevant to your research
topic. Usually, if you choose the topic, you are supposed to have
some knowledge of it. In your case, you know of a project that is
relevant.  So that gives you names, keywords, and topics to search for on the
web. Then some reading of that should give you a better
understanding, increase your competence and allow you to search for
more ... and find research groups that do that kind of work by
looking at the authors of papers. Their affiliation is usually given,
and many have a web site.

Doing this yourself will increase you general competence at doing
research, and also increase your knowledge of the field. It is in no
way wasted work. Doing if for you is not doing you a service. You
would not think of getting someone on the net to write your
dissertation for you. Of course, it does make sense to discuss issues
and ask questions, but usually after doing what work you can, so as
to spare the time of colleagues ... they do not have so much available.

But if you cannot do it yourself, you probably do not have the
maturity to do research and you should rather consider another
academic path, or professional path.


Maximizing the boolean combination of given real numbers Let $x_1, x_2, \dots, x_n \in \mathbb R$ and $b_1, b_2, \dots, b_n \in \{0,1\}$. I want to know which of all the possible boolean combinations is maximal. For example, if $x_1 = 2$ and $x_2 = -2$,

$$\max \sum_i b_i x_i = 2 \implies b_1 = 1, b_2 = 0$$

I can see that a brute force algorithm will have a running time complexity of $O(2^n)$. My question is whether there is an efficient algorithm for this or, at least, an approximation algorithm.

Maybe there is something I do not understand in your question, but the way it is formulated it seems that the set of solutions is:

set $b_i=1$ if $x_i > 0$
set $b_i=0$ if $x_i < 0$
all others $b_i$ can either be zero or one

It is clear that any other assignment will give you a lower value (either by adding a positive value or not adding a positive one). If $|\{i:x_i=0\}|=K$, then you have $2^K$ solutions. This can be settled in $O(n)$ by a simple linear scanning of $x_i$ values (even less if they are ordered).


Parallel shortest path in directed acyclic graphs Finding the shortest path in a DAG is extremely easy:

See the example here http://www.utdallas.edu/~sizheng/CS4349.d/l-notes.d/L17.pdf

However, I cannot find a way of parallelising this code. Is there a way of doing that?

In complexity theory, the notion of P-complete (wiki) denotes the problems that are (widely believed) difficult to parallelize effectively. (Note: I am not good at this area. Please correct me if I am wrong.)

One typical P-complete problem is

  Circuit Value Problem (CVP): Given a circuit, the inputs to the circuit, and one gate in the circuit, calculate the output of that gate.

The "shortest path in DAG" problem is similar to CVP. I think it is not hard for you to find a reduction in the literature with, for example, the paper A Compendium of Problems Complete for P as a starting point.

A positive side: Of course you can layer the nodes in DAG and parallel the computation layer by layer to some extent.


Is this decidable language a subset of this undecidable language? I think I understand the theoretical definition of decidable and undecidable languages but I am struggling with their examples.

A(DFA) = {(M, w): M is a deterministic finite automaton that accepts the string w}

A(TM) = {(M, w): M is a turing machine that accepts the string w}

I know that A(DFA) is decidable and A(TM) is not. But, is A(DFA) a subset of A(TM)?

No, A(DFA) is not necessarily a subset of A(TM). When you write "(M, w)" you actually refer to some encoding of M in some alphabet (usually {0,1}). These encodings of DFAs and TMs can be very different.

For a simple example: Let $A_1, A_2, \dots$ be an enumeration of all DFAs, and let $M_1, M_2, \dots$ be an enumeration of all TMs. You could say that you encode $A_i$ as the word $0 \text{bin}(i)$ and $M_i$ as $1 \text{bin}(i)$, where $\text{bin}(i)$ is the binary representation of the number $i$. Then the two langauges you presented are disjunct.

As it seems that this is part of your question: Being a subset and being computationally easier do not relate. Take the set $\Sigma^*$ of all possible words. It is easily decidable (even by a DFA) but every language, even undecidable ones, are subsets of it.


How to express complexity of two functions considering it is the same in big O notation I have two functions. a and b.
Both have linear complexity O(n).
fcn a (items)
    loop items -> item
        ...

fcn b (items)
    loop items -> item
        ...

    loop items -> item
        ...

    loop items -> item
        ...

Though b obviously takes 3 times longer to run than a for the same input.
Is there any other notion / technical way to express the difference?
Or is it normal to say "it takes 3 times longer but still O(n) in time so w.e, let's move on"

Big O notation is oblivious to this difference. This is one of its downsides.
One reason we use big O notation in the first place is that the exact running time depends on the system used to run the algorithms. It is meaningless to say that a given algorithm takes X instructions, since X depends on the CPU, the compiler, and so on. However, in some cases we can find a proxy for the running time which is meaningful to look at.
The prototypical example is the number of comparisons in a comparison-based sorting algorithm. In many cases, number of comparisons is a good proxy for the overall running time, and this is a "dimensionless" quantity which is meaningful to compare across algorithms.
Another option is to implement your algorithms as efficiently as possible, and then compare their running time empirically. In a practical paper, this is a very reasonable thing to do.
In your particular case, you can just say that algorithm B invokes algorithm A three times, and consequently is three times slower. This is not reflected in big O notation, but is quite precise and meaningful.


Conditions under which the 3-partition problem is not strongly NP-complete? I'm a bit confused about the 3-partition problem. More specifically I'm confused about this from the Wikipedia article:

  Let B denote the (desired) sum of each subset Si, or equivalently, let the total sum of the numbers in S be m B. The 3-partition problem remains strongly NP-complete when every integer in S is strictly between B/4 and B/2.

Does this mean that if the multiset contains elements that fall outside the range B/4-B/2 the problem is no longer strongly NP-complete and admits heuristics or other optimizations? Am I interpreting that right?

Also am I correct in assuming that this problem (at least when it is strongly NP-complete) pretty much requires an exhaustive search (unless P=NP)?

I've sifted through some papers but haven't been able to figure this out.

No. Intuitively, the problem gets harder if we take out the restrictions on the input values, since the restricted instances are a subset of the instances of the general problem. However, the article says, even if you introduce this restriction the problem does not get easier and it is still strongly NP-complete.

On the other hand, exhaustive search is not always the best approach for hard problems. Parameterized algorithm introduce methods usually to restrict the area where the exhaustive search must happen. Randomized algorithm offer methods where a greedy algorithm or a heuristic looking among bounded number of solutions gives an optimal answer with some probability. repeating the method enough number of times yield an answer with high probability. So no it does not mean that an exponential exhaustive method on the whole input is the best we can do. It only means unless $P = NP$, no polynomial time deterministic non-randomized algorithm can be designed for this problem.


Can Tree Transducers Self-Interpret? Is it possible for MSO graph/tree transducers to reflect themselves, namely to create an interpreter of tree/graph transducers using tree/graph transducers? If yes, I'll be happy for some design guidelines.

Not in any straightforward way, because a tree transducer only accepts a single input, while an interpreter needs two inputs.

An interpreter needs two inputs: a transducer $R$ and a tree $T$, and would output the $R(T)$.  But a tree transducer can only accept one input.

Consequently, there appears to be no way to build such an interpreter (unless you accept some crazy way of pre-processing the inputs to bring them into a form that they can be provided to a tree transducer -- but it's hard to see how to define that in a way that rules out trivial solutions where it's the pre-processor that's actually doing all the interpreting).


How does coarser lock granularity cause an decrease in time required to acquire and release locks? I understand the principles required to program locks and I have run into the following problem:

In my Operating Systems course, as well as on Wikipedia, one of the notions associated with lock overhead is the time required to acquire and release locks. And it is also implied that coarser granularity leads to less overhead (I agree it causes less memory to be allocated and less time for initializing locks), but I do not agree that it causes less time to be spent acquiring/releasing locks.

In my view, the number of times locks are being acquired/released is dependent only on the number of times threads are trying to enter a critical section and therefore, it should be the same regardless of the granularity chosen for the locks. My lecturer said in the lecture that because there are more locks, therefore the time spent to acquire/release is higher in the case of finer granularity.

It would be great if someone could explain why does coarser granularity lead to a decrease in time required to acquire/release locks compared to finer granularity.

Fine-grained locks need to be acquired and released more often.  Coarse-grained locks don't need to be acquired or released as often.  Therefore, you're both right.

For instance, suppose you're about to do a big, long operation.  With a coarse-grained lock, you'd grab the lock before beginning the operation, hold it throughout, and release it at the end -- a total of one acquisition & release.  With a fine-grained lock, you might grab and release the lock at multiple times, at each sub-step.  Also, you might grab and release multiple locks, because the operation touches multiple resources, each with its own lock.

That said, coarse-grained locks can cause other problems.  They can cause deadlock, or they can cause one thread to be stalled waiting for the other thread to perform a long operation.  Therefore, they can limit your ability to take advantage of parallelism.

Ultimately, you usually need to balance these competing considerations.


Sorting using comparison is superlinear or sublinear? My question is, is comparison based sorting problem, in time complexity, a superlinear problem or a sublinear problem?

In more details: we know that sorting using comparison have the achievable lower bound of $O(n\ln n)$ where $n$ is the number of items to be sorted. Now the question of superlinear and sublinear is dependent on what is considered the size of the input, and I am not sure if $n$ is the size here. We have 2 cases:

(a) The input is a full acyclic graph describing the comparison relation. In this case the input size is actually $O(n^{2})$ and the problem is sublinear.

(b) The input is just the item to be sorted, plus the description of a Turing machine that will perform the comparison. Then the input size is $O(n)$ and the problem is superlinear.

Can anyone clarify what is the consensus on this? Some people tell me that sorting with comparison is an example of a problem with a nontrivial lower bound (ie. the lower bound stronger than just by looking at how much information do the algorithm need to know). However, it seemed to me that in fact this is one example where figure out how much information you need is the crux of the problem, and not any combinatorial nature of Turing machine. Thanks.

In complexity theory, the input size is by convention (or definition, really) the number of cells the input takes up on a Turing machine tape.

The famous $\Omega(n \log n)$ bound does not adhere to this convention, though; $n$ is not input size but number of elements here. The input is (in general) longer than that since every element will have to be encoded on the tape in some way.

Generally, in sorting we consider the input to be the array (or list) of elements to be sorted. We don't pass the comparison matrix.

But you touch on an important point: complexity statements depend on machine model and input encoding. We usually default to TMs or RAMs depending on context and "reasonable" (i.e. not wasteful) encodings, but if there is any chance for ambiguity you need to state all the parameters.

For instance, the input size of sorting is $n$ is you consider RAMs with unit cost measure!


Access control matrices: who are the subjects: users or processes? I'm studying the basics of security in computers. The doubt I have is that the access control matrix is presented as a matrix whose rows are the subjects and the columns are the objects. Also subjects are defined both in Windows and Unix (and Multics for that matter) as processes, threads, not users, but processes.

My question is why then, when I check the Windows ACLs, I get the permissions that each user has instead of the permissions that each process under each user has.

It seems to me that more than a matrix a cube is needed, because the subject permissions, i.e. the processes permissions, are bound to the identity of the user logged in.

From what I've read it seems ambiguous: in some cases subjects are processes, and in others subjects are user accounts. Which one is the correct form?

Short answer: both.

My answer is based on knowledge of Unix, but as far as I know the same principle applies to Multics and Windows.

Runtime permission checks are performed by the kernel in system calls (such as the call to open a file). They are based on a matrix where the subjects are processes — the kernel determines the content of the cell for the calling process and for the object under concern (e.g. the file whose opening is requested).

The row for each process in that matrix is computed from data that is stored in a kernel data structure for that process. It is inherited from parent process to child process, all the way from login time. At login time, this data is initialized from the user database; it includes the information of which user the process is running as.

A file's access control list is stored on disk (if the file is a disk file). It could not reference processes: these have a too short lifetime — on a reboot, not information about processes would be meaningful. In access control lists stored on the filesystem, the subjects are users (and groups).

You can draw a cube, but that cube doesn't correspond to anything tangible in the operating system design. The user/object matrix corresponds to file ACLs, and the process/object matrix corresponds to runtime checks in the kernel.


Standard problem sets for metaheuristics I'm wanting to dabble with metaheuristics and am interested to know what the "hello world" problem sets are.

In other words, what are the common problems (e.g Traveling Salesman, Vehicle Routing Problem, Maze Solving) to test various algorithms against in order to compare algorithm design?

are these any good to you?

Binary Welded Tree (BWT). To ﬁnd a labeled node in a
graph

BooleanFormula(BF). To evaluate a NAND formula

ClassNumber (CL). To approximate the class group of a real
quadratic numberﬁeld

GroundStateEstimation(GSE). To compute the ground state
energy level of a particular molecule

QuantumLinear Systems(QLS). To solve a linear system of
equations

UniqueShortest Vector (USV). To choose the shortest vector
among a given set

Triangle Finding(TF). To exhibit a triangle inside a dense
graph


NP-completeness of the exact distance problem I am currently learning about NP-complete problems and I want to make sure my understanding is correct.

Here is a problem I am working on currently:

  The exact distance problem is, given an edge-weighted graph $G = (V,E)$, vertices $v_1,v_k$, and a distance $D$, is there a simple path from $v_1$ to $v_k$ with length exactly $D$?

The first part of my solution is proving that the problem is in NP. I did this by picking a solution to the problem and proving that we can verify the solution in polynomial time. My proof showed that we can verify the solution in $O(mn)$ time, where $m$ is the number of edges and $n$ is the number of vertices.

The next part is showing that a problem we know to be NP-complete can be reduced to the exact distance problem. I am having trouble deciding on an easy NP-Complete problem to use in this part. Would the Hamiltonian Path problem be a good choice?

Yes.  Keep in mind exactly what the inputs to each problem are.


Simple pseudorandom split of data I want to split my data into $n$ approximately equal parts. Which simple hash functions will ensure that the number of $x$ with $h(x)\equiv i\pmod{n}$ is approximately equal for each $i$?

Assuming the number of data points is much larger than the number of buckets:

The theory answer: any universal hash function will suffice to ensure that the parts are roughly similar in size (on average, in expectation, over the random choice of hash function).

The pragmatic answer: any hash function that provides roughly equidistributed outputs is likely to suffice.  Thus, any hash function that doesn't suck will normally be fine in most cases (e.g., as long as the inputs aren't adversarially chosen and as long as the hash function doesn't have serious problems).


Mean number of edges between two equal partitions For a random undirected graph with $n$ nodes, where each node has $k$ incident edges ($nk/2$ edges in total), the vertex set is  partitioned into two sets each having $n/2$ nodes.

  What is the order of the number of edges that start in one partition and end in the other?

My back of the napkin calculation is half of total number of edges, $nk/4$. If I place randomly an edge it has $1/4$ chance of having both ends in one partition, $1/4$ chance of having both ends in the other partition and $1/2$ chance of having the ends in both. I find it surprising that it could be half.

Your thinking is correct. To verify your claim you can check this lecture notes on the probabilistic method by Matousek and Vondrak. More specifically check the proof of Theorem 3.3.1 stating that any graph with $m$ edges contains a bipartite subgraph with $\frac{m}{2}$ edges.


Number of Inner nodes in a B-Tree the question goes as follows:
In a B-tree (d,2d) of height h, what is the minimal and maximal number of inner-nodes (excluding leaves)?

My idea:

Minimal: The root is 1, it has a minimum of 2 children, therefore we have 1 + 2, and then for any level below each node will have the minimum nodes allowed which is d. We get $1 + 2 + 2d + 2d^2 + ... + 2d^{h-1}$ including the leaves, therefore making $1 + \sum_{i=1}^{h-2} 2d^i$ (note that the final index is $h-2$ since we dont count the leaves).

Maximal: Pretty similiar but each level will have $2d$ children, thus making $ 1 + 2d + (2d)^2 + .... + (2d)^{h}$ including the leaves, therefore making $ \sum_{i=0}^{h-1} (2d)^i$.

However, the answer sheet goes $1 + \sum_{i=1}^{h} (2d)^i$ for maximal and $1 + \sum_{i=1}^{h} 2d^{i-1}$ for minimal.

I'll note that the height is defined as the numbers of edges from top-to-bottom, and for example; a tree of root only is of height 0. Tree of root + one set of children is of height 1.

Am I missing something or is there a mistake in our answer-sheet?

Thanks!

Update: There was an error in the answer sheet, it turns out I was right.


Complexity of "half cycle" I'm working on the following problem:
HALFCYCLE (HALFC):
Input:
A directed graph $G = (V,E)$.
Output:
Whether the longest cycle in $G$ has length $ \lfloor |V|/2 \rfloor$.

Prove that if $\mathsf{PH} \ne \mathsf{coNP}$ then HALFCYCLE is not NP-complete.

I have no idea how to solve this implication.

Show that if HALFCYCLE is NP-complete then $\mathsf{NP}=\mathsf{coNP}$, and so the polynomial hierarchy collapses to NP.

How do you prove that if HALFCYCLE is NP-complete then $\mathsf{NP}=\mathsf{coNP}$?
There are two options:

Show that coSAT reduces to HALFCYCLE. Since HALFCYCLE is NP-complete, in particular it is in NP, and so coSAT is in NP, implying NP=coNP.
Show that HALFCYCLE is in coNP. Since HALFCYCLE is NP-hard, in particular SAT reduces to HALFCYCLE, and so SAT is in coNP, implying NP=coNP.

(You can replace SAT with any NP-hard problem, and coSAT with any coNP-hard problem.)

Good luck!


Why do we use the number of compares to measure the time complexity when compare is quite cheap? I think one reason a compare is regarded as quite costly is due to the historical research as remarked by Knuth, that it came from tennis match trying to find the second or third best tennis player correctly, assuming the tennis players are not a "rock paper scissors" situation (but has an "absolute 'combat' power").

If we have an array of size n being 1,000,000, we don't usually mind comparing 2,000,000 times to find the second largest number.  With the tennis tournament, having a Player A match with Player B can be costly as it can take a whole afternoon.

With sorting or selection algorithms, for example, what if the number of comparisons can be O(n log n) or O(n), but then, other operations had to be O(n²) or O(n log n), then wouldn't the higher O() still override the number of comparisons? (Maybe it didn't happen yet, or else we would have a study case about this situation). So ultimately, shouldn't the number of atomic steps, instead of comparisons, measured by the order of growth as compared to n (O()) that determines the time complexity?

Sure.  But in practice that is rare: the sorting algorithms we usually use or analyze in practice do at most a constant number of other operations per comparison, so this isn't an issue for the sorting algorithms we actually care about.  This means that measuring the number of comparisons or the number of steps taken gives you the same asymptotic running time.

Also, there are some situations where we use sorting algorithms where each comparison is much slower than the other operations.  A comparison may be slower than the other operations, because conditional branches can be very slow on modern processors (each comparison may have a significant chance to cause pipeline flushes).  And if you are sorting complex objects with a custom comparison function, then each comparison might take many instructions.  So, in at least some cases, the number of comparisons might well dominate the over time it takes to sort the input.

Finally, there are certainly some cases we do take into account the time to perform other operations.  It's most common to only count the number of comparisons, but by no means universal.  In situations where the time taken for other operations is important, people do analyze the total running time.

Ultimately, asymptotic running time analysis is only a theoretical model.  It is a simplified model that omits many considerations.  Any such simplification will necessarily ignore many factors.  As long as those factors are unimportant, this can be useful, as it helps you simplify the problem enough to analyze it and gain insight.  But, as always, if one of those factors turns out to have a significant effect and you didn't include it in your model, then the model will yield misleading results -- this is true of all models, and is not limited to sorting or algorithmic analysis.  Part of the art of modelling is identifying which factors dominate and which factors are second-order, so that you can choose a model that's only as complex as needed -- it is as simple as possible, so you can understand it better, but no simpler than that, so it still yields predictions that are reasonably representative of the real world.


Language whose intersection with a CFL is always a CFL (2) This is a follow-up to this question, which asks for an example of a non-regular language $L$ which satisfies the following condition, intersection resilience:

  If $L'$ is context-free then so is $L \cap L'$.

We know that all regular languages are intersection-resilient, and clearly every intersection-resilient language is context-free. Ginsburg and Spanier showed in 1964, in their paper Bounded ALGOL-like languages, that every context-free subset of $x^*y^*$ is intersection-resilient (Theorem 6.1, Corollary 2).

  Which languages are intersection-resilient?

Just a few notes (I'll try to add the proofs later).

Intersection-resilience seems closed under homomorphism.

A necessary condition for intersection-resilience is that for all homomorphisms $\varphi : \Sigma \to \Sigma \cup\ \{\epsilon \}$; $\varphi(L) \cap x^*y^*x^*$ must be a regular language (where $x$ and $y$ are any two distinct symbols of $\Sigma$).

So the result of Ginsburg and Spanier seems "tight" (if we use the same homomorphism trick).


Could a directed graph be bipartite? I check for the symmetric directed graph and it's impossible to be bipartite , because we can't divide the vertices into two sets since all will have in - and out arrow
but in general it could be right ?
 if I draw a graph with one direction

The monograph Digraphs: Theory, Algorithms and Applications by Bang-Jensen and Gutin defines a bipartite digraph as a digraph whose vertices can be partitioned into two sets $A,B$ such that every directed edge connects a vertex in $A$ to a vertex in $B$ or vice versa. Alternatively, a bipartite digraph is a digraph which can be obtained from a bipartite graph by replacing each undirected edge by a directed edge or by a pair of directed edges.

In some situations we might want to add the condition that there are no parallel edges, that is, that it if $(x,y)$ is an edge then $(y,x)$ is not an edge.


Bipartite Graph - How to determine largest subsets that are all connected I have a bipartite graph $G = (U,V,E)$, where $U$ and $V$ are disjoint node sets and $U \cup V$ is the set of all vertices, and $E$ is the set of all edges.
I'm looking for subsets $U' \subseteq U$ and $V' \subseteq V$ such that there exists an edge $\{i,j\} \in E$ for all $i \in U', j \in V'$ and
$|U'| + |V'|$ is maximum.

Ideally, I'm looking for the absolute best solution (a single one is sufficient if there is more than one), but happy to find any solution so that $U'$ contains at least 50% of $U$ and $V'$ contains at least 50% of $V$ (and no solution if no such solution exists).

The naive algorithm (construct all subsets, calculate if they satisfy the requirements and pick the largest) does not seem very promising to find a quick solution.

I'm not that familiar with the terms in graph theory, so I'll be perfectly happy with references to "standard problems" if that's what I'm looking for.

Rephrasing from On Bipartite and Multipartite Clique Problems:

You can formulate the problem as an Integer Linear Program. Let the vertices in each partition be $V_1,V_2$ respectively. Take a (binary) variable $x_v$ for each $v\in V_1\cup V_2$. Then the problem is do determine

$$\textrm{maximize } \Sigma_{v\in V_1\cup V_2} x_v \textrm{ subject to}$$

$$x_v+x_u\leq 1 \textrm{ for all } u\in V_1, v\in V_2 \textrm{ so that } (u,v)\notin E$$

In general, solving ILP's is $NP$-complete. However, in this case, the corresponding constraint matrix is totally unimodular. Consider the relaxed problem: instead of requiring all $x_v$ to be binary, we instead only require that $0\leq x_v\leq 1$ (dropping the integrality constraint). Because the constraint matrix is totally unimodular, the optimal solution to the LP will be integral (and thus also a solution for the ILP). You can use the simplex method (or if you insist on wost-case polynomial time, the ellipsoid method) to obtain a solution for the LP, which is automatically a solution for the ILP.


Proving that if $L=\{ a^n b^n c^n \colon n\ge 0 \}$ than $L\notin CFL$ I'm going over "Introduction to the Theory of Computation" by Michael Sipser in which there's an example of using the pumping lemma for CFLs to prove that $L=\{ a^n b^n c^n \colon n\ge 0 \}$ is not a CFL.

Now, in the book they do it in a way that I understand but I think it can be simplified, so here goes:

Assume by contradiction that $L\in CFL$ with pumping constant $p$ and let   $\omega = a^p b^p c^p$. Clearly $\omega \in L$ and $\| \omega \| \ge p$. Let $\omega = uvxyz$ a division such that

$\| vy \| > 0$
$\| vxy \| \le p$

Condition 1 stipulates that for every $i \neq 1$ pumping will actually change the substring $vxy$.
Condition 2 stipulates that the substring $vxy$ is comprised of at most two type of alphabet symbols. For now we assume that these symbols are $a$ and $b$.

Combine these two facts and we see that for every $i \neq 1$ the string $uv^i xy^i z$ has a different number of $a$'s and $b$'s than $c$'s.

Again, the proof in the book is a bit more complexed, which leads me to think that I might have a mistake here.

Any thoughts? thanks!

Frankly, I think your argument works. As there is always one of the letters missing, the second condition forces the substring to be "short", pumping will not get equal amounts of $a,b,c$.

For didactical purposes authors in books take extra precautions to make sure the student understands that all cases must be covered. Hence they tend to avoid shortcuts.


Which areas in CS will be (or have been) most affected by fully homomorphic cryptography? I'm in the middle of planning a 5000ish word essay on fully homomorphic cryptography, the current practical implementations and their limitations.

Which areas of CS as a subject have been (or will be) most affected or will utilise fully homomorphic cryptography the most in the coming years and developments?

PS. I did several searches and couldn't find a repeated iteration of this question, hope the fact this isn't a specific theory questions gets me in hot water!

Before turning to your actual question, let me mention that there aren't any practical implementations of fully homomorphic encryption. There are some implementations that are far from being practical, and it's hard to guess whether that will change in the foreseeable future.

Fully homomorphic encryption is a goal in itself, as it enables outsourcing computation resources without sacrificing privacy. As such, its applications are mainly outside computer science, in the same way that the word processor Microsoft Word doesn't have any applications inside computer science (other than writing papers; though you should do that in LaTeX).

That said, fully homomorphic encryption could be used as a building block for other cryptographic applications. Vaikuntanathan's technical survey article contains some pointers in Section 6.4: verifiably outsourcing computation; and constructing short non-interactive zero-knowledge proofs. The latter has other applications and is not an end in itself, see Groth's technical survey article.


"pure" explanation of Reed-Solomon? I encountered two applications of RS codes - one in group testing, and another time someone said that a solution to an interview question was using it. But when I search for explanations, it's all about the cracks in the CD disks and such. Is there a good source that puts the math first?

Jon Hall's coding theory notes, available online here are quite good. See Chapter 5.
In addition, see Blahut's text Algebraic Codes for Data Transmission where more focus on decoding algorithms is present.


Do not understand why log n = O(n^c) (for any c>0) Can anyone help me understand this equation?

  $\log (n) = O(n^c)$    (for any $c>0$)

Does it mean that $O(\log (n)) < O(n^c)$ (for any $c>0$)?

Added:

Please also prove that $\log (n) = O(n^c)$ is true.

It's not actually an equation $f = O(g)$ is a lazy shorthand that should be written $f \in O(g)$. So if you look back at the definition of $O$, you should be able to see what $\log n \in O(n^{c})$ for any $c > 0$ means:

  For every $c > 0$, there exists $n_{0} \geq 0$ and $k \geq 0$ such that $\log n \leq k\cdot n^{c}$ for all $n \geq n_{0}$.

Always remember that $O(\cdot)$ describes a set, $O(\log n) < O(n^{c})$ doesn't actually make sense (unless you make up a special meaning for $<$, but then no-one will know what you're talking about). You could say $O(\log n) = O(n^{c})$, as equality for sets has a understood meaning, though of course this statement in particular would be false.

As John Kugelman points out in the comments below, normal set relations do make sense, so $O(f) \subset O(g)$, $O(f) \subseteq O(g)$, etc., make sense.


Is Hamiltonian path NP-hard on graphs of diameter 2? Let $G$ be a graph of diameter 2 ($\forall u,v\in V: d(u,v)\leq2$).

  Can we decide if $G$ has Hamiltonian path in poly time? What about digraphs?

Perhaps some motivation is in place:

the question arises from Dirac's theorem which states that if $\forall v\in V:d(v)\geq \frac{n}{2}$ then the graph is Hamiltonian, as well as it's generalizations (the Ghouila-Houri theorem and the result from Bang-Jensen and Gutin's book).

I've shown here that these degree requirements imply that the graph has diameter 2, and was wondering if such graphs can be decided without the degree requirements (strong gut feeling: No).

Assuming you are talking about directed graphs, the work of Füredi et al. [1] shows that such graphs of n vertices and diameter 2 have at least ~n log (n) edges, or an average degree of ~log(n).  I am aware of no subsequent result tightening this result, and the authors themselves suggest that they think this result is tight; this is quite far from the known sufficient conditions for Hamiltonian paths, which are based on a roughly linear vertex degree.

As a result, this appears to be an open and difficult problem that would require some significant research for a solution.

[1] Füredi, Zoltán, et al. "Minimal oriented graphs of diameter 2." Graphs and Combinatorics 14.4 (1998): 345-350.


Reduce Clique to Set Cover Is it possible directly to reduce clique to set cover?
I know that there are some ways of direct reduction from Clique to Vertex Cover and from Vertex Cover to Set Cover, so I am very interested to know if the is a way to reduce clique to set cover directly without the use of the transitive rule.

Both problems are NP-complete and, by definition, there is a direct reduction between any pair of NP-complete problems.


longest palindromic subsequence / substring and dynamic programming The longest palindromic subsequence problem can be solved using dynamic programming because it is recursive and has overlapping subproblems, as described in https://www.geeksforgeeks.org/longest-palindromic-subsequence-dp-12/ .

On the other hand, AFAIK there is no dynamic programming solution to the longest palindromic substring problem. In the DP solution presented at https://www.geeksforgeeks.org/longest-palindrome-substring-set-1/ , the overall solution is equal to the naive one: to compare the length of all palindromic substrings. The only difference is that DP is used to speed up the process of finding if each substring is palindromic, which reduces the time complexity from O(n^3) (naive solution) to O(n^2).

Why is there a DP solution for the LP subsequence problem, but not for the substring problem? Is it because the former can be expressed by a recursion and the latter not?

Finding substring palindromes of maximum size can be solved in linear time in several ways. Right now come to my mind solutions using data structure such as:
- Manacher
- Palindromic Tree
- Binary search + (Hashing or suffix array) (not really linear but almost, $O(n \cdot \log n)$

If you let me use prewritten code to solve this problem I'd choose first option, is probably the faster and easy way, but personally I don't feel comfortable implementing Manacher from scratch.

I'll try to expand in the binary search + hashing solution.

First let's solve the subproblem: is it substring from a to b a palindrome? If you use rolling hash you will be able to determine hash of substring in O(1), so you can hash the string and it's reverse, and ask whether a substring and it's reversed counterpart match in hash. Notice that this solution is susceptible to fail due to hashing collisions, and one way to address this is using some more elaborated data structure such as suffix array.

After having such function, you can binary search over the length of the palindrome, this is: fix a length k, then go over every substring of length k and check whether it is or not a palindrome.

It has a problem, and it is that function is not monotone over k, but this happens because odd palindromes are not contained in even palindromes necessarily, and vice versa. To address this just run two binary search, first over even integers, and second one over odd integers.


Complexity of recognizing whether two $\omega$-regular expressions represent the same language If the complexity of recognizing whether two regular expressions represent different languages is EXPSPACE-complete, then what can be said for the complexity of recognizing whether two $\omega$-regular expressions represent different languages?

It's quite easy to reduce the equivalence problem for regular expressions to the equivalence problem for $\omega$-regular expressions, so you have EXPSPACE hardness.

For EXPSPACE completeness, observe that given two $\omega$ regular expressions $r_1$ and $r_2$, you can translate them to equivalent NBWs $A_1,A_2$, where the size of $A_i$ is at most single-exponential in the size of $r_1$. Then, checking whether $L(A_1)=L(A_2)$ can be done in PSPACE (nontrivial, but well known).


How many bits to represent a quantity $\omega$ bounded in a particular way? I'm working out some details to implement a division algorithm, I'm following the explanation given in this book (chapter 5) for who is interested.

Anyway I need to work out how many bits are necessary to represent a value $\omega$ bounded by

$$
| \omega | \leq \rho r^{k+1} y
$$

where

$$
\begin{array}{l}
\frac{1}{2} < \rho \leq 1 \\
r = 2^l, \text{where $l\geq 1$ is some integer} \\
0 \leq y \leq 2^{k} - 1, \text{ $k$ positive integer}
\end{array}
$$

My approach is finding the number of bits to represent $| \omega |$ and then adding one bit to represent the sign of $\omega$, in two complement.

There fore

$$
\left\lceil \log_2(|\omega|) \right\rceil \leq \left\lceil \log_2(\rho r^{k+1} y) \right\rceil = \left\lceil \log_2(\rho) + (k+1)\log_2 r + \log_2(y) \right\rceil \leq \left\lceil (k+1)l  + \log_2(2^k-1))\right\rceil \leq \left\lceil (k+1)l  + k \right\rceil = \left\lceil (k+1)(l+1) - 1 \right\rceil = (k+1)(l+1) - 1
$$

Therefore in two complement I would need a total of $(k+1)(l+1)$ bits to represent my value $\omega$.

Is this correct?


General method to make circuits? I have a subject called computer architecture in university but I don't get a clue of it.
We get assignments like: make a 2-bit two’s complement carry lookahead adder using 3 4-bit adder.

This is a circuit I have to make in Logisim, however, it's like you need an already deep insight in the subject to be able to make this; insights I don't have (because it's totally new for me).

Is there a kind of method to solve and make these circuits? Using truth tables or anything?

Note: I'm not asking for the solution for this specific problem, only for a method or steps-to-take in general, to be able to make any (basic) circuit.

This is the full exercise: http://msdl.cs.mcgill.ca/people/hv/teaching/ComputerSystemsArchitecture/materials/CA2/CA_Project_2.pdf (Ex5 if you want more explanation of the problem).

I was able to solve the other 4 by trying very hard and using Google but without actually knowing what I was doing.

So again, I'm not asking for this specific solution, only if there is a general way to solve these kind of assignments using a specific method or steps, eventually explained by using this one example-exercise.

Both suggestions in the comments in the OP were excellent and I agree with the users who provided them.  I have included these comments below for continuity:

There is en.wikipedia.org/wiki/Logic_synthesis but the general way of solving exercises in university is by understanding the material or asking your TAs if you have problems. – adrianN

Work with your peers. Students manage to pass the class somehow, so there must be a principled way. The course is designed to impart the mode of thinking which enables you to solve such exercises, but unfortunately the only way to accomplish this is by actually solving the exercises, on your own or together with friends. – Yuval Filmus

To assist you, look at the Wikipedia pages here and here on digital circuits/adders.

Also, ask your instructor and/or TA for suggestions on a good computer architecture and design book.


primitive recursion in the lambda calculus I am having trouble finding out what a primitive subset of the lambda calculus would look like. I reference primitive recursion as shown here: "https://en.wikipedia.org/wiki/Primitive_recursive_function".

These are the three base axioms:

Constant function: The 0-ary constant function 0 is primitive recursive.
Successor function: The 1-ary successor function S, which returns the successor of its argument (see Peano postulates), is primitive recursive. That is, S(k) = k + 1.
Projection function: For every n≥1 and each i with 1≤i≤n, the n-ary projection function Pin, which returns its i-th argument, is primitive recursive.

Here is my confusion. In the LC zero is represented as (λfx. x).
Next the successor functions is defined as (λnfx. f (n f x)). Because they are both axioms both of these functions can be classified as primitive. But when I apply the function suc to zero I get the encoding of the number one. Which is represented as the function (λf.(λx.(f x))).  Now this number is neither zero or the suc function but the result of application. As such I do not see how this result function (value of 1) fits into the rule set. But very clearly a program with the number 1 in it is still primitive recursive. What am I not understanding here? While 1 is the suc to zero, once suc is applied it is neither suc, nor zero.

As you mention, $1$ is primitive recursive according to the following proof:

$0$ is primitive recursive (axiom)
$\operatorname{suc}$ is primitive recursive (axiom)
$1=\operatorname{suc}(0)$ is primitive recursive (composition)

Using this you can show that $1$ is admissible, that is if you add $1$ as an axiom, the resulting set of functions is still the primitive recursive functions.

Note that lambda calculus has absolutely nothing to do with the answer.


Undirected graph with 12 edges and 6 vertices For school we have to make an assignment, and part of the assignment is this question:

  Describe an unidrected graph that has 12 edges and at least 6
  vertices. 6 of the vertices have to have degree exactly 3, all other
  vertices have to have degree less than 2. Use as few vertices as
  possible.

The best solution I came up with is the following one. Here the number in the circles is the degree of that vertex, now I was wondering if there is a better solution, if so, can somebody explain this to me?

I do not need a better answer, just a push in the right direction - if needed.

You have 12 edges, so the sum of the vertex degree is 24. Then there are 6 degree-3 vertices taking away 18. Thus the best you can hope for are 3 vertices of degree 2. Thus you found the solution.


Can we use Big O notation to predict actual running time of the algorithm on machine? As per my understanding, a program can take a different amount of time to run on different machines because it is dependent on hardware. So we use big O notation which is independent of hardware to compare the performance of two algorithms as the input grows.

I am working on an algorithm which has a complexity of $O( X + Y )$ and it takes a number as an input. My advisor has asked me to collect actual runtime(on the same machine) of the algorithm with different numbers as an input. Then determine coefficients a, b and c such that

$runtime=a.X + b.Y + c$

and use this equation to predict runtime for other inputs.
(for instance, consider BFS, in which case $X$ and $Y$ could be replaced by $V$ and $E$ and it takes a source vertex as an input. Now I am asked to record runtimes of the BFS execution using different source vertices as an input and determine the coefficients. The claim is, using the same hardware and same graph but different source vertex I should be able to get a good approximation of the runtime.)

As per my understanding, this approach is incorrect as big O notations are meant for comparison, as the input grows. But my advisor argued that big o notation captures all the operations in the code and therefore there must exist coefficients a,b,c such that the above equation gives a good approximation.

Is the claim made in the above argument is correct?

I'll give you an example where it unexpectedly goes totally wrong:

Write a program that calculates the product of two square matrices with real values, stored as double precision numbers. Use the straightforward algorithm where c [i, j] = sum of a [i,k] * b [k,j]. Measure and print the time for say n = 1 to n = 1000 (this will take a while). The time is $\Theta(n^3)$, so if r (n) is the measured time, you are interested in $c_n$ where $c_n$ is defined by $r (n) = c_n·n^3$.

You will find several interesting effects. You might expect that $c_n$ is quite large for n = 1, 2, 3 etc. because all the overheads are quite large compared to $n^3$, and at some point $c_n$ stays quite unchanged.

If you learned about cache memory, you will realise that a modern processor may have say 64KByte of very fast L1 cache, maybe 256KByte of fast L2 cache, say 4M of not so fast L3 cache, and uncached memory is quite slow. So as n grows, $c_n$ will jump up every time the memory used exceeds one of those cache limits.

But there are worse problems: The naive algorithm uses a really bad pattern to access memory, but how bad it is depends on particular values of n. Worst case is n = multiple of a large power of 2. You can expect the runtime for n = 128 to be massively larger than for n = 127 or n = 129.

So I'd say your advisor is completely wrong.


Given all pairs shortest paths matrix, find graph with minimum total sum of edges I was looking at some problems about graphs, and I got stuck on this one. Namely, we have given matrix of size $N \cdot N$ representing the length of the shortest path in undirected graph between some pairs of nodes in the graph $(i,j)$.

We don't have the original graph, we instead only have the all pairs shortest paths matrix given. We need to find minimal number $x$ such that there is a way to build graph whose all pairs shortest path matrix will be the same as the given one and the sum of the edges in the graph will be exactly $x$.

Note that for some all pairs shortest paths there wont be way to build such graph, so we should also check if there can be any valid solution.

For example: for the matrix below we should output 6, if we link edges (2, 3) with cost 2 and edges (1, 3) with 4

0 6 4
6 0 2
4 2 0

I noticed that the cheapest edges will always exist, so I sorted all the numbers, then I tried using some data structure for checking if from the cheaper edges we have already covered the path from node i to node j, or we should also include new edge in the path.

However my approach doesn't give good results. Please share some advice in which direction the right solution should be.

I think your approach works even if you did not give much details.

Let's call $A$ the matrix. First you sort all pairs ($i$, $j$) with $i < j$ and $A_{ij}$ increasing. You also have initially a graph $G$ with all nodes and no edges.

Then you process the pairs ($i$, $j$) one by one deciding whether to add an edge between nodes $i$ and $j$:

compute $D$, the total weight of the shortest path existing in $G$ from $i$ to $j$ ($+\infty$ if no path).

if $D < A_{ij}$, the problem has no solution,
if $D = A_{ij}$, do nothing,
if $D > A_{ij}$, add the edge between $i$ and $j$ of weight $A_{ij}$ to $G$.

If the shortest path from $i$ to $j$ is undirect, it necessarly has already been placed as you sorted your pairs increasing.


Reduce $L_c=\{\langle M_1 \rangle, \langle M_2 \rangle):L(M_1)\cap L(M_2)\neq \emptyset\}$ to $A_{TM} $ How to reduce $L_c=\{\langle M_1 \rangle, \langle M_2 \rangle):L(M_1)\cap L(M_2)\neq \emptyset\}$ to $A_{TM} =\{\langle M,w \rangle: M$ is a Turing machine that accepts $w$}.

My try:
Construct a Turing machine $N$ using a Turing Machine $U$ that decides universal language as subroutine to decide $L_c$.
$N$, on any input $  <\langle M_1 \rangle, \langle M_2 \rangle >$:
$1.$ Construct a program that generates word $w \in \sum^\ast$ in canonical order.
$2.$ Run $U$ on $\langle M_1, w\rangle $ and $\langle M_2, w\rangle $.
$3.$ If $U$ accepts both, accept.
$4.$ If not, back to $1$.

It seems does not work. Because if $L(M_1)\cap L(M_2)= \emptyset$, $N$ will loop forever(it just can't find such $w$).

The direction of reduction that you are asking for is a bit strange. Typically, we reduce from $A_{TM}$, in order to show undecidability.

Perhaps you meant to ask about the other direction?

At any rate, in answer to your question: your attempt was actually quite close, it just needs a bit of modification. Here's how you can proceed:

Given $M_1,M_2$ as input for $L_c$, construct a new machine $N$ that works as follows: given input $x$, $N$ ignores it (i.e., erases $x$ from it's tape), and then starts simulating $M_1$ and $M_2$ on every word $w\in \Sigma^*$, in canonical order. Note, however, that in order to simulate $M_1$ and $M_2$ on all words, we cannot simply run them on each word arbitrarily, as we might get stuck (we do not use an oracle to $A_{TM}$). Instead, we run them in parallel: run $M_1$ and $M_2$ on each of the first $k$ words in $\Sigma^*$ for $k$ steps, and then increase $k$ by 1. This is a fairly common trick, but it's quite clever.

Now, if at any point both $M_1$ and $M_2$ accept, then $N$ accepts. Otherwise, it keeps running and increasing $k$ forever.

The reduction is completed by sending $<N,\epsilon>$ to the $A_{TM}$ oracle (or, alternatively, it's complete if you treat it as a mapping-reduction).

Note that $N$ accepts $\epsilon$ (and any other word) iff there is a word that is accepted by both $M_1$ and $M_2$.


Describe a turing machine that accepts Language L = {www| w is {a,b}*} I know that for the language ww, the TM can zig zag across the tape and match symbols to see if the strings are equivalent by first finding the midpoint of the string. However I am lost on how the TM can find out where in www the repeated strings start and stop. I can find midpoint but how do I get one third or two thirds of the string. Any tips to get me started?

Let $\ell$ be the length of the input.
You can assume w.l.o.g. that $\ell=3k$ for some integer $k$. If this is not the case (which can be easily checked by your TM), then the answer is trivial.
The problem boils down to finding $k$. In order to do so you can use the following strategy:

"mark" the two rightmost unmarked tape cells;
"mark" the leftmost unmarked cell;
If the cell immediately to the right of the current head position is marked, then you are done since the head must be in position $k$. Otherwise, repeat from step 1.


Solving Recurrence relation with master method? I have to solve the following recurrence equation and I thought to solve it with case #3 of the master theorem. Can I do that?

$$T(1) = c>0 $$
$$T(n) = 9T(n/3) + f(n)$$
$$f(n) = n^2\cdot lg^3 (n) + n^3 \cdot lg(n)$$

I think that $f(n) = \Omega(n^{log_ba})$ where $a=9, b=3$ so $n^{log_ba}=n^2$.

Since  $f(n) = n^3 lg(n)$, we can prove that $$a\cdot f(n/b) \leq c\cdot f(n)$$.

Is it a correct solution?

The only piece I am afraid could be tricky is proving $a\cdot f(n/b) \leq c\cdot f(n)$.

Thank you,
Alan

You are claiming that "we can prove that $af(n/b) \leq cf(n)$". There are two problems with this claim:

This is now what you actually need in order to apply the master theorem. The master theorem needs you to show that there exists $c < 1$ for which $af(n/b) \leq c f(n)$ for all large enough $n$.
You haven't proved your claim.

Reiterating, to prove the claim you need to come up with a value of $c < 1$ such that the following inequality holds for large enough $n$:
$$
9 (n/3)^3  \log(n/3) \leq cn^3 \log n.
$$
This holds for $c = 1/3$, since
$$
9(n/3)^3 \log(n/3) < 9(n/3)^3 \log n = \frac{1}{3} n^3 \log n.
$$


Adding constraints in grammar for Grammatical Evolution I'm trying to use Grammatical Evolution for creating trading strategies. Each sentence in the grammar when evaluated gives a weight matrix of size n x p . (n is the length of backtesting period and p is the total number of stocks in portfolio)

BNF form of Grammar

<expr>  ::= (<foptr>(<expr>,<expr>,<day>))|
        (<fopbi>(<expr>,<day>))|
        (<fopun>(<expr>))|
        (<expr><matbi><expr>)  |
        <var>
<foptr> ::= corr | covariance
<fopbi> ::= mean |
            sma|
            ema
<fopun> ::= rank| -1* | 1/
<matbi> ::= + | - | * | /
<var> ::= Open|High|Low|Close|Volume
<day> ::=  5 | 10 | 15 | 20

The problem is some expressions in this grammar do not make sense. For example, we cannot have a strategy like $Volume/Volume$ or $Low-Low$, etc. And some of the strategies do not have any physical significance, for example, the strategy $Volume+Close$ is not valid as the units of volume and close are different. Any suggestions/references on how to add these constraints to the grammar or circumventing this issue in genetic algorithms will be helpful.

You can enforce that units match by duplicating nonterminals, one per unit.  For instance, instead of var, you can have varA and varB (if A and B are the two types of units); instead of expr, you can have exprA and exprB; with rules like <varA> ::= Close, <varB> ::= Volume, <exprA> ::= ...|<exprA><matbi><exprA>|...|varA, <exprB> ::= ...|<exprB><matbi><exprB>|...|varB, and so on.

There's no good way to modify the grammar to ensure that it cannot generate any expression that would evaluate to 0.  That is best handled by other methods, not by changing the grammar.


0-1 knapsack without repetition My question is why O(nW) at the knapsack problem is pseudo-polynomial.

I read lots of the explanation at stackoverflow, But I don't really understand it.
(https://stackoverflow.com/questions/19647658/what-is-pseudopolynomial-time-how-does-it-differ-from-polynomial-time,
https://stackoverflow.com/questions/4538581/why-is-the-knapsack-problem-pseudo-polynomial#answer-4538668)

The core thing is why we have to think only 'W' as 'logW' bits input, not 'n' as 'log n' bits.

The many explanation said that 'W' is integer but 'n' is just the number of item. Therefore only 'W' size is proportional to 'logW'.

I think this logic have to be applied to 'n'.

Assuming that we are numbering the items from 1 to n, for differentiating the items,

we have to count the numbers from 1 to n.

I think it is the same that the loop does iteration for W times.

Therefore I think it is same with 'W' because this counting also need 'log n' bits.

What do I mis-understand at this problem?

Thanks.

Here is how you encode the input:

Weight and value of item 1.
Weight and value of item 2.
...
Weight and value of item $n$.
$W$.

Suppose that the weight and value are integers, are at most $M$, and both are encoded in binary, as is $W$. Then the length of the encoding is
$$
\Omega(n + \log W), O(n\log M + \log W).
$$
Hopefully this clarifies the difference between $n$ and $W$.


Maximum profit by two parameters Suppose we have two markets. Each market has various buy & sell orders that we can sell to or buy from respectively. Each order represents a specific number of a particular item type  that someone is selling or buying for a specific price per item and we can buy/sell any amount of items from/to any order. Each item type has its own volume per item (m3).

We have transportion that can transport a specific amount of volume and some budget amount.

Our goal is to form such transport cargo load of items that would maximize our profit by going from station A to station B assuming our limited cargo capacity and budget.

The algorithm I'm using is the following:

Sort sell orders of the source station by price_per_item in ascending order and group them by item_type.
Sort buy orders of the destination station by price_per_item in descending order and group them by item_type.
For each item type, form pairs of sell-buy orders based on the amount available in both markets (e.g. [Item, Quantity, Buy At, Sell At]: [Apple, 25, 50, 75], [Apple, 5, 50, 70], [Apple, 20, 60, 70])
Perform one of the following actions based on user input:

(A) Sort pairs by profit per m3 (sell_price - buy_price / volume_per_item) in descending order.
(B) Sort pairs by profit / buy price ratio ((sell_price - buy_price / volume_per_item) / buy_price in descending order.

Take as many items as possible from each pair of the sorted list until either budget = 0 or cargo_capacity = 0 or there are no pairs left.

When using option (A), the described algorithm doesn't take the budget into account while forming the list of most profitable pairs so it gives poor results with a limited budget. When the budget is high, due to the variety of the market the following algorithm uses a full budget amount while cargo space is usually almost empty (which I don't consider the acceptable result as I need to mitigate risks of losing cargo and having large losses due to low ROI).

When using option (B), the gives good profit compared to the amount used to buy the items but it doesn't utilize available budget efficiently.

So the task is to maximize total_profit / total_buy_price ratio while utilizing available budget_amount and cargo_capacity as much as possible.

Does this fall under some type of mathematical problem that can be solved in a mathematical way, and if so, can you suggest some sources to read up on in detail? Thanks.

If you are handling only one truck/cargo in your problem, then this is a typical  Knapsack problem. If you are handling the bigger problem of distributing all items on how many trucks, then it is a variant of Bin Packing problem. Both problems are NP-Complete, however Knapsack has approximate algorithms with guaranteed bounds from optimality.

I suggest you use a somehow mangling compromise between A and B:

Solve using A, then solve using B and take the best answer.
Do both sortings, keep 2 arrays, then at each step compare A choice to B choice and select the better choice (greedy approach)
Assign a weight to each factor then sort an array C according to your weight function. If you don't know the weights then make it equal (half for each factor). If you value price more make its weight above 0.5 if you value volume more then give it a higher weight. This is called multiplicative weight


Expected versus Randomized Is there any difference between expected polynomial time and randomized polynomial time algorithm?

RP (randomized polynomial time) is a complexity class for algorithms that always run in polynomial time, while possibly make truly random choices, and always rejecting correctly while usually accepting correctly (i.e., with probability greater than $\frac{1}{2}$).

Expected polynomial time usually means that the complexity is polynomial time only in expectation, and the answer is always correct.

Suppose you have the following (silly) algorithm to check if the first element, in an array with length n, is the maximum:

Scan the array, check if the first element is maximum.
With probability $\left(\frac{1}{2}\right)^n$, uselessly scan the array an additional $\frac{2^n}{n}$ times, and recheck the result of step 1.
Return the answer from 1 in any case.

This algorithm has expected polynomial time. The cost of the first step is $\Theta(n)$. The expected cost of the second step is $\Theta\left( \left(\frac{1}{2}\right)^n n \frac{2^n}{n}\right) = O(1)$. The cost of the third step is constant. Conversely, it is not in RP because the second step can run in time $\Theta\left( 2^n \right)$ for an unfortunate randomized outcome.