# Question
Title: Advantage of MTZ problem formulation of TSP
In class, we saw the Miller-Tucker-Zemlin formulation of the Travelling Salesmen Problem (TSP). MTZ is a way of formulating the TSP as an integer linear programming instance.

I understand how MTZ works, but I'm confused why MTZ is considered a better algorithm for checking for sub-cycles and rejecting them as answers than just keeping a list of connected nodes.

I can imagine a look-up table of each node along with a corresponding boolean that defines whether a node is connected or not. Consequently, the running time of checking if a connection is valid would be O(1). If it isn't a run-time consideration, what is the reason that MTZ is preferred?

# Answer
> 3 votes
The MTZ is not an algorithm. Miller-Tucker-Zemlin formulation is a method of formulating the Travelling Salesman Problem as an instance of integer linear programming. This lets you feed the resulting integer linear programming instance into an off-the-shelf solver for integer linear programming, and let the solver solve it for you.

Remember that an instance of integer linear programming is a set of variables and linear inequalities. Lookup tables are not allowed; the inequalities have to be linear (e.g., $5x\_1 + x\_2 \le 7$, but not $T\[x\_1\] \le 5$). Therefore, using lookup tables are simply not an option, if you want to use integer linear programming.

Alternatively, you could skip using an integer linear programming solver at all, and try to solve the Travelling Salesman Problem from scratch. But good luck with that. It's an NP-complete problem, so it is unlikely you'll be able to find an efficient algorithm to solve the problem. (And just saying "use lookup tables" is not an algorithm.)

Bottom line: I think you have a confusion about how integer linear programming works, and what MTZ is. MTZ is not an algorithm for the TSP. Rather, MTZ is a way of describing the TSP in a format that you can give to an integer linear programming solver. Lookup tables aren't an option, if you're using an integer linear programming solver.

---
Tags: algorithms, linear-programming, traveling-salesman, integer-programming
---


# Question
Title: Why do we assume that a nondeterministic Turing machine decides a language in NP in $n^k-3$ in Sipser's proof
At page 277 of Sipser's *Introduction to the Theory of Computation*, a proof of the NP-completeness of SAT is given.

The following comment is made on the trace of some machine $N$ which can decide a language $A\in\mathrm{NP}$:

*"Next, we take any language $A$ in NP and show that $A$ is polynomial time reducible to SAT. Let $N$ be a nondeterministic Turing machine that decides $A$ in $n^k$ time for some constant $k$. (For convenience, we actually assume that $N$ runs in time $n^k-3$, but only those readers interested in details should worry about this minor point.)"* (p. 277)

Interestingly, Levin's paper, *Universal Search Problems*, which discusses the search version of computation (in contrast to the decision version) states:

"*Two function $f (n)$ and $g (n)$ will be said to be equal if there exists some $k$ such that: \begin{equation} f (n) \leq (g (n) +2)^k\ \textrm{and} \ g (n) \leq (f (n) +2) ^k. \end{equation} The term less than or equal is defined similarly.*" (p.1 of the paper)

Levin is sometimes co-cited with Cook for the proof of the NP-completeness of SAT (Cook-Levin theorem).

So what are those $2$ and $3$ constants? Are they even related or was it just an intuition? In conventional big-O notation, we would have said $\pm O(1)$. But here, both authors take the time to specify an exact constant, and both are discussing the notion of polynomial-time reduction.

# Answer
The tableau used in the proof has dimensions $n^k \times n^k$. The reason is that each row represents the contents of the tape, and the number of symbols on the tape cannot possibly be more than the runtime of the algorithm. However, in the proof, the first and last cell of each row is a # symbol, and each row also needs one cell to store the current state $q$ of the TM. Thus to be sure we are able to fit the entire contents of the tape and these 3 extra symbols in $n^k$ cells, we must say the runtime (and hence the space used on tape) is bounded by $n^k - 3$.
> 4 votes

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


# Question
Title: Name for almost random memory distribution on the heap
If I had a heap like the following: with blue blocks being occupied memory and white blocks being free memory

What is the general name given to the situation illustrated, where the free and occupied cells become distributed almost 'randomly'?

This is an exam question, I've tried searching online and through the provided slides but to no avail.

# Answer
This is fragmentation. See https://en.wikipedia.org/wiki/Fragmentation\_%28computing%29 for a definition. Fragmentation can happy on any kind of storage; most commonly it is discussed for persistent storage (e.g., in filesystems), but heap fragmentation can also happen, and that is what you are describing. See also https://en.wikipedia.org/wiki/Memory\_management (which discusses heap fragmentation).
> 1 votes

---
Tags: terminology, operating-systems, virtual-memory, memory-allocation
---


# Question
Title: Lower complexity bounds without mutation
Lower complexity bounds tend to be a very hard problem in general. Despite this, I was wondering if there are any theoretical results that relate lower complexity bounds for some class of problems in the case where mutation is allowed and in the case it's not allowed? In particular, what type of problems would be inherently harder to solve in a purely functional language on a RAM machine?

The following problem is why I started thinking about this: https://stackoverflow.com/questions/24105301/number-of-occurrences-in-list-of-each-element

# Answer
> 2 votes
See the section labelled "Negative result: you cannot avoid some slowdown, for some data structures" of https://cs.stackexchange.com/a/18266/755 for examples of problems whose solution in a functional language is inherently a bit slower than a solution in an imperative language with mutation. One example is an array data structure; with mutation, you can achieve $O(1)$ worst-case time for both mutation and lookup, but with a functional language (with persistent data structures), you cannot.

---
Tags: algorithms, complexity-theory, functional-programming
---


# Question
Title: Will floating point code return the same arithmetical results on two different computers?
Say I am using boost or the built-in float or double mathematical libraries of my C++ compiler.

I distribute the program.

Will the execution of my C++ program on different machines given different floating point results given that the FPU is CPU specific and AMD may not return exactly the same thing as Intel or ARM.

Should I use fixed-point algorithms to circumvent this possibility?

Would the answer be different if my program was written in something other than C++?

# Answer
> 6 votes
As long as you execute the same machine code on the different machines and as long as the settings for the floating point unit are identical, you will get identical results. However, you cannot execute the same machine code on both Intel and ARM, so this answer is only hypothetic. Even on different Intel processors you have to take special care that exactly the same machine code gets executed. Some third party libraries like Intel-MKL use different machine specific code on different processors, and other libraries like FFTW measure speed at runtime, and select different algorithms (and hence different code) based on the outcome of these measurements.

Sometimes the compiler is able to inline a certain function (for example your rounding logic), and then you can end up with different results for identical input to that function at different parts of your code. Another very real non-reproducability for distributed floating point computations are potential reductions are the end of the computation. Because the result here depends on the order of the reduction steps, it is very easy to end up with slightly non-repreducible results.

I have run into the issues in the past, but never considered this to be a reason to switch to fixed-point algorithms. For robustness problems of "computational geometry" related code on the other hand, I consider integer or fixed point arithmetic to be an appropriate solution.

> Should I use fixed-point algorithms to circumvent this possibility?

In conclusion, there are several issues related floating point numbers, and even some problems where floating point numbers are not the most appropriate solution, but in general floating point arithmetic is still the way to go. So no, you should not abandon floating arithmetic in general, but only in the specific cases where it causes unsurmountable robustness problems.

---
Tags: compilers, floating-point, numerical-analysis
---


title: Linked list implementation problem

text:
# Question
Title: Linked list implementation problem
Note its not a homework question, just practice Hi i have always seen linked list implementation in java using the following piece of code

```
class Node
     {
         int key;
         Node prev;
         Node next;
     }

```

I implemented linked list using single array which could be increased as per need. (Took code of increasing array from Effective Java book). Please tell me why the above method is preferred over my implementation. According to me it should occupy less memory. Rest i would really like to use an optimized code. And please forgive me if my question is trivial. I am new to algorithms.

```
public class LinkedListImplementation {

private int list[];
private int currentSize;

public LinkedListImplementation() {
    this.list = new int[20];
    currentSize = 0;

}

void printList() {
    if (currentSize == 0) {
        System.out.println("******************Empty List********************");
        return;
    }
    System.out.println("*************Printing list***************");
    for (int i = 0; i < currentSize; i++) {
        System.out.print(list[i] + " ");
    }
    System.out.println();
}

int head() {
    if (currentSize == 0) {
        System.out.println("******************Empty List********************");
        return -1;
    }
    return 0;
}

int next(int i) {
    if (i >= currentSize || i < 0) {
        System.out.println("*********************Invalid************************");
        return -1;
    } else if (i == (currentSize - 1)) {
        System.out.println("***********Reached the end of list***************");
        return -1;
    }
    return i + 1;
}

int previous(int i) {
    if (i >= currentSize || i < 0) {
        System.out.println("*********************Invalid************************");
        return -1;
    } else if (i == 0) {
        System.out.println("***********Reached the head of list***************");
        return -1;
    }
    return i - 1;
}

int listSearch(int k) {
    int x = head();
    while (x != -1 && list[x] != k) {
        x = next(x);
    }
    return x;
}

private void ensureCapacity() {

    if (list.length <= currentSize) {

        list = Arrays.copyOf(list, 2 * list.length + 1);
    }
}

void listInsertBack(int x) {
    currentSize++;
    ensureCapacity();

    list[currentSize - 1] = x;

}

void listInsertFront(int x) {
    currentSize++;
    ensureCapacity();
    int i = currentSize - 1;
    while (i != 0) {
        list[i] = list[i - 1];
        i--;

    }
    list[0] = x;

}

public static void main(String args[]) {
    LinkedListImplementation lli = new LinkedListImplementation();
    lli.printList();
    lli.listInsertBack(10);
    lli.printList();
    lli.listInsertFront(20);
    Random rand = new Random();
    int count = 0;
    while (count != 30) {
        lli.listInsertBack(rand.nextInt(50));
        count++;
    }

    lli.printList();
    Scanner scn=new Scanner(System.in);
    System.out.println("Enter the number to be searched\n");
    System.out.println(lli.listSearch(scn.nextInt()));
}

```

}

# Answer
> 2 votes
This should really be on StackOverflow, not Computer Science, but here's an answer anyway.

There are a few points. First of all, your code *is not a linked list*. You created an unbounded array, an array that grows dynamically (good implementations also shrink dynamically, but that is beyond the scope of this question). A linked list is *defined* (more or less) as in the first implementation: each node stores some data and points to the node after it (and sometimes behind it, in the case of a doubly-linked list). They are two different data structures.

