# Question
Title: Is there a degree-2 SOS rewriting of the Goemans-Williamson rounding?
I use the same notation as I used in this previous question, About showing algorithmic gap instance for the Goemans-Williamson SDP The same definition continue.

Given a $f : \\{0,1\\}^n \rightarrow \mathbb{R}$ one defines a quantity called $\overline{sos}\_d(f)$ which is the smallest $c \in \mathbb{R}$ such that one can find functions on the Boolean hypercube $g\_1,g\_2,..,g\_t : \\{0,1\\}^n \rightarrow \mathbb{R}$ for some $t$ with $deg(g\_i) \leq d/2$ such that on the Boolean hypercube we have the equality, $c -f = \sum\_{i=1}^{t} g\_i ^2$

So one would say that $\overline{sos}\_d(f)$ is the minimum $c$ such that the inequality $c-f \geq 0$ has a \`\`degree-d SOS certificate" on the Boolean hypercube.

Now one claims that the GW algorithm for Max-Cut is "based on the upperbound $\overline{sos}\_2(f)$" and this in equation means that for the objective function of Max-Cut $f\_{Max-Cut(G)} = \sum\_{(i,j) \in E(G) } (x\_i -x\_j)^2$ we have,

$max(f\_{Max-Cut(G)}) \geq \alpha\_{GW} \overline{sos}\_2(f\_{Max-Cut(G)})$

* Is the above some immediate consequence of the GW analysis? Can someone kindly help recast that as this inequality if this is indeed true?
* Or if this inequality requires a separate proof then can someone kindly reference that? I haven't been able to find that..
* Do we know anything about say showing something like,

$max(f\_{Max-Cut(G)}) \geq (\alpha\_{GW} + \text{something positive}) \overline{sos}\_{\text{something greater than} 2 }(f\_{Max-Cut(G)})$ ?

# Answer
> 1 votes
The quadratic sum-of-squares relaxation of Max-Cut should indeed work out to be equivalent to the SDP that Goemans and Williamson solve. I encourage you to work this out yourself. This means that the Goemans-Williamson analysis indeed shows the inequality you mention.

You ask whether degree-2 SoS is a rewriting of the Goemans-Williamson rounding. It isn't. Rounding is a completely separate issue. Degree-2 SoS is a rewriting of the SDP that Goemans and Williamson solve. Rounding is how we bound the integrality gap.

Assuming the Unique Games Conjecture, $\alpha\_{GW}$ is the optimal approximation ratio achievable in polynomial time. Since optimizing degree $d$ sum-of-squares can be done in time $O(n^{O(d)})$, this implies (assuming UGC) that every *constant* degree $d$ has the same integrality gap $\alpha\_{GW}$ in the worst case.

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


# Question
Title: Transform grammar for repeating characters into LL(1)
I have the following simple production rule:

S -\> Sa | a

Which is left-recursive, and can recognize strings such as a or aa, etc

I tried to make it right-recursive, but I cannot find a way without creating ambigious grammars
(e.g.
S -\> aS'
S' -\> a | aS' )

Can someone explain how to make this grammar right-recursive and LL(1) form?

# Answer
Let's construct an LL(1) grammar for the language $\mathscr{L}(a^+)$.

Firstly, observe that all the production rules in this case must have one of two forms: $$A \to a\Gamma$$ or $$A \to \epsilon,$$ where $\Gamma$ is a (possibly empty) sequence of non-terminals and the terminal 'a'.

The first step would be adding the rule $S \to aS'$, since it's clear that $S \to aS \mid a$ doesn't give us an LL(1) grammar. Obviously $S'$ must have a production rule with the empty string as its body $S' \to \epsilon$, which will be used when we get the end of string symbol $\\$$ during parsing. We also need a "looping construct" to finish our construction, resulting in the following LL(1) grammar:

$$\begin{align} S &\to aS' \\ S' &\to \epsilon \mid aS' \end{align}$$

From wikipedia:

> A nonterminal is left-recursive if the leftmost symbol in one of its productions is itself (...) or can be made itself by some sequence of substitutions (...).

Since neither $S'$ nor $S$'s left-most non-terminal symbol cannot be 'made itself' by any sequence of substitutions (there are simply no left-most non-terminal symbols there), the resulting grammar is not left-recursive.
> 3 votes

# Answer
you can change your grammar in this way using epsilon symbol :

1. S -\> aS'
2. S' -\> e
3. S' -\> aS'

if you want to realize LL1 grammars , you can first read the example of simple Mathematical Grammar :

1. E -\> E + E
2. E -\> E * E
3. E -\> id
4. E -\> (E)

this grammar is ambiguous and left recursive too , so we can change it in this way :

1. E -\> TE'
2. E' -\> +TE'
3. E' -\> e
4. T -\> FT'
5. T' -\> \*FT'
6. T' -\> e
7. F -\> id
8. F -\> (E)

if you learn this so good you'll learn LL1 grammar
> 0 votes

---
Tags: formal-languages, left-recursion
---


# Question
Title: How can k-means be reduced to Integer Programming
The k-means algorithm reduces to computing the objective function:

$ \underset{\textbf{S}}{\operatorname{argmax}} \sum\_{i=1}^k \sum\_{\textbf{x}\_j\in\textbf{S}\_i} \lVert \textbf{x}\_j - \mathbf{\mu}\_i \rVert $

for some observations $\textbf{x}\_1,\ldots\textbf{x}\_n$ to be partitioned into sets $\textbf{S}\_i$.

How can this problem be reduced to an Integer Programming problem, which like k-means, is NP-hard.

# Answer
> 1 votes
I'm not sure if you can reduce this problem to an Integer Problem, because the centers are still continuous variables. There are ways to write equivalent Mixed-Integer Problems (i.e., both integer and continuous variables) but I struggle to formulate as a Linear one because of the Euclidean norm.

First you create a boolean variable $w\_{ij}$ for assignment. $w\_{ij} = 1$ means observation j belongs to cluster i (and zero means it does not belong). The following constraint ensures that one sample can only belong to one group: $$ \sum\_i{w\_{ij} = 1}, \forall i \in 1..k $$

You also create non-negative continuous variables $d\_{ij} \geq 0$ for distances between every observation j to every center, but use the Big M method to turn this distance zero if the observation does not belong to the cluster: $$ d\_{ij} \geq ||x\_j - \mu\_i|| - M(1 - w\_{ij}) $$

To select a value of M you can find the distance between the two points that are furthest from each other, or any other bigger value. If M is big enough and j doesn't belong to i, we have $d\_{ij} \geq L$ where L is negative, so the constraint is trivially satisfied - which means $d\_{ij}$ can assume any value greater or equal to zero. If j does belong to i, then the minimum value for $d\_{ij}$ is the euclidean distance between observation and cluster center.

(Note: you could use a multiplicative factor instead of Big M, like this: $ d\_{ij} = ||x\_j - \mu\_i||w\_{ij}$ - this is matematically accurate but generally doesn't work well in practice because it adds non-linearity. But since this norm is already non-linear, who knows?)

Now, if you minimize the distances (I saw in Wikipedia that the correct formulation tries to minimize the sum of distances), optimization will try to reduce every single value of $d\_{ij}$, so they will clamp to the correct distances if j belongs to i, and to zero if j doesn not belong to i:

$$ \min{\sum\_{ij}{d\_{ij}}} $$

I hope that helps.

---
Tags: complexity-theory, reductions, integer-programming, cluster
---


# Question
Title: Is it correct to say that CPUs only compute threads?
As a newcomer to the field of parallel computation, is it accurate to say that CPUs are essentially "thread" calculators? My current understanding is that a "process" is made up of multiple "threads" and a single core of a CPU can execute instructions from one "thread" at a time, sometimes a bit more with hyper-threading, but essentially it is computing threads. Once the CPU, along with all of its cores, have finished calculating all the "threads" that belong to a specific "process," then that "process" would be considered complete.

**So like an analogy of this concept would be:**

A CPU can be likened to a monkey, with N number of mouths (cores). Each mouth is responsible for eating a long chain of bananas (threads) out of wooden crates (processes). By connecting more banana chains from a program to an empty and waiting core/mouth, we can increase the rate at which the program is completed/emptied. A program is deemed complete once the wooden crate is emptied of all bananas.

**Would the following interpretation be correct?**

# Answer
Take a step back. In most operating systems, a *process* is an entity that owns resources, like memory areas, open files, and such. A *thread* is an entity that can be scheduled (i.e., get a CPU core assigned, has its own contents of registers and local variables). Several threads can exist within the same process, sharing it's resources.

Switching between threads that share memory means that the table pages and cache entries don't have to be flushed, and that is a major cost in current processors (today to access a word in memory can take the same time than hundreds of instructions!).

Note that some systems (like Linux) have a non-standard view of threads, in that you can create a new thread from an existing one and specify in detail exactly what they are to share.

Is using threads or processes a win? No way to answer in full generality. If different threads of execution don't use the same data, it won't matter much (see above), and it can be advantageous for them not to be able to trample on each other's work. Use processes. If they share data intimately, threads are a better match (and will be more efficient). But then again, having several cores accessing the same data gives rise to cache ping-pong and bad performance. Also, taking such a program and rewrite to run on a distributed system (note that current massive machines are NUMA, essentially separate machines connected by an insanely fast network, but still much slower than direct access to memory) will be much harder.
> 1 votes

---
Tags: parallel-computing, threads
---


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

---

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

---
Tags: graphs, algorithms
---


# Question
Title: Edge-connectivity of a weighted undirected graph
My question consists of two parts.

1. Let say the edge connectivity of a graph is *K*. I would like to change the edge connectivity value to *L (\> K)*. What is the best possible way to do so?

My guess: Obviously, we have to increase the edge weight of one of the critical edges (edges of the min-cut), but among the set of critical edges which edge should we choose?

2. After changing the weight of one of the critical edges, how could we find the new edge connectivity of the graph \[assume we have already computed the edge connectivity of the previous graph\]?

# Answer
This is generally known as "edge connectivity augmentation", and there is *a lot* of literature on the subject. There are several fast algorithms for the task, and they come in different flavors depending on what you know about your graph, or what you specifically care about.

A basic question is "what is the minimum number of edges (or minimum cost of edges) to be added to the graph $G$ to increase its edge connectivity to a certain value?".
> 1 votes

---
Tags: graphs, weighted-graphs
---


# Question
Title: Select a set of elements from a 2D matrix, such that each element comes from distinct row and column
We're facing following problem - an n * n 2D Matrix contains doubles (Java). Find a Set of elements such that

1. Each element in the set comes from a unique row and column combination. That is, once you've selected an element (i, j) as a candidate for a set, that set cannot contain any elements from ith row or jth column.
2. The size of the set is Maximized. The Matrix may contain NaNs, so it may not be possible to find a set of size n.
3. The sum of elements on this set is minimum over all sets of this size for this Matrix.

For Example, consider following matrix -

```
1 2 3 4
4 1 2 3
3 4 1 2
2 3 4 1

