Occurrences notation in "Compiling Pattern Matching to Good Decision Trees" From Compiling Pattern Matching to Good Decision Trees (Luc Maranget, Proceedings of ML '08, pp. 35–46. ACM, 2008.)

  We also consider the usual occurrences. Occurrences are sequences of integers that describe the positions of subterms. More precisely an occurrence is either empty, written $\Lambda$, or is an integer $k$ followed by an occurrence $o$, written $k\cdot o$. Occurrences are paths to subterms, in the following sense:
  $$\begin{align*}
v/\Lambda &= v\\
c(c_1, \dots, v_a)/k\cdot o &= v_k/o \quad(1\leq k\leq a)
\end{align*}$$

Could anyone explain the occurrences notation a bit?

I will try to illustrate the concept more intuitively and informally by representing
terms as trees.

A term can be represented as a rooted tree, where the leafs are atomic
operands (literals, or variables) and the other nodes are
operators. Typically abstract syntax trees can be built on that model
as this example (taken in another answer), for which I am giving both the textual syntax and the
tree representation.

if (x > y) {
   if (y < a) {
     x:= a
     y:= b
   } else {
    x:= b;
   }
 }
              if
     ________/|\________
    /         |         \
   >          if        :=
  / \    ____/|\____   /  \
 x   y  /     |     \ x    b
       <     :=     :=
      / \   /  \   /  \
     y   a x    a y    b

But the concept is used in a lot of different contexts, with different
kinds of operators. The example term above could also be written as in the
text of your question in function call style:

if(>(x,y),if(<(y,a),:=(x,a),:=(y,b)),:=(x,b))

where the operators are if, >, <, and :=.

Whatever the kind of term you are interested in, an occurrence is a
position in the tree (to which we can associate corresponding
positions in any of the strings representation).

A subterm corresponds to a subtree, and an occurrence is the location
of the main operator of a subterm, i.e. its root.

A simple way to designate unambiguously an occurrence is to give the
path to access that occurrence from the root of the tree. The path is
simply a string of integers that tell you at each node which of the
daughter you should consider.

So the empty word $\Lambda$ correspond to the root itself (the top
if in my example), since there is no path to be followed.

The string $2\;1\;2$ tell you to go to the second daughter, then to
the first, then the second again. So it is an occurrence corresponding
to the position of the leftmost a.

That in particular is useful to distinguish the two occurrences of
a, the other one being  $2\;2\;2$.

An the occurrence of the term :=(y,b) is $2\;3$.

Of course, an occurrence is meaningful only with respect to a term,
and that is why your document systematically associate the reference
term with the path, i.e. string, denoting an occurrence in that term.

Actually, the notation used in your document is a bit abusive, though
it is common, because an occurrence is really a position in the term,
where some subterm occurs, but it is not that subterm (though it is
sometimes taken as such if the context makes it unambiguous).

To get the subterm, you should normally explicitly apply a function
that  takes an occurrence as argument and returns whatever subterm is
found there.


Increment and Decrement on binary semaphores when their values are $1$ and $0$ respectively? What happens if we increment binary semaphore $x$ when it is equal to $1$.
E.g A process executes $V(x)$ when $x==1$;
What are the possible cases then-

Process would be blocked till $x$ becomes $0$. The moment $x$ becomes $0$,it is incremented.
Process would be blocked and no present or future changes will be there for $x$. i.e Process assumes as if there was never a $V(x)$.
Other. (If there is please mention).

Same query for $P(x)$ operation as well when $x=0$.

Actually, Galvin doesn't mention in pseudo code what to do during such condition.
Better if Someone could provide standard code for $P(x)$ and $V(x)$... Also, $P$ is wait operation whereas $V$ is signal operation.

A binary semaphore has the wait() and the signal() method. The one which causes a process to stop is the wait() method, while the one that increments the counter x in the semaphore is signal(). If signal is called when x=1, then the call is just ignored because the queue of blocked processes is empty, and x has already its maximum value. The process that called signal() doesn't block.


Is there an algorithm which finds sorted subsequences of size three in $O(n)$ time? I want to prove or disprove the existence of an algorithm which, given an array $A$ of integers, finds three indices $i, j$ and $k$ such that $i < j < k$ and $A[i] < A[j] < A[k]$ (or finds that there is no such triple) in linear time.

This is not a homework question; I saw it on a programming forum framed as “try to implement such an algorithm.” I suspect that it is impossible after various experiments. My intuition tells me so, but that does not really count for anything.

I would like to prove it formally. How do you do it? I would ideally like to see a proof laid out step-by-step, and then if you are so inclined, some explanation of how to go about proving/disproving simple questions like this in general. If it helps, some examples:

[1,5,2,0,3] → (1,2,3)
[5,6,1,2,3] → (1,2,3)
[1,5,2,3] → (1,2,3)
[5,6,1,2,7] → (1,2,7)
[5,6,1,2,7,8] → (1,2,7)
[1,2,999,3] → (1,2,999)
[999,1,2,3] → (1,2,3)
[11,12,8,9,5,6,3,4,1,2,3] → (1,2,3)
[1,5,2,0,-5,-2,-1] → (-5,-2,-1)

I supposed that one could iterate over $A$, and each time there is an $i < j$ (our current $j$, that is), we make a new triple and push it onto an array. We continue stepping and comparing each triple until one of our triples is complete. So it's like [1,5,2,0,-5,-2,-1] → 1..2.. -5.. -2.. -1, [1,5,2,0,-5,-2,3,-1] → 1..2.. -5.. -2.. 3! But I think this is more complex than mere $\mathcal{O}(n)$ as the number of triples on our triple array would in the worst case correspond to the size of the input list.

This is variation of Longest increasing subsequence problem; this is the solution presented on Wikipedia using two auxiliary arrays $M$ and $P$:

  $M[j]$ — stores the position $k$ of the smallest value $A[k]$ such that there is an increasing subsequence of length $j$ ending at $A[k]$ on the
  range $k \leq i$ (note we have $j \leq k \leq i$ here, because $j$ represents the
  length of the increasing subsequence, and $k$ represents the position of
  its termination. Obviously, we can never have an increasing
  subsequence of length $13$ ending at position $11$. $k \leq i$ by definition).
  $P[k]$ — stores the position of the predecessor of $A[k]$ in the longest increasing subsequence ending at $A[k]$.

  In addition the algorithm stores a variable $L$ representing the length
  of the longest increasing subsequence found so far.

This algorithm runs in worst-case time $\Theta(n\log n)$. Your problem is a special case that allows you to return when $L=3$ which pushes runtime down to $O(n)$ because the binary search runs only on arrays of length at most two, which is therefore in time $O(1)$ as opposed to $\Theta(\log n)$ in the general case.

Consider the modified pseudo code:

 L = 0
 for i = 1, 2, ... n:
    binary search for the largest positive j ≤ L
      such that X[M[j]] < X[i] (or set j = 0 if no such value exists)
    P[i] = M[j]
    if j == L or X[i] < X[M[j+1]]:
       M[j+1] = i
       L = max(L, j+1)
   if L==3 : return true; // you can break here, and return true.
return false; // because L is smaller than 3.


Advantage of the Monte Carlo method over a regular periodic sampling I am unclear on when to use the Monte Carlo random sampling method for algorithm design. The classic example that I keep seeing is using random points within some bounding rectangle to determine the area of some irregular figure. Wouldn't a regular periodic sampling provide more repeatable results for this application then using the Monte Carlo (random sampling) method?

If you use a fixed seed then Monte Carlo is also repeatable. Monte Carlo sampling has the advantage that the expected number of points inside your figure is proportional to the area, which is not necessarily the case for a grid — you can come up with a contrived figure in which the grid is off by a lot, whereas random points are impossible to "fool" this way.


Reducing Vertex Cover to Half Vertex Cover I need to reduce Vertex Cover to Half Vertex Cover using a Karp reduction:

Vertex Cover: Given a graph $G = (V,E)$ and an integer $k$, is there a subset of $V$ of size $k$ which intersects all edges?

Half Vertex Cover: Given a graph $G = (V,E)$ and an integer $k$, is there a subset of $V$ of size $k$ which intersects exactly half the edges?

I will be happy if you can tell me how to do that and why the reduction works (both directions of the proof).

Let special vertex cover be the special case of vertex cover in which $|V| = 2k+1$. We later reduce vertex cover to special vertex cover.

Now suppose we're given an instance $G = (V,E),k$ of special vertex cover. Construct an instance $G',k$ of half vertex cover by attaching $|E|$ new edges to each vertex in $V$.

The total number of edges in the new graph is $|E|(|V| + 1)$. A vertex cover of size $k$ in the original graph covers this many edges in the new graph:
$$
|E|(1+k) = |E|\left(1 + \frac{|V|-1}{2}\right) = |E| \frac{|V| + 1}{2},
$$
exactly half the edges. Conversely, consider any $k$ vertices of the new graph, which cover exactly half of the edges. If they cover $m$ of the original edges then they cover at most $m + k|E|$ edges of $G'$, where $m \leq |E|$. The calculation above shows that $m = |E|$, that is, all edges of $G$ are covered.

It remains to reduce vertex cover to its special case. If $|V| = 2k+1$ then there is nothing to do.

If $|V| < 2k+1$, then we add $\delta := 2k+1 - |V|$ many paths of length 2 edges. The new graph $G'=(V',E')$ has a vertex cover of size $k' = k + \delta$ iff the original graph had a vertex cover of size $k$. Note that
$$
|V'|-2k' = (|V| + 3\delta) - 2(k+\delta) = |V| - 2k + \delta = 1.
$$

Similarly, if $|V| > 2k+1$ then we add $\delta := |V| - (2k+1)$ many triangles. The new graph $G'=(V',E')$ has a vertex cover of size $k' = k + 2\delta$ iff the original graph had a vertex cover of size $k$. Note that
$$
|V'|-2k' = (|V| + 3\delta) - 2(k+2\delta) = |V| - 2k - \delta = 1.
$$


k-polynomial time approximation algorithm for set cover (k = max size of subsets) Problem Definition: Given a universe set $U = \{1, 2, \dots, n\}$ and a collection of $m$ subsets $S_1, S_2, \dots S_m \subseteq U$, find the minimum collection of subsets that cover $U$.
I am specifically trying to find a $k$ polynomial time approximation algorithm for set cover where $k$ is the largest size of the subsets. In other words, $k = \max_{i=1}^m|S_i|$
I have the following ILP and relaxed LP programs as shown at the end of page 1 and start of page 2 from these lecture notes of Luca Trevisan.
I know that the factor of the polynomial time approximation algorithm depends on the rounding factor necessary in the LP. In the case for weighted set cover, the rounding factor would depend on $m$, the number of subsets.
I have determined a lower bound on the number of subsets based on the defined $k$ to be as follows: $\lceil \frac{n}{k} \rceil \leq m$.
I don't know how to use this (or if this is the correct relationship) to show something along the lines of $A(I) \leq \alpha OPT(I)$ where $A(I)$ is the approximation algorithm solution, $OPT(I)$ is the optimal solution, and $\alpha$ is related to $k$.
How would you go about solving this problem?

Let $A = \{ i : x_i \geq 1/k \}$. By construction, $|A| \leq k \sum_i x_i \leq k \mathrm{OPT}$. The set $A$ is a set cover, since if $S_j = \{i_1,\ldots,i_\ell\}$ (where $\ell \leq k$) then $x_{i_1} + \cdots + x_{i_\ell} \geq 1$, and so $\max(x_{i_1},\ldots,x_{i_\ell}) \geq 1/\ell \geq 1/k$.


How to find the equivalence classes of a regular language Given a language $L=\{ 0^m1^n | m \neq n \}$ over $\Sigma = \{ 0,1 \}$, how would one go about characterizing the equivalence classes of this language?
I know there isn't a formal algorithm for that, but still, can some steps always be taken?

You have to be creative. In this case, the equivalence classes are:

$X_a = \{0^a\}$ for $a \geq 0$.
$Y_a = \{0^{n+a} 1^n : n > 0\}$ for $a \geq 0$.
$Z = \{0^n 1^m : m > n \}$.
$W = \{w : w \text{ contains } 10\}$.

We can construct an infinite DFA to show that each of these classes consists of equivalent words:

The initial state is $X_0$.
The accepting states are $X_a,Y_a$ for $a \neq 0$ and $Z$.
$\delta(X_a,0) = X_{a+1}$, $\delta(X_0,1) = Z$, $\delta(X_{a+1},1) = Y_a$.
$\delta(Y_a,0) = W$, $\delta(Y_0,1) = Z$, $\delta(Y_{a+1},1) = Y_a$.
$\delta(Z,0) = W$, $\delta(Z,1) = Z$.
$\delta(W,0) = \delta(W,1) = W$.

This also shows that the classes cover all of $\Sigma^*$. Finally, in order to show that these are the equivalence classes, we need to show that any two classes have a separating word:

$X_a,X_b$: $1^a$.
$X_a,Y_a$: $0$.
$X_a,Y_b$: $0$.
$X_a,Z$: $1^a$.
$X_a,W$: $0$.
$Y_a,Y_b$: $1^a$.
$Y_a,Z$: $1^a$.
$Y_a,W$: $1^{a+1}$.
$Z,W$: $\epsilon$.


What is the significance of the vector dimension in semidefinite programming relaxations? Let's say that we want to design a semi-definite programming approximation for an optimization problem such as MAX-CUT or MAX-SAT or what have you.

So, we first write down an integer quadratic program that solves the problem exactly. For example, in the case of MAX-CUT we would write:
$$
\max \sum_{\{u,v\} \in E}{\frac{1 - x_u x_v}{2}}
$$
$$
x_v \in \{-1,+1\}.
$$

Then we relax the program by allowing the variables to take on vector values in the sphere $S^{n-1}$, and replacing products with scalar products, obtaining a semi-definite program that can be solved precisely.

Our approximation proceeds by solving the SDP and rounding the solution to obtain a legal solution for the original problem whose distance from the SDP solution can be bounded.

My question is: What is the importance of the dimension of the vectors? In all the cases I have seen, the analysis would stay the same if we assume that the vectors are all unit vectors in $\mathbb{R}^2$. So why do people always take vectors in $S^{n-1}$?

Vector programs are solved by solving semidefinite programs. The basic idea is that if $v_1,\ldots,v_n$ are vectors, then the matrix $V_{ij} = \langle v_i,v_j \rangle$ is positive semidefinite:
$$ \alpha' V \alpha = \sum_{i,j} \alpha_i \alpha_j \langle v_i, v_j \rangle = \left\|\sum_i \alpha_i v_i\right\|^2. $$
The converse is also true: a positive semidefinite $n \times n$ matrix $V$ of rank $r$ can be written as $V = LL'$, where $L$ is $n \times r$ (this is known as the Cholesky decomposition). Furthermore, $L$ can be found effectively given $V$. If $\ell_1,\ldots,\ell_n$ are the $r$-dimensional rows of $L$, then $V_{ij} = \ell_i \ell'_j = \langle \ell_i, \ell_j \rangle$. We can therefore optimize a vector program involving inner products of vectors $v_i$ by solving a semidefinite program. Rank constraints are not convex, and so we cannot really control the dimension of the vectors other than the trivial bound $n$.

As you mention, the analysis in the particular case of MAX-CUT only uses the two-dimensional projections. This shows that even if you could somehow guarantee that $\operatorname{rank} V = 2$ (recall that the rank corresponds to the dimension), the analysis wouldn't get better. On the other hand, if you could guarantee than $\operatorname{rank} V = 1$, you will have solved MAX-CUT exactly. This shows that the latter constraint is NP-hard to realize. It is probably the case that any non-trivial rank constraint cannot be enforced in polynomial time, and any constant rank constraint is NP-hard.


Is there a way of objectively measuring the efficiency or quality of software or code design? I've been thinking about ways of measuring code, and, quite frankly, I can't think of truly objective, semi-universal ways of evaluating the quality or "strength" of code to say, "Yes, this is better than that based on X, Y, and Z metrics" that are popular or exist. I've looked at SonarQube, and although I think their metrics are important, I feel like there are more fundamental concepts at work than what they have now.

But, of course, it's often said that certain languages are better than others because they have stronger guarantees or abstractions: C++ > C with abstraction, and Haskell > C++ with typing and purity and a whole slew of other features. But I was wondering whether it would be possible to actually quantify how much better one is than the other.

Are there existing papers that talk about ways of objective comparing coding paradigms or languages based on objective metrics?

A few of the resources I've found while search have to do with more business-y metrics like cost of quality or coverage of unit tests over development time. Also, measuring by number of lines seems fishy and not truly crucial (imagine if we measured math proofs' qualities by how many pages of paper it takes to print!):

