Convert a digraph to the corresponding undirected graph in linear time using adjacency lists Suppose we have a directed graph $G = (V,E$) represented with adjacency lists.  Is it possible to convert $G$ into its undirected equivalent* $G'$, also represented with adjacency lists, in $O(|V|+|E|)$ time?

The obvious algorithm walks the adjacency list of each vertex $v$, and for each adjacent vertex $u$, inserts edges $(v,u)$ and $(u,v)$ into $G'$.  The issue is duplicates.  If $(u,v)$ happens to be in $G$ already, $(u,v)$ will be inserted into $G'$ twice: once when processing $v$'s adjacency list, and once when processing $u$'s.  Assuming that a well-formed graph doesn't contain any duplicate edges, we would need to check $u$'s adjacency list to see whether it contains $v$ before performing the second insertion.  But this check takes linear time in $|V|$, and we would need to perform this check for $O(|E|)$ edges, resulting in $O(|V|*|E|)$ time complexity.

*Terminology:  by "undirected equivalent" of a digraph $G=(V,E)$, I mean the directed graph $G'=(V,E')$ such that

if $(v,u) \in E$ then $(v,u) \in E'$ and $(u,v) \in E'$ and
if $(v,u) \in E'$ then either $(v,u) \in E$ or $(u,v) \in E$.

If you perform the check at the end rather than throughout, it will be much faster.

Start by going over all edges, and for each edge $(i,j)$ add the edge $(j,i)$ to the adjacency list of $j$.

Now given the adjacency list of $i$, we want to remove duplicates. For that we use an array indexed by $V$, which is initialized to zero (we only need to initialize it once). Go over the list and count how many times you see each edge. Now go over the list a second time and only add the first occurrence of every edge. Finally, go over the list a third time to reset the array back to zero. In all, we do $O(1)$ work per edge.

One drawback of this algorithm is that the resulting adjacency lists aren't sorted, even if you started out with sorted ones. Here is a different algorithm which works in $O(|V|+|E|)$ time and maintains this invariant (assuming it holds originally). For each vertex $i$, compute the sorted lists $\{ j : (i,j) \in G \}$ and $\{ j : (j,i) \in G \}$. Then merge them and remove duplicates.


Asymptotic Runtime of Interrelated Functions I have two functions $S$ and $T$ which are interrelated and I want to find the asymptotic worst case runtime. The fact that they are interrelated is stumping me...

How would I find the asymptotic runtime $S(n)$ and $T(n)$?

$$
\begin{align*}
S(n) &= 2S(n/4) +  T(n/4) \\
T(n) &=  S(n/2) + 2T(n/2)
\end{align*}
$$

Here is one approach.  Plug in the definition of $T(n)$ into your first equation, and we get

$$S(n) = 2S(n/4) + S(n/8) + 2T(n/8).$$

Now plug in again and we get

$$S(n) = 2S(n/4) + S(n/8) + 2S(n/16) + 4T(n/16).$$

Keep plugging in and eventually we get

$$S(n) = 2S(n/4) + S(n/8) + 2S(n/16) + 4S(n/32) + 8S(n/64) + \dots + O(1).$$

Now solve that recurrence relation for $S(n)$, noting that now you have a single function (you don't have two interrelated functions any longer).


Initial temperature in simulated annealing algorithm I've done some testing of different initial temperatures in my simulating annealing algorithm and noticed the starting temperature has an affect on the performance of the algorithm.

Is there any way of calculating a good initial temperature?

As noted by Thomas Klimpel in the comments, a certain acceptance probability is often used, which is equal to say $0.8$. The following is a simple iterative method to find a suitable initial temperature, proposed by Ben-Ameur in 2004 [1]. In the following, $t$ is a strictly positive transition, $\max_t$ and $\min_t$ are the states after and before the transition, $\delta_t$ the cost difference $E_{\max_t} - E_{\min_t}$ and $\pi_{\min_t} \dfrac{1}{|N(\min_t)|}$ the probability to generate a transition $t$ when the energy states are distributed in conformance with the stationary distribution

$$\pi_i = \dfrac{|N(i)|\text{exp}(-E_i/T)}{\sum_j |N(j)| \exp(-E_j/T)}$$, where $N(i)$ denotes the set of neighbors of $i$.

Finally, $\text{exp}(-\delta_t/T)$ is the probability of accepting a positive transition $t$. Now, we can have an estimation $\hat{\chi}$ of the acceptance probability $\chi(T)$  based on a "random" set $S$ of positive transitions:

\begin{eqnarray}
\hat{\chi}(T) &=& \dfrac{\sum_{t \in S} \pi_{\min_t} \dfrac{1}{|N(\min_t)|} \text{exp}(- \delta_t / T)}{\sum_{t \in S} \pi_{\min_t} \dfrac{1}{|N(\min_t)|}} \\
 &=& \dfrac{ \sum_{t \in S} \text{exp}(- E_{\max_t} / T) }{ \sum_{t \in S} \text{exp}(- E_{\min_t} / T) }.
\end{eqnarray}

We want to find a temperature $T_0$ such that $\chi(T_0) = \chi_0$, where $\chi_0 \in ] 0,1 [$ is the acceptance probability we desire.

$T_0$ is computed by an iterative method. Some states and a neighbor for each state is generated. This gives us a set of transitions $S$. The energies $E_{\max_t}$ and $E_{\min_t}$ corresponding with the states of the subset $S$ are stored. Then a value for $T_1$ is chosen, which can be any positive value. $T_0$ is then found with the recursive formula

$$T_{n+1} = T_n \dfrac{\ln(\hat{\chi}(T_n))}{\ln(\chi_0)}^{1/p}$$, where $p$ is a real number $\geq 1$.

When $\hat{\chi}(T_n)$ gets close to $\chi_0$ we can stop. $T_n$ is now a good approximation of the wanted initial temperature $T_0$. For more explantion, proofs and discussion, please see the first section of the original paper [1].

[1] Ben-Ameur, Walid. "Computing the initial temperature of simulated annealing." Computational Optimization and Applications 29, no. 3 (2004): 369-385.


non deterministic space hierarchy I want to prove the non deterministic space hierarchy theorem.

Let $f(n),g(n)\geq\log n$ be space constructible functions such that $f(n)=o(g(n))$, Prove:

$$NSPACE(f(n))\subsetneq NSPACE(g(n))$$

I feel that the standard way of constructing a TM that takes as an input a TM and simulates the machine on itself, then flipping the output won't work because the input is a nondetrministic TM maybe. Can someone suggest a hint?

The Wikipedia proof for the non-deterministic doesn't flip the output. It considers the language
$$ L = \{ (\langle M \rangle, 1^t) : \text{$M$ accepts $(\langle M \rangle, 1^t)$ in space $g(|(\langle M \rangle, 1^t)|)$} \}. $$
This language is in $\mathsf{NSPACE}(g)$. The Immerman–Szelepcsényi theorem shows that if $L \in \mathsf{NSPACE}(f)$ then also $\overline{L} \in \mathsf{NSPACE}(f)$, which leads to a contradiction.


first order logic to normal form order of operations ∃y∀x [A(x) ∧ B(y) -> C(x,y)]
 ∃y∀x [¬(A(x) ∧ B(y)) v C(x,y)]
 ∃y∀x [¬A(x) v ¬B(y) v C(x,y)]

I need to convert the above to conjunctive normal form. I'm a little confused about the order of operations in the case of both existential and universal quantifier and which part of the expression they apply to.
From the last step, would I skolemize y across the entire expression meaning:
∀x [¬A(x) v ¬B(S(x)) v C(x,S(x)]

or do I take the universal quantifier first?

You always remove quantifiers in the order in which they appear in the prefix, from left to right, that is, you first eliminate $\exists y$ and then $\forall x$.
But the variables to apply the skolem function to are just the variables occurring free in the expression, no bound ones. Since $x$ is bound by $\forall x$, and $y$ is being skolemized away, the skolem function for $\exists y$ becomes a zero-place function symbol, or constant, S():
∃y∀x [¬A(x) v ¬B(y) v C(x,y)]
>>
∀x [¬A(x) v ¬B(S()) v C(x,S())]
In the next step, eliminate the the universal quantifier:
∀x [¬A(x) v ¬B(S()) v C(x,S())]
>>
¬A(x) v ¬B(S()) v C(x,S()).


Prove (non-)recursiveness of a set of Turing Machines defined by behavior I have a list of problems which I don't know how to prove (non-)recursive (save, I think, for the first), where $\mathcal{M}_n$ is the Turing-Machine with the Gödel-number $n$:

$\mathcal{R}=\left\{n:\mathcal{M}_n\text{ does not move right for any input.}\right\}$

$\mathcal{R}_\mathcal{S}=\left\{n:\mathcal{M}_n\text{ does not move right past the starting position for any input.}\right\}$

$\mathcal{S}=\left\{n:\mathcal{M}_n\text{ does not hang for any input.}\right\}$

Note: The model used within this question is one with a one-side-unbounded tape with the bound being on the left end, thus "hangs" means trying to move off the left end of the tape; the Turing-machine starts right of the input and has three options per step: writing or moving left or right, so no movement is necessary for a step.

I already researched and tried to find solutions of my own, but as Rice's theorem is not applicable, I failed at finding a direct proof of undecidability or proof by reduction (as I cannot think of a way to reduce any known undecidable problem to any of these); research includes:

http://www.ics.uci.edu/~goodrich/teach/cs162/hw/HW7Sols.pdf
It seems sensible to perform a breadth-first-search for $\mathcal{R}$, though the presented solution would need to be modified to reflect the different model. This problem seems to be decidable.
Can an alphabet be extended in a reduction proof? (with sample problem)
This is quite precisely a question about $\mathcal{S}$, but the proposed reduction reduces the problem to a non-recursive problem, which obviously yields no result at all.

None of my own ideas worked out, thus I have little to show for; I had a vague idea of reducing $\mathcal{S}$ to $\mathcal{R}_\mathcal{S}$ by flipping the input (as well as the movements of the Turing Machine); the main problems are that I have no solution for $\mathcal{S}$ (although I expect it to be non-recursive), and a reduction would need to use an unbounded tape, which may (or may not) break the problem.

Thus, any help (or hint at methodology) would be greatly appreciated.

$\boxed{\mathcal R}$

Idea: If you never move right, you have a regular behaviour. And you can move right iff a "state" in which you can move right is reachable while following this regular behaviour.

Solution:

   $\mathcal R$ is decidable

Proof:

   Let $\mathcal M$ be a TM with states $Q$ and tape alphabet $\Gamma$. Build the following automaton:

 - States: $Q\times (\Gamma \sqcup \{?\})$ where the right component is whatever is on the tape at the current position (we write $?$ if it is whatever was there at the very beginning, and $a$ if we wrote an $a$ there)

 - Transitions:
 $\hspace{0.5em}$ - $(p, a)\overset{a}{\to}(q,?)$ if the TM can read $a$ while in state $p$ and move left
 $\hspace{0.5em}$ - $(p, a)\overset{\varepsilon}{\to}(q,b)$ if the MT can write a $b$ and move to state $q$ if it's in state $p$ and reads an $a$
 $\hspace{0.5em}$ - $(p, ?)\overset{\varepsilon}{\to}(p,b)$ (because since we just moved left and never moved right, replacing the letter at that position on the tape by anything wouldn't change the execution until that point).
 - The initial states are $(q_i, ?)$ where $q_i$ is an initial state of the TM.

 Then in this automaton, a state $(p,a)$ is accessible iff there is a run in the TM so that gets in a state where the TM is in state $p$ and is about to read an $a$ on the tape. So you just have to check if there is an accessible state $(p,a)$ in this automaton so that the TM can read an $a$ while in state $p$ and move right.

$\boxed{\mathcal S}$

Idea: Halting for all inputs is "For all input, there is an execution that halts" which is more complicated than the halting problem "Given this input, there is an execution that halts".

Solution:

   $\mathcal S$ is undecidable

Proof:

   Take a TM $\mathcal M$ and an input $w$. Build a new TM $\mathcal M'$ that erases its input, writes $w$ and then runs $\mathcal M$.

 $\mathcal M'$ halts on all inputs
 (iff $\mathcal M'$ halts on some input)
 iff $\mathcal M$ halts on input $w$

 So your problem is undecidable because the halting problem can be reduced to it.


Yes, there is a polynomial-time algorithm for your problem.  There's no need to use a LP or ILP; you can solve it directly using combinatorial, graph-based methods.  In particular, we can solve your problem by a reduction to the assignment problem, i.e., to computing a maximum weight matching in a weighted bipartite graph.

Suppose we have a bipartite graph with weights on the edge, and we want to find a perfect matching whose total weight is as large as possible.  Call this the maximum-weight perfect-matching problem.  You can solve this problem as follows.  Pick a large constant $C$ (sufficiently large); replace the weight $w$ on each edge with $w+C$ (i.e., add $C$ to each edge weight).  Now find the maximum weight matching in the resulting graph using the Hungarian algorithm or any other algorithm for maximum weight matching.  (Here the key fact we are using is that a maximum weight matching can be found in polynomial time.)

I claim that the resulting matching will be a perfect matching, if one exists.  Why?  Well, if a perfect matching exists, then its weight will be $Cn+\delta$, where $n$ is the number of edges in a perfect matching and $\delta$ is something bounded (it's the sum of $n$ weights from the original graph).  The weight of any non-perfect matching will be at most $C(n-1)+\delta'$, where $\delta$ is something bounded (it's the sum of at most $n-1$ weights from the original graph).  Suppose $C$ is at least $2n$ times the largest of the absolute values of the weights of the original graph.  Then $Cn+\delta$ will always be larger than $C(n-1)+\delta'$, or in other words, any perfect matching will have greater total weight than any non-perfect matching.  It follows that the Hungarian algorithm on this modified graph will find the maximum-weight perfect matching in the modified graph, and this corresponds to the maximum-weight perfect matching in the original graph (since we added the same constant to the weight of every edge).

So, there is a polynomial-time algorithm to find the perfect matching whose total weight is maximized.  Given this, we can solve your problem (find the perfect matching whose total weight is minimized) by simply negating all of the edge weights.


The validity of the potential function for splay tree The paper "Self-Adjusting Binary Search Trees" defines (Page 658) the potential function for analyzing the amortized cost of a sequence of $m$ splay operations as the sum of the ranks of all nodes in the splay tree, where the rank of a node $x$ is taken as the logarithm of the size ($s(x)$; i.e., number of nodes in) of the subtree rooted at $x$:

$$\Phi(T_i) = \sum_{x \in T} \log (s(x)).$$

To make sure that the amortized cost is an upper bound of the actual cost, it is required that the final potential is no less than the initial potential $\Phi(T_0)$ (Page 657):

$$\forall 1 \le i \le m: \Phi(T_i) \ge \Phi(T_0).$$

Problem: How to verify the condition above? (I did not find the argument in the paper.) Maybe it is not necessary to verify this condition; if so, why?

Answer My Own Question:

The short answer:

We don't have to verify $$\forall 1 \le i \le m: \Phi(T_i) \ge \Phi(T_0).$$ This condition is a special case of a more general one, which we need to verify for this example.

The detailed answer:

Consider a data structure $D$ and its states $D_0 \cdots D_m$ produced by a sequence of $m$ operations $o_1 \cdots o_m$:
$$
D_0,\; o_1,\; D_1,\; o_2,\; \cdots,\; \underbrace{D_{i-1},\; o_{i},\; D_{i}}_{\text{the $i$-th operation}},\; \cdots,\; D_{m-1},\; o_{m},\; D_{m}.
$$

The amortized cost of the $i$-th operation $o_i$ is defined as:
$$\hat{c_i} = c_i + \Big(\Phi(D_{i}) - \Phi(D_{i-1})\Big)$$

Therefore, the total actual cost of these $m$ operations equals the total amortized cost plus the net decrease in potential from the initial to the final state.

$$
\sum_{1 \le i \le m} c_i = \left( \sum_{1 \le i \le m} \hat{c_i} \right)
 + \Big(\underbrace{\Phi(D_{0}) - \Phi(D_m)}_{\text{net decrease in potential}} \Big).
$$

For each upper bound $\Box$ for $\Phi(D_{0}) - \Phi(D_m)$, we get a corresponding upper bound for the total actual cost of all operations:

$$
\sum_{1 \le i \le m} c_i \le \left( \sum_{1 \le i \le m} \hat{c_i} \right) + \Box.
$$

The condition $$\forall 1 \le i \le m: \Phi(D_i) \ge \Phi(D_0)$$ in the post is just a special case of deriving upper bounds for the total actual cost, where the upper bound is the total amortized cost. Moreover, it is common to choose $\Phi$ such that $\Phi(D_0) = 0$ and $\Phi(D_i) \ge 0$ for all $i$.

To verify the validity of the potential function for splay trees, we use the following upper bound for $\Phi(T_{0}) - \Phi(T_i)$:

$$\Phi(T_{0}) - \Phi(T_i) \le n \log n.$$


Time complexity of matrix multiplication in Big-Align I am reading the following paper:

Big-Align: Fast Bipartite Graph Alignment.  Danai Koutra, Hanghang Tong, David Lubensky.  International Conference on Data Mining (ICDM 2013).

I'd like to understand one of the paper's claims about the running time of their algorithm.  Their algorithm uses matrix multiplication as follows:

where $n \gg d$, $\bf A,B$ are a $n \times d$ matrices, $\bf U$ is a $n\times n$ matrix, and $\bf S$ is a $n\times n$ diagonal matrix with only the first $d$ diagonal elements being non-zero, with $\bf U,S$ derived from $\bf A$ via a SVD decomposition as indicated above.  $\bf A$ has rank at most $d$, so there are at most $d$ non-zero singular values in $\bf S$. All matrices contain only non-negative values.

The multiplication of a $l\times m$ matrix and a $m\times n$ matrix take $O(lmn)$ time.

How can we compute $\bf P$ in $O(nd^2)$ time?  I think it suffices to compute $\bf B \cdot \bf X$ in $O(nd^2)$ time.  I tried different multiplication orders but cannot arrive at a $O(nd^2)$ time complexity. For example,

  1) first compute $US^{-1}$, then result is a $n\times n$ matrix with only the first $d$ columns being "non-zero". Since $S$ is diagonal with $d$ non-zero diagonal elements, the time complexity is $O(nd)$.

  2) then compute $A^T(US^{-1})$, the result is a $d\times n$ matrix with only the first $d$ columns being "non-zero". The time complexity is $O(nd^2)$.

  3) then compute $B(A^TUS^{-1})$, the result is a $n\times n$ matrix with the first $d$ columns being "non-zero". The time complexity is $O(nd^2)$.

  4) then compute $S^{-1}U^T$ similar to 1), the result is a $n\times n$ matrix with the first $d$ rows being "non-zero". The time complexity is $O(nd)$.

  5) finally the do multiplication $(BA^TUS^{-1})(S^{-1}U^T)$, but this takes $O(n^2d)$ time.

