Pushdown Automata for words x#y where x and y are different words over {0,1} that share one similarity I was instructed to create a pushdown automaton described in the title. Basically, the pushdown automaton accepts strings of the form $x\#y$ where $x$ and $y$ are strings of 1s and 0s such that there must be at least one difference and at least one similarity between $x$ and $y$. Here is the meaning of one similarity. Let $x=x_1x_2\cdots x_m$ and $y=y_1y_2\cdots y_n$, where $x_1,x_2 \cdots, x_m, y_1,y_2, \cdots, y_n\in\{0,1\}$, then there exists an index $i$ such that $x_i=y_i$.

I understand that I must have two separate cases, with one case assuming that $|x| = |y|$ and one case where $|x| \not= |y|$. Right now I am only working on the case where $|x| = |y|$. So far, I am using nondeterminism to find the $i$-th value of $x$, matching it against the $i$-th value of $y$. However, this only determines if there is at least one difference between $x$ and $y$. I am failing to see a solution where I can also determine that there is at least one similarity. If anybody can point me in the right direction, it would be much appreciated.

Here is the critical observation.  We can combine the two conditions, there must be at least one difference and there must be at least one similarity between $x$ and $y$ into the following one condition.

Let $x=x_1x_2\cdots x_m$ and $y=y_1y_2\cdots y_n$, where $x_1, x_2,\cdots, x_m,y_1, y_2,\cdots, y_n\in \Sigma$. Then $x\#y$ is a word in the language if and only if there exists an index $i$ such that

$x_i\not=y_i$ and $x_{i+1} =y_{i+1}$ or,
$x_i=y_i$ and we do not have $x_{i+1} =y_{i+1}$.

The precise meaning of "we do not have $x_{i+1} =y_{i+1}$" is either exactly one of $x_{i+1}$ and $y_{i+1}$ is defined or $x_{i+1}\not= y_{i+1}$.

The basic motivation of the idea above is that an PDA can only keep track of one unbounded counter. So we should compress two unbounded counters, the index of the similarity and the index of the difference into one unbounded counter.


How do I prove Berman's theorem? Berman's theorem states

  If a unary language ( a language with all the strings of the type $1^i$, $ i  > 0 $ ) is NP-Complete then P = NP.

I tried reducing SAT to a given unary language $L$ assuming it is NP-Complete. But I can't think of a way  such that after applying the reduction so that SAT gets solved in polynomial time. How do I proceed further?

This is an exercise from Sanjeev Arora and Boaz Barak , but not homework.

Please refer this solution. Or see the paper by S. R. Mahaney, Sparse complete sets for NP: Solution of a conjecture by Berman and Hartmanis (Journal of Computer and System Sciences, 25:130-143, 1982).


Partitioning any language to regular? One time I saw a theorem that says something like any language can be partitioned into regular languages, but I can't remember exactly what the theorem is.
Could somebody tell me, is this true? What is this theorem?

Every language can be partitioned into a countable union of singleton languages (languages of the form $\{w\}$). Since singleton languages are regular, we get that every language can be partitioned into infinitely many regular languages.


Determine the smallest $3$ numbers in a set using comparisons Given  a set of $n$ distinct numbers, we would like to determine the smallest $3$ numbers in this set using comparisons. The elements can be determined using $n+O(\log n)$ comparisons.

This was the answer given in a multiple choice question. Now, we can easily do this using $3n\in O(n)$ comparisons. However I have been thinking about it and I can't do it in $n+O(\log n)$ comparisons.

They might be thinking about making a heap and using heapify which takes $O(n)$ time. However in heapify, the comparisons are $O(n)$ but not like $n+O\log(n)$ because every step in the heapify needs finding the minimum among $3$ numbers which takes $3$ comparisons so making a heap and finding the three minimums should be $3n$ comparisons.

So, can anyone tell me how to find three minimums in $n+O(\log n)$ comparisons or am I messing up somewhere in the heapify logic?

I can show you how to get the two smallest elements in $n + O(
\log n)$ comparisons, the extension to the three smallest elements should not be difficult.

Build the following tree. Start with your array, then for each pair of neighboring elements (non-overlapping), promote the smaller one level up. Do the same for the new level, until the tree has a root.

This tree is built using less than $n$ comparisons ($n / 2 + n / 4 + \dots$). The smallest element is obviously the root. The second smallest element must be one of of the siblings of all the nodes that are equal to the root along the path down the tree to the array level. There are at most $\log n$ such nodes.

You should also convince yourself of the bound when the number of nodes on a level is not even.


How to prove a reduction I'm just a little confused about the wordings for reductions and would appreciate some help as I am very new to reductions.

I have a question where I have two sets, A and B, and I have to provide a reduction A $\leq_p$ B and then I have to prove that the reduction is correct.

What does this mean exactly?

For the reduction portion do I have to:

Provide some sort of explanation of B in terms of A?
Provide some sort of explanation of A in terms of B?
Both 1 & 2?

And then I'm assuming to prove the reduction is correct, I need to show A $\implies$ B as well as B $\implies$ A?

(The exact question has A as the set of un-directed graphs with a Hamiltonian path and B is the set of un-directed graphs with a Hamiltonian cycle)

Any clarification would be greatly appreciated!!

Thanks.

Follow the definition of $\leq_p$.

You have to find a function $f$ (define it!), computable in polynomial time (prove this!) such that

$$
\begin{array}{l}
\forall x.\  x\in A \implies f(x)\in B
\\
\forall x.\ x\notin A \implies f(x)\notin B
\end{array}
$$
(two more proofs!)

More intuitively, $f$ converts instances of $A$ (i.e. $x$) into instances for $B$ ($f(x)$), and must map $A$ inside $B$, and the complement of $A$ inside the complement of $B$. Very, very roughly, it describes how to solve $A$ exploiting $B$.

Finally, never write nonsense formulas like $A \implies B$ since sets do not imply other sets. Try to be as formal as you can, at least when you have not yet mastered the definition.


Is there a variant of Dijkstra’s algorithm for partial recalculation? Suppose the following:

We use Dijkstra’s algorithm to find the shortest route to our destination.
The start node (current vehicle position) keeps changing, i.e. moving towards the destination along the calculated shortest path. For this reason we use the inverted form, where the cost of a node represents the cost to reach the destination from there, and the destination’s cost is 0—that way the route graph does not need to change as the vehicle moves through it.
The cost of edges may change while the vehicle is moving towards the destination (e.g. the traffic situation may affect transit times).
We want to update the route graph based on edge costs without rebuilding it completely. Rather, as a set of changes arrives, we want to determine which nodes are affected by it and set their cost.
For now, we are neglecting the fact that the cost of an edge may change again before we reach it—the route is always based on current edge costs.

Is there a standard algorithm for this kind of partial recalculation?

Yes. A search algorithm that is able to quickly recompute the fastest path when small changes are made is known as an incremental algorithm.  For your case specifically, you'll want to use D*-Lite, the algorithm used by the Mars Rovers.

See here for more information.

(Note: D*-Lite is decently complex.  If this is for a video game, there are better ways to obtain speed-ups using off-the-shelf A* implementations)


Does two languages being in P imply reduction to each other? Given two languages $L_1$ and $L_2$ that are in $\mathsf{P}$, can it be proven that there is a polynomial time reduction from $L_1$ to $L_2$ and vice versa? If so, how?

I noticed that if $L_1$ is the empty language, and $L_2$ is the "full language" $\{ 0,1 \}^*$, there does not seem to be a reduction from $L_2$ to $L_1$, but this is not clear to me. I know how a reduction works, so that is not a problem for me.

No, in general
As you've already noticed, if $L_2$ is either the full language or the empty language, there can be no reduction from $L_1$ to $L_2$ - the argument is simple enough.
Recall the definition. $L_1$ reduces to $L_2$ iff there exists a function $f: \Sigma^* \rightarrow \Sigma^*$ such that $\forall w \in L_1, f(w) \in L_2$, and $\forall w \notin L_1, f(w) \notin L_2$, and $f$ is computable in polynomial time.
Suppose $L_1 \neq \emptyset$ and $L_2 = \emptyset$. Suppose also that some function $f$ exists such that $w \in L_1 \implies f(w) \in L_2$. This argument immediately gives us a contradiction. We know that $w \in L_1$ can be true, but $f(w) \in \emptyset$ can never be true, so there cannot be such an $f$, poly-time or not.
The argument for $L_1\neq\Sigma^{*}$ and $L_2 = \Sigma^{*}$ is similar. For any function $f: \Sigma^* \rightarrow \Sigma^*$, $w \in L_1$ can be false, but $f(w) \in \Sigma^{*}$ is always true.
There are some other subtleties floating around this question, and it's a worthwhile exercise to think of all the possible combinations you could get from assigning $L_1$ and $L_2$ to $\emptyset$, $\Sigma^{*}$ and some non-empty non-"full" language.
This said, with a further assumption, there's a small trick we can apply to make this argument hold:
Yes, if we have that neither $L_1$ nor $L_2$ are empty or "full"
Both $L_1$ and $L_2$ are in $P$, so we can decide them in polynomial time.
Let $w_\top \in L_2$ and $w_\bot \notin L_2$. These words are constant, so are of constant length.
We will define $f$ as follows. If $w \in L_1$, then $f(w)=w_\top$. If $w \notin L_1$, then $f(w)=w_\bot$. Clearly, $f$ represents a reduction from $L_1$ to $L_2$ according to the above definition. Since $L_1$ can be decided in polynomial time, we can compute $f$ in polynomial time.
So $f$ is a poly-time reduction from $L_1$ to $L_2$. This argument can work the other way to provide a reduction from $L_2$ to $L_1$, so the languages reduce to each other.
If exactly one of $L_1$ or $L_2$ is empty or "full", we can reduce from one to the other. Which way? Why?


Mapping several memories to one address space I am trying to understand deeply how memories work in computers, and I faced the next difficulty.

Let's say we have a device with two memory chips but only one address space (for example, 0x00000000 to 0x10000000 will be memory1 and 0x10000000 to 0x20000000 will be memory2). In case an assembly code does a load/store instruction to memory2 to the address 0x10000004, who's responsible it is to change the address so it will be absolute to the memory chip?
I assume that the memory chip doesn't know it's relative address space, and in our example memory2 expects a load/store from/to 0x00000004.

Each RAM chip (e.g., DIMM module) has its own range of physical addresses.  The memory controller connects the CPU to the RAM chips via a memory bus.

In its simplest form, each read or write operation sent on the memory bus contains some bits that select which RAM chip it applies to, and some bits that indicate the address to be selected within that RAM chip.  So, physical memory is partitioned among the RAM chips.  The memory controller is responsible for managing this partition and determining, based on the physical address, which RAM chip to select (what to write on the chip select bits of the memory bus).  The specific architectural details have evolved over time and may differ from platform to platform.

Physical addresses are normally not visible to user-level applications.  Instead, a virtual memory subsystem (page tables) are used to translate from virtual addresses to physical addresses.  The user-level application seems virtual addresses.  There need not be any simple way that ranges of virtual memory addresses correspond to RAM chips.


