# Question
Title: Scheduling / Queuing jobs with multiple different workers
I have a stream of jobs (so I don't know upfront how many jobs). And I have N workers in the system.

Now I want to schedule / queue a job to one worker (a worker can have multiple jobs in his queue).

However, it's not the case that the workers can equally well do all jobs (think delivery -- delivery people who are closer to the pickup can do the job better than those that are further away). So there are two costs. First the cost to assign job X to worker Y (which varies with each worker -- for example time from worker's location to pickup point) and second the cost of doing the job (for eg. time from pickup to customer location).

It's perfectly alright to re assign jobs from one worker to another as long as they have not started processing the job (so only the jobs that are queued up can be "shuffled" amongst the workers).

What's a good away to do assignment of jobs to workers so as to reduce the cost (or in our example, time for delivery) across all the jobs? It doesn't have to perfectly optimal.

One simple solution would be as soon as a job comes in to find the worker that can finish the job fastest (it could be worker who is working on another, but his initial cost could be very little -- for eg. somebody who is delivering an item to a customer and the pickup for the next item is very close by). This would obviously not be very optimal.

Then periodically, try and re assign the queued up orders by swapping jobs between pairs of workers that would result in faster delivery (or rather least waiting time) for all of the jobs. But how good is this?

# Answer
The simplest option is a single queue that workers can scan for a good job for them. In other words job distribution is done when a worker just finished his previous job and needs a new one.

Using only this will create suboptimal distribution when the queue is nearly empty due to the first come first serve.

Swapping jobs between workers is very difficult to implement in a way where the overhead of the swap does not exceed the work of the actual job. One way could be to periodically in the job have it be queued back partially completed but only if the current worker is suboptimal for that task and a better job for it is available in the queue.
> 0 votes

# Answer
It sounds like the stable marriage problem. You want array of objectives to be matched to an array of workers.

My first instinct is to try to run the gale-shapely algorithm on the objectives and workers, which will assign the first objective to each worker based on the cost of assigning and completing the task.

Then repeatedly, each time an objective completes, run the algorithm again based on the positions each worker will be in when their current objective is complete and along with the current position of the worker who has finished, assigning the objective to this worker that the algorithm says he should have.
> 0 votes

---
Tags: algorithms, optimization, scheduling, queueing-theory
---


# Question
Title: Problem with Understanding "correlated attributes into a set of values of uncorrelated attributes" in PCA
I am studying PCA. I have a problem in understanding the following concept:

What is meant by transforming "correlated attributes into a set of values of uncorrelated attributes" in Principal Component Analysis?

> Principal Component Analysis (PCA) is a mathematical procedure that uses an orthogonal transformation to convert a set of observations of possibly *correlated attributes into a set of values of uncorrelated attributes* called principal components.

as discussed in the article Weight by PCA (emphasis mine)?

# Answer
It looks like you are using RapidMiner documentation as a medium to study. If that is case, then the best answer to your question and probably to some other questions of yours should be, I believe, a recommendation of related textbook, tutorial or lecture notes.

For the current question, I recommend you to read *a tutorial on Principal Components Analysis* by Lindsay I Smith, a tutorial that is self-contained and easy to read.

Now let me get back to you question, assuming we have gone through that tutorial up to and including section 3.1 or any equivalent materials.

> What is meant by transforming "correlated attributes into a set of values of uncorrelated attributes" in Principal Component Analysis"?

That just means, given existing $x$ axis and $y$ axis, and a set of data points with their coordinates (a set of observations of possibly correlated attributes), PCA will produce their eigenvectors and, using these eigenvectors as the new $x$ axis and $y$ axis as well as moving the origin to the center of the data points, obtain the new coordinates of those data points (principal components). The crux of the PCA is that the new $x$ coordinates and the new $y$ coordinates of the data points are 2 uncorrelated variables (uncorrelated attributes) in the sense that their covariance is 0. I am talking about 2-dimensional data for simplicity; PCA applies to 3 or more dimension the same way. In higher dimensions, the new coordinates of the data points are a set of variables every pair between which are uncorrelated.

All these concepts become very much alive and easy to understand once you have gone through several end-to-end computations. That is probably the fastest way to understand these concepts.
> 1 votes

---
Tags: machine-learning, features
---


title: Relational calculus to SQL

text:
# Question
Title: Relational calculus to SQL
I am somewhat aware of the correspondence between (tuple and domain) relational calculus, relational algebra, and SQL. To the best of my understanding, one should be able to automatically convert a formula in relational calculus to an SQL query whose run on a database produces rows that make the original formula satisfiable. However, I cannot find any rules for such conversion and I would expect them to exist.

Is my understanding wrong? Where can I find these "conversion" rules? I am specifically interested in how to systematically (automatically) convert predicates involving existential quantifiers.

# Answer
> 2 votes
> I am somewhat aware of the correspondence between (tuple and domain) relational calculus, relational algebra, and SQL. To the best of my understanding, one should be able to automatically convert a formula in relational calculus to an SQL query ...

Why do people persist in this confusion? The semantics of SQL is different to Codd's Relational Model. Therefore no 'conversion' makes sense. Specifically:

* Relations are sets vs SQL tables are multisets.
* In Tuple Relational Calculus and Domain Relational Calculus, attributes are named, and that is the only way to access attributes vs SQL columns of an SQL table might or might not have names, might or might not have a unique name; can also be accessed by column position (under older SQL standards), and have an obtuse and incomplete algorithm for column positioning of query results.
* For Relational Algebra, it gets messier: some versions (including in Codd 1972) access columns only positionally; some only by name.

The only formal conversion between any of these is given in Codd 1972 'Relational Completeness', where he uses conversion from TRC to Relational Algebra (*not* *v.v.*) to show the expressive completeness of (that version of) RA. (And actually, it's from his 'Alpha', which is an 'implementation' of TRC that was never implemented.)

> However, I cannot find any rules for such conversion and I would expect them to exist.

Please give some reference claiming they exist. The usual form of words is that SQL is "based upon" RA or TRC. That's not a claim of convertability, in either direction.

> I am specifically interested in how to systematically (automatically) convert predicates involving existential quantifiers.

Given some relation schema

* `S(SNO, SNAME, CITY, STATUS)` with predicate 'Supplier identified by `SNO` is named `SNAME`, is located in `CITY` and has status `STATUS`',
* a derived predicate 'exists `STATUS` s.t. Supplier identified by `SNO` is named `SNAME`, is located in `CITY` and has status `STATUS`'
* is given by RA: pi(SNO, SNAME, CITY)(S).
* That is, existentially quantifying an attribute is equivalent to projecting it away. "Projecting away" is also known as REMOVE or project ALL BUT.

---
Tags: logic, relational-algebra, relational-calculus, tuple-relational-calculus
---


# Question
Title: Are there any optimization problems in P whose decision version is hard?
Normally to show that an optimization problem is hard, we show the corresponding decision version of the problem is hard. However, is this sufficient to support the conclusion? Does there exist any optimization problem which is easy but its decision version is hard?

# Answer
> 6 votes
Maybe it depends on what it means by solving an optimization problem. If it is to find "how big is the biggest $f(x)$", then the answer is no (see the answer of @David Richerby). If it is to find "the $x$ that maximizes $f(x)$", then consider the function $f(x) = \max\_{y\in Y}g(y)$ such that $\max\_{y\in Y}g(y)$ is hard to compute. The optimization problem is easy to solve since $f(x)$ is constant w.r.t. $x$, but the decision problem — decide whether there exists an $x$ such that $f(x)\>k$ — is hard to solve.

# Answer
> 8 votes
No. The optimization problem is "How big is the biggest $X$?" and the decision problem is "Is there an $X$ that is bigger than $y$?" Solving the decision problem simply involves comparing $y$ with the size of the biggest $X$. You can certainly compare two numbers in polynomial time so, if you can solve the optimization problem (compute the size of the biggest $X$) in polynomial time, you can solve the decision problem.

# Answer
> 2 votes
No, because you are supposed to choose the decision version so that any solution to the optimization problem can be used to solve the decision problem (with at most a polynomial increase in running time).

You can't choose just any unrelated decision problem; for this methodology to work, there has to be a correspondence between the optimization problem and the decision problem. The correspondence is that you need to make sure that any algorithm A for the optimization problem can be used to solve the decision problem, with at most polynomially many invocations of A.

# Answer
> 0 votes
No... if the optimal solution is $1101$ in binary, then that inherently already represents the solution to the four corresponding decision problems.

So if finding $1101$ is easy, that means computing the respective $1$, $1$, $0$, and $1$ was easy too.

---
Tags: complexity-theory, optimization, np-hard, decision-problem, search-problem
---


title: Determining the linear address

text:
# Question
Title: Determining the linear address
So I am working on a question that requires me to find the linear address.

Here's some information:
Main memory size is 8GB, which translates to $2^{3} * 2^{30} = 2^{33}$.
Block size is 16KB each, which translates to $2^{4} * 2^{10} = 2^{14}$.

I was then required to find:

(i) The number of blocks in main memory:
$2^{33}/2^{14} = 2^{19}$ blocks.

(ii) The number of bits required to address a block:
$19$ bits.

(iii) The number of bits required for an offset within a block.
I am not so sure if I did this bit correctly, but I ended up with:
$2^{14}$ bits.

These are the parts that I'm having trouble calculating or knowing what to do. Can I be guided accordingly, please?
(iv) The linear address for:
(a) Block 32, byte 100 (b) Block 1000 byte 1800.

(v) The block and offset of a byte for the linear address:
(a) 32431 (b) 232156

# Answer
Suppose that a memory of size $M$ is divided into blocks of size $B$:

* Block 0 consists of cells $0,\ldots,B-1$.
* Block 1 consists of cells $B,\ldots,2B-1$.
* Block 2 consists of cells $2B,\ldots,3B-1$.
* Block $k$ consists of cells $kB,\ldots,(k+1)B-1$.

The "linear address" of a cell is its address in the memory.

Another way of addressing it is by giving which block it belongs to, and what is its offset inside the block. For example, linear address $B+2$ corresponds to block 1, offset 2.

Given a block and an offset, you can easily compute the corresponding linear address; and given the linear address, you can easily compute the block and the offset. Rather than spelling out the arithmetic, I challenge you to come up with the requisite formulas. Using these formulas, you can complete your exercise.
> 0 votes

---
Tags: operating-systems
---


title: Dimension of 1x1 convolution output

text:
# Question
Title: Dimension of 1x1 convolution output
I am having a hard time understanding maths behind a 1x1 convolution and how is it actually performed.

Assuming that I have a 6x6x32 input to my 1x1xK convolution layer similar to the one presented in this video and shown below. I understand that I would take a 1x1x32 slice from the input ( blue in the image below), but what operation would I actually perform?

Do I just take one value, let's say at \[1,1,1\] of yellow and multiply each value in the input slice with this value, or do I multiply each value from the slice with the corresponding value in the 1x1x32 part.

Also what is meant by #filters? Doesn't it need to match 32 in a given example?

# Answer
Have a look at this: https://medium.com/machine-learning-bites/deeplearning-series-convolutional-neural-networks-a9c2f2ee1524

It's like this: third dimension of input and filter must match! So if you only have one of those yellow filters your output will be 6x6x1. But if you have let's say 42 filters then you'll perform 42 filter operations and your output will be 6x6x42.

Hope this helps ;)
> 1 votes

