Delay Constrained Shortest Path in $O(D \cdot |E|)$ time I have the following homework exercise:

  We are given a network $N=(G,w,d)$, $G=(V,E)$ together with a designated
  source node s∈V and target node $t \in V$, where $w\colon E \to Z^+$ and $d\colon E \to Z^+$. The
  values $w_{i,j}$ correspond to arc weights, $d_{i,j}$ correspond to delays,
  i.e., using the arc $(i,j)$ requires $d_{i,j}$ time. We are further given a
  positive number $D \in N$, the delay constraint. Develop an efficient, i.e.,
  $O(D \cdot |E|)$, algorithm to find a shortest path $P$ from some $s$ to $t$, which
  does not exceed the global delay constraint $D$, i.e., $\sum_{(i,j) \in P} d_{i,j}≤D$ (Hint: use a similar approach as the one used in the Bellman
  Ford algorithm).

I was able to find an algorithm that runs in $O(D \cdot |E| \cdot |V|)$ time. However I'm struggling with finding an algorithm that runs in $O(D \cdot |E|)$ time and I'm starting to think, that such algorithm is not even possible to create (although I don't have a formal proof for this).

Could you give me a clue how would such an algorithm look like?

Hint: For $1 \leq d \leq D$, compute inductively the shortest distance between $s$ and any other node at delay at most $d$. Each such iteration runs in $O(|E|)$, so the total running time is $O(D|E|)$. (This assumes that the graph is connected. Otherwise you have to replace $|E|$ with $|E|+|V|$.)


Why is (small) $o(n^2) \neq n^2$? We know that $10n^2 = O(n^2)$ but $10n^2 \neq o(n^2)$. What is the underlying principle?

The underlying principle is that the definitions of small o and big O are different.

Big O definition

$O(f(n)) = \{g(n) | \exists c > 0, \exists n_0 > 0, \forall n > n_0 : 0 \leq g(n) \leq c*f(n)\}$

In words:

$g(n)$ is an element of $O(f(n))$ if there exists a $c > 0$ and a $n_0 > 0$ such that for all $n > n_0$, $0 \leq g(n) \leq c*g(n)$

In your example $f(n) = n^2$ and $g(n) = 10n^2$

If we pick $c = 20$, $n_0 = 1$, you can check that for all $n > 1$, $0 \leq 10n^2 \leq 20*n^2$, so $10n^2 \in O(n^2)$

Small O definition

$o(f(n)) = \{g(n) | \forall c > 0, \exists n_0 > 0, \forall n > n_0 : 0 \leq g(n) < c*f(n)\}$

In words:

$g(n)$ is an element of $o(f(n))$ if for any $c > 0$, there exists a $n_0 > 0$ so that for all $n > n_0$, $0 \leq g(n) < c*f(n)$.

In your example $f(n) = n^2$ and $g(n) = 10n^2$

If we pick $c = 1$, you can check that there is no $n_0 > 0$ so that for all $n > n_0$, $0 \leq 10n^2 < 1*n^2$

Therefore the condition does not hold and $10n^2 \notin o(n^2)$.

Informal explanation

$g(n) \in O(f(n))$ if $g(n)$ grows slower than or in the same fashion as $f(n)$.
$g(n) = 10n^2$ grows in the same fashion (quadratically) as $f(n) = n^2$, so $10n^2 \in O(n^2)$.

$g(n) \in o(f(n))$ if $g(n)$ grows strictly slower than $f(n)$.
$g(n) = 10n^2$ grows in the same fashion and thus not strictly slower than $f(n) = n^2$, so $10n^2 \notin o(n^2)$

NOTE: I've used notation like $10n^2 \in O(n^2)$ because the definitions were actually sets. But in practice, there's accepted notation abuse and $10n^2 = O(n^2)$ is written instead.


How would I algorithmically "stretch" polygons on a plane by re-scaling the distances between interior points? I've been thinking about a computational problem and could use some guidance for how to go about developing an algorithm to solve it.

On a Euclidean plane, I have a polygon A, a set of points A* bounded by A, another polygon B (that does not intersect A), and another set of points B* bounded by B. What I want is to create a mapping between points in A* and B* (not necessarily one-to-one or onto), re-scale the distances between  mapped points (the rescaling can be different for each pair of points), and then "stretch" A and B so that mapped points are still contained within their bounding polygon but are the new distances away from each other. The polygons should maintain their shape to the greatest extent possible.

As a simple example, if A and B were squares of equal size centered along the X axis, A* consisted of the center point of A, B* consisted of the center point of B, and I wanted to halve the distance between those two points, I would stretch each polygon along the X axis towards the other by horizontally extending the top and bottom edges, horizontally shift the inner edges towards each other, and leave the outer edge unchanged. The new polygons would look like rectangles that are still centered along the X axis but with each of their center points and inner edges moved a quarter of the original distance towards one another.

Another way of visualizing the transformation is to use the raisin-in-bread analogy https://www.wwu.edu/skywise/hubble_pudding.html commonly used to explain the expansion of the universe. If the points in A* and B* were raisins, the algorithm would show how shapes around those points are distorted if space-time were expanding or contracting between pairs of points.

Ideally, a solution would generalize to any number of polygons with any number of mapped interior points.

Thanks

You might try using the spring model: https://en.wikipedia.org/wiki/Force-directed_graph_drawing.  Or, you could use optimization methods.  Build an objective function $\Psi$ that is a sum of penalty terms.  For each pair of mapped points $a^*,b^*$ that you are hoping will be at distance $c_{a^*,b^*}$, you have a penalty term $(d(a^*,b^*) - c_{a^*,b^*})^2$.  Also, for each point $a^*$, add a penalty term that is zero throughout most of the interior of $A$, but increases when you get close to the boundary of $A$ and rises to $+\infty$ for all points outside $A$.  Finally, find an arrangement of points that minimizes this objective function.  You could then apply any of a number of optimization methods to do this, such as gradient descent or others.  Stress majorization may be useful.


How to start solving this type of exercise: Determine if $L$ is in $RE\setminus coRE$ or $coRE\setminus RE$ or $R$ or not in $RE\cup coRE$? I'm asking this, because in every exercise I check if I can relate it to one of the things I know,

like:$A_{TM}$, $\overline{A_{TM}}$, ${HALT_{TM}}$,$\overline{HALT_{TM}}$, $E_{TM}$, $\overline{E_{TM}}$, $ALL_{TM}$

But in many cases I can not find the connection and then get stuck with the question.

For example:$$L = \big\{ \langle M \rangle \mid M \text{ is TM and }M \text{ accepts only palindromes}\big\}$$ I know the solution to this question, I am not asking for a solution to this.

I want to understand the line of thought so that I will begin to solve questions like this.
What are the guidelines?

What is the first thing that should come to my mind with such questions?

My initial thought was always to look for words like accepts to associate it to $A_{TM}$, $\overline{A_{TM}}$ or halts to associate it to ${HALT_{TM}}$,$\overline{HALT_{TM}}$ but that does not help me so much.

My questions are not only related to the example but to the questions in general of this kind, that I need to determine.

Thanks.

The line of thought that I find the most fruitful is: try to come up with a (semi)algorithm for the problem. If you succeed, great. If you don’t, it’s probably impossible.

Let’s apply it to your problem: determining whether a Turing machine accepts only palindromes. The trivial way to solve this problem is to go over all non-palindromes, and check whether your Turing machine accepts any of them. This shows that your problem is co-r.e., since you can enumerate all Turing machines which accept some non-palindrome.

There doesn’t seem to be a matching algorithm for enumerating Yes instances of your problem, so your problem is probably not r.e. Indeed, Rice’s theorem shows that your problem isn’t recursive, and so we can deduce that it is not r.e.

With a bit more work, you can show that your problem is $\Pi_1$-complete, that is, every problem in co-r.e. can be (effectively) reduced to it. To show this, it suffices to show a reduction from the non-halting problem to your problem. In this problem, given a machine $M$ and an input $x$, the goal is to determine whether $M$ does not halt on $x$. Given an instance $\langle M,x \rangle$ of this problem, construct a machine $M’$ which goes into an infinite loop (or rejects) unless the input is $10$ (an arbitrary non-palindrome), in which case it simulates $M$ on $x$, and then accepts (if $M$ ever halts). The new machine $M’$ accepts only palindromes if and only if $M$ doesn’t halt on $x$.


How to proof a heuristic? I am not very familiar with "heuristic", so please correct me if anything said by me is wrong.

Per my understanding, Algorithm is an automatic steps which guarantee to give a correct solution corresponding to a specific problem (and its input domain)

Heuristic is somehow a rule to guess the next step, hoping when repeating this rule a nearly-optimal solution is found.

Algorithm is proof-able, the complexity, the correctness, etc.

But I wonder how can one proof heuristic?

Indeed I wonder is "proof" a correct term / action correlate to heuristic, but how about say, proof the heuristic can give sub-optimal answer (like at most 10% worst than the optimal) for 90% out of all possible input?

According to Wikipedia:

  A heuristic technique (...) is any approach to problem solving, learning, or discovery that employs a practical method not guaranteed to be optimal or perfect, but sufficient for the immediate goals.

Thus you can employ a heuristic to design an algorithm. This would give suboptimal answers, however you can still state theorems that relate to the correctness of such algorithm:

For optimization problems you may write something like:

  For any $\epsilon>0$, the algorithm approximates the problem $P$ with a multiplicative factor $1+\epsilon$ in time $O(T(\epsilon))$.

which means that for every input, if the expected answer of $P$ is $y$ and your algorithm returns $y'$, then:

$$y\le y'\le (1+\epsilon)y$$

You can also bound the error with an additive factor for instance.

For decision problems, if you fix a probability distribution on the input, you may state that your algorithm returns a correct answer with a probability of 90%. That would be a correctness result.

In any case you should keep in mind that a heuristic usually denotes general ideas applicable in many situations, which is said to work well empirically and for which you don't try to prove error bounds (such as in simulated annealing).


Can the pre-order traversal of two different trees be the same even though they are different? This question pretty much explains that they can, but does not show any examples of there being two different trees with the same pre-order traversal.

It is also mentioned that the in-order traversal of two different trees can be the same though they are structurally different. Is there an example of this?

Tree Examples (image):

     A:                 B:
     ‾‾                 ‾‾
     1                  1
    /                  / \
   2                  2   3
  /
 3

This is an example that fits your scenario, Tree A root׳s value is 1, having a left child with value 2, and his left child has also a left child with value 3.

Tree B root׳s value is 1, having a left child with value 2 and a right child with value 3.

In both cases the Preorder traversal is 1->2->3.


Given a certain context sensitive grammar, can one find out if a simpler context free grammar exists? Given a generating grammar, is it possible to reduce it to a context free form, if one exists. One method might seem to be if the context sensitive rules can be reached from higher generating points, in some sense. However, is this an interesting question worth worrying about? Are there practical situations, where there is some benefit in reducing a more complicated language to a context free language?

No. By Greibach's theorem, it is undecidable whether a CSG generates a context-free language.


Maximum Circular Subarray sum This is a question from the book Algorithms by Jeff Erickson.

Suppose A is a circular array. In this setting, a “contiguous subarray” can be either an interval A[i .. j] or a suffix followed by a prefix A[i .. n] · A[1 .. j]. Describe and analyze an algorithm that finds a contiguous subarray of A with the largest sum.
The input array consists of real numbers.

My approach:

There are two possibilities

1.) No Wrapping around (We can use Kadane's Algorithm)

2.) Wrapping around(ie; Starting index of the subarray is greater than the ending index) (I have doubt in this case)

