Can interval partition solve by sort by different approach The interval partitioning problem is described as follows: Given a set
  {1, 2, …, n} of n requests, where ith request starts at time s(i) and
  finishes at time f(i), find the minimum number of resources needed to
  schedule all requests so that no two requests are assigned to the same
  resource at the same time.

I read from many sources, that the solution often is:

- sort again by earliest time of requests.
- For each requests in sorted request:
     if can choose one resource that can do this requests:
        assign that request to resource
     else
        create new resource
        count++
        assign that request to new resource

The result will be count after finishing algorithm.

However, I approach with different idea. The following is algorithm of my idea:

- Break all time range into 2 parts: (time=start_time, type=start) and (time=end_time, type=end)
- Sort all that events. If time equals, prefer type=end.
- Go from that sorted events, if type = start: count++. else count --

count will be the total machine we need.

My question is: is there any wrong with my approach.

Thanks

Yes, your approach is correct.

"The interval partitioning problem" is more commonly known as "the interval-graph coloring problem". It is problem 16.1-4 in the book Introduction to Algorithm by CLRS, third edition.

The idea behind the common solution described in the question and your approach is essentially the same. Arguably, your algorithm is simpler than that solution given by many sources. On the other hand, there are many sources that give the roughly the same algorithm as yours such as the article at GeeksForGeeks.

There is one distinction of your algorithm, If time equals, prefer type=end. It turns out this specification is unnecessarily restrictive in the sense that you can break any tie that consists of requests of the same starting time arbitrarily. On first look, it might sound surprising that the algorithm still works when ties are breaking arbitrarily. One might take for granted that scheduling the one request that ends early should yield more room for later scheduling. However, it does not matter which one to schedule out of the requests of the same staring time. I will leave this little enigma as an exercise for readers to ponder and prove.

By the way, there are some sloppiness in the question and the algorithm. In the problem statement, it does not mention explicitly that each request must use one and only one resource all the way from its start time to its end time. That each request can use any resource. It does not specify whether a request that starts at time $t_0$ can use the same resource used by another request that ends at $t_0$, that is, whether those two requests are overlapping at $t_0$. The "total machine" is used suddenly near the end of the question, which should be, for the sake of consistency, "total number of resources". This short answer is written in the hope that
all those ambiguities and sloppiness do not affect the high-level thinking by readers.


Determining width of paths I have an image, like the one below that has different paths. I want to be able to detect the thin parts of these paths and highlight them. What is the best way to go about this?

Just an idea that might work. Let original image be $I_0$. Erode just enough to remove the thin lines, then dilate back to obtain $I_1$. Afterwards, obtain the difference of the $I_0$ and $I_1$.


How is $L^* - \{\epsilon \} \neq L^+$? I was asked which among the following is true:

  $\Sigma^*-\{\epsilon\} = \Sigma^+$
  $L^* - \{\epsilon \} = L^+$

As I can see, both $\Sigma^*$ & $L^*$ are sets. I thought both were true because of set difference, but the answer lists only the first option as correct and the second as false. How so?

If $\varepsilon \in L$, then necessarily $\varepsilon \in L^+$ (and the converse as well). This is because $L$ itself is contained in $L^+$ and $L^+$ is defined as the union over the powers $L^i$ of $L$ for $i \in \mathbb{N}_+$. Note $L^+$ is not defined as $L^\ast \setminus \{ \varepsilon \}$; this is a common mistake.

Hence, $\varepsilon \not\in L^+$ holds if and only if $\varepsilon \not\in L$. This is the case for the alphabet $\Sigma$, hence why it is correct in the first case.


What is the state of the art for k nearest neighbour search? I'm not an computer scientist, but still use/have an algorithm to find the $k$ nearest neighbours from a cloud of $N$ points in $d$ (my case $d=3$) dimensional space using some distance measure (in my case Euclidean). I had some look at the literature and it appears that the standard is J. H. Friedman, J. L. Bentley, and R. A. Finkel. An algorithm for finding best matches in logarithmic expected time. ACM Trans. Math. Softw., 3:209–226, 1977, which is a root-first tree traversal on a kd tree. This algorithm has complexity $O(dk\log N)$ for each search (after the tree has been built at cost $O(dN\log N)$). I wonder whether this is still the state of the art.

The reason I'm asking is that my own algorithm is different (also using a tree) and has (I believe) average costs of $O(dk)$ per search (but still worst case $O(dk\log N)$), provided the query point is a member of the cloud. So I was wondering whether it's perhaps worth publishing.

It seems hard to imagine that your claimed running time is correct, for a method that works in an arbitrary number of dimensions.  It sounds like you are claiming that your data structures works in an arbitrary number of dimensions ($n$), but the running time does not depend on the dimension ($n$). That seems unlikely; nearest neighbor search is known to be hard to solve in high dimensions (the so-called curse of dimensionality).

Alternatively, if you meant that your scheme works only in 3 dimensions, then that is an important caveat that needs to be mentioned.  Being able to find the nearest neighbor in 3D in $O(1)$ time would be an impressive result; I'm not aware of any data structure that is known to have this worst-case running time.

Yes, a k-d tree is a standard data structure for this task, when you are working in 3 dimensions.  There are also generalizations and related data structures; see metric trees, binary space partitioning trees and octrees.  R-trees and R*-trees can be used if the set of points are changing.

Without knowing how your algorithms works, it's hard to give a definitive answer whether it is worth publishing.  To figure out, a good starting point would be to familiarize yourself with the published and known algorithms and see if your idea still seems to be better than all known schemes.  If you're still not sure, make ask a new question here with the specifics of your algorithm and what your specific uncertainty is.


Finding a mapping reduction from $A_{TM}$ to $\overline{CF_{TM}}$ I am trying to find a mapping reduction from $A_{TM}$ to $\overline{CF_{TM}}$, but I can't seem to find one.

Definitions:
$$\begin{align*}
CF_{TM} &= \left\{ \langle M \rangle \mid \text{$M$ is a TM and $L(M)$ is context-free} \right\} \\
A_{TM} &= \left\{ \langle M,w \rangle \mid \text{$M$ is a TM and $w \in L(M)$} \right\}
\end{align*}$$

AFAIK the mapping reduction of the regular (i.e., not the complimentary) language is as follows: $\langle M,w \rangle \in A_{TM}$ if and only if we can construct a language $L$ which is context-free in the sense that $L(F((\langle M,w \rangle)))$ is context-free.

Let $L$ be recursively enumerable but not context-free (and, therefore, not empty). We only need the existence of such an $L$; the actual choice is immaterial. In addition, recall the empty set $\varnothing$ is context-free. The idea is to map to a TM which accepts $L$ in case $M$ accepts $w$ (i.e., $\langle M,w \rangle \in A_{TM}$) and to $\varnothing$ otherwise.

Given an instance $\langle M,w \rangle$ of $A_{TM}$, map it to the description $\langle S \rangle$, where $S$ is the TM which does the following:

  On input $w'$:

  Run $M$ on $w$. If $M$ rejects, reject.
  If $M$ accepts $w$, then accept if and only if $w' \in L$.

Note that, if $M$ does not halt on $w$, then $S$ does not halt either. Also, $w' \in L$ can be checked because $L$ is recursively enumerable (and $S$ need not halt in case that is false). We conclude that $L(S) = L$ if $\langle M, w \rangle \in A_{TM}$ and $L(S) = \varnothing$ (which is context-free) otherwise.

An observation. The trick behind 98% of these problems lies in understanding what you need to do (i.e., what I wrote in the first paragraph). The actual description for the instance you are reducing to (in this case, $\langle S \rangle$) might look tricky or esoteric at first sight, but it actually simply follows as a consequence once you have the right ideas in mind.


T&PL: Language grammar with terms I'm autodidacting Pierce's Types and Programming Languages. On page 27 he states a definition for "terms, concretely" in constructing a language of terms, thus:

For each natural number $i$, define a set $S_i$ as follows:

\begin{align}
S_0 & = \emptyset \\
 S_{i+1} & = \;\;\;\{true, false, 0\} \\
& \;\;\;\cup \; \{succ \: t_1, pred \: t_1, iszero \: t_1\ |\: t_1 \in S_i\} \\
&  \;\;\;\cup \; \{if\: t_1 \:then \: t_2 \:else \: t_3\: |\; t_1, t_2, t_3 \in S_i\} \\
\end{align}

where $succ\: t$ is the successor of $t$, $pred \:t$ is the predecessor of $t$ and $iszero \:t$ tests if $t = 0$. Finally, let

$$S = \bigcup_i{S_i}$$

where $S_0$ is empty; $S_1$ contains just the constants (I assume $true, false, 0$ is meant); $S_2$ contains the constants plus the phrases that can be built with constants and just one $succ, pred, iszero$ or $if$; $S_3$ contains these and all phrases that can be built using $succ, pred, iszero$ and $if$ in $S_2$; and so on. $S$ collects together all the phrases that can be built in this way, i.e., all the phrases built by some finite number of arithmetic and conditional operators, beginning with just constants.

Then as an exercise: How many elements does $S_3$ have? And the answer is (from back of book): $|S_{i+1}| = {|S_i|}^3 + |S_i| \,\times\,3+3$, and $|S_0| = 0$. So $|S_3| = 59439.$

I really get lost when he says what $S_1$ and $S_2$ are. Anyone who could get me started on what is going on here, or could point me to another treatment of these ideas would be appreciated.

$S_0$ is the empty set.

Let $i=0$.
$$\begin{align}
 S_1= S_{0+1} & = \;\;\;\{true, false, 0\} \\
& \;\;\;\cup \; \{succ \: t_1, pred \: t_1, iszero \: t_1\ |\: t_1 \in S_0\} \\
&  \;\;\;\cup \; \{if\: t_1 \:then \: t_2 \:else \: t_3\: |\; t_1, t_2, t_3 \in S_0\} \\
& = \;\;\;\{true, false, 0\} \\
& \;\;\;\cup \; \emptyset \\
& \;\;\;\cup \; \emptyset \\
& = \;\;\;\{true, false, 0\} \\
\end{align}$$

So $S_1$ contains 3 elements.

Let $i=1$.
$$\begin{align}
 S_2= S_{1+1} & = \;\;\;\{true, false, 0\} \\
