# Question
Title: The order of which time complexity is higher, 3 ^ log(n) or n ^ 3?
Which one has a higher order time complexity:

* $n ^ 3$
* $3 ^ {\log n}$

I know that an exponential time order is higher than polynomials. However, it uses a logarithmic power which is low for a large n, while n^3 or more could remain still high, not?

# Answer
The answer easily follows from the identity $3^{\log n} = n^{\log 3}$. Whether or not $\log 3 \< 3$ depends on the basis of the logarithm.
> 3 votes

---
Tags: time-complexity
---


# Question
Title: Complexity of the problem to determine if a spanning tree exists inside a connected graph
Given a connected graph G, what is the complexity of the problem to determine if a spanning tree with a number of leaves less or equal to k exists inside G? I don't really know how to determine it and how to reach a proper solution to this.

# Answer
When $k = 2$, this is just the Hamiltonian path problem, which is known to be NP-complete.
> 0 votes

---
Tags: complexity-theory, graphs
---


# Question
Title: Runtime analysis of bit sorting algorithm with input size and integer size
I'm struggling to analyze the runtime of this algorithm mainly because it depends on two parameters - the length of the input n, and also the bit size of individual n (bitnum). Most documentation I can find solve recursion based on n solely. The algorithm is:

```
def sortB(seq,bitnum):
    # length of seq
    n = len(seq)
    lists = []
    for j in range(0,256):
        lists.append([]);
    for i in range(0,n):
        bits = (seq[i] >> bitnum) & 255;
        #print("bitnum :", bitnum)
        #print("seq[i] :", seq[i] >> bitnum)
        lists[bits].append(seq[i]);
        #print("bits ",bits)
    i = 0;
    for j in range(0,256):
        seqj = [0]*len(lists[j])
        k = 0
        for m in lists[j]:
            seqj[k] = m
            k = k + 1

        if (bitnum > 0):
            bitnum = bitnum - 8
            seqj = sortB(seqj, bitnum)

        for m in seqj:
            seq[i] = m
            i = i + 1

    return seq

```

I tried to think about this and basically I get this far:

Because the recursion happens based on the number of times bitnum is decremented by 8 $b = bitnum$

$T(n,b-8)$

I solve the recursion of $T(b) = 256T(b-8)$

and I get T$(b) = 256^{(b/8)}$ which simplifies to $2^{(b)}$

Therefore, the whole algorithm gets multiplied by a factor of $2^{b}$: I get a runtime of $O(2^{b} n)$ which is in $O(n)$? But I feel this is wrong since the upper bound on the running time isn't taking this new factor (b) into account.

# Answer
> 2 votes
If you treat $b$ as a constant, then $O(2^b n)$ is $O(n)$, and $O(n)$ is right.

If $b$ is not a constant, $O(2^b n)$ is not $O(n)$.

I think it would help to review Landau notation. The running time is whatever it is; it is some value $T(n,b)$ that depends on both $n$ and $b$. The big-O notation helps us understand how this value grows as you increase $n$ but hold $b$ fixed, or how it grows as you increase both $n$ and $b$. You have to decide which of those you want to understand (do you want to understand its behavior as you increase $n$ while holding $b$ fixed? do you want to understand how it grows when you increase $b$ while holding $n$ fixed? do you want to understand how it grows when you increase both of them? that will lead to different results and different ways of applying big-O notation).

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


# Question
Title: Data addresses with ADD instruction in various architectures?
How many data addresses are specified in an `ADD` instruction in accumulator based architecture, stack based architecture, and in the most common register-based architecture?

I'm not sure what I should look at - diagrams? Assembly code? Thank you for any help in advance!

# Answer
First some terminology:

Let's consider the ADD operation that is a logically three operand operation: two sources and one target, so these 3 are the maximum that could be provided.

A (hardware) machine instruction is subdivided into fields, the main one of which is the opcode field. The instructions can also be fixed-length or variable length.

An addressing mode is a way of specifying what memory address (i.e. data address) to use for reading or writing. The architectures that you are asking about vary in the instructions that allow for addressing modes as fields in the instruction. Typically, the fields associated with an addressing mode require a fair number of bits, such as 12, 16, 20 or more because they contain parts of memory addresses.

---

In a stack-based architecture, operations such as ADD implicitly target the stack, for both sources as well as for the target. So, an ADD instruction has just one field, the opcode field, and will have no instruction set fields regarding source and target. Initial operands are moved to the (expression) stack using PUSH instructions and popped of this stack using STORE (or POP) instructions. It is the PUSH & STORE instructions that have the potential to indicate sources and targets that reference memory (e.g. data addresses). The following accomplishes an ADD in a stack architecture.

```
PUSH  item1
PUSH  item2
ADD
STORE item3

```

item1, item2, and item3 would be considered addressing modes within those instructions, and might allow access to local variables and global variables. Because the PUSH & STORE instructions have additional fields beyond the opcode whereas the ADD instruction does not, stack machine architectures typically use varying length instructions. The hardware advances the PC by the right amount for each instruction so that it can execute the logically following instruction. When several computations (multiple ADD or ADD & SUB, etc..) are combined the stack machine can use the stack to transfer intermediate computations without intervening PUSH & POP instructions.

---

In an accumulator-based architecture, you will typically have opcodes with one addressing mode. The following sequence would be typical of them:

```
LOAD  item1
ADD   item2
STORE item3

```

You can see that a similar code sequence has one less instruction, and the instructions tend to be more regular. As a result of this, accumulator machines might choose a fixed length instruction set (e.g. 16-bits). The accumulator is implicitly sourced and targeted and does not require an instruction field.

---

A RISC register architecture, like MIPS will have a large number of registers (e.g. 32 or more), and support three operand instructions, though only between registers. Memory operations will require separate LOAD and STORE instructions.

```
LOAD  r1, item1
LOAD  r2, item2
ADD   r3,r1,r2
STORE r3, item2

```

Here we have a longer sequence for the same operation; however, the RISC machine has so many registers that the idea is to use them instead of memory for local variables and such. Thus, many of the loads and stores you might otherwise expect are eliminated.

---

x86, for the most part, is two operand machine. It has more registers than your single accumulator machine, but fewer than a RISC machine. Most instructions on x86 allow specifying a register number and an addressing mode, which might refer to another register or might refer to a memory addressing mode.

```
MOV AX, item1
ADD AX, item2
MOV item3, AX

```

Like the RISC machine, the 8 or so registers can be used for heavily used local variables, reducing the memory access. However, will fewer registers the advantage isn't as good as with a RISC machine.

---

There are considerable trade-offs between these various architectural approaches to instruction set architecture. Generally speaking, the stack machines result in smaller code space, because of their variable length instruction sets. Code space has a huge impact on instruction cache performance, so the smaller the code, the better. However, by comparison with RISC machines with their fixed-size instructions, the variable length instructions (and more of them) require substantially more complex decoding hardware, which either costs transistors or sacrifices performance.
> 2 votes

---
Tags: computer-architecture, stacks
---


# Question
Title: Perceptrons: Functions not learnable without bias
I am trying to determine which functions are not learnable without a bias when building a perceptron. The set of functions I need to evaluate is {NOT, OR, AND}.

Could someone help interpret these results?

AND FUNCTION

https://i.stack.imgur.com/5sbuj.jpg

OR FUNCTION

I get a divide by 0 error in my script.

NOT FUNCTION

https://i.stack.imgur.com/yVcXw.jpg

It would appear that the AND function does not crash like the OR function but the end result is incorrect. The OR function simply won't graph due to a divide by 0 error. The NOT function appears to still be learnable.

If desired, I can post my python script with how I generated these graphs. I am using a sigmoid activate function.

# Answer
If you don't have a bias, your perceptron learns the function

$$y = w\_1 \cdot x$$

This means the decision boundary is a line through (0, 0).

## AND

$y, x, w\_1 \in \mathbb{R}^2$

Function table:

```
x_1 x_2 y
---------
0   0   0
0   1   0
1   0   0
1   1   1

```

This is not learnable.

> I am using a sigmoid activate function.

Without a hidden layer, a Perceptron is still a linear classifier.
> 0 votes

---
Tags: machine-learning, perceptron
---


# Question
Title: Do unconditional branches cause control hazards?
Do unconditional branches, such as `jump`/`goto` instructions cause control hazards? If so, why?

I am wondering because if unconditional branches did cause control hazards, that is like saying if `A` were the `jump foo` instruction and another instruction `B` was the first one under `foo:`, `B` would have a control dependency on `A`. While this is technically true, I don't see how this would cause a hazard in a pipeline since we know with 100% certainly that `B` will be executed since an unconditional `jump` instruction `A` preceded it.

# Answer
> 3 votes
YES, unconditional jumps can cause a control hazard in a pipelined machine.

> we know with 100% certainly that B will be executed since an unconditional jump instruction A preceded it.

Well, *we* know, but the CPU does not know. I mean, the CPU does know that we need to jump to B, but only after the CPU decodes the jump instruction and realizes that the instruction is a jump (to B). Until that point thee CPU *did not know* it is about to jump and during that period it continued inserting other instructions to the pipe (not necessarily from B).

When the CPU finds out it has a jump it is "too late": the pipe is already contaminated with other instructions.

In your example, the "contamination" is in fact the correct code, but in the general case it may a different code segment.

# Answer
> 0 votes
Not in the sense you probably mean. An unconditional branch cannot be mispredicted, and most architectures would be designed to avoid delays, such as by prefetching. Some ISAs even introduced mechanisms such as a delay slot to keep the pipeline full.

In a broad sense, sure, it could happen: for example, if a given CPU doesn’t have the next instruction to be executed in its cache, it needs to wait. One situation where this might come up is if a JIT compiler needs to write out some instructions and then run them, possibly on another core.

---
Tags: computer-architecture, cpu-pipelines
---


# Question
Title: What is the difference between $AC^2$ and $FO (\log \log n)$ complexity classes?
$FOLL$ or $FO (\log \log n)$ is a complexity class of all problems solvable by uniform poly-size circuit families of unbounded fan-in and depth $O(\log \log n)$.

$AC^2$ is a complexity class of all problems recognized by boolean circuits with depth $O(\log ^{2}n)$ and polynomial number of unlimited fan in AND and OR gate.

> Question. : What is a difference between $FOLL$ and $AC^2$?

In the definition of $FOLL$ they have used "uniform " poly-size and in the definition of $AC^2$ they are saying boolean circuits.

# Answer
> 3 votes
The functions $\log \log n$ and $\log^2 n = (\log n)^2$ are quite different. The latter grows much faster than the former: $\log \log n = o(\log^2 n)$. This shows that FOLL is a subset of AC2 (and even of the smaller class AC1).

Uniformity is a different aspect in which the two classes differ: FOLL is a class of uniform circuits, whereas the AC hierarchy captures non-uniform circuits. As such, even AC0 circuits can compute uncomputable functions, something that FOLL cannot do.

---
Tags: complexity-theory
---


# Question
Title: Finding the number of ways to partition $\{1,...,N\}$ into $P_1$ and $P_2$ such that $sum(P_1) = sum(P_2)$ for a given $N$
I am trying to think of how to optimize the following problem:

Let $S = \\{1,2,...,N\\}$. How many ways can $S$ be partitioned into non-empty subsets $P\_1$ and $P\_2$ such that $sum(P\_1) = sum(P\_2)$? I have implemented an algorithm that checks all partitions of $S$ into 2 subsets $P\_1$ and $P\_2$, but I am wondering if there is a faster algorithm.

# Answer
> 4 votes
Hint: find a recurrence $f(n, k)$ that tells you in how many different ways you can sum to $k$ using the first $n$ integers (ignoring order and using numbers at most once). Then the answer to your problem is $\frac 1 2 f(n, n(n+1)/4)$.

The trick is to realize that the sum of $P$, is $S= \displaystyle \sum\_{k=1}^n = \frac{1}{2}n(n+1)$, and that if you partition a set in two with equal sums, both halves must sum to $\frac{1}{2}P$. After counting the number of ways to sum to $\frac{1}{2}P$ we must still divide by two due to order, as for example the partition $(\\{3\\}, \\{1, 2\\})$ is the same as $(\\{1, 2\\}, \\{3\\})$.

# Answer
> 1 votes
This is A058377, possibly up to a normalization by 2. Since the sum of $P\_1$ has to equal $n(n-1)/4$, the number of solutions is zero when $n \equiv 1,2 \pmod{4}$ (since $n(n-1)/2$ is odd for such values of $n$).

---
Tags: algorithms, optimization, sets, partitions
---


title: Convex hull of fixed size

text:
# Question
Title: Convex hull of fixed size
I have heard that the quickhull algorithm can be modified if the size of the convex hull (the number of points it consists of) is known beforehand, in which case it will run in linear time. What modifications are required in order to decrease the time complexity of the convex hull algorithm?

# Answer
It is not true. As you know, we can reduce sorting numbers to finding convex hull (see here). So, we know that size of the convex hull, in this case, is $N$. However, we can't compute convex hull in nearly linear time! as lower bound for sorting numbers in general case is $\Omega(n\log n)$.

Anyhow, we have an algorithm to finding convex hull which is output-sensitive and can be run in $O(n\log h)$, which $h$ is the size of convex hull (see here). Hence, if you know the size of the convex hull such that its size is constant, you can compute convex hull in linear time.
> 3 votes

---
Tags: algorithms, time-complexity, convex-hull
---


# Question
Title: Obtaining a recurrence from a rational generating function
Looking at some Generating functions of a series, I have conjectured -

If $G(x) \ =\ \frac{1}{1-x^{t\_1}-x^{t\_2}-...-x^{t\_n}}$, then the recurrence equation of the the series is -

$a\_n = a\_{n-t\_1}+a\_{n-t\_2}+...+a\_{n-t\_n}$

How can I prove or disprove this?

# Answer
> 1 votes
Suppose that $$ G(x) = \sum\_{n=0}^\infty g\_n x^n. $$ Using the given equation (ending at $i\_m$, a better choice of variables), we have $$ 1 = (1-x^{i\_1}-\cdots-x^{i\_m}) G(x) = \sum\_{n=0}^\infty (1-x^{i\_1}-\cdots-x^{i\_m}) g\_n x^n = \\ \sum\_{n=0}^\infty g\_n x^n - \sum\_{n=i\_1}^\infty g\_{n-i\_1} x^n - \cdots - \sum\_{n=i\_m}^\infty g\_{n-i\_m} x^n = \\ \sum\_{n=i\_m}^\infty (g\_n - g\_{n-i\_1} - \cdots - g\_{n-i\_m}) x^n - H(x), $$ where $\deg H(x) \< i\_m$. Comparing coefficients, we find out that for $n \geq i\_m$, $$ g\_n = g\_{n-i\_1} + \cdots + g\_{n-i\_m}. $$

More generally, you could have allowed coefficients in front of the monomials.

---
Tags: combinatorics, recurrence-relation, generating-functions
---


# Question
Title: How to handle dfa with countless states?
I have a question regarding DFA:

*Design a DFA M with alphabet $\sum = \ {\\{0,1,2,R}\\}$ where the states remember actual sums of the number, except that the sum is reset to 0 whenever the symbol $R$ appears. Show diagrammatically how this DFA can be constructed. What is the problem with this DFA?*

One thing I do understand is that in order to remember the actual sums I would have to have the sums as states. But sums can be any number from 0 to infinity. So would the states increase exponentially while reading the input string? How can I tackle this problem?

# Answer
> 3 votes
You seem to have missed the last sentence of the question:

> What is the problem with this DFA?

The problem with this DFA is that it isn't finite (so it's not really a DFA).

A DFA is a *static* object — the only way it interacts with the environment is by switching states.

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


# Question
Title: Complexity of Two problems graphs with cycle
I want to determine the complexity of these two problems (with a given k):

1) Determine if the graph G has a cycle of length less or equal than k;

2) Determine if the graph G has a cycle of length equal or more than k.

For the first problem, I think it is NP-complete because it is NP (but why?) and because we can reduce the HAM-CYCLE problem to it (but how?)

I don't know what to say about the second problem. Can you help me solving this and can you help me telling me what is a good method to solve these kind of problems?

# Answer
> 2 votes
The first problem can be answered by finding the length of the shortest cycle in $G$, a parameter known as the *girth* of $G$. Indeed, if $G$ has girth $g$ then $G$ contains a cycle of length at most $k$ iff $g \leq k$. You can use BFS to find the girth efficiently, see for example these course notes. Therefore this problem can be solved in polynomial time.

The second problem is NP-complete by reduction from Hamiltonian cycle, as you mention (just choose $k = n$).

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


title: Example request for Monotone 1 in 3 SAT

text:
# Question
Title: Example request for Monotone 1 in 3 SAT
I know that monotone 3SAT is NPComplete. Also, 1 in 3SAT is NPComplete. I think both conditions together also leave the problem NP Complete (need confirmation).

If possible can someone please help with the smallest non trivial problem of this form that is unsatisfiable. Would be grateful.

# Answer
> 1 votes
How about $(x\_1 \lor x\_2 \lor x\_3) \land (\bar{x}\_1 \lor \bar{x}\_2 \lor \bar{x}\_3)$?

---
Tags: complexity-theory
---


# Question
Title: The complexity of checking the correctness of the problem solution on the Turing machine
There is a powerful simulation of Turing machine. At the input it takes problems of class P. At the output it gives solution for the problem. So, is it easier (in complexity theory) to test the correctness solution of the given problem than to solve this problem? If checking the solution is really easier than solving the problem, how much?

The practical side of my question is based on the fact that there is a large network of distributed computing. People for the award offer the power of their computers (their GPUs) to solve various problems from other people (from customers). We need an effective algorithm of protection against fraud when a person sends the wrong solution. If checking the correctness of the solution is really much easier than solving the problem, the customers themselves could easily check on their computers the correctness of the sent answers for which they pay. The most common problems are related to the solution of linear homogeneous integral equations and solved in a fraction of seconds, but in general the problem can be any of the class P. Thank you! I really hope for an answer.

# Answer
> 1 votes
What you might be looking for is an application of probabilistically checkable proofs (PCPs) for verifying computation. People have been working lately on making this practical, see for example Computational integrity with a public random string from quasi-linear PCPs, and other works by Eli Ben-Sasson and Alessandro Chiesa. At the moment this is unfortunately still a mostly theoretical concept.

---
Tags: algorithms, complexity-theory, algorithm-analysis
---


# Question
Title: How do we show that the polynomial time reduction of one problem to another has been done in polynomial time?
I have just been reading through a SO post which proves that the Halting Problem is NP-Hard. Whilst this is an easily followed proof, one slight slight aspect of it has left me scratching my head: it says that

> "This pairing can be done in polynomial time, because the Turing machine has only constant size."

So their justification for saying that the reduction was done in polynomial time is that the Turing machine 'only has constant size'.

Why would this prove that the reduction was done in polynomial time?

# Answer
> 5 votes
The reduction described in the mentioned post, from SAT to the halting problem, performs the following mapping:

$$\varphi\mapsto \big(\langle M\rangle,\varphi \big)$$

where $\varphi$ is a CNF formula and $M$ is the Turing machine which given a CNF $\psi$ as input, iterates over all the possible assignments to the variables of $\psi$, and enters a loop iff no satisfying assignment was found.

The machine $M$ does not depend on the input of the reduction, so it has some constant size description independent of the input $\varphi$. This means that you can output $\langle M \rangle$ in polynomial (even constant) time relative to the size of $\varphi$, hence the reduction is computable in polynomial time.

Note that you only need to show that you can generate $\langle M \rangle$ in polynomial time, which does not necessarily mean it has to have a constant size. Suppose e.g. that we want to show that $L=\\{\langle M\rangle | \text{M halts on input $\epsilon$}\\}$ is NP hard. In that case, the reduction $\varphi\mapsto \langle M\_{\varphi}\rangle$ does the trick, where $M\_{\varphi}$ is the machine which ignores its input, iterates over all possible assignments for $\varphi$, and enters a loop if no satisfying assignment was found. $M\_{\varphi}$ does not have a constant size description, since you have to hardcode $\varphi$ into it. However, you can still generate $\langle M\_{\varphi}\rangle$ in polynomial time, which makes the reduction polynomial.

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


# Question
Title: What is a logical approach to developing an algorithm which can find the optimal parameters for a function which make it best fit a given data set?
Consider the highlighted columns in the following table:

Starting with 100,000 newborns, $l\_{x+2}$ denotes the number of individuals in the sample still alive at age $x+2$. If we consider Makeham's law of mortality, defined by the function $$ S\_0(x) = \exp \left( -Ax - \frac{Bc^x - 1}{\log (c)} \right) $$ we find that for the correct parameters $A, B$ and $c$ this formula very closely models the actual number of deaths.

So my question is this, given a data set and a model with unknown parameters, what computational method may be used to approximate the optimal parameters for the model (which most closely fit the given data set)?

As a more simple example, suppose we are given the data set $$ X = \left\\{ 1, 3, 5.1, 7, 9 \right\\} $$ and are required to find the optimal parameters $A$ and $B$ such that the model $$ f(x) = Ax + B $$ most closely fits this data set. As humans, it is clear to see that the optimal parameters are $A = 2$ and $B = 1$. How might a computer deduce these values?

# Answer
> 1 votes
The answer depends on what is your notion of "optimal parameters", and on the specific model you have in mind.

Suppose your model is $f(x,\overline{p})$, where $p$ is the parameters vector, and you wish to find the vector $\overline{p}$ which minimizes $ \sum\limits\_{i=1}^n\left( y\_i-f(x\_i,\overline{p})\right)^2$. This problem is known as least squares fitting, and if your model $f(x,\overline{p})$ is linear, then the optimal value of $\overline{p}$ is given by ${(x^Tx)^{-1}x^Ty}$. For more complicated models, the solution might not be so easy to find analytically, and one might need to settle for approximations. One option is to use iterative methods, such as the Gauss-Newton algorithm.

There is no general way to deal with any type of error function. If for example your cost function does not allow any mistake, and your model $f$ is polynomial in the parameters, then the task reduces to solving a system of polynomial equations. Different types of error functions can take you to different areas in optimization, or even in mathematics in general.

---
Tags: optimization, modelling, numerical-analysis
---