Algorithm Analysis: Expected Running Time of Recursive Function Based on a RNG I am somewhat confused with the running time analysis of a program here which has recursive calls which depend on a RNG.  (Randomly Generated Number)

Let's begin with the pseudo-code, and then I will go into what I have thought about so far related to this one.

    Func1(A, i, j)
    /* A is an array of at least j integers */

 1  if (i ≥ j) then return (0);
 2  n ← j − i + 1 ; /* n = number of elements from i to j */
 3  k ← Random(n);
 4  s ← 0; //Takes time of Arbitrary C

 5  for r ← i to j do
 6      A[r] ← A[r] − A[i] − A[j]; //Arbitrary C
 7      s ← s + A[r]; //Arbitrary C
 8  end

 9  s ← s + Func1(A, i, i+k-1); //Recursive Call 1
10  s ← s + Func1(A, i+k, j); //Recursive Call 2
11  return (s);

Okay, now let's get into the math I have tried so far.  I'll try not to be too pedantic here as it is just a rough, estimated analysis of expected run time.

First, let's consider the worst case.  Note that the K = Random(n) must be at least 1, and at most n.  Therefore, the worst case is the K = 1 is picked.  This causes the total running time to be equal to T(n) = cn + T(1) + T(n-1).  Which means that overall it takes somewhere around cn^2 time total (you can use Wolfram to solve recurrence relations if you are stuck or rusty on recurrence relations, although this one is a fairly simple one).

Now, here is where I get somewhat confused.  For the expected running time, we have to base our assumption off of the probability of the random number K.  Therefore, we have to sum all the possible running times for different values of k, plus their individual probability.  By lemma/hopefully intuitive logic: the probability of any one Randomly Generated k, with k between 1 to n, is equal 1/n.

Therefore, (in my opinion/analysis) the expected run time is:

ET(n) = cn + (1/n)*Summation(from k=1 to n-1) of (ET(k-1) + ET(n-k))

Let me explain a bit.  The cn is simply for the loop which runs i to j.  This is estimated by cn.  The summation represents all of the possible values for k.  The (1/n) multiplied by this summation is there because the probability of any one k is (1/n).  The terms inside the summation represent the running times of the recursive calls of Func1.  The first term on the left takes ET(k-1) because this recursive call is going to do a loop from i to k-1 (which is roughly ck), and then possibly call Func1 again.  The second is a representation of the second recursive call, which would loop from i+k to j, which is also represented by n-k.

Upon expansion of the summation, we see that the overall function ET(n)  is of the order n^2.  However, as a test case, plugging in k=(n/2) gives a total running time for Func 1 of roughly nlog(n).  This is why I am confused.  How can this be, if the estimated running time is of the order n^2?  Am I considering a "good" case by plugging in n/2 for k?  Or am I thinking about k in the wrong sense in some way?

How does the recursive formula for $E[T(n)]$ compare between this algorithm and randomized quicksort? They are very similar, which might lead one to believe that the running time of your algorithm is $\Theta(n \log n)$. In fact, the recursive formula for the run-time is so similar to the one for quicksort, that you could use that fact in itself as a proof. There are more elegant ways to prove it, but you can also prove it by induction.

$$ T(n) \leq bn + \frac{1}{n}\sum_{k = 1}^n T(k) + T(n-k)
$$

$$ = bn + \frac{2}{n}\sum_{k = 1}^{n-1} T(k).
$$

Suppose (induction hypothesis) that $T(i) \leq ci \ln i$ for $i \le n - 1$.

Then use the standard trick of bounding a sum by an integral:
$\sum_{i=1}^{n-1}f(i) \leq \int_1^n f(x) dx$.

The rest of the proof works like a standard proof by induction with just a little algebra.

Here's a nice source for this and other proofs of the running time of quicksort, and the techniques apply to this problem as well.

Notes on randomized quicksort analysis


Is $L=\{a^ib^jc^k : i\leq j\leq k\}$ context-free? I have an exam and in preparation I found this language. We are supposed to determine where in Chomsky hierarchy it stands. The language is $L=\{a^ib^jc^k : i\leq j\leq k\}$. I can easily build a linear turing machine, that would delete a, b and c for each a and then b and c for each b and if the only thing left, will be c, then the word belongs to the language. So I know the language is context-sensitive. What I can't figure out is if the language is context-free.

I tried to build a pushdown automata but I couldn't find any. I also tried to use the pumping lemma but wasn't able to find a good word to prove it's not context-free.
Could you help me?

A word like $a^nb^nc^n$ should work. Remember that the pumping lemma also allows you to pump down, i.e., delete the pumping segments.

Also, each splitting $z=uvxyz$ can have its own "contradiction" to show it does not adhere to the pumping lemma. You can use different arguments, so different $i$ for each splitting. That is very natural here as $a$ has the minimal number of occurrences, and contradiction is reached by adding occurrences, whereas for $c$ deletion (choosing $i=0$) will get you into trouble.


Complexity of enumeration vs complexity of counting I have a problem understanding the difference between complexity of enumeration and counting. We can solve every counting problem using enumeration algorithm.
Now, I have problem with the following. Let say that we have to count the number of positive integers less or equal than positive integer $N$. We know that the answer is $N$ and therefore we can solve the counting problem in $\mathcal{O}(1)$. Corresponding enumeration problem is to output every positive number and this can be done in $\mathcal{O}(N)$ steps and I believe that this is pseudo-polynomial complexity and that in fact complexity is exponential.
Are these complexity assumptions correct? Is the number of solutions of counting problem always bounded by the time complexity of corresponding enumeration algorithm?
Any hints or suggestions appreciated.

Yes. An enumeration algorithm executes at least 1 step (an instruction, line of code, or whatever else your metric is) for every instance it finds, so there's at least as many steps as there are instances to count.
Just remember that if you use an asymptotic time complexity like $O(N)$, it doesn't tell you enough for an exact bound on the count. For example, it takes $O(N)$ time to enumerate $1,\dots,2N$.


Amdahl's Law and Computer Science I would like to learn more about Amdahl's Law and other similar topics.  In what branch of computer science would one place Amdahl's law?  Could someone point me to a textbook or further reading (aside from Wikipedia or other sites that are found on the first page of a Google search) that discusses it?

Amdahl's Law is perhaps most associated with computer architecture (Gene Amdahl was a computer architect).  Although initially applied to the potential speedup from partial parallelization of a task, the formula applies to the benefit from any partial improvement.

In its general form, it can be applied to many different types of problems.  E.g., the improvement in voter turn out by getting a fraction of potential voters to always vote.

Since it is a rule of thumb intended to compensate for excessive expectations from dramatic improvements in part of a system, it is most useful when the improvement factor is large and is intended more for quick estimation (and generally the best case--though sometimes an improvement can unexpectedly benefit other aspects) than an exact measurement (as systems tend to have complex and subtle interactions).  (Quick estimation facilitates quick pruning of paths of exploration.)

As a mathematically based rule of thumb, it is not an especially deep topic (rules of thumb based on history, economics, etc. are generally more susceptible to discussion), though Gustafson's Law points out that context is important.  However, Amdahl's Law is an important corrective to optimism with respect to dramatic (but partial) improvements.


Will the future quantum computers use the binary, ternary or quaternary numeral system? Our current computers use bits, so they use the binary numeral system. But I heard that the future quantum computers will use qubits instead of simple bits.

Since in the word "qubit" there is the word "bi" I first thought that this meant that quantum computers would use binary (base 2).

But then I heard that qubits had three possible states: 0, 1, or a superposition of 0 and 1. So I then thought that this must mean that they will use ternary (base 3).

But then I saw that one qubit can hold as much information as two bits. So I thought that this maybe mean that they will use quaternary (base 4).

So which numeral system will the future quantum computers use: binary, ternary or quaternary?

The other answers are nice, but none address the question: what numeric base(s) might quantum computers use? I will answer in two parts: first, the question is a little subtle, and second, you may use any numeric base, and then you work with qutrits or in general with qudits, which lead to qualitatively new intuitions! Or at any rate, I will try to make the case that they do.

A quantum bit isn't just a $0$ or a $1$, it's a bit more complex than that. For example, a quantum bit may be in the state $\sqrt{\frac{1}{4}}|0\rangle+\sqrt{\frac{3}{4}}|1\rangle$. When measured, you will measure the outcome $0$ with probability $\frac{1}{4}$ and the outcome $1$ with probability $\frac{3}{4}$. The 'superposition' you talked about is $\sqrt{\frac{1}{2}}|0\rangle+\sqrt{\frac{1}{2}}|1\rangle$, but in general any pair of complex numbers $a$ and $b$ will do, as long as $a^2+b^2=1$. If you have three qubits, then you can entangle them, and the state will be

$$a_0|000\rangle + a_1|001\rangle+a_2|010\rangle+a_3|011\rangle+a_4|100\rangle +a_5|101\rangle+a_6|110\rangle +a_7|111\rangle$$

But when you measure this three-qubit system, your measurement outcome is one out of these 8 states, that is, three bits. This is this really weird dichotomy where on the one hand quantum systems seem to have this exponential state space, but on the other hand we only seem to be able to 'get at' a logarithmic part of the state space. In 'Quantum Computing Since Democritus', Scott Aaronson probes this question by matching off several complexity classes to try and understand how much of this exponential state space we can exploit for computation.

Having said that, there is an obvious complaint to the answer above: all the notation is in binary. Qubits are in a superposition of two base states, and entangling them doesn't change that much, because three qubits are in a superposition of $2^3$ base states. It's a legitimate complaint, because one usually thinks of $\texttt{unsigned int}$ as a number, and only remembers that it is implemented as a 32-bit string as an afterthought.

Enter the qutrit. It is a vector in $\mathbb{C}^3$, in other words, it consists of three base states rather than two. You operate on this vector with a $3\times 3$ matrix, and all the usual things done in quantum computing don't change much, because any operation expressed in terms of qutrits can be expressed in terms of qudits, so it's really just syntactic sugar. But some problems are much easier to write down and/or think about when expressed as qudits instead of entangled qubits. For example, a variation of the Deutsch-Josza problem might ask, given an oracle for a function $f\colon \{0,\ldots, kn-1\}\rightarrow \{0,\ldots, k-1\}$, is this function constant or balanced, given that one is promised to be the case? This function naturally takes one $k$-qudit register as input. To solve it, you must apply a Fourier transform to this $k$-qudit, like so: (if this goes over your head, don't worry, it's just for illustration)

$$|a\rangle \mapsto \sum_{u=0}^{k-1}e^{i2\pi\frac{au}{k}}|u\rangle$$

If you want to express this in binary, you end up with a gate that does this on numbers $0\ldots k-1$ and acts trivially (does nothing) on all numbers $\geq k$, which is slightly less contrived than doing it this way. Similarly, consider a Bernstein-Vazirani variation where the oracle computes an in-product in some radix $r$. If $r=2$, then we know how to do it. But if $r=5$, the problem is much easier to solve by hand using several $5$-qudit registers. Some problems are easier if you have several different qudit registers, e.g. one $5$-qudit register and one $2$-qudit register.

