# Question
Title: How is sound input and output data converted to use with machine learning networks?
Suppose one has a couple of *.wav* files with English spoken words, multiple ones for each word, and for each such set there exists a transcription of their right output, the pronunciation as *ascii text*.

As far as I know, machine learning neural networks use arrays of floats as input and output, and also internally.

What do one do in machine learning in order to convert such 'real world' data formats/data sets into another data structure that is meaningful and suitable for the machine learning neural networks?

Furthermore, what classifies a particular data structure as 'suitable', except the fact that it can be expressed as arrays of integers (what fits every digital data)?

(I suppose it could be more sophisticated than stripping the headers and feeding the uncompressed binary data in as integers, or is it?)

---

**edit**: in an other SE site's question (regarding how to filter out an image of Justin Bieber), an answer asserts that one *"has some method of feature generation to transform the raw images into features that are useful for machine learning purposes"*, but it doesn't explain how this is done, or how does one begin to create a method for such a feature conversion.

# Answer
> 3 votes
Probably the most common way to represent audio for speech recognition is using the Mel-frequency cepstrum coefficients. If you're interested in finding out more about state of the art neural network based systems for speech recognition, I'd recommend checking out some of the recent work by George Dahl.

In regard to the other, more general portion of your question, using "binary" data in the way you describe is a very bad idea (if you mean what I think you mean). The binary representations used to store information in a computer is primarily designed for efficiency, both in terms of operations and space. Thus, this sort of representation is not necessarily representative of the actual characteristics of the data.