Now return the maximum of two cases as result.

For the second case, searching on the internet provided an approach without proof.

The approach is to find the subarray with minimum sum and subtract it from the sum of the entire array (ie; sum(A) - min_subarray_sum(A)). How is this solution correct?

Link for the method used in the second case: https://www.geeksforgeeks.org/maximum-contiguous-circular-sum/

Let $A$ be your array, let $B$ a circular subarray of $A$ that maximizes $\sum_{b \in B} b$, and let $C$ be the subarray that contains all elements of $A$ that are not in $B$. Notice that $C$ is also a circular subarray.

You have $\sum_{a \in A} a = \sum_{b \in B} b + \sum_{c\in C} c$, which implies that $\sum_{c \in C} c = \sum_{a \in A} a - \sum_{b \in B} b $. Since $\sum_{a \in A} a $ is a constant (w.r.t. $B$) and $B$ maximizes $\sum_{b \in B} b$, $C$ minimizes $\sum_{c \in C} c$.

Moreover, at least one of $B$ and $C$ is not only circular but also contiguous and can therefore be found in $O(n)$ time.


Prune and search Algorithm for Generating a Bottleneck Spanning Tree I'm trying to wrap my head around a prune-and-search algorithm for returning a bottleneck spanning tree, currently I'm selecting the median weight of all the edges, then divide the original graph G into two graphs containing the edges which are less than or equal to the median or greater than.
After separating the graphs, I test the median weight against the original graph (G) to see if it is a bottleneck value. I'm stuck on what to do, if the median is not a bottleneck value, I was thinking maybe I could compact the graph of edges with weights less than the median - but the cut of a compacted graph would still have the weights so the median wouldn't change. I'm thinking I need to form an MST at some point as well?
So far I have something like:
def F(G):
  m = find_avg_weight_of_edges(G)
  G_le_m = get_g_w_edge_weight_less_than_or_eqal_to(G,m)
  G_gt_m = get_g_w_edge_weight_greater_than(G,m)
  if is_bottleneck_value(G,x):
    T = F(G_le_m)
  else:
    # note quite sure what to do...
    # I can't remove the less than or equal to edges
    # since they are needed to make up the MST
    # but if I don't remove them m won't change
    # maybe some kind of reduce/scc function?
return T

Let $b$ is the bottleneck edge of $MBST$, and let $b$ has weight $w(b)$.
Suppose $e_{m}$ is the median weighted edge of $G$, and let $e_{m}$ has weight $w(e_{m})$. Suppose $G$ gets partitioned into two subgraphs $G_{1}$ and $G_{2}$ such that edges in $G_{1}$ have weight $\leq w(e_{m})$ and edges in $G_{2}$ have weight $> w(e_{m})$.
If $w(b) \leq w(e_{m})$, then there must exist an $MBST$ within $G_{1}$ itself. Since the algorithm is recursing on $G_{1}$, it will output an $MBST$ if it exists. If the algorithm does not output a valid spanning tree, it means $b \notin G_{1}$. In other words, $b \in G_{2}$.
In that case, the algorithm will update $e_{m}$ to be the median weight edge of $G_{2}$. The graph $G$ will again get partitioned into two subgraphs $G_{1}$ and $G_{2}$. And, the algorithm can repeat this process.


Why does Pascal have a high code density? The plots in http://blog.wolfram.com/2014/06/04/how-the-wolfram-language-measures-up/ seems to indicate that Pascal has a relatively high code density.  What features of the language makes it so?

Follow-up question:

Does this explain why Pascal are often introduced in high schools as one of the first programming languages?

What makes Pascal dense is not the features it has, but the features it doesn't. Here is a small list of features that make other languages less dense:

higher order functions
classes and inheritance
specialised syntax for sets, lists, hashes
built in regular expression syntax
good libraries


How to find optimal partition subsets Given a partition $[0,1]$，there are 5000 partition subsets $P_i=[a_{i1},a_{i2}]\in[0,1], 0≤a_{i1}\leq a_{i2} \leq 1, i \in \{1,2,...,5000\}$. I want to analyze these subsets and find 10 subsets to contain sixty or seventy percent of the subsets. These 10 subsets could be disjoint, or even overlapping.

First, let me be sure u r aware of SET PACKING & SET PARTITIONING Problems

https://slideplayer.com/slide/4514539/

Then, I think ur problem is much easier avoiding the overlapping & the complete coverage constraints.

Going simple, here r some heuristics (think as u solving for max/optimal accepting 30%-40%"deviation from optimality)

1-Pick the max. length partition, then in the next 9th steps choose bet the global max of remaining partitions & the max of those starting after what u have reached so far.... I think that's O(10*5000) let's call it $ O(k n) $

2-Do something similar to $Bucket$ $Sorting$

Divide the partition to 10 smaller partitions(put an overlapping sub partition in its starting point bucket) , then select the max length one in each bucket. Still the same order complexity $ O(k*n) $

Finally, maybe a little bit complicated, but if u want a Theoretical abstraction of ur problem I've just watched this about the $maximum$ $K$ $coverage$ problem and the $Influence$ $maximization$ problem.

If u looked to the interval [0,1] as say M smaller/unit sub intervals being ur target population, and viewed each sub partition as connected to/infleuncing the sub intervals(units) it covers. Then u want to select $K$ (10 in ur case) subpartitions that gives u maximum coverage/influence

https://youtu.be/GqKbx3LCQqE


Optimization over convex combinations in a circle Consider the following situation: given a triangle $ABC$ inscribed in a circle, define $f$ as the product

$$f(P) = d(P, A) \; d(P,B) \; d(P,C)$$

where $P$ is a point on the circle and $d$ are distances between points.

Now, every point $D$ in the interior of the circle can be written as a convex combination of points $D_i$ on the circle:

$$D = d_1 D_1 + d_2 D_2 + d_3 D_3$$
where each $d_i > 0$ and $d_1+d_2+d_3=1$. Then we define $F$ as

$$F(D) = d_1 f(D_1) + d_2 f(D_2) + d_3 f(D_3).$$

The problem I am interested in is: find the choice of points $\{D_1,D_2,D_3\}$ which minimizes $F$ for a given $D$.

However, since the optimization is performed over all possible choices of $\{D_1,D_2,D_3\}$, it is in general very difficult. Could this perhaps correspond to a more manageable optimization problem that can be computed?

Note that if one was to remove the restriction that points $D_i$ lie on the circle and define $f$ in the same way for every point in the interior, the minimization problem would correspond exactly to finding the convex hull (convex envelope) of the function $f$. This would provide a lower bound for the original problem, but I am not sure if the computation of this quantity is in any way easier.

I would appreciate any pointers with regards to computing the minimum.

A pragmatic approach is just to use off-the-shelf black-box mathematical optimization algorithms.

In particular, define parameters $\theta_1,\theta_2,\theta_3$, representing the angle from the horizontal of $D_1,D_2,D_3$, respectively.  Here each $\theta_i$ is in the range $[0,2\pi)$.  The locations of $D_1,D_2,D_3$ are completely determined by the value of $\theta_1,\theta_2,\theta_3$.  Therefore, we can express the value of $F$ as a function of $\theta_1,\theta_2,\theta_3$: let's write this as $F^*(\theta_1,\theta_2,\theta_3)$.  It's tedious but not too hard to write down an explicit expression for $F^*$.

The problem becomes: given an expression for $F^*$, find $\theta_1,\theta_2,\theta_3$ that maximize $F^*(\theta_1,\theta_2,\theta_3)$, subject to $0 \le \theta_1,\theta_2,\theta_3 < 2\pi$.  This is a mathematical optimization problem on a three-dimensional objective function $F^* : [0,2\pi)^3 \to \mathbb{R}_{\ge 0}$.  There are standard algorithms for maximizing such a function, e.g., using gradient descent or any number of other methods.  You can try applying any of them.

In practice, I suggest you run gradient descent, starting from an initial point (an initial assignment to $\theta_1,\theta_2,\theta_3$) chosen at random.  Run gradient descent until convergence.  This will give you a local maximum.  Repeat this 1000 times, with 1000 different randomly chosen starting values, and take the best solution found in any of these iterations.  While there are no guarantees, I expect this to work well.  Generally speaking, these methods tend to work very well when the number of dimensions is small, and in this case, you have only 3 variables and 3 dimensions, so I expect they'll work well.  In particular, I expect the function $F^*$ to be piecewise smooth, with only a small finite number of pieces, so this procedure will probably ensure that you have at least one starting point in each piece and thus that gradient descent finds the maximum within each piece, ensuring that you find the global maximum with high probability.

If you wanted to do a more careful analysis, you could probably work out analytically the boundaries of each piece (i.e., decompose the three-dimensional space $[0,2\pi)^3$ into a finite union of regions within which $F^*$ is continuous and differentiable) and then run one iteration of gradient descent per piece.  However, that sounds tedious, and it's probably easier to just slam the thing into an off-the-shelf optimization tool and let the computer do the grunt work for you.  Doing the delicate analysis might be important if you want a procedure that is guaranteed correct in all cases (e.g., long and skinny triangles, etc.), but if you just want something that'll probably work without working too hard, I suggest you spare yourself the headache and let the computer do the crunching.


Why every finite set is computable? According to wikipedia, every finite set is computable.
Definition: set $S \subset N$ is computable if there exists an algorithm which defines in finite time if a given number $n$ is in Set.

Question: what is wrong with this counter-example:

given some $TM$
$S \subset N$
Lets assume $S$ could contain only $0$, i.e., either $S = \{0\}$ or $S = \emptyset$
if a given $TM$ halts then $S=\{0\}$ otherwise $S=\emptyset$

So set $S$ is finite, but not computable, since we cannot "compute" if a given $TM$ halts.

What is wrong above?

A similar question was answered here:

How can it be decidable whether $\pi$ has some sequence of digits?

We can ignore the question "if a given TM halts" as it is irrelevant what the question actually is, let's just name the condition C.

If C is true, then the correct algorithm is if n == 0 return true else return false. If C is false, the correct algorithm is return false. Whether C is true or false, one of these two algorithms is correct for every n, so such an algorithm exists.

Additionally, "does a given TM halt" is computable for the same reason - the correct algorithm is either return true or return false. What is not computable is a function that answers "does this TM halt" for any TM.


Arranging Colors in a Grid; Two Dimensional TSP? I am working on an interesting problem, which I believe can be solved algorithmically. I have a 6x8 on which I am attempting to arrange 48 color swatches, such that the transition from each swatch to its neighbor is as smooth as possible.

I can compute perceptual color differences using LAB-space encoding, so it is simple to generate a matrix of color differences. If I were attempting to simply order these colors, it would essentially be the traveling salesman problem; and I could use some heuristic solutions to get a near optimal result.

However, arranging the colors into a grid introduces a new dimension. In the interest of symmetry, we can wrap the edges of the grid so that each swatch has exactly 4 neighbors.

I have a hunch that this problem reduces to the following graph problem: Given a fully connected weighted graph of 48 nodes, find a subset of this graph such that the resulting graph is fully connected, each node has exactly 4 edges, and the sum of edge weights is minimized.

Any ideas on existing algorithms that might be helpful in solving this problem? Approximate solutions and heuristic solutions are acceptable as I imagine this problem is in EXP.

You can solve the problem with any solver for the Quadratic Assignment Problem (QAP). In the traditional QAP, facilities are assigned to locations such that the cost of transporting necessary goods between any two facilities is minimal. QAP is NP-hard.

Here we assign the colors $C$ to the swatches $S$. The weight or flow $w : S \times S$ between the locations is $1$ if they are neighbors and zero otherwise – you may define neighborhood however you like. The distance $d : C \times C$ would be LAB-metric you already defined.


Pumping lemma for CFG doubt I was looking at the pumping lemma for CFG. I came across the first problem $a^nb^nc^n$ and understood the answer. Then I thought of the problem $a^nb^n$. I know that this is context free and thought of applying it. I came across a weired situation. Someone please tell me where I went wrong.

So our language is $a^nb^n$. Let $m$ be the pumping length. Pumping lemma says that any sufficiently long string can be divided in $uvxyz$, where $v$ and $y$ can be pumped.

we take our string to be $a^mb^m$ and we can split it into $uxvyz$. Also we know that $|vxy|\le m$. Also $u$ can be $\epsilon$. In that case $vxy$ consists only of $a$, since $|vxy|\le m$ and there are $m$, $a$'s. So when we pump $v$ and $y$, the resulting string wont be in the language!

So where I got wrong? Is it wrong to take $u$ is $\epsilon$ and proceed from there?

I'm not sure why the answer of Karolis doesn't satisfy you. Let me chew it a bit more for you.
First, let's recall what the pumping lemma says (taken form the credible source of Wikipedia):

  If a language L is context-free, then there exists some integer p ≥ 1 such that any string s in L with |s| ≥ p (where p is a "pumping length") can be written as

  s = uvxyz

  with substrings u, v, x, y and z, such that

  |vxy| ≤ p,
  |vy| ≥ 1, and
  uv$^n$xy$^n$z is in L for all n ≥ 0.

Ok, so you say $L=\{a^nb^n \mid n \ge 0\}$ is CF, and thus we can run the Lemma on it.
Great. Here I'll show you that the lemma works for it. Say the pumping length is $p\ge2$.$^3$

The lemma says, that for any long enough $s$ string in $L$ (let's take $s=a^mb^m$ with $m\ge p$ as you suggest) we can write it as $uvxyz$ that satisfies some conditions.$^1$

Ok, let's give a try.
Let's  set $u=a^{m-1}$,  $vxy=ab$, $z=b^{m-1}$.

Sanity check: indeed, $uvxyz$ gives $s$. I don't know yet how to split the middle part into $vxy$, but see that condition (1) is satisfied, $|vxy|= 2 \le p$. Now for condition (2), i'll have to get the $vxy$ thing. Let's take $x=\epsilon$, thus $v=a$ and $y=b$. Do we satisfy condition (2)? Yes! $|vy|=2\ge1$. Yey.

Now, it says that no matter what $n$ I take, $uv^nxy^nz$ needs to be a word in the language $L$.
Let's see. By the way we picked the substrings,
$$ uv^nxy^nz = a^{m-1}a^n\epsilon b^{n}b^{m-1}$$
indeed! for any $n\ge 0$ we pick the word we get is $a^{m+n-1}b^{m+n-1}\in L$.

To conclude, we were able to take any word in $L$, and write it as $uvxyz$ so that the conditions of the lemma hold. This can be done for any language which is context-free (and for some that are not, as well) and we just saw how to do it for $L$.

more questions?

$^{1)}$ This should be emphasized: any word can be written in some way uvxyz etc. It doesn't mean that ALL the possible $uvxyz$ will work. Only one of them needs to work in order to satisfy the lemma.
$^{2)}$ when you want to prove that a language is not CF, then all the ways $uvxyz$ must be checked. This is because when you negate the lemma, the word "There exists ... that satisfies (1), (2), (3)" negates to "does not exist ... that satisfy" == "for all ... the condition is not satisfied". So to prove $L$ is not-CFG you need to check all possible ways. To show the lemma is satisfies for a CF $L$, you only need to find one.
$^{3)}$ What if $p=1$? Well, it is not. The lemma says that there exists some $p$. It doesn't say what this $p$ is. For our $L$, any $p \ge 2$ works, but $p=1$ doesn't. We need just one such $p$ (i.e., there exists), so taking $p=2$ is enough.