http://www.infosys.com/engineering-services/white-papers/Documents/comprehensive-metrics-model.pdf
http://www.compaid.com/caiinternet/ezine/Gack-Effectiveness.pdf
http://www.compaid.com/caiinternet/ezine/Gack-Efficiency.pdf

Apparently the list of top 10 papers are also not based on measuring the efficiency of design in code, but are more focused on specific areas:

http://blog.mendeley.com/highlighting-research/the-top-10-research-papers-in-computer-science-by-mendeley-readership/

The abstract conclusion is not really that "some languages are better than others" but that "some languages are better than others for some purposes". Different languages are somewhat like species in evolutionary biology. They have evolved to fill certain niches. There are many evolutionary niches. They have strengths and weaknesses in different areas. Sometimes these types of analysis can degenerate into what is known in stackexchange as "gorilla vs shark" debates.

The question seems to mix up certain distinct areas in CS study. Code quality is measured by defects and is more programmer and implementation related than language related. Defects can be high or low in any language. efficiency in CS is generally considered interchangeable with ("execution") complexity and measured with Big-O notation. There is also another notion of code/ programming complexity where some functionally equivalent implementations may have different levels of complexity in their programs. This is studied especially in OOP theory.

However recently there is some research along the lines you mentioned. There is a large database of programs with identical functions written in the Rosetta code database and some comparative/ objective/ scientific/ quantitative analysis has been done by researchers. See eg:

A Comparative Study of Programming Languages in Rosetta Code / Nanz, Furia
Code length measured in 14 languages / McLoon, Mathematica


Lower bound on distinct element heapsort I've been self-studying algorithms and am currently working on one of the starred exercises from CLRS:

Exercise 6.4-5
Show that when all elements are distinct, the best-case running time of heapsort is $\Omega(n\text{log}(n))$.

I've been thinking over this for about a day or so, and so far I've tried working with finding the time it takes run heapsort through just the leaves of a heap (I've been focusing on full heaps with $n = 2^h - 1$ elements), but couldn't draw any conclusions except for the minimum and 2nd-minimum elements, so that hasn't really gotten anywhere.

Does anyone have any hints as to how to proceed? Please don't post solutions to the problem, just hints/potential directions to proceed.

Any help is much appreciated!

keep in mind, that a heap has a height of $O(\log n)$ and its root contains the minimal element. how long does it take to restore the heap if you remove the root element (the minimum!) and how often you have to do this in order to achieve a sorted list?

after that, think of the time you need for building a heap out of $n$ elements in abitrary order


VC Dimension Calculation for Intervals As i See in ML Course a VC dimension calculation is very theoretical.

What is the VC-dimension of intervals in R?

The target function is specifieed by an interval, and labels any example positive i it lies inside that interval.

Answers:

VC-dim = 2. A set of two points can be shattered, since there's only a single block of positive examples that could lie within the interval. But no set of 3 points can be shattered, because it can not be labeled in alternating +; - ; + order.

so i'm get stuck with meaning of interval.

for example, it means {(a, b) | "a is lower than b", a,b is real number} has VC-dim = 2?

Any idea or solution would be highly appreciated.

Yes, an open interval in $\mathbb{R}$ is defined as $(a,b) = ]a,b[ = \left \{ x \in \mathbb{R}|\,a<x<b\right \} $. It has two parameters $a$ and $b$. The sets of all open intervals, i.e. $\left \{  \left \{ x \in \mathbb{R}|\,a<x<b\right \} | a,b \in \mathbb{R}\right\}$ has a VC dimension of 2 for the reason you mention. Keep in mind that the VC dimension of a hypothesis set $H$ is the most points $H$ can shatter.). To put it graphically:

(image from CalTech's free machine Learning online course by Yaser Abu-Mostafa Learning from Data)


Language of all sequences of permutations whose product is the identity Let $\Sigma$ be the set of all permutations in $S_n$. What is the minimum number of states in a DFA accepting the language of all words over $\Sigma$ which multiply to the identity permutation?

For example, if $n=2$, then $\Sigma$ consists of two mappings, the identity mapping $\iota$ and the transposition $\tau$. The language in this case consists of all words containing an even number of $\tau$'s.

You haven't stated what happens to the empty word – I'm assuming it's accepted.

It is easy to check that the equivalence classes of the Myhill–Nerode relation correspond to all words multiplying to a certain permutation. Therefore the minimal DFA contains $n!$ states.

If the empty word is not allowed, there are $n!+1$ equivalence classes, one of them consisting only of $\epsilon$.


My code works, But how do I make this code run in a deterministic time? The Problem:
Given 3 inputs Bounce, Ball drop height, and ball view height.

How do I calculate the number of times the observer can see the ball pass.
So my code gives correct output, but it takes a longer time as bounce approaches 1, how do I make it deterministic in nature.

def bouncingBall(h, bounce, window):
    BounceFactor = bounce
    BallDropHeight = h
    ViewerHeight = window
    BounceLeft = h
    BallSeenTimes = 1
    if bounce > 1 or bounce < 0 or window >= h or h ==0:

        return -1
    else:
        while (BounceLeft > ViewerHeight):
            BounceLeft = BounceLeft * BounceFactor
            if (BounceLeft > ViewerHeight):
                BallSeenTimes = BallSeenTimes + 2
            else:
                break
        return BallSeenTimes

I am not looking for code answers, just the direction in which I need to think.
Currently, I think If I could somehow establish a linear relationship and create a function to "guess" the passes it would be faster.

Your code is determinstic: it uses no randomness. But I assume you want the running time to be essentially independent of the input.

Assuming I've understood the problem correctly, you're dropping a ball from height h and, when dropped from height x, it bounces to height x*Bouncefactor. You want to know how many times it passes through the height you're calling window.  Your approach is, essentially, to simulate the bouncing ball and count.

Instead of doing that, you should just calculate how many times the ball bounces before it's at height less than window.  This is the least k such that h * Bouncefactor^k < window, so you just need to solve this equation and then convert the number of bounces into the number of times that the ball is seen.


Polynomial-time reduction of Primality and 3-SAT Is 3-SAT $\leq_{p}$ Primality? And/or is Primality $\leq_{p}$ 3-SAT? I think the answer is no and yes, respectively, but I'm not sure. Any help would be appreciated.

Thank you.

For the first question: This is an open problem. If $\mathsf{P} \neq \mathsf{NP}$ then the answer is no: the decision version of 3-SAT is $\mathsf{NP}$-Complete, while Primality is in $\mathsf{P}$, the means that a Karp reduction from 3-SAT to Primality would imply $\mathsf{P}=\mathsf{NP}$.

For the second question:
Primality is in $\mathsf{P} \subseteq \mathsf{NP}$, therefore there is a Karp reduction from Primality to any $\mathsf{NP}$-Complete problem, such as 3-SAT.


Complexity of union-find with path-compression, without rank Wikipedia says union by rank without path compression gives an amortized time complexity of $O(\log n)$, and that both union by rank and path compression gives an amortized time complexity of $O(\alpha(n))$ (where $\alpha$ is the inverse of the Ackerman function).  However, it does not mention the running time of path compression without union rank, which is what I usually implement myself.

What's the amortized time complexity of union-find with the path-compression optimization, but without the union by rank optimization?

Seidel and Sharir proved in 2005 [1] that using path compression with arbitrary linking roughly on $m$ operations has a complexity of roughly $O((m+n)\log(n))$.

See [1], Section 3 (Arbitrary Linking):
Let $f(m,n)$ denote the runtime of union-find with $m$ operations and $n$ elements. They proved the following:

  Claim 3.1. For any integer $k>1$ we have $f(m, n)\leq (m+(k−1)n)\lceil \log_k(n) \rceil$.

According to [1], setting $k = \lceil m/n \rceil + 1$ gives
$$f(m, n)\leq (2m+n) \log_{\lceil m/n\rceil +1}n$$.

A similar bound was given using a more complex method by Tarjan and van Leeuwen in [2], Section 3:

  Lemma 7 of [2]. Suppose $m \geq n$. In any sequence of set operations implemented using any form of compaction and naive linking, the total number of nodes on find paths is at most $(4m + n) \lceil \log_{\lfloor 1 + m/n \rfloor}n \rceil$ With halving and naive linking, the total number of nodes on find paths is at most $ (8m+2n)\lceil \log_{\lfloor 1 + m/n \rfloor} (n) \rceil $.

  Lemma 9 of [2]. Suppose $m < n$. In any sequence of set operations implemented using compression and naive linking, the total number of nodes on find paths is at most $ n + 2m \lceil \log n\rceil + m$.

[1]: R. Seidel and M. Sharir. Top-Down Analysis of Path Compression. Siam J. Computing, 2005, Vol. 34, No. 3, pp. 515-525.

[2]: R. Tarjan and J. van Leeuwen. Worst-case Analysis of Set Union Algorithms. J. ACM, Vol. 31, No. 2, April 1984, pp. 245-281.


Is realization of unit disk graphs hard? It is known that recognizing a unit disk graph is NP-hard [1].
However, the paper does not mention how hard the realization problem is.
I have looked up several references [2][3][4]. None of the papers answer whether the following problem is NP-hard:

Given a unit disk graph $G = (V,E)$, find a configuration of a set
$\mathcal{D}$ of disks, such that the intersection graph
$G(\mathcal{D})$ of $\mathcal{D}$ is isomorphic to $G$.

The difference between this problem and the recognition problem is that the input of this problem is guaranteed to be a unit disk.
Is there any study that shows the complexity of the above problem? I expect it to be NP-hard, but I am yet to find a full proof.

One of the complications here is that there is no natural "decision variant" of this problem, since this isn't an optimization problem. (and the problem "given an UDG, is there a realization?" is trivial)
Since reductions between decision problems tend to be better studied, one option is to make it an optimisation problem in a chosen parameter. Even though you don't care about that value, you can use binary search on the optimisation problem to solve the realisation problem. Hence, the realisation problem is not much easier than the opt. problem, so showing the opt. problem is hard suffices.
The question then of course is what parameter to choose. Perhaps the problem "Given an UDG, find a realisation with minimum/maximum sum of edge lengths" would be suitable. It seems related to the problem that Aspnes et al. [1] show to be NP-hard.

[1]: ASPNES, James, et al. A theory of network localization. IEEE Transactions on Mobile Computing, 2006, 5.12: 1663-1678.


In first order logic, how do we normally represent a statement? I wanted for an example such as:

Everyone has a mother.

I've seen that it is represented in FOL as: $\forall x \exists y:$ Mother(x, y)

I'm seeing that as:For every x, there exists a y, such that y is a mother of x.

I want to know why isn't the following suitable:

$\forall x:$ hasMother(x)

Which I feel can be said as: For every x, x has a mother.

This is a good question and comes down to what you want to achieve with the Mother entity.

In your first example, Mother(x, y) is a (binary) relation.  That means that you can have as many ys as you would like per x.  With Mother as a relation, you can also make formula that checks whether you have two ys that satisfies motherhood for x.

In your other example, hasMother(x) is a predicate that can only be true or false.  How many mothers do x have? Impossible to say.  Who is x's mother?  We can't say.

You could also conceive of a mother(x) → y function that maps an x to its mother y, but then you can have only one mother, and every x needs to have a mother (in the model).

It all comes down to (a) what is a natural representation of "the world" (whatever you want to model), and (b) what you want to achieve (whatever you want to get out of your model).


Analysis of brute force decoder in a $q$-ary erasure channel Consider the $q$-ary erasure channel with erasure probability $\alpha$, i.e. given $x\in\mathbb{F}_q$ with probability $\alpha$ it outputs $?$ and with probability $1-\alpha$ outputs $x$.

For a linear code $\mathcal{C}$ generated by an $n\times k$ matrix $G$ over $\mathbb{F}_q$, we take a decoder $D:(\mathbb{F}_q\cup\{?\})^n\to\mathcal{C}\cup\{\text{fail}\}$ such that:

$$D(y) = \begin{cases}
      c & \text{if}\ \exists!\ c\in\mathcal{C}:y\ \text{agrees with}\ c\ \text{on the unerased entries in}\ \mathbb{F}_q \\
      \text{fail} & \text{otherwise} \\
   \end{cases}$$

For a set $J\subseteq [n]$ let $p_G(J)$ be the probability that $D$ outputs “fail” conditioned on the erasures being indexed by $J$.

Prove that $\mathop{\mathbb{E}}\limits_{G\in \mathbb{F}_q^{n\times k}}[p_G(J)]\leq q^{k-n+|J|}$.

Let $p_G$ be the probability that $D$ outputs “fail”. Show that when $k = Rn$ for $R<1-\alpha$, $\mathop{\mathbb{E}}\limits_{G\in \mathbb{F}_q^{n\times k}}[p_G]$ is exponentially small in $n$.

For the first part I think that if the errors occurred are indexed by $J$, we are left with $n-|J|$ correct entries, so $D$ fails when the corresponding $n-|J|$ rows of $G$ does not imply a unique solution to the set of linear equations. But I don't know how to compute the probability of such an event.

For the second part I took random variables $\forall\ J\subseteq [n]:\mathbf{1}_J$ which indicates whether the errors occurred are indexed by $J$. It is clear that $\mathbb{E}[\mathbf{1}_J]=\alpha^{|J|}(1-\alpha)^{n-|J|}$ and I tried to use the above bound for all the $J$'s with $|J|\leq n-k$ and a bound of $1$ with the other $J$'s, but it doesn't seem to be sub-exponential at the end. Moreover I ended up with partial binomial theorem sums and I failed to estimate them.

To upper bound the first probability, we can assume without loss of generality that the sent codeword is the zero codeword. After deleting $|J|$ rows, we are left with a random $(n-|J|)\times k$ matrix $A$, and we want to bound the probability that its (right) kernel is non-trivial, that is, that there is a non-zero vector $x$ such that $Ax=0$. For any non-zero vector $x$, $Ax$ is a uniformly random vector (why?), and so the probability that $Ax=0$ is $q^{-(n-|J|)}$. Since there are $q^k-1$ many non-zero vectors $x$, the union bound shows that the probability that one of them satisfies $Ax=0$ is at most $q^k \cdot q^{-(n-|J|)}$. We can slightly improve on this by considering vectors up to scalar products, which reduces the probability by a factor of $q-1$.

The second half involves applying Chernoff's bound (also known as Hoeffding's bound) to show that it is unlikely that there are many erasures, and then applying the bound in the first half. Choose the threshold so that $q^{k-n+|J|} \leq q^{-\epsilon n}$.


Why would anyone want CISC? In our computer systems lecture we were introduced to the MIPS processor. It was (re)developed over the course of the term and has in fact been quite easy to understand. It uses a RISC design, that is its elementary commands are regularly encoded and there are only few of them in order to keep the wires simple.

It was mentioned that CISC follows a different philosophy. I looked briefly at the x86 instruction set and was shocked. I can not image how anyone would want to build a processor that uses so complex a command set!

So I figure there have to be good arguments why large portions of the processor market use CISC architectures. What are they?

There is a general historical trend.

In the olden days, memories were small, and so programs were perforce small. Also, compilers were not very smart, and many programs were written in assembler, so it was considered a good thing to be able to write a program using few instructions. Instruction pipelines were simple, and processors grabbed one instruction at a time to execute it. The machinery inside the processor was quite complex anyway; decoding instructions was not felt to be much of a burden.

In the 1970s, CPU and compiler designers realized that having such complex instructions was not so helpful after all. It was difficult to design processors in which those instructions were really efficient, and it was difficult to design compilers that really took advantage of these instructions. Chip area and compiler complexity was better spent on more generic pursuits such as more general-purpose registers. The Wikipedia article on RISC explains this in more detail.

MIPS is the ultimate RISC architecture, which is why it's taught so often.

The x86 family is a bit different. It was originally a CISC architecture meant for systems with very small memory (no room for large instructions), and has undergone many successive versions. Today's x86 instruction set is not only complicated because it's CISC, but because it's really a 8088 with a 80386 with a Pentium possibly with an x86_64 processor.

In today's world, RISC and CISC are no longer the black-and-white distinction they might have been once. Most CPU architectures have evolved to different shades of grey.

On the RISC side, some modern MIPS variants have added multiplication and division instructions, with a non-uniform encoding. ARM processors have become more complex: many of them have a 16-bit instruction set called Thumb in addition to the “original” 32-bit instructions, not to mention Jazelle to execute JVM instructions on the CPU. Modern ARM processors also have SIMD instructions for multimedia applications: some complex instructions do pay after all.

On the CISC side, all recent processors are to some extent RISC inside. They have microcode to define all these complex macro instructions. The sheer complexity of the processor makes the design of each model take several years, even with a RISC design, what with the large number of components, with pipelining and predictive execution and whatnot.

So why do the fastest processors remain CISC outside? Part of it, in the case of the x86 (32-bit and 64-bit) family, is historical compatibility. But that's not the whole of it. In the early 2000s, Intel tried pushing the Itanium architecture. Itanium is an extreme case of complex instructions (not really CISC, though: its design has been dubbed EPIC). It even does away with the old-fashioned idea of executing instructions in sequence: all instructions are executed in parallel until the next barrier. One of the reasons Itanium didn't take is that nobody, whether at Intel or elsewhere, could write a decent compiler for it. Now a good old mostly-sequential processor like x86_64, that's something we understand.