```

This is artificially constructed to demonstrate the problem, solution for this Matrix is going to be the diagonal elements

```
{1, 1, 1, 1}

```

Any ideas?

Just to be sure, this is *not* a homework problem. We're trying to solve this for a client. Problem we're trying to solve is in Transport domain, and basically boils down to problem statement above.

I've tried to think of a polytime solution, but the first condition seems to be problematic. If it was not in place, this would have been a trivial DP problem - create a temporary 2d array, traverse each row of original array, and for each element, try to find element in last row in temporary array that has the smallest cumulative sum. Make this element's value in temp\_arr smallest cumulative sum + this element. Find smallest element in last row and you're done.

I'm trying to see if there is a polynomial time solution. In all probability, it will be easier to code, verify, and debug than any graph theory based solutions.

Edit added after some search - Just realized that what I was looking for was Hungarian Algorithm for Assignment problem - https://en.wikipedia.org/wiki/Hungarian\_algorithm

# Answer
This is maximum matching in a weighted bipartite graph in disguise. (You can easily convert your objective of minimizing the sum of weights into one of maximizing it.)
> 2 votes

---
Tags: algorithms, graphs, arrays
---


# Question
Title: Quicksort $T(n)_{best}=\Omega(n\log n) $ proof
About the proof that quicksort has $T(n)\_{best}=\Omega(n\log n)$.

I can't find this specific aspect anywhere online which is strange. I'm going through a proof for this in a book and I don't understand something, it says that about analyzing the "cost" of a level in the recursion tree that:

> Since the recurrence relation for quicksort is: $T\_{best}= T(i-1)+T(n-i) + n$, then the cost of the root is $n$, and the cost of the level below it is $n-1$, in general: if a level has $x$ vertices, then the cost of the next level is smaller by $x$.

How is that possible? It's easy to see that each complete level has a total cost of $n$.

Also about the first level, if we plug $i=1$ to the equation, we indeed see that one recursive call (say left) leaves a "cost" of $n-1$ but the second call (say right) has a cost of $1$ so the total for the first level is $n$ and not $n-1$..

> The proof then goes on to say that level $i-1$ has at most $2^{i-1}$ vertices, therefore the cost of level $i$ is at least $n-(1+2+...2^{i-1}) \> n- 2^{i}$, therefore the cost of each of the $\log n $ levels is $\Omega (n)$.

Does anyone understand the part that I'm asking about?

Alternatively, is there a proper rigorous proof for this somewhere online?

# Answer
You mentioned the quicksort recursion: $$ T\_{best}(n) = \min\_i \[T\_{best}(i-1) + T\_{best}(n-i) + n\]. $$ Note how in this recursion $(i-1) + (n-i) = n-1$. This is because the two subproblems don't involve the pivot. This is the case for *any* node in the recursion tree: if a node corresponds to an array of length $m$, then its two children correspond to arrays of lengths $m\_1,m\_2$ where $m\_1 + m\_2 = m-1$. In particular, if a certain level has $x$ nodes then the sum of lengths at that level $S$ and the sum of lengths at the next level $T$ satisfies $S = T + x$; the $x$ pivots disappear from the recursion.

Denote by $N\_i$ the number of nodes at depth $i$, and by $S\_i$ the sum of lengths at depth $i$. Assuming we start counting at level 0, we have $S\_0 = n$, $S\_{i+1} = S\_i - N\_i$, and $N\_i \leq 2^i$. You can prove by induction that $$ S\_i \geq n - (2^i-1). $$ In particular, $S\_{\log\_2 n} \geq 1$ (assuming $n$ is a power of 2), so there are at least $\log\_2 n$ levels of recursion. Furthermore, $$ \sum\_{i=0}^{\log\_2 n} S\_i \geq \sum\_{i=0}^{\log\_2 n} (n+1-2^i) = (n+1)\log\_2 n - (2n-1) = \Omega(n\log n). $$ Since $\sum\_{i=0}^\infty S\_i$ is exactly the running time of quicksort (up to constants), we see that quicksort always takes at least $\Omega(n\log n)$.
> 2 votes

---
Tags: asymptotics, correctness-proof, quicksort
---


# Question
Title: Different probabilistic statement for Simple Uniform Hashing
Let me denote the number of elements with $n$ and the size of the table with $m$. I was trying to understand the Simple Uniform Hashing assumption that people and books describe in works and make them into equations and realize which of the different equations are equivalent and which are not.

Simple Uniform Hashing as described by CLRS in page 259 says:

> we shall assume that any given element is equally likely to hash into any of the m slots, independently of where any other element has hashed to.

So for that description I would mathematically write:

$$ Pr\[h(k) = i\] = \frac{1}{m}, \forall i \in \\{0,...,m-1 \\}$$

i.e. the probability that h(k) hashes to any index $i$ is equal to any index in the table of size $m$. Furthermore to satisfy the independence condition it requires I would also write:

$$ Pr\[h(k) = i\] = Pr\[h(k) = i \mid Ops\] = \frac{1}{m}, \forall Ops $$

Where $Ops$ is any set describing the keys that might have been hashed before $k$. So its conditionally independent of anything that might have happened before. Those are the equations and maths expressions I would use to describe uniform hashing.

However on page 260 (and on wikipedia ) we have a slightly differently phrased equation which I am having a hard time realizing if its the same as the one I wrote above which says:

$$ Pr\[h(k\_i) = h(k\_j) \] = \frac{1}{m}, k\_i \neq n\_j$$

i.e. the probability that two non-equal elements map to a spot of the table is $\frac{1}{m}$.

Are these two definitions the same? Why is the second used moe often than the first?

# Answer
They're not the same, but the one in Wikipedia is a consequence of the simple uniform hashing assumption.

Let $E$ be the event that $h(k\_1)=h(k\_2)$. Let $F\_x$ denote the event that $h(k\_1)=h(k\_2)=x$. Note that

$$E = \bigcup\_x F\_x,$$

and the events $F\_x$ are disjoint. Therefore,

$$\Pr\[E\] = \sum\_x \Pr\[F\_x\].$$

Now under the simple uniform hashing assumption,

$$\begin{align\*} \Pr\[F\_x\] &= \Pr\[h(k\_1)=x \land h(k\_2)=x\]\\ &= \Pr\[h(k\_1)=x | h(k\_2)=x\] \times \Pr\[h(k\_2)=x\]\\ &= \frac{1}{m} \times \frac{1}{m}\\ &= \frac{1}{m^2}. \end{align\*}$$

Plugging in, we find

$$\Pr\[E\] = \sum\_x \Pr\[F\_x\] = \sum\_x \frac{1}{m^2} = \frac{1}{m}$$

since there are $m$ possible values of $x$.

Therefore, if the simple uniform hashing assumption holds, then the equation you found in Wikipedia also holds. The reverse isn't necessarily true.
> 1 votes

---
Tags: algorithm-analysis, probability-theory, hash, hash-tables, hashing
---


# Question
Title: The most efficient algorithm for computing cardinality of sumset
Let A and B be two finite non-empty sets of positive integers. Their sumset is the set of all possible sums a + b where a is from A and b is from B. For example, if A = {1, 2} and B = {2, 3, 6} then A + B = {1 + 2, 1 + 3, 1 + 6, 2 + 2, 2 + 3, 2 + 6} = {3, 4, 5, 7, 8}.

As we can see, cardinality #(A + B) is less than sum of cardinalities #A + #B. So i wonder whether we can calculate #(A+B) faster than just calculating all #A + #B sums and inserting them in some set-like data structure.

I've tried searching "sumset cardinality algorithm" and so on but didn't succeed.

P.S. We may assume that there is some constan K, not very lare - for example 10^5, such that 1 \<= #A, #B \<= K and all the elements of A and B are between 1 and K

# Answer
Use the FFT. The characteristic vector of $A+B$ is the convolution of the characteristic vectors for $A$ and for $B$. Convolutions can be computed efficiently using a FFT. As long as every element of $A,B$ is not too large, this will be efficient: the running time will be approximately $O(n \lg n)$ if $A,B \subseteq \\{1,2,\dots,n\\}$.
> 0 votes

---
Tags: algorithms, counting
---


# Question
Title: Proving that a programming language is not regular
I am wanting to show that the C programming language is not a regular language.

The alphabet would be ASCII characters and comments, strings, char can contain arbitrary characters.

Would I best approach this potentially with a pumping lemma? There's not really constraints or anything, this is more of a creative concept :)

Thanks!

# Answer
Yes, the pumping lemma will work fine, as would Myhill–Nerode. There's a hint below; mouse-over to see it but try without.

> Use the fact that C requires braces to be well-nested.
> 2 votes

---
Tags: formal-languages, regular-languages
---


# Question
Title: What is the role of mathematics in programming?
I am almost totally uneducated in programming and computer science in general, though I am really fascinated by these topics. I read that mathematics is important in programming and that nowadays many mathematicians specialise in applied mathematics in this field. So, I wonder how these two branches are linked with each other. What are the fields of mathematics that are useful (maybe unavoidable?) in writing a computer program?

# Answer
You don't need any math to write a Hello World or a very simple website.

You will need to know some discrete mathematics and algorithm analysis to write a program that finds a route between two cities.

You will need to know matrix transformations and quaternions to write a game engine.

You will need to know a lot about all kinds of mathematical fields to write the next Wolfram Mathematica.

What I'm trying to say, what fields of mathematics you will need to know and to what degree will depend a lot on what kind of programs do you want to write. But the ones that tend to be most widely useful are data structures, algorithms and their analysis.
> 17 votes

# Answer
You pose two questions.

1. Which is the role of mathematics in programming?

Quite fundamental. It is the universe of computers and programs. I mean no exaggeration. It describes the framework in which they exists. It provides the tools to analyze computer programs, e.g. it is used to prove the correctness of computer programs, completeness, all sorts of other properties. It is important to know that a program will work as expected, or will finish. Even a simple "hello world". You can really break it down and prove it, to the logical level. There are formal definitions of what a program is, and what a computer is.

2. Which are the fields of mathematics that are useful (maybe unavoidable?) in writing a computer program?

Unavoidable? None. Just as you don't need physics and engineering to build simple stuff.

Useful? Depends, and opinionated. The beauty of it is, to abstract and reuse tools. Some people create algorithms, some people use them to write libraries, some people use them to write services or games. Math is useful on a pretty low level, unless it is directly related to the task that a program is solving.

I would say, that fields that give a nice set of general soft skills useful for programming are logic, combinatorics and algebra, because they develop the ability to complex abstract thinking, organize things and transforming problems. I'd say skills that are very useful in seeing a "bigger picture". It's always nice to spot common functionality, reduce complex problems/tasks and avoid caveats as a programmer.
> 6 votes

# Answer
One can write a computer program without mathematics. However, when you start wanting to demonstrate that you wrote the *right* program, you typically have to turn to mathematics to prove it. For example, many parts of a program are terribly hard to prove out without using mathematical induction. Now that's not to say you're using complex mathematics. Not many programmers have to use differential equations on a daily basis, but you do need to understand the basics, such as how to make a proof.

The specialists in the field push the limits of what computing could theoretically do. For example, cryptographers make some rather demanding statements about what their algorithms can do. Many claims in that field could require eons of computing power to prove by doing it, but can be proven using a few pages of mathematics. However, that is a case by case thing. Most developers never dabble in cryptography (in fact, cryptographers bristle when you suggest it, because it's so unbelievably easy to write *bad* crypto if you don't have the background).
> 3 votes

# Answer
As svick mentioned, it depends on what you do. I can add some insights from my experience. If you are interested in just using machine learning (ML), then some math is recommended to understand what's going on. If you want to develop ML, then your math must be much more advanced, you need: advanced calculus, probability theory and linear algebra. But all this math can be learned online

Good luck
> 0 votes

---
Tags: programming-languages, mathematical-foundations
---


# Question
Title: How broken is LCG in the case of partial output?
Suppose we have a linear congruential generator defined by $X\_{n+1} = (a X\_n + c) \mod 2^n$ where $a, c, n$ are all known and we would like to determine the initial value $X\_0$. However, if we can only see the $k$ high-order bits of each of the $X\_i$ for $i \geq 0$, the best algorithm I know of is a brute force which tries $O(2^{n-2k})$ possibilities, and this is exponential in $n$.

Compare this to the Mersenne Twister, whose initial state can be computed in polynomial time given only the high-order bits of each output (it reduces to solving a system of $n$ equations in $n$ unknowns). Is there a better algorithm out there which can solve for the initial state of an LCG given only the high-order bits of each output, and if not, is LCG actually broken?

# Answer
Yes, there are techniques based on lattice reduction that are faster than brute force. See, e.g., https://crypto.stackexchange.com/a/20714/351, especially the first 3 papers cited there.

One can also use meet-in-the-middle techniques to get the running time down to $O(2^{(n - k)/2})$ if $k \ge n/2$: see https://crypto.stackexchange.com/a/10609/351.
> 2 votes

---
Tags: algorithms, cryptography, randomness, sampling, pseudo-random-generators
---


# Question
Title: Is it a good idea to determine coordinates of object on images with regression algorithms?
I am doing doing one of getting started competitions on kaggle, the one which requires you to find coordinates of different objects on images.

I know that the usual method for this is to use sliding window and predict whether some piece of image is that object. But I wonder, what if I just use values of all pixels as features and try to teach a regression algorithm how to predict the coordinates of the object on that image? What kind of regression algorithm would be best?

# Answer
It is possible to train a neural network to solve a regression problem. See facial keypoints challenge You should note that training a network for regression is harder then training towards a classification problem. The network is more prone to unnormalised, different deviation values per feature, weight initialisation etc. Try following the tutorial and then you'll have a better grasp on using ConvNets for regression.

Good luck!
> 1 votes

---
Tags: machine-learning, computer-vision
---


# Question
Title: Proving that English is not a regular language
I am wanting to try and prove that the English language is not regular. The alphabet is the set of all words in the English dictionary.

Looking at sentences, I was able to use this pattern of sentences

{ \[ (determiner) (noun)\]n (verb)n where n is \>= 1} ⊆ of the English language

and { \[ (determiner) (noun)\]m (verb)n where m ≠ n} ∩ of English

---

determiner is anything like the, my etc. Noun is any noun and verb is also any verb.

All three of these (determiner, noun, and verb) are finite and disjoint. Would something like pumping lemma be a good way to approach this?

# Answer
It is not easy to prove the complexities of natural languages. See Complexity of natural languages for some hint that English language is not regular.

In fact in Evidence Against the Context-Freeness of Natural Language, Stuart M. Shieber shows that many natural languages are not even context-free.

However, I only know about Dutch and a dialect of Swiss German, for which proof of non context-freeness exists. And the proofs are quite old, the results about them were proved in 1980s.

For detail you can also refer - The Handbook of Computational Linguistics and Natural Language Processing edited by Alexander Clark, Chris Fox, Shalom Lappin.
> 2 votes

---
Tags: formal-languages, regular-languages, natural-language-processing
---


# Question
Title: How do you express the theorem statement about unsuccessful search on average-case for unsuccessful searches in hashing with quantifiers?
I was reading CLRS and in theorem 11.1 it states:

> In a hash table in which collisions are resolved by chaining, an unsuccessful search takes average-case time $\Theta( 1 + \alpha )$, under the assumption of simple uniform hashing.

I was trying to understand how to express this theorem with quantifiers ($\exists, \forall$) and how it relates to "average-case" time (precisely, what they mean with average case time).

Is the theorem a statement that holds for all or any key? Or does it hold for all key on average and what does "on average" mean rigorously?

Usually, I like separating the terms expectation and average because the have different meanings. Expectation usually I think of it as the expected value of something according to some underlying distribution. For Average I think of the average value given a sample. So with these in mind, is the "average-case" scenario the same as the average running time for any key? i.e. Let $T\_k$ denote the amount of time to search of a key $k$. This is a random quantity because it depends on the key we search for. Define the average-case runtime for any search to be $Search = \sum^n\_{k=1} T\_k$. Is the theorem statement in CLRS statement about the random variable $Search$ I just defined? (Which takes into account all keys at once and hence, applied for "any key" I guess). Or what do they mean by average-case precisely?

# Answer
> 3 votes
There are two prominent uses of the term "average" in algorithm analysis.

1. **Average-case** as a special case of expected costs

Here, "average case" just means "expected case w.r.t. uniform distribution". Since we *usually* analyse with uniform inputs in mind (everything else is hard, and there's not much reason to prefer one distribution over the other in most cases).

*Example:* the average-case running-time cost of sorting algorithms is often analyzed w.r.t uniformly-random permutations.
2. **Average cost** in the classic sense.

When analyzing data structures, we can look at average costs across the contained elements *for a fixed instance* -- no probability distribution here (well, you *could*...). That is, we may still have/want to consider a worst-, average- or best-case instance.

*Example:* Consider BSTs. The average search cost of a *given tree* is the total cost for searching all contained elements (one after the other) divided by the number of contained elements. This is a classic quantity in AofA called internal path length.

**Note:** There are situations where average and expected do not usually mean the same thing. For instance, the expected (also: average-case) height of BSTs is in $O(\log n)$ but the average height is in $\Theta(\sqrt{n})$. That is because "expected" is implicitly (by tradition) meant w.r.t. uniformly-random permutations of insertion operations whereas "average" means the average over all BSTs of a given size. The two distributions are not the same, and apparently significantly so!

*Recommendation:* Whenever you use "expected" or "average-case", be very clear about which quantities are random w.r.t. which distribution.

---

The specific sentence you quote is indeed not clear if read in isolation -- if you ignore that CLRS specify exactly what "simple uniform hashing" means on the very same page.

There are two potentially random variables here: 1) the content of the hashtable itself, and 2) the key searched for. *Simple uniform hashing* is a simple way of specifying both.

1. We abstract from sequences of insertions¹ and just assume that every one of the $n$ elements we inserted independently hashed to each of the $m$ addresses with probability $1/m$.
2. We assume that the searched key hashes to each address with probabilty $1/m$.

That's how the proof works: our search hits each list with probability $1/m$ (cf 2), and they all have the same expected length of $n/m$ (via 1). Hence, the expected cost (under this specific model) for searching for $x$ *not* in the table is proportional to

$\qquad\displaystyle\begin{align\*} T\_u(x,n,m) &= 1 + \sum\_{i=1}^m \operatorname{Pr}\[h(x) = i\] \cdot \mathbb{E}\[\operatorname{length}(T\[i\])\] \\ &\overset{1,2}{=} 1 +\sum\_{i=1}^m \frac{1}{m} \cdot \frac{n}{m} \\ &= 1 + \frac{n}{m}. \end{align\*}$

The "$+1$" is there to account for computing $h(x)$ and accessing $T\[h(x)\]$, the sum represents the cost for searching along the list.

---

1. That is fair since the sequence of insertions does not have as much impact on the resulting structure as for, say, BSTs. The hash function shakes everything up. We don't want to talk about the precise interaction of sequence and hash function, so we just assume that the result of both is independently uniform -- that's something we can work with. It may not represent reality, of course!

# Answer
> 2 votes
The average-case running time (or expected running time) of a randomized algorithm is typically defined to be the expectation of the running time of the algorithm, with respect to the random coins used by the algorithm (i.e., the random bits used internally in the algorithm).

If this number depends on the input, we often choose the worst case over all inputs. If it matters, a good source should say what it means.

Note that this has nothing to do with amortized analysis. Amortized running time is something completely different; it is about the running time of a *sequence* of operation, and applies equally well to deterministic algorithms, whereas average-case running time applies only to randomized algorithms.

---

Therefore, the statement you are quoting means: for all keys, the running time to search for a particular key is a random variable whose expectation is $\Theta(1+\alpha)$. (It's a random variable, because the running time depends on the randomness in the hash function.)

---

Caveat: You may occasionally find some situations where a particular distribution on the inputs is specified, and one takes the expectation of the running time with respect to the random choice of input. However, this usage is rare and it would probably be poor form to use average-case for this meaning, if it's not clear from context that this is what was intended.

---
Tags: algorithm-analysis, terminology, data-structures, hash-tables, average-case
---


# Question
Title: What is the correct way to define time constructible functions?
Sipser defines a time constructible function as

> $f(n)$ is time constructible if there exists a turing machine which given input $1^n$ writes value of $f(n)$ in binary to the output tape in $O(f(n))$ time.

whereas Sanjeev Arora and Barak defines it as

> $f(n)$ is time constructible if there exists a turing machine which given input $1^n$ writes value of $1^{f(n)}$ in binary to the output tape in $O(f(n))$ time.

I am unable to see how are these two definitions equivalent. Isn't there a case where writing value in binary takes less time that writing it in unary ? Also what is the reason for inputs being given in unary rather than binary or some other base $k \> 2 $ ?

# Answer
> 1 votes
The two definitions are probably equivalent (perhaps $f(n)$ need be not too small): given $f(n)$ in binary you can write $1^{f(n)}$ in $O(f(n))$ time, and vice versa. The ideas are as follows.

Binary to unary: Inductively construct $1^{b\_m b\_{m-1} \ldots b\_{m-t}}$, where $b\_m\ldots b\_0$ is the binary representation of $1^{f(n)}$. At each step we need to roughly double the string of 1s, and in stage $t$ this takes roughly $O(f(n)/2^{m-t})$ time. Taking into account all stages, we get roughly $O(f(n))$.

Unary to binary: Construct the binary representation of $f(n)$ from LSB to MSB by repeatedly dividing $f(n)$ by two. The $t$th division by two requires time $O(f(n)/2^t)$, so overall this runs in time roughly $O(f(n))$.

As to why the input is in unary rather than in binary, this ionly affects small $f(n)$; as we have seen, converting between $1^n$ and $n$ should take time $O(n)$, and this is affordable as long as $f(n) = \Omega(n)$.

---
Tags: complexity-theory, time-complexity
---


title: Index of a language and its reversal

text:
# Question
Title: Index of a language and its reversal
The index of a language is the number of Myhill-Nerode classes that it has. It is also equal to the number of states in the minimal DFA for the language. What is an example of a language that has a different index from its reversal?

# Answer
> 4 votes
The $k$th letter equals $a$, for fixed $k$, assuming a two letter alphabet.

This generic answer is made precise in the comment by @AntonTrunov below.

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


title: Time complexity of function call

text:
# Question
Title: Time complexity of function call
what would be the complexity of such program? Code:

```
for(i=0;i<n;i++)
{
   g(n);  //any function call
}

