Minimum number of edges to remove to disconnect two node sets $A$ and $B$ in a directed graph We have directed graph $G$ (not necessarily a DAG), two disjoint sets $A$, $B$, of vertices.
I need to plan an algorithm returning the minimum number of edges that need to be removed, such that there will be no path from any node in $A$, to any node in $B$ and vice versa.

I had the idea using max flow min-cut to find the minimum number of edges needing to be removed such that there won't be a path from $A$ to $B$, and then using the algorithm again on $B$ (so there won't be a path to $A$).
The problem is that the sum of these minimum number of edges isn't necessarily the "global" minimum.

Does there even exist such an algorithm running in polynomial time?

You could try reducing your problem to the directed $s$-$t$ cut problem.

That is, given an instance $G=(V,A)$ of your problem, construct a graph $H$ that is initially a copy of $G$. Then, add to $H$ two new vertices $x$ and $y$, add an arc from $x$ to each $a \in A$ and from $y$ to each $b \in B$; all with a large weight (say $m+1$, where $m = |A|$). The intuition is that an $s$-$t$ cut of $H$ will never use any of the arcs originating from $x$ or $y$ since they are so heavy, but instead only use arcs present in $G$.

You should try to formalize this intuition, i.e., (i) show that the reduction is correct and (ii) show that there is an efficient algorithm for directed $s$-$t$ cut. If both check out, you are done.


Can coq express its own metatheory? I'm learning about language metatheory and type systems, and am using coq to formalize my study.  One of the things I'd like to do is examine type systems that include dependent types, which I understand is very involved: being able to rely on coq would be invaluable.

Since this type system feature (and other, simpler ones) brings the expressive power of my studied system closer to coq's own, I worry that I might run into a bootstrapping problem that might not reveal itself until much later.  Perhaps someone here can address my fears before I set out.

Can coq express its own metatheory?  If not, can it still express simpler systems that include common forms of dependent typing?

It is possible to formalize Coq's logic within Coq but only subsets of the logic have been formalized yet. Relevant contributions are CoqInCoq, PTS, PTSATR, and PTSF.


Obtaining an acyclic graph by removing edges using an algorithm that decides ACYCLIC i don't understand the following:

If there's an algorithm that can decide ACYCLIC in Polynomial time, then there's an algorithm who returns a set of k edges, so that the graph obtained by deleting the k edges is without cycles - in polynomial time.

The algorithm should get a directed graph and a natural k as an input, and output, if there are k edges as needed, a list of k edges, so that the graph obtained from erasing those k edges is cycles. if there are no such k edges, it simply outputs "no".

Question:my question in addition to the answer already given is this part: " then there's an algorithm who returns a set of k edges, so that the graph obtained by deleting the k edges is without cycles - in polynomial time." - what can be this algorithm? how to do it using a turing machine?

Problematic part: I can only use an algorithm that decides ACYCLIC, but it is forbidden to use any other NP-Complete algorithms, and it's running time must be polynomial in regards to its input size.

My attempt: well, to check/decide if a directed graph is ACYCLIC or not, we'll visit it topologically using DFS, then using a stack, we'll traverse edges to see if any edge in the digraph leads back to an edge already visited. if already visited - there's a cycle, if not - there's no cycle.

The algorithm: on an input of a directed graph, to check ACYCLIC:

1)finding an vertex that has only outgoing nodes - if such node doesn't exist - return "graph has cycles"

2)on that node, run DFS and traverse the digraph; add each edge found to a stack. if a vertex is shown twice - return "graph has cycles".

3)if no cycles found, accept.