& \;\;\;\cup \; \{succ \: t_1, pred \: t_1, iszero \: t_1\ |\: t_1 \in S_1\} \\
&  \;\;\;\cup \; \{if\: t_1 \:then \: t_2 \:else \: t_3\: |\; t_1, t_2, t_3 \in S_1\} \\
& = \;\;\;\{true, false, 0\} \\
& \;\;\;\cup \; \{succ \: true, pred \: true, iszero \: true, \\
&\quad\quad\;\;succ \: false, pred \: false, iszero \: false, \\
&\quad\quad\;\;succ \: 0, pred \: 0, iszero \: 0\} \\
&  \;\;\;\cup \; \{if\: true \:then \: true \:else \: true,\\
&\quad\quad\;\;if\: true \:then \: true \:else \: false,\\
&\quad\quad\;\;if\: true \:then \: true \:else \: 0,\\
&\quad\quad\;\;if\: true \:then \: false \:else \: true,\\
&\quad\quad\;\;if\: true \:then \: false \:else \: false,\\
&\quad\quad\;\;if\: true \:then \: false \:else \: 0,\\
&\quad\quad\;\;if\: true \:then \: 0 \:else \: true,\\
&\quad\quad\;\;if\: true \:then \: 0 \:else \: false,\\
&\quad\quad\;\;if\: true \:then \: 0 \:else \: 0,\\
&\quad\quad\;\;if\: false \:then \: true \:else \: true,\\
&\quad\quad\;\;if\: false \:then \: true \:else \: false,\\
&\quad\quad\;\;if\: false \:then \: true \:else \: 0,\\
&\quad\quad\;\;if\: false \:then \: false \:else \: true,\\
&\quad\quad\;\;if\: false \:then \: false \:else \: false,\\
&\quad\quad\;\;if\: false \:then \: false \:else \: 0,\\
&\quad\quad\;\;if\: false \:then \: 0 \:else \: true,\\
&\quad\quad\;\;if\: false \:then \: 0 \:else \: false,\\
&\quad\quad\;\;if\: false \:then \: 0 \:else \: 0,\\
&\quad\quad\;\;if\: 0 \:then \: true \:else \: true,\\
&\quad\quad\;\;if\: 0 \:then \: true \:else \: false,\\
&\quad\quad\;\;if\: 0 \:then \: true \:else \: 0,\\
&\quad\quad\;\;if\: 0 \:then \: false \:else \: true,\\
&\quad\quad\;\;if\: 0 \:then \: false \:else \: false,\\
&\quad\quad\;\;if\: 0 \:then \: false \:else \: 0,\\
&\quad\quad\;\;if\: 0 \:then \: 0 \:else \: true,\\
&\quad\quad\;\;if\: 0 \:then \: 0 \:else \: false,\\
&\quad\quad\;\;if\: 0 \:then \: 0 \:else \: 0\}
\end{align}$$

So $S_2$ contains 3+9+27= 39 elements.

Let $i= 2$, we will get $S_3=S_{2+1}=\cdots$, which contains 3+39*3+39^3=59439 elements.

You are supposed to get lost in case you want to find the meaning or the semantics of the elements in $S_1$ and $S_2$, because there is no meaning attached to those elements yet at this stage of the book. In other words, although you, I suspect, have understood all that are supposed to be understood, you do not feel or know that you have. Be relaxed, this introductory book is not supposed to be difficult here.

At this stage of the book, $S_0, S_1, S_2, \cdots$ are just sets of words over the alphabet $\Sigma=\{ true, false, 0, succ, pred, iszero, if, then, else \}$. In fact, 3.2.1 Definition [Terms, inductively] defines the language $\mathcal T$ by the following context-free grammar.

$S\to true \mid false \mid 0$
$S\to succ\ S \mid pred\ S \mid iszero\ S$
$S\to if\ S\ then\ S\ else\ S $

Once again, let me emphasize that there is no meaning to each symbol in the alphabet $\Sigma$. For example, $true$ is just one symbol, which happens to look like "true". It should have worked equally well had we used $asdf$ or $easypeasy$ or $humptydumpty$ instead. It is expected that we will assign meaning or semantics to all symbols in $\Sigma$ and many words in $\mathcal T$; however, that has not been done yet at this stage of the book.

To compute $|S_3|$, we need to prove the formula,
$|S_{i+1}| = {|S_i|}^3 + |S_i| \times3+3$, which comes from the following equality, where $\sqcup$ means disjoint union.

\begin{align}
 S_{i+1} & = \;\;\;\{true,\, false,\, 0\} \\
& \;\;\; \sqcup \, \{succ \: t_1\mid t_1 \in S_i\}
         \,\sqcup\, \{pred \: t_1\mid t_1 \in S_i\} \;
         \sqcup \; \{iszero \: t_1\mid t_1 \in S_i\} \\
&  \;\;\;\sqcup \, \{if\: t_1 \:then \: t_2 \:else \: t_3\: |\; t_1, t_2, t_3 \in S_i\} \\
\end{align}

Note that it might not be trivial to show the cardinality of the last set $\{if\: t_1 \:then \: t_2 \:else \: t_3\: |\; t_1, t_2, t_3 \in S_i\}$ is $|S_i|^3$ for $i\ge2$ in general since we need to show more or less that the grammar above is deterministic. However, the cases of $i=0,1,2$ that are needed for the moment can be easily enumerated.


Why SAT Requires A Non-determinstic Algorithm? I am getting started to understand the probelm of Satisfiability and i am reading (Computers and Intractability: A Guide to the Theory of NP-Completeness).

I do understand the difference between a Deterministic and Non-Deterministic Algorithm, however i don't understand why SAT requires a Non-Determinsitic Algorithm ? Why not a Deterministic Algorithm ?

How do we know for sure that a problem requires a Deterministic or Non-Deterministic Algorith that solves it ? (if it was solvable, i,e. not undecidable problem).

It is not true that it requires a non-deterministic algorithm.

You are right; if it is solvable, it should be solvable by a deterministic algorithm. And it is. This deterministic algorithm needs exponential number of steps (with respect to number of propositional variables $n$) because only known general case approach so far is to test all combinations of truth values of propositional variables, and we have $2^n$ possible combinations (rows of a truth table).

However, we can (theoretically) solve it with a non-deterministic algorithm in polynomial time which is how a class of NP problems is defined. This is where your confusion, and maybe a bad choice of words in the literature, probably comes from.

All non-deterministic algorithms can be simulated by a deterministic algorithm. In fact, all that is computable can be computed with a deterministic algorithm. It is just the time complexity that varies.


Decidability of Turing Machines with input of fixed length I'm learning about undecidability, and found this question:

Is this language decidable, make a proof:
    L = { M : machine M halts for every input of length not exceeding 100 }

Update: This is translated from an exam paper some years ago, and I'm quite sure it means that machine M should halt for every input with length from 0 to 100, and that it is no constraints on the tape size.

Update2: The solution given below, and hence the origin of this post, is for an variant of this question with fixed number of steps and input. Sorry for the confusion.

I came to the conclusion that this is an undecidable language.

My logic is as follows: Lets say for the sake of contradiction that it is possible to construct a machine $M_R$, that takes as input an arbitrary input $(M,x)$, and reduces this to $M'$. $M'$ has the property so that $(M,x) \in M_{HALT}$ iff $M' \in L$, this means that $M$ halts on all $x$ of input with maximum length of 100.

Then run $M$ on $x$, if it halts then accept.

And shows that $M_R$ decides the halting problem, and in hence a contradiction and proves that his is not decidable.

But in the solution it is written that this question is decidable:

  You can simulate $M$ on all inputs of length 100 or less (you can
  generate such input in a loop and use the universal Turing machine to
  simulate M on x), it is only $|\Sigma|^{100}$ possible inputs of
  length 100, that is finite.

@jmite correctly points out that the statement is written in such a way that the language is obviously undecidable. Even with 0 cells of input, as long as the machine is able to use an unbounded amount of work tape, the language will be undecidable. This is a completely basic fact about the Halting set.

@Michael should check to see whether the problem states that the machine only has 100 cells of input, or of total tape to work with. Did you transcribe the problem correctly?

Given the suggested official answer (which is not very good, may I know where this problem came from?), I think the problem meant to say that the total amount of tape available is 100 cells. In which case, the answer is as follows.

The language is decidable. Let us suppose the tape alphabet consists of three symbols, $0$, $1$ and blank.

Given a Turing machine $M$ with $n$ states, there are at most
$$n \times 3^{100} \times 100$$
configurations of the machine, the head and the tape: the machine can be in any one of $n$ states, each of the 100 cell tapes may contain one of three symbols, and the head may be in 100 different positions. To determine whether $M$ halts, we simulate step by step for at most $n \times 3^{100} \times 100 + 1$ steps. If the simulation halts, then $M$ halts, otherwise $M$ will have repeated the same configuration twice and therefore loop forever. We may even detect the repeated configuration if we wish.

Let me address the other two answers:

@jmite: you missed the fact that we may halt the simulation after a finite number of steps because there are only finitely many possible configurations of the machine, the tape and the state.
@Patrick87: it is true that the number 100 can be replaced with any other number. So, for any machine $M$ and any number $n$ we can decided whether $M$ will halt on a tape of length $n$. This however does not allow us to deduce anything about $M$ halting on an infinite tape because $M$ could run forever by using up unbounded amounts of tape. There will be no $n$ such that $M$ uses only $n$ cells, so knowing what it does on $n$ cells won't be helpful.


Vertex cover algorithms for directed graphs? I've recently been working on a problem that I believe can be expressed as a vertex cover problem over a directed graph.

Formally, I have a graph $G = (V,E)$ where $V$ is a vertex set and $E$ is a set of edges between vertices. The edges are directed so we can have $e_{ij} = 1$ but $e_{ji} = 0$ where $i,j \in V$. Here, $e_{ji} = 0$ would mean that there is no edge from $j$ to $i$.

My problem is as follows. I would like to find the smallest subset of vertices $S \subseteq V$ such that there is a path from every vertex in S to every vertex to V. That is, for every vertex $j \in V$, there is an $i \in S$ such that either:

$e_{i,j} > 0$ (edge between $i$ and $j$)
$e_{i,{k_1}}e_{{k_1,k_2}}$...$e_{{k_t,j}} > 0$ (path from $i$ to $j$)

I will assume that $e_{ii} = 1$ to ensure that such a subset exists, as I can set $S = V$. However, this is only optimal when the set of nodes is entirely disconnected.

I'm wondering if this a vertex cover problem? If so, are there algorithms for this problem? I'm slightly confused because most vertex cover algorithms are for problems where the graph is undirected (e.g., $e_{ij} = e_{ji}$). If not, are there algorithms to solve this problem?

Thanks for the edit!  This isn't vertex cover; it's something different.

There are simple algorithms for this problem.  Decompose the graph into a dag of strongly connected components.  (The dag is sometimes called "the metagraph".)  Each source vertex in the dag corresponds to a SCC that has no edges coming into it from outside; for each such SCC, pick one vertex and add it to $S$.

The result will be the smallest set $S$ that meets your conditions.  This can be done in $O(V+E)$ time.

Answer to the original version of your question (now irrelevant):

Your problem, as stated, is trivial: the solution is the empty set $S=\emptyset$.

If, on the other hand, you meant that $e_{ij} > 0$ implies $i \in S$, the problem is also trivial: the set $S$ has to include the source vertex of every edge.  So, you just loop over all the edges $(i,j)$ and add $i$ to $S$.


Algorithm: Shortest path (walk) with keys and doors I'm trying to solve the following algorithm question:

  A maze is given by a graph (with let's say $v$ vertices and $e$
  edges), where $k$ vertices are different keys and, $k$ vertices are
  the corresponding doors (there is always one key for a single door)
  and one vertex is the end of the maze. Find the shortest path (it's
  actually a walk because it makes sense to move back after a key is
  found) from a given vertex to the end.

I should note that it is a homework for a class, where only DFS and BFS graph traversing algorithms were used so far, so it should be possible to solve this using only these two algorithms to search the graph.

My approach so far:

I've tried a recursive DFS (to better keep track of the current path and all the keys found on it) with a concept of multiple levels of "found vertices" - when a key is found, the previously found vertices are saved for later use, but at current iterations, it continues as if no vertices were found. When the current recursive call ends, the algorithm moves back a few vertices, when it removes a key it gets back to the previous level of found vertices.

This algorithm should be possible to use but I found it quite hard to figure out the asymptotic time complexity.

