# Question
Title: Algorithms for graph generation using given properties
There may be a large number of algorithms proposed for generating graphs satisfying some common properties (e.g., clustering coefficient, average shortest path length, degree distribution, etc).

My question concerns a specific case: I want to generate a few *undirected regular* graphs (i.e., every node in these graphs has the same number of neighbors) with different clustering coefficients and average shortest path lengths. More generally, by fixing a degree distribution, I want to generate graphs with different clustering coefficients and average shortest path lengths.

I wonder what are the well-known algorithms for doing this (or in fact, is there any?), and what are the recommended software for the same purpose?

# Answer
> 5 votes
There are no general algorithms for your problem but what one usually does (for graphs of small orders) is

1. Use nauty to generate graphs satisfying some rough constraints (you can make nauty generate only (bi)connected graphs, regular graphs, triangle/quadrangle free graphs,..)
2. Use an external program to extract only the graphs you need with respect to some additional properties that you want.

You can do both 1 and 2 in sage! For example consider that you want to generate all connected 5-regular graphs of order 20 that have average distance 10 (Wiener index??) and some clustering coefficient. You do the following

```
for G in graphs.nauty_geng(" 20 -c -d5 -D5" ):
    if G.wiener_index() == 10 and G.clustering_coeff() == SOMETHING:
       print G.adjacency_matrix()

```

Let me know if you need some more specific answers related to sage.

---
Tags: algorithms, graphs, sampling
---


# Question
Title: Matching girls with boys without mutual attraction (variant of maximum bipartite matching)
Let us say you have a group of guys and and a group of girls. Each girl is either attracted to a guy or not, and vice versa. You want to match as many people as possible to a partner they like.

Does this problem have a name? Is it feasibly solvable? Sounds hard to me...

Ps. note that since the attraction is not neccessarily mutual the standard max-flow solution does not work.

# Answer
> 5 votes
I think it is still the standard bipartite maximum matching problem, which can be solved by the algorithm of Hopcroft and Karp.