Compression Bounds - Determine and Visualize for hypothesis vs VC dimension I want to visualize or calculate the compression bounds for hypothesis classes. I learnt how to figure out the VC dimension. Let's say I define two hypothesis class. For example:
$$
H_k = \{h ∈ (0,1)_X \mid |h^{−1}(1)| ≤ k\}
$$
and
$$
H_{decst} = \{h^i_a \mid a ∈ R, i ∈ (1,2)\}, \text{ where } h^i_a((x1,x2)) = 1[x_i ≤ a].
$$
For VC dimension, I showed The VC dimension of $H_{decst}$ is 2. We can shatter the two points $x_1 = (2,0)$ and $x_2 = (0, 2)$ with the four functions $h_{0.5}, h_{1.5}, h_{1.5}, h_{2.5}$.
Also, It is not hard to see that $H_k$ shatters any set $C ⊆ N$ of size $k$, but no larger
set, since the all-1 labeling can not be realized on more than $k$ points with
$H_k$. Thus, the VC-dimension of $H_k$ is $k$.
Similarly, I want to figure out the compression bounds for $H_k$ and $H_{decst}$.

Generally, every class of finite VC dimension admits to a (exponential size in the dimension) compression scheme. This was an open question resolved a few years ago by Shay and Amir in this paper. However, this is an overkill for your question, since $H_k$ obviously has a $k$-comprresion scheme (only keep the samples labeled $1$, of which there are at most $k$, and the reconstruction is zero everywhere else).
$H_{desct}$ can be compressed to two samples, given $\left((a_i,b_i),y_i\right)_{i=1}^n$, we know that either there exists $j$ such $\forall i\in[n]: y_i=\mathbb{1}_{a_i\le a_j}$ or there exists $j$ such that $\forall i\in[n] : y_i=\mathbb{1}_{b_i\le b_j}$. The compression keeps $(a_j,b_j)$ and one more sample $(a_{j'},b_{j'})$ to indicate the correct coordinate of the threshold, e.g. if the former condition holds and $\forall i\in[n]: y_i=\mathbb{1}_{a_i\le a_j}$ then pick $j'$ such that $y_{j'}\neq y_j$ (so $y_{j'}=0)$ and $b_{j'}<b_j$ (this allows us to reconstruct the function $\mathbb{1}_{x_1\le a_j}$ from the two samples). If no such $j'$ exists then $\mathbb{1}_{x_2\le b_j}$ is also a consistent hypothesis, and our compression can keep only one sample.


Christofides algorithm: why must an MST have even number of odd-degree vertices? This question is not necessarily related to Christofides algorithm per se, I just ran into it when reading about it.

I assume that a minimum spanning tree must have an even number of odd-degree vertices, since Christofides algorithm uses this fact to find a perfect matching between "the set of vertices with odd degree in $T$" - an impossible mission for a graph with odd number of vertices...

I couldn't convince myself why this is true, can someone please convince me? Either by a formal proof or with an informal explanation.

Every edge in a graph is incident with exactly two vertices. The degree of a vertex is the number of edges incident with it. From this you get the standard fact that the sum of all the vertex degrees in a graph equals twice the number of edges; in particular, it is even. A minimum spanning tree is a graph in its own right. If it had an odd number of odd-degree vertices, the sum of degrees would be odd, which is impossible.


Kleene star operation on the empty language In my text book it is mentioned that: $\emptyset^*=\{\epsilon\}$ where $\emptyset$ is an empty language.

However, we know that $L \cdot \emptyset = \emptyset$, where $L$ is any Language.

I am not able to intuitively grasp this concept because the Kleene star operation points towards the fact that $\emptyset^*=\emptyset^0 \cup \emptyset^1 \cup \emptyset^2 \cup \cdots$ .

So why is $\emptyset^*$ not equal to $\emptyset$?

If you consider now the powers of a language $W$ you have
$W^xW^y=W^{x+y}$ If you want this to be consistent over $\mathbb N_0$,
i.e. the non-negative integers, you have to define
$W^0=\{\epsilon\}$. If you took it to be $\emptyset$ you would have
$W^x=W^{x+0}=W^xW^0=W^x\emptyset=\emptyset$ including, among others,
for $x=1$. Thus we would have $W^1=W=\emptyset$ for any $W$.
Thus this would clearly be inconsistent. A similar inconsistency arises for any other choice than $\{\epsilon\}$, which is the identity for language concatenation.

Hence, the only consistent consistent definition of $W^0$ for a non empty set $W$ is
$W^0=\{\epsilon\}$.

It is then convenient to extend the definition to the case when
$W=\emptyset$ as $\emptyset^0=\{\epsilon\}$.

This is just a consistent and convenient definition, often adopted in semi-rings but
it cannot be proved, unlike thw case when $W\neq\emptyset$ where there is no other consistent definition.

However, other definitions have then to be given in a consistent way, which
implies that

$$\begin{align}
\emptyset^*&=\emptyset^0\cup\emptyset^1\cup\emptyset^2\cup\ldots \\
     &=\{\epsilon\}\cup\emptyset\cup\emptyset\cup\ldots\\
     &=\{\epsilon\}
\end{align}$$

The topic is discussed on many web pages. In the case of the semi-ring
of numbers (the lack of precision is intentional) this is discussed at
length on this page: Zero to the zero power - Is $0^0=1$?.

The semi-ring of languages is described in this answer.


Is there an algorithm to detect race conditions in logic circuits? I'm writing a logic gate simulator. I would like to prevent user from constructing circuits prone to race condition such as flip-flops, and instead provide them as separate building blocks. Is that possible?

edit: I've got an idea. I guess that race conditions can only arise from logic circuit outputs directly or indirectly affecting their own inputs. So one way to check their validity would be to compare the truth tables of their inputs and outputs.

example one: NOT gate feeding itself

    A = !A
A | A   A | !A
--+--  ---+---
T | T   T | F
F | F   F | T
the truth tables do not match!

example two: SR NOR latch

!(A || B) = C
!(C || D) = B
!((!(A || B)) || D) = B // C => !(A || B)

 A | B | D | !((!(A || B)) || D)           B | B
---+---+---+--------------------          ---+---
 F | F | F |          F                    F | F
 F | F | T |          F                    F | F
 F | T | F |          T                    T | T
 F | T | T |          F (wrong!)           T | T
 T | F | F |          T (wrong!)           F | F
 T | F | T |          F                    F | F
 T | T | F |          T                    T | T
 T | T | T |          F (wrong!)           T | T

I hope you understand what I'm trying to convey. However, I have nothing to back it up, and I struggle to define it into an algorithm, and even if I could, it would have horrible complexity. I will try to refine it tommorow.

online truth table generator tool I used

edit 2: this is what I found in logisim manual:

  Logisim will not attempt to detect sequential circuits: If you tell it
  to analyze a sequential circuit, it will still create a truth table
  and corresponding Boolean expressions, although these will not
  accurately summarize the circuit behavior. (In fact, detecting
  sequential circuits is provably impossible, as it would amount to
  solving the Halting Problem. Of course, you might hope that Logisim
  would make at least some attempt - perhaps look for flip-flops or
  cycles in the wires - but it does not.) As a result, the Combinational
  Analysis system should not be used indiscriminately: Only use it when
  you are indeed sure that the circuit you are analyzing is indeed
  combinational!

However, the amount of inputs and outputs here is finite and well defined, as opposed to infinite memory and time resources in the Halting Problem, so I do not agree that this problem is equivalent to the Halting Problem.

However, the amount of inputs and outputs here is finite and well defined, as opposed to infinite memory and time resources in the Halting Problem, so I do not agree that this problem is equivalent to the Halting Problem.

There are two different problems here. The simple solution (the one you should implement, in my opinion) is to simply look at the connection graph of the gates, and detect if the graph contains any cycles. If yes, simply reject the input.

The problem logisim refers to, which would amount to solving the halting problem, is one where you allow cycles, but reject sequential circuits.

This is different, because not every cycle in the graph affects the output, or worse, it affects the output but not in an sequential way.

  However, the amount of inputs and outputs here is finite and well defined, as opposed to infinite memory and time resources in the Halting Problem, so I do not agree that this problem is equivalent to the Halting Problem.

Initially I disagreed, but after some more thinking, I agree. Do note that we have infinite time here - we can supply infinite sequences of inputs to the circuit in an attempt to get sequential behavior.

Under the condition that we always let a circuit stabilize before changing the inputs (or rejecting the circuit as sequential in case it never stabilizes), a finite circuit is a finite state machine. The crux is that the output of the circuit depends on the input plus the internal state of every gate in the circuit.

To prove that a circuit is non-sequential you can use the following algorithm:

Add the all-zero internal state to a queue.
While the queue is not empty, pop an internal state from the queue and construct the truth table for all inputs using that initial internal state. Also add the internal state to some set tracking internal states we have handled. For each internal state reached from this internal state while computing the truth table, add it to the queue if it's not inside our handled set.
If at any point in 2 a circuit does not stabilize, return sequential. If at any point during 2 the generated truth table does not equate the one from the all-zero internal state, return sequential. Otherwise return non-sequential.

Since there are a finite amount of possible internal states, this algorithm always terminates. And it fully explores all reachable states. Nevertheless, this algorithm is very, very much infeasible.


Verification wanted: Show the language $L=\{0^m1^n \enspace | \enspace m \neq n\}$ is not regular $$L=\{0^m1^n \enspace | \enspace m \neq n\}$$

I saw that this exact question exists elsewhere, but I couldn't understand what was being said there. My question does not mandate the use of the Pumping Lemma as stated "elsewhere", but I am using the Pumping Lemma anyway. I want to present what I have so far, and for someone to tell me if I'm on the right track:

Assume $L$ is not regular.
Let $p$ be the pumping length given by the Pumping Lemma for regular languages.
Let the string $w = 0^p1^{p+1} \in L$
By the Pumping Lemma, $w = xy^iz$, where $i \geq 0$, $\color{green}{\lvert y \rvert \geq 1}$, and $\color{red}{\lvert xy \rvert \lt p}$.
Let:

\begin{equation}
\begin{aligned}
\mathcal{x} &= \mathcal{0}^{p} \\
{y} & = {1}^{p+1} \\
{z} & = \varepsilon
\end{aligned}
\end{equation}

It is at this point in the proof that I get confused. I feel as if I've set it up well, but just can't finish. Here's what I've got, though:

We see that $\lvert y \rvert= p+1 \geq 1 \enspace \color{green}{\checkmark}$
However, $\lvert xy \rvert= p+p+1 \gt p \enspace \color{red}{\textbf{X}}$

As we can see by $\textit{(7)}$, our test string $w$ violates a $\color{red}{condition}$ of the Pumping Lemma, thus is not regular.

Thumbs up, thumbs down, anyone? Did I make the appropriate inferences about my split string $w$ in order to achieve a contradiction, and did I even split the string correctly? And to boot, did I even pick a $w$ that is useful to the proof?

This is a very hard one to prove via the pumping lemma, as you have to construct a string that eventually gives you something of the form $0^{n}1^{n}$ for some $n$ when you pump it the right number of times. As Renato notes, your decomposition (at the time of writing this answer) is incorrect. We'll come back to this.

A simpler way is to use the closure properties of regular languages. In particular, regular languages are closed under complementation and intersection, so

If $R$ is regular, then $\overline{R} = \Sigma^{\ast}\setminus R$ is also regular.
If $R_{1}$ and $R_{2}$ are regular, then $R_{3} = R_{1} \cap R_{2}$ is also regular.

So we assume that $L = \{0^{m}1^{n} \mid m \neq n\}$ is regular. Then by (1), $\overline{L} = \Sigma^{\ast}\setminus L$ is regular. In particular note that $\overline{L}$ includes all strings of the form $0^{n}1^{n}$.

The language $A = \{0^{a}1^{b} \mid a,b \in \mathbb{N}\}$ is regular (we can show this via a regular expression, DFA or regular grammar for the language, e.g. $0^{\ast}1^{\ast}$).

Then by (2) $\overline{L}\cap A$ must also be regular, but this is the language $\{0^{n}1^{n}\}$, which is not regular (and much easier to prove via the pumping lemma!).

As noted in the question you linked however, it is possible to do it with the pumping lemma, but you need to pick your starting string carefully. As we only have two sections to the string, the obvious approach is to have a string of the form $0^{p}1^{x}$ for some $x$, so then we know that $y = 0^{k}$ for some $k\leq p$. Now the trick is to pick $x$ such that we can pump the string some number $y$ times and get $p + (y-1)\cdot k = x$. Of course we don't know what $k$ is - it could be anything from $1$ to $p$, so $x$ needs to take this into account. Hence $x$, in part, needs to (almost) be a multiple of every number from $1$ to $p$. So if we pick $x = p + p!$, we can say that for every $k$, there exists a $y$ such that $p + (y-1)\cdot k = p + p!$. In particular $y = \frac{p!}{k}+1$.

So then our starting string is $s=0^{p}1^{p+p!}$. By the pumping lemma if $L$ is regular, we can break $s$ up in $xyz$ such that $|y| \geq 1$, $|xy| \leq p$ and $xy^{i}z \in L$ for every $i \in \mathbb{N}$, but we have just shown that for $i = \frac{p!}{k}+1$, we get the string $0^{p+p!}1^{p+p!} \notin L$. Hence $L$ violates the pumping lemma, can thus can't be regular.


Counting inversions in a list of integers using divide and conquer techniques This is a homework. It looks easy, but not really.

A list of integers $a_n$, for every $i<j$, if $a_i>2a_j$, then it is an inversion. Count the inversions in the list, and return the count and the ordered list. Note, here the order is defined by the condition, not just sort the integers.

The easiest way is double loop, but it will be a $O(n^2)$ algorithm. So I think I should try divide and conquer, by modify the merge sort algorithm. I think I could get a $O(n \log n)$ algorithm. But I found, while merging and counting cross-halve inversions, I have to scan all the elements in both left halve and right halve. Equivalent to a double loop.

For example:

[8] [6, 3]

8 and 6 are not inversion, 6 and 3 are not inversion, but 8 and 3 are inversion. I have scan all the elements to make sure there's no exception.

Another example:

[2, 7] [1, 5]

There no inversion in either halve, but 7 and 1 are inversion.

I am thinking may be there's a function, and I can define $b_n=f(a_n)$, then I can treat $b_n$ as normal merge sort problem. But I could not figure it out.

You can do the counting in linear time for each merge step by iterating over the right list and keeping track of the following information regarding the left list:

pointers to the first and last element that formed an inversion with the previous element of the right list
the number of elements between those pointers

Since this is homework, I'll leave it to you to work out the details and analysis.


Finding the median in a heap Given a binary heap $H$, indexed in $[1..n]$, whose elements are integers, is there a way to quickly find its median in $O(\log n)$-time?

It takes $\Omega(n)$ time to find the median of a heap in the worst case. The reason is that the lowest levels of the heap (the leaves and their close ancestors) can be very disordered, and they make up the majority of the heap. As a result, if you can find the median on a heap, you can find a median of the $\Omega(n)$ unordered elements near the leaves. Since finding the median in an unordered list takes $\Omega(n)$ time, so does finding the median in a binary heap.

For instance, if finding the median in an unordered array of size $n$ takes a given amount of time, presumably it shouldn't be any faster to find the median of that array if we prepend to it an array of size $n$ consisting of only $-\infty$ and append to it an array of size $n$ consisting of only $+\infty$. Yet, this new array of size $3n$ is a valid binary heap, and its median is also the median of the original unordered array of size $n$. Thus, if we can find the median of the heap in $O(\log 3n) = O(\log n)$ time, then we can also find the median of an unordered array in $O(\log n)$ time.

Since we know that it takes $\Omega(n)$ time to find the median of an unordered array of size $n$, it must also take $\Omega(n) = \Omega(3n)$ time to find the median of a heap of size $3n$.


Large number of layers in a neural network? How large can the number of layers in a neural network be? Can there be maybe 1000 layers with, say, 1000 neurons in each layer?

I imagine the brain has hundreds of thousands of layers.

In principle, there is no limit on the number of hidden layers that can be used in an artificial neural network.  Such networks can be trained using "stacking" or other techniques from the deep learning literature.  Yes, you could have 1000 layers, though I don't know if you'd get much benefit: in deep learning I've more typically seen somewhere between 1-20 hidden layers, rather than 1000 hidden layers.  In practice the number of layers is based upon pragmatic concerns, e.g., what will lead to good accuracy with reasonable training time and without overfitting.

Don't confuse artificial neural networks with the brain.  The behavior of artificial neural networks doesn't necessarily tell us anything about the brain, and you can build artificial neural networks whose structure doesn't match anything found in the brain.


Count substrings with same first and last characters We are given a string S, we need to find count of all contiguous substrings starting and ending with same character.

Examples :

Input  : S = "abcab"
Output : 7
There are 15 substrings of "abcab"
a, ab, abc, abca, abcab, b, bc, bca
bcab, c, ca, cab, a, ab, b
Out of the above substrings, there
are 7 substrings : a, abca, b, bcab,
c, a and b.

Input  : S = "aba"
Output : 4
The substrings are a, b, a and aba

a) One approach would be to use brute force, (O(n^2)) approach where check for each substring and increment count
Please suggest optimal solutions

