A good introductory book on cryptography Can anyone suggest me some good books on cryptography? I have just starting studying cryptography but I know elementary number theory, abstract algebra and algorithms. Also please mention the difficulty level of the book.

"Introduction to Modern Cryptography", Jonathan Katz and Yehuda Lindell. This is a great book for learning about provable security.

And for actual crypto protocols and algorithms, there's always the classic: "Handbook of Applied Crypto" by  Paul van Oorschot, A. J. Menezes, and Scott Vanstone. This is more a reference book than a textbook. And its available free of cost on one of the authors web-pages.


AI Search - State in the toy vacuum problem I have been reading about AI search, specifically the toy vacuum cleaner problem and I would like to code an example of this but I am finding the description of the state hard to get my head around.
The problem states that the AI needs to be able to move between squares, either left or right and if there is dirt in the square it can clean it (suck).

Is the state something you are supposed to hard code in advance in AI search? This seems unlikely due to the possible number of potential states for a larger problem, so I am not sure how I can represent the state in a problem like this, or any other really.
In the vacuum problem the states are 'dirt left', 'dirt right' and 'vacuum position' and an action such as 'move left', 'move right' or 'suck' will leave the problem in a new state but how do you represent these changes?
Would state be an object with boolean properties for the dirt and an int value for the vacuum position of either 0 or 1 depending on which array element it is looking at?
In the context of a map program trying to get to somewhere I do understand the state might be In(New York) but I what I am struggling with is how I would represent something like that in code, or perhaps a maze where the current state might be the x, y coordinate of the square the agent is currently in, again would an object be the right thing to use to model state?

"State" is the sum of all information that describes the current situation of the robot, and everything about that past that might be relevant.  I don't understand your diagram so I can't tell you what it is specifically in your particular example, but it appears that the state includes the current location of the vacuum and which locations currently have dirt.  So, you might have one variable that defines where the robot is located, one variable that indicates whether there is dirt in the left room, and one variable that indicates whether there is dirt in the right room.
In AI search, we often assume that we know the set of all possible states and all ways to transition between them.  We give that information as input to the search algorithm, and it finds a way to reach a desired state from where we currently are.


Find a subsequence with fastest time for specific distance I have two arrays.

seconds = [0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, ..., 2680]

totalMeters =  [0, 3.2, 7.1, 10.6, 14.1, 17.9, 21.5, 24.2, 27.8, 32.5, 36.9, ..., 5000]

The totalMeters array is the total meters that I have run at this specific point of time. The sampling is 2 seconds.

I would like to find where in the array is the fastest 100 meters I have run, as well as its time.

You cannot generally get time for exactly $100$ meters with this data. The better approach would be to search for the longest run within some multiple of $2$ seconds.

Find the longest distance run in $2\cdot k$ seconds:

Set desired k.
Set i = 0 and j = k-1.
Set currentSum = maxSum = totalMeters[j].
While j < totalMeters.length - 1 do

i++; j++;
currentSum = totalMeters[j] - totalMeters[i]
if currentSum > maxSum then maxSum = currentSum

This should also give you an idea how to build other similar algorithms for this problem, if you don't change your approach.


What is the Best and easiest way to create a Classifer for Sentiment Analysis Sentiment analysis using Machine Learning is a hot topic. In the present situation when a person doesn't have a problem in having the training data set then which way should we create the classifier possibly the NaiveBayes classifier?

This isn't the best way but it's simple and fast:

preprocess the input with the Porter Stemmming algorithm (it's a process for removing the commoner morphological and inflexional endings from words in English) or similar (take a look at Snowball)
preprocess the input flagging words before and after every negation ("never", "not", "no", "n't"):

the movie was not great => the movie ¬was not ¬great

Use Bernoulli Naïve Bayes (duplicate words are removed from the document and given a class, positive or negative, you assume that the words are conditionally independent of each other):
  $$P(C_j | D) = \frac{\prod_i P(x_i | C_j) P(C_j)}{P(D)}$$

$$P(x_i | C_j) = \frac{count\ of\ x_i\ in\ documents\ of\ class\ C_j}{total\ number\ of\ words\ in\ documents\ of\ class\ C_j}$$
($x_i$ are the individual words of the document $D$)

You can also use Laplacian smoothing to avoid problems if  the  classifier encounters a word that hasn't been seen in the training set:

$$P(x_i | C_j) = \frac{1 + count\ of\ x_i\ in\ documents\ of\ class\ C_j}{2 (total\ number\ of\ words\ in\ documents\ of\ class\ C_j)}$$

This works quite well.

Further steps are feature selection (removing redundant features, while retaining those features that have high disambiguation capabilities) and the use of ngrams (e.g. Fast and accurate sentiment classification using an enhanced Naive Bayes model by Vivek Narayanan, Ishan Arora, Arjun Bhatia).


Minimum pumping length of finite language Background
Let L = {aa}. We know that the minimum pumping length of L is |aa| + 1 = 3. For this length all the three conditions of the pumping lemma vacuously hold true.
Doubt
Let L = {aa, aab}. Is it right to say the minimum pumping length is max(|w| | w belongs to L) + 1(in this case |aab| + 1 = 4) for finite languages?

Let $w \in L$ be the longest string of the finite language $L$. Assume a pumping length $p \leq |w|$. This would imply $w = xyz$ with $|y| \geq 1$ and $xy^2z \in L$. Can you see the contradiction?
Having ruled out pumping length $p \leq |w|$, the minimal possible value for $p$ is indeed $|w|+1$, for which as you noted the conditions of the pumping lemma are trivially true.


How to calculate the number of states in designing a Turing machine? I would like to ask how to determine the number of states when designing a Turing machine from the description for a language? For example:

$\qquad \displaystyle L = \{wcw \mid w \in \{0,1\}^*\}.$

I mean how to know how many states are there in the set $Q$, with the information from the description of that language.

I think that given a decidable language $L$, you can always build a 2-states TM that recognizes it.

Indeed there exists a 2 state Universal Turing Machine $UTM_{2U}$ (with alphabet $|\Sigma| \geq 18$).

If $TM_i$ decides $L$ then $UTM_{2U}(i,x)$ decides $L$; so you can build a 2-states $TM_{2L}$ hard encoding $i$ in $UTM_{2U}$ but keeping only two states; the idea is:

add $2*|i|*|\Sigma|^{|i|}*|\Sigma|$ symbols to the alphabet that will represent the possible combinations of (state, head position, tape content, first symbol $\alpha$ of $x = \alpha x'$ on the tape)  of $UTM_{2U}$ on input $(i,\alpha x')$
adjust the transition table of $TM_{2L}$ in order to simulate the behaviour of $UTM_{2U}$ on the first $|i|+1$ characters of the tape using only the first cell of the tape (that initially will contain $\alpha$).

EDIT (alternate take :)

Given a generic $TM_L$ that recognizes $L$ there is an easier way to build an equivalent 2-states $TM_{2L}$.
I'll try to sketch its construction (anybody wants to check if it is correct? :)

Idea: simulate $TM_L$ using the tape to store at the same time the alphabet symbol of the original tape, plus the current state and head position of $TM_L$.
A single cell of the tape is a 5-tuple:

[(direction)(symbol)(current_state)(state_to_copy)]

that represents:

direction: 0 = we are scanning the tape from left to right
           1 = we are scanning the tape from right to left
symbol:    symbol from the alphabet of TM_L
current_state: if > 0 then the head position of TM_L is here and
               the state is current_state
state_to-copy: if > 0 then we are copying the next state to
               the left or right according to direction

Using the direction flag we can move from left to right and "execute" the
$TM_L$ transitions that moves the head to the right (i.e. we can copy the next head/state
to the right), then we can go back and "execute" the $TM_L$ transitions that moves
the head to the left (i.e. we can copy the next head/state to the left).
The transition table with two states is built in the following way:

STATE0

...from LEFT to RIGHT

// scan left to right until we found the cell with the head
Read(0, X, 0, 0)  -> Write(1, X, 0, 0)    stay in STATE0 and move R

// if we have a rule (A, Qi) -> (B, Qj, Right) in TM_L then add the
// following transition  which will start the copy of Qj on the right cell
Read(0, A, Qi, 0) -> Write(0, B, 0, Qj-1) enter STATE1 and move R

// if we have a rule (A, Qi) -> (B, Qj, Left) in TM_L then
// add the following transition (we will process it later):
Read(0, A, Qi, 0) -> Write(1, A, Qi, 0)   stay in STATE0 and move R

// if we are copying a state to the right continue:
Read(0, X, 0, Qj) -> Write(0, X, 0, Qj-1) enter STATE1 and move R

// when we reach a blank symbol, start moving from right to left
Read(0, blank, 0, 0) -> Write(0, blank, 0, 0) stay in STATE0 and move L

... from RIGHT to LEFT

// scan right to left until we found the cell with the head
Read(1, X, 0,  0) -> Write(0, X, 0, 0)    stay in STATE0 and move L

// if we have a rule (A, Qi) -> (B, Qj, Left) in TM_L then add the
// following transition which will start the copy of Qj on the left cell
Read(1, A, Qi, 0) -> Write(1, B, 0, Qj-1) enter STATE1 and move L

// if we have a rule (A, Qi) -> (B, Qj, Right) in TM_L then
// add the following transition (we will process it later):
Read(1, A, Qi, ) -> Write(0, A, Qi, 0)    stay in STATE0 and move R

// if we are copying a state to the left continue:
Read(1, X, 0, Qj) -> Write(1, X, 0, Qj-1) enter STATE1 and move L

// when we reach a blank symbol, start moving from left to right
Read(0, blank, 0, 0) -> Write(0, blank, 0, 0) stay in STATE0 and move R

STATE1

// we are copying the head/state to the right
Read(0, Y, Qk, 0) -> Write(0, Y, Qk+1, 0) enter STATE0 and move L

// we are copying the head/state to the left
Read(1, Y, Qk, 0) -> Write(1, Y, Qk+1, 0) enter STATE0 and move R

The 5-tuple (direction)(symbol)(current_state)(state_to_copy) must be encoded using a single symbol of $TM_{2L}$, so its alphabet size is:

$|\Sigma_{2L}| = 2 \times |\Sigma_L| \times |Q_L| \times |Q_L|$

P.S. with the same technique (if it is correct) a generic UTM can be converted to a 2-states UTM ... unfortunately we are not in 1956 :-)))


How does automated verification of systems with infinitely many states work? I need some help with basic definitions and intuition to understand why and how it's possible to verify systems with infinitely many states.

For example, if I consider an x86 computer, and assuming the CPU architecture is a large and finite state machine, it will have infinitely ($\aleph_0$) many possible states (sequences) it can run, so how can systems with infinitely many states be theoretically verified at all?

Infinite-state system verification is indeed a rather broad topic. First of all, all computers used nowadays can only have a finite number of states, as the amount of RAM is fixed. But that's is mainly a matter of terminology -- any verification technique that needs to iterate over all possible states is doomed from the beginning due to computation time.

Also note that you used "verification" in your title, and "to validate" in your question. These are different concepts that should not be confused. I will assume that you meant "verification".

To solve a verification problem with a large number of states, one typically constructs a proof of correctness of some sort. Such proofs do not need to refer to all possible states, rather they group sets of states by constraints that they satisfy. The description of the constraints can indeed by small, so that in the end we get a small proof.

For example consider the following function:

int comp(int parameter) {
    int p=parameter;
    if (p<0) {
        return p*p;
    } else {
        return p;
    }
}

We want to verify that the function comp never returns a negative number. If "int" is an arbitrary-length integer datatype, this program can already have an infinite number of states. To verify this program, we can perform a case split on whether "parameter" is negative or not, and then apply basic mathematical rules that we assume the integer data type to follow. What we get is a small correctness proof for an infinite-state system.

When researchers say that they work on infinite-state verification, they typically mean that they work of verifying systems in some type of modelling framework that allows to express systems with an infinite number of states - this does not mean that they can verify arbitrary such systems and their techniques are typically sound, but not complete.


Proof of the inclusion-exclusion principle The inclusion-exclusion principle for $n$ sets is proved by Kenneth Rosen in his textbook on discrete mathematics as follows:

  THEOREM 1 — THE PRINCIPLE OF INCLUSION-EXCLUSION   Let $A_1,A_2,\ldots,A_n$ be finite sets. Then
  $$
\begin{multline*}
|A_1 \cup A_2 \cup \cdots \cup A_n| = \sum_{1 \leq i \leq n} |A_i| - \sum_{1 \leq i < j \leq n} |A_i \cap A_j| \\ + \sum_{1 \leq i < j < k \leq n} |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n+1} |A_1 \cap A_2 \cap \cdots \cap A_n|.
\end{multline*}
$$
  Proof: We will prove the formula by showing that an element in the union is counted exactly once by the right-hand side of the equation. Suppose that $a$ is a member of exactly $r$ of the sets $A_1,A_2,\ldots,A_n$, where $1 \leq r \leq n$. This element is counted $\binom{r}{1}$ times by $\sum |A_i|$. It is counted $\binom{r}{2}$ times by $\sum |A_i \cap A_j|$. In general, it is counted $\binom{r}{m}$ times by the summation involving $m$ of the sets $A_i$. Thus, this element is counted exactly
  $$
\binom{r}{1} - \binom{r}{2} + \binom{r}{3} - \cdots + (-1)^{r+1} \binom{r}{r}
$$
  times by the expression on the right-hand side of this equation. Our goal is to evaluate this quantity. The binomial formula shows that
  $$
0 = (1-1)^r = \binom{r}{0} - \binom{r}{1} + \binom{r}{2} - \cdots + (-1)^r \binom{r}{r}.
$$
  Hence
  $$
1 = \binom{r}{0} = \binom{r}{1} - \binom{r}{2} + \binom{r}{3} - \cdots + (-1)^{r+1} \binom{r}{r}.
$$
  Therefore, each element in the union is counted exactly once by the expression on the right-hand side of the equation. This proves the principle of inclusion-exclusion.

Although the proof seems very exciting, I am confused because what the author has proved is $1=1$ from the LHS and RHS.

Thus, is this still a valid proof? We need to prove that the total cardinality of LHS is the RHS. The RHS produces a $1$ for each member of the union of the sets.

I think in order to produce the cardinality of the union, an extra
summation sign should be appended before the expression in RHS. Could
someone please clarify?

Let me slightly rephrase the argument. Let $N_r$ be the number of elements contained in exactly $r$ of the sets $A_1,\ldots,A_n$. Then the left-hand side is
$$
|A_1 \cup \cdots \cup A_n| = \sum_{r=1}^n N_r.
$$
The first sum on the right-hand side is
$$
\sum_{1 \leq i \leq n} |A_i| = \sum_{r=1}^n \binom{r}{1} N_r.
$$
The second sum on the right-hand side is
$$
\sum_{1 \leq i < j \leq n} |A_i \cap A_j| = \sum_{r=2}^n \binom{r}{2} N_r.
$$
More generally,  the $m$th sum on the right-hand side is
$$
\sum_{1 \leq i_1 < i_2 < \cdots < i_m \leq n} |A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_m}| = \sum_{r=m}^n \binom{r}{m} N_r.
$$
Therefore the right-hand side is equal to
$$
\sum_{r=1}^n \binom{r}{1} N_r - \sum_{r=2}^n \binom{r}{2} N_r + \sum_{r=3}^n \binom{r}{3} N_r - \cdots + (-1)^{n+1} \sum_{r=n}^n \binom{r}{n} N_r.
$$
Rearranging, the right-hand side is equal to
$$
\left[ \binom{1}{1} \right] N_1 + \left[ \binom{2}{1} - \binom{2}{2} \right] N_2 + \left[ \binom{3}{1} - \binom{3}{2} + \binom{3}{3} \right] N_3 + \cdots + \\
\left[ \binom{n}{1} - \binom{n}{2} + \binom{n}{3} - \cdots + (-1)^{n+1} \binom{n}{n} \right] N_n.
$$
The coefficient of the general term $N_m$ is
$$
\binom{m}{1} - \binom{m}{2} + \binom{m}{3} - \cdots + (-1)^{m+1} \binom{m}{m}.
$$
By the binomial theorem, this equals $1$, and so the right-hand side equals
$$
1 \cdot N_1 + 1 \cdot N_2 + 1 \cdot N_3 + \cdots + 1 \cdot N_n = \sum_{r=1}^n N_r,
$$
which is exactly the same as the left-hand side.


Reconstructing a data table from cross-tabulation frequencies Say there is a data table $D$ that we cannot see, with $M$ columns. We are given exact cross-tabulation frequencies for all ${M \choose 2}$ pairs of columns, that is how often each combination of two values occurs.

From the cross-tabulations, we can derive a set of possible rows $R$ of $D$ and maximum frequencies for each possible row.

How can we reconstruct the original table $D$? If there is not enough information to do so, how can we construct a possible table $D'$ that has the same cross-tab frequencies? In this case, is it possible to count the number of possible tables?

(Edit: As Vor noted, define a table as an unordered collection of rows. A permutation of the rows of a table yields the same table.)

For example, if $D$ has rows:

X  A  j
Y  A  k
X  B  j
X  B  j

We have three sets of cross-tab frequencies:

X  A  1
X  B  2
Y  A  1
Y  B  0

X  j  3
X  k  0
Y  j  0
Y  k  1

A  j  1
A  k  1
B  j  2
B  k  2

I would like an algorithm which will take the cross-tab frequencies as input and output the original table or a possible original table.

We have $M$ columns $C_1, \dots, C_M$ in the original table, each with a finite set of distinct values $V_1, \dots, V_M$.

Given the cross-table frequencies $c_{i,j}(a,b)$ (frequency of $a$ in $V_i$ and $b$ in $V_j$ occurring together), proceed as follows:

Determine $V_1, \dots, V_M$ and denote $V_i = \{v^{(i)}_j \mid j \in [1,n_i] \}$ where $n_i = |V_i|$.
Solve the following integer program:

$\qquad\displaystyle \min \sum_{i_1 = 1}^{n_1} \cdots \sum_{i_M = 1}^{n_M} x_{(i_1,\dots,i_M)} \\
     \qquad \begin{align}
       \text{s.t. } \sum_{i_1 = 1}^{n_1} \cdots \sum_{i_{l-1} = 1}^{n_{l-1}} \sum_{i_{l+1} = 1}^{n_{l+1}} \cdots \sum_{i_{r-1} = 1}^{n_{r-1}} \sum_{i_{r+1}  1}^{n_{r+1}} \cdots \sum_{i_M = 1}^{n_M} x_{(i_1, \dots, i_M)} &= c_{(l,r)}(i_l,i_r) \\
       \qquad \text{for all }
       1 \leq l < r \leq M, i_l \in [1,n_l], i_r \in [1,n_r], \\
       x_{(i_1, \dots, i_M)} &\in \mathbb{N} \\
       \qquad \text{for all } i_1 \in [1,n_1], \dots, i_M \in [1,n_M]
     \end{align}$

The $x_{(i_1, \dots, i_M)}$ now indicate which row should occur how often, and we get a solution with the minimum number of rows possible. If we can influence the search, we can abort as soon as we find any feasible solution.

This is not likely to be efficient, but there are honed solvers for integer programs around so it's simple to implement. It may be possible to use an LP-solver and round to a feasible solution.


Why do particles in particle swarm optimization converge to the global best when their personal best has just as much weight? I know this is probably a really basic question but I just cant wrap my head around it right now.
So the basic PSO update formula is as follows:
$$\bar{v}_{n+1} = \omega \cdot \bar{v}_n + c_k \cdot r_1 \cdot (\bar{p}_{best}-\bar{p}_n)+ c_s\cdot r_2 \cdot (\bar{g}_{best}-\bar{p}_n) $$
velocity(n+1) = momentum_component + cognitive_component + social_component
Now both the cognitive part and the social part have the same weight to them on the updated velocity.
So when a particle is moving around the space and lets say the cognitive part pulls the particle in a certain direction while the social component pulls the particle in the opposite direction, shouldnt the particle be stuck forever? Or at least go back and forth never converging?
However if I run the basic vanilla PSO algorithm the particles always seem to converge to the gbest as if their pbest has barely any influence.

The random number biases distance along the vectors, so it changes per update helping in escaping local optimum, and the global best also changes during the algorithm, if you really want some of these answers try programming a visual particle system using PSO.


Error detection/correction algorithm We have 2 stations that communicate with each other, but we need to detect (or even correct) when something is wrong.

We use 8 binary words: each consisting of 3 bits  and to send it we code it as
  where  is the complement of  and  is the even parity check bit of  .

We need to find the capabilities of this code (up to how many can we detect and how many can we correct). BUT, a proof is required.

This is how far I've reached so far:

First we find the hamming distance:
If  changes then  changes, also  changes. So we have a hamming distance of 3.

This means that we can detect two bit errors or correct a single error.

Can you help me write the proof for that?

(also the tags may need some refinement - comments about the downvote are welcome)

Consider any two codewords based on $b_2b_1b_0$ and $c_2c_1c_0$. The Hamming distance between the two codewords is at least twice the Hamming distance between $b_2b_1b_0$ and $c_2c_1c_0$ (why?). Furthermore, if the Hamming distance between $b_2b_1b_0$ and $c_2c_1c_0$ is exactly $1$, then your argument shows that the Hamming distance between the codewords is $3$. We can conclude that the Hamming distance is always at least $3$.


Solving a recurrence relation involving square roots Give an asymptotic upper bound for $$T(n) = \sqrt{n}·T(\sqrt{n})+n+n/\log n. $$

How can I solve this recurrence relation, which involves square roots?

Dividing both sides by $n$ then introducing $S(m):=\frac{T(2^n)}{2^n}$ yields:

$$S(m)=S(m/2)+1+\frac{1}{m}$$

It follows that:
$$1<S(m)-S(m/2)\leq 2$$
And further:
$$\forall k, 1<S(m/2^k)-S(m/2^{k+1})\leq 2$$
Now summing for $k=1\dots \log(m)-1$ gives us:
$$S(m)=\Theta(\log(m))$$
And so:
$$T(n)=\Theta(n\cdot\log\log n)$$


Calculating LL(1) grammar I am trying to calculate the First and Follow of the following grammar

S->ABC
A->Aa
A->aB
B->Bb
B-> epsilon
C-> Cc
C-> Epsilon

I have calculated the firsts and it is all good

Follow(A) = {a,b,c,$}

What is confusing me is the follow of B, I get Follow(B) = Follow(A)
But on the other hand, I have a solution for the grammar that states that the follow(B) = {b,c,$}

So which one is the right one?

