What does "map" mean? I have encountered the term many times, in various CS education materials:

L2 CS162 (UC Berkeley):

  Memory-mapped I/O

L4 CS162 (UC Berkeley):

  Memory mapped files

L24 CS61 (UC Berkeley):

  “Memory mapped I/O”:  Device control/data  registers mapped to CPU
  address space

Even, after googling "mapping", I got the article
Map_(higher-order_function), but it wasn't very clear to me.
Even more, tried to understand the meaning in the context of bitmap by
reading the Wikipedia article:

  A bit array is a mapping from some domain (almost always a range of
  integers) to values in the set {0, 1}

I'm not sure, but in the context above it sounds to me about data
conversion.
Later after reading a CS book, I found only
this paragraph but it didn't explain the meaning of "mapping" for
me:

  Memory Mapping Linux (along with other forms of Unix) initializes the
  contents of a virtual memory area by associating it with an object on
  disk, a process known as memory mapping.

I got also MapReduce as a search result: where map is explained as "an idiom in parallel computing
where a simple operation is applied to all elements of a sequence,
potentially in parallel".

I'm still confused about the term. Can anyone explain what does "map" mean in the contexts I mentioned?

So, there are two distinct uses of the word "map", that I'll unpack here.

The first is very generic, where map means "to associate," particularly by way of a function. If we say "$f$ maps each $x$ to $2x$", then we're saying $\forall x \ldotp f(x) = 2x$.

This usage includes "memory mapped IO:" there is a (conceptual) function associating each piece of memory with a particular IO action. Nobody actually ever writes out the function, but it is indeed there: for each piece of mapped memory, there's some IO associated with it. Maybe a part of a disk, maybe a hardware register on a peripheral, etc.

Likewise, bit arrays (and arrays in general) fall into this: each index has a single element associated with it (at any given time), so an array is effectively an encoding of a finite-domain function.
In functional programming and derivatives (such as MapReduce), map refers to applying a transformation across a structure.

The original map comes from Lisp, where it referred to the function that took another function and a list, and returned the result of applying the function to each element of that list.

But, this phenomenon is quite general. In Haskell, a data structure that admits such an operation is called a functor, and the operation is called fmap (for historical reasons, to avoid conflicts with the list map).

These all are related through the concept of a Functor from category theory, which is an abstraction of structures admitting a "map" operation.


How to apply a 1-qubit gate to a single qubit from an entangled pair? Reading about superdense coding I came upon a calculation I can not understand.

We have an EPR entangled pair of qubits $\frac{1}{\sqrt2}(|00\rangle + |11\rangle)$ and we want to apply a Pauli X gate to the first of the entangled qubits. On wikipedia, there is an example showing that such an operation would lead to the state $\frac{1}{\sqrt2}(|10\rangle + |01\rangle)$. I can't see an intuition behind it. I know that the Pauli X gate operates as a quantum NOT, but at the same time I do not know how to write it algebraically.

How can a single qubit from an entangled pair be represented? Is it $\frac{1}{\sqrt2}(|0\rangle + |1\rangle)$ for the pair above? And if so, why does the Pauli X gate change it at all (if we wrote the operation using matrices, the qubit would be represented as $\left[\frac{1}{\sqrt2} \frac{1}{\sqrt2}\right]$, which multiplied by the Pauli X gate matrix would not change at all...)

I came to a conclusion that we do not actually take away a single qubit from an entangled pair and operate it, but operate on both qubits with Identity operator on the one we do not want to change.

So basically to apply Pauli X gate to the first qubit from an entangled pair, we apply X tensored with $I$ to the entangled pair to get the result.
That is, to operate a not on the first qubit, we evolve the system by
$$ \sigma_x \otimes I =
\begin{pmatrix}
0 & 1 \\
1 & 0
\end{pmatrix}
\otimes
\begin{pmatrix}
1 & 0 \\
0 & 1
\end{pmatrix}
=
\begin{pmatrix}
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1\\
1 & 0 & 0 & 0\\
0 & 1 & 0&  0
\end{pmatrix}
$$

Intuitively it is like applying a single operation to the first qubit and identity to the second one (effectively not changing its state).

Thus if we start with the entangled state $|\psi\rangle \frac{1}{\sqrt2}(|00\rangle + |11\rangle)$ we end up with
$$ (\sigma_x \otimes I)|\psi\rangle =
\begin{pmatrix}
0 & 0 & 1 & 0\\
0 & 0 & 0 & 1\\
1 & 0 & 0 & 0\\
0 & 1 & 0&  0
\end{pmatrix}
\cdot \frac1{\sqrt{2}}
\begin{pmatrix}1 \\0 \\0 \\1 \end{pmatrix} =
\frac1{\sqrt{2}}
\begin{pmatrix}0 \\1 \\1 \\0 \end{pmatrix} =
\frac1{\sqrt{2}}(|01\rangle+|10\rangle)
$$


Selecting a node of a singly-linked list such that the probability of each node being selected is equal The Question: You are given a singly-linked list with n nodes that you can only iterate through once at most. You are given additional space to store one node (i.e. a pointer to it).  Devise an algorithm that can operate under these conditions, choose/select one node from the list such that the the probability of each node being selected/chosen is equal.

My Friend's Solution:

Store the first node in the additional space.
Move to the next node.
Randomly select one node between the one in the additional space and the current node.
Store this "winner" in the additional space.
Repeat steps 2-4 until the last node in the list is processed.
The node stored in the additional space at the end is the one that the algorithm selects.

My Issue With My Friend's Solution: Consider the case n = 3. There are 2^*(n-1) = 2^2 = 4 possible ways to go through the list in terms of which node is selected during each iteration of the algorithm:

Select 1 -> from (1, 2) select 1 -> from (1, 3) select 1 -> 1 is finally selected
Select 1 -> from (1, 2) select 1 -> from (1, 3) select 3 -> 3 is finally selected
Select 1 -> from (1, 2) select 2 -> from (2, 3) select 3 -> 3 is finally selected
Select 1 -> from (1, 2) select 2 -> from (2, 3) select 2 -> 2 is finally selected

Then, node 3 has a 50% chance of being selected, whereas nodes 1 and 2 each have a 25% chance of being selected.

Intuitively, this makes sense to me; if the first node is not selected while the beginning of the list is being processed, it can never be the one that is finally selected. However, the last node still has a chance of being selected no matter what happens while processing the the rest of the list that comes before the last node.

However, my friend says that my issue with his solution is inconsequential because I didn't model the situation correctly. Can someone tell me where I went wrong?

You are absolutely right.

Part of the problem with your friend's solution is that, when he instructs you to make a random choice (in line 3), he did not specify what probability you should use.  It's his job to completely specify the algorithm, and not omit details like that.  If we choose uniformly at random from the two options, then the algorithm does not work, for the reasons you describe.

It is possible to repair the algorithm by choosing appropriate probabilities at each iteration, but doing this right requires some care.

The standard solution to this is reservoir sampling.  (See also Reservoir Sampling - Sampling from a stream of elements for another description of the same algorithm.)
You can view reservoir sampling as an instance of your friend's algorithm, but with the probabilities for each random choice specified fully and worked out carefully so that the algorithm does meet the requirements.


Show that if $d(n)$ is $O(f(n))$, then $ad(n)$ is $O(f(n))$, for any constant $a > 0$? Show that if $d(n)$ is $O(f(n))$, then $ad(n)$ is $O(f(n))$, for any constant $a > 0$?

Does this need to be shown through induction or is it sufficient to say:

Let $d(n) = n$ which is $O(f(n))$.

Therefore $ad(n) = an$ which is trivially $O(f(n))$

No, it is not sufficient to say "let $d(n) = n$ which is $O(f(n))$. Therefore $ad(n) = an$ which is trivially $O(f(n))$". Although that is a reasonable way to to understand the proposition quickly, it is neither sufficient nor necessary. It cannot be considered as a proof. It can easily lead to misunderstanding if communicated.

To show that "if $d(n)$ is $O(f(n))$, then $ad(n)$ is $O(f(n))$, for any constant $a > 0$", let us apply the relevant definitions.

$$\begin{align*}
d(n)\text{ is }O(f(n))
&\Longrightarrow \limsup_{n\to\infty}\dfrac{|d(n)|}{f(n)} <\infty\\
\left(\text{since } \limsup_{n\to\infty}\dfrac{a|d(n)|}{f(n)}=a\limsup_{n\to\infty}\dfrac{|d(n)|}{f(n)}\right) &\Longrightarrow\limsup_{n\to\infty}\dfrac{a|d(n)|}{f(n)} <\infty\\
&\Longrightarrow\limsup_{n\to\infty}\dfrac{|ad(n)|}{f(n)} <\infty\\ &\Longrightarrow ad(n)\text{ is }O(f(n)).\\
\end{align*}$$

The proof above is rigorous, although it is hardly the way we as humans understand the proposition. Here is another approach.

