Algorithm to select sets of objects while maximizing number of objects covered If we have different objects,

[A1, A2, A3, B1, B2, B3, B4, B5]

Some calculations will be performed to find compatible objects. For example, lets assume following 3 sets were formed and every set contains compatible objects:

 1. {A1, B2}
 2. {A3, B2}
 3. {A1, A3, B4, B5}

Now we need to perform filtering. One node can participate only once. For example, if B2 has made a pair with A1, then B2 can not participate in any other set. Which means, if we select set 1, then set 2 will be deleted because B2 has already participated. And set 3 will be deleted because A1 has already participated.

Now we need to do filtering such that we maximize number of objects being utilized. If we select set 1, then we are only utilizing A1 and B2.
Thus, optimal way would be to select set 3 which is utilizing 4 objects. And discard sets 1 and sets 2

Right now, i have a complex function which goes through list of sets recursively and keeps on adjusting until no changes are made to existing sets. This is not only inefficient, but it might not work in cases where changing sets can cause ripple effect.

I am not looking for coded solution, but just a guidance that is there any graph algorithm which I should study?

The problem you're describing can be seen as the weighted independent set problem, as follows: Construct a graph $G=(V,E)$, where every node $v$ in $V$ corresponds to your sets of objects. The nodes $v,w$ have an edge in $E$ if and only if they share an object. The weight of each node is the number of objects contained within the corresponding set.

Now, observe that maximizing the amount of objects used corresponds to finding a set of nodes in $G$ such that 1. none of the nodes are adjacent and 2. the sum of weights over these nodes is maximized. This is precisely the weighted independent set problem.

Unfortunately, this problem is NP-hard, which means an exact efficient algorithm is unlikely to exist (and even less likely to be found). This means that, unless you only have to deal with small values, you would either have to resort to heuristic or approximation algorithms, of which there are a few in the literature. It may be possible that only a particular kind of graphs arise (e.g. trees). In that case, there may be an efficient algorithm, but that depends on your input.


Can Haskell ensure a Functor (or other typeclasses) satisfies its law? It seems that Functor definitions in Haskell can be accepted if the type is correct.
This code compiles, but it doesn't satisfy the functor law:

data Bst a = NIL | Node a (Bst a) (Bst a) deriving (Eq, Ord, Show)

instance Functor Bst where
  fmap _ NIL = NIL
  fmap f (Node v left right) = Node (f v) (fmap f right) (fmap f right)

Is is possible for Haskell to check if the functor definition satisfies the functor law?
If Haskell cannot, can Agda/Idris do this?

So, while this question seems Haskell specific at first glance, I think it touches on enough aspects of modern Programming Languages theory and research that there's a good CS-general answer here.

As DW says, it's impossible to automatically verify that an implementation satisfies the Functor laws, by Rice's theorem.

However, strongly-typed languages give you several methods for proving properties of programs, so there are several approaches that work:

Refinement Types. These are a lightweight form of dependent types, where you can refine a type by a predicate that values of that type must satisfy. This lets you model things like the type of non-zero integers. These are implemented in LiquidHaskell, and there's an upcoming accepted paper where they extend techniques like this to verify typeclass laws. This is implemented as a checker on top of Haskell, so you can write normal Haskell code and get all the inference you normally would, but you add annotations that get checked using SMT.
Pseudo-dependent types. Haskell has GADTs, data-kinds, type families, and multi-parameter typeclasses, all of which let you reason about properties of types. The trick is that these tools can't do much to reason about values, so you end up "promoting" your functions to the type level (i.e. writing your functions as type families aka functions  on types) and proving about them. With these, you get some inference, but not quite as much as you do when writing normal functions.

In the long run, Dependent Types are coming to Haskell, but probably not in as full a way as you see in Idris or Agda.
Full dependent types. This is what Agda and Idris and Coq get you, and often in those languages, writing proofs that your instances satisfy typeclass laws is required. Types can depend on values, functions can return types, everything is merge. You have the full power of higher-order logic here, so if you can prove it, almost always you can prove it in these systems.

The tradeoff is that the inference in the languages is limited: you need to annotate nearly every function definition with its type, and in general, these languages add a degree of complexity above what Haskell has. And, all the proofs are explicit: you have to write the proof yourself that your programs fulfill your laws. Tactics can help to automate this process, but it ends up generally being rather tedious.


Find the number of values between i & j(given as input) in an unsorted array in O(1) time Given an unsorted array $A$ of $n$ numbers and inputs $i$ and $j$, can we find the number of values $i<k<j$ in $A$ in O(1) time complexity by doing some preprocessing? An additional requirement is that the preprocessing should be $O(n)$ in both time and space.

I tried calculating an auxiliary array $B$ of size $M$ (where M is the maximum value in $A$) where $B[i]$ stores the number of elements smaller than $i$ in the given array. But for this the time and space complexities would be of order $O(M)$. Can one do better than that?

In $A$, $rank( A[i] ) = \left\vert\left\{ j \in A : -\infty < j < A[i] \right\}\right\vert $

So you could sort the array by putting each element at its rank (up to duplicates, which can also be counted with 2 range queries), so if you could answer queries like this in $O(1)$ time and $O(n)$ preprocessing time and space, you would have an $O(n)$ sorting algorithm.

The latter does exist of course, but only under certain constraints, eg on the range of values.


If R is a regular language, is $R^3= R \circ R \circ R$ also regular? My understanding of a regular language is that for a language to be formal, it must be able to be represented by a DFA or NFA. To prove a language is not regular you can use the pumping lemma to get a contradiction.

I am trying to figure out whether $R^3$ or $R \circ R \circ R$ is regular if R is also regular.

My understanding of the definition of $R \circ R$ is that it is kind of a transitive mapping of R?

And I think if $R \circ R$ is regular then $R \circ R \circ R$ is also regular, so I need to prove $R \circ R$ is regular which really means that I am trying to prove that regular languages are transitive?

I am not sure how I would go about doing this as I am a little confused how regular languages and transitivity relate - as I have only worked with relations for transitivity.

'$R$'
 is not used in the literature to indicate languages ... generally we use $L$.
Anyway, the "$\circ$" operator indicates the concatenation of two or more languages. Keep in mind that the concatenation of regular languages is also regular: you can proove this by 'linking' the NFA's/DFA's thath recognize them.
In this case you are concatenating a regular language with itself, so the resulting language is also regular.

NB:
The opposite is not always true: if the concatenation of two languages is regular, this does not mean that the languages themselves are necessarily regular.


Why do these functions satisfy that f(n) is not O(g(n)) and g(n) is not O(f(n))? I don't understand what these function are like and why they satisfy that f(n) is not O(g(n)) and g(n) is not O(f(n)).
Where is x?
\begin{eqnarray}
f(x)=
\begin{cases}
    k^{2k}, &x\in(2,2+1)& \\
    k^{2k+1}, &x\in(2+1,2+2)&
\end{cases}
\end{eqnarray}
\begin{eqnarray}
g(x)=
\begin{cases}
    k^{2k-2}, &x\in(2,2+1)& \\
    k^{2k+2}, &x\in(2+1,2+2)&
\end{cases}
\end{eqnarray}
Also, could you teach me how to write these functions in Grapher on MacOS? Cuz I want to know what they are like.

Let's firstly imagine function $f$: for $k=2$ we have two intervals $(4,5)$ and $(5,6)$ and for $k=3$ we have two intervals $(6,7)$ and $(7,8)$. Accordingly for $f$ we have:
$$\quad\quad\quad   x\quad\ \overbrace{(4,5)\quad (5,6)}^{k=2}\quad\overbrace{(6,7)\quad (7,8)}^{k=3} \cdots\\
f(x)\quad  2^4\quad\quad 2^5\quad\quad\quad 3^6 \quad\quad3^7$$
for function $g$ we have:
$$\quad\quad\quad   x\quad\ \overbrace{(4,5)\quad (5,6)}^{k=2}\quad\overbrace{(6,7)\quad (7,8)}^{k=3} \cdots\\
g(x)\quad  2^2\quad\quad 2^6\quad\quad\quad 3^4 \quad\quad3^8$$
So, as you see both $f$ and $g$ are increasing, but alternately one is more then  other with more then constant factor, so they cannot be big-$O$ of each other.
To get an idea of an example you can take a look at DNA molecule chain  and imagine, that $f$ is one line and $g$ another.


Computation of discrete logarithm I know that an equation
$$a^x \equiv b \pmod{p}$$
can be solved for $x$ in $O(\sqrt{p} \ log(p) )$ time using meet-in-the-middle technique, which relies on fact that we can rewrite the equation as follows:
$$a^{nk} \equiv ba^{h} \pmod{p},$$ where $nk - h = x$.

I want to know whether one can solve the following equation (relatively) effectively:
$$(a^x \bmod p) \equiv b \pmod{q} $$
where $p, q$ are primes and $p > q$.  I don't see how one can rewrite this one to apply meet-in-the-middle.

Problem source: I've been reading about Digital Signature Algorithm and I want to write a program that finds signature $(r, s)$ using public key only (for toy numbers), which can be done by solving for $r, s$ the following equation $$(r^s \bmod p) \bmod q = (g^{H(m)}y^{r} \bmod p) \bmod q$$

As far as we know there is no efficient way to do that.  Such a way would constitute a break of the DSA scheme, and no break of the DSA is known.  In particular, DSA is believed to be secure, so it is believed that no efficient algorithm for this exists.

If you only want to do it for small numbers, you can just use brute force and try all possible values of $x$.  Or, you can solve

$$a^x \equiv b \pmod p.$$

Then any solution to that equation will be a solution to your equation as well. More generally, you can pick any constant $c$ of your choice such that $0 \le c < (p-b)/q$ and solve

$$a^x \equiv b + cq \pmod p;$$

if you can't find a solution for a particular value of $c$, try another one until you can.  This won't be efficient once $p,q$ get large.


Why do negative array indices make sense? I have came across a weird experience in C programming. Consider this code:

int main(){
  int array1[6] = {0, 1, 2, 3, 4, 5};
  int array2[6] = {6, 7, 8, 9, 10, 11};

  printf("%d\n", array1[-1]);
  return 0;
}

When I compile and run this, I don't get any errors or warnings. As my lecturer said, the array index -1 accesses another variable. I'm still confused, why on earth does a programming language have this capability? I mean, why allow negative array indices?

The array indexing operation a[i] gains its meaning from the following features of C

The syntax a[i] is equivalent to *(a + i).  Thus it is valid to say 5[a] to get at the 5th element of a.
Pointer-arithmetic says that given a pointer p and an integer i, p + i  the pointer p advanced by i * sizeof(*p) bytes
The name of an array a very quickly devolves to a pointer to the 0th element of a

In effect, array-indexing is a special case of pointer-indexing.  Since a pointer can point to any place inside an array, any arbitrary expression that looks like p[-1] is not wrong by examination, and so compilers don't (can't) consider all such expressions as errors.

Your example a[-1] where a is actually the name of an array is actually invalid.  IIRC, it is undefined if there's a meaningful pointer value as the result of the expression a - 1 where a is know to be a pointer to the 0th element of an array.  So, a clever compiler could detect this and flag it as an error.  Other compilers can still be compliant while allowing you to shoot yourself in the foot by giving you a pointer to a random stack slot.

The computer science answer is:

In C, the [] operator is defined on pointers, not arrays.  In particular, it's defined in terms of pointer arithmetic and pointer dereference.
In C, a pointer is abstractly a tuple (start, length, offset) with the condition that 0 <= offset <= length.  Pointer arithmetic is essentially lifted arithmetic on the offset, with the caveat that if the result of the operation violates the pointer condition, it is an undefined value.  De-referencing a pointer adds an additional constraint that offset < length.
C has a notion of undefined behaviour which allows a compiler to concretely represent that tuple as a single number, and not have to detect any violations of the pointer condition.  Any program that satisfies the abstract semantics will be safe with the concrete (lossy) semantics.  Anything that violates the abstract semantics can be, without comment, accepted by the compiler and it can do anything it wants to do with it.


Given all maximal independent sets of a graph, find the maximum indepdent set I am new to this independent set problem in graph theory. As per my understanding so far an independent set is a set of vertices in which no two vertices are adjacent. And the maximal independent set is a set of vertices in which if some vertex is added it will construct an edge.

I understand this now my question is if given all maximal independent set for a graph then the maximum independent set of that graph will be maximal independent set with maximum cardinality right?

Note: As per my understanding there can be more than one maximum independent set but their cardinality will be same.

If an independent set is maximal, it means you cannot add any more vertices into the set. As you correctly suggest, this does not mean that the set is necessarily a maximum independent set in the graph.

You are also correct in saying that every maximum independent set is maximal, and that a graph can have several maximum independent sets.


The problem of equivalence of a CFG and a RG? Given a context-free grammar and a regular grammar, check whether they are equivalent.
It's a fact that it's undecidable, but how could I prove it?

I want to clarify that my question is not about determining whether a CFG describes a regular language. In my problem I am given a CFG and a regular language  and I need to tell whether they are equal or not. These are different problems as far as I understand, mine is easier than that one.

There is no algorithm which can determine for any context-free grammar $G_1$ and regular grammar $G_2$ whether $L(G_1) = L(G_2)$.

However, it may well be possible to determine for particular $G_1$ and $G_2$, using heuristic proof techniques (aka human intuition).

Good luck with the assignment.


How can the max-flow and min-cut problems, if dual to one another, both have unbounded optimal value? The max-flow min-cut theorem states that the value of the maximum flow is equal to the minimum cut capacity.

It is possible that the max-flow and min-cut is equal to $\infty$.

However, reading Introduction to Linear Optimization by Bertsimas and Tsitsiklis, I get the impression that the max-flow and min-cut problems are dual to one another.

From duality theory, I know that, if the primal has finite optimal value then the dual has finite optimal value. Also, if the primal has unbounded optimal value, then the dual is infeasible and vice versa.

In the case of the max-flow and min-cut problems, how can they both have unbounded optimal value ??

Here is an example of this anomaly in linear programs:

$$
\begin{align*}
& \max x & & \min \infty y \\
s.t.\; & x \leq \infty & s.t.\; & y \geq 1 \\
& x \geq 0 & & y \geq 0
\end{align*}
$$

The solution to both programs is $\infty$. What goes wrong?

The duality theorem only works when all coefficients are finite. If you go through a proof of the duality theorem you'll see exactly where it fails, and this is a nice exercise.

I should also stress that $\infty$ isn't usually regarded as a legitimate number in these contexts. If we assume all coefficients are real numbers, then $\infty$ is nothing else than a type mismatch.


Decidability of a language and inclusion between two other languages I have this assignement that asks to say if the following statement is true or false, and possibly justifying the answer:

"Let L₁, L₂ be decidable languages.
For every language L s.t. L₁ ⊆ L ⊆ L₂, L is decidable too

My first idea was to use the Halting Problem Language as L and show that is not decidable to prove the statement is false.

I tried to ask the Professor and he confirmed me that the assignment is false but he gave me a hint about explicitly describing the two languages L₁ and L₂, but I don't know which one would fit for this scope.

Thank you!

Your statement is false. Indeed, if $L$ is any language over $\Sigma$, then
$$ \emptyset \subseteq L \subseteq \Sigma^*.$$


Measuring one way network latency This is a puzzle about measuring network latency that I created. I believe the solution is that it's impossible, but friends disagree. I'm looking for convincing explanations either way. (Though it is posed as a puzzle I think it fits on this web site because of its applicability to the design and experience of communication protocols such as in online games, not to mention NTP.)

Suppose two robots are in two rooms, connected by a network with differing one-way latencies as shown in the graphic below. When robot A sends a message to robot B it takes 3 seconds for it to arrive, but when robot B sends a message to robot A it takes 1 second to arrive. The latencies never vary.

The robots are identical and do not have a shared clock, though they can measure the passage of time (e.g. they have stop watches). They do not know which of them is robot A (whose messages are delayed 3s) and which is robot B (whose messages are delayed by 1s).

A protocol to discover the round trip time is:

whenReceive(TICK).then(send TOCK)

// Wait for other other robot to wake up
send READY
await READY
send READY

// Measure RTT
t0 = startStopWatch()
send TICK
await TOCK
t1 = stopStopWatch()
rtt = t1 - t0  //ends up equalling 4 seconds

Is there a protocol to determine the one way trip delays? Can the robots discover which of them has the longer message sending delay?

The following diagram, from a blog post I wrote, is a visual proof that it's impossible:

Notice how the packet arrival times on each side stay the same, even as the one-way latencies change (and even become negative!). The first packet always reaches the server at 1.5s on the server's clock, the second always reaches the client at 2s on the client's clock, etc. The packet contents and local arrival times are the only things a protocol could be based on, but the contents and arrival times can be held constant as the asymmetry varies by also varying the initial clock skew.

Basically, asymmetry in the one-way latencies looks exactly like clock skew. Since the problem states we don't start off knowing the initial clock skew or the one-way latency asymmetry, and varying one looks like varying the other so their effects are indistinguishable, we can't separate their contributions in order to solve for the one-way latency asymmetry. It's impossible.

More formally, you can't solve for edge lengths when given only the lengths of the cycles. The cycle basis has $n-1$ degrees of freedom, corresponding to $n-1$ unknown clock skews relative to one of the participants. You can always hide the one-way latencies, even when there are many participants:

If you're not so visually inclined, I have another intuitive argument. Imagine a time portal to a hundred years in the future. As you chat across it to someone on the other side, you realize the conversation is totally normal despite the hundred year asymmetry in one-way delays. Any observable effect would have been obvious on that scale!


Complexity of numerical operations I have written a program which contains a while loop: while k < sqrt(n), so clearly my program evaluates $\sqrt{n}$ at each iteration of the while loop. (Note that $n$ and $k$ can both change throughout the loop, although I do not think that this is relevant to the question.)

I am required to calculate the number of arithmetic operations used by my program in terms of the initial value of $n$ (in terms of the number $n$, not the number of digits of $n$) when it is run, where an arithmetic operation is defined as the addition, subtraction, multiplication or division of any two numbers.

My question is, how many arithmetic operations does $\sqrt{n}$ use? Is it a fixed amount or does it change with $n$ (and if so to what extent)?

If you have a look at this wikipedia page  then you will see that there are over tens of algorithms for calculating the square root of a number.

Let's consider the Babylonian method for calculating square roots. This is very similar to Newton's iterative method for finding roots and therefore an approximation algorithm. The pseudocode is as follows:

1. Start with an arbitrary positive start value x.
The closer this value is to the actual root, the better the convergence is.

2. Initialize y = 1.
This variable will hold the value for the previous iteration of the root.

3. Initialize e = some arbitrary small value.
This will determine the accuracy of our root.

4. Do following until (x - y) > e :
  a) Set y = (n/x)
  a) Set x = (y + x) / 2

This answer gives a good look into how the running time complexity of the above method can be obtained. The TLDR version is $O(log(log(n))$ for $\sqrt(n)$.

A small thing to note is that if n can change throughout the loop, then the square root will be calculated every time the loop is run. However if n does not change at all, it is treated as a loop invariant and the compiler takes steps to optimize the performance internally. In short, the calculation of the square root is taken outside the loop body.

Finally, since there are multiple algorithms for calculating the root of a number there is no single solution to the question:

  how many arithmetic operations does (√n) use?

As for the second question, ie:

  Is it a fixed amount or does it change with n (and if so to what extent)?

You can clearly see that its not a fixed amount, and the number of operations depend on the value of n itself, the initial root chosen and the level of accuracy preferred.

Some related additional reading for iterative algorithms: Gradient Descent.


Speculating big O for a binary tree I have a binary tree with $n$ nodes. The tree is not necessarily balanced.

For each node of the tree, I count down the total number of the nodes for its left sub-tree as $n_L$ and then I count down the total number of the nodes for its right sub-tree as $n_R$. Then I calculate $\min(n_L,n_R)$ and then assign the minimum value as a tag to the node. I repeat this process to produce appropriate tags for all the nodes of the tree.

Now I wonder what is the big O for the sum of all the tags. I mean, I wonder if the sum of tags is $O(n\log n)$ or $O(n)$ or $O(n^2)$.

In the most unbalanced case, the binary tree is just a long list like figure below. In this case, I think sum of tags would be 0, therefore the big O would be $O(0)$.

In the case of a perfect binary tree, the tag of the root node might be $2^0\frac{n}{2^{0+1}}$ and at the next level, i.e. root's left and right children, sum of tags might be $2^1\frac{n}{2^{1+1}}$ and for the $i$th level of the perfect binary tree, the sum of tags might be $2^i\frac{n}{2^{i+1}}$.

At the $i$th level, sum of tags might become $2^i\frac{n}{2^{i+1}}=\frac{n}{2}$ therefore looks like that some of tags at each level might be $\frac{n}{2}$ and because a perfect binary three has a total height of $\log_2n$ hence the total sum of tags might be $\frac{n}{2}\log_2n$ and this implies that for a perfect binary tree, the big O for sum of tags might be $O(n\log_2n)$.

Let us denote by $\sigma(T)$ the sum of tags of a tree $T$. As you notice in your worked out examples, $\sigma(T)$ in general depends on the tree structure and not only on the number of nodes. What you are looking for is a tight upper bound on $\sigma(T)$ in terms of the number of nodes.

What is this tight upper bound? For each $n$, we want to know what is the maximal $\sigma$ for a tree having $n$ nodes. Denoting this by $\tau(n)$, this quantity satisfies $\sigma(T) \leq \tau(n)$ for all trees $T$ on $n$ nodes, and furthermore $\tau(n)$ cannot be replaced by any smaller value.

In fact, in practice we often don't care about finding the tight upper bound to this degree of accuracy. It is often enough to find a function $f(n)$ such that for some constant $C>0$, $\sigma(T) \leq Cf(n)$ for all trees $T$ on $n$ nodes, and furthermore for some constant $c>0$, $\sigma(T) \geq cf(n)$ for some tree $T$ on $n$ nodes.

You can prove by induction on $n$ that $\sigma(T) = O(n\log n)$ for all trees on $n$ nodes. Conversely, by taking a nearly complete binary tree $T_n$ on $n$ nodes (that is, a binary tree all of whose leaves are at heights $h,h+1$ for some $h$), you can check that $\sigma(T) = \Omega(n\log n)$. Hence $O(n\log n)$ is a tight upper bound for the sum of tags of binary trees on $n$ nodes.


Is scanner and Lexical analyzer same? Today I read that

  The scanner is a subroutine which is frequently called by an
  application program like a compiler. The primary function of a scanner
  is to combine characters from the input stream into recognizable units
  called tokens.

But isn't it the job of lexical analyzer? Are they both the same?

Yes. These are two different words for the same thing. I've also heard it called a lexer sometimes.


Kolmogorov Complexity, struggle with equation I am working on understanding Kolmogorov Complexity. I've been struggling with the following exercise for quite some time now and would appreciate any inputs.

Show that there exists a constant $c$, such that for each $n \in \mathbb{N} -\{0\},$${K((01)^2}^n) \leq \lceil \log_2(n+1)\rceil +c = \lceil\log_2(\log_2(\frac{|{(01)^2}^n |}{2}))\rceil +c $

Through experimentation, I've come to the conclusion that $|{(01)^2}^n| = 2\cdot2^n \implies \log_2(|{(01)^2}^n|)=n+1$. Why is it wrong to simply substitute this in the above equation like so:

${K((01)^2}^n) \leq \lceil \log_2(n+1)\rceil +c = \lceil\log_2(\log_2(|{(01)^2}^n |))\rceil +c $

Why is the length of the string divided by 2 in the problem statement?

The statement is equivalent to \begin{align}n+1=\log_2\left(\frac{|(01)^{2^n}|}2\right)&\impliedby |(01)^{2^n}|=2^{n+2}.\end{align} If $(01)^{2^n}$ means $\underbrace{(01)(01)(01)\cdots(01)}_{2^n\,\text{times}}$ then the statement is incorrect as $|(01)^{2^n}|=2^{n+1}$ as you have correctly obtained.


Micro-optimisation for edit distance computation: is it valid? On Wikipedia, an implementation for the bottom-up dynamic programming scheme for the edit distance is given. It does not follow the definition completely; inner cells are computed thus:

if s[i] = t[j] then
  d[i, j] := d[i-1, j-1]       // no operation required
else
  d[i, j] := minimum
             (
               d[i-1, j] + 1,  // a deletion
               d[i, j-1] + 1,  // an insertion
               d[i-1, j-1] + 1 // a substitution
             )
}

