Solution to the recurrence T(n) = 2T(n − 3) We were asked the following question in our exam:

Solve or bound the recurrence T(n) = 2T(n − 3) for n>3 provided T(1) = T(2) = T(3) = 1.

How do I go about solving this type of recurrence?  For a normal recurrence of the form T(n) = 2T(n - 3) + cn, I would have considered cn to be the root and then solved the remainder of the tree.  However, since the constant term is missing here, it means that the work done in each recursive call is 0.  So, what would be the time complexity?  Is my understanding incorrect?

Thanks for you help!

P.S.: This is not this, because this one has the constant term missing.

It is easy to see the first nine terms of $\small T(n)$ is:

$$
\small
\begin{array}{|c|c|c|c|c|c|c|c|c|}
\hline
\color{red}{T(1)} & \color{blue}{T(2)} & \color{olive}{T(3)} & \color{red}{T(4)} & \color{blue}{T(5)} & \color{olive}{T(6)} & \color{red}{T(7)} & \color{blue}{T(8)} & \color{olive}{T(9)} \\ \hline
1 & 1 & 1 & 2 & 2 & 2 & 4 & 4 & 4 \\ \hline
\end{array}
$$

  Observation: For integer $\small k \geq 0$, $\small T(3k+1) = T(3k+2) = T(3k+3)$. You can prove it by induction, where the base case is $\small T(1) = T(2) = T(3)= 1$.

Given $\small n$, let $\small k$ be the smallest integer with $\small 3k \geq n$. In other words, $\small k = \lceil n / 3\rceil$. By the observation above, $\small T(n) = T(3k)$. Therefore, we have
$$
\small
T(n) = T(3k) = 2\cdot T(3(k-1)) = 2^2\cdot T(3(k-2)) = \cdots = 2^{k-1}T(3) = 2^{k-1} = 2^{\lceil n / 3\rceil - 1}
$$


Prove/disprove that the class of decidable (resp. partially decidable) languages is closed under symmetric difference Prove/disprove that the class of decidable (resp. partially decidable) languages is closed under symmetric difference. A symmetric difference of sets A and B is the set (A \ B) ∪ (B \ A).

I know that the class of decidable languages is closed under symmetric difference, because it is closed under union, complement and intersection. However, does this also apply to the class of partially decidable languages?

Assume partially decidable languages are closed under symmetric difference, and let $A$ be a language that is partially decidable but not decidable.  Then, where $U$ is the language that includes everything,

$A \otimes U = (A - U) \cup (U - A) = \overline{A}$.

Then $\overline{A}$ must also be partially decidable, and $A$ is decidable; this is a contradiction.  (This builds on an answer above, which suggested investigating complementation.)


Cellular Automata Using Small Boards I'm working on making patterns for a digital lava lamp (essentially, making interesting patterns using a 4x10 grid), and I've been looking into cellular automata. I tried implementing some variations on Langton's Ant but it tends to loop in very boring ways. Does anyone have any suggestions for interesting automata on small boards?

The lamp I'm working on can be played with here.

Any suggestions on a more appropriate place to post this question are welcome.

EDIT: By interesting, I mean patterns that work well on small boards. For example,
Langton's Ant was not interesting because it always tended to find some static state over such a small board.

"interesting" is very subjective.

You could try Brian's Brain or Brian's Seeds, both of which I find interesting.
http://en.wikipedia.org/wiki/Seeds_%28cellular_automaton%29

While they are designed for an infinite plane, you could wrap your 4x10 grid at the top and bottom presenting a theoretical sphere instead of a plane.

As a interesting thought, you could start with Langton's ant and then add a swarm to the ant, then chose a random element of the swarm to take over control for the next X iterations.


Given an NFA A and a regular expression B, is the problem of determining L(A) = L(B) decidable? I have having trouble with the following question:

  Given an NFA $A$ and a regular expression $B$, consider the problem of determining if $L(A) = L(B)$. Is this decidable? Prove your answer.

Yes. Transform both into DFAs $M_1$ and $M_2$; from them construct DFAs for $L_1 \cap \overline{L_2}$ and $\overline{L_1} \cap L_2$, and check that neither accepts anything.

As noted in the comments, the NFA to DFA construction can give an exponential increase in number of states, same for regular expression to DFA, so this doesn't prove the problem is in NP. Luckily you weren't asked about that ;-)


Intuition for maxterms I understand that in terms of minterms,

F (Boolean Function) = Sum of Products and thus will yield true when either of the products is true.

But I am unable to develop any intuition for maxterms,

F(Boolean Function) = Product of Sums (of maxterms).

Is F =  Product of sums just a different way of representing F = Sum of Products?

If yes, is it possible to prove that using the duality principle?

Indeed, maxterm is the concept dual to minterm. As you mention,
$$
f(x) = \bigvee_{y\colon f(y)=1} \text{"$x=y$"} = \bigvee_{y\colon f(y)=1} \bigwedge_{i=1}^n \text{"$x_i=y_i$"}.
$$
Here $\vee$ is OR (your addition), $\wedge$ is ADD (your multiplication), the input is $x = x_1,\ldots,x_n$, and "$x_i=y_i$" is either $x_i$ (if $y_i$ is True) or $\bar{x}_i$ (if $y_i$ is False).

Similarly, we have
$$
f(x) = \bigwedge_{y\colon f(y)=0} \text{"$x \neq y$"} = \bigwedge_{y\colon f(y)=0} \bigvee_{i=1}^n \text{"$x_i \neq y_i$"}.
$$
This time "$x_i\neq y_i$" is $x_i$ if $y_i$ is False, and $\bar{x}_i$ if $y_i$ is True.

When the function is monotone, we can improve on the first representation:
$$
f(x) = \bigvee_{\text{$y$ minterm}} \text{"$x \geq y$"} = \bigvee_{\text{$y$ minterm}} \bigwedge_{i\colon y_i=1} x_i.
$$
Here "$x \geq y$" means $x_i \geq y_i$ for all $i$, and a minterm is a satisfying assignment of $f$ which is minimal in the sense that changing any 1 to 0 changes it to an unsatisfying assignment.

We can define maxterms analogously – maximal unsatisfying assignments, and then
$$
f(x) = \bigwedge_{\text{$y$ maxterm}} \text{"not $x \leq y$"} = \bigwedge_{\text{$y$ maxterm}} \bigvee_{i\colon y_i=0} x_i.
$$


Question about ε-moves at $\varepsilon NFA$ We learning know about ε-moves at $\varepsilon NFA$ and I'm little bit confuse...

If we have, for example, this  $\varepsilon NFA$:

and we have the word "$a$" - can we end the run at $s$? Or the running will be finish at $q$?
In other words what I'm tring to ask is this:
When we have an $\varepsilon$ - we first of all reading the letter from the input and then "jump"? or we can "jump" and then reading the input? (or we can do both).

I look at the definition of: $\hat{\delta}(q,a)$ (for a word) and $\delta(q,a)$ (for a letter), and I'm not sure if the answer to my question dependence at $\hat{\delta}(q,a)$ or $\delta(q,a)$, because:
$\hat{\delta}(q,a)=\{q,s\}$ and $\delta(q,a)=\{q\}$.