Finding the maximum possible size of S, where S is a set of pairwise-disjoint subsets of the list, and every element of S sums to k Say I had a list of numbers in the range of 1-20 for example: [5, 16, 17, 3, 2, 14, 4, 9, 11, 19], and an integer k (let's say k = 40)

How would I find the maximum possible size of S, where S is a set of pairwise-disjoint subsets of the list, and every element of S sums to k?

I believe this algorithm is NP complete.

Just think of the problem as a bin packing algorithm but instead of saying that the total value of items in the bin must not exceed the bin's capcacity, I am saying that the total value of items in the bin must be exactly equal to the bin's capacity. Also, we are trying to maximise the number of bins.

Example scenario:

Say I have a list: [1, 2, 2, 3, 5, 6, 5] and k=7, then some example values of S would be:

[(3+2+2), (6+1)] - 5 and 5 left over

[(5+2), (5+2), (6+1)] - 3 left over

As you can see, the second solution is optimal because it produces 3 partitions rather than 2.

This problem is NP-complete.  Even testing whether there exists a single subset that sums to $k$ is NP-complete; that is known as the subset sum problem.  Therefore, you should not expect any efficient solution to this problem.

If you are asking for any way to solve it, without regard to efficiency, one approach is to enumerate all possible subsets that sum to $k$, build a graph with an edge between each pair of subsets that are not disjoint, and search for a maximum independent set in this graph.  Another approach would be to use integer linear programming; define the zero-or-one $x_{ij}$ integer variable to be 1 if the $i$th subset includes the element $j$, and then add constraints to reflect the problem statement, i.e., $\sum_j x_{ij} j = k$ and $x_{ij} + x_{i'j} \le 1$ for all $i\ne i'$.  Then, apply an off-the-shelp ILP solver.


PDA kleene star construction I know how to prove that CFL are closed under kleene star operation using CFG.
I can't find online or in class notes a proof using PDA.
I would appreciate description of the basic idea (not formal).

Use a PDA.  Suppose you have a PDA for language $L$ and you want to recognize $L^*$.  Given an input $x$, it is in $L^*$ if it can be partitioned as the concatenation $x=x_1 \cdots x_n$ of words $x_i$, where each $x_i \in L$.  Construct a PDA as follows: the PDA nondeterministically guesses the end of each $x_i$ (the boundary between $x_i$ and $x_{i+1}$); if it guesses that it is at a boundary, it checks that it is in an accept state and then pops everything off the stack and then transitions to its start state and continues from there.


How does a computer direct the processing of information So I'm reading Introduction to computing systems:From bits and gates to C and beyond, and the author states that a CPU is the mechanism that

...directs the processing of information. Which is figuring out what task should get carried out next

My question is: what exactly does he mean when he says that a processor "figures out" the next task that the computer has to carry out? Do we have a model for this from a software perspective?
The way that I currently understand this statement is that by "figuring out", he's referring to the Control Unit, from the Von Neumann model of a stored program computer, but I know there's different computer architectures out there. The author implying that the a computer is essentially a CPU in the same paragraph just adds to my confusion.

We have used the word computer many times in the preceding paragraphs, and
although we did not say so explicitly, we used it to mean a mechanism that does
two things: It directs the processing of information and it performs the actual
processing of information. It does both of these things in response to a computer program. When we say "directing the processing of information," we mean
figuring out which task should get carried out next. When we say "performing
the actual processing," we mean doing the actual additions, multiplications, and
so forth that are necessary to get the job done. A more precise term for this mechanism is a central processing unit (CPU), or simply a processor.

Given that this is an introduction, I wouldn't get too concerned about the wording. It's normal to describe things in general terms, and then go into specifics later.
In a typical computer system, everything ultimately happens because some program running in the CPU made it happen. Even with external events such as interrupts (e.g. someone typed on a keyboard, or a network packet arrived), it is software's responsibility to decide what that means.
Of course, the central processing unit isn't necessarily the only processing unit that you have to think about. Modern peripherals (e.g. DMA controllers, network adapters, USB hubs, monitors) tend to be quite "smart", and are often fully-realised computers in their own right.
For now, understand that the central processing unit is the programmable processing unit that a) directs the behaviour of the system as a whole, and b) is where general-purpose computation happens. This picture can be modified (e.g. to account for coprocessors) as you learn more.


Propagating node labels upwards in a tree I am trying to think of an efficient way to synchronize a tree's nodes with the following rules.

Consider for instance this tree:

so the top of the heap is always B which can have many leaf-type nodes called G, or children which are node themselves called S, which can have leaves as well (G)

it is possible in the future that each G will have many leaves, but I assume the algorithm will be the same

So each G has a list of categories, that I want to syncronize (add and remove) with their parents.

so if g1 has categories [a,b,c] then B will have [a,b,c], but if g2 has categories [a,g,w] B will have [a,b,c,g,w] (all the categories of its children)

if the S nodes' leaves have categories it goes the same, each G of an S node will have categories that will propagate to their parent (which will get all the categories of its children) and in return will propagate the categories up to B, and B will have a union of all categories below it.

if any of the G leaves changes categories, or if the a G is added or an S is added the entire tree/heap need to syncronize according the new categories added.

I need the categories to be syncronized when added or removed. So every time a category is added I need the parent to get the categories of its children, which sort of scan the whole tree again

Is there an efficient way to do this?

I understand your problem as follows (the best I could make of your presentation of it).

You have a tree rooted in node B. Each leaf is labeled wih
categories. Each other node is labeled with the categories of all
leaves below that node. The problem is to maintain proper labeling of
all nodes, when changing the labels of leaves or adding or removing
nodes from the tree.

The problem is easy when categories are added. You only have to
propagate new categories from where they are added up to the root.
The addition can come from adding a category to a leaf, or adding a
new node with its own categories as a leaf, or with the categories of
its daughters if it is an intermediate node.

The difficulty comes from removing categories, either by removing them
from a leaf, or by removing a node and all the nodes below it. The
difficulty comes from the fact that the categories it propagated
upward may still have to be kept somewhere on the path, because they are
provided by some other nodes.

However, this can be addressed very simply. Just keep a count of how
many times a category is provided to a node from the leafs below that
node. Then both addition and removal require only a bit of accounting.
You remove a category from the labeling of a node when its count falls to zero for that node.

Time complexity

The complexity analysis below is added by an edit from Billiska. It can only be partial since the OP did not clearly state how the structure is to be used. In particular, it seems that he also intends to add or remove whole subtrees. But the information needed for the purpose is available from the root of the subtrees (assuming categories have been propagated beforehand in subtrees to be added), so that operating on whole subtrees is very similar to operating on leaves.

Let the tree have depth of $d$.

Look-up category of a given node is $O(1)$ since the category information is always stored up-to-date for each node.

Add a category to a given leaf node is $O(d)$ since the count of that category has to be incremented for every ancestor node up to the root.

Remove a category from a given leaf node is $O(d)$. Just the revert of add, we decrements the count of that category for every ancestor node up to the root.


Quantum CNot algorithm problem I have a very simple quantum algorithm:

Let's start with two qubits in the state $|00\rangle$. I apply a Hadamard gate to the first one. Then I apply a CNot gate, with the first one as a control. Then I apply a Hadamard gate to both of them.