---
Tags: neural-networks
---


title: Proving a set is semi-decidable

text:
# Question
Title: Proving a set is semi-decidable
Let $S = \\{ ⟨M,q⟩ | (\exists x) M $ reaches state $q$ when running $M$ on $x$$\\}$, where ⟨M,q⟩ is coded TM M and state q.

To prove that $S$ is semi-decidable, I've tried to use the equivalence:

Language $L$ over alphabet $\Sigma $ is semi-decidable $ \iff $ There exists a semi-decidable language $M$, such that $L = \\{x \in \Sigma ^ \ast| \exists y \in \Sigma ^ \ast ⟨x,y⟩ \in M\\} $.

Let $L\_H = \\{ ⟨M, q, x⟩ ∣ M$ runs on $x$ $\\& $ $M$ reaches state $q \\}$ and let $H(⟨M, q, x⟩)$ be a TM which decides $L\_H$. If we simulate $M$ and $M$ runs on $x$ and reaches state $q$, then H accepts and $⟨M, q, x⟩ \in L\_H$, therefore all words in $L\_H$ are accepted by $H$ and $L\_H$ is semi-decidable. Is it enough to show that $S$ is also semi-decidable? What are other common ways to prove a language is semi-decidable?

# Answer
> 0 votes
You are missing a proof that $L\_H$ is semi-decidable.

Here are two ways to prove that $S$ is semi-decidable.

**First method.** The following predicate is decidable: "$M$ reaches state $q$ after running on $x$ for $t$ steps". Hence the following is semi-decidable: "there exist $x,t$ such that $M$ reaches state $q$ after running on $x$ for $t$ steps".

**Second method.** On input $M$ and $q$, simulate $M$ on all possible inputs (by dovetailing); output $\langle M,q \rangle$ for each state $q$ reached by each of these simulations.

---
Tags: turing-machines, semi-decidability
---


# Question
Title: Randomly choose vector b in range such that $\vec{a} \cdot \vec{b} = 1$
**Given**

* I have a $n$ dimensional $\vec{a}$.
* All elements of $\vec{a}$ are between 0 and a positive number $K$.
* $n$ is about 15 to 20.

**Problem**

I want to randomly and unbiasedly choose a vector $\vec{b}$ such that:

* Elements of $\vec{b}$ are between 0 and 1.
* $\vec{a} \cdot \vec{b} = 1$

How to do that?

**Attempt**

I thought about the following:

* Choose $\vec{c}$, a random direction perpendicular to $\vec{b}$.
* Find range of $\theta$ such that $\vec{b} = \frac{\vec{a}}{\lVert \vec{a} \rVert} + \theta\vec{c}$ is within bounds.
* Randoly choose a $\theta$

The problem is that this is not unbiased. Some directions have a larger range of legal $\theta$, and those directions should be chosen more often.

# Answer
> 1 votes
Uniformly sampling from a simplex with equation $\vec{a} \cdot \vec{b} = 1$, and reject samples out of bounds.

Several answers are posted here for uniform sampling over a simplex: Uniform sampling from a simplex

---
Tags: computational-geometry, linear-algebra
---


# Question
Title: Prove $L = \{M \mid L(M)\text{ is infinite}\}$ is not Turing-recognizable
I'm supposed to prove this through mapping reducibility. I think I'm supposed to show that $A\_{\mathrm{TM}} \le\_\mathrm{m}\overline{L}$, which means that $\overline{A\_{\mathrm{TM}}}\le\_\mathrm{m} L$ and, since $\overline{A\_{\mathrm{TM}}}$ is not Turing-recognizable, then $L$ is not Turing-recognizable.

I think that $\overline{L} = \\{M\mid L(M) \text{ is finite} \\}$ and that it means that $L(M)$ contains a finite number of strings.

I don't know how to construct a Turing machine that can prove $A\_{\mathrm{TM}}\le\_\mathrm{m} \overline{L}$.

# Answer
> 1 votes
Recall that the input to the halting problem is a pair $(\langle M\rangle, w)$ and we must accept this input if $M(w)$ halts, and reject it otherwise.

We want to decide the halting problem by reduction to $\overline{L}$. That is, we need to produce a computable function $f$ that takes an input $(\langle M\rangle, w)$ and produces a string in $\overline{L}$ if $M(w)$ halts and a string that is not in $\overline{L}$ if $M(w)$ does not halt.

There's a small mistake in your reasoning in the question that's worth mentioning at this point, but it doesn't make any real difference. Strings in $L$ are descriptions of Turing machines that accept infinitely many inputs. That means that a string is in $\overline{L}$ if either it's a description of a Turing machine that only accepts finitely many inputs, or if it's not a description of any Turing machine at all.

However, we can ignore the strings that don't describe Turing machines and design a function $f$ such that $f(\langle M\rangle,w)$ is always the description of a Turing machine and that Turing machine accepts only finitely many inputs if $M(w)$ halts, and is one that accepts infinitely many inputs if $M(w)$ doesn't halt.

Hint: $\emptyset$ is finite and $\Sigma^\*$ is infinite. Transform $(\langle M\rangle,w)$ into the string $\langle M'\rangle$ such that $M'$ will accept nothing if $M(w)$ halts and will accept everything if $M(w)$ doesn't halt.

There's another hint below, which you can see by mousing over the yellow box. But try to figure it out on your own, first.

> Hint 2: the reduction is very similar to the one used to prove that the problem "Does $M$ halt on the empty input?" is undecidable.

---
Tags: turing-machines, computability
---


# Question
Title: Finding minimum number of edges such that when adding into the graph, the graph is a 2-connected graph
Given is a undirected and 1-connected graph G=(V,E). Between every two node b=(u,v) in graph G there is a cost c\_b to build another edge(Regardless of whether (u,v) ∈E or not). We use a C={c\_b |c\_b∈Z^+,b∈V×V} to represent costs between every node regardless of whether (u,v) ∈E or not. Now, we want to add some edges M⊂E into the graph G which makes graph G^'=G+M is a 2-connected graph (G^' allow the appearance of multiple edges while graph G is not) such that weights of edge set of M is minimize.

# Answer
$2$-connectedness is the same as *bridgeless*.

So $M$ must be the set of bridges in $G$ no matter how large or small their sum is.
> 1 votes

---
Tags: algorithms, graphs, optimization, np-hard
---


# Question
Title: Does Halts reduce to all other undecidable languages?
In a CS theory class I'm taking, we showed Halts was undecidable via a diagonalization argument. All other undecidable problems we looked at we either got by reducing Halts to them, or some chain of reductions that started with Halts. Are there any undecidable languages which Halts does not reduce to?

# Answer
Recall that $A \leq\_m B$ iff $\bar A \leq\_m \bar B$. Indeed, the same reduction function works for both cases.

So, let $H$ be the halting problem. Both $H,\bar H$ are undecidable. We prove $H \not\leq\_m \bar H$.

By contradiction, assume $H \leq\_m \bar H$. Hence, by the property above, $\bar H \leq\_m H$. Hence $\bar H$ reduces to some RE problem, making $\bar H$ RE as well. Since $H,\bar H$ are both RE, we conclude that both are decidable. Contradiction.
> 2 votes

# Answer
$\mathrm{HALT}$ does not reduce to $\overline{HALT}$. Otherwise, all the arithmetical hierarchy would collapse to $\mathrm{R}$.
> 0 votes

---
Tags: turing-machines, computability, undecidability, halting-problem
---


# Question
Title: Calculate Shortest Path (Shortest Time) Through a Store in a Graph
There is an undirected graph and some of the vertices are said to be stores. Person A wants to reach to person B **with a present.** That means person A has to stop by one of the vertices marked as stores and get the present first before ever reaching to person B. Moreover, each store has a specific waiting time, and if the person decides to stop by at that particular supermarket, the waiting time should be included in the shortest path(shortest time).

Well, regular Dijkstra does not work very well because the shortest path may not include any store vertices, so the stores should somehow be incorporated in the algorithm. It is a must to visit one of the vertices marked as a store. But total travel time has to be the minimum.

Only the vertices marked as stores have weights, and it is a must to visit at least one of them.

# Answer
> 1 votes
You can do this with two instances of shortest paths.

1. You need to know the shortest distance $d(A,S)$ for each store $S$. This is just Dijkstra from source $A$.
2. You also need to know all the shortest paths from each store to B; i.e. $d(S,B)$ for each store $S$. This can be done by reversing the edges in the graph and running Dijkstra from source $B$.

Once you have these two, all you need to do is compute the min over paths that stop at a store, including the weight $w$ of the store.

$\min\_S \left(d(A,S) + w(S) + d(S,B)\right)$

Asymptotically, in total, this is no more expensive than just running Dijkstra's algorithm. In practice you can stop early in each instance of Dijkstra once you've seen all of the stores.

---
Tags: algorithms, graphs, shortest-path
---


# Question
Title: What is the real reason that Bubble Sort runs at O(n) in best case?
In this link https://techdifferences.com/difference-between-bubble-sort-and-selection-sort.html it says that the best case of bubble sort is order of n due to the fact that there would be only comparisons and no swaps in the inner loop.

But is that correct? Are comparisons not counted in the complexity ? Only swaps?