Now, onto the question of efficiency. From your code, it seems you are interested in the operations `insertAtBack`, `insertAtFront`, and `search`. Both arrays and lists support search in $O(n)$ time, though arrays can support search in $O(\log n)$ if they are sorted, whereas linked lists cannot. Linked lists have $O(1)$ time `insertAtBack` and `insertAtFront` operations. While `insertAtBack` is $O(n)$ worst-case for unbounded arrays, it is actually amortized $O(1)$, so it's not that bad. However, `insertAtFront` is $O(n)$ under any measure of time complexity.

So, in short, a linked-list is what you want in this situation (though linked lists are rarely used on their own, and almost always used as a building block of other data structures).

As for your question of space, you're right in that the linked-list is less efficient, as it needs to store two pointers for every data entry. On the other hand, linked-lists have the advantage that each node can be stored in a separate location in memory, whereas arrays are stored in a contiguous block of memory, which can be bad if the array is really large.

---
Tags: algorithms, linked-lists, java
---


# Question
Title: Why doesn't $O(1)+O(2)+\cdots+O(n)$ have an interpretation?
In CLRS (on pages 49-50), what is the meaning of the following statement:

> $\Sigma\_{i=1}^{n} O(i)$ is only a single anonymous function (of $i$), but is not the same as $O(1)+O(2)+\cdots+O(n)$, which doesn't really have an interpretation."

# Answer
Since $1+2+\dots+n =O(n^2)$, it is tempting to suggest that $O(1)+O(2)+\dots+O(n) = O(n^2)$ ... but this is not in fact valid. The reason is that there might a different constant for each term in the sum.

## An example

Let me give an example. Consider the sums $S(1) = 1^2$, $S(2) = 1^2 + 2^2$, $S(3) = 1^2 + 2^2 + 3^2$, $S(4) = 1^2 + 2^2 + 3^2 + 4^2$, and so on. Note that $1^2 \in O(1)$, $2^2 \in O(2)$, $3^2 \in O(3)$, $4^2 \in O(4)$, and so on for each term in the sum. Therefore, it would be reasonable to write $S(j)=1^2 + \dots + j^2$ in the form $S(j) = O(1) + \dots + O(j)$. So can we conclude that $S(j) = O(j^2)$? Nope. In fact, $S(n) = n(n+1)(2n+1)/6$, so $S(n) = \Theta(n^3)$.

If that doesn't help, let's try the following more precise mathematical development:

## A formalization

Recall that the interpretation of, say, $O(n^2)$ is that it is a set of non-negative functions $f(n)$ (namely, the set of functions $f(n)$ such that there exists constants $c \ge 0, d\ge 0$ such that $f(n) \le c \cdot n^2$ for all $n\ge d$).

The closest we can come to an interpretation of $O(1) + O(2) + \dots + O(n)$ is that it is the set of functions of the form $f\_1(n) + f\_2(n) + \dots + f\_n(n)$ such that $f\_1(n) \in O(1)$, $f\_2(n) \in O(2)$, ..., $f\_n(n) \in O(n)$.

But now the constants for each $f\_i$ can be different. Thus, each $f\_i$ is a non-negative function $f\_i$ such that there exist constants $c\_i\ge 0,d\_i \ge 0$ with $f\_i(n) \le c\_i \cdot i$ for all $n \ge d\_i$.

Now, given this, what can we say about $g(n) = f\_1(n) + f\_2(n) + \dots + f\_n(n)$? Not much useful. We know that there exists a constant $d=\max(d\_1,d\_2,\dots,d\_n)$ such that $g(n) \le c\_1 \cdot 1 + c\_2 \cdot 2 + \dots + c\_n \cdot n$ for all $n\ge d$. Now what can we say about this sum? Well, the answer is that we can't say anything at all. It could be arbitrarily large. It is tempting to let $c=\max(c\_1,c\_2,\dots,c\_n)$ and say that $g(n) \le c \cdot (1+2+\dots+n) \le c \cdot n^2 = O(n^2)$... but this is not actually correct, since we need a single constant value of $c$ that works for all $n$, and the value $\max(c\_1,c\_2,\dots,c\_n)$ is a function of $n$, not a constant.

So there might not be any constant $c$ such that $g(n) \le c \cdot (1+2+\dots+n)$; there might not be any constant $c$ such that $g(n) \le c \cdot n^2$. There is no guarantee that $g(n) \in O(n^2)$.

## For more reading

See https://math.stackexchange.com/q/86076/14578 and Sums of Landau terms revisited for other questions that deal with this general issue.
> 12 votes

# Answer
The reason that CLRS's comment is confusing is that, technically, $\sum\_{i=1}^{n} O(i)$ is *defined* as $O(1) + O(2) + \ldots O(n)$. What is really happening is that CLRS is abusing notation for sake of simplicity:

* $O(1)$ represents a set of functions. It includes, for example, $f(n)=1$, $f(n)=1/n$, and $f(n)=n^{1/n}$.
* When you write $O(1) + O(2)$ you're technically adding two sets $O(1)$ and $O(2)$ with a sumset operation. When this is done with more than a constant number of terms, it can lead to unexpected behaviors, as D.W. clearly explains in another answer.

Instead, CLRS would thus like you to interpret $\sum\_{i=1}^n O(i)$ as $\sum\_{i=1}^n f(i)$ where the generic function $f(i) \in O(i)$. For example, they would write that $\sum\_{i=1}^n 3i-5$ is $\sum\_{i=1}^n O(i)$, or $O(n^2)$.
> 1 votes

---
Tags: asymptotics, landau-notation
---


# Question
Title: Shortest path from starting cell to all cells in the grid
I found an algorithm for finding the shortest path on grid between selected cell, to all cells on the grid, with $O(KN)$ where $K$ is the number of neighbor cells and $N$ is the number of cells.

How ever if that's true than it's better than A\*, Floyd–Warshall and many others. So I probably mistaking some thing. Can you point me what.

Here is a pseudo code for my algorithm, the idea is to calculate simultaneously to all the directions.

The algorithm starts with the call to filter method

```
class MapFilter
{
    declare cellsMap, array of numbers with two dimensions, that represent a grid
    declare stack, a stack of MapFilter
    declare count of type number
    read input to map, array of Cells with two dimensions, that represent a grid
    read input to x ,y those are coordinates of starting node

    function filter(){
        initialize cellsMap with empty grid, all values are 0
        set count = 1
        set cellsMap[x][y] = 1;
        execute();
        while(stack is not empty){
            read length of the stack to length
            iterate over i from 0 to length{
                remove first element from stack and store it in mapFilter, instance of MapFilter
                mapFilter.execute()
            }
        }
    }

    function execute()
    {
        populate(x + 1, y);
        populate(x - 1, y);
        populate(x, y + 1);
        populate(x, y - 1);
    }

    function populate(x, y)
    {
        // Testing if the x,y cell is blocked by some way
        if( not isInMapRange(x,y) or
            cellsMap[x][y] not empty or{
            return;
        }

        set cellsMap[x][y] to count;
        addTask(x,y);
    }

    function isInMapRange(x,y){
        return x < cellsMap.length &&
            x >= 0 &&
            y < cellsMap[0].length &&
            y >= 0;
    }

    function addTask(x, y)
    {
        initialize mapFilter;

        set mapFilter.map = this.map
        set mapFilter.cellsMap = this.cellsMap
        set mapFilter.count = this.count + 1
        set mapFilter.x = x
        set mapFilter.y = y
        add mapFilter to stack
    }
}

```

# Answer
> 2 votes
You have an unweighted, undirected graph with $N$ vertices, and where each vertex has degree $K$. Then the problem of computing shortest paths *can* be solved in $O(KN)$ time using simple breadth-first search.

Why is this faster than Floyd-Warshall etc.? Because Floyd-Warshall has to handle *weighted* graphs. In your case you have an *unweighted* graph: every edge has weight 1 (the length of a path is just the number of edges in it). There are faster algorithms for computing shortest paths in unweighted graphs than in weighted graphs; unsurprisingly, the problem is harder if you have a weighted graph. If you have an unweighted graph, you don't need the fancier algorithms, like Floyd-Warshall; breadth-first search is enough.

---
Tags: algorithms, search-algorithms, shortest-path, square-grid
---


# Question
Title: How fast can we identifiy almost-duplicates in a list of strings?
I'm having trouble figuring out the upper bound running time for this scenario:

**Input:**

* $N$ number of strings
* $M$ upper bound of string length
* $T$ threshold for edit distance (2 strings with a ***Damerau-Levenshtein edit distance*** lower than $T$ are considered "duplicate")

**Expected values**

$N \approx 1,000,000$

$M \approx 200$

$T \leq 2$

**The algorithm should do the following:**

For each string in the list, find any other items in that list that have an edit distance smaller than some threshold, and mark them as "duplicate" (e.g. add them to some other list that tracks duplicates)

I'm having trouble calculating the upper bound for the optimal solution

What is the most optimal upper bound for such an algorithm?

I guess first I need to understand what is the best algorithm for the edit distance itself (is it $O(M \cdot N)$?) then it's simply $N^2$ times that, right? so it is surely "slower" than $N^2$ but my question is how slower?

# Answer
## Comparing two strings

Algorithms for computing the Levenshtein edit distance between a pair of strings can be found in the Wikipedia page on the edit distance. As that page explains, the running time for computing the edit distance between two strings of length $M$ is $O(M^2)$ time and $O(M)$ space. If you only care about whether the edit distance is $\le T$ or $\>T$, then the running time can be reduced to $O(MT)$ time and $O(M)$ space.

Algorithms for computing the (full) Damerau-Levenshtein distance are linked to on the corresponding Wikipedia page. As Wikipedia explains, the (full) Damerau-Levenshtein distance can be computed in $O(M^2)$ time and $O(M^2)$ space; the algorithm is found in the Lowrance and Wagner paper cited there, or in Appendix A of the Bard paper cited there.

Wikipedia also shows how to compute what is known as restricted Damerau-Levenshtein edit distance; that is considerably easier than computing the full Damerau-Levenshtein distance, and the restricted Damerau-Levenshtein edit distance can be computed using a simple modification to the standard dynamic programming algorithm for the Levenshtein edit distance. The running time is $O(M^2)$, and it can be reduced to $O(MT)$ time if you only care about whether the distance is $\le T$ or $\>T$.

