# Question
Title: Error propagation when compiling a compiler
Just for curiosity, I recently heard that many compilers are written in its own language. For example, gcc is partially written in C. And old version of compiler is used to compile the new version of compiler.

Then I have a question, if there is a bug in the compiler, and you fix the bug in the source code and use the previous buggy compiler to compile a new compiler, how can you ensure that the bug in the new compiler is fixed?

Theoretically, if you have a very buggy old compiler, and now you have a new, bug-free version of the compiler source code, would the compiler converges to a bug-free compiler if you keep repeating compilation of the compiler starting from the old compiler?

# Answer
There is no reason why compiling a compiler's source code with a broken compiler would result in a working compiler. The bug in the existing binary could well lead to a binary that is completely broken, or subtly broken, or has the very same bug.

For example, there once was a version of CAML (an ancestor language of Ocaml) where one version of the compiler omitted the code for a case in a match-case construct under certain circumstances. So the developers fixed the bug — a case was missing in a match-case construct in the source code. But the compiler was bootstrapped (the CAML compiler was written in CAML), and compiling the corrected source generated a binary that was still buggy, because the compiler bug caused the new case to not have generated code. The developers had to rewrite the code in a different way, then recompile to get a correct compiler, and after that they could change the source code back to using the desired match-case construct.

There is a rather famous example where such a self-reproducing bug was introduced deliberately: the “Thompson hack”. Ken Thompson was one of the main authors of the Unix operating system and the first  compiler. He introduced a backdoor in the operating system by modifying the source code of the `login` program to allow him to log in on any Unix system. Then he reverted this change and instead modified the C compiler to insert this backdoor whenever it was compiling `login.c`. Then he modified the C compiler again to add code to insert the backdoor in `login` whenever the compiler was compiling itself. He recompiled the compiler and removed all traces of his backdoor. So he had a self-perpetuating bug which happened to be a backdoor. I strongly recommend “Reflections on Trusting Trust”, his Turing award lecture, where he revealed and explained this backdoor.

In practice, there are a few ways to reduce the risk of self-perpetuating compiler bugs. Compiler writers usually try to use a well-known, stable subset of the language, and avoid newer features where the compiler is more likely to have bugs. Some compilers have a *bootstrap compiler* which depends on a subset $A$ of the language and is capable of compiling a subset $B \supset A$; the full compiler is written in $B$ and is capable of compiling the whole language. If multiple compilers exist for the language the compiler is written in, this makes it unlikely that they'll all be too buggy to compile the compiler.

There are research efforts to reduce the *trusted base* of compilers, i.e. the amount of software that must be assumed to be correct in order to guarantee that the compiler binaries will work correctly. In particular, *certified* compilers come with a proof that the compiler binary has the semantics specified by its source code. A correctness statement goes like this: “assuming that the proof checker for the compiler is correct, and assuming that the runtime environment in which the compiler runs conforms to its model, then the compiler always produces binaries that have the semantics specified by their source code”. The trusted base consists in the runtime environment and the proof checker, which is typically orders of magnitude smaller than a compiler.
> 4 votes

# Answer
Let's say you had a working compiler with source code X and compiled with a working compiler as CX. Then you add a "bug" where every integer literal i is compiled as if it was i+1. So int a\[10\]; for (int i = 0; i \< 10; ++i) a\[i\] = i; will actually produce an array with 11 elements, and initialised elements 1 to 10 but not 0.

This is your new compiler with source Y, and you compile it with CX to produce CY which has the same bug. If you compile Y with CY to produce CCY, you now have a compiler that does not just have a bug in its code generation, but that is completely broken. There is not a chance in hell that you will get anything useful if you try to compile X, Y, or Y or any other code with CCY.

So if you write a compiler that is supposed to compile itself, make sure it also compiles with some other compiler, and keep quite a few working compiled compilers around.

On the other hand, you will have compiler bugs that are really obscure and only affect source code that is weird in the first place. For example, I remember a compiler having problems with a loop for (unsigned char c = 100; c != 50; ++c) { ... } (not realising that this loop will wrap around from c = 255 to c = 0). I would bet that no compiler in the world is affected by this bug, so fixing the bug in the source code and recompiling the fixed source code with the broken compiler will produce most most likeky a compiler with the bug fixed.
> 2 votes

---
Tags: compilers
---


title: Why is this code uniquely decodable?

text:
# Question
Title: Why is this code uniquely decodable?
Source alphabet: $\\{a, b, c, d, e, f\\}$

Code alphabet: $\\{0, 1\\}$

* $a\colon 0101$
* $b\colon 1001$
* $c\colon 10$
* $d\colon 000$
* $e\colon 11$
* $f\colon 100$

I thought that for a code to be uniquely decodable, it had to be prefix-free. But in this code, the codeword $c$ is the prefix of codeword $f$ for example, so it is not prefix-free. However my textbook tells me that its reverse is prefix free (I don't understand this), and therefore it is uniquely decodable. Can someone explain what this means, or why it is uniquely decodable? I know it satisfies Kraft's inequality, but that is only a necessary condition, not a sufficient condition.

# Answer
> 28 votes
Your code has the property that if you reverse all codewords, then you get a prefix code. This implies that your code is uniquely decodable.

Indeed, consider any code $C = x\_1,\ldots,x\_n$ whose reverse $C^R := x\_1^R,\ldots,x\_n^R$ is uniquely decodable. I claim that $C$ is also uniquely decodable. This is because $$ w = x\_{i\_1} \ldots x\_{i\_m} \text{ if and only if } w^R = x\_{i\_m}^R \ldots x\_{i\_1}^R. $$ In words, decompositions of $w$ into codewords of $C$ are in one-to-one correspondence with decompositions of $w^R$ into codewords of $C^R$. Since the latter are unique, so are the former.

Since prefix codes are uniquely decodable, it follows that the reverse of a prefix code is also uniquely decodable. This is the case in your example.

The McMillan inequality states that if $C$ is uniquely decodable then $$ \sum\_{i=1}^n 2^{-|x\_i|} \leq 1. $$ In other words, a uniquely decodable code satisfies Kraft's inequality. Therefore if all you're interested in is minimizing the expected codeword length, there is no reason to look beyond prefix codes.

Sam Roweis gives in his slides a nice example of a uniquely decodable code which is neither a prefix code nor the reverse of a prefix code: $$ 0,01,110. $$ In order to show that this code is uniquely decodable, it suffices to show how to decode the first codeword of a word. If the word starts with a $1$, then the first codeword is $110$. If it is of the form $01^\*$, then it must be either $0$ or $01$. Otherwise, there must be a prefix of the form $01^\*0$. We now distinguish several cases:

$$ \begin{array}{c|cccc} \text{prefix} & 00 & 010 & 0110 & 01110 \\\hline \text{codeword} & 0 & 01 & 0 & 01 \end{array} $$ Longer runs of $1$ cannot be decoded at all.

# Answer
> 5 votes
If I give you any message that you are supposed to decode, then you can do the following: Reverse the message, starting with the last bit instead of the first bit. Reverse the code words. Decode the message. Reverse the decoded string.

You can do that because after reversing the six code words, you get a prefix-free code: 1010, 1001, 01, 000, 11, 001 is prefix free.

# Answer
> 0 votes
If prefix-free means what I think, the reverse of ‘a’ starts with 1, or 10, or 101, none of which is any other whole valid code.

Therefore, if a message ends with 0101, it can only be an ‘a’ and you can apply similar logic to the preceding bit(s).

However, what if there is no end to start from? Well, if the first bit is 1, you know it isn’t ‘a’ or ‘d’. The second bit will eliminate ‘e’ or {‘b’,’c’,’f’}. The third bit might bring it down to one choice, but if not, it is unique by the fourth bit.

As soon as you get to a unique sequence, you restart the algorithm on the next bit.

---
Tags: encoding-scheme
---


# Question
Title: If a NAND gate is universal, why you don't have NAND OISCs
If a NAND gate can be used to construct all other of the basic logic gates, then I'm wondering why you don't/can't have a purely NAND-based One Instruction Set Computer (OISC). All the OISC single instructions are complicated like "addleq, add and branch if less than or equal to zero", but I don't see why you can't just have an OISC be "nand, perform nand operation". Wondering what I am missing.

# Answer
> 1 votes
The NAND gate is "universal" in that a *network* of NAND gates can implement any combinational or sequential logic function.

So to construct a "program" out of NANDs all you need is a way of specifying the network that interconnects them.

So if every NAND gate in your "computer" has a address, and the list of instructions is of the form `inputA,inputB` you might have a start on a "computer" with one instruction that's a NAND. (I think you'll have to come up with a parallel semantics, no instruction pointer.)

# Answer
> 3 votes
With such an instruction set, all you could express are straight-line programs. Without branches, you can't have loops. Thus, the program would not be able to handle arbitrary-length inputs: it would be limited to dealing with fixed-size inputs (or inputs with a fixed known upper bound on the size of the input). So, that wouldn't be very satisfactory.

---
Tags: computer-architecture, logic, circuits
---


# Question
Title: Prove the languages |L<M>| = 2 and |L<M>| $\not=$ 2 to be non-Turing recognizable or non-recursively enumerable
I am trying to prove the **non**-recursively enumerable property of two languages.

$L\_2 = \\{\langle M \rangle: |L\langle M \rangle| = 2\\}$ and
$L\_{\not=2} = \\{\langle M \rangle: |L\langle M \rangle| \not= 2\\}$.

**My idea** is to use the following two properties:

1. If A $\leq\_m$ B and A is not Turing recognizable then B is not Turing-recognizable.
2. A $\leq\_m$ B if and only if $A^c \leq\_m B^c$.

For language $L\_{2}$, If I can show that $A\_{TM}$ is mapping reducible to $L\_{\not=2}$, according to **property 2** we could get that $\overline{A\_{TM}}$(the complement of $A\_{TM}$) is mapping reducible to $L\_{2}$, and for the fact that $\overline{A\_{TM}}$ is not Turing recognizable, we could get that $L\_{=2}$ is not Turing recognizable.

For language $L\_{\not=2}$, If I can show that $\overline{A\_{TM}}$ is also mapping reducible to $L\_{\not=2}$, and for the fact that $\overline{A\_{TM}}$ is not Turing recognizable, we could get that $L\_{\not=2}$ is not Turing recognizable.

However, I don't know how to prove the mapping reducible relationships between them. Or my direction could be totally wrong.

Could somebody give me the hints or possible solutions?

# Answer
> If I can show that $A\_{TM}$ is mapping reducible to $L\_{=2}$, ...

That is a nice idea. Given $\langle M, w \rangle$, can you construct a TM $M\_1$ that accepts only one word, the word $w$ if and only if $M$ accepts $w$?

Then, can you change $M\_1$ so that it accepts another word that is different from $w$?

You can also show that $A\_{TM}$ is mapping reducible to $L\_{\not=2}$ by creating a TM $M\_3$ which accepts 2 words if $M$ does not accepts $w$ and 3 words otherwise.
> 1 votes

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


# Question
Title: Greedy algorithm for even item distribution
I have this problem where I need to design a greedy algorithm. The problem is as follows:

A chocolate factory owns $n$ stores, which are connected by a single road. Each store has a limited supply $c\_i$ of chocolates. Furthermore, the factory would like to have the same amount of chocolate in each store. Therefore, they hired a truck driver to haul chocolates between the stores, but the driver eats two chocolate bars for each kilometer he drives.