In summary, yes, you are free to consider other numeric bases, and in the right setting that will make your life easier, for the same reason that thinking about numbers in terms other than their binary expansion helps you with normal computers. I felt compelled to answer because while most answers explained that a qubit has something to do with two base states when measuring but infinite in principle, no answer mentioned that the OPs suggestion of using other bases is legitimate and in fact really happens (for example, in Quantum walks on graphs, Aharonov et al. use a subroutine that takes a qubit and an $n$-qudit as input)


Dijkstra's algorithm vs A* The A* algorithm terminates when the f (distance + heuristic) is less than the f values for all of the nodes that haven't been visited. Dijkstra's algorithm produces the shortest path to every node from a starting point (not just the end node - the goal).
Is it possible to modify Dijkstra's algorithm so that when the distance to the end node is shorter than the distances to all of the unvisited nodes in the priority queue, we terminate the algorithm?

Yes, that is a common variant. In fact, Dijkstra himself included this early termination in his algorithm (see problem 2). So in that sense it's not really a modification, it's how Dijkstra himself described the algorithm to begin with. As Wikipedia puts it:

Dijkstra's original algorithm found the shortest path between two given nodes,[6] but a more common variant fixes a single node as the "source" node and finds shortest paths from the source to all other nodes in the graph, producing a shortest-path tree.

([6] is the same paper I linked to)
However, in my perception, the original version is the more popular one.
To make the exit condition a bit more precise, the algorithm can terminate when a goal node is taken out of the frontier. That can also happen if a goal node is tied for the lowest cost with other nodes. The same applies to A*. I intentionally use "a goal", because Dijkstra's algorithm also works with multiple goals or with a predicate that is evaluated to determine whether a node is a goal node.
By the way a recurring incorrect variant of Dijkstra's algorithm is to test whether a node is the goal when it is first reached and then terminate, but this fails to take into account that as long as a node is still in the frontier, it may be possible to find a shortcut to it.


What is the only condition that would cause the Insert operation of a dynamic data structure to return a “data structure full” error? I want to know where can I find some resources on this question, because, after researching for a day and half, I couldn't find information specific to my question. Can anyone help me answer my question? I know that dynamic data structures (such as linked lists) can expand the amount of nodes at runtime, but if that's the case, how could it ever return a "full error" message if has an unlimited amount of storage to get keep holding nodes inside of it?

I think this belongs more to StackOverflow than here.

As for your question, nothing in reality is unlimited. Computers have finite memory, finite storage. Words have a fixed (usually 32 or 64-bit) length, which might overflow. Or there might be some other engineering decision that limits the size of these data structures. Unlimited anything only exist in textbooks.


Proving that language is regular or not regular Let $L$ be a regular language. Prove that:

  $L_{+--}=\left\{w: \exists_u |u|=2|w| \wedge wu\in L\right\}$
  $L_{++-}=\left\{w: \exists_u 2|u|=|w| \wedge wu\in L \right\}$
  $L_{-+-}=\left\{w:\exists_{u,v} |u|=|w|=|v| \wedge uwv\in L\right\}$

  are regular and:

  $L_{+-+}=\left\{ uv:\exists_w |u|=|w|=|v| \wedge uwv\in L \right\}$

  is not regular.

Seems very hard to me. I suppose 1-3 are similar (but I may be wrong), but I don't know how to approach. General idea is usually to modify finite state machine for $L$ to accept other language. But those constructions are often very sophisticated and I still can't come up with it alone.

Here is a proof that the language $L_0 = \{ w : \exists_u |u|=|w| \land uw \in L \}$ is regular. It can be modified to show that the first three on your list are regular. (Note that I changed $wu$ to $uw$.) Given a DFA for $L$, we build an NFA for $L_0$. The first thing that the NFA does is guess (take an $\epsilon$ move) a state $q$, whose intended semantics is the state that the DFA for $L$ ends up after reading $u$. It then simultaneously runs two copies of the DFA for $L$, one starting at the start state and the other starting at $q$. On reading a symbol $a$, it moves according to an arbitrary symbol on the first, and moves according to $a$ on the second. A state is accepting if the first copy is at state $q$ and the second is at an accepting state.

For the final one, consider the language $L= a^+ b^+ c^+$, and intersect $L_{+-+}$ with $a^+ c^+$.


What is the effect of operating systems on execution speed? I'm using a Raspberry Pi 2 which works with 900MHz. (Asked this question there and they think it belongs to cs)

My question is: since it also runs an operating system in the background, I expect this would take some of the processing power.

So, how significant is the speed reduction due to operating systems? If I run a single code for example, what execution speed should I expect on average? Is it still close to 900MHz, or is it significantly lower?

Furthermore, is there a specific operating system or programming language that I can use to make it run faster?

This question doesn't have a straight forward answer, or rather the answer is very case dependent.  (And as some of the comments pointed out, attempting to qualify this as MHz is meaningless, your CPU will run at the same speed regardless {not counting power optimizations}, it's just a case of who's code it's running, yours or the OS's).

An operating system does many things for you so your simple code that does a couple of I/O operations wouldn't be as simple without calls to the operating system.  To take the OS out of the equation, you'd have to write more code to replace device driver functionality.  Your OS is doing a LOT of work just to accept that letter "A" you typed and display it on a screen.

If your I/O is to a file system, you'd have to write code to replace the file system code provided for you by the OS.

If you expect multiple tasks to run simultaneously or do multithreading, you'll also have to write code to replace the scheduling functionality.

If you allocate and deallocate memory, you'd have to write code to perform those functions.

If you want your program to be notified when an event occurs or keep time or any of a number of other functions, you'll have to supply all that code as well.  And that's just PART of what an Operating System is doing.

You also have to consider that all that OS code that you're taking advantage of has been optimized and debugged for you.  You're likely to write replacement code that is buggier and slower than the OS code you're replacing.

Then once you've got all that written, you'll have to figure out how to load the program into memory and start execution...

That said, there definitely IS overhead involved in using an operating system.  Most OS's are built for a general use case and will have many features and functions that you don't need for your specific program.  But most of us are willing to give up a few % of CPU and memory in order to get the convenience that an OS will bring.

As for which OS will make it go faster... again it depends on your application and needs.  Some OS's will definitely run some applications faster than others, but which OS runs faster depends on the features being used.

And there are reasons other than speed to choose one over another.  Application availability, security, interoperability, device compatibility, availability of programming tools, etc. are all factors to consider.


Regular Expression as basis for creating this grammar I made a right-linear grammar from a regular expression:

The alphabet is:

$Σ = \{a, b, c\} $

Regular expression:

$r = cc^{*}(ba)^{*}bb$

My solution, it seems a little too short like I'm leaving something out. Maybe someone can see where I went wrong on the right-linearity:

$ S \to cA $

$ A \to b a A | B | cA $

$ B \to bb $

$A \rightarrow ba \mid A \mid B \mid cA$

under this $bababaccc$ is also legal

You could try something like this...

$S \rightarrow cS|cA$

$A \rightarrow baA|B$

$B \rightarrow bb$


Calculating CPU throughput on a single cycle vs multicycle datapath When calculating the throughput of a CPU, how does it differ when it is implemented with a single cycle datapath versus a multicycle datapath? If for example the CPU is running 1 GHz freq, then obviously it would have 1,000,000,000 clock cycles per second...and in a single cycle, it takes 1 CPI. So what would be the throughput? And how would it be different in the multicycle datapath where clock cycles differ between instructions?

Every instruction in a CPU goes through an Instruction execution cycle. In other words every instruction goes through multiple stages like Fetch,Decode,Execute,Writeresult. In modern processor the number of stages can go up to 20. So for single cycle instruction execution (all stages finish their work), the clock duration need to be large and hence the processor should operate at lower frequencies. CPI would be 1 and hence throughput is 1/F, where F is processors clock frequency.
But most modern processors use pipelining. They take advantage of the fact that each stage hardware is different and therefore multiple instructions can be at different stages of instruction execution cycle, at the same time. The clock frequency can be higher as amount of work being done (Max of all stage execution time) is smaller. The performance will be optimal if all stages of instruction execution cycle take equal amount of time.  Hence a pipelined processor with n stage is able to provide a throughput of one instruction per cycle. CPI should be P where P is the number of pipeline stages. But often a pipeline get stalled and different types of instructions (integer,float, branch, load,store...) take different number of cycles to complete. Hence CPI will vary for each program depending on instruction mix.
Pipelined processor having superscalar execution capabilities are able to take advantage of the fact that there are multiple processing/execution hardware in a processor, e.g., Integer ALU, floating-point ALU, memory management unit. So taking advantage of this fact more than one instruction can be in its execution stage at the same time. To support this fetch and decode stages have the capability to read and process multiple instruction in parallel. They are then able to feed multiple instruction to the execute stage, and more than one instruction is then completed per cycle. CPI will be lower in this case, even going to a value less than 1. In other words more than one instruction is able to complete within a single cycle.


Possessive Kleene star operator Has anyone studied the consequences of the Kleene star in regular expressions to always be "possessive"?

In other words, if * would always match as much as possible and no backtracking is allowed, would I still be able to express any regular language?

Let's say that @ is the possessive * operator.

There are cases where it doesn't matter: a*b and a@b both will match any string with 0 or more $a$ followed by a $b$.

However there are cases where being possessive is relevant: a.*b will match any string that starts with $a$ and ends with $b$ but a.@b will never match any string as the greedy @ will eat any character, including the ending $b$.  The equivalent expression would be a[^b]@b.

One may be tempted to think that for any non-possesive expression there is an equivalent possessive expression and viceversa but I wasn't able to find any proof of this.

I'm limiting myself to * considering a+ equivalent to aa*.

As D.W. suggested in the comments below, I tried to start from the DFA. I didn't go much far, as this seems to have more to do with the way the non-determinism is handled, rather than with the structure of the automaton.

Could anyone point me in the right direction?

EDIT 3

I've posted an answer that I believe is correct.

EDIT 2

(REMOVED)

EDIT 1