Wikipedia also claims that for spelling correction and typo detection in natural language, the restricted Damerau-Levenshtein edit distance rarely differs from the full Damerau-Levenshtein distance, so you might as well use the restricted distance as it is easier to understand and implement. I have no personal knowledge of this; just passing along what is claimed in Wikipedia.

I recommend reading Appendix A of the Bard paper cited at Wikipedia for further implementation details.

## Comparing all pairs: naive computation of pairwise distances

Therefore, the naive algorithm of computing the edit distance between each pair of strings will take $O(N^2 MT)$ time and $O(M)$ space.

However, for real-world problems of the sort you mentioned, this naive algorithm is typically not optimal. If $T$ is fairly small, there are much better algorithms; the best algorithm depends heavily on $T$. But since you haven't specified $T$ in your question, you haven't provided us enough information to suggest a specific algorithm.

## Comparing all pairs: better data structures

A related problem is: given the set of $N$ strings, compute a data structure that allows us to quickly find the closest one in the set to any given string (under edit distance as our measure of "closeness"). There is lots of theoretical work on this problem, e.g., using BK-trees, Levenshtein automata, and many other techniques. See especially Efficient map data structure supporting approximate lookup and https://cstheory.stackexchange.com/q/4165/5038 for an entry into the literature.

In your case, this might be overkill, though.

## The case where $T=1$: sorting

In the special case where $T=1$, there is a clean algorithm. In other words, we want to consider two strings $X,Y$ if their edit distance is $1$ (i.e., $X$ can be transformed into $Y$ with a single insertion, deletion, or substitution, transposition).

Notice that if $d(X,Y)=1$, then the single difference must appear in either the first half of the string or in the last half of the string. In other words, either the first half of $X$ matches the first half of $Y$ (they have a long matching prefix), or the second half of $X$ matches the second half of $Y$ (they have a long matching suffix).

This immediately suggests a nice two-stage algorithm:

1. Sort the entire list of strings. For each string $X$, enumerate all other strings $Y$ that agree with $Y$ in its first half and check whether any of them are at edit distance $1$ from $X$. This can be done through a linear scan of a short contiguous stretch of the sorted list, and the start and end of that stretch can be found quickly with binary search.
2. Next, reverse all the strings and do the same thing again.

(Note that you need to be a little bit careful about the definition of "half" above, to take into account that $X,Y$ might differ in their length. However these pesky details can be easily worked out with a little bit of care.)

The space requirement is $O(N)$. Sorting takes $O(N \lg N)$ time. If you're lucky and the strings are fairly random, then hopefully each string will have only a small number of other candidates that match in the first half or last half. If this is the case, the running time might be in the vicinity $O(N \lg N)$.

Does this generalize to $T\>1$? Maybe, but it gets messier.

One way to try to generalize is to split the string into $T+1$ equal-length segments, and note that if $d(X,Y)\le T$, then there must be some segment where they match. However, this runs into messy details because the length of $X$ might differ from the length of $Y$. Therefore, if $T\>1$, I don't recommend this approach.

Another way to try to generalize is to break each string down into different fields: say the street address, the city, the country, the postal code. Now if two addresses $X,Y$ have edit distance $\le 2$, then either (a) some field of $X$ is at edit distance $2$ from $Y$, and all other fields match exactly, or (b) there are two fields where they have edit distance $1$, and all other fields match exactly. You can find all matches of type (a) by, for each field, building a hashtable keyed on everything but that field; now any two strings that match will be mapped to the same hash bucket, so you just need to solve the problem separately for each bucket. You can also find all matches of type (b) similarly. This might be more promising, depending upon the structure of your problem.

## Pragmatics

In practice, there are some techniques that I suspect will probably be helpful. One is to try to use spell-correction on each field of the address first, and then use the spell-corrected addresses to look for duplicates (confirming them by reference to the original value).

Another possible heuristic might be to map each address to geographical coordinates on the sphere, and look for pairs of addresses that are locally very near each other. This won't detect typos in (say) the country or state, but it might be helpful in detecting typos in (say) street address, by reducing the set of pairwise comparisons you need to make.

## Other resources

You might also like to look into the literature on how to build fast spell checkers, as that is a closely related problem. Take a look at Peter Norvig's article on that problem: http://norvig.com/spell-correct.html
> 3 votes

# Answer
The answer depends on $N$, $M$, and $T$. For example, if $T=M$, then you can determine the answer in constant time (i.e. there is one string, all the rest are duplicates).

The standard dynamic programming solution to the edit-distance problem runs in roughly quadratic time. In theory you can get it down to linear if $T$ is very large; see Lipton's blog for a nice description of the computational complexity of the edit-distance problem.
> 1 votes

---
Tags: algorithms, algorithm-analysis, runtime-analysis, string-metrics, edit-distance
---


# Question
Title: Finding a 4-clique among $k$ node groups
Given a connected graph $G = (V,E)$, assume that there are partitions $\\{p\_0, p\_1, ..., p\_k\\}$.
Denote the partition set of a vertex $v \in V$ as $p(v)$.
The neighborhood of a vertex $v$ is denoted as $N(v)$

I need to find a 4-clique $V' = \\{v\_0, v\_1, v\_2, v\_3\\}$ such that the total degree of $V'$ is maximum and $\forall v\_i, v\_j \in V', p(v\_i) \neq p(v\_j)$.

Is this an NP-Hard problem?

The most straightforward method that comes to my mind is:

* pick $v \in V$ with maximum degree.
* pick vertex $w \in N(v)$ with maximum degree
* pick vertex $u \in N(w) \bigcap N(v)$ with maximum degree
* pick vertex $x \in N(u) \bigcap N(w) \bigcap N(v)$ with maximum degree

Is there any more efficient way to do this?

# Answer
> 3 votes
The naive algorithm takes $O(n^4)$ time, , where $n$ is the number of vertices in the graph, as Stephen Bly explains.

It is possible to determine whether a graph contains a $4$-clique in $O(n^{3.334})$ time. See https://cs.stackexchange.com/a/18331/755 for a reference to the algorithm. I suspect their techniques could be extended to solve your problem (e.g., by enumerating all such cliques, and then you could check whether any of them satisfy your partition requirement) in the same running time. However, a caution: the techniques may be somewhat theoretical. The asymptotics may mean that their algorithm only becomes faster than naive solutions for large values of $n$.

As a trivial optimization, you can initially delete all vertices whose degree is $\<3$, decompose your graph into connected components, and solve the problem separately on each connected component. You can also decompose into biconnected components and solve the problem separately on each biconnected component, since any clique will necessarily be contained in a single biconnected component. Taking this even further, we can delete a vertex $v$ if $\\{p(w) : w \in N(v), p(w) \ne p(v)\\}$ is of size 2 or smaller (since each vertex in any clique of the form you want will pass this check), then decompose into biconnected components, and enumerate all 4-cliques of each resulting component. This optimization might improve your running time in practice, even though it doesn't make any difference to the worst-case asymptotics.

# Answer
> 8 votes
First of all, the greedy strategy you outlined does not work. It may be possible that the node with highest degree is in a clique with lower total degree than the clique with the maximum degree.

Second, this problem is clearly in **P** because we can simply check all $\binom{n}{4} = O(n^4)$ cliques, checking they meet the partition requirement, and keeping track of the one with largest total degree. It's possible there's a more efficient algorithm though, especially considering this naive one does not use the partition information to rule out any cases.

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


title: Is there only one optimal BST?

text:
# Question
Title: Is there only one optimal BST?
as i read some material about Optimal BST, i ran into a trouble.

for following key i find two optimal BST with Average Cost = 30. 1 optimal BST using Dynamic programming Algorithm and 1 by hand !

key : 1/ 2/ 3 /4/ 5

frequencies: 10 / 8/ 6/ 4/ 2

i think always the Optimal BST using dynamic programming always has a unique solution. am i wrong ? or may be we have 2 or more optimal BST and all is correct.

# Answer
There can be multiple optimal BSTs. Consider keys/frequencies

$\qquad\displaystyle \Bigl(1,\frac{1}{4}\Bigr), \Bigl(2,\frac{1}{4}\Bigr), \Bigl(3,\frac{1}{4}\Bigr), \Bigl(4,\frac{1}{4}\Bigr)$;

all of the following trees have optimal average (weighted) search cost $2$:

<sup>\[Source\]</sup>
> 4 votes

# Answer
Raphael is right: it is certainly possible to have several optimal trees, especially when all frequencies are equal.

To return to your specific example, also here you have two optimal trees, as you yourself have observed. Considering the keys $3-5$ as right subtree of the root $2$ we have to following possibilities (where the figure indicates frequencies). The "weighted pathlength", the average number of steps to find a key in the tree (starting with 1 step for the root) equals $2\cdot6+1\cdot4+2\cdot2$ and $1\cdot6+2\cdot4+3\cdot2$, respectively. Both equal to $20$.

```
  4           6
 / \           \
6   2           4
                 \
                  2

```
> 1 votes

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


# Question
Title: Floating point operations; Exception, Flags, and Trap Handlers
I am reading over the article found here specifically §*D.4.4 Exceptions, Flags and Trap Handlers* and am confused by the table D-4 in that section.

Specifically the arguments sent to the trap handler for the overflow and and underflow exceptions.

It shows **round(x2-α)** as the argument for both the over and underflow conditions (EDIT: It is not). I am not sure what **x2** is at all, I see no reference to it in the section.

As for **α** footnote says:

> \*xis the exact result of the operation, α= 192 for single precision, 1536 for double, and xmax= 1.11 …11 ×2^e\_max.

So it says "**α** = 192 for single precision, 1536 for double" which is also confusing. Where do these values come from?

I am not looking for anything super in-depth, just something succinct.

# Answer
> 3 votes
Your problem is typographical. Look at a well-formatted copy and it should all make sense. So for example, the argument to the trap handler on overflow is $\hbox{round}(x 2^{-\alpha})$, where $x$ is the exact value.

The value of $\alpha$ comes from the fact that the exponent is 8 bits in binary32 (previously called "single") and 11 bits in binary64 (previously called "double"). You can think of $\alpha$ as an unsigned integer the size of the exponent field, with the two most significant bits set. Why it would be that number in particular is left as an exercise; think the possible range of an overflowing operation and what would be required to rescale it back into a representable range.