You put an edge in the bipartite boys-girls graph, iff you have mutual attraction. Then you maximize your matching and voilà. Notice that if you would never assign a boy to a girl with one-sided attraction, since this does not increase you objective function (# of mutal attractions).

If you want to maximize the number of *happy people*, then you set the weights of the complete bipartite boys-girls graph as follows

* mutual attraction = 2 happy people
* one sided attraction = 1 happy people
* otherwise = 0 happy people

You then can compute the maximum weighted bipartite matching.

---
Tags: algorithms, graphs, bipartite-matching
---


# Question
Title: Inheritance, and dynamic access to members/attributes and methods in Java-like languages
I have a question about inheritance in Java-like OO programming languages. It came up in my compiler class, when I explained how to compile methods and their invocation. I was using Java as example source language to compile.

Now consider this Java program.

```
class A {
  public int x = 0;
  void f () { System.out.println ( "A:f" ); } }

class B extends A {
  public int x = 1;
  void f () { System.out.println ( "B:f" ); } }

public class Main {
  public static void main ( String [] args ) {
    A a = new A ();
    B b = new B ();
    A ab = new B ();

    a.f();
    b.f();
    ab.f();
    System.out.println ( a.x );
    System.out.println ( b.x );
    System.out.println ( ab.x ); } }

```

When you run it, you get the following result.

```
A:f
B:f
B:f
0
1
0

```

The interesting cases are those that happen with the object `ab` of static type `A`, which is `B` dynamically. As `ab.f()` prints out

```
B:f

```

it follows that method invocations are not affected by the compile-time type of the object the method is invoked with. But `System.out.println ( ab.x )` prints out `0`, so member access is affected by compile-time types.

A student asked about this difference: should not the access of members and methods be consistent with each other? I could not come up with a better answer than "that's the semantics of Java".

Would you know a crisp *conceptual* reason why members and methods are different in this sense? Something I could give my students?

**Edit**: Upon further investigation, this seems to be a Java idiosyncrasy: C++ and C# act differently, see e.g. Saeed Amiri's comment below.

**Edit 2**: I just tried out the corresponding Scala program:

```
class A {
  val x = 0;
  def f () : Unit = { System.out.println ( "A:f" ); } }

class B extends A {
  override val x = 1;
  override def f () : Unit = { System.out.println ( "B:f" ); } }

object Main {
  def main ( args : Array [ String ] ) = {
    var a : A = new A ();
    var b : B = new B ();
    var ab : A = new B ();
    a.f();
    b.f();
    ab.f();
    System.out.println ( "a.x = " + a.x );
    System.out.println ( "b.x = " + b.x );
    System.out.println ( "ab.x = " + ab.x ); } }

```

And to my surprise this results in

```
A:f
B:f
B:f
a.x = 0
b.x = 1
ab.x = 1

```

Note that the `overrise` modifiers are necessary. This surprises me because Scala compiles to the JVM, and moreover, when I compile and execute the Java program at the top using the Scala compiler/runtime, it behaves like the Java program.

# Answer
> 6 votes
I suspect that this is intimately related to *shadowing* of fields in Java.

When writing a derived class, I can, as in your example, write a field `x` that shadows the definition of `x` in the base class. This means that in the derived class, the original definition is no longer accessible via name `x`. The reason Java allows this is so that derived class implementations are less dependent on the base class implementation details, thereby (only partially) avoiding the fragile base class problem. For instance, if the base class did not originally have a field `x`, but then subsequently introduced one, Java's semantics avoid this breaking the derived class implementation.

The variable `x` in the derived class can have a completely different type than the variable in the base class – I tested this, it works. This is in stark contrast to method overriding, where the type needs to be sufficiently compatible (aka, the same). So when I have a variable of type `A` in your example, the only type I can derive for it is the one specified in class `A` (or above). As this can be different from the type declared in class `B`, it is only type safe to return the value of the field `x` from class `A`. (And naturally, the semantics must be the same regardless of what the type of the field is in class `B`.)

# Answer
> 4 votes
In Java, there is no 'static type of an object' - there is the type of the object, and there is the type of the reference. All Java methods are 'virtual' (to use C++ terminology), i.e. they are resolved based on the object's type. And btw. '@Override' has no effect whatsoever on the compiled code - it is just a safeguard that generates a compiler error if the so annotated method does not override a superclass' method.

Field access on the other hand is *never* resolved dynamically - or, to put it differently, Java uses no polymorphism when accessing fields. In the (pathological) case that a subclass has a field x with the same name as a superclass field, the subclass has two fields 'x'. Obviously, there is name shadowing - the name 'x' can be bound to only one of these fields in a given context.

Enter name resolution syntax - when you write b.x, the *compiler* resolves this to the field declared in the subclasss, but when you write ab.x, the compiler resolves that to the field declared in A - both fields being members of class B. You can access both fields from code in class B using super.x:

class B { ... void g() {System.out.println("both: " + x + " and " + super.x);} }

So at runtime, it makes no difference at all whether the subclass' field was named 'x' or 'y' - in both cases, the subclass has two distince fields with no relationship between them.

# Answer
> 1 votes
Remembering that inheritance is a form of saying `B` "is a" `A`, except the functionality of `A` might be extended, inherited member variables can be considered *attributes* of the object. Intuitively, the way we are taught about inheritance (admittedly from a Java-ish point of view), member variables are like attributes, and common attributes are not meant to be extended, rather only functionality is.

For example, suppose you have a `Person` class, and the person has a name variable. The name intuitively won't get changed, even if we extend `Person` to `Student` and `Professor`. However methods, for example like `Student.do_work()` do get extended, to do "homework", while the `Professor` class might grade tests in `Professor.do_work()`.

Of course you can break this intuition, and you can essentially make member variables equivalent to properties, or use getters, which can be overridden etc., but I think what I said above was the intuition of doing it this way. In fact, I'd say it would be unconventional in most cases to have a member variable of the same name, in a derived class.

---
Tags: programming-languages, semantics, typing, object-oriented, java
---


title: What is the TAK function for?

text:
# Question
Title: What is the TAK function for?
We covered this in class today. I understand the mechanics of it, but aside from being a nice example of recursion does it serve any purpose?

Searching the web reveals lots of pages with the formula and it's implementation in code, some talk about the author, but nothing about it's purpose.

# Answer
You might use it to **evaluate the performance of programming languages**:

http://en.wikipedia.org/wiki/Tak\_%28function%29

since recursive methods are pretty useful for benchmarking. In particular, deep recursion tests the speed with which a language can make method calls. This is important because modern applications have a tendency to spend much of their time calling various API functions.

You will also need it to **solve ballot problems** like this one:

```
Suppose A and B are candidates for office and there are 2n voters, n
voting for A and n for B. In how many ways can the ballots be counted
so that B is never ahead of A?

```

http://mathworld.wolfram.com/BallotProblem.html

or just to **generate Takeuchi Numbers**:

```
0, 1, 4, 14, 53, 223, 1034, 5221, 28437, ...

```
> 3 votes

---
Tags: algorithms, recursion
---


title: LL grammars and left-recursiviity

text:
# Question
Title: LL grammars and left-recursiviity
Why LL(k) and LL(∞) are incompatible with left-recursion? I understand that a LL(k) language can support left-recursivity provided that with k-overahead tokens can be resolved any ambiguity. But, with a LL(∞) grammar, which type of ambiguities can't be solved?

# Answer
The problem that $LL$ variants have with left recursion is inherent to the way $LL$ works: it is a top-down type parser, which means it replaces nonterminals by their productions.

An $LL$-style parser works as follows. It traverses the input from left to right in one go. If we are at some point in the input, then we know that everything to the left of this point is OK. For everything to the right of this point, the parser has constructed an 'approximation' of what it expects to see next. Consider for example this grammar:

> 1: $E \to E + E$
> 2: $E \to x$

Note that the grammar is not $LL$, but we can still parse inputs in $LL$-style. On input $x+x+x$, an $LL$-style parser may end up at position $x+\bullet x+x$. Let's assume it has decided that the left part, $x+$, is fine, and for the rest of the input it expects to see $x+E$. It will then find out that $x+x+$ is fine, with $E$ remaining. It may then replace this $E$ by a production, in particular production 2 above. With $x$ remaining, the parser will accept the input.

The trick is then to correctly decide the replacing production for a given nonterminal. A grammar is $LL(k)$ if we can do this by just looking at the next $k$ input symbols, and other techniques are known that are more powerful.

Now consider the following grammar:

> 1: $A \to A a$
> 2: $A \to \varepsilon$

If an $LL$ parser tries to replace $A$ by a production, it has to decide between production 1 and 2.

Let's consider what the proper course of action would be if our parser was omniscient. Every time it replaces the $A$ by production 1, it 'adds' an $a$ to what it expects for the remaining input (the expected remainder goes from $A$ to $Aa$ to $Aaa$...), but the $A$ at the start does not go away. Eventually, it must pick production 2, after which the $A$ disappears and it can never again add $a$s to the expectation.

As there is no chance to match a few more input symbols, the parser must decide at exactly that input position how many times production 1 must be matched. This means it must know exactly how many times in our case the $a$ will appear in the remainder of the input at this moment.

However, $LL(k)$ can see only $k$ symbols ahead. This means that if production 1 must be chosen more than $k$ times, the parser cannot 'see' this and so is doomed to fail. $LL(\*)$ is better at parsing than $LL(k)$, because it can see arbitrarily far ahead in the input, but the crucial detail (which is not always mentioned) is that this lookahead is *regular*.

To imagine what happens, you can view the algorithm as follows: when it has to decide which production to take, it starts up a finite state machine (a DFA, which is equivalent in power to regular expressions) and lets this machine look at the rest of the input. This machine can then report 'use this production'. However, this machine is severely limited in what it can do. Although it is strictly better than looking at only the next $k$ symbols, it cannot for instance 'count', which means that it cannot help in the above situation.

Even if you were to 'hack' in some counting function in this finite automaton, then there are still left-recursive grammars for which you really need more power. For instance, for this grammar:

> $A \to A B$
> $A \to \varepsilon$
> $B \to ( B )$
> $B \to \varepsilon$

you would have to match 'towers' of matching braces, which is something a finite automaton cannot do. Worse still:

> $A \to B C A D E$
> $A \to A'$
> $A' \to A' D E$
> $A' \to \varepsilon$
> $B \to a B a \mid b B b \mid a a \mid bb$
> $C \to c C c \mid d C d \mid c c \mid d d$
> $D \to e D e \mid f D f \mid e e \mid f f$
> $E \to g E g \mid h E h \mid g g \mid h h$

is a totally awful grammar, for which I'm pretty sure no known linear time parsing algorithm works and all known general parsing algorithms take quadratic time. Worse still, any grammar describing this language is necessarily left-recursive. The grammar is still unambiguous however. You need a hand-crafted parser to parse these monsters in linear time.
> 6 votes

---
Tags: formal-grammars, parsers, left-recursion
---


# Question
Title: Why is this $f(n) \leq 6n^3 + n^2 \log n \in O(n^3)$ for all $n \geq 1$?
I'm currently studying for an algorithms midterm in about 2 days and am reading from the beginning of the course, and stumbled upon this when I actually looked at the examples.

The question equation: $f(n) = 6n^3 + n^2\log n$

The exact line written for the answer is: $f(n) \leq 6n^3 + n^2 \centerdot n \text{, for all }n \geq 1, \text{since} \log n \leq n$

First of all, I don't really see why the logarithm was removed or why it actually matters when the dominant piece is the $6n^3$. I also don't get why it's $n \geq 1$ instead of $n \geq 6$ (unless it's a continuation of the first one.

Been staring at it for about 15 minutes and still not getting how it comes down to $n \geq 1$. Would anybody be kind enough to give me a hint as to what's wrong?

# Answer
> 10 votes
First of all, it is not a "question equation" but the **definition** of $f$.

The task at hand is to show that $f(n) \in O(n^3)$. By the definition of $O(n^3)$ this means that we need to find $n\_0$ and $C$ such that $f(n) \leq C n^3$ for all $n \geq n\_0$. There may be many $n\_0$ and $C$ that work, we just need to find one.

I pull out of my hat $n\_0$ and $C$ that work (because I am a professional mathematician), namely $n\_0 = 1$ and $C = 7$. Now we have to verify: for all $n \geq 1$ we have $f(n) \leq 7 n^3$.

Because $\log n \leq n$ whenever $n \geq 1$ (draw a graph of $y = \log x$ and $y = x$, and stare at it for a while) we may replace $\log n$ in the definition of $f$ with $n$, and we will get something bigger. So we have for all $n \geq 1$: $$f(n) = 6 n^3 + n^2 \log n \leq 6 n^3 + n^2 \cdot n = 6 n^3 + n^3 = 7 n^3$$ We have established that $f(n) \leq 7 n^3$ for all $n \geq 1$, as required. We get an A on the midterm.

The question remains how I pulled out of my hat $n\_0 = 1$ and $C = 7$, since this is what you will have to do on your mid-term. You start with $f(n)$ and "massage" it into something that is larger and has the form $C n^3$. On the way you observe that your massaging only works for $n$ large enough, and that gives you $n\_0$.

Let us have another example: show that $g(n) = 23 n^2 + 17 + \log n$ is in $O(n^2)$. The massaging process goes as follows: turn every term which grows more slowly than $n^2$ into something of the form $C n^2$, and think about which $C$ to use and for which $n$ it is going to work. We have three terms to worry about, and notice how each has several possible ways of massaging:

* the term $23 n^2$ is already in the correct form.
* the term $17$, we give three possibilities just for fun:
    + $17 \leq 17 n^2$ for $n \geq 1$
    + $17 \leq 17 n^2$ for $n \geq 100$
    + $17 \leq n^2$ for $n \geq 5$
* the term $\log n$:
    + $\log n \leq 42 n^2$ for all $n \geq 3$

I have purposely chosen weird and suboptmal values for $C$ and $n\_0$ for each of the terms to show you that there is a lot of choice. For example, it would have been more "optimal" to say that $\log n \leq n^2$ for $n \geq 1$. For the term $17$ I gave three possible massages, let us work with the second one. We compose our observations together by replacing each term with its upper bound: $$g(n) = 23n^2 + 17 + \log n \leq 23 n^2 + 17 n^2 + 42 n^2 \leq 1000 n^2.$$ I was too lazy to compute $23 + 17 + 42$ so I just approximated it with something larger, namely $1000$. Thus our $C = 1000$. We still have to figure out $n\_0$. As far as the term $23 n^2$ is concerned any $n\_0$ is ok. The term 17 wants $n\_0 = 100$ and the term $\log n$ wants $n\_0 = 3$. So we may take any $n\_0$ that is larger than or equal 100 and 3, for example let us take $n\_0 = 4127$.

We have now successfull pulled $C$ and $n\_0$ from a hat. It is time to write the official solution so that we appear to be very smart, and to confuse students who start studying only two days before the midterm:

> The function $g(n) = 23n^2 + 17 + \log n$ is in $O(n^2)$ because for every $n \geq 4127$ we obviously have $g(n) \leq 23 n^2 + 17 n^2 + 42 n^2 \leq 1000 n^2$. We used here the easy observations that $17 \leq 17 n^2$ and $\log n \leq 42 n^2$ for every $n \geq 4127$.

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


# Question
Title: Removing duplicates efficiently and with a low memory overhead
I want to filter efficiently a list of integers for duplicates in a way that only the resulting set needs to be stored.

One way this can be seen:

* we have a range of integers $S = \\{1, \dots{}, N\\}$ with $N$ big (say $2^{40}$)
* we have a function $f : S \to S$ with, supposedly, many collisions (the images are uniformly distributed in $S$)
* we then need to store $f\[S\]$, that is $\\{f(x) | x \in S\\}$

I have a quite accurate (probabilistic) estimation of what $|f\[S\]|$ is, and can therefore allocate data structures in advance (say $|f\[S\]| \approx 2^{30}$).

I have had a few ideas, but I am not sure what would be the best approach:

* a bitset is out of the question because the input set does not fit into memory.
* a hash table, but (1) it requires some memory overhead, say 150% of $|f\[S\]|$ and (2) the table has to be explored when built which requires additional time because of the memory overhead.
* an "on the fly" sort, preferably with $O(N)$ complexity (non-comparison sort). Regarding that, I am not sure what is the major difference between bucket sort and flashsort.
* a simple array with a binary search tree, but this requires $O(N \log |f\[S\]|)$ time.
* maybe using Bloom filters or a similar data structure could be useful in a relaxation (with false positives) of the problem.

Some questions on stackoverflow seem to tackle with this sort of things (https://stackoverflow.com/questions/12240997/sorting-array-in-on-run-time, https://stackoverflow.com/questions/3951547/java-array-finding-duplicates), but none seems to match my requirements.

# Answer
> 1 votes
Why not bin and chain?

The idea is to store positive integers representable by $n = k+m$ bits in an array $A$ of $2^k$ entries representing ranges of values: entry $A\[y\]$, $y \ge 0$, represents the range $\[2^m y, 2^m(y+1)-1\]$. For any $1 \le x \lt 2^n$ we may write $x = 2^m y + z$ where $y$ has $k$ bits and $z$ has $m$ bits. Try to store $z$ (not $x$!) at location $y$:

* When $A\[y\]=z$ already, do nothing: $x$ is a duplicate.
* When $A\[y\]$ is uninitialized, store $z$ at $A\[y\]$.
* Otherwise, store an index into a separate array used to chain the $z$'s (which have collided at $y$) in linked lists. You will have to search linearly through the list headed by $A\[y\]$ and, depending on what the search uncovers, potentially insert $z$ into the list.

At the end, $f(S)$ is easy to recover by looping through the initialized entries of $A$ and--by merely concatenating two bitstrings--reassembling each $z$ found at location $y$ (either directly or within a chain referenced there) into the original value $x = 2^m y + z$.

When the distribution is close to uniform and $2^k$ exceeds $N$, there will not be much chaining (this can be assessed in the usual ways) and the chains will tend to be short. When the distribution is nonuniform, the algorithm still works, but can reach quadratic timing. If that's a possibility, use something more efficient than chains (and pay a little overhead for storage).

The storage needed is at most $2^n$ bits for $A$ and $2^{2k}$ bits for the chains (assuming $m \le k$). This is exactly the space needed to store $2^k$ values of $n$ bits each. If you're confident in the uniformity, you can underallocate the storage for the chains. If nonuniformity is a possibility, you may want to increase $k$ and fully advocate the chain storage.

An alternative way of thinking about this solution is that it *is* a hash table with a particularly nice hash function (take the $k$ most significant bits) and, because of that, we only need to store the least significant $m=n-k$ bits in the table.

There are ways to overlay storage for the chains with the storage for $A$ but it doesn't seem worth the bother, because it wouldn't save much (assuming $m$ is much smaller than $k$) space and would make the code harder to develop, debug, and maintain.

---
Tags: algorithms, data-structures, sorting
---


# Question
Title: How does increasing the page size affect the number of page faults?
If we let the physical memory size remain constant,

* What effect does the size of the page have on the number of frames?
* What effect does the number of frames have on the number of page faults?

Also, please provide reference strings as an example.

# Answer
> 2 votes
After careful reading i have come to understand that this is a complex behavior when the page size is doubled the page faults is reduced also when the page size is halved. The replacement algorithm considered is FIFO.

note: page fault is denoted by `p` and no page fault by `n`
`number of frames = physical memory size / page size`

`the page size = frame size`

Reference string sequence: 1 2 3 4 5 1 2 3 4 5

*Condition 1: Initial*

> `physical memory = 400 bytes`
> `page size = 100 bytes`
> `number of frames = 4`

```
1 2 3 4 5 1 2 3 4 5
p p p p p p p p p p
1 1 1 1 5 5 5 5 4 4
  2 2 2 2 1 1 1 1 5
    3 3 3 3 2 2 2 2
      4 4 4 4 3 3 3

```

`total page fault = 10`

*Condition 2: When page size is halved*

> `physical memory = 400 bytes`
> `page size = 50 bytes`
> `number of frames = 8`

```
1 2 3 4 5 1 2 3 4 5
p p p p p n n n n n
1 1 1 1 1 1 1 1 1 1
  2 2 2 2 2 2 2 2 2
    3 3 3 3 3 3 3 3
      4 4 4 4 4 4 4
        5 5 5 5 5 5

```

`total page fault = 5` with 3 frames remaining unused.

*Condition 1: when the page size is doubled.*

> `physical memory = 400 bytes`
> `page size = 200 bytes`
> `number of frames = 2`

*Each frame can accommodate more data in one frame, here two original pages can be loaded to the frame at any time.*

> 1 2 3 4 5 1 2 3 4 5 =\> (1 2) (3 4) (5 1) (2 3) (4 5) =\> 1 3 5 2 4

```
1 3 5 2 4
p p p p p
1 1 5 5 4
  3 3 2 2

```

`Total page faults = 5`

# Answer
> 8 votes
Since the number of frames is equal to the size of the memory divided by the page size, increasing the page size will proportionately decrease the number of frames.

Having fewer frames will tend to increase the number of page faults because of the lower freedom in replacement choice. Imagine a system with four frames with the reference history of 0, 4, 3, 1. On a page fault, LRU would victimize frame 0. With a doubling of page size the reference history becomes 0a, 1b, 1a, 0b; so the LRU victim would be 1 (corresponding to small page frames 3 and 4) when one would prefer to victimize 0a (the first half of 0).

Large pages will also waste more space with internal fragmentation. If a typical process has three sections (text, heap, stack), on average about half a page per section is unused so 1.5 pages worth of memory are unused per process. If page size is doubled, this waste is doubled.

On the other hand, using larger pages will draw in more memory per fault, so the number of faults may decrease if there is limited contention and/or reasonably high spatial locality at the scale of page size (e.g., references to the high half of a double-size page occurring near in time to references to the low half would make replacement of a double-size page a close approximation of the replacement for the two smaller pages of which it is composed). (If memory is abundant, first reference \[a.k.a. compulsory\] page faults will tend to dominate, so larger pages will reduce the number of page faults.) Of course, the OS can use prefetching to accomplish the same reduction in faults with the benefit of being able to throttle prefetching under heavy memory pressure or poor prefetch behavior while avoiding the above mentioned disadvantages of large pages.

Of course, larger pages do reduce the number of TLB misses (sometimes called minor page faults), and an OS can support multiple page sizes and aggregate smaller pages to form larger pages (for reducing TLB misses) and deaggregate larger pages to from smaller pages (to reduce the volume of memory swapped and to reduce the above negative effects of larger pages).

---
Tags: operating-systems, memory-management, virtual-memory, paging
---


# Question
Title: Solving recurrence with logarithm squared $T(n)=2T(n/2) + n \log^2n$
$T(n)=2T(n/2) + n\log^2(n)$.

If I try to substitute $m = \log(n)$ I end up with

$T(2^m)=2 T(2^{m-1}) + 2^m\log^{2}(2^m)$.

Which isn't helpful to me. Any clues?

PS. hope this isn't too localized. I specified that the problem was a squared logarithm which should make it possible to find for others wondering about the same thing.

# Answer
> 4 votes
This is indeed the second case in the Master Theorem. For the standard recursion form $$T(n)=a\\;T(n/b)+f(n),$$ you get $a=b=2$, and therefore $f(n)=\Theta(n^{\log\_b a} \log^2 n)=\Theta(n \log^2 n)$.

Applying the Master theorem yields $T(n)=\Theta(n\log^3 n)$.

---
Tags: asymptotics, proof-techniques, recurrence-relation
---


# Question
Title: Given an LR grammar G and a string w, is it possible to quickly find all substrings in w that are in L(G)?
Say I have an LR grammar *G* and a string *w*. I know that I can check if *w* is in the language of *G* in linear time. But what if *w* itself is not in the language of *G*, but I want to find all substrings of *w* that are in the language of *G*? And can I get parse trees for those substrings? What would be the time complexity for these things?

# Answer
You can do this in $O(n^2)$ time using an advanced version of Earley. See this answer for this advanced version.

This algorithm can parse any $LR(k)$ grammar in linear time. While doing so, it also parses all prefixes of the string (if no lookahead is used - for lookahead you would need to also perform actions that would be performed at end-of-string tokens) and puts 'I am finished' items in item sets whose index corresponds to an index in the string at which a prefix was recognized to be in the language.

We can therefore start this algorithm at every position in the string, parsing the remainder of the string, for a total running time of $O(n^2)$. As we can have $O(n^2)$ matches, this is in a sense optimal.

You could also change the algorithm and run it once: you can insert an 'I've started here' item at every index, and then parse the string running the Early version only once. This may be faster in practice, but I'm not sure what its running time would be.

Note that recovering a parse forest from an Earley parse is not the simplest thing in parsing. The above algorithm probably needs augmenting if you also want all the parses of the substrings (rather than just what substrings match). Note that on grammars that are not $LR(\pi)$ for some regular partition $\pi$ (which includes all $LR(k)$ languages), the above algorithm may not run in quadratic time.
> 1 votes

---
Tags: formal-grammars, parsing, substrings
---


# Question
Title: Difference between reductions in algebraic problems versus reductions in computational intractability
When I read about NP-completeness for the first time, I really wondered why is the concept of reductions given such high emphasis, after all we have been looking at concepts such as reductions and 'special case of one another problem' in mathematics since elementary algebra. What I mean by reductions in algebra is the following.

Problem 1: Find value of x such that $x^2+ax+b=0$

Problem 2: Find value of x such that $(x+m/n)^2=0$

We can go on proving both the problems are same and one solution can be translated to another.

My question is that "Is the concept of reductions in computational intractability same as that in above algebraic theory?" If not, how are the reductions in CI theory different?

# Answer
> 3 votes
Reductions in computational complexity are similar to the reduction you described, but are usually given with bounds on the time or space. To be useful, these bounds are usually inconsequential (ie. the same or smaller) to the bounds of solving the problem.

Reductions in computational complexity are about converting one problem to another equivalent one. Usually one would also give bounds on how hard (how much time/space) a reduction takes as well. For example, all NP-complete problems have reductions to each-other, and their reductions are polynomially bounded. Since algorithms solving NP-complete problems are suspected to take exponential time on a deterministic Turing machine, the polynomial time reductions are inconsequential (compared with the time of actually solving the reduced problem), and thus these reductions make all of the NP-complete problems essentially equivalent. There can reductions between problems in other classes of complexity as well, and to be useful they would likely be bounded by something considered inconsequential to solving them.

# Answer
> 1 votes
We are interested in reductions (relative hardness) because of our inability to prove absolute hardness results.

For example, say you give me a problem to solve. After spending time on it, I am unable to come up with an efficient algorithm for it. Maybe I'm too dumb to come up with an algorithm, or maybe a (fast) algorithm doesn't exist. I would like to back up my excuse somehow. If I can reduce a known hard problem $X$ to the problem you gave me, I'm showing that $X$ is at least as hard the problem you gave me. That means that maybe I'm not *that* dumb; other people have not been able to solve the problem either.

# Answer
> 1 votes
Reductions are useful in studying computability not so much to prove that problems *are* computable (although that is also done), but to prove that problems are *not* computable.

Used to prove incomputability, a reduction proof is a particular kind of proof by contradiction. You take your problem P and a known incomputable problem X, and you show that if you had an algorithm that computed solutions to P you could use it to compute solutions to X. Since we already know that there there does not exist a method for computing solutions to X this proves that there cannot exist a method for computing solutions to P.

This isn't really "different" from the kind of reduction you're talking about in algebra; if you have an algebraic problem P and you show that a solution to P could be used to find a solution to X, and you already know that X has no solutions, then this would show that P has no solutions either. But you usually think about the notion of "problem" slightly differently in algebra, as well as about the way you use "reductions".

My experience in mathematics was that you're usually aiming to turn an equation you don't know how to solve in to a form that you do know how to solve, in order to find a particular solution (possibly with unknown constants). Whereas a "problem" in computer science is a specification for producing an output (usually yes/no) on instances of an infinite family of inputs.1 And for computability purposes you're interested not in finding any particular solution, but in showing whether or not there exists an algorithm that can compute the solution for any input.

Basically it has turned out that a large number of computational problems have been difficult to directly prove incomputable, but are relatively easy to reduce to known incomputable problems. Variants on the Halting Problem are particularly rich sources of undergraduate-level incomputability proofs. I'm not aware that this is done nearly so much in mathematics, hence the difference in emphasis.

---

1 Any problem that only has one instance (e.g. one specific algebraic formula, like 2x^8 - 9 = 83) is completely uninteresting from the point of view of computability theory, because finite problem series are all trivially computable by a stupid algorithm that simply has all the solutions hard-coded and immediately prints the one corresponding to its input.

My Theory of Computation lecturer liked to joke that the problem "does God exist?" is computable; the program that computes the solution is either a single-state DFA that immediately accepts, or a single-state DFA that immediately rejects. We just don't know which one it is!

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


# Question
Title: How can repeated addition/multiplication be done in polynomial time?
I can see how adding 2 unsigned $n$-bit values is $O(n)$. We just go from the rightmost digits to the leftmost digits and add the digits up sequentially. We can also perform multiplication in polynomial time ($O(n^2)$) via the algorithm we all learned in grade school.

However, how can we add up or multiply say $i$ numbers together in polynomial time? After we add up 2 numbers together, we get a bigger number that will require more bits to represent. Same with multiplication.

How can we ensure that these extra bits do not produce exponential blowup?

# Answer
> 5 votes
From what you said, I suppose that you consider complexity in terms of number of bits of the input.

Say you add up two numbers $a$ and $b$, with respectively $n\_1$ and $n\_2$ bits, then the result is at most $\max(n\_1, n\_2) + 1$ bits since $a + b \leq 2 \times \max(a, b)$.

For the multiplication, the result is at most $2 \times \max(n\_1, n\_2)$ bits since $a \times b \leq \max(a, b)^2$.

The important thing is that the number of bits necessary to represent the sum / product of two numbers is polynomial in the number of bits to represent those numbers. Hence, for $i$ numbers, the number of bits necessary to represent the answer is still polynomial in the number of bits of the input (since composition of polynomial functions yields polynomial functions).

Edit: actually, the really important thing is that $i$ is not part of the input, it is fixed. Otherwise, if you take for instance $2 \times 2 \times \ldots \times 2 = 2^i$, the answer takes $2^{i-1}$ bits, while the input takes $i + \log i$ bits. But if $i$ is fixed, then $2^{i-1}$ is a constant. This kind of distinction happens quite often in computer science, especially in the field of fixed parameter tractability.

---
Tags: time-complexity, arithmetic, integers
---


title: Is the k-clique problem NP-complete?

text:
# Question
Title: Is the k-clique problem NP-complete?
In this Wikipedia article about the Clique problem in graph theory it states in the beginning that the problem of finding a clique of size K, in a graph G is NP-complete:

> Cliques have also been studied in computer science: finding whether there is a clique of a given size in a graph (the clique problem) is NP-complete, but despite this hardness result many algorithms for finding cliques have been studied.

But in this other Wikipedia article about the Clique problem in CS it says it is solving the problem for a fixed size k is a problem in P, it can be brute forced in polynomial time.

> A brute force algorithm to test whether a graph G contains a k-vertex clique, and to find any such clique that it contains, is to examine each subgraph with at least k vertices and check to see whether it forms a clique. This algorithm takes time O(n^k k^2): there are O(n^k) subgraphs to check, each of which has O(k^2) edges whose presence in G needs to be checked. Thus, the problem may be solved in polynomial time whenever k is a fixed constant. When k is part of the input to the problem, however, the time is exponential.

Is there something I am missing here? Maybe a difference in the wording of the problem? And what does the last sentence mean, that "When k is part of the input to the problem, however, the time is exponential."? Why is there a difference when the k is part of the input to the problem?

My idea is that to find a clique of size k in a graph G, is that we first choose a subset of size k of nodes from G, and test wether they are all related to the other k nodes, which can be done in constant time. And repeat this until we have a clique of size k. The number of sets of k nodes we can choose from G is n! / k!\*(n-k)!.

# Answer
> 22 votes
Just elaborating what @Lamine pointed out : When $k$ is part of the input, $k$ can be as large as $\frac{n}{2}$, in which case the number of potential clique sets are $\binom{n}{\frac{n}{2}}$ which is at least $\left( \frac{n}{\frac{n}{2}} \right)^{\frac{n}{2}}$. Hence your naive algorithm would take time $2^{\frac{n}{2}}$ which is clearly exponential in input length $|x|+|k|=n+\log n$. The parameterized version $G(n,k)$ where we are looking for $k$-cliques in an $n$-vertex graph captures the hardness of the problem in its most generalized form because $k$ is part of the input. Hence a poly-time algorithm for $G(n,k)$ would also imply a poly-time algorithm for any specific $k$.

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


# Question
Title: is there an example of an algorithm that has O(1/n)?
> **Possible Duplicate:**
> Complexity inversely propotional to $n$

I'm curious if anyone's come up with a problem or method as n =\> infinity t =\> 0. Are there any sort of cases found in quantum computing?

# Answer
As the complexity of an algorithm is a measure of the number of operations (in a sense to be defined in each context) needed to do some computation in function of the size of some input, sub-constant complexity does not make any sense. With your exemple, $O(\frac1n)$, it means that for a sufficiently large input, the algorithm does strictly less than one operation, which in terms of Turing machines means that the initial state is accepting, which means that the corresponding Turing machine does not output anything.

Edit: I had not seen the quantum computing reference, so my answer might not be total, although I doubt it makes sense even in that context.
> 2 votes

---
Tags: time-complexity
---


# Question
Title: Minimum cost subset of sensors covering targets
I have a dynamic programming problem:

> If I have a set of sensors covering targets (a target might be covered by mutiple sensors) how can I find the minimum cost subset of sensors covering all targets given each sensor has a cost?

I have thought a lot about this, but I can't reach the recursive formula to write my program. The greedy algorithm does not always provide the correct minimum cost subset. My problem is that sensors overlap in covering targets. Any help?

**Example:** I have set of sensors $\\{s\_1,s\_2,s\_3\\}$ with costs $\\{1,\frac{5}{2},2\\}$ and 3 targets $\\{t\_1,t\_2,t\_3\\}$. Sensors cover $\\{t\_1 t\_2,t\_1 t\_2 t\_3,t\_2 t\_3\\}$ and I need to get minimum cost subset by dynamic programming. For the above example if I use greedy algorithm I would get $s\_1,s\_3$ but the right answer is $s\_2$ only.

# Answer
> 5 votes
Your problem is equivalent to the weighted version of Set Cover, which is NP-complete (and delving into other complexity classifications, W\[2\]-complete and inapproximable within $O(\log n)$).

If you want a polynomial-time algorithm, you're going to have to impose restrictions on either your problem or the input.

---
Tags: algorithms, dynamic-programming
---


# Question
Title: A programming language that can only implement computable bijective functions?
Are there programming languages(or logic) that can implement(or express) a function $f:\mathbb{N}\to \mathbb{N}$ if and only if $f$ is a computable bijective functions?

# Answer
There is no such language.

However, have a look at Boomerang. It is a language for writing bijections between strings. I do not know how wide a class of maps is expressible in it, but I am sure you can find out if you search a bit.

It is reasonable to require of a programming language that the set of valid programs be recognizable by an interpreter or a compiler, i.e., that it be a computably enumerable set. Suppose then we had a programming language whose set of valid programs were computably enumerable and which implemented precisely all computable bijections $\mathbb{N} \to \mathbb{N}$. That would imply that we can computably enumerate all computable bijections (simply enumerate all valid programs in this programming language), but this is impossible by the next theorem.

**Theorem:** *Suppose $f\_0, f\_1, f\_2, \ldots$ is a computable sequence of computable bijections. Then there is a computable bijection which is not in the sequence.*

*Proof.* We construct a bijection $g : \mathbb{N} \to \mathbb{N}$ as follows. To define the values $g(2 k)$ and $g(2 k + 1)$, we look at $f\_k(2 k)$:

* if $f\_k(2 k) = 2 k$ then set $g(2 k) = 2 k + 1$ and $g(2 k + 1) = 2 k$,
* if $f\_k(2 k) \neq 2 k$ then set $g(2 k) = 2 k$ and $g(2 k + 1) = 2 k + 1$.

Clearly, for every $k \in \mathbb{N}$, $g$ is different from $f\_k$ because $g(2 k) \neq f\_k(2 k)$. Furthermore, $g$ is computable and it is a bijection because it is its own inverse. QED.
> 9 votes

---
Tags: reference-request, programming-languages, logic, reversible-computing
---


# Question
Title: What are the effects of the alphabet size on construct algorithms for suffix trees?
For what size alphabet does it take longer to construct a suffix tree \- for a really small alphabet size (because it has to go deep into the tree) or for a large alphabet size? Or is it dependent on the algorithm you use? If it is dependent, how does the alphabet size affect Ukkonen's algorithm?

# Answer
> 6 votes
A larger alphabet is usually a drawback. However there are algorithms that can deal with this as long as the alphabet size is $n^{O(1)}$.

Ukkonen's algorithm runs only in $O(n)$ if the alphabet size is a constant but it is $O(n \log n)$ without this assumption. However, there are alternatives. You can compute the suffix-array of a text in linear time with the DC-3 Algorithm. This is a super-cool fancy algorithm that can be implemented in 50 lines of readable C++ code - one of my all-time favorites. If you can compare two characters in constant time and the alphabet size is $n^{O(1)}$, then the DC3 algorithm runs in $O(n)$ time.

Notice that you can get the suffix tree out of the suffix array in $O(n)$ time, when you have the LCP-array. Basically, you compute the Cartesian tree of the LCP-array and use the suffix-array to label the nodes. The LCP-array can be also computed with the DC3-algorithm.

---
Tags: algorithm-analysis, data-structures, strings, efficiency, suffix-trees
---


# Question
Title: One time pad, get plaintext using ciphers encoded with the same key
I'm trying to solve a problem:

I have 11 ciphers encoded with the same key. My aim is to decode target cipher.

If I do xor C1, C2 (**ciphers encoded with the same key**) I do get M1 xor M2 (where M1, M2 are plain text messages).

Please say what to do next. I don't understand how to get plain texts from M1 xor M2

**UPD:** it's a two time pad (i.e. the same key has been use more than one time)

# Answer
So I've passed coursera Scala course and deciced to apply my fresh knowledge. Here is my algo:

1. Xor ciphers with each other and collect xor result for each position. As a result I got a **Map\[Int, List\[String\]\]** where *Int is a position of char* in chiper and *List\[String\] are* all xor results for current position.
2. I have an assumption that if **xor** in **List\[String\]** equals to *UPPER ASCII alpha*, it means that source of this computation was: \*space xor lower\_alpha = UPPER\_alpha\*.
3. I can try to guess key value: **c1** (char from 1st cipher), **c2**(char from 2nd cipher), **xorRes** (c1 xor c2 = xorRes) =\> *c2 xor(c1 xor xorRes)* or *c1 xor(c2 xor xorRes)* = \*lower\_alpha\*.

Here is a part of code:

```
  /**
   * hex1 is a hex from 1st cipher
   * hex2 is a hex from second cipher
   * xor is ahex1 xor hex2
   * @return List with pos of possible key and possible key value else return empty list
   * */
  def getPossibleKey(hex1: String, hex2: String, xor: String, pos: Int): List[(Int, String)] = {
      if(isUpperAphpa(xor)){
          if( isLowerAphpa(xorHexStrings(xorWithSpace(hex1), hex2)) ){
            List( (pos, xorWithSpace(hex1)) )
          }else if( isLowerAphpa(xorHexStrings(xorWithSpace(hex2), hex1)) ){
            List( (pos, xorWithSpace(hex2)) )
      }else{
        List.empty
      }
  }else{
    List.empty
  }

```

}

As a result i got: List\[Int, String\] where String is the most popular lower\_alpha got from *getPossibleKey* function.

Then i just applied collected key to each cipher and started to fix the key. I know that c1 xor m1 = k1 where c1 is a cipher fragment, k1 is a key fragment and m1 is a plain text.
> 1 votes

---
Tags: cryptography, encryption, xor
---


# Question
Title: Solving the big-Oh notation for $T(n) = 2 T(n/2) + O(n)$
> **Possible Duplicate:**
> Solving or approximating recurrence relations for sequences of numbers

I know that the solution for $T(n) = 2 T(n/2) + O(n)$ is $ T(n) = O(n \log(n))$

But how do you get to that point? I don't understand when it says put t into the equation repeatedly until it drops out...

Any help?

# Answer
It means "open" the recursion.

For simplicity - denote $O(n)$ as $c\cdot n$:

$$ \begin{align} T(n) &= 2T(n/2) + cn \\ &= 2(2T(n/4) + cn/2) + cn\\ &= 2 (2 (2T(n/8) + cn/4) + cn/2) + cn\\ & \vdots \end{align}$$

It might give you *intuition*, but it is NOT a *proof*. To prove it, you will need mathematical induction or the master theorem.

---

**Proving with induction** (assuming `O(n)` component is `n` for simplicity):

**Claim**: `T(n) <= n*logn + n`

**Base:**
T(1) = 1 (assumption)
**Assumption:** the claim is correct for all `k < n`.
**Proof:**

```
T(n) = 2T(n/2) + n = (assumption) <= 2* (n/2 * log(n/2) + n/2) + n
     = n*log(n/2) + 2n = n*(log(n)-log(2)) + 2n = (assuming base 2 for log)
     = n*(log(n) -1 ) + 2n = nlogn -n + 2n = n*logn +n

```

**QED**
> 4 votes

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


# Question
Title: How to approach Dynamic graph related problems
I asked this question at generic stackoverflow and I was directed here.

It will be great if some one can explain how to approach partial or fully dynamic graph problems in general.

For example:

* Find Shortest Path between two vertices $(u,v)$ in a undirected weighted graph for $n$ instances, when an edge is removed at each instance.
* Find number of connected components in an undirected graph for n instances when an edge is remove at each instance, etc.

I recently encountered this genre of problems in a programming contest. I searched through the web and I found lot of research papers concerning with dynamic graphs \[1,2\]. I read couple of them and and I couldnt find anything straight forward (clustering, sparsification etc). Sorry for being vague.

I really appreciate if some can provide pointers to understand these concepts better.

---

1. *Dynamic Graph Algorithms* by D. Eppstein , Z. Galil , G. F. Italiano (1999)
2. *Shortest paths on dynamic graphs* by G. Nannicini, L. Liberti (2008)

# Answer
> 12 votes
It's hard to give you concrete techniques because "dynamic" could mean a wide variety of things, and the algorithms/results depend on your model. Below is an overview of the concerns. Here is a paper that gives an overview of some different concerns and models (related to what Peter cited in another answer).

---

For dynamic problems in general, the key issues are:

* do you want an exact solution in all cases, or is approximation allowed?
* do you know anything about what changes will occur (e.g. a probability distribution), or are they all equally likely?
* how does the algorithm learn about the changes?

A typical dynamic model is something like the following:

1. Given a graph, you want to compute some property. You are allowed to compute a solution for the initial graph.
2. You are then told one modification: edge $(e,f)$ is deleted. Compute the property on the new graph using **limited resources**.
3. Repeat 2 for $n$ times.

And here are 3 possible modifications:

* You aren't allowed to compute the complete solution at the beginning because of information / time / space limitations (one example of which is online algorithms)
* In step 2, the algorithm is not "told" the modification, but has to *find* the modification in the graph by querying a data structure or something.
* A distributed model (like Peter discusses in another answer), where the information is discovered locally and the computation/changes are made locally.

Dynamic models are typically interesting because of resource (e.g. time/space) limitations. In step 2, if I was allowed to compute a complete answer (like I did in step 1) then the problem is easy, since it's just a repeated **static** graph problem. We're more interested in the smallest amount of resources necessary to compute the change.

# Answer
> 10 votes
Dynamic graph models have been studied intensively in distributed computing. For distributed algorithms, the computation is structured into rounds and the topology of graphs (=network) might undergo some changes from round to round, which are under control of an adversary. Moreover, every node of the graph runs an algorithm which can send a message to its (current!) neighbors. (This message is the input of the neighbors' algorithm in the next round.) What makes things interesting, is that a node does not "see" the entire graph but only its local neighborhood.

Problems that are considered in these settings are for example *information spreading* where every node in the graph initially holds a token and eventually you want that every node has seen every token. The goal is to design algorithms that achieve this in the smallest number of rounds, using the least number of messages. See \[2\] for a recent survey.

For the non-distributed setting, you might want to look at \[1\], which is an extension of the paper that you've mentioned.

---

\[1\] Aris Anagnostopoulos, Ravi Kumar, Mohammad Mahdian, Eli Upfal, Fabio Vandin: Algorithms on evolving graphs. ITCS 2012: 149-160

\[2\] Fabian Kuhn, Rotem Oshman: Dynamic networks: models and algorithms. SIGACT News 42(1): 82-96 (2011)

# Answer
> 3 votes
Building on @Peter answers (it is a very long comment, so I just included as an answer hopping that someone will benefit from it).

I would suggest the following reference:

Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, Nicola Santoro: Time-varying graphs and dynamic networks. IJPEDS 27(5): 387-408 (2012)

The survey includes a theoretical classification of dynamic networks in distributed settings. For instance, you may find graphs in which the appearance of edges follows a periodic pattern. Or, edges show up at least once in a period $\Delta$. Or, edges that do not follow any periodic patter but they will show up at some point of the algorithm execution. -- and there are about 9 classes in total.

What is really important of this classification is that there are inclusion relationships between the different classes. So if you solve a problem in a certain class, you would solve it in every other class it is included in.

The same authors presented broadcasting algorithms on some of the mentioned graphs. They gave different performance metrics related to time (i.e. different definition of shortest time). In broadcasting, the idea is that each node build a view of the network in the time domain. This is done by repeatedly listening to neighbors, and sending information to neighbors. If assuming periodicity, then a node can tell what is the shortest time-path to another node. It uses this information in routing. More details can be found in:

Arnaud Casteigts, Paola Flocchini, Bernard Mans, Nicola Santoro: Deterministic Computations in Time-Varying Graphs: Broadcasting under Unstructured Mobility. IFIP TCS 2010: 111-124

One of the interesting concepts in dynamic graphs is the concept of journey, which has an analogy to path in static graphs. There is a journey between two nodes $u$ and $v$ if there is a set of edges $\\{(u,x\_1), (x\_1, x \_2), ...., (x \_k, v)\\}$ that will appear in an increasing intervals of time. Note that journey are not symmetric. The existence of a journey between $u$ and $v$ does not necessarily mean that there is a journey between $v$ and $u$.

I attended a lecture by the previous authors. From my understanding, they claim that we are far from being able to deal with dynamic graph algorithms (following the definitions they follow). That we are still in the case of simple classes. In fact, they claim that most of the mobile computing algorithms just assume that their algorithms are too fast to be executed while the network is in transition ! (which i believe I heard a lot) -- Or simply, assume periodicity of edges appearance (see delay tolerant networks etc)

---
Tags: algorithms, data-structures, graphs
---


title: Increasing entropy of random walk

text:
# Question
Title: Increasing entropy of random walk
Let $P$ be a transition matrix of a random walk in an undirected **(may not regular)** graph $G$. Let $\pi$ be a distribution on $V(G)$. The Shannon entropy of $\pi$ is defined by

$$H(\pi)=-\sum\_{v \in V(G)}\pi\_v\cdot\log(\pi\_v).$$

How do we prove that $H(P\pi)\ge H(\pi)$ ?

# Answer
Is this even true? Consider an undirected graph which is a star. That is, a central vertex $V\_0$ is connected to all other vertices $V\_1, V\_2, \dots, V\_{n-1}$, and there are no other edges in the graph. Then, if you start with an equal distribution on $V\_1, V\_2, \ldots, V\_{n-1}$, after one step all the weight is on the central vertex $V\_0$. So in one step the entropy has gone from $\log (n-1)$ to $0$.
> 8 votes

---
Tags: entropy, random-walks
---


title: Are monoids useful in optimization?

text:
# Question
Title: Are monoids useful in optimization?
Many common operations are monoids. Haskell has leveraged this observation to make many higher-order functions more generic (`Foldable` being one example).

There is one obvious way in which using monoids can be used to improve performance: the programmers is asserting the operation's associativity, and so operations can be parallelized.

I'm curious if there are any other ways a compiler could optimize the code, knowing that we're dealing with a monoid.

# Answer
The compiler can optimize exponentiation with monoids. Let $\oplus$ be a binary operator calculateable in constant time such that $\oplus$ and $a\_1, a\_2, ... \in A$ form a monoid. Then the operation

$$\bigoplus\_{\[1..n\]} a\_k = \underbrace{a\_k \oplus a\_k \oplus \dots \oplus a\_k}\_{\text{$n$ times}}$$

which usually takes $\cal O(n)$ time can be evaluated with the square and multiply algorithm in only $\cal O(\log n)$ time if the compiler knows that $\oplus$ obeys the monoid laws.
> 7 votes

# Answer
If you are in the constant folding/constant propagation step, whenever you come up with the identity of the monoid, you can just ignore it if it's multiplying other non-constant expressions.
> 0 votes

---
Tags: optimization, compilers, category-theory
---


title: Processes and Segmentation

text:
# Question
Title: Processes and Segmentation
The following problem was on my final and in `Gate 2006`, but I don't understand how to solve it:

Different methods of memory management have different overheads:

* The paging method for memory management uses two-level paging, and its storage overhead is $P$.
* The storage overhead for the segmentation method is $S$.
* The storage overhead for the segmentation and paging method is $T$.

> What is the relation among the overheads in the concurrent execution of the processes below?
>
> (a) $P \< S \< T \hspace{2em}$
> (b) $S \< P \< T\hspace{2em}$
> (c) $S \< T \< P\hspace{2em}$
> (d) $T \< S \< P$

```
Process    Total Size (in KB)    Number of segments
 P1              195                    4
 P2              254                    5
 P3               45                    3
 P4              364                    8

```
* The page size is 1 KB.
* The size of an entry in the page table is 4 bytes.
* The size of an entry in the segment table is 8 bytes.
* The maximum size of a segment is 256 KB.

# Answer
> 4 votes
I am guessing that overheads P, S, and T exclude per page/segment overheads and are per-process overheads (if they are per-system overheads, the adjustments are obvious), so the overhead of each process would be P + page\_count * 4 bytes for paging, S + segment\_count * 8 bytes for segmentation, and T + segment\_count * 8 bytes + page\_count * 4 bytes for segmentation and paging.

(The inclusion of a maximum segment size is confusing since insufficient information is provided to determine if any of the 8 segments in process P4 are larger than 256 KB, though at most one segment can be. Since the mean segment size is significantly less than the maximum allowed size, I just assume that no segment needs to use two segment table entries.)

It might help clarify the equations to substitute A \< B \< C with A = B + k1 = C + k1 + k2 (where k1 and k2 are greater than zero). It should then be straightforward to determine what values of k1 and k2 are needed for equality and so derive the conditions under which each memory management method has greater overhead (with negative values for k1 or k2, of course, being impossible).

---
Tags: operating-systems, memory-management, storage, paging
---


title: Advantages of amortized analysis

text:
# Question
Title: Advantages of amortized analysis
I understood what amortized analysis does, but can anyone tell me what is the main purpose of this kind of analysis?

What I understood:

Let say we have 3 three operations a,b,c used 1,2 and 3 times to achieve d. Based on aggregate analysis a,b and c are used 2 times each. Is this correct?

I am trying to understand the advantages of this in CLRS but I am completely lost. For example in dynamic programming we save the answers to sub problems in tables which helps us reduce the running time(lets say from exponential to polynomial). But I am unable to get a complete picture of amortized analysis.

# Answer
> 13 votes
Amortised analysis is a tool to get more useful results than "naive" worst-case analysis. Especially in the realm of advanced data structures, operations can be cheap most of the time but expensive in rare cases; worst-cases analysis yields only the latter case as characteristic of the data structure. Dynamic arrays, splay trees and some flavors of hash tables are among the more popular examples.

For many purposes, that is too pessimistic. We don't actually *need* that every operation is fast¹; we execute lots and lots of operations (e.g. during an algorithm) and we want the *total* runtime to be small. That is what amortised analysis looks at.

Be careful not to confuse amortised analysis with average-case analysis. The former is still considering the worst case; it only sums over time and spreads the cost evenly; you get for one operation its share of the worst-case total cost. On the other hand, average-case assumes a probability distribution over inputs and/or the sequence of operations, and yields the *expected* time per operation, which is (by definition) its share of the expected total cost.

---

1. Real-time applications are a notable exception.

# Answer
> 10 votes
Consider the `std::vector` container from the STL, together with it's appending operation, `push_back()`. This operation has amortized running time $O(1)$.

Why? `std::vector` implemented as an array which can dynamically grow, if more space is needed. The *strategy* it uses for resizing is simple: it doubles it's size whenever you try to `push_back` a new element to a `vector`that is full. After that resizing operation, appending elements can be done in constant time: they are just inserted into the array "behind" the last element.

So, if you are growing a `std::vector` object by calling `push_back` very often, fewer and fewer growing operations need to be done, because of that exponential growing strategy: Eventually, the likelihood that your insertion operation is running in constant time converges to one.

Long story short: you do amortized analysis to determine the "average" complexity of your algorithm, given the case that it performs "usually" well, but not always. Like e.g. inserting elements at the end of a `std::vector`.

---
Tags: algorithm-analysis, proof-techniques, amortized-analysis
---


# Question
Title: Show that a language belongs to the polynomial hierarchy
I think the following exercise is to "warm up", but nevertheless it's quite difficult for me:

> Let $k \in \mathbb{N}$ and let $L \in \Sigma\_k$. Show that also $L^{\*} \in \Sigma\_k$.

The following details from my lecture notes seem to be useful:

Notation. Let $n \in \mathbb{N}$.

We write $\exists\_n y. \varphi(y)$ for $\exists y \in \Sigma^{\*}.|y| \le n \wedge \varphi(y)$.

We write $\forall\_n y. \varphi(y)$ for $\forall y \in \Sigma^{\*}.|y| \le n \Rightarrow \varphi(y)$.

Theorem.

$L \in \Sigma^P\_i \Leftrightarrow$ there is a language $A \in P$ and a polynomial $p$ so that: $x \in L \Leftrightarrow \exists\_{p(|x|)}y\_1 \forall\_{p(|x|)}y\_2 \exists\_{p(|x|)}y\_3 .../\forall\_{p(|x|)}y\_i (x,y\_1,y\_2,...,y\_i) \in A$

Unfortunately I don't see the solution of the "puzzle". Can somebody please help me a little bit (despite the fact that it's weekend)?

# Answer
> 4 votes
Let me assume your are familiar with the oracle-version of the polynomial hierarchy. Thus, if $L\in \Sigma\_k$, then there exists a (non-deterministic polytime) Turing machine $M$ with oracle $\Sigma\_{k-1}$.

To show that $L^\*$ is also in $\Sigma\_k$ we explain how one could build a new non-deterministic polytime Turing machine $M^\*$ with oracle $\Sigma\_{k-1}$ that accepts $L^\*$. The key idea is, that we use the (simulation) of $M$ as a sub-module for $M^\*$.

The machine $M^\*$ works as follows. It guesses a partition of the input $w$ into some words $u\_1u\_2\cdots u\_k$. Then it runs the simulation for $M$ for every $u\_i$. If the simulation verifies that **all** $u\_i\in L$ then $M^\*$ accepts, otherwise it rejects. Clearly $M^\*$ accepts $L^\*$ and uses only the oracle $\Sigma\_{k-1}$. What is left to check is if $M^\*$ runs in polytime. The running time of $M^\*$ is dominated by $$t\_M(|u\_1|)+t\_M(|u\_2|)+\cdots+ t\_M(|u\_k|)\le t\_M(n)+t\_M(n)+\cdots+ t\_M(n)\le n \cdot t\_M(n),$$ for $n=|w|$. Since $t\_M(n)$ is a polynomial, we have that $n\cdot t\_M(n)$ is a polynomial as well.

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


# Question
Title: Notations around the polynomial hierarchy
I am new to "Computational Complexity" and therefore I have enough problems with some exercises like the following one:

> Remember: $\text{PH} := \bigcup\_{i} \Sigma\_i$
>
> Show:
>
> $\bullet \bigcup\_{i}(\Sigma\_i \cup \Pi\_i \cup \Delta\_i) = \bigcup\_{i}\Sigma\_i = \bigcup\_{i}\Pi\_i = \bigcup\_{i}\Delta\_i$
>
> $\bullet \forall k \in \mathbb{N} (\Sigma\_k = \Pi\_k \Rightarrow \text{PH} = \Sigma\_k)$

I have tried to make myself familiar with Polynomial hierarchy, but on the one hand I don't understand the meaning of the symbols $\Delta, \Sigma, \Pi$ and on the other hand I don't know how to solve the actual exercise.

Can somebody give me some help, please?

# Answer
> 2 votes
$\newcommand{\P}{\mathsf{P}}\newcommand{\PH}{\mathsf{PH}}$ $\newcommand{\SUM}\[1\]{\Sigma\_{#1}^{\P}}\newcommand{\PROD}\[1\]{\Pi\_{#1}^{\P}}$ $\newcommand{\DELTA}\[1\]{\Delta\_{#1}^{\P}}$ $\newcommand{\NP}{\mathsf{NP}}\newcommand{\coNP}{\mathsf{coNP}}$ From the comments:

> Why is $\SUM{1} = \NP$?

Recall the definition of $\NP$ using certificates/proofs:

> A language $L$ is in $\NP$ if there exists a poly-time TM $M$ and a polynomial $q$ such that $$x \in L \iff \exists u \in \\{0,1\\}^{q(|x|)}\ M(x, u) = 1$$

This is also exactly the definition for $\SUM{1}$. In the case of $\NP$ it is a single existential ($\exists$) quantifier. Now, the negation of existential quantifier is the universal quantifier ($\forall$). If we swap out the quantifiers in the certificate definition of $\NP$ we have $$x \in L \iff \forall u \in \\{0,1\\}^{q(|x|)}\ M(x, u) = 1$$ which is exactly $\coNP$ (and denoted in the hierarchy as $\PROD{1}$)! We see that $\PH$ is just a generalization of this, by allowing more (alternating) quantifiers.

For the first bullet:

> $\bigcup\_{i}(\SUM{i} \cup \PROD{i} \cup \DELTA{i}) = \bigcup\_{i}\SUM{i} = \bigcup\_{i}\PROD{i} = \bigcup\_{i}\DELTA{i}$

Sketch: It is straightforward to show that $\SUM{i} \subseteq \PROD{i+1} \subseteq \SUM{i+2}$. The reasoning is that you can simply "ignore" the leading quantifiers in the verifying TM. Likewise, we see $\SUM{i} \subseteq \DELTA{i+1} \subseteq \SUM{i+1}$. Again, this can be explained due to the fact that both $\DELTA{i+1}$ and $\SUM{i+1}$ have oracle access to $\SUM{i}$ with the difference being that $\SUM{i+1}$ is an $\NP$-based machine whereas $\DELTA{i+1}$ is a $\P$-based machine.

With the subset relation in-hand, we see that a union over all integers will cover all cases.

Now for your second bullet:

> $\forall k \in \mathbb{N}\ \ \SUM{k} = \PROD{k} \Rightarrow \PH = \SUM{k}$

Proof: This can be shown by induction on $k$. For our base case let $k = 1$ and observe that if $\SUM{1} = \PROD{1}$ then a collapse occurs. To see this, let $Q\_1, \cdots, Q\_i$ be the alternating quantifiers for some level $i$ in the hierarchy. Since $\SUM{1} = \PROD{1}$, we can replace each universal quantifier in the sequence with an existential quantifier resulting in $\exists u\_1, \cdots, \exists u\_i$. But by definition of the quantifiers, we can reduce this to a single $\exists \langle u\_1, \cdots, u\_i \rangle$ which is exactly $\SUM{1}$.

Now assume this holds for all values less than $k$. Given level $\SUM{k}$ we can decompose its quantifiers into two parts, the initial $\exists u\_1$ and the following alternating sequence $\forall u\_2, \cdots, Q\_{k} u\_{k}$, where $Q\_{k}$ is either $\exists$ or $\forall$ depending on whether $k$ is odd or even. Observe this sequence is exactly $\PROD{k-1}$ which by our hypothesis is equal to $\SUM{k-1}$. By substituting and combining the initial term we have $$\exists \langle u\_1, u\_2 \rangle, \cdots, Q\_{k} u\_{k}$$ which is really only $k-1$ terms! Therefore a collapse occurs.

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


title: Bellman-Ford variation

text:
# Question
Title: Bellman-Ford variation
I have a "smarter" version of Bellman-Ford here; this version is more clever about choosing the edges to relax.

```
//Queue Q; source s; vertices u, v; distance to v d(v)
Q ← s // Q holds vertices whose d(v) values have been updated recently.
While (Q !empty) {
  u ← Dequeue(Q)
  for each neighbor v of u {
    Relax(u, v)
    if d(v) was updated by Relax and v not in Q
      Enqueue(v)
  }
}

```

But, can anyone explain why this improved version correctly finds the shortest path from $s$ to every other vertex in a directed graph with no negative cycles?

Also, what is the *worst-case* runtime if every shortest path uses at most $v$ edges?

# Answer
This is precisely Moore's 1957 formulation of what is now more commonly known as the Bellman-Ford algorithm.

## **Why does it work?**

Moore's algorithm is a special case of Ford's more general relaxation strategy for computing single-source shortest paths:

```
while any edge is tense
    relax any tense edge

```

This generic algorithm will always halt after a finite number of relaxation steps with a shortest path tree, unless some negative-weight cycle is reachable from the source vertex (in which case, there is *always* at least one tense edge, so the algorithm will never halt).

For Moore's algorithm, it is not hard to the following observation by induction:

> Every tense edge leaves a vertex that is in the queue.

If fact, this lemma holds if we replace the queue with *any* other data structure that supports the operations "insert this" and "give me something". (For example, using a priority queue gives us Dijkstra's algorithm!) The algorithm halts when the data structure is empty. Thus, by the previous lemma, when the algorithm halts, there are no tense edges, so we have a shortest-path tree.

## **What is the running time?**

We can naturally divide the execution of the algorithm into *phases* by adding an artificial token to the queue immediately after the source vertex, just before the main loop begins. Each phase ends when we dequeue the token; if the queue is not empty, we enqueue the token again and start the next phase. If the queue is empty after we dequeue the token, the algorithm ends.

Each vertex in the graph is dequeued at most once in any phase. (Here I'm assuming that enqueuing a vertex that is *already* in the queue does not actually change the queue.) Thus, each edge in the graph is relaxed at most one in any phase. So each phase runs in $O(m)$ time.

Let $dist\_i(v)$ denote the distance value stored in vertex $v$ after $i$ phases. Initially, we have $dist\_0(s) = 0$ and $dist\_0(v) = \infty$ for all $v\ne s$. It is easy to prove by induction that

> $dist\_i(v)$ is at most the length of the shortest walk from $s$ to $v$ that uses at most $i$ edges.

This lemma immediately implies that the algorithm ends after at most $n-1$ phases (unless there is a negative cycle). So altogether the algorithm runs in $O(mn)$ time.

For more details, see my lecture notes, or better yet, Bob Tarjan's excellent monograph *Data Structures and Network Algorithms*. I believe Tarjan was the first to observe that Moore's algorithm is equivalent to Bellman-Ford.
> 12 votes

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


title: reducing subset-sum to partition

text:
# Question
Title: reducing subset-sum to partition
> **Subset-sum:** Given a list of numbers, find if a non-empty sublist has sum 0 (there's a variation where we want sum=k instead of 0, but 0 is easier for analysis)
>
> **Partition:** Given a list, can it be partitioned into two non-empty sublists with equal sum?

I want to reduce subset-sum to partition. The reductions I found so far are same as this one but it has following faults :

1. For $B=0$, you can always partition $L'$ into $\\{2S-0\\}$, $\\{S+0\\} U L$.
2. It supposes $2S-B$ and $S+B$ have to go to different partitions! You could have both of them in same partition along with elements that sum to $-S$, hence total sum $= 2S$ as needed.

# Answer
1. You're absolutely right that this partition always occurs. If you consider what this means in terms of the corresponding subset, you'll find that this indicates that the empty set (which is always a subset) has sum 0. In fact, this indicates the there is always a solution to subset sum when the target is 0, which is exactly as expected. It turns out fixing the target sum to 0 does not just make the problem easier to discuss, it makes it easier in a complexity sense ($O(1)$ by outputting YES immediately).
2. You're right here too. There is a formulation of subset sum where the input is a list of positive integers, and I think the reduction you are reading was from that language. The goal was to have our added elements be large enough that they cannot both go in the same part. To patch that up, we can use the sum of the absolute values. This actually shows some of the structure of the proof better, because $2S$ was actually $S +$ some-large-enough-number-for-which-$S$-will-suffice-but-so-do-larger-numbers.

At this point I'm copy-pasting from the linked post and just editing to handle negatives:

> Let $(L,B)$ be an instance of subset sum, where $L$ is a list (multiset) of numbers, and $B$ is the target sum. Let $S = \sum L$ and choose $S' \> \sum\_{l \in L} |l|$. Let $L'$ be the list formed by adding $S'+B,S'+S-B$ to $L$.
>
> (1) If there is a sublist $M \subseteq L$ summing to $B$, then $L'$ can be partitioned into two equal parts: $M \cup \\{ S' + S-B \\}$ and $L\setminus M \cup \\{ S'+B \\}$. Indeed, the first part sums to $B+(S'+S-B) = S'+S$, and the second to $(S-B)+(S'+B) = S'+S$.
>
> (2) If $L'$ can be partitioned into two equal parts $P\_1,P\_2$, then there is a sublist of $L$ summing to $B$. The sum of the two new elements is $(S'+B)+(S'+S-B) = 2S'+S$. All subsets $A \subset L$ have $\left|\sum A\right| \< S'$, so it is not possible that $\\{S'+S-B\\} \cup \\{ S'+B \\} \cup A$ has sum $S' + S$ (it is always greater). So the two new elements belong to different parts. Without loss of generality, $S'+S-B \in P\_1$. The rest of the elements in $P\_1$ belong to $L$ and sum to $B$; they do not include a new element, so they are a solution to subset sum.
> 4 votes

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


title: Optimizing a strictly monotone function

text:
# Question
Title: Optimizing a strictly monotone function
I am looking for algorithms to optimize a strictly monotonic function $f$ such that $f(x) \< y$

$f : \[a,b\] \longrightarrow \[c,d\] \qquad \text{where } \[a,b\] \subset {\mathbb N}, \[c,d\] \subset {\mathbb N}$
such that $\arg\max{\_x} f(x) \< y$

My first idea was to use a variant of binary search, pick a point $x$ in $\[a,b\]$ at random; if $f(x) \> y$ then we eliminate $\[x, b\]$, and if $f(x) \< y$ we eliminate $\[a, x\]$. We repeat this procedure until the solution is found.

Do you have any other ideas to maximize the function $f$ ?

# Answer
Given the discrete intervals $\[a,b\]\subset\mathbb{N}$ and $\[c,d\]\subset\mathbb{N}$, we might be able to do slightly better than binary search using the midpoint without utilizing gradient descent.

Instead, we could use binary search with $x=a+\lfloor\frac{y-c}{d-c}(b-a)\rfloor$, which corresponds to the below intersection of the dotted purple line denoting $y$ and the line from $f(a)=c$ to $f(b)=d$.

The red and blue lines represent the extremes of strictly monotonic functions. When $f$ is linear, this would immediately find the closest $x$ (which is a big improvement over binary search with the midpoint). Without additional information, I think linearity is the best assumption you can make; there are as many concave functions as convex functions, as well as functions that switch.

One justification for not using gradient descent is if an array $\[a,a+1,\dots,b\]$ is simply mapped to another array of the same size but different range of data $\[c,d\]$, which is randomly chosen (and sorted).

Otherwise, you could use Newton's method as suggested by Dave Clarke or gradient descent as suggested by Raphael, which I just learned are different.
> 5 votes

---
Tags: algorithms, optimization
---


title: Gödelization in Turing Machine

text:
# Question
Title: Gödelization in Turing Machine
I was looking at Gödelization in Theory of Computation course. I could understand the Gödel numbering concepts, but couldn't understand its importance in Theory of Computation. Could anyone please point to some good materials or point out its importance.

# Answer
> 19 votes
Gödel numbering in computer science means more or less "source code" and "data in binary format", so I hope the significance of this should be obvious if I can convince you that this really is so.

Before modern computers came into existence, people made single-purpose computing devices (I am telling you a story, not a history), for example someone made a machine for calculating $arctan$, and someone else made a machine for calculating the Bessel function. Turing's original insight was that we only had to build one machine (the *universal* one), which took as input the description of any machine and simulated it. But what is a "description of a machine"? An engineer might think of circuit designs and assembly instructions. But that is very complicated and not easily presented to a machine. And perhaps ever more complicated machines require ever more complicated descriptions?

We need a way of describing machines that is as simple as possible. Here Gödel's idea was important: he showed some years before Turing that all sorts of things in logic (formulas, proofs) could be encoded with numbers, and then manipulated within arithmetic. We can do a similar trick with Turing machines: encode the program, the current state, and the contents of the tape used so far, with a string of symbols on a tape (for examples $0$'s and $1$'s), and then manipulate the string with a Turing machine.

In practice we do not write down sequences of $0$'s and $1$'s when we program. We use another layer of encoding and write "source code" which is translated to $0$'s and $1$'s (the "machine code") by compilers. But in fact early computer scientists *did* write down $0$'s and $1$'s directly by flipping switches. That was Gödelization in its pure form.

In practice we represent programs and data in a variety of formats known as `.java`, `.py`, `.mp3`, `.jpg`, etc. In logic and theory of computing people prefer to stick with the good old numbers because they are more easily manipulated within mathematics.

Nowadays everybody knows that "computers do everything in terms of $0$'s and $1$'s". This fact has become so familiar that it is hard to appreciate its originality. Many years ago, when no modern computers existed, it was far from obvious that machines, text, music, pictures and movies could all be encoded with numbers, or sequences of $0$'s and $1$'s.

---
Tags: formal-languages, turing-machines
---


title: #P complexity reduction

text:
# Question
Title: #P complexity reduction
We know that counting the number of Hamiltonian paths is in $\\#\mathsf{P}$.

So, what complexity (counting version) class would the counting the number of Hamiltonian paths that have two or three particular vertexes in a graph be in?

Also, what would be like if counting the number of hampaths that have two or three particular vertexes in particular place - so, for example, calculating the hampath that has vertex 3 as the second place from starting point and so on?

# Answer
> 2 votes
Just an extended comment on the second part of the question (if I understood it correctly).

The problem is a special case of the general version; so if you allow $0$ "fixed" points (a *fixed point* is a point that must be in a particular position in the Hamiltonian paths), then there is an immediate reduction from the problem of counting Hamiltonian paths.

If your problem says that at least $k$ points must be fixed, then this reduction should work: given a graph $G$ and two vertices $s$ and $t$, and $e\_1,e\_2,...,e\_m$ are the edges from $s$; then for each $e\_i$ *split* it in $k+1$ pieces adding $k$ nodes, and solve your problem fixing the first $k$ nodes (and the number returned will be equal to the number of Hamiltonian paths from $s$ to $t$ in $G$ that start with $e\_i$).

At the end the total number of Hamiltonian paths in the original $G$ is the sum of the number Hamiltonian paths returned by your algorithm fixing the first $k$ points in the splitted $e\_1, e\_2, ... e\_m$.

---
Tags: complexity-theory
---


# Question
Title: Optimization-factoring $\le_p$ Decision-factoring
Optimization factoring:
Input: $N\in \mathbb{N}$
Output: All prime factors of $N$

Decision factoring:
Input: $N, k\in \mathbb{N}$
Output: True iff $N$ has a prime factor of at most $k$

How can I solve the optimization problem in polynomial time if the decision problem is polynomially solvable?

# Answer
You need to get an algorithm polynomial in $n$ where $n = \log N$ is the size of your input, i.e. the binary representation of $N$ (naive factorization algorithms are $O(N^2)$ which is of course exponential).

Given `dec(k, x)` solving the decision factoring problem, let's write a procedure to find the smallest prime divisor of $x$ using a dichotomy to keep logarithmic the number of steps.

```
sp(x):
  min = 2
  max = x - 1
  while (max >= 1 + min):
    k = floor ((min + max) / 2)
    if dec(k, x):
      max = k
    else:
      min = k + 1
  if x % (min + 1) == 0:
    return (min + 1)
  else if x % min == 0:
    return min
  else:
    return 1

```

The procedure above calls `dec` $O(\log x)$ times and find the smallest prime number that divides $x$, or `1` if it does not exist. Now we can easily define the following factoring function:

```
factor(x):
  p = sp(x)
  if (p == 1):
    print x
  else:
    print p
    factor(x / p)

```

Factor is called less than $\log x$ times (since $p ≥ 2$) so the number of calls to `dec` is bounded by $\log^2 x$ times on values less than $x$. If the complexity of `dec` is polynomial, let's say bounded by an increasing $P(n)$, then the complexity of `factor` is still polynomial, bounded by $n^2P(n)$.
> 4 votes

# Answer
You can use the decision version to search for the factors of $N$ by manipulating $k$. Given the input to the optimization version, you can ask if it has a prime factor less than or equal to $2$, $3$, ..., $\sim\sqrt{N}$ . Say you get your first answer at $k\_{1}$, then because it didn't say yes before, $k\_{1}$ must be a factor of $N$, so we can note this down, and start again from $\frac{N}{k\_{1}}$.

Ideally we'd only test the primes up to $\sim\sqrt{N}$, but it doesn't matter if we test the composites as well, as we'll hit their prime factors first, so we'll never get a Yes answer for a composite.

Then for each individual search we're solving at most $\sqrt{N}$ decision problems, and at each step (until we're done) we're reducing $N$ to less than $\frac{N}{2}$, so if we can solve the decision problem in PTIME (say $O(n^{c})$ for some constant $c$), we can do the whole thing in something roughly like $O(n^{c+1/2}\log n)$.
> 2 votes

---
Tags: optimization, reductions, factoring
---


# Question
Title: Viterbi training vs. Baum-Welch algorithm
I'm trying to find the most probable path (i.e., sequence of states) on an hidden Markov model (HMM) using the Viterbi algorithm. However, I don't know the transition and emission matrices, which I need to estimate from the observations (data).

To estimate these matrices, which algorithm should I use: the Baum-Welch algorithm or the Viterbi Training algorithm? Why?

In case I should use the Viterbi training algorithm, can anyone provide me a good pseudocode (it's not easy to find) ?

# Answer
From my comment:

This answer on crossvalidate.SE may be of use. I wasn't aware of viterbi-training. I have only used BW or other EM-based methods in the past. Based on the answer in the link, I think BW would be the most useful. It seems Viterbi-Training gives no guarantee on bounds. However, the latter does have useful application if BW takes far too long to compute.
> 1 votes

---
Tags: algorithms, hidden-markov-models
---


# Question
Title: What is the time complexity of the following program?
Please help me calculate the time complexity of the following program.

```
int fun (int n) {
  if (n <= 2)
   return 1;
  else
   return fun(sqrt(n)) + n;
}

```

Please explain.

There were four choices given.

1. $\Theta(n^2)$
2. $\Theta(n \log n)$
3. $\Theta(\log n)$
4. $\Theta(\log \log n)$

# Answer
> 6 votes
The running time of the function on an input $n$ can be expressed as: $$T(n) = T(\sqrt n) + \mathcal{O}(1)$$

which implies the running time of the function and the number of recursions differ only by a constant.

The recursive chain ends when $n$ has been reduced to some value $k$, where $k \le 2$. The number of recursions, $r$, can be expressed as: $$k^{2^r} = n \implies r = \log\_2 \log\_k n$$

It follows that the running time is then:

$$\Theta(\log\_2 \log\_k n) = \Theta(\log \log n)$$

# Answer
> 4 votes
The time complexity here is proportional to the depth of the recursion tree. At each level, the square root of $n$ is taken. So how many times can the square root be taken before we get 2?

This can be calculated in the same way shown at this post.

> $n = 2^{\log n}$

After taking the square root $k$ times, $n$ is equal to:

> $2^{\log n/2^{k}}$

This is equal to 2 when:

> $2^{\log n/2^k} = 2$
>
> $\log n/2^k =1 $
>
> $\log n = 2^k$
>
> $\log\log n = k$

So the time complexity is $\Theta(\log \log n)$.

---
Tags: algorithm-analysis, runtime-analysis, landau-notation
---


# Question
Title: Given a truth table, force a contradiction
Suppose I have a formula, and a lying witness is attempting to make it evaluate to False.

> Given a truth table $c(F\_1,…, F\_n)$, how could you force a lying witness to contradict herself?

A contradiction is simply when the witness's statements are logically impossible; i.e. that $x\_1,x\_2$ are each True, but $x\_1 \space AND\space x\_2$ is False.

* How can I characterize the set of all formula for which I force the witness to contradict herself?
* What complexity class does this problem fall in?

# Answer
It appears the question that you are asking is:

> What is the set of formula for which a witness attempting to prove the formula false will always fail?

That is, you are asking whether a formula is **valid**: whether it is true for every interpretation. A formula is valid if and only if its negation is unsatisfiable, which according to this resource is **Co-NP complete**.
> 1 votes

---
Tags: complexity-theory, computability, np-complete, closure-properties, decision-problem
---


# Question
Title: Scala as a language for Generic Programming
I posted the same Q at programmers.SE, but nobody really helps.

In the paper “An Extended Comparative Study of Language Support for Generic Programming” by Garcia et al. an interesting comparison of programming languages features for generic programming is given:

with the brief explanation of terminology:

Can anyone assess Scala programming language support for generic programming in a view of this framework? I.e. add a column in the first table with explanations and examples if possible.

# Answer
> 1 votes
Exact answer is given on p. 17 of “Type classes as Objects and Implicits” by Oliveira et al.

---
Tags: programming-languages, typing
---


# Question
Title: Rechecking contiguous characters (as in run length encoding)
So I have a fun little problem. It will take a minute to explain, but the situation is conceptually very simple. Suppose you have a string of characters, which is interpreted as groups of one or more contiguous characters. This is for run length encoding or something. For example:

> zz22344a is two z's, two 2's, one 3, two 4's, and one a.

Once you've parsed the original string, you retain only the characters and sizes in an array.

```
struct Run { char whatChar; int length; }

Run* runArrayVar;

void parseIntoArray(char* sourceChars);   // creates runArrayVar

```

I won't put the implementation of parseIntoArray() here because it's trivial to do with a loop, but I'll assume that arrays are null-terminated, although in the problem they don't have to be. Here is the problem part. I want to implement a function like this:

```
void alterArray(char* newSourceChars, int changedOffset,
                int changedLength, int changedCharsAdded);

```

This responds to a change in the source text. Included is the new text, the beginning and length of the altered area, and for reference, how many extra characters were added. For example, take the original `zz22344a`. If the substring `223` was pasted over with `23_44`, then the new string would be `zz23_4444a` and the new array would be two `z`'s, one `2`, one `3`, one `_`, four `4`'s, and one `a`.

I could get the new `runArrayVar` naively by just calling `parseIntoArray`, but I want to be less naive: I want to step through and only change the parts of `runArrayVar` that need to be changed. Finding the first changed element is pretty easy; skip through until you find one that overlaps `changedOffset` (you need to test one extra char after the element). After that it gets dicey and I can't figure it out. Take the above example:

`zz` needs to be re-checked because the character right after it might have been changed to a `z`. It wasn't, so it remains `zz`. Now we're at offset 2.

`22` is rechecked, and it turned into 2. So OK. Now we're at offset 3.

`3` is rechecked, and it's the same. So we're at offset 4.

`44` is rechecked, and apparently turned into an underscore. So we're at offset 5.

At this point we're still looking at characters that have changed, and we're at `4444`. According to the previous logic, `a` turned into `4444`. OK. Now we're past the characters that have changed, and our array still has an element with one a left over. I can keep parsing and terminate the array when I hit the end of the string, but suppose that `a` was actually a million `a`s in a row. The algorithm should be able to reason that it doesn't have to do any more work and terminate. If you look at the example, there is nothing you could have changed that particular section into that would influence the `a`.

This is difficult. I've tried it a lot of different ways and I can't figure out exactly when the algorithm needs to terminate. Please let me know if you have any ideas!

# Answer
If a `Run` only retains characters and sizes in an array, it seems as though you only need to find the indices corresponding to `changedOffset` and `changedOffset + changedLength`, and then potentially change the sizes of the characters in the indices to the right and left by simple addition. That is, if you have an array of `Runs`: $$\[(x,1),(y,2),(a,2),(b,1),(c,1),(z,2),(x,1)\]$$ for `alterArray("ac_zz",3,4)`, it is first determined that the $a$ and $c$ are the beginning and ending characters (the $b$ is eliminated). This is done by simply adding: $1+2=3$ (from the $1x$ and $2y$) and $2+1+1=4$ (from the $2a,1b,$ and $1c$).

Then you check whether either side has to be combined: on the left side, the $y$ is not affected; on the right side, the $z$ is affected and so we add $2+2=4z$. The $x$'s are never checked.
> 1 votes

---
Tags: strings, substrings
---


# Question
Title: NP-Hard problems which are not NP-Complete
1. Is it always true that a problem which is ${\sf NP}$-hard but not ${\sf NP}$-complete is an optimization problem such as **Minimum-Vertex-Cover** and many others.
2. Is it always true that a ${\sf NP}$-complete problem is always a decision problem such as vertex cover of size $k$, independent set of size $k$ and many others.

# Answer
1. No. E.g. the Halting problem is a decision problem which is NP-hard but not in NP and therefore not NP-complete.
2. In normal usage yes, because an NP-complete problem must be in NP and NP is a class of decision problems. But see Decision problems vs “real” problems that aren't yes-or-no.
> 10 votes

---
Tags: complexity-theory, terminology, np-complete, np-hard, decision-problem
---


# Question
Title: Bellman-Ford algorithm - Why can edges be updated out of order?
The Bellman-Ford algorithm determines the shortest path from a source $s$ to all other vertices. Initially the distance between $s$ and all other vertices is set to $\infty$. Then the shortest path from $s$ to each vertex is computed; this goes on for $|V|-1$ iterations. My questions are:

* Why does there need to be $|V|-1$ iterations?
* Would it matter if I checked the edges in a different order?
Say, if I first check edges 1,2,3, but then on the second iteration I check 2,3,1.

MIT Prof. Eric said the order didn't matter, but this confuses me: wouldn't the algorithm incorrectly update a node based on edge $x\_2$ if its value was dependent on the edge $x\_1$ but $x\_1$ is updated after $x\_2$?

# Answer
Consider the shortest path from $s$ to $t$, $s, v\_1, v\_2, \dots, v\_k, t$. This path consists of at most $|V|-1$ edges, because repeating a vertex in a shortest path is always a bad idea (or at least there is a shortest path which does not repeat vertices), if we do not have negative weight cycles.

In round one, we know that the edge $(s, v\_1)$ will be relaxed, so the distance estimate for $v\_1$ will be correct after this round. Note that we have no idea what $v\_1$ is at this point, but as we've relaxed *all* edges, we must have relaxed this one as well. In round two, we relax $(v\_1, v\_2)$ at some point. We still have no idea what $v\_1$ or $v\_2$ are, but we know their distance estimates are correct.

Repeating this, after some round $k+1$, we have relaxed $(v\_k, t)$, after which the distance estimate for $t$ is correct. We have no idea what $k$ is until the entire algorithm is over, but we know that it will happen at some point (assuming no negative weight cycles).

So, the crucial observation is that after round $i$, the $i$-th node of the shortest path must have its distance estimate set to the correct value. As the path is at most $|V|-1$ edges long, $|V|-1$ rounds suffices to find this shortest path. If a $|V|$th round still changes something, then something weird is going on: all paths should already be 'settled' to their final values, so we must have the situation that some negative weight cycle exists.
> 15 votes

# Answer
The longest a path can be without any cycles is `|V|`. We start with a source, so we already have a path of length 1, so we need `|V| - 1` more nodes to get the longest path.

The order doesn't matter because every order will maintain the invariant: after `n` iterations, the value for each node is less than or equal to the cost of the minimum cost path from `s` to the node containing at most `n` edges.

If, at the beginning of an iteration, the cost is correct up to `n` nodes, then at the end of the iteration it is correct up to `n+1` nodes. A reordering can cause some nodes to have a lower cost before they would normally be updated, but they would eventually be updated anyway.
> 3 votes

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