Thank you so much!
I hope I was clear (because I'm little bit confuse...)

In an $\varepsilon NFA$, when processing an $\varepsilon$ character, we can move on an $\varepsilon$-edge or we can stay on the state we are currently in.
And for example since $a= \varepsilon a \varepsilon\varepsilon$, in your $NFA$ these two paths are both correct:

$$p \rightarrow^{\varepsilon} p \rightarrow^{a} q \rightarrow^{\varepsilon} s \rightarrow^{\varepsilon} s$$

and

$$p \rightarrow^{\varepsilon} p \rightarrow^{a} q \rightarrow^{\varepsilon} q \rightarrow^{\varepsilon} s$$

Therefore, with the character $a$ we have $\delta(p,a)=q$ and for the word $a$ we have $\hat{\delta}(p,a)=\{q,s\}.$


Is “Find the shortest tour from a to z passing each node once in a directed graph” NP-complete? Given a directed graph with the following attributes: - a chain from node $a$ to node $z$ passing nodes $b$ to $y$ exists and is unidirectional. - additionally a set of nodes having bidirectional vertices to at least two of the nodes $a \ldots z$ exists. These nodes are connected in a second unidirectional chain.

(the red route is the requested result, the squares are the first chain (unidirectional) and the circles are the second chain (unidirectional). $1$ is the start node and $5$ is the destination node.)

Is it possible to find the shortest path from $a$ to $z$ that includes nodes $b$ to $y$ and the additional nodes once without probing all possibilities?

I think the problem is roughly the same as the minimal traveling salesman problem since adding a vertex from $z$ to $a$ will result in the min-TSP - but this problem is slightly easier since a path from $a$ to $z$ is already known.

If I understood well the question, things are clearer if you draw the graph in this way:

And you can use the following polynomial time greedy algorithm to find an Hamiltonian path from the two endpoint nodes of the bottom line.

Suppose that the nodes on the bottom line are $B_1,B_2,...,B_n$ and the nodes on the upper line are $U_1,U_2,U_m$. You need to find an Hamiltonian path from $B_1 \to B_n$.

If you are on node $B_i$, move to the first node $U_j$ linked to it (first means leftmost in the upper chain), then scan $U_{j+1}, U_{j+2},...$ until you find a link from $U_{j+k}$ to $B_{i+1}$ and such that if $j+k<m$ there is another link from $B_{i+l}, l>i$ to $U_{j+k+1}$ (that will allow you to complete the upper line). If such $U_{j+k}$ exists, add edges $B_{i}\to U_{j} \to ... \to U_{j+k} \to B_{i+1}$ to the final path, delete those nodes from the set and repeat the procedure from $B_{i+1}$.
If such $U_{j}$ doesn't exist, add the edge $B_{i} \to B_{i+1}$ and repeat the procedure from $B_{i+1}$.


Enhancing this turing machine's runtime As in, I have to design a determenistic (one-taped) turing machine that accepts that language (All strings made up of 0 and 1, where the j-th character from the end is a 0, and $j$ is a constant that we know what it is before running the machine) in less steps than the trivial steps.

In the trivial solution, I would first check if the starting point is a blank, if so the machine denies. If not, go to the last bit (first blank) then move $j$ steps to the left and check if it is $0$.
All of that takes $1 + n + j$ steps, but my professor says there is a better runtime that I should come up with.

Any hints would help!

There is a Turing machine operating in time $n + 1$ or so, but with lots of states. The machine simulates a DFA for your language. It has $O(2^k)$ states which "remember" the last $k$ characters.


Search for minimum in an array of $k$ monotonic subarrays Let $A$ be an array of totally ordered elements. A subarray $A[i..j]$ is decreasing if $A[k]\geq A[k+1]$ for all $i \leq k < j$. It is increasing if $A[k]\leq A[k+1]$ for all $i \leq k < j$. It is monotonic if it's either decreasing or increasing.

We call an array is $k$ monotonic if the array can be partitioned into $k$ monotonic subarrays.

  Given $A$ a $k$ monotonic array of length $n$, and the value $k$, find the
  minimum value in the array.

How many comparisons do we need?

If we let $m$ be the maximum number of times a value occurs in $A$, here are some known cases:

$k=1$, then the array is sorted, the minimum is at either end, a $O(1)$ solution.

$k=2$, then we could solve it in $O(m+ \log \frac{n}{m})$, by take the min of two cases.

First decrease, then increase, use a $O(m+ \log \frac{n}{m})$ solution. Basically do ternary search unless one find a large segment of equal values, which turns into linear search.
First increase, then decrease, just check the boundary values.

$k=n$, then a $O(n)$ time linear search is the best possible.

I believe a $\Omega(m+k \log \frac{n}{k})$ lower bound exists, since even if we are given position for $k/2$ partitions of first decreasing then increasing subarrays, $A_1,\ldots,A_{k/2}$, we still need to spend $O(m_i+\log \frac{|A_i|}{m_i})$ time to search for the minima in each one of them, where $m_i$ is the max number of times a value can appear in $A_i$.

Here are algorithms and matching lower bounds, which fully resolve the situation:

For $k=1$, you can find the minimum in $O(1)$ time: just examine the two endpoints of the array, $A[0]$ and $A[n-1]$.
For $k=2$, you can find the minimum in $O(m + \lg (n/m))$ time, as was mentioned in the question.  I prove below that you can't do any faster than this (up to a constant factor).
For $k\ge 3$, I prove below that finding the minimum takes $\Theta(n)$ time, regardless of $m$ (it takes $\Omega(n)$ time even if you are guaranteed that $m=0$).  The trivial algorithm takes $O(n)$ time, so if $k\ge 3$ it is not possible to do better (up to a constant factor) than the trivial algorithm.

Moreover, randomization doesn't help.

Lower bounds.  For $k=2$, consider an array $A$ that is positive and strictly decreasing on $A[0\ldots r-1]$, then $A[r]=A[r+1]=\cdots=A[r+m-1]=0$, then is positive and strictly increasing on $A[r+m\ldots n-1]$.  Now pick an index $i$ satisfying $r \le i \le r+m-1$, and replace $A[i]$ with $-1$.  Notice that this is an array with $k=2$ monotonic sub-arrays (decreasing-then-increasing).  However, even if you were given the value of $r$, you would still have to examine every element of $A[r\ldots r+m-1]$ to find the minimum, so any algorithm has to take $\Omega(m)$ time.  Moreover, it's easy to show that any algorithm will need $\Omega(\lg n)$ time, so we get a $\Omega(\max(m,\lg n))$ lower bound on the running time.  This implies a $\Omega(m + \lg(n/m))$ lower bound as well.

For $k=3$, consider an array that is positive and strictly increasing on $A[0\ldots n-1]$, then pick an index $i$ and modify $A$ by replacing $A[i]$ with $-1$.  This is an array with $k=3$ monotonic sub-arrays, and to find the minimum, you have to scan every element of $A$, so the running time is $\Omega(n)$.  Notice that in this example, $m=0$, so knowing (an upper bound on) the value of $m$ does not help you speed things up.

If you want a heuristic algorithm for $k=2$ (with no guarantees about worst-case running time), the following randomized algorithm might work well in practice, even though its asymptotic worst-case running time is not any better.

We'll assume the array is decreasing-then-increasing (until you find any evidence to the contrary; if you find evidence that it is decreasing-then-increasing, you can just look at the two endpoints and terminate immediately).  We're going to search for the changeover point (which will be the minimum we're looking for).  To do that, we'll use ternary search with random selection of the two midpoints.

In particular, we'll use random probing to find two indices $i<j$ such that $A[i],A[j]$ are different from each other and from $A[0],A[n-1]$.  Once we have these indices, we can do a case analysis on the relative order of $A[0],A[i],A[j],A[n-1]$ and recurse on either $A[i\ldots n-1]$ or $A[0\ldots j]$.  This is a smaller sub-array of expected size $2n/3$.

How long does it take to find two indices $i,j$ that are acceptable?  We can start by randomly choosing values for $i$ until $A[i]$ is different from $A[0]$ and $A[n-1]$; then we randomly choose values for $j$ until $A[j]$ is different from $A[0],A[i],A[n-1]$.  If there are $m$ repeats, then $n-m$ of the entries are unique; thus, each random choice of $i$ (or $j$) has at least a $(n-m)/n$ probability of finding an acceptable value.  Consequently, the expected number of random probes done is $O(n/(n-m))$.

Also, we recurse on an array whose expected size is a constant fraction smaller, so we expect to do only $\lg n$ recursions.

Of course, the total running time could still be bad (e.g., with the example I gave above), but it might often be OK if you have some reason to think the absolute worst-case inputs are unlikely.


Decidability of determining whether a context-free grammar generates all strings in 1* How could I prove that the following language is decidable?

$\{\langle G\rangle \mid G\ \text{is a CFG over}\ \{0,1\}\ \text{and}\ 1^* \subseteq L(G)\}$

P.S.
It's the problem 4.15 of the third edition of the "Introduction to the Theory of Computation" by Michael Sipser.

You can find the solutions to the exercises of that book here. For completeness of the answer, I rewrite the solution (with some more details) here.

Let $p$ be an upper bound of the pumping length of $G$, you only need to check whether $1^0, 1^1,\ldots,1^{p+p!} \in G$. If not, we can certainly reject $\langle G\rangle$. Otherwise, applying pumping lemma on $1^k$ ($p\le k\le p + p!$), we can conclude that there exist substrings $u,v,w,x,y$ such that

$1^k=uvwxy$, which means $u,v,w,x,y$ contain only 1s,
$|vwx|\le \text{pumping length} \le p$,
$|vx|\ge1$ and
$uv^nwx^ny\in G$, i.e. $1^{|uwy|+n|vx|}=1^{k+(n-1)|vx|}\in G$, for all $n\ge 0$, which means $1^{k+n(p!)}\in G$ for all $n\ge0$.

Note $\{1^{k+n(p!)}\mid n\ge0, p\le k\le p + p!\}$ covers all $1^m$ for large $m$, so $1^0, 1^1,\ldots,1^{p+p!} \in G$ indeed implies $1^*\subseteq G$.


Register images containing objects with varying distance to the cameras I'm learning about using image registration to align two images, e.g., two photographs of the same scene taken from a slightly different location. What factors influence how well we can align the images? Does the distance to the objects in the image influence its effectiveness of alignment, and if so how? What about the amount of variation in the distances to the objects in the images: how does that influence the effectiveness of the alignment?

Background: I came across the notion of "global image registration" when reading the paper

  "Mutual information based registration of multimodal stereo videos for
  person tracking", by Stephen J Krotosky and Mohan M Trivedi, in Computer Vision and Image Understanding 2007.

I believe "global image registration" means to use one transformation function for the registration. The authors state that global image registration is accurate when all objects of interest are in the same plane. I am trying to figure out exactly what they mean.

At first, I assumed that the authors mean objects across different
    frames (then needed to have a similar distance to the camera across
    the frames), where the previously calculated registration is
    supposed to work for each frame.

Then I thought that they maybe mean the registration of a single
    image pair and that objects of interest must be in similar distance
    to the camera.

To check this, I registered two pairs of image. The first pair has a lot of depth, the second pair does not, i.e., the first pair contains objects of varying distances to the cameras. It can be seen that the latter is much better registered than the former. This suggests that my second statement is correct: an image registration based on one transformation function is not able to register an image well if there is a lot of variation in the distances to the objects in the image. Is this correct?

First image pair:

First image pair registered:

Second image pair:

Second image pair registered:

Yes, if there is a lot of variability in the distance to the objects in the scene, then global registration will work poorly.

Let me back and give some background on how global image registration works.  It tries to align the two images.  In its simplest form, the only transformation that is allowed is translation: it tries to find a way to shift all the points in the left image in a constant direction, to make it match the right image as much as possible.  In other words, it looks for a translation $T$ such that $T(I_1)$ matches $I_2$ as much as possible, where $I_1,I_2$ are the two images.

With this background, you can see why global image registration won't work well for scenes with objects at multiple distances, when you have two pictures taken from a different point.  Imagine taking one picture, then moving left one mile, then taking another picture.  Objects that are far away won't shift their location in the image very much, but images that are close will shift to the right a lot in the second image.  Global image registration tries to find a constant translation that makes everything match up in the two images, but there is no single translation that will work well.  To make the distant objects match up, you'd need a small translation; to make the nearby objects match up, you'd need a large translation; and there is no way to reconcile these differences.

This is the major problem you're seeing.  There are other problems as well, due to the fact that the image is only a 2D representation of a 3D scene.  For instance, if you take two photographs from two different positions, then not only will the location of the objects in the images shift, but also you'll be viewing them from two different angles.  Global image registration can't un-do that, because it can't see around corners.  Look at the two images of the statue.  Imagine that the statue had a little bit of bird dropping on the left side of the person's nose (our left; the person's right).  Then the bird dropping might be visible from the second photograph, which is taken straight-on, but might not be visible from the first photograph, which is taken from an angle.  Alignment can't fix this, as it can't magically make up for things that aren't visible in the photograph.

This answer talks about global image registration based purely on translation.  In general global image registration typically allows a broader set of transformations: a typical example might be something that allows translation, scaling (zoom in or out), and rotation; or translation, scaling, and skew; or an arbitrary linear/affine transformation; or an arbitrary homography / projective transformation.  Unfortunately, none of these really help with the problems outlined above.  In general, no rigid transformation will eliminate the problems I've sketched in this answer, so this answer is pretty general.  In principle, non-rigid transformations might be more effective at handling variation in depth; I don't have any experience with that form of image registration.


Prove NP-completeness of deciding satisfiability of monotone boolean formula I am trying to solve this problem and I am really struggling.

A monotone boolean formula is a formula in propositional logic where all the literals are positive. For example,

$\qquad (x_1 \lor x_2) \land (x_1 \lor x_3) \land (x_3 \lor x_4 \lor x_5)$

is a monotone boolean function. On the other hand, something like

$\qquad (x_1 \lor x_2 \lor x_3) \land (\neg x_1 \lor x_3) \land (\neg x_1 \lor x_5)$

is not a monotone boolean function.

How can I prove NP-completeness for this problem:

  Determine whether a monotone boolean function is satisfiable if $k$ variables or fewer are set to $1$?

Clearly, all the variables could just be set to be positive, and that's trivial, so that is why there is the restraint of $k$ positively set variables.

I have tried a reduction from SAT to monotone boolean formula. One thing I have tried is to substitute a dummy variable in for every negative literal. For example, I tried replacing $\neg x_1$ with $z_1$, and then I tried forcing $x_1$ and $z_1$ to be different values. I haven't quite been able to get this to work though.

The "parent" of the problem you're looking at is sometimes called Weighted Satisfiability (WSAT, particularly in parameterized complexity) or Min-Ones (though this is normally an optimization version, but near enough). These problems have the "at most $k$ variables set to true" restriction as their defining feature.

The restriction to monotone formulae is actually surprisingly easy to show hardness for, you just need to thing outside satisfiability problems for a moment. Instead of trying to modify a SAT instance, we instead start with Dominating Set (DS).

See if you can get it from there. More is in the spoilers, broken into bits, but avoid them if you can. I won't show membership in NP, you should have no problem with that.

   Given an instance $(G, k)$ of DS (i.e. we want a dominating set of size at most $k$ for $G$), we can construct an instance $(\phi,k)$ of WSAT where the formula $\phi$ is a monotone CNF formula:

The basic construction:

   For each $v\in V(G)$ we have a variable $v' \in \text{var}(\phi)$, for each $v \in V(G)$ we have a clause $c_{v} = \bigvee_{u\in N(v)} u'$.

A sketch of the proof:

  Each vertex either has to be in the dominating set, or have a neighbour that is, so if we can find $k$ vertices that form a dominating set, the corresponding $k$ variables can be set to true in $\phi$, and each clause must contain at least one of them. Similarly if there is a weight $k$ satisfying assignment, the true variables correspond to the vertices we place in the dominating set - every clause $c_{v}$ must have at least one, so each $v$ is dominated (by itself or otherwise).


How do you go about designing a vector processor architecture for the sum of matrix products? The following equation is a matrix expression where $B_i$ and $C_i^T$ are $n\times n$ matrices and k is a positive integer:

$$P = \sum_{i=1}^k  B_i  C_i^T $$

So $P = B_1 C_1^T + B_2 C_2^T + \cdots +B_k C_k^T   $

If $B_i $ and $C_i$ are $n\times n$ matrices themselves, we have a total of 2 $\times$ k matrices that some how need to be stored in this vector architecture.

So this means P will end up being an $n\times n$ matrix after all the computation has completed.

What is the simplest possible vector processor architecture that is required to perform the matrix computation above?

Is there any literature or articles out there that discuss how this can be done?

Would appreciate all / any advise

From talking to the OP, algorithms that handle parallel matrix multiplication are apparently acceptable answers. Matrix multiplication and parallel algorithms for it are a highly studied problem in CS partly because of its widespread application e.g. in scientific computing. There are other ways to parallelize the problem given in the question, e.g. an obvious "map-reduce" that maps the separate matrices to separate processors and the reduce step does the addition.

There is some discussion on Wikipedia, Matrix multiplication, "Communication-avoiding and distributed algorithms."
Here is a somewhat recent survey of performance of standard algorithms.
Performance Analysis and Evaluation of Parallel Matrix Multiplication Algorithms
Ziad A.A. Alqadi, Musbah Aqel, and Ibrahiem M. M. El Emary.
The standard (scientific computing) matrix libraries BLAS and LAPACK have standard parallel matrix multiplication algorithms built in.
The problem as stated is also readily computed by a GPU e.g. via standard CUDA programming. This subject is increasingly studied in undergraduate classes e.g. at CalTech.

Note also the new "scicomp" stackexchange for questions on scientific computing.


Term for programming languages that read like sentences? Is there a term for programming languages that read like written sentences? I'm thinking of languages like Python, where you can almost read the code aloud as a sentence, as opposed to C++ which is really arcane.

For example, in Python if 'pizza' not in animals is very clear when read aloud.

Seems like maybe there's a formal term for this?

I know of no standard term for that aspect of PL. Maybe you can use "human-readable syntax" or "human-friendly syntax".

In PL theory, we (unapologetically) tend to disregard syntactic issues (e.g., look at LISP), and focus more on language features / semantics / types and more math-y stuff.

I mean: if you asked me what are the main differences between C++ and Python, I would probably spend a long time before mentioning some syntactic difference.

For practical applications, of course, having a more human-centric design that the one offered by pure theory is important. A clean and easy syntax is certainly quite convenient to read and write.

Note that, if a PL pushes this principle to extremes, and employs a syntax which is very close to natural language, it could possibly harm productivity. This is because, natural languages can be quite ambiguous, and when programming you really need to be rigorous. Trying to oversimplify a PL by completely removing the math-y aspects of PL is probably not a good idea.

COBOL is arguably more human-readable than Python, but it's hardly better. x = y+z is simpler than ADD Y to Z GIVING X.


Generating all the increasing subsequences Given an array of integers, how can we generate all the increasing subsequnces  of length of 4  ?
Example: given this list
l = [1, 2, 4, 5, 3, 6]

The answer should be :
[1, 2, 3, 6]
[1, 2, 4, 5]
[1, 2, 4, 6]
[1, 2, 5, 6]
[1, 4, 5, 6]
[2, 4, 5, 6]

I generated this algorithm using python :
def verif(x,temp):
    work=[]
    for k in temp:
        if len(k)<4 :
            if k[-1] < x :
                work.append(k+[x])
    return work+[[x]]

temp=[[1]]
for i in range(1,len(l)):
    print(i)
    zeta=verif(l[i],temp)
    for i in zeta:
        if len(i)==4 :
            print(i)
    temp+=zeta
    zeta=[]

I want to improve my approach , which is very slow for bigger lists unfortunately , is there another algortihm which works faster ?

Here is an algorithm to generate all increasing sequences of length $4$ of the numbers $1,\ldots,n$:
for d in {4,...,n}:
  for c in {3,...,d-1}:
    for b in {2,...,c-1}:
      for a in {1,...,b-1}:
        output a,b,c,d


Complexity of divide and conquer algorithm with a quadratic merge function Consider the following pseudocode:

int divide(int l , int r){
    if r - l > 3 then
        mid = (l + r) / 2
        divide(l , mid)
        divide(mid + 1, r)
        return merge(l, mid, r)
    else
        return bruteforce_solution(l, r)
}

If merge function takes $O(n^2)$ time, then total complexity can be found as a solution of the reccurence: $T(n)=2T(n/2)+n^2$
The solution of a the reccurence is $T(n)=2n^2-n$
So $O(log(n))$ calls of an $O(n^2)$ function takes $O(n^2)$ time?

Let $S(n) = T(n)/n^2$. Then
$$
S(n) = \frac{T(n)}{n^2} = \frac{2T(n/2)}{n^2} + 1 = \frac{2(n/2)^2S(n/2)}{n^2} + 1 = \frac{S(n/2)}{2} + 1.
$$
Assuming a base case of $S(1) = 2$ and that $n$ is a power of $2$, one can prove by induction that $S(n) = 2$. Indeed, this holds for $n = 1$, and if it holds for $n/2$, then $$S(n) = S(n/2)/2 + 1 = 2/2 + 1 = 2.$$
We conclude that if $T(1) = 2$ and $n$ is a power of $2$ then $T(n) = 2n^2$.

What happened here? First we had one call to a routine that takes time $n^2$. Then we had two calls to a routine that takes time $(n/2)^2 = n^2/4$, taking a total time of $n^2/2$. Then we had four calls to a routine that takes time $(n/4)^2 = n^2/16$, taking a total time of $n^2/4$. And so on. The amount of work at each level decreases exponentially, and so the total amount of work stays $O(n^2)$ although there are $\log n$ different levels.

If we replaced $2T(n/2)$ by $aT(n/b)$, then the behavior of the recurrence would depend on the relation between $\log_b a$ and $2$. This is covered by the well-known master theorem.


Non context free language that is pumpable? For my homework assignment, I have to come up with a non-cfl that is pumpable. I came up with the following:
$$ C = \{a^n b^n c^n d^m \mid n \ge 1 \text{ and } m \ge 1 \} $$

I'm not sure whether this works. For the pumping lemma, let $p$ being the pumping length. If I generate a string with $p$ $a$'s, $b$'s, and $c$'s, and only one $d$, my only choice for $vxy$ would be $d$. Pumping this down to $v^0xy^0$ gives $a^p b^p c^p$, thus escaping the language. However, if I let $m$ be greater than or equal to zero, if I choose a string with no $d$'s, then I am forced to put either $a$'s, $b$'s or $c$'s in my $vxy$ string.

As you say "thus escaping the language" which means your example language is not pumpable: for $m=1$ we cannot pump $d$ and stay in the language. Instead consider $D= C \cup \{a,b,c\}^*$. Now we can pump $d$ whenever it is present, and we can pump any string that does not contain $d$.


How to find all the edges shared by all diametral paths of a tree? A diametral path in a graph is a shortest path whose length is equal to the diameter of the graph. Now, given a tree with $n$ nodes, I would like to find the set of edges (possibly empty) which are present in all diametral paths. Is there an efficient algorithm to do that?

I know how to do it in $O(n^3)$ which is basically to iterate over all pairs of leaf nodes, check if their distance is equal to the diameter (this can be done using LCA) and if it is then traverse the (unique) path connecting them adding 1 to a counter associated to each edge along the way, and finally count how many edges have their counters equal to the number of diameters. This should work but it's quite expensive, and for sure there must be a more efficient approach.

An $O(n^2)$ algorithm is, for each edge, remove the edge and check the diameter of the tree (the forest now). If it did not change, then the edge is not in the set.

Finding the diameter of a tree can be done in linear time See here.

However, you can apply a greedy/dp trick for an $O(n)$ algorithm. First, root the tree at some vertex $r$. Hence, each vertex, except for $r$ gets a parent. You can then from the leaves up, find the distance from a vertex to the farthest leaf in its sub-tree. Actually, we will also keep the value of the longest path when the child having the current longest path is removed. After we compute all these values in a bottom-up manner, we go again top-down, computing for each vertex, the longest path from this vertex to a leaf not in its sub-tree. Now we can on $O(deg(v))$ compute for all edges incident to $v$ if there is a path of length equal to the maximum length and not using them.

The sum of the degrees is twice as large as the number of edges in The graph hence we get a linear total running time.


Could a Van Emde Boas tree be used for storing matrices? I'm aware that typical techniques to store matrices in sparse form are compressed formats or maps where the key is the pair of indices and value the value of the entry in a matrix.

I was wondering if vEB trees could be used to such purpose as well. At the end of the day the dynamic set to be stored would be the pairs $(i,j)$ in lexicographic order. If $MN$ is the size of the matrix a vEB tree would allow the access to a specific entry in time $O(log(log(MN))$ which isn't bad, though the space requirement doesn't change, but maybe with some improvements something interesting could come out.

Is there some research in this direction? I quickly looked up on google doesn't seem anything specific comes out.

Thank you

Yes you are right; but actually I think what you need is a hash table, which supports insert, delete and find in O(1) (although it requires some randomization).

Of course, you can replace a hash table by a VEB tree, when the elements are integers. However, if you want to optimize the space usage, you still need hashing when constructing the VEB tree. Luckily, there's some data structure called Y-fast trie that supports operations similar to VEB tree, but only needs linear space, and is deterministic.


Why Cook-Levin thorem's proof can mean SAT's NP-Hardness I'm studying about Cook-Levin theorem but there is a problem I faced. Cook-Levin theorem shows that any NPTM can be encoded as a boolean formula. About given language $A$, instance $w$, and NPTM $M$ that decides $A$, I understand that when a boolean formula $φ$ is true when $M$ accepts $w$ and false when $M$ rejects $w$, decision problem $w∈A?$ will be the same problem as $φ=true?$. But I am confused that can we actually certificate existence of reduction from any other NP problem to SAT, with Cook-Levin theorem. I can't make actual Karp reduction to SAT that doesn't picky about where the reduction comes from, so I can't tell that SAT is in NP-Hard. Please help me to understand why conversion to boolean formula can mean SAT's NP-Hardness...

Any language $L$ in NP is decided by some nondeterministic Turing machine $M$. By Cook–Levin, the problem "Does $M$ accept input $x$?" can be decided by constructing a Boolean formula $\varphi_{M,x}$ that is satisfiable if, and only if, $M$ accepts $x$. Hence $L$ reduces to SAT, so SAT is NP-hard.


Is the class of non-regular languages closed against Kleene star? How to prove that if a language A is not regular then A* isn't regular either?

I have tried the usual methods with no result.

Hint: Suppose $L$ is any language over the alphabet $\Sigma$. If $L$ is not regular then so is $L+\Sigma$, yet $(L+\Sigma)^* = \Sigma^*$ is regular.


Strictly speaking do the Hoare and Lomuto partitioning algorithms work on the same algorithm: quicksort? For Hoare's partitioning algorithm quicksort is implemented as such

 quickSort(array, first, last)
    if(last > first)
        pivot = partition(array, first, last);
        quickSort(array, first, pivot);
        quickSort(array, pivot+1, last);

but Lomuto is

 quickSort(array, first, last)
    if(last > first)
        pivot = partition(array, first, last);
        quickSort(array, first, pivot-1);
        quickSort(array, pivot+1, last);

Notice the first one doesn't have pivot-1. Is it correct to call these two the same implementations of the quicksort algorithm? I'm having trouble rapping my head around the difference, I thought quicksort worked on the premise that after one call to it the pivot is in it's final place (so do +1 and -1 for the rest of the array) but Hoare's method doesn't seem to work like this.

The term "Quicksort" stands for this abstract algorithmic idea:

Pick a value $x$.
Partition the input into $\{y\mid y \leq x\}$ and $\{y \mid y > x\}$.
Recurse on the partitions (if they are non-trivial) and append the results.

You may want to generalise to multiple pivots, or create a third partition for elements equal the pivot, but mostly that's it.

There are many, many implementations. All of them are called "Quicksort", but many modify the name.
See here for a discussion about the differences of these particular two variants.


Total number of calls during insertion into binary tree The problem:

Find a formula for the total number of calls occurring during the insertion of n elements into an initially empty set. Assume that the insertion process fills up the binary search tree level-by-level. Leave your answer in the form of a sum.

code for INSERT function:

procedure INSERT(x: elementtype; var A: SET);
begin
    if A = nil then begin
       A -> .element := x;
       A ->.leftchild := nil;
       A ->.rightchild := nil;
    end;
    else if x < A ->.element then
        INSERT(x, A->.leftchild);
    else if x > A ->.element then
        INSERT(x, A ->.rightchild);
    end;
end;

The main confusion for me here is with leaving my answer in the form of a sum. I'm not all that great at sums (haven't taken Calc 2 yet), so I don't really know how to set them up or extract information from them all that well. Any help here would be greatly appreciated.

For clarity: This is a review problem where the answer is:

Let $2^k \leq n \leq 2^{k+1}$. Then $k = \log n$ and the number of calls equals,

$$
\sum_{i = 0}^{k - 1} (i + 1)2^i + (k + 1)(n - 2^k + 1)
$$

I'd like to know the process behind getting this answer. Thank you.

The key observation here is that the input is assumed to be such that all insertions fill level 0 (the root level), then completely fill level 1, then completely fill level 2, and so on.

In filling level $i$ we will have constructed $2^i$ new nodes, each of which will require $i+1$ calls to INSERT, so the total cost to fill level $i$ will be $(i+1)2^i$. Thus, the cost to fill levels $0, 1,\dotsc,  k-1$ will be
$$
\sum_{i=0}^{k-1}(i+1)2^i
$$
Now let's say we're finishing by filling level $k$ partially or fully. We're then inserting elements $n=2^k,2^k+1,2^k+2, \dotsc, 2^{k+1}-1$. Each of those will cost $k+1$ calls to INSERT, so for $n$ elements we will have used $n-2^k+1$ insertions, each of cost $k+1$ for a total of $(k+1)(n-2^k+1)$ calls. That must be added to the cost of filling the upper rows, so you get a total cost of inserting $n$ elements level-by-level equal to
$$
\left(\sum_{i=0}^{k-1}(i+1)2^i\right) + (k+1)(n-2^k+1)
$$


What graph theory algorithm(s) would help solve this problem? I have a directed graph with the following properties:

Except for a few special progenitor nodes, every node has two parent nodes
Any node can have any whole number of child nodes
The graph is generated such that no node is a descendant of itself in the following way: I starting with a few progenitor nodes (which have no parents) then randomly select two nodes and create a "child" node with directed edges going from each parent to the child. I repeat that step an arbitrary number of times.

I'd like to find an algorithm to efficiently identify subgraphs with the following properties:

The subgraph consists of two "parent" nodes and some or all of their descendants
Except for the two "parent" nodes in the subgraph, each node has both parents also contained in the subgraph (that is, if the subgraph were separated from the rest of the graph, no node would be separated from its parents, except for the two "parent" nodes).

It's easy to find a 3-node example of this type of subgraph - just take any two nodes and one of their mutual children. However, I'd like to be able to efficiently identify larger examples of these subgraphs.

I'd really appreciate some help pointing me in the right direction. I thought that what I need might be related to finding "weakly connected components", but I haven't made much progress, and my inexperience with graph theory makes it hard to figure out what to search for. Thanks!

PS: I've provided an example depiction of one of these graphs

Given two progenitor vertices $u$ and $v$, the following "modified flood fill" builds a set $P$ of additional vertices to include:

While a vertex $x$ exists whose parents are both in the set $\{u, v\} \cup P$:

Add $x$ to $P$.

This will halt with $\{u, v\} \cup P$ being the largest possible set of vertices for the given pair of starting vertices.  You want the subgraph this vertex set induces: To get that, just include every original edge that links two vertices in the set.

To do this reasonably efficiently, you could maintain 3 vertex sets $V_0, V_1, V_2$, where $V_i$ contains every vertex with exactly $i$ parents in $\{u, v\} \cup P$. Whenever some vertex $x$ is added to $P$, all of its neighbours in $V_0$ or $V_1$ are promoted to the next higher set (e.g., if some neighbour $y$ was in $V_1$, it is moved to $V_2$).  These updates can be done in constant time per neighbour by using three doubly linked lists for $V_0, V_1, V_2$, as well as a length-$|V|$ array $A$ of pairs $(i, p)$: $A[u].i$ is the current set number (0, 1 or 2) for vertex $u$, and $A[u].p$ is a pointer to its linked list node.  The main loop just reads from $V_2$ until no unread vertices remain.  Each vertex and edge in the graph is processed only once, so the overall time for a single starting vertex pair is $O(|V|+|E|)$.

Thanks to D.W. for catching a problem in my first algorithm.


Rooted Tree Isomorphism Algorithm I have developed an algorithm to determine if two rooted trees are isomorphic, which is based on the following conjecture:

Let $S_{u}$ be the number of vertices in the rooted subtree of vertex $u$.
Namely, the size of the subtree of $u$. Now Let $L_{i}$ = {$S_{u}$ : $lvl(u)$ = $i$}.
Here, $lvl(v)$ denotes the level of $v$.
Also the height of a tree is the maximum level of any of its nodes.

Now the conjecture:

Let $H_{1}$ and $H_{2}$ be the heights of the rooted trees $T_{1}$ and $T_{2}$, respectively. $T_{1}$ and $T_{2}$ are isomorphic if and only if $H_{1} = H_{2}$
and for every integer $i \in [ \,1,H_{1}] \, $, the multiset $L_{i}$ of $T_{1}$ and that of $T_{2}$ are the same.

Apparently this conjecture is false because i implemented a C++ program (to solve a competitive programming task) that is based on it, but it failed system tests. Still, it may be an implementation fault, so i'd like to know if there are any counterexamples to this conjecture.

Nice conjecture on tree isomorphism.
However, here is a counterexample.

Exercise. Construct a counterexample using a binary tree.


Train Neural network with infinite amount of data Does a sufficiently complex neural network guarantee to find the optimal solution, given an infinite amount of data and the back propagation technique for training?

In other words, given an infinite amount of training data, can neural network get out of local minima and approaches optimal state?

The question is purely theoretical.

Update:
It is obvious that a proper neural net with optimal set of weights (in some occasions num of neurons should go to infinity though) can approximate any well-defined function. However, in practice we do not have that optimal set of weights. Those weights are approximated by a training method of choice. The most commonly used method is back-propagation. Now the question was when the number of training samples grows, does the neural net converge to the Bayes rule?  In other words, is it a universally consistent classifier? the answer seems to be no. When it gets stuck in local minima no matter how much you increase the training set, it will never get out of it (when using BP as a training method).

you may wanna look at this paper: , (Farago,93)"strong universal consistency of neural network classifiers"

Update2: Perhaps, my update was not clear since I keep getting wikipedia pages as answer: Hope this one finally clarifies:

As I said in my original question, stochastic gradient descent (or perhaps other more complex choices) with back-propagation is going to be used to train the network. This means the weights are not optimal (optimality in the sense that the network may not obtain the Bayes err rate). We also have infinite amount of data which translates to learning in the limit or online learning framework. But to keep it simple, instead of having infinite amount of data, we may assume we have finite but arbitrary large set of data.

The question is, whether the performance of a neural network in theory can now converge to Bayes rate? using any known regularization method such as dropout (which somehow is equivalent to bagging), varying the network structure during training (adding or removing layers, increasing the number of neurons etc), early-stopping and any meta algorithm to sample from this large data-set, or anything else you can think of, are allowed.

PS: Many learning methods are universally consistent meaning that as the number of training samples grows, they guarantee to converge to something good (usually Bayes rate or $\epsilon$ neighborhood of it). I am surprised if we don't have any interesting theorem in that respect for Neural Networks.

You are asking about an "infinite" set of data. The trouble with this question is that backpropagation (BP) is only applicable to a finite set of data (or a finite sample of an infinite population), which is iterated over repeatedly many times in order to converge to a minimum on the error curve. BP is simply not defined for an infinite set of data (outside of batch sampling), because repeated iteration over an infinite set of data is a undefined.

The answer to your question for a finite sample of data depends on the weights used to initialize the BP and how you are defining "optimal."

In the first regard, since the BP algorithm blindly follows the error curve gradient, it is vulnerable to get stuck in local minima, and by definition of the gradient there is no way out unless you reinitialize the weights.
In the second regard, optimality may be defined many ways. For example, it may simply stipulate producing an output error less than some $\varepsilon$ for all training data presented. Or your definition may reward generality of a model by placing less constraint on the error and instead use a threshold on some economic formula based on the likelihood of a data point together with the output error that it produces. Or you might invent some other definition.

Allowing for an infinite number of initial guesses and taking the first definition of "optimal" provided above, then it seems clear to me that Siegelmann and Sontag's theorem of universal approximation guarantees a "yes" answer to the finite-data question. But as D.W. remarked, this isn't very useful in practice.

For a trivial but illuminating example, a neural net may "universally approximate" a completely random stream of data for some finite set of training points, and then proceed to fail any and all optimality definitions for data points outside that set. Real world data can contain a sufficient degree of randomness to render the possibility of satisfying an optimality constraint based on non-training data pretty much indeterminate.


Proving that the average case complexity of binary search is O(log n) I know that the both the average and worst case complexity of binary search is O(log n) and I know how to prove the worst case complexity is O(log n) using recurrence relations.
But how would I go about proving that the average case complexity of binary search is O(log n)?

I think most text book will provide you a good proof.

For me, I can show the average case complexity as follows.

Assuming a uniform distribution of the position of the value that one wants to find in an array of size $n$.

For the case of 1 read, the position should be in the middle so there is a probability of $\frac{1}{n}$ for this case
For the case of 2 reads, one will read the middle position and then 1 of the 2 other middle positions from the 2 sub-arrays. This probability is $\frac{2}{n}$
For the case of 3 reads, there are $2*2$ positions which result in this cost as you go into the 4 sub-arrays of the first 2 sub-arrays.  The probability for this cost is $\frac{2^2}{n}$

...
For the case of $x$ reads, the probability for this case is $\frac{2^{x-1}}{n}$

For the average case, the number of reads will be

$\sum\limits_{i=1}^{\log(n)} \frac{i2^{i-1}}{n} = \frac{1}{n} \sum\limits_{i=1}^{\log(n)} i2^{i-1}$

Now you can do integration on an approximation formula which will give you $O(n\log(n))$.
Note that $\int\limits_{1}^{\log(n)} x 2^x dx$ can be calculated and bounded into $\log(n)*2^{\log(n)} = n\log(n)$
This is a very good way to do that applies to many cases.

Another way to see it can also be $i2^{i-1} < \log(n) * 2^{i-1}$

Then the formula above is bounded by
$\frac{\log(n)}{n} \sum\limits_{i=1}^{\log(n)} 2^{i-1}$

The summation part is actually $\frac{1 - 2^{\log(n)}}{1 - 2} = 2^{\log(n)} - 1 = n - 1$
which is definitely less than $n$, multiplying this with $\frac{\log(n)}{n}$ gives you what you want $\log(n)$

So you will get the bound as you want $O(\log(n))$


Machine has 64 bit architecture and two word long instruction A machine has a 64-bit architecture, with 2-word long instructions. It has 128 registers, each of which is 32 bits long. It needs to support 49 instructions, which have an immediate operand in addition to two register operands. Assuming that the immediate operand is a signed integer, the maximum value of the immediate operand is that can be stored is?

edit: would 1 word long instruction for this case be of 64 bit and 2 word long instruction be of 128 bits?
Also do we have to add an extra bit while calculating the total bits required for 49 instructions?

A "64 bit architecture" with 32 bit registers is a bit unusual.

Taking the numbers at face value, a 2-word instruction is 128 bit long, you need 6 bit to encode the instruction, 2x7 bits to specify two registers, leaving 108 bits for an "immediate" operand. The maximum value in the "immediate" operand is $2^{107}-1$.

That's answering the question that you asked. What your instructor actually asked, and what he intended to ask, and what he thinks he asked, and what answer he wants to hear, nobody can know that.


Logic Circuits - Binary divisible by 16 I have a question

  Given a 16-bit register A holding a number in 2’s complement form, use a
   single gate (e.g., AND, OR,
  XOR, NAND, NOR, NOT) with an arbitrary number of inputs to implement a
  circuit that produces an
  output 1 if the number is divisible by 16, and an output 0 otherwise. The
 bits are labelled A15, A14, ..., A0.

I'm confused at how this answer is expected because the question is only 2 marks my answer was that it would be a single XOR gate with inputs a0-a15 - would this be correct and why?

A decimal number is divisible by 100 if it ends with two zeroes. The same thing happens in your case, and leads to a solution using a single NOR gate.


Is there a binary tree structure with fast access to recently accessed elements and worst $O \left( \log n \right )$ complexity? The idea of splay trees is very nice as they move frequently accessed elements to the top, which can gain a considerable speed up in many applications. The drawback is that in the worst case an operation can have $O(n)$ complexity.
(Although amortized bounds are $O(n\log n)$ if we perform at least $n$ operations.)

Is there a self-adjusting search tree structure that has both? Favoring recently accessed elements and with worst $O(\log n)$ complexity for a single operation?

The amortized cost of entering an element to splay tree is $O(\log n)$ so in the worst case $n$ operations would do $O(n\log n)$ steps. There is a conjecture about splay tree that says that it is as optimal as a binary search tree up to constant factor called Dynamic optimality conjecture.

Tango trees are online, self adjacent trees that achive $O(\log \log n)$ competitive ratio compared to offline optimal binary search tree which is the best known.


What is the height of a tree with recursion formula: $T(n) = T(n - \sqrt{n})$ I know if the time complexity of an algorithm is given with the above formula, then the algorithm works in constant time but my question is that what will be the height of the recursion tree for this formula?

Clearly T(n) = T(0) for all n. Which is constant, not linear. Is that really the question you wanted to ask?

And I just see a mathematical relation. I can’t see any recursion or tree or algorithm here.


What does it mean when its said that most Turing Machines are not programmable? I was reading this article. In its third paragraph of the third section, named The Classical computational theory of mind, it said that Most Turing Machines are not programmable. I got the literal meaning out of the statement.
I have only done Automata Theory 101 and the way I know Turing Machine, not much is making sense. A Turing Machine has a set of rules for deciding whether to write or move (LEFT or RIGHT) given current state and symbol on current cell.
Doesn't this make Turing Machine programmable as rules are decided in advance? Correct me if I am wrong. What does the writer mean when he said, "Most Turing Machines are not programmable"?

I think the point being made is that, as you say, the transition rules of any Turing machine are fixed in advance, so every Turing machine computes a fixed function of its input. Since the machine computes a fixed function of its input ("Count the number of 1s", "Determine if the graph represented has a perfect matching", etc.), it can't really be called programmable.

However, for some Turing machines (e.g., universal Turing machines), we treat one part of the input as being a program that should be executed using the rest of the input as input. These machines would be described as programmable in the context of the article you link.

I hereby declare actors to be programmable human beings.


Polynomial generator required to detect single bit error in Cyclic Redundancy Check codes I was reading about CRC coding from two books:

Data Communication and Networking by Forouzan Page 294
Computer Network by Tanenbaum Page 188

They use following notations:

$d(x)$: dataword to be sent (as a polynomial)
$c(x)$: codeword sent (as a polynomial)
$e(x)$: error (as a polynomial)
$c(x)+e(x)$: codeword sent with error introduced (if any)
$g(x)$: generator polynomial to be used at CRC encoder (for creating c(x)) and decoder (for checking if error is introduced or not during transmission)

Forouzan then states following:

  A single-bit error is $e(x)=x^i$, where i is the position of the bit. If a single-bit error is caught, then $e(x)=x^i$ is not divisible by $g(x)$. (Note that when we say not divisible, we mean that there is a remainder.) If $g(x)$ has at least two terms and the coefficient of $x^0$ is not zero (the rightmost bit is 1), then $e(x)$ cannot be divided by $g(x)$ and all single bits errors can be caught.

He then gives example of generator:

$g(x)=x+1$ saying that it can catch all single bit error (with which I have some doubts)
$g(x)=x^3$ saying that all single-bit errors in positions 1 to 3 are caught rest are left uncaught (with which I dont have any confusion).

For example, consider the below example for generator $g(x)=x+1$:

Tanenbaum says:

  If $g(x)$ contains two or more terms, $e(x)$ will never divide into $g(x)$, so all
  single-bit errors will be detected.

My doubts:

Q1. Forouzan states additional requirement to Tanenbaum that "the coefficient of $x^0$ is not zero (the rightmost bit is 1)". Whats correct? and why? Will generator $g(x)=x^3+x^2$ (which satisfies Tanenbaum's statement) capture all single bit errors? Do we always need "$+1$" in $g(x)$ for capturing any single bit error?

Q2. I feel I dont understand the reason/logic behind statements made by both authors, thats why I am not able to decide on myself whether "$+1$" should be there in $g(x)$ or not. Whats the logic then behind both of statements (whichever is correct)? More precisely: why $e(x)$ with single bit error will not be dividable by $g(x)$ if

  $g(x)$ has at least two terms and the coefficient of $x^0$ is not zero

as Forouzan says or if

  $g(x)$ contains two or more terms

as Tanenbaum says (whichever is correct).

I must be missing something very very basic stuff here.

You just need to concentrate on the polynomial division here. First consider the case where we need to detect one - bit error . For this case

$ e(x) = x^k $

we can choose any polynomial with terms >=2 , since it will not divide the error polynomial completely .

Next let us see the case of odd number of errors. Notice how this is different from one bit error. This is a burst error. Consider the polynomial

$ g(x) = (x+1) $

If we multiply this polynomial with any other polynomial the number of terms we get as a result is always even. This result in general is true you can try this for assurance.

Consider any error polynomial with odd number of errors . This polynomial will have odd number of terms in the polynomial. example :

$e(X) = x^3 + x^2 + x $

Now

$\nexists p(x)   \quad  such\quad that \quad  p(x) * g(x) = e(x) $

In other words no polynomial could be fund which gives odd number of terms when multiplied by x+1 . This observation suggests x+1 should be a factor of our generator function in order to catch odd- number of errors. As 1 - bit error is an odd-bit error x+1 also detects one - bit errors. Both books are correct in their reasoning.


How come the branching factor of chess is 35? I was studying about minmax algorithms and it said the branching factor of a chess game is around average 35. Meaning a player can move about 35 legal moves per position.

I am not able to comprehend this.Like if I do the opening in chess I was able to count 20 possible legal moves.(1 or 2 possible moves for 8 pawns that gives us 16.
2 possible for 2 knights respectively giving a total of 20)

So how it was calculated?

Since the moves differ per turn it was calculated as the average. Yes you are right, there are exactly 20 moves in the first turn, but after advancing with knights, bishops, rooks and queen into the center of the board the number of legal moves is increasing and since it is average of the minimax tree also the situation after encrouning with several queens on the both sides is calculated (not very wise game, but still perfectly valid to have more than 100 available moves in one turn.

Please check for some more legal chess positions.


Two way deterministic pushdown automaton accepting word consisting of two equal words I have a homework where I have to construct two way deterministic pushdown automaton that accepts this language:

{ww | w ∈ {a, b}*}

Does anyone have any idea? Thanks a lot

Here are the two basic ideas.
(1) After checking that the input length is even, move to the middle position of the input.
The trick to find that position uses the stack in a similar way that we recognize the language $\{\;a^{2n}b^n \mid n \ge 0\;\}$.
(2) Then check that the two halves are equal.
Here the stack is used in a similar way that one recognizes the language $\{\; ww^R \mid w\in\{a,b\}^*\;\}$, except that the head does not move forward in both cases.


Is it possible to "unshift" onto a queue using this theoretical "queue automaton"? I have been playing Manufactoria, a game in which one has to build a production line that tests/modifies "robots". Each robot has a "tape" where each cell is colored either red, green, blue or yellow. The production line can test/modify a robot by popping colors off the start of its tape, by moving the robot to different lines depending on the color popped off, and by pushing more colors onto the end of its tape. The tape is effectively a queue.

One level ("Robostilts") asks you, the designer, to build a production line that modifies each robot's tape to put a "green" at the start, and a "yellow" at the end. It turns out this challenge is easily completed because all robots start with only red and blue colors on the tape, and no green or yellows.

However, I initially misinterpreted the challenge, thinking that the input tapes were completely arbitrary. This seemed challenging, and now I think it's impossible. However, I don't know how to show this precisely, but I thought someone here might be able to. I have formalized the problem below.

$A$ is the four-letter alphabet $\{ R, G, B, Y \}$.

An automaton is $(S,sInit,sTerm,d)$ where

$S$ is a set of states
$sInit \in S$ is the initial state
$sTerm \in S$ is the terminal state
$d$ is a transition function $: (S \times A) \rightarrow (S \times A\star)$. (Note: $A\star$ denotes lists of $A$ elements.)

The automaton steps through a series of configurations $(s, x) \in (S \times A\star)$.

For a given "input string" $i \in A\star$,
the initial configuration is $(sInit, i)$.

The function $step : (S \times A\star) \rightarrow (S \times A\star)$ is given by

$
step (s, [x] \mathbin{+\mkern-10mu+} xs) =\\
\qquad\mathbf{let}\quad(s', new) = d(s,x)\\
\qquad\mathbf{in}\quad(s', xs \mathbin{+\mkern-10mu+} new)
$

The task is to define such a machine which,
starting with configuration $(sInit, i)$ for an arbitrary $i$,
after a finite number of applications of the step function,
reaches configuration $(sTerm, [G] \mathbin{+\mkern-10mu+} i \mathbin{+\mkern-10mu+} [Y])$.

Is this possible? If yes, how? If no, why not?

Without any way of creating an unmistakeable marker on the tape, this is not possible. (As far as I recall (cannot check right now), the tape in Manufactoria is actually bounded, which would make a difference, but let us assume this is not the case.)

Let $i$ be any input string, and consider the computation of a given automaton on $i$, i.e. the sequence $(s_0,x_0),\dots,(s_n,x_n)$ with $s_0=sInit$, $x_0=i$, $s_n=sTerm$, and $(s_{j+1},x_{j+1}) = step((s_j,x_j))$. In iteration $j$, we read and remove the first letter $a_j$ of $x_{j-1}$ and append a word $u_j$; these first letters form a word $w=a_1\dots a_n$.

It is not hard to see that any input word which starts with $w$, i.e. $wv$ for some $v$, is indistinguishable from $i$ to our automaton: it reads the same letters as it would on $i$, and as a result goes through the same states and appends the same $u_j$, so that the resulting word at the end is $vu_1\dots u_n$. This will fail to have the required form for any $v$ not starting with $G$ (and many others as well).


Does having more bus in the computer increasing speed? Whát i mention here is for having 2x bus will increasing 2x memory access speed like 3x will have 3x memory access speed like that !

It is difficult to answer in full generality for any kind of bus but I think generally the answer is: no.

First speed is imprecise, there are two notions: latency and throughput. Increasing the width of a bus can increase throughput but it will not help latency. Second, in theory doubling the width indeed doubles the throughput, but there is much to consider than the bus itself. Indeed, the data comes from somewhere (source), is used somewhere else (destination) and will usually travel over several (internal) buses. Thus it is pointless to have a super fast external bus if your CPU and/or internal bus is slow for example. Also if the data comes, for example, from a hard drive then it cannot be read faster than some speed for mechanical reasons and increasing the bus width will not change that. The same applies to the destination: if your CPU cannot process the data fast enough, then having a large bus is also pointless.

Finally, I would like to point out that increasing the width of a bus comes with its own problems, like interference and routing.


How to prove closure property of regular languages using regular expressions? I know that we can prove closure of two regular languages under operations like union, intersection, concatenation etc. by constructing NFAs for them but how to do the same thing using regular expressions, specifically proving that reversal of a regular language is closed using regular expression?

You can prove it using this approach:

if $E$ is a regular expression then you can recursively define its reverse in this way:

if $E = \emptyset$ then $E^R = \emptyset$
if $E= (E_1)$ then $E^R = (E^R_1)$
if $E = a \in \Sigma$ then $E^R = a$
if $E = E_1 \cdot E_2$ then $E^R = E^R_2 \cdot E^R_1$
if $E = E_1 \cup E_2$ then $E^R = E^R_1 \cup E^R_2$
if $E = E_1^*$ then $E^R = E^{R\,*}_1$

You can prove that each "step" is correct and after a finite amount of transformations the procedure ends. At the end you get a regular expression (recursively built from $E$) that defines $E^R$.


3-SAT with 3 variable occurences 3-SAT with at most 3 occurences per variable is $\mathsf{NP}$-hard.

Now I'll try to solve it using these:

Theorem: SAT where all clauses have length 3 and variables occur 3 times, is satisfiable.
Double propagation. If there is a clause $(a\lor b)$ and no clause $(\overline a\lor\overline b)$: change all occurences of $\overline a$ by $b$ and $\overline b$ by $a$. Also, remove clause $(a\lor b)$. This will result in two occurences for $a$ and $b$.
If there is a pair of clauses $(a\lor b)\land(\overline a\lor\overline b)$, replace occurence (there will be only one) of $b$ to $\overline a$. Remove that pair of clauses. This will result in two occurences of $a$ and no occurences of $b$.

Using this technique we either must get an empty clause or all clauses will have length 3 and formula will be satisfiable. It is also possible that formula will become 2-SAT.

Can this even work?

Your second step isn't sound.

Take any unsatisfiable $3$-SAT formula (without restriction on the number of variable appearances) and perform the standard reduction to a formula where each variable occurs at most three times.  That is, for each variable $X$ that occurs $k>3$ times, replaces the occurrences respectively with $X_1, \dots, X_k$ and add the new clauses

$$(\overline{X_1}\lor X_2) \land(\overline{X_2}\lor X_3) \land \dots \land (\overline{X_{k-1}} \lor X_k) \land (\overline{X_k}\lor X_1)$$

to ensure that $X_1, \dots, X_k$ have the same value in any satisfying assignment.

Now, we have the clause $\overline{X_1}\lor X_2$ but not $X_1\lor\overline{X_2}$ so we can use your second step, taking $A=\overline{X_1}$ and $B=X_2$. So we must delete the first clause and replace any instance of $X_1$ with $X_2$ and any instance of $\overline{X_2}$ with $\overline{X_1}$.  This replaces the clauses above with

$$(\overline{X_1}\lor X_3) \land (\overline{X_3}\lor X_4) \land \dots \land (\overline{X_{k-1}} \lor X_k) \land (\overline{X_k}\lor X_2)\,,$$
i.e.,
$$(X_1\rightarrow X_3)\land (X_3\rightarrow X_4) \land \dots \land (X_{k-1}\rightarrow X_k)\land (X_k\rightarrow X_2)\,.$$

This no longer requires all the the $X_i$ variables to have the same value. There are formulas that will become satisfiable when you make this transformation.

But, further, we can now apply the transformation again to the clause $\overline{X_1}\lor X_3$, resulting in
$$(\overline{X_1}\lor X_4) \land (\overline{X_4}\lor X_5)\land\dots\land (\overline{X_{k-1}} \lor X_k) \land (\overline{X_k}\lor X_2)\,.$$
Note that the variable $X_3$ has completely disappeared and can take any value. Iterating, we see that all the clauses relating $X_1, \dots, X_k$ disappear!

What have we done? We've taken a formula that mentioned $X$ more than three times and replaced these occurrences with successive new variables $X_1, \dots, X_k$, plus the constraint that all these new variables must take the same value.  We then deleted all the constraints, so $X_1, \dots, X_k$ can take any value at all, independently of each other and, by the way, each of the variables $X_1, \dots, X_k$ now only occurs once.  So, if we started with an unsatisfiable formula in which every variable occurred more than three times, we end up with a formula where every variable occurs exactly once.  That formula is always satisfiable.


Container with findNthSmallest in O(1) Consider the following problem: we want to implement ADT SpecialContainer which stores integer numbers and is similar to a PriorityQueue. This container should support the following operations:

init(sc, n) - create a new, empty SpecialContainer sc. n is a positive integer number (will be used later) - $\Theta(1)$ total complexity

push(sc, x) - adds the integer number x to the SpecialContainer - $O(\log n)$ total complexity

findNthSmallest(sc) - returns the nth smallest element from sc, where n is the number given to the init function - $\Theta(1)$ total complexity

popNthSmallest(sc) - removes and returns the nth smallest element from sc - $O(\log n)$ total complexity

Which data structure or combination of data structures would you use as representation for the SpecialContainer and how?

Explain in short how would you implement each operation of the SpecialContainer and why the implementation fits the complexity requirement.

I was thinking about a combination of a heap and a hash map, but I don't think if it works. Can somebody help me, please?

As pointed out by orlp, it's impossible to do in $O(\log n)$ time. However, we can do this in $O(\log N)$ time, where $N$ is the total number of items.
You can do this with 2 Heaps:
The first heap is a max-heap with the smallest $n$ elements. Its root is the $n$-th smallest element.
The second one is the min-heap with the rest of the elements. Its root is the $n+1$-th smallest element.
When max-heap has less than $n$ elements, the operations are trivial. Otherwise:

findNthSmallest() - it's just the root of the max-heap. O(1) time
popNthSmallest():

Pop the root of the max-heap
x := Pop the root of the min-heap
Insert x into the max-heap

push(x):

Push x into the max-heap
y := Pop the root of the max-heap.
Push y into the min-heap.


What is the "spatial information" in convolutional neural network deep learning research papers always claim that deeper layers of CNN have good "semantic information" but poor "spatial information". What is the spatial information exactly. Is that some activations in deeper layers?

Spatial Information refers to information having location-based relation with other information.

For example,
00100
01100
00100
00100

This looks like the number "1".

If this was represented in a single line,
001100011100001100001100

It wouldn't be recognizable.

Earlier layers of CNN are convolutional layers, which take into account the image as a 2D (spatial) information. Whereas, the deeper layers flatten that (convoluted) information.


Finding the point with minimum x-ordinate, lying between two y-ordinates Given a set of points $P=p_1,p_2,..p_n$ in $R^2$ in where $p_i=(x_i,y_i)$,finding the point with smallest x-ordinate having y-ordinates between $y_1$ and $y_2$, where $y_1$ and $y_2$ are given as inputs. I can compare the point with other points which gives me an $O(n)$ time algorithm ? Can this be improved any further ?

Not unless you assume something more. Without further assumptions, if you don't check all $n$ values, the minimum can be some of the unchecked points.

If you know there is just one minimum in (sorted) range, a variant of binary search (the minimum is the point where $x_{k - 1} > x_k < x_{k + 1}$ or one of the endpoints; if $x_k > x_{k + 1}$ the minimum is to the right, and so on) gets it in time $O(\log n)$.


What's the definition of a (deterministic) formal language? Definitions

According to my UML teacher formal means strictly according to rules, officially and how it's supposed to be. He says a formal language = syntax + symbols + spelling. Another term he uses is deterministic. According to him it means "strictly predictable", which means its only interpretable in a single way. So one input can't map to two outputs.

Confusion

If I'm given any example of a language that humans invented, I can't tell nor elaborate whether it's a formal language or not. Some of these examples are natural languages (English, French, Dutch, etc.), UML, Math, notesheets, programming languages, markup languages, braille.

In my teachers powerpoint presentation, he explained a natural language is not formal because it's dependent on context (Unless I understand the definition of "deterministic" wrong, deterministic is the opposite of context dependency. By context dependency I mean, a sentence or a word can have two different meanings, e.g. You were right. But also Make a right turn at the light Thus a natural language is not deterministic).

But then a few slides later he said a formal language doesn't have to be deterministic, which makes me wonder why he would use context dependency as an argument to explain formal languages in the first place.

Question

What makes a language formal? Perhaps you can elaborate by using the examples given above. And what makes a language deterministic? Is it correct that deterministic is the opposite of context dependency?

N.B.
Wikipedia isn't making much sense to me, and I've read that the article about formal languages is quite a mess because people have different opinions on it.

Formal languages could (potentially) mean different things in different contexts. The Wikipedia page explains one sense, while your teacher might be referring to a different (and more informal) sense. You should probably not worry too much about the formal definition of formal language.

The point your teacher is probably trying to get across is that a human language has an undesirable feature: it doesn't always have an accurate denotation. For example, what do we mean by a "sad song"? This doesn't have an accurate denotation. Compare this to "a string of a's and b's", which does have an accurate denotation. This highlights the vagueness of human language. Another problem is polysemy: the same term can have several different meanings. For example, "formal language" can mean "a set of strings over an alphabet" (the Wikipedia meaning) or the more vague "a language in which each expression has a well-defined and unique meaning", which is closer to your teacher's.

In contrast, formal language defines everything in an unequivocal way. You'll see many examples of formal definitions in class, and hopefully the difference will become clear. But more importantly, you are not a philosopher, and so you shouldn't necessarily be able to explain the difference or to consciously identify which is which. Rather, you should understand that in some contexts we try to banish vagueness as far as we can, and present things in a "formal" and unequivocal way. In other contexts, say writing a newspaper article or a novel, we have different aims, but that kind of writing doesn't fit in a UML class.


Proof that a guard digit bound the error of subtraction I was reading What Every Computer Scientist Should Know About Floating-Point Arithmetic, which is extremely interesting. But I have some troubles understanding the proof of Theorem 9 (page 33).

First a pretty trivial question. When the formula $(15)$ say:
$$y - \bar{y} \lt (\beta - 1)(\beta^{-p} + \dots + \beta^{-p-k})$$
Shouldn't it be $\le$ instead of $\lt$, or did I miss something?

More importantly, I do not understand why it say that if $x-\bar{y} \lt 1$, then $\delta = 0$. How can there be no rounding error?

It is then said that:
$$x - y \ge 1.0 - 0.\overbrace{0 \dots 0}^k\overbrace{\rho \dots \rho}^k \; \textrm{with} \; \rho = \beta - 1$$

Why is that so? Can't the difference be arbitrarily small or even $0$? Why would there be as many $\rho$'s as there are $0$'s?

I'll post some elements of answer to my own question from what I understand. Anyone feel free to make a better, less sloppy answer.

First, there are several versions of this document online. They all have some typographic defects at some point. So when in doubt, better check those 3 versions first.

https://www.itu.dk/~sestoft/bachelor/IEEE754_article.pdf
https://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html
https://ece.uwaterloo.ca/~dwharder/NumericalAnalysis/02Numerics/Double/paper.pdf

Second, there's a lot of implicit stuff going on with this first actual proof. So let's clarify some of them.

Reachable bound of $y - \bar{y}$

I think that, no, the bound on $y - \bar{y}$ cannot be reached. Let's try to go for the worst case with $k = p+1$. Let's assume $p = 6$ and the radix $\beta = 10$.
\begin{align}
y           & = \overbrace{0.000000}^{k=7}\overbrace{999999}^{p=6} \\
\bar{y}     & = \overbrace{0.000000}^{p+1=7} \\
y - \bar{y} & = 0.000000999999 \\
            & = 9 \times (10^{-7}+\dots+10^{-12}) \\
            & = (\beta - 1)(\beta^{-p-1}+\dots+\beta^{-p-p}) \\
            & \lt (\beta - 1)(\beta^{-p-1}+\dots+\beta^{-p-p}+\beta^{-p-(p+1)}) \\
            & \lt (\beta - 1)(\beta^{-p-1}+\dots+\beta^{-p-p}+\beta^{-p-k})
\end{align}

I had to add an extra term to the sum (i.e. an extra digit) to get the same formula as the paper. Hence the $=$ got transformed to $\lt$.

This exact bound simplify the second case of the proof. Although a looser and simpler bound $y - \bar{y} \lt \beta^{-p}$ would be enough for the first case when $x - y \ge 1$.

No rouding error when $x - \bar{y} \lt 1$

The assertion that if $x - \bar{y} \lt 1$, then $\delta = 0$ seems true. The rounding error $\delta$ is the error we introduce by removing the guard digit to produce the final result. This is sometimes needed because $\bar{y}$ has $p+1$ digits and $x - \bar{y}$ might as well have $p+1$ digits.

For instance:
\begin{align}
x           & = 2.00000 \\
y           & = 0.0123456 \\
\bar{y}     & = 0.012345 \\
x - \bar{y} & = 1.987655
\end{align}
The result has $7$ digits therefore has to be rounded to $6$ digits.

But when $x - \bar{y} \lt 1$ then the result starts with the digit $0$. Meaning that at most only $p$ significant digits remain from the $p+1$ digits used to perform the subtraction. For example:
\begin{align}
x           & = 1.00000 \\
y           & = 0.0123456 \\
\bar{y}     & = 0.012345 \\
x - \bar{y} & = 0.987655
\end{align}
The result $x - \bar{y}$ already has 6 digits. So no rounding error need to be introduced.

However, it is worth noting that this doesn't change anything to the error introduced by truncating $y$ to $\bar{y}$.

Minimum value of $x - y$

When the paper say that the smallest value $x - y$ can take is:
$$1.0 - 0.\overbrace{0 \dots 0}^k\overbrace{\rho \dots \rho}^k$$
there's actually a typo that has been corrected in other documents. What was ment to be written is:
$$1.0 - 0.\overbrace{0 \dots 0}^k\overbrace{\rho \dots \rho}^p$$
which make more sens and is the general formula when $k$ is fixed. Maybe a better form could be:
\begin{align}
x - y & \ge 1.0 - 0.\overbrace{0 \dots 0}^k\overbrace{\rho \dots \rho}^p \\
      & \ge 0.\overbrace{\rho \dots \rho}^k\overbrace{0 \dots 0}^{p-1}1 \\
      & \gt 0.\overbrace{\rho \dots \rho}^k
\end{align}

Which lead naturally to the formula written in the paper.

Third case: $x - \bar{y} = 1$

And finally, another implicit point of this proof (not asked but worth writing down): why would having both $x - y \lt 1$ and $x - \bar{y} \ge 1$ imply that $x - \bar{y} = 1$?

I think the informal answer would be that since $x$ is a float with $p$ digits, then $x - 1$ is also a float with $p$ or $p - 1$ significant digits (if $x >= 2$ or $x < 2$ respectively). Meaning that truncating $y$ to $\bar{y}$ cannot make it less than $x - 1$ since $y > x - 1$ and $x - 1$ is a candidate value for $\bar{y}$ and is less than $y$.

In other words: $x - y \lt 1$ imply that $x - \bar{y} \le 1$. Therefore, having this and $x - \bar{y} \ge 1$ at the same time imply that $x - \bar{y} = 1$.


Maximum set packing and minimum set cover duality I read that the maximum set packing and the minimum set cover problems are dual of each other when formulated as linear programming problems. By the strong duality theorem, the optimal solution to the primal and dual LP problems should have the same value.

However, consider a universe $U = \{1, 2, 3, 4, 5\}$ and a collection of sets: $S = \{ \{1, 2, 3\}, \{3, 4, 5\}, \{1\}, \{2\}, \{3\}\}$. From what I understand, a minimum set cover would consist of the first 2 sets in set $S$, while the maximum set packing consists of the last 3 sets. These solutions aren't in accordance with the statement of the strong duality theorem.

Given that, I don't understand how the 2 problems can be dual of each other. What am I missing?

Thank you very much.

There is no contradiction. The strong duality theorem applies to the fractional linear programming formulations of the problems, where one is allowed to set fractional values for the variables, but these formulations are only relaxations of the two original problems. Strong duality does not apply to the integer linear programming formulations (as your example indeed shows).


What is the asymptotic bound for $1n + 2(n-1) + 3(n-2) + ... + (n-1)2 + n$? My best guess is that the series
$$ \sum_{i=1}^n i(n-(i-1)) $$
becomes
$$ 2 \Bigg[ n + 2(n-1) + ... + \frac{n}{2} \bigg(n-\bigg(\frac{n}{2}-1\bigg)\Bigg)\Bigg] $$
So the highest term is $n^2$ and there are $n$ terms. Does that mean its $O(n^3)$? That seems high. Intuitively, it seems like it should be closer to $O(n^2)$ but I can't find a way to bring it down mathematically.

We can lower bound the sum roughly by
$$
\sum_{i=1}^n i(n+1-i) \geq \sum_{i=n/3}^{2n/3} (n/3)^2 \geq (n/3)^3.
$$
This shows that it is $\Omega(n^3)$. Since each summand is at most $n^2$, the sum is also $O(n^3)$.

We can also compute the sum explicitly:
$$
\sum_{i=1}^n i(n+1-i) = (n+1) \sum_{i=1}^n i - \sum_{i=1}^n i^2 = (n+1) \frac{(n+1)n}{2} - \frac{n(n+1)(2n+1)}{6} = \frac{n(n+1)(n+2)}{6}.
$$
This expression equals the binomial coefficient $\binom{n+2}{3}$, and we can prove this bijectively. The binomial coefficient counts triples $(a,b,c)$ of elements satisfying $0 \leq a < b < c \leq n+1$. Notice that $1 \leq b \leq n$, and this corresponds to summation over $i$. Given $b$, we have $b$ choices for $a$ and $n+1-b$ choices for $c$.


Does Gale-Shapley work when the number of men and women are not equal? According to the Wikipedia page on the Stable Marriage Problem, the problem is presented in a way in which the number of men and women are both the same.

  Given n men and n women, where each person has ranked all members of the opposite sex in order of preference, marry the men and women together such that there are no two people of opposite sex who would both rather have each other than their current partners. When there are no such pairs of people, the set of marriages is deemed stable.

And then later on the Gale-Shapley algorithm is presented as a solution. However, based on my thinking, I believe the Gale-Shapley algorithm would work on inputs where the number of men and women do not have a 1:1 ratio. The reasoning for this is because by definition, if you look at the while loop's predicate, the men keep on proposing until they have either proposed to all of their preferences or are matched. This means that the algorithm will necessarily terminate as the men have a finite number of preferences. In the end, the men only end up matched to a woman if another man couldn't "out-bid" them for that woman. Thus it must be stable as if it were not we would have a contradiction as that man/woman that is unmatched should have proposed or been proposed to. (In general, it may be useful to let the side with a smaller number of people propose since the while loop would terminate sooner in expectation).

Overall, I'm just wondering whether the condition that the number of men and women are the same for the GS algorithm is superfluous.

First thing is algorithm will definitely terminate in the case even when number of men are not equal to women. Now at the end of Gale-Shapley algorithm for the case when number of men$(m)$ and women$(w)$ are equal.

  Each man can have the best partner that he can have in any stable matching.

If you only care about men then there are two cases:

If $m > w$ then algorithm will terminate but at the end there are going to be some men left out without matching
If $m < w$ then algorithm will terminate then at the end, each man can have the best partner that he can have in any stable matching.


Minimum-average-cost subtree that is not necessarily spanning I'm looking for an efficient algorithm for the following problem:

Input: a rooted tree (undirected) with a cost on each edge.  It could be considered directed away from the root (or towards the root).

Output: a subtree from the root that has the minimum average cost per edge.

There are some results for minimum average-cost spanning trees, but in this case the output is not necessarily spanning.

In the tree below, where A is the root of the tree:

The subgraph containing nodes A and B has average cost mean(6) = 6
We can improve on the average cost by including node C to get mean(6, 5) = 5.5.
The optimal subgraph includes nodes A, B, D and E, but not C, to get mean(6, 7, 1) = 4.67

A greedy algorithm would be a depth-first search that appends edges that lower the mean.  But such an algorithm would miss the optimal subgraph, because it wouldn't append the edge to node D with cost 7.

Tried to add this to the comments thread but stack overflow won't let me (new account)

@j_random_hacker I was thinking along similar lines to DP (a recursive algorithm that ran through the subtrees out to the leaves) but I hit a problem - I don't think the problem has an optimal substructure.

If you consider the graph in the image below, if x=1 then the 30-weight-edge is not part of the optimal solution (100,1,1,1) whereas if x=40 then it is (100,1,1,30). Inclusion of a specific edge in the optimal solution depends upon the weight of edges in completely separate parts of the graph.

I'd actually started writing some code before I realised. My recursive function assumed that given a subtree & the path from root to subtree you could make a decision but this counterexample broke it :(


How does this Turing machine accept $a^n b^n$? I'm reading this tutorial from the University of Illinois about Turing Machines, and I don't understand something.

They give a pseudocode algorithm for an machine that accepts strings from the language

$L = {0^n1^n}$

and a diagram of the machine. Both are pictured below:

What I don't understand however is how does this machine know that the number of $0$s are the same as the number of $1$s. I see no mechanism that can do that. All it seems the machine can do is recognize that there are no $0$s after $1$s.

The machine just changes the $O$ to $A$ and the $1$ to $B$, in such a
way that it changes a $1$ each time it has changes a $0$. Hence, if
there is the same number of $0$ and $1$, they all end up being changed
at some point. The TM no longer finding any $0$ will go to the bottom
part of the diagram and check that all $1$ have been changed to $B$,
i.e. that the sequence of $B$ is followed by a blank space. In that
case it accepts.

But is some $1$ is left after the $B$, then the TM will block in state
$q_3$ (no transition corresponding to $1$ on the tape) and
reject. Indeed, that means hat there were more $1$ than $0$, which
does not conform.

But if there were more $0$ than $1$, say $0^n1^m$ with $n>m$, the TM
will block in state $q_1$.  The reason is that, after erasing $m$
symbols $0$ and correspondingly $m$ symbols $1$, the TM will erase
another $0$, and try in state $q_1$ to find another $1$ to erase. But
it will find none, only a blank space.


Modified Max Product dynamic solution very inefficient The modified max product problem is as follows: given integer string $z_1\ldots z_n$, and an integer $k \leq n - 1$, what is the maximum product that can be formed by placing $k$ multiply signs in between the numbers, in the best possible configuration.

This has ${n-1 \choose k-1} = \frac{n!}{(n-k)!k!}$ configurations...so if $k$ is somewhere around $n/2$, then it should be a very large search space...so maybe some complexity makes sense.  However, I think I screwed up (aside from any indexing errors).

I have an $O(n^5)$ algorithm...

maxprod(z,n,k):
    for i = 1 to n:
        for j = 1 to n:
            T(i,j,0) = Z[i ... j] as an integer

    for s = 2 to n:
        for i = 1 to n - s:
            let j = i + s-1

            for a = max(0,k-n-s-1) to s-1: (all sizes of a)

                T(i,j,a) = max(...

                    for v = i to j: (splitting i and j)
                        for b = max(0,a-(j-v-1)) to min (a-1,v-1):
                            T(i,v,b)*T(v+1,j,a-1-b)
                  )
    Return T(1,n,k)

And I created it using a recursion,

$
T(i,j,a) = \mathop{max}\{T(i,v,b)\times T(v+1,j,a-1-b)\}
$

Where $v$ is varied from $i$ to $j$ and $b$ is varied from the minimum value it needs to be to the max it can be (for the multiplies needed in the substring such that exactly $k$ multiplies are used).

Is this even properly implemented?  Is there a faster solution? Where am I going wrong?  For some reason, I am struggling with dynamic programming...(only three or four dp problems solved so far though).

But then, I am thinking: I only do a max across two dimensions, inside the three for loops necessary to fill out a 3d array. This is essentially the fastest I can possibly do it in terms of $O(.)$ with my recursion.  Where am I screwing up, conceptually? This problem can't be as difficult as I made it...

Why do you split it in the middle? Multiplication is associative so you don't have to do that. Considering only the last multiply sign would be fine.
Here's a simpler recursion: $T(1,j,a)=\max\{T(1,v,a-1)\times T(v+1,j,0)\}$. I use the same symbols as yours so you can see the difference. The first dimension is useless so the table is actually an $n \times k$ array. Each function call takes $O(n)$, so the complexity is $O(n^2k)$.


Union of non-context free languages For two languages over the same alphabet, if neither of them is context-free, can their union still be context-free?
If not, does one of the languages need to be context-free for this to happen? Do both need to be context-free?

Yes, and this works for regularity and decidability as well! (not that this is very helpful in any sense)
For example, take any problem $A$ such that $A$ and its complement $\overline{A}$ are not CFLs (the halting problem as an extreme example)
Their union is $\Sigma^*$ which is obviously a CFL.

As a side note, and thanks for @D. Ben Knoble for pointing this out in the comments, that this is only an example. It does not necessarily hold for any two non-CFL languages, and on the contrary also a union of two CFL's may (not always!) end up not being a CFL.


The Number of Paths in a Directed Graph Suppose I have a directed graph $G = (V,E)$. Suppose that $v_1$ and $v_2$ are two nodes in the graph. Am I correct the number of simple paths (that is, it has no cycles) from $v_1$ to $v_2$ is $O(E)$? Is it true for the special case of directed acyclic graphs?

Bob

That's not true even for DAGs: consider the following, with all edges directed left-to-right:

  o   o   o ... o
 / \ / \ /       \
x   o   o   ...   y
 \ / \ / \       /
  o   o   o ... o

There are $2^{|E|/4}$ paths from $x$ to $y$. In a graph with cycles, it can be even worse: consider a clique.


Why, intuitively, does the Ackermann function require $\mu$-minimisation? I have read proofs that the function is not primitive recursive and I (think) I understand them. Most I've seen show that the set of functions dominated by the Ackermann are exactly the primitive recursive functions etc.
But, coming at it from the point of view of the 'ground requirements' which define the collection of recursive functions, I am having a hard time making the link between the (current) definition for the Ackermann function, and why it requires unbounded minimisation/search.
I am unfamiliar with a lot of theoretical computer science so I hope my question makes sense!

Roughly speaking, a function is primitive recursive if it can be computed by a program in which all loops are bounded ahead of time. Concretely, we can consider the LOOP programming language, which has the following instructions:

Set $x$ to zero.
Increment $x$.
Run a piece of code $x$ times.

We can use LOOP to compute one-argument functions using some input/output convention, say the input is in $x$ and the output is in $y$.
If the program has no loops, then $y \leq x + C$ for some constant $C$. If the program has no nested loops, then $y = O(x)$. If it has nesting depth 2 (a loop can appear within another loop, but that's it), then $y = O(x^C)$ for some constant $C$. More generally, if the program has nesting depth $d$, then $y$ can be bounded by a function on level $d$ on the Ackermann hierarchy.
The Ackermann function is constructed in such a way that it doesn't belong to the Ackermann hierarchy, and so cannot be computed by a LOOP program. In brief, it grows too fast.

Growing too fast isn't the only reason for not being primitive recursive. Indeed, using diagonalization we can construct Boolean recursive functions which are not primitive recursive. Let $f_i$ be an effective enumeration of all primitive recursive functions, and define
$$
f(n) = \begin{cases}
1 & \text{if } f_n(n) = 0, \\
0 & \text{otherwise}.
\end{cases}
$$
The function $f$ is recursive but, by construction, not primitive recursive.


Algorithm for maximizing the number of same-sized groups Let's say you have groups of objects, and a certain amount of objects you can add to these groups (you cannot create new groups, and do not necessarily have to use all your extra objects), and the goal is that you want to maximize the number of same-sized groups.
There can be multiple correct answers, and you can add to different groups (i.e. you can add 2 to one group, 3 to another, etc.)
Examples:
group sizes:[1,1,1], able to add 7 objects
Answer: 3, every group already has the same amount
[3,0,2,2,1], able to add 3 objects
Answer: 4, you can add 2 objs to the group with 0, and 1 obj to the last group that has 1.
So you maximize the 2's.
[5,4,1,3,4], able to add 2 objs
Answer: 3, you can either add 1 obj to the group with 3, creating 3 4's, or you can add 1 to each of the groups of 4, creating 3 5's.
I can easily solve this using brute-force (for each number 1...n, where n is the max amount able to be added, try all possible combinations of adding to current groups and adding the number of newly created ones to the original total) but I am confused as to where the algorithmic optimization is.  Have a nice day, thanks!
edit: put some example code of what I've tried.
#include <iostream>
#include <vector>
#include <map>

int maxCountOfEqualGroupSize(const std::vector<int>& groups, int objsToAdd) {

int maxGroupCount = 0;
std::map<int,int> groupSizeToGroupCount;
for (const auto& i : groups) {
  groupSizeToGroupCount[i]++;
}

//edge case - all groups already have the same size
auto iter = groupSizeToGroupCount.begin();
int firstVal = iter->second;
bool foundDiff = false;
for (; iter != groupSizeToGroupCount.end(); ++iter) {
  if (iter->second != firstVal) {
    foundDiff = true;
    break;
  }
}

if (!foundDiff) {
  return groups.size();
}
//end edge case

//find biggest value and get that key
//Then advance that key one by one to the right
//for each iteration: start at that key, and start moving left
//filling groups in, once you run out of objs to fill with,
//terminate.
int maxKey;
for (const auto& p : groupSizeToGroupCount) {
  if (p.second > maxGroupCount) {
    maxGroupCount = p.second;
    maxKey = p.first;
  }
}

auto startIter = groupSizeToGroupCount.find(maxKey);
auto lastIter = groupSizeToGroupCount.rbegin();
auto firstIter = groupSizeToGroupCount.begin();

for (; startIter->first != lastIter->first; ++startIter) {
  int objCounter = objsToAdd;
  int runningGroupCount = startIter->second;

  auto startPoint = --startIter;
  ++startIter;
  for(auto goingLeft = startPoint;
     objCounter >= 0;
     --goingLeft) {

    int diff = startIter->first - goingLeft->first;
    int groupsToFill = goingLeft->second;
    int amountToAdd = groupsToFill * diff;
    if (amountToAdd > objCounter) {
      //add up to what we can, since we can't fill all the groups
      while (objCounter >= diff) {
        ++runningGroupCount;
        objCounter -= diff;
      }
    } else {
      objCounter -= amountToAdd;
      runningGroupCount += groupsToFill;
    }

    if (goingLeft == firstIter) {
        break;
    }
  }
  maxGroupCount = std::max(maxGroupCount, runningGroupCount);
}
return maxGroupCount;
}

int main() {
  std::vector<int> ttt = {1,1,1};
  std::vector<int> tt = {3,0,2,2,1};
  std::vector<int> t = {5,4,1,3,4};
  std::cout << maxCountOfEqualGroupSize(t, 2) << std::endl;
  std::cout << maxCountOfEqualGroupSize(tt, 3) << std::endl;
  std::cout << maxCountOfEqualGroupSize(ttt, 2) << std::endl;

}

Hint:

 Try working through some examples.  Can you narrow down the set of possible values that might appear in the largest group in the best solution?  (For instance, your second example has 2's as the value, and your third example has 4's or 5's.)  Can you see how to use that to help you do better than brute force?