Why do we need double-rotations to rebalance AVL trees? I was reading about AVL tree rebalancing from Behrouz Forouzan's book. The book first defines Left High and Right High tree:

  Left High (LH) tree is a tree tree with the height of the left subtree more than that of right subtree.
  Right High (RH) tree is a tree with the height of the right subtree more than that of left subtree.

Then the book says:

  Insertion of a node may make an AVL tree height unbalanced. All height unbalanced trees fall in one of these four cases:

  LH of LH — A subtree of a tree that is left high has also become left high.
  RH of RH — A subtree of a tree that is right high has also become right high.
  RH of LH — A subtree of a tree that is left high has become right high.
  LH of RH — A subtree of a tree that is right high has become left high.

I went through the example of balancing RH of RH tree as below. As can be seen below it involves left rotating root of RH tree (not subtree) to replace left node of the root of RH subtree:

Now I am looking at the example in Schaum's, which inserts W in the AVL tree already containing M,E,D,G,T,P,V,U,Z as follows:

I dont understand if the rotateRight() in above is necessary. I guess above is also an example of RH of RH tree, if you apply Forouzan's analogy. In this case nodes T and V are Right High. So as per explanation in Forouzan's book, we can apply single left rotation to node T to make it left child of V and balance this AVL tree as follows:

                 M
               /   \
              /     \
             E       V
            / \     /  \
           D   G   T    Z
                  / \  /
                 P   U W

I dont find the need of first rightRotate() to make W right child of Z. Is it necessary? Or Schaum's example is wrong?

I think you are right for this example. But the title of your question is misleading. Let me explain.

After insertion the tree can be rebalanced with one (single or double) rotation at the lowest node $x$ where unbalance occurs. There are four cases, as you mention. If the key has been inserted in a left-left or a right-right subtree we do a single rotation to the right or to the left, and if it was the left-right or right-left subtree we do a double rotation at $x$ (in suitable direction).
In general a single rotation will not work.

Back to the example you show us. The lowest point of unbalance is $T$. From $T$ the new key $W$ was added right-right. That means a single rotation left at $T$. As far as I see the result of this is exactly what you have drawn in your diagram.

To close, your title is misleading, as we do not need double rotation here, but we need one in other situations.


Compute the general time complexity of a merge sort algorithm with specified complexity of the merge process The problem was from an exam, I spent much time wrapping my head up around this kind of problems, so I decided to ask for help ;(

Problem:

We implement a merge sort algorithm to sort $n$ items. The algorithm will divide the set into 2 roughly equal-size halves, and merge the 2 halves after each half set is recursively sorted. Because the item comparison is complicated, the merge process takes $\theta(m\sqrt{m})$ steps for input size $m$. What is the time complexity for this algorithm?

(a) $\theta{(n\log{n})}$
(b) $\theta{(n)}$
(c) $\theta{(n^2)}$
(d) $\theta{(n\sqrt{n})}$
(e) $\theta{(n\sqrt{n}\log{n})}$

What I tried:

I know the merge sort normally can be written $S(n) = 2S(\frac{n}{2}) + n, S(1) = 1$, where the recursive function $S$ is the step cost of the merge sort for the size $n$.
But the problem specifies the step costs to merge is $\theta(n\sqrt{n})$, I have to rewrite it as $S(n) = 2S(\frac{n}{2}) + \theta(n\sqrt{n}) = 2S(\frac{n}{2}) + n\sqrt{n}$.
I have no idea how to transform it into the general solution...

Please help me, I will learn a lot from this problem! Thanks :)

You are on the right track.

Now that we have the recurrence relation $$S(n) = 2S(\frac{n}{2}) + \Theta(n\sqrt{n}),$$ Applying the case three of the master theorem, where $a=2$, $b=2$, $\epsilon=\frac12$, we will have $S(n)= \Theta( n\sqrt n)$.

I was stretching a bit when we were applying the master theorem since the regularity condition, the existence of such $c>0$ required for case three is not necessarily satisfied. What I really meant is that we can find two constant $0<c_1<c_2$ such that $c_1n\sqrt n\le S(n)-2S(\frac n2) \le c_2n\sqrt n$ for all $n$. Define $S_1$ by $S_1(n) = 2S_1(\frac{n}{2}) + c_1n\sqrt{n}$ and $S_2$ by $S_2(n) = 2S_2(\frac{n}{2}) + c_2 n\sqrt{n}$ with the same initial condition as $S$. Now we can apply case three of the master theorem to $S_1$ and $S_2$ to get the same $\Theta$ bound, since the regularity condition is satisfied with $1>c=0.8>\sqrt2/2$. Since $S_1(n)\le S(n)\le S_2(n)$, S(n) has the same $\Theta$ bound.

In case you have not learned/are not allowed to use the master theorem, you may have to more or less prove case three of the master theorem by yourself. You could find a proof, for example, in CLRS.


What is the need of re-sampling the image for HOG features? I read Dalal and Triggs paper for HOG description and a blog Chris McCormick HOG regarding the same. The blog says that the image needs to be re-sampled at different scales to recognize different person.

My question is: Already we have a window which we place on the image having a size of 64*128 and which slides over the image. Then why re-sampling instead of sliding the whole window over the image which can detect the persons instead. ?

Please rectify if I am wrong, thanks in advance !!

You are indeed sliding window over the image which has fixed size, but the picture may have different resolution or simply the person in the photo is in some distance from the camera (so the face size in the picture will be related to distance) but your classifier should work anyway, so checking at different sizes is one of the ways to detect people at different depth.


Solving the part-of-speech tagging problem with HMM There is a famous part-of-speech tagging problem in Natural Language Processing. The popular solution is to use Hidden Markov Models.

So that, given the sentence $x_1 \dots x_n$ we want to find the sequence of POS tags $y_1 \dots y_n$ such that $y_1 \dots y_n = \arg\max_{y_1 \dots y_n}p(Y,X)$.

By Bayes Theorem, $P(X,Y)=P(Y)P(X \mid Y)$.

Solving POS by HMM implies the assumptions: $p(y_i \mid y_{i-1})$ and $p(x_i \mid y_i)$.

The question is there are any particular reason why we prefere to solve it by generative model with a lot of assumption and not directly by estimating $P(Y \mid X)$, given the training corpus it's still possible to estimate $p(y_i \mid x_i)$.

The second question, even when we convinced that the generative model is preferred why to calculate is as $P(Y,X)=P(Y)P(X \mid Y)$ and not $P(X,Y)=P(X)P(Y \mid X)$. In case we have an appropriate generative story I can use $P(X,Y)=P(X)P(Y \mid X)$ as well, is it mentioned somewhere that assumed generative story is preferred.

Isn't this exactly the same question you asked previously? I'll make some additional comments and add some links here. Hopefully that will help.

  is there are any particular reason why we prefere to solve it by generative model with a lot of assumption and not directly by estimating $P(Y∣X)$, given the training corpus it's still possible to estimate $p(y_i∣x_i)$?

It just depends. Choosing whether to model $P(X,Y)$ or $P(Y|X)$ is simply the choice of generative versus discriminative. Both have advantages. See the paper
On Discriminative vs. Generative classifiers by Ng and Jordan. One thing worth mentioning, that I didn't say last time, is unsupervised learning in a generative framework is normally straightforward. This means it is also fairly obvious how to do semi-supervised learning. Semi-supervised learning can be very helpful for NLP tasks where the amount of unlabeled data is essentially infinite and labelled data is hard to obtain. Semi-supervised learning is typically not as easy in a discriminative framework. See Co-training as an example of the later.

As for how one decomposes the joint, well that's up to you. There's no rule saying you cant decompose it as $P(X,Y) = P(X)P(Y|X)$. Doing so would be perfectly valid, just not sensible. Notice decomposing the joint this way includes the factor $P(Y|X)$ already. If you're ultimately interested in predictiong $Y$ given $X$, then you should should predict
$$
\begin{align*}
\arg\max_y P(Y=y,X=x)
&= \arg\max_y P(X=x)P(Y=y|X=x) \\
&= \arg\max_y P(Y=y|X=x).
\end{align*}
$$
So you just use $P(Y|X)$ and ignore $P(X)$ and we're back at a discriminative classifier.


Define a length function over $A^{*} \leftarrow{N}$ such that $length(l)$ outputs the length of $l$ Consider the following definitions

LIST:

$\overline{nil}  \ \ \ \ \ \frac{l}{a \ l}$ $a \in A$

$A^* = \mu \widehat{LIST}, \ A^{\infty} = v \widehat{LIST}$

NAT:

$\overline{0} \ \ \ \ \ \frac{x}{s(x)}$

$ N = \mu \widehat{NAT}, \ N^{\infty} = v \widehat{NAT}$

Given those definitions I have to define a length function over $A^{*} \leftarrow{N}$ such that $length(l)$ outputs the length of $l$.

I have tried to do this problem using structural induction on a given $l$ but I don't seem to get any relevant result.

In general, how would you approach this kind of problem?

Let F denote a “shape”, as your LIST and NAT shapes for example.

  Declaring $I := μF$ is tantamount to saying that $I$ is recursively defined by some $α : F(I) ≅ I$
    and moreover for any $β : F(K) → K$ there is a unique $f : I → K$ that respects the “F”-structure.

Since you define $A^* = μ(LIST)$, where the “LIST” structure on a set $X$ consists of a constant $c : X$
and a function $n : A × X → X$ --- c.f., your $nil, -·-$ --- we automatically obtain an operation $A^* → ℕ$ if
we can endow $ℕ$ with a “LIST” structure; namely a constant such as zero $0 : ℕ$ and an operation
on ℕ such as $A \times ℕ → ℕ : (a, n) ↦ s\, n$.

So by the μ-definition of lists, since we furnished ℕ with a LIST structure,
we have that there is a unique function, call it $length$, that respects the LIST structure in that
it takes the shape constants-to-constants and the shape functions-to-functions:
$$ \mathsf{length}(nil) \;=\; 0 $$
$$ \mathsf{length}(a \cdot l) \;=\; s(\mathsf{length}\, l) $$

Alternatively, these properties also serve to “define length by structural induction on  the shape of lists”.

Hope that helps a bit :-)


Does splitting a process across 4 terminal windows decrease the time it takes? Basically, I using an algorithm called 'miranda' to look at miRNA targets and it only runs on a single thread. It compares everything in one file against everything in another file, produces a file as an output and runs off of the command line in terminal. The process took roughly 20 hours to create the output file.

I was advised by my supervisor that if i split one of the files up into say 4 equally sized parts, and ran them in four separate terminal windows this would decrease the overall time it took for the process to be completed.

I found that when I was using a single terminal window, the process would take up about 100-120% of the CPU. However, when running four terminal windows, each individual process only takes between 30-40% of the CPU.

How much effect does splitting the file up like this have in the overall time it takes to run the process? Although I split it across four threads, will the effect only be an increase in speed of about 1.5 times?

What you describe (split job into parts, total CPU usage stays the same) indicates that your task is (or gets) I/O (or perhaps RAM) bound. Try splitting among several machines, not just several processes on the same machine. If the program you are using comes from somewhere else, see if there are newer versions, bug reports on performance, or perhaps tricks and suggestions, on its webpage or user sites.