---
Tags: floating-point
---


# Question
Title: Asymptotics of the number of words in a regular language of given length
For a regular language $L$, let $c\_n(L)$ be the number of words in $L$ of length $n$. Using Jordan canonical form (applied to the unannotated transition matrix of some DFA for $L$), one can show that for large enough $n$, $$ c\_n(L) = \sum\_{i=1}^k P\_i(n) \lambda\_i^n, $$ where $P\_i$ are complex polynomials and $\lambda\_i$ are complex "eigenvalues". (For small $n$, we may have additional terms of the form $C\_k\[n=k\]$, where $\[n=k\]$ is $1$ if $n=k$ and $0$ otherwise. These correspond to Jordan blocks of size at least $k+1$ with eigenvalue $0$.)

This representation seems to imply that if $L$ is infinite then asymptotically, $c\_n(L) \sim C n^k \lambda^n$ for some $C,\lambda\>0$. However, this is patently false: for the language $L$ over $\\{0,1\\}$ of all words of even length, $c\_{2n}(L) = 2^{2n}$ but $c\_{2n+1}(L) = 0$. This suggests that for some $d$ and for all $a \in \\{0,\ldots,d-1\\}$, either $c\_{dm+a}(L) = 0$ for large enough $m$ or $c\_{dm+a} \sim C\_a (dm+a)^{k\_a} \lambda\_a^{dm+a}$. This is proved in Flajolet & Sedgewick (Theorem V.3), who attribute the proof to Berstel.

The proof provided by Flajolet and Sedgewick is somewhat technical; so technical, in fact, that they only sketch it. I attempted a more elementary proof using Perron-Frobenius theory. We can regard the transition graph of the DFA as a digraph. If the digraph is primitive then the result follows almost directly from the Perron-Frobenius theorem. If the digraph is irreducible but imprimitive with index $r$, then by considering the "$r$th power" of the DFA (each transition corresponds to $r$ symbols), we get the same result. The difficult case is when the digraph is reducible. We can reduce to the case of a path of strongly connected components, and then we get the result by estimating sums of the form $$ \sum\_{m\_1+\cdots+m\_k=m} \prod\_{i=1}^k \lambda\_i^{m\_i}. $$ (Each such sum corresponds to a particular way of accepting a word, going through the different components in a certain way.) This sum, in turn, can be estimated by pinpointing the largest term, which corresponds to $m\_i \propto \log \lambda\_i$. For every eigenvalue which is repeated $r$ times, we get an extra factor of $\Theta(m^{r-1})$.

The proof has its rough edges: in the reducible case, we need to pass from terms asymptotic to $C \lambda\_i^m$ to the sum mentioned above, and then we need to estimate the sum.

The proof by Flajolet and Sedgewick is perhaps simpler, but less elementary. Its starting point is the rational generating function of $c\_n(L)$, and it involves induction on the number of pole magnitudes (!). The basic idea is that all eigenvalues of maximal modulus are roots of unity (if normalized by their modulus), due to a (moderately easy) theorem of Berstel. Choosing an appropriate $d$ and looking at words of length $dm+a$, all these eigenvalues become real. Considering the partial fraction expansion, we get that if the eigenvalue of maximal modulus "survives", then it determines the asymptotics, which are of the form $Cn^k\lambda^n$. Otherwise, we find a new rational generating function which corresponds just to words of this length (using an Hadamard product), and repeat the argument. The aforementioned quantity keeps decreasing, and so eventually we find the desired asymptotics; $d$ might have to grow in the process, to reflect everything that happens in the inductive steps.

> Is there a simple and elementary proof for the asymptotic property of $c\_n(L)$?

# Answer
> 3 votes
The argument you have sketched appears to be in line with Richard Stanley's treatment of the Transfer-Matrix Method in *Enumerative Combinatorics, Volume 1* (link: pp 573; print: pp 500).

He starts with the generating function, and unpacks it by considering digraphs and permissible and prohibited factors. He then abstracts to free monoids, where he uses a refined version of the sums you gave to prove:

> **4.7.11 Proposition** Let $B$ be a subset of $A^\*$ that freely generates $B$. Then $B^\*(\lambda)=(I-B(\lambda))^{-1}$

After working through some applications, he likewise closes the section by discussing Hadamard products in relation to horizontally-convex polyominoes.

---
Tags: formal-languages, reference-request, regular-languages, asymptotics, combinatorics
---


# Question
Title: What does it mean for a function to be decidable? (homework)
**Note:** This is part of a homework exercise. I am asking for clarifications, not a solution!

**Given:** Assume $g: \mathbb{N} \mapsto \mathbb{N}, g\in R$ ($R$ is the class of recursive functions) is a strictly monotone function, i.e., $\forall n\in \mathbb{N}: g(n) \< g(n+1)$.

Prove that $g(\mathbb{N})$ is decidable.

**Clarification of the assignment:** I am not sure I understand the exercise correctly. What does it mean that a function is decidable? I assume that it's a decision problem of the form "For $x \in \mathbb{N}$, is $x\in range(g)$? For a function $g$ to be decidable, we can then define a decision procedure that returns $yes$ or $no$ for any $x$.

Is this correct? Or am I on the wrong track?

# Answer
They are not asking to prove that the function $g$ is decidable, but the *image* $g(\mathbb{N})$ is decidable. The image is a subset of $\mathbb{N}$, namely $$g(\mathbb{N}) = \\{ k \in \mathbb{N} \mid \exists n \in \mathbb{N} . g(n) = k \\}.$$ The question reduces to showing decidability of "given $k$, does there exist $n \in \mathbb{N}$ such that $g(n) = k$?".
> 3 votes

---
Tags: terminology, computability
---


title: A difficult master theorem problem

text:
# Question
Title: A difficult master theorem problem
Consider the function $B:\mathbb{N}\rightarrow\mathbb{R}$ defined by $$ B(n) = \begin{cases} 1 &\text{if $n\le 2$}\\ B\left(\left\lceil\frac{n}{\log\_2n}\right\rceil \right)+n&\text{if $n\ge 3$} \end{cases} $$

I'm having a lot of trouble with this question. I tried substituting things like $n=2^m$, but that didn't really help... My exam is tomorrow... Can someone help, please?

# Answer
We'll show that $B(n)=O(n)$ first and provide a hint about showing that $B(n)=\Omega(n)$. In both proofs, the $n/\lg n$ term is the problem, so we'll find suitable bounds for that. In both proofs, we'll suppress the ceilings around the argument.

$\mathbf{B(n)=O(n)}$:

We'll show inductively that $B(n)\le 2n$ for all $n\ge 512$. The base case is easy: $$ B(512)=935\le 1024=2\cdot512 $$ Now assume that $B(k)\le 2k$ for all $512\le k \< n$. Then we'll have $n/\lg n\le n/9$ and so $$\begin{align} B(n) &= 3B(n/\lg n)+n &\text{by definition}\\ &\le 3B(n/9)+n &\text{since $B$ is increasing}\\ &\le 3\cdot 2(n/9)+n &\text{by assumption}\\ &=\frac{2n}{3}+n\\ &=\frac{5n}{3}\<2n&\text{as required} \end{align}$$

$\mathbf{B(n)=\Omega(n)}$:

In a similar way, we can show that $B(n)\ge n$ for all $n\>2$, using the fact that $n/\lg n\ge 1$. This, along with the previous result establishes that $B(n)=\Theta(n)$.
> 0 votes

---
Tags: time-complexity, master-theorem
---


# Question
Title: if (dis)proving a conjecture on graph theory can be done just by a counter example then can every (dis)proof be mapped actually to a counter-example?
Suppose we have a conjecture on graph theory that can be (dis)proved by means of a counter example, then, is it true that every alternative (dis)proof of the conjecture can be mapped to a counter example?

This is in the general case, but for instance, can any proof that the hadwiger's conjecture is false be mapped to a counter example, i.e., a particular graph?

Or,

Can any proof about a purported property $P(L)$ of a language $L$, susceptible of being (dis)proved by a counter example, be mapped to a particular word, say $w$ meaning $w$ a counter example, i.e., $P(L):=FALSE\\;$ since $w$ exists?

# Answer
> 2 votes
Your question isn't entirely clear, but it seems you're asking if every false graph property has a counterexample. Obviously this is true: by definition there must be some graph for which the property doesn't hold. On the other hand, a proof that the property doesn't hold for all graphs may not necessarily give an example of such a graph; this is called a *non-constructive* proof.

# Answer
> 1 votes
To expand on Stephen's last remark, a classic non-constructive proof (though not about graphs) is the conjecture

> For every two irrational numbers $r, s$ the value of $r^s$ is irrational.

This is not true; a proof by contradiction looks like this:

Let $r=s=\sqrt2$. Then $r^s=\sqrt2^\sqrt2$ is either rational or not.

* If $\sqrt2^\sqrt2$ is rational, we have a counterexample to the conjecture.
* If, on the other hand, we have that $\sqrt2^\sqrt2$ is irrational, then $(\sqrt2^\sqrt2)^\sqrt2$ is an irrational number raised to an irrational power, but $(\sqrt2^\sqrt2)^\sqrt2=\sqrt2^2=2$ is rational, again contradicting the conjecture.