# Question
Title: Is this problem about picking optimal entries of a matrix NP-complete?
I am trying to solve a real-world problem that I was able to reduce to the problem described below. I would like to know the following things:

1. Is there literature about this problem?
2. Is the corresponding decision problem NP-complete?
3. Do you know an efficient algorithm to solve the problem?
4. If not, what would be a good technique to solve it approximately?

The problem is as follows. Given a $n \times m$ matrix $M$ with entries in $\[0, 1\]$, and a function $a \colon \\{1, \ldots m\\} \to \mathbb{N}$. For each column $j$, we want to pick $a(j)$ entries in that column, such that in each row, at most one element was picked. We want to do this in such a way that the sum of the picked values is maximized.

More formally, find a function $T\colon \\{1, \ldots n\\} \to \\{1, \ldots m\\} \cup \\{\bot\\}$ which maps each row to a column (or $\bot$), with the following two properties:

1. $\forall j \in \\{1, \ldots m\\} \colon \lvert T^{-1}(j)\rvert = a(j)$
2. The following expression is maximized: $$ \sum\_{\substack{i=1 \\ T(i) \neq \bot}}^n M\_{i, T(i)} $$

Of course, you could also define it the other way around, with each column mapping to a set of rows. Finally, the corresponding decision problem is in NP, as the function $T$ acts as a certificate. I tried a reduction to knapsack, as the two seem quite similar, but I was unsuccessful.

# Answer
Reduce to maximum-weight bipartite matching.
If you just wanted  for each j, pick *at most* a($\hspace{.015 in}$j) entries from the j-th column ,
then the reduction would be

One of the parts is    one vertex for each row.
The other part is    for each j, a($\hspace{.015 in}$j) vertices for the j-th column .
The weight of each edge is the corresponding matrix entry.

and the reasoning would be

The  one vertex per row  ensures that at most one element will be picked for each row.
The  a($\hspace{.015 in}$j) vertices for the j-th column  allows the j-th column to be
used a($\hspace{.015 in}$j) times but prevents it from being used more than that.
The weights of the edges make the total weights of the matchings
correspond to your objective function.

.

For  for each j, pick *exactly* a($\hspace{.015 in}$j) entries from the j-th column ,  you'd do:
Check whether-or-not    n  \<  a(1) + a(2) + a(3) + ... + a(m-1) + a(m)  .

If that inequality is true, then there are no feasible solutions.

Otherwise, construct the bipartite graph like above but letting the edge weights be
a(1) + a(2) + a(3) + ... + a(m-1) + a(m) + 1  +  the corresponding matrix entry  .
This will make it so that all maximum-weight matchings use the whole column part,
thereby indicating exactly a($\hspace{.015 in}$j) entries for each j-th column.
> 3 votes

---
Tags: optimization, np-complete
---


title: Bin packing with item weight constraint

text:
# Question
Title: Bin packing with item weight constraint
In the bin packing problem, we are given a set of items I={a1,...,an}, each item with weight w\_a1,...,w\_an, and a set of n bins with B={b1,..., bn} all bins with capacity C. I want to restrict the weights of the items to be polynomial in n. Is the problem still being NP-hard (restricting the weight of the items)?

Any information and sources about this would be appreciated.

Thanks.

# Answer
Assuming that you mean the usual bin packing problem, your question is answered on Wikipedia, on the page on strong NP-completeness.

A problem is strongly NP-complete exactly when it remains NP-complete even when the weights are assumed to be of polynomial size (this is not an informal definition, so this should be regarded as an informal notion). Another way to put this is that the problem remains NP-complete even when weights are encoded in unary (the two formulations might not be formally equivalent, but they are morally equivalent). Bin packing is one of the standard examples of a strongly NP-complete problem.
> 1 votes

---
Tags: np-hard, packing
---


# Question
Title: Computational Complexity of Promise Monotone 1 in 3 SAT
Given a 3SAT problem where each clause is a Monotone Clause (i.e. each clause with all positive or negative literals).

Moreover, we are promised that each solution for the above SAT problem (if any exists at all) will be of the form 1 in 3 SAT.

Monotone 1 in 3 SAT is NP Complete, but with the additional promise above, does the problem still remain NP Complete (it obviously is NP) ?

# Answer
> 3 votes
The trivial answer is no, as promise problems cannot be (by definition) in NP, and thus cannot be NP complete. The basic complexity classes e.g. $P, NP$ refer only to decision problems.

However, if you want to relate your promise problem to the standard classes, you can say it is NP-hard in the sense that if it can be solved in polynomial time for inputs in the promise, then $P=NP$.

To see why the above holds, let us introduce some notations. Let $C$ be the set of all monotone clause 3CNF, for which all satisfying assignments are 1 in 3. We shall call this set "the promise". Now your problem is, given an input in $C$, to determine whether it lies in $L\_{yes}=C\cap SAT$, or in $L\_{no}=C\setminus L\_{yes}=C\cap\overline{SAT}$. Given an instance $\varphi$ to monotone clause 1 in 3 SAT, transform it to a monotone clause 3CNF $\psi$ such that $\psi\in C$, and in addition every 1 in 3 satisfying assignment for $\varphi$ also satisfies $\psi$. You can construct $\psi$ by adding clauses which negate conjunctions of pairs of literals in the same clause. Since $\psi\in C$ for every possible $\varphi$, and in addition $\varphi$ has a one in three satisfying assignment iff $\psi\in L\_{yes}$, then solving the promise problem in polynomial time allows you to determine whether $\varphi$ has a one in three satisfying assignment, and thus $P=NP$.

The above basically shows that you can reduce an NP complete problem to your promise problem, but when talking about promise problems the definition of reduction should be slightly adjusted. Let us say that $f$ is a reduction from $L$ to the promise problem $L\_{yes}\cup L\_{no}$ if $Im(f)\subseteq L\_{yes}\cup L\_{no}$ and for every $x$ it holds that $x\in L\iff f(x)\in L\_{yes}$. This is equivalent to saying that $x\in L\Rightarrow f(x)\in L\_{yes}$ and $x\notin L\Rightarrow f(x)\in L\_{no}$ (note that not being in $L\_{yes}$ does not imply being in $L\_{no}$).

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


# Question
Title: What is the definition of$\mathcal{Mod} P$ counting complexity class?
**Question :** What is the definition of $\mathcal{Mod} P$ counting complexity class?

I am not getting anything relevant about this complexity class on Google search. If it is available on Wikipedia, please share a link.

$\mathcal{Mod} P$: A set $L$ is in the class $\mathcal{Mod} P$ if there exist functions $f \in \\#\mathcal{P} $ and $g \in \mathcal{FP}$ such that string $x$, and $g(x) = 0^p$ for some prime $p$ and

$$x \in L \iff f(x) \ncong 0 \pmod{p}\\,.$$

I am not able to understand what it is mean by $g(x) = 0^p$ for some prime $p$.

**Reference :** Köbler and Toda, *On the Power of Generalized MOD-Classes*. In *Proceedings of 8th Annual Structure in Complexity Conference*, IEEE, 1993. PDF

# Answer
The class ModP is defined in Definition 3.1 on page 3 of your reference.

The abstract of the paper clearly states that the paper studies the computational power of the *new* counting class ModP. This suggests that this class is *introduced* in the paper, and in particular, is *defined* in the paper.
> 2 votes

# Answer
The string $0^p$ is simply the string containing $p$ zeroes.
> 2 votes

---
Tags: complexity-theory
---


title: Solving a two-variable recurrence

text:
# Question
Title: Solving a two-variable recurrence
I've written a function. I believe the function runs in complexity:

$$ T(m, n) = \begin{cases} T(m-1, n) + T(m, n-1) + T(m-1, n-1) + 1 &\text{if $m,n\>0$}\\ 0 &\text{otherwise} \end{cases} $$

I have no idea how to simplify this. Can anyone help?