Calculate the largest amount of chocolate $C$ they can have at each store.

**Input:** The position $p\_i$ and chocolate supply $c\_i$ of each store. The positions are in increasing sorted order.

**Output:** The largest amount $C$, such that each store can have a chocolate supply of at least $C$ after the truck driver has hauled between the stores.

I have a problem with identifying the greedy choice property for the problem. So far I came up with the following:

The greedy choice can be the minimum arithmetic mean of two neighbouring stores minus the delivery cost divided by $C$, but it has to be larger or equal to 1. I came up with the following equation: $$\min\\{\frac{\frac{1}{n} \cdot (c\_i + c\_{i\_{neighbour}} - delivery\_{cost})}{C}\\}$$

Where the delivery cost is $2\cdot |p\_i - p\_{i-1}|$.

I am not sure if this approach is the right one. I am open for hints and partial solutions.

# Answer
It looks like a greedy algorithm cannot do it alone.

Here is an approach based on binary search.

Suppose we have a subroutine to determine that if it is possible to have a chocolate supply of $s$ after the truck driver has hauled between the stores, given $s$. Note that if $s$ is possible, than $t$ is possible for any $t\<s$.

Let $m$ be the maximum among $c\_i$. Let us check if $m/2$ is possible. If yes, let us try $(m/2 + m + 1)/2$. (+1 to ensure we will try $m$ just in case). If no, check $m/4$. I believe you can see the rest of binary search algorithm. Be careful with various boundary cases.

Now the problem is how to build that subroutine? We can think recursively. Let $s$ be given. If $c\_1\>s$, we will use a truck to move $c\_1-s$ chocolates to $p\_2$. Whatever is left when the the truck has reached $p\_2$ will be added to $c\_2$. So we got $c\_2'$. If $c\_1=s$, $c\_2'=c\_2$. If $c\_1\<s$, compute $d\_2$, the least amount of the chocolate needed to be carried on a truck that starts from $p\_2$ can reach $p\_1$ to increase $c\_1$ to $s$. Subtract that amount from $c\_2$ and get $c\_2'$, which might be negative. We can see that $s$ is possible initially if and only if $s$ is possible for $c\_2', c\_3, \cdots, c\_n$ at $p\_2,p\_3,\cdots, p\_n$ respectively.

There should be enough hint above. I will let you finish the rest of work.
> 1 votes

---
Tags: algorithms, greedy-algorithms, algorithm-design
---


# Question
Title: Term for programming languages that read like sentences?
Is there a term for programming languages that read like written sentences? I'm thinking of languages like Python, where you can almost read the code aloud as a sentence, as opposed to C++ which is really arcane.

For example, in Python `if 'pizza' not in animals` is very clear when read aloud.

Seems like maybe there's a formal term for this?

# Answer
> 5 votes
I know of no standard term for that aspect of PL. Maybe you can use "human-readable syntax" or "human-friendly syntax".

In PL theory, we (unapologetically) tend to disregard syntactic issues (e.g., look at LISP), and focus more on language features / semantics / types and more math-y stuff.

I mean: if you asked me what are the main differences between C++ and Python, I would probably spend a long time before mentioning some syntactic difference.

For practical applications, of course, having a more human-centric design that the one offered by pure theory is important. A clean and easy syntax is certainly quite convenient to read and write.

Note that, if a PL pushes this principle to extremes, and employs a syntax which is very close to natural language, it could possibly harm productivity. This is because, natural languages can be quite ambiguous, and when programming you really need to be rigorous. Trying to oversimplify a PL by completely removing the math-y aspects of PL is probably not a good idea.

COBOL is arguably more human-readable than Python, but it's hardly better. `x = y+z` is simpler than `ADD Y to Z GIVING X.`

# Answer
> 1 votes
Natural language programming is what I believe you would call this

---
Tags: terminology, programming-languages
---


# Question
Title: How exactly do we define parametric polymorphism?
My naive distinction between parametric polymorphism and ad-hoc polymorphism, is that:

> In parametric polymorphism, the type is given as a variable: (pseudocode)
>
> Function f: \<.Type T\> T $\to$ T {...}

Whereas in ad-hoc polymorphism, we write different functions for each type:

> Function f: Int $\to$ Int {...}
>
> Function f: Bool $\to$ Bool {...}

But by that definition, we can always “pretend” to do parametric polymorphism:

> Function f: \<.Type T\> T $\to$ T { if T == Int then {...}; If T == Bool then {...} }

**How exactly do we define, from a type theory standpoint, parametric polymorphism, so that this is not allowed?** Do we simply say that the term T is not allowed to be used in the body of $f$?

The reason I’m asking is: I am reading about the fact that parametric polymorphism allows certain nice guarantees that ad-hoc polymorphism doesn’t.

# Answer
An informal, but better way of explaining parametric polymorphism is that the term has a uniform definiton/semantics for all types. A simple example is the identity function:

$$λ x. x$$

This is one term that can be reasonably given the type $ℕ → ℕ$, $\mathsf{Bool} → \mathsf{Bool}$, etc. Therefore, we also consider it reasonable for it to give it the type $∀a. a → a$, because it is a single term that works for *every* type.

If you want to talk about terms where types are explicitly talked about, then this becomes somewhat less clear. However, an informal idea of what must be going on in those definitions is that the type variables are completely unknown to the definition. So in:

$$Λa. λ(x : a). x$$

even though we get syntactically different terms for each choice of $a$, the definition didn't specify what happens for particular choices of $a$, or something of that sort.

The more formal/precise way of explaining all of this is usually relational parametricity. That's kind of complicated to get into, but it says that there are ways of interpreting our definitions into relations in addition to the normal semantics. In this explanation, parametric polymorphism is about preserving relatedness. So, if you instantiate a polymorphic value to related types, the values you get are related in a coherent way. And the reason why relations are used is that they give a precise (but general) way of talking about what it means for things to be 'uniform' like above.
> 5 votes

# Answer
Contrary to what you wrote, in many languages with parametric polymorphism, the type usually is *not* provided as an argument to the function. At least, it's not like the other arguments. You can't write something like "if T == int ..." because T is not a variable that can you can access in this way.