It is evident that $B$ can be followed by $a$  — in other words, that $a\in \text{FOLLOW}(B)$ — as shown by the partial derivation

$$\begin{align}S&\to A B C&(S\to ABC)\\
&\to  AaBC &(A\to Aa)\\&\to aBaBC&(A\to aB) \\
\end{align}$$

So the answer provided does not correspond to this grammar.


Algorithms that must compute a global property? Could you give me examples of polynomial-time algorithms that must compute a global property over their entire input? A purely illustrative example of this might be a graph algorithm that somehow must count the total number of nodes before computing its final answer.

A silly example: Checking if a graph has more than m nodes. :-)
Some more interesting examples:

Checking if a graph is connected.
Checking if a graph has an Eulerian cycle. A graph is Eulerian iff all degrees are even and the graph is connected: https://en.wikipedia.org/wiki/Eulerian_path
Checking if a graph has a perfect matching: https://en.wikipedia.org/wiki/Blossom_algorithm


What is a "wasteful" execution? And a "schedule"? I'm trying to understand what this text means in my textbook about distributed leader election algorithms, but I can't make any sense of it. Either they didn't explain what was meant, or I missed it somewhere.

In this section, we show that the leader election algorithm of Section 3.3.2 is asymptotically optimal. That is, we show that any algorithm for electing a leader in and asynchronous ring sends at least $\Omega(n\log n)$ messages. The lower bound we prove is for uniform algorithms, namely, algorithms that do not know the size of the ring.
We prove the lower bound for a special variant of the leader election problem, where the elected leader must be the processor with the maximum identifier in the ring; in addition, all the processors must know the identifier of the elected leader. The proof of the lower bound for the more general definition of the leader election problem follows by reduction.
Assume we are given a uniform algorithm $A$ that solves the above variant of the leader election problem. We will show that there exists an admissible execution of $A$ in which $\Omega(n\log n)$ messages are sent. Intuitively, this is done by building a "wasteful" execution of the algorithm for rings of size $n/2$, in which many messages are sent. Then we "paste together" two different rings of size $n/2$ to form a ring of size $n$, in such a way that we can combine the wasteful executions of the smaller rings and force $\Theta(n)$ additional messages to be received.
Although the preceding discussion referred to pasting together exections, we will actually work with schedules. The reason is that executions include configurations, which pin down the number of processors in the ring. We will want to apply the same sequence of events to different rings, with different numbers of processors. Before presenting the details of the lower bound proof, we first define schedules that can be "pasted together".
A schedule $\sigma$ of $A$ for a particular ring is open if there exists an edge $e$ of the ring such that in $\sigma$ no message is delivered over the edge $e$ in either direction; $e$ is an open edge of $\sigma$.

There is lots more, but I don't know if I should type it all out if only for copyright reasons. I hope this is enough to help clarify my question and get an explanation.

I'm not completely sure of my answer since I don't have the book but I think that:

By "wasteful" execution they mean an execution that follow $A$ but with a lot of messages. There are trying to prove that for $n$ processes you may need $\Omega(n\log(n))$ messages. So they consider a ring with $n/2$ processes and the worst execution and they want to combine two of this rings and of those executions to prove that for $n$ processes you will need a least $n\log(n)$ messages.