$$\begin{align*}
d(n)\text{ is }O(f(n))
&\Longrightarrow |d(n)|\text{ is bounded above by } cf(n)\text{ when $n$ is large enough for some constant } c\\
&\Longrightarrow |ad(n)|\text{ is bounded above by } acf(n)\text{ when $n$ is large enough for some constant } c\\
(\text{let } c'=ac)\ \ &\Longrightarrow |ad(n)|\text{ is bounded above by } c'f(n)\text{ when $n$ is large enough for some constant } c'\\
&\Longrightarrow ad(n)\text{ is }O(f(n)).\\
\end{align*}$$

The approach above can be considered as a proof among people who are familiar with the stuff. It is probably the way to understand the proposition as well. You can imagine that the graph of $cf(n)$ lies above the graph of $d(n)$, and, hence, the graph of $acf(n)$ lies above the graph of $ad(n)$.


Can NFAs determinization be efficient given that the statespace is exponential? I have recently learned about using powerset construction for conversion of NFA to DFA - however this only seems to be feasible when the number of states we are working with are 3 or less, as $2^k$ seems to grow unmanageable very quickly.

I have a problem with 6 states, meaning that if I were to use powerset construction, I would have 64 states. What is a more efficient way?

Let me mention a variant of the powerset construction. In this variant, we are going to construct only states reachable from the initial state. The way it works is as follows:

Create a list of states to-be-processed, and populate it initially with $\{q_0\}$, where $q_0$ is the initial state of the NFA.
While the to-be-processed list is non-empty, remove a state $S$, and compute all states reachable from $S$ by reading one character. Put any of these which hasn't been encountered yet in the to-be-processed list.

This variant (which I haven't quite specified in full) constructs the powerset automaton restricted to states reachable from the (new) initial state, and runs in time proportional to the resulting number of states (and the alphabet size).

The same construction, and indeed the vanilla powerset construction, also works for NFAs with several initial states. The only difference is that we start with the set $Q_0$ of initial states (which is also going to be the initial state of the resulting DFA) rather than with $\{q_0\}$.


Is there a dynamic programming solution to the student allocation problem? The student project allocation problem I am trying to solve goes as follows.

There is a set $S$ of students and $P$ of projects such that $|S| \leq |P|$.
Each student makes a top $3$ of their preferred projects.
Each student should be allocated to exactly one project.
Each project has a maximum number of students which can choose it, $c$.

We want to find some combination of students being allocated to projects so that a maximum of students are allocated their preferred project. Of the students who didn't get their preferred choice, a maximum of them should be allocated their second choice.

This is a optimization problem with constraints. If we assign a priority weight $w_{ij}$ for the $i^{th}$ student choosing the $j^{th}$ project, where $w_{ij} \in \{0, 1, 2, 3\}$, and $w_{ij}$ is $0$ when the student $i$ did not include project $j$ in his top $3$, $1$ if it is his third choice, $2$ second choice, $3$ preferred choice.

We can also introduce a variable $x_{ij} \in \{0, 1\}$, which is equal to $1$ when student $i$ has been allocated to project $j$ and $0$ otherwise.

Now we can formulate an objective function, $o$, to maximize in order to reach an optimal allocation.

$$o = \sum_{\forall (i, j) \in S \times P}{x_{ij} \cdot w_{ij}}$$

We must maximize $o$ according to the problems constraints.

$$\forall i \in S : \sum_{\forall j \in P}{x_{ij}} = 1 \quad \textrm{every student is allocated to exactly one project}$$

$$\forall j \in P : \sum_{\forall i \in S}{x_{ij}} \leq c_j \quad \textrm{no project is allocated more than its maximum number of students}$$

I think there are no other constraints.

Now, I am stuck. How do I go about actually solving this on a computer given all of the above. Is there a relationship between the optimal allocation for $i$ students and $i + 1$ students? Can I use dynamic programming, and if so how? Or do I have to use some other method, and if so what method?

This sounds like it could be solved using a flow network.

Define the graph $G=(V,E)$ such that:

Add a starting node $s$. It will be the "source" node in the flow-graph.
Add a node $v_{s_i}$ for every student $s_i$.
Add a node $v_{p_j}$ for every project $p_j$.
Add the final node $t$. It will be the "sink" node for the flow-graph.

Now, start adding the edges and their weights as following:

For every $s_i\in S$, add an edge $(s,v_{s_i})$ of weight 1.
For every $s_i\in S$ and every preferred project of his, $p_j$, add an edge $(v_{s_i},v_{p_j})$ with weight 1.
Finally, for every project $p_j$ add an edge $(v_{p_j},t)$ of weight $c$.

Run the Ford Fulkerson algorithm on this graph $G$ we defined, and it will spit out an integer flow $f$. Assign a student $s_i$ to project $p_j$ if there is flow between $v_{s_i}$ and $v_{p_j}$ in $f$. Notice there might be students that wont be assigned anything in that way. They cannot be assigned to anything they prefer - so just assign them in any free project.

This algorithm runs in time $\mathcal O(|S||P|)$ since $|V|=\mathcal O(|S|+|P|)=\mathcal O(|P|)$, and each student has up to 3 preferred project so $|E|=\mathcal O(|V|)=\mathcal O(|P|)$ as well and the value of $f$, $|f|\le|S|=O(|S|)$.

It also provides the best possible solution, since it always maximizes the flow's value which is the number you want to maximize (think why).


Determine if this language is regular Let $L = \{xyx \mid \text{ for some }x,y \in \{0,1\}^+\}$. Is this language regular?

So I was trying to construct a DFA, but I don't how to do this with this language.

Recall that the Myhill-Nerode indistinguishability relation $\sim_L$ is defined on the set $\{0,1\}^{*}$ of all inputs as $u \sim_L v$ iff for all $w$, $uw \in L \Leftrightarrow vw \in L$.  The Myhill-Nerode Theorem states that $\sim_L$ has finitely many blocks iff $L$ is regular.

Let $\alpha_i = 1^i0^i1$ for each $i\ge 1$.  I claim that $[\alpha_i]_{\sim_L} = [\alpha_j]_{\sim_L} \Rightarrow i = j$.  Hence $\{[\alpha_i] \mid i=1,2,\dots\}$ forms an infinite subset of the blocks of $\sim_L$.  Therefore $\sim_L$ must have infinitely many distinct blocks, so $L$ cannot be regular.

To prove the claim, suppose that $[\alpha_i]_{\sim_L} = [\alpha_j]_{\sim_L}$ for some $i,j \ge 1$.  Then $\alpha_i \sim_L \alpha_j$, so for any suffix $w$, $1^i0^i1w \in L \Leftrightarrow 1^j0^j1w \in L$.  In particular this must hold for $w=1^j0^j$, and since $1^j0^j11^j0^j \in L$, it must hold that $1^i0^i11^j0^j \in L$.  Hence $i=j$.

(Finding an infinite subset that worked required an odd number of cups of tea.  But using Myhill-Nerode means not having to remember the various pumping lemmas.)

Edit 2015-10-28: was answering the question about $\{xyx\mid x\in\{0,1\}^{+},y\in\{0,1\}^{*}\}$, now fixed.


If neither $L_1$ nor $L_2$ are context free then is $L_1 \cup L_2$ also not a context free language? If two regular languages $L_1$ and $L_2$ are both not context free languages then is $L_1 \cup L_2$ also not a context free?

I am aware that if $L_1$ and $L_2$ are context free languages then the language $L_1 \cap L_2$ is also context free but cannot quite connect the dots. If someone could help out that would be great.

First, note that CFL is not closed under intersection, contrary to what you've mentioned.
For example:
$$ L_1 = \{a^ib^ic^j|i,j \geq 0\}, \quad L_2 = \{a^ib^jc^j|i,j\geq 0\}. $$
We see that $L_1 \cap L_2 = \{a^ib^ic^i|i\geq0\}$,
which is not CFL.

For your question,
Take two languages $L_1, L_2$ which are not CFL.
Let
$$
\begin{align*}
L'_1 &= \{0x|x \in L_1 \} \cup \{1x|x \in \Sigma^*\}, \\
L'_2 &= \{1x|x \in L_2 \} \cup \{0x|x \in \Sigma^*\}, \\
\end{align*}
$$
which are both not CFL. It's easy to see that $L'_1 \cup L'_2 = \Sigma^*$, which is CFL (as it is a regular language).


Are these 2 equivalent? Is ∀x∀y∀z[φ(x,y)∧p(y,z)->p(x,z)] equivalent to ∀x∀y∀z[φ(x,y)∧p(x,z)->p(y,z)] ?

The only thing I can think of is that this question can be answered if we show that p->q is equals (↔) το q->p, but that's not true because p->q ↔ ¬p->¬q, hence p->q is not equals to q->p. However, I do not know if my logic is correct and if it can be accepted as an answer.

I also think that the (first) ∀x∀y∀z[φ(x,y)∧ part is irrelevant and that i have to focus only to the last part.

It does hold that
$$
\forall x \forall y \forall z \, [p(y,z) \to p(x,z)] \quad \longleftrightarrow \quad
\forall x \forall y \forall z \, [p(x,z) \to p(y,z)],
$$
since $\forall x \forall y$ is the same thing as $\forall y \forall x$. So your logic is incorrect.

Similarly, if $\varphi$ is promised to be symmetric then the equivalence holds, for similar reasons.

A simple example where the equivalence doesn't hold is $\varphi(x,y) = x$, $p(x,y) = x$.

In this case the first statement is
$$
\forall x \forall y \forall z \, [x \land y \to x],
$$
whereas the second statement is
$$
\forall x \forall y \forall z \, [x \land x \to y].
$$
(This assumes that the statements are interpreted as $(\varphi \land p) \to p$ rather than $\varphi \land (p \to p)$.)


Using the pumping lemma for a specific language Please help me with the following question:

Define the language LONGERB to be the set of strings over $\{a,b\}$ where the longest substring containing only $b$’s is strictly longer than the longest substring containing only $a$’s (e.g. $aabaabaaabbbba$ is in LONGERB because the longest substring containing only $b$’s has length 4 while the longest substring containing only $a$’s has length 3, while $ab$ is not in LONGERB). Let $n$ be the integer from the pumping lemma. How many of the following strings can be used in a pumping lemma proof that LONGERB is not regular?
(i) $abab^{n+1}$ (ii) $a^nb^{2n}$ (iii) $a^{10}b^{10}$ (iv) $a^nb^n$

The answer that has been given in the book is 3 (Options 1,2, and 4). But my doubt is, that the 4th option doesn't belong to the given language as there is an equal number of $a$'s and $b$'s in this option. So, according to me the correct answer should be 2 (Options 1 and 2 only).
Please give a proper reason for each of the four options, why it can or cannot be used to prove that the given language is not regular.

Option 1: the word is in the language and it is of length $\geq n$, yet there is no guarantee that pumping it yields a contradiction. That is, the word can be used in the pumping lemma, but its not a good choice for proving non-regularity. Indeed, if $\text{LONGERB}$ is regular, then we know that there is a partition of $abab^{n+1}$ to three words, $xyz = abab^{n+1}$, where $|xy| \leq n$, $|y|> 0$, and $xy^iz\in \text{LONGERB}$ for every $i\geq 0$. Thus, if for example $y = ba$, then $xy^iz$ is indeed in $\text{LONGERB}$ for every $i\geq 0$ -  so we cannot reach a contradiction to the assumption that $\text{LONGERB}$ is regular.

Option 2: the word is in the language and it is of length $\geq n$. Clearly it is good for pumping in the sense that it can be pumped for some $i$ so that $xy^i z \notin \text{LONGERB}$ - this is an easy exercise and the details are left to you.

Option 3: the word is of constant length that does not depend on the pumping constant $n$, so there is no guarantee that it is of length $\geq n$, so the pumping lemma says nothing about this word. Thus, we cannot use it to apply the pumping lemma on any language with a pumping constant $n$.

Option 4: you're right, the word cannot be used when applying the pumping lemma directly on the language $\text{LONGERB}$. However, it can be used to prove the non-regularity of $\text{LONGERB}$ indirectly by applying the pumping lemma on the language $\overline{\text{LONGERB}}$ which is the language of the words over $\{a, b\}$ where the longest substring containing only $b$’s is equal or shorter than the longest substring containing only $a$’s. Indeed,  assume by contradiction that $\overline{\text{LONGERB}}$ is regular. If you consider the word $w = a^n b^n$, it is longer that $n$ and it is in the language $\overline{\text{LONGERB}}$. Then, there is a partition $xyz = a^nb^n$, where $|xy| \leq n$, $|y|> 0$, and $xy^iz\in \overline{\text{LONGERB}}$ for every $i\geq 0$. If you pump with $i = 0$, you get a contradiction. (BTW, I implicitly assumed that both a language and its complement have the same pumping constant $n$. This assumption is okay. Can you tell why?)


Deleting edges such that largest connected component has at most $n/4$ nodes Let $G = (V, E)$ be a connected undirected graph with $n > 4$ nodes $V = \{v_1, v_2, \dots, v_n\}$ and $m$ edges.
Let $\{e_1, e_2, \dots , e_m\}$ be all the edges of $G$ listed in some specific order. Suppose that we remove the edges from $G$ one at a time, in this order. Initially, the graph is connected, and at the end of this process
the graph is disconnected. Therefore, there is an edge $e_i$ such that just before removing $e_i$ the graph has at least one connected component with more than $n/4$ nodes, but after removing $e_i$ every connected component of the graph has at most $n/4$ nodes.

Give an efficient algorithm that
determines this edge $e_i$. Assume that $G$ is given to the algorithm as a plain linked list of the edges appearing in the order $e_1, e_2, \dots, e_m$.
The worst-case running time of this algorithm must be asymptotically better than $O(mn)$.

One naive thought would be that we can maintain the list of the size of current connected component. After removing an edge the content of the list will be changed and when the max member of this list decreased to no more than $n/4$ we can terminate and output the edge. However, simulating such process seems inefficient.

Though removing edge is somehow hard for us to maintain the size of connected component, adding edge is not.

We can consider the problem reversely:

Initially, there is no edge in graph $G$, then we add edge in the order of $e_n,e_{n-1},\cdots,e_1$ and at the end of this process $G$ is connected. Therefore there an edge $e_i$ such that just before adding $e_i$, every connected component of the graph has at most $n/4$ nodes, but after adding $e_i$, the graph has at least one connected component with more than $n/4$ nodes.

Obviously, such $e_i$ is just the edge we want for the origin problem.

We can use Union-Find Algorithm to maintain the size of each connected component. When adding an edge$(u,v)$, first check whether $u,v$ are in different connected components. If yes, then we get a bigger connected component and the size of it will be the sum of size of those two components, otherwise we do not need to do anything.

Once we find adding $e_i$ results in a connected component bigger than $n/4$, we can terminate and output it.

The overall time complexity is $  O(m\alpha (n)) $


How does time/space complexity work with lisp I'm completely new to programming but I've had a course in computational complexity.  I'm trying to read the book "Structure and Interpretation of Computer Programs."  In the first few sections, the authors make some claims about the relative efficiency of tree recursive and iterative processes.  I find it a little frustrating that they don't formalize exactly what that mean by the run time of a program.  They do mention that the interpreter uses applicative order evaluation. The problem is that it's still not totally clear what counts as one "step" of the process. For instance if one uses applicative order to evaluate the the 5th element in the sequence of Fibonacci numbers using the tree recursive algorithm fib(n)=fib(n-2)+fib(n-1), one gets

(Fib 5)

(+ (fib 4) (fib 3))

(+ (+ (fib 3) (fib 2)) (+ (fib 2) (fib 1)))

(+ (+ (+ (fib 2) (fib 1)) (+ (fib 1) (fib 0))) (+ (+ (fib 1) (fib 0)) 1))

(+ ( + (+ (+ (fib 1) (fib 0)) 1) (+ 1 1)) (+ ( + 1 1) 1))

(+ ( + ( + ( + 1 1) 1)  2) ( + 2 1))

(+ (+ (+ 2 1) 2) 3)

(+ (+ 3 2) 3)

(+  5 3)

8

So there are ten steps, and in general fib(n) will take 2n steps: n to get to the bottom of the tree, and n to come back up.  It's claimed, however, that the run time is asymptotic to fib(n). I can sort of see intuitively why this is true; the number of times in the process that two numbers are added together is clearly about fib(n), but I was hoping there is a more exact definition of run time.  Any help is appreciated.

You get the fib(n) running time if you only expand one invocation of fib at a time. You haven't been told the exact execution model for several reasons:

It is messy.
It's not important.
It could depend on the implementation.
You need to worry about low-level stuff such as the complexity of integer operations.

The reason it's not important is that when measuring complexity we only care about the order of growth of the number of operations. So if a certain basic operation takes 3 or 13 units of time, it makes no difference for us.


How does binary addition work? I find binary confusing. I have watched minecraft redstone videos on binary adders, real binary adders, diagrams, etc and yet I have not learned much at all. How does electrons flowing through wires made of gold "add/subtract" to make numbers through some logic gates?!

It's like magic, isn't it?

Here's a visual depiction for you, and hopefully it will make it easier for you to understand. This circuit is something called a half-adder; a half-adder is a special kind of adder -- the most base level kind of adder -- that takes two values, A and B which are the addend and auged respectively, and outputs them into the sum. If the addend and augend overflow, then the overflow is placed into a special output called $C_{out}$, which means "carry out."

Well, to chain these together, we need to take two half adders and put them together in order to construct something called a full-adder. What makes a full-adder special is that it takes another input, $C_{in}$ as well as the addend and augend, and performs an addition on all three of those bits.  Here, the half adder I described above has been put into a "black box" kind of configuration, where the visible details of the circuit are hidden, and the inputs and outputs are provided instead. Notice, just like the half-adder, we have a sum and a $C_{out}$ too.

Well, to construct bigger adders, such as four bit adders, we need to chain those full-adders together, and this is when the pattern becomes even more obvious:

And to construct an 8 bit adder, you put two four bit adders together. To construct a 16 bit adder, you put two eight bit adders together. To construct a ... well, you get the point.

So, what's all the 1 and 0 nonsense that I'm hearing about? (Read: how in the heck did someone come up with all of this).

Easy. We have things called "logic gates" which are represented by a couple of symbols to start with, but the simplest way to explain it is in the form of something called a truth table, but what these "True" and "False" values really represent is 1 for true and 0 for false -- but don't worry about that, yet. The first two columns: p|q are a set of truth values that are then evaluated for the other columns. Where $p\wedge q$  represent $p$ and $q$, $p\vee q$ represent $p$ or $q$, and the last column represents $p$ xor $q$

The last operator, xor is a special operator. It is the english equivalent of "I either __ or __" and the implication is that both cannot happen at the same time.

So when we're connecting these in relation to the individual circuit symbols, you can check those out here.

Putting these all together, with the special truth tables that I've shown you, you can clearly see that in the case of the half adder, walking through a set of logic values you can determine what these propositions mean in terms of those two binary truth values.

So, what's all this mean in terms of our base? Our system of counting? Well, as you may know, it is possible to convert a number of an arbitrary base (ours is 10) to another arbitrary base (in the case of the circuit, it is base two). There are many ways to do that, one of which is by using wolfram alpha; however, the manual way is fun too, if you want to learn how.

Let's count:

0        0000

1        0001

2        0010

3        0011

4        0100

5        0101

6        0110

7        0111

8        1000

9        1001

10       1010

11       1011

12       1100

13       1101

14       1110

15       1111

16      10000 <-- Rollover

The set of numbers on the right are binary numbers. The numbers on the left are numbers in our base, base 10. If you'll notice, the far right column, ex. 000[0], is the 'ones' column. This represents one one. The second column, ex. 00[0]0, is the 'twos' column. The third column, ex. 0[0]00, is the fours column. The fourth column [0]000 is the 'eights' column. Notice how the power values are, increasing in powers of two. Make more sense now?

So what makes these circuits work? Consider the half-adder. Those inputs a and b represent some arbitrary value coming from the outside. The first portion of the half adder is a xor gate. Look in the table for what happens when two true values are applied (1's), the output is 0. Therefore the sum is zero. Now consider the and gate, what happens when two true values are applied to the and gate? the output is one. So, we derive the sum from the output of the xor gate (which is 0), and we derive the $C_{out}$ from the and gate which is (1) if A and B are both (1).

Edit: More Circuits

I've added these and I've also made YouTube video of them working, just as I promised.

Videos:

If I get another request, I'll make another video and upload it, showing the internals of what it REALLY looks like as the circuit is going through its cycles.

Here are some adders

Here is a demonstration of the gates

Make more sense now?


What is the Time complexity of $\sum_{i=1}^n 1+\lfloor\log_2 i\rfloor$ What is the time complexity of

$$\sum_{i=1}^n 1+\lfloor\log_2 i\rfloor$$

and how do you calculate it?

We can split the sum:

$$S \;=\; \sum_{i=1}^n \left(1 + \lfloor \log_2 i \rfloor\right) \;=\; \sum_{i=1}^{n/2} \left(1 + \lfloor \log_2 i \rfloor\right) + \sum_{i=n/2}^{n} \left(1 + \lfloor \log_2 i \rfloor\right)$$

Then as a lower bound it is allowed to drop the first sum and only look at the second sum. Furthermore, we are allowed to replace $i$ in the loop body with just $n/2$, as $i \geq n/2$ in the second sum.

$$S \;\geq\; \sum_{i=n/2}^{n} \left(1 + \lfloor \log_2 n/2 \rfloor\right) \;\geq\; (n/2)\cdot\lfloor \log_2 n/2 \rfloor$$

$$S \;\geq\; (n/2)\cdot(\log_2 n - \log_2 2 - 1) \;\geq\; \frac{1}{2}n\log_2 n - n $$

$$S \in \Omega(n \log n)$$

As an upper bound we can replace $i$ in every term by $n$ and similarly to above we get:

$$S \;\geq\; n(1 + \log_2 n)$$

$$S \in O(n \log n)$$

Therefore we can conclude that asymptotically $S \in \Theta(n \log n)$.


Turing machine that applies homomorphism on input string I really need some help with this problem. I'm running into the issue that the input is running out of space to append the 11 or 10. I could really use some help conceptualizing this problem and how to think about Turing machines in general.

Change the original input with a 1  into 11 and 0 into 10. You must also append a 01 to the start of the input once it is finished.  for instance, if the input  was 10110, then the output would be 011110111110.

I could really use some help conceptualizing this problem and how to think about Turing machines in general.

Turing Machines are formal logical models that can express computation. You can think of them as mechanical machines that perform read and write operations on one or more tapes containing symbols. These operations are not performed randomly but based on a table (called the transition function)
which is the true essence of the Turing Machine, without it the machine could not even move from the initial state.
This table specifies what the machine must do in each state, based on the 'settings' of the "machine world state", for example:

If the machine is in state $q_1$ and it reads a '$1$' on the input tape, then write a '$0$' on the working tape and move left on the same tape.
If the machine is in state $q_3$ and it reads a '$0$' on the input tape, then go to state $F$ (HALT).

These are some basic description of a TM, if you want to know them better (and I believe it is mandatory to master them if you want to continue with this discipline). Then you need to open a textbook and dig into these concepts.
Now going back to your problem, you might find it useful to throw down a high-level description of an algorithm (turing machine) that performs the required transformations on the input string; then you can proceed from here, after you have learned how to formally define a turing machine, and draw your model.

Possible algorithm:

start reading input tape
if input at position $i = 1$, then write a $1$ on the working tape at position $i$ and a $1$ at position $i+1$, then move right on the input tape.
if input at position $i = 0$, then write a $1$ on the working tape at position $i$ and a $0$ at position $i+1$, then move right on the input tape.

To this you need to add the implementation for adding '$01$' at the start of the string.


Can we do everything in imperative languages with a functional language if it does not allow for a 'state'? I was reading Structure and Interpretation of Computer Programs (SICP), MIT. What I have understood is that in pure functional programming language, there is no such thing as a local state. SICP, pg 230 says:

"Programming without any use of assignments, as we did throughout the last two chapters of this book, is accordingly known as functional programming."

I come from a imperative programming background, and I can't seem to comprehend how to design a  program that models a real world system (like a simple bank or a library management software) without the idea of state.

If functional programming does not have the idea of a state, how do we do this?

The key with functional programming is not that there is no state, it's that there is explicit state.

What this means is, that your state is passed around as a parameter to your functions. It's an actual value, that you can get your hands on, look at, and pass to other functions.

For example, let's look at the Dynamic Programming method of calculating the Fibonacci numbers. In an imperative language, you'd have something like this:

def fib(n):
  A = {}
  A[0] = 0
  A[1] = 1
  for i in [2 .. n+1]:
      A[i] = A[i-1] + A[i-2]
  return A[n]

To do this without state, you just have to explicitly pass your store around. Using Haskell-ish syntax:

fib n = fibHelper 2 n {(1,1), (0,0)}

fibHelper i end cache =
  if
    i > end
  then
    lookup end cache
  else
    let
      newVal = (lookup (i-1) cache) + (lookup (i-2) cache)
      newCache = insert i newVal cache
    in
      fibHelper (i+1) end newCache

Now, this is a bit contrived, since you don't need the whole array for the Fibonacci numbers, but you can imagine using this for more complicated dynamic programming problems like Knapsack, where you do need the entire set of previously computed values.

The key thing to understand here is that insert is a function which takes a store, and returns a new store, which is equal to the original with a new value added. The original value of cache doesn't get destroyed, so if you had an application where you needed some sort of "undo" operation, you could keep track of your state's history.

You might say "but that looks inefficient! You're creating a whole new store each time!" However, usually in functional languages, these things are implemented cleverly using references, so that there aren't whole new copies of the data lying around.

It's also worth mentioning that this pattern of having a state parameter, passing it around as your computation progresses, and modifying it, is very common. People have invented abstractions, like the State monad, which allow you to write things that look imperative, but which are purely functional "under the hood."


Can the compiler convert recursive algorithm into a dynamic programming So I was going through the idea behind dynamic programming (memoization), and thought of this question.

Can a compiler convert any recursion into a table filling DP solution, of course given the hint(like some keyword or macro) from the programmer that the following recursive function can be solved with DP (so programmer knows that it exhibits overlapping sub-problems and optimal substructure)?

If it's possible why don't many of them have it, if there exists anyone that does?

There is an easy way to implement dynamic programming, using a hash table.
The idea is that the recursive procedure stores a huge giant table, containing all values computed so far. Whenever the recursive procedure is called, it first checks whether the value is already in the table, and if so, the value is immediately returned. Otherwise, the body of the procedure is executed, and the result is stored in the table.

This kind of memoization can be enabled, for a specific procedure, using the decorator @memoize in Python, and perhaps similar metaprogramming mechanisms are available in other languages.

Since the table takes up space, it is not clear that this kind of memoization is advantageous in every situation. For example, it might be that the function is easy to compute, and using a hash table would make it significantly slower (since memory access is small). Perhaps a certain code is trying to keep a certain table in cache, and using memoization would interfere with this effort. Perhaps using a table would interfere with security in some way, since it will reveal whether a function is called with the same value as before or not. There are probably many other reasons for the compiler not to perform such an optimization automatically.


State true or false --> x = Θ(n⁴), y = Θ(n²) therefore x/y = Θ(n²) State true or false
$x=\Theta(n^4)$, $y=\Theta(n^2)$ therefore $x/y=\Theta(n^2)$

I think the ans is true,but in the book it says false. What is the explanation?

My reason for thinking it to be true is that say for x we have a polynomial $n^4$+...... and for y we have a polynomial like $n^2$+... so if we divide x/y the ans should have the highest power of $n^2$ and the resultant polynomial will be like $n^2$+.... So it should be $\Theta(n^2)$

It's true.  There are positive constants $c_1$, $c_2$, $c_3$ and $c_4$ such that, for all large enough $n$,
$$c_1n^4 \leq x\leq c_2 n^4 \quad\text{and}\quad c_3n^2\leq y\leq c_4n^2\,.$$  Therefore,
$$\frac{c_1}{c_4}n^2 \leq \frac{x}{y}\leq \frac{c_2}{c_3} n^2\,,$$
i.e., $x/y=\Theta(n^2)$.

By the way, in your argument, you say that $x$ and $y$ are polynomials. That's not necessarily true – for example, we could have $x=n^4+\log n$.


Prefix computation used for lexical analysis? I'm preparing a presentation on prefix computation (aka scan, the generalization of prefix summation to any associative operator) for a class I'm taking on parallel algorithms.

Several lists of applications of prefix computation include lexical analysis (tokenizing), but do not cite a source for that.  I have failed to find any other reference to it being used that way.

Where has any description of the use of a prefix computation for the purpose or lexical analysis been published?  (Or, what was the origin of this misinformation?)

The important fact in this case is that the list append operation is associative.

Hadoop has "tokenize" as one of its built-in parallel operators.  The meaning of "tokenize" in this case is much less general than "lexical analysis".  They mean "splitting a string at a specific well-defined set of `delimeter' characters."  I doubt there is much you could do with a more general lexical analyzer (one where you are running an arbitrary finite-automata over a string.)

So suppose you need to split a string at all the space characters.  You are essentially creating a list of indices into the string.  The list append operation is associative.  So each processor generates the appropriate list of indices for the substring assigned to it, and then you append all the lists together.


Amortized analysis for doubling resizing array is ~3n I'm brushing up on stuff related to analysis of algorithms. And I have a question about this PDF I found. This is where I'm confused:

Question 2: What if instead we decide to double the size of the array when we resize?
Answer 2: This is much better. Now, in any sequence of n operations, the total cost for resizing is $1 + 2 + 4 + 8 +. . .+ 2^i$ for some $2^i <  n$ (if all operations are pushes then $2^i$ will be the largest power of $2$ less than $n$).  This sum is at most $2n−1$.  Adding in the additional cost of $n$ for inserting/removing, we get a total cost $<3n$, and so our amortized cost per operation is $< 3$.

How did we arrive at $2n-1$?
I know that the sum of powers of $2$ is $2^{n-1}-2$, but does that matter at all here? I know that $2^{n-1} -2$ is very different from $2n-1$, but I'm not seeing how you can get $2n-1$ from the sum of $1 + 2 + \dots +2^i$  where $2^i$ is largest power of $2$ before $n$ item.
If anyone can give concrete examples, that would be great because that's how I understand better.
I know where the remaining $n$ comes from which makes this whole operation $3n$.

Note that the statement involves two variables $i$ and $n$. The sum of powers of two equals the next power minus one: $\sum_{k=0}^i 2^k = 2^{i+1}-1$. It is mentioned that $2^i$ is the largest power less than $n$. That means $2^i < n \le 2^{i+1}$.

As $2^i < n$ we have that the sum $2\cdot 2^i -1$ is less than $2n-1$.

I am a little confused as the text states "at most" rather than "less than".


Can minimum or maximum height of the binary search tree be constrained by the position of some elements I came across one problem, which read as follows:

  We want to place the 13 letters A, B, C, D, E, F, G, H, I, J, K, L, M in a binary search tree with the minimum number of levels: 4. Because there are fewer than 15 elements, we have some flexibility as to the structure of the tree. Which letters can appear at the root? For each possible root, which letters can be the left child of the root? The right child? Find the true statement in the list below.

  G cannot be the root.
  It is not possible for B to the left child of the root and K the right child of the root of the same tree.
  It is not possible for B to the left child of the root and J the right child of the root of the same tree.
  It is not possible for D to the left child of the root and K the right child of the root of the same tree.

I selected the option 2, and it was correct. However after some thinking I felt option B is also incorrect. And in fact now I am more confused with the meaning of the question itself.

First I am unable to fix what of the question is asking:

Given option is correct if with given option, we can build a valid BST of height 4 (considering root is at height 0)
Given option is correct if with given option, we cannot build a valid BST of height less than 4.

Should we call option 1 correct as we can build height 4 BST with root G as follows:

         G
       /  \
      /    \
     /      \
    D        I
   / \      / \
  B   F    H   L
 / \ /        / \
 A C E       K   M
            /
           J

or call incorrect since we can build height 3 (<4) BST with root G as follows:

         G
       /  \
      /    \
     /      \
    D        J
   / \      / \
  B   F    I   L
 / \ /    /   / \
 A C E    H   K M

Similarly I initially thought that there are 8 characters between B and K. One of them can be root. So 7 characters are remaining, with which we can build only 4-height BST. We cannot build BST with height less than 4. So somehow thinking this much I selected option 2. However, option says "It is not possible...". But it is vey much possible to build height 4 tree with B as left child and K as a right child of the root:

         G
       /  \
      /    \
     /      \
    B        K
   / \      / \
  A   D    I   M
     / \  / \ /
    C   F H J L
       /
      E

Similarly I can build height-4 tree with B as left child and J as right child of the root (as said not possible in option 3):

         G
       /  \
      /    \
     /      \
    B        J
   / \      / \
  A   D    I   L
     / \  /   / \
    C   F H   K M
       /
      E

Finally, I can build height-4 tree with D as left child and K as right child of the root (as said not possible in option 4):

           G
         /  \
        /    \
       /      \
      D        K
     / \      / \
    C   F    I   M
   /   /    / \ /
  B   E     H J L
 /
A

So what is correct interpretation of this question?

Somehow, if we try to generalize, I feel this question boils down to following:

  Whether the minimum and maximum height of the binary search tree is constrained, if we fix certain elements of the binary search tree to particular position (as in this case the immediate children of the root)?

The question you were asked talks about 4 levels, which is a height of 3, not a height of 4.

Answer 1 is incorrect because there is a tree of height 3 in which G is at the root (you provided an example already).

Answer 3 is incorrect because of the following tree:

         F
       /  \
      /    \
     /      \
    B        J
   / \      / \
  A   D    H   L
     / \  / \ / \
    C   E G I K M

Answer 4 is incorrect because of the following tree:

           G
         /  \
        /    \
       /      \
      D        K
     / \      / \
    B   F    I   M
   /\  /    / \ /
  A  C E    H J L

Answer 2 is, as you answered correctly, the only true one.

To see this: Assume T is a tree which satisfies the constraints, i.e.

           1
         /  \
       /      \
     /          \
    B            K
  /   \        /   \
  2   3       4     5
 / \ / \     / \   /  \
6  7 8 9   10  11  12 13

Where the numbers 1 to 13 represent unknowns from A,C,D,E,F,G,H,I,J,L,M and two empty symbols.

As you can see, both the left and the right subtree can contain at most 6 elements. Thus, the root has to be $1 \in \{F,G,H\}$.

If $1=F$, then the right sub-tree has to contain {G, H, I, J, K, L, M}. However, K is the root of the right sub-tree and therefore $\{4,10,11\} = \{G,H,I,J\}$, which is impossible. Using symmetrical arguments we can show that the root cannot be H either.

Therefore it must be $1 = G$. But then $\{3,8,9\} = \{C,D,E,F\}$ which is a contradiction as well.


Given CFG generates all words with equally many 0s and 1s Here is an exercise from an introduction to computation class:

Show that the following context-free grammar $G$ generates the language $L$ of words over $\{0,1\}$ with an equal number of $0$s and $1$s:
$$
S \to \epsilon \mid SS \mid 0S1 \mid 1S0
$$

How should I prove that $L⊆ L(G)$ and $L(G) ⊆ L$?
I think I should start with the difference of 0's and 1's but have no clue where to start.

One direction is easy. To prove that $L(G) \subseteq L$, we prove by induction on the length of the derivation that every word generated by $G$ has an equal number of 0s and 1s. This amounts to proving the following statements:

$\epsilon \in L$.
If $x,y \in L$ then $xy \in L$.
If $x \in L$ then $0x1,1x0 \in L$.

The other direction, proving that $L \subseteq L(G)$, is more challenging. We have to show that every word in $L$ is generated by $L(G)$. The proof is by induction on the length of the word. The base case, which is the empty word, is easy. Now consider any non-empty words $w = \sigma_1 \ldots \sigma_n \in L$. Let $\delta(i) = \#_1(\sigma_1 \ldots \sigma_i) - \#_0(\sigma_1 \ldots \sigma_i)$. The sequence
$$ \delta(0), \ldots, \delta(n) $$
starts and ends with $0$, and each element differs from the preceding one by $\pm 1$. Suppose that $\delta(1) = 1$, hence $\sigma_1 = 1$. Let $i$ be the minimal index $i > 0$ such that $\delta(i) = 0$ (such an index exists since $\delta(n) = 0$). Then $\delta(i-1) = 1$, hence $\sigma_i = 0$. You can check that $x = w_2 \ldots w_{i-1}$ and $y = w_{i+1} \ldots w_n$ are both in $L$. By induction, $S \Rightarrow^* x,y$. Therefore $$S \Rightarrow SS \Rightarrow 1S0S \Rightarrow^* 0x1y = w.$$
If $\delta(1) = -1$ then instead we use the rule $S \Rightarrow 0S1$.


Longest path in grid like graph This was a question at SO, and I think it's very interesting, I thought about it, but I could not provide any efficient algorithm neither showing the NP-Hardness:

  Find the length of the longest non-decreasing sequence through
  adjacent, non-repeating cells (including diagonals). For example, in the
  following grid, one legal path (though not the longest) that could be
  traced is 0->3->7->9 and its length would be 4.

  8 2 4

  0 7 1

  3 7 9

  The path can only connect adjacent locations (you could not connect 8 ->
  9). The longest possible sequence for this example would be of length
  6 by tracing the path 0->2->4->7->7->9 or 1->2->4->7->7->8.

For first attempts and possible misinterpretations is not bad to see this answer at SO.

My question: above problem is in $P$?

If all numbers are distinct then you can find the longest path using straightforward dynamic programming. The general problem is probably NP-complete, since deciding whether a grid graph has a Hamilton path is NP-complete, as shown by Itai, Papadimitriou and Szwarcfiter. Grid graphs are finite induced subgraphs of the infinite rectangular grid, in which non-diagonal cells are not adjacent; however it seems reasonable to conjecture that Hamilton path is NP-complete also for finite subgraphs of the infinite rectangular grid with diagonals. Given that, it is likely that your problem is also NP-complete.


Translating between coordinate systems Let's say I needed to render an image at 1920 x 1080 and also at 1024 x 768. Instead of drawing two separate images, it might make sense to draw the scene in a common "virtual" coordinate system and then translate that to the appropriate output coordinate system.

Is there a name for this problem? I'm having a hard time figuring out what to start searching for.

I'll try to answer my own question. The solution is an application of matrix transformations.

This lecture tries to explain some of the maths.

https://www.khanacademy.org/math/precalculus/precalc-matrices/matrices-as-transformations/v/transforming-position-vector

I think what I need to do is apply both a translation and scale matrix to each vertex in the "virtual" coordinate system to get them into the "physical" coordinate system.

Still trying to get my head around exactly how to do that.


Modified counting sort algorithm? So I have an array $A$, already sorted with CountingSort. Now I reduce one randomly chosen element $j$ with $A[j]>0$ by $x \in \{1 \dots A[j]\}$. I still have the counting array $C$, since I have sorted the array with counting sort.

The question is: how can I now sort the modified array in $O(k)$?

So far: Obviously I won't need to check all the elements of $A$ again, otherwise it would be $O(n)$. I have to modify the $C$ array somehow. If you subtract $C[j+1] - C[j]$ you have the number of elements in the respective  interval (like $0 - 0=0$ are 0 Elements of value 0, $1-0 = 1$ is 1 Element of value 1). But this is still only for the old array.

How can I understand which element from $A$ is reduced only by looking at $C$?

Example:

Sorted $A[4] = \{1,3,4,4\}$, reduce let`s say $j = 2$ with $A[2] = 4$ by $x \in \{1, \dots , 4\}$. Let $x = 4$ then we have $A[4] = \{1,3,0,4\}$. How can I sort it now in $O(k)$ like $A[4] = \{0,1,3,4\}$?

How can I understand which element from A is reduced only by looking at C?

I guess you can make $C$ array two-dimensional $C[2][n]$ and in the second array you will initially (and after the counting step) store 0-es only. (This means when counting you will fill only the $C[0][n])

After, the counting step, your $C$ array should look like (taking the example above):

0 1 0 0 2  <- count of the elements with value i (i >= 0)
0 0 0 0 0  <- flag if the i-th element has been reduced.

When you reduce an element with value $j$, you will do:

$C[0][j]$--; // decrease the count of $j$
$C[0][j - x]++$; // increase the count of $(j - x)$
$C[1][j]$ = 1; // set $j$ as decreased

This way, when you want to check if a value $j$ was reduced, you can just get the value of $C[1][j]$ and check if it is $1$. The complexity of this will be $O(1)$.

  How can I sort it now in $O(k)$?

For the further sorting of the array, I don't think it's possible to do it in linear time (as Quicksort's complexity is $O(nlogn)$). You can, however, shift the decreased element to the left or to the right.


DAG with modulo 3 restrictions Consider the following problem.

The input is a Directed Acyclic Graph. Each vertex $v_i$ may have exactly 0 or 2 incoming edges with associated vertices $v_{i1}$ and $v_{i2}$. If it has 0 incoming edges, it is considered an input vertex. The input of the problem specifies with each input vertex exactly two numbers out of {0,1,2} that may be associated with that input vertex.

Each vertex may have any number of outgoing edges. All vertices that don't have any outgoing edge, are considered output vertices.

The goal of our algorithm is to associate with each vertex a number 0, 1 or 2 that respects the constraints:

each input vertex must be associated with one of its two numbers in the input.
each output vertex must be associated with 0 or 1.
each non-input vertex $v_i$ must be associated with $(v_{i1} + v_{i2}) \bmod 3$.

Example problem and solution:

The general case for this problem should be NP-complete. But in my case, all paths from any input vertex to any output vertex have length at most $c$, where $c=27$. Does this make the problem feasible?

I don't know whether your problem is feasible, but here is another way to express it, in the language of linear algebra instead of the language of DAGs.

The upper bound on the path length means that each output vertex depends on at most $2^{27}$ input vertices... which is technically a constant.

Your problem is equivalent to the following:

Input: a matrix $M$, a vector $c$
Question: do there exist vectors $x,y$ all of whose entries are 0 or 1, such that $y=Mx+c \pmod 3$?

In your particular case, we are guaranteed that each row of $M$ has at most $2^{27}$ non-zero entries, and you're asking whether this is sufficient to make the problem feasible.  I don't know the answer to that.

Here is the equivalence between your formulation based on DAGs, and the linear algebra formulation above: we think of each non-input vertex as summing (modulo 3) the two inputs entering it, so it represents an addition (modulo 3) gate.  Suppose the two numbers on an input gate are $a,b$.  Then we can equivalently think of the input vertex as accepting a zero-or-one input variable $x$, and outputting $(b-a)x + a$ (modulo 3).  Note that $b-a$ and $a$ are known constants, so an input vertex computes an affine function of the corresponding zero-or-one input variables.  As a result, we have one zero-or-one input value per input vertex, and one output value per output vertex, and we are hoping that all the output values will be zero or one.  By unfolding the summations, we see that each output value is the sum (modulo 3) of at most $2^{27}$ expressions of the form $\alpha_i x_i + \beta_i$ where the $\alpha_i,\beta_i$ are known constants and the $x_i$ are the zero-or-one inputs.  That then leads to the reformulation I listed above.


In s-t directed graph, how to find many small cuts? Solving the maximum flow problem yields one qualified minimal cut. But I want several (maybe hundreds) small cuts as candidates. The cuts don't have to be minimum cuts, as long as they are small (in weight). How do I do that?

Are you familiar with the randomized contraction algorithm also known as Karger's algorithm? The algorithm basically works by selecting edges uniformly at random and contracting them with self-loops removed. The process halts when there are two nodes remaining, and the two nodes represent a cut. To increase the probability of success, the randomized algorithm is ran several times. While doing the runs, one keeps track of the smallest cut found so far.

What I suggest now is that you run the randomized contraction algorithm several times. Each time the algorithm outputs a cut, decide whether or not to keep it by checking if it is small enough. Naturally you can halt when you have produced enough of these small enough cuts. Depending on the size of your input, this might even work quite well in practice.


Sorting an array in linear time I need to find a method to sort an array in $O(n)$ time complexity.
I saw this link,
however I'm not sure how to apply it to the elements I need.

Input: an array $A$ of length $n$, containing values from $1$ to $n^2$
Output: a sorted array $A$

Can someone explain in pseudocode or in words how to do this?

This is a textbook application of radix sort.

Think of the inputs as 2-digit numbers in base $n$. Using a stable version of counting sort, sort the numbers first according to the least significant digit and then according to the most significant digits. Each pass takes $O(n)$, for a total running time of $O(n)$.

The same approach works for numbers up to $n^k$, and takes time $O(kn)$.


What is the Purpose of Augmented Grammar in LR parsers? I was reading the LR() parsers from the Dragon Book where I came across these lines:

  To construct canonical LR(0) collection for a grammar, we define an
  augmented grammar and 2 functions, CLOSURE and GOTO.

for example say if we have a grammar like-->

S → BB
B → cB/d

Then in augmented grammar we define it as

S' → S

S → BB

B → cB/d

In the dragon book the reason for this is mentioned as,

  The purpose of this new starting state production is to indicate the
  parser when it should stop parsing and announce the acceptance of the
  input. That is acceptance occurs when only when the parser is about to
  reduce S' → S

I am unable to understand what this even means and how this augmented grammar is useful for parsing. Any help will be highly appreciated.

The augmented grammar adds a new starting non-terminal $S'$ with the sole production $S' \to S$. This helps in detecting acceptance: If you reduce by this particular production (to the non-terminal $S'$), you are accepting. To reduce to the start non-terminal of the original grammar tells you nothing, it might appear on some right hand side.


Monograph or survey paper on smoothed analysis of algorithms The paper by Spielman and Teng, Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time (JACM 51(3):385–463, 2004), won a Gödel award in 2008.

Since then, has there been a monograph or substantial survey paper written on the subject?

The best I could find was a book chapter in Algorithm Engineering by Müller-Hanneman and Shirra.

To the best of my knowledge, the most recent survey is the following:

Spielman, Daniel A., and Shang-Hua Teng. "Smoothed analysis: an attempt to explain the behavior of algorithms in practice." Communications of the ACM 52.10 (2009): 76-84.

It contains a lot of discussion.


In context of data mining, what does it mean for an association rule measure to be maximal? In context of data mining, what does it mean for an association rule measure to be maximal?

I cannot understand the term maximal in this context.

I know of maximal independent sets in algorithms but cannot make out this term.

I believe that in the context of that paper (PS), you can read "maximal" as "maximized". That is to say, the conviction function $P(A)P(\neg B)/P(A, \neg B)$ attains its greatest value when $A \implies B$.


Prove/disprove: If $_1$ is a finite language but not empty and $_2$ is NOT regular then $_1 \circ _2$ is NOT regular That what I have so far, but I am not sure at all.

Assume toward contradiction that $_1 \circ _2$ is regular.

Define $\Sigma' = \{\sigma'|\sigma\in\Sigma\} $.

Define a regular substitution $\forall\sigma\in\Sigma, h(\sigma) = \sigma'$.

$h(_1) = \{ = '_1'_2 ... '_ |  = _1_2 ... _ \in _1\}$ is also regular and finite by the closure of RL under substitution.

Therefore, by the assumption $h(_1) \circ _2$ is also regular.
Define regular substitution $\forall\sigma'\in\Sigma',g(\sigma')=\varepsilon,\forall\sigma\in\Sigma,g(\sigma)=\sigma$.

$g(h(L_1) \circ _2) = _2$ which is regular by the closure of RL under substitution, in contradiction to the assumption.
Therefore, $_1 \circ _2$ is not regular. Q.E.D

I am not sure about this statement "$h(_1) \circ _2$ is also regular".

Thanks for any help!!

$L_1\circ L_2$ can certainly still be non-regular. For example, when $L_1$ contains exactly one word.

However, $L_1\circ L_2$ can be regular, too. Here is an example. Let $L_1=\{\epsilon,0\}$. Let $L_2$ be the complement of $\{ 0^n1^n \mid n \gt 0 \}$.
As the complement of a non-regular language, $L_2$ is not regular while $L_1\circ L_2$, the set of all words over $\{0,1\}$, is regular.

Here are three similar exercises.

Exercise 1. Construct examples when the alphabet contains exactly one letter.

Exercise 2. Prove or disprove: If $L_1$ is a finite language but not empty and $L_2$ is not context-free, then $L_1\circ L_2$ is not context-free.

Exercise 3. Prove or disprove: If $L_1$ is a finite language but not empty and $L_2$ is not recursive, then $L_1\circ L_2$ is not recursive.


Are there efficient probabilistic multiplication algorithms that use O(n log n) gates? Recently Harvey and Hoeven published a paper proving that integer multiplication can be performed using at most O(n log n) operations. This algorithm is theoretically interesting, but in practice completely silly because you only start to see advantages on numbers with an absurd number of digits.

But suppose that we only wanted a probabilistic multiplication circuit, which returned the wrong result with probability at most epsilon. Then maybe certain shortcuts could be taken, in order to avoid the most inconvenient parts of multiplying two numbers.

For a fixed acceptable failure rate epsilon, is there an O(n log n) multiplication algorithm that achieves this failure rate without being horrendously inefficient in practice?

There is no acceptable failure rate. There are cryptographic systems that can be cracked if the 64x64 but multiplication of your processor gets one single product consistently wrong.

Unless your eps is so small that my computer being destroyed by a meteorite is more likely than getting a product wrong.


Representation of used space and free space in hard drives I've read from this How data is physically stored in hard drives, that the North/South orientation of the magnetic medium represents data as 0 or 1 physically in the hard drive. Data is stored in binary, which means that it can be stored as either 0 or 1 in the hard drive. But what determines if that particular block of memory in the hard drive is "Used Space" or "Free Space".

In the OS, you can view how much memory is used, and how much is free.

Let's say i have a 1 TB hard drive. I stored 100 GB worth of data with the repeating pattern "1100 1100". This means that I have 100 GB of used space and 900 GB left of free space (does it?). How does it know that it is used or free? If both 1 and 0 can be used to represent the data in that block of memory, then what represents as a "Free Space"? What if i delete 50 GB of data? I'll have 50 GB more free space, but what represents this free space? And how is the data 1 or 0 of "Used Space" converted to "Free Space"?

Free space is a concept at the level of the filesystem, which is part of the operating system. It is up to the filesystem to determine what space is free, and how to exploit it.

Data is stored on the hard drive in a structured way. The filesystem divides the drive into sectors (basic units, usually 512, 1024, 2048, or 4096 bytes), and maintains data structures on the drive which store which sectors are used and which are available. These data structures also store the directory structure of the drive, which sectors comprise which file, file names, and other metadata (such as various file timestamps).

Your experiment, of storing a repeated pattern on the raw drive, doesn't constitute a legitimate use of the drive. The drive is usually used only via a filesystem. The filesystem presents to the user (i.e., the software programmer) a logical view of the hard drive. Physical details such as were different parts of a file are stored are the business of the filesystem rather than of the user (though sometimes the user would like to know more, for example in order to defragment the drive).

The same, by the way, is true for memory, which is maintained by the memory manager, another part of the operating system. The operating system allocated memory to the user, takes care of swapping, stores the memory when hibernating, and so on. On modern CPUs, the user can't just use unallocated memory - this will trigger an exception. The supporting data structures are perhaps more lightweight, but there is still an infrastructure supporting memory allocation and deallocation.


Can a Markov Algorithm Replace the Empty String? Suppose I have a Markov Algorithm, and I have some rules, such that after execution of these rules, the remaining string is either "a", "b", or the empty string, "". Then I have three terminal rules to cover these cases:

"a" ->. "100"
"b" ->. "99"
"" ->. "0"

Is the last rule a valid terminal rule? Can a Markov Algorithm replace the empty string, or does it halt as soon as the string it is computing is empty?

Rules of the form $\epsilon \to w$ are allowed for Markov Algorithms. Be aware, however, that they will not only match, when the string is empty. Instead they will match every string, since every string contanins $\epsilon$ as a substring.

Since a rule that matches at multiple positions will be applied to the leftmost of them by definition, Rule 3 from your question will prepend a 0 to the string and terminate, whenever no rule before it is applicable. So, unless your previous processing relies on the fact that the algorithm will terminate when no rule is applicable (or already contains a rule for a or b), adding the three rules from the question as the last rules will give you the desired result.


Does a simple calculator require an operating system? I don't mean a TI-84 type calculator, and I also do not mean a simple calculator app on your phone.

Does a basic scientific calculator require an operating system?

No.

Operating systems have several purposes, such as interfacing with the hardware and, managing multiple concurrent or sequential applications and providing protection between different users. A calculator has only user and only one application so there's nothing to manage there.  And the hardware is simple enough that the single application may as well just talk directly to it, rather than going through the intermediate layer of an operating system.


Reverse the input and output of a Mealy machine Given a Mealy machine $M$, is it possible to construct another Mealy machine $M'$ that generates the reverse outputs from the reverse inputs, and if so, how?

That is, for each string $s$, $M(s) = t$ iff $M'(s') = t'$, where $s'$ is $s$ reversed and $t'$ is $t$ reversed.

For example, if $M(``abcd")$ is $``efgh"$ then $M'(``dcba")$ should be $``hgfe"$.

That's not possible in general. The classical Mealy machine definition requires the Mealy machine to accept infinite-length input strings and produce infinite-length output strings while reading the input. You can't reverse an infinite-length input string and can't reverse an infinite-length output stream, since there is no last letter in the unreversed string that you could put as first letter in the reversed string.

So for your question to make sense, you would first need to change the definition to allow the Mealy machine to have missing successors for some state/input combination, so that an input word ends at a well-defined position. Then, you would need to assume that the automaton eventually has a missing transition for every possible input word. This excludes all cycles in the automaton.

If we have this, then there is only a finite number of different input strings. If $M'$ is actually well-defined, then it is possible to build such a Mealy machine. But $M'$ may not be well-defined. For example if $M(\textit{abcd}) = \textit{efgh}$ and $M(\textit{cd}) = \textit{he}$, then we have $M'(\textit{dcba})=\textit{hgfe}$ and $M'(\textit{dc}) = \textit{eh}$. By the definition of Mealy machine, this also means however that $M'(\textit{d})=\textit{h}$ and $M'(\textit{d}) = \textit{e}$, which is a contradiction.


How to distinguish between the different frequency domains? Sometimes the terms 'Fourier domain', 'complex frequency domain', 'Frequency domain' and 's domain' are used interchangeably. Take these answers here for example.

Can you really use them interchangeably all the time, without being technically wrong? So, could you describe what would be wrong if I would replace 's domain' by 'fourier domain' for example? Or replacing 'complex frequency domain' by 'frequency domain'?

Hopefully whoever you are talking to would actually define the terms they were using before they started slinging them around.  I've heard some of these used in multiple contexts.  Wikipedia has an article that tries to encompass some of the different things people might be talking about when they use the term frequency domain.

The domain we are referring to here is the well-defined mathematical term for the set of legal inputs to a function.  There are multiple kinds of transforms (Laplace, Z, various kinds of Fourier transforms). The domains we are referring to are the (mathematical) domains of the function that results from the transform.

I tend to think of the s-domain as being associated with the Laplace transform:
$F(s) = \mathcal{L}[f] = \int_0^{\infty} e^{-st}f(t) \mathrm{d} t$.  The function $F(s)$ is potentially defined for the entire continuous complex plane, so the domain is the complex plane.  (Although for most functions $f$ there would be a region of convergence.)  I haven't personally heard the term s-domain in any other context.  For the Z transform you might hear "Z-domain" (which is also the entire continuous complex plane).

I think if I heard a scientist use the term Fourier domain my initial assumption would be that they were (probably) talking about the Fourier decomposition of a periodic function into a Fourier series.  (If I heard an engineer use the term Fourier domain I would think they were probably talking about a discrete Fourier transform, see below.)  Most people who use Fourier series in their daily work use the exponential Fourier series:
$c_n = F(n) = \mathcal{F}[f] = \frac{1}{2\pi}\int_{-\pi}^{\pi}f(x)e^{-inx}\mathrm{d}x$.  So the domain here (the subscript $n$ of $c_n$) is the integers.  (If I were talking to a student I would assume they were talking about the sine/cosine version, which is also defined across the integers (but inconveniently with two different series across the non-negative integers (once for sines and once for the cosines))).

For an engineer, and especially a computer engineer like me, I would assume that we were talking about the discrete Fourier transform.   This applies to periodic functions that are band limited (i.e., have very little energy in frequencies above some value.)  In that case the time (or space)-domain signal can be sampled at a finite rate and the transform is:
$X_k = \mathcal{F}[\{x_n\}] = \sum_{n=0}^{N-1}x_n e^{-2\pi i k n / N}$.  Here again the domain (the subscript $k$ of $X_k$) is the integers, and in this case just a finite sequence of integers $\{0, N-1\}$.

Finally, if I was talking to a scientist or mathematician and they used the term Fourier domain, my initial assumption that they were talking about a Fourier decomposition might be wrong.  They might instead be talking about a continuous Fourier transform:
$F(\omega) = \mathcal{F}[f] = \int_{-\infty}^{\infty}f(t)e^{-2\pi i \omega t} \mathrm{d} t$.  The domain of the function $F$ is the entire real line.  Note that there is some similarity with the Laplace transform but with the Fourier transform we are typically only looking at $s=2\pi i \omega$, the complex unit circle, (although sometimes it might be useful to look at the rest of the plane), and for the Laplace transform we are only looking at positive time.

Complex frequency domain could refer to the continuous Fourier transform, I suppose, but I would tend to think of it as referring to the same thing as the s-domain.

All these transforms are related, but in any conversation you need to be clear whether the time domain is continuous or discrete and whether the time domain function/signal repeats or not.  You should also make clear whether the time domain function's range is real or complex.  Then in the frequency domain you might be talking about complex frequencies (like in the Laplace transform or Z transform) or real frequencies, and, if real frequencies, continuous or discrete.  Sometimes you can infer from context, but sometimes not.  The range in the frequency domain is more often the complexes rather than the reals.

You should start every conversation with a boring list of definitions.


Terminology - Ensemble or Bag of classifiers? I am working on a classification problem. My algorithm involves splitting the data into several subsets based on a specific feature (e.g. number of XX) then training a classifier on each of these subsets. At test time, the incoming data will be passed to one of the trained classifiers depending this number of XX.

Would such a system be called an ensemble of classifiers or a bag of classifiers ?

No, this isn't bagging.  It could perhaps be called an ensemble of classifiers (see https://en.wikipedia.org/wiki/Ensemble_learning) but the most effective description will probably be to just describe what you are doing along the lines you listed in the question.  A "name" is primarily useful as a short way to describe what you are doing.  Some techniques are used so commonly that they have an accepted "name".  What you are doing isn't standard and might not have any well-known "name", but that's OK -- you can describe what you are doing in a sentence or two, so just do that.


Difference between task and process I'd like to know which is the difference between a task and a process in computer science. I'm studying a course on real-time systems and there are some definitions that I don't know.

Thank you in advance.

The difference appears to be that "process" is a well-defined term with a specific meaning that is universally understood, whereas "task" is ambiguous and means different things to different people.

The following Stack Overflow questions on the same topic support this:

https://stackoverflow.com/questions/3042717/what-is-the-difference-between-a-thread-process-task
https://stackoverflow.com/questions/2560939/task-vs-process-is-there-really-any-difference

Microsoft Windows certainly conflates the two terms—the Task Manager is used to administer processes.


How to construct XOR gate using only 4 NAND gate? xor gate, now I need to construct this gate using only 4 nand gate

a b out
0 0 0
0 1 1
1 0 1
1 1 0

the xor = (a and not b) or (not a and b), which is
\begin{split}\overline{A}{B}+{A}\overline{B}\end{split}

I know the answer but how to get the gate diagram from the formula?

EDIT

I mean intuitively, to me, I should get this one if I do it step by step followed by the definition xor = (a and not b) or (not a and b).

\begin{split}\overline{\overline{\overline{A}{B}}\cdot\overline{{A}\overline{B}}}\end{split}

and xor will be constructed with 5 nand gates (first #1 image below)

my question is more like: imagine the first person in history figure out this formula, how can he or she (the thinking process) get the 4 nand soltuion from this formula, step by step.

\begin{split}\overline{A}{B}+{A}\overline{B}\end{split}

From that formula? It can be done. But it's easier to start with this one: (using a different notation here)

a ^ b = ~(a & b) & (a | b)

Ok, now what? Eventually we should derive ~(~(~(a & b) & a) & ~(~(a & b) & b)) (which looks like it has 5 NANDs, but just like the circuit diagram it has a sub-expression which is used twice).

So make something that looks like ~(a & b) & a (and the same thing but with a b at the end) and hope that it'll stick around: (and distributes over or)

(~(a & b) & a) | (~(a & b) & b)

Pretty close now, just apply DeMorgan to turn that middle or into an and:

~(~(~(a & b) & a) & ~(~(a & b) & b))

And that's it.


How do proof assistants nowadays avoid floatpoint error? I heard that Coq is using "Dedekind cut", but how's that related to floatpoint errors?

Can we just use something like

data Q : Type where
  div : N -> N -> Bool -> Q

To replace all usages of floatpoint numbers?

It depends on whether you want to "simply" reason about the properties of real numbers, or if you want to perform actual calculations.

If you want to prove things about their general properties, then using Dedekind cuts is feasible.

If you want to compute actual numerical things, then you need a numerical representation of the cut, and then you're back to some computable representation of (some of) the reals (you can't get all of them). It doesn't strictly have to be floating point numbers - you could use arbitrary precision arithmetic for example - more accurate but slower in general.

Your type however seems to be aiming to represent the Rationals, for which floating point numbers are unnecessary, you could just have a type with one constructor: nat -> nat -> Q.


Can every linear grammar be converted to Greibach form? Can every linear grammar be converted to a linear Greibach normal form, a form in which all productions look like $A \rightarrow ax$ where $a \in T$ and $x \in V \cup \{\lambda\}$?

($T$ is the set of terminals, $V$ is the set of non-terminals, $\lambda$ is the empty sequence.)

The more general answer is:

Blum and Koch showed a polynomial time transformation such that any context-free grammar can be converted to Greibach form.

Since a linear grammar is a special case of Context-free grammar, the answer is yes.

A simpler transformation:

Any rule $X \rightarrow a_1 a_2 \cdot a_k Y$ you transform them in $k$ rules:

$X\rightarrow a_1 X_1Y$.
$\cdots$
$X_{i-1}\rightarrow a_{i}X_i$
$X_{k-1}\rightarrow a_{k}Y$

Any rule $X \rightarrow a Y b$ should be transformed in two rules

$X \rightarrow a Y Y_1$.
$Y_1 \rightarrow b$

where the capital letters belong to $V$ and the small letters to the alphabet (terminals).


Weighted binary search tree Suppose we have binary search tree with $n$ nodes. For each node $u$
we define weight of $u$ is number of nodes in sub tree of $u$ with
$u$. if  ratio of weight of each internal node $u$  of right sub tree
and left sub tree be at least $0.5$ and at most 2, then what is worst
case of searching for a element in such binary search tree?
The answer is $2\log n$.

How it be $2\log n$? I think this tree is weighted binary search tree not AVL tree. But in proving worst case that mentioned get  stuck. Any hint be appreciated.
My attempt:
I try to use formula that we use for minimum number of nodes we need to construct a AVL tree, Prove that AVL tree has this kind of property with Fibonacci sequence, but i can't draw any relation between my problem and AVL tree.

Show by induction on the height $h$ of the tree that a tree of height $h$ has at least $2^{\frac{h}{2}}$ nodes.
The base case $h=0$ is easy since a tree of height $0$ has $1$ vertex and $1 \ge 2^\frac{0}{2}$.
Suppose that the claim holds up to some $h \ge 0$. Consider a tree $T$ with height $h+1$ rooted in $r$. Let $u$ and $v$ be the children of $r$. Let $n(x)$ and $h(x)$ denote the number of nodes and the height of the subtree of $T$ rooted at $x$, respectvely.
We must have $h(r) = 1 +\max\{h(u), h(v)\}$. Suppose w.l.o.g. that $h(r)=1+h(u)$. Then, regardless of whether $u$ is the left or right child of $r$, we have $\frac{n(v)}{n(u)} \ge \frac{1}{2}$, i.e., $n(v) \ge \frac{n(u)}{2}$.
$$
\begin{align*}
n(r) &= 1 + n(u) + n(v) > n(u) + \frac{n(u)}{2} = \frac{3}{2} \cdot n(u) \\
&\ge \frac{3}{2} \cdot 2^{\frac{h(u)}{2}}
= \frac{3}{2} \cdot 2^{\frac{h(r)-1}{2}}
= \frac{3}{2} \cdot 2^{\frac{h}{2}}
> 2^{\frac{1}{2}} \cdot 2^{\frac{h}{2}} =  2^{\frac{h+1}{2}}.
\end{align*}
$$
This concludes the proofs, and shows that a tree with $n$ nodes has height at most $2 \log n$.


Tapered Quantization In Gonzalez et al it is mentioned that Tapered Quantization is

I am unable to figure this thing out. I have searched the whole internet, but nothing of the same appears. I need a help in understanding this matter, and if you can provide a picture that will be really helpful.

Basically from what I understood, it would be something like this....
In the quantization graph, we usually see a wave and the corresponding amplitudes marked at the axes and all those amplitude values are equally spaced from each other.
But according to tapered quantization, the constantly repeating values of the amplitudes will follow a finely spaced pattern in the plotter but with the values that appear rarely, those amplitude points/ values would face an non-equal pattern in between them(they would be marked or placed far away from each other).


Can a Turing machine be both decidable and undecidable relative to itself? Consider the language:

$A'_{TM} = \{\langle M,w\rangle: M \mbox{ is a TM with access to an oracle for } A_{TM} \mbox{ and } M \mbox{ accepts } w\}$

Clearly, we expect that any language is decidable relative to itself, including $A'_{TM}$. So let $F$ be an oracle decider for $A'_{TM}$ that has access to an oracle for $A'_{TM}$. In particular, we can construct $F$ as follows.

$F = $ "On input $\langle M, w \rangle$, where $M$ is a TM and $w$ is a string:

Query the oracle for $A'_{TM}$ with $\langle M, w \rangle$.
If the oracle replies YES, accept. If the oracle replies NO, reject."

Now, consider the following TM, $D$.

$D$ = "On input $\langle M \rangle$, where $M$ is a TM.

Check if $M$ is an oracle TM with an oracle for $A'_{TM}$. If it is not, reject. Otherwise, proceed to the next step.
Simulate $F$ on $\langle M, M \rangle$. If it accepts, reject. If it rejects, accept."

Now, suppose that we feed $\langle D \rangle$ as input to $D$. Then clearly, computation proceeds to Step 2, since $D$ has an oracle for $A'_{TM}$. But Step 2 yields a contradiction, since we are forced to conclude that $D$ accepts $\langle D \rangle$ if and only if $D$ rejects $\langle D \rangle$. So it seems we must conclude that $A'_{TM}$ is both decidable and undecidable relative to itself, which seems absurd.

A Turing machine doesn't come with an oracle. The oracle comes from outside. Rather, an oracle Turing machine is a Turing machine that has a special way of accessing an oracle. When you run the Turing machine with a specific oracle $O$, whenever the machine activates the special mechanism for accessing an oracle, you forward the request to $O$. A phrase like "$M$ is an oracle TM with an oracle for $A'_{TM}$" is thus meaningless.

You are saying that you run $D$ on the input $\langle D \rangle$, but you haven't specified what oracle you are running $D$ with. If you want $F$ to have the proper semantics, then you have to run $D$ with an oracle for $A'_{TM}$. When run in this way, $D$ accepts $\langle D \rangle$ iff $F$ rejects $\langle D,D \rangle$ when run with $A'_{TM}$, and so iff $D$ rejects $\langle D \rangle$ when run with $A_{TM}$.

Notice that there is no contradiction: $D$ accepts $\langle D \rangle$ when run with the oracle $A'_{TM}$ iff it rejects $\langle D \rangle$ when run with the oracle $A_{TM}$.

The real reason this works out is that a machine cannot get as input an oracle TM together with an oracle, since the oracle is an infinite object and so it cannot be specified as input.


Show that UPrime = {1^n : n ∈ N is prime} is in P I have this question to solve. According to my understanding, it basically requires a turing machine that outputs lines on the tape, with the number of the lines being any prime number.

My idea is to take the AKS test's conclusion and making a case that since, calculating primes is a problem that can be solved in polynomial time complexity as already proven by AKS, hence this problem is also in P.

Is this the right way? what would be a more formal/mathematical way of expressing this if it is?


What is Round Robin's behavior when a process comes at the same time that the old process is swapped out? Let's say there are two processes: p1 and p2, their arrival time and service time are 0,2 and 3,1 respectively.  The time quantum is 2s.

After excuting for two seconds, will the processor excute p2 or continue excuting p1?

P1 arrives at time 0 and needs 3 seconds to process.

P2 arrived at time 2 and needs 1 second to process.

Processing

P1 arrives first and will process 2 second because time quantum is 2s. 1s left.

After processing P1 (2 seconds later), P2 will arrive.

It will completely process it and then return back to P1.

1 second later both processes are processed.


Proof-sketch on the language accepted by a Turing machine Let $T$ be a Turing machine whose accepted language is $L(T)$. Let $X$ be another language. How do you approach a proof like $L(T)\subseteq X?$

In order to prove that any machine, automaton or grammar satisfies $L(T) \subseteq X$ you have to translate your intuition of how it was designed into hard facts. What is the intended meaning of a certain configuration, how where the states chosen? So you have to divide the operation of the machine into phases. Like, "if the TM is in state $q$ on the left of the tape, it will move right, marking half of the symbols $A$ ending in state $q$ on the leftmost cell used". If the design of the machine is done right, such explanations usually suffice, if they can be easily understood. Otherwise one has to apply induction, on whatever seems interesting (like the remaining symbols $A$).

Let me try to add an example, what I would consider sufficient "proof". A Turing machine deciding the language $\{ a^{2^n} \mid n\ge 1\}$. States used $p_0,p_1,p_O,p_E,\ell,p_A,p_R$, accepting state $p_A$, rejecting $p_R$. Tape alphabet $\{a,X,B\}$, with $B$ for blank. Instructions in the order (state, symbol, new state, new symbol, direction).

We scan the tape from left to right. In each scan we halve the number of $a$'s. When the number of $a$'s on the tape is $1$ we accept, otherwise when the number is odd we reject (and halt), finally when the number is even, we return to the leftmost symbol on the tape.

Start in state $p_0$, indicating $0$ $a$'s read. Other states $p_1,p_E,p_O$ for single, even, odd number of $a$'s read.

$(p_0,a,p_1,a,R)$, $(p_1,a,p_e,X,R)$, $(p_E,a,p_O,a,R)$, $(p_O,a,p_E,X,R)$, move right, crossing out every second $a$.
$(p,X,p,X,R)$, for $p = p_0,p_1,p_E,p_O$, ignore symbol $X$.
$(p_0,B,p_R,B,L)$, $(p_1,B,p_A,B,L)$, $(p_E,B,\ell,B,L)$, $(p_O,B,p_R,B,R)$, make decision on reaching the right end of the tape, as explained above.
$(\ell,\sigma,\ell,\sigma,L)$, $\sigma = a,X$
$(r,B,p_0,B,R)$ in state $\ell$ move left to first symbol on tape, ending there in state $p_0$.

Finally, note we reject on empty tape.


Discrete assignment problem with penalties I came across a problem were you have to plan an optimal assignment pattern. Let's say you have $j=1,\ldots,n$ tasks during $i=1,\ldots,m$ time periods.

It's an single agent problem where we have to assign agent to perform exactly one task $j$ during each period $i$, i.e., $\sum_{j=1}^n x_{ij} = 1$ for $i=1,\ldots,m$ where $x_{ij}=1$ if agent is assigned to task $j$ in period $i$ and $0$ otherwise.

We receive a reward of $c_{ij}$ for performing task $j$ on period $i$. Additionally, there is a penalty $p$ each time the task changes between two consecutive periods. If during period $i$ we assign the agent to perform task $j$ and on $i+1$ the task $j^\prime$, we subtract the penalty $p$ from the total reward of all assignments.

We want to assign the agent in such way that the total profit $$\sum_{i=1}^m \sum_{j=1}^n x_{ij} c_{ij} - \text{penalties  introduced by changing task between periods}$$

is maximized. I have been able to model this as an integer program with binary decision variables, but I was thinking maybe there is some other type of recursive algorithm (via dynamic programming) that could handle this problem also. Is this a known problem with solution methods present in literature? It seems like it could have already been studied, but I haven't been able to find a name for this kind of problem.

Riley's answer is excellent.  It is possible to improve the running time further to $O(mn)$ time, using dynamic programming.  This saves a factor of $n$ in the running time.

Define $T[i,j]$ to be the total profit of the best assignment for times $i,i+1,\dots,m$, assuming that at time $i$ the agent is assigned to task $j$.  We'll compute all of the $T[i,j]$ values, in order of decreasing $i$, using the following recurrence:

$$T[i,j] = c_{ij} + \max(T[i+1,j], \max\{T[i+1,j'] : 1 \le j \le n, j' \ne j\} - p),$$

or equivalently,

$$T[i,j] = c_{ij} + \max(T[i+1,j], \max\{T[i+1,j'] : 1 \le j' \le n\} - p).$$

Naively, it looks like filling in a single cell will take $O(n)$ time so computing all the $T[i,j]$ values will take $O(n^2)$ time.  However, we can speed it up with a trick.

Define

$$M[i] = \max(T[i,1],\dots,T[i,n]).$$

We obtain the improved recurrence

$$T[i,j] = c_{ij} + \max(T[i+1,j], M[i+1] - p).$$

We'll fill in the $T[i,\cdot]$ and $M[i]$ values simultaneously, in order of decreasing $i$.   Once we've filled in $T[i,1],\dots,T[i,n]$, we can compute $M[i]$ in $O(n)$ time.  Then, once we know $M[i]$, we can compute each $T[i-1,j]$ in $O(1)$ time using the improved recurrence, so we can compute $T[i-1,1],\dots,T[i-1,n]$ in $O(n)$ time once we know $M[i]$.  Finally, $M[1]$ is the final answer to the problem.

In this way, we do $O(n)$ work per value of $i$, and there are $m$ values of $i$.  Consequently, the total running time is $O(mn)$.


Complexity of many constant time steps with occasional logarithmic steps I have a data structure that can perform a task $T$ in constant time, $O(1)$. However, every $k$th invocation requires $O(\log{n})$, where $k$ is constant.

Is it possible for this task to ever take amortized constant time, or is it impossible because the logarithm will eventually become greater than $k$?

If an upper bound for $n$ is known as $N$, can $k$ be chosen to be less than $\log{N}$?

If every $k$th operation takes $O(\log n)$ time, then the best bound you can get on the amortized complexity is $O(1 + \frac{\log n}{k})$. This follows from the definition of amortized complexity.


Why the number of equivalence classes for the intersection of an irregular language L2 and a regular languge L3 (with 3 EC) can't be determined? I'm trying to understand why can't we determine the number of equivalence classes of the intersection of L2 which is irregular and L3 which is regular and known to have 3 equivalence classes (L3 can't be empty). Can't we say it has minimum of 1?

Can we determine the number of equivalence classes for an Irregular language L with a star (L*)?

Assuming you are meaning Nerode equivalence classes, the number of classes of a language is finite iff that language is regular.

We cannot make any statement for the intersection of a regular and a non-regular language. That intersection can non-regular, but also regular.
Similar for the star of a non-regular language.

Stating that the number of classes is at least one is not very instructive. Isn't that true for all equvalence relations?


Triple nested for-loops Possible Duplicate:
  A puzzle related to nested loops

I am trying to count the exact/total number of iterations the following nested for-loops are executed:

s=0
for (i: 1 to n)
 for (j: 1 to i)
  for (k: j to i)
   s = s + 1

I know that the first two for-loops will have n(n+1)/2 iterations. My problem is with the third for-loop. Due to this third loop what factor am I supposed to multiply with n(n+1)/2 to get the total number of iterations?

Any help would be appreciated? Thanks

Instead of a general "formula", you should try to work out from principles first, at least in the beginning. You can see that the number of executions are:

$$\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{i} \sum\limits_{k=j}^{i} 1$$

We try solving them one step at a time. The innermost (right-most) summation can be solved as:

$$\sum\limits_{k=j}^{i} 1 = i - j + 1$$ (how many times will the loop execute from $j$ to $i$, inclusive).

Going on to the next level, by substituting the above result, we get:
$$\sum\limits_{j=1}^{i} \sum\limits_{k=j}^{i} 1 = \sum\limits_{j=1}^{i} (i - j + 1) = i\sum\limits_{j=1}^{i} 1 -\sum\limits_{j=1}^{i}j + \sum\limits_{j=1}^{i}1$$
$$ = i^2 - \frac{i(i+1)}{2} + i = \frac{i(i+1)}{2}$$

Notice that when summation is over the variable $j$, $i$ behaves like a constant, and so could be taken out of the summation.

The above expression gives the number of times the inner two loops are executed for every value $i$ that the outer loop takes. Solving the outermost summation with this expression ($i$ runs from $1$ to $n$), we have:

$$\sum\limits_{i=1}^{n}\frac{i(i+1)}{2} = \frac{1}{2}\sum\limits_{i=1}^{n}i^2 + \frac{1}{2}\sum\limits_{i=1}^{n}i$$
$$ = \frac{1}{2}\cdot\frac{n(n+1)(2n+1)}{6} + \frac{1}{2}\cdot\frac{n(n+1)}{2}$$
$$ = \frac{n(n+1)(n+2)}{6}$$

This will also be the value of the variable s in your pseudocode. I suggest that you should approach these kind of questions from the basics, and revise the summation rules. There are no general formulas or multiplication factors for some arbitrary nesting of loops. You might even want to go along these lines to again derive your result for the first two loops only.


CTL formula for "for every computation it is always possible to return to the initial state" In the book 'Principles of Model Checking' by Christel Baier and Joost-Pieter Katoen they state that the CTL formula for " for every computation it is always possible to return to the initial state" as  'AGEF start'. I was wondering whether the formula 'AGF start' would also be a valid one ? Is this correct ?

$AGF start$ is not a well-formed CTL formula, since in CTL you cannot write GF. Every temporal quantifier must be preceded by a path quantifier.

However, $AGF start$ is a formula in CTL*, so we can ask your question about CTL*:

  Is the formula $AGFstart$ equivalent to $AGEFstart$?

The answer to this question is no. The first formula says that in every path, you will visit start infinitely often, while the second one only claims that on every path, you can always find some way to get back to start.

Try constructing a system that satisfies one but not the other.

Hint: if $AGFstart$ holds, then $AGEF start$ also holds.


Sample a scale free subnet from random network I already have a network which is like random complex network. Is there any way I can delete some of nodes and reduce the network into a scale-free network?

I notice there are some methods that can sample a scale-free subnet from a scale-free network. But I have not found anyone sampled a scale-free subnet from a random network.

In order to do this, you need high degree nodes in your initial network: since you do not add anything, degree may only decrease, and you want high degree nodes in the end.
Now, assume your initial random network indeed has high degree nodes. Since it is random, choosing random links in it will often lead to high-degree extremities. Indeed, the probability to pick a degree $k$ extremity when you choose a link at random is proportional to $k$.
This property underlies the works conducted to estimate bias in internet measurements. Several works show that power-law networks may indeed be obtained from initially random networks, for instance by taking a BFS tree.
See e.g. On the Bias of Traceroute Sampling; or, Power-law Degree Distributions in Regular Graphs for a formal analysis published in STOC and Journal of the ACM, as well as Relevance of Massively Distributed Explorations of the Internet Topology: Qualitative Results for an experimental work published in INFOCOM and Journal of Computer Networks.


Time complexity of comparing two $N \times N$ Matrices? So each matrix has $N^{2}$ elements, and so just by comparing each element we would be doing $O(N^{2})$ operations. Is there any other way to compare these two matrices such that the number of operations is less than $O(N^{2})$ or is the matrix comparison lower bound also $\Omega(N^2)$?

A very simple adversary argument shows that when comparing two vectors of length $M$ (in your case, $M = N^2$), you must query (in the worst case) all positions of both vectors to know whether they are equal. That takes time $\Omega(M)$.