```

# Answer
Assuming that $g$ doesn't have any side effects, the complexity of this program is (up to constants) $n$ times the complexity of $g(n)$.

If $g$ does have side effects, then the time complexity of $g$ isn't well-defined. However, if the time complexity $T\_g$ of $g$ satisfies $T\_g(n) = O(G(n))$, then your code is $O(nG(n))$, and similarly if $T\_g(n) = \Omega(G(n))$ then your code is $\Omega(n(G(n))$.
> 3 votes

---
Tags: algorithms, algorithm-analysis
---


# Question
Title: Approximation Algorithm for Independet Set Problem: Any Explanation Please?
I am reading this note on approximation algorithms for independet set problem. I am confused of *Theorem 1.* and *Corollary 3.*

Here is the statement of *Theorem 1.*

**Theorem 1 (Hastad \[1\])** Unless P = NP there is no $\frac{1}{n^{1-\epsilon}}$-approximation for MIS for any fixed $\epsilon\>0$ where $n$ is the number of nodes in the given graph.

Here is the statement of *Corollary 3.*

**Corollary 3** Greedy gives a $\frac{1}{\Delta+1}$-approximation for (unweighted) MIS in graphs of degree at most $\Delta$.

I feel like there is a contradiction between *Theorem 1.* and *Corollary 3.*, no? Or because the graph in *Corollary 3.* is a special one with degree at most $\Delta$?

---

\[1\] J. Hastad. "Clique is Hard to Approximate within $n^{1-\epsilon}$". Acta Mathematica, 182:105{142, 1999.

# Answer
In general, the maximal degree in a graph can be as large as $n-1$. Therefore on general graphs, the greedy algorithm is only guaranteed to give a $1/n$ approximation, which you can also obtain by returning an arbitrary vertex.

What Corollary 3 does imply is that the graphs that Håstad uses have maximal degree $\Omega(n^{1-\epsilon})$.
> 4 votes

---
Tags: approximation
---


# Question
Title: How to make sense of this context-sensitive production in a textbook? (a typo perhaps?)
In Chapter 1 of Kenneth Slonneger and Barry L. Kurtz's *Formal Syntax and Semantics of Programming Languages: A Laboratory Based Approach*, an example of its production is given to illustrate the nature of context-sensitive grammar (page 3):

```
<thing> b ::= b <thing>

