NFA-epsilon: epsilon loops, and how do I deal with them? I am currently studying Automatons and have one, albeit simple, question about NFA-epsilon 'loops'
I know that a string can advance using epsilon without having anything read. So my first question would be, if you had a chain of epsilon-arches, would you just jump to the end of the chain instantaneously (Figure 1) ?
My other question is; At the end (Figure 1) at the accept state there is en epsilon-arch going back to a previous state, would this cause a loop and in-turn cause the string to never halt, or would it just create another fork (endlessly?)?

My last question is, how would I approach said NFA-epsilon example with these example strings: 1011100, 0101111?
To me the second string would be accepted, while the first one would be rejected because it has 2 zeroes at the end of the string. I am unsure though!

(Figure 1)

Thanks in advance! :)

if you had a chain of epsilon-arches, would you just jump to the end of the chain instantaneously

I am not sure for "instantaneously", but I would say it accepts the empty string $\epsilon$.

  would this cause a loop and in-turn cause the string to never halt, or would it just create another fork (endlessly?)?

Your input string will be accepted. On any input, a NFA runs by creating many branches of computation in parallel and if one of them reaches the accept states, after it reads the last symbol of the input, then your string is accepted and the entire computation halts. You kind of choose at least onе fork that leads the NFA to the accept state.

  how would I approach said NFA-epsilon example with these example strings: 1011100, 0101111?

Right the first string is not accepted, the second one is accepted.


Ensure groups of four 3-tuples have 9 unique numbers Note: I know the numbers are arbitrary, but this problem about this size has practical implications. It is an applied algorithm problem.

Suppose you have 200 bins. Each bin would be very happy to have the integer sequence: 1, 2, 3, 4, 5, 6, 7, 8, 9. And the algorithm would be very happy if all bins get that.

The algorithm is allowed to choose four 3-tuples from a collection of 800 3-tuples. It will assign assign 4 of them to each bin. So each bin will have four 3-tuples assigned to them. These 3-tuples have the following properties:

They are pseudo-randomly generated all at once as a collection of 800 3-tuples.
Each number in a generated 3-tuple is unique. For example, (1, 1, 2) and (7, 4, 4) are impossible but (1, 2, 3) and (8, 2, 9) are possible.
Each value within the 3-tuple can only be a number from 1 to 9. For example, (10, 3, 15) is an impossible tuple. The 3 could occur, but 10 and 15 could not.

A corollary from point 1 is that it could be the case that some integers occur less than the amount of bins that exist. In such a case the application would be very happy if as many bins get a numerical sequence from 1 to 9 and the other bins get as close as possible to such a sequence. For example, suppose that the number 9 has been randomly generated in 180 3-tuples, then at least 20 bins will not get the number 9, but they hopefully should be able to get the integers 1 to 8.

Here is an example of 2 bins and 8 3-tuples. The following numbers are pseudo-randomly generated.

(3, 8, 2)
(2, 1, 5)
(2, 7, 8)
(7, 8, 5)
(7, 8, 4)
(7, 5, 8)
(7, 9, 5)
(4, 7, 3)

Assigning them to two bins as optimal as possible by the requirements yields:

Bin 1 - Sequence: 1, 2, 3, 4, 5, 7, 8, 9
(2, 1, 5)
(4, 7, 3)
(7, 9, 5)
(7, 8, 5)

Bin 2 - Sequence: 2, 3, 4, 5, 7, 8
(2, 7, 8)
(7, 8, 4)
(7, 5, 8)
(3, 8, 2)

Note: in this particular example there is no 6. There is one 1 and one 9. This means that the 1 and the 9 automatically go to Bin 1. The integer 6, well it simply isn't there, so it cannot be assigned to a bin.

My first question: Design an algorithm that ensures the most optimal solution.

My second question: is a generalized or analogous version known as a certain problem or field in mathematics?

I suppose this problem is a variant of the set cover problem. However, instead of covering a universe, 200 'universes' need to be covered. Or said in another way: the universe needs to be covered 200 times in such a way that the cover can be split up into 200 groups of four 3-tuples.

I suspect finding the optimal assignment will be NP-hard in theory and possibly hard in practice, but it might be possible to find a near-optimal solution.

One approach is to express this as an instance of integer linear programming, and use an off-the-shelf ILP solver.  Let $x_{i,j}$ be a zero-or-one integer variable, with the intended meaning that $x_{i,j}=1$ implies the $i$th tuple is assigned to the $j$th bin, and $y_{j,d}$ another zero-or-one variable, with the intended meaning that $y_{j,d}=1$ means that digit $d$ is covered in bin $j$.  Then you can write down a set of linear inequalities on the $x$'s and $y$'s that captures what constitutes a consistent and valid solution.

For instance, the constraints might be: $\sum_j x_{i,j} = 1$ (each tuple is assigned to one bin), $\sum_i x_{i,j}=4$ (each bin receives 4 tuples), $y_{j,d} \ge x_{i,j}$ if the $i$th tuple contains digit $d$, and $y_{j,d} \le \sum_i x_{i,j}$ where the sum is over all tuples $i$ that contain digit $d$.  Now you want to maximize the linear objective function $\sum_{j,d} y_{j,d}$.  Then, you could use an off-the-shelf ILP solver to try to find an optimal solution to this linear program, or ask it to report the best solution it can find within a given time bound.

I don't know if there is a better approach.  You could look at algorithms for exact cover to see if any of them can be adapted to your setting.


On $NP=\Sigma_2^P$ from non-deterministic time? We know $NP=\bigcup_{k\in\Bbb N}NTIME(n^k)$ and $\Sigma_2^P=NP^{NP}$.

Does $\Sigma_2^P\subseteq\bigcup_{k\in\Bbb N}NTIME(n^k)$ also hold (we can do $O(n^k)$ queries to $NP$ oracle which runs in non-deterministic $O((n^k)^c)$ time which is  non-deterministic $O(poly(n))$ time)?
Is there a reason we cannot conclude $NP=\Sigma_2^P$ from this?

From this $NP=PH$ should hold.

Here is a simpler "proof" using the same ideas. I will show that NP=coNP. Indeed, suppose that $L \in \mathsf{coNP}$, and consider the machine which on input $x$, invokes the NP-oracle $\overline{L}$, and outputs the opposite value.

What goes wrong in this argument? Let us use the "witness" definition of NP: a language $L$ is in NP if there exist a polynomial $p$ and a polytime predicate $P$ such that $$ x \in L \Longleftrightarrow \exists |y| \leq p(|x|) \, P(x,y). $$
Now suppose that $L$ is in coNP, that is,
$$ x \in L \Longleftrightarrow \forall |y| \leq p(|x|) \, \lnot P(x,y). $$
(We get this by applying the previous definition to $\overline{L}$.)

Our machine deciding $L$ nondeterministically accepts as input $x,y$ and outputs $\lnot P(x,y)$. However, this accepts a different language $L'$ given by
$$ x \in L' \Longleftrightarrow \exists |y| \leq p(|x|) \, \lnot P(x,y). $$
The difference is the quantification — existential instead of universal.

Informally, this shows that nondeterministic machines cannot simulate nondeterministic oracles. However, they can simulate deterministic oracles: $\mathsf{NP}^L = \mathsf{NP}$ for all polytime $L$. This is because an NP-machine can simulate the computation of $L$ on any given input directly. The same cannot be said about nondeterministic oracles.


Union of a language in P and a language in NP\P TRUE or FALSE Statement:

  Assume that $P \neq NP$. Then, for all languages $L_1$ and $L_2$, if $L_1$ is in P and $L_2$ is in NP but not in P then $L_1 \cup L_2$ is in NP but not in P.

I have a doubt about the point: $L_1 \cup L_2$ is in NP but not in P.

I know P is a subset of NP, then $L_1 \cup L_2$ is in NP (because $P \subseteq NP$), but the sentence "is in NP but not in P"
it puzzles me.

From an Hint (by Yuval Filmus), the statement is FALSE because if $L_1=Σ^∗$ then $L_1 \cup L_2=Σ^∗$. I know $Σ^∗$ is in P (i.e., a TM which accepts all strings), and the statement is FALSE.


Move tokens from s to t as fast as possible Let $G=(V, E)$ be an unweighted and undirected graph, and $s, t \in E$.

The problems starts with $n$ tokens on $s$.

The goal is to move theses tokens to $t$ in a minimum of rounds with these rules :

Each token can be moved up to once per round (a movement being when you transfer the token from $v$ the vertex that holds it, to $w \in N_G(v)$).
Each vertex $v \in V\backslash \left\{s, t\right\}$ can hold at most one token ($s$ and $t$ are unconstrained).

So far, what I've thought to is :

If $N_G(s)=0$ or $N_G(t)=0$, it is not possible.
If $N_G(s)=1$ or $N_G(t)=1$, you can just apply a BFS from $s$ to find the shortest path, then transfer every token one by one trough this path.
If $N_G(s) \geq 2$ and $N_G(t) \geq 2$ you can apply a maximum flow algorithm on $G$ with $1$ as capacity for every edge. If the maximum flow is $1$ then you can apply a BFS and transfer every token through this path again. However if the maximum flow is $\geq 2$, then I don't really see what to do (having a maximum flow $\geq 2$ doesn't even guarantee there are multiple paths as nodes can hold at most $1$ token, while max flow tests only for edges, and even if there are multiple paths in some cases it can be better to use only the shortest path - e. g. for $2$ tokens if you have to paths but one is at least to edges longer -).

Does this problem have a name? What topic of graph theory does it belongs to? Are there efficient algorithms to solve it?

Menger's theorem states that the maximum number of $s$-$t$ (internally) vertex-disjoint paths is equal to the minimum size of an $s$-$t$ vertex cut. Let the common value be $m$.  Then it can be shown that the asymptotic number of rounds required is $n/m + O(1)$.

Using the vertex disjoint paths, we can route $n$ tokens in $n/m + O(1)$ rounds, where the constant depends on the graph $G$ (but not on $n$).  This gives an upper bound.

On the other hand, every token must pass through the vertex cut, and at most $m$ can do so at any given round, so routing $n$ tokens takes at least $n/m$ rounds.  (For each token, there must be a first time at which it reaches a vertex in the cut. Each such time can repeat at most $m$ times, since at most $m$ vertices of the cut can be occupied at any given time. So the number of rounds is at least $n/m$.)  This gives a matching lower bound.

From these two bounds, we deduce that the asymptotic number of rounds required is $n/m + O(1)$.


Hoare Logic for Factorial I came across this hoare logic for factorials but I don't quite understand it. We multiply F and X but we're not adding up all values of F so how do we get the sum/factorial at the end?

Precondition: $\{ X > 0 \land X = x \}$

$F := 1$
while $X > 0$ do
$\quad F := F \cdot X$
$\quad X := X - 1$
od

Postcondition: $\{F = x!\}$

What the Hoare invariant state is the following:

  If you run the code with $X$ equal to some value $x > 0$, then at the end, $F$ will have the value $x!$ ($x$ factorial).

You can check that this is indeed the case.


Unambiguous but nondeterministic context-free language? Whenever deterministic context-free languages are discussed, the webpage/textbook would always give a side note saying that although deterministic context-free languages are never ambiguous, unambiguous context-free languages may still be nondeterministic.

However, they never give an example. Is there a short, simple example of a context-free language that is

unambiguous
but nondeterministic

$\{ww^R\mid w\in\{a,b\}^∗\}$ should do the job. The rest is up to you regarding proofs, such as providing an unambiguous grammar.