By scheduler I think the mean a function $\sigma$ that a each state of your system associate a process and an action to be performed. A fixed system and a scheduler are equivalent to an execution (since you can see it as $s\xrightarrow{\sigma(s)}s_1\xrightarrow{\sigma(s_1)}s_2\xrightarrow{\sigma(s_2)}\dots$ But schedulers are often more easy to work with since they are functions so in the proof you don't need to manipulate indexes of where you are in the execution.

I hope it helps, please ask if I missed something.


How to determine convergence when using Q-learning? I'm using Q-Learning to find the values of states in on a gameboard. For example, something like:

-----------------
|   |   |   | 1 |
-----------------
|   | W |   | -1|
-----------------
|   | W |   |   |
-----------------
| S |   |   | 1 |
-----------------

I have the transition, and I can calculate the values of the states, but I can't tell when to stop computing. Normally I would just compute until a terminal state, for x-episodes; but this particular board has no terminal states. So I'm stuck to just calculating the values over say 1000 iterations (the more the more accurate obviously). I would like a way to stop though when I'm within an acceptable range.

How is this normally done for a non-terminal state space?

There are two ways that I know of:
First, based on how many iterations, like you would do.
Second, based on the difference between current Q value and previous Q value (i.e., insignificant difference means termination).


How to find a subset of numbers such that its average is close to the average of the full set? I have a set of n numbers whose average (arithmetic mean) is x. I have to choose a subset of k numbers from n such that its average is closest to x. Please note that k is the upper bound. If the average can be represented with less than k numbers, then that set is chosen.

For example:
set = {1, 2, 3, 4, 5, 6} (n = 6) (average = 3.5)
If k = 1 then the subset can be either {3} or {4}
If k = 2 then the subset is {3, 4}
If k = 3 then the subset is still {3, 4}

I have to write an algorithm for the same. If this problem is not solvable in polynomial time, what would be a good approach to solve it? Any heuristic approach?

I am not sure if you are allowed to use a solver for this, but this problem can be easily formulated as a Mixed Integer Nonlinear Programming (MINLP) problem.

This can be solved with open source solvers like Couenne or Bonmin. Actually this model can be linearized so it can even be solved with linear Mixed Integer Programming (MIP) solvers.


Non Turing-Recognizable from symmetric difference I have a question about how you would find a example of a non Turing-recognizable language from the symmetric difference of two Turing-recognizable languages. I believe this is possible, but I am having problems coming up with a example in my head. Does anyone have any hints, or ideas about how to think about this?

(Converting the comment hints and guidance into an answer)

If you take $A$ to consist of all strings, $A=\Sigma^*$, then $A$ is decidable and recognizable.
Then, we will take the second language, $B$, to be recognizable but not decidable.

Their symmetric difference will give us (by definition) $\overline B \triangleq \Sigma^* \setminus B$.

Now, let's get concrete. The halting problem, $HP$, is a recognizable non-decidable language. If we take $A=\Sigma^*$ and $B=HP$, then their symmetric difference is $\overline {HP}$. The last step is to show that $\overline {HP}$ is not-recognizable (but this is a very well known fact that $\overline{HP}\in coRE$ and not-recognizable, since if it was recognizable, then $HP$ would have become decidable, since for any input we would have a machine that says "yes" if it is the language, and another machine that says "no" if it is not).


Find a recurrence relation for merging of sublists of an array There are $\log n$ sublists each of size $\frac{n}{\log n}$. Write a recurrence relation for merging these lists into an $n$ element list.

My Approach
Let $m = \log n$. Then,
$T(m) = 2T(m/2) + O(n)$, where $O(n)$ is for merge algorithm.

We get $T(m) = 2T(m/2) + O(2^{m})$.

Now solving we get $T(m) = O(n)$.

But intuitively there are $O(\log\log n)$ levels each doing $O(n)$ work so complexity to merge should be $O(n\log\log n)$. Where am I wrong? Please help. Tried hard but unable to get loophole.

The mistake is when converting $O(n)$ to $O(2^m)$, and then varying $m$. In fact, $n$ is constant here and $m$ changes. So the recurrence relation is $T(m) = T(m/2) + O(n)$, whose solution is $T(m) = O(n\log m)$. Substituting $m = \log n$, we obtain $O(n\log\log n)$.


What is the difference between a prime attribute and a proper subset of the candidate key? I am taking DBMS classes and am currently studying the various normal forms. The following is the definition of a Prime Attribute I learned in class:

A prime attribute belongs to the set of attributes which compose the candidate keys.

For example, if R(ABCDEF) is a relation with the functional dependencies given as:

F = {AB -> C, D->E, C->F}
then,
Candidate Key will be ABD
and
the Prime attribute set will be {A,B,D}
and
the Prime Attributes are A,B and D.

The proper subset of a candidate key defines itself. For the above example, proper subsets of the candidate key for the relation R(ABCDEF) is:

{{A}, {B}, {D}, {A,B}, {A,D}, {B,D}}

From the above definitions, apart from the number of elements in either sets, it seems that a prime attribute and a subset of a candidate key are pretty much the same. Both of these terms are being brought up simultaneously while explaining Third Normal Form and Transitive Dependencies, which is confusing me. It would be nice if somebody clears the difference between them.

Prime attributes are, in your example, just A, B, and C. The subsets of the candidate key are combinations of prime attributes. The difference is subtle, but if you read your material carefully, it will become apparent.


Minimum capacity cut reduction from digraph with two edge weight sets Given a digraph $G$ and $f, g : E(G) \mapsto \mathbb{R}$, how would you find a cut $(X,\bar{X})$ with $s \in X$ and $t \in \bar{X}$ such that $\sum_{e \in \delta^+(X)}{f(e)} - \sum_{e \in \delta^-(X)}{g(e)}$ is minimized?

$\delta^+(X)$ is the set of edges going out of $X$ and $\delta^-(X)$ is the set of edges going into $X$.

I can solve for the case where $f = g$, simply by constructing a network flow graph with all edges adjacent to either $s$ or $t$. Since $\sum_{e \in \delta^+(X)}{f(e)} - \sum_{e \in \delta^-(X)}{f(e)}$ can be rewritten as $\sum_{e \in \delta^+(X)}{f(e)} + \sum_{e \notin \delta^-(X)}{f(e)} + constant$ then a graph can be constructed with an edge between $s$ and all $v \notin \{s,t\}$ with capacity equal to $\sum_{e \in \delta^-(v)}{f(e)}$  and an edge between all $v \notin \{s,t\}$ and $t$ with capacity equal to $\sum_{e \in \delta^+(v)}{f(e)}$. Then dealing with negative $f$ is simply a matter of adding the capacity to the $(v,t)$ edge instead of the $(s,v)$ edge and vice versa.

However this solution does not work when $f \neq g$ and I can't come up with an answer for this case.

The solution works for the case that $f=g$ because if we have an edge $(a,b)$, in the case that $a \in X, b \in \bar{X}$ then the edge is going out of X and not going into X, the contribution to the cut capacity is $2f((a,b))$ as per the formula containing the constant above. Then if you add $b$ to $X$, $a$ no longer contributes to the sum over edges going out of $X$ and so $f((a,b))$ is removed and you are left with $f((a,b))$. If $f \neq g$, then you are instead left with $f((a,b)) − g((a,b))$ which is incorrect.

In terms of what I have tried so far for the general case, the case that $g(x) < 0$ is trivial and the edge can simply be reversed and the capacity multiplied by $-1$ so that it is positive.

In the case that both $f,g > 0$ then I consider this local portion of the graph:

Let $f = f(a,b)$ and $g = g(a,b)$ in the above graph.
I can then transform it to this network graph:

Where the capacities are given by

$(s,b) = f$
$(b,a) = f - g$
$(a,t) = f$

Clearly this is only applicable in the case where $f > g$. Then in the case that $a$ but not $b$ is added to $X$ we have a net increase of $f$. When $b$ but not $a$ is added to $X$ we have a net decrease of $g$. When both $a$ and $b$ are added to $X$ there is no net change.

However I cannot reconcile this with the case where $f < g$ or $f < 0$.

This problem is NP-hard.

Consider the $f=0$ case, then you are trying to minimize $-\Sigma_{e\in\delta^-(X)}g(e)$, i.e. maximize $\Sigma_{e\in\delta^-(X)}g(e)$. This is exactly the maximum cut problem, which is NP-hard.


Is Logical Min-Cut NP-Complete? Logical Min Cut (LMC) problem definition

Suppose that $G = (V, E)$ is an unweighted digraph, $s$ and $t$ are two vertices of $V$, and $t$ is reachable from $s$. The LMC Problem studies how we can make $t$ unreachable from $s$ by the removal of some edges of $G$ following the following constraints:

The number of the removed edges must be minimal.
We cannot remove every exit edge of any vertex of $G$ (i.e., no vertex with outgoing edges can have all its outgoing edges removed).

This second constraint is called logical removal. So we look for a logical, minimal removal of some edges of $G$ such that $t$ would be unreachable from $s$.

Solution attempts

If we ignore the logical removal constraint of LMC problem, it will be the min-cut problem in the unweighted digraph $G$, so it will be solvable polynomially (max-flow min-cut theorem).

If we ignore the minimal removal constraint of the LMC problem, it will be again solvable polynomially in a DAG: find a vertex $k$ such that $k$ is reachable from $s$ and $t$ is not reachable from $k$. Then consider a path $p$ which is an arbitrary path from $s$ to $k$. Now consider the path $p$ as a subgraph of $G$: the answer will be every exit edge of the subgraph $p$. It is obvious that the vertex $k$ can be found by DFS in $G$ in polynomial time. Unfortunately this algorithm doesn't work in general for an arbitrary directed graph.

I tried to solve the LMC problem by a dynamic programming technique but the number of required states for solving the problem became exponential. Moreover, I tried to reduce some NP-Complete problems such as 3-SAT, max2Sat, max-cut, and clique to the LMC problem I didn't manage to find a reduction.

I personally think that the LMC problem is NP-Complete even if $G$ is a binary DAG (i.e., a DAG where no node has out-degree greater than 2).

Questions

Is the LMC problem NP-Complete in an arbitrary digraph $G$? (main question)
Is the LMC problem NP-Complete in an arbitrary DAG $G$?
Is the LMC problem NP-Complete in an arbitrary binary DAG $G$?

Let G = (V, E) be a weighted DAG, s and t be two vertices of G, and LSTMC = (G, s, t) be an instance of the logical s-t min-cut problem. It is obvious that the LSTMC problem is NP.Now, we should show that the LSTMC is NP-Hard. We reduce the hitting-set problem to the LSTMC problem. Let S = {s1, s2, ..., sn} be the given sets and {a1, a2, ..., am} be the union of all the sets. Given the number k1, the decision problem of the hitting set problem states whether there exists a set A with k1 elements such that every element of S (every set si s.t. i = 1..n) contains at least one element of A. We denote the hitting set problem as HS(S). We construct the weighted DAG G′ from the set S by Algorithm HS2LSTMC. This algorithm considers s as the source vertex of the DAG G′. For each set si of HS s.t. i = 1..n, the algorithm considers the corresponding vertex, si, and adds an edge with infinite weight from s to each si. Then, for each element aj of the union of the input sets s.t. j = 1..m, the algorithm considers the corresponding vertex, aj, and adds an edge with zero weight from each si to any aj s.t. aj ∈si in HS. Finally, the algorithm considers two final vertices called t and k, and add two edges from each aj s.t. j = 1..m to the both final vertices. It is clear that G′ can be made in polynomial time.

Now, we should demonstrate that HS(S) has an answer with k1 elements if and only if LSTMC = (G′, s, t) has an answer with some logically removed edges such that the sum of the weights of the removed edges is k1.

For simplicity, we perform this part of proof, by providing an example:

In the following figure, suppose that S = {s1, s2, s3} such that s1 = {1, 2, 3}, s2 = {1, 4}, and s3 = {2, 5}. Fig. 2 shows the weighted DAG G′ of the LSTMC problem corresponding to the hitting set problem HS(S). In this example, the set A, namely the union of all elements of S, is A = {1, 2, 3, 4, 5}. We have |S| = 3 and |A| = 5. This example shows how an arbitrary instance of the hitting set problem can be solved by the help of a specific instance of the logical s-t min-cut problem in a weighted DAG. If we compute an answer to LSTMC = (G′, s, t) and consider those removed edges of the answer which are in the form of (aj, t) called E1 (1 ≤ j ≤ m), then the tail set of E1 is an answer to HS(S). An answer to the LSTMC problem is the edge set E1 = {(s1, 2), (s1, 3), (s2, 4), (s3, 5), (1, t), (2, t)}. So, the tail set of the subset E2 = {(1, t), (2, t)} of the edge set E1, namely the set {1, 2}, is an answer to the HS(S).


How to prove that finding math proofs is $\text{NP}$-hard? This is Exercise 2.11 of the book "Computational Complexity: A Modern Approach" by Arora and Barak.

Mathematics can be axiomatized using for example the Zermelo-Frankel system, which has a finite description. Argue at a high level that the following language is $\text{NP}$-complete. (You don't need to know anything about ZF.)
$$\text{THEOREMS} = \{ \langle \varphi, 1^n \rangle: \text{math statement } \varphi \text{ has a proof of size at most } n \text{ in the ZF system}. \}$$

It is easy to show that $\text{THEOREM} \in \text{NP}$. However, how to prove it is $\text{NP}$-hard?
In addition, why is it $1^n$ instead of just $n$ in $\langle \varphi , 1^n \rangle$? Does this encoding scheme matter with the $\text{NP}$-hardness proof?

Define $\mathrm{Bool}$ to be the set of all subsets of $\{\varnothing\}$ (or some arbitrary set with 1 element). Then represent a propositional variable $x$ by some subset $x\in\mathrm{Bool}$, i.e. $x\subseteq\{\varnothing\}$.

Now there is an extremely straightforward translation $\rho$ of propositional formulae into such subsets:

$\rho(x)$ if $x$ is a variable is just some set (also called $x$) $\in\mathrm{Bool}$.
$\rho(\neg\phi)$  into the complement of $\rho(\phi)$ in $\mathrm{Bool}$.
$\rho(\psi\vee\phi)=\rho(\psi)\cup\rho(\phi)$
$\rho(\phi\wedge\psi)=\rho(\psi)\cap\rho(\phi)$

And you don't need any other connectives to get a polynomial sized translation of a propositional formula.

Then a formula $\phi$ is satisfiable iff
$$ ZF\vdash\exists x_1\ldots x_n\in\mathrm{Bool},\ \rho(\phi) \neq \varnothing$$

I'll let you work out the details. One important thing, though, is to show that a proof will be proportional in length to $n$, where $n$ is the number of variables.


"Semantic Web", "Semantic Network", "Semantic Search", "Knowledge graph"(not Google's Knowledge Graph) and "knowledge base" who can help me explain the concepts of  "Semantic Web", "Semantic Network", "Semantic Search", "Knowledge graph"(not Google's Knowledge Graph) and "knowledge base" and the relations among them?

Semantic Web is a set of technologies that want to make the data on the web readable and understood by machines. The domain that semantic web is the web. Therefore the URI is in the bottom of the technologies stack.

Semantic Network is a graph model to store the information. If you can model your data as a graph with node and edge, you can think it as a semantic network.

Knowledge graph is also a kind of graph model. However, it emphasis the store of all data on the level of both schema and individual. Therefore, it has no essential difference with Semantic network.
Knowledge base is an instantiated storage of a domain knowledge. You can think it as a database. It has not to be a graph model, if you can store the knowledge in some way, you can call it as knowledge base.


Is this clique algorithm in polynomial time correct or might it have another time complexity? I came up with the idea finding a k-clique through starting at a small s-clique (like 1-,2- or 3-clique) and use it to find every s+1 Clique iterative. I had some trouble finding the Time Complexity and I am not sure where I might have went wrong.
First I will show the algorithm, argue about its correctness and then what I tried on finding the time complexity.
So given a Graph $G = (V,E) $ and $n = |V|$ and $m = |V|$  and the case of k > 3 we would use the following algorithm:

Find every 3-Clique first in $O(n^3)$ (using three for loops for checking every possible triangle) and using hashing whether a triangle was already added or not.
Now we have the set $M := \{(i,j,k) | i,j,k \in V \land (i,j), (i,k), (j,k) \in E \}$ of triples of all disting 3-cliques.
Next we use the list of 3-Clique to search for 4-Clique through looking at every adjacent node $l$ of of every triple $(i,j,k)$.
If one the the adjacent nodes is connected to all $(i,j,k)$ so that $(l,i),(l,j),(l,k) \in E$ we have found a 4-Clique.
We proceed this process for every s-Clique with $s \in \{4,...,k \} $ usingal found $s-1$ clique

For the correctness of the algorithm it should be enough to show by induction that every s-clique consists of s-1 possible (s-1)-cliques. So once we have all s-1-clique it is easy to find every s-clqiue, since we just have to check every adjacent node of the s-1-clique for a connection with every node in the s-1-clique.
I tried to estimate the time complexity the following way:

Worst Case Complexity is finding a n-Clique in $G$. So this means we have $ m = n(n-1) $

We would have to do  $(n - 3)$-Loops for finding every s-clique in the sth loop.

In every loop we have less n s-clique where every s-clique might have maximum $s(n-1)$ adjacent nodes to look at.

Since we have less then n s-clique this would mean looking at $n*s(n-1)$ possible edges for finding a new s-clique.

This would sum up to $O(n^5)$ using gauss sum for every s-clique, but this would mean clique is in P and this seems a little bit to easy to be true.

Your analysis of the time complexity is wrong. Specifically this statement:

In every loop we have less n s-clique where every s-clique might have maximum s(n−1) adjacent nodes to look at.

In fact you can have up to $\binom{n}{s}$ $s$-cliques.
You approach is essentially enumerating all cliques of size up to $k-1$. So you cannot hope to have a running time better than $\Omega\left( \sum_{s=1}^{k-1} \binom{n}{s} \right)$.


Complexity of $n \times \log n$ tiling problem Is there a polynomial time algorithm for an $n \times \log n$ tiling problem?

For instance: Suppose $A$ is a finite alphabet. A tile is a $2 \times 2$ matrix of elements from $A$. A tiling is a matrix of tiles in which any adjacent symbols (including diagonally) in neighboring tiles are equal.

The Tiling Problem is as follows. Given a set of tiles $T$ and a sequence $C_1$ of $\log n$ tiles from $T$, is there an $n \times \log n$ tiling of $T$ whose first row is $C_1$?

Hint: Use dynamic programming, going row by row. Use the fact that there are only $\log n$ many columns, and so only $|A|^{\log n} = n^{\log |A|}$ many different configurations of each column.

(The resulting algorithm will be polynomial in $n$ but not in the input size, which is only $O(\log n)$.)


Interview question (constant-time algorithm, ILP) A juice machine has three buttons small, medium large. Each size adds an amount of juice in a range to the cup. Eg small might add from 10-20 mL, medium from 30-35 mL, large from 40-50 mL. The exact numbers are relatively small (0-1000), integral, and known ahead of time

Input: cup size (mL), amount to fill (mL)

Output: whether or not a sequence of button presses can be constructed that is guaranteed to fill the cup with at least amount_to_fill mL while not overflowing the cup. A different sequence of button presses cannot be performed depending on how much the previous button presses ended up filling the cup, ie the sequence must be fully determined before any of the buttons are pressed.

This trivially reduces to the integer linear programming problem:

Given a,b,c,d,e,f,G (all integers, G very large, the rest relatively small)

maximize: ax+by+cz s.t. dx+ey+fz < G and x,y,z are integers

for which, the maximum can apparently be found in constant time. Denote this maximum M(a,b,c,d,e,f,G). What is the closed-form solution to M?

After glancing at http://www.lume.ufrgs.br/bitstream/handle/10183/66091/000870881.pdf;sequence=1,

I think I figured it out.

Something along the lines of, wlog, let (a,d) have ratio a/d >= b/e >= c/f.

Then y is capped at d/gcf(e,d) and z is capped at d/gcf(f,d). brute force all possible (y,z) possibilities in constant time, fill in the corresponding x=floor[(G-ey-fz)/d] (constant time), and select the maximum ax+by+cz (constant time). QED.

This solution seems a bit inefficient and although there may be a better constant-time solution out there (particularly, for d>100), it scales well for large G which is all that really matters for this question.


Normal order sequencing vs applicative order sequencing I'm trying to understand this lecture, section 2.7. Why would the normal order sequencing print out "hello" "world" and not "world" "hello"? I may be misinterpreting the order in which the arguments are applied.

It looks like the expression

$$
((Seq (display "hello"))\; (display "world"))
$$

would evaluate to

$$
\lambda z.((display "world")\; (display "hello"))
$$

and that would, under normal order, would print out "world" "hello".

My question is whether the assumption I'm making is correct. If not, could you show the correct derivation of the end-expression?

You're misreading the combinator. In these lecture notes, lambda abstraction binds tighter than application (the opposite convention is more common — it's apparent from the spacing but the author should state that explicitly). I'll use extra (redundant) parentheses in my answers to avoid any potential for ambiguity. The combinator is
$$ \mathit{Seq} = \lambda x. \lambda y. ((\lambda z.y) \: x)$$
So
$$ \begin{align}
  & ((\mathit{Seq} \; (\text{display "hello"})) \; (\text{display "world"})) \\
  &\qquad = (((\lambda x. \lambda y. ((\lambda z.y) \; x)) \; (\text{display "hello"})) \; (\text{display "world"})) \\
  &\qquad \to^2 ((\lambda z. (\text{display "world"})) \; (\text{display "hello"})) \\
  &\qquad \xrightarrow{\text{display "hello"}} (\text{display "world"}) \\
  &\qquad \xrightarrow{\text{display "world"}} \mathord{?} \\
\end{align} $$
where $M \xrightarrow{\text{action}} N$ means that $M$ evaluates to $N$ performing the specified action.


Difference between a TM with an empty language and the one accepting empty string If a TM(Turing Machine) accepts NO input string(even the blank), then its language is empty.

If a TM ONLY accepts the blank string(meaning that there is nothing on the tape except for the default blank characters), then its language has only one item and it is the blank string.

Are these definitions correct?

Could you describe the TM for each?

Also, this might be irrelevant but let me ask: I saw somewhere that there must be at least two states for a TM. Which states must be there all the time in a TM?

The definitions (well, descriptions) look correct, more or less.

A TM accepting the empty language may move directly into the halt reject state, regardless of what may or may not be on the input tape.

A TM accepting the language consisting of only the empty string may examine the first tape symbol. If the symbol is a blank, it could move to the halt accept state. Otherwise, it would move to the halt reject state. We don't have to worry about the user providing an input that starts on some later position in the tape since the blank symbol is not allowed in the input alphabet.

To summarize:

A TM for $\{\epsilon\}$ has pseudocode:

if tape[1] is blank then accept else reject

A TM for $\emptyset$ has pseudocode:

reject

or, if it helps you make the difference even clearer:

if tape[1] is blank then reject else reject

As Yuval points out in the comments, there are infinitely many TMs accepting one or the other of these languages; the two suggested here are for illustrative purposes only.

[EDIT]Some additional discussion motivated by recent comments.

(1) Depending on what your definition of a TM is and/or how explicit you want to be, there are two possibilities. If you want your machine to explicitly enter a halting state for every input tape, then yes, you will have a transition to the halt reject state on every symbol of the input alphabet. If you allow your Turing machine to reject strings by "crashing" (reaching a configuration for which there is no defined transition), then these transitions aren't necessary; simply transition to halt accept on blank, and let the machine crash in all other cases.

(2) Yes, the machine which accepts the empty language always rejects. Notice that it is perfectly acceptable to define automata with accepting states which are never reached (depending upon your definition, of course). In particular, we could take any arbitrary TM and change it to accept the empty language by changing all transitions from the initial state to lead to the halt reject state.

(3) Typically, TMs are understood to have two special states in addition to any "user-defined" states: the halt accept and halt reject states, which the TM enters to explicitly accept or reject, respectively, some input. In addition to these two states, an initial state is required from which to begin processing the input. By my reckoning, this means that every TM has at least three states. Notice, though, that not all of these states needs to be used by any given TM. In particular, a valid TM might endlessly loop on the initial state for all inputs; this TM will accept the empty language (although it doesn't decide it; to decide it, it needs to enter one of the halting states for each input).


Algorithm: Finding shortest path through a dungeon in a game Background

I was playing the PC-Game "Darkest Dungeon" recently. In the game, you have to explore dungeons, which consist of connected rooms as shown in the picture below.

Here are the rules:

You start in fixed room (Entrance). You cannot choose where to start.
The goal is to visit every room at least once
The distance between adjacent rooms is the same for all rooms.
You can visit rooms and walk paths as often as you'd like

Question

What is the shortest path from the entrance that visits every room at least once?

Subquestions:

What algorithm(s) could be used to solve this problem?
Are there implementations that are free (and fairly simple) to use for someone like me?

What I tried

I have found other questions such as this or this without finding an answer. I am familiar with the (basic) TSP and are able to code and solve simple TSPs. Hamiltonian paths didn't solve my problem, because it doesn't allow for multiple visits. The Chinese postman problem does also not apply here in its basic form because I don't have to visit every edge.

Update

As I have stated in the comments, I'm not a computer scientist and am not interested in proving a mathematical statements (maybe I'll post this question on stackoverflow at a later stage). Also, I'm not a programmer and the chances that I'm able to code a solution myself are pretty slim. But I suspect I'm not the first one dealing with a problem of that nature.

According to @Shreesh and @Dib, the following procedure could be applied:

Create a pairwise distance matrix with all rooms thus adding edges between all rooms.
Solve TSP using a standard solver (e.g. concorde)
Starting from the Entrance, visit all rooms according to the solution. For non-adjacent rooms, substitute the shortest distance between those rooms.

Will this procedure provide the answer to the problem?

Travelling Salesman Problem, even if you allow repeating nodes is NP-hard. See Computational Complexity of TSP.

Umans and Lenhart show hardness results for Hamiltonian Graphs in Solid Grid Graphs, 1997.

TSP for Euclideal Case (or graphs with triangle inequality) also imply NP-hardness of TSP with node repetition. TSP even for manhattan distance $L_1$ (or $L_\infty$) metric is NP-complete. See the original Papadimitriou's paper on the topic.

You may be able to prove NP-hardness of TSP for your case by adding arcs to nodes that have corresponding distance as length of shortest path between nodes which will simulate repetitions of the nodes. TSP for your special case looks like an NP-complete problem.

So either write a sufficiently good (heuristic wise) exponential branch and bound algorithm to compute a shortest tour (which may not be all that inefficient, if your graph is small) , or forget about optimization and calculate a good enough approximation.


Top-down typing strategy - is there a name for this? In most statically typed languages, each expression has an intrinsic type. E.g. in Java, 3 is an int, 3.0 is a double, 3+3.0 is also a double. Types do not depend on the context of the expression.

However, in the CSS type system described in the spec, some expressions have a type depending on the context. For example, the red token can be a <color>, a <custom-ident>, or an <attr-name>, depending on the context in which it is used.

I want to build a type system for a CSS-based programming langauge. In this type system, I want to use a typing strategy that does not go from the bottom up (starting from the leaves in the AST), but top down (starting from the root of the AST).

For example, when the compiler needs to derive that the linear(red, yellow) expression inhabits the <bg-image> type, it would do the following derivation:

we want to derive that
  linear(red, yellow) :: <bg-image>
<bg-image> is defined as <url> | linear(<color>, <color>), so
  linear(red, yellow) :: <url> | linear(<color>, <color>)
let us try the second branch
  linear(red, yellow) :: linear(<color>, <color>)
let us check sub-expressions
  red :: <color>
  yellow :: <color>
everything fine, OK

Can you point me to scholarly articles where this kind of typing strategy is discussed?

P.s. I don't know of other languages where a type of the expression depends on the context, except for Perl. In Perl, ("a","b") can be interpreted as either a list or an integer (its length), depending on the context:

print ("a","b") # => ab
print 0+("a","b") # => 2

There is no top-down or bottom-up typing strategy when defining a language. It is an implementation issue. A type system will
only define operator operand constraints on your AST. The kind
constraints is fixed by the type system and is part of the design of
the language. It can be very simple as in older languages, or be a
sophisticated logical system. Even when simple, it can be seen as a
logical system. Your AST may be seen as a proof tree in that logical
system, where the nodes are to be decorated by types, that may be seen as logical
propositions proved by by the sub-tree dominated by that node . For example, the type int found for an expression is
a predicate satisfied by the expression.

So you can associate type inference rules to the operators of your
AST. For example if you have an AST operator +  with two operands,
you can associate (among others) the inference rule:
$X::int \,\wedge\, Y::int \;\Rightarrow\; X+Y::int$

Defining the type system of a language amount to defining such rules
for all AST operators where that make sense, i.e. involved with the
type system.

Type checking your program consists in finding a type for each
(relevant) AST node, such that that there is an inference
rule (associated to the operator of that node) that is satisfied by
the node type and the types of its operands.

This can be done with top-down or bottom-up algorithms, or any
mix. That is only a matter of finding efficient algorithms. But the
checking strategy is an implementation issue, not a language
definition issue. However, it is advisable to choose a type system
that allows for a tractable type checking strategy.

Note that the types may not be all completely defined by the type system,
and the checking strategy may actually infer the "details" of these
types, in particular by means of unification techniques.

The above description may not seem too complex (I hope). One hidden
aspect, that makes the whole thing a lot more interesting, is that
in static typing (particularly) all occurences of the same variable
must have the same type, which introduces additional constraints.
But getting into the details is too much for a normally sized answer.

For more about this, you should look for type inference.


What do we know about NP ∩ co-NP and its relation to NPI? A TA dropped by today to inquire some things about NP and co-NP.
We arrived at a point where I was stumped, too: what does a Venn diagram of
P, NPI, NP, and co-NP look like assuming P ≠ NP (the other case is boring)?

There seem to be four basic options.

NP ∩ co-NP = P

In particular, co-NPI ∩ NPI = ∅
NP ∩ co-NP = P ∪ NPI

In particular, co-NPI = NPI?
NP ∩ co-NP ⊃ P ∪ NPI ∪ co-NPI

A follow-up question in this case is how NPC and co-NPC are related;
is there an overlap?
Something else, that is in particular some problems from NPI are
in co-NP and others are not.

Do we know which is right, or at least which can not be true?

The complexity zoo entries for NPI and NP ∩ co-NP do not inspire much hope that anything is known, but I'm not really fluent enough in complexity theory to comprehend all the other classes (and their impact on this question) floating around there.

The fact that P ≠ NP does not preclude the possibility that NP = co-NP, in which case NP ∩ co-NP = NP. So to further the discussion, let us assume that NP ≠ co-NP. In that case, Corollary 9 in Schöning's A uniform approach to obtain diagonal sets in complexity classes shows that there exists some language in NP – co-NP which is NP-intermediate. So NPI strictly contains (NP ∩ co-NP) - P (note that every language in NP ∩ co-NP is in P ∪ NPI). This is your option (4).

In summary, assuming P ≠ NP and NP ≠ co-NP, we get this:

[source]


Is it possible to define a DFA for the language of words having exactly one double letter? Consider the language $\{ w \in \Sigma^*~|~ w~\text{contains exactly one double letter}~\}$. For example,
$baaba$ has exactly one double letter, but $baaaba$ has two double letters.

Suggested answer for the case where $\Sigma = \{a,b\}$ (even if it's an RE not a DFA): $(\epsilon \cup b)(ab)^*aa(ba)^*(\epsilon \cup b) \cup (\epsilon \cup a)(ba)^*bb(ab)^*(\epsilon \cup a)$.

In general, if you claim to have found a regular expression for the language, you can follow Thompson's algorithm to convert that expression into an NFA and then using subset construction to convert that NFA into a DFA.


Is Starvation Possible in LOOK Algorithm The LOOK algorithm (wiki) is the same as the SCAN algorithm in that it also honors requests on both sweep direction of the disk head, however, this algorithm "Looks" ahead to see if there are any requests pending in the direction of head movement. If no requests are pending in the direction of head movement, then the disk head traversal will be reversed to the opposite direction and requests on the other direction can be served.

In wiki there is a line which says

  LOOK behaves almost identically to Shortest seek time first (SSTF),
  but avoids the starvation problem of SSTF.

Is it(LOOK) always successful in avoiding starvation or there might be some order of disk request where it may lead to starvation.

The wiki article also says that

  This is because LOOK is biased against the area recently traversed, and heavily favors tracks clustered at the outermost and innermost edges of the platter.

However, I found it confusing.

The reason why LOOK avoids starvation is quite easy: For any request, it will be served within a finite time interval $t$ (since it is submitted): Suppose the number of cylinders in a disk is $N$, then we can set $t = 2N$.


Given an array of integers and a value k, find the length of the longest subarray with max-gap no more than k I'm struggling with this problem: you are given an array $A$ of $n$ integers and a number $k \in \mathbb{N} : k \neq 0$. The problem asks to find an algorithm that runs in $\Theta(n)$ that returns the length of the longest subarray $A'$ in $A$ s. t. $\max(A')-\min(A') \leq k$.

For example, in the array $A = \{6, 5, 9, 10, 7, 13, 8, 7, 5, 15\}$ with $k = 6$ the algorithm must return 6, because the subarray $A' = \{9, 10, 7, 13, 8, 7\}$ has length 6 and the difference between its maximum and its minimum is no more than 6.

Another example, with $A = \{1, 3, 5, 2, 3, 1, 7\}$ with $k = 2$ the result is 3, because the subarray $A' = \{2, 3, 1\}$ has length 3 and the difference between its maximum and minimum is less or equal than 2.

So far I tried to build an algorithm that goes like this (it may be buggy, it's just a draft to make my idea of solution clear):

int test(int* arr, int len, int k) {
    int minIndex = 0;
    int maxIndex = 0;
    int start = 0;
    int end = 0;
    int maxLength = 0;
    for (int i = 1; i < len; i++) {
        end = i;
        // Update the minimum and maximum if necessary while scanning the array
        if (arr[i] < arr[minIndex])
            minIndex = i;
        if (arr[i] > arr[maxIndex])
            maxIndex = i;
        // Check the new maximum/minimum doesn't make the subarray invalid
        if (arr[maxIndex] - arr[minIndex] > k) {
            // We broke the subarray, check the length of the longest subarray until now
            if (end - start > maxLength)
                maxLength = end - start;

            // Restart from the second element, then the third, and so on
            start++;
            maxIndex = minIndex = start;
            i = start;
        }
    }

    return maxLength;
}

The main problem with this algorithm is that in the worst case it runs in $\Theta(n^2)$, which doesn't comply with the problem's requests.

Basic idea:
Use 2 pointers to traverse the array: start and end. Both start at the beginning of the array. Try moving end one position at a time and track the maximum subarray length, until the gap is too large. When that happens, move start towards end until you have smaller gap or you meet with the end pointer (the subarray becomes empty).

How to evaluate the gap: by definition max - min of current subarray. So we keep track of min and max.

Have a min deque where you keep elements in ascending order, so that the head of the queue will be the current minimum.
When encountering a new element: remove all elements larger than it from the back of the queue, then add the new element to the back of the queue. This guarantees ascending ordering.

Have a max deque where you keep elements in descending order, so that the head of the queue will be the current maximum.
When encountering a new element: remove all elements smaller than it from the back of the queue, then add the new element to back of the the queue. This guarantees descending ordering.

NB: You don't keep the elements themselves in the min and max queues; instead, keep their indices in the original array! This way you have both position and value, which is important for the following step.

When the gap becomes too large: obviously you cannot increase end before first bringing start closer to it. So increate start by one. Now check the head of both queues: they are the indices of current min and current max. If any (or both) these indices are now lower than start, then they don't belong to the current subarray anymore. Drop them, the head of the queue will be the new min/max.

Continue until end reaches the end of the array.

This gives you linear complexity: each element is processed once, and added and removed at most once from each queue.

Java implementation:

public int find(int[] numbers, int maxGap) {
    int best = 0;
    int bestStart = 0, bestEnd = 0;

    Deque<Integer> minQueue = new LinkedList<>();
    Deque<Integer> maxQueue = new LinkedList<>();

    int start = 0, end = 0;

    while (end < numbers.length) {
        int x = numbers[end];

        // add end to the minQueue keeping increasing order
        while (!minQueue.isEmpty() && numbers[minQueue.peekLast()] >= x) {
            minQueue.removeLast();
        }
        minQueue.addLast(end);

        // add end to the maxQueue keeping decreasing order
        while (!maxQueue.isEmpty() && numbers[maxQueue.peekLast()] <= x) {
            maxQueue.removeLast();
        }
        maxQueue.addLast(end);

        // minimum is at the front of minQueue
        int minIdx = minQueue.peekFirst();
        int minVal = numbers[minIdx];

        // maximum is at the front of maxQueue
        int maxIdx = maxQueue.peekFirst();
        int maxVal = numbers[maxIdx];

        // check
        if (maxVal - minVal > maxGap) {
            start++;
            if (start > minQueue.peekFirst()) {
                minQueue.removeFirst();
            }
            if (start > maxQueue.peekFirst()) {
                maxQueue.removeFirst();
            }
        } else {

            // track progress
            if (end - start + 1 > best) {
                best = end - start + 1;
                bestStart = start;
                bestEnd = end;
            }

            end++;
        }
    }

    // debug
    for (int i = bestStart; i <= bestEnd; i++) {
        System.out.print(numbers[i] + " ");
    }
    System.out.println();

    return best;
}


How to feed videos to a neural network I have been coding and testing Neural Networks for a while but as of now I have only used IMAGE datasets. (i.e. I have M training images and N testing images).

Some datasets are video datasets. The UCSD Peds dataset for example has the following variants:

Peds 1: 34 training videos (of 200 frames each) and 36 testing videos (of 200 frames each)
Peds 2: 16 training videos (of varying number of frames) and 12 testing videos (of varying number of frames)

So basically, in this case, I have M SETS of training images and N SETS of testing images.

I know the inputs to a neural network is arbitrary and anything can be fed, but I do not really understand how to feed a set of videos.

Will we merge all the 34 x 200 = 6800 training frames together and 36 x 200 = 7200 testing frames together and use the resulting set just like we use MNIST, etc?

How do we feed a set of training videos to a neural network?

What if I want to detect anomalies in the test videos? For example a neural network is trained using videos from UCSD dataset involving only pedestrians. And tested on videos which also have cars and bikes. So these cars and bikes are anomalies.

I'd want to classify an entire video on whether it contains just normal elements or some anomalous elements as well.

If you want to detect anomalies, my suggestion would be to build a classifier to classify individual frames of the video to determine whether that frame contains an anomaly.  You'll need to categorize what you count as an "anomaly" and arrange for labelled data in your training set.  But then you can extract all 6800 frames from the training videos, label each frame, and train a classifier on that training set of 6800 images.  At this point the problem is the same as building a classifier on individual images.  Then, given a test video, you apply the classifier to each frame to determine whether any of its frames contain an anomaly, and aggregate those results somehow (e.g., report the video as anomalous if the number of anomalous frames exceeds some threshold).


monotone min 3-sat polynomial algorithm? I know that 3SAT is npc but i wonder why my little algorithm won't solve this problem:

given positive 3SAT - meaning: each of the m clauses is a disjunction of 3 literals over the variables x1,…,xnx1,…,xn (nn variables) and each literal is a positive appearance of a variable (no  xi xi).

for example: (x1∨x3∨x7)∧(x5∨x4∨x2)(x1∨x3∨x7)∧(x5∨x4∨x2)

In other words: The problem is probably called MIN 3SAT, which every literal is positive but you must find minimum integer k such that there exists a truthful assignment of the variables which sets k variables to TRUE.

What is wrong with this "greedy" algorithm?:

run through all left clauses and find the variable that appears in most of them (can be implemented by counters array..). take this variable, give him truth assignment, remove all clauses which he appeared in, zero the counters array and do again the previous step. stop when no clauses left. it looks like this algo runs in O(m2n)O(m2n) time.

why isn't it an optimal algorithm?

UPDATE: Can someone give me an example to why the greedy algorithm won't give the optimal solution? I can't figure why the greedy approch is not good..

The problem MIN-3SAT is usually know as "minimum vertex cover for 3-uniform hypergraphs". Any reasonable algorithm that you will suggest will give a 3-approximation (or worse), and indeed, it is conjectured (and follows from the unique games conjecture) that no polynomial time algorithm can improve on this approximation ratio.

This means that if you try hard enough, it is extremely likely that you will find an instance in which your greedy approach gives a solution which is roughly 3 times as worse as the optimal solution. I'll let you find it on your own.


How does SETH implies ETH? I know that ETH states that 3-SAT is not solvable in $2^{o(n)}$ time, the best known bound for 3-SAT is around $O(2^{.38n})$. Whereas, SETH states that there is no universal $\delta$ such that for every positive integer $k$, a $k$-SAT problem is solvable in $O(2^{\delta n})$ time.

It is not clear to me that how does SETH is stronger, and SETH implies ETH.

Thanks

The more usual (and slightly stronger) formulation of the exponential time hypothesis is that there is $\epsilon > 0$ such that solving 3SAT requires time $\Omega(2^{\epsilon n})$ (see, for example, Abboud, Backurs and Williams), where $n$ is the number of variables.

The strong exponential time hypothesis states that for each $\epsilon > 0$ there exists $k\ge3$ such that solving $k$SAT requires time $\Omega(2^{(1-\epsilon)n})$ (again, see the paper mentioned above).

Showing that SETH implies ETH isn't trivial. The idea is to show that $k$SAT reduces to sparse $k$SAT, which is $k$SAT restricted to instances with $O(n)$ clauses. Such instances can be coded as 3SAT instances with $O(n)$ variables. Therefore if we can solve 3SAT in time $O(2^{\gamma n})$ for every $\gamma>0$, then we can also solve $k$SAT in time $O(2^{\gamma n})$ for every $\gamma>0$. For the details, consult Impagliazzo, Paturi and Zane, Which problems Have strongly exponential Complexity?.


Chinese postman problem, but criteria = visit each vetex at least once Chinese postman problem, but where the postman have to visit each vetex at least once.

Is there a name for this problem?

What is the ideal algorithm to solve this problem?

Let $G$ be an edge-weighted graph. Create a new graph $G'$ in which the weight of the edge $(x,y)$ is the cost of the shortest path between $x$ and $y$ in $G$. The problem you are interested in is the traveling salesman problem (TSP) on $G'$.


Pumping Lemma Question: About the cases for y in the xy^iz criterion Problem statement:
Let $\Sigma = \{a, b, c\}$, and consider the task of multiplication encoded in the language $L = \{a^n b^k c^{nk} : n \geq 0, k \geq 0\}$.
Prove that L is not regular using the pumping lemma.

Relevant sources:
Sources (from three different people) arguing in favour of cases (where the links that are videos are set to the exact frame that I want you to see - there's no need to watch the video(s)):

https://youtu.be/dikEDuepOtI?t=393
https://youtu.be/Ty9tpikilAo?t=474
https://youtu.be/g4e2RElzCSQ?t=1282
https://www.physicsforums.com/threads/non-regular-language-pumping-lemma.945301/

My attempted solution:

$L = \{a^n b^k c^{nk} : n ≥ 0, k ≥ 0\}$
Let us choose the string generated when $n = k = P = 2$. That is, let us choose $S = a^2 b^2 c^4$ as a string.
Furthermore, let us assume that $S$ is regular.
Then, we try to make that string be of the form $S = xyz$, and it should meet the criteria of the pumping lemma, which are that
(i) $x y^i z ∈ L$
(ii) $|y| > 0$
(iii) $|xy| ≤ P$
Then, there are six cases, and they are as follows:
I) $y$ only contains occurrences of a.
II) $y$ only contains occurrences of b.
III) $y$ only contains occurrences of c.
IV) $y$ contains occurrences of a and b.
V) $y$ contains occurrences of b and c.
VI) $y$ contains occurrences of a, b and c.
So, for the string $S$ to fulfill the criteria of the pumping lemma, it must be shown that (i), (ii) and (iii) each hold true for at least one of I), II), III), IV), V) and VI). That is, for the string to not fulfill the criteria of the pumping lemma, it must fail at least one of the three parts of the pumping lemma for all six of the above cases.
Case I):
Let $x = a$, $y = a$ and $z = b^2 c^4$. Then, it is indeed the case that $|y| = 1 > 0$ and that $|xy| = 2 \leq 2$. However, if an integer $i = 2$ is chosen, then a string $a a^2 b^2 c^4 = a^3 b^2 c^4 ∉ L$ is obtained. So, case I) fails.
Case II):
Let $x = a^2$, $y = b^2$ and $z = c^4$. Then, it is indeed the case that $|y| = 2 > 0$, but it is not the case that $|xy| = 4 \leq 2$, and so case II) fails. (There is no need to examine part (i) of the pumping lemma.)
Case III):
Let $x = a^2 b^2$, $y = c^2$ and $z = c^2$. Then, it is indeed the case that $|y| = 2 > 0$, but it is not the case that $|xy| = 6 \leq 2$. So, case III) fails.
Case IV):
Let $x = a$, $y = a b^2$ and $z = c^4$. Then, it is indeed the case that $|y| = 3 > 0$, but it is not the case that $|xy| = 4 \leq 2$. So, case IV) fails.
Case V:
Let $x = a^2$, $y = b^2 c$ and $z = c^3$. Then, it is indeed the case that $|y| = 3 > 0$, but is not the case that $|xy| = 5 \le 2$. So, case V) fails.
Case VI:
Let $x = a$, $y = a b^2 c$ and $z = c^3$. Then, it is indeed the case that $|y| = 4 > 0$, but it is not the case that $|xy| = 5 \leq 2$. So, case VI) fails.
Then, because all six cases have failed at least one of the pumping lemma’s criteria, it follows that the language $L$ is not regular.