Use the tools on your operating system to see what the bottleneck really is. As you don't say what operating system this is, I can't give concrete suggestions. Perhaps look into  uxix.stackexchange.com, superuser.com, or serverfault.com (all part of the stackexhange network).


Understanding transactions In operating systems, Is a transaction a process? Are they the same
concept?
Does a transaction have the same meaning in database management
systems, as in OS?

A database book says

  A transaction is defined as any one execution of a user program in a DBMS and differs from an execution of a program outside the DBMS
  (e.g., a C program executing on Unix) in important ways. "

  a transaction is an execution of a user program, seen by the DBMS as a series of read and write operations.

In OS, a running program = a process, isn't it?
Is there some theory about transactions, or is there math theory
underlying transaction management?

Thanks!

A transaction in database management system is a collection of tasks to be done by the system with certain guarantees on results depending on the type of the transactions.
A process in OS is an implementation for a container which runs programs/code. Different kinds of processes (often just two types) have different capabilities.

There is a clear similarity between the two. However, they are different in several ways.

Transactions do not create new transactions. They have a beginning and an end.
Processes can create new processes, they have the beginning but they might not have an end

I believe that with PL/SQL, one can manage to accomplish a lot with transaction and with this a transaction might have a close resemblance to a process. For example, with PL/SQL, one can declare variables and use them in the same way that a process stores values and states in its virtual memory address. So in this way, a transaction and a process are very similar. This is about Turing completeness of PL/SQL. Transaction performs task written in PL/SQL language, and process performs task in the OS's programming language (which is the binary code of that OS).

One difference between the two is the way they communicate with each other. Transactions can only communicate indirectly with each other via the results of tasks stored in the database. Process can directly communicate with each other as well as indirectly with each other via side effect on the file system (or similar objects).

So the answer to your question:

Transaction is not a process in OS. They are similar concepts, but not the same
A program is not a process. This is because a program might be run by multiple processes
Of course, there are mathematical models behind transaction. Graphs are often used together with many other things. They use a lot of things in database management system theory. If you want to know more, perhaps a new, specific question will be more appropriate.


Balanced sub-sequence Consider two strings $S$ and $T$ of length $n$. Here both the strings $S$ and $T$ consists of only
( and ) that is made of parenthesis. I need to find a string $w$ which is balanced parenthesis and it should be sub-sequences of both $S$ and $T$ among all those strings $w$ i need the maximum length strings.
This problem is clearly a dynamic programming problem, but i am having hard time in finding states and also their transitions. Could anyone help me.
P.S - Problem E , but it is in Russian

Initially I missed a key part of the question, that is, the subsequence we are looking for must be a common subsequence for two strings $S$ and $T$. I'll keep my initial answer, and will elaborate after that, about how to extend to the case of interest.

One way to detect if a sequence forms a valid balanced parenthesis is to change ( for +1 and ) for -1 and check that the sum of every prefix is non-negative $(P_i \geq 0)$ and the sum of the entire sequence is $0$ ($P_n = 0)$. We define $P_i$ as the balance of the $i$-th prefix.
To compute the largest valid subsequence you can keep track for each prefix $i$ what is the largest valid subsequence of that prefix with a fixed balance $b$: $(Q_i^b)$. The answer to your problem is $Q_n^0$.
Fortunately $Q_i^*$  only depends on the $i$-th character and $Q_{i-1}^*$ so we can use dynamic programming to compute such values. Let's define for the sake of simplicity that for states such that no valid sequences exist the value of $Q_i^b = -\infty$.
The base case for empty prefix $i = 0$.

$Q_0^0 = 0$: The largest valid subsequence for the empty prefix is the empty string (size=$0$) which has balance $0$.
$Q_0^b = -\infty$: For all balance different than $0$ there is no such string that is subsequence of the empty prefix with balance $b$, so we use $-\infty$.

Let's define transitions to compute each value given that all previous values (with less $i$) are already computed. On each step we either append that character to the end of the subsequence, or we discard that character:
$$Q_i^b = \max(Q_{i - 1}^b, Q_{i - 1}^{b - s[i]} + 1)$$
The first term in the $\max$ expression cover the case that we don't use the last character, so the maximum subsequence with balance $b$ and prefix $i$ is at least as large as the maximum subsequence with balance $b$ and prefix $i - 1$.
The second term in the $\max$ expression cover the case that use the last character, notice that $s[i] = +1$ if there is an open parenthesis ( at position $i$, or $s[i] = -1$ otherwise. Then the new balance will be $b$ if in the previous step the balance was $b - s[i]$, so after adding the $i$-th character it becomes $b$.
We should only compute $Q_i^b$ values for $b \geq 0$, to keep the balance of the sequence always non-negative.
In practice we know the balance won't be larger than $n$ (in fact it won't be larger than $\frac{n}{2}$) so we can compute values of $Q_i^b$ for $0 \leq i \leq n; 0 \leq b \leq n$. Each transition is computed in $O(1)$ so the overall complexity of this solution is $O(n^2)$. Since states $Q_i^*$ only depend on states $Q_{i -1}^*$ we can use only $O(n)$ memory keeping at each moments two rows of the dynamic programming table.

To find a subsequence of two strings $S$ and $T$ we can instead use a dynamic programming state with $3$ dimensions: What is the maximum valid parenthesis sequence with balance $b$ which is a subsequence of prefix of length $i$ from $S$ and prefix of length $j$ from $T$ ($R_{i,j}^b$). The answer is $R_{|S|, |T|}^0$.
The solution is almost the same but transition should be modified to address the new constraint:
$$R_{i, j}^b = \max(R_{i - 1, j}^b, R_{i, j - 1}^b, R_{i - 1, j - 1}^{b- S[i]} \cdot [S[i] == T[j]])$$
The first two terms inside $\max$, handle the case where the best sequence with balance $b$ of prefixes $i$ and $j$ from $S$ and $T$ don't use the last character for both, so at least one of them is not used, and we cover both situations.
The third case is trickier, it handles the case where we do use the last character, but we can only use that character if both character are the same $S[i]$ and $T[j]$, since we most find a common subsequence.
Note about complexity: Now complexity is $O(n^3)$ since that is the number of states and each state is computed in $O(1)$. Again, we can apply a trick to use $O(n^2)$ memory, however it is very tricky to do that and also being able to recover the answer.
In practice: The problem have $n=700$ and time limit $3.5$ seconds. Notice that the number of operations you are doing are roughly $\frac{700^3}{2}=171500000$ basic operations. A modern machine should perform roughly $1e8$ basics operations per second, so this solution should fit in time.
However, to recover the answer you should store for each state, the optimal decision. Notice there are only 3 options, so it fits in 2 bits. It requires $\frac{700^3}{2} \cdot 2$ bits which is $~42MB$. However, if instead of bits, a byte is used to store each decision, the the code will use $\frac{700^3}{2}$ bytes which is $171MB$ and is greater than the limit $128MB$.


Restrictions needed on ADT for totality In the paper Total Functional Programming by D.A. Turner three rules are given for a programming language to remain total:

complete case analysis
covariant type recursion (type constructor should not appear in negative position in a constructor argument)
structural recursion

But with these rules I can still have an infinite loop:

data Fix f = Fix (f (Fix f))
data Bad r = Bad (r -> r)

bad :: Fix Bad -> Fix Bad
bad b =
  case b of
    Fix t ->
      case t of
        Bad f -> f b

nonTotal = bad (Fix (Bad bad))

Where is my mistake? Should all type variables also only appear covariantly? Or is the "covariant type recursion" condition more strict?

The constraint

  covariant type recursion (type constructor should not appear in negative position in a constructor argument)

excludes this

data Bad r = Bad (r -> r)
                  ^    ^--- positive position
                  ^-------- negative position

Indeed, all the occurrences of r must appear in positive position.

  Should all type variables also only appear covariantly?

Yes, precisely.

Essentially, your Fix Bad tries to generate a type $T$ isomorphic to $T \to T$. If we had that, we would have a model of the untyped $\lambda$ calculus, where terms are not normalizing ("terminating") in general.

Indeed, to apply any two terms $x, y : T$ we can exploit the isomorphism to treat $x$ as if $x : T\to T$, at which point the application $x y$ becomes feasible. As a special case, we also obtain $xx$, hence $\Omega = (\lambda x.xx)(\lambda x.xx)$ which is the archetypal non normalizing term.

To conclude let me point out that, in some advanced calculi with dependent types, covariant recursion is not enough, and you need an even stricter constraint called "strict positivity". Without that, contradictions arise. In Haskell-like languages, covariance (and the other constraints you mention) should suffice.


The Church-Turing thesis and Hyper-computation I am not a computer scientist and this is my first question.
This question is a question in layman terms and I also want the answer in layman terms.
When I searched hyper-computation. There was a list of models of hyper-computers.
Now, my question is that what are the problems with those models and if it is possible to  create models of computers which can compute non-Turing computable things then doesn't, that already proves the Church-Turing thesis wrong and if it does prove that Church-Turing thesis is wrong then why people still consider it to be a thing?

The Church–Turing thesis is about physically realizable machines. To the best of our knowledge, hypercomputation models cannot be realized in the physical world. They are a figment of our imagination.
If someone would find a new law of physics which enables solving the halting problem, that would make a big fuss in the world of science. But I am not holding my breath.


Proving that a class of languages is a subset of RE for Rice Theorem Consider language $L = \{<M> |L(M) \subseteq L(0(0\cup1)^*) \}$
  where $<M>$ is a valid encoding of a turing machine.

I know that the language is applicable for Rice Theorem.
Now, I understand that in this case the language group in $RE$ is:

$C = \{L\subseteq \Sigma^*|L\subseteq L(0(0\cup1)^*)\}$

However, I'm not sure how to prove that each of these languages is in the $RE$ class. Note That an alphabet wasn't given in the exercise so I guess that there can be other letters. I thought at first it had something to do with the languages being subests of a regular language, but then again $\Sigma^*$ is a regular language and all other languages are its subsets.

You missed a tiny detail when defining $C$: all those languages are RE by assumption; no other language can be an $L(M)$!

Let us again look at the language you want to say something about:

$\qquad L = \{ \langle M \rangle \mid M \text{ is a TM}, L(M) \subseteq L\bigl(\, 0(0\cup1)^* \,\bigr) \}$.

We see that $L \subseteq \Sigma^*$ for some alphabet $\Sigma$ that depends on the TM encoding $\langle \_ \rangle$.

Now recall the statement of Rice's theorem: the index set

$\qquad \Phi(X) = \{ \langle M \rangle \mid  M \text{ is a TM}, L(M) \in X \}$

of a language class $X$ is undecidable if $\emptyset \subsetneq X \subsetneq \mathrm{RE}$.

Now, it is obvious (read: very easy to prove -- your exercise) that $L = \Phi(C)$ with

$\qquad C = \{ Y \in \mathrm{RE} \mid Y \subseteq L\bigl( 0(0+1)^* \bigr) \}$;

the requirement $\emptyset \subsetneq C \subsetneq \mathrm{RE}$ is likewise trivial.

We don't get to "just say" anything; we have to prove all three conditions -- $L = \Phi(C)$, $\emptyset \subsetneq C$, and $C \subsetneq \mathrm{RE}$ -- but it so happens that all three proofs are very easy here since $L$ has been defined in a very suitable way. For other languages, the proofs can be more intricate (or impossible; then Rice's theorem does not apply).

