Is packing a bag of presents easier for Rupert than Santa? Or: Do we need Rupert in order to get presents at all?
Routing issues aside, Santa faces the following problem (many, many times over):

Given a bag with capacity¹ $C$ and a set of presents $\{p_1, \dots, p_n\}$, each with size $s_i$, he wants to make children $\{c_1, \dots, c_k\}$ happy. He knows from all the wish lists that child $c_j$ values present $p_i$ exactly $v_{i,j} \in \mathbb{Q}_{\geq 0}$ much.
Which (pairwise disjoint) sets of presents $I_j \subseteq [1..n]$ to pick for each child so that everything fits, i.e.
$\qquad\displaystyle \sum_{j \in [1..k]} \sum_{i \in I_j} s_i \leq C$,
and as much happiness as possible ensues², i.e.
$\qquad\displaystyle \max! \sum_{j \in [1..k]} \sum_{i \in I_j} v_{i,j}$ ?

This is clearly not easier than Bin Packing or Knapsack, so poor Santa may have to spend a long time packing bags³.

Now, as we know, his assistant Rupert does not give as unconditionally. He has knowledge about $V_j$, the maximum value child $c_j$ may receive based on behaviour during the year; that is, he adds an additional constraint

$\qquad\displaystyle \forall j \in [1..k].\ \sum_{i \in I_j} v_{i,j} \leq V_j$.

Does that make the problem of packing bags easier? If not always, then under which conditions?

If the chimney diameter is the limiting factor, a similar framework can be established.
Let's not concern ourselves with fairness and other ridiculuous ideas.
Hence, only one Christmas per year. Q.E.D.

After quickly looking at this question, I believe Rupert's extra knowledge of each child's {behavior, max value present} will not always make Santa's job easier. Santa will still need to perform a 0/1 knapsack to fill the bags and a Hungarian algorithm as well to maximize the happiness each capitalist child receives on Christmas morning. A simple case where it would make Santa's job quite simple is if every child Santa was considering didn't publish a paper and instead played video games all year received a zero from Rupert (each child would get coal).


Are there criteria that will make: $A \subseteq B$, $A$ unrecognizable imply $B$ unrecognizable? Let $A \subseteq B$, and A is unrecognizable. I know in general that doesn't mean B is unrecognizable. However, are there some limitations we could put on A and B that would make it true? The only thing I could come up with was A=B. Plus, we could say B is unrecognizable as part of our assumptions, but that's not really helpful.

(recognizable means recursively enumerable, in case you use different terminology)

The condition about $B$ can be transformed into a condition about $B\setminus A$, as follows.
If $B\setminus A$ is decidable, then $B$ is unrecognizable.
Indeed, if you could recognize $B$, you could determine whether a word $w$ is in $B\setminus A$. If it is, then it's not in $A$, otherwise it is. So $A$ would be recognizable as well.

Note, however, that the converse does not work - there are sets $C,D$ such that $C\cap D=\emptyset$, both $C$ and $D$ are not recognizable, and $C\cup D$ is unrecognizable as well.


Hash-Table in Practice I have a set of $n$ values,$v_i$ and want to insert them into a hash-table, $HT$, in a way that each bucket (or hash-table cell) has at most $d$ values. I set $k=\frac{n
}{d}$, where $k$ is the number of buckets. Then, I use SHA hash function, $H$, to find the index a bucket in the hash-table and insert the values into the bucket:

$HT [H(v) \bmod k]=v_i$

The problem is that the indices do not look uniformly at random, for instance 3 different values may map into a cell whereas an index may not appear at all. And this can lead overflow.

Notice that I need a deterministic way as two different parties encode their values using hash table. Therefore, if the parties use the identical parameters for hash table, the same values should be in the same bucket (of different hash tables). Obviously different party may have different set values.

Question: What is the best way of preventing overflow in the above scenario?

SHA1 or SHA256, whichever you use, is for any practical purpose a random function. What you are observing is that random allocation is not as good as deterministic allocation. If you knew all the values in advance then you could indeed arrange that each cell would get exactly the same number of hits. Unfortunately, when you throw $n$ balls into $k$ bins, the number of balls landing into each bin isn't $n/k$ but rather has roughly Poisson distribution with mean $n/k$ (assuming $n/k$ is "small"). Thus you expect there to be a few bins which do get quite a few balls more than their share, and vice versa. A good hash table should be able to handle that – there are several approaches that you are probably aware of.

A similar situation happens when you throw $n$ balls into two bins. Rather than each bin getting exactly $n/2$ balls, the number of balls in each bin has roughly normal distribution with mean $n/2$ and standard deviation $\sqrt{n}/2$. Thus you expect one bin to contain roughly $\sqrt{n}$ more balls than the other.

Another similar situation concerns throwing $n$ balls into $n$ bins. Rather than an even allocation, you expect the maximum cell to contain roughly $\log n/\log\log n$ balls. However, if any given ball is given two options, and you put it in the lighter bin, then the maximum cell contains only roughly $\log\log n$ balls in expectation. This is one way of coping with your problem.


Using Graphs to construct semi-supervised learning solution I am currently trying to design a graph-based approach for content tagging. In principle I am trying to two two things:

Use an algorithm such as Latent Dirichlet Allocation (LDA) or some variant of it to discover terms in documents that relate to a certain topic, thereby allowing me to tag a document as relating to that topic. None of the documents are labelled yet, so this step is entirely unsupervised
Allow user feedback on whether the labels are correct. This firstly allows us to sharpen labels on specific documents (i.e. override the output from 1. if incorrect). And secondly, it allows us to use these user-defined labels in a semi-supervised learning algorithm, which might perform better than what is done in step 1 (though this part is out of scope for this question).

Step 1 I could represent with a simple graph as follows:

The LDA algorithm outputs the terms found in the document along with some weighting according to their frequency. In addition, it outputs a set of topics along with the terms that are associated with each topic (again, weighted according to how strongly the term is associated with the topic).

Now for point 2 I need to incorporate user feedback, so I need to link a user to a document to indicate that the user has read it and then link the user to the topic, indicating that the user believes the document is about that topic.

But this doesn't really work. "Document is_read_by User" correctly describes the relationship between the document and the user, but "User believes_document_related_to Topic" is not a valid relationship because it is contingent on a specific book - in this case 1984 by George Orwell.

My question is, how could I build this relationship with a graph? I.e for each user I want to be able to capture the following information.

According to User "Karl" the document "1984 by George Orwell" is about the topic "Surveillance"

(Of course, the idea is to allow multiple users to give feedback, thereby strengthening/weakening the relationship between the document and the topic).

One way to express this as a graph is to draw an edge from the document (1984 by George Orwell) to the topic (Surveillance), labelled with the user who approved that relationship (e.g., the label might be: user_believes_doc_is_related_to: "Karl").


How to prove that adding incoming edges to source node doesn't alter the max flow I am given a homework assignment on this question:

  Show that if we add any number of incoming arcs, with any capacities, to the source node, the maximum flow value remains unchanged. Similarly, show that if we add any number of outgoing arcs, with any capacities, at the sink node, the maximum flow value remains unchanged.

While, it can be graphically proved with the help of an example, I am unsure of how to prove it systematically (like usual proofs in textbooks)

Let $G=(V,E)$ be your input graph. Now consider a maximum flow $f$ on $G$.

  Let $f$ be a flow in $G$ such that the residual network $G_R$ has no s-t path, then $f$ is a maximum flow.