My teacher's solution:

Assume for contradiction that $L$ is regular and apply the Pumping
Lemma. Let $m$ be the integer in the Pumping Lemma. Take $w = a^mb^1c^m$. Since
$w ∈ L$ and $|w| ≥ m$, we can write $w = xyz$ such that $|xy| ≤ m$ and $|y| ≥ 1$ and
any string of the form $xy^iz ∈ L$ for $i = 0, 1, 2, \dots$ This implies that $y  =a^k$ for some $k ∈ \{1, \dots , m\}$. Taking $i = 0$, we get that $xz = a^{m−k}b^1c^m ∈ L$; however, this
contradicts the definition of $L$, since $(m − k) \cdot 1 \neq m$. Contradiction.

Are we both correct? Is at least one of us wrong? Why?
Any input would be greatly appreciated!

Your proof doesn't work, since the pumping lemma only applies to large enough words. The pumping lemma states that if a language $L$ is regular, then there exists a constant $m$ such that all words in $L$ of length at least $m$ have a certain decomposition $xyz$ such that $|xy| \leq m$, $y \neq \epsilon$, and $xy^iz \in L$ for all $i \geq 0$. However, there is no guarantee for words of length smaller than $m$.

In your case, the word that you chose has size 8, which might conceivably be smaller than $m$, and so is not guaranteed to have the decomposition $xyz$ satisfying the properties stated above.

