# Question
Title: Why do admissible functions allow $A^*$ to retain correct shortest path computations?
I was reading about how to use $A^\*$ and was told that:

> A heuristic is admissible if $h(u) \leq \delta(u,t)$, where $\delta(u,t)$ function indicates that the shortest path from $u$ to $t$.

I was wondering why such a condition guarantees that the shortest paths can still be computed.

Its clear to me if the heuristic is defined as with the help of a potential function $\lambda(u)$:

$$ h(u) = \lambda(u) - \lambda(s) $$

and the new weights are defined as (i.e. the potential function is feasible):

$$ w^\*(u,v) = w(u,v) + h(u) = w(u,v) + \lambda(u) - \lambda(s) $$

then if we have $w^\*(u,v) \geq 0$ with that heuristic then its clear that shortest paths are retained (because of telescoping series).

However, otherwise, I can't see why admissible function would retain shortest paths or what the motivation is to use admissible function with the property $h(u) \leq \delta(u,t)$. Why is that?

Usually heuristics tilt search algorithms to better paths, how do admissible function attain this?

# Answer
Look at it this way:

The heuristic function lets us avoid exploring subpaths that we know are too long.

Suppose we're trying to get from $u$ to $t$. We're running our search, and the best path from $u$ to $t$ so far has length $UB$. We know it takes at most $UB$ to get to $t$.

Now, we see a vertex $v$. If we've found $v$, then we know the exact shortest path from $u$ to $v$. Call this $k$.

We want to know if we should bother looking at the shortest path from $v$ to $t$. So we ask, can it possibly be better than our best so far? So, we check our heuristic. We know that the distance from $v$ to $t$ is at least $h(v,t)$. So if $k + h(v,t) \> UB$, then we don't need to even bother expanding $v$, since there's no way it will be better than existing paths to the goal.

This is only safe if $h$ is admissible. But note also that, the larger $h$ is, the more paths we will be able to eliminate. So we have "Price is Right" rules: our goal is always to get $h$ as close to the actual distance function as we can, but we are never allowed to go over.

Dijkstra's is just A\* with the heruistic of $h(x,y) = 0$: we ignore vertices if the distance to them from the start is farther than the best distance to the end so far. But we can do a lot better than this if we have a lower-bound on the distance between two vertices, since we can eliminate even more paths.

A common heuristic in a path-finding graph is to use euclidean distance: the shortest road between two points is never shorter than the distance between those two points. Then, our heuristic lets our algorithm eliminate nodes which are close to the initial node if they take us too far away from the final node.

If you're trying to get from Seattle to New York, Dijkstra's might try to go through Portland, because it's close to Seattle. But A\* with a Euclidean heuristic sees that this takes you out of your way too much, and can avoid this path.
> 1 votes

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


title: Strict positivity

text:
# Question
Title: Strict positivity
From This reference : Strict positivity

The strict positivity condition rules out declarations such as

```
data Bad : Set where
 bad : (Bad → Bad) → Bad
         A      B       C
 -- A is in a negative position, B and C are OK

```

Why is A is negative ? Also Why B is allowed ? I understand why C is allowed.

# Answer
> 27 votes
First a terminological explanation: *negative* and *positive* positions come from logic. They are about an assymetry in logical connectives: in $A \Rightarrow B$ the $A$ behaves differently from $B$. A similar thing happens in category theory, where we say *contravariant* and *covariant* instead of negative and positive, respectively. In physics they speak of quantities that behave "covariantly" and "contravariantly, too. So this is a very general phenomenon. A programmer might think of them as "input" and "output".

Now onto inductive datatypes.

Think of an inductive datatype $T$ as a kind of algebraic structure: constructors are the operations which take elements of $T$ as arguments and produce new elements of $T$. This is very similar to ordinary algebra: addition takes two numbers and produces a number.

In algebra it is customary that an operation takes a finite number of arguments, and in most cases it takes zero (constant), one (unary) or two (binary) arguments. It is convenient to generalize this for constructors of datatypes. Suppose `c` is a constructor for a datatype `T`:

* if `c` is a constant we can think of it as a function `unit -> T`, or equivalently `(empty -> T) -> T`,
* if `c` is unary we can think of it as a function `T -> T`, or equivalently `(unit -> T) -> T`,
* if `c` is binary we can think of it as a function `T -> T -> T`, or equivalently `T * T -> T`, or equivalently `(bool -> T) -> T`,
* if we wanted a constructor `c` which takes seven arguments, we could view it as a function `(seven -> T) -> T` where `seven` is some previously defined type with seven elements.
* we can also have a constructor `c` which takes countably infinitely many arguments, that would be a function `(nat -> T) -> T`.

These examples show that the general form of a constructor should be

```
c : (A -> T) -> T

```

where we call `A` the *arity* of `c` and we think of `c` as a constructor that takes `A`-many arguments of type `T` to produce an element of `T`.

Here is something very important: the arities must be defined *before* we define `T`, or else we cannot tell what the constructors are supposed to be doing. If someone tries to have an constructor

```
broken: (T -> T) -> T

```

then the question "how many arguments does `broken` take?" has no good answer. You might try to answer it with "it takes `T`-many arguments", but that will not do, because `T` is not defined yet. We might try to get out of the cunundrum by using fancy fixed-point theory to find a type `T` and an injective function `(T -> T) -> T`, and would succeed, but we would also break the induction principle for `T` along the way. So, it's just a bad idea to try such a thing.

For the sake of completeness, let me explain the whole story. We need to generalize the above form of constructors a little bit. Sometimes we have operations or constructors that take *parameters*. For example, scalar multiplication takes a *scalar* $\lambda$ and a vector $v$ to produce a vector $\lambda \cdot v$. It is a *unary* operation on vectors, *parameterized* by a scalar. We *could* view scalar multiplication as infinitely many unary operations, one for each scalar, but that's annoying. So, the general form of a constructor `c` should allow a parameter of some type `B`:

```
c : B * (A -> T) -> T

```

Indeed, many constructors can be rewritten in this way, but not all, we need one more step, namely we should allow `A` to *depend* on `B`:

```
c : (∑ (x : B), A x -> T) -> T

```

This is the final form of a constructor for an inductive type. It is also precisely what W-types are. The form is so general that we only ever need a single constructor `c`! Indeed, if we have two of them

```
d' : (∑ (x : B'), A' x -> T) -> T
d'' : (∑ (x : B''), A'' x -> T) -> T

```

then we can combine them into one

```
d : (∑ (x : B), A x -> T) -> T

```

where

```
B := B' + B''
A(inl x) := A' x
A(inr x) := A'' x

```

By the way, if we curry the general form we see that it is equivalent to

```
c : ∏ (x : B), ((A x -> T) -> T)

```

which is closer to what people actually write down in proof assistants. The proof assistants allow us to write down the constructors in convenient ways, but those are equivalent to the general form above (exercise!).

# Answer
> 10 votes
The first occurrence of `Bad` is called 'negative' because it represents a function argument, i.e. is located to the left of the function arrow (see Recursive types for free by Philip Wadler). I guess the origin of the term 'negative position' stems from the notion of contravariance ('contra' means opposite).

It is not allowed to have the type being defined in negative position to because one can write non-terminating programs using it, i.e. strong normalization fails in its presence (more on this below). By the way, this is the reason for the name of the rule 'strict positivity': we don't allow negative positions.

We allow the second occurrence of `Bad` since it doesn't cause non-termination and we want use the type being defined (`Bad`) at some point in a *recursive* datatype (*before* the last arrow of its constructor).

It's important to understand that the following definition does *not* violate the strict positivity rule.

```
data Good : Set where
  good : Good → Good → Good

```

The rule applies only to constructor's arguments (which are both `Good` in this case) and not to a constructor itself (see also Adam Chlipala's "Certified Programming with Dependent Types").

Another example violating strict positivity:

```
data Strange : Set where
  strange : ((Bool → Strange) → (ℕ → Strange)) → Strange
                       ^^     ^
            this Strange is   ...this arrow
            to the left of...

```

You might also want to check this answer about negative positions.

---

More on non-termination... The page your referenced contains some explanations (along with an example in Haskell):
> Non strictly-positive declarations are rejected because one can write a non-terminating function using them. To see how one can write a looping definition using the Bad datatype from above, see BadInHaskell.

Here is an analogous example in Ocaml, which shows how to implement recursive behavior *without (!)* using recursion directly:

```
type boxed_fun =
  | Box of (boxed_fun -> boxed_fun)

(* (!) in Ocaml the 'let' construct does not permit recursion;
   one have to use the 'let rec' construct to bring
   the name of the function under definition into scope
*)
let nonTerminating (bf:boxed_fun) : boxed_fun =
  match bf with
    Box f -> f bf

let loop = nonTerminating (Box nonTerminating)

```

The `nonTerminating` function "unpacks" a function from its argument and apples it to the original argument. What is important here is that most type systems do not permit passing functions to themselves, so a term like `f f` won't typecheck, since there is no type for `f` to satisfy the typechecker. One of the reasons type systems were introduced is to disable self-application (see here).

Wrapping datatypes like the one we introduced above can be used to circumvent this roadblock on the way to inconsistency.

I want to add that non-terminating computations introduce inconsistencies to logic systems. In case of Agda and Coq the `False` inductive datatype doesn't have any constructors, so you cannot ever build a proof term of type False. But *if* non-terminating computations were allowed, one could do it for example this way (in Coq):

```
Fixpoint loop (n : nat) : False = loop n

```

Then `loop 0` would typecheck giving `loop 0 : False`, so under Curry-Howard correspondence it would mean we proved a false proposition.

*Upshot*: the strict positivity rule for inductive definitions prevents non-terminating computations which are disastrous for the logic.

---
Tags: type-theory, inductive-datatypes
---


# Question
Title: How is the formal definition of NP-hard equivalent to this colloquial one?
Wikipedia informally describes NP-hard problems as "at least as hard as the hardest problems in NP".

It then states the formal definition: "a problem H is NP-hard when every problem L in NP can be reduced in polynomial time to H".

It doesn't seem obvious to me that those two statements are equivalent. In particular, it's not obvious to me that any problem is always reducible to a "harder" problem.

Why is reducibility an adequate measure of difficulty? To me, the most natural measure of difficulty is worst-case asymptotic complexity. It seems at least plausible to me that there might exist two NP problems A and B which both have the same worst-case asymptotic complexity, and that this complexity is "the worst" possible in NP, but the problems are so different that having an algorithm to solve A is not at all useful for solving B, and so neither problem is reducible into the other.

I assume from the definition of NP-hard that this in fact isn't possible. Why not?

# Answer
> Why is reducibility an adequate measure of difficulty?

It's not; it provides a *relative* measure of difficulty, relative to the kind of reduction under consideration.

> To me, the most natural measure of difficulty is worst-case asymptotic complexity.

That's the idea, but for NP-complete problems in particular *we do not know* their (worst-case asymptotic time) complexity. By introducing a relative measure of hardness, we can say "A is at least as hard as B" without knowing how hard either of them really is.

> having an algorithm to solve A is not at all useful for solving B, and so neither problem is reducible into the other.

That's *not* the idea behind Karp reductions which we use to define NP-hardness. Read up on the definition.

> this complexity is "the worst" possible in NP

There is no such thing as a worst possible complexity; all polynomial complexities are allowed, and there are problems of arbitrary polynomial complexity. You find proofs for this fact in textbooks on the matter.