An example of this is the difference between signed and unsigned integers. If you're using 8 bit unsigned integers, then 11111111 \> 00000001 but if you're using signed (2's complement) integers then 11111111 \< 00000001. But, if you just represented the data as binary vectors, then you're essentially forcing a machine learning system to not only figure out whatever relationship you're trying to model, but also whatever encoding scheme you've used. You can avoid this by using representations that respect the characteristics (real valued, categorical, etc) of the data.

Lastly, if you're trying to predict 1 of $k$ mutually exclusive classes (such as characters), then the most common approach is to represent the class label (target) as a $k$ dimensional vector with a 1 at the $i$th position, corresponding to the class, and 0 everywhere else. You'll frequently see this referred to as a 1-of-$k$ or one-hot representation. You'll also want to use an appropriate output function for you're neural net, most likely the softmax function given by

$$ f(x\_i) = \frac{\exp(x\_i)}{\sum\_{j=1}^k \exp(x\_j)}, $$ where $x\_i$, $i = 1, \ldots, k$, is the total input to the $i$th output unit. You can interpret this type of output as representing the conditional probability of each class given the input. The derivative is also particularly simple under the log-loss, which is what you should probably be using in this scenario.

In conclusion, neural networks are not magic black boxes. Just like any other ML technique, if you just throw data at them without considering the choices (inputs, outputs, loss function, etc) you're making and why, you'll probably have little success.

---
Tags: data-structures, machine-learning, data-sets
---


title: reducing Max3SAT to Max2sat

text:
# Question
Title: reducing Max3SAT to Max2sat
I want to reduce $MAX3SAT$ to $MAX2SAT$ ...
MAX-n-SAT : given $\phi $ n-CNF formula and number k does $\phi$ has an assignment that satisfy k clauses?

# Answer
Garey, Johnson and Stockmeyer ("Some simplified NP-complete graph problems") came up (already in 1974!) with a gadget reduction from MAX3SAT to MAX2SAT. Given a 3SAT clause $C = x \lor y \lor z$, they come up with a gadget $G(C)$ consisting of 2SAT clauses on the variables $x,y,z$ as well as some additional variables $V(C)$, satisfying the following property. Given an assignment to $x,y,z$, the maximal number of clauses in $G(C)$ which can be satisfied by an assignment to $V(C)$ is $M\_1$ if $C$ is satisfied and $M\_2\<M\_1$ if $C$ is not satisfied.

Try to understand how the existence of this gadget allows us to reduce MAX3SAT to MAX2SAT. Then either try to construct such a gadget, or look it up.
> 4 votes

---
Tags: algorithms, np-complete, reductions, approximation
---


# Question
Title: Random generator considerations in the design of randomized algorithms
It is well known that the efficiency of randomized algorithms (at least those in BPP and RP) depends on the quality of the random generator used. Perfect random sources are unavailable in practice. Although it is proved that for all $0 \< \delta \leq \frac{1}{2}$ the identities BPP = $\delta$-BPP and RP = $\delta$-RP hold, it is not true that the original algorithm used for a prefect random source can be directly used also for a $\delta$-random source. Instead, some simulation has to be done. This simulation is polynomial, but the resulting algorithm is not so efficient as the original one.

Moreover, as to my knowledge, the random generators used in practice are usually not even $\delta$-sources, but pseudo-random sources that can behave extremely badly in the worst case.

According to Wikipedia:

> In common practice, randomized algorithms are approximated using a pseudorandom number generator in place of a true source of random bits; such an implementation may deviate from the expected theoretical behavior.

In fact, the implementations of randomized algorithms that I have seen up to now were mere implementations of the algorithms for perfect random sources run with the use of pseudorandom sources.

My question is, if there is any justification of this common practice. Is there any reason to expect that in most cases the algorithm will return a correct result (with the probabilities as in BPP resp. RP)? How can the "approximation" mentioned in the quotation from Wikipedia be formalized? Can the deviation mentioned be somehow estimated, at least in the expected case? Is it possible to argue that a Monte-Carlo randomized algorithm run on a perfect random source will turn into a well-behaved stochastic algorithm when run on a pseudorandom source? Or are there any other similar considerations?

# Answer
Here is one good justification. Suppose you use a cryptographic-strength pseudorandom number generator to generate the random bits needed by some randomized algorithm. Then the resulting algorithm will continue to work, as long as the crypto algorithm is secure.

A *cryptographic-strength pseudorandom number generator* is a standard tool from cryptography that accepts a short seed (say, 128 bits of true randomness) and generates an unlimited number of pseudorandom bits. It comes with a very strong security guarantee: as long as the underlying cryptographic primitive is not broken, then the pseudorandom bits will be completely indistinguishable from true-random bits by any feasible process (and, in particular, no efficient algorithm can distinguish its output from a sequence of true random bits). For instance, we might get a guarantee that says: if factoring is hard (or, if RSA is secure; or, if AES is secure), then this is a good pseudorandom generator.

This is a very strong guarantee indeed, since it is widely believed to be very hard to break these cryptographic primitives. For instance, if you can figure out an efficient way to factor very large numbers, then that would be a breakthrough result. For all practical purposes, you can act as though the cryptographic primitives are unbreakable. This means that, for all practical purposes, you can act as though the output of a cryptographic-strength pseudorandom number generator is basically the same as long as a sequence of true-random bits. In particular, this is a good source of the randomness needed by a randomized algorithm.

(I've glossed over the fact that, to use a crypto-strength PRNG, you still need to find 128 bits of true randomness on your own to form the seed. But usually this is not hard, and indeed, there are cryptographic tools to assist with that task as well.)

In practice, getting extremely good pseudorandom bits is as simple as

```
$ cat /dev/urandom

```
> 2 votes

# Answer
*It is well known that the efficiency of randomized algorithms (at least those in BPP and RP) depends on the quality of the random generator used.* I have to disagree. What a good pseudurandom sequence ensemble gives you is a guarantee on the performance of the algorithm run a random sequence from the ensemble, compared to a trully random sequence. If you don't have such a guarantee, you can't conclude that the algorithm will work poorly - you just don't know.

*Is there any justification of this common practice?* It works.

*Is it possible to argue that a Monte-Carlo randomized algorithm run on a perfect random source will turn into a well-behaved stochastic algorithm when run on a pseudorandom source?* Complexity theory suffers from two shortcomings. The first one is that it is very hard to prove anything (for example, P vs. NP is open). The second one is that it is mostly concerned with worst-case analysis. Put together, these two limitations rule out complexity theory as a good model for the behavior of algorithms in practice.
> 2 votes

---
Tags: randomized-algorithms, randomness, pseudo-random-generators
---


# Question
Title: Asymptotic bounds on number of 3SAT formulas with unique solutions
A set is sparse if it contains polynomially bounded number of strings of any given string length $n$ otherwise it is dense. All known NP-complete sets are dense. It was proven that P=NP if and only if there is a sparse NP-complete set (under Karp reduction).

I would like to find the density of uniquely satisfiable 3SAT formulas. Is it super-polynomially dense or exponentially dense? What is known about the asymptotic lower bound on the number of 3SAT formulas with unique solutions?

# Answer
> 4 votes
It is dense, just as one would expect.

The number of uniquely satisfiable 3SAT formulas with $n$ variables and $n$ clauses is at least $2^n$, since for every possible assignment to the $n$ variables there is at least one 3SAT formula $\phi$ for which that is the satisfying assignment, and there are $2^n$ such assignments. A 3SAT instance with $n$ variables and $n$ clauses can be represented as a string of length $\ell = 3n \lg n$. Therefore, the number of such formulas is exponential in $\ell$.

---
Tags: complexity-theory, reference-request, np-complete, satisfiability
---


# Question
Title: Chazelle's discrepancy book: greedy method
In Bernard Chazelle's book *The Discrepancy Method*, which is available free as a PDF from the author's website, the very first statement requiring thought by the reader (on page 3, just before Theorem 1) is obtained by a simple probability argument. Unfortunately, I fail to follow the intended argument. Could someone enlighten me?

Here $\chi(S\_i) = \sum\_{v\in S\_i} \chi(v)$ is the *discrepancy* of the set $S\_i$ with respect to a function $\chi$ that assigns weights to each element.

> Given a set system $(V,S)$, with $|V| = n$ and $|S| = m$, pick a random coloring $\chi$, meaning that for each $v\_j$, the "color" $\chi(v\_j)$ is chosen randomly, uniformly, and independently, in $\\{-1,1\\}$. We say that $S\_i$ is *bad* if $|\chi(S\_i)| \> \sqrt{2|S\_i|\ln (2m)}$. By Chernoff's bound, we immediately derive $$Pr\[S\_i \text{ is bad}\] \< \frac{1}{m};$$

and now the bit I don't follow:

> therefore, with nonzero probability, no $S\_i$ is bad.

Clearly this holds if the $m$ events "$S\_i$ is not bad" are mutually independent. It also holds by a form of the Lovász Local Lemma if these events form the edges of a hypergraph (with $V$ as vertices) that is "nice enough". But I don't see why this is immediately apparent in every case, as the author seems to imply. If the $n$ individual values $\chi(v\_j)$ are iid, then I simply don't see that the $m$ events "$S\_i$ is not bad" are necessarily of a nice enough form to use the probabilistic method, and they certainly don't seem to be iid.

What am I missing?

Any counterexample must be rather large (with the size of $m$ exponential in $|S\_i|$), so I provisionally do believe the statement. But I would like a convincing proof, or a pointer to another reference.

# Answer
My oversight was that $|S| = m$, so there are $m$ events of the form "$S\_i$ is bad". Then since $Pr\[\cup\_{i=1}^m A\_i\] \le \sum\_{i=1}^m Pr\[A\_i\]$ for any collection of events $\\{A\_i \mid i=1,2,\dots,m\\}$, it follows that $Pr\[\text{some }S\_i\text{ is bad}\] \< 1$, so $Pr\[\text{no }S\_i\text{ is bad}\] \> 0$.
> 3 votes

---
Tags: reference-request, combinatorics, probability-theory, books
---


# Question
Title: Binary decision diagram for a six-figure Boolean function
> Let $p$ be the six-figure Boolean function with the following definition:
>
> $p(x\_{0},x\_{1},x\_{2},x\_{3},x\_{4},x\_{5})=\begin{cases} true & \text{if } x\_{0}=x\_{5} \text{ and } x\_{1}=x\_{4} \text{ and } x\_{2}=x\_{3}, \\ false & \text{else.} \end{cases}$
>
> This function obviously yields $true$ iff $x\_{0}x\_{1}x\_{2}x\_{3}x\_{4}x\_{5}$ is a palindrome. Provide a BDD for $p$ relative to a variable ordering of your choice.

My problems begin when I try to define an appropriate variable ordering, so I am only able to guess it: $x\_{0}=x\_{5} \< x\_{1}=x\_{4} \< x\_{2}=x\_{3}$. I'm actually pretty lost with this exercise and any help is much appreciated (sorry for not being able to provide a better own approach).

# Answer
> 2 votes
So finally this should be the correct solution:

The variable ordering is $x\_{0} \< x\_{5} \< x\_{1} \< x\_{4} \< x\_{2} \< x\_{3}$. The BDD is:

# Answer
> 1 votes
The wikipedia article has a fairly good example in the "Variable Ordering" section. By carefully picking the order we evaluate the variables in, we can come to (at least some) decisions sooner.

In your case, if we know that for example $x\_{0} = true$ and $x\_{5}=false$, we can immediately answer $false$, regardless of the values of the other variables. You should be able to extend this to a full BDD of reasonably small size.

# Answer
> 0 votes
Can you show us what you've tried so far? The problem says you can choose any variable ordering you want, so I'm a bit puzzled why you are trying to choose an "appropriate" variable ordering or guess a variable ordering. I suggest you choose any variable ordering you want (anything, really, it doesn't matter what you choose, just pick one), and then try to build the BDD. Why don't you try that, and then show us what you got? At that point we might be able to help you better.

P.S. When we say a variable ordering, we mean an ordering: a list of the variables in some order. An example of a variable ordering would be $x\_0,x\_5,x\_1,x\_4,x\_2,x\_3$. (I'm not sure what's going on with $x\_0=x\_5$; that's not a valid part of a variable ordering.)

---
Tags: formal-methods
---


# Question
Title: Is there a binary search tree datastructure which can avoid becoming badly weight-balanced?
This is a follow-up question of "Not all Red-Black trees are balanced?" and "AVL trees are not weight-balanced?".$\def\le{\leqslant}\def\ge{\geqslant}$

> **Definition:** For a rooted tree $T$ and a vertex $v \in V(T)$, let $L\_T(v)$ be the number of nodes in the left-subtree from $v$, and $N\_T(v)$ be the number of nodes in the subtree rooted at $v$. We say that $T$ is *$\mu$-balanced*, with $0 \le \mu \le \frac{1}{2}$, if for every node $v \in V(T)$ the inequality $$ \mu \le \frac{L\_T(v) + 1}{N\_T(v) + 1} \le 1 - \mu$$ holds, and if $\mu$ is minimal subject to this inequality holding.

(These are apparently also known as *weight-balanced* trees in some of the literature.) A tree which is $\mu'$-balanced for some $\mu' \< \mu$, we will say is **μ-imbalanced**.

The above-linked posts essentially show that neither AVL trees, nor Red-Black trees, can be guaranteed to be $\mu$-balanced for any $\mu \> 0$: that is, for any such $\mu$, one can provide a sequence of inputs to be inserted so that the resulting tree is $\mu$-imbalanced.

**Question.** Is there any binary search tree structure, with the usual characteristics of $O(\log n)$ insertion and search time, and some $m \> 0$, such that the tree will always be $\mu$-balanced for some $\mu \> m$?

# Answer
Yes, I believe there is (though I don't remember the details of the paper to confirm).

This is the original paper which dealt with that:

> Nievergelt J. and Reingold E.M., "Binary search trees of bounded balance", Proceedings of the fourth annual ACM symposium on Theory of computing, pp 137--142, 1972

Here is a page on weight-balanced trees which seems to have some more information and mentions their usage in functional languages.

This paper: On Average number of rebalanced operations in weight balanced trees, seems to be investigating the number of rebalancing operations in weight balanced trees.

I also seem to remember that one Knuth's Art of ... books had a reference to the above Reingold paper (perhaps in the exercises).
> 6 votes

---
Tags: data-structures, search-trees
---


# Question
Title: NP complete problems that are solvable in polynomial time if the input (e.g. number of variables) is fixed?
I have seen some problems that are NP-hard but polynomially solvable in fixed dimension.

Examples, I think, are Knapsack that is polynomial time solvable if the number of items is fixed and Integer Linear Programming with fixed number of variables or constraints by Lenstras result.

Questions:

What are other examples of NP-hard problems that become polynomial time solvable if the dimension is fixed?

Are there problems for which this is not the case?

Is this always the case for problems that admit an FPTAS/pseudo-polynomial time algorithm such as Knapsack?

# Answer
In parametrized complexity we solve the problem by fixing some parameter (say $k$). If we are able to solve some problem in $f(k) \cdot p(n)$ time, we say the problem is *fixed parameter tractable* in $k$. Here $f(k)$ is just some computable function. There are lots of NP-hard problems that are FPT, however, there are many problems in NP that are believed to not be fixed parameter tractable.

If by fixing some parameter we can solve a problem in time $O(n^{f(k)})$, this problem is said to be in XP. We believe that XP is not equal to FPT (just as we believe P $\neq$ NP). But there are also lots of problems between these two (FPT and XP), and we have defined a hierarchy (actually several), one of those being the W-hierarchy. In the W hierarchy you have reductions like reduction in NP-complete classes, except, we are not looking for polytime reductions, we just need an FPT reduction. The class W\[0\] is the class FPT.

These are some samples in different classes of the W hierarchy:

1. Vertex cover is FPT (so is vertex disjoint paths on undirected graphs)
2. Independent set and Clique are both W\[1\]-complete
3. Dominating set is W\[2\]-Complete.

These are another level of complexities to classify NP problems in more precise way and if you want more you can look at this paper.

And if you want even more is good to read Grohe and Fomine's book

And finally:

> Is this always the case for problems that admit an FPTAS/pseudo-polynomial time algorithm such as Knapsack

Not necessarily, it's known that if the problem has FPTAS then it's also FPT (which is obvious), but there is some works on the relation of PTAS and XP, but there isn't very tight relation between PTAS and W hierarchy (at least I don't know at this moment).

Also in some cases may be we fix some different parameters, e.g: length of a longest path in the graph is bounded and size of a solution is bounded (e.g in feedback vertex set), ...
> 5 votes

---
Tags: np-complete, optimization, decision-problem, linear-programming, parameterized-complexity
---


# Question
Title: Hardness of approximation of the 3 colorability problem
If we have polynomial algorithm that $c$-approximation, $c\<\frac{4}{3}$ for graphs that their chromatic number $\geq k$ then $NP=P$, how to prove such statements?

I also have some sort of explanation of this statement: It's NP-hard to separate between graphs that have chromatic number $k$ and chromatic number $c \cdot k$ when $c\<\frac{4}{3} \quad \forall k\geq 3$

# Answer
Hint: Consider planar graphs.
> 5 votes

---
Tags: algorithms, np-hard, approximation
---


# Question
Title: Algorithm analysis question in growth of functions
How would I solve the following.

An algorithm that is $O(n^2)$ takes 10 seconds to execute on a particular computer when n=100, how long would you expect to take it when n=500?

Can anyone help me answer dis.

# Answer
> 0 votes
Since it is $O(n^2)$, then $t \leq c n^2$. Therefore, since $t = 10$, and $n = 100$, $c \geq t / n^2 = 10 / 100 00$.

Therefore, at $n = 500$. You have $t \leq 10 / 100 00 \times 500^2 = 250$.

But wait, the definition of the $O$-notation claims that the above formula works for large $n$'s only. I assumed that. Although honestly, I dont like this question. It is a bet weird.

# Answer
> 5 votes
Formally, there is absolutely no way to tell. O( ) notation is about the limiting behavior of a function (in this case, the running time of an algorithm) as its argument (in this case, the input size) grows to infinity. Without more information, it is absolutely impossible, even in principle, to predict behavior in the limit from a finite number of function values.

---
Tags: algorithms, time-complexity, asymptotics
---


# Question
Title: Proving that language is regular or not regular
> Let $L$ be a regular language. Prove that:
>
> 1. $L\_{+--}=\left\\{w: \exists\_u |u|=2|w| \wedge wu\in L\right\\}$
> 2. $L\_{++-}=\left\\{w: \exists\_u 2|u|=|w| \wedge wu\in L \right\\}$
> 3. $L\_{-+-}=\left\\{w:\exists\_{u,v} |u|=|w|=|v| \wedge uwv\in L\right\\}$
>
> are regular and:
>
> 1. $L\_{+-+}=\left\\{ uv:\exists\_w |u|=|w|=|v| \wedge uwv\in L \right\\}$
>
> is not regular.

Seems very hard to me. I suppose 1-3 are similar (but I may be wrong), but I don't know how to approach. General idea is usually to modify finite state machine for $L$ to accept other language. But those constructions are often very sophisticated and I still can't come up with it alone.

# Answer
Here is a proof that the language $L\_0 = \\{ w : \exists\_u |u|=|w| \land uw \in L \\}$ is regular. It can be modified to show that the first three on your list are regular. (Note that I changed $wu$ to $uw$.) Given a DFA for $L$, we build an NFA for $L\_0$. The first thing that the NFA does is guess (take an $\epsilon$ move) a state $q$, whose intended semantics is the state that the DFA for $L$ ends up after reading $u$. It then simultaneously runs two copies of the DFA for $L$, one starting at the start state and the other starting at $q$. On reading a symbol $a$, it moves according to an arbitrary symbol on the first, and moves according to $a$ on the second. A state is accepting if the first copy is at state $q$ and the second is at an accepting state.

For the final one, consider the language $L= a^+ b^+ c^+$, and intersect $L\_{+-+}$ with $a^+ c^+$.
> 6 votes

---
Tags: regular-languages
---


# Question
Title: k-basis representation of natural numbers
(This is the problem 1.56 from Michael Sipser' Introduction to the theory of computation )

Let
$A\_k(S)= \\{ w |w \text{ is the k-basis representation}$
$\text{ without leading 0 of some natural number in the set S}\\} $

Example : $A\_2 (\\{3,5\\}) = \\{11,101\\} $

Let the statement $ P = \exists S \text{, a set of natural number where} A\_2(S) \text{ is regular and }A\_3(S) \text{ isn't.} $

Is $P$ true ?

---

I think that $P$ is false.

Let's consider two case :

$S$ is finite :

Write a (possibly very long) regular expression which is the union of all of the k-basis representation strings of the numbers in $S$ no matter what $k$ is.

$S$ is infinite :

Construct a NFA $N$ that recognize $A\_k(S)$ with :
$\text{For each symbol }e\in\Sigma\smallsetminus 0, \space$ $\delta(q\_{initial},e) = q\_{begin},\space q\_{begin} \in F $ $\text{For each symbol }e\in\Sigma,\space \delta(q\_{begin},e) = q\_e ,\space \delta(q\_e,\varepsilon) = q\_{begin},\space q\_e \in F $

Am i correct ? (I think I'm not but I'm stuck with this, maybe I don't get the definition of $A$ correctly ).

# Answer
> 1 votes
Hint: For most infinite $S$, the languages $A\_2(S),A\_3(S)$ will both not be regular. Find some set $S$ for which $A\_2(S)$ is regular (since the binary representations of numbers in $S$ are very simple), and with any luck $A\_3(S)$ won't be regular. (Don't choose $S = \mathbb{N}$ or $S = \\{ ax+b : x \in \mathbb{N} \\}$.)

---
Tags: regular-languages
---


title: Algorithmic analysis using log

text:
# Question
Title: Algorithmic analysis using log
How would I solve the following.

An algorithm that is O(Lg\_2 n) takes 10 seconds to execute on a particular computer when n=100, how long would you expect to take it when n=500?

An algorithm that is O(n lg\_2 n) takes 10 seconds to execute on a particular computer when n=100, how long would you expect to take it when n=500?

For the first one would I do

10/ln(100)/ln(2) times ln(500)/(ln2)?

# Answer
> 1 votes
Let's do the first one. The running time of the algorithm is roughly $C\log n$ for some $C$ (we can "swallow" the base of the logarithm into $C$). When $n = 100$ you know that $C\log n = 10s$. Determine $C$, and then compute $C\log 500$. (You can also use a "shortcut" like the one you're trying to do, but it's more helpful to do it this way, since such a shortcut is harder to come by in the second part of the question.)

---
Tags: algorithm-analysis
---


# Question
Title: How to distinguish whether a sample is from distribution $\chi_1$ or $\chi_2$?
I am given an oracle $A$ that takes input samples from two distributions $\chi\_1$ and $\chi\_2$.

Suppose we have $Pr\_{x \sim \chi\_1}\[A(x) = 1\] = p\_1$ and $Pr\_{x \sim \chi\_2}\[A(x) = 1\] = p\_2$, where $p\_1 \neq p\_2$.

In general, how can we use $A$ to construct a distinguisher to determine whether the input samples are from $\chi\_1$ or $\chi\_2$? And how good is the running time of such distinguisher?

Thank you very much! :)

# Answer
> 1 votes
Hint: Run $A$ on lots of samples $x\_1,\ldots,x\_n$ and compute the average $(A(x\_1)+\cdots+A(x\_n))/n$.

---
Tags: complexity-theory, probability-theory
---


# Question
Title: How does variance in task completion time affect makespan?
Let's say that we have a large collection of tasks $\tau\_1, \tau\_2, ..., \tau\_n$ and a collection of identical (in terms of performance) processors $\rho\_1, \rho\_2, ..., \rho\_m$ which operate completely in parallel. For scenarios of interest, we may assume $m \leq n$. Each $\tau\_i$ takes some amount of time/cycles to complete once it is assigned to a processor $\rho\_j$, and once it is assigned, it cannot be reassigned until completed (processors always eventually complete assigned tasks). Let's assume that each $\tau\_i$ takes an amount of time/cycles $X\_i$, not known in advance, taken from some discrete random distribution. For this question, we can even assume a simple distribution: $P(X\_i = 1) = P(X\_i = 5) = 1/2$, and all $X\_i$ are pairwise independent. Therefore $\mu\_i = 3$ and $\sigma^2 = 4$.

Suppose that, statically, at time/cycle 0, all tasks are assigned as evenly as possible to all processors, uniformly at random; so each processor $\rho\_j$ is assigned $n/m$ tasks (we can just as well assume $m | n$ for the purposes of the question). We call the makespan the time/cycle at which the last processor $\rho^\*$ to finish its assigned work, finishes the work it was assigned. First question:

> As a function of $m$, $n$, and the $X\_i$'s, what is the makespan $M$? Specifically, what is $E\[M\]$? $Var\[M\]$?

Second question:

> Suppose $P(X\_i = 2) = P(X\_i = 4) = 1/2$, and all $X\_i$ are pairwise independent, so $\mu\_i = 3$ and $\sigma^2 = 1$. As a function of $m$, $n$, and these new $X\_i$'s, what is the makespan? More interestingly, how does it compare to the answer from the first part?

Some simple thought experiments demonstrate the answer to the latter is that the makespan is longer. But how can this be quantified? I will be happy to post an example if this is either (a) controversial or (b) unclear. Depending on the success with this one, I will post a follow-up question about a dynamic assignment scheme under these same assumptions. Thanks in advance!

**Analysis of an easy case: $m = 1$**

If $m = 1$, then all $n$ tasks are scheduled to the same processor. The makespan $M$ is just the time to complete $n$ tasks in a complete sequential fashion. Therefore, $$\begin{align\*} E\[M\] &= E\[X\_1 + X\_2 + ... + X\_n\] \\ &= E\[X\_1\] + E\[X\_2\] + ... + E\[X\_n\] \\ &= \mu + \mu + ... + \mu \\ &= n\mu \end{align\*}$$ and $$\begin{align\*} Var\[M\] &= Var\[X\_1 + X\_2 + ... + X\_n\] \\ &= Var\[X\_1\] + Var\[X\_2\] + ... + Var\[X\_n\] \\ &= \sigma^2 + \sigma^2 + ... + \sigma^2 \\ &= n\sigma^2 \\ \end{align\*}$$

It seems like it might be possible to use this result to answer the question for $m \> 1$; we simply need to find an expression (or close approximation) for $\max(Y\_1, Y\_2, ..., Y\_m)$ where $Y\_i = X\_{i\frac{n}{m} + 1} + X\_{i\frac{n}{m} + 2} + ... + X\_{i\frac{n}{m} + \frac{n}{m}}$, a random variable with $\mu\_Y = \frac{n}{m}\mu\_X$ and $\sigma\_Y^2 = \frac{n}{m}\sigma\_X^2$. Is this heading in the right direction?

# Answer
As $m = k \times n$, we can look at this in terms of $k$ and $n$ instead of $n$ and $m$. Let's say $T\_i$ is the time it takes the $i$-th processor to finish its work.

As $n$ grows, the probability that $T\_i$ = $5k$ (the processor was assigned only $T=5$ tasks) for some $i$ approaches $1$, so makespan being defined as $\mathrm{max}(T\_i)$, $E\[M\]$ approaches $5k$.

For the second scenario this is $4k$ so increasing the number of processors makes the 4–2 split better.

What about $k$ — increasing the number of tasks per processor? Increasing $k$ has the opposite effect, it makes it less likely to have a processor with an unlucky set of tasks. I'm going home now but I'll come back to this later. My "hunch" is that as $k$ grows, the difference in $E\[M\]$ between the 4–2 split and the 5–1 split disappears, $E\[M\]$ becomes the same for both. So I would assume that 4–2 is always better except maybe for some special cases (very small specific values of $k$ and $n$), if even that.

So to summarize:

* Lower variance is better, all else being equal.
* As the number of processors grows, lower variance becomes more important.
* As the number of tasks per processor grows, lower variance becomes less important.
> 8 votes

# Answer
I find that heuristic arguments are often quite misleading when considering task scheduling (and closely related problems like bin packing). Things can happen that are counter-intuitive. For such a simple case, it is worthwhile actually doing the probability theory.

Let $n = km$ with $k$ a positive integer. Suppose $T\_{ij}$ is the time taken to complete the $j$-th task given to processor $i$. This is a random variable with mean $\mu$ and variance $\sigma^2$. The expected makespan in the first case is $$ E\[M\] = E\[\max \left\\{\sum\_{j=1}^k T\_{ij} \mid i=1,2,\dots,m \right\\}\]. $$ The sums are all iid with mean $k\mu$ and variance $k\sigma^2$, assuming that $T\_{ij}$ are all iid (this is stronger than pairwise independence).

Now to obtain the expectation of a maximum, one either needs more information about the distribution, or one has to settle for distribution-free bounds, such as:

* Peter J. Downey, *Distribution-free bounds on the expectation of the maximum with scheduling applications*, Operations Research Letters **9**, 189–201, 1990. doi:10.1016/0167-6377(90)90018-Z

which can be applied if the processor-wise sums are iid. This would not necessarily be the case if the underlying times were just pairwise independent. In particular, by Theorem 1 the expected makespan is bounded above by $$ E\[M\] \le k\mu + \sigma\sqrt{k}\frac{n-1}{\sqrt{2n-1}}. $$ Downey also gives a particular distribution achieving this bound, although the distribution changes as $n$ does, and is not exactly natural.

Note that the bound says that the expected makespan can increase as any of the parameters increase: the variance $\sigma^2$, the number of processors $n$, or the number of tasks per processor $k$.

For your second question, the low-variance scenario resulting in a *larger* makespan seems to be an unlikely outcome of a thought experiment. Let $X = \max\_{i=1}^m X\_i$ denote the makespan for the first distribution, and $Y = \max\_{i=1}^m Y\_i$ for the second (with all other parameters the same). Here $X\_i$ and $Y\_i$ denote the sums of $k$ task durations corresponding to processor $i$ under the two distributions. For all $x \ge k\mu$, independence yields $$ Pr\[X \le x\] = \prod\_{i=1}^m Pr\[X\_i \le x\] \le \prod\_{i=1}^m Pr\[Y\_i \le x\] = Pr\[Y \le x\]. $$ Since most of the mass of the probability distribution of the maximum will be above its mean, $E\[X\]$ will therefore tend to be larger than $E\[Y\]$. This is not a completely rigorous answer, but in short, the second case seems preferable.
> 2 votes

---
Tags: probability-theory, scheduling, parallel-computing
---


# Question
Title: Prove that inserting $n$ sorted values in to an AVL using AVL insertion is $\Theta\left (n \log \left ( n \right ) \right )$
We're asked to prove the above mentioned lemma but I having a hard time proving this rigorously.

We did prove that given $n$ values AVL's height is $\Theta\left (\log \left ( n \right ) \right )$ So I thought that after inserting a $\frac{n}{2}$ values the height of the tree will be at least $\Theta\left (\log \left ( \frac{n}{2} \right ) \right )$ which and because each isertion we make is now on a tree with at least $\frac{n}{2}$ and insertion is $\log \left (h \right ) $ where $h$ is the height of the tree.

So for a function $F$ using the previous logic:

$\begin{align} F &= \frac{n}{2} \times \log \left (h \right ) \\\& \geq \frac{n}{2} \times \log \left (\frac{n}{2} \right ) \\\&=\Omega\left( n\log \left (n \right ) \right) \end{align}$

But I have a few issues with this

* This does feel fishy to me don't know why but it doesn't feel like a good well defined calculus proof :)
* I'm not sure which way to take it in order to prove the upper boud i.e $\mathcal{O}$

If I haven't given all the required information I'd be glad to.

# Answer
> 2 votes
The upper bound is easy. Because a tree with $n$ nodes has height $\Theta(\log n)$, when inserting the sequence of elements each tree has height at most $O(\log n)$, so the total complexity is $O(n\log n)$.

You're right with the lower bound. After inserting $n$ elements the tree has height $\Theta(\log \frac{n}{2})=\Theta(\log n - \log 2)=\Theta(\log n)$. So we can split the sum into two and bound each part by its lowest element: \begin{align} \sum\_{i=1}^n \Theta(\log i) &= \sum\_{i=1}^{n/2} \Theta(\log i) + \sum\_{i=n/2+1}^n \Theta(\log i) \\ &= \frac{n}{2} \Omega(\log 1) + \frac{n}{2} \Omega(\log\frac{n+1}{2})\\ &= n\\,\Omega(\log n) \\ &= \Omega(n \log n) \end{align}

---
Tags: algorithms, data-structures, binary-trees, search-trees
---


# Question
Title: Is the language of binary representation of perfect squares regular?
Let $\mbox{bin}(n)$ denote the binary representation of an integer $n$. Let $L = \\{ \mbox{bin}(n^2) \mid n \in \mathbb{N} \\}$.

> Is $L$ a regular language?

I think one can prove that $L$ is not regular by using the pumping lemma, but I don't know how to use it here.

# Answer
> 10 votes
We start with a lemma.

**Lemma.** Let $a\>b \geq 4$. If $2^a+2^b+1$ is a square then $a \geq 2b-3$.

**Proof.** Let $2^a+2^b+1 = x^2$. Clearly $x$ must be odd, say $x = 2y+1$. Then $x^2 = 4y^2 + 4y + 1$, and so $(y+1)y = y^2+y = 2^{a-2} + 2^{b-2} = 2^{b-2}(2^{a-b}+1)$. If $y$ is even then $y+1$ is odd and so $y = 2^{b-2}z$ for some odd $z$, and therefore $2^{a-b}+1 = (2^{b-2}z+1)z \geq 2^{b-2}+1$ and so $a \geq 2b-2$. If $y$ is odd then necessarily $y+1 = 2^{b-2}z$ for some odd $z$, and therefore $2^{a-b}+1 = z(2^{b-2}z-1) \geq 2^{b-2}-1 = 2^{b-3} + 1 + (2^{b-3}-2)$. Since $b \geq 4$, we can conclude that $a \geq 2b-3$. $\square$

Let $L' = L \cap 10^\*10^\*0001$. According to the lemma, all words in $L'$ are of the form $10^{a-b-1}10^{b-1}1$ with $a-b-1 \geq (b-1)-3$. Moreover, since $2^{2c} + 2^{c+1} + 1 = (2^c+1)^2$, for all $c \geq 3$, $10^{c-2}10^c1 \in L'$.

If $L$ is regular then so is $L'$, say its minimal DFA has $p$ states. Consider the word $10^{p-2}10^p1 \in L'$, and mark the substring $0^p$. The extended pumping lemma shows that for some $0 \< q \leq p$, $10^{p-2}10^{p+q(t-1)}1 \in L'$ for all $t \geq 0$. However, according to our lemma, for all $t$ we must have $p-2 \geq p+q(t-1)-3$ and so $1 \geq q(t-1)$, which is false for $t \geq 3$.

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


# Question
Title: Are there real lexers that use NFAs directly instead of first transforming them to DFAs?
I am taking the Coursera class on compilers and in the lesson about lexers it is hinted that there is a time-space tradeoff between using non-deterministic finite automaton (NFA) and deterministic finite automaton (DFA) to parse regular expressions. If I understand correctly, the tradeoff is that a NFA is smaller, but is more time consuming to traverse because all possible states have to be regarded at the same time and therefore it is most of the time transformed into a DFA. Are there any lexers that use NFAs instead of DFAs in "real"-life i.e. some compiler that is used in production and not a just a proof of concept?

# Answer
> 5 votes
*Compiled* lexical analyzers compile the NFA to a DFA.

Good *interpreted* regular expression matchers, on the other hand, use Thompson's algorithm, simulating the NFA with memoization. This is equivalent to compiling the NFA to a DFA, but you only produce DFA states on demand, if they are needed. At each step your deterministic state is a set of NFA states, then given the next input character you transition to a new set of NFA states. You cache previously seen states and their output transitions in a hash table. The hash table is flushed if it fills up, it does not grow without bound.

The reason you do it this way is that converting the NFA to DFA can take time exponential in the size of the regular expression. This is certainly not something you want to do if you are only evaluating the regular expression once.

RE2 is an example of a regex engine that (essentially) uses Thompson's algorithm. I can highly recommend the brilliant blog posts by RE2's author Russ Cox if you want to learn more (including lots of historical information and experimental comparisons of lots of different approaches to regex searching.

I can also highly recommend the "why GNU grep is fast" email chain. Lesson 1 is: the common case for regex search is simple string search, so special case your algorithm.

# Answer
> 4 votes
I see only two applications of using an NFA (or rather its power automaton without writing it down) instead of a minimized DFA:

1. Homoiconic languages, where you may want to modify your lexer frequently
2. Strange syntax that may blow up your DFA like

```
identifier := [a-z][a-z0-9_]*
indices := [0-9_]{1,256} //up to 256 times
var := identifier "_" indices | identifier

```

If you take the last rule as a precedence, your lexer has to check whether an identifier contains "\_" within the last 256 symbols and shorten it in this case.

# Answer
> 3 votes
I'd be surprised if they did. The *construction* of the lexer is done once (hopefully), the result *used* millions of times (just think how many tokens there are in your medium-sized source file). So, unless there are very unusual circumstances, it pays off to make the lexer as fast (and other resource frugal) as possible, i.e., go for a minimal DFA.

# Answer
> 0 votes
In the strict formal sense, no. Non-determinism in the theory/mathematical sense allows a machine to choose a computation path based on whether it eventually leads to an accepting state or not *without looking any further ahead in the input*. So in this strict sense it's a property that's only suitable for theoretical examination, and there's no such thing as a real non-deterministic machine, particular to this case you can't actually build an NFA, unless you can see into the future, in which case building a compiler with this talent is a bit of a waste! ;).

However, nondeterministic and nondeterminism are often used in a weaker sense, hazily defined. Sometimes it can mean randomised/probabilistic - the algorithm flips a coin, in a formal setting this is studied as probabilistic/randomised algorithms, and not referred to as nondeterminism. Another use is for an algorithm that doesn't necessarily produce the same output given two runs on the same input - it may not be random, but some part of its behaviour is unspecified, so there may be several valid outputs (personally I think this definition comes comes from confusing *un*-determined and *non*-deterministic.

Nonetheless, you could, in principle build a lexer that is nondeterministic in one of these weaker, informal senses, however it wouldn't be an NFA (that's a strict formal machine model) and I can't imagine it'd be a crash hot idea either - a lexer needs to be quite predictable.

The last option is that you can simulate non-determinism via backtracking or parallelism, but in this case you lose out on the apparent efficiency of non-determinism, as you're effectively turning it into a deterministic computation, so you're no better off than with a DFA.

---
Tags: finite-automata, compilers, efficiency, nondeterminism, lexical-analysis
---


title: Easiest way to write a grammar?

text:
# Question
Title: Easiest way to write a grammar?
When I see a problem like "Write a grammar for a language $L$ if $L = \\{..\\}$" for me is a matter of "instinct" the way that one can define productions. For example given the following exercise:

> Let $L$ a language which alphabet is $\\{x,y,z\\}$ and accepts strings $w$ where there aren't consecutive $x$'s nor consecutive $y$'s nor consecutive $z$'s.

My first aproaching was to stablish that $x$, $y$ and $z$ each one are in $L$, that is:

$$S \rightarrow x \mid y \mid z$$

If the string has an $x$, there can be a consecutive $y$ or $z$, similarly for the other symbols. I assume that there are productions $A$, $B$ and $C$ that make the work, so the start production is:

$$S \rightarrow xA\mid yB\mid zC\mid x\mid y\mid z$$

Therefore $S$ can be splitted to define $A$, $B$ and $C$:

$\begin{eqnarray\*}S &\rightarrow& A \mid B \mid C \\A &\rightarrow& yB \mid zC \mid y \mid z \\ B &\rightarrow& xA \mid zC \mid x \mid z\\ C &\rightarrow& xA \mid yB \mid x \mid y \end{eqnarray\*}$

But as you all can see this is just my version, I started with base strings accepted by $L$ and then I followed my own thought of how to build the grammar. Is there a easy way to do this? or some advice for similar languages? (like those which have different number of symbols).

# Answer
> 3 votes
Of course "instinct"always helps, but writing a grammar is more or less writing a program, but with limited resources.

Your example matches a regular language. Those languages can be defined using right-linear grammars but I prefer finite state automata. Programming linear grammars (and finite state automata) requires thinking in states. What is the characteristic information about the string I have seen so far.

In your example the "state" consists of the last letter read. OK, since your task is to avoid reading a letter twice. In other examples you might want to do some counting ("if the string contains exactly four $a$'s it ends in $b$") or modulo counting ("the number of $a$'s is even"). Perhaps you want to do a kind of pattern recognition ("words that do not contain $00110$") and you keep track of the part of the pattern you have just seen.

Sometimes the requirements consist of a Boolean combination of properties. Then you keep track of both of them in the state and react on what you know.

You see: just like programming.

If the grammar is more complicated, like context-free you probably want to think in terms of trees. That is the structure they use to derive strings.

# Answer
> 2 votes
The language you are describing is regular. Thinking in terms of states, as Hendrik Jan points, is helpful. If you are scanning a string for acceptance or rejection, then after reading one character (say $x$) you want the next one to be a member of ($\Sigma - \\{x\\}$).

An automaton for this language can have a state per alphabet symbol. So you could start by sketching the following:

A valid string can start by any alphabet symbol, so we have to add a start state with epsilon-moves to the remaining states. A valid string can end in any alphabet symbol as well, so every state is accepting. We get the following non-deterministic FSA.

You can get a right-reglar grammar by determinizing the above automaton.

---
Tags: context-free, formal-grammars
---


# Question
Title: Sublinear query time for the $i$th element of an array after some additions?
We are given an array $A\[1..n\]$ of integers, and an array of 3-tuples known as queries. The query tuples $(i,j,v)$ denote additions of an integer $v$ to the subarray of $A\[i..j\]$. I'm interested in the query time of $A\[k\]$ for $1 \leq k \leq n$ between the queries.

For example, let $A = \[1,2,3,4\]$, and let the queries be $Q = \[\[1,2,5\],\[2,3,6\],\[1,3,10\]\]$. After the second query has been processed, say I want to find the value of $A\[3\]$, which would be $3+5+6=14$. Does an algorithm exists to do this in less than linear time?

# Answer
> 5 votes
Yes, there are good data structures for this. The running time to handle $q$ queries and $\ell$ lookups will be $O((q+\ell) \lg n)$ time in total, or in other words, $O(\lg n)$ time per query and $O(\lg n)$ time per lookup. This can be much faster than linear time in general.

Let $A\_\text{orig}\[1..n\]$ denote the original value of the array $A$. We're going to build a data structure to represent the array $\Delta\[1..n\]$ of integers, where $\Delta\[i\]$ holds the amount that $A\[i\]$ has been increased by (given the queries so far). Thus, to compute $A\[i\]$, it suffices to look up $A\_\text{orig}\[i\]$ and $\Delta\[i\]$ and return their sum.

The question is, how do we maintain the $\Delta\[\]$ array in a way that we can efficiently look up $\Delta\[i\]$ at any index $i$, and that we can efficiently update $\Delta$ in response to a particular query?

If we represent $\Delta$ as an array, then lookups take $O(1)$ time, but updates (handling a query) may take $\Theta(n)$ time, which is no good.

A better solution is to represent $\Delta$ using an interval tree. With the proper data structures, each lookup will take $O(\lg n)$ time, and each update (processing each query) will take $O(\lg n)$ time. This should give an efficient algorithm.

An interval tree holds a set of non-overlapping intervals. In our case, the intervals will be consecutive ranges of array indices for which $\Delta$ holds the same value. We will augment the data structure to hold the value of $\Delta$ for each such interval.

For example, initially the interval tree could be represented as $\[1,n\] \mapsto 0$, to represent that all indices in the interval $\[1,n\]$ yield the value 0; so $\Delta\[i\]=0$ for all $i$. If we now receive the query $(1,2,5)$, then $\Delta$ is updated to the interval tree $\[1,2\] \mapsto 5, \[3,n\] \mapsto 0$. If we then receive the query $(2,5,6)$, then the interval tree should be updated to $\[1,1\] \mapsto 5, \[2,2\] \mapsto 11, \[3,5\] \mapsto 6, \[6,n\] \mapsto 0$.

We can store the interval tree using a binary search tree. If we have $m$ intervals, then there will be at most $2m$ unique endpoints of the intervals. We store these endpoints in a binary search tree. Each leaf node represents a single endpoint. We will augment the nodes with a value: if a node represents the integer $a$ (an array index) and the next-largest integer endpoint is $b$, then the value $v$ at the node for $a$ means that the interval tree contains $\[a,b-1\] \mapsto v$.

Note that each query can be processed in $O(\lg n)$ time. That's because a query might possibly split two existing intervals in the tree into two sub-intervals. Each split operation can be handled in $O(\lg n)$ time by inserting one node into the binary search tree.

Similarly, lookups can be handled in $O(\lg n)$ time, by traversing the binary search tree to find the largest node that is less than or equal to the index you're looking up.

This provides a sub-linear time solution to your problem. Processing $q$ queries and $\ell$ lookups to the array takes $O((q+\ell) \lg n)$ time in total.

# Answer
> 1 votes
If `start - end + 1` is equal to the number of elements in the array, then you have to touch every element. This is linear in the size of the array.

```
add(array, start, end, increment)
{
  if(increment == 0) return;
  for(i = start; i <= end; ++ i)
  {
    array [i] += increment;
  }
}

add_all(array, queries)
{
  for(q in queries)
  {
    add(array, q.start, q.end, q.increment);
  }
}

```

You can use an interval tree (a red-black tree data structure augmented to handle intervals). Querying the ith element is equivalent to finding queries whose intervals overlap with i (say $q\_1,\dots,qn$) and returning the sum of array\[i\] and the increments of those queries, i.e. $\text{array}\[i\] + q\_1.\text{increment}+\dots+q\_n.\text{increment}$.

Finding overlapping intervals takes $O(\log n)$ time. If the number of queries is small, then accessing the ith element takes $O(\log n)$ time.

---
Tags: algorithms, arrays
---


title: Alpha-Beta pruning in chess?

text:
# Question
Title: Alpha-Beta pruning in chess?
How can alpha-beta pruning be made safe for a chess program? Pruning away a certain set of nodes is safe when the tree is complete and it is known that no other new nodes can be found deeper in the tree, but obviously this is not the case in chess. If my program prunes away a move that looks bad because it sacrifices valuable material that may just be the sacrificial move that would have checkmated the opponent in another few additional ply (or just gain a material and/or tactical advantage)?

# Answer
What you are describing is unrelated to alpha-beta pruning. The tendency of fixed-depth minimax searches to badly underestimate or overestimate positional scores in dynamic situations is known as the horizon effect. The problem is due to static evaluation being used on positions unsuited to such evaluation. Static evaluation scores a position based on things like material, pawn structure, and king mobility, properties that can be determined without extending the search tree. But some positions are transitional, needing more search to identify their nature.

The standard way to deal with this problem is to recursively apply a quiescence function to all terminal nodes that extends the search an extra ply if there are checks, forced captures or promotions available at that node. If no such moves are available, then the position is considered quiet and the usual static evaluation function is called.
> 5 votes

---
Tags: algorithms
---


# Question
Title: Why don't we scale the cost of memory access when analyzing runtime of algorithms?
Runtime for many programming languages is typically analyzed either assuming each operation takes a constant amount of time, or assuming each operation takes a logarithmic amount of time in the size the the data being manipulated. From a practical perspective, this is reasonable since modern computers have essentially constant time memory access (albeit for a fixed amount of memory).

However, from a theoretical perspective, it seems to me that this is a bad assumption.

Since bits can't be stored denser than the Planck scale (which we are fast approaching), the number of bits we can store in a certain volume of space can grow at most linearly as volume grows. Further, since the speed of memory retrieval and storage is bounded by the speed of light, it makes a lot of sense to say that as the size of the data we store grows, the cost for storing and accessing it should grow. For instance, one could assume that storing and accessing the $n$th bit of data requires $\sqrt\[3\]{n}$ time. (Since space is 3-dimensional).

Presumably this has been discussed in the literature somewhere. Could anyone point me to some references? Have algorithms been analyzed using this model?

# Answer
You are totally right in your observation. If complexity analysis would be done on a Turing machine level the memory distance would be taken into account. You may use a 3 dimensional tape if you like and your analysis is on sub-polynomial level.

My Master thesis in 1990 was about the same topic. In that thesis I argued that instead of looking at the number of transistors/gates we should look at the length of the wires. Looking at it that way some seemingly smart ideas to reduce complexity break down. One example I used was Lupanov's method to represent an arbitrary function in a circuit taking $O(\frac{2^n}{n})$ gates. This is actually not much more efficient than a regular ROM when the average length of the wires is taken into account.

Things can get worse. If you consider a RAM machine where registers can be addressed from another register (pointers) and multiplication can be done in unit time, then it has been shown that PSPACE problems can be solved in polynomial time. I don't have a reference at hand, it was folklore at the time of my college years.

In answer to the question below. The crux of the method consists of (ab)using the fact that all registers are initially zero and the pointer arithmetic is used to leave the majority of registers at 0 and sparsely put a value in others. The registers now serve as a huge lookup table, without the burden of initializing the table.

On the wiki page for Pointer machine you will find a quote from Peter van Emde Boas:

> an interesting theoretical model, but ... its attractiveness as a fundamental model for complexity theory is questionable. Its time measure is based on uniform time in a context where this measure is known to underestimate the true time complexity. The same observation holds for the space measure for the machine (van Emde Boas (1990) p. 35)

The referred book of Van Leeuwen most likely describes the method to solve PSPACE problems on these machines in polynomial time. You may actually want to check, because it is quite some time ago for me and the machine might also need the parallelism of the PRAM model.
> 6 votes

# Answer
Usually estimations are refined only if they aren't valid in the interesting domain. Complexity theory is already a crude approximation (ignoring constant factor, ignoring all terms but one) and for interesting problem sizes considering the memory access time as constant doesn't reduce its usefulness. If you want to be more precise, taking the constant factor and some additional terms into account or the disparity in access time due to caching is probably more worthwhile. (Note that in practice the effect you are speaking will appear as a disparity in access time due to caching).
> 1 votes

---
Tags: reference-request, time-complexity, asymptotics, runtime-analysis
---


title: Disk scheduling and process scheduling

text:
# Question
Title: Disk scheduling and process scheduling
Whats the diffrence between Disk scheduling and process scheduling? I mean i know the roles of disks and processes, but it seems to me they both have the same aim. to reduce monopolies, they even both share similar algorithms like first come first serve. Am i right?

# Answer
This is part of a bigger concept called "caching". When you run a program, we would like to have it in CPU registers because is the fastest memory, but that is very expensive, so the programs (processes) are sent to RAM (also we would like to run many processes, more than the registers may keep). RAM soon or later will be full, we need to keep more programs on memory, so the next caching level is send the processes that aren't being used from RAM to disk.

* The disk scheduling then consist in send to disk the processes that are not being used right now, but someday they will.
* The process scheduling allows you to use many programs and apps in a "paralell" way (you see that everything is executing at the same time, but is just an illusion).

In fact as you mention, some algorithms are used for both functions, and I think it's because in both case you have to decide what are you going to use and bring it.

So the goal is sightly different, but uses the same ideas.
> 0 votes

# Answer
Disk scheduling has an additional physical constraint. Accelerating and moving the disk head takes times in the msec range. Wikipedia says average seek times are around 10 msec (to move halfway across the radius of the disk) and the time to move just to the adjacent track is about .5 msec. Thus an algorithm like FIFO might be reasonable for process scheduling because it would deliver about the same compute throughput as any other scheduling algorithm, but FIFO would be a disaster for disk scheduling.

You are not correct that the *primary* objective of either disk scheduling or process scheduling is "to reduce monopolies". In real time process scheduling, for example, the primary objective is to make sure that processes with lower priority *never* run when there is a higher priority process available.

There are things that are worse than monopolies on workstations too. If you are time sharing between some number of processes that are consuming so much VM that you are thrashing then no-one is getting any service, and you are better off being less fair (swapping out processes until the ones that are left can get some CPU service and hopefully finish.)

Finally, most real operating systems try to give priority to "interactive" processes. But you can't figure out which processes are interactive until you've seen them running. So you use an algorithm like Corbato's Multi-level feedback queue.

**Edit**: I forgot to mention that disk scheduling algorithms are often variants of the elevator scheduling algorithm. This moves the disk head in one direction, doing requests in the order that they lie on the disk. The objective in the elevator algorithm is to maximize throughput while putting a bound on unfairness.
> 1 votes

---
Tags: operating-systems, process-scheduling
---


# Question
Title: change the info part of each node in binary tree
i have a binary tree.

```
         2
       /   \
      3     4
     / \     \
    5  1      8
     \       /
     6      9

```

I want to change the info part of each node such that the

```
nodeinfo = nodeinfo + nextInorderNodeInfo

```

so the actual inorder traversal

```
5, 6, 3, 1, 2, 4, 9, 8

```

will change to

```
5+6,6+3,3+1,1+2,2+4,4+9,9+8,8+0

11, 9,  4,  3,  6,  13, 17, 8

```

i need to write a function that will modify the binary tree info parts of each node.

i have done the following

calling

```
change(root,NULL);

```

function definition

```
void change(node* n, node *k)
{
 if (n)
  {
    if (n->left) change(n->left,n);
    if (n->right) change(n,n->right);
    n->info + = k->info;
  }
}

```

in this way i am not able to modify the nodes that are right hand leaf nodes.

can someone give the correct solution..???

thanks in advance

# Answer
> 1 votes
In my point of view, since you want to use the next info in the inorder traversal, you have to do a function that traverse you tree backward for this order.

```
    int change(node* n,int next){
     int k;
     k=next;
     if(n){
      if(n->right) k = change(n->right,next);
      if(n->left) change(n->left,n->info);
      n->info += k;
     }
    }

```

That way, calling

```
     change(root,0)

```

You have next that is the info of the next node in your order.

I hope I didn't made a mistake and that it help.

---
Tags: data-structures
---


# Question
Title: Changing AVL's balance factor to some other $s>2 \in \mathbb{N}$
Given we change the rule to:

> $-s \ \ \leq$ height(left-subtree) - height(right-subtree) $\leq \ \ s$

I was wandering whether it's possible and how would it affect the trees' height, would it still be logarithmic?

Would the exact same balancing techniques work? (if we took those methods from a normal AVL and try to convert our modified AVL to a normal AVL running from down to top or to down).

I've tired drawing some schematics in order to find out what would be the minimal number of nodes $m$ for some tree $T$ with height $h$ like we did with a regular AVL but I had a real hard time formalizing it.

# Answer
> 2 votes
If the maximal branch is of height $h$ then you know that all the other branches have at least height $h-s$.

Lets consider $n$ the number of nodes in the two extreme case:

1. All branches of height $h$: $n=2^h$
2. One branch of height $h$ the others of height $h-s$: then $n=2^{h-s}+s$

Hence $ 2^{h-s}+s=\frac{2^h}{2^s}\leq n\leq 2^h$ since $s$ is a constant the height is still logarithmic in the number of nodes.

I think this answer your other questions too.

---
Tags: algorithms, data-structures, binary-trees, trees
---


# Question
Title: Dealing with intractability: NP-complete problems
Assume that I am a programmer and I have an NP-complete problem that I need to solve it. What methods are available to deal with NPC problems? Is there a survey or something similar on this topic?

# Answer
> 61 votes
There are a number of well-studied strategies; which is best in your application depends on circumstance.

* ***Improve worst case runtime***
Using problem-specific insight, you can often improve the naive algorithm. For instance, there are $O(c^n)$ algorithms for Vertex Cover with $c \< 1.3$ \[1\]; this is a *huge* improvement over the naive $\Omega(2^n)$ and might make instance sizes relevant for you tractable.
* ***Improve expected runtime***
Using heuristics, you can often devise algorithms that are fast on many instances. If those include most that you meet in practice, you are golden. Examples are SAT for which quite involved solvers exist, and the Simplex algorithm (which solves a polynomial problem, but still). One basic technique that is often helpful is *branch and bound*.
* ***Restrict the problem***
If you can make more assumptions on your inputs, the problem may become easy.

+ **Structural properties**
    Your inputs may have properties that simplify solving the problem, e.g. planarity, bipartiteness or missing a minor for graphs. See here for some examples of graph classes for which CLIQUE is easy.
    + **Bounding functions of the input**
    Another thing to look at is *parameterised complexity*; some problems are solvable in time $O(2^kn^m)$ for $k$ some instance parameter (maximum node degree, maximum edge weight, ...) and $m$ constant. If you can bound $k$ by a polylogarithmic function in $n$ in your setting, you get polynomial algorithms. Saeed Amiri gives details in his answer.
    + **Bounding input quantities**
    Furthermore, some problems admit algorithms that run in *pseudo-polynomial time*, that is their runtime is bounded by a polynomial function in a *number* that is part of the input; the naive primality check is an example. This means that if the quantities encoded in your instances have reasonable size, you might have simple algorithms that behave well for you.
* ***Weaken the result***
This means that you tolerate errorneous or incomplete results. There are two main flavors:

+ **Probabilistic algorithms**
    You only get the correct result with some probability. There are some variants, most notable *Monte-Carlo* and *Las-Vegas* algorithms. A famous example is the *Miller-Rabin primality test*.
    + **Approximation algorithms**
    You no longer look for optimal solutions but *almost* optimal ones. Some algorithms admit relative ("no worse than double the optimum"), others absolute ("no worse than $5$ plus the optimum") bounds on the error. For many problems it is open how well they can be approximated. There are some that can be approximated arbitrarily well in polynomial time, while others are known to not allow that; check the theory of *polynomial-time approximation schemes*.

Refer to *Algorithmics for Hard Problems* by Hromkovič for a thorough treatment.

---

1. *Simplicity is beauty: Improved upper bounds for vertex cover* by Chen Jianer, Iyad A. Kanj, Ge Xia (2005)

# Answer
> 15 votes
Other answers have addressed this from a more theoretical perspective. Here is a more practical approach.

---

For "typical" NP-complete **decision** problems (*"does there exist a thingy that satisfies all these constraints?"*), this is what I would always try first:

1. Write a simple program that encodes your problem instance as a **SAT instance**.
2. Then take a **good SAT solver**, run it (using the fastest multi-core computer that you happen to have), and see what happens.

Try with smaller instances first to get some idea of how long it might take.

---

Surprisingly often, this approach is **much** better than trying to implement your own solver specifically for your current problem:

* SAT solvers are very clever and well-optimised. They easily outperform your own implementation of backtracking search (no matter how much time you waste optimising your code). They also easily outperform many off-the-self alternatives such as integer linear programming solvers.
* This requires very little programming. Step 1 is relatively straightforward and it is not performance-critical; you can use scripting languages such as Python. Someone else has already taken care of implementing everything that you need for step 2.

---

For typical NP-hard **optimisation** problems (*"find the smallest thingy that satisfies all these constraints"*) this approach may or may not work.

If you can *easily* turn it into a **decision problem** (*"does there exist a thingy of size 4 that satisfies all these constraints?"*, *"what about size 3?"*), great, follow the same approach as above with decision problems.

Otherwise, you might want to resort to a heuristic solver that tries to find a *small* solution (not necessarily the *smallest* solution). For example:

1. Encode your problem as a (weighted) **MAX-SAT instance**.
2. Use the heuristic solvers from the **UBCSAT** package. Heuristic solvers parallelise trivially; try to find a computer cluster with hundreds of computers. You can run the solvers as long as you want, and then take the best solution that you have found so far.

# Answer
> 11 votes
# Parametrized Complexity

One way to attack intractability is thinking about the problem in the parametrized complexity context.

In parametrized complexity we solve the problem by fixing some parameter (say $k$). If we are able to solve some problem in $f(k) \cdot p(n)$ time, we say the problem is *fixed parameter tractable* in $k$. Here $f(k)$ is just some computable function. There are lots of NP-hard problems that are FPT, however, there are many problems in NP that are believed to not be fixed parameter tractable.

If by fixing some parameter we can solve a problem in time $O(n^{f(k)})$, this problem is said to be in XP. We believe that XP is not equal to FPT (just as we believe P $\neq$ NP). But there are also lots of problems between these two (FPT and XP), and we have defined a hierarchy (actually several), one of those being the W-hierarchy. In the W hierarchy you have reductions like reduction in NP-complete classes, except, we are not looking for polytime reductions, we just need an FPT reduction. The class W\[0\] is the class FPT.

These are some samples in different classes of the W hierarchy:

1. Vertex cover is FPT (so is vertex disjoint paths on undirected graphs)
2. Independent set and Clique are both W\[1\]-complete
3. Dominating set is W\[2\]-Complete.

These are another level of complexities to classify NP problems in more precise way and if you want more you can look at Parameterized Circuit Complexity and the W Hierarchy by Downey et al (1998).

And if you want even more is good to read Flum and Grohe's Parameterized Complexity Theory.

And finally:

# Parametrized complexity versus Approximation algorithms:

It's known that if the problem has FPTAS (fully polynomial-time approximation scheme) then it's also FPT (which is obvious) But there is nothing well known in reverse direction, also there is some works on the relation of PTAS and XP, but there isn't very tight relation between PTAS and W hierarchy (at least I don't know at this moment).

Also in some cases may be we fix some different parameters, e.g: length of a longest path in the graph is bounded and size of a solution is bounded (e.g in feedback vertex set), ...

# Sample practical usages:

May be some people believe that parametrized complexity is useless in practice. But this is wrong. Many of parametrized algorithms are discovered in a real world applications, when you can fix some parameters, here is an example:

1. One of a main theorems in parametrized complexity, is do to the Courcell, he provide an algorithm of running time $2^{.^{.^{.^2}}}O(n)$ for some classes of parametrized problems. The number of towers of $2$ is $O(k)$, which means for $k=10$, is impossible. But, one group implemented his algorithm with some modifications on more special case, and they got extremely fast algorithm for vertex cover, which currently used in some subway stations in Germany.
2. One of a fastest and most accurate heuristic algorithms for TSP is : Tour merging and branch decomposition, which uses parametrization of problem (not directly, but branch decomposition and the dynamic programming approach they used is based on some good assumptions).

# Answer
> 5 votes
NP completeness is about worst case intractability. Depending on which problem you are working on, many classes of instances might be solvable in a reasonable time in practice (although you might need a more specialized algorithm to get the good runtimes).

Consider seeing if there is an efficient reduction from your problem to a problem with good solvers available, such as Boolean Satisfiability or Integer Linear Programming.

# Answer
> 4 votes
You have three options in general: The first one is to **consider special cases of your problem**. In some special cases, your problem might be solvable polynomially e.g. determining whether there exists a simple path from $v\_i$ to $v\_j$ to $v\_k$ in an arbitrary directed graph $G$ is NP-Complete but it will be polynomial(linear) when $G$ is reducible. The second option is to **use a good estimation algorithm** to solve your problem. Estimation algorithms provide near-optimal answers to your problem. If you cannot use the previous options, the only remaining way will be: to **use a tolerable algorithm to solve your problem in exponential time**. Among exponential algorithms, the running time of some of them can be tolerable when the input size of your problem is less than a specific value.

# Answer
> 3 votes
Although touched upon briefly in some of the answers, let me emphasize that in practice, NP-complete problems are solved (or approximated) all the time. The main reason that you can solve NP-complete problems in practice is:

> Instances encountered in practice are not "worst-case".

Another reason for the discrepancy is:

> It is difficult to analyze heuristic algorithms formally.

In practice, you use heuristic algorithms to solve your NP-complete problems, and hope for the best. The results are often stunning.

Another issue touched upon in other answers is:

> Sometimes exponential algorithms are fast enough.

That of course depends on the problem. When big data is involved, we have the opposite maxim:

> Sometimes the only feasible algorithms are quasilinear.

---

I'm afraid that the crowd here is rather theoretically inclined. You might get better answers on the main stackexchange site.

---
Tags: algorithms, reference-request, np-complete, efficiency, reference-question
---


# Question
Title: Clique in P when the input graph's connected components have at most $3\log|V|$ vertices?
What's the time complexity of the clique problem for input graphs where each connected component has size at most $3\log|V|$? Is it in P?

# Answer
Indeed, it is:

Consider the input $G,k$. First, it is easy to verify that the sizes of the connected components are as required. Now, if $k\>3\log |V|$, then clearly there is no clique of size at least $k$.

Otherwise, we can find the maximal clique in each component by considering all the subsets of the component.

For a component of size $3\log |V|$, there are $2^{3\log |V|}=|V|^3$ possible subsets of vertices. Once we identified the maximal clique in each component, we can compare this size to $k$, and return the answer.
> 5 votes

---
Tags: algorithms, graphs
---


title: Computability of Kolmogorov Complexity

text:
# Question
Title: Computability of Kolmogorov Complexity
Fix a universal Turing machine $M$.

Let $A^\*=\\{0,1\\}^n$ be the set of all binary string of length $n$.

Determine the Kolmorogov complexity $K(x)$ of each $x\in A$, w.r.t. $M$.

Just for a matter of simplicity assume that $K(x)'=\min(|x|,K(x))$.

Let $B^\*=\\{0,1\\}^n$ be the set of all programs $y\in B$ of $T$: $x= M(y)$.

Now, suppose a parallel machine $M\_p$ that can run each program $y\in B$ for each element in $A$, in parallel. So we can get the length of all the programs $y$ whose machine ended with the right string $x$, and take the minimum as $K(x)'$.

So, should I assume that the non-computability is due to the fact that some machines that has not ended jet whose inputs $y$ are less than the current minimal program will eventually halt? What's the probability of this?

Also, maybe a measure of complexity should include a minimal length with a probabilistic confidence? Say $P(K(x)\geq l)\geq p$?

# Answer
> 4 votes
That's right. You can run all machines in parallel and you'll find shorter and shorter descriptions, but at some point there will always be a shorter program still running, for which you can't prove that it won't halt with $x$ as output.

The probability you describe (of a program not halting, assuming some distribution on inputs) is the complement to Chaitin's omega: the probability that a program will halt. Of course, Chaiting's omega is also not computable and the best way we have of approximating it, is just by running all programs in parallel and summing the probabilities for the ones we've seen halting.

If you start with a probability distribution on outputs, the probabilities have different bounds. If you take a uniform distribution on strings of length $n$, then as $n \rightarrow \infty$, the proportion of strings compressible by more than a few bits is negligible, ie. $K(x) \approx |x|$ with near certainty for large $n$. If you take the universal distribution, then every computable pattern will appear in your string with some probability.

---
Tags: computability, kolmogorov-complexity
---


# Question
Title: How can lazy learning systems simultaneously solve multiple problems?
On the english Wikipedia it says about lazy learning systems:

> Because the target function is approximated locally for each query to the system, lazy learning systems can simultaneously solve multiple problems \[…\]

What does this mean? I can only guess what "approximated locally" is supposed to say but even then I have no idea how one is supposed to follow from the other.

# Answer
After pondering the question for a while longer and talking to a professor of mine, I was able to gain enough insight to say that it is actually not that difficult to answer. Still, I will consider an example:

Given a number of points on plane which, in addition to a **position**, also have further characteristics, e.g. a **color**. If the problem is to estimate the color of a new, proposed point at a given **position**, it can be solved by looking at its $k$-nearest neighbors and determined through a majority vote, i.e. if most of its neighbors are red, assume that the new point will be red as well. If another characteristic is, say, **size**, this can be determined in the same way **without the need to run the $k$-nearest neighbors algorithm again**, thereby solving two problems simultaneously.

An interesting side-note: By searching the internet for the quote that I have taken from Wikipedia, one may turn up at least one book and one bachelor's thesis that use the exact same wording – apparently without citing any references or giving further explanations that might indicate any understanding on the respective author's side.
> 0 votes

# Answer
Let's see:

> Because the target function is approximated locally for each query to the system,

If i am going to predict the class (for example) of a brand new instance i compare it with the most similar in the train dataset. Imagine a 2D graphic with lots of points and i put the new point, so i compare with the other points locally, and the class of the nearest to it will help me say what is its class.

> lazy learning systems can simultaneously solve multiple problems and deal successfully with changes in the problem domain.

Maybe, these problems are the ones created by the eager methods that try to simulate the hyperplanes (boudaries) in a function, in logic predicates, etc between the classes and these hyperplanes make lots of mistakes. And simple local comparisons with the similarity with the train dataset could do a better work.
> 0 votes

# Answer
For the first part of your question about

## "approximated locally"

**Eager learning** methods use all available training examples to build a classiﬁer in advance that is later used for classiﬁcation of all query instances.

**Lazy learning**, or instance based learning, is a learning method that delays the building of the classiﬁer until a query is made to the system. The algorithm is trying to find similar examples from the training data to the query and uses them to build hypothesis for the classification. Examples that are used are localized near the query by some similarity.

For example if we have points in the plane that are classified with (+) sign and (-) sign, the eager learning will build single rule about how to classify any new point. In contrast, the lazy learning will aproximate only the nearest points signs to predict what will be the sign of the new point.

For the second part about

## "simultaneously solve"

I guess that here the author means the **online learning**. This means that each new query is added to the traing data after its value is known.

Because of this, the eager learning must update its hypothesis after each new query and should process each query one at a time.

In contrast, the lazy learning can take many simultanious queries (if they are not locally close) because it uses only the examples, locally close to it.
> 0 votes

---
Tags: terminology, machine-learning
---


title: Vertex Cover problem modification

text:
# Question
Title: Vertex Cover problem modification
Modification of vertex cover problem.
Given a graph G,does G have a vertex cover with 10 vertices? Is this problem still in NP?
Given a graph G and integer k, does G have a vertex cover with k vertices?
Is there any important difference between this two problems?

# Answer
> 4 votes
For fixed $c$ (i.e., we consider $c$ as a constant) this is trivially solvable in time $n^cm$ which is polynomial in $n$, however, if $k$ is part of the input, then $n^k$ would be considered exponential in $k$.

Vertex cover is solvable in $2^k \cdot n^{O(1)}$.

---
Tags: graphs, np
---


# Question
Title: How to generate uniformly random binary trees?
Could someone please provide a reference giving an algorithm to generate uniformly random binary trees?

# Answer
There is a article available here and survey available here

But desipte that its very easy to generate such tree, it all depends on random generator, it must be uniform.

There are two simple approaches:

* Generate full tree up to some height and randomly cut edges
* Start from root and make decision about each child on lower level

Both of them are guarantee to end, fist one is obvious, second one needs some induction proof which is quite simple to do.

Taking into account Juho's hint take a look at Boltzmann sampling, it is indeed a powerfull tool which you can use. And here's a working example.
> 2 votes

---
Tags: trees, randomness
---


# Question
Title: Can we understand SVM without knowledge of Machine Learning
I was told by my adviser (future one) to look into libsvm library or any other and try to get familiar with it.. to work on a programming project (on Machine Learning) (will start in a month).

my background: Programming knowledge in Python, C.. doing Java now.

So, where should I probably start? and How long it takes me to get into ML, SVM etc.. and be productive? Would I probably fit for this project? --considering my programming background (I so far have been much into Web development, wanted to take a change and have fun)

# Answer
I don't think there is anything that should stop you. A couple of tips to set you on the right path:

* The basic principles of Machine Learning are very simple. They are often formalized in a way that makes it look very complicated, but this is only necessary if you want to get into the details of why things work. The general framework of what makes a classifier or what makes a clustering algorithm is very simple. Make sure you understand things on that level, before you dig into the details.
* The title question (can SVMs be understood without ML knowledge) is slightly non-sensical. Understanding the basic ideas of ML is a minor investment and understanding SMVs takes much longer. There's no reason not to get a basic idea of what machine learning is before you dig into SVMs.
* Make sure you have a good intuitive undertanding of the following principles and distinctions: features and instances, clustering and classification, supervised and unsupervised learning. After that, SVMs are just one particular way of solving a particular problem.
* If you understand what a classifier is, you can start using SVMs without knowing anything about how they work or what they do. This may not give you the best result, but it's a good way to start learning by doing.

I can't really give you any references to start reading, since most of what's out there is far to formal for the level you'd want to start with. I recommend browsing around. If something is easy to read, then continue on, if it's too full of math, try something else first.
> 3 votes

# Answer
yes you can but you must know what linear programming is ... dual and primal ... also you must be good with using quadratic programming , and if want to understand the application of SVM then you must know Machine learning ... SVM is a binary classifier that separates linear data ... you can use it to separate nonlinear data by using kernel function which transforms the data to linear one,you have other sort of SVM which allow the classifier to make "mistakes" with in some parameters called the slacks,this method maximize what called the "margin": it is twice the distances of the support vector from the separating hyper plane, and it solves , for more information you can use google or SVM
> 0 votes

---
Tags: reference-request, machine-learning, data-mining
---


# Question
Title: A Problem on Time Complexity of Algorithms
For every integer $t$, is there a problem whose solutions can be verified in $O(n^{s})$ time but cannot be found in $O(n^{st})$ time?

By verifying, I mean that given a candidate solution $y$, we can judge whether $y$ is correct or not in time $O(n^s)$.

# Answer
For $k = \left\lceil \dfrac{r}{2} \right\rceil$, it is conjectured (and proven in some simpler models of computation by JeffE) that $r$-SUM problem has lower bounds $\Omega(n^k)$, the solution for which can be verified in $O(n)$ time.

Pick an $r$ such that $k \gt t$, implying $\omega(n^t)$ bounds.
> 4 votes

# Answer
If I understood you correctly, it is okay if $s=t=1$. In this case take *sorting* in some comparison based model. You can verify a correct solution with $O(n)$ comparisons. On the other hand you need $\Omega(n \log n)\subsetneq \omega(n)$ comparisons to sort.
> 0 votes

---
Tags: complexity-theory, time-complexity, asymptotics, complexity-classes, lower-bounds
---


# Question
Title: Finding the lower bounds of an algorithm
I am struggling to calculate the lower bounds of an algorithm. What is the right way to proceed.

For eg, I have the following algorithm

```
For i=1, 2,...,n
    For j=i+1, i+2,...,n
        Add up array entries A[i] through A[j]
    Store the result in B[i, j] Endfor
Endfor

```

How do I calculate the lower bounds of this algorithm

# Answer
> 1 votes
Hint: The complexity is proportional to the number of reads from the array $A$.

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


# Question
Title: What's the vertex cover of the null graph?
Let $N(G)$ be the null graph. What's the number of vertex cover for this graph? I wanted to modify the reduction from SAT to vertex cover by adding vertices that are not connect to any vertices.

# Answer
> 5 votes
The minimum vertex cover for a totally disconnected graph is the empty set. A vertex cover is a set of vertices that covers all the edges, i.e. every edge in the graph needs at least one of its endpoints in the vertex cover, so if there are no edges in the graph, no edges need covering.

---
Tags: algorithms, approximation
---


# Question
Title: Solving a problem related to convolution
I have this confusion related to solving this problem

> You’ve been working with some physicists who need to study, as part of their experimental design, the interactions among large numbers of very small charged particles. Basically, their setup works as follows. They have an inert lattice structure, and they use this for placing charged particles at regular spacing along a straight line. Thus we can model their structure as consisting of the points $ \\{1, 2, 3, \cdots , n\\}$ on the real line; and at each of these points $j$, they have a particle with charge $q\_j$. (Each charge can be either positive or negative.)
>
> They want to study the total force on each particle, by measuring it and then comparing it to a computational prediction. This computational part is where they need your help. The total net force on particle $j$, by Coulomb’s Law, is equal to
>
> $F\_j = \sum\_{i\<j}\frac{Cq\_iq\_j}{(j-i)^2} - \sum\_{i\>j}\frac{Cq\_iq\_j}{(j-i)^2}$
>
> They’ve written the following simple program to compute $F\_j$ for all $j$:
>
> ```
> For j = 1, 2,...,n
>    Initialize Fj to 0
>    For i = 1, 2, ..., n
> ￼     If i < j then
>        Add Cqiqj/(j-i)^2 to Fj
>      Elseif i > j then
>        ￼Add −Cqiqj/(j−i)^2 to Fj
>      Endif
>    Endfor
>    Output Fj
> Endfor
>
> ```
>
> It’s not hard to analyze the running time of this program: each invocation of the inner loop, over i, takes $O(n)$ time, and this inner loop is invoked $O(n)$ times total, so the overall running time is $O(n^2)$.
>
> The trouble is, for the large values of $n$ they’re working with, the program takes several minutes to run. On the other hand, their experimental setup is optimized so that they can throw down $n$ particles, perform the measurements, and be ready to handle n more particles within a few seconds. So they’d really like it if there were a way to compute all the forces $F\_j$ much more quickly, so as to keep up with the rate of the experiment.
>
> Help them out by designing an algorithm that computes all the forces $F\_j$ in $O(n \log n)$ time.

I am sure that this problem is solved by convolution which takes time $O(n \log n)$. However, I am not being able to proceed and see how it's converted to a problem related to convolution. Any suggestions?

# Answer
> 1 votes
Hint: Consider the two sequences $q\_1,\ldots,q\_n$ and $\ldots,-1/9,-1/4,-1,0,1,1/4,1/9,\ldots$.

---
Tags: algorithms
---


# Question
Title: Rearrange a sequence of real numbers to satisfy polynomial inequalities
Assume we fix a degree $d$ polynomials $f$ of $k$ variables. (If it helps, let $t$ be the number of terms in $f$). Consider a list of real numbers $a\_1,\ldots,a\_n$, does there exist a permutation $\pi$, such that for all $i\leq n-k$ $$ f(a\_{\pi(i)},a\_{\pi(i+1)},\ldots,a\_{\pi(i+k-1)}) \geq 0$$

How hard is this problem?

# Answer
Let's assume that the numbers $a\_1,\ldots,a\_n$ are integers, so that the problem is in NP for any fixed $f$. We construct a polynomial $f$ so that the problem is NP-complete, by reduction from vertex cover in cubic graphs ($3$-regular graphs).

Let the instance of cubic vertex cover consist of a cubic graph $G=(V,E)$ and an integer $m$, and let $|V| = n$. Pick the first $n$ primes larger than $7$, $p\_1,\ldots,p\_n$. We construct the following sequence $\mathbf{a}$:

* For each edge $(i,j)$, the numbers $p\_i,p\_j,p\_{ij}$
* For each vertex $i$, the numbers $p\_i,p\_i^3$
* $m$ copies of $3$
* $n-m$ copies of $5$
* $9n/2$ copies of $2$
* $11$ copies of $7$

Note that some numbers appear more than once. The intended solution sequence consists of eleven copies of $7$ followed by $n$ segments of length $12$ of the following two forms: either $$ 5,p\_i,p\_i^3,2,2,2,2,2,2,2,2,2 $$ where $1 \leq i \leq n$, or $$ 3,p\_i,p\_i^3,x\_1,y\_1,z\_1,x\_2,y\_2,z\_2,x\_3,y\_3,z\_3 $$ where $1 \leq i \leq n$ and for $\alpha \in \\{1,2,3\\}$, $$ x\_\alpha,y\_\alpha,z\_\alpha = 2,2,2 \quad \text{or} \quad p\_i, p\_ip\_j, p\_j \text{ for some edge } (i,j).$$ A sequence of that form encodes a vertex cover given by the vertices appearing in the second position in segments of the second form. It should be clear that such a sequence exists if and only if a vertex cover exists. It remains to show how we can test that a sequence is of that form using a single polynomial $f$ which is "run" on *all* chunks of length $12$.

We let $f = -f'$, where the function $f'(u,v,w,x\_1,y\_1,z\_1,x\_2,y\_2,z\_2,x\_3,y\_3,z\_3)$ is a non-negative function which attains zero on exactly inputs of the following forms:

* $3 \in \\{v,w,x\_1,y\_1,z\_1,x\_2,y\_2,z\_2,x\_3,y\_3,z\_3\\}$
* $5 \in \\{v,w,x\_1,y\_1,z\_1,x\_2,y\_2,z\_2,x\_3,y\_3,z\_3\\}$
* $u = 5$, $w=v^3$ and $x\_1=y\_1=z\_1=x\_2=y\_2=z\_2=x\_3=y\_3=z\_3=2$
* $u = 3$, $w=v^3$ and for each $\alpha \in \\{1,2,3\\}$, either $x\_\alpha=y\_\alpha=z\_\alpha=2$ or $x\_\alpha=v$ and $y\_\alpha=x\_\alpha z\_\alpha$

This polynomial can be constructed using the following three rules:

* A condition $I = J$ is represented by $(I - J)^2$
* Given two non-negative polynomials for the conditions $C\_1,C\_2$, the condition $C\_1 \lor C\_2$ is represented by $C\_1 C\_2$
* Given two non-negative polynomials for the conditions $C\_1,C\_2$, the condition $C\_1 \land C\_2$ is represented by $C\_1 + C\_2$

Let $\mathbf{b}$ be any permutation of $\mathbf{a}$ for which your condition holds. Since $f'$ is non-negative, it must be that one of the above conditions holds for each segment of length $12$. In particular, any segment of length $12$ must contain $3$ or $5$ somewhere. Considering the number of these compared to the length of the sequence, we see that its general form is: eleven arbitrary elements followed by $n$ segments starting with $3$ or $5$. Each segment starting with $5$ is of the form $$ 5,q,q^3,2,2,2,2,2,2,2,2,2. $$ We conclude that $q = p\_i$ for some $1 \leq i \leq n$. Each segment starting with $3$ is of the form $$ 3,q,q^3,x\_1,y\_1,z\_1,x\_2,y\_2,z\_2,x\_3,y\_3,z\_3. $$ As before, $q = p\_i$ for some $1 \leq i \leq n$. Furthermore, for each $\alpha \in \\{1,2,3\\}$, either $x\_\alpha = y\_\alpha = z\_\alpha = 2$ or $x\_\alpha = p\_i$ and $y\_\alpha = p\_i z\_\alpha$. In the latter case we conclude that $z\_\alpha = p\_j$ and $y\_\alpha = p\_ip\_j$ for some edge $(i,j)$.

In both cases, none of the elements in the segments are equal to $7$, and we conclude that the first eleven elements in the sequence must be $7$. Let $S$ be the set of $i$ such that there is a segment of the form $3,p\_i,\ldots$. Since there are exactly $m$ copies of $3$, $|S| = m$. For every edge $(i,j)$, the number $p\_{ij}$ appears somewhere, and the only legal place is a $3$-segment. We conclude that $S$ is a vertex cover of length $m$.

This shows that if your condition holds then the graph has a vertex cover of size $m$. Conversely, if the graph has a vertex cover of size $m$ then we can construct a sequence satisfying your condition by assigning each edge to one of the vertices covering it. This proves the validity of the reduction. The reduction is also polynomial time (note that the primes $p\_1,\ldots,p\_n$ can be found using brute force), showing that your problem is NP-hard, and so NP-complete.
> 6 votes

---
Tags: complexity-theory, np-complete, permutations, polynomials, real-numbers
---


# Question
Title: Euclidean Steiner Tree Question in Approximation Algorithms
Given $n$ points in $\mathbf{R}^2$, define the optimal Euclidean Steiner tree to be a minimum (Euclidean) length tree containing all $n$ points and any other subset of points from $\mathbf{R}^2$. Prove that each of the additional points must have degree 3, with all three angles being $120^\circ$.

# Answer
**Hint 1:** If there is a vertex that violate this condition, say a degree 3 vertex, take this vertex out. Now there are three vertices that have lost an edge remaining. Construct the Euclidean ST for these three points and add it back. Obviously your new solution cant be worse than what you head before. Now it remains to check that for 3 arbitrary points in the plane, the Euclidean ST fulfills the angle criterion mentioned in your question.

**Hint 2:** For a higher degree $v$, replace two consecutive edges $(v,u\_1), (v,u\_2)$ by the Euclidean ST spanned between $v,u\_1,u\_2$.
> 2 votes

---
Tags: algorithms, algorithm-analysis, computational-geometry, approximation, trees
---


# Question
Title: How do I compute the luminance of a pixel?
I have a color (say $R=100, G=150, B=130$). How do I compute its intensity?

Do I just sum up all three components? Or are the colors not evenly weighted?

# Answer
The colors are not evenly interpreted by our eyes. When I want to make a picture gray scale, I usually go for the following calculation of the luminance of a pixel.

```
luminance = (r * 0.3) + (g * 0.59) + (b * 0.11)

```

Read more in the Stackoverflow question Formula to determine brightness of RGB color.
> 4 votes

---
Tags: graphics
---


# Question
Title: Finding largest value for $\frac{\phi(i)}{i}$ for $i \in (2, N)$
I need to find largest value for $\frac{\phi(i)}{i}$ for $i \in (2, N)$ where $N$ can be as large as $10^{18}$.

I tried this approach , but is too slow. Finding the just smallest prime number to $N$, as its $\frac{\phi(i)}{i}$ value is $\frac{i-1}{i}$, which is maximum in the range. (See Maximum of ϕ(i)i\frac{\phi(i)}i)

So, I was wondering if there is any other faster way to find the maximum value. More precisely I need the value of i where $\frac{\phi(i)}{i}$ is maximum.

# Answer
> 2 votes
Since you know that the maxium value is achieved when $i$ is the largest prime smaller than $N$, your problem is equivalent to finding the largest prime smaller than $N$.

There are many ways to test for primality, so presumably you could just take your favorite primality test and run a for loop from $N-1$ downwards, to find the first number which is prime.

Perhaps I do not understand what you are asking for.

---
Tags: algorithms, arithmetic, primes
---


# Question
Title: Compare two methods of random permutations
I want to compare in a practical sense two methods of random permutations -- one theoretically perfect, namely that of Fisher and Yates, and another ad hoc, let's call it X. A way of comparison I could think of is the following:

One starts from the standard configuration of n objects \[0, 1, 2, ...., n-1\] and apply each method a fairly large number of times successively to permute them and each time one computes the Hamming distance of the result from the standard configuaration. One obtains thus the frequency distribution of the Hamming distances for each method. If these are fairly comparable to each other, then X could be practically employed in place of the theoretically perfect one.

Is this line of thought of mine correct? Does anyone have an idea of a better method of comparison? Thanks in advance.

# Answer
Your method of comparison is very easy to defeat. I assume that by "Hamming distance from the regular configuration" you mean the number of fixed points. Make a table of the number of permutations in $S\_n$ having $k$ fixed points (this can be computed recursively), and fix a *single* permutation with $k$ fixed points for every $k$. This way you can sample a permutation in a ways that matches this particular statistic of random permutations, but probably performs rather differently compared to a truly random permutation.
> 1 votes

---
Tags: probability-theory
---


# Question
Title: Can the heaviest edge ever be in an MST?
Is it true that the heaviest edge in a directed graph can not be in the MST of that graph?

I don't think it is true because we might end up with a heaviest edge that is *not* part of a cycle.

Can anyone confirm?

# Answer
> 9 votes
No, it is not true. Consider a graph with 2 vertices and an edge between them. This is the heaviest edge, and it will be in the minimum spanning tree of $G$.

---
Tags: graphs, minimum-spanning-tree
---