In other words, we've found two irrationals $r, s$ for which $r^s$ is rational, even though this proof doesn't tell us which two they are. (In fact, by the Gelfond/Schneider Theorem, $\sqrt2^\sqrt2$ is transcendental, hence irrational, but we didn't need that here.)

---
Tags: graphs, proof-techniques, undecidability
---


title: Bayesian Nets & Markov Blanket

text:
# Question
Title: Bayesian Nets & Markov Blanket
As i passed PHD entrance exam, some days ago, i want to find solutions for challenging problem.

In Bayes network on X={X1,...Xn} each random variable has P parents and Q child's. for Xi we want to find minimum number of variable that Xi independent from other variables. at least, how many variable we need?

i think, we use Markov Blanket for this problem. any solution for this problem?

Regards.

# Answer
> 3 votes
In a Bayesian network, a variable is independent from all the variables given its Markov blanket (except of course the variables in the Markov blanket).

However, the Markov blanket is not the minimal set that renders two variables independent.

Also note that a variable may be independent of some variables in the Markov blanket, given another set of variables (think about the case of a spouse in the network).

By the way, I think that this problem has been solved already (if you refer to the problem of identifying the minimal set that renders two variables independent).

Edit: Check this out: http://www.cs.iastate.edu/~jtian/r254\_min\_separator.pdf They show how to find a minimal d-separating set in a given Bayesian network.

---
Tags: machine-learning, artificial-intelligence, information-theory, hidden-markov-models, bayesian-statistics
---


# Question
Title: What is the complexity of depth first traversal that don't label nodes as discovered?
I've found an algorithm that acts like a depth first traversal that don't recognizes nodes that have been visited before.

```
  A
 / \
B   C
 \ /
  D
  |
  E

```

If run on this graph, the algorithm will traverse in this order:

`A, B, D, E, D, B, A, C, D, E`

Is there any way I can express the run-time complexity of this algorithm in terms of edges, nodes, or the depth of the graph? I expect it would be high, I have the feeling it will be exponential, but I'm struggling to explain why.

EDIT: The real algorithm that I am analyzing is computing the result of an expression tree, only it is not run at a tree, but at a DAG. This means, that nodes that have several parents get computed once for all parents.

Simple pseudo-code for the algorithm might be:

```
calculate(root){
    if(root.isLeaf){
        return root.value;
    } else {
        leftval = calculate(root.left);
        rightval = calculate(root.right);
        return root.operator(leftval, rightval);
    }
}

```

# Answer
For general DAGs, the runtime could indeed be exponential in the depth. Here's an example of a family of such graphs. Let $G\_d$ be a digraph comprised of a vertex stacked on a collection of 4-cycles as below, where I've illustrated $G\_3$:

In this figure, the edges are directed from top to bottom and every vertex has two children. The number of function calls your algorithm makes (and hence the run time) for a digraph $G\_d$ of depth $d$ will satisfy $T(0)=1, T(d)=2T(d-1)+1$, since every $G\_d$ is comprised of a root vertex at the top with two overlapping copies of $G\_{d-1}$ below it. This recurrence has solution $T(d) = 2^{d+1}-1$, exponential in the depth.
> 3 votes

---
Tags: algorithms, algorithm-analysis, runtime-analysis, search-algorithms, graph-traversal
---


# Question
Title: Existence of Efficient Set Difference Algorithm
As a foreword, I'm not asking *what* the algorithm is, just whether one can possibly exist (though, if it does already exist and someone knows what it is, that'd be great).

Basically, given two sets $S$ and $T$, I want to compute the two set differences $I = T \setminus S$ and $R = S \setminus T$. The goal is that if $S$ represents a "before" set, and $T$ an "after" set, I want to know what elements were inserted into (represented by $I$) and removed from (represented by $R$) the original set $S$ to get to $T$.

A naïve approach would be to compare every element of $S$ with every element of $T$, a worst-case runtime of $O(n * m)$, where $n = |S|$ and $m = |T|$.

An improvement would be to treat $S$ as a list and sort it, then do a binary search in the sorted list for every element in $T$. This would be worst-case (I believe) $O(n \log n + m \log n)$.

However, I think I can get it down to $O(n + m)$, and here's my thought process:

If $S$ is a list of $s\_i$ and $T$ a list of $t\_i$, we can define a "modification" bit for each element in each list.

If we define $$c\_i = \begin{cases} 1, & s\_i \in R \\ 0, & \text{else} \end{cases}$$ and $$d\_i = \begin{cases} 1, & t\_i \in I \\ 0, & \text{else} \end{cases}$$

and we define a "concatenation" sequence of the two: $$x\_i = \begin{cases} c\_i, & 0 \leq i \< n \\ d\_{i-n}, & n \leq i \< n+m \end{cases}$$

we can define a "modification" number: $$X = \sum\_{i=0}^{n+m-1} 2^i x\_i$$

We can then compute $R$ and $I$ by breaking down the "modification" number $X$ into $c\_i$ and $d\_i$, giving $$I = \\{ t\_i | d\_i = 1 \\}$$ and $$R = \\{ s\_i | c\_i = 1 \\}$$.

Now, since $c\_i$ and $d\_i$ rely on $R$ and $I$, we can redefine them based on how $R$ and $I$ are defined: $$(s\_i \in R) \iff (s\_i \in S \land s\_i \notin T)$$ $$(t\_i \in I) \iff (t\_i \in T \land t\_i \notin S)$$ So $c\_i$ and $d\_i$ are now: $$c\_i = \begin{cases} 1, & s\_i \in S \land s\_i \notin T \\ 0, & \text{else} \end{cases}$$ $$d\_i = \begin{cases} 1, & t\_i \in T \land t\_i \notin S \\ 0, & \text{else} \end{cases}$$

Therefore, the modification number $X$ only depends on the original sets/lists $S$ and $T$. Furthermore, since $X$ is composed of $n + m$ bits, any set difference algorithm should be able to compute these bits in $\Omega(n + m)$ time. It could then compute $S$ and $T$ as described above, which would take $O(n)$ and $O(m)$ time, respectively.