As an aside, if $L$ is finite than $m$ has to be larger than the size of all words in $L$ (why?), and in that case the pumping lemma cannot be applied to pump any word.


Why is there a 2n+1 comparison for a linear search algorithm? Suppose an algorithm goes through a list of n integers and for every iteration of the loop it is needs to check if the current evaluated element of the list is even. If it is even, return the index of the integer that is evaluated as even.

How come the algorithm would have 2n+1 comparison?

I thought linear search would have n comparision because it is going through n elements. +1 comparison for the if statement. So that would make the algorithm O(n+1) comparison, no?. Where did the extra n come from?

Pseudo-code:

procedure last_even_loc(a1,a2,...,an:integers);
location = 0;
for i = 1 to n

    if (a_i = 0) (mod 2) then location = i

return location;

procedure last_even_loc(a1,a2,...,an:integers)
1.location = 0;
2.for i = 1 to n
3.    if (a_i = 0) (mod 2) then location = i
4.return location;

statement 1 is executing only once.
statemet 2 is executing total n+1 times.
statement 3 is executing total n times.
statement 4 is executing only once.

The running time of the algorithm is the sum of running time of all the statements executed.so running time=1+1+n+(n+1)=O(2n+3)=O(n).so there is total n+1+n=2n+1 comparisons(statement 2 and 3).