You can do it in linear time. Loop over the characters of the string and count the frequency (how many times it appears in the string) of each distinct character. Then if a character has a frequency $n$ then the count of all contiguous substrings starting and ending with same character is $\frac{(n+1)n}{2}$ and finally sum up all counts.

Example 1: $abcab$.
Frequencies: $f(a)=2, f(b)=2, f(c)=1$.
Counts: $3,3,1$ which gives $7$.

Example 2: $aba$.
Frequencies: $f(a)=2, f(b)=1$.
Counts: $3,1$ which gives $4$.

Example 3: $aaa$.
Frequencies: $f(a)=3$.
Counts: $6$ which gives $6$.

Example 4: $abc$.
Frequencies: $f(a)=1, f(b)=1, f(c)=1$.
Counts: $1,1,1$ which gives $3$.

NOTE:
$n*(n+1)/2$ is deduced this way:

Suppose you have this string $abcaba$ where first $a$ can be matched with second a at index 3 (0 indexed array) and also third $a$ at index 5.

frequency of $a$ is 3 so for first $a$ we will get 3-1 = 2 continuous substrings.

for second a we get 2-1 = 1 continuous substring

We are seeing a pattern as this: n,n-1, n-2.....0

This leads to the formula n*(n+1)/2 as we also need to consider individual $a$'s.