My primary concern is the assumption that computing $n + m$ bits should only take $\Omega(n + m)$ time - my reasoning for that is based on the proof of the lower bound of the general sorting algorithm, and how sorting a list is similar to computing $\log\_2 n!$ bits, which (from Sterling's Approximation) is $O(n \log n)$.

Again, I'm mostly interested in the validity of my reasoning, and whether or not this means a linear-time algorithm exists for computing set-differences.

---

An example application that I'm currently interested in (and what originally inspired this) is when a SCSI host rescans its bus for changes in device topology. Typically, it has a list of custom device objects that represent the corresponding device's current state. Upon rescan, the host gets a list of devices currently on the bus, but only by a small identifier (such as it's bus location or LUN).

The problem, then, is how to efficiently map this new device list to the existing device object list, so that unchanged devices are mapped to their corresponding objects, and any device objects whose corresponding devices have been removed can be cleaned up, and any new devices can have objects allocated for them.

If I let $S$ be the list of current devices (by their ID, with some other simple mapping from the ID to the object data), and $T$ be the results of the rescan, then I can efficiently compute $I$ and $R$, and allocate new objects for devices in $I$ and clean up objects for devices in $R$ in linear ($O(n + m)$) time.

# Answer
You can compute $S\setminus T$ and $T\setminus S$ from $S$ and $T$ in $O(n+m)$ time using a hash table. Put all of list $S$ into a hashtable, and then iterate through list $T$ and look it up in the hashtable. Then do the same, with $T$ in the hashtable and iterating through $S$.

Fine print for complexity purists: this is *expected* running time, making suitable assumptions about the hash function. However, the probability that the running time takes longer than $c \cdot (n+m)$ can be made exponentially small in $c$ with a suitable choice of hash function. For practical purposes, you typically don't need to worry about this.

You can also do it in $O(n \lg n + m \lg m)$ time, using a suitable sorting algorithm plus a standard merge algorithm. In some special circumstances, sorting might be even faster (look up counting sort and radix sort).

Which of these is faster in practice will depend upon the platform you run it on. You probably will need to implement and try both, to see which will be faster. You can't trust the asymptotic complexity in this situation, as caching effects and other implementation considerations have the potential to be more important than the asymptotics.
> 5 votes

# Answer
The nature of the answer depends on what you are attempting to optimize (e.g. computation, communication, interactivity) and the computational model (e.g. deterministic, probabilistic,distributed/centralized).

In the case where the two sets are on remote devices, this problem is known as the *set reconciliation* problem, or more generally the data reconciliation/synchronization problem.

In your application, it appears that you are just interested in computational complexity on a local host. In this case, as Karolis suggested, you can use a linear-time search algorithm (counting sort or radix sort) to get your desired complexity.
> 2 votes

---
Tags: algorithms, sets, check-my-answer
---


# Question
Title: Which one of these two sequences is random, and which one is not?
We let $\alpha = \alpha\_1\alpha\_2\alpha\_3\ldots$ be an infinite random sequence (under the uniform measure) where $\alpha\_i$ may be $1$ or $0$, and then define the boolean function $B\_k$:

$$ B\_k(\alpha\_1\ldots\alpha\_k) = \begin{cases} 1 \text{ if at least } \lceil k/2 \rceil \text{ of its inputs are } 1 \\ 0 \text{ otherwise} \end{cases} $$

Then we define two sequences:

$$B\_3(\alpha\_1\alpha\_2\alpha\_3)B\_3(\alpha\_4\alpha\_5\alpha\_6)B\_3(\alpha\_7\alpha\_8\alpha\_9)\ldots$$ $$B\_4(\alpha\_1\alpha\_2\alpha\_3\alpha\_4)B\_4(\alpha\_5\alpha\_6\alpha\_7\alpha\_8)B\_4(\alpha\_9\alpha\_{10}\alpha\_{11}\alpha\_{12})\ldots$$

Which one of these two sequences is (algorithmically) random, and why? I should note that apparently there is an obvious measure-theoretic fact that gives away which one is not random.

# Answer
> 3 votes
The second sequence is not random. Let $\alpha\_1,\alpha\_2,\alpha\_3,\alpha\_4$ be random, iid Bernoulli $1/2$ random variables. Let $\beta = B\_4(\alpha\_1 \alpha\_2 \alpha\_3 \alpha\_4)$.

What is the distribution of the random variable $\beta$? Answer: $\beta=1$ if at least two of the $\alpha$'s are $1$, so $\Pr\[\beta=1\] = 11/16$.

In other words, $\beta$ is biased towards $1$. It follows that the second sequence is not algorithmically random: it is a set of independent Bernoulli random variables with $p=11/16$, i.e., the outcome of an infinite sequence of tosses of a biased coin.

---
Tags: probability-theory, randomness
---


# Question
Title: Checking whether two paths are intersecting in a tree
The problem I have is given a Tree graph , and two paths from u1 to v1 and u2 to v2 where u1,u2,v1,v2 are vertices of the Tree . How efficiently can we check that whether they are vertex disjoint paths or not ? The solution I thought was that the LCA of (u1 and v1) should be the ancestor of u2 or v2 or vice versa . But this is a wrong solution since it does not always work out correctly .

# Answer
> 5 votes
This is a standard exercise. Try drawing some pictures with the different cases, and you'll see how to formulate a criterion for when they overlap, in terms of the lowest common ancestor.

Just computing $LCA(u\_1,v\_1)$ isn't gonna be enough, because that only gives you information about the first path, and doesn't depend at all on the second path. So try computing the LCA of some other pair of nodes.

Since this looks like an exercise, I'm not going to solve your problem for you, but I'll describe for you how you can approach this problem so you can solve it yourself.

1. Every path falls into one of two categories: either it goes down (i.e., $v\_1$ is a descendant of $u\_1$); or it goes up and then down (i.e., $u\_1$ and $v\_1$ are descendants of some common ancestor, $w\_1 = LCA(u\_1,v\_1)$, where $w\_1 \ne u\_1$ and $w\_1 \ne v\_1$). So, there are two possibilities for the first path, and two possibilities for the second path: four cases in all.
2. You can quickly classify each path, put it into these categories, and find the endpoints and the common ancestor. (Exercise for you: How?)

Now, you have four cases. For each case, draw some pictures and work out the criteria under which the two paths intersect. It's straightforward.

For instance, let's take the first of the four cases. Suppose both paths go only down: $u\_1$ is an ancestor of $v\_1$, and $u\_2$ is an ancestor of $v\_2$. Can you figure out how to tell whether they overlap? Some tips: If $LCA(u\_1,u\_2)=u\_1$, what can you conclude? If $LCA(u\_1,u\_2)=u\_2$, what can you conclude? If $LCA(u\_1,u\_2)$ is something else, then what can you conclude?

Now do similar reasoning for each of the four cases.

Note: I am also assuming that you have a rooted tree; otherwise, the problem is not well-defined (as the LCA is not defined in non-rooted trees).

My thanks to @babou for his helpful comments and feedback on an earlier version of this answer.

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


title: If P != NP, then 3-SAT is not in P

text:
# Question
Title: If P != NP, then 3-SAT is not in P
I hope I'm in the right section:

I know that if P = NP, then 3-SAT can be solved in P (Cook), but is the opposite valid, too? If P != NP, then 3-SAT is not in P?

Thanks!

# Answer
The opposite is valid.

$3SAT$ is an $NP$-complete problem, so every problem in $NP$ can be reduced to $3SAT$.

If $P \neq NP$ and $3SAT \in P$, every problem in $NP$ would be in $P$, contradicting $P \neq NP$. So if $P \neq NP$ then $3SAT \notin P$.
> 5 votes

# Answer
Mike's proof is correct. I just wanted to add some other details.

Cook's theorem (or Cook-Levin theorem) says that there exists a polynomial time reduction from all problems in $NP$ to $SAT$ (3-$SAT$ or k-$SAT$ with $k\>2$ since 2-$SAT$ is in $P$).

More specifically, it states that 3-$SAT$ is $NP$-complete.

Here is the definition that Sipser gives in his *Introduction to the Theory of Computation* (p. 276) of NP-completeness:

```
A language B is NP-complete if it satisfies two conditions:
1. B is in NP, and
2. every A in NP is polynomial time reducible to B

```

If $P\neq NP$, then it means that there is at least one language in $P$ that is not in $NP$. Assume 3-$SAT\in P$ (to get a proof by contradiction), the Cook-Levin theorem says that such a language (in $P$ but not in $NP$) cannot be in $NP$ without being polynomial-time reducible to $NP$-complete. This leads to a contradiction from the definition of $NP$-complete. Therefore if $P\neq NP$, 3-$SAT$ is not in $P$.

You can draw Venn diagrams for this...

Furthermore, you can note that the Berman-Hartmanis conjecture states that if one-way functions exist, then there is a language in $NP$ that cannot be polynomially reduced to $NP$-complete.
> 2 votes

---
Tags: complexity-theory, p-vs-np, 3-sat
---


title: Unary in $P$, binary not in $P$

text:
# Question
Title: Unary in $P$, binary not in $P$
I would like to know if there is a known decision problem with the following characteristics:

* Represented in unary, the problem is decidable in polynomial time.
* Represented in binary, the problem is not decidable in polynomial time (and this fact has been proved, not just conjectured).

For example, Subset-Sum is in $P$ when represented in unary, but it is $NP$-complete in binary. However, this problem does not satisfy my second requirement because we do not know whether $P=NP$.

# Answer
Every single-exponential (i.e. known to be solvable in $O(c^n)$ for some constant $c$) EXPTIME-complete problem will answer your requirements.

For example, see checking thorough rerefinement on finite modal transition systems.
> 7 votes

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


# Question
Title: How to reduce the cost of search based on previous BFS?
I got an unweighted, undirected graph, with $N$ vertices, where each vertex has degree $K$. In my case its a grid with dynamic obstacles.

My goal is to output a map, based on given location on the grid, with the shortest path to all the cells on the grid, some thing like this:

```
4 3 2 3
3 2 1 2
4 x x 3
5 6 5 4

```

> The starting position is at node with the weight of 1. X represent the obstacles.

I achieve this goal using Breadth-first-search. My question is how can I reduce the cost of the next search if:
Only my location on the grid is changed, and/or,
if only the location of the obstacles is changes and/or
if both my location and the location of the obstacles is changed.

As for now I perform full recalculation in all those cases.

# Answer
> 1 votes
You have two very different situations in the next search condition. If the graph is set up to represent a grid, then the obstacles are simply removed edges to the vertex where the obstacle is, by moving obstacles you have changed the graph, so any new problem is a search on a new graph and the old results are meaningless. For any two verticies, to see if the new obstacles block the old path is easy, however to see if replacing the edges from the old graph will shorten the path requires you to redo path finding. So in the case of the obstacles changing any algorithm would involve much more work then just redoing the BFS, which is quite simple. As for a changed user position you could sacrifice initial cost and search for all other searches upfront, depending on how many times you want to call the algorithm this may or may not pay off, this case is very situation dependent.

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


# Question
Title: Is the Berman-Hartmanis Conjecture Solved?
The Berman-Hartmanis conjecture more or less states that if one-way functions exist, there are some problems in $NP$ which cannot be polynomially reduced to $NP$-complete (cf. Ker-I Ko, A Note on One-Way Functions and Polynomial-Time Isomorphism).

Since the Cook-Levin theorem states that $NP$ is polynomial-time reducible to $NP$-complete.

Does the Berman-Hartmanis conjecture state anything about the converse statement? I.e. if $NP$ is polynomial-time isomorphic to $NP$, then one-way functions do not exist?

It seems to me that proving the converse and proving the non-existence of one-way functions proves the $P=NP$ problem.

Furthemore, is the Berman-Hartmanis conjecture solved?

# Answer
> 2 votes
The conjecture remains open. Also there is a proof that shows that if the conjecture is true, then P=/=NP. To my knowledge no one has proven the opposite, that if the converse is true then P=NP, to be true.

---
Tags: complexity-theory, reference-request, np-complete, one-way-functions
---


# Question
Title: Can a transcendental number like $e$ or $\pi$ be compressed as not algorithmically random?
The related and interesting fields of Information Theory, Turing Computability, Kolmogorov Complexity and Algorithmic Information Theory, give definitions of algorithmically random numbers.

> An **algorithmically random number** is a number (in some encoding, usually binary) for which the shortest program (e.g using a Turing Machine) to generate the number, has the same length (number of *bits*) as the number itself.

In this sense numbers like $\sqrt{e}$ or $\pi$ are **not** random since well known (mathematical) relations exist which in effect function as algorithms for these numbers.

However, especially for $e$ and $\pi$ (which are *transcendental* numbers) it is known that they are *defined* by infinite power series.

For example $e = \sum\_{n=0}^\infty \frac{1}{n!}$

So even though a number, which is the binary representation of $\sqrt{e}$, is not alg. random, a program would (still?) need the description of the (infinite) bits of the (transcendental) number $e$ itself.

Can transcendental numbers (really) be compressed?

Where is this argument wrong?

UPDATE:

Also note the fact that for *almost all* transcendental numbers, and irrational numbers in general, the frequency of digits is uniform (much like a random sequence). So its Shannon entropy should be equal to a random string, however the Kolmogorov Complexity, which is related to Shannon Entropy, would be different (as not alg. random)

Thank you

# Answer
> 6 votes
The problem is in your poor definition of "algorithmically random number" as applied to irrational numbers. In particular:

> has the same length (number of bits) as the number itself.

has no meaning if the number is of unbounded length.

Your Wikipedia link gives better definitions, which don't have this problem. For example (and paraphrasing formatting):

> **Kolmogorov complexity** \[...\] can be thought of as a lower bound on the algorithmic compressibility of a finite sequence (of characters or binary digits). It assigns to each such sequence $w$ a natural number $K(w)$ that, intuitively, measures the minimum length of a computer program (written in some fixed programming language) that takes no input and will output $w$ when run. Given a natural number $c$ and a sequence $w$, we say that $w$ is $c$-incompressible if $K(w) \geq |w| - c$.
>
> **An infinite sequence $S$ is Martin-Löf random if and only if there is a constant $c$ such that all of $S$'s finite prefixes are $c$-incompressible.**

This is a test passed by $\sqrt{e}$ by setting $c$ a bit larger than the program to generate $\sqrt{e}$ and including in it the length to generate.

# Answer
> 4 votes
Surprisingly, the Kolmogorov complexity of some arbitrary number is known to be uncomputable. So the general form of your question, is an arbitrary number algorithmically compressible is undecidable (i.e. the problem of computing the algorithmic complexity of a sequence). This can be proven by reduction to the Halting problem.

Problems that are known to be related to "computable analysis" (the theory of computable reals) (cf. K. Weihrauch, *Computable Analysis - An Introduction*) are the following:

1. To effectively enumerate all digits of a real number, one needs an infinite time Turing machine
2. Distinguishing two Turing machines that compute two reals is uncomputable (i.e. the machine equivalence problem is undecidable)

A consequence of 1 and 2 is that the equality operator on Turing machines is not defined (at least in terms of a Choice Axiom).

In terms of undecidability, we are typically referring to Omega-like numbers (cf. Chatin's constant for which C. Calude et al. surprisingly provided "a" computation - Exact approximations of omega numbers).

Now, $e$ and $\pi$ are computable reals. The Borwein-Bailey-Plouffe formula can even compute the $n$-th digit of $\pi$.

Computability, compressibility and decidability theories refer to metamathematics. Compressibility refers to the program description of a sequence.

So for your example, $e$ would be described by 9 symbols ($\sum$,$n$,$=$,$0$,$\infty$,$\ldots$). We are assuming that the program is defined on some Universal Turing Machine, in this case, say, a symbolic algebra system. So in this case, $9 + O(1)$ symbols since the Universal Turing Machine is considered to be $O(1)$.

The problem of enumerating all digits of $e$ is a problem distinct from the problem of representing $e$ algorithmically.

Furthermore, in computer science, we only have pseudo-randomness since any random number generator that is fully described by an algorithm is by definition pseudo-random (in contrast to a hardware random number generator).

# Answer
> 1 votes
Your statement

> Also note the fact that for transcendental numbers, and irrational numbers in general, the frequency of digits is uniform

is wrong. Look at Liouville's number. It is a transcendental number, containing almost all zeros, with a sparse amount of ones added (the nth 1 is at the n! decimal position). The distribution of digits to this number is completely one sided containing only 2 different digits, and one with a dominating frequency.

---
Tags: turing-machines, information-theory, randomness, kolmogorov-complexity, descriptive-complexity
---


# Question
Title: What is wrong with this seeming contradiction with a paper about AND-compression of SAT?
Got a simple construction seemingly contradicting a paper assuming plausible conjecture.

Since it is unlikely the conjecture to be false, what is wrong with the argument?

From a paper

> An AND-compression is a deterministic polynomial-time algorithm that maps a set of SAT-instances $x\_1,\dots,x\_t$ to a single SAT-instance $y$ of size $\text{poly}(\max\_i |x\_i|)$ such that $y$ is satisfiable if and only if all $x\_i$ are satisfiable. ... Unless the unlikely complexity-theoretic collapse $\sf coNP \subseteq NP/poly$ occurs, there is no AND-compression for SAT.

Construction:

If $x\_i$ are not in CNF, convert them to CNF possibly adding new variables. This is polynomial.

In CNF one can encode AND gate $ C := A \land B $ and OR gate $ C := A \lor B $.

The AND and OR gates have the property that for all satisfying assignments of their CNFs we have $C \iff (A \land B)$ and $C \iff (A \lor B)$.

Let the $j$-th clause in $x\_i$ be $x\_{i,j} = \[y\_1, \ldots, y\_k\]$ for literals $y\_m$.

Using the OR gate and new variables, compute variable $O\_{i,j} := y\_1 \lor y\_2 \cdots \lor y\_k$.

For all clauses in $x\_i$ ($O\_{i,j}$) and the AND gate compute variable $V\_i := O\_{i,1} \land O\_{i,2} \land \cdots \land O\_{i,m}$.

By construction $x\_i \iff V\_i$.

For all $V\_i$, using the AND gate compute $F := V\_1 \land \cdots \land V\_t$.

$F \iff x\_1 \land \cdots \land x\_t$.

So the final formula $y$ is the union of the CNFs for $O\_{i,j}$,$V\_i$,$F$, and a unit clause $\[F\]$.

$|y|$ is linear in the number of all literals, $t$ is polynomial in $\max |x\_i|$, which makes $|y|$ polynomial in $\max |x\_i|$.

This appears to contradict the claim in the paper, unless the certain collapse happens.

> What is wrong with this argument that appears to contradict the claim in the paper?

Similar construction works for OR-compression, when at least one $x\_i$ must be satisfiable.

The newly introduced variable are uniquely determined by the original variables.

```
OR gate in  CNF 3 := 1 \/ 2 : [[1 2 -3],[-1 3],[-2 3]]
AND gate in CNF 3 := 1 /\ 2 : [[-1 -2 3],[1 -3],[2 -3]]

```

# Answer
> 12 votes
The confusion arises from a misunderstanding of what being polynomial in the size of the largest instance means. It does not mean that polynomial growth of the compressor's output is allowed as the number of instances ($t$) increases. Rather it means the compressor's output is allowed to grow only as the maximum instance size grows, *independent of $t$*, and then only within a fixed polynomial of that value.

Your compressor concatenates the CNF instances, converts them to circuits, and then converts the circuits back to CNF. Its output grows linearly with the number of instances ($t$) independent of the instance sizes and is therefore bound to exceed any polynomial function of the maximum instance size. Because of this, indeed because it does not do any compression at all, your compressor does not cause any hierarchy collapse.

There also seems to be a misunderstanding as to what the AND-compressor function is supposed to do. It does not have to output an instance that preserves all satisfying assignments for all the input instances, nor does there need to be a parsimonious counting reduction from the input instances to the output instance. A conforming implementation could at the extreme output an empty instance if all the input instances are satisfiable and a single empty clause otherwise.

A more plausible AND-compressor might adapt standard data compression techniques such as the use of a dictionary. A table of unsatisfiable subformulas could be precomputed and used to search against the input SAT instances. A match would imply a forbidden variable assignment, which when instantiated as a learned clause might subsume (eliminate) several other clauses.

Another technique involves taking advantage the different sizes of the input instances. If the input instances are of different sizes, the larger instances could be searched for subformulas equivalent to one of the smaller instances. Such a match implies the existence of a variable assignment that could produce the subformula, and therefore the larger instance is satisfiable if the smaller instance is satisfiable. If the smaller instance is unsatisfiable, the larger instance might still be satisfiable but it doesn't matter because compressor output should still produce an unsatisfiable formula. So the output instance is effectively decoupled from the satisfiability of the larger instance and thus the larger instance no longer has to be represented in the output at all, eliminating a large number of clauses.

There are many other techniques. The theorem in the paper suggests that efficiently achieving high levels of compression is unlikely given the implied partial collapse of the polynomial hierarchy.

# Answer
> 5 votes
Re Edit 3:
$\langle F\hspace{-0.02 in},\hspace{-0.03 in}T\hspace{.02 in}\rangle\\:$ is a satisfying assignment for the instance "$\left(\lnot \hspace{.03 in}x\_{\hspace{.02 in}0}\right) \land x\_1\hspace{-0.04 in}$".
$\langle T\hspace{-0.02 in},\hspace{-0.03 in}F\hspace{.03 in}\rangle\\:$ is a satisfying assignment for the instance "$x\_{\hspace{.02 in}0} \land \lnot \hspace{.02 in}x\_1\hspace{-0.04 in}$".
The instances "$\left(\lnot \hspace{.03 in}x\_{\hspace{.02 in}0}\right) \land x\_1\hspace{-0.04 in}$" and "$x\_{\hspace{.02 in}0} \land \lnot \hspace{.02 in}x\_1\hspace{-0.04 in}$" are both satisfiable.
The instance "$\left(\lnot \hspace{.03 in}x\_{\hspace{.02 in}0}\right) \land x\_1\hspace{-0.04 in}$" is satisfiable *iff* the instance "$x\_{\hspace{.02 in}0} \land \lnot \hspace{.02 in}x\_1\hspace{-0.04 in}$" is satisfiable.
$\langle F\hspace{-0.02 in},\hspace{-0.03 in}T\hspace{.02 in}\rangle\\:$ is *not* a satisfying assignment for the instance "$x\_{\hspace{.02 in}0} \land \lnot \hspace{.02 in}x\_1\hspace{-0.04 in}$".
$\langle F\hspace{-0.02 in},\hspace{-0.03 in}T\hspace{.02 in}\rangle\\:$ is a satisfying assignment for the instance "$\left(\lnot \hspace{.03 in}x\_{\hspace{.02 in}0}\right) \land x\_1\hspace{-0.04 in}$" but not for the instance "$x\_{\hspace{.02 in}0} \land \lnot \hspace{.02 in}x\_1\hspace{-0.04 in}$".
Thus the transformation from the instance "$\left(\lnot \hspace{.03 in}x\_{\hspace{.02 in}0}\right) \land x\_1\hspace{-0.04 in}$" to the instance
"$x\_{\hspace{.02 in}0} \land \lnot \hspace{.02 in}x\_1\hspace{-0.04 in}$" does not preserve all satisfying assignments of the input instance,
but is such that "$\left(\lnot \hspace{.03 in}x\_{\hspace{.02 in}0}\right) \land x\_1\hspace{-0.04 in}$" is satisfiable *iff* "$x\_{\hspace{.02 in}0} \land \lnot \hspace{.02 in}x\_1\hspace{-0.04 in}$" is satisfiable.

Here is a not-necessarily-efficient version of an AND-compression algorithm for SAT:
Determine whether or not all of the input SAT-instances are satisfiable. $\\:$ If they all are,
then output the single SAT-instance "$\hspace{-0.02 in}x\_{\hspace{.02 in}0}\hspace{-0.04 in}$", else output the single SAT-instance "$\hspace{-0.02 in}x\_{\hspace{.02 in}0} \land \lnot x\_{\hspace{.02 in}0}\hspace{-0.03 in}$".

# Answer
> 3 votes
The last things that used to confuse me were the bounds on $t$ and the exact definition of polynomial.

The paper "Infeasibility of instance compression and succinct PCPs for NP" helped a lot.

It is about OR-compression, but works.

In the notation of the original paper $t=m$ and $\max |x\_i|=n$.

The paper explains:

> "$n$ possibly can be much less than $m$
>
> (the algorithm) runs in time polynomial in $m$ and $n$

---
Tags: logic, satisfiability
---


# Question
Title: Why is automatically labeling data in unsupervised learning hard?
I currently studying machine learning and pattern recognition area. Today, my professor said implementing an unsupervised system that automatically labels data is difficult. Why is that?

I think if I am given a data set, then I can categorize all data into groups. Then, for unknown input data, I can extract features and put it into the group that best fits all the features. Can anyone explain whats wrong with my intuition and why is it difficult problem?

# Answer
The problem with your intuition is that, frankly, you don't have one. At least not a useful, that is algorithmic one, one that tells you what is hard for computers and what is not. You think in terms of what *you* can do with *every-day* data -- but that's not an appropriate frame of reference for this problem. As evidence, consider this question.

Some specific concerns:

1. "I can" != "I can build an algorithm which can".
2. *Can* you? Look at some data dumps from CERN and try to classify them.
3. What exactly are "features" (mathematically)?
4. What does "fits best" mean (mathematically)?

I recommend three things that will help you build a (better) intuition.

1. Study computability and complexity theory -- this will help you build intution for hardness of computational problems.
2. Program things -- this will help you build intution for hardness of implementing things.
3. Try to build an unsupervised learner and fall into all the pitfalls.
> 6 votes

# Answer
implementing any nontrivial machine learning problem is difficult! but there are some basic different levels of difficulty (a continuum/hierarchy so to speak). the professor is contrasting the problem with another problem. consider these two problems. image classification is a common challenging problem at the edge of ML feasibility but of course not the only kind of classification problem; the example is based on it.

* given a set of images, find out distinct objects that are in the images. ie the result is a set of arbitrary choices about which category each images is in. no information is given about categories at all, not even how many categories there are.
* given a set of images and finite set of labels ("categories"), classify the images based on the labels. one has training data such that the images are correctly classified. classify the images in the test set by choosing one of the finite known labels.

clearly in option B there is more data to work with, it is less arbitrary, so the ML algorithm can potentially be more successful, and also there are infinite possible labels in option A.

this basic difference in challenge is why the recent Google results that found image classifications *without* labels in the training data is considered such a dramatic milestone/ breakthrough in ML where even the tabloid headlines were not necessarily overhyped!
> 0 votes

---
Tags: machine-learning, classification, intuition
---


title: Selecting a M.S. in CS focus

text:
# Question
Title: Selecting a M.S. in CS focus
I need to pick a focus in my Masters program.
The running candidates are

* Networking
* Bioinformatics
* Data mining
* Computer Image Recognition

**In order to avoid this becoming a discussion**, I'd be interested in specific data about the type of research done in these fields, or anecdotal experience on why one particular field is more valuable than the others.

For purposes of the question I find all options equally interesting and the Masters program is out of NJIT

# Answer
My response does not provide exact data that you are looking for, but I am going to suggest a few sources from where you can capture the data.

Firstly, if you have some time to choose between those fields, take a course in each if possible and see for yourself whether you actually enjoy or not. I have had cases where I thought I was excited about a subject, started a course and then hated it. These days, you can take a week's worth of course on sites like coursera in each of these fields and see where they stand in your opinion. Of course, instructor and format matters significantly, but you'll still get an idea of what you're going to get into. Getting a hands on 'mini course' will probably give you enough data that you might just be able to decide immediately.

Other than that, it might be worthwhile trying to discover both the research world and the professional world in these fields. For research world, one of my advisors in my MA (non-CS) program advised me to just browse through the journals that were published recently and see what questions were being asked and what questions were being answered. From that list, he suggested, that I should try to evaluate what peeks my interest. I found his advice valuable and hence passing on. This is especially useful when you would do your own research because you would be trying to fit in one of those communities (in fact, he gave me this advise for me to figure out how to go about my MA thesis).

For the professional world, it's a bit harder because the world is not as much consistent as the research world (at least in my experience). However, a few sources often help: look at the job openings in each of those fields and ask the question if any of those will be interesting, and you would want to do that kind of work. Take away all the "fancy" perks and adjective to lure us into those jobs and focus on what your responsibilities will be :-) Other than that, professional magazines help too.

Also look at your core skills as well as where you get your "energy" from? Do you love to teach and write papers? Or do you like to discuss issues and write code? Do you want to get a Masters degree and end there, or are you planning to go for a PhD or an MBA?

All of these will matter. For me, it also matters what my impact for a given project will be (whether a paper or working on a product/service).
> 2 votes

---
Tags: computer-networks, image-processing, data-mining, bioinformatics
---


# Question
Title: Building probability distribution functions from observation
There are N players and M objects, each of the objects has a value. Each player has a strategy in choosing an object. Each round a player will choose an object, many players can choose the same object. However the value of each object is divided evenly among every player that has chosen it. There will be 9000 rounds(choices) per game. Our goal is to maximize the values that we accumulate at the end of the game.

Question: how can I build a probability distribution function for each playing assuming that their decisions are random variables?

Current Approach: My current approach is to count the frequency of a player choosing a specific object and dividing by the total number of rounds, that would give a probability a player is likely to choose that specific object.

Problem: With each player playing aggressively trying to be unpredictable as possible(noise), with my current approach the probability distribution functions are not accurate(9000 rounds doesn't seem to be enough data). Is there a better way to build these distribution functions?

Note: I've read somewhere that (Bayes model and HMM) are more superior than frequency counts, but I am not sure how to adapt it to this situation.

# Answer
i am not sure i understand correctly what the question is or rather what are the observations from which the (experimental) distributions are going to be *estimated*.

The problem of a distribution estimation is related more to statistics than computer science althougn it can be relevant in this area as well.

There are various methods using 2 main approaches:

1. Parametrized models of a probability distribution, where one (assuming prior knowledge) uses a pre-defined model (or *form* or function) of the distribution (e.g a Gaussian) with some free parameters depending on data (observations) and estimates these parameters (eg through Maximum Likelihood or EM algorithm or Maximum Entropy etc..). Even if the form of the prob distribution is not known this method can still be used on approximations like Gauusian Mixture Models. This method produces *smooth* (and usually *robust*) estimated distributions assuming the prior form is *close* to the underlying prob. distribution.
2. Un-parametrized models, *estimate* the whole PD (including its form) directly from the data. methods in this category are Parzen windows and kernel estimation. This method can be better from parametrized estimation provided the form of the underlying pdf is completely unknown or non-trivial or irregular in some sense.

All the previous methods are computationally efficient (although not necessarily polynomial). This is like the way the Simplex algorithm works, although it is not polynomial-time, it is efficient in many practical situations.
> 1 votes

# Answer
I think you are using the wrong approach. I suggest you use game theory, to figure out your optimal play.

Start with the special case of $N=2$; each player has $M$ choices, so we have a $M\times M$ payout matrix. The payout matrix is easy to define. The optimal strategy is (in general) a randomized strategy. There are standard methods to compute the optimal strategy, given the payout matrix. Then, you can play the optimal strategy. So, for $N=2$, solving this game is easy.

For $N\>2$, the game theory gets a bit more complicated, but I think similar ideas still represent a better approach to this problem than trying to estimate the distribution that each player has chosen in the past. After all, past history is not necessarily representative of future play; players might change their choices over time, so the distribution of their choices earlier in the game might not be representative of the distribution of their choices later in the game.
> 1 votes

---
Tags: machine-learning, probability-theory, modelling
---


# Question
Title: Example algorithms for first class in programming for EE students
I am professor of Electrical Engineering who will teach, for my first time, a class to first-year EE students about programming. This will be their first contact in an academic setting with programming, algorithms, data structures, etc.

When introducing the subject of algorithms, I'd like to present a few problems, give a naïve algorithm that might be the first thing that comes to mind to solve it, and then show an efficient algorithm that is clearly more efficient than the naïve one. Ideally, something that none of the students might come up with on their own. Obviously, being their first class in programming, I can't use overly complicated algorithms or I'll run the risk of confusing rather than illuminating them.

Right now I've collected a few examples:

1. Naïve modular exponentiation vs. left-to-right modular exponentiation
2. Linear search vs. binary search
3. Trial division vs. sieve of Erathosthenes (for creating a list of primes from, say, 1 to 100)
4. Naïve polynomial evaluation vs. Horner's rule
5. GCD by factoring vs. Euclid's GCD
6. Schoolbook multiplication vs. Karatsuba multiplication

Of these, (1) and (2) I believe students could come up on their own, and maybe (3) and (4) as well. (5) and (6), I'd risk saying most wouldn't come up with on their own.

What other algorithms could I use to demonstrate the importance of efficient algorithms? Also, would anyone advise against using one of the examples I've listed above, and for what reason?

# Answer
> 1 votes
My favorite example of the value of efficiency is Fibonacci number computation. A naive programmer could use the recursive top-down solution, which takes exponential time. A bottom-up iterative solution, on the other hand, runs in linear time.

---
Tags: algorithms, efficiency, education
---


title: Why is this algorithm $O(n^3)?$

text:
# Question
Title: Why is this algorithm $O(n^3)?$
In a programming book that I'm currently reading it's stated that

$$\sum\limits\_{i=1}^{n}i^2$$ is $O(n^3)$. My understanding was that $i\times i$ is a primitive operation and the complexity would be $O(n)$. What am I missing?

# Answer
The expression $$ \sum\_{i=1}^n i^2 $$ is not an algorithm. It is just a number. In fact, what the book really means is the *function* $$ n \mapsto \sum\_{i=1}^n i^2. $$ Since $$ \sum\_{i=1}^n i^2 = \frac{n(n+1)(2n+1)}{6} = \frac{2n^3+3n^2+n}{6}, $$ we see that this sum is indeed $O(n^3)$, in fact, even $\Theta(n^3)$.

We often use big O notation in analyzing the *running time* of an algorithm. Quicksort runs in time $O(n\log n)$ (on average) since the function $T(n)$ measuring its average running time on inputs of length $n$ is $O(n\log n)$ — the function $T(n)$, not the algorithm itself.
> 12 votes

# Answer
As an addendum to the other fine answer, you don't actually need to calculate what the exact value of the summation is:

$$\sum\_{i=0}^{n} i^2 \le \sum\_{i=0}^n n^2 = (n+1) n^2 = O(n^3)$$

It's a very coarse upper bound, but that's good enough.

As an exercise, show that the sum is $\Omega(n^3)$ using a similar argument. It's a little trickier, because you need to find a lower bound that is cubic.
> 4 votes

# Answer
For some geometric intuition about the sum, consider building a pyramid out of stone blocks. The number of stones you need to build the first layer is $n^2$, the number of stones for the second layer is $(n-1)^2$, then for the next layer $(n-2)^2$ stones, and so forth until the very top layer which requires $1$ stone. In other words, the number of stones needed to build the pyramid is, $$\text{stones needed} = \sum\_{i=1}^n i^2.$$

Now since your pyramid is made out of blocks and not smooth, it is not a "true pyramid". However, it is a pretty good approximation. In particular, your blocky pyramid contains a small true pyramid with $n\text{-by-}n$ base, and is contained in a large true pyramid with $(n+1)\text{-by-}(n+1)$ base. Since the volume of a true pyramid is $\frac{1}{3} \cdot \text{base} \cdot \text{height}$, and the pyramid has base area $n^2$ and height $n$, altogether this gives us the inequality of volumes, $$V(\text{small pyramid}) \< V(\text{blocky pyramid}) \< V(\text{large pyramid})$$ $$\frac{1}{3} n^3 \< \sum\_{i=1}^n i^2 \< \frac{1}{3} (n+1)^3.$$

Here is a diagram showing what's going on for $n=4$:
> 2 votes

---
Tags: time-complexity
---