(How can you ensure this separation between arguments vs types? One way is to have type variables and data variables. Data variables can be used in computation, and type variables can be used to describe the type of data variables and expressions and function arguments, but computation can't access the contents of type variables or branch on them.)
> 2 votes

# Answer
A useful intuition is the one you described: the code of a parametric-polymorphic function `f` can not access type `T` and choose to behave in different ways according to what `T` is.

Essentially, for `f` the values of type `T` are opaque: `f` can interact with those values only in very restricted ways. For instance, `f` can "move them around":

```
f : <T,U> (T,U) -> (U,T)
f (t,u) = (u,t)

```

Here, `f` swaps the pair "moving" their components, but does not really interact with those.

Function `f` can also interact with the values exploiting its arguments

```
f : <T> (T, T->Bool) -> Int
f (t,g) = if g(t) then 4 else 6

```

Here `f` interacts with `t`, but only through function `g` which is passed as an argument.

A precise formalization of the behavior of functions whose behavior (roughly) does not "depend on `T`" was given by Reynolds when he studied parametricity and proved the abstraction theorem. This is a bit complex in the general case, but one can grasp some ideas from the following example.

Let `List(T)` denote a type for finite sequences of values `[t1,...,tn]` of type `T`. In particular, given any function `g : T -> U`, we can "lift" this to lists and obtain `map g : List(T) -> List(U)` by letting

```
map g([t1,...,tn]) = [g(t1),...,g(tn)]

```

For instance, if `g : Int -> Int` is defined as `g(n)=n+1`, then `map g : List(Int) -> List(Int)` will increment each value of its input: `map g([x1,..,xn]) = [x1+1,...,xn+1]`.

Finally, consider a parametric-polymorphic function

```
f : <A> List(A) -> List(A)

```

and assume that, when `A = Int` we have

```
f<Int> ([1,2,3]) = [2,1,1]

```

Now, recall `f` is parametric-polymorphic. So, `f` did not really "know" that `1` was number one -- it did not even "know" it was an integer. Consequently, if we replace `1` with any value `x`, `2` with any value `y` and `3` with any value `z`, all of type `T` function `f` has to satisfy

```
f<T> ([x,y,z]) = [y,x,x]

```

This can be further generalized as follows:

```
for any g : T -> U
f<U> (map g(list)) = map g(f<T> (list))

```

which reads as: if we affect the elements of the input list elements using `g` before calling `f`, we get the same result as calling `f` first, and then affect the output list elements using `g`. Intuitively, this has to be the case, since `f` can not "read" the elements, but can only "move them around", "duplicate them", or "discard them".

(In category theory, that's called a "naturality property")

Note that, in virtue of the above property, if we need to test a list-reversal parametric-polymorphic function

```
reverse : <T> List(T) -> List(T)

```

we can simply choose `T = Int`, and test for lists of integers `[1,2,...,n]`, only. That's because if the function reverses those lists of integers, it will reverse any other list (even those having a different element type).

You may want to convince yourself that the above property can be generalized to all "cointainer" types (lists, pairs, trees, ...). Parametricity goes beyond that, but that's a good example in my mind.

The "theorems for free!" paper by Wadler is a classic introduction to parametricity and contains further examples.
> 2 votes

---
Tags: programming-languages, type-theory, functional-programming, polymorphisms
---


title: Initial States in Moore Machine?

text:
# Question
Title: Initial States in Moore Machine?
I went through the rules of Moore and Mealy Machine or FA. I read that both could have **one initial state** and no final state.

If Moore Machine has one initial state then there is a problem for converting those Mealy Machines into Moore Machines in which inputs coming towards the initial state give different outputs. In this case we will get a Moore Machine which will have many initial states.

**For example:** if we convert the following Mealy Machine then we will get a Moore Machine with two initial states!

Is there any way to convert such Mealy Machines into single initial state Moore Machines?

# Answer
> 4 votes
The tutorial that you link to does not explain what "translating" between Mealy and Moore machines actually means, which is however crucial. In every step of its computation, a Mealy machine first reads the next input character, and then produces the next output character while transitioning to the next state. A Moore machine, one the other hand, first produces the next output character and then reads the next input, after which it transitions to the next state.

These two modes of computation are different and hence there is no translation between them that does not alter the semantics of the machine. When you translate from Moore to Mealy, you can build a machine that ignores the next input, produces the next output, and only then takes input and state into account to transition to the next state. The resulting Mealy machine in a sense ignores the next input until it wrote the next output.

When you translate from Mealy to Moore, you have a problem: to compute the next output, you need the next input....which is only available to the machine after producing the next output. What you can do during the translation is however to build a Moore machine that produces its output delayed by one step. This requires you to store the last output in the state component, which blows up the automaton. Whether the resulting Moore machine is good for anything practical is a different question. Even with this semantics-altering translation, there is still the problem that the Moore machine needs to give some initial output, which needs to be defined. This could be an arbitrary one or a designated "no data" output character. This seems to be the choice of your tutorial - rather than having more than one initial state, you declare the one to be initial that is labeled by the output character representing \`\`nothing''.

Having to choose some initial output shows you that this is no one-to-one translation.

---
Tags: automata, finite-automata
---


# Question
Title: Is lazy evaluation required for do-notation?
Do-notation is most famous by Haskell, which is also famous for having lazy evaluation.

But is lazy evaluation *a requirement* for implementing do-notation?

In principle, could do-notation be added to imperative languages, such as Java and C++?

# Answer
It is not required that the language is lazy. The `do` notation exists in SML family of languages (for instance OCaml), which are eager. In these languages the `do`-notation is written as the `let`-notation, that is, instead of writing

```
do x1 <- e1
   x2 <- e2
   ...
   return e

```

we write

```
let x1 = e1 in
let x2 = e2 in
...
e

```

Note however that `let` in OCaml has a fixed monad (what in Haskell would be the IO monad), whereas the `do` notation in Haskell works for any monad. There are extensions of OCaml which allow you to use any monad.
> 2 votes

# Answer
Sure, why not? F# is eager (not lazy) and has a sort-of do-notation.

Imperative PLs might add that as well, even if there's less need for monads there, since side effects (including mutating the values of variables) is a key aspect of those languages.

Scala has a `for` loop which resembles a monadic comprehension, so it's quite close to a do-block.
> 1 votes

---
Tags: programming-languages, language-design
---


title: point clouds in machine learning

text:
# Question
Title: point clouds in machine learning
What is the purpose of point clouds in machine learning?

Consider the following suggestion: Say I have a table (per year) of records (such as days) each of which is made of n real numbers such as temperatures per hour). Can I use the table as a data point to do classification of the year as hot/cold or something like that?

Any real-world examples of point cloud data?

# Answer
The term "point cloud" is normally used to refer to a set of points (locations) in 3D space. So, a table of temperatures would normally not be called a "point cloud".
> 1 votes

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


# Question
Title: Find the smallest set of strings which "covers" a given set of strings (coverage = containing as substring)
Let $S$ be a finite set of strings and $0 \< k\leq l$ integers. We want to find the smallest set of strings $T(k,l)$ for which the following holds:

* $\forall t \in T(k,l): k \leq |t| \leq l$
* $\forall s \in S \ \exists t \in T(k,l): t \subset s$ (meaning: $s$ is containing $t$ as a contiguous substring).

I would appreciate any help regarding this problem. I see that I could generate the set of all strings with length between $k$ and $l$ then consider the power set but I think there must be a better way to solve this.

I'm not even sure how hard this problem is (I think there may be a reduction for the set cover problem which means it is $NP$-complete but I really don't know) or if there are any good approximation (or maybe exact) algorithms available.

I would like to solve this problem primarily in practice. Typically, $3 \leq k \leq l \leq 10$ holds, $|S| \approx 2000$ and the lengths of the elements in $S$ can vary from 10 to 50 mainly.

# Answer
> 2 votes
Without loss of generality, we can take $l=k$. In particular, any solution to $T(k,l)$ can be converted into a solution for $T(k,k)$ by shortening each string that's longer to $k$ to a string of length $k$ (by deleting as many characters from the beginning or end as needed to get down to length $k$, chosen arbitrarily). So, it will simplify your life to focus on solving $T(k,k)$, i.e., finding a set of strings of length $k$.

Here is one possible approach. You don't need to exhaustively generate all strings of length $k$. Instead, you can generate all length-$k$ substrings of words of $S$. If each word of $S$ has length $\le n$, then there will be $\le (n-k+1) \cdot |S|$ of them. Then, you could apply some standard set-cover algorithm to that. So, you don't need to generate exponentially many strings; just polynomially many.

It's possible there may be better algorithms that take into account the combinatorial structure of the strings; I don't know.

---
Tags: algorithms, time-complexity, approximation, strings, substrings
---


# Question
Title: Finding maximum takes at least $\lceil n/2 \rceil$ comparisons
We are given an array $A$ with $n$ elements, $n \in \mathbb{N}$ and all elements are in the set $\\{1,2,3, \cdots, n \\}$.

I want to prove that finding the maximum in $A$ (that is, outputting the index at which the maximum is found in $A$) takes at least $\lceil n/2 \rceil$ comparison by assuming that there exists an algorithm that can find the maximum in at most $\lceil n/2 \rceil -1$ comparisons.

I tried assuming that there is such an algorithm, then took as an initial input some particular array $A$ (just a basic one, namely $1,2,3,\cdots,n$) and then tried changing it somehow so that the the algorithm follows the same path in the decision tree, but outputs the wrong index.

I do not know how I should change the array such that we have the same path in the decision tree. Also, maybe this is not the best array to try such a thing.

I thank you in advance!

# Answer
In fact, at least $n-1$ comparisons are needed. Indeed, consider the graph on the vertex set $A$ whose edges correspond to pairs of elements which were compared. If less than $n-1$ comparisons were made, then the graph will have at least two connected components, and in particular, we can partition it into two non-empty sets $A\_1,A\_2$ with no edges between them. It is consistent that all elements in $A\_1$ are smaller than all elements in $A\_2$, in which case the maximum is in $A\_2$. Similarly, the maximum could be in $A\_1$. The algorithm cannot tell which is which, hence will be wrong on at least one of these scenarios.

---

The exercise was probably aiming at the following simpler argument: if less than $\lceil n/2 \rceil$ comparisons are made, then there is at least one element which is not compared at all. Hence for all we know, it could be the maximum, or the minimum (if these are different!); indeed, it could be at any position at all. This argument works as long as $n \> 1$.
> 2 votes

---
Tags: proof-techniques, arrays, lower-bounds, comparison, decision-tree
---


# Question
Title: Sorting strings with "before" and "after" constraints
I'm trying to solve a constraint-satisfaction problem for a project of mine that seems like it should have a well-known solution, but I can't for the life of me seem to find it described anywhere.

I've been poring over what literature I can find about CSP's and none of the general stuff seems to be clicking. I feel like maybe my CS chops just aren't quite up to the task, so feel free to point me to some tutorial that will make me feel stupid for even asking this, if such a thing exists.

What I'm looking to do is this:

Given a list of unique strings, where each string may have either, both, or neither of the following constraints associated with it:

* `before`, which references another string in the list, and ensures that this string occurs before that one in the final sorting.
* `after`, which also references another string in the list, and ensures that this string occurs after that one in the final sorting.

Sort the strings in a way that can guarantee satisfaction of all constraints.

Something like this:

* 'bar', no constraints
* 'foo', before 'bar'
* 'baz', no constraints
* 'qux', after 'baz'
* 'quux' before 'baz', after 'foo'

Will result in a final sort like this:

* 'foo'
* 'bar'
* 'quux'
* 'baz'
* 'qux'

Though it isn't a hard requirement, I would prefer the result be deterministic. There are several alternate answers to the problem above, as 'bar' has no constraints besides being after 'foo'. Of course, I don't really care *which* one I get back as long as the algorithm reliably produces the same result each time.

I wouldn't be surprised to learn that such determinism is impossible since it seems to be one of the biggest reasons I keep running into blocks, but I've thus far been unable to prove to myself that it can't be done.

Of course, I'll also need to be able to detect sets of constraints that are impossible to satisfy-- such as this one:

* 'foo', no constraints
* 'bar', after 'foo'
* 'baz', after 'bar', before 'foo'

In cases like this I don't need any kind of answer. I just need to detect it so I can throw an exception.

So far may natural inclination has been to bust out a genetic algorithm, but that of course kills the determinism and would be wasteful if there is a better solution that just requires me to know what the heck I'm doing, lol. So I want to see if I can rule out that possibility before proceeding.

Thanks ahead of time!

# Answer
> 2 votes
Construct a directed graph in which $a \to b$ if $a$ is constrained to appear before $b$. Run a topological search. If it finds a directed cycle, there is no solution. Otherwise, it gives you some canonical solution.

---
Tags: sorting, constraint-satisfaction
---


# Question
Title: What is the motivation behind " Descriptive Complexity "?
Time and Space are two commons parameters (and also natural parameters) to measure the complexity of the problem. I am not able to understand the motivation behind defining " Descriptive Complexity". I search on the internet and find out that it is the complexity of expressing some property of the input. Take the example of the sorting problem. Time and Space seems to be a natural choice. I am unable to come up with an example or a problem which immediately implies the importance of defining the " Descriptive Complexity ".

**Question** : What is the motivation behind " Descriptive Complexity "?

# Answer
> 2 votes
If you're interested in logic, "what problems can you express in this logic?" is a completely natural question.

If you're interested in computational complexity, descriptive complexity gives another tool that you might be able to use to prove things. For example, the fact that existential second-order logic exactly corresponds to **NP** means that, if you can prove either (a) no logic corresponds exactly to **P** or (b) there is a logic that corresponds exactly to **P** but it has different expressive power to existential second-order, then you've proven that **P**$\\,\neq\\,$**NP**. And it's turned out that trying to prove it via logic has been exactly as fruitful as every other approach!

---
Tags: complexity-theory, computation-models, descriptive-complexity
---


# Question
Title: Is it possible to implement a Neural Network using a graph data structure?
I'm trying to implement a feedforward neural network using a graph. The thing is: I haven't found any example in which is used a graph data structure. So far the examples I've found used arrays.

Can anyone please point me in the direction of some literature on the topic or some tutorial?

# Answer
> 7 votes
Many implementations you can find out in the web are done on matrices (MATLAB for instance) since it provides a compact notation. Haykin's textbook on neural networks takes this approach. Matrices also provide a simple translation to hardware design (FPGA, ASIC, etc.). They are also more often implemented on the FPU.

If you implement a neural network in an object oriented manner, you are effectively doing what your question asks: implementing a neural network on a graph. Your neurons are then objects that have relations with each others. There are a few books that take that approach. One I can think of is an undergrad level book by Renard called Réseaux de neurones (sorry, only in French).

# Answer
> 4 votes
You should use a directed graph since information passes in one way when running the network and in the other when training. Your data structure should support enumerating all incoming and all outgoing edges for each node, as well as enumerating nodes by their depth. Any data structure supporting these operations can be used to implement neural networks. Take it as an exercise.

# Answer
> 2 votes
I believe what you are looking for is a Graph Convolutional Network (GCN), though I'm sure you've long since found your answer.

https://tkipf.github.io/graph-convolutional-networks/

https://towardsdatascience.com/how-to-do-deep-learning-on-graphs-with-graph-convolutional-networks-7d2250723780

---
Tags: graphs, artificial-intelligence, neural-networks
---


# Question
Title: What is the complexity of the algorithm to calculate power set of a set?
Below is an algorithm to compute the power set of a set. To my understanding, for a set with cardinality `n`, there is a `for` loop iterating `2^(n-1)` times. Hence the time complexity has to be `O(2^n)`.

However, the time complexity as per the solution, is `O(n*2^(n-1))`. What mistake am I making?

```
Arraylist < Arraylist < Integer >> getSubsets(Arraylist < Integer > set, int index) {
    Arraylist < Arraylist < Integer >> allsubsets;
    if (set.size() == index) { //Base case - add empty set
        allsubsets = new Arraylist < Arraylist < Integer >> ();
        allsubsets.add(new Arraylist < Integer > ()); // Empty set
    } else {
        allsubsets = getSubsets(set, index + 1);
        int item = set.get(index);
        Arraylist < Arraylist < Integer >> moresubsets
        new Arraylist < Arraylist < Integer >> ();
        for (Arraylist < Integer > subset: allsubsets) {
            Arraylist < Integer > newsubset = new Arraylist < Integer > ();
            newsubset.addAll(subset); //
            newsubset.add(item);
            moresubsets.add(newsubset);
        }
        allsubsets.addAll(moresubsets);
    }
    return allsubsets;
}

```

The pseudocode looks like:

```
// set: The set[0:n-1] which the power set has to be computed for
set getSubset(set):
    1. set_size = size(set)
    2. set_size == 1:
        2.1 return [{}, set]
    3. power_set_of_subset = getSubset(set[0:set_size-2])
    4. last_element = set[set_size-1]
    5. power_set_of_set = power_sets_of_subset
    6. for subset_of_subset in power_set_of_subset:
        6.1 subset_of_subset.add(last_element)
        6.2 power_set_of_set.add(subset_of_subset)
    7. return power_set_of_set

```

# Answer
The running time of step 6 depends on the size of `subset_of_subset`.

The reason is that the final list needs to contain both the original subset and the subset with `last_element` added to it. This requires copying the subsets, which takes time linear in its size.

Consequently, the running time of the algorithm scales *at least* as the total size of all subsets, which is $n2^{n-1}$.
> 3 votes

---
Tags: algorithms, complexity-theory
---


# Question
Title: Are comparison sort algos appropriate for SUBJECTIVE sorting?
I've been tasked with creating an online feature that ranks 50 fantasy characters from a variety of domains based on combat acumen and polls users one which one is the most powerful based on their votes on a series of face-to-face matchups. (Spiderman vs. Jon Snow, etc. etc.). If this is designed well, we hope to attract a large audience and high participation.

My first instinct was to use some variety of comparison sort--probably Bubble or Heap, given the manageable size. But as I brush up on the mechanics, all the literature I can find seems to be oriented toward stochastic sorts in which any pair of items can be definitely compared.

Another curveball here is that, as more people participate, the ordered list can (but needn't mustn't) be informed by all the people who have already weighted in. This will probably be necessary since we can't expect every user to weigh for hundreds of matchups. I'm not clear on how to tell the algorithm which items are already somewhere near their appropriate place in the list thanks to a lot of preexisting votes.

I'm sure I'm not the first to confront this issue since comparison algos are commonly used exact crowd wisdom on the best of, say, a few dozen photographs. I'm just not quite sure where to start. Am I looking for a variation on comparison sort with some addition search phrase for Google, or a different approach entirely?

Thanks!\[Insert favorite fantasy sign-off.\]

# Answer
> 3 votes
I suggest reading about the theory on rating systems and ranking systems. There are many standard algorithms and methods for this. I would recommend reading the following resources, to get you started and to give you an entry-point and overview and let you figure out which might be best-suited for your particular situation:

I suspect it is likely that one of these will be a reasonable choice for you.

There is a major caveat. It is important to understand is that there may not be any linear ordering of characters that has the property you want.

Think of the game rock-paper-scissors; there is no linear ordering of these three choices that ranks them in order of "power", and polling people about pairs of them won't let you find a linear order. In particular, none of those three choices are any more powerful than any other; rock beats scissors, paper beats rock, and scissors beats rock. This can show up in fantasy settings, too.

---
Tags: sorting, comparison, heap-sort
---


# Question
Title: identify abrupt frame changes in a video
The frames of live streams or videos, in general, do not flow smoothly. A sports game would have multiple cameras recording the game and hence, there will be camera switches in the stream. I am detecting objects and tracking them as long as possible. When there are full changes in the video stream, I wish to reset object tracking and do a full detection.

I am looking for methods to efficiently identify when a camera switch (or anything of that kind) happens.

What algorithms are available to efficiently identify abrupt changes in a video?

# Answer
Easiest is to capture video with an h.264 encoder, which uses key frames to identify switches. (It’s a bit more complicated, h264 will handle situations where frames come alternatively fro two different source, for example), but extracting that information from a video stream is easier than doing it yourself).

Source code for decoders is available, and a decoder will also give you useful information about movement, and things that become covered or uncovered.
> 2 votes

# Answer
One approach: Use object tracking, to measure the change between each frame and the previous frame. For instance, you might build a metric based on how far each object moved and how many objects disappeared/appeared. If this metric is large, then suspect a camera switch.

It's likely that when there is a camera switch, the tracking algorithm will totally fail and won't be able to match any object in the prior frame to the current frame, so all objects in the prior frame will have disappeared and all objects in the current frame will be treated as just appearing. This is a strong signal of a camera switch.
> 1 votes

---
Tags: computer-vision, image-processing, statistics, video
---


title: Generating project network graph

text:
# Question
Title: Generating project network graph
I had a problem of generating project network graph (like there and there) from list of activities and their dependencies.

**Informal description:**

Every activity is represented as edge of directed acyclic graph (DAG), so such layout of the graph is called activity-on-edge, as opposed to activity-on-node layout. If the dependency of two activities can not be represented as single vertex, the zero-weight edge (drawn as dotted line) is added to satisfy this dependency.

There is example of activities and dependencies table. In addition, the weights of activities are given.

Desired project network graph looks like this:

**Formal description:**

Given a list of directed edges names, their weights and list of their predecessor edges (so there is a path between head of predecessor edge and tail of listed edge), build a directed acyclic graph having exactly one vertex with no predecessor edges (source) and one vertex with no successor edges (sink).

**Question:**

So, the problem of generating project network graph and making some analysis of related project looks so easy if we represent activities not as the edges of DAG but nodes (e.g. activity-on-node layout). But is there an algorithm solving this generating problem? Could we use prepared activity-on-node graph to generate corresponding activity-on-edge graph?

# Answer
You can build a graph from this by identifying a name for each vertex, and then identifying for each edge the names of the start vertex and end vertex for that edge.

I suggest you name a vertex by the set of edges that are entering that vertex. For instance, the name for vertex $x\_5$ in your picture would be "$a\_4,a\_5,a\_6$" if we assume that $a\_4,a\_5,a\_6$ are the names of the three edges that go to $x\_5$ -- and similarly. (If you like, you can use the SHA256 hash of the list of edges as the name of the vertex, instead of using the list itself as the name -- that will make the names shorter but won't change anything).

Given your table, we can easily identify the set of all vertex names. Then, for each edge $e$, you can identify the name of its start vertex (by looking at the list of direct predecessor edges of $e$) and the name of its end vertex (by looking at any successor edge $e'$ of $e$, i.e., any edge $e'$ such that $e$ is a direct predecessor of $e'$, and then finding the name of the start vertex of $e'$).

This gives you a description of the graph as a set of edges, where each edge is represented by the name of its start vertex and the name of its end vertex. From this, you can easily construct an adjacency list representation of the graph. This then gives you the output you were seeking.
> 0 votes

---
Tags: algorithms, graphs, dag, planning
---


# Question
Title: Proof that a subtree of a red-black tree has no more than $\frac{3n}{4}$ nodes
I have a red-black tree with $n$ nodes, rooted at $x$. How can I prove or disprove that the number of nodes in any subtree of $x$ (including the root of the subtree) will never be greater than $\frac{3n}{4}$?

# Answer
Here is a natural approach to explore the extreme case.

Let node $r$ be the root of a red-black tree.

Let its left subtree be a red-black tree of black height $h$ that has the minimum number of the nodes among red-black tree of the same black height.

Let its right subtree be a red-black tree of the same black height $h$ that has the maximum number of the nodes among red-black tree of the same black height.

Now let $h=1,2,3,\cdots$ be larger and larger. Can you see the trend?

---

Here is a related exercise.

**Exercise (red-black trees may not be weight-balanced)**. Given $\alpha\lt 1$, show that there is a red-black tree which has a proper subtree that has more than $\alpha$ of all nodes.
> 2 votes

---
Tags: data-structures, binary-search-trees, red-black-trees
---


# Question
Title: Turing Machine where branches are resolved via arbitrary operator
Alternating Turing Machines output Boolean values and combine the values returned by branches via the `any`/`all` operators. Is there a name or theory behind the class of Turing Machines where there is no restriction to the Boolean space and the `any`/`all` operators?

For example, I want a machine where terminal states output real values and non-terminal states use the `min` operator to combine the outputs of branches.

Additionally, are there subclasses of this class? I imagine operators which have certain properties (associativity, idempotence, and especially properties related to ordering or transitivity) would have interesting guarantees regarding interruptibility in the same way that a machine using only the `any` operator can terminate as soon as it finds one accepting state.

# Answer
> 4 votes
Using any/all (a.k.a. or/and) gives rise to *alternating Turing machines*. Goldschlager and Parberry (*On the construction of parallel computers from various bases of boolean functions*, *Theoretical Computer Science* 48:43–58, 1986) consider the generalization to allowing arbitrary Boolean functions, and they call the resulting machines *extended Turing machines*.

To me, it would make sense to use the same term for what you're proposing. I suggest following the references in Goldschlager and Parberry and looking up who's cited them, to see if the term "extended Turing machine" stuck and if it's been applied to your scenario.

---
Tags: complexity-theory, turing-machines, optimization, terminology, logic
---


title: (Non) Context Free language?

text:
# Question
Title: (Non) Context Free language?
In an exam question it is asked to identify if the given language is Context-Free, Non Context Free or Regular. This is the question :

In my opinion this language is not a CFL since w doesn't belong to L', meaning that it belongs to not(L') which is all words (a^n b^n c^n) which is not CFL.

Apparently my answer is not right and I really don't understand why... Is this question a "trap" because i,j,k \> 0 and not \>= ? Meaning that a word (b^n c^n) is in L ? Looks like I'm lost !

I really need your help and explantions.

Thanks in advance.

# Answer
It helps to think of $L$ as having two parts.

* First part: $L\_1$ is all strings *not* in the form $a^i b^j c^k$. We can write this with the regular expression $\neg \[a^\* b^\* c^\*\]$, so it's regular.
    + (I've been informed this notation isn't universal, so to spell it out: it's the complement of the regular language $a^\* b^\* c^\*$, and the complement of a regular language is regular.)
* Second part: $L\_2$ is all strings in the form $a^i b^j c^k$ *such that the given conditions on $i, j, k$ are not fulfilled*.

The given conditions are that $i, j, k$ are all different. So how can those conditions be violated? Either $i=j$, or $j=k$, or $i=k$. We can call these three options $L\_{2a}$, $L\_{2b}$, and $L\_{2c}$ if you want.

Let's take just one of them as an example; the others work the same way. $L\_{2a}$ is *all strings of the form $a^i b^i c^k$*. Can you write a regular expression for this? How about a CFG? (The answers are no, and yes: in fact, this is one of the classic examples for what a CFG can do that a regular expression can't.)

Now, since $L\_{2a}$, $L\_{2b}$, and $L\_{2c}$ are all context-free, their union ($L\_2$) is also context-free. And since $L\_1$ is regular, it's *also* context-free. So $L$, as the union of two context-free languages, is context-free.
> 1 votes

# Answer
Not L' isn't just all words a^nb^nc^n, it also contains words that don't fit the a^nb^mc^k pattern, like "cab" or "bac", etc. It also contains the words a^nb^nc^m, etc. Try writing a CFG for it.
> -1 votes

---
Tags: automata
---


# Question
Title: An algorithm to efficiently insert a list of elements into a binary heap ("bulk insertion")
I wonder if there is any elegant algorithm for inserting a list of elements into a binary heap (at once) whose performance would be close to that of inserting elements one by one when there are only a few elements to insert, and which would still run in linear time in the worst case (when there is a lot of elements to insert).

# Answer
Wikipedia describes a procedure, due to Floyd, which constructs a heap from an array in linear time.

It also mentions a procedure for merging two heaps, of sizes $n$ and $k$, in time $O(k + \log k \log n)$.

Altogether, we can add $k$ elements to a heap of length $n$ in time $O(k + \log k \log n)$: first build a heap containing $k$ elements to be inserted (takes $O(k)$ time), then merge that with the heap of size $n$ (takes $O(k+ \log k \log n)$ time).

Compare this to repeated insertion, which would run in time $O(k\log n)$.
> 4 votes

# Answer
A citation without too much consideration or research:
heap bulk insert, Elmasry/Katajainen style (figure 3):

**procedure:** *bulk-insert*
**input:** $A\[1..n\_0+l\]$: array; $n\_0$: index; $l$: index
**data structures:** $A\[1..n\_0\]$: partial heap; $A\[n\_0+ 1..n\_0+l\]$: buffer
$right$$n\_0+l$
$left$$\max \\{n\_0+ 1, \lfloor (n\_0 + l)/2 \rfloor\\}$
**while** $right \ne 1$
$left ← \lfloor left/2 \rfloor$
$right ← \lfloor right/2 \rfloor$
**for** $j \in \\{right, right−1, \cdots, left\\}$
*sift-down*$(A, j, n\_0+l$)

Elmasry, Amr; Katajainen, Jyrki: *Towards ultimate binary heaps*
> 3 votes

---
Tags: algorithms, data-structures, heaps
---


# Question
Title: residual graph and augmenting path in max flow
I thought I understood max flow perfectly until I got to the exam and we got this. I know how to compute a maximum flow by means of the Ford-Fulkerson algorithm, specify the residual network and augmenting path. But here they gave us a graph where some of the capacities were already full (if you can tell from the picture) and I couldn't find a new augmenting path. Is there another way to solve this?

# Answer
> 2 votes
A full edge, e.g. $a \rightarrow c$, has a residual capacity of $0$ in the residual network. So you can't make an augmenting path over that **directed** edge. However the reversed edge, $c \rightarrow a$ has a residual capacity of $5$ (since $c\_{c \rightarrow a} = 0$ and $f\_{c \rightarrow a} = -5$). Therefore you can create an augmenting path using the reversed edge. The residual network would be:

E.g. a possible augmenting path would be $s \rightarrow c \rightarrow a \rightarrow d \rightarrow t$. You can increase the flow along that path by 5 and get the following flow network:

This is also the maximal flow, since $\\{s, c\\} - \\{a, b, d, t\\}$ forms a saturated **s-t-cut**.

---
Tags: algorithms, graphs, network-flow
---


# Question
Title: To check if a chain with $n$ links can be "folded" into a size at most $L$
Given a chain of $n$ links, each of length $a\_1, a\_2,..a\_n$, where each $a\_i$ is a positive integer. $L$ defines the length of the "folded" chain. More formally, we want to decide whether there exists a $t \in \[0, L\]$ and $s\_1,...,s\_n \in \\{-1, +1\\}$ such that $t + \sum\_{i=1}^j(s\_ia\_i)\in\[0,L\]$ for all $j\in\\{0,..,n\\}$.

For example, given $a\_1 = 5, a\_2 = 1, a\_3 = 7, a\_4 = 2, a\_5 = 8,$ and $L = 9$ a possible solution could be $5+1-7-2+8$ such that the entire chain is contained within a space of $9$ units.

We need to provide an $O(nL)$ time algorithm to decide if the chain can be folded or not.

My approach: I tried a couple of different approaches:

* Greedy algorithm: starting with the first link, check if it is greater than $L$, if yes then subtract $(s = -1)$ the second link from the first link. If it is still greater than $L$, the repeat. If it was not greater than $L$ initially, then add the second link to the first. This approach failed.
* Tree approach: For every link, we can have $s=1$ or $s=-1$, this gives us $2^n$ possible arrangements. We can create a binary tree of size (layers) $n$ from this. But this method won't work due to the sheer size of the tree.

Any hints or guidance is appreciated.

I was also thinking that if $L$ is not given, is there a way to determine $L$ such that it is the best folding possible?

# Answer
The crux of the problem is to identify when we can extend a chain $t, s\_1a\_1, \cdots, s\_ka\_k$ to a longer chain?

Let $m$ be the length of that chain, i.e., $m= t +\sum\_{i=1}^ks\_ia\_i$. If $m+a\_{k+1}\in \[0,L\]$, then we can extend it with $+a\_{k+1}$. If $m-a\_{k+1}\in \[0,L\]$, then we can extend it with $-a\_{k+1}$. Otherwise, the chain cannot be extended.

### An approach by dynamic programming.

Create a $(n+1)$-row by $(L+1)$-column table $F$ (shorthand for **f**oldable). All entries of $F$ are False initially. $F\[k\]\[j\]$ will be true if there is a chain made from $a\_1,\cdots, a\_k$ with length $j$ and within space $L$.

Set $F\[0\]\[j\]=\text{True}$ for all $j$, $0\le j\le L$. According to the analysis above, $F\[k+1\]\[j\]$ is true in two cases.

* $j-a\_{k+1}\in \[0,L\]$ and $F\[k\]\[j-a\_{k+1}\]$ true.
* $j+a\_{k+1}\in \[0,L\]$ and $F\[k\]\[j+a\_{k+1}\]$ true.

In other words, we can fill all values at row $F\[k+1\]$ if we know all values at row $F\[k\]$.

If $F\[n\]\[j\]$ becomes True in the end for any $j$, then we return yes. Otherwise, return no.

### Explanation on 5, 1, 7, 2, 8

```
     0   1   2   3   4   5   6   7   8   9
t 0  T   T   T   T   T   T   T   T   T   T
5 1  T   T   T   T   T   T   T   T   T   T
1 2  T   T   T   T   T   T   T   T   T   T
7 3  T   T   T                   T   T   T
2 4  T       T   T   T   T   T   T       T
8 5  T                           T

```

The fourth row $F\[3\]$ corresponds to chains of the form $t$, $\pm5$, $\pm1$, $\pm7$. Their lengths can only be 0, 1, 2, 7, 8, 9. Now if you add $\pm2$ to them, you can get lengths

```
     2,  3, 4, 9, 10, 11 (for +2)
    -2, -1, 0, 5,  6, 7  (for -2)

```

So the possible lengths of chains of the form $t$, $\pm5$, $\pm1$, $\pm7$, $\pm2$ are 2, 3, 4, 9, 0, 5, 6, 7, which correspond to row $F\[4\]$.

### How to find the smallest realizable $L$?

A binary search on integers in \[a\_1, 2M-1\] should be a nice way to find the answer, where $M$ is the maximum value of $a\_i$s. Binary search is feasible since, if $L$ is realizable, values larger than $L$ are realizable too.

### Exercises

**Exercise 1.** (One minute or less) Show that the smallest realizable $L$ is at most $2M-1$, where $M$ is the largest of $a\_i$s.

**Exercise 2.** Adjust the algorithm if $s\_i\in\\{-2,-1,1,2\\}$ for all $i$ instead of $\\{-1,1\\}$.
> 0 votes

---
Tags: algorithms, graphs, asymptotics, dynamic-programming
---


# Question
Title: Exponential amount of information in polynomial size? Impossible!
I'm reading A note on succinct representations of graphs by Papadimitriou and Yannakakis. Let me quote the following paragraph on page 183:

> Formula $F$ has a highly regular structure. It has $|x|$ clauses stating that the input to the computation of $U$ is $x$, and a finite number of other types of clauses reflecting the moves of $U$, repeated in a regular way an exponential number of times (for each possible time-square combination of the computation of $U$ on $x$). In particular, it is very easy to see that, given two $c|x|$-bit integers, the indices of a literal and a clause, it can be determined in polynomial time whether the literal appears in the clause. Let us call $B$ the polynomial-time algorithm computing this literal-clause relation.

Though $B$ is polynomial-time, it's not polynomial-size because it contains an exponential amount of information, i.e., literal-clause pairs.

Then it continues:

> Combining algorithms $A$ and $B$, we obtain an algorithm $C$ which, given two integers with $ck|x|$ bits, determines in polynomial time whether the two nodes are adjacent in the graph $G(F)$, based only on the bits of $x$. For fixed $x$ this algorithm can be rendered as a polynomial-size circuit $C\_{G(F)}$ with $2ck|x|$ inputs, which is therefore a succinct representation of $G(F)$. Now, it is easy to see that, given $x$, we can construct $C\_{G(F)}$ in polynomial time.

I don't understand how you can pack an exponential amount of information in "a polynomial-size circuit $C\_{G(F)}$." Can you explain? This is the hardest part of the paper, or it is wrong.

# Answer
> 2 votes
The circuit encodes an exponential amount of information because it has exponentially many possible inputs. Instead of having an exponential-sized array that stores all the information you want, you instead have a polynomial-sized circuit that computes the information you want.

---
Tags: complexity-theory, reductions, succinct-data-structures
---


title: treewidth of a given graph

text:
# Question
Title: treewidth of a given graph
Is the *treewidth* of this graph equal to 2?

I have tried to prove it through the definition of a tree decomposition.

If its not correct can someone give any hints?

# Answer
Treewidth is always at least the clique number minus one. Your graph has a $K\_4$, so its treewidth is at least 3.
> 3 votes

# Answer
In the survey Treewidth, partial $k$-trees, and chordal graphs by Pinar Heggernes, we have the following lemma, whose proof is given as an exercise.

> **Lemma.** Let $(\\{X\_i \mid i \in I\\}, T = (I, M))$ be a tree decomposition of $G = (V, E)$, and let $K \subseteq V$ be a clique in $G$. Then there exists an $i \in I$ with $K \subseteq X\_i$.

Prove this lemma, and conclude that, as Yuval answered,

> **Corollary.** For every graph $G$, $tw(G) \geq \omega(G) - 1$.

Conclude that the treewidth is at least three.

The treewidth happens to be at most three as well, but that's a different exercise.
> 3 votes

# Answer
The class of graphs of treewidth two is precisely the class of graphs that are $K\_4$-minor-free. Because your graph contains a $K\_4$-minor, it has treewidth different from two.
> 2 votes

---
Tags: treewidth
---


# Question
Title: Meaning of polynomially larger or smaller in the context of the master method
I'm studying the master method of solving recurrences and I have a somewhat decent math background but I'm having difficulty understanding the concept of $n^{\log\_ba}$ being polynomially smaller or larger than $f(n)$.

What I mean is $n^{\log\_ba}$ being polynomially larger or smaller than the function $f(n)$ for recurrence relations of the form: $T(n) = aT(\dfrac nb) + f(n)$.

Case 1 is the case in which $n^{\log\_ba}$ is polynomially larger than $f(n)$.
Case 2 is the case in which $n^{\log\_ba}$ is equal to $f(n)$.
Case 3 is the case in which $n^{\log\_ba}$ is polynomially smaller than $f(n)$.

As my book defines it, for case 1 to apply $n^{\log\_ba-\epsilon}$ for some $\epsilon \> 0$ must be larger than $f(n)$. in other words, $n^c \> f(n)$ where $c\< \log\_ba$.

Similarly, for case 3 to apply $n^{\log\_ba+\epsilon}$ for some $\epsilon \> 0$ must be smaller than $f(n)$ or in other words $n^c \< f(n)$ where $c \> \log\_ba$.

Another way to think of subtracting $\epsilon$ is to think of $\dfrac{n^{\log\_ba}}{ n^e}$ for some $\epsilon \> 0$.

and another way to think of the adding of the $\epsilon$ is to think of $n^{\log\_ba}\*n^\epsilon$ for some $\epsilon \> 0$.

In my class slides on the master method the first example uses the recurrence $T(n) = 4T(\dfrac n2) + 1$ and suggests the possibility that case 1 applies. $n^{\log\_ba}$ would be $n^2$ and $f(n)$ would be 1.

The slide points out that $f(n)$ is NOT polynomially smaller than $n^2$.

I do not fully understand this because if you take $0 \> \epsilon \> 1$ such as $1/2$ for example.

You can then subtract this epsilon from $n^2$ and you'd have $n^{1.5}$ which would still be greater than $f(n) = 1$ for any $n \> 1$.

So how is this not an example of being polynomially smaller?

Further, the slide which explains that $f(n)$ in this example is not polynomially smaller, indicates that $T(n) = 4T(\dfrac n2) + \dfrac{n^2}{\log n}$ doesn't work

but why would they have attempted to divide $n^2$ by $\log n$ in the first place? I get the the division is equivalent to subtracting an $\epsilon$ from the exponent of $n$, but why $\log n$, what is the significance?

\*Edit: my professor's response:

As an example (assuming all numbers are positive to keep it sjmple), the idea is that for any numbers $p$ and $q$, if $q \> p$, $(n^p)\*log(n) \< n^q$ asymptotically, no matter how close to $p$ the number $q$ is.

So $n^p\*log(n)$ is not polynomially larger than $n^p$ because for any $q \> p$, eventually it will be smaller then $n^q$

# Answer
> 4 votes
(This answer refers to the version 6 of the question, which does not contain "my professor's response".)

It looks like there is some typo/inconsistency/misunderstanding somewhere in your class, the slides or your post. Hence, I will start from scratch, addressing the problems I can recognize.

Let me fix the meaning of "polynomially smaller" and "polynomially larger" in the current context. There are other usages, which are not relevant here.

**Meaning of polynomial differences.** $f(n)$ is polynomially smaller than $g(n)$ if $f(n) = O(g(n)/n^\epsilon)$ for some $\epsilon \> 0$. $f(n)$ is polynomially larger than $g(n)$ if $f(n) = \Omega(g(n)n^\epsilon)$ for some $\epsilon \> 0$. We will never say $f(n)$ is polynomially equal to $g(n)$.

Here are some examples.

* $f(n)=1$ and $g(n)=n^2$. Then $f(n)$ is polynomially smaller than $g(n)$. This is what you believed and it is correct.
* $f(n)=g(n)=n^2$. Then $f(n)$ is not polynomially smaller nor polynomially larger than $g(n)$.
* $f(n)=n^{1+\frac{1000}{\log n}}$ and $g(n)=n^2$. Then $f(n)$ is polynomially smaller than $g(n)$.
* $f(n)=\dfrac{n}{\log n}$ and $g(n)=n$. Then $f(n)$ is not polynomially smaller nor polynomially larger than $g(n)$.

### $T(n) = 4T(\dfrac n2) + 1$

$a=4$, $b=2$, $n^{\log\_24}=n^2$ is polynomial larger than the constant function 1. This is case 1 of the master's theorem.

### $T(n) = 4T(\dfrac n2) + \dfrac{n^2}{\log n}$

$a=4$, $b=2$, $\dfrac{n^2}{\log n}$ is not polynomially smaller nor polynomially larger than $n^2$. None of the three cases of master's theorem can be applied. However, the extension of case 2, case 2b can be applied.

---

## Simple exercises

**Exercise 1.** Suppose $f(n)$ is polynomial smaller than $g(n)$. Show that $f(n)$ is eventually smaller than $g(n)$, i.e., there exists some constant $n\_0$ such that $\lvert f(n)\rvert \lt g(n)$ for all $n\>n\_0$.

**Exercise 2.** Verify that $f(n)$ is polynomial smaller than $g(n)$ if and only if $g(n)$ is polynomial larger than $f(n)$, assuming that both $f$ and $g$ are always positive.

**Exercise 3.** Suppose $f(n)$ is polynomial smaller than $g(n)$. Find another function $h(n)$ such that $f(n)$ is polynomial smaller than $h(n)$ and $h(n)$ is polynomial smaller than $g(n)$.

---
Tags: asymptotics, master-theorem, polynomials
---


# Question
Title: Fenwick Tree/ Binary Index Tree Interval location
I have an array of positive numbers, and when calculating the cumulative sum of this array, want to know which interval a given point will lie in.

I have done this by searching linearly through an array, but want to use Fenwick trees in the hopes the speed up will be noticeable. I've followed tutorials online, and have now implemented construct, update and getsum functions. I'm not sure how to go about determining which interval a point will lie in though (while taking advantage of the data structure).

So for example, if I had the array \[1,2,2,1,4,6,7,3\], then I could calculate the cumulative sum as \[1,3,5,6,10,16,23,26\]. If I the had the number 17, I'd want to know what interval this lies in. So starting indexing at 0, this would be in the interval between the 5th and 6th elements of the array.

# Answer
You can perform binary search on a Fenwick Tree. The idea is Binary Lifting.

I'm assuming that we use a one-based indexing in the Fenwick tree, and that we have exactly $2^k$ elements in the array $A$. And to formalize the problem: we want to find the biggest $i$, such that $A\[1\] + A\[2\] + ... + A\[i\] \< x$ for a given $x$. This means that the prefix sum of the first $i$ element is still too small, but the prefix sum of the first $i + 1$ elements is exactly $x$ or already too big.

The exist multiple different implementations of the Fenwick tree. As I said here I use one-based indexing, since the algorithm is a lot more beautiful this way. For refreshment, one-based indexing in a Fenwick tree means the following (explained using an example): The sum of the first $13 = 1101\_2$ numbers can be computed as $bit\[1000\_2\] + bit\[1100\_2\] + bit\[1101\_2\]$, where $bit$ is the array of the nodes of the Fenwick tree. The first summand $bit\[1000\_2\]$ covers the first $1000\_2 = 8$ elements (last set bit), the second summand $bit\[1100\_2\]$ covers the next $100\_2 = 4$ elements (last set bit), and $bit\[1101\_2\]$ covers the last $1\_2 = 1$ elements (last set bit).

This indexing allows a very cool trick: We can iterate over the bits, from the highest to the lowest one, and check in $O(1)$ time if we should set it or not.

```
function find_biggest_smaller_index(x):
    // returns biggest i such that A[1] + A[2] + ... + A[i] < x
    i = 0
    for b = log(n)...0:
        set bit b in i
        if bit[i] < x:
            // yay, gives a better lower bound
            // this handes the last 2^b elements, therefore subtract them
            x -= bit[i]
        else:
            // damn, too big already
            unset bit b in i
    return i

```

---

edit: now that I think about it. It should also work if the size of the array $A$ is not a power of 2.
> 2 votes

---
Tags: data-structures
---


# Question
Title: Sampling numbers from a weighted set that sum to constant value
So I have a multi-set of positive integers $S = \\{n\_1, n\_2, \dots\\}$ with associated weights $W = \\{w\_1, w\_2, \dots\\}$. I want to sample some numbers, without replacement, from $S$ according to weights $W$ such that the sampled numbers sum to a given constant positive integer $k$.

The naive way to do it, as I understand it, is to find out all combinations of numbers from $S$ that sum to $k$ and add their weights and choose one of the combinations according to the sum of weights. But doing that is $O(|S|^k)$, which is unacceptably large.

What I'm doing right now is do a weighted shuffle of $S$ according to weights $W$, and picking number in the obtained order until the requirement is fulfilled. If, for example, the order obtained is $3, 2, 3, 2, 1$ and $k = 4$, then I'll pick $3$, ignore $2$ (as picking it will exceed $k = 4$) and pick $1$. This approach turns out to be $O(n\log\ n)$.

Does anyone have a better idea for doing this sampling in a way that is faster than exponential but more robust than what I'm currently doing now?

# Answer
> 2 votes
There's a close connection between *counting* the number of solutions and randomly *sampling* from the set of solutions. Any time you need to randomly sample, it's often helpful to ask yourself how you'd count the number of solutions, and then you can often turn that into a way to randomly sample.

So, one approach is to use dynamic programming to *count* the number ways to select numbers from $S$ that sum to $k$ (weighted by their weights $W$), then use that to help you *sample* from this space. Let me spell out the details more.

Define

$$f(S,W,k) = \sum\_I \prod\_{i \in I} w\_i,$$

where $I$ ranges over all sets of indices such that $\sum\_{i \in I} n\_i = k$. Notice that if all the weights were 1, then $f(S,W,k)$ would count the number of ways to select these numbers; in general, with arbitrary weights, you can think of $f(S,W,k)$ as a weighted count, where you sum up the weights of each candidate combination, and the weight of a combination is the product of the weights of the numbers selected. You can compute $f(S,W,k)$ using dynamic programming, using the recurrence

$$f(\\{n\_1,\dots,n\_j\\},W,k) = f(\\{n\_1,\dots,n\_{j-1}\\},W,k) + w\_j f(\\{n\_1,\dots,n\_{j-1}\\},W,k-n\_j).$$

Now you want to sample a set $I$ with probability proportional to $\prod\_{i \in I} w\_i$. This can be done, using your algorithm for computing $f(S,W,k)$. In particular, if $S=\\{n\_1,\dots,n\_m\\}$, then flip a coin with heads probability

$${f(\\{n\_1,\dots,n\_{m-1}\\},W,k) \over f(\\{n\_1,\dots,n\_m\\},W,k)}.$$

If it is heads, then don't include $n\_m$ in the solution: instead, recursively sample some numbers from $\\{n\_1,\dots,n\_{m-1}\\}$ that sum to $k$, and output that as the random sample. If it is tails, then do include $n\_m$ in the solution: recursively sample some numbers from $\\{n\_1,\dots,n\_{m-1}\\}$ that sum to $k-n\_m$, then add $n\_m$ to that combination, and output that as the random sample. You can see that this induces the correct probability distribution on samples.

Overall, the running time will be comparable to the time to compute $f(S,W,k)$, or in other words, the running time will be $O(|S| \cdot k)$. This is much better than the $O(|S|^k)$ naive solution. It can still be very slow if $k$ is enormous, but if $k$ is not too big, it might be perfectly satisfactory.

---
Tags: algorithms, combinatorics, probability-theory, sampling
---


# Question
Title: k-means clustered data: how to label newly incoming data
I have a data set with labels that were produced by a **$k$-means clustering algorithm**. Now there is some data (with the same data structure) from another source and I wonder what is the most sensible way to label this new, yet unseen data? I was thinking about either

* calculating the distance to the prior $k$-means centroids and label the data to the the nearest centroids accordingly
* run a new algorithm (e.g. *SVM*) on the new data using the old data as the training set

Unfortunately, I couldn't find anything about this particular problem. There are only a few questions about the general use of $k$-means as a classification model:

* Can $k$-means clustering do classification?
* How to segment new data with existing $k$-means model?

# Answer
> 1 votes
This is not answerable without knowing something about the data itself and where it comes from and what it means. But it sounds like you're trying to do something awfully dubious.

It sounds like you're trying to come up with labels for free, with a purely automated method. That usually doesn't work. There's no free lunch. You'll need to obtain labels from some ground-truth source of data (e.g., human labelling; retrospective analysis); no amount of pure algorithms can replace that. See Efficiently labelling training data in machine learning.

Using distance computations might give you a plausible approximation, or it might work poorly. It all depends on the meaning and distribution of the data. There will be some datasets where it will work well enough, and others where it will work terribly. There is no single answer, and no special algorithm that eliminates the need to obtain known-correct labels for your data.

---
Tags: machine-learning, classification, clustering, svm
---


# Question
Title: Maximum Changes that don't Break the Build
Let's say I have a set of changes, e.g. replacing `foo` with `bar` in a codebase, how do I programmatically discover the largest set of replacements that will not break my tests. let's assume that the call-sites are independent.

I can come up with a binary-search-like algorithm which would be worst case `O(n)` time. Proposed binary-search-like algorithm:

```
possible_changes = Set(Range(0, n - 1)) // all callsites
working_changes = Set()

while (possible_changes non empty) {
  for (range in possible_changes) {
    remove the range from possible_changes

    if (range causes failures) {
      if (range size == 1) {
        // forget the range
      } else {
        left, right = split the range
        if (range size == 2) {
          if (left does not cause failure) {
            add left to working_changes
            // forget right
          } else if (right does not cause failure) {
            add right to working changes
          }
        } else {
          add left to possible_changes
          add right to possible_changes
        }
      }
    } else {
      add range to working_changes
    }
  }
}

```

Is there a **faster way**, besides above to find all changes that would work?

# Answer
> 1 votes
The problem you're trying to solve is undecidable, since you can't tell if any of the changes makes the program go into an infinite loop.

# Answer
> 1 votes
In principle, the problem is NP-hard, in the worst case. If you have $n$ candidate replacements, you might have to try all $2^n$ combinations of replacements.

Fortunately, in practice, there are often circumstances where you can find a reasonable solution more efficiently, because many call sites are at least somewhat independent. Then it becomes an optimization problem: given a boolean function $f:\\{0,1\\}^n \to \\{0,1\\}$, find $x$ of largest Hamming weight such that $f(x)=1$. (Here the bit-string $x$ indicates which of the replacements are applied, and $f(x)$ represents whether the program passes all your tests.)

There are many possible approaches. One standard algorithm is to use delta debugging or some other bisection algorithms. Normally, these algorithms are phrased in terms of finding the *smallest* set of changes that makes the code work; in your case, you want to find the *largest* set of changes that makes the code work, but that is isomorphic (instead of choosing which candidate changes to apply, you can choosing which to avoid applying). These algorithms are easy to implement and fairly efficient in practice.

This assumes that, given a combination of candidate changes, you can tell whether it passes all of your tests in a finite amount of time. In theory, as David Richerby explains, you can't, because you can't tell whether the program has entered an infinite loop (and thus doesn't pass the tests) or whether the program is just taking a really long time (and will eventually pass the tests). In practice, we bypass that difficulty by placing a time limit, and if the program doesn't terminate within that time, we consider it to have failed the tests.

---
Tags: asymptotics, minimum-cuts
---


# Question
Title: When an algorithm says Summation this, and Integral that, what does it mean in coding terms?
I'm a student at a college with only two units of mathematics and I don't know if I'm asking in the right place so please bear with me.

I'm currently reading GPU Gems by nvidia and I have a question. It uses Sigma, as in summation, and integral a lot, but when look at the implementation of some of these algorithms, for example, Perlin noise, I can't find any sort of "summation" i.e.:

```
sum = 0
for i in range(x):
    sum += f(i)

```

They just convert the Sigma's formula to code. As for integral, I was never very good at them so I have a very weak foundation in them --- Therefore I can't even close to imagine how to convert an integral from an algorithm to code. I know integrals are two things: the area beneath the curve, and the reverse of the derivative --- But how can you derive an algorithm?

For example, this is from the Worely noise algorithm. How do you translate it to code, like Python, or anything?

I'm not asking for code, just explanation. And I hope this is the right place. Thank you.

# Answer
You are probably looking at a rather mathematical sketch of an algorithm. There are two general roads to implement non-trivial mathematical expressions such as series, integrals, and differential equations.

1. If you want exact, potentially symbolic results you have to simplify "complex" expressions into closed forms on paper, and/or employ *computer algebra*.
2. If you are satisfied with numerical, potentially approximate solutions, you want to employ *numerical algorithms*, including error estimations.
> 2 votes

---
Tags: algorithms, numerical-algorithms, computer-algebra
---


# Question
Title: How to generate random adjacency matrix with given number of components in graph
I am building a graph package in C and a part of the work involves generating a random graph with a given number of components in the graph.

For example, if I wanted to generate a graph of 50 vertices and 5 components, then the module will take 50 and 5 as parameters and should be able to generate an adjacency matrix of the graph(for the time being I am implementing it using adjacency matrix only). I have an idea that I can generate cliques of a different number of vertices and the number of cliques is exactly equal to the number of components. Then I can merge all the adjacency matrices corresponding to cliques to form the adjacency matrix of the graph.

Implementing this in C seems to be quite complicated, and I feel this is not an optimal solution as the graph will be dense every time and I can not achieve a sparse graph using this approach. Is there anything I am missing?

# Answer
> 2 votes
What you need is to take advantage of disjoint set, a very efficient data structure.

Here is the simple algorithm to generate a random graph of $n$ vertices and $m$ component.

1. MakeSet of size $n$.
2. Choose two random vertices that has not been connected by an edge.
3. Union these two vertices. That means adding the edge between them. Use an implementation of the union operation that tells you if two different components are unioned.
4. Stop if the number of components become $m$. Go back to step 2 otherwise.

There are existing implementations of disjoint set in C/C++, Java, Python, or just about every popular language.

You can implement step 2 in various ways.

* You can use rejection sampling. Choose two random vertices. Repeat if the edge between them has been added.

This method is about the simplest to implement. It is efficient when the number of components is greater than a fixed proportion of the number of vertices. It takes little time if the number of vertices is not large.
* You can also keep track of the degree of each vertex. Choose a vertex whose degree is not $n-1$. The choose an edge from that vertex.

You can vary step 3 as well. Step 3 above is aimed to produce a random graph with given number of components and the "minimal" number of edges.

* One way to get random number of edges is to continue adding some random number of random edges after step 3 as long as no two different components become unioned/connected.
* One way to get denser graphs is to not add the edge when it connects two different component with some probability $p$. The larger $p$ is, the more edges.

In the special case of one component (connected graph) and many vertices, you can also generate a random tree using Prüfer sequence, followed by adding some random edges.

As you have mentioned, you could also generate $m$ random connected graphs with given numbers of vertices, the joining them together. Each connected graph can be generated using either disjoint set or Prüfer sequence.

Note that for all above variations, the distribution of the generated graphs is probably different from each other. It is your task to choose an implementation whose randomness/biasness is what you want. Or roughly.

---
Tags: graphs, data-structures, adjacency-matrix, random-graphs, connected-components
---


# Question
Title: Partition array into K subsets, each with balanced sum
Given array $A = \\{ a\_{1},a\_{2}, ..., a\_{n}\\}$ and integer $k; 0 \lt k \le n$, partition array $A$ into $k$ subarrays, such that

$A'\_{1} = \\{a\_{1}, ...,a\_{x}\\}$

$A'\_{2} = \\{a\_{x+1},...,a\_{y}\\}$

$...$

$A'\_{k} = \\{a\_{z+1},...,a\_{n}\\}$

where each subarray $A'\_{1},A'\_{2}, ...,A'\_{k}$ has sum of its elements closest to $\sigma; \sigma = \frac{\sum\_{i = 1}^{n} {a\_{i}}}{k}$

Example: $A = \\{{5,6,1,3,4,10\\}}, k = 3$

$\sigma = \frac{29}{3} = 9.\overline{66} \approx 10$

Best solution to split array is:

$A'\_{1} = \\{5,6\\}$

$A'\_{2} = \\{1,3,4\\}$

$A'\_{3} = \\{10\\}$

with sums $11, 8, 10$

One way to measure "badness" of each solution, is to define function $h(A\_{1},...,A\_{k}) = \sum\_{i = 1}^{k} {(s\_{i} - \sigma)^2}$, where $s\_{i}$ is sum of elements of subarray $A\_{i}$

Can you point me towards the solution? I've been trying for a few days now, and I'm no closer to an algorithm than I was few days ago.

# Answer
> 3 votes
Use dynamic programming. This is a straightforward application of dynamic programming. This is a very nice exercise, so I'll let you do the exercise yourself and won't spoil it for you -- but since you only wanted a hint, my hint is "use dynamic programming" (that's a huge, enormous hint that should be enough for you to work out the rest of the details).

In particular, you should be able to solve this in $O(kn^2)$ time.

# Answer
> 0 votes
I faced a similar question in an algorithm exam. Where it was asked to minimize the individual $max(s\_{i})$ over all such k- partitioning of n integers.

From your approach I made an algorithm that I goes as follows .

1. total = total of all n-integers.
2. p= no of parts , I initialise it to n at first and k'=k
3. while p\>k

3a. let $s\_{i}$\_bound=$\lceil\frac{total}{k'+1}\rceil$

3b. keep track of individual element sums, whenever the $t\_{i}$ exceeds the constant $s\_{i}$\_bound , we update p by incrementing it

3c. we decrease the value of k'

If we get partitions less than the required number then we can choose a required number of partitions whose sum is less than the bound and split it such that both have individual sums less than the bound. Invariance condition meted.

Runtime analysis : 3b. will run in O(n) and 3c. can decrease k' to a minimum of 1 as the least number of partitions can be 1.
So the worst case runtime will be of the order O(nk)

---

For my particular question I just need to have one more pass over the array and find the max sum which may be less than the bound I set.

# Answer
> 0 votes
This is the game of inserting the biggest currently available number into the sub array with the smallest sum. So it is best done by sorting the main array first.

My approach would be like this;

1. create an initial sub-arrays array in length given sub arrays count. sub arrays should have a sum property too. ie `[[sum:0],[sum:0]...[sum:0]]`
2. sort the main array descending.
3. start with search for the sub-array with the smallest sum value (initially they are all 0 and you will get the first sub array) and insert the first item (biggest) from the beginning of the main array and increment the sub arrays sum property by the inserted item's value.
4. repeat item 3 one by one for each main array items up until the end of main array is reached.
5. return the initial array.

# Answer
> 0 votes
There has been a solution in StackOverflow. It uses Backtracking algorithm like 8-queen problem. But this solution is brute-forcing with additional improvement. When $n\ge 400$ and $k\ge 8$, it takes lots of time!

---
Tags: arrays, partitions
---


# Question
Title: Whether it's necessary for a grammar to be ambiguous when it is both left recursive and right recursive
I read somewhere that if a grammar is left recursive as well as right recursive, then it is not necessarily ambiguous.

I couldn't make up my mind on this statement. How can a grammar which is both left recursive as well as right recursive not have more than one parse tree for a single string.

Am I right? If not, please provide a counter example whereby my assumption can be proved wrong.

Thanks in advance!

# Answer
> 4 votes
Do you mean a **grammar** with left and right recursive rules, or a single **production rule** with left and right recursive alternatives?

If a single production rule is both left and right recursive, the grammar is ambiguous. For example, the following rule

$A \to \alpha A \mid A \alpha$

has the following two (left-most) derivations:

$A \Rightarrow \alpha A \Rightarrow \alpha A \alpha $ corresponding to the grouping $(\alpha (A\alpha)$

$A \Rightarrow A \alpha \Rightarrow \alpha A \alpha $ corresponding to the grouping $((\alpha A) \alpha)$

But a grammar can have left recursive and right recursive rules in different production rules and that can be unambiguous. For example, the following grammar:

$\begin{align\*} S &\to X \mid Y \\ X &\to X b \\ Y &\to a Y \\ \end{align\*}$

In this grammar, $X$ and $Y$ are left and right recursive, respectively, but the grammar is unambiguous.

---
Tags: context-free, compilers, recursion, parsers
---


# Question
Title: Finding number of edges with weight less than k on the path between two nodes in a tree
You are given a tree with $n$ nodes and $n-1$ edges. Each edge has a weight. There are $m$ queries. In each query you have to answer the following question:

* How many edges are there in the path between node $a$ and node $b$ with weight less than $k$?

$a$, $b$, and $k$ vary in each query. You're allowed to preprocess the tree to make it easy to answer each query.

Consider the tree with edges

```
          1
 weight=4/ \weight=5
        2   3
weight=4|
        4
weight=4|
        5

```

Between nodes 3 and 5, the total number of edges with weight less than 5 is 3, i.e. {1-2, 2-4, 4-5}.

I was trying to solve by brute force method by checking each path.

I want to know if there is a better way of solving this.

# Answer
You can answer each query in time $O(\log^3 n)$, plus whatever time is needed to answer a lowest-common-ancestor query (a tricky $O(1)$-time solution exists, but you might as well go with the easier $O(\log n)$-time solution, since it doesn't hurt the final time complexity), after doing $O(n\log^3 n)$ preprocessing.

## We only need counts from each vertex to the root

Let's call the number of edges of weight less than $k$ on the path from a vertex $v$ to the root $f(v, k)$. We can calculate the desired final answer -- the number of edges of weight less than $k$ on the path from $a$ to $b$ -- using $f(a, k) + f(b, k) - 2f(lca(a, b), k)$, where $lca(u, v)$ is a the lowest common ancestor of $u$ and $v$.

From now on we will focus on answering the simpler question of computing $f(v, k)$.

## Heavy-light decomposition

The heavy-light decomposition decomposes the tree into disjoint paths in such a way that at most $O(\log n)$ such "heavy paths" are visited on the path from any vertex to the root. This can be accomplished with a DFS in $O(n)$ time. The idea here is that, since the heavy paths are disjoint, if we have a way to quickly compute the number of edges of weight less than any given $k$ for each one, then we can *nearly* compute $f(v, k)$ for any $v$ and $k$ just by summing these counts over all heavy paths that we visit on the way from $v$ to the root. And we do have a way to do this counting: Simply by sorting the edges within each heavy path by weight in a preprocessing step, we can later binary-search for any $k$ to count the number of edges of weight less than $k$ in this particular heavy path in $O(\log n)$ time.

But why only "nearly"? Because we have so far ignored the possibility that $v$ might not begin exactly at the bottom of a heavy path -- it could begin part-way up. We could try to "patch things up" by walking down to the bottom of the heavy path containing $v$, subtracting 1 from the count for each edge of weight less than $k$ that we see -- but this won't be worst-case efficient, since an individual heavy path can be as long as $n-1$ edges. We need a way to handle this bottommost heavy path efficiently.

As noted by commenter xskxzr, the issue of beginning part-way up a heavy path is not only confined to the bottommost vertex $v$ in a path to the root -- it can also happen in the middle of such a path, such as in the path from 11 to 0 in the figure on the linked page. Fortunately, the same trick, described next, works for both cases.

## Fenwick trees of sorted lists

The subproblem we are now focussed on is: Given the ordered list of edge weights $x\_1, \dots, x\_m$ encountered while traversing down a particular heavy path, we want to preprocess this list to enable us to be able to later efficiently answer queries of the form "How many of the first $r$ elements are less than $k$?", with both $r$ and $k$ part of the query. One way is to use a Fenwick tree which has as its elements not individual integers, but *sorted lists of* integers.

A "regular" Fenwick tree with single-integer elements takes $O(n)$ space. Since each $x\_i$ belongs to at most $O(\log n)$ buckets, increasing the size of the Fenwick tree's elements from single integers to sorted lists of integers fortunately only increases space usage by a $\log n$ factor. The associative operation in a "regular" Fenwick tree is usually addition; in our Fenwick tree it's "set union". For efficiency, all lists should be populated in a first pass, and then only sorted once, in a second pass. This can be done in $O(n\log^2 n)$ time for a single heavy path, so $O(n\log^3 n)$ overall.

To process an $(r, k)$-query for a particular heavy path, a subquery in that heavy path's Fenwick tree is performed on each of the sequence of buckets found by stripping least-significant 1-bits from $r$, and the counts from these subqueries are summed. That much is standard for Fenwick trees, but the individual subqueries are more complicated: Instead of just reading out the integer value from each bucket, we must binary-search the sorted list in that bucket for $k$; the leftmost position where $k$ appears (or would appear) tells us the number of edges of weight less than $k$ in that bucket.

An example might help: Suppose $r = 43$. In binary, 43 is 101011 (32 + 8 + 2 + 1). To answer a query for $r = 43$ (and some $k$ value), we would binary-search for $k$ in the following 4 buckets: 101011, 101010, 101000, 100000. Each bucket is found by stripping the least-significant 1-bit from the previous bucket, so there cannot be more than $\log n$ subqueries. Each subquery is a binary search, so cannot take longer than $O(\log n)$ time. Finally, there are at most $O(\log n)$ heavy paths encountered on the path from any vertex to the root, so the worst-case time to compute $f(v, k)$ is $O(\log^3 n)$.
> 3 votes

# Answer
# Introduction

This is an alternative to j\_random\_hacker's solution, or more precisely, an alternative to his/her solution to the subproblem:

> Given the ordered list of edge weights $x\_1,\ldots,x\_m$ encountered while traversing down a particular heavy path, we want to preprocess this list to enable us to be able to later efficiently answer queries of the form "How many of the first $r$ elements are less than $k$?"

j\_random\_hacker uses the data structure of Fenwick tree of sorted lists, which results in a solution with

* overall $O(n\log^3 n)$ preprocessing time for all heavy paths,
* overall $O(n\log n)$ space for all heavy paths, and
* $O(\log^2 n)$ query time for the subproblem, hence $O(\log^3 n)$ query time for the primary problem.

In contrast, my alternative gives a solution with

* overall $O(n\sqrt{n})$ preprocessing time for all heavy paths,
* overall $O(n\sqrt{n})$ space for all heavy paths, and
* $O(1)$ query time for the subproblem, hence $O(\log n)$ query time for the primary problem.

# How to preprocess each heavy path?

In the very first, before we turn to those heavy paths, we sort all edges according to their weights from small to large. Say the result is $e\_1,\ldots,e\_{n-1}$ with weights $w\_1,\ldots,w\_{n-1}$. We label edge $e\_i$ by $i$ for future use. Denote $I\_1=(-\infty,w\_1\],I\_2=(w\_1,w\_2\],\ldots,I\_n=(w\_{n-1},+\infty)$.

Now let's focus on the subproblem mentioned above. We divide $x\_1,\ldots,x\_m$ into blocks of length $t=\lceil\sqrt{n}\rceil$: $\left\[x\_1,\ldots,x\_t\right\],\left\[x\_{t+1},\ldots,x\_{2t}\right\],\ldots$ We build two tables $T\_1, T\_2$ where $T\_1(p,q,r)$ represents how many of the first $r$ elements in the $q$th block are less than $k$ if $k\in I\_p$, and $T\_2(p,q)$ represents how many of the elements in the first $q$ blocks are less than $k$ if $k\in I\_p$.

Now if we have these two tables, we can answer an query for each heavy path in $O(1)$ time. For example, for a query $(r,k)$, if $k\in I\_5$ and $r=3t+2$, then the answer is $T\_1(5,4,2)+T\_2(5,3)$.

Note it takes $O(\log n)$ time to find $p$ such that $k\in I\_p$. Since we need to do this search only once for each query of the primary problem, it does not increase the query time.

# How to build these tables?

Note $T\_2(p,q)=\sum\_{i=1}^q T\_1(p,i,t)$, if we already have $T\_1$, we can build $T\_2$ in $O(nm/t)$ time and it takes $O(nm/t)$ space. Next we focus on how to build $T\_1$.

Suppose the edge weights in the $q$th block are $w\_{i\_1},\ldots,w\_{i\_t}$ where $i\_1\<\cdots\<i\_t$ (recall that these edges are already labeled by $i\_1,\ldots,i\_t$). Then we have

\begin{align} T\_1(1,q,\*)=T\_1(2,q,\*)=&\cdots=T\_1(i\_1,q,\*),\\ T\_1(i\_1+1,q,\*)=T\_1(i\_1+2,q,\*)=&\cdots=T\_1(i\_2,q,\*),\\ &\cdots\\ T\_1(i\_t+1,q,\*)=T\_1(i\_t+2,q,\*)=&\cdots=T\_1(n,q,\*), \end{align}

where $T\_1(p,q,\*)$ represents the array $\[T\_1(p,q,1),\ldots,T\_1(p,q,t)\]$, and two arrays are equal if they are element-wise equal. This means we only need to compute and store $t$ arrays for $T\_1(1, q, \*),\ldots,T\_1(n, q, \*)$. So we can build $T\_1$ in $O(t^2\cdot m/t)=O(mt)$ time, and it also takes $O(mt)$ space.

Note $t=\lceil\sqrt{n}\rceil$, the overall preprocessing time for all heavy paths are

$$ \sum\_m O(m\sqrt{n})=O(n\sqrt{n}). $$

So is the overall space used.
> 1 votes

# Answer
Judging by the comments so far, your best bet is probably to build a dictionary with each pair of nodes as keys, and any info about their path that you need.

You can build this in a systematic way by traversing the tree and reusing the partial paths as you go on. This way you can reuse partial results to improve on time complexity.

Being more specific: use Floyd-Warshall algorithm to systematically explore all shortest paths between each pair of nodes. Since this is a tree, there will only be one such path for each pair.
While computing the partial solutions, also keep an extra matrix that keeps track of how many edges are less than 5.
Any time you include a new path the number of edges with weights less than 5 is the sum of the number of such edges in the partial solutions. If the current edge being added is less than 5, add 1 to this calculated value.
> -1 votes

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