2 + 1 + 3 times $a$ = 6

Same is true for other characters in the string.


Sorting as a linear program A surprising number of problems have fairly natural reductions to linear programming (LP). See Chapter 7 of [1] for examples such as network flows, bipartite matching, zero-sum games, shortest paths, a form of linear regression, and even circuit evaluation!

Since circuit evaluation reduces to linear programming, any problem in $P$ must have a linear programming formulation. Therefore, we have a "new" sorting algorithm, via reduction to a linear program. So, my questions are

What is the linear program that will sort an array of $n$ real numbers?
What is the running time of the reduce-to-LP-and-solve sorting algorithm?

Algorithms by S. Dasgupta, C. Papadimitriou and U. Vazirani (2006)

The following answer is basically equivalent to the one you already know, but may seem a bit less "magical". On the other hand, it's more technical, but I believe the general technique "write your problem as an optimization on permutation matrices and invoke Birkhoff-von Neumann" is a great one to know.

For a permutation $\sigma$ of $\{1, \ldots, n\}$ define the permutation matrix $P_\sigma$  as the 0-1 matrix such that $P_{ij} = 1$ if $j = \sigma(i)$ and $P_{ij}=0$ otherwise. This is simply the matrix which permutes the coordinates of a vector $x$ according to $\sigma$: if $y = P_\sigma x$ then $y_i = x_{\sigma(i)}$. I'll denote $y=P_{\sigma}x$ as $\sigma(x)$ from now on.

One more definition: a non-negative $n\times n$ matrix $M$ is doubly-stochastic if each one of its rows and each one of its columns sums to 1.

And one fact which is very important in combinatorial optimization - the Birkhoff-von Neumann theorem:

  A matrix $M$ is doubly stochastic if and only if it is a convex combination of permutation matrices, i.e. if and only if there exist permutations $\sigma_1, \ldots, \sigma_k$ and positive reals $\alpha_1 , \ldots, \alpha_k$ such that $M = \sum_{i = 1}^k{\alpha_i P_{\sigma_i}}$ and $\sum{\alpha_i} = 1$.

Notice that a doubly stochastic matrix is defined by the inequalities

$$\forall i: \sum_{j = 1}^n{M_{ij}} = 1$$
$$\forall j: \sum_{i = 1}^n{M_{ij}} = 1$$
$$\forall i, j: M_{ij} \geq 0$$

All these inequalities taken together determine a polytope $P$, and the Birkhoff-von Neumann theorem states that the extremal points (vertices) of this polytope are all permutation matrices. From basic linear programming, we know this implies that any linear program which has the above inequalities as its constraints (and no other constraints) will have a permutation matrix as an optimal solution.

So given an input $a = (a_1, \ldots, a_n)$ to be sorted, we just need to come up with a linear objective $f_a(M)$ for which:

$f_a(P_\tau) < f_a(P_\sigma)$ if $\sigma(a)$ is sorted but $\tau(a)$ is not.

Then formulate a linear program with objective to maximize $f_a(M)$ and the inequalities above as constraints, and you are guaranteed that an optimal solution is the permutation matrix $P_\sigma$ for $\sigma$ such that $\sigma(a)$ is sorted. Of course, it's easy to "read off" $\sigma$ from $P_\sigma$.

One choice for $f_a(M)$ is $v^T M a$ where $v = (1, \ldots, n)$. Verify that

this is linear in $M$;
for $P_\sigma$, $f_a(P_\sigma) = \sum_{i = 1}^n{i a_{\sigma(i)}}$;
the above is maximized at the $\sigma$ for which $\sigma(a)$ is sorted (by contradiction: otherwise you could switch two coordinates of $\sigma(a)$ and achieve a higher value).

And voila, you have a linear program for sorting. Seems silly for sorting, but this is in fact a powerful method in optimization.


Justification for the pumping lemma of context free languages I understand intuitively why the pumping lemma for regular languages must hold. That is to recognize a infinite string with a finite amount of states you must repeat states and you can "pump" those repeated states as many times as you wish.

However for the context free language version I can't seem to come up with the same intuitive understanding for why the lemma holds. My textbook mentions abusing the fact every CFG can be put into Chomsky normal form and then using some properties of binary trees to show productions can be pumped but Im having a hard time following why this would lead to repeated states, let alone two repeated states.

A context-free grammar has a finite number of nonterminals. This means the number of different derivation trees you can generate such that each nonterminal on each path of each tree is different is also finite: if you have $n$ nonterminals, then each path longer than $n$ will contain at least one nonterminal twice. That means all other derivations have a repeating nonterminal $A$ on some path. We can then pump by repeating the path segment from $A$ to $A$ arbitrarily often. This remains true after we make the grammar proper by removing all unproductive and unreachable nonterminals and cyclic rules.


How to correlate a matrix of values to get a coordinated point? I got a n*m matrix updated in realtime (i.e. about every 10ms) with values between 0 and 1024, and I want to work out from that matrix a multitouch trackpad behaviour, which is:

generate one or more points on the surface given the values on the matrix,
make this or those point as big as the value can be.

For example here is a few lines of a 9x9 matrix updates, and we can consider the following matrix as an example (with a touch in the middle):

[ [ 12,  7,12 ],
  [ 12,129,19 ],
  [ 12, 11,22 ] ]

The goal is to mimic the behaviour of a common touchpad (like on every smartphone, or laptop). So, I'm getting values from a evenly distributed matrix of capacitive sensors on a physical object, which are processed by a microcontroller into a matrix, and I want to get coordinates and weight of one or several points.

The idea would be to get something like this (of course, I don't expect to have more than 2 or 3 detected points, and that level of precision with a matrix that small).

Here are a few example raw logs:

http://m0g.net/~guyzmo/touch_diag.log
http://m0g.net/~guyzmo/touch_double.log

Edits:

Thinking about my problematic made me consider this idea: I think I should make some kind of interpolation to augment the definition of the matrix, and in some way make the new values additive.

i.e. imagine we have the following matrix :

[ [ 200, 200, 150 ],
  [ 150, 150,  80 ],
  [  80,  80,  40 ] ]

and we want to interpolate it somehow into something that would look like (I'm inventing the values, but it's to expose the idea):

[ [ 200, 400, 200, 175, 150 ],
  [ 175, 200, 175, 150, 125 ],
  [ 150, 170, 150, 125,  80 ],
  [ 100, 125, 100,  80,  60 ],
  [  80,  80,  80,  60,  40 ] ]

I've looked at interpolation algorithms, and it looks like the one we want that is the closer to our needs is the hermite interpolation. But though I have RTFM on interpolation methods, I don't know how I can apply it to a matrix.

I finally managed to get what I want. I used python's scipy's

interpolate.RectBivariateSpline(x,y,z,kx,ky)

to create a 60x60 matrix out of the 3x3 matrix. And out of that, I used opencv libraries to detect blobs (mainly, findContours() and fitEllipse()), so now I got a list of ellipses matching the several touches I have.


Pumping Lemma confusion I have the following language...

$$A=\{a^ib^i | i>0\}\cup\{a^jb^k|j>2, k>3\}$$

Now, pumping lemma states that a regular language can be written in the form $x=pq^ir$. What confuses me is how to split the language into three parts, this is my attempt:

$p=a^j$

$q=a^jb^k$

$r=b^k$

I believe my attempt is incorrect but this is the extent of my knowledge on the subject. Can someone explain how to split the language properly?

The mistake is in what you're attempting to split. The pumping lemma says if $L$ is a regular language, there exists a number $m$ (the pumping length) such that every string $x \in L$ can be be split into three parts, $x=pqr$ such that:

$|pq| \leq m$
$|q| \geq 1$
$pq^{i}r \in L$ for all $i \in \mathbb{N}$

So it's the strings in the language that can be split and pumped, not the language.

So for the language you give, which is regular, you should be able to take any string, split it and pump it. One problem with doing this in practice is that the pumping length $m$ is not typically known, however we can take a larger example here and we don't have to worry.

Consider the string $y = a^{2m+3}b^{4}$, then we know that $pq = a^k$ for some $k \in [1,m]$, and in particular $p = a^{k_{1}}$ with $k_{1} \in [0,m-1]$, $q = a^{k_{2}}$ with $k_{2} \in [1,m]$ and $k_{1}+k_{2}=k$. Then $r = a^{2m+3-k}b^{4}$. As $k \leq m$, this string is in the language $A$ (it fits the definition in the second part).

Now we get to the pumping part; as $A$ is regular, assuming that we've split things correctly, we should be able to pump $y$. If we pump down, we get $a^{2m+3-k_{2}}b^{4}$, which is still in $A$ (again, $k_{2} \leq k \leq m$). If we pump up $n$ times, we get $a^{2m+3+nk_{2}}b^{4}$, which still fits the definition and is in $A$.

Then as $A$ is regular, we should be able to do this for every string in the language, but there's no real reason we would want to as it doesn't tell us anything - there are non-regular languages which can still be pumped (e.g. see the wikipedia article). What we use the pumping lemma for is showing that languages are not regular by showing that the language we suspect is not regular contains at least one string that cannot be broken up and pumped in any way.


Proving laws of take and drop functions using structural induction on lists I'm trying to prove the following laws using structural induction on (finite) lists:

take m (drop n xs) = drop n (take (m + n) xs)
drop m (drop n xs) = drop (m + n) xs

for all m, n and every finite list xs (code snippets are in Haskell). I'm not sure how to tackle it though, more specifically: afaik when using induction on intervals, the first induction step is for m > n and the second for m ≤ n. Now in this case the law must also be valid for all finite lists, does that mean the proof involves prooving all the following?

case m > n: [] and (x:xs), and in the latter m + n > length xs and m + n ≤ length xs
case m ≤ n: [] and (x:xs), and in the latter m + n > length xs and m + n ≤ length xs

If yes I can update my question and show exactly where I'm stuck.

(Please don't post the entire solution, I'd just like to have some pointers. Thanks!)

UPDATE

If [] denotes the empty list and (x:xs) a list with at least one element (x is the head of the list and xs its tail), possible definitions of take and drop are:

take n [] = []
take 0 xs = []
take n (x:xs) = x : take (n - 1) xs

if n is greater than l, where l is the length of the input list, then take returns a list of length l

drop n [] = []
drop 0 xs = xs
drop n (x:xs) = drop (n - 1) xs

if n is greater than l, where l is the length of the input list, then drop returns the empty list

You can prove the second law by induction on n:

Base case:

drop m (drop 0 xs) = drop m xs (definition of drop, base case)

= drop (m + 0) xs (since m + 0 = m)

Inductive step:

We have to consider two cases: when the input list is empty, and when it's not empty. When it's empty, we have

drop m (drop n []) = drop m [] = [] = drop (m + n) [] (definition of drop, base case)

When the input list is not empty, we have

drop (m + n) (x:xs) = drop (m + n - 1) xs (definition of drop, inductive case)

= drop m (drop (n - 1) xs) (inductive hypothesis)

= drop m (drop n (x:xs)) (definition of drop, inductive case)

I imagine that the first law is not much more difficult. Try to prove it by induction on n, and if it doesn't work, try induction on m. One of them will probably work.


Difficulty in understanding an approach to SPOJ $d$-query problem I was trying to solve this problem on SPOJ:

  Given a sequence of $n$ numbers $a_1, a_2, \ldots, a_n$ and a number of $d$-queries. A $d$-query is a pair $(i, j)$, $(1 \leq i \leq j \leq n)$. For each $d$-query $(i, j)$, you have to return the number of distinct elements in the subsequence $a_i, a_{i+1}, \ldots, a_j$.

Specifically, the input to the problem is as follows.

Line 1: $n$, where $1 \leq n \leq 30000$
Line 2: $n$ numbers $a_1, a_2, \ldots, a_n$, where $1 \leq a_i \leq 10^6$
Line 3: $q$, the number of $d$-queries, where $1 \leq q \leq 200000$
Finally, $q$ lines, where each line contains 2 numbers $i, j$ representing a $d$-query, where $1 \leq i \leq j \leq n$.

But after a few hours of trying to solve it, I googled for a possible hint. I found one approach described here by user irancoldfusion:

  First I thought a good O(n ^ 2 + q log q) would pass, but it didn't run in time. Then, I thought of the idea below which I haven't implemented yet:

  The result of a query [a, b] is number of integers whose last occurrence in [1, b] is >= a.

  Let's have two kinds of events: QueryEvent and NumberEvent. First we read whole input and sort all events, the key for QueryEvents are their end (i.e. b for query [a, b]), and for NumberEvents the key is their position in array.

  We also have a segment tree which answers the queries of kind: how many elements are at position range [x, y]. Initially the tree is empty.

  Then we process events in order:
    + When we meet a NumberEvent:
      1. If number has occurred before at position p, we remove p from segment tree.
      2. We add position of number to the segment tree.
    + When we meet a QueryEvent:
      - Query the segment tree, and find the answer.

  The overall time complexity of algorithm is O( (n + q) log n + (n + q) log (n + q) )

But I am not able to understand it properly. Can anybody help me in understanding the approach. I want to understand how are the positions inserted and deleted from the tree. That is, what does the segment tree hold, say for an interval.

(This answer is no longer very interesting, now that the question has been corrected to clarify that $1 \le a_i \le 10^6$ instead of $1 \le a_i \le 106$.)

This can be solved in $10^6(n+q)$ operations.

First, build a table $T[\cdot,\cdot]$, where $T[j,x]$ is the index of the last occurrence of the number $x$ among $a_1,a_2,\dots,a_j$.  In other words,

$$T[j,x] = \max \{i : a_i=x \wedge 1\le i\le j\}.$$

This table can be built in $10^6n$ steps.

Next, you should be able to see how to answer a query $(i,j)$ quickly, by doing some lookups into the $T$ table.  I'll let you work out the details so you can have the fun of solving the problem.


Measure two qubits, one from entangled pair, in Bell basis? In quantum teleportation we require both sender (Alice) and receiver (Bob) to share an entangled pair of qubits in the $|\beta_{00}\rangle$ Bell state. Then, if Alice wants to teleport a quibt $|v\rangle$ to Bob, she needs to measure $|v\rangle$ and her qubit from an entangled pair in the Bell basis. Such measurment requires her to perform a CNOT on the two qubits with $|v\rangle$ being the control qubit and then apply Hadamard transformation to $|v\rangle$.

I can't understand how can she perform the above. If we represent quantum gates as matrices, what vector would represent the input to the CNOT matrix (the pair $|v\rangle$ and Alice's qubit from an entangled pair?) In other words, how can we represent a pair that Alice wants to apply CNOT to (when performing measurement in the Bell Basis?)