> It seems at least plausible to me that there might exist two NP problems A and B which both have the same worst-case asymptotic complexity, and that this complexity is "the worst" possible in NP, but the problems are so different that having an algorithm to solve A is not at all useful for solving B, and so neither problem is reducible into the other.

Keep in mind that complexity classes like P and NP are *rough*; they ignore polynomial factors. So say we have $\Theta(n^k)$ algorithms for NP-complete $A$ and $B$. We know that $A \leq\_p B$ and vice versa, but all that tells us that we can use the algorithm for one to solve the other with *polynomial overhead*. The degree of this overhead is not specified, and may very well be in $\omega(n^k)$.

---

Bottom line, you have not yet understood/absorbed the basics and struggle with your faulty intuition contradicting statements you find. I recommend you check out our reference material which covers a wide array of basics and common misconceptions.

Keep in mind that the theory around P and NP defines *a* measure of hardness. There are certainly others, and some are more appropriate for making some decisions than others.
> 2 votes

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


title: Induced subgraph problem in trees

text:
# Question
Title: Induced subgraph problem in trees
Let $~G~$ be unweighted unordered tree. I have some number of pairs of this tree's vertices $~(u\_1, v\_1), \dots, (u\_n, v\_n)$. I need to construct a smallest subgraph of original tree such that for each pair $~(u\_i, v\_i)~$ there is path connecting this pair of vertices. "Smallest" in the sense that the number of edges being used is the least possible.

Does this problem have some special name? Can anyone offer efficient algorithm to deal with it?

# Answer
> 1 votes
First, notice that, in trees, the path between any pair of vertices is unique. This means that the sub-forest you want is the union of these paths.

To find them, do the following:

* Pick any vertex to be the root of the tree. Orient all the edges towards the root and store the distance from the root at each vertex.
* To process a pair $(u\_i,v\_i)$ start a walk towards the root from the element of the pair that is farther from it. (Break ties arbitrarily.) As you walk, mark edges. If the walk reaches the other item of the pair, stop. Otherwise do the same thing from the other item of the pair.
* Once all the pairs are processed, output the marked edges.

This is correct, since either $u\_i$ and $v\_i$ are on a path towards the root or the path between them goes through the root. It's also too slow, since we may end up walking over the same edge multiple times, so we end up with $O(n^2)$ running time.

To speed this up, we can just use a union-find data structure. The edges are partitioned into classes labeled by the lowest vertex they can reach by a path of marked edges. Now when we walk, we can skip upwards every time we encounter a marked edge, at the same time merging any classes that we need to.

With this scheme, marked edges are encountered at most twice, so get a total of $O(\alpha(n)n)$, where $\alpha$ is the inverse Ackermann function.

# Answer
> 0 votes
I am not sure about the name of this problem, but I assume that it is not a famous problem, as it is quite easy to solve.

In each tree, there is only one path between any pair of vertices. Therefore, you just need to run BFS starting from an arbitrary vertex $ u\_i $ from pairs, until you cover all vertices $ u\_j $ and $ v\_j $. You can then remove all subtrees that do not have any vertex $ u\_i $ or $ v\_i $ in them. Then, for dvery edge, chech if the cut caused by removal of the edge is separating any pair.

---
Tags: graphs, reference-request, trees
---


# Question
Title: Is this a proof that SET COVER is not an NP-hard problem?
In this paper, Karpinski and Zelikovsky introduce the SET COVER and the $\epsilon$-DENSE SET COVER problems as follows:

> **Set Cover Problem**. Let $X = \\{x\_1, \ldots, x\_k\\}$ be a finite set and $P = \\{p\_1, \ldots, p\_m\\} \subseteq 2^X$ be a family of its subsets. Find minimum size sub-family $M$ of $P$ such that $X \subseteq \bigcup \\{p \mid p \in M\\}$.
>
> An instance of the set cover problem is $\epsilon$-dense if there is $\epsilon \> 0$ such that any element of $X$ belongs to at least $\epsilon \\, m$ sets from $P$. We show that the dense set cover problem can be approximated with the performance ratio $c \log k$ for any $c \> 0$ **though it is unlikely to be NP-hard**.

In page 3, Lemma 2.1 implies—and Theorem 2.2 proves—that $\epsilon$-DENSE SET COVER is not NP-hard. But, since SET COVER is $\frac{1}{m}$-DENSE SET COVER (any element of $X$ belongs to at least 1 of the $m$ sets), would this mean that SET COVER is not NP-hard?

# Answer
Weighting of elements from set $P$ of SET COVER problem can be obtained by solving a system of linear inequalities for a given $\varepsilon$ that involves $\\{0,1\\}$-matrix $I=\[x\_i\in P\_j\]:$ $Iw\geq\varepsilon\sum\limits\_{i=1}^mw\_i.$ If it is not feasible then $\varepsilon$-DENSE SET COVER is void. Found weighting can be easily removed by repeating elements of $P$ with respect to the weighting but the resulting problem will be the same. Feasible SET COVER could be reduced to dense one for $\varepsilon=\frac{1}{m}$ but generally aforementioned reduction could lead to void dense problem for constant $\varepsilon.$

In the geometric case when VC-dimension is finite the dense problem with constant $\varepsilon$ could be solved in polynomial time due to result of Haussler and Welzl "epsilon-nets and simplex range queries" claiming existence of feasible solution to $\varepsilon$-dense problem of length $$\frac{8d}{\varepsilon}\log\frac{d}{\varepsilon}.$$ Having upper bound on the problem optimum we could solve te problem by brute-force search. Here $d$ denotes VC-dimension.
> 2 votes

---
Tags: complexity-theory, graphs, np-hard, approximation, set-cover
---


# Question
Title: How many number of different binary trees are possible for a given postorder (or preorder) traversal
I came across the problem:

> What is the number of binary trees with 3 nodes which when traversed in postorder give the sequence A,B,C?

Now 3 being small number I was quick to draw all possible binary trees and come at the conclusion that there can be 5 such binary trees for given postorder.

```
   C        C      C     C       C
  / \      /      /       \       \
 A   B    B      B         B       B
         /        \       /         \
        A          A     A           A

```

---

Then I tried to do the same for **4 nodes postorder traversal** `A,B,C,D`. We will need D at the root. Then all `A,B,C` can be in the right subtree of left subtree. So there will be $2\times 5$ such formations. Let us denote this as follows:

$\underbrace{1}\_{\text{root}}:\underbrace{3}\_{\text{#nodes in left subtree}}:\underbrace{0}\_{\text{#nodes in right subtree}} = \underbrace{5}\_{\text{#tree arrangements}}$

$1:0:3=5$

Now there is another possibility that 2 nodes are in the left subtree and the 3rd one in the right subtree or vice versa. Then,

$1:2:1=2$

$1:1:2=2$

Total $= 14$

---

For **5 nodes postorder traversal** `A,B,C,D,E`, I can get

$1:4:0=14$

$1:0:4=14$

$1:3:1=5$

$1:1:3=5$

$1:2:2=4$

Total $=42$

Though, I am able to figure out the number of binary trees required for these post orders, I am unable to come up with defining recurrence relation and any closed formula for number of binary trees possible for given post order traversal. Is such recurrence relation and closed formula possible?

# Answer
> 5 votes
Every binary tree (with the right number of nodes) has exactly one labelling that satisfies a given postorder labelling. So you need to find the number of binary trees. That is the famous Catalan number $C\_n = \frac 1{n+1}{2n \choose n}$. Sequence A000108 in Sloane's OIES.

It has a nice recurrence, based on the fact that a tree with $n+1$ nodes has a root and the remaining nodes are distributed into two subtrees with $i$ and $n-i$ nodes respectively: $C\_{n+1}=\sum\_{i=0}^n C\_i\\,C\_{n-i} $. Such a type of recurrence is called a convolution.

In fact, you have discovered this recurrence yourself! Here are your own numbers, in a slightly changed order:

$1:4:0=14 = 14 \cdot 1$

$1:3:1=5 = 5 \cdot 1$

$1:2:2=4 = 2 \cdot 2$

$1:1:3=5 = 1 \cdot 5$

$1:0:4=14 = 1 \cdot 14$

---
Tags: graphs, combinatorics, trees, binary-trees, graph-traversal
---


title: Are there color conventions in CS?

text:
# Question
Title: Are there color conventions in CS?
I don't remember seeing any color conventions in Computer Science used to represent some abstract information or to simplify diagrams.

For instance, chemists have the CPK coloring which associates elements to colors.

Electrical technicians have the electronic color code for resistors and wire colors (black for neutral/ground red for phase).

Physicists have conventions for magnets (North pole red, South pole blue), and even quarks have colors!

In CS, one of the only cases I know of are red-black trees, but it's not so much the concepts themselves, but this particular implementation.

I'm asking because I wonder if these colors could be useful in some contexts, for instance: if CFGs were always depicted with a given color for starting node and a different one for ending node; or in programming languages, having something as "immutable data is green, mutable data is blue", or in cryptography ("hash functions are yellow, symmetric encryption is blue, asymmetric is orange"), or computer architecture ("processors are red, memory is blue, buses are green"), etc. I've never seen for instance UML color conventions, or in automata theory, or other areas which frequently use diagrams. Apart from the very universal conventions of "green = good/pass, red = bad/stop", nothing seems to stick.

# Answer
Computer security (especially, military-oriented branches of it) has the concept of red/black separation, with accepted definitions of what is red and what is black.
> 4 votes

---
Tags: education, notation
---


title: Conjectured NP-complete problems

text:
# Question
Title: Conjectured NP-complete problems
Assume P != NP. Then there are many examples of problems in NP that are known not to be NP-complete, like 2-SAT, and many that are conjectured not to be NP-complete, like factorization. However, are there any problems that are widely conjectured but not known to be NP-complete?

# Answer
There are no natural problems that I am aware of that have that property. There are two problems which are "close", however.

The Minimum Circuit Size Problem is, given a truth table of a boolean function $f$ and an integer $k$, is $f$ computed by a circuit of size at most $k$? Note $MCSP \in NP$, and it is widely expected that $MCSP$ is "hard"; however, it is not known that $MCSP$ is $NP$-complete, and while it is easy to conjecture that it might be, there is also some evidence that it is not.

The Unique Games Conjecture states that approximating the value of a certain combinatoric problem is $NP$-hard. This problem is not strictly in $NP$ because its decision version is a "promise problem". Nevertheless, the UGC is one of the premier open questions of computer science today and there is little consensus on whether it is true or not.
> 6 votes

# Answer
For *deterministic* reductions,

$$\big\\{\langle L,U,N \rangle : N \text{ has a factor in } \\{L,L+1,\ldots,U-1,U\\}\big\\}$$

is such a problem.

(This answer is enough to make the *zero-error* reduction effective.)
> 3 votes

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


# Question
Title: Cutting yarn into integer-length pieces to maximize profit based on known prices for each length
My classmates and I were working on a problem on our introduction to algorithms homework, but we are having a lot of trouble wrapping our heads around it. Below is the problem:

> We are given a string of yarn of length $n$ meters, and our goal is to cut this yarn into integer-length pieces. For every integer $1..n$ we know the selling price of a piece of yarn of that length. We call the selling price of a string of yarn of length $i$ by $p\_i ≥ 0$. We must give an algorithm to compute the maximum amount of money that we could make by cutting the string into integer-length pieces. Our algorithm must run in $O(n^2)$.

So we know that this type of problem can be solved using a dynamic programming approach, but we're having trouble coming up with a recurrence relation. We think that we should start with an array $L$ such that $L\[i\]$ denotes the maximum amount of money given with a certain amount of cuts, but we're uncertain about how exactly we should represent this and where to go on from here.

Thanks a lot in advance!

# Answer
> 4 votes
*This answer isn't really helpful for your assignment and isn't framed in terms of dynamic programming. It's just about solving the problem fast.*

This problem can be solved in $O(n \lg^2 n)$ time by using iterative max-convolution on the prices.

Max-convolution takes an array $a$ and tells you $\max\_j^d (a\_j + a\_{d-j})$ for each starting offset $d$. By being clever you can do it in $O(n \lg n)$ time instead of $O(n^2)$, kinda reminiscent of the convolution theorem.

**edit**: but see @Kaban-5's important caveat in the comments, about this algorithm depending on random inputs instead of random choices!

The key thing to realize is that, if the price for a piece of length $d$ is less than the price of a piece of length $d-j$ plus a piece of length $j$, then the *effective* price for a piece of length $d$ should increase to the sum of those two prices. And if we keep looking for these pricing inefficiencies and fixing them, we'll converge on the true optimal selling price for each length.

A single max-convolution will replace every price with the maximum you can get by splitting a piece into up to two pieces and selling all the pieces. A second max-convolution will be searching through all splits into up to 4 pieces. The third goes up to 8. And so forth until we hit up-to-$n$ after the $\lg n$'th max-convolution.

Here's the algorithm:

```
def bestSplitPrice(prices):
    """
    Assuming you have a piece of yarn of length len(prices)+1, find
    the best price you can get by cutting it and selling the pieces
    at the given prices-per-length.
    """
    prices = [0] + prices #A zero-length piece costs nothing
    for i in range(ceil(lg2(prices))):
        prices = max_convolve(prices, prices)[:len(prices)]
    return prices[-1]

```

And here's an example:

```
prices = {1:1$, 2:3$, 3:3$, 4:4$, 5:5$, 6:5$, 7:7$}
# array-ify, including 0-length price
prices = [0, 1, 3, 3, 4, 5, 5, 7]
# max-convolve lg2(8) = 3 times
prices = [0, 1, 3, 4, 6, 6, 7, 8]
prices = [0, 1, 3, 4, 6, 7, 9, 10]
prices = [0, 1, 3, 4, 6, 7, 9, 10]

The best piece-price for length-7 is 10$

```

Here's how the max-convolutions play out if only the 1$ piece is given a price:

```
prices = [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
prices = [0, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
prices = [0, 1, 2, 3, 4, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
prices = [0, 1, 2, 3, 4, 5, 6, 7, 8, 7, 7, 7, 7, 7, 7, 7]
prices = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15]

```

Notes:

* I suspect this can be cut to $O(n \lg n)$ by having the max-convolutions double-hitting exponentially larger and larger sections of the array.

# Answer
> 1 votes
Your problem is a classic one (a variant of the knapsack problem). Maybe is more clear to you, if you see explicitly the overlapping into subproblems, something necessary to apply the dynamic programing paradigm, after then, is natural come up with the recursion relation.

For example, when you have the rod of length $n$, you can cut it in so many ways, like cut in $1$ or $2$, thats it, ending with a rod of lengths $\[1$ and $n-1\]$ or $\[2$ and $n-2\]$, respectively. In each case, you find the maximum profit and the compare with the other options, as we expect.

$$l(n):=\text{ maximun profit of cutting the rod of length $n$ in all possible ways }.$$

For instance, in the first case, we need the solution for the second one, because cut in $1$ (i.e. $\[1$ and $n-1\]$) means $\text{price}(1)+l(n-1)$, where $l$ is the method that solves our problem for a rod of length $n$. But solves $l(n-1)$ should consider cut in $1$ again, but this time in a length of $n-2$, that is, $\text{price}(1) +l(n-2)$. As we can see $l(1)$ was already required, and if we continue, it will be required again. Also, it repeats with $l(n-2)$ and others, overlapping subproblems.

$$l(n)=\max \\{\ \underbrace{\text{price}(1)+ \color{blue}{l(n-1)}}\_{\text{cut in } 1},\ \text{price}(2) + \color{red}{l(n-2)}, \text{price}(3) + \color{green}{l(n-3)}, \cdots,\underbrace{\text{price}(n-1) + l(1)}\_{\text{cut in }n-1} \\}.$$

And, $$\color{blue}{l(n-1)}=\max \\{\ \underbrace{\text{price}(1)+ \color{red}{l(n-2)}}\_{\text{cut in } 1},\ \text{price}(2) + \color{green}{l(n-3)}, \cdots, \text{price}(n-3) + l(2) \\}.$$

Therefore, $$l(n) = \max\_{i=1,\cdots,n-1} \text{price}(i) + l(n-i).$$ with $l(0) = 0$.

* Why is $O(n^2)$?

To build up the solution $l(n)$, we have to compute the small instances of the problem, $l(1), l(2),\cdots, l(n-1)$. In each case, we have to iterate all possible cuts $1, 2, \cdots, n - 1$. Then, we have $O(n)\cdot O(n)$ running time.

# Answer
> 0 votes
You are on the right track there. Using L and an array N of integers from 1 to n, you can find the max profit of any string size i, such that i\<=n. At string size i, the string will either be cut or not. The max profit will be pi if it's not cut, and pj+L\[i-j\] for all j in N given j\<=i. Then just compare the two to determine which value is greater. Here's some psuedocode

L\[0\]=0 for all i in N L\[i\]=max{pi, ((pj+L\[i-j\]) for all j in N given j\<=i)} return L\[n\]

Hope this helped

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


# Question
Title: Implication of Berman and Hartmanis conjecture
I am reading "Complexity and Cryptography" by Talbolt and Welsh. The book mentions the Berman and Hartmanis conjecture :

> All $NP$-Complete languages are $p$-isomorphic.

Then the book says that if the conjecture is True then $P \ne NP$. I am unable to make sense of the proof the book gives, which is:

> If $P=NP$ then all languages in $P$ are $NP$-Complete, but there are finite languages in $P$ and these cannot be $p$-isomorphic to infinite languages.

# Answer
Two languages $X$ and $Y$ are $p$-isomorphic if there's a polynomial-time computable bijection $f\colon X\to Y$ such that $w\in X\iff f(w)\in Y$.

Now, suppose that **P$\\,=\\,$NP**. Assuming we're defining **NP**-completeness in terms of polynomial-time many-one reductions, every language in **NP**, except for $\emptyset$ and $\Sigma^\*$ is **NP**-complete. To see this, let $Y\in\mathbf{NP}\setminus\\{\emptyset, \Sigma^\*\\}$ and pick two strings $w\_{\mathrm{in}}\in Y$ and $w\_{\mathrm{out}}\notin Y$. For any language $X\in \mathbf{NP}$, we can reduce $X$ to $Y$ in polynomial time using the function $$f(w) = \begin{cases} \\,w\_{\mathrm{in}} &\text{if }w\in X\\ \\,w\_{\mathrm{out}} &\text{if }w\notin X\\,. \end{cases}$$ Since $X$ can be decided in polynomial time, we can compute $f$ in polynomial time. Note that there is a small error in the proof quoted in the question, which claims that *all* languages in **P** would be **NP**-complete if **P$\\,=\\,$NP**. This is incorrect: if we took $Y=\emptyset$ or $Y=\Sigma^\*$, the reduction wouldn't work because one of $w\_{\mathrm{in}}$ and $w\_{\mathrm{out}}$ wouldn't exist.

So, we've established that, if **P$\\,=\\,$NP**, then every finite language is **NP**-complete; we also know that some infinite languages, such as $\mathrm{SAT}$ are **NP**-complete. But now suppose that there's a $p$-isomorphism between every pair of **NP**-complete languages. That means that, in particular, there's a bijection between every finite language and $\mathrm{SAT}$. But there can't be a bijection between a finite set and an infinite set.
> 6 votes

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


title: Summation of a Random Variable

text:
# Question
Title: Summation of a Random Variable
I'm having trouble grokking Cormen's *Algorithms* book on pg. 120. The context is the hiring problem (as it is called in the book). Here is the part that is tripping me up:

> "Let X be the random variable whose value equals the number of times we hire a new office assistant."

and later on:

> "...we let $X\_i$ be the indicator random variable associated with the event in which the $i$th candidate is hired ... \[so that\] $X = X\_1 + X\_2 + \ldots + X\_n$"

In particular, Cormen defines $X\_i$ as follows:

$$ X\_i = \begin{cases} 1 & \text{if candidate $i$ is hired} \\ 0 & \text{otherwise} \end{cases} $$

**Question:** Why does $X = X\_1 + X\_2 + \ldots + X\_n$?

First, this equation only makes sense if $X$ and each of the $X\_i$ have the same domain. Here I'm assuming the domain of $X$ is $\\{1,2, \ldots , n\\}$ (i.e., each number representing the number of assistants hired).

That implies that the domain of each $X\_i$ must be $\\{1,2, \ldots , n\\}$. Then it seems that, i.e., $X\_2$ will satisfy $X\_2(2) = 1$ and be $0$ everywhere else.

But if that's the case, then $X\_1 + \ldots + X\_n$ will satisfy $X(i) = 1$ for all $i \in \\{1, \ldots , 6\\}$, which means that $X \ne X\_1 + \ldots + X\_n$ (since, for example, $X(2) = 2$). What am I missing?

**EDIT:** The more I think about it, the more I'm convinced that my misunderstanding lies with the way $X$ itself is defined. Is it true that i.e. $X(2) = 2$?

# Answer
> 5 votes
Your outcomes are not the number of candidates but rather which candidates were hired: $\Omega = \\{0,1\\}^n$. Then you have $X\_i(a\_1, \dots, a\_n) = a\_i$ and $X(a\_1, \dots, a\_n) = \sum\limits\_{i=1}^n X\_i(a\_1, \dots, a\_n) = \sum\limits\_{i=1}^n a\_i$.

---
Tags: algorithm-analysis, probability-theory
---


# Question
Title: Data structure for efficient searching, when insertions and removals are only one-sided
I need a data structure for storing a number $n$ of elements, each of whom is associated with some different time $t\_i$. $n$ varies and while it has a theoretical upper limit, this is many orders of magnitude larger than what is typically used.

Through my application I can ensure that:

* Inserted elements are always newer than all existing elements, i.e., if an element associated with a time $\check{t}$ is inserted, then $\check{t}\>t\_i ∀ i ∈ {1,…,n}$. Elements are inserted one by one.
* Only the oldest elements are removed, i.e., if element $j$ is removed, then $t\_j \< t\_i ~∀ i ∈ \lbrace 1,…,n \rbrace \setminus \lbrace j \rbrace$. Removals happen mostly one by one, but there is no direct harm if an element’s removal is delayed, as long as the fraction of spuriously stored elements remains smaller than 1.
* Apart from inserting and removing, the only thing I need to do is find the two neighbouring elements for some given time $\tilde{t}$ with $\min\limits\_i t\_i \< \tilde{t} \< \max\limits\_{i} t\_i$. With other words I need to find the two elements $j$ and $k$ such that $t\_j\<\tilde{t}\<t\_k$ and $∄ l ∈ \\{1,…,n\\}: t\_j\<t\_l\<t\_k$.

My criteria for the data structure are:

1. Finding elements as described above should be as quick as possible.
2. Inserting and removing should be quick.
3. The data structure is comparably simple to implement.

As long as we are not talking about a small runtime offset, each criterion has priority over the next.

My research so far has yielded that the answer is likely some kind of self-balancing search tree, but I failed to find any information which of them is best for the case of one-sided inserting or deleting, and it will probably cost me a considerable time to find out myself. Also, I only found incomplete information about how well the trees self-organise and how quickly (e.g., AVL trees self-organise more rigidly than red-black trees), let alone how this is affected by one-sided inserting or deleting.

# Answer
> 5 votes
Store the elements as a sequence, sorted by increasing timestamp. Use binary search to find the location where $\tilde{t}$ would occur if it were in the array; then you can easily find the two neighboring elements. Finding the two neighboring elements can be done in $O(\lg n)$ time.

You'll also need to be able to append to the end of the sequence and delete from the beginning. Thus, basically you need a queue.

There are standard constructions for a queue. For instance, you can store them in an array, with amortized $O(1)$-time insert and delete operations. Basically, you have an array for the elements of the sequence, and a start index (for the beginning of the sequence) and an end index (for the end of the sequence). To delete from the beginning, increment the start index. To add to the end, increment the end index; if this runs past the end of the existing array, allocate a new array of double the size and copy into the new array.

Alternatively: you can store the elements in a balanced binary tree. This will achieve worst-case $O(\lg n)$-time for all operations.

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


title: Indexing a dependent type on a value?

text:
# Question
Title: Indexing a dependent type on a value?
If i'm recalling from Robert Harper's lectures Homotopy type theory A dependent type is a family of type index by a type. If we allow index to be just a value can we gain something instead of allowing to be a type ?

Is that the same thing they did in DML?

Wikipedia definition states in this regards :

> A dependent type is a type whose definition depends on a value.

If i have a specification stating : "list of Strings" rather than " a List of Strings of n length", are't i'm still stating something about the value ? Is this definition enough to distinguish dependent types ? thanks

# Answer
> 7 votes
The best answer I can give is that you are confused about the meaning of words. I tried to explain this already in another answer to you, so let me be more explicit this time.

To say

> type $A$ indexed by type $B$

and

> type $A$ indexed by values of type $B$

**is the same thing**. People say both of these to mean one and the same thing.

The important thing is to think of $A$ as a *function* with domain $B$ and codomain $\mathsf{Type}$ (the "type of all types" or a "universe of types"). So, whatever people say and however you are getting confused about "value" vs. "type" here, **a dependent type is a function** from a type (the indexing type) to the universe of types. Thus:

> A dependent type $A$ indexed by $B$ has as its domain the type $B$, therefore it takes as inputs values of type $B$.

You *cannot* index a dependent type by just a single value, that makes no sense. That would be like saying "the dependent type of lists of length 7". That is not dependent on anything because "7" is fixed. If you say "the dependent type of lists of length $n : \mathsf{nat}$" that is **the same thing** as saying "the dependent type of lists whose length is indexed by type $\mathsf{nat}$". Here $n$ is *not* fixed, it is just a sloppy way of introducing an unecessary variable. To be less sloppy, you would have to say "the dependent type which, for any $n : \mathsf{nat}$, gives the lists of length $n$". This is more correct because it explains that the dependent type is a *function* taking *any* $n$ to a type.

I hope that helps.

Just to be sure, let me also say explicitly that in set theory and ordinary mathematics *the domain of a function is a set* (and not an element of a set). Is that clear?

---
Tags: type-theory, dependent-types
---


# Question
Title: representing set of non-overlaping string in formal notation
I want to represent a set of any substrings which come from an original string with constraint that all substrings should not be overlapped. To be more clear please consider the example below:

e.g.

```
orignal_string = "ABCDEFG"      // this can be any characters.
substring = {"ABC", "DE", "FG"} // right.
substring = {"A", "BCD"}        // right.
substring = {"BC", "FG"}        // right.
substring = {"AB", "ABC"}       // wrong, AB are overlapped.
substring = {"ABCD", "CDEFG"}   // wrong, CD are overlapped.

```

How to represent this in formal notation?

# Answer
> 2 votes
*Idea:* represent substrings by their resp. start and end index.

Let $w = w\_1 \dots w\_n \in \Sigma^\*$ a string for some alphabet $\Sigma$. Denote *(indexed) substrings* of $w$ by pairs $(i,j)$ with $1 \leq i \leq j \leq n$. The actual sequence of symbols represented by $(i,j)$ would be $w\_{i,j} = w\_i \dots w\_j \in \Sigma^\*$.

Denote the set of all indexed substrings of $w$ by

$\qquad\displaystyle S\_w = \\{ (wi, j) \mid 1 \leq i \leq j \leq n \\} \subseteq \[1..n\]^2$.

Note how $\\{ w\_{i,j} \mid (i,j) \in S\_w\\}$ is can have fewer elements due to duplicate substrings.

### Non-overlapping substrings

Two indexed substrings $(i,j), (k,l) \in S\_w$ with $i \leq k$ *overlap* if and only if $k \leq j$. Otherwise, we call them *non-overlapping*.

### Sets of non-overlapping substrings

A set $A \subseteq S\_w$ of substrings of $w$ is *non-overlapping* if and only if

$\qquad \forall\\, u, c \in A.\ u$ and $v$ do not overlap¹.

### The set of all non-overlapping sets of substrings

The set of all non-overlapping sets of substrings is

$\qquad \mathcal{N}\_w = \\{ A \subseteq S\_w \mid A \text{ non-overlapping²} \\}$.

---

1. If you so desire, input the formal definition of "do not overlap" here, i.e. $u = w\_{i,j}$ and $v = w\_{k,l}$ with $i \leq k$ and $k \> j$. Or invent notation for the predicate "do overlap", e.g. $\operatorname{overlap}(u,v)$ or $\eta(u,v)$ or ...
2. Again, you can replace "non-overlapping" with the definition. I don't think that makes things more clear. The whole reason for defining shorthand is to express more complicated things easily and succinctly, after all.

---
Tags: formal-languages, strings, notation
---


# Question
Title: Trying to find a substitution to solve a recurrence
I'm trying to solve the following recurrence.

\begin{align\*} B(2) &= 1\\ B(n) &= B(\lceil n / \log\_2 n\rceil)+\Theta(n) \end{align\*}

Here is my attempt:

\begin{align\*} B(n) &= 3B(\lceil n/\log\_2 n\rceil) + \Theta(n)\\ &= 3\big(3B(\lceil n/(\log\_2 n)^2\rceil) + \Theta(n)\big) + \Theta(n)\\ &= 3\big(3\big(3B(\lceil n/(\log\_2 n)^3\rceil)\big)\big) + 3^2\Theta(n) + 3\Theta(n) + \Theta(n)\\ &\ \ \vdots\\ &= 3^{k-1}B(\lceil n/(\log\_2n)^{k-1}\rceil) + (1 + 3 + \dots + 3^{k-1})\Theta(n)\\ &= 3^{k-1} B(\lceil n/(\log\_2 n)^{k-1}\rceil) + \frac{3^k-1}{3-1}\Theta(n)\\,. \end{align\*} Is there a substitution that I can use to make the term inside the function become 2?

Or any other smart method I can use to solve this problem?

I realised I made a mistake the expansion should be

\begin{align\*} B(n) &= 3B(\lceil n/\log\_2 n\rceil) + \Theta(n)\\ &= 3\big(3B(\lceil (n/(\log\_2 n))/(\log\_2(n/(\log\_2 n) \rceil) + \Theta(n)\big) + \Theta(n)\\ &\ \ \vdots\\ \\ ,. \end{align\*}

# Answer
You don't need to try that hard. Instead, you can notice that on the one hand clearly $B(n) = \Omega(n)$, and on the other hand $$ \begin{align\*} B(n) &= \Theta\left(n + \frac{n}{\log n} + \frac{n}{\log n \log(n/\log n)} + \cdots\right) \\ &= O\left(n + \frac{n}{2} + \frac{n}{4} + \cdots\right) = O(n). \end{align\*} $$ The first inequality holds since for $n$ larger than some constant, $\log\_2 n \geq 2$ (you just need to stop the recursion once $n$ gets too small, at the cost of additional $O(1)$ which gets swallowed in the big Theta). The second inequality holds since $n+n/2+n/4+\cdots = 2n$.

Formally speaking, you can argue that $B(n) = B(n/2) + \Theta(n)$ grows faster than $B(n) = B(n/\log\_2 n) + \Theta(n)$.
> 1 votes

# Answer
Expanding more and more $\Theta(n)$ is wrong.

Start by making the recurrence explicit; replace $\Theta(n)$ by $cn$. If your solution is $f(n)$ then, you know that $B \in \Theta(f)$ assuming everything behaves nicely.
> 1 votes

---
Tags: recurrence-relation
---


# Question
Title: Why do we need double-rotations to rebalance AVL trees?
I was reading about AVL tree rebalancing from Behrouz Forouzan's book. The book first defines Left High and Right High tree:

> * **Left High (LH) tree** is a tree tree with the height of the left subtree more than that of right subtree.
> * **Right High (RH) tree** is a tree with the height of the right subtree more than that of left subtree.

Then the book says:

> Insertion of a node may make an AVL tree height unbalanced. All height unbalanced trees fall in one of these four cases:
>
> * **LH of LH** — A subtree of a tree that is left high has also become left high.
> * **RH of RH** — A subtree of a tree that is right high has also become right high.
> * **RH of LH** — A subtree of a tree that is left high has become right high.
> * **LH of RH** — A subtree of a tree that is right high has become left high.

I went through the example of balancing RH of RH tree as below. As can be seen below it involves left rotating root of RH tree (not subtree) to replace left node of the root of RH subtree:

Now I am looking at the example in Schaum's, which inserts W in the AVL tree already containing M,E,D,G,T,P,V,U,Z as follows:

I dont understand if the `rotateRight()` in above is necessary. I guess above is also an example of RH of RH tree, if you apply Forouzan's analogy. In this case nodes T and V are Right High. So as per explanation in Forouzan's book, we can apply single left rotation to node T to make it left child of V and balance this AVL tree as follows:

```
                 M
               /   \
              /     \
             E       V
            / \     /  \
           D   G   T    Z
                  / \  /
                 P   U W

```

I dont find the need of first `rightRotate()` to make W right child of Z. Is it necessary? Or Schaum's example is wrong?

# Answer
I think you are right for this example. But the title of your question is misleading. Let me explain.

After insertion the tree can be rebalanced with one (single or double) rotation at the lowest node $x$ where unbalance occurs. There are four cases, as you mention. If the key has been inserted in a left-left or a right-right subtree we do a single rotation to the right or to the left, and if it was the left-right or right-left subtree we do a double rotation at $x$ (in suitable direction). In general a single rotation will not work.

Back to the example you show us. The lowest point of unbalance is $T$. From $T$ the new key $W$ was added right-right. That means a single rotation left at $T$. As far as I see the result of this is exactly what you have drawn in your diagram.

To close, your title is misleading, as we do not need double rotation here, but we need one in other situations.
> 3 votes

# Answer
Looking at small examples can be misleading.

For a general explanation (which can be found in many textbooks), add the subtrees of P, U and W as well as the missing one of Z. Assign fitting heights symbolically, i.e. $h \pm \\{0,1,2\\}$. Observe how your proposed rotation fails.
> 2 votes

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


# Question
Title: How/when is calculus used in Computer Science?
Many computer science programs require two or three calculus classes.

I'm wondering, how and when is calculus used in computer science? The CS content of a degree in computer science tends to focus on algorithms, operating systems, data structures, artificial intelligence, software engineering, etc. Are there times when Calculus is useful in these or other areas of Computer Science?

# Answer
> 124 votes
I can think of a few courses that would need Calculus, ***directly***. I have used bold face for the usually obligatory disciplines for a Computer Science degree, and italics for the usually optional ones.

* **Computer Graphics**/Image Processing, and here you will also need Analytic Geometry and Linear Algebra, *heavily*! If you go down this path, you may also want to study some Differential Geometry (which has multivariate Calculus as a minimum prerequisite). But you'll need Calculus here even for very basic things: try searching for "Fourier Transform" or "Wavelets", for example -- these are two very fundamental tools for people working with images.
* **Optimization**, non-linear mostly, where multivariate Calculus is the fundamental language used to develop everything. But even linear optimization benefits from Calculus (the derivative of the objective function is absolutely important)
* **Probability/Statistics**. These cannot be seriously studied without multivariate Calculus.
* *Machine Learning*, which makes heavy use of Statistics (and consequently, multivariate Calculus)
* *Data Science* and related subjects, which also use lots of Statistics;
* *Robotics*, where you will need to model physical movements of a robot, so you will need to know partial derivatives and gradients.
* **Discrete Math and Combinatorics** (***yes!***, you may need Calculus for discrete counting!) -- if you get serious enough about generating functions, you'll need to know how to integrate and derivate certain formulas. And that is useful for Analysis of Algorithms (see the book by Sedgewick and Flajolet, "Analysis of Algorithms"). Similarly, Taylor Series and calculus can be useful in solving certain kinds of recurrence relations, which are used in algorithm analysis.
* **Analysis of Algorithms**, where you use the notion of limit right from the start (see Landau notation, "little $o$" -- it's defined using a limit)

There may be others -- this is just off the top of my head.

And, besides that, one benefits ***indirectly*** from a Calculus course by learning how to reason and explain arguments with technical rigor. This is more valuable than students usually think.

Finally -- you will need Calculus in order to, well, interact with people from other Exact Sciences and Engineering. And it's not uncommon that a Computer Scientist needs to not only talk but also work together with a Physicist or an Engineer.

# Answer
> 30 votes
This is somewhat obscure, but calculus turns up in algebraic data types. For any given type, the type of its one-hole contexts is the derivative of that type. See this excellent talk for an overview of the whole subject. This is very technical terminology, so let's explain.

## Algebraic Data Types

You may have come across tuples being referred to as *product types* (if not, it's because they are the cartesian *product* of two types). We're going to take this literally and use the notation:

$$a * b$$

To represent a tuple, where $a$ and $b$ are both types. Next, you may have come across *sum types* these are types which can be either one type, or another (known as *unions*, *variants*, or as the *Either* type (kinda) in Haskell). We're also going to take this one literally and use the notation:

$$a + b$$

These are named as they are because if a type $a$ has $N\_a$ values and a type $b$ has $N\_b$ values, then the type $a + b$ has $N\_a + N\_b$ values.

These types look like normal algebraic expressions and we can, in fact, manipulate them as such (to a point).

## An Example

In functional languages a common definition of a list (given in Haskell here) is this:

```
data List a = Empty
            | Cons a List

```

This says that a list is either empty or a tuple of a value and another list. Transforming that to algebraic notation, we get:

$$L(a) = 1 + a * L(a)$$

Where $1$ represents a type with one value (aka the unit type). By repeatedly inserting, we can evaluate this to get a definition for $L(a)$:

$$L(a) = 1 + a * L(a)$$ $$L(a) = 1 + a * (1 + a * L(a))$$ $$L(a) = 1 + a + a^2 * (1 + a * L(a))$$ $$L(a) = 1 + a + a^2 + a^3 * (1 + a * L(a))$$ $$L(a) = 1 + a + a^2 + a^3 + a^4 + a^5...$$

(Where $x^n$ is meant in the sense of repeated multiplication.)

This definition says then that a list is either unit, or a tuple of one item, or a tuple of two items, or of three etc, which *is* the definition of a list!

## One-hole Contexts

Now on to one-hole contexts: a one-hole context is what you get when you 'take a value out' of a product type. Let's give an example:

For a simple 2-tuple which is homogeneous, $a^2$, if we take a value out, we just get a 1-tuple, $a$. But there are two different one-hole contexts of this type: namely the first and second values of the tuple. So since it is either of these we could write that it is $a + a$, which is, of course, $2a$. This is where the differentiation comes in to play. Let's confirm this with another example:

Taking a value out of a 3-tuple gives a 2-tuple, but there three different variants:

$$(a, a, \\\_)$$ $$(a, \\\_, a)$$ $$(\\\_, a, a)$$

Depending on where we put the hole. This gives us $3a^2$ which is indeed the derivative of $a^3$. There is a proof of this in general here.

For our final example, let's use a list:

If we take our original expression for a list:

$$L(a) = 1 + a * L(a)$$

We can rearrange to get:

$$L(a) = \frac{1}{1 - a}$$

(On the surface this may seem like nonsense, but if you take the taylor series of this result you get the definition we derived earlier.)

Now if we differentiate this, we get an interesting result:

$$\frac{\partial L(a)}{\partial a} = (L(a))^2$$

Thus one list has become a pair of lists. This in fact makes sense: the two lists produced correspond to the elements above and below the hole in the original list!

# Answer
> 13 votes
Numerical Methods. There exist cumbersome calculus problems that are unique to specific applications, and they need solutions faster than a human can practically solve without a program. Someone has to design an algorithm that will compute the solution. Isn't that the only thing that separates programmers from scientists?

# Answer
> 13 votes
**Automation** \- Similar to robotics, automation can require quantifying a lot of human behavior.

**Calculations** \- Finding solutions to proofs often requires calculus.

**Visualizations** \- Utilizing advanced algorithms requires calculus such as cos, sine, pi, and e. Especially when you're calculating vectors, collision fields, and meshing.

**Logistics and Risk analysis** \- Determining whether a task is possible, the risk involved, and possible rate of success.

**Security** \- Most security can be performed without calculus; however, many people who want explanations prefer it in mathematical expressions.

**AI** \- The basics of AI can be utilized without calculus; however, calculating advanced behavior, swarm intelligence/hive minds, and complex values based decision making.

**Medical calculations** \- Visualizing most health data requires calculus such as an EKG reading.

**Science & Engineering** \- When working with nearly any other scientific discipline requires calculus: Aerospace, Astrology, Biology, Chemistry, or Engineering.

Many people in programming can go their entire career without using calculus; however, it can prove invaluable if you're willing to do the work. For me it has been most effective in automation, logistics, and visualization. By identifying specific patterns, you can simply ignore the pattern, imitate the pattern, or develop a superior method all together.

# Answer
> 7 votes
The fact is that there's very little chance you'll ever use calculus. However, virtually every other scientific discipline DOES use calculus and you are working on a science degree. There are certain expectations of what a university science degree is supposed to mean and one of those things is that you know calculus. Even if you'll never use it.

It's okay if you do poorly in calculus, but make sure you put some effort into discrete mathematics. There are a lot of real-world programming problems where discrete math comes into play and ignorance of its principles can embarrass you in front of other coders.

# Answer
> 5 votes
Many people already provided applications in CS. But sometimes you'll find Calculus when you least expect:

Regular-expression derivatives reexamined

If you know automata this pdf might be worth reading.

# Answer
> 4 votes
Some more specific examples:

* Calculus is used to derive the delta rule, which is what allows some types of neural networks to 'learn'.
* Calculus can be used to compute the Fourier transform of an oscillating function, very important in signal analysis.
* Calculus is used all the time in computer graphics, which is a very active field as people continually discover new techniques. For a fundamental example check out Kajiya's rendering equation
* Calculus is important in the field of computational geometry, investigate curve and surface modelling.

# Answer
> 3 votes
To these other excellent answers I add this point: **rigor in testing**.

In creating test cases for some applications I have had to make use of calculus to predict expected running times, memory sizes, and choose optimal parameters when tuning data structures. This includes understanding expected rounding error, etc.

While statistics is mentioned in other answers, I would like to specifically mention **Monte-carlo algorithms**, such as optimization algorithms and some **frugal streaming algorithms** that are based on Mathematical principles that include calculus.

Specific industries where I have worked where calculus was required include:

* Finance (creating a trading platform)
* Insurance (numerical integration of insurance policies in what-if scenarios to compute expected policy losses)
* Logistics (optimizing the consolidation of transportation routes)
* Signal processing

# Answer
> 3 votes
Calculus -- the integral portion -- is used directly in CS as a foundation for thinking about summation. If you work through any portion of Knuth's Concrete Mathematics section on summation, you will quickly recognize conventions common to calculus: understanding some of the continuous case gives you tools to consider the discrete.

Many of the uses of your CS study involve programming systems which monitor change, or in some cases, attempt to predict the future. The mathematics around those systems is rooted in differential equations and linear algebra, and differential equations are...calculus. There are teachers like Gibert Strang who advocate for moving more quickly into the differential equations part, but it is still a subset of calculus. When change depends on change in any system, it starts to be unstable (and stable) in ways which are both non-intuitive and very well understood. To understand why your sensible linear system is behaving in nonlinear ways, you either need the tools of calculus or you need to re-invent them for your problem space.

And finally, CS often requires reading and understanding the work of others, and calculus is the first exposure to a lot of shared vocabulary, convention, and history.

---
Tags: education, mathematical-analysis
---


# Question
Title: Expectation Maximization Algorithm for simple naive Bayesian network
I am trying to understand the following network A has two children - B & C (aka common cause)

All the variables are binary and can be either 0 or 1. In data values are missing only for some records. Only values that are missing are values A.

How does the Expectation step looks like in this example? Is it P(A|B,C) and then calculating the counts for P(A = 0| B = 0, C=0) ? I am confused with this.

How does the Maximization step looks like in this example?

# Answer
> 0 votes
I finally found the solution Expectation step is as follows Calculate new probabilities of data points as follows P(A|B,C) which we break down to

> (P(A,B,C)/P(B,C) =
>
> (P(B|C,A) * P(C|A)\*P(A)) / (sum of all P(B,C) for all A) =

since A is known then B & C is independent therefore

> (P(B|C,A) * P(C|A)\*P(A)) / (sum of all P(B,C) for all A) =

which we need to consider 3 binary variables, gives us 8 cases (2^3) lets say for A = 1, B = 0, C= 1

> (P(B=0|A=1) * P(C=1|A=1)\*P(A=1)) / ( (P(B=0|A=1) * P(C=1|A=1)\*P(A=1)) + ( (P(B=0|A=0) * P(C=1|A=0)\*P(A=0)) )
>
> = P(A=1| B=0, C=1) = lets call it value val101

we use this value (val101) to update probability of each unknown data point that has B= 0 and C = 1 and A = 1. Then update probability of each unknown data point where A=0, B=0 and C=1 with the (1-val101)

we do that for possible combinations of A, B and C 000 001 010 011 100 101 110 111

*(I think this is already an M step - Maximization, but here it goes)*

To calculate parameter theta for P(A=0) we do the following count (sum of all probabilities) of each data point where A = 0 and we divide it by the original amount of data points we do the same for the A =1

then we update conditional parameters to update parameter theta of P(B=1|A=0) we take a sum all the probabilities of all data points where A = 0 and B=1 and we divide it by the count (sum all the probabilities) of probabilities of data points where A =0 so its as follows

**#(A=0,B=1) / #(A=0) = theta P(B=1|A=0)**

and we do that for all the conditional probabilities which are as follows

P(B=1|A=0) P(B=0|A=0) P(C=1|A=0) P(C=0|A=0) P(B=1|A=1) P(B=0|A=1) P(C=1|A=1) P(C=0|A=1)

then you are done

---
Tags: algorithms, machine-learning, artificial-intelligence, probability-theory, bayesian-statistics
---


# Question
Title: Is greedy algorithm the best algorithm for set cover problem?
> Theorem: Unless $NP \subset DTIME (n^{O(\log \log n)})$, there is no $(1-o(1))\ln n$-approximation for set cover problem.

I am a bit confused by this theorem. As we know, greedy algorithm is $(\ln n+1)$-approximation, does this mean greedy algorithm is almost the best algorithm for set cover problem?

In the wiki set cover problem, there is a very bad example about the greedy algorithm, so I think a $\ln n$-approximation is meaningless. Does the theorem above say that it is impossible to design a constant approximation algorithm?

# Answer
The result you quote, due to Feige, has actually recently been improved by Dinur and Steurer (based on earlier work of Moshkovitz), who showed that unless $P = NP$, there is no polynomial time $(1 - o(1))\ln n$-approximation algorithm for set cover.

This result states that if all you care about is the worst case approximation ratio, then you cannot substantially improve on the trivial greedy algorithm. (There are also other algorithms achieving the same $\ln n$ bound.) In particular, no polynomial time algorithm gives a constant factor approximation for set cover on all instances.
> 3 votes

# Answer
Paper of P.Slavik "A Tight Analysis of the Greedy Algorithm for Set Cover" claims tight $\log m - \log\log m +\Theta(1)$ approximation factor of greedy algorithm whereas Dinur lower bound is $(1-\alpha)\log m$ for any $\alpha\>0.$ So there is some (negligible) gap between the factor and the lower bound though.
> 2 votes

---
Tags: approximation, greedy-algorithms, set-cover
---


# Question
Title: Can minimum or maximum height of the binary search tree be constrained by the position of some elements
I came across one problem, which read as follows:

> We want to place the 13 letters A, B, C, D, E, F, G, H, I, J, K, L, M in a binary search tree with the minimum number of levels: 4. Because there are fewer than 15 elements, we have some flexibility as to the structure of the tree. Which letters can appear at the root? For each possible root, which letters can be the left child of the root? The right child? Find the true statement in the list below.
>
> 1. G cannot be the root.
> 2. It is not possible for B to the left child of the root and K the right child of the root of the same tree.
> 3. It is not possible for B to the left child of the root and J the right child of the root of the same tree.
> 4. It is not possible for D to the left child of the root and K the right child of the root of the same tree.

I selected the option 2, and it was correct. However after some thinking I felt option B is also incorrect. And in fact now I am more confused with the meaning of the question itself.

First I am unable to fix what of the question is asking:

* Given option is correct if with given option, we can build a valid BST of height 4 (considering root is at height 0)
* Given option is correct if with given option, we cannot build a valid BST of height less than 4.

Should we call option 1 correct as we can build height 4 BST with root G as follows:

```
         G
       /  \
      /    \
     /      \
    D        I
   / \      / \
  B   F    H   L
 / \ /        / \
 A C E       K   M
            /
           J

```

or call incorrect since we can build height 3 (\<4) BST with root G as follows:

```
         G
       /  \
      /    \
     /      \
    D        J
   / \      / \
  B   F    I   L
 / \ /    /   / \
 A C E    H   K M

```

Similarly I initially thought that there are 8 characters between B and K. One of them can be root. So 7 characters are remaining, with which we can build only 4-height BST. We cannot build BST with height less than 4. So somehow thinking this much I selected option 2. However, option says "It is **not** possible...". But it is vey much possible to build height 4 tree with B as left child and K as a right child of the root:

```
         G
       /  \
      /    \
     /      \
    B        K
   / \      / \
  A   D    I   M
     / \  / \ /
    C   F H J L
       /
      E

```

Similarly I can build height-4 tree with B as left child and J as right child of the root (as said not possible in option 3):

```
         G
       /  \
      /    \
     /      \
    B        J
   / \      / \
  A   D    I   L
     / \  /   / \
    C   F H   K M
       /
      E

```

Finally, I can build height-4 tree with D as left child and K as right child of the root (as said not possible in option 4):

```
           G
         /  \
        /    \
       /      \
      D        K
     / \      / \
    C   F    I   M
   /   /    / \ /
  B   E     H J L
 /
A

```

So what is correct interpretation of this question?

Somehow, if we try to generalize, I feel this question boils down to following:

> Whether the minimum and maximum height of the binary search tree is constrained, if we fix certain elements of the binary search tree to particular position (as in this case the immediate children of the root)?

# Answer
> 0 votes
The question you were asked talks about 4 **levels**, which is a height of 3, not a height of 4.

Answer 1 is incorrect because there is a tree of height 3 in which G is at the root (you provided an example already).

Answer 3 is incorrect because of the following tree:

```
         F
       /  \
      /    \
     /      \
    B        J
   / \      / \
  A   D    H   L
     / \  / \ / \
    C   E G I K M

```

Answer 4 is incorrect because of the following tree:

```
           G
         /  \
        /    \
       /      \
      D        K
     / \      / \
    B   F    I   M
   /\  /    / \ /
  A  C E    H J L

```

Answer 2 is, as you answered correctly, the only true one.

To see this: Assume T is a tree which satisfies the constraints, i.e.

```
           1
         /  \
       /      \
     /          \
    B            K
  /   \        /   \
  2   3       4     5
 / \ / \     / \   /  \
6  7 8 9   10  11  12 13

```

Where the numbers 1 to 13 represent unknowns from A,C,D,E,F,G,H,I,J,L,M and two empty symbols.

As you can see, both the left and the right subtree can contain at most 6 elements. Thus, the root has to be $1 \in \\{F,G,H\\}$.

If $1=F$, then the right sub-tree has to contain {G, H, I, J, K, L, M}. However, K is the root of the right sub-tree and therefore $\\{4,10,11\\} = \\{G,H,I,J\\}$, which is impossible. Using symmetrical arguments we can show that the root cannot be H either.

Therefore it must be $1 = G$. But then $\\{3,8,9\\} = \\{C,D,E,F\\}$ which is a contradiction as well.

---
Tags: graphs, trees, binary-trees, search-trees
---


# Question
Title: How to find time complexity for functions in lazy functional languages?
So far, I have looked around the internet for information how to find the time complexity for functions in lazy functional languages, but most of the resources on time complexity focus on strict imperative languages, and there seems to be very little about finding time complexity in lazy functional languages.

The former resources are somewhat unsuitable for finding the time complexity of lazy functions. E.g.:

```
minimum = head . sort

```

For a good definition of sort, minimum will run in $\cal{O}(n)$ time even though head runs in $\cal{O}(1)$ time and sort can run in $\cal{O}(n * log(n))$ or $\cal{O}(n^2)$ time.

However if I wrote this function in a strict imperative language as

```
fun minimum(list):
    sort(list);
    return head(list);

```

and then tried to combine the complexities of the sort and head functions the way it is done with algorithms in strict imperative languages, then I would get that the minimum function will run in $\cal{O}(n * log(n)) + \cal{O}(1) = \cal{O}(n * log(n))$ or $\cal{O}(n^2) + \cal{O}(1) = \cal{O}(n^2)$ time.

Which is of course correct for the strict function, however it doesn't have to be very accurate for the lazy version of the same function as shown above. So using the same technique in lazy programming languages wouldn't be all that useful.

I think the difference comes in from the laziness, because it causes data to be computed only as much as they are required by the function using them. This is opposite to how it works in strict languages, where the function using the data has no control over how much the data gets evaluated by the function creating them.

This means that knowing the time complexity of *fully evaluating* a function, which is what one usually looks for when figuring out the time complexity of a function, isn't necessarily useful for knowing the time complexity of a function using data from this function unless said function evaluates the data fully.

So what **is** useful to know about one function to figure out the time complexity of another function using the resulting data from it inside a lazy functional language?

Is there a formal system that helps out with finding out the time complexity in this situation?

I know I could probably try evaluating the whole function by hand if I have source to all the functions that it uses, but I don't necessarily have that.

On similar note, if I don't have the source of a function and I only have a documentation to it, then what would the writer of said documentation need to include in the documentation for me to be able to accurately find the time complexity of a function that uses their function?

As said before, the time complexity of evaluating the function fully isn't enough. But what if they included time complexity of evaluating the first *i* elements of the list the function is generating? Would that be enough? If yes, then how could this be generalized to other data structures as well?

# Answer
I would consider an approach based on potential. Note that lazy evaluation changes the internal state of an object and therefore takes away an important advantage of functional programming.

As an example, imagine the following three functions

* sort : List $\rightarrow$ List. Sorts the list using Selection Sort.
* unique\_special : List $\rightarrow$ List. For every odd position $i$ in the input list, the element at that position is removed from the list if it is equal to the element at $i+1$.
* head : List $\rightarrow$ X. Finds the first element of the list.

Given a list $L$, I will use $\Phi(L)$ for its potential. $\Phi(L) : \\{1, \dots, |L|\\} \rightarrow \mathbb{N}$ is a function describing the cost of each element.

A "clear" list has a constant potential, i.e. $\Phi(L)(i) = 1$ for all indices $i$.

Let L be a list and sort(L) = L'. Then $\Phi(L')(i) = \sum\limits\_{j=1}^{|L|} \Phi(L)(j)$, because Selection Sort will have to look at every element in $L$ to find a minimal one. After this, $L$ is completely evaluated, i.e. it is not "lazy" anymore. This means the potential of every element is reduced to $\Phi(L)(i) = 1$. Here you can see the importance of the fact, that lazy evaluation can change within an object. If you assume that is not possible, for example by disallowing variables (e.g. via "where" in Haskell), the analysis becomes easier.

For unique\_special, consider again L' = unique\_special(L). To evaluate the first element, the next one has to be evaluated as well (to compare them). $\Phi(L')(1) = \Phi(L)(1) + \Phi(L)(2)$. Of course, would $L'(1)$ be evaluated, the potential of $L(1)$ and $L(2)$ would become 1.

Later elements require additional knowledge of whether the previous elements were deleted. You have $L'(2) = L(1)$ if the first element was deleted and $L'(2) = L(2)$ otherwise. Hence, $\Phi(L')(2) = \Phi(L)(1) + \Phi(L)(2)$ and $\Phi(L')(3) = \Phi(L)(1) + \Phi(L)(2) + \Phi(L)(3) + \Phi(L)(4)$.

Generalizing this formula results in $\Phi(L')(i) = \sum\limits\_{j=1}^k \Phi(L)(j)$, where $k = \lfloor \frac{i}{2} \rfloor \cdot 2$.

Finally, consider head(L). This does not create a new list, it just requires you to pay the potential of $\Phi(L)(1)$.

As you can see, this clearly increases the complexity of function definitions, especially if you want to include changing potential of the same data structure in your analysis. It gives you the opportunity for a more abstract analysis though:

Let $L$ be a completely evaluated / non-lazy list and the call head(sort(L))). The cost of this call will be $\Phi(\text{sort}(L))(1) = \sum\limits\_{j=1}^{|L|} \Phi(L)(j) = |L|$.

A second example: What is the cost of the call head(unique\_special(L')), where $L' = \text{sort}(L)$?

\begin{align\*} & \Phi(\text{unique\_special}(L'))(1) \\ =& \Phi(L')(1) + \Phi(L')(2) \\ =& \sum\limits\_{j=1}^{|L|} 1 + \sum\limits\_{j=1}^{|L|} 1 \\ =& 2 |L| \end{align\*}

You can put more detail into the description of $\Phi$ to observe more accurate results.

Regarding generalization to other data structures, I didn't think about that too much so far. It should be clear that similar structures such as queues work in a similar way. However, for example for a Union-Find structure, I can't think of a way my approach would give you any advantage.

An addition regarding non-linear data structures, for example binary search trees. While it is the easiest option, there is no definite need to use a set $\\{1, \dots, n\\}$ as the domain of $\Phi$. A common way to index the nodes of a binary tree is to use strings in $\\{0,1\\}^\*$. The root is labelled with the empty string $\varepsilon$ and for a node $v$, the left successor is $v0$ and the right successor is $v1$. For example, the following tree

```
   5
 4   8
1   6 9

```

would have the domain $\\{\varepsilon, 0, 00, 1, 10, 11\\}$.

Imagine a function delete : Tree $\times$ Node $\rightarrow$ Tree to remove a certain node from the tree. You need to check if either of the subtrees is empty. Let delete($T$, $v$) = $T'$, then the potential is $\Phi(T')(v) = \sum\limits\_{\substack{w \in \\{0,1\\}^\* \\ w \text{ is a descendant of } v}} \Phi(T)(w)$, where we assume $\Phi(T)(w) = 0$ if $w$ is not a node of $T$.
> 2 votes

---
Tags: algorithm-analysis, runtime-analysis, functional-programming
---


# Question
Title: What Does The Notation of Union Over K represent?
I am currently studying about polynomial time in Comp Theory. The definition for polynomial time given in my textbook as follows: $$P= \bigcup\_{k}TIME(n^k)$$ I have not seen the **Union over k** notation before. K is a constant. A quick introduction to the meaning of this notation would be enormously helpful.

Thank you

# Answer
Authors often leave out the domain of the union if it is clear within the context. Here, $k$ is a natural number, i.e. $P = \bigcup\limits\_{k \in \mathbb{N}} TIME(n^k) $. This is what it means for a complexity function to be bounded by a polynomial: there is a constant $k$ such that the function is in $\mathcal{O}(n^k)$.
> 3 votes

---
Tags: notation, mathematical-foundations
---


# Question
Title: Multiple matching in Maximum Flow problem?
I'm sorry if this has already been asked before, but I couldn't find any similar questions. The situation is as such:

Assume there are x restaurants, each with a capacity q, and y people, each of which can only eat from one restaurant. The x restaurants can only serve the people within radius r of its location. Try and find the maximum number of people that can be served by a restaurant and what restaurant each one must eat from.

My approach was to split it up into something similar to the bipartite matching problem. Have the x restaurants on one side and y people on the other. Then, I'd have a start node which connects to every restaurant using a directed edge of capacity q. Then, I'd connect all the y people with a directed edge of capacity 1 to a sink node, t. Lastly, I'd connect every restaurants to all the people within radius r using a directed edge of capacity 1.

Running the Ford-Fulkerson algorithm on this, however, might result in one restaurant serving less than they potentially could (for example, let's say we have two restaurants each with capacity 2, 4 people, and the first restaurant connects to the first three people and the second connects to the last two; then, if the path from the first restaurant to the third is augmented in the algorithm, we can only serve 3 people instead of an optimum of 4). My workaround to this is maybe augment an s-t path with the least amount of incoming edges to the person (so a situation like the above can be avoided), but this clearly slows down the efficiency significantly of the algorithm, as well as making it much more difficult to provide an argument saying it's optimal.

Is there any literature concerning problems like these, or any suggestions on how I can improve my approach? Thanks!

# Answer
> 1 votes
Your approach works. The situation you're worried about can't happen. It appears you haven't quite fully grasped how the Ford-Fulkerson algorithms yet, so focus on getting more familiar with it. It always finds the max-flow, and the max-flow always solves your problem.

The key misunderstanding is where you wrote:

> Running the Ford-Fulkerson algorithm on this, however, might result in one restaurant serving less than they potentially could

This is false. That actually can't happen. Work through the proof of correctness for the Ford-Fulkerson algorithm to understand why not: if there's a larger flow, then there will always be an augmenting path you can find to increase the size of the flow.

This was presumably an exercise to help you get acquainted with network flow algorithms, and it worked: it uncovered a gap in your understanding. This is great -- it means you have something yet to learn about how the algorithms work. What a great opportunity! Now you get to spend some time communing with a textbook learning this lovely subject. Have fun!

---
Tags: optimization, bipartite-matching, max-flow, ford-fulkerson
---


# Question
Title: Can we always reduce the weights of a weighted graph to rationals and preserve equality relationships?
Let $G = (Q, \Delta, W)$ be a *finite* weighted graph with $\Delta: Q \times Q$ and $W: Q \times Q \to \mathbb{R}^{+}$. Is it the case that there always exist a function $W': Q \times Q \to \mathbb{Q}^{+}$ such that $\forall S, S' \subseteq Q, \forall s, s' \in S$:

$$ \sum\_{s'' \in S'}{W(s, s'')} = \sum\_{s'' \in S'}{W(s', s'')} \Leftrightarrow \sum\_{s'' \in S'}{W'(s, s'')} = \sum\_{s'' \in S'}{W'(s', s'')} $$

?

I believe, at least for the finite case, this should be possible and I'm trying to prove this "constructively" by finding $W'$.

So let $\epsilon \in \mathbb{Q}^{+}$ be a rational such that $\forall s\_0,s\_1,s\_2,s\_3 \in Q, \epsilon \< |W(s\_0, s\_1) - W(s\_2, s\_3)|$ whenever that difference isn't $0$.

Obviously if we just round every non-rational weight in a grid with spacing $\epsilon$ we will not preserve equalities and I believe it'll be quite difficult to restore the exact relations.

So my idea is to round one weight at a time, and then fix the equalities that get broken by modifying only non-rational weights and repeating the process until there are only rational weights.

So start by taking two subsets $S, S' \subseteq Q$ and take $s \in S$ and $s'' \in S'$ such that $W(s, s'') \notin \mathbb{Q}$. Now we can round this number to the nearest rational of the form $k\cdot \epsilon$.

Let $e = W(s, s'') - W'(s, s'')$ is the error we introduced. Now if there was an $s' \in S$ and an $s'''$ such that $W(s', s''') = W(s, s'')$ then we modify that weight in the same manner, and thus the iff condition still holds for $s$ and $s'$.

Otherwise for $s' \in S$ we must have that some (more than one) weight $W(s', s''') \notin \mathbb{Q}$ and we can subtract $e$ from it and preserve the condition for $s$ and $s'$ with respect to $S$ and $S'$.

However we have now changed some other weight, and thus while we may have preserved the equality between $S$ and $S'$, we may have broken it for other subsets. So we have to consider every subset that is either a subset or superset of $S$ and $S'$, verify if we have broken that *iff* condition, and if so we must find an other weight and change it, and repeat the process until it we find an equilibrium. But does this actually happen?

My question is:

1. Does there exist such $W'$ or am I trying to build a non-existent function?
2. If $W'$ exists, is the above approach feasible in some way, or should I completely change strategy in order to find $W'$? Do you know any particular trick that can help in devising $W'$?

# Answer
Identify $W$ with the set of all weights. Let $B$ be a basis of $W$ over the rationals. That is, you can write every weight in $w$ as a linear combination of elements of $B$ with rational coefficients. You can identify the weights with vectors $\vec{w}$ of length $|B|$. Each linear dependency that you want to avoid can be thus encoded as an inequality $$ \sum\_i \alpha\_i b\_i \neq 0, $$ where the coefficients $\alpha\_i$ are not all zero. We can moreover assume that the $\alpha\_i$ are integers (by taking a common denominator).

Let $M$ be an integer larger than all $|\alpha\_i|$ appearing in an inequality you are interested in. If we replace $b\_i$ with $M^i$ then all the requisite inequalities will be satisfied, while all *equalities* will also be preserved.
> 3 votes

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


title: What is an upright rectangle?

text:
# Question
Title: What is an upright rectangle?
What is an upright rectangle?

I came across the phrase in my homework -

"The bounding box of a set of S points is the smallest upright rectangle containing S. Describe and analyze an algorithm to compute the bounding box of n points in the plane using fewer than 3n comparisons."

Can anyone explain to me what is meant by an upright rectangle?

# Answer
Most likely it means an axis-aligned rectangle, i.e., a rectangle whose bottom edge is horizontal (parallel to the $x$-axis) and whose left edge is vertical (parallel to the $y$-axis). This is the standard meaning of "bounding box". For future reference, before asking it is useful to check Wikipedia and search thoroughly. In this case you would have found lots of information on the phrase "bounding box": see, e.g. https://en.wikipedia.org/wiki/Minimum\_bounding\_box and https://en.wikipedia.org/wiki/Minimum\_bounding\_rectangle
> 4 votes

# Answer
(Yes, today I had nothing better to do)
> 2 votes

---
Tags: terminology, computational-geometry
---


# Question
Title: Need help in a question regarding polynomial oracle reductions
Prove the following:

If there is a polynomial oracle reduction from $S1$ to $S2$:

a. If $S2\in\ P$ so $S1\in\ P$

b. If $S2\notin\ P$ so $S1\notin\ P$

The way I see it - If there is a polynomial oracle reduction from $S1$ to $S2$, you can solve $S1$ with $n^k$ questions to $S2$. If $S2\in\ P$, and $S2$ is solved with $n^k$ actions, it means $S1$ can be solved in $n^{n^k}$ actions - $\in\ P?!$

(I translated the phrase 'polynomial oracle reduction' from hebrew, so ask me if you don't understand what I meant).

# Answer
Hint: Since $S\_1$ runs in polynomial time, say $O(n^a)$, every input to the oracle has polynomial length $O(n^a)$. If $S\_2 \in \mathsf{P}$, say can be decided in polynomial times $O(n^b)$, then we can simulate all the oracle calls in $O(O(n^a)^b)$.
> 0 votes

---
Tags: complexity-theory, reductions, oracle-machines
---


# Question
Title: What is the asymptotic running time of the following piece of code?
I am working with this problem:

**What is the asymptotic running time of the following piece of code?**

```
if (N < 1000)
   for (int i = 0; i < N*N*N; i = i+1) A[i] = j;
else if (N < 10000)
   for (int i = 0; i < N; i = i+1) A[i] = j;
else
  for (int i = 0; i < N*N; i = i+1) A[i] = i;

```

Where the possible answers are:

* A) linear in N
* B) linearithmic in N
* C) cubic N
* D) quadratic in N

I am unsure how to calculate it, but when I look at the code I think A and B is not the right answer, because of the for-loops multiply with the variable x-times. If possible, could someone also explain what "Asymptotic time" means?

# Answer
An easy way to intuit asymptotic notations goes like this. Say you have a number $n$ and a constant $c$. Now $n^2$ will always be greater than $n\*c$ for any choice of $c$ where $c \< n$. So no matter what the constant coefficient is, it will never exceed $n^2$.

Now your question. Asymptotic notations are calculated for *sufficiently large values of n* where sufficiently large is usually taken as infinity. So although your algorithm has $n^3$ and $n$ time complexities for smaller values of $n$, for *large* values ($n$ tends to infinity), the time complexity is $n^2$.
> 0 votes

# Answer
If you analyze the pseudocode, if we make N very large, it would correspond to the else part of your code. The loop would run for $n^2$ iterations in this scenario. However, for fairly small values of N, the first two conditions are satisfied.

We are generally interested in the Worst Case Running time of a piece of code. This typically happens for very large inputs. You could argue that since the first if condition iterates the loop for $n^3$ time, the complexity would be $n^3$. However, the subtlety here is that as N gets larger and larger, `for (int i = 0; i < N*N; i = i+1) A[i] = i;` is dominant. Hence it would be quadratic in $n$.

A good reference for asymptotic complexity is : https://www.cs.cornell.edu/Courses/cs3110/2012sp/lectures/lec19-asymp/review.html

What's important in the definition for your code is the part which says

> there exists a fixed constant $c$ and a fixed $n\_0$ such that for all $n≥n\_0 , f(n) ≤ cg(n).$

The $n\>=n\_0$ implies a bound from where the function begins to blow up. In this case, it is the larger values of N.
> 0 votes

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


# Question
Title: What to infer about maximum height of AVL tree from these three different formulae
I have came across following problem:

> What is the maximum height of any AVL-tree with 7 nodes?

The recurrence giving number of nodes $n$ in the AVL tree for given height $h$ is as follows:

> $n(h)=n(h-1)+n(h-2)+1$
>
> $n(0)=1$
>
> $n(1)=2$

So if we follow this recurrence, we get the height of the AVL tree with 7 nodes = 3 as follows

$n(2)=n(1)+n(0)+1=2+1+1=4$

$n(\color{red}{3})=n(2)+n(1)+1=4+2+1=7$

However I find two formulae, both listed on this page:

1. The first one is stricter one:

> $h \< 1.475 \times log\_2(n(h)) - 1.475$

According to this formula, I get

$h \< 1.475 \times log\_2(7)-1.475$

$h\<\color{red}{2.665}$
2. The second one is rough estimate and it is taken from Goodrich's book:

> $h \< 2 \times log\_2(n(h)) + 2$

According to this formula, I get

$h \< 2 \times log\_2(7) + 2$

$h\<\color{red}{7.61}$

So with these different answers, I don't get what should I infer. Am I doing any miscalculations? Or should I just stick to what is yielded by recurrence and ignore formulae as they are mere estimates? Or should the first formula have ceil function to give perfect answer rather than the estimates as follows?

$h \color{red}{=} \color{red}{\lceil} 1.475 \times log\_2(n(h)) - 1.475 \color{red}{\rceil}$

# Answer
Perhaps the simplest way out is to solve the recurrence explicitly. Let $m(h) = n(h) + 1$. Then $m(h)$ satisfies the recurrence $$ m(h) = n(h) + 1 = n(h-1) + n(h-2) + 2 = m(h-1) + m(h-2). $$ The initial conditions are $m(0) = 2$ and $m(1) = 3$. Define $F(h) = m(h-3)$, so that $F(3) = 2$, $F(4) = 3$, and $F(h) = F(h-1) + F(h-2)$ for $h \> 4$. It is well-known that $$ F(n) = \frac{1}{\sqrt{5}} \left\[\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right\]. $$ Since $m(h) = F(h+3)$ and $n(h) = m(h)-1$, we see that $n(h) = F(h+3)-1$ and so $$ \begin{align\*} n(h) &= \frac{1}{\sqrt{5}} \left\[\left(\frac{1+\sqrt{5}}{2}\right)^{h+3} - \left(\frac{1-\sqrt{5}}{2}\right)^{h+3}\right\] - 1 \\ &= \frac{2+\sqrt{5}}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^h - \frac{2-\sqrt{5}}{\sqrt{5}} \left(\frac{1-\sqrt{5}}{2}\right)^h - 1. \end{align\*} $$ The second term is very small, and in particular $$ \frac{2+\sqrt{5}}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^h - 2 \< n(h) \< \frac{2+\sqrt{5}}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^h. $$ This shows that $$ \log\_{(1+\sqrt{5}))/2} n(h) \< h + \log\_{(1+\sqrt{5}))/2} \< \log\_{(1+\sqrt{5}))/2} \[n(h)+2\], $$ from which you can deduce whichever excellent bounds you want.
> 2 votes

---
Tags: algorithm-analysis, data-structures, binary-trees, search-trees, balanced-search-trees
---


# Question
Title: Confusion in Banker's Algorithm: How resources are allocated?
I have seen examples about `Banker's Algorithm` from this Wikipedia link, this book and many other places. In all these examples some processes are allocated resources *less* than their *Max Need*.

For example, consider the state of system as shown in below given image taken from Wikipedia link:

Here you can see that the process P1's **Max Need** is `3 3 2 2` and the **total available** resources are `6 5 7 6`. But the system allocates `1 2 2 1` resources to P1. Although it could allocate all the requested resources to P1 and P1 would have completed.

So my questions are:

* Why does the system allocate **partial / incomplete** resources even when it has the resources available
* If the allocation of **partial / incomplete** resources is allowed, then why does the system / algorithm enforce that *the number of requested / needed resources should be less than the available resources (at the time of request)?*. The system could allocate **some** resources (available at the time of request) to process(es) and the remaining would have been assigned when released by other processes.

OR

The process has to tell the number of resource types (and their instances) in advance, but does not need to be assigned all resources at a time; rather it is assigned resources when ***actually*** needed?

Please correct me if I am wrong.

# Answer
The *maximum resources* are an estimate by the process of what they *might* need, the *currently allocated* is what the process holds at the moment. The idea is that processes request more resources as they need them (and at those points you run the algorithm to see if it could lead to deadlock to grant the resources asked for, by seeing if there is a process that could finish and release all it holds if it goes on to ask for it's maximum announced request, releases what it holds, and so on). If a process releases resources, that clearly can't lead to a deadlock, thus no special handling (except for recording what is free now) is needed.

Think of you e.g. building a box out of wood, and the tools needed. You'll need a saw, a drill, a screwdriver, among other tools. You'd announce that, but you won't require all together, while you are busy with the saw somebody else could use the drill and screwdriver, so it doesn't make sense to ask for all at the start, or keep all until finished.
> 1 votes

---
Tags: operating-systems, deadlocks
---


# Question
Title: Need help understanding a derivation of "witnesses" for a Landau bound
So here's an excerpt from *Foundations of Computer Science* by Alfred Aho and Jeffrey Ullman\[1\]. I've also found basically the same material in a few other places, and also in my discrete math textbook, but this is clearest one I've seen:

> **Example 3.2.** Suppose we have a program whose running time is $T(0) = 1$, $T(1) = 4$, $T(2) = 9$, and in general $T(n) = (n + 1)^2$. We can say that $T(n)$ is $O(n^2)$, or that $T(n)$ is *quadratic*, because we can choose witnesses $n\_{0} = 1$ and $c = 4$. We then need to prove that $(n + 1)^2 \leq 4n^2$, provided $n \leq 1$. In proof, expand $(n + 1)^2$ as $n^2 + 2n + 1$. As long as $n \leq 1$, we know that $n \leq n^2$ and $1 \leq n^2$. Thus $n^2 + 2n + 1 \leq n^2 + 2n^2 + n^2 = 4n^2$.

Even so, I get lost where it says:

$$ n^2 + 2n + 1 \leq n^2 + 2n^2 + n^2 $$

I get that it's *true*, but it seems arbitrary. How/why did the expression get modified on the right side of the $\leq$ like it did? Couldn't they also have done this?

$$ n^2 + 2n + 1 \leq 4n^2 + 0 + 0 $$

Specifically, what rule did they apply to transform the expression $n^2 + 2n + 1$ into $n^2 + 2n^2 + n^2$?

---

1. http://infolab.stanford.edu/~ullman/focs.html

# Answer
They want to end up with  constant * n2  on the very-right.
They applied "make each term a constant times n2".
> 4 votes

# Answer
Claim:

$$ n^2 + 2n + 1 \le 4n^2$$

we know it is true, but we still need to prove it.

One option, is to shift sides, getting $3n^2-2n+1 \ge 0$, and solving this equation shows it holds for any $n\ge 1$. But this is cumbersome.

What else can we do? We can take a crude bound for each term. For instance, $n^2 \le n^2$, $2n \le 2n^2$, and $1\le n^2$ hold **for any $n\ge1$**! Therefore, it is valid to say that $$n^2 + 2n + 1 \le n^2 +2n^2 +n^2 \le 4n^2.$$ and it is quite *intuitive* and easy to see, even for the non-expert.

What's wrong with $n^2 + 2n + 1 \le 4n^2 + 0+0$?
*Technically*, nothing is wrong - this is a valid claim for any $n\ge 1$.
However **intuitively** this derivation is misleading: it suggests that we bound the three terms one by one, which "suggests" the **incorrect** derivation of $n^2 \le 4n^2$; $2n \le 0$; and $1\le 0$.

Bottom-line: since Aho-Ullman is meant for students, it tries to give simple explanations that any reader can easily verify in the most simple way, even if it is longer and less "direct".

---

(actually this is not a CS question, but math. Hmpf.).
> 4 votes

---
Tags: landau-notation, didactics
---


title: Need for an augmented grammar

text:
# Question
Title: Need for an augmented grammar
The question is under the concept of LR parser. Suppose the original grammar is
S-\>AA
A-\>aA|b

Is it necessary to add an additional rule S'-\>S to make it as augmented grammar? In short, I want to know the use of augmented grammar.

# Answer
Yes, if you follow the canonical conversion of augmented grammars, a first step is adding a new start symbol $S'$ and the production $S' \to S$, since the algorithm may later "change" $S$.

However, it may not be necessary at all times. If you ask whether or not it is necessary specifically in this case, why don't you try without it and check if you get a valid answer?
> 3 votes

---
Tags: formal-grammars, parsers, lr-k
---


# Question
Title: How does the OS Scheduler give/take control of HW?
Imagine a uniprocessor system with a simple operating system with non-threaded processes and basic virtual memory (paging, no segmentation, no replacement to disk, etc).

Now assume a simple preemptive scheduler, round-robin, for example.

Because it is a uniprocessor, the scheduler **must** hand over control of the processor momentarily for any other processes it schedules to run. How does it regain control? It can't generate interrupts, as it is not running.

I originally assumed there must be some kind of register containing the time to return control to the scheduler, and a register pointing to the location of the scheduler. But if these registers existed, what would a nonpreemptive scheduler do with them? How would the processor know the difference between a preemptive and nonpreemptive scheduler, i.e. how would it know whether to use the registers to return, or allow the process to run to completion?

# Answer
> 2 votes
Your idea of interrupts is correct, but not how it works. The scheduler program will not raise an interrupt.

Let's take the round robin algorithm you have mentioned. A process is going to run for a period of time and then is supposed to relinquish the CPU. How does this work? Interrupt. It is the operating system that raises this interrupt using what is called an interval timer. The interval timer is programmable and is set to the time slice value of the round robin algorithm.

Once the interrupt is raised, the time quantum for the current process expires and the control is given to the scheduler process.

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


title: Give regular expression on language

text:
# Question
Title: Give regular expression on language
What is a regular expression for $L\_1=\\{a^{2n} b^{3m+1} \mid n \geq 1, m \geq 0\\}$?

# Answer
> 0 votes
Hint: Write $L\_1$ as a concatenation of two languages: $\\{ a^{2n} \mid n \geq 1\\}$ and $\\{b^{3m+1} \mid m \geq 0\\}$.

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