From Example of Non-Linear, UnAmbiguous and Non-Deterministic CFL?
Third answer by Google.

Another one found similarly at Non-Deterministic CFLs:  $\{x^ny^n \;\mid\; n \geq 0\} \cup \{x^ny^{2n} \;\mid\; n \geq 0\}$


Store - Order Problem Lets there are n stores.

A customer order x items. All the stores might not have all the items from the order.

So find the store/combination of stores that can serve the order request such that the combination that contain least number of stores.

Edit:

Example: Lets say there are 4 stores. User is ordering item 1, 3, 6, 7

Store 1 sells item 1, item 6
Store 2 sells item 1, item 2, item 3, item 4, item 5
Store 3 sells item 6, 7, 8, 9, 10
Store 4 sells item 5, item 7

The combinations of stores that can fulfil the orders
{ 2, 3 } , { 1, 2, 4}

So optimal solution in this case is {2,3}

P.S: I was asked this question in an interview. What would be the algorithm that would fit into the problem?

Your problem is essentially the same as set cover, a classical NP-complete problem.

In set cover, we are given sets $S_1,\ldots,S_n$ together covering a universe $U$, and the problem is to find the smallest subset that still covers $U$. The only difference between this and your problem is that you want to cover some $V \subseteq U$. You can get the classic formulation by intersecting all sets with $V$.


Can a loop be expressed by only the sequence of statements and the choice of statements? The theorem of structured programming says that any algorithm can be expressed by those three control structures:

Sequence
Selection
Iteration

Isn't it possible to rewrite any loop using a finite sequence of statements and choice between statements? Isn't this what compilers do? Can't we thus omit the third structure and stay equally expressive?

I convinced myself that this is not possible, I was indeed mixing up the selection structure with conditional jumps; but they're not equally expressive.

The conditional jump is as powerful as both selection and iteration together; this is what compilers use to rewrite both choice statements and loop statements.

As a counterexample for rewriting any loop using only the first two control structures, think of an infinite loop. This can not be rewritten using only sequence and selection while it can be rewritten using sequence and conditional jumps. So, we would lose expressiveness if we went without iterations.

Addendum to clear up the terminology:

Sequence
Selection (synonymous to choice), for example IF or SWITCH
Iteration (synonymous to loop), for example WHILE or FOR


Does Heapsort work in time o(n log n) in the best case? Is it possible for Heapsort to work in time $o(n\log n)$ on certain inputs?

For example in case of Insertion sort it is possible, however when it comes to Quickssort it is not possible.  What about Heapsort? I tried to find an input array such that Heapsort will be working in $o(n\log n)$.

I ask you is it possible? Some permutation? The same elements?

The paper: The Analysis of Heapsort by Schaffer and Sedgewick shows that

  Theorem 1: Heapsort requires that at least $\frac{1}{2} n \lg n - O(n)$ data moves for any heap composed of distinct keys.

and that

  Theorem 3: The average number of data moves required to Heapsort a random permutation of $n$ distinct keys is $\sim n \lg n$.

It also mentions that

  If equal keys are allowed, the best case is clearly linear [3]: consider the case of a heap with all keys equal.

The citation to [3] here is TechReport: On Heapsort and its Dependence on Input Data.


What is the mathematical principle of buddy algorithm? The buddy algorithm is:

  The buddy for any block of size $2^k$ is another block of the same size, and with the same page frame number except that the kth bit is reversed.

Example:

If the block size if $2^3$ and the start page frame number(aka pfn) of this block is 0xC, the page frame number of the buddy of this block is pfn=0x4.

This algorithm is very ingenious but I have two questions.

Why the buddy of 0xC is 0x4 instead of 0x14?
Why reversing the kth bit does the trick?

References:
http://research.cs.vt.edu/AVresearch/MMtutorial/buddy.php

The buddy algorithm is just treating your memory of size $2^K$ as a binary tree where the root is the entire memory, and each node of size $2^k$ has two children which are the two equal size subblocks of size $2^{k-1}$.

The buddy system restricts you to only splitting a node into its two children (which are then the two buddies), or taking two buddies and coalescing them into their parent.  This restriction is put in place entirely to enable the cute/ingenious trick of identifying your buddy by flipping the $k$th bit.

Other than being cute, there is very little to recommend buddy systems as memory allocators.  More general systems that allow you to coalesce with any neighbor, even if it's not your buddy, are slightly more expensive to compute per deallocation, but result in much less internal and external  fragmentation in practice.


Expected Number of Trials I have an algorithm problem that I want to share with you and I want to get some idea how can I solve it.

Problem statement:
You have to reach th Nth floor of a building by using a particular elevator: there is only one button that will take you from floor i to floor i+1 with probability p(i) or to floor 1 with probability 1-p(i).
you are given the number of floor. next you are given N-1 number that represent the probability p(1)...p(n-1)
you should output the expected number of turns needed to reach the Nth floor.

INPUT:

3

0.5 0.25

OUTPUT

13

What I know:
if you have an event that can happen with a probability p the expected number of turns until this event occur is 1/p.

Now for the questions:
Is the probability of getting to the last floor the product of all probabilities?
I think this is wrong because we cannot apply it to the example 1/(p1*p2) != 13

What kind of subjects (articles) should I read to solve this problem and problems similar to this.

If you have an idea feel free to share it but, please, don't give me the solution.

Thank you very much

Denote by $E_i$ the expected number of turns it takes get to the $N$th floor from the $i$th floor. You are interested in $E_1$. The numbers $E_i$ satisfy the recurrence
$$
E_i = 1 + p_i E_{i+1} + (1-p_i)E_1,
$$
valid for $i < N$, with a base case $E_N = 0$.

In order to solve this system of equations, multiply the $i$th equation by $p_1 \cdots p_{i-1}$ to get
$$
p_1 \cdots p_{i-1} E_i = p_1 \cdots p_{i-1} + p_1 \cdots p_i E_{i+1} + [p_1 \cdots p_{i-1} - p_1 \cdots p_i] E_1.
$$
Summing this for $1 \leq i \leq n-1$, we get
$$
E_1 = 1 + p_1 + p_1p_2 + \cdots + p_1 \cdots p_{n-2} + (1 - p_1 \cdots p_{n-1}) E_1,
$$
and so
$$
\begin{align}
E_1 &= \frac{1+p_1+p_1p_2\cdots+p_1\cdots p_{n-2}}{p_1 \cdots p_{n-1}} \\ &= \frac{1}{p_1 \cdots p_{n-1}} + \frac{1}{p_2 \cdots p_{n-1}} + \cdots + \frac{1}{p_{n-1}}.
\end{align}
$$


How to do a reverse topological sort using depth first search? I'm doing a replacement for the venerable make utility that will support, among other things, automatic cleaning. The utility figures out automatically what files and directories are targets, and then deletes those, if the user wishes to do a clean operation. However, a file may reside in an automatically created directory, meaning I should do a topological sort for the targets, where every file has an arc towards the parent directory, and every directory has an arc towards its parent. So, for example:

objhierarchy/obj/foo.o has an arc towards objhierarchy/obj
objhierarchy/obj has an arc towards objhierarchy

What complicates the things is that the files need to be deleted in the reverse order. So, in the example given, you need this order: (1) objhierarchy/obj/foo.o, (2) objhierarchy/obj, (3) objhierarchy.

Topological sort seems like a good solution, but it gives the opposite order. So, a topological sort of the directory parent graph would yield (1) objhierarchy, (2) objhierarchy/obj, (3) objhierarchy/obj/foo.o.

A solution could be a buffer of pointers that is reversed in-place (or just iterated in the reverse order), but I would like to avoid allocating extra memory.

What is the best way to get the files deleted in the reverse order? Can the topological sort algorithm based on depth first search be modified to call some callback function in a reverse order?

In order to get the files in the desired order, simply follow the following rule: A node can be deleted iff all of its children have been deleted. This is the same as a postorder traversal of a tree.

Let's say you use a container $S$ for your search structure (stack for DFS or queue for BFS). Now, we create a stack $T$ which will in the end will be the files to be deleted in order (starting from the top of the stack). Due to the nature of DFS/BFS on trees, every node will be pushed to and popped from $S$ before its children. Therefore, every time we pop a node from $S$, we add it to the stack $T$. At the end of the search $T$ will maintain the property that all nodes appear deeper in the stack than their children. Keep in mind this only works if the file node structure is a tree not a DAG.


Any algorithm polynomial time with infinite space? If I had an arbitrary amount of space at my disposal, couldn't I vectorize/parallelize any program in such a way that it would only need one step? For example, I could let my CPU have an inbuilt look-up-table for the function (x+y)/z with 3 input values instead of doing the calculation in 2 steps.
Does there exist any proof that something like that isn't possible?

If you don't allow preprocessing, then the answer is no (at least when talking about standard models of computation such as the Turing machine or a random access machine). The reason follows from the fact that (in reasonable models) writing to memory requires time, hence the amount of memory used is upper bounded by the running time.

The notion of preprocessing is captured in complexity by machines who have access to an advice, alongside with the input. For example, the class $\mathsf{P/Poly}$ consists of all problems solvable using polynomial machines, who given a length $n$ input, have access to an advice string of length $poly(n)$. Note that the advice is the same for all inputs of the same length, you can think of this advice as your preprocessing. If, as in your example, you allow too much preprocessing, then everything is solvable in a single step, which makes this situation uninteresting (and indeed, it is not realistic to imagine you have the answer ready for any possible input). In the language of Turing machines who take advice, you can say that $\mathsf{P/EXP}$ with random access to the advice is the class of all languages (your advice can include the answers for all inputs). This means that allowing the advice to be too long makes the game too easy.


Noncontext free for quotient Have such exercise:
Let $L_1=\{a^{2n}b^n|n\geq1\}^*$

and $L_2=\{b^na^n|n\geq 1\}^*b$

Prove, that $L_1, L_2$ are context free, while quotient $L_1/L_2$ is not context-free.

(This is  home exercise, which I am not sure what to make of it. 3rd one)

Anyway, proving $L_1, L_2$ are CFL is trivial.

For $L_1$:

S->aaSb|$\epsilon$

For $L_2$

S->Ab

A->bAa|$\epsilon$

So far so good, grammar can be constructed, i.e CFL. Fine.

But quotient.. Lets list few words for $L_1$: $\epsilon$ then: aab, aabaab, aabaabaab, $\dots$ then aaaabb, aaaabbaaaabb, $\dots$ and so on - string under Kleene, which contains twice as much $a$ than $b$

Now about $L_2$ words: b then bab,babab,bababab,$\dots$ then bbaab,bbaabbaab,$\dots$, ie - $(b^na^n)^*b$

But.. Only words in $L_1$ are of format which ends in suffix ...ab are where $n=1$: $aab,aabaab,\dots$, moreover - if we take string from $L_1$, for example $aabaab$, we kinda remove trailing $b$ ($aabaa$), after which we can't really remove anything else, in this particular case we would have to remove suffix $bbaa$, but there is no such suffix in word from $L_1$

So, all in all - quotient, to my understanding is $L_1$, with only difference that there is very last b always removed. And it feels to me like CF, what am I doing wrong?

Edit: According to comment, I have mistake in my thoughts, which is reasonable, we dont have to Kleenize $n$ in each substring.

Ie $aaaabbaab$ for $L_1$ is possible. Ok, now lets look exactly at $aaaabbaab$ - first remove trailing $b$, get $aaaabbaa$. Now $bbaa$ - resulting in $aaaa$.. So all in all, quotient is still $L_1$, which has some arbitrary suffix removed. Still feels CF to me