I know that Bell measurement does not require CNOT in general, but this is one of the ways it could be implemented (assuming we just want to get the classical 2-bit value).

My intuition is that because we need to operate on a tensor product of $|v\rangle$ and the entangled pair, we need to create a matrix representing an operation performing CNOT on $v\rangle$ and first qubit from the pair, and I on the second qubit from the pair, so it would be like $CNOT \otimes I$. Is this correct?

I figured out that as we are operating on 3 qubits ($|v\rangle$ and $\beta_{00}\rangle$ pair) and we want to perform CNOT on the first two (if we enumerate like 1- $|v\rangle$, 2- first from pair, 3 - second from pair) it is just like we want to perform $CNOT \otimes I$ on $|v\rangle \otimes |\beta_{00}\rangle$.

After performing the CNOT described above we need to perform H on the $|v\rangle$ qubit, which is now entangled (as CNOT is an entangling operation), so it is like we want to perform $H \otimes I$ on the three (where $I$ is 3 x 3 identity matrix).

Beaing able to perform both steps described above we are able to perform a measurement of qubit $|v\rangle$ and the first qubit from the entangled pair $|\beta_{00}\rangle$ in the Bell basis.


Global indexing of shared nodes in parallel Consider a tiling of quadrilaterals in 2D that provide complete coverage of a particular region.  N quadrilaterals are distributed across many parallel threads, typically in a way to keep groups of quadrilaterals together.  In each quadrilateral we distribute np nodes, with some nodes located along the boundary of the quadrilateral.  This gives rise to a 2D indexing of nodes (i,j) where i=1,..,N is the quadrilateral index and j=1,..,np is the local index of the node within that quadrilateral.

We now wish to develop a map from (i,j) to a global index of nodes that accounts for coincident nodes that may exist along the boundary of the quadrilaterals (e.g., see attached image of two quadrilaterals with three shared nodes -- np=9 but global index goes from 1..15).  In serial, a simple algorithm would be as follows:

let k = 1
let X = map from local index (i,j) to global index k
for each quadrilateral i
  for each node j in quadrilateral i
    if (i,j) is coincident with a node (i',j')->k' in X
      assign index k' to (i,j)
    else
      assign index k to (i,j) in X
      k = k + 1

In parallel, only elements of this map that are associated with quadrilaterals on the local thread need to be stored.  We can further assume that each thread has complete knowledge of the quadrilateral indices and nodes of its own quadrilaterals and those quadrilaterals and nodes that are spatially adjacent.

So the question is:  Is there a parallel algorithm that performs better than the serial algorithm above?

Assume you have an array (random access sequence) of tuples <q, j, x, y, first, k_tmp, k> where q is the (integer) identifier of a quadrilateral, j is the local index (within the quadrilateral) of a node, x, y are the coordinates of a node contained in quadrilateral q, and first, and k_tmp, and k are fields to be filled in later.

sort the array lexicographically on x, then y, then q (i.e. all the array elements corresponding to the node at x,y will be adjacent in increasing order by q).  The sort can be done in parallel.  See for example Blelloch, Leiserson, Maggs, Plaxton, Smith, and Zagha, "A comparison of sorting algorithms for the connection machine CM-2", Proc ACM Symp Parallel Alg and Arch, SPAA-3:3-16, 1991, or Arpaci-Duesseau, Arpaci-Dusseau, Culler, Hellerstein, and Patterson, "High-Performance Sorting on Networks of Workstations", SIGMOD Conference, 1997:243-254.
foreach element e of the array, in parallel:

array[e].first = if (array[e].x = array[e-1].x and array[e].y = array[e-1].y) then 0 else 1

resort the array lexicographically on q, and j.
calculate array[].k_tmp as the parallel prefix sum (sometimes called a "scan" operation) of the array[].first fields.  A good paper on parallel prefix sum is Chatterjee, Blelloch, and Zagha, "Scan Primitives for Vector Computers," Proceeedings of Supercomputing, 1990:666-675.
resort the array lexicographically on x and y and q.
calculate array[].k as the segmented copy scan of array[].k_tmp using array[].first as the bit vector to determine the segment boundaries (see Section 3.2 of the paper by Chatterjee, Blelloch, and Zagha).  Briefly: The segmented copy scan will use array[].k_tmp if array[].first is 1, else it will use the array[].k_tmp from the first element to the left where array[].first is 1.
you can now resort the array lexicographically on q and j and the k field should be correct for each array element.

The fact that we sorted the array back and forth and back and forth seems to indicate that we should probably, in practice, use two data structures (one sorted on q and j and one sorted on x and y) with pointers back and forth between them.


Is there a generic algorithm to optimally combine elements by some arbitrary scoring method? I'm looking for a generic algorithm to optimally combine elements of a list. I'm not sure if it even exists, but I believe some kind of divide-and-conquer algorithm could exist. In my specidifc case, optimally combining the score means minimizing, but that's probably not important

Formally stated:

We have the function SCORE(L) that computes score for a list.
Each adjacent pair of list elements L[i],L[i+1] can be replaced by element produced by the function COMBINE(L[i],L[i+1]). This operation can be repeated recursively, further shortening the list.
COMBINE is associative and commutative, i.e. COMBINE(A, COMBINE(B, C)) == COMBINE(COMBINE(A, B), C) and COMBINE(A, B) == COMBINE(B, A)
Given list L and functions SCORE/COMBINE, we need to find best score that can be reached on L or any its reduction.

So, as an example, if I have the list [A, B, C, D], all of these options are to be considered: (AB denotes the combination of A and B):

[A, B, C, D], [A, B, CD], [A, BCD], [A, BC, D], [AB, C, D], [AB, CD], [ABC, D], [ABCD]

Two obvious options include brute force (thanks, no) and a greedy algorithm, which would go roughly as follows in pseudocode Python:

def greedily_combine( elements, combine, score ):
    i = 0
    combine_success = False
    while i < len( elements ) - 1:
        combine_candidate = [combine( elements[i], elements[i+1] )]
        sublist_to_consider = elements[0:i+1]
        combined_score = score( combine_candidate )
        uncombined_score = score ( sublist_to_consider )

        if ( combined_score < uncombined_score ):
            elements.pop(0)
            elements.pop(0)
            elements.insert(0, combine_candidate)
            combine_success = True
        else:
            i += 1
            if i == len( elements ) - 1:
                i = 0
                combine_success = False

    return elements

However, this is almost certainly not going to be optimal. Is there a known general solution? If not, how could I have seen this myself, and is my greedy search good or easily improvable?

In your formulation, you need to compute score of each reduced list individually. So, if there are 2^(n-1) possible reduced lists, you need to perform at least O(2^n) operations.

Unless you can figure out some restrictions or relations between scores of related lists (such as "longer lists always have better scores"), it will remain O(2^n) problem.


Computer Networks: Does integrity depend on confidentiality? I'm taking the course computer networks and we currently had our second lecture. We got the following question:

  What are the differences between integrity and confidentiality of a message? Is confidentiality possible without integrity? What about integrity without confidentiality? Explain.

From what I understand the main difference between confidentiality and integrity is that "confidentiality" should prevent from spying on the message / intruders. And "integrity" is to ensure that the original message hasn't been altered in any way (modification/deletion/insertion).

What I'm unsure about: Does confidentiality mean that a possible interuder can't decode the ciphertext, or does this mean he can't even intercept the cipher?