```

where `<thing>` is a non-terminal and `b` is a terminal.

I cannot see how this fits the form

$$αAβ → αγβ $$ <sub>(where $α$ and $β$ are strings, $A$ is a non-terminal and $γ$ is a non-empty string)</sub> for context-sensitive grammar unless the right hand side ends with $b$ as well:

```
<thing> b ::= b <thing> b

```

in which case we get $α=ε$, $β=b$ and $γ = b\\; \text{\<thing\>}$.

Perhaps I haven't viewed it in the right angle? (Or is this a typo?)

# Answer
> 6 votes
First, they describe noncontracting grammars, and give an example: the one you are quoting.

Next, they write: *equivalently*, we can use a different restriction on grammars, and describe the context-sensitive grammars.

Chomsky proved the equivalence in 1963.

---
Tags: formal-grammars, context-sensitive
---


title: Regular Expression simplification

text:
# Question
Title: Regular Expression simplification
Does $(0 + 10^{\*}1)^{\*}$ simplify to the following language: Set of all binary strings with even number of ones. In specific, does the * inside the brackets get evaluated first or the outer * gets evaluated first. Or does it even matter while simplifying as what we finally need is the set of all strings possible with this expression?

# Answer
> 2 votes
Yes, $(0+10^\*1)^∗$ denotes the set of all binary strings with even number of ones. Or more technically $L(\ (0+10^\*1)^∗ \ ) = \\{ w \ |\ w$ is a binary string containing even number of 1's $\\}$. We denote language of a regular expression $E$ as $L(E)$.

To understand regular expressions, you need to understand the recursive definition of regular expressions.

if $E$ and $F$ are regular expressions $E$+$F$ is regular expression.
if $E$ and $F$ are regular expressions $EF$ is regular expression.
if $E$ is regular expression $E^\*$ is regular expression.
For basis, $\epsilon$ and symbols from alphabet $\Sigma$ are also regular expressions.

Next language of regular expressions for each of the above operations is defined: union, concatenation and repetition, respectively. For basis, it is sets of empty string or a single symbol, as the case may be.

Now if $w \in L(E)$ then $L(E^\*)$ is not just $wwwww...$, it is also any $w\_1w\_2w\_3...$ (0 or more times) such that $w\_1 \in L(E)$, $w\_2 \in L(E)$, $w\_3 \in L(E)$, etc.

So $(0+10^\*1)^\*$ is really $(0+10^\*1)(0+10^\*1)(0+10^\*1)...$ (0 or more times). Thus, you work with the outer $\*$ operator first and then work with the inner $\*$ operator.

Next comes the question of simplification. Either you want to describe the language of a regular expression in most simplest manner possible, or you want to describe the most simple regular expression for a given language. Both these are hard to do. Even if you are given a minimum DFA of the language, to compute minimum regular expression for it is NP-complete (the decision version: does there exist a regular expression of less than $k$ length for the given DFA).

We can minimize DFA but unfortunately we do not have efficient algorithms to minimize NFA or regular expressions unless $P = PSPACE$. See Minimizing NFA’s and Regular Expressions Gregor Gramlich and Georg Schnitger.

However $(0+10^\*1)^\*$ is set of all binary strings with even number of ones. Yet another expressions are $0^\*(10^\*10^\*)^\*$, $(0^\*10^\*1)^\*0^\*$, $(0^\*10^\*10^\*)^\*$ and so on. The outline of proof that the regular expression $(0+10^\*1)^\*$ is indeed the language mentioned above is as follows:

First we draw a DFA for the language. If we eliminate the state $q\_1$ we get the equivalent (enhanced) DFA in the right. It is easy to see that the equivalent regular expression is same. This is kind of reverse-engineering.

Sometimes it is easy to go this way, rather than finding the language of regular expression by automated procedures. Sometimes we can use regular expression algebra also to analyze and simplify regular expressions.

# Answer
> 2 votes
One way to go about this is to show that $S=T$, where

$S = $ the set of all strings over $\\{0,1\\}$ containing an even number of 1s,

$T = $ the set of all strings which can be represented by the regexp $(0+10^\*1)^\*$

Showing that $S\subseteq T$ can be done by induction on the number of 1's in a string and showing that $T\subseteq S$ is even easier.

# Answer
> 2 votes
(*This is not a question on formally proving the meaning of expressions and their equivalence, but on how to read them.*)

I see your point: if you match an expression with a string then the outer $\*$ fixes the number of pairs of $1$'s, and the inner $\*$ determines the number of $0$'s in between each of these pairs. That suggests outside in.

Technically the meaning ("evaluation") of $10^\*1$ however is not choosing a single string, but the full language of any number of $0$'s between two $1$'s. Then (once the inside language is evaluated) we concatenate arbitrary sequences of elements in the string. That definitely is inside-out.

Compare this with another example. The expression $(0+1)^\*$ has the same source of confusion. It is not: I choose either $0$ or $1$, and then repeat that letter, but I repeat the choice $0$ or $1$ while concatenating. That seems outside-in, however the evaluation of $(0+1)$ is not a single letter, but of the set $\\{0,1\\}$. Then the star evaluates that to $\\{0,1\\}^\*$, the set of all strings over $\\{0,1\\}$.

---
Tags: formal-languages, regular-languages, regular-expressions
---


# Question
Title: Functional programming with branches that have no order?
I was wondering if there is any programming style in which the outcome does not depend on the order of statements or groups of statements such as guards. Vaguely, I imagine this would leave room for things like optimization or parallelization. Using the functional language Haskell as an example:

```
f x
 | x < 0 = -1
 | x > 0 = 1
 | otherwise = 0