Work backwards, from right to left.
Try to find which strings of the form $a^*$ belong to $L_1/L_2$. So find matches of strings $w_1\in L_1$ and $w_2\in L_2$ such that at the start only a string of the form $a^*$ sticks out: $w_1= a^k w_2$.


Does no parents imply variable independence in a Bayesian network? If A and B don't have parents on a Bayesian network, does that mean we can infer A and B are independent? Whatever the answer is, please explain how you get to it.

Yes, they would be unconditionally independent.

This is simply a consequence of the factorisation of a Bayesian network into conditional probabilities. For example, this network will factorise as $p(A,B,C)=p(C|A,B)p(A)p(B)$, implying that $p(A,B)=p(A)p(B)$, which is the very definition of unconditional independence for the parent-less nodes $A$ & $B$:

As for the factorisation $p(A,B,C)=p(C|A,B)p(A)p(B)$ that led us here, this is definitional for Bayesian networks. I recommend Section 3.3 of Barber for a fuller explanation.

On the other hand, they are conditionally dependent if conditioned on a collider. For example, nodes $x$ and $y$ are graphically conditionally dependent when conditioning on the collider $z$ in each of these 2 BNs:

Chapter 3 of the same source contains a fuller description of BNs and similar graphical networks, together with various possible tests for conditional independence.


How can I decide manually whether two CTL formulae are equivalent? Assume I have two formulae $\Phi$ and $\Psi$ (over the same set of atomic propositions $AP$) in CTL. We have that $\Phi \equiv \Psi$ iff $Sat_{TS}(\Phi) = Sat_{TS}(\Psi)$ for all transition systems $TS$ over $AP$.