To the two questions about the dependecies of integrity and confidentiality:
At first I thought: If an intruder can't intercept the message (break confidentiality), there's no way he can alter the message in any way (break integrity). But the more I think about that, the less certain I become. Especially when I think about deletion of a message.

Thanks a lot in advance for clearing things up.

  P.S: I hope "confidentiality" and "integrity" are the right terms in English. We learned "Vertraulichkeit" & "Integrität" in German.

Confidentiality means that only the sender and receiver know the message. We ensure confidentiality by encrypting the message.

Integrity roughly means that the message being sent cannot be modified in transit. In more detail, it means that there is a way for the receiver to check that the message has not been tampered with. We ensure integrity by adding a hash or checksum to the message.

The two properties are completely independent:

Confidentiality without integrity: Suppose I am sending you a cryptographic key, encrypted using a key we share. An attacker replaces the message with garbage having the same format. You will not notice any difference. The attacker has no way to read the original message, but they can modify it without you knowing it.
Integrity without confidentiality: I can send you a signed message by encrypting a hash of the message using my private key. Anybody can verify that the hash matches the message using my public key, but I'm the only person who can sign it. There is no way to modify the message without invalidating the signature, but the message itself is free for all to see.


Decidability of directed strongly connected graphs Consider the problem of determining if a directed graph is strongly connected.
How to phrase it as a language and prove that it's decidable.
My Thoughts :
To think of decidability given a graph I could run DFS on each node and see that all the nodes
are reachable from the original node. So it can be determined if the graph is strongly connected
in polynomial time.
But I am confused about the formal automata definition of decidability. Which says a language is
decidable if there is a Turing machine such that this language is the one exactly accepted by the
Turing machine. Now given the above logic of DFS is that enough to prove decidability
or does one have to build a turing machine ?

Yes, the DFS is an algorithm, and hence has an equivalent turing machine. The definition of the decidability as you have said, is for the language to be exactly accepted by some turing machine.
The formal definition of the turing machine accepting the language of strongly connected graphs probably is waaaay too hard to explicitly write, so I guess your teacher meant for you to show an algorithm and state that an algorithm is equivalent to a turing machine.
Btw, as a side note, you can run DFS only twice in total instead of $n$ times - once per node. If you have free time, its a good exercise in algorithms :)


Algorithm to find non-overlapping intervals that minimize standard deviation I am looking for the name of an algorithm category, or even specific algorithms, that solve the following problem.

I have noisy data.  For simplicity, let this data be represented by numbers.  I have the full data set in RAM.  In this noisy data, I want to find signal.  Signal is an interval of contiguous numbers that are close-enough to each other.  In other words, their standard deviation is below some threshold.  At the same time, I don't trust the signal if it is too short-lived, so it must be at least n contiguous numbers long.

In other words, I want to find non-overlapping intervals of values, where each interval has at least n values, and those values have a standard deviation of at most sd.

The intervals do not need to be contiguous.  (Signal is intermittent in all the noise.)

I want to minimize sd in these intervals, so given a choice of one interval with a higher sd or two intervals with a lower sd, I prefer the latter. (As long as both intervals have at least n values, as I said earlier.)

For example, suppose I configure a minimum interval size of 5, and I have the following list:

  7, 7, 8, 7, 7, 4, 5, 5, 5, 4, 6, 6

The sd for this whole interval is 1.31. If we split it into

  7, 7, 8, 7, 7

then drop the middle 4, and continue to the next interval,

  5, 5, 5, 4, 6

then drop the final 6, we get sd of 0.45 and 0.71, which intuitively seems optimal to me.

Had we kept the middle “4” in the second interval, that interval’s sd would have been 0.82. Had we kept the final “6”, that interval’s sd would have been 0.76. We could have decreased sd even further by removing more elements, except intervals in this example must have at least 5 elements.

(Note, I came up with this particular split intuitively, so it may not be the optimal split.)

What algorithm(s) can solve this problem?

Let the $n$ numbers be $x[1..n]$, and the minimum interval size $k$.

Formulating an objective function

There's a conflict here between two goals: Reporting more intervals will often mean reporting worse intervals.  We need an unambiguous way to decide which set of intervals is "best".  A good way to resolve this is by assigning some score value to any interval that includes two terms: a positive term (perhaps dependent on the length), as well as a negative term for the "quality" (here, standard deviation).  The goal is now to choose a set of nonoverlapping intervals that maximises the sum of scores.  For example, we could say that the score $s(i, j)$ of the interval $i..j$ is $10 + j - i - 7*StdDev(x[i..j])$.

A quadratic-time dynamic programming algorithm

The following dynamic programming algorithm takes $O(n^2)$ time and $O(n)$ space to find a solution having optimal score (there may in general be more than one such), and works for any scoring function $s$ that depends only on the beginning and end positions of the given interval (so you may certainly tweak my example function until you get results that look good).  It seems likely to me that a faster (linear or at least log-linear) algorithm exists for simple scoring functions, but in any case the following is flexible and will certainly handle $n$ up to 10000 in well under a second on any modern-day computer.

For any $1 \le i \le n$, let $f(i)$ be the maximum sum of scores achievable by any set of nonoverlapping intervals on the subproblem consisting of just the first $i$ elements of $x$.  So in particular, $f(n)$ will be the maximum sum of scores achievable on the entire dataset.  For now, let's imagine that we have an algorithm to compute $f(i)$, and use that to compute a related quantity for an "end-inclusive" variant of the problem: let $g(i)$ be the maximum sum of scores achievable by any set of nonoverlapping intervals on the subproblem consisting of just the first $i$ elements of $x$ that places the final ($i$-th) element inside an interval.  We can compute $g(i)$ as follows:

$g(0 \le i < k) = -\infty$

$g(i \ge k) = \max_{0 \le j < i}(f(j) + s(j+1, i))$

The first equation expresses that there can be no valid end-inclusive solution if there are fewer than $k$ items in total.  Using negative infinity is essentially a trick to ensure that this value is "ignored" by any $\max$ expression it happens to find itself in.  You wouldn't need to actually represent negative infinity in a program; any sufficiently large negative number would work.

The second equation says that we can always form an optimal solution to the length-$i$ end-inclusive subproblem by taking an optimal solution to some length-$j$ subproblem (which may or may not be end-inclusive), and appending a final interval to it containing every element after the $j$-th, up to the $i$-th -- specifically, whichever choice of $j$ yields the highest combined score.  This is the core insight of the algorithm; it's worth taking the time to convince yourself that this is really true.

From here, it's simple to compute $f(i)$:

$f(0) = 0$

$f(i \ge 1) = \max \{g(i), f(i-1)\}$