Then I realized that it could be simplified. First, do a BFS from the start node (that's $O(v+e)$), get the shortest paths to the keys and to the end and make a new graph of these shortest paths. Then do a BFS again from the first key (some doors could have opened, so it makes sense to search it all over again), get the shortest paths to all other keys and to the end and add these to the graph. Continue for the rest of the keys. At the end do a BFS on the new graph again.

The problem is with the "Continue for the rest of the keys" part, as there are $k!$ ways to collect the keys in different orders, and the new graph would have something like $1+k+k(k-1)+\cdots+k!+k!$ vertices.

Is there any way not to check all the possible permutations? It seems to me, that you can never know, whether there is a possibility of a better path before collecting the keys in a different order.

Update

After submitting the solution, the teacher said, that $k$ was meant as a constant, not the input, so the goal was to minimize the time complexity relative to $v$ and $e$ after all.

This other question about mazes is closely related. It deals with the simpler problem of having to collect each of the items before leaving the maze. One can make the analogy that there is a single door at the end of the maze, but it has a very complicated lock and you must collect all the keys to get through it.

The complexity depends on the structure of the maze. In particular, my answer to the other question proves that, if the maze is a general graph, the collect-all-the-items version of the problem is NP-complete and, in fact, the same holds for planar graphs.  This means that your problem is also NP-complete on general (or planar) graphs.  Here's a sketch of the reduction.  You simulate the door with the complicated lock by replacing the exit to the maze with a very long passage that ends with the $k$ doors one after another. You make the passage long enough that the optimal solution is definitely to collect all the keys first and then walk down that passage and unlock the doors, because walking back and forth between keys and doors would simply be too long. Now the hardness of the collect-all-the-items problem implies that your problem is hard, too.

If your maze is a tree, the problem might be easier – the collect-all-the-items version has a polynomial-time algorithm in that case.  And, in any case, the more general problem being NP-complete doesn't mean there aren't more efficient algorithms than brute force: but it does mean you shouldn't expect a polynomial-time algorithm.


Running time of selection sort I wrote pseudocode for Selection Sort, but I'm not sure what is the running time of my algorithm, can you help me with that?

My Pseudocode: Selection Sort(int a[], int n)

Input: array of length $n$

Output: sorted array

for r=1 to n
    min=a[r]
    for i=r to n
        if (a[i]<min)
              min=a[i]
              k=i
              a[k]=a[r]
              a[r]=min

The external for takes $\Theta (n)$ but I'm not sure about the internal for because it depends on $r$.

The inner loop will iterate $n - r + 1$ times for each iteration of the outer loop. To find the total runtime, we can sum this expression over $r = 1$ to $r = n$:
\begin{align*}
\sum_{r = 1}^{n} (n - r + 1) &= n^2 - \left(\sum_{r = 1}^{n} r\right) + n \\
&= n^2 - \frac{n(n + 1)}{2} + n \\
&= \frac{1}{2}n^2 + \frac{1}{2}n
\end{align*}
which is $\Theta(n^2)$.

To simplify the proof, we can note that the sequence $(n - r + 1)_{r \in [1, n]}$ is just the sequence $1, 2, \ldots, n$, which you can see by substituting $r = 1$ and $r = n$ into $(n - r + 1)$. We know that this sum $\sum_{i = 1}^{n} i$ equals $\frac{n(n + 1)}{2}$, giving the same result as the first method.


Why is the difference of two NP-complete languages not in NP? I found something in my notes I don't really understand, maybe you could help.

Let $A$ = Independent Set and $B$ = Clique. Then, we clearly have

$A \in \mathsf{NPC}$ and
$B \in \mathsf{NP}$.

Now, the claim is that $A \setminus B \notin \mathsf{NP}$ with the following explanation. If it was in $\mathsf{NP}$ then $\mathsf{NP} = \mathsf{NPC}$.

Can you explain why this argument is true?

It's a bit artificial, but if we define

$A = \{(G,k):G \text{ has an independent set of size } k \}$

$B = \{(G,k):G \text{ has a clique of size } k \}$

then $A \setminus B$ is $\mathsf{coNP}$-hard because we can reduce $\overline{B}$ to it: given a graph $G$ and a number $k$ we can form $G'$ by adding $k$ isolated vertices to $G$, then $(G',k) \in A\setminus B$ iff $(G,k) \in \overline{B}$.

I claim that

$A \setminus B \in \mathsf{NP} \Leftrightarrow \mathsf{NP}=\mathsf{coNP}$

$(\Rightarrow)$: If a $\mathsf{coNP}$-hard language is in $\mathsf{NP}$, then $\mathsf{NP}=\mathsf{coNP}$.

$(\Leftarrow)$: If $\mathsf{NP}=\mathsf{coNP}$ then $A \setminus B \in \mathsf{NP}$ follows by closure properties of $\mathsf{NP}$.

Since researchers believe that $\mathsf{NP} \neq \mathsf{coNP}$ (this is a stronger version of $\mathsf{P} \neq \mathsf{NP}$), it makes sense to bet on $A \setminus B \notin \mathsf{NP}$. Currently we have no proof though.


How does a TLB lookup compare all keys simultaneously? I am reading OS Concepts dinosaur book which says, "Each entry in the TLB consists of two parts: a key (or tag) and a value. When the associative memory is presented with an item, the item is compared with all keys simultaneously."

I checked How does a TLB and data cache work? but it does not say anything about the implementation that allows this parallel checking of the keys.

I read something about a parallel hash table here:  http://www.cs.cmu.edu/afs/cs/academic/class/15210-s12/www/lectures/lecture27.pdf

Is this the basic idea?  The insertion of a key outputs a frame number and this could either be a hit or miss?

Computer hardware is fundamentally parallel.  Even a modern single CPU core is pipelined, meaning that at the same instant in time, one physical part of the CPU is initiating a fetch of an instruction, another is decoding a slightly earlier fetched instruction, another is calculating the new result of a slightly earlier decoded instruction, and another is writing back the results of a slightly earlier calculating instruction.

One of the reasons a layer 1 cache in a CPU is so small, and so much more expensive per bit of storage, is that the tag cache portion of the address is broadcast to multiple cache lines, and each of them has some independent hardware logic to compare this tag value against its own tag value in parallel, each independently calculating "that tag matches what I have" or "it doesn't match me".


Difference between the Magnitude and the Phase Spectrum of the Fourier Transform? What is the difference between the Magnitude and the Phase Spectrum of the Fourier
Transform?

Fourier Transform changes basis from time (spatial data) to frequency. To encode frequency we need amplitude (magnitude) to know how strong is signal at given frequency and phase to know when sine started - in what moment of its phase we are now.

Example: take input signal $5\sin(x + \pi)$, here phase is $\pi$ and magnitude is $5$.


Is machine learning a subarea of expert systems? My question is short and straightforward: Can be considered "machine learning" a subarea of "expert systems"?

That depends on your definition of an "expert system". Searching around, many definitions include a clear seperation between 'knowledge base' and 'inference rules', and machine learning most definitely does not always make this distinction.

In fact, unsupervised learning has no knowledge base whatsoever, and finds naturally occurring patterns in just unlabeled data.


