In syntax-directed definition, terminals are assumed to have synthesized attributes only, definition doesn't provide any semantic rules for terminals? I was going through the text Compilers: Principles,Techniques and Tools by Ullman et. al. where I came across the claim in the question by authors. Below is the definition and following it is the claim by the authors.

Form of a Syntax-Directed Definition
In a syntax-directed definition, each grammar production $A\rightarrow \alpha$ has associated with it a set of semantic rules of the form $b := f(c_1, c_2, . . . , c_k)$ where $f$ is a function, and either

$b$ is a synthesized attribute of $A$ and $c_1, c_2, . . . , c_k$ are attributes belonging to the grammar symbols of the production, or

$b$ is an inherited attribute of one of the grammar symbols on the right side of the production, and $c_1, c_2, ... , c_k$ are attributes belonging to the grammar symbols of the production.

Claim:
In a syntax-directed definition, terminals are assumed to have synthesized attributes only, as the definition does not provide any semantic rules for terminals. Values for attributes of terminals are usually supplied by the lexical analyzer.

That values of the terminals is provided by the lexical analyzer is a usual practice.(Which makes us assume that terminals have synthesized attributes usually). But cannot understand their claim, with the logic that the definition does not allow it. Going by point $2$ in the definition:
$b$ is an inherited attribute of one of the grammar symbols on the right side of the production: so the right hand side of a production might as well contain terminals, making $b$ an inherited attribute of a terminal.
The point $1$ applied to $b$ which is an attribute of a symbol(non terminal) on the LHS and only point $1$ talks about synthesized attributes, so $1$ makes no provisions for attributes for the non terminals. Hence there is no provision of synthesized attributes for the terminals.
Is this something like this?

It's not a claim; it's a definition. In mathematics, we can define things however we want.  [See Note 1]
Our only obligation is to make sure we've shared the definition with our readers.
In any event, it doesn't make the slightest difference. If we want to define an inherited attribute for a terminal, we can just replace the terminal throughout the grammar with a non-terminal with a single production whose right-hand side consists only of the terminal. Then the surrogate non-terminal can carry whatever attributes we want it to carry.
This transformation does not in any way affect the parse (provided it is done consistently throughout the grammar).

Notes

It's not a coincidence that Lewis Carroll was a mathematics professor.


Understanding access and insertion time of arrays Why do most implementations of arrays have constant access time and linear insertion time?

Because they are using the pointer to access to an index of the array, hence the access time is constant. Moreover, as indices of the array are stored beside each other (to access in constant time), insertion to the array needs to extend the allocated storage of the array to insert a value, and it needs to copy all values of the array to the newly allocated storage with size $n + 1$. Hence, insertion of the array is $O(n)$ in most of the implementations.

To know more about this, you can seek around "dynamic array" for constant access time and amortized $O(n)$  for $n$ insertion.


What is the difference between "strict schedule" and "cascadeless schedule"? In database transactions theory, what is the difference between a strict schedule and a schedule that is merely secured against cascade aborts?

Could you give an example of a schedule that is secured against cascade aborts but is not strict?

I found these slides that give definitions but it's still not clear to me where is the difference (they just seem differently worded).

On a cascadeless schedule a transaction $T_2$ cannot read a value $a$ if a transaction $T_1$ wrote $a$ before that and didn't commit. On a strict schedule $T_2$ also wouldn't be able to write $a$ after $T_1$ wrote it (even if it read $a$ before $T_1$ wrote it).

If you read carefully, the definition of strict says "not read or overwritten". That's the difference.

I reproduce here an example of cascadeless but not strict schedule, from the Wikipedia page on the subject:


Finding lower bounds for data structures with non-standard interfaces Consider the problem of designing a data structure that provides the interface functions  $\rm{pop}, \rm{push}, \rm{findmin}$, all running in constant time. This problem may be solved by (e.g.) having the $\rm{push}$ method compute the new minimum as well, and place it on the stack together with the pushed element.

Is there any systematic approach to determining lower bounds (of time and space complexity) for data structures exposing a given set of interfaces? E.g. $\rm{push,pop,sort, insertAtIndex}$? Can you provide links to relevant literature?

Data structure lower bounds is a full-fledged area in theory of computation. The main model of computation on which the lower bounds are proved is the cell probe model, which counts the number of memory accesses, but for which computation is free. For an overview of how things stood in 2008, you can take a look at Mihai Pătraşcu's thesis. Tragically, Pătraşcu died from brain cancer in 2012 at the age of 29.


How does quicksort with 3-way partitioning ~ $(2 ln 2) NH$ become linear time complexity with many duplicated keys? From Algorithms 4th:

  Quicksort with 3-way partitioning uses ~$(2\ln 2)NH$ compares to sort $N$ items, where $H$ is the Shannon entropy, defined from the frequencies of key values.

$ H = -(p_{1}\log_{2}{p_1} + p_{2}\log_{2}{p_2} + .... + p_{k}\log_{2}{p_k}) $

  Given $N$ keys with $k$ distinct key values, for each $i$ from $1$ to $k$ define $f_{i}$ to be frequency of occurrence of the $i$-th key value and $p_{i}$ to be $f_{i} / N$, the probability that the $i$-th key value is found when a random entry of the array is sampled.

How does $(2 \ln 2)NH$ become linear when there are many duplicated keys?

So does it mean that I need to prove:

$H$ is a constant (or should I say have a upperbound ?), and not related to $N$, when there are many duplicated keys.

Basically yes and slightly no.

The purpose of the quoted paragraphs is to summarize the improvement of quicksort with 3-way partitioning over the basic quicksort (with Hoare partition scheme) in the case of many duplicated keys. The root cause of the improvement is simple, "every item encountered leads to an exchange except for those items with keys equal to the partitioning item’s key". The quantification of the improvement is given by that formula involving the Shannon entropy.

  How does $(2\ln2)NH$ become linear when there are many duplicated keys? So does it mean that I need to prove: $H$ is a constant (or should I say have a upper bound ?), and not related to $N$, when there are many duplicated keys.

I would turn the question around.

How can we define "many duplicated keys"? The book Algorithms chooses to mention this concept casually, probably in an attempt to make the situation sounds immediately familiar to the widest audience at the expense of some rigor.

In fact, the more applicable and rigorous concept should be "stable discrete distributions", i.e., the distribution of all discrete key values stays roughly the same, which is somewhat more technical but still within reach of most of targeted audience of that book. Note that entropy of a multi-set is determined by the frequencies of all values appearing in the multi-set, as explained in the last paragraph quoted in the question. If the distribution of all key values stays the same, the entropy of a sample array viewed as a multi-set will be roughly the same regardless of the sample size. When sample size goes larger and larger, there will be more and more duplicate keys in the sense of the sum of duplicities. For example, if the probability of some key $k$ is 0.2, then there is likely about 20 items with key $k$ when the sample size is 100 and there is likely about 200 items with key $k$ when the sample size is 1000. That is the meaning of "many duplicate keys" here.

In other words, we could simply define "many duplicated keys" by "the same entropy regardless of the size $N$". Then there is, actually, nothing for you to prove once you have agreed that "Quicksort with 3-way partitioning uses $\sim(2\ln2)NH$".

Or, we could try to prove the following more precise proposition.

  It will take quicksort with 3-way partitioning approximately $(2\ln2)NH$ time on average to sort an array of size $N$ that comes from sampling a discrete distribution with entropy $H$, where $H$ is a constant and $N$ goes to infinity.

The following excerpt of the book implies the explanation above implicitly. The boldface is added by me.

  As with standard quicksort, the running time tends to the average as the array size grows, and large deviations from the average are extremely unlikely, so that you can depend on 3-way quicksort’s running time to be proportional to N times the entropy of the distribution of input key values. This property of the algorithm is important in practice because it reduces the time of the sort from linearithmic to linear for arrays with large numbers of duplicate keys. The order of the keys is immaterial, because the algorithm shuffles them to protect against the worst case. The distribution of keys defines the entropy and no compare-based algorithm can use fewer compares than defined by the entropy. This ability to adapt to duplicates in the input makes 3-way quicksort the algorithm of choice for a library sort—clients that sort arrays containing large numbers of duplicate keys are not unusual.

My explanation above suffers the same weakness of ambiguity as the book, although on a slightly different level, since I would also like my explanation to be understood by widest audience easily with least amount of expense of rigor. Hopefully, I have made the point clearly enough so that readers should be comfortable enough to believe he/she has understood the relevant idea in the book.

Assume the Proposition N of the book, which is the first paragraph of this question.

Exercise. Given a constant positive integer $m$, it will take quicksort with 3-way partitioning approximately less than $2N\ln2\log_2m$ time to sort an array of size $N$ whose number of distinct elements is $m$. (Hint, maximum entropy with $m$ possible values is obtained with uniform distribution.)


What is the time-complexity of histogram computation? Suppose I have an Image $I$ of $n\times m$ (or a matrix), I would like to compute its histograms in a loop.

Pseudocode:

for i=1:s1:n
      h = hist(I(i:i+s1,m),bins)
end

$I$ is a  matrix (or an image of data). When we say, $I(i:i+s1,m)$ we take the block of the matrix that starts in row from $i$ to $i+s1$ and have $m$ elements in columns.

hist is a function that counts the number of elements in its first parameters and store that number in its $bins$. For example : $hist([1,2 ,1 ,1 ,3],3)$ is equals to $[3, 1, 1]$ because there is three elements of $1$ and just one elements of $2$ and $3$. $hist$ computes the frequency of an element.

So if I understand well ... the time-complexity of this simple algorithm is $O(n/s1) * TC(hist)$.

With the $TC(hist)$ the time-complexity of histogram computation. Since $s1$  is constant. I can deduce that TC of the algorithm is $O(n)*TC(hist)$.