The first equation is obvious.  The second says that we can always form an optimal solution to the length-$i$ unrestricted subproblem by taking either the optimal solution to the corresponding end-inclusive variant of this subproblem (which puts $x[i]$ in an interval), or an optimal solution to the one-shorter unrestricted subproblem (which doesn't) -- whichever has higher score.  Again, it's worth checking that this is indeed true.

Memoisation

You can turn each of the above equations into program code to get a working, but exponential-time recursive program that can calculate $f(n)$, the maximum score achievable.  To speed this up to quadratic time only requires not recomputing answers to subproblems that we have seen before.  This can be as simple as using an array $m[0..n]$, initially filled with some placeholder value like -1, to record answers just before you return them: When $f(i)$ is called, we first check whether $m[i]$ contains a non-placeholder value, and if so immediately return that.  This approach to dynamic programming is called memoisation (that's right, there's no "R" in there).

Actually computing a solution

You may have noticed that until now, the things we have been computing ($f(\cdot)$ and $g(\cdot)$) are not actual solutions to the problem but just the scores of those solutions.  Fortunately, an actual solution can be recovered without much effort using a technique called traceback.

The key idea is that $\max$ function evaluations encode the "decisions" made by the algorithm.  We start at the end with the final total score value $f(n)$, which we know to be optimal, and work backwards, at each step determining which argument to a $\max$ function "won" (was highest): this tells us which subproblem to consider next, and (implicitly) describes one piece of the optimal solution.  (Actually there may be multiple highest-equal arguments to a $\max$; convince yourself that choosing any of them will lead to an optimal solution.)  We must do this for both $f$ and $g$.

For example, suppose that $n=1000$ and that in the very first step we have $f(1000)=150$.  From looking at the second equation defining $f$, our first question is whether this 150 value arose from $g(1000)$ (indicating that $x[1000]$ is in an interval) or from $f(999)$ (indicating that it isn't).  Suppose $g(1000)=150$ and $f(999)=133$: then the former wins, so it must be that $x[1000]$ is in an interval in every optimal solution.  The next step is to determine which $j$, in the range 0-999, gave rise to the value $g(999)=150$; this will implicitly tell us the length of this final interval, and provide the next subproblem to consider.

Often tracing back is sped up by storing the index of the "winner" in an extra array during the initial forward pass, but it can also be accomplished by recomputing the $f(\cdot)$ or $g(\cdot)$ function value at each step during the backward pass (which is slower, but not asyptotically so).


Difficulty in understanding the proof of the lemma : "Matroids exhibit the optimal-substructure property" I was going through the text "Introduction to Algorithms" by Cormen et. al. where I came across a lemma in which I could not understand a vital step in the proof. Before going into the lemma I give a brief description of the possible prerequisites for the lemma.

Let $M=(S,\ell)$ be a weighted matroid where $S$ is the ground set and $\ell$ is the family of subsets of $S$ called the independent subsets of $S$. Let $w:S\rightarrow\mathbb{R}$ be the corresponding weight function ($w$ is strictly positive).
Let us have an algorithm which finds an optimal subset of $M$ using greedy method as:

$\text{G}{\scriptstyle{\text{REEDY}}}(M,w):$
$1\quad A\leftarrow\phi$
$2\quad \text{sort $S[M]$ into monotonically decreasing order by weight $w$}$
$3\quad \text{for each $x\in S[M]$, taken in monotonically decreasing order by weight $w(x)$}$
$4\quad\quad \text{do if $A\cup\{x\} \in \ell[M]$}$
$5\quad\quad\quad\text{then $A\leftarrow A\cup \{x\}$}$
$6\quad \text{return $A$}$

I was having a problem in understanding a step in the proof of the lemma below.

Lemma: (Matroids exhibit the optimal-substructure property)
Let $x$ be the first element of $S$ chosen by $\text{G}{\scriptstyle{\text{REEDY}}}$ for the weighted matroid $M = (S, \ell)$. The remaining problem of finding a maximum-weight independent subset containing $x$ reduces to finding a maximum-weight independent subset of the weighted matroid $M' = (S', \ell')$, where
$S' = \{y\in S:\{x,y\}\in \ell\}$ ,
$\ell' = \{В \subseteq S - \{x\} : В \cup \{x\} \in \ell\}$ ,
and the weight function for $M'$ is the weight function for $M$, restricted to $S'$. (We call $M'$ the contraction of $M$ by the element $x$.)

Proof:

If $A$ is any maximum-weight independent subset of $M$ containing $x$, then $A' = A - \{x\}$ is an independent subset of $M'$.

Conversely, any independent subset $A'$ of $M'$ yields an independent subset $A = A'\cup\{x\}$ of $M$.

We have in both cases $w(A) = w(A') + w(x)$.

Since we have in both cases that $w(A) = w(A') + w(x)$, a maximum-weight solution in $M$ containing $x$ yields a maximum-weight solution in $M'$, and vice versa. ■

I could understand $(1),(2),(3)$. But I could not get how the line $(4)$ was arrived in the proof from $(1),(2),(3)$, especially the part in bold-italics. Could anyone please make it clear to me?

The adjective "maximum-weight" should not appear in item (1) in that proof of the lemma. This is a minor bug of that famous book.
To be fully clear, item (1) should have been the following.

If $A$ is any independent subset of $M$ containing $x$, then $A' = A - \{x\}$ is an independent subset of $M'$.

With item (1) corrected, item (4) follows naturally from item (1), (2) and (3). Here is more detail.

"A maximum-weight solution in $M$ containing $x$ yields a maximum-weight solution in $M'$."
Note that "solution" is just a shorthand for "independent set". Let us prove the proposition above.
Suppose $A$ is a maximum-weight solution in $M$. Then $A$ yields $A'=A-\{x\}$, which is a solution in $M'$ according to item (1). (The previous version of item (1) works as well.)
Given any solution $B'$ in $M'$, let $B=B'\cup\{x\}$, which is a solution in $M$ according to item (2).
Item (3) tells us $w(A)=w(A')+w(x),$ and $w(B)=w(B')+w(x).$ Since $A$ has maximum weight in $M$, we have $w(A)\ge w(B)$, i.e.,
$$w(A')+w(x)\ge w(B')+w(x).$$
Cancelling $w(x)$ from both sides, we obtain
$$w(A')\ge w(B'),$$
which says $A'$ is a maximum-weight solution in $M'$. $\checkmark$

A maximum-weight solution in $M'$ yields a maximum-weight solution in $M$ containing $x$.
The other direction, as stated above, can be proved similarly. Here is the proof.
Suppose $B'$ is a maximum-weight solution in $M'$. Then $B'$ yields $B=B'\cup\{x\}$, which is a solution in $M$ according to item (2).
Given any solution $A$ in $M$, let $A'=A-\{x\}$, which is a solution in $M'$ according to (the corrected version of) item (1).
Since $B'$ has maximum weight in $M'$, we have $w(B')\ge w(A')$. Adding $w(x)$ to both sides, we obtain,
$$w(B')+w(x)\ge w(A')+w(x).$$
Item (3) tells us $w(A)=w(A')+w(x),$ and $w(B)=w(B')+w(x).$  So the inequality above is the same as
$$w(B)\ge w(A),$$
which says $B$ is a maximum-weight solution in $M$. $\checkmark$


How to prove that every regular language can be obtained by some FA? I have seen this definition almost everywhere, but I don't know the underlying proof behind this definition.

These definitions are from Wikipedia

In theoretical computer science and formal language theory, a regular
language is a formal language that can be expressed using a regular
expression...
...
Alternatively, a regular language can be defined as a language
recognized by a finite automaton.

You can define a regular language as a set of strings accepted by some  FA. In this case you don't have to prove anything since a regular language is recognized by a finite automaton by definition.
But if you define a regular language as a formal language that can be expressed using a regular expression then you can prove that it is accepted by some FA using Thompson construction, i.e. prove the equivalence of regular expressions and finite automata.


Why are forks in the Blockchain eventually resolved? I'm reading Wattenhofer's The Science of the Blockchain. On page 87, he states the following thoerem:

Theorem 7.22. Forks are eventually resolved and all nodes eventually agree on which is the longest blockchain. The system therefore guarantees eventual consistency.
Proof. In order for the fork to continue to exist, pairs of blocks need to be found in close succession, extending distinct branches, otherwise the nodes on the shorter branch would switch to the longer one. The probability of branches being extended almost simultaneously decreases exponentially with the length of the fork, hence there will eventually be a time when only one branch is being extended, becoming the longest branch.

I don't quite understand why the probability decreases exponentially. I think it's quite probable that they happen at the same time, if not that the malicious block is faster and waits.

If we simplify and assume that each miner randomly guesses a hash (as opposed to being more systematic) and we discretize time, say into minutes, then each minute each miner is hoping to "roll" the right number. Let's say there are $N > 1$ possible values only one of which is correct at each minute. Then, in a world with only two miners, each minute there is only a $\frac{1}{N^2}$ chance that both miners will roll the correct value. There's a $1-\frac{3}{N^2}$ chance that neither miner rolls the correct value. There is a $\left(1-\frac{3}{N^2}\right)^k\frac{1}{N^2}$ chance that both miners roll the correct value after exactly $k$ steps of both not rolling the correct value. The probability that they will both roll the correct value for the first time at the same time is then $$\sum_{k=0}^\infty\left(1-\frac{3}{N^2}\right)^k\frac{1}{N^2} = \left(\frac{1}{1-\left(1-\frac{3}{N^2}\right)}\right)\frac{1}{N^2} = \frac{1}{3}$$

So the odds of them rolling the correct value at the same time $m$ times in a row is $\frac{1}{3^m}$. With more miners, birthday problem aspects enter, but that won't change the exponential nature. (In fact, I don't think the birthday problem really comes into play since each miner still needs to get the correct value not just a value that matches another miner's.)

I'm pretty sure this is the idea the author had in mind. As you say, though, a malicious miner (a selfish miner) can withhold announcing blocks until they notice someone else announcing them. To account for that, you could instead consider (in the two miner world again) what the probability is that the malicious miner finds a block before the honest miner. If the miners are comparable, then that's presumably something like $\frac{1}{2}$. However, things are further complicated by the fact that when the malicious miner does find the correct value first, then that miner also gets a head start on finding the correct value for the next block. Nevertheless, for comparable miners, there is still a good chance that the honest miner will find a block first despite the malicious miner's head start. This reasoning starts to get into the selfish mining aspect I referenced in the comments.


Is Carry Look-Ahead adder used in modern ALUs? I recently came across carry look-ahead adder(CLA) in David and Sarah Harris's book(Digital Design and Computer Architecture). The circuitry for a 64 bit number (standard integer size in C) is probably huge and gets very complicated.The generate function has just too many gates.

My question is: are CLAs used in current processors such as the Intel i3 or in similar series? Also, are there any better implementations of carry adders?

I am aware of the fact that older processors like the Intel 8008 and the kind did use a CLA.

“Huge and complicated” is no problem, as long as it is fast. It isn’t.

A good choice seems to be a conditional sum adder (CSA) which has a total delay of O(log n) gates. Log n is nice for 64 bit adders.


Given a set of numbers, get the maximum 10 number average below a certain threshold As an input, my program accepts a big set of numbers (often times more than 30) and a maximum threshold. I'm trying to get the maximum average between 10 of those numbers below that threshold (the numbers used in that average are also returned).

Right now, I'm testing all 10 number combinations, recording them and their average in a list and getting the maximum average from that list.

As you know, though, when the set becomes too big (usually around 30 numbers), the time period the program takes to execute gets much larger, often way too large to be usable.

What would be an algorithm that cuts down on execution time, while achieving the same (or approximate) result?

EDIT: numbers are floats between 0 and 1.

Looking for a maximum average $m$ below a threshold $m_{max}$ is the same than looking for a maximum sum $s$ below a threshold $s_{max}$. If you have to select $k = 10$ numbers among $N$, you have:

$s_{max} = k \times m_{max}$

now the question looks like a Knapsack problem with a forced number of selected items $k$. You can use a DP solution closed to the one solving Knapsack. I also assume $s_{max} > 0$ and all available numbers are strictly positives. Note, that you may apply a simple offset on all numbers and $m_{max}$ if any is negative.

Let's build a $k\times s_{max}$ array $A$ with $A[i, j]$, the index of the last number selected to have $i$ selected values for a total of $j$. $A$ is initially filled with an "null" value.

Then the pseudo algorithm is:

for n from 1 to N:
    v = n-th available value
    for i from k-1 to 1:
        for j from smax-v to 1:
            if A[i, j] is not null and A[i+1, j+v] is null then:
                A[i+1, j+v] = n
    if A[1, v] is null:
        A[1, v] = n

The best sum you can obtain is the last $A[k, j]$ which is not null. Using the index in $A$, you can backtrack the subset. Note that $i$ and $j$ loops go backward, to be sure the same value is not used twice.

Complexity is $O(Nks_{max})$ in time and $O(ks_{max})$ in space.

If $s_{max}$ is large and $N$ quite small, a (key, value) structure (in fact $k$ of these structures) instead of $A$ may be much more efficient as you won't have to loop on all empty values.


Proving that a specific grammar is ambiguous How can I prove that the following grammar is ambiguous:

$$ A \to AA\mid B  \\  B \to aBb\mid ab $$

I tried finding a string that can be derived in two different ways, but to no avail.

The word $ababab$ can be derived in two different ways.

If you don't see why, I suggest starting with the simpler grammar $A \to AA|a$.


Transforming undirected maximum spanning tree into directed augmented network I am having trouble transforming a maximum weighted spanning tree into a directed tree such that each node is allowed at most one parent node. Taken from page 141 Friedman et. al (1997), the outline of the algorithm is as follows:

1) Compute $I_{\hat{P}_{D}}(X_{i};X_{j})$ between each pair of variables $i \neq j$ where $$I_{\hat{P}_{D}}(X_{i};X_{j}) = \sum_{x,y} P(x,y) log\left(\frac{P(x,y)}{P(x)P(y)}\right)$$
2) Build a complete undirected graph in which the vertices are the variables in $X$. Annotate the weight of an edge connecting $X_{i}$ to $X_{j}$ by  $$I_{\hat{P}_{D}}(X_{i};X_{j})$$
3) Build a maximum weighted spanning tree

4) Transform the resulting undirected tree to a directed one by choosing a root variable and setting the direction of all edges to be outward from it.

I have done steps 1-3, my trouble is on step 4. As of right now I have a set of names of continuous variables $X = \{x_{1}, x_{2}, \ldots, x_{n} \}$ and a $(from , to)$ matrix of the form
$$
\begin{bmatrix}
x_{1}&x_{10}\\x_{3}&x_{7}\\ \vdots& \vdots
\end{bmatrix}
$$
For example in the undirected maximum weighted tree, there's an edge going from $x_{1}$ to $x_{10}$ and so forth (note that this could have easily been read as an edge from $x_{10}$ to $x_{1}$ because as of right now the graph is undirected). I understand exactly what's going on I'm just unsure how to actually program it. If somebody could give me a pesduocode-type overview of how I should go about implementing step 4 it would be much appreciated. If someone could provide a link to a detailed implementation of this algorithm that would be fine as well. This is my first post on stackexchange, please forgive me if I have not provided enough information or posted this question in the incorrect location.

Given an undirected tree, pick any node (it doesn't matter which one).  Call that the root.  Now do depth-first search (or breadth-first search, or any other kind of search) starting from the root, traversing only the edges of the tree.  That will visit all the vertices and edges.  When you visit an edge for the first time, it will always be in an "outward" direction, so now you know how to orient it (how to set its direction).

Work through a small example if this is still unclear.


Algorithms that run in polynomial time if P=NP On Wikipedia, it says that that there are some algorithms that would run in polynomial time if and only if P=NP. They gave one example (without citation), but are there any others? I tried looking them up and couldn't find any.

Wikipedia is describing Levin's universal algorithm. This is an algorithm for verifiable problems, which is competitive with the optimal algorithm (in some sense). In particular, the exact same approach would work for any problem in NP, not just SUBSET-SUM.