Given that there are infinitely many transition systems, it's impossible to check them all. I thought about using PNF (Positive Normal Form, allowing negation only next to literals) because judging from its name it should give me the same formula for $\Phi$ as for $\Psi$ iff they are equivalent, but I'm not convinced this works in all cases (you could say, I'm not convinced PNF is actually a normal form).

For example, take $\forall \mathrm{O} \forall \lozenge \Phi_0 \stackrel{?}{\equiv} \forall \lozenge \forall \mathrm{O} \Phi_0$ (where $\mathrm{O}$ is the next operator and $\lozenge$ is the eventually operator). I'm looking for a way do do this by hand.

It seems to me that "$\Phi≡\Psi$" is equivalent to "Neither $(\Phi ∧ ¬\Psi)$ nor $(\Psi ∧ ¬\Phi)$ is satisfiable".

Therefore deciding equivalence is as difficult as deciding satisfiability, since "$\Phi$ satisfiable" is equivalent to "not ($¬\Phi≡\top$)".

In this article there is a mention of a an exponential procedure to decide satisfiability in CTL, so it should be enough to run the algorithm on the two formulas I wrote above.

PS: I am not at all an expert in this field, so please check what I wrote. If this makes sense, I will remove the various "seems" and "should".


Confused between 2 phase locking and 2 phase commit I understand that both algorithms are very different, but what I don't understand is whether they achieve the same thing in the end. 2PC is for atomic commits and 2PL is for serializable isolation. But don't they both achieve the two things? don't these goals imply each other in the end?

These are two different things that have two different goals.

The two-phase locking protocol is designed to guarantee serializability for transactions that access concurrently a single, centralized database, using a locking mechanism. So its goal is to maintain the consistency of a centralized database, avoiding “bad” interferences among concurrent, different, transactions that operate on the same data.

Two-phase commit protocol, instead, concerns the execution of distributed transactions is a distributed database, and guarantee that a single distributed transaction, seen as “set of processes in a network system”, coordinates the work of those processes even in case of temporary system failures (for instance, in case of network failure). So the protocol has the objective of avoiding situations in which a certain transaction commit its operation is a node (that is in a part of the distributed database), but aborts in another node (that is in another part of the same distributed database).

Of course you can see both protocols as having the final objective is to maintain the “consistency” of the database, centralized in a case, distributed in the other. But this is really a generic point of view.


Greedy Algorithm: Optimal Substructure I don't have a CS degree but I have recently taken up studying algorithms very seriously.
I have been studying greedy and dynamic programming for days and I come across the below definition a lot, seems they all come from the same source, but I do not understand what it means, it is one of the vaguest definitions I have ever come across. I wonder if someone can please help me explain this.
e.g. I don't understand what they mean by optimal solution, what constitutes an optimal solution, how can I define it?

In computer science, a problem is said to have optimal substructure if
an optimal solution can be constructed from optimal solutions of its
subproblems. This property is used to determine the usefulness of
dynamic programming and greedy algorithms for a problem

Greedy algorithms are often used when solving optimization problems, like finding the maximum or the minimum of a certain quantity, under certain conditions. Solutions that satisfy those extrema are called optimal solutions.
To answer your question, let's look at a simple example, change-making problem:

Given a set of integer values of coins $C = \{c_1, …, c_n\}$ and an amount $W$, what is the minimum number of coins to add-up to the amount $W$?

The classical greedy approach is the following:
While W > 0
   pick the largest coin c that is <= W
   W <- W - c

For example, with $C = \{1, 2, 5\}$ and $W = 13$, you will pick $5$, $5$, $2$ and $1$, and you can show that the minimum number of coins required is indeed $4$.
However, this algorithm does not always provide an optimal solution. For example, if $C = \{1, 4, 5\}$ and $W = 8$, the greedy algorithm will choose coins $5, 1, 1, 1$ when there is a solution $4, 4$ using less coins.
Back to the topic of your question, the change-making problem does not have an optimal substructure, unless you add some hypotheses on $C$


generic way to convert imperative if-then-else statements into functional style? In this question, I asked about a reference for translating imperative code to functional code. I want to ask a more specific question here.

How, in general, do we translate into functional style, a statement of the form:

if (cond) then
    do x;
else
    do y;

I know that functional languages have if-then-else statements but the expressions are only allowed to be pure. Is there a general way of doing this translation?

As was mentioned in comments to the other question, any imperative program with side-effects can be trivially transformed into a pure program by simply lifting it into the IO monad, for example.

Or, by implementing an interpreter for an imperative language in a pure language.

That is, however, not good functional design. (Although, embedding a Domain Specific Language for side-effects into a program to provide limited and isolated side-effects in clearly demarcated sections of the code could certainly be considered good design.)

There is no general way of doing this translation. You need to understand what the original problem is that the program is solving, then solve that problem in a functional manner.


With a list of opcodes for a virtual machine, is it possible to assign a number to every possible program of size n that can be run on that machine? Say you have some virtual machine with < 100 numbered opcodes that fully specify its behaviour. Is there an easy way to order and enumerate all possible programs of less than n instructions, the result being that a particular number refers to a particular program? Preferably with natural numbers and short programs at the begining.
As this list would be combinatorially large, it would be helpful to assign these numbers without running the programs or loading them into memory.

There is no need to assign a number. The program already is a number.
If you have $m$ opcodes and your program has $n$ instructions, then it can be interpreted as an $n$-"digit" number written in base $m$.


The space complexity of a function that allocates space based on the input value and not size What is the space complexity of the following hyphotetical function:

void function(int n) {
  int[] array = new int[n]; // allocate array of size n
  return;
}

My intuition tells me that it is not O(n). Because the function will allocate an array of size n where n is the value of the input and not the size. The input size is constant because it is a single integer.

It is $O(n)$ and, more precisely, $\Theta(n)$.
What might be confusing you is the fact that the length of the encoding of the parameter $n$ will only be $\Theta(\log n)$, meaning that the value of $n$ (and hence the space required by the function) is exponentially larger than the size of the input to function (i.e., the number of bits needed to represent $n$).

To summarize both the following statements are true:

function(n) requires linear space w.r.t. the value of its parameter $n$, i.e., the asymptotic space complexity of function(n) is $O(n)$;
function(n) requires an exponential amount of space w.r.t. the length of the encoding of its input.


Understanding Expected Running Time of Randomized Algorithms I want to understand the expected running time and the worse-case expected running time.

I got confused when I saw this figure (source),

where $I$ is the input and $S$ is the sequence of random numbers.

What I don't understand from the above equation is why the expected running time is given for one particular input $I$?

I always thought that for a problem $\pi$,  $E(\pi) = \sum_{input \in Inputs}(Pr(input)*T(input))$ , isn't this correct?

So, let's assume Pr(x) is the uniform distribution, and we are to find the expected running time of the problem of searching an element in a $n$ element array using linear search.

Isn't the expected running time for linear search,

$$E(LinearSearch) = \frac{1}{n}\sum_1^ni $$

And what about the worst case expected running time, isn't it the time complexity of having the worst behavior? Like the figure below,

I would highly appreciate if someone can help me understand the two figures above.

Thank you in advance.

There are two notions of expected running time here. Given a randomized algorithm, its running time depends on the random coin tosses. The expected running time is the expectation of the running time with respect to the coin tosses. This quantity depends on the input. For example, quicksort with a random pivot has expected running time $\Theta(n\log n)$. This quantity depends on the length of the input $n$.
Given either a randomized or a deterministic algorithm, one can also talk about its expected running time on a random input from some fixed distribution. For example, deterministic quicksort (with a fixed pivot) has expected running time $\Theta(n\log n)$ on a randomly distributed input of length $n$. This is known as average-case analysis. Your example of linear search fits this category.
A related concept is smoothed analysis, in which we are interested in the expected running time of an algorithm in the neighborhood of a particular input. For example, while the simplex algorithm has exponential running time on some inputs, in the "vicinity" of each input it runs in polynomial time in expectation.


Given an array of N integers, how can you find M elements to remove so that the array will end up in sorted order? Here is my approach

First I compute the longest non decreasing sub-sequence in $N \log N$ time. Algorithm to do this (that only uses arrays and binary search) can be found here:
http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms

Let's suppose the longest subsequence has $L$ elements. Then if $L < N - M$, there isn't any way to solve the problem since there's no subsequence of length $N - M$ that's still sorted.

Otherwise, just remove the $N - L$ elements that aren't in the subsequence, and then remove more at random until exactly M total have been removed. In all this is an $N \log N$ algorithm.

I want to know, is there any more efficient algorithm (i.e. $O( N)$ ) to solve this problem ?

You can adapt the algorithm described in Wikipedia so that it runs in time $O(N\log (N-M))$ if you're only interested in increasing sequences of length at most $N-M$. Judging by the existence of an $N\log N$ lower bound for the general case, $O(N\log(N-M))$ might be optimal. (Your problem is equivalent to the decision problem of whether there exists a non-decreasing subsequence of length $N-M$; this can be reduced to strictly increasing subsequences by adding appropriate $\epsilon$s.)


Write a CFG for the language $\{0^n 1^a 2^b \mid n = a+b\}$ I would like some help for the computation theory.
There is a PDA that accepts the language $\{0^n 1^a 2^b \mid n = a+b\}$, so how can I express it into context free grammar? Any help would be appreciated!
That's what I was trying, I am not sure if it is correct or not
S -> 0SA | 0SB | empty
A -> 1
B -> 2

Unfortunately your grammar generates mixed $1$s and $2$s.
You can try something like this:
$S\rightarrow 0SB | S'$
$S' \rightarrow 0S'A | \varepsilon$
$A\rightarrow 1$
$B\rightarrow 2$
Notice that I don't know if in your problem $n$ can be $0$ or not (and similarly for $a$ and $b$), so maybe you have to fix something.
Anyway, here the idea is starting generating first some $0$s an all the $2$s, and then add the remaining $0$s and the $1$s: it is similar to the "standard" grammar used to generate $0^n 1^n$.


Why don't people use Fermat's little theorem to check if number is prime? There're a lot of examples of code for checking if a number is prime. Why don't people use Fermat's little theorem, i.e. this simple formula

$\qquad a^{p-1} \equiv 1 \pmod p$,

to check if a number is prime?

Expanding on Karolis's answer, the probabilistic primality tests used in practices, the Miller-Rabin test and the Solovay-Strassen test, are both based on modifications of the test you suggest, also known as the Fermat primality test. (Same for the less common Baillie-PSW test.) The problem with the Fermat test is that it is fooled by some composites known as Carmichael numbers.

The Solovay-Strassen test replaces the test $a^{n-1} \equiv 1 \pmod{n}$ with the similar formula $a^{(n-1)/2} \equiv \left(\frac{a}{n}\right) \pmod{n}$. Here $\left(\frac{a}{n}\right)$ is a Jacobi symbol, which for prime $n$ and $a \nmid n$ is equal to $1$ if $a$ is a quadratic residue modulo $n$ (i.e. has a square root modulo $n$) and to $-1$ if $a$ is a quadratic non-residue modulo $n$. There is a GCD-like algorithm for computing the Jacobi symbol, which makes the test feasible. It can be shown that if $n$ is an odd composite, then at least half the $a$s fail this test.

The Miller-Rabin test relies on the (similar) property that $1$ has two square roots modulo a prime, but more modulo composites. The idea is to check that $a^{n-1} \equiv 1 \pmod{n}$ and $a^{(n-1)/2} \equiv \pm 1 \pmod{n}$. If $a^{(n-1)/2} \equiv 1 \pmod{n}$, then we check that $a^{(n-1)/4} \equiv \pm 1 \pmod{n}$. And so on. The test fails if for some $k$, $a^{(n-1)/2^k} \equiv 1 \pmod{n}$ but $a^{(n-1)/2^{k+1}} \not\equiv \pm 1 \pmod{n}$. It can be shown that if $n$ is an odd composite, then at least three quarters of the $a$s fail this test (and so less iterations are needed compared to the Solovay-Strassen test).


Polynomial time algorithm - Matching pairs of vertices Let T be a tree with root r and S a set with an even number of vertices of T. Design a polynomial time algorithm that finds |S|/2 simple and disjoint paths in edges matching pairs of vertices in S. The following figure shows an example in which S consists of the six vertices enclosed in circles and three paths (denoted by three different types of dotted lines) that match those vertices.

Hint: Gain intuition by making instances like the one in the figure and observing what happens when you walk the entire border of the tree almost touching it, but not really doing that; then think about how to express the idea of such walk with a recursive algorithm.

I tried to analyze the problem but I don't really understand how to express it as a recursive algorithm, could you help me, please?

The idea is to use recursion. Let us suppose that the children of the root $r$ are $v_1,\ldots,v_d$, and let $S_1,\ldots,S_d$ consist of those elements of $S$ in the subtree rooted at $v_1,\ldots,v_d$, respectively.

One easy case is when $r \notin S$ and $|S_i|$ is even for all $i$. In this case, we can simply recurse on the subtrees. There are two complications that arise in the general case:

Some $|S_i|$ might be odd.
The root might belong to $S$.

The two complications are related, but let us tackle them one by one. Suppose first that $r \notin S$. If $|S_i|$ is odd for some $i$, then we would like to fix that. The only reasonable way is to add $v_i$ to $S_i$ if $v_i \notin S_i$, and to remove $v_i$ from $S_i$ is $v_i \in S_i$. We now solve the modified problem recursively, and have to somehow derive a solution for the original problem.

Let us introduce some notation: $O$ is the set of $i$ such that $|S_i|$ is odd, and $S'_i$ is the set $S_i$ after modification (adding or removing $v_i$). Consider a solution for the new instance. We will derive a solution for the original instance by pairing up the indices in $O$. Suppose that we chose to pair $i,j$, and consider the solutions for $S'_i,S'_j$. There are three cases to consider:

$v_i \in S_i$ and $v_j \in S_j$. In this case we add a path from $v_i$ to $v_j$ via $r$.
$v_i \notin S_i$ and $v_j \notin S_j$. In this case we add a path from $v_i$ to $v_j$ and "erase" $v_i,v_j$. That is, in the solution to the new problem, $v_i$ is connected to some $w_i$ in its subtree, and $v_j$ is connected to some $w_j$ in its subtree. We connect $w_i$ and $w_j$ via the path $w_i-v_i-r-v_j-w_j$.
$v_i \in S_i$ and $v_j \notin S_j$. In this case we add a path from $v_i$ to $v_j$ and "erase" $v_j$. That is, in the solution to the new problem, $v_j$ is connected to some $w_j$ in the subtree. We connect $v_i$ and $w_j$ via the path $v_i-r-v_j-w_j$.

When $r \in S$, we only have to modify the above strategy a little. We arbitrarily pair $r$ with some $i \in O$, and then proceed much as above. This time there are only two cases:

$v_i \in S_i$. In this case we simply connect $r$ and $v_i$.
$v_i \notin S_i$. In this case we add the edge between $r$ and $v_i$ and "erase" $v_i$. That is, in the solution to the new problem, $v_i$ is connected to some $w_i$ in its subtree. We connect $r$ and $w_i$ via the path $r-v_i-w_i$.


Travelling Salesman which can repeat cities In the TSP problem, we usually assume a complete graph. If we can only visit each city once, we need a complete graph to ensure that there will be a path from every city to every other city. This is easy to accomplish as if there is no straight path between A and B, we can simply assign a new edge whose length is the shortest path between A and B.

However, if we have a sparse graph, maybe we can benefit from not having a complete graph. In this case, we might be forced to repeat vertices. If our graph is only 3 cities, and only two edges, connecting (1, 2) and (2, 3), then the solution must repeat city 2: 1 - 2 - 3 - 2 - 1.

I am struggling to find examples of TSP in the scientific literature which assume a non complete directed graph. Any known references? Any keywords I may be missing? In this case, cycles are allowed.

I am especially interested in how we could separate subtour inequalities when cycles are present.  I am hoping for a solution based on integer linear programming and branch-and-bound, and am wondering how to add subtour elimination inequalities.  Any ideas?

This is directly equivalent to metric TSP. That is, TSP in which the distances obey the triangle inequality: for all cities $A$, $B$ and $C$, the distance from $A$ to $B$ is no greater than the distance from $A$ to $C$ to $B$.

As Raphael points oun in the comments, you can reduce an instance of your problem to metric TSP by setting the distance from $A$ to $B$ to be the length of the shortest $A$–$B$ path in the original graph. This shows that your problem is no harder than metric TSP. But, conversely, every instance of metric TSP is already an instance of your problem. This is because, in metric TSP, the triangle inequality guarantees that it's never necessary to revisit a vertex so allowing revisiting doesn't change the optimal solution.


Show that if L is regular, then third(L) is also regular. Hint: Construct an ϵ-NFA from the DFA for L I'm having trouble with proving the following, and my attempt and confusion is mentioned further below.
PROBLEM STATEMENT:

For a string $w = a_1 a_2 a_3 a_4 a_5 a_6 a_7 \dots$, define $third(w) = a_3 a_6 a_9 \dots$
Then, for a language $L$, define $third(L) = \{third(w) : w ∈ L\}$.
Show that if $L$ is regular, then $third(L)$ is also regular.
(Hint: Construct an ϵ-NFA from the DFA for $L$.)

TEACHER'S SOLUTION:
If $L$ is regular, it is accepted by some DFA, say $A = (Q,Σ,δ,s_0,F)$.
We will construct an ϵ-NFA $B$ such that $L(B) = third(L(A))$.
Here, you need four copies of $A$.
Formally, $B = (Q × \{1,2,3,4\}, Σ, ρ, F × \{2,3,4\})$,
where $ρ =$
${\{(⟨p, 1⟩, ϵ, ⟨q, 2⟩) : (p, a, q) ∈ δ}$, for some ${a ∈ Σ\}}$ ${∪}$
${\{(⟨p, 2⟩, ϵ, ⟨q, 3⟩) : (p, a, q) ∈ δ}$, for some ${a ∈ Σ\}}$ ${∪}$
${\{(⟨p, 3⟩, a, ⟨q, 4⟩) : (p, a, q) ∈ δ\}}$ ${∪}$
${\{(⟨p, 4⟩, ϵ, ⟨p, 1⟩) : p ∈ Q\}}$.
(Do not confuse ρ and p.)
WHAT I DO UNDERSTAND:
• I understand how Cartesian products work.
WHAT I MAY OR MAY NOT UNDERSTAND:
• Are the ${(p, a, q) ∈ δ}$ parts another way of saying ${δ(p,a) = q}$?
• I suspect that the gist of the proof is to modify the initial DFA of L with ϵ transitions, so that there are only non-ϵ transitions for every third symbol in any particular string of L, w, being analyzed. And, I suspect that that's the purpose of the stuff with the angle brackets.
• I suspect that the purpose of taking the Cartesian product of Q and ${\{1,2,3,4\}}$ and the purpose of taking the Cartesian product of F with ${\{2,3,4\}}$ is to have a state for each copy of A, where ${⟨p, 1⟩}$ represents the state p of the first copy of A (but is technically a state of B, not A).
• Should ${⟨s_0, 1⟩}$ be the start state of B, such that B's n-tuple is a 5-tuple, rather than a 4-tuple, and that that 5-tuple is ${B = (Q × \{1,2,3,4\}, Σ, ρ, ⟨s_0, 1⟩, F × \{2,3,4\})}$?
WHAT I DON'T UNDERSTAND:
• I don't understand what the transitions regarding the four copies (defined by B's transition relation, ρ) achieve exactly.
• Also, why does one need four copies of A? Can't one just add those additional transitions to a single copy of A?
Any input would be GREATLY appreciated!
Edit for adding new information (#1):
Thanks to all of you for responses. :)
I have a comparatively small question:
The transition relation, ρ, is also function in this case, because each state of the NFA B only has one transition to another state, per input, right?

And, I suspect that that's the purpose of the stuff with the angle brackets.

This is just a way to write elements of a cross product. For example: $$\lbrace 1,2\rbrace\times\lbrace 3,4\rbrace = \lbrace \langle 1,3\rangle,\langle 1,4\rangle,\langle 2,3\rangle,\langle 2,4\rangle \rbrace$$

  I suspect that the gist of the proof is to modify the initial DFA of L with ϵ transitions, so that there are only non-ϵ transitions for every third symbol in any particular string of L, w, being analyzed.

Basically yes. The construction creates four copies of $A$. The first three copies behave just as $A$ behaved originally with a minor twist: If state $q$ is reached, instead afterwards the state $q$ in the next copy of $A$ is reached. (I will ignore the $\epsilon$ edge inscriptions for now. I come back to this later.)

Thus, initially we are in state $s_0$ of the first copy of $A$ (written as $\langle s_0,1\rangle$). Then, some letter $a$ is read. Let's say that in $A$ this would lead from $s_0$ to state $p$. Now, in the new automaton, this leads to state $p$ in the second copy of $A$, i.e. $\langle p,2\rangle$. Next, some letter $b$ is read. Let's say that this would lead from $p$ to $q$ in $A$. In the new product automaton, this leads from $\langle p,2\rangle$ to $\langle q,3\rangle$, i.e. it also moves on to the next copy of $A$.