Other sources claim the reason is only because it can be optimized with a ' flag' checking if it entered the inner loop. In that case there would be ZERO swaps and n comparisons. ( If this reason is correct, can't I optimize other sorting algorithms this way? Likesay, selection sort?)

What is the correct reason? I questioned both of the reasons!

EDIT: this is what is said in the link: "In the best case, it is of order n because it just compares the elements and doesn’t swap them"

# Answer
> 4 votes
Understanding how Bubble Sort works is of course really the key here.

The main part for unraveling this is that Bubble Sort goes back to the start if it ever performs a swap. If it never performs a swap, it runs along the array once, comparing each element to the one after it, and thus performing $O(n)$ comparisons.

So both sources are correct. The comparisons are counted in the complexity, you just do more of them (and some other things) if you need to swap stuff.

The reason this doesn't work for something like Selection Sort is that Selection Sort looks for the next element to place at the end of the sorted section in each pass. It doesn't know where that element is, and moreover, it always "moves" something (even if it's a trivial move), and whether you made a trivial move doesn't affect whether you will next time either (whereas in Bubble Sort, if you don't move anything, you know you never will).

You could add a check at the start to see if the array is already sorted of course.

Other sorting algorithms can benefit from similar cases to that in Bubble Sort though; Insertion Sort for example has best case $O(n)$ behaviour as well.

# Answer
> 1 votes
Note that The linked article says,

> After each iteration, the number of comparisons decreases and at last iteration only one comparison takes place.

If we take the statement, "at last iteration only one comparison takes place" literally, it implies the version of bubble sort used in that article does not use the standard optimization techinique, stopping once no swaps have happened in an iteration. That article is then wrong in its statement, "the best case complexity (when the list is in order) of the bubble sort is of order $n$ ($O(n)$)", since that version of bubble sort runs with time-complexity $O(n^2)$.

The correct statement should be all implementations of bubble sort at Wikipedia run with $O(n)$ time-complexity at best cases, when the given list of elements are sorted.

On the other hand, as Luke Mathieson pointed out, the standard lecture on bubble sort is "here's bubble sort without any checks, this is a dumb way of doing it, never bother to do that, here's the proper way". So, it is not surprising that some people just start from there implicitly sometimes, without realizing that it might be confusing in telling $O(n)$ best time-complexity for all versions of bubble sort.

---

The general convention is that comparisons are counted in the complexity of any sorting algorithms. Swaps might not be counted in some models of complexity analysis.

Regarding to the usage of flags, I cannot, in fact, see how one can use flags in a similar way to improve the performance of selection sort although you can always check if the input array is sorted or not beforehand for any sorting algorithm.

---
Tags: complexity-theory, algorithm-analysis, runtime-analysis, sorting
---


# Question
Title: How can I show that a problem is not $NP$
Consider the following image:

The problem is: *can we cover the bigger rectangle with small rectangles such that no two rectangles overlap and no gap opens up?* Prove that this problem is $NP-Hard$.

I know that to prove that it is $NP-hard$, I must reduce a $NPC$ problem to it.

However, I guess that the problem is not $NP$, right? For example, even if we have a "**Yes**" answer for the items above, how can we fit the small rectangles into the big rectangle in polynomial time?

For the above problem, the answer can *includes* the placement of small rectangles in the bigger rectangle. So, verifying it is easy, and the problem is $NP$.

Suppose, the question was: *is there any subset of rectangles that cover the bigger rectangle so no two rectangles overlap and no gap opens up?*

Then, what would be the shape of a certificate? Would it be verifiable in polynomial time? Would it be just a subset of items, or their placements too?

What if it was an optimization problem requesting *a subset of items that cover the largest area of the bigger rectangle*? Then, we had to check other answers to see that the certificate is the optimum one, and that would make the problem non-**NP**, right?

How a certificate is defined in such cases, and what is its role in categorizing a problem as $NP$ or non-$NP$?!

# Answer
The only result that I am aware of (assuming your problem is computable) is the time hierarchy theorem, which implies that $NP\neq NEXPTIME$. If you have a problem that is $NEXPTIME$-hard and show that that problem reduces to your problem, you've shown your problem isn't in $NP$. Since $NEXPTIME\subseteq EXPSPACE$, an $EXPSPACE$-hard problem would work as well.

Your problem is in $NP$, however.
> 2 votes

---
Tags: complexity-theory, np-complete, reductions, np-hard
---


# Question
Title: Show that $R^{+} \equiv R \leftrightarrow L(RR) \subset L(R)$
Show that $R^{+} \equiv R \leftrightarrow L(RR) \subset L(R)$

sigma is any alphabet. R is a regular expression.

How can L(RR) even be a subset or equal to L(R)?

# Answer
If $\varepsilon\in L(R)$, then $RR$ matches every string matched by $R$: you can match the first $R$ against $\varepsilon$ and the second $R$ against the rest of the string.
> 0 votes

---
Tags: regular-languages, automata, finite-automata, regular-expressions
---


# Question
Title: Is there a name for this shuffle algorithm?
Is there a standard name for the following algorithm? At each step, the code picks an index, remove the object at that index, and remember to never pick that index again. See the following illustration:

Others have suggested the Fisher–Yates shuffle, but it seems like this algorithm is simpler. I found this algorithm useful for many different types of problems. An example use case is, to cycle through 24 hours in a day, by random, without picking the same hour twice.

An index is used to avoid picking the same object twice,

```
mapping(uint => uint) shufflingIndex;

```

a counter is used to shrink the list of objects to choose from

```
uint counter;

```

and a random number generator is used to select an object.

# Answer
> 1 votes
Algorithm P (Shuffling) from Knuth, 1969, similar to the Fisher–Yates shuffle from 1938 though invented independently.

```
-- To shuffle an array a of n elements (indices 0..n-1):
for i from 0 to n−2 do
     j ← random integer such that i ≤ j < n
     exchange a[i] and a[j]

```

The implementation in the question lets each object shuffle itself, adding itself to the list when doing so, whereas the example here from Wikipedia uses a loop.

---
Tags: algorithms, reference-request, randomness
---


title: Error in proof of decidability

text:
# Question
Title: Error in proof of decidability
> $L=\\{\left\<M\right\> \ | \ M $ is a TM s.t. $M$ does not accept any string starting with a '1' $\\}$. Assume the alphabet to be $\Sigma = \\{0,1\\}$.

By Rice's theorem $L$ is undecidable. I managed to "prove" that $L$ is decidable. So can someone point out the error in my proof. To keep things clean I ignore the empty string since it can easily be dealt with as a special case.

We can write $$L = \\{\left\<M\right\> \ | \ w\in \Sigma^\*, \ w \in L(M) \implies w\[0\] \neq 1\\}$$ $$ = \\{\left\<M\right\> \ | \ w\in \Sigma^\*, \ w \in L(M) \implies w\[0\] = 0 \\}$$ To get $\overline{L}$ we need to negate the condition in $L$. Hence $$\overline{L}= \\{\left\<M\right\> \ | \ w\in \Sigma^\*, \ w \in L(M) \implies w\[0\] = 1 \\}$$

We have $$\exists \ w\in \Sigma^\* \text{ such that } w\in L(M) \text{ and } w\[0\] = 1 \iff \left\<M\right\>\not \in L \iff \left\<M\right\> \in \overline{L}$$ We can construct a recognizer for $\overline{L}$ by searching for such a $w$

$R=$ 'on input $\left\<M\right\>$ where $M$ is a valid TM:

1. for $w \in \Sigma^\*$:
2. $\ \ $if $M(w) =$ accept
3. $\ \ \ \ $if $w\[0\]=1$ then accept'

So $\overline{L}$ is recognizable. Similarly we have

$$\exists \ w\in \Sigma^\* \text{ such that } w\in L(M) \text{ and } w\[0\] = 0 \iff \left\<M\right\>\not \in \overline{L} \iff \left\<M\right\> \in L$$ We can construct a recognizer for $L$ by searching for such a $w$

$R'=$ 'on input $\left\<M\right\>$ where $M$ is a valid TM:

1. for $w \in \Sigma^\*$:
2. $\ \ $if $M(w) =$ accept
3. $\ \ \ \ $if $w\[0\]=0$ then accept'

So $L$ is also recognizable, this means $L$ is decidable.

# Answer
The error is in the definition of $\overline{L}$. It should be $$ \overline{L} = \\{ \langle M \rangle \mid \exists w \\, w \in L(M) \land w\[0\] = 1 \\}. $$ In other words, $\overline{L}$ consists of all Turing machines which do accept some string starting with 1.

(More pedantically, $\overline{L}$ also accepts all strings which aren't descriptions of Turing machines.)

One further note: $w\[0\] \neq 1$ is not the same as $w\[0\] = 0$, since $w$ could also be the empty string.
> 1 votes

# Answer
Your language is indeed co-c.e.; the mistake is in the argument claiming recognizability of $L$. You have the existential and universal quantifier mixed up.
> 2 votes

---
Tags: computability, undecidability
---


# Question
Title: Approximating unique string occurrences using a small, fixed amount of memory
Is there a small-memory way to *estimate* how many unique strings have been encountered without needing to know the strings themselves? The trick is that we only have a tiny amount of memory to track what strings we have seen. Tiny like a 64 bit integer or 64 byte string. (The EZ infinite-memory solution is to keep a hash of the strings.) The strings being tracked themselves can be very long.

To make sure "unique" is clear, let's say we receive four strings: "cat", "dog", "cow" and "cat". We would count that as three unique strings as "cat" appears twice.

This method can be lossy! Some hashing solution with collisions is perfectly acceptable. Ideally the solution is more accurate for smaller amounts. E.g. counting 2 unique strings, we can be pretty sure it's exactly 2, but if the method returns 200, that's probably a decent estimate. .

The partial solution I have been considering is:

1. Set the tracker value to 1
2. Set the counter value to 0
3. For each string, get its hash value. If the tracker number is not evenly divisible by the hash, then increment the counter and multiply the tracker by the hash

The problem is that the tracker will quickly overflow and that will then (I assume) affect what numbers evenly divide it.

# Answer
> 1 votes
Your problem is known as the count-distinct problem. The Wikipedia page describes some of the algorithms which have been designed for this problem.

---
Tags: algorithms, data-structures, strings, substrings
---


# Question
Title: Possible to get the Sum x with maximal two summands?
Suppose we have $n$ different summands. Is it possible to get the sum x with a maximum of two of the $n$ summands (Below the m summands there can be several times the same one). For example you have the summands (2,4,6,7). So its possible to get the sum $2+4 =6$,$6=6$ but its impossible to get the sum $3$ or $1$ ect.

My idea of an algorithm would have the runtime $\mathcal{O}(n\log(n))$. Now I'm not sure if this is already aymptotically optimal ?

# Answer
> 0 votes
If the numbers have a limit on their value, i.e. all numbers are smaller than $m$, then you can get runtime of $O(n + m)$: in an array $t$ of size $m$, for each number $a$ in the set of summands, check if $t\[x - a\] \> 0$: if yes, then the answer is $(a, x - a)$. If not, set $t\[a\] = 1$ and continue with the next number.

This can be slightly improved with assigning values in buckets, but the worst time complexity will be $O(nm)$.

Otherwise, $O(n \log n)$ is the optimal complexity.

---
Tags: algorithms
---


# Question
Title: Uniform sampling over non-standard simplex
Uniform sampling over a $n$-dimensional standard simplex is described here: Uniform sampling from a simplex

I want to sample one point from a non-standard simplex with vertices at:

* $s\_{i}\vec{e\_{i}}$, where $\vec{e\_{i}}$ is the $i^{th}$ vector in the standard basis, and $s\_{i} \ge 0$.
* the origin is : $\vec{0}$

How to do that? It seems to be no longer a special case of the Dirichlet distribution.

Hit-and-run sampling would need a lot of cycle to diffuse throughout the simplex. When I only need one point, the other points are wasted.

Currently, $n \approx 15$

# Answer
According to Wikipedia the $n$-simplex is the set defined by:

$$S = \left \\{ \mathbf{x} \in \mathbb{R}^n \\; | \\; \mathbf{x} = \sum\_{i=0}^n \mathbf{u}\_i\theta\_i , \\; \mathbf{u}\_k \in \mathbb{R}^n , \\;\\; \theta\_k \> 0 \\;\forall k, \\;\\;\sum\_{i=0}^n \theta\_i = 1\right \\}$$

Note that the $\boldsymbol{\theta} = (\theta\_0, \dots, \theta\_n)^T$ is the standard $n$-simplex.

Hence in order to sample from $S$, compute a linear combination of the vertices $\mathbf{u}\_k$ with the weights given by a sample of the standard simplex.

Which is the same as the following random process:

Consider the matrix of vertices $U = \[\mathbf{u}\_0 \\; \dots \\; \mathbf{u}\_n\]$, then a sample in $S$ is given by:

$$\boldsymbol{\theta} \sim \text{Standard-Simplex}$$ $$\mathbf{x} = U \boldsymbol{\theta}$$

Note that in your case the vertex $\mathbf{u}\_k = s\_k \mathbf{e}\_k$.
> 2 votes

# Answer
I make this up for $n$-dimensional simplex.

Looks ok but I am not sure.

**Barycentric random walk**

1. Choose an initial point $\vec{x}$
2. Choose $\lambda \sim (U\[0, 1\])^{1/n}$
3. Choose a random vertex of the simplex $\vec{v}$
4. $\vec{x} \leftarrow \lambda\vec{x} + (1 - \lambda)\vec{v} $
5. Repeat till $\vec{x}$ is sufficiently random.

**Justification**

The probability density of $\lambda$ is proportional to the cross sections along the line between the current point and the vertex.

**Code**

```
import numpy as np

N = 10000

scales = np.array([0, 200, 3])

# -- Barycentric random walk --
vertices = np.diag(scales)
nd = scales.size
x = scales.copy().astype(float)

x[1:] = 0

x_all = np.empty((N, nd))
for i in range(N):
    # choose random vertex
    t = np.random.uniform(0, 1.0) ** (1 / nd)
    j = np.random.choice(nd)
    x = x * t + vertices[j] * (1 - t)
    x_all[i] = x

x = x_all

# -- Plot --

from mpl_toolkits.mplot3d import Axes3D
import matplotlib.pyplot as plt

fig = plt.figure()
ax = fig.add_subplot(111, projection='3d')

xs, ys, zs = x[:, 0], x[:, 1], x[:, 2]
ax.scatter(xs, ys, zs, marker='.')
ax.set_xlabel('X')
ax.set_ylabel('Y')
ax.set_zlabel('Z')

plt.show()

```
> 0 votes

---
Tags: algorithms, computational-geometry, probability-theory
---


# Question
Title: Do you >have< to define the upper and lower bound? (context: traveling salesman)
Do one have to define the upper and lower bound to be able to solve the tsp, or is that just an unnecessary intermediate step? And if so, why would one define those bounds? (context: the traveling salesman problem (TSP))

Additional question: After having calculated the upper bound (using eg. the Nearest Neighboor algorithm), and the lower bound (using eg. kruskal's algorithm) ... let's say we get: \[4; 8\]

Can we say for sure that the cost of the optimal route is a number in the interval \[4; 8\]? Is it possible to find a route whose cost is not within the interval?

# Answer
If you want to compute X (whatever X is), then you just need to compute X, and whatever intermediate results are required by your method for computing X. If your method doesn't need upper and lower bounds, there's no need to compute them.

The point of upper and lower bounds is that they're usually easier to compute than the actual answer, and they may be enough to answer your question. For example, as a typical student, you don't need to know the exact price of a helicopter to know that you can't afford one: helicopters surely cost at least \\$100,000 and you don't have \\$100000. Conversely, if you're a millionaire, you don't need to know the exact price of a chocolate bar to know that you can afford to buy one: surely a chocolate bar doesn't cost more than \\$100 and you definitely have \\$100.

> Can we say for sure that the cost of the optimal route is a number in the interval \[between the lower bound and upper bound\]?

Yes. That's what "upper bound" and "lower bound" mean.

> Is it possible to find a route whose cost is not within the interval?

Again, by definition of "lower bound" and "optimal", no route can be shorter than any lower bound on the length of an optimal route. Depending on what upper bound you use, it might be possible to find a route that is longer than an upper bound on the optimal route. For example, on upper bound on the length of a TSP route is to say that, since the optimal route must leave each vertex exactly once, the total length can't be longer than the sum of the longest edge from each vertex. But, if you think about it, that's actually an upper bound on *any* route, whether the route is optimal or not. So it's not possible to exceed this upper bound. However, it's possible that you could come up with a smarter upper bound such that the optimal route is definitely not longer than your bound, but suboptimal routes might be.
> 1 votes

---
Tags: graphs, lower-bounds, traveling-salesman, upper-bound
---


# Question
Title: A universal operator necessarily generates $\neg x$ for input $x,…,x$
I originally posted this on math.stackexchange, but then deleted it and moved it here since I think it would fit this site more.

I saw a claim in a slideshow from a basic computer architecture course that given some boolean operator $T(x\_1,...,x\_n)$, if it is universal then necessarily: $$T(x,...,x)=\neg x$$ However, I found no explicit mention of this claim anywhere else, including here. Is it correct? And if so can one please provide a proof or a proof-idea? Because it was provided as a fact completely unrelated to the rest of the slides I have no idea how to approach it, and I am not sure I even have the right tools to do so.

I have already seen this question, for example, but there the proof is tailored towards a specific function. My problem is with proving the general case.

# Answer
> 8 votes
There are two ways to define a universal operator: when constants are allowed, and when they are not allowed. If constants are allowed, then one can define a universal operator which doesn't satisfy the claim, as follows: $$ T(x,y,z) = \overline{x \land y} \land z. $$ This is universal since $T(x,y,1)$ is the NAND operator, but $T(0,0,0) = 0$.

Now suppose that constants are not allowed. Since $T$ is universal, there is a $T$-circuit which computes the NOT function $x \mapsto \lnot x$. Let us now consider the possible values that $T(x,\ldots,x)$ takes:

1. $T(x,\ldots,x) = \lnot x$: in this case the claim holds.
2. $T(x,\ldots,x) = x$: in this case, induction shows that every $T$-circuit in which the only inputs are copies of $x$ necessarily computes the value of $x$; in particular, no $T$-circuit computes NOT.
3. $T(x,\ldots,x) = 0$: in this case, when $x = 0$, induction shows that every $T$-circuit always computes 0; in particular, it doesn't compute NOT.
4. $T(x,\ldots,x) = 1$: similar to the preceding case.

This shows that $T(x,\ldots,x)$ must compute $\lnot x$.

---
Tags: logic, boolean-algebra
---


# Question
Title: Is it possible to do a NULL comparison in Relational Algebra?
Please consider the following question given in a booklet:

I have read about databases from **Database System Concepts - by Henry F. Korth**, but never saw an instance where we could do a NULL comparison in relational algebra queries - unlike SQL queries.

(C) is given the correct option, but my question is:

Is the statement III given above, a valid Relational Algebra query?

# Answer
> Is the statement III given above, a valid Relational Algebra query?

Good question; and you're going to get different answers depending on which exact version of RA you're talking about.

III has a restriction (sigma) `S.b<>null`. So it's presumably expecting that the result from the outer join will "fill values" in `S.b` where there is no S row matching an R row.

But whatever null is, it's not a 'value'. (Codd described it as a "mark".) So in SQL you can't write `... WHERE S.b <> NULL`. (Or rather you can, but it will never select any rows. `... op NULL` returns false for any comparison `op`.)

In SQL you must write `... WHERE NOT ISNULL(S.b)` (or some such) -- which shows that testing for null is not merely a comparison, because null is not merely a value.

You can choose different ways to try to make sense of nullable columns; but they all end up in some sort of gibberish like this. There simply is not any coherent semantics. I call it 'two-and-a-half value logic'.

So in any version of RA I would deal with, there's no nulls, no outer join, and III would not be a valid query.

There's a persistent confusion on stackxxx RA questions that SQL and RA are equivalent and that there's some mechanical translation between them. Well you can (as it seems in this case) add bogus semantics to RA so it's something like SQL. But why? It's putting lipstick on a pig.
> 0 votes

# Answer
Wikipedia says

> The operators defined in this section assume the existence of a null value, $\omega$, which we do not define, to be used for the fill values; in practice this corresponds to the NULL in SQL.

"This section" is the one that defines outer joins, which are used in the query you're asking about. So the answer appears to be **yes**.
> 0 votes

---
Tags: databases, relational-algebra, tuple-relational-calculus
---


# Question
Title: Longest substrings of common length with the same parity
Given two sequences $a$ and $b$, find largest $x$ such that in $a$ there is substring $A$ and substring $B$ in $b$ meeting those conditions:

1. length of both $A$ and $B$ is equal to $x$;
2. sum of elements in $A$ has the same parity as sum of elements in $B$.

Lengths of $a$ and $b$ are up to $5\times10^5$, so simple $O(n^2)$ solution won't do.

Example:
$a = \[0, 1, 2, 3, 4, 5\]$
$b = \[3, 1, 3, 6\]$
Answer: 3 (one of the possible solutions is $A = \[2, 3, 4\], B = \[3, 1, 3\]$).

I've thought about it for hours and can't find a solution. How to do this in linear or linearithmic time complexity?

I'm quite sure the problem can be simplified to for index $i$, storing only sum of elements up to $i$ modulo $2$. However, it doesn't help me much.

(The problem comes from a rather-old Israeli book תכנות תחרותי: סביב אתגרים ('Competetitive programming') by Mordechai Ben-Ari. The book isn't well known and I couldn't find any solution in Hebrew, so I translated the problem into English for a better chance of getting answer.)

Any help will be appreciated.

# Answer
> 2 votes
Here is an $O(n\log^2 n)$ solution.

The first step is to reduce to an easier problem:

> Given $x\_1,\ldots,x\_n \in \\{0,1\\}$, determine, for all $0 \leq i \leq n$ and $b \in \\{0,1\\}$, whether there is a contiguous subarray of length $i$ whose sum is equal to $b$ modulo 2.

Applying this to both $A$ and $B$, we can solve the original problem in $O(n)$.

The basic idea is to use divide and conquer. Given an array $x\_1,\ldots,x\_n$, divide it into two arrays $x\_1,\ldots,x\_m$ and $x\_{m+1},\ldots,x\_n$ of roughly equal size. Every contiguous subarray of $x\_1,\ldots,x\_n$ of length $i$ with parity $b$ has one of the following forms:

1. Contiguous subarray of $x\_1,\ldots,x\_m$ of length $i$ with parity $b$.
2. Contiguous subarray of $x\_{m+1},\ldots,x\_n$ of length $i$ with parity $b$.
3. The concatenation of a subarray $x\_{m-i\_1+1},\ldots,x\_m$ of parity $b\_1$ with a subarray $x\_{m+1},\ldots,x\_{m+i\_2}$ of parity $b\_2$, where $i\_1+i\_2 = i$ and $b\_1+b\_2 \equiv b \pmod{2}$.

We can determine whether subarrays of the first two forms exist, for all $i$ and $b$, by running the procedure recursively on the two halves. The interesting part is the third form. We start by determining the parity of all arrays of the form $x\_{m-i\_1+1},\ldots,x\_m$ and of the form $x\_{m+1},\ldots,x\_{m+i\_2}$ for all $i\_1,i\_2$, which takes time $O(n)$. Let $L\_{b\_1}$ be the set of $i\_1$ such that $x\_{m-i\_1+1},\ldots,x\_m$ has parity $b\_1$, and define $R\_{b\_2}$ analogously. Using FFT (exercise), for each $b\_1,b\_2$ we can determine in $O(n\log n)$ the set $X\_{b\_1b\_2}$ of $i$ such that there exist $i\_1 \in L\_{b\_1}$ and $i\_2 \in R\_{b\_2}$ summing to $i$. Given the sets $X\_{b\_1b\_2}$ for all $b\_1,b\_2$, we can determine whether subarrays of the third form exist, for all $i$ and $b$.

In total, denoting the running time of our algorithm by $T(n)$, we get the recurrence $$ T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + O(n\log n), $$ whose solution is $T(n) = O(n\log^2 n)$.

---
Tags: algorithms, strings, efficiency, substrings, algorithm-design
---


# Question
Title: Outputting numbers within a range that are not in a list
How could you design an efficient algorithm that uses the least amount of memory space and outputs, in ascending order, the list of integers in the range 0..255 that are not in a randomly generated list of 100 integers?

The aim is to output the number of such integers, and determine if the randomly generated list of 100 integers included any repeats.

The naive approach would be to compare each number from 0 to 255 against the list of 100 integers. This would not be very efficient.

What would be a more efficient approach to solve this?

# Answer
> 3 votes
Let $n$ be the number of random elements (in your case $n = 100$), and let $k$ be the total number of elements (in your case $k = 256$). Draconis gave a solution in time and space $O(k)$.

Another possible solution uses time $O(n\log n + k)$ and space $O(n)$:

1. Sort the input elements $A\[1\],\ldots,A\[n\]$.
2. Let $i \gets 1$.
3. For $j \gets 0,\ldots,k-1$:

* If $i \> n$ or $A\[i\] \neq j$: output $j$.
    * While $i \leq n$ and $A\[i\] = j$: let $i \gets i + 1$.

This is strictly better than the other solution if $n = o(k/\log k)$.

# Answer
> 3 votes
Facetious answer: all the sizes involved are constant, so a straightforward algorithm for this will run in $O(1)$.

Serious answer: with such small numbers involved, getting too elaborate may just slow you down. Simplicity is your friend.

```
let found be an array [0..255]
found ← [false, false, false...]

for i ← [1..100]:
    value ← A[i]
    if found[value] is true:
        there was a repeat
    found[value] ← true

for j ← [0..255]:
    if found[value] is false:
        j was not in the list

```

This runs in $O(n+k)$ time and $O(k)$ space (where $n$ is the number of elements in the array and $k$ is the maximum size of those elements). I don't believe it's possible to do better.

---
Tags: algorithms
---


# Question
Title: Design an algorithm for efficiently computing the k smallest numbers of the form a+b*sqrt(2)
Full question: Numbers of the form $a+b\sqrt{q}$, where $a$ and $b$ are nonnegative integers, and $q$ is an integer which is not he square of another integer, have special properties, e.g. they are closed under addition and multiplication. For $q=2$, some of the first few numbers of this form are given: $0 + 0\sqrt{2}, 1 + 0\sqrt{2}, 0 + 1\sqrt{2},\ldots$

Design an algorithm for efficiently computing the $k$ smallest numbers of the form $a+b\sqrt{2}$ for nonnegative integers $a$ and $b$.

(Hint: systematically enumerate points.)

I have the solution available. The first paragraph is: "A key fact about $\sqrt{2}$ is that it is irrational, i.e., it cannot equal to $a/b$ for any integers $a,b$. This implies that if $x + y\sqrt{2} = x' + y'\sqrt{2}$, where $x$ and $y$ are integers, then $x = x'$ and $y = y'$ (since otherwise $\sqrt{2} = (x-x')/(y-y')$).

I just don't see how knowing that $\sqrt{2}$ is irrational helps to reason about the problem, especially how it's a "key fact".

# Answer
> 1 votes
One way to solve this exercise is to notice that there are at least $k$ numbers of the form $a + b \sqrt{2}$ smaller than $\lfloor \sqrt{k} \rfloor + \lfloor \sqrt{k} \rfloor \sqrt{2}$ (namely, those with $0 \leq a,b \leq \sqrt{k}$). Conversely, every such number of the form $a + b \sqrt{2}$ must have $a,b \leq (1 + \sqrt{2})\sqrt{k}$. Therefore we could simply take all $O(k)$ values of the form $a+b\sqrt{2}$ with $a,b \leq (1+\sqrt{2})\sqrt{k}$, find the $k$th smallest in time $O(k)$, and then go over the list in $O(k)$ and output the $k$ smallest elements. The entire algorithm runs in time $O(k)$ (ignoring the cost of arithmetic operations).

This algorithm needs to compare two numbers of the form $a + b\sqrt{2}$. This can be done as follows. Suppose we want to determine whether $a + b \sqrt{2} \leq c + d \sqrt{2}$. If $a = c$ then this happens iff $b \leq d$, and similarly if $b = d$ then this happens iff $a \leq c$. Suppose, without loss of generality, that $d \> b$. If also $c \> a$ then $a + b \sqrt{2} \< c + d \sqrt{2}$, so suppose that $a \> c$. Then $$ a + b \sqrt{2} \leq c + d \sqrt{2} \Leftrightarrow a-c \leq (d-b) \sqrt{2} \Leftrightarrow \frac{a-c}{d-b} \leq \sqrt{2} \Leftrightarrow \\ \left(\frac{a-c}{d-b}\right)^2 \leq 2 \Leftrightarrow (a-c)^2 \leq 2(d-b)^2. $$

What would happen to this approach if we replaced $\sqrt{2}$ by, say, 2? Then there are only $O(\sqrt{k})$ numbers smaller than $\lfloor \sqrt{k} \rfloor + 2\lfloor \sqrt{k} \rfloor$, since not all combinations of the form $a + 2b$ for $0 \leq a,b \leq \sqrt{k}$ are distinct. Indeed, we need to take the upper bound on $a,b$ to be *linear* in $k$ in order to find the $k$ smallest values of the form $a + 2b$. So the irrationality of $\sqrt{2}$ does make a big difference for the algorithm.

---
Tags: algorithms, discrete-mathematics
---


# Question
Title: Does finding a cycle with $\log n$ length in $\text{P}$?
Let $G$ be an arbitrary graph with $n$ vertices and we want to find a simple cycle with $\log n$ length. Is there exists a known polynomial algorithm for this problem?

# Answer
> 7 votes
You can use color-coding, a celebrated technique due to Alon, Yuster and Zwick.

---
Tags: algorithms, complexity-theory, graphs, lower-bounds
---


# Question
Title: Can I program a universal Turing machine to accept arbitrary input encodings?
I've been reading about building Turing machines for specific purposes, and some sources talk about input encodings and some talk about programming specific machines, but I've been unable to find anything that discusses both. Here's a specific set-up:

> Suppose you have a universal Turing machine. It has a two-sided infinite tape, where the right side encodes a specific function to compute and the left side encodes the input to be provided to that function.

In general, I'm interested in the interaction between the encoding of the input, the specific program for the TM, and which UTM it is. My main question is:

> If I have a fixed underlying UTM, a fixed encoding of the input, and a desired function to compute, can I always find a way to program my UTM to compute that function on the input supplied in the specified encoding?
>
> For example, if I have the (2, 18) universal Turing machine, I encode the input using the system described here, and know that I want to compute the function $f(x, y, z) = x^3+xy+z^9$ is there guaranteed to be a program I can use to achieve this result?

I am under the impression that the answer is yes, but am not sure enough of my knowledge of Turing machine architecture to prove it.

More generally, if we think of this set up as having four parameters - the specific UTM, the specific input encoding, the specific function, and the specific program - is it always the case that if we fix three of these four parameters there will be a setting for the fourth?

# Answer
> 1 votes
I'm going to simplify your question, considering that a specific encoding for a universal Turing machine will necessarily include a method for the encoding of its programs. I'll also assume that the encoding of programs and their inputs are also interdependent, meaning that you can't define how the former is done well enough without defining how the latter is done, equally well, and vice-versa.

What's left for us to do then, is to be able to explore the correspondence between programs and mathematical functions. We know that there are functions that are definable, but not computable (there isn't a corresponding program). We tend to assume that every program is the encoding of a function, but that's debatable.

So, you ask (as I understand): if there is a program that computes a function under a specific encoding of the input, for a specific encoding of the machine on which it runs, *if one of these encodings change*, will the function still be "writable"?

The answer would have to be that, if this is not the case, then that proves the encodings are not really equivalent, i.e., the computational models they define are substantially different. In other words, with a change in encoding should come a proof of equivalence, and what that proof states is exactly that the different encodings should be able to write the same functions $-$ if writable they are.

# Answer
> 0 votes
Perhaps you are searching for the definition of computable functions. If your function is computable, there is a turing machine.

In more detail: If your desired function is expressible as a computable function on *any* encoding and if there is a computable translation between that single encoding and your desired encoding, then the function is computable on your desired encoding too.

For example let your desired function and encoding be `f : E -> V` (encoded input to result values). If there exists a positive integer `k` and computable functions `t1 : |N^k -> E` (surjective, with computable right-inverse) and `t2 : V -> |N` (injective, with computable left-inverse) such that the composition `g = t2 . f . t1 : |N -> |N` is computable (this might be proven by giving an algorithm for it), then `f` is computable too.

---
Tags: turing-machines, computation-models, code-generation
---


title: Minimizing DFA - Dead state elimination

text:
# Question
Title: Minimizing DFA - Dead state elimination
Following is a Question from a competitive exam, it is given that the solution is A but I don’t know why the dead state 4 is not eliminated.Dead states like 4 which has transitions only to itself, should be eliminated right?

***UPDATE:*** My solution to the question in the comment

# Answer
The given dfa (d) will be formed. As far as your question about removal of state r: it can't be removed because state q is having transition to state r on input b. This is necessary because a dfa cannot leave any input transition, that is, it must define all the transitions for each and every state and for each and every input given to those states.
> 2 votes

# Answer
There are two ways to define DFAs. In the more common way, for each state $q$ and symbol $\sigma$ there is exactly one edge exiting $q$ and labeled $\sigma$. In the lest common way, there is *at most* one such edge.

If you are using the second convention, then you are right that the dead state is not needed. But when using the first convention, dead states are necessary. Indeed, what should the automaton do upon reading $bb$? Any word starting $bb$ should be rejected, but the automaton has to reach some state upon reading $bb$; this is the dead state.
> 1 votes

---
Tags: formal-languages, automata, finite-automata
---


# Question
Title: 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)

# Answer
> 1 votes
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'$.

# Answer
> 0 votes
One way would be to show that, in any network, there is a maximum flow which has no flow coming into the source $s$. There are a couple more hints below; don't look at them unlessy ou need to.

Hint about how to do this:

> If is flow into $s$, there must be some cycle $sv\_1\dots v\_ks$ with positive flow around it. You can decrease the flow around that cycle to zero without affecting the total flow into the sink $t$.

Hint about why this is useful:

> It shows that adding edges into the source doesn't increase the network's capacity.

Essentially the same argument deals with out-edges from the sink.

---
Tags: network-flow
---


# Question
Title: What is the usage of a decision problem for an optimization problem like the longest path problem?
I just read this definition for the longest path problem:

> **LONGEST PATH**
> *Input*: A graph $G=(V,E)$, an integer $k$.
> *Question*: Is there a path with at least $k$ vertices in $G$

This seems a decision problem and a certificate can be verified easily. But, what is the usage of such a problem? Isn't the main concern finding the longest path in the graph? I guess that would be an optimization problem, and verifying a given certificate can't be done in polynomial time, so that is not $NP$. right?

If yes, then what is the usage of the decision problem (which is $NP$) and what is its relation to the main problem?

My question is different from "NP-complete" optimization problems because I also asked about the relationship between a decision problem and a relevant optimization problem, and how a decision problem may help us in solving the optimization problem, and basically what is their usage in such cases.

# Answer
In complexity theory, we tend to focus on decision problems. They're conceptually simpler and the corresponding function and optimization problems can be reduced to them with only a polynomial loss of efficiency. From a theoretical point of view, polynomial factors are considered "efficient".

Let's take your example of Longest Path. We know that the longest path has length between 1 and $n$ (where $n$ is the number of vertices), so we can find the actual length of the longest path by doing binary search using a series of queries of the form "Is there a path of length at least $n/2$?", "... $3n/4$?", ... That tells us that the longest path has some length $\ell$. Now, we can loop through the edges one by one. Delete the $i$th edge and ask, "Is there still a path of length at least $\ell$?" If there is, go on to the next edge; if there isn't, undelete edge $i$ and go on to the next one. When this algorithm terminates, we'll be left with a graph that is exactly a path of length $\ell$. We used $\Theta(\log n$) calls to Longest Path to find the length of the longest path, and $O(n^2)$ calls to find the actual path.

The decision problem isn't necessarily "useful" *per se*: as you observe, the function problem ("Give me a solution", rather than "Is there a solution?") is the one we usually want to solve, practically speaking.
> 2 votes

---
Tags: np-complete
---


# Question
Title: Making a profit as a high-dimensional store owner?
Been thinking about a problem recently and I am wondering if anyone can comment on some ideas to make solutions to this problem more efficient.

---

Let's say that I am some business owner with a set of $n$ possible store locations $L = \lbrace x\_i \in \mathbb{R}^m \rbrace\_{i=1}^n$, for $m \> 1$, where I'd like to build some new stores. I have estimates that each location $x\_i$ will cost $c\_i$ to build and should make a corresponding profit $p\_i$ after opening. Further, I have a budget of $B$ that I cannot exceed and all stores I build must be at least a distance $D$ away from each other based on the metric $d(\cdot,\cdot)$. My goal is to build stores such that I maximize my profit and stay within the desired constraints. Note that $(L,d)$ is a metric space.

Define $S = (s\_1, s\_2, \cdots, s\_n) \in \lbrace 0, 1 \rbrace^n$ such that $s\_i = 1$ means I am building a store at location $i$ and $s\_i = 0$ means I am not. It is clear that this optimization problem can be posed as:

\begin{align\*}& &&\max\_{S \in \lbrace 0, 1 \rbrace^n} \sum\_{i=1}^n p\_i s\_i \tag\*{}\\\&\text{subject to} &&\sum\_{i=1}^n c\_i s\_i \leq B \\\& && d( x\_j, x\_i ) \geq D \hspace{1cm} \forall j \> i \geq 1 \text{ where } s\_i = s\_j = 1 \end{align\*}

---

Now when looking at this problem, it is quite simple to solve it using dynamic programming if we assume the store locations are far enough apart that the distance constraint is automatically satisfied or the locations are all contained within some 1-dimensional affine subspace. Outside of this, things seem a bit complicated.

My thought is to initially construct a graph $G = (V,E)$ such that $V(G) = \lbrace 1, \cdots, n \rbrace$ and $E(G) = \lbrace ij \\;|\\; d(x\_i, x\_j) \geq D \rbrace$. From here, a simple but inefficient idea is to enumerate all cliques of $G$, solve them using dynamic programming, and choose the solution, across all of them, that's the best. This should be fine because each clique, by construction, is comprised of store locations that satisfy the distance constraints and in turn should individually allow for efficient solutions. This might be formalized by defining $\lbrace C\_1, C\_2, \cdots, C\_p \rbrace = \text{cliques}(G)$ as the set of cliques of $G$ and then solving

\begin{align\*}& &&\max\_{S^{(j)} \in \lbrace 0, 1 \rbrace^n} \sum\_{i = 1}^n p\_i s\_i^{(j)} \tag\*{}\\\&\text{subject to} &&\sum\_{i = 1}^n c\_i s\_i^{(j)} \leq B\\\& &&s\_i^{(j)} = 0 \hspace{1cm} i \in V(G) \setminus V(C\_j) \end{align\*}

for each $j^{th}$ clique $C\_j$. From here we then choose $S^\* = \arg \max\_{j \in \lbrace 1, \cdots, p \rbrace} \sum\_{i=1}^n p\_i s\_i^{(j)}$ as the optimal solution for the overall problem.

---

Obviously the crappy thing about the above approach is that we have to enumerate all the cliques, which may be both a large set and computationally demanding to find. Is there any structure to the problem I am missing that might make this solvable without enumerating all the cliques in this formulation? Perhaps there's a different perspective that could shed some light?

# Answer
I'm not sure why you would need to enumerate the cliques. You can encode the distance constraints explicitly in just a quadratic number of constraints.

\begin{align\*}& &&\max\_{S \in \lbrace 0, 1 \rbrace^n} \sum\_{i=1}^n p\_i s\_i \tag\*{}\\ &\text{subject to} &&\sum\_{i=1}^n c\_i s\_i \leq B \\ & && s\_i + s\_j \leq 1 \hspace{1cm} \forall j \> i \geq 1 \text{ where } d(x\_i, x\_j) \leq D \end{align\*}
> 2 votes

---
Tags: algorithms, graphs, computational-geometry, dynamic-programming, clique
---


# Question
Title: How can a computer run an infinite loop?
I understand the concept behind for and do/while loops, but I am trying to understand what is happening at the hardware level that allows a loop to run infinitely. Technically wouldn't it have to stop at some point because there are only a couple billion transistors in a microprocessor? Maybe my logic is off.

# Answer
> 26 votes
step 1: take a calculator

step 2: input a number

step 3: add 1 to the number

step 4: subtract 1 from the number

step 5: goto step 3

If you didn't eventually get tired or bored you would be switching between the 2 results forever. Computers don't get tired or bored.

# Answer
> 29 votes
In a contemporary processor there is, among many other things, a *register* (digital electronic component to hold some bits) called the **Program Counter** (**PC**). It holds the *memory address* to the current *machine instruction*.

During *normal flow* of the program, the *PC* will always be updated to address the **next** instruction. However, any *loop* will be implemented with so called **branch** or **jump** type instructions which will cause the *PC* to address some other instruction, rather than the next one.

One, if not *the*, simplest *infinite loop*, is one in which the *PC* is updated again to the **same** instruction.

An assembly (*MIPS*) code example (`beq` stands for *Branch on Equal*):

```
LABEL: beq $0, $0, LABEL # Comment: If 0 == 0,then goto LABEL.

```

# Answer
> 6 votes
At the most basic level, an "infinite loop" only requires two transistors — an astable multivibrator will alternate between two different digital states indefinitely as long as it has power. In some sense, every other loop is just a bigger version of this. You don't need more and more transistors to keep operating for a longer period of time.

But what you might notice is that the astable multivibrator only has two states. Q is on, then Q is off, then Q is on again. It can only do two things before it repeats. There isn't really anywhere else for it to go. This is a general limitation: a system with a finite state can only go through a finite *number* of states before it repeats. The more transistors you have, the more "interesting stuff" you can do *in* your infinite loop. But with "only a couple billion" transistors there are trillions of possible combinations, which is quite a lot. And that's not even counting the RAM, which adds more billions (or even a trillion) more bits of state, making the number of possible states that the system can be in truly massive. As such, it's possible (even fairly easy) to write a program that, e.g. generates prime numbers, and keeps running for longer than the probable lifetime of the hardware (or even the solar system), without running out of different possible combinations of on/off transistors.

# Answer
> 5 votes
You only need two transistors for that, as demonstrated by the old joke.

*How do you keep a (insert ethnicity here) busy forever?*

*Write "Please turn over" on both sides of a sheet of paper.*

It's as true for transistors as for humans with a sheet of paper. In this case, two transistors make a bistable oscillator, and they'll toggle between true and false for as long as there's power there.

# Answer
> 2 votes
One thing other answers have missed is that CPUs have a *clock source*, an external device (usually a quartz crystal oscillator) which switches from 0 to 1 and back a fixed number of times a second. This clock signal is what makes the CPU go from one instruction to the next. If the clock signal is too fast, the transistors that "perform" the instruction haven't finished charging up and so the results are garbled.

Modern CPUs do **very** complicated things for performance reasons but this is the basic idea.

Maybe that is enough to understand how the CPU moves from one thing to another thing and then moves back to the beginning. But I will go into a bit more detail.

Inside the CPU are memory cells using a fixed number of transistors which can be overwritten with new values. There is also a fixed number of transistors that perform various computations, like addition, comparison, and so on. The clock opens the gate to allow data to "flow" from the memory cells, through the "compute" portion, and then the result is allowed back into the memory cells.

So if your instructions are as follows:

```
1. x = 5
2. y = x + 1
3. Go to step 1

```

the processor will end up in *exactly* the same state when it starts each loop. (Well, in theory.)

---
Tags: loops
---


# Question
Title: Regular expression for $\{x : \#_{01}(x) \mod 3 = 0\}$
Let $L\_1$ be the language over alphabet $\\{0, 1\\}$ defined by $L\_1 = \\{x : \\#\_{01}(x) \mod 3 = 0\\}$.

Give a regular expression that denotes $L\_1$, and justify its correctness

---

# Attempt

Believe this is asking for number of $01$'s in $x$ but $|x|$ must be an even number. Like $x = 0101$, $|x| = |0101| = 4 \mod 3 = 1$ wouldn't work. However $x = 010101, |x| = 6$ would work?

How would I make a regex for this?

$R\_1 = (01)^\*$. How would I do the mod condition?

# Answer
Note that any amount of ones at the start or zeroes at the end has no influence on the number of $01$ pairs. Then in the middle you want any multiple of three of $01$ pairs, giving:

$$1^\*(0^+1^+0^+1^+0^+1^+)^\*0^\*$$
> 1 votes

---
Tags: regular-expressions
---


# Question
Title: Can a cycle be represented by L1 metric?
Let G be a graph that forms a cycle on $n$ vertices, with non-negative weights on the edges. Can you give each vertex v a vector $\mathbb{R}^m$ (for some $m\in \mathbb N^+$) such that the L1 distance (taxicab distance) between two vectors is the same as the distance between them in $G$?

Prove for a general circular graph or give a counter example with proof.

(I was told it is true so I have a good reason to think it is but I can't prove it.)

# Answer
Firstly for a fixed $n$, consider a path around the hypercube which is $$P\_n=(0,0,\dots,0)\to(1,0,\dots,0)\to(1,1,0,\dots,0)\to\dots\to(1,1,\dots,1)\to(0,1,\dots,1)\to\dots\to(0,0,\dots,0,1)\to(0,0,\dots,0).$$ Notice that if I give you two points $p,q\in P\_n$, then the $L\_1$-distance between $p$ and $q$ is exactly the distance between $p$ and $q$ in $P\_n$ (the shortest distance, not necessarily following the arrows in $P\_n$). Now, suppose we're given a cycle $C\_n$ with all edge weights $w\_e\in\mathbb{Z}^+$ and $w=\sum\_e w\_e$ is even. We will do the following: Let $p\_1=0$ and $p\_i=p\_{i-1}+w\_{i-1,i}$, so $p\_i$ is the weight of the path in $C\_n$ from vertex $1$ to vertex $i$ going clockwise. Label the vectors on $P\_{w/2}$ starting with $(0,0,\dots,0)$ having label $0$ and going around and map vertex $i$ of $C\_n$ to the $p\_i$'th vector in $P\_{w/2}$. By the previous comment, this is an $L\_1$-embedding.

Now, if each $w\_e$ is rational, we can find some $M$ for which $Mw\_e\in\mathbb{Z}$ for all $e$ and $M\sum\_e w\_e$ is even, so we can use the previous embedding and then scale.

Now for the irrationals.

Now, for a finite set $V$ and a subset $S\subseteq V$, we define the metric $\mu\_S$ on $V$ by $\mu\_S(x,x)=0$ and $\mu\_S(x,y)=\mathbf{1}\[|S\cap\\{x,y\\}|=1\]$ if $x\neq y$. It is not difficult to prove that any metric of the form $\mu=\sum\_{S\subseteq V}c\_S\mu\_S$ is $L\_1$-embeddable for any $c\_S\geq 0$. I claim that, in fact, if $V$ is any finite subset of $L\_1^n$, then there are constants $c\_S\geq 0$ for which $\Vert x-y\Vert\_1=\sum\_{S\subseteq V}c\_s\mu\_S(x,y)$ for every $x,y\in V$. First, if $V\subseteq L\_1^1$, then write the points $V=\\{v\_1\leq v\_2\leq\dots\leq v\_k\\}$. Then we have $$ \Vert x-y\Vert\_1=\sum\_{r=1}^k\Vert v\_{r+1}-v\_r\Vert\_1\mu\_{\\{v\_1,\dots,v\_r\\}}(x,y),$$ for any $x,y\in V$. For a general $V\subseteq L\_1^n$, we can do this construction in each coordinate direction $e\_i$ for $i\in\[n\]$ since the $L\_1$ metric is additive over the coordinates. Thus, if $\mu$ is a metric on a finite set $V$, then $\mu$ is $L\_1$-embeddable if and only if $\mu=\sum\_{S\subseteq V}c\_S\mu\_S$ for some constants $c\_S\geq 0$.

Now, suppose that some edge-weights are irrational, so suppose $w\_e^{(k)}$ are rational numbers with $w\_e^{(k)}\to w\_e$. Let $\mu^{(k)}$ be the metric induced by the weights $w\_e^{(k)}$. By above, we know that each $\mu^{(k)}$ is $L\_1$-embeddable, so we can write $\mu^{(k)}=\sum\_{S\subseteq V}c\_S^{(k)}\mu\_S$. By compactness, without loss, we may suppose $c\_S^{(k)}\to c\_S$. Finally, since $\mu^{(k)}\to\mu$, we must have $\mu=\sum\_{S\subseteq V}c\_S\mu\_S$, so $\mu$ must be $L\_1$-embeddable.
> 1 votes

---
Tags: graphs
---


# Question
Title: proof that BFS remains total after adding edge to graph
I'm trying to prove that if $G$ is a connected graph, then $BFS(u\in G)$ is total (i.e. it visits all the vertices of $G$).

The inductive proof consists in 2 cases:

(i) Prove that $\rm{BFS}$$(u \in \rm{G'})$ is total, where $\rm{G'} = G \cup (u,v) \quad u,v \in G$

(ii) Prove that $\rm{BFS}$$(u \in \rm{G'})$ is total, where $\rm{G'} = G \cup (u,v) \quad u \in G, v \not\in G$

I'm stuck at (i).

If I add a new edge $(u,v)$ to $G$, the $BFS$ will remain the same until it reaches $u$ or $v$, then it will add $v$ or $u$ to the queue (where one of them wouldn't be there). I understand that every other member of the queue is there, but there will be one more, so ignoring the fact that there is a new vertex in the queue, the $BFS$ will run in every other vertex just like it should.

How can I show formally that this new vertex in the queue will not interfere in the fact that the $BFS$ is total?

# Answer
> 1 votes
Let us assume that $G$ is a connected undirected finite graph.

Instead of by induction, a direct proof by contradiction as the following is probably easier and clearer.

Suppose we have just finished a BFS starting at vertex $s$. For the sake of contradiction, let us assume that there is a vertex $u$ of $G$ that is unvisited. Because $G$ is connected, there is a path from $s$ to $u$. Select the first unvisited vertex on that path and name it $u'$ (which may or may not be $u$). Let $s'$ be the vertex right before $u'$ on that path (which may or may not be $s$). Then $s'$ must be visited.

Now take a moment to reflect on BFS. Whenever a vertex is visited, each of it adjacent vertices must have been visited earlier or later; I will let you prove this proposition rigorously. However, this contradicts that $s'$, a visited vertex is adjacent to $u'$, an unvisited vertex. Our proof is done.

Here is the summary of the proof strategy. **A subset of vertices of a connected graph that is closed under adjacency must contain all vertices.** This also holds for infinite graphs.

---
Tags: graphs, graph-traversal
---


# Question
Title: Give a DFSA that accepts $L_1 = \{x : \#_{01}(x) \mod 3 = 0\}$ using as few states as possible
Let $L\_1$ be the language over alphabet $\\{0, 1\\}$ defined by $L\_1 = \\{x : \\#\_{01}(x) \mod 3 = 0\\}$.

Using as few states as possible, give a DFSA that accepts $L\_1$.

Also give an appropriate state invariant for your DFSA.

---

I have a regex for it and that is $1^\*(00^\*11^\*00^\*11^\*00^\*11^\*)1^\*$.

An example of accepted strings are: 100111010001. Example of a rejected string is 01010101, since |01010101| $= 4 \mod 3 = 1 \neq 0$.

How would I draw it? Also do I come up with state invariant first or draw the dfsa first? I drew the dfsa first right now

100111010001 - gets accepted. However 01010101 also gets accepted when it should be rejected. Not sure how to limit it to just mod 3

Edit:

I believe this works. (I cant use regexes in state invariants)

$q\_0$: $x$ must contain only $1$'s

$q\_1$: $x$ contains 1's before any 0's and ends with a 0

..

not sure how to write the state invariant for this case

# Answer
> 0 votes
Hint, a correct regular expression is $1^\*(00^\*11^\*00^\*11^\*00^\*11^\*)^\*0^\*$.

There are 6 states, where $q\_{0,1}$ is the initial state. Both $q\_{0,1}$ and $q\_{0,0}$ are accepting states.

$q\_{0,1}$: the number of 01s is a multiple of 3 and it ends with 1. Or empty word.
$q\_{0,0}$: the number of 01s is a multiple of 3 and it ends with 0.
$q\_{1,1}$: the number of 01s is 1 plus a multiple of 3 and it ends with 1.
$q\_{1,0}$: the number of 01s is 1 plus a multiple of 3 and it ends with 0.
$q\_{2,1}$: the number of 01s is 2 plus a multiple of 3 and it ends with 1.
$q\_{2,0}$: the number of 01s is 2 plus a multiple of 3 and it ends with 0.

---
Tags: automata
---


# Question
Title: Why is dominating set in $W[2]$, but independent set in $W[1]$
In Parameterized Complexity the Independent Set Problem for a Parameter $k$ ist $W\[1\]$-complete, and Dominating set is $W\[2\]$-complete. Now the prototypical $W\[1\]$ problem is deciding by a single-tape non-deterministic Turing machines if it has an accepting run with at most $k$ stepts, and for $W\[2\]$ it is the same notion with a multitape machine.

Intuitively they are both set selection problems, so a non-deterministic machine can guess in at most $k$ steps what elements to take into an independent (or dominating) set. So with this intuition, that the first problem ist in $W\[1\]$ is clear, but not why dominating set is not? So what am I missing, what is the distinguishing feature, why do we need a multitape machine for the second, but not for the first? My gut feeling would put domination set into $W\[1\]$, but that is not true as I know.

*EDIT*: I took the Turing machine definition of $W\[1\]$ from the following seminal paper Fixed-Parameter Tractability and Completeness I: Basic Results, but it is also written on wikipedia, together with the characterisation of $W\[2\]$. If you do not have access to the paper you can get a pdf from here, but the diagrams are missing in there (see page 6 for the definition of the Turing machine problem).

# Answer
> 3 votes
For deciding the independent or dominating set problem, it is not sufficient to guess the set. One must also verify that the guessed set indeed is an independent or a dominating set.

In the case of independent set, once the machine has guessed the set and stored it in the first $k$ cells of the tape, it checks for all pairs of guessed vertices whether they are indeed not equal and do not form an edge. There are $k\choose 2$ such pairs, so the overall running time is $O(k^2)$. Thus the reduction from independend set to short NTM acceptance is a parameterized reduction. The number of steps in the verification phase only depends on the parameter.

In the case of dominating set, one needs to checks whether all vertices are dominated. While above, we only had $k\choose 2$ pairs, now we have to deal with $n$ vertices. Which does not only depend on the parameter. (The way the multitape NTM solves this is by spending one tape per vertex.)

Of course, the above is only intended to give some intuition about why dominating set is not in W\[1\]. It does not give a proof. That would be way out of scope...

(For the sake of the casual reader, let me clarify that the NTMs above are not machines that solve the independent or dominating set problem. There is a reduction involved that converts instances of these problems into machines. Thus, a single such machine solves only a single instance of the problem, not the general problem.)

---
Tags: complexity-theory, graphs, parameterized-complexity
---


# Question
Title: What is the difference in SMO algorithm for SVM and SMO for one class?
Please let know if this is not the correct forum to ask this question. If not can anyone please tell where can I ask this question?

I am trying to understand the difference between the paper : https://pdfs.semanticscholar.org/59ee/e096b49d66f39891eb88a6c84cc89acba12d.pdf

and the paper http://users.cecs.anu.edu.au/~williams/papers/P132.pdf

The first paper is about SMO for SVM and the second paper is about SMO for one class. The question is what are the difference between this two algorithms? Also what are the common factors in both the paper?

The second paper has not shown any details of the algorithm so not sure what minimal change to be done on the first to get the second algorithm?

Given the code for the SMO for SVM, what minimum change would require to make the code suitable for one class SMO?

# Answer
> 0 votes
Both the papers attempt to develop Sequential Minimization Optimization (SMO) approaches for two kinds of Support Vector Machine (SVM) formulations, which include the conventional SVM and one-class SVM. The basic idea behind the SMO approach is to make the underlying SVM formulation scalable for larger datasets. This is a challenge since the SVM is a kernel method, and using it for large datasets requires computation of the kernel matrix whose size is of the order of the number of training samples. Thus, there is a high memory and computational requirement, moreover, issues pertaining to matrix stability may arise. In order to address this issue, the SMO approach adopts a method where pair-wise Lagrange multipliers are optimized instead of solving the entire Quadratic Programming Problem (QPP) as in the conventional case. The selection of the Lagrange multipliers may be based on heuristics. This (SMO) makes the approach (SVM) scalable for larger datasets, which is the underlying similarity between the use of SMO for SVM and one-class SVM.

In order to understand the difference between the two, it is important to understand the difference between the purpose of the SVM and one-class SVM, and subsequently the difference in their formulations (the optimization problem for each). This eventually translates into the difference in applying the SMO strategy for each of these cases.

The conventional SVM for binary classification aims to find a separating hyperplane $w^Tx+b=0$ with coefficients $w$ and bias $b$ for training data $x$ (and class labels $y$) with maximum margin ($\frac{1}{\\|w\\|\_2}$) which is at least unit distance from points of the two classes which lie close to the separating hyperplane. This is achieved by the soft-margin formulation involving trade-off using positively constrained slack variables $\xi$ and user-defined parameter $C$ as below:

$\min\_{w,b,\xi} \frac{1}{2} \\|w\\|\_2^2 + C \sum\_i \xi\_i$

subject to

$y^i (w^T x^i + b) + \xi\_i\geq 1$, $\xi\_i \geq 0$

In practice, the kernel trick is used to map the data to a high-dimensional kernel space $K$ that induces linear separability and the dual of the above formulation in terms of the Lagrange multipliers $\alpha$ is solved, which is given as

$\min\_{\alpha} \frac{1}{2} \sum\_i \sum\_j y^i y^j K(x^i,x^j) \alpha\_i \alpha\_j - \sum\_i \alpha\_i$

subject to

$\sum\_i \alpha\_i y^i = 0, \alpha\_i \geq 0$

On the other hand, in case of the one-class SVM, we would like to determine whether the test sample belongs to a specific class, determined by the training data (having $M$ samples), or not. Consequently, the one-class SVM is solved by

$\min\_{w,b,\xi} \frac{1}{2} \\|w\\|\_2^2 + \frac{1}{C M} \sum\_i \xi\_i - b$

subject to

$w^T x^i \geq (b - \xi\_i)$, $\xi\_i \geq 0$

The dual for the one-class SVM is then given as

$\min\_{\alpha} \frac{1}{2} \sum\_i \sum\_j K(x^i,x^j) \alpha\_i \alpha\_j$

subject to

$0 \leq \alpha\_i \leq \frac{1}{CM}, \sum\_i \alpha\_i = 1$

The derivation of the SMO algorithm follows the steps presented in the two papers, and the difference arises out of the nature of the two SVM formulations and their corresponding dual problems. Details of the derivation may be found in the respective papers, and newer strategies for selection of the Lagrange multipliers for optimization may also be found in literature.

---
Tags: algorithms, optimization, machine-learning
---


# Question
Title: Number of ways to choose same number of elements from two different sets
Given two sets of elements S and R, with p elements and q elements respectively. 1 \<= p,q \<= n. Now, the number of ways to choose same number of elements from set S and R is $$\sum\_{i=0}^{\min(p, q)} pCi * qCi$$. I want to calculate the result for all possible combinations of p and q. I can think of a O(n^3) solution by first calculating all the mCr values for all possible combinations of m and r. And then for each pair of (p, q) answer is the sum of products of the pre-calculated terms. Is there any way to do it within O(n^2) time?

# Answer
Sometimes a summation of products of binomial coefficients can be simplified using Vandermonde's identity.

In your case, Assuming $p\ge q$ we have $\sum^q\_{k=0}{p\choose k}{q\choose k}=\sum^q\_{k=0}{p\choose k}{q\choose q−k}$, which by Vandermonde equals $p+q\choose q$.

Actually this equality can be understood with elementary combinatorial arguments. Put the $p+q$ elements in one box. Now grabbing $q$ elements from the box means you have selected some $i$ elements from $S$ and $q−i$ elements from $R$. Or unselected $i$ elements from $R$ which is the same.
> 1 votes

---
Tags: combinatorics, discrete-mathematics
---


# Question
Title: Checking if the graph provided by a distance matrix is a tree
I came across this problem in an online judge: We are given a distance matrix consisting of $N$ rows and columns. The $i$th line of $j$th row is the distance between node $i$ and $j$ (not necessarily neighbors). The task is to find out if there exists a tree satisfying the given distance matrix or not. The only constraint is $1 \le N \le 2000$ and the time limit is 1 second.

Some sample test cases for clarity:

```
Input:
N = 3
0 2 7
2 0 9
7 9 0
Output:
True

Input:
N = 3
0 1 1
1 0 1
1 1 0
Output:
False

```

I couldn't find an answer that is feasible for implementing in a short period of time (this is kind of important for me as I participate in competitions sometimes). An idea came to my mind is that to take the distance matrix as it was an adjacency matrix and compute MST, and then run Dijkstra's SSSP from each vertex through this MST and generate a new distance matrix and finally compare if the initial distance matrix and the matrix we found are identical. I know that this solution is not efficient nor logical (and also I'm not sure if this would work correctly) and that's why I'm posting here for an answer. I can tell that the solution involves DSU (Disjoint Set Union) and DFS from the problem tags but it just didn't come to my mind.

# Answer
We can assume all weights are positive. Otherwise we can merge all pairs of nodes with distance $0$ to get an equivalent new distance matrix (a rigorous proof would be a little verbose here so I omit it).

---

We can process all distances **from small to large**. For a distance $d$ between node $u$ and node $v$, check if $u$ and $v$ are connected (initially there is no edge thus every pair of nodes is not connected). If they are not connected, add an edge with weight $d$ between them. Finally we will get a tree and we can check whether this tree satisfies the distance matrix.

To efficiently determine whether two nodes are connected, we can maintain a disjoint-set data structure where each disjoint set represents a connected component. With this data structure, we can build the tree in $O(N^2)$. In addition, computing all-pair distances in a tree takes $O(N^2)$ time, so the total running time is $O(N^2)$, which is sufficient for the constraints.

---

# Correctness of the Algorithm

If the algorithm reports "yes", then we indeed build a tree satisfying the distance matrix.

On the other hand, if there is a tree $T$ satisfying the distance matrix, we claim that our algorithm will build $T$ finally. We prove this claim by mathematical induction. Suppose our algorithm processes the distances of pairs $(u\_1,v\_1),(u\_2,v\_2),\ldots$ in order. Denote by $D(u,v)$ the distance between $u$ and $v$ in the distance matrix.

1. Our algorithm always adds the edge $(u\_1,v\_1)$ with weight $D(u\_1,v\_1)$, while there is always an edge $(u\_1,v\_1)$ with weight $D(u\_1,v\_1)$ in $T$.
2. Assume our algorithm agrees with $T$ for pairs $(u\_1,v\_1),\ldots,(u\_{n-1},v\_{n-1})$.

If there is an edge $(u\_n,v\_n)$ in $T$ (it must have weight $D(u\_n,v\_n)$), then $u\_n$ and $v\_n$ are not connected through edges $(u\_1,v\_1),\ldots,(u\_{n-1},v\_{n-1})$, which means our algorithm will add this edge by inductive assumption.

Otherwise, there is a path connecting $u\_n$ and $v\_n$ with length $D(u\_n,v\_n)$ in $T$. All of the edges in this path must have weights less than $D(u\_n,v\_n)$, thus are already added by our algorithm (again, by inductive assumption) when processing $(u\_n,v\_n)$. This means when our algorithm processes $(u\_n,v\_n)$, $u\_n$ and $v\_n$ are already connected, thus our algorithm will not add the edge $(u\_n,v\_n)$.

Now we have proved our algorithm indeed builds $T$, thus will report "yes".
> 0 votes

---
Tags: algorithms, graphs, trees
---


title: SIMD computational model

text:
# Question
Title: SIMD computational model
Flynn's taxonomy contains three interesting computer architectures: SISD, SIMD, MIMD.

* For the SISD architecture, we have RAM computational model that simulate real SISD systems very well;
* For the MIMD architecture, there is PRAM computation model that is capable to highlight main benefits of the parallel processing units that operate on the different part of a dataset (though, this model can't cope with the complexity of the real world parallel programs).

Are there any nice computational model for SIMD architecture?

# Answer
> 1 votes
I've found that Blelloch writes a book about data-parallelism: Vector models for data-parallel computing. In this work, he introduces a vector memory model (V-RAM). This model extends simple RAM with additional vector memory, that available to store an unlimited amount of homogeneous simple data types. Also, there is a vector processor that is capable to perform some "simple" operations with the vectors. Blelloch has a nice definition of the simple operation: he allows to use operations, that can be implemented in $O(n)$ time on RAM and also these operations must be contained in the $NC^1$ class of the boolean circuits.

This model is a very high level, but I think that it depicts the structure of SIMD processing more deeply than PRAM. Also, this model quite interesting by itself, because it wraps almost all parallel interaction of algorithm in the primitives and description of algorithms is purely sequential.

Does anyone know about the future of this model? Does it evolve or just stuck and no progress in done in this direction?

---
Tags: computation-models
---