Let's define $G'=(V,E')$ to be your graph  with $E'=E \cup \{(u_i,s)\}$  for $i=1,...,N$.

Since $f$ is a maximum flow on $G$, then $G_R$ has no s-t paths.
Now you can show that given $G'$, its residual network $G'_R$ does not have any s-t path too. Thus, $f$ is a max flow also for $G'$.


Estimating run time in the absence of knowledge I’ve always wondered how to make a best guess in the absence of any knowledge.

Let’s say you have a computation running, and you don’t know when it will complete (just that it will). Can you make any estimate when it will be finished just based on the elapsed time without any further knowledge? For example after 10 minutes I cannot tell how much longer it will take, it might take 10 more minutes, or less, or a lot more. But after 4 hours  I’m quite sure it will not finish in the next 10 minutes (that would be a big coincidence). So a guess might be "probably a few hours more". After 4 days I’d be quite certain that it will take a lot longer.

Can you somehow quantify this certainty / uncertainty?

No, you can't make any well-justified estimate, if you truly have no knowledge.

In practice, it's rarely that case that we have zero knowledge.  Instead, we might have some idea what the distribution of total computation time will look like.  That gives you a prior.  In other words, before you start the computation, suppose I asked you for your guess at the probability distribution of what the total computation time will be.  What probability distribution would you choose?  The result is a prior.

If you have a prior, then you can compute an estimate for the remaining run time and quantify the uncertainty, using Bayesian analysis.  Let $p(x)$ denote the prior probability that the total computation time is $x$; in other words, before you start running it and before you make any observation, $p(x)$ is your estimate of the probability that it will take $x$ seconds to terminate.

Now we make an observation, and we want to update our estimate of the probability.  We observe that the computation has run for $y$ seconds without terminating yet.  This implies that, whatever the true value of $x$ will turn out to be, it will be at least $y$.  Using Bayes' theorem we obtain

$$\begin{align*}
p(x|y) &= {p(y|x) p(x) \over p(y)}\\
 &= {p(y|x) p(x) \over \int_0^\infty p(y|x) p(x) \; dx}
\end{align*}$$

We notice that we're going to need to know the distribution $p(y|x)$.  This helps us realize that the problem isn't well-stated yet: you haven't told us how you would decide when to make the observation.

Suppose that we decide in advance, before starting the computation, that we're going to wait $y_0$ seconds and then check whether it has halted or not.  Thus there are two possible outcomes of the observation: "already halted" (finished in $\le y_0$ seconds) or "hasn't halted yet" (will take a total of $>y_0$ seconds to finish).  Let's denote those by the outcomes "A" vs "H", so we'll say $y=A$ in the former and $y=H$ in the latter.  Then we find that $p(y|x)$ has the following form: $p(A|x) = 1$ if $x \le y_0$, else $p(A|x)=0$; and the reverse for $p(H|x)$.  Plugging into the formulas above, we obtain

$$\begin{align*}
p(x|A) &= {p(A|x) p(x) \over \int_0^{y_0} p(x) \; dx}\\
p(x|H) &= {p(H|x) p(x) \over \int_{y_0}^\infty p(x) \; dx}
\end{align*}$$

When $x \le y_0$, we have $p(x|H)=0$ (naturally).  When $y_0 < x < \infty$, we see that $p(x|H) = p(x)/q$, where $q = \int_{y_0}^\infty p(x) \; dx$ is the prior probability that $x$ falls in the range $y_0 < x < \infty$.  Here $q$ is a constant that depends on the prior probability; you can think of it as a normalization constant to ensure that $p(x|H)$ is a probability distribution (it integrates to one).

This gives you the posterior distribution for $x$, after running the experiment (starting up the computation and after $y_0$ seconds checking to see whether it has finished yet) and making the observation (that it hasn't finished yet).  From the posterior distribution, you can make estimates for the total running time.  For instance, one reasonable way to make an estimate is to compute the expected value of this posterior distribution.  In this way we obtain

$$\mathbb{E}(x|H) = \int_0^\infty x p(x|H) \; dx = {\int_{y_0}^\infty x p(x) \; dx \over \int_{y_0}^\infty p(x) \; dx}.$$

You can also summarize the uncertainty in  your estimate using a 95% credible interval.

As you can see, all of this machinery requires that we have a prior for the total running time.  Selection of the prior isn't something math can give you; instead, it needs to reflect your domain knowledge and expectations.  Probably you have some ideas for how likely it is that the computation will take a certain amount of time.  For instance, maybe it's common for computations to take anywhere from 1ms to 1 day, but it's rare to run across computations that take (say) 10000 hours -- usually they'll either complete much earlier, or (occasionally) they'll take much longer, but 10000 hours is a lot less likely outcome than 1 hour.   So, constructing a prior is the (subjective) process of quantifying that knowledge you already have.  Alternatively, the choice of prior might be informed by data, if you collect a data set of how long other computations have taken to complete and use that to fit some kind of distribution to them.

Once you've chosen a prior, then you can use the mathematics shown above to estimate how long the running time will turn out to be, in a methodologically sound way.


Cost of the MST of the graph Studying for a test in a computer science class and cannot figure out the answer to this question.  Any help would be appreciated!

Although the picture shows a directed graph, please treat it as an undirected graph, ignoring all the edge orientations.

A Yuval said, you can just go ahead with any algorithm. In fact, you should probably be able to find a solution by trial and error.

In case you are stuck for some time, move your mouse over to see a solution below.

   We can use Prim's algorithm, which iteratively selects an edge of the least weight from the available edges as long as it does not introduce a cycle.

 We will select the edge of weight 1, two edges of weight 2, all edges of weight 3,4,5,6,7 respectively. We will skip the vertical edge of weight 8 since it introduces a cycle. We will select the horizontal edge of weight 8. Now all vertices have been included except the bottom left one. So we will select the edge of weight 12 to connect vertex.

 The total weight is 1 + 2 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 12 = 50. So the answer should be "none of the listed".


Show that the best case time complexity of Quicksort is $\Omega(n \log n)$ I am trying to show that the best case time complexity of Quicksort is $\Omega(n \log n)$.

The following recurrence describes the best-case time complexity of Quicksort:

$$T(n) = \min_{0 \le q \le n-1} \left(T(q) + T(n-q-1) \right) + \Theta(n).$$

But I have difficulty in proving that $T(n) = \Omega(n \log n)$ using the recurrence above.

So how to solve this recurrence?

Let us replace $\Theta(n)$ with $n$, for concreteness, and assume a base case of $T(0) = 0$. Let's try to prove inductively that $T(n) \geq cf(n)$, where $f(n) = n\log n$ for all $n$ (where $0\log 0 = 0$).

During the proof, we will need to minimize $f(q) + f(m-q)$ for $0 \leq q \leq m$. Since $f'(n) = \log n + 1$, any minimum point must satisfy
$$
\log q + 1 = \log (m-q) + 1,
$$
that is, $q = m/2$. Since $2f(m/2) = m\log(m/2)$ whereas $f(0) + f(m) = m\log m$, we see that $q = m/2$ is indeed a minimum.

We are now ready to prove inductively that $T(n) \geq cf(n)$. The base case is obvious. For the inductive step, note that for each $q \in \{0,\ldots,n-1\}$,
$$
T(q) + T(n-1-q) \geq c(f(q) + f(n-1-q)) \geq c(n-1) \log((n-1)/2).
$$
Therefore to complete the proof, we need to show that
$$
c(n-1) \log \frac{n-1}{2} + n \geq cn\log n.
$$
This holds trivially for $n=1$, and holds for all $n \geq 2$ when $c = 1/\log 3$.

Altogether, this shows that $T(n) \geq n\log_3 n$.


Dynamic Programming - Tiling Question I came across the following question while practising for my final algorithms exam, but I am unsure how to get a linear time complexity for this problem. I assumed it would require checking which tiling patterns are compatible with each other, but get a bit stuck on how to proceed.
Thanks!

Well, the state should be dp[n], the optimal answer for some prefix of size n. Considering the different tiles, the transitions should be intuitive:
dp[n] = max(dp[n-2] + max(a[n], a[n-1]), dp[n-3] + max(a[n-1], a[n-2] + a[n]))
Of course, if any of the indices n-2, n-1, or n-3 are less than 0, then the involving terms should be omitted from the calculation. This is just a general representation of what the transition should be.


Voronoi diagram algorithm with non-euclidean metric Do you know any easy to implement algorithm for constructing a Voronoi diagram from a given set of points on a surface, using some different metric (taxicab, for instance)?
It can be some modification of Fortune's algorithm.

It depends on the metric and your sites. There is a framework called abstract Voronoi diagram that allows you to compute Voronoi diagrams for well-behaved instances. In order to define what well-behaved means you have to give certain guarantees for the bisecting curves defined by your sites and your metric (for example two such curves intersect only in a finite number of points). The exact requirements might differ slightly depending on the paper you read.

If your problem is a abstract Voronoi diagram, then you can compute it with (a variant) of the randomized incremental construction due to Clarkson and Shor - see for example here. Then everything boils down to computations with the bisecting curves.

Note that there is quite some literature about these Voronoi diagrams and also recent progress has been made. I would advice you to go through this.


Either find a perfect matching, or return a witness that none exist I am looking for a polynomial-time algorithm that takes as input a bipartite graph $(X\cup Y, E)$, and returns one of two options:

If a perfect matching exists, it returns the matching;
Otherwise, it returns a witness based on Hall's theorem, i.e., a set $S\subseteq X$ such that the number of neighbors of $S$ is smaller than $|S|$.

I found in wikipedia various algorithms for finding a maximum matching in an unweighted bipartite graph. Such algorithms can be used to determine if a perfect matching exists. But does any of these algorithms also return an evidence in case of failure?

EDIT: I have read the links in the answer of Yuval Filmus below, but it took me some time to fill in the missing details. For future reference, here is a detailed solution. Below, let $n := |X| = |Y|$.

Step 1. Define a flow network with $2n+2$ nodes in the following structure:

$$ s \rightrightarrows X \rightrightarrows Y \rightrightarrows t $$

where:

$s$ is a new source node connected to all vertices in $X$ with capacity 1;
every original edge of $E$ is directed from $X$ to $Y$ with capacity $\infty$;
each vertex in $Y$ is connected with capacity 1 to a new sink node $t$.

Step 2. Use the Ford-Fulkerson algorithm to find a maximum flow in that graph. Suppose the maximum flow size is $m$ (which must be at most $n$).

Step 3. If $m = n$ then we are done - the flow induces a matching of size $n$ which is perfect.

Step 4. Otherwise, $m < n$.
The FF algorithm also returns an $s$-$t$ minimum cut of size $m$ - a partition $(C,C')$ of the vertices in the graph, such that $s\in C$, $t\in C'$, and the sum of capacities of edges directed from $C$ to $C'$ is $m$.

This cut cannot cross any edge of $E$, since these edges have infinite capacity. Hence, the cut size is determined by edges from $s$ to $X\cap C'$ and from $Y\cap C$ to $t$. So $m = |X\cap C'| + |Y\cap C| = (n-|X\cap C|)+|Y\cap C|$. Hence: $|X\cap C| = |Y\cap C| + (n-m) > |Y\cap C|$. Since the cut cannot cross edges of $E$, all neighbors of $|X\cap C|$ must be in $|Y\cap C|$, so $|X\cap C|$ is the desired Hall-violator.

I would use a degenerated version of the Hungarian algorithm (O(n^3)).

In the basic version on a U, V bipartite graph, you loop on the elements of x of U to give them the best assignement y from V. if y is already assigned, you make a growing subset X of U that may change their affectation without regret until:

either X has at least |X| neighboors in V => then you move your assignements to add properly x.
either X cannot grow anymore without regret and you accept to modify the weights (as the regret cannot be prevented).

For your problem, there is no weight. So if you are in the second case, just break off and you have your X subset. Else you will reach the last x of U and have a perfect assignement.


Is distinguishing Hadamard matrices _really_ NP-hard? In a few different places ( http://www.ams.org/journals/mcom/2004-73-246/S0025-5718-03-01539-4/S0025-5718-03-01539-4.pdf and https://books.google.com/books?id=qYYKBwAAQBAJ&pg=PA21&lpg=PA21&dq=np-hard+completing+hadamard+matrix&source=bl&ots=8sKv9bAtc8&sig=ITZSmtD2p2xr6Q4RDqhbQQk0NDI&hl=en&sa=X&ved=2ahUKEwiotuLdvfzdAhWBKHwKHUF9AO0Q6AEwB3oECAMQAQ#v=onepage&q=np-hard%20completing%20hadamard%20matrix&f=false, to give two ) it is claimed that determining the "equivalence" of two Hadamard matrices (in the sense of allowing sign-flips and permutations on rows and columns) is NP-hard. No source I found for this statement provided a citation, and I couldn't find any paper claiming to prove this.

On the other hand, https://core.ac.uk/download/pdf/82725146.pdf provides an $n^{O(\log n)}$ algorithm for identifying equivalent Hadamard matrices. This is somewhat to be expected, since Hadamard matrix equivalence is a lot like graph isomorphism. (It's also not hard to reformulate Hadamard matrix equivalence as a GI problem on $O(n^2)$ vertices directly, leading to a quasipolynomial solution under a variety of well-studied GI algorithms.)

If both of these claims were true, of course, this would be big news and violate the ETH. Is the claim of NP-hardness just a (false) folk theorem?

Both sources you cite are from the same author. Note the full quote:

  For identifying the equivalence of two Hadamard matrices of order $n$, a complete search compares $(2^n n!)^2$ pairs of matrices and is known to be an NP-hard problem when $n$ increases.

I don't think the author knows what NP-hard entails and confuses it with simply exponential. Further evidence of this is that he states that a complete search (an algorithm) is NP-hard, when that is a property of a problem, not an approach or algorithm.

This source from a different author similarly misuses the term NP-hard:

  The classification of Hadamard matrices of orders $n \geq 32$ is still remains [sic] an open and difficult problem since an algorithmic approach of an exhaustive search is an NP hard problem.

In fact the wording is very similar and found in a field study. It would surprise me if the source of this error wasn't the original paper(s) above being copied without thought.

Since these authors consistently seem to misunderstand the meaning of NP-hard, I think their claims (that come without proof or reference) can be safely dismissed.


Does the Halting Problem have practical relevance? I can calculate all outputs for a finite number of states and inputs Coming from a digital functional hardware verification background, I don’t really understand the Halting Problem. I can represent the program as a state machine and show whether all inputs in all states generate a valid output or lead to an infinite loop.

The only requirement is that the inputs and states are finite. E.g. an infinite counter would lead to an infinite number of states.

Since infinite counters or infinite inputs are impossible in reality, does the Halting Problem really have a practical relevance?

Indeed, if states and inputs are finite (and the tape is finite, which is quite reasonable), then you can easily reduce the Turing machine to a Finite State Machine. However, this is completely impractical, since it doesn't yield any reasonably effective algorithms. I.e. your solution for the halting problem will be to explode the states of the TM with all possible input combinations of size N, and then find a path that reaches a stop state, right? Probably don't want to implement such a check in your compiler.


Proving NP hardness of maximum sum of means of a partition into k sets I am trying to show the following problem is NP-hard and would like some help.

Inputs: Integer $k$, and unordered set of $N$ numbers, $O$
Output: the $\max \sum\limits_{S_i \in S} \operatorname{mean}(S_i)$
where $S=\{S_1,S_2,...,S_k\}$, $O=S_1 \cup S_2 \cup \dots \cup S_k$ and elements of $S$ are disjoint.

In simpler terms, partition $O$ into $k$ sets to maximize the total sum of the means of the sets.
This problem is a special case of a graph partition problem I am trying to prove NP-hard. I suspect even this special case that removes the graph structure is NP-hard and might be easier to prove. I have tried to reduce from the partition problem (minimize difference of sum of 2 sets).

Put each of the $k-1$ greatest numbers in their own set, and the remaining numbers all together in the $k$th set. This linear-time algorithm can be proved correct by using the following (non-strictly) improving moves to reach the specified optimal solution from any other.

Given two numbers $a<b$ with $a\in S_i$ and $b\in S_j$ and $\lvert S_i\rvert\le\lvert S_j\rvert$, swap $a$ and $b$.
Given $S_i,S_j$ where $|S_i|\ne 1$ and where all of the numbers in $S_i$ are greater than or equal to all of the numbers in $S_j$, move the smallest number in $S_i$ to $S_j$. (This move does not decrease the average of $S_i$, and does not decrease the average of $S_j$.)

An alternative correctness proof uses a linear relaxation. Let the numbers be $a_1\ge\cdots\ge a_n$ and consider the following linear program.

\begin{align}
&\text{maximize }\sum_{i=1}^na_ix_i\\
&\text{subject to}\\
&\sum_{i=1}^nx_i=k&(w)\\
&\forall i\in\{1,\ldots,n\},\quad-x_i\le\frac{-1}{n-(k-1)}&(y_i)\\
&\forall i\in\{1,\ldots,n\},\quad x_i\le1&(z_i)
\end{align}

Given a partition, for all $i\in\{1,\ldots,n\}$, we can set $x_i=1/\lvert S_j\rvert$, where $a_i\in S_j$. It follows that this program is in fact a relaxation. The proposed partition sets $x_1,\ldots,x_{k-1}=1$ and $x_k,\ldots,x_n=1/(n-(k-1))$.

Here is the dual program. By weak duality, feasible solutions of this program upperbound the objective value of the primal.

\begin{align}
&\text{minimize }kw+\sum_{i=1}^n\left(\frac{-y_i}{n-(k-1)}+z_i\right)\\
&\text{subject to}\\
&\forall i\in\{1,\ldots,n\},\quad w-y_i+z_i=a_i&(x_i)\\
&\forall i\in\{1,\ldots,n\},\quad y_i,z_i\ge0\\
\end{align}

Here is a feasible solution to the dual program whose objective value is equal to the previously proposed primal solution. It follows that both solutions are optimal.

\begin{align}
w&=a_k\\
y_i&=\begin{cases}a_k-a_i&\text{if }i\in\{k,\ldots,n\}\\0&\text{otherwise}\end{cases}\\
z_i&=\begin{cases}a_i-a_k&\text{if }i\in\{1,\:\ldots,\:k-1\}\\0&\text{otherwise}\end{cases}
\end{align}


What are the current state of art approximation algorithm for NP-Hard problems? I came cross some works try to use deep learning to approximate NP-Hard

https://arxiv.org/pdf/1810.10659.pdf

Though the paper seems to have very good results but based on the citations. I'm quit doubt if it really the state of art approximation for NP-hard problem.

I'm wondering what are some state of art NP-Hard approximation algorithms for each problems ?

First, there are two aspects to separate here: theoretical approximation and practical approximation (i.e., heuristics). With heuristics, such as in the NIPS paper you mention, the goal is roughly to propose some method, take a large bunch of actual instances of a problem, benchmark empirically the method, and draw conclusions as to how well we did in terms of approximation.

This is in contrast to (theoretical) approximation algorithms that give a formal guarantee on solution quality, on all possible instances. For example, the guarantee could be "the solution returned by this algorithm is either optimal or at most three less than the optimal". But as you might know, there is an enormous amount of hard problems that can be wildly different in terms of approximation. Maximum clique or chromatic number, for instance, are very hard to approximate theoretically.


Plain-language example of how a functional style makes parallel programming easier I read a few "function >> imperative/OOP" articles because I heard there was a move in imperative OOP languages toward a functional style of coding, especially encouraging pure functions when possible. One recurring argument is that by not mutating state, you don't have to worry about race conditions and locking.
I do get the logic behind that: no two processes would mutate the same data, so locking and race conditions are irrelevant. Problem is I hadn't done any parallel programming or know any functional languages, so it's hard for me to really understand. I got as far as reading about persistent data structures as replacements for large mutable structures, but I hit a wall. I'm looking for an example, in plain language, of a parallel algorithm in an imperative style and a functional style that illustrates this recurring argument.
If it helps to provide a programming problem, let's say I have an array of integers (A). People submit commands (A[i] += 1) in real time to increment an element of that array by 1 (at a valid index i). Different elements are intended to be incremented in parallel. I can imagine the imperative solution does this but it locks an index during an increment. What would a functional solution look like? I will accept answers as simple as naming a functional data structure, if I could understand it by looking it up.

I'm not sure functional programming does make parallel programming any easier, when taken in the round.
If you program in a "functional style" (including all so-called good practices), then converting certain steps of a serial program to parallel execution (and getting results that are equivalent to the serial execution) may not usually involve much further difficulty, but that is primarily because all the difficulty has already been imposed in drafting the program in a form where it doesn't matter whether many steps are executed serially or in parallel.
Moreover, functional programming does not claim to guarantee that a serialised execution of a program actually produces "correct" (i.e. intended) results for all inputs, only that parallelised execution will involve no additional error.
In general, business systems have an irreducible need to mutate state and shared data, so any benefit or guarantee that depends in theory on not mutating state at all, can be dismissed out of hand as almost worthless to real-world development.
If the point at which state is mutated is seen as a boundary across which the guarantees of functional programming cease to apply, then the vast majority of programs can get almost nothing done before having to cross a boundary and step outside such guarantees.
Many people seem to over-estimate how much error actually occurs in systems due to race conditions etc. involving unnecessary mutations, rather than errors which involve the necessary mutations of shared data that must occur equally in functional programs as in non-functional ones.
Arguably, a real benefit of functional programming is that it allows certain kinds of functionality (especially complex calculations) to be implemented more quickly or to a more complex extent, at the price of a higher initial learning curve.
In other words, it will allow the best programmers to work a little faster once experienced, or get a little further than before with the most complex systems, at the expense of requiring far more training and experience to begin with, and excluding third-rate programmers from getting anywhere at all.
This, however, is not the typical understanding people have of the word "easier", or of a tool that "makes things easy". I contend that functional programming may improve productivity in some cases, but it does so by increasing the threshold of difficulty in many respects.


Binary code and Hamming distance I'm learning about CRC and Hamming distance and I have three questions.
Lets say we have binary code described by ($+$ refers to sum modulo $2$):

\begin{alignat*}{1}
a_1 &+ a_2 &+ a_3 &+ a_4 &+ a_5 &= 0\\
a_6 &+ a_7 &+ a_8 &+ a_9 &+ a_{10} &= 0\\
a_1 &+ a_6 &+ a_{11} &&&= 0\\
a_2 &+ a_7 &+ a_{12} &&&= 0\\
a_3 &+ a_8 &+ a_{13} &&&= 0\\
a_4 &+ a_9 &+ a_{14} &&&= 0\\
a_5 &+ a_{10} &+ a_{15} &&&= 0
\end{alignat*}
We received: $11011\ 01010\ 10111$

So if I would like to check minimal Hamming distance, then I should compare each codeword with others, right?

$\begin{pmatrix}
1&1&1&1&1& & & & & & & & & & \\
 & & & & &1&1&1&1&1& & & & & \\
1& & & & &1& & & & &1& & & & \\
 &1& & & & &1& & & & &1& & & \\
 & &1& & & & &1& & & & &1& & \\
 & & &1& & & & &1& & & & &1& \\
 & & & &1& & & & &1& & & & &1\\
\end{pmatrix}$

I have done so, and minimal Hamming distance $ = 6$. Is there any faster method?

Second question: how many distortions causing undetectable errors? Is there any formula for that?
And last one, how to compute redundancy using above information. I'm using formula: $ R = \dfrac{n-k}{n}$. In above example $n=15$, but I don't understand how to obtain $k$.

In a linear code, the minimum distance is the same as the minimum weight of a non-zero codeword. It's a nice exercise to prove this, and reduces the computation time quadratically.

Computing the minimum distance of a code given the generator matrix (or the parity check matrix) is NP-hard, that is, given a generator matrix (or a parity check matrix) and an integer $w$, it is NP-complete to determine whether the minimum distance of the code generated by the matrix is at most $w$. The task could become easier if the code has some structure, but for arbitrary codes it is quite difficult.


how to generate/read a glyph in ocr? I have been practicing with some Machine Learning algorithms for OCR, but I have a doubt about the glyph concept. For example in the UCI repository:

https://archive.ics.uci.edu/ml/machine-learning-databases/letter-recognition/letter-recognition.names

where it says:

4. Relevant Information:

   The objective is to identify each of a large number of black-and-white
   rectangular pixel displays as one of the 26 capital letters in the English
   alphabet.  The character images were based on 20 different fonts and each
   letter within these 20 fonts was randomly distorted to produce a file of
   20,000 unique stimuli.  Each stimulus was converted into 16 primitive
   numerical attributes (statistical moments and edge counts) which were then
   scaled to fit into a range of integer values from 0 through 15.  We
   typically train on the first 16000 items and then use the resulting model
   to predict the letter category for the remaining 4000.  See the article
   cited above for more details.

and when I see the file letterdata.csv I find something like this:

"letter","xbox","ybox","width","height","onpix","xbar","ybar","x2bar","y2bar","xybar","x2ybar","xy2bar","xedge","xedgey","yedge","yedgex"
"T",2,8,3,5,1,8,13,0,6,6,10,8,0,8,0,8

So for what I have read this first line refers to the character T that has certain values according to the attributes:

7. Attribute Information:
     1. lettr   capital letter  (26 values from A to Z)
     2. x-box   horizontal position of box  (integer)
     3. y-box   vertical position of box    (integer)
     4. width   width of box            (integer)
     5. high    height of box           (integer)
     6. onpix   total # on pixels       (integer)
     7. x-bar   mean x of on pixels in box  (integer)
     8. y-bar   mean y of on pixels in box  (integer)
     9. x2bar   mean x variance         (integer)
    10. y2bar   mean y variance         (integer)
    11. xybar   mean x y correlation        (integer)
    12. x2ybr   mean of x * x * y       (integer)
    13. xy2br   mean of x * y * y       (integer)
    14. x-ege   mean edge count left to right   (integer)
    15. xegvy   correlation of x-ege with y (integer)
    16. y-ege   mean edge count bottom to top   (integer)
    17. yegvx   correlation of y-ege with x (integer)

while some attributes are easy to understand, but I have a problem to visualice this in my head; I mean a glyph it is not like a grid in which a handwritten character is put on? something like this:

]

but where is the individual pixel data on the dataset letterdata.csv that I mentioned at the beginning of the question?
Also and for not opening another question thread, how these glyphs are generated and if there is a glyph reader in which I can put the data like: "T",2,8,3,5,1,8,13,0,6,6,10,8,0,8,0,8
and I can visualize the corresponding letter.
Any help?

This is addressed in the relevant information you quoted, specifically in the following sentence:

  Each stimulus was converted into 16 primitive numerical attributes (statistical moments and edge counts) which were then scaled to fit into a range of integer values from 0 through 15.

Many machine learning algorithms won't be successful with the raw raster data, instead requiring features such as the 16 "primitive numerical attributes" mentioned above. (Deep learning algorithms should work correctly with the raster data, though.)

Computing these numerical attributed is a one-way process: you cannot recover the glyph from its statistics. We compute these statistics since we think they are the salient features which distinguish one letter from another.


Recommended readings for Probability theory applied to algorithms Currently, I'm delving into Analysis of Algorithms and I've discovered that I would need to improve my knowledge of Probability Theory. Any recommendation? Where do I start?
Thanks in advance!

I highly recommend Mitzenmacher and Upfal, Probability and Computing.

It has almost all the background needed for a beginning graduate student to start in probabilistic algorithms and analysis, and is clearly written, nice examples, etc.


Number of phrases of LZ compression It is known that for the number $c(n)$ of phrases / tupel of the LZ compression for binary words of length $n$ the following relation holds:
$$c(n)\leq\frac{n}{(1-\epsilon_n)\log_2 n}$$
With $\epsilon_n\to 0$ for $n\to\infty$.

The proof is made in Thomas & Cover: Elements of Information Theory (Lemma 12.10.1, page 320 in the linked chapter).

I tried to generalize it to an alphabet of size $k$ by adjust the proof step by step, but I failed. So, my question:

How can I prove that the number $c(n)$ of phrases / tupel of the LZ compression is bounded by
$$c(n)\leq\frac{n}{(1-\epsilon_n)\log_k n}$$
for all words of length $n$ over an alphabet of size $k$ with $\epsilon_n\to0$ for $n\to\infty\;?$

You don't need to redo the proof for this, simply note that $n$ symbols of an alphabet of size $k$ can be represented with $n \log_2(k)$ bits.  The Lempel-Ziv bound is then:

$\mbox{# phrases} \leq \frac{n log_2 k}{(1-\epsilon_{n \lg k})log_2(n \log_2 k)}$

Dividing numerator and denominator by $\log_2 k$ then gives:

$\mbox{# phrases} \leq \frac{n}{(1-\epsilon_{n \lg k})\left(log_k(n) + \log_2(\log_2(k))/log_2(k)\right)}$

Since $\epsilon_n \longrightarrow 0$ as $n \longrightarrow \infty$, the result follows.


Which instruction yields atomicity in this expression that makes the result 2? I am reading about atomicity and came across the following scenario

int x = y = z = 0;

Thread 1        Thread 2
---------       --------
x = y + z       y = 1
                z = 2

Which gives the following sets of output

$$\begin{array}{ccc}1&2&3\\
T1 : x = y + z&T2 : y = 1&T2 : y = 1\\T2 : y = 1&T2 : z = 2&T1 : x = y + z\\T2 : z = 2&T1 : x = y + z&T2 : z = 2\end{array}$$

Translating the $x=y+z$ expression to machine code gives

load r1; y
load r2; z
add r3; r1; r2
store r3;

However according to some notes I read going down the path of

T1 : load r1, y
T2 : y = 1
     z = 2
T1 : load r2, z
     add r3, r1, r
     store r3, x

I cannot seem to understand how the author came to result that $x=2$.

To me, based on the previous machine instructions the result should be 3, which I guess leads me to realize I am supposed to hit eureka (or a simple misread) and realize where the atomicity occurs. Could you explain the atomicity in this fairly simple statement that leads to the correct result?

The point you are missing is that in thread $y$ is loaded into $r1$ and that any subsequent changes to $y$ will not affect the value stored in $r1$. Thus, the value in $r1$ is $0$ even after statement $y=1$. From this it is easy to see that the result is $x=2$.


Algorithm to find the closest possible value among several combinations I have the following problem and would like an orientation on which algorithms I can try to adapt to solve it in the best possible way.
SCENARIO
A company has a warehouse where it stores several products. A product can be stored in several packages, for example:

1 box with 10 units
1 box with 3 boxes of 10 units
1 box with 30 units
1 box with 5 boxes of 30 units

Eventually these products need to be dispatched for consumption in the company's stores. Each store makes its own request for products according to their needs.
However, such requests do not take into account the available packaging, ie the quantity requested may or may not coincide with the quantity of a particular packaging.
Example:

1 box with 8 lunits
2 boxes with 2 units
1 box with 4 units
1 box with 6 units

The store could request 13 units of product, and thus there would be no packaging combination that could total exactly 13 units.
However, there would be the following options to meet the store order:

1 box of 8 units and 1 box of 4 units (total: 12)

1 box of 8 units and 2 boxes of 2 units (total: 12)

1 box of 8 units and 1 box of 6 units (total: 14)

1 box of 8 units, 1 box of 4 units and 1 box of 2 units (total: 14)

In a scenario like this I need an algorithm that might find the packaging combination to be closer to the exact value.
In the real scenario, there are dozens of possible combinations, where I need to find 3 possible combinations:

The combination that meets the exact requested quantity (requested: 20, combination: 20)
The combination that gets as close as possible through a lower value than requested (requested: 20, closest combination: 18)
The combination that answers as close as possible through a value greater than requested (requested: 20, closest combination: 23)

Is there an algorithm already known that can fit well into this scenario where I can just adapt to my context?

This is a common problem so there certainly exist many approaches to solve it. Below I'll sketch such an approach. It probably has a name but I don't know it:

The approach essentially sets up an array of target order sizes with an array length of actual order size + largest available package size. In each array element we store the ID of the package that can be used to increase the overall combined package size from a known solution for some smaller order size to get to the order size related to the index of the array. When we filled up the array we can go back from a realizable solution to an order size of 0 by collecting all the packages that lead to the respective solution. So this will be some kind of a dynamic programming approach.

We start at an order size of 0, go through all available packages and set the array index given by the respective package size to the ID of the package. Now we repeatedly increase the order size by 1 up to the target order size and for each order size we do the following:

If there is an ID of a package in the respective array element we again go through all available packages and store their ID in the array element "order size + package size" if that array element does not yet contain an ID. Otherwise we do nothing and just go on.

When we filled up the array in this way we can search in the neighborhood of the target order size for the array element that best fulfills our needs and also contains a package ID. From there we add the stored package ID to our solution and go back in the array by the size of that package. We do this repeatedly until we are back at a test order size of 0.

Of course, the solution we obtained in this way is not necessarily unique. We can prioritize certain packages by the order in which we process them when filling up the array.


Proving that converting min-heaps to max-heaps requires time Ω(n) Suppose I have a min-heap SH stored inside an array. I can perform the operations:

view-min(SH) in $O(1)$
extract-min(SH) in $O(\log n)$
insert(SH) in $O(\log n)$
is-empty(SH) in $O(1)$

If I want to build a max-heap BH from the first one, the naive algorithm I can implement is obviously

BH <- build-heap()
while not is-empty(SH) do             O(n)
    elem <- extract-min(SH)           -> O(logn)
    insert(BH, elem)                  -> O(logn)
done

whose complexity is obvously $O(n \log n)$ worst case. Is this the best algorithm or there is any algorithm whose complexity is lower? Yes

According to Wikipedia we can at least achieve $O(n)$. Without making any assumption about our array being an heap. Can we use this fact to achieve $O(\log n)$ complexity? No

It should be impossible, because we have to deal with any of the $n$ items at least one time. Does this prove that the conversion is $\Theta(n)$?

You could argue that the level-hierarchy gives more information, but not by much. Assuming a full max-heap of distinct values the $min$ element is on the deepest level of $\frac{n+1}{2}$ nodes. Unless there is some additional ordering to the heap, it would then take $\Omega(n)$ just to find the $min$ element.


Can current quantum computers decide languages that Turing Machines cannot? I am currently learning Computing Theory at university, and we were on the topic of Turing-Decidability, Recognizability, etc. Showing that a problem is undecidable with Turing machines due to reductions got me thinking about all the Quantum Computer craze.

As such my question is as follows

  Does there exist some language L that is not decidable by a Turing Machine, but is decidable by a quantum computer?

My hunch is no, as from what I understand about Quantum Computers, you can simulate them (albeit slower) using a Turing Machine. However my knowledge of Quantum Computing is limited to a 1.5 hour lecture from Microsoft on YouTube, and I would assume there was a lot more in the way of recent developments that I am not knowledgeable enough to understand

No. A state of $n$ qubits can be represented with a vector of size $2^n$, and quantum gates can be implemented as linear operations for those vectors. Therefore a quantum computer can be simulated with a Turing machine, although with an exponential overhead. It is also known that the class of problems solvable by a quantum computer in polynomial time, BQP, is contained in the class of problems solvable by a classical computer in polynomial space, PSPACE.

All this information is from the Wikipedia page https://en.wikipedia.org/wiki/Quantum_computing


Is there any base representation that produces a non-regular language for set S? To clarify, by base representation I mean binary representation (ie. 101 = 5), ternary representation, etc.

Given the set $S$ of natural numbers such that $S = \{2^i| i \in \mathbb{N}\}$ prove that for some base representation of set $S$, the resulting language is not regular.

I have tried but I can't seem to figure out how to prove this. I figure that base 3 would probably result in a nonregular language, but then how would I prove it?

You are right in saying that the binary representation of the language is regular because it is defined by the expression $10^*$(regular expression).
You are also right in saying that this does not hold for the ternary representation.
You can prove the latter in various ways including the "calssic" pumping lemma (quite cumbersome in this case) or using Cobham's Theorem.

This theorem says that if you have a subset of $\mathbb{N}$ and you take $m,n \in \mathbb{N} $ such that they are multiplicatively independent, then your set is recognizable by finite automata in both $m$-ary and $n$-ary notation if and only if it is ultimately periodic.


call by value: what is a value? In the 'call by value' evaluation of lambda-calculus, I am bit confused with  'value'.

On page 57 of the book Types and Programming languages, it is said:

  The definition of call by value, in which only outermost redexes are reduced and where a redex is reduced only when its right-hand side has already been reduced to a value - a term that is finished computing and cannot be reduced any further.

So by that definition, a term λx.x is a value, but a term λx.((λy.y)x) is not a value since it can be reduced further.

But in an example of 'call by value' on the same page, reduction as the following. (id is the identity function λx.x)

id (id (λz.id z))
   --------------
id (λz.id z)
------------
λz.id z

But in this example neither

  (id (λz.id z))

is a value, nor

  (λz.id z)

a value.

Isn't contradictions here? or I am misunderstanding something?

Can anyone clarify these to me?

Thanks in advance!

The set of values is defined for a particular reduction relation. Each reduction relation defines its own set of values.

Reduction for the lambda calculus isn't just beta reduction, there are also context rules. There are several common notions of reduction for the lambda calculus, with different sets of context rules.

In the full lambda calculus, any lambda term with a hole is a context: the context rules are
$$
\frac{M \to M'}{M\,N \to M'\,N} \qquad
\frac{N \to N'}{M\,N \to M\,N'} \qquad
\frac{M \to M'}{\lambda x.M \to \lambda x.M'}
$$
This doesn't mimic what most programming languages do. Most programming languages don't start evaluating a function's body before the function receives its arguments (this becomes especially important when evaluating the function body causes side effects). This translates into omitting the third rule above altogether: there is no reduction under a lambda. The reduction relation without that context rule is known as weak head reduction. For weak head reduction, $\lambda x. M$ is a value for any term $M$: even if $M$ could be reduced, $\lambda x. M$ can't.

Call-by-value and call-by-name are refinements of weak head reduction which also restrict the form of terms that rules can be applied to: the first two rules above, and the beta rule, have constraints on the form of $M$ or $N$.

As far as I recall, TAPL focuses on applications of the lambda calculus to programming and so focuses on weak head reduction. (λz.id z) is a value. (id (λz.id z)) isn't a value, which is why the first step reduces it (the first step is id M → id M' where M → M': it's the id in the argument that reduces, not the outer id).


Time Complexity $\Theta$ vs. $\Omega$ If an algorithm has running time of $\Theta(n^2)$, is it possible to have a best-case running time of $\Omega(n)$? Or is the fastest running time only $c n^2$ for some constant factor $c$?

There are two possible interpretations for "running time of an algorithm". The first interpretation is the worst-case running time, depending on some parameters such as the input length $n$. The second interpretation is that the running time is some bound that holds for all inputs with the given parameters. When we give a big $O$ estimate, both interpretations amount to the same thing: if an algorithm has a running time of $O(n^2)$, then this is both a worst-case bound and a bound which is valid for all inputs of length $n$.

What is then the interpretation of $\Theta(n^2)$ in your case? It's hard to say without more details, and could depend on the context. If it's a worst-case bound then the meaning is "there is a family of inputs for which the algorithm runs in $\Omega(n^2)$ time". If it's a global bound then the meaning is "the algorithm runs in $\Omega(n^2)$ time on all inputs". Out of these two possible interpretations, the first seems slightly more likely, but others may hold different opinions.


Encoding a list of numbers using gamma coding I'm trying to work out how to find the gamma $\gamma -code$ that encodes the postings list (12, 18, 21, 22).

Is the postings list encoded just by a list of the individual $\gamma$-codes for each integer? E.g. for 12 the gamma code is: 0001100, and so the first entry in the $\gamma$-code for the pointing list is just 0001100. Or is there another representation - am I thinking along the right lines?

Thanks in advance for any help!

I'm assuming that you're referring to the Elias gamma code. This code is a prefix code, also known as a self-terminating code. This means that you can encode a sequence of numbers by simply concatenating the encodings of the individual numbers. Since the code is self-terminating, the concatenated encoding can be decoded into the encodings of the individual numbers.

A prefix code is a code in which no codeword is a prefix of another codeword. This allows you to decode the list as follows. Read bits until you reach a prefix of the encoding which constitutes a codeword. This encodes the first number. Remove and repeat.

Finally, let me stress that the Elias gamma code is a way of encoding numbers using a string of bits. When you write 0001100, you should think of it as a string of 7 bits. Eventually these bits will be decomposed into 8-bit chunks (knows as bytes) and stored or communicated in this way – as a string of bytes.


$k$-way merge but without an absolute order I have $k$ lists that I would like to combine to a single list. Each list's elements are unique and are sorted in a particular order, but there is no notion of an absolute order, and different items across lists can only be compared if they are equal. To give a specific example (here I use $<$ to indicate the sorting inside each list):

l1 = a < b < c
l2 = b < d

l1 + l2 should result in one of the following (and I don't care which one it results in):

a < b < c < d
a < b < d < c

If the lists are incompatible, e.g. a < b and b < a then I want to get an error. The resulting list (if it exists) should respect all of the orderings of the sublists. Also all the items should be unique in the result.

I thought about modifying k-way merge somehow but it's not clear to me how to do that without a global order. By the way, I'll probably be happy with a $O(nk)$ solution.

Perhaps a better way to phrase the problem is this. I'd like to construct an order vector given $k$ pieces of that order vector (or get an error if that's impossible).

Here's an algorithm that I think works for $k=2$. Find and mark all the duplicates - I think this is $O(n)$ - then start writing down elements from first list until you hit a duplicate, once you do add all elements from second list until you hit that same duplicate, then write down the duplicate and continue. The part where it's a bit more tricky with $k>2$ is that the duplicate may not be in every list to do the above (and this process cannot be done sequentially, i.e. l1+l2+l3 is generally not the same as (l1+l2)+l3, where + denotes this operation of finding the superset order list).

It should be easy to extend the above to any $k$. Use a hash to find which lists each unique element belongs to. Then traverse along the first list using the above logic - writing down all elements until you hit first duplicate, in which case write down all elements (that haven't been written down yet) in all other lists before that duplicate and keep doing that until you reach the end of first list. If haven't reached the end of second list, continue same algorithm there and so on. Each list will be traversed twice - once to get the duplicates, and second time to do the above, making it $O(n)$. A compatibility error will be discovered if you iterate along a list but can't find the duplicate (because it was already written down in an earlier pass).

Edit: You recently revised the question to clarify that you are allowed to hash items.  That changes the question: it lets us build much more efficient algorithms.

With this change, your question becomes: given $k$ partial orders, find a total order that is consistent with all of the $k$ partial orders.  This problem can be solved in linear time, i.e., in $O(n)$ time, where $n$ is the total number of items across all of the sublists.

Here's how to solve it.  We'll build a directed graph, where each item (in any sublist) is a vertex is the graph.  Traverse the sublists to extract all consecutive pairs of items that appear in any sublist.  If you have a < b in a sublist (i.e., item a immediately precedes b in some sublist), add an edge $a \to b$ to the graph.  (Notice that you can have a hashtable that maps the item a to the corresponding vertex $a$ in the graph, so this operation involves two lookups in the hashtable and then adding an edge: $O(1)$ time.)

Once you've built the entire graph, topologically sort it, and output the vertices in topologically sorted order.  That will be a valid output list that solves your problem.  If the topological sort fails and reports that the graph has a cycle, then your sublists are inconsistent and you should output an error.

This solves your problem in linear time, i.e., $O(n)$ time.

My original answer to your original question:
You don't list any requirements on what order the combined list elements must appear in.  Therefore, concatenating/interleaving all of the list items in an arbitrary order appears to meet all of the explicitly stated requirements.  If that's not an acceptable solution, you'll need to think through your requirements more carefully and then edit your question to state the requirements explicitly.

I suspect you meant to require that the elements in the combined list must appear in an order that is consistent with the order in each sublist, and any item should appear only once in the combined list.  If that's what you meant, then you can't do better than $O(n^2)$ time, where $n$ is the total number of items across all of the sublists: there's no way to avoid comparing each item of each sublist with each other.  (If there is any pair of items which you have not compared explicitly, you have no way of knowing whether they are equal or not: both are possible.)

It's easy to achieve an $O(n^2)$-time algorithm.  You simply compare each item to all other items, to first find all duplicated items (items that appear in more than one sublist).  Then, you do a straightforward $k$-way merge.  At each step of the $k$-way merge, you look at the head of each of the $k$ sublists and classify each of those $k$ items as duplicated or not.  If any of them are non-duplicated, you can remove it from the head of its sublist and append it to the combined list.  If one of them is duplicated, and all of its duplicates appear among these $k$ items, then you remove each of them from their corresponding sublists and append it to the combined list.  Repeat this until done.  If no items appears twice in any sublist, and if all of the sublists are sorted in a compatible way (e.g., you don't have a before b in one sublist but b before a in another sublist), then this process will never get stuck and will yield the desired output.

The running time of this algorithm is $O(n^2)$, and it's not possible to do better than that (assuming the only operation available on items is to test two items for equality), so this algorithm is optimal up to a constant factor.


The language of Turing machines that accept exactly $k$ inputs For a fixed $k\geq 0$, let $X_k = \{\langle M\rangle\mid |L(M)|=k\}$, where $\langle M\rangle$ is the encoding of a Turing machine $M$ and $L(M)$ is the language $M$ accepts.  Is $X_k$ recursive, recursively enumerable or neither?

I think $X_k$ is NOT recursively enumerable because even if you generate every possible string, and test each one, if you find $k$ strings that M accepts, you still have to check every other string (in case $M$ accepts more than $k$ strings), which means your machine will loop indefinitely, and never find a yes-instance. However I'm not sure how you would show this, initially I thought I could reduce the NHP (Not Halting Problem) to L but that didn't go too well. Any ideas?

Hint: to decide whether $M$ halts on input $w$, consider a new machine $M'$ that rejects every input except $w$ and simulates $M$, otherwise. That's not quite the answer but it should get you close enough.


How are faces of a DCEL updated when triangulating a polygon? In chapter 3 book how to triangulate a polygon is explained, however it doesn't seems to me that how to handle the faces are explained. My guess would to add two new face and erase the old one every time a diagonal is inserted (both while decomposing the polygon in monotone pieces, and during the actual triangulation). Is my guess correct?

Is there a smarter way to do that?

For the algorithm that triangulates a monotone polygon: every time you add a diagonal, you actually find a triangle. So, you can indeed explicitly relabel the face-value associated with all edges of that triangle. That does not affect the asymptotic running time.

For the algorithm that splits a simple polygon in to monotone polygons you cannot really afford that, as you may have to relabel an (half)edge multiple times. Hence, a solution there is just to be lazy: i.e. use the sweep just to update the vertex/edge fields in the DCEL, and ignore the face values. When you are done with the sweep: use the vertex/edge fields, in particular the next-fields on the half-edges, to walk around every face, and set the face values appropriately.


How to prove language $L=\{a^{i}b^{j} : i \leq j^{2}\}$ is not CFL using Pumping lemma? I'm trying to found a way how to prove this language is not context free. Using pumping lemma I'm halfway done. Consider word $a^{n^2}b^n$. If you divide it into $uvwxy$ and have only $a$'s in $v$ and $x$, you clearly get out of language when you pump up. If you do the same with $b$'s and pump down, you get out of language as well. But how dow do you show situation where there are only $a$'s in $v$ and just $b$'s in $x$?

Thank you

Suppose towards a contradiction that  $L$ is context-free and let $c$ be the pumping length of $L$.
Consider the word $a^{c^2} b^c$ which, by the pumping lemma, can be written as $uvwxy$ with $1 \le |vx| \le c$.

Notice that:

$vx$ cannot contain only $b$s, since otherwise $uwy \not\in L$.
$vx$ cannot contain only $a$s, since otherwise $uv^2wx^2y \not\in L$.
none of $v$ and $x$ contains both $a$s and $b$s, since otherwise $uv^2wx^2y \not\in L$.

We conclude that $v$ contains only $a$s, $x$ contains only $b$s, and $x$ contains at least one $b$. Then, by the pumping lemma, $a^{c^2-|v|} b^{c-|x|} = uwy \in L$. This is a contradiction since:
$$
(c  - |x|)^2 \le (c - 1)^2 = c^2 - 2c + 1 \le i^2 - c < i^2 - |v|.
$$


Where does the interrupt handler return to? Say the CPU is currently handling an interrupt. Another interrupt arrives but it's lower priority than the current one so it gets put in the 'pending interrupt register'. My current interrupt is done so I use a 'return from exception' instruction. Where will this instruction jump to: the address which was interrupted, and then to the interrupt handler or will it immediatly jump to the handler of the new interrupt that is in the 'pending interrupt register'?

What happens internally inside the processor could go either way depending on how the designers chose to implement it.  Either you are returning to the address that was interrupted, but it immediately gets interrupted again, in which case the next instruction that executes is the first instruction of the next handler, or you are jumping directory to the first instruction of the next handler.

In either case: the first instruction of the next handler will be executed before the instruction that was originally interrupted.  Anything else would be a priority inversion bug.


Shortest path that passes through specific node(s) I am trying to find an efficient solution to my problem. Let's assume that I have positive weighted graph G containing 100 nodes(each node is numbered) and it is an acyclic graph. So there cannot be any edge like 2,2 or 2,1. I have got a list of nodes let's say 10 from graph G. Let's say each of these nodes are also in an array. I am looking for a way to find the shortest path's total weight from node 1 to 100 that passes through at least some particular(let's say 5) of those nodes from that list.

To simplify it, consider graph with 6 nodes, 0...5, now node 1 and 4 are marked as points where we could specify to pass. Let's say existing paths are 0-1-2-5, 0-3-4-5, and 1-4. Now let's say all edges are weighted as 5 except 3 to 4 is weighted as 1. If we run a shortest path algorithm this would basically find the path 0-3-4-5 as it is weighted 11. However if we run an algorithm specifying minimum amount of specified points and try the amount 2. Then the algorithm should be running on 0-1-4-5 which is weighted as 15.

I have written this way

    shortestPath(destinationNode, minAmount)

        if(destinationNode == srcNode && minAmount < 1)
            return 0

        else if(destinationNode == srcNode && minAmount > 1)
            return INFINITY

        int destNo = destinationNode get number
        int cost = INFINITY
        for (int i = 0; i < destNo; i++)
            if (d[i][destNo] != null)
                int minimumAmountCount = minAmount;
                for (int j = 0; j < marked.length(); j++)
                    if (marked[j] == i)
                        minimumAmountCount = minimumAmountCount - 1;

                cost = MIN(cost, shortestPath(Node(i), minimumAmountCount);

        return cost;

Basically we call this algorithm by using the our destination node and minimum amount of nodes from that list. Firstly we want to make sure that this is a recursive function and it should have a stopping point, which would be when passed destination is equal to source node(which is essentially node #0). The second case we need to check is whether we visited enough amount, so if it is less than 1(0 or negative number) then we visited enough points and return 0 as distance from node #0 to node #0 would be 0. If we did not visit enough amount then we return infinity so that algorithm would consider other paths.

So in order for the returning part to work, we have to define the destination node's number(if we consider that we have 100 nodes it would be node #99 at the initial start) and initialise cost as infinity.

Then we run a for loop that starts from 0(essentially node #0) till our current node number, this is because there are no backwards edges on the graph. By using node number we check from the matrix whether there is an existing weight for those nodes. If it exist then we initialise a variable for our current minimum amount and then run a loop and check if source to the current destination is in the list of marked nodes. If it is marked then we simply decrement the minimum amount.

For the final step we run the function again by changing destination as the current source and with the current minimum amount.

But it seems very expensive, considering the fact that the worst case complexity of  nested loop takes O(|Node|^2) and total recurrence would take O(|Node|^2 * |Edges|). So is there any other efficient solution for this problem?

Compute the shortest path between all pairs of the twelve special nodes (nodes 1, 100, and all ten of your particular nodes), and use these as edge lengths in a new graph consisting only of these twelve nodes. Now, you have a graph containing twelve nodes, and you want to find the shortest path from 1 to 100 that uses at least five other nodes. Now, you can use your algorithm (which I think is just dynamic programming) on this graph, which is much smaller. The solution on the new graph will give a solution for the original graph, which you can find by replacing the edges in the solution in the new graph with the shortest paths you computed in the first step.

For your example, we will have 4 nodes in the new graph. The edge lengths in the new graph are: 0-1:5, 0-4:6, 0-5:11, 1-4:5, 1-5:10, 4-5:5. These correspond to the shortest paths between nodes $i$ and $j$ in the original graph. The shortest path including one node from the list is 0-4-5, which has length 11. Now, replacing each edge in this path with the path computed in the first step gives the path 0-3-4-5 in the original graph.


Difference between end carry and overflow I am confused with end carry and overflow. When will an end carry be the overflow? How to identify whether the end carry is overflow or not? Are they both same?

Sometimes end carries obtained are simply discarded and sometimes the end carries are considered as overflows. What is the exact method to find an overflow?

In the case of unsigned numbers, if the addition causes end carry, then the end carry should not be discarded because it is the part of result number. In this case, is the end carry an overflow? In the case of signed numbers, if the addition causes end carry, then the end carry represents sign bit. In this case is the end carry an overflow?

I'm assuming we are talking about Two's Complement integers (positive and negative of course).  You need to first understand the boundaries:

The largest positive value is:

$$
2^{n - 1} - 1 = 0111\ 1111\ 1111\ ...
$$

The "largest" negative (most negative value) occurs at:

$$
-2^{n - 1} = 1000\ 0000\ 0000\ ...
$$

Adding any positive value to $2^{n - 1} - 1$ will result in an overflow!  Likewise adding any negative value to $-2^{n - 1}$ will also result in an overflow (or perhaps more precisely and underflow--but that has a different meaning when it comes to floating point values).

It should be clear that adding anything "above" $1000\ 0000\ 0000\ ...$ ($-2^{n - 1}$) to $0111\ 1111\ 1111\ ...$ ($2^{n - 1} - 1$) will result in a carry!  Yet by the above we know that adding any of these values $\geq 1000\ 0000\ 0000\ ...$ will simply be subtracting a value that results in a valid (possibly negative if it's $-1$) result.  On the contrary, if we attempt to add a positive value such that the first digit is $0$, then we get no carry and yet we get overflow.

When we try to add two negatives ($1...$ and $1...$) we are bound to have a carry but this always results in $1\ 0000\ 0000\ ...$ added to some two's complement value.

The algorithm for determining overflow is very simple: if you add two positive numbers then you should get a positive and if you add two negative numbers then you should get a negative (and if you add a positive and a negative, you will never get the "wrong" result).

I don't know if that helps or not because I'm not too sure what you mean by "end carry".


Algorithm that deside if there are two words $x$ and $y$ in the same length such that $x\in L(A_1)$ and $y\in L(A_2)$ Let $A_1=(Q,\Sigma,q_0,F_1,\delta _1)$ and $A_2=(P,\Sigma ,p_0,F_2,\delta _2)$ a finite non determinustic automaons.

  Describe algorithm that deside if there are two words $x$ and $y$ in the same length such that $x\in L(A_1)$ and $y\in L(A_2)$

Hint: Intersection automaton

My try

To bulid the intersection automaton $L_1\cap L_2$ and check if $L_1\cap L_2 \neq \varnothing$ with $"\color{blue}{\text{emptiness problem algorithm} }"$  and if $L_1\cap L_2 \neq \varnothing$ so $\exists $ word $w$ such that $w \in \mathscr L(L_1\cap L_2)$

Consider the NFA $A_1=(Q,\Sigma,q_0,F_1,\delta_1)$. Observe that an accepting run of $A_1$ induces an accepted word. That is, we don't really care about the alphabet of the automaton if we only want to consider word length.

Thus, instead of constructing the intersection automaton directly, first change the alphabet of both automata to be $\Sigma=\{a\}$, by changing the letters in all the transitions to $a$. That is, for a transition $\delta_1(q,\sigma)=q'$, change the transition to $\delta(q,a)=q'$.

Now construct the product automaton, and check emptiness.

I'm leaving the correctness proof as an exercise.


NP-hardness of finding a subset of vertices in a vertex-weighted graph This is task from the German IT contest ("Bundeswettbewerb Informatik"), but since the deadline is past, asking this question is no cheating.

Given a vertex-weighted, directed graph $G=(V, E)$ and values $c_v$, find a subset of nodes $V_{res}\subseteq V$ that maximizes $$\sum_{v \in V_{res}} c_v$$ subject to $$\forall (u,v) \in E: u \in V_{res} \implies v \in V_{res}$$
Is this problem NP-hard?

I could prove that the problem is in P if every node has either no parents or no children by showing that in this case, it can be solved by Vertex Cover on bipartite graphs, but I failed in finding a reduction that proofes the NP-hardness of the original problem.

Can somebody give me a hint how to do this?

PS: In the contest, the task was only to find an algorithm that solves this problem, the original (German) definition is task 1 of this document: http://www.bundeswettbewerb-informatik.de/fileadmin/templates/bwinf/aufgaben/bwinf35/aufgaben352.pdf

The problem is polynomial-time solvable, suggested in Lemma 1 of the paper Computational Complexity of Some Maximum Average Weight Problems with Precedence
Constraints.

Basically the idea is to write a linear program on variables $x_i\in[0,1]$, where $x_u-x_v\leq 0$ if $(u,v)\in E$. The signed adjacency matrix is totally unimodular, so we can compute the integral optimum.


How can I optimise this bitmask generation algorithm? I am emulating the left shifting of a 128-bit integer using two 64-bit integers. For this I must calculate the bits that need to be moved into the higher portion. I have the following algorithm for generating a bitmask that masks the last until bits.

Where until is an integer in the range 0..64:

 ~(power(2,64-until))-1)

For convenience this is it in Python:

def mask(until): bin((~(2**(64-until)-1))&0xFFFFFFFFFFFFFFFF)

Is there a faster way to do the same thing by avoiding the costly use of power()? Or is this the most efficient way?

You can compute a power of 2 using the operation of left shift, in C and related languages <<. For example, $2^n$ is the same as 1 << n.

An alternative is to precompute the mask for all possible input values, and store them in the array. You'll have to try it out to see whether this is faster than the other suggestion.


Variable size and CPU performance When you learn programming they tell you choose data types that suffice for the concepts you're expressing, i.e. not too small because then your data won't fit and not too big because you don't want nonsensical values stored.

Table of unsigned integers

8-bit: 0 to 255
16-bit: 0 to 65,535
32-bit: 0 to 4,294,967,295
64-bit: 0 to 18,446,744,073,709,551,615

According to the table above, an 8-bit unsigned integers can store e.g. the number of weeks in a year (approximately 52) and a 64-bit unsigned integer can store e.g. astronomical values.

To get to the point of my question; how do the different variable sizes affect the performance of a program? I imagine that a 64-bit CPU internally handles all variables as 64-bit and simply ignores the highest bits, so an 8-bit variable, travelling across the system, would be handled as:

xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx xxxxxxxx yyyyyyyy

Where y is either 0/1 and x is ignored.

Would it make any difference performance-wise to only use the largest variable size on the platform and use business logic to enforce reasonableness in the values being processed and stored? Is there a performance hit when using variable sizes lower than the native variable size of the architecture?

Would it make any difference performance-wise to only use the largest variable size on the platform and use business logic to enforce reasonableness in the values being processed and stored?

Yes, it could make your performance worse.

Memory, memory bandwidth, cache density are primary concerns. Larger data size can:

result in increased cache and translation lookaside buffer (TLB) misses;
require more RAM to avoid paging.

E.g. x86 CPUs always load (if not already in cache) a whole cache line from memory.

So, assuming a cache line of 64 bytes, there are 64 8-bit-integers per cache line, yet only eight 64-bit-integers. Thus resulting in eight times as many memory transfers for processing a large array.

Also consider that many compiler are smart enough to figure out how to perform automatic vectorization1.

Taking advantage of the processor's SIMD capabilities you can pack eight 16-bit integers into the same space as two 64-bit integers and do four times as many operations at once.

  Is there a performance hit when using variable sizes lower than the native variable size of the architecture?

There isn't a general rule.

x86 CPUs can operate on fractions of a register and there will be no slow down at all2.

Other CPUs (e.g. PowerPC) cannot process a fraction of a register. So performing multiple operations on small integers may require masking / cutting back partial results. Anyway it's just a simple AND operation and often the compiler can find a way to avoid it entirely.

As a corner case some instructions can be slower when performed with the CPU's "native size" (e.g. multiplication / division of 64-bit quantities vs 32-bit quantities on Intel Pentium IV).

Interesting readings are:

What Every Programmer Should Know About Memory by Ulrich Drepper (chapter 6, about maximizing the efficiency of the data cache)
int vs long long in 64 bit machine
Performance 32 bit vs. 64 bit arithmetic
The microarchitecture of Intel, AMD and VIA CPUs by Agner Fog

1) automatic vectorization is a major research topic in computer science

2) x86 processors can suffer a partial register stall if you, say, write to BX and then try to read from EBX (something to consider mixing integer of different sizes).


Subset sum algorithms, their time complexity The algorithm is in Python. Seems correct to me, ideas how to prove it? And what would be its time complexity?

from bisect import bisect

# Implements the decision version of subset sum.
# The subset sum problem: given a set and a number find a subset of the set which sums to the given number.
# Inputs: an ordered list of integers xs, and an integer n which is the target sum.
def subset_sum(xs, n):
    if n < sum(filter(lambda x: x < 0, xs)):
        return False
    if n > sum(filter(lambda x: x >= 0, xs)):
        return False
    xs = xs[:]
    u = {}
    def rec(i, n):
        if not (i, n) in u:
            u[i, n] = False
            k = bisect(sums[:i], n)
            while k > 0:
                k -= 1
                u[i, n] = u[i, n] or sums[k] == n
                u[i, n] = u[i, n] or rec(k, n - sums[k])
        return u[i, n]
    sums = xs
    return rec(len(sums), n)

It has been answered below that the above algorithm is exponential time.

That being so, I have a follow up question: Is the algorithm still exponential time if the rec sub-routine above is changed into the following?

def rec(i, n):
    if not (i, n) in u:
        u[i, n] = False
        k = bisect(sums[:i], n)
        k -= 1
        if k >= 0 and n >= sums[0]::
            u[i, n] = sums[k] == n or rec(k, n - sums[k]) or rec(k, n)
    return u[i, n]

The recurrence $T(i, n) = T(i - 1, n - 1) + log_2(i)$ is what I came up with for worst case running time. Maybe that's far off.
But from that it seems it is $|S|log(|S|)$.

New information:
I have been able to solve a problem instance involving a set of 8192 integers equal to the range (1, 9, ... 65537) and the target n = 65525 in one and a half minute on my laptop. The resulting list consists of 125 integers. That makes the algorithm (with the above changes applied) sub-exponential, certainly not $2^{|S|}$ . The time taken is for the search version which applies the decision version discussed here $|S|$ times.

Here is a link to the full source code of my test set-up:

http://codepad.org/5s5lkHAm

Your algorithm is very similar to exhaustive search. It is basically the following approach:

  In order to check whether some subset of $S$ sums to $n$, go over all $i \in S$ and check whether some subset of $S \setminus i$ sums to $n - i$.

The actual algorithm uses memoization and a few other optimizations. Its complexity is exponential in the size of $S$ (probably roughly $2^{|S|}$ in the worst case).


Is there a standard (common) notation for the following operation on binary strings? Typically, we use the notation $S = \{0, 1\}^n$ to denote the set of all $n$-bit strings. Suppose that I wanted to extract a subset of the strings where certain bits have some fixed values. For example, I could try defining $S' = \{s= s_n\ldots s_1 \in S : s_2 = 1, s_4=0, s_n = 1 \}$ to denote the set of $n$-bit strings where $s_2$, $s_4$ and $s_n$ have the specified values.

Given that I am going to need to define many such subsets, it would be useful to have some better notation.... say $S_{\{s_2 = 1, s_4 = 0, s_n = 1\}}$, though this doesn't look very appealing. For those perhaps more familiar with the literature than I am, is there a set of notation that is typically used to denote such subsets? If not, what might be a compact and appealing way to denote such a subset?

There are pattern languages [1].

A pattern is a string over a terminal alphabet $\Sigma$ and an (infinite) variable alphabet $V = \{x_i \mid i \in \mathbb{N} \}$. Let $p = \alpha_1 x_{i_1} \alpha_2 \dots x_{i_k} \alpha_{k_1}$ be a pattern with $\alpha_i \in \Sigma^*$ for $i \in [1..k+1]$ and $x_j \in V^*$ for $j \in \{i_1, \dots, i_k\}$; its language is defined as

$\qquad\displaystyle L(p) = \{ \alpha_1 \beta_{i_1} \alpha_2 \dots \beta_{i_k} \alpha_{k+1} \mid \beta_{i_1}, \dots, \beta_{i_k} \in \Sigma^* \}$.

Note that the $i_j$ need not be pairwise distinct in general -- that is $L(x_1x_1) = \{ww \mid w \in \Sigma^*\}$ -- but one can make that restriction.

This is stronger than what you need; you want to restrict the language of possible replacements to individual symbols, and you want the variables to be independent (i.e. the $i_j$ to be pairwise distinct). It is easy to adapt the definition:

A bit-pattern is a string over a terminal alphabet $\Sigma$ and a wildcard $\star$. Let $p = \alpha_1 \star \alpha_2 \dots \star \alpha_{k_1}$ be a pattern with $\alpha_i \in \Sigma^*$ for $i \in [1..k+1]$; its language is defined as

$\qquad\displaystyle L(p) = \{ \alpha_1 x_1 \alpha_2 \dots x_k \alpha_{k+1} \mid x_1, \dots, x_k \in \Sigma \}$.

This is so straight-forward and the concept of wildcards is so wide-spread that, actually, I don't think you even need a reference; just define whatever you need. If you do find a reference it does not hurt to cite it, of course.

Polynomial time inference of extended regular pattern languages by T. Shinohara (1982)


What is the lower bound for finding the third largest in a set of $n$ distinct elements? What is the lower bound for finding the third largest in a set of $n$ distinct elements?

For the case of finding the second largest, we have the tight lower bound of $n + \lceil \lg n \rceil -2$. The adversary argument can be found in this lecture, which also provides an optimal algorithm using the "Tournament Method".

Edit (04-04-2017): Removing the algorithm for finding the third largest element which turns out to be wrong.

Answer my own question:

At the end of "Lecture 28: Adversary Arguments" by Jeff Erickson, I found

  A similar argument implies that at least $n - k + \lceil \lg {n \choose k-1} \rceil = \Omega \big( (n - k) + k \log (n / k) \big)$ comparisons are required to find the $k$-th largest element in an $n$-element set. This bound is tight up to constant factors for all $k \le n/2$; there is an algorithm that uses at most $O \big( n+k \log(n/k) \big)$ comparisons. Moreover, this lower bound is exactly tight when $k = 1$ or $k = 2$. In fact, these are the only values of $k \le n/2$ for which the exact complexity of the selection problem is known. Even the case $k = 3$ is still open!

Therefore, the current answer to the question is that it is still unknown.


All total functions form a PRC class A class of total functions is a PRC class if:

  The class includes all projection functions $p_i(x_1,\ldots,x_n) = x_i$ and the initial functions $n(x) = 0$ and $s(x) = x+1$.
  The class is closed under composition and primitive recursion.

  Prove that the class of all total functions is a PRC class.

Is it true if I say every total function is computable?
And then say because the class of computable functions is a PRC class, so is the class of total functions.

You cannot say that every total function is computable, since that is not true. For example, the function $f(n)$ which returns $1$ if the $n$'th Turing machine halts and $0$ otherwise is not computable.

However, the question is much simpler. The definition of a PRC class specifies several closure properties, of the form: if so-and-so belong to the class, then such-and-such also belongs to the class (these include the "axioms", in which the premise is empty). Since the class of all (total) functions contains all functions, it automatically satisfies these constraints.


What is the difference between symbol recognition, classification and identification? I've just wondered if there is a difference between symbol recognition, classification and identification.

What would you use when you have a hand-written symbol and you want to get the LaTeX code for it? Is that symbol classification, because you have about 1200 classes of LaTeX symbols? Or identification? Are some of those words synonyms? Which words are used more often?

The way I've seen it used classification divides a data set into different groups (or classes), while symbol recognition means looking for a specific pattern and checking if it is present in the data or not.

If I understand correctly, what you are talking about is optical character recognition but instead of matching the symbol to an ASCII/unicode value you match it to a LATEX symbol. I think that this could be called both symbol recognition and identification.


How efficient of this prime sieving algorithm? I just found there is an old program of mine where I implemented the following prime sieving algorithm:
#define MAX=1000001
#define SQRT=1000
// ...
not_prime[1] = 1;
for (int a = 2; a <= SQRT; a++)
  if (!not_prime[a])
     for (int c = MAX / a, b = a * c; c >= a; c--, b -= a)
        if (!not_prime[c])
           not_prime[b] = 1;

It seems like my logic that time is: For any given composite a and all corresponding composite cs such that MAX >= b; b = a * c. But I forgot why I set restriction on c that c >= a? Could anyone help explain this line for me and help me analyze how efficient this algorithm is?

The loop "int c ... " is much too complicated and difficult to get right, just start with c = a, b = a*a, and iterate upwards.
Most people create a sieve for odd numbers only. Some create a sieve only for the eight out of 30 numbers that are not multiples of 2, 3 or 5. That's a factor of 3.75 in space. And removing multiples of 2, 3 and 5 takes substantial time.
Only checking multiples of 2, 3 or 5 also allows you to check fewer multiples of the prime. Another factor 3.75.
If you want to be fast, you use a bit array, and use SIMD instructions to remove multiples of small primes, say up to 100, which saves a huge amount of time. Checking whether c is still considered a prime is time consuming and likely takes more time than it saves, especially since you will end up with lots of mispredicted branches.
Now for primes up to a million that's all irrelevant, but for larger ranges it makes a huge difference.


Is Kolmogorov Complexity Universal? Is the Kolmogorov complexity of any piece of information with respect to a certain predefined encoding for all pieces of information, or can the encoding vary for each piece of information?

There are different encoding mechanisms for representing data, and different ways of compressing the encoded data. If Kolmogorov complexity was encoding agnostic, then wouldn't the shortest computer program to describe each information be "0" or "1" and a call to the encoding system where each encoding system maps "0" or "1" to pieces of information of arbitrary length (the number of encoding systems would be $\frac{n}{2}$, where $n$ is the umber of pieces of information being considered). We could also increase the length of the description string, and reduce the number of encoding systems, but I think my point stands. This seems like a trivial notion of Kolmogorov complexity--is there anything I'm missing?

The formal version of your statement is known as the invariance theorem, which states (informally) that any two definitions of Kolmogorov complexity differ by at most a constant. This issue is covered on any textbook or lecture notes on Kolmogorov complexity.


Do we want largest or smallest priority in the A* algorithm? On this site http://algs4.cs.princeton.edu/25applications/ is described A* algothihm this way

  The A* algorithm is a problem-solving process where we put the start
  configuration on the priority queue, then do the following until
  reaching the goal: remove the highest-priority configuration and add
  to the queue all configurations that can be reached from that with one
  move (excluding the one just removed).

But in the programming assignment specification (http://coursera.cs.princeton.edu/algs4/assignments/8puzzle.html) is written next

  delete from the priority queue the search node with the minimum
  priority.

I don't understand why on the booksite is written to remove the highest-priority configuration but in the assignment is written to remove the lowest-priority configuration. Please could you explain me it? Maybe they thinks about "priority" or "configuration" in different meaning?

It's just two ways of saying the same thing.  High priority means most urgent but is often represented by low numbers – my "number-one priority" is the most urgent thing on my to-do list.  Perhaps it would be clearer if people used phrases like "lowest priority value" or even "highest priority (lowest priority value)". It's often inconvenient to reformulate the algorithm to make high priority correspond to big numbers. For example, if I decide that "priority 10" means the most important thing on my to-do list, that kind of limits my lists to ten items, unless I want to number them 10, 9, ..., 1, 0, -1, -2, ..., which seems a bit silly.

Similar confusion comes up in other settings where smaller numbers represent bigger or higher things. For example, in photography, aperture is measured in f-stops but a higher f-number means a smaller aperture.


Converting If-else integer equation to Linear Programming I have an if-then-else condition with three binary variables A, B and C:

if A + B = 1 then C = 0

How do I express this as an integer linear program with equality constraints?

Your condition is effectively excluding $(0,1,1)$ and $(1,0,1)$ corners of the unit cube. Thinking of it pictorially gives you a quick formulation: (i) construct the cube, (ii) chop those corners off and (iii) ensure integrality.
In (ii), the corners we want to get rid of are on the $BC$ and $AC$ planes. We can cut from the correctly aligned diagonals on those planes. However, moving in $+A$ direction, the cut should shrink and vanish at $A=1$ to include $(1,1,1)$.
\begin{align*}
&\text{(i) } 0 \leq A,B,C \leq 1  \\
&\text{(ii) }-A+B+C \leq 1, A-B+C \leq 1 \\
&\text{(iii) }A,B,C \in \{0,1\}
\end{align*}


Applying the Pumping Lemma to aspecific string Given the language $ A = \{w \in \{a,b\}^{*} | w = w^{R}\}$ (i.e. palindromes using the symbols $a, b$), I am trying to determine if the Pumping Lemma can be applied to strings of the form $s = a^{2p}$.
From my understanding of the Pumping Lemma, to show it would hold, I need to decompose $ s $ into $ s = xyz $ such that (1) $ xy^{i}z \in A, i \geq 0 $, (2) $ y \neq \epsilon $, and (3) $ |xy| \leq p $.
For cases where $ p \geq 2 $, the decomposition makes sense to me and appears to be quite trivial.  For example, when $ p = 2 $, then $ s = aaaa $, and can be decomposed into $xyz$ where $x = a, y = a, z = aa $, which satisfies the conditions above above.  Induction could be used to show this holds for larger values of $ p $.
However, I am struggling on the case where $ p = 1 $.  Here, $ s = aa $, and it seems like there are not enough symbols to decompose into $ xyz $.  My best guess would be to choose $ x = a, y = a, z = \epsilon $, but for some reason this doesn't feel legal -- can you ad-hoc assign pieces of $ xyz $ to be $ \epsilon $?  Also, I believe this decomposition would fail to satisfy condition (3) above.  Can you offer some guidance on understanding what is happening in the case where $ p = 1 $?
Thanks for your time!

The empty string is a legitimate string, just like the empty set is a legitimate set. We say that a word $w \in \Sigma^*$ can be pumped with respect to parameter $p \geq 1$ and a language $L$ if there exists a decomposition $w = xyz$, where $x,y,z \in \Sigma^*$ satisfy the following three requirements:

$|xy| \leq p$.
$y \neq \epsilon$.
$xy^iz \in L$ for all $i \geq 0$.

A mathematical definition hides nothing. A word can be pumped if it satisfies the definition as stated. No more, no less.


Why is this a proof by contradiction for this algorithm? Isn't this a direct proof instead? First Slide: Find Max(A)

// INPUT: A[1..n] - an array of integers
// OUTPUT: an element m of A such that m >= A[j], for all 1 <= j <= A.length
max = A[j==1]
for j = 2 to A.length
if max < A[j]
max = A[j]
return max

Second Slide: Proof By Contradiction
Proof: Suppose the algorithm is incorrect. Then for some input A, either:

max is not an element of A or
A has an element A[j] such that max < A[j]

Max is initialized to and assigned to elements of A - so (1) is impossible.
After the j-th iteration of the for loop (lines 4 - 6), max >= A[j]. From lines 5,6 max only increases. Therefore upon termination, max >= A[j] which contradicts (2).
End Of Slides
This algorithm (first slide) finds the max element in the array. This is a proof by contradiction. Isn't this algorithm already proved when it gets to max >= A[j] in the last line of the second slide. Is which contradicts (2) even necessary? Because in the second slide you showed max is in the array, and then you met the condition of a maxium m: an element m of A such
that m >= A[j] for all 1 <= j <= A.length.
This seems to be two proofs in one. And since it seems to me that the direct proof happens first, then the proof by contradiction is redundant and therefore not necessary. Am i missing something here? Is this only a proof by contradiction? Or is it a direct proof instead?
The image below is just the slides 1 and 2 that I transcribed above. From York University.

You seem to think the structure of the proof is:

suppose the algorithm is incorrect;
prove that the algorithm is, in fact, correct;
this contradicts 1., so the algorithm is correct.

That's almost, but not quite true. Step 2 doesn't prove that the returned value $\mathrm{max}$ is bigger than every element of the array, which is what would be required to prove that the algorithm is correct. It just proves that $\mathrm{max}$ is bigger than the specific array value that was supposed to be a counterexample in step 1.

But, as Yuval has pointed out, the proof is much easier if you forget about contradiction completely and prove that $\mathrm{max}$ is in the array (identical to the given proof) and then show that $\mathrm{max}$ is at least as big as every array element (identical to the proof except "for all $j$" instead of just for one supposed counterexample.


Operations under which the class of undecidable languages isn't closed Do there exist undecidable languages such that their union/intersection/concatenated language is decidable? What is the physical interpretation of such example because in general, undecidable languages are not closed under these operations?

What can we say about the kleene closure? Do we have examples for it too?  I.e. can the closure of an undecidable language be decidable?

Also, can we generalize such undecidable classes?

Yes, let $H$ be binary encoding of the halting problem and $A=0H\cup 1\{0,1\}^{\ast}\cup\{\epsilon\}$, $B=1H\cup0\{0,1\}^{\ast}\cup \{\epsilon\}$, then $AB=\{0,1\}^{\ast}$ (why?)


Will the minimum spanning tree not have only those edges specified by the cycle property? I have just started to understand the "Minimum Spanning Trees" (MSTs), and had come across the cycle property. I am referring to the book - Algorithm Design by Jon Kleinberg and Eva Tardos. The statement of the property as written in the book is:

  Assume that all edge costs are distinct. Let C be any cycle in G, and let edge e = (v,w) be the most expensive edge belonging to C. Then e does not belong to any minimum spanning tree.

Now my doubt is: Are the edges of a graph (undirected graph with edges having distinct positive weights) that do not satisfy the cycle property the only ones which aren't present in the MST or will there be any other edges that don't belong to the MST and aren't covered by this property?

I am unable to come up with a proof to argue about whether such edges exist or not. Can some please give a proof for this?

Sorry if I didn't understand your question, but what I think you meant to ask is, whether it is possible for an edge to not be in a MST if this edge is not in a cycle.

Here's my answer.

Let us assume that we have an edge (u,v) in a graph G, that isn't part of a cycle. This would mean that there is no path from u to v that isn't the edge (u,v).
If the edge (u,v) weren't in the MST, this would mean that there is no path from u to v in this MST, meaning that the MST would be disconnected, and thus not an MST at all.
Hence if an edge is not part of a cycle, it must be in the MST of the graph.