The effect of this construction so far is that we not only "behave as $A$ would behave", but also that we know if the current letter position is exactly a multiple of three, or a multiple of three plus one, or a multiple of three plus two: All multiplies of three end up in the first copy of $A$, all multiplies of three plus one in the second copy, etc.

Now, let's go back to the $\epsilon$ edge inscriptions: So far, the automaton that was constructed just behaves as the original automaton $A$. But we want it to read just every third letter and skip the other two. We do this by replacing all edge inscriptions in the first two copies of $A$ with $\epsilon$. This will lead to a lot of non-determinism, because now all outgoing edges have the same label. The idea here is that when we have an input $a_3a_6a_9\dots$ the automaton "guesses" what the missing symbols $a_1, a_2, a_4, \dots$ could be. Each such guess is represented by taking an $\epsilon$-labelled edge. Only the third copy of $A$ is not modified, so this copy still actually reads $a_3a_6a_9\dots$

  What does the fourth copy do?

(No one actually wrote this question, but I need it for structure ;-) )

The fourth copy in the construction from the question actually does not do anything. When the automaton is in state $\langle q,4\rangle$, the only option to continue is to go to state $\langle q,1\rangle$ (via an $\epsilon$-transition). Thus, the fourth copy can just be removed and instead we go directly to $\langle q,1\rangle$.

  Can't one just add those additional transitions to a single copy of A?

First, there are no additional transitions (well, okay, the transitions from $\langle q,4\rangle$ to $\langle q,1\rangle$ can count as additional transitions). Instead, the construction keeps the original transitions but replaces some of the inscriptions with $\epsilon$.

Next, a single copy is not enough.
The automaton still has to keep track on the position in the input.
As an exercise, construct a DFA accepting $(abcd)^*$ and try out the construction on it.


number encoding effect on complexity I started reading the book "Data Structures and Network Algorithms" by Robert Tarjan, which is a classic (but a bit outdated - 1983) and I am a bit perplexed by the  paragraph in the first chapter, Page 3, first paragraph. I have attached the paragraph below:

  An important caveat concerning random-access and pointer machines is that if the machine can manipulate numbers of arbitrary size in constant time, it can perform hidden parallel computation by encoding several numbers into one. There are two ways to prevent this. Instead of counting each operation as one step (the uniform cost measure), we can charge for an operation a time proportional to the number of bits needed to represent the operands (the logarithmic cost measure). Alternatively we can limit the size of the integers we allow to those representable in a constant times log n bits, where n is a measure of the input size, and restrict the operations we allow on real numbers. We shall generally use the latter approach; all our algorithms are implementable on a random-access or pointer machine with integers of size at most n for some small constant c with only comparison, addition, and sometimes multiplication of input values allowed as operations on real numbers, with no clever encoding.

Would somebody be able to explain this paragraph or point me to some references that elaborates it better?

If we allow numbers to be unbounded while keeping the unit cost model (each operation costs one unit), we get a very powerful machine. For example, here is how to solve 3SAT in this model. Recall that a 3CNF is a formula of the form

$$ (x_1 \lor \lnot x_2 \lor x_3) \land (x_1 \lor x_4 \lor \lnot x_5) \land \cdots. $$

Here $\lor$ is logical OR, $\land$ is logical AND, and $\lnot$ is logical NOT. The 3CNF is an AND of clauses, each of which is the OR of three literals; a literal is either a variable or its negation. The 3SAT problem asks whether a given 3CNF is satisfiable, that is, whether there is a truth assignment to the variables under which the formula evaluates to TRUE.

Suppose the given 3CNF has $n$ variables. For a formula $\varphi$, let $T(\varphi)$ be a "bit-vector" of length $2^n$, indexed by truth assignments to the variables, such that the bit at position $x$ is the truth value of $\varphi$ evaluated at the assignment $x$ (i.e. 1 if $\varphi$ is TRUE and 0 if $\varphi$ is FALSE). We order the truth assignments in lexicographic order; for example, if $n=2$ then the truth assignments are $(F,F),(F,T),(T,F),(T,T)$, given in the format $(x_2,x_1)$. Continuing the example, $T(x_1) = 1010$ and $T(x_2) = 1100$ (we read the bits from right to left), both in binary notation.

Consider now the following operations:

For each $i$, we can compute $T(x_i)$ as follows:
$$
\begin{align*}
T(x_i) &= \sum_{a=0}^{2^{i-1}-1} \sum_{b=0}^{2^{n-i}-1} 2^{2^i b + 2^{i-1} + a} \\ &= 2^{2^{i-1}} \sum_{a=0}^{2^{i-1}-1} 2^a \sum_{b=0}^{2^{n-i}-1} (2^{2^i})^b \\ &=
2^{2^{i-1}} (2^{2^{i-1}}-1) \frac{(2^{2^i})^{2^{n-i}}-1}{2^{2^i}-1} \\ &=
\frac{2^{2^{i-1}} (2^{2^{i-1}}-1)(2^{2^n}-1)}{2^{2^i}-1}.
\end{align*}
$$
Given $T(\alpha),T(\beta)$, we can compute $T(\lnot \alpha), T(\alpha\land\beta), T(\alpha\lor\beta)$ using bitwise NOT, AND, OR.

In this way, we can efficiently compute $T(\varphi)$, where $\varphi$ is the given 3CNF. The formula $\varphi$ is satisfiable iff $T(\varphi) \neq 0$. This gives a polynomial time algorithm for 3SAT in the unit cost model. Obviously something is wrong and needs fixing, which is what Tarjan is getting at.


Is Wikipedia's formal definition of NP correct? Wikipedia's formal definition of NP based on deterministic verifiers states:

  A language L is in NP if and only if there exist polynomials p and q,
  and a deterministic Turing machine M, such that

  For all x and y, the machine M runs in time p(|x|) on input (x,y)
  For all x in L, there exists a string y of length q(|x|) such that M(x,y) = 1
  For all x not in L and all strings y of length q(|x|), M(x,y) = 0

I'm not an expert in the field but the first bullet point leads me to think that M must run in time p(|x|) regardless of the size of y, which doesn't seem to be true, at least if M gets to read y completely. What if |y| > p(|x|)?

Is the first bullet point of the definition correct? Shouldn't it be

  For all x and y, the machine M runs in time p(|x|+|y|) on input (x,y)

Can you point me to an authoritative source with the original definition of NP based on deterministic verifiers?

I am currently reading "Introduction to the Theory of Computation" by Sipser and think that it is a great introduction to complexity (as well as automata and computability). Here are his definitions of Verifier and NP:

Definition 7.18: A verifier for a language $A$ is an algorithm $V$, where $A = \{ w \mid V \text{ accepts } \langle w, c \rangle \text{ for some string } c \}.$ We measure the time of a verifier only in terms of the length
of $w$, so a polynomial time verifier runs in polynomial time in the
length of $w$. A language $A$ is polynomially verifiable if it has a
polynomial time verifier. (Sipser, 293)
Definition 7.19: NP is the class of languages that have polynomial time verifiers. (Sipser, 294)

Translating the wiki definition into the above, $A = L$, $V = M$, $w = x$, and $c = y$. It seems that the first condition of the wiki definition is correct, and this may make more sense given the alternative definition of NP. A language $L$ is in NP if there exists a non-deterministic TM $N$ that decides $L$ in non-deterministic polynomial time $NTIME(n^k)$. Here, the running time of $N$ is measured in terms of its input size $n = |w| = |x|$.
However, I have not seen nor am I familiar with the second condition, but that seems to set some upper bound on the length of $y$ so that $|y|$ is a polynomial in $|x|$, which should answer your question about if $|y| > p(|x|)$. I figure the second condition is to protect against padding arguments. At any rate, if $p(|x|) < q(|x|)$, then $p(|x|) < |y| < q(|x|)$, so $|y|$ is still a polynomial in $|x|$.


Show that C(n) = {a^k | k is a multiple of n} is a regular language I came across this question in an exam book and was unable to find a solution:

Prove that C(n) = {a^k | k is a multiple of n} is a regular language for every natural number n ≥ 1.

I wasn't able to construct a DFA as the number n is left variable in the original question. Is it possible to construct a DFA with a variable number of states?

Any help would be greatly appreciated.
Thank you!

It’s easy to construct a DFA which recognize $a^n$.

Then add an $\epsilon$ transition from all its final state to its initial state.


Decision version of the traveling salesman problem and NP-hardness Wikipedia says:

  The problem has been shown to be NP-hard