```

is the same as:

```
f' x
 | x > 0 = 1
 | x < 0 = -1
 | otherwise = 0

```

Is it possible in some languages or paradigms to make the semantics of the function not dependent on the order in which the branches are defined (probably with special treatment of the `otherwise` case)?

# Answer
Here's the problem:

1. You always need some way to resolve ambiguity when there are overlapping clauses
2. There is no easy syntactic way to ensure that clauses don't overlap.

So, if you can think of a way for the behavior of `if` to be well defined when there are overlapping clauses, that doesn't depend on the ordering of the clauses, then you can do what you're asking for.

And, there are, of course, a bunch of ways to define this: you could always default to the simplest matching condition (with the shortest code), you could attach an integer at runtime to each case and use the one with the highest number, etc.

But at their core, the process of looking at overlapping cases and choosing one, basically involves ordering the cases in some way. Requiring the user to specify the ordering, and having the order in the source code match the "priority" of each clause, seems like the simplest option.

There is likely a way to ensure that ordering doesn't matter in a dependently-typed language, when you can actually construct a proof that all your clauses are mutually exclusive. Or, you can re-order clauses in an optimizer, if a static analyzer identifies a place where all the clauses are mutually exclusive.

Or, if you're in a non-deterministic language like Prolog, you can just explore all the branches that succeed, and have an `if` expression return multiple answers. But for most languages, this isn't compatible with their deterministic semantics.

In general, you can't just ignore the order.
> 4 votes

# Answer
If you restrict yourself to using constructors of datatypes, the compiler knows what can happen during pattern matching. For instance, assume your integer type is defined by this:

```
datatype integer = Zero | Positive of natural | Negative of natural

```

Then, the example from your question translates to:

```
fun f Zero        = 0
|   f Positive(n) = 1
|   f Negative(n) = -1