(It has pointed out to me that the right term to use would be "possessive" (http://www.regular-expressions.info/possessive.html) rather than "greedy". Thanks.)

I will share below my attempt to prove that you can express every regular language as a regular expression using just the $+$ and $@$ operators. Unfortunately, my attempt at a proof has a gap.  Perhaps you can repair the gap.  My attempt based upon Brzozoswki's method for generating regular expressions, so I'll assume you are already familiar with how that works.

First, some definitions and other preliminaries.

Definition. Define $A^+$ to be the language of one or more words from $A$, i.e., $A^+ = \{a_1 a_2 \cdots a_k \mid k \ge 1, a_1,\dots,a_k \in A\}$.  In other words, $A^+ = A^* \setminus \{\epsilon\}$.

Definition. $\newcommand{\rp}{\backslash\backslash}$  For sets $A,B \subseteq \Sigma^*$, define $A\rp B$ by $A\rp B = (A^*\backslash B) - (A^+ \Sigma^*)$, where $A\backslash B$ is the left quotient, and $-$ represents the difference of two sets.  In other words, $A\rp B$ is the smallest set $C \subseteq \Sigma^*$ such that $A^* B = A^* C$ and such that no word in $A^+$ is a prefix of any word in $C$.

Example: $\{01\}\rp \{0101010,101\} = \{0,101\}$.

Note that if $A,B$ are regular languages, then $A\rp B$ is also a regular language and can be computed effectively from $A,B$.  (This follows from the standard closure properties of regular languages.)

Definition. The semantics of regular expressions using the $+$ and $@$ operators are defined inductively:

$L(w) = \{w\}$ if $w \in \Sigma^*$
$L(A_1+A_2+\dots+A_k) = L(A_1) \cup L(A_2) \cup \dots \cup L(A_k)$
$L(A^@ B) = \{ab : a \in L(A^*), b \in L(B), b \notin L(A^+ \Sigma^*)\}$
$L(w B) = \{wb : b \in L(B)\}$ if $w \in \Sigma^*$
$L(A^@) = L(A^*)$
$L((A_1+A_2)B) = L(A_1B + A_2 B)$, $L(A(B_1+B_2)) = L(AB_1 + AB_2)$
$L(A_1 A_2 \cdots A_k) = L(A_1 (A_2 \cdots A_k))$

(As a consequence, every regular expression using $+,@$ can be equivalently written as a sum of terms of the form $A_1 A_2 \cdots A_k$ where each $A_i$ is either of the form $w_i$ or $C_i^@$ for some $w_i \in \Sigma^*$ and some regular expression $C_i$ using $+,@$.  Once it is rewritten in that sum-of-products form, the semantics of the resulting expression is given by the definition above.)

For instance, we have the following property: if there is no word in $L(A^+)$ that is a prefix of any word in $L(B)$, then $L(A^@ B) = L(A^* B)$.

In what follows, I won't try to distinguish between a regular expression $E$ and its corresponding language $L(E)$.

Now we can prove a generalization of Arden's lemma.

Lemma 1.  Let $A,B \subseteq \Sigma^*$ be given, and assume $\epsilon \notin A$ and no word in $A^+$ is a prefix of any word in $B$.  Suppose we have the equation $X=AX + B$ (i.e., $X=AX \cup B$).  Then the least solution to this equation is $X=A^@ B$.

Proof.  Arden's lemma says the least solution is $X=A^* B$.  Now, since no word in $A^+$ is a prefix of any word in $B$, in fact $A^* B = A^@ B$, as there can be no ambiguity about how much the $*$ operator gobbles up.

Lemma 2. Let $A,B \subseteq \Sigma^*$ be given, and assume $\epsilon \notin A$.  Suppose we have the equation $X=AX + B$ (i.e., $X=AX \cup B$).  Then the least solution to this equation is $X=A^@ C$ where $C=(A\rp B)$.

Proof.  Arden's lemma says the least solution is $X=A^* B$.  As noted above, $A^* B = A^* C$.  Moreover, no word in $A^+$ is a prefix of any word in $C$, so $A^* C = A^@ C$.

Now given any regular language $L$, we can apply Brzozoswki's method to it, but using Lemma 2 above instead of Arden's lemma.  It's tempting to hope that the result will be a regular expression for $L$ that uses only the operators $+$ and $@$, but unfortunately there's a gap: I don't know whether one can prove that $A\rp B$ can be represented as a regular expression using only the $+$ and $@$ operators.  So, this proof method has a big gaping hole in it.

But perhaps someone will see a way to build on this and prove the desired result.


Is deciding solvability of systems of quadratic equations with integer coefficients over the reals in NP? In the book 'Computational Complexity' by Arora and Barak the following question is posed (exercise 2.20.):

  Let REALQUADEQ be the language of all satisfiable sets of quadratic equations over real variables. Show that REALQUADEQ is NP-complete.

I know how to show NP-hardness, but I'm stuck when it comes to proving that this problem is in NP, in particular how to show that we can describe a solution using a polynomial number of bits.

I did some research and found out that over the complex numbers, it remains an open question if the problem is in NP [1]. It also seems closely related to the existential theory of the reals, which again is not known to be in NP.

Thus my question: Is this problem known to be in NP? And if so, could somebody point me in the right direction regarding the proof.

[1] Pascal Koiran, Hilbert’s Nullstellensatz is in the Polynomial Hierarchy, Journal of Complexity 12 (1996), no. 4, pp. 273–286.

This problem (usually called QUAD) is in fact complete for the existential theory of the reals, and thus showing NP-membership would be a fantastic and unexpected result. It seems that Arora and Barak intended only to ask for a proof of NP-hardness.


Complexity for find pairs with sum - BST I have written an algorithm for find all the pairs in a BST which have a given sum.

def getPairsForSum(rootNode : Node, expectedSum : Int) : List[(Node,Node)] = {
    def check(node1 : Node, node2 : Node) : List[(Node,Node)] = {
      if (node1 == null || node2 == null) Nil
      else {
        val actualSum = node1.value + node2.value
        if (actualSum == expectedSum) {
          List((node1, node2))
        } else if (actualSum > expectedSum) {
          check(max(node1, node2).leftNode, min(node1, node2)):::
            check(min(node1, node2).leftNode, max(node1, node2))
        } else {
          check(max(node1, node2).rightNode, min(node1, node2)):::
            check(min(node1, node2).rightNode, max(node1, node2))
        }
      }
    }
    if(rootNode.value > expectedSum/2) check(rootNode, rootNode.leftNode)
    else check(rootNode,rootNode.rightNode)
  }

It works well (though gives nodes like (n1,n2) and (n2,n1) in the result). I would like to know the complexity of this algorithm. I am not sure how do I approach calculating time complexity. Is this algorithm better than n square??

EDIT
Assuming that this bst does not allow duplicates.

It would be $O(n^2)$ in the worst case. Suppose root of BST is $15$, all left nodes are $7$, and all right nodes are $21$. We want to find all pairs which their sum is $28$. Hence, you should report all $\frac{n}{2}\times \frac{n}{2}$ items (all left nodes with all right nodes). Hence, your algorithms should report $O(n^2)$ pairs in the worst case.


LTS of this simple FSP I have this finite-state process with the corresponding labeled transition system:

The FSP is:

MAKER = (kochen -> fertig -> MAKER).
USER = (fertig -> essen -> USER).

||MAKER_USER = (USER||MAKER).

Why is essen possible after the second kochen? USER needs to have fertig in order to able to essen right?

The middle transition fertig is the shared action so this must be ran parallel, but after this there are 2 transitions which dont have to run parallel, one is kochen and the other is essen.

Assume, we are now in the point where fertig is done by both processes and now we have 2 options, kochen and essen. We do both one after another as options: if i do kochen then the option essen is left, if i do essen, then kochen is left. I also have to do what is left to do.

So, let's say, I choose essen then go to USER back, but if I do kochen first, then I have to do essen which is the second essen in this case.


Neural Network | What is the purpose of hidden layers and how many should I use? I am pretty new to Neural Networks and I have two questions about hidden layers:

1.
What is the purpose of hidden layers? I was wondering this because obviously you can get every result you want with just one weight per input, as you're performing a multiplication.

2.
How should I choose the number of hidden layers and how many cells should they have?

It is actually not true that you can get any result that you want without any hidden layers. Consider for example a neural network with one input and one output. The only functions that such a network can be compute is threshold functions – whether the input is at most something or at least something (assuming the output is converted to Boolean).

Roughly speaking, the strength of neural networks as a computation model (rather than as a machine learning instrument) depends on two resources: size and depth. Every function can be computed (approximately) using only one hidden layer, but adding more hidden layers can dramatically reduce the size of the network needed to compute the function.

I think it is fair to say that at the moment, choosing the best network architecture involves some experience and some experimentation, since there is no good understanding of why neural networks work. Look up a paper on a similar task, and try similar parameters. There are known methods for estimating whether the network is too large or too small, and probably there are similar rules of thumb regarding depth.


Do we create a programming language by writing a compiler? Say, I wanted to create my own programming language. Assuming that I have made all of the decisions about how I want it to look and act, do I just need to write a compiler for it?

For example, is the high-level Java code anything other than just text and this text is in the correct format for the compiler to accept it and turn it into something else?

My question is, is the creation of a programming language done through a compiler? High-level is fine.

The short answer is no.

You can think of a programming language as a mathematical formalism used for expressing computation. A compiler/interpreter is a just a piece of an actual software that carries out that computation, and should not serve as the language specification.

That being said, in addition to lexical and syntax specification of a language, you should also define semantic specification, i.e., what does a (syntactically correct) program written in your language actually mean. The obvious semantics to start with is operational semantics, where the meaning of a program is given in terms of how the program actually runs. That is, it (mathematically) precisely defines how programs execute. On top of this semantics you should build an actual compiler/interpreter with optimizations and so forth.

Specifying full operational semantics of your language will give you a formal language documentation and it will make you understand your language to the very details. Also, it will allow you to formally reason about some aspects of the language. Writing down operational semantics is really a good habit.

There are other useful semantics as well, such as axiomatic, denotational, and game semantics. However, they are more advanced and typically don't make their way into a compiler/interpreter.


find derivation trees for CFG I need to draw the derivation tree for $1-2-(3-4)*5*6$ from the grammar below.
 I want to know how many possible derivation trees are there from this grammar.

$$\begin{align}V_n&=\{expr,term,factor,number\}\\
V_t&= \{(,),-,*,0...9\}\\
P&=\left \{
\begin{aligned}
expr&\to expr-expr\;\mid\;term\\
term&\to term*factor\;\mid\;factor\\
factor&\to number \;\mid\; (expr) \\
number&\to 0\mid1\mid2\mid3\mid4\mid5\mid6\mid7\mid8\mid9
\end{aligned}
\right \}\\
S&=expr
\end{align}
$$

The possibilities that I can find are:

$$(1-2)-(((3-4)*5)*6)\\
1-(2-( ((3-4)*5)  *6))$$

Are there other possibilities?

No, there are no other possibilities as far as I can see.

The ambiguity comes from the production rule $expr \rightarrow expr - expr$. This rule allows you to derive the expression in two different ways:

Derive $1$ from the left $expr$ and the rest from the right $expr$
Derive $1-2$ from the left $expr$ and the rest from the right $expr$

Some ideas that might help.

The precedences look ok to me; the lower the precedence the closer the operator should be to the root (in this case $expr$).
- has the lowest (derived from $expr$), * has a higher precedence (derived from a production after $expr$).
And the parentheses (...) have the highest (derived from a production after $term$).

The $term$ production rule is left associative, which helps avoid the ambiguity of associativity.

The $expr$ production rule is the problem as mentioned above. A solution to that would be similar to what you see for the $term$ production rule. Make it left associative.


Number of minimal unsatisfiable partial assignments in 2-SAT/3-SAT A minimal unsatisfiable partial assignment for 3-CNF is a partial assignment that:

There exist a clause where all variables are unsatisfied.
Unfixing any variable make every clause contain at least one free variable.

Particularly for 2-SAT and 3-SAT is their number bounded by polynomial?

If yes, then how number of such assignments in SAT can be reduced from $2^m$ to polynomial, when applying Tseytin transform? $m$ is number of variables.

Yes, the number of minimal unsatisfiable partial assignments is upper-bounded by a polynomial.

Suppose there are $n$ clauses.  There are $n$ ways to choose which clause is unsatisfied, call it $C$.  Suppose  clause $C$ mentions variables $x_i,x_j,x_k$.  Then the partial assignment must assign values to $x_i,x_j,x_k$ but not to any other variable.  (If it assigned a value to $x_\ell$, then unfixing $x_\ell$ would leave clause $C$ without a free variable, which violates the second requirement.)  There is only one way to assign values to $x_i,x_j,x_k$ to make clause $C$ unsatisfied.  So, there are at most $n$ minimal unsatisfiable partial assignments.


Complexity of Context Sensitive Languages I was reading above complexity classes from Formal Languages and Automata book by Peter Linz.

It gives following facts (in Theorem 5.2):

  Consider we have a CFG without null or unit productions. For parsing a string w, if restrict ourselves to leftmost derivation, we can have no more than $|P|$  sentential forms after one round, no more than $|P|^2$ sentential forms after the second round, and so on. Parsing $w$ in CFG without null or unit productions cannot involve more than $2|w|$ rounds. Therefore, the total number of sentential forms cannot exceed $M=|P|+|P|^2+⋯+|P|^{2|w|} =O(P^{(2|w|+1)})$

Then (in Example 14.5, citing back above theorem) it says

  However we cannot claim that
  $CSL \subseteq DTIME(|P|^{cn+1})$
  because we cannot put an upper bound on $|P|$ and $c$

I dont understand why it is trying to use the fact about CFLs to find time complexity of CSLs. Is it because if CFLs does not follow that DTIME complexity, CSLs will also not follow it as $CFL\subset CSL$? But then, given any grammar, $|P|$ is fixed, its not infinite and I feel $c$ is always 2 as given in the proof of the theorem 5.2.

When the book says

  Following the analysis leading to Equation (5.2),

it implies that if you apply the same kind of reasoning that resulted in Equation (5.2) to context-sensitive languages, then you will get the similar equation

  $$ N = |P| + |P|^2 + \ldots |P|^{cn} = O(|P|^{cn+1}). $$

This equation is the analog of Equation (5.2) for context-sensitive languages. To prove this equation, you use reasoning similar to that used to prove Equation (5.2).


What factors of the integer dataset being sorted can I change, in order to compare two sorting algorithms? I am comparing two comparison and binary data structure based sorting algorithms, the Tree Sort, and the Heap Sort. I am measuring the time taken for both algorithms to sort an increasing size of an integer dataset. However, I am wondering if there are any other variables which I can modify, for example standard deviation, in the integer dataset itself that would be of any benefit to my comparison.

The simplest is not doing a proper shuffle, that is having partially (reverse) sorted sequences, in extremis this can be the entire range is sorted except a few elements at the end that need to be inserted somewhere in the range.
For comparison sorts the distribution of elements doesn't make a difference, only how many duplicate values there are. This is something you can adjust as well.


Gray-like code with maximum value <= maximum value of original symbol I want to iterate through the numbers $0,1,2,\dots,n-1$ in some order, where each number in the sequence differs by only one bit from the previous bit.  I'm going to be using each number as an index into a matrix, and each index must be in the range $0..n-1$.

Gray codes look useful.  The problem is that standard grey codes only work when $n$ is a power of two.  Or, if we use a $k$-bit gray code (where $k = \lceil \lg n \rceil$), then some of the numbers in the gray code sequence will be larger than $n-1$, which will cause a segmentation fault when I try to access that index in the matrix.

So is there something like a gray code that works when $n$ is not a power of two?  In other words, is there a way to construct a permutation of $0,1,\dots,n-1$ so that each number is at a Hamming distance of one from the previous number in the sequence?

Yes, such a Gray code sequence can be constructed for all $n$, even when $n$ is not a power of two.  I'll describe how, below.

I will say that $a_0,\dots,a_{n-1}$ is a Gray code sequence for $0,1,\dots,n-1$ if each $a_i$ is in the range $0..n-1$, and if each $a_i$ differs from $a_{i-1}$ in a single bit position.  Note that this generalizes the usual notion of a Gray code, to the situation where the numbers are not a power of two.

Let $n = 2^t + u$, where $u \le 2^t$.  We'll use two steps:

First, recursively construct a Gray code sequence for the numbers $0..u-1$.  Suppose the sequence is $x_0,x_1,\dots,x_{u-1}$.  This means that each $x_i$ is in the range $0 \le x_i \le u-1$ (for each $i=0,1,\dots,u-1$), and each $x_i$ differs from $x_{i-1}$ in a single bit position (for $i=1,2,\dots,u-1$).  This in turn gives us a Gray code sequence for the numbers $2^t,2^t+1,2^t+2,\dots,2^t+u-1$ by just adding $2^t$ to each element in the sequence: specifically, $2^t+x_0,2^t+x_1,\dots,2^t+x_{u-1}$.
Second, construct a Gray code sequence for the numbers $0..2^t-1$ that starts at the number $x_{u-1}$.  A cool fact about the standard Gray code construction (for a power of two) is that it is cyclic, i.e., you can start anywhere and get to all the numbers, from that starting point.  Let $y_0,y_1,\dots,y_{2^t-1}$ be this sequence.  As mentioned, we have $y_0 = x_{u-1}$.

Now if we just concatenate these two sequences, we get an ordering of $0..n-1$ where each number in the sequence differs from its previous number by a single bit.  In particular, the full sequence is

$$2^t+x_0,2^t+x_1,\dots,2^t+x_{u-1},y_0,y_1,\dots,y_{2^t-1},$$

with the $x$'s and $y$'s defined as above.  This gives a simple and easy to implement construction for what you want.

Caution: Iterating through elements of the matrix in Gray code order will trash your cache.  Caches are optimized for sequential access.  You're doing random access (jumping around in the address space), so the caches will be useless and every memory access will be a miss in the cache.  As a result, performance might suffer.  Beware.


Test if there are two subsets which cover a set Given a set $S$ of $n$ elements, and a set $\mathcal{X}$ of $m$ subsets of $S$, decide if there exist $U,V \in \mathcal{X}$, s.t. $U \cup V = S$.

Brute force would take time $O(nm^2)$ but is there any way of solving this more efficiently?

There is an $O(n2^n)$ algorithm which is better than the trivial $O(nm^2)$ algorithm when $m$ is really big. Let $f$ be the characteristic vector of $\mathcal{X}$, of length $2^n$; $f$ can be calculated in time $O(n2^n)$. The number of solutions $U,V$ is exactly equal to
$$ f' \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^{\otimes n} f. $$
Indeed, if $\chi_U$ is the indicator vector of $U$ then
$$ \chi'_U \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^{\otimes n} \chi_V = \begin{cases} 1 & \text{if } U \cup V = S, \\ 0 & \text{otherwise}. \end{cases}$$
The vector $g = \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}^{\otimes n} f$ can be computed in time $O(n2^n)$ using an FFT-like algorithm, and then the inner product $f'g$ can be calculated in time $O(2^n)$. I'm lying a bit here: the numbers involved might get big. However, if we replace addition with OR, we still find out whether there are any solutions, and all the numbers are in $\{0,1\}$ now.

The function $g$ is in fact related the upward closure of $f$, which is given by $h_U = g_{\overline{U}}$. The FFT algorithm uses the basic operation $h_{U \cup \{i\}} = h_U \lor h_{U \cup \{i\}}$. This makes it clear why $\bigvee_U f_U g_U = \bigvee_U f_U h_{\overline{U}}$ is what we want.


Turing Machine-Like Formalism for The Actor Model Turing machines have a formal symbol alphabet, state and transition-rules based description of how a computation is done.

The Actor Model is sometimes mentioned as a more powerful computational-model than Turing machines (not in what it can compute, but in other aspects).

Is The Actor Model a full fledged Turning machine alternative as a computational model?
Does The Actor Model also have such a symbol-based formal computation description akin to the Turing machine?
Are the actors assumed to be Turing machine equivalent - since each message is processed sequentially (and atomically)?

There are many theoretical results based on Turing machines, e.g. the halting problem, decidability, relation to Gödel's incompleteness theorem etc.

Can these proofs be formally generalize to the Actor Model? Has this been done?

computer scientists generally are of the consensus that the Church Turing thesis[1] is correct and definitive, ie that Turing machines describe computation, and that more powerful forms do not really exist, and take assertions that some model is "more powerful" than Turing machines with extreme skepticism, even near hostility.[2] neophytes to the field who dont fully understand the concept are prey to near-marketing slogans of some theory as "more powerful" than Turing machines but those claims are rarely made by mainstream/reputable computer scientists.

but as a flip side to this, many models of computation are Turing complete.
therefore in CS there is in practice mostly a tolerant, "live and let live" attitude with many different models of computation proliferating depending on what is most relevant and convenient for the problem studied. most basic programming models are Turing complete with basic structures such as memory, conditionals, and loops, subroutines etcetera. so more reasonable claims are, "model [x] is better suited to study [y] because [z]". the Actor model focuses on message passing, communication, concurrency & some security.

nevertheless there is some mostly philosophical debate in CS about some models being "more powerful".

[1] Church Turing thesis

[2] Interactive models of computing vs Church Turing thesis


Deleting nodes from graph so that they can be separated by a straight line I have 2 types of points in a 2D plane, type 'A' and type 'B'. How do I delete the minimum possible number of points so that remaining can be separated (on different sides) by a straight line.

I tried modeling this as a graph, where I have 2 types of nodes, and i delete nodes from it. But I can't formulate an algorithm.

How can I go about formulating an algorithm for this situation?

Try the following (inefficient) approach. Assume there are $N$ points in total. Now with each of the $N$ points try to find a line segment that passes through it with the least number of mis-classifications (number of points that were not correctly separated) by the line segment. The important point to note here is that, you would not have more than $N-1$ such line segments to check for. At the end of the procedure simply choose the point and its best corresponding line segment. The overall complexity is $O(N^3)$ under ideal conditions. Some perturbation of point may be required in the process, if not ideal.

A slightly more efficient procedure is as follows, let the convex hull of the points in type 1 be $P_1$ and those of type 2 be $P_2$. Then I suspect, in the previous procedure, instead of computing the best line segment for every point, just do the procedure for those in $P_1 \cap P_2$.


Runtime of the binary-GCD state machine I am doing self study from MIT OCW exercises and I could not understand this question.

  The following rules define the binary-GCD state machine working on states in $\mathbb{N}^3$ with start state $(a,b,1)$ for $a>b>0$. If multiple rules apply, smaller numbers have precedence.

  Provided $\min(x,y) >0$, then $(x,y,e) \to $

  $(1,0,ex)$ if $x=y$
  $(1,0,e)$ if $y=1$
  $(x/2,y/2,2e)$ if $2|x \land 2|y$
  $(y,x,e)$ if $y>x$
  $(x,y/2,e)$ if $2|y$
  $(x/2,y,e)$ if $2|x$
  $(x-y,y,e)$ otherwise

The binary-GCD state machine computes the GCD of $a$ and $b$ using only division by $2$ and subtraction, which makes it run very efficiently on hardware that uses binary representation of numbers. In practice, it runs more quickly than the Euclidean algorithm state machine.

Each execution of a command (one of rules 1-7 according to algorithm) is a transition and the current state $(x,y,e)$ is stored in registers $A,B,E$. At first the values in the registers $a,b,1$

Here is the question I am having trouble with:

  Prove that the machine reaches a final state in at most $3+2\log(\max(a,b))$
  transitions.

  Hint: Strong induction on $\max(a,b)$

First, why does this state machine assume it halves the $\max(a,b)$ at every two transitions beacuse we can apply rule 4 and 7 and one extra rule to halve the $\max(a,b)$, which is more than two transitions/steps. I know it is not a common case but a case is a case unless proved.
Next I don't see where an extra 3 comes from in $3+2\log(\max(a,b))$.

Unless I've done this example wrong, this question is asking you to prove something that isn't true. Consider $(x,y) = (381,192) = (3\cdot 127,3\cdot 64)$. What happens when you run the algorithm?

  $(3\cdot127,3\cdot 64,1) \rightarrow (3\cdot127,3\cdot 32,1) \rightarrow \ldots \rightarrow (3\cdot 127,3,1)$
  $ (3\cdot 127,3,1) \rightarrow (3\cdot 126,3,1) \rightarrow (3\cdot 63,3,1) \rightarrow \ldots \rightarrow (3,3,1) $
  $ (3,3,1) \rightarrow (1,0,3) $

So starting with $( 3\cdot (2^k -1), 3 \cdot 2^{k-1}, 1)$, the first set of steps applies the 5th rule $k-1$ times, resulting in $(3 \cdot (2^k-1), 3, 1)$. We then alternately apply the 7th rule and the 6th rule. Each time we do this, we go from $(3\cdot (2^j-1),3,1)$ to $(3\cdot (2^{j-1}-1),3,1)$, until we reach $(3\cdot(2^1-1),3,1)$. This takes $2(k-1)$ transitions. Finally, we apply the 1st rule once, for a total of $3k-2$ transitions. But the original value has $\log_2 \max(x,y) \approx {k}$, so we needed
$3 \log_2 \max(x,y) - C$ transitions total for some constant $C$.

It's certainly true, and not hard to prove, that the algorithm runs in $O(\log \max(x,y))$. But the question has the constant wrong.


People crossing a bridge (a proof for a greedy algorithm) The problem

Some people are crossing a bridge. Each one takes a different time to pass.

Assume the people are sorted by their passing time increasingly.

These are the conditions of crossing the bridge:

only 1 or 2 people can cross the bridge at the same time in the same direction;
the speed of the two people crossing is the same as the slower one;
it is night and there is only one flashlight;
the people passing the bridge must carry the flashlight;
the flashlight cannot be thrown over the bridge so it must be carried back to the other end of the bridge.

My greedy solution

The obvious solution seems to be using the fastest guy to take every one to the other end and come back for the rest.

The proof

I tried to prove it like my text book CLRS:

  Cast the optimization problem as one in which we make a choice and are
  left with one subproblem to solve.
  Prove that there is always an optimal solution to the original problem
  that makes the greedy choice, so that the greedy choice is always
  safe.
  Demonstrate optimal substructure by showing that, having made the greedy choice, what remains is a subproblem with the property that if
  we combine an optimal solution to the subproblem with the greedy
  choice we have made, we arrive at an optimal solution to the original
  problem.

I tried something like this:

If we assume the set of all people in the start is $P$ and the set of all people in the destination is $D$ and $O(x)$ is the function that gives the optimum time by getting the set of people and people $p_i$ and $p_j$ are chosen to pass the bridge and $d_k$ is chosen to return the light and $d_k \in D\cup \{p_i , p_j\}$ then:

$$O(P) = Max( t(p_i) , t(p_j) ) + t(d_k) + O(P-\{p_i , p_j\} \cup {d_k})\,,$$

where $t(p_i)$ is the time it takes for person $p_i$ to pass.

Now I have to assume I have an optimal solution $OS$ and show that I can use the greedy choice instead of the choice the $OS$ has made.

I do not know how to proceed further.

The reason you can't prove that the greedy algorithm is correct is because it isn't.

Suppose the people cross the bridge in times 1, 2, 5 and 10 minutes.  The greedy solution involves the one-minute person walking backwards and forwards every time and takes 10+1+5+1+2=19 minutes.  The optimal solution is 17 minutes (spoiler, since it's a famous puzzle that people might want to try on their own).

   1 and 2 cross, 2 returns with the flashlight, then 5 and 10 cross and 1 returns with the flashlight to collect 2: total time 2+2+10+1+2=17 minutes.


Is it possible to accurately determine the number of instructions required to multiply or add two integers in a modern processor? I'm not nearly at the experience level in computer science to be able to properly determine the number of instructions involved in basic ALU calculations, and I'm interested in a certain software concept where the difference is important.

Multiplication

       1011   (this is 11 in decimal)
     x 1110   (this is 14 in decimal)
     ======
       0000   (this is 1011 x 0)
      1011    (this is 1011 x 1, shifted one position to the left)
     1011     (this is 1011 x 1, shifted two positions to the left)
  + 1011      (this is 1011 x 1, shifted three positions to the left)
  =========
   10011010   (this is 154 in decimal)

I've been studying the binary multiplier, which seems to calculate partial products with binary, and then shifts them to the left, the very same way that we do with base-10 multiplication in grade school. It would seem to me that this would require 2 instructions per digit, but that's merely a barely-educated guess.

Addition

I've found Wiki's explanation of an adder-subtractor to be far more advanced, (in description, not operation, surely), and I've had less luck interpreting it thus far.

Purpose

My goal is to determine the number of instructions required to compute the addition / multiplication (respectively) of number sets. Basically, I want to figure:

5 x 5 = 10 --> 5 instructions //example
5,000,000,001 x 456892 --> 50 instructions //example

1 + 1 = 2 --> 4 instructions //example
1,000,042,569 + 1,491 = 1,000,044,060 --> 45 instructions //example

Tl;dr - My Question:

Is it possible to accurately determine the number of instructions required to multiply or add two (whole number) integers in a modern processor?
If so, how is this figured (in both addition and multiplication, based on the size of the number)?

Yes and no.

“Instructions” isn't the right unit of measure: most processors include an ALU and require a single instruction to perform addition or multiplication on a number of a certain size (usually 8, 16, 32 or 64 bits, often with several possible sizes). A more relevant measure is the number of clock cycles required by this instruction. Counting instructions only comes into play when talking about bignums.

The number of clock cycles is determined by the depth of the circuit. A signal can traverse many gates in the same clock cycle, but more gates means a longer path which can be a limiting factor when trying to increase the clock frequency. It doesn't depend on the input values, only on the circuit that is being used (of course the values have to fit within the width of the circuit). For example a 32-bit adder will take the same number of cycles to calculate 1 + 1 and 1,000,042,569 + 1,491.

There are many possible designs for an adder or multiplier circuit. One of the design parameters is using more transistors or more complex connections to achieve faster operations. For example, addition the way we usually perform it requires adding the lowest-order bits, then adding their carry to the bits of order 1, and so on: the carry is propagated linearly, which means that the depth of the circuit is proportional to the word size. There are more sophisticated adders which parallelize the additions to reduce the depth.

The depth of the circuit tells you how many clock cycles the arithmetic operation requires inside the ALU. On a typical complex processor, going from there to the time it takes to perform instructions can be very complex, because you need to consider how the ALU fits in the processor. In order to actually add two values, the CPU must do many things:

Fetch the addition instruction from memory.
Decode the instruction to find that it is an addition, where its inputs are and where its output is.
Fetch the inputs — this can take different number of cycles depending on the width of the operation and whether the inputs are immediates, in registers, in memory, etc.
Make the arithmetic calculation.
Write the result into the output register or memory.

Most processors are very heavily pipelined: all of these steps are performed in parallel for different instructions. For example, at any given clock cycle, there are typically instructions in various stages of being fetched and decoded, different arithmetic operations in various stages of being carried out, etc. Advanced processors often have multiple ALUs so as to be able to make computations in parallel. For these reasons, the time it takes to perform $N$ successive additions is often not $N$ times the time it takes to perform one addition. Though in practice, the biggest variability comes from memory access — accessing an inner cache is dramatically faster than accessing RAM.


Draw DFA that accepts concatenated binary string with condition Let $\Sigma = \{0,1\}$, with $w \in \Sigma^* $ and $value(w)$ the not negative integer value of $w$. $w$ is seen as binary string, with its first index being the least significant bit:

$$value(w_1 w_2 ... w_n) =  \Sigma_{i=i}^n 2^{i-1} w_i$$

The languages is defined as:
$$L = \{a_1b_1a_2b_2 ... a_nb_n \ \in \ \Sigma^* \ \vert \ value(a_1a_2 ... a_n) = 3 \ \cdot \ value(b_1b_2 ... b_n)\}$$

The task is to draw the accepting DFA. I frankly have no idea on how to approach this question. Can someone give me a hint, not the full answer please?

Hint: $3\operatorname{value}(u)=\operatorname{value}(u)+\operatorname{value}(0u)$. Then you're just doing a simple addition with carry.

By the way, there's a much stronger result: For any first order formula $\varphi(x_1,\dots,x_n)$ of the Presburger arithmetic, there is an automaton $A$ over $\{0,1\}^n$ so that $A$ accepts $u$ iff $\varphi(\operatorname{value}_1(u),\dots,\operatorname{value}_n(u))$ is true (where $\operatorname{value}_i(u)$ is the same value that you defined except that since each "letter" of $\{0,1\}^n$ contains several digits, it only looks at the $i^{th}$).

Your question is a special case of this where the formula is $\varphi(a,b)= ``a=3b"$. (Kind of: if $L$ is what you get for this formula, then you'd need to take $f(L)$ where $f$ is the morphism defined by $(b_1,b_2)\mapsto b_1b_2$).


All Pairs Shortest Path Fewest Stops I have a graph with V vertices and E edges. Each edge is a road that takes fuel F to travel. I have a gas tank of capacity K, and want to find the fewest number of refills needed to go from any vertex to any other vertex. If I choose to refuel, I can fill the tank completely.

My thought is to modify the Floyd - Warshall Algorithm to keep track of both number of refills, and amount of gas left. However, I am not sure how to proceed.

Note: This is NOT a HW question. I was reading To Fill or not to Fill: The Gas Station Problem and began to wonder.

This problem cannot be solved using a (modified) Floyd-Warshall Algorithm. The underlying assumption in F.-W. is that all paths arriving at a given node can be extended along the same path to the destination. Therefore choosing the shortest path that arrives at a node is also optimal for all paths that pass through the node. By adding the fuel constraint, this assumption is broken.

More generally, problems of this form are called the Resource-Constrained Shortest Path Problems and are, in general, $\mathcal{NP}$-hard. A generic solution to this problem is to enumerate all feasible paths that lead to any node in the graph, which obviously leads to exponential time complexity. In practice, "dominance" rules are applied to prune partial paths that are clearly inferior to other partial paths; in your case such a dominance rule could be to throw away all paths arriving at a node with more refills and less fuel than another path arriving on the same node.


How to calculate the time complexity of a Catalan-like recurrence by substitution? I was given the following problem:

  Calculate the computational time complexity of the recurrence $$P(n) = \begin{cases} 1 & \text{if } n = 1 \\ \sum_{k=1}^{n-1} P(k) P(n-k) & \text{if } n \geq 2 \end{cases}$$ using the substitution method. Answer: $\Omega(2^n)$.

I have seen there is a closed-form for this recurrence but I am unsure whether it can be used out of the blue or not. I don't know if I have to prove it by deriving it from the recurrence or if there are simpler ways of solving such a problem by mere substitution.

On the other hand, I think substitution is not the right tool to use here. I have tried with both reverse and forward substitution, but in neither approach I could determine the function as with other problems (e.g. QuickSort).

Is it possible to solve this problem with only substitution at all? If so, how can I devise it?

You can use induction. First, check directly that $P(n) \geq 2^{n-2}$ for all $n \leq 4$ (the relevant values are $1,1,2,5$). Now suppose that $P(n) \geq 2^{n-2}$ holds for all $n \leq m$, where $m \geq 4$. Then
$$
P(m+1) = \sum_{k=1}^m P(k) P(m+1-k) \geq \sum_{k=1}^m 2^{k-2} 2^{m+1-k-2} \geq m 2^{m+1-4} \geq 2^{m+1-2},
$$
since $m \geq 4$.


Closed (visited) list in state-space search - How do I make it efficient? As part of an assignment for an AI class that I'm taking, I'm need to solve a puzzle on a 4x4 grid using breadth-first search (each element can take on 12 different values). There is a maximum of 4 moves for each state. Needless to say, after 30-or-so moves, the number of nodes (each representing a state) in the queue gets too large for most (any?) computer to handle, since many nodes are duplicates.

The solution, as far as I know, is to add all visited nodes to a "visited list." This makes it possible to compute without running out of memory, but it takes forever. Why? Because for each node that I add, I have to make sure that it's not in the list of visited nodes. For a somewhat complex puzzle, this list can get really long. Let's say the list gets to 500000 nodes, which is feasible. That means that for every new node I add to the queue, it needs to be compared to 500000 nodes to make sure that it isn't identical to any node in that list. This takes a really long time to compute. It solves the problem, but I'm pretty sure I have the wrong idea about how to approach this to actually make it efficient.

I know BFS usually isn't a very good approach to these kinds of problems, but it's part of the assignment. It's only about actually solving the puzzle, but I'm interested in knowing if there is a way to make it more efficient. In general, I mean. I'm sure that I could tailor the program to make it solve this specific puzzle much faster, but what I want to know if there's some idea that could be applied to all problems.

Any help is greatly appreciated!

Use a hash table to store the visited list. Searching the list should take $O(1)$.


Applications of Graph Automorphisms I've seen the topic of the automorphism group appear in several introductory graph theory books I've looked at. It always feel oddly disjointed and poorly motivated to me.

Is there any practical (or impractical for that matter) applications of knowing the automorphism group of a graph?

Automorphism capture a natural notion of symmetry of graphs. As a result, they can be used to speed up algorithms that would otherwise run slowly by chopping down the search space.

For example, integer programming is usually solved via branch-and-bound. However, if an equation is degenerate this can take far longer than necessary to run, because it has to keep checking symmetric parts of the tree. We can use graph automorphisms to compute the orbits of variables in the linear programming problem, and then treat parts with the same orbit as identical. A recent application of such techniques to MILP can be read here.


show that language $L'$ is regular (given $L$ regular) I am working on the following question:

  $L$ is regular. Show that $L'=\{x|\exists y,z,\ xyz\in L\wedge |x|=|y|=|z|\} $ is also regular.

Firstly I show my idea. When you accept it I will try to formalize it.
Every automata can has an equivalent automata with exactly one accept state. So let the automata for language $L$ have exactly one accept state $q_{accept}$.

And now we start in two places - in the normal start state $q_0$ and $q_{accept}$.
From $q_{accept}$ we guess symbol. For one symbol we do two steps. From $q_0$ we go according to symbol - one step.
A state is accepting is when two "starts" meet in one state.

Am I on the right track with this idea?

For language $L-$ $M=(Q,\Sigma,\delta, q_0, F) $
For language $L'-$ $M'=(Q',\Sigma,\delta, q_{start}, F')$
$Q'=(Q\times Q)\cup q_{start}$
Transistions
$\delta'(q_{start}, \epsilon)=\{(q,q_{acc})|q_{acc}\in F\}$
Transition from $(q_1, q_2)$ to $(q_3,q_4)$
$\delta'((q_1,q_2),a\in\Sigma) = \{(q_3,q_4)\}\text{   iff }\delta(q_1,a )=q_3 \text{ and } \delta(\delta(q_4,b),c)=q_2 $ for some $b,c\in\Sigma$
Accepting states
$F'=\{(q,q)|q\in Q\}$


Proving a language (ir)regular (standard methods have failed) I'm currently trying to prove a language regular (for personal amusement). The language is:

The language containing all numbers in ternary that have even bit-parity when encoded in binary.

Now, I've currently tried a few different approaches that have not led me to any success. I've tried using the pumping lemma (couldn't find anything to pump on), Myhill-Nerode (similar) and even counted the number of strings of each length for which the statement is true (my intuition is that it checks out with a probabilistic argument).

Are their any other approaches that might help here, or are there any intuitions that might be helpful? At this point, my best guess is that the language is not regular, but I don't seem to be able to come up with an explanation.

This can be proven, but you need some nontrivial tools to do it.

Start with the set S = {0,3,5,6, ...} of non-negative integers having an even number of 1's in their base-2 expansion.

It is well-known that this set is "2-automatic"; that is, there is a finite automaton accepting exactly the base-2 expansions of elements of S.  Furthermore, it is well-known that this set is not ultimately periodic (that is, it is not true that there exists a period P such that after some point C, if x >= C is in S then so is x+P).  (If it were, then the associated Thue-Morse word 01101001... would be ultimately periodic, but it is known from Thue's 1912 paper not to contain any block repeated three times consecutively.)

Next, assume S is actually "3-automatic"; that is, there is an automaton accepting exactly the base-3 expansions of elements of S.  Then by a classic theorem of Cobham (Math. Systems. Theory 3 (1969) 186-192, this would imply that S is ultimately periodic.  But we have already seen it isn't.

You can find a lot more about these ideas in my book with Allouche, "Automatic Sequences".  Warning, though, our proof of Cobham is a bit flawed, and a corrected version by Rigo can be found online here:  http://arxiv.org/abs/0907.0624 .


Do relativized relations between complexity classes tell us anything about the nonrelativized relation? The existence of relativized relations between complexity classes seems to often be treated as "circumstantial" evidence about the "true" or "real-world" (i.e. nonrelativized) relation between the classes. (For example, this lecture describes one particular oracle separation as "formal evidence" that the complexity classes are unconditionally distinct.) However, as far as I understand (please correct me if I am wrong), for complexity classes $A$ and $B$ and an oracle for a language $L$, all four of these cases are logically possible:

$A = B$ and $A^L = B^L$
$A = B$ and $A^L \neq B^L$
$A \neq B$ and $A^L = B^L$
$A \neq B$ and $A^L \neq B^L$

So presuming that at the end of the day the unrelativized result is what we really care about, what are relativized results "good for"?

I can see one application: if we happen to be able to find oracles for two languages $L$ and $L'$ such that $A^L = B^L$ and $A^{L'} \neq B^{L'}$, then that tells us that any proof that either $A = B$ or $A \neq B$ cannot relativize, and this fact saves us a lot of time by allowing us to immediately skip many potential proofs.

But do oracle results give us any evidence about the actual relation? In particular, why are oracle separations treated as "evidence" (though not a proof) that the complexity classes are unequal? How strong does the complexity-theory community consider such evidence to be? (I know that last question is subjective and hard to answer precisely.)

I am by no means an expert, but 2 things come to mind:

Because if we know things like $A^L \neq B^L$, for some $L$, then a proof of $A = B$ need to be non-relativizing. This puts constrains on the techniques used for such a proof, and thus it is helpful in the way towards getting a proof.

Because if you prove $A^L = B^L$, and the oracle is not very strong, then it seems that you are narrowing down the possibility of $A \neq B$, as with some extra help they become equal. This can arguably be evidence towards believing that $A = B$. To me it feels like saying that John and Peter were equally strong in a fight with boxing gloves. That doesn't necesarily mean that they will be equally strong without the gloves, as one of them could be weaker but use the gloves better. Nevertheless, the information about their fight with gloves is arguable evidence of their relative strength.


Time complexity described by recurrence relation I need to find the time complexity described by the following recurrence relation.

$T(n) = T(n/2) + T(n/3) + T(n/6) + n$

$T(1) = \Theta(1)$

The solution must be something like $T(n) = \Theta(f(n))$.

Obviously the standard form of the master theorem can't help me and any other special cases that I have found weren't useful.

If we draw recurrence tree for this relation than it would be something like following:

         T(n)            -> Cost: n
    /     |    \
T(n/2)  T(n/3)  T(n/6)   -> total cost: n/2 + n/3 + n/6 = n
   .
   .
  T(1) --------------->  highest depth which is about lg(n).

So, there are $lg(n)$ levels and every level has at least cost $n$ so $T(n) = \mathcal{O}(n\lg{n})$.

Now let's conjecture that $T(n) = \Omega(n\lg{n})$ and try to prove it.

We will prove this by induction.

Let's assume that $T(n) \ge c.n\lg{n}$ for some $c > 0$.

$T(n+1) = T(\frac{n+1}{2}) + T(\frac{n+1}{3}) + T(\frac{n+1}{6}) + n+1$

$\therefore T(n+1) \ge c.\frac{n+1}{2}.\lg{\frac{n+1}{2}} + c.\frac{n+1}{3}.\lg{\frac{n+1}{3}} + c.\frac{n+1}{6}.\lg{\frac{n+1}{6}} + n+1$

$\therefore T(n+1) \ge c.(n+1)\lg{(n+1)} + (n+1 - c.(n+1)(\frac{\lg{2}}{2} + \frac{\lg{3}}{3} + \frac{\lg{6}}{6})$

$\therefore T(n+1) \ge c.(n+1)\lg{(n+1)} + (n+1 - c.(n+1)(\frac{\lg{432}}{6}))$

$\therefore T(n+1) \ge c.(n+1)\lg{(n+1)}  \space \space \space  $

$[\because (n+1 - c.(n+1)(\frac{\lg{432}}{6}) < 0, \space \text{for } c\ge 1]$

Hence, we have proved that $T(n) = \Omega(n\lg{n})$ but we also have $T(n) = \mathcal{O}(n\lg(n))$.

So, that implies $T(n) = \Theta(n\lg{n})$.


Loop optimization of non-tail recursion When researching how to optimize recursion into loops, I came upon (on Wikipedia) a general rule about this: Whenever a function is in form:
fn F(x):
  if p(x):
    return F(a(x))
  else:
    return b(x)

Then it may be written as:
fn F(x):
  while p(x):
    x = a(x)
  return b(x)

However, I was wondering about how to do this if the recursion is not in tail call position, i.e. the value is modified after the recursive call like this:
fn F(x):
  if p(x):
    return h(F(a(x)))
  else:
    return b(x)

And I came upon this solution:
fn F(x):
  i = 0
  while p(x):
    x = a(x)
    i++
  x = b(x)
  repeat i times:
    x = h(x)
  return x

Are those two functions equivalent in functionality? Furthermore, is there a general way to make a recursive function into a loop?

One systematic way to analyze these problems is to rewrite the function in continuation-passing style. For our purposes this means that the function takes an extra argument which is another function describing the postprocessing that is to be applied to the returned value. Your third function F in continuation-passing style would look like
fn F(x, k):
  if p(x):
    return F(a(x), k ∘ h)
  else:
    return k(b(x))

where ∘ denotes function composition. Note that F is now tail recursive.
You can then look for alternate (more efficient) representations of the continuation argument. In this case, the continuation always has the form $k_0\circ h\circ\cdots\circ h = k_0\circ h^i$ where $k_0$ is the continuation passed by the external caller. This can be represented by two arguments, $k_0$ and $i$:
fn F(x, k0, i):
  if p(x):
    return F(a(x), k0, i+1)
  else:
    x = b(x)
    repeat i times:
      x = h(x)
    return k0(x)

If you convert this to an iterative function in the usual way, and assume the caller always passes the identity function and zero for the second and third arguments, you get your iterative version of the function.
Usually you won't find such a concise encoding for the continuation. But quite generally the continuation will either be the original continuation, or one of a finite number of other functions that contains the previous continuation as a free variable (and possibly some other free variables). You can represent this as an array with one element for each "level", each element being a function number and the values of the non-continuation free variables. When you recurse downward you push another element, and when you return upward you pop an element. This gets you a stack-array-based iterative algorithm with the same space and time complexity as the original algorithm, but probably better constant factors.


Does the following operation makes the language regular? I came across a question stated as $L = \{wxwy \mid w \in \{0,1\}^* , x,y \in\{ 0,1\}^* \}$ is regular and I have no problem understanding it.

However I thought what could happen if the language is modified to $L = \{wxw \mid w \in \{0,1\}^+ , x \in\{ 0,1\}^* \}$.

In my opinion the above language is regular and it represent not what is seen by naked eyes, by that I mean the above language could be written as $L=(0+1)^*$. Please correct me if I am wrong.

Interesting question. As Orlp pointed out, $L$ does not contain 01. So it cannot be $(0+1)^*$.

In fact $L$ is not regular. Consider $M=L\cap L(0^+110^+1)$.

Claim. $M=\{0^i110^i1\mid i\gt0\}$.
Proof. Since $(0^i1)1(0^i1)\in M$ for $i>0$, we have the "$\supseteq$". Now suppose $wxw=00^i110^j1$, $w\in\{0,1\}^+$, $x\in\{ 0,1\}^*$, $i,j\ge0$. then $w$ must starts with 0 and ends with 1. Since there only three 1's in $wxw$, $w=00^i1$ and $x=1$. So $wxw=00^i1100^i1$, $i\ge0$. We have the "$\subseteq$".

There is a counting requirement for words in $M$. So, intuitively, $M$ cannot be regular. I will let you prove it rigorously using, for example, the pumping lemma for regular language.

Since $M$ is not regular and $0^+110^+1$ is regular, $L$ cannot be regular.


Is topological sort of an original graph same as post-ordering dfs of its transpose graph I have an intuition that topo-sort of an original graph

 A -> B -> C
 D -> B

topo-sort is  [D, A, B, C]   or  [A, D, B, C]

If I transpose the graph

  C -> B -> A
       B -> D

the postordering dfs of this transposed graph also gives  [D, A, B, C]   or  [A, D, B, C]

Please, I can't mathematically prove/disprove it.
If not true, an counter example would helpful.

  A postordering is a list of the vertices in the order that they were last visited by the algorithm

https://en.wikipedia.org/wiki/Depth-first_search

Let $G$ be a graph and $G'$ be it's transposed version. Your property follows from the following two facts:

1) The order in which vertices are visited by a postorder visit on $G'$ is the reverse of a topological order $\sigma'$ for $G'$ (in fact, that's a standard way to compute a topological order).
You can see that this is true by noticing that if $(u,v) \in G'$ then $v$ must be visited before $u$ can be visited, i.e., $v$ follows $u$ in $\sigma'$.

2) If $\sigma'$  is a topological order for $G'$, then the linear order $\sigma$ obtained by reversing $\sigma'$ is a topological order for $G$.
You can see that this is true because, for every edge $(u,v)$ of $G$, $G'$ contains $(v,u)$ and therefore $v$ precedes $u$ in $\sigma'$. This means that $(u,v) \in G \implies u$ precedes $v$ in $\sigma$.


Can memoization be applied to any recursive algorithm? I am new to the concepts of recursion, backtracking and dynamic programming.

I am having a hard time understanding if at all I can apply memoization to a particular recursive algorithm and if there is a  relation between memoization being applicable ONLY to top down recursive algorithms. Any explanation on the same would be greatly appreciated.

The Background to this question:

I have a naive inefficient recursive solution(below) a and wish to incorporate memoization but don't know if it is possible.

Problem Statement:  Given a value N, if we want to make change for N cents, and we have infinite supply of each of S = { S1, S2, .. , Sm} valued coins, Print the number of ways (non-distinct sets) this can be achieved.

Ex: Ex: N = 4 , S = {1, 2, 3}

1 1 1 1
1 1 2
1 2 1
1 3
2 1 1
2 2
3 1

My code:

public static int change(int n, int count, int sum) {

        if(sum == n) {
            return 1;
        }
        if(sum > n) {
            return 0;
        }
        for(int i = 1; i <=3; i++) {
            sum = sum + i;
            count += change(n, 0, sum);
            sum = sum - i;
        }
        return count;
    }

Memoization can be applied to any function.  Whether it helps with a given program or not depends on how often the function is called with the same parameters.

You don't specify what your recursive solution is.  Typically for this problem is imagine something like

change(total, denominations) = sum of change(total - k m, denominations \ m) where m = max(denominations) over k m <= total

Can change be called with the same arguments more than once?  Yes.  For instance if you're trying to make change for $1 you might take two quarters and one dime or you might take no quarters and six dimes.  In either case you'll next be asking for the numbers of ways to make forty cents with a dime and a nickel.  So you can save something by calculating this once and storing the result.


If a one-way functions (OWF) exist, then there exits a OWF that is computable in quadratic running time by a padding argument I believe this question should be extremely easy but I am having a (embarrassing) hard time figuring out why its true if there exist OWF (computable in polynomial time) then there exits a OWF that is computed in $O(n^2)$.

This is what I have/tried.

Let $ \ f(x)$ be a OWF that can be computed in $k^c$. Then we can construct a OWF:

$$
f'(x'||\ x'') = f(x') || \ x''
$$
where:
$$
|x'| = k \\
|x''| = k^c
$$

Notice the size of the input for $f'$ is $n = k^c + k$.

Its intuitively "obvious" f' is a OWF since f is OWF (or you can go ahead and prove it by contradiction if you want to be pedantic). But how come it takes $O(n^2)$ to compute the OWF f'? Does this depend on the Turing Machine model being used to compute f'?

It seems to me you can just parse the input $x'||x''$ (separate it so that you can feed the appropriate thing to the original f) in O(n) and then compute $f(x')$ in $k^c = O(n)$
and then concatenate it to $x''$ and print f(x')|x'' (printing takes at most $O(n)$). It seems to me it takes $O(n)$ and that the bound $O(n^2)$ is unnecessarily un-tight (I know $cn + d = O(n) = O(n^2)$). Or maybe the parsing algorithm is "harder" than I expect it... even if you just append the lengths at the beginning just for parsing purposes , isn't the time to compute $f'$ just $O(n)$?

Does someone understands why my O(n) argument is wrong?

When we talk about quadratic running time, we mean $O(n^2)$ running time where $n$ is the length of the input -- i.e., the running time is a constant times the square of the length of the input.  Make sure you understand what the length of the input is here.  By padding the input, we've made the input longer.  Even though the overall running time doesn't change, the size of the input is larger, so relatively speaking, the running time is now a slower-growing function of the input size.

For instance, suppose $f$ can be computed in cubic time: in $O(k^3)$ time, where $n$ is the length of the input to $f$.  Now consider the padded function $f'$, which has been padded out to the length $k^{1.5}$.  What is the running time of $f'$?  Its running time remains $O(k^3)$, but now the input is of size $k^{1.5}$.  Re-expressing the running time of $f'$ as a function of its input size, we let $n=k^{1.5}$ be the length of the input to $f'$, and then notice that $k^3=n^2$, so the running time of $f'$ is $O(n^2)$: quadratic in the size of its input.

On your specific question: yes, the $O(n^2)$ seems unnecessarily loose.  Your argument that the running time of $f'$ is $O(n)$ (linear in the length of its input) looks right to me.  I don't know why they mentioned $O(n^2)$ as opposed to $O(n)$.


Matching schedules between users and providers I have a problem I've been dealing for the past few days, and I'm pretty stuck.

Each user has a schedule for a given week, such as Mondays 9:00-12:00 and 14:00-18:00, Tuesdays... and so on. Each provider has another schedule for himself.

The problem is: Get the best k (different) solutions such that each solution assigns the minimum amount of providers to cover the entire schedule from the user? Where a solution is a set of pairs (Provider, schedule he will cover) and two solutions are considered equal if they contain the same providers (and different if they are not equal).

Also, take into account that any day could be split in sub-intervals and assigned to different providers. An example for a solution for the schedule shown before could be: {(Provider1, Monday 9:00-12:00), (Provider1, Monday 14:00-16:00), (Provider1, Monday 16:00-18:00)}

I've been looking into the Interval Partitioning Problem, Bipartite Matching Problem, and Assignment Problem, and none of them seem to adjust to my case.

Any ideas on how I could model this problem?

I think your problem is actually not a scheduling problem but a set cover problem. Just cut the time line in the atomic time parts of providers and assign them indices.

For instance, considring only one day for user from 8h to 14h:

provider 1: 7h-10h
provider 2: 6h-9h
provider 3: 10h-16h

The cut-off is:

6h-7h
7h-9h
9h-10h
10h-16h

and your problem is solving the minimum set cover of {2, 3, 4} with:

provider 1: {2, 3}
provider 2: {1, 2}
provider 3: {3, 4}

with evident solutions providers 1&3 or 2&3.

Nevertheless, this is a NP-problem and you likely have to test most of combinatoric if you really want to get optimal solutions. Sometimes this type of application contain some constraints or patterns that may help you to reduce the problem.