I think I should end up with with two qubits 100% in the $|00\rangle$ state. However, I tested this algorithm on two different simulators (QuantumPlayground and Davy Wybiral's), and the output of both was:

$$ 0.707\,|00\rangle ;\ 0.707\,|11\rangle\,. $$

Where did I go wrong?

The other answers explain how the circuit behaves. This answer will explain how to directly manipulate the circuit into a simpler form.

Here's a surprising fact: surrounding a CNOT with Hadamards flips the CNOT.

(I get that checking this on paper requires already understanding the solution to your question. You can confirm it for yourself in a circuit simulator such as Quirk at least.)

Your CNOT circuit is surrounded by 3 Hadamards. By flipping the CNOT, and using the fact that H is its own inverse, we can turn that into a single Hadamard:

Leaving us with the standard make-an-entangled-bell-pair circuit. So, when the input is $|00\rangle$, the output is $\frac{1}{\sqrt 2}|00\rangle + \frac{1}{\sqrt 2}|11\rangle$.


Deriving the regular expression for C-style /**/ comments I'm working on a parser for a C-style language, and for that parser I need the regular expression that matches C-style /**/ comments. Now, I've found this expression on the web:

/\*([^\*]*\*+[^\*/])*([^\*]*\*+|[^\*]*\*/

However, as you can see, this is a rather messy expression, and I have no idea whether it actually matches exactly what I want it to match.

Is there a different way of (rigorously) defining regular expressions that are easy to check by hand that they are really correct, and are then convertible ('compilable') to the above regular expression?

I can think of four ways:

Define an automaton for the language you are interested in. Convert the regular expression to an automaton (using Brzozowski's derivatives). Check that both automata accept the same language (determinize and minimize or use a bisimulation argument).
Write loads of test cases and apply your regular expression to them.
Convert the automaton defined in point 1 to a regular expression, using standard techniques.
A combination of the above.


Is it possible to implement a dictionary with efficient access according to insertion order? I am trying to build a generic data structure that needs to hold keys and values and in the same time keep track on the indices in which keys and values were put in, like arraylists do but in a complexity of $O(\log n)$ or less.

I tried to work around a solution to this problem and created various TreeMaps that has Integer indices and values and vice-versa, and the same with keys.

Just to make it more clear, the indices symbolize the insertion order from the user. So if I had 3 elements then their index values are 0, 1, 2 and if element 0 was deleted then I need to push 1 to 0 and 2 to 1 and a new element would be added with index 2.

My problem is when I remove a key and its value, if I want to insert the next key and value in the right index I have to make sure all the old ones were set back by 1. I don't know how to do it and not to fall into $O(n)$ complexity.

My goal is to use existing data structures and mix them to get this result, please take a look at the methods I implemented as I need those.

What I am asking is how can I create a data structure for keys and values that has the put, remove, get, getValueByIndex, getKeyByIndex, getIndexByKey methods in it while each method takes $O(\log n)$ or less and the indices change at each deletion.

Is it possible? And if so what is the mixture of Data-structures to create this?

To summarize, this is what you require:

a dictionary that
offers find, add and delete in $O(\log n)$ time and also
GetByIndex, KeyByIndex and IndexByKey in $O(\log n)$ time, where the index is determined by insertion order.

The first part is easy: use any balanced search tree. Say we use AVL trees.

For the second, we can use a second tree but use an increasing counter as key. With a small change to the data structure, we can find the $i$th element in $O(\log n)$ time (rank selection). Thus, we don't have to change any indices; the tree structure maintains the order for us.

We can further link the two AVL trees back and forth.

Assuming we have an implementation AVL which provides efficient select and rank (zero-based) and has a field for crosslinks, this would be rough pseudocode:

class IndexedDictionary {
  dataTree  = new AVL()
  indexTree = new AVL()
  nextId = 0

  add(key, data) {
    dataNode  = dataTree.add(key, data)
    indexNode = indexTree.add(nextId, data)
    dataNode.crosslink = indexNode
    indexNode.crosslink = dataNode
    nextId += 1
  }

  delete(key) {
    i = index(key)
    dataTree.delete(key)
    indexTree.delete(indexTree.select(i).key)
  }

  find(key) {
    return dataTree.find(key).value
  }

  get(index) {
    return indexTree.select(index).value
  }

  key(index) {
    return indexTree.select(index).crosslink.key
  }

  index(key) {
    return indexTree.rank(dataNode.find(key).crosslink.key)
  }
}

Of course, delete(index) can be implemented similarly to delete(key). Delete can be implemented faster if you add an operation delete-ith to AVL, and have AVL-delete return the removed node.


Minimum spanning tree and its connected subgraph This problem is from the book [1]. In case of being closed as a duplication of that in [2], I first make a defense:

The accepted answer at [2] is still in dispute.
The proof given by @eh9 is based on Kruskal's algorithm.
I am seeking for a proof independent of any MST algorithms.

  Problem: Let $T$ be an MST of graph $G$. Given a connected subgraph $H$ of $G$, show that $T \cap H$ is contained in some MST of $H$.

My partial trial is by contradiction:

  Suppose that $T \cap H$ is not contained in any MST of $H$. That is to say, for any MST of $H$ (denoted $MST_{H}$), there exists an edge $e$ such that $e \in T \cap H$, and however, $e \notin MST_{H}$.
  Now we can add $e$ to $MST_{H}$ to get $MST_{H} + {e}$ which contains a cycle (denoted $C$).

  Because $MST_{H}$ is a minimum spanning tree of $H$ and $e$ is not in $MST_{H}$, we have that every other edge $e'$ than $e$ in the cycle $C$ has weight no greater than that of $e$ (i.e., $\forall e' \in C, e' \neq e. w(e') \le w(e)$).
  There exists at lease one edge (denoted $e''$) in $C$ other than $e$ which is not in $T$. Otherwise, $T$ contains the cycle $C$.

  Now we have $w(e'') \le w(e)$ and $e \in T \land e'' \notin T$, $\ldots$

I failed to continue...

Algorithms, Chapter 5: Greedy algorithms
"Minimum Spanning tree subgraph"@StackOverflow

Flaws in the accepted answer: When I re-read the accepted answer given by @Mahmoud A. today, I find flaws in it.

Consider the figures for an example:

In this example, $e = CE$. In figure (5), the edge $CD$ in the cycle created by adding edge $e = CE$ into $T_H$ is not in $T_G$ shown in figure (2), but we have $w(CD)<w(e=CE)$. So the claim "For every other edge $e' \notin T_G$ in the cycle we have $w(e′)=w(e)$" does not hold.

Note: In the following, I fix the flaws. I leave the answer given by @Mahmoud A. as accepted because it is original and insightful.

Correction: While where is an edge $e \in T_G \cap H$ such that $e \notin T_H$ do:

Adding $e$ to $T_H$ to create a cycle $C$.

1.1 Because $T_H$ is an MST of $H$, for every other edge $e' \in C$ we have $w(e') \le w(e)$. Otherwise, for any edge $e' \in C$ such that $w(e')>w(e)$, $T_H + \{ e \} - \{ e' \}$ has smaller weight than $T_H$.
1.2 Let $e = (u,v)$. Remove $e$ from $T_G$. Then vertices $u$ and $v$ are separated into two different connected components, denoted by $U \ni u$ and $V \ni v$, of $T_G$. Because $T_H$ is an MST of $H$ (which includes vertices $u$ and $v$) and $e \notin T_H$, there must be an edge $e'' \in C$ which connects the two components $U$ and $V$ again.
We claim that $w(e'') = w(e)$. In 1.1, we have proved that $w(e'') \le w(e)$ (replacing $e'$ there by $e''$). If $w(e'') < w(e)$, then $T_{G} - \{ e \} + \{ e'' \}$ has smaller weight than $T_G$.
1.3 According to 1.1 and 1.2 above, there are an edge $e'' \in C$ such that $e'' \neq e \land w(e'') = w(e)$. We replace $e''$ with $e$ in $T_H$ to obtain $T'_H = T_H - \{ e'' \} + \{ e \} \in MST_H$.
Since $e'' \notin T_{G} \cap H$ and $e \in T_{G} \cap H$, $T'_H$ contains one more common edge with $T_{G} \cap H$ than $T_H$ does.

Rename $T'_H$ to $T_H$

EndWhile

After the loop we have $T_{G} \cap H \subseteq T_H$.


Is Universality Theorem applicable to Halting problem? This is Universality theorem In the Computability, Complexity and Languages book written by Davis in page 70:

If $\phi^{(n)}(x_1,...,x_n,y) = \psi_P(x_1,...,x_n)$        $where$  #$(P) = y$
Theorem 3.1 (Universality Theorem): for each $n>0$ the function $\phi^{(n)}(x_1,...,x_n,y)$ is partially computable.

From what I understand of this theorem, the universal program is more like an interpreter it takes $x_1,...,x_n$ as input and $y$ as a program number and simulates what program with number $y$ does on the $x_i$s.
Since there is no program for halting problem so there is no $y$ for it to be passed to $\phi^{(n)}(x_1,...,x_n,y)$ so I think this theorem is not applicable to halting problem.Is it right?

By this book notation we have

$Halt(x,y)$ $\iff$ Program number $y$ eventually halts on input $x$.

Since there $Halt(x,y)$ is not computable predicate (theorem 2.1 page 68) there is no program that check if program number $y$ halts in input $x$ (for every $y$ and $x$), but this not mean that there is no program that run program number $y$ on input $x$!

By using universal program $\phi(x,y)$ we can run program number $y$ on input $x$. This means that $Halt(x,y)$ is r.e.

+if you think a bit more you can observe that program number y can get stuck in loop on input x, and that's why $Halt(x,y)$ is not computable.


Is it possible to reduce a SAT problem to it's simplest form with no assumed variables in P time? So as you read in the title I want to know if it is possible in polynomial time to reduce a SAT problem to it's simplest version in CNF format with no assumed variables?

The simplest form is with minimal gates in the circuit, assumed variable is not important it was assuming the value of a variable.

An example, I have a problem which has only one solution and it is phrased in CNF/SAT but a simpler version in CNF would be a list of conjunct clauses with only one var is it possible to simplify to that.

What if i already know the problem has a solution can simplification run in P time?

No, this is not possible, unless $P=NP$.

Why? The formula $x \wedge\lnot x$, which is always false, is technically in CNF. But, this is unsatisfiable.

Suppose we could do this in polynomial time? Then to check of a problem is satisfiable, we just minimize it. If it minimizes to our false formula, then it's not satisfiable. If it minimizes to anything else, it must be satisfiable! So we've solved SAT in polynomial time.

In terms of gates, we have the same problem: if a formula is UNSAT, then always outputting LOW is the minimal gate circuit that's equivalent.


Efficient (sublinear) approximation algorithms for matrix-vector multiplication? Given a matrix $A \in \mathbb{R}^{n \times p}$ and a vector $x \in \mathbb{R}^p$, I am interested in computing the value of the mean matrix-vector product:

$$v = \frac{1}{n} Ax$$

If I did this using standard matrix-vector multiplication, then it would take $O(np)$ operations. I am wondering if there exists an approximate approach that can do better (that is sublinear in $n$ or $p$).

One approach is to treat each component of the result as a separate approximation problem. In this case, we can assume that $A$ is a row vector, so really the problem is to approximate a dot product $\sum_{i=1}^p a_ix_i$, or equivalently, to approximate the mean of the terms, $\frac1p\sum_{i=1}^p a_ix_i$.

This can be done by selecting a random sample of the indices $1,\dots,p$, and taking the mean of $a_ix_i$ over the sample, and constructing the $z$ confidence interval, a standard statistical procedure. In order to apply a Central Limit Theorem type of result to show that this gives asymptotically correct confidence intervals, we would need some mild assumptions on the entries of $A$ and $x$ to ensure that, roughly speaking, the mean cannot be dominated by outliers in a small proportion of entries. If you had upper and lower bounds on the entries of $A$ and $x$, for instance, then you could use Hoeffding's inequality to bound the probability of the estimate exceeding a given margin of error.

Of course, this approach gives only a probabilistic approximation method; it cannot guarantee accuracy with 100% certainty. But this is not of practical significance, as long as the error probabilities can be made sufficiently low. And in any case, it's not too hard to show that there cannot exist a deterministic approximation algorithm running in sublinear time, so probabilistic approximation is all that we could ask for in this case.

If a separate confidence interval for each component is not a desirable form for the output, then the approach could probably be adapted to instead give a margin of error for the norm of the error vector (e.g., with respect to the $\ell^1$, $\ell^2$, or $\ell^\infty$ norms).


Learning juntas, with membership queries The junta problem is the following: we have a boolean function $f:\{0,1\}^n \to \{0,1\}$ that actually happens to depend on only $k$ of its input variables.  Given the value of $f(x)$ for many random values of $x$, we want to identify the $k$ input variables that $f$ actually depends upon.  In other words, secretly $f(x_1,\dots,x_n) = g(x_{i_1},\dots,x_{i_k})$ for some indices $i_1,\dots,i_k$; given many pairs $(x,f(x))$ where each $x$ is random, we want to find the $i_1,\dots,i_k$.

I am interested in a variant of the junta problem, where we are allowed membership queries.  In particular, at any point, we can choose a value $x$ and receive the value of $f(x)$.  The goal remains the same: We want to learn the junta, i.e., learn the indices $i_1,\dots,i_k$.

How many membership queries are needed, and what is the running time to learn the junta?

There is a simple, straightforward algorithm that uses something like $O(n)$ membership queries (first find $x,y$ such that $f(x)\ne f(y)$, then move from $x$ to $y$ by changing one bit of the input at a time, to identify $x',y'$ such that $f(x')\ne f(y')$ and $x',y'$ differ in a single bit position).  But can it be done with many fewer membership queries?  For instance, can we learn the junta with, say, $O(\lg n)$ membership queries?

Information theory shows that you need at least $\log_2 \binom{n}{k}$ queries. When $k$ is small, this is $\Theta(k\log n)$, which is probably enough. Consider for example the case $k=1$, and suppose for simplicity that $n$ is a power of $2$. By feeding the inputs $x_i = \text{bit $r$ of $i$}$ to $f$ you can recover the index $i_1$. (To determine whether the function is $i_1$ or $\lnot i_1$, feed the all-zero vector to $f$.)


does a DFA converted from NFA always contain 2^Q states? when converting an NFA to DFA, we create sub-sets of states in the NFA.
does it mean that every DFA-converted-from-NFA contain 2^Q states? or if some sub-sets are unreachable then they are not included in it?

The answer to the question depends on its precise meaning.

  when converting an NFA to DFA, we create sub-sets of states in the NFA. does it mean that every DFA-converted-from-NFA contain 2^Q states?

Yes, when applying the standard construction for DFA constrution the new automaton obtains a state set $2^Q$, the power set of $Q$, containing all subsets of original state set $Q$. This construction will always yield a deterministic automaton of that size even when the original automaton is deterministic.

  or if some sub-sets are unreachable then they are not included in it?

That touches on the difference between the "formal" construction and the more "practical implementation" that is usually taken. In the latter version we only take the states that are reached during construction. Technically, we just determine the connected component that includes the initial state (where we start the construction).

In the figure we see a NFA (with three states) and the DFA using the standard subset construction with eight states (formal interpretation) or four states (omitting the gray states not reached). (PS. I forgot to mark the final states in the gray part)


Side effect and recursion My algorithm professor said a recursive function should not have side-effects since it's a methodological error because recursion is "pure".
Anyway I don't understand why, even because I find side-effects useful and difficult to replace a recursive side-effect function with a "pure" one.

Recursion is orthogonal to side effects.

You can have a recursive function with side effects, or without.  You can also have a non-recursive function with side effects, or without.  It's a matter of opinion and taste whether it's better to avoid side effects in any particular situation.  As far as I know, there is no scientific evidence to support a claim that "you should always avoid side effects in any recursive function".

There are reasons to be wary of side effects.  They make programs more complex to reason about.  This doesn't mean you should never use side effects, but they have tradeoffs.  Perhaps one could argue that recursive functions are especially tricky to code and thus one should be especially wary of recursive functions with side effects -- personally, I don't know that I'm particularly persuaded by it.  Ultimately, I think it's a matter of taste and judgement, and it's unlikely that any "one-size-fits-all" rule will be scientifically justified.


Generating uniformly random bits from a stream of arbitrarily biased bits Say we have a function called GenBiasedBit. This function returns 1 with probability p (where p is an unknown real number between 0 and 1 exclusive) and returns 0 with probability 1 − p. How could I write a Las Vegas algorithm (called GenUnbiasedBit) that returns 1 or 0 with equal (nonzero) probability, using calls from GenBiasedBit as a source of randomness? I'm not really sure how to approach this problem. Since 1 and 0 must be generated with equal chance, I'm assuming they must both have a 50/50 chance of being selected. Since this is a Las Vegas algorithm, I'm not sure how to guarantee that its output is correct, if we don't know the probability of GenBiasedBit generating a 1 or 0.

We can simulate an unbiased coin as follows. Toss a pair of coins, and repeat until they produce different outcomes. If the outcome was H,T (heads followed by tails) output heads, and if it was T,H output tails.

Conditioning on the event that the above simulation halts (i.e. at some iteration $i$ we receive different outcomes), then both H/T have equal probability. The probability of a "bad output" in a single iteration (same result from both coins) is $p^2+(1-p)^2$, which is less than $1$ for $p\in (0,1)$. Thus, the probability of "failure" after $n$ iterations is bounded by $(1-2p(1-p))^{-n}$.


Lower complexity bounds without mutation Lower complexity bounds tend to be a very hard problem in general. Despite this, I was wondering if there are any theoretical results that relate lower complexity bounds for some class of problems in the case where mutation is allowed and in the case it's not allowed? In particular, what type of problems would be inherently harder to solve in a purely functional language on a RAM machine?

The following problem is why I started thinking about this: https://stackoverflow.com/questions/24105301/number-of-occurrences-in-list-of-each-element

See the section labelled "Negative result: you cannot avoid some slowdown, for some data structures" of https://cs.stackexchange.com/a/18266/755 for examples of problems whose solution in a functional language is inherently a bit slower than a solution in an imperative language with mutation.  One example is an array data structure; with mutation, you can achieve $O(1)$ worst-case time for both mutation and lookup, but with a functional language (with persistent data structures), you cannot.


Show that a regular language L contains only palindromes if and only if all words of length at most 3n are palindromes This is an extension of a previous question asked by a different user earlier:

Let $x, u, v, w, y, x', u', v', w', y'$ be words satisfying

$y'x' = xy$.
$y'u'x' = xuy$.
$y'v'x' = xvy$.
$y'w'x' = xwy$.
$y'v'u'x' = xuvy$.
$y'w'v'x' = xvwy$.

Then $y'w'v'u'x' = xuvwy$.

Now, using the above result, show that a regular language $L$ recognized by an NFA $M$ consists purely of palindromes if and only if $\{x \in L : |x| < 3n\}$ consists purely of palindromes, where $n$ is the number of states in $M$.  When I say that some language "consists purely of palindromes," I mean that every string in the language is a palindrome.

Suppose that $L$ satisfies your condition. We prove that $L$ accepts only palindromes by induction on the size of the word.

Let $a \in L$ be a word of length at least $3n$. Tracing some accepting computation of $a$ on the given NFA, some state must repeat at least four times, so we can write $a=xuvwy$ (where $u,v,w$ are non-empty), where the state after reading $x,u,v,w$ is the same, say $s$. So $u,v,w$ all have a computation that goes from $s$ to $s$. This implies that the NFA also accepts $xy,xuy,xvy,xwy,xuvy,xvwy$. By induction, all of these are palindromes, and so they satisfy the prerequisites of the lemma with $x',u',v',w',y'$ being obtained by reversing the unprimed string. The lemma then implies that $a$ itself is a palindrome.


If the Halting Problem was solvable, and we solved it, what would be its implications? Perhaps a way to better understand the Halting Problem's importance is to know what would happen or what could be possible if this was solved.
What would be the Halting Problem's implications in today's technology, mathematics and its practical applications, if it was somehow solved?

Maybe I should make a more serious answer. First off: the unsolvability of the halting problem by "conventional" computing methods is a logical theorem. It is very simple to prove, and can be proven in almost any reasonable logical framework (that can express the problem).
There are however two questions we can reasonably ask:

What are the mathematical consequences of having a halting oracle? A halting oracle can be imagined as a genie (instantly) giving us the answer to any halting problem we ask of it. This is a rather well studied subject in computability theory and the "world" in which you have access to such a genie is called the first turing degree.
An interesting observation is that even given such an oracle, we can ask computational problems for which we cannot compute the answer, such as "does the turing machine $M$ with access to the halting oracle halt on all inputs"? The proof is almost identical to the original proof of undecidability of the halting problem!

What would happen if we could solve all halting problems that come up "in practice"? This isn't really a mathematical question, since you would need to define in practice but it's a really interesting scientific question. The whole field of termination analysis tries to find such algorithms. It works surprisingly well: if you write a reasonable program to compute some quantity, odds are that there is a tool in this list that can handle it.
It's not too hard to find examples that break these tools though: even a program as simple as the $3n+1$ algorithm would choke them, since there it is not known whether it halts on all inputs. A lot of similar open problems in number theory (the twin primes conjecture, the existence of odd perfect numbers) can be expressed as a halting problem, which suggests that there are many such problems that can't be handled by any "reasonable" automated termination tool.


Solve X(n) = 2X(n-1) + 2 recurrence relation I'm trying to solve the excersice from Knuth's "Concrete
Mathematics":

A Double Tower of Hanoi contains 2n disks of n different sizes, two of
each size. As usual, we're required to move only one disk at a time,
without putting a larger one over a smaller one.

How many moves does it take to transfer a double tower from one peg to
another, if disks of equal size are indistinguishable from each other?

My solution was like this. Let $n$ be the number of disks of
different sizes and $X_n$ - number of moves. The first few solutions
are:

$n = 0$ $X_n = 0$

$n = 1$ $X_n = 2$

$n = 2$ $X_n = 6$

$n = 3$ $X_n = 14$

Recurrence is $X_n = 2X_{n-1} + 2$

We can add $2$ to both sides:

$X_n+2 = 2X_{n-1} + 4$

let $Y_n = X_n + 2$, then

$Y_n = 2Y_{n-1}$

$Y_n = 2^n$

$X_n = 2^n - 2$

The problem is that the correct solution is $2^{n+1} - 2$, but I
cannot find an error in my approach.

Your $Y_0$ is probably wrong. $Y_0$ must be equal to $X_0+2=0+2=2$. Then $Y_n=2^{n+1}$ and hence $X_n=2^{n+1}-2$. Please double check.


Good mathematical book on algorithms I’m a sucker for mathematical elegance and rigour, and now am looking for such literature on algorithms and algorithm analysis. Now, it doesn’t matter much to me what algorithms are covered, but very much how they are presented and treated.¹ I most value a very clear and precise language which defines all used notions in a stringent and abstract manner.

I found that the classic Introduction to Algorithms, by Cormen, Leiserson, Rivest and Stein is pretty neat, but doesn’t handle the mathematics well and is quite informal with its proofs and definitions. Sipser’s Introduction to the Theory of Computation seems better in that regard, but still offers no seamless transition from mathematics to algorithms.

Can anyone recommend something?

¹: The algorithms should at least invole the management of their needed data using classical non-trivial abstract data structures like graphs, arrays, sets, lists, trees and so on – preferably also operating on such data structures. I wouldn’t be too interested if the issue of usage and management of data structures was ignored altogether. I don’t care much about the problems solved with them, though.

I think the book you describe has a name. It is in seven volumes, only three and half  of which have been published. It is called The Art of Computer Programming,
(TAOCP) and is written by Donald Knuth.

It may be though that he will sometimes describe applications. But you can always skip that, and I doubt it makes much of the content. You should not be too disappointed with the maths.


Doubts abouts join implementation I'm studying advanced database and I can not understand some concepts related to the join.
I hope I'm in the right place to post my doubts, otherwise I'm sorry.

I realized that to make the equijoin there are several families.
In particular, the family that is based on the Cartesian product includes three main methods: nested loops, nested blocks and nested scans.

The nested loop method iterates on the outer relation R (tipically the smaller one) and for each tuple of R, it scans the internal relation S and applies the join condition.
Then it just use the join definition: Cartesian product + selection.
The cost of this process is:

C = |R| + |R| * |S|

You can get an improvement if instead of considering the tuples, consider the pages.
In this case the cost is:

C = P_R + |R| * P_S

Why? I do not understand.

From what I remember of Operating Systems, the logical memory is divided into pages and the physical memory in frames, where the pages are of the same size of the frames.
This is done to permit the non-contiguous allocation of files.

A tuple instead of what corresponds? I guess as a record (one line) of a table, but in this context what is it?

The nested blocks method is a further improvement because in main memory maintains a block of tuples of R.
The improvement is obtained by scanning S only once for each group of tuples of R.
A version of this charging algorithm in the tuples of R memory, then proceeds to S and examines the memory to find the S tuples that match any tuple of R.
This reduces the number of necessary S scans.
In this case the cost is:

C = P_R + P_R * P_S

I must admit that I did not understand very well this algorithm.
Someone could explain it better?

Thus a block is a set of tuples? And a set of tuples form one page?
I'm very confused.

Maybe some sketch could help me, I have not found that showed the tuples.

Thank you all

If I understand correctly, this is how I imagine the logical memory, physical memory, pages and frames:

Nested loops (tuple)

Again, as I understand it:

I apologize but I have not yet understood the nested loop (pages) and nested block :(

What do you mean with "We can achieve some improvement checking the tuples stored on one page of relation S for each record in relation R"?

And with "In Block nested approach each block in the inner relation S is read once for each block in the relation R which gives you the desired cost"?

I feel a bit stupid, sorry.

First of all let us talk about the cost measure .
The cost C is calculated actually in terms of the number of disk access made in order to compute the join.

A block is defined as the smallest unit of memory which is transferred from disk to main memory during a disk access.

A page is a contiguous block of memory. (set of blocks)

Anther term associated is the blocking factor. which is the number of records which can be present on a single block of memory.

Suppose we need to compute the join of relation RxS
The first method we first bring the relation R in the main memory which take n(R) disk accesses (n(R)= number of records in the relation R). Note that records and tuples mean the same thing. For each record in relation R we make another disk access to bring a single record of relation S to check the join condition this gives another n(r)*n(S) disk accesses.
the total being n(r)+n(R)*n(S)

We can achieve some improvement checking the tuples stored on one page of relation S  for each record in relation R.

In Block nested approach each block in the inner relation S is read once for each block in the relation R
which gives you the desired cost


Regular Languages and Separating Suffixes Preparing for the next semester, I wanted to give the following as a homework question, yet after a few attempts, I failed to solve it.
Given a language $L\subseteq \Sigma^*$ and two words $x,y\in \Sigma^*$, define the language $L_{x,y}$ consisting of all the separating suffixes of the words $x,y$ relative to the Myhill-Nerode relation of $L$. That is, $$L_{x,y} = \{ z\in \Sigma^*:  (xz\in L \wedge yz\notin L) \lor (xz\notin L \wedge yz\in L) \}$$
Is it true that if $L_{x,y}$ is regular for every $x,y \in \Sigma^*$ then $L$ is regular?
Thoughts:

The solution I had in mind works only for languages that have bad prefixes. A word $y$ is a bad prefix for $L$ if you cannot extend $y$ to a word in $L$. That is, $y\cdot z \notin L$ for every $z \in \Sigma^*$.
If $y$ is a bad prefix for $L$, then $L = L_{\epsilon,y}$, and so if $L_{\epsilon,y}$ is regular, we're done.
But clearly, some languages don't have bad prefixes.

The opposite claim is correct: if $L$ is regular, then $L_{x, y}$ is regular. This can be easily solved as follows. If $A = \langle Q, \Sigma, q_0 , \delta, F \rangle$ is a DFA for $L$, then one can define a DFA $B$ for $L_{x, y}$ over the product of $A$ with itself: $B = \langle Q^2, \Sigma, \langle \delta(q_0, x), \delta(q_0, y) \rangle, \delta', ((Q\setminus F) \times F) \cup (F \times (Q\setminus F))\rangle$. I omit the details.

For $\sigma \in \Sigma$, let $f_\sigma$ be the indicator function of $L_{\epsilon,\sigma}$, let $f$ be the indicator function of $L$, and let $b$ be the indicator of $\epsilon \in L$. If $w = \sigma_1 \ldots \sigma_n$ then
$$
f(w) = f_{\sigma_1}(\sigma_2 \ldots \sigma_n) \oplus f_{\sigma_2}(\sigma_3 \ldots \sigma_n) \oplus \cdots \oplus f_{\sigma_n}(\epsilon) \oplus b.
$$
Imagine a finite automaton reading the word in reverse (we know that regular languages are closed under reversal). The finite automaton maintains an accumulator $a$ initialized by $b$, and states of DFAs for the reverses of $L_{\epsilon,\sigma}$ for all $\sigma \in \Sigma$. When reading $\sigma_i$, it updates $a$ by $a \oplus f_{\sigma_i}(\sigma_{i+1} \ldots \sigma_n)$, and then updates the states of all DFAs. Finally, it accepts if $a = 1$.


Recurrence relation in 2 variables When analyzing an algorithm, the following recurrence relation popped up:

$T(n,d)=2T(n/2,d)+T(n,d-1)+O(dn)$

where $T(n,1)=O(n \log{n})$ and $T(1,d)=O(d)$.

By applying the Master Theorem inductively, for any particular $d$, it holds that $T(n,d)=O(n (\log{n})^d)$. However, it does not necessarily hold that $T(n,d)=O(n (\log{n})^d)$ because the constant hidden by the $O$-notation depends on the value of $d$.

I was hoping that the technically incorrect bound given by repeated application of the master theorem would be good enough. It turns out that this is actually a terrible, terrible bound. The actual values of $T(n,d)$ are orders of magnitude lower from what the asymptotic bound would predict. Does anyone know how to get a better bound?

Suppose $T(n,d) = 2T(n/2,d) + T(n,d-1) + dn$, that $T(1,d) = d$, that $T(n,1) = n\log n$, and that $n$ is a power of $2$. Then
$$
T(n,d) = dn\log n + T(n,d-1) + 2T(n/2,d-1) + \dots + nT(1,d-1).
$$
In particular,
$$
\begin{align*}
T(n,2) &= 2n\log n + n\sum_{i=0}^{\log n} i \\ &\approx
2n\log n + \tfrac{1}{2}n\log^2n, \\
T(n,3) &\approx 3n\log n + 2n\sum_{i=0}^{\log n} i + \tfrac{1}{2}n \sum_{i=0}^{\log n} i^2 \\ &\approx
3 n\log n + n\log^2 n + \tfrac{1}{6} \log^3 n,
\end{align*}
$$
and so on. More generally, we can think of $T(n,d)$ as a degree $d$ polynomial of the form $n\sum_{i=1}^d c_{d,i} \log^d n$. The coefficients are given by $c_{d,1} = d$ and $c_{d,i+1} = c_{d,i}/(i+1)$. Unrolling the recurrence, we obtain
$$
T(n,d) \approx n \sum_{i=1}^d \frac{d+1-i}{i!} \log^d n.
$$
In particular,
$$ T(n,d) = \frac{1}{d!} n\log^d n + O(n\log^{d-1} n). $$


Reducing "multiple satisfiability" to normal SAT I have to prove the NP-completeness of the following set:
QUADRUPLE-SAT:={F is Formula in CNF|F has at least 4 satisfying interpretations}

My idea so far has been to reduce the problem to the normal SAT by constructing a new formula, copying the original formula 4 times and using a new set of literals in every copy, then adding clauses to ensure that the 4 sets of literals are pairwise differently interpreted (there is at least 1 literal which is flipped). Such a formula is easy to find, I'm unable to get it to CNF though.

I might also be on the completely wrong track on this one, if you know another NP-complete problem this could be reduced to more easily, that would be great as well.

CNF-SAT can be reduced to QUADRUPLE-SAT by adding two new variables, $x_1$ and $x_2$, and adding the following CNF clauses.

$(x_1 \lor \lnot x_1)$

$(x_2 \lor \lnot x_2)$

Because $x_1$ and $x_2$ can take any value and not affect satisfiability, if the original formula had at least one solution then the new formula will have at least four.  And if the original formula had no solutions then the new formula will still have none.

Since CNF-SAT is NP-complete, then this reduction to QUADRUPLE-SAT proves the NP-completeness of the QUADRUPLE-SAT.


$\#P$ closure under binomial coefficients? It is quite straightforward to understand $\#P$ closure under addition and multiplication since there are canonical $NTM$ constructions.

Is there illustrative non-trivial example to understand $NTM$ construction for closure under binomial coefficients?

Let me take a guess: you mean an operation of the form $f(x) \mapsto \binom{f(x)}{d}$, where $d$ is a constant. Let's assume also that $f(x)$ is the number of $y$ such that $\phi(x,y)$. Then $\binom{f(x)}{d}$ is the number of $d$-tuples $y_1,\ldots,y_d$ such that $y_1 < \cdots < y_d$ and $\phi(x,y_1) \land \cdots \land \phi(x,y_d)$.


Regular and not Regular Grammar According the Peter Linz Book, am a confusing about the two example
the Grammar G1 = ({S},{a,b},S,P1) with P1 given as

S -> abS|a

and G2 = ({S,S1,S2,},{a,b},S,P2)

S -> S1ab
S1 -> S1ab|S2
S2 -> a

G1,G2 is regular..

i generated from G1 Language= {ababa,...} and it Regular expression (ab)a
and from G2 = {aabab} is that right it regular expression a(ab) in the book it show its aab(ab)* but how

First, is it write regular expression ??
Why this G3 = ({S,A,B},{a,b},S,P) with Production

S -> A
A -> aB | 'epsilon'
B -> Ab

is not regular ? although its left or right linear prodcution.

second why G3 is not regular ?

Consider $G_1$. Strings generated by this grammar could be derived by repeated use of the production $S\rightarrow abS$ followed by one use of $S\rightarrow a$ to eliminate the variable $S$. Consequently, we can generate strings in the language by repeatedly adding $ab$ to the right and ultimately stopping by adding an $a$ to the right:
$$
S\Rightarrow ab\color{red}S\Rightarrow ab\color{red}{abS}\Rightarrow abababS\Rightarrow\dotsm (ab)(ab)(ab)\dotsm a
$$
so we generate strings of the form
$$
\underbrace{ab\ ab\ \dotsc ab}_{\text{$0$ or more}}\ a
$$
which corresponds to the regular expression $(ab)^*a$, so $L(G_1)$ is regular. Note that $G_1$ is a regular grammar, since it's a right-linear grammar, namely one for which all the productions are of the form $A\rightarrow xB$ or $A\rightarrow x$ where $A, B$ are variables and $x$ is a string of terminals.

Grammar $G_2$ is only slightly more complicated. We now have four productions

$S\rightarrow S_1ab$
$S_1\rightarrow S_1ab$
$S_1\rightarrow S_2$
$S_2\rightarrow a$

Now a string of terminals can only be generated by production (1) adding $ab$ to the left (since the grammar is left-linear), followed by zero or more productions (2) adding another $ab$ to the left, followed by production (3) and then production (4) adding $a$ to the left. We then can generate strings
$$
a\ \underbrace{ab\ ab\ \dotsc ab}_{\text{$0$ or more}}\ ab
$$
In a way similar to the above, a regular expression denoting $L(G_2)$ could be $aab(ab)^*$.

Your $G_3$ is not a regular grammar, since in such a grammar, all productions must either be right-linear or left-linear. In $G_3$ the production $A\rightarrow aB$ is right-linear but the production $B\rightarrow Ba$ is left-linear. A regular grammar cannot, by definition, have both right- and left-linear productions.

By the way, $L(G_3)=\{a^nb^n\mid n\ge 0\}$ which you'll soon learn is not a regular language.


Smallest possible sorting network for given permutation I need to build a sorting (comparator) network using comparators for a specific permutation on a set $x_1, \dots, x_n$. The solution should not be a general sorting network that sorts every permutation. I should build the smallest possible sorting network for the given permutation (the depth of the network should be $O(\log n)$).

I am really unsure about how to approach this problem. I thought I might go through the permutation and if the number is in the correct spot then leave it, if not then place a comparator with this number as input and the number that should be here as the second input. But I don't think that the depth of such network would be $O(\log n)$. So how would I go about building the needed network?

For concreteness, let us assume that $x_1,\ldots,x_n$ are numbers between $1$ and $n$, and that a comparison puts the smaller number at the smaller index.

Consider first the case in which $n$ is even. We divide $x_1,\ldots,x_n$ into two halves: $x_1,\ldots,x_{n/2}$ and $x_{n/2+1},\ldots,x_n$. Let us call a number misplaced if it is in the wrong half: that is, a number in the first half is misplaced if it is in $\{n/2+1,\ldots,n\}$, and a number in the second half is misplaced if it is in $\{1,\ldots,n/2\}$. Note that the first half contains as many misplaced numbers as the second half (why?). Using one round of parallel comparisons, you can exchange the locations of the misplaced numbers, and guarantee that $\{x_1,\ldots,x_{n/2}\} = \{1,\ldots,n/2\}$, and similarly $\{x_{n/2+1},\ldots,x_n\} = \{n/2+1,\ldots,n\}$. Now recursively sort each half, in parallel.

When $n>1$ is odd, we use the same strategy, dividing the array into two unequal halves, say the first half larger than the second by one element.

As an illustration, suppose that we are given the array
$$3,4,2,6,1,5$$
We switch $1$ and $4$ to obtain
$$3,1,2,6,4,5$$
Now we recursively sort $3,1,2$ and $6,4,5$.

In order to sort $3,1,2$, we first exchange $1$ and $3$ to obtain $1,3,2$, and then sort the two halves $1$ and $3,2$ in parallel, which means to exchange $2$ and $3$.

Sorting $6,4,5$ is completely analogous.


Is in-place run length encoding possible in O(1) space given that the output is shorter than the input? This is inspired by a problem from here. This is the approximate form of the problem:
Given a string like "aaaa777cbb" (10 symbols long), run length encode it in-place to a string like "a473c1b2" (8 symbols long). You are guaranteed that the input will always be longer than the output.
The precise form of the problem is:

You are given an ordered list $L$ of symbols from a set $S$. Any symbol from $S$ may appear in the list.
$S$ contains all the positive integers up to and including $|L|$ (the length of $L$) and also some other symbols.
Rules of manipulating the input in-place

You can replace one symbol in the list with another
You can trim the list to a length of your choice by removing symbols from the end
You cannot insert symbols

You must overwrite the list of symbols with it's run-length-encoding representation and trim it to length so that it includes only the run-length-encoding representation.

The run-length-encoding representation replaces each series of 1 or more of the same symbol in the input with that symbol followed by the symbol representing the number of occurrences of the previous symbol.

For example: $[a, a, a, a, a, a, a, a, a, a, 7]$ becomes $[a, 10, 7, 1]$ meaning "$a$ ten times followed by $7$ one time"
Note that the length of the output list is always even

You are guaranteed that the length of the input list is always larger than the length of the output list

You must do this with $O(1)$ additional working memory

Each "word" of working memory contains $log_2 |S|$ bits (put another way, words may be constructed which store constant amounts of information, the position of any element in the input, or any symbol from the input)

Intuitively I don't think this is possible. The solutions provided on the original site seem to break on strings like "abccccc" (length 7) where the output should be "a1b1c5" (length 6), since they start by overwriting "b" with the "1" from "a1" before they have even checked which symbol is in the 2nd position.
I have thought about trying to start by finding the compressible runs of letters (2 or more of the same letter), but I don't know how to tell which symbols are already processed and which are from the original input without using some sort of memory that which would grow with the size of the input (like a bitmap of processed areas) and therefore put me in violation of the $O(1)$ space requirement.
I consider acceptable answers to be proofs that this problem either is or is not solvable in $O(1)$ space.

An $O(1)$ space algorithm that uses one extra symbol not found in $L$, which I will call $B$ for blank space.
I define an operation, a "shift right" at position $k$. It finds the next blank symbol $B$ after position $k$ , shifts all symbols one to the right, and sets position $k$ to $B$. For example a right shift at the third symbol:
abcdeBfjgB    becomes    abBcdefjgB
  ^                        ^

Similarly a "shift left" at position $k$ assumes there is a $B$ symbol there, and moves it all the way to the end of the string, shifting all other symbols left.
abBdeBfjgB    becomes    abdeBfjgBB
  ^                        ^

Note that you can perform both shifts in $O(1)$ memory.
Now, first we replace all runs of any symbol $x$  with length $l \geq  3$ or greater with $xlB^{l-2}$. This can be done in-place, and leaves such runs identifiable. Also note that these are all the runs that shortens the output compared to the input.
Then, move a single pointer $p$ from left to right:

If the string at the pointer starts with $B$, shift left.

If the string at the pointer starts with $xlB^+$, this is the start of a run with length at least 3. Increment $p$ by $2$.

If the string at the pointer starts with $xx$ replace it with $x 2$ and increment $p$ by 2. Note that $xx$ can never be the start of a run of length 3 or higher, since we already replaced those.

If the string at the pointer has form $xy$, increment $p$ by 1, shift right, and replace the resulting $B$ at $p$ with $1$. Increment $p$ by 1 again. Note that the shift right must succeed due to the guarantee the output is shorter than the input, and we already created all space possible when replacing all runs of length $3$.

If any space is left over at the end, the algorithm will eventually get stuck performing step 1. Detect this, strip the remaining space, and you are done.


Infinite alphabet Turing Machine Is a Turing Machine that is allowed to read and write symbols from an infinite alphabet more powerful than a regular TM (that is the only difference, the machine still has a finite number of states)?

Intuition tells me not, since you need an infinite number of states to differentiate each symbol. So I think some of the symbols or the transitions caused by the symbols (or some subsets of the transitions) have to be equivalent. So you can actually simulate such machine with a regular TM and a bounded subset of such symbols or transitions.

How could I approach a formal proof of this?

No, it would be more powerful. The transition function would no longer be finite, and that buys you a lot of power.

With an infinite alphabet, you can encode any input item from an infinite set in one symbol (although the input set can't be "more infinite" than the alphabet set, e.g. the alphabet would presumably be only countably infinite, so elements of uncountable sets like the real numbers couldn't be represented in one symbol). And likewise for the output.

So you can make a two-state (one initial, one accept) infinite-alphabet-TM with a single transition that moves to the accept state and changes the symbol under the tape head in accordance with the function you're trying to compute. This recipe would allow you to compute any mapping between sets that can be put in a one-to-one correspondence with the alphabet.

So to avoid that degenerate sort of machine being the answer to everything, you'd need to restrict what the transition function can do. An obvious one would be to require the transition function itself to be computable (ordinary TM's transition functions are trivially computable after all, since they're finite). But then you'd be trying to use computable functions to define your model of computable functions.


Can a TM recognize whether another TM recognizes a non-empty language? Let $$L_1 = \{\langle M\rangle\mid M \text{ is a Turing Machine and }L(M)\ne\emptyset\}.$$
Is $L_1$ recognizable? If so, can you give me a pseudo-algorithm?

My attempt:

I wanted to study reachability the same way one does with DFA/NFA. However although a transition might be defined between $q_i$ and $q_j$ for $ x \in \Gamma  $ is no guarantee that the configuration is possible.

I will use the following definition of $L(M)$: it is the set of inputs for which $M$ halts.

I will use the following definition of recognizable: a language $L$ is recognizable if there exists a Turing machine $M$ such that $L = L(M)$.

In order to recognize $L_1$, on input $\langle M \rangle$, we simulate $M$ on all possible inputs (using dovetailing), and if $M$ halts on any input, we halt.

In order to simulate $M$ on all possible inputs, we list all possible inputs in a sequence $x_1,x_2,\ldots$, and then work as follows:

Initiate a run of $M$ on $x_1$, and advance it one step.
Initiate a run of $M$ on $x_2$, and advance both existing runs by one step each.
Initiate a run of $M$ on $x_3$, and advance all three existing runs by one step each.
And so on.

If $M$ halts on any input, then we will eventually notice it, and then immediately halt. Conversely, if $M$ never halts, then we will also never halt.


Proving correctness and optimality of a greedy algorithm Here is a (slightly abridged) problem from Kleinberg and Tardos:

Consider a complete balanced binary tree with $n$ leaves where $n$ is a power of two. Each edge $e$ of the tree has an associated length $\ell_e$, which is a positive number. The distance from the root to a given leaf is the sum of the lengths of all the edges on the path from the root to the leaf.

Now, if all leaves do not have the same distance from the root, then
the signals we send starting from the root will not reach the leaves at the same time, and this is a big problem. We want the leaves to be completely synchronized, and all to
receive the signal at the same time. To make this happen, we will have to
increase the lengths of certain edges, so that all root-to-leaf paths have
the same length (we’re not able to shrink edge lengths). If we achieve this, then we say the tree has zero skew.

Give an algorithm that increases the lengths of certain edges so that
the resulting tree has zero skew and the total edge length is as small as
possible.

This problem was in the "Greedy Algorithms" chapter.

I know the solution to this problem is as follows:

Let the subtrees below the root be $L$ and $R$. If the maximum sum of the edge lengths on the path to a leaf in $L$ starting from the root is greater than the maximum sum of the edge lengths on a path to a leaf in $R$, then increase the edge length from the root to the right subtree by the positive difference between the two.

Conversely, if the maximum sum of the edge lengths on a path to a leaf in $R$ starting from the root is greater than the maximum sum of the edge lengths on a path to a leaf in $L$, then increase the edge length from the root to the left subtree by the positive difference between the two.

I am having trouble proving the following:

$1)$ The resulting tree upon termination of this algorithm is a zero-skew tree (the length from the root to any leaf is the same).
$2)$ The sum of the edge lengths is minimized with this algorithm.

I have tried to prove these facts in many ways, such as induction and direct proof, but I am having a lot of difficulty doing so. The algorithm makes sense to me intuitively, but I'm having trouble explaining why it works formally.

I would greatly appreciate some help in solving this problem.

Notation.
Given a binary tree $T$ and vertex $v$ of $T$, let $\ell_v$ and $r_v$ be the left and right children of vertex $v$ in $T$, respectively. Let $T_v$ be subtree of $T$ rooted at $v$.
Let $d_T(v)$ be the weighted distance between the root of $T$ and $v$ and $h(T) = \max_{v \in T} d_T(v)$.
If $(u,v)$ is an edge of $T$, let $w_T(u,v)$ be its weight.
With a slight abuse of notation, define $w(T) = \sum_{(u,v) \in T} w(u,v)$.
Finally, we define the skew of $v$ as $s_T(v) = w_T(v, \ell_v) + h(T_{\ell_v}) - w_T(v, r_v) - h(T_{r_v})$ if $v$ is an interval vertex of $T$ and $s_T(v)=0$ if $v$ is a leaf of $T$.

  1) The resulting tree upon termination of this algorithm is a zero-skew tree (the length from the root to any leaf is the same).