I tried some other order without success to derive $O(nd^2)$ complexity. Am I missing something, or the paper is wrong about this?

D.W. is absolutely right about the time complexity for $\bf X$. Meanwhile, I think the paper is vague on what they are saying and not exact on the complexity.

The paper is about network alignment, where $\bf A$ and $\bf B$ are adjacency matrices for bipartite networks, and $\bf P$ can be viewed as a matrix indicating alignment. $\bf P$ is dependent on $\bf B$ based on the equation. So it is better to view $\bf P$ as a function $\bf P(B)$ of $\bf B$, and $\bf X$ and $\bf Y$ are representation of function $\bf P$.

I believe the paper means first "pre"-compute $\bf X$ and $\bf Y$, store the results somewhere, and then for any given $\bf B$, they can compute the value of $\bf P$ given $\bf B$ using the pre-computed $\bf X,Y$.

The problem is, eventually one has to compute $\bf P (B)$ in order to determine the alignment result between $\bf A$ and $\bf B$. The complexity of that computation is $O(n^2d)$, since $\bf B$ is $n\times d$ and $\bf X$ is $d\times n$, and there is no guaranteed zero rows or columns in $\bf B$ or $\bf X$ to reduce computation.

Thus, the computation of $\bf P(B)$ requires indeed quadratic time. It is just that computation of the function $\bf P$ is $O(d^2n)$.


Proof of SAT is randomly reducible to UNIQUE-SAT I am asking for help to explain some crucial points of the central lemma and it's proof of famous paper NP is as easy as detecting unique solutions by L.Valiant and V.Vazirani.
The proof can be found in the section 2. The proof of the paper.
The idea of the lemma: lemma shows that there is a randomized polynomial - time reduction from SAT to Unique-SAT. Lemma uses GF[2] inner product with polynomial few {0,1} vectors.
Problem in general: I have some difficulties in understanding the definition of the lemma and in usage of GF[2] for proving the lemma.
Specific questions:
Following is the number of citations from the paper with relevant question to the citation.

Lemma 2.1. If $f$ is any CNF formula in $x_1,...,x_n$ and $w_1,...,w_k \in \{0,1\}^n$,

Q:I think $x_1,...,x_n$ are literals, but what are $w_1,..,w_k$? Are they literals or something else? If yes, why to distinct between them and $x$ literals.
A:$w_1,..,w_k$ are the truth assignments.

then one can construct in linear time a formula $f'_k$ whose solution $v$ satisfy $f$ and the equations $v\cdot  w_1=...=v\cdot w_k=0$. Furthermore, one can construt a polynomial-size CNF formula $f_k$ in variables $x_1,...,x_n,y_1,...y_m$,

Q: $x_1,...x_n$ are unknown literals, how can we construct $f_k$ with unknown literals and where $y_1,...,y_m$ came from?

for some $m$ such that there is a bijection between solutions of $f_k$ and $f'_k$, defined be equality on the $x_1,...,x_n$ values.
Proof: It is sufficient to show the lemma for $k=1$. Then, $f'_k$ is
$f \wedge (x_{i_1} \bigoplus x_{i_2} \bigoplus ... \bigoplus x_{i_j} \bigoplus 1)$

Q: this is the most vague point, how do we come to the such construction of $f'_1$ and why showing only $f'_1$ sufficient for the proof.
I hope you forgive me for my naivety. I will appreciate any hint in accordance to the above questions.

Q: $x_1,...x_n$ are unknown literals, how can we construct $f_k$ with unknown literals and where $y_1,...,y_m$ came from?

$x_1, \ldots, x_n$ are variables, each of which can appear as a positive literal ($x_i$) or a negative one ($\lnot x_i$). To construct an equivalent formula $f_1$ of another formula $f_1'$, you don't have to know the values (truth assignments) of $f_1'$. (A simple example is $x_1 \to x_2 \Leftrightarrow \lnot x_1 \lor x_2$.)

