How to map the tapes of a "k-tape" Turing Machine into the single tape of a "1-tape" Turing Machine I'm reading Sipser and I'm finding it hard to understand what the process is such that if you give me k Turing machines with k tapes, I can spit out an equivalent Turing machine with only one tape. An example would be nice. Actually, a worked out example that shows how to go from TM that has $k$ tapes to one that has 1 tape is what I'm really looking for. I have been unable to find one so far. I'm also not looking for any proofs.

An answer shamelessly copied from myself:

A multi-tape Turing Machine is mostly the same as a single-tape machine, except we have an extended transition function $Q\times\Gamma^{k}\rightarrow Q\times\Gamma^{k}\times\{L,R\}^{k}$ where $k$ is the number of tapes. So in each state, the transition function reads the contents of each tape, moves to a new state, (maybe) writes something on each tape and moves each head - just as a regular TM, except now we have more things to read, write and move.

As your question suggests, such a machine can be simulated by a single-tape TM. Even better, it can be done with only quadratic slowdown (so for polynomially closed classes, it's sufficient to talk about single-tape machines).

The proof for this is somewhat involved, and easily available with a simple web search, so I'll just sketch the key mapping of the $k$ tapes to a single tape.

The basic idea is pretty straightforward; we simply add a few new symbols and keep track of each tape and head one after the other. At each step in the computation we can only have visited a finite amount of any of the tapes, so we need only to store this much information about each tape. Thus for each $\gamma \in \Gamma$ we add a new symbol $\underline{\gamma}$ to $\Gamma$ which will indicate where the head (for each tape) is at any point in the computation. We also introduce a separator character $\#$ to $\Gamma$ which will indicate the start and end of the "virtual" tapes. Given input $\omega = \omega_{1}\ldots\omega_{n}$ (we can assume that even on the multi-tape machine all of the input is on the first tape - proving why is a good exercise) on the multi-tape machine, our single-tape machine will have input
$$
\underbrace{\#\underline{\omega_{1}}\ldots\omega_{n}\#\underline{\sqcup}\#\underline{\sqcup}\#\ldots\#\underline{\sqcup}\#}_{k \text{ sections, one per tape}}\sqcup\sqcup\sqcup\sqcup\sqcup\sqcup\ldots
$$

We then use the state of the single-tape machine to encode what state the multi-tape machine is in and what the heads are looking at. The transition function of the single-tape machine is a multistage simulation of the multi-tape transition function, where we perform the $k$ different tape actions appropriately, moving up the single tape to each section in turn. The only wrinkles left are shifting everything along when we run out of space in a section (but such a sub-machine is a simple exercise) - we never reduce the size of each section.

A (hopefully) simple example:

Say we have a 3-tape TM, where the input alphabet is just $\Sigma=\{0,1\}$, the tape alphabet is $\Gamma=\{0,1,\sqcup\}$ and the input is $\omega=10101$. The initial tape state of the machine looks like:
$$
\begin{array}{lc}
\text{Tape 1:} & \underset{\wedge}{1}0101\sqcup\sqcup\sqcup\ldots\\
\text{Tape 2:} & \underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\sqcup\ldots\\
\text{Tape 3:} & \underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\sqcup\ldots\\
\end{array}
$$
The "$\wedge$" is to denote where the read/write head is on each tape.

To construct the combined single-tape machine, we need to add new symbols to the tape alphabet:

We need a symbol that will denote the start and end of the simulated tapes
For each symbol in $\Gamma$ we also need a version that indicates that the simulated tape head is at that character on the simulated tape.

So for the single-tape machine, our new tape alphabet is $\Gamma' =\{0,1,\sqcup,\underline{0},\underline{1},\underline{\sqcup},\#\}$. The initial state of the tape is:
$$
\#\underset{\wedge}{\underline{1}}0101\#\underline{\sqcup}\#\underline{\sqcup}\#\sqcup\sqcup\sqcup\ldots
$$
Note the difference between the head of the machine (the $\wedge$) and the simulated heads of the 3 simulated tapes (the underlined characters). Of course the tape extends infinitely to the right as usual. I have also cheated mildly by moving the tape head to the first character on the first string; strictly it should start out on the leftmost cell, but this is a trivial technicality.

So we have three marked out sections (between the $\#$ marks), which will correspond to the 3 tapes of the original machine.

Now let's make up an action for the machine. Let's say that the original machine reads from the first tape, if it sees a $1$, it writes a $1$ on the second tape, if it sees a $0$ it writes a $1$ on the third tape. At each read or write, the head moves to the right.

So after the first "step" (perhaps requiring several states and transitions in the actual machine), the tapes should have a $1$ on the second tape, and the first and second heads will have moved right one step:

$$
\begin{array}{lc}
\text{Tape 1:} & 1\underset{\wedge}{0}101\sqcup\sqcup\sqcup\ldots\\
\text{Tape 2:} & 1\underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\ldots\\
\text{Tape 3:} & \underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\sqcup\ldots\\
\end{array}
$$

On the second go around, the first tape reads a $0$, so we write to the third tape instead:

$$
\begin{array}{lc}
\text{Tape 1:} & 10\underset{\wedge}{1}01\sqcup\sqcup\sqcup\ldots\\
\text{Tape 2:} & 1\underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\ldots\\
\text{Tape 3:} & 1\underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\ldots\\
\end{array}
$$

The single-tape machine simulates this by moving the underline (by using the alternate version of the characters in $\Gamma'$, and writing to the appropriate simulated tape. So after the first step, the combined tape looks like:

$$
\#1\underset{\wedge}{\underline{0}}101\#1\underline{\sqcup}\#\underline{\sqcup}\#\sqcup\sqcup\sqcup\ldots
$$

After the second step:

$$
\#10\underset{\wedge}{\underline{1}}01\#1\underline{\sqcup}\#1\underline{\sqcup}\#\sqcup\sqcup\sqcup\ldots
$$

Of course this is a high level view of the process - I haven't attempted to explain how to construct the states, or how each simulated tape gets longer (for this, you need a little routine that checks if you've run into the end of the simulated tape, then moves everything to the right one step along and squeezes in a new blank - i.e. it only adds simulated tape cells when they're needed).


How many times can you pour milk among 3 buckets? This is a problem from usaco, which I solved, but I don't know how to estimate the number of times you can pour milk among the jugs, my solutions just uses a big enough number.

Here's the problem statement:

  Farmer John has three milking buckets of capacity A, B, and C liters. Each of the numbers A, B, and C is an integer from 1 through 20, inclusive. Initially, buckets A and B are empty while bucket C is full of milk. Sometimes, FJ pours milk from one bucket to another until the second bucket is filled or the first bucket is empty. Once begun, a pour must be completed, of course. Being thrifty, no milk may be tossed out.

  Write a program to help FJ determine what amounts of milk he can leave in bucket C when he begins with three buckets as above, pours milk among the buckets for a while, and then notes that bucket A is empty.

  For example, if the input is 8, 9, 10 then the output is 1, 2, 8, 9, 10.

  Another example: if the input is 2, 5, 10 then the output is 5, 6, 7, 8, 9, 10.

My approach is to recursively try all possible move sequences, keeping track of the contents of bucket C each time bucket A is empty. Currently I stop the recursion at the arbitrary depth 200. What is the correct depth to stop the recursion at?

Since the total amount of water is C liters (C being the capacity of bucket C), the number of possible states is at most the number of non-negative integer solutions of $x+y+z = C$, which is $\binom{C+2}{2}$. Any sequence of moves longer than that must repeat a state. Therefore it is enough to recurse up to level $\binom{C+2}{2}$.


Simple question: Pushdown automata transition I am currently constructing pushdown automata.
can I push/pop alphabet more than two in a transition??

For example, $\delta$(a, a/aaa) means, in the state of input alphabet 'a' and stack point 'a' (there is only one item 'a') then it can push two more item 'a' on the stack so that there is three a's in the stack.

This depends on the formalism you are using.

As a "abstract data structure" you would have simple instructions like push(symbol), pop, top, isempty that you then can program as an add-on to a finite state automaton.

In standard formal language theory one uses a single instruction of the form you describe $(p,a,A,q,\gamma) \in \delta$ means: in state $p$ with $A$ on top of the stack we can pop $A$ and push the symbols $\gamma$ and move to state $q$. Thus we can indeed push several symbols at once, and we always pop one. With this single instruction we can also pop a symbol (by not pushing anything back) or keep the stack unchanged (by pushing back what has been popped).

In the Sipser book the formalism is different for instance.


How to simulate this randomized "finite" sum? Consider the the Geometric Brownian motion

$\qquad dX_t=\mu X_t dt+\sigma X_t dW_t$, with $X_0=1$, $\mu=0.2$, and $\sigma=0.30$.

for each $n=1,2,3,..$ let $h_n=1/n$, and let $X^n_n$ be the final value of the discrete process obtained from Euler scheme wrt $h_n$, i.e.

$\qquad  X^n_{k+1}=X^n_{k} +\mu X^n_k h_n +X^n_k \sigma \sqrt{h_n} \text{randn}(0,1),$

for $k=0,1,2,\ldots n-1$. Here $\text{randn}(0,1)$ means the standard normal random variable with mean 0, standard deviation 1.

That is, after using Euler scheme ,for each $n=1,2,3, \ldots$ you have a sequence  (which depends on $n$)

$\qquad \{1,X_1^2, X_2^n,\ldots, X_n^n \}$.

For simplicity assume that $F_n\equiv X_n^n$.

I do know how to find $F_n$ for $n=1,2,\ldots$.

Assume that $N\sim \text{Geometric}(p)$, i.e, $P(N=k)=(1-p)^{k-1}(p)$ ( let assume $p=0.5$ here for simplicity), for $k=1,2,3,\ldots$.

My question here is:

How to simulate this sum

$\qquad Y=\sum_{k=1}^{N}\frac{(F_{k+1}-F_{k})}{2^k} N^2 $?

Using geornd(p) provided by matlab, I do know how to generate $N$.
How to approximate $E(Y)$?

My confusion comes from here. There are random variables floating around here: $N$ and $F_{k+1}-F_{k}$. Assume that $N$ and $F_k$ are independent, so we have

$\qquad E(Y)=\sum_{k=1}^{\infty}\frac{E[(F_{k+1}-F_{k})]E[N^2 I_{k\leq N}]}{2^k} $.

Let me give you some basic principles that seem helpful for your problem:

How to estimate an expected value. You want to estimate $\mathbb{E}[Y]$.  Here's a standard fact: if you can sample from the distribution of $Y$, then you can estimate $\mathbb{E}[Y]$.  Concisely, what you do is sample $n$ values according to the distribution of $Y$, then take their average; the result is a pretty good estimate for $\mathbb{E}[Y]$.  The larger the value of $n$, the more accurate your estimate will be.

With more mathematical precision: let $y_1,\dots,y_n$ be the result of sampling $n$ times from the distribution of $Y$.  This means that they come from i.i.d. r.v.'s with the same distribution as $Y$.  Now let $\hat{y} = (y_1+\dots + y_n)/n$ be the average of these values.  Then it follows that $\hat{y}$ is a good estimate for $\mathbb{E}[Y]$ (with high probability).  In particular, $\mathbb{E}[\hat{y}] = (\mathbb{E}[y_1]+\dots + \mathbb{E}[y_n])/n = (\mathbb{E}[Y]+\dots + \mathbb{E}[Y])/n = \mathbb{E}[Y]$, so $\hat{y}$ is an unbiased estimator for $\mathbb{E}[Y]$.  Also, by a similar calculation, $\text{Var}[\hat{y}] = \text{Var}[Y]/n$; the interpretation of this is that the error in your estimate of $\mathbb{E}[Y]$ will typically be roughly on the order of $\sigma/\sqrt{n}$, where $\sigma = \sqrt{\text{Var}[Y]}$ is the standard deviation of $Y$.  Thus, if $Y$ has variance that is not too large, then this approach gives a reasonably accurate estimate of $\mathbb{E}[Y]$.

In your case, this shows how to answer your second question: if you can sample from $Y$, this gives you one candidate way to estimate $\mathbb{E}[Y]$.  There are other ways to get an estimate, but this is a simple method that applies whenever you know how to sample from the underlying distribution.
How to sample from a sum of random length. The next question is, how to sample from $Y$?  The challenge you seem to be struggling with is how to deal with the fact that the definition of $Y$ is as a sum containing $N$ terms, but where here $N$ is a random variable.

It turns out there is a simple way to deal with this.  In particular, you can sample from $N$ by using the following process:

Sample from $N$, i.e., pick a random value for $N$ by sampling from a geometric distribution (since that's the distribution of $N$).
Now you have a fixed, constant value for $N$, so it becomes easy to sample from $Y$.  In particular, for this fixed value of $N$, sample a random value for $F_1,F_2,\dots,F_{N+1}$ (according to the distribution of these random variables).  Then, plug those values into the definition of $Y$; the result will be a random value for $Y$, picked according to the correct definition for $Y$.

In general, if you have a random variable that is defined by some stochastic process, then you can sample from it by simulating the process, sampling from random values whenever the process does.

So, let me spell out the implications for you.  This means that if you can figure out how to sample from the distribution of $F_i$, then you can use the above two techniques to sample from the distribution of $Y$ and thereby estimate the value of $\mathbb{E}[Y]$.  This reduces your problem to a smaller/simpler one: figuring out how to sample random values, distributed according to the distribution of $F_i$.


Is there any meaning behind the classification of "λ-terms" in classes such as "church number" and "church list"? λ-calculus terms can be informally/intuitively categorized, such as:

(λ f x . (f (f (f x))))) is a church natural (3)
(λ a b . a) is a church boolean (true)
(λ c n . (c 1 (c 2 (c 3 n)))) is a church list ([1,2,3])
(λ s z . (s (λ s z . (s (λ s z . (s (λ s z . z))))))) is a peano natural (3)

That is, while the untyped lambda calculus obviously doesn't have explicit types, one can certainly recognize patterns on terms and categorize them based on their behavior - as if those had a type. When you say: "a church number is a function that applies another function n times to an argument" you are informally characterizing a wide range of λ-terms. My question is: is there any way to formalize that intuition? Any system/theory that meaningfully categorizes (untyped) λ-terms?

Several observations can be made based on your remarks:

In System F, every data type can be given an encoding using polymorphic types, e.g. $\mathrm{Bool}$ can be defined as the type
$$\forall A.A\rightarrow A\rightarrow A$$
On the other hand, certain terms (not all of course) can be given a principal type in system F, e.g.
$$\lambda ab.a $$
can be given the type $\forall AB.A\rightarrow B \rightarrow A$. But you can now notice that this is a generalization of the type $\forall A.A \rightarrow A \rightarrow A$, and this happens to be the most general type it shares with $\lambda a b.b$, which is of course the polymorphic encoding of $\mathrm{Bool}$. In this way, one can always attempt to assign the most general type to a term, and then check to see if this happens to be (a generalization of) the polymorphic encoding of a datatype.
Intersection type systems are usually undecidable type systems assigning types to pure $\lambda$-terms that have the remarkable property of classifying their behavior: in particular the most simple such system is complete for strong normalization: a term has a type iff it is SN.

In intersection type systems, it is always possible to interpret the set of all types of a term (ordered by the sub-typing relation) as a representation of the behavior of that term. In particular, there is a close correspondence between the various domain theory models of the pure $\lambda$-calculus and various intersection typing systems. See for example Intersection Types and Lambda Theories for an overview.


how two phase commit ensure serializability Two phase commit is used in distributed transaction. For example, a client sends a transaction to two databases with a coordinator.

step1: client get a global transaction id from coordinator
step2: client send the transaction to two databases respectively
step3: client send the commit flag to coordinator
step4: coordinator send prepare flag to two databases, and two databases response prepare ack
step5: coordinator send commit flag to two databases, and two databases response commit ack
step6: coordinator response commit ack to client

My questions are

What is the global transaction id in step1 used for?
And two phase commit is used to ensure the atomic in ACID, but how does it ensure the serializability? For examples, if client A sends transaction A and client B sends transaction B to databases simutaniously, then two databases may execute two transactions in different orders. Then two databases may end with non consistent states.

Let me try to explain this using an example. Suppose there is coordinator and two participants named P1 & P2.
Now suppose both P1 & P2 creates a transaction to modify a variable A and no other transaction is raised in between, in this case coordinator know that both participants are doing same this coordinator will raise a commit message indicating that both participants can commit and changes will be saved.
Now let's take other example Suppose variable A depends on variable B, now participant P1 raises message to modify variable A and at the same time participant P2 raises message to modify both B & A, in this case coordinator know that participants are going out of sync by executing these commands so master will decline this transaction since it will not serialize.
An assumption about the outcome of transactions, either commit, or abort, can save both messages and logging operations by the participants during the 2PC protocol's execution. For example, when presumed abort, if during system recovery from failure no logged evidence for commit of some transaction is found by the recovery procedure, then it assumes that the transaction has been aborted, and acts accordingly. [Wikipedia]


Can you solve 2-sat problem when truth assignments of some variables are determined I am trying to find a assignment to satisfy a 2-sat statement. Problem is some of the clauses are 0 or x or 1 or x. I think the 1 or x clauses have no effect on the solution, but the 0 or x clauses determine the value for x. As I have clauses like ~x or y the determined value for x results in determining the value for y and so on. Can I solve this problem with Krom's procedure?

First set all literals $x$ to $1$ if they appear in a clause $0 \vee x$, and set $\bar x$ to $0$. If that requires you to set some $x$ to both $0$ and $1$, it's unsatisfiable. Iterate this until you don't have to set any more literals to $0$. If you get this far without finding out that the formula is unsatisfiable, remove all clauses that contain a $1$. Now you either have no clauses left - then it's satisfiable - or some 2-CNF formula to which you can apply Krom's algorithm.

Alternatively, remove all clauses $1 \vee x$ and replace all clauses $0 \vee x$ by $(y \vee x) \wedge (\bar y \vee x)$ for a newly introduced variable $y$. You can directly apply Krom's algorithm (or more likely, a linear-time algorithm like that of Aspvall, Plass, Tarjan) to the formula you get this way.


calculate the effective (average) access time (E AT) of this system A computer with a single cache (access time 40ns) and main memory (access time 200ns) also
uses the hard disk (average access time 0.02 ms) for virtual memory pages. If it is found that the cache hit rate is 90% and the page fault rate is 1%

I have to work out the EAT time for this and the speedup due to use of cache.
I'm really confused about how to do this because I have seen two different ways of doing this and I'm not sure which is correct

solution 1: 0.90*40 + 0.10[0.01*20,000 + 0.99*200]=75.8 ns

solution 2: 0.90*40 + 0.10[0.01*(20,000+200) + 0.99*(2*200)]= 95.8 ns

In the second one, it accesses main memory twice when there is a page hit and accesses disk and main memory when there is a page fault. Which one is correct?

And for the speedup, which equation do I use?:
Memory access time/(Memory + Cache access EAT)
OR
EAT without cache/EAT

I would approach it this way : Consider 1000 requests made by the processor - the number arrived at by ensuring whole number of requests to each storage. 90 % or 900 of those are served by the cache. Of the 10 % or 100 which are not, only 1 % or a single request faces a page fault and 99 are served by main memory.

The Expected time per request = ( 900 * 40 + 99 * 200 + 20000 ) / 1000 = 75.8 ns.

The speedup due to the cache is based on the ratio of number of cycles spent on a set of operations without the cache to the same set with a cache.


k-basis representation of natural numbers (This is the problem 1.56 from Michael Sipser' Introduction to the theory of computation )

Let
$A_k(S)= \{ w |w \text{ is the k-basis representation}$
$\text{ without leading 0 of some natural number in the set S}\} $

Example : $A_2 (\{3,5\}) = \{11,101\} $

Let the statement $ P = \exists S \text{, a set of natural number where} A_2(S) \text{ is regular and }A_3(S) \text{ isn't.}   $

Is $P$ true ?

I think that $P$ is false.

Let's consider two case :

$S$ is finite :

Write a (possibly very long) regular expression which is the union of all of the k-basis representation strings of the numbers in $S$ no matter what $k$ is.

$S$ is infinite :

Construct a NFA $N$ that recognize $A_k(S)$ with :
$\text{For each symbol }e\in\Sigma\smallsetminus 0, \space$
$\delta(q_{initial},e) = q_{begin},\space q_{begin} \in F $
$\text{For each symbol }e\in\Sigma,\space \delta(q_{begin},e) = q_e ,\space \delta(q_e,\varepsilon) = q_{begin},\space q_e \in F  $

Am i correct ? (I think I'm not but I'm stuck with this, maybe I don't get the definition of $A$ correctly ).

Hint: For most infinite $S$, the languages $A_2(S),A_3(S)$ will both not be regular. Find some set $S$ for which $A_2(S)$ is regular (since the binary representations of numbers in $S$ are very simple), and with any luck $A_3(S)$ won't be regular. (Don't choose $S = \mathbb{N}$ or $S = \{ ax+b : x \in \mathbb{N} \}$.)


Write the Context free Grammar What will be the context-free grammar of $B= A_1.A_2 $
when $A_1 = \{0^n1^n|n\geq 0\}$
$A_2 = \{1^n0^n|n \geq 0\}$
Also verify using a string.
if  the Grammar for
$A_1$: $S_1 \rightarrow 0S_11 | \varepsilon$
$A_2$: $S_2 \rightarrow 1S_20 | \varepsilon$
I am stuck with the value of $S \rightarrow$ ?

Your grammars for $A_1$ and $A_2$ seem correct. Since you want to compute the concatenation of $A_1$ and $A_2$, you just need to express this fact with the start symbols of $A_1$ and $A_2$.
$S \rightarrow S_1S_2$ is a way to do it.
You can check by computing the derivation that creates the word $001110$.


Why is there no deterministic algorithm for determining the majority vote of a recursive 3 branch tree without inspecting all the leafs? Say that we have nodes in a tree and it has a branching factor of 3. At the leaves we have a binary value 1 or 0 (which can be viewed as "votes"). Each parent computes the majority of its children and assigns itself that value ("vote").

What I want to show is that in the worst case, a deterministic algorithm will have to query the value of all of the $n = 3^h$ leaves in order to determine the value assigned to the root.

I do have the following solution which I am having a hard time understanding:

But that algorithm doesn't seem to work in some trivial cases (unless I misunderstood the algorithm).

Say that A just started querying the leaves. So it queries the first leaf and since nothing has been assigned, when it goes to its first ancestor such that at most 1 is determined, since none of his siblings (which in this case are the siblings of the parent of the leaf, the uncles) have been determine, then that leaf is arbitrarily assigned true. When it goes to the next leaf, one should assign it false so that one has to inspect the other leaf, but when if you follow what the adversarial algorithm does it doesn't work. It says to go to the parent of the currently queried leaf and in this case, since still, none of the siblings of the parent have been assigned anything, then one would arbitrarily choose true, which is bad, because it determines the parent to be true without looking at the last leaf node of that subsection!

I am wrong or am I misunderstanding what $B$ is suppose to do?

Why isn't it just optimal to always choose 1 0 1 or 0 1 0 or 1 1 0 or however A queries leaves, to make sure that it always sees two leaf, such that it has to see the other leaf no matter what (i.e. if A sees a 1 to make sure the next thing it sees in that sub section of the leafs to see a 0 etc). I don't understand why we need to consider ancestors. Why does that matter?

For completeness I will provide the full text:

Yes, you are misunderstanding the algorithm. While I explain your misunderstanding below, in general, when such a misunderstanding occurs, see if you understand what the algorithm is trying to do, and then try to match your understanding with what is written.

While there are numerous errors in textbooks, usually they are slight and easy to correct. Whenever an error seems to have occurred (which doesn't seem to be the case here), see if you can try to correct it by making some small change to the argument.

In this case, the first ancestor of the second leaf which has at most one sibling determined is the leaf itself, which has one sibling determined. According to the strategy, our answer to the second leaf would be complementary to our answer to the first leaf.

Your misunderstanding might stem from the fact that for you a node is not considered its own ancestor. However, for this strategy to work, a node must be considered its own ancestor, as your example shows. Presumably the text defined ancestor correctly to include the node itself, but even if it doesn't you could correct the proof by changing slightly the meaning of ancestor. This demonstrates my points above regarding reading mathematical texts.


Relationship of algorithm complexity and automata class I have been unable to find a graph depicting or text answering the following question: Is there a direct relationship between the complexity of an algorithm (such as best / worst case of quick sort), and class of automata that can implement the algorithm. For example is there a range of complexity push down automata can express? If the answer is yes to said question is there a resource depicting the relationship? Thanks!

Here are some known results:

$\mathsf{REG} = \mathsf{DSPACE}(1) = \mathsf{NSPACE}(1) = \mathsf{DSPACE}(o(\log\log n)) = \mathsf{NSPACE}(o(\log\log n))$, where $\mathsf{REG}$ is the set of regular languages. For proofs, see the Wikipedia page on $\mathsf{DSPACE}$.
$\mathsf{DCFL} \subseteq \mathsf{SC}$, where $\mathsf{DCFL}$ is the set of deterministic context-free languages, and $\mathsf{SC}$ is Steve's class. See the Wikipedia page on $\mathsf{DCFL}$.
$\mathsf{NL} \subseteq \mathsf{LOGCFL} \subseteq \mathsf{AC^1}$, where $\mathsf{LOGCFL}$ is the set of languages logspace-reducible to a context-free language. See the Wikipedia page on $\mathsf{LOGCFL}$, which also gives some languages complete for $\mathsf{LOGCFL}$ under logspace reductions.
$\mathsf{CSL} = \mathsf{NSPACE}(n)$, where $\mathsf{CSL}$ is the set of context-sensitive languages. See the Wikipedia page on $\mathsf{CSL}$.
The class of languages accepted by deterministic nonerasing PDAs is $\mathsf{DSPACE(n\log n)}$, and the class of languages accepted by non-deterministic nonerasing PDAs is $\mathsf{NSPACE}(n^2)$. See the Wikipedia page on PDAs.
Two-stack automata are equivalent in power to Turing machines, but restricting the automata results in weaker models. See a technical report of San Pietro.


Proof of NP-completeness via extra information I have a set of multisets $S = \{ X_1, \dots, X_K\}$ where $X_i \subset \mathbb{R}$.  I need to find an optimal partition $L^*, R^*$ such that this $E(L) + E(R)$ is minimized. Denote $K(X) = \cup_{I \in X} I$, then
$E(X) := \sum_{i \in K(X)} |i - \text{median}(K(X))|$, where $|.|$ is the absolute value. $X_i$ might contains duplicated elements and all operations are on multisets; in $K(X)$, $\cup$ is a union of multisets, and in $E(X)$, $\sum$ adds "with repetition" (repeated elements are summed multiple times).
I want to prove this problem is hard, but I don't have a very straightforward way to prove it's NP-complete.
What I did instead was assuming given extra information, suppose I know the median of both $K(L^*)$ and $K(R^*)$, and then I can show find the optimal partition is an integer linear programming problem, which is NP-complete.  Can I conclude the original problem is at least NP-complete?

For the sake of sharing, a wrong attempt I did on proving NP-completeness of with extra information problem.
I was converting this "given $m_L = \textbf{median}(L), m_R = \textbf{median}(R)$ and $S$, find $L$ and $R$" problem into a integer programming feasibility problem. Thanks to D.W helped me, I should do the opposite. Maybe doing the opposite is also possible. So sharing my effort in case it helps.
We can collect two vectors $A, B$ with length $K$, for every $X_i \in S$, get the imbalance with respect to $m_L$ and $m_R$. Namely $A[i] = \sum_{j \in X_i} sign(m_L - j) $, $B[i] = \sum_{j \in X_i} sign(m_R - j) $, where $$\text{sign}(x) = \begin{cases}
1 &\text{if }x>0\\
0 &\text{if }x=0\\
-1 &\text{if }x<0
\end{cases}$$
Now we can introduce another boolean indicator vector $I = \{0, 1\}^K$. When $I[i] = 0$, we assign $X_i$ to $L$, if $I[i] = 1$, we assigns $X_i$ to $R$.
$$
\langle I, A \rangle = 0 \\
\langle 1-I, B \rangle = 0
$$
Since $m_l$ is the median of $L$, we would definitely have the sum of imbalance equals to 0. The same applies to $m_R$. And here $A, B$ are coefficients and $I$ is the variable. If such a problem has any solutions, then we found $L$, $R$.
And clearly, the newly formed problem is an integer programming problem. Which is well-known NP-complete.  Whether if it is possible to convert any such type of problem into our set partition problem in polynomial time, I still need some help

No.  Your argument is not valid; it doesn't prove NP-completeness.  You have shown that an ILP solver can be used to solve your problem.  But an ILP solver can be used to solve easy problems, too, so it doesn't rule out the possibility that your problem might be easy (solvable in polynomial time).  The reduction needs to go the other way.  I suggest studying standard material on NP-completeness and reductions, e.g., What is the definition of P, NP, NP-complete and NP-hard? and What are common techniques for reducing problems to each other? and How do I construct reductions between problems to prove a problem is NP-complete?.
As it happens, I believe your problem can be solved in polynomial time; in other words, I believe it is not hard.  I believe the following algorithm solves your problem:

Enumerate over all possibilities $m_L,m_R$ for $\text{median}(K(L))$ and $\text{median}(K(R))$.  For each such possibility:

Find the partition $L,R$ that minimizes $E(L)+E(R)$, subject to the requirement that $\text{median}(L)=\mu_L$ and $\text{median}(R)=\mu_R$.

Output the best solution found at any of these stages.

I show below how to do the innermost step in polynomial time.  This gives a polynomial-time algorithm for your problem, as there are only $O(n^2)$ possibilities for $m_L,m_R$ (i.e., each $m_L,m_R$ must be an element of $\cup_i X_i$).
We'll use dynamic programming for this.  Let $\text{imb}(T,m)$ be defined by
$$\text{imb}(T,m) = (\sum_{t \in T} \text{sgn}(t-m), \sum_{t \in T} (t=m))$$
where the sum is "with repetition", and where
$$\text{sgn}(x) = \begin{cases}
1 &\text{if }x>0\\
0 &\text{if }x=0\\
-1 &\text{if }x<0
\end{cases}$$
$$(x=y) = \begin{cases}
1 &\text{if }x=y\\
0 &\text{otherwise}
\end{cases}$$
Define the imbalance of a partition $L,R$ with respect to $m_L,m_R$ to be the pair $(\vec{b_L},\vec{b_R})$ where $\vec{b_L}=\text{imb}(L,m_L)$ and $\vec{b_R}=\text{imb}(R,m_R)$.  Then we can reformulate the problem as follows:
Given $m_L,m_R$, find $L,R$ that minimizes $E(L)+E(R)$ subject to the requirement that the imbalance of $L,R$ with respect to $m_L,m_R$ is $(0,0)$ (or $+\infty$ if no such partition exists).
Now we can solve that using dynamic programming.  Define $A[k,\vec{b_L},\vec{b_R}]$ to be the smallest possible value of $E(L)+E(R)$ subject to the requirements that $L,R$ are a partition of $X_1,\dots,X_k$ with imbalance $(\vec{b_L},\vec{b_R})$ with respect to $m_L,m_R$ (or $+\infty$ if no such partition exists).  Then $A$ satisfies the recurrence relation
$$A[k,\vec{b_L},\vec{b_R}] = \min(A[k-1,\vec{b_L}-\text{imb}(X_k,m_L),\vec{b_R}] + \sum_{i \in X_k} |i - m_L|,A[k-1,\vec{b_L},\vec{b_R}-\text{imb}(X_k,m_R)] + \sum_{i \in X_k} |i - m_R|).$$
Using this recurrence, you can fill in the array $A$ in $O(Kn^4)$ time, where $n=|\cup_i X_i|$ is the number of elements (counting repetitions): you just initialize every entry to $+\infty$ except that $A[0,0,0]=0$, then fill it in, in order of increasing $k$.  Then, scan  all $A[K,(a,b),(c,d)]$ such that (i) $|a|<b$ and $b>0$, or $a=0$, and (ii) $|c|<d$ and $d>0$, or $c=0$; the smallest such value is the answer to the original problem.


ANN architectures that perform faster/efficient prediction over time? ANN when compared to biological neural systems have this common concept of reducing error in prediction over time (training) and becoming more good at predicting correctly. But there is one behavior of biological neural system where the prediction do become good over time but it also becomes fast and uses less energy, it seems like the system is able to do the prediction based on few input rather than requiring all the inputs. For example when you start to learn to read, you have to look at each character and then then brain predicts what the word is but over a period of time you don't even look at the whole word and the prediction becomes more fast and efficient by using just a small portion of the input.

Are there any ANN architectures with their corresponding learning methods that have this aspect of becoming more efficient in prediction along with more correct prediction?.

The machine learning term for this is dimensionality reduction (see here for a survey), which is used in a more general context than just neural networks.

Dimensionality reduction can be both supervised and unsupervised. An example for unsupervised dim. reduction is PCA, in which a projection onto a lower-dimension space is found, in a way that preserves distances / structure as much as possible. In the case of supervised dimensionality reduction, the labels of the training set are also used in order to reduce the dimension. This is, however, a more advanced research area. This paper and references therein would be a good starting point.

Hope this helps.


Proving that Rice's theorem does not apply to a property This is related to an assignment, but I would still appreciate help in formalising proof either through private message or on this topic.

The question is about if Rice theorem applies to certain property. For example for a structural property such as number of states. I would argue that:

The property is decidable through its definition in encoded form.
The property is irrelevant to the language, because given the same language we can easily find another TM that does not have this property, ie one with empty states, so the property is not a language property, and hence Rice Theorem does not apply, since by definition, Rice theory only applies if it is a non trivial language property.

To me, this seems to be a good argument, but the question is assign a substantial mark of 10, and I feel like this is not enough for 10 marks, am I missing out some rigorous argument that I need to include to make my explanation crystal clear?

The answer is right but the argument is not sufficient. Try to build a contradicting example as a proof. Describe how to encode each machine into a binary number (can be found in any tcs book). Then choose some random non-trivial property say number of tates equal to 4. Show that there is a machine the belong to the ass and a machine that does not. Finally describe a universal machine deciding the property (which is doable if the encoding is injective/reverseable (which is usually the case). Since the example contradics the theorem it early does not apply here. The intuitive reason is that you defined property in machines and not on languages.


Maximum Equal Sum K Subsequences Given an array we need to find maximum equal sum $K$ subsequences, i.e. we want the sum to be maximized such that there are exactly $K$ non-overlapping subsequences each having the same sum.
Example:

A = [1, 2, 3, 4, 6] & K = 2
Maximum Sum Subsequence = 8 = [2, 6] & [1, 3, 4]

If, K = 3 and A = [1, 2, 3, 4, 6, 8, 9]
Maximum Sum Subsequence = 11 = [9, 2] & [8, 3] & [6, 4, 1]

It is not necessary that all the elements of the array need to be a part of the subsequences but each element can only be part of 1 subsequence.

I tried a brute force approach with Knapsack but that doesnt work.
Any better approaches or optimizations?

This problem is NP-complete by reduction to the given subset sum problem, which asks if there is a subset $S$ from a set with a certain sum $n$.

Suppose we are given such an instance and that your problem can be efficiently solved. Then we can transform the instance by making $S' = S \cup \{x, x - n\}$ for some sufficiently large $x$ and solving your problem to find the $K = 2$ maximum equal subsequence sums. Then iff the answer includes $x$ and $x - n$ there is a subset that sums to $n$ and we efficiently solved the given subset sum problem.


Approximation of a gaussian function I want to approximate a Gaussian function as shown below
$$
e^{\frac{-\|x-c\|^2}{2\sigma^2}} \approx \sum_{i=1}^{N}\alpha(c,c_i)e^{\frac{-\|x-c_i\|^2}{2\sigma^2}} \forall x
$$
Here c, $\sigma$ and $c_i$ are known. Are there functions $\alpha(c,c_i)$ which gives a good approximation? The limitation I am facing is that I can not optimize as I have to calculate the functions $\alpha$ for various c(around 1024*1024) thus leading to too many optimizations. I used linear solver as this optimisation problem can be framed as $A\alpha=b$. Here $x$ in the above equation is sampled according to each $c$. Hence for every $c$, both $A$ and $b$ in $A\alpha = b$ changes.

I am also fine if functions in RHS are not Gaussians i.e existence of pair of $\alpha$ and $f_\sigma$ such as

$$
e^{\frac{-\|x-c\|^2}{2\sigma^2}} \approx \sum_{i=1}^{N}\alpha(c,c_i)
 {f_\sigma}(x,c_i) \forall x
$$

Can someone help me to point out how to go about it?
Here N can be treated as a variable. So as N increases number of gaussians used to interpolate increases and hence get a better approximation.

Now to explain what I meant by a good approximation : The function in LHS is used as a filtering kernel to filter my data. Replacing it with RHS (one part of my algorithm) will help in speeding up my filtering algorithm by a huge margin. Now I check my performance by comparing actual filtering algorithm and this approximation by using parameters such as Mean Square Error.

One approach could be to use least-squares fitting.

Your problem is: given functions $f_1,\dots,f_N$ and $f$, we want to find constants $\alpha_1,\dots,\alpha_N$ such that

$$f(x) \approx \sum_i \alpha_i f_i(x).$$

Here

$$f(x) = e^{\frac{-\|x-c\|^2}{2\sigma^2}}$$

and

$$f_i(x) = e^{\frac{-\|x-c_i\|^2}{2\sigma^2}}.$$

To make this problem well-defined, we need to make precise the notion of approximation.  One plausible notion is the $L_2$ error of the approximation, i.e., the error is

$$E = \int \big( f(x) - \sum_i \alpha_i f_i(x) \big)^2 \; dx.$$

This is tricky to compute, but we can approximate $E$ by picking values $x_1,\dots,x_m$ and then calculating

$$\hat{E} = \sum_j \big( f(x_j) - \sum_i \alpha_i f_i(x_j) \big)^2.$$

If the $x_j$'s are chosen appropriately (e.g., evenly spaced over the range you care about; or randomly chosen according to the distribution of $x$-values you're likely to evaluate the approximation at), and if $m$ is large enough, then $\hat{E}$ should be a good approximation to $E$.

So, the problem becomes: given functions $f_1,\dots,f_N$ and $f$ and values $x_1,\dots,x_m$, we want to find constants $\alpha_1,\dots,\alpha_N$ that minimize the error $\hat{E}$.

This turns out to be exactly a multiple linear regression problem.  We try to find a fit

$$z = \alpha_1 y_1 + \dots + \alpha_N y_N$$

where $y_i = f_i(x)$ and $z = f(x)$.  We can evaluate the $f_i$'s and $f$ at any input $x$ of our choice.  When we evaluate at $x_j$, we obtain a single input $(y_1,\dots,y_N)$ and a single output $z$; in this way, we obtain $m$ matching input-output pairs.  You can now use a standard library to solve this multiple linear regression problem and find $\alpha_1,\dots,\alpha_N$.

All that remains is to choose $m$ and $x_1,\dots,x_m$.  I would suggest that you try to figure out what values you'll evaluate the approximation on, and choose the $x_j$'s randomly from the distribution (it might be a uniform distribution over some range, or something else), or choose the $x_j$'s to be evenly spaced over some range.  The larger $m$ is, the better the approximation will be, but the longer the algorithm will take, so experiment with some different values of $m$ and see what the tradeoff is.  My guess is you'll want $m$ to be a small constant multiple of $N$ (say $m=2N$), but you can see what you get.

Since you said $N$ is small (8--16), this should be very fast.

An optimization: Since you're going to repeat this many times with the same values for $c_1,\dots,c_N$ (i.e., $f_1,\dots,f_N$) but a different value of $c$ each time, you can also speed things up.  If the matrix is $X$ and the vector is $y$, the solution is $(X^\top X)^{-1} X^\top y$, where $X$ depends only on the $c_i$'s but not on $c$.  Thus, you can precompute the matrix $(X^\top X)^{-1} X^\top$ (once), then for each instance of the problem you want to solve, you just have to do a matrix multiplication -- no need to solve a new linear system.

Lastly, one optional refinement you could also try: use multiple linear regression to choose $\alpha_i$'s, then follow that up with gradient descent to fine-tune the $\alpha_i$'s and improve the quality of the approximation.  Often if you choose a good starting point that is close to optimal, gradient descent will converge faster.  Thus you can use the solution from multiple linear regression as the starting point for the gradient descent optimization routine.


Context free grammar for $L = \{u\#v \mid u,v \in \{a,b\}^* , \vert u \vert_a \neq \vert v \vert_a \text{ or } \vert u \vert_b \neq \vert v \vert_b\}$ I try to find a context free grammar for the language  $L = \{u\#v \mid u,v \in \{a,b\}^* , \vert u \vert_a \neq \vert v \vert_a \text{ or }  \vert u \vert_b \neq \vert v \vert_b\}$. There is a hint in the task that one should first construct the context free grammar for cases such as
$L_1 = \{u\#v \mid u,v \in \{a,b\}^* , \vert u \vert_a > \vert v \vert_a\}$ and later combine all of these.

I would appreciate a hint to come up with $L_1$. I do not know how construct $u\#v$ such that $u$ and $v$ are free independent from each other except of the fact that $u$ has more $a$'s than $v$. I tried to build my language around the $\#$ and also tried to move the $\#$ in the direction of the most appearing $a$'s but none of my attempts worked.

What is the proper way to tackle such constructions in general?

I'll just show how to build a grammar for  $L_1 = \{ u\#v, |u|_a > |v|_a \}$. Then it'll be straightforward to combine 4 similar grammars into a grammar for $L$.

The idea is to write $u\#v$ as $xay\#v$ with $x,y,v \in \{a,b\}^*$ and $|y|_a = |v|_a$.  The construction of $y\#v$ is handled by the non-terminal $Z$ which "grows" it from the center.

$$
\begin{align*}
S &\to aS \mid bS \mid aZ \\
Z &\to bZ \mid Zb \mid aZa | \,\#
\end{align*}
$$


Is there any algorithm for 3SAT problem that is fast and relatively easy to implement? Here is the description for 3SAT satisfiability problem. I already know about the DPLL algorithm, but it's implementation is pretty complex. I would like some algorithm that is relatively simpler but improves the performance by some extent. I would prefer something that is not Tree/Graph based instead bit-mask or multi-bit assignment based approach.

If you're determined not to use the standard deterministic algorithm, the usual alternative is what's known as local search or stochastic search.  The basic idea is that you start with a random bit pattern as a variable assignment, observe what's wrong with it in terms of unsatisfied clauses and try to improve it by flipping one or more variable assignments.  Observe how this new assignment fails, try to improve it, and repeat.
Local search typically outperforms deterministic search for satisfiable random SAT instances, but performs poorly on more structured instances.  It also offers no way to prove unsatisfiability unless some proof system is layered atop it.
There are various local search algorithms on offer, from Uwe Schöning's scheme to PPSZ and its variants.  None of them outperform DPLL-based solvers on all instances.


Single pair shortest path algorithm with time a constraint I am trying to solve the shortest path problem between n cities. Any single pair shortest path algorithm such as Dijkstra's and Bellman-Ford would work here, but if we add a simple additional constraint "the total time should not exceed T time units", then the problem becomes much harder.

More formally:

The input consists of a set of n cities and m roads between pairs of cities. There can be  multiple roads between a pair of cities $(i, j)$. For each road, you are given its departure city $x_i$, its destination city $y_i$, its duration $d$, and its cost $c$. The objective is to find the cheapest path between a pair of cities $(a, b)$ such that the cost is minimized while keeping the duration less than the maximum duration $T$.

I tried thinking on the lines of Dijkstra's and modifying the graph so that it is in some way possible to run a shortest path algorithm on it, but there seems to be no trivial way of doing this. Simple solutions like (follow a greedy strategy until you exceed the time limit, and then move on to the next element in the priority queue) don't seem to work because the use of a priority queue in the Dijkstra's algorithm and DEQUEUING the minimum element from the priority queue behave like destructive operations. There is a need to backtrack (of sorts) but the shortest path algorithms visit each node in the graph only once.

I've tried thinking about other simpler approaches using the Bellman-Ford algorithm, but the time complexity of the algorithm I  turned out writing depended on $T$ (which is not very desirable).

I spent almost 2 days on this and every solution I try either seems to not work, or runs in exponential time. Is this problem NP hard or are there polynomial time solutions possible?

P.S. I am not looking for a practical implementation of this problem, just an algorithm that can solve this problem in polynomial time. Although any thoughts about how to efficiently implement this would be more than welcome :)

Your problem is NP-hard: The partition problem reduces to it as follows:

Let $ S = \{s_0, ... , s_{n-1} \} $ be a multiset of non-negative integers.

Construct cities $ \{ c_0, ... , c_n \} $, with each city $ c_i $ having 2 roads to $ c_{i+1} $, one with duration $ 0 $ and cost $ s_i $, the other with duration $ s_i $ and cost $ 0 $.

Then find the minimum-distance path from $ c_0 $ to $ c_n $ with total duration at most $ \frac 1 2 \sum S $.  This path has equal cost and duration iff $ S $ can be partitioned into subsets of equal sum.


Algorithm to maximize $j-i$ subject to $A[j]>A[i]$ We want an algorithm that, given an array $A$ of length $n$ of integers (indexed by $A[0],A[1],\ldots,A[n-1]$, determine values $i<j$ that maximizes $j-i $ subject to $A[j]>A[i]$ (if such values $i,j$ exist.)

One possibility is as follows: First check whether the array is non-increasing. If so, no such $i,j$ exist. Else, iterate through the elements from front to back, keeping a running array which we append the current element if it is the minimum so far. This running array is decreasing, and we can use binary search to find the greatest element that's less than the current element. We update $j-i$ if it beats the previous maximum. This takes time $O(n\log n)$ because of binary search.

Is there a faster way, e.g., an $O(n)$ algorithm?

As you mention, the candidate $i$s are those who are left-to-right minima, and they form a decreasing sequence. Similarly, the candidate $j$s are right-to-left maxima, and they form an increasing sequence going from right to left (so a decreasing sequence in the usual order). Now imagine keeping two points, one on the left-to-right minima, starting at the leftmost, and another on the right-to-left maxima, starting at the rightmost. Is there a way to traverse both lists in $O(n)$, answering your question on the way?


How to turing reduce equivalent languages $Q$ to infinite language $I$ Given two languages:

$Q= \{(\langle M_1 \rangle , \langle M_2 \rangle ) \mid L(M_1) = L(M_2)\}$

$I= \{\langle M \rangle \mid \;\vert L(M) \vert = \infty \}$

I'm trying to Turing reduce $Q$ to $I$ ($Q \le_T I$), not the other way around as solved here

Any ideas on how to solve this? What exactly will the Turing machine do here and which part is getting solved by the mysterious Oracle?

Given $M_1$ and $M_2$ you construct a machine $M$ that on input $w$ does the following:

it runs $M_1$ on the first $w$ inputs ($\epsilon$,0,1,00,01,..) for $w$ steps each.

if  $M_1$ accepts some input, you run $M_2$ on the same input and check it accepts too. (note, $M_2$ may not halt!)
If $M_1$ rejects some input, you run $M_2$ for $w$ steps and verify it doesn't accept during that time.

you do the same with $M_2$: run $w$ steps on each of the first $w$ inputs, and verify everything works, or reject otherwise
if all checks pass - accept. Otherwise reject.

The idea is the following: as long as $M_1$ and $M_2$ behave the same, you will keep accepting all $w$'s. but as long as you find a difference, then you will reject that $w$ and all inputs $w'>w$, thus the accepted language becomes finite. You should be careful because machines may not halt. For instance, $M_1$ may reject some input, but $M_2$ won't halt on it -- still, they both "reject" it, and this case should be carefully analyzed.


Union of finite and non-regular language Question: ($B$ and $C$ are languages)
$B$ is finite,$C$ isn't regular:

Prove/Disprove: $C\cup B$ isn't regular.

Thoughts:
My intuition says this is true, but I need an idea to prove it. Since I don't know if $C$ as a CFG or RE language I don't know what kind of machine I can build for it.

Hint 1: Try to prove the contrapositive, namely: if $C\cup B$ is regular and $B$ is finite, then $C$ is regular.

Hint 2: Use closure properties of regular languages.


Algorithm for assigning people to groups Given a list $L = [1, 2, .., n]$ and a list $C = [(L_i, L_j), ....]$ form a group of pairs $G = g_1, ..., g_{n/2}$ such that:

every element of $L$ is assigned to exactly one group
$g_k = (L_i, L_j) \Rightarrow (L_i, L_j) \notin C $ (constraint)

I get that there are (potentially) many solutions to this problem.
How can one construct a recursive algorithm $group(L, C)$ to that returns a possible grouping?
I get that you can: 1) Create all pairs from $L$ and 2) Create all possible groups of size $n/2$ from the pairs and select one group that is legal.
I see that there are $N_P = {N\choose 2} = \frac{n!}{2!(n-2)!}$ potential pairs in $L$. The number of groups is then ${N_P\choose N/2} = \frac{N_P}{(N/2)!(N_P-N/2)!}$
Then one has to go through all these groups and check if it is legal and return it if so.
Any other solutions?

This problem is equivalent to Perfect Matching
We can view the input as an almost-complete graph, with L as its vertices and every two vertices connected by an edge except for those in C. We then want to find a set of edges that uses every vertex exactly once. This is the perfect matching problem.
To solve this problem, you can use any algorithm for finding a maximal matching, and check if the maximal matching has $n/2$ matches.


Show that the string $( [ ) ]$ is not in a Dyck language I think I understand why the string $( [ ) ]$ is not in a Dyck language.

In my words,

D2* is all the dyck words of 2 parentheses.

From the definiton of $D2*$, every words must have exactly 2 pairs correctly nested pairs of parentheses.

All the words of the language are given by

$\sum = { (1, )1, (2, )2 } $

The alphabet consisting of 2 kinds of left and right parentheses.

The language is given by the following grammar :

Terminal set is $\sum$
Start variable is not in terminal set
$ S -> \big( \epsilon | SS | (i S )i \big)$ for all i > 1

But the form of that word is $(i (j )i )j$  which fails to match the definition.

But I'm having trouble writing a formal proof on that.

Consider producing a leftmost derivation of ( [ ) ]. We can begin with
$$
S\Rightarrow SS\stackrel{*}{\Rightarrow}SS\dotsc S
$$
and to get the ( on the left we must eventually use the production $S\rightarrow(S)$ on the leftmost $S$, giving
$$
S\stackrel{*}{\Rightarrow}(S)S\dotsc S
$$
and then we'll have
$$
S\stackrel{*}{\Rightarrow}(SS\dotsc S)S\dotsc S
$$
and to get the [ as the second terminal on the left we must eventually use the production $S\rightarrow[S]$, giving
$$
S\stackrel{*}{\Rightarrow}([S]SS\dotsc S)S\dotsc S\stackrel{*}{\Rightarrow}([SS\dotsc S]SS\dotsc S)S\dotsc S
$$
and now we're stuck, since no production will give us the ) terminal we need on the left without introducing a ( first.

For a slightly different take, consider that $S$ can only derive strings in $D_2$, so to  derive ( ]  ) ] we must use the production $S\rightarrow (S)$, where the $S$ in the right term of the production must also derive a string in $D_2$, but that would imply $S$ derives ], which cannot be, since $]\notin D_2$.


what does the redundancy of a code means? I was reading a paper about a transposition and single deletion error correcting code and they claim that the redundancy of the code was only $\log(6n-3)$ bits.

But what does that means? I was trying to get that from the proof of that fact but what they proved instead was that

there exists a such (with the structure they propose) code whose redundancy is at most $\log(6n-3)$ bits

and in the proof itself they just said that the cardinality of the code is greater or equal than $\frac{2^n}{6n-3}$.

How does that proved the hypothesis?

Also, if I have my own code how do I compute the redundancy (or a reasonable bound on it?)

A linear error-correcting code encodes $m$ message bits using $w$ encoded bits. The redundancy is $r = w-m$. In other words, it is a collection of $M = 2^m$ codewords out of the possible $W = 2^w$ words of length $w$. We can extract the redundancy using the formula
$$ r = \log_2 \frac{W}{M}. $$
This formula makes sense for arbitrary error-correcting codes.

In your case, codewords are of length $n$, and there are at least $2^n/(6n-3)$ of them. Therefore the redundancy is at most
$$ \log_2 \frac{2^n}{2^n/(6n-3)} = \log_2 (6n-3). $$


Minimizing total distance to a point from a set of points I've read about a problem:

  There are $n$ houses that are placed randomly. Place a parking lot so that the (straight-line) distance to all houses is minimal.

I've written a Monte-Carlo algorithm, but that can't be the optimal approach.

Is there a solution other than approximating the position with Monte-Carlo method? Especially by using a graph or is that a wrong approach?

Is there a way to calculate the optimal position?

What is the name of this problem?

It's a two-dimensional facility location problem. In this case, the optimum location is the centre of gravity (also known as the barycentre or centroid) of the locations of the houses, which is easily calculated from their co-ordinates.


Find the center node on a weighted, non-directed graph So I have a problem, and it's an assignment from school.

This is a figure made out of matchsticks.
The goal is to find the optimal location to light up the figure so that it burns in minimal time. You can only light it up at integer positions (C,B) but not A. Different matchsticks may have different burn times.

My approach to this problem:

Iterate through every possible "light up" point
For every "light up" point, light up the figure and wait it to burn completely
Store the time it took to burn
Once iteration is complete, find the lowest time and there's your answer

The problems with my approach

Burning each figure will take a while since it's done realtime. It's also possible to do it faster then realtime, but I still don't think it's a viable solution.

Problems with center of a weighted graph:

What if we come up with A as the center?

Solution:

Just pick the next potential center and check if it's a valid "light up" point.

So I'm looking for a graph algorithm that can calculate the center on a weighted graph. I've never dealt with graph algorithms before, so that's why I'm asking here.
I'm also just asking for you to point me in the right direction, and not write the code for me (although I guess some pseudo code will come in handy).

Use the Floyd-Warshall algorithm to compute all-pairs shortest paths (i.e., compute the distance between each pair of nodes).  Then it is easy to find the center of the graph by enumerating all possibilities for the center node.  The running time will be $O(n^3)$.


Turing machine that checks whether a given string is an output of a given machine and input Is there a Turing machine such that, given a description $\langle M \rangle$ of a Turing machine $M$, an input $x$ and a string $y$, computes whether or not $y$ is the output of $M$ input $x$?
My guess is that the answer is no because this might imply that the set of strings with Kolmogorov complexity greater than or equal to their length is decidable.

No, in fact any non-trivial semantic property of Turing machines is undecidable. This result is Rice's theorem.


Decomposition of the set of computable functions into base functions Say I have some computation model/programming language $M$ (e.g. Turing machine or equivalent), and let $C_M$ be the set of all partial or total functions $f : \mathbb{N} \to \mathbb{N}$ computable by that model. Also, assume that $C_M$ is countable.

Now let $B = \{ B_1, B_2, ... , B_n \}$ a finite set of computable base functions and $\cdot : C_M \times C_M \to C_M$ an binary operator, which serves as a combination function. Thus, $(B,\cdot)$ is a magma.

I can now choose $B$ and $\cdot$ in such a way that I can decompose each computable function $f \in C_M$ into a finite product from $(B,\cdot)$, i.e. $\forall f \in C_M : \exists b_1, b_2, ..., b_k \in B : f = b_1 \cdot b_2 \cdot ... \cdot b_k$.

To show that, I consider that my programming language consists of a set of instructions $I$ and programs are words over $I$. Then, I choose exaclty one base function $b_{i,m}$ for each instruction $i_m$. Because each computable function $f$ has at least one program computing it, I can just pick one of those $f$-computing programs $P_f \in I^*$ and define
$b_{i,a} \cdot b_{i,b} \cdot b_{i,c} ...  = f$ when the program is the word $P_f = i_a i_b i_c ...$.

This decomposition is obviously not very useful, because it makes the base vectors arbitrary and the definition of $\cdot$ an infinite list of special cases. To consider it useful, the operator $\cdot$ should have some form of structure/finite definition, or in other words, be computable. My interest would be an element-wise function, so that given two values $f(x)$ and $g(x)$, it should be possible to compute $(f\cdot g)(x)$.

My question: Assuming $M$ is turing-complete, is it possible to choose $(B,\cdot)$ in such a way that $\cdot$ is elementwise computable, i.e.

$\exists h \in C_M : \forall f,g \in C_M : \forall x \in \mathbb{N} : (f\cdot g)(x) = h(f(x), g(x))$

and still have each computable function being decomposable into a finite product from $(B,\cdot)$?

Unlambda is an example of a Turing-complete programming language that implements your requirements.

Unlambda has only one type, functions. They are also its only basic syntactic elements. In particular there are no variables.
Its expressive power only requires two base terms, s, and k. They would be your base $B$. k takes two arguments and returns the first, while s takes three arguments, and applies the result of applying the first one to the third one, to the result of applying the second one to the third one.
It has an additional construct, `, which represents function application. It would be your binary operator $(\cdot)$. It is written in a prefix manner.
So for any term X, Y and Z we have ``kXY = X, and ```sXYZ = ``XZ`YZ. These simple rules, believe it or not, are sufficient to make Unlambda Turing-complete.
Unlambda has a few more built-ins but they are just here to make the programmer's life easier (although mentioning easy anywhere in the context of this language is probably an overstatement).

Natural numbers can be represented using Church's method, e.g. $3$ can be written as ``s``s`ksk``s``s`kski (note i, the identity, can be written as ``skk). Pretty simple, no? Recursion can be defined by building a fixed point combinator, and from there the usual techniques can be applied to define more and more complex functions until an universal Turing machine has been simulated.

This language is based on SKI combinator calculus, which itself finds its source in Combinatory Logic. There is a simple mapping between the Lambda and SKI calculi, which luckily makes proving Turing completeness much easier than actually doing the work!

Now that I've introduced the programming language, which is the most interesting part and the crux of this answer, let's go through the tedious details of how to use it to formally answer your question.

First define an embedding $\phi$ of unlambda programs (restricted to s and k) into the natural numbers. We could use base-4 encoding by mapping its alphabet $\Sigma = \{\text{k}, \text{s}, \text{`}, \text{^}\}$ with $\{0, 1, 2, 3\}$ ($\text{^}$ is the start-of-string character). So for example $\phi(k) = \phi(\text{^k}) = 30_4 = 12$, and $\phi(i) = \phi(\text{^``skk}) = 322100_4 = 3728$.
We can then define $\phi^{-1}$ as the opposite operation, except that for convenience, we'll remove the starting $\text{^}$. So $\phi^{-1}(12) = \text{k}$
Let's also define an unlambda evaluation function $\text{uneval}$, partially defined on $\mathbb{N}\times\mathbb{N}$ and mapping to $\mathbb{N}$. For any $p$, $q$, $\text{uneval}(p,q)$ is defined as the number of stars printed when compiling and running $\text{``}||\phi^{-1}(p)||church(q)||.*$ as an Unlambda program, where $church(q)$ is the representation of the $q$-th church numeral in Unlambda, $.*$ is the Unlambda function which prints one star, and $||$ represents string concatenation. If the Unlambda program thus defined doesn't compile or never halts, then $\text{uneval}$ isn't defined on $(p,q)$.
Then define the following functions

$k : \mathbb{N} \to \mathbb{N}, n \mapsto 2\phi(\text{^k})+1 = 25$
$s : \mathbb{N} \to \mathbb{N}, n \mapsto 2\phi(\text{^s})+1 = 27$
$init : \mathbb{N} \to \mathbb{N}, n \mapsto 2n$

Let $B = \{k, s, init\}$
Define $h : \mathbb{N}\times\mathbb{N} \to \mathbb{N}$ as follows

$h(2p, n)$ is undefined
$h(2p+1,2q+1) = 2\phi(\text{^`}||\phi^{-1}(p)||\phi^{-1}(q))+1$, if $\phi^{-1}$ is defined on $p$ and $q$, and undefined otherwise
$h(2p+1,2q) = \text{uneval}(p,q)$, if $\text{uneval}$ is defined on $(p,q)$

Define $(\cdot)$ as $(f\cdot g)(n) = h(f(n),g(n))$.

Using these definitions, we have

$h \in C_M$, because $\phi$, $\phi^{-1}$, $||$, $\text{uneval}$ and basic arithmetic are all computable.
and $\forall f,g \in C_M : \forall x \in \mathbb{N} : (f\cdot g)(x) = h(f(x), g(x))$, by definition of $(\cdot)$

Finally, $(B, \cdot)$ generates $C_M$ entirely, because

Unlambda (restricted to s and k) is Turing-complete, so I can build a (restricted) Unlambda function for any computable function in $C_M$.
I can build a constant function whose value is the representation of that Unlambda function using $s$, $k$ and $(\cdot)$. For example, for add1 =  `s``s`ksk, I can build $s\cdot((s\cdot(k\cdot s))\cdot k)$ whose constant value is $2\cdot3212212010_4+1 = 1889033$
I can build a function that evaluates any function $f$ built by the above process on $\mathbb{N}$, simply as $f \cdot init$.


Hardness of approximating hitting set Consider the hitting set problem with $n$ elements and $m$ sets. I gather from the linked page as well as this that

1) it is NP-hard to approximate the cost of the optimal solution to a multiplicative factor of $c \log n$ for some $c>0$.

2) it is NP-hard to approximate the cost of the optimal solution to a multiplicative factor of $c \log m$ for some $c>0$.

3) it is NP-hard to approximate the cost of the optimal solution to a multiplicative factor of $c \log \max(n,m)$ for some $c>0$.

Is my understanding correct? This seems to be a straightforward consequence of what is on the internet, but some of the notation in these sources is mysterious to me and I want to make sure I'm not misunderstanding.

For every choice of $\alpha > 0$, Moshkovitz shows that approximating set cover on instances with $n^{C_\alpha}$, where $C_\alpha$ is some constant depending only on $\alpha$, better than $(1-\alpha) \log n$ is NP-hard. Since $\log m \leq C_\alpha \log n$, it is NP-hard to approximate set cover better than $\frac{1-\alpha}{C_\alpha} \log m$. I'm not sure what is $\sup_{\alpha\to 1} \frac{1-\alpha}{C_\alpha}$, but it can probably be gleaned from the paper. At any rate, all three results you mention are correct, and the first can be strengthened by replacing $c$ with $1-\alpha$ for any $\alpha > 0$.


Is the problem of deciding whether two programs have the same semantics decidable? If I have program and I want to check whether other programs have the exact same semantics or not, could I always build a machine that could make that decision?

This is a question relevant to information security as metamorphic malware will perform transformations on its own code which will make it look different to static malware detectors while preserving its semantics. If it is possible to write a machine that can detect whether two programs carry the same semantics, then it is impossible to write "undetectable" malware.

Concretely, we are always dealing with syntactical transformations, regardless whether there is a semantic theory that renders these transformations intelligible to us, or not. In the end, our ability to automatically demonstrate that two different programs are equivalent is restricted to properties that can be defined syntactically. Even then, there are limits to what we can do, if we allow the language in which these properties are defined to be rich enough, so the answer to your question, in the general case, would have to be negative.

More specifically though, behind every specific metamorphic process that can be automated there is also a specific strategy, so there are also limits to the efficacy of those malware pieces. Because of that, it may be possible, given some knowledge of this strategy, to target its syntactical features in a controlled way, and automatically crack the code behind it, preventing it from attacking.

Malware creators have the initiative though, which gives them an advantage. This advantage can be amplified with technical skill and mathematical sophistication, so it's not advisable to base your security strategy on the ability to detect and deactivate a piece of software that already entered your system.


Binary 2s Compliment Applied Twice Gives Original - How? At the moment the maths behind binary 2s compliment seems like voodoo to me.

If I take 0011 (+3) and "flip and add 1", I get 1101 (-3)

If I apply the same process to 1101, ("flip and add 1"), I get back to the original positive value.

How is this so?

First, if we wouldn't get the same number after negating it twice, it wouldn't make much sense, right?

So we just need to prove that the "complement and add 1" has indeed the effect of negation, i.e., taking $x$ into $-x$  (and thus, $-x$ to $x$). (well, maybe except for an edge case I will mention below.)

A signed number of $n$ bits, $b_{n-1}, \ldots, b_1,b_0$ where each $b_i\in\{0,1\}$,  is to be interpreted in the following way: the $i$-th bit amount $2^i$ except for the last bit (MSB). The MSB $b_{n-1}$ is what makes the number negative, and can be seen as having the value $-2^{n-1}$.

  Sanity check.
  4 bits. The number 5 is 0101 = 2^2+ 2^0 = 4+1.
  The number -5 is 1011 = -2^{3}+ 2^1+2^0 = -8+2+1 = -5.

With this in mind, given $x = -2^{n-1}b_{n-1} + \sum_{i=0}^{n-2}2^ib_i$ if we complement each bit ($b_i \to (1-b_i)$) we will get
$$\begin{align}NOT(x) &= -2^{n-1}(1-b_{n-1}) + \sum_{i=0}^{n-2}2^i(1-b_i) \\
& = -2^{n-1} + \sum_{i=0}^{n-2}2^i - [-2^{n-1}b_{n-1} + \sum_{i=0}^{n-2}2^ib_i] \\
&= -1 -x
\end{align}$$
therefore, $NOT(x)+1$ equals $-x$.

Note the edge case(s).If $x=0$ then negating it should give 0. Yet complementing each bit gives $111111 \ne 0$ and after +1 we will get back 0  (ignoring the carry).
The other edge case is the maximal negative number $1000$ for 4-bit numbers.
If we negate it we get $0111$ after complementing and $1000$ after adding 1 to the complemented number. In this case (and this case only) the 2-complement system "doesn't work" and gives that the negation of $x$ is $x$.


Rigorous proof against pseudorandom generator I am trying to teach myself the principles of cryptograhpy, and want to solve the following question:

Let G be the algorithm that takes an input x = (x1, . . . , xn) from
{0, 1} n (so each xi ∈ {0, 1}) and outputs the string G(x1, . . . ,
xn) = (x1, . . . , xn, x1 ⊕ x2) in {0, 1} n+1. Rigorously prove that G
is not a pseudorandom generator.

So, we would want to prove that either expansion doesn't hold (for all n, l(n) > n), which, in this case, would mean that for each x, the corresponding G > x, or pseudorandomness doesn't hold ( For efficient algorithm D, there is a negligible function 'n' such that:

Pr[D(r) = 1]-Pr[D(G(s)) = 1] $\leq$ $\epsilon$(n),
where 'r' is uniform on {0,1}$^{l(n)}$ and 's' is uniform on {0,1}$^n$

), which, in this case, means that we need to prove that there does not exist a function n such that the difference of the probabilities of the function D(r) and D(G(s)) is very small.
Now, I understand these concepts, but I am  having trouble approaching this problem practically... what would be the best way to start?

Your definition of pseudorandomness is misleading. A better definition would start with a function with "expansion", and then state then it is indistinguishable from random. In your case, the function is "expanding" since it takes $n$ bits and outputs $n+1$ bits. However, the $n+1$ bits it produces don't look random. Can you tell why?


For each vertex of a tree count vertices closer than a specified value We have a weighted tree of $n\leq 10^5$ nodes, and for every node $v$, value $L(v)$. The goal is to calculate, for every vertex $v$, number of vertices $u$ such that $\mathrm{dist}(v,u)\leq L(v)$. This is a task from a programming contest. Judging by the limit on $n$, and also specifics of time limits on this contest, the desired complexity should be close to linear, i.e. $O(n \log n)$.

If the tree was rooted, and we were asked to count vertices $u$ that are also in a subtree of $v$, then the task could be solved by in-order traversal and a segment tree. However, this doesn't seem to help with this more general problem.

As it is a contest problem, I will give you some tips which may be a good start point.

Consider an easier problem: the graph has a vertex $v$ and multiple paths going out of it (they are straight). Of course, the result for vertex $v$ is easy to compute (one DFS). Now try to use the binary search to find the result for remaining vertices (tip: make a sorted list of distances from $v$ to all the other vertices in whole graph and in each separate branch).
Now the real problem. Choose any vertex $v$. We can compute the result for it using usual DFS. What if we remove this vertex? Let's say we computed recursively the result in each of the generated subtrees. Then for each vertex $w$ other than $v$ we need to add the number of vertices $s$ outside the $v$-subtree containing $w$ (formally, vertices $s$ such that $d(s,w)\le L(w)$ and $s\to w$ path contains vertex $v$). Try to do it in total $O(n \log n)$ time using the experience from point (1.).
Can you choose such vertex $v$ in the graph such that the size of the subtrees after removing $v$ doesn't exceed half of the initial size? Assuming you can, prove that the total running time is $O(n \log^2 n)$.


NP-Completeness and commutative property If $X$ is NP-complete and for some $Y, X\leq_p Y$ and $Y\leq_p X$ what can we say about $Y$?

My intuition says that this is only the case when $X=Y$ but I'm not sure how to justify this.

Your property holds for, for example 3-SAT and 3-COLOURABILITY so it's certainly not required that $X=Y$.

The fact that $Y\leq_p X$ and $X\in\mathrm{NP}$ tells you that $Y\in\mathrm{NP}$; the fact that $X$ is $\mathrm{NP}$-complete and $X\leq_p Y$ tells you that $Y$ is $\mathrm{NP}$-hard.  Therefore, $Y$ is $\mathrm{NP}$-complete.


Context-sensitive grammars for $a^ib^jc^{ij}$ and $a^ib^jc^{i^j}$ I would like to get some help for finding the context-sensitive grammar for the language:

$$L_1=\{a^ib^jc^{ij} \mid i,j\geq 0\}.$$

To answer the question before it's written here, yes I've tried to construct it myself, but my attempts are far from promising, so I don't include them, because there is no point (also I've tried to find a similar question - without luck).

Additionally, although I'm familiar with the one question per post rule, I'm adding another language here:

$$L_2=\{a^ib^jc^{i^j} \mid i,j\geq 0\}.$$

(The reason is that I think these two have a similar solution — of course if I'm mistaken, I will erase it.)

Please include the thought process as I've just started learning grammars. Any hint appreciated.

Designing context-sensitive grammars (with productions $\alpha X \gamma \to \alpha \beta \gamma$ with $\beta \neq \varepsilon$) is no fun at all. It is slightly more convenient to construct monotone grammars (with productions $\alpha \to \beta$ with $|\alpha| \le |\beta|$). There is a standard construction from one to the other.

But even then it is full of tiny details that have to be observed.

It is relatively easy to construct a grammar for $\{ La^ib^jc^{ij} \mid i,j\ge 0 \}$.
First generate strings of the form $LB^jA^i$, just like in a context-free grammar. Add the rule $BA \to ABC$, so that if every $A$ moves over every $B$ we generate $ij$ $C$'s. But now we have $C$'s in between. Let $B$'s move over $C$'s whenever needed.

Then we have to rewrite $A,B,C$ into $a,b,c$ respectively provided they are in the right order. This can be done using the boundary symbol $L$ and the productions $LA \to La$, $aA \to aa$, $aB\to ab$ etcetera. Like a finite state automaton that accepts $a^*b^*c^*$.

Now what about the $L$? We used it to mark the start of the string. According to the rules of monotone grammars it cannot be deleted. Well, let the $L$ double as one of the $a$'s. But then we should carefully match the $c$;s with the new design. Thus start by generating the context-free language  $aB^jA^iC^j$.

Done? not yet. We now always have at least one $a$, i.e., $i>0$.   Add these special cases.

Problem with the construction is its correctness. Productions can be applied in any order, not only the one order you have considered during its construction.


Student Course Allocation Problem with Many Constraints Problem statement

In an university, there are $t$ course categories, $m$ courses, $n$ sections, $p$ students.

$i$-th section has:

A student capacity: $cap_i$.
Two lecture timings. (Formally, each section has two elements from $S$ associated with itself, where $S$ contains all lecture timings.)
A parent course $course_i$. ($m \leq n$)

$i$-th course has:

Some lecture section(s) under it. (As mentioned above.)
A parent course category $category_i$. ($t \leq m$)

Each student has ordered all $n$ sections from $1$ to $n$ on the basis of his/her preference.

Now, each student $i$ has to be allocated $q_i$ ($2 \geq q_i \geq 1$) sections such that:

No student has been allocated more than two or more section that have the same element(s) from $S$ associated with themselves. Formally, if the sets of lecture timings of allocated sections for a student $i$ are $T_1$, $T_2$, $\cdots$, $T_{q_i}$, then allocation should ensure that $|T_1 \cup T_2 \cup \cdots \cup T_{q_i}| = 2{q_i}$.
No student has been allocated two or more sections which have the same parent course.
No student has been allocated more than $u$ sections which have a parent course which have the same course category. ($u \geq 1$) Formally, let $X$ be a list of $category_{course_{j}}$ where $j$ is any section allocated to a student. The frequency of any element in $X$ should not exceed $u$.
No section $j$ is allocated to more than $cap_j$ students.
$\sum_{j=1}^p cost(j)$ is minimized. $cost(x)$ is defined as the sum of positions of the $x$th student's allocated sections in his/her preference list. For example, a student had ordered the courses P, Q, R, S in the order: R, Q, S, P. If he/she was allocated Q and S, cost() function will return 5. (2+3)

Constraints:

$1 \leq t \leq 7$
$3 \leq m \leq 9$
$5 \leq n \leq 30$
$250 \leq p \leq 700$
$\sum_{i=1}^p q_i \leq \sum_{i=1}^n cap_i$

My take

I tried to represent the problem in the form of a k-partite graph. Doing so would have helped implement network flow algorithms like minimum-cost, maximum-flow. However, I have not been able to come up with any representation that satisfies all of the given constraints.

Timetabling is known to be NP-complete. Your more complex variant is too. Don't expect "nice" or "efficient" solutions. Either settle for an approximate solution (good luck in deriving one) or some sort of randomized heuristic.

I'd try some variant of genetic algorithms (look around for it's application to time tabling, they use special mutation and crossover operations that at least try to respect restrictions).


Finding maximum and minimum of consecutive XOR values Given an integer array (maximum size 50000), I have to find the minimum and maximum $X$ such that $X = a_p \oplus a_{p+1} \oplus \dots \oplus a_q$ for some $p$, $q$ with $p \leq q$.

I have tried this process: $\text{sum}_i = a_0 \oplus a_1 \oplus  \dots \oplus a_i$ for all $i$. I pre-calculated it in $O(n)$ and then the value of $X$ for some $p$, $q$ such that $(p\leq q)$ is: $X = \text{sum}_q \oplus \text{sum}_{p-1}$. Thus:

$$
\mathrm{MinAns} = \min_{(p,q) \text{ s.t. } p\le q}{\text{sum}_q \oplus \text{sum}_{p-1}} \\
\mathrm{MaxAns} = \max_{(p,q) \text{ s.t. } p\le q}{\text{sum}_q \oplus \text{sum}_{p-1}} \\
$$

But this process is of $O(n^2)$. How can I do that more efficiently?

If $k$ is the bitsize of the integers, then you can compute the Max in $O(n k)$ time.

Basically, the problem is, given $n$, $k$-bit integers $S_i$, find $i,j$ such that $S_i \oplus S_j$ is maximum.

You treat each $S_i$ as a binary string (looking at the binary representation), and create a trie out of those strings. This takes $O(nk)$ time.

Now for each $S_j$, you trying walking the complement of $S_j$ in the trie you created (taking the best branch at each step basically), finding a $j'$ such that $S_j \oplus S_{j'}$ is maximum.

Do this for each $j$, and you find the answer in $O(n k)$ time.

Since your integers are bounded, this algorithm for max is basically linear, and so is the algorithm for min got by sorting (as sorting can be done in linear time).

Incidentally, if there were no bounds, then you can reduce element distinctness to the min version.


How to show that a language {w|ww^R in A} is regular, A being regular? Been working on my homework and I've been stuck on a question for over a week now. Not really asking for a solution but if someone could point me towards the right direction that would be great, as I have literally no idea of how to go about this. A previous question asked us to show that for any DFA that accepts A, we can create a NFA that accepts {wR | w in A}, which was pretty easy (just reverse the DFA).

This question asks: Show that if A is a regular language, then so is {w|wwR in A}, where wR is the reverse of the string w.

I know that if I have two regular expressions, then their concatenation is also a regular expression, that's simple. But this asks me to show that the first-half of some of the strings in A is a regular expression. No idea how to show that this is true. It's not even intuitive to me that this is true, except that the question implies it is.

Anyone got any idea of where to start about this? Thanks!

You might want to study If $L$ is a regular language then so is $\sqrt L=\{w\mid ww∈L\}$.

The solution is to simulate the DFA in parallel with itself, from both sides of the string. For each letter one step forward (for $w$) and one step backward (for $w^R$). If the forward state reading $w$ reaches the same state as the backward simulation, both parts joined form a computation on $ww^R$.


Running time of an algorithm containing binary elements for cryptography Hey guys sorry I'm new to cs and I'm trying to find the running time of algorithms... could you tell me about the algo given how much time is needed in terms of complexity?  The actual algo I created is the same as below but the sum must be more or equal to 2^(n-2).Thank you]1

We take only one step for computing each $2^ix_i$ (By using left-shift operation we can compute $2^i$ in constant time). So the complexity of Algorithm $\mathcal{A}$ is $\mathcal{O}(n)$.

I suspect you used loop for computing $2^i$, and this incurred your bad result.

PS : sorry for my bad english


Is there a *simple* proof that the intersection of a CFL and a regular language is a CFL? I am following a course on complexity theory where languages are a part of the course. There is a proof that no matter how hard I try to understand, it is till so complex that I cannot make it to half of the proof. Namely, the proof of the statement that the intersection of a CFL and a regular language is again CFL.

The proof that is provided to us is 2-3 pages of pure text and notations. The ones online are also heavily dependent on much notations and unfortunately, Sipser does not handle it in his book Introduction to the theory of computation. I'm wondering if there's a straight-forward and less-dependent-on-notation proof that someone knows that will contribute to understanding the proof or even reproducing it. Because at this moment, I don't even understand the proof.

I don't know of a simple proof, but there is a proof where the underlying idea is simple to understand.

Suppose you have a PDA $N$ (deterministic or nondeterministic; doesn't matter) which accepts the language $L_M$, and whose set of states is $S$. And further suppose you have a DFA $M$ with $T$ as its set of states which accepts the language $L_M$.

Conceptually, you can construct a new PDA, whose set of states is the Cartesian product $S \times T$, and awhich "runs" both the PDA and the DFA in parallel. A transition from state $(s_i,t_j)$ to state $(s_p,t_q)$ does whatever the PDA does when transitioning from state $s_i$ to $s_p$, but also takes the appropriate transition from $t_j$ to $t_q$.

An accept state in this new PDA is any state which corresponds to an accept state in both $M$ and $N$. Then this PDA should, assuming we get the details right, accept the language $L_M \cap L_N$.

There are a lot of details that you need to get right, which makes the proof fairly technical. So it's not a short proof. But it's simple to understand the idea behind it.

If you want to understand how this works, I would suggest trying to write a reasonably formal proof that the intersection of two regular languages is regular using a similar construction.

And as an additional exercise: Why can't you use this technique to prove that the intersection of two context-free languages is context-free?


Asymptotics of $\frac{1}{\log(\frac{2^n}{2^n-1})}$ I am trying to understand the asymptotics of

\begin{equation}
f(n) = \frac{1}{\log(\frac{2^n}{2^n-1})}
\end{equation}
In particular, is there some $c \geq 1$ such that $f(n) = O(n^c)$?

From this post, you can approximate $\log(1+x)$ with $x$ for little values of $x$. Hence,

$$
f(n) \sim \frac{1}{\frac{1}{2^n-1}} = 2^n-1
$$

Therefore, you can't find any constant $c$, such that $f(n) = O(n^c)$, as it is $\Theta(2^n)$.


Is uniform cost search optimal? In my AI lecture notes (also many other AI lectures) it's written that uniform cost search is optimal (that is, uniform search always outputs the optimal path), but what if the cost is negative, won't the search algorithm possibly trapped in infinite loops? If solution is using a closed set to track explored nodes, we will lose ability of reopening a node when less cost is seen, thus optimal might compromise.

In my AI lecture notes (also many other AI lectures) it's written that uniform cost search is optimal (that is, uniform search always outputs the optimal path)

Kinda.  While it's true that the algorithm should output the optimal path, that's probably not what your notes were referring to.  Rather, it's likely that they were making a claim about the algorithm itself being optimal in terms of performance.
A blog post, "Artificial Intelligence - Uniform Cost Search (UCS)", provides a claim like this:

Uniform Cost Search is the best algorithm for a search problem, which does not involve the use of heuristics. It can solve any general graph for optimal cost. Uniform Cost Search as it sounds searches in branches which are more or less the same in cost.

The logic behind this claim seems simple enough: you don't want to search down paths that can't be optimal, since that'd be wasteful, but you don't have any way of knowing which paths might be optimal in advance.  So, by going down each equally, you don't assume any effective bias.
I'm not 100% if this is true in all cases in which this claim's made, but it seems like a useful tidbit to be aware of.

but what if the cost is negative, won't the search algorithm possibly trapped in infinite loops?

There can't be negative costs.  If there are negative nodes, you'd have to modify the algorithm by removing its termination condition, effectively reducing it to a brute force search.
For example, consider using UCS and finding an apparently optimal path without having searched the entire space.  Then, it turns out that there's a node that you didn't search that has a cost of $-{\infty}$.  Presumably an optimal path should've gone through that node, but the search couldn't have found it since it terminated too soon.
Disclaimer about method names
Basic, widely known methods like this often have some variation in exactly how different sources define them or what name the method is given.  For example, below I linked the relevant Wikipedia article, which calls it "Dijkstra's algorithm".  The Wikipedia article discusses several different implementations.
Claims about algorithms with fuzzy definitions and frequently confused names should be taken with a grain of salt as there's plenty of room for miscommunication.
Further reading
Wikipedia's article on Dijkstra's algorithm would likely be helpful:

In some fields, artificial intelligence in particular, Dijkstra's algorithm or a variant of it is known as uniform-cost search and formulated as an instance of the more general idea of best-first search.


DFA for the language L = { $ \omega = xy \in (a,b)^*\mid |x|_a = |y|_b $ } I need to find a DFA for this language:
 L = { $ \omega = xy \in (a,b)^*\mid |x|_a = |y|_b $ }

Let $w=w_1\dots w_n$ be any word in $\{a,b\}^*$. For $i=0,\dots,n$ consider the values $d_i(w):=|w_1\dots w_i|_a - |w_{i+1}\dots w_n|_b$. We can prove

$d_0(w) = - |w|_b \le 0$,
$d_n(w) = |w|_a \ge 0$,
$d_{i+1}(w) = d_i(w) + 1$ for $i=0,\dots,n-1$.

This implies that there must be some $i$ with $d_i(w) = 0$, and therefore $w\in L$. So $L=\{a,b\}^*$.


How to calculate Big O of $T(n) = aT(n^b) + f(n)$? I'm a student studying Big O. I know that we can solve $T(n) = aT(\frac{n}{b}) + f(n)$ by compering $n^{\log_b{a}}$ to $f(n)$ or

  $O(n^{\log_b{a}} + f(n))$

Today I was faced with $T(n) = T(\sqrt n) + 1$ and I think it is $O(\log\log n)$. and I was faced with this too, $T(n) = T(\sqrt n) + O(\log\log n)$ that I think it is $O(\log^2\log n)$.

I'm wondering what is the formula (or method) to solve any kind of this type of problems (my guess is $O(f(n)a^n\log\log n)$). so:

  How to calculate Big O of $T(n) = aT(n^b) + f(n)$ with $0<b<1$?

Thanks in advance.

How to calculate Big O of $T(n) = aT(n^b) + f(n)$ with $0<b<1$?

The powerful technique you are searching for is variable substitution.

Let $S(m)=T(2^m)$. Then
$$S(m)=T(2^m)=aT(2^{mb}) + f(2^m)=aS(mb)+g(m),$$
where $g(m)=f(2^m)$.

Now that we have a recurrence relation about $S(m)$, to which we might be able to apply the master's theorem. Here are some examples.

If $f(n)$ is a constant, so is $g(m)$.  If $a=1$ and $b=\frac12$, then we know that $S(m)=O(\log m)$. Hence,
$$T(n)=S(\log n)=O(\log \log n).$$
If $f(n)=\log n$, $a=1$ and $b=\frac23$, then $S(m)=S(2m/3)+m$. So $S(m)=O(m)$. Hence,
$$T(n)=S(\log n)=O(\log n).$$
If $f(n)=\log\log n$, $a=1$ and $b=\frac12$, then $S(m)=S(m/2)+\log m$. So $S(m)=O((\log m)^2)$. Hence,
$$T(n)=S(\log n)= O((\log\log n)^2).$$

Note that the above reasoning is rather loose as $\log n$ and $\sqrt n$ might not be an integer when $n$ is. A lot of careful sandwiching together with some kind of continuity or monotonicity is needed to establish the result rigorously.


Greedy sequential/parallel task scheduling We have N tasks that need to be scheduled for processing. Each task consists of two parts that need to executed in order. The first one is guarded by a mutex and therefore only one task can be executing this part at a time. The second part has no such constraint and any number of the tasks can be executing this at the same time. For task i we know how much time it needs to spend in each part, namely mi for the guarded part, and ai for the part that can be executed in parallel.
The problem is to find a permutation of the tasks such that the time needed to execute all of them is minimized.
My intuition says that this can be solved with a greedy algorithm, by scheduling the tasks in descending ai order.
For example given the tasks with:
m1 = 3, a1 = 9
m2 = 2, a2 = 7
m3 = 6, a3 = 10
The optimal solution is the permutation 3, 1, 2.
However, I have trouble proving that the greedy solution is optimal. Any ideas on how to do that?

I have a pretty messy proof. I'm sure this can be cleaned up with a bit of work. Let me know if you need me to simplify the proof.
For the sake of the proof, lets rearrange all the terms such that
$a_1 \geq a_2 \geq a_3 \ldots$. Let $f(1), f(2), \ldots, f(N)$ be some schedule. The total time spent for any schedule $f$ is given by the following.
$$T(f) = \max \{m_{f(1)} + a_{f(1)}, m_{f(1)} + m_{f(2)} + a_{f(2)},\ldots, \sum_{i = 1}^N m_{f(i)} + a_{f(N)} \}$$.
For the sake of contradiction, suppose that your greedy method is not the optimal solution. There exists some schedule $\phi$ such that $T(Id) > T(\phi)$ (here $Id$ is the identity). Choose $k$ such that $\sum_{i = 1}^k m_{i} + a_k = T(Id)$. Let $h$ be the smallest number such that $\{1,\ldots, k\} \subset \{\phi(1), \ldots, \phi(h)\}$. Note that $\phi(h) \leq k$.
Because $\{1,\ldots, k\} \subset \{\phi(1), \ldots, \phi(h)\}$, $\sum_{i = 1}^h m_{\phi(i)} \geq \sum_{i = 1}^k m_i$. Because $a_1 \geq a_2 \geq \ldots$, we know that $a_{\phi(h)} \geq a_k$. This means that
$$\sum_{i = 1}^k m_i + a_k \leq\sum_{i = 1}^h m_{\phi(i)} + a_{\phi(h)}$$
But $T(Id) = \sum_{i = 1}^k m_i + a_k \leq \sum_{i = 1}^h m_{\phi(i)} + a_{\phi(h)} \leq  T(\phi)$. This is a contradiction.


can every LR(k) grammer be transformed to LR(1) when i was studying compilers i came across this in Wikipedia every DCFL has a corresponding unambiguous grammar and hence can be parsed by an LR(1) parser which is the most powerful parser then what is the significance of LR(k) parsers are they more powerful than LR(1) when every DCFL can be parsed by LR(1) why do we need LR(k)?

Remember that the point of parsing (in almost all practical applications) is not simply to recognize whether or not a sentence is in a language, but rather to find the parse tree corresponding to the sentence in order to do further processing (such as compilation). Or, to put it another way, few people would purchase a "compiler" which took some input and whose output was limited to one of two sentences:

That input is a syntactically valid C program
That input is not a syntactically valid C program.

By a large, the desired product is an executable, not just an assurance that the program could be compiled if you had a compiler.

So, it is true that if there is an LR(k) grammar for a language, then there is also an LR(1) grammar. But it is not the same grammar (unless k is 1) and it will therefore not produce the same parse tree.

It is possible to mechanically transform the LR(k) grammar into an LR(1) grammar in a way that the original parse tree can be recovered, but it is not a procedure you want to try by hand. (Trust me on this.)

So if you have an LR(k) grammar and you want to build a parser, you could:

Find an LR(k) parser generator
Find a program which mechanically tranforms an LR(k) grammar into the corresponding LR(1) grammar and the code necessary to transform a parse tree produced by the LR(1) grammar into the corresponding parse tree which would have been produced by an LR(k) parse. Then feed the LR(1) grammar into an LR(1) parser generator and add the parse tree recovery code to the semantic actions.

These two tasks are not particularly different. The mechanical transformation of an LR(k) grammar into an LR(1) grammar blows up the size of the grammar much in the way that the LR(k) parse tables are much larger than the LR(1) parse tables. From a practical viewpoint, it is roughly equally difficult to find an LR(k) parser generator as it is to find an automatic LR(k)→LR(1) transformer.


Reduction problem to another problem I would like to show that a problem $A$ is $NP\text{-complete}$. So, I am trying to reduce 3-SAT problem to $A$. Reduction is kind of function, let say $f$. What is necessary complexity of $f$? Probably, it has be in $NP$. But, does it mean that $f$ must be a non-deterministic Turing machine working in polynomial time?

No, $f$ need not be a NDTM.  To prove a problem is NP-complete by reducing another NP-complete problem to it requires only a Karp reduction, which is a polynomial-time deterministic reduction.  So $f$ would live in the complexity class FP.


Confused about proof that $\log(n!) = \Theta(n \log n)$ So I was able to show that:

$\log(n!) = O(n\log n)$ without any problems.

My question is when trying to prove that $\log (n!) = \Omega(n\log n)$.

I was able to show that:
$$\begin{align*}
\log n! &= \log(1 \cdot 2 \cdot 3 \cdots n  )\\
&= \log 1 + \log2 + \log3 + \dots + \log n \\
&= \log 1  + \dots + \log\tfrac{n}{2} + \dots + \log n\\
&\geq \log\tfrac{n}{2} + \log\big(\tfrac{n}{2} + 1\big) + \dots + \log n &&\text{(i.e., the larger half of the sum)}\\
&\geq \log\big(\tfrac{n}{2}\big) + \log\big(\tfrac{n}{2}\big) + \dots + \log\big(\tfrac{n}{2}\big)&&\text{(adding $\tfrac{n}2$ times)}  \\
&= \log\big(\tfrac{n}{2} \cdot \tfrac{n}{2} \cdots \tfrac{n}{2}) &&\text{($\tfrac{n}{2}$ times)}  \\
&= \log\Big(\tfrac{n}{2}^{\tfrac{n}{2}}\Big)\\
&= \tfrac{n}{2} log\big(\tfrac{n}{2}\big) &&\text{(by log exponent rule)}
\end{align*}$$

Thus, $\log(n!) \geq \tfrac{n}{2}\log\big(\tfrac{n}{2}\big)$, so we conclude that $\log(n!) = \Omega(n\log n)$.

I don't understand how finding the lower bound of $\log(n!)$ is found by getting the larger half of the sum. Why is that chosen to find $\Omega(n\log  n)$? I feel like it's probably something obvious but it's the only thing keeping me from fully grasping the proof. If someone can enlighten me, I would appreciate it!

Consider the sum $S = \log(1) + \dots + \log(n)$.  We're going to break it into two parts: $S=T+U$, where

\begin{align*}
T &= \log(1) + \log(2) + \dots + \log(n/2)\\
U &= \log(n/2+1) + \dots + \log(n-1) + \log(n).
\end{align*}

Basically, $T$ has the first $n/2$ terms of $S$, and $U$ has the remaining $n/2$ terms.

Now we'll lower-bound each of them.  Start with $T$.  Each term in $T$ is at least $\log(1)$, so we get

$$T \ge \log(1) + \log(1) + \dots + \log(1) = 0 + 0 + \dots 0,$$

so $T \ge 0$.  Next look at $U$.  Each term in $U$ is at least $\log(n/2)$, so we get

$$U \ge \log(n/2) + \log(n/2) + \dots + \log(n/2) = (n/2) \times \log(n/2).$$

Now $S = T+U$, so plugging in the lower bounds obtained above, it follows that

$$S =T+U\ge 0 + (n/2) \times \log(n/2).$$

This is exactly the result you wanted to prove.  Also, $(n/2) \times \log(n/2)$ is $\Omega(n \log n)$, so this proves that the sum $S$ is $\Omega(n \log n)$.