and

  the decision problem version ("given the costs and a number x, decide
  whether there is a round-trip route cheaper than x") is NP-complete.

How can the "non-decision problem" version be NP-hard? Doesn't this class contain decision problems, by definition? Is this some sort of abuse of notation? Are they just being overly flexible with the definition of NP-hard?

When we say that an optimization problem is NP-hard, what we mean is that its decision version is NP-hard. In this particular case, according to Wikipedia more is true: the function version (finding an optimal solution) is complete for $\mathsf{FP}^\mathsf{NP}$.


Prove that at least as many edges as vertices implies a cycle I am EXTREMELY confused on where to start with this problem. We recently just started learning about graph theory and I don't know where to begin.

  Prove that in a connected graph G with $p$ vertices, $q$ edges, and at least one cycle, $q \ge p$

How do I begin with this question? Any help would be greatly appreciated. Thank you so much.

Graph has a cycle on $k$ vertices implies that those vertices are connected with $k$ edges. Also, the graph is connected so $p-k$ vertices which left should be connected to the cycle, that means extra $p-k$ edges (distinct end points). Totally the graph has more($\geq$) than $p$ edges.


Create a shallow logic circuit that increments a binary number This circuit should be reasonably efficient in size and depth, but with priority on depth.

If depth was not a concern, then I guess I could make a specialized adder for the least significant bit and then modelled the rest of the circuit as a ripple adder with only that initial, possible carry. The carry has to ripple through the first sequence of consecutive bits set to 1. For example:

$inc(0111) = 1000$
$inc(0001) = 0010$
$inc(0100) = 0101$ (no ripple)

But this takes linear time, in the worst case (binary string is $1...1$). How do you optimize for depth? Does the optimal circuit have a $log_2(n)$ depth?

Is perhaps the best strategy to use a parallel prefix circuit? If so, I guess one would make a specialized adder for the least significant bit. Then you have the result of the least significant bit, which is 0 if a carry was generated, 1 otherwise. If a carry was generated, then you need to efficiently ripple it through all the adjacent, consecutive 1-bits. If one is to use a prefix sum, then you need an associative binary operator. It also needs to preserve the value of the bits that are not part of the initial, consecutive 1-bits (from right to left). This might mean that you pass in the carry bit that was (possibly) generated after the increment on the least significant bit, while the rest of the operators gets fed predefined bits which preserve the values of the relevant bits of the number (bit vector).

At this point, I'm stuck.

You are on the right track with a parallel-prefix circuit.  You already have the key when you said

  The carry has to ripple through the first sequence of consecutive bits set to 1.

Now suppose you are figuring out the output for, say, the 5th bit.  What function of the first 4 bits tells you whether the 5th bit should ripple?  That's the function you need to make a parallel-prefix circuit for.


min vertex cover to access k edges in a tree I need to find the minimum number out of $N$ vertices on a tree with $N-1$ edges, so that at least $K$ edges of that tree are connected to these vertices.

For example, if $N=9$ and $K=6$ and we have this tree:

   Edges  |  Vertice #1  | Vertice #2
     1            1          2
     2            1          3
     3            1          4
     4            2          5
     5            2          6
     6            3          7
     7            4          8
     8            4          9

The right answer should be $\mathrm{min}=2$.

Any thoughts?

There is a $\mathcal{O}(nk)$ DP approach.

Call an edge covered if we select a vertex next to it. Root the tree at an arbitrary vertex $r$. Define $DP[i][b][t]$ as the maximum number of edges in the subtree of node $i$ that can be covered by selecting at most $t$ nodes from the subtree. If $b = 0$ we are not allowed to select node $i$, and if $b = 1$ we must select it.

If we calculate this DP, we can solve the problem, as the minimum number of nodes to cover $k$ edges is the smallest $t$ for which $max(DP[r][0][t], DP[r][1][t]) \geq k$. Further note that it suffices to only calculate the $DP$ for $t \leq k$, as any $k < n$ nodes cover at least $k$ edges.

To give the recurrence to calculate the DP, we first give the knapsack-function: let $K(V_{1}, \dots, V_{m})$ be an array such that

\begin{equation*}
K(V_{1}, \dots, V_{m})[t] = \max_{t_{1} + \dots + t_{m} = t} \sum_{j = 1}^{m} V_{j}[t_{j}]
\end{equation*}

Note that $K(K(V_{1}, \dots, V_{m-1}), V_{m}) = K(V_{1}, \dots, V_{m})$, and that $K(A, B)$ can be directly calculated by the above formula in $\mathcal{O}(|A| \cdot |B|)$ time. Hence calculating $K(V_{1}, \dots, V_{m})$ takes $\mathcal{O}(\sum_{i = 2}^{m} |V_{i}| \sum_{j = 1}^{i-1} |V_{j}|)$ time regardless of the order we combine the sets in. If we are interested in only the first $k$ values of the DP, the complexity drops to $\mathcal{O}(\sum_{i = 2}^{m} |V_{i}| \min(k, \sum_{j = 1}^{i-1} |V_{j}|))$

Let $C_{i}$ be the set of children of node $i$, and $C_{ij}$ be the $j$th child of $i$. Then
\begin{gather*}
DP[i][0][t] = K(V_{1}, \dots, V_{|C_{i}|})[t]\\
DP[i][1][t] = |C_{i}| + K(V'_{1}, \dots, V'_{|C_{i}|})[t-1]
\end{gather*}
Where
\begin{gather*}
V_{j}[t] = \max(DP[C_{ij}][0][t], DP[C_{ij}][1][t] + 1)\\
V'_{j}[t] = \max(DP[C_{ij}][0][t], DP[C_{ij}][1][t])\\
\end{gather*}
Calculating the answer with this recursion takes $\mathcal{O}(nk)$ time. Informally this is because over the course of the algorithm, we combine single-element DPs into a DP representing the whole tree. We do at most $\frac{n}{k}$ combinations of sets of size $k$, and any element costs us at most $2k$ time (if element $x \in A$ costs us $|B|$ time when calculating $K(A, B)$) before it gets merged into a set of size $k$, so the total amount of work is at most $\mathcal{O}(k^{2} \frac{n}{k} + k n) = \mathcal{O}(nk)$. This is easy but tedious to formalise with induction.

#include <iostream>
#include <vector>
#include <tuple>
using namespace std;
const int INF = (int)1e9 + 7;

vector<int> knapsack(const vector<int> a, const vector<int> b, int k) {
    int n = a.size();
    int m = b.size();
    vector<int> c(n+m-1, -INF);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) c[i+j] = max(c[i+j], a[i] + b[j]);
    }
    if (c.size() > k) c.resize(k);
    return c;
}

pair<vector<int>, vector<int>> dfs(int i, int p, int k, const vector<vector<int>>& g) {
    vector<int> dp0 = {0, 0};
    vector<int> dp1 = {-INF, (int)g[i].size() - (p != -1)};
    for (auto t : g[i]) {
        if (t == p) continue;
        vector<int> dp0_t, dp1_t;
        tie(dp0_t, dp1_t) = dfs(t, i, k, g);
        int m = dp0_t.size();

        vector<int> off0(m), off1(m);
        for (int j = 0; j < m; ++j) off0[j] = max(dp0_t[j], dp1_t[j] + 1);
        for (int j = 0; j < m; ++j) off1[j] = max(dp0_t[j], dp1_t[j]);
        dp0 = knapsack(dp0, off0, k+1);
        dp1 = knapsack(dp1, off1, k+1);
    }
    return {dp0, dp1};
}