```

Now, the compiler knows that the alternatives are

1. exhaustive *and*
2. mutually exclusive

and it can optimize away.

Be aware that this is likely a micro-optimization of the premature denomination. Especially in functional languages -- where you program at high levels ob abstraction -- I would not worry about such details. Unless you have made very sure that *this* is a performance hotspot.
> 2 votes

---
Tags: programming-languages, functional-programming, program-optimization, language-design, ordering
---


# Question
Title: What to do when the information gain on decision trees is 0 for all possible splits?
I just started studying decisions trees and I am trying to construct a tree for a training set which uses Status as the class label. I am using the misclassification error as measure of impurity. After the first iteration, the information gain indicates that Department should be the tree root. The following table represents the sub-table for Department = Secretary.

I got to this point and I don't know how to add the corresponding nodes to the tree. Should the next node be Age or Salary?

Thanks!

# Answer
> 2 votes
You should process ALL of the possible splits and hope for information gain somewhere down the line.

# Answer
> 0 votes
You are asking how to resolve ties. The answer is: resolve the tie arbitrarily. In other words, randomly pick one of the attributes. As far as you can tell at this stage, they are all equivalent.

Is this optimal? No. But the ID3 algorithm is already not claimed to be optimal. It is a greedy algorithm, which means we make the best decision we can at each stage, using only local information, without trying to predict their future impact. The benefit of this approach is that you get an algorithm that is very efficient at computing a decision tree. And, while it might not output the optimal decision tree, experience suggests that the resulting decision tree is often still very good in practice.

---
Tags: artificial-intelligence, data-mining
---


# Question
Title: What is meant by "solvable by non deterministic algorithm in polynomial time"
In many textbooks NP problems are defined as:

> Set of all decision problems solvable by non deterministic algorithms in polynomial time

I couldn't understand the part "solvable by non deterministic algorithms". Could anyone please explain that?

# Answer
> 28 votes
Adding to Shitikanth's answer, a nondeterministic algorithm is one that has multiple choices in some points during its control flow. The actual choice made when the program runs is not determined by the input or values in registers, or if we are talking about Turing machines, the choice is not determined by the input value and the state; instead an arbitrary choice among the possibilities can be made in a given run of the program. Thus multiple runs of the same algorithm on the same input can result in different outputs.

The point of using a non-deterministic algorithm is that it can make certain guesses at certain points during its computation. Such algorithms are designed so that if they make the right guesses at all the choice points, then they can solve the problem at hand.

A simple example is primality testing. To decide whether a number $N$ is *not* prime, one simply selects non-deterministically a number $n\le\sqrt{N}$ and checks whether $N$ is divisible by $n$. For any composite number, this algorithm finds a factor of the number by making the right guess.

The polynomial time part means that if the nondeterministic algorithm makes all the right guesses, then the amount of time it takes is bounded by a polynomial.

# Answer
> 10 votes
"$L$ is solvable by non deterministic algorithms in polynomial time" means that there exists a non-deterministic turing machine $M$, and a polynomial $p$ s.t. for all $x \in L$, $M$ accepts $x$ in at most $p(|x|)$ steps in one of the branches of its execution.

# Answer
> 9 votes
Informally, the main difference between nondeterministic algorithms and the normal, deterministic, algorithms is that when provided with multiple choices to take, the deterministic solution will have to check one of them at a time in sequence while the nondeterministic version can cheat a bit. There are two main ways to look at it that I know of:

1. When faced with multiple possibilities, the nondeterministic version runs all of them in parallel, suceeding if any of the threads succeed and failing if all of them fail.
2. When faced with multiple possibilities, the nondeterministic version always luckily chooses a possibility that succeeds and fails otherwise.

There is also a popular definition of NP that turns out to be equivalent if you think about it:

> A problem is in NP iff it is always possible to provide a polynomially long proof certificate for any positive solution to a problem instance.

---

For a concrete example, let's take the problem of determining if a number $N$ is composite (not prime). A way to solve this is to test all numbers less then N to check whether they are divisors of N.

If you do the tests sequentially this naive algorithm would take exponential time (since $N$ is exponentially large compared to the number of digits it has), but if you are allowed to do a magical nondeterministic choice the algorithm takes polynomial time (since each different divisor test takes polynomial time). Thus, testing if a number is composite is in NP.

And in the alternate formulation, providing a divisor of $N$ gives a polynomially long proof of compositeness.

# Answer
> 2 votes
Here is an equivalent and more natural interpretation:

A problem $L$ is said to be in $NP$ if there is a deterministic polynomial-time algorithm for all $x\in L$ which verifies the membership of $x$ in $L$ using a short certificate $y$ ($|y| \lt |x|^c$).

# Answer
> -4 votes
A non-deterministic algorithm is one where the input includes a random choice. Meaning, the input is composed of the nominal input plus a purely random selection -- so the answers differ when you run the algorithm with the same nominal input time and again. If one of the random choices leads to an easy, short (polynomial) solution, the algorithm is NP (non-deterministic polynomial). The unresolved question (is P=NP?) comes down to: is there anyway to make the random choices non-random, but based on some mathematical smarts. Most mathematicians think that the random choice cannot be "improved" to insure a fast solution, namely they believe that NP problems are immunized against future insight that would solve them in short (polynomial) time. They say: P \< NP; or at least claim so in order to give credence to a host of cryptographic products. Alas, even if in general P \< NP there are numerous special cases where the solution is fast, so the crypto products that rely on them are vulnerable to advanced math (like the Enigma that was defeated by Alan Turing -- we don't know how many Alan Turings work for our adversaries).

---
Tags: complexity-theory, terminology, nondeterminism
---


title: Simplifying Boolean Expression

text:
# Question
Title: Simplifying Boolean Expression
I am designing a 4-bit comparator with a look ahead unit using a bit slice approach. I have to break the propagation of the Logical expressions for `(A<B)i` and `(A>B)i`. The main question is, could I use the following to simplify the boolean expressions.. The i is a subscript meaning the ith bit. The i-1 is a subscript meaning the bit before the ith bit.

`(A<B)i = ~Ai*Bi + ~Ai*(A<B)i-1 + Bi*(A<B)i-1`

Could I Take `~Ai` common from the first two expressions leaving me with

`~Ai*(Bi + (A<B)i-1) + Bi(A<B)i-1`

Let's call `Bi + (A<B)i-1) = Q`

And let's call `~Ai = P`

I'm left with `P*Q + Q`

Using the boolean law that `Q + Q*P = Q`

Can I simplify the expression to just

`(A<B)i = Bi + (A<B)i-1`

# Answer
> 0 votes
No, you cannot simplify to $(A\<B)\_i = B\_i + (A\<B)\_{i-1}$, Take for example $A=11$ and $B = 10$.

Then $(A\<B)\_2$ = False, $B\_2$ = True, and $(A\<B)\_1$ = False. If you substitute the values above then the equation is not satisfied. The original equation(s) is correct.

$(A\<B)\_i = \neg A\_i B\_i + (\neg A\_i+B\_i)(A\<B)\_{i-1}$
$(A\<B)\_1 = \neg A\_1 B\_1$

In your derivation of simpler formula, $B\_i + (A\<B)\_{i-1} = Q$ but you are incorrectly substituting $B\_i (A\<B)\_{i-1} = Q$ in rightmost term.

---
Tags: logic, boolean-algebra, digital-circuits, karnaugh-map
---


# Question
Title: Dijkstra's algorithm to compute shortest paths using k edges?
I am aware of using Bellman-Ford on a graph $G=(V,E)$ with no negative cycles to find the single-source single-destination shortest paths from source $s$ to target $t$ (both in $V$) using at most $k$ edges. Assuming we have no negative edge weights at all, can we use Dijkstra's algorithm for the same?

**My thoughts/algorithm:** I was wondering if instead of having a $dist\[u$\] array (storing the best known distance from s to u), we could use a $dist\[u\]\[k\]$ table to store the best known distance from $s$ to $u$ using at most $k$ edges (dynamic programming maybe?), and similarly have the priority queue with $(u,n)$ tuples as keys. We can then terminate the algorithm when the tuple popped off the priority queue is $(t,n)$ where t is the target destination and $n \<= k$?

# Answer
If the graph has no negative edges, the problem can be solved in $O(k \cdot (|V|+|E|) \lg |E|)$ time using Dijkstra's algorithm combined with a product construction. We construct a new graph $G'=(V',E')$ with vertex set $V' = V \times \\{0,1,2,\dots,k\\}$ and edge set

$$E' = \\{((v,i), (w,i+1)) : (v, w) \in E\\}.$$

In other words, for each edge $v \to w$ in $G$, we have edge $(v,i) \to (w,i+1)$ for all $i$ in $G'$.

Now use Dijkstra's algorithm to find the shortest path in $G'$ from $(s,0)$ to a vertex of the form $(t,i)$ where $i \le k$. This will be the shortest path in $G$ that uses at most $k$ edges.
> 5 votes

---
Tags: algorithms, graphs, dynamic-programming, shortest-path, weighted-graphs
---


# Question
Title: Regular languages and constructing a regular grammar
I'm pretty new to computer science and just read about the concept of grammars. Now, I have a practical problem to solve. Here is the alphabet `{a, b, c, d}`.

How can I determine if the language consisting of all strings `a^k b^n c^m d^l`, where all `k,n,m,l >= 1` is regular. I need to do this because as far as I got all regular languages may be parsed by a regular expression. So, to avoid generating my own parser and lexer, is it possible to do so?

My first attempt was to construct a regular grammar generating the language. I failed, but that doesn't mean that the grammar does not exist. I would appreciate any advice.

# Answer
First of all it is enough if we can give regular expression for a regular language. To determine if a language is regular you have to show existence of a DFA or a regular expression for the language. Or you can show it is regular if you can prove it is union, intersection, concatenation, etc. (operations under which regular languages are closed) of other known regular languages.

The language in question is regular because it has regular expression $aa^\*bb^\*cc^\*dd^\*$.

To construct a regular grammar you need to do it step by step.

$A \rightarrow aA\ \ | \ \ a$
$B \rightarrow bB\ \ | \ \ b$
$C \rightarrow cC\ \ | \ \ c$
$D \rightarrow dD\ \ | \ \ d$

Then finally,

$S \rightarrow ABCD $

Yet another method to get a regular grammar is to convert from DFA. Then you will get (which might be a little difficult to understand right away):

$S \rightarrow aA$
$A \rightarrow aA\ \ |\ \ bB$
$B \rightarrow bB\ \ |\ \ cC$
$C \rightarrow cC\ \ |\ \ dD$
$D \rightarrow dD \ \ |\ \ \epsilon $

My two cent opinion is directly write a lexer (or use automatic-lexer-generator like flex) rather than writing a parser (or using automatic-parser-generator like bison).
> 2 votes

---
Tags: formal-languages, regular-languages, formal-grammars
---


title: Certificate Definition of NL

text:
# Question
Title: Certificate Definition of NL
As per the Sanjeev Arora book, for a certificate based definition of $NL$, the machine is allowed a "read-once" certificate tape to store the certificate along with $O(log n)$ read/write work tape for a deterministic verifier machine.

My doubt is that for a $3-SAT$ problem, if instead of storing an assignment to the $n$ variables, I store the $3k$ assignments to the $3k$ literals in a $k$ clause 3-SAT formula in the certificate tape. This way I don't have to re-read a previous symbol and I can go from left to right in the certificate tape at each step of the machine.

And in work tape I can calculate OR of 3 literals. If it is $0$, then I reject, if it is $1$, I erase the contents of the work tape and store the values of 3 literals of the next clause, and repeat. If all clauses were satisfying, I accept.

The certificate is also polynomial in the length of input. Kindly point out the flaw in this argument, otherwise $3-SAT$ would $\in NL$, which is not believed to be true.

# Answer
The problem is that you won't be able to verify if the certificate is legitimate as you are making certificate with assignment of variables clause by clause. To check it is legitimate you would have to traverse back on certificate tape which you won't be able to. For example let $\phi = \\{ (x\_1 \vee x\_2 \vee x\_3) \wedge (\overline{x\_1} \vee x\_4 \vee x\_5) $. And say your certificate is {(True,False,False),(True,False,False)}. In this case you would declare that assignment makes $\phi$ True but that's not the case as $x\_1$ and $\overline{x\_1}$ can't both be True and to check all assignments are valid you will have to traverse back and forth on certificate tape which you can't do. Thus your approach is not correct.
> 2 votes

---
Tags: complexity-theory, turing-machines, space-complexity, 3-sat, computational-complexity
---


title: Contracting Several nodes into one node

text:
# Question
Title: Contracting Several nodes into one node
After finding the Strongly Connected Components of a graph and putting each SCC in a list, how i can contract each list of nodes into one node?

Thanks!

# Answer
> 1 votes
I am going to assume that you want to build the graph of strongly connected components.

Traverse the edges of the graph once more. For every edge `(x,y)`:

* If `x` and `y` belong to the same SCC you do nothing.
* Else insert edge `(SCC[x],SCC[y])` in a new graph (the graph of strongly connected components).

---
Tags: graphs
---


title: Huffman Coding and Depth Calculation?

text:
# Question
Title: Huffman Coding and Depth Calculation?
I'd like to as a variation on this question regarding Huffman tree building. Is there any theory or rule of thumb to calculate the depth of a Huffman tree from the input (or frequency), without drawing tree.

Specific Example is : 10-Input Symbol with Frequency 1 to 10 is 5. the above question mentioned depth is 5.

I read about max depth of Huffman and Entropy, but not well description for me.

Edit:

We know in my specific example the frequency is: $1$ to $10$ which means probability is: $(1/55)+(2/55)+(3/55)+(4/55)+(5/55)+(6/55)+(7/55)+(8/55)+(9/55)+(10/55) = 1 $

# Answer
In each step of the Huffman coding algorithm the list of probabilities is being sorted and the 2 lowest of them are merged into a new node of the tree, resulting into a new probability. As for your example probabilities the below illustration shows:

```
step 1:  [1/55,2/55,3/55,4/55,5/55,6/55,7/55,8/55,9/55,10/55]
step 2:  [3/55,3/55,4/55,5/55,6/55,7/55,8/55,9/55,10/55]
step 3:  [4/55,5/55,6/55,6/55,,7/55,8/55,9/55,10/55]
step 4:  [6/55,6/55,7/55,8/55,9/55,9/55,10/55]
step 5:  [7/55,8/55,9/55,9/55,10/55,12/55]
step 6:  [9/55,9/55,10/55,12/55,15/55]
step 7:  [10/55,12/55,15/55,18/55]
step 8:  [15/55,18/55,22/55]
step 9:  [22/55,33/55]
step 10: [1]