Graph partition that maximize the number of triangles within its parts Given a graph $G = (V,E)$, how to partition $V$ into $k$ parts $P_1, P_2, \ldots P_k$ of at most $M$ vertices, such that the number of triangles (3-cliques) contained in the parts is maximal?
This seems NP-complete. Was this problem studied before? (I couldn't find anything after searching clique graph partition). Furthermore, I would appreciate a heuristic approach to solve it.

I don't know whether there are any good heuristics, but I can suggest one approach: you could try to use an ILP solver on this task.  Introduce zero-or-one variables $x_{i,v}$, $y_{i,u,v,w}$, where $x_{i,v}=1$ means that vertex $v$ is contained in partition $P_i$, and $y_{i,u,v,w}=1$ means that $u,v,w$ are a 3-clique in $P_i$.  (Only introduce variables $y_{i,u,v,w}$ for triples of vertices $u,v,w$ that are a 3-clique in the original graph $G$; all others are effectively hardcoded at 0.)  You can add constraints
$$y_{i,u,v,w} \ge x_{i,u} + x_{i,v} + x_{i,w} - 2,$$
$$y_{i,u,v,w} \le x_{i,u}, y_{i,u,v,w} \le x_{i,v}, y_{i,u,v,w} \le x_{i,w},$$
$$\sum_v x_{i,v} \le M, \sum_i x_{i,v}=1.$$
Then, maximize the objective function $\sum_{i,u,v,w} y_{i,u,v,w}$ subject to these constraints, using an off-the-shelf ILP solver.


Why does $L = \{ 0^n 1^n \space | \space n \in \mathbb{N} \}$ belong to $\mathrm{P}$? My professor said that the non-regular language $L_{1} = \{ 0^n 1^n \space | \space n \in \mathbb{N} \}$ belongs to $\mathrm{P}$. I do understand that all regular languages belong to $\mathrm{P}$ as it's easy to determine and so can be computed in $\mathcal{O}(n^k)$, but why do most non-regular languages not belong to $\mathrm{P}$ but $L_{1}$ does? Is it also possible to give an example of a language $L$ that does not belong to $\mathrm{P}$?

You can easily write a polynomial-time algorithm to decide $L_1$ (just count the zeros and check you see the same number of ones), so the language is in $\mathrm{P}$.

Most non-regular languages are not in $\mathrm{P}$ because there are uncountably many languages in total, but only countably many languages in $\mathrm{P}$.

The halting problem is not in $P$. If you want a computable example then, by the time hierarchy theorem, any language that is $\mathrm{EXP}$-complete is not in $\mathrm{P}$.

This answer is intentionally brief because all the things I've mentioned are well-known facts that you should be able to look up, now that you know what to look for. If you need more detail, I suggest asking a new question about that, after checking that we don't already have a question about it.


Is there an algorithm that will fill any shape with points a given distance away from each other? I would like to know if there is an algorithm that if I give a 2D polygon it will give me a set of 2D points. More specifically, those points should have M neighbors that are D apart. The shape is continually filled up with points until no new points can be found without exceeding the bounds of the polygon. The polygon can be given as set of vertices.

I could see an algorithm starting out with a point at the center of the polygon, and then adding a second point exactly the desired distance away. With those two points, another point equidistant to the two previous points could be found by finding the intersection of two circles with the two previous points as their centers and their radii the desired distance.

This gives two points, each of which can be added to a growing list of points. Each point keeps track of what points have been added as neighbor relative to it, and when it has M neighbors, it no longer tries to find any new neighbor. It also does not continue to look for more neighbors if no new neighbors can be found that don't leave the bounds of the polygon.

I am having some mental blocks and if anyone could suggest any leads I would greatly appreciate it. Thank you.

Are you looking for something like this?

Another way is to create equilateral triangle tiling like this, plot your polygon and check which points are inside. Of course it is not needed to actually plot it, just store it in memory.
If your resolution is e.g. one pixel big, you can check all possible starting points shifts from the starting point to find better solution.
To find optimal solution also rotation would be needed, or different approach.
If you decide that not rotated version is sufficient, the ray casting algorithm (also known as scanline test) for testing point inside polygon would be very effective, because all points in a row form line, so in one longer pass you can test whole row.


Thorup : What is the meaning of super distance? While reading Thorup's Algorithm to solve SSSP problem, I have one point that I can't understand: super distance.

It says: "For each vertex we have a super distance $D(v)\geq d(v)$"

$d(v)$ must refer the shortest distance from origin to $v$, but what is $D$ ?

Is it just a distance value from origin while calculation until $D(v)=d(v)$ ?

It says: "For each vertex we have a super distance $D(v)\geq d(v)$"

"Super" refers to the "$\ge$" relation between $D$ and $d$. In other words, since $D(v)\ge d(v)$ where $d(v)$ is the distance from $v$ to $s$, $D(v)$ is called super distance.

  Is it just a distance value from origin while calculation until $D(v)=d(v)$ ?

Correct. It is just a distance that approximates the shortest distance from the source from above, which will become that shortest distance at the time $v$ is moved to $S$, the set of vertices whose distances have been settled.


Is there an O(1) solution to find the kth-smallest element in an implicit min-heap? I know this would be an O(k log n) operation on a traditional heap, and I know there are ways to maintain Kth-smallest over a stream of inserts/deletes for constant-time access...

My question though is, when we have an implicit array representation of a min-heap, e.g.:

min_heap = [1, 2, 4, 3, 6, 5, 54, 12, 12, 34]

In this case, is it possible to infer the Kth-smallest value's index from the value of K, so you can use the array index to get the value in O(1) time?

This is not possible. If this is the case then we could extract a sorted list in linear time; $O(1)$ for each $k$th smallest element. We can also create a min heap in linear time thus we could sort in linear time! We know comparison sorting has an $\Omega(n \log n)$ lower bound worst case, so this is not possible.


3SAT instance with EXACTLY 3 instances of each literal I'm trying to solve a question which requires me to

prove that an instance of 3SAT where each literal appears in exactly 3 clauses (positive and negative appearances combined)  and each clause contains exactly 3 literals is always satisfiable.
Find a polynomial time algorithm to find a satisfying assignment for it.

My Solution

I'm not sure how to prove part 1.
I'm trying to solve 2 by reducing it to an instance of Vertex Cover in which each literal has 2 nodes - one positive, one negative - and each node is connected to the other literals its in a clause with. A vertex cover of size m = # of literals will give us the assignment needed.

Im not sure of I'm along the right path or not? Any help would be appreciated!

It looks like you missed the promising reformulation of this 3SAT. The simple idea is to select a different variable for each clause.
Always satisfiable
Let the variables be $V=\{v_1, v_2, \cdots, v_n\}$ and the clauses be $C=\{c_1,c_2,\cdots, c_m\}$.

Construct a bipartite graph $G=(C,V)$, where $(c,v)$ is an edge if $v$ or $\neg v$ is a literal of $c$. The given conditions mean the degree of each clause and the degree of each variable are 3.
For a subset $W$ of $C$, let $N(W)$ denote the set of all variables adjacent to some clause in $W$. Consider the edges that have one endpoint in $W$. The number of them is exactly $3|W|$ and at most $3|N(W)|$. Hence $|W|\leq |N(W)|.$ By Hall's marriage theorem, for each clause $c$, we can select a distinct variable $m(c)$ such that $(c,m(c))$ is an edge.
For all clause $c$ do the following. If $m(c)$ is a literal of $c$, set $m(c)$ to be true. Otherwise, $\neg m(c)$ is a literal $c$ and we set $m(c)$ to be false. In either case, $c$ becomes true.
Polynomial algorithm
The proof above actually gives the outline of an algorithm. Each step of the algorithm takes polynomial time. In particular, the application of Hall's marriage theorem can be implemented in polynomial time as, for example shown here.
A generalization
Here is a natural generalization.
Exercise. Generalize to the case when each variable appears in at most $r$ clauses and each clause contains at least $r$ distinct variables, where $r\ge1$.


Why Does the Fixed Point Theorem Apply to Quines? A quine is a program that outputs its own source code without taking in any input. An example would be this (taken from here)

public class Quine {
    public static void main(String[] args) {
        char quote = 34;
        String[] code = {
"public class Quine {",
"    public static void main(String[] args) {",
"        char quote = 34;",
"        String[] code = {",
"        };",
"        for(int i=0; i<4; i++){",
"            System.out.println(code[i]);",
"        }",
"        for(int i=0; i<code.length; i++){",
"            System.out.println(quote + code[i] + quote + ',');",
"        }",
"        for(int i=4; i<code.length; i++){",
"            System.out.println(code[i]);",
"        }",
"    }",
"}",
        };
        for(int i=0; i<4; i++){
            System.out.println(code[i]);
        }
        for(int i=0; i<code.length; i++){
            System.out.println(quote + code[i] + quote + ',');
        }
        for(int i=4; i<code.length; i++){
            System.out.println(code[i]);
        }
    }
}

Running this produces exactly the same output as the source code. I've heard that the fixed point theorem applies, meaning that any turing-complete programming language will contain a quine. However, the more I thought about this the less it made sense.

The rules for the fixed point theorem in mathematics are that it must be continuous, bounded surface with no holes or 'cutting and gluing'. This seems to make no sense in terms of programming languages.

The first rule can be broken by the nature of characters as not continuous, for example there is no inbetween 'a' and 'b' in terms of ASCII encoding.

The second rule can be broken by stating that there can be infinitely many programs all equally valid, for example you could have System.out.println("");, System.out.println("a");, System.out.println("aa");...System.out.println("aaaaaaaaaaaaaaaaaaaaa");.

The third rule can be broken by saying that not all programs are valid, for example abstract System out.println(23");" is not valid, however the build output could be used as the output, ie

Main.java:2: error: class, interface, or enum expected
  public static void main(String[] args) {abstract System out.println(23");"
                                                   ^
Main.java:2: error: ')' expected
  public static void main(String[] args) {abstract System out.println(23");"
                                                                        ^
2 errors

If all but one of the rules are broken, then why does the fixed point theorem still apply?

As Discrete Lizard points out, there exist more than one "fixed point theorem." The one you're mentioning makes sense in terms of topology and geometry, but you're right to realize that it does not apply to programming languages.

It turns out, though, that a more general notion of continuity, called Scott Continuity, can give you something that is applicable, namely the Kleene fixed-point theorem:

  Any Scott-continuous function over a directed-complete partial order has a least fixed point.

An earlier, and easier to understand, version of this is given by Knaster-Tarski:

  Any monotone function over a complete lattice has a fixed-point. In fact, the fixed points of such a function form a complete lattice.


How to write a many-one reduction proof Writing a proof by contradiction is fairly formulaic--first you assume the opposite, then derive a contradiction.  I would like to know the steps and conventions for writing a many-one reduction proof.  This answer was somewhat helpful, but like other explanations I've heard, it sounds too similar to a proof by contradiction for me to understand the difference.

My specific points of confusion:

The exact meaning of $A \leq _{m} B$
Do we reduce an unknown problem to a known problem, or the opposite
Does the reduction function transform a known problem into an unknown problem, or the opposite
How a many-one reduction is different from a proof by contradiction.  It seems like a simpler version of the same logic; if so, how is the simplification justified

I am only interested in many-one reductions of language/Turing machine problems (in case the term has meaning in other contexts as well).  Any help is appreciated, including links and illustrative examples.  Thanks.

A many-one reduction is not a "proof-by-contradiction" per se, it is an application of a theorem. The theorem is:

  Let $L,L'\subseteq \{0,1\}^*$, and $L \leq_m L'$. Then, it holds that

  If $L$ is undecidable, then $L'$ is undecidable.
  if $L'$ is decidable, then $L$ is decidable.

I will omit the proof, there are plenty of resources where you can read up on it. You can view the statement $L \leq_m L'$ intuitively as "The language $L$ is easier to decide than the language $L'$". And that's what a reduction proof does. You show that one language (the hard, known one, like the halting problem $H_0$)  is easier to decide than a new, unknown language $L$. By showing $H_0 \leq_m L$ you've essentially shown (by application of the above theorem) that the halting problem is easier than $L$. Thus, $L$ cannot be decided.
So, to answer your questions:

$A \leq_m B$ means that the language $A$ is easier to decide than the language $B$.
To show hardness, you reduce "YOUR_HARD_LANGUAGE $\leq_m$ SOME_NEW_LANGUAGE". To show computability, you can reduce in the other direction, but usually it's simpler to just construct a TM that solves the given problem.
A reduction $L \leq_m L'$ takes an instance $x \in \{ 0,1\}^*$ and does the following with it: If $x \in L$, you make sure that the reduction $f(x) \in L'$. If $x \not \in L$, then the reduction maps $f(x) \not \in L'$. So - if you prove hardness, you transform a known hard problem into the unknown problem.
It is a contradiction in the sense of "If I could solve the new problem, then I can solve the hard problem, which cannot be, since it is proven to be hard". This contradiction is hidden in the Theorem above and you just slap it (implicitly) on every reduction you do.

I hope that helped. As I said, my main intuitive approach to reductions is "How could I use a new language $L'$ to solve an old, hard language $L$?".


Reducing 3 SAT to 3 SET PACKING I'm trying to prove NP-hardness of 3 SET PACKING, which is a following problem: given a family of sets where each set contains 3 elements, decide whether the family contains k sets that are pairwise disjoint.

I tried reducing 3 SAT, but to now avail, but reduction of any other NP-complete problem would be helpful.

Your problem is known as 3-dimensional matching, or 3DM. It is one of the 21 problems proved to be NP-hard in Karp's original paper (number 17 on his list).


How to Implement a reversible OR operator with a Fredkin gate (controlled swap)? How to implement a reversible OR operator with a Fredkin gate ?

As also stated in the relevant Wikipedia page, you can do it by using the first two inputs (the control-bit and one of the target bits) as input for the reversible OR, and the third input bit fixed with the value 1.
Then, the second output is what you want.

To better see this, write the general action of a Fredkin on an input as following:
$$\begin{pmatrix}a\\b\\ c\end{pmatrix}\mapsto
\begin{pmatrix}
a \\
(a c)\oplus[(1\oplus a)b] \\
(a b)\oplus[(1\oplus a)c]
\end{pmatrix}.$$
Note that this is just rewriting the action of the Fredkin algebraically.

Then, if you use as input $(a,b,1)$, you get

$$\begin{pmatrix}a\\b\\ 1\end{pmatrix}\mapsto
\begin{pmatrix}
a \\
a\oplus[(1\oplus a)b] \\
(a b)\oplus(1\oplus a)
\end{pmatrix},$$
which is what you want as soon as you notice that $a \oplus b\oplus ab=a\,\operatorname{OR}\, b$.


Number of clique in random graphs There is a family of random graphs $G(n, p)$ with $n$ nodes (due to Gilbert). Each possible edge is independently inserted into $G(n, p)$ with probability $p$. Let $X_k$ be the number of cliques of size $k$ in $G(n, p)$.

I know that $\mathbb{E}(X_k)=\tbinom{n}{k}\cdot p^{\tbinom{k}{2}}$, but how do I prove it?

How to show that $\mathbb{E}(X_{\log_2n})\ge1$ for $n\to\infty$? And how to show that $\mathbb{E}(X_{c\cdot\log_2n}) \to 0$ for $n\to\infty$ and a fixed, arbitrary constant $c>1$?

So basically there are three questions involved.

I know that $E(X_k)=\tbinom{n}{k}\cdot p^{\tbinom{k}{2}}$, but how do I prove it?

You use the linearity of expectation and some smart re-writing. First of all, note that
$$ X_k = \sum_{T \subseteq V, \, |T|=k} \mathbb{1}[T \text{ is clique}].$$
Now, when taking the expectation of $X_k$, one can simply draw the sum out (due to linearity) and obtain
$$ \mathrm{E}(X_k) = \sum_{T \subseteq V, \, |T|=k} \mathrm{E}(\mathbb{1}[T \text{ is clique}]) = \sum_{T \subseteq V, \, |T|=k} \mathrm{Pr}[T \text{ is clique}]$$
By drawing out the sum, we eliminated all possible dependencies between subsets of nodes. Hence, what is the probability that $T$ is a clique? Well, no matter what $T$ consists of, all edge probabilities are equal. Therefore, $\mathrm{Pr}[T \text{ is clique}] = p^{k \choose 2}$, since all edges in this subgraph must be present. And then, the inner term of the sum does not depend on $T$ anymore, leaving us with $\mathrm{E}(X_k) = p^{k \choose 2} \sum_{T \subseteq V, \, |T|=k} 1 = {n \choose k} \cdot p^{k \choose 2}$.

How to show that for $n\rightarrow\infty$: $E(X_{\log_2n})\ge1$

I am not entirely sure whether this is even correct. Applying a bound on the binomial coefficient, we obtain

$$E(X_{\log n}) = {n \choose \log n} \cdot p^{\log n \choose 2} \leq \left(\frac{n e p^\frac{(\log n)}{4}}{\log n}\right)^{\log n} = \left(\frac{ne \cdot n^{(\log p) / 4}}{\log n}\right)^{\log n}.$$
(Note that I roughly upper bounded $p^\frac{-1 + \log n}{2}$ by $p^\frac{\log n}{4}$.) However, now one could choose $p = 0.001$, and obtain that $\log_2 0.001 \approx -9.96$, which makes the whole term go to $0$ for large $n$. Are you maybe missing some assumptions on $p$?


Is there an efficient algorithm for this vertex cycle cover problem? I've been trying to find an algorithm to find a maximum vertex cycle cover of a directed graph $G$ — that is, a set of disjoint cycles which contain all the vertices in $G$, with as many cycles as possible (we don't consider individual vertices cycles here). I know that the problem of finding a minimum vertex cycle cover, as well as finding a vertex cycle cover with exactly $k$ cycles is NP-complete. But what about the maximum case?

While I'd find an answer to this interesting in general, the graphs I want to use this for are actually quite constrained by their construction, so maybe even if the problem is NP-complete there might be a polynomial solution for these specific instances.

We have a list of integers $L$, elements $l_i$ and we'll use $S$, elements $s_i$ to refer to $L$ after sorting it. As an example:

$$
  L = (1, 3, 2, 5, 0, 7, 4, 2, 6, 0, 8, 1)\\
  S = (0, 0, 1, 1, 2, 2, 3, 4, 5, 6, 7, 8)
$$

The vertices of the graph will be identified with pairs $(n, i)$ such that $l_i = n$ and $s_i \neq n$. The graph has a directed edge $(n, i) \rightarrow (m, j)$ if and only if $s_j = n$. (A cycle in this graph corresponds to a set of values which can be cyclically permuted such that they'll end up in their sorted position.)

The above example would yield the following graph (using 1-based indices):

One thing that doesn't work is the greedy approach of repeatedly removing the smallest cycle (as this example shows).

Note that this problem is (if I didn't make any mistakes) equivalent to asking how many swaps you need to sort a given list. (Which is what inspired looking into this problem in the first place.)

After some pointers from Juho's answer and a bit more sifting through literature, I've come across the assignment problem which seems very closely related. However, the assignment problem is formulated in terms of a weighted bipartite graph and so far I have not been able to find a way to choose edges and weights to reduce this problem to it. If we wanted to formulate the problem here in terms of minimising a weight function, then an intuitive approach would be to say that the weight of each cycle is $|C|-1$ where $|C|$ is the number of edges (or vertices) in the cycle. (Of course this is equivalent to just setting the weight to $-1$.) That is, the weight depends on the size of the cycle, not the particular edges it includes. But maybe this gives someone another idea for how to reduce the problem.

It also appears that bounding the size of the cycles makes the problem APX-hard for general graphs. This doesn't necessarily imply that the same is true for task of maximising the number of cycles, nor for the specific graphs under consideration here, but it seems to be sufficiently closely related that it could be important.

In summary: Can a maximum vertex disjoint cycle cover be found for the graphs constructed from the above process?

As two asides, I'd also be interested in whether the maximum vertex disjoint cycle cover also has an efficient solution for arbitrary graphs that admit at least one cycle cover (which will probably fall out as an answer to the main question), or whether just determining the number of cycles in the maximum cover (as opposed to the actual edges contained in each) makes the problem any simpler. I'm happy to post these as separate questions if people think they deserve full-fledged answers on their own.

Let a cycle cover of a directed graph be a collection of vertex-disjoint cycles such that each vertex is in exactly one cycle. So if I understand you correctly, given a directed graph $G$, you want a maximum cycle cover, where each cycle is of length at least $k$ (perhaps for $k=2$, or $k=3$ at least). A cycle cover where each cycle is of length at least $k$ is called a $k$-cycle cover.

Deciding if a digraph $G$ has a 2-cycle cover is solvable in polynomial time. The problem of deciding whether $G$ has a 3-cycle cover is NP-complete. The corresponding optimization problem (i.e., finding a maximum weight 3-cycle cover) is APX-complete, and has an $((3/5)-\epsilon)$-approximation algorithm (for any $\epsilon > 0$). The good news here is that one can also compute a maximum weight 2-cycle cover in polynomial time (provided edge weights are nonnegative).

For details and proofs of the above claims, see [1].

[1] Bläser, Markus, and Bodo Manthey. "Two approximation algorithms for 3-cycle covers." Approximation Algorithms for Combinatorial Optimization. Springer Berlin Heidelberg, 2002. 40-50.


Testing the property of being a union of three disjoint cliques Design an $\epsilon$-test for the following property in the dense graph model: $G(V,E)$ is a union of three disjoint cliques.

I've been sitting for a few hours and I don't have any idea of how to solve this one ... anyone has any ideas / leads?

I have tried to pick the vertices randomly and then conclude from the graph they make G' what it says about G , I've divided into cases by connectivity : if the connectivity is 4 or more it is easy to conclude that the Graph do not has the property . i have struggled with the math in the other cases...sorry for not posting my progress (I am new)

I will explain how to solve a similar question:

  Design an $\epsilon$-test for the following property in the dense graph model: $G(V,E)$ is a union of two disjoint cliques.

I assume that a clique is also considered a union of two disjoint cliques (one of them empty).

The natural test to try is

  Sample three vertices $x,y,z$, and check that the graph $G[x,y,z]$ induced by $x,y,z$ is either a triangle or an edge.

If a graph is a union of two disjoint cliques, then this test always passes. Conversely, suppose that this test always passes. Fix some vertex $x$, and let $V_1$ be the set of vertices connected to $x$, $V_2$ be the set of vertices not connected to $x$. If $y,z \in V_1$ then $G[x,y,z]$ includes the edges $(x,y),(x,z)$, and so must be a triangle, that is, $(y,z) \in E$. If $y,z \in V_2$ then $G[x,y,z]$ doesn't contain the edges $(x,y),(x,z)$, and so must be the edge $(y,z) \in E$. Finally, if $y \in V_1$ and $z \in V_2$ then $G[x,y,z]$ contains $(x,y)$ but not $(x,z)$. It must be an edge, so that $(y,z) \notin E$. We conclude that $G$ is indeed a union of two disjoint cliques.

Now suppose that the test passes with probability $1-\epsilon$. In particular, there must be a vertex $x_0$ such that conditioned on $x = x_0$, the test passes with probability at least $1-\epsilon$ (why?). Define $V_1,V_2$ as before. The argument above shows that $H$, the union of the cliques on $V_1$ and on $V_2$, is $\epsilon$-close to $G$ (in fact, slightly closer). Indeed, for every pair of vertices $y,z \neq x_0$, the test passes on $x_0,y,z$ if and only if the edge $(y,z)$ exists on both or neither $G$ and $H$. Thus $G$ and $H$ agree on all edges involving $x$, and agree on a $1-\epsilon$ fraction of the rest of the edges.

What about the actual question? Again, the natural test to try is

  Sample four vertices $x,y,z,w$, and check that the graph $G[x,y,z,w]$ induced by $x,y,z,w$ is a union of three disjoint cliques.

This time the analysis is slightly more complicated. Suppose that the test passes with probability $1 - \epsilon$. We consider two cases.

Case 1. $G$ contains at least a $1-\sqrt{\epsilon}$ fraction of all possible edges.

In this case, $G$ is $\sqrt{\epsilon}$-close to a clique.

Case 2. $G$ contains at most a $1-\sqrt{\epsilon}$ fraction of all possible edges.

In this case, we can find two unconnected vertices $x_0,y_0$ such that conditioned on $x=x_0,y=y_0$, the test passes with probability at least $1-\sqrt{\epsilon}$. We can now define $V_1,V_2,V_3$ analogously to how we defined $V_1,V_2$ in the preceding case, and show that $G$ is $\sqrt{\epsilon}$-close to the union of the cliques on $V_1,V_2,V_3$. Details left to the reader.


Question about threads and locks I am currently reading Fuss, Futexes and Furwocks: Fast Userland Locking in Linux and came across this quote:

  In a fair locking scheme the lock is granted in the order it was
  requested. This can have negative impact on throughput due to the
  increased number of context switches. At the same time it can lead to
  the so called convoy problem. Since the locks are granted in the order
  of arrival, they all proceed at the speed of the slowest process,
  slowing down all waiting processes. A common solution to the convoy
  problem has been to mark the lock available upon release, wake all
  waiting processes and have them recontend for the lock. This is
  referred to as random fairness. However, this also leads to the
  thundering herd problem. Despite this, it can work well on
  uni-processor systems if the first task to wake releases the lock
  before being preempted or scheduled, allowing the second herd member
  to obtain the lock, etc...

I have a few questions about this quote.

First, does a fair locking scheme result in an increased number of context switches because different tasks put processes into the wait queue at different times and thus by serving processes in the order they were received, we'd be context switching between multiple tasks?

Second, how does granting locks in the order of arrival cause processes to proceed at the speed of the slowest process? Wouldn't this only be the case if the slowest process is granted the lock before the other processes? Similarly, how does having processes contending randomly for the lock solve the convoy problem?

Finally, I don't understand how random fairness is any better on uni-processor systems in comparison to multiprocessor systems. For example, in both cases, all of the waiting processors are woken up, one gets the lock, and the others have to go to sleep again, right? So how does this work well on uni-processor systems?

Let me answer the last question first.  It points out that the paper was written in 2002, when multi-core processors were much more expensive.  I think the authors were largely concerned with optimizing for the single-core case.

  ... how [is] random fairness ... any better on uni-processor systems in comparison to multiprocessor systems.

On a uniprocessor only one process can be scheduled at a time.  So everyone gets "woken up," but that just means they get moved from a waiting state to a ready state.  Then the scheduler is invoked and it chooses one of the ready processes to run, and lets that process run for some period of time.

The first thing the newly running process does is acquire the lock.  Then it does some processing and (if you are not unlucky) releases the lock.  In this case the next time the kernel scheduler gets control it chooses another "ready" process and starts it running.  If the first process released the lock, then the second process will acquire it, and so on.

On a multiprocessor on the other hand, all the processes might get "woken up" and then the scheduler starts some/many/all of them running simultaneously on different processors.  One of the processes will acquire the lock, but all the other processes will try to acquire the lock, immediately fail, and put themselves back to sleep on the wait queue.  So on all the processors but one you just wasted several kernel calls and several context switches just so you could tell a bunch of processes that there was nothing to do.

  does a fair locking scheme result in an increased number of context switches because different tasks put processes into the wait queue at different times and thus by serving processes in the order they were received, we'd be context switching between multiple tasks?

I think the case they have in mind is if you have multiple processes (on one processor), where each process acquires the same lock repeatedly for short periods of time.  In the unfair case the first process can run for a while and acquire and release the lock many times without doing a context switch.  Then the second process runs for a while and acquires and releases the lock many times.

In the "fair" case the first process locks/releases and then the second time it tries to lock it must be put to sleep, and the kernel has to do a context switch and wake up the other process.  The processes ping-pong back and forth doing "wake up, lock, unlock, work a little while, try-to-lock, get put to sleep."

  how does granting locks in the order of arrival cause processes to proceed at the speed of the slowest process? Wouldn't this only be the case if the slowest process is granted the lock before the other processes? Similarly, how does having processes contending randomly for the lock solve the convoy problem?

I think they are making the observation that, on a uniprocessor, shortest-job-first (unfair) has shorter average wait times than does round-robin (fair).  But I don't understand how random decreases the average wait times compared to round-robin.


Complexity of Towers of Hanoi I ran into the following doubts on the complexity of Towers of Hanoi, on which I would like your comments.

Is it in NP?
Attempted answer: Suppose Peggy (prover) solves the problem & submits it to Victor (verifier). Victor can easily see that the final state of the solution is right (in linear time) but he'll have no option but to go through each of Peggy's moves to make sure she didn't make an illegal move. Since Peggy has to make a minimum of 2^|disks|  - 1  moves (provable), Victor too has to follow suit. Thus Victor has no polynomial time verification (the definition of NP), and hence can't be in NP.
 Is it in PSPACE  ? Seems so, but I can't think of how to extend the above reasoning.
 Is it PSPACE-complete?  Seems not, but I have only a vague idea. Automated Planning , of which ToH is a specific instance,  is PSPACE-complete. I think that Planning has far more hard instances than ToH.

 Updated : Input = $n$, the number of disks; Output = disk configuration at each step. After updating this, I realized that this input/output format doesn't fit a decision problem. I'm not sure about the right formalization to capture the notions of NP,PSPACE, etc. for this kind of problem.

 Update #2 : After Kaveh's and Jeff's comments, I'm forced to make the problem more precise:

  Let the input be the pair of ints $(n,i)$ where $n$ is the number of disks. If the sequence of moves taken by the disks is written down in the format (disk-number,from-peg,to-peg)(disk-number, from-peg, to-peg)... from the first move to the last, and encoded in binary, output the $i$th bit.

Let me know if I need to be more specific about the encoding. I suppose Kaveh's comment applies in this case?

No, the problem you've described is actually quite easy.  The high-level reason is that the index $i$ is roughly $n$ bits long, so we can actually afford to spend time polynomial in $n$.

Consider the following related problem: Given two integers $n$ and $k$, describe the $k$th move in the solution of the $n$-disk puzzle.  The input size is $\lg n + \lg k < n + \lg k$, but in fact, only the least significant bit of $n$ matters.  So even if $\lg k$ is significantly smaller than $n$, we can solve this problem in time polynomial in $O(\log k)$.

Suppose the disks are numbered from $0$ to whatever in increasing order by size, and pegs are numbered 0=source, 1=destination, and 2=spare.  Let us write $k = (2p+1)\cdot 2^d$ for some integers $p$ and $d$.  Then on turn $k$:

If $d+n$ is odd, then disk $d$ moves from peg $(p\bmod 3)$ to peg $((p+1)\bmod 3)$.
If $d+n$ is even, then disk $d$ moves form peg $(-p\bmod 3)$ to peg $((-p-1)\bmod 3)$.

We can easily compute $p$ and $d$ in time $O(\log k)$ by looping through the binary representation of $k$ from the least significant bit upward.  That's it.

Now suppose you really want the $i$th bit in the output sequence, where $i$ is part of the input instead of $k$.  If every turn is encoded using the same number of bits — specifically, $\lg(n+1)$ bits for the disk number, $2$ bits for the from-peg, and $2$ bits for the to-peg — then we just have to compute the $k$th move, where $k = \lfloor{i/(\lg(n+1)+4)\rfloor}$, and then extract the appropriate bit.  (Notice that $\lg(n+1)+4$ is linear in the input size, since we need to know $n$ to determine the output.)

On the other hand, if we're using a variable-length representation for the disk numbers, then we can find the move number $k$ in polynomial time by binary search.  We need to know  the total number of turns needed to move the top $m$ disks, for all $m\le k$, but this is given by the recurrence
$$
M(m) = 2M(m-1) + (\text{\#bits to record moving disk } m)
$$
which we can evaluate in polynomial time by dynamic programming.  The remaining details are left as a boring exercise for the reader.

(I assume I've made at least one off-by-one or parity error, but hopefully the main idea is clear.)


DFA that rejects $a^{23}$ but accepts $\{a^i|i\geq 24\}$ Construct a DFA $M$ with $\Sigma = \{a\}$ and max. 11 states so that $a^{23}\not\in L(M)$ but $\{a^i|i\geq 24\}\subset L(M)$.

I don't see how it is possible? Because it's a DFA and the alphabet only contains $a$, shouldn't I only be able to look at modulo 11? I could make 1 mod 11 not accepting but then $a^{34}$ would not be accepted as well.

EDIT: The prof confirmed it was a typo. We are looking for a NFA. Thanks everyone!

This is not possible. A DFA on a one symbol alphabet is a directed graph with out-degree 1. The walk one follows from the start state consists of a (possibly zero length) path followed by a cycle. As all sufficiently long strings are accepted, all states in the cycle must accept. If the DFA has at most 11 states, a walk of length 23 must be in the cycle, so it must accept.

More generally, if a DFA on one symbol rejects $a^n$ but accepts all $a^m$, $m>n$, then it must have at least $n+1$ symbols and start with a path of length $\ge n$, the $n$th state rejecting, followed by a cycle of accepting states of length $\ge 1$.


Space efficient data structure for subsets of [1:n] Let $S= \{1,2,3...,n\}$ be a set and I want to store a subset of $A \subseteq S$. Is there exists any data structure such that insert$(x)$, delete ($x$) can be done in amortised $O(1)$ time and search($x$) can be done in $O(1)$ time, where $x\in A$. Space used by data structure should be $O(n \log^{*}n)$ or $O(n)$ bits. Model of computation is RAM.

Bit vectors fulfill all your requirements.


Leo's deterministic reduction for Earley Parsing I am trying to build an Earley parser using the Wikipedia pesudocode as a base, with Aycock's fix for epsilon rules as follows:

def predict(self, column, symbol, state):
    # original predict
    for alternative in grammar[symbol]:
        column.add(a new state corresponding to alternative)
    # Aycock fix
    if nullable(symbol):
        column.add(state.advance())

And Leo's optimization for right recursion using the explanation here for further insight.
I am able to understand how to parse Right Recursive grammars with it. However, I am confused when it comes to using it to parse non-right recursive grammars.
For example, here is a grammar that can parse an example string aa

    <start> := <A>
    <A>     := <A> + 'a'
    <A>     := \epsilon

Without the deterministic reduction from Leo, the Earley items constructed (pipe indicates the dot) are as follows:
The parenthesis is in this format (starting column, earley set).

char: _ column[0]
<start>:= | <A>(0,0)     #1) init
<A>:= | <A> a(0,0)       #2) predict from 1
<A>:= |(0,0)             #3) predict from 1
<start>:= <A> |(0,0)     #4) epsilon complete from 3
<A>:= <A> | a(0,0)       #5) epsilon complete from 3

char: a column[1]
<A>:= <A> a |(0,1)       #6) scan a from 5
<start>:= <A> |(0,1)     #7) complete A from 1 (start col of 6)
<A>:= <A> | a(0,1)       #8) complete A from 2 (start col of 6)

char: a column[2]
<A>:= <A> a |(0,2)       #9) scan a from 8
<start>:= <A> |(0,2)     #10) complete A from 1 (start col of 9)
<A>:= <A> | a(0,2)       #11) complete A from 2 (start col of 9)

According to Leo,

  Definition 2.1: An item is said to be on the deterministic reduction path above $ [A \rightarrow  \gamma., i] $ if it is $ [B
> \rightarrow \alpha A ., k] $ with $ [B \rightarrow \alpha . A, k] $
  being the only item in $ I_i $ with the dot in front of A, or if it is
  on the deterministic reduction path above $ [B \rightarrow \alpha A .,
> k] $. An item on such a path is called topmost one if there is no
  item on the deterministic reduction path above it.

(I am assuming that $ [B \rightarrow \alpha A ., k] $ is also in $ I_i $.)

The completer is as follows:

def complete(self, column, state):
    detred = self.deterministic_reduction(state)
    if detred:
        column.add(detred)
    else:
        for st in (matching states in start column of state):
            column.add(st.advance())

column 0

So, when it processes item (3) <A>:= |(0,0) in column[0] for completing, it finds both item (1) which obeys the restriction for a single item with dot before <A> and the corresponding item (4) with dot after. Hence, it considers (4) on the deterministic path. This does not change anything for column[0]. However, things change for column[1].

column 1

When it processes (6) for completing, it again finds (1) and item (4), and hence (4) is considered a parent in the deterministic path. Hence, it saves a copy (4) to the column[1] rather than completing it traditionally in earley. This means that the item (8) <A>:= <A> | a(0,1) from the original Earley parse never gets created, which means no item for accepting the next a in column[2] (which should have been added to column[2] by scanning of this item), and the parsing fails.

So, my understanding of deterministic reduction bye Leo is somehow faulty. Where have I gone wrong?

I have read up on all materials I could get on Leo's optimization, but still unclear what I have missed. I think the item (4) should not be a parent because it is not a previous instance of the recursive rule in item (6). However, nothing in Leo's paper seems to explain how I can exclude such instances from the deterministic path.

If it helps, the complete self contained implementation is here.

I found the problem: Essentially, I misunderstood the definition. It says that

  it is [B→αA.,k] with [B→α.A,k] being the only item in Ii with the dot
  in front of A, or if it is on the deterministic reduction path above
  [B→αA.,k].

Which should be interpreted as [B→αA.,k] should be considered to be created corresponding to [B→α.A,k]. The basic idea which seems to be elided in Leo's paper but given in Grune et al. (2008) is that, the deterministic reduction is basically simply an eager completion with all intermediate results thrown away. With this change, the parser works correctly.

(The "Parsing Techniques A Practical Guide" by Grune et al. from 2008 is the book I refer to here.)


Can an FO formula with infinite length be expressed with an infinite set of finite formulas? I'm confused as to why we can't write formulas of infinite length in FO. For example, to express reachability, I understand the proof that there cannot be a single formula for it, but it is expressible with a set of formulas?

Since any formula has an equivalent formula in CNF, if we transform a formula of infinite length to some CNF, and then break the conjunct up into clauses and put them in a set, is it then expressed with an infinite set of finite formulas?

On the other hand, can an infinite set of finite formulas be joined by conjunctions to obtain an equivalent formula of infinite length?

You are getting at infinitary (first-order) logic. While a well-defined (and natural, and extensively studied) concept, it is quite different from ordinary first-order logic. Before diving into more detail, let me point out the main issue with your suggestion:

  There are "infinitely long" expressions which aren't just infinite conjunctions of finite expressions.

That is to say, your idea

  Since any formula has an equivalent formula in CNF, if we transform a formula of infinite length to some CNF, and then break the conjunct up into clauses and put them in a set, is it then expressed with an infinite set of finite formulas?

is incorrect. One way to see this is with the compactness theorem. For example, suppose I had a set $\Gamma$ of (finitary) first-order sentences which expressed connectedness. Then consider the expansion of $\Gamma$ to include sentences saying "$c$ is at distance at least $n$ from $d$," for each natural number $n$, where $c$ and $d$ are new constant symbols. By the usual compactness argument, this has a model, but (the reduct of) this model isn't a connected graph; contradiction.

The usual manipulations we perform with finitary formulas don't behave intuitively in general when we look at "infinitary" formulas, and in fact infinitary logic (see below) is a very different beast from its finite counterpart.

Having said what infinitary logic isn't, let me end by saying a couple sentences about what infinitary logic is.

For a start, let's look at the simplest nontrivial example: $\mathcal{L}_{\omega_1,\omega}$. This is smallest class containing all first-order formulas, closed under (a) quantifiers and (b) countably infinite conjunctions and disjunctions. This logic is much stronger than first-order logic - for example, connectedness (in the language of graphs) is definable by an $\mathcal{L}_{\omega_1,\omega}$-formula, namely

$$\forall x,y[\bigvee_{n\in\mathbb{N}}\exists z_1,...,z_n(z_1=x,z_n=y, z_1Ez_2E...Ez_n)].$$ This is a relatively simple infinitary formula, and there are much more complicated ones we can consider; there is a rich (and non-collapsing) hierarchy of infinitary formulas, and in fact many fragments of $\mathcal{L}_{\omega_1,\omega}$ of mathematical interest (see e.g. this paper for a good starting point).

We can go beyond $\mathcal{L}_{\omega_1,\omega}$ by either allowing longer Boolean combinations, or infinitely long blocks of quantifiers, but as we go further up the hierarchy of infinitary logics things get progressively much nastier. $\mathcal{L}_{\omega_1,\omega}$ is quite abstract, but still "concrete" enough to be relevant outside of infinitary logic - see e.g. the notion of a Scott sentence, which is useful in computability theory, classical model theory, and set theory.

There are several texts on infinitary logic; I recommend Marker's recent book as a good starting point, and Barwise's old book for a more in-depth treatment of the "local" flavor.


Induction proofs in Big-O notation I'm not sure how go about this question:
Prove the following inequality. For a correct proof, we require a value of the constant $c>0$ and an $n \in \mathbb N$, such that $\forall n>N : f(x)<c\cdot g(n)$.

$\mathcal O(2^n) < \mathcal O (n!)$.

I'm well aware how to prove $2^n < n!$ using induction, I just don't understand how  one is supposed to find a constant, etc. The only thing that springs to mind here is choosing $N = 4$, since that is when $2^n < n!$ begins to hold. If someone could clarify how I can apply the definition of Big-O notation to solve this, I would be greatful.

We need to inspect the factors after that, since the factors of $n!$ grows linearly while the factors of $2^n$ stays constant. We use the first four factors and the rest of them to formulate the constant factors used for the big-O proof. It is obvious that $2^4 = 16$ while $4! = 24$. However, by observing the factors, we notice $2^n$ has $16$ as a factor and $n!$ has $24$ as a factor for all $n \geq 4$ and we factor out the first four [the first $N$] to clearly highlight that the factorial grows faster.

The factors of $\frac{1}{16} 2^n$ factors out the first $2\cdot 2 \cdot 2 \cdot 2$. It is equal to $2\cdot 2\cdot 2\,\cdot \, ... \cdot \, 2$ with $(n-4)$ factors. The factors of $\frac{1}{24}n!$ factors out $1 \cdot 2 \cdot 3 \cdot 4$ and is equal to $5 \cdot 6 \cdot 7\, \cdot \,... \cdot \, n$, again with $(n-4)$ factors. When $n = 4$ then these factored-out functions are equal to unity. In fact:

$2\cdot 2\cdot 2\,\cdot \, ... \cdot \, 2\cdot 2 = c_f2^n$ where $c_f = \frac{1}{16}$ whereas
$5 \cdot 6 \cdot 7\, \cdot \,... \cdot \, (n-1) \cdot n = c_gn!$ where $c_g = \frac{1}{24}$.

The $(n-4)$ factors of $c_f2^n$ is clearly less than the $(n-4)$ factors of $c_gn!$. We arrive at $c_f2^n < c_gn!$. Move the constant factor on the LHS to obtain $2^n < \frac{c_g}{c_f}n! = \frac{24^{-1}}{16^{-1}}n! = \frac{16}{24}n! = \frac{2}{3}n!$.

By inspecting the factors of $2^n$ and $n!$ after the initial four, and knowing that for all $n > 4:\: 2^n < n!$, we factored out the first four terms of each function and inspected the rest to determine $2^n \leq \frac{2}{3}n!$.

The formal definition of big-O states that:

$$\exists c > 0\; \exists N > 0: \forall n\; (n>N) \Longrightarrow f(n) \leq cg(n)$$

In your case, $c = \frac{2}{3} = \frac{16}{24}$ and $N = 4$.


Proving NP completeness of maximal length path I have this question to answer:

For each node i in an undirected network $G = (N,E)$, let $N(i) = \{j \in N : \{i, j\} \in E\}$ denote the set of neighbors of node $i$ and let $c_e\geq0$ denote the length of edge $e \in E$. For each node $i \in N$, suppose
the set $N(i)$ is partitioned into two subsets, $N^+(i)$ and $N^-(i)$ such that $j \in N^+(i)(j \in N^-(i))$ is referred to as a positive (negative) neighbor of $i$. (Note: Regardless of whether $j$ is a positive or negative neighbor of
$i$, $i$ can be either a positive or negative neighbor of j.) Consider the problem of ﬁnding a maximum-length
path $(s =) i(0)–i(1)–···–i(h)(= t)$ in $G$ between two nodes $s ∈ N$ and $t ∈ N$ subject to the following restriction: For each internal node $i(k)(k \in\{1,...,h − 1\})$ on the path, the set $\{i(k − 1),i(k + 1)\}$ must contain exactly one positive neighbor and one negative neighbor of $i(k)$. Prove NP-completeness of the decision problem and state whether it strongly NP-complete or not.

I wonder about the steps of the proof and whether shall I start from the longest path problem or from another problem instance.

I think here is a pitfall due to inaccurate notation.
Notation for me:

A trail is a sequence of distinct connected edges.
A path is a trail with distinct vertices.

In the problem instance $MNPL$ (maximum neighbor path length) the sets $(G,N^+, N^-)$ and the weight function $c_e$ are given as input(and hereby fixed).
Since $N$ is partitioned, for two vertices $u,v$ either $\{u,v\}\notin E$ or $u$ is a positive neighbor of $v$ or vice-versa. Especially $u$ and $v$ cannot be a positive neighbor of each other by definition ($N$ would not be partitioned). Hence $G$ must be a directed graph.
Now, for any path  $s \rightsquigarrow (u,v,w) \rightsquigarrow t$(not way nor cycle nor walk!) the neighbor-condition is fullfilled.

Maybe this was the real challenge of this exercise?

So, claim: $MNPL$ is $NP$-complete.

Proof: $MNPL \leq_p LPP$ (longest path problem)
Consider the reduction $f$. For $(G,N^+,N^-,c_e)$ construct $G'=(V',E',c_e')$ as the following:

$c_e'$ = $c_e$
$V' = V$
$E' = \bigcup_{v \in N^+(u), u \in N} (u,v) \cup \bigcup_{u \in N^-(v), v \in N} (v,u)$

Clear: $f$ is computable and runs in poly-time ($O(|E|)$). By construction and with the observations above $f$ will construct a digraph from $N$ and the neighbor sets.

So $f$ is a reduction and $MNPL \in NP$ is obvious using "guess and check".
Since $LPP$ is strongly $NP$-complete, $MNPL$ is as well strongly $NP$-complete.
This is no decision problem but a maximization problem.


Given a pile of cards, how to program to get card combinations whose sum is closest to 21? This is an interview question:

Given a pile of cards, how to program to get card combinations whose sum is closest to 21?

Example:

input:

Array : 2, 3, 4, 5, J, K

output:

2, 4, 5, J

2, 4, 5, K

I have a naive solution:

check if two cards' sum is 21;

check if three cards' sum is 21;

check if four cards' sum is 21;

check if five cards' sum is 21;(Max number of cards in blackjack)

However, this is brute force solution.

Can anyone give me a hint to get a better solution? Thanks!

You have at least two options.

If the number of cards is very small, as in your example, then you can go over all possible subsets of cards and compute their sum, taking note of the one closest to 21. Then go over all of them again and output the ones achieving the best sum. With a realistic number of cards this will be very fast.

What they might have expected you to answer is to use dynamic programming. For each sum from 2 to 21, go over all cards and see if it is achievable from an earlier sum (including 0), and if so, annotate this with all possible cards. Now find the best sum and follow the edges back to 0.


Implementing Deterministic Turing Machine If i want to implement a Deterministic Turing Machine from a Non-deterministic Turing machine is always suggested to use the Breadth-first algorithm ?
If yes, why ?

The reason for that is, if you use Depth-First Search (DFS), there exists the probability of the search going through a path that is infinite in length (loop) and you will never get an answer. If you use BFS it's more likely that you will find a path on to an accept state, if a path to one exists.

For example imagine that you have a tree with 100 children on left from the root and the right child of the root you only have 3. If you use DFS you will traverse the 100-deep left branch and later go right, and now instead having 100 branches just imagine you have infinite number of branches.


Find sets of weighted objects to maximize number of sets with weight >= X I have N objects, each of which has a weight. I need to form combinations of the objects to maximize how many sets of objects add up to at least x total weight. Combinations can consist of any number of objects.
1). What is a fast and correct algorithm to solve this?
2). Is this NP-complete, hard, or neither?
Ideally, I'd want the left over set of objects that does not add up to x to be maximal as well, but would settle for an understanding of how to solve the problem without this.

This problem is NP-hard as it can be seen by a reduction from $3$-partition.
In the $3$-partition problem we are given a (multi-)set $\mathcal{S}$ containing $3n$ positive integers $x_1, \dots, x_{3n}$ and the goal is that of deciding whether there exists a partition of $\mathcal{S}$ into $n$ sets $S_1, \dots, S_n$ of $3$ elements each, such that, for each $i$, $\sum_{x \in S_i} x = T$, where $T = \frac{1}{n} \sum_{i=1}^{3n} x_i$.
It is known that this problem remains NP-hard even when each $x_i$ is strictly between $T/4$ and $T/2$. We will therefore restrict to such instances.
To obtain an instance of your problem, it suffices to use the same set of integers $\{ x_1, \dots, x_{3n} \}$ (i.e., $N=3n$) with $X = T$.
Clearly, since the sum of any two input elements can be at most $2 \cdot (\frac{T}{2}-1) < T = X$, we have that, in any partition $\mathcal{P}$ of $\{ x_1, \dots, x_{3n} \}$, the number of sets $S \in \mathcal{P}$  such that $\sum_{x \in S} x \ge X$ can be at most $N/3 = n$.
If the answer to the 3-partition instance is "yes", then the same partition $S_1, \dots, S_n$ exactly matches this upper bound in the instance of your problem.
On the other hand, if the answer to the 3-partition instance is "no", then in any partition of $\{ x_1, \dots, x_{3n} \}$ there is at most one set with sum smaller than $T$, i.e., there are at most $n-1$ sets with sum at least $T$.
To summarize: the answer to the instance of $3$-partition is yes if and only if the optimal solution to the corresponding instance of your problem has measure at least $n$.
Your problem is not NP-complete since it does not belong to NP (since it is not a decision problem). Unless P=NP there is no efficient (polynomial-time) algorithm for your problem.


Is this a good way of generating diverse solutions to a problem using a genetic algorithm? Imagine a complicated blackbox-esque system that has 20 inputs and 5 outputs. I have a set of criteria I am able to use to construct a fitness function. I run a genetic algorithm to deduce values which maximize my fitness function, and I keep iterating until a solution emerges which passes a threshold. Once this threshold is met, the genetic algorithm starts afresh except the fitness function now includes a positive term proportional to the euclidan distance between the candidate solutions and the previously determined solution (the one that exceeded the threshold earliar.)

Once a second set of inputs is found which matches exceeds the threshold, the fitness function is updated to also include a term proportional to the euclidian disance from the second solution. Both terms are divided by two to prevent this euclidan distance derived terms in my fitness function from overpowering the others.

Would a process like this, iterated sufficiently, be an efficient way of generating a diverse set of inputs, each of which represents a set of inputs which achieve a high fitness score?

(Please assume that a diverse of solutions exists for the problem at hand; the goal of the algorithm is to find them)

The success (or otherwise) of your proposed scheme may well be highly problem dependant, so I would urge you to consider diversity-promoting methods such as 'niching' or 'island models' that have proved useful across a wide-range of problems.

Island models, for example involve partitioned populations that are evolved separately, with only occasional gene transfer.

More details on diversification methods can be found in the (freely downloadable) 'Essentials of Metaheuristics'


What is an algorithm that maps back and forth from (x,y) coordinates to the index of that point in a space filling curve over a rectangle? Suppose that I have a space filling curve over a rectangle of width W and height H. For example, for the rectangle:

W = 4
H = 4

I have the following curve:

Now, given the following coordinate:

X = 1
Y = 2

We can say that its position on the space-filling curve is 7, as it takes 7 steps walking over the curve to reach that tile. Using that logic, we can build a mapping width → height → x → y → index, such as:

spaceFillingIndex(4,4,1,2) = 7

As well as its inverse, width → height → index → (x,y).

spaceFillingCoordinate(4,4,7) = (1,2)

My question is: what is an algorithm that implements spaceFillingIndex, and what is an algorithm that implements spaceFillingCoodinate?

I found the math behind the hilbert curve very interesting (generates the space filling coordinates, with index)
http://www.fundza.com/algorithmic/space_filling/hilbert/basics/index.html

Python package refer,
https://github.com/galtay/hilbertcurve

for rectangles , you need pseudo Hilbert curve generation
https://stackoverflow.com/questions/38463130/hilbert-peano-curve-to-scan-image-of-arbitrary-size

and refer this
https://github.com/jakubcerveny/gilbert


Is $\Gamma = Inv(Pol(\Gamma))$? I'm reading A Rendezvous of Logic, Complexity and Algebra, my first introduction to the world of CSP. Let $\Gamma$ be a finite constraint language. It says in Pg. 9 that

  $Pol(\Gamma)$ is used to denote the set of all polymorphisms of $\Gamma$, that is,
  $$Pol(Γ) = \{f : \forall R \in \Gamma, \textrm{ f is a polymorphism of }R\}.$$
  Also, for a set of operations $O$, we use $Inv(O)$ to denote the set of relations having all operations in $O$ as a polymorphism, that is,
  $$Inv(O) = \{R : \forall f \in O, \textrm{ f is a polymorphism of } R\}.$$

The answer to my question is: No (in fact it is a subset of $\Gamma$). But I don't understand why:

Isn't every $R\in \Gamma$ in $Inv(Pol(\Gamma))$?
Are the $R$'s from $Inv(O)$ allowed to come only from $\Gamma$?

The operation $\operatorname{Inv}(\operatorname{Pol}(\cdot))$ is a closure operation. This means that

$\Gamma \subseteq \operatorname{Inv}(\operatorname{Pol}(\Gamma))$.
$\operatorname{Inv}(\operatorname{Pol}(\Gamma)) = \operatorname{Inv}(\operatorname{Pol}(\operatorname{Inv}(\operatorname{Pol}(\Gamma))))$.

See for example lecture notes of Jin-Yi Cai.


Suitable choice for moderate-size square matrix multiplication? The problem is to find $C = AB$, where $A$ and $B$ are $n \times n$ matrices that may be sparse. Let $n$ be around 1000. The elements of $A$ and $B$ are real values, though, for practicality's sake, let's say we use floating-point numbers. Ideally, the approach would be fast enough for small $n$ and, of course, should not require size ($n$ value) of ~$10 ^ 6$ to break even relative to brute-force cubic time approach. The lower the running time, the better. Given ties, the lower the coefficient for running time, the better. Given ties again, lower space requirement is desired. Algebraic or combinatorial approaches are acceptable.

Then, what is a suitable algorithm choice for this moderate-size-input square matrix product problem?

Dumas and Pan recently wrote a non-asymptotic survey of fast matrix multiplication in practice, which hopefully answers your questions. They concentrate on matrices of order at most a million, and list all relevant algorithms.


Wikipedia says this grammar is LR(0), but Grammophone says it is not; is it? E -> E * B .
  E -> E + B .
  E -> B .
  B -> 0 .
  B -> 1 .

I am confused because Wikipedia cites this grammar as an example of an LR(0) grammar and constructs an LR(0) parsing table for this grammar, while Grammophone reports shift-reduce conflicts and marks some cells in the grammar's LR(0) parsing table red. (The dots are not terminals; rather, they denote end of production; Grammophone requires this.)
What's going on here?

Before applying the LR algorithm to a grammar, the grammar must be "augmented" by adding the rule

$S' \to S \$$

where $S$ is the original start symbol and $S'$ and $\$$ are symbols not in the grammar. $S'$ becomes the start symbol for the augmented grammar, and the string to be parsed is augmented by appending a $\$$ at the end. A reduce action for this newly added rule is written as "accept", which has the side effect of terminating the parse.

The table shown in the Wikipedia article is for the augmented grammar, as you can see from its parsing table, which includes "accept" actions and the $\$$ end marker symbol.

For whatever reason, Grammophone does not augment grammars before applying the LR(0) algorithm. The grammar is augmented for the other algorithms. (I would call this a bug, but it could argued that it is an idiosyncratic interpretation of the algorithm.) If you give it an augmented grammar, then you get roughly the same LR(0) table as is found in Wikipedia (although an extra state is produced prior to the accept action.)

Grammophone has other issues. I don't recommend relying on it for grammar analysis.


Positive Definiteness Constraint I want to add a constraint to a convex program, to guarantee some matrix $A$ to be positive semidefinite.
How should I do it?

The library I am working with can cope with linear/ quadratic inequalities only.

By definition, $A$ is positive semidefinite iff $\forall x \in \mathbb C^n : x^T A x \geq 0$, but this is a set of inifinitely many constraints. So, my question is: how can I formulate it using a finitely many set of contraints and using linear/ quadratic inequalities only.

Thanks in advance!

A matrix $A$ is positive semidefinite if and only if there exists a matrix $V$ such that $$A = V^\top V.$$
So, you can use the entries of $V$ as your unknowns, and express each entry of $A$ as a quadratic function of the unknowns.  Whenever you want to use $A$, instead rewrite that equation in terms of the entries of $V$.


How to find out the complement of a language of turing machines? With only using our thinking. What do I have to think about when finding a complement of a Turing machine for example.

L={M∣M is a TM that halts on empty tape after even transition steps}
What's the complement of L would it be:

L={M∣M is a TM that does not halt on empty tape after even transition steps}
L={M∣M is a TM that halts on empty tape after odd transition steps}

Please give me your train of thought when coming up with a complement for an automaton.

You cant find the complement of a $TM$ for undecidable languages.
A decidable language is such that a $TM$ which recognizes language membership, always halts with a yes. In this case finding the complement of the machine is simple, just reverse the yes with the no, obtaining the complement of the original decision problem. I leave to you
the task of determining whether the language of your example is decidable or not.

HINT:
you can compare it with the Halting problem or $ATM$


Find all local minima in a big 2d array Assume we have a big 2d array. All its elements are either zeros or natural numbers. A local minimum is an element that is less than all its 8 neighbors. Is there an effective algorithm to find all local minima in the array?

Scan the entire array to check each cell to see whether it is a local minimum.

There's no algorithm that is asymptotically better; this is optimal to within a constant factor.  (Proof: if there is any 3x3 region that you haven't looked at, it might contain a local minimum.  So any correct algorithm will need to examine at least one cell out of each 3x3 region, i.e., must examine at least 1/9th of the array.)


Can we build a nondeterministic decider PDA using two PDAs accepting a language and its complement? When talking about turing machines, it can be easily shown that starting from two machines accepting $L$ and its complement $L^c$, one can build a machine which can fully decide if a word is inside $L$ or not.

But what about PDAs? starting from two different PDAs, one accepting $L$ and one accepting $L^c$ can we build another PDA, which accepts $L$, and only crashes or halts in non-final states (rejects) when $w\notin L$?

Yes, it is possible to do so. Although a given PDA may have $\varepsilon$ loops that can induce infinite computation, we can sidestep this by converting the PDA to a CFG, then back to a PDA (using the standard methods). The second PDA is guaranteed to halt on all inputs (this is not too hard to see if you know the conversion method - essentially you guarantee that either a non-terminal from the CFG is added to the stack, or a terminal is read from the input at each broad step and the nondeterminism takes care of the rest, or equivalently, CFGs can always be parsed).

So then we can take the PDA for $L$, apply this transition, and we get a machine that always halts, and only halts in an accept state if the input is in $L$.


Multiple neural networks or multiple outputs? Suppose you have data of the form input a matrix A, and output a matrix B, where each row of each is one datapoint. Should you create multiple neural networks, one for each column of B, or one NN with multiple output neurons, one for each column of B?

You can do either.

If the learning tasks are related at all (i.e., the meaning of the columns of B are related), it's probably better to have one neural network with multiple outputs.  This is often more effective, because the first few stages of that neural network might do some processing that is relevant to all of the outputs -- e.g., it might look for some local patterns or properties of the input that can then be useful for predicting all of the outputs.  The network might take a bit longer to train if you use one big network rather than many smaller networks, but usually this is worth it if it leads to better accuracy.

But if you're not sure, you can always try both approaches and see which works better.


Terminology - machine code and byte code Do "machine code" and "byte code" terms refer to the available instruction set to the CPU and virtual CPU and their encoding (the language specification) or do they refer to the "encoding" of the current program's instructions after compilation?
The definitions I found in wikipedia seem to lean towards the notion of "instruction set":

https://en.wikipedia.org/wiki/Machine_code
https://en.wikipedia.org/wiki/Bytecode

Both are sequence of instructions encoded as binary data. The difference being that "Machine code" is executed by the CPU whereas "byte code" is executed by a software (which itself is made up of machine code and executed by CPU).


Can this CFG be written into an equivalent LL(1) grammar? I have the following CFG which I suspect cannot be rewritten to one which is LL(1):

$S \rightarrow \epsilon\ |\ aSbS\ |\ bSaS\ |\ cSdS\ |\ dScS$

I've thought about it for a while, and can't seem to make any progress. I know that the simpler grammar here can be rewritten into LL(1), but it seems like there is something different about the above grammar which prevents a rewriting in a similar style. Is it possible? If not, is there an easy way to prove that this is the case?

The comment above is correct. What is referenced here is generally called a "first-follow set clash" and occurs when a non-terminal is nullable, and has non disjoint first and follow sets. You can try to remove these by substituing for the nullable non terminal (shown for your grammar below). However, this process might result in a loop. If that happens, your grammar can't be transformed to LL(1).

Note that . simply denotes esp.

S → a S b S
|   c S2 S
|   d S1 S
|   .
S1 →    a S b S1
|   c S2 S1
|   d S1 S1
|   c .
S2 →    a S b S2
|   c S2 S2
|   d S1 S2
|   d .

S2 =    S d. (uh-oh, we've gone in a loop here)
S1 =    S c.