int minCover(int k, const vector<vector<int>>& g) {
    vector<int> dp0, dp1;
    tie(dp0, dp1) = dfs(0, -1, k, g);
    for (int i = 0;; ++i) {
        if (max(dp0[i], dp1[i]) >= k) return i;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, k;
    cin >> n >> k;

    vector<vector<int>> g(n);
    for (int i = 0; i < n-1; ++i) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    int t = minCover(k, g);
    cout << t << '\n';
}


Difference between regular expression and grammar in automata I am new to automata, and I have been given a brief introduction to regular expressions only yesterday. I have read the various rules which to define a regular expression. But I am unable to differentiate between regular expressions and grammar of a language( I have not been taught the grammar for regular expressions).

I understand that grammar helps us to generate the valid strings in a language, but then this is what the rules for defining a regular expressions state. So where does the difference lie? I asked my professor and he said that regex are the most basic strings in a language and grammar is the set of rules for any language, which are of higher order than regex. Can someone provide some more in-depth information?

Regular expressions, regular grammars and finite automata are simply three different formalisms for the same thing. There are algorithms to convert from any of them to any other.

The basic reason that we have all three is that they were created independently, with the first set of equivalences (there are several other formalisms as well) proven by Kleene (this result, or part thereof is called Kleene's Theorem).

So in that context, depending on which way round you want to run the models, they all recognise or generate strings of a regular language, and mathematically, there is, in that sense, no difference.

Of course sometimes one model is easier to use than another for a particular task, due to the details of the formalism. Furthermore the way they work in a human's head is often a little different, finite automata "feel" like computers, regular expressions "feel" like you're constructing a string out of smaller substrings and regular grammars "feel" like a more traditional grammatical derivation or classification of a sentence in a language (unsurprisingly when you look at the history).

So to compare the two, let's define them:

Regular Expressions

So regular expressions are recursively defined as follows:

$\emptyset$ is a regular expression
$\varepsilon$ is a regular expression
$a$ is a regular expression for every $a \in \Sigma$
if $A$ and $B$ are regular expressions then

$A\cdot B$ is a regular expression (concatentation)
$A \mid B$ is a regular expression (alternation)
$A^{\ast}$ is a regular expression (Kleene star)

Along with some semantics (i.e. how we interpret the operators to get a string), we get a way of generating strings from a regular language.

Regular Grammars

Regular grammars consist of a four tuple $(N,\Sigma, P, S \in N)$ where $N$ is the set of non-terminals, $\Sigma$ is the set of terminals, $S$ is the start non-terminal and $P$ is the set of productions which tell us how to change the start symbol, step by step, into a string in $\Sigma^{\ast}$. $P$ can have its productions drawn from one of two types (not both though):

Right Linear Grammars

For non-terminals $B$, $C$, terminal $a$ and the empty string $\varepsilon$, all rules are of the form:

$B \rightarrow a$
$B \rightarrow aC$
$B \rightarrow \varepsilon$

Left Linear Grammars

Left linear grammars are the same, but rule #2 is $B \rightarrow Ca$.

Things to Ponder

So looking at these definitions and playing with them, we can see that regular expressions look like matching rules, or ways of dealing with strings a bit at a time.

Grammars seem to "label" sections of the string, and group labels under new labels to validate the string (i.e. if we can get from $S$ to the string, or vice versa, we're happy).

However these are really doing the same fundamental thing, and how you view the metaphor of their function is really up to you.


Implementing Queue operations in $\Theta(1)$ We want to implement a Queue which has two special operations besides the regular Queue operations: $getMiddle$(returns the element from the middle of the Queue, for example, if the Queue has 7 elements, it returns the 4th element, if the Queue has 6 elements, it returns the 3rd or the 4th) and $popMiddle$(removes the middle element). We want both of these operations and all the other Queue operations to run in $\theta(1)$. Pick a suitable data structure for representing the Queue, implement the $popMiddle$, pop and push operations and explain in short how the other operations would be implemented.

I was thinking that the linked list would be a good pick if we keep in mind also the tail. But there is a problem when popping the middle because we have to iterate until there. An array would not be good because when erasnig we have to move all the elements to the left, if not there is no suitable formula to find the middle. Does somebody have better ideas?

The problem can be solved by keeping two deques $Q_1$ and $Q_2$ (implemented, e.g., using doubly linked lists) with the invariant that $Q_1$ always contains the first $\lceil n/2 \rceil$ elements of the queue.

The operations are implemented as follows:

push($x$): push $x$ at the beginning of $Q_1$. If the invariant is violated, then pop the last element $y$ from the end of $Q_1$ and push $y$ at the front of $Q_2$.
get(): return the element at the beginning of $Q_1$.
pop(): pop the the element at the beginning of $Q_1$. If the invariant is violated then pop the first element $y$ from the beginning of $Q_2$ and push $y$ at the back of $Q_1$.
getMiddle(): return the element at the end of $Q_1$.
popMiddle(): pop the element at the end of $Q_1$. If the invariant is violated then pop the first element $y$ from the beginning of $Q_2$ and push $y$ at the back of $Q_1$.


How to describe an algorithm whose input size diminishes by 1 for each iteration To elaborate on the title: I have a recursive algorithm whose input is reduced by 1 for every iteration until the input size is 1.

1st iteration: n

2nd iteration: n-1

3rd iteration: n-2

4th iteration: n-3

.

.

.

nth iteration: n-(n-1)

How can I describe this in asymptotic notation?

On recursive algorithms, you need first to obtain the recurrence relation. Then you solve the recurrence to get the total time required by the algorithm.

Let $n$ be the input size. Let $f(n)$ be the time required in each recursive call. Let $b$ be the input size for the base case. A general recurrence relation might look like this

$$
T(n) = T(n-1) + f(n)  \quad \quad \textrm{if } n > b \\
T(n) = c \quad \quad  \quad \quad \quad \quad \quad \quad \;\ \textrm{if } n = b
$$
where $c$ typically is a constant (because typically the base case takes constant time).

So, you need to figure it out the function $f(n)$, which is specific for each algorithm. For example, if $f(n)=n$ (e.g. a simple pass on a array), and assuming $b=1$ and $c=1$ (it is not a problem to assume $c=1$ if you are working with assymptotic notation) then

$$
T(n) = T(n-1) + n  \quad \quad \textrm{if } n > 1 \\
T(n) = 1 \quad \quad  \quad \quad \quad \quad \quad  \textrm{if } n = 1
$$

Solving this recurrence, you have that $$T(n) = n + (n-1) + \ldots + 2 + 1 = \frac{n(n+1)}{2} = O(n^2)$$.


Computing the rank of a multiset after inserting another element What is the procedure for computing the rank of a multiset after inserting an element?

For instance, lets say we have a set $S = (0,1)$ containing $n = 2$ distinct elements.

The multiset $M = (1,1)$ has rank $5$ because there are $4$ multisets less than it based on lexicographic ordering: $(0), (1), (0,0), (0,1)$.

If we insert $0$, we get $(0,1,1)$ which has rank $8$. If $1$ were inserted instead we'd have $(1,1,1)$ with rank $9$.

Is there a function $f(r,x,n)$ which takes a rank $r$, an element $x$, and $n$, and returns the new rank after inserting $x$?

I'll consider the easy $|S|=2$ case. There are $n+1$ multisets of size $n$, and so the rank of the multiset $0^{n-k} 1^k$ is
$$ r(n,k) = \sum_{m=0}^{n-1} (m+1) + k = \frac{n(n+1)}{2} + k. $$
What happens when adding an element? Adding $0$ and $1$, respectively, correspond to $r(n+1,k)$ and $r(n+1,k+1)$. We have
$$
\begin{align*}
r(n+1,k) &= \frac{(n+1)(n+2)}{2} + k = n + 1 + \frac{n(n+1)}{2} + k = n+1 + r(n,k), \\
r(n+1,k+1) &= r(n+1,k)+1 = n+1 + r(n,k) + 1.
\end{align*}
$$
Therefore the function you want is
$$ f(r,x,n) = r + n+1 + x. $$
Here $n$ is the size of the old multiset, rather than the number of elements. For example, the rank of $(1,1)$ is $5$, and $f(5,0,2) = 5 + 3 + 0 = 8$, $f(5,1,2) = 5 + 3 + 1 = 9$.


An algorithm to efficiently insert a list of elements into a binary heap ("bulk insertion") I wonder if there is any elegant algorithm for inserting a list of elements into a binary heap (at once) whose performance would be close to that of inserting elements one by one when there are only a few elements to insert, and which would still run in linear time in the worst case (when there is a lot of elements to insert).

Wikipedia describes a procedure, due to Floyd, which constructs a heap from an array in linear time.

It also mentions a procedure for merging two heaps, of sizes $n$ and $k$, in time $O(k + \log k \log n)$.

Altogether, we can add $k$ elements to a heap of length $n$ in time $O(k + \log k \log n)$: first build a heap containing $k$ elements to be inserted (takes $O(k)$ time), then merge that with the heap of size $n$ (takes $O(k+ \log k \log n)$ time).

Compare this to repeated insertion, which would run in time $O(k\log n)$.


Why I can't parse factorial? Given that I have a simplified Bison BNF grammar:

%token T_EXP '^'
%token T_NOT '!'

%right T_NOT
%right T_EXP
%right T_FAC
%nonassoc T_LPAREN T_RPAREN T_NUMBER

%type expr

%%

expr:
  T_NOT expr # logical not, e.g. !a
| expr T_EXP expr # exponent, e.g. 2 ^ 3
| expr T_NOT %prec T_FAC # factorial, e.g 3!
| T_LPAREN expr T_RPAREN { $$ = $2; }
| T_NUMBER
;

%%

Given a classical example, 2 ^ 3!, it is natural to human that 3! should be produced first, then the exponent and the answer is 2 ^ 3! -> 2 ^ (3!) -> 2 ^ 6 -> 64. It makes sense to assert that factorial goes before the exponent operator, so its binding power must be higher than that of the exponent.

However, in reality, the parser didn't produce a correct result. I modified the grammar production so that it shows as an AST:

calc eval > 2 ^ 3!
unary !!
  binary ^
    number 2
    number 3
        [expr: 40320]

This expression was evaluated as (2 ^ 3)! -> 8! -> 40320. And no matter how I move the precedences, it always produces the wrong result. If I wrap the factorial with parentheses, i.e. 2 ^ (3!), the result is correct. What's happening in here? Shouldn't 3! be evaluated first?

At first glance, I thought this could be an ambiguity error.

2 ^ 3!    # Input
. 2 ^ 3!  # Lookahead is T_NUMBER(2), shift
2 . ^ 3!  # Lookahead is T_EXP(^), shift
2 ^ . 3!  # Lookahead is T_NUMBER(3), reduce as `expr -> expr T_EXP expr`?
          # But wait! There's a T_NOT behind it

Diverge 1:

2 ^ . 3!  # Lookahead is T_NUMBER(3), reduce as `expr -> expr T_EXP expr`
expr . !  # Lookahead is T_NOT(!), reduce as `expr -> expr T_NOT`?
expr ! .  # EOF reached, final stack: expr -> expr T_NOT -> (expr T_EXP expr) T_NOT // Incorrect

Diverge 2:

2 ^ . 3!   # Potential lookahead found T_NOT(!), shift
2 ^ 3 . !  # Lookahead is T_NOT(!), reduce as `expr -> expr T_NOT`
2 ^ expr . # EOF reached, final stack: expr -> expr T_EXP expr -> expr T_EXP (expr T_NOT) // Correct

But I considered this as a pure insanity and absurdity that comes out of nowhere in my mind, still ! should be shifted before the number gets reduced because the binding power of T_FAC is higher than that of T_EXP and T_NUMBER, so diverge 2 should have had happened, am I right?

I have no comment on the precedence of the factorial operator; my inclination is to consider it to have higher precedence than other operators because of the almost universal rule that postfix operators bind more tightly than other operators.

When implementing that, you need to create a pseudotoken to modify the default precedence of the prefix operator:

%precedence PREFIX_OP
%right      '^'
%precedence '!'
%%
expr : '!' expr %prec PREFIX_OP
     | expr '^' expr
     | expr '!'
     | '(' expr ')'
     | T_NUMBER

(Using actual character constants in your grammar really makes it more readable, and it also simplifies writing the lexer. So I did that.)

To understand this, remember that precedence relations always compare the precedence of a reduction with the precedence of a shift. These are two distinct things; they only seem to be the same because (f)lex sets the precedence of a reduction (i.e. the right-hand side of a rule) to be equal to the precedence of the last non-terminal in the rule (unless it is specified explicitly with %prec). That's often the "right thing" but it leads to a lot of confusion because it makes it appear that the precedence comparison is between two objects of the same type.

In the resolution of !3!, the parser must decide what to do after seeing !3. The only thing it can do with the 3 (a T_NUMBER) is reduce it to an expr; there is no ambiguity and thus no need to consult precedence relations. (Consequently, %nonassoc T_NUMBER has absolutely no effect, which is which I removed it from the grammar.) It then has two options:

reduce '!' expr to expr
shift the second !

To decide, it precedence-compares the reduction expr: '!' expr with the terminal !. Since the precedence of the reduction was explicitly set with %prec PREFIX_OP this results in a comparison between reduction PREFIX_OP and shift !; the shift wins. The same would happen with 2^3! because the comparison will involve the reduction expr: expr '^' expr whose last terminal is '^' with the shift !.

In your original grammar, the precedence declaration

expr: expr '!' %prec T_FAC

had no effect whatsoever, because that reduction is never ambiguous (3 ! 2 is a syntax error; no grammar rule applies to it.) Furthermore, the ambiguity between the reduction expr '^' expr and the shift !  was incorrectly resolved because the terminal was declared as having lower precedence than the reduction. Just changing the order of the precedence list wouldn't have the desired result because that would also change the precedence of the reduction expr: '!' expr.


Run-Time environments I was reading about Run-Time Environments.
In the Dragon book (2nd ed.) I came across the following presentation:

  [To implement abstractions, the] compiler creates and manages a run-time environment in which it assumes its target programs are being executed. This environment deals with a variety of issues such as the layout and allocation of storage locations for the objects named in the source program, the mechanisms used by the target program to access variables…

so I'm getting confused about points highlighted above:

How does compiler execute the code, it is only supposed to generate the intermediate code right?
And does it create runtime environment? I mean there's not a virtual machine that the program runs on, it just runs on your computer right? When does it create a runtime environment?
Isn't memory managed by the operating system? Why is allocation of storage done by the compiler and at what point? Probably what variables are needed and how much may be known by the compiler but, how does it communicate this information to the OS?

(Your question seems to be about concepts and terminology. The meaning of termini depends on context - the quote is from a compiler writers' book. Not only are the authors entitled to a "compiler centric" view of things: that perspective is to be expected.)

There are at least two "CS" interpretations to runtime environment.
 One is the process/OS level - some lump of hardware turned into a MINIX machine, an OS/400, QNX, z/OS, Multics one, defined in an applicable application binary interface (ABI).
At this level, memory usually gets allocated in segments or pages (taking care no information leaks). (In a conventional OS,) Requirements like amount and initialisation are taken from an "executable file" in an appropriate format.
It is a matter of definition whether "the compiler" is responsible for the generation of such a file from source code or just some intermediate code which may be executed by an interpreter, or statically analysed&improved, turned into assembly language, assembled into an object file/module, linked with other modules.

To me, the existence of a virtual machine is a philosophical question (as opposed to the existence of the computing hardware heating up my environment) - I take the pragmatic stance of accepting help, from a mere concept when that is what it is. Proponents of something like the Java virtual machine (JVM) (a popular target for compilers, btw.) are entitled to making the case for VM existence.

Regarding exactly when the compiler does something, anything going on during execution of the compiler should be beyond doubt. A compiler-centric view may include anything from decisions made during the specification of the compiler (like row-major or column-major layout of two-dimensional arrays) up to and during the execution of the compiled program - anything not due explicitly to a specific part of the source code, but the language specification implemented by the compiler.

 This is the programming language level - what gets your main() running (and possibly constructors&co. of statically allocated objects before that), that Begin…End;-block implicitly prefixed with Simula - you name it. It takes care of memory(/address) allocation (and possibly initialisation) for a subroutine call stack (per coroutine/thread), "statically allocated" program data (those objects named in the source program - on behalf of the program source code/the coder/the one who started the program), "automatically allocated" space (e.g., for "local" variables in potentially recursive subroutine calls), "dynamically allocated" space (e.g. objects for linked data structures. "dynamically": as need arises during program execution, a "program request" for (memory for) another object may lead to the language runtime environment requesting more memory from the OS - often, the RTE manages a memory pool for smallish requests and makes largish ones to the OS).
"The compiler" decides about memory layout for multi-dimensional arrays.
It arranges access to machine code for the "runtime library" - with OS support more often than not.
In all, a Forth machine, a Java, Fortran, Beta one.

Note that

the paragraph quoted does not say the compiler [executes] the code
creates and manages needs interpretation/leaves room for it
one resource managed by one authority doesn't preclude the same resource being managed by another one - expect conflicting responsibilities handled usefully.


How can I compute logarithm when comparison is undecidable? In Haskell, I have the following datatypes that encodes arbitrary real numbers and arbitrary complex numbers, respectively:
newtype ArbReal = ArbReal {approximate :: Word -> Integer}
data ArbComplex = ArbReal :+ ArbReal

For the ArbReal type, the ArbReal constructor labels a function that, when fed an integer $n$, computes the encoded real number to $n$ decimal digits below the decimal point, rounded. For example, when ArbReal f = pi, f 0 = 3, f 1 = 31, f 2 = 314, and so on.
Note that there is no guarantee to the direction of rounding. Given ArbReal g = 0.5, g 0 can be either 0 or 1. This is inevitable, for if there were, an interval would be decidable.
ArbComplex encodes a complex number by specifying its real part and imaginary part.
I've successfully implemented addition, subtraction, multiplication, and division on both types. Division by 0 falls in an infinite loop, though.
I also implemented nth root function of real numbers, square root function of complex numbers (where branch cut doesn't exist, hence multivalued), and $\pi$.
Now it's time to implement natural logarithm (on complex numbers, without a branch cut). And that's where a problem emerged. I was implementing the algorithm (namely, AGM iteration) in this paper, but:

Finally, if $0< x <1$, we may use $\log(x) =−\log(1/x)$, where $\log(1/x)$ is computed as above.

This paragraph forces a comparison, which is undecidable. So it's impossible to implement the algorithm directly. Indeed, in my current version of implementation, $\log 1$ falls in an infinite loop.
Is there a tweak on the algorithm that makes the algorithm computable? Or must I implement a completely different algorithm?

Even though absolute comparisons may not converge, you should be able to narrow the argument into at least one of several partially overlapping ranges, such that you have a technique that works in that range.
For example, you should be able to tell that $x$ definitely falls into at least one of the ranges $A = \left(0,\frac{3}{4}\right]$, $B = \left[\frac{1}{2},\frac{3}{2}\right]$, or $C = \left[\frac{5}{4},\infty\right)$ with little difficulty. Use AGM if it's in $C$, the transformation if it's in $A$, and if it's in $B$, use this transformation:
$$\log (x) = \log (2x) - \log 2$$


How to check ambiguity of a specific grammar Giving the following Grammar:

S → ^ | SaSMSM |  SMSaSM | SMSMSa
M → b | c

^ means eopsilon.

How can i check whether its ambgious or not?
My intuition is that its not: every time you derive,the a is placed in different places between the M's.

Can you give me a clue to get a better prove? Or give an example for its ambiguity?

In other words,Can i have to different derevation trees for a same string in this grammar?

Thank you.

The grammar is ambiguous. The word $abbabb$ can be derived in at least 3 ways:

$$S \Rightarrow SaSMSM \Rightarrow^2 SaMM \Rightarrow SaSMSMaMM \Rightarrow^7 abbabb,$$
$$S \Rightarrow SaSMSM \Rightarrow^2 aSMM \Rightarrow aSMSMSaMM \Rightarrow^7 abbabb,$$
$$S \Rightarrow SaSMSM \Rightarrow^2 aMSM \Rightarrow aMSMSaSMM \Rightarrow^7 abbabb.$$

I found this by thinking about how words in the language might be parsed. My first observation was that if a word ends with $a$, the derivation must have started with the last rule for $S$. If it ends with $b$ or $c$ one of the other non-$\epsilon$-rules must have been used in the first step.

In order to distinguish these two rules, I looked at the preceding symbol, which is $S$ for both rules. The symbol before that differs again. So if we could uniquely identify the word resulting from the $S$ we could determine the initial rule unambiguously. If we furthermore could uniquely identify which subword results from which symbol of the rule in each case, we would get a procedure that yields a unique parse tree for each word, proving unambiguity.

Alas, I noted that it is not possible to uniquely determine the yield of the rightmost $S$. But now I had a better idea, how an ambiguous word should look like.


Max flow and Matching problem Where can i find a list of problems reducible to max flow and matching problems. I need such examples to learn and practice .

Based on the book "Algorithm Design" by Kleinberg and Tardos, Kevin Wayne has a set of slides (second part here) where the following applications of max flow and matching are presented in some detail:

survey design
airline scheduling
image segmentation
project selection
baseball elimination
assignment problem
input-queued switching

For even more examples, have a look into the exercises of Chapter 7 of Kleinberg and Tardos' book, or into the exercises of the book "Network Flows: Theory, Algorithms, and Applications" by Ahuja, Magnanti and Orlin.


Turing Machine - Analyze brackets For a practical task, we are asked to provide the transition table for a Turing machine that validates the number of open brackets is equal to the number of closing brackets.
The only tape symbols allowed are ( ) E B
If the number of brackets is equal (opening brackets = closing brackets) then the machine must halt in-state 'yes' and if they are not equal than it must halt in-state 'no'

Any clarification on this would be greatly appreciated! :)

It sounds like the only thing you care about is whether the number of open brackets equals the number of close brackets. In which case, I'd recommend an algorithm something like this:

Look for an open bracket.

If you can't find one, look for a close bracket.

If you find one, reject. Otherwise, accept.

If you can find one, erase it.

Look for a close bracket.

If you can't find one, reject.
If you can find one, erase it.

The exact mechanics of searching for brackets are up to you, but if you need more guidance, I'd recommend using one of your spare symbols ($E$ for empty) to mark empty patches of tape (everything to either side of the input) and the other ($B$ for bracket deleted) to mark things you've erased. That way you can tell when you reach the edge of the input string.


Why does Min-Max algorithm delays a good move indefinitely? Consider a simple chess example:

Q is white Queen.

K, R is black King and black Rook respectively.

  A B
1 . Q
2 . .
3 K .
4 . .
5 . .
6 R .
7 . .
8 . R

1,2...8 is the rank and A and B are the files of the chessboard.

Assume the king can only move horizontally for this example.

Here, if we search to depth 0, the best move should be Qxb8 (queen takes rook on B8)

But if we search for depth 2, then one line goes:

1. Qa1+ Kb3 2. Qxa6 (evaluation of the position +100 as rook is taken)

Second line:

1. Qxb8 Ra4 2. Qb1 (evaluation of the position +100 as rook is taken)

And since both have the same evaluation we select the first variation and play Qa1+ and let's say opposing player plays Kb3.

And now, if we again search to depth 2, same situation arise:

One line:

1. Qb1+ Ka3 2. Qxb8 (evaluation of the position +100 as rook is taken)

Second line:

1. Qxa6 Rb4 2. Qa1 (evaluation of the position +100 as rook is taken)

And again since both lines have the same evaluation we select the first variation and play Qb1+ and let's say opposing player plays Ka3.

And this will keep repeating and the queen will never capture the rook and just keep checking the king in the hope of capturing the rook in the next move but again repeats the same idea.

I hope this example makes it much clear what I am trying to say.

In a game-theoretical sense, both of the moves you describe are equally good in the scenarios you describe, so the algorithm is "correct" in that it doesn't matter which move it picks -- you do not explicitly encode a preference for faster wins (or faster gains of $+100$) over slower scores.

Introducing a discount factor to explicitly encode such a preference, as described in ryan's answer, can be a solution... but it's not very common in game AI / minimax / alphabeta search literature, and it can also be detrimental in slightly different scenarios. For example, if we can get a score of $+100$ in one ply, or a score of $+101$ in the second ply, we would generally prefer the path leading to that delayed $+101$... but a common choice of a discount factor $\gamma = 0.9$ would lead us to prefer the suboptimal path. Note that this does not just hold for the example of $\gamma = 0.9$; we can come up with such a counterexample for any value $0 \leq \gamma < 1$ that will cause the solution with discount factor to break down and lead to suboptimal behaviour.

A more robust solution is a combination of iterative deepening with move ordering. In practice, we rarely use a plain minimax search with a predetermined depth limit. In practice, we usually do something like:

Start out with a $1$-ply search
Proceed to run a $2$-ply search afterwards if we still have time
Proceed to run a $3$-ply search if we still have time
etc.

This is referred to as iterative deepening. Now, when we start a new search (with an increased depth limit), a common trick is to first re-order the moves at the root node based on the scores found in the previous search (with the lower depth limit).

Now, imagine that we apply this process to the scenario described in your question. The Qxb8 line of play will first be discovered to give a $+100$ score in one of the first iterations (shallow searches). Based on this, we will sort that Qxb8 line to be searched before the Qa1+ line when moving on to the next iteration with a deeper search. Both lines will then be discovered to have the same $+100$ score, but now, due to clever move ordering (not specific to this case, but clever move ordering in general thanks to iterative deepening!), the shorter line will have been searched first and be the preferred line of play.

Note that the "trick" with iterative deepening + move ordering is not just useful to solve the issue highlighted in this question, but in general can also significantly increase the number of prunings that can be achieved when we extend the basic minimax algorithms with techniques like alpha-beta pruning.


Show that the following algorithm doesn't always find the optimal matching Consider the following algorithm for the maximum matching problem:

Sort all nodes by their $\deg(v)$
Take the node with minimal $\deg(v)$
Take a random edge $(u,v)$ $\in$ $E$
Add $(u,v)$ to $M$
Delete all edges of $u$ and $v$ in $E$

I have to show that the algorithm isn't correct for undirected graphs with maximum degree 3. (It does find the maximum matching if the maximum degree is 2.)

To prove that the algorithm does not find a maximal matching for a graph $G$, I have to give a counterexample.

My problem is that I am drawing and drawing graphs, but the algorithm is always able to find the optimal matching. Could somebody help me to find a graph where the algorithm cannot find the optimal matching?

Consider a graph consisting of two triangles connected by an edge (a total of seven edges). Using this graph, Besser and Poloczek show that no greedy-like algorithm for maximum matching can be optimal even on graphs with maximum degree 3.


Find amount of elements greater then number k in a BST I am trying to find an Algorithm to find the amount of elements in a BST which are greater than a certain number K.
I found it problematic as there are elements which might be greater then K but wont be found by traveling constantly to the right child, as there might be elements that are greater then K in the left sub-tree.
The Algorithm must be executed in a run-time complexity of O(h), while h is the height of the tree.

You can do it in $O(h)$ time only if you know some additional information at every node about the subtree rooted at that node. (Maybe @greybeard is suggesting the same in the comments). For example:
Suppose $x$ is any node in the tree, and suppose you know the number of nodes in the sub-tree rooted at $x$. Let us call this variable "x.total". Then, the following algorithm works in $O(h)$ time:
fun(root,K) // It returns the number of elements greter than K
---if (root = NULL)
------- return 0;
---if(root.value > K)
-------- return fun(root.left_child,K) + 1 + root.right_child.total
---else
-------- return fun(root.right_child,K)

The correctness of the above algorithm follows due to the fact that the given tree is a Binary Search tree (BST).
Moreover, you can maintain the extra information (i.e, x.total) for all nodes by traversing the tree only once. You can use DFS procedure for the same. Thus, the preprocessing time is only $O(n)$. And, the query time complexity would be just $O(h)$.

If you do not store any kind of extra information, then you can not do better than $O(n)$. For example: suppose the tree contains only positive elements and the query is for $K =  0$. Then, this query is the same as finding the total number of elements in the tree, which requires you to traverse every node and it essentially requires $\Omega(n)$ time.


Proving that if A⊕B ∈ NP then NP = coNP I got this question:

  Let $A \oplus B = (A\cap \bar{B})\cup(\bar{A}\cap B)$.

  Proof that $NP = coNP$ if and only if $A,B\in NP$ and $A \oplus B\in NP$.

But I don't know how to proof the direction that if $A,B\in NP$ and $A \oplus B\in NP$ then $NP = coNP$.

I have tried to build the non-deterministic machines for $\bar{A}$ and $\bar B$, but I don't know how.

What that I tried: Say I want to build the non-deterministic machine for $\bar{A}$. I know that if $w\in A \oplus B$ and $w\in B$, then for sure $w \in \bar A$. My problem is with the condition if $w\notin A \oplus B$ and $w\notin B$ then $w \in \bar A$, because I don't know if $w\notin A \oplus B$ and $w\notin B$ since I don't know that $NP = coNP$.

So how can I show non deterministic machines for $\bar{A}$ and $\bar B$ when I don't know how to decide if "word is not in ..."?

Thanks to G. Bach and Yuval Filmus.

If every $A, B \in NP$ and $A \oplus B \in NP$, then let $E$ to be some language $E\in NP$. Since $\Sigma^*\in NP$ then $E \oplus \Sigma^* \in NP$. But $ E \oplus \Sigma^* = \bar E$, so $\bar E \in NP$, and we got that $NP \subseteq coNP$.

Let $D$ to be some language $D\in coNP$ ($\bar D \in NP$). Since $\Sigma^*\in NP$ then $\bar D \oplus \Sigma^* \in NP$. But $ \bar D \oplus \Sigma^* = D$, so $\bar D \in NP$, and we got that $coNP \subseteq NP$.

And then $NP = coNP$.