As you can see, the algorithm always chooses the value from the upper-left neighbour if there is a match, saving some memory accesses, ALU operations and comparisons.

However, deletion (or insertion) may result in a smaller value, thus the algorithm is locally incorrect, i.e. it breaks with the optimality criterion. But maybe the mistake does not change the end result -- it might be cancelled out.

Is this micro-optimisation valid, and why (not)?

I don't think that the algorithm is flawed. If two strings are matched, we compare first its last two characters (and then recurse). If they are the same, we can match them to get an optimal alignment. For example, consider the strings test and testat.
If you don't match the two last ts, than one of the ts remains unmatched, since otherwise your matching would look like this:

This is impossible, since the arrows are not allowed to "cross". The matched t induces several inserts (green boxes in the figure), as depicted on the left:

But then you can simply find an equally good alignment, depicted on the right. In both cases you match a t and you have two inserts.

The argument for a substitution of one of the last ts is the same. So if you substitute one of the last ts, then you can instead match the last two t, and get a better alignment (see the picture).


Red-Black Tree deletion algorithm (CLRS, 3rd edition) : Deleting the root I have been following the third edition of Introduction to Algorithms (by Cormen, Rivest, et al.), and have been studying the deletion algorithm for red-black trees. However, I am confounded at the moment while I am trying to delete a node from the tree.
The algorithm could be found at Page No. 324, third edition, Introduction to Algorithms,(CLRS).
Suppose I have a red-black tree as follows:

This RB TRee was constructed by inserting the number 1 to 7 in non-decreasing order (i.e. 1,2,3,4,5,6,7).
Suppose we wish to delete the root of the tree, node 2.
Then as per the delete algorithm, on page-324,
1. y = z (i.e. y = ROOT of the tree)
2. y-original-color = BLACK
3. z.left exists, skip lines 4-5
6. z.right exists, skip lines 7-8
9. Now y = tree-minimum(z-right), i.e. y is a pointer to 3
10. y-original color = BLACK
11. x = y.right (i.e. T.NIL only)
12. y's parent = pointer to 4, which is not z (i.e. ROOT), skip line 13
14. Else transplant y with y.right, i.e. left of '4' is T.NIL now
15. Lines 15-16 fix the new parent issue for the transplanting node
17. Line 17 transplants z (i.e. the ROOT) with the pointer y, i.e. 3 is the root now
18. Lines 18-21 fix the parent and left child issue for the new ROOT
21. as y-original-color is BLACK, call the RB-DELETE-FIXUP function for x

As x is T.NIL, this is passed as an argument for the RB-DELETE-FIXUP function.
However, there is an issue.

How can we claim the parent of this x, i.e. the T.NIL, for the purpose of finding its sibling?
Even if we claim that 4 be the parent of this x, and 6 be the sibling (as per the diagram), then the deletion falls under none of the categories mentioned in the book since 6 is a BLACK parent and both of its children are RED.

I have been following the algorithm and have been quite confounded by this case. Maybe there is a misinterpretation on my end regarding following the algorithm. Any help in this regard would be appreciated.

This is case 4, because w's right child is red. the left child (of z) could have any color red/black.


What is the best way to compress a string with only numbers and commas in it? I have a string like this:

11,512,64,23,46,12,67,85,84

And I'm sure it's following these rules below:

Only , and 0123456789 in it.
No number will be bigger than 999, that means they are all 1,2 or 3 digits number.

Are there any simple algorithms that I can have to compress/decompress the data?

For instance, a very stupid way I can think is to convert each number into base-16 or even base base-36 numbers.

Treat this as a base-11 number (the comma is treated like the digit "10").  Convert the base-11 number to binary, and use the resulting binary string as the compressed version of your data.

This will be close to optimal.  It falls short of optimal only in that it does not take into account the guarantee that every number in the list will have at most 3 digits -- but even taking that into account would not improve the compression ratio much.

The absolute best method will depend on the distribution of data that you will be compressing; but I expect this will be close to optimal for most real-world distributions.


What is the definition of$\mathcal{Mod} P$ counting complexity class? Question : What is the definition of $\mathcal{Mod} P$ counting complexity class?

I am not getting anything relevant about this complexity class on Google search. If it is available on Wikipedia, please share a link.

$\mathcal{Mod} P$:  A set $L$ is in the class $\mathcal{Mod} P$ if there exist functions $f \in \#\mathcal{P} $ and $g \in \mathcal{FP}$ such that string $x$, and $g(x) = 0^p$ for some prime $p$ and

$$x \in L \iff f(x) \ncong 0 \pmod{p}\,.$$

I am not able to understand what it is mean by  $g(x) = 0^p$ for some prime $p$.

Reference  : Köbler and Toda, On the Power of Generalized MOD-Classes. In Proceedings of 8th Annual Structure in Complexity Conference, IEEE, 1993. PDF

The class ModP is defined in Definition 3.1 on page 3 of your reference.

The abstract of the paper clearly states that the paper studies the computational power of the new counting class ModP. This suggests that this class is introduced in the paper, and in particular, is defined in the paper.


Visit all vertices of a graph I need to find the fastest route passing in all vertices

Each vertex is a class.
I can choose the number of classes for semester.
Some classes have prerequisites (A and B need to be done one semester before C), so I can't do A, B and C at the same time.
Some classes (C in this case) have only in the second semester of the year (a year has only 2 semester).

So let's say that I study 2 classes each semester

Worst case possible:

First semester of year 1:

Study A and D

Second semester of year 1:

Study B (C can't be done because A and B is a prerequisite)

First semester of year 2:

nothing (C can only be done in the second semester)

Second semester of year 2:

Study C

The optimal answer would be:

First semester of year 1:

Study A and B

Second semester of year 1:

Study C and D

I know the basics of the most common graph algorithm like Kruskall, Prim, DFS... but I just don't know how I could apply them to my problem, the first think that I thought was use Dijkstra algorithm to pass in all vertices but how I would take in count that C can only be done at certain semesters? maybe I should use different algorithms at the same time?

This is not an exercise, it's a real problem that exists at my college, and I would like to solve using a smarter solution using an algorithm rather than a hard coded implementation. Anything that helps me to guide to the right direction will be well appreciated.

Ignoring the even semester constraints, you can model this as a scheduling problem where classes are jobs of processing time $1$ which have to satisfy precedence constraints and must be processed on a parallel machine that can process at most a fixed number $m$ of jobs at the same time. In standard notation, this problem would be called $Pm\mid\text{prec},p_j=1|C_\text{max}$ and is NP-complete (Ullman, NP-complete scheduling problems, J. Comp. Sys. Sci., 10, 1975).

That said, for the size of problems you may be interested in, an integer programming model can likely be solved to optimality. If you let the semesters be $S=\{1,2,\ldots,s\}$, where $s$ is some upper bound on the number of semesters, $m$ the maximum number of classes you can do every semester, and $\prec$ the predecence relation (i.e. $c\prec c'$ if class $c$ must precede class $c'$) a formulation would be
\begin{align}
\text{minimize } & C_\text{max},\\
\text{subject to } & C_\text{max} \geq s\,x_{cs}, & \forall c,s,\\
& \sum_c  x_{cs} \leq m, & \forall s,\\
& \sum_s x_{cs} = 1, & \forall c,\\
& 1+\sum_s s\,x_{cs} \leq \sum_s s\,x_{c's}, & \forall c\prec c'\\
& x_{cs}\in\{0,1\}, & \forall c,s,
\end{align}
where $x_{cs}=1$ indicates that class $c$ is done in semester $s$. It would be also easy to add even semester restrictions to this model.


Nested Loop Time Complexity vs Successive Loops An algorithm has a calculation whose worst case time complexity $T(x)=O(x^2)$ that outputs solutions $y$ & $z$ for input $x$ (the algorithm's worst case time complexity is greater than quadratic time):

for (i = 1; i <= x; i++)
    {
    for (j = 1; j <= i; j++)
        {
           // Some quadratic time calculation of x that gives y & z
        }
    }

A different algorithm using successive loops is created for a given $x$ that outputs the same $y$ & $z$:

for (i = 1; i <= x; i++)
    {
         // Some quadratic time calculation of x that gives y
    }
for (i = 1; i <= x; i++)
    {
         // Some quadratic time calculation of x that gives z
    }

Is the time complexity of the second algorithm $T_s(x)=O(x^2)$?

I think that the first algorithms running time is actually $\mathcal{O}(x^4)$.

The outer for loop executes exactly $x$ times,
the inner for loop executes at most $x$ times during every one of these $x$ iterations of the outer loop

In fact, the inner loop executes exactly $\frac{x(x+1)}{2}$ times, and $\frac{x(x+1)}{2} = \frac{x^2 + x}{2} = \mathcal{O}(x^2)$, since our asymptotic notation allows us to essentially ignore the constant factors.

So already we have a growing complexity of $\mathcal{O}(x^2)$. If we now consider the contents of the inner for loop, which you say is a quadratic time calculation of $x$. I read this as follows: the complexity of the inner loops body is a quadratic function of x $\rightarrow \mathcal{O}(x^2)$. My answer is based largely upon this assumption.

If my assumption is correct, then a time complexity of $\mathcal{O}(x^4)$ easily follows from this reasoning: the outer and inner for loop collectively produce $\mathcal{O}(x^2)$ iterations of some algorithm that takes $\mathcal{O}(x^2)$ steps to complete itself. An extremely informal (read: not quite right, but right enough to demonstrate a point) mathematical argument for this might be:

($x$ outer loop iterations) $\cdot$ ($x$ inner loop iterations) $\cdot$ ($x^2$ loop body steps) $= x^4$ total steps.

With the second algorithm, the same reasoning can be used. Again, we have some procedure, which takes $\mathcal{O}(x^2)$ steps to run, which is being executed $x$ times. This gives us $\mathcal{O}(x^3)$ steps in total. Since we have two loops of this form, we can conclude that algorithm 2 has a time complexity of:

$\mathcal{O}(x^3) + \mathcal{O}(x^3) = \mathcal{O}(x^3)$

Note that in this case we have two consecutive loops that, asymptotically speaking, do essentially the same amount of work. In reality it might be that our first loop which calculates $y$ performs some constant factor amount more or less steps than our second, which calculates $z$, but here that doesn't matter, since we're focusing on the rate of growth of our running time. One way of thinking about it is as follows:

$\mathcal{O}(x^3) + \mathcal{O}(x^3) = \mathcal{O}(x^3 + x^3) = \mathcal{O}(2 \cdot (x^3)) = \mathcal{O}(x^3)$.

Here we can drop the 2, since its a constant factor.


Minimal size of a context-free grammar which defines $L_n=\{a^k\mid 1\le k\le n\}$ I am looking for the minimal size of a context-free grammar which defines the finite language $$L_n=\{a^k\mid 1\le k\le n\}.$$
The size of a grammar is defined as the total length of all right-hand sides of the rules.
For example a grammar with
$$S\to A_1A_1\\A_1\to A_2A_2\\A_2\to A_3A_3\\A_3\to A_4A_4\\A_4\to aa$$
has size $5\cdot 2=10$.
It is well-known that the minimal context-free grammar which defines the language only accepting the word $a^k$ has size $\Theta(\log k)$ (see the example above for the construction of the word $a^{32}$).
Now, I am interested in the size of a grammar constructing all strings $a^k$ ($1\le k\le n$) for a given $n$. By the information above it is easy to create a grammar for $L_n$ of size $$\Theta(n+\sum_{k=1}^{n}\log k)=\Theta(\log n!)=\Theta(n\log n)$$
since we can create all words by a grammar of size $\Theta(\log k)$ and connect those grammars with a start rule of size $n$ (one symbol for each word). But since the final grammar is allowed to share nonterminals this construction is clearly not optimal. Maybe the smallest grammar has asymptotically the same size, but i don't know. Any help?

There is a grammar of size $O(\log n)$ using repeated squaring.

Let's start with the simpler case $n = 2^m$:
$$
\begin{align*}
&S \to a B_0 B_1 \dots B_{m-1} \\
&B_i \to A_i | \epsilon && (0 \leq i \leq m-1) \\
&A_i \to A_{i-1}A_{i-1} && (1 \leq i \leq m-1) \\
&A_0 \to a
\end{align*}
$$
Here $A_i \to a^{2^i}$ and $B_i \to a^{2^i}|\epsilon$.

More generally, suppose $n-1 = 2^{d_0} + 2^{d_1} + \cdots + 2^{d_\ell}$, where $d_0 > d_1 > \cdots > d_\ell$. The corresponding grammar is:
$$
\begin{align*}
&S \to a B_{d_0} | a C_0 B_{d_1} | a C_1 B_{d_2} | \cdots | a C_{\ell-1} B_{d_\ell} | aC_\ell  \\
&C_j \to C_{j-1} A_{d_j} && (1 \leq j \leq \ell) \\
&C_0 \to A_{d_0} \\
&B_i \to B_{i-1} A_{i-1} | B_{i-1} && (1 \leq i \leq d_0) \\
&B_0 \to \epsilon \\
&A_i \to A_{i-1}A_{i-1} && (1 \leq i \leq d_0) \\
&A_0 \to a
\end{align*}
$$
Here $A_i \to a^{2^i}$, $B_i \to \{a^k : 0 \leq k < 2^i\}$ and $C_j \to a^{2^{d_0} + \cdots + 2^{d_j}}$.

As an extra property, both grammars are unambiguous.


Why is this NP complete? I am looking at the diverse subset problem in Kleinberg and Tardos, shown in the image:

Why can't we give a polynomial time algorithm for this? Cant we iterate through each person a, and then each item i, and then see for each person b $\neq$ a if b has bought item i, then conclude that a and b cannot be diverse? And if we get through all items and no item that a has bought has been bought by b therefore implies they're diverse? Then we do this with each customer. What's wrong with this approach?

The algorithm you described isn't polynomial time because it has to consider every possible subset of customers (they are $2^m$ of these).

Solution

This problem is NP-hard because the vertex cover problem can be reduced to it.

https://en.wikipedia.org/wiki/Vertex_cover#Computational_problem

HINT: To do the reduction, consider how you would model $A$ as a graph and vice-versa. Once you've done that, consider how a "diverse set" is related to a vertex cover in the graphs.


Why CLRS example on residual networks does not follows its formula? I am learning algorithms to solve Maximum Flow problem by reading the CLRS book and confused by the following figure:

That is:

  A flow in a residual network provides a roadmap for adding flow to the
  original flow network. If $f$ is a flow in $G$ and $f'$ is a flow in
  the corresponding residual network $G_f$, we define $f \uparrow f'$,
  the augmentation of flow $f$ by $f'$, to be a function from $V \times V$ to
  $R$, defined by

  $$(f \uparrow f')(u, v) = \begin{cases} f(u,v) + f'(u, v) - f'(v, u) &
> \text{if (u,v) $\in$ E} \\ 0 & \text{otherwise} \end{cases}$$

How the flow network in (c), for example $(s, v_2)$ got the flow 12 ?
If we follow the formula, it must have a flow 5:
$8 + 5 - 8 = 5$

That's not what the formula gives you.  As the caption says, the capacity of the augmenting path in the residual network in (b) is $4$.  Therefore we send 4 units of flow along the augmenting path from $s$ to $t$, namely, the path $s \to v_2 \to v_3 \to t$.  In particular, $f(s,v_2)=8$, $f'(s,v_2)=4$, and $f'(v_2,s)=0$, so the updated flow is $8+4-0=12$.


Quicksort to find median? Why is the worst scenario $\mathcal{O}\left(n^2\right)$ when using quicksort to find the median of a set of numbers?

If your algorithm continually picks a number larger than or smaller than all numbers in the list wouldn't your algorithm fail? For example if the list of numbers are:

$S = (12,75,82,34,55,15,51)$

and you keep picking numbers greater than $82$ or less than $12$ to create sublists with, wouldn't your set   always remain the same size?
If your algorithm continually picks a number that creates sublists of $1$ why is the worst case scenario $\mathcal{O}\left(n^2\right)$? Wouldn't efficiency be linear considering that according to the Master Theorem,  $d>\log_b a$?* (and therefore be $\mathcal{O}\left(n^d\right)$ or specifically in this case $\mathcal{O}\left(n\right)$)

*Where $d$ is the efficiency exponent (i.e. linear, exponential etc.), $b$ is the factor the size of problem is reduced by at each iteration, $a$ is the number of subproblems and $k$ is the level. Full ratio: $T(n) = \mathcal{O}\left(n^d\right) * (\frac{a}{b^d})^k$

Quicksort is for sorting, the algorithm you refer to is a selection algorithm known as Quick Select.

Since you can only pick as pivot a number that is in the list case #1 never happens.
Worst case is that you continually pick a number that partitions the list into 2 lists: A list with just one element and a list with $n-1$ elements, if this is the case in each iteration you only rule out a single element.

So first iteration you do $n$ operations, second iteration $n-1$ operations, third one
 $n-2$ operations, ... last iteration 1 operation.

Which its the sum of the first $n$ natural numbers:

$1+2+3+... +(n-2)+(n-1)+ n = n(n-1)/2$ operations = $O(n^2)$


Printing actual solutions for the coin exchange problem As I teach myself dynamic programming, I have learned about the coin exchange problems. Specially this site: https://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/ provides great insight about it. Specifically, the following implementation of a tabulated-DP-based solution for this problems is presented as follows:

def count(S, m, n ):
    # If n is 0 then there is 1
    # solution (do not include any coin)
    if (n == 0):
        return 1
    # If n is less than 0 then no
    # solution exists
    if (n < 0):
        return 0;
    # If there are no coins and n
    # is greater than 0, then no
    # solution exist
    if (m <=0 and n >= 1):
        return 0
    # count is sum of solutions (i)
    # including S[m-1] (ii) excluding S[m-1]
    return count( S, m - 1, n ) + count( S, m, n-S[m-1] );

However, this only counts the number possibles solutions.

Question: How can I actually save these solutions for post-processing?

Previous research: In this very helpful video: https://www.youtube.com/watch?v=ENyox7kNKeY they explain how to use an array of parent pointers, to generate the actual solutions, however, I am having issues with implementing this approach with the previous tabulated solution. Any hint?

Assuming that you want the minimum number of coins to achieve a desired value and that you have a sufficient number of coins of every value we have this relation of recurrence:

Let $S(i,k)$ be the minimum number of coins to achieve the value $k$ considering the first $i$ coins. Also, let $V[i]$ be the value of the $i$-th coin.

So:

$$S(i,k) = \begin{cases}
0 & i = 0 \land k = 0\\
-\infty & i = 0 \land k > 0\\
S(i-1,k) & i > 0 \land V[i-1]-k < 0\\
\max(S(i-1,k),S(i,k-W[i-1])) + 1 & \text{otherwise}
\end{cases}$$

Case 1 = Base case, considering the first 0 coins and the value 0 you pay 0 coins.
Case 2 = Base case, considering the first 0 coins and a value greater than 0 you cant pay the value.
Case 3 = Considering the first $i$ coins you can pick the solution to pay the value $k$ without considering the $i$-th coin, which is in $S(i-1,k)$.
Case 4 = Considering the first $i$ coins, you should maximize between the solutions considering the $i$-th coin and not considering it. If the i-th coin is considered, you increment the number of coins in the solution, because you used the $i$-th coin.

A recursion based solution follows in verbatim from this relation of recurrence, but in Dynamic Programming you will replace a recursive call by a table lookup. So basically, where is $S(a,b)$ you will replace by a table access $S[a,b]$.


Fix two primes p and q. Given input a number of the form $p^aq^b$, find the immediate next number of the same form As stated in the title:
Fix two primes p and q. Given input a number of the form $p^aq^b$, find the immediate next number of the same form.

For example: when $p = 2$ and $q = 3$
Next of $2^2*3=12$ is $2^3=16$ and after that is $2*3^2=18$

Question [edited]:

Can this be done in poly-time of the representation of $a$ and $b$?

I believe so and I do have a sketch for this, but I want to see what a "proper" answer to this question is.

Let $c = \log p$ and $d = \log q$.  Then $\log (p^a q^b) = ca + db$.  Define the set $S_{c,d} = \{ci+dj : i,j \in \mathbb{N}\}$.  Your problem is equivalent to the following:

  Problem 1. Given $a,b \in \mathbb{N}$ and $c,d \in \mathbb{R}$, find $a',b' \in \mathbb{N}$ so that $ca' + db'$ is the next attainable real number in $S_{c,d}$ after $ca + db$.

This is in turn equivalent to the following problem:

  Problem 2. Given $\alpha \in \mathbb{R}$ and $X,Y \in \mathbb{Z}$, find $x,y \in \mathbb{N}$ that minimizes $x+\alpha y$, subject to the requirements that $x \ge X$, $y \ge Y$, and $(x,y) \ne (0,0)$.

(The equivalence can be seen by letting $\alpha = d/c$, $X=-a$, $Y=-b$, and $x=a'-a$, $y=b'-b$.)

Problem 2 now amounts to finding the best rational approximation $x/y$ of $-\alpha$, subject to constraints on the size of $x,y$.  There are many techniques for that, including continued fractions.  You can also express this as the problem of finding a closest lattice point to $(0,0)$ in a certain two-dimensional lattice.  There are many algorithms for closest lattice point search in lattices, also known as the closest vector problem; in two dimensions, I believe they run in polynomial time, if I remember correctly.  See, e.g., https://mathoverflow.net/q/61897.


Given two $a^n b^n$-style languages, how do I find out if their intersection is regular? I have two languages as below.

$$L_1=\{a^ncb^n\}\cup\{a^mdb^{2m}\}$$
$$L_2=\{a^{2n}cb^{2m+1}\}\cup\{a^{2m+1}db^{2n}\}$$

Now, I wonder what is $L_1\cap L_2$. Is it a regular language? Is it context-free?

To solve the problem, I feel like I need to solve the following system of equations, but I'm not sure.

$$
\begin{cases}
2n=2m+1\\
2m+1=\frac{2n}{2}
\end{cases}
$$

$L_1=\{a^ncb^n\}\cup\{a^mdb^{2m}\}$

$L_2=\{a^{2n}cb^{2m+1}\}\cup\{a^{2m+1}db^{2n}\}$

If we say $\;L_1=L_{11}\cup L_{12}\;\:$and$\;L_2=L_{21}\cup L_{22}$

$L_1\cap L_2=((L_{11}\cap L_{21})\cup (L_{12}\cap L_{21}))\cup ((L_{11}\cap L_{22})\cup (L_{12}\cap L_{22})) $

$L_{11}\cap L_{22}\:,\:L_{12}\cap L_{21}\;$will be zero because d and c are different symbols.

So $\;L_1\cap L_2=(L_{11}\cap L_{21})\cup  (L_{12}\cap L_{22}) $

$L_{11}\cap L_{21}=\emptyset \:\;$because it is not possible for an even number to be equal to an odd number.

$\;L_1\cap L_2=L_{12}\cap L_{22}=L=\{a^{2m+1}db^{4m+2}\}$

So the language is not regular but context free. It is impossible to construct a finite automaton for this language because finite automaton has a memory that is fixed and cannot thereafter be expanded. ( It cannot store number of a's ) But it is easy to recognize that L is context free since $L=(a(aa)^*db^*)\cap \{a^ndb^{2n}|n\geq 0\}$ ( intersection of a CFL with a regular language is CFL ) And $ \{a^ndb^{2n}|n\geq 0\} $ is context free because there exists a push-down automaton that accepts L. When this automaton sees an $\:a\:$ it pushes 2 $\:a\:$'s into the stack and when $\:d\:$ is the input it changes it's state to a final state and then for each $\:b\:$ it pops an $\:a\:$ from the stack.


What's flawed about the "save-the-input" method of reversible computing? I'm an undergraduate just beginning to read about reversible computing. I know that, because of Landauer's principle, irreversible computations dissipate heat (and reversible ones do not). I brought it up with my professor, who had never heard of reversible computing before, and he was having difficulty understanding why the theory of reversible computing was not trivial.

His point was just that you can always save the input, i.e. for any function $f: \{ 0, 1 \}^n \rightarrow \{ 0, 1 \}^n$ that you wish to make reversible, define a new function $f_{reversible}: \{ 0, 1 \}^n \rightarrow \{0, 1 \}^{2n}$ (or $\{ 0, 1 \}^{2n} \rightarrow \{0, 1 \}^{2n}$ and you just put $0$s in for the last $n$ bits of the input) which returns the output in the first $n$ bits and the input in the other $n$ bits. Then in order to invert $f_{reversible}$ you just discard the output and return the input that you saved.

My immediate objection was that this takes more memory than the original function did -- though only by a constant factor. Constraining the output to $n$ bits would seem to restore the interesting-ness of the problem, though. Is this what is usually meant by reversible computing?

Another objection seemed to be that when we discard the output, we're doing something irreversible which is going to dissipate heat. But we correctly recovered the initial state, so how could it be irreversible? I don't know enough physics to understand whether the important thing w/r/t heat is just for the entire computation to be reversible, or whether every step needs to be reversible as well, or if this idea is just up the wrong tree.

There are two important features of reversible computing that are missing from your discussion of reversible computing:

A reversible function has to be a bijection, and
Reversibility is defined on the level of local gates, not just the global level.

In particular, for your extension of $\{0,1\}^n \rightarrow \{0,1\}^n$ into $\{0,1\}^{2n} \rightarrow \{0,1\}^{2n}$ by copying, you don't ensure bijection because you don't explain what happens when the last $n$ bits of input for your function aren't $0^n$.

As for the second point, that is really the essential part of reversible-computing from the physics perspective. The physical process can't simply "undo" heating at a global level, thus every gate has to be reversible for the circuit to be reversible in the relevant-to-physics sense.

Finally, the theory of reversible computing is not unreasonably complicated, but it is definitely not trivial. In particular, there are some circuits that can be implemented with strictly fewer registers/wires non-reversibly than they can be reversibly. However, the blow up in going from non-reversible to reversible is not too bad.

In general, I seldom hear reversible computing come up in classical CS courses, because it is seldom relevant to classical computation. However, it is an important topic in quantum computing because all quantum circuits are reversible and because one has to handle what is on your 'junk' wires carefully to avoid unnecessary entanglement.


How to pick a good structural induction hypothesis (Full disclosure: homework question)

Let $M = (Q, \Sigma, q_0, A, \delta)$ be a finite automaton. The extended transition function $\delta^*$ is defined as follows:

$\forall q \in Q$

$\delta^*(q, \Lambda) = q$
$\forall q \in Q, y \in \Sigma^*, \sigma \in \Sigma$

$\delta^*(q, y \sigma) = \delta(\delta^*(q, y), \sigma)$

I am attempting to prove the following statement $\forall x,y \in \Sigma^*$:

$\delta^*(q, xy) = \delta^*(\delta^*(q, x), y)$

It seems pretty obvious from an intuitive standpoint. Since the definition of $\delta^*$ states that for all $y \in \Sigma^*, \sigma \in \Sigma$

$\delta^*(q, y\sigma) = \delta(\delta^*(q, y), \sigma)$

And since the base case of $\delta^*$ is (using $\Lambda$ as the empty string)

$\delta^*(q, \Lambda) = q$

That means $\delta^*(q, y)$ is just a bunch of nested $\delta^*$ applications with the first symbol of $y$ on the innermost application, and the last symbol of $y$ on the outermost application. E.g. if $y = y_1y_2y_3$, then

$\delta^*(q, y) = \delta^*(\delta^*(\delta^*(y_1), y_2), y_3)$

I'm not very experienced at writing proofs, so I'm not sure how to go about setting up the basis case, induction hypothesis, etc. I can prove the first equation for $xy = \Lambda$ as the basis, but I don't know what to do beyond that.

Hint: Prove the identity $\delta^*(q,xy) = \delta^*(\delta^*(q,x),y)$ by induction on $|y|$ (the length of $y$).


Classes of Functions Closed Under Polynomial Composition - Papadimitriou Exercise 7.4.4 I am studying Computation complexity using Papadimitrious's book: "Computational Complexity".
I am trying to do Problem 7.4.4:

"Let $C$ be a class of functions from nonnegative integers to nonnegative integers. We say that $C$ is closed under left polynomial composition if $f(n) \in C$ implies $p(f(n))=O(g(n))$ for some $g(n) \in C$, for all polynomials $p(n)$. We say that $C$ is closed under right polynomial composition if $f(n) \in C$ implies $f(p(n))=O(g(n))$ for some $g(n) \in C$, for all polynomials $p(n)$.
Intuitively, the first closure property implies that the corresponding complexity class is "computational model-independent", that is, it is robust under reasonable changes in the underlying model of computation (from RAM's to Turing machines, to multistring Turing machines, etc.) while closure under right polynomial composition suggests closure under reductions (see the next chapter)."
Which of the following classes of functions are closed under left polynomial composition, and which under right polynomial composition?
(a) - $\{n^k: k > 0 \}$
(b) - $\{k \cdot n: k > 0 \}$
(c) - $\{k^n : k > 0 \}$
(d) - $\{2^{n^k} : k > 0 \}$
(e) - $\{\log^k n: k > 0 \}$
(f) - $\{\log n\}$

After understanding the definition of closed under left/right polynomial composition, I think I was able to solve items (a), (b), (c) and (f). However, I was not able to solve items (d) and (e).
My solution for item (a):

Closed Under Left Polynomial Composition: consider an arbitrary $f(n) \in C$ and an arbitrary polynomial $p(n)$. Then, $f(n)$ is of the form $n^{k'}$, for some $k' > 0$ and therefore $p(f(n))$ is a polynomial. Let $k''$ be the degree of the polynomial $p(f(n))$. Take $g(n) = n^{k''} \in C$ and we have $p(f(n)) = O(g(n))$.
Closed Under Right Polynomial Composition: same reasoning.

My solution for item (b):

Not Closed Under Left Polynomial Composition: consider as a counterexample $f(n) = n \in C$ and $p(n) = n^2$. Then, $p(f(n)) = n^2$. For every $g(n) = k n \in C$ we have $O(g(n)) = O(n)$. Since $n^2 \neq O(n)$ we conclude.
Not Closed Under Right Polynomial Composition: the previous counterexample applies.

My solution for item (c):

Closed Under Left Polynomial Composition: Consider an arbitrary $f(n) = k_1^n$ and a polynomial $p(n)$. Notice that $p(f(n))$ is a polynomial in $k_1^n$. For sufficiently large $n$, there exists some $k_2$ such that $p(n) \leq n^{k_2}$ and therefore $p(f(n)) \leq [f(n)]^{k_2} = (k_1^{n})^{k_2} = (k_1^{k_2})^n$. Therefore, taking $g(n) = (k_1^{k_2})^n \in C$ we obtain that $p(f(n)) = O(g(n))$.
Not Closed Under Right Polynomial Composition: Consider as a counterexample $f(n) = 2^n$ and $p(n) = n^2$. Then, $f(p(n)) = 2^{n^2}$, which is greater than $g(n) = k^n$, for every fixed value of $k$, if $n$ is sufficiently large. Therefore, $f(p(n)) \not \in O(g(n))$.

My solution for (f):

Not Closed Under Left Polynomial Composition: Consider as a counterexample $f(n) = \log n$ and $p(n) = n^2$. Then, $p(f(n)) = \log^2 n$. Also, $g(n) \in C$ implies that $g(n) = O(\log n)$. We have $\log^2 n \not \in O(\log n)$.
Closed Under Right Polynomial Composition: If $f(n) \in C$ then $f(n) = \log n$. Given an arbitrary polynomial $p(n)$, we have that there exists some $k'$ such that, for sufficiently large $n$, $p(n) < n^{k'}$. Then, for sufficiently large $n$:
$ f(p(n)) \leq f(n^{k'}) = \log n^{k'} = k' \log n = O(\log n) = O(g(n)).$

Can anyone help me with items (d) and (e)?
Thanks in advance. Of course, corrections/comments on the other items are also welcomed.

For item (d):

Closed under left polynomial composition: Consider an arbitrary $f(n) = 2^{n^{k_1}} \in C$ and an arbitrary polynomial $p(n)$. There exists some $k_2$ such that $p(n) \leq n^{k_2}$, for sufficiently large $n$. For sufficiently large $n$, $p(f(n)) \leq [f(n)]^{k_2} = [2^{n^{k_1}}]^{k_2} = 2^{k_2 n^{k_1}}$. There exists $k_3$ such that $2^{k_2 n^{k_1}} < 2^{n^{k_3}}$ for sufficiently large $n$. Therefore, choosing $g(n) = 2^{n^{k_3}} \in C$ we have $p(f(n)) = O(g(n))$.
Closed under right polynomial composition: Consider an arbitrary $f(n) = 2^{n^{k_1}} \in C$ and an arbitrary polynomial $p(n)$. There exists some $k_2$ such that $p(n) \leq n^{k_2}$, for sufficiently large $n$. For sufficiently large $n$, $f(p(n)) = 2^{[p(n)]^{k_1}} \leq 2^{(n^{k_2})^{k_1}} = 2^{(n^{k_2 k_1})}$. Therefore, taking $g(n) = 2^{(n^{k_2 k_1})} \in C$ we obtain that $f(p(n)) = O(g(n))$.

For item (e):

Closed under left polynomial composition: Consider an arbitrary $f(n) = \log^{k_1} n$ and an arbitrary polynomial $p(n)$. Then, exists some $k_2$ such that $p(n) \leq n^{k_2}$, for sufficiently large $n$. Therefore, for sufficiently large $n$, $p(f(n)) \leq f(n)^{k_2} = (\log^{k_1} n)^{k_2} = \log^{k_1 k_2} n$. Choosing $g(n) = \log^{k_1 k_2} n$ we have $p(f(n)) = O(g(n))$.
Closed under right polynomial composition: Consider an arbitrary $f(n) = \log^{k_1} n$ and an arbitrary polynomial $p(n)$. Then, exists some $k_2$ such that $p(n) \leq n^{k_2}$, for sufficiently large $n$. Take $g(n) = \log^{k_1} n$. We have, for sufficiently large $n$:
$ f(p(n)) = \log^{k_1} p(n) \leq \log^{k_1} (n^{k_2}) =
 (k_2 \log n)^{k_1} = {k_2}^{k_1} \log n^{k_1} = O(\log n^{k_1}) = O(g(n))$.


Lamarckian and Genetic algorithm Yesterday I've done some research how to optimize genetic algorithm and I've encountered a very interesting theory that we can use Lamarckian theory (adaptive theory) to optimize the neural network. But I still didn't understand how can it be done? What I've read from some source to optimize the genetic algorithm we must do some adaptation to the parents before we do the mating (crossover & mutation) but how is exactly the adaptation done? For example, if I have a genetic algorithm population to train a neural network, how can I alter the chromosome of the population to be adapted to the environment? Is it based on the error of the output or how?

In fact, you're talking about Memetic Algorithms. In the case of a neural network, supposing you have training samples, the individual learning may be done through an iteration of backpropagation. If you don't have training examples, you may apply some noise to the weights and keep the modification only if it performs better (hill climbing). Actually, any local search algorithm could be used.
Regarding the frequency of individual adaptation, this is currently a research topic, but you can find works that suggest applying the adaptation to all individuals at every generation as well as other works suggesting to increase this frequency gradually, since the last generations are the ones which need more fine tuning. Genetic algorithms are very good to find some good global solution, while local search is very good to find the optimal local solution. So the trick is to find the optimal solution region with GA and fine tune with local search.


How to prove the existence of a number which cannot be written by any algorithm? I have the problem:

  Show that there exists a real number for which no program exists
  that runs infinitely long and writes that number's decimal
  digits.

I suppose it can be solved by reducing it to the Halting problem, but I have no idea how to do so.

I would also appreciate links to similar problems for further practice.

As Sebastian indicates, there are only (infintely but) countably many programs. List them to create a list of programs. The list is (infinitely but) countably long. Each program generates one number in R. From that we can create an (infinite but) countable list of numbers in R. Now we can apply Cantor's diagonal argument directly to prove that there still must be other numbers.

By the way if the algorithm has (finite) arguments, you can just rewrite that as a "longer" list of programs where each program doesn't have any arguments.

With regard to your comment "What if real numbers are allowed as argument", then the question's premise is wrong: all numbers in R can then be generated. If someone finds a number, say 皮 and claims it cannot be computed, we have the following "algorithm":

func(number):
    return number

and call func(皮)


Maximum connected cell length containing two different numbers Suppose we are given an $n\times m$ matrix $M$ of positive integers. The adjacent cells of a particular cell is the up, down, left and right cells. Like for cell $M[i][j]$ the adjacent cells are $M[i-1][j]$, $M[i+1][j]$, $M[i][j-1]$ and $M[i][j+1]$ respectively.

An area is a set of cells such that for each pair of cells $(u_0,v)$ in the area, there is a sequence of cells $u_1,\ldots,u_k$ in the area such that $u_{i+1}$ is an adjacent cell of $u_i$ and $u_k$ is an adjacent cell of $v$. The problem is to find out a maximum area (i.e. an area with maximum number of cells) of this matrix which contains exactly two different numbers.

For an example: $$M=\begin{bmatrix}5&3&2&5&5\\2&1&2&5&3\\6&1&5&2&5\\5&2&5&3&5\\4&6&8&9&6\end{bmatrix},$$
Here the maximum area contains 10 cells. And the area is:
$$\begin{bmatrix}*&*&2&5&5\\*&*&2&5&*\\*&*&5&2&*\\5&2&5&*&*\\*&*&*&*&*\end{bmatrix}.$$
What is the most efficient way to find the maximum area?

First you can transform the matrix to a graph, where every maximal area containing the same integer is transformed to a vertex with a weight that is the number of cells in the area, and there is an edge between two vertices iff the two corresponding areas are adjacent, that is, there is a cell in one area that is adjacent to at least one cell in the other area. Therefore, the matrix in your example is transformed to

5 - 3 - 2 - 5
|   | / |   | \
2 - 1   |   |   3
| / | \ |   |   |
6   |   5 - 2 - 5
|   | / | \ | / |
5 - 2   |   3   |
|   |   |   |   |
4 - 6 - 8 - 9 - 6

Now the problem turns out to be finding the connected subgraph with maximum sum of weights such that it contains exactly two integers. This transformation can be done in $O(mn)$ time.

Next, run the following algorithm:

maxS := empty set
While True:
    Search the next edge (u,v) that is not used
    If not found:
        return maxS
    Let x,y be the integers contained in u,v respectively
    (#) Do BFS from u where only edges between vertices containing x,y respectively are considered
    Mark all edges found during the BFS as used
    S := the set of vertices found during the BFS
    If the sum of weights in S > the sum of weights in maxS
        maxS := S

Note the (#) line, this algorithm requires us to, given a vertex containing integer x, efficiently find all its neighbors (as well as edges) containing y. You can sort all the neighbors for all vertices in advance, which takes $O(\sum_v n_v\log n_v)=O(mn\log(mn))$ time ($n_v$ is the number of neighbors of vertex $v$). Now compared to normal BFS, it takes extra $O(\log n_v)$ time for each vertex $v$.

Basically, each BFS induces a maximal connected subgraph containing exactly two integers. This algorithm checks all such subgraphs and choose the optimal one. Note each edge belongs to only one such subgraph and each vertex $v$ belongs to $t_v$ such subgraphs ($t_v$ is the number of distinct integers among all neighbors of $v$), the time complexity of this algorithm is

$$O\left(mn+\sum_vt_v\log n_v\right)=O\left(mn\log(mn)\right).$$


When it is said an algorithm runs in exponential time, is it meant it has complexity $O(2^n)$, or $2^{O(n)}$? Also, are they equivalent or are they different?

Examples of algorithms/Turing Machines that run in complexity of one but not the other would be much appreciated.

Beware the abuse of notation; I can not recommend using "$2^{O(n)}$".

That said, a common interpretation is using the placeholder semantic. That is, we read

$\qquad\displaystyle f \in 2^{O(n)} \quad"\iff"\quad \exists\, g \in O(n).\ f \in O(2^{g(n)})$

Compare that to the definition of $O(2^n)$ and you'll quickly see that the two are not the same.

   Because $2^{cn} = (2^c)^n$, the term "$2^{O(n)}$" covers all exponentially bounded functions, i.e. the union of all $O(a^n)$; use $c = \log_2 a$.

Your titular question should answer itself now.

   Since $3^n \not\in O(2^n)$, this Landau class does not cover all exponential function. This is easy to show independently of above discussion, by the way.

Note how the "definition" makes two $O$ out of one; that's why I think that notation is bad. See also this related question where is becomes clear that even experts don't agree on what the notation should mean here, exactly. Here's another related question.


How many bits are needed? Advantages/disatvantages of this configuration? So the question is:

Assume we had 15 CPU instructions and, for each instruction, we were trusting one particular component of the kernel to handle it. How many modes do we need to support (including the user mode), and how many bits we had to use to represent these modes? What is an advantage and a disadvantage of using this scheme instead of the kernel/user mode scheme, where one kernel component is trusted to handle all 15 instructions?

Is it 16 modes (1 kernel mode for each component, then the 1 user mode) or is it just the regular 2 modes?

Would it be 4 or 1 bit(s) for 16 modes or 2 modes respectively?

I want to say an advantage are that 15 components would be more powerful, but I feel like I should be able to explain more.
I think a disadvantage would be power and memory allocation.

Is that somewhat in the right direction?

for each instruction, we were trusting one particular component of the kernel to handle it

This seems to represent a misunderstanding of how code is executed.  That's not how CPUs work.  Instructions are executed by the CPU -- not handled by the kernel.  So, the question seems to be based on a faulty premise.

(OK, there are sometimes occasional exceptions to this in real-world architectures -- e.g., in old x86 platforms, some floating-point instructions might be emulated by the kernel when running on a CPU that didn't have floating-point support -- but that's a detail.  Treat what I've described above as the basic rule.)


Chinese room test vs Turing Test So, I took up a new course (AI) in my uni and came across these two test
$TURING$ $TEST$ and $CHINESE$ $ROOM$ $TEST$. But I am not able to understand is the Chinese room test really accurate? Does it really dis-approve the TURING test?

The Turing test and Searle's Chinese Room argument represent two alternative definitions of intelligence.

The Turing test is based on the assumption that intelligence is difficult to formally define but can be easily recognised by behavior. So if a computer program behaves and interacts in a way that is practically indistinguishable from the behavior of human being (who we assume is "intelligent") then, based on this assumption, we should say that the computer program is also intelligent. In the Turing test, the particular behavior that is tested is holding a conversation in natural language.

Searle's Chinese Room argument is a challenge to the validity of the Turing test. It posits a complex system that behaves as if it were intelligent (in this case, holding a conversation in Chinese), but in which each component of the system follows an algorithm, and so no part of the system can be said to "understand" Chinese. The Chinese Room argument is based on the assumption that the system as a whole cannot be said to be intelligent unless some of its individual components are intelligent - it is essentially a reductionist argument.

In summary, the Chinese Room argument says that its is possible for a system to simulate intelligence without actually being intelligent. Whereas the Turing test is says that if a system can simulate intelligence then it actually is intelligent.

We can illustrate the difference between the two points of view with an analogy as follows. The Turing test would say that an aeroplane flies because it travels through the air from one place to another - it exhibits "flying" behavior. The Chinese room argument would say that an aeroplane only simulates flight because it does not flap its wings.


binary code to encode binary tree I would like to encode a binary tree where every node has either 0 or 2 kids into a binary word.

I was thinking about marking every left edge with a "0" and every right edge with a "1"
and then use every path from root to a leaf concatenated to encode the tree, but I'm not sure if this results in a unique code for every tree?

I thought about it for quite some time but I can not figure out... maybe you know?

First of all, let's consider that we are talking about labeled trees. Otherwise it will be difficult to find bijection between trees and binary strings.

Then we can traverse a given tree in-order (https://en.wikipedia.org/wiki/Tree_traversal#In-order_(LNR)) and print $1$ each time, when we enter some vertex, and $0$ each time, when we leave some vertex.

Another possible encoding can be constructed in the following way. Let's enumerate all vertices by layers from root to bottom (and from left to right inside each layer). And then let's construct binary string of length $|V|$ where the $i$-th position is $1$ if the corresponding vertex has children and $0$ otherwise.


Using the pumping theorem to show that this language is not context-free Let $\sigma = \{a,b,c\}$ and let $L = \{s | s = a^jb^jc^k\}$ where $k=i\cdot j$ and $i,j \geq 0\}$. Using the pumping theorem, prove that $L$ is not context-free.
I really don't know where to start, here. Nobody in the class knows what to do and we're all failing pre-curve.

Suppose that $L$ is context-free. Then the pumping lemma for context-free languages tells us that $L$ has a pumping length $p \ge 1$. We want to show that this leads to a contradiction, by exhibiting a string that is in $L$ but cannot be pumped in the manner specified in the lemma.

Consider the string $s = a^pb^pc^{(p^2)}$. Clearly, $s \in L$.

Now, see if you can show that all the possible ways of breaking down this string into the chunks specified in the lemma lead to a pumped string that is not in $L$.


A framework to capture common variation of sequence alignments The global alignment problem can be generalized by setting the cost of some boundary gaps to 0.

Gaps at both end in both strings have 0 cost, then we get the semiglobal alignment.
Gaps are at the left end of the first string, and right end of second string have 0 cost, then we get overlap alignment.
If both boundary gaps for the second string has no cost, we get the fitting alignment.

But this can't capture local alignment. Seems strange to let the local alignment to be the odd man out, are there a general (but not too general) framework that captures all the above alignment problems?

Despite the different uses of the algoritms, and the various names, I personally would say this is a single algorithm, with different variations. To make this answer more readable, I will add some details.

The basic algoritm global alignment (aka Needleman-Wunsch, below left) compares two strings $x=x_1\dots x_m$ and $y = y_1 \dots y_n$ (with match/mismatch score $\sigma$ between letters and negative gap cost $g$ between letter and missing letter). It is computed using an array $A$ and the recursion $$A[i,j] = \max \left\{\begin{array}{lll}A[i,j-1]&+&g\\A[i-1,j-1]&+&\sigma(x_i,y_j)\\A[i-1,j]&+&g\end{array}\right.$$
The starting values along the borders of the matrix are $A[i,0]=i\cdot g$ and $A[0,j]=j\cdot g$.

The value of the alignment is found in the last cell of the computation, and the alignment itself can be found by tracing back how this maximum value is obtained.

For local alignment (aka Smith-Waterman, below right) we need not a complete match but only the optimal value of matches between substrings of $x$ and $y$. That can be obtained by considering only part of the 'full' computation, ignoring any prefix or suffix with a negative value. This requires two changes. First any negative value obtained by the basic recursion is set to $0$, and also we look for a maximum inside the matrix (not the last cell). As any negative values are set to $0$ this effects the boundary values in the same way: they are set to $0$.

The three variants of semi-global alignment you mention (including overlap and fitting alignment) are somewhat in the middle of these two, as they carefully select which prefixes and suffixes do not count towards cost. They each follow the basic recursion (allowing negative values). Such alignments follow a path from one border of the matrix to another one. Starting at a left or top border means ignoring prefixes, and setting the corresponding border to $0$. Ending at a right or bottom border (i.e. choosing the maximum value at that side) corresponds to ignoring that suffix.

The two pictures below represent overlap and containment/fitting.


How do I prove that a language is deletion closed? For example, how could I prove that the following language is deletion closed:

{$a^k$$b^j$ : $j$, $k$ $\geqslant$ 0}

The reason seems obvious to me, I just can't see a way to prove it.

You'd prove that a language $L$ is deletion-closed as follows.

Consider a word $w\in L$ and let $w = w_1\dots w_\ell$.  Now, for any $r$ and $s$ with $1\leq r\leq s\leq \ell$, consider the word $w' = w_1\dots w_{r-1}w_{s+1}\dots w_\ell$, i.e., the word that results from deleting the substring $w_r\dots w_s$ from $w$. We have $w'\in L$ because [some argument that will be specific to the language $L$ you're working with].


Finding all paths from s to t in linear time I was looking at the following algorithm which prints all the paths from node s to node t and I have some questions I don't understand

The basic idea is :

DFS-Visit(s)
Change current status to "currently visiting"
If neighbor is t -> print the path (from the stack trace or any way)
If not: DFS-Visit on neighbors
When done visiting neighbors: change status to "not-visited yet"

It seems like it's run-time is exponential, however - could I use the memorization technique like in dynamic programming to turn this into linear time ? since a lot of calculations are repeating

The example given in the algorithm is a DAG, but I couldn't find an regular graph that makes this algorithm fail.

It seems highly unlikely that this algorithm is possible in linear time on a regular graph... Wouldn't that help me to calculate shortest path from s to t in linear time ?

The algorithm you describe cannot possibly be linear time for a DAG or general graph. Consider the following DAG on $n$ vertices $V = \{v_1, v_2, \ldots v_n\}$. Take a particular node $v_i$, for all $j > i$ add an edge $(v_i, v_j)$. This will create $\Theta(n^2)$ edges in this DAG. Note that a path from $v_1$ to $v_n$ can use any subset of nodes $\{v_2, v_3, \ldots v_{n-1}\}$. That is to say there are $2^{n-2}$ possible paths from $v_1$ to $v_n$. Clearly to print all these would take exponential time.

What you can do in linear time, is determine the subgraph that would contain all possible paths from $s$ to $t$. With a source $s$ in mind, we first check if it can reach $t$ (via DFS), if not then return an empty subgraph. Otherwise we check if $s$'s children $\{v_1, v_2, \ldots\}$ can reach $t$, this can be done recursively top-down or bottom-up if we start at $t$ and work backwards. Let's say $A$ is the set of nodes who are a descendant of $s$ and an ancestor of $t$. $A$ will also include $s$ and $t$ for obvious reasons. The subgraph we are interested will contain exactly the vertices in $A$. With this we can iterate through edges an include them as necessary, or we could even pick up edges long the way as we are determining which nodes are in $A$. This procedure overall will take $O(n + m)$. Of course, this is only interesting in a DAG unless $t$ or $s$ is an articulation point.


Complexity of testing if a number is a primorial For the $n$-th prime number $p_n$ the primorial $p_n\#$ is defined as the product of the first $n$ primes.

What is the complexity of testing if a given number $n$ is a primorial?
Is it related in some way to the FACTORING problem?

This is simpler than factoring.  You can simply multiply all prime numbers up to the point where you (a) reach $p_n$ or (b) get a product which is larger than $p_n$.  In the first case, you answer yes otherwise you answer no.

The reason it is simpler is that the prime factorization is trivial, whereas in the FACTORING problem, you don't know how many of each prime number you need.


Show that NP is closed under concatenation Show that NP is closed under concatenation.

This is a homework problem and I would appreciate some guidance. I began by saying the following:

Let $A$ and $B$ exist in NP. Let $V_1$ and $V_2$ be verifiers for $A$ and $B$, respectively.

Is it as simple as saying build two NTMs $M_1$ and $M_2$ that decide $A$ and $B$ and then concatenate them and build a new machine to decide?

The easiest way to prove that NP is closed under concatenation is the following:

Assume that $L_1 , L_2 \in NP$. Thus, there are two nondeterministic deciders $M_1$ and $M_2$ such that $M_1$ decides $L_1$ in nondeterministic time $O(n^l)$ and $M_2$ decides $L_2$ in nondeterministic time $O(n^k)$.
Let $M$ a TM s.t.

  $M$ on input $w$:

  Split $w$ into $w_1 \in L_1$ and $w_2 \in L_2$ s.t. $w = w_1 w_2$;
  Run $M_1$ on $w_1$. If $M_1$ rejects then reject;
  Else run $M_2$ on $w_2$, if $M_2$ rejects then reject;
  Else accept.

This will use $O(n^{\max{l,k}})$ steps. So $M$ is a polytime nondeterministic decider for $L_1L_2$.


How do search engines efficiently retrieve documents in a sorted (e.g. page rank) order from an already sorted (by document id) inverted index? The standard way a search engine retrieves documents is by using an inverse index from words in the query to document ids. Since the ids are sorted, a query like "word1 AND word2" would fetch the lists of document ids two for word1 and word2, and find the intersection in linear time (similar to merge in merge sort).

But how would the search engine efficiently retrieve documents in some specified order , like page rank for example? Since the inverse indices for each word are already sorted by document id (to enable the merging described above), there seems to be no way to sort them also by page rank. (For instance, for "word1" the index might have ids :  5, 11, 19 where these documents have page ranks 3, 1, 2 respectively).

Retrieving the documents by document id first and then sorting by page rank at query time can be impractical if the number of documents to sort is large (say, millions), and especially if the user just wants the top page or two.

I don't know what search engines actually do, but one approach would be sort by decreasing pagerank, resolving ties using the document ID.  (In other words, the primary sorting key is the page rank, and the secondary sorting key is the document ID.)

This still allows the merge operation.  It also ensures that results are generated in decreasing pagerank order, i.e., the top-ranked results are generated first.  Note that if two documents have the same document ID, then they'll definitely have the same pagerank, too, which is why this approach works.


About hardware multithreading I'm reading Multithreading (computer architecture) - Wiki, aka hardware threading, and I'm trying to understand the second paragraph:

  (p2): Where multiprocessing systems include multiple complete processing units in one or more cores, multithreading aims to increase utilization of a single core by using thread-level parallelism, as well as instruction-level parallelism.

while the link to thread-level parallelism says:

  (Link): Thread-level parallelism (TLP) is the parallelism inherent in an application that runs multiple threads at once. This type of parallelism is found largely in applications written for commercial servers such as ...

which is not so useful... So I read task parallelism above, since I guess TLP is a subtype of it:

  Task parallelism (also known as function parallelism and control parallelism) is a form of parallelization of computer code across multiple processors in parallel computing environments. Task parallelism focuses on distributing tasks—concurrently performed by processes or threads—across different processors.

Question: If thread-level parallelism is task parallelism, and task parallelism is for parallelization across multiple processors, how increase utilization of a single core by thread-level parallelism work?

Guessing: I guess for TLP, it should mean across multiple logical processors, i.e. hardware threads in the perspective of OS, correct?

Another minor issue is that for my first link, Multithreading:

  In computer architecture, multithreading is the ability of a central processing unit (CPU) (or a single core in a multi-core processor) to execute multiple processes or threads concurrently, supported by the operating system.

And in (p2) it aim to increase utilization of a single core by using thread-level parallelism? What a contradiction.

It may be helpful to show the motivation for this kind of parallelism.

Compared to other components (such as memory access), computation, especially adding/subtraction, is cheap on chips. It takes very little space, relatively, to add another adder - and of course that adder could be used for address calculations as well as for actual arithmetic.

So more ALUs are easy to add. The problem is how to keep them busy. For instance, if you are calculating A+B+C then you need to work out A+B first and then add C to it. Nothing useful can be done with C until you have worked out A+B. So two ALUs don’t help and one is idle.

There is a lot that a CPU can do in terms of sorting out what calculation depends on what data. If a compiler emits code for “add A to B, store in X, add C to D, store in Y, add X to Y” then the chip itself can work out that the first two adds are independent of each other so can be executed simultaneously by two ALUs (but that the third add depends on the results of the first two).

But in many instruction streams there isn’t enough scope for such parallelism, because of the problem of having to wait for results. This is particularly annoying when memory access is involved because memory today is hundreds of times slower than it was in the 1980s, so there are long periods when everything may be idle waiting for memory data to arrive.

The hyper-threading solution is to run two unrelated instruction streams on the same core at the same time. Since they are unrelated, the data for one never depend on a result from the other, and while one is waiting for memory there is a good chance that the other will not be. The main cost is a doubling of the number of registers (one set of registers per instruction stream) but that is silicon area, not long-distance wiring, so it is cheap.

The threads in a core still share the same memory access mechanism, including the cache, so how well all this works does depend on what the instruction streams are doing. If they are both memory-intensive then they will get in each other’s way.

The term “multithreading” is incorrect for this kind of setup because multithreading means any way of accomplishing a goal by means of multiple threads, irrespective of the actual bits of hardware that execute the threads.


Confusion about the definition of the average-case running time of algorithms In this lecture note,

  The average-case running time is defined by the expected value, over all inputs $X$ of a certain size, of the algorithm's running time for $X$:
  $$T_{\text{average-case}}(n) = E_{|X| = n}[T(X)] = \sum_{|X| = n} T(X) \cdot Pr[X].$$

This wiki article (Quicksort) gives an average-case time complexity analysis for Quicksort:

  When the input is a random permutation, the rank of the pivot is uniform random from $0$ to $n − 1$. Then the resulting parts of the partition have sizes $i$ and $n − i − 1$, and $i$ is uniform random from $0$ to $n − 1$. So, averaging over all possible splits and noting that the number of comparisons for the partition is $n − 1$, the average number of comparisons over all permutations of the input sequence can be estimated accurately by solving the recurrence relation:
  $$C(n) = n - 1 + \frac{1}{n} \sum_{i=0}^{n-1} (C(i)+C(n-i-1)).$$

My confusion is how does the average-case analysis for Quicksort fit the definition above? First, I would expect a term $\frac{1}{n!}$ (which is $Pr[X]$) in the recurrence. But, it is not the case. Second, the analysis above is on a random permutation and the averaging is done over all possible splits. How is this related to averaging over all possible inputs? Do I need another definition for average-case running time?

The definition is a special case of a more general notion. Given probability distributions $\mu_1,\mu_2,\ldots$ on inputs, the average running time (with respect to the $\mu_i$) is defined as
$$
\newcommand{\Tavg}{T_{\mathit{avg}}}
\newcommand{\EE}{\mathbb{E}}
\Tavg(n) = \sideset{\EE}{}{}_{X \sim \mu_n} [T(X)].
$$
Usually $\mu_n$ is supported on inputs of "length" $n$, though length is not necessarily measured in bits or in machine words.

When analyzing comparison-based sorting algorithms, usually $\mu_n$ is chosen as the uniform distribution over all permutations of the array $1,2,\ldots,n$ (or any other array consisting of $n$ distinct comparable elements). The analysis of quicksort uses these distributions.

Now regarding the recursive formula you mention. Given an input array $X$, let $I$ be the rank of the pivot; if $X$ is a random variable, then so is $I$. The formula in Wikipedia is
$$
\Tavg(n) = \sum_{i=0}^{n-1} \Pr[I=i] \EE[T(X)|I=i] = \sum_{i=0}^{n-1} \frac{1}{n} \left[n-1 + \Tavg(i) + \Tavg(n-1-i)\right].
$$
Rearranging gives you the quoted formula.


Information-theoretic limits for a weighing puzzle Consider the following problem:

You are given $n$ coins with labels $1, \ldots, n$. You know that coins have weights $1, \ldots, n$, but you don't know whether the labels are correct (i.e. they can be in a different order). Using balance scales (the outcomes are $>$, $=$ or $<$) at most $k$ times, determine whether the labels are correct.

I'm not exactly interested in how to solve the problem: the original problem was for $n=6$ and $k=2$, and I know solutions. What I'm interested in is the following: when I heard the problem, I first tried to determine whether a solution even exists from the information-theoretic standpoint. I.e. is the amount of information revealed by $k$ weighings even potentially enough? I don't know how to approach it.
For example, for $n=6$ and $k=2$ there exist $2$ solutions:

 compare $1,2,3$ with $6$ and then compare $3,5$ with $1,6$
 compare $1,3$ with $5$ and then compare $1,2,5$ with $3,6$

But if we estimate the amount of information naively, then we conclude that with $2$ weighings we can only distinguish $3^k=9$ permutations, which is much less than required $6!$.

You don't need to distinguish n! permutations. You only need to decide whether you have one particular permutation or not.
You start with a set of n! possible permutation. Then you make a measurement, and some permutations in that set are compatible with your measurement, and some are not. So you replace the set of permutations with one that is compatible with your measurement.
For sorting, your measurement is a comparison of two elements. What you need to achieve is that no matter what the outcome is, you are finally left with a set containing one permutation only. To achieve this, you will try to find a comparison that splits your set into two halves that are as close together in size as possible, in case the outcome of the comparison leaves you with the bigger set.
For your problem, you just need to decide whether the permutation (1, 2, 3, ..., n) is in the set of permutations compatible with your measurements or not. You will therefore make a measurement where one of the two possible outcomes means that (1, 2, 3, ..., n) is in your set, and as few other permutations as possible. So you want to split the set as unevenly as possible.
That's what you did. Comparing (1, 2, 3) against 6 means that only twelve permutations including the perfectly ordered one will be compatible with the result: (1, 2, 3) can be ordered in six ways, and (4, 5) can be ordered in two ways. If the comparison is not equal, then there are 708 permutations compatible with that, but that is fine since you have your answer.
Obviously each coin except one must be part of some weighing (if you leave out two coins you can't know if they are in the right order). If you had a limit like "at most four coins can be weighed" that would give you a lower bound. Since you are allowed to weigh all coins in one measurement you'd have to come up with something more clever to find a useful lower bound.


In Strassen's algorithm, why does padding the matrices with zeros not affect the asymptopic complexity? In Strassen's algorithm, why does padding the matrices with zeros, in order to multiply matrices that are not powers of 2, not affect the asymptopic complexity?
Hi, I was reading this question but I do not follow Yuval Filmus's answer completely.
He offers two ways of padding the matrix with zeroes, I am interested in his first suggestion, padding the entire matrix with zeroes at the start such that the new matrix has dimensions $N\times N$ where $N = 2^c$.
He says "$N < 2n$ so this doesn't affect the asymptotic complexity."
Could someone please elaborate as I do not follow, I understand calculating time complexity with the master theorem and $T(n) = aT(n/b) + f(n)$ so if someone could explain how this works in reference to that it would be greatly appreciated.

Suppose that if $N = 2^c$ then you can multiply two $N \times N$ matrices in time $O(N^{\log_2 7})$. For concreteness, let us say that two such matrices can be multiplied in time at most $CN^{\log_27}$.
Now suppose that we are given two $n\times n$ matrices. We pad them to $N \times N$ matrices, where $N = 2^{\lceil \log_2 n \rceil} < 2n$. We can extract the product of the original matrices from the product of the new matrices. The two new matrices can be multiplied using at most this many operations:
$$
CN^{\log_2 7} < C (2n)^{\log_2 7} = 7C n^{\log_2 7} = O(n^{\log_2 7}).
$$


Distance query in trees with integer edge weights (Constant time, linear space) Consider an unrooted tree with integer edge weights. I'm looking for a linear space data structure which allows for constant time distance queries (finding the distance, i.e. the sum of edge weights, between any two vertices).

Is this possible? If yes, how? I have an idea that it should be possible using some Lowest-Common-Ancestor or Range-Minimum-Query approach.

Pick an arbitrary node to be the root.  Store in each node its depth (distance from the root).  Also, build a least-common ancestor data structure so you can answer least-common ancestor queries in constant time.

Given two vertices $u,v$, compute their least common ancestor, $a$.  Now the shortest path from $u$ to $v$ goes up from $u$ to $a$, then down to $v$.  You can compute the length of this path as

$$(\text{depth}(u)-\text{depth}(a)) + (\text{depth}(v) - \text{depth}(a)).$$

That's the distance from $u$ to $v$.  Total running time is $O(1)$ time per query.  There exist LCA data structures that use only linear space.


Is there a clear definition of "computable" for models of computation which are not turing complete? This is a follow-up of another question here, and I hope it is not too philosophical. As Raphael pointed out in a comment on my previous question, I don't really get the definition of "computable", but according to some papers I read, the definition is also not really clear when it comes to models of computation weaker than turing machines because of the encoding of the input and output.

The typical definition of turing computable is as follows:

  Definition 1: A function $f : \mathbb{N}^k \to \mathbb{N}$ is called turing computable iff there is a turing machine $M$ which computes $f$ using a suitable encoding of the natural numbers as strings.

The definitions differ in what exactly is a suitable encoding is, but most refer to binary encoding, unary encoding or decimal encoding as the one fixed and suitable encoding. It is also possible to show that fixing one encoding is required for the definition of turing computability. But what makes, say, binary encoding of natural numbers special so that we can axiomatize it as the one suitable encoding? Probably because it fits the intuitive notion of what computability means coincidentally.

Now what if we look at weaker models of computation than turing machines? For example, let's consider the set $M_c$ of "crippled" turing machines with the alphabet $\{0,1\}$ which may only move to the right, and a definition of crippled turing computable which is consistent with that of turing computability:

  Definition 2: A function $f : \mathbb{N}^k \to \mathbb{N}$ is called crippled turing computable or computable in $M_c$ iff there is a crippled turing machine $M$ which computes $f$ using a suitable encoding of the natural numbers as a string.

If we define "suitable encoding" as "binary encoding", then the function $f : \mathbb{N} \to \mathbb{N}, n \mapsto n+1$ is not computable in $M_c$. If we axiomatize "suitable encoding" as "unary encoding", then $f$ is computable in $M_c$. This seems awkward given the fact that everyone may fix one of the infinitely many intuitive encodings at will. It should be clear if a computation model can compute $f$ or not without referring to some specific encoding - at least I have never seen anyone mention what encoding is used when stating "loop programs are weaker than turing machines".

After this introduction I can finally phrase my question: How would one define "suitable encodings" and "computability" for arbitrary models of computation which do not coincide with the intuitive notion of computability? Is this possible within the framework of turing computability?

Edit: I shortened the introduction, it didn't add to the question.

Some basic fact that you are missing here is that all the encodings that you mention are equivalent from the perspective of computability: there is a computable function mapping the binary encoding of a number to its unary encoding, or vice versa. Therefore for the sake of defining computability, it does not matter which of these encodings you choose for numbers. Just fix your favorite encoding.

Computability is at its core a property of string functions $f\colon \Sigma^* \to \Sigma^*$. When you define computability in any other domain, you have to fix an encoding. In practice, all "reasonable" encodings are equivalent in the sense of the preceding paragraph, so the exact encoding doesn't matter.

The encoding does, however, matter in restricted models of computation. To take an extreme example, suppose that you consider time-restricted Turing machines: say you want your machine to terminate in time $O(n^c)$ for some $c$, where $n$ is the length of the input (as a string). We can no longer switch between binary encoding and unary encoding, because binary encoding is much more compact. When we talk about a polynomial time computable function of integers, we specify that integers are encoded in binary. Even this is a somewhat arbitrary choice, since decimal encoding would lead to the same notion of polynomial time computability.

So to answer your question – the encoding is specified as part of the definition of the restricted model.