But, I am not sure how to do it in regards to the algorithm required in the problem(first two paragraphs of the questions - basically, returning a set of k edges, so that by removing them, the graph will be cycles.

would really appreciate knowing how to do it.

thank you very much

Disclaimer This solution assumes that the language $\text{Acyclic}$ is the language that contains exactly all acyclic directed graphs.

It is impossible to achieve this in polynomial time unless $\operatorname{P}=\operatorname{NP}$. The reason is that the problem you have to solve is NP-hard. It is called the directed feedback arc set problem. It is one of Karp's 21 hard problems. On the other hand, finding whether a graph is acyclic can be done with any graph traversal method in polynomial (actually linear) time. Hence, $\operatorname{P}^{\text{Acyclic}} = \operatorname P$. Hence, if you solved the task you are given in polynomial time you would have proven $\operatorname{P} = \operatorname{NP}$.


Efficient algorithms for identifying the diamond fork&join vertices and the diamond pairs in directed acyclic graph? Given a DAG (directed acyclic graph) $G=(V,E)$ without multiple edges, i.e., edges with the same source and target vertices, we define:

A vertex $v_j \in V$ is a diamond-join ($\Diamond_J$) vertex if there exists some other vertex $v_f \in V$ such that there are at least two vertex-disjoint paths (except $v_f$ and $v_j$) from $v_f$ to $v_j$.

Furthermore, we call such a corresponding vertex $v_f$ above a diamond-fork ($\Diamond_F$) vertex. And, we call such a pair $(v_f, v_j)$ above a diamond ($\Diamond$) pair.

An Example:
In the figure below,

$E$ and $F$ are $\Diamond_J$ vertices.
$A$ and $C$ are $\Diamond_F$ vertices.
$(A,E), (A,F)$ and $(C,F)$ are $\Diamond$ pairs.

The problems are:

  How to identify all the $\Diamond_J$ vertices?
  How to identify all the $\Diamond_F$ vertices?
  How to identify all the $\Diamond$ pairs?

The algorithms should be as efficient as possible. For example, are there linear algorithms, i.e., in $\Theta(n + m)$, for them, where $|V| = n, |E| = m$?

My Thoughts:

The first problem is easy: Run DFS on $G$ and the vertices pointed to by cross edges are the $\Diamond_J$ vertices.

I do not know how to solve 2&3 efficiently.

Edit (2016-05-11): I accept the answer by @Chao Xu which solves the third problem in $O(nm)$ (I think it is correct; please peer review it). I am still open to possibly more efficient algorithm for the third problem, like $O(n+m)$.

$G=(V,E)$ is the graph we work on.

Problem 2: $\Diamond_F(reverse(G))=\Diamond_J(G)$, where $reverse(G)$ reverses all the edges of G.

Problem 3:
This can be solved in $O(nm)$ time. For each vertex $s$, find all the pairs $(s,v)\in \Diamond$ in $O(m)$ time. To do this and split every outgoing edge $(s,v)$ with a new vertex $v'$. Namely, delete edge $(s,v)$, and replace it with $(s,v')$ and $(v',v)$. Find the dominator tree with source $s$ in the new graph, which can be done in linear time for dags.

$(s,v)\in \Diamond$ iff $v$ is the children of $s$ in the dominator tree and $v\in V$.


Is this big O notation format correct? $3^n = 2^{(O(n))}$ I am completing a university exercise deciding whether big notations are true or false.

I am stuck on this question :

  $$3^n = 2^{(O(n))}$$

I want to answer False as the format looks incorrect and I have never seen big O notation written is this way.

Is this a valid way to write big O notation?

Sure, that is a correct notation. It is also a correct statement.
Essentially it is a compact way to say the following:

$\exists c>0, \exists n_0 \ge 0 : \forall n>n_0, 3^n \le 2^{c n} $.

You can pick any $c  \ge \log_2 3$ and $n_0 = 0$.


Why graph planarity is important What is the reason to study planar graphs and algorithms on such graphs (as well as algorithms allowing to check a graph's planarity)? Where in industry this knowlege is needed?
I know that planarity arises in microchip design ("wires" intersection). I also found the following excerpt from a lecture notes:

  The study of two-dimensional images often results in problems related to
  planar graphs, as does the solution of many problems on the two-dimensional surface of our earth.
  Many natural three-dimensional graphs arise in scientific and engineering problems. These often
  come from well-shaped meshes, which share many properties with planar graphs.

Where I can read about it in more detail? Or may be you can explain in a few words what exactly these applications are?

For some graph classes $C$, the question "is there a fast algorithm for deciding whether a graph $G$ belongs to class $C$?" is perhaps only of theoretical curiosity. But it can also be argued otherwise: suppose a problem you care about is hard in general, but efficiently solvable for graphs of class $C$. Wouldn't it be nice if you could quickly test if you can use a fast algorithm, instead of always using a slow brute-force, for example?

In general, it is not hard to imagine some graphs arising from applications are naturally planar, like road networks, printed electric circuits, railways, or chemical molecules. For more concreteness, it seems like a good set of keywords is "planar graph applications". One of my first hits was [1] from the domain of computer vision.

[1] Schmidt, Frank R., Eno Toppe, and Daniel Cremers. "Efficient planar graph cuts with applications in computer vision." Computer Vision and Pattern Recognition, 2009. CVPR 2009. IEEE Conference on. IEEE, 2009.


If X reduces to a problem in NP, is X in NP? Let $X$ and $Y$ be problems, and let $X \le_p Y$.  Is it true that
\begin{equation}
Y \in NP \rightarrow X \in NP\ ?
\end{equation}

I do mean $NP$ here, not $NP$-complete or $NP$-hard.

The solution is simple if the reduction from $X$ to $Y$ transforms an instance of $X$ to an instance of $Y$; to verify that a solution to $X$ is correct, we could transform it to an instance of $Y$ and then verify that the transformed instance is a solution to $Y$.

All we know from $X \le_p Y$, though, is that you can solve $X$ with a polynomial number of solutions to $Y$; we're not guaranteed a simple one-to-one transformation.

I suspect that
\begin{equation}
Y \in NP \rightarrow X \in NP
\end{equation}
is true for all $X,Y$ such that $X \le_p Y$, but I would like confirmation, and I would like to know how to prove it.

The answer depends on what you mean by the notation $\le_p$.

If $\le_p$ refers to a Karp reduction (i.e., a many-one reduction), then the answer is "Yes".  It follows from the definition of NP.  See What is the definition of P, NP, NP-complete and NP-hard? to learn more.
Assuming that $\le_p$ refers to a Cook reduction (also known as a polynomial-time Turing reduction), then the answer is "We don't know for sure, but we think not".

In particular, let $X$ be the problem TAUTOLOGY, and $Y$ be the problem SAT.  Then $X \le_p Y$ (we can transform an instance of TAUTOLOGY to an instance of SAT; if you then flip the answer from an algorithm to solve SAT, the result will be the answer to TAUTOLOGY).  We know that SAT is in NP.  However $X$ is co-NP-complete, so $X$ is not likely to be in NP: if $X$ is in NP, then it follows that NP = co-NP, which would be a surprise.  While we can't prove NP $\ne$ co-NP, many/most complexity theorists expect that NP $\ne$ co-NP is true, and from that it would follow that the answer to your question is "No" -- assuming you are referring to Cook reductions.

To learn more about the difference between these two types of reductions and why both notions exist, take a look at the following questions:

What is the difference between these terms?
Can one show NP-hardness by Turing reductions?
https://cstheory.stackexchange.com/q/138/5038
https://cstheory.stackexchange.com/q/686/5038


How to properly solve this Hidden Markov Model problem? I got a an exercise problem which should be seen as a HMM scenario and argument some statements. However I'm quite confused about how to properly solve and argument my solutions.

Problem tells:

Imagine you want to determine the annual temperature centuries of years ago, when of course there wasn't any thermometer or records. So, nature as an evidence is a worth to try resource, we may achieve it by watching at tree's inside rings. There's reliable evidence suggesting that there's a relation among the rings inside trees and temperature.
There will be 2 different temperature states, WARM (W) and COLD (C) and three discretized tree rings sizes: SMALL (S), MEDIUM (M) and LARGE (L).
Some researchers have provided two matrixes:

$\begin{bmatrix}.7 & .3\\.4 & .6\end{bmatrix}$

As transition matrix, so the probability of remaining in COLD state if COLD is present is $.6$ and the probability of passing from COLD to WARM is $.7$.

Also, a second matrix with the relation among the ring's size and the temperature over the year:

$\begin{bmatrix}.1 & .4 & .5\\.7 & .2 & .1\end{bmatrix}$

So, problem asks what I should do to calculate the chance of a sequence (for example):

  SSSMMLLL

To happen. I considered multiplying the 4 distinct cases and so generate a Markov matrix with transitions among trees ring sizes. However I never got a matrix whose rows sum 1 as it should.

How could I solve this?

The Viterbi algorithm solves the problem. It calculates the most probable state sequence for an HMM given an observation sequence. In your example, ring sizes are observations and temperatures are hidden states. I suggest to refer to the Wikipedia article about the Viterbi algorithm (http://en.wikipedia.org/wiki/Viterbi_algorithm). It contains an example of an HMM with 2 hidden states and observations with 3 discrete probabilities.


What other than programming does a computer science degree usually involve? Programming courses are about 30% of my computer science degree. Also at my university, around 15-20% of the degree are applied math courses.

What other areas/fields are covered? For the majority of ABET accredited universities?

The question that inspired this post was "should i study computer science if I'm only interested in programming at this point?"

A computer science education, among answering a lot of "how?" questions, also covers areas whose purpose is to answer most of the "why?" questions. Those are, in my opinion, the most important, mind-opening and motivating for a future computer scientist with a programming background:

Logic
Computer Architecture
Computability
Complexity
Machine Learning and Artificial Intelligence (which are very closely related and are a part of applied math, which you mentioned. These are of great importance on today's market)

see comments for more examples.

Those will give your programming skills a major boost, enrich you with deeper understanding of what's behind the lines of code and thus give you a great advantage when applying for a future job in this area.

Should you study computer science if you are now interested only in programming? I think absolutely yes. You will not lack programming courses for sure, so that's a plus already. Also, you will learn many more interesting things about programming that maybe you haven't yet encountered to figure out that you are interested in them.


How to get Loop invariants to prove program is correct in Hoare logic start off stating the definition of a loop invariant. It is a condition that must be true at the start of the loop and must be true after each iteration of the loop. I understand what it is but i have trouble trying to come up with one.

Here below is a program which i know is correct and I have stated the loop invariant. Could someone please go through explaining simply why this is the loop invariant. I've been looking at it for awhile now but cannot see why the loop invariant is what it is. I am very new to Hoare logic.

{N >=0}//Pre condition

x = 1;

i = 0;

{x == A^i}//Invariant

while (i != N)

{x == A^i || i != N}//Invariant and Guard

x = x * A;

i = i + 1;

{x == A^i} //invariant

{x == A^i    ||    i==N}// Invariant and !Guard

{x == A^N}//Post condition

By definition, an invariant of while guard do c is a property I for which {I && guard} c {I} is a valid Hoare triple.

In your case, it is enough to prove the validity of what you wrote in the body, namely

{x == A^i && i != N}//Invariant and Guard
x = x * A;
i = i + 1;
{x == A^i} //invariant

This can be done using the rules for assignment and composition. Usually, it's best to proceed backwards, from the bottom of the code block, recovering the (weakest) precondition in the process.

{x == A^i && i != N}
{x*A == A^(i+1)}
x = x * A;
{x == A^(i+1)}
i = i + 1;
{x == A^i}

We now get two Hoare assertions one after the other at the top. This means that we proved the validity of

{x*A == A^(i+1)}
x = x * A;
i = i + 1;
{x == A^i}

when we actually need instead

{x == A^i && i != N}
x = x * A;
i = i + 1;
{x == A^i}

For that, we can exploit the weakening rule (AKA "Pre-" or "PrePost" rule). Such rules simply states that we need to prove the implication between the topmost assertion and the other one. Concretely, we need to prove the implication

(x == A^i && i != N)
   ==>
(x*A == A^(i+1))

which trivially follows by arithmetic.


Prove the time complexity of this algorithm of finding longest subarray with maximum value in the middle I'm trying to find time complexity $T(n)$ of the algorithm by a given pseudocode:

1: for i:=1 to N do
2: begin
3:   len := 1
4:   while i - len >= 1 and i + len <= N do
5:   begin
6:     if a[i] > a[i - len] and a[i] > a[i + len] then
7:       len := len + 1
8:     else
9:       break
10:   end
11:   print(i, len)
12: end

I know that the answer is $T(n) = O(n\log n)$ but I struggle to prove that.

From the pseudocode its clear that this algorithm is designed to find the longest subarray with each element smaller then the middle one. (actually this algorithm prints the length of such array for each array element)

I can't prove it formally because I struggle with the content-dependent loop at 5-10, but informally I went like this:
Lets construct the array which will be the worst case for this algorithm.

For the sake of simplicity lets use array with 15 elements and start with array filled with zeros:
$$0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0$$
external loop will execute 15 times and each time the loop 5-10 will perform a single comparison
Now we will do the following: we divide array in two and put maximum value in the middle. Then for each half we will do the same, except the value will be decresed by 1.

We will get the following array:
$$0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0$$

Now, intuitively I can see why this is the worst case for the algorithm and where $logn$ comes from, but I can't prove it properly.

As a side note I would appreciate any pointers toward where one can practice these kind of problems (concrete algorithms time complexity analysis, preferably with answers/explanations)

Let an array $a[1],\ldots,a[n]$ be given. For an index $i$, let $\ell(i)$ be the largest $\ell$ such that $\{i-\ell,\ldots,i+\ell\} \subseteq \{1,\ldots,n\}$ and $a[i]$ is larger than all elements $a[i-\ell],\ldots,a[i-1],a[i+1],a[i+\ell]$. It is not difficult to see that the running time of the algorithm on the array is $\Theta(n + \sum_{i=1}^n \ell(i))$.

This prompts the following definition:

  Given $n$, the quantity $M(n)$ is the maximum of $\sum_{i=1}^n \ell(i)$ over all arrays of length $n$.

Let $a$ be an array for which $M(n)$ is achieved, and let $a[i]$ be an element of maximum value. Then $\ell(i) = \min(i-1,n-i)$. Moreover, since $a[i]$ is not smaller than any other element, we have $\sum_{j=1}^{i-1} \ell(j) \leq M(i-1)$ and $\sum_{j=i+1}^n \ell(j) \leq M(n-i)$. This shows that
$$
M(n) \leq \max_{i=1}^n M(i-1) + M(n-i) + \min(i-1,n-i).
$$
In fact it is not hard to check that equality holds: take the maximum $i$, and combine two arrays attaining $M(i-1)$ and $M(n-i)$ with a larger element in the middle. This gives the recurrence
$$
M(0)=0, \; M(n) = \max_{i=1}^n [M(i-1) + M(n-i) + \min(i-1,n-i)].
$$
This recurrence is A078903. It is intuitively clear that the best choice for $i$ is $\lfloor \frac{n+1}{2} \rfloor$ or $\lceil \frac{n+1}{2} \rceil$.

We can solve the recurrence explicitly: for $0 \leq k < 2^m$, we have
$$
M(2^m+k) = (m-2)2^{m-1}+1+N_2(k),
$$
where $N_2(k)$ is the total number of 1s in the binary expansions of $1,\ldots,k$ (this is A000788). It is known that $N_2(k) = k\log_2 k + O(k)$, and so $M(n) = \Theta(n\log n)$. This asymptotic estimate also follows from the monotonicity of $M(n)$, by considering the cases $k = 0$.

We conclude that the running time of the algorithm is indeed $O(n\log n)$, and moreover this estimate is tight.


Running time of a nested loop with $\sum i \log i$ term So I have the following pseudo-code:

Function(n):
for (i = 4 to n^2):
    for (j = 5 to floor(3ilog(i))):
        // Some math that executes in constant time

So far, I know that to find this i will be calculating

$\sum_{i=4}^{n^2}\sum_{j=5}^{3i \log_{2}i}C$ where $C$ is a constant, but I am completely lost as to how to proceed past the first summation which, if I'm not mistaken, will give me $3C \cdot (\sum_{i=4}^{n^2}(i \log_{2}i) - 5(n^2 - 4))$, but from here I'm lost.  I don't need exact running time, but the asymptotic complexity.

All help is greatly appreciated!  I realize that this might be a duplicate, but I haven't been able to find a nested for loop problem of this nature anywhere...

$$F(n) = \sum\limits_{i = 4}^{n^2} \sum\limits_{j = 5}^{3i\log i}C = C\sum\limits_{i = 4}^{n^2}(3i\log i - 4) = 3C\sum\limits_{i = 4}^{n^2}i \log i - \Theta(n^2)$$

For asymptotic analysis, we can start the summation from $i = 1$ instead of $4$.  Let

$\begin{align}
T(n) &= \sum\limits_{i = 1}^{n^2}i\log i = \sum\limits_{i = 1}^{n^2}\log {i^i} \\
&= \log {1^1} + \log {2^2} + \log {3^3} + \dots + \log {(n^2)^{n^2}} \\
&\le n^2 \cdot \log (n^2)^{n^2} \ \ \text{(there are \(n^2\) terms)}\\
&= 2n^4 \log n \\
&= O(n^4 \log n)
\end{align}
$

Now, since $f(x) = x\log x$ is a continuous increasing function in $x \in [1, \infty)$, you can verify that :
$\int\limits_{1}^{n^2}x\log x \ dx \le \sum\limits_{x = 1}^{n^2}x\log x \ \ $ (changing  $i$ to $x$ simply because $x$ looks better when integrating).

According to Wolfram, $\int\limits_{1}^{n^2}x\log x \ dx = \frac{1}{4}\left(n^4 \log \left({\frac{n^4}{e}}\right) + 1\right) = n^4 \log \left({\frac{n}{e}}\right) + \frac{1}{4}$

Therefore, $\sum\limits_{x = 1}^{n^2}x\log x = \Omega(n^4\log n)$.

Combining the upper and lower bounds, we have $T(n) = \Theta(n^4\log n)$

Overall, $F(n) = \Theta(n^4\log n) - \Theta(n^2) = \Theta(n^4 \log n)$.

So, your loops have complexity $\Theta(n^4 \log n)$.

Remarks:
1. You can show the lower and upper bounds in a similar way by observing that:
$\int\limits_{1}^{n^2}x\log x \ dx \le \sum\limits_{x = 1}^{n^2}x\log x \le \int\limits_{0}^{n^2}(x+1)\log {(x+1)} \ dx$
2. For the above inequalities, you can use the method of Riemann sum (use the left and the right Riemann sums to see the two bounds). Draw unit-width rectangles on an increasing function to see these bounds.
3. I have done some implicit simplifications, such as just ignoring the constant $3C$ term, or starting the summation from $1$ instead of $4$ since we are dealing with $\Theta$. I have also made the common but slight abuse of notation when equating or subtracting $\Theta$ terms, without affecting the answer.


Simulating a TM with a 2-head, right moving TM Is it possible to simulate a regular Turing Machine with a TM with the following specs?

There are two heads, one of which can read, one of which can write
Both heads can only move right
When a head reads (or it writes) it moves right

I know it's possible to simulate a TM that only moves right. But, is it possible to simulate the left moves as well?

Yes you can simulate a standard Turing machine, indeed you can easily simulate a Tag System which is Turing complete (and can simulate a Turing machine with only a polynomial-time slowdown).

Informally to simulate a k-tag system, you keep the write head at the end of the tape (on the first blank symbol) and use internal states to store the production rules; with the read head you can read k symbols, and append the symbols of the corresponding production rule at the end of the tape.

For example if you have a 2-tag system with the following production:

a --> aab

and the tape is:

a b a b c a b c _
^               ^
Read            Write

you can read the first two symbols and apply the production:

a b a b c a b c a a b _
    ^                 ^
    Read              Write

Furthermore it is also easy to see how a k-Tag system can simulate a Turing machine; a hint: use a special symbol to mark the position of the head, and just rewrite (with one symbol of delay) on the right what you read with the read head but on the "new copy" change the symbol on the right of the head marker according to the transition table of the simulated TM and also change the head marker position one step left or right  (and at every "copy cycle" write also two "empty spaces" to allow the expansion of the tape); use internal states to keep track of the copy phase and of the current state of the simulated TM.

For example if you use # to mark the head position and one transition is:

q1, read a -> q2, write b, move left

a c # a a b c a b c _ a _
    ^RH               ^WH (q1 and c are buffered in the internal states)

a c # a a b c a b c _ a _
      ^RH               ^WH (here the "simulated" TM is on symbol "a"
in state q1 and we can apply the transition above)

a c # a a b c a b c _ a # c b _
        ^RH                   ^WH (q2 is buffered in the internal state)

continue with the copy and start another "cycle":

a c # a a b c a b c _ a # c b a b c a b c _
                    ^RH                   ^WH

... let me know if you need more hints.


Interval sorting that avoids covering I have a collection of intervals and I want to sort them so that the order is interpreted as a sort of "z-index". That is, a given interval may or may not be "visible" depending on whether the merge of the intervals to its left (i.e. preceding it in the given order) contains it.

I am looking for an algorithm to search the optimal ordering, that maximizes the number of visible intervals.

Context: the intervals are spans of text (that all contain a given keyword) and I want to color them using CSS cascading behavior so that all regions are at least partially visible.

Example

A phrase: "The quick brown fox jumps over the lazy dog"

The intervals: ["quick brown fox", "fox", "fox jumps over", "fox jumps over the lazy dog"].

An optimal sorting: ["fox", "quick brown fox", "fox jumps over", "fox jumps over the lazy dog"] (all 4 intervals are "visible")

Non optimal sortings: for instance, any sorting where "fox" is not the first element (so there'd be at most 3 visible intervals).

If no two intervals end at the same point then you can simply sort them in increasing order of their right endpoint, and all of them will be visible.

If more than two intervals can end at the same point, then sort the intervals $[a,b]$ in increasing order of $b$ and break ties in decreasing order of $a$.

Assume w.l.o.g., that there are no identical intervals (you can discard multiple copies of the same interval, since at most one copy will ever be visible). We will show that the above algorithm is optimal with an exchange argument.
Suppose that an optimal order $S$ of the intervals places two intervals in a different order than the one computed by the algorithm. Let $[a,b]$ and $[a',b']$ be the first two consecutive intervals in $S$ that are in the "wrong" order, that is:

$b>b'$; or
$b=b'$ and $a<a'$.

we will show that $[a,b]$ and $[a',b']$ can be swapped without decreasing the number of visible intervals.

If $[a,b]$ is not visible, then swapping $[a',b']$ with $[a,b]$ cannot decrease the number of visible intervals. Therefore we assume that $[a,b]$ is visible.
Let $p \in [a,b]$ be the largest point that is not covered by any the intervals preceding $[a,b]$.

If $p \not \in [a',b']$, then swapping $[a',b']$ with $[a,b]$ yields a solution $S'$ in which (i) $[a,b]$ is visible in $S'$, and (ii) if $[a',b']$ is visible in $S$ then it is visible in $S'$. Assume then that $p \in [a',b']$.

If $[a',b']$ is not visible then swapping $[a',b']$ with $[a,b]$ yields a solution in which $[a',b'] \ni p$ is visible (therefore the number of visible intervals cannot decrease). Assume then that $[a',b']$ is visible.

If $[a,b] \supset [a',b']$ then $[a',b']$ would not be visible, therefore we are in the first case ($b>b'$). By the choice of $p$, all the points of the subinterval $(p,b]$ of $[a,b]$ are not visible. Therefore $S$ must contain an interval $[a'',b'']$ that precedes $[a,b]$ and is such that $b'' \ge b$ and $a'' > p$.
This cannot happen since $[a'', b'']$ and $[a, b]$ is a pair of intervals in the wrong order which appears before the pair $[a,b]$ and $[a', b']$ in $S$.


Tree search returning parents and children I've a flat structure where a node references its parent instead of children

class Node(int Id, Node Parent, string Data);

Given a list of all nodes, and a search condition, I want to return the matches plus all ancestors and descendants

This what I'm trying to implement https://hshn.github.io/angular-ui-tree-search/

What would be a reasonably efficient algorithm to achieve this? I was aiming to build a tree as described here https://stackoverflow.com/questions/444296/how-to-efficiently-build-a-tree-from-a-flat-structure, and replicate the algorithm from the angular library above but it went over my head with all that OOP'ness

Given a tree, expressed with parent pointers, you can easily add child pointers: just traverse all nodes, and when you encounter a node $n$, look up its parent $p$, then add a child pointer from $p$ to $n$.

Given a tree and a search condition, you can find all matches by iterating over all nodes to see which ones satisfy the search condition.  If you've augmented the tree to contain both parent pointers and child pointers, for each matching node, you can return its parent and its children using those pointers.


Solving a recurrence relation using Divide and Conquer Master Theorem For the recurrence relation

$$T(n) = 16T(n/4) + n!\,,$$

I have found that $T(n)\in Θ(n!)$.
Can this be deduced using the Master Theorem?

Yes. Recall that the Master Theorem deals with recurrences of the form
$$
T(n) = a\cdot T\left(\frac{n}{b}\right)+f(n)
$$
In your particular case you have $a = 16$, $b=4$ and $f(n) = n!$.

Then we decide the complexity by comparing $f(n)$ to three functions of $n$, $a$ and $b$ (really we compare it basically the same function, with a $\log$ wiggle room, but in different ways).

In particular the third case holds where $f(n) \in \Omega(n^{c})$ where $c > \log_{b}a$. You have that $\log_{b}a = \log_{4}16 = 2$, so you have to prove (or at least convince yourself, depending on how rigorous you're being) that $n! \in \Omega(n^{c})$ for some $c > 2$.

It should be reasonably clear that you can pick any constant $c$ in this instance, and that this case holds. As it does, we get immediately (which is of course the point of the Master Theorem) that $T(n) \in \Theta(f(n))$, which in this case gives $T(n) \in \Theta(n!)$.


Best case for sorting algorithm Given this sorting algorithm:

Sort(A, n):
    if (n == 1)
     return
    isSorted = true
    for i=1 to n-1 do:
        if (A[i] > A[i+1]):
            isSorted = false
            temp = A[i]
            A[i] = A[i+1]
            A[i+1] = temp
    end for
    if (isSorted)
         return
    else
         Sort(A, n-1)

I'm required to find the upper bound for the best case.
My question is - is the best case considered when the array length is 1? Or when the array is already sorted and then the loop runs only once? Or both cases?

Also, I need to find a recursive formula for the worst case.
I got to this formula:

if n $\neq1$
$F(n) = F(n-1) + n - 1$
else
F(n) = 1

Is it correct?

We usually measure the running time of algorithm as a function of the length of the input.

For example, when we say that an algorithm runs in time $O(n\log n)$, what we mean is:

For every input of length $n$, the algorithm runs in time $O(n\log n)$.

This is an example of worst-case complexity. In your case, you are looking for a function $T(n)$ which satisfies the following:

For every input of length $n$, the algorithm runs in time at least $T(n)$.
Furthermore, for each $n$ there exists an input of length $n$ on which the algorithm runs in time $T(n)$.

To answer your particular questions: the answer should be a function of $n$; and we are looking for the "best-case scenario" of the algorithm for each input length $n$. Whether this best-case scenario is the one you said or not, depends on the algorithm. There might be algorithms for which your best-case scenario is actually a worst-case input (we can construct such algorithms artificially).


Decision variation of max sat I am trying to prove that following decison variation of MaxSAT is both NP hard and co-NP hard.
$(\phi ,k) \in L$ iff an assignment of $\phi$ satisfies k clauses and no assignment satisfies more than k clauses.

I think we can show that NP hardness by reducing SAT to L by setting k=m (number of clauses). But I can't reduce $\overline{SAT}$ to L. Is that reduction possible?

Given a $\overline{SAT}$ instance $\psi$ with $m$ clauses, let $\phi$ be the formula formed by adding to each clause a new variable $x$ (the same for all clauses), and a new clause $\bar{x}$. If $\psi$ is satisfiable then $\phi$ is satisfiable, whereas if $\psi$ is unsatisfiable then the maximum number of clauses that can be satisfied is $m$.


Are semantic networks ontologies? I struggle with few definitions in knowledge representation and seek credible help to distinguish between them. I have been searching on wikipedia and many websites for the difference between ontologies and semantic networks (not to be confused with semantic web). While the wikipedia page on semantic network never refer to ontologies, they seem extremely similar and have similar application in CS.

My guess is that semantic network are a type of ontology adapted for research on AI. However, I don't know the difference between both. So my question is simply:

Are semantic networks ontologies? If so, are they synonym? or what are the distinctions?

A semantic network is a graphic notation for representing knowledge in patterns of
interconnected nodes and arcs. It is one way for knowledge visualization and presentation. It was used firstly for for artificial intelligence and machine translation in computer science. What is common to all semantic networks is a declarative graphic representation that can be used either to represent knowledge or to support automated systems for reasoning about knowledge.

Ontology is a representation vocabulary, specialized to some domain or subject. It is a representation of a set of concepts within a domain and the relationships between those concepts. It is used to reason about the properties of that domain, and may be used to define the domain.

You can find more in references as (specially 4):

1)  Sowa, John F., ed. “Principles of Semantic Networks: Explorations in the Representation
of Knowledge”, Morgan Kaufmann Publishers, San Mateo, CA, 1991.

2) Noy N.F., McGuinnes D. L. “Ontology Development 101: A Guide to Creating Your
First Ontology”. Stanford Knowledge Systems Laboratory Technical Report KSL−01−05 and
Stanford Medical Informatics Technical Report SMI−2001−0880, March 2001.

3)María Auxilio, “An Overview of Ontologies”, Center for Research in Information and Automation Technologies Technical Report, Interactive and Cooperative Technologies Lab, Universidad De Las Américas Puebla, México, March 2003.

4) ABDEL-BADEEH M. SALEM, MARCO ALFONSE "Ontology versus Semantic Networks for Medical Knowledge Representation", ICCOMP'08 Proceedings of the 12th WSEAS international conference on Computers, 2008.


How to read this inductive language definition? A language $L$ is defined recursively according to the following rules:

$λ ∈ L$
If $w ∈ L$, then $bw ∈ L$ and $waa ∈ L$

I am not sure if strings from this language should mix from this definition. Would strings only consist of $bbbb$ and $aaaa$, or can it also consist of $bbaa$, $aabb$, and so on?

The recursive definition implies that a word $w$ is in $L$ if there is a sequence $w_0,\ldots,w_n=w$ such that $w_0$ is the empty word and for each $i=1,\ldots,n$, either $w_i = bw_{i-1}$ or $w_i = w_{i-1}aa$. This, in turn, implies that $L = b^*(aa)^*$.


Chinese Postman Problem: finding best connections between odd-degree nodes I am writing a Program, solving the Chinese Postman Problem (also known as route inspection problem) in an undirected draph and currently facing the problem to find the best additional edges to connect the nodes with odd degree, so I can compute an Eulerian circuit.

There might be (considering the size of the graph that wants to be solved) an enormous combination of edges which need to be computed and evaluated.

As an example there are the odd-degree nodes $A, B, C, D, E, F, G, H$. The best combinations could be:

$AB$, $CD$, $EF$, $GH$
$AC$, $BD$, $EH$, $FG$
$AD$, $BC$, $EG$, $FH$
$AE$ ....

where $AB$ means "edge between node $A$ and node $B$".

Therefore my question is: is there a known algorithm to solve that problem in a complexity better than pure brute force (computing and evaluating them all)?

€:After some research effort I found this article, speaking about the "Edmonds' minimum-length matching algorithm" but I cannot find any pseudo-code or learners-descriptions of this algorithm (or at least I do not recognize them, as Google offers a lot of hits an matching algorithms by J. Edmonds)

As remarked in the comments, Wikipedia gives a reduction from route inspection to minimum-weight matchings.  Vladimir Kolmogorov has published a fast implementation of the weighted version of Edmonds' blossom algorithm, in C++ [1].

[1] V. Kolmogorov, Blossom V: A new implementation of a minimum cost perfect matching algorithm. Mathematical Programming Computation, 1(1):43–67, 2009.


Proving time complexity of $T(n) = 2T(n/3 + 1) + n$ I am working on proving the time complexity for the following problem, but believe I am stuck:

$$T(n) = 2T(n/3 + 1) + n$$

I have checked out this link here on time complexity on cs.stackexchange

However, I still cannot seem to find the answer. Using this proof from a Dartmouth course:

$a = 2, b = 3, c = 1$

In this case, I know logb a is .63, which is less than 1, so the complexity is $Θ(n)$. However, I don't know how to prove that.

I am trying to practice with the methods that I "know" - Master Theorem, Substitution, Iteration, or a Recursion Tree. And using one of those 4 methods, I can't find a way to prove the complexity is $Θ(n)$, even though I know that's the answer.

Would anyone be able to assist?

You can use the Akra–Bazzi theorem, a generalization of the master theorem.

Using the notations in the Wikipedia page:

$g(x) = x$
$k = 1$
$a_i = 2$
$b_i = 1/3$
$h_1(x) = 1$ (in fact, probably $h_1(x)$ is a bit different, since $n/3+1$ isn't always an integer)
$x_0$ is a constant which is missing from your recurrence relation

You can easily check that all conditions of the theorem hold. To get the asymptotics, we first compute the value of $p$, which is the solution to $2(1/3)^p = 1$, that is, $p = \log_3 2$. Next, we calculate the integral appearing in the answer formula:
$$
\int_1^x \frac{u}{u^{p+1}} \, du = \int_1^x u^{-p} \, du = \frac{x^{1-p}-1}{1-p}.
$$
We conclude that
$$
T(x) = \Theta\left(x^p\left(1 + \frac{x^{1-p}-1}{1-p}\right)\right) =
\Theta(x^p + x) = \Theta(x^{\max(p,1)}).
$$
Since $p < 1$, the answer is $T(x) = \Theta(x)$.

More generally, the Akra–Bazzi theorem shows that the master theorem applies even when the applications of $T$ on the right-hand side of the recurrence are off by a small amount (at most $O(x/\log^2 x)$).


Applications of Four Color Theorem I tried finding real life applications for the Four Color Theorem (except for coloring maps) but couldn't find anything useful and well illustrated. For example I found this:

Graph coloring problems are widely applicable to the problem of scheduling.
Consider a university, where you are trying to schedule times for all of the final exams. Some students are taking more than one class, so you want to make sure they don't have two exams scheduled at the same time. However, you want your exam writing period to be as short as possible, to run as many exams concurrently as you can.
You can represent this as a graph coloring problem: construct a graph in which each class is a vertex, and there is an edge between vertices any time a two classes contain the same student. Your colors will represent different exam timeslots. The minimum number with which you can color that graph is the smallest number of timeslots you need to write all your exams.
source: jmite on cs.se.

However, I don't really get how it works! Also if you could give more examples related with graph theory and four color theorem

Explanation of the graph coloring problem stated above:

So each vertex represents a class. Each edge represents a timing conflict between two classes. Suppose there was a graph with 4 vertices and a single edge between two. This would require only 2 colors, which translates to two time slots. Draw this graph. Write out a few scenarios of class schedules and draw their corresponding graphs to get a better idea. Answer the question on whether or not these graphs are planar. If so, what does that mean w.r.t. the four color theorem?


Push relabel why return back to source In push relabel algorithm, at the end excess at any nodes is pushed back to source by raising height of those nodes above the height of source. Why is this done? In CLRS it's mentioned:

  To make the preflow
  a “legal” flow, the algorithm then sends the excess collected in the reservoirs of
  overflowing vertices back to the source by continuing to relabel vertices to above
  the fixed height |V| of the source. As we shall see, once we have emptied all the
  reservoirs, the preflow is not only a “legal” flow, it is also a maximum flow.

What does it mean to say "to make preflow a legal flow". Could someone elaborate on the same.

Inspecting the correctness proof and/or executing any non-trivial example, you'll note that push-relabel algorithms are different from Ford-Fulkerson and variants in that they do not maintain a flow; that's just not part of the invariant, and it's blatantly violated right at the start.

This whole "push flow to the sink, then push the excess back to the source" idea is only that: an idea. The algorithm does not really work like that, always. But it's still useful.

Once the "wave" reaches the sink $t$, it saturates the cut $V \setminus \{t\}$. You still have vertices with excess left¹, though; the conservation of flow property is violated. This has to be remedied before we can terminate with a flow -- hence the "push flow back to the source" phase.

Whenever the cut $V \setminus \{s\}$ is not by coincidence a min-cut.


Environment detection - How to detect "city" versus "landscape" background environment in computer vision? I'm searching for computer vision or machine learning algorithms/methods that are used to classify or differentiate two outdoor environments. Given an image with vehicles, I need to be able to detect whether the vehicles are in a natural open landscape (desert, in particular), or whether they're in the city.

I've searched but can't seem to find relevant work on this. Perhaps because I'm new at computer vision, I'm using the wrong search terms.

Any ideas? Is there any work (or related) available in this direction?

Think of what different features the desert has compared to an urban environment. The desert is probably restricted the a limited set of colors/hues. It is limited to mostly smooth textures. It lacks "man-made" geometries such as straight lines from building edges etc.

So you should be able to differentiate between desert and urban environment by looking at the color components (both the number of colors and the variation), textures and the amount of prominent straight lines/edges in the environment.

By googling "image processing classify outdoor environment" I found the paper Automatic Classification of Outdoor Images by Region Matching which can be a good starting point for reading up on environment classification. They seem to base the classification mostly on color and texture features.

These are just general ideas but hopefully they can help you get started. Good luck.


For what applications of the traveling salesman problem, does visiting each city at most once truely matter? Traditionally, the traveling salesman problem has you visit a city at least once and at most once.

However, if you were an actual traveling salesman, you would want the least cost route to visit each city at least once, and you wouldn’t be bothered visiting a city 2, 3, or more times. For  given city, you might stop and hawk your wares only once, and on subsequent visits, only drive through the city without stopping.

Consider an undirected graph having a city incident to exactly two  edges. The cost on one of these edges is only 10 units, while the cost on the other is 99,999,999,999. If you insist on visiting each city at most once, then you are forced to incur the cost of the high cost edge. However, if you allow yourself to visit cities multiple times, then you simply leave the way you came in (on the low cost edge). The low cost edge leads you back to a city you've passed through before.

The traveling salesman problem is highly contrived for an actual traveling salesman. I want to give students an application for which there's a real incentive to visit each city at most once. For what applications is visiting each city a critical aspect of the problem?

Your conceptual difficulty stems from not distinguishing between TSP and Weighted Hamiltonian Cycle. These are usually discussed as if they are the same problem, but they're not.

In Weighted Hamiltonian Cycle, we are given a graph with nonnegative edge weights and we wish to determine the minimum-weight Hamiltonian cycle, i.e., the minimum-weight cycle that includes every vertex exactly once, and which therefore doesn't repeat any edge. That's just the definition; it's a problem about graphs and it may or may not correspond to any particular problem in the real world.

In TSP, we are given the cities and the matrix of distances between them. That's all the values are: distances. In particular, there is a distance between every pair of cities, regardless of what the road network looks like. You need to visit each city and your job is to choose the order in which to visit them, to minimized the total journey length. For example, consider the following distances:

                 B    P    W
Baltimore        -   100   40
Philadelphia    100   -   140
Washington DC    40  140   -

The shortest route is to, say, start in Philadelphia, drive to Baltimore, drive to DC, then drive back to Philadelphia.  If the distances look a bit strange, it's because I-95 runs from Philadelphia to DC and passes through Baltimore.  This means that "then drive back to Philadelphia" means passing through Baltimore again. This doesn't matter, because TSP isn't modelling that. It's just modelling visiting each city and completely ignores what happens en route between cities, except for the distances.

In contrast, if you represented this as the graph

    40       100
W ------ B ------- P

then there is no Hamiltonian cyle at all.  This doesn't correspond well to the idea of travelling between cities: as you rightly ask, why not allow yourself to drive back through Baltimore?  Should we add in a road from Washington to Philadelphia that doesn't go via Baltimore? That seems weird, as it would be longer. Why force yourself to do that? TSP isn't Weighted Hamiltonian Cycle.

The formal relationship between the two problems is that TSP is the restriction of weighted Hamiltonian path to the case where the graph is complete.  Alternatively, you can associate a weighted Hamiltonian path instance as corresponding to the TSP instance where there's one city per vertex and the distance between two cities is the length of the shortest path between the corresponding vertices.

Note that, in the above, I've referred to the "distance" between cities.  Even more formally, one should talk about an abstract "cost".  The distinction is that distance sounds a lot like it ought to be symmetric and obey the triangle inequality, which corresponds to metric TSP. Cost isn't necessarily either of those things.


Systematic approach or algorithm for designing a pushdown automata that accepts a langauge I understand that designing automatons is mostly a creative process but, a month ago I was having a discussion with a classmate about designing a NPDA or a DPDA that accepts a non-trivial language (trivial meaning, it is straightforward to design a PDA that accepts it) and he gave me a solution while mentioning an algorithm that he used to arrive at said solution.
his solution was correct but used nearly twice the number of states than my solution which was also correct (both solutions used NPDAs). unfortunately I don't have access to him to ask about what he meant by an algorithm, anymore.

I looked in both Sipser and Linz books and I didn't find anything about such an algorithm or systematic approach.

If you know of such thing please demonstrate with your own language of choice.

Your question is something very natural, that comes up a lot when first encountering computational model.
The main problem is that your question does not "compile":

You ask if there is an algorithm that constructs PDAs. What would be the input for such an algorithm? This is the main crux of the problem.

Until you specify that, you won't really have an answer. As Yuval commented, if you get a CFG as input, then there is an easy procedure to convert it to a PDA.

Let's look at the other extreme: suppose you are given a Turing Machine, and you just ask whether there exists a PDA for its language (even without constructing it). As it turns out, this problem is undecidable (it's an immediate consequence of Rice's theorem, but in fact it's neither in RE nor in coRE).

This problem is something that often comes up in designing computational models - how do we specify what we want? If we give a rich specification formalism, such as Turing machines, then things become undecidable. And if we give something too poor, such as CFGs, then the construction task becomes easy, but writing down the specification becomes the hard part, so it's debatable whether we actually did any good...


Proving NP hardness about graph creation problem with triangle number I have graph creation problem.

Given a set of nodes of graph, and node constraints such as given every node's number of neighbors (degree). I am also provided with the total number of triangles in the graph. Given the above constraints ($n+1$), I have to generate a graph that satisfies all the constraints.

I know that given nodes' degrees, it is possible to construct using Havel–Hakimi algorithm a graph satisfying node degrees. But I am not sure how to fulfill the total triangle count constraint and if it makes the problem NP-hard.

This is just a begining of reflexion. I hope it will help. This is not a solution for the very general case but some points that can reduce the problem.

If you consider triangles as unique 3-cliques, you know how many triangles are provided by a k-clique:

3-clique : 1 triangle
4-clique : 4 triangles
5-clique : 10 triangles
k-clique : C(k, 3) triangles

Thus the number of triangles you have to provide is a combination of these numbers: N = 1*a + 4*b + 10*c ...

You also know that building a clique requires nodes with sufficient neighboors. A k-clique requires k nodes having k-1 edges. And any node with only one edge cannot create any triangle.

On a short example :
10 nodes with (5, 5, 4, 4, 3, 3, 2, 2, 1, 1) edges. A 5-clique is not possible. I think this can do up to 12 triangles with 3 different 4 cliques (5, 5, 4a, 4b), (5, 5, 4a, 3a), (5, 5, 4b, 3b). The remaining (2, 2, 1, 1) cannot provide any triangle.


Is the following extension of finite state automata studied? Consider a finite state machine as usual, but every transition, it can also update an integer counter by adding or subtracting a number.
Say, a transition function of the form
$\delta(q,a) = (p,k)$
moves to the new state $p$, and add $k$ to the counter, where $k \in \mathbb{Z}$ (so $k$ can be positive, negative, or zero).

A string is accepted if the final state and the counter value is in $F$, where $F$ is a finite set of pairs of states and counter values.

Is this model known? I could not find any reference of this particular extension.

Assuming $k$ can be any integer, then this can be formalized as a blind one-counter automaton. Usually these automata accept on final state when its counter is zero, but we can easily model your acceptance type if you allow $\epsilon$ transitions (that do not consume input). If I am not mistaken, like with finite state automata, one can get rid of the $\epsilon$, but that is a non-trivial result.

There are several types of one-counter automata. In the most general form they are allowed to test whether the value of the counter equals zero.
The languages they accept are a strict subset of the context-free languages.

The model you are probably looking for is called blind, it cannot test for zero, except as the final test for acceptance at the end of the computation.


Average Intelligence Quotient of Computer Scientists? Have there been studies measuring the average IQ of successful computer scientists/programmers? The US military uses the AFQT test to determine intelligence of potential recruits (100 million Americans aren't intelligent enough to be accepted, according to the source). But I know of no similar way to gauge the average IQ makeup of computer scientists/programmers. That a considerable number of them have a facility with math and have degrees doesn't suggest that they are necessarily geniuses, but does suggest they would place much higher than the average person on IQ tests. I've known a few people who have pursued computer programming and have given up, And not for lack of effort but due to what they felt was a lack of brainpower necessary to grasp a language.

This is not necessarily the most robust estimation, and is just a blog post (hence I'm not sure it's reliable enough to do anything real with), but here is a posting which uses GRE/SAT scores to estimate IQ across different majors. It puts the average IQ of CS students at ~124.

Another blog post uses GRE/SAT scores again to do the estimate, arriving at 128.5 for CS.

Their original data are from here and here, respectively. I haven't puzzled out yet whether they're using the same base data yet.

Undermining these a little is that there are no supporting statistics (again they are just blog posts, not scientific articles).

I would use these results with a great deal of caution. If nothing else, they appear to be heavily biased to the US setting (simply because of the source data), and given the relatively rapid ups and downs of CS popularity, the data for at least one is somewhat old.


Incorrect proof of closure under the star operation using NFA results in the NFA recognizing undesired strings? I'm currently reading the book Introduction to the Theory of Computation (2nd or 3rd Ed.) by Michael Sipser, and have stumbled upon a question in Chapter 1 - Regular Languages, namely when the author is presenting the proof idea of Theorem 1.49 - "The class of regular languages is closed under the star operation." using NFA.

The approach suggested is that, if we have a regular language $A_1$ and want to prove that $A_1^*$ also is regular, we can take an NFA $N_1$ and modify it into an $N$ as in the image below, which is then a particular NFA recognizing $A_1^*$.

He noted:

  One (slightly bad) idea is simply to add the start state to the set of accept states. This approach certainly adds $ε$ to the recognized language, but it may also add other, undesired strings.

I have drawn the "bad" NFA as below and tried to figure out why this will result in undesired strings. However, I can't find an example of when the an undesired string is recognized. Why will this idea result in the NFA recognizing undesired strings?

Could someone point this out for me or give me a hint, or have I misunderstood the author? Thanks in advance!

Consider a two state automaton for the language $a^*b$, two transitions from the initial state, one looping with label $a$, the other with label $b$ to the final state.

Making the initial state final, would also accept $a^*$.


How does the problem of having a coffee-machine close relate to vertex cover? Meeting rooms on university campuses may or may not contain coffee machines. We would
  like to ensure that every meeting room either has a coffee machine or is close enough to a
  meeting room that does have a coffee machine. (For any two meeting rooms, the architect
  has told us whether or not they are close enough.) Our problem is to determine among all the
  meeting rooms of any university campus, which ones should have coffee machines so that we
  use as few coffee machines as possible. Specify this problem as an optimization problem on a
  graph. Formulate the corresponding Coffee-machine Decision Problem (abbreviated Coffee).
  Prove that the Coffee Machine Decision Problem is NP-complete.

  Hint: You could use Vertex Cover. For every edge, add two more edges and one more vertex.

I'm confused at the hint given and why this problem isn't just a straight reduction from Vertex Cover.  What's the point of adding two more edges and a vertex for every edge?

As I already pointed out in my comment, there is in fact a need for a transformation of the problem. The problem you ask for is not known as vertex cover, but as dominating set.
The proof then goes as follows:

We transform an instance of vertex cover $(V, E, k)$ as follows (we assume that the graph $(V,E)$ is connected). For every edge - just as the hint says - add two edges and one vertex. More precisely, for an edge $uv \in E$, add a new node $w \not\in V$ and edges $vw, wu$ to the graph. The resulting graph constitutes an instance of Coffee in the obvious way, that is, the "close-enough"-relation is represented by edges and the meeting rooms are represented by vertices. Let $(V', E', k)$ denote the instance of coffee produced by the transformation.

We now need to show now that $(V, E)$ has a vertex cover of size $\leq k$ if and only if for $(V', E')$ it suffices to use $\leq k$ coffee machines.

"$\Rightarrow$": Let $v_1, \ldots, v_l, l \leq k$ be a vertex cover of $(V,E)$. It is clear that the same choice of nodes produces a valid choice for coffee machine placement on $(V', E')$, as we assumed $(V, E)$ to be connected.

"$\Leftarrow$": Let $v_1, \ldots, v_l, l \leq k$ be a valid choice for coffee machine placement. WLOG, assume that $\forall i \in \{1, \ldots, l\}: v_i \in V$, for if $v_s \in V' - V$ with $1 \leq s \leq l$, we can obtain another valid choice for coffee machine placement by replacing $v_s$ with $v \in V$ such that $vv_s \in E' - E$, that is, with one of the two nodes "between" which $v_s$ was inserted by the transformation. Note that these two nodes were also precisely the ones that were covered by choosing $v_s$ to have a coffee machine. By construction, there must have been an edge between the two nodes and an edge between $v_s$ and each of the two nodes. So by replacing $v_s$ with one of them, we don't shrink the set of covered nodes.
Then, $v_1, \ldots, v_l$ constitutes a vertex cover of $(V, E)$. To show this, let $uv \in E$. By construction, there is $w \in V' - V$ and $uw, wv \in E' - E$, and no other edges are incident to $w$. As $(V', E')$ covers $w$, one of $u$ or $v$ need must have been chosen as places for a coffee machine, and thus, $uv$ is incident to at least one node in $\{v_1, \ldots, v_l\}$. Thus, $v_1, \ldots, v_l$ is a vertex cover of size $l \leq k$.


What is exactly an empty Sub-array I read the question in Exercise 4.1-4 in Introduction To Algorithms:

Suppose we change the definition of the maximum-subarray problem to allow the result to be an empty subarray, where the sum of the values of an empty subarray is 0. How would you change any of the algorithms that do not allow empty subarrays to permit an empty subarray to be the result?

I cannot get what's an empty sub-array.
I came across the point that a single number can be returned if the array consists of negative elements only.
Please can anyone explain the concept of an empty sub-array? And how can we have an empty sub-array?
Even if a single element is returned it still means that sub-array is not empty. Please clear the doubt.
Edit:
To make it more clear as a question if I take an array of elements:
[-3,-4,-1,-8]

The answer would be -1 or 0?
Please explain if why it should be 0 and how can we conclude an empty sub-array.
Thank you.

If you have this array: $[-2,-10,-5]$, and the problem specifies that you should return to it the sum of the maximum subarray whose length is at least $1$, you will return the sum of the subarray $[-2]$, which is $-2$. So far so good?
Now, focus here because this is where you are most probably having trouble:
The problem is now tweaked. The problem now allows you to return to it an empty subarray, which means, you can return to it a subarray that is empty - a subarray that has no elements. Bear with me:
In mathematics, an "empty sum" is a summation where the number of terms is zero. Verify.
Similarly, in computer science, an "empty subarray" is a subarray in which the number of terms is zero. This is just the definition. It's just a subarray whose sum evaluates to zero.
Now, concerning the tweaked version of the problem, what would be better, returning to it $[-2]$ whose sum evaluates to $-2$, or returning the empty subarray $( [ \ \ \ ] )$ whose sum evaluates to $0$?


Terminology - What does alphanumeric order mean in relation to decimals? It is also called Natural sort order.

  "It's hard to find information on natural sorting"-Jeff Atwood on Coding Horror.

And it seems true today as the Wikipedia entry seems pretty bare.

Definition 1: Non-numeric word-character substrings are sorted lexically, case-insensitively. Numeric substrings are sorted numerically. non words-characters, non-digits are ignored.

Definition 2: Natural sort order is an ordering of strings in alphabetical order, except that multi-digit numbers are ordered as a single character.

The main difference is that Definition 1 allows decimals while Definition 2 does not. For example I have the list ["t8.1", "t8.11", "t8.2", "t7.2", "t7.11"].

Definition 1 would yeild: ["t7.11", "t7.2", "t8.1", "t8.11", "t8.2"].

Definition 2 would yeild: ["t7.2", "t7.11", "t8.1", "t8.2", "t8.11"].

Python's natsorted function was definition 1 until v4.0.0 and now uses realsorted for this behavior. Python's natsorted function currently follows definition 2.

Perl follows definition 1 (which is where I found it.

Php follows definition 2

MATLAB uses definition 2 for non-version numbers.

Dave Koelle implements definition 1 for his examples but says it's a 'glitch' and thus supporting definition 2 as correct. In most the linked code, the code treats '.' as a string but what if it was a decimal in a numeric substring? Dave Koelle notes this as a glitch by saying "There is currently a glitch when it comes to periods/decimal points - specifically, periods are treated only as strings, not as decimal points.".

To me, the word numeric would imply decimals but in practice it seems that this is not the case unless specifically noted to include decimals.

What does Alphanumberic/Natural Order Sort mean exactly without additional qualifiers? For example: In "Natural Order Sort with decimals", "with decimals" would be an additional qualifiers. Which definition is correct for "Natural Order Sort"?

Alphanumberic (Non-Decimal) vs Alphanumberic (Decimal)

Alphanumeric sort means that every character is compared according to ascii representation.
Natural sort treats consecutive digits as one chatacter, so actually compares as integer. There is no place for decimals, but when you compare two numbers in the form $X.Y > W.Z$ it looks like decimal compare.

So what does "natural sort does not compare decimals" really mean?
The example above is just coincidence, like reading month.day as float and sorting will give good order, but adding and subtracting is not defined. Same here, "-" will not be identified as part of decimal, so comparison will be shifted. The separator might be given as anything, but will change results when inconsistent.


Why is $(\log(n))^{99} = o(n^{\frac{1}{99}})$ I am trying to find out why $(\log(n))^{99} = o(n^{\frac{1}{99}})$. I tried to find the limit as this fraction goes to zero.

$$
\lim_{n \to \infty} \frac{ (\log(n))^{99} }{n^{\frac{1}{99}}}
$$

But I'm not sure how I can reduce this expression.

$\qquad \begin{align}
  \lim_{x \to \infty} \frac{ (\log(x))^{99} }{x^{\frac{1}{99}}}
&= \lim_{x \to \infty} \frac{ (99^2)(\log(x))^{98} }{x^{\frac{1}{99}}} \\
&= \lim_{x \to \infty} \frac{ (99^3) \times 98(\log(x))^{97} }{x^{\frac{1}{99}}} \\
&\vdots \\
&= \lim_{x \to \infty} \frac{ (99^{99})\times 99! }{x^{\frac{1}{99}}} \\
&= 0
\end{align}$

I used L'Hôpital's rule law in each conversion assuming natural logarithm.


Two-phase locks: why is it better? I'm reading Arpaci's Operating Systems: Three Easy Pieces, the chapter on Locks.
At the end of the chapter, they present Two-phase locks (section 28.16). They say

A two-phase lock realizes that spinning can be useful, particularly if the lock is about to be released. So in the first phase, the lock spins for a while, hoping that it can acquire the lock.

I understand this may only be useful in a multiprocessor environment, is that right?
Also, it seems a little arbitrary to me to wait the first time and then go to sleep. I mean, I don't see why this would be such a great improvement over going directly to sleep in the case the lock is being held.
Is there anything I'm missing?
Thanks in advance!

Below is the whole paragraph on Two-phase locks:

One final note: the Linux approach has the flavor of an old approach that has been used on and off for years, going at least as far back to Dahm Locks in the early 1960’s [M82], and is now referred to as a two-phase lock. A two-phase lock realizes that spinning can be useful, particularly if the lock is about to be released. So in the first phase, the lock spins for a while, hoping that it can acquire the lock.
However, if the lock is not acquired during the first spin phase, a sec- ond phase is entered, where the caller is put to sleep, and only woken up when the lock becomes free later. The Linux lock above is a form of such a lock, but it only spins once; a generalization of this could spin in a loop for a fixed amount of time before using futex support to sleep.
Two-phase locks are yet another instance of a hybrid approach, where combining two good ideas may indeed yield a better one. Of course, whether it does depends strongly on many things, including the hard- ware environment, number of threads, and other workload details. As always, making a single general-purpose lock, good for all possible use cases, is quite a challenge.

To answer your first question: Spinlocks are only useful in a multiprocessing environment.
Spinning is waiting. If you're waiting for a lock to be released, and it must occur on the current CPU because there are no other CPUs, then a context switch must occur for the lock to be released. It follows that the current thread should just sleep, because it will need to anyway.
Of course, in a single-CPU environment, you can still spin-wait for other types of resource, such as a hardware device.
As Joppy indicated in the comment, putting a thread to sleep is a much heavier-weight operation than sitting in a loop. Whether or not it's worth spinning depends on a bunch of things, such as how expensive it is to sleep and context switch, and how long the lock is likely to be held.
There is a huge design space here. The default behaviour of Solaris kernel locks, for example, is to spin if the owner is running on another CPU, and sleep otherwise, the theory being that if the owner is making progress, it's more likely that the lock may be released soon. As a nice bonus, this automatically does the "right" thing on a single CPU.


Computer Vision - What is spatial histogram/pyramid feature? I am trying to re-implement the model in this paper https://arxiv.org/pdf/1511.02917v2.pdf. But the paper omitted some details in feature extraction (Section 4.1). I am new to computer vision so I am confused when the paper just said they got the spatial feature (1440 dimensional) that corresponds to a 32*32 spatial histogram, combined with a spatial pyramid, to indicate the bounding box location at multiple scales.

I guess a 32*32 spatial histogram is to divide the image into 32*32 regions and concatenate histogram for each small region together? But what does it mean to combine with a spatial pyramid, and how to end up with a 1440 dimensional spatial features.

Spatial histogram.  A simple histogram is obtained by taking a region of an image, assigning a label to each pixel (somehow; via some mapping function), and then computing a histogram of the labels.  The histogram counts, for each possible label, how many pixels received that label.  You obtain a feature vector: a vector of counts, one count per possible label.

Such a histogram doesn't capture any information about where the labels appear.  A spatial histogram addresses that shortcoming by dividing the image up into several smaller patches, computing a histogram for each patch, and concatenating those histograms.  For instance, you could take a 32x32 image and break it up into sixteen 8x8 patches, compute a histogram for each patch, and concatenate them to get a feature vector.

You still have to choose an appropriate matching.  You might choose a texture descriptor, or just the pixel RGB value (quantized appropriately), or something about the direction of the gradient (quantized), or something else.  For more about spatial histograms, see also http://www.answers.opencv.org/question/7207/spatial-histogram/ and the following paper:

Hongming Zhang, Wen Gao, Xilin Chen, Debin Zhao.  Object detection using spatial histogram features.  Image and Vision Computing, vol 24 no 4, April 2006.

Pyramid.  A pyramid allows you to do something at multiple scales.  You start with a 32x32 image and compute a feature vector for it.  Then, you rescale the image down to a 16x16 image and compute a feature vector for it.  Then you rescale down to a 8x8 image and compute a feature vector for that.  And so on.  Finally, you concatenate all of those feature vectors.  This allows you to capture both coarse features (from the highly downscaled images) as well as fine features (from the large images).

For more about pyramids, see https://en.wikipedia.org/wiki/Pyramid_%28image_processing%29.


Why is the unit of image size not Pixel²? If you calculate the area of a rectangle, you just multiply the height and the width and get back the unit squared.
Example:
5cm * 10cm = 50cm²

In contrast, if you calculate the size of an image, you also multiply the height and the width, but you get back the unit - Pixel - just as it was the unit of the height and width before multiplying.
Example:
What you actually calculate is the following:
3840 Pixel * 2160 Pixel = 8294400 Pixel

What I would expect is:
3840 Pixel * 2160 Pixel = 8294400 Pixel²

Why is that the unit at multiplying Pixels is not being squared?

Because "pixel" isn't a unit of measurement: it's an object. So, just like a wall that's 30 bricks wide by 10 bricks tall contains 300 bricks (not bricks-squared), an image that's 30 pixels wide by 10 pixels tall contains 300 pixels (not pixels-squared).


average time to access a word in memory Here is the question:

  Consider a computer system that has cache memory, main memory (RAM) and disk, and the operating system uses virtual memory. It takes 2 nsec to access a word from the cache, 10 nsec to access a word from the RAM, and 10 ms to access a word from the disk. If the cache hit rate is 95% and main memory hit rate (after a cache miss) is 99%, what is the average time to access a word?

Here is how I solved it.
   consider 100 references
   95 cache hits(due to 0.95 cache hit ratio)
   95*2nsec = 190 nsec

this would leave 5 references which were passed to memory
   5*0.99=4.95=5 successfully found in memory

this would count for

5*10nsec=50nsec

average access time=total time/total accesses
   =(50+190)/100 nsec
   =240/100 nsec
   =2.4 nsec

Is this correct?

Here is another solution

memory access time
   =cache hit ratio * cache access time + (1 - hit ratio) * miss penalty(or memory access time)
   =0.95*2+(1-0.95)10
   2.4 nsec

which one is the perfect solution to this problem?

In question memory hit ratio is also given but is not used in the formula I used in second solution.Was it unnecessarily given in the question?
If there is a problem where cache hit rate is 85% and memory hit rate is 5% and disk hit rate is 10%, then what would be the miss penalty in that case?

This is not the answer, but you may consider it as hints to find it
yourself.

Why do you write 4.95=5 without any explanation. Is that your idea of
perfect solution? Apparently your first solution never accesses the
disk. Your second solution is essentially the same as the first,
presented more abstractedly (hence a bit better in my opinion, but the reasonning may not be explicited enough for what seems to be your level of proficiency), but it
ignores the disk access as much as the first soution.

That may not always be true, but you should always worry at least a
little bit where you are ignoring part of the data of your problem.
You should convince yourself that the data you ignore is

either redundant with the data you use. This means that it is
actually a consequence of the data you are using, and can thus be
taken into acount implicitly through the data you are using;
or irrelevant to the problem. In this case you should preferably
have some argument as to why it is irrelevant. This argument may not
be required in your answer (though it may not hurt to give it), but
you probably at least sketch it for yourself to convince yourself
that you are right in ignoring the corresponding data.
Irrelevance can also include the fact that the corresponding data is negligible in the context of your problem. But that usually demands some argument to convince the reader that it is indeed the case.

Does the data you ignore correspond to such a case?


Use machine learning algorithms data structure to store information (memory) DISCLAIMER : I'm pretty new to machine learning field, so forgive me
  if my questions are somehow naive ... I already searched on Internet
  about this topic and find nothing interesting so I am asking here ....

I wonder if a ML algorithm can be consider as a way to store data ?
There is programs that "contains" thousands of decimal of PI (e.g. https://www.quora.com/What-is-the-smallest-C-program-generating-pi-without-using-the-math-library) : in some way it's a "compressed" version of the first thousands decimal of PI, right ?

In the same way ML (e.g. Deep Neural Net) seems to store information. Can we mesure how many bits is stored in a Deep Neural Net ? Can we use ML  algorithms data structure to compress information and retrieve it later (even if it's not 100% accurate) ? ...

Is there (not too technical ) papers that discuss these possibilities ?

Thanks :)

ML algorithms are definitely capable of storing information. Generally, any ML algorithm can be trained to remember a set of data. This is commonly referred to as overfitting and something that most ML researchers try very hard to avoid.

Also feature learning
 and compression are common themes in ML. In this case, the goals are actually to find efficient ways to represent the data. This allows to store information efficiently. Because you asked for some illustrative papers: image compression with autoencoders, image compression with PCA, ...

Methods like generative models are probably also interesting as their purpose is to discover the distribution of some data in order to generate new data. This technique can be used to generate new images that are not just random noise for example.

These are just some examples with some random papers that are top hits when searching for the terms I mentioned. Probably every machine learning algorithm can be said to store some sort of information, but for some models the stored information is more useful/meaningful than for other models.

Generating pi with machine learning has probably not been done (at least it has not been published). However, nothing keeps you from trying it out. You could try to overfit a model to learn digits of pi or you could just try what happens when you feed an LSTM with a very large sequence of pi-digits (you would have to find a reasonable objective, but might be interesting), or do some sequence to sequence learning with encoders and decoders to predict digits for pi. Probably, the methods would not perform well from a ML perspective, but some interesting things might happen.

PS: as you might have noticed, I have mentioned quite some neural networks. There are other methods out there as well: do not get too biased.


Application of cosine similarity to detect plagiarism Can anyone tell me how using cosine similarity to see the correlation between two documents actually shows you if someone is plagiarising the other? I understand how cosine similarity works but don't understand how using this shows how closely related they are when the cosine deals with vectors and angles. How can this relate to a document?

Usually this would be used in conjunction with a bag of words model. You need to convert each document to a vector where the length of the vector is the number of words in the vocabulary. The entries in the vector correspond to the number of occurrences of each vocabulary word in the document. You can apply cosine similarity to these document vectors.

You should consider using tf-idf weighting to make sure that a small set of very common words doesn't end up dominating the distance computation. https://en.wikipedia.org/wiki/Tf%E2%80%93idf


Convolutional Neural Network with constant kernels I'm starting to learn about CNNs, and I have this question that I haven't been able to answer. Sorry if it is too basic.

I know that in a CNN, the network learns to extract relevant features of images in order to classify them. My question is: if I just update the weights of the fully-connected layer and leave the kernels constant, will the network learn how to classify as well?

(The kernels might be a Gaussian blur or a sharpenning, or whatever comes to mind).

A fully connected layer is able to classify images better than random. If you make the kernels constant and there is still information in the result, the network is essentially only a FCN operating on a preprocessed image. Of course it will learn how to classify the image. But it will certainly be worse than a similar network where the convolutional weights are learned.


Integral solutions to circulation problem Suppose we have a circulation problem (with only one commodity), where all lower bounds, upper bounds, and costs are integers.  Are we guaranteed that if there is a solution, then there is an integral solution?  Is there an algorithm that can find one in polynomial time?
For standard network flow, we know that there is a max flow that is integral, and there are polynomial-time algorithms that can find such an integral flow.  I'm wondering if the same is true for circulation problems, which are a generalization of max-flow.

Circulation problems are not just a generalization of max-flow, there is a reduction backwards as well. Suppose we have some directed graph $G = (V, E)$ with edge costs, capacities, and lower bounds.
Any edge $u \to v$ in $G$ with we can replace with two nodes $s, t$ and two edges $s \to v$ and $u \to t$ where one of the edges has the original cost, capacities, and lower bounds and the other is free and unlimited. Call this graph $G'(e)$, where $e = u\to v$ is the edge that was replaced.
Then if a flow with a certain cost exists in $G'(\cdot)$, it must also exist as a circulation in $G$ with the same cost. Vice versa, if a circulation exists in $G$ and it uses edge $u \to v$, then that flow also exists in $G'(u\to v)$ with the same cost.
Therefore to solve the circulation problem we can pick an arbitrary edge $e$, calculate $G'(e)$ and use a traditional network flow algorithm to find the optimal flow. By the traditional arguments, this optimal flow is integral. We then pick another edge (avoiding edges that were part of a previous optimal flow) and repeat, keeping the best solution, until no more unknown edges are left.
Since in the worst case this adds a factor of $|E|$ to the complexity of the polynomial complexity, this is still polynomial. And of course the optimum from all integral flows found is itself integral.
To handle the lower bounds on the edges of $G'$, one can either note that the linear programming constraint matrix is unimodular (see these MIT lecture notes), from which it follows that there exists an integral solution if there is any solution; or one can use a standard reduction to eliminate the lower bounds (see, e.g., Ahuja et al, Network Flows, page 39) and then solve with a standard algorithm for network flow.


What is the optimal way to find unique combinations of N sets of integers This is a simplification of a real world problem and only a small piece at that.

Example sets are

----------------------       ------------------------------------
| Set1 | Set2 | Set3 |  OR   | Set1 | Set2 | Set3 | Set4 | Set5 |
|--------------------|       |--------------------|--------------
| 1    | 10   | 40   |       | 1    | 1    | 1    | 1    | 1    |
| 2    | 12   | 45   |       | 2    | 2    | 2    | 2    | 2    |
| 3    | 13   | 51   |       | 3    | 3    | 3    | 3    | 3    |
| 4    | 20   | 61   |       | 4    | 4    | 4    | 4    | 4    |
| 5    | 25   | 76   |       | 5    | 5    | 5    | 5    | 5    |
|      | 31   | 78   |       ------------------------------------
|      |      | 81   |
----------------------

Real world constraints are

Up to 12 sets
N numbers in each set
Only care about distinct combinations - (112), (211) and (121) are considered the same.

Example with desired result

----------------------
| Set1 | Set2 | Set3 |
|---------------------
| 1    | 1    | 1    |
| 2    | 2    | 2    |
| 3    | 3    | 3    |
----------------------
Results: [1,1,1],[1,1,2],[1,1,3],[1,2,2],[1,2,3],[1,3,3],[2,2,2],[2,2,3],[2,3,3],[3,3,3]

Generally real world examples tend to either be like the first example where there are a variable number in each set and they are different in each set, or like the second where there are the same items in each set. However there are no hard and fast rules.

A real world example of the latter is 10 sets with 40 values in each. To naively iterate that example would be $1x10^{16}$ iterations.

Are there any optimal algorithms I can implement to find distinct combinations? I am hoping that there is something clever that can be done when there are the same items in different sets, somehow excluding them once certain conditions are met, but i have failed to think of or find one.

This may be wrong
I don't follow the multiple set of the set input part of question

Have a loop for each N

Assume N = 3
L is length of array A

for(i = 0; i < L-2; i++)
    for(j = i + 1; j < L-1; j++)
        for(k = j + 1; k < L; k++)
            A[i], A[j], A[k]

I write poker software and this matches the number of combinations


Time efficient way to implement Multi-Armed-Bandits? I'm doing a research on Multi-Armed Bandit (MAB) problem with approx. 1 million arms. In contrast, the number of iterations is of course much larger, about 10-20 million.

Most MAB-algorithms require an argmax operator (argmax of the action space) that has to be executed in each iteration in order to select the current arm (which maximizes a given selection criterion). Regardless of the chosen programming language for implementation, this procedure/ this argmax operator over the entire action space (1 million arms) is very time-consuming.

Does anyone have some ideas on how to implement MAB algorithms in a time-efficient way?

Store the values in a priority queue.  Typically, in each iteration you will update the value for only a single arm, so you need to change the key of a single value in the priority queue, which can be done in $O(\log n)$ time, where $n$ is the number of arms.  You can also find the argmax in $O(\log n)$ time.


Find cell neighbors of a given edge in a 2D grid In the figure below, cells are labeled row wise, and edges are labeled counter clockwise.  That is, vertices 1' and 2' form edge #1, vertices 2' and 5' form edge #2, vertices 5' and 8' form edge #7, etc.

vertices 1' and 2' form edge #1
vertices 2' and 5' form edge #2
vertices 4' and 5' form edge #3
vertices 1' and 4' form edge #4
vertices 2' and 3' form edge #5
vertices 3' and 6' form edge #6
vertices 6' and 5' form edge #7
vertices 5' and 8' form edge #8
vertices 7' and 8' form edge #9
vertices 4' and 7' form edge #10
vertices 6' and 9' form edge #11
vertices 8' and 9' form edge #12

  Question: given an edge number (and/or the vertices that form it), is there a way to algorithmically
  compute its corresponding cell neighbors?

There's no need for any special algorithm.  There are only 12 edges, so it's enough to simply use a switch statement with 12 cases.  Or, you can use 12 if statements.  Any of these will have $O(1)$ running time, since there are only finitely many cases, so they are (asymptotically) as good as any other "algorithm".


Which kind of interrupt has the highest priority on 8086 processors? Which of the following interrupts has the highest priority in 8086 micro-processor:

Overflow,
NMI or
Type 255?

The book I read suggests that type 255 has highest priority.
But most of the searches on google showed that it is NMI. Which is true?

The Intel manual for 8086 on page 2-23's diagram and also in the text says that internally generated interrupts are processed before hardware. It says in particular an overflow is processed as part of the instruction that generated the over flow, and hardware interrupts aren't checked until instructions are complete.  So overflow is the answer.


In perfect hashing, why does a secondary hash table that is quadratic in size leads to no collisions? See below a screenshot from CLRS 3rd Edition (Section 11.5, "Perfect Hashing"). The last sentence of the last paragraph says that the choice of $m_j = n^2_j$ leads to collision-free constant-time lookup.

Why? Is it because:

It assumes that one could, in theory, try or sample several hashing functions $\mathcal{h} \in \mathcal{H}$, checking for each for collisions, until we find one $h'$ that doesn't have them?
the probability of sampling $h$ without collisions is 1/2, so it shouldn't be that difficult to find $h'$?

If not, why?

If $n_j$ keys hash to slot $j$ of the first-level hashtable, and if $n_j > 1$, we will need to use a second-level hashtable for that slot. Theorem 11.9 helps us in the sense that, if we keep this second hashtable size as $n_j^2$, then atleast 1/2 of the hash-functions in any universal-class (which all hash to range 0 to $n_j^2-1$) must give no collisions for the $n_j$ keys.
We can NOT conclude that if we pick any random function from this class, we will have a collision-free case. We will need to do some trials, and can hope to succeed for this set of $n_j$ keys very soon, due to the 1/2 probability provided by Theorem 11.9.
Please also refer below answer for details:
https://cs.stackexchange.com/a/134386/123596.


Construct non-recursive predictive parser for grammar $S \to Aa \mid b A c \mid Bc \mid bBa, A \to d, B \to d$ In the grammar for S production two bodies have same starting symbol

$ S \to Aa \mid b A c \mid Bc \mid bBa $

So i removed the left factoring from those two productions

$ S \to bC$

$ C \to Ac  Bc$

Then I calculated first and follow for all of them. Then i constructed parse table, but for the entry on state S when input symbol is d there are two possible productions

$ A \to d$

$ B \to d$

I don't have much knowledge about what to do when there is a conflict in the entry for this table, if I'm completely wrong please help me to find solution

You're looking at an implicit conflict in your grammar. Given
\begin{align*}
S &\to Aa \mid b A c \mid Bc \mid bBa \\
A &\to d \\
B &\to d,
\end{align*}
we know that a pair of rules $S \to \alpha$ and $S \to \beta$ "conflicts" if ${\rm first}(\alpha) \cap {\rm first}(\beta) \ne \varnothing$, that is, if the set of characters that can be immediately "consumed" by the productions $\alpha$ and $\beta$ intersects.

Intuitively, you can try to visualize what a 1-lookahead recursive-descent parser would do in the state $S$ when it sees a character that can shift to multiple productions. Say you're parsing $S$, and you encounter a symbol $b$; if you're given no other knowledge about the string you are parsing, then it's entirely uncertain whether you should take the $S \to bAc$ path or the $S \to bBa$ path. Therefore, for a grammar to be "well-formed" for a 1-lookahead recursive descent parser, we have to make sure that the grammar contains no such conflicts.

This also generalizes nicely for the case of n-lookahead. We say that two rules $S \to \alpha$ and $S \to \beta$ conflicts in the first $n$ words if ${\rm first}_n (\alpha) \cap {\rm first}_n(\beta) \ne \varnothing$. Intuitively, an n-lookahead parser will be confused if for a particular string of $n$-words, it can shift into multiple productions as well.

Now, besides the obvious conflict between $bAc$ and $bBa$, you should realize that ${\rm first}(Aa) = \{d\} = {\rm first}(Bc)$, so the rules $Aa$ and $Bc$ also conflicts. We can easily resolve this by "inlining" the nonterminals $A$ and $B$ directly and do the same left-factoring trick you did before:
\begin{align}
S &\to da \mid bdc \mid dc \mid bda \\
&\Rightarrow ({\rm left ~ factoring}) \\
S &\to d X \mid bd X \\
X &\to a \mid c
\end{align}

Computing the 1-lookahead predictive table results in
$$
\begin{array}{ccccc}
& a & b & c & d \\
S & & \to bdX && \to dX\\
X & \to a & & \to c
\end{array}
$$

which corresponds to the algorithm

function parseS(words):
  if next word is b:
    // -> bdX
    consume b; consume d; parseX(rest)
  else if next word is d:
    // -> dX
    consume d; parseX(rest)
  else: error

function parseX(words):
  if next word is a: consume a
  else if next word is c: consume c
  else: error


How to prove membership of NP My tutor often says that proving membership of NP is the easy part of proving that a problem is NP-complete, and that this should only take a minute. What I don't understand is what exactly you're suppose to do at this step   I understand that you're suppose to verify the correctness of a solution but how do I do that?

Here are several examples:

MAX-CLIQUE: The witness is a set of vertices of given size. The verifier checks that edges connect all pairs of vertices in the set.
SAT: The witness is a satisfying assignment. The verifier checks that it satisfies all clauses in the formula.
3COL: The witness is a 3-coloring of the graph. The verifier checks that all edges connect vertices of different color.
SUBSET-SUM: The witness is a subset of the set. The verifier checks that the subset sums to the target number.


Expressing unsigned comparison through signed comparison of 2's complement Let n > 0 be a natural number and for any two reminders a, b modulo 2^n we have that a < b iff a xor 0x800..00 <(signed) b xor 0x800...00.

It is also true that a <(signed) b iff (0x800...00 & b <= 0x800...00 & a) && (a & 0x7FF...FFF < b & 0x7FF...FFF).

Is there a way to prove the equivalence of these two propositions?

It's even a bit simpler, namely both:

a <u b == (a ^ m) <s (b ^ m), and,
a <s b == (a ^ m) <u (b ^ m)

Where m is the mask with the sign bit set.

I don't have a formal proof for that, but the image below shows what is happening. The top row shows the "unsigned order" of the number line, chopped in half, with the first part having a 0 in the top bit and the second half having a 1 in the top bit. The bottom row shows the same sub-ranges but in the "signed order". The bottom block in the signed case is the same block as the top block in the unsigned case. Notice that the signed and unsigned order of the two sub-ranges is swapped, but the order within the sub-ranges is the same.

XORing by m is equivalent to adding m and to subtracting m, so you may think of it as:

swapping the order of the two sub-ranges (xor)
pushing the two sub-ranges to the right (by the width of a block), with wrap-around to the left side (addition)
pushing the two sub-ranges to the left, with wrap-around to the right side (subtraction)

In any case the order of the blocks is swapped, so it swaps between the signed order and the unsigned order.


Is there a canonical form that uses AND and XOR? Is there something like the sum of products form of a circuit which uses AND and XOR instead of AND and OR?

I know that you can create an OR gate from AND and XOR (but i can't remember or find the details of that at the moment), but am wondering if there is anything more straightforward, as in an actual form that uses AND and XOR?

You're looking for Reed-Müller forms. The introduction to this paper summarizes some families of these forms:

An arbitrary n-variable  function $f(x_1,x_2,...,x_n)$ can be represented using the positive polarity Reed-Muller form (PPRM)
$f(x_1,x_2,...,x_n) = a_0\oplus a_1x_1\oplus a_2x_2\oplus\ldots\oplus a_{12}x_1x_2\oplus a_{13}x_1x_3\oplus\ldots\oplus a_{n-1,n}x_{n-1}x_n\oplus\ldots\oplus a_{12\ldots n}x_1x_2\ldots x_n$.
For each function $f$, the coefficients $a_i$ are determined uniquely, so PPRM is a canonical form. If we used either only the positive literal ($x_i$) or only the negative literal ($\overline{x_i}$) for each variable in Eq. (4)1, we get the FPRM. There are $2^n$ possible combinations of polarities and as many FPRMs for any given logical function.
If we freely choose the polarity of each literal in Eq. (4), we get a GRM. In GRMs, contrary to FPRMs, the same variable can appear in both positive and negative polarities. There are $n2^{n-1}$ literals in Eq. (4), so there are $2^{n2^{n-1}}$ polarities for an $n$-variable function and as many GRMs. Each of the polarities determines a unique set of coefficients, and thus each GRM is a canonical representation of a function.

1 It's not clear from the text, but equation 4 is the generic PPRM equation included in the quote


complexity of finding the hampath of length $k$ in a graph with $n$ vertexes where $k < n$ A simple question:

What would be the complexity of finding whether a hampath of length $k$ exists in a graph with $n$ vertexes where $k < n$?

Would this be in NP-complete or just NP?

Purely for clarity I'll lay out the definitions first, then give a reduction for your problem, so skipping a little ahead shouldn't cause a problem (if it does, start a bit earlier ;) ).
The two problems:

Hamiltonian Path (HP)
Input: A graph $G$.
Question: Does $G$ contain a path with $|V(G)|$ vertices?
Not Quite Longest Path (NQLP)
Input: A graph $G$ and an integer $k < |V(G)|$.
Question: Does $G$ contain a path on $k$ vertices?

Now, what we want to prove:

Lemma 1: NQLP is $\mathcal{NP}$-complete.

Of course this has two parts, membership and hardness.

Proposition 2: NQLP $\in \mathcal{NP}$

Proof: Given an order set of vertices we can easily check that it is of length $k$ and forms a path in $G$. $\Box$

Proposition 3: HP $\leq_{m}$ NQLP

Proof: Let $G$ be an instance of HP and for convenience let $n = |V(G)|$. We construct an instance $(G', k)$ of NQLP by taking $G'$ as $G$ with an additional, disconnected vertex $v$, i.e. $V(G') = V(G)\cup \{v\}$ and $E(G') = E(G)$. Thus $|V(G')| = n' = n+1$. We choose $k = n < n'$. This construction is clearly computable in polynomial time.
Claim: If $G$ has a Hamiltonian path, $G'$ has a path of length $k$.
By definition, the Hamilton path includes all vertices of $G$, as $G'$ has $G$ as an (induced) subgraph, this path exists in $G'$. Moreover it is of length $n = k$.
Claim: If $G'$ has a path of length $k$, $G$ is has a Hamiltonian path.
If $G'$ contains a path of length $k$, it cannot include the added vertex $v$, as it has no incident edges (except the trivial case where $G$ was one vertex, but then we have a symmetry which does our work for us). Therefore it must include every other vertex in $G'$ (as $k = n' -1 = n$), as $G' - v$ is simply $G$, $G$ must be Hamiltonian. $\Box$
Proof of Lemma 1: As HP is $\mathcal{NP}$-complete, Prop. 3 proves that NQLP is $\mathcal{NP}$-hard. Then combining Propositions 2 & 3, we have proved Lemma 1. $\Box$