If we use a hash table of size $bins$, (it is a memory, so it won't impact the time complexity). We will have to browse the $s1\times m$ part of the image. So the $TC(hist)$ is equal $O(s1*m)$.

I don't know how to link $O(s1*m)$ to the $n$ and $m$. Is $TC(hist)$ linear following $m$ so equals $O(m) $ since $s1$ is a constant ?

please, check if my reasoning is correct ? and what is the global time-complexity ? do we take in consideration the memory usage in the computation of time-complexity ?

Presumably the time complexity of the function hist applied to data of length $N$ and to $B$ bins is $O(N+B)$ (the exact definition of $B$ depends on the implementation of hist; in your case, it seems to be the maximum of the input). In your case, each of the $n/s_1$ iterations of the loop is applied to data of length $s_1 m$, and so the total running time is
$$ \frac{n}{s_1} O(s_1m + B) = O(nm + \frac{n}{s_1} B). $$
The answer that your teacher expects is $O(nm)$.


When are multiple CPU's needed? Forgive me if I'm asking something that should be obvious, my experience is with software development, not computer science.  I've glanced at some articles on hyperthreading and parallel processing, but it seems like those implementations are primarily for consumer devices to persist multiple apps at the same time (listen to a music app while browsing the internet) but for non consumer implementations where there is only one primary process, like a VM exclusively used for tensorflow, would there be any benefit to the VM having additional CPU's?  There may be other OS processes going on with the VM, but the only way to calculate tensorflow faster would be to use a different hardware, like a GPU or a TPU, right?

As Wikipedia states,

  The improvement in performance gained by the use of a multi-core processor depends very much on the software algorithms used and their implementation. In particular, possible gains are limited by the fraction of the software that can run in parallel simultaneously on multiple cores; this effect is described by Amdahl's law. In the best case, so-called embarrassingly parallel problems may realize speedup factors near the number of cores, or even more if the problem is split up enough to fit within each core's cache(s), avoiding use of much slower main-system memory. Most applications, however, are not accelerated so much unless programmers invest a prohibitive amount of effort in re-factoring the whole problem.

Whether you'll see an improvement when running a particular software application depends upon how that software application is built, and whether it can make use of threads to parallelize computation.  Some can; others can't.

I don't know what the situation is for Tensorflow, but my impression is that Tensorflow tries to use your GPU if possible, because the GPU is far faster than the CPU at the kinds of tasks Tensorflow is designed for.  And, if Tensorflow is using your GPU, then there's little or no benefit to having a multiple-core CPU or multiple threads.

Parallelization can be useful for some tasks.  For instance, some video processing applications are designed to make use of multiple cores, so even if you're running only one application (the video editor application), it still runs faster with multiple cores than with a single core.  It's not just for running multiple applications at the same time.

See also https://superuser.com/q/153833/93541, https://superuser.com/q/2489/93541, https://superuser.com/q/453799/93541, and https://superuser.com/q/949030/93541 for more background.

Hyperthreading is best ignored until you understand the fundamentals of multi-core procoessors and multi-threaded applications.


Runtime of a recursive algorithm to find a path in a DAG About the following algorithm:

reach(Vertex s, Vertex t):
    if s = t return TRUE
    else
        for v in Adj(s) do
            if reach(v,t) return TRUE
        return FALSE

Why can we say that its runtime on a directed acyclic graph is $O(n!)$?

I can see why there are $n!$ different paths in the graph, is it because in each of those $n!$ paths, the loop will run at most $n$ times?

If you take each recursive call and trace it back to the original call reach(s,t) then you get some directed path starting at $s$. Hence the running time of the algorithm is $\Theta(N)$, where $N$ is the number of directed path starting at $s$ in which $t$ is not an internal vertex.

The number of paths of length $k$ (containing $k$ edges) is at most $(n-1)(n-2)\cdots(n-k)$, since each such path consists of distinct vertices different from $s$ (here we use the DAG property). Since paths have length between $0$ and $n-1$, we get that
$$
N \leq \sum_{k=0}^{n-1} (n-1)\cdots(n-k) = (n-1)! \sum_{k=0}^{n-1} \frac{1}{k!} \leq e(n-1)!.
$$
In particular, $N = O(n!)$.


Shortest path in weighted(positive or negative) undirected graph I have to find an algorithm that finds the SSSP (single-source shortest path - shortest paths from one source vertex to all other vertices) on a weighted undirected graph. If there are 2 different shortest paths, the algorithm should prefer the one with less edges on it. The time complexity of the algorithm is $O((|V|+|E|) \log |V|)$.

So, I tried:

My first thought was DFS/BFS (the $O(|V|+|E|)$ looks tempting), but (I believe) no modification of these two algorithms works on weighed graphs.
Then I thought about Dijkstra's algorithm - but that one doesn't work on graphs, which can have negative edges.
My last hope was Bellman-Ford algorithm, which could work I guess, but I have no idea, how to rewrite it for undirected graphs.

Any hint is appreciated.

A generic scheme to make an undirected graph directed is to replace each of its edges by two directed edges with same weight as the original weight of the edge. For an undirected edge $(u,v)$. Replace it by two directed edges $(u,v)$(direction u to v) and $(v,u)$(direction v to u). The weight of both of these edges are same as weight of undirected edge $(u,v)$.

Thus the algorithm which you have in mind for solving directed SSSP can also be applied on undirected graph with the above mentioned changes.

And, a good way to get a shortest path with smallest number of edges is to add a small constant weight ($\epsilon$) to all edges. Note that if we have two shortest path having $x$ and $y$ edges ($x > y$) before, then adding small value to all edges changes the weight of the shortest path with $x$ and $y$ edges by amount $x\epsilon$ and $y\epsilon$. As $x\epsilon > y\epsilon$, now the shortest path with $y$ edges is having lesser cost. Thus after changing the edge weight by a very small amount you can apply your favorite SSSP algo to get the path with minimum number of edges. Note that as $\epsilon$ is very small a path which was not shortest before can't be shortest after changing the weights.


Are there any techniques for checking whether a clause is subsumed by another clause when adding it to a cnf formula? When doing variable elimination on a formula in cnf form, there is created a lot of new clauses. Is there any efficient way to check if these are subsumed by other, already existing clauses?

There is a preprocessing method called vivification$^1$ that can be used to detect subsumed clauses.  It relies on unit propagation to work.

To vivify a clause, make a partial variable assignment such that all the proposed clause's literals are false.  E.g. if your proposed clause is $x_1 \lor \lnot{x_2} \lor x_3 \lor \lnot{x_4}$, assign $x_1$ = FALSE, $x_2$ = TRUE, $x_3$ = FALSE, and $x_4$ = TRUE.  If while you're doing these assignments unit propagation produces a conflict, or if one of the variables is set by unit propagation and vivification later wants to set it to a different value, then the new clause is implied by the existing formula and can be discarded as redundant.

$^1$"Vivifying Propositional Clausal Formulae" by Cédric PIETTE,
Youssef HAMADI and Lakhdar SAÏS


Ordered Cartesian Product Say I have three sets:

A = [banana, apple, grape]

B = [1, 2, 3, 4]

C = [Alice, Bob, Carol]

I need to design an algorithm that gives me the Cartesian Product A x B x C, but with any number of sets and any number of elements in each set. Another requirement is that the order of the elements in the Product is such:

A x B x C = [(banana, 1, Alice),
             (apple, 1, Alice),
             (banana, 2, Alice),
             (banana, 1, Bob),
              ...]

I could only come up with a recursive algorithm that ends up giving me:

A x B x C = [(banana, 1, Alice),
             (banana, 1, Bob),
             (banana, 1, Carol),
             (banana, 2, Alice),
              ...]

Obviously, A x B x C needs to have every possible combination of the elements of the sets. Also, I need an algorithm that covers the general case of any number of sets, not only three.
Is there any well-known algorithm that provides the Cartesian Product in this order that I need?

Any help or tips is much appreciated.

You want to enumerate first by sum, then by lexicographic order of some sort (it's impossible to tell which type exactly from your example). Replacing actual elements with indices, here is the order you're interested in for $A \times B$:
$$
(0,0) \\
(1,0), (0,1) \\
(2,0), (1,1), (0,2) \\
\ldots
$$
It's a simple exercise to generate this order for $A \times B$. Generating the order for $A \times B$ is somewhat more challenging, but still not too bad. When generating the triples summing to $n$, if we focus on just the first two parts of each pair, then we're interested in a list of all pairs $(i,j)$ such that $i+j \leq n$, in some sort of lexicographic order. Whichever variant of the lexicographic order you choose, you should be able to figure out how to generate it by looking at some examples.


Relation between $\sqrt{x^2+y^2}$ and $|x|+|y|$ I have a problem in which I was given $n$ points and an integer $k$, and I need to find the $k$ points that are the closest to origin. My approach is to find the distances from origin of all points and sort them. Instead of using distances $\sqrt{x^2+y^2}$, can I use $|x|+|y|$ as my key? Also, I would like to find out the complexity for both approaches.

The two notions of distance are not equivalent. That is, you can find a pair of points $p,q$ such that $p$ is closer to the origin with respect to the distance $\sqrt{x^2+y^2}$ (known as $L_2$), and $q$ with respect to the distance $|x|+|y|$ (known as $L_1$). An example is $p=(2,2)$ and $q=(3,0)$. However, you can simplify your task by considering $x^2+y^2$ instead of $\sqrt{x^2+y^2}$.

There is no need to sort the distances. Instead, you can use a comparison-based linear time selection algorithm.


Minimum cost problem of breaking containers in $O(n\log n)$ Can anyone kindly give me some hint on solving this?
There are $n$ water containers placed on the top of each other (container1 on top of container2, container2 on top of container3, ...), each with capacity $c_i$ and initial water $a_i$ ($a_i<c_i$).
In case of breakage of any container, all the water inside it will pour into the container below.
Each container will break if the water inside it is more than its capacity.
On the other hand, we can always break a container manually by paying the cost $p_i$.
Provide an algorithm to find the minimum cost to break the $n$th container in $O(n\log n)$.
Using a binary heap may be useful.

To solve this problem in $O(nlogn)$, We can use a min-heap.
Consider $s_i = \Sigma_{k=i}^{n}{a_k}$ and $b_i = s_i + c_i - a_i$. You can see that if $b_i - s_j < 0$ for $j < i$, by starting from $j$ and breaking every container from $j$ to $i$, container $i$ will break by the amount of water from the containers $j$ to $i$.
First set $cost = 0$ and $min = p_i$. Then do the following from $n$ to $1$:

Calculate $s_i$.
Calculate $b_i$.
Add $p_i$ to $cost$.
Add $b_i$ to the mean-heap and heapify it.
While $b_j - s_i < 0$ ($b_j$ is the root of the heap): Remove the root and subtract $p_j$ from $cost$.
If $cost < min$, update $min$.

At every container, we know that if we start from that container, we need to break some of them and the rest will break by the water. When we remove a container from the heap, we can be sure that if we start from that container, the removed container will break by itself, and the total cost will be to break the rest, so we can subtract the cost of breaking the removed container from the total cost.
Since the while loop is run once for each container, and the for loop runs n times, the total time will be $O(nlogn)$.


Does basic 2 PL always ensure conflict serializability? While going through the DBMS book by Korth, it was mentioned :

" For a set of transactions, there may be conflict-serializable schedules that
cannot be obtained through the two-phase locking protocol.

Does this imply that basic 2 PL ensures serializability but does not always ensure conflict serializability ?

No,

If you use 2PL protocol you are guaranteed to have a conflict-serializable schedule but there are conflict serializable schedules which may not honour 2 PL protocol i.e. locking data items in the growing phase and releasing them in the shrinking phase.


Data strucutre for finite graphs on a cylinder My problem is to find an efficient data structure that allows the encoding of a (non-directed) graph on the surface of a cylinder (without top and bottom discs).  Usually I would store a graph as a list of edges, which are pairs $(a,b)$ of vertices. My problem is that I can have two kinds of edge from $a$ to $b$ either by taking the shortest path or going around the cylinder. These two edges should be considered as being different.

My set of vertices is fixed ($n$ vertices on the top circle, $n$ vertices on the bottom circle of the cylinder) and I requires that, for any vertex, there exists precisely one edge to another vertex. Furthermore crossings of edges are not allowed (that is why it is important to be able of "going around" the cylinder; taking a "longer" way).

The aim then is to glue two such cylinders together (the bottom of one goes on the top of the other) and compute the connected components of the "glued" graphs, which will produce another graph on a cylinder.

Of course one could just tag the edges, depending whether one goes the shortest or longest way, but maybe someone has a better idea!?

Let the vertices at the top be $a_0, \dots, a_{n-1}$ and those at the bottom be $b_0,\dots, b_{n-1}$, both ordered, say, clockwise. If the graph has no edge-crossings, the edge set can only be $\{(a_i,b_{i+k})\mid 0\leq i\leq n\}$ for some $k$, with addition carried out modulo $n$. So the edge set is uniquely determined by the value of $k$.

Beyond that, though, it's not clear what you're asking. The embedding of the graph in the surface of the cylinder could be much more complicated than you're suggesting. For example, the edges could all spiral anticlockwise around the cylinder thirteen times. Or they could spiral anticlockwise three times, then clockwise four times, and then wiggle around lots. Perhaps you have a requirement that the edges can't spiral multiple times? And/or that they're straight lines if you "unwrap" the cylinder and lay it flat?  If so, note that gluing two cylinders together doesn't maintain this property: for example, if you glue the cylinder that has edges $(a_i,b_{i+1})$ using shortest paths to the cylinder that has edges $(a_i,b_{i-1})$ using shortest paths, you get a cylinder whose edges zig-zag, so aren't straight lines, don't use shortest paths and don't "go the long way around". Likewise, if you glue $2n$ copies of the cylinder that uses shortest paths to link $a_i$ to $a_{i+1}$, you get a cylinder whose edges spiral twice.


Solving a recurrence relation with √n as parameter Consider the recurrence

$\qquad\displaystyle T(n) = \sqrt{n} \cdot T\bigl(\sqrt{n}\bigr) + c\,n$

for $n \gt 2$ with some positive constant $c$, and $T(2) = 1$.

I know the Master theorem for solving recurrences, but I'm not sure as to how we could solve this relation using it. How do you approach the square root parameter?

In your comment you mentioned that you tried substitution but got stuck. Here's a derivation that works. The motivation is that we'd like to get rid of the $\sqrt{n}$ multiplier on the right hand side, leaving us with something that looks like $U(n) = U(\sqrt{n}) + something$. In this case, things work out very nicely:

$$\begin{align}
T(n) &= \sqrt{n}\ T(\sqrt{n}) + n & \text{so, dividing by $n$ we get}\\
\frac{T(n)}{n} &= \frac{T(\sqrt{n})}{\sqrt{n}} + 1 &\text{and letting $n = 2^m$ we have}\\
\frac{T(2^m)}{2^m} &= \frac{T(2^{m/2})}{2^{m/2}} + 1
\end{align}$$
Now let's simplify things even further, by changing to logs (since $\lg \sqrt{n} = (1/2)\lg{n}$). Let
$$\begin{align}
S(m) &= \frac{T(2^m)}{2^m} & \text{so our original recurrence becomes}\\
S(m) &= S(m/2)+1
\end{align}$$
Aha! This is a well-known recurrence with solution
$$
S(m)=\Theta(\lg m)
$$
Returning to $T(\,)$, we then have, with $n=2^m$ (and so $m=\lg n$),
$$
\frac{T(n)}{n} = \Theta(\lg\,\lg n)
$$
So $T(n) =\Theta(n\,\lg\,\lg n)$.


How can a Turing machine run another machine for an infinite amount of strings? The proof in my textbook, that $E_{TM}$ can be decided by oracle machine $O^{A_{TM}}$, uses a Turing machine $P$ such that for an input $w$:

$P$ runs the Turing machine $M$ on all strings of $\Sigma^*$
If $M$ accepts the string, $P$ accepts

$O^{A_{TM}}$ then asks the oracle if $<P,w> \in A_{TM}$

I can't seem to understand why $P$ can run $M$ for all strings of $\Sigma^*$ because this is an infinite amount of strings. I do, however, understand that $P$ actually never has to run and is purely constructed to ask the oracle if it accepts.

The technique is knows as dovetailing. The machine $P$ keeps a two-dimensional tape and uses the following algorithm:

Run $M$ on the first string for one step.
Run $M$ on the first two strings for one step.
Run $M$ on the first three strings for one step.
...

(We imagine that all possible strings are arranged in some arbitrary computable order, say $\Lambda,0,1,00,01,10,11,000,\ldots$.)

Each simulation of $M$ runs on its own "row" of the two-dimensional tape of $P$, which also stores the location of the head and the current state. (A two-dimensional tape can be simulated by a one-dimensional tape.)

If $M$ ever halts on one of the strings, then $P$ halts. Therefore $P$ halts iff $M$ halts on some input.


Why does NTM need to derive certificate to prove "If a language is in in NP iff it is decidable by some nondeterministic polynomial time TM"? (Sipser's Chapter 7: Time COmplexity, Pgs 294-295)

If we have to prove the forward direction, then we must have the certificate along with the verifier. I don't get why we are "guessing the certificate"--essentially constructing the verifier-- if we already know one exists.

On the other hand, if you don't have the certificate, you can use a NTM to derive it and check w against c. So you don't need to pass any input into V. So V is useless.

I don't really understand this proof.

By definition NP is the class of languages for which you can efficiently verify with a certificate that a string is in the language.

Informally; it is the class of problems that you can verify the solution to given a witness, but you cannot find one easily. If you could, then it would be in P.

A NTM can be seen as a unrealistic Turing machine which always guesses the right answer. Since the NTM is non-deterministic given an input x. We cannot be sure exactly what path he took to derive the solution, therefore a witness is needed.

For example;

Problem: Is 24 prime?

A NTM would guess the answer to be no and the certificate would be the number “4”.

A verifier presented with the certificate can divide 24 by 4 and also come to the conclusion that 24 is not prime.


How to find polygons overlap reign I have an  algorithmic problem.

I have a set of different polygons in the 2D space. Each polygon is represented according to its vertex representation (x and y coordinates) and may contain up to N different vertices.

Assuming I have a set of N polygons, then for a new polygon k, how do I determine whether or not k overlaps with each one of the N polynomials in the set AND what is the overlapping reign percentage?

This is a purely algorithmic question but I plan on writing the algorithm in parallel using the CUDA platform, therefore any highly parallel solution would be preferred.

Building on top of polygon intersection, a naive process would just intersect each polygon with every other polygon and using the area of the polygons and the area of the intersection could compute what you call the overlapping reign percentage. This is easily parallel, and one could use a simple bounding box intersection to avoid computing the polygon intersect when the polygons's bounding boxes don't overlap.


No Lambda Normal Form How can we show that the term $\Omega = (\lambda x.x\ x)\ (\lambda x.x\ x)$ does not have a normal form? Building on this, what is an example term different than Omega that is not normalizing (meaning a term that every reduction sequence starting from it is infinite)?

If a term has a normal form then there is a sequence of $\beta$-reductions leading to it. However, $\Omega$ has only one $\beta$-redex, which leads back to $\Omega$. Therefore, because $\Omega$ is not already in normal form it has no normal form.

It is easy to generate other terms that have only infinite chains of reductions. For instance, the related $Y$ combinator $Y = \lambda f . (\lambda x . (f (x x)) (\lambda x . (f (x x))$ gives
$$Y \to \lambda f . f Y \to \lambda f . f(f Y) \to \lambda f . f(f(f Y)) \to \cdots$$
Note that by applying $Y$ to a specific $f$ we may get a normalizing term (because for a specific $f$ there will be additional reductions that may lead to a normal form). In fact, $Y$ is quite useful because for any term $g$ we have $Y g = g (Y g)$, so $Y$ computes fixed points.


Why is the complexity of negative-cycle-cancelling $O(V^2AUW)$? We want to solve a minimal-cost-flow problem with a generic negative-cycle cancelling algorithm. That is, we start with a random valid flow, and then we do not pick any "good" negative cycles such as minimal average cost cycles, but use Bellman-Ford to discover a minimal cycle and augment along the discovered cycle. Let $V$ be the number of nodes in the graph, $A$ the number of edges, $U$ the maximal capacity of an edge in the graph, and $W$ the maximal costs of an edge in the graph. Then, my learning materials claim:

The maximal costs at the beginning can be no more than $AUW$
The augmentation along one negative cycle reduces the costs by at least one unit
The lower bound for the minimal costs is 0, because we don't allow negative costs
Each negative cycle can be found in $O(VA)$

And they follow from it that the algorithm's complexity is $O(V^2AUW)$. I understand the logic behind each of the claims, but think that the complexity is different. Specifically, the maximal number of augmentations is given by one unit of flow per augmentation, taking the costs from $AUW$ to zero, giving us a maximum of $AUW$ augmentations. We need to discover a negative cycle for each, so we multiply the maximal number of augmentations by the time needed to discover a cycle ($VA$) and arrive at $O(A^2VUW)$ for the algorithm.

Could this be an error in the learning materials (this is a text provided by the professor, not a student's notes from the course), or is my logic wrong?

According to TopCoder the correct running time is $O( A^2 \cdot VUW)$.


Implementing piecewise linear functions I need to implement piecewise linear functions (this is not homework, it is for my own personal project). However, I have been having difficulties to get it right. Below, I describe the characteristics of the function, operations, and what I have tried so far.
Function: It is defined by linear segments. It may be discontinuous, and some segments may actually be points rather than lines. The function can be any mix of increasing or decreasing parts. The domain is completely bounded by a box with $x \in [0,M]$ and $y \in [0,M]$. The maximum value $M$ is always defined (e.g., never $\infty$).
Operations: The operations I need to perform are fairily simple in mathematical terms. I need:

Shift in $x$ and $y$ (easy)
Shrink/expand pieces (always at the end or start of the function, never in the middle)
Take the maximum between two piecewise linear functions $f(x)$ and $g(x)$ considering that all pieces are within the domains of the box ($[0,M]$) but the actual domain of the functions may not be the same (this has been tricky!)

What I have tried: So far I tried to implement the function as a series of linear pieces defined by their starting starting $(x_0,y_0)$ and ending ($x_1,y_1)$ coordinates. A function then is simply an array of such pieces. However, defining the maximum operation has been quite difficult for me, specially when there are discontinuities and the domain of the two functions $f$ and $g$ are different.
I know this may look more like a "help me with my code" question, but all I wanted was some guides in how to better implement such functions and operations. For example, is my current strategy good? Is there a description of an algorithm to take the maximum of two functions somewhere in the internet? I have tried Stack, Git, and Googling, but have not found any good result to help me with that. I guess either it is too easy and I just don't see it, or it is too obscure and few people do it.
NOTE: I really don't care about operation complexity right now. As long as it is polynomial it is good for me.

A similar question has been asked before, that may answer your question, here. Quoting the answer:

This is basically an instance of the line segment intersection problem.  One standard approach is to use a sweep line algorithm.  For instance, the Bentley-Ottman algorithm would be a reasonable choice, and is not too difficult to implement.
At each iteration of the algorithm, we have some value of $x$, and we calculate what is the next largest value of $x$ where something interesting happens.  Here, "something interesting" is either (1) two pieces intersect each other at a point, or (2) we reach the end of one of the current pieces.  Then we advance $x$ to this next value.
At each iteration, we keep track of which pieces are currently active (i.e., $x$ is within the domain of that piece) and the order of the pieces, ordered by their $y$-value for that particular value of $x$.  Store them in sorted order, sorted by $y$-value.

So, in some sense it is a matter of proper abstraction: you need to implement a function
 something_interesting_happens(real x, function f1, function f2)

the function should return, given an x-value x, the next x-value where either an intersection occurs or the start or end of a line segment occurs. With this functionality out of the way, to return your maximum function, you just iterate over all the interesting x-values, starting from 0 and repeatedly using something_interesting_happens to get the next interesting x-value. It is a bit simpler for you as you are looking to only maximize two functions, and in the above quote they consider maximizing $n$ functions.
The final issue is that you need to settle on a representation for your piecewise linear functions. As plop points out in the comments, your current representation has an issue: it can't represent discontinuous functions.
Here's one possibility, for simplicity:

Define a piece to be either an open line segment, represented by a pair of points $(x_1, y_1), (x_2, y_2)$, or a single point, represented by $(x_1, y_1)$. This gives you sufficient expressiveness to have both closed and open line segments, without worrying about representing open and closed line segments separately. In particular, a closed line segment will be an open line segment, plus points at both of the endpoints.

It will be probably useful to have some functions on pieces, such as:
intersect(piece p1, piece p2)

to indicate if two pieces intersect in the $x$-values they consider, and
less-than(piece p1, piece p2)

which means that p1 and p2 don't intersect, and p1 is before p2.

Represent a piecewise linear function by a (possibly empty) sequence of pieces. The pieces should be sorted, so that less-than(p1, p2) holds for all pieces in the list p1 and p2 where p1 occurs before than p1.


NP-complete problems and sub-expenential sized circuits If one were to show that an NP-complete problem had $2^{n^{O(1)/\log{\log{n}}}}$ circuit complexity, what would the consequences of this be?

If such an algorithm were found, it would violate the exponential time hypothesis.  See also, for example, Are there subexponential-time algorithms for NP-complete problems?.

And of course, if this were the best possible complexity for any algorithm for this problem, you would have shown that $P \ne NP$ (and in fact that $NP \ne P/\text{poly}$).  When you wrote that the problem has such-and-such circuit complexity, I don't know whether you meant (a) there exists an algorithm with that complexity, or (b) the problem has that complexity (which means there exists an algorithm of that complexity, and there is no better algorithm); this paragraph only applies if you meant (b).

Beyond that, I don't think there would be any other obvious consequences.  In particular, I don't know of any significant consequences if the ETH is violated (other than the obvious one, that the theorems of the form "if the ETH holds then..." become moot).


Complement and Context Free Surprising Anyone can describe why $L_{1}$ is not the complement of $L_{2}$, and why $L_{2}$ is not context free?

$$L_{1}= \{w_{1}cw_{2} : w_{1},w_{2} \in \{a,b\}^{\ast}, w_{1} \neq w_{2}\}$$
$$L_{2}= \{w_{1}cw_{2} : w_{1},w_{2} \in \{a,b\}^{\ast}, w_{1} = w_{2}\}$$

If two languages $A$, $B$ are complements of each other, then their disjoint union $A \uplus B$ must be the set of all strings $\Sigma^{\ast}$ over the given alphabet $\Sigma$. That is, every string in $\Sigma^{\ast}$ has to be in $A$ or $B$ but not both. So if we want to show that $L_{1} \neq \overline{L_{2}}$, all we have to do is find a string that is either in both or neither.

In this case it's fairly trivial. All strings in $L_{1}$ and $L_{2}$ have a $c$ in them, so pick any string that doesn't have a $c$ it in. For example $\varepsilon$, it's in neither $L_{1}$ nor $L_{2}$.

A construction for a PDA for $L_{1}$ is given here.

As for proving $L_{2}$ is not context free, everything you need is here.


Generation regular languages by context free grammar I came across problem asking whether given statement is true and false. The statement given was as follows:

  Every Type-2 grammar can generate regular language.

I felt that Type-2 grammar means, its context free grammar and is generated by PDA. PDA is more powerful than FA which generate regular languages. Hence any Type-2 grammar should be able to generate regular language. But the answer given was FALSE saying that there are Type-2 grammars which generate "pure CFL" (non regular languages).

So I was guessing whats going on here. I have following doubts:

Is the question asking whether all CFLs are also regular? (which is not the case and thats why the given answer states "pure CFL")?
Is the question asking whether every CFG generate "all" regular languages? (which is obviously senseless and hence is FALSE?)
Is the answer FALSE because deterministic context free automata accepting on empty stack cannot even accept regular languages?

The question is poorly worded. Here is what they probably meant to ask:

  Is the language generated by a context-free grammar always regular?

Clearly, the answer is negative.

However, this is just a guess, since the question isn't really clear. I suspect ignoring questions which are not clearly stated. If you encounter such a question in an exam, ask the setter to rephrase the question using proper English.


How to give the nearest text that the user has written In my database I have 1500 food dishes, not all are single words, there are compound words like "cheese with dried fruit and nuts". And I have them in 5 languages (de, en, fr, es, it).
My question is how could I do it so that given a text it gives me a prediction of the 5 dishes that are closest to that text.
For example, if the user search for "roquefort with almonds" as closest would return "cheese with dried fruit and nuts" and other 4 results with other dishes.
I have thought about using the Word2Vec model but I am not sure how to start (I am quite a novice) if I should do transfer learning, or how.
Could someone guide me on how to approach the solution to this problem?

This is not an easy task.  There is no simple answer; you could do something crude that might give mediocre results, or you could put a lot of effort into it; and it's not obvious to me what will work best.
One possible simple approach is to map each word (except for a few stopwords) to an encoding, using a standard word embedding (e.g., word2vec), average the vectors of the words to get an embedding of the phrase, and then compare two phrases using the L2 distance of their embeddings.  I don't know how well this will work; you could try it and see.
There will probably be more sophisticated approaches, e.g., training a language-based model to compare two phrases for similarity, perhaps building on an existing model (such as BERT) and fine-tuning it.  I anticipate this will require many labelled samples and a non-trivial amount of research and experimentation, so it's not a minor project to take on.


What are GEN and KILL statements in dataflow analysis? In data flow analysis, is GEN statement where a variable is used and KILL statement is where variable is redefined?

Dataflow analysis works on sets of facts.  GEN points are points in the graph where one of the facts you care about becomes true, and KILL points are points in the graph where one of the facts you care about becomes false.

The GEN and KILL points thus depend on the facts you care about.

For example: if you were doing a constant propagation analysis you might care about the fact that variable x has the constant value 3.  Any point in the graph where x is assigned the value 3 is a GEN point.  Any point in the graph where x is assigned a constant value other than 3 is a KILL point.

If you were doing reaching definitions, and x is defined in two different places then the facts you are interested in are (1) "x from the first definition may be available here" and (2) "x from the second definition may be available here."  In this case the point where x is first defined is a GEN point for fact (1) and a KILL point for fact (2).  The point where x is second defined is a GEN point for fact (2) and a KILL point for fact (1).

As a third example, suppose you were doing a liveness analysis.  This is a backwards analysis.  In this case the places where x is used are GEN points, because x is live at the statement where it is used, and at some of the statements above the statement where it is used.  The definitions of x are KILL points, because the previous definitions of x are no longer needed after this node (as well as at along all the nodes along the reverse path until you reach a GEN statement higher in the graph.)


Closure under the Star Operation I'm doing my homework, but there's one task that I didn't get the idea.

Task:

Recall the alternative definition for the star of a language A that we gave just before Theorem 2.3.1. In Theorems 2.3.1 and 2.6.2 (which is about closure under union operation), we have shown that the class of regular languages is closed under the union and concatenation operations. Since $A^* = \cup_{=0}^\infty ^$, why doesn’t this imply that the class of regular languages is closed under the star operation?

One must be careful about what the closure properties actually state.

If $A,B$ are regular languages, then $AB$ and $A \cup B$ are regular languages as well.

By induction, one can obtain that the concatenation / union of finitely many regular languages $A_1,\ldots,A_n$ is regular.

This however does not extend to infinite unions!

To understand why the extension would be wrong, consider a simpler case, first. Take the class of finite languages: sets containing finitely many words. Clearly this class is closed under union: if $A,B$ are finite languages, then $A\cup B$ is a finite language. However, taking the union of the infinitely many finite languages $\{1\},\{11\},\{111\},\ldots$ one gets an infinite language $\{1,11,111,\ldots\}$.

In the realm of regular languages, we met the same problem. Take any non-regular language $L$: it has to be infinite, since otherwise it would be regular. We can write $L=\{w_1,w_2,\ldots\}$ for some $w_1,w_2,\ldots$. But we also have $L=\{w_1\}\cup\{w_2\}\cup\ldots = \bigcup_{i\geq 1}\{w_i\}$, which is an infinite union of singleton-languages, which are regular. So, any non regular $L$ can be written as an infinite union of regular languages.

We conclude that the union of infinitely many regular languages is not necessarily a regular language.


MST Proof (Kleinburg & Tordos) Consider the Minimum Spanning Tree Problem on an undirected graph
G = (V, E), with a cost ≥ 0 on each edge, where the costs may not all
be different. If the costs are not all distinct, there can in general be
many distinct minimum-cost solutions. Suppose we are given a spanning
tree T ⊆ E with the guarantee that for every e ∈ T, e belongs to some
minimum-cost spanning tree in G. Can we conclude that T itself must
be a minimum-cost spanning tree in G? Give a proof or a counterexample
with explanation.


A pumping lemma for deterministic context-free languages? The pumping lemma for regular languages can be used to prove that certain languages are not regular, and the pumping lemma for context-free languages (along with Ogden's lemma) can be used to prove that certain languages are not context-free.

Is there a pumping lemma for deterministic context-free languages?  That is, is there a lemma akin to the pumping lemma that can be used to show that a language is not a DCFL?  I'm curious because almost all of the proof techniques I know to show that a language is not a DCFL are really complicated, and I was hoping that there was an easier technique.

There is a Pumping Lemma specifically for DCFL, under the title "A Pumping Lemma for Deterministic Context-Free Languages", by Sheng Yu; Information Processing Letters 31 (1989) 47-51, doi 10.1016/0020-0190(89)90108-7. With this explicit title I must apologize that I missed it!
The online copy unfortunately has a blank spot in one of the formula, so I hope I reconstructed the result properly. Below ${}^{(1)}y$ is the first symbol of $y$ (when it exists) or $\varepsilon$ (if $y=\varepsilon$).
Lemma 1 (Pumping Lemma). Let $L$ be a DCFL. Then there exists a constant $C$ for $L$ such that for any pair of words $w,w'\in $ if
(1) $w=xy$ [?] and $w'=xz$, $|x|>C$ and
(2) ${}^{(1)}y = {}^{(1)}z $, [?]
then either (3) or (4) is true:
(3) there is a factorization $x=x_1x_2x_3x_4x_5$, $|x_2x_4|\ge 1$ and $|x_2x_3x_4|\le C$, such that for all $i\ge 0$ $x_1x^i_2x_3x^i_4x_5y$ and $x_1x^i_2x_3x^i_4x_5z$  are in $L$;
(4) there exist factorizations $x=x_1x_2x_3$, $y=y_1y_2y_3$ and $z=z_1z_2z_3$,  $|x_2|\ge 1$ and $|x_2x_3|\le C$, such that for all $i\ge 0$ $x_1x^i_2x_3y_1y^i_2y_3$ and $x_1x^i_2x_3z_1z^i_2z_3$ are in $L$.
Two applications of the Lemma are given: $\{ a^ib^i \mid i\ge 0 \} \cup \{ a^ib^{2i}  \mid i\ge 0 \}$ as well as $\{ w\in\{a,b\}^* \mid w=uv, |u|=|v|, \mbox{ and } v \mbox{ contains an } a \}$ are not DCFL.
The proof uses the fact that each DCFL has an LR(1) grammar in Greibach normal form.


How to find a 2-wise independent hash family that is not 3-wise independent? I'm trying to find a family of hash functions mapping $\{1, 2, ..., 2^n\}$ to $\{0, 1\}$ that is 2-wise independent but not 3-wise independent. Any ideas on that?

I know two 2-wise independent families but I think they are 3-wise independent as well:

1) Let x be a vector in $\{0, 1\}^n$. The hash functions are $h_{a, b}(x)=a^\top x+b \mod  2$ for all $a\in\{0, 1\}^n$ and $b\in\{0, 1\}$.

2) Consider $GF(2^n)$. The hash functions are $$h_{a, b}(x)= \text{the last bit of }a \cdot x+b $$ for all $a, b\in GF(2^n)$.


Shortest path in modular arithmetic Suppose we have 7 vertices, each of which corresponds to a different integer modulo seven. The edge exists between two vertices x and y if x + 3 ≡ y mod 7. For example, there is an edge between 0 and 3, and an edge between 5 and 2. What is the length of the shortest path between 0 and 1?
My method to get the answer is to apply the definition of congruence. The edge exits iff $7 | x + 3 - y$. Thus, I got one cyclic graph and then get the answer is 2. Is there any method I can play with modular arithmetic without drawing a graph so that I can get shortest path between node 0 and node 1?

Let us consider the more general case in which you have $n$ vertices, and you connect $x,y$ if $x-y \equiv a \pmod{n}$ (in your case, $n = 7$ and $a = 3$).
Your graph is a union of disjoint cycles. When $n$ is prime (as in your case), it is a single cycle. Hence if you want to get from $x$ to $y$, either you keep adding $a$ (modulo $n$), of you keep subtracting $a$ (modulo $n$). If you add $m$ times the value $a$ (where $m$ is possibly negative) then $x+ma \equiv y \pmod{n}$, that is, $ma \equiv y-x \pmod{n}$. Let us now assume that $(a,n) = 1$ (for example, $n$ is prime and $1 \leq a \leq n-1$). Then $m \equiv a^{-1}(y-x) \pmod{n}$.
Solving the equation above (assuming $x \not\equiv y \pmod{n}$), there will be one solution $m_+$ in the range $1,\ldots,n-1$ and another $m_-$ in the range $-1,\ldots,-(n-1)$. The distance is $\min(m_+,-m_-)$.
In your case, $n = 7$ and $a = 3$. We can compute $a^{-1} = 5$. If $x = 0$ and $y = 1$ then $a^{-1}(y-x) = 5$, and so $m_+ = 5$ and $-m_- = 2$. So the shortest path goes backwards for two steps: $0 \to 4 \to 1$.


Why is CAN protocol preferred to be used in automotive application? Is it only because of the fact that it is asynchronous and can be used for long distance message transfer. An example of where other protocols will fail would help.
Thanks.

A few reasons :

CAN was developed by BOSCH, which have a lot of influence in automotive equipment (engine control, braking, body, gearbox control...). BOSCH ensured that CAN killed competitors like the VAN protocol. (CAN was patented, and BOSCH sells CAN controller IPs)
CAN is much cheaper than Ethernet.
There were no suitable industrial bus at the time, using physical layers like RS-485 : Modbus, Profibus...

Now several other busses are used in automotive applications :

LIN : Slower, cheaper than CAN. For very simple devices.
FlexRay : Faster than CAN, deterministic. For advanced real time functions like dynamic suspension.
Ethernet : The future, particularly in a 2 wires implementation. For a few advanced applications, including steer-by-wire, video...

Anyway, CAN is here to stay as it offer a good balance between performance and cost of implementation.


Updating an MST $T$ when the weight of an edge not in $T$ is decreased Given an undirected, connected, weighted graph $G = (V,E,w)$ where $w$ is the weight function $w: E \to \mathbb{R}$ and a minimum spanning tree (MST) $T$ of $G$.
  Now we decrease the weight by $k$ of an edge $e$ which does not belong to $T$.

  How to efficiently update $T$ to make it an MST (denoted $T'$) of $G'=(V,E,w')$, where $w'$ is the same as $w$ except that $w'(e) = w(e) - k$?

The algorithm for updating $T$ to $T'$ is easy: Adding $e$ to $T$ creates a cycle $C$ in $T$. Let $e'$ be a maximum-weighted edge in the cycle $C$. If $w(e') > w’(e)$, then $T' = T \cup \{e\} - \{e'\}$ is the MST as desired. Otherwise, $T' = T$.

I have difficulty in proving its correctness by contradiction. Suppose $T''$ is a spanning tree of $G'$ and $w'(T'') < w'(T')$.

$e \notin T''$: we have $w(T'') = w'(T'') < w'(T') \le w(T)$. Contradicts with the fact that $T$ is an MST of $G$.
$e \in T''$: I am stuck here.

Two Notes:

The accepted answer here to the same question is too general for me to follow.
I prefer to proofs which do not rely on any concrete MST algorithms, such as Kruskal's and Prim's algorithms. However, you don't need to prove it by contradiction or separate the two cases $e \notin T''$ and $e \in T''$ as I did.

Let $T$ be a minimum spanning tree of $G$. Let $e$ be the edge we modify to get $G'$, and let $T'$ be the tree computed according to the algorithm. We know that weight of $T'$ is less than or equal to the weight of $T$.

Firstly, $T'$ is a tree - we create exactly one cycle in the algorithm, and break it, so we have no cycles in $T'$.

Secondly $T'$ is a spanning tree of $G'$. Let $e'$ be the edge removed and $e''$ be the edge added in the algorithm (we have either $e'' = e'$ or $e'' = e$) . To be a spanning tree, we must have a path between every pair of vertices $u$, $v$ using only edges of $T'$. Suppose that in $T$ (which is definitely a spanning tree), the path from $u$ to $v$ did not involve $e'$, then the same path exists in $T'$. Alternatively, suppose that it did use $e'$, then there is a path (without loss of generality) from $u$ to one endpoint of $e'$ and from the other endpoint of $e'$ to $v$. There is also a path from one endpoint of $e'$ to the other endpoint via $e''$ (around the cycle), all within $T'$. Then we can construct a path from $u$ to $v$ via $e''$ in $T'$ by merging these three paths and removing the overlap (although a walk is sufficient for connectivity).

Now, the important part, we wish to prove that $T'$ is a minimum spanning tree for $G'$.

Case 1: The algorithm does not add $e$ to the tree. In this case $T' = T$. Suppose that there is a minimum spanning tree $H$ for $G'$ that is different to $T'$. If $H$ has the same weight as $T'$, we're done. Now suppose for contradiction that the weight of $H$ is less than the weight of $T'$. There must be some edge $e'$ of lowest weight that is in $H$ but not in $T'$ (there must be some edge that does better, otherwise $G$ would not be of lower weight than $T'$, moreover we can assume that the edge that does better is the lowest weight edge that's not in $T'$ - we can take any $H'$ that is a lower weight tree than $T'$ and look at the candidate for $e'$, if it is not smaller than any edge in its cycle, then either $H'$ is not an MST, or we can create a new $H'$ where we swap the $e'$ for some edge of $T'$, this process must terminate with an edge $e'$ which has the property that it is the edge that does better).

If $e' \neq e$, then consider the tree obtained by adding $e'$ to $T$ (note, not $T'$), and removing the highest weight edge on the cycle formed. This new tree has weight less than that of $T$ and is a spanning tree for $G$, contradicting the fact that $T$ is an MST for $G$ - so we know this can't happen.
If $e' = e$, consider the cycle formed by adding $e' = e$ to $T'$ (i.e. the one the algorithm considered). All other edges in the cycle have lower weight than $e'$ (otherwise the algorithm would've included $e$ as an edge), and hence must be in $H$ (as $e'$ is the lowest weight edge that is not already in $T'$), but then $H$ must contain a cycle, so isn't a tree and we have a contradiction.

Case 2: The algorithm adds $e$ to $T'$. Let $x$ be the edge in $T$ that is removed by the algorithm (and hence not in $T'$) Again assume we have another MST $H$ as before. If the weight is the same, we're happy. So assume for contradiction that $H$ has lower weight, and as before $e'$ is the lowest weight edge in $H$ that's not in $T'$. We can make similar arguments as before with $x$.

If $e' \neq x$, (note also that $e' \neq e$), then we can improve $T$ as before, but we know that $T$ is an MST, and recalling the property that we can assume $e'$ has lower weight that at least one edge in the cycle its addition induces, this gives a contradiction and $H$ can't exist.
If $e' = x$, then again $e'$ must have higher weight than all the other edges in the cycle, hence $H$ must contain all these edges and $H$ is not a tree, and we derive a contradiction.

So in every case we derive a contradiction, therefore there can be no spanning tree of lower weight that $T'$, hence $T'$ is a minimum spanning tree for $G'$.


Is a non-deterministic turing machine that both accepts and rejects the same input valid? I.e. - if a TM accepts the word 0011100 on one path, while on another the same word is rejected. Do we say that 0011100 is part of the language, or do we say that it is not a valid TM?

A non-deterministic Turing machine accepts a word if an accepting computation exists. There can be many non-accepting computation paths. This is what makes recognizing the complement of the language more difficult than just inverting accepting an rejecting states as you would do with a deterministic machine.


In a DBMS what are the implementation details that make set operations faster than cursors? What are the low level implementation details that make set based operations exponentially faster than iterative processes, like cursors?

At a memory level how does a set operation "touch" the data less than a cursor?

Set-based operations are iterative at a "low level", and are not necessarily any faster to execute than cursors under all circumstances.
The main advantage with set-based operations is that they are well-defined operators which can be analysed algebraically, and the order of operations thus rearranged or simplified by the database engine, or the exact algorithmic implementation altered - not just at the time of writing the query, but possibly later at the time of subsequent executions of the query.
What is "simple" or "fast" here is constantly re-determined by the database engine at runtime based on the statistics it collects about actual whole database performance.
By contrast, there is much less flexibility for the database engine in the case of cursors, and if every action in a database were written as a cursor then overall performance could become abysmal (or the system more recalcitrant to any changes) far sooner than when set-based operations are used which provide the database engine a large latitude for optimisation.
The most straightforward analogy is the performance of a modern optimising compiler for a high-level language, versus writing everything in assembly language, although this does not quite capture the ongoing monitoring that a database engine performs.


Mastermind (board game) - Five-guess algorithm The algorithm (from here) -

  Create a set S of remaining possibilities (at this point there are 1296). The first guess is aabb.
  Remove all possibilities from S that would not give the same score of colored and white pegs if they were the answer.
  For each possible guess (not necessarily in S) calculate how many possibilities from S would be eliminated for each possible
  colored/white score. The score of the guess is the least of such
  values. Play the guess with the highest score (minimax).
  Go back to step 2 until you have got it right.

I confused about the 3nd step -

what is mean -

  how many possibilities from S would be eliminated for each possible
  colored/white score

what is the "correct answer" and the "guess" here  ?

Can someone clear it some more ?

The text you quoted seems clear as it is.  But I'll try to elaborate on step 3, since you asked:

Let $S$ denote the set of possible secrets (given responses to moves you've made so far).  Given a candidate guess $g$, you run over all possibilities $s \in S$ and calculate the response that you'd get if you guessed $g$ and the secret was $s$ (the number of black pegs and the number of white pegs); this is "the colored/white score".  Now, for each colored/white score that could be received, if you were to get that score, you could eliminate some possibilities from $S$ as incompatible with that colored/white score; the "goodness" of a colored/white score is the number of possibilities eliminated.  The "helpfulness" of a candidate guess $g$ is the minimum of the "goodness" of all the colored/white scores you could possibly get, in response to $g$.  Select the guess $g$ with highest "helpfulness".

In other words, let $R(g,s)$ denote the number of black pegs and number of white pegs you'd get if the secret were $s$ and you guessed $g$ (this is what your quote calls the "colored/white score").  Let $Z(g) = \{R(g,s) : s\in S\}$, so that $Z(g)$ denotes the set of "colored/white scores" you could possibly get if you made guess $g$ (given that the secret $s$ has to be one of the possibilities in $S$).   Now, if you have a "colored/white score" $z$ where $z \in Z(g)$, let

$$G(g,z) = |\{ s \in S : R(g,s) \ne z\}|,$$

so that $G(g,z)$ is the "goodness" of getting a "colored/white score" $z$ in response to guess $g$.  Also, let

$$H(g) = \min \{G(g,z) : z \in Z(g)\},$$

so that $H(g)$ denotes the "helpfulness" of a candidate guess $g$.

Now step 3 says: you should play the guess $g$ that maximizes $H(g)$.


Unable to understand an inequality in an application of the pumping lemma for context-free languages The problem

Prove that the language

$\qquad L = \{a^n b^j \mid n = j^2\}$

is not context free using pumping lemma.

Approach taken by the book

To prove such statements, the book takes the approach of a game played against an opponent who strives to fail our effort to prove that the language is not context free. The steps involved in the game are as follows:

The opponent chooses m such that for all w $\in$ L, |w| >= m
We choose the string w
The opponent decomposes w in uvxyz such that |vxy| <= m and |vy| >= 1
We pump v and y i-times to get the string uv$^i$xy$^i$z.

Now, if for any i = 0,1,2,...

uv$^i$xy$^i$z $\notin$ L

the language L is not context free.

The solution to the above problem

Opponent chooses m
We choose w = a$^{m^2}$b$^m$
The opponent decomposes w in uvxyz as follows:

Pumping v and y i-times yields string with m$^2$+(i-1)k$_1$ a's and m+(i-1)k$_2$ b's.
If opponent takes k$_1$ $\ne$ 0 and k$_2$ $\ne$ 0, we can take i = 0, such that

(m-k$_2$)$^2 \leq$  (m-1)$^2$             ... since k$_2\ne$ 0 making minimum value of k$_2$ is 1

= m$^2$-2m+1

< m$^2$ - k$_1$

Q. This last line I did not understand. How is -2m+1 < -k$_1$? Especially because I can find the below decomposition uvxyz for which -2m+1 > -k$_1$.

I must be missing some stupid algebra here.

The solution further continues saying that the pumped resultant string does not belong to L.

Similar argument can be done if user select k$_1$ = 0 and k$_2$ $\ne$ 0  or k$_1$ $\ne$ 0 and k$_2$ = 0

The Pumping Lemma requires $|vxy| \le m$ so that the pumped parts are of bounded length. Thus $k_1+k_2\le m$. With this it is easy.

As $k_2 \neq 0$, we must have $k_1<m$. Also $m>0$ as the pumping constant must be positive (but in fact we can assume it to be as large as we want, of course).

Now $2m-1 \ge m > k_1$.

That's all.


How is $\text{PCP}[O(\log n),O(1)]$ NOT P? As a prover, we just try to convince the verifier that it's correct, no matter whether it is or not. So we can just analyze every possible route.

For $\text{PCP}[O(\log n),O(1)]$, won't there just be polynomial many possible routes, and checking all just cost polynomial time?

  In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties. The parties, the verifier and the prover, interact by exchanging messages in order to ascertain whether a given string belongs to a language or not. The prover is all-powerful and possesses unlimited computational resources, but cannot be trusted, while the verifier has bounded computation power. Messages are sent between the verifier and prover until the verifier has an answer to the problem and has "convinced" itself that it is correct.

A language $L$ is in $\mathsf{PCP}(r(n),q(n))$ if there is a randomized polytime algorithm $V(x,y)$ which acts as follows:

The algorithm is given $r(n)$ random bits.
Given these random bits, it chooses (deterministically) $q(n)$ locations in $y$.
It reads $y$ at these locations, and based on that, decides whether to accept or reject.

Furthermore, $V$ satisfies the following two conditions:

If $x \in L$ then there exists $y$ such that $\Pr[V(x,y) \text{ accepts}] = 1$.
If $x \notin L$ then for any $y$, $\Pr[V(x,y) \text{ accepts}] \leq 1/2$.

Let $n = |x|$. Since $V$ uses only $r(n)$ random bits and reads at most $q(n)$ bits of $y$, at most $2^{r(n)} q(n)$ bits of $y$ can potentially be read. when $r(n) = O(\log n)$ and $q(n) = O(1)$, this means that at most polynomially many bits are read from $y$, and so we can assume that $y$ has polynomial length.

Every language in $\mathsf{PCP}(O(\log n), O(1))$ is in $\mathsf{NP}$. Indeed, given $y$, we can compute $\Pr[V(x,y)\text{ accepts}]$ in polynomial time (since there are only polynomially many choices for the random bits). However, the language is not obviously in $\mathsf{P}$, since there are exponentially many choices for $y$.


What happens when there is a branch mispredict and an interrupt occurs? There is a branch mispredict and while executing the false code, an interrupt occurs (for example a keyboard interrupt). The EPC (register that holds the return address) now holds the wrong return address (after the interrupt handler has finished, it would return in code that wasn't even meant to be executed). How do CPUs deal with this problem?

All instructions in the processor are executed speculatively and every instruction that is fetched after a mispredict needs to be cancelled without allowing any of its effects to become externally visible.  This is done with register renaming and a reorder buffer that commits instruction effects in-order.  Instructions from asynchronous interrupt handlers are handled the same way, the main difference (and complexity) being how you refetch them after the mispredict causes them to get cancelled.

Example: you fetch the branch at the address $B$, mispredict its target as $M_0$, and start fetching $M_0, M_1, \cdots, M_n$.  At this point the fetch unit realizes that an asynchronous interrupt, starting at address $I_0$, needs to be handled and proceeds to set $M_{n+1}$ as the predicted EPC, and fetch $I_0, I_1, \cdots, I_m$.  (Note that we've only set the predicted EPC to $M_{n+1}$, not the "real" (externally visible) EPC.)  Now the execution unit finally realizes that the branch at $B$ was mispredicted and that the correct branch target was $T_0$.

At this point we must mark all the instructions $M_0, M_1, \cdots, M_n, I_0, I_1, \cdots, I_m$ as "cancelled."  Luckily none of them have been committed because they are all behind $B$ in the reorder buffer.  Then the execution unit sends a signal to the fetch unit that the correct instruction after $B$ should have been $T_0$, rather than $M_0$.

At this point the fetch unit must realize that there was an asynchronous interrupt handler that had been fetched but not committed.  It could do this, for example, by keeping a counter that is incremented the first time the first instruction of an asynchronous interrupt handler is fetched, and decremented when that instruction retires (is committed).  So the fetch unit sets $T_0$ as the predicted EPC, starts fetching from $I_0$ again (a new copy of the instruction at $I_0$, let's call it $I_0'$), and proceeds with $I_1', I_2', \cdots, I_m'$.  At some point the branch $B$ reaches the head of the reorder buffer and commits.  That means that it records $T_0$ as the correct (externally visible) "next instruction pc".

$B$ is followed in the reorder buffer by a bunch of cancelled instructions, $M_0, M_1, \cdots, M_n, I_0, I_1, \cdots, I_m$, these are not committed, but any resources (e.g., physcial registers) allocated to them need to be returned to the free-register queue.  Finally $I_0'$ reaches the head of the reorder buffer.  It commits.  As part of committing the externally visible "next instruction pc" is copied into the real (externally visible) EPC register.

TL;DR

Register renaming and the reorder buffer make handling mispredicted branches much easier.


Designing context free grammar for a language with range restriction on repetition of alphabets I am having issue with designing contex free grammar for the following language:

$L = \{0^n 1^m \, | \, 2n \leq m \leq 3n \}$

I can design for the individual cases i.e. for $m \geq 2n$ and $m \leq 3n$ but don't know how should i combine both. Or is it a different approach altogether?

It has been a while, since I have done context-free grammars, but I think this should be the answer:

$\qquad \displaystyle A \to 0A11 \mid 0A111 \mid \varepsilon$

I am assuming that empty string is in $L$.

The idea behind is, that you are working your way from outside. Since you need at least 2 times more of $1$'s, than you need $0$'s, you need the first rule. The upper limit is handled with the second rule. All cases inbetween are also covered. $-$ is needed for termination.


Why doesn't this derivation of the margin in a SVM give the correct result? I'm trying to derive the optimization objective for an SVM (namely $1/\|w\|$), but I'm running into a little trouble. I've already read this question, which has certainly offered a lot of insight into the problem, but I would like to know why my own derivation doesn't quite work.

So essentially, let's say our support vectors on either side of the decision boundary are $\vec x_+$ and $\vec x_-$. Suppose the decision boundary itself is $\vec w\cdot\vec x + b = 0$. We have $\vec w\cdot x_\pm + b = \pm 1$. Now, the margin $d$ can be calculated as the sum of the distances between the points $\vec x_\pm$ and the decision boundary. We can use the typical projection formula to obtain

$$
\begin{aligned}
d & = \left\|\vec w\frac{\vec x_+\cdot\vec w}{\vec w\cdot\vec w}\right\| + \left\|\vec w\frac{\vec x_-\cdot\vec w}{\vec w\cdot\vec w}\right\| \\
& = \frac{\|\vec w\|}{\|\vec w\|^2}(|\vec x_+\cdot\vec w| + |\vec x_-\cdot\vec w|) \\
& = \frac1{\|\vec w\|}(|1-b|+|1+b|)
\end{aligned}
$$

This is almost the correct result, and in fact if we restrict $b\in[-1, 1]$, $d$ reduces to $2/\|\vec w\|$ as expected. However, in general this can be written:
$$
d = \frac{2\max(1,|b|)}{\|w\|}
$$
So my question essentially is why did I end up with the extra b in the numerator? Does it change the optimization objective at all (I feel like it does)? Is there a reasonable explanation for why we could potentially restrict $b\in[-1,1]$?

The first line of your equation for $d$ is incorrect.  It should be

$$d = \left\|\vec w\frac{\vec x_+\cdot\vec w}{\vec w\cdot\vec w} - \vec w\frac{\vec x_-\cdot\vec w}{\vec w\cdot\vec w}\right\|.$$

(Why?  The distance between two points $u,v$ is $\|u-v\|$, not $\|u\|+\|v\|$.)

If you continue the derivation from there, you will obtain the result you were expecting.


Find dominated or subsumed linear inequalities efficiently Problem statement
Given a set of $N$ linear inequalities of the form $a_1x_1 + a_2x_2 + ... + a_Mx_M \geq RHS$, where $a_i$ and $RHS$ are integers. The inequality $A$ dominates or subsumes inequality $B$ if all its coefficients are less or equal and $RHS_A \geq RHS_B$. Most inequalities are sparse, i.e. most coefficients are zero. Usually, both $N > 1000$ and $M > 1000 $. I'm trying to identify dominating or subsuming inequalities efficiently.
What are quick ways to find
a) if an inequality is dominated by any other inequality, and
b) which inequalities are dominated by a given inequality?
(Monte-Carlo algorithms are fine, that only report correct results most of the time)
Proposed solutions in the literature
Eén, N. and Biere, A., 2005, June. Effective preprocessing in SAT through variable and clause elimination. In International conference on theory and applications of satisfiability testing (pp. 61-75). Springer, Berlin, Heidelberg. (chapter 4.2) discuss a variant of this problem in the context where all coefficients are binary, i.e. $a_i \in {0, 1}$. They propose occurrence lists, one per variable $x_i$, containing all inequalities with non-zero coefficients $a_i$. Additionally they use a hashing scheme, similar to Bloom filters, to quickly eliminate candidates. I don't see how to translate this to non-binary coefficients.
Achterberg, T., Bixby, R.E., Gu, Z., Rothberg, E. and Weninger, D., 2020. Presolve reductions in mixed integer programming. INFORMS Journal on Computing, 32(2), pp.473-506. (chapter 5.2) discuss a variant of the problem, but don't solve it. They first hash inequalities by indices of non-zero coefficients and the coefficient values. Additionally, they limit their search to a small subset of inequalities.
Schulz, S., 2013. Simple and efficient clause subsumption with feature vector indexing. In Automated Reasoning and Mathematics (pp. 45-67). Springer, Berlin, Heidelberg. describes Feature Vectors for clauses and a kd-tree-like data structure to query combinations of feature vectors.
Things I've tried

The trivial solution is to check all pairs of inequalities in $O(n^2)$. Unfortunately, that's too slow for my application where I have millions of inequalities.
I tried performing a random projection of the coefficients for every inequality, resulting in a projection $p_j$ for every inequality. An inequality $j$ can only dominate inequality $k$ if $p_j \leq p_k$. Thus we don't have to check all pairs. I repeat this process 10 times with multiple random projections, and use the random projection where I have to check the fewest pairs. In practice this is not effective, as most coefficients are zero - and it's unlikely that a random projection focusses exactly on the few non-zero elements. It doesn't help nearly enough.
Similarly I implemented Feature Vectors, but couldn't replicate the performance reported by Schulz.
AFAIK, multi-dimensional data structures break down in high-dimensional scenarios (curse of dimensionality). I'm not aware of indexing techniques that work for high-dimensional range queries.
I thought about Bloom filters, unsuccessfully.
I thought about randomized algorithms, unsuccessfully.

Do you have any other ideas?

Unfortunately there is a nearly-quadratic-time lower bound that may prove a barrier.  In particular, you can't solve it in $O(N^{2-\varepsilon})$ time for any $\varepsilon>0$ unless the Strong Exponential Time Hypothesis is false.  In particular, the special case where all coefficients are 0 or 1 and the RHS is the same for all inequalities is equivalent to searching a bunch of sets for a pair that have a subset relationship, and that is hard: see https://cstheory.stackexchange.com/q/9896/5038.
The one saving grace is that this lower bound is for arbitrary sets, i.e., it does not take into account sparsity.  It is possible that you might be able to use sparsity somehow to do better than the general case.
Here is an algorithm that takes advantage of sparsity to do a bit better.  Suppose that every inequality has only $K$ nonzero coefficients.  Form a balanced binary tree on the $N$ inequalities.  Annotate each node with a map that maps $x_i$ to the max of all coefficients of $x_i$ in all inequalities under that node.  Now given an inequality $A$, you can check whether it dominates any other inequality by traversing the tree in a top-down breadthfirst fashion.  Any time you hit a node that maps $x_i$ to something smaller than $x_i$'s coefficient in $A$, there is no need to visit any of the children of that node, and traversal of that subtree can be skipped.  Heuristically, I expect you'll probably need to visit $O(KN/M)$ nodes of the tree on average (well, plus $O(\lg N)$ to account for the fact that each inequality dominates itself, but I'll ignore that as it seems likely to be small in comparison to the other terms).  Creating the tree takes $O(NK)$ time, and visiting each node takes $O(K)$ time, so I expect the overall running time per inequality will be something like $O(KN + K^2N/M)$, on average.  Since you have $N$ inequalities, the total time should be something like $O(KN + K^2N^2/M)$.  I don't know whether this is any better than what you already have in mind, though.


Why does this pumping lemma proof not cover every division of xyz? I am trying to prove $L =$ {${a^k|k=2^n, n \ge 0}$} is not regular.
So far I have identifed a string $s = a^{2^p}$, and I've divided $s$ into $xyz$ as follows:

$x = a^l$

$y = a^k$

*(where $k + l \le p$)

$z = a^{2^p-l-k}$

Now, when I start to look at pumping, I first select $i=0$:

$xy^iz = xy^0z = xz = a^la^{2^p-l-k}=a^{2^p-k}$, which is clearly not equivalent to $a^{2n}$. However, I know that there are mistakes in this proof and I have been told that my division of the string $s$ into $xyz$ does not account for all divisions. Could anyone please help?

For reference, the pumping lemma is (from Introduction to the Theory of Computation by Michael Sipser)

  If $A$ is a regular language, then there is a number $p$ (the
  pumping length) where if $s$ is any string in $A$ of length at least $p$, then $s$ may be divided into three pieces, $s = xyz$, satisfying the following conditions:

  for each $i ≥ 0, xy^i z \in A$,
  $|y| > 0$, and
  $|xy| \le p$.

When you want to prove that a language is not regular using the pumping lemma, you use a proof by contradiction. You first assume that the given language is regular.

As per the pumping lemma, given a regular language, there exists a number $p$ such that for all $s$ with length at least $p$, there exists a way to partition it in the form $x,y,z$ such that all the three conditions hold.

The contrapositive is

For all $p\ge1$, there exists a string $s$ with length at least $p$, such that for all ways to partition $s$ in the form $x,y,z$, at least one of the three conditions are false, implies that the language is not regular.

So, to show that $L$ is not regular, you need to show that the appropriate quantifier (existential or universal) for each entity is used correctly.

Initially, you have taken a value $p$, with no assumption. This is in accordance with for all $p$.

Then, you have chosen a string $s$ with length at least $p$. This is in accordance with there exists a string $s$, i.e., a single instance of a string satisfying the rest of the statement is sufficient.

Now, you need to consider all ways of partitioning $s$ in the form $x,y,z$, and show that always, at least one of the three statements of the lemma is false.

So, you have partitioned it into $x=a^l, y=a^k, z=a^{{2^p}-l-k}$. As of now, there are no assumptions on the values $l$ and $k$ can take, except that they are non negative, which is as required. To force a contradiction, you need to try to show that all the statements of the lemma do hold. Statement 2 states that $|y|\gt0$. So, if it were true, we must have $k\gt0$. Statement 3 states that $|yz|\le p$. If it were true, we must have $k+l\le p$.

Finally, Statement 1 must be true if $L$ is regular, so $xy^iz\in L$ for all $i\ge0$ must be true. It is sufficient thus to show that it is false for any one value of $i$. I choose $i=2$. So, we must have $a^la^{2k}a^{{2^p}-l-k}=a^{{2^p}+k}\in L$ for all possible values of $l$ and $k$ except as per the previously imposed restrictions.

Now, we have
$$k\gt0\implies k\ge1$$
$$2^p+k\ge 2^p+1\gt 2^p\tag1$$

$$k+l\le p$$
But $l\ge 0$, so we have
$$k\le p$$
$$2^p+k\le 2^p+p\tag2$$

But we have $$p\lt 2^p$$

for all $p\ge 1$, which is the set of all allowed values of $p$. So, $(2)$ becomes,
$$2^p+k\le 2^p+p\lt 2^p+2^p=2^{p+1}\tag3$$

From $(1)$ and $(3)$,

$$2^p\lt 2^p+k \lt2^{p+1}$$

As $2^p+k$ lies strictly between consecutive powers of $2$, it cannot be a power of $2$ itself. So, $a^{2^p+k}\notin L$, and we have a contradiction as desired.

Thus, $L$ is not regular.

In your proof, the initial steps are all correct, all you need to do is to show why the string cannot lie in the language, using an appropriate value of $i$, as shown in this answer. Moreover, choosing $i=0$ is not straightforward. For $i=2$, I argued that $2^p\gt p$. For $i=0$, you will need to use $2^{p-1}\gt p$, which is not true if $p=1$.


Deterministic construction for trapezoidal decomposition There is a nice decomposition called trapezoidal to process point location queries given a set of disjoint generally curvilinear segments. I found the randomized algorithm for building this type of decomposition in Berg's book on computational geometry. Can someone point me out papers which report deterministic algorithms with only a little polynomial overhead which provides the same capabilities of trapezoidal decomposition for point location ?

I finally found recent paper titled "Optimal randomized incremental construction for guaranteed logarithmic planar point location" by several authors, where deterministic times are given for query and the seach structure, but expected time for preprocessing.


Which goes first stl or data structures and algorithms? So I'm a newbie to c++. I know the basic concepts of c++ as I have already learnt c language. For competitive programming DSA is very important. But I don't know any STL functions.
Is it possible to learn DSA without knowing STL?
Which one is advisory to learn first(STL or DSA) so that it will be easy further?
Also suggest some good references for both stl and dsa.

I think STL (assuming you mean C++ standard template library) is something you sort of learn as you use it. Exposure to DSA (data structures and algorithms) is essential for solving new problems or progressing in CS. Since you are just starting out and partial to C++, any DSA textbook in C++ will be a good reference. Just try to Google search “Data Structures and Algorithms C++,” maybe with your preferred file type.


How hard is a variant of Sudoku puzzle? Sudoku is well known puzzle which is known to be NP-complete and it is a special case of more general problem known as Latin squares. A correct solution of the $N \times N$ square consists of filling every row and every column with numbers from $1$ to $N$ under the condition that every number appears exactly once in any row or any column.

I define a new problem. The input is a correct solution of $N \times N$ Sudoku puzzle (more generally Latin square problem). I would like to decide whether there is permutation of rows and permutation of columns such that no row and no column contains consecutive triples.

An examples for a row without consecutive triple is 9 5 6 2 3 8 4 7 1. An example for a row with consecutive triple is 8 9 5 2 3 4 7 6 1. The triple is 2 3 4.

I suspect the problem is NP-hard but I was not able to find a reduction.

How hard is solving this variant of Sudoku puzzle? Is it NP-complete?

EDIT : To clarify, the same permutation must be applied to the columns and the rows.

When the row and column permutations are different and the consecutive triples have to be increasing: The answer is always YES.

Suppose the matrix has size $N\times N$. Consider a random permutation of the columns. Each row (by itself) is a random permutation. The probability that the numbers $i,i+1,i+2$ appear in positions $t,t+1,t+2$ is $1/(N(N-1)(N-2))$. There are $N-2$ choices for $t$ and $i$, and $N$ different rows. Therefore the expected number of consecutive triples is $N(N-2)^2/(N(N-1)(N-2)) < 1$. We conclude that there is some permutation of the columns, under which there are no consecutive triples in any of the rows. Now repeat the same argument for the columns - note that permuting the rows cannot create a consecutive triple in any of them.

When the row and column permutations are the same, and consecutive triples can be either increasing or decreasing: The answer is still YES, for large enough $N$.

The idea is to use the lopsided version of the Lovász local lemma, via Lu and Székely's paper Using Lovász local lemma in the space of random injections. In the earlier proof, we considered events $X_{\ell,i,t,\sigma}$ for $\sigma \in \{\pm 1\}$, which for a line $\ell$ (either a row or a column), state that $\ell(i+\sigma\delta)=t+\delta$ for $\delta \in \{0,1,2\}$. These are examples of the canonical events considered by Lu and Székely: if the random permutation (permuting both rows and columns) is $\pi$, then they are of the form $\pi(t)=j_0,\pi(t+1)=j_1,\pi(t+2)=j_2$, where $j_\delta = \ell^{-1}(i+\sigma\delta)$. Two events $X_{\ell,i,t,\sigma},X_{\ell',i',t',\sigma'}$ conflict if $\{t,t+1,t+2\} \cap \{t',t'+1,t'+2\} \neq \emptyset$ or $\{j_0,j_1,j_2\} \cap \{j'_0,j'_1,j'_2\} \neq \emptyset$ (this is actually only a necessary condition). Each event conflicts with at most $2N\cdot 2\cdot 2\cdot 5 - 1= 40N-1$ other events ($2N$ lines, two orientations, two ways to conflict, five conflicting positions). While non-conflicting events are in general dependent, using the lopsided version of the Lovász local lemma we can ignore this, and let our dependency graph include edges only for conflicting events. Since the probability that each event happens is $p = 1/(N(N-1)(N-2))$ and the size of each neighborhood is $d \leq 40N-1$, the lemma applies whenever $ep(d+1) \leq 1$, that is
$$ 40eN \leq N(N-1)(N-2). $$
This condition is satisfied for $N \geq 12$. We conclude that for $N \geq 12$, the required permutation always exists. Using the recent constructive version of LLL, we can even find it efficiently.


Will hardware/implementation affect the time/space complexity of algorithms? I’m not even a CS student, so this might be a stupid question, but please bear with me...

In the pre-computer era, we can only implement an array data structure with something like an array of drawers. Since one have to locate the drawer with corresponding index before extracting the value from it, the time complexity of array lookup is $O(log(n))$, assuming binary search.

However, the invention of computers made a big difference. Modern computers can read from their RAM so fast that we now consider the time complexity of array lookup to be $O(1)$ (even it’s technically not the case, because it takes more time to move the register over a greater distance, etc)

Another example is Python dictionaries. While one might get a dictionary access complexity of $O(n)$ with an ill-written overloaded __hash__ magic method (or ridiculously bad luck, i.e. keys having lots of hash collisions), it’s usually presumed to be $O(1)$. In this case, time complexity depends on both the hash table implementation of Python dictionaries, and the keys’ implementation of the hash functions.

Does this imply that hardware/implementation can affect the time complexity of algorithms? (While both examples are about data structures instead of algorithms, the latter are built on the former, and I've never heard of time complexity of data structures, so I'm using the term "algorithms" here)

To me, algorithms are abstract and conceptual, whose properties like time/space complexity shouldn’t be affected by whether they’re implemented in a specific way, but are they?

Sure.  Certainly.  Here's how to reconcile your discomfort.

When we analyze the running time of algorithms, we do it with respect to a particular model of computation.  The model of computation specifies things like the time it takes to perform each basic operation (is an array lookup $O(\log n)$ time or $O(1)$ time?).  The running time of the algorithm might depend on the model of computation.

Once you've picked a model of computation, the analysis of the algorithm is a purely abstract, conceptual, mathematical exercise that no longer depends on hardware.

However, in practice we usually want to pick a model of computation that reflects the reality of our hardware -- at least to a reasonable degree.  So, if hardware changes, we might decide to analyze our algorithms under a different model of computation that is more appropriate to the new hardware.  That is how the hardware can affect the running time.

The reason this is non-obvious is because, in introductory classes, we often don't talk about the model of computation.  We just implicitly make some assumptions, without ever making them explicit.  That's reasonable, for pedagogical purposes, but it has a cost -- it hides away this aspect of the analysis.  Now you know.


Understanding of big-O massively improved when I began thinking of orders as sets. How to apply the same approach to big-Theta? Today I revisited the topic of runtime complexity orders – big-O and big-$\Theta$. I finally fully understood what the formal definition of big-O meant but more importantly I realised that big-O orders can be considered sets.

For example, $n^3 + 3n + 1$ can be considered an element of set $O(n^3)$. Moreover, $O(1)$ is a subset of $O(n)$ is a subset of $O(n^2)$, etc.

This got me thinking about big-Theta which is also obviously a set. What I found confusing is how each big-Theta order relates to each other. i.e. I believe that $\Theta(n^3)$ is not a subset of $\Theta(n^4)$. I played around with Desmos (graph visualiser) for a while and I failed to find how each big-Theta order relates to other orders. A simple example Big-Theta example graphs shows that although $f(n) = 2n$ is in $\Theta(n)$ and $g(n) = 2n^2$ is in $\Theta(n^2)$, the graphs in $\Theta(n)$ are obviously not in $\Theta(n^2)$. I kind of understand this visually, if I think about how different graphs and bounds might look like but I am having a hard time getting a solid explanation of why it is the way it is.

So, my questions are:

Is what I wrote about big-O correct?
How do big-Theta sets relate to each other, if they relate at all?
Why do they relate to each other the way they do? The explanation is probably derivable from the formal definition of big-Theta (might be wrong here) and if someone could relate the explanation back to that definition it would be great.
Is this also the reason why big-O is better for analysing complexity? Because it is easier to compare it to other runtimes?

Is what I wrote about big-O correct?

Yes.

  How do big-Theta sets relate to each other, if they relate at all?

They are a partition of the space of functions. If $\Theta(f)\cap \Theta(g)\not = \emptyset$, then $\Theta(f)=\Theta(g)$. Moreover, $\Theta(f)\subseteq O(f)$.

  Why do they relate to each other the way they do? The explanation is probably derivable from the formal definition of big-Theta (might be wrong here) and if someone could relate the explanation back to that definition it would be great.

A function $f$ is in $\Theta(g)$ if and only if there are constants $c_1,c_2>0$ such that $c_1 g(n)\leq f(n) \leq c_2g(n)$ for all sufficiently large $n$. Seeing that the above relation holds is a simple case of doing some substitutions:

Suppose there is some $a\in \Theta(f), a\in \Theta(g)$ and $b\in \Theta(f)$, then we know there exist constants such that (for sufficiently large $n$)

$c_1 f(n)\leq a(n) \leq c_2f(n)$

$c_3 g(n)\leq a(n) \leq c_4g(n)$

$c_5 f(n)\leq b(n) \leq c_6f(n)$

then

$c_5 c_3 g(n)/c_2 \leq c_5 a(n)/c_2 \leq c_5 f(n)\leq b(n)\leq c_6f(n)\leq c_6 a(n)/c_1\leq c_6c_4g(n)/c_1$

and thus $b\in \Theta(g)$.

  Is this also the reason why big-O is better for analysing complexity? Because it is easier to compare it to other runtimes?

It is not "better". You could say it is worse, because an algorithm being $\Theta(f)$ implies that it is $O(f)$ (but not vice-versa), so "$\Theta$" is a strictly stronger statement than "$O$".

The reason "$O$" is more popular is because "$O$" expresses an upper bound on the speed of an algorithm, i.e., it is a guarantee it will run in at most a given time. "$\Theta$" also expresses the same upper bound, but, in addition, also expresses that this upper bound is the best possible upper bound for a given algorithm. E.g., an algorithm running in time $O(n^3)$ can actually turn out to also run in $O(n^2)$, but an algorithm running in time $\Theta(n^3)$ can not also run in $\Theta(n^2)$ time.

From a practical perspective, if we want to know whether an algorithm is fast enough for a practical purpose, knowing it runs in $O(n^2)$ time is good enough to determine whether it is fast enough. The information that it runs in $\Theta(n^2)$ time is not really important to the practical use. If we have determined that an $O(n^2)$-time algorithm is fast enough for our application, then who cares if the algorithm that was claimed to be $O(n^2)$ is actually $\Theta(n)$?

Obviously, if you are going to give an upper bound on the running time of an algorithm, you will endeavor to give the best possible upper bound (there is no sense in saying your algorithm is $O(n^3)$ when you could also say it is $O(n^2)$). For this reason, when people say "$O$" they often implicitly mean "$\Theta$". The reason people write "$O$" is because this is easier on a normal keyboard, is customary, conveys the most important information about the algorithm (the upper bound on the speed) and people often can't be bothered to formally prove the lower bound.


Finding the rectangle with maximum perimeter weight in a 2D array [Problem Description]:

Given an array of size $N \times N$, the task is to find the rectangle with maximum perimeter weight in the array. The perimeter is defined as the number of cells on the sides. The perimeter weight of a rectangle is defined as the sum of all the values lying on the sides of the rectangle.
For example, the above image shows an array of size 5*5. Each cell has a value. The pink cells form the perimeter of the rectangle with upper left cell (0,0) and lower right cell (2,3). The perimeter is 10. The perimeter weight is (1-1+0+4+2+1+0+2-5-1) = 3
I am asked to give:
(1): an $O(N^3)$ algorithm to find a rectangle with the maximum weight.
(2): an $O(N^3)$ algorithm to find a rectangle with the maximum weight with perimeter no greater than a given constant L.
I really have no idea about how to do. Could anyone give me some idea about these 2 problems?
Thanks a lot in advance!

Let us denote the entries of the array by $A(i,j)$.
Fix the first and last rows of the rectangle $i_1,i_2$. For $j_1<j_2$, the perimeter of the corresponding rectangle is
$$
\sum_{i=i_1}^{i_2} [A(i,j_1) + A(i,j_2)] + \sum_{j=j_1}^{j_2} [A(i_1,j) + A(i_2,j)] = \\
\left[\sum_{i=i_1}^{i_2} A(i,j_1) - \sum_{j<j_1} [A(i_1,j) + A(i_2,j)]\right] +
\left[\sum_{i=i_1}^{i_2} A(i,j_2) + \sum_{j \leq j_2} [A(i_1,j) + A(i_2,j)]\right].
$$
Let us denote the first term by $x_{j_1}$ and the second by $y_{j_2}$. Using appropriate precomputation, it is possible to compute the arrays $x_j,y_j$ in $O(n)$. We can also compute $\max_{j_1<j_2} (x_{j_1}+y_{j_2})$ in $O(n)$. In total, for each $i_1<i_2$ we can compute the maximum perimeter in $O(n)$. Since there are $O(n^2)$ choices for $i_1,i_2$, the entire algorithm runs in $O(n^3)$.
This answers your first question. I'll let you check whether these methods can help with the second question.