We will show by induction on $i=0,1,\dots$ that, for all trees $T$ with $2^{i+1} - 1$ vertices, the algorithm returns a tree in which all vertices have skew $0$.

The base case $i=0$ is trivially true since $T$ must have exactly one vertex and the algorithm does nothing.

Suppose now that $i>0$ and let $v$ be the root of $T$.
The trees $T_{\ell_v}$ and $T_{r_v}$ have exactly $\frac{(2^{i+1} - 1) - 1}{2} = 2^i - 1$ vertices and, by inductive hypothesis, the recursive calls on $T_{\ell_v}$ and $T_{r_v}$ ensure that all vertices, except possibly $v$, have skew $0$. The reweighing of $(v, \ell_v)$ and $(v, r_v)$ only affects the skew of $v$ and ensures that $s(v)=0$.

  The sum of the edge lengths is minimized with this algorithm.

Let $T'$ be the tree returned by the algorithm. Suppose that an optimal zero-skew tree $T^*$ obtained from the input tree $T$ by lengthening edges is such that $w(T^*) < w(T')$.

Let $(u,v)$ be an edge of $T$ (where $u$ is the parent of $v$) such that
$w_{T^*}(u,v) < w_{T'}(u,v)$ and the depth of $u$ is maximized.

Since  $s_{T^*}(u)=0$ and since $h(T_v^*) \ge h(T_v) = h(T'_v)$,
the sum of the weights in $T^*$ on each path from $v$ to a leaf in $T_v$
must have increased by at least $w_{T'}(u,v) - w_{T^*}(u,v)$.
Consider the subgraph of $T^*_v$ induced by the edges whose weight has not been increased w.r.t. $T$ and let $C$ be the connected component containing $v$.
Let $E$ be the set of edges with one endpoint in $C$ and the other in $T^*_v \setminus C$. Let $\Delta = \min_{(x,y) \in E} \{ w_{T^*}(x,y) - w_T(x,y) \}$.

Consider a new tree $T''$ that is obtained from $T'$ by reducing the weight of all edges in $E$ by $\Delta$ and increasing the weight of $(u,v)$ by $\Delta$.
The tree $T''$ is a feasible solution to your problem and weighs $w(T^*) - |E| \Delta + \Delta < w(T^*)$ (since $|E|\ge 2$). This is a contradiction.