Generators in category theory An object K in a category C is called a generator if, for all pairs of
  morphisms f, g : A → B between arbitrary objects A and B, f = g iff ∀e
  : K → A. f ◦ e = g ◦ e.

Source: http://events.cs.bham.ac.uk/mgs2012/lectures/ReddyNotes.pdf (Page 7, Definition 3)

Can someone help me break down the meaning of this definition?

  for all pairs of morphisms f, g : A → B  between arbitrary types A and B

A morphism can be thought of as a a mapping from one type to another?

f and g are morphisms from type A to type B?

  f = g iff ∀e : K → A. ...

Morphism f is equivalent to morphism g if and only if for the morphism type K to type A

  f ◦ e = g ◦ e

e applied to f is equivalent to e applied to g

Is my interpretation of this correct?

The number of steps in this definition blows my mind, can anyone help me visualize the entire definition?

The most obvious intuition comes from the notion of well pointed categories. A well pointed category is simply a category $\cal C$ in which the final object $1$ exists and is a generator for $\cal C$. This means that for every $f,g:A \rightarrow B$,
$$ f = g \ \Leftrightarrow \forall p:1\rightarrow A, f\circ p = g\circ p$$

Note that $\circ$ is composition and not application! In haskell you would define:

f `comp` g = \x -> f (g x)

In programmatic notation the definition of well-pointedness gives

f == g iff for all p : () -> A, f `comp` p == g `comp` p

or unfolding the definitions

f == g iff for all p : () -> A, \x:() -> f (p x) == \x:() -> g (p x)

if we assume that the only inhabitant of () is in fact () (which is not the case in haskell, btw), then we get

f == g iff for all p : () -> A, \_ -> f (p ()) == \_ -> g (p ())

assuming extentionality (functions are equal if they are equal on all arguments)

f == g iff for all p, f (p ()) == g (p ())

Now the crucial observation, is that in "reasonable" categories, like $\mathrm{Set}$, morphisms $1\rightarrow A$ can be identified with elements of $A$ which gives

f == g iff for all x : A, f x == g x

which is obviously true in $\mathrm{Set}$ (this is exactly extentionality). Now note that "elements of an object of $\cal C$" doesn't even make sense in a general category, where objects are just "things" that can have morphisms into or out of them.

So the notion of well-pointedness says 2 things:

It's reasonable to treat morphisms $1\rightarrow A$ as "elements" of the object $A$
Extensionality holds.

It's reasonable to generalize this notion by replacing the terminal object $1$ by some arbitrary object $K$.

Now it might be useful to see a category where this doesn't hold (i.e. a category that is not well-pointed) just to see where this intuition can fail.

The simplest example I know of is the category of groups and group morphisms $\mathrm{Grp}$. Here the terminal (and initial) object $1$ is the group $\{e\}$ with a single element $e$, which is the unit for that group, and the operation $e*e=e$.

Because group morphisms must send $e$ to $e_G$ (the unit of $G$), there is always exactly 1 morphism $1\rightarrow G$ for any group $G$, namely, $\phi(e)=e_G$.

But now take any 2 distinct morphisms $f,g:\mathbb{Z}\rightarrow \mathbb{Z}$, for example $f(n) = n$ and $g(n) = 2\cdot n$.

It's not true that $f = g$ iff $\forall p : 1\rightarrow \mathbb{Z}, f\circ p = g\circ p$. Indeed there is only one $p$, namely $\phi$ from above, and $f\circ \phi(e) = g\circ \phi(e) = e_{\mathbb{Z}} = 0$. But $f \neq g$!

So $\mathrm{Grp}$ is not well-pointed, and it's not useful to treat morphisms $1\rightarrow G$ as points of $G$. However, in this case, there happens to be a generating object $K\neq 1$, so the generalization is useful after all! I'll leave it as an exercise to figure out what $K$ is...

I'll try to answer the questions more directly.

  A morphism can be thought of as a a mapping from one type to another?

Sort of. It's a good intuition, but you shouldn't think that it always makes sense to talk about elements of type $A$, unless you're working in a well-pointed category as explained above..

  Morphism f is equivalent to morphism g if and only if for the morphism type K to type A

It's equal rather than equivalent (though computer scientists tend to define equality in a much stricter sense than category theorists, e.g. by syntactic equality).

Also, it's "if and only if for every morphism from K to A", in general you can have many morphisms in K -> A

  e applied to f is equivalent to e applied to g

Composition (written $\circ$) is not application! I've tried to break it down above.

  The number of steps in this definition blows my mind, can anyone help me visualize the entire definition?

Category theory often offers very abstract definitions, and it's useful to work through examples and basic lemmas yourself to gain intuition.