```

So **in each step the set of the corresponding probabilities is reduced by 1.** This corresponds to the size of the tree being increased by one. Without drawing the tree we can quickly deduce that the length (or height depending on how you visualize it) will be 10.This is because the algorithm terminates when we reach the root of the tree that corresponds to probability of 1. As you can see there is absolutely no difference with the case of probabilities being all equal or any other specific distribution of probabilities among the symbols.

Note that there is not direct link to the average length of the resulting code and the length/height of the Huffman tree. The former depends very much on the probability distribution of the alphabet symbols. The best metric that we can use to address this issue is the entropy of the source that uses the alphabet under consideration. Entropy is a measure of the average uncertainty that we have about which symbol will appear next (at source's output) and is defined as this $$H(\Phi) =\sum\_{i=1}^{N} p(s\_i)\cdot log\_2(1/p(s\_i))$$ Entropy indicates the minimum average codelength that we can achieve in coding the source $\Phi$. In general, when the symbols have all equal probabilities of appearance the entropy is maximized and $H(\Phi)=log\_2N$. The intuition behind this is that when all symbols are equiprobable then our uncertainty about the source's output is maximized.
> 3 votes

---
Tags: algorithms, data-structures, trees, probability-theory, coding-theory
---


# Question
Title: Question about DFA for exact string matching
In the Handbook of Exact String Matching algorithms, it describes the transition set for a basic string matching automaton as:

> for
>
> * q in **Q** (q is a prefix of x)
> * a in $\Sigma$
> * (q, a, qa) is in **E** if and only if qa is also a prefix of x
> * otherwise (q, a, p) is in **E** such that p is the longest suffix of qa which is a prefix of x.

I'm having difficulty understanding the last statement. Why would there be a state transition to a suffix?

# Answer
> 2 votes
Assume that you build an automaton for finding occurrences of $bububa$ in the input string. When the automaton reads the input string $bubububa$, then it after reading $bububu$, it must not just return to state $\epsilon$, as otherwise an occurrence of $bububa$ is not detected. Also, jumping back to state $bu$ is would not do the trick, as then again, the $bububa$ starting in letter 3 of the word would be missed. Rather, after seeing a $u$ in state $bubub$, the automaton must transition to $bubu$ in order to no miss the possibility that only the first two letters are to be ignored.

The last line in the definition of $E$ describes how the back transitions in the automaton are found: in order not to miss any occurrence of $bububa$, the state in the automaton jumps back as little as possible.

---
Tags: finite-automata, strings, exact-string-matching
---


# Question
Title: What is a good example to illustrate the difference between isomorphic and homomorphic representations?
I am learning about "knowledge representation" in my intro to AI course and one of the key ideas has to do with isomorphic vs homomorphic representations. The examples I find when I google around are mainly on the topic of mathematical graphs, which are over my head.

Can someone give me a simple, non-mathematical example of homomorphic vs isomorphic knowledge representation to help me wrap my head around the idea?

# Answer
You are probably talking about homomorphisms from logic, i.e. homomorphisms that just preserve your functions and relations: https://en.wikipedia.org/wiki/Structure\_(mathematical\_logic)

I'm a bit suspicious about why your instructor bothered to give you these concepts in the intro course. I also suspect you just need to understand a difference between injective and bijective functions (for this is what the difference between a homomorphism and isomorphism is in the logic world, ignoring all the stuff that deals with preserving structures).

1. Injective function. You have a set of shirts. You represent the shirts by their colours. Many shirts have the same colour. Some colours don't have any shirts mapped into them. If you are given just a colour, you cannot recover the knowledge of what shirt it was.
2. Bijective function. You have a set of books. You represent them by the ISBN number. Every book gets and ISBN number. Every ISBN number is associated with some unique book. You can go back and forth between these representations.
> 2 votes

---
Tags: terminology, artificial-intelligence, knowledge-representation
---


# Question
Title: Is the Kleene star of an intersection contained in the intersection of Kleene stars?
I need to find if given two formal languages $L\_1$ and $L\_2$ $$(L\_1 \cap L\_2)^\*\subseteq (L\_1^\* \cap L\_2^\*) $$ I think that it's true since this can be rewritten as $$ \bigcup^\infty\_{i=0}(L\_1 \cap L\_2)^i \subseteq (\bigcup^\infty\_{i=0}L\_1^i \cap \bigcup^\infty\_{i=0}L\_2^i)$$ and in general, $$(A \cap B) \cup (C \cap D) \subseteq (A \cup C) \cap (B \cup D)$$ I may be wrong since it has been a long time since i have done anything with set theory, and this is taken as given. Thanks

# Answer
Yes, it is true. But the argument to support the conjecture is incorrect.

The correct proof is as follows: $L\_1 \cap L\_2 \subseteq L\_1 $ and therefore $(L\_1 \cap L\_2)^\* \subseteq L\_1^\*$. (argument: if $A \subseteq B$ then $A^\* \subseteq B^\*$). Similarly $(L\_1 \cap L\_2)^\* \subseteq L\_2^\*$.

Therefore $(L\_1 \cap L\_2)^\* \subseteq (L\_1^\* \cap L\_2^\*)$ (argument: if $A \subseteq B$ and $A \subseteq C$ then $A \subseteq B \cap C$).

Anyway you can not write $(A \cap B)^i \cup (C \cap D)^j = (A^i \cup C^j) \cap (B^i \cup D^j)$.

Correct relation is: $(A \cap B) \cup (C \cap D) = (A \cup C) \cap (B \cup D) \cap (A \cup D) \cap (B \cup C) $

However $\bigcup^\infty\_{i=0}(L\_1 \cap L\_2)^i \subseteq (\bigcup^\infty\_{i=0}L\_1^i \cap \bigcup^\infty\_{i=0}L\_2^i)$ is correct because
$\bigcup^\infty\_{i=0}(L\_1 \cap L\_2)^i \subseteq \bigcup^\infty\_{i=0}L\_1^i $ and $\bigcup^\infty\_{i=0}(L\_1 \cap L\_2)^i \subseteq \bigcup^\infty\_{i=0}L\_2^i $.
> 4 votes

---
Tags: formal-languages, kleene-star
---


# Question
Title: Succinct data structure for "bookkeeping problem"
I have a "standard" problem, but I can't remember its "official" name: I have to keep track of the presence of the absence of value in an array.

Currently I use an each bits of an other array to track it. Let's say I have a byte array of 8k elements if I want to know if a place is taken (without accessing to the array), I need a 1k byte array (8 bits per byte) to track it. So I have more or less these complexities:

* Check: $O(1)$
* Change: $O(1)$
* Memory: $O(n/8)$

I wanted to know if there's a more memory optimized data structure keep the constant check factor because I have the following properties:

* The targetted array has a fixed size known at compile-time
* Most of the actions performed are *Check* (maybe 10k-1k checks for one change)
* The array is mostly sparsed (5-25% used)
* There are only few space freeing
* Sometimes a value take more than one byte but I only need to keep track of the first one.

I'm looking for data-structures name or samples. Thanks.

# Answer
> 4 votes
Let's suppose that there the occupancy rate is 25%. Then given an array of $n$ elements, there are ${ n \choose 0.25n}$ possible bitmaps. The theoretical minimum number of bits per entry that you need is, then:

$$\lim\_{n \rightarrow \infty}\frac{1}{n} \log\_2 { n \choose 0.25n } \approx 0.81$$

At 5%, the minimum number is:

$$\lim\_{n \rightarrow \infty}\frac{1}{n} \log\_2 { n \choose 0.05n } \approx 0.29$$

Note that I didn't actually calculate it this way. I used the binomial entropy function:

$$B(p) = -\left(p \log\_2 p + (1-p) \log\_2 (1-p)\right)$$

Then $B(0.05) \approx 0.29$.

So given a 25% occupancy rate, there is no data structure which compresses better than 80% of the size of the uncompressed bitmap.

Given that it sounds like you have a real problem to solve, does shaving 20% off the size of the bitmap seem like a reasonable benefit, given that the cost is likely to be a much higher-constant-factor data structure?

Besides, 1kB just isn't that big. It's a fraction of a page in size, and likely to be in cache most of the time if this is really your inner loop.

**EDIT**

OK, if you really need this, I suspect that succinct hashing might be your best bet. There are dynamic bitmap data structures which support the rank operation, but none of them have constant time queries to my knowledge.

# Answer
> 1 votes
https://en.wikipedia.org/wiki/Bloom\_filter is an interesting approach with O(1) memory use that might not fit your case if you can handle the occasional false positive - i.e., the system sometimes falsely saying that a particular location is not available; if the array is mostly sparse and/or you can double-check somewhere.

---
Tags: algorithms, data-structures, data-compression
---


# Question
Title: Find the minimum count of elements summing to a pre-defined sum
We have the following problem: Given an array of integers $\\{a\_1, a\_2,...,a\_n\\}$ and a number $s$, find a contiguous sub-array of elements that sum exactly to $s$. If multiple solutions exist, find a solution that is smallest in terms of length (length of sub-array). If there is no such contiguous sub-array, output "-1".

I have thought of an $O(n^2)$ algorithm, using two pointers and prefix sums, but I cannot find an $O(n)$ algorithm. What would an $O(n)$ algorithm be like?

# Answer
This can be solved in $O(n \lg n)$ time by computing prefix sums and then using divide-and-conquer.

Step 1. Compute the prefix sums $p\_0,p\_1,\dots,p\_n$, where we define $p\_i = a\_1 + a\_2 + \dots + a\_i$. Throw away the $a\_i$'s. Now the problem becomes: count how many index-pairs $i,j$ there are where $0 \le i \le j \le n$ and $p\_j = p\_i + s$.

Step 2. Solve this problem using divide-and-conquer. First, count the number of solutions where $0 \le i \le j \le n/2$ (recursively). Second, count the number of solutions where $n/2 \< i \le j \le n$ (recursively). Third, count the number of solutions where $0 \le i \le n/2$ and $n/2 \< j \le n$. This third step can be done in $O(n)$ time (expected running time). Since this is your exercise, I'll let you work out how: it's not too hard.

The total running time satisfies the recurrence $T(n) = 2 T(n/2) + O(n)$, so this yields a $O(n \lg n)$ time solution.
> 1 votes

# Answer
**This algorithm is $O(n)$ only for non-negative integers, $O(n~log~n)$ otherwise.** I think there is no $O(n)$ solution for mixed positive/negative numbers, though I cannot formally prove it.

First, calculate the cumulative sum over the array. This yields an array of length $n+1$

$$\\{b\_1,b\_2,...,b\_{n+1}\\} = \\{0, a\_1,a\_1+a\_2,...\\}$$

and allows the calculation of any sum over a range $i..j$ in constant time as $b\_{j+1}-b\_i$.

If all $a\_i$ are non-negative, $\\{b\_1,b\_2,...\\}$ is already monotonic. If this is not the case, sort it. Also store the array of indices.

Now you can start with two pointers, called $p\_1$ and $p\_2$, both initialized to $b\_1$. Perform the following algorithm:

* If the sum over the range is too large, move $p\_1$ one step forward.
* If the sum over the range is too small, move $p\_2$ one step forward.
* If the sum over the range is exactly $s$, you found a solution.

+ Store it (if the element count is smaller than that of the currently best solution).
    + If the element in front of the trailing pointer is equal to the current one, move the trailing pointer one step forward. Otherwise move the leading pointer.
    + You can get range over which you calculated the sum by subtracting the indices. This range can be either ascending or descending, dependent on whether the element were swapped during sort.

Both the cumulative sum and the search require exactly one pass over the array, so the algorithm is of time complexity $O(n)$ for non-negative numbers. In the general case, a sort is required which results in a complexity of $O(n~log~n)$.

**Example**

```
s=1
a=[1, -1, 1, -1]

Calculate the prefix sums:
b=[0, 1, 0, 1, 0]

Sort b, keep track of the original indices.
b=[0, 0, 0, 1, 1]
i=[1, 3, 5, 2, 4]

Use the two-pointer method
b=[0, 0, 0, 1, 1]
p1 ^
p2 ^
p2 - p1 = 0 < 1     => rule 2

b=[0, 0, 0, 1, 1]
p1 ^
p2    ^
p2 - p1 = 0 < 1     => rule 2

b=[0, 0, 0, 1, 1]
p1 ^
p2       ^
p2 - p1 = 0 < 1     => rule 2