(No, this is not a homework assignment. Well, writing the function was, but after writing it I'm certain that I wrote a very inefficient implementation and am trying to figure out just how bad my version really is.)

# Answer
Let $P = \sum\_{n,m \geq 0} T(n,m) x^n y^m$. We have $$ \begin{align\*} P &= \sum\_{n,m \geq 1} T(n,m) x^n y^m \\ &= \sum\_{n,m \geq 1} \[T(n-1,m) + T(n,m-1) + T(n-1,m-1)+1\] x^n y^m \\ &= \sum\_{n \geq 0, m \geq 1} T(n,m) x^{n+1} y^m + \sum\_{n \geq 1, m \geq 0} T(n,m) x^n y^{m+1} + \sum\_{n,m \geq 0} T(n,m) x^{n+1} y^{m+1} + \sum\_{n,m \geq 1} x^n y^m \\ &= (x+y+xy)P + \frac{xy}{(1-x)(1-y)}. \end{align\*} $$ We deduce that $(1-x-y-xy)P = xy/(1-x)(1-y)$, and so $$ P = \frac{xy}{(1-x)(1-y)(1-x-y-xy)}. $$

At this point we could invoke multivariate asymptotic analysis, but instead we'll connect $P$ to the Delannoy numbers $D(n,m)$, which follow a similar recurrence $D(n,m) = D(n-1,m) + D(n,m-1) + D(n-1,m-1)$, with base case $D(0,0) = 1$. These numbers have generating series $Q = 1/(1-x-y-xy)$. Our formula above shows that $$ P = \frac{x}{1-x} \frac{y}{1-y} Q = \sum\_{n,m \geq 1} x^n y^m Q, $$ and so we obtain the formula $$ T(n,m) = \sum\_{n'\<n,m'\<m} D(n',m'). $$ This formula can also be derived directly in various ways.

Pemantle and Wilson shows that when $n,m \to \infty$ and $n/m,m/n$ are bounded, $$ D(n,m) \sim \frac{nm}{\sqrt{2\pi}(n+m-\sqrt{n^2+m^2})^2\sqrt{n^2+m^2}} \left(\frac{m}{\sqrt{n^2+m^2}-n}\right)^m \left(\frac{n}{\sqrt{n^2+m^2}-m}\right)^n $$ This should be compared to the similar frightening formula for the binomial coefficients, $$ \binom{n+m}{m} \sim \sqrt{\frac{n+m}{2\pi nm}} \left(\frac{n+m}{n}\right)^n \left(\frac{n+m}{m}\right)^m. $$ The asymptotic formula for $D(n,m)$ can probably be used to come up with an asymptotic formula for $T(n,m)$, or one can do the asymptotic analysis directly using the same methods, but I doubt that it would be very useful.
> 2 votes

# Answer
**Hint**: expand the equation: $$T(m,n) = T(m-2,n) + T(m-2, n-1) + T(m,n-2) + T(m-1,n-2) + 3T(m-1,n-1) + 1$$

As $T(m,n)$ is related to $3T(m-1,n-1)$ we can say $T(m,n) = \Omega(3^{min(m,n)})$.
> 1 votes

---
Tags: recurrence-relation
---


title: Iterating over a solid circle of pixels

text:
# Question
Title: Iterating over a solid circle of pixels
Given a 2d array of pixel values, is it possible to iterate over just the pixels in a circle in a way that is less costly than simply iterating over a square and checking if a value is within the circle?

I need to get the values of pixels within a circle given center coordinates and the radius. Ideally I would ONLY iterate over the pixels in the circle as the leave number of iterations possible is the least costly for time.

The only solution I have found so far is to iterate over a square(shown in green below) and for each pixel, check if its inside the circle using pythagoras before performing the logic I wish to do.

Is there a way to only iterate over the solid circle of pixels alone?

(Int the image below, the desired pixels are highlighted in RED and the containing square is in GREEN)

thank you in advance for any help and resources offered

# Answer
The most important optimization is to save resources, not only avoid traversing the full square. For this reason the best option is to calculate the upper quarter of circle (hull) and then use scanlines - traverse row for fixed number of steps. Exploiting symmetry by calculating octant algorithm may not be the best option due to random access in the array and subtraction used (it should make no difference, but it happens). This is know as the midpoint circle algorithm.

Standard way is to calculate 1/8 of the circle, reflect it and use the hull, dividing circle into rows. The naive algorithm to calculate starting points uses round operation, which is time consuming (but still worth something due to actual avoiding square traversal). More optimized version is due to Bresenham circle which avoids rounding operation.
> 1 votes

---
Tags: computational-geometry
---


# Question
Title: Efficient way to get integral points of segment from two points in grid
I have two lattice (grid) end points of the line, how can I generate intermediate points of the line segment between them?
One way is iterate through all the x points or y points and check (solve line equation) if the coordinates we get each time are integral solution or not.

# Answer
> 3 votes
For a line segment defined by two integral lattice points $(x\_0,y\_0), (x\_1,y\_1)$ there will be $gcd(y\_1-y\_0,x\_1-x\_0)-1$ additional integral points along the line segment. To find them move along line by largest value in the reduced slope.

# Answer
> 2 votes
It seems that you are interested in line rasterization or digitization algorithm, meaning that you want efficiently find continous representation of line in discrete grid.
Very efficient algorithm was made by Bresenham. There are other algorithms like DDA, or anialiased Wu line algorithm.

The core idea is to calculate gradient of the line, iterate by discrete step (here exactly pixel) and determine the exact position (one of two adjacent pixels).

---
Tags: algorithms, computational-geometry
---


# Question
Title: Bottom-up algorithm to build subset of maximum weight
I have this problem of obtaining a subset of maximum weight from a given array of size n (the i-th element is the weigth of the item i) - lets call it P. The only restriction is defined by an array R of size n: for each j in R\[i\] we have that the subset can not contain both P\[i\] and P\[j\]. How do I build a DP bottom-up solution for this problem?

# Answer
This is the maximum-weight independent set problem, which is known to be NP-hard. Therefore, there is unlikely to be any efficient solution. However, you could use any of the standard algorithms for this problem, if you're willing to accept an exponential-time algorithm.
> 1 votes

---
Tags: dynamic-programming
---


# Question
Title: Do Nested Monte Carlo Algorithm always find the best score where score is the number of moves on the leftmost path
I am studying Nested Monte Carlo Algorithm addressing the problem of guiding the search toward better states when there is no available heuristic. It uses nested levels of random games in order to guide the search. It consists in two functions : `nested(position, level)` and `sample(position)`

> The basic sample function just plays a random game from a given position, we use the function `play(position, move)` which plays the move in the position and returns the resulting position.

```
int sample (position)
1  while not end of game # I don't understand why did he wrote a while
2    position = play (position,random move)
3  return score

```

If it just played a random game from a given position, shouldn't it have been without a while and only this : `position = play (position,random move)` ? And where does he get the score ?

> The Nested Monte-Carlo Search function plays a game, choosing at each step of the game the move that has the highest score of the lower level Nested Monte-Carlo Search. At each step the algorithm
>
> 1. tries all possible moves
> 2. plays a nested search at the lower level after each move
> 3. memorizes the move associated to the best score of the lower level searches.
>
> As the samples are randomized, it is not guaranteed that a nested search will always improve on previous searches or even lower level searches. In order not to lose the best moves of the best sequence found by a previous search, the algorithm memorizes the best sequence. If none of the moves improve on the best sequence, the move of the best sequence is played, otherwise the best sequence is updated with the newly found sequence and the best move is played:

```
int nested (position, level)
1  best score = -1
2  while not end of game
3    if level is 1
4      move = argmax_m (sample (play (position, m)))
5    else
6      move = argmax_m (nested (play (position, m), level - 1))
7    if score of move > best score
8      best score = score of move
9      best sequence = seq. after move
10   bestMove = move of best sequence
11   position = play (position,bestMove)
12 return score

```

In the following example he claims that if depth first search has one chance out of two of choosing the wrong move at the root, A level 1 Nested Monte-Carlo Search will always find the best score.

Yet I don't get why for the first step. I have some difficulties when starting playing `move = argmax_m (sample ( play (position, m)))`

$$move = \underbrace{argmax\_m (\overbrace{sample ( \underbrace{play (position, m)}\_{(1)})}^{(2)})}\_{(3)}$$

1. so we move first for a given unkown position m. I believe it is chosen by argmax\_m. Yet, how can it chose between both nodes ? Where do we test the score ?
2. Why randomness here ?
3. Where can we test the argmax\_m ?

# Answer
You've asked many questions. The usual rule on this site is to ask one question per post.

The definition of `sample` is correct. `play` evaluates where you end up after making a single move. `sample` evaluates the result of a game where both players randomly choose a move.

In other words, imagine a particularly stupid strategy, where both players randomly pick a move (blindly, without taking into account the position or any other strategy; it's purely random) at each step. Starting from `position`, you could simulate playing out a full game and see what happens. The resulting score (which player won) gives you a *very* crude approximation of how you should evaluate `position`. For instance, suppose in that random playout, the first player happens to win. Then we might suspect that `position` is better for the first player than the second player. Obviously, this is a crude approximation, but it's just a start. And that's what `sample` computes.

So that approach computes the level-0 approximation of the evaluation of each position.

Of course, given a way to compute an evaluation score for any position, that gives you a way to play the game: whenever it is your turn, look at all possible moves you could make, evaluate the resulting position, and pick whichever move takes you to the position that looks most favorable for you. That's what the logic is doing with the `argmax`. So, this gives you a level-0 strategy.

Now we're ready to talk about how to compute a level-1 approximation of the evaluation of each position. Basically, we simulate doing a playout -- we simulate playing the game -- but now rather than using a blind random strategy, we use a slightly smarter strategy. In particular, each player uses the level-0 strategy described above to decide how to move. So now simulate a game where both players are using the level-0 strategy, starting from `position`, and keep going until the end of the game. See which player wins. This is your level-1 evaluation of `position`.

You can use the level-1 evaluation to form a level-1 strategy: always make the move that leads to the position whose level-1 evaluation is as favorable as possible.

And now you can probably see how to use this idea to form a level-2 evaluation, and a level-2 strategy, and a level-3 evaluation, and so on. That's the idea of nested Monte Carlo.
> 0 votes

---
Tags: algorithms, algorithm-analysis, monte-carlo
---


# Question
Title: How to find kth largest element in (max) priority queue in O(m) time?
Here is my exercise.

> FINDLARGEST(k): return the elements in the heap with key \>=k" ... "expand the priority queue (max-heap) so that it supports FINDLARGEST(k) in O(m) time, where m is the number of elements with key\>=k.

Can anyone elaborate on this maybe?

I stumbled upon this on the wikipedia entry on min-max heap: "The structure can also be generalized to support other order-statistics operations efficiently, such as find-median, delete-median,\[6\]find(k) (determine the kth smallest value in the structure) and the operation delete(k) (delete the kth smallest value in the structure), for any fixed value (or set of values) of k. These last two operations can be implemented in constant and logarithmic time, respectively." However, that did not help much.

# Answer
You can implement FINDLARGEST recursively:

```
FINDLARGEST(k, vertex) # call with vertex = root
  if value(vertex) < k: exit the function
  output vertex
  FINDLARGEST(k, left-child(vertex))
  FINDLARGEST(k, right-child(vertex))

```

If there are $m$ vertices whose value is at least $k$, then FINDLARGEST explores at most $3m$ vertices: each eligible vertex together with its two children.
> 2 votes

---
Tags: asymptotics, heaps, selection-problem
---


# Question
Title: Why are the control statements[if-else, while, for] commonly used in programming?
One simple question I've never been able to answer is, "why use 'for', 'while', and 'if' as control statements?"

Could someone please elucidate the rationale behind using the above mentioned control statements, that have been embraced by most, if not all, high-level languages. I believe this has something to do with automata theory, but I'm generally uncertain.

# Answer
> 2 votes
From computability theory, we know that a programming language which only contains terminating programs (say, without loops and recursion) is strictly less powerful than a Turing machine (or any other Turing-complete programming languages).

So, if we want a programming language $P$ which is able to express, say, a Python interpreter, a JVM implementation, or even an interpreter for $P$ itself, we need a language having some sort of unbounded loop / recursion.

Technically, if we have a `while` loop, we no longer need `if`, since

```
if condition then cTrue else cFalse

```

is equivalent to

```
branchTaken = false
while condition and !branchTaken do
   cTrue
   branchTaken = true
while !condition and !branchTaken do
   cFalse
   branchTaken = true

```

where `branchTaken` is an otherwise unused boolean variable. But this is terribly inconvenient to use in practice! So, programming languages tend to include `if`, even if not strictly needed.

Now, about `while` (ans similar unbounded loops). We said that we need some construct for unbounded looping/recursion. Why `while`, then?

Well, recursion alone suffices, but it is not very convenient in imperative programming. Note that, by contrast, functional programming languages typically do not have any `while` loop, and only exploit recursion -- in functional programming, recursion is far more natural and convenient, especially if the language is pure (without side effects) and a WHILE loop would be pointless, since we can not mutate variables.

Most widespread imperative programming languages use `while` or similar loops. In principle, they could instead use `if`+`goto`, which have the same power. However, practice showed that `goto` often led to code which was very hard to read and modify. Dijkstra wrote his famous letter "GOTO considered harmful", advocating for using structured programming (`while` and friends) instead. One of the scientific motivations behind this, is that to properly reason about a `while` loop we need to think about a loop invariant. This is already quite hard, in general. In a `goto`-using program, we need an invariant for every label/line number which is being targeted by some `goto`. This is much harder, in general, since many `goto`s may point to the same label, so the invariant must take into account the multiple "incoming" points. A solution for this could be using `goto` in a more disciplined way, but if we do, we'll probably end up in using `while` (or another loop) under a different notation.

---
Tags: programming-languages
---


# Question
Title: Implementation/translation of the $s^1_1$
This is the Lisp code (from wikipedia) that implements the $s^1\_1$ form of the $s^m\_n$ theorem

```
(defun s11 (f x)
   (let ((y (gensym)))
     (list 'lambda (list y) (list f x y))))

```

since I don't know Lisp, can someone explain me what this code does and/or translate this code into other languages

# Answer
> 1 votes
Roughly, `s11` a program which takes as its first argument a representation of a 2-arguments program e.g. a string like

```
def foo(x,y):
   return g(x,y)

```

and a number `n` as its second argument.

The result of `s11` is the representation of another program, obtained by "hard-coding" the value `n` for `x` in the source code, effectively removing the argument `x`. In the example above we would get the string

```
def newFoo(y):
   return g(n,y)

```

or something equivalent to that, e.g.

```
def newFoo(y):
   return foo(n,x)
def foo(x,y):  # original code unaffected
   return g(x,y)

```

The code posted by the OP does this using LISP lambdas. The part

```
(let ((y (gensym)))

```

generates a new variable name `y`, while

```
(list 'lambda (list y) (list f x y))))

```

returns the representation of the function

$$ \lambda y.\ f (x, y) $$

where `x` is the value to "hard-code" (the one which we called `n` above).

The representation is a LISP s-expression / tree instead of a string, but the concept is the same. LISP is famous for being able to express code as data (roughly as an AST), and being able to run it in a simple way (homoiconicity).

---
Tags: computability
---


# Question
Title: Difference between CNOT and 2nd bit bitflip
I understand how the outcome of each is supposed to be different, but in matrix form are these gates not the same? The CNOT matrix negates the second bit regardless of the input of the first.

# Answer
The controlled NOT gate is represented by the matrix $$ \begin{pmatrix} 1&0&0&0\\ 0&1&0&0\\ 0&0&0&1\\ 0&0&1&0 \end{pmatrix} $$ In contrast, the matrix corresponding to negating the second bit is $$ \begin{pmatrix} 0&1&0&0\\ 1&0&0&0\\ 0&0&0&1\\ 0&0&1&0 \end{pmatrix} $$
> 1 votes

---
Tags: quantum-computing, bit-manipulation
---


title: How can I detect carry and overflow

text:
# Question
Title: How can I detect carry and overflow
What is the diffrence between a **carry** bit and *overflow*

# Answer
**Carry is generally used for unsigned arithmetic and overflow is used for signed arithmetic.**

This unsigned 8-bit operation results in Carry, but no overflow (the sign of the result is correct):

```
0xC0 + 0xD8 = 0x98

```

If we're doing unsigned 8-bit arithmetic, that's fine and we're only interested in the carry bit in this case, which tells us that the "correct" answer is actually `0x198`.

If we look at the same operation and the same operand values, but consider that the operands are signed, we have the equivalent:

```
-0x40 + -0x28 = -0x68

```

In this case, there is also no "overflow" and the result of the arithmetic is correct.

Consider this unsigned operation, however:

```
0x70 + 0x68 = 0xD8

```

No overflow here -- and no carry. The unsigned arithmetic is simple. But now look at the operands as signed values:

```
0x70 + -0x98 = 0x28

```

The answer is obviously wrong. We have subtracted a larger number from a smaller one and ended up with a positive value. The carry is not set here, so it doesn't offer a clue of the problem. The overflow flag reveals that the "correct" signed answer is `-0x28`.

source
> 1 votes

---
Tags: computer-architecture
---


# Question
Title: Why does the given solution to this problem works? How can it's correctness be proven?
This is a question asked in Adobe interview:

> Given heights of n towers and a value k. We need to either increase or decrease height of every tower by k (only once) where k \> 0. The task is to minimize the difference between the heights of the longest and the shortest tower after modifications, and output this difference.

Link of problem and it's solution: solution and problem

Solution posted at the website(click on the link above):

```
// C++ program to find the minimum possible
// difference between maximum and minimum
// elements when we have to add/subtract
// every number by k
#include <bits/stdc++.h>
using namespace std;

// Modifies the array by subtracting/adding
// k to every element such that the difference
// between maximum and minimum is minimized
int getMinDiff(int arr[], int n, int k)
{
    if (n == 1)
       return 0;

    // Sort all elements
    sort(arr, arr+n);

    // Initialize result
    int ans = arr[n-1] - arr[0];

    // Handle corner elements
    int small = arr[0] + k;
    int big = arr[n-1] - k;
    if (small > big)
       swap(small, big);

    // Traverse middle elements
    for (int i = 1; i < n-1; i ++)
    {
        int subtract = arr[i] - k;
        int add = arr[i] + k;

        // If both subtraction and addition
        // do not change diff
        if (subtract >= small || add <= big)
            continue;

        // Either subtraction causes a smaller
        // number or addition causes a greater
        // number. Update small or big using
        // greedy approach (If big - subtract
        // causes smaller diff, update small
        // Else update big)
        if (big - subtract <= add - small)
            small = subtract;
        else
            big = add;
    }

    return  min(ans, big - small);
}

// Driver function to test the above function
int main()
{
    int arr[] = {4, 6};
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 10;
    cout << "\nMaximum difference is "
        << getMinDiff(arr, n, k);
    return 0;
}

```

After trying for around an hour. This is the solution I came up with:

> 1. Sort the array in non decreasing order.
> 2. Initialise two pointers, one at the starting(0th index) and other at the end(n-1 th index) of the array. If the difference between the values at the two pointers is greater than or equal to twice of k, then increment the value at the left pointer by k and decrement the value at the left pointer by k. Get the difference between the new values and update the variable that stores the minimum answer.
> 3. Increment left pointer and decrement right pointer.
> 4. Repeat steps 2 and 3 until left and right pointers converge to the same address.

But the algorithm I wrote only passed sample test cases. When I looked at the editorial, I could not understand why the solution works the way it does. Can anyone break it down step by step.

Also I read in comments it can be solved in O(N). Would be thankful if someone can put insight if that's possible and how. Also where can I practice similar questions?

# Answer
There's a simple $O(n\log n)$ solution. It also sounds plausible that there is a linear time solution, but it seems to require a bit of case analysis.

First of all, instead of either decreasing by $k$ or increasing by $k$, we can first decrease all values by $k$, and then either not change the value or increase it by $\Delta := 2k$.

Suppose now that the sorted list is $x\_1 \< \cdots \< x\_n$. We first show that without loss of generality, an optimal solution increases a prefix of the sorted list. Indeed, consider a solution $y$ which increases $x\_{i+1}$ but not $x\_i$. Let us consider an alternate solution $z$ which doesn't increase $x\_{i+1}$. Denote by $s(y),s(z)$ the *span* of the solution, which is the objective we're trying to minimize. If $s(y) \neq s(z)$ then $s(z)$ involves $z\_{i+1}$, and so $z\_{i+1}$ is an extreme point of $z$. Since $z\_i \< z\_{i+1}$, necessarily $z\_{i+1}$ is a maximum. Let $z\_j$ be the other extreme point of $z$. Since $y\_j = z\_j$, we see that $s(y) \geq y\_{i+1} - y\_j = z\_{i+1} + \Delta - z\_j = s(z) + \Delta$, and so $z$ improves over $y$. We conclude that any optimal solution which increases $x\_{i+1}$ must also increase $x\_i$, and so also $x\_{i-1},\ldots,x\_1$, and generally increases a prefix of $x$.

The $O(n\log n)$ algorithm first sorts the list, and then considers all possible increases of prefixes. The idea is to consider what happens when not changing the list, when increasing $x\_1$, then $x\_1,x\_2$, then $x\_1,x\_2,x\_3$, and so on. At each point of this process, we need to know the span of the solution under consideration. When increasing $x\_1,\ldots,x\_i$, the minimum is always $x\_{i+1}$ (there is no need to consider the case $i=n$). We can determine the maximum in an online fashion: if the maximum is $M$ before increasing $x\_i$, then after increasing $x\_i$ it is $\max(M,x\_i+\Delta)$.

Here is the resulting algorithm, which assumes that we have already sorted the list.

1. Set $M \gets x\_n$ (current maximum).
2. Set $O \gets x\_n - x\_1$ (smallest span currently known).
3. For $i=1,\ldots,n-1$:
    * Set $M \gets \max(x\_i+\Delta,M)$.
    * Set $S \gets M-x\_{i+1}$ (current span).
    * Set $O \gets \min(O,S)$.
4. Return $O$.
> 1 votes

---
Tags: algorithms, data-structures, greedy-algorithms
---


# Question
Title: Does PDA epsilon transition only transition when there's no more input?
For the Pushdown Automata episilon transition $\epsilon$ which is shorthand for $\epsilon; \epsilon / \epsilon$, does this mean that at any point, regargless of if there is input or not, you can transition to the next state? Or does it only transition to the next state when there is no more input?

# Answer
A PDA is always allowed to take $\epsilon$ transitions, just like an NFA. More generally, the PDA is not allowed to peek at anything beyond the current letter. It cannot tell whether it has finished reading the word or not. Whether it can take a transition or not depends only on the contents of the stack and, in the case of a transition "swallowing" an input symbol, on the next symbol in the input (if any).
> 2 votes

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


# Question
Title: Analogy between Gödel's incompleteness proof and Richard's argument
If we take a look at Gödel's paper “On formally undecidable propositions”, the first self referential proof given in the paper, with the following formula:

$$n \in K \equiv \overline{\textit{Bew}}\[R(n); n\]$$

Which look like this in more modern mathematics:

$$K = \\{n \in \mathbb N : \lnot\text{provable}(R\_n(n))\\}$$

Gödel says:

> The analogy of this argument with Richard antinomy leaps to the eye

I'm trying to figure out how this is the case:

I know Richard's Paradox basically uses Cantor's diagonal argument.

Which begins its set description like so:

$$X = \\{s \in S : s \not\in f(s)\\}$$

We can see the similarity between this and and Gödel's argument, especially given that both set/class descriptions end up with a self-referential contradiction.

However, I'm trying to construct a more rigorous comparison between Richard and Gödel's arguments, and how they are considered to be analogical of each other.

In particular, how the contradictions are seen to be analogous by Gödel.

Can anyone help out?

# Answer
> 5 votes
Both examples are instances of *diagonalization*, a technique also used to prove Cantor's theorem ($\kappa \< 2^\kappa$ for all cardinals $\kappa$) and Turing's theorem that the halting problem is undecidable.

An analogy is by nature informal. It is not supposed to be rigorous.

---
Tags: undecidability, proof-techniques, mathematical-foundations, incompleteness
---


# Question
Title: What's the difference between Adaptive Control and a Kalman Filter?
From my basic understanding of Adaptive Control, I understand that it uses the error and the velocity of the error to approximate the error in the solution space of a problem, thus allowing for guaranteed convergence under certain conditions and rapid adaptation to changing conditions. I've accumulated this knowledge basically from anecdotal evidence and from this video.

From my basic understanding of a Kalman Filter, it takes into account the error from past measurements to estimate the current state with greater accuracy.

From my flawed perspective, they seem almost identical, but what's the difference between the two? I've heard anecdotally that they are duals of each other, but that the Kalman Filter is only for linear systems? Is this close to the truth?

# Answer
The Kalman Filter only estimates the current state variables of the system, but doesn't (try to) influence the future state of the system. So a Kalman filter alone is just adaptive observation. **I'm not sure whether it makes sense to say that adaptive observation is dual to adaptive control, because adaptive control implies some observation based feedback mechanism, while adaptive observation is just adaptive over time**, but doesn't need any control based feedback mechanism, even so it doesn't exclude it.

A mathematically pure Kalman filter only applies to (discrete or continuous) linear system of the form $x\_k = F\_k x\_{k-1} + B\_k u\_k + w\_k$ where $F\_k$ and $B\_k$ are matrices, $u\_k$ in the known control signal, $w\_k$ is noise with a Gaussian distribution, and the observed signal is $z\_k = H\_k x\_k + v\_k$ with a matrix $H\_k$ and noise $v\_k$. However, the extended Kalman filter overcomes these restrictions sufficiently well, so that this is no real limitation. However, what stays true is that there should already be a sufficiently accurate model of the system. The noise terms allow to compensate for some model errors, but the overall model still has to be sufficiently predictive, because no adaptive model adjustment is performed, only the current state variables are estimated adaptively.

---

The video shows strongly nonlinear adaptive neural networks. This is completely different from Kalman filters, because here even the model of the system itself is adaptively adjusted. This resembles more closely what we do ourselves, in case our experiences don't match with out expectations and predictions.
> 5 votes

# Answer
These are two fundamentally different parts of control theory, although the way that they work is kindof similar. In a Kalman Filter you *assume* a model for your system and a model for your error and the filter estimates the dynamic states of the model, which change as a function of time. On the other hand, with adaptive control you assume a model, but define some parameters of the model that are unknown. Usually these are assumed to be fixed in time or changing slowly with respect to your system dynamics. The adaptive part then estimates these parameters, and the controller acts accordingly to control the states. You can actual use a Kalman Filter *and* adaptive control at the same time, each one achieving a different control result for your system.
> 4 votes

# Answer
Technically a controller and observer are different by definition. I will illustrate the difference between an adaptive observer, versus a classical observer here. In the classical observer you have the observed signal , $z\_k$ and you estimate $x\_k$ in real time. An adaptive observer would also estimate plant parameters in real time as well, say $F$ in this example (lets not let it change with time). So not only would you have an estimate $\hat x\_k$ but also an estimate of $\hat F\_k$ as well (which can change with each time step as more information is obtained). Look at work by Narendra, Annaswamy, etc.
> 1 votes

---
Tags: machine-learning
---


# Question
Title: implementing ExtractMin on a Max-heap in O(log(n)) time
Is it possible to implement extractMin on a Max-Heap in O(log(n)) time, and if so how? Or do you need a more elaborate structure like a max-min heap?

# Answer
> 1 votes
Suppose that there is an algorithm that examines a complete max-heap (i.e. one in which all leaves have the same depth) and outputs the minimum without accessing all leaves. Whenever the algorithm examines the value of an internal node, hand it the value 2, and whenever it examines the value of a leaf, hand it the value 1. The algorithm misses at least one leaf $\ell$, and so cannot tell the situation in which all leaves have the value 1 from the situation in which all leaves but $\ell$ have the value 1, and $\ell$ has the value 0.

---
Tags: time-complexity, heaps
---


title: Intersection of two independent sets

text:
# Question
Title: Intersection of two independent sets
I am trying to make sure my intuition for the following question from an assignment is correct

Prove or disrove: if $G = (V, E)$ is a graph and $I\_1$ and $I\_2$ are independent sets in $G$, then $I\_1 \cap I\_2$ is an independent set in $G$.

Answer: This statement is true. Consider arbitrary nodes $x, y \in I\_1$ and $u, v \in I \_2$. Since $I\_1$ and $I\_2$ are independent sets in $G$, there is no edge between $\\{x, y\\}$ and there is no edge between $\\{ v, u \\}$. Similarly, here is no edge between $\\{x, u\\}$ and $\\{v, y\\}$ because otherwise, $I\_1$ and $I\_2$ would have to have nodes that are adjacent two each other. We see that $I\_1 \cap I\_2 = \emptyset$ and therefore, the statement that $I\_1 \cap I\_2$ is an independent set in $G$ is vacuously true.

Is this approah necessarily true for any two independent sets in a graph? I would appreciate any feedback

# Answer
> 1 votes
Your proof is unfortunately wrong. Consider what happens when $I\_1 = I\_2$, for example.

The essential reason behind the statement is the following more general fact:

> Any subset of an independent set is an independent set.

You can try proving this rigorously.

---
Tags: sets
---


# Question
Title: Master theorem with $T(n) = 6T(n/10) + \lg^2 n$
So I think this falls under case 1...but I am not sure how to formally prove that $n^{lg\_{10} 6}$ is asymptotically greater than $\lg^2 n$. I tried using L'hopitals but kinda reached a dead end. Here's what i have so far

$$\lim\_{n \rightarrow \infty} \frac{d(\lg^2 n)}{d(n^{\lg\_{10}6})} = \frac{2 \lg n (\frac{1}{n})}{(\lg\_{10}6) n ^{(\lg\_{10}6) - 1}}$$

Is there some better way I can think about proving case 1?

# Answer
> -1 votes
Yuval Filmus pretty much showed the way in the comment above. I will just elaborate on his approach.

First, we raise both to the power **lg610**.

## **(nlg106)lg610** = **n(lg106 x lg610) = n**

and,

## **(lg2n)lg610 = (lg n)2 x lg610 = (lg n)2.57**

Now, taking **log** of both of these, we get **lg(n)** and **2.57xlg(lg(n))** respectively.

**lg(n)** is asymptotically greater than **lg(lg(n))**, and thus, our case is proved.

---
Tags: recurrence-relation, master-theorem
---


title: A general question on NP class problem

text:
# Question
Title: A general question on NP class problem
I read the paper *Certification-Cognizant Time-Triggered Scheduling of Mixed-Criticality Systems* (Baruah and Fohler, in *Proceedings of 32nd IEEE Real Time Systems Symposium*, 2011; see Section 6) which proves a particular problem to be NP-hard in strong sense and in PSPACE. Then they proposed a polynomial algorithm for the same problem which is sufficient but not necessary. For this algorithm, they claim that if the algorithm finds a solution then it is correct. Does this algorithm a verifier type algorithm? I am new to the field of theoretical computer science research. If anyone may explain this concept. Thanks.

# Answer
In short: no, it doesn't follow from the claims you mention that this algorithm is a verifier in a meaningful use of the term.

The paper states:

> Our attempt here is to obtain a polynomial-time algorithm for computing these tables that is sufficient but not necessary, in the following sense. Our algorithm will not be able to generate the scheduling tables for all TT-schedulable instances; however, if the algorithm does generate scheduling tables for an instance, then these tables are correct.

So, they claim to have a polynomial time algorithm that can provide a solution for a subset of all problem instances, but there are some cases for which this algorithm fails to provide a correct solution. Furthermore, they claim elsewhere that there is some characterization of this subset.

By contrast, a *polynomial time verifier* for a certain problem $X$ is an algorithm, that given an problem instance $I$ of $X$ and a certificate $C$, can prove whether the instance is a YES-instance or not in polynomial time. Usually, the certificate corresponds to some 'solution' that the verifier needs to verify correctness for.

So, the algorithm in this paper *can* be called a polynomial time verifier algorithm for the subset it solves in polynomial time *only*, as a polynomial algorithm that solves a problem is also a verifier. But, the claim that this algorithm is a verifier in this sense isn't useful, as it is a strictly weaker property (at least, if $P\neq NP$ ) than being an actual algorithm for the solution.
> 3 votes

---
Tags: algorithms, algorithm-analysis, np-complete
---


# Question
Title: Implementing mathematical theory of arithmetic in Haskell via Curry-Howard correspondence
I have to ask for forgiveness in advance if the whole question doesn't make a lot of sense, but unfortunately, I have no better intuition as of right now and this seems like the best starting point I could come up with.

I'm reading Tarski's book "Introduction to Logic: and to the Methodology of Deductive Sciences", I'm on Part VII Chapter 43 "Primitive terms of the theory under construction; axioms concerning fundamental relations among numbers". It begins by laying out an elementary mathematical theory of arithmetic of real numbers.

The primitive terms are:

* real number (denoted as variables like `x`, `y`)
* is less than (`<`)
* is greater than (`>`)
* sum (`+`)
* `N` meaning "the set of all numbers". Thus, an expression "x is a number" would be written as `x ∈ N`
* is not less than ()
* is not greater than ()

Among the axioms of the theory under consideration, two groups may be distinguished. The axioms of the first group express fundamental properties of the relations less than and greater than, whereas those of the second are primarily concerned with addition. For the time being, we shall consider the first group only; it consists, altogether, of five statements:

* AXIOM 1. For any numbers `x` and `y` (e.g., for arbitrary elements of the set `N`) we have: `x = y` or `x < y` or `x > y`
* AXIOM 2. If `x < y`, then `y ≮ x`
* AXIOM 3. If `x > y`, then `y ≯ x`
* AXIOM 4. If `x < y` and `y < z`, then `x < z`
* AXIOM 5. If `x > y` and `y > z`, then `x > z`

Our next task consists in the derivation of a number of theorems from the axioms adopted by us:

* THEOREM 1. No number is smaller than itself `x ≮ x`
* THEOREM 2. No number is greater than itself: `x ≯ x`

Now I have to stop and finally explain my intentions. I've heard many times about a so-called "Curry–Howard–Lambek correspondence", and it made sense whenever I've read examples of it. I am also not comfortable with manually writing out the reasoning to prove the theorems, I'd like the machinery of going through reasoning steps to be checked by a computer for me.

So, I tried to encode the terms, axioms and potentially theorems (got stuck earlier) in Haskell, but I failed in many ways. I won't show you all the examples of what I did, but here's the most naive approach of encoding propositions as types and their proofs as programs:

```
data Nats
  = NatX
  | NatY
  | NatZ

x :: Nats
x = NatX

data OpGt =
  OpGt Nats
       Nats

data OpLt =
  OpLt Nats
       Nats

data OpEq =
  OpEq Nats
       Nats

data OpNotLt =
  OpNotLt Nats
          Nats

data OpNotGt =
  OpNotGt Nats
          Nats

data Ax1Res
  = Ax1ResLt OpLt
  | Ax1ResGt OpGt
  | Ax1ResEq OpEq

-- how to implement best?
ax1 :: Nats -> Nats -> Ax1Res
ax1 = undefined

-- this doesn't describe the x and y in the type
ax2 :: OpLt -> OpNotGt
ax2 = undefined

```

This piece of code brings more questions than it gives answers:

* should axioms be implemented or kept as unimplemented functions which we just assume to exist?
* how do I limit the implementation of my functions to only rely on available theorems and axioms if I can construct basically any term? Should I hide the constructors?
* types should obviously contain variables like `x` and `y`, I tried that in other approaches but that gets even hairier

My questions are:

* what would be a proper implementation of such proofs in Haskell?
* what materials should I read in order to make a proper implementation myself and understand the topic better?

I hope the vagueness and my level of ignorance in the question will not put you off from answering it. Thank you!

# Answer
> 6 votes
## Proofs in Haskell?

Okay, first let's talk about the Curry-Howard correspondence. This says that one can view theorems as types and proofs as programs. However, it says *nothing* about *which* specific logic a particular programming language represents.

In particular, Haskell lacks dependent types. That means that it can't express statements with "forall x" or "exists x". So immediately there's no way to encode your axioms. The problem is that Haskell's types only let you refer to other types, not to specific values of those types. Your axiom says "forall x and y, Property holds for x and y": it's reasoning not about $Nat$ as a class, but about specific values of that class.

There are ways to fake it in Haskell, by encoding values with a type-level representation, but I'd *strongly* recommend against those for a beginner.

## What does the Curry-Howard Correspondence Actually Mean?

What Curry-Howard is actually saying is not that we can write a program that implements a checker for proofs. What is says is that we can view a proof as a form of a program in a purely-functional language. Specifically, a proof is like a program that takes proofs of its assumptions as input, and produces proofs of its conclusions as outputs.

The key is that propositions are like types, and proofs are like programs. So in your example, it doesn't make sense to have an implementation of your axioms, since axioms are propositions that you take as true, without proof. An implementation would correspond to a proof of them.

The real magic of Curry-Howard comes when we introduce *dependent types*. The key is the dependent function type: instead of just having $A \to B$, we have $(x:A) \to B$, where $x$ can occur in $B$.

There's a lot going on here. First, we've blurred the line between types and values. In the same way that the type constructor `List` takes an argument to become a type, like `List Int`, we now can have type constructors that take *values* as arguments.

The classic example of this is $Eq$ for representing proofs of equality. For any values $x,y$, $Eq\ x\ y$ is the type of proofs that $x = y$. So we have a type indexed on values.

Secondly, we've now given names to our arguments *in the type*, not just in the implementation. So the order of arguments very much matters, because the types on the right can refer to the names on the left. They *depend* on the names, thus the name dependent types. What this is really saying is that the return type of the function can change, depending on the value of the argument given.

Curry-Howard then says that, if we produce a well typed function of type $(x:A) -\> B$, this is the same as saying "for all $x$ that satisfy $A$, $B$ holds".

The dual of this is dependent pairs, which code "exists" proofs. Instead of having the tuple type $(A,B)$, we now have $(x:A, B)$, where $B$ can refer to $x$. This means that the type of the thing on the right can depend on the value of the thing on the left. This is a constructive form of an existential proof: the way you prove "there exists an x satisfying B" is by saying "here's the x, and here's the proof it satisfies B".

## Where to learn more?

If you want to prove things in a formal setting, I'd recommend Coq, Agda, Idris, or Isabelle, since they have the machinery for dealing with dependent types and proving things.

Some good free resources:

Some nice articles/papers/tutorials on the topic include:

The Idris book is popular, but not free: Type Driven Development in Idris

---
Tags: logic, propositional-logic, curry-howard, haskell
---


# Question
Title: What is the best way to algorithmically sort physical boxes?
I work part time at UPS. Part of my job consists of taking boxes from in front of me, determining if the correct cage (1 of 6 moving cages) is behind me (true about 50% of the time), and then putting the box down either in the cage or back in front of me. There can be 6-20 boxes in front of me at any given time depending on box size (essentially the available storage for the sorting algorithm). Each time a box is removed it is replaced with another random box, if there is room for that box. If the next box is particularly large, 3-4 boxes may need to be removed first (meaning that removing a box does not guarantee a new box will appear unless the total number of boxes is sufficiently small). The number of boxes can be considered infinite (UPS does ship nearly all of Amazon’s boxes, after all).

I’m trying to figure out the best strategy for sorting these boxes, partially to work faster and partially for fun.

---

A few more details

* 2 boxes cannot be picked up at the same time (they can be up to 70 lbs). The boxes can, however, be slid sideways. This means a box can be picked up and inserted between other boxes, but two non-adjacent boxes cannot be swapped in a single movement.
* Boxes can be stacked. However, the stack still needs to be put into the cages one by one. Stacking can reduce the number of comparisons needed (because you know all boxes in a given stack go to a certain cage), but not the number of movements required.
* Boxes must be picked up to be evaluated
* 1 cage will disappear and a new cage will appear every 10 seconds, in a predictable order
* If the correct cage is not behind me, I must either wait for the cage or set down the box on the shelf and select a new box

Computational time (seconds)

* Picking up a box: 1
* Evaluating a box: 2
* Placing a box in its original location: 0
* Placing a box in a new location: 1

Examples:

* Picking up a box, determining that the correct cage is not behind me, and putting the box back where it came from: 3 seconds
* Picking up a box, determining the correct cage is behind me, placing the box in the cage: 4 seconds
* Picking up a box from a presorted pile and placing it in the correct cage: 2 seconds
* Picking up a box and placing it in a cage without sorting: 2 seconds (plus the time to find a new job)

For context, the current rate is around 700 boxes per hour (5.14seconds/box). So reducing the average time per box by only 0.5 seconds is a fairly significant change.

What is the most time-efficient way to move the boxes from the shelf to the correct cage? Solutions to simplified versions of this problem are also welcome.

# Answer
> 3 votes
I'll analyze some basic strategies, show that always stacking is best in your model, and then discuss a more sophisticated strategy.

# Analysis of basic strategies: never stack

The simplest strategy is one where you never stack boxes: when you pick it up, if it doesn't belong to a cage behind you, you put it back down where it was. Heuristically, I expect the "never-stack" strategy requires an average of 7 seconds per box. Not good.

Why? We can model the number of times we pick up a box as a geometric distribution with parameter $0.5$; thus the average number of times you need to pick it up is 2. You spend 3 seconds each time you pick it up, including the time to evaluate it; plus 1 second more to place it into the cage, for a total of $2 \times 3 + 1 = 7$ seconds.

I'm making an assumption here that might not be quite right... but it's probably in the ballpark. Anyway, it suggests that "never stack" probably isn't a good strategy.

# Analysis of basic strategies: always stack

The other extreme is to always stack boxes that can't be placed into the cage behind you. I will assume that, as you specified in a comment, for each stacked box you perfectly remember what cage it belongs to, so once a box is stacked you never need to evaluate it again.

This strategy takes 5 seconds per box, which seems pretty good. Why? Look first at the boxes that end up getting stacked. We've spent $1+2+1=4$ seconds for each box in the stack to move it into the stack, and we'll spend $1+1=2$ more seconds per box in the stack to move them all to their cage when it arrives, for a total of $6$ seconds per box. 50% of the boxes get stacked. The total time per unstacked box is 4 seconds, and the total time per stacked box is 6 seconds, for an average time per box of $0.5 \times 4 + 0.5 \times 6 = 5$ seconds.

Not bad. The great thing about always stacking is that you avoid ever evaluating any box twice.

If we think about it a bit more, it appears that "always stack" is the optimal strategy: it's not possible to lower the time per box any further. Once you've picked up a box and know it doesn't belong into a cage behind you, what are your options? You can either stack it or not. If you stack it, it'll take only 2 seconds more to deal with that box in the future. If you don't stack it, it's guaranteed to take at least 3 seconds more to deal with it again in the future, no matter what, maybe more (1 second to pick it up again, 2 seconds to evaluate it). So given your assumption that you memorize the cage number of each stacked box, but don't memorize the cage number of boxes that you didn't stack and put back in their original place -- always stacking is optimal.

So what's wrong with always stacking? Why wouldn't you always want to stack? Stacking does have a cost. It requires enough shelf space for all possible stacks. If shelf space is limited, that might potentially be an issue. Also in practice if you make the shelf too large, then that'll presumably increase the time it takes to pick up boxes and put them down somewhere else (since you have to walk further to reach the place where the stack belongs), so eventually that will be counterproductive. Also, the more stacks you have, the more the burden on your memory (since you have to remember the cage number for each stack), which presumably isn't realistic once the number of stacks gets too large.

So perhaps we should consider "shelf space" or "number of stacks" as a limited resource as well, and consider whether we can construct a strategy that is almost as fast as always stacking, but doesn't require as many stacks. With that motivation, I propose a more complicated strategy, next.

# More sophisticated strategy: limited number of stacks

I'll describe a possible strategy where we try to achieve close to the same efficiency as always stacking, but with a limit on the maximum number of stacks we'll ever have. This allows a tradeoff between shelf space vs time spent per box.

Divide the shelf into two zones, an arrival zone and a holding zone. Divide the holding zone into 10 regions, labelled 0-9. Each region can hold one stack, so at any point we'll have at most 10 stacks. New boxes show up at the arrival zone. I will assume that the cages are numbered sequentially (e.g., currently cages $i,i+1,\dots,i+5$ are behind you and cage $i+6$ will be the next to appear, and cage $i+7$ will be the next after that, and so on).

At each step, pick up a box from the arrival zone. You can pick any one arbitrarily. Evaluate it. If it belongs to one of the cages behind you, put it there. Otherwise, if it belongs to one of the next 10 cages to appear, put it into the holding zone. Select the region corresponding to the last digit of the cage it belongs to. For instance, if it belongs to cage 176, put it in the region labelled 6 of the holding zone.

When a new cage arrives, go to the corresponding region in the holding zone, pick up all of the boxes and place them into the cage. There is no need to evaluate any of them -- you already evaluated them and know which cage they belong in.

In this way, each box gets evaluated only once. It'll either be picked up once and evaluated and placed into its correct cage immediately (takes $1+2+1=4$ seconds), or picked up once, evaluated, moved to a new location, then picked up again and placed into the cage (takes $1+2+1+1+1=6$ seconds). You said about 50% of the time a box can go into its correct cage immediately, so we should expect that the average time per box is $0.5 \times 4 + 0.5 \times 6 = 5$ seconds.

Now here's what I admit this is a little bit of a lie. I oversimplified. I assumed that if you pick up a package and it isn't in the cage behind you, then it will belong to one of the next 10 cages. But what if it doesn't? What if it belongs to a cage that won't appear until even further in the future? This is the bad case. In this bad case, all you can do in this strategy is put it back into the arrival zone. Eventually, at some point in the future it'll be picked up again, and maybe then you can do something more productive with it. The cost, though, is that this means occasionally a box will have to be evaluated more than once.

So in reality, the actual average time per box will be more than 5 seconds per box. It might not be too much more. But exactly how much more depends on how often you pick up a box and discover it belongs to a cage that won't appear for a long time (how often the bad case occurs).

Of course the number 10 (the number of regions in the holding zone) is arbitrary and can be tuned. You can make it larger, to reduce how often the bad case arises; this will reduce the average time per box, at the cost of increasing the amount of shelf space you need. Of course, in practice if you make the shelf too large, then that'll actually increase the time it takes to pick up boxes and put them down somewhere else, so eventually that will be counterproductive. Alternatively, you can make that number smaller; this will reduce the amount of shelf space needed, at the cost of increasing the average time per box.

So I think this is worth a try. Its effectiveness will depend on details of the distribution of when boxes arrived vs when their cage appears, which aren't specified in the question, but if you have data on that, you should be able to simulate this strategy and see how well it will work.

# Second-level refinement of the above strategy

If you like this strategy, there is a refined version of it you could also consider. The refined version is more complicated but might reduce time per box even a little further. Divide the shelf into three zones, an arrival zone, a holding zone, and purgatory. The holding zone is divided into 10 regions, labelled 0-9, as before. Purgatory is also divided into 10 regions, labelled 0-9.

The scheme is exactly as before. The only difference is what we do if you pick up a box and discover its correct cage is at least 10 cages into the future, but less than 100 cages into the future. In that case, you put it into purgatory. You place it into the region corresponding to the next-to-last digit of the cage it belongs to. For instance, if you currently handling cages 112-117, and you pick up a box that belongs to cage 176, then you can't put it into the holding zone, but you can put it into purgatory; and you put it into the region labelled 7 of the purgatory.

Now, when a new cage arrives, do the same as before to move all boxes from the corresponding region of the holding zone into the cage. Also, for every 10th cage that arrives -- in particular, when a cage arrives whose last digit is 5 -- go to the corresponding region in purgatory and sort all of those boxes into the cages or the holding zone. About 60% of those boxes can be placed directly into a cage behind you, and the remaining 40% can go into the holding zone.

Again, there is nothing special about the numbers 10 here. You can adjust the number of regions in the holding zone, and the number of regions in purgatory (they don't need to be the same number, either), to trade off shelf space vs time per box. I don't know whether the extra complexity of this scheme will be worthwhile, but it's a natural extension to the idea above.

---
Tags: algorithms, sorting, radix-sort
---


# Question
Title: Is it possible to find the nodes larger than k in a min-max heap in O(m) time?
Is it possible to find the nodes larger than $ k $ in a min-max heap in $ O(m) $ time, where $ m $ is the number of nodes larger than $ k $?

If it *is* possible, then how do I implement the rest of the standard heap procedures in standard time (insert and delete, extract min and extract max is easy obviously)?

---

If needed the whole problem statement goes like this:

We want to add operation to our (max) priority queue. We are interested in adding the following operation. Below, `x` and `y` are objects and `x.key` and `y.key` are their keys in the priority queue (the objects can also have other satellite data). If an implementation of the priority queue is done as in *CLRS, chapter 6*, then the table can be a table of objects – not numbers; in that case `x` and `y` can have an attribute `i`, so that `x.i` and `y.i` denote their places (indices) in the table.

* `REMOVELARGEST(m)`: remove the `m` largest elements in the heap
* `DELETE(x)`: remove the element x from the heap.
* `FUSION(x,y)`: remove `x` and `y` from the heap and add the element `z` with key `x.key+y.key`
* `EXTRACTMIN`: remove and return the element with the smallest key

---

1. Expand the priority queue to support `REMOVELARGEST(m)` in $ O(m\*log(n)) $ time.
2. Expand the priority queue to support `DELETE` and `FUSION` in $ O(log(n)) $ time
3. Expand the priority queue to support `FINDLARGEST(k)` in $ O(m) $ time, where $ m $ is the number of elements $ \>=k $.
4. Expand the priority queue to support `EXTRACTMIN` in $ O(log(n)) $ time.

# Answer
You can use a max-heap and a min-heap containing the same elements, with pointers joining pairs of identical elements in both heaps. This allows supporting all the usual operations in logarithmic time, and the new operation (finding all nodes larger or smaller than a given value) in time linear in the output size.
> 1 votes

---
Tags: time-complexity, heaps
---


# Question
Title: Counter-example to regular expression statement
Show a counter-example to disprove the following statement:

If $R1$ and $R2$ are two regular expressions, then $L((R1 \cup R2)^\*) = L(R1^\* \cup R2^\*)$.

# Answer
Let $\\{a\\} = R1$ and $\\{b\\} = R2$. $'aba'$ belongs to $L((R1 \cup R2)^\*)$ but not to $L(R1^\* \cup R2^\*)$.

explentation:

$'aba'$ belongs to $L((R1 \cup R2)^\*)$ since $a$ belongs to $R1$ than with using the $\*$ itiration we take $b$ from $R2$ than again we take $a$ from $R1$ by using $\*$

$'aba'$ does not belong to $L(R1^\* \cup R2^\*)$ excepts only $a^n$ or $b^m$.

this answer is based on @Yuval Filmus
> 1 votes

---
Tags: automata, regular-expressions
---


title: Regular Expression Building

text:
# Question
Title: Regular Expression Building
I'm having trouble constructing a regular expression to meet the following criteria:

$$\sum = \\{0,1\\}$$

$$\epsilon \in L$$

$$0 \in L$$

$$1 \in L$$

$$\forall x \in L, 110x \in L \land x01 \in L$$

What I have so far is: $$((1^\*0)^\*(0+1)^\*(01)^\*)^\* \text{ or } (1^\*(0+1)^\*)$$

However I dont believe this to be fully correct because the $1^\*$ implies that not only can $110x \in L$ be true, but so can $1111110x \in L$. Not sure to to structure it such that only the first exists or doesnt.

What really throws me off is Kleene's closure. Because say $(1^\*0)^\*$ is grouped with a $^\*$, that means it may be any combination of whats inside, including nothing at all right? The $\epsilon$ string?

Surely it is not as easy as:

$$(0+1)^\*$$

Because $1100000001010101011101010$ would be captured by that expression right?

# Answer
> 0 votes
To check whether your proposed solution is correct, check each of the criteria to see whether the criteria is met. Then you will know whether your candidate solution is correct.

Yes, the language $(1^\*0)^\*$ includes the empty string. That follows from the definition of the Kleene star. When it doubt, look up the definition and see what it says.

If you want a more systematic way to find a solution to this kind of problem -- or if you want to find the smallest language that satisfies these conditions, as you later suggest in a comment -- here's a big hint for how to do that:

> Construct a grammar for a language that meets these criteria. What kind of grammar is it? What can you do with that?

It's your exercise, so I'll let you work out the details for yourself and have the joy of solving it on your own.

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


# Question
Title: Implementing SUM(i,j) and CHANGE(i,j) in O(log(n)) using a datastructure with O(n) space complexity
I have two operations:

$Sum(i,j)$ : Calculate $A\[i\]+A\[i+1\]+....+A\[j\]$

$Change(i,x)$: Set $A\[i\]=x$

I need to implement these operations in an appropriate data structure using $O(n)$ space ($n$ is the length of the input array $A$).

The $Sum(i,j)$ procedure needs to have a runtime complexity of $O(\log(n))$ and the $Change(i,x)$ procedure needs to have a runtime of $O(\log(n))$.

I thought about using a heap seeing as change-key in a heap is $O(\log(n))$, but I cant figure out how exactly to get the $Sum(i,j)$ procedure down to $O(\log(n))$. To me it seems you would need $O(n)$ time to do this. If anyone could nudge me in the right direction I would appreciate it.

# Answer
> **What is a Segment Tree?**

It is a data structure which is used to operate over a range of input.

> **How does it work?**

The original elements of the array form the leaves of the tree. Each internal node represents some merging of the sub trees. For example consider the array $A = \[1,5,7,8,9,15\]$.

If we were to construct a segment tree out of the array with the sum operation in mind, we would have the following tree.

> **What about the run time complexity?**

If we try to implement the $Sum(i,j)$ and $Change(i,x)$ operations via a segment tree, the time complexity would be the following:

* Construction of the Segment Tree: This would take $O(n)$ time.
* $Sum(i,j)$ : This would take $O(\log(n))$ time.
* $Change(i,x)$ : This would take $O(\log(n))$ time.

> **What about the space complexity?**

Being an almost complete binary tree, a Segment tree with $n$ leaf nodes will have $2n — 1$ total nodes. Hence the space complexity will be $O(n)$.
> 1 votes

---
Tags: data-structures, time-complexity, heaps, subsequences
---


title: Online Set Filling

text:
# Question
Title: Online Set Filling
Suppose we have 3 sets $A, B, C$ which can can hold a maximum of **two** elements, each. So the total number of elements that the sets can hold together i.e. total capacity (TC) is $ 3\*2 = 6$.

Now, elements arrive serially (one-by-one) with some properties that impose the following constraints:

```
E1 : Can be placed in either A or B but not C.
E2 : Can be placed in either B or C but not A.
E3 : Can be placed in either A or C but not B.
E4 : Can be placed in only B.

```

Given that we have no prior knowledge about these elements, the challenge is to distribute these elements into the sets $A, B, C$ such that the properties are satisfied.

Here we can see that the total number of incoming elements are $4$ and TC is $6$.

*Assumption* : *There always exists a feasible solution*

**Question** : What algorithmic approach is appropriate for this situation? Again I stress that we have no *apriori* knowledge about the elements.

# Answer
> 1 votes
There's no way to guarantee that you will find such an assignment, if you have to do it on the fly.

For example, suppose E1's constraint is "Can be placed in either A or B but not C". Now you decide which set you want to put it into (A or B).

* If you decide A, maybe E2's constraint will be "Can only be placed in A" and E3's constraint will be "Can only be placed in A" and you are hosed. At that point there's no way you can satisfy all the constraints (even though in retrospect there does exist a way to satisfy the constraints, there's no way to reach it once you decide to put E1 into A).
* If you decide E1 goes into B, maybe E2's constraint will be "Can only be placed in B" and E3's constraint will be "Can only be placed in B" and you are still hosed. You are stuck and won't be able to satisfy all the constraints.

Of course, at the time you see E1, you don't know which one of those situations it will turn out to be. So no matter what you pick after seeing the constraint for E1, there's a chance you will end up stuck. You cannot guarantee to always find such an assignment -- not even if you are promised that one exists.

If you knew all of the constraints before having to make any selections, then it would be feasible (e.g., brute force suffices). But that doesn't work on the fly.

This is an example of what's known as an "adversarial argument": no matter what choice your algorithm makes, an adversary can always arrange to screw you over.

---
Tags: algorithms, combinatorics, online-algorithms
---


# Question
Title: Median of Medians Recurrence Relation for 3-grouping
So I am trying to figure out the recurrence relation for the median of medians algorithm using groups of 3 instead of groups of 5. Per CLRS's method, my recurrence relation looks like

$$ T(n) = T(\lceil \frac{n}{3} \rceil) + T(\frac{2n}{3} + 4) + c\_1n $$

And I want to show $T(n) = O(n \lg n)$

Via substition, I assume inductively that

$T(n') = cn' \lg n'$

So by substition

$$T(n') \leq c\lceil \frac{n'}{3} \rceil \lg \lceil \frac{n'}{3} \rceil + c(\frac{2n'}{3} + 4) \lg (\frac{2n'}{3} + 4) + c\_1n' $$

$$ \leq c (\frac{n'}{3} + 1) \lg (\frac{n'}{3} + 1) + c(\frac{2n'}{3} + 4) \lg (\frac{2n'}{3} + 4) + c\_1n'$$

aaand now im stuck. Is there anyway i can drop the +1 and +4 from this expression to make it simpler?

# Answer
You can use the inequality $\log (1+x) \< x$ (valid for $x \> 0$, where $\log$ is the natural logarithm), which follows from a Taylor expansion, to reason as follows: $$ \log \left(\frac{n'}{3} + 1\right) = \log \left(\frac{n'}{3} \cdot \left(1 + \frac{3}{n'}\right)\right) = \log \frac{n'}{3} + \log \left(1 + \frac{3}{n'}\right) \< \log \frac{n'}{3} + \frac{3}{n'}. $$ This shows (after some calculation) that you can remove the $+1$ and $+4$ in return for an additional constant additive term, that is, you can estimate your final line by $$ c \left(\frac{n'}{3}+1\right) \lg \frac{n'}{3} + c\left(\frac{2n'}{3}+4\right) \lg \frac{2n'}{3} + M + c\_1 n', $$ where $M\>0$ is some constant.
> 3 votes

---
Tags: algorithms, recurrence-relation, selection-problem
---