The variables $y_1, \ldots, y_m$ are unimportant (at least in this Lemma). The Lemma define the "equivalence" of the two formulas $f_1$ and $f_1'$ by equality on the $x_i$ values (leaving $y_i$ values unspecified).

  Q: How do we come to the such construction of $f'_1$ and why showing only $f'_1$ sufficient for the proof?

Each $f_i$ (and $f_i'$) is independent and similar. Therefore, the case of $f_1'$ is sufficient for the proof. To justify the construction of $f_1' = f \land (x_{i_1} \oplus x_{i_2} \oplus \cdots \oplus x_{i_j} \oplus 1)$, you should prove the following two points:

Each solution $v$ to $f_1'$ satisfies $f$.

This is trivial by the definition of $f_1'$.

Each solution $v$ satisfies the equation $v \cdot w_1 = 0$.

This is the tricky part. We argue as follows:

First, $$v \cdot w_1 = x_{i_1} + x_{i_2} + \cdots + x_{i_j} \text{ (here `+` is over GF[2])} = x_{i_1} \oplus x_{i_2} \oplus \cdots \oplus x_{i_j}$$
The first equality follows from the fact that other $w_l$ with indices $l \neq i_1, i_2, \cdots, i_j$ are all 0 (according to the definition of all $x_{i_j}$).

Because $v$ is a solution to $f_1'$, we have $$x_{i_1} \oplus x_{i_2} \oplus \cdots \oplus x_{i_j} \oplus 1 = 1$$
Thus,
$$v \cdot w_1 = x_{i_1} \oplus x_{i_2} \oplus \cdots \oplus x_{i_j} = 0$$


find a path to visit every node in graph not necessarily once I meet a problem but when I google, there are all Hamiltonian Path Problem: How to find a path to visit every node in directed graph(not necessarily once)?
This problem is different from Hamiltonian Path.
For example:
1 --> 2 -->  3 ↔ 4
             ↕
             5

I have a path $1\rightarrow 2\rightarrow3\rightarrow4\rightarrow3\rightarrow5$ to visit all nodes in this graph, however this graph has no hamiltonian path.
My questions:

What's the terminology of this problem?

Is there algorithm or theorem to determine whether a general graph has such path? If a graph has such graph, how to find the detailed
path?

Thanks

You probably haven't found anything in your searches because this problem is fairly easy to solve, without needing any fancy methods.
If the graph is strongly connected, then it is easy.  Let $s$ be the starting node.  Pick any vertex $v$ you haven't visited yet, and append a path $s \leadsto v$ followed by some path $v \leadsto s$ (both must exist, since the graph is strongly connected).  Repeat, appending to the end of the path, until every vertex has been visited.
If the graph isn't strongly connected, decompose it into a dag of scc's.  Then you can reduce the problem to finding a path through this dag (within a scc, use the algorithm of the first paragraph).  You can find a path to visit every node in a dag iff the dag is itself a path, i.e., it has the structure $v_1 \to v_2 \to \dots \to v_k$, and then it is trivial to write down this path.
This is not a Hamiltonian path, since it may visit the same vertex multiple times.


Why isn't this undecidable problem in NP? Clearly there aren't any undecidable problems in NP.  However, according to Wikipedia:

  NP is the set of all decision problems for which the instances where the answer is "yes" have [.. proofs that are] verifiable in polynomial time by a deterministic Turing machine.

  [...]

  A problem is said to be in NP if and only if there exists a verifier for the problem that executes in polynomial time.

Now consider the following problem:

  Given a Diophantine equation, does it have any integer solutions?

Given a solution, it's easy to verify in polynomial time that it really is a solution:  just plug the numbers into the equation.  Thus, the problem is in NP.  However, solving this problem is famously known to be undecidable!

(Similarly, it seems the halting problem should be in NP, since the "yes"-solution of "this program halts at the N-th step" can be verified in N steps.)

Obviously there's something wrong with my understanding, but what is it?

I think you misunderstood what it means to solve a diophantine equation, and Matiyasevich's indecidability theorem.

Matiyasevich proved that for every RE set $S$ there is a diophentine equation $f(n;x_1,...,x_k)$ such that $n \in S$ only if there exists integer coefficients $x_1$,..,$x_k$ such that $f(n;x_1,...,x_k) = 0$. In particular, the halting problem is a typical RE set, and so solving the above problem is undecidable.

Note that $x_1, ... x_k$ are not bounded in size, and in general can be arbitrarily large, so there is no "polynomial sized certificate" evident in this problem.

To expand: the integers $x_1, ... , x_k$ need to be written in binary to be a certificate. Since these integers can be arbitrarily large (regardless of $n$), we have that the certificate is not polynomial in $\log n$ or more importantly, not bounded by and computable function.

Every problem in $\mathsf{NP}$ however, has a certificate that is bounded by some polynomial $p(N)$ (where $N$ is size of input). So $\mathsf{NP}$ questions are trivially decidable, since you can enumerate every possible bit string upto length $p(N)$ and if none of them certify the input, return false. If some does then return true.


Lambda Calculus inductive substitution definition I'm reading Lambda-Calculus and Combinators: An Introduction, and there's the following definition of $\lambda$-substitution:

$FV(P)$ stands for the set containing all free-variables from $P$.

Definition 1.12 (Substitution) For any $M, N, x$, define $[N/x]M$ to be the result of substituting $N$ for every free occurrence of $x$ in $M$, and changing bound variables to avoid clashes. The precise definition is by induction on $M$, as follows (after [CF58, p.94]).
(a) $[N/x]x \equiv N$
(b) $[N/x]a \equiv a$ for all atoms $a \not \equiv x$
(c) $[N/x](PQ) \equiv ([N/x]P)([N/x]Q)$
(d) $[N/x](\lambda x.P) \equiv (\lambda x.P)$
(e) $[N/x](\lambda y.P) \equiv P$ if $x \not \in FV(P)$.
(f) $[N/x](\lambda y.P) \equiv \lambda y. [N/x]P$ if $x \in FV(P)$ and $y \not \in FV(N)$.
(g) $[N/x](\lambda y.P) \equiv \lambda z. [N/x][z/y]P$ if $x \in FV(P)$ and $y \in FV(N)$.

I do understand that:

$(a), (b)$ are the base cases for this induction.
$(d)$ exists per definition, as one is not allowed to substitute bound variables.
$(g)$ prevents a bound variable from changing to a free one. It does this by first substituting a bound variable.

My question is: If one deletes $(d)$ and allows bound variables to be substituted, is $(g)$ strong enough to handle it without messing up everything?
I'm asking this because $(d)$ seems to prevent the following $\alpha$-equivalent substitutions.
$$ [y/x] ~~ \lambda x. x \equiv \lambda y.y $$

"If one deletes $(\mathrm{d})$ and allows bound variables to be substituted..."

The problem here is that substitution of a bound variable makes little sense, since one substitutes a variable (let's forget for a moment it should be free) with a term, which may very well be an abstraction or application, but not a variable.

Let me illustrate this by example. What if we are trying to substitute a bound variable with a term, which is not a variable? Like this:
$$[(y\; y)\ / \ x]\ \lambda x. x.$$
What should we do?

Produce $\lambda (y\; y). (y\; y)$? It is not a well-formed term, so the answer is no.
Another choice would be to leave the binding instance intact and make $\lambda x. (y\; y)$ a result. Let's not take into account if it makes sense, at least it is syntactically correct. This variant causes us major troubles too: it will mess up scopes and render $\beta$-reduction useless. And our end goal is to define $\beta$-reduction via substitution.

  $(\mathrm{g})$ prevents a bound variable from changing to a free one. It does this by first substituting a bound variable.

It does not use substitution, it uses renaming, which is a different notion.

  "...is $(\mathrm{g})$ strong enough to handle it without messing up everything?"

$(\mathrm{g})$ does not tell us anything about substitution of bound variables, since it has the condition $x \in \mathrm{FV}(P)$


Given a DFA A, give a formal construction of a PDA with three states M such that L(A) = L(M) given a Deterministic Finite Automata, I am looking for a formal construction of Push Down Automata with 3 states such that the languages of the DFA and the PDA are the same. How we can prove correctness?

Any help appreciated.

Thanks!

From the NFA $N$ construction an equivalent context-free grammar $G$ using the standard construction for this, and then construct a PDA $M$ such that $L(M) = L(G)$. The standard construction will (given a suitable definition of the notion of pushdown automaton) give us an automaton with three states only.

The automaton will simulate the leftmost derivations of $G$, and its stack symbols include the set $V$ of nonterminals and the set $\Sigma$ of terminals as well as a bottom marker $\$$. Initially, $\$$ is placed on the stack together with $S$. The main loop of the automaton is that involving the state $q_2$: If a nonterminal $A$ appears as the topmost symbol on the stack and there is a production $A \rightarrow w$ in $G$, then $A$ is replaced by $w$ in reverse. If a terminal $a$ appears as the topmost symbol on the stack and the next input symbol to be read is also $a$, then the automaton proceeds. Finally, if all input characters have been read and the bottom marker is the only symbol on the stack, the computation succeeds.


Are all NP-complete languages log-space reducible to each other? NP-complete languages are reducible to each other in polynomial time. Does this mean that they are also log-space reducible to each other?

It seems as if this is true because in log-space, we can have polynomially many computations.

Wikipedia makes the following points:

It is unknown whether all NP-complete languages are NP-complete also with respect to logspace reductions.
However, "all known" NP-complete languages are NP-complete also with respect to logspace reductions.
There are some hints that a weaker class of reductions, AC0 reductions, may result in a different notion of NP-completeness.


Does the language $\{(1^n2^n)^t \mid t,n\ge0\}$ contain the string $121122$? Does the Context Free Language $\{(1^n2^n)^t \mid t,n\ge0\}$ contain the string $121122$? Does $t$ fix $n$? I think the string belongs to this language.

$t$ and $n$ are independent numbers. Any string in the language consists of $t$ units, where each unit consists of $n$ $1$s followed by $n$ $2$s.  In particular, then, the string generated by any choice of $t$ and $n$ contains $tn$ $1$s and $tn$ $0$s.


Is there an undecidable finite language of finite words? Is there a need for $L\subseteq \Sigma^*$ to be infinite to be undecidable?

I mean what if we choose a language $L'$ be a bounded finite version of $L\subseteq \Sigma^*$, that is $|L'|\leq N$, ($N \in \mathbb{N}$), with $L' \subset L$.  Is it possible for $L'$ to be an undecidable language?

I see that there is a problem of "How to choose the $N$ words that $\in$ $L' "$ for which we have to establish a rule for choosing which would be the first $N$ elements of $L'$, a kind of "finite" Kleene star operation. The aim is to find undecidability language without needing an infinite set, but I can't see it.

EDIT Note:

Although I chose an answer, many answers and all comments are important.

Yes, there is a need for $L$ to be infinite in order to be undecidable.

To add up on the answers of Raphael and Sam, you should think about "decidable" as things that a computer-program can solve. The program required is very simple, it just needs to output "Yes" for elements in $L$, or otherwise, say no.

So the more "complex" $L$ is, the longer the program you are required to write. In other words, the longer the program you run, you can check more things... So if someone gives a language $L$ which is finite, say $L=\{ a_1, a_2, \ldots, a_n\}$, you can write the following program:

if INPUT = $a_1$ output Yes;
if INPUT = $a_2$ output Yes;
...
if INPUT = $a_n$ output Yes;
output No;

Now, if some one gives you a larger $L$ (yet finite), you will just write a longer program. This is always true, and any finite $L$ will have it's own program. The only "interesting" case is what happens when $L$ is infinite - your program cannot be infinite.

The issue of "undecidability" is even more interesting: its those (infinite) $L$'s that have no program that works correctly for them. We know that such languages must exists since there are way more (infinite) languages $L$ than the number of programs of finite (but unbounded) length.


Bias of first values produced by a family of RNGs Suppose I'm doing a large number of pseudo-random but deterministic experiments, where each experiment requires generating several random numbers.

I'm approaching this by having each experiment use a random number generator seeded with a random-looking seed - e.g. hash of the index of the experiment. This is especially convenient for parallelizing my experiments.

I'm wondering if this is a sound way to get good randomness. In particular, this article points out at the end that the first value returned by e.g. Java's random generator (LCG) is highly biased even if you vary the seed.

How can I avoid this bias? Is it sufficient to throw away one or two numbers, as that article suggests? Is there any research on this topic? (I wasn't able to find the right keywords)

Would, e.g., Mersenne Twister behave better?

Yes.  This general approach (use a hash of the index as seed to your prng) is a sound way to perform repeatable but pseudorandom experiments.

The most critical factor is to choose the pseudo-random number generator wisely, so that its statistical properties are sufficient for the kind of simulations you are doing.  Some pseudo-random number generators are especially awful: for instance, on some platforms rand() is terrible (its least significant bit alternates between 0 and 1), and Excel's RAND() has been criticized in the statistical literature.  So, choose wisely.  But this issue is more a matter of choosing a suitable pseudo-random generator, which is something you need to do anyway.

It's important to include the hashing step.  If you don't do that, then you're feeding closely related seeds into the pseudo-random generators.  For some pseudo-random generators, bad things might happen: you might get closely related outputs.  For instance, that's exactly what the article you mentioned is warning about, when you use Java's Math.random().  Using a good hash function will fix this, because now the seeds to the pseudo-random generator will look unrelated (each bit will be different with probability about 1/2, etc.).

In particular, if you're concerned about this risk, one extremely effective solution is to use a strong cryptographic hash function (e.g., SHA256) as your hash.  This ensures that the resulting seeds will look entirely unrelated.  After all, any detectable relationship in the resulting seeds would likely count as a "break" of the cryptographic hash function, and would be huge news.  So, heuristically, if you use a cryptographic hash function to hash the index and use its output as the seed, you're likely on safe ground.  This can be formalized using the random oracle model, but I'll spare you the technical details -- you can read more about that sort of analysis in the cryptographic literature if you really want, but in the interests of space, I'll spare you all the mathematics.

I expect that using a good hash will be more effective/reliable than throwing away the first few numbers, and more effective than trying to choose a different pseudo-random number generator.  Those alternatives are a crapshoot: they might work, but they might not.  In contrast, there is sound science behind the "hash the index and use the result as a seed" approach.


Strengthening a given attack on discrete log I am trying to prove the following claim:

Let $(G,*)$ be a cyclic group of size $m$ with generator $g$. Assume
there exists some adversary $A'$ of size
$T'=\frac{\left(T-O\left(\log m\right)\right)}{2}$, for some
$T$, such that $$\mathbb{P}_{b\gets
 G}\left[A'(b)=\log_{g}(b)\right]>\frac{1}{2}.$$ Show that there exists
an adversary $A$ of size $T$ such that $$\mathbb{P}_{b\gets
 G}\left[A(b)=\log_{g}(b)\right]>\frac{3}{4}.$$
Assume multiplication over $G$ requires $O(1)$ circuit.

How can I prove this claim? Intuitively, since $A$ is bigger than $A'$ in about $O(\log m)$, the construction should be based on dividing the problem into halfs recursively, as in binary search. However, I can't think of any clever way to do that...

Suppose that we had a stronger guarantee: $A'$ is a randomized algorithm, and for every $b$, $\Pr[A'(b) = \log_g b] > 1/2$, over the randomness of the algorithm. In that case, you would construct $A$ by running $A'$ several times, and checking each output until you get one that satisfies $g^{A'(b)} = b$.
Now suppose that the guarantee is $\Pr_b[A'(b) = \log_g b] > 1/2$. You would like to somehow get "independent samples" of $A'(b)$. You can accomplish that using randomized self-reducibility. I'll let you fill that out since it's your exercise. The resulting algorithm is randomized, but by choosing the optimal randomness, you get a deterministic (but non-uniform) algorithm with the same guarantees.


Is the word problem for regular languages in ALogTime? Given a regular language (by a sparse or dense matrix describing the graph of the NFA) (initially the description was supposed to be a regular expression) and a word, can the problem whether the word belongs to the regular language be decided on a (random access) alternating Turing machine in a logarithmic amount of computation time? (The many links above try to compensate for the fact that I didn't find a nice self-contained description of ALogTime.) The length of the input is the length of the description of the regular language plus the length of the word.

If the regular expression is not fixed, it is rather doubtful that your problem belongs to ALOGTIME. However, the phrase word problem usually refers to a fixed setting, which in this case means that the regular language is fixed.

If the regular language is fixed, this is apparently shown in Barrington's famous paper. Alternatively, you can describe a logtime game for deciding the word problem for regular languages. The game starts with the YES player stating the final (accepting) state and the state at the middle (the initial state is of course fixed). The NO player then chooses one of the halves, and the game continues until it comes down to a word of length 1, in which case the problem can be settled by examining one character of the input.


Add edges to undirected graph to make connected and minimize longest path I am trying to find an efficient algorithm to solve to following problem: Given an undirected disconnected graph, I want to add as few as possible edges to make to graph connected while minimizing the number of vertices on the longest path in the resulting connected graph. As a result I need the number of vertices on the longest simple path in the resulting graph.

For example, given a graph with the following edges:

1 0
2 0
4 3
5 3

There are multiple ways to add edges to make it a connected graph. But since I want to minimize the number of vertices on the longest path in the resulting graph, I have to add an edge between 0 and 3. Now the path with the most vertices contains 4 vertices (2 -> 0 -> 3 -> 5). If I had added an edges between 2 and 4 then the path with the most vertices would've been 1 -> 0 -> 2 -> 4 -> 3 -> 5.

Another example, given a graph with the following edges:

0 1
1 2
3 4
5 6

Here two edges need to be added: between 1 and 3 and between 3 and 5. The path with the most vertices then contains 5 vertices.

My approach was to first use DFS to identify all components. Then, for each component, I find the longest path in that component, I take the vertex that is in the middle of each of those paths and connect them. This results in one connected graph. In that resulting graph I can find the path with the most vertices. I suspect that there must be a more efficient approach to this, especially since it needs to work for a disconnected graph with at most $10^6$ vertices. Hopefully someone has a better idea on how to solve this.

Clearly, the number of added edges is one less than the number of connected components in the graph, since we can decrease this number by one by adding an edge and we seek the minimum number of added edges.

The trick is to add the edges between central vertices of the connected components. A central vertex of a connected  component is a vertex that has minimum distance to the farthest vertex to this vertex in the component (we call this distance the eccentricity). So it is a vertex that minimises the eccentricity.

Here goes the algorithm. In each step we find the connected components of the graph and we handle them as different graphs say $G_1, \dots, G_l$. Note that the task is to add $l-1$ edges between these graphs in a way that makes them connected. Each time we add an edge we will combine two graphs and decrease $l$ by one until it gets to the value 1.

After we found the connected component we find a central vertex in each of them (central vertices might not be unique but we can choose any of them). We keep for each component a central vertex and the value of its eccentricity. Now in each step we combine to graphs, we distinct two cases.
- The minimum eccentricities are equal, then any of the two central vertices can be chosen as a central for the new graph and the new eccentricity is the previous one plus one. (Try to prove the correctness and optimality of this statement).
- The minimum eccentricities differ. Keep the central with the greater eccentricitiy. Its eccentricity does not change. (Also try to prove this).

The eccentricity of each component can be built using a BFS from each vertex in total quadratic time in the size of the input graph. Each iteration can be implemented in constant ime (for example keep a stack of pairs (central, eccentricity) and in each step pop two elements, unify them and push thr new pair back to thr stack. each step decreases the size of the stack by one and hence we end after $l-1$ steps.

The correctness of the previous two cases implies the correctness of the algorithm and that it does not matter in which order you process the components. Hence we get a total quadratic running time. There are some heuristics to improve the running time of computing central vertices if connected components (which is the only quadratic factor in our algorithm and gence the bottleneck) including pruned BFS. However, as far as I know, this is the best achievable asymptotic running time.


Random algorithm termination Suppose I have an algorithm that works as follows when invoked: it calls itself recursively with probability $0 < p < 1$ and terminates with probability $1-p$. Does this algorithm terminate? On the one hand you can show that $\lim_{n \to \infty}p^n = 0$, so it must terminate at some point before infinity. On the other hand it also seems reasonable to say that it is possible for the algorithm to call itself repeatedly indefinitely. What is the correct interpretation?

The question "Does it terminate?" isn't well-formed.  You need to define more precisely what you mean by that question before it can be answered.

Is it guaranteed to terminate on all possible execution traces?  No.  There exists an execution trace where it never terminates.
Does it terminate with probability one?  Yes.  If you flip a coin until you first get heads, the probability of getting a never-ending sequences of tails is zero.
Is the expected number of repetitions until termination finite?  Yes.  If you flip a coin until you first get heads, the expected number of flips is finite (it is the expected value of a geometric distribution).

So, the answer to the question depends upon precisely which of those questions you meant to ask.  Normally, that's about all we can say.

Usually, if it matters, we try to define what we mean by "terminate" more precisely.  For instance, in the definition of the Halting Problem, "terminates" is specified to mean "guaranteed to terminate on all possible inputs and all possible execution traces", and the formalization of the Halting Problem implicitly restricts us to deterministic algorithms (more precisely, to Turing machines, which are necessarily deterministic; they don't have access to randomness).  Anyway, in general, if the differences matter, it's your job to specify exactly which meaning you have in mind.


Space complexity analysis of binary recursive sum algorithm I was reading page 147 of Goodrich and Tamassia, Data Structures and Algorithms in Java, 3rd Ed. (Google books).
It gives example of linear sum algorithm which uses linear recursion to calculate sum of all elements of the array:

Algorithm linearSum (arr , n)
    if (n == 1)
        return arr[0]
    else
        return linearSum (arr , n-1) + arr[n-1]
end linearSum

And the binary sum algorithm which uses binary recursion to calculate sum of all elements of the array:

Algorithm binarySum (arr, i, n)
    if (n == 1)
        return arr[i]
    return binarySum (arr, i, ⌈n/2⌉) + binarySum (arr, i+⌈n/2⌉, ⌊n/2⌋)
end binarySum

It further says:

  The value of parameter $n$ is halved at each recursive call binarySum(). Thus, the
  depth of the recursion, that is, the maximum number of method
  instances that are active at the same time, is $1 + \log_2 n$. Thus the
  algorithm binarySum() uses $O(\log n)$ additional space. This is big
  improvement over $O(n)$ needed by the linearSum() algorithm.

I did not understood how the maximum number of method instances that are active at the same time, is $1 + \log_2n$.

For example consider the below calls to method with method parameters given in rounded box:

Then in two recursive calls of second row from top, $n = 8$. So, $1 + \log_2 8 = 4$. Now I dont get what maximum limit this 4 represent?

In a given tree, all the vertices of this tree correspond to binarySum() calls.
The value of parameter n to binarySum() is halved at each recursive call.
Also, each recursive call finishes after all its children finish. Thus at each recursive call, number of active calls include all the ancestor calls in call sequence.
Thus when any binarySum() call corresponding to leaves in above call tree is active, its parent, grandparent and so on are still active as well.
Thus, the depth of the recursion, that is, the maximum number of method instances that are active at the same time, which is always equal to the height of the recursive calls tree is 1 + log$_2$n.
For example in binarySum() recursive calls tree above, with n = 8, at any of the calls correspnding to leaves,

Why does the depth of recursion affect the space, required by an algorithm? Each recursive function call usually needs to allocate some additional memory (for temporary data) to process its arguments. At least, each such a call has to store some information about its parent call - just to know where to return after finishing. Let's imagine you are performing a task, and you need to perform a sub-task inside this first task - so you need to remember (or write down on a paper) where you stopped in the first task to be able to continue it after you finish the sub-task. And so on, sub-sub-task inside a sub-task... So, a recursive algorithm will require space O(depth of recursion).

@randomA mentioned the Call Stack, which is normally used when a function invokes another function (including itself). The call stack is the part of the computer memory, where a recursive algorithm allocates its temporary data.


Express semantic duplicates of records formally I'm working on a paper about record linkage and duplicate detection and want to visualize my definitions of "hard" and "semantic" duplicates.
Hard ones are a 100% match; where's only true or false-
Semantic ones have different variations but still are representing the same thing.

Now I'd like to write it as a set but actually I have forgotten all about this.

Here are my thoughts about it.
All 4 records are part of the Set "Persons" p

For both: Values are already filtered according to custom settings.
Hard Duplicates

  {[Name]Max; [Surname] Mustermann} ≙

  {[Name]Max; [Surname] Mustermann} ≠

  {[Surname]Max; [Name] Mustermann} ≠

  {[Name]Max; [Surname] M.}

Semantic Duplicates

  {[Name]Max; [Surname] Mustermann}

  {[Name]Max; [Surname] Mustermann} ≙

  {[Surname]Max; [Name] Mustermann ≙

  {[Name]Max; [Surname] M.} ≙

Any help is appreciated

The basic mathematical concept at play here is a binary relation. For a certain measure of similarity, two records are either similar or not. Formally, a binary relation assigns a truth value (true or false) to every ordered pair of records. The usual notation to state that two records are similar is $r_1 \approx r_2$ where $\approx$ is the notion of similarity. There can be multiple notions of similarity (allowing for more or fewer differences between records).

Given the intended purpose, any notion of similarity should be reflexive: a record is similar to itself. Any notion of similarity should probably be symmetric: if $r_1$ is similar to $r_2$ (for a given notion of similarity) then $r_2$ is similar to $r_1$ for that same notion of similarity. It's less clear whether the similarity relation should be transitive, which would make it an equivalence relation. If $r_1$ is similar to $r_2$ and $r_2$ is similar to $r_3$, does that make $r_1$ similar to $r_3$? Or in other words, is a duplicate of a duplicate a duplicate? If your intuition of similarity is that the records are at most a certain distance from each other, then no (this thread on Math.SE discusses this intuition). But if you think of all records falling into a well-defined bucket, with sufficiently similar records ending up in the same bucket, then you have an equivalence relation, and the buckets are called equivalence classes. If you have a way of defining a privileged element in each equivalent class (a “completed” or “presentation” version of the record), that's called a canonical representation.

Equality is the finest (i.e. most discriminating) equivalence. It is normally written $=$. A generic equivalence relations is typically written $\equiv$. If you need to consider more than one equivalence relation, then the typical notation scheme is to use $=$ or $\equiv$ with some ornaments on it.

The terminology “hard duplicate” or “soft duplicate” isn't standard, but it's comprehensible. “Equal” vs. “equivalent” or “equal” vs. “similar” are more standard terms.

To define an equivalence, a typical approach is to give rules: “if $r_1$ and $r_2$ are such that … then the two records are equivalent”. For example, you might have a rule that if two records are the same except for letter case variations on the name field then they're equivalent. Two records are equivalent if there's a way to find a chain using those rules plus the “built-in” reflexivity, symmetry and transitivity rules from one record to the other.

To define a non-transitive similarity, a typical approach is to define a distance between records.

The general problem of determining when records in a database should be treated as representing the same entity is called data normalization. With respect to database design, that's database normalization.


Round Robin Scheduling: No process in Ready Queue First post here, glad I found this exchange. I am in my Operating Systems course at university learning process scheduling. In my homework assignment we have to fill out a simulated scheduling chart along with the corresponding Gant chart. The arrival time of the first process is at time 0, and it's service time is 5 seconds. The second process doesn't arrive until time 7. The time quantum is 6. How do I fill out the gant chart if nothing is in the queue?

your first process will take time only upto 5 seconds as its service time is only upto 5 seconds and then you have to keep blank space between 5-7 and then your next process arriving at 7 would be processed,i think.


Assigning keys to the nodes of a Binary search tree given its shape Let's say I have a Binary search tree with $n$ nodes and know its shape. I also knows each node has a unique key that is an integer between $1$ and $n$ (inclusive). This would make the assignment of the keys to the nodes unique, given its shape. What is a good $O(n)$ algorithm for assigning each node its correct key? For example, the trees with $n=3$ nodes are shown below. Even if I  removed the keys assigned to each node, I could have labeled them manually. Now, I want an algorithm for this. The motivation here is that I'm obtaining a Binary search tree through some mechanism (and the tree has the right shape), but that mechanism is labeling the nodes incorrectly. See: https://math.stackexchange.com/questions/4051677/converting-a-dyck-path-to-corresponding-binary-search-tree.

Simply assign key $i$ to the $i$-th node to appear in an in-order depth-first traversal of the BST.


Counting Inversions Using Merge Sort In Corman, Introduction To Algorithms, 3rd edition, question 2-4 it asks to count the number of inversions in a list of numbers in $\theta( n \lg n )$ time.  He uses a modified Merge Sort to accomplish this.  However, there is something in his algorithm which seems redundant / unnecessary to me:

MERGE-INVERSIONS(A, p, q, r)
n1 = q - p + 1
n2 = r - q
let L[1 ... n1 + 1] and R[1 ... n2 + 1] be new arrays
for i = 1 to n1
    L[i] = A[p + i - 1]
for j = 1 to n2
    R[j] = A[q + j]
L[n1 + 1] = infinity
R[n2 + 1] = infinity
i = 1
j = 1
inversions = 0
counted = FALSE
for k = p to r
    if counted == FALSE and R[j]  < L[i]
        inversions = inversions + n1 - i + 1
        counted = TRUE
    if L[i] <= R[j]
        A[k] = L[i]
        i++
    else A[k] = R[j]
        j++
        counted = FALSE
return inversions

The counted variable seems redundant to me and I would have written the last for loop as follows:

inversions = 0
for k = p to r
    if L[i] <= R[j]
        A[k] = L[i]
        i++
    else A[k] = R[j]
        inversions = inversions + n1 - i + 1
        j++
return inversions

What am I missing, or is counted really unnecessary?

We can show that after every iteration of the for-loop in question, counted is FALSE. Therefore, inversions = inversions + n1 - i + 1 is executed if and only if j++ is executed in the same iteration (both are guarded by R[j] < L[i]). Since neither i nor j is changed between evaluation of the two if conditions, this implies that your version is equivalent.

   We perform an induction over k. Before the loop, counted is explicitly set to FALSE. In any given iteration, we start (by induction hypothesis) with counted == FALSE. If L[i] <= R[j], counted is not changed throughout the current iteration. If the opposite is the case, counted is first set to TRUE, but reset to FALSE in the else block. For this, we note that the truth value of R[j] < L[i] remains unchanged from the first to the second if.

I guess the extra block is there for didactic reasons.


Why do errors occur in programming? I like to reduce the number of exceptions raised in my code, and I thought it might help to consider why these exception are raised in the first place, and whether they are a really a fundamental part of code or just an artefact of not really finishing the program.

As a related note I hear OS programming requires avoiding errors where possible, perhaps there are some answers there.

Errors occur in programming because programs are written by humans and humans make errors.


What do these arrows in design pattern diagrams mean? I am learning about software design patterns by reading Wikipedia pages about them. A lot of the patterns such as the bridge pattern have diagrams with boxes and different kinds of arrows:

Source: Wikipedia

Do these diagrams stem from a standard? Why do some arrows have different ending markings? Also, why are some of them dotted?

The arrows mean distinct things. This is a UML (unified modeling language) diagram. Rules for reading and writing these diagrams are pretty well-established, and you should be able to look up some references.

In that diagram, the hollow arrow means generalization (i.e., inheritance, IS_A), and the hollow diamond means aggregation (i.e., a kind of association, HAS_A). The dotted line connects a comment/label and contains auxiliary/meta information (I believe, but double check this one).


Height of a full binary tree A full binary tree seems to be a binary tree in which every node is either a leaf or has 2 children.
I have been trying to prove that its height is O(logn) unsuccessfully.
Here is my work so far:

I am considering the worst case of a full binary tree in which each right node has a subtree, and each left node is a leaf.
In this case:
$N = 2x - 1$
$H = x - 1$
I am going nowhere trying to prove that $H = O(\log(N))$

Furthermore, we know that leaves l is bounded by $h+1 <l<2^h$.
Internal nodes is bounded by $h<i<2^{h-1}$.
All this proves is that number of nodes $n=i+e$ is $<= 2^{h+1} - 1$ i.e. $\log(n) <= h$. But this does not take me anywhere closer to prove that $H = O(\log(n))$

Your claim is incorrect (which might make it really hard to prove...)
Indeed, as you describe, you can have a full binary tree of height $O(n)$: Let every right child be a leaf, and every left child have 2 children, until some level in which it has two leaf-children.

It holds that $x-1\in \theta(2x-1)$, and in particular, $x-1\in \omega(\log(2x-1))$, so $H\notin O(\log N)$.


Need help understanding textbook solution I am studying for my final exam in coding-theory class, and as textbook provides poorly written solution to the exercise question, I decided to ask the question here, hoping for more clarification.

Question:

  If $C_1$, $C_2 \subseteq V$ are linear codes, with generator matrices $G_1$, $G_2$
  and parity-check matrices $H_1$, $H_2$, explain how to find a
  generator matrix for $C_1 + C_2$ and a parity-check matrix for $C_1 \cap C_2$.

Textbook solution:

  Form a generator matrix $G$ for $C_1 + C_2$ by adjoining the rows of
  $G_2$ to $G_1$ and then using elementary row operations to eliminate
  linearly dependent rows. A similar process with the rows of $H_1$ and
  $H_2$ gives a parity-check matrix $H$ for $C_1 \cap C_2$.

Clarification: My question is by word "adjoining", solution is referring to addition of two matrices or adjudicating them. Also, what is definition of "linearly dependent row"? If you could provide an example, it would be great.

Note:
I really don't like asking this type of question but combination of unhelpful professor and awful textbook made me to do this.

Try to think of it that way. A code $C$, is just a subspace. A generator matrix is simply one basis of that subspace (i.e., each row is a basis element).

So in order to create the subspace $C_1+C_2$, you can take a basis of $C_1$ (for instance, the rows of its generator matrix), and add to it a basis of $C_2$. The new set is not a basis anymore, but if you eliminate dependencies it will be, and this new basis can be seen as the generator matrix of the new subspace (why?).

Same goes with $C_1 \cap C_2$. This subspace contains only elements which are both in $C_1$ and in $C_2$. Stated via  parity matrix, it contains only vectors that are in the kernel of $H_1$ and in the kernel of $H_2$. What happens if you build a matrix $H$ that contains both the rows of $H_1$ and of $H_2$? Which vectors will be in the kernel now?


Is it possible to get information from websites as a human? If I want to read any websites and get some information as names (or dates) on some part of the site as a human. What solution I could use in order to get these datas using deep learning or machine learning?. Is it possible?.. it is not necessary artificial inteligence? .... or maybe it might be as a part of a Phd thesis about machine learning?... If someone has a PAPER about it, could you share it with me?.

Sorry I dont know a lot about this topic.

The comments by David and D.W. are accurate. Your question is way too broad. But to give you a hint were you might start to dive deeper into the field, here is a very general answer to your question:

Yes, it is possible. Although, the methods we have are at the moment not as good as human performance (not surprisingly—the task is very hard; side note: If you restrict the text genre and the kind of information you are looking for strongly enough (say gene interactions in biomedical texts) then it is actually possible to achieve near-expert performance).

The name of the task you are describing is information extraction.

An excellent text book which covers elementary methods of it (as well as lots of basics in natural language processing you need to know for that) is this one. There should be free pdf version around in the web as well.


micro programming and hard wiring I have a question about the details of microprogramming and hard wiring in CPU architecture.

in hardwiring, we write a code the compiler translates it to the ISA. then ISA is run in the hardware.

in microprogramming, we write a code the compiler translates it to the ISA(which is much more complicated than the ISA in hardwiring)then a device(I don't know the name) translates it to the hardware language.

am I correct?

Not Exactly. The microcode is a layer "below" the ISA and the Hardware-level functionality. That is, when you write some machine code like MOV or ADD or MUL (which are part of the ISA), the microcode translates it into multiple simpler activities (e.g., "move info from A register to B register. ADD this registers. Load from the Memory. etc.). These simple activities eventually perform the instruction you coded.

For instance, think of the MUL instruction that can be micro-coded as multiple add and subtract, like in done in elementary school.


What is the time complexity of an algorithm that calls a polynomial time algorithm? I'm having a difficult time understanding time complexities of algorithm. I know that a polynomial time is of the form O(n^m) where m is a constant. Consider the following case where A is a list of elements:

Foo(A)
for each element a in A:
    for each element b in A-a:
        Polynomial-Time-Algorithm-Bar(A, a, b)

If n is the size of A,

1) Am I right in understanding that Foo(A) is also a polynomial time algorithm , because the function Polynomial-Time-Algorithm-Bar is called (n-1)*n times ?

2) When would an algorithm making calls to another polynomial time algorithm become exponential. I understand that if it has a running time of O(n^m) and m is variable and n is constant, then it would be exponential. Can you give me an example of such a case in the above example?

I assume $n$ is the number of entries in array/set A.

Yes, since polynomials are closed against multiplication; specifically, $n(n-1) \cdot p(n)$ is always polynomially bounded as long as $p(n)$ is polynomially bounded.
As a consequence, the only way to achieve exponential running-time by calling a polynomial-time algorithm with parts of the original input is to call it exponentially often.

Example:

Foo(A)
  if |A| >= 2
    a = A[0]
    b = A[1]
    Polynomial-Time-Algorithm-Bar(A, a, b)
    Foo(A - a)
    Foo(A - b)

The number of calls to PTA-Bar is given by

$\qquad\begin{align*}
  C(0) &= 0,\\
  C(1) &= 0,\\
  C(n) &= 2C(n-1) + 1, \qquad n \geq 2,
\end{align*}$

which solves to
$C(n) = 2^{n-1} - 1$ for $n \geq 1$. Ergo, the running time of Foo is in $\Omega\bigl( 2^n \cdot p(n) \bigr)$ if PTA-Bar takes time $p(n)$.


What is the system's mean time to failure? I have the following homework problem:

A 10 TB disk drive has an MTTF of 6,000,000 hours.  How much data can we store in a system comprised of these disks, if we want the system MTTF to be at least 1.2M hours?
If we are allowed to make it redundant (i.e., two of them operating in a parallel mode), and if the MTTR is 120 hours, what is the system MTTF?

I think it is
$\qquad \operatorname{MTTF}(\text{System}) = \frac{1}{\sum_i \frac{1}{\operatorname{MTTF}_i}}$.

For part 1, its simple. You need to find the $x$ (as defined below) for which MTTF(system) = 1.20M.

So $1.20 * 10^6 = \frac{1}{[(\frac{1}{6*10^6})*x]} \implies x = 5$.

We can have 5 disks (50 TB) if we want an MTTF(System) = 1.2M.

Part 2 is homework for you.


Algorithm for detecting overlaps This is a real-world application, not a student assignment.

Suppose a list of events of that have startTime and endTime, and some overlap information. In pseudocode:

class Event {
    Time startTime;
    Time endTime;
    bool overlapsStart;
    bool overlapsEnd;
}

Events are considered overlaping if and only if their times intersect, but it's not considered overlap if some event just "touches" another (starts exactly when some other finishes).

There are two types of event: NormalEvent and EmptyEvent.

What I want?

For each event in the list, I want to:

1) Remove all EmptyEvents that overlap another event of any type. In special, if some EmptyEvent overlaps another EmptyEvent, only one needs to be removed, so that the overlap ceases.

2) The NormalEvents are first ordered by startTime, and then their booleans are set:

overlapsStart is true if the event overlaps some event that comes before it.
overlapsEnd is true if the event overlaps some event that comes after it.

A trivial example:

event1 = 6:00AM ➜ 8:00AM

and

event2 = 7:00AM ➜ 9:00AM

then:

event1.overlapsStart == false
event1.overlapsEnd == true

event2.overlapsStart == true
event2.overlapsEnd == false

Another example:

Now, this is what happens if some event "contains" another:

event1 = 6:00AM ➜ 9:00AM

and

event2 = 7:00AM ➜ 8:00AM

then, first event1 is put before event2, since it starts before. Then:

event1.overlapsStart == false
event1.overlapsEnd == true

event2.overlapsStart == true
event2.overlapsEnd == false

Naive implementation: I could analyze each event in turn, one by one, looking at all other events. That's easy, however this is too slow for a large number of events.

My question: What's an efficient way of solving this?

I suppose you want to delete as little EmptyEvents as possible.

In that case, you can achieve what you want in O(nlog(n)) time, where n is the number of events.

Proceed as follows:

First, get rid of the EmptyEvents which overlap with a NormalEvent. To do so, put all your starting and ending times in a vector and sort them in increasing order, breaking ties by putting end-times before start-times. Set a counter = 0 and an empty unordered set S. Now go through your vector of times in order.

Each time you come across the start-time of an EmptyEvent, if counter > 0, then flag that event for deletion. If counter == 0, put that event (or rather its id) in S.
Each time you come across the end-time of an EmptyEvent, if counter > 0, then flag that event for deletion. Delete the corresponding event from S (if it is still in there).
Each time you come across the start-time of a NormalEvent, increase the counter by 1.
Each time you come across the end-time of a NormalEvent, decrease the counter by 1, flag all EmptyEvents in S for deletion and clear S.

(then delete all the flagged events)
Then, choose the largest subset of EmptyEvents, no two intersecting. To do so, sort all EmptyEvents according to end-time. Then just go through these events and greedily select one each time it doesn't intersect with the last selected one.
Then, set all the NormalEvent booleans. Set a counter = 0 and prevStart to track the most recent start-time. Sort all NormalEvents start and end-times. Iterate through them in order.

Each time you come across start-time of NormalEvent e, set e.overlapsStart to counter > 0. Then increase counter by 1. Also set prevStart = e.startTime.
Each time you come across end-time of a NormalEvent e, decrease the counter by 1 and set e.overlapsEnd to e.startTime < prevStart.

I'll let you convince yourself of the validity of each step. But here is a good starting point if you are unable to do so :
Interval scheduling on Wikipedia


Is $\{a^nb^n\}\cup\{a^nb^{2n}\}$ LR(k)? I was reading Knuth's paper "On The Translation of Languages from Left to Right", my particular interest being on RL($k$) languages (not a typo). By the end of the paper, he puts the grammar:

$$
S \rightarrow Ac
\\
S \rightarrow B
\\
A \rightarrow aAbb
\\
A  \rightarrow abb
\\
B \rightarrow aBb
\\
B \rightarrow ab
$$

Which generates the language $\{a^nb^n\}\cup\{a^nb^{2n}c\}$. He states that this language is clearly RL($k$), which is easy to see, and he proves that it cannot be LR($k$). But, in his proof, he states:

  The problem is, of course, the appearance of "c" at the extreme right.

So, my doubt is: if it wasn't for the extra "c", could the language be LR($k$)? He remarks that, of course, the problem is the "c", but I don't see how I could write an LR($k$) grammar for $\{a^nb^n\}\cup\{a^nb^{2n}\}$.

Propbably you should read the citation as: "The problem is that the c (which separates the two parts of the language) is at the extreme right and not at the extreme left, where we start parsing."

Therefore it is of no help (unlike the case where you start reading at the right), and therefore there is no LR-grammar for this language. Neither with the c nor without.


If a grammar G is left and right regular, why $||L(G)|| \leq ||P||$? I was studying automata theory and formal languages and came across this question:
If a grammar $G$ is left and right regular, why $||L(G)|| \leq ||P||$ ?
I've searched the theory but I am missing something. And I cant find the answer anywhere, so I am asking here.
Definitions:
$P$ = set of rules
Right-regular rule: grammar $G =(N,T,P,S)$, a rule is in $P$ if the rule is in the form: $A \rightarrow Ba$ $(A, B \in N) \wedge (a \in T)$
Left-regular rule: grammar $G =(N,T,P,S)$, a rule is in $P$ if the rule is in the form: $A \rightarrow aB$ $(A, B \in N) \wedge (a \in T)$.
Left-regular grammar: a grammar where all the rules are left-regular rules.
Right-regular grammar: a grammar where all the rules are right-regular rules.
Example of a rule set $P$ with both left-regular and right-regular rules:
$P = \{ A \rightarrow a, B \rightarrow b \}$
And being both left-regular and right-regular makes the grammar regular and type 3

Your grammar only contains rules of the form $A \to a$, for $A \in N$ and $a \in T$. Therefore $L(G) = \{ \sigma \in T : S \to \sigma \in P \}$. You take it from here.


How to write an EBNF grammar for Java float literals? I've got this question on my study guide: "Write an EBNF grammar description for Java float literals and one for Java double literals."

I've browsed the Oracle site and found the grammar for java float literals, but I'm not entirely sure how to convert that to EBNF grammar. I understand EBNF notation but for some reason I'm stuck on this.

I was hoping/wondering someone would be able to get me started? It would be highly appreciated.

You could try answer the question "How do I define double and float literals?"

doubles are usually defined as:

double a = 12d;
//or
double b = 12.1;
//or
double c = 12.1d;
//or
double d = 12;

while floats could be defined as:

float m = 10;
//or
float n = 10.4f;
//but this is invalid:
float p = 10.4;

Note that by default a literal like 10.123 is considered to be double, so if you really want to assign it to a float variable, you need to append a f
character in the end. However, f is optional when the literal is 10.

Let's also list the properties of both types:

float: 32 bits (4 bytes) where 23 bits are used for the mantissa (up to 9 decimal digits). 8 bits are used for the exponent, so a float can move the decimal point to the right or to the left using those 8 bits. There is 1 bit used as the sign bit. The max long value that double can hold is $10_18$

double: 64 bits (8 bytes) where 52 bits are used for the mantissa (up to 19 decimal digits). 11 bits are used for the exponent and 1 bit is the sign bit.

So, double and float could be defined like:

digit = "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9";

double = 19 * digit, [ [, | .]  18 * digit]["d" | "D"];
float = 19 * digit, [ [, | .]  18 * digit, "f" | "F"];


Trying to understand a token file for lexical analysis I am reading this article about compiler. I am facing some problem in understanding the content of the token file. Specifically, what is the meaning of the following lines:

    [ \t\n]                 ;
    [a-zA-Z_][a-zA-Z0-9_]*  SAVE_TOKEN; return TIDENTIFIER;
    [0-9]+\.[0-9]*          SAVE_TOKEN; return TDOUBLE;
    [0-9]+                  SAVE_TOKEN; return TINTEGER;

What is * and + at the end of the expressions ?

Thanks in advance for explaining me.

* means that any number (including zero) of preceding expression can occur

+ means that at least one instance of preceding expression must occur


Reason for thread pooling Can someone explain what is the reason for thread-pooling in Linux, even if the threads are light to create and destroy??

Not as light as you think.

Thread pooling is orders of magnitudes lighter, so you can use pooled threads for gazillions of tiny tasks and still be efficient, while the same with freshly created threads would be inefficient.

In my environment, I can use five different threads in ten lines of code (without you even seeing that I'm using threads), which is possible because of highly efficient thread pooling).


what is edge-disjoint cycles in graph? I was reading something about Eulerian Tour and there is one property claiming that:

  An undirected graph can be decomposed into edge-disjoint cycles if and only if all of its vertices have even degree.

Can someone explain what is edge-disjoint cycles?

Wikipedia: Eulerian path

A set of cycles $C$ of a graph $G=(V,E)$ is edge-disjoint if the cycles $c_i$, $c_j \in C$ have no edges in common.


Convolutional Neural Network Feature Engineering? I'm working through the tensorflow tutorial, and I see how you go from 28 x 28 to zero-padding and applying a 5x5x32 convolution to get 28x28x32 and max-pooling etc.  What I'm confused about is the 32 outputs seem to be described as filters acting upon the 5x5 layers.  The description is typically something like these are equivalent to filters being used to feature engineer, but when you set up the network you don't define any filters.  So how do the filters come about?

I read this question as well Intuition for convolution in image processing and although it's informative, it doesn't describe how the filters come about.

This is the tutorial, you can see the description of the layers in the first and second convolutional layers:
https://www.tensorflow.org/versions/r0.7/tutorials/mnist/pros/index.html

Your questions phrasing is a bit confusing. I'll try to answer my interpretation of your confusion.

I think the base of your confusion relays on the assumption that 2D convolution receives a 2 dimensional array as input.
This is not true - The input of a 2D convolution layer is a 3 dimensional array.
At the beginning you have an image which can be greyscale/RGB, let's consider an RGB image of 28x28, this image is represented as a tensor of 3x28x28 (greyscale will be 1x28x28), generally - colors x width x height as the colors can exceed 3 for opacity etc.
A 2D convolutional layer with patch size 5x5 will be a applied over each patch of size 5x5 of the images over all colors.
To sum it up, slice the image to cubes of patch size (which overlap according to the stride parameter) each of these patch is taken with all it's colors as the input to the filter.

The process I've described above is the application of a single filter over the input. The result of "running" the filter over the input is a matrix (as the dot product of each patch of the image with the filter is a scalar).
Now, take 32 such filters stacked on top of the other, the output will be 32 matrices where each matrix is the application of a different filter over the input.

As far as dimensions go, let's assume you apply 5x5x32 over a 1x28x28 image (without padding & stride=1) you'll have: $\frac{input\ size-patch\ size}{stride}+1$, where I assumed everything is symmetrical for both axises.
So you have output of $\frac{28-5}{1}+1=24$, which means the second layer is of size 32x24x24.

You can either think of the second layer as an "image" of size 24x24 with 32 "colors" which is weird but some people do it, or you can think about everything in terms of 3 dimensional arrays and understand exactly how a filter is applied over each 3 dimensional array.

Why is this referred to as filters?

Let's consider the case where you apply a 2D convolutional layer with parameters 5x5x1. What does this layer actually do? How does it look?
(consider the case where your images are greyscale for simplicity), The layer is actually a dot product of each patch of size 5x5 with a 2D weight matrix of size 5x5. Organized to form a 2 dimensional array of results (which is the output layer).
The 5x5 weights matrix is called "filter". You can think of it as a gaussian for a moment, the 5x5 weight matrix is applied over each patch of the image thus blurring the image. This is applying a gaussian filter over the image.
Now instead of a gaussian filter, you learn the weights and have a general filter.
Now consider a layer of 5x5x32, it is the same, but with 32 different filters.


position to insert element in inserionsort (equality of probablity) prove that in algorithm insertionsort, for successively considered element a[i] there is equal probablity that element will be inserted in one of i positions:

a[1] <= a[2] <= ... <= a[i-1]

To my eye it is obvious and I can't prove it. What is your opinion ?

Try counting the number of permutations where it is inserted in position $i$.  How does this number depend on $i$?  That will lead immediately to a proof.

In general, when you need to calculate a probability of some event, and you have a uniform distribution, one way is to use counting to compute the probability: count the number of outcomes where the event is true, and then divide by the total number of possible outcomes.


Counting inversion pairs - $n^2$ results in $n \log n$ time? The number of possible inversions in an array is bounded by $\binom{n}{2}$, i.e $\frac{n(n-1)}{2} \in O(n^2)$. How it is possible to calculate $O(n^2)$ results in $O(n\log n)$ time using something like modified merge sort? (sample algo : http://www.geeksforgeeks.org/counting-inversions/).

Here is an even more amazing example. The determinant of an $n\times n$ matrix is a sum of $n!$ products, yet we can compute it in time $O(n^{2.373})$.
Here is another striking example. Given a binary string of length $n$, we can count the number of binary strings of the same length in time $O(n)$ even though there are $2^n$ of them.
What limits the running time is not the magnitude of the output but its length.

In this particular case, the output length is $O(\log n)$, so it provides no meaningful limit at all. Even though there could be up to $\binom{n}{2}$ many inversions, we can count them without listing them all, just as in the example of binary strings. As you mention, there is an $O(n\log n)$ algorithm doing that. It is conceivable that there is an even faster algorithm, though nothing faster than $O(n)$, since you need (in general) to read at least $n-1$ entries of the permutation before you can be sure what the number of inversions is.


CFG and PDA for the set of strings in $\{a, b, c\}^∗$ such that the number of b’s is equal to the sum of number of a’s and c’s I'm trying to find the CFG and PDA for the above language. I have so far come up with this
$S \to S_1S_2 \\ S_1 \to aS_1b \\ S_2 \to bS_2c$
However, I realized that this is just a subset of the required language. How do I consider the remaining ones? Also, how do I construct a PDA for it? Any help is appreciated.

For the PDA, I think you use the stack to track the number of A plus the number of C minus the number of B seen so far, using both positive and negative tokens:

If the stack is empty and you see an A or a C, you push a "+1" token.
If the stack is empty and you see a B, you push a "-1" token.
If the stack is not empty and you see the kind of token that's already on there (e.g. you have a +1 token and you see an A or a C), then you push another of the same token.
If the stack is not empty and you see the wrong kind of token (e.g. there's a "-1" token on the stack and you see an A or a C), you pop one token.

Depending on your formalisation of PDA you may want to start off by pushing a "zero" token in order to check whether the stack is "logically empty" or not.
The stack keeps the invariant that there can never be both a "+1" and a "-1" token on it at the same time.
The word is in the language if and only if the stack is (logically) empty at the end of the string.


Why in Flow network, there is no reversed edges? I have read that Flow network is a directed graph, with no self loops and there is no reverse edges and non negative capacity.
However in Residual network, we allow the reverse edges so we can cancel(subtract) some units from the flow.

My question is why there is no reversed edges in flow networks?

I understand that it is directed since we need to go from source to sink, non negative capacity since there is no a negative flow but i don't understand why no reversed edges.

Here is your definition of reversed edges in the case of flow network given in your comment.

  Between 2 vertices there is the normal forward edge (u,v) , and another edge (v,u) that goes backward(this is the reversed edge). regardless their capacities.

If your definition is used, flow networks may have reversed edges indeed. For example, the flow network (a) in the picture below does have reversed edges between node $v_1$ and $v_2$. The two edges are usually called anti-parallel edges.

However, anti-parallel edges can be eliminated by introducing a new node and two edges having the same capacity as one of the anti-parallel edges. For example, the flow network (a) is equivalent to the flow network (b) in the above picture. Be careful that we can't simply remove the edge from $v_2$ to $v_1$ and subtract 4 from 10 to get 6 as the new capacity for the edge from $v_1$ to $v_2$ because the resulting flow network would not allow us to use only the edge from $v_2$ to $v_1$.

Flow networks without anti-parallel edges are easier to explain and process. It is not surprising if anti-parallel edges are avoided or excluded or disallowed for the sake of simplicity in many situations.

Exercise. Consider a flow network $(V,E,s,t,c)$, and let $e, e'\in E$ be anti-parallel edges. Prove that there exists a maximum flow in which at least one of $e, e'$ has no flow through it.


How to show that $\log (n!) = \Omega(n\log n)$ using Stirling's approximation? Using Stirling's approximation, we have $\log_{2} (n!) = n\log_{2} n - (log_{2} e)n + O(log_{2}n)$. Most lecture notes I have come across say that $ n\log_{2} n - (log_{2} e)n + O(log_{2}n) = \Omega (n\log_{2} n)$. Can someone give a rigorous proof of the last line using the basic definitions of big-O and big-Omega?

Thank you in advance.

P.S. There are similar posts on this and I know some other proofs of  $\log (n!) = \Omega(n\log n)$ with or without using Stirling's approximation. I don't have any problem with $\log (n!) = \Omega(n\log n)$. It's just that I can't see why $ n\log_{2} n - (log_{2} e)n + O(log_{2}n) $ is $ \Omega (n\log_{2} n)$.

A function $f(n)$ is said be $\Omega(g(n))$ if there exist $c,n_0\gt 0$ such that $f(n)\ge cg(n)\ge 0$ for all $n\ge n_0$.

A function $f(n)$ is said be $\mathcal O(g(n))$ if there exist $c,n_0\gt 0$ such that $0\le f(n)\le cg(n)$ for all $n\ge n_0$.

Here,
$$\log_2(n!)=n\log_2 n-(\log_2 e)n+\mathcal O(\log_2 n)$$

Let $f(n)=\mathcal O(\log_2 n)$ such that
$$\log_2(n!)=n\log_2 n-(\log_2 e)n+f(n)$$

By definition, $f(n)\ge 0$.

Thus,
$$\begin{align}\log_2(n!)&\ge n\log_2 n-(\log_2 e)n\end{align}$$

We want to find some constants $c,n_0\gt0$ such that
$$n\log_2n-(\log_2e)n\ge cn\log_2 n$$
for all $n\ge n_0$, that is, it must satisfy,
$$(1-c)n\log_2n\ge (\log_2e)n$$
As $n\gt 0$, it must satisfy
$$(1-c)\log_2n\ge (\log_2e)$$
Note that
$$(1-c)\log_2n\ge(1-c)\log_2n_0$$
for all $n\ge n_0$.
So, we need a positive $c$ and a $n_0$ to satisfy
$$(1-c)\log_2n_0\ge (\log_2e)$$
This is easily possible, as the RHS is a constant and the LHS can be made large by choosing $n_0$ and $c$ appropriately. For instance, choosing $c=0.1$ and $n_0=4$ works.

Thus, by definition,
$$\log(n!)=\Omega(n\log n)$$


largest bitwise-or subset with a maximum number of on bits? Suppose I have the following set of bit sets:

 [1,]    0    1    1    1    0    1    0    1    0     0
 [2,]    1    0    1    1    0    0    0    1    0     1
 [3,]    0    0    1    0    1    1    0    1    1     0
 [4,]    1    0    1    0    0    0    0    1    1     1
 [5,]    0    1    0    1    0    1    0    1    1     0
 [6,]    0    1    1    1    1    0    0    1    0     0
 [7,]    1    1    0    0    0    1    1    0    0     1
 [8,]    1    1    0    1    1    1    0    0    0     0
 [9,]    0    1    1    0    1    1    0    0    0     1
[10,]    0    1    1    1    0    0    1    1    0     0

How would I go about finding the largest set such that the bitwise-or of that set does not exceed n bits in the "on" position.

For example, if I or rows 1 & 10...

 [1,]         0    1    1    1    0    1    0    1    0     0
[10,]         0    1    1    1    0    0    1    1    0     0
[1 or 10,]    0    1    1    1    0    1    1    1    0     0

This gives me 7 bits in the "on" position.

Now suppose my limit was 8 bits... how would I go about finding the largest set?

Edit:  I know how to do this as a mixed-integer-linear program, but I'm assuming there's a nifty graph approach.

This problem is NP-hard. It is called "the minimum-k-union problem". Given a universe $U$ and a family of sets $\mathcal{F}$ over this universe. Are there $k$ distinct sets in $F$ such that the union of all these sets has size at most $d$.

Your presentation is the matrix formulation of this problem where each column corresponds to an element in the universe and each row corresponds to a set in the family. We are looking for $k$ rows such that the number of columns having at least one "1" is at most $d$.

The Problem is NP-hard and has approximation algorithms. Here is a link for one of them.


Is Supervised Learning Better than Unsupervised Learning (For Recommendation Systems) I am working on a Recommendation System as a personal project (I finish it on time, I'll present it as my final year project). I devised mathematical methods that estimated User's ratings of products based on their previous ratings, without using ML. I developed a host of such algorithms for recommendation (I developed a paradigm that allowed me to generate an infinite number of distinct recommendation systems). I intended to assign weights to a select few of them (maybe the ones with the highest accuracy), and take the weighted average of the estimated user ratings.

I realised that Machine Learning could be used to best determine the appropriate weight to assign each of the algorithms on a per user basis, and decided to start learning ML yesterday. It seems what I'm intending to do, is supervised learning.

From what I can tell, it seems existing recommendation systems on the market use unsupervised learning. I am curious to how the two paradigms compare in my case. Would supervised learning work better than unsupervised learning, or is unsupervised learning a better paradigm for recommendation systems?

It doesn't make sense to ask if supervised learning is better or worse than unsupervised since they are used in different contexts.

In the most simple terms, supervised learning is used when you have a dependent variable, so you're investigating the relationship between this dependent variable and one or more independent variables.  Often you're trying to predict something about the dependent variable using the independent variable(s).

In unsupervised learning, you are essentially looking for certain kinds of structure in the data or trying to find various kinds of relationships between variables, but none are considered special in the sense of being a dependent variable.


Is SAT a single language or a union of languages? I know that a language is in NP if a Turing machine can decide the language of its checking relation $\{\text{boolean formula }\#\text{ truth assignment | truth assignment is correct}\}$ in polynomial time.

Here is my confusion. All Turing machine have a finite input alphabet $\Sigma$. Thus, none of them can solve any SAT problem with, say, $|\Sigma|+1$ variables. Thus, do we need another Turing machine with a larger input alphabet and its associated language to cover this problem? By induction, does this make SAT a union of an infinite number of languages?

If SAT is indeed a union of languages, and any Turing machine only responsible for solving boolean satisfiability problems with variables within its input alphabet, a Turing machine can simply "memorize" all possible 3-SAT problems without redundant clauses over this finite set of variables, and regurgitate the answer in linear time?

In other words, is there a loophole in the definintion of NP that allows for solving SAT by looking up pre-prepared answers? If such cheating is allowed, P=NP?

The way each variable is represented is a matter of encoding of the problem and the machine does not have to assign an independent symbol for each variable. Your question is similar to, we can not represent all graphs in a turning machine since for a fixed alphabet $\Sigma$ we can set the number of vertices to $\Sigma + 1$. Well, we can represent each variable of sat, or each vertex in the graph using a binary number. Hence, a machine whose input and working alphabet is zero and one can represent any graph or Boolean formula. Note that any turing machine can be translated to a turning machine over the binary language on the expense of a constant factor of the time and the place complexity using the following trick.

Let $1, 2, 3, \dots n$ be an enumeration of the elements of the alphabet. Let $m = \left\lfloor \log n \right\rfloor + 1$. Change each symbol with a word of length $m$ in the machine, where the $i$th symbol turns into $\mathrm{bin}(i)$ prefixed with zeroes to reach length $m$. The machine reads the letters in blocks (you can save what word you are reading now in the state of the machine).

Note. The way a machine encodes the input can have a big effect on its time and place complexity note the adjacency lists and adjacency matrices representations of graphs.


Algorithm to find k elements following the median in sorted order I have the following problem:

Given an unsorted array A of size n, print the first k elements in A larger than its median.

Here's my approach to the problem:

     1. Create a minHeap and a maxHeap
     2. Iterate over elements in A // O(n)
        - if maxHeap.count < minHeap.count
             insert current element to maxHeap // O(log(n))
          else:
             insert current element to minHeap // O(log(n))
     3. if maxHeap.count < minHeap.count:
              median = minHeap.extractMin()
     4.  output k elements from minHeap  // O(klog(n))

This maintains a maxHeap of elements less than the median and a minHeap of elements greater than or equal to the median. But from my analysis, this seems to take O(nlogn + k(log(n)) which is no better than sorting A first and grabbing A[n/2:n/2+k] in just O(nlog(n) + k).

Now I have 2 questions:

Is my analysis tight? I am doubtful since the heaps have at most i elements in the ith iteration, not n.
Is there a better algorithm? Maybe something like O(n+klog(k))?

Answering your second question:

Find the median $m$, and partition the set into $L_1 = \{x | x \in S \wedge x < m\}$ and $L_2 = \{x | x \in S \wedge x > m\}$.
Find the $k$th largest element $x_k$ in $L_2$, and partition the set into $L_2' = \{x | x \in L_2  \wedge x \leq x_k\}$ and $L_3 = \{x | x \in L_2 \wedge x > x_k\}$.
Sort $L_2'$ and return.

Steps 1 and 2 take $O(n)$. Step 3 takes $O(k \log k)$. Total time $O(n + k \log k)$.

Note this assumes distinct values. Repeated values involves some edge case handling.


simple uniform hashing: unclear definition of probability I am trying to understand the assumption of Simple Uniform Hashing (SUHA) as e.g., in CLRS textbook; or other courses about hashing.

The usual description given to SUHA is (cf. CLRS):

  "we shall assume that any given element [i.e., key] is equally likely to hash into
  any of the m slots, independently of where any other element has
  hashed to. We call this the assumption of simple uniform hashing."

However this is quite informal, and thus I don't fully understand it.
My understanding is that the assumption supposedly means that

$ Pr[h(k)=\ell]=1/m\,$, for any given key $k$ and slot in the table $\ell=0,\ldots,m-1$, where $m$ is the number of slots in the table.
But since given a key $k$ the deterministic hash function $h$ is fixed on $k$, there is no probability distribution here!

Perhaps it is meant here that $k$ is a random variable distributed uniformly over all keys?

  Question: what is the distribution the probability $ Pr[h(k)=\ell]=1/m\,$ is defined over in SUHA?

EDIT:

My understanding is the SUHA is an (idealized) assumption that formally means that the probability $Pr[h(k)]$ is the probability of the event of inserting a key to the table nevertheless the time of insertion (it might be the first key I insert or the last one).

In other words, the sample space of probability $\Omega$ is

$\Omega:=($the set of all [ordered] sequences of insertions to the hash table$)$.

The probability event $h(k)=\ell$ is thus the set of all [ordered] sequences of insertions to the hash table in which the $n+1$th insertion hashes to $\ell$, where $n+1$ is the ``current'' insertion that I'm analyzing and where $n$ is the current number of keys in my hash table.

In SUHA we shall also assume that $h(k)=\ell$ for every $n$ (the current position of insertion in the sequence); namely, we assume that the event $h(k)=\ell$ is completely independent of the sequence.

  To sum up the answer: the probability $Pr[h(k)=\ell]$ is taken over
  all possible ordered sequences of insertions to the hash table.

First, the outcome of a situation being deterministic doesn't mean we will necessarily assign a probability of $1$ or $0$ to it. If I say I'm going to flip a coin, but it is actually a double-sided coin meaning both sides are heads or both sides are tails, the probability that it comes up heads is still $0.5$. Indeed, with respect to classical mechanics, the outcome of a normal coin flip is a deterministic function of the state of the universe, and even quantum mechanics would at best predict near certainty of the classical outcome. But you are correct, that if we knew $h$ and $k$ and $\ell$, then $h(k)=\ell$ would be either a logical tautology or a logical contradiction, and thus of probability $1$ or $0$ respectively.

We could consider any of $h$, $k$, or $\ell$ to be random variables, but the most natural choice would be $k$. I'll write $K$ for the random variable of the keys and reserve $k$ for some particular key. We have $$P(h(K)=\ell)=P(K\in h^{-1}(\ell)) = \mu_K(h^{-1}(\ell))$$ where $\mu_K$ is the probability measure corresponding to $K$. The simple uniform hashing assumption (SUHA) states that $$\mu_K(h^{-1}(\ell))=\frac{1}{m}$$ for every $\ell\in\{0,\dots,m-1\}$. This is simply a constraint on the probability measure $\mu_K$. There is no assumption that $K$ is "uniformly distributed" in any (other) sense. $K$ could be wildly "non-uniform" and still satisfy SUHA. Indeed, it would have to be for some hash functions, $h$.

For example, let's say $m=2$ and $h^{-1}(0)=\{k_0\}$ and thus $h^{-1}(1)=X\setminus \{k_0\}$ where $X$ is the domain of $h$. Let's further say $|X|=101$. Then for this $h$ to satisfy SUHA, it must be the case that $P(K=k_0)=\frac{1}{2}$. For $k\in X\setminus \{k_0\}$, it could be the case that there's a $k_1\in X\setminus \{k_0\}$ such that $P(K=k_1)=\frac{1}{2}$ and thus if $k\neq k_1$ then $P(K=k)=0$. Or maybe, $P(K=k)=\frac{1}{200}$ for any $k\in X\setminus \{k_0\}$. In fact, any distribution over the elements of $X\setminus \{k_0\}$ that sums to $\frac{1}{2}$ will suffice.

Typically, we would specify a distribution for $K$ and then SUHA would constrain what $h$ could be. The point is that the hash function is "well matched" to the distribution of keys whatever that is. There is no sense in stating a hash function satisfies SUHA without specifying the distribution of keys, but we can say a pair of a hash function and a distribution of keys satisfy SUHA while giving the details of neither. This is all that is needed to prove many results about hashing. We don't want to limit ourselves to only talking about "uniformly" distributed keys. A hash table will still gave the same performance guarantees for "non-uniformly" distributed keys as long as the hash function is chosen to "compensate" for the "non-uniform" distribution, i.e. to satisfy SUHA.