However, if this helps, in the $\mathrm{Hask}$ category with types as objects and total programs of type A -> B as morphisms between A and B, the unit type () is a generator, as I tried to explain above.


Fibonacci Heap / Binomial Heap - Decrease Key I've been implementing a Fibonacci Heap in C this past week and today I just hit a mental roadblock that I can't figure out.

Decrease Key is a function that almost all min heaps have (vice versa with increase key with max heaps). However all of the decrease key functions declarations look like this:

// Big Theta 1 performance.
void decrease_key(Node n);

That's great, but what about Node find_node(Object data);?

Before you can decrease the key of the node, you have to locate it first. So the call of

decrease_key(52,17) first needs to search for 52, then update it to 17, and then restructure the tree (unless structure is lazy, such as fib tree). Doesn't that absolutely murder the complexity of that call? Locating an element in the tree cannot be fast. You'd approach n very quickly, only skipping Node roots that are greater than the element you are looking for (since their children are even larger).

None of the documents online which feature Fibonacci heaps or binomial heaps talk AT ALL about locating a node inside the tree. I assume that I just loop over each node, and perform the following logic?

for every node n in the list
   int c = compare(n, data)
   if (c > 0)
      call logic recursively on his child
   if (c == 0)
      decrease_key(n, data)
   otherwise
      error cannot compare greater

Furthermore, why is there a decrease_key but not a increase_key, or frankly a set? I suppose increase_key is a much harder problem to solve?

Thanks

The call takes a specific node because that's what you typically want to do. Since you're given a pointer to the node you're supposed to be changing, you don't need to find it.

Your heap is storing a set of objects ordered by priority, and you're much more likely to want to adjust the priority of a specific object ("Crap, my algorithms homework is due tomorrow – I thought it wasn't until Thursday!") than you are to want to adjust the priority of whatever object has some given priority. In any case, there might be multiple objects with the same priority. Would your version of decrease_key adjust the priority of all of them?

I'm not familiar with Fibonacci heaps but certainly with ordinary heaps, an operation of "adjust the priority of the items that have priority $k$" would, in the worst case, involve a linear search through the whole heap. The ordering of the heap items isn't strong enough to let you do better than that: for example, the largest item in the heap could be at any leaf.

In ordinary heaps, increase_key and set_key aren't a problem: just adjust the key value and then filter up or down as appropriate.


Given a chordal graph $G$, what is the complexity of computing the reduced clique graph $C_r(G)$? A graph $G$ is chordal if it doesn't have induced cycles of length $4$ or more. A clique tree $T$ of $G$ is a tree in which the vertices of the tree are the maximal cliques of $G$. An edge in $T$ corresponds to a minimal separator. The number of distinct clique trees can be exponential in the number of vertices in a chordal graph.

The reduced clique graph $C_r(G)$ is the union of all clique trees of $G$. That is, it has all the same vertices, and all possible edges. What is the complexity of computing $C_r(G)$ for a given $G$?

I think I once saw a presentation claiming $C_r(G)$ can be computed in $O(m+n)$ time without proof. This would mean it is as easy as computing a clique tree of $G$. Is there a reference that confirms this, or gives a slower algorithm for computing it?

The complexity is O(nm)... from G compute the maximal cliques and make them vertices in your graph H (initially with no edges)... then compute all minimal separators and order them by size... pick the largest separator S and make any two cliques C,C' adjacent in H (connect them by an edge with label S) if C,C' both contain S and are in different connected components of H (initially this is of course always true, but may not be later)... then pick next largest separator and do the same... repeat until all separators are processed... the resulting graph H is the reduced clique graph of G... computing maximal cliques and minimal separators takes O(n+m)... there are O(n) cliques and O(n) separators... the rest of the construction is O(nm) as processing each separator can take O(m) time...
... this cannot be improved below O(n^2) unless you can solve the following problem: given a graph G find two vertices u,v such that N(u) contains N(v)... the latter is not known to have O(n+m) solution...
... it is therefore unlikely that a O(n+m) algorithm for computing reduced clique graphs is possible...

see Section 5 in M. Habib, J. Stacho: Polynomial-time algorithm for the leafage of chordal graphs, In: Algorithms - ESA 2009, Lecture Notes in Computer Science 5757/2009, pp. 290-300. (http://www.cs.toronto.edu/~stacho/public/leafage-esa1.pdf)


DFA for exactly two of a and one or more of b I'm totally new to DFA's and automaton in general -- this is the first week or two of class that I've actually seen this -- and I'm curious as to a pattern to match the following:

"Match the set of all strings on the alphabet {a, b} that have at least one b and exactly 2 a's"

I've tried to construct a DFA to represent this structure, but I have no idea how to form a structure to count for something and match for one.

Can someone help?

Okay, so. Here's what I got and I think it's the right answer.

Since it's for class, I won't actually build the DFA for you, but I will give you a way to look at it that'll help.

As far as $b$s go, you really only care about whether or not you've seen a $b$ so far in the string.
As for $a$s, you care about whether you've seen 0, 1, 2, or more.

Each combination of scenarios for both letters (like "seen none of either" or "seen one of each" or "seen one $a$ and no $b$s") changes in its own way depending on whether you read another $a$ or $b$. How might you express that in a DFA?


Is this language Recursively Enumerable or Not RE? $L = \{\langle M, k\rangle  : M\;\text{is a Turing Machine and } |\{w \in L(M) :  w \in a^*b^*\}|
 \geq k \}$

My Interpretation of language is that $L$ is a language which contains Turing machine whose language contains string greater than equal to $k$ and also strings belong to $a^* b ^*$.

My Analysis : Using Rice's Theorem,

$T_{yes} = L$ and $T_{no} = a^*b^*$

By rice's first theorem we can say that this language is Undecidable and by using rice's second theorem we can say this it is not even recognizable because $T_{yes} \subset T_{no}$.

My intuitive approach : As we know language $L$ is a set of TM which accept a set of strings length greater than or equal to k and are a subset of $a^* b^*$ then for language $L$ to be Recursively Enumerable there must be yes cases for turing machines which are fulfilling the requirement and for no cases it might halt and reject or might stay in loop but the issue here is there might exist a string in $a^*b^*$ which might get accepted later and there are infinite such strings so turing machine can never give yes cases. Yes cases can only happen if TM checks all strings of ab and rejects which are not a part of language but this will not happen as there are infinite strings.

This is not a proof but just my intuition.

Hence by using Rice's theorem we got to know that $L$ is not even Recursively Enumerable but I've been told that my interpretation of language itself is wrong and $L$ is Recursively Enumerable.

$L = \{\text{<M, k>| M is a Turing Machine and } |w \in L(M) :  w \in a^*b^*|
 \geq k \}$

Now we want to find whether $L$ is $RE$ or not.

Yes, indeed your interpretation of language $L$ is wrong.

$L$ is a language of strings of form $\langle M, k \rangle$ where $M$ is turing machine which accepts atleast $k$ strings of form $a^*b^*$.

So, now it's easy to see that $L$ is indeed $RE$. For that we can run $M$ on all strings of form $a^*b^*$ by using dove tailing approach. If $\langle M, k \rangle \in L$ then eventually $M$ will accept $k$ strings of form $a^*b^*$. And at that point we will accept $\langle M, k \rangle$.

So as per your question answer is that $L$ is $RE$.


Cube 3x3: Using just face rotations, transform the cube from configuration A to B I'm looking for some tips on how to best implement the algorithm to accomplish the following:

Imagine a 3×3 cube with a rubik's cube mechanism, i.e. you can freely rotate any of the 6 faces.
You don't care about colors.
Instead you index the component 26 cubes A–Z and ignore the middle.

Illustration image (component cubes): https://paste.pics/AOYUS
Now, I would like to generate a list of face rotations that would get me from this configuration to some other configuration. E. g. this: https://paste.pics/AOYWM
Note: I don't care which component cubes end up in positions labeled as *
Ideally the algorithm produces the shortest list of transformations necessary, but it's not a firm condition. Any suggestions welcome, thanks!

If the number of "don't care" colours is large, as it is in this example, you probably can't do much better than A* search.
One simple heuristic function is the minimum number of moves required to move the currently-least-correct piece to its correct position. Since you're willing to tolerate some non-optimality, summing over all pieces that are not in their correct locations will probably do quite well in practice.


Could an NP-Hard problem be in P in after a basis transform? I'm aware that there must be something wrong with my reasoning, but I'm not sure what and neither are a few other CS people I've asked.

So here goes:

Take the following problem for example:

Let $x[n]$ be a real valued discrete signal of length $N$.

It is known that the signal is of the form $$x[n] = sin(an) + sin(bn) + sin(cn)$$ where $a,b,c$ are some real valued constants.

We want to find $a,b,c$ , the 3 frequencies composing $x[n]$.

Now lets assume a parallel universe which somehow doesn't know of the Fourier transform. The only way they could propose to solve the problem (that I can think of) would be some form of grid search over $a,b,c$ which would seem to be exponentially hard.

Given the Fourier transform, one could solve the problem in poly-time.

So my question is: could some problems we think are NP-hard just seem that way because we haven't yet found the "magic" transform to change them into a basis which bring the problem to be solvable in poly-time?

I know that I haven't given the full formal formulation of the problem, and probably the catch is that even without Fourier the problem isn't NP hard.. but I'm still curious about how to refute the claim that there could exist a basis transform which would make an NP-hard problem solvable in poly time.

The only way they could propose to solve the problem (that I can think of) ... would seem to be exponentially hard."

That's your core fallacy, and "that I can think of" is the answer. The complexity of the problem did not change, but the transformation made finding an efficient algorithm easier (as a tool).

Yes, it's certainly possible that we have yet to find a similar tool that, once we have it, allows even our feeble minds to easily find efficient algorithms for NP-hard problems. That would be a constructive and generalisable proof for P=NP, that is something like a holy grail.


Solve modulus with constraints for multiple equations I'm trying write a program to solve equations from the following form:

$$ \begin{align}
a \bmod x &= t_1 \\
b \bmod x &= t_2 \\
\end{align} $$

where $a$, $b$, $t_1$ and $t_2$ are known values.

I have multiple equations of the same form and I'd like to solve them for $x$.
Assuming I have constraints on $t_1$ and on $t_2$ for some constant $C$:

$$ \begin{align}
0 \le t_1 \lt C \\
0 \le t_2 \lt C \\
\end{align} $$

e.g :
for $a=150$, $b=50$, $t1=2$, $t_2=1$:
$$ \begin{align}
150 \bmod x &= 2 \\
50 \bmod x &= 1 \\
1, 2 \lt 5 \\
\end{align} $$

What would be the most efficient way to program such a thing?

Expand the equivalences $150 \equiv 2 \pmod{x}$, $50 \equiv 1 \pmod{x}$ into $150 = 2 + k_1 x$, $50 = 1 + k_2 x$ for some integers $k_1, k_2$ and deduce that $148 = k_1 x, 49 = k_2 x$. There is no
integer solution since $\gcd(148, 49) = 1$. But (for example; another system) if you replace $150$ with say $65$, then you have $\gcd(49, 63) = 7$. Since $x$ must be $> t_1, t_2$ (or your given upper bound on $t_1, t_2$), we can set $x = 7$ (or other factors of the gcd which satisfy the aforementioned conditions). You can probably turn this into an algorithm. The dominant cost is gcd computation.