Side note: If we consider

$\qquad C' = \{ Y \in \Sigma^* \mid  Y \subseteq L\bigl( 0(0+1)^* \bigr) \}$

then we also get $\Phi(C') = L$! While there are non-RE $X$ in $C'$ (a simple if non-constructive argument is that there are uncountably many such $X$), $\Phi$ "ignores" them. However, $C'$ does not fulfill the conditions of Rice's theorem so we can not use it.


Is it decidable whether a Turing machine M will reach state q on input s? Given a turing machine $M$, one of its states $q$ and an input word $w$, will $M$ ever reach $q$ on $w$?

As we are not given anything about the word length, I assume that we have a finite length word. Then I believe this problem is decidable. After all, we only have to check whether we come across state $q$ when we feed $w$ to $M$.

But my solution manual claims that it is an undecidable problem.

Am I correct or is the manual correct? Do we ever take into consideration a word with infinite length during such analysis?

Do we ever take into consideration a word with infinite length during such analysis?

Never say never. However, it is a safe bet that in the course of your undergraduate or even graduate study you can assume that all inputs to Turing machines are finite.

Here is a more formal restatement/understanding of the problem in the question.

  $$\begin{align}\text{TRIPLE }=&\{\langle M, q, w\rangle: M\text{ is a Turing machine. }\\
&q\text{ is one of the states of }M. \\
&w\text{ is a word over the input alphabet of }M.\}\\
\text{REACH }=&\{\langle M, q, w\rangle\in\text{TRIPLE}: M\text{ will reach }q\text{ on input }w. \}\end{align}$$
  Is $\text{REACH}$ decidable? (the problem of state reachability)

Assume $\text{REACH}$ is decidable. By definition, there is a Turing machine $T$, which, given a Turing machine $M$, its state $q$ and an input word $w$ as its input, it will accept the input if and only if $M$ will reach state $q$ on input $w$.

Recall that $A_{\text{TM}} = \{\langle M,w\rangle : M \text{ is a TM and }M\text{ accepts }w\}$. Construct a new Turing machine $T'$ such that given input $\langle M, w\rangle$ where $M$ is a TM and $w$ is an input for $M$, $T'$ will change the input to $w'=\langle M, q_{\text{accept}}, w\rangle$ where $q_{\text{accept}}$ is the unique accept state of $M$, and then simulate $T$ on input $w'$. We see that $T'$ is a decider for $A_{\text{TM}}$.

I would believe you have learned that $A_{\text{TM}}$ is not decidable. That contradiction shows that our assumption must be wrong, which means this problem of state reachability cannot be decidable.

(In case that the Turing machines defined for you could have multiple accept states, $T'$ could replace all accept states in $M$ with a unique accept state at first.)

Reader can also take a look at a more intuitive and less notation-cluttered but less rigorous version of this answer here, which is just the first version of this answer.


Shortest path in a dynamic tree with vertex updates There is a tree with $n$ nodes. All edges are of equal weights. The vertices of the tree can be of two types: 0 or 1. There are two types of queries:

Set(X): change the given vertex X from type 0 to type 1,
Dist(X): find the shortest path from X to a node of type 1 and return the length of this path.  This will return zero if X is of type 1.

The naive method would be to just maintain a tree and on every update change the type of vertex; to answer queries of second type, run a bfs starting at X and stop as soon as a vertex with type 1 is found.  With this simple scheme, Set(X) would run in $O(1)$ time, but Dist(X) would take $O(n)$ time.

However, in my application the number of queries and number of nodes are both of the order of $10^5$, so the naive method is too slow.  In particular, $O(n)$ time is too slow.

Can somebody suggest a better algorithm for doing this?

One can improve your naive method by augmenting the data structure.  At each node in the tree, store an extra field that contains the distance to the closest descendant of type 1.  Assume each node as a pointer to its parent.  Let the depth of the tree be $d$.

Now Set(X) takes $O(d)$ time: you traverse the parent pointers to visit each of X's ancestors and update their distance field.  Also Dist(X) takes $O(d)$ time: the distance field for X tells you the shortest path to a descendant of X, and by looking at the distance fields for the siblings of the nodes along the path from X to the root, you can find the shortest path to a non-descendant of X.  Thus, both operations can be done in $O(d)$ time.

If the tree is balanced, we'll have $d = O(\lg n)$, so both operations run in $O(\lg n)$ time -- a significant improvement over the naive method you mention.

Of course, in the worst case the depth of the tree could be $\Theta(n)$, so this method won't help for such trees.  But in practice many trees (e.g., random trees) tend to have depth $O(\lg n)$.  And if you need an algorithm that works for all trees, you might be able to take advantage of a heavy-light decomposition to achieve good worst-case running time bounds.


Is there an efficient algorithm for expression equivalence? e.g. $xy+x+y=x+y(x+1)$ ?

The expressions are from ordinary high-school algebra, but restricted to arithmetic addition and multiplication (e.g. $2+2=4; 2.3=6$), with no inverses, subtraction or division.  Letters are variables.

If it helps, we can forbid any expression representable with numeric values other than $1$; i.e. not $x^2$ nor $3x$ nor $4$:

multilinear, no powers other than $1$: $x+xy \equiv x^1+x^1y^1$ is OK, but not $x^2+x^3y^4$, and not anything that could be represented as that, as in a full expansion to sum-of-products e.g. not $x(x+y) \equiv x^2+y$;
all one, no coefficients other than $1$: $x+xy \equiv 1.x+1.xy$ is OK, but not $2x+3xy$, and not anything that could be represented as that, as in a full expansion to sum-of-products e.g. not $a(x+y)+x(a+b) \equiv 2ax+ay+bx$ ; and
no constants other than $1$: again, in the fully expanded sum-of-products e.g. not $(a+1)+(b+1) \equiv a+b+2$

$Q.$ Is there an efficient algorithm to determine if two expressions are equivalent?

To illustrate, here's an inefficient brute-force algorithm with exponential time:

  expand both expressions fully to sum-of-products, which can easily be checked for equivalence (just ignore order, since commute/associate can reorder).

e.g.
$(a+b)(x+y) \rightarrow ax+ay+bx+by$
$a(x+y)+b(x+y) \rightarrow ax+ay+bx+by$

This seems a well-known problem - even high school students are taught manual ways to solve it. It's also solved by automated theorem provers/checkers, but they concentrate on more sophisticated aspects.

Here's a working online automated theorem prover: http://tryacl2.org/, which shows equivalence by finding a sequence of commute/associate/distribute etc:

$xy+x+y=x+y(x+1)$ ?
(thm (=  (+ (* x y) x y)  (+ x (* y (+ x 1)))  )) --- 188 steps

$y+x(y+1)=x+y(x+1)$ ?
(thm (=  (+ y (* x (+ y 1)))  (+ x (* y (+ x 1)))  )) --- 325 steps

This is my first question here, so please let me know if I've chosen the wrong place, wrong tags, wrong way of describing/asking etc. Thanks!
NB: this question has been rewritten in response to comments
Thanks to all responders! I've learned a lot.

Your problem reduces to zero testing of multivariate polynomials, for which there are efficient randomized algorithms.

Your expressions are all multivariate polynomials.  Apparently, your expressions are built up by the following rules: (a) if $x$ is a variable, then $x$ is an expression; (b) if $c$ is a constant, then $c$ is an expression; (c) if $e_1,e_2$ are expressions, then $e_1+e_2$ and $e_1e_2$ are expressions.  If that's indeed what you intended, every expression is a multivariate polynomial over the variables.

Now, you want to know if two expressions are equivalent.  This amounts to testing whether two multivariate polynomials are equivalent: given $p_1(x_1,\dots,x_n)$ and $p_2(x_1,\dots,x_n)$, you want to know if these two polynomials are equivalent.  You can test this by subtracting them and checking whether the result is identically zero: define

$$q(x_1,\dots,x_n) = p_1(x_1,\dots,x_n) - p_2(x_1,\dots,x_n).$$

Now $p_1,p_2$ are equivalent if and only if $q$ is the zero polynomial.

Testing whether $q$ is identically zero is the zero testing problem for multivariate polynomials.  There are efficient algorithms for that.  For instance, one example algorithm is to evaluate $q(x_1,\dots,x_n)$ at many random values of $x_1,\dots,x_n$.  If you find a value of $x_1,\dots,x_n$ such that $q(x_1,\dots,x_n)$, then you know that $q$ is not identically zero, i.e., $p_1,p_2$ are not equivalent.  If after many trials they are all zero, then you can conclude that $q$ is identically zero (if $q$ is not identically zero, the probability that all of those trials yield zero can be made exponentially low).  The number of iterations you need to do is related to the degree of $q$; see the literature on polynomial identity testing for details.

For instance, see https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma and http://rjlipton.wordpress.com/2009/11/30/the-curious-history-of-the-schwartz-zippel-lemma/

These algorithms apply if you are working over a finite field.  You didn't state what field/ring you are working in, and whether you are are treating these expressions as formal expressions (e.g., polynomials as abstract objects) or as functions from $\mathbb{F}^n \to \mathbb{F}$.  If you are working over a finite field, the methods above apply immediately.

If you're treating the expressions as formal objects, then your expressions are equivalent to multivariate polynomials with integer coefficients.  You can test equivalence of these by choosing a large random prime $r$ and testing equivalence modulo $r$, i.e., in the field $\mathbb{Z}/r\mathbb{Z}$.  Repeat this polynomially many times, with different random values of $r$, and you should get an efficient randomized algorithm for testing equivalence of these formal expressions.


4 Vertex Cover Problem is not NP Complete why? With Given Graph $G$ why finding that $G$ has a vertex cover of at most $4$ is in $P$ and Not in NP Complete. it means there us poly-time algorithm for this problem !!?

If your graph has $n$ vertices, there are $O(n^4)$ possible subsets of $4$ vertices. Given one such subset, it is easy to check if it is a cover in $O(n^2)$ operations, by inspecting every edge and verifying whether it has an endpoint in the given subset.
Thus, in $O(n^6)$ operations we can check all possibilities.


Proving $\log (N)$ mistake bound is "tight" for a learner when learning thresholds I'm studying the online learning model and the Halving algorithm.

We've seen the threshold problem:

The domain is $X=\left\{ 1,2,...,N-1\right\} $, the label set is  $Y=\{-1,1\}$ and the hypotheses class is $H=\left\{ h_{\theta}(x)=sign(x-\theta):\theta\in\left\{ \frac{1}{2},1+\frac{1}{2},...,(N-1)+\frac{1}{2}\right\} \right\} $

I'll denote the number of mistakes the learner $A$ does on the environment $E$ by $M(A,E) = \left|\left\{ i:\hat{y_{i}}=A_{\mbox{pred}}(x_{i})\neq y_{i}\right\} \right|$ where $E=\left\{ (x_{i},y_{i})\right\} _{i=1}^{n}$

For any environment $E$, the mistake bound for Halving  is  $M$(Halving,$E$)$\leq\left\lfloor \log N\right\rfloor $

Now I must prove that this bound is "tight", i.e., for any learning algorithm $A$ there exists a realizable environment $E$ such that $M(A,E)\geq \left\lfloor \log N\right\rfloor$

My try - I came to the conclusion that finding the correct $h^{*} \in H$ is pretty similar in this case to finding a value in a sorted array.
Since we'll need at least $\left\lfloor \log N\right\rfloor $ comparisons, an algorithm $A$ which can find $h^{*}$ and make less than $\left\lfloor \log N\right\rfloor$  mistakes "can find a value in a sorted array in less than $\left\lfloor \log N\right\rfloor$ comparisons for any given array, which is a contradiction."

The sentence in quotes is my intuition, but I'm having trouble proving it formally.

Is this the right way to go?

Many thanks.

I am assuming the learning model described in Wikipedia. The environment will maintain a set of hypothesis forming an interval $S = [h_\alpha,h_\beta]$ consistent with its current answers, and will ensure that the first $\log N$ answers by the algorithm are wrong. In the beginning, $S = H$. At each step, the environment presents the middle point of the interval (we're identifying hypotheses with points in the domain in a natural way). Depending on the learner's answer, the interval $S$ is halved so that the learner is wrong. This process can go on for $\log N$ steps, in each of which the learner is mistaken, so that in total the learner makes at least $\log N$ mistakes.


T(n) = aT(n/b)+f(n), I don't understand the difference between a and b I was analyzing the time complexity for recursive algorithms like merge sort, but when I came across that recurrence, [I think that equation is called a recurrence right?] I couldn't differentiate between a which mean the number of subproblems and b which in my slides it says is the factor by which n is divided by.

Here are three examples of algorithms with $b=2$ and $a=1,2,3$.

In all these examples, there is some small-scale cheating involved, which doesn't affect the asymptotic running time. I'll let the reader figure out where I'm cheating.

Binary search

In this algorithm, we are looking for an element $x$ in a sorted array $A$ of length $n$.

If $n = 1$, the problem is easy.

Otherwise, let $m$ be the index of the middle element:

If $x = A[m]$, we are done.
If $x < A[m]$, we recurse with the array $A[1],\ldots,A[m-1]$.
If $x > A[m]$, we recurse with the array $A[m+1],\ldots,A[n]$.

Every time we recurse, the size of the array decreases by a factor of 2. Therefore, the running time of binary search on inputs of length $n$ satisfies the following recurrence:

  $T(n) = T(n/2) + O(1)$.

Here $a = 1$ and $b = 2$. The solution is $T(n) = O(\log n)$.

Merge sort

In this algorithm, we are sorting an array $A$ of length $n$.

If $n = 1$, the array is already sorted.

Otherwise, partition $A$ into two arrays $A_1,A_2$ of length $n/2$, sort each recursively, and then merge them in $O(n)$ time.

In contrast to binary search, in which we only recursed on one of the half-arrays, in merge sort we recurse on both. Therefore the appropriate recurrence is

  $T(n) = 2T(n/2) + O(n)$.

Here $a = b = 2$. The solution is $T(n) = O(n\log n)$.

Karatsuba multiplication

In this algorithm, the goal is to multiply two $n$-bit integers $x,y$.

We first divide $x,y$ into two $n/2$-bit integers: $x = 2^{n/2} x_1 + x_2$, $y = 2^{n/2} y_1 + y_2$. We then proceed as follows:

Compute $z_1 = x_1 y_1$.
Compute $z_2 = x_2 y_2$.
Compute $w = (x_1+x_2)(y_1+y_2)$.
Return $2^n z_1 + 2^{n/2} (w - z_1 - z_2) + z_2$.

In steps 1,2,3, we are multiplying $n/2$-bit integers (more or less; in step 3 they are $(n/2+1)$-bit integers). The rest of the algorithm consists of addition and subtraction, which can be done in linear time. Therefore the appropriate recurrence for the running time of this algorithm is
$$
T(n) = 3T(n/2) + O(n).
$$
Here $a = 3$ and $b = 2$. The solution is $T(n) = O(n^{3/2})$, improving on the trivial $O(n^2)$ algorithm.


Is the $k$P$k$N-3SAT problem NP-complete? Consider the following 3-SAT variant defined over the variables $x_1,\ldots,x_n$. In the $k$P$k$N-3SAT problem each variable $x_j$, $j \in [n]$, occurs exactly $k$ times as a positive literal in $\phi$, and exactly $k$ times as a negative literal in $\phi$, where $\phi$ is a 3-CNF formula. The problem is then to decide if such a formula has a satisfying assignment.

  Is the $k$P$k$N-3SAT problem NP-complete?

In the $m$P$n$N-SAT problem each positive literal occurs exactly $m$ times in $\phi$, and each negative literal occurs exactly $m$ times in $\phi$, where $\phi$ is a CNF formula. It was shown in [1] that $2$P$1$N-SAT is NP-complete. This hints that the $k$P$k$N-3SAT problem is hard as well.

The $1$P$1$N-SAT is apparently easy, see a related question and answer here. Is $k$P$k$N-3SAT perhaps hard already for $k \geq 2$?

[1] Yoshinaka, Ryo. "Higher-order matching in the linear lambda calculus in the absence of constants is NP-complete." Term Rewriting and Applications. Springer Berlin Heidelberg, 2005. 235-249.

1) 2P2N-3SAT is NP-complete

(Edit to take into account all comments below)

Take a 2P1N-SAT instance, check the all-1 vector is not a model, then add the clause with all variables negated to the formula to transform it into a 2P2N-SAT instance.

For each 1-clause $(a)$ in the new 2P2N formula, replace it by the three following 3-clauses : $(a \lor x \lor x)(\lnot x \lor y \lor y)(\lnot x \lor \lnot y \lor \lnot y)$ where $x,y$ are fresh 2P2N variables (i.e. appearing twice as positive literals and twice as negative literals).
For each 2-clause $(a \lor b)$ in the formula, replace it by the six following 3-clauses : $(a \lor b \lor x)(\lnot x \lor y \lor y)(\lnot x \lor \lnot y \lor \lnot y)(x \lor z \lor \lnot z)(z \lor t \lor  \lnot t)(\lnot z \lor t \lor \lnot t)$ where $x,y,z,t$ are fresh 2P2N variables.
Keep all 3-clauses in the formula.
For each $k$-clause ($k>3$) in the formula, transform it into a set of 3-clauses by the usual way, which does not change the number of occurences of positive (negative) literals of the taken $k$-clause, but add only extra variables which appear once as a positive literal and once as a negative literal. For each such new variable $x$, add the two following clauses to the 3-CNF formula :  $(x\lor y \lor \lnot y)$ and  $(\lnot x \lor \ y\lor  \lnot y)$ where $y$ is a fresh 2P2N variable.

All these transformations can obviously be done in polynomial time and transform the 2P1N-SAT instance into a 2P2N-3SAT instance. The NP-complete 2P1N-SAT problem is then reducible to the 2P2N-3SAT problem.

2) The extension to $k$P$k$N-3SAT can be done in the same spirit (a bit longer) to prove it is NP-complete as well.


"Ways to make change for a dollar": How to optimize with constraints I'm working on an algorithm that takes a number of unit coins ([1, 2, 5, 10] for example) and a certain amount of money (13 in this case), and figures out how many ways there are to provide change for it. In the case of this testset the solution is 16.

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2
1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2
etc
5, 5, 2, 1
10, 1, 1, 1
10, 2, 1
Total number of ways: 16

I've first tried making a list of these permutations, but that generally was slow and unwieldy. There is no need to give every permutation just the amount of them: 7/10 test cases were able to be done under 5 seconds.

So I went looking around and found this. Where a Haskell solution to a similar problem was used. I just had to make it more general for my needs and translate it in a language I could actually run (e.g. Python). I did and I ended up with the following:

def change(list, number):
    if (number is 0):
        return 1
    if (len(list) is 0):
        return 0
    if (number < list[0]):
        return 0

    return change(list, (number - list[0])) + change(list[1:], number)

print(change([1, 2, 5, 10], 13)) #prints 16 (list needs to be in order btw)

This solution is better then the first one: 9/10 test cases succeeded. However this can be done better! I've yet to talk about the constraints of this assignment.

There are no more then 8 unit coins (len(unit_coins) <= 8)
The unit coins are never more then 250 (unit_coin <= 250)
The amount of money is between 0 and 300 (0 < money < 300)
There is always a unit coin with a value of 1

The last part is important (you can tell, because I've highlighted it). The current solution is absolutely not taking advantage of that, and I thing there's a lot to be gained when this is used in the function.

Does anyone have an idea how to to the thing I just described. Any help would be greatly appreciated. More general answers are also welcomed as this type of optimization isn't exclusive to this perticular algorithm.

P.S. I know Python isn't a very quick language, but that's not the point of this exercise. This exercise is about making the whole algorithm better, not just a specific implementation in a certain language.

The way I understand this, it seems to be the classic coin change problem with a few constraints which you have provided. Although if we try to consider all the subsets of the available coins this problem will definitely take exponential time in terms of number of coins available. (The size of the power-set , each subset has to be considered although few optimizations exist but still it doesn't reduce the time to polynomial). For reducing the time taken we can employ the optimization called memorization.

  return change(list, (number - list[0])) + change(list[1:], number)

If you see the line closely in your solution you can see the problem has overlapping subproblems which will be computed again and again. For optimization we try to remember the results of the subproblems and return this precomputed result if we encounter the same sub-problem again.However, as you can guess there is a space-time trade-off here. For speeding up we need to remember the results for this we need atleast $\mathcal{O}({n})$ space (n is the sum which we are trying to make.).

For overlapping subproblems consider the example of making a sum of N using coins 2,3 and, 5.

Suppose solution is given by F(n), then

let us choose the permutations i can make using 2:

Then F(n) = 1+F(n-2)

Now let us choose coin 3:

F(n) = 2+F(n-5)
.
.
.
.
 We calculate this quantity and return the result.
However suppose if we choose 5 in the starting step.

then F(n) = 1+ F(n-5)

We now have to calculate F(n-5) again. Hence overlapping subproblems exist.

For the constraints which you have mentioned we can add those constraints by maintaining a count of each coin as well as total count of the coins used at each step of the recursive call to our function (In the function which is named $change(list, number)$ in your implementation ) we can check the constraint and add zero as the result of that particular function call as it generated an invalid permutation. valid permutation contributes to a 1 in our function.
Our function will look something like this :

def change(list, number, countCoinsList, totCount):
if (number is 0):
    return 1
if (len(list) is 0):
    return 0
if (number < list[0]):
    return 0
if(countCoinsList[i]<8)
     countCoinsList[i]+=1
     tmp1= change(list, (number - list[i]),countCoinsList,totCount+1)

 tmp2= change(list[i+1:], number,countCoinsList,totCount)
return  tmp1+tmp2;


What problem does cache coloring solve? According to what I have read from two different sources, cache coloring is (was?) required in order to:

Counter the problem of aliasing: Prevent two different virtual addresses with the same physical address from mapping to different cache sets. (According to a CS Stack Exchange Answer)
Exploit the spatial locality property of virtual memory: by guaranteeing that two adjacent blocks of virtual memory (not necessarily adjacent in physical memory), do not map to the same cache index. (According to Wikipedia)

These seem to me to be fundamentally different definitions, and without comprehending the motivation for cache coloring, I can't seem to understand the mechanism for selecting the number of colors required. Are they really one and the same?

If the spatial locality of virtual memory is the primary motivation, is cache coloring really required for VIPT caches, where the index of the cache is derived from the virtual memory to begin with? Or is cache coloring simply used in VIPT caches to get around aliasing?

Both avoiding aliases and avoiding excessive cache conflicts are valid reasons for using page coloring. Requiring page coloring to avoid aliases is unpopular because it places a mandatory constraint on page allocation. In general, modern non-embedded processors do not require page coloring to avoid aliasing.

Avoiding aliasing issues in hardware increases hardware complexity, so earlier processors (and perhaps some more recent embedded processors) chose to place the burden on software. Hardware can avoid aliasing issues in a cache with more index+offset bits than bits in the page offset by (for example):

checking alternate sets on a cache miss (as done by AMD's Athlon; when an alias was detected the block was moved to the current virtual index)
including the virtual address bits used for indexing L1 in a (tag) inclusive L2 (on an L1 miss and L2 hit, if the virtual address bits match the corresponding bits for the request, no action is necessary; if the bits do not match, the appropriate set to probe is known [whether the block is also in L1 could also be stored in the L2 tags to reduce coherence overhead, so some probes might be avoided])
using set prediction to guess the extra physical address bits used for indexing (a misprediction would be discovered after TLB access and corrected)
using reverse translation (physical to virtual) on a cache miss to find possible aliases (I think a PA-RISC implementation used reverse translation for coherence)

Using page coloring to reduce conflicts (for caches with simple modulo a power of two indexing) is less unpopular because the page coloring is not required for correctness. If a particular color becomes scarce, a page can be mis-colored with only a possible reduction in performance. This rationale for page coloring also means that the number of bits colored is less constrained. The (less practical) ideal may be to match all physical index bits for the last level cache with the corresponding virtual address bits, but even coloring just four bits can substantially reduce conflict issues.

It might be worth noting that coloring for alias avoidance need not match virtual address bits with physical address bits. As long as all potential aliases share the same virtual address bits used for indexing, alias issues are avoided. However, matching physical and virtual address bits may be convenient (and provide predictable conflict in physically addressed levels of cache).


Which data structure to use to solve equations? Let's say I have two equations for a geometric object (a rectangle):

$\left\{
    \begin{array}{l}
      x \ge 0 \\
      y \ge 0 \\
      A \ge 0 \\
      P \ge 0 \\
      A = x*y \\
 P = 2*x + 2*y
    \end{array}
\right.$

Now I would like to set the values of some variables, and compute the values of the other ones.

At first, I thought it could be done with simple tree transformations on the AST, but I realized that I was more or less building a full solver.

The easy case is when one side of the equality consists only of constant terms, as it consists of a simple recursive tree evaluation. But the interesting case is when there are several variable bound together in a subtree. For example, for $ (A,P)=(30,11)$ the solution is $(x,y)=(5,6)$ or $(6,5)$

Can arbitrary complex instances of this problem solved just with tree transformations ? Or do I need something more elaborate ?

Which data structure to use to solve equations?

I assume that we are talking about polynomial equations here, because I want to base my answer on a Gröbner basis method. The example problem given in the question contains equations, inequalities, variables and parameters. We can replace inequalities $f(x_1,\ldots,x_n) \geq 0$ by equations with slack variables $f(x_1,\ldots,x_n) - e^2 = 0$. We can convert parameters $P$ into variables by adding equations enforcing their value $P-11 = 0$. We can convert equations $f(x_1,\ldots,x_n)=g(x_1,\ldots,x_n)$ to the form $f(x_1,\ldots,x_n)-g(x_1,\ldots,x_n) = 0$.

$\left\{
    \begin{array}{r}
      A - 30 = 0\\
      P - 11 = 0\\
      x - e_x^2 = 0\\
      y - e_y^2 = 0\\
      A - e_A^2 = 0\\
      P - e_P^2 = 0\\
 x*y - A = 0 \\
 2*x + 2*y - P = 0
    \end{array}
\right.$

Each equation can be represented as a list of its monomials and their coefficients.
A monomial $M$ is a product $M=x_1^{a_1}\cdots x_n^{a_n}$,  where the $a_i$ are nonnegative integers. The vector $[a_1, \ldots ,a_n]$ is called the exponent vector of $M$. A monomial can be represented by its exponent vector. This statement and the preceding description assumes that we have already fixed an enumeration of the variables. There are certainly more efficient ways to store a single equation, but these are just optimizations.

  Can arbitrary complex instances of this problem solved just with tree transformations ?

It depends a bit on what we consider to be a tree transformation, and whether we mean by solved just the symbolic precomputation, or the entire solution process. A Gröbner basis method is able to transform the intial system into a triangular form, with respect to any admissible monomial order. In our case, we will probably want to use an elimination order such that the parameters are smaller than all other monomials, and the slack variables are bigger than all other monomials. The example system will then be transformed to

$\left\{
    \begin{array}{r}
      e_x^2 - x = 0 \\
      e_y^2 - y = 0 \\
      e_A^2 - A = 0 \\
      e_P^2 - P = 0 \\
      x + y - \frac{1}{2}P = 0 \\
      y*y - \frac{1}{2}P*y + A = 0 \\
      A - 30 = 0 \\
      P - 11 = 0 \\
    \end{array}
\right.$

This would be the results of the preprocessing. We can now solve this system numerically by back substitution. So we set the parameters to $P=11$ and $A=30$, solve the quadratic equation for $y$, then get $x$ from the linear equation, and then check the positivity constraints for $P$, $A$, $y$ and $x$. There are two solutions for $y$, so we have to do part of this process twice.

The are only two operations used during the transformation. The first operation is to reduce a polynomial by other polynomials, that is $f$ is replaced by $f-\sum_{g\in G}q_gg$ where the $q_g$ are polynomials. (This should actually be a multivariate division with respect to a monomial order.) The other operation is to add the S-polynomial of two polynomials. The S-polynomial of two polynomials $f$ and $g$ with leading terms $l_f$ and $l_g$ (with respect to a monomial order) is given by $\frac{a}{l_f}f-\frac{a}{l_g}g$, where $a$ is the least common multiple of the leading terms $l_f$ and $l_g$. In a certain sense, one can really call these operations tree transformations, because we just transform polynomials into other polynomials.

One interesting lesson for myself here was that adding the inequalities and parameters didn't really affect the outcome of the Gröbner basis method. We had to choose an appropriate elimination order for the monomial order. However, there are well know fill-in reduction strategies, and any sufficiently complete strategy would have automatically chosen an appropriate order. (The equation system can be seen as a bipartite graph between the variables and the equations, where a variable is connected to an equation if it occurs in the equation. This bipartite graph already contains enough information to determine an appropriate elimination order such that any harm which could be caused by the inequalities and parameters is avoided.)

  Or do I need something more elaborate ?

One major problem is the order in which to apply the transformations. This already starts with the determination of an appropriate monomial order, but doesn't end there. Some of the methods developed for the direct solution of sparse linear systems can also be applied here. In addition, the reduction to an univariate polynomial of high degree is also a bit dangerous, from a numerical robustness point of view.


Why is the complexity of factorial a function of n? When we compute the complexity of calculating factorial of a number $n$ why is it in terms of $n$ instead of the number of the number of bits occupied by the number of bits occupied by $n$ (like we do in number-theoretic algorithms like primality checking etc.)?

Complexity can be expressed in terms of any reasonable measure. For example, when discussing graph algorithms, we usually state the complexity in terms of the number of vertices and/or edges, rather than the number of bits required to write the graph as input, e.g., as an adjacency matrix.

So I guess you've just come across resources that discuss the complexity in terms of the number being "factorialed" rather than the number of bits required to write down that number – I'm sure you'll agree that this is a reasonable measure, even if it's not your favourite one. Further, it's easy to convert between the two: a $k$-bit number can represent values up to $2^k$, so just take the expression you've been given and substitute $2^n$ for $n$.


Prove language is regular let's have these two languages in the alphabet $\{a,b,c\}$:

$L_1 = \{ w \mid w \text{ is a palindrome and $|w| < 200$}\}$

$L_2 = \{ w \mid w \text{ is a suffix of $u$ and $|u|$ is a prime number and $u$ doesn't contain a $c$}\} $

and I have to prove that $L_1 ∪ L_2$ is regular.

So my idea is I have to prove both languages are regular and therefore their union would be regular. $L_1$ is obviously regular since it's finite. I also know that the language consisting of all suffixes of words from a regular language is also regular, so I narrowed it down to proving that

$L = \{w \mid |w| \text{ is a prime number and $w$ doesn't contain a $c$}\}$

any ideas on that one? Thanks in advance.

The language $L$ is not regular, but $L_2$ is. In fact $L_2 = \{a,b\}^*$.
Indeed if $w \in L_2$, then by definition, $w$ is suffix of a word of $\{a,b\}^*$ and thus $w \in \{a,b\}^*$. Thus $L_2 \subseteq \{a,b\}^*$. To prove the opposite inclusion, consider a word $w \in \{a,b\}^*$. Let $p$ be a prime such that $p \geqslant |w|$ and let $u = a^{p-|w|}w$. By construction, $|u| = p$,
$u \in \{a,b\}^*$ and $w$ is a suffix of $u$, and thus $w \in L_2$.


Perfect random number generation using normal numbers This paper describes a computable normal number. One property of normal numbers is that, written in binary, the $i^{th}$ bit is equally likely to be 0 or 1 (in the sense that as $n$ gets large, the number of 1-bits and 0-bits before the $n^{th}$ bit are about the same). Doesn't this mean that the algorithm that computes bits of this normal number is a perfect random number generator? I thought deterministic random number generation is inherently pseudo-random, by information-theoretic limits or whatever. (Also: can anyone figure out the complexity of computing the $i^{th}$ bit using their method? The math in that paper is beyond me).

Finally: many easily-computable irrationals, like $\sqrt{2}$ and $\pi$, are very strongly conjectured to be normal. If that were proven, wouldn't that provide a poly-time perfect random number generator? Which is definitely impossible? What am I missing here?

many easily-computable irrationals, like $ \sqrt{2} $ and $ \pi $

Therein lies your missing bit.  They are in no way easy to compute if you want many of them, as you would for a real world application.  A nuclear detonation simulation or Monte Carlo model of  stock market behaviour requires millions /billions of pseudo random numbers.  It's just that the formulae are simple to write down.  They are not simple to use for digits far  away from the decimal point.

12 trillion digits of $ \pi $ required the following not simple kit and about a week to compute using a BPP variant:-

Even more impressively (or uselessly depending on your point of view), the quadrillionth bit of $ \pi $ (which is a zero) took 1.2 million cpu hours to compute using >1000 computers.   I suppose computers have gotten faster since then, but it'll still be a while before you can do it on an iPhone.

Secondly, you'd be using the same sequence of numbers over and over, which isn't very random.  So a smart chap might then decide to pick random sub sequences of say irrational number $ \frac{1}{ \sqrt{2} } $ to use.  You'd then have to choose which digits /sequences to use, and how would you actually decide those?  Use a random number generator?

In short, it's unfeasible to use this technique for general pseudo random number generation. Which is why no one does.

Smallish caveat.  Very short sequences from irrationals like these are used as nothing up my sleeve numbers in cryptography for variable initialisation.


How to find maximum matching edges in undirected tree Let $B$ be an undirected tree with $|V|$ nodes given as adjacency list. I want to develop a greedy algorithm using pseudo code to find a maximal matching in runtime $\mathcal{O}(|V|)$.

My approach:

Find all leaves. For each leaf if the parent edge has not been seen by another leaf, mark the edge to its parent as matching edge. Now delete all found leaves, its parents and the associated edges of the parents. Start over from the beginning.

Pseudo code:

graph = {
     1: [2, 3],
     2: [1, 4, 5],
     3: [1, 6],
     4: [2, 7, 8],
     5: [2, 9],
     6: [3],
     7: [4, 10, 11],
     8: [4, 12, 13],
     9: [5],
    10: [7, 14],
    11: [7],
    12: [8],
    13: [8, 15, 16],
    14: [10],
    15: [13],
    16: [13],
}
# example graph I used for testing purposes

while we haven't seen all nodes:
    leaves = [i for i in graph if len(graph[i]) == 1]
    seen += leaves
    for leaf in leaves:
        parent = graph[leaf][0]
        del graph[leaf]  # Throw away all leaves
        if not parent in seen:
            del graph[parent] # And throw away their parent
            matching_edges += [(leaf, parent)]
            seen += [parent]
            next_round_nodes += [parent]

But I'm afraid that is not linear, is it?
Because first we look at $|V|$ and perform our algo. Then we do the same with $|V|-c$ leaves, where $c$ could actually be 2, if I understand that correctly, looking at graph which is a "line". So, really that seems quadratic.

TL;DR:

Is my algorithm correct?
What is the runtime?
If it is not linear, what other approach could I chose?

It is correct and runs in linear time. You can run a DFS to find the height and the parent node  of each vertex and visit the vertices according to their heights in ascending order.

The correctness of such algortihms is usually proved using an exchange argument. Assume $M$ is the matching computed by your algortihm and $M_{\mathrm{OPT}}$ an arbitrary maximum matching. Show that you can turn $M_{\mathrm{OPT}}$ into $M$ by removing and adding edges to the matching where its size never gos smaller.


Maximum trailing zeros of the path Problems:

A table with $n$ rows and $m$ columns is filled with number from $1$ to $100$ (duplication allowed). The player starts at $(1, 1)$. He can only move right or down. The goal is to reach $(n, m)$. Let $S$ be the product of numbers the player has met along the way to $(n, m)$. Find maximum number of trailing zeros of $S$ if the player moves optimally.

What I think about this problem is to use Dynamic Programming. $S$ is equal to $2^x\times5^y\times other\ primes$ so the answer should be $min(x, y)$ but finding maximum $x$ or $y$ is not optimal. $min(x, y)$ instead should be maximized. Please help with this problem.

For each cell $(i,j)$, store the set of possible pairs $(x,y)$'s.

Now, DP by scanning row-major from top row to bottom row, for each cell $(i,j)$, only needs to consider $(i,j-1)$ and $(i-1,j)$ (if any), either choose or not to choose $(i,j)$. So from the stored set in $(i,j-1)$ and $(i-1,j)$, compute $(i,j)$'s set easily.

Try to finish the above idea in details. And then code it in your favorite programming language will quickly improve your DPing skill.


Does an optimal path imply the heuristic is admissible? If we are given an A$^*$ path search with some heuristic $h$ that yields an optimal path, without knowing that the heuristic is admissible beforehand, would this imply that $h$ is admissible?

No.

Let us consider an extreme example. Let graph $G$ contain only two nodes, the starting node $s$ and the destination node $t$. The distance of edge $(s,t)$ is 1.

We have a heuristic function $h$, $h(s)=2$ and $h(t)=0$. $h$ is not admissible since $h(s)>1$.

However, using $A^*$ search algorithm, we will end up with the path $s, t$, the unique and, hence, optimal path.

Exercise. Construct a counterexample where there are more than one path.


Shortest path form node X to nodes A, B, C in graph I have an unweighted consistent graph and some node X(the source) and some nodes A, B, C and more. I need to find the shortest paths: X->A, X->B, X->C and so on. Note that the number of goal nodes will not be very big.

If I were looking for only one path I would use BFS. But I'm quite sure how I can use BFS to find all paths to goal nodes.

Time is of the essence here so I wanted to use one BFS call to find all paths at once. I basically only need their costs. But I don't really know how to do that.

Does Dijkstra's algorithm do that?

The ultimate goal is that for every source node(because there are more of them) find the shortest paths to goal nodes. All sources want to find paths to the same goal nodes.
And based on every path cost I want to create a consistent bipartite graph.

Use BFS, and keep prev pointers.  Good textbooks will have a chapter on shortest-path algorithms where they describe how to reconstruct the paths themselves (not just the distances) using prev pointers; use that method, and then you'll be able to reconstruct a shortest path from $X$ to any other node.  Initially the estimated distance to all nodes is $+\infty$.  Whenever you update the distance to something lower, update its prev pointer to point to the node where you came from.


What does $ \forall \alpha_1, \dots , \alpha_n . \tau $ mean formally as a type? I was learning about polymorphic types but I couldn't understand the notation, can someone explain it means (context cs421 UIUC):

$$ \forall \alpha_1, \dots , \alpha_n . \tau $$

its supposed to be a type but I have no idea what it's suppose to mean.

Perhaps writing some of my thoughts or questions might be helpful in clarifying what I'm confused about:

Why is there a dot separating the quantifier and the type
How does this relate to normal FOL? e.g. if I had $$ \forall x \phi(x) $$ that would mean that for all values x can take in the universe at hand, the proposition $\phi(x)$ is true (assuming the whole expression is true, which it may not be but whatever)
Is $\tau$ a function of the (meta?) variables $$ \forall \alpha_1, \dots , \alpha_n $$?
What do $$ \forall \alpha_1, \dots , \alpha_n $$ stand for?
Are $$ \forall \alpha_1, \dots , alpha_n $$ meta-variables? What is their domain?
Could I have a couple of concrete examples of what they are
I am still confused what entails a monomorphic type vs a polymorphic type. In slide 54 they define that a monomorphic type can be a "type variable $\alpha, \beta, \gamma, \delta, \epsilon $". However, I find that very very confusing because consider the value $e$ with type $\alpha$ ($e:\alpha=<e,\alpha>$). What confuses me is that $\alpha$ can be ANY value, so doesn't that mean $e$ is polymorphic? How is that different from specifying the type value pair for that expression $e:\forall \alpha. \alpha$. They both seem the same to me. This is confusing me a lot. Whats the difference?

I think the lectures assume the definition of them its clear but it really isn't. Can I have a more formal specification of it?

For example when we are told $$x:\tau$$ as a notation its not clear at all it really just means the tuple $$ \langle x, \tau \rangle$$ (until I looked it up at Wikipedia). But Wikipedia didn't save my day for this question, unfortunately...

Crossposted: https://www.quora.com/unanswered/What-does-forall-alpha_1-dots-alpha_n-tau-mean-formally-as-a-type

The notation is explained in your course material, e.g. here starting on slide 47.
In the notation $$T = \forall \alpha_1, \dots, \alpha_n.\tau$$ $\alpha_i$ are type variables, the $\tau$ is a monomorphic type, and $T$ is a universally quantified, polymorphic type. While free type variables may occur in $\tau$, the quantified variables $\alpha_i$ do not occur free in $\tau$.

  Why is there a dot separating the quantifier and the type

This is a just a syntactic convention used in type theory. The dot separates the quantifier part from the type it applies to.

  How does this relate to normal FOL? e.g. if I had $ \forall x \phi(x) $ that would mean that for all values x can take in the universe at hand, the proposition $\phi(x)$ is true

There's a strong relationship between logical formulas and types in programming languages, called Curry-Howard isomorphism.

  Is $\tau$ a function of the (meta?) variables $ \forall \alpha_1, \dots , \alpha_n $?

$\tau$ is not a function, it's a monomorphic type. You can think of the quantification as adding more context to this monomorphic type thus making it polymorphic. The quantification basically "hides" the variables from the context the whole expression appears in.

  What do $ \forall \alpha_1, \dots , \alpha_n $ stand for?
  Are $ \forall \alpha_1, \dots , \alpha_n $ meta-variables? What is their domain?

$\alpha_i$ are type variables that (typically) occur free in $\tau$, but are bound by the quantification and do not occur free in $\forall\alpha_i.\tau$ anymore. Like variables in a mathematical expression represent placeholders for concrete values, type variables represent placeholders for more concrete types.

  Could I have a couple of concrete examples of what they are

The most common example of a polymorphic type is the list type $\forall \alpha . \alpha\;\mathsf{list}$ (this is the notation for Ocaml, in Haskell the notation would be $\forall \alpha.[\alpha]$). In your real code this polymorphic type might be used as a monomorphic type when $\alpha$ is replaced by a concrete type like $\mathsf{int\;list}$, $\mathsf{bool\;list}$ or even $\mathsf{(int\;list)\;list}$.

Sometimes you may still deal with polymorphic types, for example the empty list literal $[\,]$ has the polymorphic type $\forall\alpha.\alpha\;\mathsf{list}$. Note that this is different from when you use $[\,]$ in your real code when it usually will be specialized to $\mathsf{int\;list}$ (or whatever concrete lists you are dealing with) when type inference happens. So $[\,]$ may have one polymorphic type or one of many monomorphic types, where the latter are all very different.

The above linked PDF gives more examples on slide 55.


Why is log(n/p) asymptotically less than log(n)/log(p) I'm trying to figure out which is better asymptotic complexity, $O(\log{\frac{n}{p}})$ or $O\left(\frac{\log{n}}{\log{p}}\right)$. $p$ is the amount of parallelism (i.e. number of cores), and $n$ is the problem size. When I plot them in Grapher.app with any constant value for $p$, the first looks better:

But when I try to work out the math it doesn't seem right:

$$
O(\log{\frac{n}{p}}) = O(\log{n} - \log{p})
$$

$O\left(\frac{\log{n}}{\log{p}}\right)$ seems like a better bound than the above since it divides by $\log{p}$ instead of just subtracting it. What am I missing?

I assume that $p > 1$ (which is equivalent to $\log p > 0$, otherwise we have negative-valued functions which are meaningless as complexity measures.

For a given $p$,  $O\left(\frac{\log n}{\log p}\right) = O(\log n)$ since big oh isn't affected by multiplication by a positive constant.
$\log \frac{n}{p} = \log n - \log p$. Since $\log p = o(\log n)$, $O\left(\log \frac{n}{p}\right) = O(\log n)$.

So up to big-oh complexity (or big-theta, for the same reasons), these two classes are the same.

Your diagram doesn't show a visual difference: you need to bring the two curves to the same scale. One is $a \log n$ for some constant $a > 0$, the other is $\log n + b$ for some constant $b$.

If you want to study the variation in $p$, then $O$ or $\Theta$ with respect to the variable $n$ are not good ways of modeling the complexity of your problem. You need more precise approximations that treat multiplicative constants as relevant. The complexity in $p$ is probably relevant to your problem, and is very different. I'm not familiar enouhg with parallelism to know whether it's the right measure to use here, this could warrant a separate question (with more information about what you're modeling). You're going to need express the complexity in terms of $n$ and $p$, and look at how the variation in $p$ (not the complexity itself) behaves for large $n$.


Is "ternary search" an appropriate term for the algorithm that optimizes a unimodal function on a real interval? Suppose that I want to optimize a unimodal function defined on some real interval.  I can use the well-known algorithm as described in Wikipedia under the name of ternary search.

In case of the algorithm that repeatedly halving intervals, it is common to reserve the term binary search for discrete problems and to use the term bisection method otherwise.  Extrapolating this convention, I suspect that the term trisection method might apply to the algorithm that solves my problem.

My question is whether it is common among academics, and is safe to use in, e.g., senior theses, to apply the term ternary search even if the algorithm is applied to a continuous problem.  I need a reputable source for this.  I'm also interested whether the term trisection method actually exists.

The word "bitonic search" can probably refer to this concept. See this book and these lecture notes for instance.


Pipelining and Preemption According to the concepts of Pipelining,

In a single cycle different stages of different instructions are
executed.

Now I have a bit of confusion here, that if a single processing element is there and can perform one processing at a time ,
then -
Do the preemption occurs multiple times in a single cycle in order to complete the different stages of different instructions inside the pipeline ?
If so, then does this mean that clock cycle duration is larger than the time quanta assigned to execute each stage of an instruction ?
For Example -
In Cycle 2 - below given stages of different instructions is to be executed -

IF of instruction5, ID of instruction4, EX of instruction3, MEM of
instruction2,
WB of instruction1

OR the pipelining works only when there are multiple processing elements ? If I am missing something ?
Please explain or provide some helpful links for me to clear my doubts.
Thanks in Advance !

Your question reminds me of an old joke:

If the Atlantic can be crossed in 7 days with one boat, you can cross it in
one day, if you have seven boats available. (there are actually many variants)

Your problem is the problem of assembly lines in general, and that is the technical model of a pipelined processor.

On the assembly line for making car (I am of course simplifying), you
will have one fellow placing the doors, another one placing the
bumpers, one placing the wheels, another painting the car. They all
work at the same time, doing their job in the duration of a single
car making cycle, fixed by the big clock on the factory wall.

Every cycle, the last worker of the line finishes one car, while the first
does the initial steps of making a new one. So there is exactly one
car produced for each cycle. There is a single assmbly line (read:
a single processor), producing one car with each cycle.

But it does not mean that it takes only one cycle to produce a car. It
takes as many as there are stages in the assembly line. The rate of
production (read processing rate) of one car per cycle is only a
average over time.

The idea that that it is more efficient to have specialized workers
working independently. But you do not want to keep them idle, when it
is not their turn on a given car.

And, it may not be necessary that each car is built identically to the
previous one. All you need is that each worker gets his part of the
instruction(s), such as the diameter of the wheels to be placed, or
the color of the paint. So the instructions may change, while going
through the same assembly line to produce cars.

No one ever preempts the line to get something done. But all contributing workers are synchronized.


How to use Parikh's Theorem to show language is not context free Parikh's Theorem  is quite complicated, I understand intuition of that theorem but I don't see how to use that to prove that language is not context free. I kindly ask you to show me how to do, language isn't important, but for definiteness:

$$ L=\{0^m1^n:m>n\text{ or }(m\text{ is prime and }m\leq n)\}$$

If $L$ were context free, then the set
$$ H = \{(m,n) : m > n\} \cup \{(m,n) : m \leq n \text{ and } m \text{ is prime}\} $$
would be semilinear. The set $\{(m,n) : m \leq n\} = \mathbb{N} (1,1) + \mathbb{N} (0,1)$ is also semilinear. The intersection of semilinear sets is also semilinear, so the set
$$ H' = \{(m,n) : m \leq n \text{ and } m \text{ is prime}\} $$
is also semilinear. The projection of a semilinear set is semilinear, and so the set of primes is semilinear. But one-dimensional semilinear sets with asymptotic density zero are finite, whereas the set of primes is an infinite set with asymptotic density zero.


How may an algorithm always color optimally connected bipartite graphs? Let's consider a greedy algorithm for the coloration problem called the Dsatur algorithm, designed by Daniel Brélaz in 1979 at the EPFL, Switzerland.. This algorithm is based on an order of vertices which we can obtain from considering the saturation degree of each vertex $v$ from $G$. The saturation  degree of a vertex $v$ , which we can write as $DSAT(v)$, is the number of color, the number of different colors used in $v$ neighborhood. The idea is to color  first the vertices with a saturation degree high enough to avoid using too many colors.

Data : an undirected (*non-orienté*) connected graph $G=(V,E)$.
Output : all vertices of $G$ colored.

SORT the vertices by decreasing order of degrees.
COLOR a vertex of maximum degree with color 1.
While it exists vertices not colored do
  CHOOSEa vertex $v$ with max DSAT
  COLOR $v$ with the smallest possible color
  UPDATE DSAT for all neighbors of v

How to show that DATSUR Algorithm always  color optimally connected bipartite graphs ?

My attempt

I think I have to prove it by the absurd :

As far as it is a conected graph it can't be colored by one color solely.
If there were three colors returned by the algorithm Dsatur, taht would mean that a vertex would return $Dsatur(v)= 2$ (it exists two neighbors with two different colors). Which is impossible. But why ?

That would mean that it gives three kind of different colors... But I don't know how to show why this is impossible... Can you help me ?

You can prove an even stronger claim. Consider the following algorithm:

Let $v_1,\ldots,v_n$ be an ordering of the vertices such that for $i>1$, each $v_i$ is connected to at least one of $v_1,\ldots,v_{i-1}$.
Go over all vertices $v_1,\ldots,v_n$ in order, and color each one with the smallest available color.

This algorithm also uses (at most) two colors to color a connected bipartite graph. The property of the ordering that I highlight, which is satisfied by the ordering produced by the Dsatur algorithm, suffices to guarantee that the algorithm uses the minimal number of colors.
To prove that this algorithm works for a connected bipartite graph with bipartition $V_1 \cup V_2$, where $v_1 \in V_1$, prove by induction that if $v_i \in V_j$ then $v_i$ gets colored $j$.


Can we convert an NFA to a regular expression of polynomial length? Can we convert an NFA having $n$ states to a regular expression of length $\mathrm{poly}(n)$?

In contrast, it is well known that a regular expression of length $n$ can be easily converted to an $\mathcal{O}(n)$-state NFA.

Using the concept of star height, Gruber and Holzer showed in Finite Automata, Digraph Connectivity, and Regular Expression Size that there exists a constant $C>1$ and a sequence of languages $L_n$ over $\{0,1\}$ which can be accepted by DFAs having $n$ states, but for which every regular expression has length at least $C^n$.


Functional data structure fast to add and unorded deletion I am looking for a functional data structure that would work in this role.

Adding items to the struct happens often. Removing items from the struct happens as often as adding them but I have no way of knowing what order the deletion happens in. Over the long term addions will equal removal Rarely I need all items currently in the struct

I thought of using a queue but out of order removal from a queue is expensive.

My recommendation is a straightforward hash map. If you have a good hash function for your distribution of keys, the time complexity for adding and removing (with an arbitrary key) is amortized $O(1)$.

EDIT: Hash maps can be purely functional if you want (example), they just become a whole lot less efficient. I don't think it's theoretically possible to get lower than $O(\log n)$, which is what you get from using a red-black tree as the backend. The linked HAMT implementation is also $O(\log n)$, just with a significantly smaller hidden constant.


Context free grammar for $\{ a^i b^n a^n \mid i \ge 0, n \ge 0 \}$ Give a context-free grammar for the following language: $\{ a^i b^n a^n \mid i \ge 0, n \ge 0 \}$

So far, this is the solution that I have been able to come up with, though I am not sure how accurate it is:

$$\begin{align*}
S &\to aSa \mid X \\
X &\to bX \mid a \mid \varepsilon
\end{align*}$$

I worked this out from outside first, which gives me the first and last a's and then used the second rule to get the b's or a's after.

The reason I came up with that answer, I thought the grammer need to start and end with "a" and then have b's in between those a's.

So for each letter with different power we need to have a rule? That is, for $a^i$ we need a rule and for the $n$ power we need another one ?

You could break down the language into simpler parts, e.g., you can generate languages separately for $a^i$ and $b^na^n$, then concatenate them in the end (we know that CFG's are closed under concatenation).

In your case, you can do

  A $\rightarrow$ aA | $\epsilon$

to generate $a^i$, and

  B $\rightarrow$ bBa | $\epsilon$

to generate $b^na^n$, then concatenate by doing:

  S $\rightarrow$ AB


What functions can combinator calculus expressions compute? A combinator expression (let's say in the SK basis) can be thought of as a function that maps combinator calculus expressions to combinator calculus expressions. That is, one can think of an expression $X$ as a function $X:L \to L$, where $L$ is the set of all syntactically valid combinator expressions in the SK basis. This mapping is performed by applying the input to the expression, and then reducing to normal form to get the output.

Since the SK basis is Turing complete, one might naïvely think that there exists a an SK expression $X$ that implements any computable function from $L$ to $L$. However, this clearly isn't the case, since the result of reduction will always be in normal form. This means there is no way for an expression to have an output that isn't in normal form.

So instead, I could think of SK calculus expressions as mapping $L'$ to $L'$, where $L'$ is the set of SK expressions in normal form. Is it the case that, for any computable map $f:L'\to L'$, there is an SK expression $X$ that implements this map? Or are there further restrictions on the set of functions that can be computed by combinator calculus expressions in this way?

To get the ball rolling, and in hopes of other people giving deeper and more detailed answers on the structure of the $\lambda$-definable functions $L'\to L'$, let me cite Corollary 20.3.3 from Barendregts' The Lambda Calculus, Its Syntax and Semantics (aka "the bible").

  Corollary 20.3.3: The function $\delta:L'^2\to L'$, defined by
  $$ \delta(M, N) = \cases{\mathrm{True}\mbox{ if }M=_{\beta\eta}N\\ \mathrm{False}\mbox{ otherwise}}$$
  is not definable in the untyped $\lambda$-calculus, i.e. there is no term $D$ such that
  $$D\ M\ N =_{\beta\eta} \delta(M,N)$$
  for all $M,N\in L'$.

The proof involves considerations on Böhm trees which give a rather strong characterization of the possible "actions" of arbitrary lambda terms on normal forms. In particular, for any non-constant closed term $F$, on can find $n\in\mathbb{N}$ and $P_1,\ldots,P_n$ such that
$$ F\ x\ P_1\ldots P_n =_{\beta\eta} x\ Q_1\ldots Q_k$$

For some $k$, $Q_1,\ldots,Q_k$. This drastically constrains the possible forms of a hypothetical $D$ that implements $\delta$, showing with a little work that such a $D$ cannot exist.


Context-free grammar from language I'm trying to come up with a context-free grammar for the following language:

$$L = \{a^mb^nc^{m+n}\mid 0 \le n \le m\}$$

My thinking is that i can rewrite this to

$$L = \{a^mb^nc^nc^m\mid 0 \le n \le m\}$$

and then create the grammar

$$
\begin{align*}
S &\rightarrow aSc \mid B\\
B &\rightarrow bBc \mid \epsilon
\end{align*}
$$

The problem is that this grammar doesn't capture $0 \le n \le m$ and I can't figure out how to do this. Any help would be greatly appreciated.

Hint: is the language $L' = \{a^n b^n c^{2n} \mid n \ge 0\}$ context-free?


Why does coNP⊆NP∖P imply that the polynomial hierarchy collapses? I was looking for some information on 1-in-3 SAT and came across this paper, last updated 9 days ago, which claims that the Polynomial Time Hierarchy collapses "to the level above P=NP". That's quite exciting if you ask me, although I don't have the toolkit to understand the actual proof. My question is about something much simpler.

Specifically, in the abstract on arxiv, the author writes,

  Our proof shows the structure formerly known as the Polynomial
  Hierarchy collapses to the level above P=NP. That is, we show that
  coNP⊆NP∖P.

Could anyone help me understand why these two statements are equivalent?

I believe the claim is more commonly written as $coNP \subseteq NP/poly$, but that of course does not immediately answer your question.

The fact that this implies that the polynomial hierarchy collapses is shown in Theorem 2 here:

Chee-Keng Yap. Some consequences of non-uniform conditions on uniform
classes. Theoretical Computer Science, 26:287–300, 1983. doi:10.1016/
0304-3975(83 ) 90020-8

If I understand correctly, $coNP \subseteq NP/poly$ is shown to be equivalent to $coNP/poly = NP/poly$ (unnamed corollary on page 292), and this would then imply $\Pi_3 = \Sigma_3$ (Theorem 2), implying collapse of the further hierarchy. For an actual proof, if you have access to the paper, I'll refer you there, I am not familiar enough with it to attempt an explanation now.

On an unrelated note, I believe the paper you are citing to be incorrect (but that would probably warrant a separate question?)


When can a greedy algorithm solve the coin change problem? Given a set of coins with different denominations $c1, ... , cn$ and a value v you want to find the least number of coins needed to represent the value v.

E.g. for the coinset 1,5,10,20 this gives 2 coins for the sum 6 and 6 coins for the sum 19.

My main question is: when can a greedy strategy be used to solve this problem?

Bonus points: Is this statement plain incorrect? (From: How to tell if greedy algorithm suffices for the minimum coin change problem?)

  However, this paper has a proof that if the greedy algorithm works for the first largest denom + second largest denom values, then it works for them all, and it suggests just using the greedy algorithm vs the optimal DP algorithm to check it.
  http://www.cs.cornell.edu/~kozen/papers/change.pdf

Ps. note that the answers in that thread are incredibly crummy- that is why I asked the question anew.

A coin system is canonical if the number of coins given in change by the greedy algorithm is optimal for all amounts.

The paper D. Pearson. A Polynomial-time Algorithm for the Change-Making Problem. Operations Reseach Letters, 33(3):231-234, 2005 offers an $O(n^3)$ algorithm for deciding whether a coin system is canonical, where $n$ is the number of different kinds of coins. From the abstract:

  We then derive a set of $O(n^2)$ possible values which must contain the smallest counterexample. Each can be tested with $O(n)$ arithmetic operations, giving us an $O(n^3)$ algorithm.

The paper is quite short.

For a non-canonical coin system, there is an amount $c$ for which the greedy algorithm produces a suboptimal number of coins; $c$ is called a counterexample.  A coin system is tight if its smallest counterexample is larger than the largest single coin.

The paper Canonical Coin Systems for Change-Making
Problems provides necessary and sufficient conditions for coin systems of up to five coins to be canonical, and an $O(n^2)$ algorithm for deciding whether a tight coin system of $n$ coins is canonical.

There is also some discussion in this se.math question.


What would be the practical consequences of ZPP=exptime What would be the practical consequences of ZPP=exptime.
It would be pretty ridiculous if the was true but what if it was?

If ZPP = EXPTIME then NP $\subseteq$ ZPP, which implies NP $\subseteq$ BPP.  As described in Russell Impagliazzo's informal paper "A personal view of average-case complexity", we would be living in a world he calls Algorithmica.

Algorithmica is the world in which $P = NP$ or some moral equivalent, e.g. $NP \subseteq BPP$. [...]
Such a method of automatically producing a solution for a problem from the method of recognizing a valid solution would revolutionize computer science. Seemingly intractable algorithmic problems would become trivial. Almost any type of optimization problem would be easy and automatic; for example, VLSI design would no longer use heuristics, but could instead produce exactly optimal layouts for problems once a criterion for optimality was given. Programming languages would not need to involve instructions on how the computation should be performed. Instead, one would just specify the properties that a desired output should have in relation to the input.

And so on.  Read the paper for more extrapolation on this topic, along with the consequences of less fantastic algorithmic complexity conjectures being true.  And observe @Dmitry's caveat: Knowing a problem is in a tractable complexity class isn't the same as having an efficient algorithm for the problem that takes advantage of that fact.
Theoretically, ZPP = EXPTIME implies EXPTIME $\subseteq$ BPP.  Since we already know P $\subset$ EXPTIME we have P $\subset$ BPP as well, which means there are some polynomial-time randomized algorithms that cannot be derandomized.  This is another way of saying that pseudo-random number generators will never be as effective as true randomness, algorithmically, which would be a very interesting result.
We know that BPP is low for itself, i.e. BPP$^{BPP}$ = BPP.  Therefore an EXPTIME no more powerful than BPP must be low for itself as well, which removes the separation between some exponential classes, e.g. EXPTIME = EEXP = EE = EEE.  This in turn makes some decidable but intractable problems simply decidable. For example, deciding the truth of first-order mathematical statements expressed in Presburger arithmetic would now be in BPP.
We also know that BPP $\subseteq \Sigma^P_2 \cap \Pi^P_2$.  Together with EXPTIME $\subseteq$ BPP this means that the polynomial hierarchy collapses to the second level; the oracle calls above that level do not offer any more computational power, as EXPTIME is powerful enough to capture all the rest of PH.  Since P is strictly a subset of BPP and P = NP would collapse PH completely, bringing P and BPP together, ZPP = EXPTIME would imply P $\neq$ NP.  Interestingly, I think NP = co-NP would still be an open problem.  But with the proof writing power you'd get from EXPTIME being tractable, I doubt the problem would be open for long.


Undecidability of closure under reverse of language accepted by TM Prove that the following problem is undecidable using a reduction: Given a Turing machine $S$, does $S$ accept a word $w$ iff it accepts its reverse $w^R$?

There is a solution here, which I don't understand. We reduce from the halting problem. Given a Turing machine $M$ and a word $w$, we construct a Turing machine $M_1$:
M1(x) =
   simulate M on w
   if M accepts w
      if x = 01
         accept

The machine $M_1$ accepts only 01 and all other strings will be rejected. Then
MA(<M>, w) =
   Construct M1 as above
   if ML accepts <M1>
      reject
   else if ML rejects <M1>
      accept

so the Turing machine $S$ will accept all strings except $w=01$.
Why is the string 01 the only string which is accepted by $M_1$? Why it cannot be 10 instead of 01, for example? It doesn't make sense to me.
If $w$ were 01 and $L$ would also contain 10 and 01, then it should also be accepted, no?
Would anyone please explain me the whole process and especially the Turing machine $M_1$? Why does this work?

Ok , first consider this clearer proof which takes a similar approach :
Assume S is decidable , we show a reduction ATM ≤m S , obtaining a contradiction
We map <M,w> to <M'> such that :
M' = " on input x :
If x = 01 accept ,
If x = 10 reject ,
If x = 10 simulate M on w , if M accepts w accept , if M halts and rejects w then reject
Now , if M accepts w , meaning <M,w>   ∈ ATM  , then the L(M') would be =  {01 (which is always accepted) , 10 (which is only accepted if M accepts w) } and thus <M'> ∈ S
If M rejects w or loops on w , meaning <M,w> does not belong to ATM , then L(M') = {01} and thus <M'> does not belong to S , completing our reduction , and thus if S is decidable ATM is decidable which is a contradiction , thus S is undecidable
The point is to construct M' such that it accepts a string and it's reverse if M accepts w so that also S accepts M' or accept a single string if M rejects w so S rejects M' since M' doesn't also accept the reverse of the string
You could have used any 2 different strings as long as one is the reverse of the other , instead of 01,10 feel free to use 110,011 hopefully you get the point
Following the link the reduction is from ATM , the only difference is that if M accepts w , then L(M') is ∅ so S accepts M' and if M rejects w or loops on w L(M) = {01 (which could have been chosen to be any string) } and thus M' does not belong to S
Finally it's worth reminding that ATM is the language where M accepts w , while Halting is the language where M halts on w , you may find it a good exercise to try showing a reduction from Halting to S , the proof would be very similar


What does actually reasonable mean when we say "reasonable model of computation"? I have seen in many text when the author says "reasonable model of computation". What does it really mean?

It doesn't have a precise meaning. What an author considers "reasonable" largely depends on the context. It is usually meant to exclude certain pathological cases.


Algorithms for logical synthesis Let's say that I want to map some string of binary digits to a single binary digit of output, like the below:

$
\begin{array}{l|l}
\text{Input}&\text{Output}\\
\hline
0001&0\\
0011&1\\
0111&0\\
1111&1
\end{array}
$

If inputs besides those listed are given, I don't care what the output is.  I only care about the inputs listed.

I can eyeball the truth table and come up with the below:

$Output = \lnot (Input_0 \oplus Input_1 \oplus Input_2 \oplus Input_3)$

However, that isn't the only solution, and might not be the solution using the fewest number of operations.

Are there any algorithms to figure this out for arbitrary length inputs mapping to a single binary digit of output?

Ultimately I'm trying to solve for mapping $M$ bits of input to $N$ bits of output.  I figure an ok way to do this might be to break it into $N$ problems of mapping $M$ bits of input to a single bit of output so am starting with that.

I'm actually going to be implementing something using a standard modern computer (aka desktop CPU), so I know that there is some extra complexity if I want better efficiency, due to the fact that operations happen not on single binary digits, but on eg. words.  Not only will efficiency depend on minimizing the number of operations done on each bit, there will also be efficiency to be gained by letting "bit programs" share operations where they can, if that makes sense.

One step at a time, but I bring this up in case there is an answer which encompasses my future needs as well.

Edit:
I've found these pages which talk about minterms and karnaugh maps and understand what they are talking about, however I also know that they aren't guaranteed to be the minimal circuit, and they also mention that some other algorithms are used in more complex circuit design (but they don't say what they are)
https://www.facstaff.bucknell.edu/mastascu/eLessonsHTML/Logic/Logic2.html
https://www.facstaff.bucknell.edu/mastascu/eLessonsHTML/Logic/Logic3.html

This is an instance of logic synthesis.  A standard approach is to use Karnaugh maps or the Quine-McCluskey algorithm.  Finding the minimal circuit is hard (see circuit minimization), but there are tools and techniques that often work reasonably well in practice.  For instance, you can use the Espresso tool to help with this; there are other tools for this task as well.

See also Creating a logical circuit and Working out the connectives (And, Or, Not) in a Truth Table that has the outputs.