b=[0, 0, 0, 1, 1]
p1 ^
p2          ^
p2 - p1 = 1 == 1    => rule 3
Look up indices
i=[1, 3, 5, 2, 4]
p1 ^
p2          ^
=> solution: sum from 1 inclusive to 2 exclusive is 1
=> length of solution is 2 - 1 = 1 (accept)

b=[0, 0, 0, 1, 1]
p1    ^
p2          ^
p2 - p1 = 1 == 1    => rule 3
Look up indices
i=[1, 3, 5, 2, 4]
p1    ^
p2          ^
=> solution: sum from 3 exclusive down to 2 inclusive is 1
=> length of solution is 2 - 3 = -1 (we already have a solution of length 1 => reject)

b=[0, 0, 0, 1, 1]
p1       ^
p2          ^
p2 - p1 = 1 == 1    => rule 3
Look up indices
i=[1, 3, 5, 2, 4]
p1       ^
p2          ^
=> solution: sum from 5 exclusive down to 2 inclusive is 1
=> length of solution is 2 - 5 = -3 (we already have a solution of length 1 => reject)

b=[0, 0, 0, 1, 1]
p1       ^
p2             ^
p2 - p1 = 1 == 1    => rule 3
Look up indices
i=[1, 3, 5, 2, 4]
p1       ^
p2             ^
=> solution: sum from 5 exclusive down to 4 inclusive is 1
=> length of solution is 4 - 5 = -1 (we already have a solution of length 1 => reject)

b=[0, 0, 0, 1, 1]
p1          ^
p2             ^
p2 - p1 = 0 < 1     => rule 2

rule 2 not applicable: pointer reached end, terminate.

The final solution is: sum from 1 inclusive to 2 exclusive, length 1

```
> -1 votes

---
Tags: algorithms
---


# Question
Title: Calculate maximum ammount of Bus Bandwidth
Don't know if this is the right community for this and this should be pretty basic but here goes. I'm studying System Engineering and one of the homework problems is the following question.

> A 32-bit computer with a 200-MHZ Bus requires four cycles to read a 32-bit word. How much bus bandwidth does the CPU consume in the worst case ?

I just can't get my head around this for some reason. I thought that because it's a worst case scenario the CPU would just consume 4x (cycle) the entire Bus (200MHZ) which would be 800MB/s. I even reasoned this with reversing BIT \> BYTE. Byte per Clock cycle. clock Cycle * Clock rate = bandwidth. But appereantly i'm wrong with the correct answer seemingly being 400MB/s. I can't find (in the study material atleast) how to determine this.

Anyone out there that can help me out or at least set me on the right track ? I could drop this question but i'm afraid this will haunt me in my nightmares.

Thanks so much.

# Answer
> 0 votes
Start from the definition. Bandwidth is defined as data transferred per unit time. For instance, it's the number of bytes transferred, per second.

So, work out how many bytes it would be possible to transfer across the bus, in one second. Forget formulas: just try to reason it through. How many 32-bit words could you transfer in one second? How many bytes does that correspond to?

---
Tags: cpu
---


title: How is n-gram different from k-mer?

text:
# Question
Title: How is n-gram different from k-mer?
How is n-gram different from k-mer? Both seem to be (n or k) length substrings of a larger string. Are these just terms common with different practitioners? viz. Computer Scientists and Bioinformaticians?

# Answer
Yes, they mean the same thing. A n-gram is a sequence of n consecutive things (words, letters, whatever). A k-mer is a sequence of k consecutive things (DNA basepairs). The phrase k-mer is more common in computational genomics.

See https://en.wikipedia.org/wiki/N-gram and https://en.wikipedia.org/wiki/K-mer for definitions.
> 4 votes

---
Tags: strings, string-metrics, substrings, subsequences, bioinformatics
---


# Question
Title: Normalized measure from dynamic time warping
I am trying to find the similarity between two time series, but not in terms of distance, in something more sensible such as percentage of similarity. In other words I need something that shows the similarity, not dis-similarity.

The dynamic time warping gives a very good response, when trying to compare the time-series. But the distance computed by dynamic time warping depends on the duration of the time series and the magnitude of the template and the query. Moreover, it shows the distance, which demonstrates the dis-similarity.

Is there a way to convert the distance from DTW into some form of normalized similarity measure?

# Answer
> 11 votes
Sure. There's a straightforward way to convert an unnormalized distance metric into a normalized similarity measure. Basically, use

$$S(x,y) = \frac{M - D(x,y)}{M},$$

where $D(x,y)$ is the distance between $x$ and $y$, $S$ is the normalized similarity measure between $x$ and $y$, and $M$ is the maximum value that $D(x,y)$ could be.

In the case of dynamic time warping, given a template $x$, one can compute the maximum possible value of $D(x,y)$. This will depend on the template, so $M$ becomes $M(x)$, and the formula becomes

$$S(x,y) = \frac{M(x) - D(x,y)}{M(x)}.$$

So how do you compute $M(x)$? Basically, multiply the length of the template (the number of samples in the time series), times the maximum value of each sample. If each sample is in the range $\[0,1\]$, then the maximum value of each sample is 1, so $M(x)$ becomes just the length of $x$. This gives a simple upper bound on $D(x,y)$. \[Trivia: in fact one could compute a slightly tighter upper bound, but in practice that's probably not necessary.\]

It is easy to verify that the similarity measure is always in the range $\[0,1\]$ and thus is normalized as you were hoping for.

---
Tags: machine-learning, pattern-recognition, time-series-analysis
---


# Question
Title: An ID (auto increment integer) always as primary key for each db-table?
Till now, I always gave each db-table an id-column (generally with the table name and an underscore as a prefix, e.g. employee\_id), and I also **never** have seen another approach to unique a db-table-record **in practice**. But on the other hand during my studies, I often have seen other columns that act as a primary key, for instance: an email/url as priamary key for a table user/photo.

At the moment I'm designing a database that contains a table first\_name (because a human can have more than one first name). The scheme of this table first\_name:{\[first\_name\_id:integer,first\_name:string\]}. But to avoid duplicate, I would like to use the first\_name as a primary key. And I also have a table employee with the column email address that also can be used as a primary key, becuase its unique.

My loss is that I dont know if I should use this approach, becuase its uncommon in practice and maybe it will cause any trouble during the programming part. So my questions is: An ID (auto increment integer) always as primary key for each db-table?

# Answer
I assume you are using RDBS.As far as you can set any value as primary key this will not cause strict programming trouble - but will be cumbersome.

What about convention that people use integer?
This comes from two parts:
It is easier to give unique id from autoincremented value.
Second is from relations and optimizations - database internally connects related items, so setting something different will cause overhead.

You should read two pages:
normal forms in database and primary keys.

Normal form is something you should have (at least third level) in your database, it saves programming trouble later like with splitting keys manually.
> 0 votes

---
Tags: databases
---


# Question
Title: How to handle horizontal lines in the Polyfill Algorithm?
When I look at polyfill algorithm tutorials/articles or examples, nothing mentioned about how to handle horizontal lines. Does anyone have any idea how horizontal lines should be handled?

For instance, consider the following image:

For intersection I wrote if the line on the scan line count it as 1 point, even I count as 2 point or no point, wont help. Any idea how should I handle the horizontal line?

**Edit:** here a complex example of horizontal line intersection, let's take a look at **line 3**:

Alright, if we take a look at next point and previous point of the intersection of both end of horizontal line, if those point are in same side, means I can count them in or out, doesn't effect the whole calculation.
But if they are are opposite side, I have to count them in and count one side extra.

**What do I mean?**
Take **InterS1** and **InterS2** as an example, so when I get this I have count that horizontal line as 3 points:

```
point1 = InterS1
point2 = InterS2
point3 = InterS2

```

**Why I need to do that?**

1. When next point and previous point are in different direction, is letting us know that our intersection line crossing outside and passing through inside of shape.
2. Also because line can be created when there is start point and end point, so I need to have even number to draw lines.

So now I have no idea base on what I need to add the extra point to one side.
Do I make sense?

# Answer
See Polygon Filling. It gives one method to deal with edges parallel to scanline. It says that it is imperfect, but you can ignore the horizontal edges. Other solution is to take either left or right endpoint of horizontal edge (any one point only). Yet another solution is to take right or left endpoint depending on the situation, so that whole edge is filled.

If you ignore horizontal lines you should get something like the following:
> 2 votes

---
Tags: algorithms, computational-geometry
---


title: How do I prove Berman's theorem?

text:
# Question
Title: How do I prove Berman's theorem?
Berman's theorem states

> If a unary language ( a language with all the strings of the type $1^i$, $ i \> 0 $ ) is NP-Complete then P = NP.

I tried reducing SAT to a given unary language $L$ assuming it is NP-Complete. But I can't think of a way such that after applying the reduction so that SAT gets solved in polynomial time. How do I proceed further?

This is an exercise from Sanjeev Arora and Boaz Barak , but not homework.

# Answer
Please refer this solution. Or see the paper by S. R. Mahaney, Sparse complete sets for NP: Solution of a conjecture by Berman and Hartmanis (Journal of Computer and System Sciences, 25:130-143, 1982).
> 4 votes

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


title: Pi in place of binary

text:
# Question
Title: Pi in place of binary
Some time ago, I asked this question but no one quite understood it or was able to answer. I deleted the original question and have since decided to try it again.

As I understand it, all things digital are originally based on ones and zeros - binary code.

However, I have wondered for some time if it would be possible (now or in the future) to use the digits of pi (22/7) in place of the ones and zeros.

So, my question, is it possible? Could it ever be?

# Answer
No it cannot happen for many reasons.
How would logic look like?
How would you add two numbers?
There is a big problem with telling apart $0$ and $1$ at high frequencies, so adding third option would be harder to manufacture. But encoding it with non-natural basis gets harder.
With non-natural base, all operations that we do are doomed.
If you consider that, try easy example: convert $4$ and $6.5$ into $\pi$ base, add them and write down result.
Since the finite precission kicks in, your basic addition fails. The only operation that would benefit from such base is $\pi + \pi$.

And the most efficient base is e.
> 2 votes

---
Tags: computational-complexity
---